UNIT 2: OPERATING SYSTEMS - COMPREHENSIVE NOTES

Based on analysis of 6 past examination papers (Jun 2025, Jun 2024, Jun 2023, Nov 2023, Dec 2024, Nov 2022, Jun 2022).

1. INTRODUCTION & OVERVIEW OF OPERATING SYSTEMS

Evolution of Operating Systems

• Generations:

  1. Batch OS: Jobs grouped, no user interaction. (e.g., early IBM systems).

  2. Multiprogramming OS: Multiple jobs in memory, CPU switches when one waits. Increases CPU Utilization.

  3. Time-Sharing OS: CPU time shared among users (time slices). Interactive. (e.g., UNIX).

  4. Parallel OS: Manages multiple CPUs/cores tightly coupled. (e.g., modern Linux/Windows).

  5. Distributed OS: Network of independent computers appears as single system. (e.g., Amoeba).

  6. Network OS: Provides file/print sharing over network. (e.g., Windows Server).

• Key Milestone: Transition from batch to time-sharing enabled interactive computing.

Functions of an Operating System

• Process Management: Create/terminate/schedule processes/threads.

• Memory Management: Allocate/deallocate memory, handle paging/segmentation.

• Storage Management: File system, disk scheduling, space allocation.

• I/O System Management: Device drivers, buffering, caching.

• Protection & Security: Access control, authentication, cryptography.

• Network Management: Remote access, resource sharing, communication.

• Command Interpreter (Shell): User interface to OS services.

Services Provided to Users and Applications

Characteristics of an Operating System

• Convenience: Makes computer easy to use.

• Efficiency: Maximizes resource utilization (CPU, I/O).

• Ability to Evolve: Should accommodate new features/hardware (modular design).

• Reliability: Minimize failures, ensure correct operation.

• Security: Protect against internal/external threats.

• Portability: Run on different hardware with minimal changes.

OS Structure and Design

• Layered Approach: OS in layers (hardware at bottom, UI at top). Each layer uses services of layer below.

  • Advantage: Easier to debug, verify.

  • Disadvantage: Can be inefficient (must traverse layers).

• Microkernels: Minimal kernel (only essential services: IPC, memory management). Other services (file system, drivers) run in user space as servers.

  • Advantage: More secure, reliable, portable.

  • Disadvantage: Performance overhead due to IPC.

• Modules (Loadable Kernel Modules): Kernel components loaded/unloaded dynamically (e.g., Linux kernel modules). Balances modularity & performance.

• Virtual Machines: Hypervisor (VMM) shares hardware among multiple OSes (e.g., VMware).

  • Provides isolation and hardware abstraction.

• System Boot Process:

  1. BIOS/UEFI initializes hardware.

  2. Loads bootloader from disk.

  3. Bootloader loads kernel into memory.

  4. Kernel initializes, mounts root filesystem.

  5. First user-space process (init/systemd) starts.

Utility Programs

Common tools provided with OS:

• File Management: copy, move, del, dir.

• System Status: top, ps, df, free.

• Debugging: gdb, strace.

• Disk/Partition: fdisk, format.

• Security: passwd, chmod, firewall.

[!TIP] Exam Focus: Evolution generations, OS functions, layered vs. microkernel trade-offs, and boot sequence are frequently asked (Jun 2025, Nov 2023, Dec 2024).

2. PROCESS MANAGEMENT

Process Concept

• Program: Passive entity (executable file on disk).

• Process: Active entity (program in execution). Has Program Counter, registers, memory, resources, PCB.

• Process State Diagram:

  
  New → Ready → Running → Waiting → Terminate
  
              ↑         ↓
  
              └───(I/O)─┘
  
  

  • New: Being created.

  • Ready: Waiting for CPU.

  • Running: Executing on CPU.

  • Waiting/Blocked: Waiting for I/O/event.

  • Terminate: Execution finished.

Process Control Block (PCB)

• Definition: Kernel data structure storing all process information.

• Fields:

  • Process State (Ready, Running, etc.)

  • Process ID (PID)

  • Program Counter (PC)

  • CPU Registers

  • Memory Management Info (page tables, base/limit)

  • Scheduling Info (priority, queue pointers)

  • I/O Status Info (open files, allocated I/O devices)

  • Accounting Info (CPU time used, limits)

