Chapter 7 – Memory Management (PowerPoint)

Memory Management Techniques
Memory Management Techniques
(Table is on page 315 in textbook)
There are two difficulties with the use of equal-size fixed partitions:
• A program may be too big to fit into a partition. In this case, the programmer must design the program with the use of overlays so that only a portion of the program need be in main memory at any one time. When a module is needed that is not present, the user’s program must load that module into the program’s partition, overlaying whatever programs or data are there.

• Main memory utilization is extremely inefficient. Any program, no matter how small, occupies an entire partition. In our example, there may be a program whose length is less than 2 Mbytes; yet it occupies an 8-Mbyte partition whenever it is swapped in. This phenomenon, in which there is wasted space internal to a partition due to the fact that the block of data loaded is smaller than the partition, is referred to as internal fragmentation .

Memory Assignment for Fixed Partitioning: Placement Algorithm
Memory Assignment for Fixed Partitioning: Placement Algorithm
With equal-size partitions, the placement of processes in memory is trivial. As long as there is any available partition, a process can be loaded into that partition. Because all partitions are of equal size, it does not matter which partition is used. If all partitions are occupied with processes that are not ready to run, then one of these processes must be swapped out to make room for a new process. Which one to swap out is a scheduling decision; this topic is explored in Part Four.

With unequal-size partitions, there are two possible ways to assign processes to partitions. The simplest way is to assign each process to the smallest partition within which it will fit. In this case, a scheduling queue is needed for each partition, to hold swapped-out processes destined for that partition ( Figure 7.3a ). The advantage of this approach is that processes are always assigned in such a way as to minimize wasted memory within a partition (internal fragmentation).

The use of unequal-size partitions provides a degree of flexibility to fixed partitioning. In addition, it can be said that fixed-partitioning schemes are relatively simple and require minimal OS software and processing overhead. However, there are disadvantages:
-The number of partitions specified at system generation time limits the number of active processes in the system

-Small jobs will not utilize partition space efficiently

Dynamic Partitioning
Dynamic Partitioning
One technique for overcoming external fragmentation is compaction : From time to time, the OS shifts the processes so that they are contiguous and so that all of the free memory is together in one block. For example, in Figure 7.4h , compaction will result in a block of free memory of length 16M. This may well be sufficient to load in an additional process. The difficulty with compaction is that it is a time-consuming procedure and wasteful of processor time. Note that compaction implies the need for a dynamic relocation capability. That is, it must be possible to move a program from one region to another in main memory without invalidating the memory references in the program (see Appendix 7A).
The Effect of Dynamic Partitioning
The Effect of Dynamic Partitioning
An example, using 64 Mbytes of main memory, is shown in Figure 7.4 . Initially, main memory is empty, except for the OS (a). The first three processes are loaded in, starting where the operating system ends and occupying just enough space for each process (b, c, d). This leaves a “hole” at the end of memory that is too small for a fourth process. At some point, none of
the processes in memory is ready. The operating system swaps out process 2 (e), which leaves sufficient room to load a new process, process 4 (f). Because process 4 is smaller than process 2, another small hole is created. Later, a point is reached at which none of the processes in main memory is ready, but process 2, in the Ready-Suspend state, is available. Because there is insufficient room in memory for process 2, the operating system swaps process 1 out (g) and swaps process 2 back in (h).

As this example shows, this method starts out well, but eventually it leads to a situation in which there are a lot of small holes in memory. As time goes on, memory becomes more and more fragmented, and memory utilization declines. This phenomenon is referred to as external fragmentation , indicating that the memory that is external to all partitions becomes increasingly fragmented. This is in contrast to internal fragmentation, referred to earlier.

Placement Algorithms
Placement Algorithms
Because memory compaction is time consuming, the OS designer must be clever in deciding how to assign processes to memory (how to plug the holes). When it is time to load or swap a process into main memory, and if there is more than one free block of memory of sufficient size, then the operating system must decide which free block to allocate.

Three placement algorithms that might be considered are best-fit, first-fit, and next-fit. All, of course, are limited to choosing among free blocks of main memory that are equal to or larger than the process to be brought in. Best-fit chooses the block that is closest in size to the request. First-fit begins to scan memory from the beginning and chooses the first available block that is large enough. Next-fit begins to scan memory from the location of the last placement, and chooses the next available block that is large enough.

