Memory Management

• Memory allocation (Slides)
  • Compile-link-load models
  • Static binding (SGG Ch.9.1.1)
  • Load time binding
  • Dynamic binding (SGG Ch.9.1.1)
    • Logical and physical address spaces (SGG Ch.9.1.2)
    • Contiguous allocation (SGG Ch.9.3)
    • Swapping (SGG Ch.9.2)
  • Multiple partition allocation (SGG Ch.9.3.2)
    • Fragmentation (SGG Ch.9.3.3)

• Segmentation and Paging (Slides)
  • What is segmentation? (SGG Ch.9.5)
    • Address translation (SGG Ch.9.5.1-2)
  • Features of segmentation
    • Memory protection (SGG Ch.9.5.3)
    • External fragmentation (SGG Ch.9.5.4)
    • Shared segments (SGG Ch.9.5.3)
  • Dynamic linking and loading (SGG Ch.9.1.3-4)
  • What is paging? (SGG Ch.9.4)
    • Address translation (SGG Ch.9.4.1)
  • Memory protection (SGG Ch.9.4.3)
  • TLBs (SGG Ch.9.4.2)
    • TLB reach (SGG Ch.10.8.3)
  • Large memory paging
    • Multilevel paging (SGG Ch.9.4.4.1)
    • Hashed page tables (SGG Ch.9.4.4.2)
    • Inverted page table (SGG Ch.9.4.4.3)
  • Features of paging
    • Swapping (SGG Fig.10.2)
    • Fragmentation
    • Page sizes (SGG Ch.10.8.2)
    • Shared pages (SGG Ch.9.4.5)
  • Segmentation with paging (SGG Ch.9.6)
    • The MULTICS model
    • The OS/2 32-bit model

• Virtual Memory (Slides)
  • What is virtual memory? (SGG Ch.10.1)
  • Demand paging (SGG Ch.10.2)
    • Partial load (SGG Ch.10.2.1)
    • Page faults (SGG 10.2.1)
  • Global vs local allocation (SGG Ch.10.5.3)
  • IO interlock (SG Ch.10.8.6)
  • Thrashing
    • Locality of reference (SGG Ch.10.6.1)
    • Working set model (SGG Ch.10.6.2)
    • What is thrashing? (SGG Ch.10.7)
    • Cause of thrashing (SGG Ch.10.7.1)
  • Frame allocation (SGG Ch.10.5)
    • Fixed allocation (SGG Ch.10.5.2)
    • Dynamic allocation (SGG Ch.10.5.2)
    • Page fault frequency (SGG Ch.10.6.3)
  • Page replacement (SGG Ch.10.4)
    • Page faults with replacement (SGG Ch.10.4.1)
    • Performance of demand paging (CH.10.2.2)
  • Page replacement algorithms (SGG Ch.9.5)
    • Optimal (SGG Ch.10.4.3)
    • FIFO (SGG Ch.10.4.2)
    • LRU (SGG Ch.10.4.4)
    • LRU approximation (SGG Ch.10.4.5)
      • Reference bits
      • References bytes
      • Second chance
      • Enhanced second chance
    • Counting algorithms (SGG Ch.10.4.6)
  • Features of virtual memory
    • Page buffering (SGG Ch.10.4.7)
    • Pre-paging (SGG Ch.10.8.1)
    • Copy on write (SGG Ch.10.3.1)
    • Program structure (SGG Ch.10.8.5)
  • Examples
    • Windows NT (SGG Ch.10.7.1)
    • Solaris (SGG Ch.10.7.2)

• UNIX Memory Management (SGG Ch.21.6)

Exam Style Questions

• Differentiate between logical and physical memory addresses.
• What benefit does dynamic linking provide, in terms of applications using system libraries?
• What basic task does the memory management unit hardware perform for an operating system.
• Explain how base and limit registers are used to provide memory protection when contiguous memory allocation is used.
• Explain how relocation and limit registers implement execution time address binding and memory protection, when contiguous memory allocation is used.
• Briefly describe the first-fit, best-fit, and worst-fit approaches to contiguous memory allocation.
• Given the following sequence of memory requests in an operating system that uses a non-preemptive contiguous memory allocation scheme, give the time and memory layout as each request is satisfied. The computer has MegaBytes of memory.
  [Some sequence of requests, make up your own]
