5-2010-单处理器调度

《5-2010-单处理器调度》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、操作系统北京大学计算机科学技术系陈向群2010-2011第一学期单处理器调度处理机调度的类型设计处理机调度算法的原则典型的处理机调度算法实例：Windows线程调度一、处理机调度（CPU调度）问题的重要性处理机是计算机系统中的重要资源处理机调度算法对整个计算机系统的综合性能指标有重要影响处理机调度可分为三类：长程调度、中程调度、短程调度调度和进程状态转换队列图1.处理机调度的三种类型长程调度（作业调度或宏观调度）创建新进程时是否进入当前活跃进程集合中程调度涉及进程在内外存间的交换，从存储资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供

2、所需内存空间，将当前进程所需部分换入到内存短程调度（微观调度）从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，短程调度的时间尺度通常是毫秒级的。由于短程调度算法的频繁使用，要求在实现时做到高效2.CPU调度基本概念(1/2)CPU调度CPU调度的任务是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程CPU调度要解决的三个问题WHAT：按什么原则分配CPU—调度算法WHEN：何时分配CPU—调度时机HOW：如何分配CPU—调度过程（进程的上下文切换）进程调度的时机新进程创建时或一个等待进程变成就绪进程

3、正常终止或由于某种错误而终止当一个进程阻塞在I/O和信号量上或由于其他原因处于等待状态I/O中断发生时钟中断（如：时间片用完、定时器到时）进程切换进程切换一个进程让出处理器，由另一个进程占用处理器的过程进程的切换使系统中的各进程均有机会占用CPU进程的切换是由进程状态的变化引起的，而进程状态的变化又与出现中断事件有关当有中断事件发生时，当前运行的进程被中断，中断响应后由操作系统处理出现的中断事件。中断处理后，某些进程的状态会发生变化，也可能又创建了一些新的进程。因此，要进行队列的调整。然后，进程调度根据预定的调度算法从就绪队列选一个进程占用CPU。这个占用CPU运行的进

4、程可能仍是被中断的进程，也可能是另一个进程进程上下文切换的步骤保存处理器的上下文，包括程序计数器和其它寄存器用新状态和其它相关信息更新正在运行进程的PCB把原来的进程移至合适的队列——就绪、阻塞选择另一个要执行的进程（如果没有就绪进程,系统会安排一个闲逛进程idle）更新被选中进程的PCB从被选中进程中重装入CPU上下文二、CPU调度算法的设计讨论什么情况下需要仔细斟酌调度算法？批处理系统→多道程序设计系统→批处理与分时的混合系统→个人计算机→网络服务器进程分类按行为分：–I/O密集型(I/O-bound)频繁的进行I/O通常会花费很多时间等待I/O操作的完成–CPU

5、密集型(CPU-bound)计算密集型需要大量的CPU时间进行运算一些讨论(续)•另一种分类–交互式进程（interactiveprocess）需要经常与用户交互，因此要花很多时间等待用户输入操作响应时间要快，平均延迟要低于50~150ms典型的交互式程序：shell、文本编辑程序、图形应用程序等–批处理进程（batchprocess）不必与用户交互，通常在后台运行不必很快响应典型的批处理程序：营业额计算、利息计算、索赔处理–实时进程（real-timeprocess）有实时需求，不应被低优先级的进程阻塞响应时间要短典型的实时进程：视频/音频、机械控制等短程调度调度准则面向用户面向系

6、统周转时间性能吞吐量响应时间CPU利用率最后期限公平性其他可预测性强制优先级平衡资源调度准则的应用在互相竞争的各种要求中折中权衡针对某类操作系统确定原则：批处理系统：吞吐量/周转时间/CPU利用率交互式系统：响应时间/平衡实时系统：最后期限/可预测性三、各种CPU调度算法进程控制块中的相关信息√进程优先级及就绪队列的组织时间片大小选择及设置抢占式调度与非抢占式调度衡量指标（周转时间、归一化周转时间）调度器的开销√能否恒定（不依赖于当前系统负载）调度机制和调度策略分离的原则√是否会产生“饥饿”√进程优先级确定优先数的方法静态优先数：在进程创建时指定优先数，在进程运

7、行时优先数不变动态优先数：在进程创建时创立一个优先数，但在其生命周期内优先数可以动态变化。如等待时间长优先数可改变优先级排队抢占与非抢占两种占用CPU的方式：可剥夺式（可抢占式Preemptive）：当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用不可剥夺式（不可抢占式Non-preemptive）：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去时间片(quantum)选择