Operating System (IT-501) - Unit 4 Short Notes

UNIT 4: Operating System Concepts (Exam-Focused Short Notes)

1. Introduction to Operating Systems

• Definition: An OS is system software that manages computer hardware and software resources, providing a platform for application programs.

• Objectives: Convenience, efficiency (resource utilization), ability to evolve, security, and fairness.

• Major Services:

  • Program Execution: Load and run programs.

  • I/O Operations: Hide device specifics via drivers.

  • File System Abstraction: Manage storage and data access.

  • Communication: Inter-process communication (IPC) and networking.

  • Error Detection & Handling: Ensure system integrity.

  • Protection & Security: Control access to resources.

  • Resource Allocation: Allocate CPU, memory, I/O devices.

  • Accounting & Monitoring: Track resource usage.

• Types of OS:

  • Batch: Jobs submitted together (e.g., early mainframes).

  • Multiprogramming: Multiple jobs in memory; CPU switches when one waits.

  • Time-Sharing: CPU switches rapidly among users (quantum-based).

  • Real-Time: Hard (strict deadlines) and Soft (deadline important but not critical).

  • Distributed: Network of independent computers (e.g., cluster).

  • Network: Supports remote login/file access (e.g., thin client).

  • Mobile: Optimized for smartphones (power, touch, sensors).

• OS Structure:

  • Monolithic: All OS services in kernel space (e.g., traditional UNIX). Fast but hard to maintain.

  • Layered: OS in layers; lower layers serve upper. Easier to debug but rigid.

  • Microkernel: Minimal kernel (IPC, memory, scheduling); services as user-space processes (e.g., Mach). More secure/reliable but slower due to IPC.

  • Modular: Loadable kernel modules (e.g., modern Linux).

• System Calls: Interface between user programs and OS kernel. Types: process control, file management, device management, information maintenance, communication.

• Design Issues: Efficiency (speed), flexibility (adaptability), security (isolation), reliability, compatibility.

• Spooling: Simultaneous Peripheral Operations On-Line. Uses disk as buffer for I/O (e.g., printer queue) to overlap I/O with CPU.

• Protection: Mechanisms to control access to hardware/resources (e.g., CPU modes, memory protection, I/O protection).

[!TIP] Exam Focus: Distinguish between multiprogramming (CPU utilization) and time-sharing (interactive). Know microkernel vs monolithic trade-offs.

2. Process Management

A. Process Concept

• Process: An executing program. It is an active entity with its own Process Control Block (PCB).

• PCB: OS data structure containing process state, program counter, CPU registers, memory management info, I/O status, and accounting info. PCB is the key to process management.

• Process States: New → Ready → Running → Waiting (or Blocked) → Terminated. Some systems include Suspended states (Ready/Suspend, Wait/Suspend).

• Scheduling Queues:

  • Job Queue: All processes in system.

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

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

• Operations:

  • Creation: fork()/create(); new PCB allocated, resources assigned.

  • Termination: exit(); PCB and resources reclaimed.

  • Suspend/Resume: Move between main memory and disk (swapping).

[!IMPORTANT] CPU & Ready Queue: With n CPUs, maximum n processes can be in Running state simultaneously. The Ready Queue size is not limited by the number of CPUs; it can hold any number of ready processes waiting for CPU time.

B. CPU Scheduling

• Scheduling Criteria:

  • CPU Utilization: % time CPU busy.

  • Throughput: # of processes completed per unit time.

  • Turnaround Time: Total time from submission to completion.

  • Waiting Time: Total time spent in ready queue.

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

• Algorithms:

  1. FCFS/FIFO: Non-preemptive. Processes in arrival order. Causes "Convoy Effect".

  2. SJF/SRTF (Shortest Remaining Time First): Optimal for minimizing average waiting time (proven). Preemptive version is SRTF. Requires knowledge of CPU burst times.

  3. Priority Scheduling: Preemptive or non-preemptive. Lower number = higher priority. Starvation possible; solution: aging (gradually increase priority of waiting jobs).

  4. Round Robin (RR): Preemptive. Each process gets a time quantum (q). Cyclically moves through ready queue. New processes always placed at end to ensure fairness and prevent starvation of older processes.

  5. Multilevel Queue: Ready queue partitioned into multiple priority-based queues (e.g., system, interactive, batch). Scheduling between queues (fixed priority or time-slice).

  6. Multilevel Feedback Queue: Multiple queues with different time quanta. Process moves between queues based on behavior (e.g., CPU-bound moves to lower-priority queue).

• Performance Calculation:

  • Gantt Chart: Visual timeline of process execution.

  • Turnaround Time = Completion Time – Arrival Time.

  • Waiting Time = Turnaround Time – Burst Time.

  • Normalized Turnaround Time = Turnaround Time / Burst Time.

