Allocation Methods In Contiguous

In continuous memory management, there are 4 algorithms. Through these algorithms, we can allocate the upcoming process in the proper holes to avoid internal fragmentation. These algorithms are known as Partition Allocation Methods In Contiguous.

1. First Fit: In this algorithm, OS allocates the process to the first Hole that is big enough.

It is very fast and easy to implement

The first fit algorithm starts scanning the partitions from the beginning of memory every time to load a new process in the main memory. When it first found a big enough partition that could accommodate the loading process, the scanning stopped, and the process loaded successfully. Explanation is given under

2. Next Fit: Next fit is modified of the first fit, but it will search for the first big enough partition from the last allocation partition.

3. Best Fit: In this algorithm, OS allocates the process to that partition which is the first smallest enough (among all free available partition) to accommodate that process.

It is a time-consuming algorithm, but the internal fragmentation factor is minimized.

4. Worst Fit: In this algorithm, OS allocates the process to that partition, which is the first Largest (among the all free available partition) to accommodate that process.

Allocation Methods in FIXED and Dynamic Partitions are explained under,

1. Fix Sized Partitions

Explain with example

Let’s suppose we have four FIX-sized partitions with sizes 1MB, 6MB, 5MB, and 4MB, respectively, and four incoming processes (P1 to P4) with sizes 4MB, 1MB, 3MB, and 2MB, respectively.

 Let’s start the Next Fit algorithm execution from above mentioned processes and memory. 

 Let’s start the Best Fit algorithm execution from above-mentioned processes and memory.

Let’s start the Worst Fit algorithm execution from above mentioned processes and memory.

2. Dynamic Partitions

Explain With Example

Let’s suppose we have four empty Dynamic sized partitions with sizes 1MB, 6MB, 5MB, and 4MB, respectively

and four incoming processes (P1 to P4) with sizes 4MB, 1MB, 3MB, and 2MB, respectively.

Case 01: First Fit

Case 02: Next Fit

Case 03: Best Fit

Case 04: Worst Fit

Practice Questions

Question 1:  if there are 8 jobs (J1 to J8) arriving at time zero having job sizes 2K, 14K, 3K, 6K, 6K, 10K, 7K, 20K, respectively, and their usage time 4, 10, 2, 8, 4, 1, 8, 6 respectively then calculate the time at which Job 7 will complete by applying BEST FIT algorithm.

Solution

Step 1

 As it is the best fit case, so J1 fits in 2K, J2 in 20K, J3 in 4K, and J4 in 8K memory Partitions. Timeline of completion time of all jobs is given below

 

Step 2

J5 came now, but the memory is already full. J5 waits for the termination of any Job, so J5 will check the timeline to find his place in memory. At Point 2, Job J3 terminates, but its space is not enough to accommodate J6 size, and the same case with J1 at Point 4.

So at point 8, Job J4 is completed, and J5 enters at point 8 and is completed at point 12.   

Step 3

J6 came now, but the memory is already full. J6 waits for the termination of any Job, so J6 will check the timeline to find his place in memory. At Point 2, Job J3 terminates, but its space is not enough to accommodate J6 size, and the same case with J1 at Point 4.

So at point 10, Job J2 is completed, and J6 enters at point 8 and is completed at point 11.

Because its execution time is 1.   

Step 4

 J7 came now, following the previous rules, so it will replace J6 and terminate at point 19.   

 

Question2: In dynamic partitions, If the process requests are in the given order

• 300MB
• 25MB
• 125MB
• 50MB

and two memory blocks are available in sizes of 150MB and 350 MB.
Which of the following partition allocation methods fulfills the above conditions?

A) Best fit but not first fit.
B) Both first fit & best fit.
C) First fit but not best fit.
D) Neither first fit nor best fit.

Solution

According to First Fit

According to Best Fit

So, option C is the correct choice.