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

1. Introduction to Operating Systems

Definition: An Operating System (OS) is system software that manages hardware resources, provides common services to applications, and acts as an intermediary between users and computer hardware.

Objectives:

• Abstraction: Hide hardware complexity.

• Resource Management: Efficient allocation of CPU, memory, I/O.

• Concurrency: Support multiple processes/threads.

• Security & Protection: Prevent unauthorized access.

• Convenience: User-friendly interface (CLI/GUI).

• Performance: Maximize throughput, minimize response time.

Major Services:

Types of Operating Systems:

OS Structure:

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

• Layered: OS divided into layers, each using only lower layers (e.g., THE). Easier to debug but performance overhead.

• Microkernel: Minimal kernel; services as user-space processes (e.g., Mach, QNX). More secure and modular but slower due to IPC.

System Calls: Interface between user programs and OS (e.g., fork(), read(), open()). Provide controlled access to hardware.

Design Issues:

• Spooling (Simultaneous Peripheral Operations On-Line): Buffer I/O on disk to overlap I/O and CPU (e.g., print spooling).

• Buffering: Temporary storage to match speed differences between producer and consumer.

[!TIP] Compare monolithic vs microkernel: monolithic = performance, microkernel = modularity.

2. Process Management

Process Concept: A process is a program in execution. It consists of:

• Text (code), Data (global variables), Stack (function calls), Heap (dynamic memory).

Process Control Block (PCB): OS data structure containing:

• Process state, program counter, CPU registers, memory management info (page table, base/limit), I/O status, scheduling info, accounting info.

Process States:

1. New: Being created.

2. Ready: Waiting for CPU.

3. Running: Executing on CPU.

4. Waiting/Blocked: Waiting for I/O or event.

5. Terminated: Execution finished.

State Transitions:

• Admit (new → ready)

• Dispatch (ready → running)

• Timeout/interrupt (running → ready)

• I/O request (running → waiting)

• I/O complete (waiting → ready)

• Exit (running → terminated)

Context Switch: Saving state of running process (PCB, registers) and loading state of next process. Overhead due to no useful work during switch.

Operations on Processes:

• fork(): Create child process (copy of parent). Returns child PID to parent, 0 to child.

• exec(): Replace process memory image with new program.

• wait(): Parent waits for child to terminate.

• exit(): Terminate process, release resources.

Scheduling Criteria:

• CPU Utilization: % time CPU busy.

• Throughput: # processes completed per unit time.

• Turnaround Time: Completion time – arrival time.

• Waiting Time: Time spent in ready queue.

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

Scheduling Algorithms:

Gantt Chart: Timeline showing process execution order. Used to compute waiting/turnaround times.

Example Calculation (Processes P1(5), P2(3), P3(8), all arrive at 0):

• FCFS: Order P1, P2, P3. Waiting: P1=0, P2=5, P3=8. Avg = (0+5+8)/3 = 4.33 ms.

• SJF: Order P2, P1, P3. Waiting: P2=0, P1=3, P3=8. Avg = (0+3+8)/3 = 3.67 ms.

• RR (quantum=2): P1(2), P2(2), P3(2), P1(2), P1(1), P3(2), P3(2), P3(2). Avg waiting > SJF.

[!TIP] For SJF, if all processes arrive at same time, it minimizes average waiting time. SRTF for varying arrivals.

3. Process Synchronization

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

Requirements:

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

2. Progress: If no process in CS and some wish to enter, decision must be made in finite time.

3. Bounded Waiting: Process waiting to enter CS must eventually be allowed.

Synchronization Tools:

Semaphores:

• Counting Semaphore: Integer value ≥ 0.

• Binary Semaphore (Mutex): Values 0 or 1.

• Wait (P): while (S <= 0); S--; (busy wait) or block if S=0.

• Signal (V): S++; wake up waiting process if any.

• Atomicity: Wait and Signal must be indivisible; implemented with hardware instructions like TestAndSet.

TestAndSet Implementation (minimal busy waiting):

bool TestAndSet(bool *target) {

    bool old = *target;

    *target = true;

    return old;

}
// Wait for mutex:

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

// Critical section

lock = false; // Signal

Better: Use waiting queue to avoid busy wait.

Monitors: High-level construct with procedures and shared variables; only one process active in monitor at a time. Condition variables for waiting: wait(c), signal(c).

Classic Problems:

1. Producer-Consumer (Bounded Buffer): Semaphores mutex (binary), empty (counting), full (counting).

2. Readers-Writers: Multiple readers allowed simultaneously; writers exclusive. First readers-preference may starve writers.

3. Dining Philosophers: N philosophers, each needs two forks. Resource hierarchy (pick lower-numbered fork first) prevents deadlock but may starve.

Starvation vs Deadlock:

[!TIP] Deadlock involves circular wait; starvation is indefinite postponement without circularity.

4. Deadlock

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

Necessary Conditions (all must hold):

1. Mutual Exclusion: Resources non-shareable.

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: Circular chain of processes, each waiting for resource held by next.

Handling Methods:

1. Prevention: Design to ensure at least one condition never holds.

   • Break Mutual Exclusion: Make resources shareable (e.g., read-only files).

   • Break Hold and Wait: Require all resources at once (may cause low utilization).

   • Break No Preemption: Preempt resources if possible (e.g., CPU registers).

   • Break Circular Wait: Impose total ordering on resources; request in increasing order.

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

   • Resource Allocation Graph (RAG): For single instance resources, cycle indicates deadlock.

   • Banker’s Algorithm (multiple instances):

     • Data Structures:

       • Available: Vector of available instances.

       • Max: Matrix of maximum demand per process.

       • Allocation: Matrix of current allocation.

       • 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 all Finish[i] = true, system is safe; safe sequence is order of finishing.

     • Resource Request Algorithm:

       • If Request_i ≤ Need_i, proceed; else error.

       • If Request_i ≤ Available, allocate provisionally; else process waits.

       • Check safety with provisional allocation; if safe, allocate; else wait.

3. Detection and Recovery:

   • Detection:

     • Single instance: RAG cycle detection.

     • Multiple instances: Wait-for graph (process nodes, edge Pi→Pj if Pj holds resource Pi wants). Cycle detection.

   • Recovery:

     • Process termination: Abort all deadlocked processes or one by one until cycle broken.

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

Case Study: Banker’s algorithm (Nov 2023):

Processes P1, P2, P3; total tape drives = 9.

Allocation: P1=3, P2=1, P3=3 → Available = 2.

Max: P1=7, P2=6, P3=6.

Need: P1=4, P2=5, P3=3.

Safety: Work=2. No process has Need ≤ Work → unsafe state → deadlock possible.

[!TIP] For RAG, a cycle means deadlock only if each resource has single instance. For multiple instances, use wait-for graph.

5. Memory Management

Background:

• Relocation: Programs loaded anywhere; base/limit registers.

• Protection: Prevent access to others’ memory; hardware checks.

• Sharing: Multiple processes share code/data.

• Logical vs Physical Address Space: Logical generated by CPU; physical seen by memory. Translated by MMU.

Memory Partitioning:

1. Fixed Partitioning: Fixed-size partitions (equal/unequal). Internal fragmentation.

2. Dynamic Partitioning: Variable-size partitions. External fragmentation; solved by compaction.

   • Allocation Algorithms:

     • First-Fit: Allocate first block large enough.

     • Best-Fit: Allocate smallest block large enough.

     • Worst-Fit: Allocate largest block.

Paging:

• Divide physical memory into frames (fixed size). Logical memory into pages.

• Page Table: Per-process, maps page number → frame number.

• Address Translation: Logical = <page#, offset> → Physical = <frame#, offset>.

• Protection: Bits in page table entry (read-only, read-write, execute).

• Sharing: Multiple processes can share same page.

Page Table Implementations:

• Hierarchical (Multi-level): Page table paged (e.g., two-level). Reduces contiguous memory needed but adds accesses.

• Hashed: Hash page number to bucket; each bucket has linked list. Good for sparse large spaces.

• Inverted: One entry per physical frame; stores process ID and virtual page. Fast lookup but needs hash.

Translation Lookaside Buffer (TLB):

• Hardware cache for page table entries.

• TLB Hit: Fast translation.

• TLB Miss: Access page table in memory.

• Effective Access Time (EAT):

  Let:

  • $$\displaystyle t_{tlb} $$ = TLB access time

  • $$\displaystyle t_{mem} $$ = memory access time

  • $p$ = TLB miss ratio

  On hit: $$\displaystyle t_{tlb} + t_{mem} $$

  On miss: $$\displaystyle t_{tlb} + 2t_{mem} $$

  \boxed{EAT = (1-p)(t_{tlb} + t_{mem}) + p(t_{tlb} + 2t_{mem}) = t_{tlb} + t_{mem} + p \cdot t_{mem}}

[!TIP] Example: t_tlb=20ns, t_mem=100ns, hit ratio=80% → p=0.2 → EAT = 20 + 100 + 0.2×100 = 140ns.

Page Replacement Algorithms:

• FIFO: Replace oldest page. May suffer Belady’s anomaly.

• OPT (Optimal): Replace page not used for longest time (theoretical minimum).

• LRU: Replace least recently used (approx OPT).

• Second-Chance: FIFO with reference bit; if referenced, give second chance.

• Clock: Circular list with hand; if reference bit=0, replace; else clear bit and advance.

• Counting: LFU (least frequently used), MFU (most frequently used).

Page Fault Calculation:

Simulate algorithm with reference string and frames. Count faults when page not in memory.

Thrashing:

• High page fault rate due to insufficient frames or overcommitment.

• Cause: Process’ working set > allocated frames → frequent faults → CPU spends time swapping.

• Working Set Model: For process, working set W(t, Δ) = pages referenced in [t–Δ, t].

• Page Fault Frequency: Monitor fault rate; adjust frames accordingly.

Segmentation:

• Logical address = <segment-number, offset>.

• Segment table: base address and limit for each segment.

• External fragmentation (like dynamic partitioning).

Segmented Paging:

• First segment, then page within segment.

