Chapter 1: Computer System Architecture & Foundations

I. Core Characteristics of Operating Systems

An Operating System (OS) is defined by four foundational intertwined attributes: Concurrency, Sharing, Virtualization, and Asynchrony.

┌─────────────────┐       ┌───────────────┐
│   Concurrency   │ ◄───► │    Sharing    │
└────────┬────────┘       └───────┬───────┘
│                        │
▼                        ▼
┌─────────────────┐       ┌───────────────┐
│ Virtualization  │       │  Asynchrony   │
└─────────────────┘       └───────────────┘

Concurrency: The ability of multiple events or programs to execute over overlapping time intervals on a single computer system. (Distinct from Parallelism, which requires separate physical CPU cores running instructions simultaneously).
Sharing (Resource Sharing): The system design enabling multiple concurrent processes to utilize hardware resources (e.g., memory, disk space, CPU time).
- Mutual Exclusion Sharing: Resources (e.g., printers) can only be safely modified by one process at a given time.
- Simultaneous Sharing: Resources (e.g., read-only disk sectors) can be accessed by multiple processes concurrently.
Virtualization: The physical system resources are abstracted into logical, isolated slices. Physical memory is virtualized into Virtual Memory; a single physical processor is virtualized into multiple logical processors.
Asynchrony: In a concurrent multi-programmed environment, processes proceed along uncoordinated pathways, executing at unpredictable, intermittent rates.

II. OS Interfaces and System Configurations

1. User Control Interfaces

Online Command Interface (Interactive): The user types an individual command at a terminal window (e.g., a CLI prompt), and the operating system processes it immediately before waiting for the next user interaction.
Offline Command Interface (Batch Processing): The user compiles a structural sequence of execution instructions (e.g., a batch script). The system ingests the script file and executes the commands sequentially without real-time human intervention.

2. Programmatic Interface: System Calls

The programmatic interface consists of a dedicated library of System Calls (sometimes referred to as Generalized Instructions). User programs invoke system calls to request low-level hardware or kernel resources securely.

3. The Extended Machine Concept

Bare Machine (Bare Metal): Computer hardware completely stripped of any software layers, communicating strictly through raw binary instruction codes.
Extended Machine (Virtual Machine): A hardware core encapsulated within operating system layers. It abstracts away structural register logic, presenting application developers with high-level clean system functional interfaces.

III. Historical Evolution of Operating Systems

[Manual Input] ──> [Single-Program Batch] ──> [Multi-Program Batch] ──> [Time-Sharing] ──> [Real-Time]

Manual Processing Stage: Early computers lacked software frameworks. Users monopolized the machine sequentially via physical plugboards or punched paper tapes. The fast CPU stood idle while humans adjusted physical equipment, creating a significant speed bottleneck.
Single-Program Batch Operating System: A resident monitor program loaded batches of jobs sequentially into memory. It automated execution changes to minimize human setup delays, but only one job occupied memory at a time, leading to poor CPU efficiency when waiting for slow I/O sweeps.
Multi-Program Batch Operating System: Multiple independent application images are loaded into main memory simultaneously. When the active job stalls on an I/O request, the CPU instantly switches to execute an alternate job image.
- Features: Exceptional resource utilization, high throughput.
- Drawbacks: Extremely long turn-around delays, no live user interaction.
Time-Sharing Operating System: The processor divides its execution timeline into tiny millisecond slices (Time Slots/Time Quanta), cycling through all active memory jobs in a round-robin loop.
- Features: Simultaneous multi-user configurations, real-time interactivity, independent isolated sessions, rapid response profiles.
Real-Time Operating System (RTOS): Guarantees task execution within hard, predictable timing constraints. It prioritizes deterministic reliability over total system throughput.

IV. Core Architecture and Exception Handling Mechanism

1. CPU Execution States (Privilege Modes)

To guarantee security, hardware processors split execution environments into distinct privilege modes:

User Mode (Problem State / Non-Privileged Mode): The sandbox state where normal application programs run. Access to unsafe machine instructions or direct physical I/O ports is blocked.
Kernel Mode (Supervisor State / Privileged Mode): The highest access tier where the core operating system routines run. The CPU has unrestricted access to all registers, memory addresses, and privileged instructions (e.g., disabling physical interrupts).

