调度算法

所有系统的调度目标：
公平——给每一个进程公平的CPU份额
策略强制执行——保证规定的策略被执行
平衡——保证系统的所有部分都忙碌

在不同的系统中，调度程序的优化是不同的。这里有必要划分出三中环境。

目标：
吞吐量——系统每小时完成的作业数量
周转时间——从一个批处理作业提交时刻开始直到该作业完成时刻为止的时间。
CPU利用率——保持CPU始终忙碌
（CPU利用率并不是一个好的度量参数。真正有价值的是吞吐量和周转时间。另一个方面，知道什么时候CPU利用率接近100%比知道什么时候要求得到更多的计算能力要有用）

先来先服务:

优点：
易于理解，并且便于在程序中运用。
单链表记录了所有的就绪进程，实现简单易于理解。
缺点：
平均等待时间长
CPU和设备的使用率降低

最短作业优先：

使用该算法前提必须要了解到进程运行所需要的时间。

平均周转时间为（4a+3b+2c+d）/4其中A、B、C、D为四个进程。可以看出A对平均值的影响最大，所以A应该为最短作业的进程，其次是B、C、D.

最短剩余时间优先：

使用该算法前提必须要了解到进程运行所需要的时间。
最短作业优先的抢占版本是最短剩余时间优先，调度程序总是选择剩余时间最短的那个先运行。
如果有新的进程比当前进程需要更少的时间，则当前进程会被挂起，而运行新的进程。可以使新的最短作业获得良好的服务。

目标：
响应时间——快速响应请求
均衡性——满足用户的期望
（对于交互式系统，最重要的是最小响应时间，即从发出命令到响应之间的时间。。。）

轮盘调度：

每个进程被分配一个时间段，称为时间片，即允许该进程在这个时间段中运行。如果在时间段结束该进程还在运行，则将剥夺CPU并分配给另外一个进程。如果该进程在时间片结束时该进程还在运行，则将剥夺CPU并分配给另外一个进程，将该进程移动队列的末尾处。如果该进程在时间片结束之前阻塞或者结束，则CPU立即进行切换。时间片轮转调度很容易实现，调度程序所需要做的就是维护一张可运行的线程表。

时间片的长短很重要，设的太短会导致过多的进程切换（进程切换也是需要时间的），降低了CPU效率，设置的太长，可能对短的交互请求的响应时间过长。将时间片设置为20~50ms通常是一个比较合理的折中

优先级调度：

一种方法：每个进程被赋予一个优先级，允许优先级最高的可运行进程运行。为了防止高优先级进程无休止地进行下去，调度程序可能在每个始终中断降低当前进程的优先级。如果当前进程优先级低于次高级的进程，则进行进程切换另一种方法：给每一个进程一个允许运行的最大时间片，当用完这个时间篇，此高级进程获得运行的机会。优先级的动态赋予与静态赋予静态赋予即给进程固定的优先级动态赋予：将优先级设为1/F，F为该进程在上一个时间片中所占用的部分（一个在其50ms的时间片中只使用1ms的进程将获得优先级50，而在阻塞之前用掉25ms的进程将具有优先级2，而使用掉全部时间片的进程将得到优先级1），对于I/O密集型进程会获得较好的服务。使用该算法需要偶尔对优先级进行调整，否则优先级较低的进程会产生饥饿现象（有优先级高的进程便不会理会优先级低的进程，所以优先级低的进程要等好久才会运行）

多级队列：

属于最高优先级类的进程运行一个时间片，次高优先级类的进程运行2个时间片，再次以及运行4个时间片，以此类推.当一个进程用完分配的时间片后，它被移到下一类。
设想一个需要100个时间片的进程，它最初被分类1个时间片，接下来是 2、4、8、16、32、64.最后只需要37个时间片便可结束。
随着优先级不断降低，它的运行频率逐渐放慢，从而为短的交互进程让CPU。
上述例子可能64的时间片要等好久才会运行。为了防止这种进程永远处于地类优先级，可以采取按键的方式将当前进程一道最高优先级类里面。

保证调度：

系统必须跟踪各个进程自创建以来已使用了多少CPU时间。计算各个进程应获得的CPU时间/n（用户工作时有n个用户登录）。这期间进程实际获得CPU的时间是已知。

比率为1/2说明一个进程只获得了应得时间的一半，而比率为4/2
则说明它获得应得时间2倍。于是该短发随后转向比率最低的进程，知道该进程的比率超过它的最接近竞争者为止。

彩票调度：

为进程提供提供各种系统资源（如CPU时间）的彩票。一旦需要做出一项调度决策时，系统可以掌握每秒钟50次的一种彩票，作为奖励，每个获奖者可以得到20ms的CPU时间。
可以给重要的进程额外的彩票，以便增加它们获胜的机会。
彩票调度是反应迅速的。
如果希望协作进程可以交换它们的彩票。客户进程可以把它左右的彩票交给服务器，以增加该服务器的下次运行的机会。服务器运行完成后，该服务器再把彩票还给客户机，这样客户机便可运行。
如果没有客户机，服务器根本不需要彩票。
彩票调度可以解决用其他方法很难解决的问题，例如，视频服务器的帧速率。

公平分享调度：

每个用户分配到CPU时间的一部分，而调度程序以一种强制的方式选择进程。

目标：
满足截止时间——避免丢失数据
可预测性——在多媒体系统中避免品质降低

硬实时：必须满足绝对的截止时间。

软实时：不希望偶尔错失截止时间，但可以容忍。

实时系统中的时间可以按照相应方式进一步分为周期性时间或非周期性时间。