Linux操作系统中常用调度算法 _调度算法

明确先来先服务FCFS、时间片轮转RR、优先级三种常用的调度算法的实现思想，并在此基础上计算周转时间、带权周转时间、平均周转时间和平均带权周转时间。
（一）先来先服务先来先服务（First-Come，First-Served，FCFS）方法是最简单的一种调度算法。它的实现思想就是“排队买票”的办法。对于作业调度来说，按照先来先服务法，是每次调度从后备作业队列（按进入时间先后为序）中选择队头的一个或几个作业，把它们调入内存，分配相应的资源，创建进程，然后把进程放入就绪队列。
对于进程调度算法来说，采用先来先服务法，就是每次调度从就绪队列中选择一个最先进入该队列的进程，把CPU分给它，令其投入运行。该进程一直运行下去，直至完成或者由于某些原因而阻塞，才放弃CPU 。这样，当一个进程进入就绪队列时，它的PCB就链入就绪队列的末尾。每次进程调度时就把队头进程从该队列中摘下，分给它CPU，使它运行。
设有3个作业，编号为1，2，3，各作业分别对应一个进程。各作业依次到达，相差一个时间单位。图示出采用FCFS方式调度时这3个作业的执行顺序。

文章插图
FCFS调度算法示意图
根据图，可算出各作业的周转时间和带权周转时间等，如表所示。
表 FCFS调度算法性能

文章插图

由表可以看出，FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。因为短作业运行时间很短，如果让它等待较长时间才得到服务，它的带权周转时间就会很长。
另外，FCFS调度算法对CPU繁忙型作业（指需要大量CPU时间进行计算的作业）较有利，而不利于I/O繁忙型作业（指需要频繁请求I/O的作业）。因为在执行I/O操作时，往往该作业（进程）要放弃对CPU的占有。当I/O完成后要进入就绪队列排队，可能要等待相当长一段时间，才得到较短时间的CPU服务，从而使这种作业的周转时间和带权周转时间都很大。
FCFS调度算法容易实现，但它的效率较低。
（二）时间片轮转法【Linux操作系统中常用调度算法】时间片轮转法（Round-Robin，RR）主要用于分时系统中的进程调度。为实现轮转调度，系统把所有就绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时，进程调度程序总是选出就绪队列的队首进程，让它在CPU上运行一个时间片的时间。
时间片是一个小的时间单位，通常为10至100毫秒数量级。当进程用完分给它的时间片后，系统的计时器发出时钟中断，调度程序便停止该进程的运行，并把它放入就绪队列的末尾；然后，把CPU分给就绪队列的队首进程，同样也让它运行一个时间片，如此往复。
例如，考虑如下4个进程A、B、C和D的执行情况。设它们依次进入就绪队列，但彼此相差时间很少，可以近似认为“同时”到达。四个进程分别需要运行12，5，3和6个时间单位。图3-6示出时间片q=1和q=4时它们运行的情况。

文章插图
RR法（q=1和q=4时进程运行情况）

文章插图

由图可以看出，在轮转法中，一次轮回时间内分给任何进程的CPU时间都不会大于一个时间片。如果一个进程在一个时间片内没有做完自己的事情，那么在时间片用完后，该进程就失去对CPU的控制权，被放到就绪队列的末尾。所以，一个运行较长时间的进程需要经过多次轮转才能完成。
可见，时间片的大小对轮转法的性能有很大影响。如果时间片太长，每个进程都在这段时间内运行完毕，那么时间片轮转法就退化为先来先服务算法。很显然，对用户的响应时间必然加长。如果时间片太短，CPU在进程间的切换工作就非常频繁，从而导致系统开销增加。因为在每个时间片末尾，都产生时钟中断，操作系统要处理这个中断，在把CPU分给另一个进程之前，要为“老”的进程保留全部寄存器的内容，还要为新选中的进程装配所有寄存器的值。这一工作无疑加大了系统开销。
时间片的长短通常由以下4个因素确定：
（1）系统的响应时间。在进程数目一定时，时间片的长短直接正比于系统对响应时间的要求。
（2）就绪队列进程的数目。当系统要求的响应时间一定时，时间片的大小反比于就绪队列中的进程数。