Cheatsheet Operating System - Operating System - Computer Science Engineering

1. Process Management

1.1 Process States and Transitions

1.2 Process Control Block (PCB)

• Process ID (PID)
• Process State
• Program Counter (PC)
• CPU Registers
• Memory Management Information
• I/O Status Information
• Accounting Information
• Priority

1.3 Context Switch

• Overhead time when switching from one process to another
• Save state of old process to PCB
• Load state of new process from PCB
• Introduces overhead since no user-level process executes during the switch, though OS performs scheduling and state management.

2. CPU Scheduling

2.1 Scheduling Criteria

2.2 Scheduling Algorithms

2.2.1 First Come First Serve (FCFS)

• Non-preemptive
• Processes executed in order of arrival
• Simple implementation using FIFO queue
• Convoy effect: short processes wait for long processes
• Average WT can be high

2.2.2 Shortest Job First (SJF)

• Non-preemptive: executes shortest burst time first
• Optimal for minimum average waiting time
• Starvation: long processes may never execute
• Requires knowledge of burst time

2.2.3 Shortest Remaining Time First (SRTF)

• Preemptive version of SJF
• Preempts if new process has shorter remaining time
• Optimal for minimum average waiting time among preemptive algorithms
• More context switches than SJF

2.2.4 Round Robin (RR)

• Preemptive
• Each process gets time quantum (q)
• If q large: behaves like FCFS
• If q small: high context switch overhead
• Fair allocation, no starvation
• Higher average TAT than SJF but better response time

2.2.5 Priority Scheduling

• Each process assigned priority number
• CPU allocated to highest priority process
• Can be preemptive or non-preemptive
• Starvation: low priority processes may never execute
• Solution: Aging - gradually increase priority of waiting processes

2.2.6 Multilevel Queue Scheduling

• Multiple queues with different priorities
• Processes permanently assigned to one queue
• Each queue has its own scheduling algorithm
• Scheduling among queues: fixed priority or time slice

2.2.7 Multilevel Feedback Queue

• Processes can move between queues
• Separates processes based on CPU burst characteristics
• I/O bound and interactive processes kept in higher priority queues
• CPU bound processes move to lower priority queues

3. Process Synchronization

3.1 Critical Section Problem

3.2 Peterson's Solution

• Software solution for 2 processes
• Uses two variables: flag[2] and turn
• flag[i] = true indicates process i ready to enter CS
• turn indicates whose turn it is
• Satisfies all three requirements

3.3 Synchronization Hardware

3.3.1 Test-and-Set Lock (TSL)

• Atomic instruction: tests and modifies word atomically
• Returns original value and sets to true
• boolean TestAndSet(boolean *target) { boolean rv = *target; *target = true; return rv; }

3.3.2 Compare-and-Swap (CAS)

• Atomic instruction comparing and swapping values
• int CAS(int *value, int expected, int new) { int temp = *value; if (*value == expected) *value = new; return temp; }

3.4 Semaphores

• Binary Semaphore: value 0 or 1 (mutex lock)
• Counting Semaphore: unrestricted integer value
• Used for mutual exclusion and synchronization
• Can cause busy waiting (spinlock) or use blocking

3.5 Classical Synchronization Problems

3.5.1 Producer-Consumer Problem

• Semaphores: mutex = 1, full = 0, empty = n (buffer size)
• Producer: wait(empty) → wait(mutex) → produce → signal(mutex) → signal(full)
• Consumer: wait(full) → wait(mutex) → consume → signal(mutex) → signal(empty)

3.5.2 Readers-Writers Problem

• Multiple readers can read simultaneously
• Writers need exclusive access
• Semaphores: mutex = 1 (for readcount), wrt = 1 (for writing)
• First readers-writers: readers preference, writers may starve
• Second readers-writers: writers preference, readers may starve
• Third readers-writers (fair): ensures no starvation of readers or writers.

3.5.3 Dining Philosophers Problem

• 5 philosophers, 5 chopsticks (forks)
• Each needs 2 chopsticks to eat
• Deadlock possible if all pick left chopstick simultaneously
• Solutions: limit philosophers to 4, asymmetric solution, pick both atomically

