Homework 3

Short-Answer Problems

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

1. (10 points) Consider a logical address space of eight pages of 1024 words each, mapped onto a physical memory of 32 frames. How many bits are there in the logical address? In the physical address?
2. (10 points) How does the Working Set replacement strategy relate job scheduling to memory management?
3. (5 points) What is “device independence”?

Long-Answer Problems

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.

1. (25 points) A virtual memory has a page size of 1024 words, eight virtual pages, and four physical page frames. The page table is as follows:

   virtual page	page frame
   0	3
   1	1
   2	not in main memory
   3	not in main memory
   4	2
   5	not in main memor
   6	0
   7	not in main memor

   1. Make a list of all virtual addresses that will cause page faults.
   2. What are the physical addresses for 0, 3728, 1023, 1024, 1025, 4096, and 7800?
2. (25 points) You are the president of Cheapo Computronics, Inc., and your star hardware designer has suggested a brilliant idea: Implement segmentation, but let the least significant m bits of a virtual address be used to select the segment, and let the other bits determine the offset. What is the problem with this idea?
3. (25 points) This question asks you to compare different disk scheduling policies.
   1. Under very light loads, all the disk scheduling policies we have discussed degenerate into which policy? Why?
   2. Consider a system on which a seek takes 0.5 + 0.4T msec, where T is the number of cylinders moved. Then assume the arm is initially at cylinder 100, the disk has 200 cylinders, and the arm is moving inward. Will requests scheduled by a FCFS disk scheduling policy ever have a lower mean waiting time than those scheduled by a SCAN policy? Than those scheduled by a SSTF policy? Justify your answers.

Extra Credit Problems

1. (10 points) Prove that Belady’s anomaly cannot occur in a stack algorithm.