First fit Best fit Worst fit with example | Allocation Algorithm

By:   Last Updated: in: ,

Operating System: Q1.How Memory can dynamically allocated using First fit Best fit Worst fit strategies? - with example. or  Explain 3 Allocation Algorithm with example? Q2.Dynamic Memory Allocation? (Operating System all notes)

Q1. How Memory can dynamically allocated using ‘first fit’, ‘best fit’, ‘worst fit’ strategies? or Explain 3 Allocation Algorithm?

Ans. The sets are an allocation algorithm to satisfy the dynamic shape allocation problem, which concerns how to satisfy a request of size from the list of free holes.

(a) First-Fit: Allocate the first hole that is big enough. Searching can start either at the beginning of the set of holes or where the previous first search ended. We can stop searching as soon as we find a free hole that is large enough.
(b) Best-Fit: Allocate the smallest hole that is big enough. We must search the entire list unless the list is ordered by size.
(c) Worst-Fit: Allocate the largest hole. We must search the entire list unless the list is ordered by size.

UsedHoleUsedHoleUsedHoleUsedHoleUsedHoleUsedHole
5k10k20k30k10k5k30k20k10k15k20k20k
Fig. (a) Variable partition memory allocation.

1. Using first-fit if the request arrives in order 20k, 10k, then the memory allocation is for 20k according to above figure a is:
UsedHoleUsedUsedFreeUsedHoleUsedHoleUsedHoleUsedHole
5k10k20k20k10k10k5k30k20k10k15k20k20k
Fig. (b)

Memory allocation for 10k according to above figure (b) is:
UsedHoleUsedHoleUsedHoleUsedHoleUsedHole
60k10k10k5k30k20k10k15k20k20k

2. Using best-fit if the request arrives in order 20k, 10k, then memory allocation for 20k according to figure (a) is:
UsedHoleUsedHoleUsedHoleUsedHoleUsedHole
60k10k10k5k30k20k10k15k20k20k
Fig. (c)

Memory allocation for 10k according to figure (c) is:
UsedHoleUsedHoleUsedHoleUsedHole
40k30k10k5k60k15k20k20k

3. Using Worst-fit if the request arrives in order 20k, 10k, then memory allocation according to the figure for 20k according to figure (a) is:
UsedHoleUsedHoleUsedHoleUsedHoleUsedHoleUsedHole
10k10k40k10k10k5k30k20k10k15k20k20k
Fig. (d)

Memory allocation for 10k according to the figure (d) is:
UsedHoleUsedHoleUsedHoleUsedHoleUsedHoleUsedHole
10k10k40k10k10k5k40k10k10k15k20k20k

Q2. Dynamic Memory Allocation?

Ans. The disk can be viewed as a large array of blocks. At any given time, the source of these blocks is allocated to files and others are free. Disk space can be seen as a collection of free and used segments in which each segment is a contiguous set of disk blocks.

A free segment (or unallocated segment) is called a hole. The dynamic storage allocation problem is how to satisfy a request of n-size from a list of free holes.

There are many solutions to this problem. The set of the hole is searched to determine which hole is best to allocate. These three strategies(which are in the 1st question) are the common strategies that are used to select a free hole from the set of available holes.

These algorithms suffer from external fragmentation. To prevent external fragmentation user must compact all free space into one hole.