• Significance: PCB is the "process" from OS perspective. Context switching saves/restores PCB.

Process Scheduling

• Scheduling Queues:

  • Job Queue: All processes in system.

  • Ready Queue: Processes in main memory, ready to run.

  • Device Queues: Processes waiting for specific I/O device.

• Schedulers:

  • Long-term (Job Scheduler): Selects processes from job pool to admit to main memory (controls degree of multiprogramming). Rarely used in modern systems.

  • Short-term (CPU Scheduler): Selects ready process to run on CPU (very frequent, context switch overhead).

  • Medium-term (Swapper): Swaps processes in/out of memory to control multiprogramming level.

Context Switching

• Mechanism: Save state of current process (PCB) → Load state of next process (PCB).

• Overhead: Purely system overhead (no useful work). Depends on hardware support (register set size), OS complexity.

• Role of PCB: PCB is the "saved state"; switching PCBs = switching processes.

Operations on Processes

• Creation (fork() in UNIX): Parent creates child (duplicate of parent's PCB/memory). Returns child PID to parent, 0 to child.

• Termination (exit()): OS deallocates resources, removes PCB. Parent may wait() for child's termination.

• Key System Calls:

  • fork(): Create child process.

  • exec(): Replace process memory space with new program.

  • wait(): Parent waits for child to terminate.

  • exit(): Terminate current process.

  • getpid(): Get process ID.

Interprocess Communication (IPC)

• Shared Memory Systems:

  • Processes share a region of physical memory.

  • Fastest IPC (no kernel involvement after setup).

  • Requires synchronization (semaphores) to avoid race.

• Message Passing Systems:

  • Processes exchange messages via kernel.

  • Direct Communication: Processes name each other explicitly.

  • Indirect Communication: Messages sent to/received from mailboxes/ports.

  • Synchronous: Sender blocks until message received.

  • Asynchronous: Sender continues after message sent.

• Pipes:

  • Unidirectional byte stream between related processes (parent-child).

  • Implemented as kernel buffer.

• Named Pipes (FIFOs):

  • Pipe with a name in filesystem. Unrelated processes can communicate.

Threads

• Definition: Basic unit of CPU utilization; lightweight process within same address space.

• Benefits:

  • Responsiveness: One thread can run while another waits.

  • Resource Sharing: Threads share code, data, files of process.

  • Economy: Creating/context-switching threads cheaper than processes.

  • Scalability: Parallelism on multi-core systems.

• User-Level Threads (ULT):

  • Managed by user-space thread library (e.g., Pthreads, Java threads).

  • Kernel unaware of threads (sees only one process).

  • Advantages: Fast creation/switch (no kernel call), portable.

  • Disadvantages: One thread blocks → entire process blocks. No true parallelism on multi-core.

• Kernel-Level Threads (KLT):

  • Managed directly by OS kernel.

  • Kernel schedules individual threads.

  • Advantages: True parallelism, one thread block doesn't affect others.

  • Disadvantages: Slower creation/switch (kernel mode), less portable.

• Multithreading Models:

  • Many-to-One: Many ULTs → one KLT. (e.g., early Solaris green threads).

  • One-to-One: Each ULT maps to a KLT. (e.g., Linux, Windows). Good concurrency.

  • Many-to-Many: Many ULTs multiplexed onto many KLTs. Balances.

[!TIP] Exam Focus: PCB fields, thread comparison (ULT vs KLT), and IPC methods are very frequent (Jun 2025, Jun 2024, Dec 2024). Know advantages/disadvantages of thread models.

3. CPU SCHEDULING

Fundamental Concepts

• CPU-I/O Burst Cycle: Process alternates between CPU bursts (computation) and I/O bursts (waiting).

• Preemptive: OS can forcibly take CPU from process (e.g., RR, SRTF, Priority with preemption).

• Non-preemptive: Process voluntarily yields CPU (e.g., FCFS, non-preemptive SJF/Priority).

• Scheduling Criteria:

  • CPU Utilization: % time CPU busy. (Goal: 40-90%).

  • Throughput: # processes completed per unit time.

  • Turnaround Time: Total time from submission to completion. $$\displaystyle T_{turnaround} = T_{completion} - T_{arrival} $$.

  • Waiting Time: Total time spent in ready queue. $$\displaystyle T_{waiting} = T_{turnaround} - T_{burst} $$.

  • Response Time: Time from request to first response (in time-sharing).

Scheduling Algorithms

Gantt Chart Calculation Steps:

1. Sort processes by algorithm rule.

2. Draw timeline (Gantt chart) showing process execution blocks.

3. Calculate Completion Time (CT) for each process (end of its last burst).

4. Turnaround Time (TAT) = CT - Arrival Time.

5. Waiting Time (WT) = TAT - Burst Time.

6. Average WT/TAT = Sum / number of processes.

[!TIP] Exam Focus: FCFS, SJF (preemptive/non-preemptive), Priority, and RR are highest priority. Be prepared to draw Gantt charts and compute avg waiting/turnaround time (Jun 2024, Jun 2023, Nov 2022). Know convoy effect (FCFS) and Belady's anomaly (FIFO in VM).

4. SYNCHRONIZATION & CONCURRENCY

Critical Section Problem

• Problem: Multiple processes/threads share data/ resources. Code segment accessing shared resource is critical section.

• Requirements for Solution:

  1. Mutual Exclusion: Only one process in CS at a time.

  2. Progress: If no one in CS and others want to enter, decision cannot be postponed indefinitely.

  3. Bounded Wait: No process waits indefinitely to enter CS (fairness).

Solutions to Critical Section Problem

• Peterson's Solution (for 2 processes):

  
  int turn = 0; // shared
  
  bool flag[2]; // shared, initially false
  
  // Process Pi (i = 0 or 1)
  
  flag[i] = true;
  
  turn = j; // other process
  
  while (flag[j] && turn == j) ; // busy wait
  
  // Critical Section
  
  flag[i] = false;
  
  // Remainder Section
  
  

  • Uses busy waiting. Works for two processes only.

• Hardware Support:

  • Test-and-Set: Atomic instruction TS(&lock) returns old value and sets lock to true.

  • Compare-and-Swap (CAS): Atomic CAS(&lock, expected, new).

  • Both can implement spinlocks (busy waiting).

• Semaphores:

  • Definition: Integer variable accessed atomically via two operations: wait() (P) and signal() (V).

  • Operations:

    
    wait(S) {
    
        while (S <= 0) ; // busy wait
    
        S--;
    
    }
    
    signal(S) {
    
        S++;
    
    }
    
    

  • Usage:

    • Mutual Exclusion: semaphore mutex = 1; → wait(mutex); CS; signal(mutex);

    • Ordering/Synchronization: Count > 0 indicates available resource/event.

  • Blocking Semaphores: OS blocks process instead of busy wait (more efficient).

• Monitors:

  • High-level synchronization construct. Only one process active in monitor at a time.

  • Contains shared variables, procedures, and condition variables.

  • Condition Variables: wait(cv) (releases monitor lock & blocks), signal(cv) (wakes one waiting process).

  • Dining Philosophers Solution: Use monitor with two condition variables (left, right) per philosopher.

Concurrency Issues

• Race Condition: Outcome depends on timing of concurrent accesses.

• Starvation: Process perpetually denied resource.

• Deadlock: (Covered in next section).

• Real Concurrency: Multiple processes truly executing simultaneously on multi-processor.

• Virtual Concurrency: Single CPU rapidly switches between processes (time-sharing).

[!TIP] Exam Focus: Peterson's solution, semaphore operations, and monitor solution to Dining Philosophers are classic questions (Jun 2023, Nov 2023). Understand how to use semaphores for mutual exclusion and ordering.

5. DEADLOCK

Definition & Necessary Conditions (Coffman Conditions)

• Deadlock: Set of processes are blocked because each holds a resource and waits for another held by another in the set.

• Four conditions must hold simultaneously:

  1. Mutual Exclusion: Resource cannot be shared.

  2. Hold and Wait: Process holds at least one resource and waits for another.

  3. No Preemption: Resources cannot be forcibly taken.

  4. Circular Wait: Circular chain of processes, each waiting for next's resource.

• Example: Two processes, each holding one CD drive and waiting for the other's scanner.

Deadlock Handling Methods

Deadlock Prevention (Strategies per Condition)

1. Mutual Exclusion: Not always possible (printers, etc.).

2. Hold and Wait: Require processes to request all resources at once (low utilization, starvation possible).

3. No Preemption: Preempt resources if process waits (complex, state must be saved/restored).

4. Circular Wait: Impose total ordering on resource types. Request in increasing order.

Deadlock Avoidance: Banker's Algorithm

• Data Structures (for n processes, m resource types):

  • Available[1..m]: Available instances of each resource.

  • Max[n][m]: Maximum demand of each process.

  • Allocation[n][m]: Currently allocated to each process.

  • Need[n][m]: Need = Max - Allocation. Remaining need.

• Safety Algorithm (Find Safe Sequence):

  1. Work = Available, Finish[i] = false for all i.

  2. Find i such that Finish[i]==false and Need[i] <= Work.

  3. If found, Work = Work + Allocation[i], Finish[i]=true, goto 2.

  4. If all Finish[i]==true → safe state, sequence is order found.

• Resource-Request Algorithm:

  1. If Request[i] <= Need[i], else error (exceed max claim).

  2. If Request[i] <= Available, allocate; else process waits.

  3. Check if new state is safe. If yes, allocate; if no, process waits.

• Example Problem (from Nov 2022):

  Given Allocation, Max, Available matrices, compute Need, check safety, and test request.

Deadlock Detection & Recovery

• Single Instance (Resource Allocation Graph - RAG):

  • Graph: Processes (circles), Resources (squares), Assignment edges (→), Request edges (--→).

  • Cycle detection in RAG = deadlock (only for single instance).

• Multiple Instances (Wait-for Graph + Detection Algorithm):

  • Similar to Banker's safety check but using Allocation and Request matrices.

  • If no process can be found whose request can be satisfied → deadlock.

• Recovery:

  • Process Termination: Terminate one/more deadlocked processes (choose victim by priority, age, resources held).

  • Resource Preemption: Take resource from a process (must rollback process to safe state, avoid starvation).

[!TIP] Exam Focus: Banker's algorithm (safety & request) is extremely frequent (Jun 2025, Jun 2024, Nov 2022). Practice with given snapshots. Know all 4 Coffman conditions with examples (Jun 2023).

6. MEMORY MANAGEMENT

Background

• Logical (Virtual) Address: Generated by CPU.

• Physical Address: Seen by memory unit.

• Binding of Instructions to Memory:

  • Compile-time: Absolute code (must know load address).

  • Load-time: Relocatable code (loader modifies addresses).

  • Execution-time: Dynamic relocation (base/limit registers). Most flexible.

Contiguous Allocation

• Single Partition: OS in low memory, user process in high memory.

• Multiple Partition (Fixed/ Variable):

  • Fixed Partitioning: Memory divided into fixed-sized blocks. Internal fragmentation (wasted space in block).

  • Variable Partitioning: Allocate exact-size block. External fragmentation (holes between processes).

• Fragmentation:

  • Internal: Wasted space within allocated partition.

  • External: Total memory space enough, but not contiguous.

• Compaction: Shift processes in memory to create one large free hole. Only possible with dynamic relocation (base register).

• Relocation: Moving process in memory requires updating base/limit and all logical addresses in code/data (done by OS or hardware with relocation registers).

Non-Contiguous Allocation

• Paging:

  • Concept: Divide physical memory into fixed-size frames (power of 2). Logical memory into same-size pages. No external fragmentation, internal fragmentation (last page).

  • Address Translation: Logical Address = Page # + Offset. Physical Address = Frame # + Offset.

    • Page # → Page Table lookup → Frame #.

  • Page Table: Array mapping page # → frame #. Stored in memory (PTBR - Page Table Base Register).

  • Translation Lookaside Buffer (TLB): Fast associative cache for page table entries. Hit ratio crucial for performance.

  • Page Table Structures:

    • Hierarchical (Multi-level): Page table paged (e.g., 2-level for 32-bit). Reduces contiguous memory needed for PT.

    • Hashed: Hash page # → bucket of PTEs.

    • Inverted: One entry per physical frame, stores (process ID, logical page #). Good for shared memory.

• Segmentation:

  • Concept: Memory divided into logical segments (code, data, stack, heap). Each has name and length.

  • Address Translation: Logical Address = <Segment #, Offset>. Segment Table entry: <base, limit>.

  • Advantages over Paging:

    • User's view of memory (segments correspond to program modules).

    • Easier sharing (share entire segment).

    • Easier protection (per-segment R/W/X).

    • No internal fragmentation (segments variable).

  • Disadvantage: External fragmentation (variable segments).

• Paged Segmentation: Combine both. Memory divided into segments, each segment paged. (e.g., Intel x86).

Virtual Memory & Demand Paging

• Virtual Memory: Allows execution of processes not completely in memory. Only parts needed are loaded.

• Demand Paging: Pages loaded only when referenced (on page fault).

• Page Fault: Occurs when referenced page not in memory.

  • Handling:

    1. Check validity of reference.

    2. Find free frame (or replace victim).

    3. Schedule disk I/O to read page.

    4. Context switch to another process (I/O wait).

    5. Page read, restart instruction.

• Page Fault Rate: p = (Page Faults) / (Total References). Low p (~0.001) needed for good performance.

• Effective Access Time (EAT):

$$ EAT = (1 - p) \times t_{access} + p \times (t_{pagefault} + t_{access}) $$

where $$\displaystyle t_{pagefault} $$ includes disk access + swap overhead + context switch.

Page Replacement Algorithms

• Goal: Minimize page fault rate.

• FIFO: Replace oldest page (Belady's Anomaly possible).

• Optimal (OPT): Replace page not used for longest time in future. (Theoretical minimum faults, unimplementable).

• LRU (Least Recently Used): Replace page not used for longest time in past. Approximates OPT. Can be implemented with stack or aging bits.

• Second-Chance (Clock): FIFO with reference bit. If R=1, set R=0 and give second chance (circular queue).

• Clock: Similar to Second-Chance, pointer advances circularly.

• Belady's Anomaly: For some algorithms (FIFO), increasing frames increases page faults. Happens due to non-stack algorithms (OPT, LRU are stack algorithms, no anomaly).

Page Fault Calculation Steps:

1. Initialize frames (empty or with initial pages).

2. For each reference in string:

   • If page in frame → hit (no fault).

   • If page not in frame → fault. If free frame, use it; else apply replacement algorithm to choose victim, replace.

   • Record fault.

3. Count total faults.

[!TIP] Exam Focus: Page fault calculation for FIFO & LRU is very frequent (Jun 2024, Dec 2024, Nov 2022). Know Belady's anomaly definition and example (FIFO). Understand difference between paging & segmentation (Jun 2023, Nov 2023).

Thrashing

• Definition: Process spends more time paging than executing. CPU utilization drops.

• Cause: Working Set (set of pages a process needs in recent time window) > allocated frames.

• Detection: Monitor page fault rate. High rate + low CPU utilization → thrashing.

• Solution: Working-Set Model: Ensure each process has enough frames for its working set. Reduce degree of multiprogramming if total working set > total frames.

Memory Management in Specific OS

• UNIX (BSD/FFS):

  • Uses demand paging with LRU-like approximation (2nd chance).

  • Swap space on disk for swapped-out pages.

  • Page replacement daemon (kswapd) runs when free memory low.

  • Inode-based file system (UFS).

• Windows (NTFS):

  • Virtual address space per process (2GB user, 2GB kernel by default).

  • Paging file (pagefile.sys) for virtual memory.

  • Working Set: Set of pages resident for process. OS trims working set if memory pressure.

  • NTFS: Master File Table (MFT) based, journaling, ACLs.

[!TIP] Exam Focus: Compare UNIX vs Windows memory management (Jun 2025, Jun 2023, Dec 2024). Know working set concept and thrashing.

7. STORAGE MANAGEMENT (DISK & TAPE)

Disk Structure & Performance

• Disk Geometry: Platters → Tracks → Sectors (blocks). Cylinder = tracks aligned vertically.

• Performance Parameters:

  • Seek Time ($$\displaystyle T_s $$): Move head to correct track. Dominant factor.

  • Rotational Latency ($$\displaystyle T_r $$): Wait for sector to rotate under head. Avg = $1/(2 \times rotation rate)$.

  • Transfer Time ($$\displaystyle T_t $$): Read/write data. $$\displaystyle T_t = (bytes) / (transfer rate) $$.

  • Access Time: $$\displaystyle T_a = T_s + T_r + T_t $$.

Disk Scheduling Algorithms

• Goal: Minimize total seek time (not rotational latency/transfer).

• FCFS (First-Come, First-Served): Serve requests in arrival order. Fair but often poor seek.

• SSTF (Shortest Seek Time First): Select request closest to current head position.

  • Advantage: Reduces average seek.

  • Disadvantage: Starvation of far requests. Not fair.

• SCAN (Elevator): Head moves in one direction (e.g., low→high), servicing requests until end, then reverses.

  • Advantage: Fair, good average seek.

• C-SCAN (Circular SCAN): Head moves in one direction only. When reaches end, jumps to beginning (no service). Treats cylinders as circular.

  • Advantage: More uniform wait time than SCAN.

• LOOK & C-LOOK: Like SCAN/C-SCAN but only go as far as last request in direction, then reverse/jump.

• Calculation: Sum absolute differences between consecutive requests (including initial head position).

Example (from Nov 2023, Dec 2024):

Head at 143, previous 125, requests: 86,147,91,177,94,150,102,175,130.

• FCFS: |143-86| + |86-147| + ... = Total Head Movement.

• SSTF: Choose closest each time from current position.

Disk Space Allocation

• FAT (File Allocation Table): Special linked allocation. Table indexed by block # contains next block #. Entire table kept in memory for speed.

• Multi-level Indexed (UNIX inode):

  • Direct pointers (12), single indirect (1), double indirect (1), triple indirect (1).

  • Supports very large files.

Tape Organization (if covered)

• Sequential Access: Must wind tape to position. No random access.

• Tape Drives: Reel-to-reel, cassette, cartridge.

• Mounting/Dismounting: Manual or automated tape libraries (jukeboxes).

Disk Mounting

• System Boot: BIOS/UEFI → bootloader → kernel → mount root filesystem.

• Mounting: Attach filesystem on partition/device to directory tree (mount point).

• Unmounting: Detach filesystem (ensure no open files).

• Mount Table: OS maintains table of mounted filesystems.

[!TIP] Exam Focus: Disk scheduling calculations (FCFS, SSTF, SCAN, C-SCAN) are very frequent (Jun 2023, Nov 2023, Dec 2024). Disk allocation methods comparison (Jun 2024, Jun 2023).

8. FILE SYSTEM

File Concept

• File Attributes: Name, Identifier (inode #), Type, Location, Size, Protection, Time/date (create, modify, access).

• File Operations: create, delete, open, close, read, write, append, seek (lseek), truncate.

• File Types: Regular, Directory, Character special, Block special.

• File Structure:

  • Byte Sequence: (UNIX, Windows) - no structure.

  • Record Sequence: Fixed/variable length records.

  • Tree: Indexed by key (e.g., B-tree).

Directory Structure

• Single-level: All files in one directory. No subdirectories. (Simple, but name collision).

• Two-level: Master directory with user directories. No subdirectories under user dirs. (No file sharing across users).

• Tree-structured: Hierarchical (directories can contain subdirectories). Path names (absolute/relative). (e.g., UNIX, Windows). Most common.

• Acyclic Graph: Directories can have shared subdirectories/files (links). Reference count needed. (e.g., UNIX hard links).

• General Graph: Cycles possible (need garbage collection). Complex.

• Sharing: Same file/directory appears in multiple directories (links).

[!TIP] Exam Focus: Draw and explain Two-level and Acyclic-graph directory structures (Nov 2023).

File System Implementation

• Disk Layout:

  • Boot Control Block: Boot info (first sector, FAT for FAT).

  • Partition Block: Partition info (size, blocks, etc.).

  • Directory Structure: Root directory location.

  • File Control Block (FCB): Contains all file attributes (inode in UNIX, MFT entry in NTFS).

• Virtual File Systems (VFS):

  • Purpose: Provide common interface to different filesystem types (ext4, NTFS, NFS).

  • Key Objects: vnode (in-memory FCB), file (open file description).

  • Switch Table: VFS calls appropriate filesystem-specific functions via function pointers in vnode.

Free Space Management

• Bit Vector (Bitmap): One bit per block. (1=free, 0=allocated). Simple, fast.

• Linked List: Free blocks linked together. (Can waste space storing pointers).

• Grouping: First free block contains addresses of many free blocks.

• Counting: Keep list of (address, count) for contiguous free runs.

File System in Specific OS

• UNIX (UFS/FFS):

  • Inode: Fixed-size structure per file. Contains: mode (type/permissions), link count, owner, size, direct/indirect block pointers (12 direct, 1 single, 1 double, 1 triple), timestamps.

  • Directory: Simple file containing <inode#, filename> pairs.

  • Features: Hard links (multiple dir entries → same inode), special files (device inodes), journaling (in later versions).

• Windows (NTFS):

  • Master File Table (MFT): Array of fixed-size MFT records (like FCB/inode). First 16 records reserved.

  • Attributes: Stored in MFT record or external runs (if large). Standard attributes: $$\displaystyle STANDARD_INFORMATION, $$FILE_NAME, $DATA.

  • Features: Journaling (log file), ACLs (security descriptors), compression, encryption, sparse files, hard links, symbolic links.

• Comparison:

  | Feature | UNIX (UFS) | Windows (NTFS) | | :--- | :--- | :--- | | Metadata Structure | Inode (fixed size) | MFT record (variable, extensible) | | Links | Hard links (inode link count) | Hard links, Symbolic links | | Journaling | Optional (ext3/4, JFS) | Mandatory | | Security | rwx for user/group/others | Full ACLs (permissions, auditing) | | Compression | Not native | Native per-file/directory | | Max File Size | ~2TB (traditional) | 16 EB (theoretical) |

[!TIP] Exam Focus: Compare UNIX & Windows file systems in detail (structure, performance) - highest priority (Jun 2025, Jun 2024, Jun 2023). Know inode structure and MFT.

9. I/O SYSTEMS

I/O Hardware

• Components: I/O device → Controller (electronics) → Port/Bus → CPU.

• Polling vs. Interrupt-Driven I/O:

  • Polling: CPU repeatedly checks device status bit. Wastes CPU cycles.

  • Interrupt-Driven: Device controller signals CPU via interrupt when ready. CPU saves state, jumps to Interrupt Service Routine (ISR).

• Interrupt Handling:

  • Interrupt Vector: Table of ISR addresses indexed by interrupt number.

  • Masking: Disable/enable interrupts (critical sections).

  • Steps: CPU finishes current instruction → pushes PSW/PC → fetches ISR address from vector → executes ISR → returns.

Application I/O Interface

• Block vs. Character Devices:

  • Block: Read/write blocks of data (disks). Random access. Buffered by OS.

  • Character: Read/write streams of bytes (terminals, printers). No random access. Often unbuffered.

• Kernel I/O Subsystem:

  • Services:

    1. Scheduling: Queue I/O requests, prioritize.

    2. Buffering: Store data in memory while in transit (to/from device).

    3. Caching: Keep copies of data in fast memory (disk cache).

    4. Spooling: Overlap I/O of multiple jobs (e.g., printer spooler).

    5. Device Reservation: Grant exclusive access (e.g., tape drive).

    6. Error Handling: Retry, report errors.

  • Structure: Device drivers (kernel modules) → Device-independent I/O module → User I/O interfaces (system calls).

I/O Buffering

• Need: Device speed mismatch, block size differences, support for read()/write() semantics.

• Single Buffer: OS allocates one buffer in memory. Process blocked until I/O completes into buffer, then copies to user space.

• Double Buffer: Two buffers. While process uses one, I/O fills other. Overlaps I/O & compute.

• Circular Buffer: For stream I/O (e.g., terminal). Multiple buffers in ring. Producer/consumer pointers.

• Buffering Strategies:

  • Block Devices: Often use buffer cache (disk cache). Read-ahead, write-behind.

  • Character Devices: Often line-buffered (terminal) or unbuffered.

I/O Operations

• Synchronous (Blocking) I/O:

  • read()/write() call blocks process until I/O completes.

  • Simple programming model.

• Asynchronous (Non-blocking) I/O:

  • aio_read() returns immediately. Process continues. Completion signaled via callback, signal, or aio_error()/aio_return().

  • Overlaps I/O with computation. Better for high-performance servers.

• Comparison:

  | Aspect | Synchronous | Asynchronous | | :--- | :--- | :--- | | Process State | Blocked during I/O | Running during I/O | | Programming | Simple, sequential | Complex, event-driven/callback | | Performance | Lower overlap | Higher overlap, throughput | | Use Case | Simple apps, shells | High-performance servers, GUIs |

I/O Management in Specific OS

• UNIX I/O:

  • System Calls: read, write, lseek, open, close, ioctl, stat, fstat.

  • Device Files: All I/O devices appear as files in /dev. Uniform interface.

  • Streams: STREAMS mechanism for protocol stacks (e.g., TCP/IP).

• Windows I/O:

  • I/O Manager: Kernel component. Uses IRPs (I/O Request Packets).

  • Device Drivers: WDM (Windows Driver Model)/KMDF.

  • Asynchronous I/O: I/O Completion Ports (IOCP) for high-performance scalable I/O (thread pool model).

  • System Calls: Win32 API (ReadFile, WriteFile, DeviceIoControl).

• Comparison: UNIX uses file descriptor abstraction uniformly. Windows uses file handles and explicit async APIs (IOCP). Both support overlapped I/O.

System Calls for File Management

• open(path, flags, mode): Open file, return descriptor.

• close(fd): Close descriptor.

• read(fd, buf, count): Read bytes.

• write(fd, buf, count): Write bytes.

• lseek(fd, offset, whence): Reposition file offset.

• stat(path, &buf): Get file status (inode info).

• ioctl(fd, request, argp): Device-specific control.

• chmod(path, mode): Change permissions.

• unlink(path): Delete file.

[!TIP] Exam Focus: Synchronous vs Asynchronous I/O (Jun 2025, Jun 2024, Dec 2024). Kernel I/O subsystem functions (Jun 2025, Dec 2024). UNIX vs Windows I/O comparison (Jun 2024, Jun 2023).

10. OPERATING SYSTEM TYPES & ADDITIONAL TOPICS

Network OS vs. Traditional OS

Distributed OS vs. Multiprocessor OS

Dynamic Linking and Loading

• Static Linking: Linker copies library code into executable at link-time. Larger executables, no runtime dependency.

• Dynamic Linking:

  • Load-time: Shared library loaded when program starts. Resolved by dynamic linker (ld.so).

  • Run-time: Library loaded on first function call (dlopen()). More flexible.

  • Shared Libraries (.so, .dll): One copy in memory, mapped into multiple processes.

  • Advantages: Saves memory/disk space, easier updates (replace DLL).

Overlays

• Concept: Only keep needed parts of large program in memory. Rest on disk. Program itself loads/overlays modules.

• Use Case: Executing program larger than physical memory (historical, before virtual memory).

• Implementation: Programmer partitions code/data into overlays. Overlay driver (part of program) loads correct overlay from disk.

• Disadvantage: Complex programming, I/O overhead. Superseded by virtual memory/paging.

Security & Protection Mechanisms

• Goals: Confidentiality, Integrity, Availability (CIA triad).

• Mechanisms:

  • Authentication: Verify identity (passwords, biometrics, tokens).

  • Authorization: Define access rights (ACLs, capabilities).

  • Cryptography: Encrypt data (symmetric/asymmetric).

  • Firewalls: Filter network traffic.

• OS-Level Security:

  • UNIX Permissions: rwx for user/group/others (chmod).

  • ACLs: Fine-grained per-user/group permissions (NTFS, POSIX ACLs).

  • Capabilities: Token (capability) granting access to object (uncommon in general OS).

  • Secure Kernels: Mandatory Access Control (SELinux, AppArmor).

[!TIP] Exam Focus: Dynamic linking vs static (Jun 2024). Overlays concept (Jun 2025). Network vs Distributed OS (Jun 2023, Dec 2024). Security mechanisms (Jun 2025).

Final Notes for Exam:

1. Draw Diagrams: Process states, PCB, Gantt charts, RAG, directory structures, paging/segmentation translation.

2. Practice Calculations: CPU scheduling (Gantt, avg WT/TAT), page faults (FIFO/LRU), disk head movement (SSTF/SCAN), Banker's algorithm.

3. Compare & Contrast: ULT vs KLT, paging vs segmentation, contiguous vs linked vs indexed allocation, UNIX vs Windows (memory, file, I/O), synchronous vs async I/O.

4. Definitions: Deadlock conditions, Belady's anomaly, thrashing, working set, critical section, semaphore, monitor.

5. Past Paper Focus: Prioritize topics marked "Highest" in Priority Key.