Process Synchronization Introduction

Process Synchronization & Critical Section Concepts

1. Process Types and Race Conditions

Independent vs Cooperative Processes

• Independent Processes:

  Do NOT interact or share data.

  Example:

  You’re listening to music on Spotify while typing in a text editor.

  The music app and text editor don’t interfere with each other.

• Cooperative Processes:

  Work together and share data/resources.

  Example:

  Two bank clerks updating the same customer’s balance.

  If Clerk A adds 100 and Clerk B adds 200, their actions must coordinate to avoid overwriting each other.

What is a Race Condition?

Definition: When two or more processes “race” to modify shared data, causing unpredictable results.

Real-Life Analogy:

Two chefs sharing a single oven.

Chef A sets the temperature to 180°C, but Chef B changes it to 200°C before Chef A starts baking.

The cake burns because the final temperature depends on who acted last.

Example: Shared Counter Update

Scenario:

Two people (Process P1 and P2) try to increment a shared counter X = 5.

Step-by-Step Race:

P1 reads X = 5.

P1 gets interrupted (e.g., a phone call) before writing.

P2 reads X = 5, increments it to 6, and writes back.

P1 resumes, increments its copy (5) to 6, and overwrites P2’s update.

Result: Final X = 6 instead of 7.

Why Synchronization is Necessary

Without Synchronization:

Data becomes unreliable (e.g., bank balances, inventory counts).

With Synchronization:

Processes take turns, ensuring only one modifies data at a time.

2. Producer-Consumer Problem

Scenario Overview

Producer: Makes data (e.g., a sensor recording temperatures).

Consumer: Uses data (e.g., an app displaying temperature graphs).

Buffer: A shared “waiting area” (e.g., a conveyor belt in a factory).

Example: Pizza Delivery System

Buffer = A shelf that holds 10 pizzas.

Full Buffer: If the shelf is full, the chef (producer) waits.

Empty Buffer: If the shelf is empty, delivery drivers (consumers) wait.

Race Condition:

Chef adds a pizza while a driver takes one, causing the shelf count to miscalculate.

Synchronization Requirements

Mutual Exclusion: Only one chef/driver can access the shelf at a time.

Semaphores:

empty = 10 (empty slots on the shelf).

full = 0 (no pizzas initially).

mutex (lock to prevent simultaneous access).

3. Printer-Spooler Problem

Real-World Example

Scenario:

Office with 3 employees sending documents to one printer.

The printer can only handle one job at a time.

Problem:

If two employees click “Print” at the same time, their jobs might overlap.

Race Condition Example

Shared Resource: Print queue (a list of pending jobs).

Unsafe Sequence:

Employee A adds Job 1 to Queue[0].

Employee B adds Job 2 to Queue[0] before the printer starts.

Result: Job 1 is lost, and the printer outputs garbled text.

Solution with Mutex and Semaphores

Mutex: Ensures only one employee adds to the queue at a time.

Semaphores:

Track available slots (empty) and pending jobs (full).

4. Critical Section Problem

What is a Critical Section?

Definition: Code that accesses shared resources (e.g., variables, files).

Analogy: A shared diary. Only one person can write at a time to avoid chaos.

Conditions for Correctness

Mutual Exclusion: Only one process in the critical section (CS).

Example: A bathroom with a lock – only one person enters.

Progress: If the CS is free, someone must enter (no infinite waiting).

Bounded Waiting: No process waits forever (e.g., a ticket system at a deli counter).

Example: Bank Account Withdrawal

Critical Section: Code that deducts money from an account.

Unsafe Withdrawal:

Two ATMs read balance = \(500\).

Both allow \(400\) withdrawals, resulting in −\(300\) instead of \(100\).

5. Lock Variable Solution & Its Flaws

How Lock Variables Work

Shared Lock: A “flag” (0 = unlocked, 1 = locked).

Pseudocode:

while (lock == 1); // Wait until lock is 0
lock = 1; // Acquire lock
// Critical Section
lock = 0; // Release lock

Why It Fails: Non-Atomic Check-and-Set

Atomic Operation: An uninterruptible action (e.g., snapping fingers).

Race Example:

Process A checks lock = 0.

Process B checks lock = 0 before A sets it to 1.

Both set lock = 1 and enter the CS.

Better Solutions

Test-and-Set Instruction: Hardware ensures checking and setting the lock is atomic.

Semaphores: A counter with atomic wait() and signal() operations.

Example: A nightclub bouncer tracking available seats.

6. Real-World Synchronization Solutions

Traffic Light System (Semaphores)

Red Light (wait()): Stop if no permits (slots) are available.

Green Light (signal()): Proceed when permits are available.

Bakery Algorithm (Software Solution)

Analogy: Customers take a number at a bakery.

Each process gets a unique ticket number, ensuring fairness.

Monitors (High-Level Abstraction)

Example: A shared document editor where only one user can type at a time.

The monitor automatically handles locking/unlocking.

7. Summary

Race Conditions: Occur when processes clash over shared data.

Synchronization Tools:

Mutexes (locks), semaphores (counters), monitors (automatic locks).

Critical Section: Must enforce mutual exclusion, progress, and bounded waiting.

Always Use Atomic Operations: Hardware instructions or OS-provided tools.