Memory Allocation: First Fit vs. Best Fit vs. Worst Fit Explained

🧠 Mastering Memory Allocation: First Fit vs. Best Fit vs. Worst Fit Explained

Hello, future computer scientists! Today, we're diving into a fundamental concept in Operating Systems: Dynamic Storage Allocation.

When processes need memory, the OS has to decide where to put them in the available "holes" (free blocks) of RAM. The strategy it uses can significantly impact system performance and memory efficiency.

Let's explore the three classic algorithms for this: First Fit, Best Fit, and Worst Fit, using the exact example from your image.

The Problem

We have a set of available memory blocks (holes) and a queue of processes waiting to be allocated.

• Available Memory Holes: 50K, 75K, 150K, 175K, 300K
• Process Requests (in order): P1(25K), P2(50K), P3(100K), P4(75K)

Let's see how each algorithm handles this!

---

1. First Fit Algorithm

The Logic: Scan the memory holes from the beginning and place the process in the first hole that is large enough to hold it. This is the fastest algorithm.

Step-by-Step Allocation:

• Initial Holes: [50K, 75K, 150K, 175K, 300K]

1. Process P1 (25K):
   • Scans holes: 50K is the first block >= 25K.
   • Allocate: P1 goes into the 50K block.
   • Remaining Holes: [25K, 75K, 150K, 175K, 300K] (50-25=25K leftover)
2. Process P2 (50K):
   • Scans holes: 25K (too small), 75K is the first block >= 50K.
   • Allocate: P2 goes into the 75K block.
   • Remaining Holes: [25K, 25K, 150K, 175K, 300K] (75-50=25K leftover)
3. Process P3 (100K):
   • Scans holes: 25K (too small), 25K (too small), 150K is the first block >= 100K.
   • Allocate: P3 goes into the 150K block.
   • Remaining Holes: [25K, 25K, 50K, 175K, 300K] (150-100=50K leftover)
4. Process P4 (75K):
   • Scans holes: 25K (small), 25K (small), 50K (small), 175K is the first block >= 75K.
   • Allocate: P4 goes into the 175K block.
   • Remaining Holes: [25K, 25K, 50K, 100K, 300K] (175-75=100K leftover)

• Final Result (First Fit): All processes are allocated. The final memory holes are [25K, 25K, 50K, 100K, 300K].

---

2. Best Fit Algorithm

The Logic: Scan the entire list of holes. Place the process in the smallest hole that is large enough. This tries to leave the smallest possible leftover fragment.

Step-by-Step Allocation:

• Initial Holes: [50K, 75K, 150K, 175K, 300K]

1. Process P1 (25K):
   • Holes >= 25K are: [50K, 75K, 150K, 175K, 300K]
   • The best (smallest) fit is 50K.
   • Allocate: P1 goes into the 50K block.
   • Remaining Holes: [25K, 75K, 150K, 175K, 300K]
2. Process P2 (50K):
   • Holes >= 50K are: [75K, 150K, 175K, 300K]
   • The best (smallest) fit is 75K.
   • Allocate: P2 goes into the 75K block.
   • Remaining Holes: [25K, 25K, 150K, 175K, 300K]
3. Process P3 (100K):
   • Holes >= 100K are: [150K, 175K, 300K]
   • The best (smallest) fit is 150K.
   • Allocate: P3 goes into the 150K block.
   • Remaining Holes: [25K, 25K, 50K, 175K, 300K]
4. Process P4 (75K):
   • Holes >= 75K are: [175K, 300K]
   • The best (smallest) fit is 175K.
   • Allocate: P4 goes into the 175K block.
   • Remaining Holes: [25K, 25K, 50K, 100K, 300K]

• Final Result (Best Fit): All processes are allocated. The final memory holes are [25K, 25K, 50K, 100K, 300K].
  • Note: In this specific case, First Fit and Best Fit gave the same result! This is because our initial list of holes was already sorted by size.

---

3. Worst Fit Algorithm

The Logic: Scan the entire list of holes. Place the process in the largest available hole. The idea is to leave the largest possible leftover fragment, which might be more useful for future processes.

Step-by-Step Allocation:

• Initial Holes: [50K, 75K, 150K, 175K, 300K]

1. Process P1 (25K):
   • Holes >= 25K are: [50K, 75K, 150K, 175K, 300K]
   • The worst (largest) fit is 300K.
   • Allocate: P1 goes into the 300K block.
   • Remaining Holes: [50K, 75K, 150K, 175K, 275K] (300-25=275K)
2. Process P2 (50K):
   • Holes >= 50K are: [50K, 75K, 150K, 175K, 275K]
   • The worst (largest) fit is 275K.
   • Allocate: P2 goes into the 275K block.
   • Remaining Holes: [50K, 75K, 150K, 175K, 225K] (275-50=225K)
3. Process P3 (100K):
   • Holes >= 100K are: [150K, 175K, 225K]
   • The worst (largest) fit is 225K.
   • Allocate: P3 goes into the 225K block.
   • Remaining Holes: [50K, 75K, 150K, 175K, 125K] (225-100=125K)
4. Process P4 (75K):
   • Holes >= 75K are: [75K, 150K, 175K, 125K]
   • The worst (largest) fit is 175K.
   • Allocate: P4 goes into the 175K block.
   • Remaining Holes: [50K, 75K, 150K, 100K, 125K] (175-75=100K)

• Final Result (Worst Fit): All processes are allocated. The final memory holes are [50K, 75K, 150K, 100K, 125K].

---

💻 Dynamic Example: Try It Yourself!

Want to test other scenarios? Use this dynamic simulator! Enter your own comma-separated values and see the results live.

Memory Holes (e.g., 50, 75, 150): Process Requests (e.g., 25, 50, 100):

Simulation Log:

Click a button to run a simulation...

---

🧠 Check Your Knowledge: Quick Quiz

Test your understanding with these multiple-choice questions. Click a button to see the answer!

Question 1:

Given holes [100K, 20K, 80K, 200K] and a process of 70K, where will First Fit place it?

Question 2:

Given holes [100K, 20K, 80K, 200K] and a process of 70K, where will Best Fit place it?

Question 3:

Which algorithm is generally the fastest to execute (has the lowest time complexity)?

---

Final Thoughts

As you can see, the choice of algorithm matters!

• First Fit is fast.
• Best Fit tries to save space but can create tiny, unusable holes (external fragmentation).
• Worst Fit tries to leave big, useful holes but can quickly consume the largest blocks, making it impossible to fit other large processes later.

There's no single "best" algorithm; it always depends on the specific workload and memory state.

Happy coding!