Hardware Synchronization, Mutex Locks, and Semaphores

Memory Barriers and Hardware Synchronization Foundations

• Memory barriers (also known as memory fences) provide a basic architectural instruction that guarantees all preceding instructions are completely executed before any subsequent instructions are permitted to execute.

• Hardware synchronization support is an absolute prerequisite for implementing higher-level software synchronization tools such as mutex locks and semaphores; without underlying processor support, synchronization cannot be guaranteed.

• The core requirement of synchronization hardware is providing atomic instructions that guarantee that when a shared status or lock value is modified, the operation executes without interruption and completely blocks competing updates from other processors or cores.

• In modern multi-core and multiprocessor architectures, multiple threads or processes can be scheduled simultaneously across distinct execution cores; multiple instructions can be initiated at the exact same clock cycle.

• The Central Processing Unit (CPU) must enforce at the hardware level that if multiple processors attempt to modify a synchronization variable concurrently, exactly one process succeeds in making progress, while all competing processes are suspended or prevented from altering the state.

Critical-Section Problem and Architectural Solutions

• The critical-section problem requires coordinating processes that access shared variables or data structures such as a critical section.

• The complete structural layout of a cooperating process consists of four sequential sections:

  • Entry Section: The code preceding the critical section where a process requests permission to access the critical resource.

  • Critical Section: The block of code where shared resources, variables, or files are accessed and modified.

  • Exit Section: The code immediately following the critical section where the lock or resource status is released.

  • Remainder Section: The remaining operational code executed by the process after leaving the exit section.

• Any valid solution to the critical-section problem must satisfy three fundamental requirements:

  • Mutual Exclusion: If a process is executing in its critical section, no other processes are allowed to execute in their critical sections simultaneously.

  • Progress: If no process is executing in its critical section and there are processes wishing to enter, only those processes not executing in their remainder sections can participate in deciding which process enters next, and this selection cannot be postponed indefinitely.

  • Bounded Waiting: A bound or limit must exist on the number of times other processes are allowed to enter their critical sections after a process has made an entry request and before that request is granted, preventing process starvation.

• Locking mechanism abstraction:

  • Entry section acquires the lock by verifying whether it is free; if free, it takes ownership of the lock.

  • Exit section releases the lock, restoring its status so other waiting processes can acquire it.

  • Lock status is represented by a shared variable (such as a boolean or an integer).

  • In pass-by-reference parameter passing (signified in C-style syntax by the address-of operator &, such as &lock), the memory address of the variable is passed to the function, enabling direct in-place modification of the memory cell.

  • Pass-by-value merely provides a local copy to the receiving function, leaving the original memory address unaltered.

Hardware Instruction: Test and Set

• test_and_set is a low-level atomic hardware instruction provided by CPU instruction sets under various architecture-specific instruction names.

• Internal behavioral definition of test_and_set:

  • Accepts a pointer to a target boolean variable: boolean test_and_set(boolean *target)

  • Copies the original value stored at the target address into a local return variable: boolean rv = *target;

  • Overwrites the memory cell of target with true: *target = true;

  • Returns the original value stored in rv: return rv;

  • Entire sequence executes atomically; the CPU guarantees it cannot be preempted or interrupted mid-execution.

• Implementation of mutual exclusion using test_and_set:

  • A shared boolean variable lock is initialized to false (where false indicates the critical section is unlocked and open).

  • Process entry section executes a busy-waiting spin lock: while (test_and_set(&lock));

  • Process exit section executes: lock = false;

• Execution trace for a single process entering the critical section:

  • Initial state: lock = false.

  • Process invokes test_and_set(&lock).

  • Inside test_and_set, rv receives false, lock is updated to true, and the instruction returns false.

  • The while loop condition receives false, terminating the loop immediately.

  • The process enters and executes its critical section.

• Execution trace for competing processes attempting entry while lock = true:

  • Competing processes invoke test_and_set(&lock).

  • Because lock is already true, rv receives true, lock remains written as true, and test_and_set returns true.

  • The while loop condition evaluates to true, causing competing processes to repeatedly spin in the while loop (busy waiting / spin lock).

  • When the owning process executes the exit section (lock = false;), the lock returns to false.

  • At that point, the next execution of test_and_set(&lock) by a waiting process will return false, allowing that process to exit the loop and enter the critical section.

• Hardware arbitration in multi-core systems:

  • If two or more cores initiate test_and_set on the identical memory address at the exact same clock cycle, hardware bus arbitration or memory locking guarantees that exactly one core executes the instruction first and receives false.

  • The remaining cores execute sequentially after the lock value has transitioned to true, receiving true and remaining trapped in their spin locks.

Hardware Instruction: Compare and Swap

• compare_and_swap is an alternative hardware instruction operating on integer variables that performs atomic comparison and conditional assignment.

