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

UNIT 2: PROCESS MANAGEMENT & SYNCHRONIZATION

Process Concept & PCB

• Process: A program in execution; an entity with its own address space, resources, and state.

• Process Control Block (PCB): OS data structure storing process state (ID, program counter, registers, memory limits, I/O status, scheduling info).

• Process States: New → Ready → Running → Waiting → Terminated. Transitions via OS scheduler/dispatcher.

• Context Switch: Saving state of running process to its PCB and loading state of next ready process. Costly due to TLB flushes & cache misses.

[!TIP]

Exam Focus: PCB contents & state diagram are frequent 2-4 mark questions. Know context switch overhead reasons.

CPU Scheduling

• Objectives: Maximize CPU utilization & throughput; minimize turnaround, waiting, and response time.

• Key Metrics:

  • Turnaround Time = Completion Time – Arrival Time

  • Waiting Time = Turnaround Time – CPU Burst Time

  • Normalized Turnaround = Turnaround Time / CPU Burst Time

  • Response Time = First CPU allocation – Arrival Time (for time-sharing)

Scheduling Algorithms

[!TIP]

Gantt Chart: Draw timeline with process allocations. Calculate waiting time per process as sum of gaps between its bursts.

For multiprocessors: Ready queue size can exceed number of CPUs; processes wait in ready queue if all CPUs busy.

Process Synchronization

• Critical Section Problem: Code segment accessing shared resources. Must satisfy:

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

  2. Progress – If no process in CS and others wish to enter, decision made in finite time.

  3. Bounded Waiting – No process starves; limit on times other processes enter CS after request.

Semaphores

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

• Counting Semaphore (≥0): Counts available resources.

• Operations:

  • wait(S) / P(S): S--; if S < 0, block process.

  • signal(S) / V(S): S++; if S ≤ 0, wake blocked process.

• Atomicity of wait/signal is critical; interrupts disabled or hardware instructions (TestAndSet) used.

TestAndSet Implementation (Minimal Busy Waiting)

boolean TestAndSet(boolean *target) {

    boolean r = *target;

    *target = true;

    return r;

}

// wait() for binary semaphore S:

while (TestAndSet(&S)) ; // busy wait

// signal():

S = false;

[!TIP]

Semaphore Problems: Common in exams – e.g., "Given 20 P and 12 V operations, largest initial S so at least one P blocks?"

Solution: Net decrement = 20 – 12 = 8. For at least one P to block, S_initial – 8 < 0 → S_initial ≤ 7. Max initial S = 7.

UNIT 3: DEADLOCK

Definition & Conditions

• Deadlock: Set of processes blocked; each holds resource waiting for another held by another in set.

• Coffman Conditions (all necessary):

  1. Mutual Exclusion – Resource non-sharable.

  2. Hold and Wait – Process holds resources while requesting more.

  3. No Preemption – Resources released only voluntarily.

  4. Circular Wait – Circular chain of processes waiting for each other’s resources.

[!TIP]

Deadlock vs Starvation: Deadlock – circular wait; all processes blocked forever. Starvation – indefinite postponement but not necessarily circular; may eventually get resource.

Resource Allocation Graph (RAG)

• Vertices: Processes (circles), Resources (squares with dots for instances).

• Edges:

  • Request Edge (process → resource): Process requests resource.

  • Assignment Edge (resource → process): Resource allocated.

• Cycle Detection: In RAG with single instance per resource type, cycle ⇒ deadlock. With multiple instances, cycle may not imply deadlock.

Example from Past Paper:

Given edges: P1→R1, P2→R2, R2→P2, R2→P1, R3→P3.

• R2 assigned to P2 and P1? Wait: R2→P2 means R2 allocated to P2; P2→R2 is request? Clarify: Typically, R→P is assignment, P→R is request.

• If P2→R2 is request and R2→P2 is assignment, then P2 holds R2 and requests R2? Contradiction. Likely typo; interpret as:

  P1 holds R1, requests R2; P2 holds R2, requests R1 → cycle → deadlock.

• Adding P3→R2: P3 requests R2 held by P2. If P2 also waiting for P1’s resource, cycle may grow. Check: If P1→R2, P2→R1, then cycle P1→R2→P2→R1→P1. Adding P3→R2 doesn’t break cycle; deadlock persists if P2 still waits for R1.

Handling Deadlock

1. Prevention: Attack one condition.

   • Mutual exclusion: Make resources sharable (e.g., read-only files).

   • Hold and wait: Request all resources at once; or release held resources before requesting new.

   • No preemption: Preempt resources if possible (e.g., take memory from process).

   • Circular wait: Impose total ordering on resource types; request in increasing order.

