Critical Section Problem

The critical section problem arises in concurrent programming when multiple processes access shared resources. A
correct solution must satisfy: Mutual Exclusion, Progress, Bounded Waiting

Peterson’s Solution for critical section problem

Peterson’s solution is a classical software-based synchronization technique that guarantees all three conditions for
two processes only.

Variables: boolean flag[2]; // flag[i] and flag[j]

int turn; // indicates whose turn it is (i or j)

Note: flag[i] = true → Process 𝑃𝑖 wants to enter the critical section, turn = j → Give priority to process 𝑃𝑗

Process 𝑃𝑖 Process 𝑃𝑗
do { do {
flag[i] = true; // express interest flag[j] = true; // express interest
turn = j; // give chance to Pj turn = i; // give chance to Pi

while (flag[j] == true && turn == j) ; // busy while (flag[i] == true && turn == i) ; // busy waiting
waiting
// Critical Section
// Critical Section
flag[j] = false; // exit section
flag[i] = false; // exit section
// Remainder Section
// Remainder Section
} while (true);
} while (true);

• Each process indicates its desire to enter the critical section using its flag.
• The variable turn resolves conflict when both processes attempt to enter simultaneously.
• If both flags are true, the process whose turn is not selected will wait.
• This ensures orderly and fair access to the shared resource.

Peterson’s Solution satisfy:

1. Mutual Exclusion

Both processes cannot enter the critical section at the same time because: If both flags are true, only one process will
satisfy the while condition and proceed. The other process will remain in the waiting loop.

2. Progress: If no process is in the critical section, one of the processes that wants to enter will be allowed. The
decision depends only on the values of flag and turn, not on unrelated processes.

3. Bounded Waiting: Each process gets a fair chance. Once a process expresses interest, the other process cannot
repeatedly bypass it. The turn variable ensures alternation, preventing starvation.

Limitations:

a) Works only for two processes

b) Uses busy waiting (CPU cycles are wasted)
c) Not suitable for modern multi-core systems due to memory consistency issues
 Test and Set Lock

Test-and-Set is a hardware-supported atomic operation used to implement mutual exclusion. It checks the value of a
variable and sets it to true in a single indivisible step.

Shared variable: boolean lock = false; // initially free

Test and Set Instruction Process Structure:

boolean test_and_set (boolean *target)
do {
{
while (test_and_set(&lock)) ; // busy waiting (spin)
boolean rv = *target;
*target = true; // Critical Section
return rv; lock = false; // release lock
} // Remainder Section
} while (true);

How It Works

Initially, lock = false

A process calls test_and_set(&lock):
If lock = false →
rv = false, lock becomes true
Loop condition fails → process enters CS
If lock = true →
rv = true, loop continues → process waits
When the process exits CS:
It sets lock = false
Another waiting process can now enter

How It Solves Critical Section Problem

Mutual Exclusion: Only one process can successfully set lock from false to true. Others remain in the waiting loop.
Hence, only one process enters the critical section

Progress: If the lock is free, a process can immediately enter, decision depends only on the processes attempting
entry

Bounded Waiting: Not guaranteed and some processes may suffer starvation if others repeatedly acquire the lock

Important Concept:

Busy Waiting

• Processes continuously execute test_and_set()

• This is called spinlock

• Leads to CPU wastage, especially for long waiting times

Limitation: Busy waiting , No fairness (possible starvation) , Not efficient for long critical sections
 Compare and Swap

Compare-and-Swap (CAS) is a hardware atomic instruction used in synchronization.

It compares the value of a memory location with an expected value and swaps (updates) it with a new value only if
they match.
Shared Variable: int lock = 0; // 0 = free, 1 = busy

Compare and Swap Instruction Process Structure:

int compare_and_swap(int *value, int do {
expected, int new_value)
while (compare_and_swap(&lock, 0, 1) != 0) ;
{
int temp = *value; // busy waiting
//Critical Section
if (*value == expected) lock = 0; // release lock
*value = new_value;
// Remainder Section
return temp; } while (true);
}

How it works: How It Solves Critical Section Problem

Initially, lock = 0 (free)
1. Mutual Exclusion:
A process executes:
Only one process can successfully change lock from 0 → 1. So only
compare_and_swap(&lock, 0, 1)
one process enters the critical section
If lock == 0
→ condition true 2. Progress: If lock is free, a process enters immediately.
No unnecessary delay
→ lock becomes 1
3. Bounded Waiting: Not guaranteed. Some processes may
→ returns 0
repeatedly fail → starvation possible
→ process enters critical section
If lock == 1
→ condition false
→ no change
→ returns 1
→ process keeps waiting
When the process finishes:
lock = 0;
→ lock becomes free for others

Note:
Busy Waiting: Processes continuously retry CAS in a loop
This is called spinlock. Leads to CPU wastage
Limitations:
Busy waiting.
No fairness guarantee
Starvation possible
 Mutex Lock

A Mutex Lock (Mutual Exclusion Lock) is a synchronization mechanism used to control access to a critical
section in concurrent systems. It ensures that only one process or thread can access a shared resource at a time,
preventing race conditions.

A mutex is a binary lock variable that has only two states:

• 0 (unlocked / free)

• 1 (locked / busy)

A process must acquire the lock before entering the critical section and release it after execution.

Basic Operations:

1. Acquire (lock): How Mutex Lock Works:

acquire() { Initially, lock = 0 (free)
while (lock == 1)
A process calls acquire():
; // busy waiting
lock = 1; If lock = 0 → it sets lock = 1 and enters CS
} If lock = 1 → it keeps waiting (busy waiting)
2. Release(lock) After completing the critical section:
release() { The process calls release()
lock = 0; lock becomes 0
} Another waiting process can now acquire the lock

Process Structure Using Mutex:

do {
acquire();

// Critical Section

release();

// Remainder Section

} while (true);

How Mutex Solves Critical Section Problem

Mutual Exclusion: Only one process can hold the lock at a time. Prevents simultaneous access to the critical section
Progress: If no process is in the critical section, a waiting process can acquire the lock immediately. Decision depends
only on competing processes
Bounded Waiting: Not guaranteed in basic mutex (spinlock). Some processes may suffer starvation
However, advanced mutex implementations (with queues) can ensure bounded waiting.
Types of Mutex Locks
1. Spinlock (Busy Waiting Mutex): Processes continuously check the lock. Suitable for short critical sections
2. Blocking Mutex: Waiting processes are put to sleep. That’s why CPU is not wasted. Used in modern operating
systems
 Semaphore
A semaphore is a fundamental synchronization mechanism used in operating systems to control access to shared
resources in concurrent environments. It helps prevent race conditions and provides a structured way to solve the
critical section problem.
A semaphore is an integer variable that is accessed only through two atomic operations:

• wait(S) → also called P operation

• signal(S) → also called V operation

These operations are atomic, meaning they execute without interruption, ensuring correct synchronization.
Types of Semaphore
1. Counting Semaphore

• Can take any non-negative integer value (0, 1, 2, …)

• Used when multiple instances of a resource are available

• Example: managing access to a pool of printers

2. Binary Semaphore

• Value is only 0 or 1

• Used for mutual exclusion (similar to a mutex lock)

Operations on Semaphore:

Wait (S): Signal(S)

wait(S) { signal(S) {
while (S <= 0); S++;
S--;
}
}
Process Structure Using Semaphore:
How Semaphore Works
Do{ 1. Semaphore is initialized:
wait(S); o S = 1 → for mutual exclusion (binary
semaphore)
// Critical Section o S = n → for n identical resources
2. When a process calls wait(S):
signal(S); o If S > 0 → it decrements S and enters CS
} while(true); o If S ≤ 0 → process is blocked and placed in a
queue
3. When a process calls signal(S):
o S is incremented
o One waiting process is awakened
How Semaphore Solves Critical Section Problem
Mutual Exclusion: With S = 1, only one process can enter the critical section at a time
Progress: If the critical section is free, a waiting process is selected and allowed to enter
Bounded Waiting: Maintained using a queue of waiting processes (FIFO). It ensures no process waits indefinitely
Advantages

• Can handle multiple resources (counting semaphore)

• Avoids busy waiting (in blocking implementation)
• Ensures all three conditions of critical section problem
Disadvantages

• Complex to implement correctly

• Risk of: Deadlock (improper ordering) . Starvation (if queue discipline not fair)
• Harder to debug compared to mutex locks
Applications

• Process synchronization
• Resource allocation (e.g., printers, memory buffers)
• Producer–Consumer problem

Semaphore is a powerful synchronization tool that ensures mutual exclusion, progress, and bounded waiting
when properly implemented. It is widely used in operating systems for managing shared resources and coordinating
concurrent processes, although it requires careful handling to avoid errors like deadlock and starvation.