MeMOry page RePlacement alGorithms (MMORPG)#

This project had several goals:

• find what each of the page replacement algorithms (PRA) share in common.
• try to use functional programming patterns to implement each algorithm[1].
• implement the algorithms correctly.

Some caveats:

• [1]: I tried avoiding mutation and loops. For example, the only use of for loops happens in "list-comprehensions", and list-comprehensions are equivalent to list(map(...)).

The first item was rather simple, after implementing all three algorithms, I have come to the conclusion:

All PRA's are basically a function that, depending on the current state of the memory, take in a page access and return a new state of memory.

Because of this, the "prototype" for these functions is the following:

def optimal(state: State, access: tuple[str, int]) -> State:
    pass

def second(state: State, access: tuple[str, int]) -> State:
    pass

def wsclock(state: State, access: tuple[str, int]) -> State:
    pass

They are all functions that return a new state, given a previous state and a memory access. Executing these algorithms then consists of running each algorithm on the sequence of accesses while accumulating some state. For this, I implemented the usual fold algorithm used in many other programming languages:

#Folding function.
def fold[T, U](f: Callable[[U, T], U], z: U, l: list[T]) -> U:
    # This is a simple for loop that accumulates a value and then returns it.
    for x in l:
        z = f(z, x)
    return z

In this case z is the state, f is the accumulating function and l is the sequence that is used.

Then, for the implementation of each algorithm.

Second chance#

The algorithm basically has two parts:

• the access' page is in the page table: and this is considered a page hit
• the access' page is not in the page table: this is a page fault and the page must be inserted into the page table. If the page table is full, then a page must be evicted.

This process will seem very similar to the other algorithms.

def second(state: State, access: tuple[str,int]) -> State:
    page = access[1]
    if page in state.page_table:
        return state.modify(page, True).hit()
    else:
        if len(state.page_table) == state.physical_capacity:
            return state.evict().insert(page).fault()
        else:
            return state.insert(page).fault()

Optimal#

This is a very similar algorithm to the previous. In this case, thhe only difference is that we use the method update() to update the indices that are used to decide what page to evict.

def optimal(state: State, access: tuple[str,int]) -> State:
    page = access[1]
    if page in state.page_table:
        return state.update().hit()
    else:
        if len(state.page_table) == state.physical_capacity:
            return state.evict().insert(page).update().fault()
        else:
            return state.insert(page).update().fault()

WSClock#

This was also very similar to the previous two, except that there is a method for modifying a page depending on the access mode (modify(page, True, mode == "W")) and a method for updating the list of indices (update()).

def wsclock(state: State, access: tuple[str,int]) -> State:
    mode, page = access
    assert mode in {"R", "W"}
    if page in state.page_table:
        return state.modify(page, True, mode == "W").update().hit()
    else:
        if len(state.page_table) == state.physical_capacity:
            return state.evict().insert(page).update().fault()
        else:
            return state.insert(page).update().fault()

General#

Then, each state must implement these algorithms. The details for the implementations of these algorithms are all in their respective files. Most of the heavy lifting for these algorithms occurs inside the implementation of evict() since that is where most of these algorithms differ.

One more thing, each algorithm's file is accompanied with an untyped version of that file, suffixed with *_bare.py. This is useful in case your python implementation doesn't use the fancier type hints that more modern versions of Python have.

Running#

To run the second-chance algorithm:

python second.py number_of_pages file_path

To run the optimal algorithm:

python optimal.py number_of_pages file_path

To run the WSClock algorithm:

python wsclock.py number_of_pages tau file_path

References#

I would like to thank Yadiel Mercado, Uriel Fuentes, for helping me debug and implement the algorithms; Jantony Velazquez for helping me understand functional programming patterns better; and Sebastian Ramirez for giving me advice on how to make my code more readable.

I enjoyed working on this project a lot, so if you have any questions, feel free to contact me!