Operating Systems (CY-404) - Unit 1 Short Notes

I. INTRODUCTION & OVERVIEW

Evolution of Operating Systems

• Generations:

  1. Batch: No direct user interaction; jobs grouped by similar requirements; CPU idle during I/O.

  2. Multi-programmed: Multiple jobs in memory; CPU switches to another when one waits for I/O; improves utilization.

  3. Time-sharing: Multi-programming + rapid context switching; interactive use; CPU time sliced among users (quantum).

  4. Parallel/Distributed: Multiple CPUs/processors; distributed OS manages networked, independent systems as single entity.

  5. Real-time: Hard/soft deadlines; often no virtual memory; priority-driven preemptive scheduling.

  6. Mobile: Specialized for resource-constrained devices; touch interfaces; app-centric; power management.

• Driving Forces: Hardware advances (multiprocessors, storage), user needs (interactivity, security), application demands (graphics, real-time).

Functions & Services of an OS

Operating System Characteristics

• Concurrency: Multiple tasks in progress (logical).

• Parallelism: Multiple tasks executing simultaneously (physical, requires multi-core).

• Persistence: Data/state survives process termination (stored on disk).

• Sharing: Controlled access to resources (CPU, memory, files).

• Security: Protection against internal/external threats.

• Portability: OS runs on different hardware (abstraction).

• Reliability: Fault tolerance, mean time between failures (MTBF).

Operating System Structures

UNIX/Linux Structure:

Hardware

  ↓

Kernel (process, memory, file, I/O, network mgmt)

  ↓

System Libraries (POSIX, C library - wrappers for syscalls)

  ↓

Shell & System Utilities (user interface, tools)

Windows NT Structure (Hybrid):

Hardware

  ↓
**Kernel** (scheduler, memory manager, I/O manager, security)

  ↓
**Executive** (object manager, process/thread manager, I/O manager)

  ↓
**Subsystems** (Environment subsystems: Win32, POSIX; Protection subsystems)

[!TIP] Exam Focus: Be prepared to draw and explain UNIX/Linux layered structure and Windows NT hybrid structure. "Process-based kernel" means kernel is structured around processes/threads, not monolithic code.

II. PROCESS MANAGEMENT

The Process Concept

• Process vs. Program: Program is passive code; Process is active execution instance (code + data + resources + PCB).

• Process States: New → Ready → Running → Waiting → Terminated. (State transitions via scheduler, I/O, events).

• Process Control Block (PCB): OS data structure storing:

  • Process state, PID, program counter, CPU registers.

  • Memory management info (page tables, base/limit).

  • I/O status (open files, I/O devices allocated).

  • Scheduling info (priority, queue pointers).

  • Accounting info (CPU time used).

• Scheduling Queues: Job Queue (all processes), Ready Queue (in memory, ready to run), Device Queues (waiting for I/O).

Process Scheduling

• Criteria:

  • CPU Utilization: % time CPU busy.

  • Throughput: # processes completed / 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).

• Scheduling Algorithms:

  • Non-Preemptive:

    1. FCFS/FIFO: Processes in arrival order. Simple, but convoy effect (long job blocks short ones).

    2. SJF/SRTF (Shortest Remaining Time First): Select process with smallest next CPU burst. Optimal for minimizing average waiting time (requires future knowledge). SRTF is preemptive version.

    3. Priority Scheduling: Each process has priority; highest priority runs. Can be preemptive/non-preemptive. Starvation possible (solution: aging - gradually increase priority of waiting jobs).

  • Preemptive:

    1. Round Robin (RR): Each ready process gets time quantum (q). Cyclically moves through ready queue. Context switch overhead if q too small; FCFS-like if q large.

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

    3. Multilevel Feedback Queue (MLFQ): Multiple queues with different time quanta. Process moves between queues based on behavior (e.g., if uses all quantum, demoted to lower-priority queue). Balances response time & CPU burst preference.

Gantt Chart & Calculation Example (SJF, non-preemptive):

Processes: P1(6), P2(8), P3(7), P4(3) all arrive at 0.

Order: P4 → P1 → P3 → P2

Gantt: | P4 | P1 | P3 | P2 |

Time:   0    3    9   16   24

• Waiting Time: P4=0, P1=3, P3=9, P2=16 → Avg WT = (0+3+9+16)/4 = 7

• Turnaround Time: P4=3, P1=9, P3=16, P2=24 → Avg TAT = (3+9+16+24)/4 = 13

[!TIP] Common Pitfall: SJF requires knowledge of next CPU burst length (not always possible). In problems, given burst times are assumed known. SRTF preempts if a new shorter job arrives.

