PagingAlgorithm - MoriMoin

LRU

least recentry used page is replaced.

   1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
pages = [[None, 0], [None, 0], [None, 0] , [None, 0]]
access = "ABCDCEACBCDCAFBC"

time = 1
for char in access:
    candidate = [None, 999]
    for page in pages:
        if page[0] == char:
            candidate = page
    if not candidate[0]:
        for page in pages:
            if candidate[1] > page[1]:
                candidate = page
        candidate[0] = char
    candidate[1] = time

    print time, pages
    time = time + 1

output

1 [['A', 1], [None, 0], [None, 0], [None, 0]]
2 [['A', 1], ['B', 2], [None, 0], [None, 0]]
3 [['A', 1], ['B', 2], ['C', 3], [None, 0]]
4 [['A', 1], ['B', 2], ['C', 3], ['D', 4]]
5 [['A', 1], ['B', 2], ['C', 5], ['D', 4]]
6 [['E', 6], ['B', 2], ['C', 5], ['D', 4]]
7 [['E', 6], ['A', 7], ['C', 5], ['D', 4]]
8 [['E', 6], ['A', 7], ['C', 8], ['D', 4]]
9 [['E', 6], ['A', 7], ['C', 8], ['B', 9]]
10 [['E', 6], ['A', 7], ['C', 10], ['B', 9]]
11 [['D', 11], ['A', 7], ['C', 10], ['B', 9]]
12 [['D', 11], ['A', 7], ['C', 12], ['B', 9]]
13 [['D', 11], ['A', 13], ['C', 12], ['B', 9]]
14 [['D', 11], ['A', 13], ['C', 12], ['F', 14]]
15 [['B', 15], ['A', 13], ['C', 12], ['F', 14]]
16 [['B', 15], ['A', 13], ['C', 16], ['F', 14]]

FINUFO

first in not used first out, (also known as second chance)

   1 
  2 
  3 
  4 
  5 
  6 
  7 
  8 
  9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
pages = [[None, 0], [None, 0], [None, 0] , [None, 0]]
pagehash = {}

access = "ABCDCEBABCDCAFBC"

needle = -1
time = 1
for char in access:

    if pagehash.has_key(char):
        page = pagehash[char]
        page[1] = 1
    else:
        while 1:
            needle = (needle + 1) % len(pages)
            page = pages[needle]
            if page[1] == 0:
                if pagehash.has_key(page[0]):
                    del pagehash[page[0]]
                page[0] = char
                pagehash[char] = page
                break
            page[1] = 0
            print time,"(",char ,")", needle, pages

    print time,"(",char ,")", needle, pages
    time = time + 1

output

1 ( A ) 0 [['A', 0], [None, 0], [None, 0], [None, 0]]
2 ( B ) 1 [['A', 0], ['B', 0], [None, 0], [None, 0]]
3 ( C ) 2 [['A', 0], ['B', 0], ['C', 0], [None, 0]]
4 ( D ) 3 [['A', 0], ['B', 0], ['C', 0], ['D', 0]]
5 ( C ) 3 [['A', 0], ['B', 0], ['C', 1], ['D', 0]]
6 ( E ) 0 [['E', 0], ['B', 0], ['C', 1], ['D', 0]]
7 ( B ) 0 [['E', 0], ['B', 1], ['C', 1], ['D', 0]]
8 ( A ) 1 [['E', 0], ['B', 0], ['C', 1], ['D', 0]]
8 ( A ) 2 [['E', 0], ['B', 0], ['C', 0], ['D', 0]]
8 ( A ) 3 [['E', 0], ['B', 0], ['C', 0], ['A', 0]]
9 ( B ) 3 [['E', 0], ['B', 1], ['C', 0], ['A', 0]]
10 ( C ) 3 [['E', 0], ['B', 1], ['C', 1], ['A', 0]]
11 ( D ) 0 [['D', 0], ['B', 1], ['C', 1], ['A', 0]]
12 ( C ) 0 [['D', 0], ['B', 1], ['C', 1], ['A', 0]]
13 ( A ) 0 [['D', 0], ['B', 1], ['C', 1], ['A', 1]]
14 ( F ) 1 [['D', 0], ['B', 0], ['C', 1], ['A', 1]]
14 ( F ) 2 [['D', 0], ['B', 0], ['C', 0], ['A', 1]]
14 ( F ) 3 [['D', 0], ['B', 0], ['C', 0], ['A', 0]]
14 ( F ) 0 [['F', 0], ['B', 0], ['C', 0], ['A', 0]]
15 ( B ) 0 [['F', 0], ['B', 1], ['C', 0], ['A', 0]]
16 ( C ) 0 [['F', 0], ['B', 1], ['C', 1], ['A', 0]]