Session 3.2: Synchronization Solutions

Peterson's solution, hardware support, atomic operations, and memory barriers

Module 3 2 Hours Theory & Practice

Learning Objectives

By the end of this session, you will be able to:
  • Understand Peterson's solution for two-process synchronization
  • Explain hardware-based synchronization mechanisms
  • Implement atomic operations for mutual exclusion
  • Analyze test-and-set and compare-and-swap instructions
  • Understand memory barriers and their importance
  • Compare software vs hardware synchronization approaches
Key Concept

Synchronization solutions range from pure software approaches like Peterson's algorithm to hardware-supported atomic operations that provide efficient and reliable mutual exclusion.

Peterson's Solution

Two-Process Synchronization

Peterson's solution is a classic software-based approach to achieve mutual exclusion between two processes without requiring special hardware support.

Algorithm Implementation

// Shared variables
int turn;
boolean flag[2];

// Process Pi (i = 0 or 1, j = 1 - i)
do {
    flag[i] = true;        // Show interest
    turn = j;              // Give turn to other process
    while (flag[j] && turn == j);  // Wait
    
    // Critical Section
    
    flag[i] = false;       // Release interest
    
    // Remainder Section
} while (true);
How It Works
  1. Show Interest: Process sets its flag to true
  2. Be Polite: Process gives turn to the other
  3. Wait: If other is interested and has turn, wait
  4. Enter: Enter critical section when safe
  5. Release: Clear flag when done
Properties Satisfied
  • Mutual Exclusion: Only one process in CS
  • Progress: Decision made in finite time
  • Bounded Waiting: No indefinite postponement
Limitations
  • Only works for two processes
  • Requires busy waiting (CPU cycles wasted)
  • Assumes atomic load/store operations
  • May not work on modern architectures without memory barriers

Hardware-Based Solutions

Modern processors provide atomic hardware instructions that make synchronization more efficient and reliable than pure software solutions.

Test-and-Set Instruction

// Hardware instruction (atomic)
boolean test_and_set(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
}

// Using test-and-set for mutual exclusion
boolean lock = false;

do {
    while (test_and_set(&lock));  // Busy wait
    
    // Critical Section
    
    lock = false;  // Release lock
    
    // Remainder Section
} while (true);

Compare-and-Swap (CAS)

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

// Using CAS for lock-free programming
int lock = 0;

do {
    while (compare_and_swap(&lock, 0, 1) != 0);  // Acquire
    
    // Critical Section
    
    lock = 0;  // Release
    
    // Remainder Section
} while (true);
Advantages of Hardware Solutions
  • Atomic operations guaranteed by hardware
  • Work for any number of processes
  • Simple to understand and implement
  • Foundation for higher-level constructs
Disadvantages
  • Still require busy waiting
  • Can cause priority inversion
  • May not be fair (starvation possible)
  • Cache coherency overhead in multicore systems

Atomic Operations

Atomic operations are indivisible operations that complete without interruption, providing the foundation for lock-free and wait-free algorithms.

Common Atomic Operations

// Atomic increment
atomic_increment(&counter);

// Atomic decrement  
atomic_decrement(&counter);

// Atomic add
atomic_add(&value, 5);

// Atomic exchange
old_value = atomic_exchange(&var, new_value);

// Load-Link/Store-Conditional (LL/SC)
do {
    old_val = load_linked(&shared_var);
    new_val = old_val + 1;
} while (!store_conditional(&shared_var, new_val));

// Fetch-and-Add
old_value = fetch_and_add(&counter, increment);
Lock-Free Programming

Atomic operations enable lock-free data structures and algorithms that avoid the overhead and complexity of traditional locking mechanisms while ensuring thread safety.

Memory Barriers and Ordering

Modern processors may reorder memory operations for performance. Memory barriers ensure proper ordering of memory accesses in concurrent programs.

Types of Memory Barriers

Load Barrier

Ensures all load operations before the barrier complete before any load operations after it.

Store Barrier

Ensures all store operations before the barrier complete before any store operations after it.

Full Barrier

Prevents reordering of any memory operations across the barrier in either direction.

Example: Memory Ordering Problem

// Without memory barriers - may not work correctly
// Thread 1
data = 42;
flag = true;

// Thread 2  
while (!flag);
print(data);  // May print garbage!

// With memory barriers - correct behavior
// Thread 1
data = 42;
memory_barrier();  // Ensure data write completes first
flag = true;

// Thread 2
while (!flag);
memory_barrier();  // Ensure flag read completes first  
print(data);       // Guaranteed to print 42
Why Memory Barriers Matter
  • CPU caches and write buffers can delay memory updates
  • Compiler optimizations may reorder instructions
  • Multiple CPU cores have separate caches
  • Without barriers, synchronization algorithms may fail

Software vs Hardware Solutions

Software Solutions (Peterson's Algorithm)

Advantages:
  • No special hardware required
  • Provably correct
  • Educational value
Disadvantages:
  • Limited to two processes
  • Busy waiting wastes CPU
  • Complex for multiple processes
  • May fail on modern architectures

Hardware Solutions (Atomic Instructions)

Advantages:
  • Works for any number of processes
  • Simple to implement
  • Atomic guarantee by hardware
  • Foundation for higher-level constructs
Disadvantages:
  • Still involves busy waiting
  • Hardware-dependent
  • Can cause cache coherency issues

Session Summary

Key Takeaways:
  • Peterson's Solution: Classic software approach for two-process synchronization
  • Hardware Support: Atomic instructions provide efficient synchronization primitives
  • Test-and-Set/CAS: Fundamental atomic operations for mutual exclusion
  • Memory Barriers: Essential for correct behavior on modern architectures
  • Trade-offs: Software solutions are portable but limited; hardware solutions are efficient but platform-specific
Study Tips:
  • Practice implementing Peterson's algorithm
  • Understand why memory barriers are needed
  • Compare different atomic operations
  • Analyze synchronization trade-offs
Next Session:

Session 3.3: High-Level Synchronization Tools
Semaphores, mutex locks, monitors, and classic synchronization problems

Previous Session Next Session