ENGIMY.IO - CHEATSHEET
OS × QUICK REFERENCE
OS
CORE SUBJECT REFERENCE

OPERATING
SYSTEMS CHEATSHEET.

A comprehensive reference for operating systems – processes, threads, scheduling, memory management, file systems, deadlock, and synchronisation. All in one place.

REFERENCE v1.0

Operating Systems Quick Reference

Everything you need day‑to‑day – concepts, algorithms, and system design.

Process Management

Process States
  • New – being created
  • Ready – waiting for CPU
  • Running – executing on CPU
  • Blocked / Waiting – waiting for I/O or event
  • Terminated – finished execution
Process Control Block (PCB)
  • Process ID (PID)
  • Process state
  • Program counter (PC)
  • Registers
  • Memory limits
  • List of open files
  • Scheduling information

Process vs Thread

Process Thread
Has own memory space Shares memory with other threads
Heavyweight (context switch is expensive) Lightweight (context switch is cheap)
Independent execution Lightweight execution within a process
Processes do not share memory (by default) Threads share heap and global variables
IPC via pipes, sockets, shared memory IPC via shared memory (faster)

CPU Scheduling

Common Scheduling Algorithms

Non‑Preemptive
  • FCFS (First Come First Serve) – simple, but convoy effect
  • SJF (Shortest Job First) – optimal average waiting time
  • Priority – fixed priority, may cause starvation
Preemptive
  • Round Robin – fair, time‑quantum based
  • SRTF (Shortest Remaining Time First) – preemptive SJF
  • Multilevel Queue – multiple priority queues
  • Multilevel Feedback Queue – adapts to process behaviour

Scheduling Comparison

Algorithm Preemptive Avg Waiting Time Starvation Use Case
FCFS No High No Batch systems
SJF No Optimal Yes (long jobs) Batch systems
SRTF Yes Optimal Yes Real‑time
Round Robin Yes Moderate No Time‑sharing
Priority Both Varies Yes (low priority) Priority based
MLFQ Yes Low No (with aging) General purpose

Round Robin – Time Quantum

  • Too large – becomes FCFS
  • Too small – high context switch overhead
  • Typical – 10‑100 ms (modern systems: 1‑4 ms)

Memory Management

Address Binding
  • Compile time – absolute addresses
  • Load time – relative addresses
  • Execution time – dynamic relocation
Logical vs Physical
  • Logical address – generated by CPU
  • Physical address – actual memory location
  • MMU – maps logical to physical

Memory Allocation Techniques

Contiguous
  • Fixed Partition – rigid, internal fragmentation
  • Variable Partition – flexible, external fragmentation
  • Buddy System – power of 2 allocation
Non‑Contiguous
  • Paging – fixed size pages
  • Segmentation – variable size segments
  • Virtual Memory – demand paging, page replacement

Paging

  • Page – fixed‑size block of logical memory
  • Frame – fixed‑size block of physical memory
  • Page Table – maps page → frame
  • TLB – Translation Lookaside Buffer (cache for page table)
+----------------+     +----------------+
| Logical Address  |     | Physical Address|
|  [Page | Offset] | --- | [Frame | Offset]|
+----------------+     +----------------+
        |                       |
        v                       v
Page Table (MMU)        Physical Memory

Page Replacement Algorithms

Algorithm Description Optimal? Implementation
Optimal (MIN) Replace page used farthest in future Yes (theoretical) Not possible in practice
FIFO Replace oldest page No Simple queue
LRU Replace least recently used Close Stack / counters
Clock (Second Chance) Circular FIFO with reference bit No Circular list
MFU Replace most frequently used No Counters

Thrashing

  • Occurs when system spends more time paging than executing
  • Caused by insufficient physical memory
  • Working set model – keep process' working set in memory
  • Solution: increase memory, reduce degree of multiprogramming

Deadlock

Four Necessary Conditions

  • Mutual Exclusion – resources cannot be shared
  • Hold and Wait – process holds resources while waiting
  • No Preemption – resources cannot be taken away
  • Circular Wait – cycle of dependencies

Deadlock Handling

Prevention
  • Break one of the four conditions
  • Resource allocation in order
  • Request all resources upfront
Avoidance
  • Banker's Algorithm
  • Only grant resources if system stays in safe state
  • Need maximum resource claim
Detection
  • Resource Allocation Graph
  • Wait‑for Graph
  • Periodic detection
Recovery
  • Abort one or more processes
  • Preempt resources (rollback)
  • Process checkpointing

Banker's Algorithm

  • Process declares maximum resources needed
  • System checks if allocation leads to safe state
  • Safe state – all processes can finish
  • Unsafe state – possible deadlock

Synchronisation

Critical Section Problem

  • Mutual Exclusion – only one process in critical section
  • Progress – if no process in CS, others can enter
  • Bounded Waiting – finite waiting time

Classic Synchronisation Problems

Producer‑Consumer
  • Producer adds to buffer
  • Consumer removes from buffer
  • Need synchronisation for buffer access
  • Semaphores: empty, full, mutex
Readers‑Writers
  • Multiple readers can read together
  • Only one writer at a time
  • Writers exclusive
  • Priority: readers (starvation) or writers
Dining Philosophers
  • 5 philosophers, 5 chopsticks
  • Each needs two chopsticks to eat
  • Risk of deadlock
  • Solution: resource ordering
Sleeping Barber
  • Barber sleeps when no customers
  • Customer wakes barber
  • Waiting room with chairs
  • If full, customer leaves

Synchronisation Primitives

Mutex
  • Binary semaphore (0/1)
  • Mutual exclusion
  • Ownership tracked
  • Lock/unlock
Semaphore
  • Counting semaphore (≥0)
  • General synchronisation
  • No ownership
  • wait() / signal()
Monitor
  • High‑level synchronisation
  • Only one thread at a time
  • Condition variables
  • Encapsulated in class
Condition Variable
  • Used with mutex
  • wait() – release lock and wait
  • signal() – wake one waiter
  • broadcast() – wake all waiters

File Systems

File Allocation Methods
  • Contiguous – fast, external fragmentation
  • Linked – no fragmentation, sequential access only
  • Indexed – fast random access, index overhead
Free Space Management
  • Bit Vector – bit per block, simple
  • Linked List – each free block points to next
  • Grouping – group of free blocks
  • Counting – contiguous free blocks

Directory Structures

  • Single‑level – all files in one directory
  • Two‑level – user directories
  • Tree – hierarchical directories
  • Acyclic Graph – shared subdirectories/aliases
  • General Graph – cycles (hard links)

Inter‑Process Communication (IPC)

Message Passing
  • Pipes – unidirectional (named/unnamed)
  • Message Queues – structured messages
  • Sockets – network communication
  • RPC – remote procedure calls
Shared Memory
  • Shared memory segment – fastest IPC
  • Memory‑mapped files – file → memory
  • Threads – share process memory
  • Semaphores/Mutex – for synchronisation

Key OS Concepts Summary

Concept Key Points
Context Switching Saving and restoring process state (PCB) – overhead
Interrupts Hardware/software signals that interrupt CPU execution
System Calls Kernel interface for user processes (open, read, write, fork)
DMA Direct Memory Access – I/O without CPU involvement
Protection Rings Ring 0 (kernel), Ring 3 (user) – security and privilege
📌 Quick Reference
Process states: New → Ready → Running → Blocked → Terminated
Scheduling: FCFS, SJF, SRTF, RR, Priority, MLFQ
Memory: Paging, Segmentation, Virtual Memory, Page Replacement (FIFO, LRU, Clock)
Deadlock conditions: Mutual Exclusion, Hold & Wait, No Preemption, Circular Wait
Synchronisation: Mutex, Semaphore, Monitor, Condition Variable
← Back to All Cheatsheets