【自制操作系统13】锁

2020 年 3 月 8 日
筆記

没错，就是你们这群高级程序员（其实我也是）所耳熟能详但又讲不明白的锁，只是本章不是如何用，也不是讲它是什么原理，而是在实现我们操作系统的过程中所自然而然地产生的一个需求，并且我们从零开始来实现锁

本章需要和上一章【自制操作系统12】熟悉而陌生的多线程连起来看，因为正是上一章我们多线程输出字符串时，发现了一些问题，导致我们需要想个办法来解决，用你们高级程序员的牛逼的话来讲，就是 为了解决线程不安全的问题，提出了锁这种技术手段。

一、到目前为止的程序流程图

为了让大家清楚目前的程序进度，画了到目前为止的程序流程图，如下。（红色是我们要实现的）

二、上一篇文章的多线程问题

上篇文章我们创建了两个线程，加上主线程，一共三个线程循环打印字符串，最终的输出是这样的

　　先忽略上面那个异常，看下面话框的地方，argA 还没有打印完，就从中间断开了，开始打印了 argB

　　其实很好解释，因为 打印一个字符串 put_str 是通过一次次调用 put_char 来实现的，假如任务切换刚好发生在打印字符串 “argA” 刚刚打印到 “ar” 的时候切换了（实际上这概率很大），就会出现上面的问题。再往细了说，单单一个 put_char 函数，也是分成 获取光标、打印字符、更新光标值 等多个步骤实现的，假如在中间某处发生了任务切换，不但字符串被分割，还会出现少字符的情况，大家可以想想为什么。至于最上面的异常，当然也是由于类似的原因造成的。

　　上面的种种问题，归纳起来就是，虽然我们的任务切换可以发生在任何一个指令和下一条指令之间，但有的时候我们希望多条指令是具有 原子性 的，也就是要么不执行，要执行就全部执行完，这中间不允许发生任务切换。考虑到这点，我们可以通过简单的开关中断来实现，就像这样。