2. Interrupts vs. Exceptions

An interrupt or exception halts normal program flow, forcing the CPU to switch from User Mode to Kernel Mode to run an OS handler.

          ┌───────────────────────────────┐
          │ CPU Interrupt/Exception Event │
          └───────────────┬───────────────┘
                          │
 ┌────────────────────────┴────────────────────────┐
 ▼                                                 ▼

┌──────────────────┐                              ┌──────────────────┐
│  True Interrupt  │                              │    Exception     │
│  (Asynchronous)  │                              │   (Synchronous)  │
└────────┬─────────┘                              └────────┬─────────┘
│                                                 │
├─► Physical I/O Device Signals                   ├─► System Call (Trap)
└─► Timer Quanta Expiration                       ├─► Page Fault (Memory Access)
└─► Divide-by-Zero (Arithmetic Error)

Interrupts (Asynchronous / External Interrupts): Events triggered by hardware external to the current CPU instruction stream. They are completely independent of program execution.
- Examples: Hard disk controller signaling an I/O read completion, network card packet arrival, or programmable interval timer timeouts.
Exceptions (Synchronous / Internal Interrupts / Faults / Traps): Processor-internal disruptions directly triggered by the execution of the active instruction itself.
- Examples: Dividing a number by zero, encountering an illegal opcode, virtual memory page faults, address bounds violations, or executing a explicit software trap instruction (INT, SYSCALL).

Hardware Interruption Handling Flow:

When an interruption signal hits the hardware line, the system executes a deterministic sequence of protection protocols:

[Disable Interrupts] ──> [Save Program Counter] ──> [Vector Table Lookup] ──> [Save CPU Registers] ──> [Run ISR] ──> [Restore Registers] ──> [IRET]

Hardware State Save: The processor hardware automatically completes the atomic phase:
- Disable Interrupts: The CPU sets its internal status flags to block new incoming interrupt signals from causing race conditions.
- Save Breakpoint (Program Counter / Context): The active Program Counter (PC) and Processor Status Word (PSW) are pushed onto the kernel system stack.
- Vector Table Lookup: The CPU queries the interrupt vector table using the event identifier code to locate the starting address of the corresponding Interrupt Service Routine (ISR).
Software Service Phase: Control transitions to the OS kernel:
- Save Register Environment: The ISR pushes all general-purpose CPU registers onto the stack to preserve the state of the interrupted program.
- Enable Interrupts (Optional): Changes mask bits to allow higher-priority interrupts to preempt the current routine (nested interrupts).
- Run Main ISR Logic: The system executes the specific device handler code.
Restoration and Return:
- Disable Interrupts: Prepares the system for state restoration.
- Restore Register Environment: Pops the cached register states back into the physical CPU cores.
- Enable Interrupts & Return: Executes the atomic IRET (Interrupt Return) instruction, which simultaneously pops the saved PC and PSW, switching the CPU state back to User Mode.

3. System Call Execution Architecture

A system call acts as a secure doorway, allowing a user-space application to request services from the privileged kernel.

[User App Code] ──► [Call Wrapper Function] ──► [Execute TRAP Instruction] ──► [Kernel Handler Execution] ──► [Return to User Mode]

The user program invokes an API wrapper function provided by the standard system library (e.g., read()).
The library routine places the system call identifier code into a designated register and executes an explicit software Trap instruction (e.g., sysenter or svc).
The trap instruction automatically flips the CPU from User Mode to Kernel Mode, saves the execution context, and transfers control to the centralized system call handler inside the kernel.
The kernel validates the parameters, executes the requested service, writes return values to user memory, and drops execution privilege back down to User Mode, returning control to the application.

4. Kernel Architecture Models

Monolithic Kernel (Macrokernel): All foundational operating system modules (scheduler, file system, virtual memory manager, device drivers) run inside a single, unified kernel address space.
- Pros: High execution performance; components communicate via fast, direct internal function calls.
- Cons: Poor modular isolation; a bug inside a device driver can trigger a fatal crash of the entire operating system kernel.
Microkernel Architecture: Minimizes kernel responsibilities to the absolute essentials: low-level address space management, basic thread scheduling, and Inter-Process Communication (IPC). Non-essential services (file systems, network stacks, drivers) run as decoupled servers in User Space.
- Pros: High reliability, secure fault containment, easy to extend.
- Cons: Significant performance overhead due to frequent mode switches and IPC message passing across boundary lines.

Chapter 2: Process & Thread Management

I. Processes: State Management and Inter-Process Communication

A Process is a dynamic instance of a running program. It is composed of three structural parts: the Program Code Segment, the Data Segment, and the Process Control Block (PCB). The PCB serves as the definitive structural record used by the OS to track process states.

1. Lifecycle Process State Transitions

Ready State: The process has acquired all necessary memory and execution resources and is waiting in a queue for the scheduler to allocate CPU time.
Running State: The process occupies a physical CPU core and is actively executing instruction streams.
Blocked State (Waiting State): The process cannot execute because it is waiting for an external event (e.g., disk I/O read completion, network packet arrival, or semaphore signal).
Creation State: The OS is instantiating the PCB and allocating initial memory resources, but the process is not yet eligible to run.
Termination State: The process has completed execution or crashed. Its resources are reclaimed by the system while its parent reads its final exit status.

2. Inter-Process Communication (IPC) Mechanisms

Shared Memory Systems: Multiple processes map a common physical memory segment into their respective virtual address spaces. Communication occurs at memory speeds without kernel intervention, though applications must use synchronization primitives (e.g., semaphores) to prevent data corruption.
Message Passing Systems: Processes transfer structured data blocks (Messages) using explicit OS primitives: send() and receive().
- Direct Communication: The sender must explicitly name the target recipient process.
- Indirect Communication: Messages are routed through intermediary system objects called mailboxes or message queues.
Pipe Communication: An isolated, unidirectional data channel (implemented as a memory buffer backed by a pseudo-file) connecting the standard output of one process directly to the standard input of another. Pipes operate on a strict First-In, First-Out (FIFO) byte-stream basis.
- Standard pipes are half-duplex; full-duplex communication requires two independent pipes.

II. Thread Architectures and Concurrency Control

1. Process vs. Thread Concepts

Processes were historically introduced to facilitate concurrent program execution. However, creating, destroying, and switching processes incurs significant CPU performance overhead due to address space modifications.

To reduce these costs, modern operating systems use Threads. A process acts as the base unit for resource allocation, while a thread acts as the base unit for CPU scheduling. A single process can contain multiple concurrent threads that share its memory address space and file handles.

┌──────────────────────────────────────────────────────────┐
│                      PROCESS SPACE                       │
│  ┌──────────────────────┐      ┌──────────────────────┐  │
│  │     Code Segment     │      │     Data Segment     │  │
│  └──────────────────────┘      └──────────────────────┘  │
│  ┌──────────────────────┐                                │
│  │   Allocated Files    │                                │
│  └──────────────────────┘                                │
│  ┌──────────────────┐          ┌──────────────────┐      │
│  │     THREAD 1     │          │     THREAD 2     │      │
│  │ ┌──────────────┐ │          │ ┌──────────────┐ │      │
│  │ │Regs  │ PC    │ │          │ │Regs  │ PC    │ │      │
│  │ ├──────────────┤ │          │ ├──────────────┤ │      │
│  │ │ Stack Space  │ │          │ │ Stack Space  │ │      │
│  │ └──────────────┘ │          │ └──────────────┘ │      │
│  └──────────────────┘          └──────────────────┘      │
└──────────────────────────────────────────────────────────┘

2. Thread Implementation Models

User-Level Threads (ULT): Thread management tasks (creation, switching, synchronization) are performed entirely within user space via a runtime library. The OS kernel is unaware of individual threads and schedules the process as a single unit.
- Pros: Fast context switches that do not require entering kernel mode.
- Cons: If a single thread blocks on a system call, the kernel blocks the entire parent process, stalling all other threads in that process.
Kernel-Level Threads (KLT): Thread management tasks are performed directly by the OS kernel. The kernel maintains a thread context record for every execution thread in the system.
- Pros: If a thread blocks, the kernel can independently schedule other threads within the same process.
- Cons: Thread switches require transitioning into kernel mode, which introduces performance overhead.

