《处理机调度》PPT课件.ppt

操作系统Operating System,北方工业大学计算机系North China University of TechnologyDepartment of Computer 授课教师：宋丽华Email：Tel:88803939 五教1102,为什么要管理处理机?,处理机是计算机中最宝贵的资源，处理机调度策略是否合适直接影响着计算机的性能。在批处理系统用户一旦将作业提交就失去了对作业的控制，用户希望系统的周转时间尽量短。交互式系统中用户以交互方式工作，好象整个计算机都为一个用户工作，这时希望系统的响应时间快。由此可以看出，不同的操作系统类型和用户要求，处理机的管理策略应该有所不同。,衡量调度策略的指标,周转时间一个作业从投入计算机到结束所使用的时间。吞吐量在给定的时间内，一个计算机系统所完成的总的工作量。响应时间从用户向计算机发出指令到计算机将结果返回给用户需要的时间。设备利用率主要指输入输出设备的使用情况。,-小,-大,-短,-高,第四章 处理机调度,4.1 分级调度,4.2 作业调度,4.3 进程调度,4.4 调度算法,4.1 分级调度,操作系统中一个程序运行相关的概念：作业、进程、线程。它们是程序在计算机中不同运行阶段的不同体现，为此应该有不同的调度程序。,程序的各种状态及相应的调度方式,提交状态：一个作业从输入设备进入外存的过程叫做提交状态，这时的作业不能被调度。后备状态：当一个作业的全部都已经进入了输入井，未运行之前叫做后备状态（收容状态）。运行状态：作业调度程序从后备作业中选择一个作业到内存运行，并为它创建进程和分配资源。这些被选中的作业处于执行状态，执行状态的作业并不一定占用处理机，哪个进程占用处理机由进程调度程序决定。这个状态中还包括：就绪状态、执行状态和等待状态。完成状态：当作业运行完毕后，它所占用的资源并未全部释放。,4.1 分级调度,处理机调度分四个级别作业调度（高级）：按一定的原则从作业输入井中选择作业，为其创建进程、分配资源，当作业运行完毕后回收作业占用的资源。交换调度（中级）：按某种策略将处于外存交换区的就绪进程调入内存、把内存中就绪状态或等待状态的进程调出内存。,4.1 分级调度,处理机调度分四个级别进程调度（低级）：按某种策略选择一个就绪进程占用处理机，在确定了占用处理机的进程后，必须进行进程上下文切换，以便为运行进程准备好执行环境。线程调度（微级）：负责各个线程的调度。,第四章 处理机调度,4.1 分级调度,4.2 作业调度,4.3 进程调度,4.4 调度算法,4.2 作业调度,作业调度程序的功能作业调度程序的目标和性能衡量,4.2.1 作业调度程序的功能,记录已经进入系统的各个作业的情况。作业调度要记录作业进入系统时的一些信息，并跟踪作业在运行中的状态变化情况。这些信息记录在作业控制块JCB，它建立和撤消都是由作业调度程序完成的。选择作业。从输入井中选择符合“条件”的作业送到内存的作业缓冲区中，使这些作业的状态由“后备”状态变为“运行”状态。,4.2.1 作业调度程序的功能,为被选中的作业做执行前的准备。建立进程，分配作业运行需要的资源，如内存和外部设备。作业调度程序只能保证该作业具有使用处理机的资格，而不能分配处理机资源。作业运行结束后的善后处理和资源回收。统计作业的运行时间，作业执行状态等信息的输出。撤消该作业的所有进程和该作业的JCB。,作业调度程序的处理流程,例 题,当作业进入完成状态，操作系统（）A 将删除该作业并收回其所占资源，同时输出结果；B收回其所占资源，输出结果，并将该作业的控制块从当前作业队列中删除；C 将收回该作业所占资源并输出结果；D 将输出结果并删除内存中的作业。,B,4.2.2 作业调度算法的目标和性能衡量,调度目标：1）对所有的作业应该是公平合理的。2）应使设备有较高的利用率。3）单位时间内执行尽可能多的作业。4）有快的响应时间。,由于这些目标的相互冲突，任一调度算法要想同时满足上述目标是不可能的。,周转时间=作业完成时间 作业提交时间。Ti=Tei Tsi平均周转时间：注意：一个作业的周转时间说明了它在系统内部停留的时间，应该包括两部分：等待时间和执行时间。Ti=Twi+Tri Twi：是作业由后备状态到执行状态的等待时间，不包括作业进入执行状态后的等待时间。Tri：是作业在执行状态的时间。,4.2.2 作业调度算法的目标和性能衡量,带权周转时间=作业的周转时间 作业执行时间如果有多个作业同时进入系统，则平均带权周转时间：,4.2.2 作业调度算法的目标和性能衡量,一般来说，作业的平均周转时间短，说明作业在系统的时间短，用户等待的时间短，系统的利用率高，所以，应该选择平均周转时间短的作业调度算法。,Wi=Ti/Tri,第四章 处理机调度,4.1 分级调度,4.2 作业调度,4.3 进程调度,4.4 调度算法,4.3 进程调度,进程调度程序的功能进程调度的时机进程调度性能评价,4.3.1 进程调度程序的功能,1）记录和保持系统中所有进程的有关情况和状态特征：由进程调度模块管理PCB表的内容，记录进程状态。2）选择占用处理机的进程：在处理机空闲时，根据一定的原则选择一个进程来运行。3）进行进程上下文切换：上下文切换时首先检查是否可以做切换，然后保存被切换进程的上下文，由调度程序选择一个进程，装载该进程的上下文，控制转向该进程，从刚恢复的程序计数器所指示的指令地址开始执行。,4.3.2 进程调度的时机,引起进程调度的原因有以下7类：一个进程完成其任务时。执行中的进程自己调用阻塞原语，进入等待状态。执行了一次P操作，资源不满足；执行V操作激活了等待队列的进程。执行的进程提出I/O请求后被阻塞。在分时系统中时间片已经用完。执行完系统调用，系统返回用户态之前，由于系统进程结束，需求调度新的进程。在采用可剥夺调度方式的系统中，当具有更高优先级的进程要求处理机时。,【13年考研28题】,下列选项中，会导致用户进程从用户态切换到内核态的操作是()I.整数除以零 II.sin()函数调用 III.read 系统调用 A.仅I、II B.仅I、III C.仅II、III D.I、II和III,B,4.3.2 进程调度的时机,可剥夺方式：在就绪队列中一旦有优先级高于当前执行进程的进程存在便立即发生进程调度，转让处理机。而不可剥夺方式即使在就绪队列存在有优先级高于当前执行进程时，当前进程仍将继续占有处理机，直到该进程自己因调用原语操作或等待I/O而进入阻塞状态，或时间片用完时才重新发生调度让出处理机。,4.3.3 进程调度性能评价,进程调度策略的好坏直接影响作业调度的性能。作业调度性能评价周转时间平均周转时间带权周转时间平均带权周转时间,4.3.3进程调度性能评价,进程调度性能评价定性调度的可靠性简洁性定量CPU的利用率进程在就绪队列中等待时间与执行时间之比,第四章 处理机调度,4.1 分级调度,4.2 作业调度,4.3 进程调度,4.4 调度算法,4.4 调度算法,先来先服务轮转法多级反馈轮转法优先级法最短作业优先法最高响应比优先法,4.4 调度算法,思想：按作业和就绪进程到来的次序进行调度。这种算法优先考虑在系统中等待时间最长的作业，而不管它要求运行时间的长短。优点：算法简单，公平，容易实现缺点：对于短作业或短进程，等待时间长,作业调度算法FCFS（First come first serve）,4.4 调度算法,作业调度算法FCFS,下面是4个作业在系统中从提交、运行的信息。,平均周转时间：T=1.725 平均带权周转时间W=6.875,8,10,10.5,10.6,10,10.5,10.6,10.8,2,2,1.6,1.3,1,4,16,6.5,4.4 调度算法,思想：比较作业缓冲区中的作业预计的运行时间，选择预计时间最短的作业进入运行状态。优点：算法简单，可得到最大系统吞吐率，效率高。缺点：主要问题是对长作业不利，如果系统不断地接收短作业，就会使长作业长时间等待。,短作业优先算法SJF（shortest job first）,4.4 调度算法,短作业优先算法SJF,平均周转时间：T=1.55 平均带权周转时间W=5.15,8,10.3,10,10.1,10,10.8,10.1,10.3,2,2.3,1.1,0.8,1,4.6,11,4,4.4 调度算法,响应比=响应时间/预计执行时间响应时间=等待时间+预计执行时间所以响应比为：1+作业等待时间/预计执行时间思想：当需要从就绪队列中选择进程投入运行时，先计算每个进程的响应比，选择响应比最高的进程运行优点：短作业响应比高，执行时间短；长作业响应比随着等待时间增加而提高，不会过长等待。既照顾了短作业、也考虑到了长作业。缺点：每次调度前计算响应比增加了系统开销。,最高响应比优先HRN（highest response-ratio next）,4.4 调度算法,平均周转时间：T=1.625 W=5.675,最高响应比优先HRN,8,10.1,10,10.6,10,10.6,10.1,10.8,2,2.1,1.1,1.3,1,4.2,11,6.5,4.4 调度算法,算法描述：根据分配给进程的优先数来决定运行进程。算法的核心：是确定进程或作业的优先级静态法：静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。动态法：动态优先权是指，在创建进程时所赋予的优先权可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。,优先级法 HPF（highest priority first）,特点：静态优先级法简单，但缺点是公平性差，可能会造成优先级低的长期等待；动态优先级法资源利用率高，公平性好，缺点是系统开销较大，实现复杂。,4.4 调度算法,静态法作业调度确定优先级原则由用户根据作业的紧急程度输入一个适当的优先级；由系统或操作员根据作业的类型确定；系统根据作业要求的资源确定优先级。进程调度确定优先级原则按照进程的类型确定；将作业的优先级作为它所属进程的优先级。,优先级法 HPF（highest priority first）,4.4 调度算法,动态法优先级确定原则根据进程占有CPU时间长短确定占用的时间越长，下次调度的优先级越低；占用的时间越短，下次调度的优先级越高。根据就绪进程等待CPU的时间长短确定等待时间越长，优先级越高；等待时间越短，优先级越低。,优先级法 HPF（highest priority first）,4.4 调度算法,算法描述：将CPU的处理时间分成固定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。,轮转法 RR（round robin）,优点：具有公平性；易于实现，算法简单；缺点：CPU存在较大额外开销，用于进程切换和调度。,4.4 调度算法,时间片：时间片长度的选择会直接影响系统开销和响应时间。太长，则使每一个进程均能在一个 时间片内完成，RR算法褪化成了FCFS；太短，导致频繁的时间片中断和调度，CPU额外开销大。,轮转法 RR（round robin）,计算表达式：qR/Nmax q：时间片长度；R：系统对响应时间的要求 Nmax：就绪队列要求的最大进程数量,q=1和q=4的进程运行情况,4.4 调度算法,轮转法 RR（round robin）,4.4 调度算法,轮转法 RR（round robin）,4.4 调度算法,算法描述：把就绪队列按照进程到达就绪队列的类型和进程被阻塞时的阻塞原因分成不同的就绪队列，每个队列按FCFS原则排列，各队列之间的进程享有不同的优先级，但同一队列内优先级相同。多级反馈轮转法与优先级法在原理上的区别是，一个进程在它执行结束之前，可能需要反复多次通过反馈循环执行，而不是优先级法中的一次执行。,多级反馈轮转法,特点：复杂，实现困难；是FCFS，RR，HPF的综合应用。,4.4 调度算法,设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍。,多级反馈轮转法,多级反馈队列调度算法,4.4 调度算法,算法的入队原理 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度；当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。,例 题,【09年考研24题】下列进程调度算法中，综合考虑进程等待时间和执行时间的是()A时间片轮转调度算法 B.短进程优先调度算法 C.先来先服务调度算法 D.高响应比优先调度算法【11年考研23题】下列选项中，满足短任务优先且不会发生饥饿现象的是()调度算法 A先来先服务 B高响应比优先 C时间片轮转 D非抢占式短作业优先,D,B,作业调度，交换调度，进程调度，线程调度作业调度的目标:尽量做到公平合理，能执行尽可能多的作业、尽快地响应时间以及高的设备利用率等。任一调度算法要同时满足这些调度目标是不可能的。调度算法：FCFS、SJF、HRN、HPF、RR、多级反馈轮转法等。,小 结,作业,P108 4.6,