• Combines benefits: protection/sharing at segment level, no external fragmentation at page level.

• Example: Intel x86.

Demand Paging:

• Load pages only when needed (on page fault).

• Advantages: Less I/O, less memory, more processes in memory.

• Effective Access Time:

  Let:

  • $m$ = memory access time

  • $p$ = probability of page fault

  • $D$ = page fault service time (disk access + transfer + restart)

  \boxed{EAT = (1-p) \cdot m + p \cdot (D + m) = m + p \cdot D}

Memory Protection in Paging:

• Page table entry has protection bits (read-only, read-write, execute).

• Hardware checks every memory reference; violation → trap to OS.

6. I/O and Disk Management

File System:

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

File Operations: Create, delete, read, write, truncate, seek, get/set attributes.

File Access Methods:

1. Sequential: Read next record; reset to beginning (tape).

2. Direct (Random): Read/write at arbitrary position by block number (databases).

3. Indexed: Index block contains pointers to data blocks; allows direct access via index (e.g., ISAM).

File Organization and Allocation Methods:

Free-Space Management:

• Bit Vector: 1 bit per block; 1=free, 0=allocated. Simple, but large for big disks.

• Linked List: Free blocks linked together; each block contains list of free blocks. Problem: traverse long list; on removal, need to coalesce adjacent free blocks.

• Grouping: First block in list contains many free block addresses; when exhausted, read next block.

• Issues with Simple Free List on Removal: When a file is removed, its blocks are added to free list. If not sorted, allocation may become inefficient. Need to coalesce adjacent free blocks to form larger holes, requiring checking neighbors (may need to read block headers).

File System Granularity:

• Allocate disk space in different block sizes (e.g., 4KB as one block or eight 512-byte blocks).

• Advantage: Small files use small blocks (save space); large files use large blocks (reduce fragmentation and I/O overhead).

• Modifications: Track free blocks of each size separately (multiple free lists) or use buddy system.

Disk Structure:

• Tracks on platter; cylinders (same track on all platters).

• Seek Time: Time to move head to correct track.

• Rotational Latency: Time for desired sector to rotate under head.

• Transfer Time: Time to read/write data as sector passes.

Disk Scheduling Algorithms:

Head Movement Calculation:

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

• FCFS: Sum of absolute differences: |53–98|+|98–183|+... = 640 (example).

• SSTF: At each step choose closest.

• SCAN (assume decreasing first): 53→37 (16), 37→14 (23), 14→0 (14), 0→65 (65), 65→67 (2), 67→98 (31), 98→122 (24), 122→124 (2), 124→183 (59) = 236.

• C-SCAN (increasing direction): 53→65 (12), 65→67 (2), 67→98 (31), 98→122 (24), 122→124 (2), 124→183 (59), 183→max (e.g., 4999) = 4816, jump to 0, 0→14 (14), 14→37 (23) = 4983.

Disk Performance and Loading Programs:

• Load Time = seek time + rotational latency + transfer time per page.

• Impact of Page Size: Larger page size → fewer page faults but more data transferred per fault; internal fragmentation in memory.

7. Additional and Advanced Topics

Protection in Operating Systems:

• Hardware Resources: CPU mode (user/kernel), I/O privilege (only kernel), memory protection (base/limit, paging).

• Access Control Mechanisms:

  • Access Control Lists (ACL): Per file, list of users and permissions.

  • Capabilities: Tokens granting access; can be passed between processes.

  • Role-Based Access Control (RBAC): Permissions based on roles.

Local vs Global Page Allocation:

• Local: Each process keeps its own frames; replacement only among its pages.

  • Advantages: Performance isolation; one process’s thrashing doesn’t affect others.

  • Disadvantages: Underutilization of free frames; global free frames not used by needy processes.

• Global: System-wide pool; any process can replace any page.

  • Advantages: Better overall utilization; can balance load.

  • Disadvantages: Thrashing in one process can affect others; no isolation.

Comparison: Segmented Paging vs Hashed Page Tables:

• Segmented Paging:

  • Good for sparse address spaces with protection needs (segments group related pages).

  • Overhead: two-level translation (segment then page).

  • Used in x86 (segmentation optional).

• Hashed Page Tables:

  • Good for very large address spaces (e.g., 64-bit) where multi-level paging would be deep.

  • Hash collisions handled via linked lists; average access time depends on hash function.

  • Used in SPARC, UltraSPARC.

• Preference: Segmented paging when segmentation needed for logical grouping; hashed when address space huge and sparse.

Application Support for Random Access Indexed Files:

• Example: Database management system (DBMS) uses indexed allocation for fast record access by key. OS provides system calls to read/write by block number within file (direct access). Index file maintained by DBMS or OS (e.g., ISAM).

Spooling and Buffering:

• Spooling: Overlap I/O and CPU by storing I/O data on disk (e.g., print spooling). Allows multiple processes to output to printer without waiting.

• Buffering: Temporary storage in memory to match speed differences between producer and consumer (e.g., keyboard input buffered before process reads).

[!TIP] Spooling is for I/O devices; buffering is general for any speed mismatch.