Memory allocation techniques are assigning of blocks of memory on request to the processes. Main memory is divided into set of non-overlapping memory regions called partitions that can be allocated in contiguous or non - contiguous partitions. The advantages of memory allocation techniques is simple and no hardware supports required, but there are some disadvantages like program size is fixed, wastage of CPU time, and main memory not utilized fully etc.
There are two types of partitions:
Contiguous partition, which is divided into two categories, i.e., Single partitions and multiple(fixed and variable) partitions.
Non contiguous partition, which is divided into three categories, i.e., Paging, segmentation, and segmented paging scheme.
Single Partition Allocation
This is simple to implement, however inefficient and program size is fixed. The main memory is divided into two parts for operating system and for user program that is running. That means only one user with one process is present in the system.
Multiple Partition Allocation
User memory is divided into more than one partitions. There are two types fixed partition or static partition and variable partition or dynamic partition.
Fixed partition has equal or unequal size of partitions and a partition is allocated to an active process in the multiprogramming system, however it may suffers from internal and external fragmentations, it supports only fixed number of active processes.
Variable partition has equal or unequal size of partitions and these partitions are created dynamically. A block or hole is available memory or free partitions. Variable partition has no internal fragmentation and it better utilization of memory than fixed partition. However, variable partition suffers from external fragmentation and it has overhead of compaction.
Dynamic Allocation Algorithms
If more than one empty hole or blocks are available for an active process then the operating system decides how to select a best hole or block using using dynamic allocation algorithms. These algorithms are as following:
First fit: It allocated the first hole that is big enough to process, this started from the beginning to search such empty hole, so first fit algorithm is simple to implement and faster to use.
Best fit: This allocates smallest hole that is big enough for process. This is fast when all empty blocks or holes sorted in increasing order of size. Best fit minimize internal fragmentation.
Worst fit: This allocates largest hole that is empty for process. This creates maximum internal fragmentation. Worst fit is fast when all empty blocks or holes sorted in decreasing order of size.
Next fit: This allocates first empty block or hole that big enough for process. Next fit starts searching from where it left off, not from the beginning. This works same as first fit algorithm.