OPERATING SYSTEMS

Process Synchronization
Complete Study Notes
Race Conditions • Critical Sections • Software & Hardware Solutions

📌 Topics Covered

1. Why Synchronization? — Race Conditions & Core Concepts

2. Critical Section Structure & Three Mandatory Requirements
3. Software Solutions — Four Algorithms (Lock Variable → Peterson's)
4. Software Solutions — Bakery Algorithm (N-Process)
5. Hardware Solutions — Disabling Interrupts, TSL, Swap
6. Comparison: Software vs Hardware
7. Advanced Problems & Past Paper Analysis
8. Quick-Reference Summary & Exam Checklist

Section 1: Why Synchronization? — The Core Problem

1.1 Concurrent vs Parallel Execution
In modern operating systems, processes and threads run in two modes:
• Concurrent (time-slicing): Multiple processes overlap in time on a single CPU via rapid
context switching. Only one runs at a true instant.
• Parallel: Processes run simultaneously on multiple CPU cores.
When cooperating processes share access to a common resource — a global variable, shared
memory buffer, or file — uncoordinated access leads to data corruption. Synchronization is the set
of techniques used to ensure concurrent processes interact safely and maintain data consistency.

1.2 Race Condition

⚠️ Definition
A Race Condition occurs when multiple threads/processes read and write to a shared data
location concurrently, and the final outcome depends entirely on the exact order or
interleaving of execution.

Hardware-Level Example: counter++ and counter-- on a shared variable

Consider two threads sharing int counter = 5. Thread A does counter++ and Thread B does
counter--. At the CPU level, these are NOT atomic — each compiles to 3 separate machine
instructions:

Operating Systems — Process Synchronization | Page 1

 High-Level Code Assembly Instructions What Happens Internally

counter++ MOV R1, [counter] ADD R1, 1 MOV Load → Increment → Store back
[counter], R1

counter-- MOV R2, [counter] SUB R2, 1 MOV Load → Decrement → Store back
[counter], R2

Detailed Dry Run — Worst-Case Interleaving (counter = 5)

Time Thread Instruction Register RAM (counter)
─────────────────────────────────────────────────────────────────
T1 Thread A MOV R1, [counter] R1 = 5 counter = 5
T2 Thread A ADD R1, 1 R1 = 6 counter = 5
──── CONTEXT SWITCH: Thread A → Thread B ────
T3 Thread B MOV R2, [counter] R2 = 5 counter = 5
T4 Thread B SUB R2, 1 R2 = 4 counter = 5
T5 Thread B MOV [counter], R2 R2 = 4 counter = 4
──── CONTEXT SWITCH: Thread B → Thread A resumes ────
T6 Thread A MOV [counter], R1 R1 = 6 counter = 6 ← BUG!

❌ Result
Expected: 5. Actual: 6. Thread A overwrote Thread B's update. Depending on
interleaving, counter could be 4, 5, or 6 — this unpredictable behaviour is the race
condition.

1.3 Structural Anatomy of a Cooperating Process

Every access to shared data must be wrapped in this standard four-part structure:

Section Purpose Key Rule

Entry Section Request permission to enter Critical Must WAIT if another process is inside
Section CS

Critical Section (CS) Reads/modifies shared resources — Only ONE process allowed here at a
the danger zone time

Exit Section Release permission; signal resource Must notify waiting processes
is free

Remainder Section All other non-shared local code Cannot block entry of other processes

Operating Systems — Process Synchronization | Page 2

Section 2: The Three Mandatory Requirements

📋 Every synchronization protocol MUST satisfy all three:

These are tested in nearly every exam — know them cold.

✅ 1. Mutual Exclusion

If process Pᵢ is executing in its critical section, NO other process can be in its critical
section. This is the absolute safety requirement — the most fundamental rule.

✅ 2. Progress (No Deadlock)

If no process is currently in the CS, and some processes want to enter, only those NOT in
their remainder sections can decide who enters next. This decision cannot be postponed
indefinitely.
→ Prevents deadlocks where no one ever enters.

✅ 3. Bounded Waiting (No Starvation)

There must be a LIMIT on how many times other processes can enter the CS after a
process has requested entry and before that request is granted.
→ Prevents starvation where one process waits forever.

Section 3: Software Solutions — Four Algorithms

The following four algorithms represent the historical evolution of software-based mutual exclusion.
Each directly addressed a weakness of its predecessor.

Summary at a Glance
Algorithm Mutual Progress? Bounded Main Failure
Exclusion? Waiting?

Lock Variable ❌ No ❌ No — Race condition (check-set

not atomic)

Strict Alternation ✅ Yes ❌ No ✅ Yes (1 turn) Process in remainder

blocks others

Yet Another Solution ✅ Yes ❌ No ❌ No Deadlock possible

(Flags)

Operating Systems — Process Synchronization | Page 3

 Peterson's Algorithm ✅ Yes ✅ Yes ✅ Yes (1 turn) Works (hardware
reordering caveat)