III. Processor Scheduling Architectures

1. Scheduling Tiers

High-Level Scheduling (Job Scheduler): Selects batch jobs from a backup queue on disk and loads them into main memory, creating the initial process profiles.
Medium-Level Scheduling (Swapping Scheduler): Temporarily removes idle or blocked processes from main memory to disk swap space when memory is low, and restores them when memory becomes available.
Low-Level Scheduling (CPU Scheduler / Dispatcher): Selects an active process from the ready queue and allocates a physical CPU core to it.

2. Core Operational Metrics

To analyze scheduling algorithms, the system computes standard operational metrics:

\[\text{Turnaround Time} = \text{Task Completion Time} - \text{Task Submission Time}\] \[\text{Weighted Turnaround Time} = \frac{\text{Turnaround Time}}{\text{Actual Execution Time}}\] \[\text{Average Turnaround Time} = \frac{\sum_{i=1}^{n} \text{Turnaround Time}_i}{n}\]

3. CPU Scheduling Algorithms

Algorithm	Preemption Style	Primary Metric Basis	Starvation Risk	Common Target System
FCFS (First-Come, First-Served)	Non-preemptive	Arrival sequence time order	No	Early Batch Systems
SJF / SPF (Shortest Job First)	Non-preemptive	Anticipated execution burst length	Yes (Long tasks)	Batch Processing
SRTN (Shortest Remaining Time)	Preemptive	Shortest remaining execution time	Yes	Advanced Batch Systems
HRRN (Highest Response Ratio)	Non-preemptive	Dynamic priority computed dynamically	No	Balanced Systems
Priority Scheduling	Both Styles	Configured priority number token	Yes (Low priority)	Real-Time Systems
RR (Round-Robin)	Preemptive	Fixed execution time quantum slice	No	Time-Sharing Systems
Feedback (Multilevel Feedback Queue)	Preemptive	Dynamic behavior across queues	Yes (Compute heavy)	Modern Desktop OS

HRRN Priority Metric Calculation: $\text{Response Ratio } R_p = \frac{\text{Wait Time} + \text{Estimated Service Burst Time}}{\text{Estimated Service Burst Time}}$
Multilevel Feedback Queue Workflow: The system maintains multiple sequential ready queues with decreasing priority levels. New processes enter Queue 1 with a short time quantum. If a process does not complete within its allocated quantum, it is demoted to the tail of Queue 2, which has a longer time quantum. Higher-priority queues must be completely empty before tasks in lower-priority queues can execute.

IV. Process Synchronization and Mutual Exclusion Primitives

1. Critical Sections

A Critical Section is a segment of code that accesses shared, mutable resources (such as global variables or hardware devices). To prevent race conditions, only one process can execute within its critical section at any given moment.

A valid mutual exclusion implementation must satisfy four core principles:

Progress (Free Choice): If no process is in its critical section, any requesting process should be allowed to enter without arbitrary delay.
Bounded Waiting: A process requesting entry must eventually be granted access within a bounded number of turns, preventing infinite starvation.
Mutual Exclusion (Busy Waiting Isolation): Only one process can execute within the critical section at a time.
Bounded CPU Utilization (Yield Control): Waiting processes should yield execution resources rather than consuming CPU cycles in infinite spin loops.

2. Software & Hardware Synchronization Solutions

Software-Based Protocols:

Turn-Based Isolation (Strict Alternation): Forces two processes to alternate access perfectly. This violates the Progress principle if one process executes much less frequently than the other.
Flag-Based Checks: Processes use state flags to signal intent before entering. Checking and setting flags are separate operations, which can allow two processes to enter the critical section simultaneously, or lead to mutual deadlock.
Peterson’s Algorithm: Combines intention flags with a turn-arbitration variable to provide mutual exclusion for two processes. It satisfies the first three validation criteria but relies on busy-waiting, which violates the Yield Control principle.

