• 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 .
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).
-Small jobs will not utilize partition space efficiently
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.
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.
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.
-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.
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.
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.
-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).
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.
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.
may vary in length
there is a maximum length
-Addressing consists of two parts:
-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.
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
• 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.
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.