Threads & Concurrency

• Motivation: Reduce context switch overhead vs. processes; share address space easily; improve responsiveness (UI thread); enable parallelism on multi-core.

• User-Level vs. Kernel-Level Threads:

• Virtual vs. Real Concurrency: Virtual Concurrency - single CPU, threads time-sliced (illusion of parallel). Real Concurrency - multiple CPUs/cores, threads truly execute in parallel.

Interprocess Communication (IPC) & Synchronization

• Critical Section Problem: Code segment accessing shared resource (variable, file). Must ensure mutual exclusion.

• Race Condition: Outcome depends on timing/ordering of concurrent accesses.

• Solutions:

  1. Peterson's Solution: For two processes; uses flag[] and turn shared variables. Assumes sequential consistency.

  2. Semaphores: Integer variable S with atomic wait(S) (P) and signal(S) (V) operations.

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

     • Counting Semaphore: Any integer; for resource counting.

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

  3. Monitors: High-level construct; shared variables only accessible via monitor procedures; mutual exclusion automatic. Uses condition variables with wait() and signal().

• IPC Mechanisms:

  • Shared Memory: Fastest; processes attach to common memory region. Needs synchronization (semaphores).

  • Message Passing: send()/receive(); can be synchronous (blocking) or asynchronous (non-blocking). Used in distributed systems.

  • Pipes: Unidirectional byte stream (Unix |). Named pipes (FIFOs) allow unrelated processes.

  • Sockets: Endpoint for network communication (TCP/UDP).

• Classic Problems:

  • Producer-Consumer (Bounded Buffer): Semaphores: empty (count of empty slots), full (count of full slots), mutex (for buffer access).

  • Reader-Writer: Prioritize readers or writers; use semaphores (rw_mutex, mutex, read_count).

  • Dining Philosophers: 5 philosophers, 5 forks. Solution with semaphore per fork (may deadlock) or monitor (avoid deadlock).

Deadlocks

• Definition: Set of processes blocked; each holds at least one resource and waits for another held by another process in set.

• Necessary Conditions (Coffman Conditions):

  1. Mutual Exclusion: Resource non-shareable.

  2. Hold and Wait: Process holds resources while waiting for others.

  3. No Preemption: Resources only released voluntarily.

  4. Circular Wait: Circular chain of processes waiting for resources.

• Handling Methods:

  1. Prevention: Design system to violate at least one condition.

     • Violate Mutual Exclusion: Make resources shareable (spooling).

     • Violate Hold and Wait: Request all resources at once (low utilization) or release all before requesting new.

     • Violate No Preemption: Preempt resources (complex, may cause rollback).

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

  2. Avoidance: Dynamically check if request leads to unsafe state. Requires maximum claim knowledge in advance.

     • Resource-Allocation Graph (RAG) Algorithm: For single instance resources; cycle = deadlock.

     • Banker's Algorithm (Safety Algorithm): For multiple instances. Checks if system is in safe state (exists safe sequence).

       • Safety Algorithm Steps:

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

         (ii) Find i such that Finish[i]==false and Need[i] <= Work. If none, go to (iv).

         (iii) Work = Work + Allocation[i], Finish[i]=true, repeat (ii).

         (iv) If Finish[i]==true for all i, state is safe.

       • Request Handling: If Request[i] <= Need[i] and Request[i] <= Available, pretend allocate and run safety. If safe, grant; else, wait.

  3. Detection & Recovery: Allow deadlock, detect periodically, recover.

     • Detection Algorithm: Similar to safety but Request matrix is current allocation; cycle in Wait-for graph (for single instance) or RAG indicates deadlock.

     • Recovery: Process termination (all or one by one), Resource preemption (checkpoint/rollback, victim selection).

[!TIP] Banker's Algorithm is MUST. Practice with given matrices (Need = Max - Allocation). Safe state means there exists an order <P1, P2,...> where each process's Need <= Work (Available + sum of Allocation of finished processes).

III. MEMORY MANAGEMENT

Background & Requirements

• Base & Limit Registers: Base holds start physical address; limit holds range. CPU generates logical address; MMU adds base, checks against limit (protection).

• Relocation: Ability to move process in physical memory (dynamic relocation via base register).

• Sharing: Allow multiple processes access to same memory (code, data).

• Fragmentation:

  • Internal: Wasted space within allocated region (e.g., fixed partitioning, paging last frame).

  • External: Wasted space between allocated regions (holes in variable partitioning). Solved by compaction (expensive) or non-contiguous allocation (paging, segmentation).