Hardware-Based Support:

Interrupt Mask Primitives: Disables physical interrupts on the CPU core right before entering a critical section, preventing preemption.
- Drawbacks: Ineffective on modern symmetric multi-core processors, as disabling interrupts on one core does not prevent a thread on another core from accessing shared memory.
Atomic Hardware Instructions (TSL / CAS): Modern processors provide atomic hardware instructions, such as Test-and-Set-Lock (TSL) or Compare-and-Swap (CAS). These instructions read and modify a memory word in a single, un-interruptible bus cycle, enabling secure lock implementations.

3. Semaphores: Low-Level Synchronization Primitives

Counting Semaphores (Integer Semaphores)

An integer variable $S$ tracks resource availability. Access is managed through two atomic functions: wait(S) (P operation) and signal(S) (V operation). This simple model can cause busy-waiting if the resource count drops below zero.

void wait(int S) {
    while (S <= 0); // Busy waiting loop
    S--;
}
void signal(int S) {
    S++;
}

Record-Type Semaphores

To eliminate busy-waiting, record-type semaphores combine a counting variable with a FIFO wait queue. When a resource is unavailable, the process blocks and yields the CPU.

typedef struct {
    int value;           // Available resource count
    struct process *L;   // FIFO link queue for blocked processes
} semaphore;

void wait(semaphore S) {
    S.value--;
    if (S.value < 0) {
        add_this_process_to(S.L);
        block(S.L);     // Yields CPU control immediately
    }
}

void signal(semaphore S) {
    S.value++;
    if (S.value <= 0) {
        process P = remove_process_from(S.L);
        wakeup(P);      // Moves process back to ready queue
    }
}

4. Monitors: High-Level Synchronization Abstractions

Semaphores require developers to place P and V operations carefully throughout their code. A single misplaced function call can cause deadlocks or race conditions that are difficult to debug.

To address this, Monitors provide an object-oriented synchronization abstraction. A monitor encapsulates shared data structures, private variables, and a set of access methods. The compiler automatically guarantees that only one thread can execute a method inside the monitor at any given time, ensuring mutual exclusion.

5. Classic Concurrency Challenges

Challenge A: The Bounded-Buffer (Producer-Consumer) Problem

A shared buffer holds up to $n$ data items. Producers add items to the buffer, and consumers remove them. Synchronization must ensure that producers stop when the buffer is full, and consumers stop when the buffer is empty.

       Producer               Shared Buffer (Size n)               Consumer
   ┌──────────────┐          ┌───┬───┬───┬───┬───┐          ┌──────────────┐
   │ Produce Item ├─────────►│   │   │   │   │   ├─────────►│ Consume Item │
   └──────────────┘          └───┴───┴───┴───┴───┘          └──────────────┘

semaphore mutex = 1;  // Ensures exclusive access to the buffer
semaphore empty = n;  // Tracks available slots in the buffer
semaphore full = 0;   // Tracks populated slots in the buffer

void Producer() {
    while(true) {
        item data = produce_item();
        wait(empty);   // Decrement empty slots; block if full
        wait(mutex);   // Enter critical section
        append_to_buffer(data);
        signal(mutex);  // Leave critical section
        signal(full);   // Increment full slots
    }
}

void Consumer() {
    while(true) {
        wait(full);    // Decrement full slots; block if empty
        wait(mutex);   // Enter critical section
        item data = extract_from_buffer();
        signal(mutex);  // Leave critical section
        signal(empty);  // Increment empty slots
        consume_item(data);
    }
}

Challenge B: The Readers-Writers Problem

Multiple threads need to access a shared dataset. Multiple readers can safely access the data at the same time, but only one writer can modify it exclusively.

int read_count = 0;    // Tracks the active readers
semaphore mutex = 1;   // Protects modification of read_count
semaphore rw = 1;      // Ensures mutual exclusion for writers

void Reader() {
    while(true) {
        wait(mutex);
        if (read_count == 0) wait(rw); // First reader locks the dataset from writers
        read_count++;
        signal(mutex);
        
        read_data_file();
        
        wait(mutex);
        read_count--;
        if (read_count == 0) signal(rw); // Last reader releases the lock for writers
        signal(mutex);
    }
}

