多处理机调度短程调度

第7章 CPU调度,多道程序的关键是调度:对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。 处理机调度是OS的重要功能之一。 WHAT：按什么原则分配CPU 进程调度算法 WHEN：何时分配CPU 进程调度的时机 HOW： 如何分配CPU CPU调度过程（进程的上下文切换）,7.1 处理器调度的类型,处理器调度 对CPU资源进行合理地分配使用，以提高CPU的利用率，使各用户公平地得到CPU资源。 处理器调度的目标 以满足系统目标（如响应时间、吞吐率、处理器效率）的方式，把进程分配在一个处理器或多个处理器上执行。,处理器调度的准则,面向用户的准则 响应时间 (min)； 周转时间（结束时间-进入系统时间）(min)； 优先级 面向系统的准则 吞吐量(max) CPU利用率(max) 公平 资源的平衡使用 系统开销 (min),7.1 处理器调度的类型,长程调度（高级调度）：从外存的后备队列中选择一个或者多个作业调入内存，并为它们创建进程，分配必要的资源。 长程调度程序决定OS可以接纳一个还是多个进程 创建的进程越多，每个进程执行时间百分比就越小。 每当一个进程终止时或空闲时间片超过了一定的域值 ，调度程序可能会决定增加一个或多个新进程，或调用长程调度程序。 决定下一次允许哪个进程进入： 基于简单的FIFO原则，基于优先级、执行时间、I/O需求等 进程状态的变化为： 创建就绪/挂起；创建就绪,中程调度（中级调度）：将进程的部分或全部加载到内存中，提高内存利用率。进程状态变化（通过执行挂起和激活操作）： 就绪/挂起就绪 阻塞/挂起阻塞 短程调度（低级调度、进程调度、分派程序dispather )：选择哪个进程在处理机上执行，执行最频繁） 进程状态：就绪运行 当可能导致当前进程挂起或可能剥夺当前正在运行的进程的事件发生时，调用短程调度程序。包括如下事件： 时钟中断、I/O中断、操作系统调用、信号,7.1 处理器调度的类型,其它:按照OS类型的分类,批处理调度应用场合：大中型主机集中计算，如工程计算、理论计算 分时调度、实时调度 多处理机调度,7.1 处理器调度的类型,三种调度类型之间的关系: 当创建新进程时，执行高级调度，将新进程加入到当前活动的一组进程中。 中级调度是交换功能的一部分，它将一个进程至少部分换入内存中，使之以后能够执行。 低级调度才真正决定哪个就绪进程是下一个得以执行的进程。,调度和进程状态转换,用于调度的队列图,批作业,CPU,释放,超时,短程调度,就绪队列,就绪、挂起队列,阻塞、挂起队列,阻塞队列,事件等待,事件发生,交互用户,长程调度,中程调度,Admit,Running,Ready Suspend,Ready,Blocked,Dispatch,Timeout,Event,Wait,Event,Occurs,Release,Blocked Suspend,Suspend,Event,Occurs,Activate,Admit,高级调度,低级调度,中级调度,调度的层次,Activate,Suspend,Suspend,Exit,New,几个概念：CPU burst vs. I/O burst,阵发期 : CPU burst cycle: 进程(线程)使用CPU计算； I/O burst cycle: 进程(线程)使用设备I/O。 进程运行行为： CPU burst, I/O burst, CPU burst, I/O burst, CPU调度：考虑处于CPU burst进程集合 CPU burst时间根据以前行为推定。,7.2 进程调度算法-基本类型,非抢占调度（NonPreemptive）：就绪进程不可以从运行进程手中抢占CPU。 一旦进程处于运行状态，它就不断执行直到终止或者为等待I/O或请求某些操作系统服务而阻塞自己，才把CPU让给别人 抢占调度（Preemptive）：就绪进程可以从运行进程手中抢占CPU。 允许调度程序根据某种策略中止当前运行进程的执行，将其转移到就绪状态，并选择另一个进程投入运行。 时机： 一个新进程到达时 一个中断的发生 将一个被阻塞进程置为就绪态 周期性的时间中断,7.2 进程调度算法-基本类型,比较： 抢占策略可能会导致较大的开销，但是可对所有进程提供较好的服务，避免任一个进程独占CPU太长时间 通过使用有效的进程切换机制以及提供比较大的主存，使得大部分程序都在主存中，剥夺的代价可以相对比较低。,7.2 进程调度程序的功能,保存现场：记录放弃CPU的进程A的现场信息（如PC，通用寄存器的内容等） 选择进程：当进程出让CPU或调度程序剥夺执行状态进程占用的CPU时，选择适当的进程B分派CPU 完成上下文切换 用户态执行进程A代码，之后进入OS内核（通过时钟中断或系统调用） 保存进程A的上下文，载入进程B的上下文（CPU寄存器和一些表格的当前指针） 用户态执行进程B代码,7.2 进程调度-执行时机,与引起进程调度的原因及进程调度的方式有关： 创建进程。决定运行父进程还是子进程； 进程终止。正在执行的进程执行完毕； 执行中进程自己调用阻塞原语将自己阻塞进入阻塞状态； 执行中进程调用了P原语操作或V操作原语； 执行中进程提出I/O请求后被阻塞； 在分时系统中时间片已经用完； 在执行完系统调用等系统程序后返回用户进程时，这时可看作系统进程执行完毕，从而可调度选择一新的用户进程执行 在CPU执行是可剥夺的方式下，还有： 就绪队列中的某进程的优先级变得高于当前执行进程的优先级，也引发进程调度。,7.3 调度算法(1) 先来先服务FCFS,先来先服务FCFS (First-Come-First-Served) 当每个进程就绪后，它加入就绪队列。当正在运行的进程停止执行时，选择在就绪队列中存在时间最长的进程运行（要事先知道每个进程的结束时间）. 评价 非抢占调度 对于长进程有利，而不利于短进程。 有利于CPU繁忙型的进程，而不利于I/O繁忙型的进程 不能用于分时系统。 改进 FIFO自身对于单处理器系统并不是很有吸引力，通常与优先级策略结合，维护多个队列，每个优先级一个队列，每个队列采用FCFS的方法。如反馈法。,7.3调度算法(2)-最短作业优先(shortest-job-first，SJF),原则： 非剥夺的，下一次选择所需处理时间最短的进程（最短下一个CPU区间）。如果两个进程剩余时间相同，则使用FCFS来调度。 问题： 需要知道或至少需要估计每个进程所需要的处理时间。 评价： 有利于短进程。可以证明：SJF算法平均等待时间最小 长进程就可能被饿死：只要有持续不断的短进程存在 。 缺少剥夺机制，不适用于对分时系统或事务处理环境,7. 3调度算法（3）-最短剩余时间调度SRT（shortest remaining Timer，SRT）,原理： 对SJF增加了剥夺机制 选择预期剩余时间最短的进程，当一个新进程加入就绪队列时，它可能比当前运行的进程具有更短的剩余时间，只要新进程就绪，调度程序就进行剥夺。 优点： 既不偏爱长进程，也不像RR算法那样会产生额外的中断，从而减少了开销。 周转时间方面，SRT比SJF性能要好，短作业可以立即被选择执行。,7. 3调度算法（3）-最短剩余时间调度SRT（shortest remaining Timer，SRT）,SRT问题： 需要知道或至少需要估计每个进程所需要的处理时间。 只要有持续不断的短进程存在，长进程就可能被饿死 它必须记录过去的服务时间，从而增加了开销。,7.3 调度算法(4)优先级调度,优先级 每个进程都有一个优先级，调度程序总是选择具有较高优先级的进程。 静态优先级(static) 优先数在进程创建时分配，生存期内不变。 响应速度慢，开销小。 适合批处理进程 动态优先级(dynamic) 进程创建时继承优先级，生存期内可以修改。 响应速度快，开销大。,7.3 调度算法(4)优先级调度,问题 低优先级的进程可能会饿死(无穷阻塞）。如果一直有高优先级的就绪进程的话。 改进 一个进程的优先级随着它的时间或执行历史而变化老化策略(aging)。,7.3调度算法(5)-轮转调度RR （Round Robin）,轮转调度（或称时间片调度（time slicing） ：以一定的时间间隔周期性产生一个时钟中断，当中断发生时，当前正在运行的进程被置于就绪队列中，然后基于FCFS选择下一个就绪进程运行。专门为分时系统设计。 执行过程 将系统中所有的就绪进程按照FCFS原则，排成一个队列。 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。 在一个时间片结束时，发生时钟中断。 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。 进程可以未使用完一个时间片，就出让CPU（如阻塞）。,7.3调度算法(5)-轮转调度RR （Round Robin）,适用于分时系统,7.3调度算法（6）-轮转RR （Round Robin）,时间片长度变化的影响 过长响应时间长。退化为FCFS算法，进程在一个时间片内都执行完， 过短响应时间长。用户的一次请求需要多个时间片才能处理完，上下文切换次数增加。 因为处理时钟中断、执行调度和分派函数都需要处理器开销 策略：时间段最好略大于一次典型的交互所需要的时间，否则使响应时间延长（使用两个时间片）。 评价： 在分时系统或事务处理器系统中特别有效 缺点：偏向于CPU型的进程。,7.3调度算法（7）-最高响应比调度算法（HRRN）,原理： 当前进程完成或被阻塞时，选择响应比最大的就绪进程运行。 响应比R定义： R(wS)/S (R:响应比,W等待时间,S运行时间 响应比R= 周转时间 / 运行时间 =（运行时间 + 等待时间）/ 运行时间 = 1 +（等待时间 / 运行时间） 评价： 该算法是FCFS和SJF的结合，克服了两种算法的缺点 公平，吞吐率大 需要估计期待的服务时间，增加了计算，增加了开销,7.3调度算法（8）-多级队列调度算法,多级队列调度算法：将就绪队列分成多个独立队列，进程所属的队列固定。通过各队列的区别对待，达到一个综合的调度目标。 例如：通用系统中： 队列1：实时进程就绪队列（优先级） 队列2：分时进程就绪队列 （RR） 队列3：批处理进程就绪队列 （优先级）,7.3调度算法（8）-多级队列调度算法,各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等。如前台对队列可能用RR，而后台队列可能是用FCFS。 队列之间也要进行调度：采用固定优先级、可抢占调度来实现。如前台队列优先级高于后台队列优先级。 各队列的优先级自上而下降级。只有优先级高的队列中没有进程时，才可以调度优先级低的队列中的进程,7.3调度算法-多级队列调度算法,7.3调度算法（9）-多级反馈队列调度,多级反馈队列（Feed-Back）: 多个就绪队列，进程所属队列可变，即进程可以在不同的就绪队列之间移动 设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如：逐级加倍 队列优先级逐级降低，而时间片长度逐级递增,7.3调度算法（9）-多级反馈队列调度,出发点 SJF，SRT都需要知道进程的运行时间，有局限性。如果没有关于各个进程相对长度的任何信息，则可以以已经执行了的时间进行衡量 调度基于剥夺原则（按时间片），使用动态优先级机制。 OS将处理器分配给一个进程，当这个进程被阻塞或被剥夺时，就反馈到多个优先级队列中的一个队列中。 多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展，基于抢占式，使用动态优先级机制 问题：可能饿死。,Multilevel Feedback Queues,优先级递增,时间片递增,7.3调度算