Answer by Justin:

The critical section is a part of the code where at most on thread may be executing at any given time. Mutual exclusion is when one thread is using a shared resource, all other threads must be excluded from using that same resource.

Elaboration (by LLM):

Mutex locks (mutual exclusion locks) are synchronization primitives that work by controlling access to shared resources. When a thread acquires a mutex lock using lock() or pthread_mutex_lock(), it gains exclusive access to the protected resource. Any other thread attempting to acquire the same lock will block (wait) until the first thread releases it via unlock() or pthread_mutex_unlock(). This ensures that only one thread executes the critical section at a time, preventing race conditions and data corruption from concurrent access.

Answer by Justin:

An atomic instruction is one that cannot get interrupted. In intel architecture, the name of the atomic instruction used to implement a mutex lock is Compare & Change.

Elaboration (by LLM):

Atomic instructions are CPU-level operations that execute without interruption by the operating system or other processors. The Intel Compare and Exchange (CMPXCHG) instruction is fundamental to lock implementation: it compares a value in memory with an expected value, and only if they match, it atomically stores a new value. This atomicity is critical because it prevents race conditions during lock acquisition—the test-and-set operation must happen as an indivisible unit. Without atomicity, two threads could both see the lock as available and both acquire it, breaking mutual exclusion.

Answer by Justin:

Tests the value of a memory location and sets it to a new value in atomically. First loads 0 unlocked, then attempts to lock by setting to 1, but only if the tests passes and its 0, otherwise the lock was already set. It is used to implement locks and achieve mutual exclusion.

Elaboration (by LLM):

The Test-and-Set (TAS) instruction is a classic low-level synchronization primitive. It works in two steps atomically: (1) read the current value of a memory location (test), and (2) write a new value to that location (set). For locks, the convention is 0 = unlocked and 1 = locked. A thread calls TAS to set the lock to 1; if it was previously 0, the lock is successfully acquired. If it was already 1, the lock is held by another thread. The algorithm typically uses a spinlock approach where threads repeatedly call TAS until they succeed. Though simple, TAS is the foundation for higher-level lock mechanisms and atomic operations in modern processors.

Answer by Justin:

Constantly wasting CPU cycles so that a thread can check if another thread is done with a lock. With multiprocessor systems, you can make this checking happen on one core alone while have execution continue on another core.

Elaboration (by LLM):

Spinlocks are a busy-waiting synchronization mechanism where a thread repeatedly checks a lock in a tight loop until it becomes available. On single-processor systems, this is inefficient because the spinning thread monopolizes the CPU while the thread holding the lock cannot run—creating a deadlock-like situation. The CPU cycles are wasted on repeated checks that will never succeed until context switching occurs. On multiprocessor systems, spinlocks are viable because the spinning thread uses one processor core while the lock-holding thread can execute on another core, eventually releasing the lock. For short wait times on multicore systems, spinlocks can be faster than the overhead of context switching and condition variable signaling.

Answer by Justin:

A race condition is when multiple threads try to access the same resource at the same time. This causes the output to be nondeterministic and uncertain, as the results depends on timing of threads.

Elaboration (by LLM):

Race conditions occur when the outcome of a program depends on the relative timing of threads or processes accessing shared resources. For example, consider two threads incrementing a shared counter: Thread A reads value 5, Thread B reads value 5 (before A writes), A increments to 6 and writes, B increments to 6 and writes—the counter is now 6 instead of 7. The interleaving of operations is unpredictable and varies based on OS scheduling decisions. Race conditions lead to data corruption, inconsistent program states, and bugs that are difficult to reproduce and debug. This is why synchronization primitives (locks, semaphores) are essential: they enforce a strict order of operations on shared data to prevent such races.

Answer by Justin:

1. Mutual Exclusion
2. Progress (no dead locks)
3. No starvation (Bounded Waiting)
4. Performance (small overhead)

Elaboration (by LLM):

Mutual Exclusion: Only one thread can be in the critical section at any time, preventing concurrent access to shared resources. Progress: If no thread is in the critical section and some thread wants to enter, one of those threads must eventually enter—the system should not deadlock. No Starvation (Bounded Waiting): Once a thread requests entry to the CS, there must be a bound on the number of times other threads can enter before it, ensuring every waiting thread eventually gets access. This prevents indefinite postponement. Performance: The synchronization overhead should be minimal—the cost of acquiring and releasing locks should not dominate the execution time, and the complexity of the lock implementation should be reasonable. These four requirements collectively define a correct and practical mutual exclusion algorithm.

Answer by Justin:

One reason is this will affect important system activities. Another reason is that in multi-core processors, threads running on another core would still be able to run, potentially breaking mutual exclusion.

Elaboration (by LLM):

Disabling interrupts is a crude and dangerous synchronization mechanism. First problem: When interrupts are disabled, critical system activities like I/O handling, timer interrupts, and keyboard input cannot be processed, potentially causing system hangs or data loss. A long-running critical section with interrupts disabled can crash the entire system. Second problem: On multicore/multiprocessor systems, disabling interrupts on one processor does nothing to prevent threads running on other processors from executing—the mutual exclusion is completely broken. Thread A on CPU 0 disables interrupts and enters the CS, while Thread B on CPU 1 simultaneously enters the same CS unaffected. Modern systems universally avoid interrupt disabling for user-level synchronization; it’s only used sparingly in kernel code where absolutely necessary.

Answer by Justin:

If a thread fails to unlock a thread it creates a deadlock so all other processes are stuck in a waiting cycle and are starved since that process will never release.

Elaboration (by LLM):

A deadlock in the context of locks occurs when one or more threads become permanently blocked. The most common scenario is when a thread acquires a lock but fails to release it (e.g., due to an exception, crash, or logic error). Other threads waiting for that lock will block indefinitely, unable to progress. More generally, deadlock can occur in cycles: Thread A holds lock X and waits for lock Y, while Thread B holds lock Y and waits for lock X. Neither can proceed, and both wait forever. Deadlock requires four conditions: mutual exclusion, hold-and-wait, no preemption, and circular wait. Preventing deadlock requires breaking at least one condition, typically through careful lock ordering (acquire locks in a consistent order globally) or using timeouts to detect and recover from potential deadlocks.

Answer by Justin:

A condition variable is a tool that allows threads to sleep until a certain condition is true. This is used in multi threaded applications to synchronize threads together, and this is important because sometimes a thread cannot continue until something else occurs.

Elaboration (by LLM):

Condition variables enable efficient event-based synchronization in concurrent programs. While locks ensure mutual exclusion to shared data, condition variables allow threads to wait for specific conditions and be awakened when those conditions change. A typical pattern: a thread locks a resource, checks if a condition is true, and if not, calls wait() on a condition variable—this atomically releases the lock and puts the thread to sleep. When another thread modifies the condition and calls signal() or broadcast() on the condition variable, sleeping threads are awakened. Condition variables prevent busy-waiting (spinning in loops checking conditions) and are essential for producer-consumer problems, bounded buffers, and any scenario where threads must synchronize based on data state changes. Without condition variables, threads would waste CPU cycling in loops checking for changes.

Answer by Justin:

With mutex’s the thread has ownership over the lock, and with binary semaphores the thread does not have ownership over it. Both accomplish mutual exclusion, but mutex locks are safer because since there is no ownership in semaphores, another thread not in the CS can unlock the semaphore.

Elaboration (by LLM):

Mutex (Mutual Exclusion Lock): A mutex is owned by the thread that acquired it. Only that thread can release the mutex. This ownership property provides safety: if a thread dies or crashes while holding the mutex, the ownership is clearly known, and the OS can clean up and prevent deadlock. Mutexes support recursive locking (the same thread can acquire the same mutex multiple times, as long as it releases it the same number of times). Binary Semaphore: A semaphore is a counter with no ownership semantics. Any thread can call wait() or signal() on it, regardless of who called the other operation. This flexibility is sometimes useful but can lead to bugs: a thread not in the critical section could accidentally signal a semaphore, allowing an unintended thread to enter. For synchronization problems requiring strict mutual exclusion and resource protection, mutexes are the safer, more appropriate choice. Semaphores are better suited for signaling between threads and general counting problems.

Answer by Justin:

No

Elaboration (by LLM):

This is a fundamental property of mutexes due to ownership semantics. When Thread A locks a mutex, the mutex records that Thread A is the owner. When Thread A attempts to unlock, the mutex verifies that the caller is indeed the owner before releasing it. If Thread B tries to unlock a mutex owned by Thread A, the mutex library (on most systems) will:

1. Check ownership: “Who owns this mutex? Thread A, not Thread B”
2. Reject the operation: Return an error code (typically EPERM - Operation not permitted)
3. Maintain safety: The mutex remains locked, protecting the critical section

Why This Ownership Model Matters:

Without ownership, the pattern would be possible but dangerous:

// Without ownership (binary semaphore behavior):
Thread A: wait(sem);      // Acquire
Thread A: <use resource>
Thread B: signal(sem);    // Oops! B can unlock A's resource!
 
Result: Thread A loses exclusive access, critical section violated

With mutex ownership:

// With ownership (mutex behavior):
Thread A: pthread_mutex_lock(&m);      // A becomes owner
Thread A: <use resource>
Thread B: pthread_mutex_unlock(&m);    // Error! Ownership check fails
 
Result: Mutex remains locked, critical section protected

The ownership property provides safety guarantees that prevent accidental or malicious interference with synchronization state.

Answer by Justin:

Yes this is possible with mutex locks as long as the same thread that does the locking does the unlocking. This is not possible with binary semaphores because they do not have the same ownership properties.

Elaboration (by LLM):

Recursive Mutex Locking - YES ✅

A recursive (reentrant) mutex allows the same thread to acquire the same lock multiple times:

// Recursive function
void recursive_function(int depth) {
    pthread_mutex_lock(&recursive_mutex);  // Acquire #1
 
    if (depth > 0) {
        recursive_function(depth - 1);     // Recursive call
        // Inside recursive call:
        // pthread_mutex_lock(&recursive_mutex);  // Acquire #2 - succeeds!
    }
 
    // ... critical section work ...
 
    pthread_mutex_unlock(&recursive_mutex);  // Release #1
}
 
// Without recursion, the second lock would deadlock (same thread waits on itself)
// With recursive mutex, lock maintains a counter:
// lock #1: count = 1
// lock #2: count = 2 (same thread, increments counter)
// unlock #1: count = 1
// unlock #2: count = 0 (finally released)

Binary Semaphore - NO ❌

Binary semaphores have no ownership, so they cannot support recursion safely:

// With binary semaphore (no ownership):
void recursive_function(int depth) {
    wait(&sem);   // Decrement: 1 → 0
 
    if (depth > 0) {
        recursive_function(depth - 1);
        // wait(&sem);   // Decrement: 0 → DEADLOCK! (negative value blocks)
        // The semaphore doesn't know the same thread is trying again
    }
 
    signal(&sem);  // Increment: 0 → 1
}

Technical Difference:

Implementation Detail:

Recursive mutexes typically use:

struct recursive_mutex {
    pthread_t owner_tid;     // Which thread owns it
    int lock_count;          // How many times locked
    pthread_mutex_t internal_lock;  // Protect this structure
};

Answer by Justin:

Recursive locking allows a thread that currently holds the lock to acquire it again without being blocked. Without recursive locking the thread would deadlock itself, which is why we have recursive locking! You do this by using a special type of lock called a recursive mutex lock, and the lock accomplishes this by keeping a count of how many times the lock was used and only releasing once the count goes back to 0 (unlock).

Elaboration (by LLM):

Purpose: Avoid Self-Deadlock in Recursive/Reentrant Code

Many programs have naturally recursive structures or call chains where a function holding a lock calls another function that also needs the same lock. Without recursive mutex support, the thread would deadlock itself:

// Example: Tree traversal with lock
void traverse_tree(Node *node) {
    pthread_mutex_lock(&tree_mutex);    // Acquire once
 
    // Process node
    printf("Node: %d\n", node->data);
 
    // Recursively process children
    if (node->left) {
        traverse_tree(node->left);      // Call needs same lock!
        // Without recursive mutex: DEADLOCK (thread waits on itself)
        // With recursive mutex: succeeds, increments counter
    }
 
    if (node->right) {
        traverse_tree(node->right);
    }
 
    pthread_mutex_unlock(&tree_mutex);  // Release once
}

How It Works: Lock Counter

A recursive mutex (also called “reentrant mutex”) maintains an acquisition counter per thread:

Lock State:
┌──────────────────────────┐
│ Recursive Mutex          │
│ owner_thread_id: T1      │
│ acquisition_count: 0     │
└──────────────────────────┘

Thread T1: lock() → count becomes 1
Thread T1: lock() → count becomes 2 (same thread, succeeds!)
Thread T1: lock() → count becomes 3
Thread T1: unlock() → count becomes 2
Thread T1: unlock() → count becomes 1
Thread T1: unlock() → count becomes 0 (now truly released)
Thread T2: lock() → succeeds (count was 0, T1 no longer owns it)

Implementation:

Using POSIX threads, you create a recursive mutex:

pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE);
pthread_mutex_t recursive_lock;
pthread_mutex_init(&recursive_lock, &attr);
 
// Now the mutex supports recursive locking

Real-World Scenarios Where This Matters:

1. Object-Oriented Code with Member Functions:

   class LinkedList {
       pthread_mutex_t lock;
   public:
       void remove(int value) {
           pthread_mutex_lock(&lock);
           if (head->value == value) {
               head = head->next;
           } else {
               removeHelper(head->next, value);  // Needs same lock
           }
           pthread_mutex_unlock(&lock);
       }
    
       void removeHelper(Node *node, int value) {
           // This function also needs lock, which it already has
           // Without recursive mutex: deadlock!
       }
   };

2. Complex State Machines:

   void handle_event(State *s, Event e) {
       lock_state(s);
       switch(s->type) {
           case STATE_A:
               transition_to_b(s);  // This also needs the state lock
               break;
       }
       unlock_state(s);
   }

Trade-offs:

Why Default Mutex Isn’t Recursive:

Performance! The counter check adds overhead. For single-acquisition use cases (the majority), this overhead is unnecessary. Programs that need recursion explicitly create recursive mutexes.

Answer by Lauren:

A lower priority task holds the lock needed to run a higher priority task.

Elaboration (by LLM):

Priority Inversion: Definition

Priority inversion occurs when a high-priority task must wait for a low-priority task to release a lock, effectively causing the high-priority task to execute at the low priority level. This violates the fundamental principle of priority scheduling: higher priority work should always complete before lower priority work.

Scenario:

Priority levels: T1 (high=10) > T2 (medium=5) > T3 (low=1)

Timeline:
T:0     T3 (low) acquires lock X
T:1     T1 (high) arrives, wants lock X → BLOCKS (must wait for T3)
T:2     T2 (medium) arrives → runs because T1 is blocked

At T:2, the CPU is executing T2 (medium priority)
But T1 (high priority) is waiting!
This is BACKWARDS - violates priority model.

Unbounded Priority Inversion: The Dangerous Form

Unbounded inversion occurs when there are intermediate-priority tasks that can delay the high-priority task indefinitely:

Priority: T1 (high=10) > T2 (medium=5) > T3 (low=1)

T:0     T3 acquires lock X
T:1     T1 arrives, wants lock X → BLOCKS
T:2     T2 arrives → starts running
T:3     T2 finishes, CPU idle, T3 resumes (still has lock)
T:4     T3 still computing (hasn't finished critical section yet)
        T2 arrives again → runs because T1 is blocked and T2 > T3
T:5     T2 finishes, T2 arrives AGAIN → runs again
T:6     ...T2 keeps running indefinitely...
T:100   T3 finally releases lock
T:101   T1 finally acquires lock and runs

Result: T1 (high priority) waited 100 time units!
The wait is UNBOUNDED - dependent on how much work T2 does.

Why It’s Called “Unbounded”:

Without intervention, there’s no upper bound on how long T1 must wait. The delay depends on how many times lower-priority tasks can preempt T3:

This sum can grow arbitrarily large.

Real-World Impact:

This issue famously affected the Mars Pathfinder rover (1997):

• High-priority task (meteorological sensor) needed a lock
• Low-priority task (housekeeping) held the lock
• Medium-priority task (communication) kept preempting
• Result: System watchdog timer saw no progress from high-priority task → system reset
• Solution: Implemented priority inheritance protocol in flight software

Visualization:

Without Priority Inversion Problem (ideal):
Time:    0  1  2  3  4  5  6  7  8
CPU:    [T1][T1][T1][T1][T1][Done]

With Priority Inversion (problem):
Time:    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
Lock X: [T3 holding          T3 still holding...              ]
CPU:    [T3 blocked by T1][T2    ][T2    ][T2    ][T3][T1        ]
                  ↑
            T1 waiting (inverted!)

Answer by Lauren:

Assign a priority ceiling level to each resource/lock. When a task works with the resource/lock, its priority level is boosted to the ceiling value so no medium priority tasks can preempt it.

Elaboration (by LLM):

Priority Ceiling Protocol: How It Works

The priority ceiling protocol assigns each lock a ceiling priority equal to the highest priority of all tasks that might acquire it. When any task acquires the lock, it temporarily inherits that ceiling priority, preventing intermediate-priority tasks from preempting it.

Setup:

Task Priorities:
  T1 (high) = priority 10
  T2 (medium) = priority 5
  T3 (low) = priority 1

Lock X usage:
  T1 might acquire X
  T3 might acquire X
  T2 does NOT use X

Ceiling of Lock X = max(priority of T1, priority of T3)
                  = max(10, 1) = 10

Execution with Priority Ceiling:

Timeline:
T:0     T3 acquires lock X → T3's priority boosted to 10 (lock's ceiling)
T:1     T1 arrives, wants lock X → BLOCKS (T3 priority is now 10, not 1!)
T:2     T2 arrives → CANNOT RUN (T3 at priority 10 blocks it)
        T3 continues at priority 10
T:3     T3 releases lock X → T3's priority drops back to 1
        T1 now unblocks, runs at its priority 10
T:7     T1 finishes critical section
T:8     T2 runs

Result: T1 waits only for T3's critical section (bounded!)
        Medium-priority T2 cannot preempt T3

Why Ceiling Priority Prevents Inversion:

The ceiling guarantee: If a high-priority task is blocked on a lock, no lower-priority task can be running on the CPU.

Proof:

• T1 (high) wants lock held by T3 (low)
• T3 is boosted to lock’s ceiling priority
• Ceiling ≥ any task that uses the lock, including T1
• So T3’s boosted priority ≥ T2’s (medium) priority
• Therefore T2 cannot preempt T3

Comparison: With vs Without Ceiling

WITHOUT Ceiling Protocol (unbounded):
T:0   T3 acquires X
T:1   T1 wants X, blocks
T:2   T2 runs (preempts T3) ← INVERSION!
T:3   T2 continues
...
T:50  T2 finally done
T:51  T3 resumes (finally!)
T:56  T3 releases X
T:57  T1 runs
Result: T1 waited 57 time units (unbounded)

WITH Ceiling Protocol (bounded):
T:0   T3 acquires X, boosted to priority 10
T:1   T1 wants X, blocks
T:2   T2 arrives but priority 10 guard blocks it
T:3   T3 continues unmolested
T:6   T3 releases X, priority drops to 1
T:7   T1 runs
Result: T1 waited only 6 time units (bounded by T3's critical section!)

Strict Bound on Delay:

With priority ceiling, the delay is bounded by the length of the critical section:

Compare to unbounded inversion:

Implementation:

struct ceiling_lock {
    pthread_mutex_t mutex;
    int ceiling_priority;  // Highest priority that uses this lock
};
 
void acquire_ceiling_lock(ceiling_lock *lock, thread_t *current_thread) {
    // Save original priority
    int original_priority = current_thread->priority;
 
    // Boost to ceiling before acquiring
    current_thread->priority = lock->ceiling_priority;
 
    // Acquire the lock
    pthread_mutex_lock(&lock->mutex);
 
    // Store original priority for restoration later
    current_thread->saved_priority = original_priority;
}
 
void release_ceiling_lock(ceiling_lock *lock, thread_t *current_thread) {
    // Release lock
    pthread_mutex_unlock(&lock->mutex);
 
    // Restore original priority
    current_thread->priority = current_thread->saved_priority;
}

Advantages and Disadvantages:

When Priority Ceiling Is Used:

Real-time systems with strict deadlines where bounded response time is critical (aviation, medical devices, aerospace).

Answer by Lauren:

Boost the priority temporarily of a task holding a lock to that of any other high priority task trying to take that lock.

Elaboration (by LLM):

Priority Inheritance Protocol: How It Works

Unlike priority ceiling (which boosts immediately), priority inheritance is reactive: a lock holder’s priority is boosted only when a higher-priority task actually tries to acquire the same lock. The lock holder inherits the priority of the highest-priority task waiting for it.

Setup and Execution:

Task Priorities:
  T1 (high) = priority 10
  T2 (medium) = priority 5
  T3 (low) = priority 1

Timeline:
T:0     T3 acquires lock X (priority still 1, no one waiting)
T:1     T1 arrives, wants lock X
        → T1 sees T3 has lock
        → T1 donates its priority 10 to T3
        → T3 is now boosted to priority 10 temporarily
        → T1 blocks waiting for X
T:2     T2 arrives
        → T2 has priority 5
        → T3 has priority 10 (boosted by T1's donation)
        → T2 cannot preempt T3 (priority 5 < priority 10)
T:3     T3 continues (unmolested by T2)
T:6     T3 releases lock X
        → T3's priority drops back to 1
        → T1 unblocks, acquires lock, runs at priority 10
T:10    T1 releases lock, completes
T:11    T2 runs at priority 5

Result: Inversion prevented! T3's priority temporarily increased to match
        the highest-priority waiter (T1), preventing T2 from interfering.

Key Difference from Ceiling Protocol:

Implementation Concept:

// Pseudo-code for priority inheritance
void acquire_lock_with_inheritance(lock_t *lock, task_t *task) {
    // Try to acquire lock
    if (lock is free) {
        lock->owner = task;
        return;  // Success, no boost needed
    }
 
    // Lock held by someone else
    current_owner = lock->owner;
 
    // Donate our priority to lock owner
    if (task->priority > current_owner->priority) {
        current_owner->priority = task->priority;  // Boost owner
    }
 
    // Wait for lock
    add_to_waitqueue(lock->waiters, task);
    task->state = BLOCKED;
    schedule_other_task();
}
 
void release_lock_with_inheritance(lock_t *lock, task_t *task) {
    // Release lock
    lock->owner = NULL;
 
    // Restore original priority
    task->priority = task->original_priority;
 
    // Wake next waiter if any
    if (lock->waiters not empty) {
        next_task = dequeue(lock->waiters);
        next_task->state = RUNNABLE;
    }
}

Real Scenario: Chain of Priority Inheritance

Priority inheritance can cascade through multiple locks:

T1 (high) waits for lock X
  held by T2 (medium)
T2 waits for lock Y
  held by T3 (low)

What happens:
T3 acquires Y (no one waiting, priority 1)
T2 acquires X (no one waiting, priority 5)
T1 wants X → donates to T2 (now priority 10)
T2 wants Y → donates to T3 (now priority 10)
T3 executes at priority 10 (eventually!)
T3 releases Y → priority drops
T2 resumes (at priority 10 from T1)
T2 releases X → priority drops
T1 runs

Result: Priority donations propagate through lock chain.

Advantages and Disadvantages:

When Used:

Modern systems like Linux, Android, and real-time kernels (PREEMPT_RT) use priority inheritance because:

1. No need to know lock users in advance (unlike ceiling)
2. Adaptive to actual contention patterns
3. Works well with multiple locks
4. Less conservative than ceiling (doesn’t over-boost)

Comparison with Priority Ceiling:

Scenario: T1 (pri 10) wants X held by T3 (pri 1), T2 (pri 5) waiting

Priority Ceiling:
- Ceiling of X = 10 (highest user)
- T3 immediately at 10 even before T1 arrives
- T2 blocked by T3's ceiling priority
- Over-cautious but predictable

Priority Inheritance:
- T3 at priority 1 until T1 arrives
- T2 might run while T3 runs (if T1 hasn't arrived yet)
- T3 boosted only when T1 actually needs it
- More efficient but needs careful implementation

Answer by Lauren:

class Addsub {
  private int g = 0;
 
  public synchronized void Add() {
    while (g == 5) {
      wait();
    }
 
    g++;
    notifyAll();
  }
 
  public synchronized void Sub() {
    while (g == 0) {
      wait();
    }
 
    g--;
    notifyAll();
  }
}

Elaboration (by LLM):

This Java monitor solution elegantly demonstrates the producer-consumer pattern with bounded resources. The synchronized keyword provides automatic mutual exclusion, while wait() and notifyAll() provide condition variable semantics.

How It Works:

1. Mutual Exclusion: synchronized ensures only one thread can execute Add() or Sub() at a time, protecting the shared variable g.

2. Add() Logic:

   • Loop while condition false: while (g == 5) uses a loop (not if) because spurious wakeups can occur—a thread might wake without the condition being true
   • Wait if blocked: If g == 5, the thread releases the lock and sleeps on the implicit condition variable
   • Increment: If g < 5, increment it
   • Notify: notifyAll() wakes all waiting threads (both adders and subtractors) so they can re-check their conditions

3. Sub() Logic: Mirror image—wait while g == 0, decrement if possible, notify all.

Why notifyAll() Instead of notify():

• notify() wakes only one random thread
• notifyAll() wakes all waiting threads
• Safe choice because threads re-check their conditions after waking

If we used notify() with only one adder and one subtractor:

• Subtractor wakes and re-checks; g > 0, so proceeds
• Subtractor’s notifyAll() wakes only the Adder
• If g == 5, Adder immediately waits again
• Result: Both threads can deadlock if synchronization is wrong

Key Pattern:

while (condition_not_met) {
    wait();  // Release lock, sleep
             // Reacquire lock when awakened
}
// Proceed (condition is now met)
notifyAll();  // Wake all other threads

This is the standard monitor pattern for bounded resources.

Advantages of Java Monitor:

• ✅ Automatic cleanup (no manual mutex/condition destruction)
• ✅ Exception safety (lock released even if exception thrown)
• ✅ No manual lock/unlock calls (synchronized handles it)
• ✅ Straightforward to understand

Answer by Lauren:

GlobalVariableMonitor() : g(0) {
  pthread_mutex_init(&mutex, NULL);
  pthread_cond_init(&canAdd, NULL);
  pthread_cond_init(&canSubtract, NULL);
}
 
void Add() {
  pthread_mutex_lock(&mutex);
  while (g == 5) {
    pthread_cond_wait(&canAdd, &mutex);
  }
 
  g++;
  pthread_cond_signal(&canSubtract);
  pthread_mutex_unlock(&mutex);
}
 
void Subtract() {
  pthread_mutex_lock(&mutex);
  while (g == 0) {
    pthread_cond_wait(&canSubtract, &mutex);
  }
 
  g--;
  pthread_cond_signal(&canAdd);
  pthread_mutex_unlock(&mutex);
}

Elaboration (by LLM):

This C++ implementation uses explicit POSIX mutexes and condition variables, demonstrating the lower-level primitives that Java’s monitors abstract away. This approach provides more control and efficiency but requires careful resource management.

Key Mechanisms:

1. Condition Variables for Waiting Threads:

The solution uses two condition variables:

• canAdd: Signals when the subtractor allows adding (g < 5)
• canSubtract: Signals when the adder allows subtracting (g > 0)

This separation improves efficiency:

• When Add() makes progress, it only wakes threads waiting to add/subtract, not all threads
• pthread_cond_signal() wakes just one thread (more efficient than notifyAll())

2. The Wait-Check-Proceed Pattern:

// Acquire lock
pthread_mutex_lock(&mutex);
 
// Check condition in loop (handles spurious wakeups)
while (g == 5) {
    // Atomically:
    // 1. Release lock
    // 2. Sleep on condition variable
    // 3. Reacquire lock when awakened
    pthread_cond_wait(&canAdd, &mutex);
}
 
// Condition now guaranteed true
// Critical section with lock held
g++;
 
// Wake waiting threads
pthread_cond_signal(&canSubtract);
 
// Release lock
pthread_mutex_unlock(&mutex);

3. Atomicity of Condition Wait:

This is crucial: pthread_cond_wait() performs an atomic operation:

// Atomically (cannot be interrupted):
pthread_mutex_unlock(&mutex);       // 1. Release lock
// [Other threads can now run]
wait_on_condition_variable();       // 2. Sleep
// [When awakened]
pthread_mutex_lock(&mutex);         // 3. Reacquire lock

Without this atomicity, a race condition would occur:

Thread A (unsafe if not atomic):
  while (g == 5) {
      unlock(&mutex);           // Release lock
      // Thread B acquires lock here!
      // g becomes 4, Thread B calls signal()
      // But we haven't called wait() yet!
      wait(&cv);                // Miss the signal forever!
      lock(&mutex);
  }

4. Signal vs Broadcast:

pthread_cond_signal(&canSubtract);    // Wake ONE thread
// vs
pthread_cond_broadcast(&canAdd);      // Wake ALL threads

• signal(): More efficient (less context switch overhead)
• broadcast(): Safer if multiple threads waiting (all recheck condition)

In this solution, since there’s only one adder and one subtractor typically, signal() works. But broadcast() would be safer in general.

Comparison: Java vs C++ Approaches

Why Two Condition Variables?

Using one condition variable for both would work but be less efficient:

// Less efficient: one CV, both threads wait on it
void Add() {
    while (g == 5) {
        pthread_cond_wait(&cv, &mutex);  // Might wake for subtraction
    }
    g++;
    pthread_cond_broadcast(&cv);  // Wakes subtractors unnecessarily
}
 
void Subtract() {
    while (g == 0) {
        pthread_cond_wait(&cv, &mutex);  // Might wake for addition
    }
    g--;
    pthread_cond_broadcast(&cv);  // Wakes adders unnecessarily
}

Each wake causes all threads to check their conditions—wasted context switches.

Resource Cleanup:

~GlobalVariableMonitor() {
    pthread_mutex_destroy(&mutex);
    pthread_cond_destroy(&canAdd);
    pthread_cond_destroy(&canSubtract);
}

Must destroy in user code (unlike Java where GC handles it).

sem_t consumerQ = 1;        // To block consumers while producers are in critical section
mutex_t bufferMutex;        // to protect shared buffer
mutex_t counterMutex;       // to protect producerCount
int producerCount = 0;      // # of producers within the critical section
sem_t full = 0;             // # of full slots
sem_t empty = N;            // # of empty slots
 
Produce(item):
    down(empty);
    lock(counterMutex);
    producerCount++;
    /* 1st producer to block consumers */
    if (producerCount == 1) down(consumerQ);
    unlock(counterMutex);
    lock(bufferMutex);
    insert(Q, item);        /* Place item in Q in CS */
    unlock(bufferMutex);
    lock(counterMutex);
    producerCount--;
    /* Last producer to wake up consumers */
    if (producerCount == 0) up(consumerQ);
    unlock(counterMutex);
    up(full);
 
Consume():
    down(full);
    down(consumerQ);
    lock(bufferMutex);
    item = remove(Q);       /* Remove an item from Q in CS */
    unlock(bufferMutex);
    up(consumerQ);
    up(empty);
    return item;

Elaboration (by LLM):

This is a sophisticated solution that combines three classic synchronization problems: (1) bounded buffer producer-consumer, (2) producer priority, and (3) reader-writer mutual exclusion. Let’s decompose it:

Problem Decomposition:

The solution layers three mechanisms:

1. Producer-Consumer Semaphores (empty, full): Count available buffer slots
2. Producer Tracking (producerCount, counterMutex): Track how many producers are active
3. Consumer Blocking (consumerQ): Binary gate that blocks consumers when producers exist

How Producer Priority Works:

Timeline with competing producer and consumer:

Scenario: Buffer has 1 item (not empty, not full)

Event 1: Producer arrives (wants to insert)
         - down(empty) succeeds (there are empty slots)
         - lock(counterMutex): producerCount = 0 → 1
         - down(consumerQ) succeeds (nobody blocked it yet)
         - Can proceed to insert

Event 2: Consumer arrives (wants to remove)
         - down(full) succeeds (buffer not empty)
         - down(consumerQ) BLOCKS! (producer incremented, so consumerQ blocked)
         - Consumer waits for all producers to finish

Result: Producer gets priority — consumer blocked until producer finishes

Produce() Breakdown:

Produce(item):
    // 1. Wait for empty slot (standard bounded buffer)
    down(empty);        // Decrement empty count, block if 0
 
    // 2. Enter producer-tracking section
    lock(counterMutex); // Protect producerCount variable
    producerCount++;
 
    // 3. First producer blocks all consumers
    if (producerCount == 1)
        down(consumerQ);  // Block consumers (consumerQ = 0)
 
    unlock(counterMutex);
 
    // 4. Insert item (mutual exclusion with other producers)
    lock(bufferMutex);
    insert(Q, item);
    unlock(bufferMutex);
 
    // 5. Leave producer-tracking section
    lock(counterMutex);
    producerCount--;
 
    // 6. Last producer unblocks consumers
    if (producerCount == 0)
        up(consumerQ);    // Unblock consumers (consumerQ = 1)
 
    unlock(counterMutex);
 
    // 7. Signal that buffer has one more full slot
    up(full);           // Increment full count, wake waiting consumer

Consume() Breakdown:

Consume():
    // 1. Wait for full slot (standard bounded buffer)
    down(full);         // Block if buffer empty
 
    // 2. Producer gate: wait for all producers to finish
    down(consumerQ);    // Blocks if any producer active
                        // Succeeds only when producerCount == 0
 
    // 3. Remove item safely
    lock(bufferMutex);
    item = remove(Q);
    unlock(bufferMutex);
 
    // 4. Release producer gate (allow next consumer or to check again)
    up(consumerQ);
 
    // 5. Signal that buffer has one more empty slot
    up(empty);          // Wake waiting producer
 
    return item;

Key Insight: Producer-Tracking Pattern

The producerCount with first/last producer logic is a classic pattern for enforcing priority:

First Producer:   producerCount 0→1, blocks consumers
Other Producers:  producerCount 1→2, consumers already blocked
Last Producer:    producerCount 1→0, unblocks consumers

Effect: Consumers cannot run as long as ANY producer is active

Semaphore Values During Execution:

Initial: empty=N, full=0, consumerQ=1, producerCount=0

Producer inserts:
  down(empty):        empty N → N-1
  [produces]
  up(full):           full 0 → 1

Consumer removes:
  down(full):         full 1 → 0
  down(consumerQ):    consumerQ 1 → 0 (blocks if producers active)
  [consumes]
  up(consumerQ):      consumerQ 0 → 1 (may unblock next consumer)
  up(empty):          empty N-1 → N

Why This Beats Simple Priority:

Simple approach (less elegant):

// Naive: Try to give producers priority
down(empty);
lock(bufferMutex);  // Big lock held for all producer work
insert(Q, item);
up(full);
unlock(bufferMutex);  // Consumers blocked entire time

Problem: Buffers full producers’ work inside the lock, blocking consumers completely.

Better approach (this solution):

// Smart: Track producers, let them work in parallel
// But block consumers while ANY producer active
down(empty);
lock(counterMutex);      // Small lock for counting
producerCount++;
if (producerCount == 1) down(consumerQ);  // Gate only on first
unlock(counterMutex);
 
lock(bufferMutex);       // Insert (other producers can wait for lock)
insert(Q, item);
unlock(bufferMutex);
 
lock(counterMutex);      // Exit tracking
producerCount--;
if (producerCount == 0) up(consumerQ);
unlock(counterMutex);
up(full);

Effect: Multiple producers can work in parallel (bufferMutex still serializes buffer access), but consumers are blocked until all producers done.

Potential Issue: Consumer Starvation

If producers continuously arrive, producerCount never reaches 0, and consumers starve. Real implementations might add a fairness mechanism or timeout.

sem_t P1_done = 0;
sem_t P2_done = 0;
sem_t P3_done = 0;
sem_t P4_done = 0;
sem_t P5_done = 0;
sem_t P6_done = 0;
sem_t P7_done = 0;
sem_t P8_done = 0;
 
P1:
    <execute>
    signal(P1_done);    // Let go off P3
    signal(P1_done);    // Let go off P4
 
P2:
    <execute>
    signal(P2_done);    // Let go off P3
    signal(P2_done);    // Let go off P4
 
P3:
    wait(P1_done);
    wait(P2_done);
    <execute>
    signal(P3_done);    // Let go off P8
 
P4:
    wait(P1_done);
    wait(P2_done);
    <execute>
    signal(P4_done);    // Let go off P5
    signal(P4_done);    // Let go off P6
    signal(P4_done);    // Let go off P7
 
P5:
    wait(P4_done);
    <execute>
    signal(P5_done);    // Let go off P8
 
P6:
    wait(P4_done);
    <execute>
    signal(P6_done);    // Let go off P9
 
P7:
    wait(P4_done);
    <execute>
    signal(P7_done);    // Let go off P9
 
P8:
    wait(P3_done);
    wait(P5_done);
    <execute>
    signal(P8_done);    // Let go off P9
 
P9:
    wait(P6_done);
    wait(P7_done);
    wait(P8_done);
    <execute>

Elaboration (by LLM):

This is an elegant solution to the process precedence constraint problem using semaphores. It demonstrates how to encode complex dependency graphs using binary semaphores (initialized to 0). Each semaphore signals one constraint completion.

Dependency Graph:

P1 ──┐
     ├─→ P3 ──┐
P2 ──┤        │
     └─→ P4 ──┼─→ P5 ──┐
             │         │
             ├─→ P6 ──→┤
             │         ├─→ P9
             └─→ P7 ──→┤
                       │
             P8 (needs P3, P5) ┘

Constraints:
- P1 and P2 must complete before P3 starts
- P1 and P2 must complete before P4 starts
- P4 must complete before P5, P6, P7 start
- P3 and P5 must complete before P8 starts
- P6, P7, and P8 must complete before P9 starts

The Pattern: One Signal Per Consumer

Key insight: Each consumer that waits must have a corresponding signal from the producer.

For example, P1 produces for two consumers (P3 and P4), so P1 signals twice:

P1:
    <execute>
    signal(P1_done);    // Signal P3
    signal(P1_done);    // Signal P4

Similarly, P4 signals three times (for P5, P6, P7):

P4:
    <execute>
    signal(P4_done);    // Signal P5
    signal(P4_done);    // Signal P6
    signal(P4_done);    // Signal P7

And P9 waits for three predecessors:

P9:
    wait(P6_done);
    wait(P7_done);
    wait(P8_done);
    <execute>

Why Multiple Signals Work:

In this solution, P1_done is used as a counting semaphore (values 0, 1, 2):

Initial:  P1_done = 0

After P1 executes:
  signal(P1_done):  P1_done = 1
  signal(P1_done):  P1_done = 2

P3 waits:
  wait(P1_done):    P1_done = 1  (P3 unblocked)

P4 waits:
  wait(P1_done):    P1_done = 0  (P4 unblocked)

This mimics a counting semaphore using multiple signal operations.

Complete Execution Timeline:

Time  P1      P2      P3      P4      P5      P6      P7      P8      P9
0     START   START
1     RUN     RUN
2     DONE    DONE
3     SIG     SIG
4     SIG     SIG
5             [run]   RUN     RUN
6     WAIT    WAIT    [run]   [run]   RUN    RUN     RUN    WAIT    WAIT
7     ...     ...     DONE    DONE    [run]  [run]   [run]  WAIT    WAIT
8             ...     SIG             DONE   DONE    DONE   RUN     WAIT
9             ...             ...             [run]
10                    ...     ...                    DONE
11                            ...                          RUN
12                                                   SIG
13                                                   SIG
14                                                   SIG
15                                                         DONE
16                                                         SIG
17                                                         SIG
18                                                         SIG
19                                                               RUN
20                                                               DONE

Why Use Different Semaphores?

This solution reuses semaphore names (e.g., P1_done, P2_done, etc.) but they’re actually different semaphore objects. An alternative (less clear) would be:

// Alternative: use indices (less readable)
sem_t done[9];
 
P[i]:
    wait(done[j]);  // Which j?
    signal(done[i]); // Which times?

Named semaphores are clearer about the dependency graph.

Counting Semaphores vs Binary:

Technically, this uses counting semaphores under the hood (since each is signaled multiple times). But the problem statement asks for semaphores, and these are implemented with counting semantics—each signal() increments, and each wait() decrements.

A More Structured Approach (Alternative):

Some might prefer separate semaphore names for clarity:

// Alternative: one semaphore per producer per consumer
sem_t P1_to_P3 = 0;
sem_t P1_to_P4 = 0;
sem_t P2_to_P3 = 0;
sem_t P2_to_P4 = 0;
sem_t P4_to_P5 = 0;
// ... etc
 
P1:
    signal(P1_to_P3);
    signal(P1_to_P4);
 
P3:
    wait(P1_to_P3);
    wait(P2_to_P3);

But the original solution (reusing semaphore names) is more elegant if you understand the multiple signals pattern.

Key Takeaway:

This solution demonstrates:

1. One signal per consumer: Each task that consumes a signal must have it signaled
2. Multiple waits per consumer: A task can wait on multiple predecessors
3. Dependency encoding: Complex DAGs can be expressed with simple wait/signal operations
4. Counting semaphore effect: Multiple signals create a counting semaphore effect

Problem Analysis:

We need T2 to finish first, then T1 can finish, and finally T3 can finish. This is a linear dependency chain where:

• T2 must complete before T1 can proceed to completion
• T1 must complete before T3 can proceed to completion

Solution Using Binary Semaphores:

// Semaphore declarations and initialization
sem_t T2_done = 0;    // Signals when T2 finishes
sem_t T1_done = 0;    // Signals when T1 finishes
 
void T1() {
    // T1 does its work
    printf("T1 starting work\n");
    DoWork();           // Perform some computation
 
    // T1 waits for T2 to finish before completing
    wait(T2_done);      // Block until T2 signals
    printf("T1 terminating\n");
}
 
void T2() {
    // T2 does its work without waiting
    printf("T2 starting work\n");
    DoWork();           // Perform some computation
 
    // T2 finishes first and signals T1
    printf("T2 terminating first\n");
    signal(T2_done);    // Wake up T1
}
 
void T3() {
    // T3 waits for T1 to finish before it can terminate
    wait(T1_done);      // Block until T1 signals
    printf("T3 terminating last\n");
}
 
main() {
    // Create the three threads
    pthread_t tid1, tid2, tid3;
 
    pthread_create(&tid1, NULL, (void*)T1, NULL);
    pthread_create(&tid2, NULL, (void*)T2, NULL);
    pthread_create(&tid3, NULL, (void*)T3, NULL);
 
    // Wait for all threads to complete
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    pthread_join(tid3, NULL);
 
    printf("Main thread terminating\n");
}

Wait, there’s an issue: T1 needs to signal T3 after T2 signals T1. Let me fix:

sem_t T2_done = 0;    // Signals when T2 finishes
sem_t T1_done = 0;    // Signals when T1 finishes
 
void T1() {
    printf("T1 starting work\n");
    DoWork();           // T1 does work
 
    wait(T2_done);      // T1 waits for T2 to finish
    printf("T1 terminating\n");
    signal(T1_done);    // Signal T3 that T1 is done
}
 
void T2() {
    printf("T2 starting work\n");
    DoWork();           // T2 does work
 
    printf("T2 terminating first\n");
    signal(T2_done);    // Signal T1 that T2 is done
}
 
void T3() {
    printf("T3 waiting for T1\n");
    wait(T1_done);      // T3 waits for T1 to finish
    printf("T3 terminating last\n");
}

Semaphore Initial Values:

• sem_t T2_done = 0; (T2 hasn’t finished yet)
• sem_t T1_done = 0; (T1 hasn’t finished yet)

Termination Sequence:

1. T2 completes first: T2 calls signal(T2_done), waking T1
2. T1 completes second: T1 receives the signal, continues, then calls signal(T1_done), waking T3
3. T3 completes last: T3 receives the signal and terminates
4. Main thread uses pthread_join() on all three threads, then terminates

Key Points:

• Binary semaphores enforce strict ordering through blocking
• T1 cannot exit its critical point until T2 signals
• T3 cannot exit its critical point until T1 signals
• Initial values are 0 (not signaled) so threads block until explicitly signaled

Elaboration:

This problem demonstrates how synchronization primitives (semaphores) interact with scheduling algorithms. The key insight is that different scheduling strategies produce dramatically different execution orders and turnaround times when threads have interdependencies.

Problem Analysis:

The three threads have explicit synchronization constraints:

• T1 must wait for sem1 before it can execute its second Compute(5) block
• T2 must wait for sem2 before it can execute its final Compute(8) block
• T3 signals sem1 after its first work, then later signals sem2

This creates a dependency chain: T3 must signal before T1 can proceed to its second phase, and T3 must signal again before T2 can proceed.

Preemptive Priority Scheduling Analysis (Highest priority = T1, then T2, then T3):

Round-Robin (RR) with Quantum = 4:

RR cycles through ready threads equally, ignoring priority:

Key Teaching Points:

1. Blocking vs Preemption: In priority scheduling, even if T2 has higher priority than T3, T2 cannot run while blocked on a semaphore—T3 must signal first.

2. Semaphore Chain: The actual execution order is constrained by semaphore dependencies, not purely by scheduling algorithm.

3. Fairness vs Performance: Round-Robin is fairer but less predictable; Priority scheduling gives better guarantees for critical tasks but risk of starvation.

4. Context Switch Overhead: Each RR quantum boundary causes context switch overhead not modeled in this problem; Gantt charts usually ignore it for simplicity.

5. Utilization: Both schedules achieve good CPU utilization—few idle periods—because T3 can always make progress while others block.

Answer by Justin:

public class AlarmClock{
    int ticks = 0;
 
    public synchronized void Wait(int numOfTicksToWait) throws InterruptedException {
        int wakeupTicks = ticks + numOfTicksToWait;
        while(ticks < wakeupTicks){
            wait();
        }
    }
 
    public synchronized void Tick(){
        ticks += 1;
        notifyAll();
    }
}

Elaboration (by LLM):

This is a classic monitor-based condition synchronization pattern. The solution uses Java’s built-in monitor (the synchronized keyword) to implement a hardware clock abstraction that allows multiple threads to sleep for a specified duration.

How the Solution Works:

1. Core Variables:

• ticks: A counter that represents elapsed time (incremented by hardware clock at regular intervals)
• synchronized keyword: Creates a monitor—only one thread can execute monitor methods at a time

2. Wait Method Logic:

Calculate target wake-up time = current_time + delay
While current_time < wake_up_time:
    Release lock and sleep on this.wait()
    When awakened, check condition again

The while loop (not an if statement) is critical—it guards against spurious wakeups and rechecks the condition after being signaled.

3. Tick Method Logic:

• Increments the global time counter
• Calls notifyAll() to wake ALL sleeping threads so they can check their individual wake-up conditions

4. Why notifyAll() Instead of notify()?

In this case, notifyAll() is correct because each Wait() call has a different wake-up time. When Tick() occurs, we don’t know which thread(s) have reached their target time—safer to wake all and let them check individually.

Execution Example:

Thread A:          Thread B:         Hardware Clock (Tick):
Wait(5)
  → goal = 0 + 5 = 5
  → ticks < 5, so sleep
                    Wait(3)
                      → goal = 0 + 3 = 3
                      → ticks < 3, so sleep
                                      Tick() → ticks = 1, notifyAll()
                                      (A and B wake, check: 1 < 5? 1 < 3? Both false, sleep again)
                                      Tick() → ticks = 2, notifyAll()
                                      Tick() → ticks = 3, notifyAll()
                                      (B wakes: 3 < 3? FALSE! Exits Wait() ✅)
                                      (A wakes: 5 < 3? FALSE, sleeps)
                                      Tick() → ticks = 4, notifyAll()
                                      Tick() → ticks = 5, notifyAll()
                                      (A wakes: 5 < 5? FALSE! Exits Wait() ✅)

Key Design Patterns:

1. Condition Variable Pattern: wait() and notifyAll() form a condition variable—threads wait for a boolean condition to become true

2. Lock Held During Wait: In Java monitors, the lock is automatically released when calling wait() and reacquired before returning—crucial for allowing other threads to call Tick()

3. Spurious Wakeup Protection: The while loop handles spurious wakeups (OS may wake a thread without notification) and predicate changes while the thread was waking up

Advantages of This Solution:

• Simplicity: Leverages Java’s built-in monitor; very readable
• Correctness: Works for any number of threads with different wait times
• Efficiency: Threads sleep rather than spin-polling

Comparison with Busy-Waiting (Anti-pattern):

// BAD - CPU inefficient
public void Wait(int numOfTicksToWait) {
    int wakeupTicks = ticks + numOfTicksToWait;
    while (ticks < wakeupTicks) {
        // Spin-polling: wastes CPU cycles checking repeatedly
    }
}

This “busy-waits” consumes CPU while the thread should be sleeping—the monitor solution is far superior.

Real-World Applications:

• Thread.sleep(millis): Java’s sleep uses this pattern internally
• System timers: OS provides hardware interrupt-based tick handler calling a notifyAll() equivalent
• Game engines: Frame-rate limiting uses similar tick-based synchronization

Problem Analysis:

We need to implement an alarm clock where:

• Wait(n) blocks the caller for n ticks
• Tick() is called by hardware regularly to advance time
• Multiple threads may be waiting

Solution Using Semaphores:

// Declarations and initializations
sem_t mutex = 1;           // Protects shared data
sem_t alarm = 0;           // Condition variable (binary semaphore)
int currentTick = 0;       // Current system time
 
// Track waiting threads
int waitingThreads = 0;    // Count of threads waiting
int wakeUpTick[MAX_THREADS];  // Array to track when each thread should wake
 
Wait(int numOfTicksToWait) {
    int myWakeupTick;
    int threadId = GetCurrentThreadId();
 
    down(mutex);
 
    // Calculate when this thread should wake up
    myWakeupTick = currentTick + numOfTicksToWait;
    wakeUpTick[threadId] = myWakeupTick;
    waitingThreads++;
 
    // Wait until tick count reaches wake-up time
    while (currentTick < myWakeupTick) {
        up(mutex);           // Release mutex while waiting
        wait(alarm);         // Sleep on alarm semaphore
        down(mutex);         // Reacquire mutex
    }
 
    waitingThreads--;
    up(mutex);
}
 
Tick() {
    down(mutex);
 
    currentTick++;
 
    // Wake up all threads whose wake-up time has arrived
    // Note: Since we only have binary semaphore, we signal once per tick
    // and waiting threads will check their wake-up time
    if (waitingThreads > 0) {
        up(alarm);  // Wake up ONE waiting thread
    }
 
    up(mutex);
}

Better Solution Using Condition Variable Pattern:

A more practical approach uses a counting semaphore or multiple binary semaphores:

// Declarations
sem_t lock = 1;              // Mutex
sem_t waitQueue = 0;         // For blocked threads
int ticks = 0;               // Current time
int threadsWaiting = 0;      // Count of waiting threads
 
Wait(int numOfTicksToWait) {
    int targetTick;
 
    down(lock);
    targetTick = ticks + numOfTicksToWait;
 
    while (ticks < targetTick) {
        threadsWaiting++;
        up(lock);            // Release lock
        wait(waitQueue);     // Sleep
        down(lock);          // Reacquire lock
    }
 
    up(lock);
}
 
Tick() {
    int i;
 
    down(lock);
    ticks++;
 
    // Wake all sleeping threads so they can check their condition
    for (i = 0; i < threadsWaiting; i++) {
        up(waitQueue);
    }
 
    threadsWaiting = 0;  // Reset count for next tick
    up(lock);
}

Explanation:

1. Lock Protection: mutex semaphore protects the shared variables currentTick and waitingThreads

2. Wait Logic:

   • Calculate target wake-up time
   • Check if current time < target time
   • If not ready, increment waiting counter, release lock, and sleep on alarm
   • When signaled, reacquire lock and check condition again

3. Tick Logic:

   • Increment tick counter
   • For each waiting thread, signal the alarm semaphore once
   • This wakes threads so they check their wake-up condition

4. Correctness:

   • Lock ensures atomic read-modify-write of currentTick
   • Loop in Wait ensures thread wakes up for correct tick
   • Semaphore provides efficient sleep/wake mechanism

Key Points:

• Semaphores act as both mutex (lock) and condition variable (alarm)
• Binary semaphore value: 0 = not signaled, 1 = signaled
• down() = wait(), up() = signal() in POSIX terminology
• Multiple threads can wait and all wake at appropriate ticks

Answer by Lauren:

pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&morered, NULL);
pthread_cond_init(&moreblue, NULL);
int red = 0;
int blue = 0;
 
void red() {
  pthread_mutex_lock(&mutex);
  while (red == 3) {
    pthread_cond_wait(&morered, &mutex);
  }
 
  red++;
  pthread_mutex_unlock(&mutex);
  red--;
 
  if (red == 0) {
    pthread_cond_signal(&moreblue);
  }
}
 
void blue() {
  pthread_mutex_lock(&mutex);
  while (blue == 3) {
    pthread_cond_wait(&moreblue, &mutex);
  }
 
  blue++;
  pthread_mutex_unlock(&mutex);
  blue--;
 
  if (blue == 0) {
    pthread_cond_signal(&morered);
  }
}

Elaboration (by LLM):

This elegant solution implements alternating batch scheduling using condition variables. The key insight is that each color maintains a counter tracking how many threads of that color are currently in the critical section, and threads signal the other color when their batch completes.

Problem Understanding:

The goal is NOT strict alternation between single Red and Blue threads. Instead:

• Allow up to 3 threads of one color to enter together
• When all 3 (or fewer) exit, the other color gets a turn
• If no threads of the other color are waiting, allow 3 more of the same color

How the Solution Works:

1. Data Structures:

int red = 0;              // Count of Red threads currently in CS
int blue = 0;             // Count of Blue threads currently in CS
pthread_mutex_t mutex;    // Protects red and blue counters
pthread_cond_t morered;   // Condition variable for waiting Red threads
pthread_cond_t moreblue;  // Condition variable for waiting Blue threads

2. Red Thread Execution Flow:

1. Lock mutex (only one thread manages state at a time)
2. While red == 3:
      Wait on morered condition variable
      (releases mutex, sleeps; wakes when signaled)
3. red++  (increment count of Red threads in CS)
4. Unlock mutex (now another thread can check/enter)
5. ENTER CRITICAL SECTION (not under lock for parallelism!)
6. Lock mutex
7. red--  (decrement count as we exit)
8. If red == 0:
      Signal moreblue (wake sleeping Blue threads)
9. Unlock mutex
10. Return

3. Why Count Instead of Just a Binary Flag?

The counter tracks how many threads of that color are actively in the CS:

Scenario A (3 Red threads active):
  red = 3
  4th Red arrives: red == 3? YES → wait

Scenario B (2 Red threads active, 1 exiting):
  red = 2 (the exiting thread already decremented)
  3rd Red arrives: red == 3? NO → red++, enters

Scenario C (All Red threads exited):
  red = 0
  Signal moreblue: "Blue threads can now enter"

Execution Timeline Example:

Time | Red1      | Red2      | Red3      | Blue1     | Blue2 | State
-----|-----------|-----------|-----------|-----------|-------|------
0    | Lock, red | -         | -         | -         | -     | red=0
1    | red++, US | -         | -         | -         | -     | red=1 (US=unlock/sig)
2    | IN CS     | Lock, red | -         | -         | -     | red=2
3    | IN CS     | red++, US | -         | -         | -     | red=3
4    | IN CS     | IN CS     | Lock, red | -         | -     | red=3
5    | IN CS     | IN CS     | wait()    | Lock, wait| -     | red=3 (wait=on cond)
6    | Lock, red | IN CS     | waiting   | waiting   | -     |
7    | red--, US | Lock, red | waiting   | waiting   | -     | red=2
8    | (exit)    | red--, US | waiting   | waiting   | -     | red=1
9    | -         | (exit)    | waiting   | waiting   | -     | red=0
10   | -         | -         | signal    | waiting   | -     | moreblue signaled
11   | -         | -         | Lock, red | waking... | -     |
12   | -         | -         | red--, US | Lock, red | -     | blue=0, red=0
13   | -         | -         | (exit)    | blue++, US| -     | blue=1
14   | -         | -         | -         | IN CS     | -     |
...

Key Design Insights:

1. Why Decrement After Exiting CS?

   red++;                      // Increment WHILE holding lock
   pthread_mutex_unlock(...);  // Release lock
   // ... CRITICAL SECTION (parallelism!) ...
   pthread_mutex_lock(...);    // Reacquire lock
   red--;                      // Decrement WHILE holding lock

   This allows multiple threads of the same color to execute in parallel in the CS while maintaining accurate counting.

2. Why Not Decrement Inside the Lock Before Exiting?

   // WRONG approach:
   red++;
   pthread_mutex_unlock(...);
   // CRITICAL SECTION
   pthread_mutex_lock(...);
   red--;  // OOPS - if red==0 and another color is waiting,
           // new threads of same color might enter!

3. Avoiding Spurious Wakeups:

   while (red == 3) {  // Loop, not if!
       pthread_cond_wait(...);  // Might wake multiple times
   }

   Uses while instead of if to handle spurious wakeups and ensure the condition is still valid.

Comparison with Semaphore-Based Solutions:

Real-World Applications:

• Thread pool work queues: Batches of workers process jobs alternately
• Reader-writer locks: Readers batch-enter; writers get exclusive turns
• Traffic light control: One direction gets a green batch of vehicles; then other direction

Potential Improvements:

The current solution has a thundering herd problem if using multiple Blue readers—signal() only wakes one Blue thread, but other waiting Blues remain sleeping. Using pthread_cond_broadcast() instead of signal() would wake all waiting threads of the other color (though with overhead).

sem_t S1 = 1;           // A binary semaphore to protect count
sem_t S2 = 0;           // A binary semaphore to sleep on in case we are not able to proceed
int count = N;          // Initial value of the counting semaphore
 
P(CountingSemaphore):
    P(S1);
    count--;
    if (count < 0){
        V(S1);          // Release the mutex binary semaphore
        P(S2);          // Sleep on S2
    } else {
        V(S1);          // Release the mutex binary semaphore
    }
 
V(CountingSemaphore):
    P(S1);
    count++;
    if (count <= 0)
        V(S2);          // Wake up one sleeping process
    V(S1);

Elaboration (by LLM):

This is a fundamental OS pattern showing how to synthesize a counting semaphore from binary semaphores—two semaphores of value 0 or 1. The solution uses a clever trick: the count variable stores information that the binary semaphore value cannot encode.

The Challenge:

A binary semaphore can only be 0 or 1—insufficient to track how many resources are available (e.g., “2 buffers free”). A counting semaphore maintains an integer count that goes negative to track waiting threads.

The Solution - Two Binary Semaphores:

The count variable is the key—it can go negative to indicate waiting threads.

P(CountingSemaphore) - Wait/Decrement Operation:

1. P(S1)                      // Acquire mutex
2. count--                    // Decrement count
3. If count < 0:              // Not enough resources
      V(S1)                   // Release mutex first!
      P(S2)                   // Sleep on binary semaphore
      // (We don't re-acquire S1; V() below implicitly happens)
   Else:                       // Enough resources available
      V(S1)                   // Release mutex and return

Example Trace (Counting Semaphore initialized with N=2):

count = 2

Thread A: P(CountingSem)
  P(S1) → acquire (S1=0)
  count-- → count=1
  count < 0? NO
  V(S1) → release (S1=1)
  return (Thread A acquired resource 1 of 2)

Thread B: P(CountingSem)
  P(S1) → acquire (S1=0)
  count-- → count=0
  count < 0? NO
  V(S1) → release (S1=1)
  return (Thread B acquired resource 2 of 2)

Thread C: P(CountingSem)
  P(S1) → acquire (S1=0)
  count-- → count=-1  ← NEGATIVE! Resources exhausted
  count < 0? YES
  V(S1) → release (S1=1)
  P(S2) → SLEEP (blocked, S2 remains 0)
  ↓ (C stays blocked until S2 is signaled)

Thread A: V(CountingSem)
  P(S1) → acquire (S1=0)
  count++ → count=0  ← Still 0 because C is waiting
  count <= 0? YES
  V(S2) → WAKE C (S2=1)
  V(S1) → release (S1=1)
  ↓ (C wakes from P(S2) and returns)

Thread C: ← NOW RUNS
  return from V(S2) wait
  (C now has resource; continues execution)

Critical Insight - Why count <= 0 in V():

if (count <= 0)    // NOT just count == 0
    V(S2);

• If count == 0: No threads waiting; don’t signal
• If count < 0: Some threads are sleeping; wake one
• Why <=? After V() increments count, if new count ≤ 0, there are still waiting threads

Example showing why <= 0:

count = -1 (one thread sleeping)

V(CountingSemaphore):
  P(S1)
  count++ → count=0
  if (count <= 0) ← TRUE (0 ≤ 0)
    V(S2)  ← Signal sleeping thread!

Comparison: Binary vs Counting Semaphores

Design Pattern - Mutex + Condition Variable Pattern:

This solution demonstrates the classic OS pattern:

P():                          V():
  acquire mutex (S1)            acquire mutex (S1)
  decrement resource (count)    increment resource (count)
  if not available:             if waiters:
    release mutex                 wake one waiter
    sleep on condition (S2)      release mutex

This pattern is used in:

• Producer-consumer buffers: count = free spaces
• Thread pools: count = available workers
• Bounded semaphores: count = available permits

Key Observations:

1. Why P(S1) After Waking? The V() caller re-acquires S1 implicitly when waking up from P(S2)—there’s a subtle assumption here about mutex handoff between V(S2) and the acquisition of S1. Some implementations use a more explicit approach.

2. Atomic Operations The entire P() and V() must be atomic—the mutex S1 ensures this by protecting count.

3. Correctness Proof

   • Resources can’t go below 0 (threads block)
   • Threads wake in order (queued on S2)
   • No lost wake-ups (count variable tracks them)

Real-World Usage:

// Example: Semaphore as buffer slots
sem_t emptySlots;
sem_init(&emptySlots, 0, BUFFER_SIZE);  // N empty slots initially
 
Producer:
  // ... create data ...
  P(emptySlots);      // Wait until buffer has space
  // ... add to buffer ...
  V(filledSlots);     // Signal consumer
 
Consumer:
  P(filledSlots);     // Wait for data
  // ... remove from buffer ...
  V(emptySlots);      // Free up buffer space

Monitor Queue{
    int front = 0;      // Initializations
    int rear = 0;
    int Q[10];          // At most 10 items
    // Other initialization below (if necessary)
    int numItems = 0;   // # of items in the queue
    condition not_full;
    condition not_empty;
 
    // Insert an element to the rear of the Queue
    void add(int item){
        while (numItems == N)
            wait(not_full);
        // numItems < N
        numItems++;
        Q[rear] = item;
        rear = (rear + 1) % N;
        signal(not_empty); // Wake up any sleeping consumer
    }
 
    // Remove an element from the front of the Queue
    int remove(){
        while (numItems == 0)
            wait(not_empty); // Q is empty. Wait until an item is enqueued
        // numItems > 0
        numItems--;
        int item = Q[front];
        front = (front+1) % N;
        signal(not_full); // Signal a sleeping producer
        return item;
    }
}

Elaboration (by LLM):

This is the bounded buffer problem—one of the most important classical synchronization patterns in OS. The solution uses a monitor (Java’s synchronized constructs) to elegantly manage producer-consumer coordination with finite queue capacity.

Problem Setup:

• Producers add items to a queue with limited capacity (N=10)
• Consumers remove items from the queue
• Constraints:
  • Producers block if queue is full
  • Consumers block if queue is empty
  • Only one thread can modify queue at a time (mutual exclusion)

The Solution Components:

1. Circular Buffer Implementation:

int front = 0;        // Points to first item in queue
int rear = 0;         // Points to next insertion position
int numItems = 0;     // Count of items currently in queue
int Q[10];            // Fixed-size array (capacity = N)

The indices wrap around using modulo arithmetic: (index + 1) % N

Example with N=4 and 3 items:
Q[0] | Q[1] | Q[2] | Q[3]
-----+-----+-----+-----
  A  |  B  |  C  |
  ↑         ↑
front      rear
numItems = 3

2. Condition Variables:

condition not_full;    // Producers wait on this when queue is full
condition not_empty;   // Consumers wait on this when queue is empty

These condition variables allow threads to sleep efficiently rather than busy-wait.

3. Monitor Semantics:

The Java synchronized keyword provides:

• Mutual exclusion: Only one thread in the monitor methods at a time
• Atomicity: Variable updates are atomic
• Condition variables: wait() releases lock, sleeps; signal() wakes one sleeper

The add() Method - Producer:

1. while (numItems == N)      // Queue full?
     wait(not_full)           // Sleep until consumer removes something

2. // Now guaranteed: numItems < N (and we hold the lock)
   numItems++                 // Increment count
   Q[rear] = item             // Add item
   rear = (rear + 1) % N      // Advance rear pointer (with wrap)

3. signal(not_empty)          // Wake any sleeping consumer
   // Return (lock released when exiting monitor method)

The remove() Method - Consumer:

1. while (numItems == 0)      // Queue empty?
     wait(not_empty)          // Sleep until producer adds something

2. // Now guaranteed: numItems > 0 (and we hold the lock)
   numItems--                 // Decrement count
   int item = Q[front]        // Get item
   front = (front + 1) % N    // Advance front pointer (with wrap)

3. signal(not_full)           // Wake any sleeping producer
   return item

Execution Timeline:

Producer P1:     Producer P2:        Consumer C1:        Queue State
                                                         front=0,rear=0,numItems=0
add(A)
  numItems++ → 1
  Q[0]=A
  rear=1
  signal()
                                      remove()
                                        wait(not_empty)

                                      [NOW UNBLOCKED by signal]
                                      numItems-- → 0
                                      item=A
                                      front=1
                                      signal(not_full)
                                      return A            front=1,rear=1,numItems=0

add(B)
  numItems++ → 1
  Q[1]=B
  rear=2
  signal()
                                      remove()
                                        wait(not_empty)
                                        [UNBLOCKED]
                                        numItems-- → 0
                                        item=B, front=2
                                        signal()
                                        return B            front=2,rear=2,numItems=0

Key Design Insights:

1. Circular Buffer with Modulo:

Why modulo instead of linear indices?

// Linear approach (BAD):
rear++;
front++;
// Eventually rear and front exceed array bounds ❌
 
// Circular approach (GOOD):
rear = (rear + 1) % N;
front = (front + 1) % N;
// Indices wrap: 0,1,2,3,0,1,2,3,... ✅

Circular buffers maximize space usage and avoid reallocating arrays.

2. Why while Instead of if?

// WRONG:
if (numItems == N)
    wait(not_full);
 
// CORRECT:
while (numItems == N)
    wait(not_full);

Spurious wakeups: OS may wake a thread without explicit signal. Lost signals: Multiple producers might wake simultaneously.

The while ensures the condition is still true after waking.

3. Signal vs Broadcast:

signal(not_empty);  // Wake ONE consumer (sufficient here)
// vs
broadcast(not_empty); // Wake ALL consumers (wasteful)

Use signal() to wake exactly one thread (the one that needs to run). Broadcast wakes all, causing unnecessary context switches.

4. Condition Variable Semantics:

when Producer P1 calls wait(not_full):
  → Releases monitor lock automatically
  → Sleeps
  → When Consumer C1 calls signal(not_full):
    → One sleeping producer wakes
    → Must re-acquire monitor lock before resuming
    → Continues from after wait() call

Comparison: Semaphore vs Monitor Approach

Real-World Examples:

1. Thread pools: Job queue with bounded size—prevents memory exhaustion
2. Buffer for I/O: Disk reads fill a buffer; display thread consumes from it
3. Producer-consumer pipelines: Assembly line where each stage has finite buffer

Bounded Buffer Pattern:

// Producer thread
while (true) {
    Item item = produce();
    queue.add(item);  // Blocks if queue full
}
 
// Consumer thread
while (true) {
    Item item = queue.remove();  // Blocks if queue empty
    consume(item);
}

This is far cleaner than manually managing semaphores.

Correctness Guarantees:

1. Mutual exclusion: Only one thread modifies Q at a time ✅
2. Producer blocks if full: wait(not_full) ensures this ✅
3. Consumer blocks if empty: wait(not_empty) ensures this ✅
4. No lost items: numItems correctly tracks items ✅
5. No integer overflow (with wrap-around):

   After 2^31 operations, indices wrap but % N restores correctness
   

Potential Extensions:

• Priority producers: Some producers have higher priority
• Timeout on wait: wait(not_full, timeout_ms)
• Batch add/remove: Add/remove multiple items at once
• Drain operation: Remove all items atomically

This is a classic “bounded semaphore” or “limited resource” problem. We need to limit entry to at most 5 threads in the critical section simultaneously.

(a) Using mutex locks and binary semaphores:

// Declarations and Initializations
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
sem_t semaphore;
int count = 0;           // Number of threads in CS
 
// Initialize semaphore
sem_init(&semaphore, 0, 5);  // Binary semaphore, value = 5
 
// Code to ENTER the CS
pthread_mutex_lock(&mutex);
// At this point, we're protected by mutex, but we need counting semaphore behavior
// Since we only have binary semaphores, we need different approach
 
// Better approach using mutex + counter:
pthread_mutex_lock(&mutex);
while (count >= 5) {
    pthread_mutex_unlock(&mutex);
    wait(semaphore);         // Sleep if CS is full
    pthread_mutex_lock(&mutex);
}
count++;
pthread_mutex_unlock(&mutex);
 
// CRITICAL SECTION
// ... your critical code here ...
 
// Code to EXIT the CS
pthread_mutex_lock(&mutex);
count--;
pthread_mutex_unlock(&mutex);
signal(semaphore);  // Wake up one waiting thread

Actually, this is cleaner with a counting semaphore. Let me provide the correct solutions:

(a) Using Mutex Locks and Condition Variables (Cleaner):

// Declarations and Initializations
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int count = 0;           // Number of threads currently in CS
const int MAX_THREADS_IN_CS = 5;
 
// Code to ENTER the CS
pthread_mutex_lock(&mutex);
while (count >= MAX_THREADS_IN_CS) {
    pthread_cond_wait(&cond, &mutex);  // Wait until space available
}
count++;
pthread_mutex_unlock(&mutex);
 
// CRITICAL SECTION (not under lock for efficiency)
// ... your critical code here ...
 
// Code to EXIT the CS
pthread_mutex_lock(&mutex);
count--;
pthread_cond_signal(&cond);  // Wake one waiting thread
pthread_mutex_unlock(&mutex);

Why this works:

• Mutex protects the counter
• Condition variable allows threads to sleep when CS is full
• When a thread exits, it signals one waiting thread
• Counter ensures at most 5 threads in CS simultaneously

(b) Using ONLY Counting Semaphores:

// Declarations and Initializations
sem_t semaphore;
 
// Initialize semaphore with initial value of 5
sem_init(&semaphore, 0, 5);
 
// Code to ENTER the CS
wait(semaphore);         // Decrement semaphore
                         // If value becomes negative, thread blocks
                         // At most 5 threads can pass this point
 
// CRITICAL SECTION
// ... your critical code here ...
 
// Code to EXIT the CS
signal(semaphore);       // Increment semaphore
                         // Wakes up one waiting thread if any

Why this works:

• Counting semaphore with initial value 5
• Each wait() decrements the semaphore
• When semaphore reaches 0, subsequent wait() calls block
• signal() increments and wakes one blocked thread
• This naturally limits CS to 5 concurrent threads

(c) Using ONLY Locks and Condition Variables:

// Declarations and Initializations
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t notFull = PTHREAD_COND_INITIALIZER;
int threadsInCS = 0;
const int MAX = 5;
 
// Code to ENTER the CS
pthread_mutex_lock(&lock);
while (threadsInCS >= MAX) {
    // CS is full, wait for someone to leave
    pthread_cond_wait(&notFull, &lock);
}
threadsInCS++;
pthread_mutex_unlock(&lock);
 
// CRITICAL SECTION
// ... your critical code here ...
 
// Code to EXIT the CS
pthread_mutex_lock(&lock);
threadsInCS--;
pthread_cond_signal(&notFull);  // Signal one waiting thread
pthread_mutex_unlock(&lock);

Key Differences:

Recommendation:

• Use (b) Counting Semaphore for this specific problem - it’s the most elegant
• Use (a) or (c) when you need additional conditions beyond simple count limit
• All three are equivalent in terms of synchronization guarantee

Behavior Verification:

• Thread 1-5 enter CS immediately (semaphore value 5 → 4 → 3 → 2 → 1 → 0)
• Thread 6 calls wait() on semaphore value 0, blocks
• When any of 1-5 exit, they signal(), waking Thread 6
• Thread 6 enters as one of the 5 (semaphore remains 0, but only 5 can be in)