Chapter 5: Process Synchronization

Introduction to Process Synchronization

In a multi-programming environment, multiple processes often run concurrently, and they might share data or resources. Process synchronization is the mechanism to manage the execution of these cooperating processes to ensure orderly access to shared resources and maintain data consistency. Without proper synchronization, concurrent access can lead to unpredictable outcomes and errors.

What is Process Synchronization?

Process Synchronization refers to the coordination of multiple processes (or threads) that are executing concurrently and potentially accessing shared data or resources. The primary goal is to control the sequence of their execution to prevent conflicts and ensure that the outcome of their concurrent operations is correct and predictable, as if they were executed in some sequential order.

Why is Process Synchronization Needed?

Synchronization is crucial for several reasons:

• Data Consistency: When multiple processes access and manipulate shared data concurrently, the final state of the data might depend on the precise order of execution. This can lead to inconsistent data if accesses are not managed.
• Preventing Race Conditions: A race condition occurs when the outcome of a computation depends on the non-deterministic timing or interleaving of operations by multiple processes. Synchronization helps prevent such scenarios.
• Orderly Resource Sharing: Shared resources like printers, files, or memory segments need to be accessed in a controlled manner (e.g., one process at a time for exclusive resources).

Cooperating Processes vs. Independent Processes

Processes can be categorized based on their interaction:

• Independent Processes: An independent process is one whose execution does not affect and is not affected by other processes executing in the system. They do not share any data (temporary or persistent) with other processes.
• Cooperating Processes: A cooperating process is one that can affect or be affected by other processes executing in the system. These processes typically share data, either through shared memory, message passing, or common files. Cooperation is essential for information sharing, computation speedup (by dividing tasks), modularity, and convenience.

Process synchronization is primarily concerned with managing the interactions of cooperating processes.

Competitive vs. Cooperative Synchronization

Synchronization needs can arise from two main scenarios:

• Competitive Synchronization: This occurs when multiple processes compete for exclusive access to a shared resource. For example, two processes trying to print to the same printer. The main goal here is to ensure mutual exclusion – only one process uses the resource at any given time.
• Cooperative Synchronization: This occurs when processes need to work together to achieve a common goal. For instance, one process (a producer) might generate data that another process (a consumer) uses. They need to synchronize their actions (e.g., the consumer waits if no data is available, the producer waits if the buffer is full).

The Critical Section Problem

A fundamental challenge in concurrent programming is managing access to shared resources. The part of a program where a shared resource is accessed is known as the critical section.

Defining the Critical Section

A Critical Section (CS) is a segment of code in a process where shared resources (like common variables, data structures, files, etc.) are accessed and potentially modified. It's "critical" because if multiple processes execute their respective critical sections concurrently, it can lead to data corruption or inconsistent state due to uncoordinated modifications.

The general structure of a process involving a critical section is:

do {
    // Entry Section: Code to request permission to enter CS
    
    // --- CRITICAL SECTION ---
    // Access shared resources
    // --- END CRITICAL SECTION ---
    
    // Exit Section: Code to release CS
    
    // Remainder Section: Other non-critical code
} while (true);

Race Conditions

A Race Condition is an undesirable situation that occurs when a device or system attempts to perform two or more operations at the same time, but because of the nature of the device or system, the operations must be done in the proper sequence to be done correctly. In the context of processes, it occurs when multiple processes access and manipulate shared data concurrently, and the final outcome depends on the particular order in which their instructions are interleaved by the scheduler.

Example of a Race Condition:

Consider two processes, P1 and P2, both trying to increment a shared counter variable, count, initialized to 5.

The high-level instruction count++ might translate to the following machine instructions:

1. LOAD R, count (Load the value of count into a register R)
2. INCREMENT R (Increment the register R)
3. STORE R, count (Store the new value from R back to count)

If P1 and P2 execute concurrently, their instructions might interleave like this:

Expected Result: count should be 7 (5 + 1 + 1).
Actual Result (due to race condition): count is 6.

This demonstrates how unsynchronized access to shared data can lead to incorrect results. The critical section is the code segment count++.

Requirements for a Valid Solution to the Critical Section Problem

Any solution to the critical section problem must satisfy the following three fundamental requirements:

1. Mutual Exclusion (M.E.):

   If a process is executing in its critical section, then no other process can be executing in its critical section for the same shared resource. This is the primary goal – to prevent simultaneous access.

2. Progress:

   If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder sections can participate in the decision of which will enter its critical section next. Furthermore, this selection cannot be postponed indefinitely. This means:

   • If the critical section is free, and at least one process wants to enter, one process must be allowed to enter.
   • The decision of who enters next cannot be blocked by processes that are not interested in entering the critical section.
3. Bounded Waiting (No Starvation / Fairness):

   There must exist a bound on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. This ensures that no process waits indefinitely to enter its critical section (i.e., it prevents starvation).

Additionally, a good solution should be efficient and, if possible, work for any number of processes, not just two.

Synchronization Mechanisms: An Overview

Solutions to the critical section problem can be broadly categorized based on how a process waits when it cannot enter its critical section:

1. Busy-Waiting (Spinlocks)

In busy-waiting solutions, when a process attempts to enter its critical section but finds it occupied, it continuously executes a loop, repeatedly checking if the critical section has become available. This "spinning" consumes CPU cycles without doing productive work. These are also known as spinlocks.

• Pros: Low latency in acquiring the lock once it's free, as no context switch is involved. Useful for short critical sections where the wait time is expected to be minimal.
• Cons: Wastes CPU cycles, especially if the critical section is held for a long time or on a single-processor system (where the waiting process prevents the process holding the lock from running and releasing it). Can lead to priority inversion problems if a low-priority process holds the lock and a high-priority process is spinning.

2. Non-Busy Waiting / Blocking (Sleep & Wakeup)

In blocking solutions, when a process cannot enter its critical section, it is moved from the Running state to a Waiting (or Blocked) state by the operating system. It yields the CPU, allowing other processes to run. When the critical section becomes free, the blocked process is woken up (moved to the Ready state) and can eventually re-enter the Running state to attempt entry again.

• Pros: Avoids wasting CPU cycles. Generally better for longer critical sections or when contention is high.
• Cons: Involves the overhead of context switching (saving and restoring process state), which can be more time-consuming than a short spin if the lock is released very quickly.

Primitives like semaphores and monitors typically use blocking.

Software-based Busy-Waiting Solutions

These solutions rely purely on software algorithms and shared variables, without special hardware instructions. They are often complex to design correctly and typically work for a limited number of processes.

Attempt 1: Simple Lock Variable (Naive Approach)

One of the simplest ideas is to use a shared lock variable.

// Shared variable
boolean lock = false; // false means free, true means busy

// Process Pi
do {
    while (lock == true) {
        // busy wait
    }
    lock = true; // Acquire lock
    
    // --- CRITICAL SECTION ---
    
    lock = false; // Release lock
    
    // --- REMAINDER SECTION ---
} while (true);

Analysis:

• Mutual Exclusion: No. This solution can violate mutual exclusion. Consider this scenario:
  1. Process P0 sees lock is false.
  2. Before P0 can set lock to true, it's preempted.
  3. Process P1 runs, sees lock is false, sets lock to true, and enters CS.
  4. Process P0 resumes, also sets lock to true (it had already passed the while condition), and enters CS.
  Both P0 and P1 are in the critical section simultaneously. The check (while (lock == true)) and the acquisition (lock = true;) are not atomic.
• Progress: Yes (conditionally). If ME were guaranteed, and the CS is free, a process wanting to enter could. However, with ME failure, progress is ill-defined.
• Bounded Waiting: No. If multiple processes are waiting, there's no guarantee which one will get the lock next.
• Busy Waiting: Yes. Processes spin in the while loop.

Attempt 2: Strict Alternation (Turn Variable)

This approach uses a shared turn variable to ensure that two processes take turns entering their critical sections.

// Shared variable
int turn = 0; // Initially, process 0 can enter

// Process Pi (where i is 0 or 1)
do {
    while (turn != i) {
        // busy wait - wait for its turn
    }
    
    // --- CRITICAL SECTION ---
    
    turn = 1 - i; // Pass the turn to the other process
    
    // --- REMAINDER SECTION ---
} while (true);

Analysis:

• Mutual Exclusion: Yes. Only one process can have turn == i at any time.
• Progress: No. This solution enforces strict alternation. If P0 wants to enter CS again but P1 is in its remainder section, P0 must wait.
• Bounded Waiting: Yes (trivially). A process waits for at most one entry by the other process.
• Busy Waiting: Yes.
• Process Limit: Only works for two processes.

Peterson's Solution (for 2 Processes)

Peterson's solution is a classic software-based solution that combines the ideas of a turn variable and flag variables to satisfy all three critical section requirements for two processes.

// Shared variables:
boolean flag[2]; // Indicate if a process wants to enter the critical section. Initially false.
int turn;     // Indicates whose turn it is.

// Initialization:
flag[0] = false;
flag[1] = false;
// turn can be initialized to 0 or 1. Let's say 0.
turn = 0; 

void process_i_peterson(int i) { // i is the process ID (0 or 1)
    int j = 1 - i; // The other process ID

    while (true) { 
        flag[i] = true;     // Indicate desire to enter critical section
        turn = j;           // Give priority to the other process (j) if contention
        
        // Wait if Pj also wants to enter AND it's Pj's turn
        while (flag[j] && turn == j) { 
            // Busy wait
        }

        // --- CRITICAL SECTION ---
        // System.out.println("Process " + i + " is in Critical Section (Peterson)");
        // --- END CRITICAL SECTION ---

        flag[i] = false;    // Indicate exit from critical section
        
        // --- REMAINDER SECTION ---
    }
}

Analysis:

• Mutual Exclusion: Yes. A process Pi enters its CS only if either flag[j] is false (Pj doesn't want to enter) or turn == i (it's Pi's turn).
• Progress: Yes. If Pj is not interested (flag[j] is false), Pi can enter. If both are interested, one will eventually enter.
• Bounded Waiting: Yes. Pi waits for at most one entry by Pj.
• Busy Waiting: Yes. The while (flag[j] && turn == j) loop is a busy-wait loop.
• Process Limit: Works for two processes.

Hardware-Assisted Busy-Waiting Solutions

Modern computer architectures provide special atomic instructions that can simplify the implementation of critical sections.

Disabling Interrupts

On a single-processor system, disabling interrupts before CS and re-enabling after can ensure ME.

• Cons: Not for user-level; inefficient on multi-processors; impacts system responsiveness. Used by OS kernel for very short CS.

Test-and-Set Lock (TSL) Instruction

The TestAndSet() instruction atomically reads a boolean lock, sets it to true, and returns the original value.

// Shared variable:
boolean lock_tsl = false; 

// Atomic Test and Set Lock function (hardware-dependent)
boolean TestAndSet(boolean *target) {
    boolean oldValue = *target;
    *target = true; 
    return oldValue; 
}

void process_using_tsl() {
    while (true) {
        while (TestAndSet(&lock_tsl)) {
            // Busy wait
        }
        // --- CRITICAL SECTION ---
        lock_tsl = false; 
        // --- REMAINDER SECTION ---
    }
}

Analysis:

• Mutual Exclusion: Yes.
• Progress: Yes.
• Bounded Waiting: No (simple form).
• Busy Waiting: Yes.
• Process Limit: N processes.

Atomic Swap (or Exchange) Instruction

The AtomicSwap() instruction atomically swaps the contents of two memory locations.

// Shared variable:
int lock_swap_var = 0; // 0 means unlocked, 1 means locked

// Atomic Swap function (hardware, simplified conceptual implementation)
void atomic_swap_int(int *val1, int *val2) {
    // This operation must be atomic by hardware.
    int temp = *val1; *val1 = *val2; *val2 = temp;
}

void process_using_swap() {
    int local_key;
    while (true) {
        local_key = 1; 
        do {
            atomic_swap_int(&local_key, &lock_swap_var); 
        } while (local_key != 0); 
        // --- CRITICAL SECTION ---
        lock_swap_var = 0; 
        // --- REMAINDER SECTION ---
    }
}

Analysis:

• Mutual Exclusion: Yes.
• Progress: Yes.
• Bounded Waiting: No (simple form).
• Busy Waiting: Yes.
• Process Limit: N processes.

Blocking Synchronization Primitives

These primitives allow a waiting process to sleep, yielding the CPU.

Semaphores

A Semaphore is an integer variable accessed via atomic wait() (P) and signal() (V) operations.

Core Concept and Operations (Conceptual with Blocking):

typedef struct {
    int value;
    // Queue waiting_queue; // Pseudo-code for waiting queue
} Semaphore;

void wait_sem(Semaphore *S) { // Renamed to avoid conflict with HTML wait
    S->value--;
    if (S->value < 0) {
        // add current process to S->waiting_queue;
        // block(); // Suspend the process
    }
}

void signal_sem(Semaphore *S) { // Renamed
    S->value++;
    if (S->value <= 0) { 
        // remove a process P from S->waiting_queue;
        // wakeup(P); // Move P to the ready queue
    }
}

Types of Semaphores:

1. Counting Semaphore:

• Value can range over an unrestricted domain.
• Use Cases: Controlling access to N identical resources (init S to N), signaling events.
• Mutual Exclusion: Only if S is initialized to 1. If S > 1, ME for a single CS is violated.

2. Binary Semaphore (Mutex):

• Value is 0 or 1. Acts like a lock.
• Use Case: Mutual exclusion.
  Show Code

  Semaphore mutex_sem_example = { .value = 1 }; // Initialize to 1
  do {
      wait_sem(&mutex_sem_example);
      // --- CRITICAL SECTION ---
      signal_sem(&mutex_sem_example);
      // --- REMAINDER SECTION ---
  } while (true);

Mutex Locks

A Mutex (Mutual Exclusion) Lock is specifically for enforcing ME.

Key Characteristics:

• States: Locked/Unlocked.
• Operations: lock() (acquire), unlock() (release).
• Ownership: Typically, only the thread that locked it can unlock it.

Mutex vs. Semaphore:

Classical Synchronization Problems

1. The Producer-Consumer (Bounded Buffer) Problem

Producers add items to a shared buffer, consumers remove them. Buffer has finite size.

Solution using Semaphores:

// Assume N is buffer_size
// Semaphore mutex_pc = { .value = 1 };
// Semaphore emptySlots_pc = { .value = N };
// Semaphore fullSlots_pc = { .value = 0 };

// Producer Process:
while (true) {
    // item = produce_item();
    wait_sem(&emptySlots_pc);     
    wait_sem(&mutex_pc);          
    // add_item_to_buffer(item);
    signal_sem(&mutex_pc);        
    signal_sem(&fullSlots_pc);      
}

// Consumer Process:
while (true) {
    wait_sem(&fullSlots_pc);        
    wait_sem(&mutex_pc);          
    // item = remove_item_from_buffer();
    signal_sem(&mutex_pc);        
    signal_sem(&emptySlots_pc);     
    // consume_item(item);
}

2. The Readers-Writers Problem

Shared resource: Readers can access concurrently; Writers need exclusive access.

First Readers-Writers Problem (Readers' Priority):

// Semaphore db_access_rw = { .value = 1 }; 
// Semaphore mutex_reader_count_rw = { .value = 1 }; 
int reader_count_rw = 0;    

// Reader Process:
while (true) {
    wait_sem(&mutex_reader_count_rw);
    reader_count_rw++;
    if (reader_count_rw == 1) { wait_sem(&db_access_rw); } 
    signal_sem(&mutex_reader_count_rw);

    // 

    wait_sem(&mutex_reader_count_rw);
    reader_count_rw--;
    if (reader_count_rw == 0) { signal_sem(&db_access_rw); } 
    signal_sem(&mutex_reader_count_rw);
}

// Writer Process:
while (true) {
    wait_sem(&db_access_rw);      
    // 
    signal_sem(&db_access_rw);
}

Analysis (Readers' Priority):

• Bounded Waiting: Not guaranteed for writers (Writer Starvation).

3. The Dining Philosophers Problem

Five philosophers, five chopsticks. Each needs two to eat. Illustrates deadlock and starvation.

Naive Solution (Deadlock-Prone):

int N_PHIL = 5;
// Semaphore chopsticks_dp[N_PHIL]; // Initialized to 1 each

void philosopher_dp(int i) {
    while (true) {
        // think()
        wait_sem(&chopsticks_dp[i]);             
        wait_sem(&chopsticks_dp[(i + 1) % N_PHIL]); 
        // eat()
        signal_sem(&chopsticks_dp[i]);
        signal_sem(&chopsticks_dp[(i + 1) % N_PHIL]);
    }
}

Deadlock Prevention Strategies:

1. Limit concurrent diners to N-1.
2. Asymmetric solution (one philosopher picks right then left).
3. Acquire both chopsticks atomically.

Advanced Synchronization Constructs

Monitors

A Monitor is a high-level ADT encapsulating shared data and procedures operating on it. Only one process can be active within a monitor at a time (implicit mutual exclusion).

Condition Variables

Used within monitors for processes to wait for specific conditions. Operations:

• wait_cond(c): Suspends process, releases monitor lock. (Renamed)
• signal_cond(c): Resumes one waiting process (if any). (Renamed)

Example: Producer-Consumer with Monitors (Conceptual)

monitor BoundedBufferMonitor {
    // Buffer buffer_mon; int count_mon = 0; int BUFFER_SIZE_MON;
    // Condition notFull_mon, notEmpty_mon;

    procedure produce_mon(Item item) {
        if (count_mon == BUFFER_SIZE_MON) { notFull_mon.wait_cond(); }
        // add_item_to_buffer(item); count_mon++;
        notEmpty_mon.signal_cond();
    }
    procedure Item consume_mon() {
        if (count_mon == 0) { notEmpty_mon.wait_cond(); }
        // Item item = remove_item_from_buffer(); count_mon--;
        notFull_mon.signal_cond();
        // return item;
    }
}

Common Synchronization Challenges

Deadlock

Two or more processes indefinitely waiting for resources held by each other.

Necessary Conditions:

Starvation (Indefinite Postponement)

A process is perpetually denied resources, making no progress. Prevented by fair scheduling/allocation (e.g., bounded waiting).

Livelock

Processes actively change state in response to others but make no useful progress. They are "busy" but stuck.

Analogy: The Overly Polite Hallway Dance

Two people try to step aside for each other in a narrow hallway, repeatedly mirroring moves and never passing. Unlike deadlock, processes are active, not blocked.

Priority Inversion

A high-priority task (H) is blocked by a lower-priority task (L) because L holds a resource H needs, and L itself is preempted by a medium-priority task (M).

Classic Scenario:

1. Task L (low) acquires resource R.
2. Task H (high) preempts L, tries to acquire R, blocks.
3. Task M (medium) becomes ready, preempts L (since H is blocked).
4. Result: H waits for L, but L can't run because M is running. H is effectively blocked by M.

Example: Mars Pathfinder (1997)

System resets due to this. A low-priority meteorological task held a mutex, blocked by a high-priority bus task. A medium-priority communication task preempted the meteorological task, preventing mutex release, leading to a watchdog timeout.

Solutions:

• Priority Inheritance Protocol (PIP): L temporarily inherits H's priority while holding the resource.
• Priority Ceiling Protocol (PCP): Resource has a priority ceiling (highest priority of any task using it). A task acquiring it gets its priority raised to this ceiling.

Related Concepts

Concurrency vs. Parallelism

• Concurrency: Tasks appear to run simultaneously (interleaved execution). Dealing with many things at once.
• Parallelism: Tasks actually run simultaneously (on multiple cores). Doing many things at once.

Thread Safety

Code behaves correctly when accessed by multiple threads concurrently. Achieved using synchronization mechanisms to protect shared data.

Inter-Process Communication (IPC) and Synchronization

IPC mechanisms (pipes, shared memory, etc.) often require synchronization (e.g., semaphores for shared memory access) to ensure correct data exchange and coordination.

Data Integrity in the Context of Process Synchronization

Ensuring shared data remains accurate, consistent, and valid despite concurrent access. Synchronization prevents race conditions, inconsistent updates, and lost updates, thereby maintaining data integrity.

Summary of Synchronization Techniques

Spinlocks (Busy-Waiting: TSL, Swap)

• Advantages: Low latency for very short lock holds (no context switch).
• Disadvantages: Wastes CPU; priority inversion risk; not for long holds.

Mutexes/Semaphores (Blocking Locks)

• Advantages: CPU yielded (no wasted cycles); better for longer holds; can incorporate fairness.
• Disadvantages: Context switch overhead for short holds; more complex to use perfectly.

Monitors

• Advantages: Higher-level, easier to use; implicit ME; clear condition management.
• Disadvantages: Language/compiler support; potential for complex deadlocks (e.g., nested calls).