Operating Systems (AL-501) - Unit 3 Short Notes

UNIT 3: OPERATING SYSTEMS - EXAM-FOCUSED SHORT NOTES

1. OPERATING SYSTEM OVERVIEW & FUNDAMENTALS

Evolution of Operating Systems

• Batch Systems: Jobs grouped by similar requirements; no user interaction. Goal: Maximize CPU utilization.

• Multiprogrammed Systems: Multiple jobs in memory; CPU switches to another when one waits (I/O). Goal: Increase CPU utilization.

• Time-Sharing Systems: CPU time slices (quantum) shared among interactive users. Goal: Quick response (interactivity).

• Distributed Systems: Collection of independent, networked computers appearing as a single system.

• Network OS: Provides file/print sharing across a LAN; each machine has its own OS.

• Real-Time OS (RTOS): Hard (strict deadline) or Soft (deadline important) real-time constraints.

Functions & Services of an OS

Characteristics of an OS

• Concurrency: Multiple tasks in progress (logical).

• Parallelism: Multiple tasks executing simultaneously (physical, requires multi-core).

• Persistence: Data/state survives process termination (stored on disk).

• Virtualization: Presents abstract resources (e.g., virtual CPU, memory).

• Openness: Ability to add new functions/modules.

OS Structures

• Monolithic: All OS components in kernel (single address space). Fast but insecure/unstable.

• Microkernel: Minimal kernel (scheduling, memory, IPC); other services as user-space processes. More secure, stable, but slower IPC.

• Layered: OS organized in layers (0: hardware; N: user interface). Each layer uses only lower layers. Easier to verify, but rigid.

• Modules (Modern): Kernel with loadable modules (e.g., Linux). Flexible.

Exam Tip: Distinguish Concurrency (tasks making progress) from Parallelism (tasks executing at same instant).

2. PROCESS MANAGEMENT

Process vs. Program

• Program: Passive executable code (static).

• Process: Active execution instance of a program (dynamic). Contains: program code, data, stack, PCB.

Process States & PCB

States: New → Ready → Running → Waiting (Blocked) → Terminated.

Process Control Block (PCB): OS data structure storing process context.

• Fields: Process state, PID, PC, CPU registers, memory management info, scheduling info (priority), I/O status, accounting info.

• Significance: Enables context switching, process control, resource tracking.

Scheduling Queues & Schedulers

• 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): Admits jobs from job pool to ready pool (controls degree of multiprogramming).

  • Short-term (CPU): Selects ready process for CPU execution (fast).

  • Medium-term: Swaps processes in/out of main memory (reduces multiprogramming).

CPU Scheduling Algorithms (Calculation Focus)

Key Metrics:

• Turnaround Time (TAT) = Completion Time - Arrival Time

• Waiting Time (WT) = Turnaround Time - Burst Time

• Response Time = First CPU allocation - Arrival Time (for RR)

1. FCFS / FIFO (Non-preemptive)

• Processes execute in order of arrival.

• Gantt Chart: Simple timeline.

• Convoy Effect: Long job delays short jobs.

2. SJF / SRTF (Shortest Remaining Time First) (Preemptive)

• SJF (Non-preemptive): Select process with shortest next CPU burst.

• SRTF (Preemptive): New process with shorter burst than remaining time of current preempts.

• Optimal for minimizing average WT, but requires future knowledge (not practical). Use past bursts as prediction.

3. Priority Scheduling (Can be Preemptive/Non-preemptive)

• Process with highest priority (lowest number) selected.

• Problem: Starvation of low-priority processes. Solution: Aging (gradually increase priority of waiting jobs).

• Tie-breaking: FCFS.

4. Round Robin (RR) (Preemptive)

• Ready queue treated as circular. Each process gets a time quantum (q).

• Context switch occurs if process doesn't finish before q.

• Gantt Chart: Repeated slices.

• Avg WT/TAT: Inversely proportional to q. Too large → FCFS; too small → excessive context switches.

• Calculation: Last finish time of each process = sum of all q's it receives.

Exam Tip: For preemptive algorithms (SRTF, Priority preemptive), always check for new arrivals at each time unit. For non-preemptive, once a process starts, it runs to completion or first I/O wait.

3. THREADS & CONCURRENCY

Thread Fundamentals

