2014第三章 处理机调度与死锁

的作业调入内存，并创建进程、分配资源，安排在就绪
队列上。 用于多道批处理系统中。
2019/1/15
4
2、低级调度
也称为进程调度或短程调度，决定内存上处于就 绪队列中的哪个进程应获得处理机。 用于多道批处理、分时和实时三种类型的操作系 统中。
2019/级调度又称中程调度 为了提高内存利用率和系统吞吐量
2019/1/15 14
3、作业运行的三个阶段和三种状态
收容阶段：后备状态 运行阶段：运行状态 完成阶段：完成状态
2019/1/15
15
3.2.2 作业调度的主要任务
在每次执行作业调度时，都须做出以下两个决定： (A)接纳多少个作业 取决于多道程序度，即允许多少个作业同时在内存 中运行。 作业太少 资源利用率低 作业太多 服务质量下降 (B)接纳哪些作业：作业调度算法 先来先服务 短作业优先 优先权高优先 高响应比优先
2019/1/15
处理机调度的层次和调度算法的目标 作业与作业调度 进程调度 实时调度 死锁概述 预防死锁 避免死锁 死锁的检测与解除
2
3.1 处理机调度的层次和调度算法的目标
3.1.1 处理机调度的层次 1、高级调度 2、低级调度 3、中级调度
2019/1/15
3
1、高级调度
又称为作业调度或长程调度：将外存上处于后备队列上
2019/1/15
17
先来先服务调度算法(FCFS)
内存无限大，作业调度和进程调度都采用FCFS。
作业名 进入磁盘 时间 需要服务 装入主存 时间 时间 开始执行 时间 结束执行 时间 周转 时间 带权周转 时间
A B C D
0 1 2 3
1 100 1 100

8
第三章 处理机调度与死锁
3. 分时系统的目标 (1) 响应时间快
响应时间指用户提交请求到系统首次响应为止的时 间。
(2) 均衡性。 系统响应时间的快慢应与用户所请求的复杂性相适
应。
9
第三章 处理机调度与死锁
4. 实时系统的目标 (1) 截止时间的保证。 (2) 可预测性。
10
第三章 处理机调度与死锁
第三章 处理机调度与死锁
第三章 处理机调度与死锁
3.1 处理机调度的层次和调度算法的目标 3.2 作业与作业调度 3.3 进程调度 3.4 实时调度 3.5 死锁概述 3.6 预防死锁 3.7 避免死锁 3.8 死锁的检测与解除 习题
1
第三章 处理机调度与死锁
3.1 处理机调度的层次和调度算法的目标
为了提高系统效率，应当让管理输入输出的I/O进程与计算 进程搭配起来，并给予I/O进程较高的优先级。这样，一旦 I/O进程被唤醒就可很快得到运行，启动低速外设，而后再 被阻塞起来让计算进程使用CPU，使主机和外设高度并行 运行。
24
第三章 处理机调度与死锁
2. 高响应比优先调度算法(Highest Response Ratio Next，HRRN)
16
第三章 处理机调度与死锁 17
第三章 处理机调度与死锁
FCFS算法的优缺点 • 比较有利于长作业（进程），而不利于短作业（进
程）。 上图中短作业C的带权周转时间高达100，不能容忍。 而D仅为1.99。 • FCFS算法有利于CPU繁忙型作业（该类型的作业需 要大量CPU时间进行计算，很少I/O。）不利于I/O繁 忙型作业（频繁的请求I/O服务的作业）
5
第三章 处理机调度与死锁
2. 批处理系统的目标 (1) 平均周转时间短。 对每个用户而言，都希望自己作业的周转时间最短。但 作为计算机系统的管理者，则总是希望能使平均周转时间最 短，这不仅会有效地提高系统资源的利用率，而且还可使大 多数用户都感到满意。应使作业周转时间和作业的平均周转 时间尽可能短。否则，会使许多用户的等待时间过长，这将 会引起用户特别是短作业用户的不满。可把平均周转时间描 述为：

Event
Event Queue
32
Exit
Start
Ready Queue Time Slice CPU
Event
Event Queue
33
Exit
Start
Ready Queue Time Slice CPU
Event
Event Queue
34
3.2.2 短作业优先
(SJF, Shortest Job First)
2
主要内容


处理机调度的基本概念
调度算法


实时调度
多处理机系统中的调度


产生死锁的原因和必要条件
预防死锁的方法

死锁的检测与解除
3
3.1

处理机调度的基本概念
3.1.1 高级、中级和低级调度
处理机（ CPU ）在进程之间的动态分配和切换，
涉及到三种类型（或者说三个层次）的调度，
即高级调度（也叫作业调度、长程调度）、中
执行 时间 1 100 1 100
开始执 行时间 0 1 101 102
完成时 周转时 带权周 间 间 转时间 1 101 102 202 1 100 100 199 1 1 100 1.9919
CPU Scheduler Example

Process 1 burst computes for 14 time units Process 2 burst computes for 8 time units Process 3 burst computes for 8 time units
Hale Waihona Puke I/OChild Terminates

第三章处理机调度与死锁1、时间片轮转调度算法是为了（）。

A、多个用户能及时干预系统B、使系统变得高效C、优先级较高的进程得到及时响应D、需要CPU时间最少的进程最先做2、（）有利于CPU繁忙型的作业，而不利于I/O繁忙型的作业。

A、时间片轮转调度算法B、先来先服务调度算法C、短作业（进程）优先算法D、优先权调度算法3、下面有关选择进程调度算法的准则中不正确的是（）。

A、尽快响应交互式用户的请求B、尽量提高处理器利用率C、尽可能提高系统吞吐量D、适当增长进程就绪队列的等待时间4、设有4个作业同时到达，每个作业的执行时间均为2h，它们的一台处理器上按单道式运行，则平均周转时间为（）。

A、1hB、5hC、2.5hD、8h5、若每个作业只能建立一个进程，为了照顾短作业用户，应采用（）；为了照顾紧急作业用户，应采用（）；为了能实现人机交互，应采用（）；而能使短作业、长作业和交互作业用户都满意，应采用（）。

A、FCFS调度算法B、短作业优先调度算法C、时间片轮转调度算法D、多级反馈队列调度算法E、剥夺式优先级调度算法6、（）优先级是在创建进程时确定的，确定之后在整个运行期间不在改变。

A、先来先服务B、动态C、短作业D、静态7、现在有三个同时到达的作业J1、J2和J3，它们的执行时间分别是T1、T2、T3，且T1<T2<T3。

系统按单道方式运行且采用短作业优先调度算法，则平均周转时间是（）A、T1+T2+T3 B、（3×T1+2×T2+T3）/3C、（T1+T2+T3）/3D、（T1+2×T2+3×T3）/38、设有三个作业，其运行时间分别是2h、5h、3h，假定它们同时达到，并在同一个处理器上以单道方式运行，则平均周转时间最小的执行顺序是（）A、J1，J2，J3B、 J3 ，J2，J1C、J2，J1，J3D、 J1 ，J3 ，J29、采用时间片轮转调度算法分配CPU时，当处于运行状态的进程用完一个时间片后，它的状态是（）状态。