otherworld

Mutex

5 min read

Stands for mutual exclusion. Also called a lock or a semaphore.1 They are mechanisms provided by the OS.

To prevent two Threads from accessing and modifying the same global/shared resource, we can use the concept of a lock to only let one thread access a critical section, e.g. loading a value, incrementing it, storing it back.

This is executed in an atomic manner, meaning that it cannot be interruptible.

Acquiring and releasing

When a thread acquires a lock,2 it will block execution until the lock is free, then take it for itself. When a thread releases a lock,3 if there are other threads waiting, then it will wake up exactly one of them to pass the lock to.

POSIX threads mutex API

Also see POSIX threads API. Since locks are inherently tied to threads, the locks API that POSIX includes is part of the pthreads library.

<pthread.h> defines the datatype pthread_mutex_t with a whole family of pthread_mutex_* functions to initialize, acquire, release, and destroy a mutex.

Stuff that also deals with concurrency and synchronization. Either allows us to implement mutexes or can completely replace them.

Test and set lock (test-and-set, TSL)

A hardware instruction implemented by processors that is guaranteed to be atomic at the hardware level.

Given a memory location, the instruction returns it (by reading from it and writing the value to a register), and then sets the value of the memory location to 1.

Implementing a mutex

We can use this primitive to implement a lock:

  1. Create a variable int lock that represents our lock. Initialize it to zero.
  2. For a thread to acquire a lock, it calls the TSL instruction using lock as the memory location. This returns the previous value. If it was zero, then this thread has successfully acquired the lock. If the previous value was already one, then the lock is currently acquired by another thread.
  3. For a thread to release the lock, it simply sets lock back to zero and wakes up any threads that were blocked when they tried acquiring it.

Pseudocode for implementing pthread_mutex_t:

void pthread_mutex_lock(lock) {
    int prev_value = TSL(lock);
 
    // If prev_value = 1, then the lock was already acquired
    // by another thread. Therefore we should block this thread.
    while (prev_value == 1) {
        block_this_thread();
 
        // Thread will become unblocked when the lock is released.
        // Here we attempt to acquire it again. If we fail, we
        // repeat the while loop another time.
        prev_value = TSL(lock);
    }
}
 
void pthread_mutex_unlock(lock) {
    // Since the lock can only ever have the values 0 or 1, the
    // lock could totally be a boolean as well
    lock = 0;
    wakeup_all_blocked_threads(lock);
}

Disabling interrupts

If the issue is that a thread cannot be interrupted while performing some critical work, what if we simply disable interrupts for a thread? This way we literally can’t switch to another thread.

Disabling interrupts disables the global clock interrupt that interrupts the currently running thread. This has some problems:

  • Will stop threads that aren’t trying to access shared resources from running as well
  • If interrupts are disabled for a long time, other threads will starve
  • In a multi-core environment, this becomes complicated to implement/manage
  • Generally a bit overkill—should only be done on the kernel level

Peterson’s algorithm

  1. Each thread first declares they want to enter the critical section by setting their flag to true
  2. Each thread then states that the other thread should “go first.” This is done by setting the value of a variable turn to the “index” or “ID” assigned to a thread. One of these assignments to turn will happen last, and that’s the one that decides who goes first
  3. One of the threads goes first (originally decided by turn), accesses the critical section, and then sets itself as done by setting its flag to false

Here is an example with two threads, but the algorithm can be generalized for more than two.

// The shared resource we're modifying
int sum_total = 0;
 
// Keeping track of the thread flags and whose turn it is
bool flag[2] = {false, false};
int turn = 0;
 
void thread_code(int arg) {
    // `arg` represents the index/ID of the thread
    int me = arg;
    flag[me] = true;
 
    // Attempt to give the turn to the other thread
    int other_thread = 1 - me;
    turn = other_thread;
 
    while (flag[other_thread] && (turn != me)) { /* Block */ }
 
    // Critical section
    sum_total++;
 
    // Thread marks itself as finished with critical section
    flag[me] = false;
}

Mutual exclusion happens here because only one thread at a time will not satisfy the while loop constraints. Even if all thread flags were true, only one thread will have the turn, therefore turn != me evaluates to false.

When that thread is done and it sets its own flag to false, this triggers one other thread to start running because they each check one other thread’s flag status.

Some assumptions that Peterson’s algorithm makes:

  • Reading from and writing to flag and turn cannot be interrupted
  • Instructions are executed in the specific order laid out in the code (this is not always true).

Also see

Footnotes

  1. There does seem to be differences between these terms but I don’t care about it right now. ↩

  2. Also called “locking” a mutex. ↩

  3. Aka “unlocking” a mutex. ↩

Graph View

Backlinks