UNIT 1: OPERATING SYSTEMS - COMPREHENSIVE NOTES

I. INTRODUCTION & OVERVIEW

Evolution of Operating Systems

• Generations:

  1. Batch: No direct user interaction. Jobs grouped & processed sequentially. (e.g., early IBM systems).

  2. Multiprogrammed: Multiple jobs in memory. CPU switches to another when one waits (I/O). Increases CPU utilization.

  3. Time-Sharing: Multiple users interact concurrently via terminals. CPU switches rapidly (time quantum). Interactive computing.

  4. Network: OS facilitates communication & resource sharing across interconnected computers (e.g., LAN).

  5. Distributed: Collection of independent computers appearing as a single system. Resources shared transparently.

  6. Real-Time (RTOS): Strict timing constraints. Hard RTOS: Must meet deadline (e.g., flight control). Soft RTOS: Occasional miss tolerable (e.g., multimedia).

• Driving Forces: Hardware cost reduction, need for resource sharing, user convenience, application complexity.

Major 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 sharing of resources (CPU, memory, I/O, files).

• Security: Protection against unauthorized access.

• Virtualization: Abstraction of physical resources (e.g., Virtual Memory).

• Asynchrony: Events occur unpredictably (handled via interrupts).

OS Structures & Design

• Simple/Layered: Monolithic (MS-DOS) vs. Layered (THE, UNIX). Layered simplifies debugging but can be inefficient.

• Microkernel: Minimal kernel (IPC, memory mgmt, scheduling). Drivers & FS run as user-space servers. More secure, modular, but performance overhead due to IPC (e.g., QNX, Mach).

• Modular: Loadable kernel modules (Linux). Balance between monolithic speed and microkernel flexibility.

• Virtual Machine: Host OS creates VMs running guest OSes. Provides isolation & platform independence (e.g., VMware, Hyper-V).

• Process-Based Kernel: Kernel organized as set of cooperating processes (often used in microkernels).

• System Boot: BIOS/UEFI → Bootloader (GRUB) → Kernel loaded into memory → Kernel initializes hardware & starts init/systemd.

System Calls & API

• Definition: Controlled entry points into kernel for requesting services.

• Categories & Examples:

  | Category | Purpose | Examples | | :--- | :--- | :--- | | Process Mgmt | Create/control processes/threads | fork(), exec(), wait(), exit(), pthread_create() | | File Mgmt | File operations | open(), read(), write(), close(), lseek(), stat(), mkdir() | | Device Mgmt | Device control | ioctl(), read(), write() (on device files) | | Info Maintenance | Get system/process info | time(), getpid(), alarm() | | Communication | IPC & networking | pipe(), shmget(), msgget(), socket(), bind() | | Protection | Security & access control | chmod(), chown(), umask() |

Operating System Types

[!TIP] Exam Focus: Distinguish Distributed (geographically dispersed, independent nodes, communication latency) vs. Multiprocessor (tightly coupled, shared memory, single OS instance).

II. PROCESS MANAGEMENT

Process Concept

• Process: An instance of a program in execution. Contains: program code, data, stack, heap, PCB.

• Program vs. Process: Program is passive code (file). Process is active execution state.

• Process State Diagram:

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

  • New: Being created.

  • Ready: Waiting for CPU.

  • Running: Executing on CPU.

  • Waiting/Blocked: Waiting for I/O/event.

  • Terminated: Execution finished.

• Process Control Block (PCB): Kernel data structure storing process state.

  • Fields: Process ID, Program Counter, CPU Registers, Scheduling Info (priority, queue pointers), Memory Management Info (page tables), I/O Status (open files, allocated devices), Accounting Info.

  • Significance: The only data structure that exists for every process. Enables context switching.

Process Scheduling

• 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.

• Schedulers:

  • Long-term (Job Scheduler): Admits jobs from job pool to main memory (controls degree of multiprogramming). Rarely used in modern systems.

  • Short-term (CPU Scheduler): Selects ready process to run on CPU. Very frequent.

  • Medium-term (Swapper): Swaps processes in/out of memory to control multiprogramming level.

• Context Switch: Saving state of running process (PCB, registers) to memory, loading state of next process. Pure overhead (no useful work).

CPU Scheduling Algorithms (High Frequency)

