《进程调度.ppt》由会员分享，可在线阅读，更多相关《进程调度.ppt（50页珍藏版）》请在三一文库上搜索。
1、处理机调度（CPU调度）,(1)起因 (2)调度范围与调度模型 (3)调度标准 (4)调度方式与调度算法 (5)性能分析 (6)后果（饥饿，死锁）及解决,处理机调度（CPU调度）,关键要解决的问题 WHAT：按什么原则分配CPU 进程调度算法 WHEN：何时分配CPU 进程调度的时机 HOW： 如何分配CPU CPU调度过程（进程的上下文切换）,处理机调度的三个层次,处理机是计算机系统中的重要资源 处理机调度算法对整个计算机系统的综合性能指标有重要影响 可把处理机调度分成三个层次： 高级调度 中级调度 低级调度,高级调度也称为作业调度或宏观调度 高级调度的时间尺度通常是分钟、小时或天 中级调度
2、涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问 低级调度也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效,处理机调度的三个层次（续）,分类 -按层次：高级（作业）、中级、低级（进程） -按OS类型：批处理、分时、实时、多处理机 -按时间尺度：宏观（分、时、天），微观（毫秒）,处理机调度的分类,1.处理机调度算法,（1）处理机
3、调度 处理机调度的任务是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程,（2）调度标准确定算法的原则,用户希望周转时间短-对批处理系统 系统希望平均（带权）周转时间短-对批处理系统 用户希望响应时间短-对分时系统 用户希望开始执行的时间或完成时间短-对实时系统 用户希望自己优先权高-对三种OS 系统希望吞吐量大-对批处理系统 系统希望处理机和资源的利用率高-对三种OS,（）调度方式与算法,调度方式:抢占式非抢占式 可剥夺式（可抢占式Preemptive）： 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提
4、供给具有更高优先级的进程使用 不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去 常用算法 FIFO,SPF（改进得最短剩余时间优先SRT: shortest remaining time first）,优先级,时间片轮转（round robin）,高响应比优先（Highest Response Ratio Next）、Unix的多级队列反馈（Round Robin with Multiple Feedback） 不同OS，选择特定的算法 评价,各种进程调度算法,先进先出进程调度算法（FIFO） 按照进程就绪的先后次
5、序来调度进程 优点:实现简单 缺点:没考虑进程的优先级,基于优先数的调度 （HPFHighest Priority First） 优先选择就绪队列中优先级最高的进程投入运行 优先级根据优先数来决定,各种进程调度算法（续1）,确定优先数的方法 静态优先数法： 在进程创建时指定优先数，在进程运行时优先数不变 动态优先数法： 在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变,各种进程调度算法（续2）,时间片轮转程序调度算法 (RRRound Robin) 把CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程，进程轮流占有CPU，当时间片用完时，即使进
6、程未执行完毕，系统也剥夺该进程的CPU，将该进程排在就绪队列末尾。同时系统选择另一个进程运行,各种进程调度算法（续3）,分时系统中常用时间片轮转法： 时间片选择问题： 固定时间片 可变时间片 与时间片大小有关的因素： 系统响应时间 就绪进程个数 CPU能力,各种进程调度算法（续4）,多级队列反馈调度算法 将就绪队列分为N级，每个就绪队列分配给不同的时间片，队列级别越高，时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列，.当运行进程用完一个时间片，放弃CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列
7、；当进程第一次就绪时，进入第一级队列,各种进程调度算法（续6）,* 首先系统中设置多个就绪队列 * 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大 * 各个队列按照先进先出调度算法 * 一个新进程就绪后进入第一级队列 * 进程由于等待而放弃CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列 * 当有一个优先级更高的进程就绪时，可以抢占CPU，被抢占进程回到原来一级就绪队列末尾 * 当第一级队列空时，就去调度第二级队列，如此类推 * 当时间片到后，进程放弃CPU，回到下一级队列,各种进程调度算法（续6）,UNIX 动态优先数法 5.
8、3BSD 多级反馈队列法 Windows 基于优先级的抢占式多任务调度 Linux 抢占式调度,各种进程调度算法（续7）,2.进程调度的时机,当一个进程运行完毕，或由于某种错误而终止运行 当一个进程在运行中处于等待状态（等待I/O） 时间片用完 当有一个优先级更高的进程就绪（可抢占式） 如：新创建一个进程；一个等待进程变成就绪 在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语，唤醒原语） 进程中断/异常/系统调用返回到用户态时,3.进程切换,进程切换 一个进程让出处理器，由另一个进程占用处理器的过程 进程的切换使系统中的各进程均有机会占用CPU 进程的切换是由进程状态的变化引起的
9、，而进程状态的变化又与出现中断事件有关 当有中断事件发生时，当前运行的进程被中断，中断响应后由操作系统处理出现的中断事件。中断处理后，某些进程的状态会发生变化，也可能又创建了一些新的进程。因此，要进行队列的调整。然后，进程调度根据预定的调度算法从就绪队列选一个进程占用CPU。这个占用CPU运行的进程可能仍是被中断的进程，也可能是另一个进程,何时切换进程?,只要OS取得对CPU的控制，进程切换就可能发生，如: 超级用户调用 来自程序的显式请求 (如：打开文件)， 该进程通常会被阻塞 陷阱 最末一条指令导致出错，会引起进程移至退出状态 中断 外部因素影响当前指令的执行，控制被转移至IH（中断处理程
10、序）,4.CPU调度过程,* 保存现场：顺序保存，最后一步保存PSW * 选择要运行的程序 （如果没有就绪进程,系统会安排一个空转进程(idle),没有其他进程时该进程一直运行,在执行过程中可接收中断） * 恢复现场：最后一步恢复选中进程的PSW,在进程（上下文）中切换的步骤,保存处理器的上下文，包括程序计数器和其它寄存器 用新状态和其它相关信息更新正在运行进程的PCB 把原来的进程移至合适的队列-就绪、阻塞 选择另一个要执行的进程 更新被选中进程的PCB 从被选中进程中重装入 CPU 上下文,5.Windows的线程调度,Windows处理机调度的调度对象是线程 Windows 的线程调度并
11、不是单纯使用某一种调度算法，而是多种算法的综合体，针对实际系统的需要进行针对性的优化和改进,Windows 线程调度的特征,调度单位是线程而不是进程，采用严格的抢先式动态优先级调度，依据优先级和分配时间配额来调度。,每个优先级的就绪线程排成一个先进先出队列 当一个线程状态变成就绪时，它可能立即运行或进入相应优先级队列 系统总是运行优先级最高的就绪线程 在同一优先级的各线程按时间片轮转算法进行调度 在多处理机系统中多个线程并行运行,Windows 2000/XP在内核中实现它的线程调度代码，线程调度的触发事件有以下四种： 一个线程进入就绪状态，如一个刚创建的新线程或一个刚刚结束等待状态的线程 一
12、个线程由于时间配额用完而从运行状态转入结束状态或等待状态 一个线程由于调用系统服务而改变优先级或被Windows 2000/XP系统本身改变其优先级 一个正在运行的线程改变了它的亲合处理机集合,与线程调度相关的Win32 API函数,Suspend/ResumeThread Get/SetPriorityClass Get/SetThreadPriority Get/SetProcessPriorityBoost Get/SetThreadPriorityBoost Get/SetProcessAffinityMask SetThreadAffinityMask SetThreadIdealP
13、rocessor SwitchToThread Sleep SleepEx,线程优先级,Windows 2000/XP内部使用32个线程优先级，范围从0到31，它们被分成以下三个部分 16个实时线程优先级（1631） 15个可变线程优先级（115） 一个系统线程优先级（0），仅用于对系统中空闲物理页面进行清零的零页线程,线程优先级,实时优先级,在应用程序中，用户可在一定范围内升高或降低线程优先级 要把线程的优先级提升到实时优先级，用户必须有升高线程优先级的权限 如果用户进程在实时优先级运行时间过多，它将可能阻塞关键系统功能的执行，阻塞系统线程的运行；但不会阻塞硬件中断处理 在被其他线程抢先时，
14、具有实时优先级线程与具有可变优先级线程的行为是不同的 Windows 并不是通常意义上的实时，并不提供实时操作系统服务,中断优先级与线程优先级的关系,如上图所示，所有线程都运行在中断优先级0和1 用户态线程运行在中断优先级0，内核态的异步过程调用运行在中断优先级1，它们会中断线程的运行 只有内核态线程可提升自己的中断优先级；虽然高优先级的实时线程可阻塞重要的系统线程执行，但不管用户态线程的优先级是多少，它都不会阻塞硬件中断,线程时间配额,时间配额是一个线程从进入运行状态到Windows 检查是否有其他优先级相同的线程需要开始运行之间的时间总和 一个线程用完了自己的时间配额时，如果没有其它相同优
15、先级线程，Windows将重新给该线程分配一个新的时间配额，并继续运行 时间配额不是一个时间长度值，而一个称为配额单位(quantum unit)的整数,提高前台线程优先级的问题,假设用户首先启动了一个运行时间很长的电子表格计算程序，然后切换到一个计算密集型的应用(如一个需要复杂图形显示的游戏) 如果前台的游戏进程提高它的优先级，后台的电子表格将会几乎得不到CPU时间 但增加游戏进程的时间配额，则不会停止电子表格计算的执行，只是给游戏进程的CPU时间多一些,线程时间配额,调度器数据结构,就绪位图(KiReadySummary) 为了提高调度速度，Windows维护了一个称为就绪位图(KiRea
16、dySummary)的32位量。就绪位图中的每一位指示一个调度优先级的就绪队列中是否有线程等待运行。B0与调度优先级0相对应，B1与调度优先级1相对应，等等 空闲位图(KiIdleSummary) Windows 还维护一个称为空闲位图(KiIdleSummary)的32位量。空闲位图中的每一位指示一个处理机是否处于空闲状态,调度器数据结构,调度策略,Windows严格基于线程的优先级来确定哪一个线程将占用处理机并进入运行状态 Windows 在单处理机系统和多处理机系统中的线程调度是不同的,(1)主动切换,(2)抢先,当一个高优先级线程进入就绪状态时，正在处于运行状态的低优先级线程被抢先,用
17、户态下运行的线程可以抢先内核态下运行的线程 在判断一个线程是否被抢先时，并不考虑线程处于用户态还是内核态，调度器只是依据线程优先级进行判断 当线程被抢先时，它被放回相应优先级的就绪队列的队首 处于实时优先级的线程在被抢先时，时间配额被重置为一个完整的时间配额 处于动态优先级的线程在被抢先时，时间配额不变，重新得到处理机使用权后将运行到剩余的时间配额用完,(2)抢先,(3)时间配额用完,如果刚用完时间配额的线程优先级降低了，Windows 将寻找一个优先级高于刚用完时间配额线程的新设置值的就绪线程 如果刚用完时间配额的线程的优先级没有降低，并且有其他优先级相同的就绪线程，Windows 将选择相
18、同优先级的就绪队列中的下一个线程进入运行状态，刚用完时间配额的线程被排到就绪队列的队尾(即分配一个新的时间配额并把线程状态从运行状态改为就绪状态) 如果没有优先级相同的就绪线程可运行，刚用完时间配额的线程将得到一个新的时间配额并继续运行,(3)时间配额用完,(4)线程结束,当线程完成运行时，它的状态从运行状态转到终止状态 线程完成运行的原因可能是 通过调用ExitThread而从主函数中返回 通过被其他线程通过调用TerminateThread来终止 如果处于终止状态的线程对象上没有未关闭的句柄，则该线程将被从进程的线程列表中删除，相关数据结构将被释放,在下列5种情况下，Windows 会提升
19、线程的当前优先级： I/O操作完成 信号量或事件等待结束 前台进程中的线程完成一个等待操作 由于窗口活动而唤醒图形用户接口线程 线程处于就绪状态超过一定时间，但没能进入运行状态(处理机饥饿) 线程优先级提升的目的是改进系统吞吐量、响应时间等整体特征，解决线程调度策略中潜在的不公正性。但它也不是完美的，它并不会使所有应用都受益 Windows 永远不会提升实时优先级范围内(16至31)的线程优先级,线程优先级提升,I/O操作完成后的线程优先级提升,在完成I/O操作后，Windows 将临时提升等待该操作线程的优先级，以保证等待I/O操作的线程能有更多的机会立即开始处理得到的结果 为了避免I/O操
20、作导致对某些线程的不公平偏好，在I/O操作完成后唤醒等待线程时将把该线程的时间配额减1 线程优先级的实际提升值是由设备驱动程序决定的 与I/O操作相关的线程优先级提升建议值在文件“Wdm.h”或“Ntddk.h”中。设备驱动程序在完成I/O请求时通过内核函数IoCompleteRequest来指定优先级提升的幅度 线程优先级的提升幅度与I/O请求的响应时间要求是一致的，响应时间要求越高，优先级提升幅度越大,等待事件和信号量后的线程优先级提升,当一个等待事件对象或信号量对象的线程完成等待后，它的优先级将提升一个优先级 阻塞于事件或信号量的线程得到的处理机时间比处理机繁忙型线程要少，这种提升可减少
21、这种不平衡带来的影响 SetEvent、PulseEvent或ReleaseSemaphore函数调用可导致事件对象或信号量对象等待的结束 提升是以线程的基本优先级为基点的，而不是线程的当前优先级。提升后的优先级永远不会超过15。在等待结束时，线程的时间配额被减1，并在提升后的优先级上执行完剩余的时间配额；随后降低1个优先级，运行一个新的时间配额，直到优先级降低到初始的基本优先级,前台线程在等待结束后的优先级提升,对于前台进程中的线程，一个内核对象上的等待操作完成时，内核函数KiUnwaitThread会提升线程的当前优先级(不是线程的基本优先级)，提升幅度为变量PsPrioritySepar
22、ation的值 在前台应用完成它的等待操作时小幅提升它的优先级，以使它更有可能马上进入运行状态，有效改进前台应用的响应时间特征 用户不能禁止这种优先级提升，甚至是在用户已利用Win32的函数SetThreadPriorityBoost禁止了其他的优先级提升策略时，也是如此,图形用户接口线程被唤醒后的优先级提升,拥有窗口的线程在被窗口活动唤醒(如收到窗口消息)时将得到一个幅度为2的额外优先级提升 窗口系统(Win32k.sys)在调用函数KeSetEvent时实施这种优先级提升，KeSetEvent函数调用设置一个事件，用于唤醒一个图形用户接口线程 这种优先级提升可以改进交互应用的响应时间,对处
23、理机饥饿线程的优先级提升,系统线程“平衡集管理器(balance set manager)” 会每秒钟检查一次就绪队列，是否存在一直在就绪队列中排队超过300个时钟中断间隔的线程 如果找到这样的线程，平衡集管理器将把该线程的优先级提升到15，并分配给它一个长度为正常值两倍的时间配额 当被提升线程用完它的时间配额后，该线程的优先级立即衰减到它原来的基本优先级,空闲线程,如果在一个处理机上没有可运行的线程，Windows会调度相应处理机对应的空闲线程 由于在多处理机系统中可能两个处理机同时运行空闲线程，所以系统中的每个处理机都有一个对应的空闲线程 Windows给空闲线程指定的线程优先级为0，该空闲线程只在没有其他线程要运行时才运行,空闲线程的功能就是在一个循环中检测是否有要进行的工作。其基本的控制流程如下： 处理所有待处理的中断请求 检查是否有待处理的DPC请求。如果有，则清除相应软中断并执行DPC 检查是否有就绪线程可进入运行状态。如果有，调度相应线程进入运行状态 调用硬件抽象层的处理机空闲例程，执行相应的电源管理功能,空闲线程的功能,Thanks for your attention!,