Operating System

Outline

Definition

An Operating System (OS) is a layer of software that manages hardware resources and provides abstractions to user programs. It serves two fundamental roles:

• Resource Manager — multiplexes CPU, memory, I/O devices among competing processes.
• Extended Machine — hides hardware complexity behind clean, portable interfaces (system calls).

Tips

• Process Management, Memory Management, File System, Device Management.

• Concurrency, Sharing, Virtualization, Asynchronism.

Architecture

The OS kernel runs in supervisor mode (kernel mode), with unrestricted access to hardware; user programs run in user mode, confined to their own virtual address space. The boundary is crossed via system calls and interrupts.

Philosophy

• Abstraction v.s. Performance: higher-level interfaces simplify programming but introduce overhead.
• Protection v.s. Sharing: isolate processes for safety, yet allow efficient communication.
• Fairness v.s. Throughput: scheduler must balance individual response time with overall system utilization.

Process & Thread

Process

A process is a program in execution. It consists of:

• Code (text segment) — executable instructions.
• Data — global/static variables.
• Heap — dynamically allocated memory.
• Stack — function call frames, local variables.
• PCB (Process Control Block) — metadata: PID, state, registers, memory maps, open file descriptors.

Process State Diagram:

          ┌──────────┐
          │  Created  │
          └─────┬─────┘
                │ admitted
                ▼
          ┌──────────┐  scheduler dispatch  ┌──────────┐
          │  Ready   │ ───────────────────► │ Running  │
          └─────┬─────┘ ◄─────────────────── └─────┬─────┘
                │    interrupt / yield             │
                │                                  │ I/O or event wait
                │         ┌──────────┐             │
                └─────────│ Waiting  │◄────────────┘
                          └──────────┘     exit → Terminated

• Ready → Running: chosen by the scheduler (dispatch).
• Running → Ready: preempted (timer interrupt) or voluntarily yields.
• Running → Waiting: blocks on I/O or an event.
• Waiting → Ready: I/O or event completes.

Thread

A thread is the unit of CPU scheduling. Threads within the same process share:

• Code, data, heap, open files — all global resources.
• Each has its own stack, registers, and PC (program counter).

Kernel-level Threads (KLT) v.s. User-level Threads (ULT):

• ULT: managed entirely in user space by a threading library. Fast creation/switching (no kernel involvement), but one blocking call blocks the entire process.
• KLT: managed by the kernel. Blocking is per-thread, but switching requires a mode switch.
• Hybrid: multiple KLTs mapped from multiple ULTs (e.g., Go’s goroutines on OS threads).

Context Switch

A context switch is the mechanism by which the CPU switches from one process/thread to another.

Steps:

1. Save the current process’s state (registers, PC, stack pointer) into its PCB.
2. Load the next process’s state from its PCB.
3. Switch memory mappings (page table base register).
4. Flush the TLB and pipeline if necessary.

The cost is pure overhead — no useful work is done during the switch. Typical latency: 1–10 μs.

CPU Scheduling

Scheduling Metrics

Scheduling Algorithms

FCFS (First-Come, First-Served) — non-preemptive. Simple but suffers from the convoy effect: short jobs queue behind long jobs, inflating average waiting time.

SJF (Shortest Job First) — non-preemptive, selects the process with the smallest burst time. Provably optimal for minimizing average waiting time. However, requires knowing future CPU bursts.

SRTF (Shortest Remaining Time First) — preemptive version of SJF. Whenever a new process arrives with a shorter remaining time than the currently running one, the CPU is preempted.

Round Robin (RR) — each process gets a fixed time quantum $q$. After $q$ expires, it’s preempted and placed at the tail of the ready queue. If there are $n$ processes, each waits at most $(n-1)q$ before its next turn.

• $q$ large → degenerates to FCFS.
• $q$ small → many context switches, high overhead.
• Typical $q$: 10–100 ms.

Priority Scheduling — each process has a priority; the CPU is allocated to the highest-priority ready process. May lead to starvation: low-priority processes never run. Solution: aging — gradually increase priority over time.

Multilevel Feedback Queue (MLFQ) — the BSD/Linux approach:

• Multiple queues with different priorities.
• High-priority queues have short time slices (for interactive jobs).
• Low-priority queues have long time slices (for CPU-bound jobs).
• Processes migrate between queues based on observed behavior.
• Periodically, all processes are boosted to the top queue (prevents starvation).

Preemptive v.s. Non-Preemptive

Synchronization

The Critical Section Problem

A critical section is a code segment that accesses shared resources and must not be executed concurrently by multiple threads. The solution must satisfy:

1. Mutual Exclusion: at most one thread in its critical section at any time.
2. Progress: if no thread is in the critical section and some threads want to enter, the selection of the next entrant cannot be postponed indefinitely.
3. Bounded Waiting: a thread that requests entry must eventually be granted it (no starvation).

Locks

A mutex (mutual exclusion lock) provides two atomic operations:

1
2
3
4

lock_t mutex;
lock(&mutex);    // acquire — block if already held
/* critical section */
unlock(&mutex);  // release

Spinlock — the waiting thread spins in a loop while (test_and_set(&lock)), consuming CPU cycles. Efficient only for very short critical sections.

Hardware Support: Atomic Instructions

Test-and-Set (atomic RMW — Read-Modify-Write):

1
2
3
4
5

int TestAndSet(int *ptr, int new) {
    int old = *ptr;
    *ptr = new;
    return old;
}

Compare-and-Swap (CAS):

1
2
3
4
5
6

int CAS(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}

These are the building blocks of lock-free data structures.

Semaphores

A semaphore $S$ is an integer variable accessed only through two atomic operations:

• $P$ (wait / down / proberen): while (S <= 0); S--;
• $V$ (signal / up / verhogen): S++;

If $S$ counts resources, it’s a counting semaphore. If $S \in \{0, 1\}$, it’s a binary semaphore (equivalent to a mutex with ownership tracking).

Classic use: the Producer-Consumer problem with a bounded buffer:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

sem_t empty = N;  // buffer slots available
sem_t full  = 0;  // items in buffer
sem_t mutex = 1;  // buffer access

// Producer
P(&empty); P(&mutex);
/* insert item */
V(&mutex); V(&full);

// Consumer
P(&full);  P(&mutex);
/* remove item */
V(&mutex); V(&empty);

Monitors

A monitor is a high-level synchronization construct (language-level, e.g., Java’s synchronized) that encapsulates shared data, operations, and synchronization into a single module. Only one thread may be active inside a monitor at a time.

Condition variables allow threads to wait for a condition inside a monitor:

• wait(cond) — releases the monitor lock and blocks.
• signal(cond) — wakes one waiting thread.
• broadcast(cond) — wakes all waiting threads.

Hoare semantics: signal immediately transfers the monitor to the awakened thread.
Mesa semantics (Java, pthreads): the signaler continues; the awakened thread must re-check the condition upon wake-up (use while instead of if).

Deadlock

Necessary Conditions (Coffman, 1971)

All four must hold simultaneously for a deadlock to occur:

1. Mutual Exclusion: resources cannot be shared.
2. Hold and Wait: a process holds some resources while waiting for others.
3. No Preemption: resources cannot be forcibly taken away.
4. Circular Wait: a cycle exists in the resource allocation graph.

Resource Allocation Graph

• Process $P_i$ → Resource $R_j$ (request edge): $P_i$ is waiting for $R_j$.
• Resource $R_j$ → Process $P_i$ (assignment edge): $R_j$ is allocated to $P_i$.
• A cycle in the graph with single-instance resources iff deadlock.
• With multi-instance resources, a cycle is necessary but not sufficient.

Handling Strategies

Banker’s Algorithm (Avoidance)*

Maintains:

• Available $[m]$: available instances of each resource type.
• Max $[n \times m]$: maximum demand of each process.
• Allocation $[n \times m]$: currently allocated.
• Need $[n \times m]$ = Max − Allocation.

A state is safe if there exists a sequence $\langle P_{i_1}, \dots, P_{i_n} \rangle$ such that for each $P_{i_k}$, its remaining need can be satisfied by currently available resources plus those held by preceding $P_{i_j}$.

When $P_i$ requests resources, the algorithm:

1. Temporarily grants the request.
2. Checks if the resulting state is safe.
3. If safe → grant; if unsafe → deny and block $P_i$.

Complexity: $O(m \cdot n^2)$ per request.

Memory Management

Address Binding

Logical v.s. Physical Address

• Logical (virtual) address: generated by the CPU; what the process sees.
• Physical address: actual location in RAM.
• The MMU (Memory Management Unit) maps logical to physical at runtime:

with bounds checking: $0 \le \text{Logical Address} < \text{Limit}$.

Fragmentation

Compaction — move allocated blocks to coalesce free space. Costly, and only possible with dynamic relocation.

Paging

Paging divides physical memory into fixed-size frames and logical memory into same-sized pages. The mapping is maintained in a page table.

where $\text{Frame} = \text{PageTable}[\text{Page Number}]$.

Page Table Entry (PTE) typically contains:

Translation Lookaside Buffer (TLB)

The page table is in memory — every data access would require two memory references (page table, then data). The TLB is a small, fast, fully-associative hardware cache for PTEs.

Effective Access Time:

where $h_{\text{TLB}}$ is the TLB hit rate (typically > 99%).

Multi-level Page Tables

A single page table for a 64-bit address space would be enormous (e.g., $2^{52}$ entries for 4 KB pages). Multi-level paging resolves this by hierarchically indexing:

• The outer page table maps large chunks; only populated subtrees are allocated.
• x86-64 uses 4 levels: PML4 → PDPT → PD → PT → Offset.

Inverted Page Table

Instead of one entry per virtual page, the inverted table has one entry per physical frame, indexed by (PID, page number). Searched via a hash table. Used by PowerPC and some IA-64 implementations.

