UNIT 3: OPERATING SYSTEMS - EXAM-FOCUSED SHORT NOTES

I. INTRODUCTION & FUNDAMENTALS

Evolution of Operating Systems

• Generations & Driving Forces:

  1. Batch: No interaction, offline job scheduling (punched cards). Goal: Maximize CPU utilization.

  2. Multiprogrammed: Multiple jobs in memory. CPU switches when one waits (I/O). Goal: Increase CPU utilization.

  3. Time-Sharing: Interactive, multi-user via terminals. CPU switches rapidly (time quantum). Goal: Response time.

  4. Personal/PC: Single-user, GUI focus (MS-DOS, early Mac OS).

  5. Network: File/print sharing across LANs.

  6. Distributed: Loosely coupled systems, resource sharing, single system image.

  7. Real-Time (RTOS): Strict timing constraints (Hard: life-critical; Soft: quality-of-service).

  8. Mobile: Touch interface, power management, app ecosystem (iOS, Android).

Functions & Services of an OS

Characteristics of an OS

• Convenience: Abstraction for users.

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

• Evolvability: Easy to add new functions/modules.

• Fault Tolerance: Handle hardware/software failures gracefully.

• Security/Protection: Control access to resources.

• Portability: Run across different hardware.

OS Structure & Design

• Layered Approach: OS in layers (hardware at bottom, UI at top). Each layer uses services of layer below. Advantage: Easier to debug/modify. Disadvantage: Performance overhead.

• Microkernels: Minimal kernel (only essential services: IPC, memory management, scheduling). Other services (file system, drivers) run in user space as servers. Advantage: Extensibility, reliability, portability. Example: Mach.

• Modules: Loadable kernel modules (e.g., device drivers). More flexible than layered.

• Virtual Machines: Hypervisor (VMM) provides interface identical to underlying hardware. Allows multiple OS instances. Example: VMware, VirtualBox.

• Process-Based Kernel: Kernel represented as a set of processes (often a single process). Advantage: Simpler to design/debug; uses standard IPC.

System Calls & API

• System Call: Controlled entry point into kernel. Interface between user program and OS services.

• Categories:

  1. Process Control: fork(), exec(), wait(), exit(), kill().

  2. File Management: open(), read(), write(), close(), lseek(), stat(), ioctl().

  3. Device Management: ioctl(), read(), write() (for device files).

  4. Information Maintenance: time(), getpid(), alarm().

  5. Communication: pipe(), shmget(), msgget(), socket().

• API (Application Programming Interface): Library functions (e.g., C library) that wrap system calls. POSIX API is standard for UNIX/Linux.

OS Security & Protection

• Goals: Confidentiality (no unauthorized read), Integrity (no unauthorized modify), Availability (service accessible).

• Protection: Mechanisms to control access to resources (within the system). Methods: Access Control Lists (ACLs), Capabilities, Passwords, Encryption.

• Security: Broader, protects system from external threats. Methods: Authentication (passwords, biometrics, tokens), Authorization, Intrusion Detection, Antivirus.

• Key Distinction: Protection is about internal policy enforcement; Security is about external threat defense.

Utility Programs

• Program Status (ps, top), File Management (cp, mv, rm), System Status (df, free), File Content (cat, more), Compilers/Linkers (gcc, ld).

II. PROCESS MANAGEMENT

Process Concept

• Process vs Program: Program is passive (code on disk). Process is active (program in execution + resources). One program can create many processes.

• Process State:

  
  New → Ready → Running → Waiting → Terminated
  
         ↑________←________|
  
  

  • New: Being created.

  • Ready: In main memory, waiting for CPU.

  • Running: Executing on CPU.

  • Waiting: Blocked (I/O, event).

  • Terminated: Finished.

• Process Control Block (PCB): OS data structure per process. Key Fields: Process State, PID, Program Counter, CPU Registers, CPU Scheduling Info, Memory Management Info, I/O Status Info, Accounting Info.

Process Scheduling

• Scheduling Queues:

  • Job Queue: All processes in system (on disk).

  • Ready Queue: Processes in main memory, ready/ready.

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

