• Serving Fairly: Lamport’s Bakery Algorithm
  • Background
  • Pseudocode
  • Scenario
• The Bakery Dilemma
  • Background
  • Scenario
• Broken Counter
  • Background
  • Scenario
• Fast but Wrong, Slow but Safe
  • Background
  • Scenario
• Sleepy Barber And Spinning Chef
  • Background
  • Scenario
  • Further Notes
• Signal, Wait, Or Die Trying
  • Background
  • Scenario
• Kernel Or User: Who Should Control?
  • Background
  • Scenario
• Visual Trace Exercise: Interleaving Madness
  • Background
  • Scenario
  • Visual Timeline Example
• Visual Trace Exercise: Missed Wakeups
  • Background
  • Scenario
  • Visual Timeline Example
• Visual Trace Exercise: The Silent Corruption
  • Background
  • Correct Implementation (Reference)
  • The Silent Corruption
  • Visual Timeline Example
• Visual Trace Exercise: Find The Missing Semaphore
  • Background
  • Scenario
  • Visual Timeline Example
• Visual Trace Exercise: Unintended Garbage Collection
  • Background
  • Scenario
  • Visual Timeline Example

50.005 Computer System Engineering
Information Systems Technology and Design
Singapore University of Technology and Design
Natalie Agus (Summer 2025)

Synchronizing Processes and Threads

Serving Fairly: Lamport’s Bakery Algorithm

Background

Most mutual exclusion mechanisms rely on hardware support, e.g., disabling interrupts, atomic instructions like Test-And-Set, or kernel-managed mutexes. However, Lamport’s Bakery Algorithm is a pure software-based solution that requires no atomic hardware and works for n processes or threads.

It was proposed by Leslie Lamport in 1974 and is inspired by the “take-a-number” system used in bakeries:

• Customers take numbered tickets.
• They are served in order based on their number.

The algorithm uses this analogy to enforce fairness and mutual exclusion:

• Each process “takes a number” using a shared array.
• They wait their turn based on number, then process ID.

Lamport designed the algorithm to work under the assumption of a single-core processor with sequential consistency, meaning memory operations appear in program order to all threads. On modern multicore systems, it may fail unless memory fences or barriers are added, due to instruction reordering or cache visibility issues.

It uses shared memory and two arrays:

• choosing[n]: indicates if a thread is picking a number.
• number[n]: tickets representing order; a higher number means later turn.

The algorithm satisfies the three classical conditions of correct critical section solutions:

• Mutual Exclusion
• Bounded Waiting
• Progress

Pseudocode

int choosing[N] = {0};  // initially all false
int number[N] = {0};    // initially all zero

void lock(int i) {
    choosing[i] = 1;
    number[i] = 1 + max(number[0..N-1]); // take a number
    choosing[i] = 0;

    for (int j = 0; j < N; j++) {
        while (choosing[j]);  // wait if j is choosing
        while (number[j] != 0 &&
              (number[j] < number[i] ||
              (number[j] == number[i] && j < i)));
    }
}

void unlock(int i) {
    number[i] = 0;  // release turn
}

Each thread i calls lock(i) before entering the critical section and unlock(i) after.

Scenario

You are reviewing Lamport’s Bakery Algorithm as a potential solution for managing access to a shared queue in a bare-metal, multi-threaded runtime with no kernel or atomic hardware support.

To approve its use, you need to verify that it satisfies all the required properties of a correct critical section protocol.

Answer the following questions:

1. What is the purpose of the choosing[] array?
2. Prove that the Bakery Algorithm ensures Mutual Exclusion.
3. Prove that it provides Bounded Waiting, i.e., starvation is not possible.
4. Prove that it satisfies Progress, if no one is in the critical section, some thread can proceed.
5. What are the hardware or memory assumptions required for the algorithm to work correctly?

Hints:

• The choosing[] array makes the number assignment atomic.
• Use contradiction to show mutual exclusion.
• Lexicographic ordering ensures fairness.
• Think about how a process knows it has the “smallest” ticket.
• Reflect on issues like cache coherence and memory visibility in multicore systems.

The Bakery Dilemma

Background

