BCS-401 · AKTU · Unit II

OS Unit-2: Concurrent Processes

Complete Notes · Mind Maps · Key Concepts · Pseudocode · PYQs

3 Producer-Consu 5 Dekker &

1 Process Concept 2 Concurrency mer 4 Mutual Exclusion Peterson 6 Semaphores

8 Dining 11 Process
7 Test & Set Philosophers 9 Sleeping Barber 10 IPC Models Generation

1. Process Concept

● Definition: A process is a program in execution — an active entity that includes code, current activity (PC +
registers), and resources (memory, files).

● Program vs Process: Program = passive file on disk; Process = active entity in RAM with states, PID, and
lifetime only during execution.

● Process Address Space: TEXT (compiled code) → DATA (global/static vars) → HEAP (dynamic alloc, grows
up) → STACK (local vars, grows down).

Process States & Transitions

New → admit → Ready → dispatch → Running → exit → Terminated

Transition Meaning

New → Ready Process admitted into memory (admit)

Ready → Running CPU assigned by scheduler (dispatch)

Running → Ready Time slice expired or preemption (interrupt)

Running → Blocked Process waits for I/O or event

Blocked → Ready I/O / event completes

Running → Terminated Process finishes or is killed (exit)

Process Control Block (PCB)

Page 1 · OS Unit-2 Concurrent Processes · BCS-401 AKTU

 Process ID (PID) Process State Program Counter

Unique integer identifier — like a roll Current condition: New / Ready / Address of next instruction to
number assigned by OS Running / Blocked / Terminated execute when resumed

Registers Memory Limits Open Files / I/O

CPU register values saved at the Page tables, segment tables, List of open file descriptors and
moment of context switch memory bounds for this process assigned I/O devices

Context Switching: Saving old process PCB state + loading new process PCB state. Enables concurrency
illusion on single CPU. Pure overhead — no useful work done during switch.

AK ◆ Explain process concept with states and state transition diagram. (2024-25 Sec B 7M)
TU
PY ◆ Explain structure and contents of a Process Control Block (PCB). (2023-24 Sec B 7M)
Qs
◆ Define process and PCB. Describe state transition diagram in detail. (2022-23 Sec B 10M)

◆ What is the difference between a process and a program? (2024-25 Sec A 2M)

2. Principle of Concurrency

● Definition: Concurrency is execution of multiple processes in overlapping time periods via interleaving (1
CPU) or parallelism (multi-CPU).

● Interleaving: Single CPU switches between processes so fast the user perceives simultaneity — achieved via
Context Switching.

● Parallelism: Multiple CPU cores physically execute different processes at the exact same instant — true
simultaneous execution.

● Race Condition: Final outcome depends on execution order — e.g. two ATMs both read ■1000 balance, both
approve ■800 withdrawal, account goes negative.

Feature Interleaving (Concurrency) Parallelism

CPU Count 1 CPU core Multiple CPU cores

Logic Tasks overlap in time (fast switching) Tasks run at same physical instant

Mechanism Context Switching Hardware multiple cores

Example Music + typing on single-core PC Multi-core server processing requests

Goals of Concurrency
Problems Caused
CPU utilization · Faster throughput via I/O overlap ·
Fairness (every process gets CPU time) · Modularity of Race Conditions · Deadlock · Starvation · Data
system design inconsistency · Increased complexity

Page 2 · OS Unit-2 Concurrent Processes · BCS-401 AKTU

AK ◆ Explain the challenges of achieving mutual exclusion in concurrent programming. (2023-24 Sec B 7M)
TU
PY
Qs

3. Producer / Consumer Problem (Bounded Buffer)

● Definition: Classical sync problem — Producer generates data into a fixed-size shared buffer; Consumer
removes it. Both run concurrently.

● 3 Challenges: (1) Mutual Exclusion — only 1 process accesses buffer at a time. (2) Overflow — producer
blocked when buffer full. (3) Underflow — consumer blocked when buffer empty.

mutex = 1 empty = N full = 0

Binary semaphore — locks buffer Counting semaphore — tracks Counting semaphore — tracks filled
for mutual exclusion during available empty slots (initially = slots (initially 0 = buffer starts
add/remove buffer size N) empty)

PRODUCER CONSUMER

