Operating Systems 1

Tutorial 5

1. Does a system which uses 'paged' memory management suffer from external fragmentation?
2. A certain computer system has a page size of 4K, and a 16-bit virtual address space. What is the maximum page table size? If there are 128 page frames in physical memory, what is the size of the physical address space?
3. In the computer system described above, the (single-level) page table of a certain process is

   <A, 6, 7, 16, 17, X, 37, 3C>

   (all numbers are hexadecimal and the X indicates an 'absent' page). Where do virtual addresses 0345₁₆ and 6FF0₁₆ map to in physical memory?
4. Decribe a method by which processes could share some areas of memory, but also keep some areas of their memory private, using paging.
5. The Alpha AXP processor includes a few bits' worth of 'granularity hints' in page table entries, which let the paging hardware know if several consecutive pages map to several consecutive physical memory frames. What might be the advantage in this, as regards the TLB?
6. What happens if an instruction attempts to reference a location in virtual memory whose page is marked as 'absent' in the page table for the process?
7. What are the advantages of keeping the page table entirely in on-chip registers in the MMU? What are the advantages of keeping the page table entirely in memory?
8. What is a multilevel page table? What are the disadvantages of a single-level page table that a multilevel page table corrects?
9. A TLB has a hit rate of 94%. The system contains 70ns RAM. When using paging through the TLB, there is an overhead of 12ns if the page table entry can be found in the TLB; otherwise the 3-level page table in RAM must be consulted.

   What is the memory access overhead on a TLB-miss? ('Overhead' means the time takein in addition to the 70ns to eventually access data in physical memory.) What is the average overhead when using the TLB? What is the average total memory access time? (And how much slower is this than accessing physical memory directly?)