2. Avoidance: Banker’s Algorithm – ensure system never enters unsafe state.

   • Data Structures:

     • Available: Vector of available instances per resource.

     • Max: Max demand per process.

     • Allocation: Currently allocated per process.

     • Need = Max – Allocation.

   • Safety Algorithm:

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

     2. Find i such that Finish[i]=false and Need_i ≤ Work. If none, go to 4.

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

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

   • Resource Request Algorithm: If Request_i ≤ Need_i and Request_i ≤ Available, pretend allocate and check safety. If unsafe, process waits.

[!TIP]

Banker’s Example: Given matrices, compute Need, then simulate safety. Safe sequence found if all processes can finish.

Past Paper: With Allocation and Max, compute Need, then check safety with given Availability.

3. Detection & Recovery:

   • Detection: For multiple instances, use RAG cycle detection algorithm (similar to safety but with Request vs Allocation).

   • Recovery:

     • Process Termination: Abort deadlocked processes (all or one-by-one).

     • Resource Preemption: Select victim process, rollback to safe state (checkpoint/restart).

UNIT 4: MEMORY MANAGEMENT

Techniques

Allocation Algorithms (Dynamic)

• First-Fit: Allocate first hole ≥ size. Fast, but may cause many small holes at start.

• Best-Fit: Allocate smallest hole ≥ size. Minimizes leftover, but many small holes; costly search.

• Worst-Fit: Allocate largest hole. Aims to leave large leftover, but often worse than best-fit.

[!TIP]

Example: Memory blocks: 200, 400, 600, 500, 300, 250 KB. Processes: 357, 210, 468, 491 KB (Best Fit).

• 357 → 400 (left 43)

• 210 → 250 (left 40)

• 468 → 500 (left 32)

• 491 → 600 (left 109)

Not allotted: 200, 300 KB blocks.

Paging

• Logical Address = Page Number + Page Offset.

• Physical Address = Frame Number + Page Offset.

• Page Table: Maps page # → frame #. Stored in memory → two accesses (page table + data) unless TLB.

• TLB (Translation Lookaside Buffer): Associative cache for page table entries.

  • Effective Access Time (EAT):

    Let p = TLB hit ratio, t_TLB = TLB access time, t_mem = memory access time.

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

If TLB hit, 1 memory access; if miss, 2 (page table + data).

• Protection: Valid/invalid bit per page; read/write bits.

[!TIP]

Past Paper: "Memory reference 200 ns, 75% TLB hit, TLB lookup 0 time" →

EAT = 0.75200 + 0.25400 = 150 + 100 = 250 ns.

Segmentation

• Logical address = Segment # + Offset.

• Segment Table: Base address + limit per segment.

• Protection: Segment-level read/write/execute bits.

Segmented Paging vs Hashed Page Tables

• Segmented Paging: Each segment has its own page table. Good for sparse address spaces; segment # → page table pointer.

