Process Synchronization

Process Synchronization

Deadlock Handling

Round Robin

Process Scheduling and Synchronization

Critical Section Problem

Process Synchronization is a technique used to coordinate multiple processes so they can safely share resources (like memory, files, variables) without causing errors or inconsistencies.

Critical Section Problem (Operating Systems)

The Critical Section Problem is about designing a protocol so that multiple processes can safely access shared resources (like variables, files, memory) without causing errors.

The Critical Section Problem is a fundamental concept in Operating Systems that deals with how multiple processes can safely share resources without causing errors.

What is a Critical Section?

A critical section is the part of a process where it accesses shared data.

A critical section is the part of a program where a process accesses shared data/resources (like variables, files, memory).

Structure of a Process:

while(true) {
   Entry Section      // request access
   Critical Section   // access shared resource
   Exit Section       // release resource
   Remainder Section  // other work
}

The Problem

When multiple processes enter their critical sections at the same time, it can lead to:

Race Condition

Incorrect results

Data inconsistency

Example

Shared variable: count = 5

Process P1: count++
Process P2: count--

If both execute simultaneously, final value may be wrong (not 5).

Requirements (Solution Conditions)

To solve the critical section problem, a solution must satisfy:

1. Mutual Exclusion

Only one process at a time can execute in the critical section

2. Progress

If no process is in the critical section,

One of the waiting processes should be allowed to enter

Decision should not be delayed indefinitely

3. Bounded Waiting

A process should not wait forever

There must be a limit on how many times others can enter before it

Solutions to Critical Section Problem

1. Software Solutions

Peterson’s Algorithm (for 2 processes)

Uses shared variables like flag and turn

Ensures mutual exclusion without hardware

2. Hardware Solutions

Test-and-Set instruction

Compare-and-Swap

These provide atomic operations.

3. High-Level Solutions

Mutex (Lock)

lock()
critical section
unlock()

Semaphore

wait(S)
critical section
signal(S)

Monitor

High-level construct (used in Java, etc.)

Automatically handles synchronization

Key Issues

Busy Waiting (wastes CPU time)

Deadlock (processes wait forever)

Starvation (some processes never get access)

 

Summary

Critical section problem ensures safe access to shared resources

Prevents race conditions

Requires:

Mutual Exclusion

Progress

Bounded Waiting

Solved using algorithms, hardware instructions, and synchronization tools

 

Critical Section Problem – Example 2

Let’s understand the Critical Section Problem with a simple and clear example.

Example: Shared Bank Account 💰

Assume two processes are accessing the same bank account balance.

Initial Balance = 1000

Process P1 (Deposit ₹500)

read balance (1000)
balance = balance + 500  → 1500
write balance (1500)

Process P2 (Withdraw ₹300)

read balance (1000)
balance = balance - 300 → 700
write balance (700)

What Goes Wrong? (Race Condition)

If both processes execute at the same time, this may happen:

1.                      P1 reads balance = 1000

2.                      P2 reads balance = 1000

3.                      P1 writes 1500

4.                      P2 writes 700

Final Balance = 700 (WRONG ❌)
Correct answer should be 1200 (✔)

Where is the Critical Section?

The critical section is where the shared variable (balance) is accessed:

read balance
modify balance
write balance

Both processes execute this part → conflict occurs.

Solution Using Mutual Exclusion

We ensure only one process at a time accesses the balance.

Using Mutex Lock

lock()
read balance
modify balance
write balance
unlock()

Correct Execution (After Fix)

1.                      P1 enters → updates balance to 1500 → exits

2.                      P2 enters → updates balance to 1200 → exits

Final Balance = 1200 (Correct ✔)

Key Takeaways

• Critical section = code accessing shared data
• Problem occurs due to simultaneous access
• Leads to race condition
• Solution: Mutual Exclusion (locks, semaphores, etc.)

 

Another Quick Example (Counter)

count = 0

P1: count++
P2: count++

Expected result = 2
But due to race condition → result may be 1

 

 

Classical Synchronization Problems

Described by Dutch computer scientist Edsger W. Dijkstra in mid 1960.

(Producer-Consumer, Readers-Writers, Dining Philosophers)

Classical Synchronization Problems are standard problems used to understand how processes coordinate and share resources safely without conflicts.

1. Producer–Consumer Problem (Bounded Buffer Problem)

Concept

A producer creates data and puts it into a buffer

A consumer takes data from the buffer

Buffer has limited size

Problem

Producer should not add data if buffer is full

Consumer should not remove data if buffer is empty

Solution

Use Semaphore: (we can use semaphores to keep track of the number of empty and full slots in the buffer.)

Mutex → for mutual exclusion

Full → number of filled slots

Empty → number of empty slots

Mutual Exclusion (Mutex) is a concept used in operating systems to ensure that only one process or thread can access a shared resource (critical section) at a time.

Mutual exclusion is a technique that prevents multiple processes from entering the critical section simultaneously.

2. Dining Philosophers Problem 1965

