PROCESS SYNCHRONIZATION ALGO-

RITHMS FOR GATE CS

Complete Guide - Hindi/Hinglish Comments Edition

1. INTRODUCTION TO PROCESS SYNCHRONIZA-

TION
Process Synchronization Kya Hai?
Process synchronization ek mechanism hai jisko use karke multiple processes ke
execution ko manage kiya jaata hai jo shared resources ko access karte hain,
taaki data consistency maintain rahe aur race conditions avoid ho.

Kyun Zaruri Hai?

• Prevents Race Conditions: Jab multiple processes same data ko simul-
taneously access karte hain
• Ensures Data Consistency: Data ko correct aur consistent rakhta hai
sabhi processes ke across
• Avoids Deadlock: Circular waiting situations ko prevent karta hai
• Fairness: Sabhi processes ko fair access deta hai resources tak

2. SOFTWARE-BASED SOLUTIONS
Ye solutions user mode mein implement hote hain without OS support.

2.1 LOCK VARIABLE MECHANISM

Type: Software-based, Busy Waiting

Algorithm with Hinglish Comments:

// Global shared variable - pura program use kar sakta hai
int lock = 0; // lock = 0 matlab CS vacant hai, lock = 1 matlab CS mein koi hai

// Process ke liye Entry Section

entry_section() {
// Jab tak lock 1 hai (matlab CS occupied hai), tab tak busy wait karo
while(lock != 0); // Agar lock != 0 hai to while loop mein raho, CPU cycle waste karo

// Jab lock 0 ho gaya, to lock ko 1 set karo (apne CS ko occupy kar raha hoon)

1
 lock = 1; // Critical section mein entry le raha hoon, isliye lock = 1
}

// Critical Section - Ye code part sirf ek process chala sakta hai

critical_section() {
// Shared data par operations karo
// Yahan sirf ek process ko hona chahiye
printf("Process %d in critical section\n", process_id);
}

// Exit Section - CS se bahar nikalne ke liye

exit_section() {
// Lock ko 0 set karo taki dusre process entry le sake
lock = 0; // CS ko vacant kiya, dusre process ab enter kar sakte hain
}

// Main Program
main() {
entry_section(); // Entry section ko call karo
critical_section(); // Critical section ko execute karo
exit_section(); // Exit section ko call karo
}

Problem Kya Hai? � Mutual Exclusion Violate Hoti Hai:

Timeline of Disaster:
T1: Process P0 checks: lock = 0 (CS empty hai, main enter kar sakta hoon)
T2: Context switch hota hai (P0 ko bahar nikala)
T3: Process P1 checks: lock = 0 (P1 ko bhi lagta hai CS empty hai)
T4: Context switch (P1 ko bahar nikala)
T5: P0 resume hota hai: lock = 1 set karo (P0 CS mein enter)
T6: P1 resume hota hai: lock = 1 set karo (P1 bhi CS mein enter!)

Result: Dono processes same time CS mein hain = DISASTER!

2.2 STRICT ALTERNATION (TURN VARIABLE)

Type: Software-based, Two-Process Solution

Algorithm with Hinglish Comments:

// Shared variables - dono processes ko access hain
int turn = 0; // 0 = P0 ki turn, 1 = P1 ki turn

// ===== PROCESS P0 KA CODE =====

2
void process_P0() {
while(1) { // Infinite loop - process har baar ye kaam karta hai

// ENTRY SECTION
while(turn != 0) { // Agar turn 0 nahi hai (matlab P1 ki turn hai)
// to tab tak wait karo jab tak P0 ki turn aa jaaye
// Busy waiting - CPU cycle waste ho rahi hai lekin shuddha spin lock
}

// CRITICAL SECTION
// Ab P0 ki turn hai, isliye critical section ko safely execute kar sakte hain
shared_data++; // Shared variable ko increment karo
// Yahan sirf P0 execute hoga (P1 entry_section mein stuck hai)

// EXIT SECTION
turn = 1; // Ab P1 ko turn dedo (P0 ki jaankari P1 ko "Hey, ab teri turn hai")

// REMAINDER SECTION
// Kuch aur kaam karo jo shared data ko affect nahi karta
}
}

// ===== PROCESS P1 KA CODE =====

void process_P1() {
while(1) { // Infinite loop

// ENTRY SECTION
while(turn != 1) { // Agar turn 1 nahi hai (matlab P0 ki turn hai)
// to tab tak wait karo
// Busy waiting
}

// CRITICAL SECTION
shared_data++; // Shared variable ko increment karo
// Ab sirf P1 execute hoga

// EXIT SECTION
turn = 0; // Ab P0 ko turn dedo

// REMAINDER SECTION
}
}

Properties:
• � Mutual Exclusion: Haan, sirf ek ek process CS mein jaata hai

3
 • � Progress: Nahi. Agar P0 CS mein nahi jana chahta but P1 jana chahta,
to P1 kabhi entry nahi le sakta
• � Bounded Waiting: Haan, har process ko ek explicit turn mila

Problem Kya Hai? � Progress Fail:

Example:
- P0 ko CS mein entry nahi chahiye
- P1 ko bhot zaroori hai
- Lekin turn = 0 (P0 ki turn)
- P1 forever `while(turn != 1)` mein stuck rahega
- P0 remainder section mein kuch aur kaam kar raha hai
- CS empty hai lekin P1 enter nahi kar sakta!

2.3 PETERSON’S ALGORITHM

Type: Software-based, Two-Process Solution (Most Important!)

Algorithm with Hinglish Comments:

// Shared variables - dono processes ko access hain
int flag[2]; // flag[0] = P0 interested hai ya nahi, flag[1] = P1 interested hai ya nahi
// flag[i] = true matlab Pi CS mein jana chahta hai
int turn; // turn = 0 matlab P0 ki priority, turn = 1 matlab P1 ki priority

// ===== PROCESS Pi KA CODE (i = 0 ya 1) =====

void process_Pi(int i) {
int j = 1 - i; // j = dusra process, agar i=0 to j=1, agar i=1 to j=0

while(1) { // Infinite loop

// ENTRY SECTION
flag[i] = true; // Apni flag ko true set karo (Haan main interested hoon CS mein)
// Is line se signal karte hain ki "Main entry lena chahta hoon"

turn = j; // Dusre process ko priority dedo

// Ye strategy hai mutual exclusion ensure karne ke liye
// Apne dusre ko turn diya means "Agar both interested hain to tu enter"

// Ab while loop mein wait karo jab tak:

while(flag[j] && turn == j) {
// flag[j] = true matlab dusra process bhi interested hai
// AND turn == j matlab dusre process ki priority hai
// To apne busy wait karo (spin karo)
}

4
 // Jab ye condition false ho jaaye:
// 1. ya to dusra process interested nahi hai (flag[j] = false)
// 2. ya to turn mera ho gaya (turn = i)
// To entry le sakte ho

// CRITICAL SECTION
// Yahan sirf ek process execute hota hai
shared_data++; // Shared resource ko access karo
// Mutual exclusion guaranteed hai!

// EXIT SECTION
flag[i] = false; // Apni flag ko false karo (Main exit ho gaya, ab interested nahi)
// Signal karte hain "Main CS mein nahi jana"

// REMAINDER SECTION
// Kuch aur kaam jo CS se independent hai
}
}

