UNIT 5: OPERATING SYSTEMS - COMPREHENSIVE NOTES

Based on rigorous analysis of RGPV past papers (2022-2025), these notes prioritize exam-critical concepts using a schematic, definition-first approach.

I. FOUNDATIONS & OVERVIEW

Evolution of Operating Systems

Impact: Each generation drove hardware development (e.g., time-sharing → terminals, multiprocessing → multi-core CPUs).

Operating System Services

User Services:

1. Program Execution: Load & run (system calls: fork, exec).

2. I/O Operations: Hide device specifics (system calls: read, write).

3. File System Manipulation: Create, delete, access files.

4. Communication: IPC (pipes, shared memory, sockets).

5. Error Detection: Protect hardware & data.

System Services:

1. Resource Allocation: Scheduler, memory manager.

2. Accounting: Track resource usage (CPU time, I/O).

3. Protection & Security: Access control, authentication.

OS Structure: Monolithic vs. Microkernel

Process-Based Kernel: OS services implemented as server processes communicating via IPC. Enhances modularity & fault isolation.

II. PROCESS MANAGEMENT

Process States & PCB

Five-State Model:

New → Ready → Running → Waiting → Terminated

         ↑         ↓

         └─ Medium-term Scheduler (Swapping) ─┘

Process Control Block (PCB): OS's per-process data structure.

• Fields: Process state, PID, program counter, CPU registers, memory management info, I/O status, accounting info.

• Significance: Enables context switch (saving/restoring state).

CPU Scheduling Algorithms (VERY HIGH FREQUENCY)

Key Criteria:

• CPU Utilization: % time CPU busy.

• Throughput: # processes completed / unit time.

• Turnaround Time: Submission → Completion.

• Waiting Time: Time in Ready queue.

• Response Time: First response to request.

Non-Preemptive:

1. FCFS/FIFO: "First Come First Served". Simple, causes convoy effect.

2. SJF (Shortest Job First): Minimizes avg. waiting time. Requires knowledge of burst time.

   • Gantt Chart Example: P1(10), P2(1), P3(2) → | P2 | P3 | P1 |

   • Avg. WT = (0 + 0 + 10)/3 = 3.33 ms.

3. Priority Scheduling: Lower number = higher priority. Can cause starvation → solved by aging (gradually increasing priority of waiting jobs).

Preemptive:

1. SRTF (Shortest Remaining Time First): Preemptive SJF.

2. Round Robin (RR): Time quantum (q). Cyclically executes each ready process for ≤ q.

   • Gantt Chart: q=4, P1(10), P2(1), P3(2) → | P1 | P2 | P3 | P1 | P1 | P1 |

   • Avg. WT depends heavily on q (too small → overhead, too large → FCFS).

Multi-level Queue: Ready queue partitioned (e.g., System, Interactive, Batch). Fixed priority between queues. Multi-level Feedback Queue (MLFQ): Multiple queues with different time quanta. Processes move between queues based on behavior (e.g., CPU-bound → lower priority queue).

Threads: User-Level vs. Kernel-Level

Exam Tip: M:1 model (many user threads to 1 kernel thread) is not used in modern general-purpose OS due to blocking issue.

Synchronization: Semaphores & Monitors

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

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

• Binary Semaphore (0/1): Mutual exclusion.

• Counting Semaphore: Counting resources.

// Binary semaphore for mutual exclusion

semaphore mutex = 1;

wait(mutex);

// Critical Section

signal(mutex);

Monitor: High-level construct. Only one process active in monitor at a time. Uses condition variables (wait(), signal()) for blocking.

• Example: Dining Philosophers solution using monitor avoids deadlock by limiting concurrent philosophers to 4.

Classical Problems:

1. Bounded-Buffer (Producer-Consumer): Use two semaphores (empty, full) and one mutex.

2. Readers-Writers: Prioritize readers (no writers) or writers (no readers).

3. Dining Philosophers: Solution requires preventing circular wait (e.g., odd/even pick-up order).

III. DEADLOCKS

Necessary Conditions (MUST ALL HOLD)

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

2. Hold and Wait: Process holds resource while waiting for another.

3. No Preemption: Resource released only voluntarily.

4. Circular Wait: Cycle of processes waiting for each other's resources.

   
   P0 → R0 → P1 → R1 → P2 → R2 → P0
   
   

Handling Methods

