操作系统原理：处理机调度

处理机调度

处理机调度1、功能

对CPU资源进行合理的分配使用，提高处理机利用率，并使各用户公平地得到处理机资源。

处理机调度2、解决的问题（3W）WHAT：按什么原则分配CPU—进程调度算法（主要内容）WHEN：何时分配CPU—进程调度的时机HOW：如何分配CPU—CPU调度过程（进程的上下文切换）提交状态收容状态完成状态外存内存4.1分级调度1、

作业的状态及其转换就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度（1）提交状态：作业处于从输入设备进入外存的过程；（2）收容状态：作业的全部信息被输入到输入井，尚未被调度执行；（3）完成状态：作业运行完毕，所占资源尚未被收回。1、作业的状态及其转换一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、后备、执行和完成等4个状态。（1）提交状态：一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态。4.1分级调度1、作业的状态及其转换（2）后备状态：也称为收容状态。若一个作业的全部信息已全部被输入进输入井，则在它还未被调度去执行之前，该作业处于后备状态。4.1分级调度（3）执行状态：作业调度程序从后备作业中选取若干个作业到内存投入运行。它为被选中作业建立进程并分配必要的资源，这时，这些被选中的作业处于执行状态。1、作业的状态及其转换4.1分级调度（4）完成状态：当作业运行完毕，但它所占用的资源尚未全部被系统回收时，该作业处于完成状态。1、作业的状态及其转换4.1分级调度一个作业从进入系统到运行结束,经历的状态包括_________。进入状态A就绪状态B后备状态C运行状态D完成状态E提交多选题1分2调度的层次提交状态收容状态完成状态外存内存就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度第1级：作业调度、宏观调度、高级调度对外存输入井上的大量作业进行选择，对选择的作业分配资源，建立相应进程。作业执行完毕时，回收资源。4.1分级调度提交状态收容状态完成状态外存内存就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度第2级：交换调度、中级调度将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换导外存交换区。4.1分级调度2调度的层次提交状态收容状态完成状态外存内存就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度第3级：进程调度、微观调度、低级调度选取一个处于就绪状态的进程占用处理机，之后，进行上下文切换以便建立与占用处理机进程相适应的执行环境。2调度的层次4.1分级调度提交状态收容状态完成状态外存内存就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度第4级：线程调度选取一个处于就绪状态的线程进入执行状态。2调度的层次4.1分级调度提交状态收容状态完成状态外存内存就绪等待就绪等待执行输入管理系统交换调度线程调度进程调度作业调度多道批处理系统存在作业调度和进程调度；分时系统和实时系统一般只有进程调度、交换调度和线程调度。2调度的层次4.1分级调度一个作业处于运行状态,则所属该作业的进程可能处于（）状态。运行A就绪B等待C(1)或(2)或(3)D提交单选题1分AdmitRunningReadySuspendReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendEventOccursActivateAdmit宏观调度微观调度中级调度ActivateSuspendSuspendExitNew2调度的层次4.1分级调度下列有关作业的叙述中,_________是正确的。作业一旦被作业调度选中,即占有了CPUA批处理系统对作业的控制意图是靠作业说明书来实现的,用户不能控制作业的执行B作业调度程序从处于等待状态的队列中选取作业投入运行C作业一旦被作业调度选中,该作业即进入内存D允许多个用户在各自的终端上同时交互地使用计算机的系统称为分时操作系统E提交多选题1分3、

调度时间周期（1）长期(long-term)：将进程投入“允许执行”进程缓冲池中，或送到“退出”进程缓冲池中。进程状态：New

Readysuspend,Running

Exit,它将控制多道程序的程度，执行频率相对较低。4.1分级调度3、

调度时间周期（2）中期(medium-term)：将进程的部分或全部加载到内存中。进程状态：Ready

Readysuspend,Blocked

Blockedsuspend。4.1分级调度3调度时间周期（3）短期(short-term)：也称分派程序（dispatcher）选择哪个进程在处理机上执行。进程状态：Ready

Running。（4）I/O调度：选择哪个I/O等待进程，使其请求可以被空闲的I/O设备进行处理。4.1分级调度3调度时间周期用于调度的队列图

