You are expected to do your own work on all homework assignments. You may (and are encouraged to) engage in general discussions with your classmates regarding the assignments, but specific details of a solution, including the solution itself, must always be your own work. (See the statement of Academic Dishonesty on the Syllabus.)
Assignments need to be turned in via Lamaku. Check the Syllabus for the late assignment policy for the course.
You should turn in single plain text or PDF file named README.txt, or README.pdf, with your answers to the assignment’s questions. Your file must be readable “as is” and points will be removed if the report is not readable.
Consider a system with four page frames and a program that uses eight pages. Consider the reference string 0 1 7 2 3 2 0 7 1 2 3 7 and assume that all four page frames are initially empty. Consider the three following algorithms:
a. [16 pts] Optimal page replacement
b. [16 pts] FIFO page replacement
c. [16 pts] 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 3 . . .
-------------------------
0 | 0 0 0 0 1 . . .
1 | - 1 1 1 7 . . .
2 | - - 7 7 2 . . .
3 | - - - 2 3 . . .
-------------------------
f | X 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 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 8 additional milliseconds to handle a page fault if the victim page is not “dirty” or 20 additional milliseconds if the victim page is “dirty”.
Assume that the page to be replaced is dirty 25% of the time. What is the maximum acceptable probability of having a page fault so that the expected data access time (i.e., the time to retrieve data given a CPU-issued virtual address) is no more than 500 nanoseconds?
Show your work.
Hint: Call the page fault probability p and write a simple equation that gives the average data access time as a function of p, and then solve for 500. The result is a very small number of course.