1、处理机调度与死锁PPT课件调度策略考虑：调度策略考虑：周转时间周转时间 吞吐率吞吐率响应时间响应时间 设备利用率设备利用率研究的内容有：研究的内容有：作业与进程的关系作业与进程的关系 作业调度策略与算法作业调度策略与算法进程调度策略与算法进程调度策略与算法 处理机调度处理机调度2022-11-262第三章第三章 处理机调度与死锁处理机调度与死锁3.1 处理机调度的层次处理机调度的层次3.2 调度队列模型和调度准则调度队列模型和调度准则3.3 调度算法调度算法3.4 实时调度实时调度3.5 产生死锁的原因和必要条件产生死锁的原因和必要条件3.6 预防死锁的方法预防死锁的方法3.7 死锁的检测与解
2、除死锁的检测与解除2022-11-263作业的定义作业的定义 作业：作业：是指在一次是指在一次应用业务处理过程应用业务处理过程中，从中，从输入输入开始到开始到输出输出结束，用户要求计算机所做的有关该次业务处理的结束，用户要求计算机所做的有关该次业务处理的全部工作。全部工作。用户的观点：用户的观点：在一次业务处理过程中，从输入程序和数在一次业务处理过程中，从输入程序和数据到输出结果的全过程。据到输出结果的全过程。系统的观点（针对作业进行资源分配）：系统的观点（针对作业进行资源分配）：作业由程序及作业由程序及数据（作业体）和作业说明书（作业控制语言）组成。批数据（作业体）和作业说明书（作业控制语言
3、）组成。批处理系统以作业为单位把程序和数据输入内存以便执行。处理系统以作业为单位把程序和数据输入内存以便执行。作业由不同的顺序相连的作业由不同的顺序相连的作业步作业步组成。组成。作业步：作业步：是在一个作业的处理过程中，计算机所做的是在一个作业的处理过程中，计算机所做的相对独相对独立的工作立的工作。2022-11-266 每个作业步运行的结果产生下一个作业步所需要的文件。每个作业步运行的结果产生下一个作业步所需要的文件。一个作业步能否正确地执行，依赖于前一个作业步是否成一个作业步能否正确地执行，依赖于前一个作业步是否成功地完成。功地完成。作业步之间的关系作业步之间的关系2022-11-267作
4、业组织作业组织 作业由作业由程序程序、数据数据和和作业说明书作业说明书三部分组成。三部分组成。程序和数据完成用户所要求的业务处理工作。程序和数据完成用户所要求的业务处理工作。作业说明书则体现用户的控制意图。作业说明书则体现用户的控制意图。用批处理控制方式组织的作业，在作业进入系统之前，程序员用批处理控制方式组织的作业，在作业进入系统之前，程序员除了要准备好源程序和初始数据外，还必须用作业控制语言来书除了要准备好源程序和初始数据外，还必须用作业控制语言来书写一份作业控制说明书，系统通过作业说明书控制文件形式的程写一份作业控制说明书，系统通过作业说明书控制文件形式的程序和数据，使之执行和操作。序和
5、数据，使之执行和操作。在批处理系统中，把一批作业依次放置在相应的输入设备上，在批处理系统中，把一批作业依次放置在相应的输入设备上，在操作系统的控制下，依次将它们输入辅助存储器中，这样就形在操作系统的控制下，依次将它们输入辅助存储器中，这样就形成了一个成了一个作业流作业流，也称输入流。，也称输入流。2022-11-268作业说明书作业说明书 作业说明书作业说明书包括作业基本情况、作业控制、作业资源要求的描包括作业基本情况、作业控制、作业资源要求的描述；它体现用户的控制意图。如：预计运行时间、要求的资源述；它体现用户的控制意图。如：预计运行时间、要求的资源情况、执行优先级等。情况、执行优先级等。作
6、业基本情况描述：作业基本情况描述：用户名、作业名、编程语言、最大处用户名、作业名、编程语言、最大处理时间等；理时间等；作业控制描述：作业控制描述：作业控制方式、作业步的操作顺序、作业作业控制方式、作业步的操作顺序、作业执行出错处理等；执行出错处理等；作业资源要求描述：作业资源要求描述：处理时间、优先级、内存空间、外设处理时间、优先级、内存空间、外设类型和数量、库函数或实用程序等；类型和数量、库函数或实用程序等；2022-11-269作业的建立作业的建立n 建立一个作业必须把该作业所包含的程序和建立一个作业必须把该作业所包含的程序和数据输入到计算机的外部辅助存储设备上，数据输入到计算机的外部辅助
7、存储设备上，而且还要由作业注册程序在系统中为该作业而且还要由作业注册程序在系统中为该作业申请建立起一个相应的作业控制块。申请建立起一个相应的作业控制块。n即作业的建立过程包括两个子过程：即作业的建立过程包括两个子过程：n 作业的输入；作业的输入；n 作业控制块的建立。作业控制块的建立。2022-11-2610JCB JCB 的建立的建立n 在系统把作业信息输入到外存输入井之后，在系统把作业信息输入到外存输入井之后，还需要根据作业说明书中的说明及其它信息还需要根据作业说明书中的说明及其它信息建立作业控制块建立作业控制块(JCB)。只有在获得。只有在获得JCB表表项和足够的输入井空间之后，一个作业
8、才可项和足够的输入井空间之后，一个作业才可能创建成功。能创建成功。n JCB是作业存在的唯一标志。作业进入系是作业存在的唯一标志。作业进入系统时，则为之建立统时，则为之建立JCB，当作业退出系统时，当作业退出系统时，则其则其JCB也被撤消。也被撤消。2022-11-2611作业控制块作业控制块 内容内容：作业名、作业类型、资源要求、当前状态、：作业名、作业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。资源使用情况以及该作业的优先级等。作业类型作业类型：计算型（要求：计算型（要求CPUCPU时间多）、管理型时间多）、管理型（要求输入（要求输入/输出量大）和图形设计型（要求高速图输出
9、量大）和图形设计型（要求高速图形显示）等。形显示）等。资源要求资源要求：该作业估计执行时间、要求最迟完成：该作业估计执行时间、要求最迟完成时间、要求的内存量和外存量、要求的外设类型及时间、要求的内存量和外存量、要求的外设类型及台数以及要求的软件支持工具库函数等。台数以及要求的软件支持工具库函数等。2022-11-2612 资源使用情况资源使用情况：作业进入系统时间、开始：作业进入系统时间、开始执行时间、已执行时间、内存地址、外设台执行时间、已执行时间、内存地址、外设台数等。数等。作业进入系统时间作业进入系统时间：指作业的全部信息进入输入井，：指作业的全部信息进入输入井，作业的状态成为后备状态的
10、时间。作业的状态成为后备状态的时间。开始执行时间开始执行时间：指该作业被调度程序选中，其状态由：指该作业被调度程序选中，其状态由后备状态变为执行状态的时间。后备状态变为执行状态的时间。内存地址内存地址：指分配给该作业的内存区起始地址。：指分配给该作业的内存区起始地址。外设台数外设台数：指分配给该作业的外设实际台数。：指分配给该作业的外设实际台数。优先级优先级：用来决定该作业的调度次序。可：用来决定该作业的调度次序。可以由用户给定，也可以由系统动态计算产生以由用户给定，也可以由系统动态计算产生作业名作业名作业类型作业类型资源要求资源要求资源使用情况资源使用情况 优先级优先级当前状态当前状态其它其
11、它作业控制块作业控制块2022-11-2613作业的状态作业的状态作业从提交给系统直到它完成后离开系统前的整个活动过程，作业从提交给系统直到它完成后离开系统前的整个活动过程，要经历四种不同状态：要经历四种不同状态：提交状态提交状态：一个作业在其处于从输入设备进入外部存储设备：一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态的过程称为提交状态后备状态（收容状态）后备状态（收容状态）：输入管理系统不断地将作业输入到：输入管理系统不断地将作业输入到外存对应部分（或称输入井），如果一个作业的全部信息已全外存对应部分（或称输入井），如果一个作业的全部信息已全部输入到输入井，在它还没有被调度去
12、执行前，该作业处于后部输入到输入井，在它还没有被调度去执行前，该作业处于后备状态。备状态。运行状态运行状态：作业一旦被作业调度程序选中而被送入主存中投：作业一旦被作业调度程序选中而被送入主存中投入运行，作业就处于执行状态。入运行，作业就处于执行状态。完成状态完成状态：作业运行完毕，但它所占用的资源尚未被系统全：作业运行完毕，但它所占用的资源尚未被系统全部回收时，该作业处于完成状态部回收时，该作业处于完成状态2022-11-2614作业状态及其转换作业状态及其转换数据数据提交状态提交状态完成状态完成状态后备状态后备状态执行状态执行状态作业控制进程作业控制进程 输入设备输入设备数据数据源程序源程序
13、输出设备输出设备作业说作业说明书明书输输入入井井运行运行等待等待就绪就绪输输出出井井输输入入程程序序作作业业调调度度2022-11-2615n作业是用户向计算机提交任务的任务实体。作业是用户向计算机提交任务的任务实体。n进程是计算机为了完成用户任务实体而设进程是计算机为了完成用户任务实体而设置的执行实体。置的执行实体。n计算机要完成一个任务实体，必须要有一计算机要完成一个任务实体，必须要有一个以上的执行实体，因此一个作业总是由个以上的执行实体，因此一个作业总是由一个以上的多个进程组成。一个以上的多个进程组成。作业与进程的关系作业与进程的关系2022-11-2616作业、作业步、进程的关系作业、
14、作业步、进程的关系用户作业作业步进程作业步进程线程线程由用户创建由用户创建由用户指定由用户指定由系统创建由系统创建2022-11-2617n也称为也称为作业调度作业调度、长程调度长程调度（Long-Term SchedulingLong-Term Scheduling）或或宏观调度宏观调度。n根据某种根据某种算法对外存输入井上的大量后备作业进行选算法对外存输入井上的大量后备作业进行选择调入内存，择调入内存，并为它们创建进程、分配必要的资源，再并为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行。将新创建的进程排在就绪队列上，准备执行。n 一般在一般在批处理系统批处理系统中
15、有作业调度。而在分时系统中，中有作业调度。而在分时系统中，为了及时响应，用户通过键盘输入的命令或数据都是直为了及时响应，用户通过键盘输入的命令或数据都是直接送入内存，因此无需配置作业调度机制，实时系统亦接送入内存，因此无需配置作业调度机制，实时系统亦然。然。高级调度高级调度2022-11-2618 高级调度高级调度n执行作业调度时应决定：执行作业调度时应决定：n接纳多少个作业？接纳多少个作业？n接纳哪些作业？接纳哪些作业？取决于多道程序度。取决于多道程序度。取决于所采用的调度算法，如先来先服务取决于所采用的调度算法，如先来先服务调度算法、短作业优先调度算法、最高响调度算法、短作业优先调度算法、
16、最高响应比法等。应比法等。2022-11-2619作业调度功能作业调度功能 1:1:记录系统中各作业的状况记录系统中各作业的状况 2 2：按某种算法从：按某种算法从后备队列后备队列中挑选一个或一批中挑选一个或一批作业调入作业调入内存内存，让它们投入执行。，让它们投入执行。3 3：为被选中作业做好执行前的准备工作。：为被选中作业做好执行前的准备工作。4 4：在作业执行结束时做善后处理工作：在作业执行结束时做善后处理工作2022-11-2620 按照某种调度算法从后备作业队列中选取作业。按照某种调度算法从后备作业队列中选取作业。为被选取的作业分配内存和外设资源（当系统为动态分配外设时，为被选取的作
17、业分配内存和外设资源（当系统为动态分配外设时，作业所申请的外设只作为调度的参考因素）。因此要用到内存分配程作业所申请的外设只作为调度的参考因素）。因此要用到内存分配程序和外设分配程序。序和外设分配程序。为选中的作业建立相应的进程。为选中的作业建立相应的进程。为作业开始运行做好一切准备工作。如构造和读写作业运行时所为作业开始运行做好一切准备工作。如构造和读写作业运行时所需要的有关表格及建立负责其运行控制的作业运行控制程序。需要的有关表格及建立负责其运行控制的作业运行控制程序。在作业运行完毕或运行过程中因某种原因需要撤离时，作业调度在作业运行完毕或运行过程中因某种原因需要撤离时，作业调度程序还要完
18、成作业的善后处理工作，如输出作业管理信息（执行时程序还要完成作业的善后处理工作，如输出作业管理信息（执行时间），收回分配给该作业的全部资源，撤销与该作业有关的全部进程间），收回分配给该作业的全部资源，撤销与该作业有关的全部进程和该作业的作业控制块等和该作业的作业控制块等作业调度应完成如下几方面的工作作业调度应完成如下几方面的工作2022-11-2621作业从后备状态到执行状态作业从后备状态到执行状态后备作业队列空按调度算法从作业中选出一作业调用存储、设备管理程序，审核资源要求资源要求能满足？放弃该作业否分配资源调用进程管理程序建立进程进程调度否是出口2022-11-2622作业从执行状态到完成
19、状态作业从执行状态到完成状态撤销该作业的所有进程及作业的JCB调用存储管理，设备管理回收分配给该作业的全部资源调用会计程序，计算该作业的执行费用调度下一个作业2022-11-2623作业调度目标与性能衡量作业调度目标与性能衡量1)1)调度目标调度目标 对所有作业应该是公平合理对所有作业应该是公平合理 应使设备有高的利用率应使设备有高的利用率 执行尽可能多的作业执行尽可能多的作业 有快的响应时间有快的响应时间2022-11-26242 2）在批处理系统中衡量作业调度算法优劣的性能量）在批处理系统中衡量作业调度算法优劣的性能量度度周转时间周转时间 其中某一作业进入其中某一作业进入“输入井输入井”的
20、时间为的时间为Tsi，它被选中，它被选中执行，运行结束时的时间为执行，运行结束时的时间为Tei n 个作业个作业平均周转时间平均周转时间为：为：niiTnT11ieisiTTT作业调度目标与性能衡量作业调度目标与性能衡量2022-11-2625作业调度目标与性能衡量作业调度目标与性能衡量 一个作业的周转时间说明了该作业在系统内停留的一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：一是等待时间；二为执行时间，时间，包含两部分：一是等待时间；二为执行时间，即即-带权周转时间带权周转时间 平均带权周转时间平均带权周转时间：iwiriTTT/iiriWTT11niiWWn2022-11-
21、2626n又称又称中程调度中程调度(Medium-Term Scheduling)、交换调交换调度度。n引入中级调度的目的是为了提高内存的利用率和系引入中级调度的目的是为了提高内存的利用率和系统吞吐量。统吞吐量。n将目前不在运行态的进程，包括其数据，从内存交将目前不在运行态的进程，包括其数据，从内存交换到外存（此时进程的状态为挂起状态），将新进换到外存（此时进程的状态为挂起状态），将新进程的代码、数据、栈等交换入内存。程的代码、数据、栈等交换入内存。中级调度中级调度2022-11-2627n也称也称微观调度微观调度、进程调度进程调度或或短程调度短程调度（Short-Term Short-Ter
22、m SchedulingScheduling）。）。n用来决定就绪队列中的哪个进程应获得处理机，再由用来决定就绪队列中的哪个进程应获得处理机，再由分派程序执行把处理机分配给该进程的具体操作。分派程序执行把处理机分配给该进程的具体操作。n从处理机资源分配的角度来看，处理机需要经常从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态。由于低级调度选择就绪进程或线程进入运行状态。由于低级调度算法的频繁使用，要求在实现时做到高效（算法不算法的频繁使用，要求在实现时做到高效（算法不宜复杂）宜复杂）n任何任何OSOS都必须配置进程调度。都必须配置进程调度。低级调度低级调度2022-11
23、-2628进程调度的两种方式进程调度的两种方式n非抢占式非抢占式(Non-preemptive Mode)：分派程序一旦把处分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一完成或发生某事件而阻塞时，才把处理机分配给另一个进程。个进程。n抢占方式抢占方式(Preemptive Mode)：当一个进程正在运行时，当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。将之分配给其它进程。n抢占原则抢占原则：优先权原则
24、、短作业（进程）优先原：优先权原则、短作业（进程）优先原则、时间片原则。则、时间片原则。2022-11-2629WHAT：按什么原则分配：按什么原则分配CPU 调度算法调度算法WHEN：何时分配：何时分配CPU 调度的时机调度的时机HOW：如何分配如何分配CPU CPU调度过程（进程的上下文切换）调度过程（进程的上下文切换）进程调度要解决的问题进程调度要解决的问题2022-11-2630进程调度的功能进程调度的功能1 1、记录系统中所有进程的执行情况、记录系统中所有进程的执行情况 作为进程调度的准备，进程管理模块必须将系统中各进程作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状
25、态特征记录在各进程的的执行情况和状态特征记录在各进程的PCBPCB表中。并且将各进表中。并且将各进程的程的PCBPCB表排成相应的队列并进行动态队列转接。表排成相应的队列并进行动态队列转接。2 2、选择占有处理机的进程、选择占有处理机的进程 进程调度的主要功能是按照一定的策略选择一个处于就绪进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。状态的进程，使其获得处理机执行。3 3、进行进程上下文切换、进行进程上下文切换 一个进程的执行是在其上下文中执行的。当正在执行的进一个进程的执行是在其上下文中执行的。当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下
26、文切换，程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。以使另一个进程得以执行。2022-11-2631 一个进程运行完毕，或因某种错误而终止运行一个进程运行完毕，或因某种错误而终止运行 当一个进程在运行时变为等待状态（等待当一个进程在运行时变为等待状态（等待I/O）分时系统中时间片到分时系统中时间片到 在进程通信中，执行中的进程执行了某种原语操作（在进程通信中，执行中的进程执行了某种原语操作（P操操作，阻塞原语）作，阻塞原语）在执行完系统调用，系统程序返回用户进程时，可认为在执行完系统调用，系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户
27、进程执行。系统进程执行完毕，从而可调度选择一新的用户进程执行。当有一个优先级更高的进程就绪（可抢占式）当有一个优先级更高的进程就绪（可抢占式）例：新创建一个进程；一个等待进程变成就绪例：新创建一个进程；一个等待进程变成就绪进程调度的时机进程调度的时机2022-11-2632AdmitRunningReadySuspendExitReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendNewEventOccursActivateSuspendActivateAdmitSuspend宏观调度微观调度中级调
28、度处理机调度的层次处理机调度的层次2022-11-2633调度队列模型调度队列模型 仅有进程调度的调度队列模型仅有进程调度的调度队列模型主要适用于分时系统。主要适用于分时系统。CPU就就 绪绪 队队 列列阻阻 塞塞 队队 列列时间片完时间片完进程调度进程调度等待事件等待事件进程完成进程完成交互用户交互用户事事件件出出现现FIFO FIFO 队列队列2022-11-2634 具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型 适用于批处理操作系统适用于批处理操作系统 进程完成CPU就 绪 队 列阻 塞 队 列时间片完进程调度进程调度等待事件1作业作业调度调度事件1出现阻 塞 队 列
29、等待事件n事件n出现后后 备备队队 列列调度队列模型调度队列模型优先权队列优先权队列多个阻多个阻塞队列塞队列2022-11-2635调度队列模型调度队列模型 同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型2022-11-2636选择调度方式和调度算法的准则选择调度方式和调度算法的准则n面向用户的准则面向用户的准则周转时间短周转时间短（批处理系统）（批处理系统）响应时间快响应时间快（分时系统）（分时系统）响应时间是从用户通过键盘提交一个请求开始，直至系统响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。首次产生响应为止的时间。截止时间的保证截止时间的保证（实
30、时系统）（实时系统）截止时间是指某任务必须开始执行的最迟时间，或必须完截止时间是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。成的最迟时间。优先权准则优先权准则（批处理、分时和实时系统）（批处理、分时和实时系统）2022-11-2637选择调度方式和调度算法的准则选择调度方式和调度算法的准则n面向系统的准则面向系统的准则系统吞吐量高系统吞吐量高（批处理系统）（批处理系统）吞吐量指在单位时间内系统所完成的作业数。吞吐量指在单位时间内系统所完成的作业数。处理机利用率好处理机利用率好各类资源的平衡利用各类资源的平衡利用公平公平 2022-11-26383.3 3.3 调度算法调度算法 现有的
31、多种调度算法中，有的算法适用于作业调度，有的现有的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。算法适用于进程调度，有的两者都适应。1 1先来先服务调度算法先来先服务调度算法(FCFS(FCFS：First Come First Serve)First Come First Serve)n应用范围与含义应用范围与含义 作业调度：作业调度：选择一个或多个最先进入选择一个或多个最先进入后备队列的作业后备队列的作业，将它们将它们调入内存调入内存，为它们分配资源、创建进程，并放，为它们分配资源、创建进程，并放入就绪队列。入就绪队列。进程调度：进程调度：按照进程就绪的按
32、照进程就绪的先后次序先后次序来调度进程，为来调度进程，为之之分配处理机分配处理机。当前作业或进程占用当前作业或进程占用CPUCPU，直到执行完或阻塞直到执行完或阻塞，才出，才出让让CPUCPU（非抢占方式）。非抢占方式）。2022-11-2639先来先服务调度算法先来先服务调度算法 在作业或进程在作业或进程唤醒后唤醒后（如（如I/OI/O完成），并不立即恢复完成），并不立即恢复执行，通常等到当前作业或进程出让执行，通常等到当前作业或进程出让CPUCPU。最简单的算法最简单的算法。特点特点 比较有利于长作业，而不利于短作业。比较有利于长作业，而不利于短作业。有利于有利于CPUCPU繁忙的作业，而
33、不利于繁忙的作业，而不利于I/OI/O繁忙的作业。繁忙的作业。例例1：在单道环境下，某批处理系统有四道作业，已知它：在单道环境下，某批处理系统有四道作业，已知它们的进入系统的时刻、估计运算时间如下：们的进入系统的时刻、估计运算时间如下：2022-11-2640先来先服务调度算法先来先服务调度算法作业作业进入时刻进入时刻(h)运行时间运行时间(h)12348.008.509.009.502.000.500.100.20用用FCFSFCFS算法计算作业的运行情况、平均周转时间和平均算法计算作业的运行情况、平均周转时间和平均带权周转时间带权周转时间2022-11-2641例例1 1：作业作业进入时刻
34、进入时刻运行时间运行时间开始时刻开始时刻 完成时刻完成时刻 周转时间周转时间 带权周转带权周转12348.008.509.009.502.000.500.100.208.0010.0010.5010.6010.0010.5010.6010.802.002.001.601.301.004.0016.006.50平均周转时间平均周转时间T1.725（h）平均带权周转时间平均带权周转时间W6.875（h）2022-11-2642作业名作业名 进入时间进入时间 运行时间（分）运行时间（分）需内存量需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36
35、24 10 E 8:42 12 20 有用户空间有用户空间100KB，并规定作业相应程序装入内存，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用连续区域，并不能被移动，作业与进程均采用FCFS算法算法例例2 2：2022-11-2643名名装入内装入内存时间存时间开始时开始时间间结束时结束时间间周转时周转时间间带权周带权周转时间转时间A8:068:068:484242/42B8:188:489:186060/30D8:369:189:426666/24C9:189:4210:069696/24E9:1810:0610:189696/1215K60K10K15K100K作业名
36、 进入时间 运行时间（分）需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 1220T=72W=3.552022-11-26442 2 时间片轮转算法时间片轮转算法(RRRound Robin)(RRRound Robin)n 把把CPU划分成若干时间片。划分成若干时间片。将系统中所有的就绪进程按照将系统中所有的就绪进程按照FCFSFCFS原则，排成一个原则，排成一个队队列列。每次调度时将每次调度时将CPUCPU分派给分派给队首进程队首进程，让其，让其执行一个时间执行一个时间片片。时间片的。时间片的长度长度从几个
37、从几个msms到几百到几百msms。在一个时间片结束时，发生在一个时间片结束时，发生时钟中断时钟中断。调度程序据此调度程序据此暂停当前进程的执行暂停当前进程的执行，将其送到，将其送到就绪队就绪队列的末尾列的末尾，并通过上下文切换，并通过上下文切换执行当前的队首进程执行当前的队首进程。进程可以进程可以未使用完一个时间片未使用完一个时间片，就，就出让出让CPUCPU（如阻塞）。如阻塞）。2022-11-2645时间片长度的确定时间片长度的确定 时间片轮转策略特别适合于时间片轮转策略特别适合于分时系统分时系统中使用中使用 在轮转法中，时间片长度的选取非常重要，时间在轮转法中，时间片长度的选取非常重要
38、，时间片长度的选择会直接影响系统开销和响应时间片长度的选择会直接影响系统开销和响应时间 过长过长 退化为退化为FCFSFCFS算法，进程在一个时间片内都执行完，算法，进程在一个时间片内都执行完，响应时间长。响应时间长。过短过短 用户的一次请求需要多个时间片才能处理完，上用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，系统开销大。下文切换次数增加，系统开销大。最佳的时间片量值应能使分时用户得到好的响应最佳的时间片量值应能使分时用户得到好的响应时间时间2022-11-2646 时间片长度时间片长度 S SR/R/NmaxNmax R R：响应时间响应时间 NmaxNmax：最大进程数最
39、大进程数 时间片长度的影响因素：时间片长度的影响因素：就绪进程的数目：数目越多，时间片越小（当响应时间就绪进程的数目：数目越多，时间片越小（当响应时间一定时）一定时）系统的处理能力：通常应当让用户输入能在一个时间片系统的处理能力：通常应当让用户输入能在一个时间片内能处理完，否则会使响应时间，平均周转时间和平均带内能处理完，否则会使响应时间，平均周转时间和平均带权周转时间延长。权周转时间延长。时间片长度的确定时间片长度的确定2022-11-2647n设有设有5个任务个任务A、B、C、D、E，它们几乎同时到达，它们几乎同时到达，预计它们的运行时间为预计它们的运行时间为10、6、2、4、8min。若
40、采若采用时间片为用时间片为2min的时间片轮转调度算法，则各个任的时间片轮转调度算法，则各个任务的执行情况是：务的执行情况是：第一轮：（第一轮：（A A、B B、C C、D D、E E）10min10min 第二轮：（第二轮：（A A、B B、D D、E E）8min8min 第三轮：（第三轮：（A A、B B、E E）6min6min 第四轮：（第四轮：（A A、E E）4min4min 第五轮：（第五轮：（A A）2min2min例：例：2022-11-2648例：例：n它们的周转时间为：它们的周转时间为：TA30min，TB22min，TC6min，TD16min、TE28min所以进程
41、的平均周转时间为：所以进程的平均周转时间为：T（302261628）/520.4minn从上面的计算中，可以看出从上面的计算中，可以看出A的周转时间最长，假的周转时间最长，假设设A第一轮从第一轮从0分钟开始，则第二轮从分钟开始，则第二轮从10分钟开始，分钟开始，第三轮从第三轮从18分钟开始，第四轮从分钟开始，第四轮从24分钟开始，第五分钟开始，第五轮从轮从28分钟开始，一共占用分钟开始，一共占用5轮的时间片。轮的时间片。2022-11-26493 3 多级反馈轮转法多级反馈轮转法(round robin with multiple feedback)系统中设置系统中设置多个就绪队列多个就绪队列
42、每个就绪队列赋予不同的每个就绪队列赋予不同的优先级和优先级和时间片，第一个队列的优先时间片，第一个队列的优先级最高，时间片最小，随着队列优先级的降低，时间片加大级最高，时间片最小，随着队列优先级的降低，时间片加大各个队列按照各个队列按照先进先出原则先进先出原则排队等待调度排队等待调度,第第n n级队列（最低一级队列（最低一级）中的进程采用级）中的进程采用时间片轮转时间片轮转算法进行调度。算法进行调度。一个新进程就绪后进入一个新进程就绪后进入第一级队列第一级队列末尾末尾进程由于等待而放弃进程由于等待而放弃CPUCPU后，进入等待队列，一旦等待的事件后，进入等待队列，一旦等待的事件发生，则回到原来
43、的就绪队列发生，则回到原来的就绪队列当有一个优先级更高的进程就绪时，可以抢占当有一个优先级更高的进程就绪时，可以抢占CPUCPU，被抢占进被抢占进程回到原来一级就绪队列末尾程回到原来一级就绪队列末尾当第一级队列空时，就去调度第二级队列，如此类推当第一级队列空时，就去调度第二级队列，如此类推当时间片到后，进程放弃当时间片到后，进程放弃CPUCPU，回到下一级队列末尾回到下一级队列末尾2022-11-26503 3 多级反馈轮转法多级反馈轮转法(round robin with multiple feedback)就绪队列 1就绪队列 2就绪队列 3就绪队列 nS1S2S3至CPU至CPU至CPU
44、至CPU时间片：S1S2a0时，享受服务队列中永远只有一个进时，享受服务队列中永远只有一个进程；程；SRR算法退化成算法退化成FCFS算法；算法；当当ab=0时，时，SRR算法就是时间片轮转算法；算法就是时间片轮转算法；事实上，线性优先级调度策略是一种介于轮事实上，线性优先级调度策略是一种介于轮转法和转法和FCFSFCFS方式之间的调度策略。方式之间的调度策略。2022-11-26615 5 最短作业优先法最短作业优先法(SJF,Shortest Job First)又称为又称为“短进程优先短进程优先”(SPJ(SPJ，Shortest Process Shortest Process Fir
45、st)First)；这是对这是对FCFSFCFS算法的改进，其目标是减少平算法的改进，其目标是减少平均周转时间。均周转时间。对对预计执行时间预计执行时间短的作业（进程）优先分派处理短的作业（进程）优先分派处理机。通常后来的短作业机。通常后来的短作业不抢先不抢先正在执行的作业。正在执行的作业。2022-11-2662SJFSJF的特点的特点n优点：优点：比比FCFS改善改善平均周转时间平均周转时间和和平均带权周转时间平均带权周转时间，缩短作业的等待时间；缩短作业的等待时间；提高系统的提高系统的吞吐量吞吐量；n缺点：缺点：对长作业非常不利对长作业非常不利，可能长时间得不到执行；，可能长时间得不到执
46、行；未能依据作业的未能依据作业的紧迫程度紧迫程度来划分执行的优先级；来划分执行的优先级；难以准确估计作业（进程）的执行时间难以准确估计作业（进程）的执行时间，从而影响，从而影响调度性能。调度性能。2022-11-2663作业名作业名提交时间提交时间运行时间运行时间P110.1时时0.3小时小时P210.3时时0.5小时小时P310.5时时0.4小时小时P410.6时时0.3小时小时P510.7时时0.2小时小时设有设有5道作业，道作业，它们的提交时它们的提交时间和运行时间间和运行时间如表如表 例例1 12022-11-2664作业名作业名提交时间提交时间运行时间运行时间开始运行时间开始运行时间
47、完成时间完成时间P110.1时时0.3小时小时10.1小时小时10.4小时小时P210.3时时0.5小时小时10.4小时小时10.9小时小时P310.5时时0.4小时小时11.4小时小时11.8小时小时P410.6时时0.3小时小时11.1小时小时11.4小时小时P510.7时时0.2小时小时10.9小时小时11.1小时小时n执行的顺序为：执行的顺序为：P1-P2-P5-P4-P3P1-P2-P5-P4-P3nT0.68小时小时 例例1 12022-11-2665例例2 2作业名 进入时间 运行时间（分）需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50
48、 D 8:36 24 10 E 8:42 12 20 有用户空间有用户空间100KB，并规定作业相应程序装入内存，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用连续区域，并不能被移动，作业与进程均采用SJF算算法法2022-11-2666作业名 进入时间 运行时间（分）需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 1220名装入内存时间开始时间结束时间周转时间带权周转时间A8:068:068:484242/42D8:368:489:123636/24E9:129:129:244242/12
49、B8:189:249:549696/30C9:429:5410:18108108/24T=64.8W=2.7415K60K10K15K100K2022-11-26676 6 高响应比优先调度算法高响应比优先调度算法（HRN：Highest Response-Ratio Next）响应比响应比R=作业周转时间作业周转时间/作业执行时间作业执行时间 =（作业执行时间（作业执行时间+作业等待时间）作业等待时间）/作业执行时间作业执行时间 =1+（作业等待时间（作业等待时间/作业执行时间）作业执行时间）=1+W/T是是FCFSFCFS和和SJFSJF的折衷的折衷2022-11-26686 6 高响应比
50、优先调度算法高响应比优先调度算法（HRN：Highest Response-Ratio Next）响应比响应比R=1+（作业等待时间（作业等待时间/作业执行时间）作业执行时间）如作业等待时间相同，则执行时间越短，响如作业等待时间相同，则执行时间越短，响应比越高，有利于短作业。应比越高，有利于短作业。对于长作业，随等待时间增加，响应比增高，对于长作业，随等待时间增加，响应比增高，最后同样可获得处理机。最后同样可获得处理机。如执行时间相同，等待时间越长，响应比越如执行时间相同，等待时间越长，响应比越高，实现的是先来先服务。高，实现的是先来先服务。2022-11-2669例例作业名作业名提交时间提交
