UNIT 3: Operating System (Exam-Focused Short Notes)

I. Operating System Fundamentals

Definition & Objectives

An Operating System (OS) is system software that acts as an intermediary between computer hardware and user applications. Its primary objectives are:

• Convenience: Makes the system easy to use.

• Efficiency: Manages system resources effectively.

• Ability to Evolve: Allows for the addition of new functions and hardware.

• Security & Protection: Prevents unauthorized access to system resources.

Major Services

Types of OS (with Examples)

OS Structures

• Monolithic: All OS components in a single binary (high performance, hard to debug). Example: Traditional UNIX.

• Layered: OS organized in layers, each using only lower layers (easier to debug, may be inefficient). Example: THE OS.

• Microkernel: Minimal core (IPC, memory management); other services as user-space processes (more secure, slower). Example: QNX, macOS XNU.

• Modular: Dynamic loading of OS modules (balance of flexibility & performance). Example: Modern Windows, Linux (loadable kernel modules).

System Calls

• Concept: The programmed interface through which an application requests a service from the kernel.

• Importance: Provides controlled access to hardware and protected resources; defines the OS's "API".

• Types: Process control (fork(), exit()), file management (open(), read()), device management (ioctl()), information maintenance (getpid()), communication (pipe(), shmget()).

Design Issues: Spooling & Buffering

• Spooling (Simultaneous Peripheral Operations On-Line): Holds output data on disk (e.g., print queue) to allow processes to continue without waiting for slow I/O devices.

• Buffering: Temporary storage of data while it's being transferred between devices or between a device and an application. Smooths out speed differences.

[!TIP] Exam Focus: Be ready to contrast OS types and structures. Know that system calls are the only way for user processes to request OS services.

II. Process Management

A. Process Concept

• Process: A program in execution. It is an active entity with a Process Control Block (PCB).

• PCB: The OS's data structure containing all information about a process:

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

• Process States & Transitions:

  
  New → Ready → Running → Waiting → Terminated
  
         ↑         ↓
  
         └─── Suspended ────┘
  
  

  • Suspension: Process moved to secondary storage (Ready/Suspend, Wait/Suspend).

• Multiprocessor Considerations:

  • Maximum ready processes with n CPUs: n (if all are identical and multiprogrammed).

  • Ready queue size is independent of CPU count. Multiple CPUs can pull from the same ready queue.

B. CPU Scheduling

Scheduling Criteria

Scheduling Algorithms

Performance Calculation (Gantt Chart)

1. Draw Gantt Chart showing start/end times for each process.

2. Calculate for each process: Completion Time, Turnaround Time (TAT), Waiting Time (WT).

3. Compute Averages: Avg WT = Σ WT / n, Avg TAT = Σ TAT / n.

4. Normalized TAT: TAT / Burst Time (useful for comparing efficiency).

[!TIP] Common Pitfall: For preemptive algorithms (SRTF, Priority Preemptive, RR), arrival times matter. A process arriving later can preempt a running one. Always sort by arrival time first.

C. Process Synchronization

Critical Section Problem

A code segment where a process accesses shared resources (variables, files, devices). Must satisfy:

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

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

3. Bounded Waiting: There exists a bound on the number of times other processes can enter their CS after a process requests entry.

Semaphores

• Integer variable used for signaling and coordination.

• Types:

  • Binary Semaphore (Mutex): Values 0 or 1. Used for mutual exclusion.

  • Counting Semaphore: Integer ≥ 0. Counts available resources.

• Operations (must be ATOMIC):

  • wait(S) / P(S): while (S <= 0) ; S--; (decrements, blocks if ≤0)

  • signal(S) / V(S): S++; (increments, wakes a blocked process if any)

