Prof Hall's Website

CS180_L_10 Synchronization

Aug 04, 202619 min read

We’ve talked a bit about the kinds of problems you can encounter when multithreading a program. Does this section of code look familiar?

#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
 
int counter = 0;
  
void* AddTenMil(void* p)
{
    for (int i = 0; i < 1e7; ++i)
    {
        ++counter;
    }
    return NULL;
}
 
int main()
{
    pthread_t tIDs[2];
    int ptcCode = -1;
    ptcCode = pthread_create(&tIDs[0], NULL, AddTenMil, "A");
    ptcCode = pthread_create(&tIDs[1], NULL, AddTenMil, "B");
    pthread_join(tIDs[0], NULL);
    pthread_join(tIDs[1], NULL);
    printf("Counter value:%d\n", counter);
 
    return 0;
}

The reason this code is problematic boils down to the increment instruction not being atomic. We cannot guarantee that a context switch won’t happen during the middle of the increment to the variable. If a context switch DOES happen, we will likely restore a register with stale data, which will then be used to update the variable’s value after the other thread has done a bunch of increments. We’ll almost certainly never reach the 20 million mark we’re aiming for.

There are a few ways around this problem. The first and most straightforward is to just never write code like this! Ensure that the problem you are trying to solve doesn’t involve writing to the same memory location from two different points of execution (threads).

Say for whatever reason we MUST write code this way, and we can’t get around it? Our other solution is to make sure a context switch CAN NOT happen in our critical section. But how do we ensure that? We need something that looks like the following:

LOCK
//Critical Section!
UNLOCK

The lock, before the critical section, will allow only a single thread into the critical section at a time; if another thread attempts to enter when the critical section is locked, it will wait until the critical section becomes unlocked.

OK, this kind of solution makes sense… but how does it work under the hood, and what does the API actually look like in practice? Let’s take a look!

The Qualities of a Lock

Before talking about how a lock works in practice, we should discuss the properties that we should consider when making a lock.

The first is: does the lock provide mutual exclusion? The whole point of using a lock in the first place is to ensure multiple threads can’t enter a critical section at the same time. If the lock doesn’t accomplish this, then it isn’t doing its job.

The second: is the lock fair? When we say fair, we mean it in the sense that each thread gets a fair shot at entering the critical section. Imagine a scenario where four different threads are all vying for the same lock. Additionally, say that the critical section exists in a loop, meaning each thread will need to acquire the lock multiple times. Let’s say Thread 1 acquires the lock, completes the critical section, and relinquishes the lock. Once the lock is relinquished, let’s say Thread 2 acquires the lock and is in the critical section. As Thread 2 is executing code in the critical section, Thread 1 makes its way back to the beginning of the critical section, and is now waiting on the lock. Since Thread 1 is waiting on the lock (same as Threads 3 and 4, which have never entered the critical section!), it could be granted the lock once Thread 2 finishes. This would be unfair, because Threads 3 and 4 haven’t ever entered the critical section, while Thread 1 is about to start its second run through the critical section. Somehow we need to ensure that the way the lock is distributed to waiting threads is fair.

The third: is the lock performant? Because we’re no longer context switching with abandon, we need to use this locking mechanism… which unfortunately means there will be overhead. The overhead will be different depending on the context, such as threads contending for the lock on a single-core CPU vs threads contending for the lock on a multi-core CPU. The lock must perform well enough that the overhead of using it doesn’t outweigh its usefulness in managing our multithreading woes.

Making a Lock

Turning off Interrupts

One solution that could possibly work for our dilemma is to simply disable interrupts whenever we enter the critical section. This means our process won’t context switch in the middle of the critical section, because a CPU timer interrupt won’t happen to hand control back to the Kernel to force a context switch. The upside of this is that we would stop the very thing that is causing us so much trouble… we couldn’t be interrupted in the middle of our increment operation! So, why is this NOT the correct solution?

For one, if the ability to turn off interrupts is given to a user program, that allows user programs to abuse that power to keep the CPU all to themselves. Clearly that’s something we can’t allow to happen.

Second, this approach doesn’t work on multi-core CPUs. Even if interrupts are disabled, two threads could still enter the critical section at the same time on multiple cores. For example, suppose a program has four threads running simultaneously on an eight core CPU. If those four threads are entering the critical section at the same time, it doesn’t matter that one of the threads disabled interrupts; the other three threads are still entering the critical section on their own cores.

Test-And-Set

Alright, since we can’t rely on disabling interrupts, what can we do? We’ll need to turn to the hardware/OS combo once again to help us out.

Let’s use an instruction that is guaranteed by the CPU to be atomic! This instruction is called TestAndSet, and looks something like this:

int TestAndSet(int *old_ptr, int new) 
{
	int old = *old_ptr; // fetch old value at old_ptr
	*old_ptr = new; // store ’new’ into old_ptr
	return old; // return the old value
}

(different CPU architectures call this kind of instruction something different; in x86 it is called atomic exchange, or xchg)

The code above is a C code representation of what’s happening, but in reality this is a single atomic instruction that happens all in one go. To be clear on what’s happening: we are storing the current/old value of an integer in a variable called old (the test), we are then setting the value of the original integer to a new value (the set), and then this function (the instruction) is returning the original/old value of the integer.

To summarize: this atomic instruction sets the value of an int to a new value, while returning the old value so we know what it was prior to the instruction.

OK cool… how does this help us? Let’s grab some supporting code to gain a better understanding:

typedef struct __lock_t 
{
	int flag;
	
} lock_t;
 
void init(lock_t *lock) 
{
	// 0: lock is available, 1: lock is held
	lock->flag = 0;
}
 
void lock(lock_t *lock) 
{
	while (TestAndSet(&lock->flag, 1) == 1)
	; // spin-wait (do nothing)
}
 
void unlock(lock_t *lock) 
{
	lock->flag = 0;
}

Case 1: a thread calls lock when no other thread holds the lock. TestAndSet will set the value of the flag to 1 TestAndSet will return 0 (the old value) The thread will not loop because TestAndSet returned 0

Case 2: a thread calls lock when another thread DOES hold the lock TestAndSet will set the value of the flag to 1 TestAndSet will return 1 (the old value, because another thread holds the lock) This thread will continue calling TestAndSet in a loop until 0 is returned Once 0 is returned (because another thread unlocked) this thread will acquire the lock

Does this now work? And what is a Spin-Lock?

Yes, this type of lock works for us! Using some simple hardware support (in the form of the atomic TestAndSet instruction) we can now make a lock that guarantees mutual exclusion. So from our earlier requirements, we’ve met the first one: we can lock our critical section off to only a single thread at a time. But what about our other requirements?

Unfortunately our locking mechanism described above doesn’t hit our other requirements as well as we’d like. In terms of fairness, we could still have many different threads that are all waiting on the lock, and there’s no way we can guarantee that any particular thread (especially one has been repeatedly passed over) will acquire the lock. This comes down to the CPU scheduling algorithm being pretty mercurial; it has its own criteria for choosing which thread runs next, which doesn’t include our synchronization woes. We don’t currently have a way to signal to the scheduler that a particular thread is being starved.

In terms of performance, we’re also suffering. The issue is that whenever a thread is waiting to acquire the lock, it’s doing so in a loop, basically wasting CPU cycles asking if the lock is available. I’ll let the book take over from here:

OK, so what can be done? How do we avoid spinning when we want to acquire the lock? It’s back to the textbook for the answer…

Condition Variables (leading to Semaphores)

We’ve now seen that locks (created using atomic instructions, with some help to support fairness via the OS) are an indispensable tool for preventing race conditions in concurrent programing. But we may need more than just locks… remember this section of code that you likely used in your threading homework?

pthread_t myThread;
 
pthread_create(&myThread, NULL, ThreadFunctionThing, NULL);
 
pthread_join();

We’re creating a thread, sending it off to do work, and then waiting for it to return. This paradigm makes sense; the worker thread(s) can go off and do some portion of work (like performing matrix multiplication) and the main thread can wait for all the workers to return, then aggregate the results. But to do this, we need a way to wait for our threads to finish. The pthread_join call above is responsible for this… but how does it actually work? It isn’t a mutex… so what is it?

First let’s look at an approach that doesn’t work. We could make this with what we already know, but it’s clunky:

int done = 0;
 
void *child(void *arg) 
{
	printf("child\n");
	//DO A BUNCH OF WORK HERE!
	done = 1;
	return NULL;
}
 
int main(int argc, char *argv[]) 
{
	printf("parent: begin\n");
	pthread_t myThread;
	pthread_create(&myThread, NULL, child, NULL); // child
	while (done == 0)
		; // spin
	printf("parent: end\n");
	return 0;
}

Basically, make a thread, send it off on its way, and while we’re waiting for it to finish, keep checking the done variable. But of course, this has a massive downside; if the main thread is scheduled while the worker thread is off doing its business, the main thread simply spins in a while loop, waiting for the worker to finish. This wastes CPU cycles that could be used for other processes or threads.

So, can we make some kind of condition variable that allows us to put the main thread to sleep while the worker thread is still busy? And how will the worker thread notify the main thread that it is done?

From the textbook

In multi-threaded programs, it is often useful for a thread to wait for some condition to become true before proceeding. The simple approach, of just spinning until the condition becomes true, is grossly inefficient and wastes CPU cycles, and in some cases, can be incorrect. Thus, how should a thread wait for a condition?

First let’s define a few terms:

  • Condition Variable - an explicit queue that threads can put themselves on when some condition is not as desired
  • Signal - when a thread changes the condition, it alerts threads in the queue to allow them to continue

So say we have this “condition variable”, and it looks something like this:

pthread_cond_t myCond;
 
pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
pthread_cond_signal(pthread_cond_t *c);

The condition variable has two operations associated with it. The first is wait, which is used to atomically put the calling thread to sleep. The second is signal, which is used to wake a sleeping thread that is waiting on this condition.

We won’t dive into too many examples behind condition variables, but if you’d like to see some examples, they’re in chapter 30 of the textbook.

Semaphores

A semaphore is a synchronization primitive that can be used for both locks AND condition variables. It was first proposed/created by Edsger Dijkstra:

Dijkstra

Among his most famous contributions to computer science is Dijkstra’s algorithm, for finding the shortest path through a network, which is widely taught in modern computer science undergraduate courses, and is used in the computer network routing protocols OSPF and IS-IS.3637

Other important work included the Shunting yard algorithm for parsing; the “THE” operating system, an early example of structuring an operating system as a set of layers; the Banker’s algorithm for resource allocation; and the semaphore construct for coordinating multiple processes. Another concept formulated by Dijkstra in the field of distributed computing is that of self-stabilization, a method of ensuring fault-tolerance.

So what exactly is a semaphore, and how does it work? You can think of a semaphore as being an object that houses a single integer value. The value of this integer is changed using two critical functions (beyond just initializing the semaphore):

int sem_wait(sem_t *sem);
//Decrements the value of the semaphore by 1
//Wait if the value of the semaphore is negative
 
int sem_post(sem_t *sem);
//Increments the value of the semaphore by 1
//If there are one or more threads waiting, wake one

From the textbook

We should discuss a few salient aspects of the interfaces here. First, we can see that sem_wait() will either return right away (because the value of the semaphore was one or higher when we called sem_wait()), or it will cause the caller to suspend execution waiting for a subsequent post. Of course, multiple calling threads may call into sem_wait(), and thus all be queued waiting to be woken. Second, we can see that sem_post() does not wait for some particular condition to hold like sem_wait() does. Rather, it simply increments the value of the semaphore and then, if there is a thread waiting to be woken, wakes one of them up. Third, the value of the semaphore, when negative, is equal to the number of waiting threads. Though the value generally isn’t seen by users of the semaphores, this invariant is worth knowing and perhaps can help you remember how a semaphore functions.

Binary Semaphores (Locks)

Seems like a semaphore could, given the API above, be used in the following familiar way:

sem_t mySemaphore;
//Init the semaphore
 
sem_wait(&mySemaphore);
//critical section
sem_post(&mySemaphore);

And you’d be right! This is basically just using a semaphore as if you would a lock (so… a mutex!). To get a better understanding of how this works, look at the diagrams below. The first is an example of a single thread using the semaphore, without the second thread interacting with it at all:

The next is a look at how two threads would interact with the semaphore as a locking mechanism:

Used as a simple locking mechanism as shown above, you’d call this semaphore a binary semaphore (since the lock is either acquired or not).

Something about the above diagram is a bit screwy though… what happens if a bunch of threads contend for the semaphore lock at the same time? Wouldn’t that break the example above?

Turns out the textbook isn’t quite matching with real-world examples from the Linux semaphore API. Whenever a thread tries to call sem_wait (when acquiring the lock ), it won’t decrement the counter if it can’t acquire the lock. Thus, multiple threads calling sem_wait will cause them to block, while the value of the semaphore stays at 0. Once a thread calls sem_post to release the lock, the value of the semaphore will be set to 1 and a signal sent to wake a thread that is waiting on the lock.

From the Linux MAN Pages

sem_wait() decrements (locks) the semaphore pointed to by sem. If the semaphore’s value is greater than zero, then the decrement proceeds, and the function returns, immediately. If the semaphore currently has the value zero, then the call blocks until either it becomes possible to perform the decrement (i.e., the semaphore value rises above zero), or a signal handler interrupts the call.

Later in the chapter, the authors actually call this out when implementing their own version of a semaphore as an exercise:

From the book

One subtle difference between our [sempahore] and pure semaphores as defined by Dijkstra is that we don’t maintain the invariant that the value of the semaphore, when negative, reflects the number of waiting threads; indeed, the value will never be lower than zero. This behavior is easier to implement and matches the current Linux implementation.

Ordering: waiting to continue execution

We can also use semaphores in a manner similar to our pthread_join code from HW3. We’d like to do have a paradigm similar to the following:

Parent thread    -> Spawn worker thread(s) and wait
Worker thread(s) -> Do work signal that work is done
Parent thread    -> Receive signal, continue running

So how do we accomplish this with a semaphore? Let’s start with handling a single worker thread. We first initialize the semaphore to 0. After the parent thread spawns the worker, it calls sem_wait. Since the semaphore as been initialized to 0, the parent will wait until the semaphore’s value becomes 1. Meanwhile on the worker thread, it will do its work and eventually call sem_post, incrementing the value of the semaphore and signaling to the waiting parent that it should start again.

We may instead encounter a situation where the spawned worker thread is immediately scheduled, before the parent can call sem_wait. In this case the worker thread will call sem_post, incrementing the value of the semaphore to 1. When the parent thread is scheduled and calls sem_wait, it will immediately proceed by decrementing the semaphore’s value back to 0, and continues on its merry way!

Deadlock

Deadlock is a an unfortunate situation that can arise in concurrent programs that will cause the program to essentially wait forever, freezing itself. This happens when Thread 1 is holding onto resource A, and Thread 2 is holding onto resource B. Each thread need’s the other’s resource, but won’t relinquish their resource until they receive the one they’re waiting on. Sort of a “You first” “No, YOU first” problem.

We won’t be discussing this situation much now, because it strays away from our discussion about operating systems and more into “how to correctly write concurrent code”, and this isn’t something we really need the OS (or the supporting hardware) to help us with. But, figured I’d mention it here anyway!

Graph View

Backlinks