stau.space
MeMOry RePlacement alGorithms
1# MeMOry page RePlacement alGorithms (MMORPG)
2
3This project had several goals:
4- find what each of the page replacement algorithms (PRA) share in common.
5- try to use functional programming patterns to implement each algorithm[1].
6- implement the algorithms correctly.
7
8Some caveats:
9- [1]: I tried avoiding mutation and loops. For example, the only use of `for`
10 loops happens in "list-comprehensions", and list-comprehensions are
11 equivalent to `list(map(...))`.
12
13The first item was rather simple, after implementing all three algorithms, I
14have come to the conclusion:
15> All PRA's are basically a function that, depending on the current state of the
16> memory, take in a page access and return a new state of memory.
17
18Because of this, the "prototype" for these functions is the following:
19```python
20def optimal(state: State, access: tuple[str, int]) -> State:
21 pass
22
23def second(state: State, access: tuple[str, int]) -> State:
24 pass
25
26def wsclock(state: State, access: tuple[str, int]) -> State:
27 pass
28```
29
30They are all functions that return a new state, given a previous state and a
31memory access. Executing these algorithms then consists of running each
32algorithm on the sequence of accesses while accumulating some state. For this, I
33implemented the usual `fold` algorithm used in many other programming languages:
34
35```python
36#Folding function.
37def fold[T, U](f: Callable[[U, T], U], z: U, l: list[T]) -> U:
38 # This is a simple for loop that accumulates a value and then returns it.
39 for x in l:
40 z = f(z, x)
41 return z
42```
43
44In this case `z` is the state, `f` is the accumulating function and `l` is the
45sequence that is used.
46
47Then, for the implementation of each algorithm.
48
49## Second chance
50
51The algorithm basically has two parts:
52- the access' page is in the page table: and this is considered a page hit
53- the access' page is not in the page table: this is a page fault and the page
54 must be inserted into the page table. If the page table is full, then a page
55 must be evicted.
56
57This process will seem very similar to the other algorithms.
58
59```python
60def second(state: State, access: tuple[str,int]) -> State:
61 page = access[1]
62 if page in state.page_table:
63 return state.modify(page, True).hit()
64 else:
65 if len(state.page_table) == state.physical_capacity:
66 return state.evict().insert(page).fault()
67 else:
68 return state.insert(page).fault()
69```
70
71## Optimal
72
73This is a very similar algorithm to the previous. In this case, thhe only
74difference is that we use the method `update()` to update the indices that are
75used to decide what page to evict.
76
77```python
78def optimal(state: State, access: tuple[str,int]) -> State:
79 page = access[1]
80 if page in state.page_table:
81 return state.update().hit()
82 else:
83 if len(state.page_table) == state.physical_capacity:
84 return state.evict().insert(page).update().fault()
85 else:
86 return state.insert(page).update().fault()
87```
88
89## WSClock
90
91This was also very similar to the previous two, except that there is a method
92for modifying a page depending on the access mode
93(`modify(page, True, mode == "W")`) and a method for updating the list of
94indices (`update()`).
95
96```python
97def wsclock(state: State, access: tuple[str,int]) -> State:
98 mode, page = access
99 assert mode in {"R", "W"}
100 if page in state.page_table:
101 return state.modify(page, True, mode == "W").update().hit()
102 else:
103 if len(state.page_table) == state.physical_capacity:
104 return state.evict().insert(page).update().fault()
105 else:
106 return state.insert(page).update().fault()
107```
108
109## General
110
111Then, each state must implement these algorithms. The details for the
112implementations of these algorithms are all in their respective files. Most of
113the heavy lifting for these algorithms occurs inside the implementation of
114`evict()` since that is where most of these algorithms differ.
115
116One more thing, each algorithm's file is accompanied with an untyped version of
117that file, suffixed with `*_bare.py`. This is useful in case your python
118implementation doesn't use the fancier type hints that more modern versions of
119Python have.
120
121# Running
122
123To run the second-chance algorithm:
124
125```sh
126python second.py number_of_pages file_path
127```
128
129To run the optimal algorithm:
130
131```sh
132python optimal.py number_of_pages file_path
133```
134
135To run the WSClock algorithm:
136
137```sh
138python wsclock.py number_of_pages tau file_path
139```
140
141# References
142
143I would like to thank Yadiel Mercado, Uriel Fuentes, for helping me debug and
144implement the algorithms; Jantony Velazquez for helping me understand functional
145programming patterns better; and Sebastian Ramirez for giving me advice on how
146to make my code more readable.
147
148I enjoyed working on this project a lot, so if you have any questions, feel
149free to contact me!