Now that you’ve learned how Lamport’s Bakery Algorithm works and why it satisfies the conditions for correct mutual exclusion, it’s time to evaluate its practical usefulness.

There are many ways to solve the critical section problem, including hardware-supported instructions (e.g., Test-And-Set), kernel-level mutexes, spinlocks, and other software solutions like Peterson’s Algorithm (for two threads). Each has trade-offs in complexity, scalability, performance, and assumptions.

The Bakery Algorithm is remarkable for being:

• Purely software-based
• Scalable to n threads
• Fair and starvation-free

However, its real-world deployment is rare due to hardware assumptions and inefficiencies on modern multi-core architectures.

Scenario

You are designing synchronization primitives for a small embedded operating system that supports up to 8 concurrent threads. The platform does not support atomic instructions, but it does guarantee sequentially consistent memory (single-core). You implemented Lamport’s Bakery Algorithm successfully, but your teammate suggests replacing it with Peterson’s Algorithm, citing simplicity.

You must defend your design, but also understand when Bakery is or isn’t the better option.

Answer the following questions:

1. Conceptual: Explain how the Bakery Algorithm guarantees mutual exclusion, fairness, and bounded waiting (briefly recap key ideas).
2. Comparison: Compare Bakery Algorithm and Peterson’s Algorithm with respect to:
   • Number of threads supported
   • Fairness
   • Assumptions and hardware requirements
   • Implementation complexity
3. Scalability: What performance issues might arise as the number of threads increases? How does Bakery’s use of arrays affect overhead?
4. Modern Systems: Why is the Bakery Algorithm rarely used in modern multi-core systems? What kinds of failures could occur without memory barriers?
5. Practical Design: Would a simple spinlock using Test-And-Set (assuming hardware allows) be more practical in this case? Justify based on system characteristics.

Hints:

• Think about Bakery’s use of shared arrays and lexicographic ordering.
• Peterson’s is for 2 threads only but uses simpler logic.
• Memory visibility is a major challenge on multi-core systems.
• A Test-And-Set lock is fast but can waste CPU with busy waiting.
• Consider energy, determinism, and fairness in embedded contexts.

Broken Counter

Background

In multithreaded programs, race conditions occur when multiple threads read-modify-write shared variables without proper synchronization. Even a simple increment operation like counter++ is not atomic. It involves reading the current value, incrementing it, and writing it back, potentially allowing interleaved access that corrupts the result.

Languages like C and C++ allow you to create threads using pthread_create, but unless you use locks (e.g., pthread_mutex_t), race conditions may occur.

Scenario

You and a teammate are writing a benchmarking tool that spawns 10 threads to increment a shared counter 100,000 times each. You expect the result to be exactly 1,000,000. However, the output is often much lower and non-deterministic.

Here’s the simplified C code you’re using:

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

#define NUM_THREADS 10
#define NUM_INCREMENTS 100000

int counter = 0;

void* increment(void* arg) {
    for (int i = 0; i < NUM_INCREMENTS; i++) {
        counter++;  // not atomic!
    }
    return NULL;
}

int main() {
    pthread_t threads[NUM_THREADS];

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_create(&threads[i], NULL, increment, NULL);
    }

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    printf("Final counter: %d\n", counter);
    return 0;
}

Answer the following questions:

1. Explain why counter++ causes a race condition. What are the read-modify-write steps behind it?
2. Why does this lead to a final value that is less than expected?
3. Suggest two ways to fix this race condition in C using the pthreads library.
4. If the increments were performed in a signal handler, would a mutex still be safe? Why or why not?
5. Rewrite the increment function using a mutex to make it correct.

Hints:

• Think in terms of instruction interleaving between threads.
• counter++ expands to a load, increment, and store.
• Consider using pthread_mutex_t or __sync_fetch_and_add (if allowed).
• Signal handlers have limitations on which functions are safe to use.
• Mutexes must be initialized before use and destroyed afterward.

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void* increment(void* arg) {
    for (int i = 0; i < NUM_INCREMENTS; i++) {
        pthread_mutex_lock(&lock);
        counter++;
        pthread_mutex_unlock(&lock);
    }
    return NULL;
}

Fast but Wrong, Slow but Safe

