Also discuss partition selection algorithm in brief.

Given memory partition of 150k, 500k, 200k, 300k &550k (in order).

How would each pf the first fit , best fit and worst fit algorithm place the processes of 220k, 430k, 110k &425k (in order).

MEMORY ALLOCATION ALGORITHMS

Given Memory Partition = 150 KB, 500 KB, 200 KB, 300 KB, and 550 KB (in order),

how would each algorithm place processes of size 220 KB, 430 KB, 110 KB & 425 KB (in order)?

First Fit:

In the first fit, a partition is allocated which is first sufficient from the top of Main Memory.

• 220 KB is put in a 500 KB partition. 220KB => 500 KB partition, leaves a 280 KB partition
• 430 KB is put in a 550 K partition. 430 KB => 550 KB partition, leaves a 120 KB partition
• 110 KB is put in a 280 K partition (new partition 280 KB = 500 KB - 220 KB). 110 KB => 280 KB partition, leaves a 170 KB partition
• 425 KB must wait. Because 425 KB would not be able to allocate, no partition large enough!

Fastest algorithm because it searches as little as possible. The remaining unused memory areas left after allocation become waste if it is too smaller. Thus request for a larger memory requirement cannot be accomplished.

Best-fit:

Allocate the process to the partition which is the first smallest sufficient partition among the free available partition.

• 220 KB is put in a 300 KB partition. 220 KB => 300 KB, leaving a 80 KB partition
• 430 KB is put in a 500 KB partition. 430 KB => 500 KB, leaving a 70 KB partition
• 110 KB is put in a 150 KB partition. 110 KB => 150 KB, leaving a 40 KB partition
• 425 KB is put in a 550 KB partition. 425 KB => 550 KB, leaving a 125 KB partition

Memory utilization is much better than the first fit as it searches the smallest free partition first available. It is slower and may even tend to fill up memory with tiny useless holes.

Worst-fit:

Allocate the process to the partition which is largest sufficient among the freely available partitions available in the main memory.

• 220 KB is put in a 550 KB partition. 220 KB => 550 KB, leaving a 330 KB partition
• 430 KB is put in a 500 KB partition. 430 KB => 500 KB, leaving a 70 KB partition
• 110 KB is put in a 330 KB partition. 110 KB => 330 KB (new partition 330 KB = 550 KB - 220 KB)., leaving a 220 KB partition
• 425 KB must wait. Because 425 KB would not be allowed to allocate as no partition is large enough!

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.

In this problem, the Best-Fit Algorithm makes the most efficient use of memory because it was the only algorithm that meet all the memory requests.