Execution Example (Hinglish):

Scenario: P0 aur P1 dono CS mein entry lena chahte hain

Time P0 P1 Status
---- --- --- ------
1 flag[0]=true flag[1]=true Dono interested
2 turn=1 (P1 ko priority) turn=0 (P0 ko priority)
3 Check: flag[1]&&turn==0? Check: flag[0]&&turn==1?
True && True = Spin! True && False = EXIT!
P0 busy waiting karo P1 enter karta hai!
4 CS mein execute
5 flag[1]=false (exit)
6 Check: flag[1]&&turn==0?
False && True = EXIT!
P0 enters CS!
7 CS mein execute
8 flag[0]=false (exit)

Properties (Sabhi 3 satisfied!):

• � Mutual Exclusion: Haan, sirf ek ek process CS mein jaata hai
• � Progress: Haan, agar dono interested hain to koi ek definitely enter
karega
• � Bounded Waiting: Haan, turn mechanism se fairness hai

5
2.4 DEKKER’S ALGORITHM
Type: Software-based, Two-Process Solution (First Correct Solution!)

Algorithm with Hinglish Comments:

// Shared variables
int flag[2]; // flag[i] = true matlab Pi CS interested hai
int turn; // Whose turn it is

// ===== PROCESS Pi KA CODE =====

void process_Pi(int i) {
int j = 1 - i; // j = dusra process

while(1) {

// ENTRY SECTION
flag[i] = true; // Apna interest declare karo ("Main interested hoon")

// Ab jab tak dusra process interested hai

while(flag[j]) { // Agar dusra process interested hai to...

// Check karo: agar dusre ki turn hai to apne apna interest withdraw karo
if(turn == j) { // Agar dusra process ki priority hai
flag[i] = false; // Apna interest remove karo ("Thik hai, tu ja")

// Ab jab tak dusre ki turn hai, wait karo

while(turn == j) {
// Busy wait - turn se check karte raho
// Jab turn i ho jaaye tab continue karo
}

flag[i] = true; // Dobara apna interest declare karo

}
// Agar meri turn hai to while loop continue karega aur check karega
}

// CRITICAL SECTION
// Yahan sirf main hoon, dusra CS mein nahi hai
shared_data++;

// EXIT SECTION
turn = j; // Ab dusre process ko turn dedo
flag[i] = false; // Apna interest remove karo
}
}

6
Properties (Sabhi 3 satisfied!):
• � Mutual Exclusion: Guaranteed hai
• � Progress: Ensured hai
• � Bounded Waiting: Fairness maintained hai
Historical Significance: Ye pehla correct solution tha critical section problem
ke liye!

2.5 LAMPORT’S BAKERY ALGORITHM

Type: Software-based, N-Process Solution (Generalized!)

Algorithm with Hinglish Comments:

// Shared variables
bool choosing[N]; // choosing[i] = true matlab Pi apna number choose kar raha hai
int number[N]; // number[i] = Pi ka ticket number (jo queue order decide karega)
// Chhoti number = priority (pehle CS mein jaega)

// ===== PROCESS Pi KA CODE =====

void process_Pi(int i) {

while(1) {

// ENTRY SECTION - Bakery mein token lena (jaise real bakery mein)

choosing[i] = true; // Main apna number choose kar raha hoon (ticket le raha hoon)

// Sabhi process ke numbers check karo aur max find karo

int max_num = number[0]; // Pehle number ko max assume karo
for(int j = 1; j < N; j++) { // Baaki sabke numbers dekho
if(number[j] > max_num) { // Agar kisi ka number bada hai
max_num = number[j]; // Usko max banao
}
}
number[i] = max_num + 1; // Apna number = maximum + 1
// Ye ensure karta hai ki sabse unique aur bada number

choosing[i] = false; // Main apna number choose kar chuka hoon

// Ab jab tak mere se pehle wale process ko priority na ho, wait karo
for(int j = 0; j < N; j++) { // Sabhi processes ko check karo
if(j != i) { // Apne alag, dusre processes dekho

// Agar j still choosing kar raha hai to wait karo

7
 while(choosing[j]) {
// j apna number choose kar raha hai, isiliye wait karo
// Jab choosing[j] false ho to proceed karo
}

// Ab check karo: kya j ka priority mera se pehle hai?

// Priority = (number[j], j) < (number[i], i)
// Matlab pehle number dekho, agar same ho to process id dekho
while((number[j] != 0) &&
((number[j] < number[i]) || // Agar j ka number chhota hai
(number[j] == number[i] && j < i))) { // Ya number same hai but j <
// To wait karo - j ka priority zyada hai
// Jab (number[j] == 0) ya j ka priority khatam ho, tab continue
}
}
}

// CRITICAL SECTION
// Ab meri turn hai! Sabhi ka priority check kiya, sabse pehle main hoon
shared_data++;

// EXIT SECTION
number[i] = 0; // Apna ticket number clear karo (queue se bahar niklo)
// (0, i) sabse last priority hai, isliye sab pehle jayenge
}
}

Example (Hinglish):
Scenario: 3 processes P0, P1, P2 hain

Time P0 P1 P2
---- --- --- ---
1 choosing[0]=true choosing[1]=true choosing[2]=true
2 number[0]=5 number[1]=5 number[2]=5
3 choosing[0]=false choosing[1]=false choosing[2]=false
4 Check order:
(5,0) vs (5,1) vs (5,2)
(5,0) < (5,1) < (5,2)
P0 entry le!
5 CS execute Wait... Wait...
6 number[0]=0 (exit) Check redo:
(0,0) vs (5,1) vs (5,2)
(5,1) < (5,2)
P1 entry le!
7 CS execute Wait...

8
8 number[1]=0 (exit) Check redo:
(0,1) vs (0,2)
P2 entry le!
9 CS execute
10 number[2]=0 (exit)

Properties:
• � Works for N processes (unlimited processes possible!)
• � Mutual Exclusion: Guaranteed
• � Progress: Ensured
• � Bounded Waiting: Strong fairness - FCFS order!
• � Fairness: First-Come-First-Serve mechanism

3. HARDWARE-BASED SOLUTIONS
Ye solutions special hardware instructions use karte hain jo atomic hain (ek hi
instruction cycle mein complete hote hain).

3.1 TEST AND SET LOCK (TSL)

Type: Hardware Atomic Instruction

Atomic Instruction with Hinglish Comments:

// Hardware mein ye atomic instruction available hai
// Ye instruction ek hi processor cycle mein complete hota hai
// Context switch beech mein nahi ho sakta

// ATOMIC OPERATION - Ye pura ek hi instruction hai

boolean TestAndSet(boolean *lock) {
boolean old_value = *lock; // Pehle lock ka purana value read karo
// (Jaise lock false tha ya true)

*lock = true; // Ab lock ko true set karo (ACQUIRED state)

// Ye aur upar wali line dono atomic hain

return old_value; // Purana value return karo

// Agar purana false tha to lock was free
// Agar purana true tha to lock was busy
}

