Synchronisation

The scheduler decides when threads run, and this behavior is outside the programmer’s control. So threads may interleave in unpredictable ways and correctness must be reasoned about under all possible interleavings.

For example, Two threads updating a shared counter may produce incorrect results if not synchronized.

Without synchronization, one thread may overwrite another’s changes, leading to inconsistent state.

The whole problem of synchronization is addressed ensuring threads wait in the right way:

• Not too early (don’t block when resource is available).
• Not too late (don’t proceed when resource is unavailable).
• Not wastefully (avoid busy waiting).

To understand synchronisation, we need to understand the following definitions:

• Atomic Operations: Operations that appear indivisible (i.e. they are executed fully or not at all). In practice, only basic reads and writes to memory can be assumed atomic.
• Synchronization: Mechanisms to coordinate threads so they operate correctly when accessing shared resources.
• Mutual Exclusion: Ensures that only one thread at a time can enter a critical section (a block of code accessing shared resources).
• Critical Region: The portion of code where shared resources are accessed and must be protected to avoid race conditions.

Since complex operations (like incrementing a counter) are not atomic, we must enforce atomicity using locks:

• A lock is acquired before entering the critical region.
• While the lock is held, no other thread can enter that region.
• The lock is released after the operation completes.

lock(mutex);
counter = counter + 1;  // critical region
unlock(mutex);

With the lock, increments happen sequentially, preserving correctness.

Example: Red Black Trees

A red-black tree is a type of self-balancing binary search tree.

The balancing is achieved by enforcing rules about node colors (red or black) and their arrangement, preventing the tree from becoming skewed.

Operating systems often need efficient data structures for:

• Scheduling tasks (e.g., Linux uses red-black trees for process scheduling).
• Memory management (tracking free memory blocks).
• File systems (indexing and searching).

The guarantee of logarithmic time complexity makes red-black trees ideal for these performance-critical tasks. However, this comes with issues when multiple threads or processes access the tree concurrently.

A common approach is to lock the root before performing operations:

• This ensures consistency and prevents race conditions.
• However, it introduces a bottleneck: only one thread can operate at a time, even if they want to work on different parts of the tree.

  Even if two operations target completely different subtrees, they must wait for the lock.

To overcome this bottleneck, operating systems and concurrent data structure designers explore:

• Fine-grained locking:
  • Instead of locking the root, locks are applied to specific nodes or subtrees.
  • This allows multiple threads to work in parallel, provided they don’t overlap.
• Lock-free data structures:
  • Use atomic operations (like compare-and-swap) to update nodes without traditional locks.
  • These are complex to implement but can greatly improve concurrency.
• Read-Write locks:
  • Multiple readers can access the tree simultaneously.
  • Writers still need exclusive access, but this improves performance when reads dominate.

More broadly, this section highlights a fundamental tension: data structure efficiency vs. concurrency control. Red-black trees are powerful, but their usefulness in parallel environments depends on how locking is managed.

Beyond Locks

Here, we consider whether the lock is the ideal mechanism for synchronization. The example we look at is a circular buffer where locks present a problem.

A circular buffer (or ring buffer) is a fixed-size data structure where the end wraps around to the beginning.

It’s commonly used in operating systems for producer-consumer scenarios:

• Producer writes data into the buffer.
• Consumer reads data out.

To coordinate access, we need atomic operations (operations that complete without interruption).

For example, incrementing a buffer index must be atomic, otherwise two producers could corrupt the index.

If synchronization is done with locks, we could run into two issues:

Busy Waiting

Busy waiting occurs when a process repeatedly checks a condition in a loop, consuming CPU cycles while waiting for a resource to become available.

Imagine a producer-consumer system with a circular buffer:

• The producer wants to add data, but the buffer is full.
• Instead of sleeping, it spins in a loop checking if space is available.

While spinning, the producer consumes CPU time but makes no progress. The processor is doing “work” that doesn’t advance the system.

In early multiprocessor systems, spinlocks were common because context switching was expensive. But in modern systems with many threads, busy waiting is unacceptable for long waits (e.g., disk I/O, network I/O).

Livelock

Livelock occurs when processes are not blocked—they keep running—but they continually interfere with each other, preventing progress.

Two processes attempt to acquire a lock:

• Each detects contention and politely backs off (e.g., releases the lock and retries).
• Unfortunately, they both retry at the same time, collide again, and back off again.

Both are “active,” but neither succeeds in acquiring the lock. The system appears busy, but useful work isn’t happening. Unlike deadlock (where processes are frozen), livelock looks like activity.

Livelock can occur in priority inversion scenarios. A high-priority task keeps retrying but is constantly preempted by lower-priority tasks trying to “help.”

Locks are too primitive. They only enforce mutual exclusion. They don’t encode coordination logic (e.g., “wait until buffer has space” or “signal when resource is free”).

In general, operating systems need synchronization mechanisms that encode correct behavior by design.

Semaphores (and related abstractions like condition variables and monitors) solve this by:

• Allowing processes to block instead of spin (avoiding busy waiting).
• Structuring wait/signal semantics so processes don’t interfere endlessly (avoiding livelock).
• Encoding resource availability directly in the synchronization primitive, making code correct by design.

Refer to Semaphores.