MeMOry RePlacement alGorithms
stau.space
1import sys
2from typing import NamedTuple
3
4# Folding function.
5def fold(f, z, l):
6 # This is a simple for loop that accumulates a value and then returns it.
7 for x in l:
8 z = f(z, x)
9 return z
10
11# This is what the algorithm uses to tell whether a page was used or not.
12class Bits(NamedTuple):
13 read: bool
14 write: bool
15
16# This class manages the state of physical/virtual memory.
17class State(NamedTuple):
18 faults: int
19 hits: int
20 order: list[int]
21 page_table: dict[int, Bits]
22 physical_capacity: int
23
24 # Increase hits by 1.
25 def hit(s):
26 return State(s.faults, s.hits + 1, s.order, s.page_table, s.physical_capacity)
27
28 # Increase faults by 1.
29 def fault(s):
30 return State(s.faults + 1, s.hits, s.order, s.page_table, s.physical_capacity)
31
32 # Change the mode on a page.
33 def modify(s, page, mode):
34 return State(s.faults, s.hits, s.order, s.page_table | {page: Bits(mode, False)}, s.physical_capacity)
35
36 # Make space in physical memory depending on the order.
37 def evict(s):
38 def rec(page_table, order, page):
39 # if the page table says that the page's R bit was set:
40 if page_table[page].read == True:
41 # rotate the queue: s_.order[1:] + [page]
42 # change the current page's R bit to False: s_.page_table | {page: Bits(False, False)}
43 # the next page to check for is: s_.order[0]
44 return rec(page_table | {page: Bits(False, False)}, order[1:] + [order[0]], order[0])
45 else:
46 return page, order
47 last_page, new_order = rec(s.page_table, s.order[1:] + [s.order[0]], s.order[0])
48 # Finally, return the new state, without that page.
49 return State(s.faults, s.hits, new_order[:-1], {k: v for k, v in s.page_table.items() if k != last_page}, s.physical_capacity)
50
51 # This function simply inserts a page into the page table.
52 def insert(s, page):
53 return State(s.faults, s.hits, s.order + [page], s.page_table | {page: Bits(False, False)}, s.physical_capacity)
54
55# This is the algorithm for second chance page replacement.
56def second(state, access) -> State:
57 page = access[1]
58 # If the page is in the page table, that is a page hit.
59 if page in state.page_table:
60 # Also, the page's R bit must be set to 1.
61 return state.modify(page, True).hit()
62 else:
63 # If there isn't any space in the page table, call make_space()
64 if len(state.page_table) == state.physical_capacity:
65 return state.evict().insert(page).fault()
66 else:
67 # If there is space in the page table, we can simply insert the page.
68 return state.insert(page).fault()
69
70def main():
71 # The user must provide the physical capacity and the file path to the
72 # access sequence.
73 if len(sys.argv) != 3:
74 print("USAGE:", sys.argv[0], "number_of_pages", "file_path")
75 print("\twhere:\n\t\tnumber_of_pages : int\n\t\tfile_path : string")
76
77 # The second argument is the file path.
78 file_path = sys.argv[2]
79
80 # This simply parses the access sequence file.
81 accesses = []
82 with open(file_path) as f:
83 accesses = [(x.split(":")[0], int(x.split(":")[1])) for x in f.read().split()]
84
85 # The physical capacity is the first argument.
86 limit = int(sys.argv[1])
87 # The result is simply the evaluation of the second algorithm on the access
88 # sequence.
89 res = fold(second, State(0, 0, [], dict(), limit), accesses)
90
91 # Print the result.
92 print("Faults:", res.faults, "\nHits:", res.hits)
93
94main()