操作系统03 CPU scheduling and dead lock.pptVIP

* 3. 死锁检测流程 Work=Available 找进程Li:Requesti≤Work 其资源图能否简化 否 有死锁，结束 是 释放资源 Work=Work+Allocationi L=Li∪L 还有进程吗 否 无死锁，结束 是 * 3.7.2 死锁的解除 (1) 剥夺资源 (2) 撤消进程 * 2. 成组调度(Gang Scheduling)方式 优点： 相互合作型进程或线程，能并行执行，有效减少线程（进程）阻塞的发生，从而减少线程切换，改善系统性能 依次调度一组线程，显著减少调度频率，减小了调度开销 * 3. 专用处理器分配(Dedicated Processor Assigement)方式 在一个应用程序的执行期间，专门为该程序分配一组处理器，每一个线程一个处理器。这组处理器仅供该应用程序专用，直至该应用程序完成 在同时加工的应用程序中，其线程数的总和，不应超过系统中处理机的数目 * 3.5 产生死锁的原因和必要条件 死锁：多个进程在运行过程中因争夺资源而造成的一种僵局 * 3.5.1 产生死锁的原因 1. 竞争资源引起进程死锁 (1) 可剥夺和非剥夺性资源 (2) 竞争非剥夺性资源 (3) 竞争临时性资源 * 竞争非剥夺性资源 1. 竞争资源引起进程死锁 * 1. 竞争资源引起进程死锁 竞争临时性资源 * 2. 进程推进顺序不当引起死锁 1) 进程推进顺序合法 2) 进程推进顺序非法 * 3.5.2 产生死锁的必要条件 (1) 互斥条件 (2) 请求和保持条件 (3) 不剥夺条件 (4) 环路等待条件 * 3.5.3 处理死锁的基本方法 (1) 预防死锁。 (2) 避免死锁。 (3) 检测死锁。 (4) 解除死锁。 * 3.6 预防死锁的方法 3.6.1 预防死锁 (1) 摒弃“请求和保持”条件 资源分配方案：要么分配进程所需的所有资源，要么不分配资源 优点：简单、易于实现、安全 缺点：资源严重浪费、进程延迟执行 * 3.6.1 预防死锁 (2) 摒弃“不剥夺”条件 资源分配方案：需要时才请求资源，一旦不能获得需要的资源，则释放所有已保持的资源 缺点：实现复杂、代价大 延长了进程的周转时间 增加了系统开销，降低了系统吞吐量 * 3.6.1 预防死锁 3. 摒弃“环路等待”条件 将所有资源按类型进行线性排队，并赋予不同序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出。 缺点：各类资源所分配的序号需相对稳定，从而限制了新类型设备的增加 进程使用资源的顺序可能与系统规定的顺序不同 限制了用户简单、自主的编程 * 3.6.2 系统安全状态 1. 安全状态 所谓安全状态，是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 避免死锁的实质：在进行资源分配时，如何使系统不进入不安全状态。 * 系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： 进 程 最 大 需 求 已 分 配 可 用 P1 P2 P3 10 4 9 5 2 2 3 2. 安全状态之例 *  如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。 3. 由安全状态向不安全状态的转换 * 3.6.3 利用银行家算法避免死锁 1. 银行家算法中的数据结构 (1) 可利用资源向量Available 这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available［j］=K，则表示系统中现有Rj类资源K个。 * (2) 最大需求矩阵Max 这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max［i,j］=K，则表示进程i需要Rj类资源的最大数目为K。 1. 银行家算法中的数据结构 * (3) 分配矩阵Allocation 这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进