Memory Allocation Strategies

• Contiguous Allocation:

  • Fixed Partitioning: Memory divided into fixed-size partitions. Internal fragmentation (process smaller than partition).

  • Variable Partitioning: Partitions of variable size; allocate exactly needed size. External fragmentation (many small holes).

  • Allocation Algorithms (for variable):

    1. First-Fit: Allocate first hole big enough. Fast, but may cause many small holes at start.

    2. Best-Fit: Allocate smallest hole big enough. Minimizes leftover, but many tiny holes, slow (search entire list).

    3. Worst-Fit: Allocate largest hole. Aims to leave large leftover, but may cause large holes, slow.

    • Compaction: Move processes to one end to create large free hole; requires dynamic relocation (base register).

Paging

• Mechanism: Divide physical memory into fixed-size frames (power of 2, e.g., 4KB). Logical memory into same-size pages. Page table maps page number → frame number.

• Address Translation: Logical address = (page#, offset). Physical address = (frame#, offset). Offset unchanged.

• Protection: Valid/Invalid bit in page table entry. Invalid → page fault.

• Page Table Structure: Hierarchical, hashed, inverted (for large address spaces).

• Translation Lookaside Buffer (TLB): Fast associative cache storing recent (page#, frame#) mappings. Hit ratio crucial for performance.

  • EAT (Effective Access Time) with TLB:

$$EAT = (1 - h) \times (t_{TLB} + t_{mem}) + h \times (t_{TLB} + t_{mem})$$

    where `h` = hit ratio, `t_TLB` = TLB access time, `t_mem` = memory access time.

    Actually: `EAT = t_TLB + (1-h) * 2*t_mem + h * t_mem = t_TLB + (2 - h)*t_mem`.

Page Replacement Algorithms (Demand Paging)

• When page fault occurs: OS finds free frame (if none, replace victim page), reads page from disk into frame, updates page table, restarts instruction.

• Algorithms (reference string, frames):

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

     • Belady's Anomaly Example: Ref: 1,2,3,4,1,2,5,1,2,3,4,5. With 3 frames: 9 faults; with 4 frames: 10 faults.

  2. LRU (Least Recently Used): Replace page not used for longest time. Approximations: LRU stack (reference bit), additional reference bits (shift register).

  3. OPT (Optimal/Min): Replace page whose next reference is farthest in future. Theoretical minimum, not implementable (needs future).

Segmentation

• Motivation: User's view of memory (segments: code, data, stack, heap). Each segment has name, length.

• Mechanism: Logical address = (segment#, offset). Segment Table maps segment# → (base, limit). Base + offset = physical address; check offset < limit.

• Advantages over Paging: Logical grouping, protection (read/write/execute per segment), sharing (share entire segment).

• Segmentation with Paging (Paged Segmentation): Each segment divided into pages. Segment table points to page tables. Intel Pentium uses this. Combines benefits: user view (segments) + efficient memory use (paging).

Virtual Memory & Demand Paging

• Virtual Memory: Abstraction that process memory can be larger than physical memory. Backed by disk (swap space).

• Demand Paging (Lazy Swapping): Only load pages when needed (on page fault).

• Page Fault Handling Steps:

  1. Trap to OS (invalid reference → page fault).

  2. Check if reference is legal (within segment limit).

  3. Find free frame (if none, replace victim page).

  4. Schedule disk I/O to read required page into frame.

  5. Update page table (valid bit, frame#).

  6. Restart interrupted instruction.

• Performance - EAT:

$$EAT = (1 - p) \times t_{mem} + p \times (t_{pagefault} + t_{mem})$$

where `p` = page fault rate, `t_pagefault` = service time (disk I/O + swap in/out).

• Thrashing: High page fault rate → OS spends most time swapping → low CPU utilization. Cause: Degree of multiprogramming too high for available memory.

  • Working-Set Model: Each process has working set (pages referenced in recent Δ time). If sum of working set sizes > available frames → thrashing.

  • Page-Fault Frequency (PFF): Directly control page fault rate; if too high, suspend process; if too low, may have too many frames.

Memory Management in Specific OS

• UNIX (BSD): Demand paging, modified clock page replacement (approx LRU), kernel memory allocator (slab allocator in modern Linux, buddy system in BSD).

• Windows NT: Virtual address space (2GB user, 2GB kernel by default), page file (swap), working set (min/max limits), page replacement uses modified clock algorithm.

Overlay

• Concept: Load only necessary parts of program into memory; rest on disk. Programmer specifies overlay structure.

• Usefulness: Executes programs larger than physical memory without virtual memory. Manual, complex, largely obsolete.

[!TIP] Numerical Focus: Page fault calculation (FIFO, LRU, OPT), EAT with/without TLB, Belady's anomaly. Understand why FIFO can have anomaly but LRU/OPT do not.

IV. STORAGE MANAGEMENT: FILE SYSTEMS & MASS STORAGE

File System Structure & Concepts

• File Attributes: Name, identifier (inode #), type, location, size, protection, time (create, access, modify).

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

• File Types: Regular, directory, character special, block special.

• File System Layers (Top to Bottom):

  1. Logical File System: File control block (FCB), directory operations, protection.

  2. File Organization Module: Maps logical blocks to physical blocks (allocation methods).

  3. Basic File System: Allocates/free blocks, buffers.

  4. I/O Control: Device drivers, interrupts, DMA.

Directory Structures

File Allocation Methods

1. Contiguous: Allocate contiguous blocks. Fast access (seek + sequential read). External fragmentation; file growth difficult.

2. Linked Allocation:

   • Singly-linked: Each block has pointer to next. No external fragmentation; can grow easily. Slow access (sequential), space for pointers, reliability (lost pointer = lost rest).

   • FAT (File Allocation Table): Central array; each entry points to next block. Fast traversal (FAT cached), no external fragmentation. FAT entry per cluster.

3. Indexed Allocation: Bring all pointers together into index block.

   • Single-level: Index block holds all pointers. Small files efficient; large files limited by index block size.

   • Multi-level (UNIX inode): Inode has 12 direct, 1 single indirect, 1 double indirect, 1 triple indirect block pointers. Supports large files.

   • Linked (Multilevel): Index blocks linked (e.g., FAT is linked multi-level).

Free Space Management

• Bit Vector (Bitmap): 1 bit per block (1=free, 0=allocated). Compact, easy to find contiguous free space.

• Linked List: Free blocks linked together; pointer stored in free block itself.

• Grouping: First block in group contains addresses of many free blocks; last block points to next group.

• Counting: Keep track of contiguous free blocks (like variable partitioning).

Disk Management & Scheduling

• Disk Structure: Platters → Tracks → Sectors (blocks). Cylinder = tracks aligned vertically.

• Performance Parameters:

  • Seek Time: Move head to correct track.

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

  • Transfer Time: Read/write sector.

  • Access Time = Seek Time + Rotational Latency.

  • Bandwidth: Total bytes transferred / total time.

• Disk Scheduling Algorithms (reduce seek time):

  • FCFS: Simple, fair, but high average seek.

  • SSTF (Shortest Seek Time First): Select request closest to current head position. Starvation possible (edges ignored).

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

  • C-SCAN (Circular SCAN): Head moves in one direction, services requests, jumps back to start without servicing (more uniform wait).

  • LOOK / C-LOOK: SCAN/C-SCAN but only go as far as last request in direction, then reverse/jump.

• Example Calculation (FCFS):

  
  Head starts at 143, previous at 125. Queue: 86,147,91,177,94,150,102,175,130.
  
  Movement: |143-86|=57, |86-147|=61, |147-91|=56, |91-177|=86, |177-94|=83, |94-150|=56, |150-102|=48, |102-175|=73, |175-130|=45.
  
  Total = 57+61+56+86+83+56+48+73+45 = **565 tracks**.
  
  

File Systems in Specific OS

[!TIP] Draw & Explain: Tree-structured directory, acyclic-graph (with links), FAT structure, inode with direct/indirect pointers. For disk scheduling, always draw head movement on number line.

V. INPUT/OUTPUT (I/O) SYSTEMS

I/O Fundamentals

• Hardware: Devices (disk, keyboard), controllers (interface between device and bus), buses (data/control/address lines).

• I/O Functions:

  • Device Independence: Programs use generic operations (read/write), not device-specific.

  • Error Handling: I/O errors reported to OS, possibly to application.

  • Buffering: Store data temporarily to cope with speed mismatch (CPU vs I/O).

  • Caching: Keep copy of data in faster memory (disk cache).

  • Spooling: Overlap I/O of one job with computation of another (e.g., print spooling).

• Logical I/O Structure Example (Read):

  
  Application → System Call (read) → I/O System (buffering, caching) → Device Driver → Controller → Device
  
  

I/O Techniques

I/O Buffering

• Purpose: Decouple CPU & I/O; handle speed mismatch; allow read-ahead/write-behind.

• Strategies:

  1. Single Buffer: OS allocates buffer in kernel. Process blocked until I/O completes into buffer, then copies to user space (double copy).

  2. Double Buffer: Two buffers; process can process one while I/O fills other. Overlaps I/O & compute.

  3. Circular Buffer: Multiple buffers in ring; producer/consumer pointers. Used for streams (audio, video).

Kernel I/O Subsystem

• Functions:

  • Scheduling: Queue I/O requests (e.g., disk scheduling).

  • Buffering: Manage memory buffers for I/O data.

  • Caching: Maintain cache of data (disk cache).

  • Spooling: Manage spooling queues (printers).

  • Device Status Monitoring: Keep status info, error counters.

  • Error Handling: Retry, fail operations.

• Structure:

  • Device-Independent Interface: Common functions (open, close, read, write) for all devices.

  • Device Drivers: Kernel modules, one per device/controller. Provide device-dependent interface to hardware.

  • Interrupt Handlers: Service device interrupts.

I/O Management in Specific OS

• UNIX I/O:

  • System calls: read, write, lseek, ioctl (control), stat (info).

  • Device Files: All I/O devices appear as files in /dev. Use same calls.

  • STREAMS: Full-duplex communication between user process and device driver (kernel modules: stream head, module, driver).

• Windows I/O:

  • I/O Manager: Kernel component; provides synchronous/asynchronous I/O.

  • Device Drivers: WDM (Windows Driver Model) for compatibility.

  • I/O Request Packet (IRP): Data structure sent from I/O manager to driver; contains operation type, buffers, etc.

  • Asynchronous I/O: I/O Completion Ports for efficient notification of many async I/O completions.

VI. SYSTEM CALLS & PROTECTION/SECURITY

System Calls (Interface to OS Services)

• Process Management: fork() (create child), exec() (replace image), wait() (wait for child), exit() (terminate), getpid() (PID), kill() (send signal).

• File Management: open(), close(), read(), write(), lseek() (reposition), stat() (info), ioctl() (control), chmod() (change mode), unlink() (delete).

• Directory Management: mkdir(), rmdir(), link() (create hard link), unlink() (remove link).

• Protection: chmod(), chown() (change owner).

Protection & Security

• Goals: Confidentiality (no unauthorized read), Integrity (no unauthorized modify), Availability (accessible when needed).

• Protection Mechanisms:

  • Access Control: ACLs (Access Control Lists) - per-file list of users/permissions. Capabilities - unforgeable tokens granting access.

  • Authentication: Passwords, biometrics, tokens, multi-factor.

  • Encryption: Data at rest/in transit.

• Security Threats & Attacks:

  • Viruses: Attach to programs, replicate.

  • Worms: Self-replicate over network.

  • Trojan Horses: Disguised malicious code.

  • Logic Bombs: Triggered by event/time.

  • Denial-of-Service (DoS): Overwhelm resource (CPU, network, disk).

• OS Security: User authentication (login), memory protection (base/limit, paging), I/O protection (privileged instructions, I/O access control), TOCTOU (Time-of-Check-to-Time-of-Use) race conditions in file access.

VII. SPECIAL TOPICS & COMPARISONS (FREQUENTLY ASKED)

UNIX vs. Windows OS Comparisons

Distributed vs. Multiprocessor OS

Network Operating System (NOS)

• Characteristics:

  • Users aware of multiple machines (remote login, file access).

  • Heterogeneity: Support diverse hardware/OS.

  • Remote Access: Transparent file/device sharing.

  • Fault Tolerance: Continue if one node fails.

• Differences from Traditional OS:

  • Traditional OS manages one system's resources.

  • NOS extends OS to manage network-wide resources (files, printers, compute).

  • Provides network transparency (remote access like local).

Utility Programs

• Programmer Utilities: Compilers, assemblers, linkers, loaders, debuggers, editors.

• System Utilities: Disk defragmenter, backup/restore, antivirus, performance monitors (Task Manager), file comparison, disk cleanup.

• File Management: File viewers, archivers (zip), search tools.

Tape Organization

• Physical Structure: Magnetic tape on reels; tracks parallel to length; block = unit of read/write (multiple records).

• Tape Drive: Read/write head; moves tape sequentially.

• Blocking: Grouping records into blocks (fixed/variable). Blocking factor = records per block.

• Operations: Forward/Backward spacing (over blocks/records), rewind, write EOF (tape mark), read forward.

• Characteristics: High capacity, low cost/byte, sequential access only, slow (meters/sec), used for backup/archiving.

[!TIP] Comparison Questions: Always structure answer in point-wise table format. For UNIX vs Windows, focus on memory, file system, I/O as per past papers. For Distributed vs Multiprocessor, highlight communication, fault tolerance, scalability.