void Writer() {
    while(true) {
        wait(rw);      // Request exclusive write access
        write_data_file();
        signal(rw);     // Release write access
    }
}

V. Deadlock Theory and Resource Contention Strategies

A Deadlock occurs when two or more processes are permanently blocked because each is waiting for a resource that is held by another process in the group.

┌───────────┐  Holds Resource A   ┌───────────┐
│ Process 1 ├────────────────────►│ Resource A │
└─────▲─────┘                     └─────┬─────┘
      │                                 │
  Requests                              │
 Resource B                          Held By
      │                                 │
┌─────┴─────┐                     ┌─────▼─────┐
│ Resource B│◄────────────────────┤ Process 2 │
└───────────┘  Requests Resource A└───────────┘

Four conditions must hold simultaneously for a deadlock to occur:

Mutual Exclusion: At least one resource must be held in a non-shareable mode.
Hold and Wait: A process must hold at least one resource while waiting to acquire additional resources held by others.
No Preemption: Resources cannot be forcibly taken from a process; they must be released voluntarily.
Circular Wait: A closed chain of processes exists, where each process requests a resource held by the next process in the chain.

Deadlock Mitigation Strategies

Deadlock Prevention: Design the system’s resource allocation policies to eliminate at least one of the four necessary conditions. For example, requiring processes to request all needed resources upfront eliminates the Hold and Wait condition.
Deadlock Avoidance (Banker’s Algorithm): The OS evaluates resource requests dynamically based on current availability and allocation states. A request is only granted if the resulting allocation leaves the system in a Safe State, ensuring that at least one valid execution sequence remains to satisfy all processes.
Deadlock Detection and Recovery: The system allocates resources without constraints. Periodically, it runs a detection algorithm on a Resource Allocation Graph to find cycles. If a deadlock is detected, the system recovers by aborting processes or preempting resources to break the cycle.

Chapter 3: Memory Management Strategies

I. Compilation, Linking, and Program Loading

Before a source code file can execute in memory, it must go through three distinct processing phases:

[Source Code] ──► (Compiler) ──► [Object Modules] ──► (Linker) ──► [Load Module] ──► (Loader) ──► [Memory Image]

1. Linking Strategies

Static Linking: The linker combines all compiled object modules and required library functions into a single, self-contained executable binary file before runtime.
Load-Time Dynamic Linking: The system links independent object modules together as they are being loaded into main memory.
Run-Time Dynamic Linking: The system defers linking until a specific module is explicitly called during execution, minimizing memory usage for rare code paths.

2. Loading Strategies

Absolute Loading: The compiler generates absolute physical memory addresses directly. This approach is simple but rigid, limiting execution to a single pre-determined memory location.
Static Relocation (Relocatable Loading): The loader translates relative logical addresses to absolute physical addresses as the program is loaded into memory. This requires the system to allocate a continuous block of physical memory large enough to hold the entire program, and the program cannot move during execution.
Dynamic Relocation: The translation of logical addresses to physical addresses is deferred until an instruction is executed. This process is accelerated by hardware support, such as a Base Register (Relocation Register). This architecture allows a process to be split across non-contiguous memory segments and moved dynamically during execution.

II. Continuous Memory Allocation Schemes

Continuous allocation schemes require a process to occupy a single, contiguous block of physical memory.

Single-Contiguous Allocation: Memory is divided into a dedicated system kernel area and a single user application area. Only one program can run at a time, which simplifies management but results in low resource utilization.
Fixed Partitioning Allocation: User memory is divided into fixed, static partitions of equal or unequal sizes. Each partition holds exactly one process. If a small process is assigned to a large partition, the unused space within that partition is wasted, creating Internal Fragmentation.
Dynamic Partitioning Allocation: Memory partitions are created dynamically based on the exact size requested by each process. Over time, as processes are loaded and freed, small unuseable gaps develop between allocated blocks, creating External Fragmentation. This issue can be mitigated by using compaction techniques to slide active segments together.