Example Memory Configuration before and after Allocation of 16 Mbyte Block
Example Memory Configuration before and after Allocation of 16 Mbyte Block
Figure 7.5a shows an example memory configuration after a number of placement and swapping-out operations. The last block that was used was a 22-Mbyte block from which a 14-Mbyte partition was created. Figure 7.5b shows the difference between the best-, first-, and next-fit placement algorithms in satisfying a 16-Mbyte allocation request. Best-fit will search the entire list of available blocks and make use of the 18-Mbyte block, leaving a 2-Mbyte fragment. First-fit results in a 6-Mbyte fragment, and next-fit results in a 20-Mbyte fragment.

Which of these approaches is best will depend on the exact sequence of process swapping that occurs and the size of those processes. However, some general comments can be made (see also [BREN89], [SHOR75], and [BAYS77]). The first-fit algorithm is not only the simplest but usually the best and fastest as well. The next-fit algorithm tends to produce slightly worse results than the first-fit. The next-fit algorithm will more frequently lead to an allocation from a free block at the end of memory. The result is that the largest block of free memory, which usually appears at the end of the memory space, is quickly broken up into small fragments. Thus, compaction may be required more frequently with next-fit. On the other hand, the first-fit algorithm may litter the front end with small free partitions that need to be searched over on each subsequent first-fit pass. The best-fit algorithm, despite its name, is usually the worst performer. Because this algorithm looks for the smallest block that will satisfy the requirement, it guarantees that the fragment left behind is as small as possible. Although each memory request always wastes the smallest amount of memory, the result is that main memory is quickly littered by blocks too small to satisfy memory allocation requests. Thus, memory compaction must be done more frequently than with the other algorithms.

Addresses
Addresses
A logical address is a reference to a memory location independent of the current assignment of data to memory; a translation must be made to a physical address before the memory access can be achieved. A relative address is a particular example of logical address, in which the address is expressed as a location relative to some known point, usually a value in a processor register. A physical address , or absolute address, is an actual location in main memory.
Paging
-Partition memory into equal fixed-size chunks that are relatively small

-Process is also divided into small fixed-size chunks of the same size

*Pages – chunks of a process

*Frames – available chunks of memory

Both unequal fixed-size and variable-size partitions are inefficient in the use of memory; the former results in internal fragmentation, the latter in external fragmentation. Suppose, however, that main memory is partitioned into equal fixed-size chunks that are relatively small, and that each process is also divided into small fixed-size chunks of the same size. Then the chunks of a process, known as pages , could be assigned to available chunks of memory, known as frames , or page frames. We show in this section that the wasted space in memory for each process is due to internal fragmentation consisting of only a fraction of the last page of a process. There is no external fragmentation.

Hardware Support for Relocation
Hardware Support for Relocation
Programs that employ relative addresses in memory are loaded using dynamic run-time loading (see Appendix 7A for a discussion). Typically, all of the memory references in the loaded process are relative to the origin of the program. Thus a hardware mechanism is needed for translating relative addresses to physical main memory addresses at the time of execution of the instruction that contains the reference.

Figure 7.8 shows the way in which this address translation is typically accomplished. When a process is assigned to the Running state, a special processor register, sometimes called the base register, is loaded with the starting address in main memory of the program. There is also a “bounds” register that indicates the ending location of the program; these values must be set when the program is loaded into memory or when the process image is swapped in. During the course of execution of the process, relative addresses are encountered. These include the contents of the instruction register, instruction addresses that occur in branch and call instructions, and data addresses that occur in load and store instructions. Each such relative address goes through two steps of manipulation by the processor. First, the value in the base register is added to the relative address to produce an absolute address. Second, the resulting address is compared to the value in the bounds register. If the address is within bounds, then the instruction execution may proceed. Otherwise, an interrupt is generated to the operating system, which must respond to the error in some fashion.

The scheme of Figure 7.8 allows programs to be swapped in and out of memory during the course of execution. It also provides a measure of protection: Each process image is isolated by the contents of the base and bounds registers and safe from unwanted accesses by other processes.

Assignment of Process Pages to Free Frames
Assignment of Process Pages to Free Frames
Figure 7.9 illustrates the use of pages and frames. At a given point in time, some of the frames in memory are in use and some are free. A list of free frames is maintained by the OS. Process A, stored on disk, consists of four pages. When it is time to load this process, the OS finds four free frames and loads the four pages of process A into the four frames ( Figure 7.9b ). Process B, consisting of three pages, and process C, consisting of four pages, are subsequently loaded. Then process B is suspended and is swapped out of main memory. Later, all of the processes in main memory are blocked, and the OS needs to bring in a new process, process D, which consists of five pages.

Now suppose, as in this example, that there are not sufficient unused contiguous frames to hold the process. Does this prevent the operating system from loading D? The answer is no, because we can once again use the concept of logical address.

Page Table
-Maintained by operating system for each process

-Contains the frame location for each page in the process

-Processor must know how to access for the current process

-Used by processor to produce a physical address

A simple base address register will no longer suffice. Rather, the operating system maintains a page table for each process. The page table shows the frame location for each page of the process. Within the program, each logical address consists of a page number and an offset within the page. Recall that in the case of simple partition, a logical address is the location of a word relative to the beginning of the program; the processor translates that into a physical address. With paging, the logical-to-physical address translation is still done by processor hardware. Now the processor must know how to access the page table of the current process. Presented with a logical address (page number, offset), the processor uses the page table to produce a physical address (frame number, offset).

Data Structures for the Example of Fig. 7.9 at Time Epoch (f)
Data Structures for the Example of Fig. 7.9 at Time Epoch (f)
Continuing our example, the five pages of process D are loaded into frames 4, 5, 6, 11, and 12. Figure 7.10 shows the various page tables at this time. A page table contains one entry for each page of the process, so that the table is easily indexed by the page number (starting at page 0 ). Each page table entry contains the number of the frame in main memory, if any, that holds the corresponding page. In addition, the OS maintains a single free-frame list of all the frames in main memory that are currently unoccupied and available for pages.

Thus we see that simple paging, as described here, is similar to fixed partitioning. The differences are that, with paging, the partitions are rather small; a program may occupy more than one partition; and these partitions need not be contiguous.

Segmentation (cont.)
Usually visible
Provided as a convenience for organizing programs and data
Typically the programmer will assign programs and data to different segments
For purposes of modular programming the program or data may be further broken down into multiple segments
the principal inconvenience of this service is that the programmer must be aware of the maximum segment size limitation

Whereas paging is invisible to the programmer, segmentation is usually visible
and is provided as a convenience for organizing programs and data. Typically, the
programmer or compiler will assign programs and data to different segments. For
purposes of modular programming, the program or data may be further broken down
into multiple segments. The principal inconvenience of this service is that the programmer
must be aware of the maximum segment size limitation.

Segmentation
-A program can be subdivided into segments
may vary in length
there is a maximum length

-Addressing consists of two parts:
segment number
an offset

-Similar to dynamic partitioning

-Eliminates internal fragmentation

A user program can be subdivided using segmentation, in which the program and its associated data are divided into a number of segments . It is not required that all segments of all programs be of the same length, although there is a maximum segment length. As with paging, a logical address using segmentation consists of two parts, in this case a segment number and an offset.

Because of the use of unequal-size segments, segmentation is similar to dynamic partitioning. In the absence of an overlay scheme or the use of virtual
memory, it would be required that all of a program’s segments be loaded into memory for execution. The difference, compared to dynamic partitioning, is that with segmentation a program may occupy more than one partition, and these partitions need not be contiguous. Segmentation eliminates internal fragmentation but, like dynamic partitioning, it suffers from external fragmentation. However, because a process is broken up into a number of smaller pieces, the external fragmentation should be less.

Address Translation
Address Translation
Another consequence of unequal-size segments is that there is no simple relationship
between logical addresses and physical addresses. Analogous to paging, a
simple segmentation scheme would make use of a segment table for each process
and a list of free blocks of main memory. Each segment table entry would have to
give the starting address in main memory of the corresponding segment. The entry
should also provide the length of the segment to assure that invalid addresses are
not used. When a process enters the Running state, the address of its segment table is
loaded into a special register used by the memory management hardware.

Consider an address of n + m bits, where the leftmost n bits are the segment number and the
rightmost m bits are the offset. In our example (Figure 7.11c), n = 4 and m = 12.
Thus the maximum segment size is 212 = 4096. The following steps are needed for
address translation:

• Extract the segment number as the leftmost n bits of the logical address.

• Use the segment number as an index into the process segment table to find the
starting physical address of the segment.

• Compare the offset, expressed in the rightmost m bits, to the length of the segment.
If the offset is greater than or equal to the length, the address is invalid.

• The desired physical address is the sum of the starting physical address of the
segment plus the offset.

Examples of Logical-to-Physical Address Translation
Examples of Logical-to-Physical Address Translation
In our example, we have the logical address 0001001011110000, which is segment number 1, offset 752. Suppose that this segment is residing in main memory starting at physical address 0010000000100000. Then the physical address is 0010000000100000 + 001011110000 0010001100010000 ( Figure 7.12b ).

To summarize, with simple segmentation, a process is divided into a number
of segments that need not be of equal size. When a process is brought in, all
of its segments are loaded into available regions of memory, and a segment table
is set up.