HW4 Test file descriptions. Four input files are described here: fifo_worstcase nfu_worstcase age_testfile clock_testfile ------------ 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 ------------ nfu_worstcase ---------------------- worst case scenario for nfu algorithm with 4 pages of 32 bytes each using time interval of 1 (counter is updated after every memory access). Basically does the following: repeat 10 times: read page 0 read page 1 read page 2 The above sets the counters for pages 0,1 and 2 all to 10. Next we have the following: repeat 10 times: read page 3 read page 4 read page 5 read page 6 Since pages 0,1 and 2 have high counters, they will never be booted, so every one of the reads to pages 3,4,5 and 6 will result in a page fault. When run through the VM simulator with parameters -n 4 -p 32 -t 1 -a nfu, should result in 3 faults for the first part, and 40 faults for the second part: > ./hw4 -n 4 -p 32 -a nfu -t 1 < nfu_worstcase Page Size: 32 # page frames: 4 Replacement Algorithm: nfu Lines processed: 71 Memory operations: 70 Faults: 43 If we change the number of physical pages to 8, it should have only one fault per virtual page accessed: (total of 7 faults): >./hw4 -n 8 -p 32 -a nfu -t 1 < nfu_worstcase Page Size: 32 # page frames: 8 Replacement Algorithm: nfu Lines processed: 71 Memory operations: 70 Faults: 7 > ./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 ------------ age_testfile ---------------------- a test file for age algorithm with 4 pages of 32 bytes each and time interval set to 10. Does the following: repeat 10 times: read page 0 read page 1 read page 2 read page 3 The above sets the age for pages 0,1,2 and 3 to high values. Next we have the following: repeat 10 times: read page 4 read page 0 read page 5 read page 1 read page 6 read page 2 read page 7 read page 3 At the beginning of this loop, page 4 must be placed somewhere, assuming the ages of all four pages are the same this choice is random. However, once this happens the loop will always use the same physical page for each page fault, since every page is accessed in the loop. The result is that 3 of the physical pages will continue to hold on to 3 of the original pages (0-3), and the other page will be used to hold the 4th original page as well as the 4 new pages (4,5,6 & 7). The total result is 4 faults in the first loop, and 5 faults per loop in the second loop (for a total of 54 faults): ./hw4 -n 8 -p 32 -t 10 -a age < age_testfile Page Size: 32 # page frames: 4 Replacement Algorithm: age Lines processed: 121 Memory operations: 120 Faults: 54 If we change the number of physical pages to 8, it should have only one fault per virtual page accessed: (total of 8 faults): ./hw4 -n 8 -p 32 -t 10 -a age < age_testfile Page Size: 32 # page frames: 8 Replacement Algorithm: age Lines processed: 121 Memory operations: 120 Faults: 8 ------------ clock_testfile ---------------------- a test file for clock algorithm with 4 pages of 32 bytes each and time interval set to 4. Does the following: loads 4 pages in the 4 frames: read page 0 read page 1 read page 2 read page 3 Note that since time interval is set to 4, all read bits will be clear after these four lines. Next the first three pages are accessed - this makes sure the read bits are set and the read bit for page 3 is not set: read page 0 read page 1 read page 2 Now we repeat 5 times: read page 4 read page 0 read page 1 read page 2 read page 5 read page 0 read page 1 read page 2 At the beginning of this loop, page 4 must be placed somewhere, since the read bit is set for pages 0,1 and 2, it ends up in physical page 3. Next pages 0,1 and 2 are accessed (all HITS). Then page 5 is accessed - once again it is placed in physical page 3, then pages 0,1 and 2 are accessed again (to prevent them from being booted). The overall result is that there are the four initial faults, then every access to pages 4 and 5 is a fault, for a total of 14 faults. > ./hw4 -n 4 -t 4 -p 32 -a clock < clock_testfile Page Size: 32 # page frames: 4 Replacement Algorithm: clock Lines processed: 47 Memory operations: 47 Faults: 14 If we change the number of page frames to 8, each virtual page causes a single page fault (total of 6 faults): ./hw4 -n 8 -t 4 -a clock < clock_testfile Page Size: 32 # page frames: 8 Replacement Algorithm: clock Lines processed: 47 Memory operations: 47 Faults: 6