四川大学操作系统原理、操作系统课件 死锁.ppt

死锁知识铺垫-基本概念 指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。 即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。 死锁知识铺垫-举例1 死锁知识铺垫-举例2 可分配空间为200K。 当两个进程都执行第二次空间请求时，发生死锁。 死锁知识铺垫-有关结论 参与死锁的进程最少是两个 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。 死锁知识铺垫 竞争系统资源 进程的推进顺序不当 死锁产生原因：①竞争系统资源 若系统中只有一台打印机R1和一台读卡机R2，可供进程P1和P2共享。若形成环路，这样会产生死锁。 死锁产生原因： ①竞争系统资源 死锁产生原因： ②推进顺序不当 死锁产生原因： ②推进顺序不当 死锁知识铺垫 互斥条件（资源独占） 请求和保持条件（部分分配，占有申请） 不剥夺条件（不可强占） 环路等待条件 死锁知识铺垫 预防死锁：破坏必要条件 避免死锁：银行家算法、安全性算法 检测死锁：资源分配图、死锁定理 解除死锁：以最小代价恢复系统 预防死锁的方法 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。 资源一次性分配--破坏请求和保持条件。 可剥夺资源--即当某进程新的资源未满足时，释放已占有的资源，破坏不可剥夺条件。 资源有序分配法--系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反，破坏环路等待条件。 1.死锁避免 死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。 预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意得系统性能来避免死锁。 1.死锁避免 由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。 其中最具有代表性的避免死锁算法是 银行家算法。 2.安全状态与不安全状态 安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。 安全序列 一个进程序列{P1，…，Pn}是安全的，如果对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和，系统处于安全状态。 安全状态一定是没有死锁发生的 若系统不存在这样一个序列，则称系统处于不安全状态。 ①安全状态的例子 ②安全状态到不安全状态的转换 如果不按照安全序分配资源，则系统可能会由安全状态进入不安全状态。 例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。 3.银行家算法-数据结构 Available：可利用资源向量 这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目； 其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变； 如果Available［j］=K，则表示系统中现有Rj类资源K个。 3.银行家算法-数据结构 Max：最大需求矩阵 这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求； 如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。 3.银行家算法-数据结构 Allocation：分配矩阵 这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数； 如果Allocation［i,j］=K，则表示进程i当前已分得Rj类资源的数目为K。 3.银行家算法-数据结构 Need：需求矩阵 这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数； 如果Need［i,j］=K，则表示进程i还需要Rj类资源K个，方能完成其任务； Need［i,j］=Max［i,j］-Allocation［i,j］ 3.银行家算法-数据结构 Ava