Algorithm 1 — Lock Variable (Single Shared Lock)

Core Idea
A single shared boolean variable lock acts as a flag. lock = false → CS is free. lock = true →
CS is occupied; other processes busy-wait.

Pseudo-Code
bool lock = false; // Shared variable, initially free

do {
while (lock == true) ; // Busy-wait if locked
lock = true; // Acquire lock
/* CRITICAL SECTION */
lock = false; // Release lock
/* REMAINDER SECTION */
} while (true);

Dry Run — Race Condition

Ste Process A Process B lock Explanation
p

1 Sees lock=false → — false A observes CS is free

exits loop

2 — Sees lock=false → false B also observes CS is free

exits loop

3 lock = true — true A sets the lock

4 — lock = true true B also sets the lock (too late!)

5 Enters CS Enters CS true Both in CS — Mutual Exclusion

VIOLATED ❌

❌ Why It Fails — Race Condition

The check (while(lock==true)) and the set (lock=true) are two separate, non-atomic
steps. A context switch between them allows two processes to both see the lock as free and
both enter simultaneously.

📚 Exam Note
This is the classic motivation for atomic test-and-set hardware instructions.

Operating Systems — Process Synchronization | Page 4

Algorithm 2 — Strict Alternation (Turn Variable)
Core Idea
A shared integer turn explicitly records whose turn it is to enter the CS. After exiting, a process
passes the turn to the other. Processes take turns in strict order.

Pseudo-Code
int turn = 0; // 0 = P0's turn, 1 = P1's turn

// Process 0 // Process 1
do { do {
while (turn != 0) ; while (turn != 1) ;
/* CRITICAL SECTION */ /* CRITICAL SECTION */
turn = 1; turn = 0;
/* REMAINDER SECTION */ /* REMAINDER SECTION */
} while (true); } while (true);

Dry Run — Progress Failure

Ste P0 P1 turn Who Can Enter?
p

1 In CS — 0 P0

2 Exits CS → turn = 1 — 1 —

3 In long Remainder Wants CS; checks turn!=1 1 Nobody (P1 stuck, P0

Section → false → spins uninterested)

❌ Why It Fails — Progress Violated

The algorithm forces strict turn-taking. Even if P0 has no interest in the CS, P1 cannot
enter until P0 gives the turn. A process in the remainder section is blocking another
from entering — a direct Progress violation.

📚 Exam Note
Mutual Exclusion: ✅ Bounded Waiting: ✅ (wait at most 1 turn) Progress: ❌ — the only
failure.

Algorithm 3 — Yet Another Solution (Interest Flags)

Core Idea
Each process has its own flag in a shared array, indicating desire to enter the CS. A process only
waits if the other also wants to enter.

Pseudo-Code
bool flag[2] = {false, false}; // Initially nobody is interested

// Process i (j = 1 - i)

Operating Systems — Process Synchronization | Page 5

 do {
flag[i] = true; // Announce intent
while (flag[j] == true) ; // Wait if other also wants to enter
/* CRITICAL SECTION */
flag[i] = false; // Retract intent
/* REMAINDER SECTION */
} while (true);

Dry Run — Deadlock

Ste P0 P1 flag[0] flag[1] Explanation
p

1 flag[0] = true — T F P0 announces intent

2 — flag[1] = true T T P1 announces intent (context

switch)

3 while(flag[1]) → — T T P0 waiting for P1

spins

4 — while(flag[0]) → T T P1 waiting for P0 → DEADLOCK

spins ❌

❌ Why It Fails — Deadlock (Progress Violated)

If both set flags before either checks the other's flag, they enter a symmetric deadlock:
each waiting for the other to lower its flag. The system halts entirely.

📚 Exam Note
Direct stepping stone to Peterson's. Mutual Exclusion holds when no deadlock occurs, but
Bounded Waiting can also fail (starvation possible).

