进程调度采用两种方式： ①非抢占方式： • 一旦分配处理机，进程就一直执行，直至完成或
发生某事件而被阻塞，不允许其它进程抢占处理 机。
• 优点：简单、系统开销小，适合大多数批处理系统 • 缺点：无法满足紧急任务的需要，不适合实时系统
②抢占方式： • 允许调度程序根据某原则，暂停正在执行的进 程，将处理机重新分配。 • 抢占原则：优先权原则 、短作业(进程)优先原 则、时间片原则
包括四部分：
等待作业调度时间(高级调度) 等待进程调度时间(低级调度) 执行时间 进程等待I/O操作完成时间
平均周转时间： t
1 n
n
ti
i 1
ti = tci-tsi
ti: 作业周转时间，tci：作业完成时间，tsi: 作业提 交（到达）时间
带权周转时间：
wi
ti tr
tr: 作业实际运行时间
先来先服务 短作业（进程）优先 高优先权先调度 时间片轮转 多级反馈队列
1、 先来先服务（FCFS）
可用于作业调度和进程调度
进程 到达 服务 开始执 完成 周转 带权周 名 时间 时间 行时间 时间 时间 转时间
A0 1
0
11
1
B 1 100 1 101 100 1
C 2 1 101 102 100 100
3、中级调度（中程调度）
目的：为了缓解内存紧张问题，将那些暂时不能 运行的进程调到外存上去等待。
当进程运行条件具备、且内存又空闲时，中级调 度程序决定将外存上的哪些进程重新调入内存。
进程状态：Ready <－>Ready suspend, Blocked <－>Blocked suspend
第三章 处理机调度与死锁
3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度(*) 3.4 产生死锁的原因和必要条件 3.5 死锁问题的解决方法
外存
提交 收容
就绪
阻塞
中
级
调
度
就绪
阻塞
内存
执行
完成
低级调度
高级调度
3.1 处理机调度的基本概念
高/中/低级调度 调度队列模型 调度方式和算法的选择准则
截止时间保证——评价实时系统 优先权准则——三种系统中皆适用 公平性原则—— 分时系统
面向系统的准则
系统吞吐量高——评价批处理系统 处理机利用率好——针对大中型系统 各类资源的平衡利用——对大中型系统
周转时间 (通常作为评价批处理系统的性能、 选择作业调度方式与算法的重要准则之一)： 是指从作业被提交系统开始，到作业完成为 止的这段时间间隔。
等待事件n
具有高、低两级调度的调度队列模型
作业 调度
后备队列
中级 调度
时间片完
就绪队列
进程调度
进程完成
CPU
挂起
挂起就绪队列
事件出现
事件发生
挂起阻塞队列 阻塞队列
挂起 等待事件
具有高、低、中三级调度的调度队列模型
3.1.3 调度方式和算法的选择准则
面向用户的准则 周转时间短——评价批处理系统 响应时间快——评价实时，分时系统
3.1.1 处理机调度的层次
1、高级调度（作业调度 / 长程调度 / 接纳调度）
多用于批处理系统，决定外存上处于后备队列中 的哪些作业调入内存。
每次调度时要考虑：
(1)接纳多少作业：取决于多道程序度 (2)接纳哪些作业：取决于调度算法
系统规模 运行速度
作业调度运行频率低，几分钟一次
2、低级调度（进程调度/ 短程调度） 用来决定就绪队列中哪个进程应获得处理机，然后再 由分派程序(Dispatcher)执行处理机分配操作。 进程状态：Ready <－>Running 引起进程调度的原因有： 进程正常终止或异常终止 正在执行的进程因某种原因而阻塞（I/O请求） 分时系统中时间片用尽 当有一个优先级更高的进程就绪（可抢占式） 在进程通信中，执行中的进程执行了某种原语操作。 如：wait/signal操作、Block原语、wakeup原语等 运行频率高，几十毫秒一次，算法不能太复杂，以免 占用太多的CPU时间。
平均带权周转时间：
w
1 n
n i 1
wi
响应时间(用来评价分时系统的性能，选择分时 系统中进程调度算法的重要准侧之一)：
从用户通过键盘提交一个请求开始直至系统首次 产生响应为止的时间。
响应时间包括三部分时间：从键盘输入的请求信 息传送到处理机的时间、处理时间、响应信息回 送终端的时间。
3.2 调度算法
带权周转时间 1 2.67 3.2 1.5 2.25 2.1
3、高优先权优先调度算法（HPF）
作业调度：从后备队列中选择若干个优先权最高的作业装入内存。
进程调度：把处理机分配给就绪队列中优先权最高的进程
非抢占式优先权算法：
一旦分配处理机给优先权最高的进程，进程便一直执行直至 完成，或发生某事件而被阻塞。
运行频率介于高级调度和低级调度之间。
3.1.2 调度队列模型
交互用户
时间片完
就绪队列
进程调度
进程完成
CPU
事
件 发 生
阻塞队列
等待事件
仅具有进程调度的调度队列模型
作业 调度
后备队列
时间片完
就绪队列
进程调度
进程完成
CPU
事件1发生
阻ห้องสมุดไป่ตู้队列
等待事件1
事件2发生
阻塞队列 ……
等待事件2
事件n发生
阻塞队列
作 调业
度情 算况 法
进程名
到达时间 服务时间 完成时间
AB
C
D
E
平 均
01 2 3 4 43 5 2 4 4 7 12 14 18
周转时间 4 6 10 11 14 9 FCFS
带权周转时间 1 2 2 5.5 3.5 2.8
完成时间 4 9 18 6 13
周转时间 4 8 16 3 9 8 SJF
短进程优先（SPF）
从就绪队列中选出估计运行时间最短的进程，将处理机分配 给它，使它立即执行。
直到运行完成，或发生某事件而被阻塞，进程才会让出处理 机——非抢占式。
优点：
有效地降低了作业的平均等待时间，提高系统的吞吐量。
缺点：
对长作业不利，有可能长期不被调度。 完全没考虑作业的紧迫程度（某些特殊的）。 用户做出的估计时间带有很大的主观性。
D 3 100 102 202 199 1.99 周优有转缺利时点 于间： 长实作业现（简=进单完程成）时，间不–利到于达短时作间业（进程）。 带有权利周于转CP时U间繁忙=型周作转业时，间不/利服于务I（/O运繁行忙）型时作间业。
2、短作业 / 进程优先（SJF/SPF）
短作业优先（SJF）
从后备队列中选择估计运行时间最短的作业，调入内存运行。