记录实现操作系统互斥锁的一次思考

今天实现操作系统互斥锁的时候遇到一个有趣的问题。

场景

有两个进程分别名为 taskA，taskB，采取时间片轮转的方式交替运行——也即维护了一个 ready_queue，根据时钟中断来 FIFO 地调度任务。它们的任务是无限循环调用 sys_print() 来打印自己的名称。

我还设置了一个 mutex 互斥锁，它包含一个 0/1 互斥信号量：用于表示锁是否已经被取走，还有一个等待队列 waiting_queue：用于存放正在等待该锁的进程。

为了保证打印出来的字符不错乱，我为 sys_print() 函数设置一个 mutex 对象，我们暂且称之为 print_mutex。在调用 sys_print() 前执行 mutex_lock() 上锁，如果此时锁已经被取走，那么将当前任务加入 print_mutex 的 waiting_queue。调用 sys_print() 后执行 mutex_unlock() 解锁，如果 waiting_queue 中有任务，那么将 print_mutex 直接分配给其中的第一个任务，同时将该任务加入进程的就绪队列，否则将锁归还，由需要该锁的进程主动来取锁。

运行

想一想，这时候运行系统，屏幕上的输出形式是怎么样的呢？

容易想到一些情况：

一、交替连续输出，且无打印出错误，形如以下形式

taskA
taskA
taskA
taskB
taskB
taskB
taskA
taskA
taskA
... ...

二、交替连续输出，但在进程切换的瞬间，有打印错乱的可能，形如以下形式

taskA
taskA
tastaskB
taskB
taskB
ttaskA
taskA
taskA
... ...

三、严格交替输出，且无打印出错误，形如以下形式

taskA
taskB
taskA
taskB
taskA
taskB
... ...

四、严格交替输出，但在进程切换的瞬间，有打印错乱的可能，形如以下形式

tasktaskB
tataskB
taskA
tataskA
... ...

其实还有很多其他可能，碍于篇幅受限，不再列出。

输出

很容易想到，加了互斥锁 print_mutex 后，肯定不会出现打印错乱的情况，因此情况二和情况四首先排除，那么到底是情况一还是情况三呢？大家可以根据场景先思考一下。

好了，公布答案，最终形式其实既不是情况一也不是情况三，而是这样的：

taskA
taskA
taskA
taskA
taskA
taskB
taskA
taskB
... ...

也就是一个任务先连续输出，然后两个任务严格交替输出，如下图：

分析

假设先上时间片运行的是 taskA，那么在第一个时间片周期中， taskA 可以调用 sys_print() 函数若干次，当时间片发生切换的瞬间，taskA 会被挂起，然后重新加入到 ready_queue 尾部，等待下一次被分配 cpu。

这个任务的功能很简单，可以简化成以下形式：

void taskA(){while(true){metux_lock();   //关中断保证原子操作sys_print();mutex_unlock(); //关中断保证原子操作}
}

其中 mutex_lock() 和 mutex_unlock() 都关中断保证了不会有时钟中断发生， 所以在切换进程的时候，taskA 可能会

1. 停留在 metux_lock() 之前、mutex_unlock() 之后
2. 停留在 sys_print() 中

显然，由于sys_print() 需要与外围设备端口交互，包含的指令数也比较多，而情况1 包含的指令数极少，因此 taskA 此时绝大概率停留在 sys_print() 中，也就是 taskA 持有 print_mutex 互斥锁，并在 ready_queue 中等待执行，而这时候 taskB 虽然被分配了时间片，但在执行 mutex_lock() 的时候发现锁已被取走，只能进入 print_mutex 的 waiting_queue 等待。taskA 重新上cpu 运行，执行完上次执行一半的 sys_print() 之后，紧接着执行 mutex_unlock() 将锁分配给锁等待队列中的 taskB，下一轮循环时，taskA 执行 mutex_lock() 发生锁等待被挂起，循环往复，两者就严格交替打印了。

事实上，如果 taskA 在切换时间片的时候遇到的是情况 1，那么也可能出现两个进程交替连续打印的情况，但是这个概率极小。