Page 131 - DCAP403_Operating System

Operating System

Notes 7.4 Contiguous Memory Allocation

The real challenge of efficiently managing memory is seen in the case of a system which has

multiple processes running at the same time. Since primary memory can be space-multiplexed,
the memory manager can allocate a portion of primary memory to each process for its own
use. However, the memory manager must keep track of which processes are running in which
memory locations, and it must also determine how to allocate and deallocate available memory
when new processes are created and when old processes complete execution. While various
different strategies are used to allocate space to processes competing for memory, three of the

most popular are Best fi t, Worst fit, and First fit. Each of these strategies is described below:
1. Best fi t: The allocator places a process in the smallest block of unallocated memory in

which it will fit. For example, suppose a process requests 12KB of memory and the memory
manager currently has a list of unallocated blocks of 6KB, 14KB, 19KB, 11KB, and 13KB

blocks. The best-fit strategy will allocate 12KB of the 13KB block to the process.
2. Worst fi t: The memory manager places a process in the largest block of unallocated
memory available. The idea is that this placement will create the largest hold after the

allocations, thus increasing the possibility that, compared to best fit, another process can
use the remaining space. Using the same example as above, worst fit will allocate 12KB of

the 19KB block to the process, leaving a 7KB block for future use.
3. First fi t: There may be many holes in the memory, so the operating system, to reduce the
amount of time it spends analyzing the available spaces, begins at the start of primary

memory and allocates memory from the first hole it encounters large enough to satisfy the

request. Using the same example as above, fi rst fit will allocate 12KB of the 14KB block to
the process.
Figure 7.4: Best Fit, Worst Fit and First Fit Memory Allocation Method
6KB

14KB 12KB

12KB
19KB

11KB

13KB 12KB
Primary Best fit Worst fit First fit
Memory

Notice in the above figure that the Best fit and First fit strategies both leave a tiny segment of

memory unallocated just beyond the new process. Since the amount of memory is small, it is not
likely that any new processes can be loaded here. This condition of splitting primary memory
into segments as the memory is allocated and deallocated is known as fragmentation. The Worst

fit strategy attempts to reduce the problem of fragmentation by allocating the largest fragments
to new processes. Thus, a larger amount of space will be left as seen in the Figure 7.4.

124 LOVELY PROFESSIONAL UNIVERSITY