批作业CPU释放短程调度就绪队列就绪、挂起队列阻塞、挂起队列阻塞队列事件等待事件发生交互用户长程调度中程调度4.1分级调度4OS类型划分调度

（1）批处理调度－－应用场合：大中型主机集中计算，如工程计算、理论计算（流体力学）（2）分时调度、实时调度：通常没有专门的作业调度（3）多处理机调度4.1分级调度5作业与进程的关系（1）作业是用户向计算机提交任务的任务实体。（2）进程是计算机为完成用户任务而设置的执行实

体，是系统分配资源的基本单位。（3）一个作业有多个进程组成4.1分级调度5作业与进程的关系创建根进程创建子进程为子进程分配资源系统系统或根进程系统或根进程作业提交时作业后备状态执行状态完成状态4.1分级调度1作业调度的功能（1）记录系统中各作业的状况系统为每个作业建立一个JCB记录作业信息，系统通过JCB感知作业的存在。作业名作业类型资源要求资源使用情况优先级（数）当前状态其它作业进入后备状态时，系统为其建立JCB；作业进入完成状态后，系统撤销其JCB。4.1分级调度作业在系统中存在与否的唯一标志是()。源程序A作业说明书B作业控制块C目的程序D提交单选题1分1作业调度的功能（2）记录系统中各作业的状况作业名作业类型资源要求资源使用情况优先级（数）当前状态其它用户提供，系统将其转换为系统可识别的作业标识符计算型（CPU时间多）、管理型（I/O量大）、图形设计型（高速图形显示）执行时间、内外存量、外设、软件工具等进入系统/开始执行/已执行时间、内存地址、外设数目决定作业调度顺序，用户给定/系统动态产生作业的当前状态处于后备状态时，可被调度4.1分级调度

1作业调度的功能（1）记录系统中各作业的状况（2）从后备队列中选择一部分作业投入运行（涉及调度算法）（3）为被选中的作业做好执行前的准备（建立进程、为进程们分配系统资源）（4）作业执行结束时的后处理4.2作业调度2作业调度中状态的转换后备作业队列空？从中选一作业审核资源要求资源要求能满足？分配资源建立进程进程调度否是放弃该作业否从后备状态到执行状态从执行状态到完成状态回收该作业占用的资源计算该作业的执行费用撤销该作业进程及JCB调度下一个作业4.2作业调度3作业调度目标与性能衡量（1）目标公平性：对所有作业应该是公平的利用率：应使设备有高的利用率作业量：每天执行尽可能多的作业响应时间：有快的响应时间4.2作业调度3作业调度目标与性能衡量（2）面向用户的调度性能准则（定量指标）1）周转时间：作业从提交到完成所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等。主要用在批处理系统中。4.2作业调度作业从后备作业到被调度程序选中的时间称为()。周转时间A响应时间B等待调度时间C运行时间D提交单选题1分3作业调度目标与性能衡量（2）面向用户的调度性能准则1）周转时间Ti=作业完成时刻(Tei)-作业提交时刻(Tsi)=作业等待时间(Twi)+作业执行时间(Tri)2）平均周转时间4.2作业调度在批处理系统中,周转时间是（）。作业运行时间A作业等待时间和运行时间之和B作业的相对等待时间C作业被调度进入内存到运行完毕的时间D提交单选题1分3作业调度目标与性能衡量（2）

面向用户的调度性能准则

3）带权周转时间带权周转时间Wi=Ti/Tri平均带权周转时间4.2作业调度3作业调度目标与性能衡量（2）

面向系统的调度性能准则吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系，用于批处理系统中。处理机利用率：用于大中型主机。各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配——大中型主机4.2作业调度在一个以批处理为主的系统中,为了保证系统的吞吐率,总是要力争缩短用户作业的()。周转时间A运行时间B提交时间C完成时间D提交单选题1分3作业调度目标与性能衡量（3）算法本身的调度性能准则易于执行执行开销比4.2作业调度1进程调度的功能（1）记录所有进程的运行状况（静态和动态）（2）当进程出让CPU或调度程序剥夺执行状态进程占用的CPU时，选择适当的进程分派CPU（3）完成上下文切换4.3进程调度2进程调度的时机（1）正在执行的进程执行完毕（2）执行进程自己调用阻塞原语使自己变为等待状态（3）将睡眠的进程唤醒，将其加入就绪队列后，执行进程调度程序（4）执行进程调用P操作，因资源不足被阻塞4.3进程调度2进程调度的时机（5）执行进程因I/O被阻塞（6）分时系统中时间片用完（7）系统调用执行完毕，从系统程序返回到用户程序时，进行进程调度（8）可剥夺方式下，就绪队列中某进程优先级高于执行进程

