记录实现操作系统互斥锁的一次思考
今天实现操作系统互斥锁的时候遇到一个有趣的问题。
场景
有两个进程分别名为 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 直接分配给其中的第一个任务,同时将该任务加入进程的就绪队列,否则将锁归还,由需要该锁的进程主动来取锁。
运行
想一想,这时候运行系统,屏幕上的输出形式是怎么样的呢?
容易想到一些情况:
一、交替连续输出,且无打印出错误,形如以下形式
1 | taskA |
二、交替连续输出,但在进程切换的瞬间,有打印错乱的可能,形如以下形式
1 | taskA |
三、严格交替输出,且无打印出错误,形如以下形式
1 | taskA |
四、严格交替输出,但在进程切换的瞬间,有打印错乱的可能,形如以下形式
1 | tasktaskB |
其实还有很多其他可能,碍于篇幅受限,不再列出。
输出
很容易想到,加了互斥锁 print_mutex 后,肯定不会出现打印错乱的情况,因此情况二和情况四首先排除,那么到底是情况一还是情况三呢?大家可以根据场景先思考一下。
好了,公布答案,最终形式其实既不是情况一也不是情况三,而是这样的:
1 | taskA |
也就是一个任务先连续输出,然后两个任务严格交替输出,如下图:
分析
假设先上时间片运行的是 taskA,那么在第一个时间片周期中, taskA 可以调用 sys_print() 函数若干次,当时间片发生切换的瞬间,taskA 会被挂起,然后重新加入到 ready_queue 尾部,等待下一次被分配 cpu。
这个任务的功能很简单,可以简化成以下形式:
1 | void taskA(){ |
其中 mutex_lock() 和 mutex_unlock() 都关中断保证了不会有时钟中断发生, 所以在切换进程的时候,taskA 可能会
- 停留在 metux_lock() 之前、mutex_unlock() 之后
- 停留在 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,那么也可能出现两个进程交替连续打印的情况,但是这个概率极小。