公平调度(fair-share scheduling)的进程调度算法：一、公平分享的调度策略 Linux 的调度算法是相对独立的一个模块，而且较容易理解。因此很多系统高手都爱对调度算法做改进。但是可以说调度器是一个非常神秘，难以捉摸的精灵。可能通过改变一个关键参数你就可以大大提高系统的效率。 对于一般进程，CPU的使用时间都是系统平均分配给每一个进程的，因此这种公平分享都是从进程的角度出发的。Bach在1986 年提出了公平分享调度策略（Fair_Share scheduling）来解决这个问题。和Linux 三种内建策略比，公平分享调度策略是一种更抽象的调度策略。它认为CPU应该根据拥有进程的组（对Linux 来说是用户）来分配时间，它实现了从用户角度考虑的公平原则。 由内核的结构来看，实现这个算法有很多种方式。我们可以在与调度相关的程序里做小小的改动来实现，如改动一些数据结构并改写schedule()函数。当然也可以做得很复杂，比如重写schedule()来实现所需要的结果。但是有一点我们是要必须牢记的，那就是大部分的Linux 核心都是以短小高效为最高目标。所以，改进的算法必须尽量向这个目标靠拢。二、新调度策略的实现：分析1、这里所说的‘组’的概念，在Linux 中是一个用户。我们所关心的是Linux 的用户，而不是UNIX 系统下的用户组或是别的什么概念。因此在公平共享调度策略中，一个进程能够分配到的时间与登录的系统用户数以及拥有该进程用户开辟进程数的多少有关。2、超级用户的进程是独立于公平分享算法的，因此它拥有的进程得到的调度时间应该和现在的进程调度算法分配时间相当。3、对于实时进程，调度算法仍旧给予比普通进程更高的优先权。不过也不用担心会花太多的时间去实现，只要在现在调度算法的基础上稍做改进就可以简单实现。4、新的调度算法对系统的吞吐量不能有太多的影响。比如说，如果定义的时间片少于2 个“滴答”，那么新实现的调度器效率将变得很差。因为过于频繁的进程切换将耗费大部分的系统时间，而真正用于程序计算的时间则排在第二位了。此条说明时间片的划分不能太小。5、我们所实现的算法并不需要绝对的公平，严格的平均是需要用效率为代价来换取的。如果算法过于精确，那就需要复杂的数据结构和耗时的计算过程，所以我们可以在以速度为第一原则的基础上实现“模糊”的公平分享。6、我们首先需要的是不断地思考和设计，只有将所有的问题都考虑清楚以后才可以开始动手。调度器是操作系统的核心，它将被频繁调用，因此其作用和影响也将是巨大的。我们要花费最小的代价实现算法，并且这种改动对系统核心的影响要降到最小。Linux的进程调度机制：概述：在多进程的操作系统中，进程调度是一个全局性的、关键性的问题。可以说，关于进程调度的研究是整个操作系统理论的核心，它对系统的总体设计、系统的实现、功能设置以及各方面的性能都有着决定性的影响。
1. 150ms：当系统中有大量进程共存时，根据测定，当每个用户可以接受的相应速度延迟超过１５０ms时，使用者就会明显地感觉到了。
2. 在设计一个进程调度机制时要考虑的具体问题主要有：
o 调度的时机：什么情况下、什么时候进行调度；
o 调度的政策：根据什么准则挑选下一个进入运行的进程；
o 调度的方式：是“可剥夺”还是“不可剥夺”。当正在运行的进程并不自愿暂时放弃对ＣＰＵ的使用权时，是否可以强制性地暂时剥夺其使用权，停止其运行而给其他进程一个机会。如果是可剥夺的，那么是否在任何条件下都可剥夺，有没有例外？
3. linux内核的调度机制：１）调度的时机： *首先，自愿的调度(主动调度)随时都可以进行：在内核里面，一个进程可以通过schedule()启动一次调度。也就是由当前进程自愿调用schedule()暂时放弃运行的情景。 *除此之外，调度还可以非自愿的，即强制地发生在每次从系统调用返回的前夕，以及每次从中断或者异常处理返回到用户空间的前夕。 上述红字说明：只有在用户空间（当ＣＰＵ在用户空间运行时）发生的中断或者异常才会引起调度。ret_from_exception: movl SYMBOL_NAME(bh_mask),%eax andl SYMBOL_NAME(bh_active),%eax jne handle_bottom_half ALIGNret_from_intr: GET_CURRENT(%ebx) movl EFLAGS(%esp),%eax # mix EFLAGS and CS movb CS(%esp),%al testl $(VM_MASK | 3),%eax # return to VM86 mode or non-supervisor? jne ret_with_reschedule jmp restore_all 从上述代码中(arch/i386/kernel/entry.S)，可以看出，转入ret_with_reschedule的条件为中断或异常发生前CPU的运行级别为３，即用户态。这一点(只有在用户空间发生的中断或者异常才会引起调度)对于系统的设计和实现有很重要的意义：因为这意味着当CPU在内核中运行时无需考虑强制调度的可能性。发生在系统空间中的中断或异常当然是可能的，但是这种中断或者异常不会引起调度。这使得内核的实现简化了，早期的Unix内核正是靠这个前提来简化其设计与实现的。否则的话，内核中所有可能为一个以上进程共享的变量和数据结构就全都要通过互斥机制(如信号量)加以保护，或者说放在临界区里面。即在内核中由于不会发生调度而无需考虑互斥。但是在多处理器SMP系统中，这种简化正在失去重要性：因为我们不得不考虑在另一个处理器上运行的进程访问共享资源的可能性。这样，不管在同一个CPU上是否可能在内核中发生调度，所有可能为多个进程(可能在不同的CPU上运行)共享的变量和数据结构，都得保护起来。这就是为什么读者在阅读代码时看到那么多的up()、down()等信号量操作或者加锁操作的原因。
注意：“从系统空间返回到用户空间”只是发生调度的必要条件，而不是充分条件。也就是说，这个条件满足了，调度并不是一定会发生的，具体是否发生调度还要判断当前进程的task_struct结构中的need_resched成员是否为非０，非０时才会转到reschedule处调用schedule():ret_with_reschedule: cmpl $0,need_resched(%ebx) jne reschedule cmpl $0,sigpending(%ebx) jne signal_return….reschedule: call SYMBOL_NAME(schedule) # test jmp ret_from_sys_callneed_resched成员是内核设置的，因为在用户空间是访问不到进程的task_struct结构的。除了当前进程通过系统调用自愿让出运行以及在系统调用中因某种原因受阻以外，主要就是当因某种原因唤醒一个进程的时候，以及在时钟中断服务程序发现当前进程已经连续运行太久的时候，内核会对need_resched成员进行设置(非０)，以重新调度。
２）调度的方式：Linux内核的调度方式可以说是“有条件的可剥夺”方式。＊当进程在用户空间运行时，无论自愿不自愿，一旦有必要(例如该进程已经运行了足够长的时间)，内核就可以暂时剥夺其运行而调度其他进程进入运行。＊但是，一旦进程进入了内核空间，或者说进入“系统态”。这时候，尽管内核知道应该要调度了，但是实际上调度并不会发生，直到该进程即将“下台”，也就是回到用户空间的前夕才能剥夺其运行权力。所以，linux的调度方式从原则上来说是可剥夺的，可是实际上由于调度时机的限制而变成了有条件的。３）调度策略： 基本上是从UNIX继承下来的以优先级为基础的调度。内核为系统中的每个进程计算出一个反映其运行“资格”的权值，然后挑选权值最高的进程投入运行。在运行的过程中，当前进程的资格(权值)随时间而递减，从而在下一次调度的时候原来资格较低的进程可能就更有资格运行了。到所有的进程的资格都变为０时，就重新计算一次所有进程的资格。 但是，为了适应各种不同应用的需要，内核在此基础上实现了三种不同的策略：SCHED_FIFO、SCHED_RR、SCHED_OTHER。每个进程都有自己适用的调度策略，并且，进程还可以通过系统调用sched_setscheduler()设定自己适用的调度策略。下面介绍一下他们的区别： SCHED_FIFO：适用于时间性要求比较强，但每次运行所需的时间比较短的进程，因此多用于实时进程； SCHED_RR:RR表示Round Robin，是轮流的意思(轮换调度)，这种策略适合比较大、也就是每次运行时间较长的程序。使用SCHED_RR策略地进程在schedule()调度中有一点特殊的处理。
上两者的比较：SCHED_FIFO、SCHED_RR都是基于优先级的调度策略，可是在怎样调度具有相同优先级的进程的问题上两者有区别： 调度策略为SCHED_FIFO的进程一旦受到调度而开始运行之后，就要一直运行到自愿让出或者被优先级更高的进程剥夺为止。对于每次受到调度时要求运行时间不长的进程，这样并不会有多大的影响。可是，如果是受到调度后可能执行很长时间的进程，这样就不公平了。这种不公正性是对具有相同优先级的进程而言的，同级的进程必须等待该进程自愿让出或者直到其运行结束。因为具有更高优先级的进程可以剥夺他的运行，而优先级则本来就没有机会运行，谈不上不公正。 所以，对于执行时间可能会很长的进程来说，应该使用SCHED_RR调度策略，这种策略在相同的优先级的进程上实行轮换调度。也就是说：对调度策略为SCHED_RR的进程有个时间配额，用完这个配额就要让具有相同优先级的其他就绪进程先运行。看schedule()的５４０行对调度策略为SCHED_RR的当前进程的处理。
SCHED_OTHER：是传统的调度策略，比较适合于交互式的分时应用。 问题：既然每个进程都有自己的适用的调度策略，内核怎样来调用使用不同调度策略的进程的呢？是根据什么挑选出下一个要运行的进程呢？ 实际上，挑选的原则最后还是归结到每个进程的权值，只不过是在计算资格的时候将适用的策略也考虑进去了，就好像考大学时符合某些特殊条件的考生会获得加分一样。同时，对于适用不同策略地进程的优先级别也加了限制。
4. 调度程序schedule()： 调度程序schedule()是一个非常频繁地执行的函数，因此要将运行效率放在第一位，函数中使用了很多的goto语句。 前面讲过，对schedule()只能由进程在内核中主动调用，或者在当前进程从系统空间返回用户空间的前夕被动的发生，而不能在一个中断服务程序的内部发生。即使一个中断服务程序有调度的要求，也只能通过把当前进程的need_resched字段设为１来表达这种要求，而不能直接调用schedule()。所以，如果在某个中断服务程序内部调用了schedule()，那一定是有问题的，所以转向scheduling_in_interrupt.(kernel/sched.c) asmlinkage void schedule(void)509 {510 struct schedule_data * sched_data;511 struct task_struct *prev, *next, *p;512 struct list_head *tmp;513 int this_cpu, c;514515 if (!current>active_mm) BUG();516 need_resched_back:517 prev = current;518 this_cpu = prev>processor;519520 if (in_interrupt())521 goto scheduling_in_interrupt;522523 release_kernel_lock(prev, this_cpu);524525 /* Do “administrative” work here while we don’t hold any locks */526 if (softirq_active(this_cpu) & softirq_mask(this_cpu)) /*检查是否有内核软中断服务请求在等待，若有，就转入handle_softirq为这些请求服务*/527 goto handle_softirq;528 handle_softirq_back:我们来看一下内核对这种问题的响应：[schedule()]686 scheduling_in_interrupt:687 printk(“Scheduling in interrupt/n”);688 BUG();689 return;内核对此的响应是显示或者在/var/log/messages文件末尾添上一条出错信息，然后执行一个宏操作BUG。接着往下看schedule()：如果有内核软中断服务请求在等待，那么就转入 handle_softirq： [schedule()]675 handle_softirq:676 do_softirq();677 goto handle_softirq_back;执行softirq队列完毕以后继续往下看： ==================== kernel/sched.c 528 541 ====================[schedule()]528 handle_softirq_back:529530 /*531 * ‘sched_data’ is protected by the fact that we can run532 * only one process per CPU.533 */534 sched_data = & aligned_data[this_cpu].schedule_data;535536 spin_lock_irq(&runqueue_lock);537538 /* move an exhausted RR process to be last.. */539 if (prev>policy == SCHED_RR)540 goto move_rr_last;541 move_rr_back:指针sched_data指向一个schedule_data数据结构，用来保存供下一次调度时使用的信息。此数据结构的定义如下：==================== kernel/sched.c 91 101 ====================91 /*92 * We align perCPUscheduling data on cacheline boundaries,93 * to prevent cacheline pingpong.94 */95 static union {96 struct schedule_data {97 struct task_struct * curr;98 cycles_t last_schedule;99 } schedule_data;100 char __pad [SMP_CACHE_BYTES];101 } aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0}}};这里的cycles_t实际上是无符号整数，用来记录调度发生的时间。这个数据结构是为多处理器SMP结构而设的，因此我们不必关心。数组中的第一个元素，即CPU0的schedule_data结构初始化为{&init_task,0}，其余的则全为｛０，０｝。代码中的__cacheline_aligned表示数据结构的起点应与高速缓存中的缓冲线对齐。下面就要涉及可执行进程队列了，所以先将这个队列锁住(536行)，以防止其他处理器的干扰。从538行开始：如果当前进程prev的调度策略是SCHED_RR，也就是轮换调度，那就要先进行一点特殊的处理(540 : goto move_rr_last;)。 （对使用SCHED_RR策略的当前进程的处理） ==================== kernel/sched.c 679 685 ====================[schedule()]679 move_rr_last:680 if (!prev>counter) {681 prev>counter = NICE_TO_TICKS(prev>nice);682 move_last_runqueue(prev);683 }684 goto move_rr_back;这里的prev>counter：代表这当前进程的运行时间配额，其数值在每次时钟中断时都要递减(update_process_times()中实现的)。因此，不管一个进程的时间配额有多高，随着运行时间的积累最终总会递减到０。对于调度策略为SCHED_RR的进程，一旦其时间配额降到０，就要从可执行进程队列runqueue中当前的位置上移动到队列的末尾，同时恢复其最初的时间配额（NICE_TO_TICKS），以等待下一次的调度。对于具有相同优先级的进程，调度的时候排在前面的进程优先，所以这使队列中具有相同优先级的其他进程有了优势。 宏操作NICE_TO_TICKS根据系统时钟的精度将进程的优先级别换算成可以运行的时间配额。在kernel/sched.c中定义。 将一个进程的task_struct结构从可执行队列中的当前位置移到队列的末尾是由move_last_runqueue()完成的(kernel/sched.c)。把进程移到可执行进程队列的末尾意味着：如果队列中没有资格更高的进程，但是有一个资格与之相同的进程存在，那么，这个资格虽然相同而排在前面的进程会被选中。继续看schedule()：==================== kernel/sched.c 541 553 ====================[schedule()]541 move_rr_back:542543 switch (prev>state) {544 case TASK_INTERRUPTIBLE:545 if (signal_pending(prev)) {546 prev>state = TASK_RUNNING;547 break;548 }549 default:550 del_from_runqueue(prev);551 case TASK_RUNNING:552 }553 prev>need_resched = 0;当前进程，就是正在执行的进程，当进入schedule()时其状态却不一定是TASK_RUNNING。例如：当前进程如已经在do_exit()中将其状态改成TASK_ZOMBIE，又如当前进程在sys_wait4()中调用schedule()时的状态为TASK_INTERRUPTIBLE。所以，这里的prev>state与其说是当前进程的状态不如说是其意愿。当其意愿既不是继续执行也不是可中断的睡眠时，就要通过del_from_runqueue()把这个进程从可执行队列中撤下来。另一方面，也可以看出TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE两种睡眠状态之间的区别：前者在进程有信号等待处理时要将其改成TASK_RUNNING，让其处理完这些信号再说，而后者则不受信号的影响。最后，将prev>need_resched恢复为０，因为所需求的调度已经在进行了。 下面的任务就是要挑选出一个进程来运行了(这一部分是很重要的，通过对就绪进程队列进行扫描)。==================== kernel/sched.c 555 576 ====================[schedule()]555 /*556 * this is the scheduler proper:557 */558559 repeat_schedule:560 /*561 * Default process to select..562 */563 next = idle_task(this_cpu);564 c = 1000;565 if (prev>state == TASK_RUNNING)566 goto still_running;567568 still_running_back:569 list_for_each(tmp, &runqueue_head) {570 p = list_entry(tmp, struct task_struct, run_list);571 if (can_schedule(p, this_cpu)) {572 int weight = goodness(p, this_cpu, prev>active_mm);573 if (weight > c)574 c = weight, next = p;575 }576 }在这段程序中，next总是指向已知最佳的候选进程，c则是这个进程的综合权值，或者是运行资格。挑选的过程是从idle进程即0号进程开始，其权值为－1000，这是可能的最低值，表示仅在没有其他进程可以运行时才会让他运行。 然后，遍历可执行队列runqueue中的每个进程(在单CPU系统中can_schedule()的返回值永远是1)，也就是一般操作系统书中所称的就绪进程。为每一个就绪进程通过函数goodness()计算出他当前所具有的权值，然后与当前的最高值c相比。注意这里的条件：weight > c，这意味着“先入为大”。也就是说，如果两个进程有相同的权值的话，排在队列前面的进程胜出，优先运行。