Background

Fixing a race condition with locks ensures correctness, but may introduce performance bottlenecks, especially when many threads contend for the same lock. Low-level operations like __sync_fetch_and_add() or C11 atomic types may avoid locks entirely, but they are still not “free.”

The __sync_fetch_and_add() function is a GCC-provided built-in that performs an atomic fetch-and-add operation. It is often used in multithreaded programs to safely increment shared counters without requiring explicit locks. This operation reads the current value of a variable, adds a specified amount to it, and writes the result back, all as a single atomic step. It ensures that no other thread can interleave its access between the read and write, thus preventing race conditions.

Unlike mutexes, __sync_fetch_and_add() avoids the overhead of blocking and kernel-level context switching, making it much faster for simple counter updates under light to moderate contention. However, under heavy contention, it still suffers from memory bus contention and potential cache line bouncing, since all threads are updating the same memory location.

Scenario

You fixed the counter race condition by protecting counter++ with a mutex. But you notice that your benchmark runs dramatically slower, especially with more threads. Your teammate switches to __sync_fetch_and_add, which improves performance. However, you later redesign the benchmark to use per-thread counters, one for each thread, and aggregate them only at the end.

To your surprise, this last version is not only correct, it’s much faster!

Answer the following questions:

1. Why does adding a mutex to counter++ slow the program down as threads increase?
2. How does __sync_fetch_and_add() improve performance compared to mutexes?
3. What is false sharing, and how can it slow down multithreaded code?
4. How does using per-thread counters avoid false sharing and improve performance?
5. In the code below, why might this still suffer from false sharing, and how can you fix it?

int counters[NUM_THREADS];

void* increment(void* arg) {
    int tid = *(int*)arg;
    for (int i = 0; i < NUM_INCREMENTS; i++) {
        counters[tid]++;
    }
    return NULL;
}

Hints:

• Mutex contention causes cache line bouncing and kernel transitions.
• Atomic ops avoid the kernel but still serialize at the hardware level.
• On most CPUs, adjacent integers are packed into a single 64-byte cache line.
• Use padding or cache alignment to separate frequently written variables.
• Think of data locality and thread-private storage.

typedef struct {
    int value;
    char pad[64 - sizeof(int)];
} PaddedCounter;

PaddedCounter counters[NUM_THREADS];

Sleepy Barber And Spinning Chef

Background

There are many synchronization primitives available for managing concurrent access in operating systems: mutexes, condition variables, and spinlocks, to name a few. Each has trade-offs in responsiveness, CPU usage, and complexity.

• Spinlocks are useful for short, fast critical sections. They keep the thread active in a loop while waiting.
• Condition variables put a thread to sleep and allow it to wait for a specific condition to become true, often used when coordinating work between producer and consumer threads.

Scenario

You are building a multithreaded kitchen simulation. In one task, a chef repeatedly checks for new orders and prepares them. In another, a barber sleeps until a customer arrives, then services them.

The chef currently uses a spinlock to protect the queue of orders and continuously polls it. The barber uses a mutex and condition variable to sleep until a customer wakes him.

You are asked to review these two designs and evaluate which synchronization primitive is more appropriate for each case.

Answer the following questions:

1. Why is using a spinlock appropriate or inappropriate for the chef scenario? When would it be acceptable?
2. Why does the barber benefit from using a condition variable instead of a spinlock?
3. What happens if the chef’s critical section is long or gets delayed by other threads? How does this affect spinlock behavior?
4. Describe the difference in CPU usage between a thread using a spinlock and one waiting on a condition variable.
5. Could the chef’s polling be replaced with a condition variable? If so, what trade-off would that involve?

Hints:

• A spinlock avoids sleeping but wastes CPU while waiting.
• Condition variables block the thread, allowing CPU reuse by others.
• Think about how “active waiting” and “passive waiting” behave under load.
• Consider real-time responsiveness vs. system efficiency.
• Long critical sections make spinlocks problematic.

Further Notes

The diagram below compares the behavior of spinlocks (active waiting) and condition variables (passive waiting), showing what a thread do during each case.

Thread State Timeline

| Time → → →

Case A: Spinlock (Chef)
────────────────────────────────────────────────────────────
[ Check Lock ]→[ Check Lock ]→[ Check Lock ]→[ Acquire Lock ]
(Consumes CPU) (Consumes CPU) (Consumes CPU) (Finally enters)

Notes:
- Thread stays active, continuously polls
- CPU is busy even if lock is not available
- Wasteful under contention

Case B: Condition Variable (Barber)
────────────────────────────────────────────────────────────
[   Wait (Sleep)   ]────────────→[  Wake & Acquire Lock  ]
(No CPU used while sleeping)     (CPU used only on wake)

Notes:
- Thread sleeps until notified
- CPU can be used by other threads
- More scalable and efficient under low activity

Condition Variable puts the waiting thread to sleep until lock is available (resource is available), hence preventing redudant usage of the CPU like in the Spinlock case.

Signal, Wait, Or Die Trying

Background

Semaphores are a fundamental synchronization primitive used to control access to shared resources. A counting semaphore uses two atomic operations:

• wait() (or P()): decrements the counter and may block the thread if the value is below zero.
• signal() (or V()): increments the counter and may unblock a waiting thread.

Semaphores are more flexible than mutexes but trickier to use correctly. Misordered or missing operations can lead to deadlock, starvation, or undefined behavior. Interleavings of wait() and signal() across multiple threads can lead to surprising outcomes.

Scenario

You have a counting semaphore sem initialized to 1, and three threads A, B, and C trying to use it. They each execute code similar to this:

wait(sem);
// critical section
signal(sem);

However, during debugging, you observe the following behavior:

• Sometimes all three threads make progress eventually.
• Other times, one thread seems to never proceed.
• Occasionally, two threads enter the critical section at once.

You suspect there is a bug either in your semaphore implementation or how it’s being used.

Answer the following questions:

1. Describe what should happen if all three threads execute the wait() and signal() pairs properly, assuming a correct semaphore.
2. What could cause more than one thread to enter the critical section at once?
3. Could starvation happen even if the semaphore is working correctly? Why or why not?
4. How would initializing sem to 0 affect behavior? Give an example use case for this.
5. How can priority inversion affect semaphore-based scheduling?

Hints:

• Check whether wait() and signal() are atomic.
• Semaphores can have fairness issues if wakeups are not queued.
• A semaphore initialized to 0 means the first wait() always blocks.
• Consider real-time systems where lower-priority threads hold semaphores.

Kernel Or User: Who Should Control?

Background

Synchronization can be implemented in user space (e.g. spinlocks) or kernel space (e.g. mutexes that cause a thread to sleep). Both approaches provide mutual exclusion but have different performance characteristics depending on the context and workload.

• Spinlocks perform well when the wait time is short because they avoid context switches, but they consume CPU cycles while spinning.
• Blocking locks (like pthread_mutex_lock) may incur the overhead of system calls and context switches, but they free up the CPU for other work while waiting.

Operating systems often use spinlocks for short kernel critical sections and blocking locks for user programs.

Scenario

You are designing a shared-memory message-passing system for inter-thread communication in a real-time control application. Message queues must be accessed with mutual exclusion, but responsiveness is critical. You initially use a pthread_mutex_t, but performance profiling reveals delays in message delivery under high contention.

Your teammate suggests replacing the blocking mutex with a spinlock implemented using atomic instructions. You must evaluate the correctness and efficiency of this change.

Answer the following questions:

1. Why might a user-space spinlock reduce latency compared to a blocking mutex?
2. What are the downsides of using spinlocks in user applications, especially under contention?
3. Under what conditions would a blocking mutex be more appropriate than a spinlock?
4. Why do operating systems often implement hybrid locks (e.g. spin-then-sleep)?
5. If the spinlock is implemented with an atomic compare-and-swap loop, what issues should you watch for?

Hints:

• Context switches cost time and involve kernel interaction.
• Spinlocks make sense only if locks are held briefly.
• Think about CPU starvation and scheduler fairness.
• Consider responsiveness vs. CPU efficiency.

Visual Trace Exercise: Interleaving Madness

Background