3.6 Monitors

• High-level synchronization construct
• Only one process active inside monitor at a time
• Condition variables: wait() and signal()
• In Mesa-style monitors (used in practice), signal() wakes a waiting process but the signaling process continues execution.

4. Deadlocks

4.1 Necessary Conditions for Deadlock

• All four conditions must hold simultaneously for deadlock

4.2 Resource Allocation Graph (RAG)

• Vertices: Processes (circles) and Resources (rectangles)
• Request edge: Pi → Rj (directed)
• Assignment edge: Rj → Pi (directed)
• If no cycle: no deadlock
• If cycle exists with single instance per resource type: deadlock
• If cycle exists with multiple instances: deadlock possible but not certain

4.3 Deadlock Handling Methods

4.3.1 Deadlock Prevention

• Negate one of the four necessary conditions
• Mutual Exclusion: make resources sharable (not always possible)
• Hold and Wait: require process to request all resources at once
• No Preemption: allow resource preemption
• Circular Wait: impose total ordering on resource types

4.3.2 Deadlock Avoidance

• Requires advance information about resource requests
• Safe state: system can allocate resources to each process in some order and avoid deadlock
• Unsafe state: no guarantee of deadlock avoidance

4.3.3 Banker's Algorithm

• Deadlock avoidance algorithm for multiple resource instances
• Data structures: Available[m], Max[n][m], Allocation[n][m], Need[n][m]
• Need[i][j] = Max[i][j] - Allocation[i][j]
• Safety algorithm checks if system is in safe state
• Resource request algorithm: if Request[i] ≤ Need[i] and Request[i] ≤ Available, try allocation and check safety
• Time complexity: O(m × n²) where m = resources, n = processes

4.3.4 Deadlock Detection

• Allow deadlock to occur, then detect and recover
• Single instance: use wait-for graph (remove resource nodes from RAG)
• Multiple instances: detection algorithm similar to Banker's algorithm
• Time complexity: O(m × n²)

4.3.5 Deadlock Recovery

• Process termination: abort all or one at a time
• Resource preemption: select victim, rollback, and prevent starvation

4.3.6 Deadlock Ignorance

• Assume deadlock never occurs (Ostrich algorithm)
• Commonly used for certain resources in general-purpose operating systems (Ostrich approach), relying on higher-level prevention.

5. Memory Management

5.1 Logical vs Physical Address

5.2 Address Binding

• Compile time: absolute code, fixed physical address
• Load time: relocatable code, binding at load time
• Execution time: binding delayed until run time, requires hardware support

5.3 Contiguous Memory Allocation

5.3.1 Fixed Partitioning

• Memory divided into fixed-size partitions
• Internal fragmentation: wasted space within partition
• Limit on degree of multiprogramming

5.3.2 Dynamic Partitioning

• Partitions created dynamically based on process size
• External fragmentation: wasted space between partitions
• Solution: compaction (costly)

5.3.3 Allocation Strategies

5.4 Paging

• Logical memory divided into fixed-size blocks: pages
• Physical memory divided into fixed-size blocks: frames
• Page size = Frame size (power of 2; commonly 4KB; some systems support large/huge pages).
• No external fragmentation
• Internal fragmentation in last page only
• Page table stores mapping from page number to frame number

5.4.1 Address Translation in Paging

• Logical address = (page number, page offset)
• Physical address = (frame number, page offset)
• If logical address space = 2^m and page size = 2ⁿ
• Page number = m - n bits, Page offset = n bits
• Number of pages = 2^(m-n)

5.4.2 Page Table Implementation

• Page Table Base Register (PTBR) points to page table
• Page Table Length Register (PTLR) indicates size
• Every data access requires two memory accesses: one for page table, one for data
• Solution: Translation Look-aside Buffer (TLB)

5.4.3 Translation Look-aside Buffer (TLB)

• Fast associative cache for page table entries
• Contains subset of page table entries
• TLB hit: frame number obtained directly
• TLB miss: access page table in memory
• Effective Access Time (EAT) = α × (c + m) + (1 - α) × (c + 2m)
• α = TLB hit ratio, c = TLB access time, m = memory access time

5.4.4 Multi-level Paging

• Page table itself is paged
• Two-level paging: outer page table and inner page tables
• Reduces memory for page table storage
• Logical address: (p1, p2, d) where p1 = outer page, p2 = inner page, d = offset

5.4.5 Inverted Page Table

• One entry per physical frame instead of per page
• Each entry: (process-id, page-number)
• Reduces memory for page table
• Increases search time: use hash table

5.5 Segmentation

• Logical address space: collection of segments
• Segment = logical unit (code, data, stack, heap)
• Segment table: (base, limit) for each segment
• Logical address = (segment number, offset)
• Physical address = base[segment] + offset (if offset < />
• External fragmentation present
• No internal fragmentation

5.6 Segmentation with Paging

• Segment table entry contains page table base address
• Each segment has its own page table
• Combines advantages of both schemes

6. Virtual Memory

6.1 Demand Paging

• Page loaded into memory only when needed
• Valid-invalid bit in page table: v = in memory, i = not in memory
• Page fault: reference to page not in memory
• Lazy swapper (pager): swaps page only when needed

6.2 Page Fault Handling

• Trap to OS
• Check if reference valid or invalid
• If invalid: terminate process
• If valid but not in memory: page in from disk
• Find free frame
• Swap page into frame
• Update page table
• Restart instruction

6.3 Effective Access Time with Demand Paging

• EAT = (1 - p) × m + p × page_fault_time
• p = page fault rate (0 ≤ p ≤ 1)
• m = memory access time
• page_fault_time = page fault overhead + swap out + swap in + restart overhead

6.4 Page Replacement Algorithms

6.4.1 First In First Out (FIFO)

• Replace oldest page in memory
• Simple implementation using queue
• Belady's Anomaly: more frames may lead to more page faults

6.4.2 Optimal Page Replacement (OPT)

• Replace page not used for longest time in future
• Lowest page fault rate
• Not implementable: requires future knowledge
• Used as benchmark

6.4.3 Least Recently Used (LRU)

• Replace page not used for longest time in past
• Approximates OPT
• No Belady's Anomaly (stack algorithm)
• Implementation: counters or stack (expensive)

6.4.4 LRU Approximation Algorithms

• Reference bit: set when page referenced, periodically cleared
• Second Chance (Clock): FIFO with reference bit, gives second chance if bit = 1
• Enhanced Second Chance: uses (reference bit, modify bit) pairs
• Order of preference: (0,0) → (0,1) → (1,0) → (1,1)

6.4.5 Counting Algorithms

• Least Frequently Used (LFU): replace page with smallest count
• Most Frequently Used (MFU): replace page with largest count

6.5 Allocation of Frames

6.5.1 Frame Allocation Algorithms

6.5.2 Global vs Local Replacement

• Global: process can select replacement frame from all frames
• Local: process selects from only its allocated frames
• Global generally gives better throughput

6.6 Thrashing

• Process spending more time paging than executing
• Occurs when process lacks sufficient frames
• CPU utilization decreases despite increased multiprogramming
• Solution: working set model or page fault frequency

6.7 Working Set Model

• Working set (WS): set of pages referenced in most recent Δ page references
• Δ = working set window
• WSS = working set size
• If Σ WSS > total frames: thrashing
• OS monitors working set and allocates sufficient frames

6.8 Page Fault Frequency (PFF)

• Establish acceptable page fault rate
• If actual rate too high: allocate more frames
• If actual rate too low: remove frames

7. File Systems

7.1 File Concepts

• File: named collection of related information stored on secondary storage
• File attributes: name, type, location, size, protection, time stamps
• File operations: create, read, write, reposition (seek), delete, truncate, open, close
• Open file table: per-process and system-wide
• File descriptor/handle: index into open file table

7.2 File Access Methods

7.3 Directory Structure

• Single-level: all files in one directory
• Two-level: separate directory for each user
• Tree-structured: hierarchical directory structure
• Acyclic-graph: allows sharing via links
• General graph: allows cycles (problem with traversal and deletion)

7.4 File Allocation Methods

7.4.1 Contiguous Allocation

• Each file occupies contiguous blocks on disk
• Directory entry: (start block, length)
• Advantages: simple, supports sequential and direct access, minimal head movement
• Disadvantages: external fragmentation, file size difficult to estimate

7.4.2 Linked Allocation

• Each file is linked list of disk blocks
• Directory entry: pointer to first and last blocks
• Each block contains pointer to next block
• Advantages: no external fragmentation, file can grow dynamically
• Disadvantages: sequential access only, overhead of pointers, reliability issues
• FAT (File Allocation Table): variation where pointers stored in separate table

7.4.3 Indexed Allocation

• Index block contains pointers to all data blocks
• Directory entry: pointer to index block
• Advantages: supports direct access, no external fragmentation
• Disadvantages: overhead of index block, wasted space for small files
• Multi-level index: index block points to other index blocks
• Combined scheme (UNIX inode): direct, single indirect, double indirect, triple indirect blocks

7.5 Free Space Management

7.6 Disk Structure

• Platter, Surface, Track, Sector, Cylinder
• Disk address: (cylinder, surface, sector)
• Disk access time = seek time + rotational latency + transfer time
• Seek time: time to move head to desired cylinder
• Rotational latency: time for desired sector to rotate under head
• Transfer time: time to transfer data

7.7 Disk Scheduling Algorithms

7.7.1 First Come First Serve (FCFS)

• Service requests in order of arrival
• Fair but may not provide fastest service

7.7.2 Shortest Seek Time First (SSTF)

• Service request closest to current head position
• Reduces total seek time
• Starvation possible for requests far from head

7.7.3 SCAN (Elevator Algorithm)

• Head moves in one direction servicing requests until end
• Then reverses direction
• No starvation
• More uniform wait time than SSTF

7.7.4 C-SCAN (Circular SCAN)

• Head moves in one direction servicing requests
• At end, returns to beginning without servicing
• More uniform wait time than SCAN

7.7.5 LOOK and C-LOOK

• Like SCAN/C-SCAN but head reverses when no more requests in current direction
• Does not go to end of disk unnecessarily

8. I/O Systems

8.1 I/O Hardware

• Port: connection point between device and computer
• Bus: set of wires and protocol for communication
• Controller/Host Adapter: electronics that operate port, bus, or device
• Device driver: software interface to hardware controller

8.2 I/O Methods

8.3 DMA Operation

• CPU provides: operation, memory address, data count
• DMA controller performs transfer
• DMA controller interrupts CPU when complete
• CPU free to perform other work during transfer
• Cycle stealing: DMA controller takes bus cycles from CPU

8.4 Buffering

• Single buffer: while one buffer being emptied, device fills another
• Double buffer (Buffer Swapping): two buffers alternate roles
• Circular buffer: multiple buffers in circular arrangement
• Buffer cache: pool of buffers in memory

8.5 Spooling

• Simultaneous Peripheral Operations On-Line
• Device can handle only one request at a time
• OS intercepts all output to device and stores in disk buffer (spool)
• Used for printers and batch systems

9. Protection and Security

9.1 Protection Goals

• Control access to system resources
• Ensure processes access only authorized resources
• Principle of least privilege: give minimum necessary rights

9.2 Access Matrix

• Rows: domains (users/processes)
• Columns: objects (files, devices, memory)
• Entry: access rights for domain on object
• Implementation: Access Control List (ACL) or Capability List

9.3 Security Threats

9.4 Authentication Methods

• Password: secret string known only to user
• One-time password: each password used only once
• Biometrics: fingerprint, retina scan, face recognition
• Two-factor authentication: combination of methods

9.5 Cryptography

• Symmetric encryption: same key for encryption and decryption (DES, AES)
• Asymmetric encryption: public key and private key (RSA)
• Hash functions: one-way function producing fixed-size output (MD5, SHA)
• Digital signatures: verify authenticity and integrity

10. Important Formulas