12 - Thread Synchronization

Class: CSCE-313

Notes:

Atomic Operations

An atomic operation either "runs to completion" or "not at all".

• It is indivisible: in the sense that during the operation done by $\mathbf{A}$
  • B cannot "observe" or "act" on the state under modification by A.
• Fundamental building block-without atomic operations we have no way for threads to work together and make sense of the resulting computation

Each instruction in the x86 instruction set is atomic. An instruction fully finishes before the current process/thread can be preempted/interrupted.

Notes:

• The "All-or-Nothing" Guarantee: An atomic operation is an action that completes entirely, or does not happen at all. It is strictly indivisible.
• Complete Isolation: The most important feature of an atomic operation is that its intermediate states are completely invisible to the rest of the system. If Thread A is performing an atomic operation, Thread B cannot observe it halfway through or interfere with it.
• The Hardware Reality: While individual, low-level CPU instructions (like those in the x86 architecture) are naturally atomic and cannot be interrupted mid-instruction, high-level C++ code like x = x + 1 translates to multiple assembly instructions (Read, Add, Write). Because a context switch can happen exactly between those underlying instructions, high-level operations are not atomic by default.

Synchronization Variable - Lock to Provide Mutual Exclusion

• First step towards making shared data thread-safe
• The idea is to make a sequence of instructions "atomic" prevent two threads from executing the block concurrently
  • The idea is to make multiple instructions atomic to stop context switching from being useful

General idea:

Notes:

• Faking Atomicity: Because high-level operations (like updating a shared variable) are composed of multiple instructions, we must artificially make them "atomic" to make our code thread-safe. We do this by placing a lock right before the operation and unlocking it immediately after.
• Stopping Destructive Context Switches: When you wrap code in a lock, you don't actually stop the OS from context switching. Instead, you stop context switching from being useful/destructive. If Thread A holds the lock and is paused mid-update, and the OS switches to Thread B, Thread B will see the lock is held and immediately go to sleep. It cannot enter the critical section, thus preserving isolation.
• Serialization: Locks force threads to execute the protected block sequentially (one at a time), rather than concurrently.

What is a mutex?

• A mutex is a lock that we acquire before using a shared resource and releasing it after use.
• When the lock is "set", no other thread can access the locked region of code [advisory].
• It is used to protect data or other resources from concurrent access.
• A mutex lock (pthreads) can only be released by the thread that locked it.

Notes:

• Definition: Mutex stands for Mutual Exclusion. It is the actual locking mechanism (the object) used to enforce serialization.
• The "Advisory" Trap (Crucial Exam Concept): Mutexes are strictly advisory. This means the OS and the compiler do not inherently know which variables your mutex is protecting, and they will not enforce it automatically. If Thread A politely uses the mutex before writing to x, but Thread B is poorly written and writes to x without checking the mutex, the OS will allow it and your data will corrupt! You, the developer, must ensure the lock is used everywhere the data is touched.
• Ownership: A mutex has strict ownership rules: it can only be unlocked by the exact same thread that locked it.

What is a critical section?

• A critical section is a segment of a program that multiple threads should not access simultaneously.
• The segment needs to be executed exclusively & atomically, such as accessing a resource (file, input or output port, global data, etc.)
• It contains shared variables or resources that need to be synchronized to maintain consistency of data variables.
• In concurrent programming, if one thread tries to change the value of shared data at the same time as another thread tries to read the value (i.e., data race across threads), the result is unpredictable.

Notes:

• The Danger Zone: A critical section is simply the specific segment of your code where a shared resource (like a global variable, a file, or a network port) is being accessed or modified.
• Data Races: If you fail to protect a critical section and multiple threads enter it simultaneously (and at least one is writing), you cause a data race. The final result becomes completely unpredictable because threads overwrite each other's work.
• The Golden Rule: To properly protect a critical section, every thread that wants to execute that code must acquire the exact same lock.

Mutex thread synchronization

Notes:

• Thread 0 executes completely isolated from thread 1
• In general if the only thing you are doing is read(), then you can get away without locking.
• But if you are writing, this is where critical sections happen
  • It is the entire read-write section that needs to be protected
  • Critical section should include the read that derived the thing you will write to

Mutex thread synchronization

Mutex in C++ for Thread Safety

#include <iostream>
#include <thread>
#include <mutex>

using namespace std;

void func(int * p, int x, mutex *m) {
    // increment *p x times
    m->lock();
    for (int i = 0; i < x; i++) {
        * p = 'p + 1;
    }
    m->unlock();
}

int main(int ac, char ** av) {
    int data = 0;
    int times = atol(av[1]);
    mutex m;
    
    thread t1(func, &data, times, &m);
    thread t2(func, &data, times, &m);
    t1.join(); // pauses until first finishes
    t2.join(); // pauses until second finishes
    cout << "data = " << data << endl;
}

• Lock before critical section
• Unlock after critical section

Notes:

• If they don't use the same mutex, then you are not serializing anything
• This is just a big heavy duty block that basically has one thread finishing, then the second thread executing or the other way around.

Now when we do:

./a.out 1000000
data = 2000000

• You will be able to see a deterministic output

Mutex in C++ -- Finer Locking

#include <iostream>
#include <thread>
#include <mutex>
using namespace std;
void func (int * p, int x, mutex* m) {
    // increment *p x times
    for (int i=0; i<x, i++){
	    m->lock();    // Critical section: This is more fine-grained,
	    *p = *p + 1;  // produces the same
	    m->unlock()
    }
}
int main(int ac, char** av) {
    int data = 0;
    int times = atoi (av [1]);
    mutex m;
    
    thread t1 (func, &data, times, &m);
    thread t2 (func, &data, times, &m);
    
    t1.join(); // pauses until first finishes
    t2.join(); // pauses until second finishes
    cout << "data = " < < data < < endl;
}

• The previous approach puts entire thread body under lock.
  • Which effectively makes the threads completely sequential.
  • No threading/interleaving happens at all.
• This is "coarse-grained" locking
• You can make locking "finer" (example on left)
• The result is correct in both cases
• The choice would depend on other factors
• Locking and unlocking usually take time

osboxes@osboxes:~/$ /a.out 10000000
data = 20000000
osboxes@osboxes:~/$ ./a.out 10000000
data = 20000000
osboxes@osboxes:*/$ /a.out 10000000
data=20000000

Notes:

• We can only protect the read-modify-write section
• It produces the same correct result
• So yes, we can put locks inside loops to do fine locking

When we do:

./a.out 1000000
data = 2000000

• Once again we are in happy territory

Timeline of Coarse/Fine Grained Locking

Notes:

• Coarse grained: A thread that acquire a lock right at the beginning of the function, and then releases it at the end
• Fine grained: you have much more locks and unlocks, since these happen between small sections of code that are critical

Producer-Consumer Synchronization

Simple mutual-exclusion is not adequate for many problems. Mutual-exclusion provides isolation, but not execution ordering.

For e.g.,

• Thread "producer" generates a result that thread "consumer" uses
  • Dependence between consumer & producer, in addition to mutual exclusion
• This is the Producer-Consumer problem
• One solution is to use another synchronization primitive called the condition variable

Notes:

• Mutual exclusion is not enough!
• It is good but for shared variables we may need other types of primitives to be able to do more general things
• The Limitation of Mutexes: Up until now, we've used mutual exclusion (mutexes) to provide isolation. However, mutexes are not enough for complex multi-threaded problems because they do not provide execution ordering. A mutex ensures only one thread accesses the data at a time, but it cannot dictate which thread should go next.
• The Dependency Problem: In the classic Producer-Consumer scenario, you have "producer" threads generating data and "consumer" threads processing that data. This introduces a strict dependency: a consumer fundamentally cannot do its job until the producer has finished generating an item.
• The Shared Queue Example: If both producers and consumers share a queue, they are modifying the exact same variables (head, tail, and size). While a mutex is necessary to stop them from corrupting the queue pointers simultaneously, we need a new synchronization primitive (the condition variable) to handle the dependency of waiting for data to arrive.
  • Here is an example if a Queue
    • You have multiple consumers and multiple producers
    • You can already see that there are shared variables between consumer and producer
      • producer needs to touch head/tail and size to add an element
      • consumer as it pulls an item from the list needs to change the size and look at head/tail.
      • What if both of them read tail at the same time and both try actions at the same time?
      • The order in which things happens, you can actually lose elements
  • This sounds like a problem for mutex
    • Only one guy can be in the mutation at any given time

Producer-Consumer: problems

• There’s a race condition in accessing the list if there are multiple producers
  • Push-back at a queue end may not be thread-safe.
  • It may require incrementing size, which may not be thread-safe.
• If there are multiple consumers, more than one thread may pass the test even if there is only one item in the queue
  • Two threads may call list.pop().

Notes:

• If the list size is 0, they do a busy wait

• When both think the queue is now empty, they can both try to read/write to the list, which is where bad things happen

• You might say: I do not need to protect anything because these are thread safe. But actually the problem is not that this is thread safe or not, it is that thread safety has gone out of the window much earlier.

• Both think that there are elements in the queue that they can pull off. The fact that you have multiple threads that both determine that there is at least one element in the queue and add an element in the queue is a violation. Now they basically both invoke list.pop, and depending on how well it is written, that can be our problem.

• The Busy-Wait Trap: If you try to solve the dependency problem without condition variables, you might write code where the consumer loops continuously (while (list.size() == 0)), waiting for an item. This is called a busy wait. It is terrible for performance because the consumer thread wastes precious CPU cycles constantly checking an empty queue instead of going to sleep.

• The "Check-Then-Act" Race Condition: Even if the underlying queue data structure is supposedly "thread-safe," you still have a massive problem. Imagine the queue has exactly 1 item. Two consumer threads might check the queue at the exact same microsecond, and both see size != 0. Because both threads passed the test, they both attempt to call list.pop(). The first thread gets the item, but the second thread attempts to pop from an empty queue, causing a violation and a crash.

Solution:
You might attempt to solve multiple consumer’s race condition by trying to do
the following:

• while (list.size() == 0)

This leads to a deadlock when list is empty, because “consumer” is blocked
with mutex held.

• Consumer holds the lock while the queue is empty,
• Producer must wait for lock to add data to the queue.

It would be nice if the lock could somehow be transferred to another thread while one consumer thread is “stuck”.

Notes:

• We are guaranteeing that only one thing sits at that critical section at any given time
• Mutexes do not give us dependence order, the order in which to execute things
• For this we need a new primitive
• Example:
  • Lets say that a consumer tried to pull an item from the que and found that the size of the queue was empty, now they will just wait for something to appear but since they are holding the mutex, that won't never happen! the producer is not able to run!
    • You are deadlock!
• Mutexes are not enforcing an ordering
• The only way I can actually test whether I can consume or not is by acquire the lock, but now when I determine that I can actually not do my thing, I want to be able to relinquish this lock and try again later.
• One thing that the consumer can do is to throw an error here, and have the higher level program call consumer again.
  • But this i still a busy wait, we are just trying again repeatedly!
• The only way a consumer can progress is if a producer runs, but since you are holding the lock, nothing else can run, so you are essentially deadlock
  • If you have written your mutexes correctly, if you return an exception you will be able to unlock the consumer
  • But this is still a busy/pooling situation
• Takeaway: Mutexes give you mutual exclusion but they do not directly provide serialization and ordering!

What if...

• we determine that we cannot proceed (even though it is holding the lock)
• It would be nice is that at this point it could release the lock and go off to sleep
• So instead of a busy wait, you atomically release the mutex and go to sleep
• The producer can actually define a signal that can tell the consumer to wake up! when waking up the consumer acquires the mutex
• It still have mutual exclusion, and you can proceed!
• It turns out that if the consumer wakes up and turns out there are 0 elements in the list, once again, it releases the mutex and goes to sleep

Rewritten notes:

• The Deadlock Trap: If you try to solve the Producer-Consumer problem using only a mutex and a simple while loop, you will almost certainly cause a deadlock. Imagine a consumer locks the mutex, checks the queue, and sees it is empty. If the consumer just waits right there for an item to appear, the entire system freezes. Why? Because the consumer is still holding the lock, meaning the producer can never acquire it to add an item to the queue.
• The Busy-Wait/Polling Trap: A naive workaround would be to have the consumer lock the mutex, check the queue, and if it's empty, unlock it, throw an error, and immediately try again in a loop. While this avoids a strict deadlock, it creates a busy-wait (or polling) situation. The consumer wastes massive amounts of CPU time continuously grabbing and releasing the lock just to check an empty queue.
• The Core Limitation of Mutexes: This scenario perfectly illustrates that mutexes only provide mutual exclusion (isolation); they do not provide execution ordering or serialization. They cannot tell threads when to execute based on dependencies.
• The Conceptual Solution ("What if..."): To solve this efficiently, we need a mechanism that allows the consumer to do three things:
  1. Realize it cannot proceed (e.g., the queue is empty).
  2. Atomically release the lock and go to sleep (so it doesn't waste CPU cycles, and the producer can finally get the lock).
  3. Receive a "wake-up" signal from the producer once data is added.
  4. Upon waking up, the consumer must automatically reacquire the mutex before continuing. If it wakes up and the queue happens to be empty again (e.g., another consumer beat it to the item), it simply releases the lock and goes back to sleep.

What we need is "condition variables"

A condition variable (CV) is

• a queue of waiting threads, with
• a lock for access to CS (multiple CVs per lock is ok)

wait(cond_t *cv, mutex_t *lock)

• assumes lock is held when wait() is called
• puts caller to sleep & releases the lock atomically
• when awoken, reacquires lock before returning

signal(cond_t *cv)

• wake a single waiting thread (if >= 1 thread is waiting)
• if there is no waiting thread, just return w/o doing anything

Notes:

• Think of a condition variable as of being a queue were threads can wait, and that it is associated with a lock
• When you call wait(), you will release the lock and park yourself in the queue corresponding to this condition variable
• The OS will pick one random process from the queue later, the first thing the chosen thread will do is to acquire the mutex.
• The consumer calls wait on this condition vraiable when there is no items on the lists
  • This says: here is this mutex, here is this queue -> release the mutex and put me on the queue
• Now what the producer does is that it signals on the condition variable
  • This says:
    • if tehre is someone waiting on the queue -> please wake them (one) up
    • if there is none waiting on the queue -> that signal is lost
• What about having multiple waits?
  • You get blocked on the first wait() you call, if it is the case that you wake up from that wait you can continue calling other waits one at a time.
  • You can't call wait() twice in an object!
    • The first wait() you call you are already blocked!
    • There are no nested waits
• This functions as some sort of agreement between the waiter and the signaler
• This mechanism is so general that you can basically encode any condition that you want basically
• Remember:
  • When you call wait() you better hold this mutex
  • Whenever somebody signals this condition variable, you either pick one or eveyone waiting on this queue, but the first thing they will do is to acquire this mutex for this critical section

Rewritten notes:

• The Condition Variable (CV) Concept: A condition variable acts as a waiting room (a queue) where threads can safely park themselves and go to sleep when a specific condition isn't met (e.g., when a consumer sees an empty list). Every CV must be paired with a mutex to protect the shared data.
• The wait() Operation: To call wait(), a thread must already hold the mutex. The wait() function does two things atomically: it releases the mutex and puts the thread to sleep in the queue.
  • Why atomicity matters: If releasing the lock and going to sleep weren't perfectly atomic, a producer might send a wake-up signal in the microsecond between the two actions. That signal would be lost, and the consumer could end up sleeping forever.
  • Waking up: When the OS finally wakes the sleeping thread, the very first thing the thread does is automatically reacquire the mutex before wait() even returns.
• The signal() Operation: A producer uses this to wake up exactly one random thread that is sleeping in the CV's queue. If nobody is waiting in the queue, the signal simply disappears (is lost), which is the intended behavior.
• No Nested Waits: You cannot call wait() twice on the same object because the very first wait() completely blocks your thread from executing any further lines of code until it is awakened.

Example:

void Consumer () {
    mutex.lock();
    while (list.size() == 0) {
    mutex.unlock();
    // sleep until list = empty;
    mutex.lock();
    }
    int data = list.front();
    list.pop();
    mutex.unlock();
}

void Producer () {
    int data = 0;
    while (true) {
        data = produce_data();
        mutex.lock();
        list.push_back(data);
        mutex.unlock();
        nofify_consumer();
    }
}

Notes:

• Once the lock is acquired, it tests again
• Between releasing the lock and sleep there is a lot of space
• Note if the signal is lost and the consumer goes to sleep, it may potentially go to sleep forever
• It is dangerous because when you release the lock, you need to make this things atomic
  • This is so that if there is a signal, then that signal is not lost

"Broadcasting" on a condition variable

• Two burgers already available in the warmer.
• 5 consumers show up and place their orders.
• 2 consumers get their burgers—the remaining 3 start playing.
• When each burger is ready:
  • The producer notifies all waiting consumers.
  • All consumers queue up to the counter—but the first one gets the burger.
  • The remaining consumers return to their tables and continue playing.

Notes:

• Waking everybody = broadcasting on the condition variable
• Since you have two burgers in the burner, two consumers are automatically satisfied, but the remaining 3 are parked on the condition variable queue
• Every time that the cook produces 1 or more burgers, he sends a broadcast signal to the condition variable queue
  • They all now compete to get the mutex, only one of them succeeds, and that client gets the burger and the rest will go back to sleep: they will acquire the mutex, they will find that the condition is false (there are no burgers) and they will release and go to sleep.
• The advantage of the broadcaster is that if you happen to produce 2 burgers you just need to wakeup everybody at the same time and you will know that 2 of them will get served automatically
• Be sure that your Exam will have condition variables. This is a fundamental thing and are very useful!

Rewritten notes:

• Broadcasting vs. Signaling: While a signal() only wakes a single thread, a broadcast sends a wake-up call to every single thread currently parked in the condition variable's queue.
• The Burger Shop Analogy: Imagine 3 customers (consumers) are asleep waiting for burgers. The cook (producer) finishes 2 burgers and sends a broadcast signal.
  1. All 3 consumers wake up simultaneously, but they must all immediately compete to grab the single mutex.
  2. Consumer A wins the mutex, takes burger #1, releases the mutex, and leaves.
  3. Consumer B grabs the newly released mutex, takes burger #2, releases the mutex, and leaves.
  4. Consumer C finally gets the mutex. However, they check the warmer and see 0 burgers left. Consumer C must release the mutex and go back to sleep.
• The Loop is Mandatory: This analogy highlights why consumers must always re-test the condition (using a while loop, not an if statement) after waking up. Just because you were woken up does not guarantee the condition is still true by the time you manage to acquire the lock!
• The Advantage: Broadcasting is perfect for when a producer generates multiple items at once (like 2 burgers) and wants to efficiently let the consumers sort out who gets them without needing to send multiple individual signals.

A detour through the C++ Thread API

#include <iostream>
#include <string>
#include <thread>
void hello_worldstring s {
    cout << s << std::endl;
}
class HelloWorld {
public:
    void hello_worldstring s {
        cout << s << " from " <<
        "HelloWorld.hello_world." << endl;
    }
    void operator string s) const { (2
        cout << s << "from " <<
        " HelloWorld.operator()." << endl;
    }
};

int main() {
    std::string s = "Hello World";
    thread t1(hello_world, s); (1)
    HelloWorld hw;
    thread t2(hw, s);
    thread t3hello_world, &hw, s;
    std::thread t4([s] {
        cout << s << "from a lambda." << endl;
    });
    t1.join();
    t2.join();
    t3.join();
    t4.join();
}

Notes:

• Immediate Execution: In C++, the moment you instantiate a std::thread object, it immediately becomes "runnable". The OS can start executing it concurrently right away; there is no separate start() command required.
• Flexibility of the API: The C++ threading library is highly flexible and allows you to spawn threads in four primary ways:
  1. Standard Functions: Passing a regular global function and its arguments directly to the thread (t1).
  2. Functors (Function Objects): Passing an instance of a class that has overloaded the operator() method. The new thread will automatically invoke that operator (t2).
  3. Class Member Functions: Passing a pointer to a specific member function inside a class. Because member functions need a specific object to run on, you must also pass a pointer to the object instance (which acts as the "self" or this pointer), followed by the arguments (t3).
  4. Lambda Expressions (Anonymous Functions): Often the most important and useful approach in modern C++. You can define the function inline without giving it a name. By using the capture list [s], the lambda captures the variable s from the surrounding local scope by value (making a distinct copy of it). This ensures the thread has its own safe copy of the data to work with, avoiding scope issues (t4).

Producer-Consumer: Correctly

Step 1: Declare a condition variable and a mutex

Step 2: The producer produces data in a way such that the consumer can notice e.g., pushing into the vector that consumer checks

Step 3: Calls notify_one/all() on the condition to wake up the consumers so that they can check again

Notes:

• The Danger of Raw Locks: In C++, it is highly dangerous to manually lock a mutex using m.lock(). Because C++ utilizes exceptions, if an error is thrown while the lock is held, the execution might jump out of the function entirely. The m.unlock() would never be reached, leaving the lock permanently held and causing a massive deadlock.
• The Safe Approach (unique_lock): To prevent this, C++ provides a scope-based wrapper called std::unique_lock. When instantiated, it acquires the mutex. More importantly, it guarantees that no matter how you exit the current scope (normally or via an exception), the lock will be safely and automatically released.
• The Predicate Function (The Magic Lambda): In previous examples, we manually wrote a while loop to check if the queue was empty. The C++ wait() function handles this elegantly by accepting the unique_lock and a predicate function (typically an inline lambda expression).
• How the wrapped wait() works: This effectively encapsulates the entire while loop logic. When a consumer calls wait(), the underlying system checks the lambda. If the lambda returns false (e.g., the list is empty), the consumer atomically releases the lock and goes to sleep. When a producer wakes the consumer up using notify_one() or notify_all(), the consumer automatically reacquires the lock and re-runs the lambda. It will only return from the wait() call if the lambda is now true; if it is still false, it releases the lock and goes right back to sleep.

Produce-Consumer

Step 3: The consumer(s) do the following:

• Calls wait() on the condition
• wait() needs a “wrapped” lock (as unique_lock) and a predicate function
  • The “wrapper” also locks the lock
    • Consume data
    • Unlock the lock

An example producer-consumer scenario

Producer-consumer with bounded size?

Notes:

• The Bounded Queue Problem: In the real world, queues often have a maximum capacity (e.g., they can only hold 100 items) so they don't consume infinite memory. To manage a bounded queue, a single condition variable is no longer sufficient.
• Two Condition Variables (can_write & can_read)**: You must define application-layer conditions using two separate condition variables.
  • The Producer's Check: Before the producer can push new data, it must use the can_write condition variable to wait until the current size of the queue is strictly less than the maximum limit. Once it successfully adds an item, it must notify the can_read variable.
  • The Consumer's Check: The consumer uses the can_read condition variable to wait until there is at least one item in the queue. Once it successfully pops an item, it must notify the can_write variable to wake up any producers that might be sleeping because the queue was previously full.
• Extreme Flexibility: Because condition variables in C++ rely on generic predicate functions, you can encode literally any application-state requirement into them, making them a very general and powerful synchronization tool.

Producer-Consumer in C

#define QUEUE_SZ 10
int queue[QUEUE_SZ];
int queue_hd = 0, queue_tl = 0, queue_nitems = 0;

pthread_mutex_t m;
pthread_cond_t can_write, can_read;

void*producer(void *pv) {
	static int counter = 1;
	
	while (1) {
		pthread_mutex_lock(&m);
		while(queue_nitems == QUEUE_SZ) {
			...
		}
		...
	}
}

Notes:

• The C Translation: While C++ provides high-level wrappers like std::thread and unique_lock, in standard C, we rely on the POSIX threads (pthreads) library. The core logic remains identical, but the syntax changes: we manually declare and use pthread_mutex_t for locks and pthread_cond_t for condition variables.
• The Shared State: Just like in C++, you still need shared variables (like queue_nitems) to track the state of the bounded buffer.

Cond Var I

int done = 0;

void *child (void *arg) {
	printf ("child\n");
	done = 1;
	return NULL;
}

int main (int argc, char *argv[]) {
	pthread_t p;
	printf ("parent: begin\n");
	pthread_create (&p, 0, child, 0);
	while (done == 0);
	printf ("parent: end\n");
	return 0;
}

Notes:

• pthread_create: This is the C equivalent of spawning a thread. It returns a thread ID of type pthread_t.
• The void* Constraint: Unlike C++ where you can pass any number of arguments cleanly or use lambdas, the pthreads C API strictly requires the thread's starting function to accept exactly one argument of type void* (a generic pointer) and return a void*.
• Passing Multiple Arguments: Because you can only pass a single pointer, if your thread needs multiple arguments, you must package them all into a custom struct, pass a pointer to that struct into pthread_create, and then carefully cast that void* back into your struct pointer inside the thread function.

Cond Var II

void *child (void *arg) {
	printf ("child\n");
	done = 1;
	pthread_cond_signal(&cv);
	return NULL;
}

int main (int argc, char *argv[]) {
	pthread_t p;
	printf ("parent: begin\n");
	pthread_create(&p, 0, child, 0);
	while(done == 0) {
		pthread_cond_wait(&cv, &m);
	}
	printf("parent: end\n");
	return 0;
}

Notes:

• If you try to synchronize threads using a state variable (done) and a signal, but fail to use a mutex, you create a fatal race condition. \
• Imagine the parent checks while (done == 0). The condition is true, but right before the parent calls wait(), the OS context-switches to the child. The child sets done = 1 and fires the signal. Because the parent isn't officially asleep in the condition variable queue yet, the signal is permanently lost. When the OS switches back, the parent calls wait() and sleeps forever, resulting in a deadlock.

Cond Var III

void *child (void *arg) {
	printf ("child\n");
	pthread_mutex_lock(&m);
	pthread_cond_signal(&c);
	pthread_mutex_unlock(&m);
	return NULL;
}

int main (int argc, char *argv[]) {
	pthread_t p;
	printf ("parent: begin\n");
	pthread_create (&p, 0, child, 0);
	pthread_mutex_lock(&m);
	pthread_cond_wait(&c, &m);
	pthread_mutex_unlock(&m);
	printf ("parent: end\n");
	return 0;
}

Notes:

• Now we acquire mutexes before going to sleep!
• The "No State" Disaster: You might think the solution is just to add mutexes and remove the state variable (done), relying entirely on the signal to wake the parent up. This also fails! Because thread execution order is non-deterministic, the child might run to completion first. It would acquire the lock, signal the empty queue, and exit. Later, the parent runs, acquires the lock, and goes to sleep waiting for a signal that has already happened

Cond Var IV (works)

void *child (void *arg) {
    printf ("child\n");
    othread_mutex_lock(&m);
    done = 1;
    pthread_cond_signal(&c);
    pthread_mutex_unlock(&m);
    return NULL;
}
int main (int argc, char *argv[]) {
    pthread_t p;
    printf ("parent : begin\n");
    pthread_create (&p, 0, child, 0);
    othread_mutex_lock(&m);
    while (done == 0)
        pthread_cond_wait(&c, &m);
    pthread_mutex_unlock(&m);
    printf ("parent: end\n");
    return 0;
}

Notes:

• The Holy Trinity of Synchronization: To safely wait for an event, you absolutely must combine three things: a mutex, a condition variable, and a state variable (done).
• Why this works:
  1. The child locks the mutex, updates the state (done = 1), signals, and unlocks.
  2. The parent locks the mutex before testing the state in the while loop.
• The Guarantee: Because both threads use the mutex, the parent's action of "checking the state and going to sleep" is strictly serialized against the child's action of "changing the state and signaling". The context switch race condition from Cond Var II is impossible because the child cannot change the state or signal while the parent is holding the lock to evaluate the while loop.

What if the two operations are not atomic?

release(mutex);
add yourself to the Q;

Lost update problem