Sample questions from previous semester's second exam

  1. Describe two data structures needed to implement paged virtual memory. Think what is needed for a process and what is needed for the OS.
  2. Show the LRU replacement policy for the following reference string and three frames of memory. How many page faults occurred.
  3. Describe how a logical address is converted to a physical address for a two level page table.
  4. Briefly describe two advantages of a virtual memory system.
  5. What does it mean when: a) the logical address space is smaller than the physical address space; b) the logical address is larger than the physical address space.
  6. Suppose a machine has a physical memory of 1M organized as 256 4K pages. As there are only 256 frames of memory, the frame value could be stored in a byte. What is the primary disadvantage of storing the frame number this way. Suggest an alternative that eliminates this disadvantage.
  7. What would be the primary disadvantage of making the page size a value that was NOT a power of 2.
  8. Suppose a 32 bit virtual address is split into four fields: a, b, c, d. The first three are used for a three level page table. Give a formula defining the number of pages needed to handle this scheme.
  9. What is the difference between a physical address and a logical address and where is each used.
  10. Explain how shared memory can be implemented in a paging system.
  11. Main memory of a computer contains 90 frames. Nine identical programs are running and each references its pages (0123456789) in that order over and over. What is the page fault rate? If a tenth identical program is introduced and an LRU page replacement policy is used, describe what happens and why.
  12. A system is running with following measure behavior: CPU utilization 20%; Paging disk 98% Other I/O devices 5%. For each of the following say whether it will improve CPU utilization
  13. Describe two page replacement algorithms and describe an advantage and disadvantage of each.
  14. What information needs to be stored to implement segmentation? What needs to be stored to implement paging? What is the trade off between the two?
  15. Describe how decreasing the page size could result in fewer page faults (assuming total memory allocated to a process remains constant).
  16. A group of designers for the Frugal computer Company are thinking about ways of reducing the size of the backing store (the swap area) and propose just paging programs text area directly from the disk. Are there any problems with this?
  17. What factors might be used in selecting a frame to page out?
  18. Suppose a computer has a 48 bit virtual address and 16 G physical memory. How many bytes would be needed for storing the frames of an inverted page table using 8K pages?
  19. Describe what hardware is needed to support pure segmentation.
  20. Describe what hardware is needed to support paging.
  21. Describe how a single level page table works. Describe how a two level page tablew works. What is the primary tradeoff between the two?
  22. A computer has a 32 bit address space and 4K-byte pages. The program and data segments each occupy one page and the stack occupies one page. a) How much total memory is required when paging is implemented with a single level page table? b) How much total memory is required when paging is implemented with a two level page table with 10 bits in each part.
  23. A certain system has 4 G-byte logical addresses and 23 bit physical address. Paging is implemented with a page size of 2048 bytes. Describe what an entry in the TLB might look like, including information needed for various page replacement algorithms. Assume a single level page table.
  24. With respect to virtual memory a) Describe internal fragmentation and how it occurs b) Describe external fragmentation and how it occurs c) How can internal fragmentation be minimized and what is the trade off for doing so.
  25. a) Describe how an inverted page table works. b) Why is its major advantage? c) What change in memory mapping is required when compared to a normal page table?
  26. Describe two disc scheduling algorithms and give a disadvantage of each.
  27. Describe the idea of program locality. What would be the consequence if programs did not exhibit locality?
  28. Describe thrashing. Suggest two ways of reducing thrashing.
  29. Describe various factors that might be considered in selecting a page to use when a page fault occurs.
  30. A student in a compiler design course proposes to write a compiler extension that outputs lists of page references that can be used for the optimal page replacement algorithm. Is this possible? Why or why not?