Programming Assignment $3-$ Virtual Memory Manager

Due Date: Friday, April $26,2024,11$:$59$pm CDT

In this assignment, you will design and implement a virtual memory manager with paging, and then

simulate its operation for each of the following page replacement algorithms: LIFO $($last$-$in$-$first$-$out

or stack$),$ MRU $($most recently used$),$ LRU$-$X $($replace the page whose K$-$th most recent acoess is

furthest in the past; for example, LRU$-1$ is simply LRU while LRU$-2$ replaces pages according to

the time of their penultimate access; LRU$-$K improves significantly on LRU with regard to locality

in time$),$ LFU $($least frequently used$),$ OPT$-$lookhead$-$X $($optimum with lookahead of X future

addresses$),$ and WS $($Working Set$).$ There will be $6$ sets of output from these $6$ runs.

The information provided here is intended to guide you in your design; it is not a complete

description of all issues that must be considered. The assignment requires a combination of

Unix$/$Linux processes $($such as the page fault handler, disk driver, and page replacement process$)$

synchronized by Unix$/$Linux semaphores, and simulators $($such as the paging disk$).$

Data Structures:

You may add additional fields to these data structures if needed in your design. There is one page

table per address space $($process$),$ and one table entry per page. The address can thus be divided

into $2$ parts: page number and displacement $($offset$).$

A single frames table contains the address space and page number of the page currently occu$-$

pying each page frame. The format of the entry for frame $f$ is:

FRAMES$[$f$]$: a p forward$\_$link backward$\_$link

Entries in the frames table are linked together in allocated and free lists. The disk page table

entry, DPT $[$a$,$p$],$ contains the address on the paging disk of page $p$ of address space a$.$

Key Elements of the Assignment:

Write a page fault handler process that can be invoked by the interrupt dispatcher when a

page fault occurs. The address space and page number of the missing page are made available

to the fault handler by the addressing hardware. The fault handler requests a page transfer

by placing an entry in the disk driver work queue and signaling the associated semaphore.

Design a disk driver process which schedules all $\frac{\text{I}}{O}$ to the paging disk. disk command

STARTDISK $($read$/$urite$,$ memory$\_$addr, disk$\_$addr$)$

initiates an I$/$O operation. The paging disk is wired to the semaphore of the disk driver

process, which it signals when a command is complete. The disk has a work queue containing

entries of the form

$($process$\_$id$,$ read$/$write$,$ frame$\_$index, disk$\_$addr$).$