4.3进程调度________可能会引起处理机从一个进程转到另一个进程。一个进程从运行状态变为等待状态A一个进程从运行状态变为就绪状态B一个就绪状态进程的优先级降低C一个进程运行完成而撤离系统D一个就绪状态进程的优先级升高E提交多选题1分3进程上下文切换（1）进程上下文组成

由正文段、数据段、硬件寄存器的内容以及有关数据结构组成。4.3进程调度3进程上下文切换（2）

进程上下文切换步骤决定是否切换以及是否允许切换保存当前执行进程的上下文应用调度算法选择一个处于就绪状态的进程恢复或装配所选进程的上下文，将CPU控制权交给所选进程4.3进程调度4进程调度性能评价（1）定性衡量调度的可靠性调度的简洁性（2）

定量衡量CPU利用率进程在队列中的等待时间与执行时间之比4.3进程调度一个进程处于等待状态,则该进程所属的作业存在于()中。内存A外存B高速缓存C寄存器D提交单选题1分1先来先服务（FCFS)（2）

算法思想按照作业或进程变为就绪状态的先后次序，分派CPU；当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。4.4调度算法（重点）1先来先服务

（2）FCFS特点比较有利于长作业，而不利于短作业；有利于CPU繁忙的作业，而不利于I/O繁忙的作业。4.4调度算法（重点）2短作业优先(SJF,ShortestJobFirst)

对FCFS算法进行了改进，其目标是减少平均周转时间。（1）

算法思想对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业4.4调度算法（重点）2短作业优先(SJF,ShortestJobFirst)

（2）

优点比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量。4.4调度算法（重点）

2短作业优先(SJF,ShortestJobFirst)（3）SJF缺点对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。4.4调度算法（重点）作业调度算法中“短作业优先”调度算法使得()。每个作业的等待时间较短A作业的平均等待时间最短B系统效率最高C长作业的等待时间较短D提交单选题1分

2短作业优先(SJF,ShortestJobFirst)

（4）SJF变形最短剩余时间优先SRT(ShortestRemainingTime)：允许比当前进程剩余时间更短的进程来抢占最高响应比优先HRRN(HighestResponseRatioNext)：是FCFS和SJF的折衷。响应比R=(等待时间+要求执行时间)/要求执行时间。4.4调度算法（重点）

3最高响应比优先（HRN）

（1）

算法思想及计算响应比最高的作业优先启动；响应比R=作业周转时间Ti/作业处理时间Tri=(作业处理时间Tri+作业等待时间Twi

)/作业处理时间Tri

=1+(作业等待时间Twi

/作业处理时间Tri

)。4.4调度算法（重点）3最高响应比优先（HRN）（2）

算法评价

该算法是FCFS和SJF的结合，克服了两种算法的缺点。优点:公平，吞吐率大缺点:增加了计算，增加了开销4.4调度算法（重点）4时间片轮转算法(RoundRobin)

（1）

与其它算法分析对比FCFS和SJF算法主要用于宏观调度；时间片轮转算法主要用于微观调度。4.4调度算法（重点）

4时间片轮转算法(RoundRobin)（2）算法设计目标通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率4.4调度算法（重点）时间片轮转法进行进程调度是为了()。多个终端都能得到系统的及时响应A先来先服务B优先级较高的进程得到及时响应C需要cpu最短的进程先做D提交单选题1分为了照顾紧迫型作业,应采用()。先来先服务调度算法A短作业优先调度算法B时间片轮转调度算法C优先权调度算法D提交单选题1分4时间片轮转算法(RoundRobin)（3）算法思想将系统中所有的就绪进程按照FCFS原则，排成一个队列；每次调度时将CPU分派给队首进程，让其执行一个时间片；在一个时间片结束时，发生时钟中断；4.4调度算法（重点）

