《操作系统处理器调度》由会员分享，可在线阅读，更多相关《操作系统处理器调度（39页珍藏版）》请在金锄头文库上搜索。
1、本章教学目标理解处理器调度的三个层次掌握处理器调度算法及其评价方法处理器调度的目的作业数量众多，而处理器、内存资源有限将处理器分配给不同的进程，以提高 响应时间 吞吐能力 处理器效率调度的层次长程调度(long-term scheduling)又称高级调度、作业调度决定了哪些作业被允许进入系统参与CPU的竞争高级调度将控制多道程序的道数中程调度(medium-term scheduling) 又称中级调度、平衡调度 根据主存状态决定主存中所能容纳的进程数目。当主存资源紧缺时，决定将哪些进程交换出内存；而当主存资源空闲时，选择将哪些进程交换回内存。短程调度(short-term scheduli
2、ng)又称低级调度、进程调度/线程调度、CPU调度 决定将就绪队列中的哪个进程/内核级线程分配处理器资源，使其能占用CPU执行。低级调度是操作系统最核心的部分，执行频繁长程调度批处理系统 何时从后备作业队列中创建新进程？一个作业运行结束CPU的空闲时间比例超过某个门限值 选择哪些作业进入主存，使其成为进程？FCFS, SJF, 平衡CPU密集型作业和I/O密集型作业平衡I/O资源的使用时分系统所有授权用户都被准入，直至系统饱和短程调度又称分派器，执行最为频繁短程调度的执行时刻外部中断系统调用信号调度算法调度算法的准则调度策略调度算法的准则吞吐率单位时间完成的进程数响应时间从请求提交到开始接收到
3、响应的时间，适用于交互型进程处理器利用率CPU利用率=CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间）周转时间进程从提交到结束的时间，包括执行时间和等待时间，适用于批处理作业截止时间进程必须在给定截止时间前完成，适用于实时任务公平性确保每个进程过的合理的CPU份额和其他资源分配，避免出现进程饿死。批处理系统的调度性能指标平均作业周转时间 平均带权作业周转时间短程调度的决策模式抢占式 系统可以根据所规定的原则剥夺正在运行的进程/线程的处理器资源，将其移入就绪队列，选择其他进程/线程执行； 剥夺原则高优先级进程/线程剥夺低优先级进程/线程当前运行进程/线程的时间片用完非抢占式 进程/
4、线程开始运行后不再让出处理器，除非进程/线程运行结束，或因发生某个事件（如等待I/O操作完成）而不能继续执行。单处理器调度算法种类先来先服务(First Come First Served: FCFS)最短作业优先(Shortest Job First: SJF)最短剩余时间优先(Shortest Remaining Time First: SRTF)响应比最高者优先(Highest Response Ratio First: HRRF)优先级调度轮转调度(Round Robin: RR)多级反馈队列调度(Multi-Level Feedback Queue: MLFQ)彩票调度(Lotter
5、y Scheduling) FCFS机制每个进程就绪时，加入就绪队列。当前进程停止执行时，选择在就绪队列中时间最长的进程执行。优点： 非剥夺式调度算法，易于实现适用于作业调度和进程调度缺点：效率不高不利于短作业而优待长作业 不利于I/O繁忙作业而有利于CPU繁忙作业若进程到达顺序为1，2，3，则平均周转时间为(28+37+40)/3=35ms若进程到达顺序为3，2，1，则平均周转时间为(3+12+40)/318ms平均周转时间：(3+7+9+12+12)/5=8.6平均带权周转时间：2.56虚线为调度决策时刻FCFS优待长作业，不利于短作业SJF机制当前进程停止执行时，选择预计所需的CPU运行
6、时间最小的进程执行。 非抢占式优点：有利于短作业 易于实现缺点无法准确获知进程所需的CPU运行时间 忽视作业的等待时间，有可能造成长作业饿死 缺乏抢占机制，对分时、实时处理依然不理想。假设进程1，2，3，4同时到达系统，则按SJF的调度顺序为：2，4，1，3平均周转时间=(4+12+21+31)/4=17ms平均周转时间：(3+7+11+14+3)/5=7.6平均带权周转时间：1.84SJF估算进程的下一个CPU周期长度指数衰减算法SRTF机制：调度器总是选择具有最短期望剩余运行时间的进程运行；当一个新进程加入就绪队列时，它可能具有比当前运行进程更短的剩余运行时间，此时，调度器将让该就绪进程抢
7、占当前运行的进程。 实际上可以看作是支持处理器抢占的SJF优点 有利于短作业 实现额外代价低缺点必须估计进程的处理时间 有可能会造成长作业的饿死平均周转时间：(3+13+4+14+2)/5=7.2平均带权周转时间：1.59HRRF机制 R=(w+s)/s；R: 响应比， w：等待处理器的时间，s：服务时间 当前运行进程结束或阻塞时，选择响应比R值最大的进程执行。非抢占式优点 考虑了进程的老化，有利于短进程(由于s小，所以R值将比较大)，也不会造成长进程的饿死(等待时间加长会使得其R值增加)缺点需要估算进程的服务时间平均周转时间：(3+7+9+14+7)/5=8平均带权周转时间：2.14Roun
8、d Robin机制 将时间划分成定长的时间片，当时间片完成后，产生时钟中断。 当时钟中断发生后，当前运行进程被放到就绪队列，按FCFS的原则选取下一个就绪进程执行。抢占式优点克服了FCFS中短作业可能会等待很长时间的问题有利于多用户、交互型进程缺点 增加了切换的额外开销 对I/O密集型和CPU密集型作业一视同仁，优待了CPU密集型作业时间片长度的选择对算法的性能影响很大时间片的选择RR, 时间片长度为1平均周转时间(4+16+13+14+7)/5=10.8RR, 时间片长度为4平均周转时间：（3+15+7+14+11)/5=10MLFQ机制 SJF, SRTF, HRRF都需要预先知道进程的运
9、行时间，这在实际上是很困难的。 MLFQ通过惩罚已经在处理器上运行时间很长的进程来达到优待短作业的效果。 系统维持一个动态优先级队列RQ0, RQ1, RQ2,.。当进程首次进入系统，置于队列RQ0，当其运行时间片到并返回就绪队列时，被置于RQ1。随后每次由于时间片到被抢占，它将被置于下一级就绪队列。每个队列内部采用FCFS的机制调度。当进入最低优先级队列后，进程不能再进入更低优先级的队列，而是采用Round Robin的方式呆在该队列中，直至完成服务。优点无需预先估算进程的运行时间 新进入系统的短进程将得到优待缺点长进程可能会饿死MLFQ的变种进程每次允许被执行的时间片为定长处于队列i的进程
10、被执行的时间片长度为2i个时间单元若进程在当前队列等待时间过长后，可以提升到一个更高优先级的队列，从而避免长进程饿死MLFQ, 队列i的时间片为2i时间单元彩票调度算法机制为进程发放针对系统各种资源（如CPU）的彩票，当调度程序需要作出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源。对CPU调度，系统可能每秒钟抽50次彩票，每次中奖者可以获得20ms的运行时间。优点所有进程都是平等的，有相同的运行机会如果某些进程需要更多机会，可以被赋予更多的额外彩票。实时调度硬实时必须满足时间限制软实时偶尔超过时间限制是可以容忍的响应事件分类周期性事件非周期性事件周期性任务的可调度性m个周期性任务，
11、任务i出现周期为Pi,处理所需要的CPU时间为Ci,则满足下列条件才可调度：实时调度算法单比例调度算法基于周期长度的抢占式调度策略周期越短，优先级越高如，为每个进程/线程分配与事件发生频率成正比的优先数限期调度算法将进程/线程按照发生事件的截止处理期限排序周期性事件的截止期限为事件下一次发生的时间选择截止期限最近的进程/进程运行当新进程/线程就绪时，依据截止期限决定是否抢占当前运行进程/线程最少裕度法计算各个进程/线程的富裕时间（裕度），然后选择裕度最少者执行 裕度=截止时间-(就绪时间+计算时间)多处理器调度多处理器系统的类型非对称多处理器(asymmetric multiprocessin
12、g)Master server: 负责所有的调度决策、I/O处理、以及其它系统行为Slave client: 仅执行用户代码对称多处理器(symmetric multiprocessing)每个处理器都具有相同的角色，自我调度所有处理器共享公共的就绪队列，or 每个处理器有自己的私有就绪队列多处理器调度的决策因素处理器亲和性(processor affinity)由于高速缓存的存在，如果一个进程在执行过程中被调度到其它处理器继续执行，则之前被缓存在高速缓存中与该进程相关的数据都将失效因此，应尽可能让进程在一个处理器上完成其执行，而会在生命周期内在不同的处理器上迁移。实现上存在两种模式Soft
13、affinityHard affinity负载均衡(load balancing) 试图将工作负载均匀地分布到不同的处理器上仅当每个处理器都有一个私有的就绪队列时才成为问题（共享公共就绪队列不存在负载均衡问题） 实现方式：Push migration： 存在一个进程定期检查每个处理器的负载Pull migration：由空闲处理器主动从繁忙的处理器取工作负载负载均衡与处理器亲和性存在矛盾多处理器调度算法负载共享调度算法实现方法系统维护全局性进程就绪队列当处理器空闲时，就选择进程的一个线程去运行优点 负载均衡 无需集中调度缺点 就绪队列必须被互斥访问 违背了处理器亲和性群调度算法一群相关线程被同时调度到一组处理器上运行紧密相关线程的并行执行能够减少同步阻塞，从而减少进程切换，降低调度代价，提高系统性能专用处理器调度算法 将同属一个进程的一组线程同时分派到一组处理机上运行，每个线程均获得一个处理机，专用于处理这个线程，直到进程运行结束。是群调度的一种极端形式当线程因等待事件而阻塞时，并不让出处理器，这就是所谓的专用性。