• Internal behavioral definition of compare_and_swap:

  • Accepts three parameters: a pointer to an integer variable, an expected value, and a new target value: int compare_and_swap(int *value, int expected, int new_value)

  • Preserves the current value in a temporary local variable: int temp = *value;

  • Conditionally evaluates whether the current value matches expected: if (*value == expected) *value = new_value;

  • Returns the original value: return temp;

  • Executed as an uninterruptible, atomic hardware instruction.

• Implementation of mutual exclusion using compare_and_swap:

  • A shared integer variable lock is initialized to $0$.

  • Process entry section executes: while (compare_and_swap(&lock, 0, 1) != 0);

  • Process exit section executes: lock = 0;

• Execution trace of compare_and_swap:

  • When lock is $0$, a process calls compare_and_swap(&lock, 0, 1).

  • temp is assigned $0$.

  • The condition *value == expected evaluates to 0 == 0 (true); lock is updated to $1$.

  • The function returns $0$.

  • The loop condition 0 != 0 evaluates to false, terminating the spin lock and admitting the process to the critical section.

  • If subsequent processes execute compare_and_swap(&lock, 0, 1) while lock is $1$, temp receives $1$, the condition 1 == 0 evaluates to false (leaving lock unchanged at $1$), and the function returns $1$.

  • The loop condition 1 != 0 evaluates to true, holding competing processes in a busy wait until the lock is reset to $0$ in the exit section.

Bounded-Waiting Mutual Exclusion Algorithm Using Test and Set

• While simple test_and_set and compare_and_swap loops guarantee mutual exclusion and progress, they do not guarantee bounded waiting because process selection among spinning threads is arbitrary.

• An enhanced algorithm utilizing test_and_set satisfies all three requirements (Mutual Exclusion, Progress, and Bounded Waiting) for $n$ processes.

• Shared data structures and initializations:

  • boolean waiting[n]; where every element is initialized to false.

  • boolean lock; initialized to false.

  • Each process $P_i$ maintains a local boolean variable key.

• Algorithmic structure for process $P_i$:

  • Entry Section:

  • waiting[i] = true;

  • key = true;

  • while (waiting[i] && key)

  • key = test_and_set(&lock);

  • waiting[i] = false;

  • Critical Section:

  • Code accessing shared resources.

  • Exit Section:

  • j = (i + 1) % n;

  • while ((j != i) && !waiting[j])

  • j = (j + 1) % n;

  • if (j == i)

  • lock = false;

  • else

  • waiting[j] = false;

  • Remainder Section:

  • Non-critical process operations.

• Detailed trace of the entry section:

  • Process $P_i$ announces its intent to enter by asserting waiting[i] = true and initial key = true.

  • It enters the while loop, executing key = test_and_set(&lock).

  • If lock was false, test_and_set returns false, causing key to become false.

  • The condition waiting[i] && key evaluates to true && false, which is false, exiting the loop.

  • Process sets waiting[i] = false and enters the critical section.

  • If other processes $P_j$ attempt to enter while $P_i$ is in the critical section, lock is true, so test_and_set(&lock) consistently returns true.

  • Because waiting[j] remains true and key remains true, waiting[j] && key evaluates to true && true, confining all competing processes to their spin locks.

• Detailed trace of the exit section and handover:

  • Upon completing its critical section, process $P_i$ scans the waiting array in circular order starting at index $j = (i + 1) \pmod n$.

  • The loop while ((j != i) && !waiting[j]) advances $j$ cyclically as long as process $P_j$ is not waiting (!waiting[j] is true).

  • If no processes are waiting, the cycle completes such that $j == i$. Process $P_i$ sets lock = false, leaving the lock available for any future process.

  • If a waiting process $P_j$ is discovered ($waiting[j] == true$), the loop terminates with $j \neq i$.

  • Process $P_i$ executes waiting[j] = false; without resetting lock to false.

• Verification of the three requirements:

  • Mutual Exclusion: A process can enter the critical section only if waiting[i] == false or key == false. When a process enters, lock is true. Even if another process resets its own key, lock remains true. Only the designated process chosen by the exit section has its waiting flag set to false, guaranteeing only one process enters at any time.

  • Progress: If a process leaves the critical section and other processes are waiting, the exit section designates a specific waiting process or sets lock = false, ensuring an unblocked process immediately enters without hindrance.

  • Bounded Waiting: The cyclic scan ($i + 1, i + 2, \dots$) ensures that any waiting process will be serviced within at most $n - 1$ turns, eliminating indefinite postponement or starvation.

Mutex Locks

• Mutex (mutual exclusion) locks represent a software-level synchronization tool built upon hardware atomic primitives to protect critical sections.

• A mutex lock utilizes a boolean variable available indicating whether the lock is obtainable.

• Two fundamental operations manage the mutex lock:

  • acquire(): Invoked in the entry section to obtain the lock.

  • release(): Invoked in the exit section to relinquish the lock.

