Main Memory Management, Virtual Memory, and Page Replacement

Memory management is a core operating system responsibility that dictates how physical and virtual memory spaces are allocated, tracked, and secured among multiple concurrent processes. This chapter covers deadlock management strategies, physical memory hierarchies, continuous memory allocation techniques, paging and segmentation architectures, and the operational mechanics of virtual memory, page fault handling, and thrashing.

1. Deadlock Handling Strategies

To manage deadlocks in multi-process systems where resource competition can create indefinite circular waiting, operating systems deploy four primary architectural strategies:

1. Deadlock Prevention: Involves invalidating at least one of the four essential Coffman conditions (Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait).
2. Deadlock Avoidance: The operating system dynamically evaluates every resource request in advance. It only grants resources if the resulting system state is a Safe State—meaning there exists a valid process execution sequence (a Safe Sequence) where all processes can run to completion. A classic implementation of this is Banker's Algorithm, which uses matrices of resource Allocation, Max demand, and Available capacity to calculate remaining Need.
3. Deadlock Detection and Recovery: The system allows deadlocks to occur, periodically executes a cycle detection algorithm over the resource-allocation graph, and initiates recovery when a cycle is detected. Recovery involves terminating one or more deadlocked processes or preempting allocated resources.
4. Deadlock Ignorance (The Ostrich Algorithm): The OS ignores the possibility of deadlocks entirely. This approach is adopted by general-purpose operating systems like Linux and Windows because deadlocks are relatively rare, and the performance overhead of continuous prevention or avoidance algorithms is not cost-effective for general computing workloads.

2. Memory Hierarchy and Address Binding

The Storage Hierarchy

Because high-speed memory is cost-prohibitive to manufacture at scale, modern computers organize memory into a multi-tiered hierarchy. As you move downward through the hierarchy, capacity increases, access latency increases, and cost per byte decreases.

Address Binding Stages

Address binding maps a program's symbolic instructions and data to actual physical memory addresses:

• Compile Time: If the target physical address is known at compile time, absolute code with fixed addresses is generated. Changing the location requires recompiling.
• Load Time: The compiler produces relocatable code. The final physical binding occurs when the loader places the program into memory.
• Execution (Run) Time: If a process can be moved across different physical memory frames during its execution, binding is deferred until run time. This requires dedicated hardware support (the Memory Management Unit).

3. Logical vs. Physical Address Spaces and the MMU

Modern operating systems separate the program's perceived memory space from the actual physical RAM chips.

• Logical (Virtual) Address: The address generated by the CPU while executing an instruction. The program operates entirely within this logical abstraction.
• Physical Address: The actual electrical address seen by the memory hardware bus (the RAM chips).
• Memory Management Unit (MMU): The dedicated hardware component that translates logical addresses into physical addresses on the fly at runtime using base/relocation registers and translation tables.

4. Contiguous Memory Allocation and Fragmentation

In contiguous allocation, each process is loaded into a single contiguous block of physical memory.

Partitioning Strategies

1. Fixed Partitioning: Physical memory is pre-divided into fixed-size regions. Processes are assigned to these partitions.
2. Dynamic Partitioning: Memory partitions are created dynamically based on the exact memory footprint requested by a process.

Real-Life Analogy: The Over-Sized Slice

Real-Life Analogy

Imagine cutting a large cake into fixed, equal-sized large slices. If a young child asks for a piece because they only want a small bite, you still have to give them the entire fixed slice. The unused portion of that slice goes to waste and cannot be given to anyone else. This represents internal fragmentation.

Types of Fragmentation

• Internal Fragmentation: Occurs when allocated memory blocks are larger than the requested payload. The unused space within an assigned partition is wasted.
• External Fragmentation: Occurs in dynamic partitioning when total free memory across the system is sufficient to satisfy a request, but the space is broken into small, scattered holes that are non-contiguous.

Dynamic Allocation Strategies

• First Fit: Allocates the very first available free block (hole) that is large enough. Fast execution.
• Best Fit: Scans the entire list of free holes and allocates the smallest hole that is large enough, minimizing leftover space in that partition. Tends to create many tiny, unusable holes.
• Worst Fit: Allocates the largest available hole, leaving behind the largest possible remainder block for future requests.
• Next Fit: Begins searching from the location of the previous allocation rather than starting from the top of the list.

5. Paging and Page Table Architectures

Paging eliminates external fragmentation by allowing a process's physical memory allocation to be non-contiguous.

Core Definitions

• Pages: Fixed-size logical blocks into which the process's address space is divided.
• Frames: Fixed-size physical memory blocks into which RAM is divided. A Frame has the exact same byte size as a Page.
• Page Table: A per-process data structure maintained by the OS that translates logical Page Numbers ($p$) to physical Frame Numbers ($f$).

Address Translation Mechanism

A logical address generated by the CPU is divided into two parts:

1. Page Number ($p$): Used as an index into the process page table.
2. Page Offset ($d$): The displacement within the page/frame.

Scaled Page Table Architectures

1. Hierarchical (Multi-Level) Paging: When 32-bit or 64-bit systems have large address spaces, a flat single page table becomes too large to store contiguously in memory. Multi-level paging divides the page table itself into distinct pages, introducing outer and inner page tables.
2. Inverted Page Table: Instead of keeping one page table per process (which tracks every virtual page), an inverted page table contains only one entry per physical memory frame. Each entry records which process ID owns the frame and which virtual page maps to it, significantly reducing the memory overhead of the page tables.

6. Paging vs. Segmentation

Segmentation divides a program into variable-sized logical units (Code, Stack, Heap, Shared Libraries) that reflect the programmer's view of the software, rather than fixed-size byte blocks.

7. Virtual Memory and Demand Paging

Virtual memory abstracts physical storage, providing programs with the illusion of an expansive, contiguous address space that can exceed the actual capacity of physical RAM.

Demand Paging

In a demand paging architecture, pages are not pre-loaded into RAM during process startup. Instead, a page is brought into physical memory only when the running process attempts to read or execute an address within that page.

The Page Fault Handling Cycle

8. Page Replacement Algorithms

When a page fault occurs and no physical memory frames are free, the OS must select an existing frame to evict. The chosen algorithm directly influences page fault rates and system throughput.

Common Replacement Strategies

1. FIFO (First-In, First-Out):
   • Evicts the page that has been in physical memory for the longest time.
   • Pitfall: Susceptible to Belady's Anomaly, where increasing the number of physical frames can paradoxically increase the number of page faults.
2. Optimal Page Replacement (OPT / MIN):
   • Evicts the page that will not be accessed for the longest duration in the future.
   • Feasibility: Cannot be implemented in real operating systems because it requires perfect knowledge of future memory accesses. It is used as a theoretical benchmark.
3. LRU (Least Recently Used):
   • Evicts the page that has not been accessed for the longest period in the past (using past behavior to approximate future access patterns).
   • Requires hardware tracking mechanisms, such as access timestamps or a stack.
4. Clock (Second-Chance) Algorithm:
   • An approximation of LRU. It arranges frames in a circular queue and maintains a single reference bit per frame.
   • If the bit is 0, the page is chosen for eviction. If the bit is 1, the OS clears the bit to 0, advances the clock hand, and gives the page a second chance.

9. Thrashing: Causes, Mechanics, and Mitigation

What is Thrashing?

Thrashing occurs when an operating system spends significantly more time swapping pages into and out of secondary storage than it does executing actual application instructions.

Real-Life Analogy: The Over-Spiced Meal

Real-Life Analogy

Spending ₹100 on a chicken dish but buying ₹200 worth of spices to cook it means you are spending twice as much on preparation overhead as on the actual food. Thrashing is identical: the operating system spends far more computational time on the overhead of paging (swapping pages to disk) than on the actual execution of the program.

Root Causes and Working Set Model

• Cause: The degree of multiprogramming is too high. The total physical frames available cannot accommodate the Working Sets (the collection of pages actively referenced during a given time window) of all running processes.
• Resolution:
  • The OS must track the working set sizes of processes and reduce the degree of multiprogramming by temporarily suspending or swapping out one or more processes.
  • Allocate a sufficient number of baseline frames to remaining processes to stabilize page fault frequencies.

Summary and Key Takeaways

• Deadlock Management: Operating systems choose between prevention (breaking Coffman conditions), avoidance (Banker's Algorithm checking for safe states), detection/recovery, or ignorance (the Ostrich algorithm, standard in Linux/Windows).
• Physical Memory Hierarchy: Memory access speed follows a strict trade-off where registers and SRAM caches are fast and expensive, RAM provides medium capacity and speed, and secondary storage provides high capacity with high latency.
• MMU Role: Address translation maps logical (CPU-generated) addresses to physical (hardware RAM) addresses at runtime, isolating process spaces.
• Contiguous Allocation Trade-offs: Fixed partitions lead to internal fragmentation, while dynamic partitions lead to external fragmentation.
• Paging Mechanics: Paging divides memory into fixed-size logical pages and physical frames, eliminating external fragmentation through page table lookups.
• Segmentation Strategy: Segmentation maps variable-sized logical code segments (Code, Data, Stack) to physical blocks, reflecting developer domain boundaries while introducing external fragmentation risks.
• Demand Paging: Virtual memory allows execution of partially loaded processes by generating page faults when missing pages need to be loaded from disk on demand.
• Eviction Algorithms: FIFO is simple but prone to Belady's anomaly, Optimal provides a theoretical ceiling, and LRU/Clock serve as practical real-world replacement algorithms.
• Thrashing Dynamic: When physical frames fall below the working set requirements of active processes, the OS enters a state where Disk I/O overhead dominates CPU execution.