• Schedulers:

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

  • Mid-term (Swapper): Swaps processes in/out of main memory (to control memory load, introduce suspension).

  • Short-term (CPU Scheduler): Selects process from ready queue to run on CPU (very frequent, executes on interrupt/clock tick).

• Context Switch: Saving state of running process (into its PCB) and loading state of next process (from its PCB). Overhead: Pure CPU time for switching.

CPU Scheduling Algorithms (Preemptive vs Non-Preemptive)

[!TIP] Exam Tip: Always draw Gantt chart. Calculate Turnaround Time (TAT) = Completion Time - Arrival Time and Waiting Time (WT) = TAT - Burst Time. Avg. WT/TAT = Sum / No. of processes.

Threads

• Thread vs Process: Thread is a lightweight process within same process. Shares address space, global variables, files but has own stack, PC, registers, TCB. Process creation is heavy (new address space); thread creation is light.

• Benefits: Responsiveness (concurrency), Economy (less overhead), Utilization (better CPU use on multi-core), Scalability (parallelism on MP systems).

• User-Level vs Kernel-Level Threads:

Interprocess Communication (IPC)

• Shared Memory: Processes share a region of memory. Fastest IPC. Issues: Synchronization (need semaphores/monitors), Memory protection.

• Message Passing: Processes exchange messages via kernel.

  • Direct: Process names receiver explicitly (e.g., send(P2, msg)).

  • Indirect: Messages sent to/received from a mailbox/port (e.g., POSIX messages, Mach ports).

  • Synchronous: Sender blocks until message received.

  • Asynchronous: Sender sends and continues.

  • Buffering: Kernel may buffer messages (0 capacity, bounded, unbounded).

Synchronization

• Critical Section Problem: Code segment accessing shared resource. Requirements: Mutual Exclusion, Progress, Bounded Wait.

• Peterson's Solution (2 processes): Uses two shared arrays (flag[2]) and turn. Software solution, but not practical for >2 processes.

• Semaphore: Integer variable with atomic wait() (P) and signal() (V) operations.

  • Binary Semaphore (Mutex): 0/1. For mutual exclusion.

  • Counting Semaphore: Any integer. For resource counting.

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

  [!TIP] Common Pitfall: wait()/signal() must be atomic (uninterruptible). Busy waiting wastes CPU.

• Monitor: High-level construct. Condition Variables for waiting: wait(c) (release lock & block), signal(c) (wake one waiting thread). Only one process active in monitor at a time.

• Dining Philosophers Problem: 5 philosophers, 5 forks (chopsticks). Need 2 forks to eat. Solution (Semaphores): One mutex for table access, one semaphore[5] per fork. Prevent deadlock/starvation.

Deadlocks

• Definition: Set of processes are in deadlock if each process waits for an event that can only be caused by another process in the set.

• Necessary Conditions (MUST hold simultaneously):

  1. Mutual Exclusion: Resource non-shareable.

  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: Cycle of processes, each waiting for resource held by next.

• Handling Methods:

  1. Prevention: Ensure at least one condition never holds.

     • Attack Hold & Wait: Request all resources at start, or release all before requesting new.

     • Attack Circular Wait: Impose total ordering on resource types, request in increasing order.

  2. Avoidance: Dynamically check if request leads to unsafe state. Banker's Algorithm (see below).

  3. Detection & Recovery: Allow deadlocks, detect periodically (Resource Allocation Graph, Wait-for Graph), then recover (process termination/resource preemption).

  4. Ignorance (Ostrich Algorithm): Pretend deadlocks never occur (used in many general OS like Windows/Linux).

[!TIP] Banker's Algorithm (Safety & Resource-Request)

Safety Algorithm: Checks if system is in safe state (exists a sequence where all processes can finish).

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, go to 2.

4. If all Finish[i]==true → SAFE.

Resource-Request Algorithm: For process Pi's request Request[i].

1. If Request[i] > Need[i] → Error (exceed max claim).

2. If Request[i] <= Available → proceed; else Pi waits.

3. Pretend allocation: Available -= Request[i], Allocation[i] += Request[i], Need[i] -= Request[i].

4. Run Safety Algorithm. If safe → grant; else, restore state & wait.

