Chapter 26: Mutex

26.1 What is a Mutex?

A mutex (mutual exclusion) is a synchronization primitive that provides exclusive access to a resource. Only one thread can hold the mutex at a time. If another thread tries to acquire a held mutex, it sleeps (blocks) until the mutex is released. This is different from a spinlock (Chapter 27), where the thread busy-waits.

Use a mutex when:

• The critical section is long (more than a few microseconds)
• The thread might block while holding the lock (e.g., waiting for I/O)
• You want to avoid wasting CPU cycles on busy-waiting

26.2 Mutex Data Structure

/* Mutex structure */
struct mutex {
    int locked;            /* 0 = unlocked, 1 = locked */
    struct tcb *owner;     /* Thread currently holding the lock */
    struct wait_queue waiters;  /* Queue of threads waiting for this lock */
};

/* Wait queue entry */
struct wait_queue {
    struct tcb *thread;
    struct wait_queue *next;
};

26.3 Mutex Lock Implementation

/* Try to acquire the mutex without sleeping */
int mutex_trylock(struct mutex *m) {
    return atomic_cas(&m->locked, 0, 1);
}

/* Acquire the mutex, sleeping if needed */
void mutex_lock(struct mutex *m) {
    while (1) {
        /* Try to lock */
        if (atomic_cas(&m->locked, 0, 1)) {
            m->owner = get_current_thread();
            return;
        }

        /* Lock is held: add ourselves to the wait queue and sleep */
        struct tcb *current = get_current_thread();
        current->state = PROCESS_BLOCKED;

        /* Add to wait queue (atomically) */
        spinlock_lock(&m->waiters.lock);
        wait_queue_add(&m->waiters, current);
        spinlock_unlock(&m->waiters.lock);

        /* Schedule another thread */
        thread_schedule();

        /* When we wake up, try again */
    }
}

/* Release the mutex */
void mutex_unlock(struct mutex *m) {
    /* Wake up one waiting thread */
    spinlock_lock(&m->waiters.lock);
    struct tcb *waiter = wait_queue_remove(&m->waiters);
    spinlock_unlock(&m->waiters.lock);

    if (waiter) {
        waiter->state = PROCESS_READY;
        thread_enqueue(waiter);
    }

    /* Release the lock */
    m->owner = NULL;
    atomic_set(&m->locked, 0);
}

26.4 Priority Inversion and Priority Inheritance

Priority inversion occurs when a high-priority thread is blocked waiting for a mutex held by a low-priority thread, and a medium-priority thread preempts the low-priority thread. The high-priority thread is effectively delayed by the medium-priority thread.

Priority inheritance solves this: when a high-priority thread waits for a mutex, the mutex owner temporarily inherits the high priority. This prevents medium-priority threads from preempting the lock holder.

/* Mutex lock with priority inheritance */
void mutex_lock_priority(struct mutex *m) {
    while (1) {
        if (atomic_cas(&m->locked, 0, 1)) {
            m->owner = get_current_thread();
            return;
        }

        struct tcb *current = get_current_thread();
        struct tcb *owner = m->owner;

        /* Priority inheritance: boost owner's priority */
        if (current->priority < owner->priority) {
            owner->original_priority = owner->priority;
            owner->priority = current->priority;
        }

        /* Sleep on wait queue */
        current->state = PROCESS_BLOCKED;
        wait_queue_add(&m->waiters, current);
        thread_schedule();
    }
}

void mutex_unlock_priority(struct mutex *m) {
    /* Restore owner's original priority */
    m->owner->priority = m->owner->original_priority;

    /* Wake up next waiter */
    struct tcb *waiter = wait_queue_remove(&m->waiters);
    if (waiter) {
        waiter->state = PROCESS_READY;
        thread_enqueue(waiter);
    }

    m->owner = NULL;
    atomic_set(&m->locked, 0);
}

26.5 Mutex vs Spinlock Decision

Characteristic	Mutex	Spinlock
Wait behavior	Sleep (context switch)	Busy-wait (spins)
CPU usage while waiting	None (other thread runs)	100% (wastes cycles)
Critical section length	Any length	Short (microseconds)
Can be used in interrupt	No (might sleep)	Yes (if IRQs disabled)
Overhead per acquire	Higher (context switch)	Lower (spins a few cycles)
Priority inversion	Possible (use PI)	Not applicable (no sleep)

26.6 Our Implementation

Our kernel provides both regular and priority-inheritance mutexes. The default mutex has priority inheritance enabled. Key implementation details:

• FIFO wait queue: threads are woken in the order they arrived (fair)
• Recursive mutex flag: optional, allows the owning thread to lock again without deadlocking
• Mutex debugging: tracks owner, check for double-unlock, detects lock held too long
• Interrupt safety: mutex_lock/mutex_unlock use local IRQ disable to protect the wait queue (preventing race with interrupt handlers)

/* Mutex with interrupt safety */
void mutex_lock_irq(struct mutex *m) {
    uint64_t flags = local_irq_save();
    mutex_lock(m);
    m->irq_flags = flags;
}

void mutex_unlock_irq(struct mutex *m) {
    uint64_t flags = m->irq_flags;
    mutex_unlock(m);
    local_irq_restore(flags);
}

26.7 Exercises

26.8 Summary

A mutex provides mutual exclusion with sleep-wait semantics: threads that cannot acquire the lock block and yield the CPU. Mutexes are suitable for long critical sections and situations where the lock holder might block. Priority inheritance prevents priority inversion by temporarily boosting the lock holder's priority. Our kernel implements mutexes with FIFO wait queues, optional recursion, and interrupt-safe variants. The choice between mutex and spinlock depends on critical section length, context (interrupt vs thread), and contention level.