• Motivation: Responsiveness (UI), Resource Sharing (memory/files), Economy (cheaper than process), Scalability (parallelism on multi-core).

• Thread vs. Process:

  | Thread | Process | | :--- | :--- | | Lightweight (shares address space) | Heavyweight (separate address space) | | Low creation/switching cost | High creation/switching cost | | Communication easy (shared memory) | Communication complex (IPC) | | Same PID (within process) | Unique PID |

Thread Models

Concurrency & Critical Section

• Real Concurrency: Multiple threads/processes executing simultaneously on different CPUs.

• Virtual Concurrency: Single CPU rapidly switching between tasks.

• Critical Section Problem: Code segment accessing shared resource that must execute atomically.

  • Requirements: Mutual exclusion, Progress, Bounded wait.

Solutions to Critical Section

1. Peterson's Solution (Two Processes)

• Uses two shared arrays: flag[i] (wants to enter), turn (whose turn).

• Algorithm ensures mutual exclusion and progress.

Pitfall: Works only for two processes; requires atomic reads/writes.

2. Semaphores

• Integer variable accessed atomically via two operations:

  • wait(S) / P(S): while (S <= 0); S--;

  • signal(S) / V(S): S++;

• Usage:

  • Binary semaphore (mutex): For mutual exclusion.

  • Counting semaphore: For resource counting (e.g., N identical printers).

  • Solving Producer-Consumer: Use two semaphores: empty (count of empty buffers), full (count of full buffers), and a mutex for buffer access.

3. Monitors

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

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

• Dining Philosophers Solution with Monitor:

  • Each philosopher calls pickup() which checks neighbors. If both forks available, take them; else wait on condition variable.

  • putdown() signals neighbors.

Classic Synchronization Problems

• Producer-Consumer: Bounded buffer. Use semaphores (empty, full, mutex).

• Readers-Writers: Readers can read concurrently; writer needs exclusive access. Priority variants: Reader-preference, Writer-preference.

• Dining Philosophers: Deadlock/starvation possible. Solutions: limit to 4 philosophers, pick up forks in specific order, use arbitrator (waiter).

4. DEADLOCK

Definition & Necessary Conditions (All Must Hold)

1. Mutual Exclusion: Resource non-shareable (e.g., printer).

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.

Example: P1 holds R1, waits for R2; P2 holds R2, waits for R1 → Circular wait.

Handling Methods

1. Prevention: Negate one necessary condition.

2. Avoidance: Allow possibility but ensure system never enters unsafe state.

• Banker's Algorithm (Multiple Instances):

  • Data Structures: Available, Max, Allocation, Need (Need = Max - Allocation).

  • Safety Algorithm: Find a sequence of processes where Need[i] <= Available for each step. If found → Safe state.

  • Resource-Request Algorithm:

    1. Check Request[i] <= Need[i] and Request[i] <= Available.

    2. Pretend allocate (update Available, Allocation, Need).

    3. Run safety check. If safe → grant; else → wait.

  Calculation Steps: Compute Need matrix. Find safe sequence by iteratively finding a process whose Need <= Work (initially Available). Update Work += Allocation of that process.

• Resource Allocation Graph (RAG) Algorithm (Single Instance):

  • Graph with processes (circles) and resources (squares). Edges: Request (P→R), Assignment (R→P).

  • Deadlock if cycle exists. No deadlock if no cycle. Avoidance: Only grant request if resulting graph is acyclic.

3. Detection & Recovery

• Detection (Multiple Instances): Use Wait-for Graph (simplify RAG by collapsing resource nodes). Periodic cycle detection.

• Recovery:

  • Process Termination: Terminate all deadlocked processes or one by one (choose victim based on priority, resources held, etc.).

  • Resource Preemption: Select victim, rollback to safe state (checkpointing), possibly starvation.

4. Ignorance (Ostrich Algorithm): Assume deadlocks rare; let them happen and reboot. Used in many general-purpose OS (e.g., Windows, Linux).

5. 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 binding (virtual memory). Most flexible.

• Logical (Virtual) vs. Physical Address: CPU generates logical; MMU translates to physical.

Contiguous Allocation

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

