Operating Systems Essentials

Cheatsheet Content

1. Introduction to Operating Systems Definition: Software managing computer hardware & software resources. Goals: Efficiency, fairness, responsiveness, reliability, security. Components: Kernel, shell/UI, system utilities, applications. 2. Process Management 2.1. Process Concept Process: A program in execution. Process States: New, Running, Waiting, Ready, Terminated. PCB (Process Control Block): Stores process state, program counter, CPU registers, memory limits, open files, etc. 2.2. Process Scheduling Scheduler: Selects which process to execute next. Dispatch Latency: Time to stop one process and start another. Scheduling Criteria: CPU utilization, throughput, turnaround time, waiting time, response time. Scheduling Algorithms: FCFS (First-Come, First-Served): Non-preemptive. SJF (Shortest-Job-First): Optimal for minimum average waiting time. Can be preemptive (SRTF) or non-preemptive. Priority Scheduling: Preemptive or non-preemptive. Can suffer from starvation. Round Robin (RR): Preemptive, time-sliced. Good for interactive systems. Time quantum $q$. Multilevel Queue: Processes permanently assigned to a queue. Multilevel Feedback Queue: Processes can move between queues. 2.3. Inter-Process Communication (IPC) Shared Memory: Fastest, but requires synchronization. Message Passing: Slower, but simpler for small data. Pipes: Unidirectional communication between related processes. Sockets: Network communication between processes. 3. Thread Management Thread: A lightweight process, unit of CPU utilization. Benefits: Responsiveness, resource sharing, economy, scalability. User-level Threads: Managed by user-level library. Faster context switch, but blocking call blocks all threads. Kernel-level Threads: Managed by OS kernel. Slower, but one blocking thread doesn't block others. Many-to-One, One-to-One, Many-to-Many models. 4. CPU Synchronization 4.1. Critical Section Problem Definition: Section of code where shared resources are accessed. Requirements: Mutual exclusion, progress, bounded waiting. 4.2. Synchronization Tools Mutex Locks: `acquire()`, `release()`. Only one process can hold the lock. Semaphores: Integer variable $S$. `wait(S)` (decrement), `signal(S)` (increment). Can be counting or binary. Monitors: High-level synchronization construct. Encapsulates shared data and procedures. Deadlock: Two or more processes waiting indefinitely for an event that can only be caused by one of the waiting processes. Conditions for Deadlock: Mutual exclusion, Hold and wait, No preemption, Circular wait. Handling Deadlock: Prevention, Avoidance (Banker's Algorithm), Detection and Recovery. 5. Memory Management 5.1. Basic Concepts Logical Address: Generated by CPU. Physical Address: Seen by memory unit. MMU (Memory Management Unit): Hardware that maps logical to physical addresses. Swapping: Moving processes between main memory and disk. 5.2. Memory Allocation Contiguous Allocation: Fixed Partitioning: Internal fragmentation. Variable Partitioning: External fragmentation. Dynamic Storage-Allocation Problem: First fit, Best fit, Worst fit. Non-Contiguous Allocation: Paging: Divides logical memory into fixed-size blocks (pages) and physical memory into same-size blocks (frames). No external fragmentation. Page Table: Maps page numbers to frame numbers. TLB (Translation Look-aside Buffer): Cache for page table entries. Segmentation: Divides logical memory into variable-size logical units (segments). 5.3. Virtual Memory Concept: Allows execution of processes not entirely in memory. Demand Paging: Pages loaded only when needed. Page Fault: Attempt to access a page not in memory. Page Replacement Algorithms: FIFO (First-In, First-Out): Simple, but can suffer from Belady's anomaly. Optimal: Replaces page not used for longest time. Unimplementable. LRU (Least-Recently-Used): Replaces page not used for longest time. Practical approximation of optimal. Counting-Based: LFU (Least-Frequently-Used), MFU (Most-Frequently-Used). Thrashing: High paging activity, low CPU utilization. 6. File System File: Named collection of related information. File Attributes: Name, type, location, size, protection, time/date. File Operations: Create, write, read, reposition, delete, truncate. Directory Structure: Single-level, Two-level, Tree-structured, Acyclic-graph, General-graph. Allocation Methods: Contiguous, Linked, Indexed. Free-Space Management: Bit vector, Linked list, Grouping, Counting. 7. I/O Systems I/O Hardware: Ports, buses, controllers. Polling: CPU repeatedly checks device status. Interrupts: Device notifies CPU when ready. DMA (Direct Memory Access): Controller transfers data directly to/from memory without CPU intervention. Disk Scheduling: FCFS: Simple. SSTF (Shortest-Seek-Time-First): Prioritizes requests closest to current head position. SCAN (Elevator Algorithm): Head moves in one direction, servicing requests, then reverses. C-SCAN (Circular SCAN): Head moves in one direction, then immediately returns to the other end without servicing requests on the return trip. LOOK/C-LOOK: Similar to SCAN/C-SCAN but only moves as far as the last request in each direction. 8. Security and Protection Protection: Mechanisms controlling access to resources. Security: Defending against internal and external attacks. Access Matrix: Rows are domains, columns are objects, entries are access rights. Authentication: Verifying user identity. Authorization: Granting access based on identity. Threats: Viruses, worms, denial-of-service, privilege escalation.