Introduction

Threads within the same process commonly share global variables, heap objects, files, sockets and other process resources. Shared access is efficient, but concurrent operations can interfere with one another when ordering and ownership are not controlled.

Synchronization is the coordination of concurrent execution so that shared state remains valid and operations occur according to the required ordering rules.

Synchronization can be used to:

• Protect shared mutable data
• Allow only one thread to execute a critical section
• Limit concurrent access to a resource
• Make one thread wait until a condition becomes true
• Coordinate producer and consumer threads
• Establish ordering between operations
• Publish completed data safely to another thread
• Coordinate phases of parallel computation

In your System Design curriculum, Synchronization is Topic 2.3 under Computer Systems, Linux and Concurrency. The topic follows processes versus threads and prepares learners for race conditions and deadlocks.

Prerequisites

Shared Mutable State

Shared mutable state is data that can be accessed by more than one execution context and can change during program execution.

static int shared_counter = 0;

If two threads update this variable without coordination, the final result can depend on how their instructions are interleaved.

Increment Is a Read-Modify-Write Operation

Thread A reads counter: 10
Thread B reads counter: 10

Thread A calculates: 11
Thread B calculates: 11

Thread A stores: 11
Thread B stores: 11

Expected after two increments: 12
Observed result: 11

A source statement such as ++shared_counter should not be assumed to perform one indivisible operation.

Critical Section

A critical section is a region of code that accesses shared state or a shared resource and must follow a synchronization rule.

Acquire synchronization primitive
        |
        v
Enter critical section
        |
        | Read or modify protected state
        v
Restore the protected invariant
        |
        v
Release synchronization primitive

Protected Invariant Example

Invariant:

available_items must remain between 0 and capacity.

Protected operations:

- Add an item
- Remove an item
- Update queue indexes
- Update the current item count

The lock should protect the complete invariant rather than one isolated variable when several fields must change consistently.

Mutual Exclusion

Mutual exclusion ensures that only one participating thread enters a protected critical section at a time.

Thread A requests lock
        |
        v
Thread A enters critical section

Thread B requests same lock
        |
        v
Thread B waits

Thread A releases lock
        |
        v
Thread B can acquire lock

Mutual exclusion is commonly implemented through a mutex.

Mutex

A mutex is a synchronization primitive with an ownership model. A thread acquires the mutex before accessing protected state and releases it after restoring the state invariant.

Conceptual Pattern

lock(&mutex);

/*
 * Access or modify the shared state.
 */

unlock(&mutex);

POSIX Mutex Example

The following example uses POSIX threads. POSIX thread functions are not part of ISO C.

#define _POSIX_C_SOURCE 200809L

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

enum
{
    THREAD_COUNT = 4,
    INCREMENTS_PER_THREAD = 100000
};

static long long shared_counter = 0;

static pthread_mutex_t counter_mutex =
    PTHREAD_MUTEX_INITIALIZER;

static void *increment_counter(
    void *argument)
{
    (void)argument;

    for (int index = 0;
         index < INCREMENTS_PER_THREAD;
         ++index) {

        int status =
            pthread_mutex_lock(
                &counter_mutex
            );

        if (status != 0) {
            return NULL;
        }

        ++shared_counter;

        status =
            pthread_mutex_unlock(
                &counter_mutex
            );

        if (status != 0) {
            return NULL;
        }
    }

    return NULL;
}

int main(void)
{
    pthread_t threads[
        THREAD_COUNT
    ];

    int created = 0;

    for (int index = 0;
         index < THREAD_COUNT;
         ++index) {

        int status =
            pthread_create(
                &threads[index],
                NULL,
                increment_counter,
                NULL
            );

        if (status != 0) {
            fprintf(
                stderr,
                "Unable to create thread %d.\n",
                index
            );

            break;
        }

        ++created;
    }

    for (int index = 0;
         index < created;
         ++index) {

        if (pthread_join(
                threads[index],
                NULL) != 0) {

            fprintf(
                stderr,
                "Unable to join thread %d.\n",
                index
            );

            return EXIT_FAILURE;
        }
    }

    printf(
        "Final counter: %lld\n",
        shared_counter
    );

    if (pthread_mutex_destroy(
            &counter_mutex) != 0) {

        return EXIT_FAILURE;
    }

    return
        created == THREAD_COUNT
            ? EXIT_SUCCESS
            : EXIT_FAILURE;
}

Compile

cc -std=c17 -Wall -Wextra -Wpedantic -pthread mutex_counter.c -o mutex_counter

Program Analysis

1. All worker threads access the same counter.
2. The mutex protects every increment.
3. Only one participating thread performs the read-modify-write operation at a time.
4. The mutex is released after the shared update is complete.
5. The main thread joins every successfully created worker.
6. The mutex is destroyed only after no worker can use it.

Lock Contention

