OPERATING SYSTEMS

Complete Mid-Semester Study Notes

BSDCBZC364 | BITS Pilani WILPD | Closed Book | 30% | 2 Hours
Deep Notes + Exam Q&A mapped to paper + All Formulas + 10-Day Plan

COURSE CONTENT & EXAM QUESTION MAPPING

# Module / Topic Sub-Topics Questions Asked in Paper

1 Introduction to OS CS Organization, Architecture, OS Structure, Q.1A — System calls (3M)
Operations, Components, Design Issues Q.2 — OS Structures (6M)
2 Processes & Threads Process Concept, Scheduling, Operations, IPC, Q.1B — Multithreading
Thread Models, Thread Libraries, Threading model & threading issues
Issues (3M)
3 Process Scheduling Basic Concepts, Criteria, FCFS/SJF/Priority/RR, Q.3 — Non-Preemptive
Thread Scheduling, Multi-processor Priority Scheduling full
numerical (6M)
4 Process Synchronization Critical Section, Peterson's Algorithm, Q.4A — Peterson's trace
Semaphores, Monitors, Classic Problems (3M) Q.4B — Semaphores
vs Monitors (3M) Q.5 —
Dining Philosopher's (6M)
5 Deadlock System Model, 4 Conditions, Prevention, Likely question in future
Banker's Algorithm, Detection, Recovery papers
6 Memory Management Paging, Segmentation, Contiguous Allocation, Numerical questions likely
Swapping, Page Table Structure
7 Virtual Memory Demand Paging, Page Replacement Numerical questions likely
(FIFO/LRU/OPT), Frames, Thrashing
8 File Systems Structure, Implementation, Allocation Conceptual questions
Methods, Free Space, Efficiency, Recovery, NFS likely

HOW TO USE THIS DOCUMENT

Step 1: Read each module's notes carefully — every concept is explained with examples.
Step 2: After each module, attempt the Q&A section before checking the model answer.
Step 3: For Sample Paper solutions — see the dedicated section at the end.
Step 4: Use the Formula Sheet and 10-Day Plan in the last pages for final revision.
MODULE 1: Introduction to Operating Systems
Exam Questions from This Module: Q.1A (System Calls — 3 marks) | Q.2 (OS Structures — 6 marks)

1.1 What is an Operating System?

An OS is system software that acts as an intermediary between users/applications and hardware. It manages
hardware resources, provides services to applications, and creates an abstract environment in which programs can
execute safely.

OS Role What It Does Real Example

Resource Manager Allocates CPU, memory, I/O devices fairly Deciding which of 10 open
among competing processes Chrome tabs gets CPU time
next
Control Program Prevents erroneous/malicious programs Stopping a program from
from harming the system reading another process's
memory
Interface Provider Provides GUI or command-line interface Windows Desktop, Linux shell
between user and hardware (bash)
Abstraction Layer Hides hardware complexity — programs use Reading '[Link]' without
file names not disk sectors knowing which disk track it
occupies
Security Enforcer Controls access permissions to files, Linux file permissions: rwxr-xr--
memory, and devices

1.2 Computer System Organization

A computer system has one or more CPUs and device controllers connected through a common bus that provides
access to shared memory. Key concepts:

Bootstrap Program
• Stored in ROM/EEPROM firmware (BIOS/UEFI) — first code that runs at power-on
• Its job: initialize hardware registers, device controllers, then locate and load the OS kernel into RAM
• After kernel loads, it initialises OS data structures, then spawns the first process (init/systemd on Linux)

Interrupts — The Heart of Modern OS

An interrupt is a hardware or software signal that causes the CPU to suspend its current task and execute a special
routine called an Interrupt Service Routine (ISR).

Interrupt Type Triggered By Example

Hardware Interrupt External device signals CPU that it Disk finishes reading data → signals CPU;
needs attention keyboard key pressed
Software Interrupt (Trap) Program executes INT instruction — Application calls read() → INT instruction
used for system calls → OS takes over
Exception CPU detects error condition during Division by zero, page fault, invalid
 execution memory access
Non-Maskable Interrupt Critical hardware failure — cannot Power failure imminent signal; memory
(NMI) be disabled parity error

• Interrupt Vector Table (IVT): Array of addresses — one per interrupt type. CPU uses interrupt number as
index to find the ISR address
• Interrupt Latency: Time from interrupt signal to ISR start — must be minimised in real-time systems

DMA — Direct Memory Access

Without DMA, the CPU must supervise every byte transferred between I/O device and memory — wasteful. DMA
allows a device controller to transfer data directly to/from memory without CPU intervention.
• CPU programs DMA controller: source, destination, transfer size
• DMA performs the transfer independently while CPU does other work
• DMA raises interrupt when complete — CPU only interrupted once per block, not once per byte
• Cycle stealing: DMA occasionally takes a memory bus cycle from CPU — minor slowdown

1.3 Computer System Architecture

Architecture Description Advantage Disadvantage Exampl
e
Single-Processor One general-purpose CPU. One Simple design and No parallelism — Old PCs,
process at a time in strict sense OS bottleneck embedd
ed
systems
Multi-Processor Multiple CPUs share memory N× throughput; fault Cache coherence Modern
(SMP) and system bus. All CPUs run tolerant complexity servers
same OS
Multi-Core Multiple cores on single chip Low power vs Thermal throttling Intel
share LLC cache multiple chips; fast Core i9,
cache sharing AMD
Ryzen 9
NUMA Multiple processor boards, Scales beyond OS must be NUMA- High-
each with own local memory. single-bus limit aware for end
Fast local, slow remote access performance Xeon
servers
Clustered Multiple full systems connected Extreme scalability; Complex Google/
by LAN/Infiniband. Each node HA failover management; Amazon
runs own OS network latency data
centers

• SMP (Symmetric Multiprocessing): Most common today. All CPUs are peers — any CPU can run any process.
Single ready queue or per-CPU queues with load balancing
• Asymmetric Multiprocessing: One master CPU runs OS; others run user processes on master's instructions —
simpler but bottleneck at master
1.4 Operating System Structure
How the OS code is organised determines performance, reliability, maintainability, and extensibility. The sample
paper Q.2 asks for all three below with diagrams and pros/cons.

A. Monolithic Structure
All OS services run together in a single large kernel address space. Every component can call every other component
directly via function calls.

Structure (ASCII — draw this in exam):

┌─────────────────────────────────────────┐
│ USER PROGRAMS │
├─────────────────────────────────────────┤
│ System Call Interface │
├─────────────────────────────────────────┤
│ ┌──────────────────────────────────┐ │
│ │ MONOLITHIC KERNEL │ │
│ │ Scheduler | Memory Manager │ │
│ │ File System | Device Drivers │ │
│ │ Networking | IPC | Security │ │
│ └──────────────────────────────────┘ │
├─────────────────────────────────────────┤
│ HARDWARE │
└─────────────────────────────────────────┘

Monolithic — Advantages Monolithic — Disadvantages

Very high performance — direct function calls, zero Extremely large, complex codebase — difficult to
context-switch overhead between subsystems maintain, debug, and extend
Simple design — all services visible to all other No isolation — one faulty driver crashes the entire
services kernel
Low overhead for OS service calls Adding new features requires recompiling entire
kernel
Examples: Traditional Linux kernel, early UNIX Poor security isolation between kernel components

B. Layered Structure
OS divided into N numbered layers. Layer 0 = bare hardware. Layer N = user interface. Each layer only uses services
provided by the layer directly below it.

Layer 5: User Programs

Layer 4: User I/O Management
Layer 3: Operator-Process Communication
Layer 2: Memory Management
Layer 1: CPU Scheduling
Layer 0: Hardware

Layered — Advantages Layered — Disadvantages

Modularity — each layer is independently testable Performance overhead — every request traverses
and replaceable multiple layers
 Easy debugging — test each layer in isolation from Difficult to define clean boundaries — what belongs
bottom up in which layer?
Abstraction — each layer hides its implementation Top layers are far from hardware — deep call chains
from the layer above are slow
Example: THE OS (Dijkstra, 1968), early MULTICS Rarely used in pure form in modern systems

C. Microkernel Structure
Minimal kernel contains ONLY: IPC (inter-process communication), basic memory management, CPU scheduling. ALL
other services (file system, device drivers, networking) run as user-space server processes. Communication via
message passing.

┌──────────────────────────────────────────────┐
│ USER SPACE │
│ [File Server] [Device Driver] [Net Server] │
│ [User App] [Window Server] [Print Server] │
├────────────── message passing ───────────────┤
│ MICROKERNEL │
│ Basic IPC | Memory Mgmt | CPU Sched │
├──────────────────────────────────────────────┤
│ HARDWARE │
└──────────────────────────────────────────────┘

Microkernel — Advantages Microkernel — Disadvantages

High reliability — faulty server crashes without Significant performance overhead — IPC for every OS
taking down kernel service request
Easy to extend — add new services as user-space Complex IPC mechanism design — must be very
processes efficient
Easy to port — most code in user space, hardware- Worse raw performance than monolithic for same
independent workload
Secure — services isolated from each other and Example: Mach, QNX, L4, MINIX 3, Symbian OS
kernel

Additional Structure: Modular / Hybrid (common in modern OS)

Modular: Core kernel + dynamically loadable modules. Linux uses this — you can insmod/rmmod
drivers without rebooting. Best of monolithic (performance) and microkernel (modularity).
Hybrid: Windows NT uses a layered/monolithic hybrid. macOS uses a Mach microkernel + BSD
subsystem hybrid. Most real-world OS are hybrid.

1.5 Operating System Operations

Dual-Mode Operation — Critical Concept
The CPU hardware provides two operating modes, controlled by a mode bit in the processor status register:

Mode Mode Bit Capabilities Who Runs Here

