Comp111: Operating Systems
Classroom Exercise 14 Answers
Virtual Memory
Fall 2018

In class, we've studied the basic function of virtual memory. Recall that a frame is a unit of allocatable memory from the operating system, while a page represents a need for memory in a process. Let's explore these concepts further.

  1. Why is it practical to relocate a frame to another physical address? What must one do?
    A frame gets mapped to a page. Its physical address is never used except by the kernel. Processes see its logical address only. Its physical address can thus be moved and the logical address stays the same. In fact, this always happens when the page is recovered from disk.
  2. Why is it impractical to relocate a heap page to another address?
    A heap page -- by nature -- contains objects that are pointed to from elsewhere. We don't know which pointers point to it from elsewhere, because there are no runtime type descriptors in C and we cannot discover -- at runtime -- whether an object is a pointer or not. The runtime system can't distinguish a pointer from an integer! Thus we could not correct the pointers that point to it.
  3. Does keeping lots of processes dormant (with no pages swapped in) slow down the OS? Why or why not?
    Just a little. The pages for the process will all eventually swap out, due to becoming "least recently used." The processes will not be in the run queue so the scheduler is not affected. However, the process page tables will remain in memory until their frames are needed and the process of swapping them out and recovering their frames will slow down things a tiny bit.
  4. What memory do dormant processes consume when they're not running?
    As above, the page table remains in memory even when the process is not running. However, the pages of the process will eventually be completely virtual.
  5. (Advanced) Current wisdom is to allocate lots of swap space on a workstation, but use none at all on a server. Why might this be a good strategy?
    A workstation can have lots of dormant processes, e.g., word processors, image editors, and other things waiting for user input. While these are dormant, they consume mostly virtual memory.

    By contrast, a typical server answers requests with processes that never wait for I/O. Thus, there is little need for a server request handler to ever go dormant, so there is little need to have it ever swap out of memory.

    Thus, we tend to put as much memory into servers as possible, and almost no swap space on disk.

  6. (Advanced) The OS doesn't store the page table as an array. What data structure would be more appropriate? How would it be structured?
    It's actually a kind of search tree. The reason for this is that the page table isn't a dense structure. There are lots of holes. Thus we don't want to store the whole page table as an array. More about this in the next lecture.
  7. (Advanced) Why did the IA64 architecture do away with segment descriptors? It seems like they would save space over recording a protection bit for each page.
    This is really deep. A segment descriptor encodes the operating systems's idea of protection for a page. In the page table, this is an attribute of the page rather than the segment. Thus, although the OS needs to keep track of the segment, the CPU does not. It can simply look at the page protection word instead. The real reason that it does this concerns how the page table is stored in the CPU, which is the subject of this lecture.

    There are two ostensible reasons for this change:

    1. The designers of the IA64 did not wish to couple the design to the traditional C model of execution with very few, fixed-meaning segments. Instead, they wished to support possible extensions to and complete divergence from the text/globals/heap/stack model of computation. Thread computing is greatly eased, e.g., if one can have multiple co-resident stacks, one for each thread.
    2. Once the above decision was made, it was cheaper in hardware dollars to support a really efficient page-based mapping system than to support segments at all. We'll talk about this next.