• Hashed Page Tables: Single global table; hash(page #) → bucket of entries. Used in 64-bit systems (e.g., SPARC, x86-64) to avoid huge linear tables.

Virtual Memory & Demand Paging

• Demand Paging: Page brought to memory only when needed (page fault on invalid access).

• Page Fault Service Time = t_{swap} (disk I/O) + t_{overhead} (queue, transfer).

• EAT with Page Fault Probability p:

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

Page Replacement Algorithms

Given reference string, # frames, initially empty.

• FIFO: Replace oldest page. Belady’s anomaly: more frames → more faults for some strings.

• LRU: Replace least recently used. Approximated by reference bits or stack.

• Optimal (Belady’s): Replace page not used for longest future time. Theoretical lower bound.

[!TIP]

Past Paper: Reference string: 1,2,3,4,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6. Compute faults for 1-7 frames.

LRU: Use stack; FIFO: queue; Optimal: look ahead.

Thrashing

• Cause: Low p (page fault rate) but high p due to insufficient frames → CPU spends most time swapping.

• Working Set Model: Set of pages referenced in recent Δ time. If Σ working_set_sizes > m (frames), thrashing occurs.

• Page Allocation:

  • Local: Each process gets fixed frames; reduces thrashing but may underutilize memory.

  • Global: Processes compete for all frames; better utilization but can cause thrashing if one process hogs memory.

UNIT 5: I/O SYSTEMS & DISK SCHEDULING

Disk Structure & Performance

• Tracks, Sectors, Cylinders (same track # across platters).

• Metrics:

  • 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 + Transfer Time.

Disk Scheduling Algorithms

Given request queue, initial head position.

• FCFS: Serve in arrival order. Fair but high head movement.

• SSTF: Serve closest request. Reduces movement but may starve outer/inner requests.

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

• C-SCAN: Head moves in one direction; when reaching end, jumps to start without servicing.

• LOOK/C-LOOK: Like SCAN/C-SCAN but only go as far as last request in direction.

[!TIP]

Calculation: Total head movement = sum of |next cylinder – current|.

Past Paper Example: Requests: 98,183,37,122,14,124,65,67; head at 53.

• FCFS: |98-53|+|183-98|+... = compute.

• SSTF: Always pick closest to current.

• SCAN: Assume direction (e.g., toward larger). Serve all in direction, then reverse.

• C-SCAN: Only one direction; jump from max to min.

Program Loading Time

Time = seek + rotational latency + transfer for each page (if pages on different cylinders).

For n pages: Total Time = n*(seek + latency) + transfer_time_total.

Transfer time = (page size * n) / (track capacity * rotation time).

[!TIP]

Past Paper: 64 KB program, avg seek=10ms, rotation=20ms, track=32KB. Page size 2KB vs 4KB.

• Pages = 64/2 = 32 or 64/4 = 16.

• Each page on different cylinder → seek+latency per page.

• Transfer: total data / (track capacity * rotation time).

Compute separately.

UNIT 6: FILE SYSTEMS

File Attributes & Operations

• Attributes: Name, identifier, type, location, size, protection, timestamps (create, modify, access).

• Operations: Create, delete, read, write, reposition (seek), truncate.

Access Methods

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

• Direct (Random): Jump to any block via seek(address).

• Indexed: Index block contains pointers to data blocks (allows direct access without sequential scan).

Allocation Methods

[!TIP]

DBMS Preference: Indexed or Hashed allocation for fast random access. Contiguous may cause fragmentation; linked slow for seeks.

Free Space Management

• Bit Vector: 1 bit per block; 1=free, 0=allocated. Compact, easy to find contiguous blocks.

• Linked List: Free blocks chained; each block stores list of next free blocks.

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

• Directory-Based: Directory contains free block info.

File Removal Issues

• Problem: Simply adding freed blocks to free list may create many small fragments → external fragmentation.

• Solution: Coalescing – merge adjacent free blocks when possible. Maintain free list sorted by address for easy merging.

Granularity in Disk Allocation

• Variable Block Sizes (e.g., 4KB vs 512B):

  • Advantage: Large files use large blocks → fewer I/Os, less metadata. Small files use small blocks → less internal fragmentation.

  • Modifications to Free-Space Management:

    • Bit vector: Need multiple bitmaps per block size or size field in block header.

    • Linked list: Separate free lists per size class (like buddy system).

    • Allocation: Choose block size based on file size (rounded to nearest power-of-2 or fixed classes).

[!TIP]

Past Paper: "How could we take advantage of flexibility to improve performance?"

Answer: Match block size to file size to reduce internal fragmentation and metadata overhead. Use segregated free lists per size class.

UNIT 1: OS FUNDAMENTALS (Brief – Less Exam Weight but Asked)

Definition & Objectives

• OS: System software managing hardware/resources, providing platform for applications.

• Objectives: Convenience, efficiency (resource utilization), ability to evolve, security/protection.

Major Services

• Process management, memory management, I/O management, file system, protection, command interpreter, networking, error detection.

Types of OS

• Batch: Jobs submitted in batches; no interactivity.

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

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

• Real-Time: Hard/soft deadlines; often no virtual memory.

• Distributed: Network of independent computers; appears as single system.

• Network: Emphasizes networking services (e.g., Windows Server).

OS Structures

• Monolithic: All OS components in kernel; fast but hard to maintain.

• Layered: Hierarchical layers; each uses only lower layers. Easier to debug.

• Microkernel: Minimal kernel (IPC, memory, CPU); services as user processes. More secure, modular.

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

System Calls

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

• Importance: Provide controlled access to hardware; ensure protection and security.

Design Issues

• Spooling: Overlap I/O and CPU by buffering I/O to disk (e.g., printing). Simulates parallel operation.

• Buffering: Temporary storage for data transfer between devices of different speeds. Smooths bursts.

Protection

• CPU Modes: Kernel (privileged) vs User (non-privileged). System calls switch to kernel.

• Memory Protection: Base/limit registers or paging (valid/invalid bits).

• I/O Protection: All I/O instructions privileged; user programs request via system calls.

Final Note: Past papers heavily test numerical problems (scheduling, Banker’s, page faults, disk scheduling). Practice with given process tables, reference strings, and matrices. Always show steps: Gantt chart → compute completion → waiting time. For Banker’s, compute Need matrix first, then simulate safety.