• Fundamentals:

  • Preemptive: OS can forcibly take CPU from running process (e.g., RR, SRTF, Priority with preemption).

  • Non-preemptive: Process relinquishes CPU voluntarily (e.g., FCFS, non-preemptive Priority, SJF).

  • Criteria:

    • CPU Utilization: % time CPU busy.

    • Throughput: # processes completed per unit time.

    • Turnaround Time: Total time from submission to completion. TAT = Completion - Arrival.

    • Waiting Time: Total time spent in ready queue. WT = TAT - Burst Time.

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

• Algorithms with Examples:

  • 1. First-Come, First-Served (FCFS):

    • Non-preemptive. Processes served in arrival order.

    • Convoy Effect: Long process holds CPU, short processes wait.

    • Example: P1(10), P2(1), P3(2) → Gantt: P1 | P2 | P3

      • WT: P1=0, P2=10, P3=11 → Avg WT = 7

      • TAT: P1=10, P2=11, P3=13 → Avg TAT = 11.33

  • 2. Shortest Job First (SJF) / Shortest Remaining Time First (SRTF):

    • SJF: Non-preemptive. Selects process with smallest next CPU burst. Optimal for minimizing Avg WT.

    • SRTF: Preemptive version. Compare remaining time of running vs. next burst of new arrival.

    • Requires knowledge/estimation of burst time (e.g., weighted average of past bursts).

    • Example (SJF): P1(10), P2(1), P3(2) → Gantt: P2 | P3 | P1

      • Avg WT = (0 + 2 + 3)/3 = 1.67

    • Starvation: Possible for long jobs if short jobs keep arriving.

  • 3. Priority Scheduling:

    • Each process has priority (integer, lower = higher priority).

    • Can be preemptive or non-preemptive.

    • Starvation: Low-priority processes may never run. Solved by Aging (gradually increasing priority of waiting processes).

    • Example (Non-preemptive): P1(10, p=3), P2(1, p=1), P3(2, p=3) → Order: P2, then tie P1/P3 (FCFS tie-break) → P2 | P1 | P3

  • 4. Round Robin (RR):

    • Preemptive. Ready queue treated as circular queue.

    • Each process gets time quantum (q). If burst > q, process is preempted and placed at end of queue.

    • q too large → FCFS. q too small → excessive context switches.

    • Example: P1(10), P2(1), P3(2), q=3 → Gantt: P1(3) | P2(1) | P3(2) | P1(3) | P1(3) | P1(1)

      • Calculate WT/TAT by tracking start/end times in Gantt chart.

[!TIP] Exam Tip: For scheduling problems, always draw Gantt chart first. Calculate Waiting Time (time spent in ready queue) and Turnaround Time (completion - arrival). Avg WT/TAT = sum/n.

Threads & Concurrency

• Motivation: Traditional processes have heavy context switch cost, no resource sharing within process. Threads are "lightweight processes" within same address space.

  • Responsiveness: One thread blocked doesn't halt entire process.

  • Resource Sharing: Threads share code, data, heap.

  • Economy: Cheaper to create/switch than processes (no address space change).

  • Scalability: Parallelism on multi-core CPUs.

• User-Level vs. Kernel-Level Threads:

  | Aspect | User-Level Threads (ULT) | Kernel-Level Threads (KLT) | | :--- | :--- | :--- | | Management | By user-space thread library | By OS kernel | | Scheduling | User-space, no kernel involvement | Kernel scheduler | | Blocking | Entire process blocks if one thread blocks (system call) | Only blocking thread blocked | | Context Switch | Fast (no mode switch) | Slower (kernel mode switch) | | Multiprocessing | One process on one CPU at a time (kernel sees one thread) | Kernel can schedule threads on multiple CPUs | | Examples | POSIX Pthreads (user), Java Green Threads | Windows, Linux Pthreads (kernel) | | Implementation | 1:1 (KLT), M:1 (ULT), M:N (Hybrid) | Primarily 1:1 |

Interprocess Communication (IPC)

• Shared Memory:

  • Processes share a region of memory (set up by OS).

  • Fastest IPC (no kernel involvement for data transfer).

  • Issues: Requires synchronization (semaphores/mutexes) to avoid race conditions on shared data.

• Message Passing:

  • Processes exchange messages via kernel-provided primitives (send(), receive()).

  • Direct Communication: Processes name each other explicitly.

  • Indirect Communication: Messages sent to/received from mailboxes/ports.

  • Synchronization: Can be blocking or non-blocking send/receive.

• Pipes:

  • Anonymous Pipes: Unidirectional, parent-child relationship, no name in filesystem (pipe()).

  • Named Pipes (FIFOs): Have a pathname, can be used by unrelated processes (mkfifo()).

Synchronization & Critical Section Problem

• Race Condition: Multiple processes/threads concurrently access shared data, outcome depends on execution order.

• Critical Section: Code segment accessing shared resource.

• Requirements for Solution:

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

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

  3. Bounded Waiting: There is a limit on number of times other processes can enter CS after a request.

• Software Solution: Peterson's Solution (2 processes)

  
  // Shared variables
  
  bool flag[2] = {false, false};
  
  int turn;
  
  
  
  // Process Pi (i = 0 or 1)
  
  flag[i] = true;
  
  turn = j; // other process index
  
  while (flag[j] && turn == j) ; // busy wait
  
  // Critical Section
  
  flag[i] = false;
  
  // Remainder Section
  
  

  • Assumptions: Sequential consistency, atomic read/write of shared variables. Not practical for modern hardware due to memory models.

• Hardware Support:

  • Test-and-Set: Atomically reads and sets a memory location. Returns old value.

  • Compare-and-Swap (CAS): Atomically compares and swaps if equal. Used for lock implementation.

  • Memory Barriers/Fences: Ensure memory operations order across CPU cores.

• Semaphores:

  • Integer variable S accessed via two atomic operations.

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

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

  • Binary Semaphore (Mutex): Value 0 or 1. For mutual exclusion.

  • Counting Semaphore: Value can be any integer. For counting resources.

  • Usage Example (Producer-Consumer with bounded buffer):

    
    semaphore mutex = 1; // for critical section
    
    semaphore empty = N; // empty slots count
    
    semaphore full = 0;  // full slots count
    
    
    
    producer() {
    
        while (true) {
    
            item = produce();
    
            wait(empty);
    
            wait(mutex);
    
            insert_item(item);
    
            signal(mutex);
    
            signal(full);
    
        }
    
    }
    
    

• Monitors:

  • High-level synchronization construct. Only one process active in monitor at a time.

  • Condition Variables: wait(cv), signal(cv) (or broadcast). Must be called inside monitor.

  • Dining Philosophers Solution (Monitor):

    
    monitor DiningPhilosophers {
    
        enum { THINKING, HUNGRY, EATING } state[5];
    
        condition self[5];
    
        
    
        void pickup(int i) {
    
            state[i] = HUNGRY;
    
            test(i);
    
            if (state[i] != EATING) self[i].wait();
    
        }
    
        void putdown(int i) {
    
            state[i] = THINKING;
    
            test((i+4)%5); test((i+1)%5);
    
        }
    
        void test(int i) {
    
            if (state[i]==HUNGRY && state[(i+4)%5]!=EATING && state[(i+1)%5]!=EATING) {
    
                state[i] = EATING;
    
                self[i].signal();
    
            }
    
        }
    
        // initialization: state[] = THINKING
    
    }
    
    

• Classic Problems:

  • Producer-Consumer: As shown above.

  • Reader-Writer: Readers may access concurrently, writers need exclusive access. Priority variants exist.

  • Dining Philosophers: As above.

III. DEADLOCKS

Deadlock Definition & Modeling

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

• Resource Allocation Graph (RAG):

  • Nodes: Processes (circles), Resource Types (squares). Resource instances as dots inside square.

  • Edges: Request Edge (process → resource), Assignment Edge (resource → process).

  • Deadlock Detection: Cycle in RAG iff each resource type has exactly one instance. For multiple instances, need more complex algorithm.

Necessary Conditions (must hold simultaneously)

1. Mutual Exclusion: At least one resource must be 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 waiting for resources held by next process.

Deadlock Handling Strategies

Deadlock Avoidance: Banker's Algorithm (High Frequency)

• Assumptions: Max claim of each process known in advance. Resources have multiple identical instances.

• Data Structures (n processes, m resource types):

  • Available[m]: Vector of available instances.

  • Max[n][m]: Max demand of each process.

  • Allocation[n][m]: Currently allocated instances to each process.

  • Need[n][m]: Remaining need. 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.

  3. If found, Work = Work + Allocation[i], Finish[i]=true, goto 2.

  4. If all Finish[i]==true → Safe State. Else Unsafe.