do { do {
wait(empty); // check empty slot available wait(full); // check data exists
wait(mutex); // lock buffer — enter CS wait(mutex); // lock buffer — enter CS
// add item to buffer // remove item from buffer
signal(mutex); // unlock — exit CS signal(mutex); // unlock — exit CS
signal(full); // signal filled slot signal(empty); // signal empty slot
} while(TRUE); } while(TRUE);

● Deadlock Risk: If wait(mutex) is called BEFORE wait(empty) — producer locks buffer then waits for empty
slot that consumer can never free because the buffer is locked. Both block forever.

AK ◆ Explain producer-consumer problem and its solution using semaphore. (2022-23 Sec C 10M)
TU
PY ◆ Buffer size=4, Producer produces 6, Consumer consumes 3 — items in buffer at end = 3. (2024-25 Sec A 2M)
Qs

4. Mutual Exclusion & Critical Section Problem

● Critical Section (CS): A code segment where a process accesses/modifies shared resources (variables, files,
tables). Only 1 process may execute CS at a time.

● Mutual Exclusion: If process Pi is in CS, no other Pj can execute in its CS simultaneously — prevents race
conditions.

3 Mandatory Requirements for a Valid CS Solution

Page 3 · OS Unit-2 Concurrent Processes · BCS-401 AKTU

 1. Mutual Exclusion 2. Progress 3. Bounded Waiting

If Pi is in CS, no other process can If CS is free and processes want in, Limit on times others enter CS after
be in CS simultaneously — absolute decision on next process cannot be a request is made — prevents
requirement postponed indefinitely starvation of any process

Process Structure with CS Protocol

Entry Section Critical Section Exit Section Remainder

Request lock Access shared data Release lock Non-critical code

● Without CS management: Two simultaneous ATM withdrawals on same account may both see ■1000, both
approve ■800 → balance becomes -■600 (race condition).

● Limitation: Performance overhead from waiting; incorrect implementation leads to deadlocks where two
processes wait for each other forever.

AK ◆ Explain in detail about Mutual Exclusion and Critical Section Problem. (2021-22 Sec B 10M)
TU
PY ◆ Define Critical Section Problem and list the conditions a solution must satisfy. (2024-25 Sec C 7M)
Qs

5. Dekker's & Peterson's Solution

● Purpose: Software-based algorithms to solve Critical Section Problem for 2 processes without special
hardware support.

Peterson's Algorithm (Cleaner Approach)

● Uses: boolean flag[ ] (interest flag) + int turn (whose turn variable).
● Logic for Pi: (1) Set flag[i]=TRUE (interested); (2) Set turn=j (yield); (3) Busy-wait while flag[j] AND turn==j; (4)
Enter CS; (5) Set flag[i]=FALSE on exit.

// Process i
flag[i] = TRUE; // I want to enter
turn = j; // But you go first if you want
while(flag[j] && turn == j); // Busy wait
/* CRITICAL SECTION */
flag[i] = FALSE; // I am done

Dekker's Algorithm (First Known Correct Solution)

● Historically first correct 2-process mutual exclusion algorithm — more complex, uses nested conditional
checks to resolve simultaneous flag assertions.

Feature Peterson's Dekker's

Simplicity Short, elegant code Complex nested logic

Page 4 · OS Unit-2 Concurrent Processes · BCS-401 AKTU

 Efficiency More efficient Slightly more overhead

Process count 2 processes only 2 processes only

Modern hardware May fail (instruction reordering) May fail (memory visibility)

Busy waiting Yes — wastes CPU cycles Yes — wastes CPU cycles

AK ◆ Compare and contrast Dekker's and Peterson's algorithms. (2023-24 Sec C 7M)
TU
PY ◆ Discuss limitations of Dekker's and Peterson's on modern multiprocessors. (2024-25 Sec C 7M)
Qs

6. Semaphores

● Definition: Integer variable S accessed ONLY via two atomic operations: wait(S) and signal(S) — apart from
initialization.

● Atomicity = the entire read-modify-write is uninterruptible — prevents race condition on the semaphore
variable itself.

WAIT (P / Down / Proberen) SIGNAL (V / Up / Verhogen)

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

Aspect Binary Semaphore (Mutex) Counting Semaphore

Values 0 and 1 only Any non-negative integer

Purpose Mutual exclusion — acts as a lock Manage N instances of a resource

Example Lock a single printer Manage a pool of 5 printers

Init value 1 (unlocked) N (number of resources)

