Contiguous Memory Allocation

Contiguous Memory Allocation

The operating system is allocated space first, usually at either low or high memory locations, and then the remaining available memory is allocated to processes as needed. Contiguous Memory Allocation is one of the approaches where each process is loaded into a single contiguous section of memory.

Memory Mapping and Protection

The relocation-register scheme provides protection against user programs accessing areas that they should not, allows programs to be relocated to different memory starting addresses as needed, and allows the memory space devoted to the OS to grow or shrink dynamically as needs change.

Memory Allocation

One method of allocating contiguous memory is to divide all available memory into equal sized partitions, and to assign each process to its own partition. The degree of multi programming is bound by the number of partitions.

An alternative approach is variable-partition scheme, the operating system keeps a table indicating which parts of memory are available and which are occupied. The approach is to keep a list of unused ( free ) memory blocks ( holes ), and to find a hole of a suitable size whenever a process needs to be loaded into memory. There are many different strategies for finding the "best" allocation of memory to processes:

1. First fit - Search the list of holes until one is found that is big enough to satisfy the request, and assign a portion of that hole to that process. Whatever fraction of the hole not needed by the request is left on the free list as a smaller hole. Subsequent requests may start looking either from the beginning of the list or from the point at which this search ended.

2. Best fit - Allocate the smallest hole that is big enough to satisfy the request. This saves large holes for other process requests that may need them later, but the resulting unused portions of holes may be too small to be of any use, and will therefore be wasted. Keeping the free list sorted can speed up the process of finding the right hole.

3. Worst fit - Allocate the largest hole available, thereby increasing the likelihood that the remaining portion will be usable for satisfying future requests.

Simulations have shown that both first fit and best fit are better than worst fit in terms of decreasing time and storage utilization. First and best fits are about equal in terms of storage utilization, but first fit is faster.

Fragmentation

All the memory allocation strategies suffer from external fragmentation, though first and best fits experience the problems more so than worst fit. External fragmentation means that the available memory is broken up into lots of little pieces, none of which is big enough to satisfy the next memory requirement, although the sum total could.

Internal fragmentation also occurs, with all memory allocation strategies. This is caused by the fact that memory is allocated in blocks of a fixed size, whereas the actual memory needed will rarely be that exact size. 

If the programs in memory are relocatable, ( using execution-time address binding ), then the solution to external fragmentation problem is compaction, i.e. moving all processes down to one end of physical memory. This only involves updating the relocation register for each process, as all internal work is done using logical addresses.

Another possible solution to the external fragmentation problem is to permit the logical address space of the process to be non contiguous. Two techniques achieve this solution are Paging and Segmentation.