• In our previous article we had explained about memory protection and in this post we will discuss about memory allocation techniques used by the operating system. This article deals with contiguous memory allocation technique.
  • The main memory is divided into two partitions, one portion contains operating system code and other is used for storing the user processes.
  • Different types of methods are used for memory allocation. The simplest method for memory allocation is to divide memory into several fixed size partition. Two alternative methods are used for fixed size partitioning. One is equal-size partitions and other is unequal-size partitions.
  • In equal-size partition method process can be allocated any available free partition which is greater than or equal to the process size. If there is no any free partition available than operating system performs swapping of the process. When the process terminates partition becomes available for another process.
  • There are two limitations of this method.
  1. If the program is too big to fit in a partition then a programmer must design the program in modules so that only required module will be in a memory whenever it needs.
  2. Second if program’s size is very small, still it will be allocated an entire free block so unused space will result in wastage of the memory inside the partition. It is referred to as internal fragmentation.  
  • Operating System keeps track of available free memory areas. There are three approaches to select a free partition from the set of available blocks.

First Fit:

  • It allocates the first free large area whose size is >= program size. Searching may start from either beginning of the list or where previous first-fit search ended. Limitation of this technique is that it may split a free area repeatedly and produce smaller size of blocks that may consider as external fragmentation.

Contiguous Memory Allocation-Fix size PartitionBest Fit:

  • It allocates the smallest free area with size >= program size. We have to search the entire free list to find out the smallest free hole so it has higher allocation cost. Limitation of this technique is that in long run it too may produce numerous unusable small free areas. It also suffers from higher allocation cost because it has to process entire free list at every allocation.

Worst Fit (Next Fit):

  • The worst fit technique is a compromise between these two techniques. It remembers the entry of last allocation. It searches the free list starting from the previous allocation for the first free area of size >= program size.
  • The first fit technique is better than best fit. Both first fit and next fit performs better than best fit.

Example:

  • A free list contains three free areas of size 200, 170 and 500 bytes respectively (figure a). Processes sends allocation requests for 100, 50 and 400 bytes.

Memory Allocation Techniques

  • The first fit technique will allocate 100 and 50 bytes from the first free area leaving a free area of 50 bytes. It allocates 400 bytes from the third free area.
  • The best fit technique will allocate 100 and 50 bytes from the second free area leaving a free area of 20 bytes. The next fit technique allocates 100, 50 and 400 bytes from the three free areas.