Algorithm 4 — Peterson's Solution

Core Idea
Combines flag[] (intent) with turn (tie-breaker). By writing turn = j immediately after raising its
flag, a process altruistically yields to the other in case of a tie. This single move breaks deadlock
symmetry and satisfies all three requirements.

Pseudo-Code
bool flag[2] = {false, false};
int turn;

// Process i (j = 1 - i)
do {
flag[i] = true; // Declare intent
turn = j; // Yield turn to other
while (flag[j] == true && turn == j) ; // Wait only if: other wants
AND it is their turn

Operating Systems — Process Synchronization | Page 6

 /* CRITICAL SECTION */
flag[i] = false; // Retract intent
/* REMAINDER SECTION */
} while (true);

Step-by-Step Dry Run — Both Processes Enter Simultaneously

St P₀ Action P₁ Action flag[ flag[ turn Explanation
ep 0] 1]

1 flag[0]=true — T F 0 P₀ announces interest

2 turn=1 — T F 1 P₀ yields to P₁

3 — flag[1]=true T T 1 P₁ announces interest

4 — turn=0 T T 0 P₁ yields to P₀

5 while: flag[1]=T, — T T 0 P₀ enters CS ✅

turn=1? → turn=0 →
FALSE → enters CS

6 — while: flag[0]=T, T T 0 P₁ busy-waits

turn=0 → TRUE →
spins

7 flag[0]=false (exit CS) — F T 0 P₀ exits CS

8 — Re-checks: flag[0]=F F T 0 P₁ enters CS ✅

→ FALSE → enters
CS

✅ How It Fixes Each Previous Failure

Lock Variable (non-atomic check-set): No atomicity needed. The while condition uses
both flag and turn together — a context switch mid-entry cannot allow simultaneous access.
Strict Alternation (progress failure): If flag[j]=false, the while condition is immediately false
and process i enters right away — no forced alternation.
Flag Algorithm (deadlock): If both set flags, turn holds the value of whichever wrote last.
Only one can have turn==j, so exactly one process passes through.

✅ Correctness Proof (Sketch)

• Mutual Exclusion: For both to be in CS, flag[0]=flag[1]=true and turn=0 and turn=1
simultaneously — impossible.
• Progress: If flag[j]=false, the loop exits immediately. No uninterested process blocks
another.
• Bounded Waiting: A process waits at most one complete cycle of the other. Once it
exits and sets flag[j]=false, entry is guaranteed.

Operating Systems — Process Synchronization | Page 7

⚠️ Important Caveat — Hardware Memory Reordering
Peterson's is correct under the Sequential Consistency memory model. On modern
processors, instruction reordering by the compiler/CPU can break mutual exclusion. In
practice, memory barriers (mfence) or atomic operations are required.

❗ Why Peterson's Is NOT Used in Practice (Exam Favourite)

• Instruction Reordering: Compiler and CPU may reorder flag[i]=true and turn=j,
breaking mutual exclusion on real hardware.
• Busy Waiting: The spin loop wastes CPU cycles — acceptable only for very short
critical sections.
• Only 2 Processes: Does not scale — use Bakery Algorithm for N processes.
📚 Past paper (Spring 2024, Q1c): "What are the limitations of Peterson's solution on
modern architectures?"

📝 Evolution Chain
Lock Variable → check-set not atomic → Race Condition
↓
Strict Alternation → forced turns → Progress Failure
↓
Interest Flags → symmetric deadlock → Progress Failure
↓
Peterson's → flag[] + turn tie-breaker → All three ✅

Operating Systems — Process Synchronization | Page 8

Section 4: Bakery Algorithm (N Processes)
🥨 Real-World Analogy

Like a bakery ticket counter: every arriving customer takes a number. The customer with the
LOWEST number is served first. If two customers get the same number, the one with the
smaller Process ID wins.

Shared Variables
bool choosing[N] = {false}; // choosing[i] = true while Pᵢ is picking a number
int number[N] = {0}; // number[i] holds Pᵢ's ticket (0 = not
interested)

Algorithm Structure (for Process Pᵢ)

