第四章-处理器调度.pptVIP

调度算法——轮转法 为了减少在FCFS 策略下短作业的不利情况，一种简单的方法是采用使用基于时钟的抢占策略，最简单的是轮转法。 具有8个进程的时闾片轮转调度示意图 调度算法——轮转法 将就绪的进程排列为一个就绪进程队列。 调度器每次把处理器分配给处在队列首部的进程，并使之运行一个规定的时间。 当时间片结束时，强迫当前进程让出处理器，并把这个进程插入就绪进程队列的尾部，然后把处理器分配给排在队列首部的进程，并同样使之运行一个规定的时间。 之后再重复上述过程，如此循环轮转地运行系统中的所有就绪进程。 调度算法——轮转法 在轮转法中，时间片长度的选取非常重要。时间片长度的选择会直接影响系统开销和响应时间。 时间片长度过短——调度程序剥夺处理器的次数增多，进程上下文切换次数也大大增加，加重系统开销。 时间片过长——例如一个时间片能使就绪队列中所需执行时间最长的进程能执行完毕，则轮转法变成了先来先服务法。 时间片长度的选择是根据系统对响应时间的要求R和就绪队列中所允许的最大进程数Nmax确定的。可表示为： q = R/ Nmax 一种可行的办法是，每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次q值，作为新一轮调度的时间片。这种方法得到的时间片是随就绪队列中的进程数变化的。 调度算法——优先级法 系统或用户按照某种原则为作业或进程指定一个优先级来表示该作业或进程所享有的调度优先权，调度器总是选择具有较高优先级的进程。 调度算法——优先级法 算法的核心——确定进程的优先级。 确定优先级的方法可以分为两类：静态法和动态法。 静态法根据进程的静态特性，在进程开始执行之前就确定它们的优先级，一旦开始执行之后就不能改变。 动态法把进程的静态特性和动态特性结合起来，确定进程的优先级，随着进程的执行，优先级不断变化。 调度算法——优先级法 进程静态优先级确定原则——按进程类型给予不同的优先级。例如： 系统进程具有比用户进程更高的优先级。 频繁使用外围设备的进程具有的优先级要大一些，有利于提高效率；承担重要计算任务的进程具有的优先级要大一些，有利于尽早得到计算结果；交互式用户的进程具有的优先级要大一些，可使用户等待响应的时间短一些，等等。 将用户进程划分为：I/O限制（繁忙），CPU限制，I/O与CPU均衡等类别，对系统进程，也可以根据所要完成的功能划分为不同类型，如调度进程、I/O进程、中断处理进程、存储管理进程等，这些进程还可以进一步划分和赋予不同的优先级。 给予静态优先级的调度算法实现简单，系统开销小，但由于静态优先级一旦确定以后，直到执行结束为止始终保持不变，因此系统效率较低，调度性能不高。现代操作系统中，如果使用优先级调度，则大多采用动态优先级的调度策略。 调度算法——优先级法 进程动态优先级确定原则 根据进程占有CPU时间的长短来确定。一个进程占有处理器的时间越长，则被阻塞之后再次获得调度的优先级就越低，反之，获得调度的可能性就会越大。 根据就绪进程等待CPU的时间长短来决定。一个就绪进程在就绪队列中等待的时间越长，则它获得的优先级就越高。 由于动态优先级随时间推移而变化，系统要经常计算各进程的优先级，因此，系统要为此付出一定的开销。 动态法——线性优先级调度策略 使用轮转法调度进程时，新创建的进程也放入就绪队列末尾享受平等的处理器时间片。这对于执行时间长的进程来说是不公平的，因为它们需要多个时间片才能完成。 线性优先级调度策略中，新创建的进程按FCFS方式排成就绪队列，而其它已得到过时间片服务的进程也按FCFS方式排成另一个就绪队列或称享受服务队列。 线性优先级调度策略 对于这两个不同队列中的进程，设新创建进程就绪队列中进程的优先级P以下列速率增加： P=a*t (a0) 另外，享受服务队列中进程的优先级P以下列速率增加： P=b*t (ab0) 设某一进程在时刻t1 被创建，在时刻t时，该进程的优先级为： P(t) = a*(t-t1) (t1 t t1’ )； 线性优先级调度策略 当新创建进程就绪队列中的第一个进程的优先级P(t)= a*(t-t1) 与享受服务队列中最后一个就绪进程的优先级P(t) = b*t 相等时，新创建进程队列中的第一个进程可以转入享受服务进程队列，优先级变化曲线如图。 设该进程在t1’时刻转入享受服务队列，则在时刻t，该进程的优先级变为： P(t) = a*(t1’ -t1)+b*(t-t1’ ) (t1’tt2’) 另外，当享受服务进程队列为空时，新创建进程队列的第一个进程也将移入享受服务进程队列。 调度算法——多级反馈轮转法 调度基于抢占原则(按时间段)并且使用动态优先级机制。 当一个进程第一次进入系统时，它