// ===== PROCESS USAGE =====

void process_critical_section(int process_id) {

9
 // ENTRY SECTION
while(TestAndSet(&lock)) { // Jab tak lock true aa raha hai
// Matlab lock busy hai, kisi aur process ke pass hai
// Busy wait karo - dobara try karo
// while condition mein:
// TestAndSet(&lock) ko call karo
// - agar lock false tha (free tha) to true set karo aur false return karo
// while(false) = exit loop, ENTRY MILGAYA!
// - agar lock true tha (busy tha) to true rahega aur true return karo
// while(true) = continue loop, busy wait karo
}
// Jab while loop se exit ho, matlab lock acquire ho gaya!
// lock ab true hai aur sirf mera hai

// CRITICAL SECTION
printf("Process %d in CS\n", process_id);
shared_data++;

// EXIT SECTION
lock = false; // Lock ko release karo (false set karo)
// Ab dusra process pick up kar sakta hai
}

Timeline of Execution:
Scenario: P0 aur P1 dono entry le rahe hain

Time P0 P1 Lock
---- --- --- ----
1 TestAndSet(&lock)? TestAndSet(&lock)? false
Returns: false, set to true - true
2 While(false)=Exit! - true
P0 enters CS!
3 CS executing... TestAndSet(&lock)? true
4 Returns: true true
While(true)=Continue
Busy waiting...
5 CS executing... Busy waiting... true
6 CS executing... Busy waiting... true
7 lock = false (exit) Busy waiting... false
8 - TestAndSet(&lock)? false
Returns: false, set to true
While(false)=Exit!
9 - P1 enters CS! true

10
Properties:
• � Mutual Exclusion: Guaranteed by hardware atomicity
• � Works for N processes: Sabhi process queue mein wait kar sakte hain
• � Hardware backed: Atomic operation isliye race condition nahi

3.2 COMPARE AND SWAP (CAS)

Type: Hardware Atomic Instruction (Modern)

Atomic Instruction with Hinglish Comments:

// Modern processors mein ye instruction available hai
// Ye atomic operation bohot powerful hai

// ATOMIC OPERATION - Pura ek hi instruction mein

int CompareAndSwap(int *address, int expected_value, int new_value) {
int old_value = *address; // Address pe jo value hai, read karo

// Ab check karo: kya value hamare expected value ke equal hai?

if(*address == expected_value) { // Agar match hua
*address = new_value; // To new value set karo
}
// Agar match nahi hua to kuch nahi karo, bas return karo

return old_value; // Purana value return karo

// Caller check kar sakta hai ki swap hua ya nahi
}

// ===== PROCESS USAGE =====

void process_critical_section(int process_id) {

// ENTRY SECTION
// Jab tak lock fail na ho jaaye, try karte raho (Retry logic)
while(CompareAndSwap(&lock, 0, 1) != 0) {
// CompareAndSwap call karo:
// - lock check karo, kya 0 hai?
// - agar 0 hai to 1 set karo aur 0 return karo
// while(0 != 0) = while(false) = Exit! ENTRY MILGAYA!
// - agar 0 nahi hai (lock pehle se 1 hai) to kuch mat karo aur 1 return karo
// while(1 != 0) = while(true) = Continue, Retry karo
}
// Jab while se exit ho, matlab lock acquire hua!

// CRITICAL SECTION

11
 printf("Process %d in CS\n", process_id);
shared_data++;

// EXIT SECTION
lock = 0; // Lock reset karo
}

Why CAS is Better than TSL?

TSL:
- Sirf check karo: is lock free?
- Agar free ho to acquire karo
- Lekin "check" aur "acquire" atomically nahi ho sakte

CAS:
- Check karo aur specific value ke liye
- Agar match karo to naya value set karo
- Sab atomic hai, bohot flexible hai
- Lock-free data structures banane mein use hota hai

3.3 SWAP INSTRUCTION

Type: Hardware Atomic Instruction

Atomic Instruction with Hinglish Comments:

// ATOMIC OPERATION - Dono values ko exchange (swap) karo
void Swap(boolean *a, boolean *b) {
boolean temp = *a; // a ki value ko temporary store karo
*a = *b; // b ki value ko a mein daalo
*b = temp; // Temporary value ko b mein daalo
}
// Ye pura atomic instruction hai, beech mein context switch nahi

// ===== PROCESS USAGE =====

void process_critical_section(int process_id) {

boolean key = true; // Local variable - sirf is process ka hai

// ENTRY SECTION
while(key == true) { // Jab tak key true hai
Swap(&lock, &key); // Lock aur key ko swap karo
// Atomic operation se:
// - agar lock false tha to key mein false aa jayega
// aur lock true ho jayega (acquired)

12
 // - agar lock true tha to key true hi rahega
// aur lock true hi rahega (still occupied)
}
// Loop exit means: lock false tha, key mein false aa gaya
// Ab lock true hai = acquired!

// CRITICAL SECTION
printf("Process %d in CS\n", process_id);
shared_data++;

// EXIT SECTION
lock = false; // Lock release karo
}

Timeline of Execution:
Scenario: P0 aur P1 entry le rahe hain

Initially: lock = false, key_P0 = true, key_P1 = true

Time P0 P1 Lock
---- --- --- ----
1 Swap(&lock, &key_P0) - false
lock=true, key_P0=false
while(false)=Exit!
P0 ENTERS!
2 CS executing... Swap(&lock, &key_P1) true
lock=true, key_P1=true
while(true)=Continue
3 CS executing... Swap(&lock, &key_P1) true
lock=true, key_P1=true
while(true)=Continue
(Busy waiting)
4 lock = false (exit) Swap(&lock, &key_P1) false
lock=true, key_P1=false
while(false)=Exit!
5 - P1 ENTERS! true

4. OPERATING SYSTEM BASED SOLUTIONS

4.1 SEMAPHORES
4.1.1 BINARY SEMAPHORE Type: OS Primitive (0 or 1 only)

13
Data Structure with Hinglish Comments:
// Semaphore ko represent karne ke liye
struct BinarySemaphore {
int value; // Value sirf 0 ya 1 ho sakti hai
// 0 = Resource occupied hai
// 1 = Resource available hai
Queue process_queue; // Agar resource nahi mila to yahan queue mein wait karo
};

// Initially semaphore ko 1 se initialize karo

BinarySemaphore mutex;
[Link] = 1; // Resource available hai

wait() Operation with Hinglish Comments:

void wait(BinarySemaphore *S) {
// Atomic operation - beech mein context switch nahi

// Check: kya resource available hai?

if(S->value == 1) {
// Haan, available hai!
S->value = 0; // Resource ko occupy karo (0 set karo)
// Ab koi aur process nahi lega
}
else { // value == 0, matlab resource occupied hai
// Resource available nahi hai
// Process ko sleep karo aur queue mein add karo
add_to_queue(S->process_queue); // Current process ko queue mein daalo
sleep(); // Process ko sleep mode mein daalo (CPU relinquish karo)
// Jab signal hoga tab wake up hoga
}
}