• Resource-Request Algorithm:

  1. Check Request[i] <= Need[i]. If not, error (exceed max claim).

  2. Check Request[i] <= Available. If not, process waits.

  3. Pretend to allocate: Available -= Request[i], Allocation[i] += Request[i], Need[i] -= Request[i].

  4. Run Safety Algorithm. If safe, grant request. If unsafe, block request & restore old state.

[!TIP] Exam Focus: You will be asked to compute Need matrix and determine safe state or if a request can be granted. Show all steps clearly.

IV. MEMORY MANAGEMENT

Background

• MMU (Memory Management Unit): Hardware that translates logical to physical addresses using page/segment tables.

• Address Binding:

  • Compile-time: Absolute code (fixed in memory). Rare.

  • Load-time: Relocatable code, bound at load time.

  • Execution-time (Dynamic): Binding delayed until runtime (via MMU). Allows process to move in memory.

• Logical vs. Physical Address Space:

  • Logical (Virtual) Address: Generated by CPU.

  • Physical Address: Seen by memory hardware.

  • Address Binding: Map from logical to physical.

• Dynamic Loading: Load routine only when called (first call). Saves memory. OS support not strictly required.

• Dynamic Linking: Linking postponed until load/execution time. Uses stubs in code. Shared libraries (.dll, .so) are a form of this.

Memory Allocation Strategies

• Contiguous Allocation:

  • Single Partition: OS in low memory, user process in high memory (or vice versa). Protection via base/limit registers.

  • Multiple Partition (Fixed/Static): Memory divided into fixed-sized partitions. Each process fits into one. Internal Fragmentation: Wasted space within partition.

  • Multiple Partition (Variable/Dynamic): Allocate exactly-sized block. Maintain list of free/busy holes. External Fragmentation: Total memory enough, but not contiguous. Solved by Compaction (expensive, requires dynamic relocation).

  • Placement Algorithms: First-fit, Best-fit, Worst-fit.

