大工20春《操作系统概论》辅导资料八
《操作系统概论》辅导资料八主 题：第3章处理器调度与死锁（第1—2节）学习时间：2020年5月18日--5月24日“不忘初心、牢记使命”主题理论学习：
“一带一路”是促进共同发展、实现共同繁荣的合作共赢之路，是增进理解信任、加强全方位交流的和平友谊之路。中国政府倡议，秉持和平合作、开放包容、互学互鉴、互利共赢的理念，全方位推进务实合作，打造政治互信、经济融合、文化包容的利益共同体、命运共同体和责任共同体。
摘选自《推动共建丝绸之路经济带和21世纪海上丝绸之路的愿景与行动》内 容：
第3章处理器调度与死锁
这周我们将学习课件第3章中的第1—2节，下面整理出的理念框架供同学们学习。
本篇的基本要求：
1．了解处理器调度的基本概念
2. 掌握处理器调度的分类
3．掌握调度算法
重点掌握内容：
1. 低级调度、高级调度、调度算法
3.1 处理器调度
1处理器调度的基本概念
处理器调度就是按照一定的规则分配处理器。在多道程序环境中，一个作业提交后，必须经过处理器调度，方能获得处理器而运行。不同类型的作业，需要经历的调度各不相同。对批处理作业而言，一般需要先后经历高级调度（作业调度）和低级调度（进程调度）方能获得处理器；而对于交互型的终端作业，通常只需经过低级调度（进程调度）就可以获得处理器。除了高级调度和低级调度以外，在一些比较完善的操作系统中，还设置了中级调度。每一种调度可以采用不同的调度方式和调度算法来实现。各种调度类型与进程状态之间的关系如图3-1所示。
/2 调度的层次
1、短期调度（低级调度、进程调度）
1）分配CPU给进程
2）进程的状态转换
低级调度（进程调度）是OS的核心部分，常驻内存。
低级调度是各类操作系统必须具备的一种调度。在最简单的分时操作系统和实时操作系统中，可以只设置低级调度。与低级调度相关联的进程（线程）队列称为就绪队列。就绪队列可以按照多种方式进行组织（FIFO原则、优先权原则、短进程优先原则），若按先进先出原则组织，并采用时间片原则进行调度，则只有低级调度的处理机调度模型如图3-2所示。
/2、长期调度（高级调度、作业调度）
1）自外存选择作业进入内存
2）分配I/O资源
3）建立进程
4）作业执行结束后回收系统资源
作业经由高级调度调入内存，为它们分配资源，建立进程，插入就绪队列之后，还需要经过低级调度才能获得处理机而执行。具有高级和低级两级调度的处理机调度模型如图3-3所示。
/
3、中期调度（中级调度、交换调度）
1）决定那些进程可以参与竞争CPU
2）内外存负荷的平衡：挂起就绪<──>就绪
挂起阻塞<──>阻塞
（外存） （内存）
交换调度涉及到内存，所以也可以归为内存管理部分。
中级调度又称为中程调度、交换调度、平衡调度等。引入这种调度的目的是提高内存的利用率和提高系统吞吐量。中级调度实际上就是交换（对换）功能。
中级调度可以使内存得到更加合理的利用，起到短期均衡系统负载的作用。
/3 作业调度及其功能
作业调度：按照某种调度算法从后备队列中挑选作业进入主存运行。
（1）、调度原则
1）对所有作业公平合理
2）设备有较高的利用率
3）能运行尽可能多的作业
4）有较快的响应时间
（2）、作业调度的功能
1）按某种原则从后备作业队列中挑选作业
2）分配主存和其他资源（除CPU）
3）为选中的作业建立第一个进程
4）构造和填写JCB
5）作业运行结束后善后处理
作业调度流程图:
/
5 选择调度算法时应考虑的问题
1、设计目标：
例如：批处理系统：效率问题
实时系统：实时性问题
分时系统：及时响应性问题
2、资源利用率：最大限度的发挥资源的作用
3、均衡处理系统和用户的要求
一对矛盾 系统要求：提高利用率
用户要求：及时响应（作业独占）
4、优先运行优先级高的进程（优先级调度方法）
5、优先级调度方法中的“可抢占”和“不可抢占”策略
不可抢占：除自己的原因外不可被其他进程抢占CPU
可抢占：允许其他进程抢占CPU3.2 调度算法
按一定的原则调度作业或进程投入运行的方法（作业或进程调度）
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)、优先级调度算法：按进程的优先级调度。
a）优先级高的先运行
b）优先级确定原则：系统指定，高费用等
c）分可抢占，不可抢占两种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、轮转法
分析：先来先服务调度算法。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。
短作业（进程）优先调度算法。短作业（进程）优先调度算法（SJ/PF）是指对短作业或短进程优先调度的算法，但其对长作业不利；不能保证紧迫性作业（进程）被及时处理；作业的长短只是被估算出来的。
优先权调度算法的类型。为了照顾紧迫性作业，使之进入系统后便获得优先处理，引入了最高优先权优先（FPF）调度算法。
时间片轮转法。时间片轮转法一般用于进程调度，每次调度，把CPU分配队首进程，并令其执行一个时间片。 当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环。
答案:B2、调度算法与作业的估计运行时间有关的是（）算法。
A、先来先服务
B、均衡
C、短作业优先
D、时间片轮转
分析：短作业（进程）优先调度算法。短作业（进程）优先调度算法（SJ/PF）是指对短作业或短进程优先调度的算法，该算法既可用于作业调度， 也可用于进程调度。但其对长作业不利；不能保证紧迫性作业（进程）被及时处理；作业的长短只是被估算出来的。
答案:C3、在进程调度算法中，最有利于提高系统吞吐量的作业调度算法是（）。
A、FCFS调度算法
B、短作业优先调度算法
C、时间片轮转法
D、多级反馈队列调度算法
分析：ABC第一道题分析已经介绍过,多级反馈队列调度算法，不必事先知道各种进程所需要执行的时间，它是目前被公认的一种较好的进程调度算法。 其实施过程如下：
1) 设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权越高的队列中， 为每个进程所规定的执行时间片就越小。
2) 当一个新进程进入内存后，首先放入第一队列的末尾，按FCFS原则排队等候调度。 如果他能在一个时间片中完成，便可撤离；如果未完成，就转入第二队列的末尾，在同样等待调度…… 如此下去，当一个长作业（进程）从第一队列依次将到第n队列（最后队列）后，便按第n队列时间片轮转运行。
3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1到第（i-1）队列空时， 才会调度第i队列中的进程运行，并执行相应的时间片轮转。
4) 如果处理机正在处理第i队列中某进程，又有新进程进入优先权较高的队列， 则此新队列抢占正在运行的处理机，并把正在运行的进程放在第i队列的队尾。
答案:B4、设有4个作业同时到达，每个作业的执行时间均为2小时，它们在一台处理机上按单道方式运行，则平均周转时间为（）。
A、1小时 B、5小时 C、2.5小时 D、8小时
分析：作业i从提出时刻tis到完成时刻tic的经历时间。即：
作业周转时间：Ti＝tic－tis
1作业 周转时间2小时，2作业等待2小时，执行2小时，共4小时，3号作业等待4，执行2，共6小时，4号等待6，执行2，共8小时。
作业周转时间=2+4+6+8=20
平均周转时间20/4=5小时
答案:B5、下列关于时间片轮转调度算法的叙述中，哪个是不正确的？（）。
A、在时间片轮转调度算法中，系统将CPU的处理时间划分成若干个时间段
B、就绪队列中的诸进程轮流在CPU运行，每次最多运行一个时间片
C、当时间片结束时，运行进程自动让出CPU，该进程进入等待队列
D、如果时间片长度很小，则调度程序抢占CPU的次数频繁，加重系统开销
分析：时间片轮转法。时间片轮转法一般用于进程调度，每次调度，把CPU分配队首进程，并令其执行一个时间片。 当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环。
答案:C转载注明 奥鹏无忧答案网
页:
[1]