OPERATING

Complete Exam Notes SYSTEMS

— All 7 Chapters
COMSATS University Islamabad, Lahore Campus
Course: CSC 322/323 — Principles of Operating Systems

Reference: Operating System Concepts, 10th Edition

Silberschatz, Galvin & Gagne ("The Dinosaur Book")

Chapter Topic Exam Weight

Ch 1 OS Introduction & Concepts Medium

Ch 2 OS Services & Structure High

Ch 3 Processes Very High

Ch 4 Threads & Concurrency High

Ch 5 CPU Scheduling Very High

Ch 6 Synchronization Tools Very High

Ch 7 Synchronization Examples High

Legend: Orange boxes = exam focus | Green boxes = analogies | Blue boxes = important notes | Purple text = book reference
 Chapter 1: Introduction to Operating Systems

1.1 What is an Operating System?

An Operating System (OS) is a program that acts as an intermediary between the user and the computer
hardware. It manages hardware resources and provides services for application programs.

ANALOGY: Think of the OS like a restaurant manager. The kitchen (hardware) does the actual cooking.
The customers (user/apps) place orders. The manager (OS) coordinates everything — takes orders, assigns
cooks, serves food — so the customer never directly touches the stove.
[Dinosaur Book Ref] Chapter 1, Section 1.1 — "An OS is a program that manages computer hardware."

Goals of an OS:
• Execute user programs and solve user problems
• Make the computer system convenient to use
• Use hardware in an efficient manner

1.2 Computer System Structure

A computer system has four main components:

Component Description Examples

Hardware Physical computing resources CPU, RAM, I/O devices

Operating System Controls & coordinates hardware use Windows, Linux, macOS

Application ProgramsDefine how resources are used to solve user problemsWord, Chrome, Games

Users People, machines, or other computers You, servers, IoT

[Dinosaur Book Ref] Figure 1.1, Chapter 1 — "Abstract View of Computer System Components"

1.3 Computer-System Organization

Modern computers use a common bus that connects CPUs, device controllers, and shared memory. All of
these can execute concurrently.
• Each I/O device has its own device controller (e.g., disk controller, USB controller)
• Each device controller has a small local buffer — a temporary data store
• CPU moves data between main memory and these local buffers
• When a controller finishes an operation, it sends an interrupt to notify the CPU

1.4 Interrupts — VERY IMPORTANT

EXAM FOCUS: What is an interrupt? What are its types? How is it handled? — asked every year!
An interrupt is a signal sent to the CPU that something needs immediate attention. The CPU stops what it is
doing, saves its state, and handles the interrupt.

ANALOGY: Imagine you are studying (CPU doing work). Your phone rings (interrupt). You save your place in
the book (save CPU state), answer the call (handle interrupt), then return to studying (resume work). That's
exactly what the OS does!

Types of Interrupts:
Type Cause Example

Hardware Interrupt A device signals the CPU Keyboard press, disk read done
 Software Interrupt
Generated by software or errors Division by zero, system call
(Trap/Exception)

How Interrupt Handling Works (Step by Step):

• Step 1: Device or software generates an interrupt signal
• Step 2: CPU finishes its current instruction
• Step 3: CPU saves the current state (registers, program counter) into memory
• Step 4: CPU looks up the Interrupt Vector Table to find the handler address
• Step 5: CPU jumps to the Interrupt Service Routine (ISR) and executes it
• Step 6: CPU restores saved state and resumes normal work
[Dinosaur Book Ref] Section 1.2.1 — "Interrupts are used by hardware to notify the OS of events"

1.5 Storage Structure & Hierarchy

Storage is organized in a hierarchy based on speed, cost, and volatility:

FASTEST (most expensive, smallest) SLOWEST (cheapest, largest)

■■■■■■■■■■■■■■
■ Registers ■ ← inside CPU, super fast
■■■■■■■■■■■■■■
■ Cache ■ ← L1/L2/L3, near CPU
■■■■■■■■■■■■■■
■ Main Memory■ ← RAM (volatile — loses data on power off)
■■■■■■■■■■■■■■
■ SSD ■ ← Non-volatile, fast secondary storage
■■■■■■■■■■■■■■
■ HDD ■ ← Non-volatile, slow magnetic disk
■■■■■■■■■■■■■■
■Optical/Tape■ ← Slowest, cheapest, for backup
■■■■■■■■■■■■■■
NOTE: Volatile = loses data when power is off (e.g., RAM). Non-volatile = keeps data (e.g., HDD, SSD).
[Dinosaur Book Ref] Section 1.3.1 — Storage-Device Hierarchy

Caching:
Caching = copying data from slow storage into faster storage temporarily. The CPU checks cache first; if data is
there (cache hit), great. If not (cache miss), it fetches from slower storage and stores in cache.

ANALOGY: Caching is like keeping your most-used books on your desk (cache = desk, library = main
memory). You grab from the desk first — much faster!

1.6 Direct Memory Access (DMA)

For high-speed I/O, the DMA controller transfers blocks of data directly between device and main memory —
without CPU involvement. Only one interrupt per block (not one per byte), greatly reducing CPU overhead.

ANALOGY: DMA is like hiring a moving company (DMA) to move furniture (data) directly from store to house
(memory). The owner (CPU) doesn't carry each piece — just gets one call when the job is done.

1.7 Operating System Operations

Bootstrap Program:
• First program that runs when computer is powered on
• Stored in ROM/EPROM (firmware)
• Initializes hardware, loads OS kernel into memory, starts execution
1.8 Multiprogramming vs Multitasking (Timesharing)
EXAM FOCUS: How does multiprogramming improve CPU utilization? — Asked in FALL 2025
Midterm!

Feature Multiprogramming Multitasking (Timesharing)

Keep CPU busy by switching to CPU switches SO fast users can

Core Idea
another job when one waits for I/O interact with all programs simultaneously

Goal Maximize CPU utilization Minimize response time

Interaction No user interaction during execution Users interact in real time

Response Time Not a concern Must be < 1 second

Example Batch processing systems Modern desktop OS (Windows, Linux)

How Multiprogramming Improves CPU Utilization:

Without multiprogramming, when one program waits for I/O (e.g., reading a file), the CPU sits idle. This is
wasteful.

• With multiprogramming, a subset of jobs is kept in memory

• When Job A waits for I/O, the OS switches to Job B
• CPU is always doing something useful — utilization goes up from ~20% to ~90%+
Without Multiprogramming: Job A [====I/O wait====] Job A [====I/O wait====]
CPU IDLE !!!!

With Multiprogramming: Job A [===] Job B [===] Job A [===] Job C [===]
CPU NEVER IDLE!
[Dinosaur Book Ref] Section 1.4.1 — "Multiprogramming increases CPU utilization"

1.9 Dual-Mode Operation: User Mode vs Kernel Mode

EXAM FOCUS: Define User Mode and Kernel Mode. What is the difference? — asked in Fall 2022 &
Spring 2024!

Feature User Mode Kernel Mode

Who runs in it? User applications (Word, Chrome) Operating System itself

Mode bit value 1 (user) 0 (kernel)

Privileges Limited — cannot access hardware directly

Full — can execute ANY instruction

Privileged Instructions? NOT allowed Allowed

Example Running a game OS handling a disk read

NOTE: The mode bit is a single hardware bit. When 0 = kernel mode, when 1 = user mode. The hardware
enforces this — user programs physically cannot execute privileged instructions.

Why do we need two modes?

• Protection: Prevents user programs from crashing the OS or accessing others' memory
• If user code could run in kernel mode, a buggy app could crash the entire system
• System calls switch from user mode → kernel mode → user mode

User Program OS Kernel

■■■■■■■■■■ ■■■■■■■■■
[User Mode] [Kernel Mode]
printf("hello")
■
▼ System Call (write())
 mode bit → 0 (kernel) ■■■■■■ OS handles I/O
■
mode bit → 1 (user) ■■■■■■■■return to user
[Dinosaur Book Ref] Section 1.4.2 — Dual-Mode Operation

1.10 Timer
The OS uses a hardware timer to prevent any single process from hogging the CPU forever.

• Timer is set before a process runs (e.g., 10 milliseconds)

• Timer counts down; when it reaches zero, it generates an interrupt
• OS regains control and can switch to another process
ANALOGY: A timer is like an egg timer at a debate. Each speaker gets 2 minutes. When the timer rings, the
moderator (OS) stops the current speaker and lets the next one talk.

1.11 Resource Management Summary

Resource Type Examples OS Responsibility

Hardware Resources CPU, RAM, I/O devices, Disk Allocate & schedule efficiently

Software Resources Files, Processes, Semaphores, Locks Manage access & synchronization

EXAM FOCUS: Name two hardware resources and two software resources — asked in FALL 2024
Midterm!
• Hardware: CPU, Main Memory (RAM), I/O devices (keyboard, disk)
• Software: Files, Processes, Semaphores, Message queues

1.12 Computing Environments

Environment Key Feature

Traditional Stand-alone PC, now mostly connected to internet

Mobile Smartphones/tablets — GPS, touch, battery-constrained

Client-Server Clients request; servers respond (e.g., web servers)

Peer-to-Peer (P2P) All nodes are equal — both client and server (e.g., BitTorrent)

Cloud Computing Virtualized resources over internet (IaaS, PaaS, SaaS)

Real-Time Embedded Strict timing requirements (e.g., pacemaker, car airbag)

1.13 Virtualization
Virtualization allows one physical computer to run multiple OS instances simultaneously. A Virtual Machine
Monitor (VMM) or Hypervisor manages this.

ANALOGY: Virtualization is like building apartments (virtual machines) inside one big building (physical
hardware). Each apartment thinks it has its own kitchen and bathroom, but they're sharing the building's real
plumbing.
• Benefits: Run multiple OSes, testing, isolation, server consolidation
• Examples: VMware, VirtualBox, Hyper-V
[Dinosaur Book Ref] Section 1.7 — Virtualization
 Chapter 2: Operating-System Services & Structure

2.1 OS Services
The OS provides services both for users and for the system itself:

Service Description

User Interface (UI) CLI (command line), GUI (graphical), or touch

Program Execution Load & run programs; handle normal/abnormal termination

I/O Operations Provide access to files and I/O devices

File-System Manipulation Create, delete, read, write, search files & directories

Communications Between processes (shared memory or message passing)

Error Detection Detect and recover from CPU, memory, I/O errors

Resource Allocation Allocate CPU, memory, I/O to multiple users/jobs

Logging Track which users use which resources

Protection & Security Control access; authenticate users

[Dinosaur Book Ref] Section 2.1 — OS Services

2.2 System Calls — VERY IMPORTANT

EXAM FOCUS: What is a system call? What are the 3 methods to pass parameters? — asked in Fall
2022 Midterm (both sections)!

A system call is the programming interface between a user program and the OS kernel. It is how user
programs request services from the OS.

ANALOGY: A system call is like a waiter in a restaurant. You (user program) cannot go into the kitchen
(kernel) yourself. You tell the waiter (system call) what you want, and they bring it to you. The waiter is the
only one allowed in the kitchen.

How a System Call Works:

1. User program calls a library function (e.g., printf)
2. Library function invokes the system call (e.g., write)
3. Mode bit switches: User Mode → Kernel Mode
4. OS executes the requested service
5. Mode bit switches back: Kernel Mode → User Mode
6. Control returns to the user program
[Dinosaur Book Ref] Section 2.3 — System Calls

3 Methods to Pass Parameters to the OS:

EXAM FOCUS: These 3 methods are directly asked — memorize them!

Method How it Works Limitation

1. Registers
Parameters placed directly in CPU registers before
Limited
system
by number
call of registers (usually ~6-8)

2. Block/Table
Parameters
in Memory
stored in a memory block; address of block placed
None
in a—
register
used by Linux & Solaris

3. Stack
Parameters pushed onto program stack by user; OSNone
pops—them
flexible
off for any number of params

NOTE: Methods 2 (block) and 3 (stack) do NOT limit the number or length of parameters. Method 1 (registers) is
simplest but limited.
[Dinosaur Book Ref] Section 2.3.1 — Parameter Passing
Types of System Calls:
• Process Control: create process, terminate process, wait, allocate memory
• File Management: create/delete file, open/close, read/write
• Device Management: request/release device, read/write device
• Information Maintenance: get/set time, get system data
• Communications: create connection, send/receive messages
• Protection: get/set permissions, control access

2.3 How a Normal User Program Executes a System Call

EXAM FOCUS: Using an example, explain how a normal user program executes a system call —
Spring 2024!

Example: printf("Hello") in a C program

User Space: Kernel Space:

■■■■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■
printf("Hello")
■ calls
▼
C Library (libc)
→ prepares args
→ executes INT instruction ■■■■■■■ write() system call handler
(software interrupt) → writes to screen buffer
■■■■■■■■■■ → returns status
→ continues execution

2.4 OS Design Structures

EXAM FOCUS: Layered approach — advantage and disadvantage — asked in FALL 2025 Midterm!

1. Simple/Monolithic Structure (e.g., original UNIX, MS-DOS):

All OS functionality in one large kernel. Everything runs in kernel mode together.

• Advantage: Very fast — no layer overhead, direct function calls

• Disadvantage: Hard to maintain, debug, or modify — a bug anywhere can crash everything
ANALOGY: Like a giant Swiss Army knife — everything in one tool, efficient but messy.

2. Layered Approach:
OS divided into layers. Layer 0 = hardware. Layer N = user interface. Each layer uses services only from the
layer directly below it.
Layer N ■ User Interface
Layer N-1 ■ I/O Management
Layer N-2 ■ Process/Memory Management
... ■ ...
Layer 1 ■ Hardware Abstraction
Layer 0 ■ HARDWARE

• Advantage: Easy to debug and verify — each layer can be tested independently
• Advantage: Simple design — each layer only interacts with adjacent layers
• Disadvantage: Performance overhead — requests must pass through many layers
• Disadvantage: Difficult to define layer boundaries cleanly
[Dinosaur Book Ref] Section 2.7.2 — Layered Approach

3. Microkernel (e.g., Mach):

Only essential functions in the kernel (memory management, IPC, basic scheduling). Everything else (file
system, device drivers) runs in user space.

• Advantage: More secure and reliable — less code in kernel mode

• Advantage: Easier to extend and port to new hardware
• Disadvantage: Slower — communication between user-space modules through kernel takes time

4. Hybrid (e.g., modern Linux, Windows, macOS):

Combines multiple approaches. Linux = monolithic + modular (loadable kernel modules). Windows = mostly
monolithic + microkernel elements.

Structure Key Idea Pro Con

Monolithic All in one kernel Fast Hard to maintain

Layered Layers, each uses layer below Easy to debug Slow, hard to define layers

Microkernel Minimal kernel, rest in user space Secure, reliable Performance overhead

Hybrid Mix of above Best of all Complex

2.5 Virtual Machines

EXAM FOCUS: What is a virtual machine and what are its benefits? Give an example — Spring 2024,
Spring 2023!

A Virtual Machine (VM) is a software emulation of a physical computer. It lets you run a guest OS inside a host
OS. The VMM (Virtual Machine Monitor / Hypervisor) manages this.

ANALOGY: A VM is like a TV show set. It looks like a real office/kitchen/hospital (guest OS), but it's all built
inside a studio (host OS). The director (VMM) controls everything.

Benefits of Virtual Machines:

• Run multiple OSes on one physical machine simultaneously
• Isolation: A crash in the guest VM does not affect the host or other VMs
• Testing & development: Test software on different OSes without extra hardware
• Security: Malware in a VM is contained
• Server consolidation: One powerful server runs many VMs — saves cost
• Example: VirtualBox running Ubuntu Linux inside a Windows 11 host
[Dinosaur Book Ref] Section 18.1 — Virtual Machines
 Chapter 3: Processes

3.1 What is a Process?

A process is a program in execution. A program is just a passive file on disk; a process is active — it has
resources allocated to it and is being executed by the CPU.

ANALOGY: A recipe (program) sitting in a cookbook is passive. When a chef (CPU) follows that recipe to
cook a meal (process), it becomes active. Multiple chefs can follow the same recipe simultaneously — just
like multiple processes can run from one program.
[Dinosaur Book Ref] Section 3.1 — Process Concept

Parts of a Process in Memory:

■■■■■■■■■■■■■■■■■■■■ ← High address
■ Stack ■ ← Function calls, local variables, return addresses
■ ↓ ↑ ■ (grows downward)
■ (free space) ■
■ ↑ ↓ ■ (grows upward)
■ Heap ■ ← Dynamically allocated memory (malloc)
■■■■■■■■■■■■■■■■■■■■
■ Data Section ■ ← Global & static variables
■■■■■■■■■■■■■■■■■■■■
■ Text Section ■ ← Program code (instructions)
■■■■■■■■■■■■■■■■■■■■ ← Low address

3.2 Process Control Block (PCB)

Each process is represented in the OS by a PCB (Process Control Block) — a data structure that contains all
information about a process.

PCB Field What it Stores

Process State New, Ready, Running, Waiting, or Terminated

Program Counter Address of next instruction to execute

CPU Registers All CPU registers (saved during context switch)

CPU Scheduling Info Priority, scheduling queue pointers

Memory Management Info Base/limit registers, page tables

Accounting Info CPU time used, total time, job/process numbers

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

ANALOGY: The PCB is like your student file at university. It has your name, ID, grades, courses, outstanding
fees — everything about you. The admin (OS) checks your file whenever they need to deal with you (your
process).

3.3 Process States — VERY IMPORTANT

EXAM FOCUS: Draw the 5-state transition diagram WITH labels — asked in EVERY midterm paper!

A process moves through 5 states during its lifetime:

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■■■■■■
■ 5-STATE PROCESS MODEL ■
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■■■■■■
 ■■■■■■■ admitted ■■■■■■■■■ scheduler ■■■■■■■■■■■
■ NEW ■ ■■■■■■■■■■■ ■ READY ■ ■■dispatch■■■ ■ RUNNING ■ ■■■■ exit ■■■■■ TERM
INATED
■■■■■■■ ■■■■■■■■■ ■■■■■■■■■■■
▲ ■
■ interrupt/ ■ I/O or event
■ time quantum ■ wait
■ expires ▼
■ ■■■■■■■■■■■
■■■■■■■■■■■■■■■■■■■■ ■ WAITING ■
I/O complete ■■■■■■■■■■■
event occurs

State Description Trigger to enter

New Process is being created Program launched

Ready Waiting to be assigned to CPU Admitted from New, or I/O complete

Running CPU is executing this process Scheduler dispatches it

Waiting Waiting for I/O or an event to complete Process requests I/O

Terminated Process has finished execution exit() call or error

State Transition Table (asked in FALL 2023 & FALL 2024 Midterms!):
EXAM FOCUS: Given an event, identify starting state and ending state — appears as a table
question!

Event Starting State Ending State

I/O complete (event occurs) Waiting Ready

Process admitted to ready queue for 1st time New Ready

Scheduler preempts (interrupts) process Running Ready

Process finishes execution (task complete) Running Terminated

Process initiates I/O Running Waiting

Scheduler dispatches process to CPU Ready Running

[Dinosaur Book Ref] Section 3.1.2 — Process State, Figure 3.2

3.4 Context Switch

EXAM FOCUS: What actions does a kernel take during a context switch? Which are overhead? — Fall
2022!

A context switch happens when the CPU switches from running one process to another.

Process P1 running Context Switch Process P2 running

■■■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■■■■■■■■
Executing... 1. Save P1 state Executing...
into P1's PCB
2. Load P2 state
from P2's PCB
3. Give CPU to P2

• Overhead: No useful work is done during context switch — it is pure overhead

• The more complex the OS and PCB, the longer the context switch takes
• Hardware with multiple register sets can speed up context switching
 NOTE: Context switch time is typically 1–1000 microseconds depending on hardware.

3.5 Process Creation

EXAM FOCUS: When fork() creates a child, what is shared between parent and child? — FALL 2024
Midterm!

In UNIX/Linux, processes are created using the fork() system call.

