First Fit Best Fit Worst Fit in OS (Example)

best, worst, first fit in os

First Fit Best Fit Worst Fit in OS


The modern computer system has memory space divided into blocks of varying sizes. The operating system assigns these memory block to the different process demanding empty memory spaces. This memory is assigned in the main memory segment depending on the demanded memory and the empty memory slots present in the main memory.

Processes need execution time/storage space in memory blocks. OS has various algorithms to allocate in-coming processes to available memory blocks.

The following are the most used algorithms –

  • First Fit
  • Best Fit
  • Worst Fit

Code for Each Algorithm

Example of First Fit Method

This method works as for any process Pn, the OS searches from starting block again and again and allocates a block to process Pn such that –

  • Block is available 
  • Can fit the process

In simple words First Fit algorithm finds, the first block to fix the process.

In the given example, let us assume the jobs and the memory requirements as the following:

First Fit Allocation in OS ex

Process

ProcessProcess Size
Process 190
Process 250
Process 330
Process 440

Let the free space memory allocation blocks be:

Blocks

BlockBlock Size
Block 120
Block 2100
Block 340
Block 4200
Block 510

Explanation

Process P1

  • All Blocks 1 – 5 are available
  • P1 checks for block 1, Block 1 Size (20K) < P1 size (90K), can’t fit
  • P2 checks for block 2, Block 2 Size (100 k) > p1 size (90K)
  • P2 goes to block 2

Process 2

  • Block 1 size (20K) < P2 size (50K), can’t fit
  • Block 2 is already occupied by P1, unavailable
  • Block 3 size (40K) < p2 size (50K), can’t fit
  • Block 4 size (200K) > p2 size (50K)
  • Block 4 allocated to P2

Process 3

  • Block 1 size (20K) < p3 size (30K)
  • Block 2 unavailable
  • Block 3 size (40K) > p3 size (30K)
  • Block 3 allocated to p3

Process 4

  • Block 1 size (20K) < p4 size (40K)
  • Block 2, 3, 4 are unavailable
  • Block 5 size (10K) < p4 size (40K)
  • Process 4 remains unallocated

Result

ProcessSizeAllocated toBlock sizeMemory Wastage
Process 190Block 210010
Process 250Block 4200150
Process 330Block 34010
Process 440Unallocated

Let’s have a look at the detailed explanation in the image below –

First Fit Allocation in OS

Example of Best Fit Method

This method works as for any process Pn, the OS searches from starting block again and again and allocates a block to process Pn such that –

  • Block can accommodate process
  • Memory wastage is minimum

In the given example, let us assume the jobs and the memory requirements as the following:

Process

ProcessSize
Process 140
Process 210
Process 330
Process 460

Blocks

Let the free space memory allocation blocks be:

BlocksSize
Block 1100
Block 250
Block 330
Block 4120
Block 535

Job 1 (size – 40K)

  • Block 3 and 5 can not place as their size is lesser than 40K
  • Block 1 Memory wastage : 100 – 40 = 60K
  • Block 2 Memory wastage : 50 – 40 = 20K
  • Block 4 Memory wastage : 120 – 40 = 80K
  • Thus Block 2 is best, P1 placed in block 2

Job 2 (size – 10K)

  • Block 2 is unavailable now
  • Block 1 memory wastage: 100 – 10 = 90
  • Block 3 memory wastage: 10 – 10 = 20
  • Block 4 memory wastage : 120 – 10 = 110
  • Block 5 memory wastage: 35 – 10 = 25
  • Thus, block 3 is the best, P2 placed in block 3

Job 3 (size – 30K)

  • Block 2, 3 unavailable
  • Block 1 memory wastage : 100 – 30 = 70
  • Block 4 memory wastage : 120 – 30 = 90
  • Block 5 memory wastage : 35 – 30 = 5
  • Thus, block is the best, P3 placed in block 5

Job 4 (size 60K)

  • Block 2, 3 and 5 are unavailable
  • Block 1 memory wastage : 100 – 60 = 40
  • Block 4 memory wastage : 120 – 60 = 60
  • Thus, block 1 is the best P4 goes to block 1

Results

ProcessSizeAllocated toBlock sizeWastage
Process 140Block 25010
Process 210Block 33020
Process 330Block 5355
Process 460Block 110040

Example of Best Fit Method

This method works as for any process Pn, the OS searches from starting block again and again and allocates a block to process Pn such that –

  • Block can accommodate process
  • Memory wastage is maximum
Worst Fit Allocation in OS Working

In the given example, let us assume the jobs and the memory requirements as the following:

Process

ProcessSize
Process 140
Process 210
Process 330
Process 460

Blocks

Let the free space memory allocation blocks be:

BlocksSize
Block 1100
Block 250
Block 330
Block 4120
Block 535

Explanation

Process 1 (size 40K)

  • Block 2 and 5 are smaller than P1 thus can not accommodate
  • Block1 memory wastage : 100 – 40 = 60
  • Block2 memory wastage: 50 – 40 = 10
  • Block3 memory wastage 120 – 40 = 80
  • Thus Block 3 is worst and P1 goes to block 3

Process 2 (size: 10)

  • Block 4 is occupied
  • Block 1 memory wastage: 100 – 10 = 90
  • Block 2 memory wastage : 50 – 10 = 40
  • Block 3 memory wastage: 30 – 10 = 20
  • Block 5 memory wastage: 35 – 10 = 25
  • Thus, block 1 is the worst, and Process 2 goes to block 1

Process 3 (size: 30K)

  • Block 1 and 4 are occupied
  • Block 2 memory wastage : 50 – 30 = 20
  • Block 3 memory wastage : 30 – 30 = 0
  • Block 5 memory wastage: 35 – 30 = 5
  • Thus block 2 is the worst, process 3 goes to block 2

Process 4 (size : 60K)

  • Block 1, 2 and 3 are occupied
  • Block 3 and 4 can not accommodate the process p4
  • Thus, process 4 will remain unallocated

Results

ProcessSizeAllocated toBlock sizeWastage
Process 140Block 412080
Process 210Block 110090
Process 330Block 25020
Process 460Unallocated
Worst Fit Allocation in OS Example new