III. MEMORY MANAGEMENT

Background

• Binding: When addresses are bound to memory.

  • Compile-time: Absolute code (not flexible).

  • Load-time: Relocatable code (compiler generates relocatable addresses).

  • Execution-time (Dynamic): Hardware support (MMU) needed. Most modern OS use this.

• Logical vs Physical Address Space: Logical (CPU-generated) vs Physical (seen by memory unit). MMU translates at runtime.

• Dynamic Loading: Load routine only when called (saves memory). No OS support needed.

• Dynamic Linking: Linking postponed until load/execution time. Uses shared libraries (.so, .dll).

• Overlays: Load only necessary parts of a large program into memory. Manual by programmer. Used in systems without virtual memory.

Memory Allocation Strategies

• Contiguous Allocation:

  • Fixed Partitioning: Memory divided into fixed-size partitions. Internal Fragmentation: Wasted space within partition.

  • Variable Partitioning: Partition size = process size. External Fragmentation: Small free holes between allocated partitions.

• Compaction: Shuffle allocated processes to gather all free memory into one block. Expensive (requires dynamic relocation support).

Paging

• Concept: Divide physical memory into frames (fixed size, power of 2). Divide logical memory into pages (same size as frames). Page Table maps page number → frame number.

  • Logical Address = [Page #, Offset]

  • Physical Address = [Frame #, Offset]

• Protection: Valid-Invalid bit in page table entry. Valid = page in process's address space.

• Page Table Structures:

  • Hierarchical: Multi-level page tables (e.g., 2-level for 32-bit). Reduces memory for sparse tables.

  • Hashed: Hash page # to table entry (good for large address spaces).

  • Inverted: One entry per physical frame, contains (virtual page, process ID). Used for shared memory.

• Translation Lookaside Buffer (TLB): Cache of recent page table entries (associative memory). Hit ratio (α) crucial. Effective Access Time (EAT):

$$ \text{EAT} = (1 - \alpha) \times (\text{Memory Access} + \text{Page Table Access} + \text{Memory Access}) + \alpha \times (\text{Memory Access}) $$

$$ \text{EAT} = (2 + \alpha) \times \text{Memory Access Time} $$

Segmentation

• Concept: Divide logical address space into segments (logical units: code, data, stack). Each segment has a number and offset.

• Segment Table: Entry contains segment base (physical start) and segment limit (length).

• Segmentation with Paging (Paged Segmentation): Each segment is paged (e.g., Intel x86). Combines benefits: protection, sharing (segments), no external fragmentation (paging).

• Advantages over Paging: Logical view (programmer sees segments), sharing (share entire segment), protection (segment-level R/W/X).

Virtual Memory & Demand Paging

• Demand Paging: Bring page into memory only when needed (on page fault). Valid-Invalid bit indicates if page is in memory.

• Page Fault: Access to page not in memory → trap to OS → OS finds free frame (or evicts), reads page from disk (swap space), updates page table, restarts instruction.

• Page Fault Service Time: Page Fault Rate (p) → Effective Access Time:

$$ \text{EAT} = (1 - p) \times \text{Memory Access} + p \times \text{Page Fault Service Time} $$

Page Fault Service Time ≈ **disk access** (dominant).

• Belady's Anomaly: For FIFO page replacement, increasing frames can increase page faults. Occurs due to FIFO's non-stack property. Does not occur in OPT or LRU (stack algorithms).

Page Replacement Algorithms (Assume n frames, reference string)

[!TIP] Exam Must: Calculate page faults for given reference string and frames. Draw frames after each reference.

Thrashing

• Definition: Processes spend most time paging (page faults) rather than executing. CPU utilization drops.

• Cause: Degree of multiprogramming too high → each process has too few frames → high page fault rate → OS spends time swapping.

• Detection: Monitor CPU utilization vs. Page Fault Rate. Low CPU + high PFR → thrashing.

• Elimination:

  • Working Set Model: Each process needs a certain number of frames (working set size) to run efficiently. OS ensures sum of working sets ≤ total frames.

  • Page Fault Frequency (PFF): Directly control PFR by adjusting frames per process.

Memory Management in UNIX & Windows

• UNIX:

  • Uses demand paging with LRU approximation (clock algorithm).

  • Swap Space: Disk area for swapped-out pages (can be partition or file).

  • Memory-mapped files: File I/O via paging.

• Windows (NT/XP/10):

  • Virtual Address Space: 2GB user / 2GB kernel (32-bit); 128TB user (64-bit).

  • Paging: Uses modified clock algorithm (similar to second-chance).

  • Page File: pagefile.sys (usually on C:). Size configurable.

IV. INPUT/OUTPUT (I/O) SYSTEMS

I/O Hardware

• Components: I/O Device → Controller → Bus → CPU/Memory.

• DMA (Direct Memory Access): Controller transfers data directly between device and memory without CPU intervention. CPU only sets up DMA (address, count, direction) and gets interrupt on completion. Reduces CPU overhead for large transfers.

Logical Structure of I/O Function

Application → I/O System Interface → Device Drivers → Interrupt Handlers → Hardware

1. Application: read(), write().

2. Device-Independent Software: Uniform interface, buffering, caching, error handling.

3. Device Drivers: Kernel modules specific to each device (translate generic requests to device-specific ops).

4. Interrupt Handlers: Service device interrupts.

5. Hardware: Actual device/controller.

Kernel I/O Subsystem Functions

• Scheduling: Order I/O requests (e.g., disk scheduling).

• Buffering: Copy data to/from temporary memory (kernel buffer) to match device speed or unit transfer.

• Caching: Keep copies of data in faster memory (e.g., disk cache in RAM).

• Spooling: Hold output for a slow device (e.g., printer) on disk; multiple processes can output simultaneously.

• Device Allocation: Allocate devices (claim, allocate, deallocate).

• Error Handling: Many errors are device-specific; drivers handle them.

Synchronous vs Asynchronous I/O

I/O Buffering

• Single Buffer: OS allocates one buffer in kernel space. Process blocked until I/O completes into buffer, then copies to user space. Double Buffer: Two buffers; while one fills, process uses other. Circular Buffer (Buffer Pool): Multiple buffers in ring. Producer/consumer can run concurrently.

[!TIP] Buffering Purpose: Match speed differences, unit transfer mismatch, support copy semantics.

Disk Management

• Disk Structure: Platters → Tracks → Sectors (with gaps). Cylinder: Same track on all platters.

• Timing Parameters:

  • Seek Time (Ts): Move head to track. Dominant.

  • Rotational Latency (Tr): Wait for sector to rotate under head. Avg = ½ rotation time.

  • Transfer Time (Tt): Read/write sector. Tt = (sector size) / (rotation rate).

  • Access Time = Ts + Tr + Tt.

• Disk Scheduling Algorithms (Goal: Minimize average seek time)

  • FCFS: Simple, fair, but high seek.

  • SSTF: Select closest request to head. Starvation possible for far requests.

  • SCAN (Elevator): Head moves in one direction servicing requests until end, then reverses. Fair.

  • C-SCAN: Head moves in one direction, services requests. When reaches end, jumps to beginning (no service on return). 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.

  [!TIP] Calculation: Sum absolute differences between consecutive requests (including head start position).

I/O Management in UNIX & Windows

• UNIX:

  • Device Files: /dev/ entries. read()/write() on device files invoke drivers.

  • ioctl(): Device-specific control operations.

• Windows:

  • I/O Manager: Central kernel component.

  • Device Drivers: WDM (Windows Driver Model).

  • Asynchronous I/O: Native support via I/O Request Packets (IRPs) and completion ports.

V. FILE SYSTEMS

File Concept

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

• Operations: create, delete, open, close, read, write, reposition (lseek), truncate.

• Types: Ordinary, Directory, Special (block/character device).

• Structure: Byte sequence (UNIX), Record sequence (fixed/variable), Tree (directories).

Access Methods

• Sequential: Read next record (e.g., tape).

• Direct (Random): seek to record i, then read.

• Indexed: Build index for each file (pointers to blocks). Allows direct access without sequential scan.

Directory Structure

• Single-Level: All files in one directory. Problem: Naming conflict.

• Two-Level: User directory + master directory (with UFDs). Problem: No subdirectories.

• Tree-Structured: Hierarchical (directories contain subdirectories). Unique path from root.

• Acyclic-Graph: Allow shared files/directories (links). Multiple parent paths. Problem: Cycles? (Must be acyclic). Need reference counts to delete.

• General Graph: Cycles allowed. Need garbage collection to reclaim unreachable shared files.

Virtual File System (VFS)

• Purpose: Provide common interface to multiple file system types (ext4, NTFS, NFS). Allows transparent remote file access.

• VFS Objects:

  • Vnode (Virtual inode): Represents a file/directory (in-memory). Unique per file system.

  • File: Represents an open file (per-process).

  • Inode: On-disk structure (UNIX-specific). Contains metadata + data block pointers.

• Structure: VFS defines operations (open, read, write). Each file system provides its own inode operations and file operations tables.

File System Implementation

• Disk Space Allocation:

  | Method | How | Advantages | Disadvantages | | :--- | :--- | :--- | :--- | | Contiguous | File in contiguous blocks. | Fast sequential/direct access. | External fragmentation, file growth hard. | | Linked | Each block has pointer to next. | No external fragmentation, files can grow. | Slow direct access, pointer overhead, reliability (lost pointer). | | FAT (Linked variant) | All pointers in single table at start. | Fast table lookup, no external fragmentation. | Table in memory? (large disks), still sequential for direct. | | Indexed | Index block contains pointers to data blocks. | Fast direct access, no external fragmentation. | Small files waste index space, large files need multi-level/indexed. |

• Free-Space Management:

  • Bit Vector (Bitmap): 1 bit per block. 1=free, 0=allocated. Compact, easy to find contiguous free space.

  • Linked List: Free blocks linked together. Grouping: Store addresses of many free blocks in one free block. Counting: Keep (address, count) for contiguous runs.

• Directory Implementation:

  • Linear List: Simple, slow search (O(n)).

  • Hash Table: Fast search (O(1) avg), collisions, fixed size.

File System in UNIX & Windows

[!TIP] Comparison Key: UNIX uses inode-based with simple permissions; NTFS uses MFT-based with rich ACLs and B-trees.

File Protection & Security

• Access Control:

  • ACL (Access Control List): Per-file list of (user/group, permissions). Flexible.

  • Capabilities: Token (capability) that grants access to object. Secure (hard to forge).

  • Password: Basic.

• Other Methods: Encryption (file-level), Traps (honeyfiles), Code signing.

VI. SPECIAL TOPICS & COMPARISONS

Multiprocessor vs Distributed OS

Real-Time OS (RTOS) Scheduling

• Hard Real-Time: Must meet deadline (e.g., flight control). Preemptive, priority-based (often Rate-Monotonic for periodic tasks: shorter period → higher priority).

• Soft Real-Time: Desirable to meet deadline (e.g., video streaming). Can miss occasionally.

Tape Organization

• Structure: Sequential access. Tracks (parallel), Blocks (records + gaps), Gaps for start/stop.

• Tape Drive: Moving head? No, tape moves. Reel-to-reel or cartridge (DAT, LTO).

• Use: Backup/archive (high capacity, low cost, slow random access). Not for primary storage.

Miscellaneous High-Frequency Topics

• Overlay: Load only required program parts into memory. Manual by programmer (divide program into overlay modules). Used when virtual memory unavailable and program > memory.

• Spooling (Simultaneous Peripheral Operations On-Line): Buffer output for slow device (printer) on disk. Allows multiple processes to "print" simultaneously. Input spooling also exists (e.g., reading cards to disk).

• System Boot:

  1. Bootstrap: ROM code loads bootloader from disk (MBR/GPT).

  2. Bootloader: Loads kernel image into memory, jumps to kernel entry.

  3. Kernel: Initializes hardware, mounts root FS, starts init/systemd.

END OF UNIT 3 NOTES

Focus practice on: SJF/Priority calculations, Banker's algorithm steps, Page Replacement (FIFO/LRU) with examples, Disk Scheduling (SSTF/SCAN/C-SCAN) head movement, File Allocation (Contiguous/Linked/Indexed) diagrams, UNIX vs Windows File System comparison table.