Operating Systems

Complete Guide — Theory + Calculations + Examples

Process Management • CPU Scheduling (Gantt Charts) • Synchronization

Deadlock (Banker's Algorithm) • Memory Management • Virtual Memory
Page Replacement • File System • Disk Scheduling • I/O Management

Full answers to every Exam / Viva / Interview question

Designed for: CSE Fresher • Lecturer Written Exam • Viva • Interview
 Table of Contents
Chapter 1 — OS Introduction & Structure
What is an OS?
OS Functions & Goals
Types of OS
OS Structure (Monolithic, Microkernel, Layered)
System Calls
Kernel vs User Mode
Chapter 2 — Process Management
What is a Process?
Process vs Program
PCB — Process Control Block
Process States & Transitions
Context Switching
Threads vs Processes
Chapter 3 — CPU Scheduling
Scheduling Criteria
FCFS — with Gantt chart & calculations
SJF (Non-preemptive & Preemptive/SRTF)
Round Robin — with quantum examples
Priority Scheduling
Multilevel Queue
Chapter 4 — Process Synchronization
Critical Section Problem
Mutex & Locks
Semaphore (Binary & Counting)
Classical Problems: Producer-Consumer, Readers-Writers, Dining Philosophers
Monitors
Chapter 5 — Deadlock
Necessary Conditions (MHCC)
Resource Allocation Graph
Deadlock Prevention
Deadlock Avoidance — Banker's Algorithm (full example)
Deadlock Detection & Recovery
Chapter 6 — Memory Management
Logical vs Physical Address
Contiguous Allocation (Fixed & Variable Partitioning)
Fragmentation (Internal & External)
Paging — address translation calculations
Segmentation
TLB
Chapter 7 — Virtual Memory & Page Replacement
Virtual Memory Concept
Demand Paging
Page Fault
FIFO Page Replacement (traced)
LRU Page Replacement (traced)
Optimal Page Replacement (traced)
 Belady's Anomaly
Thrashing
Chapter 8 — File System
File Attributes & Operations
File Allocation Methods: Contiguous, Linked, Indexed
Directory Structures
Free Space Management
File Protection
Chapter 9 — I/O Management & Disk Scheduling
I/O Hardware
I/O Software Layers
Disk Structure
FCFS Disk Scheduling (with calculation)
SSTF Disk Scheduling
SCAN & C-SCAN
LOOK & C-LOOK
Chapter 10 — Master Reference
All scheduling algorithms comparison
Page replacement comparison
Key formulas
Quick concept table
 CHAPTER 1

OS Introduction & Structure

What is an OS and how is it built?

1.1 What is an Operating System?

An Operating System (OS) is system software that manages computer hardware and software resources and
provides common services for computer programs. It acts as an intermediary between users/applications and
computer hardware.

Think of the OS as a government — it manages resources (CPU, memory, I/O), enforces rules (security, access
control), provides services (file system, networking), and allows multiple programs to run concurrently without
interfering with each other.

OS Role Description Example

Manages CPU, memory, I/O devices Decides which process gets CPU
Resource Manager fairly time

Hides hardware complexity behind

Extended Machine clean interface File system hides disk details

Process A cannot read Process B

Security Enforcer Protects processes from each other memory

Provides APIs (system calls) for

Service Provider programs fopen(), malloc(), printf()

1.2 Types of Operating Systems

Type Description Example

Jobs collected in batches, no user

Batch OS interaction during execution Early IBM systems

Multiple users share CPU in time

Time-Sharing OS slices simultaneously Unix, Linux

Guaranteed response within strict

Real-Time OS (RTOS) time deadlines Medical devices, aircraft, ATMs

Multiple computers work together as

Distributed OS one system Google's infrastructure

Designed for specific hardware with

Embedded OS limited resources Android (phones), VxWorks (routers)

Provides networking services to

Network OS multiple computers Windows Server, Novell NetWare

1.3 OS Structure
Structure Description Pros Cons
 Fast (no
All OS services in one large communication Hard to maintain, one bug
Simple/Monolithic kernel overhead) crashes all

OS divided into layers, each Easy to debug, Performance overhead

Layered using layer below modular crossing layers

Only essential services in

kernel (IPC, basic
scheduling). Rest in user Reliable, portable, Slower (user-kernel
Microkernel space secure switches for services)

Core kernel + loadable Module bugs can affect

Modular modules (like Linux) Flexible, efficient kernel

1.4 System Calls

System calls are the programming interface between user programs and the OS kernel. When a user program
needs an OS service (file access, memory allocation, process creation), it makes a system call. This causes a
trap to kernel mode.

Category System Calls Purpose

Process Control fork(), exec(), exit(), wait() Create, run, end processes

File Management open(), read(), write(), close(), unlink() File operations

Device Management ioctl(), read(), write() Device I/O

Information getpid(), alarm(), sleep() Get/set system info

Communication pipe(), socket(), send(), recv() IPC and networking

1.5 Dual Mode — Kernel vs User Mode

Hardware provides two execution modes to protect the OS from user programs:

• User Mode: Programs run with restricted privileges. Cannot directly access hardware, memory of other
processes, or execute privileged instructions. All user applications run here.
• Kernel Mode (Supervisor Mode): OS runs with full hardware access. Can execute any instruction, access
any memory, control all hardware. System calls switch from user to kernel mode via software interrupt (trap).

Exam / Viva / Interview — Questions & Answers

■ Q: What is an operating system? What are its main functions?

Ans:

An OS is system software that manages hardware resources and provides services to programs. Main functions: (1)
Process management — create, schedule, terminate processes. (2) Memory management — allocate/deallocate
memory, virtual memory. (3) File system — organize, store, retrieve files. (4) I/O management — control devices
uniformly. (5) Security — protect processes, files, users from each other. Acts as resource manager, extended machine,
and service provider.

■ Q: What is the difference between monolithic kernel and microkernel?

Ans:
 Monolithic kernel: all OS services (scheduling, file system, device drivers, networking) run in kernel space as one large
program. Fast (no context switches) but unreliable (one bug crashes all). Linux is mostly monolithic. Microkernel: only
minimal services (IPC, basic scheduling, memory management) in kernel. Everything else (file system, drivers) runs as
user-space servers. More reliable and portable, but slower due to user-kernel communication overhead. Examples:
Mach, MINIX, QNX.

■ Q: What is a system call? Why is it needed?

Ans:

System call is the interface between user programs and OS kernel. Needed because user programs cannot directly
access hardware or protected OS resources — this would be a security risk. When a program needs OS service (open a
file, allocate memory, create a process), it invokes a system call which causes a trap to kernel mode. OS validates the
request, performs the action, and returns to user mode. Examples: fork(), read(), write(), open(), malloc() (internally uses
brk() or mmap()).
 CHAPTER 2

Process Management
PCB, States, Threads

2.1 Process vs Program

Aspect Program Process

Passive — set of instructions stored

Definition on disk Active — program in execution

Storage Static (file on disk) Dynamic (in memory, changing)

Existence One program file Multiple processes from same program

Resources Needs no resources Has CPU, memory, files allocated

Example [Link] on disk Chrome running = multiple processes

2.2 Process Control Block (PCB)

The PCB (also called Task Control Block) is a data structure maintained by the OS for every process. It contains
all information needed to manage and restart a process. The PCB is the process's identity in the OS.

PCB Field Contains

Process ID (PID) Unique integer identifier for the process

Process State Current state: new, ready, running, waiting, terminated

Program Counter Address of next instruction to execute

CPU Registers All register values (saved during context switch)

CPU Scheduling Info Priority, scheduling queue pointers

Memory Management Info Page tables, segment tables, base/limit registers

I/O Status Info List of open files, I/O devices allocated

Accounting Info CPU time used, time limits, job numbers

2.3 Process States & Transitions

Five-State Model:

NEW ----admit----> READY <----I/O complete---- WAITING

| ^

dispatch (scheduler) I/O request

| |
 v |

RUNNING ------exit------> TERMINATED

NEW: Process being created

READY: Process waiting for CPU (in ready queue)

RUNNING: Process currently executing on CPU

WAITING: Process waiting for I/O or event (not using CPU)

TERMINATED: Process finished execution

Key Transitions:

New -> Ready: admitted to ready queue

Ready -> Running: scheduler dispatches (gives CPU)

Running -> Ready: preempted (time slice expired or higher priority)

Running -> Waiting: process requests I/O (voluntary)

Waiting -> Ready: I/O completed, back to ready queue

Running -> Terminated: process calls exit()

2.4 Context Switching

Context switching is the process of saving the state of the currently running process (into its PCB) and loading
the state of the next process (from its PCB). During context switch, no useful work is done — it is pure overhead.

Context switch steps: (1) Save PC, registers, state of current process to its PCB. (2) Update scheduling info. (3)
Move process to appropriate queue. (4) Select next process via scheduling algorithm. (5) Load next process's
PCB — restore registers, PC, memory maps. (6) Resume next process.

2.5 Threads vs Processes

Aspect Process Thread

Definition Independent program in execution Lightweight unit within a process

Memory Separate address space Shares address space with other threads

Resources Own code, data, files, registers Shares code, data, files; own stack, registers

Communication IPC needed (pipes, sockets) Shared memory (fast but needs sync)

Creation Expensive (fork()) Cheap (pthread_create())

Overhead High context switch cost Low context switch cost

Crash of one does not affect

Crash impact others One thread crash may kill entire process
Exam / Viva / Interview — Questions & Answers

■ Q: What is a PCB? What information does it contain?

Ans:

PCB (Process Control Block) is a data structure the OS maintains for every process — it IS the process to the OS.
Contains: PID (unique identifier), process state (ready/running/waiting), program counter (next instruction address), CPU
registers (saved during context switch), memory management info (page tables), I/O status (open files, devices),
scheduling info (priority), accounting info (CPU time used). During context switch, current process PCB is saved and
next process PCB is loaded.

■ Q: Explain all process states and transitions.

Ans:

Five states: NEW (being created), READY (waiting for CPU in queue), RUNNING (executing on CPU), WAITING
(blocked for I/O or event), TERMINATED (finished). Transitions: New->Ready (admitted), Ready->Running
(scheduled/dispatched), Running->Ready (preempted — time slice up or higher priority arrives), Running->Waiting
(requested I/O), Waiting->Ready (I/O complete), Running->Terminated (exit called).

■ Q: What is the difference between a process and a thread? Why use threads?

Ans:

Process: independent execution unit with own memory space. Thread: lightweight execution unit sharing memory with
other threads in same process. Threads are faster to create, have less context switch overhead, and share data easily
(no IPC needed). Use threads for: concurrent tasks sharing data (web server handling multiple requests), parallel
computation (matrix multiplication), background tasks (UI thread + download thread). Risk: shared memory requires
synchronization to avoid race conditions.
 CHAPTER 3

CPU Scheduling
Gantt Charts, Waiting Time, Turnaround Time

3.1 Scheduling Criteria

Metric Definition Goal

CPU Utilization % of time CPU is busy Maximize (100% ideal)

Number of processes completed per

Throughput unit time Maximize

Total time from submission to

completion: TAT = Completion -
Turnaround Time (TAT) Arrival Minimize

Time spent in ready queue: WT =

Waiting Time (WT) TAT - Burst Time Minimize

Time from submission to first

Response Time response Minimize (for interactive)

Key Formulas:

Turnaround Time (TAT) = Completion Time - Arrival Time

Waiting Time (WT) = TAT - Burst Time

Response Time = First CPU Time - Arrival Time

Average WT = Sum of all WT / Number of processes

Average TAT = Sum of all TAT / Number of processes

3.2 FCFS — First Come First Served

Non-preemptive. Processes served in order of arrival. Simple but can cause Convoy Effect — short processes
wait behind long ones.

Example: 4 processes

Process Arrival Burst

P1 0 6

P2 1 4

P3 2 2

P4 3 8
 Gantt Chart:

|--P1--|----P2----|--P3--|--------P4--------|

0 6 10 12 20

Completion Times: P1=6, P2=10, P3=12, P4=20

TAT = Completion - Arrival:

P1: 6-0=6, P2: 10-1=9, P3: 12-2=10, P4: 20-3=17

Average TAT = (6+9+10+17)/4 = 42/4 = 10.5

WT = TAT - Burst:

P1: 6-6=0, P2: 9-4=5, P3: 10-2=8, P4: 17-8=9

Average WT = (0+5+8+9)/4 = 22/4 = 5.5

3.3 SJF — Shortest Job First

Non-preemptive: at each scheduling point, pick the process with shortest burst time among all arrived
processes. Optimal — gives minimum average waiting time among all non-preemptive algorithms. Problem:
need to know burst time in advance (not always possible).

Same processes as above, SJF:

At t=0: only P1 arrived -> run P1 (burst=6)

At t=6: P2(4), P3(2), P4(8) all arrived -> pick P3 (shortest=2)

At t=8: P2(4), P4(8) -> pick P2 (shortest=4)

At t=12: only P4 -> run P4

Gantt Chart:

|--P1--|--P3--|----P2----|--------P4--------|

0 6 8 12 20

TAT: P1=6-0=6, P2=12-1=11, P3=8-2=6, P4=20-3=17

Average TAT = (6+11+6+17)/4 = 40/4 = 10.0

WT: P1=0, P2=11-4=7, P3=6-2=4, P4=17-8=9

Average WT = (0+7+4+9)/4 = 20/4 = 5.0

Compare: FCFS avg WT=5.5, SJF avg WT=5.0 (SJF is better!)

3.4 SRTF — Shortest Remaining Time First (Preemptive SJF)
Preemptive version of SJF. When a new process arrives,

compare its burst with REMAINING time of current process.

If new process is shorter, preempt current process.

Example:

Process Arrival Burst

P1 0 8

P2 1 4

P3 2 2

P4 3 1

t=0: P1 arrives, run P1 (remaining=8)

t=1: P2 arrives (burst=4) < P1 remaining(7) -> preempt P1, run P2

t=2: P3 arrives (burst=2) < P2 remaining(3) -> preempt P2, run P3

t=3: P4 arrives (burst=1) < P3 remaining(1)? NO, equal. P3 continues.

t=4: P3 finishes. P4(1) < P2 remaining(3) -> run P4

t=5: P4 done. P2 remaining=3. P1 remaining=7. Run P2.

t=8: P2 done. Run P1.

t=15: P1 done.

Gantt: |P1|P2|P3|P4|--P2--|-------P1-------|

0 1 2 3 4 8 15

TAT: P1=15-0=15, P2=8-1=7, P3=4-2=2, P4=5-3=2

WT: P1=15-8=7, P2=7-4=3, P3=2-2=0, P4=2-1=1

Avg WT = (7+3+0+1)/4 = 11/4 = 2.75 (optimal!)

3.5 Round Robin (RR)

Preemptive. Each process gets a fixed time quantum (time slice). After quantum expires, process is preempted
and added to end of ready queue. Fair, good response time. Key factor: quantum size. Too small = too many
context switches. Too large = degenerates to FCFS.
 Example: Quantum = 3

Process Arrival Burst

P1 0 5

P2 0 3

P3 0 4

Queue order: P1, P2, P3 (all arrive at 0)

t=0: P1 runs for 3 (quantum). P1 remaining=2.

t=3: P2 runs for 3 (full quantum, done!). P2 complete.

t=6: P3 runs for 3 (quantum). P3 remaining=1.

t=9: P1 runs for 2 (remaining, done!). P1 complete.

t=11: P3 runs for 1 (remaining, done!). P3 complete.

Gantt: |--P1--|--P2--|--P3--|P1|-P3|

0 3 6 9 11 12

Completion: P1=11, P2=6, P3=12

TAT: P1=11, P2=6, P3=12

WT: P1=11-5=6, P2=6-3=3, P3=12-4=8

Avg WT = (6+3+8)/3 = 17/3 = 5.67

Note: Larger quantum -> better TAT, worse response time

Smaller quantum -> better response time, more overhead

3.6 Priority Scheduling

Each process has a priority. Highest priority process runs first. Can be preemptive or non-preemptive. Problem:
Starvation — low priority processes may never run if high priority processes keep arriving. Solution: Aging —
gradually increase priority of waiting processes.

Algorithm Preemptive? Optimal? Starvation? Best For

FCFS No No No Batch jobs

Yes (long
SJF No Yes (avg WT) processes) Batch with known burst

SRTF Yes Yes (avg WT) Yes Interactive systems

Round Robin Yes No No Time-sharing, interactive

 Yes (low
Priority Both No priority) Real-time systems

MLFQ Yes No No General purpose OS

Exam / Viva / Interview — Questions & Answers

■ Q: Compare FCFS, SJF, and Round Robin scheduling algorithms.

Ans:

FCFS: non-preemptive, processes in arrival order. Simple but convoy effect — short processes wait behind long ones.
SJF: non-preemptive, shortest burst runs first. Optimal average waiting time among non-preemptive algorithms.
Problem: needs burst time in advance; starvation of long processes. Round Robin: preemptive, fixed quantum. Fair,
good response time, no starvation. Performance depends on quantum size — too small causes overhead, too large
becomes FCFS.

■ Q: Calculate average waiting time and turnaround time: P1(arrive=0,burst=5), P2(arrive=1,burst=3),

P3(arrive=2,burst=8), P4(arrive=3,burst=2) using SJF non-preemptive.

Ans:

At t=0: only P1 ready -> run P1 (burst=5). At t=5: P2(3),P3(8),P4(2) arrived -> pick P4(shortest=2). At t=7: P2(3),P3(8) ->
pick P2. At t=10: P3 -> run P3. Completion: P1=5,P4=7,P2=10,P3=18. TAT: P1=5,P4=7-3=4,P2=10-1=9,P3=18-2=16.
Avg TAT=(5+4+9+16)/4=8.5. WT: P1=0,P4=4-2=2,P2=9-3=6,P3=16-8=8. Avg WT=(0+2+6+8)/4=4.0

■ Q: What is the convoy effect in FCFS? How does Round Robin solve it?

Ans:

Convoy effect: one long process holds CPU while many short processes wait behind it — like a convoy of slow trucks
blocking fast cars. Example: P1(burst=100ms) arrives before P2,P3(burst=1ms each) — they wait 100ms unnecessarily.
Round Robin solves this by preempting every process after quantum expires (say 10ms), so short processes get CPU
time quickly without waiting for long processes to finish.
 CHAPTER 4

Process Synchronization
Critical Section, Semaphores, Classic Problems

4.1 The Critical Section Problem

When multiple processes/threads access shared data concurrently, and at least one modifies it, a race condition
can occur — the final result depends on the order of execution. The Critical Section is the code segment that
accesses shared data. Any solution must satisfy three properties:

• Mutual Exclusion: Only one process can be in critical section at a time.

• Progress: If no process is in critical section and some want to enter, selection cannot be postponed
indefinitely.
• Bounded Waiting: There must be a limit on how many times other processes can enter CS before a
waiting process is allowed in (no starvation).

4.2 Mutex (Mutual Exclusion Lock)

Mutex = binary lock. Two operations: lock() and unlock()

acquire() {

while(lock == busy) // spin-wait (busy-wait)

; // do nothing

lock = busy; // set lock

release() {

lock = free;

// Usage:

[Link]();

// critical section here

[Link]();

Problem with busy-wait: wastes CPU cycles spinning.

Solution: blocking mutex — process sleeps while waiting.

4.3 Semaphore
A semaphore is an integer variable accessed only through two atomic operations: wait() (P operation,
decrement) and signal() (V operation, increment). More powerful than mutex — can allow N processes
simultaneously (counting semaphore) or just 1 (binary semaphore = mutex).

Semaphore operations (MUST be atomic!):

wait(S) { // P operation

S--;

if(S < 0) {

add process to S.waiting_queue;

block(); // sleep, do not busy-wait

signal(S) { // V operation

S++;

if(S <= 0) {

remove process P from S.waiting_queue;

wakeup(P);

Binary Semaphore: S initialized to 1 (acts like mutex)

wait(mutex); // lock

// critical section

signal(mutex); // unlock

Counting Semaphore: S initialized to N

Allows N processes in critical section simultaneously

Used for resource pools (e.g., 5 database connections)

4.4 Classical Synchronization Problems

Producer-Consumer (Bounded Buffer)
 Problem: Producer adds items to shared buffer, Consumer removes.

Buffer size = N. Producer must wait if full. Consumer must wait if empty.

Semaphores:

mutex = 1 (mutual exclusion for buffer access)

empty = N (counting: number of empty slots)

full = 0 (counting: number of filled slots)

Producer: Consumer:

wait(empty); wait(full);

wait(mutex); wait(mutex);

add_item(buffer); remove_item(buffer);

signal(mutex); signal(mutex);

signal(full); signal(empty);

Dining Philosophers
5 philosophers sit at a round table with 5 chopsticks between them. Each needs 2 chopsticks to eat.
Philosophers alternate between thinking and eating. Problem: each picks up left chopstick, waits for right —
circular wait = deadlock!

Solutions:

1. Allow only 4 philosophers to sit at a time (asymmetric)

2. Pick up BOTH chopsticks atomically (if both available)

3. Odd-numbered philosophers pick left first, even pick right first

Solution using semaphore:

chopstick[5] = {1,1,1,1,1} // one semaphore per chopstick

Philosopher i:

while(true) {

think();

wait(chopstick[i]);

wait(chopstick[(i+1)%5]);

eat();
 signal(chopstick[i]);

signal(chopstick[(i+1)%5]);

// Problem: deadlock if all pick left simultaneously!

// Fix: philosopher 4 picks RIGHT first, others pick LEFT first

Exam / Viva / Interview — Questions & Answers

■ Q: What is the critical section problem? What are the three requirements for a solution?

Ans:

Critical section problem: multiple processes share data, only one should access critical section at a time. Three
requirements: (1) Mutual Exclusion — only one process in CS at any time. (2) Progress — if CS is free and processes
want to enter, a selection must be made in finite time (no indefinite postponement). (3) Bounded Waiting — limit on how
many times others can enter before a waiting process gets in (prevents starvation).

■ Q: What is a semaphore? Difference between binary and counting semaphore?

Ans:

Semaphore is an integer variable accessed only through atomic wait() (P) and signal() (V) operations. Binary semaphore
(mutex semaphore): initialized to 1, values only 0 or 1, provides mutual exclusion for one resource. Counting
semaphore: initialized to N, allows N simultaneous accesses, used for resource pools (e.g., limit 5 database
connections). Both prevent busy-waiting by blocking processes and adding to waiting queue when S<0.

■ Q: Explain the Producer-Consumer problem and its semaphore solution.

Ans:

Problem: Producer adds to bounded buffer (size N), Consumer removes. Producer must wait if buffer full, Consumer
must wait if empty — concurrent access needs synchronization. Solution: Three semaphores — mutex(=1) for mutual
exclusion, empty(=N) counting empty slots, full(=0) counting filled slots. Producer: wait(empty) -> wait(mutex) -> add ->
signal(mutex) -> signal(full). Consumer: wait(full) -> wait(mutex) -> remove -> signal(mutex) -> signal(empty). Order of
waits matters — wrong order can deadlock.
 CHAPTER 5

Deadlock
Detection, Prevention, Avoidance — Banker's Algorithm

5.1 What is Deadlock?

Deadlock is a situation where a set of processes are each waiting for a resource held by another process in the
set — creating a circular wait where no process can proceed. All processes are permanently blocked.

Classic example: P1 holds printer, wants scanner. P2 holds scanner, wants printer. Both wait forever.

5.2 Four Necessary Conditions (MHCC)

ALL four conditions must hold simultaneously for deadlock to occur. Eliminating any one prevents deadlock:

Condition Description How to eliminate

Resource cannot be shared — Make resources sharable (not always

Mutual Exclusion only one process uses it at a time possible, e.g., printer)

Process holds resources while Require all resources at once before

Hold and Wait waiting for more starting; or release before requesting

Resources cannot be forcibly Allow OS to preempt resources from

No Preemption taken from a process waiting processes

Circular chain: P1 waits P2, P2 Assign global ordering to resources;

Circular Wait waits P3, P3 waits P1 always request in increasing order

5.3 Banker's Algorithm — Deadlock Avoidance

The Banker's Algorithm checks whether granting a resource request will leave the system in a safe state. A safe
state means there exists a safe sequence — an ordering of all processes such that each process can get its
remaining needed resources using currently available + resources released by previously finished processes.

Setup:

n processes, m resource types

Available[m]: currently available resources

Max[n][m]: maximum demand of each process

Allocation[n][m]: resources currently allocated

Need[n][m]: remaining need = Max - Allocation

=== FULL WORKED EXAMPLE ===

n=5 processes (P0-P4), m=3 resource types (A,B,C)

Allocation Max Need Available

A B C A B C A B C A B C

P0 0 1 0 7 5 3 7 4 3 3 3 2

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3 4 3 1

Safety Algorithm:

Work = Available = [3,3,2], Finish = [F,F,F,F,F]

Step 1: Find process with Need <= Work:

P1: Need=[1,2,2] <= [3,3,2]? YES!

Finish[P1]=T, Work = Work + Alloc[P1] = [3,3,2]+[2,0,0] = [5,3,2]

Step 2: P3: Need=[0,1,1] <= [5,3,2]? YES

Work = [5,3,2]+[2,1,1] = [7,4,3]

Step 3: P4: Need=[4,3,1] <= [7,4,3]? YES

Work = [7,4,3]+[0,0,2] = [7,4,5]

Step 4: P0: Need=[7,4,3] <= [7,4,5]? YES

Work = [7,4,5]+[0,1,0] = [7,5,5]

Step 5: P2: Need=[6,0,0] <= [7,5,5]? YES

Work = [7,5,5]+[3,0,2] = [10,5,7]

Safe Sequence: -> SAFE STATE!

Resource Request Algorithm:

If P1 requests [1,0,2]:

Check: Request <= Need[P1]? [1,0,2] <= [1,2,2]? YES

Check: Request <= Available? [1,0,2] <= [3,3,2]? YES

Pretend to allocate: Available=[2,3,0], Alloc[P1]=[3,0,2], Need[P1]=[0,2,0]

 Run Safety Algorithm -> if SAFE, grant request

-> if UNSAFE, rollback, make P1 wait

Exam / Viva / Interview — Questions & Answers

■ Q: What are the four necessary conditions for deadlock?

Ans:

(1) Mutual Exclusion: resources not shareable — only one process uses at a time. (2) Hold and Wait: process holds
some resources while waiting for others. (3) No Preemption: resources cannot be forcibly taken. (4) Circular Wait: P1
waits for P2, P2 waits for P3, ..., Pn waits for P1. ALL four must hold for deadlock. Eliminate any one to prevent
deadlock.

■ Q: Explain Banker's Algorithm. What is a safe state?

Ans:

Banker's Algorithm is a deadlock avoidance algorithm. Safe state: a state where there exists at least one safe sequence
— an ordering of processes such that each process can finish using available + resources freed by previously finished
processes. Algorithm: when a process requests resources, pretend to allocate them, then run Safety Algorithm. If
resulting state is safe, grant request. If unsafe, make process wait. Requires knowing maximum resource needs in
advance.

■ Q: What is the difference between deadlock prevention, avoidance, and detection?

Ans:

Prevention: eliminate at least one of the four necessary conditions before deadlock can occur (e.g., require all resources
upfront — eliminates Hold and Wait). Avoidance: dynamically check each request to ensure system stays in safe state
(Banker's Algorithm) — requires advance knowledge of maximum needs. Detection: allow deadlock to occur, detect it
(Resource Allocation Graph or detection algorithm), then recover (kill process or preempt resources). Prevention is most
restrictive; detection allows most concurrency.
 CHAPTER 6

Memory Management
Paging, Segmentation, Address Translation

6.1 Logical vs Physical Address

Aspect Logical (Virtual) Address Physical Address

Generated by CPU during execution Memory Management Unit (MMU)

Seen by User program Actual RAM hardware

Value Starts from 0 for each process Actual location in RAM

Translation Done by MMU This IS the real address

The MMU (Memory Management Unit) translates logical addresses to physical addresses at runtime. This
allows processes to be loaded anywhere in physical memory while they see a clean 0-based address space.

6.2 Contiguous Memory Allocation

Strategy How it works Pros Cons

Allocate first hole large

First Fit enough Fast External fragmentation

Less wasted Slow (search all), tiny leftover

Best Fit Allocate smallest hole that fits space holes

Large leftover Slow, may run out of large

Worst Fit Allocate largest hole useful holes

• Internal Fragmentation: Allocated memory slightly larger than requested. Unused space INSIDE allocated
partition. Occurs in fixed-size partitioning.
• External Fragmentation: Enough total free memory but not contiguous. Scattered holes too small to use.
Occurs in variable-size partitioning. Solution: Compaction (expensive) or Paging.

6.3 Paging — Eliminating External Fragmentation

Paging divides physical memory into fixed-size blocks called frames, and logical memory into same-size blocks
called pages. Any page can be placed in any free frame — no need for contiguous physical memory! A page
table maps each logical page to its physical frame.

Address Translation in Paging:

Logical Address = (Page Number p, Page Offset d)

Physical Address = (Frame Number f, Page Offset d)

page_size = 2^n bytes -> offset requires n bits

 logical address size = m bits

number of pages = 2^(m-n)

Example: logical address space = 32 bits, page size = 4KB = 2^12

page number = upper (32-12) = 20 bits

page offset = lower 12 bits

number of pages = 2^20 = 1M pages

Full Example:

Page size = 256 bytes (2^8), Logical address = 847

p = 847 / 256 = 3 (page 3)

d = 847 mod 256 = 79 (offset 79)

Page table: page 3 -> frame 5

Physical address = 5 * 256 + 79 = 1280 + 79 = 1359

TLB (Translation Lookaside Buffer):

Hardware cache for page table entries

TLB hit: physical address in 1 cycle (very fast)

TLB miss: consult page table in memory (slow)

Effective Access Time = hit_rate * (TLB_time + mem_time)

+ (1-hit_rate) * (TLB_time + 2*mem_time)

6.4 Segmentation
Segmentation divides logical address space into variable-sized segments (code, data, stack, heap). Each
segment has a base (start in physical memory) and limit (size). Matches programmer's view of memory. Can
have external fragmentation.

Segment Table: each entry has (Base, Limit)

Logical Address = (Segment Number s, Offset d)

Translation:

1. Check: d < Limit[s]? If NO -> Segmentation Fault!

2. Physical Address = Base[s] + d

 Example:

Segment table: Seg0(base=1000,limit=400), Seg1(base=2500,limit=100)

Logical address (0, 300): offset 300 < limit 400? YES

Physical = 1000 + 300 = 1300

Logical address (1, 150): offset 150 < limit 100? NO -> ERROR!

Exam / Viva / Interview — Questions & Answers

■ Q: What is paging? How does address translation work in paging?

Ans:

Paging divides physical memory into fixed-size frames and logical memory into same-size pages. Any page maps to any
free frame — eliminates external fragmentation. Address translation: logical address = (page number p, offset d). Look
up page number in page table to get frame number f. Physical address = (f, d) = f * page_size + d. Example:
page_size=256, logical address 847: page=847/256=3, offset=847%256=79. If page 3 maps to frame 5, physical =
5*256+79=1359.

■ Q: What is the difference between internal and external fragmentation?

Ans:

Internal fragmentation: wasted space INSIDE an allocated partition — process gets slightly more than it needs, unused
space cannot be given to others. Occurs in fixed partitioning and paging (last page may be partially used). External
fragmentation: enough total free memory but scattered in non-contiguous pieces — no single hole large enough for a
process. Occurs in variable partitioning and segmentation. Solution for external fragmentation: paging (fixed frames, any
page anywhere) or compaction (expensive — moves processes together).
 CHAPTER 7

Virtual Memory & Page Replacement

FIFO, LRU, Optimal — Fully Traced

7.1 Virtual Memory Concept

Virtual memory allows executing processes that are not completely in main memory. Only the needed parts
(pages) are loaded — the rest remain on disk. This allows: running programs larger than physical RAM, more
programs simultaneously, efficient memory use.

Demand Paging: Pages are loaded only when accessed (on demand). When a process accesses a page not in
memory, a page fault occurs — OS loads the page from disk into a free frame.

Page Fault Handling:

1. Process accesses page -> check page table

2. Valid bit = 0 -> PAGE FAULT -> trap to OS

3. OS finds free frame (or evicts a page)

4. Load requested page from disk into frame

5. Update page table: set frame number, valid bit = 1

6. Restart the faulting instruction

Effective Access Time (EAT) with page fault:

EAT = (1-p) * memory_time + p * page_fault_time

p = page fault rate (probability)

page_fault_time ≈ 8ms (disk seek + read)

memory_time ≈ 200ns

Example: p=0.001 (1 fault per 1000 accesses)

EAT = 0.999*200ns + 0.001*8,000,000ns

= 199.8ns + 8000ns = 8199.8ns ≈ 40x slower!

This is why minimizing page faults is critical.

7.2 Page Replacement Algorithms

When a page fault occurs and no free frames exist, a page must be evicted. The page replacement algorithm
decides which page to evict. Goal: minimize page faults.
Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1

Number of frames: 3

=== FIFO (First In, First Out) ===

Replace the page that has been in memory the longest.

Ref: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 7

F1: 7 7 7 2 2 2 2 4 4 4 0 0 0 1 7

F2: - 0 0 0 0 3 3 3 2 2 2 2 2 2 0

F3: - - 1 1 1 1 0 0 0 3 3 3 3 3 3

Hit? F F F F H F F F F F F H H F F

Page Faults = 12 (F=fault, H=hit)

=== LRU (Least Recently Used) ===

Replace the page that has not been used for longest time.

Ref: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 7

F1: 7 7 7 2 2 2 2 4 4 4 0 0 0 1 7

F2: - 0 0 0 0 0 0 0 2 2 2 2 2 2 2

F3: - - 1 1 1 3 3 3 3 3 3 3 3 3 3

Hit? F F F F H F H F F H F H H F F

Page Faults = 10 (better than FIFO!)

=== OPTIMAL (OPT) ===

Replace page that will not be used for longest time in FUTURE.

(Cannot be implemented -- requires future knowledge)

(Used as benchmark to compare other algorithms)

Ref: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 7

F1: 7 7 7 7 7 7 7 4 4 4 4 4 4 4 7

F2: - 0 0 0 0 0 0 0 0 0 0 0 0 1 1

F3: - - 1 2 2 3 3 3 2 3 0 3 2 2 2
 Hit? F F F F H F H F H H F H H F F

Page Faults = 8 (minimum possible -- optimal!)

Algorithm Strategy Faults (example) Implementable?

Yes — easy with

FIFO Evict oldest loaded page 12 queue

Yes — with
LRU Evict least recently used 10 timestamp/stack

Evict page not needed longest in No — needs future

Optimal future 8 knowledge

Yes — with
LFU Evict least frequently used Varies counter

Yes — with
MFU Evict most frequently used Varies counter

• Belady's Anomaly: For FIFO, adding MORE frames can sometimes INCREASE page faults. This
counterintuitive behavior does not occur in LRU or Optimal.
• Thrashing: Process spends more time paging than executing. Occurs when too many processes compete
for too few frames — each process gets so few frames it page-faults constantly. Solution: Working Set Model
— allocate enough frames for each process's working set (set of pages actively used).

Exam / Viva / Interview — Questions & Answers

■ Q: Compare FIFO, LRU, and Optimal page replacement algorithms.

Ans:

FIFO: evict the page in memory longest — simple queue. Easy to implement. Suffers Belady's anomaly (more frames
can cause more faults). LRU: evict least recently used — approximates Optimal using past. No Belady's anomaly.
Harder to implement (need timestamps or stack). Better than FIFO in practice. Optimal: evict page not needed for
longest future time — minimum possible faults. Cannot implement (needs future). Used as benchmark. In practice: LRU
(or LRU approximations like Clock algorithm) is standard.

■ Q: What is Belady's Anomaly? Which algorithms suffer from it?

Ans:

Belady's anomaly: increasing the number of frames allocated to a process can INCREASE the number of page faults for
FIFO algorithm. Counterintuitive — more memory causes worse performance. Example: with 3 frames FIFO may have 9
faults, with 4 frames may have 10 faults. Only FIFO suffers from this. LRU and Optimal do NOT suffer from Belady's
anomaly — they are stack algorithms (set of pages in memory with n frames is always subset of pages with n+1 frames).

■ Q: What is thrashing? How is it prevented?

Ans:

Thrashing: process spends more time handling page faults than doing useful work. Happens when OS has too many
processes competing for limited frames — each gets too few frames to hold its working set. Every memory reference
causes a page fault, causing high disk I/O. CPU utilization drops. Prevention: (1) Working Set Model — track each
process's working set (pages used in last delta time references), only allow processes whose working sets fit in available
memory. (2) Page Fault Frequency — if page fault rate too high, give more frames; too low, take frames away. (3)
Reduce multiprogramming degree.
 CHAPTER 8

File System
Allocation Methods, Directory Structures

8.1 File Attributes & Operations

Attribute Description

Name Human-readable identifier ([Link])

Identifier Unique tag (inode number)

Type Extension or magic bytes (txt, exe, jpg)

Location Pointer to device and blocks on disk

Size Current file size in bytes

Protection Read/write/execute permissions (rwxrwxrwx)

Timestamps Created, last accessed, last modified

File operations: create, open, close, read, write, seek, delete, rename, get/set attributes.

8.2 File Allocation Methods

Contiguous Allocation
Each file occupies a set of contiguous blocks on disk. Directory entry: (file name, start block, length). Fast
sequential and direct access. Suffers external fragmentation. Pre-allocation requires knowing file size.

Example: File "A" starts at block 5, length 3

-> occupies blocks 5, 6, 7

Access block 3 of A: block 5+3-1 = 7 (direct access - fast!)

Problem: Files cannot grow easily (adjacent blocks may be occupied)

External fragmentation over time

Linked Allocation
Each file is a linked list of disk blocks. Each block contains a pointer to the next block. Directory entry: (file
name, start block, end block). No external fragmentation. Files can grow easily. Bad for random access — must
traverse from start.

Example: File "B" starts at block 9

Block 9 -> Block 16 -> Block 1 -> Block 10 -> NULL

 Access block 3: must traverse 9->16->1->10 (slow!)

FAT (File Allocation Table): variant where pointers stored in

separate table (FAT), not in data blocks. Used by FAT32 (Windows).

FAT can be cached in memory -> faster traversal.

Indexed Allocation
Each file has an index block containing all pointers to its data blocks. Directory entry: (file name, index block).
Supports direct access, no external fragmentation. Index block overhead. Used by Unix/Linux (inode).

Example: File "C" has index block at 19

Index block 19: [15, 8, 22, 1, 3, ...]

Block i of file -> index_block[i]

Access block 3: index_block[3] = 1 -> go to disk block 1 (fast!)

Unix inode structure:

Direct pointers (12): point directly to data blocks

Single indirect: pointer to block of pointers

Double indirect: pointer to block of pointers to blocks of pointers

Triple indirect: one more level

Max file size with 4KB blocks, 4-byte pointers:

Direct: 12 * 4KB = 48KB

Single indirect: 1024 * 4KB = 4MB

Double indirect: 1024 * 1024 * 4KB = 4GB

8.3 Directory Structures

Structure Description Pros Cons

One directory for all No same-name files, no

Single-level files Simple grouping

Two-level One directory per user User isolation No subdirectories

Hierarchical (modern Efficient, grouping

Tree-structured standard) possible Sharing complex

Allows shared files

Acyclic Graph (hard links) Sharing supported Dangling pointers on delete
 Arbitrary links Cycles possible, need
General Graph (symbolic links) Maximum flexibility garbage collection

Exam / Viva / Interview — Questions & Answers

■ Q: Compare contiguous, linked, and indexed file allocation methods.

Ans:

Contiguous: file in consecutive blocks. Fast sequential and direct access. External fragmentation, hard to grow. Linked:
blocks scattered, each has pointer to next. No fragmentation, easy growth. Slow random access (O(n) traversal).
Indexed: index block holds all pointers. No fragmentation, fast direct access. Index block overhead. Unix uses indexed
(inode) with direct + single/double/triple indirect pointers to support files of varying sizes efficiently.

■ Q: What is an inode in Unix? What does it contain?

Ans:

inode (index node) is a data structure in Unix/Linux file systems storing metadata about a file. Contains: file type,
permissions (rwx), owner (UID, GID), size, timestamps (created/modified/accessed), link count, and block pointers (12
direct + 1 single indirect + 1 double indirect + 1 triple indirect). Does NOT contain the filename — filename is stored in
directory entries that point to the inode by number. Each file has exactly one inode.
 CHAPTER 9

I/O Management & Disk Scheduling

FCFS, SSTF, SCAN, C-SCAN, LOOK

9.1 Disk Structure

• Platter: Circular disk coated with magnetic material
• Track: Concentric circles on a platter
• Cylinder: Set of tracks at same position across all platters
• Sector: Smallest addressable unit on a track (typically 512B or 4KB)
• Seek Time: Time to move arm to correct track (dominant delay)
• Rotational Latency: Time for sector to rotate under head
• Transfer Time: Time to actually read/write data

Total Access Time = Seek Time + Rotational Latency + Transfer Time

Seek time dominates -> minimize head movement!

9.2 Disk Scheduling Algorithms

Setup for all examples:

Disk has tracks 0-199

Current head position: 53

Request queue: 98, 183, 37, 122, 14, 124, 65, 67

=== FCFS (First Come First Served) ===

Serve requests in order of arrival.

Head movement: 53->98->183->37->122->14->124->65->67

|98-53|=45, |183-98|=85, |183-37|=146, |122-37|=85,

|14-122|=108, |124-14|=110, |65-124|=59, |67-65|=2

Total head movement = 45+85+146+85+108+110+59+2 = 640 cylinders

=== SSTF (Shortest Seek Time First) ===

Serve the request closest to current head position.

From 53: closest is 65 (dist=12)

From 65: closest is 67 (dist=2)

From 67: closest is 37 (dist=30)

From 37: closest is 14 (dist=23)

From 14: closest is 98 (dist=84)

From 98: closest is 122 (dist=24)

From 122: closest is 124 (dist=2)

From 124: closest is 183 (dist=59)

Total = 12+2+30+23+84+24+2+59 = 236 cylinders (much better!)

Problem: Starvation -- far requests may wait indefinitely

=== SCAN (Elevator Algorithm) ===

Head moves in one direction, serves all requests in that direction,

then reverses. Like an elevator.

Assume head moving toward higher tracks (direction: up):

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 (end)

Then reverse: 199 -> 37 -> 14

Total = (199-53) + (199-14) = 146 + 185 = 331 cylinders

=== C-SCAN (Circular SCAN) ===

Head moves in one direction only. When it reaches end, jumps

to beginning without serving requests on return (more uniform).

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199

Jump to 0 (no service): 0 -> 14 -> 37

Total service movement = (199-53) + (37-0) = 146+37 = 183

(Does not count jump 199->0 as useful movement)

 === LOOK & C-LOOK ===

Like SCAN/C-SCAN but head only goes as far as last request

(does not go to disk end). More efficient than SCAN/C-SCAN.

LOOK: 53->65->67->98->122->124->183 (reverse)->37->14

C-LOOK: 53->65->67->98->122->124->183 (jump)->14->37

Algorithm Head Movement Starvation? Best For

FCFS 640 (worst) No Light load

Yes (far
SSTF 236 requests) Moderate load

SCAN 331 No Heavy load

C-SCAN 183 No Heavy load, uniform

LOOK < SCAN No General purpose

C-LOOK < C-SCAN No Best practical choice

Exam / Viva / Interview — Questions & Answers

■ Q: Compare FCFS, SSTF, and SCAN disk scheduling algorithms.

Ans:

FCFS: serve requests in arrival order. Simple, fair, no starvation. High head movement (640 in example) — inefficient.
SSTF: serve closest request. Low head movement (236). Risk of starvation for far requests. SCAN (Elevator): move in
one direction serving all requests, reverse at end. Moderate movement (331), no starvation. C-SCAN: like SCAN but
return without serving — more uniform response time (183). LOOK/C-LOOK: like SCAN/C-SCAN but stop at last
request, not disk end — most efficient in practice.

■ Q: Calculate total head movement for SSTF: head at 50, requests: 90, 30, 70, 20, 45, 80.

Ans:

From 50: closest=45(dist=5) -> From 45: closest=30(dist=15) -> From 30: closest=20(dist=10) -> From 20:
closest=70(dist=50) -> From 70: closest=80(dist=10) -> From 80: closest=90(dist=10). Total = 5+15+10+50+10+10 =
100 cylinders.
 CHAPTER 10

Master Reference
All Algorithms, Formulas, Quick Revision

CPU Scheduling — Summary

Algorithm Type Preemptive? Starvation? Special

FCFS Simple queue No No Convoy effect

Yes (long
SJF Shortest burst first No processes) Optimal avg WT

Optimal avg WT
SRTF Shortest remaining Yes Yes (preemptive)

Round Robin Time quantum Yes No Good response time

Yes (low
Priority By priority Both priority) Aging solves starvation

MLFQ Multiple queues Yes Managed Used in modern OS

Page Replacement — Summary

Algorithm Strategy Belady's Anomaly? Performance

FIFO Evict oldest loaded YES Poor to moderate

LRU Evict least recently used No Good (near optimal)

Optimal Evict not needed longest No Best (benchmark only)

LFU Evict least frequently used No Moderate

Clock (2nd
chance) Approximate LRU No Good, efficient

Key Formulas
CPU SCHEDULING:

Turnaround Time (TAT) = Completion Time - Arrival Time

Waiting Time (WT) = TAT - Burst Time

Response Time = First CPU Start - Arrival Time

CPU Utilization (%) = (Total Burst Time / Total Time) x 100

MEMORY / PAGING:
 Physical Address = Frame Number x Page Size + Offset

Page Number = Logical Address / Page Size

Page Offset = Logical Address mod Page Size

Number of Pages = Logical Address Space / Page Size

Internal Fragmentation = Frame Size - (Process Size mod Frame Size)

EAT (with TLB) = h x (t_TLB + t_mem) + (1-h) x (t_TLB + 2xt_mem)

EAT (with page fault) = (1-p) x t_mem + p x t_page_fault

DISK:

Total Access Time = Seek Time + Rotational Latency + Transfer Time

Average Rotational Latency = (1/2) x Rotation Time

SEMAPHORE:

wait(S): S--; if S<0 -> block

signal(S): S++; if S<=0 -> wakeup one process

Quick Concept Reference

Concept One-Line Definition

OS data structure storing all info about a process (PID, state, registers,
PCB memory maps)

Save current process state to PCB, load next process PCB — pure
Context Switch overhead

Deadlock Circular wait: each process holds resource another needs

Mutual Exclusion Only one process in critical section at a time

Semaphore Integer variable with atomic wait(P) and signal(V) operations

Demand Paging Load pages from disk only when accessed (page fault on first access)

Thrashing Process spends more time paging than computing — too few frames

Belady's Anomaly More frames -> MORE page faults (only in FIFO)

Internal Fragmentation Wasted space inside allocated partition

External Fragmentation Free space exists but too scattered to use

Hardware cache for page table — speeds address translation

TLB significantly

Banker's Algorithm Deadlock avoidance: only grant request if safe state maintained
Aging Gradually increase priority of waiting processes — prevents starvation

Working Set Set of pages actively used by a process in last delta time window

inode Unix file metadata structure with direct + indirect block pointers

Disk scheduling: serve closest cylinder — reduces seek time but may
SSTF starve far requests

Simultaneous Peripheral Operations OnLine — buffer I/O for slow

Spooling devices (printer)

Best of luck for your OS exam, viva, and interview!