Kernel Mode (Privileged) 0 Can execute ALL instructions including OS kernel code
 privileged ones — I/O, memory only
management, interrupt control
User Mode (Restricted) 1 Cannot execute privileged instructions All user
— attempting one causes a hardware programs and
exception applications

• System Call: The ONLY sanctioned way for user programs to request kernel services. Causes a trap (software
interrupt) → CPU switches to kernel mode → OS validates and executes request → returns to user mode
• Timer Hardware: Prevents any process from monopolising CPU. Timer interrupt fires after a set interval →
OS regains control → can preempt the process
• Privileged Instructions: Halt CPU, access I/O ports, modify interrupt table, access memory management
registers — ONLY in kernel mode

Why Dual Mode Matters (Q.1A connection)

Without dual mode, any user program could: (1) Execute I/O instructions directly — bypassing OS
security (2) Modify interrupt vectors — taking over the machine (3) Access any memory address —
reading other processes' data.
System calls are the ONLY bridge: user program → software interrupt → kernel validates → executes →
returns. This is exactly why programs MUST use system calls instead of accessing hardware directly.

1.6 System Calls — Deep Dive

System calls are the programming interface between user programs and OS services. They are the boundary crossing
from user mode to kernel mode.

Category System Calls Design Goal Served Example Use

Process Control fork(), exec(), exit(), wait(), kill(), Process management; Shell creates
getpid() resource allocation new process:
fork() then
exec() the
command
File Management open(), read(), write(), close(), Abstraction; Any program
create(), delete(), lseek() protection; reading/writing
persistence files
Device Management ioctl(), read(), write(), open() on Hardware Printer driver;
device files abstraction; uniform serial port
interface access
Information Maintenance getpid(), alarm(), sleep(), Diagnostics; time Profiling tools;
gettimeofday() management cron jobs
Communications pipe(), socket(), send(), recv(), IPC; network Web server
shmget(), mmap() communication receiving HTTP
requests
Protection chmod(), setuid(), getuid(), umask() Security; access File permission
control management
Parameter Passing to System Calls — 3 Methods
• Method 1 — Registers: Pass parameters directly in CPU registers. FAST. LIMITATION: only a few registers
available — cannot pass many or large parameters
• Method 2 — Memory Block/Table: Store parameters in a memory block; pass the address of that block in
one register. Linux uses this. No limit on number/size of parameters
• Method 3 — Stack: Push parameters onto program stack; OS pops them off. Flexible; no register limit

1.7 System Programs

System programs provide a convenient environment for program development and execution. They sit between OS
services and user applications:

Category Examples Purpose

File Management ls, cp, mv, rm, mkdir, find Create, delete, copy, rename, list files
and directories
Status Information top, ps, df, du, date, who Query system state: CPU usage, disk
space, running processes
File Modification Text editors (nano, vim), sed, awk Create and modify text files
Programming Support Compilers (gcc), Assemblers, Support program development lifecycle
Debuggers (gdb), Linkers
Program Loading & Loaders, dynamic linkers, shell Load compiled programs into memory
Execution and execute them
Communications ssh, ftp, mail, ping, telnet Create virtual connections between
processes, users, systems
Application Programs Browsers, word processors, End-user applications — not strictly OS
databases but supplied with OS

1.8 OS Design & Implementation

• Policy vs Mechanism (KEY distinction): Mechanism = HOW something is done (e.g., timer interrupt). Policy =
WHAT will be done (e.g., how long each process gets). Separating them allows policy to change without
redesigning mechanisms
• Design Goals — User perspective: convenient, easy to learn, reliable, safe, fast
• Design Goals — System perspective: easy to design/implement/maintain, flexible, reliable, error-free,
efficient
• Implementation: Early OS in assembly language (efficiency). Today mostly C/C++ with assembly only for
interrupt handlers and context switching. High-level language → easier to port, debug, maintain; slight
performance cost

EXAM QUESTIONS — MODULE 1

Q: Q.1A: Explain why programs must use system calls instead of accessing hardware directly.
Classify any 2 types of system calls and relate them to OS structure/design goals. [3 Marks]
MODEL ANSWER:
WHY SYSTEM CALLS ARE REQUIRED (1.5 marks):
Programs must use system calls — not direct hardware access — for three fundamental reasons rooted
in the Dual-Mode Operation mechanism:

1. Protection via Dual Mode: Hardware provides two modes — User mode (restricted) and Kernel mode
(privileged). In user mode, privileged instructions (direct I/O, interrupt control, memory management)
are ILLEGAL — executing one causes a hardware exception and the OS terminates the offending
process. The system call is the ONLY authorised mechanism for transitioning to kernel mode, where
hardware can be safely accessed.

2. Security and Validation: The OS validates every system call request before executing it. If a program
called hardware directly, it could read other processes' memory, corrupt the file system, or take control
of I/O devices. The system call interface allows the OS to check permissions, validate parameters, and
enforce access control.

3. Abstraction and Portability: System calls provide a uniform hardware-independent interface. A

program calling write() works on any hardware — disk, SSD, network socket — without change. Direct
hardware access would make programs hardware-specific and unportable.

TWO SYSTEM CALL TYPES + DESIGN GOALS (1.5 marks):

(a) Process Control — fork(), exec(), exit(), wait():

These manage the lifecycle of processes. Design Goal: Resource Management — the OS must track all
processes, allocate CPU and memory, and clean up on termination. In a Monolithic OS, these are direct
kernel function calls (fast). In a Microkernel, they communicate with a process management server via
IPC.

(b) File Management — open(), read(), write(), close():

These provide controlled access to the file system. Design Goal: Abstraction and Protection — users
access files by name (not disk block addresses), and the OS enforces read/write/execute permissions.
Supports the layered OS structure's I/O management layer.

Q: Q.2: Explain Monolithic, Layered, and Microkernel OS structures with diagrams. Advantages
and disadvantages. [6 Marks — 2 each]
MODEL ANSWER:
MONOLITHIC STRUCTURE [2 marks]:
All OS services (scheduler, memory manager, file system, device drivers, networking) run together in a
single kernel address space. Components communicate via direct function calls.
Diagram: User Programs → [System Call Interface] → [MONOLITHIC KERNEL: all services together] →
Hardware
Advantages: (1) Very high performance — no overhead switching between components; (2) Simple
design — all kernel parts directly accessible to each other.
Disadvantages: (1) Reliability — one faulty driver crashes the entire system; (2) Hard to maintain —
huge, tangled codebase; (3) No isolation between kernel components.
Example: Traditional Linux kernel, early UNIX.

LAYERED STRUCTURE [2 marks]:

OS divided into N numbered layers. Layer 0 = hardware, Layer N = user interface. Each layer ONLY uses
services from the layer immediately below it — strict hierarchy enforced.
Diagram: Layer 5 (User) → Layer 4 (I/O) → Layer 3 (Memory) → Layer 2 (Scheduling) → Layer 1
(Hardware abstraction) → Layer 0 (Hardware)
Advantages: (1) Easy debugging — test each layer independently from the bottom up; (2) Modularity —
change one layer without affecting others.
Disadvantages: (1) Performance overhead — every service call must traverse multiple layers; (2)
Difficult to define clean layer boundaries in practice.
Example: THE OS (Dijkstra), early MULTICS.

MICROKERNEL STRUCTURE [2 marks]:

Minimal kernel contains ONLY: IPC, basic memory management, CPU scheduling. All other services (file
system, drivers, networking) run as isolated user-space server processes communicating via message
passing.
Diagram: [File Server | Device Driver | Net Server | User App] (user space) ↕ message passing ↕
[MICROKERNEL: IPC + Memory + Scheduling] ↕ Hardware
Advantages: (1) High reliability — faulty server crashes without affecting kernel; (2) Easy to extend —
add services as user-space processes; (3) Easy to port.
Disadvantages: (1) Performance overhead — every OS service requires IPC (user→kernel→user); (2)
Complex IPC design required.
Example: Mach, QNX, L4, MINIX 3.
MODULE 2: Concept of Processes and Threads
Exam Questions from This Module: Q.1B — Multithreading model causing slowdown + threading issues (3 marks)

2.1 Process Concept

A process is a program in execution — a dynamic entity with its own address space and execution state. A program is
a passive binary stored on disk; a process is active with resources allocated to it.

Process State Description Transition Trigger

New Process being created; OS allocating fork() called; job submitted
resources
Ready Process waiting to be assigned to CPU; in I/O complete; new process
ready queue created; preempted
Running Instructions actively executing on CPU; only Selected by CPU scheduler (short-
ONE per CPU core term scheduler)
Waiting (Blocked) Process waiting for event — I/O completion, Process calls read(), wait(), or
signal, lock release sleep()
Terminated Process finished; OS de-allocating exit() called; killed by signal
resources; entry in process table still exists

Process Control Block (PCB) — Everything OS Knows About a Process

PCB Field Contents Why Needed
Process State New/Ready/Running/Waiting/ Determines what to do with this
Terminated process
Process ID (PID) Unique integer identifier Distinguish processes; used in kill(),
wait()
Program Counter Address of next instruction to Must save/restore on context switch
execute
CPU Registers All register values (accumulator, Must save/restore entirely on
stack pointer, etc.) context switch
Memory Management Info Page tables, segment tables, Identify process's memory space
base/limit registers
I/O Status Open file descriptors, I/O devices Know what resources process holds
allocated
Accounting Info CPU time used, process creation Billing, scheduling decisions,
time, time limits debugging
Scheduling Info Priority, scheduling queue pointers Used by CPU scheduler

Context Switch Cost

When CPU switches from Process A to Process B:
1. Save ALL of A's CPU state (registers, PC, flags) into A's PCB
2. Load ALL of B's CPU state from B's PCB into CPU registers
3. Switch memory maps (TLB flush — expensive!)
 This is PURE OVERHEAD — no useful work done. Modern CPUs provide multiple register sets to reduce
