第四章_处理机调度(1)

第四章处理机调度4.1调度的类型与模型4.2调度算法4.3调度算法性能分析4.4实时调度4.5多处理机调度4.6调度举例4.7死锁处理机管理的工作是对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。这里的主要问题是处理机调度算法和调度算法特征分析。4.1调度的类型与模型4.1.1作业的状态及其转换4.1.2调度的类型(scheduling)4.1.3调度队列模型4.1.4选择调度方式和算法的若干准则返回4.1.1作业状态及其转换4.1.2调度的类型(scheduling)作业：又称为宏观调度、高级调度。从用户工作流程的角度，一次提交的若干个流程，其中每个程序按照进程调度。时间上通常是分钟、小时或天。内外存交换：又称为中级调度。从存储器资源的角度。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。指令和数据必须在内存里才能被CPU直接访问。进程或线程：又称为微观调度、低级调度。从CPU资源的角度，执行的单位。时间上通常是毫秒。因为执行频繁，要求在实现时达到高效率。从处理机调度的对象、时间、功能等不同角度，我们可把处理机调度分成不同类型。1.按照调度的层次AdmitRunningReadySuspendExitReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendNewEventOccursActivateSuspendActivateAdmitSuspend宏观调度微观调度中级调度处理机调度的层次高级调度/作业调度功能记录系统中作业状况通过JCB表从后备作业队列中选出部分作业为其建立进程，分配资源执行完毕，处理善后作业名作业类型资源要求资源使用情况优先级(数)当前状态其他需解决问题接纳多少作业接纳哪些作业低级调度/进程调度功能：调度程序(dispatcher)记录所有进程的运行状况（静态和动态）当进程出让CPU或调度程序剥夺执行状态进程占用的CPU时，选择适当的进程分派CPU完成上下文切换进程的上下文切换过程：觉得是否做上下文切换或是否允许做上下文切换保存当前进程A的上下文，恢复进程B的上下文（CPU寄存器和一些表格的当前指针）用户态执行进程B代码性能评价：定形（可靠性，简洁性）；定量低级调度方式采用方式：非抢占式和抢占式非抢占式优点：实现简单，开销小缺点：难满足紧急任务要求抢占式时间片原则优先权原则短作业优先原则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.3调度队列模型仅有进程调度的调度队列模型就绪队列阻塞队列交互用户CPU进程调度等待事件事件出现进程完成具有高级和低级调度的调度队列模型就绪队列阻塞队列1作业调度CPU进程调度等待事件事件出现进程完成后备队列阻塞队列2阻塞队列n…………同时具有三级调度的调度队列模型就绪队列就绪挂起作业调度CPU进程调度等待事件事件出现进程完成后备队列阻塞挂起阻塞队列挂起事件出现中级调度4.1.4调度的目标与性能衡量我们可从不同的角度来判断处理机调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的处理机调度算法选择是一个综合的判断结果。周转时间：作业从提交到完成（得到结果）所经历的时间。包括：在收容队列中等待，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时间片轮转算法4.2.4优先级算法4.2.5多级队列算法4.2.6多级反馈队列算法返回通常将作业或进程归入各种就绪或阻塞队列。有的算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。4.2.1先来先服务(FCFS,FirstComeFirstService)按照作业提交或进程变为就绪状态的先后次序，分派CPU；当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。最简单的算法。这是最简单的调度算法，按先后顺序进行调度。1.FCFS算法2.FCFS的特点比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。4.2.2短作业优先(SJF,ShortestJobFirst)又称为“短进程优先”SPN(ShortestProcessNext)；这是对FCFS算法的改进，其目标是减少平均周转时间。1.SJF算法对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业。2.SJF的特点优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；缺点：对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。3.SJF的变型最高响应比优先HRRN(HighestResponseRatioNext)响应比R=(等待时间+要求执行时间)/要求执行时间是FCFS和SJF的折衷最短剩余时间优先SRT(ShortestRemainingTime)允许比当前进程剩余时间更短的进程来抢占4.2.3时间片轮转(RoundRobin)算法前两种算法主要用于宏观调度，说明怎样选择一个进程或作业开始运行，开始运行后的作法都相同，即运行到结束或阻塞，阻塞结束时等待当前进程放弃CPU。本算法主要用于微观调度，说明怎样并发运行，即切换的方式；设计目标是提高资源利用率。其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率；1.时间片轮转算法将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。2.时间片长度的确定时间片长度变化的影响过长－退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。过短－用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。对响应时间的要求：T(响应时间)=N(进程数目)*q(时间片)时间片长度的影响因素：就绪进程的数目：数目越多，时间片越小（当响应时间一定时）系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。4.2.4多级队列算法(Multiple-levelQueue)根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列。每个作业固定归入一个队列。各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等。如：系统进程、用户交互进程、批处理进程等。本算法引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标；4.2.5优先级算法(PriorityScheduling)4.2.5.1静态优先级4.2.5.2动态优先级4.2.5.3线性优先级调度算法（SRR,SelfishRoundRobin）本算法是多级队列算法的改进，平衡各进程对响应时间的要求。适用于作业调度和进程调度，可分成抢先式和非抢先式；4.2.5.1静态优先级依据：进程类型（系统进程优先级较高）对资源的需求（对CPU和内存需求较少的进程，优先级较高）用户要求（紧迫程度和付费多少）创建进程时就确定，直到进程终止前都不改变。通常是一个整数。4.2.5.2动态优先级在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。如：4.2.5.3线性优先级调度算法（SRR,SelfishRoundRobin）就绪进程队列分成两个：新创建进程队列：按FCFS方式排成；进程优先级按速率a增加；享受服务队列：已得到过时间片服务的进程按FCFS方式排成；进程优先级按速率b增加；新创建进程等待时间的确定：当新创建进程优先级与享受服务队列中最后一个进程优先级相同时，转入享受服务队列；本算法是优先级算法的一个实例，它通过进程优先级的递增来改进长执行时间进程的周转时间特征。1.SRR算法abTimePrioritySRR算法的优先级变化2.SRR算法与FCFS算法和时间片轮转算法的关系当ba0时，享受服务队列中永远只有一个进程；SRR算法退化成FCFS算法；当ab=0时，SRR算法就是时间片轮转算法；4.2.6多级反馈队列(轮转)算法(RoundRobinwithMultipleFeedback)多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优点：为提高系统吞吐量和缩短平均周转时间而照顾短进程为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程不必估计进程的执行时间，动态调节1.多级反馈队列算法设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按时间片轮转算法调度直到完成。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。2.几点说明I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。I