Study Notes on Process Synchronization in Operating Systems

Chapter 6: Process Synchronization

Introduction to Processes

• Processes can execute concurrently.
• A process may be interrupted at any time, leading to partial completion of execution.
• Concurrent access to shared data can result in data inconsistency.

Need for Synchronization

• Maintaining data consistency requires mechanisms to ensure orderly execution of cooperating processes.
• Example scenario in context of the producer-consumer problem:
  • Solution includes an integer counter that tracks the number of full buffers.
  • Initially, the counter is set to 0:
  • Producer increments the counter after producing a new buffer.
  • Consumer decrements the counter after consuming a buffer.

Producer Process

• Producer pseudocode:

while (true) {
    /* produce an item in next_produced */
    while (counter == BUFFER_SIZE) ; /* do nothing */
    buffer[in] = next_produced;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
}

Consumer Process

• Consumer pseudocode:

while (true) {
    while (counter == 0) ; /* do nothing */
    next_consumed = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--; /* consume the item in next_consumed */
}

Race Condition

• Description of race conditions arising from concurrent updates to the counter:
  • The increment operation could be divided into:
  • register1 = counter
  • register1 = register1 + 1
  • counter = register1
  • Decrement follows similar steps:
  • register2 = counter
  • register2 = register2 - 1
  • counter = register2
  • Execution interleaving example when count = 5:
  • Producer first reads counter (S0: register1 = 5)
  • Producer increments register1 (S1: register1 = 6)
  • Consumer reads counter (S2: register2 = 5)
  • Consumer decrements register2 (S3: register2 = 4)
  • Producer writes updated value to counter (S4: counter = 6)
  • Consumer writes updated value (S5: counter = 4)
  • This leads to inconsistency in counter value.

Critical Section Problem

Definition and Structure

• In a system with n processes {P0, P1, …, Pn-1}, each process has a critical section where it can modify common variables:
  • Critical Section: Segment of code where processes may change shared data.
  • Only one process may be in its critical section at any time.
• Protocol must be designed to manage access to critical sections.

General Structure of Process Pi

do {
    entry section;
    critical section;
    exit section;
    remainder section;
} while (true);

Algorithm for Process Pi

• Example of a simple algorith:

do {
    while (turn == j);
    critical section;
    turn = j;
    remainder section;
} while (true);

Requirements to Solve Critical-Section Problem

1. Mutual Exclusion: Only one process can be in its critical section at one time.
2. Progress: If no process is in its critical section, the next process that wants to enter should not be delayed indefinitely.
3. Bounded Waiting: A limit must exist on how many other processes may enter their critical sections after a request has been made.
   • Does not assume speed of processes.

Critical-Section Handling in OS

• Two approaches based on kernel mode:
  • Preemptive Kernel: Allows preemption of running process.
  • Non-Preemptive Kernel: Runs until process exits kernel mode or explicitly yields.
  • Discusses low risk of race conditions during kernel execution.

Peterson’s Solution

• A well-known algorithm for two processes:
  • Assumes atomicity of load and store instructions.
  • Shares two variables:
  • int turn; // Indicates which process's turn it is to enter the critical section.
  • Boolean flag[2]; // Indicates readiness of processes to enter critical section.
    • flag[i] = true means process Pi is requesting entry.

Peterson's Algorithm for Process Pi

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
    critical section;
    flag[i] = false;
    remainder section;
} while (true);

Validation of Peterson's Solution

• Demonstrates that all three critical section requirements are satisfied:
  1. Mutual Exclusion: Pi enters critical section only if flag[j] = false or turn = i.
  2. Progress: If no processes in critical section, progress is guaranteed.
  3. Bounded Waiting: Ensured by the protocol structure.

Synchronization Hardware

• Hardware support can simplify critical section management.
• Solutions often utilize locking mechanisms to protect critical regions:
  • Uniprocessor systems may disable interrupts.
  • Multiprocessor systems struggle with this, leading to inefficiency.
• Atomic hardware instructions are better suited for modern machines:
  • Atomic actions are non-interruptible (e.g., testing and setting memory words).

Implementing Locks in Critical Sections

• Basic pseudocode for a lock-acquire and release process:

do {
    acquire lock;
    critical section;
    release lock;
    remainder section;
} while (TRUE);

Test and Set Instruction

• Definition of test_and_set instruction:

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

• Executed atomically and sets value of target to TRUE, returning previous value.

Solution Using test_and_set

• Lock implementation using a shared Boolean variable initialized to FALSE:

do {
    while (test_and_set(&lock)); /* busy wait */
    /* critical section */
    lock = false;
    /* remainder section */
} while (true);

Mutex Locks

• Simplified structure for managing critical sections:
  • OS designers use mutex locks to create tools for managing critical sections.
  • Protect a critical section by calls to acquire() and release().
  • Mutex indicates if the lock is available, requiring atomic operations.
  • Drawback is busy waiting, leading to efficiency losses (hence termed spinlock).

Acquire and Release Operations

• Definitions for acquire() and release():

acquire() {
    while (!available);
    available = false;
}
release() {
    available = true;
}

• Usage in pseudocode:

do {
    acquire lock;
    critical section;
    release lock;
    remainder section;
} while (true);

Semaphores

• A semaphore is a synchronization tool that allows processes to communicate through an integer variable, accessed via two atomic operations: wait() and signal(). Originally referred to as P() and V().

Semaphore Operations

• wait(S):

while (S <= 0);
S--;

• signal(S):

S++;

Semaphore Usage

• Counting Semaphore: Can take any non-restricted integer value.
• Binary Semaphore: Only takes values 0 or 1, resembling a mutex lock.
• Can solve various synchronization challenges such as waiting signals from events.

Example of Semaphore Usage

// Create a semaphore “synch” initialized to 0
P1: S1; signal(synch);
P2: wait(synch); S2;

Semaphore Implementation

• Semaphore must ensure no simultaneous access to operations wait() and signal(), effectively turning it into a critical section problem:
  • Place wait and signal code in a critical section to avoid busy waiting as much as possible. However, this approach can lead to contention if critical sections are long.

Implementation Data Structure

• Each semaphore contains data indicating its current state and an associated queue for waiting processes:

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

Operations Without Busy Waiting

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);
    }
}

Deadlock and Starvation

• Deadlock: Occurs when two or more processes wait indefinitely for a resource that can only be released by one of the waiting processes.
• Example with semaphores S and Q initialized to 1:

P0: wait(S); wait(Q);
P1: wait(Q); wait(S);

• Starvation: Indefinite blocking where a process remains suspended indefinitely in the semaphore queue.
• Priority Inversion: Scheduling issue where a lower-priority process holds a lock needed by a higher-priority process, potentially solvable through priority-inheritance protocols.

Classical Problems of Synchronization

• Bounded-Buffer Problem: A fixed-size buffer shared between producer and consumer processes.
• Readers and Writers Problem: Multiple readers can read simultaneously, but only one writer can write.
• Dining-Philosophers Problem: Philosophers alternate between thinking and eating by accessing shared chopsticks.

Bounded-Buffer Problem Description

• Buffer consists of n slots with the following semaphores:
  • mutex: Initializes to 1.
  • full: Initializes to 0.
  • empty: Initializes to n.

Producer Process Structure

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

Consumer Process Structure

do {
    wait(full);
    wait(mutex);
    /* remove an item from buffer to next_consumed */
    signal(mutex);
    signal(empty);
    /* consume the item in next_consumer */
} while (true);

Readers-Writers Problem Description

• Problem involves shared data sets accessed by multiple concurrent processes:
  • Readers: Only read the dataset.
  • Writers: Can both read and write.
  • Conditions dictate that multiple readers can read at one time but only one writer can do so at any given time.

Data Structures in Context

• Semaphore rw_mutex initialized to 1.
• Semaphore mutex initialized to 1.
• Integer read_count to track the number of readers.

Writer Process Structure

do {
    wait(rw_mutex);
    /* writing is performed */
    signal(rw_mutex);
} while (true);

Reader Process Structure

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);

Dining-Philosophers Problem Description

• Philosophers alternate between thinking and eating:
  • Need to acquire two chopsticks (one at a time) for eating.
  • Deadlock may occur if several philosophers try to pick up chopsticks simultaneously.

Implementing the Dining-Philosophers Algorithm

// Philosopher i process
do {
    wait(chopstick[i]);
    wait(chopstick[(i + 1) % 5]); // eat
    signal(chopstick[i]);
    signal(chopstick[(i + 1) % 5]); // think
} while (true);

Deadlock Handling Solutions

• Limit the number of philosophers sitting simultaneously at the table to 4.
• Ensure a philosopher can pick up chopsticks only if both are available.
• Implement an asymmetric grab approach based on positioning (odd/even identifiers).

Problems With Semaphores

• Common issues include incorrect operations:
  • Calling signal before wait or missing either altogether.
  • Potential for deadlock and starvation.

Monitors

• A higher abstraction for process synchronization, ensuring mutual exclusive access and hiding internal variables.
• Only one process can be active in a monitor at the same time; syntax includes procedures and shared variable declarations.

Condition Variables

• Operations allowed on a condition variable:
  • x.wait() suspends the invoking process until x.signal() is called.
  • x.signal() resumes one of the processes that invoked x.wait(), having no effect if no process is waiting.

Schematic View of a Monitor

• Layout shows shared data, operations, initialization code, and entry queue associated with condition variables.

Synchronization Examples in Operating Systems

• Windows: Uses interrupt masks and spinlocks.
• Linux: Semaphores and atomic integers, with ongoing preemptive capabilities.
• Pthreads: Offers mutex locks and condition variables as part of an OS-independent API.

Summary

• The critical section problem and related synchronization issues are foundational in operating systems to maintain consistency and avoid deadlocks, which can arise due to contention for scarce resources. Multiple strategies, including semaphores, mutex locks, and monitors, offer solutions tailored to specific synchronization challenges faced by concurrent processes.