计算机操作系统——锁的进化

作者 | 陌无崖

转载请联系授权

导语

相信大家都知道金鱼是不知道饥饿的，如果有食物吃，金鱼就会不停的填饱肚子，哪怕被撑死。在计算机中锁的进化可以用金鱼生存的例子来引入。

金鱼生存

左一和右尔共同养了一条金鱼，该金鱼每天仅仅喂食一次，如果多喂了一次，鱼会被撑死，如果没有喂金鱼，则金鱼会饿死。那么左一和右尔必须约定好各自如何喂鱼。

当然左一和右尔都是喂鱼高手，仅仅查看鱼的状态，就知道今天鱼是否被喂，因此他们两个约定在喂鱼之前，必须先检查鱼的状态。当然这样的做法在现实生活中可以实行，但是如果切换到计算机操作系统时，可能就会出错了。

在操作系统中左一和右尔相当于两个线程，而金鱼相当于一个共享资源，因此这个问题就是两个或多个线程操作同一资源的问题。

在计算机中，线程是可以任意穿插的，因此对于金鱼问题，当线程切换到左一，左一检查鱼的状态时，发现鱼没有被喂，此时线程切换到右尔，右尔也检查鱼的状态，此时鱼没有被喂，因此成功喂了鱼，这时线程又切换到左一，左一现在的状态就是喂鱼，将继续执行这个指令，因此也喂了鱼，结果，鱼被撑死。

防止竞争

看来上述的方案不完善，导致的原因是什么呢？左一和右尔操作了同一个对象，即检查了鱼的状态。争相执行引起的结果。即在计算机中两个或多个线程同时执行了一段代码或访问了同一个资源，资源被称为临界区。

那么如何防止竞争呢？也就是说任何时候只能有一个线程在临界区。那么左一和右尔想了一个办法，每个人在喂鱼之前先留下字条，告诉对方自己将要检查鱼的状态。这样就可以了吗？仔细想想其实这样的作法并没有从根本上解决问题，仅仅减少了鱼被撑死的概率。为什么？我们可以看如下的步骤：

• 左一检查是否有字条，发现没有字条
• 线程切换
• 右尔检查，没有字条，放了字条
• 线程切换
• 左一放了字条

导致的问题显而易见，最终左一和右尔都放了字条，鱼还是会被撑死。因此这样的作法并没有完成互斥。

互斥改进

左一和右尔仔细分析了结果，发现导致的以上结果的原因是检查字条和留字条之间发生了时间的间隙，那么可不可以杜绝这样的问题呢？很快他们又想到了办法，先留字条，后检查有没有对方的字条，左一和右尔非常开心，因为这样做了之后，无论线程如何切换，都会出现有过一张字条。

但是又出现了问题，金鱼似乎没有被撑死，但是被饿死了。发生了什么？

• 左一留下字条
• 线程切换，右尔留下字条
• 左一检查字条，发现已经有了一张，线程切换
• 右尔发现也有了字条，线程切换
• 左一此时移除字条，线程切换
• 右尔此时移除字条
• 鱼被饿死

这样的作法，导致互斥过了头，因此这种方案是不行的，但至少相对于之前的方法，进步了不少，对于计算机来说，饿死总比撑死好。

等待

左一和右尔又仔细分析了原因，分析出，原来当他们放下字条后就离开了，那么不离开就可以了，当留下字条后，等待确认鱼是否被喂，不仅仅留下字条就离开。看起来这样的方法是可以的，但是在计算机中导致了什么问题呢？就是等待是一种资源的浪费，而且可能导致优先级倒挂，如果右尔先启动，留下字条，这时左一启动，如果左一的优先级高，左一在处于等待的过程中，右尔无法获得cpu的调度，因此出现循环等待。

升级

左一和右尔想了很久，似乎哪个方案都会出现问题。这时一位长者出现告诉他们，你们的方法都太局限于鱼身上了？左一和右尔突然一激灵，原来可以把保护鱼升级到保护放鱼的房间。那么如何防止两个人同时进入一个房间呢？很快他们想到了人类生活中的锁的原理。当他们进去之后，将房间上锁，这样其他的线程就无法进入了。但是仍然会有等待，那么如何解决呢？他们又想到了字条，当获得锁之后，留下一个字条，然后把锁释放，那么等待的时间就换成了留字条的时间。这样就不会导致一个线程执行速度慢，导致其他线程出现一直等待的情况。

于是左一和右尔每天开心的喂着鱼，虽然还会有等待的时间，但是这个等待时间是可以容忍的。

本文参考书籍《计算机操作系统之哲学原理》