signal() Operation with Hinglish Comments:

void signal(BinarySemaphore *S) {
// Atomic operation - beech mein context switch nahi

// Check: kya queue mein koi process wait kar raha hai?
if(S->process_queue is NOT empty) {
// Haan, queue mein process hain
Process p = remove_from_queue(S->process_queue); // First process ko nikalo
wakeup(p); // Us process ko wake up karo (ready state mein daalo)
// Ab ye process ready queue mein ja jayega
}
else { // Queue empty hai

14
 // Koi process wait nahi kar raha
S->value = 1; // Resource ko available mark karo (1 set karo)
// Agar next process wait() call kare to directly entry lega
}
}

Usage Example with Hinglish Comments:

// Global semaphore
BinarySemaphore mutex = 1; // Initially available

void process_code(int process_id) {

while(1) {
// ENTRY SECTION
wait(mutex); // Resource ke liye request karo
// Agar available ho to acquire karo
// Nahi to sleep karo aur wait karo

// CRITICAL SECTION
// Ab sirf ek process execute karega
printf("Process %d in CS\n", process_id);
shared_data++;

// EXIT SECTION
signal(mutex); // Resource ko release karo
// Queue mein koi wait kar raha hai to wake up karo
// Nahi to [Link] = 1 set karo

// REMAINDER SECTION
do_other_work();
}
}

Key Properties:
• � Mutual Exclusion: Haan, sirf ek process CS mein
• � No Busy Waiting: Process sleep karta hai, CPU waste nahi hota
• � Fair: FIFO queue se fairness maintained

4.1.2 COUNTING SEMAPHORE Type: OS Primitive (0 to N values)

Data Structure with Hinglish Comments:

// Counting semaphore structure
struct CountingSemaphore {

15
 int value; // Koi bhi non-negative integer ho sakti hai
// value = available resources ki count
// Initially = total resources
Queue process_queue; // Wait karne wale processes
};

// Example: 5 identical resources hain

CountingSemaphore resource_pool;
resource_pool.value = 5; // 5 resources available hain

wait() Operation with Hinglish Comments:

void wait(CountingSemaphore *S) {
// Atomic operation

// Pehle value ko decrease karo

S->value--; // Ek resource lena chahta hoon, count ko 1 se kam karo

// Ab check: kya resources negative ho gaye?

if(S->value < 0) {
// Haan, negative hua matlab resources sufficient nahi the
// Current process ko queue mein add karo
add_to_queue(S->process_queue);

// Process ko sleep karo (blocked state)

sleep(); // Wait karo jab tak signal nahi hota
}
// Agar value >= 0 tha to process directly continue karega
// Iska matlab resource available tha
}

signal() Operation with Hinglish Comments:

void signal(CountingSemaphore *S) {
// Atomic operation

// Value ko increase karo (resource return karo)

S->value++; // Ek resource return kar raha hoon

// Check: kya queue mein blocked process hain?

if(S->value <= 0) {
// Haan, S->value <= 0 matlab still queue mein processes hain
// (Negative ka matlab queue mein block ho gaye the)
Process p = remove_from_queue(S->process_queue);
wakeup(p); // Ek blocked process ko wake up karo
}

16
}

Usage Example with Hinglish Comments:

// Global: 3 printers available hain
CountingSemaphore printers = 3;

void process_needs_printer(int process_id) {

while(1) {
do_other_work(); // Kuch aur kaam

// Printer chahiye
wait(printers); // Ek printer request karo
// value 3->2 ho jayega
// Agar value >= 0 to printer mil jayega
// Agar value < 0 to queue mein jaao aur wait karo

// PRINTER USE SECTION

printf("Process %d using printer\n", process_id);
print_data();

// Printer return karo

signal(printers); // Printer release karo
// value 2->3 ho jayega
// Agar queue mein wait kar rahe ho to ek ko wake karo
}
}

Key Differences from Binary:

Binary Semaphore:
- value sirf 0 ya 1
- Ek resource for mutual exclusion
- Like a lock

Counting Semaphore:
- value 0 to N
- Multiple instances of resources
- Resource pool management

Example:
Binary: Ek bathroom - sirf ek person use kar sakta
Counting: 5 bathrooms - 5 persons ek saath use kar sakte

17
4.2 MONITORS
Type: High-level Language Construct

Structure with Hinglish Comments:

// Monitor - High level abstraction
// Ye ek class jaisa hota hai, lekin automatic mutual exclusion milta hai
public class BankAccount {
// Private data - sirf monitor mein access ho sakta hai
private int balance; // Ye shared resource hai

// Condition variables - threads ko synchronize karne ke liye

Condition insufficient_funds; // Agar paise nahi hain to wait karo

// Constructor
public BankAccount(int initial_balance) {
balance = initial_balance;
}

// PROCEDURE 1: Paise nikalna

public synchronized void withdraw(int amount) {
// synchronized keyword = automatic mutual exclusion
// Sirf ek thread ye method ko ek time mein execute kar sakta hai

while(balance < amount) {

// Paise sufficient nahi hain
insufficient_funds.wait(); // Wait karo condition ko
// Jab tak dusra thread deposit nahi kare
}

// Paise sufficient hain, withdraw kar sakte hain

balance = balance - amount; // Paise nikalo

// Jab paise nikalne se baad balance increase ho gaya

// (Ye case nahi hota lekin condition ke liye)
insufficient_funds.signal_all(); // Sabko wake up karo
}

// PROCEDURE 2: Paise deposit karna

public synchronized void deposit(int amount) {
// synchronized keyword = automatic mutual exclusion

balance = balance + amount; // Paise add karo

// Ab paise sufficient ho sakte hain

18
 insufficient_funds.signal(); // Kisi ek ko wake up karo
// Jo paise ka wait kar raha tha
}

// PROCEDURE 3: Balance check karna

public synchronized int get_balance() {
return balance; // Current balance return karo
}
}

// Usage
BankAccount account = new BankAccount(1000);

// Thread 1: 500 withdraw karna

[Link](500); // 1000-500=500, success

// Thread 2: 600 withdraw karna

[Link](600); // 500 < 600, wait karo

// Thread 3: 200 deposit karna

[Link](200); // 500+200=700
// insufficient_funds.signal() call
// Thread 2 ko wake up karo
// Thread 2 ko 600 mil jayega (700-600=100)

Key Features:
• � Automatic Mutual Exclusion: synchronized keyword se
• � High Level: Semaphores se easier
• � Condition Variables: wait(), signal(), signal_all()
• � No Manual Locking: Compiler handle karta hai

4.3 MUTEX LOCKS

Type: Simple Binary Lock

Implementation with Hinglish Comments:

// MUTEX structure
struct Mutex {
boolean locked; // true = locked (unavailable)
// false = unlocked (available)
};

// ACQUIRE operation with Hinglish Comments:

19
void mutex_acquire(Mutex *m) {
// Atomic operation

while(m->locked == true) {
// Mutex locked hai, wait karo
// Busy waiting ya OS se sleep kar sakte ho
}

// Mutex ab free hai

m->locked = true; // Lock kro - aur koi nahi le sakta ab
}

// RELEASE operation with Hinglish Comments:

void mutex_release(Mutex *m) {
m->locked = false; // Unlock - ab dusra process le sakta hai
}

// ===== USAGE =====

Mutex lock;
[Link] = false; // Initially unlocked

void critical_section_code(int process_id) {

// ENTRY SECTION
mutex_acquire(&lock); // Lock acquire karo
// Agar available nahi to wait karo

// CRITICAL SECTION
// Ab sirf ek thread yahan hai
printf("Process %d in CS\n", process_id);
shared_resource++;

// EXIT SECTION
mutex_release(&lock); // Lock release karo
// Ab dusra thread acquire kar sakta hai
}

Difference from Binary Semaphore:

MUTEX:
- Ownership concept hai
- Sirf jo thread mutex acquire kiya vo hi release kar sakta hai
- Simpler, sirf mutual exclusion ke liye
- Deadlock prevention features hote hain modern systems mein

BINARY SEMAPHORE:
- Ownership concept nahi

20
- Koi bhi process signal kar sakta hai
- Flexible, signaling mechanism bhi hai
- General purpose synchronization

5. CLASSICAL SYNCHRONIZATION PROBLEMS

5.1 PRODUCER-CONSUMER PROBLEM (BOUNDED BUFFER)

Description: Producer data generate karte hain, consumer consume karte hain,
buffer limited size ka hai.

Solution with Hinglish Comments:

// SHARED RESOURCES
typedef struct {
int buffer[BUFFER_SIZE]; // Buffer array - data store karne ke liye
int in; // Haan next producer yahan data dalega
int out; // Next consumer yahan se data lega
} BoundedBuffer;

BoundedBuffer b;
[Link] = 0; // Pointer - shuru se start
[Link] = 0; // Pointer - shuru se start

// SEMAPHORES
Semaphore mutex = 1; // Mutual exclusion - buffer ko protect karne ke liye
Semaphore empty = 10; // Empty slots ki count (BUFFER_SIZE = 10)
// Initially 10 slots empty hain
Semaphore full = 0; // Filled slots ki count
// Initially 0 slots filled hain

// ===== PRODUCER CODE =====

void producer() {
while(1) {
int item;

// ITEM PRODUCE KARO

item = produce_item(); // Producer data generate karega

// WAIT FOR EMPTY SLOT

wait(empty); // Check: kya buffer mein empty slot hai?
// empty = 10 -> 9 (ek slot use karega)
// Agar empty = 0 tha (buffer full) to wait karta

21
 // ACQUIRE MUTUAL EXCLUSION
wait(mutex); // Buffer ko exclusively access karne ke liye
// mutex = 1 -> 0
// Ab sirf ye producer buffer access kar sakta hai

// ADD TO BUFFER
[Link][[Link]] = item; // Produced item ko buffer mein add karo
[Link] = ([Link] + 1) % BUFFER_SIZE; // Next position mein ja (circular)

// RELEASE MUTUAL EXCLUSION

signal(mutex); // Buffer ko release karo
// mutex = 0 -> 1
// Ab consumer access kar sakta hai

// SIGNAL FULL
signal(full); // Buffer mein ab ek filled slot add hua
// full = 0 -> 1 (consumer ko signal karo)
}
}

// ===== CONSUMER CODE =====

void consumer() {
while(1) {
// WAIT FOR FILLED SLOT
wait(full); // Check: kya buffer mein filled item hai?
// full = 0 -> ...waiting
// Jab producer signal karega tab wake up

// ACQUIRE MUTUAL EXCLUSION

wait(mutex); // Buffer ko exclusively access karo
// mutex = 1 -> 0

// REMOVE FROM BUFFER

int item = [Link][[Link]]; // Buffer se item nikalo
[Link] = ([Link] + 1) % BUFFER_SIZE; // Next position

// RELEASE MUTUAL EXCLUSION

signal(mutex); // Buffer release karo
// mutex = 0 -> 1

// SIGNAL EMPTY
signal(empty); // Buffer mein ab ek empty slot add hua
// empty ko increment karo
// Agar producer wait kar raha tha to wake up ho jayega

22
 // CONSUME ITEM
consume_item(item); // Item ko use karo
}
}

// ===== EXECUTION TIMELINE (HINGLISH) =====

/*
Scenario: BUFFER_SIZE = 3, initially empty

Time Producer Consumer Semaphores (mutex,empty,full)

---- -------- -------- ----------------------------
1 produce_item()=10 - (1,3,0)
wait(empty): 3->2 -
wait(mutex): 1->0 -
2 buffer[0]=10, in=1 - (0,2,0)
signal(mutex): 0->1 -
signal(full): 0->1 - (1,2,1)
3 - wait(full):2->1 (1,2,0)
wait(mutex):1->0
4 - item=10, out=1 (0,2,0)
signal(mutex):0->1
5 - signal(empty):2->3
consume_item(10) (1,3,1)
6 produce_item()=20 - (1,3,1)
wait(empty): 3->2 -
wait(mutex): 1->0 -
7 buffer[1]=20, in=2 - (0,2,1)
signal(mutex): 0->1 -
signal(full): 1->2 - (1,2,2)
*/

Key Points:
• � 3 Semaphores: mutex (exclusion), empty (slots), full (items)
• � Order Important: empty pehle, phir mutex, phir full
• � Deadlock Prevention: Order aur signaling carefully designed
• � Circular Buffer: (pointer + 1) % SIZE se wrap around

5.2 READERS-WRITERS PROBLEM

Description: Multiple readers can read together, but writer ko exclusive access
chahiye.

READERS PREFERENCE SOLUTION with Hinglish Comments:

23
// SHARED RESOURCES
int read_count = 0; // Kitne readers currently reading hain

// SEMAPHORES
Semaphore write_lock = 1; // Writers ke liye - exclusive access
// agar 1 to writer enter kar sakta
// agar 0 to writer wait karega
Semaphore read_count_lock = 1; // read_count ko protect karne ke liye
// read_count shared resource hai

// ===== READER CODE =====

void reader(int reader_id) {
while(1) {
// ENTRY SECTION

// read_count ko safely access karne ke liye lock lao

wait(read_count_lock); // Pehle read_count ko protect karo
// agar 1 to access kar sakte
// agar 0 to wait karo

read_count++; // Ab ek reader aur add ho gaya

// read_count = 1, 2, 3, ... (kitne readers active hain)

if(read_count == 1) {
// Pehla reader - writers ko block karo
wait(write_lock); // Write_lock acquire karo
// Isse writers block ho jayenge
}

// read_count ko release karo

signal(read_count_lock); // Ab read_count ko release

// READ SECTION
printf("Reader %d is reading\n", reader_id);
read_data(); // Data ko read karo

// EXIT SECTION

// read_count ko safely decrease karne ke liye lock lao

wait(read_count_lock); // read_count ko protect karo

read_count--; // Ek reader kam ho gaya

if(read_count == 0) {
// Aakhri reader - writers ko unblock karo
signal(write_lock); // Write_lock release karo

24
 // Ab writers entry le sakte hain
}

signal(read_count_lock); // read_count ko release

}
}