Parent Process Child Process
■■■■■■■■■■■■■■ ■■■■■■■■■■■■■■
pid = fork(); ■■creates■■■ pid = 0 (child gets 0)
(pid = child's PID) (child is a copy of parent)
wait(&status;); exec() ← loads new program
(waits for child) exit(0) ← terminates

What is shared after fork()?

Resource Shared after fork()? Explanation

Text (code) YES (read-only) Both run from same code

Heap Initially YES (copy-on-write) Copied when either writes

Stack NO — each has own copy Each process has its own stack

Shared Memory Segments YES (explicitly shared) Both can access

File Descriptors YES (initially) Both inherit open files

NOTE: On fork(): Stack is NOT shared (each has its own). Heap uses "Copy-on-Write" — copied only when
modified. Shared memory segments remain shared.
[Dinosaur Book Ref] Section 3.3.1 — Process Creation

3.6 Interprocess Communication (IPC)

EXAM FOCUS: Message passing vs shared memory — why is message passing slower? — FALL
2024 Midterm!

Processes may need to communicate. There are two main IPC models:

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■■■
■ (a) SHARED MEMORY ■ (b) MESSAGE PASSING ■
■ ■ ■
■ Process A ■ SHARED ■ Process B ■ Process A ■■msg■■■ Process B ■
■ ■ MEMORY ■ ■ ■■■msg■■ ■
■ Both read/write a common ■ OS delivers messages between ■
■ area of memory. ■ processes (like email). ■
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■■■

Feature Shared Memory Message Passing

How it works Both processes access same memory

OSregion
sends/receives messages between processes

Speed FASTER — no OS involvement after

SLOWER
setup — every message goes through OS kernel

Why slower? N/AEach send/receive requires a system call (mode switch to kernel and back)

Ease of use Harder — need synchronization Easier — OS handles details

Best for Large data, same machine Small messages, different machines

Example POSIX shared memory (shm_open) Pipes, sockets, message queues

 [Dinosaur Book Ref] Section 3.4 — Interprocess Communication

Why is Message Passing Slower?

Every send() and receive() call requires a system call, which means: user mode → kernel mode → kernel
handles message → kernel mode → user mode. This mode switching takes time. With shared memory, after the
initial setup, processes read/write directly to RAM — no system calls needed.

Pipes:
• Ordinary (Anonymous) Pipes: Unidirectional, require parent-child relationship
• Named Pipes: Bidirectional, no parent-child needed, multiple processes can use it
ANALOGY: A pipe is literally a one-way pipe: data flows in one end and out the other, just like water in a
plumbing pipe.

3.7 Thread Switching vs Process Switching

EXAM FOCUS: Under what situation does thread switching and process switching take same time?
— FALL 2024!

Thread switching is normally faster than process switching because threads share the same address space (no
need to switch memory maps, page tables, etc.).

• Thread switching == Process switching time when: threads belong to different processes
• In this case, the OS must switch address spaces just like a full process switch
• Within the same process, thread switch is cheaper (same memory space, same open files)

3.8 Concurrency vs Parallelism

EXAM FOCUS: Difference between concurrent and parallel system — FALL 2024, FALL 2023
Midterms!

Concurrency Parallelism

Definition
Multiple tasks making PROGRESS (not necessarily
Multiple tasks
at same
executing
instant)SIMULTANEOUSLY (at the same instant)

Hardware needed Single CPU is enough Requires multiple CPUs/cores

How?CPU switches between tasks rapidly (context switching)

Multiple CPUs each run a task at the same time

Analogy
One chef cooking multiple dishes by switching
Multiple
between
chefsthem
each cooking a different dish at the same time

[Dinosaur Book Ref] Section 4.1.1 — Concurrency vs Parallelism

 Chapter 4: Threads & Concurrency

4.1 What is a Thread?

A thread is a lightweight unit of execution within a process. A process can have multiple threads that share the
same resources but execute independently.

ANALOGY: A process is like a factory. Threads are like workers inside that factory. They all share the same
building (memory), tools (resources), and blueprints (code), but each worker (thread) does their own task
simultaneously.

What threads share vs. have separately:

Shared Among Threads (in same process) Each Thread Has Its Own

Code (text section) Thread ID

Data section (global variables) Program Counter (PC)

Heap (dynamically allocated memory) Register Set

Open files & I/O resources Stack (local variables, function calls)

[Dinosaur Book Ref] Section 4.1 — Thread concept, Figure 4.1

4.2 Benefits of Multithreading

• Responsiveness: App stays responsive even if one thread is blocked (e.g., UI thread keeps running while
download thread waits)
• Resource Sharing: Threads share memory by default — no need for complex IPC
• Economy: Creating a thread is much cheaper than creating a new process (less memory, less time)
• Scalability: Can take advantage of multiple CPU cores — each thread can run on a different core

Why is thread switching faster than process switching?

• Threads share address space — no need to switch page tables or memory maps
• Less state to save/restore compared to a full process context switch
• Thread switch stays within the same process — no TLB flush needed

4.3 Concurrency vs Parallelism (Revisited)

EXAM FOCUS: This distinction appears in almost every midterm — know it cold!
CONCURRENCY (single core — one at a time but rapid switching):
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
Core 1: [T1]■[T2]■[T1]■[T3]■[T2]■[T1] ← switching fast

PARALLELISM (multiple cores — truly simultaneous):

■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
Core 1: [T1■■■■■■■■■■■■■■■■■■]
Core 2: [T2■■■■■■■■■■■■■■■■■■] ← actually at same time
Core 3: [T3■■■■■■■■■■■■■■■■■■]

4.4 Data Parallelism vs Task Parallelism

EXAM FOCUS: Differentiate between data parallelism and task parallelism — Spring 2023!

Type Definition Example

Data
The
Parallelism
SAME operation is performed on different
Summing
SUBSETS
a large
of data
array:
simultaneously
Core 1 sums first half, Core 2 sums second half
 DIFFERENT
Task Parallelism
operations (tasks/threads) run simultaneously
One thread spells-check,
on the sameanother
or different
thread
data
auto-saves, another syncs to cloud

ANALOGY: Data Parallelism: 4 workers all painting walls — same job, different walls. Task Parallelism:
Worker 1 paints, Worker 2 lays flooring, Worker 3 installs windows.
[Dinosaur Book Ref] Section 4.2.1 — Types of Parallelism

4.5 Multithreading Models

User threads must be mapped to kernel threads. There are 3 models:

Model How it Maps Problem Example

Many-to-One Many user threads → 1 kernel

If one
thread
blocks, ALL block. No true parallelism.
Solaris Green Threads (old)

One-to-One 1 user thread → 1 kernel thread

Creating many threads = overhead
Windows, Linux (most common)

Many user threads → Many kernel threads

Many-to-Many Complex to implement Not very common today

[Dinosaur Book Ref] Section 4.3 — Multithreading Models

4.6 Thread Libraries

• Pthreads (POSIX): Standard API for Unix/Linux. Functions: pthread_create(), pthread_join(),
pthread_exit()
• Windows Threads: CreateThread(), WaitForSingleObject()
• Java Threads: Implement Runnable interface or extend Thread class

4.7 Implicit Threading — Fork-Join

EXAM FOCUS: Fork-join strategy — explain and give examples — Spring 2023 Midterm!

In fork-join, a parent thread forks (creates) multiple child threads to do work in parallel, then joins (waits for) all
children to complete before continuing.
Parent Thread
■
■■■■ fork ■■■ Child Thread 1 (does task 1)
■■■■ fork ■■■ Child Thread 2 (does task 2)
■■■■ fork ■■■ Child Thread 3 (does task 3)
■
■■■■ join ■■(waits for all children to finish)
■
Parent continues with combined result

When to use Fork-Join?

• Merge Sort: Fork to sort each half in parallel, join and merge
• Matrix Multiplication: Each thread computes one row/column
• Web server: Fork a thread for each incoming request, join when done
[Dinosaur Book Ref] Section 4.5.1 — Fork-Join Parallelism

4.8 Thread Pools

Instead of creating a new thread for every task (expensive!), create a pool of threads at startup and reuse them
for incoming tasks.

• Avoids overhead of creating/destroying threads for each task

• Limits total number of threads — prevents system overload
ANALOGY: A thread pool is like a taxi stand. When you need a taxi (task), you don't build a new car — you
take one from the stand. After the ride, the taxi returns to the stand for the next customer.

4.9 NUMA (Non-Uniform Memory Access)

 EXAM FOCUS: What is NUMA? Should the scheduler take it into account? — Spring 2023 Midterm!

In NUMA systems, each CPU has its own local memory that it can access faster than memory belonging to
other CPUs.
■■■■■■■■■■■■ fast ■■■■■■■■■■■■ ■■■■■■■■■■■■ fast ■■■■■■■■■
■■■
■ CPU 0 ■ ■■■■■■■■ ■ Memory 0 ■ ■ CPU 1 ■ ■■■■■■■■ ■ Memory 1 ■
■■■■■■■■■■■■ ■■■■■■■■■■■■ ■■■■■■■■■■■■ ■■■■■■■■■
■■■
■ ■ ■ ■
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ (slow cross-access)

• Should scheduler consider NUMA? YES!

• Assign a thread to a CPU close to the memory it uses → faster memory access
• Moving threads across NUMA nodes causes "remote" (slow) memory access
• NUMA-aware scheduling improves performance significantly
[Dinosaur Book Ref] Section 5.5.4 — NUMA and CPU Scheduling

4.10 Threading Issues

fork() in multithreaded programs:
• Some UNIX versions have 2 fork() versions: one duplicates ALL threads, one duplicates only the calling
thread
• exec() replaces the entire process (including all threads)

Thread Cancellation:
• Asynchronous cancellation: Target thread terminated immediately — risky
• Deferred cancellation: Thread checks at safe points if it should cancel — safer
 Chapter 5: CPU Scheduling

5.1 Basic Concepts

CPU Scheduling decides which process in the Ready Queue gets the CPU next. The goal is to maximize
CPU utilization and efficiency.

• CPU Burst: Time a process uses the CPU before needing I/O
• I/O Burst: Time a process waits for I/O to complete
• Processes alternate between CPU bursts and I/O bursts throughout their life
ANALOGY: CPU scheduling is like a doctor's appointment system. The doctor (CPU) can only see one
patient at a time. The scheduling algorithm decides which patient (process) gets to go in next.
[Dinosaur Book Ref] Section 5.1 — Basic Concepts

Preemptive vs Non-Preemptive Scheduling:

Type Definition When CPU is released

Non-Preemptive
Once a process gets CPU, it keeps it until doneOnly
or waiting
when process terminates or does I/O

Preemptive OS can forcibly take CPU away from running

Anytimeprocess
— timer interrupt, higher priority process arrives

NOTE: Modern OSes (Windows, Linux, macOS) ALL use preemptive scheduling.

Dispatcher:
The dispatcher is the module that gives control of the CPU to the process selected by the scheduler. It does
context switch, switches to user mode, and jumps to the right program location.

• Dispatch latency = time to stop one process and start another (should be minimal)

5.2 Scheduling Criteria

EXAM FOCUS: Difference between waiting time and response time — Spring 2024 Midterm!

Criterion Definition Goal

CPU Utilization Percentage of time CPU is busy Maximize (ideally 100%)

Throughput Number of processes completed per unit time Maximize

Total time from submission to completion

Turnaround Time Minimize
= Completion Time - Arrival Time

Total time process spends in ready queue

Waiting Time Minimize
= Turnaround Time - Burst Time

Time from submission until FIRST response is produced

Response Time Minimize
(not full completion)

NOTE: Waiting time = Response time when: there is no output until full completion (e.g., FCFS, SJF, Priority
non-preemptive, and RR if process runs to completion without preemption). In Round Robin, response time <
waiting time typically.
[Dinosaur Book Ref] Section 5.2 — Scheduling Criteria

5.3 Scheduling Algorithms

Algorithm 1: FCFS — First Come, First Served (Non-Preemptive)
Processes are served in the order they arrive. Simplest algorithm.

• Advantage: Simple and easy to implement

• Disadvantage: Convoy Effect — short processes wait behind long ones
 EXAM FOCUS: FCFS Gantt chart + average waiting time calculation
Example: P1 (burst=24), P2 (burst=3), P3 (burst=3), all arrive at t=0

Gantt Chart:
|■■■■P1■■■■■■■■■■■■■■■■■■■■■|■P2■|■P3■|
0 24 27 30

Waiting Times: P1=0, P2=24, P3=27

Average Waiting Time = (0+24+27)/3 = 17 ms

Algorithm 2: SJF — Shortest Job First (Non-Preemptive)

The process with the shortest next CPU burst is selected. Optimal for minimizing average waiting time
(non-preemptive version).

• Advantage: Minimum average waiting time — optimal!

• Disadvantage: Starvation — long processes may never get CPU if short ones keep arriving
• Problem: Cannot know the exact next CPU burst — must estimate

Example: P1(burst=6), P2(burst=8), P3(burst=7), P4(burst=3), all arrive t=0

Order: P4(3) → P1(6) → P3(7) → P2(8)

Gantt Chart:
|■P4■|■■■■P1■■■■■|■■■■■■■P3■■■■■■|■■■■■■■■P2■■■■■■■■■■|
0 3 9 16 24

Waiting Times: P4=0, P1=3, P3=9, P2=16

Average Waiting Time = (0+3+9+16)/4 = 7 ms

Algorithm 3: SRTF — Shortest Remaining Time First (Preemptive SJF)

Preemptive version of SJF. Whenever a new process arrives with a shorter remaining burst than the current
running process, CPU is preempted.

EXAM FOCUS: SRTF Gantt chart is asked in nearly every midterm — practice this!

Example: P1(arrive=0,burst=8), P2(arrive=1,burst=4),

P3(arrive=2,burst=9), P4(arrive=3,burst=5)

At t=0: P1 runs (only process)

At t=1: P2 arrives (remaining=4 < P1 remaining=7) → P2 preempts P1
At t=2: P3 arrives (remaining=9 > P2 remaining=3) → P2 continues
At t=3: P4 arrives (remaining=5 > P2 remaining=2) → P2 continues
At t=5: P2 done. Shortest remaining: P4(5) < P1(7) < P3(9) → P4 runs
At t=10: P4 done → P1 runs
At t=17: P1 done → P3 runs → finishes at t=26

Gantt: |P1|P2■■|P4■■■■|P1■■■■■■|P3■■■■■■■■■■■■■|
0 1 5 10 17 26

Waiting: P1=(10-1)=9, P2=(1-1)=0, P3=(17-2)=15, P4=(5-3)=2

Avg Waiting = (9+0+15+2)/4 = 6.5 ms

[Dinosaur Book Ref] Section 5.3.2 — Shortest-Remaining-Time-First

Algorithm 4: Round Robin (RR) — Preemptive

Each process gets a fixed time slice called a time quantum (q). After the quantum expires, the process is
preempted and added to the end of the ready queue. Good for time-sharing.
 • Advantage: Fair — every process gets equal share. Good response time
• Disadvantage: Higher average turnaround than SJF if quantum is large
• If q is large → behaves like FCFS. If q is tiny → lots of context switch overhead
• Rule of thumb: 80% of CPU bursts should be shorter than the quantum

EXAM FOCUS: RR Gantt chart with given quantum — calculated in multiple midterms!
Example: P1(burst=24), P2(burst=3), P3(burst=3), arrive t=0, quantum=4

t=0: P1 runs 4ms → preempted (remaining=20)

t=4: P2 runs 3ms → done at t=7
t=7: P3 runs 3ms → done at t=10
t=10: P1 runs 4ms → preempted (remaining=16) ... continues cycling

Gantt: |■■P1■■|■P2■|■P3■|■■P1■■|■■P1■■|■■P1■■|■■P1■■|■■P1■■|
0 4 7 10 14 18 22 26 30

Algorithm 5: Priority Scheduling

Each process has a priority number. The CPU is given to the process with the highest priority. Convention
varies: lower number = higher priority is common (asked in most papers!).

• Preemptive: Higher priority process arriving preempts current running process

• Non-Preemptive: Once running, process runs to completion
• Problem: Starvation — low priority processes may never run
• Solution: Aging — gradually increase priority of waiting processes

EXAM FOCUS: Priority scheduling Gantt chart — preemptive and non-preemptive — asked in FALL
2022, FALL 2023, SPRING 2022, SPRING 2023, FALL 2025 Midterms!
IMPORTANT CONVENTION (check problem statement!):
"Lower number = HIGHER priority" (most common in exam papers)
OR "Lower number = LOWER priority" (sometimes used — READ CAREFULLY!)

Non-Preemptive Priority Example:

P1(burst=10,priority=3,arrive=0), P2(burst=1,priority=1,arrive=0),
P3(burst=2,priority=4,arrive=0), P4(burst=1,priority=5,arrive=0),
P5(burst=5,priority=2,arrive=0) [Lower number = higher priority]

Order: P2(p1)→P5(p2)→P1(p3)→P3(p4)→P4(p5)
Gantt: |P2|■■P5■■|■■■■■■P1■■■■■■|■■P3■■|P4|
0 1 6 16 18 19

5.4 How to Solve Scheduling Problems (Step-by-Step)

EXAM FOCUS: This is THE most important skill for the exam — Gantt charts appear in every paper!

• Step 1: List all processes with arrival time, burst time, priority
• Step 2: Understand the algorithm: preemptive or non-preemptive? which criterion?
• Step 3: Draw the Gantt chart timeline step by step
• Step 4: Calculate Completion Time (CT) = when process finishes
• Step 5: Calculate Turnaround Time (TAT) = CT − Arrival Time
• Step 6: Calculate Waiting Time (WT) = TAT − Burst Time
• Step 7: Calculate averages: Average WT = sum of all WTs ÷ number of processes

Complete Worked Example (Mixed Priority + Round Robin):

EXAM FOCUS: This type of mixed-algorithm question appeared in FALL 2025 Midterm!
 Processes: P1(arrive=0,burst=8,priority=3), P2(arrive=0,burst=6,priority=4),
P3(arrive=0,burst=7,priority=2), P4(arrive=4,burst=3,priority=1),
P5(arrive=6,burst=5,priority=5)
Rules: Priority 1=highest. Medium-priority share CPU via RR (q=2).
Highest priority(1) preempts whenever it arrives.

Note: Identify groups: P4 priority 1 (highest, preemptive)

P3 priority 2 (medium→RR), P1 priority 3 (medium→RR)
P2 priority 4 (medium→RR), P5 priority 5 (lowest, runs last)

→ Draw timeline, apply P4 preemption at t=4, medium processes RR when P4 done

5.5 Key Formulas

Term Formula

Turnaround Time (TAT) Completion Time − Arrival Time

Waiting Time (WT) Turnaround Time − Burst Time OR Start Time − Arrival Time

Response Time Time of FIRST response − Arrival Time

Average WT Sum of all Waiting Times ÷ Number of Processes

CPU Utilization (Total Busy Time ÷ Total Time) × 100%

5.6 Multilevel Feedback Queue (MLFQ)

EXAM FOCUS: MLFQ calculation appeared in Spring 2023 Midterm!

A Multilevel Feedback Queue has multiple queues with different scheduling algorithms and priorities.
Processes can move between queues based on their behavior.
Queue 0 (Highest Priority): RR with quantum = 8ms
■ if not done in 8ms → move to Queue 1
▼
Queue 1: RR with quantum = 16ms
■ if not done in 16ms → move to Queue 2
▼
Queue 2 (Lowest Priority): FCFS

• New processes start in the highest priority queue

• Short CPU bursts → stay in high priority queue (get done quickly)
• Long CPU bursts → demoted to lower queues
• I/O-bound processes tend to stay at high priority (use CPU for short bursts)
• This adapts to process behavior automatically!
[Dinosaur Book Ref] Section 5.3.6 — Multilevel Feedback Queue Scheduling
 Chapter 6: Synchronization Tools

6.1 The Problem — Race Condition

EXAM FOCUS: What is a race condition? Explain with an example — Spring 2022 Midterm!

A race condition occurs when two or more processes/threads access shared data concurrently, and the final
result depends on the order of execution (which is unpredictable). This leads to data inconsistency.

ANALOGY: Two people editing the same Google Doc simultaneously without coordination. Person A reads
"balance = 500", Person B reads "balance = 500". A adds 100 and writes 600. B subtracts 200 and writes
300. The result is 300 — but the correct answer is 400! A's update was lost.

Example: counter++ done by TWO processes simultaneously

counter++ is actually 3 machine instructions:

register = counter (load)
register = register + 1 (increment)
counter = register (store)

Interleaved execution (counter = 5 initially):

P1: register1 = counter → register1 = 5
P1: register1 = register1+1 → register1 = 6
P2: register2 = counter → register2 = 5 ← PROBLEM! reads old value
P2: register2 = register2+1 → register2 = 6
P1: counter = register1 → counter = 6
P2: counter = register2 → counter = 6 ← Should be 7!
[Dinosaur Book Ref] Section 6.1 — Race Condition

6.2 Critical Section Problem

A critical section is a part of code that accesses shared resources (shared variables, files, etc.). The Critical
Section Problem is: design a protocol so that processes can enter their critical sections safely.

Structure of a process:
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
■ do { ■
■ ENTRY SECTION ← ask permission to enter ■
■ ■■■■■■■■■■■■■■■■■■■■■■ ■
■ CRITICAL SECTION ← access shared resource ■
■ ■■■■■■■■■■■■■■■■■■■■■■ ■
■ EXIT SECTION ← announce leaving ■
■ REMAINDER SECTION ← rest of code ■
■ } while(true); ■
■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■

3 Requirements for a Valid Solution:

EXAM FOCUS: The 3 requirements are directly asked — must memorize all three!

Requirement Meaning Simple Explanation

1. Mutual Exclusion
If Pi is in its CS, no other process can beOnly
in their
ONE CSprocess in the critical section at a time

If no process
2. Progress
is in CS and some want to enter, selection
If CS cannot
is free and
be postponed
someone wants
indefinitely
in, they should eventually get in

A bound
3. Bounded
must exist
Waiting
on how many times others enter
NoCS
process
after ashould
process
wait
hasforever
requested
— there's
entry a limit to how long you wait

[Dinosaur Book Ref] Section 6.2 — The Critical-Section Problem

6.3 Semaphores — VERY IMPORTANT
EXAM FOCUS: Semaphore questions appear in EVERY midterm — binary vs counting, wait/signal,
ordering!

A semaphore is an integer variable that is accessed only through two atomic operations: wait() and signal().

wait(S) { signal(S) {
while (S <= 0) S++;
; // busy wait }
S--;
}

ANALOGY: A semaphore is like a parking lot counter sign. The sign shows available spots (S). When a car
enters (wait), the count decreases. When a car leaves (signal), the count increases. If count = 0, you wait
outside until someone leaves.

Types of Semaphores:
Type Value Range Purpose Equivalent To

Binary Semaphore 0 or 1 only Mutual exclusion (one process at a time) Mutex Lock

Counting Semaphore 0 to N (any integer)

Control access to a resource with N instances
N-space parking lot

[Dinosaur Book Ref] Section 6.6 — Semaphores

Using Semaphores for Mutual Exclusion:

Semaphore mutex = 1; // initialized to 1

Process Pi:
wait(mutex); // enter: decrement, wait if 0
// CRITICAL SECTION
signal(mutex); // exit: increment, wake up waiter

Using Semaphores for Process Ordering (Synchronization):

EXAM FOCUS: Semaphore ordering/synchronization problems are the most common exam question!

Goal: Ensure S1 in P1 executes BEFORE S2 in P2.

Semaphore sync = 0; // initialized to 0

P1: P2:
S1; wait(sync); // wait until signaled
signal(sync); S2; // runs after S1

NOTE: Key insight: Initialize to 0 for ordering/synchronization. Initialize to 1 for mutual exclusion (mutex).

Classic Ordering Problem (appears in many papers):

EXAM FOCUS: Process A must finish before B starts, B before C or D, D before E — Fall 2022, Spring
2022, Spring 2024 Midterms!
Goal: A→B, B→(C or D), D→E [A finishes before B starts, etc.]

Semaphores: S1=0, S2=0, S3=0 (all initialized to 0)

Process A: Process B: Process C: Process D: Process E:

... wait(S1); wait(S2); wait(S2); wait(S3);
signal(S1); ... ... ... ...;
signal(S2); signal(S2 signal(S3);
signal(S2);
 NOTE: Pattern: After completing, a process signals the next one's semaphore. The next process waits on that
semaphore before starting.

6.4 Semaphore Implementation — Busy Waiting vs Block-Wakeup

EXAM FOCUS: Busy waiting — what is it? How do you remove it? With pseudo code — Spring 2022!

Busy Waiting (Spinlock):

In the basic semaphore, a waiting process keeps looping: while(S<=0) ; — wasting CPU cycles. This is called
busy waiting or spinning.

• Problem: CPU is consumed even while waiting — wasteful

• OK for: Very short waits (e.g., kernel critical sections)

Removing Busy Waiting (Block-Wakeup):

Each semaphore has a waiting queue:
typedef struct {
int value;
struct process *list; // waiting queue
} semaphore;

wait(S):
S->value--;
if (S->value < 0) {
add process to S->list; // put to sleep
block(); // suspend process
}

signal(S):
S->value++;
if (S->value <= 0) {
remove process P from S->list; // wake someone up
wakeup(P); // put in ready queue
}

• Advantage: Process sleeps — CPU used productively elsewhere

• Disadvantage: Overhead of block/wakeup (more complex than spinlock)
ANALOGY: Busy waiting: Standing at a door knocking every second until it opens. Block/wakeup: Leaving
your number at the door and going home. They call you when ready.
[Dinosaur Book Ref] Section 6.6.1 — Semaphore Implementation

6.5 Tricky Semaphore Question Types

EXAM FOCUS: Find max and min value of shared variable — FALL 2025 Midterm Part C!

Scenario: Variable Y = 10. Three processes: P1: Y×2, P2: Y+5, P3: Y-8. Binary semaphore (S=1) enforces
strict mutual exclusion. Find max and min final value of Y.
All 6 possible orderings:
P1→P2→P3: (10×2)+5-8 = 17
P1→P3→P2: (10×2)-8+5 = 17
P2→P1→P3: (10+5)×2-8 = 22
P2→P3→P1: (10+5-8)×2 = 14
P3→P1→P2: (10-8)×2+5 = 9
P3→P2→P1: (10-8+5)×2 = 14

Maximum = 22, Minimum = 9

6.6 Mutex Locks
A mutex lock is the simplest synchronization tool — a boolean variable (lock) that is either available (false) or
unavailable (true).
acquire() { release() {
while (!available) available = true;
; // busy wait }
available = false;
}

Usage:
acquire(lock);
// critical section
release(lock);

NOTE: A binary semaphore (initialized to 1) and a mutex lock serve the same purpose. Mutex = "MUTual
EXclusion". Only one process can hold it at a time.

6.7 Deadlock and Starvation

Deadlock: Two or more processes are each waiting for an event that only the other can cause — they wait
forever.
P0: P1:
wait(S); wait(Q);
wait(Q); ←■■■ Q held by P1 ■ P0 holds S ■■■ wait(S);
... ... ■ DEADLOCK!
signal(S); signal(Q);

• Starvation: A process is indefinitely blocked — others keep getting priority over it

• Priority Inversion: Low-priority process holds a lock needed by high-priority process
• Solution to Priority Inversion: Priority Inheritance Protocol — temporarily give the low-priority process the
high priority until it releases the lock
 Chapter 7: Synchronization Examples

7.1 Classical Synchronization Problems

These are classic problems used to test synchronization solutions. They model real-world scenarios and are
heavily tested in exams.

7.2 Bounded-Buffer Problem (Producer-Consumer)

EXAM FOCUS: Producer-Consumer with semaphores — FALL 2025 Midterm Part A & B!

A producer produces items and puts them in a shared buffer. A consumer takes items from the buffer and
consumes them. The buffer has limited size N.

ANALOGY: Producer = chef making dishes. Consumer = customer eating dishes. Buffer = the serving
counter (max N dishes). Chef waits if counter is full. Customer waits if counter is empty.

Semaphores Needed:
Semaphore Initial Value Meaning

mutex 1 Mutual exclusion for buffer access

empty N (buffer size) Count of empty buffer slots

full 0 Count of filled buffer slots

Solution:
PRODUCER: CONSUMER:
while (true) { while (true) {
produce item wait(full); // wait for item
wait(empty); // wait slot wait(mutex); // get exclusive access
wait(mutex); // lock buffer remove item from buffer
add item to buffer signal(mutex); // release lock
signal(mutex);// unlock signal(empty); // signal empty slot
signal(full); // signal item consume item
} }

NOTE: Order matters! Always do wait(empty/full) BEFORE wait(mutex). Doing wait(mutex) first can cause
deadlock!
[Dinosaur Book Ref] Section 7.1 — Bounded-Buffer Problem

What happens if producer forgets signal(full)?

EXAM FOCUS: FALL 2025 Midterm Part A asks exactly this!
If producer executes wait(empty) and wait(mutex) to add an item but then forgets signal(full): the consumer
will always wait on wait(full) since full is never incremented. The consumer will be stuck forever — this is a
liveness failure / indefinite blocking.

7.3 Readers-Writers Problem

A shared data set is accessed by two types of processes:

• Readers: Only read — multiple readers can read simultaneously (no conflict)
• Writers: Read AND write — only one writer at a time, no readers while writing

ANALOGY: A library's book: Many students (readers) can read the same book at the same time. But when
an author (writer) edits the book, nobody else can read or write until done.
Semaphores:
• rw_mutex = 1: Mutual exclusion for writers (and first/last reader)
• mutex = 1: Protect the read_count variable
• read_count = 0: Number of currently reading processes

WRITER: READER:
while (true) { while (true) {
wait(rw_mutex); wait(mutex);
// WRITE read_count++;
signal(rw_mutex); if (read_count == 1)
} wait(rw_mutex); // first reader locks writer
signal(mutex);
// READ
wait(mutex);
read_count--;
if (read_count == 0)
signal(rw_mutex); // last reader unlocks
signal(mutex);
}

NOTE: First reader blocks writers by doing wait(rw_mutex). Last reader unblocks writers with signal(rw_mutex).
While any reader is reading, writers are blocked.
• Problem: Writers may starve if readers keep arriving (First Readers-Writers problem)
[Dinosaur Book Ref] Section 7.2 — Readers-Writers Problem

7.4 Dining-Philosophers Problem

5 philosophers sit at a round table. Between each pair of philosophers is one chopstick (5 total). A philosopher
needs BOTH chopsticks to eat. They alternate thinking and eating.
Phil 0
/ \
chop[4] chop[0]
/ \
Phil 4 Phil 1
\ /
chop[3] chop[1]
\ /
Phil 3 - chop[2] - Phil 2

Naive Solution (with Deadlock Problem!):

Philosopher i:
wait(chopstick[i]); // pick up left chopstick
wait(chopstick[(i+1) % 5]); // pick up right chopstick
// EAT
signal(chopstick[i]); // put down left
signal(chopstick[(i+1) % 5]); // put down right

• Problem: All 5 philosophers pick up left chopstick simultaneously → all wait for right → DEADLOCK!

Solutions to Deadlock in Dining Philosophers:

• Allow at most 4 philosophers at the table simultaneously
• Allow philosopher to pick up chopsticks only if BOTH are available (atomic pickup)
• Asymmetric solution: Odd philosophers pick left first, even pick right first
• Use a Monitor solution with states: THINKING, HUNGRY, EATING

Monitor Solution:
 States: THINKING, HUNGRY, EATING

pickup(i):
state[i] = HUNGRY;
test(i); // try to eat
if (state[i] != EATING) self[i].wait(); // wait if cannot eat

test(i):
if (left neighbor != EATING) AND (state[i]==HUNGRY) AND (right neighbor != EATING):
state[i] = EATING;
self[i].signal(); // wake up philosopher i

putdown(i):
state[i] = THINKING;
test(left neighbor); // maybe they can eat now
test(right neighbor);

• No deadlock with Monitor solution, but starvation is still possible

[Dinosaur Book Ref] Section 7.1.3 — Dining-Philosophers Problem

7.5 Quick Reference: Semaphore Patterns

EXAM FOCUS: These patterns cover 90% of semaphore exam questions!

Pattern Initial Value Usage

Mutex (mutual exclusion) S=1 Only 1 process in critical section at a time

Ordering (A before B) S=0 A does signal(S), B does wait(S) at start

Counting (N resources) S=N Track available instances of a resource

Full/Empty (buffer) full=0, empty=N Producer-Consumer pattern

Barrier (all wait for all) S=0 All processes reach barrier, then all continue

7.6 Legal Execution Orders with Semaphores

EXAM FOCUS: Given processes with wait/signal code, list legal orderings — FALL 2023, SPRING
2022!

To find legal orderings: A process can execute its next operation only if the semaphore value allows it (wait
blocks if S=0, signal always succeeds).
Example: X=0, Y=1, Z=1
P1: wait(Z), print P1, signal(Z)
P2: wait(Z), print P2, signal(X)
P3: wait(Y), print P3, signal(Z)
P4: wait(X), print P4, signal(Y)

Initially: Z=1 (P1 or P2 can start), Y=1 (P3 can start), X=0 (P4 BLOCKED)

Tip: Start from processes where wait() can succeed immediately.

Trace: Which semaphores are >0? Those processes can go next.
Update values after each signal/wait.

NOTE: Algorithm for finding legal orders: 1. List semaphore values initially 2. Find all processes that can run (their
wait semaphore > 0) 3. Pick one, execute it, update semaphore values 4. Repeat until all processes done 5. Each
path through this decision tree is a legal order

7.7 Summary of All Synchronization Tools

Tool Type Use Case Busy Wait?
 Mutex Lock Binary Mutual exclusion Yes (spinlock)

Binary Semaphore Binary (0 or 1) Mutual exclusion or ordering Optional

Counting Semaphore Integer 0..N N resources / ordering Optional

Monitor High-level Structured synchronization No

Condition Variable With Monitor Wait for a condition to be true No

[Dinosaur Book Ref] Chapter 6-7, Operating System Concepts 10th Ed. — Synchronization Tools & Examples