《进程调度培训课件》由会员分享，可在线阅读，更多相关《进程调度培训课件（50页珍藏版）》请在金锄头文库上搜索。
1、处理机调度（CPU调度）,(1)起因(2)调度范围与调度模型(3)调度标准(4)调度方式与调度算法(5)性能分析(6)后果（饥饿，死锁）及解决,处理机调度（CPU调度）,关键要解决的问题WHAT：按什么原则分配CPU进程调度算法WHEN：何时分配CPU进程调度的时机HOW：如何分配CPUCPU调度过程（进程的上下文切换）,处理机调度的三个层次,处理机是计算机系统中的重要资源处理机调度算法对整个计算机系统的综合性能指标有重要影响可把处理机调度分成三个层次：高级调度中级调度低级调度,高级调度也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天中级调度涉及进程在内外存间的交换，从存储器资源
2、管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效,处理机调度的三个层次（续）,1.处理机调度算法,（1）处理机调度处理机调度的任务是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程,（2）调度标准确定算法的原则,用户希望周转时间短-对批处理系统系统希望平均
3、（带权）周转时间短-对批处理系统用户希望响应时间短-对分时系统用户希望开始执行的时间或完成时间短-对实时系统用户希望自己优先权高-对三种OS系统希望吞吐量大-对批处理系统系统希望处理机和资源的利用率高-对三种OS,（）调度方式与算法,调度方式:抢占式非抢占式可剥夺式（可抢占式Preemptive）：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用不可剥夺式（不可抢占式Non-preemptive）：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去常用算法FIFO,SPF（改进得最短剩余时间优先SRT:shorte
4、stremainingtimefirst）,优先级,时间片轮转（roundrobin）,高响应比优先（HighestResponseRatioNext）、Unix的多级队列反馈（RoundRobinwithMultipleFeedback）不同OS，选择特定的算法评价,各种进程调度算法,先进先出进程调度算法（FIFO）按照进程就绪的先后次序来调度进程优点:实现简单缺点:没考虑进程的优先级,基于优先数的调度（HPFHighestPriorityFirst）优先选择就绪队列中优先级最高的进程投入运行优先级根据优先数来决定,各种进程调度算法（续1）,确定优先数的方法静态优先数法：在进程创建时指定优先
5、数，在进程运行时优先数不变动态优先数法：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变,各种进程调度算法（续2）,时间片轮转程序调度算法(RRRoundRobin)把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行,各种进程调度算法（续3）,分时系统中常用时间片轮转法：时间片选择问题：固定时间片可变时间片与时间片大小有关的因素：系统响应时间就绪进程个数CPU能力,各种进程调度算法（续4）,多级队列反馈调度算
6、法将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出；系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列,各种进程调度算法（续6）,*首先系统中设置多个就绪队列*每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大*各个队列按照先进先出调度算法*一个新进程就绪后进入第一级队列*进程由于等待而放弃CPU后，进入等待队列，一旦等待的
7、事件发生，则回到原来的就绪队列*当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾*当第一级队列空时，就去调度第二级队列，如此类推*当时间片到后，进程放弃CPU，回到下一级队列,各种进程调度算法（续6）,UNIX动态优先数法5.3BSD多级反馈队列法Windows基于优先级的抢占式多任务调度Linux抢占式调度,各种进程调度算法（续7）,2.进程调度的时机,当一个进程运行完毕，或由于某种错误而终止运行当一个进程在运行中处于等待状态（等待I/O）时间片用完当有一个优先级更高的进程就绪（可抢占式）如：新创建一个进程；一个等待进程变成就绪在进程通信中，执行中的进程执行
8、了某种原语操作（P操作，阻塞原语，唤醒原语）进程中断/异常/系统调用返回到用户态时,3.进程切换,进程切换一个进程让出处理器，由另一个进程占用处理器的过程进程的切换使系统中的各进程均有机会占用CPU进程的切换是由进程状态的变化引起的，而进程状态的变化又与出现中断事件有关当有中断事件发生时，当前运行的进程被中断，中断响应后由操作系统处理出现的中断事件。中断处理后，某些进程的状态会发生变化，也可能又创建了一些新的进程。因此，要进行队列的调整。然后，进程调度根据预定的调度算法从就绪队列选一个进程占用CPU。这个占用CPU运行的进程可能仍是被中断的进程，也可能是另一个进程,何时切换进程?,只要OS取得
9、对CPU的控制，进程切换就可能发生，如:超级用户调用来自程序的显式请求(如：打开文件)，该进程通常会被阻塞陷阱最末一条指令导致出错，会引起进程移至退出状态中断外部因素影响当前指令的执行，控制被转移至IH（中断处理程序）,4.CPU调度过程,*保存现场：顺序保存，最后一步保存PSW*选择要运行的程序（如果没有就绪进程,系统会安排一个空转进程(idle),没有其他进程时该进程一直运行,在执行过程中可接收中断）*恢复现场：最后一步恢复选中进程的PSW,在进程（上下文）中切换的步骤,保存处理器的上下文，包括程序计数器和其它寄存器用新状态和其它相关信息更新正在运行进程的PCB把原来的进程移至合适的队列-
10、就绪、阻塞选择另一个要执行的进程更新被选中进程的PCB从被选中进程中重装入CPU上下文,5.Windows的线程调度,Windows处理机调度的调度对象是线程Windows的线程调度并不是单纯使用某一种调度算法，而是多种算法的综合体，针对实际系统的需要进行针对性的优化和改进,Windows线程调度的特征,调度单位是线程而不是进程，采用严格的抢先式动态优先级调度，依据优先级和分配时间配额来调度。,每个优先级的就绪线程排成一个先进先出队列当一个线程状态变成就绪时，它可能立即运行或进入相应优先级队列系统总是运行优先级最高的就绪线程在同一优先级的各线程按时间片轮转算法进行调度在多处理机系统中多个线程并
11、行运行,Windows2000/XP在内核中实现它的线程调度代码，线程调度的触发事件有以下四种：一个线程进入就绪状态，如一个刚创建的新线程或一个刚刚结束等待状态的线程一个线程由于时间配额用完而从运行状态转入结束状态或等待状态一个线程由于调用系统服务而改变优先级或被Windows2000/XP系统本身改变其优先级一个正在运行的线程改变了它的亲合处理机集合,与线程调度相关的Win32API函数,Suspend/ResumeThreadGet/SetPriorityClassGet/SetThreadPriorityGet/SetProcessPriorityBoostGet/SetThreadPr
12、iorityBoostGet/SetProcessAffinityMaskSetThreadAffinityMaskSetThreadIdealProcessorSwitchToThreadSleepSleepEx,线程优先级,Windows2000/XP内部使用32个线程优先级，范围从0到31，它们被分成以下三个部分16个实时线程优先级（1631）15个可变线程优先级（115）一个系统线程优先级（0），仅用于对系统中空闲物理页面进行清零的零页线程,线程优先级,实时优先级,在应用程序中，用户可在一定范围内升高或降低线程优先级要把线程的优先级提升到实时优先级，用户必须有升高线程优先级的权限如果用
13、户进程在实时优先级运行时间过多，它将可能阻塞关键系统功能的执行，阻塞系统线程的运行；但不会阻塞硬件中断处理在被其他线程抢先时，具有实时优先级线程与具有可变优先级线程的行为是不同的Windows并不是通常意义上的实时，并不提供实时操作系统服务,中断优先级与线程优先级的关系,如上图所示，所有线程都运行在中断优先级0和1用户态线程运行在中断优先级0，内核态的异步过程调用运行在中断优先级1，它们会中断线程的运行只有内核态线程可提升自己的中断优先级；虽然高优先级的实时线程可阻塞重要的系统线程执行，但不管用户态线程的优先级是多少，它都不会阻塞硬件中断,线程时间配额,时间配额是一个线程从进入运行状态到Win
14、dows检查是否有其他优先级相同的线程需要开始运行之间的时间总和一个线程用完了自己的时间配额时，如果没有其它相同优先级线程，Windows将重新给该线程分配一个新的时间配额，并继续运行时间配额不是一个时间长度值，而一个称为配额单位(quantumunit)的整数,提高前台线程优先级的问题,假设用户首先启动了一个运行时间很长的电子表格计算程序，然后切换到一个计算密集型的应用(如一个需要复杂图形显示的游戏)如果前台的游戏进程提高它的优先级，后台的电子表格将会几乎得不到CPU时间但增加游戏进程的时间配额，则不会停止电子表格计算的执行，只是给游戏进程的CPU时间多一些,线程时间配额,调度器数据结构,就
15、绪位图(KiReadySummary)为了提高调度速度，Windows维护了一个称为就绪位图(KiReadySummary)的32位量。就绪位图中的每一位指示一个调度优先级的就绪队列中是否有线程等待运行。B0与调度优先级0相对应，B1与调度优先级1相对应，等等空闲位图(KiIdleSummary)Windows还维护一个称为空闲位图(KiIdleSummary)的32位量。空闲位图中的每一位指示一个处理机是否处于空闲状态,调度器数据结构,调度策略,Windows严格基于线程的优先级来确定哪一个线程将占用处理机并进入运行状态Windows在单处理机系统和多处理机系统中的线程调度是不同的,(1)主
16、动切换,(2)抢先,当一个高优先级线程进入就绪状态时，正在处于运行状态的低优先级线程被抢先,用户态下运行的线程可以抢先内核态下运行的线程在判断一个线程是否被抢先时，并不考虑线程处于用户态还是内核态，调度器只是依据线程优先级进行判断当线程被抢先时，它被放回相应优先级的就绪队列的队首处于实时优先级的线程在被抢先时，时间配额被重置为一个完整的时间配额处于动态优先级的线程在被抢先时，时间配额不变，重新得到处理机使用权后将运行到剩余的时间配额用完,(2)抢先,(3)时间配额用完,如果刚用完时间配额的线程优先级降低了，Windows将寻找一个优先级高于刚用完时间配额线程的新设置值的就绪线程如果刚用完时间配额的线程的优先级没有降低，并且有其他优先级相同的就绪线程，Windows将选择相同优先级的就绪队列中的下一个线程进入运行状态，刚用完时间配额的线程被排到就绪队列的队尾(即分配一个新的时间配额并把线程状态从运行状态改为就绪状态)如果没有优先级相同的就绪线程可运行，刚用完时间配额的线程将得到一个新的时间配额并继续运行,(3)时间配额用完,(4)线程结束,当线程完成运