• Explain why memory might not be used efficiently when contiguous memory allocation is used in a multi-tasking operating system.
• What is the difference between internal and external memory fragmentation?
• Explain what "compaction" is used for in memory management.
• Work out the optimal (minimal movement) compaction of the following fragmented memory.
• What is "swapping", in the context of memory management?
• How might swapping interfere with DMA?

• What are the two components of a logical address in a segmented memory environment?
• In the given the following segment table, and a logical addressing scheme that uses the first 5 bits of a 16 bit logical address to specify the segment table offset, what is the physical address that corresponds to the following logical address?
  [Segment table, logical address, make up your own]
• What information do a Segment Table Base Register and Segment Table Limit Register hold?

• Explain the basic principal of paging in memory management (without virtual memory management, i.e., no demand paging).
• What is a page table used for?
• Explain how a logical memory address is transformed into a physical memory address in a paged memory system.
• Explain how paging implicitly implement memory protection.
• What information do the Page Table Base Register and Page Table Limit Register hold?
• In a paged memory system, why is the number of pages and each frame size typically a power of 2?
• In a computer system with 64KB memory divided into 2KB frames, and with the following page table, what is the final physical address computed for the following logical address?
  [Page table, physical address, make up your own].
• How does a TLB improve the performance of a paged memory system?
• If the memory cycle time of a computer is 1microsecond, and the TLB look-up time is 0.15microsecond, what is the effective memory access time if the TLB hit rate is 98%?
• Give two factors that suggest increasing the page size and two factors the suggest decreasing the page size, in a paged memory system.
• How may page tables be extended to provide various forms of memory protection? Give an example.
• Explain how swapping is easily implemented in a paged memory system.
• What is the motivation for using multi-level paging?
• In a two level paged memory system, explain the components of a logical memory address.
• What information does each entry of an inverted page table contain?
• Explain the format of a logical address in a memory management system that uses an inverted page table, and explaion how such an address is converted into a physical address.
• Explain how shared memory is easily implemented in a paged memory system.
• Why is a segmented memory management system potentially more effective than a paged system?
• What is a drawback of segmentation compared to paging?
• Can segementation and paging be effectively combined?
• Describe the three components of a logical address for a paged-segmented memory system.

• What is the valid-invalid bit used for in a virtual memory system?
• Explain the steps that need to be taken when a page fault occurs in a paged virtual memory system (assume there is a free frame available).
• Explain the steps that need to be taken when a page fault occurs in a paged virtual memory system (assume there is no free frame available).
• How can a "dirty bit" improve the performance of a virtual memory system?
• What is the difference between global and local replacement in a paged virtual memory system?
• In a paged virtual memory system, with N frames of memory, and the following sequence of page references, show which pages are in which frames after each memory reference, using the {optimal,FIFO,LRU,second chance,enhanced second chance} page replacement algorithm. Give the total number of page faults.
  [Make up your own example]
• What is Belady's anomaly?
• Describe two ways of implementing the LRU page replacement algorithm for a paged virtual memory system.
• Describe the four categories of pages used to determine replacement in the enhanced second chance replacement algorithm.
• Given the following processes' claims for pages of memory in a system that has N frames, how many pages are allocated to each process using {equal,proportional} allocation?
  [List of processes and claims]
• In a system that has a memory cycle time of 1microsecond and a page transfer time of 5000microseconds, what is the effective memory access time if the page fault rate is 0.5%?
• Define "thrashing" in the context of paged memory management.
• How may long-term CPU scheduling be a cause of thrashing?
• Explain a possible conflict between paging and DMA.
• Explain how paging can make process start-up efficient, using the copy-on-write technique.