4003-440 and 4003-713 Operating Systems
Homework #8
Due February 14, 2007
Name: __David Oguns______Section: __02______
1. Consider a logical address space of eight pages of 1024 words each, mapped onto a physical memory of 32 frames.
a. How many bits are there in the logical address? Explain how you arrived at your answer.
13 – Since a word is the smallest unit of memory a system can address, 1024 words would be 1024 different addresses that need to be mapped in each page. It would require at least 10 bits to do this. Since there are 8 pages, it would take 3 bits to address the page number.
b. How many bits are there in the physical address? Explain how you arrived at your answer.
32 – Since page size and frame size are the same, every frame in physical memory can be assumed to be 1024 words too. Given that there are 32 of them, it would take 5 bits to address the frame, and 10 more bits to address the exact word in the frame.
2. Consider a replacement policy that examines each page regularly and discards a page if it has not been usedsince the last examination. What would you gain and what would youlose by using this policy rather than LRU?
You would gain some performance during a page fault. Instead of having to copy what is in memory to the disk and then copy what is on disk to memory(swap), you would more than likely only have to bring what is on disk into memory.
3.Consider the following reference string:
2, 1, 4, 1, 3, 2
Sketch the sequence of page replacements that will occur usingthe FIFO, LRU, and Optimal page replacement algorithms,assuming three frames (the initial empty frames are sketched for your convenience on the following page). How many page faults will be generated for each algorithm? Remember all frames are initially empty, so your first unique pages willall cost one fault each.
FIFO:LRU:Optimal:
[E] [E] [E][E] [E] [E][E] [E] [E]
Page faults indicated with a (*)
[2][E][E]*[2][E][E]*[2][E][E]*
[2][1][E]*[2][1][E]*[2][1][E]*
[2][1][4]*[2][1][4]*[2][1][4]*
[2][1][4][2][1][4][2][1][4]
[3][1][4]*[3][1][4]*[2][3][4]*
[3][2][4]*[3][1][2]*[2][3][4]
5 page faults5 page faults4 page faults
4. What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate thisproblem?
Thrashing is caused by excessive paging that decreases CPU utilizations drastically for a process. It happens when a process has too little frames and gets paged out entirely only to be needed again. Thrashing can be detected by observing a decreasing CPU utilization and increasing page fault frequency. The system can use a local replacement algorithm for paging to reduce the likelihood of paging out something that will be needed in the future.
5. Consider a demand-paging system with amemory access time of 0.1microsecond. The page fault overhead is 8.2 milliseconds, with a page fault rate of 1/400,000. What is the effective access time? What should the page fault rate be if we require performancedegradation of less than 15% (that is, we require the effective access time to be less than 0.115 microseconds)?
EAT = (1 – p) x MAT + p x page_fault_overhead
EAT = (1 – 1/400000) + 1/400000 x .0082s = 2.05 x 10-15 = .00205picoseconds
EAT’ = 1.15 * EAT = .002357picoseconds