• Example (SJF Justification): For a set of CPU-bound processes arriving together, non-preemptive SJF minimizes average waiting time because it schedules shortest jobs first, reducing the wait for subsequent jobs.

C. Process Synchronization

• Critical Section Problem: Code segment where a process accesses shared resources (variables, files, devices). Must be executed atomically.

• Requirements for Solution:

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

  2. Progress: If no process is in CS and others wish to enter, decision cannot be postponed indefinitely.

  3. Bounded Waiting: There exists a bound on the number of times other processes can enter CS after a process requests entry and before it is granted.

• Semaphores: Integer variable (S) accessed atomically via two operations:

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

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

  • Atomicity is crucial; implemented via hardware instructions like TestAndSet.

• TestAndSet Implementation (Minimal Busy Waiting):

  
  boolean lock = false;
  
  void wait(int *S) {
  
      while (TestAndSet(&lock)) ; // busy wait
  
      // critical section
  
      lock = false; // release
  
  }
  
  

• Semaphore Arithmetic Problem: Given x P and y V operations, largest initial S so at least one P blocks: S_max = x - y - 1. (Final value S_final = S_initial + y - x. Blocking occurs if S_final < 0 at any P).

• Monitors: High-level synchronization construct. Procedures are executed with mutual exclusion. Uses condition variables (wait(), signal()) for blocking.

[!TIP] Common Pitfall: In semaphore problems, track the value after each P/V. Blocking happens when S becomes negative during a P.

3. Deadlock

• Definition: A set of processes are deadlocked if each is waiting for an event that can only be caused by another process in the set.

• Example: P1 holds R1, waits for R2; P2 holds R2, waits for R1.

• Necessary Conditions (ALL must hold simultaneously):

  1. Mutual Exclusion: Resources are non-shareable.

  2. Hold and Wait: Process holds at least one resource while waiting for others.

  3. No Preemption: Resources cannot be forcibly taken.

  4. Circular Wait: A circular chain of processes exists, each waiting for a resource held by the next.

• Deadlock vs Starvation:

  | Deadlock | Starvation | |---|---| | Circular wait; processes never proceed. | Process waits indefinitely but could eventually proceed. | | All involved processes are stuck. | One or more processes are perpetually denied resources. | | Caused by circular wait condition. | Caused by biased scheduling (e.g., always high-priority jobs). |

• Handling Methods:

  • Prevention: Design system to ensure at least one necessary condition never holds.

    • Eliminate mutual exclusion (only for shareable resources).

    • Eliminate hold-and-wait: request all resources at once (low utilization) or release held resources before requesting new ones.

    • Allow preemption: take resource from waiting process (only if state can be saved/restored).

    • Eliminate circular wait: impose total ordering on resource types; request in increasing order.

  • Avoidance: Dynamically check if allocation leads to unsafe state. Requires a priori knowledge of max needs.

    • Banker's Algorithm (for multiple instances): Safe state → allocation granted; unsafe → denied.

    • Safety Algorithm: Find if there exists a safe sequence (order of processes that can finish).

    • Need Matrix: Need[i][j] = Max[i][j] - Allocation[i][j].

  • Detection & Recovery:

    • Detection: For single-instance resources, use Resource Allocation Graph (RAG); cycle = deadlock. For multiple instances, use Wait-For Graph (collapse RAG); cycle = deadlock.

    • Recovery: Process termination (all or one-by-one) or resource preemption (checkpoint/rollback).

• Banker's Algorithm Steps:

  1. Check Request_i <= Need_i. If not, error.

  2. Check Request_i <= Available. If not, process waits.

  3. Pretend allocation: Available -= Request_i, Allocation_i += Request_i, Need_i -= Request_i.

  4. Run Safety Algorithm:

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

     • Find i such that Finish[i]=false and Need_i <= Work.

     • If found, Work += Allocation_i, Finish[i]=true, repeat.

     • If all Finish[i]=true, state is safe; safe sequence is order of finishing.

• RAG Analysis: Directed edges: P → R (request), R → P (assignment). Cycle in a single-instance RAG = deadlock. Adding a new edge may create/break cycles.

[!TIP] Exam Focus: Banker's algorithm questions always ask for Need matrix and safe sequence. In RAG, distinguish request edges (dashed) from assignment edges (solid).

4. Memory Management

A. Basic Partitioning

• Fixed Partitioning: Memory divided into fixed-size partitions. Internal Fragmentation: Wasted space inside partition (process smaller than partition).

• Dynamic Partitioning: Partitions of variable size. External Fragmentation: Free memory exists but is not contiguous. Compaction: Move processes in memory to create one large free block (expensive, requires dynamic relocation).

B. Paging

