- A+
一、调度算法的原理和分类
1.进程调度简介
进程调度的研究是整个操作系统理论的核心，在多进程的操作系统中，进程调度是一个全局性的、关键性的问题，它对系统的总体设计、系统的实现、功能设置以及各方面的性能都有着决定性的影响。进程运行需要各种各样的系统资源，如内存、文件、打印机和最宝贵的CPU等，所以说，调度的实质就是资源的分配。系统通过不同的调度算法(Scheduling Algorithm)来实现这种资源的分配。通常来说，选择什么样的调度算法取决于资源分配的策略(Scheduling Policy)。
Linux是一个支持多任务的操作系统，而多个任务之间的切换是通过调度器来完成，调度器使用不同的调度算法会有不同的效果。
Linux2.4版本使用的调度算法的时间复杂度为O(n),其主要原理是通过轮询所有可运行任务列表，然后挑选一个最合适的任务运行，所以其时间复杂度与可运行任务队列的长度成正比。
而Linux2.6开始替换成名为0(1)调度算法 ，顾名思义，其时间复杂度为0(1)。
此后，后面的版本开始使用CFS（Completely Fair Scheduler）调度算法。
Linux的CFS调度器抢占处理器的要求是：新进程消耗的使用比比当前进程小，则新进程立刻投入运行。否则，将推迟进行。
一个好的调度算法应当考虑以下几个方面：
（1）公平:保证每个进程得到合理的CPU时间。
（2）高效:使CPU保持忙碌状态，即总是有进程在CPU上运行。
（3）响应时间:使交互用户的响应时间尽可能短。
（4）周转时间:使批处理用户等待输出的时间尽可能短。
（5）吞吐量:使单位时间内处理的进程数量尽可能多。
很显然，这5个目标不可能同时达到，所以，不同的操作系统会在这几个方面中作出相应的取舍，从而确定自己的调度算法，例如UNIX采用动态优先数调度、5.3BSD采用多级反馈队列调度、Windows采用抢先多任务调度等。
2.按不同需求对调度的进程分类
第一种分类：
I/O-bound
1.频繁的进行I/O
2.通常会花费很多时间等待I/O操作的完成
CPU-bound
1.计算密集型
2.需要大量的CPU时间进行运算
前者需要更多的IO资源，比如多数的图形交互程序；后者则把时间花在了执行代码上。linux系统为了保证交互式应用和桌面的性能，更倾向于有限调度IO消耗型的进程。
第二种分类
交互式进程（interactive process）
1.需要经常与用户交互，因此要花很多时间等待用户输入操作
2.响应时间要快，平均延迟要低于50~150ms
3.典型的交互式程序：shell、文本编辑程序、图形应用程序等
批处理进程（batch process）
1.不必与用户交互，通常在后台运行
2.不必很快响应
3.典型的批处理程序：编译程序、科学计算
实时进程（real-time process）
1.有实时需求，不应被低优先级的进程阻塞
2.响应时间要短
3.典型的实时进程：视频/音频、机械控制等
对于实时进程，采用FIFO, Round Robin或者Earliest Deadline First (EDF)最早截止期限优先调度算法的调度策略.
Linux既支持普通的分时进程，也支持实时进程，Linux中的调度是多种调度策略和调度算法的混合。Linux的调度基于分时和优先级，随着版本的变化，分时技术在不断变化，优先级越来越复杂。Linux的进程根据优先级排队，根据特定的算法计算出进程的优先级，用一个值表示，这个值表示把进程如何适当的分配给CPU。，Linux中进程的优先级是动态的，调度程序会根据进程的行为周期性的调整进程的优先级，较长时间未分配到CPU的进程，通常优先级被提升，已经在CPU上运行了较长时间的进程，通常优先级被减低。
3.调度算法分类
（1）时间片轮转调度算法
时间片(Time Slice) 就是分配给进程运行的一段时间。在分时系统中，为了保证人机交互的及时性，系统使每个进程依次地按时间片轮流的方式执行，此时即应采用时间片轮转法进行调度。在通常的轮转法中，系统将所有的可运行(即就绪)进程按先来先服务的原则，排成一个队列， 每次调度时把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms不等。当执行的时间片用完时，系统发出信号，通知调度程序，调度程序便据此信号来停止该进程的执行，并将它送到运行队列的末尾，等待下一次执行。然后，把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证运行队列中的所有进程，在一个给定的时间( 人所能接受的等待时间)内，均能获得一时间片的处理机执行时间。
（2）优先权调度算法
为了照顾到紧迫型进程在进入系统后便能获得优先处理，引入了最高优先权调度算法。当将该算法用于进程调度时，系统将把处理机分配给运行队列中优先权最高的进程，这时，又可进一步把该算法分成两种方式。
(a)非抢占式优先权算法(又称不可剥夺调度，Nonpreemptive Scheduling) 在这种方式下，系统一旦将处理机(CPU) 分配给运行队列中优先权最高的进程后，该机分配给另一个优先权高的进程。这种调度算法主要用于批处理系统中，也可用于某些对实时性要求不严的实时系统中。
(b)抢占式优先权调度算法(又称可剥夺调度，Preemptive Scheduling) 该算法的本质就是系统中当前运行的进程永远是可运行进程中优先权最高的那个。在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但是只要一出现了另一个优先权更高的进程时，调度程序就暂停原最高优先权进程的执行，而将处理机分配给新出现的优先权最高的进程，即剥夺当前进程的运行。因此，在采用这种调度算法时，每当出现一新的可运行进程，就将它和当前运行进程进行优先权比较，如果高于当前进程，将触发进程调度。 这种方式的优先权调度算法，能更好的满足紧迫进程的要求，故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。Linux 也采用这种调度算法。
(3)多级反馈队列调度
其本质是:综合了时间片轮转调度和抢占式优先权调度的优点，即:优先权高的进程先运行给定的时间片，相同优先权的进程轮流运行给定的时间片。
(4)实时调度
最后我们来看一下实时系统中的调度。什么叫实时系统，就是系统对外部事件有求必应、尽快响应。在实时系统中存在有若干个实时进程或任务，它们用来反应或控制某个(些)外部事件，往往带有某种程度的紧迫性，因而对实时系统中的进程调度有某些特殊要求。在实时系统中，广泛采用抢占调度方式，特别是对于那些要求严格的实时系统。因为这种调度方式既具有较大的灵活性，又能获得很小的调度延迟;但是这种调度方式也比较复杂。
二、调度的时机
进程调度的Linux 的调度程序是一个叫Schedule()的函数，这个函数被调用的频率很高，由它来决定是否要进行进程的切换，如果要切换的话，切换到哪个进程等。我们先来看在什么情况下要执行调度程序，我们把这种情况叫做调度时机。Linux调度时机主要分两种情况：主动调度和被动调度。
Linux 调度时机主要有：
(1）进程状态转换的时刻:进程终止、进程睡眠;
(2）当前进程的时间片用完时(current->counter=0） ;
(3）设备驱动程序;
(4）进程从中断、异常及系统调用返回到用户态时。
时机1，进程要调用sleep()或exit()等函数进行状态转换，这些函数会主动调用调度程序进行进程调度。
时机2，由于进程的时间片是由时钟中断来更新的，如同时机4。
时机3，当设备驱动程序执行长而重复的任务时，直接调用调度程序。在每次反复循环中，驱动程序都检查need_resched的值，如果必要，则调用调度程序schedule()主动放弃CPU。
时机4，如前所述，不管是从中断、异常还是系统调用返回，最终都调用ret_from_sys_call()，由这个函数进行调度标志的检测，如果必要，则调用调度程序。那么，为什么从系统调用返回时要调用调度程序呢﹖这当然是从效率考虑。从系统调用返回意味着要离开内核态而返回到用户态，而状态的转换要花费一定的时间，因此，在返回到用户态前，系统把在内核态该处理的事全部做完。
三、调度的依据
在linux2.4.16中，调度程序运行时，要在所有处于可运行状态的进程之中选择最值得运行的进程投入运行。选择进程的依据是什么呢?在每个进程的task_struct结构中有如下5项:need_resched、 nice、counter、 policy 及rt_priority
（1）need_resched:在调度时机到来时,检测这个域的值,如果为1,则调用schedule()。
（2） counter:进程处于运行状态时所剩余的时钟滴答数，每次时钟中断到来时，这个值就减1。当这个域的值变得越来越小，直至为0时，就把need_resched域置1，因此，也把这个域叫做进程的“动态优先级”。
（3）nice:进程的“静态优先级”，这个域决定 counter的初值。只有通过 nice()、POSIX.1b sched_setparam()或5.4BSD/SVR4 setpriority()系统调用才能改变进程的静态优先级。
（4） rt_priority:实时进程的优先级
（5）policy:从整体上区分实时进程和普通进程，因为实时进程和普通进程的调度是不同的，它们两者之间，实时进程应该先于普通进程而运行，可以通过系统调用sched_setscheduler ( )来改变调度的策略。对于同一类型的不同进程，采用不同的标准来选择进程。对于普通进程，选择进程的主要依据为counter和nice。对于实时进程，Linux采用了两种调度策略，即FIFO（先来先服务调度）和RR(时间片轮转调度)。因为实时进程具有一定程度的紧迫性，所以衡量一个实时进程是否应该运行，Linux采用了一个比较固定的标准。实时进程的counter只是用来表示该进程的剩余滴答数，并不作为衡量它是否值得运行的标准，这和普通进程是有区别的。
与其他操作系统一样，Linux的时间单位也是“时钟滴答”，只是不同的操作系统对一个时钟滴答的定义不同而已(Linux设计者将一个“时钟滴答”定义为10ms)。在这里，我们把counter叫做进程的时间片，但实际上它仅仅是时钟滴答的个数，例如，若counter为5，则分配给该进程的时间片就为5个时钟滴答，也就是5*10ms=50ms，实际上，Linux 2.4中给进程初始时间片的大小就是50ms。
函数goodness()就是用来衡量一个处于可运行状态的进程值得运行的程度。该函数综合使用了上面我们提到的5项，给每个处于可运行状态的进程赋予一个权值(weight)，调度程序以这个权值作为选择进程的唯一依据。函数主体如下:
将函数goodness（）简化如下：
在sched.h中对调度策略定义如下：
这个goodness（）函数比较很简单。首先，根据 policy区分实时进程和普通进程。实时进程的权值取决于其实时优先级，其至少是1000，与conter和nice无关。
普通进程的权值需特别说明如下两点。
(1）为什么进行细微的调整﹖如果p->mm为空，则意味着该进程无用户空间（例如内核线程），则无需切换到用户空间。如果 p->mm=this_mm，则说明该进程的用户空间就是当前进程的用户空间，该进程完全有可能再次得到运行。对于以上两种情况，都给其权值加 1，算是对它们小小的“奖励”。
(2）进程的优先级nice是从早期UNIX沿用下来的负向优先级，其数值标志“谦让”的程度，其值越大，就表示其越“谦让”，也就是优先级越低，其取值范围为一20~~19，因此，（20-p->nice）的取值范围就是0~40。可以看出，普通进程的权值不仅考虑了其剩余的时间片，还考虑了其优先级，优先级越高，其权值越大。
有了衡量进程是否应该运行的标准，选择进程就是轻而易举的事情了，“弱肉强食”，谁的权值大谁就先运行。根据进程调度的依据，调度程序就可以控制系统中的所有处于可运行状态的进程并在它们之间进行选择。
四、调度的实现
1.Linux2.4.16版本
在linux2.4.16中调度的实现具体过程如下：
为了讨论方便﹐我们同样对其进行了简化,略去对SMP的实现部分。
如果当前进程既没有自己的地址空间,也没有向别的进程借用地址空间,那肯定出错。另外，如果schedule()在中断服务程序内部执行,那也出错。
对当前进程做相关处理，为选择下一个进程做好准备。当前进程就是正在运行着的进程，可是，当进入schedule()时，其状态却不一定是TASK_RUNNIG，例如，在exit()系统调用中，当前进程的状态可能已被改为TASK_ZOMBE;又例如，在wait4()系统调用中，当前进程的状态可能被置为TASK_INTERRUPTIBLE。因此，如果当前进程处于这些状态中的一种，就要把它从运行队列中删除。从运行队列中选择最值得运行的进程，也就是权值最大的进程。
如果已经选择的进程其权值为0，说明运行队列中所有进程的时间片都用完了(队列中肯定没有实时进程，因为其最小权值为1000)，因此，重新计算所有进程的时间片，其中宏操作NICE_TO_TICKS 就是把优先级nice转换为时钟滴答。
进程地址空间的切换。如果新进程有自己的用户空间，也就是说，如果next->mm 与next->active_mm相同，那么，switch_mm ( ）函数就把该进程从内核空间切换到用户空间，也就是加载next的页目录。如果新进程无用户空间(next->mm为空），也就是说，如果它是一个内核线程，那它就要在内核空间运行，因此，需要借用前一个进程（prev)的地址空间，因为所有进程的内核空间都是共享的，因此，这种借用是有效的。用宏switch_to()进行真正的进程切换。
2.Linux2.6.23版本
O(1)调度算法：
O(1)调度算法通过优先级来对任务进行分组，可分为140个优先级(0～139，数值越小优先级越高），每个优先级的任务由一个队列来维护。prio_array 结构就是用来维护这些任务队列，如下代码:
下面介绍prio_array结构各个字段的作用:
- nr_active:所有优先级队列中的总任务数。
- bitmap:位图，每个位对应一个优先级的任务队列，用于记录哪个任务队列不为空，能通过bitmap够快速找到不为空的任务队列。
- queue:优先级队列数组，每个元素维护一个优先级队列，比如索引为0的元素维护着优先级为0的任务队列。
下图更直观地展示了prio_array结构各个字段的关系:
如图所述， bitmap的第2位和第6位为1(红色代表为1，白色代表为0)，表示优先级为2和6的任务队列不为空，也就是说queue数组的第2个元素和第6个元素的队列不为空。
runqueue结构:
另外，为了减少多核CPU之间的竞争，所以每个CPU都需要维护―份本地的优先队列。因为如果使用全局的优先队列，那么多核CPU就需要对全局优先队列进行上锁，从而导致性能下降。每个CPU都需要维护一个runqueue结构，runqueue结构主要维护任务调度相关的信息，比如优先队列、调度次数、CPU负载信息等。其定义如下:
runqueue结构有两个重要的字段: active和expired ，这两个字段在o(1)调度算法中起着至关重要的作用。我们先来了解一下o(1)调度算法的大概原理。我们注意到active和expired字段的类型为prio_array，指向任务优先队列。active代表可以调度的任务队列，而expired字段代表时间片已经用完的任务队列。active和expired会进行以下两个过程:1.当active中的任务时间片用完，那么就会被移动到expired中。2.当active中已经没有任务可以运行，就把expired 与active交换，从而expired中的任务可以重新被调度。如下图所示：
0(1)调度算法把140个优先级的前100个(0 -99)作为实时进程优先级，而后40个(100 -139）作为普通进程优先级。实时进程被放置到实时进程优先级的队列中，而普通进程放置到普通进程优先级的队列中。
实时进程调度：实时进程分为FIFo（先进先出)和RR（时间轮询)两种。
普通进程调度：每个进程都要一个动态优先级和静态优先级，静态优先级不会变化(进程创建时被设置)，而动态优先级会随着进程的睡眠时间而发生变化。动态优先级可以通过以下公式进行计算:
上面公式的bonus（奖励或惩罚)是通过进程的睡眠时间计算出来，进程的睡眠时间越大，bonus的值就 越大，那么动态优先级就越高（前面说过优先级的值越小，优先级越高)。
当一个普通进程被添加到运行队列时，会先计算其动态优先级，然后按照动态优先级的值来添加到对应优先级的队列中。而调度器调度进程时，会先选择优先级最高的任务队列中的进程进行调度运行。
运行时间片计算：当进程的时间用完后，就需要重新进行计算。进程的运行时间片与静态优先级有关，可以通过以下公式进行计算:
0(1)调度算法的具体实现：
时钟中断是由硬件触发的，可以通过编程来设置其频率，Linux内核一般设置为每秒产生100 ～1000次。时钟中断会触发调用scheduler_tick()内核函数，其主要工作是:减少进程的可运行时间片，如果时间片用完，那么把进程从active队列移动到expired队列中。代码如下:
代码主要完成以下几个工作:
1.减少进程的时间片，并且判断时间片是否已经使用完。
2.如果时间片使用完，那么把进程从active队列中删除。
3.调用set_tsk_need_resched()函数设TIF_NEED_RESCHED标志，表示当前进程需要重新调度。
4.调用effective_prio()函数重新计算进程的动态优先级。
5.调用task_timeslice()函数重新计算进程的可运行时间片。
6.如果当前进程是交互进程或者出来饥饿状态，那么重新加入到active队列。
7.否则移动到expired 队列。
如果进程设置了TIF_NEED_RESCHED标志，那么当从时钟中断返回到用户空间时，会调用schedule()函数进行任务调度。schedule()函数代码如下:
代码主要完成以下几个工作:
1.如果当前runqueue的active队列为空，那么把active队列与expired 队列进行交换。
2.调用sched_find_first_bit()函数在bitmap中找到优先级最高并且不为空的任务队列索引。
3.减少当前进程的睡眠时间。
4.调用context_switch()函数切换到next进程进行运行。
小结
在Linux 2.4中用户进程数越多，系统开销越大；而Linux 2.6系统开销并不随用户进程数增加而增加。Linux 2.6调度程序比Linux 2.4有了很大的改进，做到了调度程序算法复杂度与系统负载无关，但对于实时进程的调度性能的改变还是不大，仅仅实现了内核抢占调度，离真正的实时性还有一定的距离。
