Assigned: 4 Nov 1999
Due: 11 Nov 1999 at 2:30 PM

Late homeworks will not be accepted.

1. Given memory partitions of 200K, 600K, 100K, 300K, and 500K (in that order, how would each of first-fit, worst-fit, and best-fit place processes of 225K, 370K, 88K, and 418K? Which algorithm uses memory most efficiently? Put another way, which ending allocation would be best suited for a new incoming process?
2. In some systems, such as the Motorola 680x0, page tables could have up to 5 levels! Why might a OS designer want to use 5 separate levels of page tables, as compared to the one and two level page tables discussed in class? What are some drawbacks to using all 5 levels?
3. You are given a system with 4 KB pages and 32-bit virtual addresses, and you are designing the virtual memory portion of the OS for this system. You are considering two different schemes, a single-level page table scheme and a two-level page table scheme with 1K entries in the top level page table. The average process on this system has 3.5 MB of code, 4.3 MB of data, and a 512 KB stack arranged in virtual memory as follows:

   0

   232-1

   Code (3.5MB)

   Data (4.3MB)

   empty

   Stack (512KB)

   1. Show how the two level page table scheme translates a virtual address to a physical address. Include the sizes of various bit fields as necessary.
   2. For an average process, how much space is required for page tables using each proposed scheme?
4. For the memory system in problem 2, we are using a TLB to reduce the cost of paging. Suppose the TLB has a hit rate of 99.9%, and incurs no overhead if a translation is found in the TLB. Memory accesses take 50ns, and instructions require 5ns each (excluding memory overhead). How much slower does paging make the computer if:
   1. There is no TLB?
   2. There is a TLB filled in hardware (no additional overhead beyond the memory accesses required)?
   3. There is a TLB filled by software, requiring 10 instructions to fill? Assume that the TLB code doesn't itself cause TLB faults; the code does, however, need to access memory to get at the page tables.
5. Problem 8.17 from the text.
6. Problem 9.9 from the text.
7. Problem 9.19 from the text.
8. Consider the following page reference string:
   1,2,3,4,2,5,7,1,3,6,4,5,1,3,2,4,5,2,7,1,2
   How many page faults would occur for the following replacement algorithms? For each algorithm, simulate it using 3,4, and 5 frames. Remember that all page frames are initially empty, so the first unique pages cause page faults.
   1. LRU replacement
   2. FIFO replacement
   3. Optimal replacement