do {
// ── ENTRY: Step A – Pick a ticket safely ──
choosing[i] = true;
number[i] = 1 + max(number[0], ..., number[N-1]);
choosing[i] = false;

// ── ENTRY: Step B – Wait for your turn ──

for (int j = 0; j < N; j++) {
while (choosing[j]); // Wait if j is still
choosing
while (number[j] != 0 &&
(number[j] < number[i] ||
(number[j] == number[i] && j < i))); // Smaller ticket or
smaller PID wins
}

/* CRITICAL SECTION */
number[i] = 0; // EXIT: give up ticket
/* REMAINDER SECTION */
} while (1);

Dry Run — 3-Process Conflict Resolution

Initial state: choosing = {F,F,F}, number = {0,0,0}

Ste Event number[] Result

p

1 P₁ and P₂ arrive simultaneously; both {0,1,1} Tie — same ticket!

compute max+1=1

2 P₁ checks j=2: 1<1? No. 1==1 && {0,1,1} P₁ passes → enters CS

2<1? No → FALSE

3 P₂ checks j=1: 1<1? No. 1==1 && {0,1,1} P₂ busy-waits for P₁

1<2? YES → TRUE

Operating Systems — Process Synchronization | Page 9

 4 P₁ exits CS: number[1] = 0 {0,0,1} P₁ releases ticket

5 P₂ re-checks j=1: number[1]=0 → {0,0,1} P₂ enters CS ✅

FALSE → escapes

Property Verification
• Mutual Exclusion ✅ — Only one process holds the minimum (ticket, PID) pair at a time.
• Bounded Waiting ✅ — Each arriving process gets a strictly increasing number; finite wait
guaranteed.
• Progress ✅ — Tie-breaking by PID ensures one process always advances.
• Busy Waiting ❌ — Still spins in while loops; no blocking/sleeping.
• Real OS Use ❌ — Too complex; compiler reordering still an issue.

Section 5: Hardware Solutions

Modern processors provide hardware instructions that perform memory operations atomically — the
read, modify, and write steps happen in a single uninterruptible clock cycle, eliminating the race
condition at its root.

5.1 Disabling Interrupts (Uniprocessor Only)

In a uniprocessor system, context switches occur when a hardware timer interrupt fires. By
disabling interrupts, the process ensures the CPU cannot preempt it.
do {
disable_interrupts(); // Entry: turn off timer interrupt
/* CRITICAL SECTION */
enable_interrupts(); // Exit: turn timer back on
/* REMAINDER SECTION */
} while (1);

❌ Why It Fails in Practice

• Multiprocessor ineffective: Disabling interrupts only affects the LOCAL CPU core.
Other cores can still access shared memory — mutual exclusion is violated.
• Security risk: User programs cannot be trusted with interrupt control (privileged
instruction). A malicious app could disable interrupts and loop forever, locking up the
OS.
• Misses real interrupts: Critical I/O and clock interrupts are also blocked — the
system may hang.
→ Theoretical understanding only; not a realistic solution.

Operating Systems — Process Synchronization | Page 10

5.2 Test-and-Set Lock (TSL) — Atomic Hardware Primitive

📌 Exam Reference
Appears in: Spring 2022, Spring 2024 Solution Q1d (busy-waiting methods)

Atomic Definition (Conceptual)

// This ENTIRE function executes as ONE uninterruptible hardware step
bool TestAndSet(bool *target) {
bool old = *target; // 1. Record original value
*target = true; // 2. Force-set memory to TRUE
return old; // 3. Return original value
}

Using TSL for Mutual Exclusion

bool lock = false; // Shared lock, initially free

do {
while (TestAndSet(&lock)) ; // Entry: spin until lock was false
/* CRITICAL SECTION */
lock = false; // Exit: release lock
/* REMAINDER SECTION */
} while (1);

Dry Run — Two Threads Competing (Initial: lock = false)

St Thread TSL Internal Execution lock Return Outcome
ep Val

1 Thread A old=false; lock→true; return true false while(false) → ENTER CS ✅

false

2 Thread B old=true; lock stays true; true true while(true) → SPIN ⏳

return true

3 Thread A lock = false (exit CS) false — Thread A exits CS

4 Thread B old=false; lock→true; return true false while(false) → ENTER CS ✅

false

• Mutual Exclusion ✅ — Only the thread that sees return value FALSE enters CS.
• Busy Waiting ❌ — Thread B wastes CPU cycles spinning continuously.
• Starvation possible ❌ — No fairness guarantee in basic TSL; a thread may never be
scheduled.

5.3 Swap (Exchange) Instruction — Another Atomic Primitive