4时间片轮转算法(RoundRobin)（3）算法思想调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程进程可以未使用完一个时间片，就出让CPU（如阻塞）4.4调度算法（重点）4时间片轮转算法(RoundRobin)F…DCBACPU阻塞完成超时4.4调度算法（重点）

4时间片轮转算法(RoundRobin)（4）

时间片长度的确定

1）时间片长度变化的影响过长

退化为FCFS算法，进程在一个时间片内都执行完，响应时间长；过短

用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。4.4调度算法（重点）4时间片轮转算法(RoundRobin)（4）时间片长度的确定

2）对响应时间的要求T(响应时间)=N(进程数目)*q(时间片)4.4调度算法（重点）影响时间片轮转调度算法对进程响应时间的因素有()。内存容量A时间片值的选取B外存容量C交互进程的数量DIO设备的速度E提交多选题1分下列有关基于时间片的进程调度的叙述中,错误的是()。时间片越短,进程切换的次数越多,系统开销也越大A当前进程的时间片用完后,该进程状态由执行态变为阻塞态B时钟中断发生后,系统会修改当前进程在时间片内的剩余时间C影响时间片大小的主要因素包括响应时间、系统开销和进程数量等。D提交单选题1分5多级队列算法(Multiple-levelQueue)

本算法引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标4.4调度算法（重点）5多级队列算法(Multiple-levelQueue)（1）

算法思想根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列；每个作业固定归入一个队列;各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等。4.4调度算法（重点）5多级队列算法

(Multiple-levelQueue)4.4调度算法（重点）6优先级算法是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。4.4调度算法（重点）为了照顾紧迫型作业,应采用()。先来服务调度算法A短作业优先调度算法B时间片轮转调度算法C优先权调度算法D提交单选题1分6优先级算法

（1）

静态优先级1）定义：创建进程时就确定，直到进程终止前都不改变。2）评级依据进程类型（系统进程优先级较高）对资源的需求（对CPU和内存需求较少的进程，优先级较高）用户要求4.4调度算法（重点）

6优先级算法（2）

动态优先级在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。4.4调度算法（重点）6优先级算法（2）动态优先级

优先级变化案例：在就绪队列中，等待时间延长则优先级提高，保证每个进程都有机会执行；进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU4.4调度算法（重点）6优先级算法（3）动态优先级具体算法1）线性优先级调度（SRR,SelfishRoundRobin）是动态优先级算法的一个算法，它通过进程优先级的递增来改进长执行时间进程的周转时间特征4.4调度算法（重点）6优先级算法（3）动态优先级具体算法1）线性优先级调度算法思想：就绪进程队列分成两个。新创建进程队列：按FCFS方式排成；进程优先级按速率a增加享受服务队列：已得到过时间片服务的进程按FCFS方式排成；进程优先级按速率b增加4.4调度算法（重点）6优先级算法（3）

动态优先级具体算法1）线性优先级调度算法思想新创建进程等待时间的确定：当新创建进程优先级与享受服务队列中最后一个进程优先级相同时，转入享受服务队列4.4调度算法（重点）

6优先级算法（3）动态优先级具体算法1）线性优先级调度4.4调度算法（重点）F…DCBACPU阻塞完成享受服务进程队列IJK…新创建进程队列6优先级算法（3）动态优先级具体算法abTimePrioritySRR算法的优先级变化4.4调度算法（重点）6优先级算法（4）SRR、FCFS、时间片轮转算法的关系当b>a>0时，享受服务队列中永远只有一个进程；SRR算法退化成FCFS算法；当a>b=0时，SRR算法就是时间片轮转算法。4.4调度算法（重点）在采用动态优先权的优先权调度算法中,如果所有进程都具有相同优先权初值,则此时的优先权调度算法实际上和()相同。先来先服务调度算法A短作业优先调度算法B时间片轮转调度算法C长作业优先调度算法D提交单选题1分下列进程调度算法中,()可能会出现进程长期得不到调度的情况。非强占式静态优先权法A强占式静态优先权法B时间片轮转调度算法C非强占式动态优先权法D提交单选题1分7多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。（1）

优点

为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程不必估计进程的执行时间，动态调节4.4调度算法（重点）7多级反馈队列

（2）算法思想设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍；4.4调度算法（重点）7多级反馈队列

