First Fit Best Fit Worst Fit in OS (Example)

April 1, 2022

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

[table id=987 /]

Let the free space memory allocation blocks be:

Blocks

[table id=988 /]

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

[table id=991 /]

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

[table id=992 /]

Blocks

Let the free space memory allocation blocks be:

[table id=993 /]

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

[table id=995 /]

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

[table id=992 /]

Blocks

Let the free space memory allocation blocks be:

[table id=993 /]

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

[table id=994 /]

Worst Fit Allocation in OS Example new
Operating systems Memory

      Read More

  1. Memory Management Introduction
  2. Partition Allocation Method
    1. First Fit in OS
      1. Program in C | C++ | Java | Python
    2. Best fit
      1. Program in C | C++ | Java | Python
    3. Worst fit
      1. Program in C | C++ | Java | Python
    4. Next fit
      1. Program in C | C++ | Java | Python
    5. First fit best fit worst fit in OS Example
  3. Buddy- System Allocator
  4. Paging
    1. Types of Paging
  5. Fragmentation
    1. internal fragmentation
    2. external fragmentation
    3. internal fragmentation vs external fragmentation
  6. Mapping Virtual address to Physical Address.
  7. Virtual Memory 
  8. Demand Paging
  9. Implementation of Demand paging and page fault
  10. Segmentation
  11. Page Replacement Algorithms
    1. LRU
    2. FIFO
    3. Optimal Page Replacement algorithm
  12. Thrashing
  13. Belady’s Anomaly
  14. Static vs Dynamic Loading
  15. Static vs Dynamic Linking
  16. Swapping
  17. Translational Look Aside Buffer
  18. Process Address Space
  19. Difference between Segmentation and Paging
Go to Operating System Tutorials Main Page