COP 4610: OPERATING SYSTEMS & CONCURRENT PROGRAMMING

Memory Management

 

Context and Motivation


As we study memory management, we will focus mainly on the original problem for which memory management techniques and algorithms were developed: the allocation of main (originally core) memory to processes. As we will see, work on that problem led to the development of hierarchical paged virtual memory, which has replaced the earlier-developed techniques for allocating main memory to processes.

We study these techniques in the context of the original problem, to provide historical context and motivation for the developments that came later, but that is not all, by far. All of the techniques, data structures, and algorithms, developed for allocating main memory tor processes still have other important applications, outside of the allocation of main memory to processes.

These outline notes are based largely on the presentation in Chapter 7 of Stallings' book. Please see the book for the full-text explanation of most of the outline points. Detailed notes are provided here on just a few points, where we want to go beyond Stallings.


Main Memory Management


The complexity of memory management has grown as the functional complexity of operating systems has grown. The original problem was limited to allocation of main memory.


Memory Implementation Hierarchy


Over time, the searches for faster performance and lower cost have led to the development of hierarchical memory implementations. This has extended the scope of the allocation problem, to the different levels individually, and to the interactions between levels. For the moment, we limit ourselves to one level of memory.


Memory Management Requirements


Stallings quotes and earlier textbook (Lister & Eager) as characterizing the memory management problem in terms of five requirements, each of which we will consider in some detail.


Memory Management Requirements: Relocation


Addressing Requirements for a Process


The figure shows a schematic "process image", i.e. all the memory-resident system data structures, the executable code of the process, the executing stack (assuming a single-threaded process), and the global static and dynamically allocated data areas. It is shown as a contiguous region of memory for simplicity, not to imply that must be so. The arrows from point to point within the process image indicate several different ways in which the code or data may depend on the location where the process image is loaded into memory. In particular, the red arrows indicate cases of addresses embedded in code, which will need adjustment to reflect the (re)location of the code in memory.

In order to fully understand the relocation requirement, one needs to understand the program compilation, assembly, linkage, and loading process. To keep the flow of the presentation on memory management going, Stallings' places his explanation of this material in an appendix. We also choose to cover that material in a separate set of notes, but choose to provide a bit more detail than Stallings. Please see the separate notes on Linking and Loading.


Memory Management Requirements: Protection


Memory Management Requirements: Sharing


Memory Management Requirements: Logical Organization


Memory Management Requirements: Physical Organization


Historical Evolution Leading to Virtual Memory Systems


We will review the historical evolution of memory management in operating systems, leading up to the virtual memory organization found in most present-day systems.


Fixed Partitioning


The Placement Problem

Decide which of the free memory partitions to allocate to fill a request

  • Equal-size partitions
    • because all partitions are of equal size, it does not matter which partition is used
  • Unequal-size partitions
    • can assign each process to the smallest partition within which it will fit
    • queue for each partition
    • processes are assigned in such a way as to minimize wasted memory within a partition

Placement Algorithms


Dynamic Partitioning


Dynamic Partitioning


Dynamic Relocation


Different Kinds of Addresses


In order to discuss dynamic relocation precisely, we must distinguish several different kinds of addresses.


Hardware Support for Dynamic Relocation


The hardware support for dynamic relocation shown in the figure includes a base register and the bounds register, which define the starting and ending addresses of the region of memory addressable by the process. These values are set when the process is loaded and when the process is swapped in. The value of the base register is added (by the hardware) to a relative address to produce an absolute address. The resulting address is compared with the value in the bounds register. If the address is not within bounds, an interrupt is generated to the operating system.

Is there a good reason for the base register to point to the location just past the process control block?

Is there a good reason for the bounds register to point to a location before the stack?


Three Simple Placement Algorithms for Dynamic Partitioning


These are three obvious simple algorithms that an operating system could apply when it must decide which of the currently free blocks of memory to allocate to a given process.

The implementation of C malloc() and C++ new must solve the same problems for memory management within the virtual address space of a single process as the memory management portions of operating systems did for management of memory between processes before the advent of virtual memory. In other words, understanding the available algorithms and the performance issues here will help you understand performance of programs and classes/libraries that use dynamic memory allocation. One big difference is that within a process we generally cannot compact free memory (Why not?), so external fragmentation is a more serious matter.

The same issues come up again inside the OS kernel, for allocation of data structures that are used to keep track of processes, files, etc.. An understanding if issues such as internal/external fragmentation and runtime overheads of placement algorithms here will help you understand why kernel-internal data structures are mostly equal-sized, and pre-allocated.


Example Memory Configuration Before and After Allocation


The Replacement Problem


When is replacement needed with dynamic memory partitioning? That is, under what circumstances would an OS need to swap out a process before the process has completed execution?

What are some reasonable policies for replacement with dynamic memory partitioning?

Replacement is discussed in more detail under virtual memory systems.


Buddy System


For comparison, see the boundary tag scheme for storage management, explained in the notes on memory allocation.


Example of Buddy System


The figure shows how a buddy system would work on a storage area of size 64K, though a series of three allocations and two deallocations. Notice that any request for a block whose size is not a power of two results in some wasted storage (fragmentation). This is usually classified as internal fragmentation, since we effectively allocate the entire block os size 2k.


Addresses of Buddy Blocks Viewed as Implicit Tree


Observe that the pairs of buddies form a conceptual binary tree, and that the starting address of a block can be read off the path from the root of the tree.

There is no need to build an explicit tree using pointers.

The address of the buddy of a block of size 2k is obtained by "flipping" (i.e., changing from zero to one or from one to zero) the kth bit of the block's address.

For example, the size 4 (22) buddy of the block with address 01000 is the block with address 01100, and vice versa.


The Gnu malloc() Implementation

See the code in fsuthreads/malloc.


The Gnu implementation of malloc() is an example of a full-fledged implementation of a storage management system. This version is not the latest, but it should still be useful as an example. You may benefit from reading it, in particular, free.h and malloc.c.


Paging


Paging is a technique that solves the placement problem by dividing memory up into equal-sized chunks, called pages. These days, it is applied along with virtual memory (coming up in Chapter 8), but it can also be done without virtual memory. Take care to be sure you understand the difference between paging and virtual memory.


Assignment of Process Pages to Free Frames


The figure shows how (external) fragmentation is no longer a problem, without any need for compaction. When 5-page process D needs to be brought in, it can use the three pages from process B, plus two more pages. They do not need to be contiguous.


Page Tables for Example


To implement paging, the system needs to maintain a page table for each process, which contains the beginning address of each page of logically contiguous region of memory occupied by the process.


Segmentation


© 2002, 2005 T. P. Baker & Florida State University. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means without written permission. (Last updated by $Author: cop4610 $ on $Date: 2002/09/26 20:06:06 $.)