OS-04处理机调度.ppt

中等粒度的并行度 应用程序可以作为进程中的一组线程被有效地实现。在这种情况下，可以由程序员显式地指定应用程序潜在的并行性。典型地，在应用程序的线程之间，需要更高程度的合作与交互，从而导致中等粒度级的同步 尽管多处理器和多道程序单处理器都支持独立、非常粗和粗粒度的并行度，并对调度功能产生少许影响或没有影响，但是在处理线程调度时，我们仍然需要重新分析调度。由于应用程序中各个线程间的交互是如此地频繁，关于线程调度的决策可能会影响整个应用的性能 粒度 细粒度的并行度 代表着比线程中的并行更加复杂的使用。尽管在高度并行的应用中已经完成了大量的工作，迄今为止，这仍然是一个特殊的、被分割的领域 粒度 多处理器中的调度涉及到以下三个相关问题 把进程分配到处理器 在单个处理器上使用多道程序 一个进程的实际分派 在讨论这三个问题时，必须记住所采用的方法通常取决于应用程序的粒度等级和可用的处理器的数目 设计问题 把进程分配到处理器 假设多处理器结构中各个处理器在访问主存和I/O设备时没有特别优势，那么最简单的调度方法是把处理器看作是一个资源池，并按照要求把进程分配到相应的处理器。带来的问题是：分配应该是静态的还是动态的 设计问题 调度算法 分级轮转法 为了公平性，低优先级就绪队列的进程如果获得调度，将得到比高优先级就绪队列进程更多的时间片，加以弥补 这样能大大降低长作业的交换频率，减少系统在交换作业时的时间消耗，又给了短作业较高的优先级 两个优先级队列特例：前台和后台进程。 优先级调度算法：按进程的优先级调度 非抢占的优先级调度法：一旦一个高优先级的进程占有了处理器，就一直运行下去，直到因等待某事被阻塞或执行结束，才选择就绪队列中优先级最高的进程来执行。 可抢占的优先级调度法：任何时刻都按照高优先级进程在处理器上运行的原则进行进程调度。当一高优先级进程运行时，若有一更高优先级进程到达就绪队列，则当前运行进程立刻将处理器让给更高优先级的进程（即使未处理完，也无遇到阻塞情况） 调度算法 动态优先级法 指进程的优先级在该进程的生存期间可以改变 大多数动态优先级设计方案 把交互式和I/O频繁的进程移到优先级队列的顶端，而让计算量大的进程移到较低的优先级上 对与优先级相同的进程，按先来先服务或轮转法则分配处理机 对于一给定时间周期，一个正在运行的进程，每请求一次I/O操作后其优先级就自动加 1，直接反映出I/O请求的频率，从而使I/O设备具有很高的利用率 调度算法 最短进程SPN（短进程优先调度算法） 减少FCFS固有的对长进程的偏爱的另一种方法是最短进程 (SPN) 策略，这是一种非剥夺的策略，其原则是下一次选择所需处理时间最短的进程，因此，短进程将会越过长进程，跳到队列头 SPN策略的难点在于需要知道或至少需要估计每个进程所需要的处理时间 长进程可能被“饿死” 调度算法 最短剩余时间优先调度算法 (SRT) 对SPN增加剥夺机制。当一个时钟中断周期到后，调度程序总是选择预期剩余时间最短的进程 当一个新进程加入就绪队列时，它可能比当前运行的进程具有更短的剩余时间，因此，调度程序将剥夺当前程序，将处理器分配给新进程。 和SPN一样，调度程序必须有关于处理时间的估计，并且存在长进程被饿死的危险 调度算法 最高响应比优先调度算法（HRRN） 响应比： R=(w+s)/s=1+w/s w表示等待时间；s表示执行所需时间 最高响应比也是对最短进程法的一种改进，当当前进程完成或被阻塞时，选择响应比最大的进程先执行，是一种非剥夺的策略。 响应比R，代表了进程的年龄，算法在保证短进程优先的同时又兼顾了长进程——折中 调度算法 最高响应比优先调度算法（HRRN） R=(w+s)/s=1+w/s 当一系列进程同时进入系统时，由于短作业s值小，R值就大，因此短作业得到了优先执行。 但随着长作业等待的时间(w)增长，R值不断增大，到达一定的等待时间，长进程最终将凭借年龄的增长战胜短进程，从而获得处理器。 可见，在HRRN算法中，长作业不会被饿死 调度算法 反馈FB（多级反馈队列调度算法） 分级轮转调度和动态优先级算法的结合，采用剥夺策略 划分多个就绪队列，优先级逐步降低。 新建进程进入优先级最高的队列中，每当进程规定的时间片用完，被剥夺时，就送往低一级的就绪队列。 进程调度时总是先执行高优先级队列中的进程。高优先级队列为空后，才转去处理低一级优先级队列中的进程。 同一优先级队列（除最低）的进程，按FIFO机制调度。最低优先级队列，按时间片轮转调度算法执行 调度算法 允许进入 CPU RQ0 RQ1 RQ2 RQn 释放 CPU 释放 CPU 释放 CPU 释放 反馈调度 不同优先级的就绪队列可以给予相同的时间片，也可以不同。 调度算法 反馈FB 在反馈调度算法中，长进程