• Concepts:

  • Logical Address: Generated by CPU (page number p + offset d).

  • Physical Address: Seen by memory unit (frame number f + offset d).

  • Page: Fixed-size logical block.

  • Frame: Fixed-size physical block (same size as page).

  • Page Table: Per-process mapping page → frame. Stored in memory.

• Translation Lookaside Buffer (TLB): Associative, high-speed cache for page table entries.

  • Effective Access Time (EAT):

    Let:

    • t_TLB = TLB access time

    • t_mem = memory access time

    • h = TLB hit ratio

    Then:

$$ \text{EAT} = h \cdot (t_{TLB} + t_{mem}) + (1-h) \cdot (t_{TLB} + 2 \cdot t_{mem}) $$

    \boxed{\text{EAT} = t_{TLB} + t_{mem} + (1-h) \cdot t_{mem}}

*   **Example**: `t_TLB=20ns`, `t_mem=100ns`, `h=0.8` → EAT = 20 + 100 + 0.2*100 = **140 ns**.

• Protection in Paging:

  • Valid/Invalid Bit: 1 = page in process space; 0 = illegal access (trap to OS).

  • Read/Write Bit: Prevents writing to code pages.

  • User/Supervisor Bit: Kernel pages inaccessible in user mode.

  • A process cannot access memory it does not own because its page table only contains mappings to frames allocated to it. OS could allow access by sharing page table entries (e.g., shared libraries), but this risks security/corruption.

• Demand Paging: Load pages only when needed (on page fault). Effective Access Time:

  Let p = page fault probability.

  Let t_{service} = page fault service time (disk I/O + swap in/out).

  Then:

$$ \text{EAT} = (1-p) \cdot t_{mem} + p \cdot t_{service} $$

\boxed{\text{EAT} = t_{mem} + p \cdot t_{service}}

(assuming `t_{service}` >> `t_{mem}`).

C. Page Replacement Algorithms

• Goal: Minimize page faults.

• Algorithms (for a fixed number of frames N):

  1. FIFO: Replace oldest page. Belady's Anomaly: More frames → more page faults (for some reference strings).

  2. LRU (Least Recently Used): Replace least recently used page. Approximated via counter/stack.

  3. Optimal (OPT): Replace page whose next use is farthest in future. Theoretical lower bound; not implementable in practice.

• Page Fault Calculation: Simulate algorithm with given reference string and N frames. First N unique references always fault.

  • Example Reference String (from Nov 2022): 1,2,3,4,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6.

  • For 4 frames, LRU: Faults at 1,2,3,4,5,6,7 → 7 faults (verify by simulation).

• Comparison: LRU close to Optimal; FIFO simple but suffers anomaly; Optimal is benchmark.

D. Thrashing and Working Set

• Thrashing: High page fault rate causing CPU to spend most time swapping, not executing. Occurs when degree of multiprogramming is too high relative to available frames.

• Working Set Model: W(t, Δ) = set of pages referenced by process in time interval (t-Δ, t). If Σ W_i > M (total frames), thrashing occurs.

• Page Fault Frequency (PFF): Directly monitor page fault rate. If too high, allocate more frames; if too low, take frames away.

E. Segmentation and Segmented Paging

• Segmentation: Logical address = <segment-number, offset>. Segment Table maps segment to physical memory (base, limit). Supports programmer's view (code, data, stack). External fragmentation occurs.

• Segmented Paging: Each segment is paged. Segment table points to page tables. Combines benefits: no external fragmentation (paging), logical view (segmentation). Used in Intel 386+.

• Hashed Page Tables: For large address spaces (64-bit). Page number hashed → bucket of entries. Good for sparse address spaces; average lookup longer than 2-level paging.

• Comparison:

  | Segmented Paging | Hashed Page Tables | |---|---| | Good for moderate address spaces with clear segmentation. | Good for very large, sparse address spaces (e.g., 64-bit). | | 2-level lookup (segment→page→frame). | 1-level but with collisions; average multiple comparisons. | | Supports protection/sharing at segment level. | Harder to implement protection/sharing. |

F. Allocation Policies

• Local Replacement: Process replaces only its own pages. Stable but may hold low-priority pages.

• Global Replacement: Process can replace any page in memory. Higher throughput but can cause priority inversion (low-priority process evicts high-priority's page).

• Advantages/Disadvantages:

  | Local | Global | |---|---| | Predictable per-process performance. | Higher system throughput. | | Prevents one process from affecting others. | Can cause thrashing if aggressive processes take frames. | | Less flexible. | More flexible, better memory utilization. |

5. I/O and Disk Management

A. Disk Scheduling

• Disk Structure: Platters → Tracks → Sectors. Cylinder: All tracks aligned across platters.

• Timing Components:

  • Seek Time (t_s): Move arm to cylinder.

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

  • Transfer Time (t_t): Read/write sector (sectors per track / rotation time).

• Scheduling Algorithms (minimize seek time):

  1. FCFS: Simple, fair, but poor seek performance.

  2. SSTF: Select closest request. Can cause starvation of far requests.

  3. SCAN (Elevator): Arm moves in one direction servicing requests until end, then reverses.

  4. C-SCAN (Circular SCAN): Arm moves in one direction only; jumps back to start without servicing (like a circular queue). More uniform wait times.

  5. LOOK/C-LOOK: Like SCAN/C-SCAN but only goes as far as last request in direction, then reverses.

• Total Head Movement Calculation: Sum of absolute differences between consecutive cylinder requests (including initial head position).

  • Example (Nov 2022): Requests: 98,183,37,122,14,124,65,67, initial head 53.

    • FCFS: |53-98|+|98-183|+... = 640 cylinders.

    • SSTF: Order from 53: 65,67,98,122,124,183,37,14 → calculate.

    • SCAN (to 199): 65,67,98,122,124,183,199 then reverse to 37,14 → calculate.

    • C-SCAN: 65,67,98,122,124,183,199 then jump to 0, then 14,37 → calculate.

• Impact of Page Size on Load Time:

  • Load Time = (Seek time per page) + (Rotational latency per page) + (Transfer time per page).

  • Larger page size → fewer pages → fewer seeks/latencies → faster load, but more internal fragmentation.

  • Calculation (Nov 2022): Program size 64 KB, track holds 32 KB, seek 10 ms, rotation 20 ms.

    • Page size 2 KB → 32 pages. Each page on different cylinder (given). Load time = 32 × (10 + 10 + 0.625) ≈ 32 × 20.625 = 660 ms (transfer time per page: 2KB / (32KB/20ms) = 1.25ms? Actually, track holds 32KB, rotation 20ms → transfer rate = 32KB/20ms = 1.6KB/ms. For 2KB page, transfer = 2/1.6 = 1.25ms. Avg rotational latency = 10ms. So per page = 10(seek) + 10(latency) + 1.25(transfer) = 21.25ms. Total = 32×21.25 = 680 ms).

    • Page size 4 KB → 16 pages. Per page transfer = 4/1.6 = 2.5ms. Per page = 10+10+2.5=22.5ms. Total = 16×22.5 = 360 ms.

B. File Management

• File Attributes: Name, identifier, type, location, size, protection, time/dates (creation, modification, access).

• File Operations: Create, delete, read, write, reposition, truncate, append.

• Access Methods:

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

  2. Direct/Random: read(n) reads record n (e.g., disk).

  3. Indexed: Build index for direct access (e.g., ISAM).

• File Allocation Methods:

  | Method | How | Advantages | Disadvantages | |---|---|---|---| | Contiguous | One continuous block. | Fast sequential/direct access; simple. | External fragmentation; file growth difficult; need compaction. | | Linked | Each block points to next. | No external fragmentation; file grows easily. | Slow direct access (sequential traversal); space for pointers; reliability (broken link). | | FAT (Linked variant) | Table in memory maps blocks. | Faster than pure linked; easy to traverse. | Table memory overhead; poor direct access for large files. | | Indexed | Blocks of pointers (index block) at start. | Fast direct access; no external fragmentation. | Large files need multi-level/indexed; index block size limit. |

  • For Database Management Systems (DBMS): Indexed allocation (or extent-based contiguous for large sequential scans). DBMS requires fast random access to records → indexed provides direct mapping via index.

• Free Space Management:

  • Bit Vector: 1 bit per block. Simple, fast allocation.

  • Linked List: Free blocks chained. Wastes space in free blocks.

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

  • Counting: Keep runs of contiguous free blocks (like FAT for free space).

• Issues in File Removal:

  • Problem: Simply adding freed blocks to free list creates external fragmentation (many small holes).

  • Solutions:

    1. Coalescing: Merge adjacent free blocks during removal.

    2. Compaction: Periodically move files to create large free space (expensive).

    3. Use better allocation (e.g., indexed) to reduce fragmentation.

• Granularity in Disk Allocation:

  • Idea: Allow variable block sizes (e.g., 4KB vs 512B).

  • Performance: Small files use small blocks → less internal fragmentation, more I/O overhead (more blocks to read). Large files use large blocks → fewer I/Os, less overhead.

  • Free Space Management Modification: Need to track block size in free list/bitmap. Could use multiple free lists for each size (like slab allocator).

• Application for Random Access to Indexed Files: Database Management Systems (DBMS). They frequently perform record lookups by key → indexed allocation provides O(1) direct access via index.

[!TIP] Exam Focus: Disk scheduling calculations are high-yield. Know formulas for total head movement. For file allocation, justify choice for DBMS (indexed). Understand how variable block sizes improve performance (trade-off I/O count vs internal fragmentation).