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 1?s, 
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.1?s?

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.

a.	First In First Out (FIFO)

b.	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.

a.	Give an example of a reference string showing that doubling the page size can reduce page faults.

b.	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 algo-
rithms."  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)