Dynamic Partitioning Placement Strategies

First Fit (FF): Allocates the first free memory block from the beginning of the address space that is large enough. This strategy is fast but tends to leave many small, unusable fragments at the beginning of memory.
Best Fit (BF): Searches the entire space to find the free block whose size matches the requested size most closely. This approach preserves large blocks but leaves behind tiny, unusable remnants, often maximizing external fragmentation.
Worst Fit (WF): Allocates the largest available free memory block. This keeps remaining fragments large enough to be usable, but it quickly consumes the large contiguous blocks needed by demanding tasks.
Next Fit (NF): Operates like First Fit but resumes its search from the location of the last successful allocation loop, distributing fragments more evenly across memory.

III. Non-Contiguous Memory Allocation Schemes

Non-contiguous allocation schemes break a program’s address space into segments that can be distributed across non-contiguous blocks of physical memory, eliminating external fragmentation.

1. Paging Architecture

The logical address space of a process is divided into fixed-size blocks called Pages. Physical memory is divided into corresponding blocks of the same size called Page Frames.

A logical address is split into a Page Number ($P$) and a Page Offset ($W$):

| Page Number ($P$) | Page Offset ($W$) | | — | — |

The operating system maintains a Page Table for each process to map logical Page Numbers to physical Page Frame Numbers.

Extracted Page Number (P) = Logical Address / Page Size
Extracted Offset (W)      = Logical Address % Page Size
If P >= Page Table Length, trigger an addressing exception.
Physical Frame Address    = Page Table Base + (P * Entry Size)
Physical Address          = (Frame Number * Page Size) + Offset

Translation Lookaside Buffer (TLB)

Standard paging requires two memory accesses for a single data request: first to query the page table, and second to access the actual data. To accelerate this process, hardware systems use a fast cache called a Translation Lookaside Buffer (TLB) or Fast Table.

When a virtual address is parsed, the CPU searches the TLB in parallel. If a match is found (TLB Hit), the physical frame number is returned immediately. If a miss occurs, the system queries the page table in main memory and copies the entry into the TLB for future use.

Multi-Level Paging

For large virtual address spaces, the page table can become too large to fit in a single contiguous memory page. Multi-Level Paging addresses this by creating a hierarchy of page tables, allowing parts of the page table to be swapped out to disk when not in use.

2. Segmentation Architecture

Segmentation divides a program’s address space into logically independent blocks called Segments (such as the main routine, stack, or individual data blocks) based on the programmer’s perspective. Each segment can vary in length.

A logical address consists of a Segment Number ($S$) and a Segment Offset ($W$):

| Segment Number ($S$) | Segment Offset ($W$) | | — | — |

The system uses a Segment Table to map each segment to its base address and length limit in physical memory.

// Address Translation Protocol
int segment = extract_segment_bits(logical_address);
int offset  = extract_offset_bits(logical_address);

if (segment >= segment_table_length) trigger_exception("Out of bounds segment index");
SegmentEntry entry = segment_table[segment];

if (offset >= entry.limit_boundary)  trigger_exception("Offset exceeds segment length limit");
physical_address = entry.base_address + offset;

3. Segmented-Paging (Segment-Paging) Hybrid Architecture

This hybrid approach combines the logical organization of segmentation with the efficient memory utilization of paging. The address space is first divided into logical segments, and each segment is then broken down into fixed-size pages.

A logical address is parsed into three components:

| Segment Number ($S$) | Page Number ($P$) | Page Offset ($W$) | | — | — | — |

To access data, the system performs three sequential memory lookups: first to find the segment entry, second to look up the page frame inside that segment’s page table, and third to access the physical address. This overhead is typically mitigated by using a TLB cache.

IV. Virtual Memory Management Systems

1. Foundation Principles

Traditional memory management requires a program to be loaded entirely into memory before execution can begin, and it must remain there until the program exits. This limits the size of a program to the available physical memory.

Virtual Memory addresses this limitation by leveraging the Principle of Locality:

Temporal Locality: Instructions or data cells that are accessed once are highly likely to be accessed again soon (e.g., inside loops).
Spatial Locality: Accessing a specific memory address suggests that nearby addresses are likely to be accessed soon (e.g., sequential array traversals).