（2）算法思想新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若在队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成；4.4调度算法（重点）下列选项中,降低进程优先级的合理时机是()。进程的时间片用完A进程刚完成I/O,进入就绪队列B进程长期处于就绪队列中C进程从就绪状态转为运行态D提交单选题1分7多级反馈队列

（2）算法思想仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。4.4调度算法（重点）

8调度算法性能指标（3）FCFS、RoundRobin和SRR周转时间比较长作业时：T(FCFS)<T(SRR)<T(RR)（运行时间是主要因素）；短作业时：T(RR)<T(SRR)<T(FCFS)（等待时间是主要因素）

。4.4调度算法（重点）1、假设在批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间：作业进入时间估计运行时间（分钟）JOB18:00120JOB28:5050JOB39:0010JOB49:50204.5调度算法应用举例要求：

应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间。4.5调度算法应用举例（考点）答：（1）先来先服务算法计算结果时间8:0010:0010:5011:0011:20J1120J250J310J4204.5调度算法应用举例（考点）（2）最短作业优先算法计算结果时间8:0010:0010:1010:3011:20J1120J250J310J4204.5调度算法应用举例（考点）（3）最高响应比算法计算结果时间8:0010:0010:1011:0011:20J1120J250J310J42070+50,60+10,10+2050102080+50,20+20

50204.5调度算法应用举例（考点）（4）最短作业优先算法执行结果4.5调度算法应用举例（考点）1．在一个多道程序设计系统中，不采用移动技术的可变分区方式管理内存。设用户空间为100K，主存空间采用最先适应分配算法，采用计算机时间短的作业优先算法管理作业。今有如所示的作业序列，请分别列出各个作业的开始执行时间、完成时间和周转时间（忽略系统开销）。作答正常使用主观题需2.0以上版本雨课堂可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本此处添加答案解析答案解析答案解析主观题10分

1实时调度概述（1）实时计算越来越重要，实时调度是实时系统中最重要的组（2）实时系统，如实时控制、过程控制、机器人、远程通信等；4.6实时调度（Real-TimeScheduling）1实时调度概述（3）实时计算系统的正确性不仅依赖于计算的逻辑结果，而且依赖于产生结果的时间；（4）通常给一个特定的任务制定一个最后期限，最后期限指定开始时间或结束时间。4.6实时调度（Real-TimeScheduling）

2实时调度分类（1）硬实时任务：必须满足最后期限的限制，否则产生致命的错误；（2）软实时任务：希望满足最后期限，但并不是强制的，超过期限，调度完成任务仍有意义；4.6实时调度（Real-TimeScheduling）2实时调度分类（3）一个非周期任务（aperiodictask）有一个必须结束或开始的最后期限；（4）周期任务，期限描述为“每隔周期T一次”。4.6实时调度（Real-TimeScheduling）2实时调度的特点（1）要求更详细的调度信息：如，就绪时间、开始或完成截止时间；（2）采用抢先式调度；4.6实时调度（Real-TimeScheduling）2实时调度的特点（3）快速中断响应，在中断处理时（硬件）关中断的时间尽量短；（4）快速上下文切换：相应地采用较小的调度单位（如线程）。4.6实时调度（Real-TimeScheduling）

3实时调度算法（1）静态表驱动调度；（2）静态优先级驱动的剥夺调度；（3）动态分析调度算法；（4）无保障动态调度算法。4.6实时调度（Real-TimeScheduling）3实时调度算法（1）静态表驱动调度算法适用于周期性的实时应用；算法的输入为：到达时间、运行时间、最后结束时间、任务间的优先关系；通过对所有周期性任务的输入信息分析预测，事先确定一个固定的调度方案，使得能够满足所有周期性任务的要求；4.6实时调度（Real-TimeScheduling）3实时调度算法（1）静态表驱动调度算法特点有效，但不灵活。因为任何任务要求的任何变化都需要重做调度变种：最早最后期限优先4.6实时调度（Real-TimeScheduling）3实时调度算法（2）静态优先级驱动的剥夺调度

把通用的优先级调度算法用于实时系统；

优先级的确定是通过静态分析完成的；

速率单调算法：任务的优先级=任务周期的倒数，即任务速率；优先级最高的任务是周期最短