死锁
- 资源
- 需要排他性使用的对象称为资源
- 硬件资源，打印机，蓝牙驱动器
- 一组信息，数据库中加锁的数据
- 可抢占资源
- 可以从拥有它的进程中抢占而不会产生任何副作用，存储器就是一类可抢占的资源
- 不可抢占资源
- 在不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来
- 某个资源是否可抢占取决干上下文环境。在一台标准的 PC 中，内存中的页面总是可以置换到磁盘中并置换回来，故内存是可抢占的。但是在一部不支持交换和页面调度的智能机上，仅通过将内存消耗大户交换出来是不能避免死锁的。
- 总的来说，死锁与不可抢占资源有关，有关可抢占资源的潜在死锁通常可以通过在进程之间重新分配资源而化解。
- 若请求时资源不可用，则请求进程被迫等待。某些进程会自动阻塞，有一些会发挥错误代码并在稍后重试。
- 资源获取
- 对于数据库系统中的记录这类资源，应该由用户进程来管理其使用. 一种允许用户管理资源的可能方法是为每一个资源配置一个信号量。
- 死锁简介
- 如果一个进在集合中的每个进在都在等持只能由该进在集合中的其他进程才能引发的事件，那么，该进在集合就是死锁的.
- 资源死锁的条件，同时满足以下四个条件
- 互斥条件.每个资源要么已经分配给了一个进程，要么就是可用的
- 占有和等待条件。已经得到了某个资源的进程可以再请求新的资源。
- 不可抢占条件。已经分配给一个进程的资源不能强制性地被抢占，它只能披占有它的进程显式地释放。
- 环路等待条件。死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。
- 死锁建模
- Holt 指出如何用有向图建立上述四个条件的模型。在有向图中有两类节点:用圆形表示的进程，用方形表示的资源。从资源节点到进程节点的有向边代表该资源已被请求、授权井被进程占用。由进程节点到资源节点的有向边表明当前进程正在请求该资源，并且该进程已被阻塞，处于等待该资源的状态。
- 有四种处理死锁的策眳
- 忽略该问题。也许如果你忽略它，它也会忽略你。
- 检测死锁井恢复。让死锁发生，检测它们是否发生，一旦发生死锁，采取行动解决问题。
- 仔细对资源进行分配，动态地避免死锁。
- 通过破坏引起死锁的四个必要条件之一，防止死锁的产生。
- 鸵鸟算法
- 死锁检测和死锁恢复
- 每种类型一个资源的死锁检测
- 每种类型多个资源的死锁检测
- 现在我们提供一种基于矩阵的算法来检测从 p1 到 pn 这 n 个进程中的死锁。
- 假设资源的类型数为 m, E1 代表资源类型 1, E2 代表资源类型 2, Ei 代表资源类型 i。E 是现有资源向量 (existing resource vector) ,
- 现在我们需要两个数组:C 代表当前分配矩阵 (current allocation matrix), R 代表请求矩阵 (request matrix)。 C 的第 i 行代表 Pi 当前所持有的每一种类型资源的资源数。所以，Cij 代表进程 i 所持有的资源 j 的数量。同理，Rij 代表 Pi 所需要的资源 j 的数量。
- 每个进程起初都是没有标记过的。算法开始会对进程做标记，进程被标记后就表明它们能够被执行，不会进入死锁。当算法结束时，任何没有标记的进程都是死锁进程。该算法假定了一个最坏悄形:所有的进程在退出以前都会不停地获取资源。
- 死锁检测算法如下:
- 寻找一个没有标记的进程 Pi, 对于它而言 R 矩阵的第 i 行向让小于或等于 A。
- 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转到第 1 步。
- 如果没有这样的进程，那么算法终止。
- 从死锁中恢复
- 利用抢占恢复：在不通知原进程的情况下，将某一资源从一个进程强行取走给另一个进程使用，接着又送回，这种做法是否可行主要取决于该资源本身的特性。用这种方法恢复通常比较困难或者说不太可能。若选择挂起某个进程，则在很大程度上取决干哪一个进程拥有比较容易收回的资源。
- 利用回滚恢复：周期性地对进程进行检查点检查，进程检查点检查查就是将进程的状态写入一个文件以备以后重启。该检查点中不仅包括存储映像，还包括了资源状态，即哪些资源分配给了该进程。一旦检测到死锁，就很容易发现需要哪些资源。为了进行恢复，要从一个较早的检查点上开始，这样拥有所需要资源的进程会回滚到一个时间点，在此时间点之前该进程获得了一些其他的资源。在该检查点后所做的所有工作都丢失。
- 通过杀死进程恢复：最直接也是最简单的解决死锁的方法是杀死一个或若干个进程。一种方法是杀掉环中的一个进程。如果走运的话，其他进程将可以继续。如果这样做行不通的话，就需要继续杀死别的进程直到打破死锁环。另一种方法是选一个环外的进程作为牺牲品以释放该进程的资源。在使用这种方法时，选择一个要被杀死的进程要特别小心，它应该正好持有环中某些进程所需的资源.
- 死锁避免
- 安全状态和不安全状态
- 单个资源的银行家算法
- 多个资源的银行家算法
- 死锁预防
- 破坏互斥条件
- 破坏占有并等待条件
- 规定所有进程在开始执行前请求所需的全部资源。如果所需的全部资源可用，那么就将它们分配给这个进程，千是该进程肯定能够运行结束。如果有一个或多个资沥正被使用，那么就不进行分配，进程等待。
- 破坏不可抢占条件
- 一些资源可以通过虚拟化的方式来避免发生这样的情况。假脱机打印机向磁盘输出，并且只允许打印机守护进程访问真正的物理打印机，这种方式可以消除涉及打印机的死锁
- 破坏环路等待条件
- 保证每一个进程在任何时刻只能占用一个资源，如果要请求另外一个资源. 它必须先释放第一个资源。
- 进程可以在任何时刻提出资源请求，但是所有诮求必须按照资源编号的顺序(升序)提出。
- 其他问题
- 两段式加锁: 在第一阶段，进程试图对所有所需的记录进行加锁，一次锁一个记录。如果第一阶段加锁成功，就开始第二阶段，完成更新然后释放锁。在第一阶段并没有做实际的工作。 如果在第一阶段某个进程需要的记录已经被加锁，那么该进程释放它所有加锁的记录，然后重新开始第一阶段。
- 通信死锁: 通信死锁不能通过对资源排序(因为没有)或者通过仔细地安排调度来避免(因为任何时刻的诮求都是不允许被延迟的)。幸运的是，另外一种技术通常可以用来中断通信死锁:超时。
- 活锁: 在某些情况下，当进程意识到它不能获取缓冲区路由器所需要的下一个锁时，就会尝试礼貌地释放已经获得的锁，然后等待 1ms, 再尝试一次。
- 饥饿: 动态运行的系统中，在任何时刻都可能请求资源。这就需要一些策略来决定在什么时候谁获得什么资源。虽然这个策略表面上很有道理，但依然有可能使一些进程永远得不到服务，虽然它们并不是死锁进程。饥饿可以通过先来先服务资源分配策略来避免。在这种机制下，等待最久的进程会是下一个被调度的进程。随着时间的推移，所有进程都会变成最“老”的，因而，最终能够获得资源而完成。
- 有关死锁的研究