Operating Systems
Processes, memory, scheduling, deadlocks
Operating Systems (OS) are system software that manages computer hardware and software resources, providing common services for computer programs. Core topics include process management, memory management, file systems, I/O management, and CPU scheduling. Understanding these concepts is essential for system programming, performance optimisation, and technical interviews.
Key formulas and rules
Key concepts
Process vs Thread
A process is an independent program in execution with its own address space, resources, and PCB (Process Control Block). A thread is a lightweight unit of execution within a process, sharing the same address space and resources but having its own stack, registers, and program counter. Processes are isolated; threads within the same process communicate easily but can cause race conditions. Context switching between threads is faster than between processes.
CPU Scheduling Algorithms
First-Come-First-Served (FCFS): Non-preemptive, simple, may cause convoy effect. Shortest Job First (SJF): Optimal for minimum waiting time, requires prediction of burst times. Priority Scheduling: Can be preemptive or non-preemptive, may suffer from starvation. Round Robin (RR): Time quantum-based, fair, good for time-sharing systems. Multilevel Queue: Processes permanently assigned to queues. Multilevel Feedback Queue: Allows processes to move between queues based on behaviour.
Memory Management
Contiguous Allocation: Memory divided into partitions (fixed or variable size). External fragmentation occurs in variable partitioning. Paging: Divides logical memory into fixed-size pages and physical memory into frames. Eliminates external fragmentation, may have internal fragmentation. Segmentation: Divides memory into variable-sized segments based on program structure (code, data, stack). Virtual Memory: Allows execution of processes not entirely in memory using demand paging. Page replacement algorithms: FIFO, Optimal, LRU, LRU Approximation (Clock), Second Chance.
Deadlock
Deadlock occurs when processes wait indefinitely for resources held by each other. Four necessary conditions: Mutual Exclusion (resources cannot be shared), Hold and Wait (process holds resources while waiting for more), No Preemption (resources cannot be forcibly taken), Circular Wait (circular chain of processes waiting). Deadlock Handling: Prevention (break one condition), Avoidance (Banker's Algorithm), Detection and Recovery, Ignorance (Ostrich Algorithm). Banker's Algorithm checks if system is in safe state before granting resource requests.
Synchronisation Mechanisms
Race Condition: Multiple processes access shared data concurrently with outcome dependent on execution order. Critical Section: Code segment accessing shared resources; requires mutual exclusion. Solutions: Peterson's Solution (software), Mutex Locks (binary semaphore), Semaphores (counting and binary), Monitors (high-level abstraction). Classical Problems: Producer-Consumer (Bounded Buffer), Readers-Writers, Dining Philosophers. Deadlock can occur in Dining Philosophers if all pick up left fork simultaneously.
File System & I/O
File Allocation Methods: Contiguous (fast access, external fragmentation), Linked (no fragmentation, slow random access), Indexed (direct access, pointer overhead). Directory Structure: Single-level, Two-level, Tree-structured, Acyclic Graph (shared files), General Graph (allows cycles, requires garbage collection). Disk Scheduling: FCFS, SSTF (shortest seek time first), SCAN (elevator), C-SCAN, LOOK, C-LOOK. I/O Techniques: Programmed I/O, Interrupt-Driven I/O, DMA (Direct Memory Access) for large transfers without CPU intervention.
Worked examples
Example 1
Consider three processes arriving at time 0 with burst times: P1=24ms, P2=3ms, P3=3ms. Calculate average waiting time using FCFS and SJF scheduling.
FCFS (order: P1, P2, P3):
P1 completes at 24, waiting time = 0
P2 completes at 27, waiting time = 24
P3 completes at 30, waiting time = 27
Average waiting time = (0 + 24 + 27) / 3 = 17ms
SJF (order: P2, P3, P1):
P2 completes at 3, waiting time = 0
P3 completes at 6, waiting time = 3
P1 completes at 30, waiting time = 6
Average waiting time = (0 + 3 + 6) / 3 = 3ms
SJF reduces average waiting time significantly for short jobs.
Example 2
A system has 4 processes (P1-P4) and 3 resource types (R1=9, R2=3, R3=6). Allocation and Max matrices are given. Determine if the system is in a safe state using Banker's Algorithm. Allocation: P1(1,0,0), P2(2,1,0), P3(3,0,2), P4(2,1,1). Max: P1(3,2,1), P2(5,2,0), P3(6,0,3), P4(4,2,2).
Step 1: Calculate Need = Max Allocation
P1: (2,2,1), P2: (3,1,0), P3: (3,0,1), P4: (2,1,1)
Step 2: Calculate Available = Total sum(Allocation)
Available = (9,3,6) (8,2,3) = (1,1,3)
Step 3: Find safe sequence
Work = (1,1,3)
P1 needs (2,2,1) > Work -> skip
P2 needs (3,1,0) > Work -> skip
P3 needs (3,0,1), (3>1) -> skip
P4 needs (2,1,1) <= Work -> execute P4, Work = (1,1,3) + (2,1,1) = (3,2,4)
P1 needs (2,2,1) <= Work -> execute P1, Work = (3,2,4) + (1,0,0) = (4,2,4)
P2 needs (3,1,0) <= Work -> execute P2, Work = (4,2,4) + (2,1,0) = (6,3,4)
P3 needs (3,0,1) <= Work -> execute P3
Safe sequence exists: <P4, P1, P2, P3>. System is in SAFE state.
Example 3
A system uses demand paging with page fault service time = 8ms, memory access time = 200ns, and page fault rate = 0.001. Calculate effective access time.
Given:
Page fault service time = 8ms = 8,000,000ns
Memory access time = 200ns
Page fault rate (p) = 0.001 = 0.1%
Formula:
Effective Access Time = (1 p) x memory_access_time + p x page_fault_time
Calculation:
EAT = (1 0.001) x 200 + 0.001 x 8,000,000
EAT = 0.999 x 200 + 0.001 x 8,000,000
EAT = 199.8 + 8,000
EAT = 8,199.8ns ~= 8.2 s
Even with 0.1% page fault rate, effective access time is dominated by page fault overhead.
Example 4
Consider the dining philosophers problem with 5 philosophers. Explain how deadlock can occur and suggest a solution.
Problem Setup:
5 philosophers, 5 forks (one between each pair). Each philosopher needs 2 forks to eat.
Deadlock Scenario:
All 5 philosophers simultaneously pick up their left fork.
Each philosopher now holds 1 fork and waits for the right fork.
All philosophers are waiting -> circular wait -> DEADLOCK.
Solutions:
1. Allow at most 4 philosophers to sit at the table simultaneously.
2. A philosopher picks up forks only if both are available (atomic operation using mutex).
3. Odd-numbered philosophers pick left then right; even-numbered pick right then left (breaks circular wait).
4. Use a monitor with condition variables to manage fork access.
Solution 3 is most elegant - by changing the order for alternate philosophers, at least one philosopher will always be able to eat, breaking the cycle.
Representative solved questions
See the kind of question in this topic before opening the full practice set.
Question 1
What is a page fault?
An error in the page table
A trap to the software raised by the hardware when a process accesses a page not in physical memory
A corruption in the page file
A successful page replacement
Answer: B. A trap to the software raised by the hardware when a process accesses a page not in physical memory
ExplanationStep 1: When a process tries to access a page that is mapped in its virtual address space but not loaded in physical memory, a page fault occurs.\nStep 2: The MMU (Memory Management Unit) detects this and triggers a trap to the OS.\nStep 3: The OS then handles the fault by finding a free frame, loading the page from disk, and updating the page table.\nStep 4: This is a normal part of virtual memory operation, not necessarily an error.\nStep 5: Excessive page faults lead to thrashing.\nAnswer: A trap to the software raised by the hardware when a process accesses a page not in physical memory
Sources and review notes
This is an AISEA-authored practice question.
Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening
Question 2
Which of the following is a necessary condition for deadlock?
Preemption
Time-sharing
Mutual Exclusion
Multithreading
Answer: C. Mutual Exclusion
ExplanationStep 1: The four necessary conditions for deadlock are: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait.\\nStep 2: Mutual Exclusion means at least one resource must be held in a non-shareable mode.\\nStep 3: Preemption is the opposite — if preemption is allowed, deadlock can be prevented. Time-sharing and multithreading are OS features, not deadlock conditions.\\nAnswer: Mutual Exclusion
Sources and review notes
This is an AISEA-authored practice question.
Review status: accepted · Reviewed 2026-08-13 · structure and answer-key checks, editorial quality checks, duplicate screening
Common mistakes and useful habits
- For CPU scheduling problems, always draw a Gantt chart to visualise process execution order and calculate completion times accurately.
- Remember the key differences: Paging uses fixed-size blocks (eliminates external fragmentation), Segmentation uses variable-size blocks (matches program structure).
- In deadlock questions, check for ALL four necessary conditions. Breaking any one condition prevents deadlock.
- For page replacement algorithms, track frames visually. LRU approximates Optimal; FIFO suffers from Belady's anomaly.
- Banker's Algorithm: Always calculate 'Need' matrix first, then find a process that can execute with current Available resources.
- For disk scheduling, SCAN (elevator) and C-SCAN provide more uniform wait times than SSTF which may cause starvation.
Ready to test your understanding?
Work through 235 questions with explanations after each answer.