Memory Allocation Strategies in OS: First, Best, Worst Fit, Internal vs External Fragmentation

Memory allocation strategies and the two kinds of fragmentation are staple topics of the Memory Management unit of TU BSc CSIT Operating Systems (CSC264, unit 4) and the Memory Management unit of BIT Operating Systems (BIT204, unit 7). The same papers also set "differentiate deadlock from starvation" from the Process Deadlocks unit (CSC264 unit 3) and Deadlock Management (BIT204 unit 6), so this article covers that table too.

You will find contiguous allocation, first fit, best fit, worst fit and next fit explained with one worked example, the difference between internal and external fragmentation in a table, compaction and paging as the cure, and the deadlock vs starvation comparison.

Memory allocation strategies in OS

In contiguous allocation each process is loaded into one unbroken block of main memory. There are two ways to organise the blocks.

In fixed (static) partitioning, memory is divided into partitions of set sizes at boot time. A process is placed in a partition large enough for it, and the unused space inside that partition is wasted. The degree of multiprogramming is limited by the number of partitions.

In variable (dynamic) partitioning, a partition is created for each process with exactly the size it needs. Memory is a set of allocated blocks and free blocks called holes. As processes finish and leave, holes appear scattered through memory. When a new process arrives, the OS must pick a hole for it. This is the dynamic storage allocation problem, and the usual answers are the following.

First fit: scan the list of holes from the start and take the first hole big enough. It is fast because the search stops early.

Next fit: like first fit, but the scan starts from where the last search ended, wrapping round at the end of the list.

Best fit: search the entire list and take the smallest hole that is big enough. It leaves the smallest leftover, but needs a full search and leaves many tiny, nearly useless holes.

Worst fit: search the entire list and take the largest hole. The idea is that the leftover will be large enough to be useful, but in practice it breaks up the large holes quickly.

Simulations reported in Silberschatz show first fit and best fit are better than worst fit in both time and storage use, and that first fit is generally faster.

Worked example: first, best and worst fit

Take free holes in memory, in address order, of 100K, 500K, 200K, 300K and 600K. Processes of 212K, 417K, 112K and 426K arrive in that order. Place them with each strategy.

First fit. The 212K process takes the first hole that fits, which is 500K, leaving a hole of 288K. The 417K process skips 100K, 288K, 200K and 300K and takes 600K, leaving 183K. The 112K process skips 100K and takes the 288K hole, leaving 176K. The 426K process now finds holes of 100K, 176K, 200K, 300K and 183K, and none is large enough, so it must wait.

Best fit. The 212K process takes the smallest hole that holds it, 300K, leaving 88K. The 417K process takes 500K, leaving 83K. The 112K process takes 200K, leaving 88K. The 426K process takes 600K, leaving 174K. All four processes are placed.

Worst fit. The 212K process takes the largest hole, 600K, leaving 388K. The 417K process takes 500K, leaving 83K. The 112K process takes the largest remaining hole, 388K, leaving 276K. The 426K process finds holes of 100K, 83K, 200K, 300K and 276K, and none is large enough, so it waits.

Therefore best fit is the only strategy that places every process in this example, which is why the question is a classic: it shows the strategies can behave very differently on the same data. With next fit, the same sequence gives the same placements as first fit here, and 426K also waits. State the free holes remaining after each placement when you write it in the exam; that is what the marks follow.

Internal vs external fragmentation

Fragmentation is memory that is free but cannot be used. It takes two forms.

Silberschatz notes a statistical result called the 50-percent rule: with first fit, for every N blocks allocated, about 0.5 N blocks are lost to fragmentation, so one third of memory may be unusable.

Compaction and paging as the cure

Compaction shuffles memory contents so that all free holes join into one large block. It is possible only if relocation is dynamic, done at execution time using a relocation register, because the processes are moved and their addresses change. It is expensive because a lot of memory is copied, and the system is slow during the move.

The more permanent cure is non-contiguous allocation. Paging divides physical memory into fixed-size frames and a process into pages of the same size, so a process can be scattered over any free frames and external fragmentation disappears. Only the last page of a process is partly empty, so a small internal fragmentation remains, averaging half a page per process. Segmentation allows non-contiguous logical pieces but still suffers external fragmentation, since segments have different sizes.

Deadlock vs starvation

Because the Deadlock unit is in the same exam paper, the other frequently paired question is the comparison below.

Every deadlocked process is starved, but a starving process is not necessarily deadlocked.

How to write it in the exam

For 5 marks on memory allocation strategies, define contiguous allocation, describe first, best and worst fit in a line each, and show the worked example above with the leftover holes. For 10 marks, add fixed vs variable partitions, the fragmentation table, and compaction and paging as the solutions. For the fragmentation question alone, the table with the 20K and 50K + 40K + 30K examples is enough for 5 marks.

The unit notes are on Memory Management in CSC264 and Process Deadlocks, with past papers on the CSC264 subject page. BIT students should use Memory Management in BIT204 and Deadlock Management.