Atomic Definition (Conceptual)
void Swap(bool *a, bool *b) {
bool temp = *a;
*a = *b;

Operating Systems — Process Synchronization | Page 11

 *b = temp;
}

Using Swap for Mutual Exclusion

bool lock = false; // Shared lock

do {
bool key = true; // Local variable unique to THIS thread
while (key == true) {
Swap(&lock, &key); // Entry: swap until key becomes false
}
/* CRITICAL SECTION */
lock = false; // Exit: release lock
/* REMAINDER SECTION */
} while (1);

Key Insight
key starts as true. Swap exchanges lock and key. If lock was false → key becomes false → loop
exits → enter CS. If lock was true → key stays true → loop continues.

Dry Run — Two Threads Competing (Initial: lock = false)

St Thread Swap Internals lock key Outcome
ep

1 Thread A temp=false; lock=true; true false while(false) → ENTER CS ✅

key=false

2 Thread B temp=true; lock=true; true true while(true) → SPIN ⏳

key=true

3 Thread A lock = false (exit CS) false — Thread A exits CS

4 Thread B temp=false; lock=true; true false while(false) → ENTER CS ✅

key=false

Same properties as TSL: mutual exclusion guaranteed, but busy waiting and potential starvation
remain.

Operating Systems — Process Synchronization | Page 12

Section 6: Comparison — Software vs Hardware Solutions
Aspect Peterson's Bakery Disable Interrupts TSL / Swap

Hardware needed? No (software) No (software) No (privileged) Yes (atomic

instr.)

No. of processes 2 only N (unlimited) Any (uniprocessor) Any number

Multiprocessor safe? Yes (in theory) Yes (in theory) ❌ NO ✅ YES

Busy waiting? Yes Yes No (disables CPU) Yes

Starvation risk? No (bounded No (ordered No Yes (basic TSL)

wait) tickets)

Used in real OS? No (reordering) No (too No (unsafe) Yes (short

complex) spinlocks)

Scales to N proc? ❌ No ✅ Yes ❌ No ✅ Yes

Section 7: Advanced Problems & Past Paper Analysis

7.1 Strict Alternation Protocol — Formal Evaluation
This problem appears frequently in past papers. Evaluate the two-process protocol below against
the three mandatory requirements.
int turn = 0; // Shared variable

// Process P₀ // Process P₁
while(1) { while(1) {
while(turn != 0); while(turn != 1);
/* CRITICAL SECTION */ /* CRITICAL SECTION */
turn = 1; turn = 0;
/* REMAINDER SECTION */ /* REMAINDER SECTION */
} }

✅ Mutual Exclusion — SATISFIED

turn holds only one value (0 or 1) at any instant. It is impossible for both while(turn!=0)
and while(turn!=1) to be false simultaneously. → Only one process in CS at a time.

❌ Progress — VIOLATED (Critical Failure)

Scenario: turn=0. P₀ enters CS, sets turn=1, then enters remainder. P₁ enters CS, sets

Operating Systems — Process Synchronization | Page 13

 turn=0, then enters remainder.
Now P₁ finishes remainder and wants CS again — but turn=0, so P₁ BLOCKS even though
the CS is completely EMPTY.
A process in the remainder section is preventing another from entering CS. Direct
Progress violation.

✅ Bounded Waiting — SATISFIED

A process waits at most ONE turn before the other must hand control back. No infinite
waiting (assuming both processes keep running).

📝 Verdict
This protocol FAILS because it violates Progress. Not a valid synchronization solution.

7.2 TSL Hardware Trace Analysis (Spring 2025 Sessional-II, Q3-b)

Question: Trace the internal return values and state changes for TestAndSet, given lock is initially
FALSE. Rule: A thread enters CS only if TestAndSet returns FALSE.

Call Thread lock passed in Return Value Final lock Thread Outcome
#

1 Thread A FALSE FALSE TRUE Enters Critical Section ✅

2 Thread B TRUE TRUE TRUE Busy-waits (spins) ⏳

3 Thread A Executes: lock = N/A FALSE Exits Critical Section

FALSE

4 Thread B FALSE FALSE TRUE Enters Critical Section ✅

7.3 Pthread Mutex — Complete C Implementation (Race Condition Fix)

Problem: A flight ticket booking system has a shared variable availableTickets. If two threads
call bookTicket() concurrently when only 1 ticket remains, both pass the if (availableTickets >
0) check — both decrement — counter drops to −1. Classic race condition.

Complete Solution with POSIX Mutex

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

