浅谈锁机制

前言

在上节线程 - 进阶 - 任务调度的末尾，笔者演示了当删去 put_str() 上下的 STI 和 CLI 后发生的错误情况（打印不规律，且发生 GP 异常）这是为什么呢？这里就不卖关子了，直接原因是 线程不同步 。这样说了也当白说，让我们仔细还原现场：

k_thread_a 在 put_char 中读取了字符打印的光标位置 p 。
当 k_thread_a 准备更新光标位置时，中断发生，切换到 k_thread_b 。
k_thread_b 读取光标位置，由于 k_thread_a 还未更新光标，所以此时光标值仍为 p 。
于是，k_thread_b 在相同地方打印字符，覆盖了 k_thread_a 的字符。

因此才出现少字符的情况。对于其他错误，比如一大串空格以及 GP 异常，就不详细说明原因了，只需明白，它们的罪魁祸首都是线程不同步造成的。为了进一步解释什么叫线程不同步，先来看看下面几个概念：

临界区： 是指包含有共享数据的一段代码，这些代码可能被多个线程访问或修改。临界区的存在就是为了保证当有一个线程在临界区内执行的时候，不能有其他任何线程被允许在临界区执行。

注意，临界区是代码，不是受访的静态公共资源。
互斥： 某一时刻公共资源只能被一个任务访问，即，不允许多个任务同时出现在临界区中。
竞争条件： 多个任务以竞争的方式（非互斥）进入临界区，其最终的的结果依赖于多个进程的指令执行顺序。
举例：假设两个进程 P1 和 P2 共享了变量 a。在某一执行时刻，P1 更新 a 为 1，在另一时刻，P2 更新 a 为 2。因此两个任务竞争地写变量 a。在这个例子中，竞争的失败者（最后更新的进程）决定了变量 a 的最终值。多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关，称为竞争条件。

显然，我们代码中的临界区就应该为 put_char（准确来说，是 put_char 中操作光标的代码部分），而 k_thread_a 和 k_thread_b 两个线程以竞争的方式访问临界区，从而产生竞争条件，最终引发不同步导致错误。那么，如何才能实现互斥访问呢？最简单的方式就是像视频演示中的那样开关中断，但现实的方式是采用锁 。关于这两种方式的比较，请见文末。

下面我们来看看锁的进化历程，以此加深读者对锁的理解。

锁的进化

情景：金鱼有个很奇怪的特点，就是没有饱的感觉，如果你不停地给它喂食，它就会一直进食直到把自己撑死。现在线程 A 和线程 B 共同喂养一条金鱼，要求只能由其中一个线程进行喂食，即，若 A 线程已经投喂，那么 B 就不能再继续投喂；如果 B 线程已经投喂，则 A 线程也不能再投喂，否则金鱼被撑死。除了不能多次投喂外，也不能不进行投喂，即 A 和 B 线程中总有一者必须投喂金鱼，否则金鱼被饿死。

第一阶段

使用全局变量 if_feed 标记喂食情况：

//thread_A
if(if_feed == false){
    feed fish;
    if_feed = true;
}
//thread_B
if(if_feed == false){
    feed fish;
    if_feed = true;
}

这样就能防止多次投喂了吗？

哦豁，依旧投喂了两次，金鱼被撑死。这里的原因在于，A、B 两线程同时进入了临界区。

第二阶段

经过第一阶段的失败，我们吸取了教训：要防止金鱼胀死，就必须避免多个线程同时进入临界区，即需要做到互斥。下面通过留字条的方式来互斥：

//thread_A
noteA = true;
if(noteB == false)
{
    if(if_feed==false)
        feed fish;
}
noteA = false;
//==================
//thread_B
noteB = true;
if(noteA == false)
{
    if(if_feed==false)
        feed fish;
}
noteB = false;

以上代码无论按什么顺序穿插执行 A、B 线程，都不会再造成金鱼胀死了，但却可能饿死！如下：

哈哈，即使饿死，也比撑死好。这是因为几个线程同时获得一个资源，最终出现崩溃几乎是必然的事；如果谁都获取不了资源，则可能只是停止推进，而不一定产生错误结果。让我们继续改进。

第三阶段

为了保证投喂，我们让某个线程一直等着，直到确认对方投喂之后再离开：

//thread_A
noteA = true;
while(noteB == true){}
if(noteB == false)
{
    if(if_feed==false)
        feed fish;
}
noteA = false;
//================
//thread_B
noteB = true;
if(noteA == false)
{
    if(if_feed==false)
        feed fish;
}
noteB = false;

这样一来就能够保证金鱼能够被投喂了。但即使如此，以上方式仍存在较大问题：

程序不对称。功能完全相同，程序却不一样，这加大了代码的难度。
浪费 CPU 资源。线程 A 的 while 完全是白占着 CPU 资源。
可能造成优先级倒挂。

第四阶段
那么现在，我们又该怎么办呢？仔细思考后其实可以发现，第 2、3 个阶段的重心都落在字条上，即留字条是为了防止两个线程同时投喂或都不投喂金鱼。既然留字条不能完美地解决办法，那有没有其他方法来进行互斥呢？有，当要投喂时，进入房间，把门锁上，投喂金鱼，打好标记，解锁并离开房间：

//thread_A
lock();
if(if_feed == false)
{
    feed fish;
    if_feed = true;
}
unlock();
//thread_B
lock();
if(if_feed == false)
{
    feed fish;
    if_feed = true;
}
unlock();