void k_thread_a(void* arg) {      char* para = arg;      while(1) {          intr_disable(); // 关中断          put_str(para);          intr_enable(); // 开中断      }  }

　　我们再运行程序，就会发现上述问题被完美解决了。可别瞧不起这粗暴的方法，关中断是实现互斥最简单的方法，没有之一。我们今后实现的各种互斥手段也将以它为基础。

三、问题抽象（公共资源、临界区、互斥、竞争条件）

刚刚提到的问题只是特例，我们把它归纳总结为一般描述，就是：

公共资源：可以是公共内存、公共文件、公共硬件等，总之是被所有任务共享的一套资源
临界区：么各任务中访问公共资源的指令代码组成的区域，注意是指令哦
互斥：某一时刻公共资源只能被 1 个任务独享，即不允许多个任务同时出现在自己的临界区中
竞争条件：多个任务以非互斥的方式同时进入临界区，对公共资源的访问是以竞争的方式并行进行的，因此公共资源的最终状态依赖于这些任务的临界区中的微操作执行次序。

在我们这个例子中，对应关系就是

公共资源：光标寄存器、显存
临界区：put_char 函数，因为该函数都对公共资源光标寄存器进行了访问
互斥：暂时通过开关中断，实现 put_str 之间的互斥
竞争条件：“少字符”问题是对显存未实现互斥访问造成的，“GP”异常是对光标寄存器未实现互斥访问造成的

　　总结起来，多线程的问题就是，多个任务同时出现在临界区，也就是产生了竞争条件。那解决问题的办法就只有一个，那就是 不要让多个任务同时出现在临界区。怎么做到这一点呢？刚刚简单粗暴的 开关中断 是一种方法，下面要说的更灵活的锁也是一种方法，再后面把多条指令重新用 一条原子指令 实现，如 CAS，也是一种方法。千万不要被再后面各种各样五花八门的各种技术绕晕，多线程解决的问题都是，不要让多个任务同时出现在临界区，仅此而已。

四、信号量与锁

我们的锁是用信号量来实现的，信号量就是一个计数器，它包括了 P（down）和 V（up）操作

V（up）：可以理解为释放锁

将信号量的值加 1
唤醒在此信号量上等待的线程

P（down）：可以理解为获取锁

判断信号量是否大于 0
若信号量大于 0，则将信号量减 1
若信号量等于 0，当前线程将自己阻塞，以在此信号量上等待

有了这两个操作，两个线程在进入临界区时，便可以这样操作

线程 A 进入临界区前先通过 down 操作 获得锁，此时信号量的值便为 0
线程 B 再进入临界区时也通过 down 操作获得锁，由于信号量为 0，线程 B 便在此信号量上等待，也就是相当于线程 B 进入了阻塞
当线程 A 从临界区出来后执行 up 操作 释放锁，此时信号量的值重新变成 1，之后线程 A 将线程 B 唤醒
线程 B 醒来后获得了锁，进入临界区

五、代码实现

锁的底层实现

sync.h

 1 // 信号量结构   2 struct semaphore {   3     uint8_t value;   4     struct list waiters;   5 };   6   7 // 锁结构   8 struct lock {   9     struct task_struct* holder; // 持有者  10     struct semaphore semaphore; // 二元信号量  11     uint32_t holder_repeat_nr; // 持有者重复申请锁的次数  12 };

sync.c

 1 #include "sync.h"   2 #include "list.h"   3 #include "global.h"   4 #include "interrupt.h"   5   6 // 初始化信号量   7 void sema_init(struct semaphore* psema, uint8_t value) {   8     psema->value = value; // 为信号量赋初值   9     list_init(&psema->waiters); // 初始化信号量的等待队列  10 }  11  12 // 初始化锁 plock  13 void lock_init(struct lock* plock) {  14     plock->holder = NULL;  15     plock->holder_repeat_nr = 0;  16     sema_init(&plock->semaphore, 1); // 信号量初值为1  17 }  18  19 // 信号量 down 操作  20 void sema_down(struct semaphore* psema) {  21     // 关闭中断保证原子操作  22     enum intr_status old_status = intr_disable();  23     while(psema->value == 0) {  24         // 表示已经被别人持有，当前线程把自己加入该锁的等待队列，然后阻塞自己  25         list_append(&psema->waiters, &running_thread()->general_tag);  26         thread_block(TASK_BLOCKED);  27     }  28     // value不为0，则可以获得锁  29     psema->value--;  30     intr_set_status(old_status);  31 }  32  33 // 信号量的 up 操作  34 void sema_up(struct semaphore* psema) {  35     // 关闭中断保证原子操作  36     enum intr_status old_status = intr_disable();  37  38     if (!list_empty(&psema->waiters)) {  39         struct task_struct* thread_blocked = elem2entry(struct task_struct, general_tag, list_pop(&psema->waiters));  40         thread_unblock(thread_blocked);  41     }  42  43     psema->value++;  44     intr_set_status(old_status);  45 }  46  47 // 获取锁 plock  48 void lock_acquire(struct lock* plock) {  49     if (plock->holder != running_thread()) {  50         sema_down(&plock->semaphore);  51         plock->holder = running_thread();  52         plock->holder_repeat_nr = 1;  53     } else {  54         plock->holder_repeat_nr++;  55     }  56 }  57  58 // 释放锁 plock  59 void lock_release(struct lock* plock) {  60     if (plock->holder_repeat_nr > 1) {  61         plock->holder_repeat_nr--;  62         return;  63     }  64     plock->holder = NULL;  65     plock->holder_repeat_nr = 0;  66     sema_up(&plock->semaphore);  67 }

thread.c

 1 ...   2   3 // 当前线程将自己阻塞，标志其状态为 stat(取值必须为 BLOCKED WAITING HANGING 之一)   4 void thread_block(enum task_status stat) {   5     enum intr_status old_status = intr_disable();   6     struct task_struct* cur_thread = running_thread();   7     cur_thread->status = stat;   8     schedule();   9     intr_set_status(old_status);  10 }  11  12 // 解除阻塞  13 void thread_unblock(struct task_struct* pthread) {  14     enum intr_status old_status = intr_disable();  15     if (pthread->status != TASK_READY) {  16         if (elem_find(&thread_ready_list, &pthread->general_tag)) {  17             // 错误！blocked thread in ready_list  18         }  19         // 放到队列的最前面，使其尽快得到调度  20         list_push(&thread_ready_list, &pthread->general_tag);  21         pthread->status = TASK_READY;  22     }  23     intr_set_status(old_status);  24 }

画黄线是重点要看的部分，也就是我们的目的，实现 获取锁 和 释放锁 两个函数。看整体逻辑

获取锁：如果锁的持有者不是当前线程，则 sema_down 信号量减一，锁的持有者变为当前线程。如果锁的持有者就是当前线程，则变量 holder_repeat_nr 递增，可以理解为可重入的次数
释放锁：变量 holder_repeat_nr 递减少，锁的持有者置空，执行 sema_up 信号量递增

上述两个函数中有两个子函数，是对信号量操作的，我们看一下

sema_down（信号量递减）：while 判断信号量值 value 是否为 0，若不为 0 则可以获取锁，直接将其减一；若为 0 表示锁被别的线程持有，则该线程加入信号量的等待队列 waiters，并阻塞该线程 thread_block。
sema_up（信号量递增）：信号量值 value++，同时若信号量等待队列 waiters 不为空，则表示有需要唤醒的线程，pop 出一个，唤醒该线程 thread_unblock

上述函数中又有两个子函数，我们继续拆解

thread_block（阻塞）：将当前线程的状态，改为阻塞态的一种（BLOCKED WAITING HANGING），并执行任务切换函数 schedule，由该函数真正将其换下 CPU
thread_unblock（唤醒）：唤醒一个指定线程，也就是上面由 sema_up 函数里从 waiters 中 pop 出来的线程。如果该线程不是 READY 状态（应该说不出错的话就不应该是 READY 状态），则将其放到 thread_ready_list 中，等待下次被调度

忘记了 schedule 函数的，可以看下面回顾一下

 1 // 实现任务调度   2 void schedule() {   3     struct task_struct* cur = running_thread();   4     if (cur->status == TASK_RUNNING) {   5         // 只是时间片到了，加入就绪队列队尾   6         list_append(&thread_ready_list, &cur->general_tag);   7         cur->ticks = cur->priority;   8         cur->status = TASK_READY;   9     } else {  10         // 需要等某事件发生后才能继续上 cpu，不加入就绪队列  11     }  12  13     thread_tag = NULL;  14     // 就绪队列取第一个，准备上cpu  15     thread_tag = list_pop(&thread_ready_list);  16     struct task_struct* next = elem2entry(struct task_struct, general_tag, thread_tag);  17     next->status = TASK_RUNNING;  18     switch_to(cur, next);  19 }

schedule

将所有这些都串起来，我画了个图，表示在各种情况下，各个变量是如何变化的（蓝色代表增加，绿色代表减少）

使用锁实现 console 输出

上一步我们只是实现了锁（其实就是实现了获取锁和释放锁两个函数），但我们还没有任何地方用它，接下来我们就重新封装一个原来多线程调用会出错的 put_str 函数的升级版（原子化） console_put_str

 1 static struct lock console_lock;   2   3 void console_init() {   4     lock_init(&console_lock);   5 }   6   7 void console_acquire() {   8     lock_acquire(&console_lock);   9 }  10  11 void console_release() {  12     lock_release(&console_lock);  13 }  14  15 void console_put_str(char* str) {  16     console_acquire();  17     put_str(str);  18     console_release();  19 }

可以看到，其实就是把 put_str 函数加了锁，又封装了一层而已。接下来我们 main 函数调用一下新输出函数的试试

 1 int main(void){   2     put_str("I am kerneln");   3     init_all();   4     thread_start("k_thread_a", 31, k_thread_a, "argA ");   5     thread_start("k_thread_b", 8, k_thread_b, "argB ");   6     intr_enable();   7   8     while(1) {   9         put_str("Main ");  10         console_put_str("Main ");  11     }  12     return 0;  13 }  14  15 void k_thread_a(void* arg) {  16     char* para = arg;  17     while(1) {  18         console_put_str(para);  19     }  20 }  21  22 void k_thread_b(void* arg) {  23     char* para = arg;  24     while(1) {  25         console_put_str(para);  26     }  27 }

可以看到画黄线的部分，我们只是把原来的 put_str 函数，更换成了 console_put_str 函数了而已，这样在输出的时候就有了锁的保护，多线程不再有上一章出现的问题了。简单吧！

运行

这回终于没有报错，且字符都整齐无误地输出在了屏幕上，不再有覆盖字符的现象了

写在最后：开源项目和课程规划

如果你对自制一个操作系统感兴趣，不妨跟随这个系列课程看下去，甚至加入我们（下方有公众号和小助手微信），一起来开发。

参考书籍

《操作系统真相还原》这本书真的赞！强烈推荐

项目开源

项目开源地址：https://gitee.com/sunym1993/flashos

当你看到该文章时，代码可能已经比文章中的又多写了一些部分了。你可以通过提交记录历史来查看历史的代码，我会慢慢梳理提交历史以及项目说明文档，争取给每一课都准备一个可执行的代码。当然文章中的代码也是全的，采用复制粘贴的方式也是完全可以的。

如果你有兴趣加入这个自制操作系统的大军，也可以在留言区留下您的联系方式，或者在 gitee 私信我您的联系方式。

课程规划

本课程打算出系列课程，我写到哪觉得可以写成一篇文章了就写出来分享给大家，最终会完成一个功能全面的操作系统，我觉得这是最好的学习操作系统的方式了。所以中间遇到的各种坎也会写进去，如果你能持续跟进，跟着我一块写，必然会有很好的收货。即使没有，交个朋友也是好的哈哈。

目前的系列包括

微信公众号

　　我要去阿里（woyaoquali）

小助手微信号

　　Angel（angel19980323）

while