操作系统第3章处理机调度与死锁剖析.ppt

3.1　处理机调度的层次和调度算法的目标 高级调度（也称作业调度、长程调度） 功能 选择外存上处于后备队列中的一个或几个作业调入内存，并为它们创建进程，分配必要的资源，然后，再将新创建的进程排在就绪队列，准备执行。 使用系统 批处理系统 分时系统和实时系统不需要 执行频率 分钟、小时或天 3.1　处理机调度的层次和调度算法的目标 低级调度（也称进程调度、短程调度） 功能 从就绪队列中选择一个进程，然后，由分派程序将处理机分配给该进程。 使用系统 各种系统均需要 执行频率 毫秒 3.1　处理机调度的层次和调度算法的目标 处理机调度算法的目标 共同目标 资源利用率 公平性 平衡性 策略强制执行 3.1　处理机调度的层次和调度算法的目标 批处理系统的目标 平均周转时间短 作业周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔，它包括四部分时间：作业在外存后备队列上等待作业调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU上执行的时间，以及进程等待I/O操作完成的时间 平均周转时间可描述为 平均带权周转时间则可描述为 3.1　处理机调度的层次和调度算法的目标 系统吞吐量高 处理机利用率高 分时系统的目标 响应时间快 均衡性 实时系统的目标 截止时间的保证 可预测性 3.3　进程调度 多队列调度算法 按性质和类型将就绪队列分为若干子队列，每个就绪进程固定地分属于一个子队列，每个队列有自己的调度算法 各队列间的调度方式或采用固定优先权抢占调度，或为各队列分配一定比例的CPU时间 3.4　实时调度 优先级倒置（priority inversion problem） 优先级倒置的形成 例 3.4　实时调度 优先级倒置的解决方法 简单：P3进入临界区后，其处理机不允许被抢占 实用：动态优先级继承方法 3.3　进程调度 例：时间片=2 进程名 到达时间 服务时间 A 0 4 B 0 5 C 0 2 D 0 4 开始时间 完成时间 周转时间 带权周转时间 0 10 10 2.5 2 15 15 3 4 6 6 3 6 14 14 3.5 A B C D A B D B 0 2 4 6 8 10 12 14 15 3.3　进程调度 优先级调度算法 非抢占式或抢占式均可 选择具有最高优先级的就绪进程 优先级（优先权、优先数） 利用某一范围内的一个整数来表示 不同系统的具体用法各异 确定进程优先权的依据 进程类型 进程对资源的需求 用户要求 3.3　进程调度 优先级的类型 静态优先级 创建进程时确定，在进程的整个运行期间保持不变 简单易行，系统开销小，但不够精确 仅在要求不高的系统中才使用 动态优先级 创建进程时确定初值，运行期间基于某种原则动态改变 灵活，调度性能好，但系统开销大 3.3　进程调度 例 进程名 到达时间 服务时间 优先级 A 0 10 3 B 0 1 5 C 0 5 2 D 5 3 4 B A D C 0 1 11 14