第三章 处理机管理

作业调度
就绪
等待
进程调度
内存
执行
3
高级调度
一.基本概念
作业：
用户在一次计算过程中，或者一次事务处理
过程中，要求计算机所做的工作的总称。作业由
程序、数据和作业说明书构成。 在批处理系统中，是以作业为基本单位从外 存调入内存的。
4
3.1
处理机调度的基本知识
作业说明书是一个独立于程序的文件，刻画
作业说明书：
9
1.高级调度
功能
▪ 根据JCB中的信息，审查系统能否满足用户作业的资 源需求，以及按照一定的算法，从外存的后备队列中 选取某些作业调入内存，并为它们创建进程、分配必 要的资源。然后再将新创建的进程插入就绪队列，准 备执行。
又称：
– 接纳调度、作业调度、长程调度
一般用于批处理系统，分/实时系统一般直接入 内存，无此环节。（P85下方）
41
例2(FIFO课堂练习)（时间为十进制形式）
作业名 提交时 刻 要求运行时间 开始运行时刻 完成时 刻
12.00 13.00 13.25 13.35
Ti
2.00 2.90 3.00 1.45
Wi
1 2.9 12 14.5
1
2 3 4
10.00
10.10 10.25 11.90
2.00
1.00 0.25 0.1
1 T Ti n i 1
n i
1 Ti W n i 1 TSi
n
31
3.2.2选择调度方式和算法的若干准则 响应时间： 用户从键盘提交一个请求到首次获得响应的时间， 包括从键盘输入的请求信息传送到处理机的时
间、处理机对请求处理的时间、处理后响应结
了用户对作业的描述，以及用户对作业处理的控制
要求，它是用作业控制语言书写的，内容有两部分： 作业情况的描述，如用户名、作业名、使用语言、 作业步骤、优先级等；另一部分是作业所需要的资 源，如空间需求、I/O设备要求、数量、估计运行
时间等。体现了用户的控制意图。
5
3.1
处理机调度的基本知识
作业步： 通常，每一个作业都必须经过若干个相互独
10.00 12.00 13.00 13.25
2.34 平均周转时间T= 平均带权周转时间W=
时间单位， 7.6 时间单位
44
3.2
调度算法
显然，FCFS调度算法有利于长作业，而不利于短
由调度程序(Dispatcher)把处理器分配给进程。
需为选中的进程恢复处理机现场，即把选中进程的进程控制 块内有关处理机现场的信息装入处理器相应的各个寄存器中，
把处理器的控制权交给该进程，让它从取出的断点处开始继
续运行。
14
2. 低级调度
三个基本机制：
– 排队器；
– 分派器； – 上下文切换机制。（两对上下文切换）
任务在本次分得的时间片内尚未完成，OS便将该任务再放 入就绪队列的末尾；
在执行期间，进程因为某事件而被阻塞后，被OS放入阻塞 队列。
25
3.2 进程调度模型
具有高级和低级调度的调度队列模型（批处理 系统）： 引入作业调度从外存的后备队列中选择一批作业 调入内存，为之创建进程后送入就绪队列。就绪队 列为优先权队列，按优先权进行调度； 设置多个阻塞队列，每个队列对应于一个引起进 程阻塞的事件。
12
2. 低级调度
功能：
– 决定就绪队列中的哪个进程（或内核级线程，为 叙述方便，以后只写进程）应获得处理机，然后 再由调度程序执行把处理机分配给该进程的具体 操作。主要是由调度程序（Dispatcher）分派处 理机。
又称：
– 进程调度、短程调度
13
2. 低级调度
主要功能：
– 保存处理机的现场信息； – 按某种算法从就绪队列中选取进程； – 把处理器分配给进程。
主要内容
处理机调度的基本概念 调度算法 实时调度 产生死锁的原因和必要条件
预防死锁的方法
死锁的检测和解除
1
主要内容
处理机调度的基本概念 调度算法 实时调度 产生死锁的原因和必要条件
预防死锁的方法
死锁的检测和解除
2
3.1 处理机调度的三个层次
外存 后备 状态 外存 就绪 等待 中级调度
28
3.2.2选择调度方式和算法的若干准则
几个概念：
时间片：一个很小的CPU时间间隔，通常从几ms到 几百ms。 I/O等待时间：是进程等待 I/O 完成的时间 。 截止时间：指某任务必须开始的最迟时间，或必须 完成的最迟时间.
29
3.2.2选择调度方式和算法的若干准则
周转时间： 从作业提交给系统开始，直到作业完成的时间，包括 作业在外存中等待运行的时间、进程在就绪队列中的
2 3 1
1
100
1 101 102
101 102 202
100 100 199
1 100 1.99
40
– 缺点:没考虑进程的优先级Leabharlann D1003.2
调度算法
一.先来先服务调度算法（FCFS）(属于不可抢占 调度) 优点： 简单、易于实现. 缺点： 1）有利于长的作业或进程，不利于短的。 2）有利于CPU繁忙型的作业或进程，不 利于I/O繁忙型的作业或进程。
15
2. 低级调度
进程调度的时机：
– 进程创建时
– 进程退出时 – 进程阻塞时 – I/O中断发生时
16
2. 低级调度
调度方式：
– 非抢占方式： – 一旦把处理机分配给某个进程，不管他要运行多长时 间，一直让他运行，绝不会因为时钟中断抢占他的处 理机，也不允许其他进程抢占已经分配给他的处理机。 直至进程完成或发生某事件阻塞。 – 抢占方式： – 允许调度程序根据某种原则去暂停某个正在执行的进 程，将已分配给该进程的处理机重新分配给另一个进 程。可防止一个进程长时间占据处理机。
7
3.1
处理机调度的基本知识
是作业说明书在系统中生成一个表格。该
作业控制块（Job Control Block，JCB）：
表格登记该作业所要求的资源情况、预计执行
时间和执行优先级等。JCB包含了系统对作业
进行管理和调度所必须的信息。
JCB是作业存在的唯一标志。
8
3.1
处理机调度的基本知识
作业的状态及其转换（了解） 提交状态：用户作业由输入设备向系统外存输入 时作业所处的状态。 后备状态：作业输入到外存后，系统为其建立了作 业控制块，并把它插入到后备作业队列中等待调度 运行。 执行状态：作业进入主存开始运行。 完成状态：作业正常或异常结束，但作业占有的资 源还未被系统全部回收。
22
高级、中级和低级调度
外存 后备作业 高级调度 操作系统 CPU 内存
对换进程 低级调度
中级调度
23
3.2 进程调度模型
就绪
在分时系统中，通常仅设臵了进程 调度，用户键入的命令和数据都直接送 入内存。
图 3 - 1 仅具有进程调度的调度队列模型
I/O完成 进程调度
时间片完
阻塞
执行 I/O请求
时间片完
10
1.高级调度
调度时要考虑因素
– 用户满意，系统满意
11
1.高级调度
– 接纳多少个作业（内存驻留数） 作业数目太多时，可能会影响到系统的服务质量，周转时间 （P90）太长。 作业的数量太少时，又会导致系统的资源利用率和系统吞吐量 （P91）太低 – 接纳策略：即采用何种调度算法 先来先服务调度算法 短作业优先调度算法 基于作业优先级的调度算法 – “响应比高者优先”的调度算法
FIFO队列
交互用户 事 件 出 现
就 绪 队 列
进程调度
CPU
进程完成
阻 塞 队 列
等待事件
24
3.2 进程调度模型
仅有进程调度的调度队列模型（假设把就绪进 程组织成FIFO队列形式，采用时间片轮转法进行调 度）： 每个进程在执行时，可能出现三种情况：
任务在给定的时间片内已经完成，该进程便在释放处理机 后进入完成状态；
等待时间、进程占用CPU时执行的时间、进程因发生
某等待事件在阻塞队列中的时间。 周转时间=完成时间-提交时间 运行时间：？ =完成时间-开始时间
30
3.2.2选择调度方式和算法的若干准则 平均周转时间：
作业的周转时间T与系统为它提供服务的 时间TS之比，即W=T/TS，称为带权周转
时间，而平均带权周转时间则可表示为:
39
3.2 调度算法--FCFS
思想： 到达
服务 开始执行 完成 周转 带权周转 进程名 时间 时间 时间 时间 时间 时间 – 把处理机分配给最先进入就绪队列的进程，一个进程
一旦分得处理机，便执行下去，直到该进程完成或阻 A 0 1 0 1 1 1 塞时，才释放处理机。
评价:
B C
– 优点:实现简单.
38
3.2
调度算法
一.先来先服务调度算法（FCFS）
适用于作业调度，进程调度。
调度方法： 作业调度采用该算法时，每次都是从后备作业队列 中选择一个或多个最先进入该队列的作业，将它们调 入内存，分配资源、创建进程，然后放入就绪队列. 进程调度中采用该算法时，每次都是从就绪队列中 选择一个最先进入该队列的进程，为之分配处理机， 投入运行.直到运行完成或阻塞时才放弃处理机.
立又相互关联的顺序加工步骤才能得到结果，
我们把其中的每个加工步骤称为一个作业步。
各作业步之间存在相互联系，往往上一个作
业步的结果为下一个作业步的输入。
6
3.1
处理机调度的基本知识