Banker's Algorithm (Avoidance):

• Safety Algorithm: Finds if system is in safe state (exists safe sequence).

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

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

  3. Work = Work + Allocation[i], Finish[i]=true, repeat.

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

• Resource-Request Algorithm: Checks if request ≤ Need & Available. If yes, pretend allocate & run safety check.

Example: Given Available=(1,5,2,0), Need matrix from Max - Allocation. Safe sequence found? Yes → P0, P3, P4, P1, P2.

IV. MEMORY MANAGEMENT

Contiguous Allocation

• Fragmentation:

  • Internal: Wasted space within allocated partition (e.g., fixed partition).

  • External: Wasted space between partitions (small holes).

• Placement Strategies:

  | Algorithm | How it works | Pros | Cons | | :--- | :--- | :--- | :--- | | First-fit | Allocates first hole ≥ size | Fast | Fragmentation | | Best-fit | Allocates smallest hole ≥ size | Minimizes leftover | Slow, causes many small holes | | Worst-fit | Allocates largest hole | Produces large leftover | Slow, high fragmentation |

Paging

• Mechanism: Divide physical memory into frames, logical memory into pages. Page table maps page# → frame#.

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

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

• Protection: Valid/Invalid bit in page table.

• Sharing: Same physical frame mapped by multiple page tables.

Segmentation

• Mechanism: Memory viewed as collection of segments (code, data, stack). Each has segment# & offset.

• Segment Table: Base address & limit for each segment.

• Advantages over Paging:

  1. User's View: Matches programmer's logical modules.

  2. Protection: Per-segment (read/write/execute).

  3. Sharing: Share entire segment (e.g., library).

  4. Independent Growth: Stack & heap can grow independently.

Paged Segmentation: Segment table points to page tables. Combines benefits (e.g., Intel x86).

Virtual Memory & Demand Paging

Demand Paging: Load pages only when needed (on page fault). Brings pages from disk (swap space) to memory.

• Benefits: Larger virtual memory, efficient memory use (only needed pages), protection.

Page Replacement Algorithms (VERY HIGH FREQUENCY) Goal: Minimize page faults.

Belady's Anomaly: FIFO can have more page faults with more frames.

Example: Ref string 1,2,3,4,1,2,5,1,2,3,4,5. 3 frames: 9 faults. 4 frames: 10 faults.

Thrashing: CPU spends more time paging than executing.

• Cause: Under-allocation of frames → high page fault rate.

• Detection: Working-Set Model (set of pages used in recent time window Δ) or Page Fault Frequency (PFF).

• Elimination: Working-set strategy (adjust frames per process), PFF (adjust based on fault rate).

V. FILE SYSTEMS

Directory Structures

Disk Space Allocation Methods (VERY HIGH FREQUENCY)

UNIX File System (UFS/FFS):

• Inode: Fixed-size metadata structure (permissions, size, timestamps, 15 pointers: 12 direct, 1 single indirect, 1 double, 1 triple).

• Directory: Maps filename → inode#.

• Data Blocks: Actual file content.

Windows NTFS:

• Master File Table (MFT): Relational database. Each file is a record with attributes (filename, data, security descriptor).

• Directories: B+ trees for fast lookup.

• Features: Journaling, security descriptors (ACLs), alternate data streams.

UNIX vs. Windows File System Comparison:

VI. I/O SYSTEMS & SECONDARY STORAGE

Synchronous vs. Asynchronous I/O

Kernel I/O Subsystem Functions (HIGH FREQUENCY)

1. Scheduling: Queue I/O requests (see Disk Scheduling).

2. Buffering: Store data temporarily (to cope with speed mismatch).

3. Caching: Keep copies in fast memory (e.g., disk cache).

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

5. Device Allocation: Manage exclusive access (e.g., open() with O_EXCL).

6. Error Handling: Retry failed I/O, report errors.

Disk Scheduling Algorithms (VERY HIGH FREQUENCY)

Parameters:

• Seek Time: Move head to cylinder.

• Rotational Latency: Wait for sector to rotate under head.

• Transfer Time: Read/write sector.

• Access Time = Seek Time + Rotational Latency.

Algorithms (Head Movement Calculation):

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

Formula: Total movement = Σ |current - next|.

VII. OPERATING SYSTEM SECURITY & PROTECTION

Security Goals (CIA Triad)