Contention occurs when multiple threads compete for the same synchronization primitive.

Low contention:
Thread usually acquires the lock immediately.

High contention:
Several threads wait for one protected resource.
Waiting time increases.
Parallel execution decreases.

Contention can increase because of:

• Large critical sections
• Too many participating threads
• Slow work performed while holding a lock
• One global lock protecting unrelated data
• Hot shared counters or collections
• Lock acquisition in a high-frequency code path

Avoid Slow I/O While Holding a Lock

pthread_mutex_lock(
    &state_mutex
);

update_shared_state();

send_to_remote_service();

pthread_mutex_unlock(
    &state_mutex
);

struct Message message;

pthread_mutex_lock(
    &state_mutex
);

update_shared_state();

message =
    build_message_from_state();

pthread_mutex_unlock(
    &state_mutex
);

send_to_remote_service(
    &message
);

This pattern is appropriate only when the copied message remains valid and the remote operation does not need the state to remain locked.

Lock Granularity

Lock granularity describes how much state one lock protects.

Semaphore

A semaphore maintains a count that can represent available permits or resources.

Common conceptual operations are:

• Wait or acquire: consume one permit, waiting when no permit is available.
• Post or release: return one permit and potentially wake a waiting thread.

Connection-limit Example

Database allows 20 concurrent operations.

Semaphore initial value: 20

Before using database connection:
Acquire one permit.

After completing operation:
Release one permit.

A semaphore is useful when concurrency must be limited to a known resource capacity.

POSIX Semaphore Example

#define _POSIX_C_SOURCE 200809L

#include <errno.h>
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum
{
    WORKER_COUNT = 6,
    MAXIMUM_CONCURRENT_WORKERS = 2
};

static sem_t work_permits;

static void simulate_work(
    void)
{
    struct timespec duration = {
        .tv_sec = 0,
        .tv_nsec = 200000000L
    };

    nanosleep(
        &duration,
        NULL
    );
}

static int wait_for_permit(
    sem_t *semaphore)
{
    for (;;) {
        if (sem_wait(
                semaphore) == 0) {

            return 1;
        }

        if (errno != EINTR) {
            return 0;
        }
    }
}

static void *worker(
    void *argument)
{
    int worker_id =
        *(const int *)argument;

    if (!wait_for_permit(
            &work_permits)) {

        return NULL;
    }

    printf(
        "Worker %d entered.\n",
        worker_id
    );

    simulate_work();

    printf(
        "Worker %d leaving.\n",
        worker_id
    );

    if (sem_post(
            &work_permits) != 0) {

        return NULL;
    }

    return NULL;
}

int main(void)
{
    if (sem_init(
            &work_permits,
            0,
            MAXIMUM_CONCURRENT_WORKERS) != 0) {

        perror(
            "sem_init"
        );

        return EXIT_FAILURE;
    }

    pthread_t threads[
        WORKER_COUNT
    ];

    int identifiers[
        WORKER_COUNT
    ];

    int created = 0;

    for (int index = 0;
         index < WORKER_COUNT;
         ++index) {

        identifiers[index] =
            index + 1;

        if (pthread_create(
                &threads[index],
                NULL,
                worker,
                &identifiers[index]) != 0) {

            break;
        }

        ++created;
    }

    for (int index = 0;
         index < created;
         ++index) {

        pthread_join(
            threads[index],
            NULL
        );
    }

    if (sem_destroy(
            &work_permits) != 0) {

        return EXIT_FAILURE;
    }

    return
        created == WORKER_COUNT
            ? EXIT_SUCCESS
            : EXIT_FAILURE;
}

Compile

cc -std=c17 -Wall -Wextra -Wpedantic -pthread semaphore_limit.c -o semaphore_limit

Condition Variable

A condition variable allows threads to wait until shared state may satisfy a required condition.

Condition variables are commonly used with mutexes:

1. Acquire the mutex protecting the shared state.
2. Check the required predicate.
3. Wait while the predicate is false.
4. The wait operation releases the mutex while the thread sleeps.
5. After waking, the mutex is reacquired.
6. Check the predicate again.

Correct Wait Pattern

pthread_mutex_lock(
    &mutex
);

while (!condition_is_true()) {
    pthread_cond_wait(
        &condition,
        &mutex
    );
}

/*
 * Protected state satisfies
 * the required predicate.
 */

pthread_mutex_unlock(
    &mutex
);

A waiting thread must recheck the predicate because another thread may consume or change the state before the awakened thread continues, and condition waits can return without the application condition being true.

if (!data_ready) {
    pthread_cond_wait(
        &condition,
        &mutex
    );
}

use_data();

while (!data_ready) {
    pthread_cond_wait(
        &condition,
        &mutex
    );
}

use_data();

Producer-Consumer Pattern

In the producer-consumer pattern, producer threads create items and consumer threads process them.