this cost.

2.2 Process Scheduling

Scheduler Type Also Called Selection From Frequency Purpose
Long-term Scheduler Job Scheduler Job pool on disk Slow — Decides
minutes to which jobs
hours enter
memory
(ready
queue).
Controls
degree of
multiprogr
amming
Short-term Scheduler CPU Scheduler Ready queue in Very fast — Selects
memory milliseconds which
ready
process
gets CPU
next. Most
critical for
performan
ce
Medium-term Scheduler Swapper Memory / disk Medium Swaps
processes
in/out of
memory
to manage
multiprogr
amming
level and
free RAM

• Degree of multiprogramming: Number of processes simultaneously in memory. Long-term scheduler

controls this
• I/O-bound process: Spends more time doing I/O than computation — needs short CPU bursts
• CPU-bound process: Spends more time computing — needs long CPU bursts
• Good mix: Long-term scheduler should maintain a good mix of I/O-bound and CPU-bound processes

2.3 Operations on Processes

Process Creation — fork() and exec()
pid = fork(); // Creates EXACT copy of parent process
// fork() returns:
// 0 → in child process
// child_PID → in parent process
// -1 → error (fork failed)
 if (pid == 0) {
exec("/bin/ls", args); // Child replaces itself with new program
} else {
wait(&status); // Parent waits for child to finish
}

• Parent-Child relationship: Parent and child share (copy-on-write) memory initially. exec() replaces child's
memory with new program
• Process tree: init/systemd (PID 1) is ancestor of all processes on Linux
• Zombie process: Child has exited but parent hasn't called wait() yet — PCB remains, taking up process table
entry
• Orphan process: Parent exits before child — init process (PID 1) 'adopts' orphans, preventing zombies

2.4 Inter-Process Communication (IPC)

IPC Mechanism How It Works Advantages Disadvantages Best For
Shared Memory Processes map same physical Very fast — no kernel Requires explicit High-
memory region. One writes, involvement after synchronisation speed
other reads. OS sets it up then setup; high (semaphores/mute local
steps back bandwidth xes) to prevent commu
race conditions nication
;
produce
r-
consum
er
Message Passing send(msg) and receive(msg) No shared data — Slower — every Distribu
system calls. Kernel copies safe; works across message goes ted
message from sender to network; easier to through kernel; systems
receiver use correctly copy overhead ;
microke
rnel IPC;
network
commu
nication
Pipes Unidirectional byte stream. Simple; standard Unidirectional only; Shell
Ordinary pipe: requires UNIX idiom: ls | grep ordinary pipes pipeline
related processes (parent- need related s;
child). Named pipe (FIFO): any processes streami
processes ng data
betwee
n
related
process
es
Sockets Bidirectional communication Network-capable; full Higher overhead; Web
endpoint = IP address + port. duplex; widely more complex servers;
Works over network or locally supported programming distribut
ed
applicati
ons;
network
 IPC
Signals Asynchronous notification to a Lightweight; used for Limited data (just Process
process control signal number); control:
unreliable ordering SIGTER
M,
SIGKILL,
SIGCHL
D

2.5 Threads — Overview

A thread is the basic unit of CPU utilisation within a process. Multiple threads share one process's address space but
each has its own execution context.

Resource Process Thread

Address Space Own separate virtual address SHARED with other threads in
space same process
Code Section Own copy of program code SHARED — all threads execute
same program
Data Section Own global/static variables SHARED — race conditions
possible
Heap Own heap memory SHARED — concurrent allocation
issues
Stack Own stack PRIVATE — each thread has its
own stack and local variables
Registers/PC Own (saved in PCB) PRIVATE — own program counter
and register set (TCB)
Open Files Own file descriptor table SHARED — all threads can access
same open files
Creation Cost High — full address space copy Low — only TCB and stack needed
Context Switch Expensive — TLB flush, page table Cheap — same address space,
switch only register state

• TCB (Thread Control Block): Lightweight analog of PCB. Contains: Thread ID, PC, register set, stack pointer,
state, priority
• Benefits of Multithreading: (1) Responsiveness — UI stays active while background thread works; (2)
Resource sharing — threads share memory cheaply; (3) Economy — creating threads is 30× faster than
creating processes; (4) Scalability — threads can run in parallel on multiple CPU cores

2.6 Multithreading Models — CRITICAL for Q.1B

The relationship between user-level threads (managed by thread library) and kernel-level threads (managed by OS)
defines the model:

Model Mapping How It Works Advantage Disadvantage Real

