Memory Allocation (First Fit, Best Fit)

Main memory must accommodate both the operating system and the various user processes. Therefore, we need to allocate main memory in the most efficient way possible.

Before the invention of Paging, memory was allocated contiguously. This meant that an entire process had to be loaded into a single, continuous block of physical memory.

1. Contiguous Allocation

In contiguous memory allocation, the memory is usually divided into two partitions: one for the resident operating system and one for the user processes.

When a process arrives and needs memory, the OS searches the physical memory for a free block (a hole) that is large enough to accommodate the process.

Over time, as processes are loaded and removed from memory, the free memory space is broken into little pieces. We are left with a set of scattered holes of various sizes.

2. Dynamic Storage-Allocation Problem

How does the OS satisfy a request of size $n$ from a list of free holes? There are three standard strategies:

First-Fit

Allocate the first hole that is big enough.

• How it works: The OS scans the list of holes from the beginning and assigns the process to the first hole it finds that is $\ge n$.
• Pros: Generally the fastest algorithm, as it minimizes the amount of searching.

Best-Fit

Allocate the smallest hole that is big enough.

• How it works: The OS must search the entire list of holes (unless the list is sorted by size) and chooses the hole whose size is closest to the process size.
• Pros: Produces the smallest leftover hole.
• Cons: Extremely slow due to the full list scan. Ironically, the tiny leftover holes it produces are often too small to be useful, contributing to severe external fragmentation.

Worst-Fit

Allocate the largest hole.

• How it works: The OS must search the entire list and allocates the process into the absolute largest available block of memory.
• Pros: The leftover hole is large, making it more likely to be useful for another incoming process.
• Cons: Performance is generally worse than First-Fit, and it prevents large processes from running because the massive blocks are split up early on.

3. Fragmentation

Contiguous memory allocation suffers from severe fragmentation problems, which drastically reduce system efficiency.

External Fragmentation

Exists when there is enough total memory space to satisfy a request, but the available spaces are not contiguous. The free memory is chopped up into a large number of small holes scattered throughout RAM.

• Solution: Compaction. The OS can pause all processes, shuffle the memory contents, and place all free memory together in one large block. However, this is incredibly expensive and slow.

Internal Fragmentation

Memory allocated to a process may be slightly larger than the requested memory. The difference between these two numbers is internal fragmentation—memory that is internal to a partition but is not being used.

• Example: If memory is allocated in fixed blocks of 4KB, and a process requests 3KB, the OS allocates the full 4KB block. The remaining 1KB is wasted and cannot be used by any other process.