Locks and Semaphores

Introduction

In concurrent programming, Locks and Semaphores are two fundamental synchronization primitives used to coordinate access to shared resources. They help ensure mutual exclusion, prevent race conditions, and enable safe interaction between threads or processes in parallel systems.

While both serve the broad purpose of controlling access to critical sections, they differ in capabilities, semantics, and use cases. Understanding their mechanics is essential for writing reliable, thread-safe programs.

The Problem: Race Conditions

A race condition occurs when multiple threads or processes read and write shared data simultaneously, and the final outcome depends on the timing of execution.

Example (Race Condition in C-like pseudocode)

int counter = 0;

void increment() {
    counter = counter + 1;
}

If two threads run increment() at the same time, they may both read counter as 0, increment it, and write back 1—losing one increment. This leads to data inconsistency.

Synchronization Primitives Overview

Primitive	Purpose	Guarantees
Lock (Mutex)	Mutual exclusion (1 thread at a time)	Exclusive access
Semaphore	Signaling, resource counting	Can allow more than 1 thread
Monitor	Encapsulated lock + condition vars	High-level abstraction
Barrier	Synchronization point for threads	Group wait

Locks and semaphores are low-level, but form the basis for more advanced constructs.

What Is a Lock?

A Lock (also known as a Mutex — MUTual EXclusion) is a mechanism that allows only one thread to access a critical section at a time.

Basic Operations

lock() or acquire(): Wait until the lock is available and take it.
unlock() or release(): Release the lock for others.

Example (Pseudocode)

Lock myLock;

void safe_increment() {
    myLock.lock();
    counter = counter + 1;
    myLock.unlock();
}

Only one thread at a time can execute the code between lock() and unlock().

Lock Variants

Type	Description
Spinlock	Busy-waits in a loop until the lock is available
Recursive Lock	Allows the same thread to re-acquire the lock
Read/Write Lock	Allows multiple readers or one writer
Timed Lock	Fails after timeout if lock is not acquired

What Is a Semaphore?

A Semaphore is a generalized synchronization tool that uses a counter to control access to multiple instances of a resource.

Two Types:

Counting Semaphore: Counter > 1 → multiple resources
Binary Semaphore: Counter = 0 or 1 → acts like a lock

Basic Operations

wait() or P(): Decrement the counter. If counter is 0, block.
signal() or V(): Increment the counter. If any thread is waiting, wake one.

Example (Counting Semaphore)

Semaphore chairs = 3;

void sit_down() {
    chairs.wait(); // Block if no chairs
    // Sit on chair
    chairs.signal(); // Free up a chair
}

Example (Binary Semaphore)

Semaphore mutex = 1;

void critical_section() {
    mutex.wait();
    // Do something
    mutex.signal();
}

Key Differences Between Locks and Semaphores

Feature	Lock	Semaphore
Concept	Mutual exclusion	Signaling and resource counting
Counter	No	Yes (internal counter)
Ownership	Only the thread that locks can unlock	Any thread can signal
Fairness	Depends on implementation	Can be fair or unfair
Blocking Behavior	Blocks until acquired	Can allow multiple permits

Common Use Cases

Use Case	Preferred Primitive
Protecting shared memory (1 thread)	Lock / Mutex
Managing limited resources (e.g., DB connections)	Counting Semaphore
Producer-Consumer queues	Semaphores (2 total)
Avoiding data races	Lock / Binary Semaphore
Signaling between threads	Binary Semaphore

Real-World Analogy

Lock Analogy:

A bathroom with a single key:

If someone enters and locks the door, others must wait until it’s unlocked.

Semaphore Analogy:

A parking lot with 5 spaces:

Cars enter if a space is available (semaphore counter > 0).
Once full (counter = 0), incoming cars wait.

Example: Producer-Consumer Problem

Semaphore empty = N;  // N empty slots
Semaphore full = 0;   // 0 full slots
Semaphore mutex = 1;

void producer() {
    while (true) {
        produce_item();
        empty.wait();     // Wait for empty slot
        mutex.wait();     // Enter critical section
        insert_item();
        mutex.signal();   // Leave critical section
        full.signal();    // Signal new full slot
    }
}

void consumer() {
    while (true) {
        full.wait();      // Wait for full slot
        mutex.wait();     // Enter critical section
        remove_item();
        mutex.signal();   // Leave critical section
        empty.signal();   // Signal empty slot
        consume_item();
    }
}

This classic pattern uses 3 semaphores to safely coordinate producers and consumers.

Common Issues

Issue	Cause
Deadlock	Two threads wait on each other indefinitely (circular wait)
Starvation	One thread never gets the lock due to unfair scheduling
Livelock	Threads keep changing state but make no progress
Priority Inversion	Low-priority thread holds lock needed by high-priority one

Debugging Synchronization Issues

Tools for identifying and debugging lock/semaphore issues:

ThreadSanitizer (Clang)
Helgrind (Valgrind)
Intel Inspector
Race Detector (Go runtime)
Visual Studio Concurrency Analyzer

Best Practices

Practice	Reason
Use smallest critical sections	Reduces contention and improves performance
Avoid nested locks	Prevents deadlocks
Prefer higher-level abstractions	Use `std::mutex`, `std::lock_guard`, or `synchronized` blocks
Use timeouts or try-locks	Prevent hangs in uncertain environments
Use atomic types when possible	Lightweight alternative for simple data types

High-Level Abstractions Built on Locks and Semaphores

Abstraction	Built Using	Language/Library Example
Monitor	Lock + Condition Variables	Java `synchronized`, Python `threading.Lock`
Barrier	Semaphores or Counters	OpenMP, POSIX barriers
Thread Pool	Queue + Semaphore/Locks	C++ `std::async`, Java Executor
Event Loop	Signaling Semaphores	Node.js, asyncio

Conclusion

Locks and Semaphores are foundational tools in concurrent programming. While locks enforce exclusive access, semaphores offer more generalized control over shared resources, including signaling and capacity management.

Writing correct parallel programs requires a solid understanding of these primitives, their limitations, and how to use them without introducing deadlocks, race conditions, or livelocks. Mastering them opens the door to building fast, scalable, and robust software that leverages modern multi-core and distributed systems effectively.