• Counting Semaphore Calculation:

  • Final value S_final = S_initial + (#V operations) - (#P operations).

  • If S_final < 0, |S_final| processes are blocked.

  • Largest initial S for at least one block: S_initial < (#P operations) - (#V operations).

TestAndSet() Implementation (Minimal Busy Waiting)

boolean TestAndSet(boolean *target) {

    boolean r = *target;

    *target = true;

    return r;

}

void wait(boolean *lock) {

    while (TestAndSet(lock)); // Busy wait

}

void signal(boolean *lock) {

    *lock = false;

}

Resource Allocation Graph (RAG)

• Vertices: Processes (P1...) & Resource Types (R1...).

• Edges:

  • Assignment Edge: Ri → Pj (resource Ri allocated to process Pj).

  • Request Edge: Pj → Ri (process Pj requests resource Ri).

• Deadlock ⇔ Cycle in the graph if each resource type has exactly one instance.

• For multiple instances, cycle is necessary but not sufficient for deadlock.

[!TIP] Exam Tip: For semaphore problems, track S after each P/V. A P blocks if it would make S negative. For RAG, draw carefully and check for cycles.

III. Deadlock

A. Definition & Conditions

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

• Four Necessary Conditions (ALL must hold simultaneously):

  1. Mutual Exclusion: At least one resource is non-sharable.

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

  3. No Preemption: Resources cannot be forcibly taken away.

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

• Deadlock vs. Starvation:

  • Deadlock: Permanent blocking; circular wait condition holds.

  • Starvation: Process waits indefinitely but could eventually proceed (e.g., always losing in priority scheduling). No circular wait.

B. Handling Strategies

C. Case Studies & Calculations

Banker's Algorithm (Multiple Resource Types)

Goal: Determine if a state is safe (exists a safe sequence) or unsafe (possible deadlock). Data Structures:

• Available: Vector of available instances of each resource.

• Max: n x m matrix (max demand of each process).

• Allocation: n x m matrix (currently allocated resources).

• Need = Max - Allocation (remaining need of each process).

Algorithm Steps:

1. Find a process Pi such that Need_i ≤ Available.

2. If found, pretend to allocate Allocation_i back to Available (Available = Available + Allocation_i), and mark Pi as finished (add to safe sequence).

3. Repeat until all processes finish (safe) or no such Pi exists (unsafe).

[!TIP] Exam Pattern: You will be given Max, Allocation, and Available vectors. First compute Need matrix. Then apply the algorithm step-by-step to find a safe sequence or declare unsafe.

Resource Allocation Graph (RAG) Analysis

• Single-instance resources: Deadlock iff there is a cycle.

• Multiple-instance resources: Cycle is necessary but not sufficient. Must use wait-for graph (derived from RAG) or Banker's-like detection.

IV. Memory Management

A. Partitioning & Allocation

Allocation Algorithm Comparison (for a given set of partitions & process sizes):

• First-Fit: Allocate first block large enough. Fast, may cause external fragmentation at low addresses.

• Best-Fit: Allocate smallest block large enough. Minimizes leftover space, slower, causes many small holes.

• Worst-Fit: Allocate largest block. Aims for large leftover holes, generally worst performance.

B. Paging

• Basic Concept: Divide physical memory into fixed-size frames and logical memory into same-size pages. No external fragmentation.

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

• Page Table: Maps page numbers to frame numbers. Stored in memory.

• Structures:

  • Hierarchical: Multi-level page tables (e.g., two-level for 32-bit).

  • Hashed: For large address spaces (sparse).

  • Inverted: One entry per physical frame, stores all (process, page) mapping. Used for shared memory.

• Translation Lookaside Buffer (TLB): Fast associative cache for recent page table entries.

  • Effective Access Time (EAT) with TLB:

$$EAT = (TLB\_hit\_ratio) \times (TLB\_access + Memory\_access) + (1 - TLB\_hit\_ratio) \times (TLB\_access + 2 \times Memory\_access)$$

    (Assuming TLB miss requires two memory accesses: one for page table, one for data).

• Protection & Sharing: Page table entries have protection bits (R/W/X). Sharing is achieved by mapping same physical frame into page tables of multiple processes.

• Process Isolation: A process can only access frames its page table points to. The Memory Management Unit (MMU) translates logical to physical addresses using the page table; unauthorized accesses cause a trap.

C. Page Replacement Algorithms

• FIFO: Replace oldest page. Simple, but suffers from Belady's Anomaly (more frames → more faults for some strings).

• LRU: Replace least recently used page. Near-optimal, requires hardware/software history tracking.

• Optimal (Belady's): Replace page whose next use is farthest in future. Theoretical minimum faults, but not implementable (needs future knowledge).

• Reference String Analysis: Given a string of page references and n frames, simulate the algorithm, count page faults. First n unique references always fault.

D. Demand Paging

• Concept: Bring a page into memory only when it is referenced (on page fault).

• Page Fault: Trap to OS when accessed page is not in memory.

• Effective Access Time (EAT):

$$EAT = (1 - p) \times (memory\_access\_time) + p \times (page\_fault\_service\_time + memory\_access\_time)$$

Where `p` = page fault rate.

*   `page_fault_service_time` includes: disk seek, rotational latency, transfer time, and OS overhead.

E. Thrashing

• Cause: High page fault rate → processes spend most time paging, not executing → low CPU utilization.

• Working Set Model: The set of pages a process has referenced in its recent window of time Δ. If Σ (working set sizes) > # of frames, thrashing occurs.

• Prevention:

  • Working Set Policy: OS tracks working sets; suspends processes if Σ WS > available frames.

  • Page Fault Frequency (PFF): Directly control p. If p too high, allocate more frames; if too low, take frames away.

F. Allocation Policies

V. Storage Management

A. Disk Scheduling

• Disk Geometry: Tracks (concentric circles), Sectors (on a track), Cylinders (same track # across platters).

• Access Time Components:

  • Seek Time: Moving arm to correct cylinder.

  • Rotational Latency (Delay): Waiting for disk to rotate to correct sector.

  • Transfer Time: Reading/writing the sector(s).

• Algorithms (given request queue & initial head position):

  | Algorithm | Principle | Total Head Movement | Fairness | | :--- | :--- | :--- | :--- | | FCFS | Serve in arrival order. | Often high. | Fair. | | SSTF | Serve closest request to current head. | Lower than FCFS. | May starve far requests. | | SCAN (Elevator) | Arm moves in one direction servicing requests until end, then reverses. | Good, predictable. | Fair. | | C-SCAN | Like SCAN but only services in one direction; jumps back to start without servicing. | More uniform wait than SCAN. | Fairer than SCAN? | | LOOK / C-LOOK | Like SCAN/C-SCAN but only goes as far as last request in direction. | Slightly better than SCAN. | Fair. |

Calculation: Sum the absolute differences (|next_cylinder - current_cylinder|) for the sequence of head movements.

[!TIP] Exam Pattern: You will be given a queue like 98, 183, 37, ... and head start at 53. Draw the head movement path for each algorithm and sum the distances.

B. File Management

File Attributes

Name, Identifier, Type, Location, Size, Protection, Timestamps (creation, last modified, last accessed).

File Operations

Create, Delete, Read, Write, Seek, Append, Truncate.

File Access Methods

• Sequential: Read next record (e.g., tape). Simple, slow for random.

• Direct (Random): Read(n) reads nth record directly (e.g., fixed-length records on disk). Fast random access.

• Indexed: Build an index (file) containing pointers to data blocks. Allows variable-length records and efficient access (e.g., ISAM).

File Allocation Methods

Free Space Management

Variable Granularity (e.g., 4KB vs 512B):

• Advantage: Small files use small blocks (less internal waste); large files use large blocks (fewer pointers/indirection).

• Modification Needed: Free-space management must track both the size and starting location of free extents (use Counting or Grouping with size info).

Directory Structure

• Single-Level: All files in one directory. Simple, naming conflict.

• Two-Level: User directories under a master directory. No user naming conflict.

• Tree-Structured: Hierarchical (directories/subdirectories). Unique path names.

• Acyclic Graph: Shared files via links (hard/soft). Multiple paths.

• General Graph: Cycles possible (needs garbage collection for deletion).

C. Disk Performance & Reliability

• Access Time Formula:

$$Access\_Time = Seek\_Time + Rotational\_Latency + Transfer\_Time$$

*   `Rotational Latency ≈ (1/2) * Rotation_Time` (average).

• Loading Time for Program: Sum of access times for all pages/blocks needed, plus transfer time.

• Impact of Page Size:

  • Larger page: Fewer page faults (better locality), but more internal fragmentation (last page partially filled). Larger transfer time per fault.

  • Smaller page: Less internal waste, but more page faults (TLB misses, disk I/O overhead).

• Application Example (Random Access to Indexed Files): Database Management Systems (DBMS). Indexed allocation (like B+ trees) allows efficient record retrieval by key without scanning entire file.

[!TIP] Exam Focus: Be prepared to calculate total head movement for all disk scheduling algorithms. Know the pros/cons of each file allocation method and which is best for DBMS (indexed). Understand the trade-off of page size on I/O and fragmentation.