• Non-Contiguous Allocation:

  • Paging (High Frequency):

    • Concept: Divide physical memory into fixed-size frames (e.g., 4KB). Logical memory into same-size pages. No external fragmentation, only internal (last page).

    • Address Translation: Logical address = (page#, offset). Physical address = (frame#, offset). Look up frame# in page table.

    • Page Table: Array mapping page number → frame number. Stored in memory. Translation Lookaside Buffer (TLB) is a fast cache for page table entries.

    • Page Table Structures:

      • Hierarchical (Multi-level): Page table itself paged (e.g., 2-level, 3-level). Reduces memory overhead for sparse address spaces.

      • Hashed: Hash page number to bucket, chain of PTEs.

      • Inverted: One global entry per frame, with pointers to all pages mapping to it. Good for sparse address spaces, used in some OS kernels.

    • Protection: Valid/Invalid bit in PTE. Valid → page in process space. Invalid → not in process space (or not in memory).

    • Demand Paging:

      • Concept: Bring page into memory only when referenced. Page table entry has Valid/Invalid bit. Invalid page fault → OS brings page from disk (swap space).

      • Lazy Swapper: Swapper doesn't swap in entire process, only pages as needed.

      • Page Fault: Trap to OS. OS finds free frame (or evicts victim page), reads page from disk, updates PTE, restarts instruction.

      • Page Replacement: If no free frame, choose victim page to evict.

        • FIFO: Replace oldest page. Belady's Anomaly: More frames → more faults (possible).

        • Optimal (OPT): Replace page whose next use is farthest in future. Unrealizable (future knowledge), used for comparison.

        • LRU (Least Recently Used): Replace page not used for longest time. Approximated by hardware (reference bits) or software (stack). Near-optimal.

      • Example (LRU with reference string 1,2,3,4,1,2,5,1,2,3,4,5 and 3 frames):

        
        Ref 1: [1] faults=1
        
        Ref 2: [1,2] faults=2
        
        Ref 3: [1,2,3] faults=3
        
        Ref 4: [2,3,4] faults=4 (evict 1)
        
        Ref 1: [1,3,4] faults=5 (evict 2)
        
        ... etc.
        
        

      • Allocation Algorithms:

        • Fixed Allocation: Each process gets fixed number of frames (e.g., proportional to size, priority). Global vs. Local Replacement: Can process A take frame from process B? (Global: yes, Local: no).

        • Variable Allocation: Number of frames varies based on behavior (working set).

      • Thrashing: CPU spends more time paging than executing. Caused by under-allocation of frames. Working Set Model: Set of pages a process has referenced recently. OS must ensure sum of working set sizes ≤ physical memory.

  • Segmentation (High Frequency):

    • Concept: Programmer's view. Memory divided into logical segments (code, data, stack, heap). Each segment has a number and offset.

    • Segment Table: Entry contains segment base (physical start) and segment limit (length). Check 0 <= offset < limit.

    • Address Translation: (segment#, offset) → physical (base + offset).

    • Advantages over Paging:

      • User's View: Logical grouping (segments) vs. arbitrary paging. Easier for programmer.

      • Protection & Sharing: Share entire segment (e.g., code) by pointing multiple segment table entries to same physical segment. Protection bits per segment.

    • Disadvantages: External fragmentation (variable-sized segments). Complex allocation.

    • Paged Segmentation (Combined): Each segment is paged. Segment table points to page table for that segment. Combines user's view (segments) with efficient memory use (paging). Used in Intel x86 (though not cleanly).

Memory Management in Specific OS

• UNIX (BSD): Uses demand paging with LRU approximation (reference bits). Swap space on disk. Page replacement uses clock algorithm (second-chance). Process size limited by swap space.

• Windows (NT-based): Virtual address space per process (2GB user, 2GB kernel on 32-bit; 128TB on 64-bit). Uses working set model. Page replacement uses modified clock algorithm. Supports large pages.

Special Concepts

• Overlays: Manual technique. Programmer divides program into modules. Only keep needed modules in memory. Load/unload as needed. Used before virtual memory. Still useful in deeply embedded systems.

V. STORAGE MANAGEMENT & FILE SYSTEMS

File System Concepts

• File Attributes: Name, Identifier (inode #), Type, Location, Size, Protection (permissions), Time/Date (create, modify, access).

• File Operations: create, delete, open, close, read, write, seek, append, rename.

• File Types: Regular, Directory, Special/Device (block, character).

• File Structure: Byte sequence (UNIX), Record sequence (fixed/variable), Tree (directory).

Directory Structure (High Frequency)

• Hard Link: Direct pointer to inode. Same inode #. Cannot cross filesystems. Cannot link to directory (usually). Deleted when link count reaches 0.

• Symbolic (Soft) Link: Special file containing pathname to target. Can cross filesystems. Can point to directory. Becomes dangling if target deleted.

File System Implementation

• Disk Space Allocation Methods (High Frequency):

  | Method | Mechanism | Advantages | Disadvantages | | :--- | :--- | :--- | :--- | | Contiguous | File occupies contiguous block set. | Fast sequential/random access. Simple. | External fragmentation. File growth difficult. | | Linked | Each block has pointer to next. | No external fragmentation. Files can grow. | Slow random access (follow pointers). Space for pointers. Reliability (broken pointer). | | FAT (File Allocation Table) | Special array in memory. Entry[i] = next block of file i. | Fast traversal (table in memory). No external frag. | Table size limits disk size. | | Indexed | All pointers (index block) stored in one location. | Fast random access. No external frag. | Large files need multi-level or linked index. Space overhead for index. |

  • Indexed Variants:

    • Single-level: Index block holds all pointers. Limited file size (block size * pointers/block).

    • Multi-level (e.g., i-nodes): Hierarchical index blocks (direct, single indirect, double indirect, triple indirect). UNIX inode.

    • Linked Index: Index blocks linked together.

• Free Space Management:

  • Bit Vector (Bitmap): 1 bit per block. 0=free, 1=allocated. Fast to find first free block.

  • Linked List: Free blocks linked together. Can traverse to find contiguous set.

  • Grouping: Free blocks in groups, first block contains addresses of next groups.

  • Counting: Keep ranges of free blocks (extent-based).

File System in Specific OS

• UNIX (V7, BSD, Ext):

  • VFS (Virtual File System): Abstraction layer for multiple file system types.

  • Inode: Unique per file. Contains: mode, owner, group, size, timestamps, block pointers (12 direct, 1 single indirect, 1 double, 1 triple), link count.

  • Directory: Special file mapping filename → inode #.

  • Allocation: Indexed (i-nodes). Can have fragmentation but OS tries to allocate contiguous blocks for data blocks pointed by direct pointers.

• Windows (NTFS):

  • Master File Table (MFT): Each file is a record in MFT. Small files stored directly in MFT entry.

  • Attributes: $DATA (file content), $FILE_NAME, $STANDARD_INFORMATION (timestamps), etc.

  • Allocation: Indexed (B+ tree for large directories). Uses $Bitmap file for free space. Clusters (variable size, 512B-64KB).

• Comparison (UNIX vs. Windows):

  | Feature | UNIX (Ext4) | Windows (NTFS) | | :--- | :--- | :--- | | Metadata Structure | Inode (fixed size) | MFT record (variable, can be resident) |

  Small File Storage | Direct block pointers in inode | Resident in MFT (no separate data clusters) |

  Directory Structure | Linear list or HT (for large) | B+ Tree |

  Journaling | Yes (Ext3/4) | Yes (NTFS log) |

  Access Control | rwx for user/group/others | ACLs (more granular) |

  Performance | Generally faster for small files | Better for large files, fragmentation handling |

Virtual File Systems (VFS)

• Purpose: Provide common interface to diverse file systems (ext4, NTFS, NFS, FAT). Allows OS to support multiple FS types transparently.

• Architecture:

  • VFS Objects: vnode (virtual inode, file-specific), file (open file description), dentry (directory entry cache), inode (FS-specific).

  • Operations: Each object has a set of function pointers (inode_operations, file_operations). FS-specific implementation fills these.

  • Flow: System call → VFS layer → dispatch to specific FS's operations via vnode.

VI. I/O SYSTEMS

I/O Fundamentals

• Components: I/O Device → Controller (hardware, has registers) → Driver (kernel software) → OS.

• I/O Techniques (High Frequency):

  1. Programmed I/O (Polling): CPU repeatedly checks device status bit. Wastes CPU cycles.

  2. Interrupt-Driven I/O: CPU issues I/O command, continues other work. Device controller interrupts CPU when ready (or on error). CPU handles interrupt (saves context, runs ISR, restores). Better CPU utilization.

  3. DMA (Direct Memory Access): For large data transfers. CPU programs DMA controller (source, dest, count). DMA controller manages transfer on bus, interrupts CPU only on completion. Frees CPU completely during transfer.

Logical I/O Structure & Kernel I/O Subsystem (High Frequency)

• Logical I/O: User process issues system calls (read, write). Kernel uses file descriptors → open file table entry → inode/vnode.

• Kernel I/O Subsystem Functions:

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

  • Buffering: Store data temporarily (in kernel memory) to cope with speed mismatches or different block sizes.

  • Caching: Keep copies of data in faster memory (e.g., disk cache in RAM).

  • Spooling: Hold output for a device that cannot accept interleaved data (e.g., printer). Uses disk as buffer.

  • Device Reservation: Allocate exclusive access to a device (e.g., flock).

  • Error Handling: Retry transient errors, report permanent failures.

I/O Buffering (High Frequency)

• Purpose: Decouple producer/consumer speeds, allow block-oriented devices to work with variable-sized data.

• Types:

  • Single Buffer: One buffer in kernel. Process blocked until I/O completes into buffer, then copies to user space.

  • Double Buffer: Two buffers. While one fills, other can be processed/emptied. Overlap I/O and computation.

  • Circular Buffer: Multiple buffers in ring. Producer/consumer pointers. Used in streams (audio/video).

• Buffering Strategies:

  • I/O vs. Memory: Buffer in kernel memory (protected) vs. user memory (faster but unprotected).

  • Read-ahead (Prefetch): Read more than requested anticipating future needs.

  • Write-behind (Delayed Write): Buffer writes, write to disk later (periodically or when buffer full).

Synchronous vs. Asynchronous I/O

Disk Scheduling Algorithms (High Frequency)

• Parameters:

  • Seek Time: Move head to target track.

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

  • Transfer Time: Read/write data as sector passes.

  • Access Time: Seek + Rotational Latency.

• Algorithms (Assume requests: 86, 147, 91, 177, 94, 150, 102, 175, 130; head starts at 143, previous at 125):

  • FCFS / SSTF: Already in queue order / shortest distance from current head.

    • FCFS: 143→86→147→91→177→94→150→102→175→130

      • Movement: |143-86|+|86-147|+... = 664 tracks.

    • SSTF: 143→147→150→130→125(prev? no)→... (tie-breaking matters). Usually lower than FCFS, but can cause starvation.

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

    • Start at 143, go up: 147,150,175,177 → then down: 130,102,94,91,86.

    • Movement: (177-143) + (177-86) = 34 + 91 = 125.

  • C-SCAN (Circular SCAN): Head moves in one direction only. When reaches end, jumps to beginning (without servicing) and continues.

    • Start 143, go up to max (199): 147,150,175,177 → jump to 0 → go up: 86,91,94,102,130.

    • Movement: (199-143) + (130-0) = 56 + 130 = 186.

  • LOOK / C-LOOK: Like SCAN/C-SCAN but only go as far as last request in direction, not to disk end.

    • LOOK: 143→147→150→175→177→130→102→94→91→86. Movement: (177-143)+(177-86)=34+91=125 (same as SCAN here).

    • C-LOOK: 143→147→150→175→177→ jump to 86→91→94→102→130. Movement: (177-143)+(130-86)=34+44=78.

[!TIP] Exam Tip: For disk scheduling, draw the track diagram (0 to 199), mark head position, draw arrows in order of service, sum absolute differences.

Disk Management

• Disk Structure: Platters → Tracks (concentric circles) → Sectors (fixed-size blocks, e.g., 512B, 4KB). Cylinder = same track on all platters.

• Disk Allocation Methods: Same as file system allocation (Contiguous, Linked, Indexed) but applied to disk blocks for file storage.

• Tape Organization: Sequential access only. Forward/Backward space records. Rewind. Density (bits/inch). No random access.

VII. PROTECTION & SECURITY

Goals of Protection & Security

• Confidentiality: Prevent unauthorized disclosure.

• Integrity: Prevent unauthorized modification.

• Availability: Ensure service accessible when needed.

• Authenticity: Verify user/process identity.

Protection Mechanisms

• Access Control:

  • ACLs (Access Control Lists): Per-object list of (principal, permissions). Flexible, but large for files with many users.

  • Capabilities: Unforgeable token (e.g., integer, pointer) that grants access to an object. Held by process. Easier to revoke? (Harder than ACLs).

• Protection Domains: Set of resources a process can access.

  • User Mode vs. Kernel Mode: CPU rings. Kernel mode has full access. User mode restricted (system calls for privileged ops).

  • Process Privilege: UNIX root (UID 0) vs. normal user.

• Role in Paging/Segmentation: Protection bits in page table entry (read/write/execute) or segment table entry. MMU enforces on every memory access.

Security Mechanisms

• Authentication: Verify identity. Passwords (hashed, salted), biometrics, tokens, multi-factor.

• Authorization: Determine allowed actions after authentication (ACLs, capabilities, roles).

• Encryption: Confidentiality via cryptography (symmetric, asymmetric).

• Firewalls: Network-level access control (packet filtering, stateful inspection, application proxy).

• Intrusion Detection: Monitor for malicious activity (signature-based, anomaly-based).

• OS-Specific Security:

  • UNIX Permissions: rwx for user/group/others. Setuid/setgid bits. Capabilities (Linux).

  • Windows Security Model: Security Descriptors (DACL, SACL, owner, SID). Access tokens. Mandatory Integrity Control (MIC). User Account Control (UAC).

Final Note: This summary covers all high-frequency topics from past RGPV papers. For exam success:

1. Practice calculations: Scheduling (Gantt, Avg WT/TAT), Banker's algorithm, Page Replacement (FIFO, LRU, OPT), Disk Scheduling (head movement).

2. Draw diagrams: Process states, RAG, Gantt charts, disk scheduling tracks, directory trees, paging/segmentation translation.

3. Compare/contrast: ULT vs KLT, paging vs segmentation, contiguous vs non-contiguous allocation, synchronous vs async I/O, distributed vs multiprocessor, UNIX vs Windows FS.

4. Explain with examples: Semaphores (producer-consumer), monitors (dining philosophers), system calls (process/file management).

5. Remember definitions: Deadlock conditions, Belady's anomaly, thrashing, working set, VFS, etc.