本文首发于稀土掘金。该平台的作者 逐光而行 也是本人。
本文为个人阅读《现代操作系统》相关章节后的笔记。
preview
为什么会有锁？
操作系统授权一个进程排他性地访问某种资源。
什么是死锁现象？
以a,b为例（数量上可能不止a,b，所指对象上a,b可以是进程、机器等），a,b互相占用对方需要的资源并申请对方占用的资源，互不相让，导致双方进度都停滞。
如何判断一个进程集合体是否是死锁级别的？
当其中的每个进程都等待只能由其他进程才能触发的事件（比如哲学家就餐问题）
（一些体悟）
- 死锁研究大约在1980年已完成，属于40年没有大变动的知识点，一定要重点掌握！
- 我记得数据库中的死锁解决方案其实和操作系统的不太相同
资源
- 可抢占资源
即可以被抢的，暂时抢了过来也没影响的，如存储器资源。
（因为存储器中原来存的信息可以被置换到磁盘，之后再换回来，信息不存在丢失问题）
- 不可抢占资源
比如光盘刻录机，如果抢了过来，原来划的东西就丢失了。
死锁与不可抢占资源有关
请求资源的过程很依赖于系统本身的设计。有的提供request系统调用，允许进程进行资源请求；有的只把资源当成特殊文件，上一个open了的进程不close，别的进程就无法使用。
发生资源死锁的必要条件
- 资源的状态互斥，只有可用和进程正在用。
- 进程 被允许 同时占有多个资源。
- 有的资源是非抢占式
- 环路等待，如a等b，b也在等a
处理死锁的策略
忽略问题————鸵鸟算法
这个是相对而言的，如果处理死锁的代价比不处理大，那肯定是不处理好。
检测死锁并恢复
一种类型对应一个资源的
一种可能的算法：（我阅读文字后的理解）
思路：dfs+回溯
对于每一个结点，将其作为起始点执行如下步骤：
- 每次用一个set存储遍历过的结点，如果contains当前结点，说明存在环，算法结束；
- 每次用一个set存取经过的结点的有向边，如果contains当前的，随机选取从该结点出发的还没有放入set中的其中一条有向边放入set，并顺着它找到新结点，返回1；如果没有contains，且当前结点是起始节点，说明无环，算法结束，否则说明接下来是死胡同，需要移除当前结点，并回溯至上一个结点（相当于在上一个结点中重选另一条路）
一种类型对应多个资源的
- 理论基础：现有资源=当前已分配资源+可用资源
- 数学表示：E表示现有资源向量（exist），A表示可用资源向量（available）,C[]表示可分配资源矩阵
- 该算法的本质就是基于向量的比较。
- 算法具体实现：
进程初始为未标记，算法会对能够被执行、不发生死锁的进程进行标记，算法结束后，仍未被标记的进程即为死锁进程。
- 算法关键点：首先找出哪一个进程的资源请求可被满足
上述两小点提到的是如何检测，问题关键还在于何时检测。
何时检测？
可选方案:
- 每当有资源请求时即检测
缺点：占用昂贵的CPU时间
- 每隔k分钟检测一次/达到CPU使用率阈值时检测
理论基础：当发生死锁时，没有多少进程可运行，所以CPU使用率会很低
（这个应该是从宏观看的，局部的小锁不适用）
死锁恢复
- 抢占
比如对大型主机上的批处理操作系统进行人工干预
- 回滚
回滚到资源还没有被恶性占用前的状态
- 杀死进程
最好选择可以从头开始运行但不会带来副作用的进程去杀。
比如像数据库的计数类进程就不要乱杀。
避免死锁的算法和策略————银行家算法
安全状态与非安全状态
- 安全状态：没有死锁，且即使所有进程突然 最大限量请求资源，也存在顶得住的调度方案。
- 安全与非安全的区别：在上述条件下非安全状态不能保证所有进程都能完成。（当然，非安全状态不一定会导致死锁）
单个资源的银行家算法
算法概述：把操作系统比作银行家，把进程比作客户。对于每一个客户的贷款（资源请求），银行家检查其是否能达到安全状态，若能，则批准，不能，则推迟。
- 如何判断是否安全？
通俗来说就是检查假设把钱给了当前用户之后，剩余的钱是否能支撑当其他所有用户都突然最大限度提款。
多个资源的银行家算法
类似
算法背景及意义
- 作者及发表时间：Dijkstra 1965
- 局限：算法本体实用性不强，因为很难事先确定某个进程所需资源的最大值，且进程数往往不固定。
- 意义：其思想的变体得到应用，如当缓冲区利用率达到70%以上时，网络会实现自动节流。
预防死锁
从本质上说，不可能完全避免死锁，就像误差没办法避免一样。但是在单个案例中，如果能破坏前面所提的死锁产生的必要条件中的其中一个，死锁将不会发生。
（回顾：
发生资源死锁的必要条件
- 资源的状态互斥，只有可用和进程正在用。
如打印机可以采用假脱机技术，真正请求打印机资源的只有打印机守护进程，而守护进程不会有其他状态。
- 进程 被允许 同时占有多个资源。
破坏这种 占有并等待 的条件。
如：
- 如果预先知道进程需要多少资源，则可以使用银行家算法；
- 有些大型批处理系统就要求用户提交作业时列出所需资源，系统再予以分配；
或者稍微再变换一点:
当进程申请新资源时，必须先释放当前已有的所有资源，之后再一次性连旧带新返还。
- 有的资源是非抢占式
可以通过虚拟化解决一部分问题，不过要注意，不是所有东西都可以虚拟化，比如数据库和操作系统中的表。
- 环路等待，如a等b，b也在等a
消除该现象的方法：
- 跟上面变换一点的方法类似，再加一个限制条件：某一时刻一个进程只能占用一个资源。
- 把所有资源统一编号，每个资源不允许请求之前已经被请求（或许还没得到）的资源（编号比自己小的），但是可以请求比自己后请求的资源。
我个人的理解就是类似于上下级关系，每个人不能顶撞领导，但是相对下属而言有特权，只要这套等级规则在这里并且不被违反，公司就不会乱。
）
其他的锁
在特定场景通用的锁————数据库的两阶段加锁
- 概述：第一阶段加锁只是形式，确定能够锁定这么多资源并且不受干扰，之后会释放资源并进行第二次加锁，再做实际修改工作。如果第一次锁的已经被加锁，就释放其所有加锁记录，并重新开始。
- 问题：如果在上述的后一种情况中没有释放锁，可能会导致死锁。
- 局限：在诸如实时系统和进程控制系统中，半途中断并从头开始是不可接受的。
前面讲的都是资源锁，接下来讲的是通信锁。这是涉及到计算机网络相关的概念。
资源锁是竞争性同步问题，通信锁是协同同步问题。
通信死锁
比如如果a发消息给b，b收到后回消息，但是消息中途丢失，a还在一直等b回消息，b也在等a的新答复。
不过这并不是什么大问题？因为计网一开始就告诉我们有超时机制(timeout则重新发送）、还有返回信息的不同性（信息正确接收返回新信息，否则返回原信息）等
Q:通信或网络系统上只会发生通信死锁吗？
A:不是的，有资源实体的地方就会有资源死锁的可能。
比如packet绕了一圈实际上又发给最初的路由器的话，这些packet不会移动。
活锁
举哲学家就餐的例子，死锁类似于大家都不松开餐具；活锁类似于大家每次都同时松开餐具并在下一秒尝试重新拿起两边的餐具，虽然在活动，但是做的无用功。
饥饿
操作系统中的最小作业优先调度算法容易引起大作业的饥饿现象，这种情况可以通过使用先来先服务调度算法避免。
一点杂碎
《现代操作系统》一书的作者认为，死锁问题是一个经典图论问题，出了很多论文，但后来的很多算法很古怪且不贴合现实。
- 2011年有人提出要在应用程序中检测死锁并保存其特征，从而避免日后遇到相同死锁。
- 有人说采用并发控制来避免死锁。
- 2012年有人提出一种能动态地减少没有入边和出边的锁的依赖关系的方案。
以上是比较靠谱的。
- 很多分布式锁的研究其实只是在水论文。（作者认为的哈，不是我说的，不喜勿喷）
