操作系统_第四章 处理机管理

第四章处理机管理4.1分级调度4.2作业调度算法4.3进程调度算法处理机管理的工作是对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。这里的主要问题是处理机调度算法和调度算法特征分析。4.1引言4.1.1调度的类型(scheduling)4.1.2调度的性能准则4.1.1调度的类型(scheduling)•作业：又称为宏观调度、高级调度。从用户工作流程的角度，一次提交的若干个流程，其中每个程序按照进程调度。时间上通常是分钟、小时或天。•内外存交换：又称为中级调度。从存储器资源的角度。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。指令和数据必须在内存里才能被CPU直接访问。•进程或线程：又称为微观调度、低级调度。从CPU资源的角度，执行的单位。时间上通常是毫秒。因为执行频繁，要求在实现时达到高效率。从处理机调度的对象、时间、功能等不同角度，我们可把处理机调度分成不同类型。1.按照调度的层次AdmitRunningReadySuspendExitReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendNewEventOccursActivateSuspendActivateAdmitSuspend宏观调度微观调度中级调度处理机调度的层次2.按照调度的时间周期•长期(long-term)：将进程投入允许执行进程缓冲池中，或送到退出进程缓冲池中。进程状态：New－Readysuspend,Running－Exit•中期(medium-term)：将进程的部分或全部加载到内存中。进程状态：Ready－Readysuspend,Blocked－Blockedsuspend•短期(short-term)：选择哪个进程在处理机上执行。进程状态：Ready－Running•I/O调度：选择哪个I/O等待进程，使其请求可以被空闲的I/O设备进行处理。3.按照OS的分类•批处理调度－－应用场合：大中型主机集中计算，如工程计算、理论计算（流体力学）•分时调度、实时调度：通常没有专门的作业调度4.1.2调度的性能准则我们可从不同的角度来判断处理机调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的处理机调度算法选择是一个综合的判断结果。•周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待－－批处理系统–平均周转时间T–平均带权周转时间（带权周转时间W是T(周转)/T(CPU执行)〕•响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间－－分时系统•截止时间：开始截止时间和完成截止时间－－实时系统，与周转时间有些相似。•公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。•优先级：可以使关键任务达到更好的指标。1.面向用户的调度性能准则2.面向系统的调度性能准则•吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系－－批处理系统–平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。如：在2小时内完成4个作业，而每个周转时间是1小时，则吞吐量是2个作业/小时•处理机利用率：－－大中型主机•各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配－－大中型主机3.调度算法本身的调度性能准则易于实现执行开销比4.2作业调度算法4.2.1先来先服务4.2.2短作业优先4.2.3最高响应比算法返回所谓作业调度，是指按某种算法把处于后备状态的作业的一个或一批调度到主机上运行。作业调度性能的衡量指标•对于批处理系统，作业调度的原则体现在一个指标——各作业的平均周转时间上。如设i作业的周转时间为Ti=Tci-Tsc其中：Tci为作业的完成时间；Tsc为作业的提交时间则平均周转时间为：T=（∑Ti）/n•平均带权周转时间定义为：W=（∑Ti/tri）/n（其中，tri作业的运行时间。）•一般认为T、W越小，系统对作业的吞吐量越大，系统的性能越高。4.2.1先来先服务(FCFS,FirstComeFirstService)•按照作业提交或进程变为就绪状态的先后次序，分派CPU；•当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。•在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。最简单的算法。这是最简单的调度算法，按先后顺序进行调度。1.FCFS算法2.FCFS的特点•比较有利于长作业，而不利于短作业。•有利于CPU繁忙的作业，而不利于I/O繁忙的作业。实例作业号提交时间运行长度110:002小时210:061小时310:150.25小时表4.2三个作业计算结果作业号开始时间结束时间周转时间110:0012:002.00小时212:0013:002.90小时313:0013:153.00小时4.2.2短作业优先(SJF,ShortestJobFirst)又称为“短进程优先”SPN(ShortestProcessNext)；这是对FCFS算法的改进，其目标是减少平均周转时间。1.SJF算法对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。2.SJF的特点•优点：–比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；–提高系统的吞吐量；•缺点：–对长作业非常不利，可能长时间得不到执行；–未能依据作业的紧迫程度来划分执行的优先级；–难以准确估计作业（进程）的执行时间，从而影响调度性能。表2.4三个作业短作业优先调度结果作业号开始时间结束时间周转时间110:0012:002.00小时212:1513:153.15小时312:0012:152.00小时4.2.3最高响应比算法•这是一种折衷算法，是为了克服上述两种算法的不足而提出来的。它既考虑到作业进入系统的先后次序，又顾及到作业的运行长度。•响应比为：作业等待时间作业估计运行时间RP=1+表4.4四个作业提交与运行情况表作业号提交时间运行长度18:002小时28:300.5小时39:000.1小时49:300.2小时表4.5四个作业计算结果作业号开始时间结束时间周转时间18:0010:002.00小时210:0610:362.1小时310:0010:061.10小时410:3610:481.30小时4.3进程调度完成进程运行态到等待态、就绪态到运行态的转换•4.3.1进程调度的功能•4.3.2进程调度的时机•4.3.3时间片轮转法•4.3.4多级队列反馈法4.3.1进程调度的功能•记录系统中所有进程的执行情况，利用PCB了解各进程的状态和资源需求；•选择占用处理机的进程（与算法有关）；•进行进程上下文切换。4.3.2进程调度的时机•引起进程调度的原因不仅与操作系统的类型有着密切的关系，而且还与下列因素有关：①正在运行的进程运行完毕；②运行中的进程要求I/O；③执行某种原语操作；④一个比正在运行进程优先数更高的进程申请运行（在可剥夺调度方式下）；⑤分配给运行进程的时间片已经用完等。进程调度的方式•进程调度的方式可分为非剥夺式和剥夺式。•剥夺式调度是指当系统按照某种原则发现一个比现运行进程更合适、更应该占用CPU的进程时，系统将强迫处于运行状态的进程将CPU的使用权交给这个更适合的进程。•非剥夺式调度是指一旦某个进程占用了CPU，除非是由于它自身原因自动放弃CPU，否则它将一直运行下去直到完成。4.3.3时间片轮转(RoundRobin)算法本算法主要用于微观调度，说明怎样并发运行即切换的方式；设计目标是提高资源利用率。其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率。1.时间片轮转算法•将系统中所有的就绪进程按照FCFS原则，排成一个队列。•每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。•在一个时间片结束时，发生时钟中断。•调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。•进程可以未使用完一个时间片，就出让CPU（如阻塞）。2.时间片长度的确定•时间片长度变化的影响–过长－退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。–过短－用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。•对响应时间的要求：–T(响应时间)=N(进程数目)*q(时间片)•时间片长度的影响因素：–就绪进程的数目：数目越多，时间片越小（当响应时间一定时）–系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。4.3.4多级反馈队列算法(RoundRobinwithMultipleFeedback)•多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优点：–为提高系统吞吐量和缩短平均周转时间而照顾短进程。–为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。1.多级反馈队列算法•设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍•新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列。如果因I/O中断放弃CPU，则中断完成后回原队列尾。•仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。2.几点说明•I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。•计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。•I/O次数不多，而主要是CPU处理的进程：在I/O完成后，放回原先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。4.3.5优先级法通过为各个进程确定其优先级别的方式对进程进行调度。1、静态优先级法2、动态优先级法静态优先级法进程开始执行之前即确定它们的优先级，其后不能改变。优先级确定原则：1）按进程的类型确定；2）按进程的功能确定。动态优先级法静态优先级法尽管实现非常简单，但是系统效率低，调度性能不高。动态优先级法可以根据进程的不同状态进程优先级的调整。动态优先级调整原则：1）根据进程占有CPU的时间长短；2）根据就绪进程等待CPU的时间长短。小结•调度的类型（如调度单位的不同级别，时间周期，不同的OS），性能准则•作业调度三个算法的原理及应用，调度次序及各种调度指标的计算•进程调度算法的原理