Overview
This lesson is a condensed reference you can revisit before an exam or interview. Rather than re-explaining every concept in depth, it collects the essential definitions, formulas, and algorithm names from across the course in one place, organized by topic area: scheduling, deadlocks, memory management, and file/disk systems.
Cricket analogy: This lesson is like a cricket coaching manual's quick-reference appendix — not re-teaching every drill, but collecting field placements, scoring rules, and DRS protocols in one page to revise before a big match.
Scheduling Metrics and Algorithms
Scheduling algorithms are compared using a small set of standard metrics. Turnaround time is completion time minus arrival time — the total time a process spends in the system. Waiting time is turnaround time minus burst time — the time spent in the ready queue not executing. Response time is the time from arrival until the first time the process gets the CPU, important for interactive systems. Throughput is the number of processes completed per unit time.
Cricket analogy: Turnaround time is like the total time from a batsman walking in to being dismissed and walking off; waiting time is the time spent in the dugout not yet padded up; response time is how long until they face their first ball; throughput is how many wickets fall per session.
- FCFS (First-Come, First-Served): non-preemptive, simple, suffers the convoy effect when a long job leads.
- SJF (Shortest Job First): minimizes average waiting time provably; needs burst-time estimates; can starve long jobs.
- SRTF (Shortest Remaining Time First): preemptive version of SJF, re-evaluates on new arrivals.
- Priority Scheduling: runs highest-priority job first; can starve low-priority jobs and suffer priority inversion.
- Round Robin: preemptive, fixed time quantum, fair and responsive; quantum size trades overhead against responsiveness.
- Multilevel Queue: partitions processes into queues (e.g., system, interactive, batch) each with its own scheduling policy.
- Multilevel Feedback Queue: like multilevel queue but allows processes to move between queues based on observed behavior.
Deadlock Essentials
Deadlock is a state where a set of processes are each waiting for a resource held by another process in the set, and none can proceed. The four necessary conditions, which must all hold simultaneously, are mutual exclusion, hold and wait, no preemption, and circular wait.
Cricket analogy: A recap: deadlock needs exclusive resource hold (mutual exclusion), holding one resource while awaiting another (hold and wait), refusal to give up resources voluntarily (no preemption), and a circular chain of waiting players — like a fielding huddle where nobody moves position until someone else does first.
- Prevention: structurally eliminate one of the four conditions (e.g., request all resources at once to remove hold-and-wait).
- Avoidance: use runtime information (e.g., the Banker's Algorithm) to only grant requests that keep the system in a safe state.
- Detection and recovery: allow deadlock to occur, detect it via resource-allocation graph cycle checks, then recover by process termination or resource preemption.
- Ignoring the problem (the 'ostrich algorithm'): common in general-purpose OSes because deadlocks are rare enough that prevention overhead isn't worth it.
Memory Management
Memory management schemes trade off simplicity, fragmentation type, and how naturally they map to program structure.
Cricket analogy: Memory management schemes are like different ways to organize a team's kit room — simple shelving is easy but wastes space, labeled bins by player mirror how the coach thinks about the squad but leave gaps, and each approach trades simplicity for how naturally it maps to team structure.
- Paging: fixed-size pages/frames, no external fragmentation, has internal fragmentation, uses a page table for address translation.
- Segmentation: variable-size logical segments, natural protection/sharing, has external fragmentation.
- Virtual memory: gives each process a private address space, enables demand paging, backed by disk when RAM is full.
- Demand paging: pages are loaded into memory only when referenced (on a page fault), not all at process start.
- Thrashing: excessive paging activity when combined working sets exceed physical memory, causing low CPU utilization.
Page Replacement and Disk Scheduling Algorithms
When physical memory is full, a page-replacement algorithm decides which page to evict; when multiple disk I/O requests are pending, a disk-scheduling algorithm decides their service order.
Cricket analogy: When the practice nets are all booked, a coach must decide which team to bump (page replacement); when several players want physiotherapy at once, the physio must decide the service order (disk scheduling) — two different queueing decisions for two different bottlenecks.
- FIFO page replacement: evicts the oldest-loaded page; simple but can suffer Belady's anomaly.
- Optimal (OPT/MIN) page replacement: evicts the page not needed for the longest future time; theoretical best-case benchmark, not implementable in practice.
- LRU (Least Recently Used) page replacement: evicts the page unused for the longest time in the past; good practical approximation of optimal.
- Clock (Second-Chance) page replacement: approximates LRU cheaply using a reference bit and circular scan.
- FCFS disk scheduling: services requests in arrival order; simple but can cause long seek times.
- SSTF (Shortest Seek Time First) disk scheduling: services the closest request next; can starve far-away requests.
- SCAN / C-SCAN disk scheduling: the disk arm sweeps in one direction servicing requests, then reverses (SCAN) or jumps back to the start (C-SCAN) for more uniform wait times.
Quick Reference
- Turnaround time = completion time − arrival time.
- Waiting time = turnaround time − burst time.
- Response time = time of first CPU burst − arrival time.
- Deadlock needs: mutual exclusion + hold-and-wait + no preemption + circular wait.
- Internal fragmentation = wasted space inside an allocated unit; external = wasted space between allocated units.
- LRU approximates optimal page replacement using recency of past access.
- SSTF minimizes seek time locally but can starve distant requests; SCAN bounds worst-case wait more fairly.
- Context switch overhead = time to save/restore process state, pure overhead with no useful computation.
- Semaphore = counting synchronization primitive; mutex = binary lock with ownership.
- Page fault = trap on access to a not-present page, resolved by the OS fault handler.
Key Takeaways
- Know the three core scheduling metrics (turnaround, waiting, response time) and how to compute them from a Gantt chart.
- Deadlock's four conditions and the three handling strategies (prevention, avoidance, detection/recovery) are exam and interview staples.
- Paging vs segmentation fragmentation types are opposite and frequently tested together.
- LRU and Clock are the practical page-replacement algorithms; Optimal is a theoretical benchmark only.
- SCAN-family disk algorithms exist specifically to bound the worst-case wait time that SSTF can produce.
Practice what you learned
1. How is waiting time calculated for a process?
2. Which page-replacement algorithm serves as the theoretical best-case benchmark but cannot be implemented in practice?
3. Which disk-scheduling algorithm can cause starvation of far-away requests by always favoring the closest one?
4. Which memory management scheme causes internal fragmentation rather than external fragmentation?
5. Which deadlock-handling strategy uses runtime checks like the Banker's Algorithm to only grant requests that keep the system in a safe state?
Was this page helpful?
You May Also Like
Scheduling Algorithms Overview
How the CPU scheduler picks the next ready process, the metrics used to judge it, and the family of algorithms available.
Page Replacement Algorithms
How an OS decides which page to evict on a page fault when all frames are full, compared via FIFO, LRU, and Optimal.
Disk Scheduling Algorithms
How the OS orders pending disk I/O requests to minimize head movement, comparing FCFS, SSTF, and SCAN.
Introduction to Deadlocks
Get a high-level preview of what deadlock is and the four necessary conditions that must all hold for it to occur.