CH3 处理机调度与死锁.ppt

(1) 竞争资源引起进程死锁 – cont. 3) 竞争临时性资源 临时性资源： 由一进程产生，被另一进程使用一短暂时间后便无用的资源 如：S1、S2、S3为临时性资源， P1、P2、P3为进程 * */97 不发生死锁 P1：…Release(S1); Request(S3); … P2：…Release(S2); Request(S1); … P3：…Release(S3); Request(S2); … 执行顺序1： 发生死锁 P1：… Request(S3); Release(S1);… P2：… Request(S1); Release(S2);… P3：… Request(S2); Release(S3);… 执行顺序1： (2) 进程推进顺序非法 * */97 D：不安全区域 死锁的发生必须具备下列4个条件： (1) 互斥条件 进程对所分配的资源进行排它性使用 (2) 请求和保持条件 进程已经保持了至少1个资源，但又申请其它资源 (3) 不剥夺条件 进程一旦获得资源，在未用完前不能被剥夺 (4) 环路等待条件 资源的环形链，即进程集合{P0, P1, P2, …, Pn}中P1正等待P2占用的资源，……，Pn正等待P0占用的资源。 2. 死锁产生的必要条件 * */97 四种基本方法： (1) 预防死锁 事先设置某些限制条件，破坏产生死锁的必要条件 限制条件太严格，可能会导致资源利用率及系统吞吐量降低 (2) 避免死锁 在资源的动态分配过程中，用某种方法防止系统进入不安全状态 限制条件较弱，对资源利用率及系统吞吐量影响不大 (3) 检测死锁 允许发生死锁，但能通过某种机制检测出死锁的发生，并确定与死锁有关的进程和资源 (4) 解除死锁 通过撤销或挂起一些进程，将资源释放，将进程从死锁状态解脱出来 3. 处理死锁的基本方法 * */97 3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 * */97 条件1：由设备的固有特性决定，无法改变 破坏四个必要条件中的2、3、4个条件： (1) 摒弃“请求和保持”条件 (2) 摒弃“不剥夺”条件 (3) 摒弃“环路等待”条件 预防死锁 * */97 (1) 摒弃“请求和保持”条件 进程在运行之前，一次性申请所需的所有资源 优点： 简单、安全、易于实现 缺点： 降低了资源利用率 进程延迟执行 * */97 (2) 摒弃“不剥夺”条件 当一个已经保持了某些资源的进程，在申请其它资源而得不到满足时，须释放其已保持的所有资源 特点： 实现较复杂、代价大 被迫释放资源而使前段工作失效 如：打印机 延长了进程周转时间、降低了系统吞吐量 反复申请和释放资源，导致进程执行被无限地推迟 * */97 (3) 摒弃“环路等待”条件 系统将所有资源按类型进行线性排队，并赋予不同序号 所有资源请求必须按照资源序号顺序提出 这样，总有一个进程占据较高序号的资源，则其继续申请的资源必然是空闲的，进程可以一直向前执行 问题： 1) 序号相对稳定，限制了新类型设备的添加 2) 当进程使用资源的顺序与系统规定顺序不同时，造成资源浪费 3) 限制用户简单、自主的编程 * */97 在避免死锁的方法中，在进行资源分配之前，应先计算此次资源分配的安全性。 把系统分为安全状态和不安全状态。 安全状态 指系统能按某种进程顺序(P1, P2, …，Pn)（称P1, P2, …, Pn序列为安全序列），来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。 若系统无法找到这样一个安全序列，则称系统处于不安全状态。 系统安全状态 * */97 安全状态的例子 假定系统中有三个进程P1、 P2和P3，共有12台磁带机。 T0时刻的状态如下表： T0时刻的系统是安全的 存在着一个安全序列P2，P1，P3 由安全状态向不安全状态的转换 在T0时刻以后，P3又请求1台磁带机 * */97 进 程 最大需求 已分配 可 用 P1 P2 P3 10 4 9 5 2 2 3 Dijkstra提出，可用于银行系统现金贷款 数据结构： (1) 可利用资源向量Available 含有m个元素的数组，每一个元素代表一类可利用的资源数目。 初始值是系统中所配置的该类全部可用资源的数目。 Available[j] = K，表示系统中现有Rj类资源K个。 (2) 最大需求矩阵Max n×m矩阵，表示n个进程中的每一进程对m类资源的最大需求。 如果Max[i, j] = K，表示进程i需要Rj类资源的最大数目为K。 避