When multiple threads execute code that manipulates shared state, the exact order in which operations occur determines the program’s behavior. Without proper synchronization, these operations can interleave in many ways, leading to data races and inconsistent results.

Understanding this interleaving is key to debugging and reasoning about concurrent programs.

Scenario

You are given the following C program with two threads accessing a shared variable:

int x = 0;

void* thread1(void* arg) {
    x = x + 1;
    return NULL;
}

void* thread2(void* arg) {
    x = x + 1;
    return NULL;
}

You expect x to be 2 at the end, but sometimes it’s 1.

You are asked to list possible interleavings of the two threads’ operations and explain how they lead to different outcomes.

Answer the following questions:

1. What low-level operations make up x = x + 1? (Assume it expands into three steps.)
2. Construct a timeline showing an interleaving where the final value of x is 1.
3. Show a timeline where the final value is 2.
4. How many possible interleavings are there if both threads’ operations are broken into three steps?
5. What is the only way to make the result consistently 2?

Hints:

• Think in terms of LOAD x, ADD 1, STORE x.
• Interleavings can overlap these steps.
• No synchronization = no guarantees.
• You can use mutexes or atomic operations to protect critical sections.

Visual Timeline Example

Step-by-step Breakdown of: x = x + 1

Thread 1:        LOAD x → ADD 1 → STORE x
Thread 2:        LOAD x → ADD 1 → STORE x

Interleaving that leads to x == 1:

T1: LOAD x  (x = 0)
T2: LOAD x  (x = 0)
T1: ADD 1   (temp1 = 1)
T2: ADD 1   (temp2 = 1)
T1: STORE x (x = 1)
T2: STORE x (x = 1) ← overwrites T1’s result

Final value: x == 1 (lost update)

Interleaving that leads to x == 2:

T1: LOAD x  (x = 0)
T1: ADD 1   (temp1 = 1)
T1: STORE x (x = 1)
T2: LOAD x  (x = 1)
T2: ADD 1   (temp2 = 2)
T2: STORE x (x = 2)

Final value: x == 2

Visual Trace Exercise: Missed Wakeups

Background

Condition variables are used to block a thread until a certain condition is true. They are used in combination with a mutex:

• pthread_cond_wait(&cond, &mutex) releases the mutex and puts the thread to sleep.
• pthread_cond_signal(&cond) wakes one waiting thread.
• pthread_cond_broadcast(&cond) wakes all waiting threads.

However, condition variables are not message queues. If no thread is waiting when signal() is called, the signal is lost. This leads to the classic missed wakeup problem.

Scenario

You implement a producer-consumer system with a shared buffer and one slot. You use a condition variable to notify the consumer when the producer inserts an item. But sometimes the consumer seems to block forever.

Here is the simplified code:

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

int ready = 0;

void* producer(void* arg) {
    pthread_mutex_lock(&mutex);
    ready = 1;
    pthread_cond_signal(&cond); // wake consumer
    pthread_mutex_unlock(&mutex);
    return NULL;
}

void* consumer(void* arg) {
    pthread_mutex_lock(&mutex);
    if (ready == 0) {
        pthread_cond_wait(&cond, &mutex); // wait for signal
    }
    // consume
    pthread_mutex_unlock(&mutex);
    return NULL;
}

Answer the following questions:

1. What happens if the producer signals before the consumer starts waiting?
2. Why must pthread_cond_wait() always be used inside a while loop, not an if?
3. What is a spurious wakeup and how does the loop guard handle it?
4. Construct a timeline where the consumer blocks forever due to a missed signal.
5. Rewrite the consumer code to be safe against missed signals and spurious wakeups.

Hints:

• A condition variable does not remember past signals.
• Signals are not queued, they are lost if no thread is waiting.
• Always recheck the condition after waking up.

Visual Timeline Example

Missed Wakeup Scenario:

T1 (Producer): LOCK → ready = 1 → SIGNAL cond → UNLOCK
T2 (Consumer): LOCK → if (ready == 0) → WAIT cond → blocks forever

Explanation:
- Consumer calls wait *after* signal was sent.
- Condition is already true, but signal is gone.
- Since wait is inside an "if", the condition is never rechecked.
- Consumer sleeps forever.

Corrected Flow (Using while):

T2 (Consumer): LOCK
               while (ready == 0)
                   WAIT cond
               // proceed
               UNLOCK

pthread_mutex_lock(&mutex);
while (ready == 0) {
    pthread_cond_wait(&cond, &mutex);
}
// consume
pthread_mutex_unlock(&mutex);

Visual Trace Exercise: The Silent Corruption

Background

The bounded buffer problem is a classic producer-consumer scenario where multiple threads insert and remove items from a shared buffer of fixed size. To coordinate access safely and efficiently, the solution typically uses:

• A counting semaphore empty, initialized to the buffer size, which tracks how many empty slots are available.
• A counting semaphore full, initialized to 0, which tracks how many items are available to consume.
• A mutex, which ensures mutual exclusion during access to the buffer itself.

While the semaphores regulate when threads can proceed, the mutex protects how they access shared memory.

Correct Implementation (Reference)

#define BUFFER_SIZE 5
int buffer[BUFFER_SIZE];
int in = 0, out = 0;

sem_t empty, full;
pthread_mutex_t mutex;

void* producer(void* arg) {
    while (1) {
        int item = produce_item();

        sem_wait(&empty);
        pthread_mutex_lock(&mutex);

        buffer[in] = item;
        in = (in + 1) % BUFFER_SIZE;

        pthread_mutex_unlock(&mutex);
        sem_post(&full);
    }
}

void* consumer(void* arg) {
    while (1) {
        sem_wait(&full);
        pthread_mutex_lock(&mutex);

        int item = buffer[out];
        out = (out + 1) % BUFFER_SIZE;

        pthread_mutex_unlock(&mutex);
        sem_post(&empty);

        consume_item(item);
    }
}

This implementation is safe because:

• Only one thread at a time accesses the buffer.
• Producers block when the buffer is full.
• Consumers block when the buffer is empty.

The Silent Corruption

Your teammate attempts to simplify the code by removing the mutex, arguing that the semaphores already control access:

sem_t empty, full; // mutex removed

void* producer(void* arg) {
    while (1) {
        int item = produce_item();

        sem_wait(&empty);
        buffer[in] = item;
        in = (in + 1) % BUFFER_SIZE;
        sem_post(&full);
    }
}

void* consumer(void* arg) {
    while (1) {
        sem_wait(&full);
        int item = buffer[out];
        out = (out + 1) % BUFFER_SIZE;
        sem_post(&empty);

        consume_item(item);
    }
}

The program runs and does not crash, but consumers occasionally receive corrupted or duplicated data. The bug is subtle, intermittent, and hard to trace.

Answer the following questions:

1. Why does the code seem to work most of the time, even without a mutex?
2. Explain why empty and full alone are not enough to ensure safe access to the buffer.
3. Show a timeline where two producers write to the buffer concurrently and cause data corruption.
4. What are some ways this bug could manifest in a real system?
5. What is the minimal fix required to make this implementation correct?

Hints:

• Semaphores only count availability, not protect consistency.
• Shared variables like buffer, in, and out need to be accessed atomically.
• The bug may not appear on single-core machines or under light load.

Visual Timeline Example

Initial: empty = 5, full = 0, in = 0

T1 (Producer):
    sem_wait(empty) → proceeds
    writes buffer[0] = A

T2 (Producer):
    sem_wait(empty) → proceeds
    writes buffer[0] = B  ← overlaps with T1

→ Consumer:
    sem_wait(full)
    reads buffer[0] = B or corrupted value
    consumes wrong or partial data

T1: sem_wait(empty)
T1: buffer[in] = A        // in == 0
T2: sem_wait(empty)
T2: buffer[in] = B        // in == 0 (same)
T1: in = 1
T2: in = 1

Visual Trace Exercise: Find The Missing Semaphore

Background

In a bounded buffer with multiple producers and consumers, correct synchronization requires managing both access safety (via a mutex) and resource availability (via semaphores). Omitting either can cause subtle bugs.

This exercise presents code with a mutex but no semaphores. You must identify what goes wrong and fix it.

Scenario

The following code is used to implement a bounded buffer between a producer and consumer. It uses a shared circular buffer of size 10. A mutex ensures only one thread accesses the buffer at a time.

However, no semaphores are used to track available slots or items. Occasionally, the consumer reads invalid data, or the producer writes past the buffer limit.

#define BUFFER_SIZE 10
int buffer[BUFFER_SIZE];
int in = 0, out = 0;

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

void* producer(void* arg) {
    while (1) {
        int item = produce_item();

        pthread_mutex_lock(&mutex);
        buffer[in] = item;
        in = (in + 1) % BUFFER_SIZE;
        pthread_mutex_unlock(&mutex);
    }
}

void* consumer(void* arg) {
    while (1) {
        pthread_mutex_lock(&mutex);
        int item = buffer[out];
        out = (out + 1) % BUFFER_SIZE;
        pthread_mutex_unlock(&mutex);

        consume_item(item);
    }
}

Answer the following questions:

1. What is the role of the mutex in this code, and what problems does it prevent?
2. Why does this code fail even though mutual exclusion is enforced?
3. Describe two different failure scenarios: one from buffer overrun, one from under-read.
4. Which semaphores are missing? What should their initial values be?
5. Rewrite the core logic of both producer and consumer using semaphores correctly.

Hints:

• A mutex only protects access. It doesn’t count how much data is in the buffer.
• Use empty to block producers when the buffer is full.
• Use full to block consumers when the buffer is empty.
• Always acquire semaphores in the correct order.

Visual Timeline Example

Initial: in = 9, out = 9

T1 (Producer):
    LOCK
    buffer[9] = A
    in = 0
    UNLOCK

T2 (Producer):
    LOCK
    buffer[0] = B
    in = 1
    UNLOCK

→ buffer now contains 11 items (overflowed)

T3 (Consumer):
    LOCK
    item = buffer[0] // maybe stale or overwritten
    out = 1
    UNLOCK

void* producer(void* arg) {
    while (1) {
        int item = produce_item();

        sem_wait(&empty);
        pthread_mutex_lock(&mutex);
        buffer[in] = item;
        in = (in + 1) % BUFFER_SIZE;
        pthread_mutex_unlock(&mutex);
        sem_post(&full);
    }
}

void* consumer(void* arg) {
    while (1) {
        sem_wait(&full);
        pthread_mutex_lock(&mutex);
        int item = buffer[out];
        out = (out + 1) % BUFFER_SIZE;
        pthread_mutex_unlock(&mutex);
        sem_post(&empty);

        consume_item(item);
    }
}

Visual Trace Exercise: Unintended Garbage Collection

Background

In producer-consumer synchronization using semaphores, the order of operations matters. If a producer signals the consumer too early, it may allow a consumer to proceed before the shared data is actually written. This causes a classic race condition: the consumer reads a garbage value, a default-initialized variable, or stale memory.

Condition variables are often paired with a loop to guard against this. But with semaphores, the ordering alone must guarantee correctness.

Scenario

Your teammate makes the following optimization: they move sem_post(&full) to just before inserting the item. They believe this improves responsiveness by unblocking consumers early.

sem_wait(&empty);
sem_post(&full); // moved up
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;

It “seems to work”, but in some runs, the consumer logs an invalid item or reads garbage values.

Answer the following questions:

1. Why is it incorrect to post full before inserting the item?
2. Show a timeline where the consumer reads from the buffer before the producer writes to it.
3. Why might this bug be rare in tests but critical in production?
4. How would you fix this bug?
5. In general, when is it safe to signal a semaphore that releases another thread?

Hints:

• Semaphores should reflect the logical state of the resource.
• The signal must mean “the item is fully ready.”
• Use timeline thinking: what happens between signal and actual write?

Visual Timeline Example

Initial state: empty = 3, full = 0

T1 (Producer):
    sem_wait(empty) → OK (empty = 2)
    sem_post(full)  → early signal (full = 1)

T2 (Consumer):
    sem_wait(full)  → OK (full = 0)
    reads buffer[in] before producer writes
    → reads uninitialized or stale value

T1:
    writes buffer[in] = 42

sem_wait(&empty);
buffer[in] = item;
in = (in + 1) % BUFFER_SIZE;
sem_post(&full);