Solutions to Process Synchronization Problems
Getting multiple processes to share resources without stepping on each other is not a simple task. Over time, four main approaches have been developed to tackle this: Locks, Semaphores, Monitors, and Interrupt Disable.
Each one works differently and fits different situations. Understanding when and why to use each mechanism is what separates a working concurrent system from a broken one.
Overview of the four main synchronization mechanisms
1. Locks
Locks are probably the most straightforward approach to synchronization. The idea is simple: before a process touches a shared resource, it grabs the lock for that resource. If another process already has the lock, the requesting process just waits until it is released. Only then can it proceed.
There are two ways locks are typically built: through software or through hardware.
Software-Based Locks
Software-based locks rely purely on algorithms to manage access. Things like flags, turn variables, or ticket systems are used to decide which process gets to enter the critical section. Some well-known examples include:
- Peterson's Algorithm: Handles mutual exclusion between two processes using a combination of a turn variable and a flag array.
- Dekker's Algorithm: A more complex take on the same two-process problem, historically the first known correct solution to mutual exclusion.
- Bakery Algorithm: Extends mutual exclusion to more than two processes using a token-based numbering system, similar to taking a number at a bakery counter.
- Test-and-Set Lock: Uses a single atomic check-and-set operation to determine if the lock is free and acquire it in one step.
Hardware-Based Locks
Hardware-based locks use special CPU instructions that are atomic, meaning once they start, they run to completion without anything else interfering. Common hardware instructions include:
- Test-and-Set (TAS): Atomically reads a memory location and sets it to 1, returning the old value. If the old value was 0, the lock has been acquired.
- Compare-and-Swap (CAS): Atomically compares a memory location to an expected value and, only if they match, replaces it with a new value.
- Fetch-and-Add: Atomically increments a value in memory and returns the original value, useful for implementing ticket locks.
2. Semaphores
Semaphores operate at the operating system level rather than the application level. At their core, a semaphore is just a non-negative integer variable that tracks resource availability. It is accessed only through two atomic operations: wait() and signal().
| Type | Value Range | Use Case |
|---|---|---|
| Binary Semaphore | 0 or 1 | Acts like a simple on/off switch for mutual exclusion. Only one process can enter the critical section. |
| Counting Semaphore | 0 to N | Tracks multiple instances of a resource. For example, allowing up to 5 simultaneous database connections. |
When a process calls wait(), the semaphore value drops by one. If it goes below zero, the process is blocked and placed in a waiting queue. When another process calls signal(), the value goes up by one and any blocked process gets woken up and given a chance to proceed.
Here is a basic example in C showing how a binary semaphore controls access to a critical section:
#include <stdio.h>
#include <semaphore.h>
#include <pthread.h>
sem_t semaphore;
void* process(void* arg) {
sem_wait(&semaphore); // Acquire (decrement)
printf("Process %d in critical section\n", *(int*)arg);
sem_post(&semaphore); // Release (increment)
return NULL;
}
int main() {
pthread_t threads[5];
int process_ids[5] = {1, 2, 3, 4, 5};
sem_init(&semaphore, 0, 1); // Initialize to 1 (binary)
for (int i = 0; i < 5; i++) {
pthread_create(&threads[i], NULL, process, &process_ids[i]);
}
for (int i = 0; i < 5; i++) {
pthread_join(threads[i], NULL);
}
sem_destroy(&semaphore);
return 0;
}Even though 5 threads are created, the binary semaphore ensures that only one thread enters the critical section at a time. Each process enters, prints its ID, exits, and then the next one gets its turn.
3. Monitors
Monitors are a cleaner, higher-level solution compared to semaphores. Instead of manually calling wait and signal everywhere in your code, a monitor packages the shared data and all the operations on it together into one unit. The rule is that only one process can be active inside the monitor at any given time, so mutual exclusion is baked in automatically.
The key advantage over semaphores is that monitors drastically reduce the chance of programmer error. With semaphores, a developer must manually remember to call wait() before entering and signal() after leaving the critical section. Forgetting either one leads to bugs that are extremely difficult to reproduce and debug. With monitors, the locking is handled behind the scenes.
4. Interrupt Disable
This is the most low-level approach of the four. When a process needs to enter its critical section, it simply turns off all hardware interrupts on the processor. Since the CPU cannot be interrupted, no context switch can occur, which means no other process can run. Once the process is done with its critical section, it turns interrupts back on.
The obvious and fatal downside is that this only works on single-processor systems. On a multi-processor machine, disabling interrupts on one CPU does absolutely nothing to stop another CPU from accessing the same shared resource at the same time. This makes interrupt disabling largely useless in modern multi-core systems.
Even on a single-processor system, keeping interrupts disabled for too long is dangerous because the system cannot respond to critical hardware events like disk I/O completions or network packets arriving.
Choosing the Right Mechanism
| Mechanism | Level | Best For | Key Limitation |
|---|---|---|---|
| Software Locks | Application | Simple mutual exclusion between a small number of processes | Complex to implement correctly, prone to subtle bugs |
| Hardware Locks | Application/Kernel | Short critical sections where spinning is acceptable | Wastes CPU cycles during long waits (busy waiting) |
| Semaphores | OS Level | Controlling access to resource pools with known capacity | Easy to misuse; forgetting signal() causes deadlocks |
| Monitors | OS/Language Level | Complex synchronization with automatic locking | Not natively supported in all programming languages |
| Interrupt Disable | Hardware/Kernel | Very short kernel-level critical sections on uniprocessors | Completely ineffective on multi-processor systems |
Knowing which mechanism to reach for is part of what makes designing concurrent systems a skill rather than just a checklist. Locks are common at the application level, semaphores and monitors handle things at the OS level, and interrupt disable is reserved for very specific low-level scenarios where a single processor is involved.