Published by: Zaya
Published date: 22 Jun 2021
For both fixed and dynamic memory allocation schemes, the operating system must keep a list of each memory location noting which are free and which are busy. Then as new jobs come into the system, the free partitions must be allocated.
These partitions may be allocated in 4 ways:
1. First-Fit Memory Allocation 2. Best-Fit Memory Allocation 3. Worst-Fit Memory Allocation 4. Next-Fit Memory Allocation
These are Contiguous memory allocation techniques.
This method keeps the free/busy list of jobs organized by memory location, low-ordered to high-ordered memory. In this method, the first job claims the first available memory with space more than or equal to its size. The operating system doesn’t search for an appropriate partition but just allocates the job to the nearest memory partition available with sufficient size.
Fig: First-Fit Memory Allocation[/caption]
As illustrated above, the system assigns J1 the nearest partition in the memory. As a result, there is no partition with sufficient space is available for J3 and it is placed in the waiting list.
Advantages of First-Fit Memory Allocation:
It is fast in processing. As the processor allocates the nearest available memory partition to the job, it is very fast in execution.
Disadvantages of Fist-Fit Memory Allocation :
It wastes a lot of memory. The processor ignores if the size of the partition allocated to the job is very large as compared to the size of the job or not. It just allocates the memory. As a result, a lot of memory is wasted and many jobs may not get space in the memory and would have to wait for another job to complete.
This method keeps the free/busy list in order by size – smallest to largest. In this method, the operating system first searches the whole of the memory according to the size of the given job and allocates it to the closest-fitting free partition in the memory, making it able to use memory efficiently. Here the jobs are in the order from the smallest job to the largest job.
[caption id="attachment_6377" align="aligncenter" width="762"]
Fig: Best-Fit Memory Allocation[/caption]
As illustrated in the above figure, the operating system first searches throughout the memory and allocates the job to the minimum possible memory partition, making the memory allocation efficient.
Advantages of Best-Fit Allocation :
Memory Efficient. The operating system allocates the job minimum possible space in the memory, making memory management very efficient. To save memory from getting wasted, it is the best method.
Disadvantages of Best-Fit Allocation :
It is a Slow Process. Checking the whole memory for each job makes the working of the operating system very slow. It takes a lot of time to complete the work.
The next fit is a modified version of 'first fit'. It begins as the first fit to find a free partition but when called next time it starts searching from where it left off, not from the beginning. This policy makes use of a roving pointer.
Algorithm for memory allocation using Next Fit
Step 1. Enter the number of memory blocks.
Step 2. Enter the size of each memory block.
Step 3. Enter the number of processes with their sizes.
Step 4. Start by selecting each process to check if it can be assigned to the current memory block.
Step 5. If the condition in step 4 is true, then allocate the process with the required memory and check for the next process from the memory block where the searching was halted, not from the starting.
Step 6. If the current memory size is smaller, then continue to check the next blocks.
Step 7. Stop
[caption id="attachment_6378" align="aligncenter" width="645"]
Fig: Next-Fit Memory Allocation[/caption]
In worst fit approach is to locate the largest available free portion so that the portion left will be big enough to be useful. It is the reverse of best fit.
Reduces the rate of production of small gaps.
If a process requiring larger memory arrives at a later stage then it cannot be accommodated as the largest hole is already split and occupied.
[caption id="attachment_6379" align="aligncenter" width="640"]
Fig: Worst-Fit Memory Allocation[/caption]
Problems:
