A mutex is a type of lock, sometimes also called a monitor. It is more specifically a type of blocking lock. Similarly to other types of locks, it includes the basic operations lock and unlock. It is most often used in conjunction with a condition variable that allows threads to synchronize events with each other. Mutexes make it possible for threads to wait on specific conditions, making them an extremely useful synchronization primitive when trying to synchronize threads.
Info
I’ve found the term “condition” to be super confusing. Because the condition in the mutex is not actually something like a boolean that a thread will check. It is just a queue that threads can put themselves in, saying “wake me up later”. You can have multiple of these queues per mutex, and they are super useful, but the actual “condition” that these queues depend on is not associated with a mutex at all. In general, you the programmer have to provide such a condition. This variable is sometimes called a predicate.
In order to implement a mutex, the following operations are necessary:
- Lock
- Unlock
- Wait: blocks until another thread signals
- Signal: unblocks a thread currently waiting, if one exists
- Broadcast: unblocks all threads currently waiting
Wait
The current thread, as long as it owns the mutex associated with the current condition, releases the mutex and blocks itself. Before the waiter blocks it atomically releases the mutex to allow other threads to acquire it.
The current thread is put into a waiting queue, waiting for another thread to signal or broadcast that it can wake up.
This is almost always paired with a predicate flag that checks for whether the condition being waited for has already occurred, to make sure that a thread doesn’t miss a signal.
Non-Testable
The predicate flag also makes it so your code handles spurious wakeups, which is when threads awaken when they shouldn’t. This can happen for a variety of reasons, and is implementation-dependent, but it shouldn’t happen in CPSC 213 with u_threads.
Signal
Signal awakens at most one thread. The calling thread will awaken the next thread in the queue of the condition of that mutex. In CSPC 213, this is based on a FIFO queue.
Proper usage of signal generally will require the thread that has been awoken to check a certain predicate upon wake-up. See the example usage below.
Broadcast
Broadcast awakens all waiting threads. May wake up too many. It is usually okay though sometimes a bit wasteful since threads re-check condition and wait again if necessary.
Example Implementation
This example is straight out of the u_thread library.
struct uthread_mutex {
uthread_t holder;
int reader_count;
spinlock_t spinlock;
uthread_queue_t waiter_queue;
uthread_queue_t reader_waiter_queue;
}
struct uthread_cond {
tuhread_mutex_t mutex;
uthread_queue_t waiter_queue;
}Example Usage
Typically, using a mutex to synchronize threads will look something like this:
int predicate = 0; //global static variable
uthread_mutex_t mtx;
uthread_cond_t condition;
void thread2(){
uthread_mutex_lock(mtx);
while(!predicate){
uthread_cond_wait(condition);
}
printf("%d", 2);
uthread_mutex_unlock(mtx);
}
void main() {
uthread_init(4); //initialize 4 user-level threads
mtx = uthread_mutex_create();
condition = uthread_cond_create(mtx); // initialize cond queue
u_thread_t thread = u_thread_create(thread, thread2); //pass the thread and a procedure to start with
uthread_mutex_lock(mtx);
printf("%d", 1);
predicate = 1;
uthread_cond_signal(condition);
uthread_mutex_unlock(mtx);
}Statically, we create a global condition, or a predicate. Generally this should be a numerical type like int, or char, that will be evaluated as true or false like a boolean.
The main thread initializes user threads using uthread_init. It assigns our mutex variable with a new mutex. It then creates a condition associated with that mutex, so that our threads have something to wait on. A new thread is then created and the process is split into two control flows.
The nascent thread starts running thread2. Let that thread be thread 2, and our original main thread be thread 1. Thread 1 and thread 2 then both attempt to acquire the mutex. There are two scenarios based on who acquires it first:
Thread 1 Acquires First
If thread 1 acquires the mutex first, it will lock the mutex, blocking thread 2 out of acquiring it and making the thread’s state blocked. Thread 1 keeps executing, printing 1. It sets the predicate int to 1, and signals. Since no threads are currently waiting on a signal, the signal is missed. The mutex unlocks.
Thread 2 acquires the mutex, checks if the global condition evaluates to true. Since it’s non-zero, it skips the wait call, prints 2, unlocks the mutex and completes.
Thread 2 Acquires First
If thread 2 acquire the mutex first, it will check if the global condition is true, which it is not, and call wait. If thread 1 attempts to acquire the mutex before the wait call, it will be blocked, since the mutex is currently held by thread 2.
Once thread 2 calls wait, thread 2 will block itself, atomically release the mutex, and put itself in the condition queue for the mutex, waiting for a signal. Releasing the mutex makes thread 1 runnable again, and thread 1 resumes and proceeds to acquire the mutex and print 1. It sets the predicate to 1, then signals. Since thread 2 is waiting on that condition, it will make itself runnable instead of blocked. Both threads are now running concurrently. Thread 2 prints 2, and the mutex is unlocked and both threads complete.
Theoreticals
So the above implementation basically guarantees a certain order of print statements, and can be extended to have as many threads as possible by adding more conditions (or using semaphores). Try thinking about what would happen if for example,
There were no global condition?
Answer
If there were no global condition, in the first scenario where thread 1 acquires first, because the signal thread 1 produces is missed by thread 2, once thread 1 completes and releases the mutex for thread 2 to have, it would wait indefinitely, on a signal that would never come.
We used an if instead of a while?
Answer
In this case, not much would happen. No other thread would be messing with our thread, so it’s theoretically completely fine to have an if statement here. However, it’s considered good practice to use a while loop, because the cost of using it is pretty insignificant in comparison to that of a potential deadlock. Furthermore, in many other implementations of threads there are other factors that could cause a thread to wake up when it shouldn’t.
Signal and Mutex Races
It is possible for multiple threads competing for a single mutex to continually exclude a thread, whether through being ‘unlucky’ or other mechanisms, effectively causing thread starvation through what’s called a signal or mutex race.