PadhaikoAll subjects

Memory Management

Operating System (ENCT 254)

Open in the Padhaiko app

4.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):

  1. Tracking Memory State: Monitors every byte of physical memory to determine whether it is currently allocated to an active process or free for allocation.
  2. Dynamic Memory Allocation & Deallocation: Allocates physical memory blocks to incoming processes, reclaims memory upon process termination, and manages runtime heap expansion.
  3. Protection & Isolation: Ensures that each process accesses only its designated legal address range, protecting user processes from one another and safeguarding the OS kernel.
  4. 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:

Definition

Logical and Physical Addresses

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:

  1. 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.
  2. 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.
  3. 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.
AspectLogical AddressPhysical Address
OriginGenerated by the CPU during instruction fetch/executionPresent on the address bus to physical RAM chips
VisibilityDirectly visible to user programs and compilersHidden from user programs; managed exclusively by the MMU and kernel
Range to to
Binding TimeDetermined at compile/assembly timeDetermined 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):

Definition

Base and Limit Registers

For any memory reference with logical address :

  1. 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.
  2. If , the relocation unit adds the base address to compute the physical memory address:
  1. 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).

Definition

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.

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)

2. Fixed-Size Partitioning (Multiprogramming with Fixed Tasks — MFT)

Memory is divided into static partitions at system configuration time (OS Ch4):

Fixed Partition AdvantagesFixed Partition Disadvantages
Extremely simple to implement with minimal CPU overheadLimited Multiprogramming: Number of concurrent active processes is strictly bounded by partition count
Low operating system tracking complexityInternal Fragmentation: Unused space inside an allocated partition is wasted
Fast dispatchingProcess 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):

AspectInternal FragmentationExternal Fragmentation
DefinitionUnused memory that resides inside an allocated partition or page frameUnused memory that resides outside allocated partitions, between active blocks
OccurrenceFixed-size partitioning and paging (last page/partition larger than needed)Dynamic (variable-length) partitioning and pure segmentation
CauseMemory is allocated in discrete fixed-size blocks exceeding process requirementsFrequent allocation and deallocation leaving scattered holes of varying sizes
Primary RemedyAllocate smaller partition/page sizesCompaction (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):

  1. 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.
  2. 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:

Techniques for Managing Free Memory Space
TechniqueStructure & OrganizationAdvantagesDisadvantages
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 ListsDoubly 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 SystemMemory 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):

Definition

First Fit, Best Fit, Worst Fit, and Next Fit

  1. 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.
  2. 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.
  3. 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.
  4. 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:

Definition

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.

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):

Definition

Pages and Frames

Address Translation Hardware in Paging

Every logical address generated by the CPU is divided into two distinct binary components:

  1. Page Number (): Used as an index into the process's page table to retrieve the physical frame number .
  2. 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:

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):

Control and Status Bits in a Page Table Entry (PTE)
Bit FlagNameFunction and Operating System Role
P / VPresent / Valid BitSet 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 / DModified / Dirty BitSet 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 / AReferenced / Access BitSet to by hardware whenever the page is read or written. Periodically cleared by the OS timer interrupt to implement LRU/Clock algorithms.
ProtProtection BitsEncodes access rights: Read-only (), Read-Write (), or Execute (). Prevents unauthorized writes to code or execution of data.
CDCaching Disabled BitSet 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:

To eliminate this memory latency penalty, computer hardware incorporates a specialized, ultra-fast associative cache called the Translation Lookaside Buffer (TLB) (OS Ch4):

Definition

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 ).

Effective Access Time (EAT) Formula

Let:

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:

Operating systems solve this through two architectures:

  1. Hierarchical (Multi-Level) Paging: The page table itself is paged into chunks. In a two-level paging system:
  1. 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):

Definition

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:

Each entry in the segment table contains:

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 ]
  1. Hardware verifies whether . If , the CPU generates a hardware trap (segmentation fault).
  2. If valid, the physical address is computed as:
AspectPagingSegmentation
Programmer VisibilityCompletely invisible; managed purely by hardware and OSVisible; user/compiler partitions program into logical segments
Unit SizeFixed, uniform power-of-two size (e.g., ) across the systemVariable size dynamically determined by function/data size
Address StructureLinear 1-dimensional binary address split by bit mask2-dimensional logical address
FragmentationInternal fragmentation on last page; zero external fragmentationZero internal fragmentation; suffers from external fragmentation
Protection & SharingDifficult to protect/share variable-length procedures cleanlyNatural 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):


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):

Definition

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

2. Optimal Page Replacement (OPT / MIN / Belady's Algorithm)

3. Least Recently Used (LRU) Page Replacement

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 ():

Second-Chance (Clock) Page Replacement AlgorithmC
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):

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

Frame Allocation Strategies

  1. 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.
  2. 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:
  1. 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:


4.2.5 Thrashing

Definition and The Thrashing Collapse

Definition

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:

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)

2. Page Fault Frequency (PFF) Strategy

Instead of calculating mathematical working sets, PFF monitors each process's actual page fault frequency:


Worked Out Examples

Example

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 :

  1. ():
    • (too small).
    • Placed in partition.
    • Leftover hole: .
  2. ():
    • Next available partitions: (too small), (too small), (too small), Placed in partition.
    • Leftover hole: .
  3. ():
    • (too small).
    • Placed in partition.
    • Leftover hole: .
  4. ():
    • 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 :

  1. ():
    • Candidate partitions : , , .
    • Smallest adequate: Placed in partition.
    • Leftover hole: .
  2. ():
    • Candidate partitions : , .
    • Smallest adequate: Placed in partition.
    • Leftover hole: .
  3. ():
    • Candidate partitions : (no), , .
    • Smallest adequate: Placed in partition.
    • Leftover hole: .
  4. ():
    • 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:

  1. ():
    • Largest available: Placed in partition.
    • Leftover hole: .
  2. ():
    • Partitions: , , , , .
    • Largest available: Placed in partition.
    • Leftover hole: .
  3. ():
    • Partitions: , , , , .
    • Largest available: Placed in partition.
    • Leftover hole: .
  4. ():
    • 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.
Example

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:

Example

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

Question 1
  1. Differentiate between compile-time, load-time, and execution-time address binding. Why is execution-time binding mandatory for operating systems that support swapping?
  2. 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.
Answer:
  1. 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.
  2. 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.
Question 2
  1. Define Internal Fragmentation and External Fragmentation. Explain how coalescing and compaction address external fragmentation.
  2. 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:
Answer:
  1. 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.
  2. 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 .
Question 3
  1. Compare Paging and Segmentation across: programmer visibility, unit sizing, address structure, fragmentation types, and protection/sharing.
  2. 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).
Answer:
  1. 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.
  2. Bit allocation: , , . Both the outer page directory and each inner page table contain entries ().
Question 4

A virtual memory system has a main memory access time of and an average page fault service time of ().

  1. Calculate the Effective Access Time (EAT) if one page fault occurs for every memory accesses (). By what factor does performance degrade?
  2. 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 ().

Answer:
  1. (), representing a -fold slowdown relative to normal RAM access.
  2. Maximum allowable page fault rate is (at most fault per memory accesses).
Question 5
  1. State Belady's Anomaly. Which page replacement algorithms can exhibit it, and why does LRU never suffer from it?
  2. A process references pages in the following sequence (OS Ch4):

Assuming empty frames, calculate the total page faults for:

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, 4 faults.
    • 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.
  • 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:
Answer:
  1. 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.
  2. 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)
Question 6
  1. Explain the cause-and-effect feedback loop of Thrashing.
  2. 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.
  3. 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:

  1. Processes lack sufficient frames for their active localities, causing frequent page faults.
  2. As processes queue for disk I/O, the CPU becomes idle, causing CPU utilization to plummet.
  3. The operating system's CPU scheduler misinterprets low CPU utilization as system underload and admits more processes (increasing the degree of multiprogramming).
  4. The new processes request more frames, worsening page fault frequency and saturating the disk queue.
  5. 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.
Answer:
  1. 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.
  2. Under proportional allocation: , , and (total ).
  3. 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 .

Past exam questions for Operating System

← I/O managementFile Systems →