Assignment 4 on Using Reference Strings to simulate page replacement algorithms in demand paging,
        make turnitin due by 11:59 PM on Thursday May 2.
        Make sure to do STUDENT F for FIFO, LRU, and LRUDirty.

Outline of editing and testing stages:
1. Copy  PageReplaceOptimal.stm to PageReplaceFIFO.stm and follow all instructions.
2. When make testFIFO passes, copy PageReplaceFIFO.stm to PageReplaceLRU.stm & re-read / follow ALL instructions.
3. When make testLRU passes, copy PageReplaceLRU.stm to PageReplaceLRUDirty.stm & re-read / follow ALL instructions.
4. Use make testLRUDirty, then make clean test, then edit README.txt.

Make sure to assign into the variable victimPage in STUDENT requirements C, D, and E in their respective STM files.
 
Perform the following steps to get my handout. You will code and test on mcgonagall, to which you can ssh mcgonagall from acad.
Make sure to answer all questions in README.txt before make turnitin.
Each day late costs a 10% penalty and I cannot accept solutions after I go over mine in class.
cd $HOME # or start out in your login directory
mkdir OpSys # All of this semester’s work goes under here, skip if you did it before.
cd ./OpSys
cp ~parson/OpSys/DemandPagingCSC343Spring2024.problem.zip DemandPagingCSC343Spring2024.problem.zip
unzip DemandPagingCSC343Spring2024.problem.zip
cd ./DemandPagingCSC343Spring2024
make clean testOptimal
As before, if you get a run-time error in terms of the compiled __codeTable__ like this:

  File "PageReplaceOptimal.py", line 372, in run
    exec(__codeTable__[13],globals,locals)
  File "nofile", line 1, in <module>
NameError: name 'yang' is not defined
0.47user 0.03system 0:00.57elapsed 89%CPU (0avgtext+0avgdata 14556maxresident)k
72inputs+8outputs (0major+6140minor)pagefaults 0swaps
make: *** [testOptimal] Error 1

Run decode.py against that model's .py file and the code location [N] :

$ ./decode.py PageReplaceOptimal.py 13
__codeTable__[13] = compile('ying = yang','nofile','exec'),

I have implemented the textbook's Optimal page replacement algorithm in PageReplaceOptimal.stm. You will implement the other three in this order.

PageReplaceOptimal.stm            Optimal page replacement based on future knowledge.
                                                     make testOptimal tests this model.
PageReplaceFIFO.stm                FIFO page replacement based on history of page accesses.
                                                     make testFIFO tests this model. Run it when you complete coding this one.
PageReplaceLRU.stm                 Least recent used page replacement based on history of page accesses.
                                                     make testLRU tests this model. Run it when you complete coding this one.
PageReplaceLRUDirty.stm          Least recent used page replacement based on history of page accesses and unmodified / modified page status.
                                                     make testLRUDirty tests this model. Run it when you complete coding this one.

Edit the README.txt file when make clean test works without errors.
There is some overhead in the simulation mechanics that could have been tuned, but I didn't want to make the code too complicated.
That overhead does not affect the fidelity of the simulations.

STUDENT instructions in PageReplaceOptimal.stm guide your development stages. From the textbook slides:

Reference Strings

referencePageCount=100,000 page number references in referencePageList implement the Reference String.

Gaussian

Above is the Gaussian Distribution of page references, giving pretty good Locality of Reference.

Optimal

Handout PageReplaceOptimal.stm is already working. It is your starting point.
 
The changes in PageReplaceFIFO.stm are worth 26% of the assignment.

FIFO


Page numbers in referenceQueues[0] and referenceQueues[1] implement the FIFO queues of page reference history.

The changes in PageReplaceLRU.stm are worth 21% of the assignment.

LRU

The changes in PageReplaceLRUDirty.stm are worth 26% of the assignment.

There is no slide for LRU page replacement that uses the "dirty" (a.k.a. "modified") bit in the resident page status to prefer selecting pages that have not been modified since the most recent page-in.
They do not incur page-out over head once they are on the paging disk ("swap device").

The three questions in README.txt are worth 9% each, totaling 100% of the assignment.
We will use the final exam period to go over the solution.

Here is the state machine diagram. You do not need to add or remove any transitions.

stm