Example
Many-to-One M user → 1 Thread library manages all Fast thread ONE blocking call Green
kernel threads entirely in user management — no blocks ALL Threads
space. Kernel sees only one kernel involvement threads. No (old Java,
thread. parallelism on Solaris
multicore — only 2.x)
1 kernel thread
ever runs
One-to-One 1 user → 1 Every user thread has a True parallelism on Overhead: Linux
kernel corresponding kernel multicore. Blocking creating user (pthreads
thread. Kernel manages one thread doesn't thread = creating ),
everything. block others. kernel thread. OS Windows
may limit max threads
threads.
Many-to-Many M user → N OS provides N kernel Flexibility: parallel Most complex IRIX, HP-
kernel (N ≤ M) threads; thread library + no kernel thread implementation UX, old
multiplexes M user threads limit Solaris
onto them.
Two-Level M:M + optional Like M:M but allows binding Best of all worlds Most complex Solaris 9
(hybrid) 1:1 important threads to and
dedicated kernel threads earlier

Q.1B ANSWER — Many-to-One Causes Slowdown

The Many-to-One model causes the video streaming server slowdown.

Root cause: In Many-to-One, ALL user-level threads of the server process map to a SINGLE kernel
thread. When a server thread handles a streaming request and makes a BLOCKING system call (e.g.,
reading video data from disk, writing to a network socket for a user), the ENTIRE PROCESS blocks —
every other connection thread is frozen, even if they have data ready to deliver.

Additionally, even on a multi-core server, only ONE kernel thread exists — no true parallel execution
possible. With hundreds of simultaneous users, connections queue up, latency spikes, and the server
appears slow.

Solution: Switch to One-to-One model (Linux pthreads / POSIX threads): each connection handler
thread gets its own kernel thread → parallel execution on multiple cores → one blocking I/O call doesn't
freeze other connections.

2.7 Thread Libraries

Library Platform Key Functions Implementation
POSIX Pthreads UNIX/Linux/macOS pthread_create(), pthread_join(), Can be user-level or
pthread_exit(), kernel-level (Linux
pthread_mutex_lock/unlock() uses kernel-level)
Win32 Threads Windows CreateThread(), Kernel-level — each
WaitForSingleObject(), thread is a kernel
CloseHandle(), CRITICAL_SECTION object
Java Threads JVM (all platforms) Thread class / Runnable interface; JVM maps to OS
start(), join(), sleep(), threads (One-to-One
synchronized keyword on modern JVMs)
2.8 Threading Issues — Deep Dive
Issue Description Problem Solution
fork() Semantics After fork() in UNIX provides two Use single-thread fork
multithreaded process: versions. Duplicating all then exec() — fork to
duplicate ALL threads or threads: some threads single-threaded child,
only calling thread? may be in inconsistent immediately exec() new
state. Duplicating only program
calling thread: other
threads' work is lost
exec() Semantics exec() replaces entire All threads are terminated Not a bug: intended
process address space — exec() replaces behaviour. Use fork()
everything +exec() pattern correctly
Signal Handling Where to deliver OS Signal may need to reach Synchronous signals
signals (SIGTERM, all threads or a specific (SIGSEGV) → to the thread
SIGSEGV, SIGUSR1) in a thread that caused it. Async
multithreaded process? signals (SIGTERM) → to
designated signal handler
thread or all threads. Use
pthread_sigmask()
Thread Cancellation Terminate a thread Asynchronous Deferred cancellation
before it completes its cancellation: immediate (preferred): thread checks
task kill → thread may hold pthread_testcancel() at
mutexes, have half-written defined safe cancellation
data → corruption. points. Thread cleans up
Resource leaks. (releases locks, flushes
buffers) before exiting.
Thread-Local Storage Multiple threads need Using a single global TLS allocates a separate
(TLS) thread-private versions variable → race conditions instance of the data for
of global data (e.g., when multiple threads each thread. Each thread
errno, transaction ID) write to it simultaneously reads/writes its own copy.
pthread_key_create(),
__thread keyword in C.
Scheduler Activations In M:M and Two-Level Without notification, Upcall mechanism: kernel
(LWPs) models, kernel needs to thread library cannot sends upcall to thread
notify thread library of redistribute work to library when a kernel
events (kernel thread available kernel threads thread blocks or becomes
blocking) available. Implemented via
LWPs (Lightweight
Processes) as the
communication channel.

Q: Q.1B: Identify which multithreading model causes the video streaming server slowdown.
What other threading issues could be responsible? Suggest solutions. [3 Marks]
MODEL ANSWER:
Part (i) — Model causing slowdown [1.5 marks]:
The Many-to-One multithreading model is the cause of the slowdown.
Justification: In this model, all user-level threads of the media server process are managed by a user-
space thread library and map to a SINGLE kernel thread. When any one server thread makes a blocking
system call — for example, waiting for network data from a slow user, or reading video content from
disk — the entire process is blocked at the kernel level. ALL other threads handling other users are also
frozen even if they have pending data to serve. Furthermore, even on a multi-core CPU, only one kernel
thread runs at a time, preventing genuine parallelism.
Fix: Migrate to One-to-One model (POSIX pthreads on Linux). Each connection thread has its own kernel
thread — blocking one does not affect others, and multiple cores are utilised simultaneously.

Part (ii) — Other threading issues and solutions [1.5 marks]:

1. Thread Cancellation: When a streaming user disconnects, the server must cancel their handler
thread. Asynchronous cancellation risks leaving video buffers partially written and mutexes locked —
corrupting shared state. Solution: Deferred cancellation — thread checks pthread_testcancel() at safe
points after completing each video chunk delivery, then cleans up resources before exiting.

2. Thread-Local Storage (TLS): Each connection thread needs its own session data — user ID, stream
position, bitrate selection. If stored in shared global variables, concurrent writes cause race conditions
(Thread A corrupts Thread B's stream position). Solution: Use TLS (pthread_key_create()) to give each
thread a private copy of session state.

3. Signal Handling: The server receives SIGTERM for graceful shutdown. In a multithreaded server,
which thread handles it? Solution: Designate one thread as signal handler (using pthread_sigmask() to
block signals in all other threads) — ensures orderly shutdown — streams finish, buffers flushed,
connections closed properly.
MODULE 3: Process Scheduling
Exam Questions from This Module: Q.3 — Non-Preemptive Priority Scheduling full numerical with Gantt Chart (6
marks)

3.1 Basic Concepts

CPU scheduling is the OS function that selects which ready process gets CPU time. The goal is to maximise CPU
utilisation by keeping the CPU busy, while meeting fairness and responsiveness goals.

• Preemptive scheduling: OS can take CPU away from a running process (all 4 state transitions trigger
scheduling decisions). Requires synchronisation mechanisms to protect shared data
• Non-preemptive scheduling: Once a process gets the CPU, it keeps it until it voluntarily releases (I/O wait or
termination). Only cases 1 and 4 trigger scheduling. Simpler but potentially unfair

CPU Burst Cycle

Processes alternate between CPU bursts (doing computation) and I/O bursts (waiting for I/O). The CPU
scheduler makes decisions at the boundaries of these bursts. Frequency distribution of CPU burst
lengths: many short bursts, few long bursts — this is why SJF works well in practice.

3.2 Scheduling Criteria — ALL 6

Criterion Definition Formula Optimise
CPU Utilization Percentage of time CPU is CPU Util = (Total CPU busy Maximize (target: 40–
executing useful work time / Total time) × 100% 90%)
Throughput Number of processes Throughput = # completed Maximize
completing per unit time processes / time period
Turnaround Time (TAT) Total time from process TAT = CT − AT Minimize
submission to completion
Waiting Time (WT) Total time process spends WT = TAT − BT OR WT = Minimize
waiting in ready queue CT − AT − BT
Response Time (RT) Time from submission to first RT = First CPU Start Time − Minimize
CPU response (first time on AT
CPU)
Completion Time (CT) Absolute clock time when CT = time at which process —
process finishes execution exits CPU for last time

3.3 FORMULA SHEET — All Scheduling Formulas

Turnaround Time TAT = CT − AT

Waiting Time WT = TAT − BT = CT − AT − BT

Response Time RT = First_CPU_Start − AT

Average TAT Avg TAT = Σ(all TAT) / n

Average WT Avg WT = Σ(all WT) / n

 Average RT Avg RT = Σ(all RT) / n

CT (FCFS/Non-preemptive) CT[P] = max(CT[prev], AT[P]) + BT[P]

SJF Burst Estimate τ(n+1) = α × t(n) + (1−α) × τ(n) [α = 0.5

typical]
RR Response Time RT[i] = (position_i − 1) × quantum

CPU Utilization Util = (1 − p^n) × 100% [p = I/O fraction, n

= processes]

3.4 Scheduling Algorithms — Deep Dive

A. FCFS — First Come First Served
Non-preemptive. Processes served in order of arrival. CPU given to first process in ready queue.
• Implementation: Simple FIFO queue
• Convoy Effect: One long process holds CPU; all short processes wait behind it — poor average WT
• Best for: Batch systems with uniform job lengths

FCFS Example — P1(AT=0,BT=24), P2(AT=0,BT=3), P3(AT=0,BT=3):

Gantt: | P1: 0−24 | P2: 24−27 | P3: 27−30 |
Avg WT = (0 + 24 + 27)/3 = 17ms ← Very high due to convoy effect

B. SJF — Shortest Job First

Selects process with shortest next CPU burst. Non-preemptive version: runs to completion. Preemptive version
(SRTF): preempts if new process has shorter remaining burst.
• PROVEN optimal for minimising average waiting time in non-preemptive category
• Starvation: Long processes may wait indefinitely if short ones keep arriving
• Problem: Cannot know next CPU burst — must ESTIMATE using exponential average

SJF on same example — P1(AT=0,BT=24), P2(AT=0,BT=3), P3(AT=0,BT=3):

Gantt: | P2: 0−3 | P3: 3−6 | P1: 6−30 |
Avg WT = (6 + 0 + 3)/3 = 3ms ← Much better!

C. Priority Scheduling
Assign each process a priority number. CPU goes to highest priority process.
• Internal priorities: Set by OS based on measurable quantities — time limits, memory requirements, CPU/IO
burst ratio, system parameters
• External priorities: Set outside OS — user or system administrator assigns based on importance
• Starvation: Low-priority processes may never run in heavy-load systems
• Aging: Gradually increase priority of waiting processes over time — prevents starvation
• Non-Preemptive Priority (Q.3 in sample paper): Once started, process runs until it voluntarily releases CPU

D. Round Robin (RR)

Each process gets a time quantum (time slice) q. After q, process is preempted and placed at END of ready queue.
 • Designed specifically for time-sharing systems — ensures response time
• If q → ∞: becomes FCFS. If q → 0: becomes processor sharing (each process gets 1/n of CPU)
• Rule of thumb: 80% of CPU bursts should be shorter than q
• Context switch overhead: if q is very small, most time spent context-switching
RR Example — P1(BT=24), P2(BT=3), P3(BT=3), q=4:
Gantt: |P1:0−4| P2:4−7 | P3:7−10 | P1:10−14 | P1:14−18 | P1:18−22 | P1:22−26 | (P1 CT=26)

Algorithm Preemptive? Optimal For Problem Use Case

FCFS No Nothing — simplest Convoy effect; high avg WT Batch, background
jobs
SJF No Avg WT (provably optimal for Starvation; burst time Batch with known
non-preemptive) unknown durations
SRTF Yes Avg WT (optimal for Starvation; frequent Interactive with short
preemptive) preemptions jobs
Priority Both Important jobs run first Starvation of low-priority — Real-time; critical
fix with aging systems
Round Robin Yes Response time; fairness Higher avg TAT than SJF Time-sharing;
interactive

3.5 FULLY SOLVED — Q.3 Sample Paper

Q.3: Non-Preemptive Priority Scheduling [Higher value = Higher Priority]
P1: AT=0, BT=8, Priority=2 | P2: AT=1, BT=4, Priority=1 [L=Lowest]
P3: AT=2, BT=9, Priority=3 [H=Highest] | P4: AT=3, BT=5, Priority=2

Step 1 — Decision at Each Time Point (Non-Preemptive: runs to completion once started)
• t=0: Only P1 available (others not yet arrived). P1 starts. P1 runs 0→8. CT(P1)=8
• t=8: P2(AT=1,P=1), P3(AT=2,P=3), P4(AT=3,P=2) ALL available. Highest priority=P3(3). P3 runs 8→17.
CT(P3)=17
• t=17: P4(P=2) and P2(P=1) remain. P4 higher. P4 runs 17→22. CT(P4)=22
• t=22: Only P2 left. P2 runs 22→26. CT(P2)=26

Step 2 — Gantt Chart (MANDATORY — marks deducted if missing)

┌──────────┬────────────────┬─────────┬────────┐
│ P1 │ P3 │ P4 │ P2 │
└──────────┴────────────────┴─────────┴────────┘
0 8 17 22 26

Step 3 — Calculate CT, TAT, WT, RT

Process AT BT Priorit CT TAT = CT−AT WT = TAT−BT RT = Start−AT
y
P1 0 8 2 8 8−0 = 8 8−8 = 0 0−0 = 0
P2 1 4 1 [L] 26 26−1 = 25 25−4 = 21 22−1 = 21
 P3 2 9 3 [H] 17 17−2 = 15 15−9 = 6 8−2 = 6
P4 3 5 2 22 22−3 = 19 19−5 = 14 17−3 = 14
AVERAGE − − − − (8+25+15+19)/4 (0+21+6+14)/4 = (0+21+6+14)/
= 16.75 10.25 4 = 10.25

Step 4 — Starvation Analysis

YES, starvation CAN occur in this system. P2 has the lowest priority (1). In a dynamic system where high-priority
processes continuously arrive before P2 gets CPU, P2 could be indefinitely postponed. In this specific instance, no
new arrivals occur after t=3, so P2 eventually runs at t=22. However, if a stream of priority-3 and priority-2 processes
kept arriving throughout, P2 would never execute — this IS starvation.
Solution: AGING — the OS periodically (e.g., every 15 minutes of waiting) increments a process's effective priority by
1. Eventually P2's effective priority would reach 3, guaranteeing it gets CPU.
MODULE 4: Process Synchronization
Exam Questions from This Module: Q.4A — Peterson's trace (3M) | Q.4B — Semaphores vs Monitors (3M) |
Q.5 — Dining Philosophers (6M)

4.1 The Critical-Section Problem

When multiple concurrent processes share data, a Race Condition can occur — the final outcome depends on the
unpredictable order of execution. The Critical-Section Problem seeks to design a protocol ensuring only one process
at a time accesses shared data.

Requirement Formal Definition Why It Matters

1. Mutual Exclusion If process Pi is executing in its critical Prevents corruption of
section, NO other process can be executing shared data
in their critical section simultaneously
2. Progress If no process is in its CS and some want to Prevents deadlock —
enter, only those NOT in their remainder the system must make
section participate in the decision about progress
who enters next. This selection cannot be
postponed indefinitely
3. Bounded Waiting There exists a bound B such that after a Prevents starvation —
process requests entry, at most B other every process
processes may enter before it. Its request eventually gets in
must eventually be granted

Critical section code structure:

do {
[ENTRY SECTION] // Request permission to enter
CRITICAL SECTION // Access shared data
[EXIT SECTION] // Signal that you're leaving
REMAINDER SECTION // Everything else
} while (true);

4.2 Peterson's Solution — Deep Dive

A classic software-only solution for 2-process mutual exclusion. Uses two shared variables:
• int turn: Indicates whose turn it is to enter the critical section (value: 0 or 1)
• boolean flag[2]: flag[i] = true means process Pi WANTS to enter the critical section

Code for Process Pi (the other process is Pj where j = 1-i):

flag[i] = true; // I want to enter
turn = j; // But I'll give priority to the other process
while (flag[j] && turn == j) // Busy-wait if other wants in AND it's their turn
; // spin
/* ===== CRITICAL SECTION ===== */
flag[i] = false; // I'm done — release

Why Peterson's Works — All 3 Requirements

 MUTUAL EXCLUSION: Both processes enter CS simultaneously only if: flag[0]=flag[1]=true AND turn=0
AND turn=1 simultaneously — impossible (turn has only one value). So at most one enters.

PROGRESS: If Pi wants to enter and Pj doesn't (flag[j]=false), Pi's while condition is false → Pi enters
immediately. No deadlock.

BOUNDED WAITING: If Pi is waiting and Pj is in CS, Pj will set flag[j]=false on exit. Then Pi's while
condition becomes false → Pi enters. Pi waits at most ONE complete CS execution of Pj.

Q.4A — PETERSON'S TRACE (Exact sample paper values)

Given: t=0ms: P1 sets flag[1]=true, turn=2. t=1ms: P2 sets flag[2]=true, turn=1.
Final state: flag[1]=TRUE, flag[2]=TRUE, turn=1 (P2 wrote last)

P1 checks while condition: (flag[2] && turn==2) → flag[2]=TRUE ✓ BUT turn=1 ≠ 2 → Condition FALSE
P1 EXITS the while loop → P1 ENTERS CRITICAL SECTION FIRST.

P2 checks while condition: (flag[1] && turn==1) → flag[1]=TRUE ✓ AND turn=1 ✓ → Condition TRUE
P2 BUSY-WAITS (spins in while loop).

KEY INSIGHT: P2 was the LAST to set 'turn' (turn=1 means 'it's P1's turn'). The last process to set turn
gives priority to the OTHER process. This is the elegant core of Peterson's algorithm.

When P1 exits CS: flag[1]=false → P2's while condition: flag[1]=FALSE → P2 enters CS.
Mutual exclusion ensured. Bounded waiting: P2 waits at most ONE CS execution of P1.

4.3 Synchronization Hardware

• TestAndSet (TAS): Atomically reads current value of lock AND sets it to true in one hardware operation.
Returns old value. If returned value was false → you got the lock. Spin otherwise
• CompareAndSwap (CAS): Atomically compare a memory location with expected value — if equal, swap in
new value. Foundation of lock-free data structures
• Memory Barriers (Fences): Hardware instruction that forces all preceding memory operations to complete
before any subsequent ones — prevents CPU reordering from breaking synchronisation

// TestAndSet lock implementation

while (TestAndSet(&lock)) // Spin until lock acquired
; // busy-wait
/* CRITICAL SECTION */
lock = false; // Release lock

4.4 Semaphores — Complete Coverage

A semaphore S is an integer synchronisation variable accessed ONLY through two atomic operations — wait() and
signal(). Dijkstra introduced them in 1965.

wait(S) { signal(S) {
S--; S++;
if (S < 0) { if (S <= 0) {
 block(); // add to wakeup(process); // remove
} // wait queue } // one from queue
} }

Semaphore Type Initial Value Usage Pattern Example

Binary Semaphore (Mutex) 1 Mutual exclusion — only Protecting a shared counter:
ONE process in CS at a time wait(mutex); counter++;
signal(mutex)
Counting Semaphore N (resource Control access to N Buffer with 5 slots: counting
count) identical resources semaphore initialized to 5
simultaneously

Semaphore Implementation Description Advantage Disadvantage

Busy-Waiting (Spinlock) Process spins in while loop No context switch Wastes CPU
checking semaphore overhead — fast for cycles while
SHORT waits on spinning — bad
MULTIPROCESSOR for long waits,
bad on single
processor
Blocking (Sleep-Lock) Process calls block() — No CPU waste while Context switch
removed from CPU, placed waiting — process overhead on
on semaphore's waiting sleeps entry and exit
queue. signal() calls
wakeup()

Producer-Consumer with semaphores (Bounded Buffer):

Semaphore mutex = 1; // Mutual exclusion for buffer
Semaphore empty = N; // Count of empty slots (init = buffer size N)
Semaphore full = 0; // Count of filled slots (init = 0)

Producer: Consumer:
wait(empty); // Need space wait(full); // Need item
wait(mutex); // Lock buffer wait(mutex); // Lock buffer
add_item(); remove_item();
signal(mutex); // Unlock signal(mutex); // Unlock
signal(full); // Item added signal(empty); // Space freed

4.5 Classic Synchronization Problems

Bounded Buffer (Producer-Consumer) — shown above

Readers-Writers Problem
Multiple readers can read shared data simultaneously. Writers need EXCLUSIVE access — no readers or writers while
writing.
Semaphore rw_mutex = 1; // Exclusive write access
Semaphore mutex = 1; // Protect read_count
int read_count = 0; // Number of active readers

READER: WRITER:
 wait(mutex); wait(rw_mutex);
read_count++; /* WRITE */
if (read_count==1) signal(rw_mutex);
wait(rw_mutex); // First reader locks
signal(mutex);
/* READ */
wait(mutex);
read_count--;
if (read_count==0)
signal(rw_mutex); // Last reader unlocks
signal(mutex);

• Reader priority: Writers may starve if readers keep arriving

• Writer priority variant: New readers blocked while writer is waiting — prevents writer starvation

4.6 Monitors
A monitor is a high-level synchronization construct — an abstract data type that bundles shared data with the
procedures that operate on it and AUTOMATICALLY ensures only one process is active inside the monitor at any
time.

monitor MonitorName {
// Shared variable declarations
int count = 0;
condition not_full; // Processes wait here
condition not_empty; // Processes wait here

procedure entry insert(item) {

if (count == N) not_full.wait();
/* add item */
count++;
not_empty.signal();
}
}

Feature Semaphore Monitor Winner

Abstraction Level Low-level — integer + 2 High-level language Monitor
atomic ops construct with compiler
support
Mutual Exclusion Programmer must call Automatic — Monitor
wait()/signal() correctly compiler/runtime enforces it
around every CS
Error Risk HIGH — one mistake LOW — structure makes Monitor
(missing signal, wrong order) mistakes nearly impossible
→ deadlock or violation
Condition Variables Must simulate with counting Built-in [Link]() and [Link]() Monitor
semaphores (complex) — cleaner
Flexibility More flexible — works across More structured — typically Semaphore
processes with named within one program
semaphores
 Debugging Hard — errors in semaphore Easier — structure is explicit Monitor
use are subtle and timing- and enforceable
dependent

4.7 Dining Philosophers — Full Solution for Q.5

Five philosophers sit around a circular table. Between each adjacent pair is ONE chopstick (5 chopsticks total). A
philosopher alternates between THINKING and EATING. To eat, needs BOTH left AND right chopstick.

The Deadlock Scenario

If all 5 philosophers simultaneously become hungry and each picks up their LEFT chopstick: each holds 1 chopstick
and waits for the right one (held by their neighbour) → CIRCULAR WAIT → DEADLOCK. All 4 deadlock conditions
present: Mutual Exclusion, Hold & Wait, No Preemption, Circular Wait.

Semaphore Solution + Code

semaphore chopstick[5] = {1, 1, 1, 1, 1}; // Each initialized to 1

void philosopher(int i) { // i = 0, 1, 2, 3, 4
while (true) {
think(); // Non-critical section
wait(chopstick[i]); // Pick up LEFT chopstick
wait(chopstick[(i+1) % 5]); // Pick up RIGHT chopstick
eat(); // Critical section
signal(chopstick[i]); // Put down LEFT
signal(chopstick[(i+1) % 5]); // Put down RIGHT
}
}

Problem: The above code has deadlock risk — if all 5 simultaneously execute wait(chopstick[i]), all are blocked.

Three Deadlock Prevention Solutions

• Solution 1 — Allow only N-1 at table: Add a room semaphore initialized to 4. wait(room) before picking
chopsticks, signal(room) after eating. At most 4 philosophers attempt to eat simultaneously — at least one
will always succeed
semaphore room = 4; // At most 4 allowed to try
wait(room); wait(left); wait(right); eat(); signal(right); signal(left);
signal(room);

• Solution 2 — Asymmetric (break circular wait): Even-numbered philosophers pick LEFT then RIGHT. Odd-
numbered philosophers pick RIGHT then LEFT. Circular wait is impossible
if (i % 2 == 0) { wait(chopstick[i]); wait(chopstick[(i+1)%5]); }
else { wait(chopstick[(i+1)%5]); wait(chopstick[i]); }

• Solution 3 — All or Nothing (Monitor): Philosopher picks up BOTH chopsticks atomically or waits. Eliminates
Hold & Wait condition

Q: Q.5: Describe the Dining Philosopher's problem with a neat diagram. Explain how it can be
solved using Semaphores. Provide relevant code snippets. [6 Marks]
MODEL ANSWER:
PROBLEM DESCRIPTION [2 marks]:
Five philosophers sit around a circular table. There is one chopstick between each adjacent pair of
philosophers — 5 chopsticks total. Each philosopher alternates between two activities: THINKING (no
resources needed) and EATING (needs BOTH left and right chopsticks). Since chopsticks are shared
between adjacent philosophers, concurrent access must be managed.

Diagram (draw in exam):

Phil 0
C4 C0
Phil 4 Phil 1
C3 C1
Phil 3 Phil 2
C2
(C0-C4 = chopsticks. Each Ci is shared between Phil i and Phil (i+1)%5)

DEADLOCK SCENARIO [1 mark]: If all 5 simultaneously pick up their LEFT chopstick, each holds 1 and
waits for the right (held by neighbour) → CIRCULAR WAIT → permanent deadlock. All 4 Coffman
conditions are satisfied: Mutual Exclusion (one at a time per chopstick), Hold & Wait (holding one,
waiting for another), No Preemption, Circular Wait.

SEMAPHORE SOLUTION + CODE [2 marks]:

semaphore chopstick[5] = {1,1,1,1,1}; // 1 = available

void philosopher(int i) {
while(true) {
think();
wait(chopstick[i]); // Pick up left
wait(chopstick[(i+1) % 5]); // Pick up right
eat();
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
}
}

DEADLOCK PREVENTION — N-1 Solution [1 mark]:

semaphore room = 4; // Only 4 can attempt simultaneously
void philosopher(int i) {
while(true) {
think();
wait(room); // Enter room (at most 4)
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
eat();
signal(chopstick[(i+1)%5]);
signal(chopstick[i]);
signal(room); // Leave room
}
}
With only 4 philosophers allowed to attempt simultaneously, at least one will always have both
chopsticks available. Deadlock eliminated.
MODULE 5: Deadlock Prevention, Avoidance & Detection
Exam Relevance: Conceptual questions likely. Banker's Algorithm is a high-priority numerical topic.

5.1 Deadlock Definition & System Model

Deadlock: A set of processes is in deadlock if each process in the set is waiting for an event that can ONLY be caused
by another process in the same set — forming a permanent, circular dependency.

• Resource types R1,R2,...,Rm (CPU, memory pages, I/O devices, semaphores, files)
• Each type Ri has Wi identical instances
• Process lifecycle with resources: Request → (wait if unavailable) → Use → Release

5.2 The 4 Necessary Conditions (Coffman Conditions) — ALL must hold

Condition Definition How to Eliminate It
1. Mutual Exclusion At least one resource held in non- Make resources sharable where
sharable mode — only one process at a possible (read-only files). Not
time can use it always possible.
2. Hold and Wait A process holding resources is waiting Require all resources requested at
to acquire additional resources held by once before starting. OR release
others all before requesting new ones.
3. No Preemption Resources cannot be forcibly taken Allow OS to preempt resources.
from a process — voluntarily released Only works for resources whose
only state can be saved/restored (CPU,
memory).
4. Circular Wait A set {P0,P1,...,Pn} where P0 waits for Impose total ordering on all
P1, P1 waits for P2,..., Pn waits for P0 resource types. Processes must
request in increasing order of
type.

5.3 Resource Allocation Graph (RAG)

• Process nodes: circles (Pi). Resource type nodes: squares (Ri). Dots inside resource squares = instances
• Request edge: Pi → Rj (process Pi is waiting for an instance of Rj)
• Assignment edge: Rj → Pi (one instance of Rj is assigned to Pi)

Graph Condition Deadlock?

No cycles in graph NO deadlock — guaranteed
Cycle AND each resource has exactly 1 instance DEADLOCK — guaranteed
Cycle AND some resource has multiple instances POSSIBLE deadlock — not certain, need detection
algorithm
5.4 Deadlock Prevention — Negating Each Condition
• Negate Mutual Exclusion: Make resources sharable. E.g., read-only files can be shared. Not applicable to
printers, tape drives, etc.
• Negate Hold & Wait: Require ALL resources at once before starting (low utilisation, starvation). OR release
all held resources before requesting more (practical but complex)
• Allow Preemption: OS preempts resources from waiting processes. Process state saved; resumes when all
resources available. Only works for resources with saveable state
• Negate Circular Wait: Assign numbers to resource types. Process must request in strictly increasing order. If
Pi holds Ri, can only request Rj where j > i

5.5 Deadlock Avoidance — Banker's Algorithm

Requires processes to declare maximum resource needs upfront. OS only allocates resources if resulting state is
SAFE.

Safe State Definition

A state is SAFE if there exists a SAFE SEQUENCE — an ordering of all processes such that for each Pi in
the sequence, resources Pi still needs can be satisfied by currently available resources PLUS resources
held by all Pj where j < i (processes before Pi in sequence).

Banker's: Need Need[i][j] = Max[i][j] − Allocation[i][j]

Banker's: Available Available[j] = Total[j] − Σ Allocation[i][j]

Safety Check Need[i] ≤ Available → Pi can finish →

Available += Allocation[i]

Banker's Algorithm Steps:

• Step 1: Calculate Need matrix = Max − Allocation for all processes
• Step 2: Find process Pi where Need[i] ≤ Available — this process CAN finish
• Step 3: When Pi finishes: Available += Allocation[i] (it releases all resources)
• Step 4: Mark Pi as finished. Repeat from Step 2 with updated Available
• Step 5: If all processes finish → SAFE state. If some cannot finish → UNSAFE state

5.6 Deadlock Detection & Recovery

• Single instance of each resource type: Use Wait-For Graph (WFG) — simplified RAG with only process nodes.
Pi → Pj if Pi waits for resource held by Pj. CYCLE = DEADLOCK
• Multiple instances: Use detection algorithm similar to Banker's. Run periodically or when CPU utilisation
drops (sign of deadlock)

Recovery Method How Advantage Disadvantage

Process Termination — Kill all deadlocked processes at Guaranteed to break Expensive — all
All once deadlock partial work lost
Process Termination — Kill one process, check if Less drastic Expensive —
One at a Time deadlock broken, repeat detection algorithm
 run each time; which
to kill?
Resource Preemption Forcibly take resources from Can be cheaper than Victim selection
some process and give to killing processes complex; starvation
others risk if same process
always preempted;
rollback required
MODULE 6: Memory Management
Exam Relevance: Paging address translation numericals very likely. Contiguous allocation fragmentation concepts
common.

6.1 Background — Key Concepts

• CPU can directly access ONLY main memory (RAM) and CPU registers — not disk
• Base register + Limit register: Hardware enforces memory protection. Every access checked: base ≤ address
< base+limit. Violation → segmentation fault
• Address Binding: When does a program's symbolic addresses become actual memory addresses?

Binding Time When? Flexibility Example

Compile Time Compiler generates absolute None — program must load at MS-
physical addresses same address always DOS .COM
files
Load Time Loader calculates physical Can load anywhere but address Old UNIX
addresses when loading into fixed after loading static
memory executable
s
Execution Time Addresses translated at Full flexibility — process can be Modern
runtime by MMU hardware moved while running OS with
virtual
memory

• Logical address (virtual address): Generated by CPU during program execution. What the program sees
• Physical address: Actual address in RAM hardware. What memory chips see
• MMU (Memory Management Unit): Hardware device that translates logical → physical addresses at runtime

6.2 Swapping
Temporarily move an entire process from memory to backing store (disk swap partition), then bring back later.
Allows more processes than memory can simultaneously hold.
• Standard swapping: Move entire process. Context switch time dramatically increases due to disk I/O
• Swapping with paging (lazy swapping): Modern OS only moves individual pages, not entire processes
• Swap space: Dedicated disk partition (Linux swap, Windows pagefile) for swapped pages

6.3 Contiguous Memory Allocation

Scheme How Internal External
Fragmentation Fragmentati
on
Fixed Partitioning Memory divided into fixed-size YES — process NO —
partitions at boot. One process per smaller than partitions are
partition partition fixed
wastes leftover
space within
partition
 Dynamic Partitioning OS creates variable-size partitions NO — no waste YES — free
exactly matching each process's size inside partition space
scattered in
small holes
that can't fit
new
processes

Allocation Strategy Algorithm When to Use

First Fit Scan from start, allocate FIRST hole that Fastest; fragments start of
is large enough memory
Best Fit Allocate SMALLEST hole that is large Minimises wasted space per
enough allocation; slow; creates many
tiny useless holes
Worst Fit Allocate LARGEST hole available Leaves largest remaining
holes; usually worst performer
overall

• Compaction: Move all processes to one end to consolidate free space. Only possible with execution-time
binding. EXPENSIVE — must copy all process data and update all addresses

6.4 Paging — Complete Coverage

Paging is the modern solution to external fragmentation. Physical memory divided into fixed-size FRAMES. Logical
memory divided into same-size PAGES. The OS maps any logical page to any physical frame.

Paging Term Definition

Page Fixed-size block of logical address space (typically 4KB–16MB). Pages
are numbered from 0.
Frame Fixed-size block of physical address space. Same size as a page. Frames
numbered from 0.
Page Table Per-process array mapping page numbers to frame numbers. Stored in
main memory.
Page Size Must be a power of 2 — this makes address division and modulo
trivially efficient (bit shifts)
Internal Fragmentation Average waste = page_size/2 per process (last page partially filled)

PAGING ADDRESS TRANSLATION — Must Know for Numericals

Logical address (p, d): p = page number, d = page offset
p = logical_address / page_size (integer division)
d = logical_address mod page_size
Physical address = frame_number × page_size + d
frame_number = page_table[p]

Example: Page size = 1KB = 1024 bytes. Logical address = 2500.

p = 2500 / 1024 = 2, d = 2500 mod 1024 = 452
 If page_table[2] = frame 3:
Physical address = 3 × 1024 + 452 = 3072 + 452 = 3524

TLB Effective Access Time EAT = h×(t_tlb + t_mem) + (1−h)×(t_tlb +

2×t_mem)

• TLB (Translation Lookaside Buffer): Hardware cache for recent page table entries. Hit ratio h=0.9−0.99 in
practice. On TLB hit: 1 memory access. On TLB miss: 2 memory accesses (page table + data)
• Multi-level paging: For large address spaces, page table itself is paged. 32-bit with 4KB pages → 1M entries ×
4 bytes = 4MB page table per process → too much. Two-level paging splits this
• Inverted Page Table: One entry per physical frame (not per page). Saves memory — one table for all
processes. But search time increases: must search table to find frame for given virtual page

6.5 Structure of the Page Table

Structure How Advantage Disadvantage
Single-Level One flat array indexed by page Simple Too large for big
number address spaces
(4MB for 32-bit
with 4KB pages)
Two-Level Outer page table points to inner Sparse allocation — Two memory
page tables. Only inner tables for most page table lookups per
used regions need exist in space not needed access (without
memory TLB)
Hashed Page Table Virtual page number hashed to Good for sparse Collision handling;
find entry in hash table address spaces (64- variable lookup
bit) time
Inverted Page Table One entry per physical frame One global table for Linear search for
containing (pid, virtual_page) ALL processes — virtual→physical;
huge memory saving must search
entire table

6.6 Segmentation
Segmentation matches the programmer's view of memory: a program is a collection of segments — each a logical
unit of different size (main program, functions, objects, stack, data, symbol table).
• Segment table: Per-process. Each entry has base (starting physical address) and limit (length) of segment
• Logical address: (segment number s, offset d). If d ≥ limit[s] → hardware trap (segmentation violation)
• Physical address = base[s] + d
• Benefits: Different protection per segment (code = read-only, stack = read-write). Segments can be shared
between processes (shared library segment). Logical units can grow independently
• Drawback: External fragmentation (variable-size segments, like dynamic partitioning)
MODULE 7: Virtual Memory
Exam Relevance: Page replacement algorithm numericals (FIFO/LRU/OPT) are very high probability.

7.1 Demand Paging

With demand paging, pages are loaded into memory ONLY when they are actually needed (demanded by a page
fault), not all at once when the process starts.

Step Action
1 Process references a virtual address → MMU checks page table
2 Valid bit = 0 (page not in memory) → MMU raises PAGE FAULT exception
3 OS page fault handler invoked → checks if reference is valid (is this address in
the process's legal space?)
4 Invalid reference? → terminate process. Valid but not in memory? → page it in
5 Find free frame. If none available → run page replacement algorithm to select
VICTIM frame
6 Read desired page from disk into the free/victim frame — this is SLOW
(milliseconds)
7 Update page table: set frame number, set valid bit = 1
8 Restart the instruction that caused the page fault

EAT with Page Faults EAT = (1−p) × ma + p × page_fault_service_time

Example: ma = 200ns, page fault service = 8ms = 8,000,000ns, p = 0.001 (1 fault per 1000 accesses)
EAT = 0.999 × 200 + 0.001 × 8,000,000 = 199.8 + 8000 = 8199.8ns ≈ 41× slowdown!
Key insight: Even a tiny page fault rate dramatically degrades performance — must keep p very small.

7.2 Page Replacement Algorithms

When no free frame is available, OS selects a VICTIM frame, writes it to disk (if dirty), and loads the needed page
into that frame.

Algorithm Selection Policy Belady's Implementation Optimality

Anomaly?
FIFO Replace page that has been in YES — more Simple queue — oldest Not optimal
memory for the LONGEST time frames can page is at front
(loaded earliest) cause MORE
faults
(counterintuitiv
e bug)
Optimal (OPT/MIN) Replace page that will NOT be NO Impossible to OPTIMAL —
used for the LONGEST time in implement — requires minimum
future future knowledge faults for any
algorithm
 LRU Replace page that was LEAST NO Counter method or Near-optimal
RECENTLY USED (longest since last stack method — in practice
reference) hardware support or
software overhead
LRU Approximation Reference bit: if 1, give second NO Hardware reference bits Good
(Clock/Second Chance) chance (clear bit, move on); if 0, + circular queue practical LRU
replace it approximatio
n

Worked Example — All Three Algorithms

Reference String: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 | 3 Frames

FIFO — Count Page Faults

Frames hold 3 pages. Replace oldest (first loaded) on fault.
7: [7,-,-] FAULT | 0: [7,0,-] FAULT | 1: [7,0,1] FAULT | 2: [2,0,1] FAULT (replace 7)
0: HIT | 3: [2,3,1] FAULT (replace 0) | 0: [2,3,0] FAULT (replace 1) | 4: [4,3,0] FAULT (replace 2)
2: [4,2,0] FAULT (replace 3) | 3: [3,2,0] FAULT (replace 4) | 0: HIT | 3: HIT | 2: HIT | 1: [1,2,0] FAULT
(replace 3)
Total FIFO Page Faults: 12 | Note: With 4 frames this string gets MORE faults — Belady's Anomaly!

LRU — Count Page Faults

Replace page least recently used — track when each page was last referenced.
7: FAULT | 0: FAULT | 1: FAULT | 2: FAULT (replace 7-LRU) | 0: HIT | 3: FAULT (replace 1-LRU)
0: HIT | 4: FAULT (replace 2-LRU) | 2: FAULT (replace 3-LRU) | 3: FAULT (replace 0-LRU) | 0: FAULT | ...
Total LRU Page Faults: ~9-10 — Better than FIFO, no Belady's Anomaly

7.3 Frame Allocation

Proportional Allocation frames(i) = (size_i / Σ sizes) × total_frames
• Equal Allocation: m frames among n processes → each gets m/n frames. Simple but unfair
• Proportional Allocation: Larger processes get more frames proportional to their size
• Priority Allocation: Higher priority processes get more frames
• Local replacement: Process can only replace from its OWN frames — predictable performance, isolated
• Global replacement: Process can take any frame from any other process — better throughput, less
predictable

7.4 Thrashing
Thrashing occurs when a process spends more time servicing page faults than executing useful instructions —
effectively stalling.

Thrashing Cycle: Process needs more frames than available → constant page faults → CPU utilisation drops → OS
scheduler adds more processes (thinks CPU is underloaded) → even fewer frames per process → even more faults
→ CPU utilisation approaches 0%.
• Working Set Model (Denning): The working set of a process is the set of pages it actively uses in the last Δ
time units (the working set window). If a process has its ENTIRE working set in memory, it runs efficiently
with few faults
Working Set Size WSS(i, t) = number of distinct pages
referenced in last Δ references of Pi
• Thrashing prevention: If Σ WSS > total available frames → suspend one process (reduce multiprogramming
level until Σ WSS ≤ available frames)
MODULE 8: File Systems
Exam Relevance: File allocation method comparisons common. NFS and Recovery are newer topics — understand
conceptually.

8.1 File System Structure

• File: Named collection of related information. OS's abstraction over raw disk blocks
• File system layers (bottom to top): I/O control (device drivers) → Basic file system (raw blocks) → File-
organisation module (maps blocks to files) → Logical file system (metadata, FCB, protection)
• FCB (File Control Block) / inode: Per-file OS data structure containing permissions, timestamps, owner, size,
data block pointers

Layer Responsibility
I/O Control Device drivers + interrupt handlers. Translates high-level commands to
low-level device commands
Basic File System Issues generic read/write block commands to appropriate device
driver. Manages memory buffers and caches
File-Organisation Module Knows about files AND their logical/physical blocks. Translates logical
block addresses to physical ones
Logical File System Manages metadata. Maintains directory structures. Protects files. Uses
FCB (inode).

8.2 File System Implementation

• On-disk structures: Boot control block (partition 0, block 0), Volume control block (superblock — partition
details, block count, free blocks), Directory structure (organises files), FCBs/inodes (per-file metadata + block
pointers)
• In-memory structures: Mount table (mounted partitions), Global open-file table (one entry per open file
system-wide), Per-process open-file table (file descriptors pointing to global table entries)
• open() creates in-memory structures and returns a file descriptor (integer index into per-process table)

8.3 Directory Implementation

Method How Advantage Disadvantag
e
Linear List Array/linked list of file names + Simple to program Linear search
pointers to FCBs O(n) — slow
for large
directories
Hash Table Hash file name to get index into O(1) average lookup Hash
directory structure — fast collisions
need
handling;
fixed size (or
rehashing
needed)
B+ Tree (modern) Balanced tree structure for directory O(log n) for all More
entries operations; ordered complex
listing implementati
on

8.4 File Allocation Methods

Method How Sequential Random External Internal Grow File
Access Access Frag Frag
Contiguous File occupies consecutive disk Excellent — Excellent — YES — No Difficult —
blocks. Directory entry: start read n start + offset holes must know
block + length consecutive directly created size upfront
blocks over time
Linked Each block has pointer to next. Good — Poor — must NO Pointer Easy — add
Directory entry: first block only follow traverse overhead block
pointers from start per block anywhere
Indexed One index block holds all Good Excellent — NO Index Easy within
pointers to data blocks (inode look up block index capacity
in UNIX has 12 direct + indirect) pointer wasted for
directly tiny files

• FAT (File Allocation Table) — MS-DOS/Windows: Linked allocation variant. Link info stored in separate FAT
table at start of volume, not in each data block. Faster traversal — entire FAT cached in memory
• UNIX inode: Indexed allocation. 12 direct pointers (for small files), 1 single indirect (points to block of
pointers), 1 double indirect, 1 triple indirect — supports files up to terabytes
UNIX Max File Size 12×BS + (BS/4)×BS + (BS/4)²×BS + (BS/4)³×BS
[BS = block size]

8.5 Free Space Management

Method How Advantage Disadvanta
ge
Bit Vector (Bitmap) One bit per block. bit=0: free, bit=1: Easy to find Must keep
allocated contiguous free entire
blocks; simple bitmap in
memory for
efficiency
Linked Free List Link all free blocks together — store No space wasted for Hard to find
pointer to next free block in each bitmap contiguous
free block blocks; I/O
to traverse
list
Grouping First free block stores n addresses of Quickly find large More
free blocks; last of those points to numbers of free complex
next group blocks than simple
linked list
Counting Pair: (first_free_block_address, Efficient when free Overhead
count_of_consecutive_free_blocks) space tends to be of
 contiguous (after maintaining
large deletes) counts

8.6 Efficiency and Performance

• Buffer Cache / Unified Buffer Cache: Keep recently accessed disk blocks in memory. Read hits avoid disk I/O
entirely. Write-back vs write-through policies
• Read-Ahead: OS predicts sequential access pattern and prefetches next blocks before requested — hides
latency
• Free-behind: Free buffer of current block once next block arrives — for sequential streams that won't re-
read
• Synchronous vs Asynchronous I/O: Synchronous blocks process until I/O completes. Asynchronous: process
continues; OS signals when done — better performance
• Page Cache: Unified cache for file data AND virtual memory pages in modern OS — avoids double caching

8.7 Recovery
File system can become inconsistent if system crashes during a write operation — partially written metadata leaves
file system in a corrupted state.

• Consistency Checking: fsck (UNIX) / chkdsk (Windows) — scan entire file system at boot to find and repair
inconsistencies. SLOW — may scan entire disk
• Log-Structured File Systems (LFS): Write ALL changes sequentially to a log first. Log is truth — replay log to
recover. Very fast writes (sequential); reads may need reconstruction
• Journaling File Systems (ext3, ext4, NTFS, HFS+): Write-Ahead Logging (WAL). Log the INTENT before making
changes. On crash, replay the log. Only log needs scanning on recovery — fast

Recovery Method How Recovery Speed Write

Performance
No journaling Changes written directly to disk SLOW — full fsck Fast writes —
scan on crash no logging
overhead
Journaled Metadata Only Log metadata changes only; FAST — only log Moderate
data written directly replayed overhead
Full Journaling Log both metadata AND data FAST Highest
changes overhead —
write data
twice

8.8 NFS — Network File System

NFS (developed by Sun Microsystems, now open standard) allows a computer to access files over a network as if
they were on local disk. It is a key technology for distributed computing.

NFS Concept Explanation

Mounting NFS client mounts a remote directory exported by NFS server. After
 mounting, remote files appear in local directory tree — transparent to
applications
Stateless Protocol NFS server keeps no state about clients — each request is self-
contained. Simplifies crash recovery: if server crashes and restarts,
clients just retry
RPC (Remote Procedure Call) NFS operations (read, write, lookup) are implemented as RPCs —
network calls that look like local function calls to the client
Caching Clients cache file data and attributes locally to reduce network traffic.
Cache consistency protocol needed to handle multiple clients
modifying same file
Exports Server specifies which directories it 'exports' (makes available).
/etc/exports on Linux defines exported directories and access
permissions per client
Versions NFSv3: stateless, UDP-based. NFSv4: stateful, TCP-based, built-in
security (Kerberos), better WAN performance. Most modern Linux uses
NFSv4

NFS Advantage and Challenge

ADVANTAGE: Centralised file storage accessible from any workstation on the network. One backup
covers all users. Home directories available from any machine.
CHALLENGE: Network latency makes NFS slower than local disk. Cache consistency — if two clients
write the same file simultaneously, who wins? NFS uses a 'close-to-open consistency' model: changes
are flushed when file is closed.
COMPLETE SAMPLE PAPER SOLUTIONS
BSDCBZC364 | Operating Systems | 15-03-2026 | 5 Questions | 30 Marks | 2 Hours

Q.1A + Q.1B — See Module 1 & Module 2 model answers above

Q.1A model answer is in Module 1 (system calls — why needed + 2 types). Q.1B model answer is in
Module 2 (Many-to-One slowdown + 3 threading issues).

Q.2 — See Module 1 model answer above

Q.2 asks for Monolithic, Layered, Microkernel with diagrams + advantages/disadvantages. Full answer
with ASCII diagrams in Module 1.

Q.3 — See Module 3 fully solved section above

Complete Gantt Chart + CT/TAT/WT/RT table + Starvation analysis all in Module 3.

Q.4A — See Module 4 Peterson's trace box above

Exact values from paper traced through. P1 enters first. Complete mutual exclusion explanation.

Q.4B — Semaphores vs Monitors model answer

See the detailed table comparison in Module 4 Section 4.6.

Q.5 — See Module 4 Dining Philosophers qbox above

Full Q.5 model answer with diagram, code, and deadlock prevention solution in Module 4 Section 4.7.
LAST-MINUTE REVISION SHEET

TOP 10 CANNOT-MISS TOPICS

1. Process Scheduling numericals — all 4 algorithms + Gantt chart + CT/TAT/WT/RT formulas
2. Peterson's Algorithm — know the code + trace through any example
3. Semaphores — wait()/signal() code + Producer-Consumer full code
4. Dining Philosophers — diagram + semaphore code + N-1 fix
5. OS Structures — Monolithic/Layered/Microkernel with ASCII diagrams
6. System Calls — why needed (dual mode) + 6 categories
7. Multithreading Models — Many-to-One vs One-to-One (Q.1B pattern)
8. Paging — address translation formula + worked numerical
9. Page Replacement — FIFO/LRU/OPT with reference string example
10. Deadlock — 4 conditions + Banker's algorithm steps

ALL FORMULAS — 10-Day Final Reference

TAT CT − AT

WT TAT − BT = CT − AT − BT

RT First_CPU_Start − AT

Avg TAT/WT/RT Sum_of_values / n

CT (FCFS/Non-preemptive) max(CT_prev, AT) + BT

SJF Burst Estimate τ(n+1) = α×t(n) + (1−α)×τ(n)

Banker's Need Max − Allocation

Banker's Available Total − Σ(Allocation)

Paging: Page Number logical_address / page_size (integer ÷)

Paging: Offset logical_address mod page_size

Physical Address frame_number × page_size + offset

TLB EAT h×(t_tlb+t_mem) + (1−h)×(t_tlb+2×t_mem)

EAT with Page Faults (1−p)×ma + p×page_fault_time

Proportional Frames (size_i / Σ sizes) × total_frames

CPU Utilization (1 − p^n) × 100%

UNIX Max File (4KB block) (12 + 1024 + 1024² + 1024³) × 4KB

QUICK KEY-WORD DEFINITIONS

Term One-Line Definition
Process Program in execution — active entity with its own PCB, address space,
 and allocated resources
Thread Lightweight process — shares address space with siblings; own stack,
PC, and registers only
PCB Per-process OS data structure holding all state needed to manage and
resume that process
Context Switch Save current process state to PCB, load next process state from PCB —
pure overhead
Critical Section Code accessing shared data — must be executed by only one process
at a time
Race Condition Multiple processes access shared data concurrently; outcome depends
on execution order
Deadlock Set of processes permanently waiting, each for a resource held by
another in the set
Starvation Process waits indefinitely for resource — not deadlocked, but never
scheduled
Aging Gradually increase priority of waiting processes — prevents starvation
Semaphore Integer sync variable with atomic wait() and signal() — the mutex
primitive
Monitor High-level sync construct — compiler enforces mutual exclusion
automatically
Thrashing Process spends more time paging than executing — insufficient frames
allocated
Working Set Set of pages a process actively references in a recent time window Δ
TLB Fast hardware cache for recent page table entries — reduces memory
access overhead
Demand Paging Page loaded into memory only on first reference (page fault) — not at
process start
Fragmentation Internal: waste inside allocated block. External: free space too
scattered to use
DMA Device controller transfers data directly to/from memory without CPU
intervention
Dual Mode Hardware enforces user mode (restricted) and kernel mode
(privileged) — protects OS
System Call Controlled interface for user programs to request OS kernel services —
mode switch mechanism
NFS Network File System — access remote files transparently over network
as if they were local

10-DAY STUDY PLAN

Day Focus Area What To Do
Day 1 Module 1: OS Intro + System Calls Read notes. Memorise dual-mode concept. Practice Q.1A
answer. Draw all 3 OS structure diagrams.
Day 2 Module 1: Q.2 OS Structures Write out full Q.2 answer from memory. Practice ASCII
 diagrams for all 3 structures.
Day 3 Module 2: Processes + Threads Read PCB table. Memorise multithreading models. Practice
Q.1B in full including 3 threading issues.
Day 4 Module 3: Scheduling Theory Understand all 5 algorithms. Learn all formulas. Do FCFS and
SJF examples.
Day 5 Module 3: Scheduling Numericals Solve Q.3 from sample paper independently. Then solve 2
new Priority and RR examples.
Day 6 Module 4: Synchronization Part 1 Peterson's code + trace. TAS hardware. Semaphore code
patterns. Producer-Consumer.
Day 7 Module 4: Synchronization Part 2 Readers-Writers. Monitors vs Semaphores table. Full Dining
Philosophers Q.5 answer.
Day 8 Modules 5 + 6: Deadlock + Memory Banker's algorithm example. Paging address translation
numericals.
Day 9 Modules 7 + 8: Virtual Memory + FS Page replacement FIFO/LRU/OPT examples. File allocation
methods comparison. NFS overview.
Day 10 Full Paper Simulation Write complete answers to all 5 questions under exam
conditions — 2 hours, closed book.

ALL THE BEST — You've got this!

Every answer: fresh page | Gantt chart mandatory for scheduling | Code for every semaphore/monitor question