First fit Best fit Worst fit with example | Allocation Algorithm

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.

Used	Hole	Used	Hole	Used	Hole	Used	Hole	Used	Hole	Used	Hole
5k	10k	20k	30k	10k	5k	30k	20k	10k	15k	20k	20k

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:

Used	Hole	Used	Used	Free	Used	Hole	Used	Hole	Used	Hole	Used	Hole
5k	10k	20k	20k	10k	10k	5k	30k	20k	10k	15k	20k	20k

Fig. (b)

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

Used	Hole	Used	Hole	Used	Hole	Used	Hole	Used	Hole
60k	10k	10k	5k	30k	20k	10k	15k	20k	20k

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

Used	Hole	Used	Hole	Used	Hole	Used	Hole	Used	Hole
60k	10k	10k	5k	30k	20k	10k	15k	20k	20k

Fig. (c)

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

Used	Hole	Used	Hole	Used	Hole	Used	Hole
40k	30k	10k	5k	60k	15k	20k	20k

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:

Used	Hole	Used	Hole	Used	Hole	Used	Hole	Used	Hole	Used	Hole
10k	10k	40k	10k	10k	5k	30k	20k	10k	15k	20k	20k

Fig. (d)

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

Used	Hole	Used	Hole	Used	Hole	Used	Hole	Used	Hole	Used	Hole
10k	10k	40k	10k	10k	5k	40k	10k	10k	15k	20k	20k

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.

External Links:-

1. Allocation Algorithm - (click here)
2.  Three Strategies - (click here)


[ Topic= Allocation Algorithm ]