Segmentation

Segmentation divides memory into variable-sized segments (code, data, stack). Each segment has a base and limit.

Segmentation matches the programmer’s view of memory but suffers from external fragmentation. Many systems combine segmentation + paging (e.g., x86 in protected mode).

Virtual Memory

Virtual memory decouples the address space from physical memory, enabling:

• Programs larger than physical memory.
• Isolation: each process has its own virtual address space.
• Efficient sharing (e.g., shared libraries mapped into multiple processes).

Demand Paging

Pages are loaded into memory on demand — only when accessed.

• Page fault: CPU accesses a page not in memory → trap to OS.
• OS selects a victim frame (if memory is full), swaps it out, loads the requested page, updates the page table, and restarts the faulting instruction.

Page Replacement Algorithms

When memory is full and a page fault occurs, the OS must evict a page. The goal: minimize the page-fault rate.

Belady’s Anomaly: with FIFO, increasing the number of frames can paradoxically increase the page-fault rate. This cannot happen with stack algorithms (LRU, OPT).

Working Set Model

The working set $W(t, \Delta)$ is the set of pages referenced during the last $\Delta$ memory references at time $t$. The OS should allocate enough frames to hold the working set; if $\sum |W_i| > \text{total frames}$, thrashing occurs — the system spends more time paging than executing.

Working set clock (WSClock) — an efficient implementation combining the clock algorithm with working set tracking.

Thrashing

Thrashing: a process is spending more time swapping pages in and out than executing. Detection:

• Monitor page-fault rate: if it exceeds a threshold, the process needs more frames.
• If total demand exceeds available memory, the OS must suspend (swap out) some processes — load control.

File System

File Abstraction

A file is a named, persistent collection of data. The OS provides:

• Naming: hierarchical directory structure.
• Access methods: sequential, random (direct), indexed.
• Protection: owner, group, world permissions (rwx).

Directory Structure

/ (root)
├── bin/
├── etc/
├── home/
│   └── alice/
│       └── notes.md
├── usr/
└── var/

• Single-level — all files in one directory (naming conflicts).
• Two-level — per-user directories.
• Tree-structured — arbitrary depth; most modern OSes.
• Acyclic graph — allows sharing via links (hard links / symbolic links).
• General graph — cycles possible; garbage collection needed.

File Allocation Methods

Inode Structure (Unix)

The inode (index node) stores metadata and block pointers:

• File type, permissions, owner, timestamps.
• Direct blocks: first 12 block pointers point directly to data blocks.
• Single indirect: points to a block of block pointers.
• Double indirect: points to a block of single indirect pointers.
• Triple indirect: for very large files.

For a 4 KB block with 4-byte pointers, the maximum file size:

Free Space Management

• Bit vector: each block represented by 1 bit (free/allocated). Efficient but large.
• Linked list: free blocks form a list. Slow traversal.
• Grouping: store addresses of $n$ free blocks in the first free block.
• Counting: store (start_block, count) for contiguous free runs.

Journaling

Write-ahead logging to ensure file system consistency after a crash:

1. Write intended changes to a journal (log).
2. Commit the journal entry.
3. Checkpoint: apply changes to the actual file system.
4. On crash recovery: replay committed journal entries, discard uncommitted ones.

Linux ext4 supports three journaling modes: journal (data + metadata), ordered (metadata only, data first), writeback (metadata only, no ordering).

I/O Management

I/O Architecture

User Process
     │ system call
     ▼
Device-Independent OS Software
     │
     ▼
Device Driver ─── Device Controller ─── Device

• Device controller: hardware interface (registers, DMA).
• Device driver: OS kernel module that talks to a specific controller.
• Device-independent layer: buffering, caching, naming, protection.

I/O Methods

Disk Scheduling

For a moving-head disk, access time = seek time + rotational latency + transfer time. Seek time dominates.

Inter-Process Communication (IPC)

Virtualization

The OS itself can be virtualized:

• Type 1 Hypervisor (bare metal): runs directly on hardware (VMware ESXi, KVM, Xen).
• Type 2 Hypervisor (hosted): runs on a host OS (VirtualBox, VMware Workstation).

Key techniques:

• Trap-and-emulate: guest privileged instructions trap to the hypervisor.
• Binary translation: rewrite non-virtualizable instructions on the fly.
• Hardware-assisted: Intel VT-x / AMD-V provide VMX root/non-root modes.
• Paravirtualization: guest OS is modified to call hypercalls instead of privileged instructions.

References

• Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.), Wiley.
• Tanenbaum & Bos, Modern Operating Systems (5th ed.), Pearson.
• McKusick, Neville-Neil & Watson, The Design and Implementation of the FreeBSD Operating System (2nd ed.), Addison-Wesley.
• Love, Linux Kernel Development (3rd ed.), Addison-Wesley.
• 2027年计算机操作系统考研复习指导，王道论坛。