------------ fifo_worstcase ---------------------- worst case scenario for fifo algorithm with 4 pages of 32 bytes each. Basically does the following (many times): read page 0 read page 1 read page 2 read page 3 read page 4 - will boot page 0 from memory read page 0 - will boot page 1 from memory read page 1 - will boot page 2 from memory read page 2 - will boot page 3 from memory read page 3 - will boot page 4 from memory read page 4 - will boot page 0 from memory read page 0 - will boot page 1 from memory ... When run through the VM simulator with parameters -n 4 -p 32, should result in a fault on every access: > ./hw4 -n 4 -p 32 -a fifo < fifo_worstcase Page Size: 32 # page frames: 4 Replacement Algorithm: fifo Lines processed: 51 Memory operations: 50 Faults: 50 If we change the number of physical pages to 8, it should have only one fault per virtual page accessed: (total of 5 faults): > ./hw4 -n 8 -p 32 -a fifo < fifo_worstcase Page Size: 32 # page frames: 8 Replacement Algorithm: fifo Lines processed: 51 Memory operations: 50 Faults: 5 ------------ belady ---------------------- illustrates Belady's anomaly: in some situations it is possible for FIFO to do better with fewer pages of memory. This is the example from the book, designed for page size of 4. When run with 3 frames of memory there are 9 faults, when run with 4 frames of memory there are 10 faults: > ./hw4 -p 4 -n 3 -a fifo < belady Page Size: 4 # page frames: 3 Replacement Algorithm: fifo Lines processed: 13 Memory operations: 12 Faults: 9 > ./hw4 -p 4 -n 4 -a fifo < belady Page Size: 4 # page frames: 4 Replacement Algorithm: fifo Lines processed: 13 Memory operations: 12 Faults: 10