自制操作系统 - 互斥、信号量与锁 | 王富杰的博客

一、原子操作

在单处理机系统中，单个指令总是原子的，所以对于单指令例如 xchg 或者 inc 等都是原子的。

如果一个操作需要多个 CPU 指令，由于每条指令结束之后都可能发生中断，而发生上下文切换，那么这个操作就可能不会很好的完成。所以就可能需要加锁机制来防止这种情况发生。但加锁很可能不高效，所以为了执行原子操作的指令序列，有时候禁止中断可能反而更高效。

1.1、信号量

信号量是一种最古老而且应用最广泛的保证互斥的方法，计算机中信号量是个整数值，由于 Dijkstra 是荷兰人，他用 P(Proberen) 尝试减少和 V(Verhogen) 增加，来表示信号的变化，但 PV 操作语义并不明显，因此这里使用 up 和 down 来表示对信号量的增减，当然也有人使用 wait 和 signal 来表示信号量的操作。

1.2、互斥量

当信号量使用 0/1 二值来表示时，就是互斥量，表示临界区只能有一个进程可以取得。当信号量只有一个资源时就是互斥量。互斥量的实现：

typedef struct mutex_t
{
    bool value;     // 信号量
    list_t waiters; // 等待队列
} mutex_t;

void mutex_init(mutex_t *mutex)
{
    mutex->value = false; // 初始化时没有被人持有
    list_init(&mutex->waiters);
}

void mutex_lock(mutex_t *mutex)    // 尝试持有互斥量
{
    bool intr = interrupt_disable();   // 关闭中断，保证原子操作
    task_t *current = running_task();
    while (mutex->value == true)
    {
        task_block(current, &mutex->waiters, TASK_BLOCKED);  // 若 value 为 true，表示已经被别人持有。则将当前任务加入互斥量等待队列
    }
    assert(mutex->value == false);  // 无人持有
    mutex->value++;      // 持有
    assert(mutex->value == true);
    set_interrupt_state(intr);   // 恢复之前的中断状态
}

void mutex_unlock(mutex_t *mutex)       // 释放互斥量
{
    bool intr = interrupt_disable();    // 关闭中断，保证原子操作
    assert(mutex->value == true);       // 已持有互斥量
    mutex->value--;                     // 取消持有
    assert(mutex->value == false);
    if (!list_empty(&mutex->waiters))     // 如果等待队列不为空，则恢复执行
    {
        task_t *task = element_entry(task_t, node, mutex->waiters.tail.prev);
        assert(task->magic == ONIX_MAGIC);
        task_unblock(task);
        task_yield();  // 保证新进程能获得互斥量，不然可能饿死
    }
    set_interrupt_state(intr);     // 恢复之前的中断状态
}

前边我们多线程打印争抢控制台资源的问题时，遇到了打印有问题，当时通过在控制台输出函数处进行了关中断保障原子性。现在拥有了互斥量，就可以通过互斥量来解决。在线程中，每次执行打印前申请互斥量，打印完成释放互斥量。

注意在释放互斥量后当前线程交出执行权，这是需要防止其他线程被饿死，因此当前线程循环打印，释放互斥量后可能立即再次申请了互斥量。

二、锁

锁有三种，分别为互斥锁、自旋锁、和读写锁。

2.1、互斥锁

互斥锁是基于互斥量实现的，互斥锁可以重入，即一个线程可以多次申请，同样需要多次释放。结构如下：

typedef struct lock_t
{
    struct task_t *holder; // 持有者
    mutex_t mutex;         // 互斥量
    u32 repeat;            // 重入次数
} lock_t;

互斥锁初始化、申请和释放我们这里就省略了。也是需要关中断，然后通过修改互斥量来保护临界区。

2.2、自旋锁

自旋锁最多只能被一个可执行线程持有。如果一个执行线程试图获得一个被已经持有（即所谓的争用）的自旋锁，那么该线程就会一直进行忙循环一旋转一等待锁重新可用。要是锁未被争用，请求锁的执行线程便能立刻得到它，继续执行。在任意时间，自旋锁都可以防止多于一个的执行线程同时进入临界区。同一个锁可以用在多个位置，例如，对于给定数据的所有访问都可以得到保护和同步。

使用 CAS (Compare And Swap) 原语实现，IA32 中是 cmpxchg 指令，但在多处理机系统中 cmpxchg 指令本身不是原子的，还需要加 lock 来锁定内存总线实现原子操作。

2.3、读写锁

有时，锁的用途可以明确地分为读取和写入两个场景。并且绝大多数是读的情况，由于读并不影响数据内容，所以如果直接加锁就会影响性能，那么可以将读和写区别开来，这种形式的锁就是读写锁；

当对某个数据结构的操作可以像这样被划分为读／写或者消费者／生产者两种类别时，类似读／写锁这样的机制就很有帮助了。这种自旋锁为读和写分别提供了不同的锁。一个或多个读任务可以并发地持有读者锁：相反，用于写的锁最多只能被一个写任务持有，而且此时不能有并发的读操作。有时把读／写锁叫做共享排斥锁，或者并发／排斥锁，因为这种锁以共享（对读者而言）和排斥（对写者而言）的形式获得使用。

但在实现的时候需要注意，有可能会发生读者过多而饿死写着的情况。如果写的情况比较多就不应该使用这种锁。

三、说明

这里实现的互斥量和互斥锁都需要关中断，因此只能内核态调用。至于用户态，等到了用户态再展开介绍。因为我们开发的单处理系统，因此内核暂不实现自旋锁，因为自旋锁在单处理系统可能存在死锁风险，如线程A持有自旋锁 → 时间片用完被调度器抢占 → 线程B尝试获取锁 → 线程B忙等待（自旋） → 线程A因CPU被线程B占用而永远无法执行并释放锁。

「真诚赞赏，手留余香」

自制操作系统 - 互斥、信号量与锁

互斥、信号量与锁