Memory Allocation Fit Algorithms

Introduction

Variable partitioning creates memory blocks according to process requirements. As processes enter and leave memory, free space may become scattered into multiple holes.

When a new process requests memory, the operating system may find more than one suitable hole. First Fit, Best Fit, Worst Fit, and Next Fit are four classic rules for choosing which hole to use.

Why Fit Algorithms Are Needed

In variable partitioning, memory is not divided into fixed-size partitions in advance. Instead, the OS keeps track of free holes and allocates memory from them when processes arrive.

The problem is not only whether enough memory exists. The OS must also decide which free hole should be selected, because each choice changes the holes left for future requests.

If the selected hole is larger than the request, the remaining part stays as a smaller free hole.

First Fit

First Fit scans the free-hole list from the beginning and selects the first hole large enough for the request.

It does not try to find the smallest suitable hole or the largest suitable hole. It stops as soon as it finds a block that works.

For example, if the holes are 100 KB, 500 KB, 200 KB, 300 KB and the request is 212 KB, First Fit selects 500 KB because it is the first hole large enough.

Best Fit

Best Fit searches the available holes and selects the smallest hole that is still large enough for the request.

The idea is to avoid using a much larger block when a closer-sized block is available. However, Best Fit can leave many tiny leftover holes.

For example, if the holes are 100 KB, 500 KB, 200 KB, 300 KB, 600 KB and the request is 212 KB, Best Fit selects 300 KB because it is the smallest hole that can fit the request.

Worst Fit

Worst Fit chooses the largest available hole that can hold the process.

The intention is to leave a reasonably large remainder after allocation. In practice, it can also consume large holes early, which may hurt later large requests.

For example, with holes 100 KB, 500 KB, 200 KB, 300 KB, 600 KB and request 212 KB, Worst Fit selects 600 KB.

Next Fit

Next Fit is similar to First Fit, but it does not restart from the beginning every time. It remembers where the previous allocation happened and continues searching from the next position.

If it reaches the end of the hole list, it wraps around to the beginning and continues the search.

This can reduce repeated scanning from the start, but the final result still depends heavily on the request order and remaining hole sizes.

Comparison of Fit Algorithms

All four algorithms solve the same problem: selecting a free hole for a memory request. Their difference is the rule used for choosing that hole.

Compact Worked Example

Use the same initial holes for all four algorithms:

• Free holes: 100 KB, 500 KB, 200 KB, 300 KB, 600 KB

• Requests: 212 KB, 417 KB, 112 KB, 426 KB

Best Fit succeeds in this particular example, but that does not mean Best Fit is always best. A different request sequence can produce a different result.

Fragmentation Effect

Every allocation changes the memory state. A hole that is useful now may be split into a smaller hole, and that smaller hole may or may not be useful later.

Best Fit can create very small holes. Worst Fit can consume large holes too early. First Fit and Next Fit may leave different patterns because they search from different starting positions.

The important idea is that fragmentation depends on both the algorithm and the sequence of process requests.

Summary

First Fit, Best Fit, Worst Fit, and Next Fit are allocation strategies used with variable partitioning. They decide which free memory hole should be assigned to an incoming process.

First Fit chooses the first suitable hole, Best Fit chooses the smallest suitable hole, Worst Fit chooses the largest suitable hole, and Next Fit continues searching from the previous allocation position. Different choices create different fragmentation patterns.