Homework #4: Memory Management
CMSC 421, Section 0101 (Fall 1999)
Assigned: 4 Nov 1999
Due: 11 Nov 1999 at 2:30 PM
Late homeworks will not be accepted.
- 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?
- 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?
- 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:
- 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.
- For an average process, how much space is required for page tables using each proposed scheme?
- 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:
- There is no TLB?
- There is a TLB filled in hardware (no additional overhead beyond the memory accesses required)?
- 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.
- Problem 8.17 from the text.
- Problem 9.9 from the text.
- Problem 9.19 from the text.
- Consider the following page reference string:
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.
- LRU replacement
- FIFO replacement
- Optimal replacement
Syllabus | Schedule | News & Notes | Grades | Feedback
Submit | Homework: 1 2 3 4 5 6 | Project: 1 2 3 4
3 Dec 1999
by Ethan Miller (firstname.lastname@example.org)