241_死锁的概念(1)
# 2.4_1_死锁的概念(1)
各位同学大家好。在这个小节中我们会介绍死锁的相关基本概念，我们会用两个例子让大家比较直观的体会到什么是死锁现象。 另外我们会解释进程死锁，进程饥饿，还有死循环这几个比较容易让人混淆的概念，他们之间有什么联系和区别。之后我们会介绍死锁产生的4个必要条件，什么时候会发生死锁，发生死锁事之后应该做什么处理，或者说我们应该怎么避免死锁的发生，这就是这又是小节最后会提到的内容。那么我们会按照从上至下的顺序依次讲解。
# 什么是死锁
其实死锁这个概念在之前哲学家进餐问题当中就已经提到过，如果5个哲学家进程都并发的执行，那么他们有可能依次拿起自己左手边的筷子，但是之后当他们都尝试拿起右手边的筷子的时候，发现右边那只筷子已经被另一个哲学家就是自己右手边的哲学家所占领了，所以这种情况下就会发生这种循环等待的现象。每一个哲学家手里都持有一只他的左边哲学家想要的筷子，但是他同时又在等待他右边的哲学家手里的那只筷子，所以在这种情况下，所有的哲学家都是阻塞状态，没有一个哲学家进程可以顺利的往下推进，因此这种情况下就称为发生了所谓的死锁现象。
再来看另外一个例子，我记得之前在什么时候听过一首歌歌词是这样，什么我爱你，你爱他，他爱他，他爱我，这个世界每个人都爱别人，大概是这个样子，不一定准确，大家可以去搜一下，应该可以搜到。我们可以从资源占有的角度来分析一下它这个歌词描述的这段关系为什么看起来那么纠结
总共有4个人，我爱你，说明你拥有我的心。你爱他，说明他拥有你的心。他爱她，说明她拥有他的心，她又爱我，所以说明我有他的心。因此这4个人或者说这4个进程，他们每个进程都持有1种独特的临界资源。但是由于我爱你，所以其实我想要拥有的是你的心，而她爱我，所以我想拥有的是他的心，也就是所以我进程他是占有了她的心，同时在等待你的心。而他进程是占有了你的心，但是又在等待她的心，也就是我手里的资源是他想要的，而他手里的资源又是我想要的，这就发生了刚才咱们像哲学家问题一样的那种循环等待的现象。
而你和她其实也一样的，你占有我的心，但是在等待他的心，她占有他的心，但是又在等待我的心，所以这两个进程他们之间也存在这样的循环等待的关系。
因此这两组进程就都发生了所谓的死锁现象。所以其实所谓的死锁并不难理解，就是指在并发环境下各个进程，因为竞争资源而造成的一种互相等待对方手里资源的这种情况，导致了各个进程都阻塞，都无法向前推进，因为都在等待着对方先放下自己手里的资源，但是每一个进程都会持有当前的资源不放，因此这就是所谓的死锁现象。
如果发生了这种死锁现象的话，那么如果没有外力干涉或者说没有操作系统干涉的话，那么这些进程就都没办法顺利的向前推进了。
# 死锁、饥饿和死循环
接下来咱们再来看三个比较容易让人混淆的概念，死锁、饥饿和死循环。所谓的死锁刚才已经解释过，是指各个进程互相等待对方手里的资源，而导致所有的这些进程都阻塞，而无法向前推进的现象。
而饥饿这个概念咱们在之前处理机调度的时候提到过，是由于进程长期得不到想要的资源而无法向前推进的现象。比如说咱们之前介绍短进程优先算法的时候，如果说用短进程优先算法，那么系统中有源源不断的短程进程到来的话，长进程就会一直得不到处理机这种资源，所以就导致了进程饥饿的现象。
而死循环是指某种进程，在执行的过程中，因为遇到一些问题，所以一直跳不出某一个循环，比如说while循环或者for循环这样的现象。相信如果大家有编程经验的话，每个人应该都写过死循环。当然有时候死循环是因为我们自己程序逻辑的bug而导致的，有的时候就是程序员故意设计的，比如说之前咱们写过的那些pv操作的代码，其实就是故意设计成死循环的。但那么这儿所指的死循环，其实特指的是这种程序逻辑bug导致的死循环，导致了一个进程没有办法按照我们期待的那样顺利的往下推进。
这三个概念的共同点在于他们都是进程发生了某种异常的状况，而无法继续往下推进的这种现象。所以这三个概念其实比较容易在选择题当中放在一起对大家进行考察。那么除了进程都无法向前推进共同点之外，他们又有一些很明显的区别。死锁现象咱们刚才解释过，是各个进程循环等待对方手里拥有的那种资源而导致的，所以发生死锁的话肯定至少是有两个或者两个以上的进程同时发生死锁。因为如果只有一个进程的话，那么怎么循环等待对方手里的资源，所以由于死锁的进程是在等待某一种资源的分配。因此发生死锁的进程肯定是处于阻塞态的
而饥饿和死锁不同。在刚才的短进程优先算法这个分析过程中，我们也会发现，即使系统当中只有一个长进程，然后有别的源源不断的短进程到达，这个的长进程有可能是他自己处于饥饿的状态，因此如果说发生饥饿的话，可能是只有一个进程发生饥饿，而死锁的话肯定是两个或者两个以上的进程，同时死锁，发生饥饿的进程，有可能是长期得不到自己想要的某种资源，比如说IO设备，当然有可能是像上面这所提到的这样是长期得不到处理机的服务。所以发生饥饿这种现象的进程，它有可能是处于阻塞态的，也有可能是处于就绪态的。
另外处于死循环这种状态的进程有可能只有一个，并且死循环状态的进程，它是可以上处理机运行的，如果写过程序的话，大家应该也有这种体会，比如说自己写一个死循环，不断的输出hello world，那么你会发现屏幕上不断的会有hello word被打印出来，所以死循环的进程其实是可以上处理机运行的，因此处于这种状态的进程，它有可能是处于运行态的，而死锁和饥饿的进程，它们肯定不会是运行态。死锁和饥饿的问题一般来说是由于操作系统分配资源的这种策略不合理而导致的。比如说像刚才咱们提到的饥饿这种现象，就是由于操作系统分配处理机这种资源的策略不合理，所以导致了肠镜成饥饿。
而对于死循环这种现象来说，它是由写程序的那个人导致的，是由代码逻辑的错误导致的。所以死锁和饥饿应该是操作系统需要关心需要尝试解决的问题，而死循环应该是写程序的应用程序员来关心的问题。
所以在操作系统这门课中，大家会发现，有的地方会说怎么解决死锁，有的地方说怎么解决饥饿，但是他从来不说怎么解决死循环，因为解决死循环根本就不是操作系统应该来负责处理的问题，所以这就是死锁、饥饿、死循环这三个概念的联系和区别。
# 死锁产生的必要条件
其实死锁的发生是需要遵循一定的条件的，总共有4个条件，这些条件当中只要有任何一条不成立死锁就不会发生。
第一个条件是互斥条件，是指这些进程并发执行的进程，只有对必须互斥使用的资源进行争抢的时候才会导致死锁。比如说咱们之前提到的哲学家问题，筷子这种资源它就是一种只能互斥使用的资源，只要其中一个哲学家把筷子占有了之后，别的哲学家就暂时不可以使用这只筷子，所以这是互斥条件，但是像内存扬声器这样同时可以让多个进程使用的资源是不会导致死锁的，因为各个进程在申请使用这些资源的时候，并不用阻塞等待这种资源，所以当然就不会发生咱们之前提到的那种互相等待的现象，因此也必然不会发生死锁，所以一定要满足互斥条件才有可能发生死锁。
第二个条件是不可剥夺条件，是指各个进程在获得资源，这个资源没有使用完之前，是不能由其他进程强行抢夺的，只能由进程自己主动释放。比如说咱们之前提到的哲学家问题，每个哲学家自己手里拿了一只筷子之后，其他的哲学家是不能从自己手里抢走这只筷子的，如果说其他哲学家可以抢走自己想要的那只筷子的话，那么抢得筷子的抢得两只筷子的哲学家，肯定就可以顺利的吃饭，就不会出现所有的哲学家都被阻塞发生死锁的那种问题，因此也一定要满足不可剥夺条件，才有可能发生死锁。
第三个条件是请求和保持条件，还是以哲学家问题作为例子，每一个哲学家在保持了一个资源不放的同时，他还在请求另一个新的资源，而新的资源又恰好是被别的哲学家进程所持有的，所以他们满足了请求和保持的条件，因此发生了死锁，而如果这个条件不满足的话，死锁现象也是不会发生的。
第四个条件是循环等待条件，是指存在一种进程资源的循环等待链。咱们之前已经聊过，每一个哲学家都在等待自己右手边的哲学家放下资源，所以这就形成了一种资源的循环等待链。那么如果说没有这种循环等待的话，死锁也是不会发生的，但是这个地方需要注意的一个问题是在发生死锁的时候，一定是会有这种循环等待资源的现象的，但是发生了循环等待资源现象的时候，未必就一定发生了死锁。
比如说此时有一个神秘的第六人，第六个哲学家，他拥有一支筷子资源，这个筷子是可以让三号哲学家的右手来拿起使用的。所以3号哲学家右手没有筷子的时候，他其实既在等待4号哲学家放下这只筷子，同时他其实也可以等待神秘哲学家放下这只筷子，因为这只筷子也可以让三号的右手来使用。所以在这种情况下，虽然我们看起来它是有一个循环等待的这种关系的，但是只要哲学家他放下了这只筷子资源，那么这个筷子资源就可以被分配给三号哲学家，这个时候三号哲学家就可以顺利的开始吃饭，于是他就不需要再等待别的哲学家手里的资源了。
因此可以看到即使发生了循环等待资源的现象，但是如果还有别的进程持有一个同类型的可以替代的资源，那么死锁是不一定发生的，就像刚才这个例子一样，但是如果说一个系统当中每一类资源都只有一个，那么循环等待就是死锁的充分必要条件了，就像刚才没有哲学家那种时候一样，三号哲学家右手可以用的筷子其实只有一个，这类的资源只有一个，所以在发生了循环等待现象，同时又满足系统中每类资源只有一个条件的时候，循环等待就必然是会导致死锁了。
# 什么时候会发生死锁
那么什么时候会发生死锁？咱们书上给出了这样的三种情况，
- 对一种不可剥夺的系统资源的竞争的时候，有可能会引起死锁。
- 第二，进程推进顺序非法也会导致死锁问题。比如说两个并发的进程，p1和p2，他们分别申请并占有了r1和r2这两种资源，但是之后 p1又紧接着申请r2资源，而p2又紧接着申请r1这种资源，这种情况下就发生了死锁现象。但是如果说我们改变一种进程的推进顺序，比如说先由p1上处理机运行，那么p1一气呵成，先申请r1资源，再申请r2资源，那么这两个资源都同时归p1所占有，那么p1就可以顺利的往下执行下去。所以如果用我们刚才所说的这种方法来推进这些进程的话，那么p1进程是不会被阻塞的，只有p2会被阻塞，所以这种情况下就不会再发生死锁
- 那么第三种情况，当信号量使用不当的时候也会发生死锁现象，比如说咱们之前在讲生产者消费者问题的时候就提到过，如果说实现互斥的对mutex变量的p操作，在实现同步的p操作之前，那么就有可能会导致死锁，这个地方大家也趁着咱们提到再来回忆一下这个知识点
其实我们可以把互斥信号量和同步信号量也看作是一种抽象的系统资源。所以其实上面这么多东西，我们可以总结为一句话，就是说当对不可剥夺的资源的分配不合理的时候，就有可能会导致死锁。
# 死锁的处理策略
那么当死锁发生的时候，我们应该怎么做？或者说我们应该怎么避免死锁的发生呢？一般来说对于死锁问题的处理策略有这样三种，
- 第一种叫预防死锁，会想办法破坏刚才咱们聊到的4个死锁的必要条件当中的1个或者几个，这是预防死锁的策略
- 第二种叫做避免死锁，用某一种算法来检查，防止系统进入不安全的状态，咱们之后还会展开细聊。我们会介绍银行家算法，避免死锁的这种方案。
- 第三种死锁的检测和解除，前面这两种解决方案是不会引起死锁现象的。而第三种解决方案是允许死锁的发生，但是操作系统会要负责检查到底有没有死锁发生，如果此时发生了，那么就需要通过某种策略来解除死锁。
这三个方法也是咱们之后的小节会依次展开细聊的三种死锁处理的策略。这个地方先让大家形成一个框架，暂时不展开细聊。
# 小结
那么这个小节我们介绍了死锁相关的一些基本知识，包括什么是死锁，另外死锁和饥饿，死循环这几个比较容易混淆的概念，它们有什么区别。大家一定要着重体会，很容易作为选择题来作为考察。
之后我们又介绍了死锁产生的4个必要条件，其中循环等待条件的知识点是比较容易作为选择题的陷阱来考察的，循环等待未必导致死锁，而死锁一定是会有循环等待现象的。当然其他的这些条件也需要体会，并且通过课后的习题来进行进一步的巩固。
最后我们简单的提了一下死锁处理的三种策略，这三种策略会在之后的小结依次展开细聊，那么预防死锁是要破坏死锁产生的这4个必要条件，所以在之后学习预防死锁的过程当中，也会对这几个必要条件再重新的进行复习和巩固。