The operating system loads only the actively needed pages of a process into memory, leaving the rest on disk. If the program references an address that is not currently in memory, the system dynamically swaps the required pages into memory, creating the illusion of a much larger address space.

2. Demand Paging Architecture

Demand paging extends standard paging by adding control flags to each page table entry to manage virtual memory states.

Valid/Invalid Bit: Signals whether the page is currently loaded in physical memory.
Access History Field: Tracks how often or when the page was last accessed, used by page replacement algorithms.
Dirty Bit (Modified Bit): Indicates whether the data on the page has been modified since it was loaded into memory. If the dirty bit is $0$, the page can be overwritten immediately upon eviction; if it is $1$, the page must be written back to disk first.
Disk Swap Address: Records the physical location of the page within the swap space on disk.

The Page Fault Resolution Flow:

When a program attempts to access a page whose valid bit is set to $0$, the hardware triggers a Page Fault Exception.

The CPU attempts to read a virtual address; the hardware detects a missing page and throws a Page Fault exception.
The CPU context is saved, control transfers to the kernel, and the process enters the Blocked state.
The OS checks for an empty page frame in physical memory.
If memory is full, a Page Replacement Algorithm selects a victim page to evict.
If the victim page's Dirty Bit is 1, the page is written back to disk.
The requested page is read from disk into the freed frame.
The page table entry is updated, its Valid Bit is set to 1, and the process moves back to the Ready queue.
The CPU resumes execution, retrying the instruction that caused the fault.

3. Page Replacement Algorithms

When physical memory is full, the operating system must choose which page to evict to make room for a new page.

Optimal Replacement Algorithm (OPT): Evicts the page that will not be used for the longest duration in the future. This algorithm provides the lowest possible page fault rate but cannot be implemented in practice because it requires perfect knowledge of future execution paths. It is used primarily as a baseline for performance comparisons.
First-In, First-Out (FIFO): Evicts the oldest page in memory. While simple to implement, it can exhibit Belady’s Anomaly, where increasing the number of physical page frames paradoxically increases the number of page faults.
Least Recently Used (LRU): Evicts the page that has not been accessed for the longest period. This aligns well with the principle of locality and offers strong performance, but it requires hardware support (such as counters or a stack architecture) to track access history efficiently.
Clock Replacement Algorithm (Second-Chance Algorithm): Approximates LRU with lower overhead by arranging page frames in a circular loop with a pointer. Each page maintains a Use Bit. When a page is accessed, its use bit is set to $1$. When a page replacement is needed, the pointer advances through the loop. If it encounters a use bit of $1$, it resets it to $0$ and passes over the page. It evicts the first page it finds with a use bit of $0$.
Enhanced Clock Algorithm: Improves upon the basic Clock algorithm by considering both the Use Bit ($u$) and the Dirty Bit ($m$) to prioritize evicting clean pages first, minimizing disk write operations:
1. Step 1: Scan for $(u=0, m=0)$ without modifying use bits. Evict the first match found.
2. Step 2: If no match is found, scan for $(u=0, m=1)$, setting the use bit to $0$ on all pages passed over. Evict the first match found.
3. Step 3: If needed, repeat from Step 1. Since use bits were cleared in Step 2, a match is guaranteed.

4. Thrashing and Working Sets

Thrashing (System Churn): If a process is not allocated a sufficient number of physical frames, its page fault rate will rise sharply. The system spends more time moving pages between disk and memory than executing actual instructions, causing CPU efficiency to drop significantly.
Working Set Model: The working set is the collection of pages a process has actively accessed within a recent moving time window $\Delta$. To prevent thrashing, the operating system monitors each process’s working set and ensures it allocates enough physical page frames to hold the entire working set.

                  Page Fault Rate Curve
             ▲
             │       /◄── Thrashing Boundary Zone
             │      /
             │     /
             │    /
             │   / 
             └───┴────────────────────────► Allocated Frames
                 ▲
                 └─ Working Set Size Boundary

Operating Systems: Architecture, Process Management, and Memory Structures