• Structural implementation of acquire():

  • acquire() {

  • while (!available); // busy wait

  • available = false;

  • }

  • The testing of available and its transition to false must be executed atomically via underlying instructions like test_and_set to prevent multiple threads from acquiring the lock concurrently.

• Structural implementation of release():

  • release() {

  • available = true;

  • }

• A mutex lock implemented with busy waiting is classified as a spinlock; processes repeatedly execute a loop checking the availability condition, consuming CPU cycles while waiting.

Semaphores: Definition, Operations, and Types

• A semaphore is a synchronization tool represented by an integer variable $S$.

• Classical synchronization defines two standard atomic operations on a semaphore: wait() and signal() (historically designated as $P$ for proberen, to test, and $V$ for verhogen, to increment).

• Definition of wait(S) (utilized in the entry section):

  • wait(S) {

  • while (S <= 0); // busy wait

  • S--;

  • }

  • If $S \le 0$, the executing process is blocked in a busy wait; once $S > 0$, the process decrements $S$ and proceeds.

• Definition of signal(S) (utilized in the exit section):

  • signal(S) {

  • S++;

  • }

  • Increments the value of semaphore $S$ atomically.

• All modifications to the integer value of $S$ in wait() and signal() must execute atomically and indivisibly without preemption.

• Classification of semaphores based on integer range:

  • Binary Semaphore: The value of $S$ is restricted to $0$ and $1$. A binary semaphore functions identically to a mutex lock, where $1$ denotes available and $0$ denotes locked.

  • Counting Semaphore: The value of $S$ can range over an unrestricted domain ($0, 1, 2, 3, \dots$), used to control access to a finite set of identical resources.

Controlling Execution Path Using Semaphores

• Semaphores can enforce deterministic execution orderings across concurrent processes, guaranteeing that specific statements execute in a defined sequence regardless of CPU scheduling order.

• Scenario: Enforce that statement $S_1$ in process $P_1$ executes strictly before statement $S_2$ in process $P_2$.

• Mechanism:

  • Define a shared synchronization semaphore: semaphore synch; initialized to $0$.

  • Process $P_1$ code structure:

  • S1;

  • signal(synch);

  • Process $P_2$ code structure:

  • wait(synch);

  • S2;

• Execution trace:

  • If $P_2$ is scheduled first, it executes wait(synch). Because synch is $0$, the condition synch <= 0 holds, forcing $P_2$ to busy-wait.

  • When $P_1$ executes, it completes statement $S_1$ and executes signal(synch), which increments synch from $0$ to $1$.

  • $P_2$ detects synch == 1, exits its wait loop, decrements synch back to $0$, and executes statement $S_2$.

  • If $P_1$ is scheduled first, it completes $S_1$, signals synch (setting it to $1$), and when $P_2$ arrives at wait(synch), it proceeds immediately without waiting.

Questions & Discussion: In-Class Exercise 7

• Problem Formulation:

  • Design a synchronization scheme using semaphores for four processes ($P_1$, $P_2$, $P_3$, and $P_4$) submitted to the ready queue in arbitrary order (e.g., $P_4$, then $P_2$, then $P_3$, then $P_1$).

  • Execution Constraint: Process $P_1$ must always execute first. Once $P_1$ completes, processes $P_2$ and $P_3$ can execute concurrently. Process $P_4$ can start execution only after both $P_2$ and $P_3$ have fully completed their work.

• Implementation Steps Proposed:

  • To block $P_2$ and $P_3$ until $P_1$ finishes, declare two separate semaphores, a and b, both initialized to $0$:

  • semaphore a = 0;

  • semaphore b = 0;

  • Process $P_2$ executes wait(a) at its entry.

  • Process $P_3$ executes wait(b) at its entry.

• Dialogue on Coordinating Completion:

  • Prompt: Which process should call signal(b) and signal(c)?

  • Response: Process $P_1$ must call signal(a) and signal(b) upon completing its execution.

  • Prompt: How should $P_2$ and $P_3$ signal the completion of their tasks to enable $P_4$?

  • Response: Processes $P_2$ and $P_3$ could both invoke signal(c) on a shared semaphore c (initialized to $0$), while $P_4$ precedes its execution with wait(c).

• Inherent Race Condition Flaw Identified:

  • In a proposed scheme where $P_2$ calls signal(c), $P_3$ calls signal(c), and $P_4$ executes a single wait(c):

  • If process $P_2$ finishes its job while process $P_3$ is still executing, $P_2$ invokes signal(c), incrementing c from $0$ to $1$.

  • Process $P_4$, blocked at wait(c), sees c == 1, decrements c to $0$, and proceeds to execute its task.

  • Consequently, process $P_4$ and process $P_3$ run concurrently, directly violating the prerequisite condition that $P_4$ must wait until both $P_2$ and $P_3$ have finished.

  • Resolving this race condition requires an additional synchronization mechanism (such as multiple semaphores, barrier synchronization, or a counter) to ensure $P_4$ is unblocked only when both predecessors have finished.