操作系统调度与接口（二）

二、其他调度算法

1、时间片轮转（Round-Robin）（RR）调度算法

它用于进程调度，是分时系统中采用的主要调度算法。进程调度程序总是选择就绪队列中的第一个进程，允许其占有处理机一个时间片的时间。当执行的时间片用完时，调度程序便停止该程序的执行，并将它送到就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片处理机执行时间。

在RR算法中，时间片的大小对系统性能有很大的影响。

2、优先权调度算法

静态优先权在进程创建时确定，且在整个生命期中保持不变。

确定进程优先权的依据有：

进程类型

进程对资源的需求

根据用户要求

动态优先权是指在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能。

在UNIX系统中，一类是因等待磁盘I/O、等待缓冲器等不可中断优先权最高，而另一类因等待TTY输入输出等可中断优先权其次。处于用户态的优先权相对较低，用户态优先权又分为n+1级优先权。优先数为0级的优先权最高，优先数为n级的优先权最低。

用户态优先权是可变的，它随着占用CPU时间的增加而降低。核心每隔1秒钟便按下述公式对个进程重新计算其用户优先数（优先数与优先权成反比关系）

优先数=最近使用CPU的时间/2+基本用户优先数

3、多级队列调度算法

多队列调度是根据作业的性质和类型的不同，将就绪队列再分为若干个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法。

对多级就绪队列调度策略有两种：

一种是各就绪队列按进程性质赋予不同的优先权，这样，只有较高优先权的就绪队列都空时才调度最低优先权就绪队列的进程。

另一种调度就绪队列的方式是为每个队列分配一定的占用CPU时间的比例。

4、多级反馈队列调度算法

多级反馈队列调度算法，不必事先知道各种进程所需的执行时间。

WindosNT采用可抢占动态优先级多级就绪队列调度算法。NT执行体支持32级优先级，并将他们分成两类，实时优先级（16-31）和可变优先级（1-15），0级为系统保留。每个优先级一个就绪队列，高序号队列为高优先级，调度程序从高优先级的队列开始往下找，如高优先级队列为空时才再往下找，直至找到一个线程。

各个就绪队列中进程执行时间片的大小也各不相同，在优先级越高的队列中，每个进程的执行时间片就规定得越小。

当一个线程执行完一个完整的时间段后被中断抢占处理器，而被抢占的线程优先级降低一级而进入下级就绪队列，如此继续，直至降到线程的基本优先级。

而一个线程从阻塞态变为就绪态时要提高优先级，提高的幅度与等待的事件有关。如等待键盘输入所提高的幅度要大于等待磁盘I/O。在NT中，交互式线程处于高优先级，I/O型型线程处于中间优先级，计算型线程处于低优先级，系统还设置了一个空闲线程，其优先级为0，是优先级最低的线程，只要处理空闲，就执行该线程。