互斥锁

互斥锁的工作流程，可以按照如下进行描述：

当一个线程请求一个已经被其他线程持有的互斥锁时，该线程会被阻塞并进入睡眠状态，直到锁被释放。这种方式的优点是不会浪费 CPU 资源，因为线程会被挂起，直到它可以获得锁。此时，其他线程可以取得 CPU 的控制权。然而，线程的挂起和唤醒需要操作系统进行上下文切换（systemcall），这是一个相对昂贵的操作。

一个更为形象的解释：

以下是一个 c 语言的简单实现：

// 定义锁的数据结构
typedef struct __lock_t {
    int flag; // 标志位，用于表示锁是否被持有，0表示未被持有，1表示已被持有
    int guard; // 保护位，用于保护flag字段，防止同时修改flag
    queue_t *q; // 等待队列，用于存储等待获取锁的线程
} lock_t;

// 初始化锁
void lock_init(lock_t *m) {
    m->flag = 0; // 设置锁为未被持有状态
    m->guard = 0; // 设置保护位为0
    queue_init(m->q); // 初始化等待队列
}

// 获取锁
void lock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1) // 自旋，直到获取保护位
        ; 
    if (m->flag == 0) {
        m->flag = 1; // 如果锁未被持有，获取锁
        m->guard = 0; // 释放保护位
    } else {
        queue_add(m->q, gettid()); // 如果锁已被持有，将当前线程添加到等待队列
        m->guard = 0; // 释放保护位
        park(); // 挂起当前线程，等待被唤醒
    }
}

// 释放锁
void unlock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1) // 自旋，直到获取保护位
        ;
    if (queue_empty(m->q))
        m->flag = 0; // 如果等待队列为空，释放锁
    else
        unpark(queue_remove(m->q)); // 如果等待队列非空，唤醒队列中的一个线程，并将锁传递给它
    m->guard = 0; // 释放保护位
}