1、第四章第四章 处理机调度处理机调度第四章第四章 处理机调度处理机调度1、功能、功能 对对CPU资源进行合理的分配使用，提高处理机资源进行合理的分配使用，提高处理机利利用率用率，并使各用户，并使各用户公平公平地得到处理机资源。地得到处理机资源。第四章第四章 处理机调度处理机调度2、解决的问题（、解决的问题（3W）WHAT：按什么原则分配：按什么原则分配CPU 进程进程（作业）（作业）调度算法（主要内容）调度算法（主要内容）WHEN：何时分配：何时分配CPU 进程调度的时机进程调度的时机HOW：如何分配如何分配CPU CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）提交提交状态状态收
2、容收容状态状态完成完成状态状态外存外存内存内存4.1 4.1 分级调度分级调度1 1、作业的状态及其转换作业的状态及其转换就绪就绪等待等待就绪就绪等待等待执行执行输入管理系统输入管理系统交换调度交换调度线程调度线程调度进程调度进程调度作业调度作业调度（1 1）提交状态：作业处于从）提交状态：作业处于从输入设备进入外存的过程；输入设备进入外存的过程；（2 2）收容状态：作业的全部）收容状态：作业的全部信息被输入到输入井，尚未信息被输入到输入井，尚未被调度执行；被调度执行；（3 3）完成状态：作业运行）完成状态：作业运行完毕，所占资源尚未被收回。完毕，所占资源尚未被收回。1 1、作业的状态及其转换
3、、作业的状态及其转换一个作业从提交给计算机系统到执行结束退出系统，一般一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、后备、都要经历提交、后备、执行执行和完成等和完成等4个状态。个状态。（1）提交状态：）提交状态：一个作业在其处于从输入设备进入外部一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态。存储设备的过程称为提交状态。4.1 4.1 分级调度分级调度1 1、作业的状态及其转换、作业的状态及其转换（2）后备状态：）后备状态：也称为收容状态。若一个作业的全部信也称为收容状态。若一个作业的全部信息已全部被输入进输入井，则在它还未被调度去执行之息已全部被输入进输入井，
4、则在它还未被调度去执行之前，该作业处于后备状态。前，该作业处于后备状态。4.1 4.1 分级调度分级调度（3）执行状态：）执行状态：作业调度程序从后备作业中选取若干个作业调度程序从后备作业中选取若干个作业到作业到内存投入运行内存投入运行。它为被选中作业建立进程并分配必。它为被选中作业建立进程并分配必要的资源，这时，这些被选中的作业处于执行状态。要的资源，这时，这些被选中的作业处于执行状态。1 1、作业的状态及其转换、作业的状态及其转换4.1 4.1 分级调度分级调度（4）完成状态：）完成状态：当作业运行完毕，但它所占用的资源尚当作业运行完毕，但它所占用的资源尚未全部被系统回收时，该作业处于完成
5、状态。未全部被系统回收时，该作业处于完成状态。1 1、作业的状态及其转换、作业的状态及其转换4.1 4.1 分级调度分级调度一个作业从进入系统到运行结束,经历的状态包括_。进入状态A就绪状态B后备状态C运行状态D完成状态E提交多选题1分2 2 调度的层次调度的层次提交提交状态状态收容收容状态状态完成完成状态状态外存外存内存内存就绪就绪等待等待就绪就绪等待等待执行执行输入管理系统输入管理系统交换调度交换调度线程调度线程调度进程调度进程调度作业调度作业调度第第1 1级：作业调度、级：作业调度、宏观宏观调度、高级调度调度、高级调度 对外存输入井上的大对外存输入井上的大量作业进行选择，对选量作业进行选
6、择，对选择的作业分配资源，建择的作业分配资源，建立相应进程。作业执行立相应进程。作业执行完毕时，回收资源。完毕时，回收资源。4.1 4.1 分级调度分级调度提交提交状态状态收容收容状态状态完成完成状态状态外存外存内内存存就绪就绪等待等待就绪就绪等待等待执行执行输入管理系统输入管理系统交换调度交换调度线程调度线程调度进程调度进程调度作业调度作业调度第第2 2级：交换调度、级：交换调度、中级中级调度调度将处于外存交换区中的将处于外存交换区中的就绪状态或等待状态的就绪状态或等待状态的进程调入内存，或把处进程调入内存，或把处于内存就绪状态或内存于内存就绪状态或内存等待状态的进程交换导等待状态的进程交换
7、导外存交换区。外存交换区。4.1 4.1 分级调度分级调度2 2 调度的层次调度的层次提交提交状态状态收容收容状态状态完成完成状态状态外存外存内内存存就绪就绪等待等待就绪就绪等待等待执行执行输入管理系统输入管理系统交换调度交换调度线程调线程调度度进程调度进程调度作业调度作业调度第第3 3级：进程调度、级：进程调度、微微观调度、低级调度观调度、低级调度选取一个处于就绪状选取一个处于就绪状态的进程占用处理机，态的进程占用处理机，之后，进行上下文切之后，进行上下文切换以便建立与占用处换以便建立与占用处理机进程相适应的执理机进程相适应的执行环境。行环境。2 2 调度的层次调度的层次4.1 4.1 分级
8、调度分级调度提交提交状态状态收容收容状态状态完成完成状态状态外存外存内存内存就绪就绪等待等待就绪就绪等待等待执行执行输入管理系统输入管理系统交换调度交换调度线程调线程调度度进程调进程调度度作业调作业调度度第第4 4级：线程调度级：线程调度选取一个处于就选取一个处于就绪状态的线程进绪状态的线程进入执行状态。入执行状态。2 2 调度的层次调度的层次4.1 4.1 分级调度分级调度提交提交状态状态收容收容状态状态完成完成状态状态外存外存内存内存就绪就绪等待等待就绪就绪等待等待执行执行输入管理系统输入管理系统交换调度交换调度线程调度线程调度进程调度进程调度作业调度作业调度多道批处理系统存在多道批处理系
9、统存在作业调度和进程调度作业调度和进程调度；分时系统和实时系统分时系统和实时系统一般只有一般只有进程调度、进程调度、交换调度和线程调度。交换调度和线程调度。2 2 调度的层次调度的层次 4.1 4.1 分级调度分级调度一个作业处于运行状态,则所属该作业的进程可能处于（）状态。运行A就绪B等待C(1)或(2)或(3)D提交单选题1分AdmitRunningReadySuspendReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendEventOccursActivateAdmit宏观调度宏观调度微观调
10、度微观调度中级调度中级调度ActivateSuspendSuspendExitNew2 2 调度的层次调度的层次4.1 4.1 分级调度分级调度下列有关作业的叙述中,_是正确的。作业一旦被作业调度选中,即占有了CPUA批处理系统对作业的控制意图是靠作业说明书来实现的,用户不能控制作业的执行B作业调度程序从处于等待状态的队列中选取作业投入运行C作业一旦被作业调度选中,该作业即进入内存D允许多个用户在各自的终端上同时交互地使用计算机的系统称为分时操作系统E提交多选题1分3、调度时间周期调度时间周期（1）长期）长期(long-term)：将进程投入：将进程投入“允许执行允许执行”进程缓进程缓冲池中，
11、或送到冲池中，或送到“退出退出”进程缓冲池中。进程状态：进程缓冲池中。进程状态：New Ready suspend,Running Exit,它将控制多道它将控制多道程序的程度，执行频率相对较低。程序的程度，执行频率相对较低。4.1 4.1 分级调度分级调度3、调度时间周期调度时间周期（2）中期）中期(medium-term)：将进程的部分或全部加载到：将进程的部分或全部加载到内存中。进程状态：内存中。进程状态：Ready Ready suspend,Blocked Blocked suspend。4.1 4.1 分级调度分级调度3 调度时间周期调度时间周期（3）短期）短期(short-ter
12、m)：也称分派程序（：也称分派程序（dispatcher）选择选择哪个进程在处理机上执行。进程状态：哪个进程在处理机上执行。进程状态：Ready Running。（4）I/O调度调度：选择哪个：选择哪个I/O等待进程，使其请求可以被空等待进程，使其请求可以被空闲的闲的I/O设备进行处理。设备进行处理。4.1 4.1 分级调度分级调度3 调度时间周期调度时间周期 用于调度的队列图用于调度的队列图 批作业批作业CPUCPU释放释放短程调度短程调度就绪队列就绪队列就绪、挂起队列就绪、挂起队列阻塞、挂起队列阻塞、挂起队列阻塞队列阻塞队列事件等待事件等待事事件件发发生生交互用户交互用户长程调度长程调度中
13、程调度中程调度4.1 4.1 分级调度分级调度 4 OS类型划分调度类型划分调度 （1）批处理调度）批处理调度应用场合：大中型主机集中计算，应用场合：大中型主机集中计算，如工程计算、理论计算（流体力学）如工程计算、理论计算（流体力学）（2）分时调度、实时调度：）分时调度、实时调度：通常没有专门的作业调度通常没有专门的作业调度（3）多处理机调度）多处理机调度4.1 4.1 分级调度分级调度 5 作业与进程的关系作业与进程的关系（1）作业是用户向计算机提交任务的任务实体。）作业是用户向计算机提交任务的任务实体。（2）进程是计算机为完成用户任务而设置的执行实）进程是计算机为完成用户任务而设置的执行实
14、 体，是系统分配资源的基本单位。体，是系统分配资源的基本单位。（3）一个作业有多个进程组成）一个作业有多个进程组成4.1 4.1 分级调度分级调度 5 5 作业与进程的关系作业与进程的关系创建创建根进程根进程创建创建子进程子进程为子进程为子进程分配资源分配资源系统系统系统或根进程系统或根进程系统或根进程系统或根进程作业提交时作业提交时作业作业后备后备状态状态执行执行状态状态完成完成状态状态4.1 4.1 分级调度分级调度 1 1 作业调度的功能作业调度的功能（1 1）记录系统中各作业的状况）记录系统中各作业的状况系统为每个作业建立一个系统为每个作业建立一个JCBJCB记录作业信息，记录作业信息
15、，系统通过系统通过JCBJCB感知作业的存在。感知作业的存在。作业名作业名作业类型作业类型资源要求资源要求资源使用情况资源使用情况优先级（数）优先级（数）当前状态当前状态其它其它作业进入后备状态时，系统为其建立作业进入后备状态时，系统为其建立JCBJCB；作业进入完成状态后，系统撤销其作业进入完成状态后，系统撤销其JCBJCB。4.1 4.1 分级调度分级调度作业在系统中存在与否的唯一标志是()。源程序A作业说明书B作业控制块C目的程序D提交单选题1分1 作业调度的功能作业调度的功能 （2）记录系统中各作业的状况）记录系统中各作业的状况作业名作业名作业类型作业类型资源要求资源要求资源使用情况资
16、源使用情况优先级（数）优先级（数）当前状态当前状态其它其它用户提供，系统将其转换为系用户提供，系统将其转换为系统可识别的作业标识符统可识别的作业标识符计算型（计算型（CPUCPU时间多）、管理型（时间多）、管理型（I/OI/O量量大）、图形设计型（高速图形显示）大）、图形设计型（高速图形显示）执行时间、内外存量、外设、软件工具等执行时间、内外存量、外设、软件工具等进入系统进入系统/开始执行开始执行/已执行时间、内存地址、外设数已执行时间、内存地址、外设数目目决定作业调度顺序，用户给定决定作业调度顺序，用户给定/系统动态产生系统动态产生作业的当前状态作业的当前状态处于后备状态时，可被调度处于后备
17、状态时，可被调度4.1 4.1 分级调度分级调度 1 作业调度的功能作业调度的功能（1）记录系统中各作业的状况）记录系统中各作业的状况（2）从后备队列中选择一部分作业投入运行）从后备队列中选择一部分作业投入运行（涉及调度算法）（涉及调度算法）（3）为被选中的作业做好执行前的准备）为被选中的作业做好执行前的准备（建立进程、为进程（建立进程、为进程们分配系统资源）们分配系统资源）（4）作业执行结束时的后处理）作业执行结束时的后处理4.2 4.2 作业调度作业调度 2 2 作业调度中状态的转换作业调度中状态的转换后备作业后备作业队列空？队列空？从中从中选一作业选一作业审核审核资源要求资源要求资源要求
18、资源要求能满足？能满足？分配分配资源资源建立建立进程进程进程进程调度调度否否是是放弃放弃该作业该作业否否从后备状态到执行状态从后备状态到执行状态从执行状态到完成状态从执行状态到完成状态回收该作业回收该作业占用的资源占用的资源计算该作业计算该作业的执行费用的执行费用撤销该作业撤销该作业进程及进程及JCB调度调度下一个作业下一个作业4.2 4.2 作业调度作业调度3 作业调度目标与性能衡量作业调度目标与性能衡量（1）目标）目标公平性：对所有作业应该是公平的公平性：对所有作业应该是公平的利用率：应使设备有高的利用率利用率：应使设备有高的利用率作业量：每天执行尽可能多的作业作业量：每天执行尽可能多的作
19、业响应时间：有快的响应时间响应时间：有快的响应时间4.2 4.2 作业调度作业调度 3 作业调度目标与性能衡量作业调度目标与性能衡量（2）面向用户的调度性能准则（定量指标）面向用户的调度性能准则（定量指标）1）周转时间：周转时间：作业从提交到完成所经历的时间。作业从提交到完成所经历的时间。包括：在收容队列中等待，包括：在收容队列中等待，CPU上执行，就绪队列和上执行，就绪队列和阻塞队列中等待，结果输出等。主要用在批处理系统阻塞队列中等待，结果输出等。主要用在批处理系统中。中。4.2 4.2 作业调度作业调度作业从后备作业到被调度程序选中的时间称为()。周转时间A响应时间B等待调度时间C运行时间
20、D提交单选题1分 3 作业调度目标与性能衡量作业调度目标与性能衡量（2）面向用户的调度性能准则）面向用户的调度性能准则1）周转时间）周转时间Ti=作业完成时刻作业完成时刻(Tei)-作业提交时刻作业提交时刻(Tsi)=作业等待时间作业等待时间(Twi)+作业执行时间作业执行时间(Tri)2）平均周转时间）平均周转时间 niiTnT114.2 4.2 作业调度作业调度在批处理系统中,周转时间是（）。作业运行时间A作业等待时间和运行时间之和B作业的相对等待时间C作业被调度进入内存到运行完毕的时间D提交单选题1分3 作业调度目标与性能衡量作业调度目标与性能衡量（2）面向用户的调度性能准则面向用户的调
21、度性能准则 3）带权周转时间（没有单位）带权周转时间（没有单位）带权周转时间带权周转时间Wi=Ti/Tri平均带权周转时间平均带权周转时间 niiWnW114.2 4.2 作业调度作业调度 3 作业调度目标与性能衡量作业调度目标与性能衡量（2）面向系统的调度面向系统的调度性能准则性能准则吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系，用于批处理系统中。处理机利用率：用于大中型主机。各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配大中型主机4.2 4.2 作业调度作业调度在一个以批处理为主的系统中,为了保证系统的吞吐率,总是要力争缩短用户作
22、业的()。周转时间A运行时间B提交时间C完成时间D提交单选题1分 3 3 作业调度目标与性能衡量作业调度目标与性能衡量（3）算法本身的调度性能准则）算法本身的调度性能准则易于执行易于执行执行开销比执行开销比4.2 4.2 作业调度作业调度 1 进程调度的功能进程调度的功能（1）记录）记录所有进程的运行状况（静态和动态）所有进程的运行状况（静态和动态）（2）当进程出让）当进程出让CPU或调度程序剥夺执行状态进程占用或调度程序剥夺执行状态进程占用的的CPU时，时，选择选择适当的进程分派适当的进程分派CPU（3）完成）完成上下文切换上下文切换4.3 4.3 进程调度进程调度 2.进程调度的时机进程调
23、度的时机（1）正在执行的进程执行完毕）正在执行的进程执行完毕（2）执行进程自己调用阻塞原语使自己变为等待状态）执行进程自己调用阻塞原语使自己变为等待状态（3）将睡眠的进程唤醒，将其加入就绪队列后，执行进）将睡眠的进程唤醒，将其加入就绪队列后，执行进程调度程序程调度程序（4）执行进程调用）执行进程调用P操作，因资源不足被阻塞操作，因资源不足被阻塞4.3 4.3 进程调度进程调度 2 进程调度的时机进程调度的时机（5）执行进程因）执行进程因I/O被阻塞被阻塞（6）分时系统中时间片用完）分时系统中时间片用完（7）系统调用执行完毕，从系统程序返回到用户程序时，进）系统调用执行完毕，从系统程序返回到用户
24、程序时，进行进程调度行进程调度（8）可剥夺方式下，就绪队列中某进程优先级高于执行进程）可剥夺方式下，就绪队列中某进程优先级高于执行进程 4.3 4.3 进程调度进程调度若某单处理器多进程系统中有多个就绪态进程,则下列关于处理机调度的叙述中,错误的是()。在进程结束时能进行处理机调度A创建新进程后能进行处理机调度B在进程处于临界区时不能进行处理机调度C在系统调用完成并返回用户态时能进行处理机调度D提交单选题1分 3 进程上下文切换进程上下文切换 （1）进程上下文组成）进程上下文组成 由正文段、数据段、硬件寄存器的内容以及有关数据结由正文段、数据段、硬件寄存器的内容以及有关数据结构组成。构组成。4
25、.3 4.3 进程调度进程调度 3 进程上下文切换进程上下文切换（2）进程上下文切换步骤进程上下文切换步骤决定是否切换以及是否允许切换决定是否切换以及是否允许切换保存当前执行进程的上下文保存当前执行进程的上下文应用调度算法选择一个处于就绪状态的进程应用调度算法选择一个处于就绪状态的进程恢复或装配所选进程的上下文，将恢复或装配所选进程的上下文，将CPU控制权交给所选进程控制权交给所选进程4.3 4.3 进程调度进程调度 4 进程调度性能评价进程调度性能评价（1）定性衡量定性衡量调度的可靠性调度的可靠性调度的简洁性调度的简洁性（2）定量衡量定量衡量 CPU利用率利用率 进程在队列中的等待时间与执行
26、时间之比进程在队列中的等待时间与执行时间之比4.3 4.3 进程调度进程调度一个进程处于等待状态,则该进程所属的作业存在于()中。内存A外存B高速缓存C寄存器D提交单选题1分1 先来先服务（先来先服务（FCFS)（2）算法思想算法思想 按照作业或进程变为就绪状态的按照作业或进程变为就绪状态的先后次序先后次序，分派，分派CPU；当前作业或进程占用当前作业或进程占用CPU，直到执行完或阻塞直到执行完或阻塞，才出让，才出让CPU（非抢占方式）（非抢占方式）在作业或进程在作业或进程唤醒后唤醒后（如（如I/O完成），并不立即恢复执行，通完成），并不立即恢复执行，通常等到当前作业或进程出让常等到当前作业或
27、进程出让CPU。4.4 4.4 调度算法（重点）调度算法（重点）1 先来先服务先来先服务 （2 2）FCFS FCFS特点特点 比较有利于长作业，而不利于短作业；比较有利于长作业，而不利于短作业；有利于有利于CPU繁忙的作业，而不利于繁忙的作业，而不利于I/O繁忙的作业。繁忙的作业。4.4 4.4 调度算法（重点）调度算法（重点）2 短作业优先短作业优先(SJF,Shortest Job First)对对FCFS算法进行了改进，其目标是减少平均周转时间。算法进行了改进，其目标是减少平均周转时间。（1）算法思想算法思想 对对预计执行时间预计执行时间短短的作业（进程）优先分派处理机。的作业（进程）
28、优先分派处理机。通常后来的短作业通常后来的短作业不抢先不抢先正在执行的作业正在执行的作业4.4 4.4 调度算法（重点）调度算法（重点）2 短作业优先短作业优先(SJF,Shortest Job First)（2）优点优点 比比FCFS改善改善平均周转时间平均周转时间和和平均带权周转时间平均带权周转时间，缩，缩短作业的等待时间；短作业的等待时间；提高系统的提高系统的吞吐量。吞吐量。4.4 4.4 调度算法（重点）调度算法（重点）2 短作业优先短作业优先(SJF,Shortest Job First)（3）SJF缺点缺点 对长作业非常不利对长作业非常不利，可能长时间得不到执行；，可能长时间得不到
29、执行；未能依据作业的未能依据作业的紧迫程度紧迫程度来划分执行的优先级；来划分执行的优先级；难以准确估计作业（进程）的执行时间难以准确估计作业（进程）的执行时间，从而影响调度，从而影响调度性能。性能。4.4 4.4 调度算法（重点）调度算法（重点）作业调度算法中“短作业优先”调度算法使得()。每个作业的等待时间较短A作业的平均等待时间最短B系统效率最高C长作业的等待时间较短D提交单选题1分 2 短作业优先短作业优先(SJF,Shortest Job First)（4）SJF变形变形最短剩余时间优先最短剩余时间优先SRT(Shortest Remaining Time)：允许：允许比当前进程剩余时
30、间更短的进程来比当前进程剩余时间更短的进程来抢占抢占最高响应比优先最高响应比优先HRRN(Highest Response Ratio Next)：是：是FCFS和和SJF的折衷。响应比的折衷。响应比R=(等待时间等待时间+要求执行时要求执行时间间)/要求执行时间。要求执行时间。4.4 4.4 调度算法（重点）调度算法（重点）3 最高响应比优先（最高响应比优先（HRN）（1）算法思想及计算算法思想及计算 响应比最高的作业优先启动；响应比最高的作业优先启动；响应比响应比R=作业周转时间作业周转时间Ti/作业处理时间作业处理时间Tri =(作业处理时间作业处理时间Tri+作业等待时间作业等待时间T
31、wi)/作业处理时间作业处理时间Tri =1+(作业等待时间作业等待时间Twi/作业处理时间作业处理时间Tri)。4.4 4.4 调度算法（重点）调度算法（重点）3 最高响应比优先（最高响应比优先（HRN）（2）算法评价算法评价 该算法是该算法是FCFS和和SJF的结合，克服了两种算法的缺点。的结合，克服了两种算法的缺点。优点优点:公平，吞吐率大公平，吞吐率大 缺点缺点:增加了计算，增加了开销增加了计算，增加了开销4.4 4.4 调度算法（重点）调度算法（重点）4 时间片轮转算法时间片轮转算法(Round Robin)（1）与其它算法分析对比与其它算法分析对比 FCFS和和SJF算法主要用于算
32、法主要用于宏观调度宏观调度；时间片轮转；时间片轮转算法主要用于微观调度。算法主要用于微观调度。4.4 4.4 调度算法（重点）调度算法（重点）4 时间片轮转算法时间片轮转算法(Round Robin)（2）算法设计目标）算法设计目标 通过通过时间片轮转时间片轮转，提高进程，提高进程并发性并发性和和响应时间响应时间特特性，从而提高性，从而提高资源利用率资源利用率4.4 4.4 调度算法（重点）调度算法（重点）时间片轮转法进行进程调度是为了()。多个终端都能得到系统的及时响应A先来先服务B优先级较高的进程得到及时响应C需要cpu最短的进程先做D提交单选题1分为了照顾紧迫型作业,应采用()。先来先服
33、务调度算法A短作业优先调度算法B时间片轮转调度算法C优先权调度算法D提交单选题1分 4 时间片轮转算法时间片轮转算法(Round Robin)（3）算法思想）算法思想 将系统中所有的就绪进程按照将系统中所有的就绪进程按照FCFS原则，排成一个原则，排成一个队列；队列；每次调度时将每次调度时将CPU分派给分派给队首进程队首进程，让其，让其执行一个时间执行一个时间片片；在一个时间片结束时，发生在一个时间片结束时，发生时钟中断；时钟中断；4.4 4.4 调度算法（重点）调度算法（重点）4 时间片轮转算法时间片轮转算法(Round Robin)（3）算法思想）算法思想 调度程序据此调度程序据此暂停当前
34、进程的执行暂停当前进程的执行，将其送到，将其送到就绪队就绪队列的末尾列的末尾，并通过上下文切换，并通过上下文切换执行当前的队首进程执行当前的队首进程 进程可以进程可以未使用完一个时间片未使用完一个时间片，就，就出让出让CPU（如阻塞）（如阻塞）4.4 4.4 调度算法（重点）调度算法（重点）4 时间片轮转算法时间片轮转算法(Round Robin)F DCBACPU阻塞阻塞完成完成超时超时4.4 4.4 调度算法（重点）调度算法（重点）4 时间片轮转算法时间片轮转算法(Round Robin)（4）时间片长度的确定时间片长度的确定 1）时间片长度变化的影响时间片长度变化的影响 过长过长退化为退
35、化为FCFS算法，进程在一个时间片内都执行算法，进程在一个时间片内都执行完，响应时间长；完，响应时间长；过短过短用户的一次请求需要多个时间片才能处理完，用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。上下文切换次数增加，响应时间长。4.4 4.4 调度算法（重点）调度算法（重点）4 时间片轮转算法时间片轮转算法(Round Robin)（4）时间片长度的确定）时间片长度的确定 2）对响应时间的要求对响应时间的要求T(响应时间响应时间)=N(进程数目进程数目)*q(时间片时间片)前面四种算法是计算的重点。前面四种算法是计算的重点。4.4 4.4 调度算法（重点）调度算法（
36、重点）影响时间片轮转调度算法对进程响应时间的因素有()。内存容量A时间片值的选取B外存容量C交互进程的数量DIO设备的速度E提交多选题1分下列有关基于时间片的进程调度的叙述中,错误的是()。时间片越短,进程切换的次数越多,系统开销也越大A当前进程的时间片用完后,该进程状态由执行态变为阻塞态B时钟中断发生后,系统会修改当前进程在时间片内的剩余时间C影响时间片大小的主要因素包括响应时间、系统开销和进程数量等。D提交单选题1分 5 多级队列算法多级队列算法(Multiple-level Queue)本算法引入多个就绪队列，通过各队列的区别对待，本算法引入多个就绪队列，通过各队列的区别对待，达到一个综
37、合的调度目标达到一个综合的调度目标4.4 4.4 调度算法（重点）调度算法（重点）5 多级队列算法多级队列算法(Multiple-level Queue)（1）算法思想算法思想 根据作业或进程的性质或类型的不同，将就绪队列再分根据作业或进程的性质或类型的不同，将就绪队列再分为若干个为若干个子队列子队列；每个作业每个作业固定归入一个队列固定归入一个队列;各队列的各队列的不同处理不同处理：不同队列可有不同的优先级、时间：不同队列可有不同的优先级、时间片长度、调度策略等。片长度、调度策略等。4.4 4.4 调度算法（重点）调度算法（重点）5 多级队列算法多级队列算法(Multiple-level Q
38、ueue)4.4 4.4 调度算法（重点）调度算法（重点）6 优先级算法优先级算法 是多级队列算法的改进，平衡各进程对响应时间的要求。是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式。适用于作业调度和进程调度，可分成抢先式和非抢先式。4.4 4.4 调度算法（重点）调度算法（重点）6 优先级算法优先级算法（1）静态优先级静态优先级 1）定义：创建进程时就确定，直到进程终止前都不改变。定义：创建进程时就确定，直到进程终止前都不改变。2）评级依据评级依据 进程类型进程类型（系统进程优先级较高）（系统进程优先级较高）对资源的需求对资源的需求（对（对C
39、PU和内存需求较少的进程，优先级和内存需求较少的进程，优先级较高）较高）用户要求用户要求4.4 4.4 调度算法（重点）调度算法（重点）6 优先级算法优先级算法（2）动态优先级动态优先级 在创建进程时赋予的优先级，在进程运行过程中可以自在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。动改变，以便获得更好的调度性能。4.4 4.4 调度算法（重点）调度算法（重点）6 优先级算法优先级算法（2）动态优先级）动态优先级 优先级变化案例：优先级变化案例：在就绪队列中，在就绪队列中，等待时间等待时间延长则优先级提高，保证延长则优先级提高，保证每个进程都有机会执行；每个进程
40、都有机会执行；进程每进程每执行一个时间片执行一个时间片，就降低其优先级，从而一，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让个进程持续执行时，其优先级降低到出让CPU 4.4 4.4 调度算法（重点）调度算法（重点）6 优先级算法优先级算法（3）动态优先级具体算法）动态优先级具体算法 1）线性优先级调度线性优先级调度（SRR,Selfish Round Robin）是动态优先级算法的一个算法，它通过进程优先级的递增是动态优先级算法的一个算法，它通过进程优先级的递增来改进长执行时间进程的周转时间特征来改进长执行时间进程的周转时间特征4.4 4.4 调度算法（重点）调度算法（重点）6
41、 优先级算法优先级算法（3）动态优先级具体算法）动态优先级具体算法1）线性优先级调度线性优先级调度 算法思想：就绪进程队列分成两个。算法思想：就绪进程队列分成两个。新创建进程队列新创建进程队列：按：按FCFS方式排成；进程优先级方式排成；进程优先级按速率按速率a增加增加享受服务队列享受服务队列：已得到过时间片服务的进程按：已得到过时间片服务的进程按FCFS方式排成；进程优先级按速率方式排成；进程优先级按速率b增加增加4.4 4.4 调度算法（重点）调度算法（重点）6 优先级算法优先级算法（3）动态优先级具体算法动态优先级具体算法 1）线性优先级调度线性优先级调度 算法思想算法思想 新创建进程等
42、待时间的确定：当新创建进程优先级新创建进程等待时间的确定：当新创建进程优先级与享受服务队列中最后一个进程优先级相同时，转与享受服务队列中最后一个进程优先级相同时，转入享受服务队列入享受服务队列4.4 4.4 调度算法（重点）调度算法（重点）6 优先级算法优先级算法（3）动态优先级具体算法）动态优先级具体算法 1）线性优先级调度线性优先级调度4.4 4.4 调度算法（重点）调度算法（重点）F DCBACPU阻塞阻塞完成完成享受服务进程队列享受服务进程队列IJK新创建进程队列新创建进程队列 6 优先级算法优先级算法（3）动态优先级具体算法）动态优先级具体算法abTimePrioritySRR算法的
43、优先级变化算法的优先级变化4.4 4.4 调度算法（重点）调度算法（重点）6 优先级算法优先级算法（4）SRR、FCFS、时间片轮转算法的关系、时间片轮转算法的关系当当ba0时，享受服务队列中永远只有一个进程；时，享受服务队列中永远只有一个进程；SRR算法退化成算法退化成FCFS算法；算法；当当ab=0时，时，SRR算法就是时间片轮转算法。算法就是时间片轮转算法。4.4 4.4 调度算法（重点）调度算法（重点）在采用动态优先权的优先权调度算法中,如果所有进程都具有相同优先权初值,则此时的优先权调度算法实际上和()相同。先来先服务调度算法A短作业优先调度算法B时间片轮转调度算法C长作业优先调度算
44、法D提交单选题1分下列进程调度算法中,()可能会出现进程长期得不到调度的情况。非强占式静态优先权法A强占式静态优先权法B时间片轮转调度算法C非强占式动态优先权法D提交单选题1分 7 多级反馈队列算法多级反馈队列算法 是是时间片轮转算法时间片轮转算法和和优先级算法优先级算法的综合和发展。的综合和发展。（1）优点优点 为提高系统吞吐量和缩短平均周转时间而照顾短进程；为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的为获得较好的I/O设备利用率和缩短响应时间而照顾设备利用率和缩短响应时间而照顾I/O型进程型进程 不必估计进程的执行时间，动态调节不必估计进程的执行时间，动态调节4.4 4.4
45、 调度算法（重点）调度算法（重点）7 7 多级反馈队列多级反馈队列 （2 2）算法思想）算法思想 设置多个就绪队列，分别赋予不同的优先级，如逐级降设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列低，队列1 1的优先级最高。每个队列执行时间片的长度的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍；也不同，规定优先级越低则时间片越长，如逐级加倍；4.4 4.4 调度算法（重点）调度算法（重点）7 7 多级反馈队列多级反馈队列 （2 2）算法思想）算法思想新进程进入内存后，先投入队列新进程进入内存后，先投入队列1 1的末尾，按的末尾，按FCFSFCFS算法
46、算法调度；若在队列调度；若在队列1 1一个时间片未能执行完，则降低投入一个时间片未能执行完，则降低投入到队列到队列2 2的末尾，同样按的末尾，同样按FCFSFCFS算法调度；如此下去，降算法调度；如此下去，降低到最后的队列，则按低到最后的队列，则按“时间片轮转时间片轮转”算法调度直到算法调度直到完成；完成；4.4 4.4 调度算法（重点）调度算法（重点）下列选项中,降低进程优先级的合理时机是()。进程的时间片用完A进程刚完成I/O,进入就绪队列B进程长期处于就绪队列中C进程从就绪状态转为运行态D提交单选题1分7 7 多级反馈队列多级反馈队列 （2 2）算法思想）算法思想 仅当较高优先级的队列为
47、空，才调度较低优先级的队仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。程投入原队列的末尾。4.4 4.4 调度算法（重点）调度算法（重点）8 调度算法性能指标调度算法性能指标（3）FCFS、Round Robin和和SRR周转时间比较周转时间比较长作业时：长作业时：T(FCFS)T(SRR)T(RR)（运行时间（运行时间是主要因素）；是主要因素）；短作业时：短作业时：T(RR)T(SRR)T(
48、FCFS)（等待时间（等待时间是主要因素）是主要因素）。4.4 4.4 调度算法（重点）调度算法（重点）1、假设在批处理环境下有四个作业，已知它们进入系统的时假设在批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间：间、估计运行时间：作业作业进入时间进入时间估计运行时间（分钟）估计运行时间（分钟）JOB18:00120JOB28:5050JOB39:0010JOB49:50204.5 4.5 调度算法应用举例调度算法应用举例要求：要求：应用先来先服务、最短作业优先和最高响应比优先作业应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周调
49、度算法，分别计算出作业的平均周转时间和带权的平均周转时间。转时间。4.5 4.5 调度算法应用举例（考点）调度算法应用举例（考点）答：（答：（1 1）先来先服务算法计算结果先来先服务算法计算结果时间时间8:00 10:00 10:50 11:00 11:20J1120J250J310J4204.5 4.5 调度算法应用举例（考点）调度算法应用举例（考点）（2 2）最短作业优先算法计算结果最短作业优先算法计算结果 作作业业 进进入入时时间间 估估计计运运行行时时间间（分分钟钟）开开始始时时间间 结结束束时时间间 周周转转时时间间（分分钟钟）带带权权周周转转时时间间 JOB1 8：00 120 8
50、：00 10：00 120 1 JOB2 8：50 50 10：30 11：20 150 3 JOB3 9：00 10 10：00 10：10 70 7 JOB4 9：50 20 10：10 10：30 40 2 作作业业平平均均周周转转时时间间 T=95 作作业业带带权权平平均均周周转转时时间间 W=3.25 380 13 时间时间8:00 10:00 10:10 10:30 11:20J1120J250J310J4204.5 4.5 调度算法应用举例（考点）调度算法应用举例（考点）（3）最高响应比算法计算结果最高响应比算法计算结果时间时间8:00 10:00 10:10 11:00 11:
