Chapter 6: Process Synchronization

CS330 - Operating Systems

Critical Section, Semaphores, Classical Problems

6.1 Background

Concurrent access to shared data may result in data inconsistency. Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes.

Cooperating Processes

Processes can execute concurrently and may be interrupted at any time, partially completing execution. Concurrent access to shared data may result in race conditions.

Race Condition

⚠️ Race Condition Definition:

A situation where several processes access and manipulate the same data concurrently, and the outcome depends on the particular order in which access takes place.

Example: Counter Problem

Suppose counter = 5

Producer executes: counter++

Consumer executes: counter--

Result could be: 4, 5, or 6!

// Race Condition Example
// Producer Process
counter++; // This is actually three machine instructions:
           // 1. register1 = counter
           // 2. register1 = register1 + 1
           // 3. counter = register1

// Consumer Process
counter--; // This is also three machine instructions:
           // 1. register2 = counter
           // 2. register2 = register2 - 1
           // 3. counter = register2
            

6.2 The Critical-Section Problem

The Critical Section (CS) is the part of process code that manipulates shared data or resources. Execution of the CS should be mutually exclusive.

Entry Section

CRITICAL SECTION

Exit Section

Remainder Section

Requirements for Solution

Mutual Exclusion: If process Pi is executing in its critical section, then no other processes can be executing in their critical sections.
Progress: If no process is executing in its critical section and some processes wish to enter, then only those not in their remainder section can participate in deciding who enters next, and this selection cannot be postponed indefinitely.
Bounded Waiting: A bound must exist on the number of times other processes are allowed to enter their critical sections after a process has made a request and before that request is granted. This prevents starvation.

⚠️ Important:

All three requirements must be satisfied for a correct solution to the critical section problem!

6.3 Peterson's Solution

Two-Process Solution

Assumes that load and store instructions are atomic. Uses two shared variables:

int turn; - Indicates whose turn it is to enter critical section
boolean flag[2]; - Indicates if a process is ready to enter critical section

// Peterson's Solution for Process Pi
do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
        ; // busy wait
    
    // CRITICAL SECTION
    
    flag[i] = false;
    
    // REMAINDER SECTION
} while (true);
            

✅ Proof that Peterson's Solution Works:

Mutual Exclusion: Both processes cannot be in CS simultaneously
Progress: A process outside CS doesn't block others
Bounded Waiting: Process waits at most one turn

6.4 Synchronization Hardware

Many systems provide hardware support for critical section code. Modern machines provide special atomic hardware instructions.

Test and Set Instruction

boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

// Solution using test_and_set()
do {
    while (test_and_set(&lock))
        ; // busy wait
    
    // CRITICAL SECTION
    
    lock = false;
    
    // REMAINDER SECTION
} while (true);
            

Compare and Swap Instruction

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if (*value == expected)
        *value = new_value;
    return temp;
}
            

6.5 Mutex Locks

Previous solutions are complicated for application programmers. OS designers build software tools to solve critical section problem. Simplest is mutex lock.

// Mutex Lock Usage
acquire() {
    while (!available)
        ; // busy wait
    available = false;
}

release() {
    available = true;
}

// Process code
do {
    acquire(lock);
    
    // CRITICAL SECTION
    
    release(lock);
    
    // REMAINDER SECTION
} while (true);
            

⚠️ Spinlock Problem:

This implementation requires busy waiting. While a process is in its critical section, any other process trying to enter must loop continuously (spin). This wastes CPU cycles.

6.6 Semaphores

Semaphore Definition

A synchronization tool that provides more sophisticated ways for processes to synchronize their activities.

Semaphore S is an integer variable accessed only through two atomic operations:

wait(S)

S--;
if (S < 0)
  block();

↔

signal(S)

S++;
if (S <= 0)
  wakeup();

Types of Semaphores

Type	Range	Usage
Binary Semaphore	0 or 1	Mutual exclusion (mutex)
Counting Semaphore	Unrestricted domain	Resource allocation with multiple instances

Semaphore Implementation Without Busy Waiting

typedef struct {
    int value;
    struct process *list;
} semaphore;

wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // add this process to S->list
        block();
    }
}

signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // remove a process P from S->list
        wakeup(P);
    }
}
            

6.7 Classic Problems of Synchronization

1. Bounded-Buffer Problem

Item

Empty

Semaphores Used:

mutex - initialized to 1 (mutual exclusion)
full - initialized to 0 (number of full buffers)
empty - initialized to n (number of empty buffers)

// Producer Process
do {
    // produce an item in next_produced
    
    wait(empty);
    wait(mutex);
    
    // add next_produced to buffer
    
    signal(mutex);
    signal(full);
} while (true);

// Consumer Process
do {
    wait(full);
    wait(mutex);
    
    // remove item from buffer to next_consumed
    
    signal(mutex);
    signal(empty);
    
    // consume item in next_consumed
} while (true);
                

2. Readers-Writers Problem

A data set is shared among concurrent processes:

Readers: Only read the data set; no updates
Writers: Can both read and write

Problem: Allow multiple readers to read simultaneously. Only one writer can access shared data at a time.

Shared Data:

rw_mutex - initialized to 1 (common to readers/writers)
mutex - initialized to 1 (protects read_count)
read_count - initialized to 0 (number of readers)

// Writer Process
do {
    wait(rw_mutex);
    
    // WRITING is performed
    
    signal(rw_mutex);
} while (true);

// Reader Process
do {
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);
    
    // READING is performed
    
    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw_mutex);
    signal(mutex);
} while (true);
                

3. Dining-Philosophers Problem

🍝 Dining Philosophers Table

[Insert diagram: 5 philosophers around table with rice bowl and chopsticks]

Problem Description:

5 philosophers who only eat and think
Each needs 2 chopsticks for eating
Only 5 chopsticks available
Illustrates difficulty of allocating resources without deadlock and starvation

// Simple Solution (may cause deadlock!)
chopstick[5]; // semaphores initialized to 1

do {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
    
    // EAT
    
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    
    // THINK
} while (true);

// Problem: Deadlock if all pick up left chopstick!
                

Solutions to Prevent Deadlock:

Allow at most 4 philosophers at the table
Allow pickup only if both chopsticks available
Odd philosophers pick up left first, even pick up right first

6.8 Monitors

Monitor Structure

Shared Data

↓

Operations/Procedures

↓

Initialization Code

↓

Entry Queue

A high-level abstraction that provides a convenient and effective mechanism for process synchronization. Only one process may be active within the monitor at a time.

Monitor Solution for Dining Philosophers

monitor DiningPhilosophers {
    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];
    
    void pickup(int i) {
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            self[i].wait();
    }
    
    void putdown(int i) {
        state[i] = THINKING;
        test((i + 4) % 5);
        test((i + 1) % 5);
    }
    
    void test(int i) {
        if ((state[(i+4)%5] != EATING) &&
            (state[i] == HUNGRY) &&
            (state[(i+1)%5] != EATING)) {
            state[i] = EATING;
            self[i].signal();
        }
    }
}
            

6.9 Deadlock and Starvation

⚠️ Deadlock Example

Two or more processes waiting indefinitely for an event that can be caused only by one of the waiting processes.

// Deadlock Example with Two Semaphores
Semaphore S = 1, Q = 1;

// Process P0        // Process P1
wait(S);           wait(Q);
wait(Q);           wait(S);
   ...                ...
signal(S);         signal(Q);
signal(Q);         signal(S);
                

P0 waits for Q (held by P1), P1 waits for S (held by P0) → DEADLOCK!

⚠️ Starvation

Indefinite blocking. A process may never be removed from the semaphore queue in which it is suspended.

Priority Inversion

A high-priority process is indirectly preempted by a lower-priority process that holds a lock needed by the high-priority process.

Solution: Priority-inheritance protocol

6.10 Practice Problems and Exam Questions

Multiple Choice Questions

Q1. A situation where several processes access the same data concurrently and the outcome depends on the order of access is called:

a) Dynamic condition
b) Race condition
c) Essential condition
d) Critical condition

Q2. What is the correct order of operations for protecting a critical section using a binary semaphore?

a) release() followed by acquire()
b) acquire() followed by release()
c) wait() followed by signal()
d) signal() followed by wait()

Q3. Mutual exclusion can be provided by:

a) Spinlocks
b) Mutex locks
c) Both (a) and (b)
d) Both (a) and (b)

Q4. Which of these does NOT satisfy the critical section requirements?

a) Mutual Exclusion
b) Progress
c) Bounded Wait
d) All satisfy the requirements

Q5. The bounded buffer problem is also known as:

a) Readers-Writers problem
b) Dining Philosophers problem
c) Producer-Consumer problem
d) None of the mentioned

Q6. In the dining philosophers problem, deadlock occurs when:

a) All 5 philosophers pick up their left chopstick
b) 4 philosophers pick up chopsticks
c) 3 philosophers pick up chopsticks
d) 6 philosophers pick up chopsticks

Short Answer Questions

Q7. Given two concurrent programs that use semaphores S1 (init=1) and S2 (init=0):

Process P1:            Process P2:
Sem S1=1;             Sem S1=1;
Sem S2=0;             Sem S2=0;
                      
while(True) {         while(True) {
  wait(S2);             wait(S1);
  print("A");           print("B");
  signal(S1);           signal(S2);
}                     }
                    

What will be the output pattern?

Answer:

P1 will be blocked initially on wait(S2). P2 executes wait(S1), prints "B", then signals S2. P1 can now proceed, prints "A", signals S1. Pattern: BABA...

Q8. A shared variable mutex is initialized to 1. Each process executes wait(mutex) before entering CS and signal(mutex) after. What happens if a process replaces signal(mutex) with wait(mutex)?

Answer:

Deadlock will occur. After the first process enters and exits its CS, it will execute wait(mutex) again, making mutex = -1. No process can enter CS again.

Q9. What are the three requirements for a solution to the critical section problem?

Answer:

Mutual Exclusion: Only one process in CS at a time
Progress: Selection of next process cannot be postponed indefinitely
Bounded Waiting: Limit on times others enter CS after request

6.11 Key Terms and Definitions

Term	Definition
Race Condition	Outcome depends on order of process execution
Critical Section	Code segment that accesses shared data
Mutual Exclusion	Only one process in CS at a time
Semaphore	Integer variable with atomic wait/signal operations
Mutex	Binary semaphore for mutual exclusion
Spinlock	Lock that uses busy waiting
Deadlock	Processes waiting indefinitely for each other
Starvation	Process never gets resources
Monitor	High-level synchronization construct
Atomic Operation	Operation that completes without interruption
Busy Waiting	Continuously testing a condition
Priority Inversion	Low priority process blocks high priority

6.12 Diagrams from Slides

📊 Race Condition Illustration

[Insert diagram showing concurrent access to shared counter]

📊 Dining Philosophers Table

[Insert diagram from Chapter_6.pdf showing 5 philosophers with chopsticks]

📊 Monitor Structure

[Insert monitor schematic diagram]

📊 Producer-Consumer Buffer

[Insert bounded buffer visualization]

Note: Please provide the actual diagrams from your Chapter_6.pdf slides to replace these placeholders.