Concurrence Control

Multiprogramming introduces the possibility of concurrent execution, and if concurrent execution is not properly managed in terms of accessing shared resources (process communication), it can lead to race conditions. To avoid race conditions, synchronization mechanisms such as locks or semaphores are required. However, if these mechanisms are used improperly (e.g., inconsistent lock acquisition order), they may result in deadlock.

Mutual Exclution & Synchronization

Mutual exclusion and synchronization are two of the requirements in concurrent program.

  • Different threads share the same resource, so we need mutual exclusion to concurrently control in sapce.
  • Different threads may rely on other threads, so we need to synchronizaztion to concurrently control in timing sequence.

For example, in the producer-consumer problem:

  • Mutual Exclusion (Space): Protects access to the shared buffer using a mutex.
  • Synchronization (Timing): Ensures the producer waits if the buffer is full and the consumer waits if the buffer is empty, so they operate in the correct sequence.

Mechanisms

Mutual Exclusion: Spin lock & Mutex lock

A spinlock is a synchronization primitive that uses busy-waiting. When a thread attempts to acquire a spinlock that another thread already holds, it continuously checks the lock in a loop (spins) until the lock becomes available, which is non-blocking.

1
2
3
4
5
6
7
8
9
10
// Spin lock
void spinlock_lock(spinlock_t *s) {
    while (atomic_exchange(&s->lock, 1) != 0) {
        // busy-waiting
    }
}

void spinlock_unlock(spinlock_t *s) {
    atomic_store(&s->lock, 0);
}

A mutex is a mechanism that locks critical sections of code and only allows one thread to acquire the lock and use the resources at a time. If another thread tries to run the critical section while it’s locked, the OS puts this thread to sleep, which is blocking:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Mutex lcok
void Mutex_Lock(Mutex* mutex) {
    while (atomic_exchange(&mutex->state, 1) != 0) {
        // Add current thread to waiting queue
        Queue_Enqueue(&mutex->waiting_queue, current_thread);
		Thread_Block(current_thread);
    }
}

void Mutex_Unlock(Mutex* mutex) {
    atomic_store(&mutex->state, 0);
    // signal()
    if (!Queue_IsEmpty(&mutex->waiting_queue)) {
        Thread* next_thread = Queue_Dequeue(&mutex->waiting_queue);
        Thread_Unblock(next_thread);
    }
}

When it comes to performance, mutexes involve context switches, which can introduce significant overhead, especially if the critical section is short. This overhead arises because the operating system needs to put the thread to sleep and later wake it up.

In contrast, spinlocks don’t use context switches. Therefore, they are faster for short critical sections, but this speed comes at the cost of potentially wasting CPU cycles if the wait time for the lock to become available is longer.

Synchronizaion: Semaphore & Condition Variable

Semaphore is more powerful in terms of functionality:

  • It can achieve both mutual exclusion and synchronization.
  • A binary semaphore (initialized to 1) acts like a mutex to enforce mutual exclusion.
  • A counting semaphore (initialized to N) allows up to N threads to access a resource concurrently.
  • Semaphores inherently track state (e.g., counting mechanism), so signals are not lost if no thread is currently waiting.

Condition variable is more expressive for certain synchronization patterns:

  • It’s purely for synchronization, meaning it does not provide mutual exclusion on its own.
  • It requires an explicit lock (mutex) to protect shared data.
  • It is more suitable for event-based synchronization (e.g., producer-consumer, where a thread waits until a condition is met).
  • Unlike semaphores, if a condition variable is signaled before a thread starts waiting, the signal is lost.
1
2
3
4
5
6
7
8
9
10
11
// Templet of using condition vaiable
mutex_lock(&lk);
while (!CONDITION) {
	cond_wait(&lk, &cond_var)
}

/* critical section */

cond_signal(&lk, &cond_var)
// or cond_broadcast()
mutex_unlock(&lk);

Semaphores are lower-level and more flexible but trickier to use correctly. Condition variables make synchronization easier to reason about when dealing with complex thread interactions. If you misuse semaphores, you risk deadlocks or priority inversions. If you misuse condition variables, you risk lost signals and unexpected hangs.

Synchronization Problems

1. Producers-Consumers Problem

This classic synchronization problem consists of two types of processes: producer and consumer.

  • Producer: Generates data and places it into a shared bounded buffer (mutual exclusion) only if it’s not full (synchronization).
  • Consumer: Retrieves data from the buffer for processing only if it’s not empty.

2. Readers-Writers Problem

Different from producers-consumers problem, we distinguish between two types of processes: readers, which may want only to read the shared data; writers, which may update (to read and write) the shared data. While a reader is reading, other readers can read the shared data simultaneously because the data won’t change. However, when a writer is updating the data, no other process, including readers and writers, can access the shared data.

This problems have some variations, all involving priorities:

  • No readers be kept waiting unless a writer has already obtained the lock --> writers starvation
  • Writer perform its write as soon as possible once it is ready --> readers starvation

The readers-writer problem and its solutions can be generalized to reader-writer lock, which have read and write modes. Acquiring a reader-writer lock requires specifying the mode of the lock: read or write access.

Reader-Writer lock is suitable for some situations where reading is performed frequently while writing is in low frequency:

  1. Caching system: data will be frequently read but only be wrote when caching expires or data updating
  2. Configuration management: configuration data will be frequently read simultaneously by several threads but only when configuration updating, writing happens

3. Dining-Philosophers Problem

TODO

Reference: