When multiple programs need to run at the same time, the operating system acts as a manager, deciding how to split up the computer's physical memory. The core challenge is simple: how do you divide a finite resource among competing demands? The earliest and most straightforward answers to this question involve contiguous allocation, where each process gets a single, unbroken block of memory. The two main strategies for this are fixed and variable partitioning.

The simplest approach is to divide memory into a set of fixed-size partitions when the system boots up. This is called fixed partitioning. These partitions can be of equal or unequal sizes, but once they are set, they don't change. When a new process arrives, the OS looks for a free partition large enough to hold it.

This method is straightforward to implement. The OS just needs to maintain a simple table, often called a static partition table, that tracks whether each partition is occupied or free. The number of partitions determines the maximum degree of multiprogramming – the system can't run more processes than it has partitions, regardless of how small those processes are.

The major drawback is inefficiency. If a 5MB process is placed in an 8MB partition, the 3MB of leftover space is wasted. This is known as internal fragmentation because the waste occurs inside the allocated partition. The process can't use it, and the OS can't assign it to any other process. Furthermore, a process that is larger than the biggest available partition simply cannot run at all, even if there is enough total free memory scattered across smaller partitions.

To address the wastefulness of fixed partitions, operating systems developed variable partitioning. In this dynamic scheme, memory is initially treated as one large, empty block. When a process arrives, the OS allocates a chunk of memory precisely the size that the process needs. There are no predefined boundaries.

When a process finishes, it frees its memory, which the OS then returns to the pool of available space. Over time, memory becomes a checkerboard of allocated blocks and free blocks, or 'holes'. The OS must keep track of these holes. It can do this using data structures like a linked list of free blocks or a bitmap representing the entire memory space.

This approach solves the problem of internal fragmentation. Since each partition is custom-sized for the process, there is no wasted space within the allocation. However, it introduces a new problem: external fragmentation.

As processes are loaded and unloaded, the free memory gets broken into many small, non-contiguous holes. You might have 5MB of total free memory, but it could be split into a 2MB chunk and a 3MB chunk. If a new 4MB process arrives, it cannot be loaded, even though there's technically enough free space. The memory is wasted outside the allocated partitions.

With variable partitioning, when a new process needs to be loaded, the OS has to decide which free hole to place it in. There are several common strategies, each with its own trade-offs.

• First-Fit: Scan memory from the beginning and choose the first hole that is large enough. This is fast but can lead to many small, unusable holes forming at the beginning of memory.
• Best-Fit: Search the entire list of holes and choose the smallest one that is large enough. This minimizes the size of the leftover hole but is slower because it must search everywhere. It can also create tiny, useless fragments.
• Worst-Fit: Search the entire list and choose the largest hole. The idea is that the leftover fragment will be large enough to be useful for another process. In practice, this often performs poorly.

These placement algorithms represent a classic computer science trade-off between speed and efficiency. First-fit is quick, while best-fit tries to be more clever about preserving memory but costs more in CPU cycles. The choice of algorithm directly impacts how quickly external fragmentation becomes a problem.

While both fixed and variable partitioning were foundational, their issues with fragmentation ultimately led to the development of more advanced techniques like paging and segmentation, which are standard in modern operating systems.