● Deadlock scenario: P1 holds S1, waits for S2. P2 holds S2, waits for S1. → Circular wait → neither can
proceed → system hangs forever.

● Busy Waiting: Process loops in while(S<=0) wasting CPU. Solution: block the process (OS sleep/wake), add
to waiting queue — this is the blocking semaphore.

AK ◆ Define semaphore and its types. (2022-23 Sec A 2M)

TU
PY ◆ S1=S2=1; P1: wait(S1),wait(S2); P2: wait(S2),wait(S1) — explain deadlock sequence. (2024-25 Sec C 7M)
Qs

7. Test and Set Operation

Page 5 · OS Unit-2 Concurrent Processes · BCS-401 AKTU

● Definition: An atomic hardware instruction — reads lock value, sets it to TRUE, returns old value — all in
ONE uninterruptible CPU cycle.

● Return 0 (false): Lock was free → process gets lock and enters CS. Return 1 (true): Lock busy → process
busy-waits in loop.

Usage in Process
TestAndSet Instruction
do {
boolean TestAndSet(boolean *target) { // Entry:
boolean r = *target; // 1. Read while(TestAndSet(&lock;)); // busy wait
*target = TRUE; // 2. Set /* CRITICAL SECTION */
return r; // 3. Return old value lock = FALSE; // exit
} } while(TRUE);

Advantages Limitations

Simple to implement — easy basic lock Busy waiting wastes CPU cycles

Works on multiprocessor systems Starvation possible — some process may wait indefinitely

Guarantees mutual exclusion Priority inversion / deadlock risk possible

AK ◆ Define the term busy waiting. (2022-23 Sec A 2M)

TU
PY ◆ Discuss mutual-exclusion implementation with test-and-set instruction. (2017-18 7M)
Qs

8A. Dining Philosophers Problem (Classical)

● Definition: 5 philosophers sit at a round table with 5 chopsticks between them. Each needs LEFT + RIGHT
chopstick to eat — models multi-resource allocation.

● Lifecycle: Thinking → Hungry (wants left chopstick) → picks left → picks right → Eating → puts both down →
Thinking again.

● Deadlock Scenario: All 5 simultaneously pick their LEFT chopstick → each waits for right (held by neighbor)
→ circular wait → system frozen forever.

// chopstick[5] semaphores, all initialized to 1

do {
wait(chopstick[i]); // pick up LEFT chopstick
wait(chopstick[(i+1) % 5]); // pick up RIGHT chopstick
/* EATING SECTION */
signal(chopstick[i]); // put down LEFT
signal(chopstick[(i+1) % 5]); // put down RIGHT
/* THINKING SECTION */
} while(TRUE);

● Common exam mistake: Writing i+1 instead of (i+1) % 5 for right chopstick — causes error for philosopher 4
(index out of bounds).

Page 6 · OS Unit-2 Concurrent Processes · BCS-401 AKTU

● Deadlock prevention strategies: (1) Allow only 4 philosophers to sit at once. (2) Pick BOTH chopsticks
atomically. (3) One philosopher picks right first (asymmetric solution).

AK ◆ Explain in detail about the Dining Philosopher Problem. (2021-22 Sec C 10M)
TU
PY ◆ Explain dining philosopher problem and its solution using semaphore. (2022-23 Sec C 10M)
Qs

8B. Sleeping Barber Problem (Classical)

● Setup: 1 barber + 1 barber chair + N waiting chairs. Barber sleeps when no customers; customer wakes
barber or waits or leaves if all chairs full.

● Models: Single service provider (CPU/printer) with limited request queue — models OS scheduling/buffering
behavior.

customers = 0 barber = 0
mutex = 1
Barber sleeps when 0. Incremented Customer waits when 0. Signaled
when customer arrives to wake by barber when ready for next Binary semaphore protecting the
barber. customer. "waiting" counter variable from race.

BARBER CODE CUSTOMER CODE

while(TRUE) { wait(mutex); // lock

wait(customers); // sleep if none if(waiting < n) { // chair free?
wait(mutex); // lock chair count waiting++;
waiting--; signal(customers); // wake barber
signal(barber); // ready to cut signal(mutex);
signal(mutex); // release lock wait(barber); // wait for service
cut_hair(); get_haircut();
} } else signal(mutex); // leave

