Operating Systems
Complete Study Guide: Theory + Exam Practice
Chapter Topic Page
1 What is an Operating System? 2
2 Process Concept - The Heart of OS 3-4
3 CPU Scheduling - Who Runs When? 5-8
4 Process Synchronization - Avoiding Chaos 9-12
5 Classical Problems & Solutions 13-14
6 Exam Question Bank 15-16
Chapter 1: What is an Operating System?
The Big Picture
Think of your computer as a restaurant:
• Hardware = Kitchen (ovens, stoves, utensils) - the actual equipment
• Operating System = Restaurant Manager - coordinates everything
• Applications = Chefs cooking different dishes - Word, Chrome, Games
• Users = Customers who want food - you!
Definition: An Operating System is software that manages computer hardware and provides services to programs. It's the middleman
between you and the machine.
Two Ways to Look at OS
User View System View
How easy is it to use? How efficiently are resources used?
Can I run my apps smoothly? Is CPU being utilized properly?
Is the interface friendly? Is memory allocated fairly?
Focus: Convenience Focus: Resource Management
Dual-Mode Operation: Protecting the System
Imagine if any app could directly control your computer's hardware - a buggy game could crash your entire system or a virus could
destroy everything!
Solution: Two Modes of Operation
User Mode: Where your apps run. Limited powers - can't directly touch hardware.
Kernel Mode: Where OS runs. Full powers - can do anything.
How it works: When your app needs something (read file, print), it makes a System Call which switches to Kernel Mode. OS does the
work, then switches back to User Mode.
EXAM: System calls are invoked using Software Interrupt (Trap) - this is how user mode switches to kernel mode!
System Calls: Asking OS for Help
A system call is like raising your hand in class to ask the teacher (OS) for something.
Category What it does Examples
Process Control Create/end programs fork(), exit(), wait()
File Management Work with files open(), read(), write(), close()
Device Management Use hardware read/write to printer, disk
Information Get system info time(), getpid()
Communication Programs talk to each other send(), receive()
Protection Security & permissions chmod(), chown()
OS Structures: How is OS Built?
Structure Idea Pros Cons Example
Monolithic Everything in one big kernel Very fast Hard to maintain, one bug crashes
Linux,
all Unix
Layered OS built in layers like a cake Easy to debug layer by layer
Slow, hard to design layers THE OS
Microkernel Tiny kernel, rest in user space Very reliable & secure Slower communication Minix, QNX
Hybrid Mix of above approaches Balance of speed & reliability
Complex Windows, macOS
Virtual Machine: Computer Inside a Computer
Imagine having multiple separate apartments inside one building. Each apartment (VM) thinks it has the whole building to itself!
Benefits: Isolation (virus in one VM can't affect others), run multiple OS on one machine, cost savings.
Chapter 2: Process Concept - The Heart of OS
Program vs Process: What's the Difference?
A recipe book sitting on your shelf is like a Program - it's just instructions, doing nothing.
When you start cooking using that recipe, it becomes a Process - active, using ingredients, following steps!
Program Process
Passive - just a file on disk Active - running in memory
Contains only code Contains code + data + stack + heap
One program can create many processes Each process is independent
Example: [Link] file Example: Chrome running with 5 tabs
Process Memory Layout
Every process gets its own memory space divided into 4 sections:
Section What it stores Grows?
Text The actual program code (instructions) Fixed size
Data Global and static variables Fixed size
Heap Dynamic memory (malloc, new) Grows UPWARD ↑
Stack Local variables, function calls Grows DOWNWARD ↓
The 5 Process States (VERY IMPORTANT!)
Think of a student in school:
• New = Just enrolled, not in class yet
• Ready = In class, hand raised, waiting to be called
• Running = Currently answering the teacher's question
• Waiting = Told to wait while teacher checks something
• Terminated = Graduated, left school
State Transitions:
NEW → READY: Process admitted to memory
READY → RUNNING: Scheduler picks this process (dispatch)
RUNNING → READY: Interrupted (time's up!) or preempted
RUNNING → WAITING: Process needs I/O (waiting for disk, keyboard)
WAITING → READY: I/O completed, ready to run again
RUNNING → TERMINATED: Process finished execution
EXAM TIP: Blocked process can NEVER go directly to Running! It must go to Ready first.
Process Control Block (PCB): The Process's ID Card
Just like your student ID card has all your info, every process has a PCB containing everything about it:
PCB Field What it stores Why needed?
Process ID Unique number (like roll number) To identify this process
Process State New/Ready/Running/Waiting/TerminatedKnow what it's doing
Program Counter Address of next instruction Resume from where it stopped
CPU Registers Values in CPU registers Restore CPU state
Memory Info Where process is in memory Access its data
I/O Status Files opened, devices used Manage resources
Scheduling Info Priority, time used For scheduling decisions
Context Switch: Changing the Active Process
When teacher switches from asking Student A to Student B, she mentally notes where A stopped (context). Same with CPU!
Steps: 1) Save PCB of current process → 2) Load PCB of new process → 3) Resume new process
Context switch is overhead - CPU does no useful work during switch. Too many switches = slow system!
Process Creation: fork() System Call
fork() creates an exact copy of the current process (parent creates child).
Key Point: After fork(), BOTH parent and child continue from the next line!
fork() returns: 0 to child, child's PID to parent
EXAM: fork(); fork(); printf("hi"); → prints "hi" 4 times (2² = 4 processes)
Chapter 3: CPU Scheduling - Who Runs When?
Why Do We Need Scheduling?
Imagine one doctor with 10 patients waiting. Who should be treated first? The one who came first? The one with minor issue (quick)?
The most critical? This is scheduling!
Goal: Keep CPU busy, be fair to all processes, minimize waiting time.
Key Terms You MUST Know
Term Meaning Formula
Arrival Time (AT) When process enters ready queue Given in question
Burst Time (BT) How long process needs CPU Given in question
Completion Time (CT) When process finishes From Gantt chart
Turnaround Time (TAT) Total time from arrival to completion TAT = CT - AT
Waiting Time (WT) Time spent waiting (not running) WT = TAT - BT
Response Time (RT) Time from arrival to first run RT = First Run - AT
Write these formulas FIRST in your exam answer!
Preemptive vs Non-Preemptive
At a bank, Non-preemptive = once you start with teller, you finish. Preemptive = VIP can interrupt you mid-transaction!
Non-Preemptive Preemptive
Once running, process keeps CPU until done or blocks
OS can take CPU away anytime
Simple, less overhead Complex, more context switches
FCFS, SJF SRTF, Round Robin, Priority
Poor response time for short jobs Better response time
Algorithm 1: FCFS (First Come First Served)
Rule: Whoever arrives first, runs first. Simple queue - like waiting in line at a shop.
Type: Non-preemptive
Example: All arrive at time 0
Process Burst Time
P1 24
P2 3
P3 3
Gantt Chart: | P1 (0→24) | P2 (24→27) | P3 (27→30) |
Calculations:
P1: CT=24, TAT=24-0=24, WT=24-24=0
P2: CT=27, TAT=27-0=27, WT=27-3=24
P3: CT=30, TAT=30-0=30, WT=30-3=27
Avg WT = (0+24+27)/3 = 17ms
Problem - Convoy Effect: Short processes stuck behind long one. If P2, P3 came before P1, Avg WT would be just 3ms!
Algorithm 2: SJF (Shortest Job First)
Rule: Process with shortest burst time runs first. Like express checkout for people with few items!
Type: Non-preemptive | Optimal for minimizing average waiting time
Same Example with SJF: Order becomes P2→P3→P1
Gantt Chart: | P2 (0→3) | P3 (3→6) | P1 (6→30) |
Avg WT = (0+3+6)/3 = 3ms (vs 17ms with FCFS!) - Much better!
Problem - Starvation: Long processes may never run if short ones keep arriving.
Algorithm 3: SRTF (Shortest Remaining Time First)
Rule: Like SJF, but PREEMPTIVE. If new process has shorter remaining time, SWITCH!
Imagine you're getting a haircut (20 min remaining). Someone walks in needing just a quick trim (5 min). Barber says 'wait' to you and
serves them first!
Solved Example (From Your Exam):
Process Arrival Burst
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Step-by-step Solution:
t=0: Only P1 here. Run P1 (remaining=8)
t=1: P2 arrives (burst=4). P1 remaining=7. Compare: 4 < 7? YES! Preempt P1, run P2
t=2: P3 arrives (burst=9). P2 remaining=3. Compare: 3 < 9? YES, continue P2
t=3: P4 arrives (burst=5). P2 remaining=2. Compare: 2 < 5? YES, continue P2
t=5: P2 done! Ready queue: P1(7), P3(9), P4(5). Shortest=P4. Run P4
t=10: P4 done! Ready queue: P1(7), P3(9). Shortest=P1. Run P1
t=17: P1 done! Only P3 left. Run P3
t=26: P3 done! All finished.
Gantt: |P1(0-1)|P2(1-5)|P4(5-10)|P1(10-17)|P3(17-26)|
Process AT BT CT TAT=CT-AT WT=TAT-BT
P1 0 8 17 17 9
P2 1 4 5 4 0
P3 2 9 26 24 15
P4 3 5 10 7 2
Avg TAT = (17+4+24+7)/4 = 13ms | Avg WT = (9+0+15+2)/4 = 6.5ms
Algorithm 4: Round Robin (RR)
Rule: Each process gets a fixed time slice (quantum). After that, go to back of queue.
Like a talking stick in a meeting - everyone gets 2 minutes, then passes it on!
Example: Time Quantum = 4
Process Burst
P1 24
P2 3
P3 3
How to solve RR:
1. P1 runs for 4ms (remaining=20), goes to back. Queue: [P2,P3,P1]
2. P2 runs for 3ms (done! burst < quantum). Queue: [P3,P1]
3. P3 runs for 3ms (done!). Queue: [P1]
4. P1 runs for 4ms (remaining=16). Queue: [P1]
5. Continue until P1 finishes at t=30
Gantt: |P1(0-4)|P2(4-7)|P3(7-10)|P1(10-14)|P1(14-18)|P1(18-22)|P1(22-26)|P1(26-30)|
Key insight: Large quantum → becomes FCFS | Small quantum → too many context switches
Algorithm 5: Priority Scheduling
Rule: Process with highest priority runs first. Usually lower number = higher priority.
Problem: Starvation - low priority may never run
Solution: Aging - increase priority of waiting processes over time
The Three Types of Schedulers
Scheduler When it runs What it does Frequency
Long-term When new job arrives Decides which jobs to admit to memory Minutes
(Job Scheduler)
Medium-term During execution Swaps processes in/out of memory Seconds
Short-term Very frequently Picks next process to run on CPU Milliseconds
(CPU Scheduler)
Inter-Process Communication (IPC)
Processes sometimes need to talk to each other. Two main ways:
Shared Memory Message Passing
Processes share a memory region Processes exchange messages
Like roommates sharing a whiteboard Like sending letters/texts
Fast - no kernel involvement Slower - kernel handles messages
Need synchronization (careful!) Safer, no sync needed
Good for large data Good for small messages
Chapter 4: Process Synchronization - Avoiding Chaos
The Problem: Race Condition
Imagine two people editing the same Google Doc at the exact same time, both trying to change the same sentence. Chaos!
Race Condition: When multiple processes access shared data simultaneously and the result depends on the order of execution.
Real Example - Bank Account:
Account has Rs.1000. Two ATM withdrawals happen simultaneously:
ATM1: Read balance (1000) → Withdraw 500 → Write balance (500)
ATM2: Read balance (1000) → Withdraw 700 → Write balance (300)
Problem: If both read 1000 before either writes, final balance could be wrong!
The Critical Section Problem
Critical Section: Part of code where shared data is accessed. Only ONE process should be here at a time!
Structure of a Process:
Entry Section ← Ask permission to enter
CRITICAL SECTION ← Access shared data (only 1 allowed!)
Exit Section ← Signal that you're leaving
Remainder Section← Rest of the code
Three Requirements for a Solution (MEMORIZE!)
Requirement What it means Analogy
1. Mutual Exclusion Only ONE process in CS at a time Only one person in bathroom
2. Progress If CS is free, waiting process must get in Don't keep bathroom locked when empty
3. Bounded Waiting Limit on how long anyone waits Can't hog bathroom forever
Hardware Solutions
Test-and-Set Instruction:
An atomic (uninterruptible) instruction that:
1. Reads the old value of a variable
2. Sets it to TRUE
3. Returns the old value
boolean TestAndSet(boolean *target) {
boolean old = *target; // Save old value
*target = TRUE; // Lock it
return old; // Return what it was
Using it: If TestAndSet returns FALSE → lock was free, you got it!
If it returns TRUE → someone else has the lock, keep trying.
Compare-and-Swap (CAS):
Compare value with expected. If equal, swap with new value. Return old value.
Mutex Locks
Mutex = Mutual Exclusion lock. Like a key to a room - only one person can have it.
acquire(): Get the lock. If busy, wait.
release(): Give up the lock.
Problem: Busy waiting (spinlock) - wastes CPU cycles while waiting!
Semaphores: The Better Solution
A semaphore is like a bouncer at a club with a counter showing how many can enter.
Semaphore: An integer variable accessed via two atomic operations:
wait(S) [also called P() or down()]:
wait(S) {
while (S <= 0) ; // wait if no resource
S--; // take one resource
signal(S) [also called V() or up()]:
signal(S) {
S++; // release one resource
Two Types of Semaphores
Binary Semaphore Counting Semaphore
Value: 0 or 1 only Value: 0 to N
Like a mutex - one resource Multiple resources available
Example: One printer Example: 5 printers in a pool
Problems with Semaphores
1. Deadlock:
Two or more processes waiting for each other forever. Like two cars at an intersection, each waiting for the other to go first!
// Process P1 // Process P2
wait(S); wait(Q);
wait(Q); ← stuck! wait(S); ← stuck!
2. Starvation: A process waits indefinitely because others keep getting the resource.
3. Priority Inversion:
Low priority process holds a lock that high priority process needs. Medium priority process runs instead!
Solution: Priority Inheritance - temporarily boost low priority process so it finishes faster.
EXAM: Race Condition Problem
Q: P1 and P2 share variable B=2. Find all possible values of B.
P1() { C=B-1; B=2*C; } P2() { D=2*B; B=D-1; }
Solution Method: List ALL possible orderings of the 4 operations:
P1 has: (1) C=B-1, (2) B=2*C
P2 has: (1) D=2*B, (2) B=D-1
Order Execution Final B
P1 completely, then P2 C=1, B=2, D=4, B=3 3
P2 completely, then P1 D=4, B=3, C=2, B=4 4
P1.1, P2.1, P2.2, P1.2 C=1, D=4, B=3, B=2 2
P1.1, P2.1, P1.2, P2.2 C=1, D=4, B=2, B=3 3
Answer: B can be {2, 3, 4} - three distinct values
Chapter 5: Classical Synchronization Problems
Problem 1: Bounded Buffer (Producer-Consumer)
A restaurant kitchen (producer) makes dishes and puts them on a counter (buffer). Waiters (consumers) take dishes to serve. Counter
has limited space!
The Problem:
• Producer shouldn't add to full buffer (overflow)
• Consumer shouldn't take from empty buffer (underflow)
• Only one should access buffer at a time (mutual exclusion)
Solution using Semaphores:
Semaphore Initial Value Purpose
mutex 1 Mutual exclusion for buffer access
empty N (buffer size) Counts empty slots
full 0 Counts filled slots
Producer Code:
while(true) {
produce_item();
wait(empty); // Wait for empty slot
wait(mutex); // Enter critical section
add_to_buffer(); // Add item
signal(mutex); // Exit critical section
signal(full); // Increment full count
Consumer Code:
while(true) {
wait(full); // Wait for item
wait(mutex); // Enter critical section
remove_from_buffer(); // Take item
signal(mutex); // Exit critical section
signal(empty); // Increment empty count
consume_item();
Key: Producer does wait(empty) then signal(full). Consumer does opposite!
Problem 2: Readers-Writers
A library book can be read by many people simultaneously, but only one person can write/edit at a time. While someone writes, no one
can read!
Rules:
• Multiple readers can read simultaneously ✓
• Only ONE writer can write at a time ✓
• No reading while writing (and vice versa) ✓
Solution (Readers Priority):
Variable Initial Purpose
rw_mutex (semaphore) 1 Exclusive access to data
mutex (semaphore) 1 Protect read_count
read_count (int) 0 Number of active readers
Writer:
wait(rw_mutex); // Get exclusive access
// ... write ...
signal(rw_mutex); // Release
Reader:
wait(mutex);
read_count++;
if (read_count == 1) wait(rw_mutex); // First reader locks writers
signal(mutex);
// ... read ...
wait(mutex);
read_count--;
if (read_count == 0) signal(rw_mutex); // Last reader unlocks
signal(mutex);
Key insight: First reader locks out writers. Last reader lets writers in.
Problem 3: Dining Philosophers
5 philosophers sit at a round table with 5 chopsticks (one between each pair). To eat, a philosopher needs BOTH chopsticks beside
them.
The Problem: If everyone picks up their left chopstick simultaneously, everyone waits for right chopstick forever → DEADLOCK!
Simple (but flawed) Solution:
semaphore chopstick[5] = {1,1,1,1,1};
Philosopher i:
wait(chopstick[i]); // Pick left
wait(chopstick[(i+1)%5]); // Pick right
// EAT
signal(chopstick[i]); // Put left
signal(chopstick[(i+1)%5]); // Put right
Solutions to prevent deadlock:
1. Allow only 4 philosophers to sit at once
2. Pick up both chopsticks atomically (or none)
3. Odd philosophers pick left first, even pick right first
Multi-Processor Scheduling
Concept Explanation
Asymmetric One master CPU does all scheduling, others just execute
Symmetric (SMP) Each CPU schedules itself from common/private queue
Processor Affinity Keep process on same CPU to reuse cached data
Soft Affinity OS tries to keep on same CPU, but may move
Hard Affinity Process strictly bound to specific CPU
Load Balancing Distribute work evenly across CPUs
Push Migration OS pushes tasks from busy to idle CPU
Pull Migration Idle CPU pulls tasks from busy CPU
Chapter 6: Exam Question Bank
Fork() Questions
Q: void main() { fork(); fork(); printf("yes"); } - How many times 'yes' printed?
Answer: 4 times. Formula: n fork() calls = 2^n processes = 2² = 4
Q: for(i=0; i<3; i++) fork(); - How many processes?
Answer: 2³ = 8 processes (loop runs 3 times = 3 forks)
True/False: Process State Transitions
Statement Answer Why?
Running → Ready TRUE Interrupt/preemption can do this
Ready → Running TRUE Scheduler dispatch
Blocked → Running FALSE Must go Ready first!
Blocked → Ready TRUE I/O completion
Ready → Blocked FALSE Must run to request I/O
Scheduling True/False
I. SRTF may cause starvation → TRUE (long jobs may never run)
II. Preemptive scheduling may cause starvation → TRUE
III. Round Robin better than FCFS for response time → TRUE
If asked which statements are true: Answer = All three (I, II, III)
Context Switch Counting
Q: Three processes arrive at 0, 2, 6 with bursts 10, 20, 30. Context switches with SRTF? (Don't count start/end)
t=0: P1 starts. t=2: P2 arrives, P1 remaining=8. 8<20, continue P1. t=6: P3 arrives, P1 remaining=4. 4<30, continue P1.
t=10: P1 done → Switch to P2 (CS#1). t=30: P2 done → Switch to P3 (CS#2).
Answer: 2 context switches
Quick Definitions
Term Definition
Multiprogramming Multiple programs in memory; CPU switches when one waits for I/O
Time Sharing CPU time divided among users for interactive computing
Real Time OS Guaranteed response within deadline (Hard/Soft)
Throughput Number of processes completed per unit time
Turnaround Time Time from submission to completion
Convoy Effect Short processes wait for long process (FCFS problem)
Starvation Process waits indefinitely (Priority/SJF problem)
Aging Gradually increase priority of waiting processes
Scheduling Algorithm Comparison
Algorithm Type Advantage Disadvantage
FCFS Non-preemptive Simple, fair Convoy effect
SJF Non-preemptive Optimal avg WT Need burst time, starvation
SRTF Preemptive Better than SJF High overhead, starvation
Priority Both Important tasks first Starvation (solve: aging)
Round Robin Preemptive Fair, good response Higher avg WT than SJF
Good Luck! Remember: Understand concepts first, formulas second, practice problems third!