This is a sample assignment.
Solutions are available as a plain ASCII file.
Consider a system with four page frames and a program that uses eight pages. Consider the reference string 0 1 7 2 0 3 1 7 0 1 7 and assume that all four page frames are initially empty. Consider the three following algorithms:
a. Optimal page replacement
b. FIFO page replacement
c. LRU page replacement
In each cases show a diagram (ASCII art recommended) that shows which pages are in which frames throughout time, and page faults at the bottom. For instance:
| 0 1 7 2 . . .
-------------------------
0 | 0 0 0 0 . . .
1 | - 1 1 1 . . .
2 | - - 7 7 . . .
3 | - - - 2 . . .
-------------------------
f | X X X X . . .would mean that at step 1 page 0 is referenced and loaded into frame 0, which is a page fault; then page 1 is referenced, and so on. The goal is to fill this table to see what in memory when and thus infer the number of page faults.
The first 4 steps are ALWAYS the same, as above (i.e., just fill the four frames, with one page fault each time)
Consider a system that implements demand paging without a TLB. The single-level page table is held in memory, and we assume that there are no free frames. Each memory access requires 100 nanoseconds. It takes 6 additional milliseconds to handle a page fault if the victim page is not “dirty” or 12 additional milliseconds if the victim page is “dirty”.
Experiments show that the probability of page faulting is 0.00003 (i.e., 0.003% chance) and that the average memory access time is 400ns. What is the percent chance that a page is dirty at the time it is evicted?
Show your work.
Hint: Call the “being dirty” probability d and write a simple equation that gives the average data access time as a function of d. Solve for d (the result should be a number between 0 and 1, which you then convert to a percentage).