Mutex Lock

A mutex (mutual-exclusion lock) is a synchronization primitive used solely to enforce mutual exclusion on a critical section.

Mutex vs binary semaphore

A binary semaphore has the same fields but does not track the owner. A mutex knows who holds it, so only the owner can release.

Typical fields (from CS343):

class MutexLock {
    bool avail;                    // resource available?
    Task * owner;                  // lock owner (nullptr if free)
    queue<Task> blocked;           // tasks waiting to acquire
    SpinLock lock;                 // internal spin lock
};

• avail alone is not enough, the blocked queue can be empty while the CS is still occupied, so avail exists independently
• owner lets release error-check and supports multiple acquisition (recursive re-entry, see uOwnerLock)
• Internal SpinLock serializes access to the three fields above; held for a short window around enqueue/dequeue

The yieldNoSchedule(lock) trick

Blocking must be atomic with spin-lock release, or there’s a race: blocker releases lock ⇒ preempted ⇒ unblocker enters, sees blocker in the queue, moves them to the ready queue ⇒ blocker is now on both the blocked queue and the ready queue. Fix: runtime cooperation.

// add self to blocked list
yieldNoSchedule( lock );     // runtime: yield slice, do NOT put on ready queue,
                             // then release lock on behalf of the task

Passing the spin lock into the runtime makes “release lock + yield without rescheduling” a single uninterruptible step. Alternative is park/unpark with a private per-task binary semaphore (see Solution 6 of Reader-Writers).

Barging: three regimes

1. Plain (barging allowed), released task busy-waits in while (! avail); incoming bargers can overtake, unbounded starvation possible
2. Barging avoidance, releaser holds avail until the unblocked task runs; bargers enter the protocol but block. Released task uses if not while. Bounded overtaking, but a spinlock-unfair runtime still lets infinite bargers block the spinlock acquire
3. Barging prevention, releaser holds the spinlock itself (does not call release) until the unblocked task runs. Critical section is no longer bracketed by the spinlock, the lock is conceptually passed via baton passing. The unblocked task wakes already owning the spinlock

// barging prevention (owner-less variant)
void acquire() {
    lock.acquire();
    if ( blocked.empty() ) {                  // no one waiting ?
        // add self as owner at front
    } else {
        // add self to tail of blocked list
        yieldNoSchedule( lock );              // block with lock STILL held by runtime
    }
    lock.release();
}
void release() {
    lock.acquire();
    if ( ! blocked.empty() ) {
        // remove next task; do NOT lock.release()
        // baton (spinlock ownership) is passed to the unblocked task
    } else {
        lock.release();                       // no waiters, normal release
    }
}

In Rust, the standard pattern is to wrap a Mutex<T> in an Arc so multiple threads can share protected mutable state. Deadlock is still possible even with automatic unlock: thread 1 taking A then B while thread 2 takes B then A will still hang.

Related

• Arc (Rust)
• Semaphore