Limitation
Advantage
Hypothetical model. Real OS has thousands of
No two customers try to take the same chair. Barber only processes — managing N chairs becomes complex.
works when customers exist — efficient resource use. Risk of starvation.

9. Inter Process Communication (IPC) Models & Schemes

● Definition: IPC = OS mechanism allowing cooperating processes to communicate and synchronize.

Cooperating processes can affect or be affected by other executing processes.

● Why needed: Information sharing · Computation speedup (parallel subtasks) · Modularity · Convenience
(multitasking applications like editors, browsers).

Page 7 · OS Unit-2 Concurrent Processes · BCS-401 AKTU

 Model 1: Shared Memory Model 2: Message Passing

Processes establish a shared memory region. They Processes communicate via send(message) /
exchange data by reading/writing to it directly. OS only receive(message) through OS kernel. No shared
involved at setup. FAST — memory speed. Manual memory needed. OS handles synchronization. Slower
synchronization required (semaphores). Best for large (kernel overhead). Best for small data or distributed
data, same machine. systems (different computers).

Feature Shared Memory Message Passing

Mechanism Shared region in RAM Messages via OS kernel

Speed Faster (memory access) Slower (kernel overhead)

Synchronization Manual — programmer uses Automatic — handled by OS

semaphores

Implementation Complex for programmer Easier to implement

Suitability Large data, same machine Small data / distributed systems

Communication type Direct read/write Direct (name) or Indirect

(mailbox/port)

Blocking Not applicable Blocking (sync) or Non-blocking

(async)

AK ◆ Explain in detail about IPC models and schemes. (2021-22 Sec C 10M) — Both diagrams required.
TU
PY ◆ Keywords: cooperating processes, shared memory, message passing, direct/indirect, blocking/non-blocking.
Qs

10. Process Generation

● Definition: Process Generation (Process Creation) — a running parent process creates new child
processes via OS system calls (fork() in UNIX).

● fork() return values: Returns 0 in child, returns child PID in parent, returns negative on error. Child gets
duplicate of parent address space.
3
● 3 forks rule: fork(); fork(); fork() → 2 = 8 total processes (including original) — each fork doubles the
existing process count.

● Orphan Process: Child continues after parent terminates — adopted by init/systemd (PID 1). Zombie
Process: Child finishes but parent has not called wait() yet.

Page 8 · OS Unit-2 Concurrent Processes · BCS-401 AKTU

 pid = fork(); // OS creates child process
if(pid < 0) { // fork failed
/* handle error */
}
else if(pid == 0) { // CHILD process code
printf("I am the child process.");
} else { // PARENT process code
printf("My child PID = %d", pid);
}

Why: Multitasking
Why: Parallelism Why: Modularity
Open web browser while editor runs
— each app is a child of shell Break large computation into Chrome creates separate child
process parallel child sub-tasks for speedup process per tab — crash isolation

Advantages Limitations

Efficient multitasking · Crash isolation (one child fails, Process creation + context switching = memory and
others survive) · System modularity · Parallel CPU overhead · Orphan/zombie process management
computation needed · Resource limits

AK ◆ fork(); fork(); fork(); — how many total processes? Answer: 8. (2024-25 Sec A 2M)
TU
PY ◆ Name one piece of process identification information — Answer: PID. (2023-24 Sec A 2M)
Qs

Master Revision — AKTU High-Frequency PYQ Tracker

Focus on these for maximum marks

10 Producer-Consumer semaphore solution (2022-23 C) · Dining Philosophers + semaphore code (2021-22 C,

marks 2022-23 C) · IPC both models with diagrams (2021-22 C) · Mutual Exclusion + Critical Section (2021-22 B)

7 Process concept + state diagram + PCB (2023-24 B, 2024-25 B) · Dekker's vs Peterson's compare
marks (2023-24 C) · Critical Section 3 conditions (2024-25 C) · Semaphore deadlock scenario S1+S2 (2024-25 C)
· Limitations on multiprocessors (2024-25 C)

2 3×fork() = 8 processes (2024-25 A) · Define process state (2023-24 A) · PID as identification info (2023-24
marks A) · Program vs process difference (2024-25 A) · Define busy waiting (2022-23 A) · Semaphore types
(2022-23 A)

Notes compiled from Bitwise Learning — BCS-401 OS Unit-2 · All topics as per AKTU syllabus

Page 9 · OS Unit-2 Concurrent Processes · BCS-401 AKTU