[第三章]处理机调度与死锁

处理机调度

• 调度算法、调度时机、CPU调度过程

层次

高级调度

• 任务：决定把外存后备作业队列中的作业调入内存，为之创建进程，并将进程加入就绪队列

低级调度

• 任务：选择就绪进程或线程进入运行状态

• 高效、频繁使用

中级调度

• 目的：提高内存利用率和系统吞吐量

• 任务：决定把那些具备运行条件的挂起就绪进程调入内存并将其状态设置为就绪状态

调度队列模型

仅有进程调度的队列模型

高低两级调度的调度队列模型

• 大型系统中常设置多个阻塞队列，以应对多种事件

三级调度的调度队列模型

• 调出操作后，内存就绪变为外村就绪、内存阻塞变成外存阻塞；中级调度下外存就绪变成内存就绪

评价

引起进程调度的主要原因

• 时间片完

• 阻塞

• 运行完成

• 被抢占

调度方式

抢占式

• 时间片原则

• 优先权原则

• 短进程优先原则

非抢占式

• 优点：实现简单、开销小、适用于大多数批处理环境

• 缺点：不能满足紧急任务的要求，不适用实时系统

调度准则

• CPU使用率

• 吞吐量：单位时间完成的进程数量

• 周转时间：进程从提交到完成的时间
• 等待时间+运行时间

• 等待时间：在就绪队列中的等待时间

• 响应时间：从提交请求到产生第一响应的时间（从提交到获得CPU）

调度机制

• 排队器：事先将系统中所有就绪进程排成一个或多个队列，每当有一个进程变成就绪状态，便插入到相应的就绪队列

• 分派器：根据进程调度所选的进程，将就绪队列取出

• 上下文切换器
• 第一对上下文切换：保存当前进程上下文，装入分派程序的上下文
• 第二对上下文切换：移除分派程序的上下文，装入新选程序上下文

调度程序

• 运行→等待、进程终止：非抢占

• 运行→就绪、等待→就绪：抢占

常用调度算法

• 先来先服务：FCFS：非抢占式

• 最短作业优先算法：SJF
• 非抢占
• 平均等待时间应减去到达时间
• 抢占：最短剩余时间优先（SRTF）
• 平均等待时间要每一片减去到达时间再加和1
• 优点：对给定一组进程平均等待时间最小
• 缺点：堆场作业不利，未考虑紧迫程度，必须事先知道进程的长度

• 基于优先权的调度：HPF
• 非抢占式
• 抢占式：适用严格的实时系统
• 优先级根据优先数来决定
• 系统可以规定优先数最小优先级最高或反之
• 因素
• 进程类型
• 运行时间
• 作业的优先数
• 动态/固定优先数
• 缺点：饥饿（无穷阻塞） || 解决：老化：优先权随时间变化

• 时间片轮转调度算法：RR
• CPU时间分为若干个时间片
• 有时间片长就运行时间片长，没有就运行自己部分，然后下一个给另一个时间片
• 取时间片应略大于一次经典的交互所需时间

• 多级队列调度算法
• 就绪队列分成不同的独立队列
• 每个队列有自己的调度算法
• 队列之间必须有调度次序
• 固定优先权调度：存在饥饿现象 || 时间片调度

• 多级反馈队列调度：MFQ(Multilevel Feedback Queue)
• 抢占式
• 进程可以在不同的队列间移动，每个就绪队列有不同优先级，优先级越高，时间片越短
• 队列间按优先级运行
• 通常1~n-1队列FCFS→[如果能在时间片内完成，则可撤离系统。否则，调度程序将其转入第二队列的末尾等待调度]，第n队列RR
• 高优先级没有运行完，则降档到次优先级

作业调度算法性能评价指标

• 作业周转时间Ti = Ei - Si Ei运行结束时间 Si作业进入输入井时间

• T =

• 带权平均周转时间 ri是作业i实际执行时间长度
• Ti = ri + 作业等待时间

• 响应比（带权周转时间）：Ti/ri = 1+（作业等待时间/作业处理时间）

死锁

• 发生死锁的进程至少是两个都已占有资源、都等待资源的所有进程的子集

• 要运行完该进程的全部才会释放

• 443

资源问题

• 可重用资源：一次只能分配给一个进程，不允许多个进程共享，遵循：请求、使用、释放

• 可消耗性资源：由进程动态创建和消耗

• 可抢占性：进程可被其他进程或系统抢占CPU和主存区

• 不可抢占性资源：不可强行收回

死锁原因

• 进程都申请另一个进程而占有其他需要的资源

死锁必要条件

• 互斥（独占）条件
资源非共享，一段时间内只能被一个进程占用

• 不剥夺条件（不可抢占）
不能剥夺进程拥有的资源

• 部分分配条件（请求和保持）
进程在等待新资源时继续占有已分配资源

• 环路条件（循环等待）
存在进程循环连，每一个进程获得资源的同时被链中的下一个进程请求

应对死锁

• 允许死锁发生
• 不予理睬
• 监测解除

• 不允许死锁发生
• 预防死锁，破坏条件
• 避免死锁，合理分配资源
• 检测死锁
• 解除死锁

死锁预防

• 确定资源分配方法，保证不死锁

• 破坏死锁的四个中的三个必要条件之一（对互斥：资源共享所必须，不能改变）
• 请求和保持条件
• 系统要求所有进程要一次性申请在整个运行过程中所需的全部资源，若系统有足够资源则完全分配（资源预分配法）
• 简单安全
• 缺点：可能无法提出所需资源，降低系统利用率，用户要等到所有资源满足才能运行
• 不可抢占条件
• 一个已拥有资源的进程若提出要求不能立即满足，则释放已拥有的所有资源（监测死锁并释放资源）
• 复杂，代价大
• 循环等待条件
• 给所有资源分配唯一的号码，分配请求必须以序号上升的次序运行
• 优点：资源利用率和系统吞吐量明显改善
• 缺点：实际进程与资源顺序不一定一致，造成资源浪费

死锁避免

银行家算法

• 数据结构
• 可用资源Available m个，代表一类可利用资源的数目
• 最大数据需求量Max n*m矩阵，表示n个进程的每一个对m类资源的最大需求
• 分配矩阵 Allocation n*m矩阵 表示每个进程分配的资源数
• 需求矩阵Need n*m矩阵 每个进程还需要的数目

• 算法
• Request[i] ≤ Need[i]
• Request[i] ≤ Available
• →Available = Available -Request[i];
• Allocation[i] = Allocation[i] + Request{i]
• Need[i] = Need[i] - Request[i];

• 安全性算法
• 安全性检查数据结构
• Work:ARRAY[0…m-1] of integer;系统中存在的资源数目
• Finish:ARRAY[]0…n-1] of Boolean;进程
1. Work = Available Finish[i] = false;
2. Finish[i] = false; Need[i] ≤ Work;
3. Work = Work - Need[i];
Allocation[i] = Allocation[i] + Need[i]
Work = Work + Allocation[i]
Finish[i] = ture;
4. 若所有i Finish[i] = ture,则处于安全状态

死锁检测和解除

死锁解除

1. 重新启动
2. 撤销进程
3. 剥夺资源
4. 进程回退
资源分配图
有向图描述死锁G=（V,E)

• 资源,方框

• 资源实例,方框中的圆点

• 进程，圆圈

• 分配边：资源实例到进程的一条有向边

• 申请边：进程到资源的一条有向边

• 简化：把只有分配边的分配边去掉，资源给等待进程

课后题