• Multiple Partition (MVT): Variable-sized partitions. Problems:

  • External Fragmentation: Memory between partitions too small for any process. Solution: Compaction (expensive, requires dynamic relocation).

  • Internal Fragmentation: Wasted space within allocated partition (if partition > process).

Non-Contiguous Allocation

1. Paging

• Divides physical memory into fixed-size frames (power of 2). Logical memory into same-size pages.

• Address Translation: Logical address = [page # | offset]. Physical address = [frame # | offset].

• Page Table: Per-process array mapping page numbers to frame numbers.

  • Structure:

    • Hierarchical: Multi-level page tables (save space for sparse address space).

    • Hashed: For large address spaces.

    • Inverted: One global table with <PID, page> entries. Shared pages handled easily.

• Protection: Valid/Invalid bit in page table entry.

2. Segmentation

• User's view: memory as segments (code, data, stack, heap). Each segment has name, length.

• Segment Table: Per-process. Entry: <base, limit> (physical base address, segment length).

• Address Translation: Logical address = <segment #, offset>. Check offset < limit, then physical = base + offset.

• Advantages over Paging: Better logical view, easier sharing (share entire segment), protection (read/write/execute per segment).

• Disadvantages: External fragmentation (variable-sized segments). Solution: Paged Segmentation (segment → pages → frames).

Virtual Memory & Demand Paging

• Concept: Only keep needed pages in memory. Logical address space > physical.

• Benefits: Larger programs, memory protection, efficient loading, more processes in memory.

• Demand Paging: Page brought into memory only when referenced (on page fault).

  • Valid/Invalid Bit: valid → in memory; invalid → not in memory (or illegal).

  • Page Fault Handling Steps:

    1. Trap to OS, save process state.

    2. Check if reference legal (within segment limit).

    3. Find free frame (if none, use page replacement).

    4. Schedule disk I/O to read page into frame.

    5. Update page table (set valid bit, record frame).

    6. Restart instruction that caused fault.

• Pure Demand Paging: Start with no pages in memory; first instruction causes page fault.

Page Replacement Algorithms (Calculation Focus)

• Reference String: Sequence of page numbers referenced.

• Frames: Fixed number of physical frames.

• Goal: Minimize page fault rate.

Exam Calculation Tip: For LRU, maintain a stack/queue of page references; on hit, move page to top (most recent). On fault, replace page at bottom. For FIFO, simple queue.

Belady's Anomaly: Counterintuitive increase in page faults when increasing number of frames. Occurs in FIFO (and some others), not in LRU or OPT. Example: Ref string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. 3 frames: 9 faults; 4 frames: 10 faults.

Frame Allocation

• Fixed Allocation: Equal allocation (each process gets same number) or proportional (based on size).

• Variable Allocation: Number of frames changes as process runs (e.g., working set model).

• Page Fault Frequency (PFF): Monitor fault rate; allocate more frames if rate high, reclaim if low.

Memory Management in UNIX & Windows

• UNIX:

  • fork(): Creates child with copy of parent's address space (copy-on-write).

  • exec(): Overlays child's memory with new program (demand paged).

  • Swap Space: Disk area for swapped-out pages (separate from file system).

• Windows:

  • Virtual Address Space: 4GB (2GB user, 2GB kernel by default).

  • Paging File (pagefile.sys): Stores modified pages. Size configurable.

  • Working Set: Set of pages a process has in physical memory. OS adjusts working set size.

6. STORAGE MANAGEMENT: FILE SYSTEMS

File Concept

• Attributes: Name, identifier, type, location, size, protection, time/date/user ID.

• Operations: create, delete, open, close, read, write, seek, get/set attributes.

• Types: Regular, Directory, Special (device).

• Structure: Byte sequence (UNIX), record sequence (legacy), tree (Windows).

Access Methods

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

• Direct (Random): seek to position based on record number.

• Indexed: Build index for each file; index read first, then data via pointers.

Directory Structure

Disk Space Allocation Methods (Calculation Focus)

Calculation Tip: For linked allocation, to find block k, must traverse k pointers. For indexed, direct access via index block.

File System Implementation

Layers:

1. I/O Control: Device drivers, interrupt handlers.

2. Basic File System: Block allocation, buffering.

3. File Organization Module: Files, directories, paths, protection.

4. Logical File System: Metadata (inode/MFT), operations.

Virtual File System (VFS): Interface layer providing common operations (open, read, write) for different file systems (ext4, NTFS, NFS). Uses vnode (virtual inode) object.

UNIX vs Windows File Systems

7. STORAGE MANAGEMENT: DISK SCHEDULING & PERFORMANCE

Disk Structure & Performance

• Tracks: concentric circles on platter.

• Sectors: arc segments on track (typically 512B-4KB).

• Cylinder: Set of tracks aligned vertically across platters.

• Access Time = Seek Time (move head to cylinder) + Rotational Latency (wait for sector to rotate under head) + Transfer Time (read/write sector).

• Transfer Rate = Sectors per rotation / rotation time.

Disk Scheduling Algorithms (Calculation Focus)

• Input: Queue of cylinder requests, current head position, direction (for SCAN).

• Goal: Minimize total head movement (seek time).

• Assumption: All requests are for reading/writing data blocks.

1. FCFS (First-Come-First-Served)

• Service in arrival order.

• Total Movement: Sum of absolute differences between consecutive requests (including from current position).

2. SSTF (Shortest Seek Time First)

• Select request closest to current head position.

• Greedy, not fair (can starve distant requests). Total movement usually less than FCFS.

3. SCAN (Elevator)

• Head moves in one direction (say, increasing cylinder) servicing requests until end, then reverses.

• Total Movement: Move to farthest request in direction, then to farthest in opposite direction, etc.

4. C-SCAN (Circular SCAN)

• Head moves in one direction (e.g., increasing), services all requests, then jumps to lowest cylinder (without servicing) and repeats.

• More uniform wait time than SCAN.

• Total Movement: Move from current to highest request, then jump to lowest, then to highest, etc.

5. LOOK / C-LOOK

• Like SCAN/C-SCAN but head only goes as far as last request in direction, then reverses/jumps.

Example Calculation (FCFS): Head at 143, requests: 86, 147, 91, 177, 94, 150, 102, 175, 130.

Movement: |143-86|=57 + |86-147|=61 + |147-91|=56 + |91-177|=86 + |177-94|=83 + |94-150|=56 + |150-102|=48 + |102-175|=73 + |175-130|=45 = 567 tracks.

Disk Management

• Formatting: Low-level (sectors/tracks), partition creation, high-level (file system).

• Boot Block: Initial program (bootstrap) stored in first sector.

• Bad Blocks: Marked during formatting or via badblocks utility; remapped to spare sectors.

• Attachment: Host-attached (SATA, SCSI), Network-attached (NAS, SAN).

• Mounting: Making file system accessible.

  • Manual: mount command.

  • Automatic: OS mounts at boot (e.g., /etc/fstab).

  • Remote: NFS, SMB (network file systems).

Tape Organization

• Sequential Access: Must wind through tape to reach point. No random access.

• Structure: Tracks parallel to tape length. Reel-to-reel vs. Cartridge (tape drive).

• Use: Backup, archival (high capacity, low cost per GB, slow access).

8. I/O SYSTEMS

I/O Hardware

• Components: I/O device (printer, disk), controller (interface), bus (data pathway).

• Polling vs. Interrupt-Driven:

  • Polling: CPU repeatedly checks device status register (busy-wait). Wastes CPU cycles.

  • Interrupt-Driven:

    1. Device controller signals interrupt when ready.

    2. CPU saves context, jumps to interrupt handler (ISR) via interrupt vector.

    3. ISR services device (may block for slow I/O).

    4. CPU resumes interrupted process.

  • Modern: Interrupts for completion, DMA (Direct Memory Access) for large transfers (controller moves data between device & memory without CPU).

Application I/O Interface

Kernel I/O Subsystem

Functions:

1. Scheduling: Queue I/O requests (e.g., disk scheduling).

2. Buffering: Store data temporarily (e.g., keyboard input buffer, disk cache).

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

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

5. Device Reservation: Exclusive access (e.g., flock).

6. Error Handling: Retry, report to user.

I/O Buffering

• Need: Match speed differences between producer/consumer, block vs. stream devices.

• Types:

  • Single Buffer: Producer fills buffer, consumer empties. Stop-and-go between buffer fill/empty.

  • Double Buffer: Two buffers; while one consumed, other filled. Overlap possible.

  • Circular Buffer: Multiple buffers in ring. Producer/consumer pointers. Continuous flow (e.g., audio).

• Strategies:

  • Block Devices (disk): Read-ahead (prefetch), write-behind (delayed write).

  • Stream Devices (keyboard/mouse): Line discipline, editing.

I/O Management in UNIX & Windows

• UNIX:

  • Character I/O: Unbuffered, byte-by-byte (e.g., terminal). read/write.

  • Block I/O: Buffered, block-oriented (e.g., disk). bread/bwrite.

  • ioctl: Device-specific control (e.g., set terminal mode).

  • lseek: Reposition file offset.

• Windows:

  • I/O Manager: Routes I/O requests.

  • IRP (I/O Request Packet): Kernel object representing I/O request. Passed through driver stack.

  • Asynchronous I/O: Overlapped I/O, completion ports (efficient for many concurrent I/O).

System Calls for File Management

Transforming I/O Requests to Hardware Operations

1. Application: Calls write(fd, buf, n).

2. System Call: Trap to kernel, validate fd/buffer.

3. VFS: Determines file system type, calls appropriate FS write.

4. File System: Converts to logical blocks, checks cache, may schedule I/O.

5. Buffer Cache: If cache hit, copy to cache; if miss, allocate buffer, mark dirty.

6. Block I/O Layer: Creates bio (block I/O) structure, passes to block device driver.

7. Device Driver: Translates to device commands (e.g., SATA), may use DMA.

8. Device Controller: Executes command, interrupts on completion.

9. Interrupt Handler: Marks I/O complete, wakes waiting process, writes back to cache if dirty.

9. PROTECTION & SECURITY

Goals

• Protection: Control access of processes/users to resources (confidentiality, integrity).

• Security: Defend system against external attacks (authentication, authorization, auditing).

Protection Mechanisms

• Access Control:

  • Capability List: Per-process list of objects & permitted operations (like "tickets"). Secure but hard to revoke.

  • Access Control List (ACL): Per-object list of users/processes & permissions (rwx). Flexible, common (e.g., chmod). Revocation easy.

• Language-Based Protection: Compiler enforces security policies (e.g., Java sandbox, type safety).

Security Mechanisms

• Cryptography:

  • Symmetric: Same key for encrypt/decrypt (AES). Fast, key distribution problem.

  • Asymmetric: Public/private key pair (RSA). Slower, solves distribution.

  • Digital Signature: Hash of message encrypted with sender's private key. Provides authentication, non-repudiation.

• Authentication:

  • Passwords: Weak (dictionary attacks).

  • Multifactor: Something you know (password), have (token), are (biometric).

• Intrusion Detection/Prevention: IDS/IPS monitors for suspicious activity (signature-based, anomaly-based).

UNIX vs Windows Security

10. ADVANCED & SPECIAL TOPICS

Overlays

• Concept: Load only necessary parts of large program into memory; overlay manager loads new overlay when needed.

• Utility: Allows execution of programs larger than physical memory. Manual (programmer defines overlays). Superseded by virtual memory.

Dynamic Linking and Loading

Distributed vs. Multiprocessor OS

Network Operating Systems

• Characteristics: File/print sharing, user/group management, remote login (Rlogin, SSH), distributed processing.

• vs Traditional OS: Emphasizes network transparency, remote resource access, client-server model. Less focus on single-system performance.

Concurrent I/O

• Multiple I/O operations in progress simultaneously (overlapped).

• Enabled by asynchronous I/O, interrupts, DMA.

• Example: Process issues read A, then read B without waiting for A to complete.

Final Exam Strategy:

1. Calculation Problems: Always show Gantt chart and step-by-step table (Process, Burst, Start, Finish, TAT, WT). Box final averages.

2. Banker's Algorithm: Explicitly compute Need matrix first. Show Work and Finish arrays in safety check.

3. Page Replacement: Draw frame table for each step. Mark hits/faults clearly.

4. Disk Scheduling: Draw head movement line diagram (tracks vs. time). List movement sequence.

5. Diagrams: Draw neat state diagrams, PCB fields, RAG, file system structures.

6. Comparisons: Use tables for UNIX/Windows, User/Kernel threads, Allocation methods.

7. Definitions: Start answers with clear, boxed definitions.