int availableTickets = 10;

pthread_mutex_t ticketMutex; // Declare mutex lock

Operating Systems — Process Synchronization | Page 14

 void* bookTicket(void* arg) {
long tid = (long)arg;
pthread_mutex_lock(&ticketMutex); // ── ENTRY: Acquire lock ──
if (availableTickets > 0) {
usleep(100000); // Simulate processing delay
availableTickets--;
printf("[Thread %ld] Booked! Remaining: %d\n", tid, availableTickets);
} else {
printf("[Thread %ld] No tickets available.\n", tid);
}
pthread_mutex_unlock(&ticketMutex); // ── EXIT: Release lock ──
return NULL;
}

int main() {
pthread_t threads[4];
pthread_mutex_init(&ticketMutex, NULL); // Initialize mutex
for (long i = 0; i < 4; i++)
pthread_create(&threads[i], NULL, bookTicket, (void*)i);
for (int i = 0; i < 4; i++)
pthread_join(threads[i], NULL);
pthread_mutex_destroy(&ticketMutex); // Clean up
printf("Final count: %d\n", availableTickets);
return 0;
}

🔑 Key Points About This Solution

• pthread_mutex_lock() → Entry Section: blocks if lock already held by another

thread.
• pthread_mutex_unlock() → Exit Section: releases lock, wakes up one waiting
thread.
• The entire check + modify block is inside the lock — no interleaving possible.
• pthread_mutex_destroy() must be called to free kernel resources after use.

Operating Systems — Process Synchronization | Page 15

Section 8: Quick-Reference Summary & Exam Checklist
8.1 Full Algorithm Summary
Algorithm Type Process Mutual Progress Bounded Busy Wait
es Excl. Wait

Strict Alternation Software 2 ✅ ❌ FAILS ✅ Yes

Peterson's Software 2 only ✅ ✅ ✅ Yes

Bakery (Lamport) Software N ✅ ✅ ✅ Yes

Disable Interrupts Hardware 1 CPU ✅ (uniproc) ✅ N/A No

Test-and-Set (TSL) Hardware N ✅ ✅ ❌ (basic) Yes

Swap/Exchange Hardware N ✅ ✅ ❌ (basic) Yes

Pthread Mutex OS/Library N ✅ ✅ ✅ No (blocks)

8.2 Exam Diagnostic Checklist

📝 Use this framework when analyzing any synchronization problem

• Step 1 — Identify Shared State: Which variables/resources are globally shared?

• Step 2 — Verify Atomicity: Is every read-modify-write on shared data protected?
• Step 3 — Check Mutual Exclusion: Can two processes be in CS simultaneously?
• Step 4 — Check Progress: Can a process in remainder section block CS entry?
• Step 5 — Check Bounded Waiting: Is there a finite limit on waiting time?
• Step 6 — Check Busy Waiting: Does the solution spin-wait? Is that acceptable?
• Step 7 — Modern Hardware: Could compiler/CPU reordering break the solution?

8.3 Common Exam Traps

• Peterson on modern hardware: Always mention instruction reordering (compiler + CPU
out-of-order execution) as the key limitation.
• Strict alternation: It ALWAYS fails Progress — that is the expected answer.
• TSL starvation: Basic TSL has no fairness — a process can starve. The bounded-waiting
TSL variant (waiting array) fixes this.
• Disable interrupts on SMP: Only disables on one core — completely ineffective on
multiprocessor systems.
• Busy waiting: Both software (Peterson, Bakery) and hardware (TSL, Swap) solutions busy-
wait. Mutex/semaphores block instead.

Operating Systems — Process Synchronization | Page 16

8.4 Key Vocabulary
Term Definition

Race Condition Non-deterministic outcome caused by concurrent access to shared data

Critical Section (CS) Code segment that reads/writes shared resources — must be protected

Mutual Exclusion Only one process can be in CS at any given time

Busy Waiting / Spin-lock A thread repeatedly checks a condition in a loop, consuming CPU

Deadlock Two or more processes block each other forever, waiting for resources

Starvation A process waits indefinitely because others keep getting priority

Atomic Operation An operation that executes as a single uninterruptible step

Context Switch OS saves current process state and restores another process to run

Peterson's turn variable Tie-breaking variable that prevents deadlock in 2-process solution

Lamport's Bakery Ticket-based N-process algorithm using (number, PID) pair for ordering

Operating Systems — Process Synchronization | Page 17