// ===== WRITER CODE =====

void writer(int writer_id) {
while(1) {
// ENTRY SECTION

// Writer ko exclusive access chahiye

wait(write_lock); // Write lock acquire karo
// Jab koi reader na ho, tab tab acquire hoga
// Readers wait kar rahe hain to writer wait karega

// WRITE SECTION (Exclusive - sirf ye writer)

printf("Writer %d is writing\n", writer_id);
write_data(); // Data ko write karo

// EXIT SECTION

signal(write_lock); // Write lock release karo

// Ab readers ya aur writer proceed kar sakte
}
}

// ===== EXECUTION TIMELINE (HINGLISH) =====

/*
Initially: read_count = 0, write_lock = 1, read_count_lock = 1

Time Event read_count write_lock Status

---- ----- ---------- ---------- ------
1 Reader1 wait(read_count_lock) 0 1 (1,1)
read_count++, if check 1 1
signal(read_count_lock) 1 1 (1,1)
2 Reader1 reading... 1 1 OK
3 Reader2 wait(read_count_lock) 1 1 (1,1)
read_count++ 2 1
if(count==1) nahi -> no wait 2 1
signal(read_count_lock) 2 1 (1,1)
4 Reader2 reading... 2 1 OK
5 Reader1 aur Reader2 dono reading saath mein! (Readers preference)
6 Writer wait(write_lock) 2 1
write_lock = 0 -> wait! 0 (Writers blocked!)

25
 Writer waiting...
7 Reader1 exit:
wait(read_count_lock) 2 0
read_count-- 1 0
if(count==0) nahi 1 0
signal(read_count_lock) 1 0
8 Reader2 exit:
wait(read_count_lock) 1 0
read_count-- 0 0
if(count==0) YES!
signal(write_lock) 0 1 (Writer unblocked!)
signal(read_count_lock) 0 1
9 Writer proceed
write_lock already locked by writer
*/

WRITERS PREFERENCE SOLUTION (Variant):

// Writers ko preference dene ke liye extra mechanism
int read_count = 0;
int write_count = 0; // EXTRA: Kitne writers wait kar rahe hain

Semaphore write_lock = 1;
Semaphore read_lock = 1; // EXTRA: read_count access ke liye
Semaphore read_count_lock = 1;
Semaphore write_count_lock = 1; // EXTRA: write_count ko protect kare

void reader(int reader_id) {

// Check karo: kya koi writer wait kar raha hai?
// Agar ha to reader ko wait karo (Writers ko priority)

while(1) {
wait(read_lock); // EXTRA: Check karo agar writer wait kar raha
wait(read_count_lock);

read_count++;
if(read_count == 1)
wait(write_lock);

signal(read_count_lock);
signal(read_lock);

// READ
read_data();

wait(read_count_lock);

26
 read_count--;
if(read_count == 0)
signal(write_lock);
signal(read_count_lock);
}
}

void writer(int writer_id) {

while(1) {
wait(write_count_lock); // EXTRA
write_count++; // EXTRA: Ek writer aur wait kar raha
if(write_count == 1) // EXTRA: Pehla writer
wait(read_lock); // EXTRA: Readers ko block karo
signal(write_count_lock); // EXTRA

wait(write_lock); // Actual write lock

// WRITE
write_data();

signal(write_lock);

wait(write_count_lock); // EXTRA
write_count--; // EXTRA
if(write_count == 0) // EXTRA: Aakhri writer
signal(read_lock); // EXTRA: Readers ko allow karo
signal(write_count_lock); // EXTRA
}
}

5.3 DINING PHILOSOPHERS PROBLEM

Description: N philosophers, N chopsticks, circular table. Eating needs 2
chopsticks.

BASIC (PROBLEMATIC) SOLUTION with Hinglish Comments:

// SHARED RESOURCES
Semaphore chopstick[5] = {1,1,1,1,1}; // 5 chopsticks, initially available

// ===== PHILOSOPHER i KA CODE =====

void philosopher(int i) {
while(1) {
// THINKING SECTION
think(); // Philosopher soch-vichar kar raha hai

27
 // HUNGRY - Eating ke liye chopsticks chahiye

// Apna left chopstick lo

wait(chopstick[i]); // Apna left chopstick acquire karo
// chopstick[i] acquire hua

// Apna right chopstick lo

wait(chopstick[(i+1) % 5]); // Right chopstick acquire karo
// agar available ho to le lo
// nahi to wait karo

// EATING SECTION
eat(); // Dono chopsticks mein khana kha raha hai

// Chopsticks return karo

signal(chopstick[i]); // Left chopstick release karo
signal(chopstick[(i+1) % 5]); // Right chopstick release karo
}
}

// ===== DEADLOCK SCENARIO (HINGLISH) =====

/*
Maan lo: 5 philosophers hain P0, P1, P2, P3, P4

Time P0 P1 P2 P3 P4
---- --- --- --- --- ---
1 think() think() think() think() think()

2 wait(chop[0]) wait(chop[1]) wait(chop[2]) wait(chop[3]) wait(chop[

Got chop[0]! Got chop[1]! Got chop[2]! Got chop[3]! Got chop[4

3 wait(chop[1]) wait(chop[2]) wait(chop[3]) wait(chop[4]) wait(chop[

WAITING... WAITING... WAITING... WAITING... WAITING...
chop[1] occupied chop[2] occupied chop[3] occupied chop[4] occupied chop[0] oc
by P1 by P2 by P3 by P4 by P0

DEADLOCK!
Sabhi philosophers apna left chopstick pakde hain
Sabhi apna right chopstick ke liye wait kar rahe hain
Circular waiting! Koi bhi proceed nahi kar sakta!
*/

SOLUTION 1: ASYMMETRIC APPROACH (Easiest Fix)

28
// SHARED RESOURCES
Semaphore chopstick[5] = {1,1,1,1,1};

// ===== PHILOSOPHER i KA CODE =====

