Memory Management
Open in the Padhaiko app4.2 Memory Management
In a modern multiprogramming computer system, the central processing unit (CPU) fetches instructions and operands directly from primary memory (RAM) and high-speed CPU registers. Because modern software applications frequently require more memory than physical RAM can accommodate, and because multiple processes must execute concurrently without interfering with one another, the operating system's memory management subsystem performs several fundamental tasks (OS Ch4):
- Tracking Memory State: Monitors every byte of physical memory to determine whether it is currently allocated to an active process or free for allocation.
- Dynamic Memory Allocation & Deallocation: Allocates physical memory blocks to incoming processes, reclaims memory upon process termination, and manages runtime heap expansion.
- Protection & Isolation: Ensures that each process accesses only its designated legal address range, protecting user processes from one another and safeguarding the OS kernel.
- Relocation & Virtual Memory: Transparently maps logical program addresses to arbitrary physical RAM addresses and moves processes between main memory and secondary storage (swapping and demand paging).
4.2.1 Memory address, swapping and managing free memory space
Logical vs. Physical Address Spaces
To provide process isolation and dynamic relocation, operating systems enforce a strict separation between logical and physical memory addresses:
Logical and Physical Addresses
- Logical Address (Virtual Address): An address generated by the CPU while executing an instruction. The complete set of all logical addresses generated by a program constitutes its logical address space.
- Physical Address: The actual hardware memory location presented to the memory controller and loaded into the Memory Address Register (MAR) over the system bus. The set of all corresponding physical addresses is the physical address space.
- Memory Management Unit (MMU): The hardware component situated between the CPU core and the physical memory bus that converts each logical address into a physical memory address at runtime.
The conversion of program instructions and data addresses from symbolic names to hardware physical addresses is called address binding, which occurs at one of three distinct phases:
- Compile Time: If it is known at compile time where the process will reside in physical RAM, the compiler generates absolute code (fixed physical addresses). If the starting location changes, the program must be completely recompiled.
- Load Time: If the load address is unknown at compile time, the compiler generates relocatable code. Address binding is delayed until the loader places the binary into memory. If the process is later moved, it must be reloaded from disk.
- Execution Time (Run Time): If a process can be moved from one memory segment to another during execution (e.g., via swapping), address binding is delayed until instruction execution. This requires dedicated hardware support such as base and limit registers.
| Aspect | Logical Address | Physical Address |
|---|---|---|
| Origin | Generated by the CPU during instruction fetch/execution | Present on the address bus to physical RAM chips |
| Visibility | Directly visible to user programs and compilers | Hidden from user programs; managed exclusively by the MMU and kernel |
| Range | to | to |
| Binding Time | Determined at compile/assembly time | Determined at execution time via MMU translation |
Hardware Protection: Base and Limit Registers
In simple contiguous allocation systems, memory protection is enforced using a pair of hardware registers (OS Ch4):
Base and Limit Registers
- Base Register (Relocation Register): Holds the smallest legal physical memory address assigned to the currently running process.
- Limit Register: Specifies the exact range or size (in bytes or words) of the process's allocated memory space.
For any memory reference with logical address :
- The CPU hardware first checks whether .
- If , the access is out of bounds; the CPU triggers a hardware trap to the operating system (addressing error / segmentation violation), terminating or suspending the offending process.
- If , the relocation unit adds the base address to compute the physical memory address:
- The valid physical memory range accessible to the process is .
Swapping
Because installed physical RAM is finite, it cannot simultaneously hold the address spaces of all active processes in a busy multiprogramming environment (OS Ch4).
Swapping
Swapping is a memory management technique wherein an operating system temporarily moves an entire idle or blocked process from main memory to a secondary storage device (backing store / swap space on disk), and later brings it back into main memory for continued execution.
- Swap Out: Moving a process image from RAM to secondary storage to free contiguous memory for another ready process.
- Swap In: Loading a suspended process image from secondary storage back into physical memory when CPU scheduling assigns it execution time.
- Advantages of Swapping:
- Enables a much higher degree of multiprogramming than physical RAM size alone would allow.
- Allows dynamic relocation and priority-based scheduling (low-priority processes can be swapped out to admit higher-priority real-time jobs).
- Maximizes overall CPU utilization by ensuring a queue of ready processes always occupies memory.
- Disadvantages and Overheads:
- Transfer Time Bottleneck: Secondary disk access is orders of magnitude slower than semiconductor RAM. For example, swapping out a process over a disk channel transferring at requires of pure transfer latency, completely dominating context-switch time.
- Hole Fragmentation: Swapping in and out variable-sized process images creates non-contiguous gaps ("holes") of unused memory.
Contiguous Memory Allocation Schemes
In contiguous allocation, each process is loaded into a single contiguous block of physical memory addresses.
1. Single-Partition Allocation (Bare Machine & Resident Monitor)
- The operating system kernel is placed in low memory (or high memory), protected by a fence register.
- The remaining memory forms a single user partition allocated to one program at a time.
- Used in early batch processing (resident monitor) and MS-DOS; offers no concurrent multiprogramming.
2. Fixed-Size Partitioning (Multiprogramming with Fixed Tasks — MFT)
Memory is divided into static partitions at system configuration time (OS Ch4):
- Equal-Size Fixed Partitions: Every partition has the identical size (e.g., four partitions in a space). Any process of size can be loaded into any available free partition.
- Variable-Size (Unequal) Fixed Partitions: Partitions have differing fixed sizes (e.g., ). Arriving processes are placed either into separate input queues per partition size, or a single combined queue dispatched to the smallest partition large enough to hold the process.
| Fixed Partition Advantages | Fixed Partition Disadvantages |
|---|---|
| Extremely simple to implement with minimal CPU overhead | Limited Multiprogramming: Number of concurrent active processes is strictly bounded by partition count |
| Low operating system tracking complexity | Internal Fragmentation: Unused space inside an allocated partition is wasted |
| Fast dispatching | Process Size Ceiling: A process larger than the single largest partition cannot run |
3. Dynamic (Variable-Length) Partitioning (Multiprogramming with Variable Tasks — MVT)
To eliminate the rigid limits of fixed partitioning, partitions are created dynamically according to each process's exact memory request (OS Ch4):
- Initially, user memory is one large unallocated contiguous block (a single large "hole").
- When process requests bytes, the OS allocates exactly bytes from the hole, leaving a smaller hole of remaining memory.
- As processes terminate and deallocate memory, multiple disjoint holes of various sizes appear scattered across physical memory.
| Aspect | Internal Fragmentation | External Fragmentation |
|---|---|---|
| Definition | Unused memory that resides inside an allocated partition or page frame | Unused memory that resides outside allocated partitions, between active blocks |
| Occurrence | Fixed-size partitioning and paging (last page/partition larger than needed) | Dynamic (variable-length) partitioning and pure segmentation |
| Cause | Memory is allocated in discrete fixed-size blocks exceeding process requirements | Frequent allocation and deallocation leaving scattered holes of varying sizes |
| Primary Remedy | Allocate smaller partition/page sizes | Compaction (shuffling) or non-contiguous allocation (paging) |
Solutions to External Fragmentation: Coalescing and Compaction
When dynamic partitioning leaves memory riddled with scattered holes, two techniques are employed (OS Ch4):
- Coalescing: When a process terminates and its memory is released, the operating system inspects immediately adjacent neighboring blocks. If the preceding or succeeding block is also a free hole, the OS merges them into a single larger contiguous hole.
- Compaction (Defragmentation / Memory Shuffling): When total free memory is sufficient to satisfy an incoming process but no individual hole is large enough, the OS shifts all active processes toward one end of physical memory, consolidating all scattered holes into one large contiguous block.
- Requirement: Compaction is possible only if relocation is dynamic and performed at execution time using base/relocation registers.
- Overhead: Compaction requires copying hundreds of megabytes or gigabytes across the memory bus, freezing process execution and imposing severe CPU penalties.
Managing Free Memory Space: Bitmaps vs. Linked Lists
To keep track of which memory segments are allocated and which are free, operating systems maintain dedicated data structures:
| Technique | Structure & Organization | Advantages | Disadvantages |
|---|---|---|---|
| Bitmaps (Bit-Arrays) | Memory divided into fixed allocation units (e.g., ). Each unit is represented by bit in a bitmap (, ). | Compact, fixed-size tracking overhead: memory size depends only on total RAM and unit size (). | Slow search: finding a contiguous block of free units requires scanning the bitmap for a run of consecutive zeros. |
| Linked Lists | Doubly linked list of nodes, where each entry specifies type (P = process, H = hole), start address, length, and pointer to next node. | Fast coalescing: merging adjacent holes requires only checking predecessor and successor list nodes; allocation involves splitting node. | Extra memory pointer overhead; traversing long lists can become a performance bottleneck. |
| Buddy System | Memory allocated in power-of-two blocks (). When a hole of size is too large, it is split into two equal "buddies" of size . | Extremely fast allocation and instantaneous coalescing with buddy addresses calculated via bitwise XOR. | Causes moderate internal fragmentation when requested size is slightly larger than . |
Dynamic Storage Partition Selection Algorithms
When an arriving process requests bytes and multiple free holes in memory are large enough (), the operating system chooses a hole using one of four classic placement strategies (OS Ch4):
First Fit, Best Fit, Worst Fit, and Next Fit
- First Fit: Scans the free list from the beginning and allocates the very first hole that is large enough ().
- Performance: Generally the fastest algorithm because searching halts immediately upon finding the first adequate hole. Produces good overall memory utilization.
- Best Fit: Scans the entire list of holes and allocates the smallest hole that is large enough ().
- Performance: Minimizes immediate wasted space within the partition. However, it generates tiny, scattered residual holes ("dust") that are typically too small to satisfy any subsequent requests, worsening external fragmentation.
- Worst Fit: Scans the entire list and allocates the largest available hole.
- Performance: Leaves the largest possible residual hole, theoretically keeping leftover space usable for subsequent processes. However, simulation studies show it performs poorly in practice because it systematically breaks up the largest blocks needed by large jobs.
- Next Fit: Identical to First Fit, except the search begins at the location in the list where the previous allocation ended, wrapping around cyclically.
- Performance: Slightly faster than First Fit on average, but tends to break up large free holes located near the end of memory.
4.2.2 Virtual memory management, paging, segmentation
The Concept of Virtual Memory
Early computing systems required an entire program and all its working data to be resident in physical RAM before execution could begin. However:
- Error-handling routines and unusual edge cases are rarely, if ever, executed during typical runs.
- Large arrays, tables, and file buffers are often oversized relative to actual usage.
- Certain modules (e.g., initialization routines) are needed only once at process startup.
Virtual Memory
Virtual Memory is a memory management architecture that separates the user's logical memory view from physical memory. It provides the application programmer with the illusion of an extremely large, uniform, contiguous address space—frequently much larger than the physical RAM installed in the computer.
- Only the actively referenced portions of a process must reside in physical RAM at any given moment; the remainder resides on a high-speed secondary storage device (backing store / paging area).
- When an unmapped address is referenced, the hardware and OS coordinate to load the missing block on demand (demand paging).
Paging
Paging is a non-contiguous memory management scheme that completely eliminates external fragmentation by breaking physical and logical memory into uniform, fixed-size blocks (OS Ch4):
Pages and Frames
- Page Frames (Frames): Physical RAM is divided into fixed-size contiguous blocks called frames. Frame sizes are powers of two, typically between and ( is standard on modern x86/ARM systems).
- Pages: A process's logical address space is divided into blocks of the exact same fixed size called pages.
- Page Table: A data structure maintained by the operating system for each process that maps each logical page number to its corresponding physical frame number in RAM.
Address Translation Hardware in Paging
Every logical address generated by the CPU is divided into two distinct binary components:
- Page Number (): Used as an index into the process's page table to retrieve the physical frame number .
- Page Offset (): The displacement within the page/frame indicating the exact byte accessed.
If the logical address space has size bytes and the page size is bytes:
- The low-order bits specify the page offset ().
- The high-order bits specify the page number .
- The physical address is generated by combining the frame number from the page table with the unchanged page offset :
Logical Address:
+---------------------+-------------------+
| Page Number (p) | Page Offset (d) |
+---------------------+-------------------+
| |
v |
[ Page Table ] |
| Index p: | |
| Frame = f | |
+------------+ |
| |
v v
+---------------------+-------------------+
| Frame Number (f) | Page Offset (d) |
+---------------------+-------------------+
Physical Address:
Page Table Entry (PTE) Control Bits
In addition to the frame number , each entry in a modern page table contains hardware control and status flags (OS Ch4):
| Bit Flag | Name | Function and Operating System Role |
|---|---|---|
| P / V | Present / Valid Bit | Set to if the page currently resides in physical RAM; set to if the page is on disk or invalid (triggers a page fault if accessed). |
| M / D | Modified / Dirty Bit | Set to by hardware whenever the CPU executes a write to any byte in the page. If , the page can be discarded on replacement without writing to disk. |
| R / A | Referenced / Access Bit | Set to by hardware whenever the page is read or written. Periodically cleared by the OS timer interrupt to implement LRU/Clock algorithms. |
| Prot | Protection Bits | Encodes access rights: Read-only (), Read-Write (), or Execute (). Prevents unauthorized writes to code or execution of data. |
| CD | Caching Disabled Bit | Set to for pages mapped to memory-mapped I/O registers so the CPU bypasses L1/L2 caches and interacts directly with the device. |
Translation Lookaside Buffer (TLB) and Effective Access Time (EAT)
In a pure paging scheme where page tables reside in main memory:
- First memory access: The MMU reads the process's page table in RAM (pointed to by the Page Table Base Register — PTBR) to obtain frame number .
- Second memory access: The MMU fetches the actual instruction or data operand from physical address .
- Bottleneck: Every logical memory reference requires two full RAM accesses, slowing program execution by .
To eliminate this memory latency penalty, computer hardware incorporates a specialized, ultra-fast associative cache called the Translation Lookaside Buffer (TLB) (OS Ch4):
Translation Lookaside Buffer (TLB)
A Translation Lookaside Buffer (TLB) is a small, high-speed associative hardware cache integrated into the CPU's MMU. Each entry in the TLB consists of two fields: a key (Page Number ) and a value (Frame Number ).
- When the CPU issues a logical address, the MMU simultaneously checks all TLB entries in parallel (typically within ).
- TLB Hit: If page number matches a TLB key, the corresponding frame number is retrieved immediately, requiring zero extra RAM accesses.
- TLB Miss: If is not found in the TLB, the MMU accesses the page table in main memory, retrieves , and inserts the new mapping into the TLB (replacing an old entry via LRU or FIFO) for rapid subsequent accesses.
Effective Access Time (EAT) Formula
Let:
- (the fraction of memory accesses satisfied directly by the TLB, typically ).
- .
- .
When a TLB lookup occurs simultaneously with or prior to main memory access:
Simplifying:
If the TLB lookup time is negligible or parallelized ():
Multi-Level Paging and Inverted Page Tables
In a modern 32-bit system with () pages:
- The logical address space has .
- If each Page Table Entry (PTE) requires , each process's page table occupies of contiguous physical memory—an unacceptable overhead for hundreds of processes.
Operating systems solve this through two architectures:
- Hierarchical (Multi-Level) Paging: The page table itself is paged into chunks. In a two-level paging system:
- (): Index into the outer page table (page directory).
- (): Index into the inner page table pointed to by .
- (): Offset within the target frame.
- Advantage: Unused regions of the logical address space require no inner page tables, drastically reducing RAM footprint.
- Inverted Page Table: Instead of one page table per process, the OS maintains one global table for all of physical RAM.
- The table has exactly one entry per physical frame in memory.
- Each entry contains .
- Eliminates page table bloat, but requires hashing or inverted searches to map logical addresses to frames.
Segmentation
While paging divides memory into mechanical fixed-size blocks transparent to the programmer, segmentation reflects the logical, modular structure of programs (OS Ch4):
Segmentation
Segmentation is a memory management scheme that supports the user's view of memory. A program is viewed as a collection of variable-length logical units called segments, each corresponding to a meaningful functional component such as the main program, procedures/functions, global variables, call stack, heap, and symbol tables.
Address Translation in Segmentation
A logical address under segmentation is an ordered pair:
- Segment Number (): Used as an index into the process's Segment Table.
- Segment Offset (): The displacement within the segment ().
Each entry in the segment table contains:
- Base: The starting physical memory address where the segment resides in RAM.
- Limit: The length of the segment.
Logical Address: < s , d >
| |
+--------+ |
| |
v v
[ Segment Table ] |
| s: Base, Limit |-+-----> Hardware Check: is d < Limit?
+----------------+ | |
| | NO | YES
| Base v v
| [ TRAP: Addressing ] Physical Address = Base + d
+-----------------------------------> [ Physical RAM Access ]
- Hardware verifies whether . If , the CPU generates a hardware trap (segmentation fault).
- If valid, the physical address is computed as:
| Aspect | Paging | Segmentation |
|---|---|---|
| Programmer Visibility | Completely invisible; managed purely by hardware and OS | Visible; user/compiler partitions program into logical segments |
| Unit Size | Fixed, uniform power-of-two size (e.g., ) across the system | Variable size dynamically determined by function/data size |
| Address Structure | Linear 1-dimensional binary address split by bit mask | 2-dimensional logical address |
| Fragmentation | Internal fragmentation on last page; zero external fragmentation | Zero internal fragmentation; suffers from external fragmentation |
| Protection & Sharing | Difficult to protect/share variable-length procedures cleanly | Natural protection and sharing: an entire code or data segment is shared |
Paged Segmentation (Segmentation with Paging)
To combine the natural logical modularity and sharing of segmentation with the zero-external-fragmentation benefits of paging, modern operating systems implement paged segmentation (OS Ch4):
- Each logical segment is broken down into fixed-size pages.
- The logical address consists of three components: .
- indexes the Segment Table to locate the base address of the Page Table for that specific segment.
- indexes that segment's page table to retrieve the physical Frame Number .
- is the displacement within the page/frame.
- This architecture eliminates external fragmentation (as segments no longer require contiguous physical memory) while preserving segment-level access control and shared code libraries.
4.2.3 Page replacement algorithms (FIFO, LRU, LFU), page fault and hit ratio
Demand Paging and Page Fault Handling
Under demand paging, an operating system loads a page into physical memory only when an instruction actually references it (OS Ch4):
Page Fault
A Page Fault is a hardware interrupt (exception trap) generated by the MMU when a program attempts to access a logical address whose page table entry has its Present/Valid bit set to (), indicating the page is not currently in physical RAM.
Step-by-Step Page Fault Handling Sequence:
1. CPU references memory location -> MMU checks Page Table -> Valid bit is 0 -> Trap: Page Fault Interrupt.
2. OS kernel traps process, saves CPU registers and Program Counter (PC) in Process Control Block (PCB).
3. OS checks internal architectural tables:
- If invalid address reference (out of bounds) -> Terminate process (SIGSEGV).
- If valid reference -> Page resides on backing store (disk).
4. OS finds a free frame in physical RAM from the free-frame list:
- If NO free frame exists, run Page Replacement Algorithm to pick a victim frame.
- If victim frame is dirty (Modified bit M = 1), write victim page back to disk swap space.
- Update victim's PTE: set Present/Valid bit = 0.
5. OS issues disk read I/O to fetch desired page from swap space into allocated free frame.
6. When I/O completes (disk interrupt), OS updates page table:
- Set frame number = allocated frame.
- Set Present/Valid bit = 1.
7. Restore saved CPU registers and restart the faulting instruction from saved PC.
Effective Access Time (EAT) under Demand Paging
Let be the page fault rate (), be the memory access time, and be the average page fault service time (including interrupt latency, disk read/write, and context switches):
Because disk access takes () while RAM access takes , even a page fault rate of () slows system memory access by a factor of nearly .
Page Replacement Algorithms
When a page fault occurs and all physical frames are occupied, the operating system must choose a victim page to evict (OS Ch4):
1. FIFO (First-In, First-Out) Page Replacement
- Mechanism: The OS tracks all pages in memory using a FIFO queue. When a victim is needed, the page at the head of the queue (the page that has resided in memory the longest) is evicted.
- Advantage: Trivial to implement with very low tracking overhead.
- Disadvantage: Heavily accessed pages (such as standard library routines or kernel loops) loaded early are repeatedly evicted and reloaded.
- Belady's Anomaly: Counterintuitively, under FIFO replacement, increasing the number of allocated physical frames can actually increase the number of page faults for certain reference strings (e.g., reference string
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5causes faults with frames, but faults with frames).
2. Optimal Page Replacement (OPT / MIN / Belady's Algorithm)
- Mechanism: Replace the page that will not be referenced for the longest period of time in the future (
OS Ch4). - Advantage: Mathematically proven to produce the absolute lowest possible number of page faults for any given reference string and frame allocation. Never suffers from Belady's Anomaly.
- Limitation: Unrealizable in general-purpose operating systems because it requires perfect, clairvoyant knowledge of future memory references. Used primarily as an optimal benchmark to evaluate realizable algorithms.
3. Least Recently Used (LRU) Page Replacement
- Mechanism: Replaces the page that has not been referenced for the longest period of time in the past (
OS Ch4). It uses past access behavior as an approximation of future behavior. - Property: LRU is a stack algorithm (the set of pages in memory for frames is always a subset of the pages in memory for frames). Consequently, LRU can never suffer from Belady's Anomaly.
- Implementation Challenges:
- Hardware Counter (Logical Clock): Every memory reference increments a CPU clock and copies the counter value into the page table entry. On replacement, the OS searches all frames for the smallest counter. Searching is slow on large frame counts.
- Hardware Stack: A doubly linked list of page numbers. When a page is referenced, it is removed from its current position and pushed to the top. The bottom of the stack is always the LRU victim. Maintaining pointers on every memory access is prohibitively expensive.
4. Hardware Approximations to LRU: The Second-Chance (Clock) Algorithm
Because pure LRU requires prohibitive hardware support, operating systems approximate LRU using page Reference bits ():
- Frames are arranged logically in a circular buffer (a "clock face") with a moving pointer ("clock hand").
- When a page is referenced, hardware sets .
- When a victim is required:
- The hand inspects the page it points to:
- If , this page has not been referenced recently; it is selected as the victim and replaced.
- If , the page is given a "second chance": the OS clears the bit (), advances the hand to the next frame, and repeats.
int clock_hand = 0;
int get_victim_frame(int num_frames, int ref_bit[]) {
while (1) {
if (ref_bit[clock_hand] == 0) {
int victim = clock_hand;
clock_hand = (clock_hand + 1) % num_frames;
return victim; /* Evict this unreferenced frame */
}
/* Give second chance: clear bit and advance */
ref_bit[clock_hand] = 0;
clock_hand = (clock_hand + 1) % num_frames;
}
}5. Counting-Based Page Replacement (LFU and MFU)
Operating systems maintain a software counter tracking the total number of references made to each page (OS Ch4):
- Least Frequently Used (LFU): Replaces the page with the smallest reference count.
- Rationale: Actively used pages maintain high access counts; infrequently accessed pages have low counts.
- Flaw: A page heavily used during process initialization retains a large count forever and is never evicted, even when it is never used again (requires periodic counter aging / right-shifting).
- Most Frequently Used (MFU): Replaces the page with the largest reference count.
- Rationale: Argues that a page with a low reference count was probably just brought into memory and has not yet had an opportunity to execute.
Page Hit and Miss Ratios
For a reference string of length :
4.2.4 Allocation of frames
An operating system executing multiple concurrent processes must determine how many of its finite physical memory frames to allocate to each process (pages="added"):
Minimum Number of Frames
- Every process requires a minimum number of frames determined strictly by the computer's Instruction-Set Architecture (ISA).
- For any instruction to complete, all pages referenced by that instruction simultaneously must be in physical RAM. For example, an indirect addressing instruction (
ADD @A, @B) may require frames concurrently: instruction page, address pointer page, target operand page, address pointer page, target operand page, and destination.
Frame Allocation Strategies
- Equal Allocation: Divides available frames equally among active processes, allocating frames to each.
- Flaw: Severely discriminates against large processes (e.g., a database engine receives the same frames as a text utility), causing massive paging.
- Proportional Allocation: Allocates available frames to each process in direct proportion to that process's virtual memory size . If total virtual memory requested across all processes is , the frame allocation for process from physical frames is:
- Priority Allocation: Allocates frames based on process priority rather than size alone, or allows high-priority processes to select replacement frames from lower-priority processes.
Global vs. Local Replacement
When process encounters a page fault:
- Global Replacement: The process is permitted to select a replacement frame from the entire pool of all frames in memory, potentially stealing a frame currently allocated to another process.
- Advantage: Higher overall system throughput; flexible memory utilization.
- Disadvantage: A process's execution time is non-deterministic, as its page fault rate depends on the paging behavior of external processes; vulnerable to cascading thrashing.
- Local Replacement: The process is restricted to choosing a victim frame only from its own set of allocated frames.
- Advantage: Predictable, consistent per-process performance; isolates thrashing to the misbehaving process.
- Disadvantage: May underutilize memory if a process does not actively need all its allocated frames.
4.2.5 Thrashing
Definition and The Thrashing Collapse
Thrashing
Thrashing is a pathological operating system condition where a system spends significantly more time servicing page faults (swapping pages back and forth between RAM and disk) than executing actual user instructions (OS Ch4).
Thrashing occurs when the sum of the minimum active pages needed by all concurrent processes exceeds the total capacity of physical memory. It triggers a catastrophic system performance collapse:
Vicious Thrashing Feedback Cycle:
1. Processes begin faulting because physical memory is overcommitted.
2. Faulting processes enter the disk I/O wait queue, leaving CPU run queues empty.
3. CPU utilization plunges toward 0%.
4. The OS Long-Term Scheduler observes low CPU utilization and mistakenly concludes
the system is underloaded.
5. To increase CPU utilization, the scheduler introduces NEW processes into memory
(increasing the Degree of Multiprogramming).
6. The newly admitted processes demand even more frames, triggering more page faults.
7. The disk queue saturates, throughput collapses to near zero, and the system freezes.
CPU Utilization vs. Degree of Multiprogramming:
CPU %
100 | Peak Utilization
| /\
| / \ <--- Rapid Thrashing Collapse
| / \
| / \
| / \
0 +-------------+----------+-------->
Optimal Degree of Multiprogramming
The Locality of Reference Principle
Programs do not access their address spaces uniformly; rather, they adhere to the Principle of Locality:
- Temporal Locality: If a memory location is referenced, it is highly likely to be referenced again in the near future (e.g., loops, iteration variables, subroutines, stack pointers).
- Spatial Locality: If a memory location is referenced, nearby memory locations are highly likely to be referenced soon (e.g., sequential instruction execution, array traversals).
As a program executes, it transitions between overlapping localities (sets of pages accessed together). If the system allocates enough frames to hold a process's current locality, the process executes with very few page faults. If allocated frames are fewer than the current locality size, thrashing begins immediately.
Prevention and Resolution: Working-Set Model and Page Fault Frequency
Operating systems employ two primary strategies to prevent and eliminate thrashing:
1. The Working-Set Model (Peter Denning)
- The OS defines a parameter called the working-set window (a fixed number of the most recent page references, e.g., references).
- The Working Set () of process at time is the set of distinct pages referenced in the most recent references.
- The Working Set Size () is the count of pages in .
- The total system frame demand across all active processes is:
- Operating Rule:
- If (total physical frames), all processes can run without thrashing.
- If , physical memory is overcommitted. To prevent thrashing, the OS suspends (swaps out) one or more active processes, freeing their frames to satisfy the working sets of remaining processes. Once remaining processes complete, the suspended processes are swapped back in.
2. Page Fault Frequency (PFF) Strategy
Instead of calculating mathematical working sets, PFF monitors each process's actual page fault frequency:
- The OS establishes an Upper Threshold () and a Lower Threshold ().
- If a process's fault frequency exceeds , the process does not have enough frames to hold its active locality: the OS allocates additional frames to it.
- If a process's fault frequency falls below , the process holds redundant frames: the OS reclaims frames from it.
- If a process exceeds and no free frames exist in the system, the OS suspends the process and swaps it to disk.
Worked Out Examples
Dynamic Memory Partition Selection: First Fit, Best Fit, and Worst Fit
First Fit Allocation: Scan partitions from left to right for the first partition with :
- ():
- (too small).
- Placed in partition.
- Leftover hole: .
- ():
- Next available partitions: (too small), (too small), (too small), Placed in partition.
- Leftover hole: .
- ():
- (too small).
- Placed in partition.
- Leftover hole: .
- ():
- Available free partitions: , (remaining from first), , , .
- No remaining contiguous partition has size .
- cannot be allocated and must wait.
Best Fit Allocation: Scan all free partitions and choose the partition with the smallest size that satisfies :
- ():
- Candidate partitions : , , .
- Smallest adequate: Placed in partition.
- Leftover hole: .
- ():
- Candidate partitions : , .
- Smallest adequate: Placed in partition.
- Leftover hole: .
- ():
- Candidate partitions : (no), , .
- Smallest adequate: Placed in partition.
- Leftover hole: .
- ():
- Candidate partitions : Only the untouched partition remains!
- Placed in partition.
- Leftover hole: .
- All four processes are successfully accommodated!
Worst Fit Allocation: Scan all free partitions and choose the partition with the largest size:
- ():
- Largest available: Placed in partition.
- Leftover hole: .
- ():
- Partitions: , , , , .
- Largest available: Placed in partition.
- Leftover hole: .
- ():
- Partitions: , , , , .
- Largest available: Placed in partition.
- Leftover hole: .
- ():
- Partitions: , , , , .
- None of the remaining partitions can fit .
- cannot be allocated and must wait.
Conclusion:
- Best Fit is the most efficient algorithm here because preserving the largest partition () allows () to be scheduled. Both First Fit and Worst Fit allocate the partition prematurely, leaving waiting.
Paging Address Translation and TLB Effective Access Time (EAT)
Part 1 — Address Bit Structure and Translation:
- Page size . Therefore, the page offset requires .
- Total pages . Therefore, the page number requires .
- Total logical address size .
We decompose the logical address :
In binary representation:
Mapping to Physical Address: From the page table, maps to (). The physical address is formed by concatenating the 4-bit frame number with the 13-bit offset:
Converting to decimal:
Part 2 — Effective Access Time (EAT) Calculation: When a memory reference is issued:
- On a TLB Hit (probability ): Time required .
- On a TLB Miss (probability ): Time required (one access for page table, one for operand).
Applying the EAT formula:
Page Replacement Tracing: FIFO, LRU, and Optimal with Fault & Hit Ratios
FIFO Simulation (3 Frames): Frames start empty:
- Ref
5: Fault - Ref
0: Fault - Ref
5: Hit - Ref
3: Fault (Frames full; oldest is ) - Ref
5: Hit - Ref
2: Fault Replace (oldest) - Ref
5: Fault Replace (oldest) - Ref
0: Fault Replace (oldest) - Ref
1: Fault Replace (oldest) - Ref
0: Hit - Ref
7: Fault Replace (oldest) - Ref
3: Fault Replace (oldest)
Optimal Simulation (3 Frames): Replace the page not referenced for the longest time into the future:
- Ref
5: Fault - Ref
0: Fault - Ref
5: Hit - Ref
3: Fault - Ref
5: Hit - Ref
2: Fault Future references: (next), (at reference 8), (at reference 12). Page is farthest replace - Ref
5: Hit - Ref
0: Hit - Ref
1: Fault Future: (next), (reference 11), (reference 12). Neither nor are referenced again! Replace - Ref
0: Hit - Ref
7: Fault Future: (reference 12). Neither nor nor referenced after 10. Replace - Ref
3: Fault Replace
LRU Simulation (3 Frames): Replace the page that has not been referenced for the longest time in the past:
- Ref
5: Fault - Ref
0: Fault - Ref
5: Hit (Past: ) - Ref
3: Fault (Past: ) - Ref
5: Hit (Past: ) - Ref
2: Fault Least recent is replace - Ref
5: Hit (Past: ) - Ref
0: Fault Least recent is replace - Ref
1: Fault Least recent is replace - Ref
0: Hit (Past: ) - Ref
7: Fault Least recent is replace - Ref
3: Fault Least recent is replace
Summary Comparison:
- Optimal: faults ( hits) — Absolute theoretical minimum.
- LRU: faults ( hits) — Best practical heuristic.
- FIFO: faults ( hits) — Worst performance.
Exercises
Practice Exercises — Memory Management, Paging, Segmentation & Virtual Memory
- Differentiate between compile-time, load-time, and execution-time address binding. Why is execution-time binding mandatory for operating systems that support swapping?
- A process has a base register value of and a limit register value of .
- Specify the exact legal physical memory range for this process.
- For logical addresses and , determine the hardware action and corresponding physical address (if legal).
Part 1 — Address Binding Comparison and Swapping Requirement:
- Compile-Time Binding: The compiler generates absolute physical memory addresses. If the program's starting location in RAM changes, the code must be recompiled.
- Load-Time Binding: The compiler produces relocatable addresses. Binding to physical memory is delayed until the loader loads the program. If the process moves, it must be reloaded from scratch.
- Execution-Time Binding: Address translation is delayed until instruction execution and performed dynamically by MMU hardware (e.g., base/relocation registers).
- Why Mandatory for Swapping: In a system with swapping, a process swapped out to disk is rarely returned to the exact same physical memory location upon swapping back in. Only execution-time binding allows a process to be relocated to an arbitrary physical memory block during execution without recompiling or reloading.
Part 2 — Legal Address Range and Bounds Checking:
- Legal Range Calculation:
The legal physical address range is .
- Evaluating Logical Address :
- Check: (True Legal access).
- Physical Address: .
- Evaluating Logical Address :
- Check: (False Out of bounds!).
- Hardware Action: The hardware MMU traps to the operating system with an addressing error (segmentation violation). Access is denied.
- Compile-time uses absolute addresses; load-time binds relocatable addresses upon loading; execution-time binds dynamically per instruction via MMU hardware. Swapping requires execution-time binding because a process swapped back into RAM typically occupies a different physical location than before.
- Legal physical address range: . Logical address is legal and maps to physical address . Logical address is out of bounds () and triggers an MMU hardware trap.
- Define Internal Fragmentation and External Fragmentation. Explain how coalescing and compaction address external fragmentation.
- A system using dynamic partitioning has four non-contiguous free holes in memory of sizes , , , and .
- Can an incoming process requesting be allocated memory? Identify the condition.
- Describe how compaction resolves this issue and state the remaining free hole size after allocation.
Part 1 — Fragmentation, Coalescing, and Compaction:
- Internal Fragmentation: Memory that is internal to a partition but is not being used. It occurs when fixed-sized blocks (partitions or pages) are allocated that exceed the actual space requested by the process.
- External Fragmentation: Occurs when total free memory is sufficient to satisfy a request, but the available space is split into multiple non-contiguous holes scattered across memory, none of which is individually large enough.
- Coalescing: The OS merges immediately adjacent free holes when a process terminates, creating a single larger free block.
- Compaction: The OS physically relocates all occupied partitions to one end of memory, consolidating all scattered free holes into one contiguous block.
Part 2 — Allocation Analysis and Compaction:
- Total Free Memory Available:
- Because the largest individual hole is , the process cannot be allocated memory despite being free. This is external fragmentation.
- Compaction Resolution: The operating system shifts all active processes toward lower memory addresses. This consolidates the four disjoint holes into a single contiguous hole of size .
- After allocating to the incoming process, the remaining free hole is:
- Internal fragmentation is unused space within an allocated block; external fragmentation is scattered free memory outside partitions that cannot be used contiguously. Coalescing merges adjacent holes upon deallocation; compaction shuffles all active processes to create one large contiguous block.
- The process cannot be allocated initially due to external fragmentation (largest hole is ). Compaction merges all four holes into a single contiguous block; after allocating , the remaining contiguous hole is .
- Compare Paging and Segmentation across: programmer visibility, unit sizing, address structure, fragmentation types, and protection/sharing.
- A 32-bit computer architecture uses a two-level hierarchical paging scheme with a page size of . The page table is divided such that the outer page table and inner page tables each fit within a single frame.
- Determine the number of bits allocated to the outer page table index (), the inner page table index (), and the page offset ().
- How many entries does each outer and inner page table contain?
Part 1 — Comprehensive Paging vs. Segmentation Comparison:
- Programmer Visibility: Paging is transparent to the user/programmer; segmentation reflects the user's logical view of programs (functions, objects, stacks).
- Unit Sizing: Pages have fixed hardware-defined sizes (powers of two); segments have dynamically variable lengths determined by code/data size.
- Address Structure: Paging uses a linear 1D virtual address partitioned by hardware bit masks (); segmentation uses an explicit 2D tuple .
- Fragmentation: Paging suffers from internal fragmentation on the last page and zero external fragmentation; segmentation exhibits zero internal fragmentation but suffers from external fragmentation.
- Protection & Sharing: Difficult in paging because code and data may share pages; natural in segmentation because entire functions or data structures reside in discrete segments.
Part 2 — Two-Level Paging Bit Breakdown:
- Page Offset ():
- Virtual Address Space: . Total bits for page numbers: .
- Inner and Outer Page Tables: Each page table entry requires . A single frame holds:
Therefore:
- Inner page table index () requires ( entries).
- Outer page directory index () requires the remaining ( entries).
- Paging is invisible, fixed-size, 1D, has internal fragmentation, and provides mechanical protection; segmentation is programmer-visible, variable-sized, 2D, has external fragmentation, and supports natural logical sharing and protection.
- Bit allocation: , , . Both the outer page directory and each inner page table contain entries ().
A virtual memory system has a main memory access time of and an average page fault service time of ().
- Calculate the Effective Access Time (EAT) if one page fault occurs for every memory accesses (). By what factor does performance degrade?
- What is the maximum tolerable page fault rate if the system requires that EAT does not exceed (allowing at most a slowdown)?
Part 1 — EAT with (): The Effective Access Time under demand paging is:
Substituting , , and :
Performance degradation factor:
A page fault rate of only slows down memory access by over times!
Part 2 — Maximum Tolerable Page Fault Rate for :
To keep degradation under , at most out of every memory accesses may result in a page fault ().
- (), representing a -fold slowdown relative to normal RAM access.
- Maximum allowable page fault rate is (at most fault per memory accesses).
- State Belady's Anomaly. Which page replacement algorithms can exhibit it, and why does LRU never suffer from it?
- A process references pages in the following sequence (
OS Ch4):
Assuming empty frames, calculate the total page faults for:
- FIFO
- Optimal (OPT)
- LRU
- LFU
Part 1 — Belady's Anomaly and Stack Algorithms:
- Belady's Anomaly: The phenomenon wherein increasing the number of physical page frames allocated to a process results in an increase in the total number of page faults for a given reference string.
- FIFO exhibits Belady's anomaly because it evicts the oldest page regardless of recency or frequency of access.
- Why LRU is Immune: LRU belongs to the class of stack algorithms. A page replacement algorithm is a stack algorithm if the set of pages in memory for frames is always a strict subset of the pages in memory for frames (). Because adding frames can never cause a page that was in memory to be missing, stack algorithms can never exhibit Belady's anomaly.
Part 2 — Tracing Page Faults with 4 Frames ( references):
- FIFO:
- Initial 4 refs:
1, 2, 3, 4faults. - Refs
2, 1: Both hits. - Refs
5, 6: Faults (replace ) frames: . - Refs
2, 1: Faults (replace ) frames: . - Ref
2: Hit. - Ref
3: Fault (replace ) . - Ref
7: Fault (replace ) . - Ref
6: Fault (replace ) . - Ref
3: Hit. - Ref
2: Fault (replace ) . - Ref
1: Fault (replace ) . - Ref
2: Hit. - Ref
3: Fault (replace ) . - Ref
6: Hit.
- Initial 4 refs:
- Optimal (OPT):
- Tracing future references: evicts the page unreferenced for the longest time ahead.
- LRU (Least Recently Used):
- Tracks recency of past access:
- LFU (Least Frequently Used):
- Evicts page with lowest reference count:
- Belady's Anomaly is the counterintuitive increase in page faults when frames are added; FIFO exhibits it. LRU is immune because it is a stack algorithm where the set of pages resident with frames is always a subset of those with frames.
- Total page faults for frames across the references:
- FIFO: faults ( hits, fault rate)
- Optimal: faults ( hits, fault rate)
- LRU: faults ( hits, fault rate)
- LFU: faults ( hits, fault rate)
- Explain the cause-and-effect feedback loop of Thrashing.
- A system has allocatable physical frames and three concurrent processes: of size , of size , and of size .
- Calculate the frame allocation for each process using Proportional Allocation.
- Explain how the Working-Set Model and Page Fault Frequency (PFF) prevent thrashing. If working set sizes for three processes are , , and , what is the minimum number of frames required to avoid thrashing?
Part 1 — The Thrashing Feedback Loop: When memory is overcommitted:
- Processes lack sufficient frames for their active localities, causing frequent page faults.
- As processes queue for disk I/O, the CPU becomes idle, causing CPU utilization to plummet.
- The operating system's CPU scheduler misinterprets low CPU utilization as system underload and admits more processes (increasing the degree of multiprogramming).
- The new processes request more frames, worsening page fault frequency and saturating the disk queue.
- Paging activity overwhelms instruction execution, causing total system throughput to collapse.
Part 2 — Proportional Frame Allocation: Total virtual size requested:
Total available frames . The proportional frame allocation formula is :
- Process :
- Process :
- Process :
Total allocated frames: frames.
Part 3 — Working-Set Model and PFF:
- Working-Set Model: Tracks the set of unique pages referenced in the most recent memory accesses (). Total frame demand is . If , the OS prevents thrashing by suspending (swapping out) one process until .
- Minimum Frames Needed:
The system requires at least physical frames to prevent thrashing.
- Page Fault Frequency (PFF): Sets upper and lower fault-rate thresholds (). If a process faults faster than , the OS allocates it more frames; if below , frames are deallocated. If fault rate remains high and memory is full, the process is suspended.
- Thrashing occurs when high page fault rates cause CPU utilization to drop, prompting the OS scheduler to admit more processes, which intensifies memory pressure and collapses throughput.
- Under proportional allocation: , , and (total ).
- The working-set model dynamically allocates frames based on active page localities over window ; PFF adjusts frames using high/low fault thresholds. With working set sizes , the minimum frames required to prevent thrashing is .