The Dining Philosopher Problem is a classic synchronization problem introduced by Edsger Dijkstra in 1965. It illustrates the challenges of resource sharing in concurrent programming, such as deadlock, starvation, and mutual exclusion.

Concept

6 Pphilosophers sit around a circular table.

Each philosopher alternates between thinking and eating.

There is one chopstick between each philosopher (total K chopsticks).

A philosopher must pick up two chopsticks (left and right) to eat.

Only one philosopher can use a chopstick at a time.

The challenge: Design a synchronization mechanism so that philosophers can eat without causing deadlock (all waiting forever) or starvation (some never get a chance to eat).

Issues in the Problem

If all pick one chopstick →

1.             Deadlock: If every philosopher picks up their left chopstick first, no one can pick up the right one circular wait.

2.             Starvation: Some philosophers may never get a chance to eat if others keep eating.

3.             Concurrency Control: Must ensure no two adjacent philosophers eat simultaneously.

 

deadlock occurs (A deadlock is a situation in which two or more processes are unable to proceed because each is waiting for a resource held by another process.)

Solution

Resource hierarchy

Resource Hierarchy is a technique used to prevent deadlock by assigning an order (number) to resources and forcing processes to request them in that order.

Idea behind It

Each resource (chopstick) is given a unique number

A philosopher must always pick the lower-numbered chopstick first, then the higher-numbered one
this breaks circular wait, so deadlock cannot occur

Example (Dining Philosophers)

Assume:

5 philosophers: P1, P2, P3, P4, P5

5 chopsticks numbered: C1, C2, C3, C4, C5

Arrangement:

P1 → C1 & C2

P2 → C2 & C3

P3 → C3 & C4

P4 → C4 & C5

P5 → C5 & C1

Rule Applied

Each philosopher picks:
First lower-numbered chopstick, then higher-numbered

So:

P1 → picks C1 then C2

P2 → picks C2 then C3

P3 → picks C3 then C4

P4 → picks C4 then C5

P5 → picks C1 then C5 (since C1 < C5)

Why Deadlock is Avoided?

No circular waiting chain is formed

At least one philosopher can always eat
Circular wait condition is eliminated

 

Limit number of philosophers

Basic Idea

If there are N philosophers, allow only N − 1 philosophers to sit (or pick chopsticks) at a time

Example:

Total philosophers = 5

Only 4 philosophers can try to eat at once

Why does it work?

At least one philosopher will always be able to get both chopsticks

This breaks circular wait condition so deadlock cannot occur

Example

• Philosophers: P1, P2, P3, P4, P5
• Only 4 allowed to pick chopsticks

Suppose:

• P1, P2, P3, P4 are trying to eat
• P5 is waiting

Since one philosopher is not competing:
One of the active philosophers will get both chopsticks and eat
Then resources are released → others proceed

Use semaphores or monitors

3. Readers–Writers Problem

Concept

Multiple processes:

Readers → only read data

Writers → modify data

Problem

Multiple readers can access at same time

Ensure that only one writer writes at a time.

Prevent readers from reading while a writer is writing.

Writer needs exclusive access

Solution

Readers Preference – give readers priority, making writers wait.

Writers Preference – give writers priority, ensuring timely updates.

Use read-write locks / semaphores (The reader-writer problem using semaphores manages concurrent access to a shared resource, allowing multiple readers to read simultaneously but giving writers exclusive access. (exclusive-not to be shared) It utilizes a mutex (for updating reader count, ( mutex - to prevent multiple threads from accessing shared resources simultaneously)) and a wrt semaphore (for locking the resource) to prevent data inconsistency, ensuring that while a writer is active, no reader or other writer can enter)

Allow multiple readers

Block writers when readers active

Semaphores & Mutex

Both semaphores and mutex are used for process synchronization and to control access to shared resources.

1. Semaphore

What is a Semaphore?

A semaphore is a signaling mechanism used to control access to multiple resources.

Types

Binary Semaphore (0 or 1)

Counting Semaphore (0, 1, 2, …)

Operations

wait (P) → decrease value

signal (V) → increase value

Example

wait(S);
// critical section
signal(S);

2. Mutex (Mutual Exclusion)

What is a Mutex?

A mutex is a locking mechanism used to ensure that only one process/thread accesses a resource at a time.

It is like a lock/unlock system

Example

lock(mutex);
// critical section
unlock(mutex);

Key Differences

Feature	Semaphore	Mutex
Meaning	Signaling mechanism	Locking mechanism
Values	Integer (0,1,2,…)	Only 0 or 1
Usage	Multiple resources	Single resource
Ownership	No ownership	Has ownership
Operations	wait() / signal()	lock() / unlock()

Similarities

Used for synchronization

Prevent race conditions

Control access to critical section

Advantages

Efficient resource management

Ensures data consistency

Disadvantages

Can cause deadlock if misused

Difficult to implement correctly

Short Answer (Exam Ready)

Semaphore is a signaling mechanism used to manage multiple resources, while mutex is a locking mechanism used to allow only one process to access a resource at a time.