• Confidentiality: Prevent unauthorized disclosure.

• Integrity: Prevent unauthorized modification.

• Availability: Ensure service for authorized users.

Protection Mechanisms

• Access Control Matrix: Rows = domains (users/processes), columns = objects (files), entries = rights (r,w,x).

  
     F1  F2  F3
  
  U1 r*  r   -
  
  U2 -   rw* r
  
  

• Access Lists: Per-object list of (domain, rights).

• Capability Lists: Per-domain list of (object, rights). "Capability" = unforgeable token.

• Protection via Paging: Use protection bits in page table (read-only, execute-only). Ring-based protection (e.g., x86 rings 0-3).

VIII. COMPARATIVE ANALYSIS: UNIX vs. WINDOWS

Memory Management Comparison

I/O Management Comparison

File System Comparison (VERY HIGH FREQUENCY)

IX. SYSTEM CALLS (API to OS)

Categories with Examples

Key File Management Calls:

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

• read(fd, buffer, count): Bytes from file to buffer.

• write(fd, buffer, count): Bytes from buffer to file.

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

• stat(path, &buf): Get file metadata (size, permissions).

• ioctl(fd, request, argp): Device-specific control (e.g., terminal settings).

X. FREQUENTLY ASKED SHORT NOTES (From Past Papers)

Overlay

• Concept: Load only necessary parts of a large program into memory. Programmer specifies overlay structure.

• Usefulness: Allows execution of programs larger than physical memory by swapping modules in/out.

• Modern Equivalent: Demand paging & virtual memory (automated overlaying).

Asynchronous I/O

• Process issues I/O request and continues execution.

• OS signals/completes via callback, signal, or polling.

• Advantage: No blocking, better CPU utilization.

• Disadvantage: Complex programming (concurrency issues).

Real vs. Virtual Concurrency

• Real Concurrency: Multiple processors/cores truly executing simultaneously.

• Virtual Concurrency: Single CPU rapidly context-switching between processes (time-sharing), appearing concurrent.

Dynamic Linking & Loading

• Dynamic Loading: Load routine into memory only when called (reduces memory use).

• Dynamic Linking: Link libraries at load time or runtime (shared libraries: .so, .dll).

  • Advantages: Saves disk/memory, easy updates.

  • Disadvantages: "DLL Hell", runtime overhead.

Disk Space Allocation: Indexed (Detailed)

• Single Indexed: All pointers in one index block.

  • Example: 512-byte blocks, 4-byte pointers → 128 pointers → 64KB file max.

• Multi-level Indexed (UNIX):

  • Direct pointers (12) → 12 blocks.

  • Single indirect → 1 block of pointers → 1024 blocks (512KB).

  • Double indirect → 1 block → 1024 pointer blocks → 1M blocks (512MB).

  • Triple indirect → huge files.

• Linked Indexed (FAT): Chain of pointers stored in separate table in memory.

Kernel I/O Subsystem

• Components: Device drivers, device-independent I/O software, user-level I/O libraries.

• Functions: (See Section VI.II above).

• Structure: Device driver registers with kernel, provides entry points. Kernel uses uniform interface (e.g., read()).

Final Exam Strategy:

1. For 7-mark questions: Define → Explain mechanism → Give example/diagram → Compare/contrast if applicable.

2. For calculation questions (Scheduling, Page Faults, Disk Movement): Always draw Gantt chart or table. Show step-by-step.

3. For comparison questions: Use tables (UNIX vs Windows, User vs Kernel threads).

4. Key Formulas to Remember:

   • Avg. Waiting Time = Σ(Waiting Time) / n

   • Avg. Turnaround Time = Σ(Turnaround Time) / n

   • Page Fault Rate = Page Faults / Total References

   • Belady's Anomaly: FIFO page faults increase with frames.

Common Pitfalls:

• Confusing Preemptive (SRTF, RR) vs Non-Preemptive (SJF, Priority).

• Forgetting aging solves starvation in priority scheduling.

• Misapplying Banker's algorithm (Need = Max - Allocation).

• Confusing Internal (within partition) vs External (between partitions) fragmentation.

• In UNIX inode, forgetting indirect pointers count toward block count.

• In disk scheduling, C-SCAN does not reverse direction at end (jumps to start).

\boxed{\text{Master algorithms with calculations, comparisons with tables, and definitions.}}