Mutex Lock

Introduction

Mutex lock 用 mutual exclusion 保護 critical section：進入前 acquire()，離開後 release()。

while (true) {
    acquire(lock);
    /* critical section */
    release(lock);
    /* remainder section */
}

acquire() 與 release() 本身必須 atomic，否則 lock state 也會有 race condition。

簡化的 mutex 可用 boolean available 表示：

acquire() {
    while (!available)
        ;
    available = false;
}
 
release() {
    available = true;
}

當 lock 不可用時，等待者一直 loop 檢查，稱為 busy waiting；這種 lock 也叫 spinlock。

Spinlock 適合 lock 持有時間很短的情境，因為可以避免 sleep / wakeup 的 context switch overhead；若 critical section 很長，spin 會浪費 CPU。

Lock contention 指 thread acquire lock 時發現 lock 已被持有。