大工13春《操作系统概论》辅导资料十二
大工13春《操作系统概论》辅导资料十二主 题：第六章多处理器管理系统和处理器管理（第3—4节）
学习时间：2013年6月17日－6月23日
内 容：
第六章多处理器管理系统和处理器管理
这周我们将学习第六章中的第3—4节，下面整理出的理念框架供同学们学习。
第三节 调度的层次和作业调度
一、调度的层次
1、长期调度（高级调度、作业调度）
1）自外存选择作业进入内存
2）分配I/O资源
3）建立进程
4）作业执行结束后回收系统资源
2、中期调度（中级调度、交换调度）
1）决定那些进程可以参与竞争CPU
2）内外存负荷的平衡：挂起就绪<──>就绪
挂起阻塞<──>阻塞
（外存） （内存）
交换调度涉及到内存，所以也可以归为内存管理部分。
3、短期调度（低级调度、进程调度）
1）分配CPU给进程
2）进程的状态转换
低级调度（进程调度）是OS的核心部分，常驻内存。
二、作业的状态及其转换图
作业也有生命周期，作业提交给系统直到运行结束，可能有如下状态及其状态转换：
三、作业的调度：实现作业由后备状态向完成状态的转换
1、后备作业队列和作业控制块
1）后备作业队列
输入到磁盘内的作业按作业的类型分成多个后备作业队列。
作业的类型可分为：CPU型：大量的时间使用CPU计算
I/O型：有较多的I/O操作
例如：按作业到达的顺序；按作业的优先级别等。
2）作业控制块JCB
由SPOOLING系统建立，记录作业相关信息的数据结构。
1）标志了作业的存在
2）记录作业所有信息
3）作业调度进行调度的依据
四、作业调度及其功能
作业调度：按照某种调度算法从后备队列中挑选作业进入主存运行。
1、调度原则
1）对所有作业公平合理
2）设备有较高的利用率
3）能运行尽可能多的作业
4）有较快的响应时间
2、作业调度的功能
1）按某种原则从后备作业队列中挑选作业
2）分配主存和其他资源（除CPU）
3）为选中的作业建立第一个进程
4）构造和填写JCB
5）作业运行结束后善后处理
3、作业调度流程图
五、补充
补充1、作业调度与进程调度的关系
进程调度从就绪队列中挑选一个进程占有处理机运行。
补充2、进程调度的功能
1）记录系统内所有进程的执行情况，通过PCB实现
2）选择占有处理机的进程
选择策略：静态优先级调度算法
轮转法
多级反馈轮转法等
3）控制进程间状态的转换（间接的，如有进程阻塞后，进程调度投入运行，选择新的进程占有处理机）。
第四节单处理器系统的处理器调度
一、进程调度的时机
决定什么时候进行调度：
1）正在执行的进程执行结束
2）正在执行的进程自己阻塞自己
3）正在执行的进程进行了wait、signal操作：
如：Wait操作，由于资源不足而阻塞自己Signal操作，唤醒了优先级高的进程
4）正在执行的进程提出了资源要求
5）分时系统中时间片到时
6）执行完系统调用后，重新调度（有的系统采用）
7）就绪队列中新增高于正在执行进程优先级的进程
二、选择调度算法时应考虑的问题
1、设计目标：
例如：批处理系统：效率问题
实时系统：实时性问题
分时系统：及时响应性问题
2、资源利用率：最大限度的发挥资源的作用
3、均衡处理系统和用户的要求
一对矛盾 系统要求：提高利用率
用户要求：及时响应（作业独占）
4、优先运行优先级高的进程（优先级调度方法）
5、优先级调度方法中的“可抢占”和“不可抢占”策略
不可抢占：除自己的原因外不可被其他进程抢占CPU
可抢占：允许其他进程抢占CPU
三、调度算法
按一定的原则调度作业或进程投入运行的方法（作业或进程调度）
1、衡量调度算法的指标
1）平均周转时间
作业i从提出时刻tis到完成时刻tic的经历时间。即：
作业周转时间：Ti＝tic－tis
进程周转时间：Ti＝tic－tis
几个作业（或进程）的平均周转时间：
T＝1/n（∑Ti）
T可用来衡量不同调度算法对同一作业（进程）的调度性能。理论上说：T的值越小越好。
其中：tic表示进程执行完本次CPU时刻；tis表示进程进入队列时刻。
2）平均等待时间
Wi＝tip－tir
tip表示获得CPU时刻，tir表示进程进入就绪队列时刻
n个进程的平均等待时间：
W＝1/n（∑Wi）
理论上说：W的值越小越好。
2、调度算法
1)、先来先服务调度算法（FIFO，FCFS）
a）按作业到达系统或进程到达就绪队列的先后次序调度
b）先来先服务
c）不可抢占调度算法
Ä高昂型：步态轻盈，昂首挺胸，阔步前进。语义：愉悦、自信、傲慢。
2)、优先级调度算法
按进程的优先级调度。
1）优先级高的先运行
2）优先级确定原则：系统指定，高费用等
3）分可抢占，不可抢占两种
3)、时间片轮转法
FIFO与时间片轮转的综合方法：
a）FIFO选择就绪队列中最先到达的进程运行
b）时间片：进程占有CPU的时间有限，到时后排到就绪队列的末尾
问题：1）时间片太大：退化到FIFO
2）时间片太小：增加系统的进程切换开销
4)、最短进程优先调度算法
从就绪队列中选择所需运行时间最短（估计）的进程运行
a）非抢占调度算法
b）可有效减少平均等待时间
c）提高系统的吞吐量
缺点：a）大进程等待时间长
b）用户很难准确估计进程的运行时间
c）不能保证及时响应
5)、最短剩余时间优先调度算法
让运行到进程完成时所需的运行时间最短的作业优先运行
已运行时间 剩余时间
进程1|─────|─────────|
所需运行时间
进程2 |──────|
优点：保证对用户的及时响应，可用于分时系统
缺点：系统开销大，如比较时间，切换时间等
6、最高响应比优先调度算法
改进的优先级调度算法，非抢占调度策略。
到达时间＋要求服务时间
优先级＝─────────────
要求服务时间
7)、多级反馈队列调度算法
时间片轮转法的发展，依据：
a）短作业优先：提高吞吐能力，降低平均等待时间
b）输入输出型优先：提高外设的效率
c）动态决定作业的性质（什么类型等）来进行调度
调度方法：
a）多个就绪队列
b）各队列有不同的时间片，级高，时间片小
c）先运行高级队列内进程，时间片到时进入下一级队尾
d）低级队列进程运行时，有高级进程进入队列时抢占CPU
选择题
1、对紧急进程或重要进程进行调度，调度算法应采用（）。
A、先进先出调度算法
B、优先级调度
C、短作业优先调度
D、轮转法
2、调度算法与作业的估计运行时间有关的是（）算法。
A、先来先服务
B、均衡
C、短作业优先
D、时间片轮转
3、在进程调度算法中，最有利于提高系统吞吐量的作业调度算法是（）。
A、FCFS调度算法
B、短作业优先调度算法
C、时间片轮转法
D、多级反馈队列调度算法
4、设有4个作业同时到达，每个作业的执行时间均为2小时，它们在一台处理机上按单道方式运行，则平均周转时间为（）。
A、1小时 B、5小时 C、2.5小时 D、8小时
5、下列关于时间片轮转调度算法的叙述中，哪个是不正确的？（）。
A、在时间片轮转调度算法中，系统将CPU的处理时间划分成若干个时间段
B、就绪队列中的诸进程轮流在CPU运行，每次最多运行一个时间片
C、当时间片结束时，运行进程自动让出CPU，该进程进入等待队列
D、如果时间片长度很小，则调度程序抢占CPU的次数频繁，加重系统开销
参考答案
1-5BCBBC
页:
[1]