Q4Operating Systems (Departmental Elective)

In the early eras of Operating System design, physical RAM was managed using the strict architectural paradigm of Contiguous Memory Allocation. When a user executes a 10MB program, the OS Kernel is mathematically forced to hunt down a single, unbroken, perfectly contiguous 10MB block of physical memory. The program cannot be fractured.

The Mathematical Allocation Algorithms

As processes load and terminate, the RAM shatters into a massive list of random-sized free blocks (Holes). To satisfy a request of size $N$, the OS uses three search algorithms:

• 1. First-Fit: The OS aggressively scans the memory list from the very beginning and violently allocates the absolute first hole it finds that is $\ge N$. It is incredibly fast but heavily fragments the front of the RAM.
• 2. Best-Fit: The OS mathematically scans the ENTIRE list of holes to find the absolute tightest fit (the smallest hole that is $\ge N$). This minimizes wasted internal space but leaves behind microscopic, completely useless slivers of RAM.
• 3. Worst-Fit: The OS scans the entire list and violently allocates the absolute largest hole available. The theory is that the leftover fragment will be massive enough to hold another process.

The Catastrophe of External Fragmentation

Contiguous Allocation suffers from a fatal mathematical flaw: External Fragmentation. Over time, the RAM becomes a warzone of tiny scattered holes. Suppose a 50MB process demands RAM. The OS scans the memory and calculates there is 100MB of total free space. However, because that 100MB is physically shattered into fifty 2MB holes scattered randomly, the contiguous allocation mathematically fails. The process is violently blocked despite massive available memory. The only primitive solution is "Compaction"—aggressively pausing the entire CPU to physically shift gigabytes of RAM to merge the holes, creating catastrophic system latency.