这种为房间上锁的方式实际上是对第一种方案的改善，即，将检查标记和打标记合并为一个原子操作（投喂金鱼也被合并了）。如此一来，似乎就完美了。但再仔细观察后仍可以发现一个问题：如果线程 A 喂鱼的动作很慢，那么线程 B 将会被锁很长一段时间，这种等待不仅浪费 CPU 资源，也会降低系统效率。而且，喂鱼这个动作并非临界区，对标记的操作才是，所以完全可以将喂鱼的动作移出去：

//thread_A
lock();
if(noteB == false)
    noteA = true;
unlock();
if(noteB == false)
{
    if(if_feed == false)
        feed fish;
    noteA = false;
}
//==================
//thread_A
lock();
if(noteA == false)
    noteB = true;
unlock();
if(noteA == false)
{
    if(if_feed == false)
        feed fish;
    noteB = false;
}

谨记，临界区的动作越少越好！ 另外，当其他线程被锁在临界区外时，只能苦等锁被打开，除此之外无法进行任何动作，所以这些线程就不应该再占用 CPU 资源，即，在锁被打开前，CPU 不再调度这些任务，直到锁被打开后再恢复调度 。这就涉及到线程的睡眠与觉醒。

睡眠与觉醒：生产者和消费者问题

线程的睡眠和觉醒是指：当对方持有锁，将你锁在外面时，你无需一直敲门，而是可以在门口睡觉，等到对方解锁之后再来叫醒你 。下面用线程中经典的生产者和消费者问题来演示睡眠与觉醒。我们知道，一般来说，生产者（厂家）会将商品批发给超市，然后消费者在超市进行购买。如果没有超市这个中转站，生产者就无法独立操作，必须拿到消费者的订单才能生产；消费者也必须在每次订货后且等待商品完工后才能拿到货。显然，超市扮演着重要的缓冲区角色。现在抛出两个问题：1）当超市没货了怎么办？2）当超市货太多装不下怎么办？

现实的实际做法一般是：当超市没货了，如果有顾客上门购买商品，则告知顾客缺货并让顾客回家等候通知；当超市货满了，则通知厂商暂时不要再生产 。用代码表示即如下：

#define N 100  //超市最多能存下的商品数
int count = 0; //超市中现存的商品数

void producer(){
    while(1){
        if(count == N)
            sleep();         //不再生产
        count++;
        if(count == 1)
            wakeup(consumer);//通知客户取货
    }
}
void consumer(){
    while(1){
        if(count == 0)
            sleep();         //回家等通知
        count--;
        if(count == N-1)     //如果count==N-1,说明厂家一定处于睡眠状态
            wakeup(producer);//通知厂家生产
    }
}

注意，wakeup() 只是叫醒对方线程，即让其重新在 thread_ready_list 中，而不是立刻调度！

以上代码看上去正确无误，实际上存在着巨大问题：可能造成死锁！

死锁，即生产者和消费者均无法向前推进。

例如，若消费者先来，此时 count=0，则去睡觉，但在睡下的前一刻，CPU 任务调度，执行流转移到生产者。生产者开始运行，生产一件商品后发现 count=1，于是叫醒消费者。但此时消费者并没有睡觉（还在 thread_ready_list 中），所以这个叫醒信号无用。缓冲区满后，生产者转入睡眠，执行流转移到消费者。而消费者执行的第一个操作就是 sleep()，于是消费者也转入睡眠。最后两者都陷入睡眠状态并等待彼此叫醒自己，显然，它们都无法再醒来，系统死锁发生。

解决上述问题的方法也很简单。很容易发现，造成死锁的原因是因为叫醒信号的丢失。那我们想个办法将信号收集起来不就OK了嘛！消费者换上 CPU 执行 sleep 后，生产者发送的叫醒信号依然保留，因此消费者检测到该信号而觉醒。这种能够累积的信号就叫做信号量 。

信号量

实际上，信号量是操作系统中一个极其重要，威力巨大的概念，它不仅可以用来线程同步，还能用于进程间通信。我们现在仅讨论其作为锁的用途。当信号量的取值限制在 0 和 1 时，则获得了一把锁，也称二元信号量 。对信号量有 up、down 两种操作：

up： 1）将信号量加 1；2）唤醒在此信号量上等待的线程。
down： 1）判断信号量是否大于 0；2）若信号量大于 0，则将信号量减 1；3）若信号量等于 0，则在此信号量上睡眠。

因为信号量是荷兰科学家 Dijkstra 发明的一种程序设计规范，所以 up 和 down 也被称为 PV 操作，即荷兰语中的 Proberen 和 Verhogen 。

down 即获得锁，up 即解锁 。初始状态下信号量值为 1，某线程获得锁后，其值减为 0，当其他线程申请锁时，则只能在此锁上陷入睡眠，直到该线程解锁。

值得一说的是，信号量也不是完美的解决方案，当二元信号量多起来后，死锁也有极大的概率会发生，但由于我们的操作系统非常简单，不会发生如此复杂的情况，所以不考虑这些情况，详细内容请参考《操作系统之哲学原理》。

死锁

有大概如下几种情况会产生死锁：

忘记释放锁
单线程重复申请锁
多线程多锁申请

锁比开关中断好在哪？

前文提到，关中断是避免资源竞争最简单的方式，那为什么还需要锁呢？

从上图可见，当红色箭头进入临界区时，关闭中断，虽然这避免了资源竞争，但却令红色箭头在整个临界区内独占 CPU，其他任务得不到调度，从而导致系统效率下降。这是关中断的方式，下面来看看用锁是什么情况：

锁就不一样了，当红色箭头获得锁进入临界区后，绿色箭头仍然能够得到 CPU 调度，直到到达临界区才会被锁住而进入睡眠。因此，相比于开关中断，锁机制在任务调度上的效率更高 。

以上是笔者的个人想法，若读者还有其他想法，不妨在评论区提出。

本文就到这里，下节我们将实现锁机制。