Producer Threads
       |
       | Add items
       v
Bounded Shared Queue
       |
       | Remove items
       v
Consumer Threads

The queue has two important predicates:

• The queue is not full, allowing a producer to add an item.
• The queue is not empty, allowing a consumer to remove an item.

Bounded Queue Structures

enum
{
    QUEUE_CAPACITY = 8
};

struct WorkQueue
{
    int items[QUEUE_CAPACITY];
    size_t head;
    size_t tail;
    size_t count;
    int closed;

    pthread_mutex_t mutex;
    pthread_cond_t not_empty;
    pthread_cond_t not_full;
};

Add an Item

static int queue_push(
    struct WorkQueue *queue,
    int value)
{
    if (queue == NULL) {
        return 0;
    }

    if (pthread_mutex_lock(
            &queue->mutex) != 0) {

        return 0;
    }

    while (queue->count ==
               QUEUE_CAPACITY
           && !queue->closed) {

        if (pthread_cond_wait(
                &queue->not_full,
                &queue->mutex) != 0) {

            pthread_mutex_unlock(
                &queue->mutex
            );

            return 0;
        }
    }

    if (queue->closed) {
        pthread_mutex_unlock(
            &queue->mutex
        );

        return 0;
    }

    queue->items[
        queue->tail
    ] = value;

    queue->tail =
        (queue->tail + 1)
        % QUEUE_CAPACITY;

    ++queue->count;

    pthread_cond_signal(
        &queue->not_empty
    );

    pthread_mutex_unlock(
        &queue->mutex
    );

    return 1;
}

Remove an Item

static int queue_pop(
    struct WorkQueue *queue,
    int *value)
{
    if (queue == NULL ||
        value == NULL) {

        return 0;
    }

    if (pthread_mutex_lock(
            &queue->mutex) != 0) {

        return 0;
    }

    while (queue->count == 0
           && !queue->closed) {

        if (pthread_cond_wait(
                &queue->not_empty,
                &queue->mutex) != 0) {

            pthread_mutex_unlock(
                &queue->mutex
            );

            return 0;
        }
    }

    if (queue->count == 0
        && queue->closed) {

        pthread_mutex_unlock(
            &queue->mutex
        );

        return 0;
    }

    *value =
        queue->items[
            queue->head
        ];

    queue->head =
        (queue->head + 1)
        % QUEUE_CAPACITY;

    --queue->count;

    pthread_cond_signal(
        &queue->not_full
    );

    pthread_mutex_unlock(
        &queue->mutex
    );

    return 1;
}

Close the Queue

static int queue_close(
    struct WorkQueue *queue)
{
    if (queue == NULL ||
        pthread_mutex_lock(
            &queue->mutex) != 0) {

        return 0;
    }

    queue->closed = 1;

    pthread_cond_broadcast(
        &queue->not_empty
    );

    pthread_cond_broadcast(
        &queue->not_full
    );

    pthread_mutex_unlock(
        &queue->mutex
    );

    return 1;
}

Broadcasting during closure wakes producers and consumers so they can inspect the closed state and terminate according to the queue contract.

Mutex vs Semaphore vs Condition Variable

These primitives can work together. A bounded queue can use:

• A mutex to protect queue fields
• A condition variable for the not-empty predicate
• A condition variable for the not-full predicate

Read-Write Lock

A read-write lock distinguishes shared read access from exclusive write access.

• Several readers may hold the lock concurrently.
• A writer requires exclusive access.
• Reader and writer admission follows the implementation's policy.

Readers:
Reader A ----+
Reader B ----+--> Shared read access
Reader C ----+

Writer:
Writer A --------> Exclusive write access

Read-write locks are not automatically faster than mutexes. They add coordination overhead and can create reader or writer starvation depending on policy and workload.

Atomic Operations

Atomic operations perform selected operations without exposing a partial update to other participating threads.

C Atomic Counter

#include <stdatomic.h>

static atomic_ullong request_count = 0;

static void record_request(
    void)
{
    atomic_fetch_add_explicit(
        &request_count,
        1u,
        memory_order_relaxed
    );
}

Relaxed ordering can be appropriate for an independent statistical counter when no other state is published through the counter. It is not a general replacement for synchronization around compound invariants.

atomic_int available;
atomic_int reserved;

/*
 * Updating both independently does not
 * automatically preserve a relationship
 * between them.
 */

struct Inventory
{
    int available;
    int reserved;
    pthread_mutex_t mutex;
};

Choose a mutex or another coordinated design when several values must change consistently as one logical operation.

Barrier

A barrier coordinates several participating threads at the end of a processing phase. Threads wait until the required number of participants reaches the barrier.

Phase 1:

Thread A ---------> Barrier
Thread B -------------> Barrier
Thread C -------> Barrier

All required threads arrive.

Phase 2 begins.

Barriers are useful for:

• Parallel simulation steps
• Multi-stage numerical processing
• Data-parallel transformations
• Coordinated test execution

A barrier design must define what happens when a participant fails, terminates or never arrives.

Busy Waiting

Busy waiting repeatedly checks a condition instead of blocking.

while (!data_ready) {
    /*
     * Repeatedly check.
     */
}

Busy waiting can consume CPU capacity while no useful work is completed. Blocking synchronization is normally preferable when the expected wait is not extremely short or when the platform cannot justify spinning.

pthread_mutex_lock(
    &mutex
);

while (!data_ready) {
    pthread_cond_wait(
        &condition,
        &mutex
    );
}

pthread_mutex_unlock(
    &mutex
);

Some low-level synchronization primitives use controlled spinning before blocking. Such behaviour should be selected through platform knowledge and measurement rather than implemented as an unrestricted application loop.

Memory Visibility

Synchronization is concerned not only with preventing simultaneous updates. It also establishes when one thread's completed writes become safely observable by another participating thread.

Producer thread:

Lock
Write data
Set ready state
Unlock
Notify


Consumer thread:

Lock
Check ready state
Read published data
Unlock

Accessing the shared state through a common synchronization protocol allows the consumer to observe the published data according to that protocol.

Ownership as Synchronization

Not every design requires several threads to mutate the same object. Assigning one owner can reduce synchronization complexity.

Worker Threads
      |
      | Submit commands
      v
Owner Thread
      |
      | Exclusively updates state
      v
Shared Logical Resource

Single-owner designs can use:

• Message passing
• Task queues
• Immutable snapshots
• Partitioned state
• Per-thread accumulators

Per-thread Aggregation

Thread A -> Local total A
Thread B -> Local total B
Thread C -> Local total C

After completion:

Final total = A + B + C

This design can avoid a heavily contended shared counter during the main processing phase.

Timed Waiting

Indefinite waiting can make shutdown and failure recovery difficult. Selected synchronization operations support deadlines or timeouts.

A timed wait should define:

• The deadline or duration
• Which clock is used
• What timeout means to the caller
• Whether the operation is retried
• How cancellation and shutdown are handled
• Whether partial state must be cleaned up

A timeout does not prove that the required operation failed permanently. It proves only that the required condition was not observed within the defined waiting period.

Graceful Shutdown

Synchronization design must include shutdown behaviour.

Shutdown requested
       |
       v
Stop accepting new work
       |
       v
Mark queue closed
       |
       v
Wake waiting producers and consumers
       |
       v
Drain or cancel work according to policy
       |
       v
Join worker threads
       |
       v
Destroy synchronization objects

Destroying a mutex, condition variable or shared queue while another thread may still access it creates an unsafe lifetime condition.

Synchronization Performance

Synchronization can affect performance through:

• Lock acquisition and release
• Waiting and wake-up operations
• Context switching
• Cache-line movement between processor cores
• Serialization of otherwise parallel work
• Contention and queueing
• False sharing

False Sharing

False sharing can occur when separate variables used by different threads occupy the same cache line. Even though the threads modify different variables, processor cache-coherence activity can reduce performance.

One cache line:

+----------------+----------------+
| Thread A field | Thread B field |
+----------------+----------------+

Thread A writes its field.
Thread B writes its field.

The cache line can move repeatedly
between processor cores.

Diagnose false sharing with appropriate profiling evidence before changing structure layout.

Choosing a Synchronization Method

Common Synchronization Mistakes

Synchronization Testing

Concurrency tests should attempt to expose different execution orderings rather than validating one successful run.

Thread Sanitizer Build

A supported compiler can provide race-detection instrumentation. Support and behaviour depend on the platform and toolchain.

cc -std=c17 -Wall -Wextra -Wpedantic -g -O1 -fsanitize=thread -pthread program.c -o program

Dynamic race detection observes executed paths only. A clean run does not prove that every possible execution is race-free.

Linux Observation Commands

Inspect Process Threads

ps -T -p PROCESS_ID

Interactive Thread Activity

top -H -p PROCESS_ID

Context-switch Activity

pidstat -w -p PROCESS_ID 1

Profile CPU Behaviour

perf stat ./program

Tool availability, permissions and output vary by Linux environment.

Synchronization Best Practices

Practice Exercise

Design a synchronized task queue containing several producer and consumer threads.

Requirements

1. The queue has a fixed maximum capacity.
2. Several producers can submit tasks.
3. Several consumers can remove tasks.
4. Producers wait while the queue is full.
5. Consumers wait while the queue is empty.
6. No task is removed more than once.
7. Queue indexes and count remain valid.
8. Shutdown wakes every blocked thread.
9. Consumers process remaining accepted tasks according to the shutdown policy.
10. All synchronization resources are destroyed safely.

Model Synchronization Design

Frequently Asked Questions