Homework #4

Due Date: Thursday, March 9, 2000 at 11:59PM
Points: 60 regular, 20 extra credit

Short-Answer Questions

These can be answered in a sentence or two, and are intended to reinforce important points.

1. (5 points) How does the Working Set replacement strategy relate job scheduling to memory management?
2. (5 points) Consider a logical address space of 16 pages of 4096 words each, mapped onto a physical memory of 1024 frames. How many bits are there in the logical address? In the physical address?

Long-Answer Questions

These questions require some thought and longer answers than the short-answer questions. They are intended to have you use the concepts discussed in class, to be sure you understand them and can work with them.

3. (10 points) Assume that we have a paged memory system with a cache to hold the most active page table entries. It takes 20ns to search the cache. If the page table is normally held in memory, and memory access time is 1microsec, what is the effective access time if the hit ratio is 85%? What hit ratio will be necessary to reduce the effective memory access time to 1.1microsec?
4. (20 points) Consider the following page reference string: 1 2 3 4 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6 How many page faults would occur for the following replacement algorithms, assuming 1, 2, 3, 4, and then 5 frames? Remember all frames are initially empty, so your first unique pages will all cost one fault each.
   1. First In First Out (FIFO)
   2. Least Recently Used (LRU)
5. (20 points) This problem is meant to show that page size has a complex effect on performance. Assume that the total amount of real memory is fixed.
   1. Give an example of a reference string showing that doubling the page size can reduce page faults.
   2. Give an example of a reference string showing that halving the page size can reduce page faults.

Extra Credit

6. (10 points) Tanenbaum, and many other authors, refer to the LOOK and SCAN algorithms as "elevator algorithms." What is the major conceptual difference between disk scheduling and "elevator scheduling"? (Hint: are we trying to minimize elevator movement?)
7. (10 points) Why does the MINIX memory management scheme make it necessary to have a program like chmem? (text, chapter 4, problem 19)