This chapter brings several topics together. As you read it, make sure to think beyond just memory and to try to understand how what is discussed here connects to process management, to the compilation of programs, and to overall system performance.

9.1 Background

• In general purpose computing systems, we work with multiprogramming. That is, multiple executables become processes that coexist in memory. If each process could “imagine” that it owns all memory, things would be easier to understand. This raises the point that there are two views of memory: one physical (what is in RAM) and one logical. It’s important to understand the difference.
• The code of a process deals with logical address, but to get to content in RAM physical addresses are used. How are logical addresses mapped to physical addresses?
• With these two views of the memory space, we have to be able to translate addresses from one into the other’s perspective. How can we do that? Is there hardware involved in making this happen?
• We use the PCB as a bookkeeping data structure for managing processes. Now that you are aware of how we need to manage memory for processes, reflect on whether we need to add anything to the PCB that we didn’t discuss earlier.
• Memory is a constrained resource and the OS has to do its best to conserve memory so that it can run the largest possible number of applications. This chapter talks about techniques to accomplish this goal.
• How does dynamic loading work and how does it help memory management?
• There are two options for linking programs to the libraries they use: static linking and dynamic linking. It is important that you understand how each method works and that you can identify the advantages and disadvantages of each.
• Thinking back to how executables are generated, we realize that at some point, code and data need to be bound to memory address. You need to be able to explain how address binding is done at compile, load, and execution time.
• What do shared libraries do for the memory utilization in a multiprogrammed computer system?

9.2 Contiguous Memory Allocation

Dynamic memory allocation within the logical address space of a process makes use of the process’ heap. When we look at this logical space as one contiguous area, we realize that requests from calls like malloc are satisfied by “chunks” of memory within the heap that can be identified in different ways. The big questions that we need to investigate in developing strategies for memory allocation include:

• Evaluating the cost/benefit of allocation strategies such as first-fit, best-fit, and worst-fit. You need to be able to explain the rationale behind each of these strategies.
• Determining objective metrics to quantify the performance of allocation strategies. For instance, you need to understand whether internal fragmentation or external fragmentation are useful metrics in this context.
• Understanding the cause of external fragmentation and thinking of ways to minimize its negative effect on the memory system.

Another important point to consider is how the operating system can prevent a process from accessing the memory space of another. Is there need to have hardware for this or can this type of protection be implemented purely in software?

9.3 Paging

Not all memory is dealt with as a contiguous collection of bytes. It turns out that it can be very productive to view the memory as a collection of fixed sized, discrete units called frames. When we use this view of memory, we think of the logical space of a process as divided into a collection of fixed size, discrete units called pages.

• What is there to gain from dividing the memory into frames?
• How does the efficiency of memory usage change when the smallest unit that can be allocated is a frame?
• You need to understand the difference between frame and page. You also need understand whether the sizes of frame and page should be related or independent, and be able to argue the pros and cons of selecting larger or smaller page/frame sizes.
• Can there be external fragmentation or internal fragmentation with “paginated” memory?
• Processes view their logical memory space as contiguous, but their pages may be mapped to non-adjacent frames in physical memory. It is important for you to understand how we can translate a logical address translated into a physical address.
• Two types of data structures are needed to support paging systems: a  frame table and page tables. You need to understand the purpose that each of these will serve. You should also think about whether the system needs one or more instances of frame table or page table.
• You need to be able to describe the general structure of a page table and the function of each piece of information it contains.
• Systems based on paging require additional support from their processor hardware. For instance: we can find the address of page table for a process in a register reserved for this purpose,  the page-table base register (PTBR). How is this register used by the operating system? Does the value contained in this need to be recorded in a process’ PCB?
• Another supporting hardware construct for paging systems is the translation look-aside buffer (TLB). You need to understand its purpose and its potential impact on the performance of the memory system.
• One of the ways to quantify the performance of this type of memory system is via a metric called effective memory access time. You need to be able to explain how this metric is defined.
• You need to be able to describe the sequence of operations that is triggered when a process references any logical memory position in a paged system.
• When an address inside a page that resides in physical memory is referenced, the memory system has a page hit. When that reference corresponds to an address that is not currently in physical memory, we have a page fault. You need to be able to describe how the system handles page faults.
• Similarly, looking up information in the TLB and result in hits and misses. You need to understand how these are handled.
• Paging enable the system to eliminate the unnecessary replication of memory content. You need to be able to explain how one might take advantage of paging to end.

9.4 Structure of the Page Table

• Page tables can get too big and unwieldy, a problem which you can address by using different designs/structures for the information it holds. Hierarchical paging is one possible solution to this problem – you need to be able to show how a logical address is mapped to a physical address using this scheme.

9.5 Swapping

• Swapping takes process that have been previously loaded into memory and exiles them (temporarily) to backing storage. How does this help the goals of the operating system? What are the costs and benefits that come from this?
• If a process is exiled to backing storage, it cannot have terminated. This means that, at some point, the process will come back to memory to resume its execution. What component of the OS causes this to happen and at which point in the lifetime of the process does this event happen? Does this activity of bringing back a process from backing storage have any negative effect on the performance metrics of the operating system?