void philosopher(int i) {
while(1) {
think();

// ASYMMETRIC APPROACH: Odd aur even philosophers different order se le

if(i % 2 == 0) { // Even philosophers (0, 2, 4)

// Pehle left lo, phir right
wait(chopstick[i]); // Left chopstick
wait(chopstick[(i+1) % 5]); // Right chopstick
}
else { // Odd philosophers (1, 3)
// Pehle right lo, phir left (reverse order!)
wait(chopstick[(i+1) % 5]); // Right chopstick (actually pick it first)
wait(chopstick[i]); // Left chopstick
}

// EATING
eat(); // Ab khana kha sakta hai

// Both chopsticks return

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

/*
Timeline:
T1: P0(even) take chop[0] P1(odd) take chop[1]
T2: P0 wait chop[1] - BLOCKED P1 take chop[0]
P1 eat() - P0 wait ho gaya to P1 freely eat kar sakta
T3: P1 release both P0 ab take chop[1], phir chop[0]
T4: P0 eat() P2 start thinking

NO DEADLOCK! (Circular wait break ho gaya)

*/

SOLUTION 2: RESOURCE MANAGER APPROACH

// SHARED RESOURCES
Semaphore chopstick[5] = {1,1,1,1,1};
Semaphore manager = 4; // EXTRA: At most 4 philosophers at table

29
// ===== PHILOSOPHER i KA CODE =====
void philosopher(int i) {
while(1) {
think();

wait(manager); // Manager se permission lo

// manager = 5 -> 4 (5th philosopher ko block karo)
// Max 4 philosophers ek saath

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

eat(); // Ab 5 me se max 4 hain, deadlock nahi possible

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

signal(manager); // Manager ko inform karo ki finished

}
}

SOLUTION 3: ATOMICITY APPROACH

// ===== PHILOSOPHER i KA CODE =====
void philosopher(int i) {
while(1) {
think();

// Both chopsticks atomic way mein le

atomic { // Ye operation indivisible hai
wait(chopstick[i]); // Left
wait(chopstick[(i+1) % 5]); // Right
}
// Agar dono mil gaye to proceed
// Agar koi mil nahi sakta to RELEASE dono aur retry

eat();

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

30
5.4 SLEEPING BARBER PROBLEM
Description: Barber, 1 cutting chair, N waiting chairs.

Solution with Hinglish Comments:

#define CHAIRS 5 // 5 waiting chairs available

// SHARED RESOURCES
int waiting_count = 0; // Kitne customers waiting hain

// SEMAPHORES
Semaphore customers = 0; // Customers ki count (barber ke liye signal)
// 0 = koi customer nahi
// >0 = customers waiting
Semaphore barbers = 0; // Barbers ki count (customer ke liye signal)
// 0 = barber occupied
// 1 = barber free
Semaphore mutex = 1; // waiting_count ko protect karne ke liye

// ===== BARBER CODE =====

void barber() {
while(1) {
// SLEEP KARO JAB TAK CUSTOMER NA AAYE
wait(customers); // Agar customers = 0 to sleep karo
// Customers aane par signal aayega

// CUSTOMER READY KARO

wait(mutex); // waiting_count ko safely access karo
waiting_count--; // Ek customer waiting list se nikalo
signal(barbers); // Signal karo customer ko (tu ready ho!)
signal(mutex);

// HAIRCUT DO
cut_hair(); // Barber apna kaam kar raha hai
}
}

// ===== CUSTOMER CODE =====

void customer() {
wait(mutex); // waiting_count ko safely access karo

if(waiting_count < CHAIRS) { // Agar waiting chairs available hain

waiting_count++; // Waiting list mein add ho jao
signal(customers); // Barber ko signal karo (main aa gaya!)
signal(mutex); // waiting_count ko release karo

31
 wait(barbers); // Barber ke ready hone ka wait karo

// HAIRCUT LELO
get_haircut(); // Apna haircut le raha hai
}
else { // Sab chairs full hain
signal(mutex); // Kuch nahi, just release
leave(); // Saloon se bahar niklo (frustrated!)
}
}

// ===== EXECUTION TIMELINE (HINGLISH) =====

/*
Initially: customers=0, barbers=0, mutex=1, waiting_count=0

Time Barber Customer1 Customer2

---- ------ --------- ---------
1 wait(customers) - -
customers=0->SLEEP! - -

2 SLEEPING... wait(mutex) -
waiting_count++, 1 -
3 - signal(customers) wait(mutex)
signal(mutex) WAIT...
- -
4 Signal wakes barber wait(barbers) -
wait(customers)=WAKE! WAITING... -
waiting_count--=0 - -
5 signal(barbers) GET HAIRCUT! -
signal(mutex) - -

6 - - wait(mutex)
waiting_count++, 1
7 cut_hair()... - signal(customers)
signal(mutex)
8 - - wait(barbers)
-
9 signal(customers)=OK - WAKE UP! GET HAIRCUT!
(No one waiting) - -
GO BACK TO SLEEP! - -

RESULT: Barber efficiently serves customers

No idle time
Customers wait orderly
*/

32
5.5 CIGARETTE SMOKERS PROBLEM
Description: 3 smokers (tobacco, paper, match hain), 1 agent. Agent provides
2 items, smoker with 3rd combines aur smokes.

Challenge:
Main Problem:
- Agent produces 2 random items
- Smoker with 3rd item le sakta hai
- BUT: Smoker agent ko signal nahi kar sakte "kya available hai?"
- Agent sirf signal kar sakta hai, pehle nahi pata ki kya chahiye

Traditional semaphores se solve nahi ho sakta!

Patil ka proof hai.

Solution: Intermediate "Pusher" processes use karne padenge

Solution with Intermediate Pushers:

// SHARED VARIABLES
int agentSem = 1; // Agent active hai
int tobaccoSmokerSem = 0; // Tobacco smoker ready
int paperSmokerSem = 0; // Paper smoker ready
int matchSmokerSem = 0; // Match smoker ready

int tobacco = 0, paper = 0, match = 0; // Available items

// Pushers ke semaphores
int tobaccoPusherSem = 0; // Tobacco+paper ->match smoker
int paperPusherSem = 0; // Tobacco+match ->paper smoker
int matchPusherSem = 0; // Paper+match ->tobacco smoker

// ===== AGENT CODE =====

void agent() {
while(1) {
wait(agentSem); // Agent active ho gaya

// Randomly 2 items select karo

int choice = random() % 3; // 0,1,2 mein se koi

if(choice == 0) { // Tobacco aur Paper

// Semaphore signal karo
signal(tobaccoSem); // Tobacco available
signal(paperSem); // Paper available

33
 signal(tobaccoPusherSem); // Pusher ko inform karo
}
else if(choice == 1) { // Tobacco aur Match
signal(tobaccoSem);
signal(matchSem);
signal(paperPusherSem); // Paper smoker ko pusher call karega
}
else { // Paper aur Match
signal(paperSem);
signal(matchSem);
signal(matchPusherSem); // Match smoker ko pusher call karega
}
}
}

// ===== TOBACCO SMOKER CODE =====

void tobacco_smoker() {
while(1) {
wait(tobaccoSmokerSem); // Tobacco smoker ka turn

// Tobacco already hamare pass hai

// Paper aur match use kar ke cigarette banana
use(tobacco);
use(paper);
use(match);

smoke(); // Smoke kar raha hai

signal(agentSem); // Agent ko ready karo next iteration ke liye

}
}

// ===== PAPER SMOKER CODE =====

void paper_smoker() {
while(1) {
wait(paperSmokerSem);

// Paper already hai, tobacco aur match chahiye

use(paper);
use(tobacco);
use(match);

smoke();

signal(agentSem);
}

34
}

// ===== MATCH SMOKER CODE =====

void match_smoker() {
while(1) {
wait(matchSmokerSem);

// Match already hai, paper aur tobacco chahiye

use(match);
use(tobacco);
use(paper);

smoke();

signal(agentSem);
}
}

// ===== PUSHER PROCESSES (MAGIC!) =====

void tobacco_pusher() { // Tobacco+Paper available -> Match smoker ke liye
while(1) {
wait(tobaccoPusherSem);

wait(tobaccoSem); // Tobacco le lo
wait(paperSem); // Paper le lo

signal(matchSmokerSem); // Match smoker ko call karo!

}
}

void paper_pusher() { // Tobacco+Match available -> Paper smoker ke liye

while(1) {
wait(paperPusherSem);

wait(tobaccoSem); // Tobacco le lo
wait(matchSem); // Match le lo

signal(paperSmokerSem); // Paper smoker ko call karo!

}
}

void match_pusher() { // Paper+Match available -> Tobacco smoker ke liye

while(1) {
wait(matchPusherSem);

wait(paperSem); // Paper le lo

35
 wait(matchSem); // Match le lo

signal(tobaccoSmokerSem); // Tobacco smoker ko call karo!

}
}

// ===== EXECUTION (HINGLISH) =====

/*
Agent produces: Tobacco + Paper

Tobacco_pusher detect: Tobacco + Paper = Match smoker ready!

Match_pusher wait hua, lekin paperPusherSem activate nahi
Tobacco_pusher wait karta: matchSem check (0 hai) -> WAIT

Paper_pusher ko chance: paperPusherSem signal aata?

Nahi, tobaccoPusherSem signal hua

Tobacco_pusher: wait(tobaccoSem) - acquire, wait(paperSem) - acquire

Tobacco_pusher: signal(matchSmokerSem) - MATCH SMOKER WAKE UP!

Match_smoker: wait(matchSmokerSem) - WAKE UP!

Match_smoker: smoke!
Match_smoker: signal(agentSem) - Agent ko ready

Process continues...

Pushers aur smokers ka coordination ensure hota hai!

*/

Key Insight:
Ye problem ka solution hai PUSHERS.
Pushers agent ke behalf mein kaam karte hain.
Woh items combine karte hain aur sahi smoker ko signal karte hain.
Ye mechanism "monitor" approach se bhi kar sakte hain.

6. REQUIREMENTS AND PROPERTIES

Three Critical Requirements (MUST KNOW):
1. MUTUAL EXCLUSION (Most Important!)
// Meaning: Sirf ek process CS mein ek time mein

// Example:
Bank_balance = 1000;

36
// Process P0 aur P1 dono +100 ka transaction karte hain

// WITHOUT Mutual Exclusion:

P0: Read balance = 1000
P1: Read balance = 1000 // P0 ne abhi update nahi kiya
P0: balance = 1000 + 100 = 1100
P1: balance = 1000 + 100 = 1100 // Galat! Ek transaction miss hua
// Result: 1100 instead of 1200 (DISASTER!)

// WITH Mutual Exclusion:

P0: ENTER critical section (lock)
Read balance = 1000
balance = 1100
WRITE
EXIT critical section (unlock)
P1: WAIT for P0 to exit
ENTER critical section
Read balance = 1100
balance = 1200
WRITE
EXIT critical section
// Result: 1200 (CORRECT!)

2. PROGRESS (Livelock Prevention)

// Meaning: Agar koi process CS nahi use kar raha aur koi aur CS mein jane chahta hai
// to decision postpone nahi hona chahiye

// Bad Example (No Progress):

strict_alternation algorithm mein:
- P0 ko CS nahi chahiye, remainder section mein kaam kar raha
- P1 ko CS bohot zaroori hai
- Lekin turn = 0 (P0 ki turn)
- P1 forever wait karega!
- Decision postponed = Lack of Progress

// Good Example (Progress hai):

Peterson algorithm mein:
- P0 ko CS nahi chahiye: flag[0] = false
- P1 ko CS chahiye: flag[1] = true
- P1 check: flag[0] && turn==0? = false && ? = FALSE
- P1 immediately enter kar sakta!
- Decision made = Progress hai

3. BOUNDED WAITING (Fairness/Starvation Prevention)

37
// Meaning: Process indefinite wait nahi karega
// Max X times other processes enter kar sakte hain tab apne turn aayega

// Bad Example (Unbounded Waiting):

Simple TSL (Test-and-Set):
```c
while(TestAndSet(&lock)); // Jab tak nahi mila
P0: waiting for lock P1, P2, P3: … sabhi competing hain P0: hamesha last mein
aata hai (STARVATION!) No upper bound = Unbounded waiting

// Good Example (Bounded Waiting):

Peterson's Algorithm:
- Ek dum dusra process priority le sakta maximum
- turn variable se fairness ensure hoti hai
- Max 1 baar dusra process entry le sakta
- Phir apni turn guaranteed!

7. SUMMARY TABLE
All Algorithms Comparison

Algorithm Type Processes ME Prog BW Busy-wait Best For

Lock Variable SW N � � � � Theory only
Strict Alternation SW 2 � � � � 2 processes
Peterson’s SW 2 � � � � Classic example
Dekker’s SW 2 � � � � Historical
Bakery SW N � � � � General N
TSL HW N � � � � Simple systems
CAS HW N � � � � Lock-free
Semaphore OS N � � � � General purpose
Monitor OS N � � � � High-level
Mutex OS N � � � � Modern threads

8. GATE EXAM TIPS

High Priority Topics (���):
• Peterson’s Algorithm (90% guaranteed)
• Binary + Counting Semaphores
• Producer-Consumer (10 marks easily)
• Readers-Writers variants

38
Medium Priority (��):
• Dining Philosophers
• Dekker’s Algorithm
• Hardware solutions (TSL, CAS)
• Monitors

Low Priority (�):

• Lock Variable
• Strict Alternation
• Bakery Algorithm
• Sleeping Barber
• Cigarette Smokers

9. QUICK REVISION SUMMARY

One-Liners (Agar exam mein time kam rahe):
1. Peterson’s: flag declaration + priority dusre ko + dono check = Perfect!
2. Semaphore: wait() decreases, signal() increases, queue mein sleep karo
3. Producer-Consumer: 3 sems (mutex, empty, full), order matter karta
hai
4. Readers-Writers: Multiple readers OK, but writers exclusive
5. Dining Philosophers: Asymmetric order se deadlock avoid
6. Sleeping Barber: Manager semaphore se bounded waiting
7. TSL/CAS: Atomic hardware operations, busy-wait but simple
8. Monitors: Automatic ME, clean code, easy to understand

Must Remember Formulas:

// Producer-Consumer
Circular buffer: (pointer + 1) % SIZE

// Dining Philosophers
Right chopstick: (i + 1) % N

// Lexicographic ordering (Bakery):

(number[i], i) < (number[j], j)
Pehle number dekho, same ho to process ID dekho

END OF DOCUMENT
Remember: Concepts samjhna zaroori hai, formulas yaad karna nahi. Har
algorithm ke “kyun?” ko samjho.

39
Good Luck for GATE 2026! �

Document with Complete Hinglish Comments Every Line Explained All Algo-
rithms Covered Last Updated: November 2025

40