精华内容
下载资源
问答
  • Linux进程调度

    千次阅读 2014-09-19 18:30:02
    Linux进程调度的目标  1.高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,所以调度程序要尽可能的高效;  2.加强交互性能:在系统相当的负载下,也要保证系统的响应时间;  ...

     Linux进程调度的目标

        1.高效性:高效意味着在相同的时间下要完成更多的任务。调度程序会被频繁的执行,所以调度程序要尽可能的高效;

        2.加强交互性能:在系统相当的负载下,也要保证系统的响应时间;

        3.保证公平和避免饥渴;

        4.SMP调度:调度程序必须支持多处理系统;

        5.软实时调度:系统必须有效的调用实时进程,但不保证一定满足其要求;

    Linux进程优先级

      进程提供了两种优先级,一种是普通的进程优先级,第二个是实时优先级。前者适用SCHED_NORMAL调度策略,后者可选SCHED_FIFO或SCHED_RR调度策略。任何时候,实时进程的优先级都高于普通进程,实时进程只会被更高级的实时进程抢占,同级实时进程之间是按照FIFO(一次机会做完)或者RR(多次轮转)规则调度的。

      首先,说下实时进程的调度

      实时进程,只有静态优先级,因为内核不会再根据休眠等因素对其静态优先级做调整,其范围在0~MAX_RT_PRIO-1间。默认MAX_RT_PRIO配置为100,也即,默认的实时优先级范围是0~99。而nice值,影响的是优先级在MAX_RT_PRIO~MAX_RT_PRIO+40范围内的进程。

      不同与普通进程,系统调度时,实时优先级高的进程总是先于优先级低的进程执行。知道实时优先级高的实时进程无法执行。实时进程总是被认为处于活动状态。如果有数个 优先级相同的实时进程,那么系统就会按照进程出现在队列上的顺序选择进程。假设当前CPU运行的实时进程A的优先级为a,而此时有个优先级为b的实时进程B进入可运行状态,那么只要b<a,系统将中断A的执行,而优先执行B,直到B无法执行(无论A,B为何种实时进程)。

       不同调度策略的实时进程只有在相同优先级时才有可比性:

       1. 对于FIFO的进程,意味着只有当前进程执行完毕才会轮到其他进程执行。由此可见相当霸道。

       2. 对于RR的进程。一旦时间片消耗完毕,则会将该进程置于队列的末尾,然后运行其他相同优先级的进程,如果没有其他相同优先级的进程,则该进程会继续执行。

       总而言之,对于实时进程,高优先级的进程就是大爷。它执行到没法执行了,才轮到低优先级的进程执行。等级制度相当森严啊。

      重头戏,说下非实时进程调度

      引子 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    将当前目录下的documents目录打包,但不希望tar占用太多CPU:
     
    nice -19 tar zcf pack.tar.gz documents
     
    这个“-19”中的“-”仅表示参数前缀;所以,如果希望赋予tar进程最高的优先级,则执行:
     
    nice --19 tar zcf pack.tar.gz documents
     
    也可修改已经存在的进程的优先级:
     
    将PID为1799的进程优先级设置为最低:
     
    renice 19 1799
     
    renice命令与nice命令的优先级参数的形式是相反的,直接以优先级值作为参数即可,无“-”前缀说法。

       言归正传

        Linux对普通的进程,根据动态优先级进行调度。而动态优先级是由静态优先级(static_prio)调整而来。Linux下,静态优先级是用户不可见的,隐藏在内核中。而内核提供给用户一个可以影响静态优先级的接口,那就是nice值,两者关系如下:

      static_prio=MAX_RT_PRIO +nice+ 20

      nice值的范围是-20~19,因而静态优先级范围在100~139之间。nice数值越大就使得static_prio越大,最终进程优先级就越低。

      ps -el 命令执行结果:NI列显示的每个进程的nice值,PRI是进程的优先级(如果是实时进程就是静态优先级,如果是非实时进程,就是动态优先级)  

      而进程的时间片就是完全依赖 static_prio 定制的,见下图,摘自《深入理解linux内核》,

      

       我们前面也说了,系统调度时,还会考虑其他因素,因而会计算出一个叫进程动态优先级的东西,根据此来实施调度。因为,不仅要考虑静态优先级,也要考虑进程的属性。例如如果进程属于交互式进程,那么可以适当的调高它的优先级,使得界面反应地更加迅速,从而使用户得到更好的体验。Linux2.6 在这方面有了较大的提高。Linux2.6认为,交互式进程可以从平均睡眠时间这样一个measurement进行判断。进程过去的睡眠时间越多,则越有可能属于交互式进程。则系统调度时,会给该进程更多的奖励(bonus),以便该进程有更多的机会能够执行。奖励(bonus)从0到10不等。

      系统会严格按照动态优先级高低的顺序安排进程执行。动态优先级高的进程进入非运行状态,或者时间片消耗完毕才会轮到动态优先级较低的进程执行。动态优先级的计算主要考虑两个因素:静态优先级,进程的平均睡眠时间也即bonus。计算公式如下,

         dynamic_prio = max (100, min (static_prio - bonus + 5, 139))

      在调度时,Linux2.6 使用了一个小小的trick,就是算法中经典的空间换时间的思想[还没对照源码确认],使得计算最优进程能够在O(1)的时间内完成。

      为什么根据睡眠和运行时间确定奖惩分数是合理的

      睡眠和CPU耗时反应了进程IO密集和CPU密集两大瞬时特点,不同时期,一个进程可能即是CPU密集型也是IO密集型进程。对于表现为IO密集的进程,应该经常运行,但每次时间片不要太长。对于表现为CPU密集的进程,CPU不应该让其经常运行,但每次运行时间片要长。交互进程为例,假如之前其其大部分时间在于等待CPU,这时为了调高相应速度,就需要增加奖励分。另一方面,如果此进程总是耗尽每次分配给它的时间片,为了对其他进程公平,就要增加这个进程的惩罚分数。可以参考CFS的virtutime机制.

    现代方法CFS

      不再单纯依靠进程优先级绝对值,而是参考其绝对值,综合考虑所有进程的时间,给出当前调度时间单位内其应有的权重,也就是,每个进程的权重X单位时间=应获cpu时间,但是这个应得的cpu时间不应太小(假设阈值为1ms),否则会因为切换得不偿失。但是,当进程足够多时候,肯定有很多不同权重的进程获得相同的时间——最低阈值1ms,所以,CFS只是近似完全公平。

        详情参考 《linux内核cfs浅析

    Linux进程状态机

     

      

     

      进程是通过fork系列的系统调用(fork、clone、vfork)来创建的,内核(或内核模块)也可以通过kernel_thread函数创建内核进程。这些创建子进程的函数本质上都完成了相同的功能——将调用进程复制一份,得到子进程。(可以通过选项参数来决定各种资源是共享、还是私有。)
    那么既然调用进程处于TASK_RUNNING状态(否则,它若不是正在运行,又怎么进行调用?),则子进程默认也处于TASK_RUNNING状态。
    另外,在系统调用clone和内核函数kernel_thread也接受CLONE_STOPPED选项,从而将子进程的初始状态置为 TASK_STOPPED。

       进程创建后,状态可能发生一系列的变化,直到进程退出。而尽管进程状态有好几种,但是进程状态的变迁却只有两个方向——从TASK_RUNNING状态变为非TASK_RUNNING状态、或者从非TASK_RUNNING状态变为TASK_RUNNING状态。总之,TASK_RUNNING是必经之路,不可能两个非RUN状态直接转换。

    也就是说,如果给一个TASK_INTERRUPTIBLE状态的进程发送SIGKILL信号,这个进程将先被唤醒(进入TASK_RUNNING状态),然后再响应SIGKILL信号而退出(变为TASK_DEAD状态)。并不会从TASK_INTERRUPTIBLE状态直接退出。

        进程从非TASK_RUNNING状态变为TASK_RUNNING状态,是由别的进程(也可能是中断处理程序)执行唤醒操作来实现的。执行唤醒的进程设置被唤醒进程的状态为TASK_RUNNING,然后将其task_struct结构加入到某个CPU的可执行队列中。于是被唤醒的进程将有机会被调度执行。

       而进程从TASK_RUNNING状态变为非TASK_RUNNING状态,则有两种途径:

      1、响应信号而进入TASK_STOPED状态、或TASK_DEAD状态;
      2、执行系统调用主动进入TASK_INTERRUPTIBLE状态(如nanosleep系统调用)、或TASK_DEAD状态(如exit系统调用);或由于执行系统调用需要的资源得不到满     足,而进入TASK_INTERRUPTIBLE状态或TASK_UNINTERRUPTIBLE状态(如select系统调用)。
      显然,这两种情况都只能发生在进程正在CPU上执行的情况下。

     通过ps命令我们能够查看到系统中存在的进程,以及它们的状态:

    R(TASK_RUNNING),可执行状态。

    只有在该状态的进程才可能在CPU上运行。而同一时刻可能有多个进程处于可执行状态,这些进程的task_struct结构(进程控制块)被放入对应CPU的可执行队列中(一个进程最多只能出现在一个CPU的可执行队列中)。进程调度器的任务就是从各个CPU的可执行队列中分别选择一个进程在该CPU上运行。
    只要可执行队列不为空,其对应的CPU就不能偷懒,就要执行其中某个进程。一般称此时的CPU“忙碌”。对应的,CPU“空闲”就是指其对应的可执行队列为空,以致于CPU无事可做。
    有人问,为什么死循环程序会导致CPU占用高呢?因为死循环程序基本上总是处于TASK_RUNNING状态(进程处于可执行队列中)。除非一些非常极端情况(比如系统内存严重紧缺,导致进程的某些需要使用的页面被换出,并且在页面需要换入时又无法分配到内存……),否则这个进程不会睡眠。所以CPU的可执行队列总是不为空(至少有这么个进程存在),CPU也就不会“空闲”。

    很多操作系统教科书将正在CPU上执行的进程定义为RUNNING状态、而将可执行但是尚未被调度执行的进程定义为READY状态,这两种状态在linux下统一为 TASK_RUNNING状态。

    S(TASK_INTERRUPTIBLE),可中断的睡眠状态。

    处于这个状态的进程因为等待某某事件的发生(比如等待socket连接、等待信号量),而被挂起。这些进程的task_struct结构被放入对应事件的等待队列中。当这些事件发生时(由外部中断触发、或由其他进程触发),对应的等待队列中的一个或多个进程将被唤醒。

    通过ps命令我们会看到,一般情况下,进程列表中的绝大多数进程都处于TASK_INTERRUPTIBLE状态(除非机器的负载很高)。毕竟CPU就这么一两个,进程动辄几十上百个,如果不是绝大多数进程都在睡眠,CPU又怎么响应得过来。

    D(TASK_UNINTERRUPTIBLE),不可中断的睡眠状态。

    与TASK_INTERRUPTIBLE状态类似,进程处于睡眠状态,但是此刻进程是不可中断的。不可中断,指的并不是CPU不响应外部硬件的中断,而是指进程不响应异步信号。
    绝大多数情况下,进程处在睡眠状态时,总是应该能够响应异步信号的。否则你将惊奇的发现,kill -9竟然杀不死一个正在睡眠的进程了!于是我们也很好理解,为什么ps命令看到的进程几乎不会出现TASK_UNINTERRUPTIBLE状态,而总是TASK_INTERRUPTIBLE状态。

    而TASK_UNINTERRUPTIBLE状态存在的意义就在于,内核的某些处理流程是不能被打断的。如果响应异步信号,程序的执行流程中就会被插入一段用于处理异步信号的流程(这个插入的流程可能只存在于内核态,也可能延伸到用户态),于是原有的流程就被中断了(参见《linux异步信号handle浅析》)。
    在进程对某些硬件进行操作时(比如进程调用read系统调用对某个设备文件进行读操作,而read系统调用最终执行到对应设备驱动的代码,并与对应的物理设备进行交互),可能需要使用TASK_UNINTERRUPTIBLE状态对进程进行保护,以避免进程与设备交互的过程被打断,造成设备陷入不可控的状态。(比如read系统调用触发了一次磁盘到用户空间的内存的DMA,如果DMA进行过程中,进程由于响应信号而退出了,那么DMA正在访问的内存可能就要被释放了。)这种情况下的TASK_UNINTERRUPTIBLE状态总是非常短暂的,通过ps命令基本上不可能捕捉到。

    linux系统中也存在容易捕捉的TASK_UNINTERRUPTIBLE状态。执行vfork系统调用后,父进程将进入TASK_UNINTERRUPTIBLE状态,直到子进程调用exit或exec。
    通过下面的代码就能得到处于TASK_UNINTERRUPTIBLE状态的进程:
    #include <unistd.h>
    void main() {
    if (!vfork()) sleep(100);
    }
    编译运行,然后ps一下:
    kouu@kouu-one:~/test$ ps -ax | grep a\.out
    4371 pts/0 D+ 0:00 ./a.out
    4372 pts/0 S+ 0:00 ./a.out
    4374 pts/1 S+ 0:00 grep a.out
    然后我们可以试验一下TASK_UNINTERRUPTIBLE状态的威力。不管kill还是kill -9,这个TASK_UNINTERRUPTIBLE状态的父进程依然屹立不倒。

    T(TASK_STOPPED or TASK_TRACED),暂停状态或跟踪状态。

    向进程发送一个SIGSTOP信号,它就会因响应该信号而进入TASK_STOPPED状态(除非该进程本身处于TASK_UNINTERRUPTIBLE状态而不响应信号)。(SIGSTOP与SIGKILL信号一样,是非常强制的。不允许用户进程通过signal系列的系统调用重新设置对应的信号处理函数。)
    向进程发送一个SIGCONT信号,可以让其从TASK_STOPPED状态恢复到TASK_RUNNING状态。

    当进程正在被跟踪时,它处于TASK_TRACED这个特殊的状态。“正在被跟踪”指的是进程暂停下来,等待跟踪它的进程对它进行操作。比如在gdb中对被跟踪的进程下一个断点,进程在断点处停下来的时候就处于TASK_TRACED状态。而在其他时候,被跟踪的进程还是处于前面提到的那些状态。
    对于进程本身来说,TASK_STOPPED和TASK_TRACED状态很类似,都是表示进程暂停下来。
    而TASK_TRACED状态相当于在TASK_STOPPED之上多了一层保护,处于TASK_TRACED状态的进程不能响应SIGCONT信号而被唤醒。只能等到调试进程通过ptrace系统调用执行PTRACE_CONT、PTRACE_DETACH等操作(通过ptrace系统调用的参数指定操作),或调试进程退出,被调试的进程才能恢复TASK_RUNNING状态。

    Z(TASK_DEAD - EXIT_ZOMBIE),退出状态,进程成为僵尸进程。

    进程在退出的过程中,处于TASK_DEAD状态。

    在这个退出过程中,进程占有的所有资源将被回收,除了task_struct结构(以及少数资源)以外。于是进程就只剩下task_struct这么个空壳,故称为僵尸。
    之所以保留task_struct,是因为task_struct里面保存了进程的退出码、以及一些统计信息。而其父进程很可能会关心这些信息。比如在shell中,$?变量就保存了最后一个退出的前台进程的退出码,而这个退出码往往被作为if语句的判断条件。
    当然,内核也可以将这些信息保存在别的地方,而将task_struct结构释放掉,以节省一些空间。但是使用task_struct结构更为方便,因为在内核中已经建立了从pid到task_struct查找关系,还有进程间的父子关系。释放掉task_struct,则需要建立一些新的数据结构,以便让父进程找到它的子进程的退出信息。

    父进程可以通过wait系列的系统调用(如wait4、waitid)来等待某个或某些子进程的退出,并获取它的退出信息。然后wait系列的系统调用会顺便将子进程的尸体(task_struct)也释放掉。
    子进程在退出的过程中,内核会给其父进程发送一个信号,通知父进程来“收尸”。这个信号默认是SIGCHLD,但是在通过clone系统调用创建子进程时,可以设置这个信号。

    通过下面的代码能够制造一个EXIT_ZOMBIE状态的进程:
    #include <unistd.h>
    void main() {
    if (fork())
    while(1) sleep(100);
    }
    编译运行,然后ps一下:
    kouu@kouu-one:~/test$ ps -ax | grep a\.out
    10410 pts/0 S+ 0:00 ./a.out
    10411 pts/0 Z+ 0:00 [a.out] <defunct>
    10413 pts/1 S+ 0:00 grep a.out

    只要父进程不退出,这个僵尸状态的子进程就一直存在。那么如果父进程退出了呢,谁又来给子进程“收尸”?
    当进程退出的时候,会将它的所有子进程都托管给别的进程(使之成为别的进程的子进程)。托管给谁呢?可能是退出进程所在进程组的下一个进程(如果存在的话),或者是1号进程。所以每个进程、每时每刻都有父进程存在。除非它是1号进程。

    1号进程,pid为1的进程,又称init进程。
    linux系统启动后,第一个被创建的用户态进程就是init进程。它有两项使命:
    1、执行系统初始化脚本,创建一系列的进程(它们都是init进程的子孙);
    2、在一个死循环中等待其子进程的退出事件,并调用waitid系统调用来完成“收尸”工作;
    init进程不会被暂停、也不会被杀死(这是由内核来保证的)。它在等待子进程退出的过程中处于TASK_INTERRUPTIBLE状态,“收尸”过程中则处于TASK_RUNNING状态。

    X(TASK_DEAD - EXIT_DEAD),退出状态,进程即将被销毁。

    而进程在退出过程中也可能不会保留它的task_struct。比如这个进程是多线程程序中被detach过的进程(进程?线程?参见《linux线程浅析》)。或者父进程通过设置SIGCHLD信号的handler为SIG_IGN,显式的忽略了SIGCHLD信号。(这是posix的规定,尽管子进程的退出信号可以被设置为SIGCHLD以外的其他信号。)
    此时,进程将被置于EXIT_DEAD退出状态,这意味着接下来的代码立即就会将该进程彻底释放。所以EXIT_DEAD状态是非常短暂的,几乎不可能通过ps命令捕捉到。

     

    一些重要的杂项

    调度程序的效率
    “优先级”明确了哪个进程应该被调度执行,而调度程序还必须要关心效率问题。调度程序跟内核中的很多过程一样会频繁被执行,如果效率不济就会浪费很多CPU时间,导致系统性能下降。
    在linux 2.4时,可执行状态的进程被挂在一个链表中。每次调度,调度程序需要扫描整个链表,以找出最优的那个进程来运行。复杂度为O(n);
    在linux 2.6早期,可执行状态的进程被挂在N(N=140)个链表中,每一个链表代表一个优先级,系统中支持多少个优先级就有多少个链表。每次调度,调度程序只需要从第一个不为空的链表中取出位于链表头的进程即可。这样就大大提高了调度程序的效率,复杂度为O(1);
    在linux 2.6近期的版本中,可执行状态的进程按照优先级顺序被挂在一个红黑树(可以想象成平衡二叉树)中。每次调度,调度程序需要从树中找出优先级最高的进程。复杂度为O(logN)。

    那么,为什么从linux 2.6早期到近期linux 2.6版本,调度程序选择进程时的复杂度反而增加了呢?
    这是因为,与此同时,调度程序对公平性的实现从上面提到的第一种思路改变为第二种思路(通过动态调整优先级实现)。而O(1)的算法是基于一组数目不大的链表来实现的,按我的理解,这使得优先级的取值范围很小(区分度很低),不能满足公平性的需求。而使用红黑树则对优先级的取值没有限制(可以用32位、64位、或更多位来表示优先级的值),并且O(logN)的复杂度也还是很高效的。

    调度触发的时机
    调度的触发主要有如下几种情况:
    1、当前进程(正在CPU上运行的进程)状态变为非可执行状态。
    进程执行系统调用主动变为非可执行状态。比如执行nanosleep进入睡眠、执行exit退出、等等;
    进程请求的资源得不到满足而被迫进入睡眠状态。比如执行read系统调用时,磁盘高速缓存里没有所需要的数据,从而睡眠等待磁盘IO;
    进程响应信号而变为非可执行状态。比如响应SIGSTOP进入暂停状态、响应SIGKILL退出、等等;

    2、抢占。进程运行时,非预期地被剥夺CPU的使用权。这又分两种情况:进程用完了时间片、或出现了优先级更高的进程。
    优先级更高的进程受正在CPU上运行的进程的影响而被唤醒。如发送信号主动唤醒,或因为释放互斥对象(如释放锁)而被唤醒;
    内核在响应时钟中断的过程中,发现当前进程的时间片用完;
    内核在响应中断的过程中,发现优先级更高的进程所等待的外部资源的变为可用,从而将其唤醒。比如CPU收到网卡中断,内核处理该中断,发现某个socket可读,于是唤醒正在等待读这个socket的进程;再比如内核在处理时钟中断的过程中,触发了定时器,从而唤醒对应的正在nanosleep系统调用中睡眠的进程;

    内核抢占
    理想情况下,只要满足“出现了优先级更高的进程”这个条件,当前进程就应该被立刻抢占。但是,就像多线程程序需要用锁来保护临界区资源一样,内核中也存在很多这样的临界区,不大可能随时随地都能接收抢占。
    linux 2.4时的设计就非常简单,内核不支持抢占。进程运行在内核态时(比如正在执行系统调用、正处于异常处理函数中),是不允许抢占的。必须等到返回用户态时才会触发调度(确切的说,是在返回用户态之前,内核会专门检查一下是否需要调度);
    linux 2.6则实现了内核抢占,但是在很多地方还是为了保护临界区资源而需要临时性的禁用内核抢占。

    也有一些地方是出于效率考虑而禁用抢占,比较典型的是spin_lock。spin_lock是这样一种锁,如果请求加锁得不到满足(锁已被别的进程占有),则当前进程在一个死循环中不断检测锁的状态,直到锁被释放。
    为什么要这样忙等待呢?因为临界区很小,比如只保护“i+=j++;”这么一句。如果因为加锁失败而形成“睡眠-唤醒”这么个过程,就有些得不偿失了。
    那么既然当前进程忙等待(不睡眠),谁又来释放锁呢?其实已得到锁的进程是运行在另一个CPU上的,并且是禁用了内核抢占的。这个进程不会被其他进程抢占,所以等待锁的进程只有可能运行在别的CPU上。(如果只有一个CPU呢?那么就不可能存在等待锁的进程了。)
    而如果不禁用内核抢占呢?那么得到锁的进程将可能被抢占,于是可能很久都不会释放锁。于是,等待锁的进程可能就不知何年何月得偿所望了。

    对于一些实时性要求更高的系统,则不能容忍spin_lock这样的东西。宁可改用更费劲的“睡眠-唤醒”过程,也不能因为禁用抢占而让更高优先级的进程等待。比如,嵌入式实时linux montavista就是这么干的。
    由此可见,实时并不代表高效。很多时候为了实现“实时”,还是需要对性能做一定让步的。

    多处理器下的负载均衡
    前面我们并没有专门讨论多处理器对调度程序的影响,其实也没有什么特别的,就是在同一时刻能有多个进程并行地运行而已。那么,为什么会有“多处理器负载均衡”这个事情呢?
    如果系统中只有一个可执行队列,哪个CPU空闲了就去队列中找一个最合适的进程来执行。这样不是很好很均衡吗?
    的确如此,但是多处理器共用一个可执行队列会有一些问题。显然,每个CPU在执行调度程序时都需要把队列锁起来,这会使得调度程序难以并行,可能导致系统性能下降。而如果每个CPU对应一个可执行队列则不存在这样的问题。
    另外,多个可执行队列还有一个好处。这使得一个进程在一段时间内总是在同一个CPU上执行,那么很可能这个CPU的各级cache中都缓存着这个进程的数据,很有利于系统性能的提升。
    所以,在linux下,每个CPU都有着对应的可执行队列,而一个可执行状态的进程在同一时刻只能处于一个可执行队列中。

    于是,“多处理器负载均衡”这个麻烦事情就来了。内核需要关注各个CPU可执行队列中的进程数目,在数目不均衡时做出适当调整。什么时候需要调整,以多大力度进程调整,这些都是内核需要关心的。当然,尽量不要调整最好,毕竟调整起来又要耗CPU、又要锁可执行队列,代价还是不小的。
    另外,内核还得关心各个CPU的关系。两个CPU之间,可能是相互独立的、可能是共享cache的、甚至可能是由同一个物理CPU通过超线程技术虚拟出来的……CPU之间的关系也是实现负载均衡的重要依据。关系越紧密,进程在它们之间迁移的代价就越小。参见《linux内核SMP负载均衡浅析》。

    优先级继承
    由于互斥,一个进程(设为A)可能因为等待进入临界区而睡眠。直到正在占有相应资源的进程(设为B)退出临界区,进程A才被唤醒。
    可能存在这样的情况:A的优先级非常高,B的优先级非常低。B进入了临界区,但是却被其他优先级较高的进程(设为C)抢占了,而得不到运行,也就无法退出临界区。于是A也就无法被唤醒。
    A有着很高的优先级,但是现在却沦落到跟B一起,被优先级并不太高的C抢占,导致执行被推迟。这种现象就叫做优先级反转。

    出现这种现象是很不合理的。较好的应对措施是:当A开始等待B退出临界区时,B临时得到A的优先级(还是假设A的优先级高于B),以便顺利完成处理过程,退出临界区。之后B的优先级恢复。这就是优先级继承的方法。

    中断处理线程化
    在linux下,中断处理程序运行于一个不可调度的上下文中。从CPU响应硬件中断自动跳转到内核设定的中断处理程序去执行,到中断处理程序退出,整个过程是不能被抢占的。
    一个进程如果被抢占了,可以通过保存在它的进程控制块(task_struct)中的信息,在之后的某个时间恢复它的运行。而中断上下文则没有task_struct,被抢占了就没法恢复了。
    中断处理程序不能被抢占,也就意味着中断处理程序的“优先级”比任何进程都高(必须等中断处理程序完成了,进程才能被执行)。但是在实际的应用场景中,可能某些实时进程应该得到比中断处理程序更高的优先级。
    于是,一些实时性要求更高的系统就给中断处理程序赋予了task_struct以及优先级,使得它们在必要的时候能够被高优先级的进程抢占。但是显然,做这些工作是会给系统造成一定开销的,这也是为了实现“实时”而对性能做出的一种让步。

     

    参考文献:《linux内核设计与实现》

           《现代操作系统》

           《进程调度的红黑树实现分析

         《linux内核SMP负载均衡浅析》(本文未引用可以做拓展参考)

         《linux内核cfs浅析

    展开全文
  • linux进程调度

    千次阅读 2014-11-03 09:12:27
     何为进程调度  在linux这样的多用户多任务操作系统上,有大量程序执行的需求。如果每次只运行一个进程,一是其它进程得不到及时的响应,二是CPU时间不能得到充分利用。进程调度就是要解决诸如此类的一些问题,将...

    一. 何为进程调度 

    在linux这样的多用户多任务操作系统上,有大量程序执行的需求。如果每次只运行一个进程,一是其它进程得不到及时的响应,二是CPU时间不能得到充分利用。进程调度就是要解决诸如此类的一些问题,将CPU资源合理地分配给各个进程。同时调度过程又需要对各个进程不可见,在每个进程看来,自己是独占CPU在运行的。这就是虚拟CPU的概念。

    调度程序是像linux这样的多任务操作系统的基础。只有通过调度程序的合理调度,系统资源才能最大限度地发挥,多任务才会有并发执行的效果。 



    二. 进度调度的目标和基本工作 

    进程调度最终要完成的目标就是为了最大限度的利用处理器时间。

    只要有可以执行的进程,那么就总会有进程获得CPU资源而运行。当进程数大于处理器个数时,某一时刻总会有一些进程进程不能执行,这些进程处于等待状态。在这些等待运行的进程中选择一个合适的来执行,并且确定该进程运行多长时间,是调度程序所需完成的基本工作。 

     


    三. 调度策略 

    调度策略决定调度程序在何时让什么进程运行。 

    3.1、 根据进程类型:I/O消耗型和处理器消耗型

    I/O消耗型指进程的大部分时间用来提交I/O请求或者等待I/O请求,这样的进程经常处于可运行状态,但通常都是只运行短短的一会儿,因为它们等待更多的I/O请求时总会阻塞。举例来说,图形用户界面(GUI)和键盘输入都属于I/O消耗型。

    处理器消耗型进程把大多数时间用在执行代码上,除非被抢占,否则它们通常都处于一直不停运行的状态。对于这类进程,调度策略往往是尽量降低它们的调度频率,而延长其运行时间。举例来说:MATLAB

    I/O消耗型和处理器消耗型不是绝对划分的,处于动态变化的过程中。

    这两种类型的进程是矛盾的,如果调度程序倾向于处理器消耗型进程,则I/O消耗型进程会因为前者长时间占用CPU而得不到好的响应。如果调度程序倾向于I/O消耗型进程,频繁进行调度,则处理器消耗型进程的执行将会不断被打断。

    linux为了保证交互式应用和桌面系统性能,对进程的响应做了优化,更倾向于优先调度I/O消耗型进程。

    3.2、 根据进程优先级

    调度算法中最基本的一类就是基于优先级的调度。调度程序总是选择时间片未用尽而且优先级最高的进程运行。

    linux实现了一种基于动态优先级的调度方法。即:一开始,先设置基本的优先级,然后它允许调度程序根据需要加减优先级。例如:如果一个进程在I/O等待上消耗的时间多于运行时间,则明显属于I/O消耗型进程,那么根据上面的考虑,应该动态提高其优先级。 

    linux采用了两种不同的优先级范围,分别用于普通进程和实时进程。

    • nice值。范围为-20到+19,默认值为0。越大的nice值意味着越低的优先级,相比高nice值的进程,低nice值的进程可以获得更多的处理器时间。在linux的CFS调度算法中,nice值用于计算时间片的比例。

    • 实时优先级。值可配置,默认变化范围是0到99。与nice值相反,越高的实时优先级意味着越高的进程优先级。

    实时优先级和nice优先级处于互不相交的两个范畴,任何实时进程的优先级都高于普通进程。 

    3.3、时间片

    时间片是一个数值,表明进程在被抢占之前所能持续运行的时间。调度策略必须规定一个默认的时间片,时间片过长会导致系统对交互进程的响应欠佳,时间片太短会增大进程切换带来的处理器消耗。

    linux的CFS调度器没有直接分配时间片到进程,而是将处理器的使用比例分给了进程。这样一来,进程所获得的处理器时间其实是和系统负载相关的。这个比例进一步还会受进程nice值的影响,nice值作为权重将调整进程所使用的处理器时间比。



    四. 和进程调度相关的知识准备

    进程调度涉及到进程切换的问题,也就是使用一个新的进程来替换旧的进程在CPU上运行。进程切换涉及到了CPU寄存器的切换以及进程内核栈以及指令指针的切换。进程切换稍后会详细介绍,这里先介绍相关的预备知识。

    4.1、 TSS-任务状态段

    任务状态段(Task State Segment)是保存一个任务重要信息的特殊段。 TSS在任务切换过程中起着重要作用,通过它实现任务的挂起和恢复。所谓任务切换是指,挂起当前正在执行的任务,恢复或启动另一任务的执行。在任务切换过程中,首先,处理器中各寄存器的当前值被自动保存到任务状态段寄存器TR所指定的TSS中,包括通用寄存器状态,段寄存器状态,标志寄存器状态,EIP寄存器状态等等;然后,下一任务的TSS的选择子被装入TR;最后,从TR所指定的TSS中取出各寄存器的值送到处理器的各寄存器中。

    由此可见,通过在TSS中保存任务现场各寄存器状态的完整映象,实现任务的切换。每项任务均有其自己的 TSS,而我们可以通过STR指令来获取指向当前任务中TSS的段选择器。

    任务状态段TSS的基本格式如下图所示。


    从图中可见,TSS的基本格式由104字节组成。这104字节的基本格式是不可改变的,但在此之外系统软件还可定义若干附加信息。基本的104字节可分为链接字段区域内层堆栈指针区域地址映射寄存器区域寄存器保存区域其它字段等五个区域。

    • 寄存器保存区域   寄存器保存区域位于TSS内偏移20H(32)至5FH(95)处,用于保存通用寄存器、段寄存器、指令指针和标志寄存器。当TSS对应的任务正在执行时,保存区域是未定义的;在当前任务被切换出时,这些寄存器的当前值就保存在该区域。当下次切换回原任务时,再从保存区域恢复出这些寄存器的值,从而,使处理器恢复成该任务换出前的状态,最终使任务能够恢复执行。 从上图可见,各通用寄存器对应一个32位的双字,指令指针和标志寄存器各对应一个32位的双字;各段寄存器也对应一个32位的双字,段寄存器中的选择子只有16位,安排再双字的低16位,高16位未用,一般应填为0。  

    • 内层堆栈指针区域   为了有效地实现保护,同一个任务在不同的特权级下使用不同的堆栈。例如,当从外层特权级3变换到内层特权级0时,任务使用的堆栈也同时从3级变换到0级堆栈;当从内层特权级0变换到外层特权级3时,任务使用的堆栈也同时从0级堆栈变换到3级堆栈。所以,一个任务可能具有四个堆栈,对应四个特权级。四个堆栈需要四个堆栈指针。   TSS的内层堆栈指针区域中有三个堆栈指针,它们都是48位的全指针(16位的选择子和32位的偏移),分别指向0级、1级和2级堆栈的栈顶,依次存放在TSS中偏移为4、12及20开始的位置,3级堆栈的指针就是保存在寄存器域里面的。当发生向内层转移时,把适当的堆栈指针装入SS及ESP寄存器以变换到内层堆栈,外层堆栈的指针保存在内层堆栈中。没有指向3级堆栈的指针,因为3级是最外层,所以任何一个向内层的转移都不可能转移到3级。但是,当特权级由内层向外层变换时,并不把内层堆栈的指针保存到TSS的内层堆栈指针区域。 

    • 地址映射寄存器区域   从虚拟地址空间到线性地址空间的映射由GDT和LDT确定,与特定任务相关的部分由LDT确定,而LDT又由LDTR确定。如果采用分页机制,那么由线性地址空间到物理地址空间的映射由包含页目录表起始物理地址的控制寄存器CR3确定。所以,与特定任务相关的虚拟地址空间到物理地址空间的映射由LDTR和CR3确定。显然,随着任务的切换,地址映射关系也要切换。TSS的地址映射寄存器区域由位于偏移1CH处的双字字段(CR3)和位于偏移60H处的字段 (LDTR)组成。在任务切换时,处理器自动从要执行任务的TSS中取出这两个字段,分别装入到寄存器CR3和LDTR。这样就改变了虚拟地址空间到物理地址空间的映射。 但是,在任务切换时,处理器并不把换出任务的寄存器CR3和LDTR的内容保存到TSS中的地址映射寄存器区域。事实上,处理器也从来不向该区域自动写入。因此,如果程序改变了LDTR或CR3,那么必须把新值人为地保存到TSS中的地址映射寄存器区域相应字段中。可以通过别名技术实现此功能。   

    • 链接字段   链接字段安排在TSS内偏移0开始的双字中,其高16位未用。在起链接作用时,低16位保存前一任务的TSS描述符的选择子。如果当前的任务由段间调用指令CALL或中断/异常而激活,那么链接字段保存被挂起任务的 TSS的选择子,并且标志寄存器EFLAGS中的NT位被置1,使链接字段有效。在返回时,由于NT标志位为1,返回指令RET或中断返回指令IRET将使得控制沿链接字段所指恢复到链上的前一个任务。  

    • 其它字段   为了实现输入/输出保护,要使用I/O许可位图。任务使用的I/O许可位图也存放在TSS中,作为TSS的扩展部分。在TSS内偏移66H处的字用于存放I/O许可位图在TSS内的偏移(从TSS开头开始计算)。   在TSS内偏移64H处的字是为任务提供的特别属性。在80386中,只定义了一种属性,即调试陷阱。该属性是字的最低位,用T表示。该字的其它位置被保留,必须被置为0。在发生任务切换时,如果进入任务的T位为1,那么在任务切换完成之后,新任务的第一条指令执行之前产生调试陷阱。 

    linux是如何使用TSS的 

    intel的建议:为每一个进程准备一个独立的TSS段,进程切换的时候切换TR寄存器使之指向该进程对应的TSS段,然后在任务切换时(比如涉及特权级切换的中断)使用该段保留所有的寄存器。  

    Linux的做法:

    •  Linux没有为每一个进程都准备一个TSS段,而是每一个CPU使用一个TSS段,TR寄存器保存该段。进程切换时,只更新TSS段中的esp0字段为新进程的内核栈,esp0字段存放在thread_struct中。

    •  Linux的TSS段中只使用esp0和iomap等字段,不用它来保存寄存器,在一个用户进程被中断进入ring0的时候,TSS中取出esp0,然后切到esp0,其它的寄存器则保存在esp0指示的内核栈上而不保存在TSS中。

    • 结果,Linux中每一个CPU只有一个TSS段,TR寄存器永远指向它。符合x86处理器的使用规范,但不遵循intel的建议,这样的结果是开销更小了,因为不必切换TR寄存器了。 

    Linux的TSS实现:

    定义tss:

    struct tss_struct init_tss[NR_CPUS] __cacheline_aligned ={[0... NR_CPUS-1]= INIT_TSS };(arch/i386/kernel/init_task.c)
    INIT_TSS结构定义为:
    define INIT_TSS  {                            \
    .esp0        =sizeof(init_stack)+(long)&init_stack,    \
    .ss0        = __KERNEL_DS,                   \
    .esp1        =sizeof(init_tss[0])+(long)&init_tss[0],    \
    .ss1        = __KERNEL_CS,                    \
    .ldt        = GDT_ENTRY_LDT,                \
    .io_bitmap_base    = INVALID_IO_BITMAP_OFFSET,            \
    .io_bitmap    ={[0... IO_BITMAP_LONGS]=~0},        \
    }

    总结

    TSS段的作用在于保存每个进程的硬件上下文,intel 80x86CPU为TSS段的使用定义相应的汇编指令,这样在进程切换的时候,只要使用该汇编指令,就可以自动进行硬件上下文的切换了。

    这样做的好处在于利用了CPU指令的功能,操作系统设计者不需要专门处理硬件上下文切换的细节,缺点在于

    • 要在TSS段中为每个进程静态定义一个数组元素,这样该数组将会很大;

    • 不能对硬件上下文切换进行优化;

    • linux系统为了运行在各种硬件平台下,需要一个通用模型,而完全遵循intel的建议却受到了太多的约束。

    所以linux部分使用了intel80x86硬件平台的TSS段。主要使用了一下功能:

    • 完成从用户态到内核态切换时,内核堆栈地址的获取;

    • I/O端口访问能力检查。

    其实windows也没有完全使用TSS段来做任务切换。

    4.2、 与程序跳转相关的汇编指令

    (1)call

    将程序当前执行的位置(ip)压入栈中;

    转移到调用的子程序中执行。

    (2)ret

    用栈中esp指向的内容替换ip,转移到原来的程序继续运行。

    (3)jmp

    无条件转移指令,需要给出两种信息,转移的目的地址或者转移的距离。

    后面我们将会看到linux的进程切换程序是如何使用指令jmp和ret来实现执行流的切换的。



    五. 进程切换的实现 switch_to

    见附件

    下载链接:http://download.csdn.net/detail/da310blog/8115261


    六. linux的进程调度

    内存中保存了对每个进程的唯一描述,并通过若干结构与其它进程连接起来。调度器面对的情形就是这样,其任务是在程序之间共享CPU时间,创造并行执行的错觉。正如上面的讨论,该任务分为两个不同部分:一个涉及调度策略,另一个涉及上下文切换。上下文切换我们已经详细解释过了,接下来的任务就是研究一下调度策略。

    linux进程调度主要包括对以下进程的调度:

    • 普通进程   调度策略CFS

    • 实时进程   调度策略FIFO、RR

    • idle进程

    6.1、 数据结构

    调度器使用一系列数据结构,来排序和管理系统中的进程。调度器的工作方式与这些结构的设计密切相关。几个组件在许多方面彼此交互,下图表明了这些组件之间的关联。

    可以通过两种方法激活调度。一种是直接的,比如进程打算睡眠或者处于其他原因放弃CPU;另一种是通过周期性调度机制,以固定的频率运行,不时检测是否有必要进行进程切换。下文中将这两个组件称为为通用调度器或者核心调度器。

    • 调度器类用于判断接下来运行哪个进程。内核支持不同的调度策略,调度器类使得能够以模块化方法实现这些策略,一个类的代码不需要与其他类的代码交互。而且调度器因此有了很好的层次结构,进程调度的过程就是一个接口的调用过程。在调度器被调用时,它会按照优先级顺序遍历调度器类,选择一个拥有可执行程序的最高优先级的调度器类,再选择具体要投入运行的进程。

    • 在选中要运行的进程以后,必须执行底层任务切换,这需要与CPU的紧密交互。

    • 每个进程都刚好属于某一调度器类,各个调度器类负责管理所属的进程。通用调度器自身完全不涉及进程管理,其工作都委托给调度器类。

    (1)task_struct的成员

    各进程的task_struct有几个成员与调度相关。

    struct task_struct{
    ...
    	int prio, static_prio, normal_prio;
    	unsigned int rt_priority;
    	struct list_head  run_list;
    	const struct sched_class *sched_class;
    	struct sched_entity se;
    	unsigned int policy;
    	cpunask_t cpus_allowd;
    	unsigned int time_slice;
    ...
    }

    • task_struct使用了3个成员表示进程的优先级:

      static_prio表示进程的静态优先级。静态优先级是进程启动时分配的,范围为100-139。它可以用nice值和sched_scheduler系统调用修改,否则在进程运行期间会一直保持恒定。计算公式为:static priority = nice + 20 + MAX_RT_PRIO。

      normal_prio表示基于进程的静态优先级和调度策略计算出的优先级。普通进程和实时进程的normal_prio计算方式是不同的,后面会介绍。进程分支时,子进程会继承普通优先级。

      但调度器考虑的优先级则保存在prio。由于某些情况下内核需要暂时提高进程的优先级,因此需要这个成员。这些改变不是持久不变的,静态和普通优先级不受影响。

    • rt_priority表示实时进程的优先级。该值不会代替前面讨论的那些值。实时优先级的范围为0-99,值越大,优先级越高。

    • sched_class表示该进程所属的调度器类。

    • 调度器不限于调度进程,还可以处理更大的实体。这可以用于组调度:可用的CPU时间首先在一般的进程组之间分配,接下来再在组内进程间分配。

      这种一般性要求调度器不直接操作进程,而是处理可调度实体。一个实体用sched_entity的一个实例表示。se在task_struct内部嵌入了一个sched_entity实例,调度器据此可以操作各个task_struct。

    • policy保存了该进程对应的调度策略。linux支持可能的5个值:

      SCHED_NORMAL用于普通进程,它们通过完全公平调度策略来处理。

      SCHED_BATCH和SCHED_IDLE也通过完全公平调度来处理,不过可用于次要的进程。SCHED_BATCH用于非交互、CPU使用密集的批处理进程。调度策略对此类进程给予“冷处理”:它们绝不会抢占CFS调度器处理的另一个进程,因此绝不会干扰交互式进程。SCHED_IDLE的相对权重总是最小的,在没有进程可以调度时被内核选择来运行。

      SCHED_RR和SCHED_FIFO用于实现软实时进程(linux不能保证硬实时工作方式)。SCHED_RR实现了一种循环方法,而SCHED_FIFO则使用先入先出机制,它们由实时调度器类处理。

    • cpus_allowed是一个bitmap,在多处理器上使用,用来限制进程可以再哪些CPU上运行。对于负载均衡有意义。

    • run_list和time_slice标志是循环实时调度器所需要的,但不用于完全公平调度器。runlist是一个表头,用于维护包含各进程的一个运行表,而time_slice则制定进程可用CPU的剩余时间段。

    (2)调度器类

    调度器类提供了通用调度器和各个调度方法之间的关联。调度器类由特定数据结构中汇集的几个函数指针表示。这使得无需了解不同调度器类的内部工作原理,即可创建通用调度器。

    对各个调度器类,都要提供struct sched_class的一个实例。调度器类之间的层次结构是平坦的,实时进程最重要,在完全公平调度之前处理;而完全公平进程则优先于空闲进程;空闲进程只有CPU无事可做时才处于活动状态。

    struct sched_class{
    	const struct sched_class *next;
    	void(*enqueue_task)(struct rq *rq,struct task_struct *p,int wake_up);
    	void(*dequeue_task)(struct rq *rq,struct task_struct *p,
    	int sleep);
    	void(*yield_task)(struct*rq)
    	void(*check_preempt_curr)(struct rq *rq,struct task_struct *p);
    	struct task_struct *(*pick_next_task)(struct rq *rq);
    	void(*put_prev_task)(struct rq *rq,struct task_struct *p);
    	void(*set_curr_task)(struct rq *rq);
    	void(*task_tick)(struct rq *rq,struct task_struct *p);
    	void(*task_new)(struct rq *rq,struct  task_struct *p);
    };

    • next用于将不同调度器类的sched_class实例按上述处理顺序连接起来。这个层次结构在编译已经建立,没有运行时动态增加新调度器类的机制。

    • enqueue_task向就绪队列添加一个新进程。在进程从睡眠状态变为可运行状态时发生该操作。

    • dequeue_task将一个进程从就绪队列去除。在进程从可运行状态切换到不可运行状态时就会发生该操作;内核也可能因为其它理由将进程从就绪队列去除,例如,进程的优先级可能需要改变。

    • 进程想要自愿放弃对处理器的控制权时,可使用sched_yield系统调用。这导致内核调用yeild_task。

    • 在必要的情况下,会调用check_premmpt_curr,用一个新唤醒的进程来抢占当前进程。比如用wake_up_new_task唤醒新进程时,会调用更该函数。

    • pick_next_task用于选择下一个将要运行的进程,而put_prev_task则在用另一个进程代替当前运行的进程之前调用。

    • set_curr_task 在进程的调度策略发生变化时,需要调用set_curr_task,还有其它一些场合也需要调用该函数。

    • task_tick在每次激活周期性调度器时,由周期性调度器调用。

    • new_task用于建立fork系统调用和调度器之间的关联。每次新进程建立以后,就用new_task通知调度器。

    标准函数activate_task和deactivate_task调用前述的函数,提供进程在就绪队列的入队和离队功能。此外,它们还更新内核的统计数据。

    static void activate_task(struct rq *rq,struct task_struct *p,int flags);
    static void deactivate_task(struct rq *rq,struct task_struct *p,int flags);
    内核定义了便捷方法check_preempt_curr,调用与给定进程相关的调度器类的check_preempt_curr方法。
    static void check_preempt_curr(struct rq *rq,struct task_struct *p);

    (3)调度实体

    由于调度器可以操作比进程更一般的实体,因此需要一个适当的数据结构来描述此类实体。

    调度实体的作用是用来为普通进程和实时进程进行时间记账。不同之处在于,普通进程由于用到了虚拟时间,所以vruntime字段是有意义的;而实时进程没有虚拟时间,该字段没有意义。

    struct sched_entity{
            struct load_weight load;
            struct rb_node run_node;
            unsigned int on_rq;
             
            u64 exec_start;
            u64 sum_exec_runtime;
            u64 vruntime;
            u64 prev_sum_exec_runtime;
    ...
    }

    如果编译内核时启用了调度器统计,那么该结构会包含很多用于统计的成员。如果启用了组调度,还会增加一些成员。但目前我们只对上面列出的几项感兴趣。
    • load指定了权重,决定了各个实体占队列总负荷的比例。

    • run_node是标准的树节点,使得实体可以在红黑树上排序。

    • on_rq表示该实体当前是否在就绪队列上接受调度。

    • 在进程运行时,需要记录消耗的CPU时间,以用于完全公平调度。sum_exec_runtime即用于该目的。该时间的更新是通过计算当前时间和exec_start之间的差值, 累加到sum_exec_runtime上。而exec_start则会更新到当前时间。

      在进程执行期间虚拟时钟上流逝的时间数量由vruntime统计。

    • 在进程被撤销CPU时,其当前sum_exec_runtime值保存到prev_sum_exec_runtime。此后,在进程抢占时又需要该数据。需要注意的是:在prev_sum_exec_runtime中保存sum_exec_runtime的值并不意味着重置sum_exec_runtime。原值保存下来,而sum_exec_runtime则持续保持单调增长。

    (4)就绪队列

    核心调度器用于管理活动进程的主要数据结构称为就绪队列。各个CPU都有自身的就绪队列,每个活动进程只出现在一个就绪队列中,在多个CPU上同时运行一个进程是不可能的。注意:进程并不是由就绪队列的成员直接管理的,而是由各个调度器类来完成的,就绪队列只是定义了进程管理的数据结构。

    下面列出就绪队列的主要成员

    struct rq {
    ...
            unsigned long nr_running;
            #define CPU_LOAD_IDX_MAX 5
            unsigned long cpu_load[CPU_LOAD_IDX_MAX];
    ...
            struct load_weight load;
      
            struct cfs_rq cfs;
            struct rt_rq rt;      
             
            struct task_struct *curr, *idle;
            u64 clock;
    ...
    };

    • nr_running指定了队列上可运行进程数,不考虑其优先级和调度类。

    • cpu_load用于跟踪此前的负荷状态。

    • load提供了就绪队列当前负荷的度量。队列的负荷本质上与队列上当前活动进程的数目成正比,其中的各个进程又有优先级作为权重。每个就绪队列的虚拟时钟的速度即基于该信息。

    • cfs和rt是嵌入的子就绪队列,分别用于完全公平调度器和实时调度器。

    • curr指向当前运行进程的task_struct实例。

    • idle指向idle进程的task_struct实例。

    • clock用于实现就绪队列自身的时钟。每次调用周期性调度器时,都会更新clock的值。另外,内核还提供了标准函数update_rq_clock,可在操作就绪队列的调度器中多处调用。

    系统的所有就绪队列都在runqueues数组中,该数组的每个元素分别对应于系统中的一个CPU。

    static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

    内核还定义了一些便利的宏
    #define cpu_rq(cpu)(&per_cpu(runqueues,(cpu)))
    #define this_rq()(&__get_cpu_var(runqueues))
    #define task_rq(p)            cpu_rq(task_cpu(p))
    #define cpu_curr(cpu)(cpu_rq(cpu)->curr)
    • cpu_rq用于获取编号为cpu的就绪队列

    • this_rq用于获取当前cpu的就绪队列

    • task_rq用于获取当前进程所在cpu的就绪队列

    • cpu_curr用于获取编号为cpu的处理器上正在执行的进程

    (5)CFS的就绪队列

    struct cfs_rq{
    	struct load_weight load;
    	unsignedlong nr_running;
          		  u64 min_runtime;
    	struct rb_root tasks_timeline;
    	struct rb_node *rb_leftmost;
    	struct sched_entity *curr;
    }
    • nr_running表示该就绪队列上运行进程的数目。

    • load维护了所有这些进程的累积负荷值。负荷值的计算方法稍后介绍。

    • min_vruntime跟踪记录队列上所有进程的最小虚拟运行时间,这个值是实现与就绪队列相关的虚拟时钟的基础。

    • task_timeline是一个基本成员,用于在按时间排序的红黑树中管理所有进程。

    • rb_leftmost总是设置为指向树最左边的节点,即需要被调度的进程。加入该字段的根本原因在于进程加入红黑树和调度程序选择下一进程之间是异步的关系。使用该变量可以缓存虚拟运行时间最小的进程,省去了遍历红黑树来寻找的过程,减少了搜索树所花的平均时间。

    • curr指向当前执行进程的可调度实体。

    (6)实时进程的就绪队列

    实时进程的就绪队列非常简单,使用链表就够了。对与组调度和SMP系统,还有更多的成员,我们这里不予考虑。

    struct rt_prio_array {
             DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
             struct list_head queue[MAX_RT_PRIO];
      };

    具有相同优先级的所有实时进程都保存在一个链表中,表头为active.queue[prio],而active.bitmap位图中的每个比特对应于一个链表,如果链表不为空,则相应的比特置位。其结构如下:


    6.2 上述数据结构之间的关系 




    6.3 处理优先级

    6.3.1 优先级的内核表示

    linux进程描述符中与进程优先级有关的域有4个:

    • static_prio  静态优先级的计算基于nice值,不论是普通进程还是实时进程,它们的静态优先级的表示都是相同的,结果为NICE_TO_PRIO(nice),即120 + nice。可以通过系统调用nice()对普通进程和实时进程指定nice值,该系统调用会如前所属计算进程的静态优先级。对于实时进程来说,指定了nice值并不会将其降级为普通进程,因为实时进程对静态优先级并不感冒,它更感兴趣的是实时优先级。详情参考set_user_nice()函数。

      静态优先级是基于nice值的,值越小说明进程的优先级越高。

    • rt_priority  实时进程的优先级,范围从0-99。值越小优先级越低。

    • normal_prio 由于静态优先级和实时优先级的表示正好相反,引入一个normal_prio对它们进行统一。实时进程的普通优先级计算方式为MAX_RT_PRIO - 1- rt_priority,范围从99 - 0。普通进程的普通优先级等于静态优先级。统一以后进程优先级的表示如下。



      :只要没有通过系统调用nice()或者sched_setscheduler()系统调用修改,上述的三个优先级在进程运行过程中都不会改变。

    • prio 是进程的动态优先级,该优先级在进程创建的时候继承自父进程的normal_prio(见copy_process()->sched_fork())。在进程运行的过程中可能会临时提高进程的优先级,如磁盘I/O时,所以引入了动态优先级。

    下列宏用于在各种不同形式之间转换(MAX_RT_PRIO 等于实时进程的最大优先级加1,而MAX_PRIO则等于普通进程的最大优先级加1,他们的值分别为100和140)。

    <sched.h>
    #define MAX_USER_RT_PRIO        100
    #define MAX_RT_PRIO             MAX_USER_RT_PRIO
    #define MAX_PRIO                (MAX_RT_PRIO +40)
    #define DEFAULT_PRIO            (MAX_RT_PRIO +20)//普通进程默认静态优先级为120
    <kernel/sched.c>
    #define NICE_TO_PRIO(nice)((nice)+ DEFAULT_PRIO)
    #define PRIO_TO_NICE(prio)((prio)- DEFAULT_PRIO)
    #define TASK_NICE(P)            PRIO_TO_NICE((P)->static_prio)

    6.3.2 计算优先级

    static_prio是计算的起点。假设它已经设置好,内核现在想要计算其它优先级,只需要一行代码即可:

    p->prio = effective_prio(p);
    <kernel/sched.c>
    staticint effective_prio(struct task_struct *p)
    {
            p->normal_prio = normal_prio(p);
    	if(!rt_prio(p->prio))
    		return p->normal_prio;
    	return p->prio;
    }

    该函数首先计算了normal_prio,然后根据进程当前的动态优先级是否处于实时优先级的范围返回不同的结果。
    <kernel/sched.c>
    staticinlineint normal_prio(struct task_struct *p)
    {
    	int prio;
    	if(task_has_rt_policy(p))
                 prio = MAX_RT_PRIO -1+ p->rt_priority;
    	else
                 prio = __normal_prio(p);
    	return prio;
    }
    对于实时进程,它的普通优先级是将实时优先级按6.3.1中提到的方法进行反转,折算成低数值高优先级的情况。注意这里判断是否是实时优先级是看进程的调度策略,而不是动态优先级的数值。为什么呢?因为普通优先级是一个确定不变的数值,而动态优先级是一个变化的量。

    对于普通进程而言,返回值__normal_prio(p),它就是静态优先级。

    <kernel/sched.c>
    staticinlineint __normal_prio(struct task_struct *p)
    {
    	return p->static_prio;
    }
    综上所述:

     进程类型/优先级                  static_prio                normal_prio                                          prio

     非实时进程                          static_prio                static_prio                                             static_prio

     优先级提高的非实时进程    static_prio                static_prio                                             effective_prio/不变

     实时进程                              static_prio                MAX_RT_PRIO - 1 - p->rt_priority     normal_prio/不变


    6.3.3 计算负荷权重

    进程重要性和两个因素有关:进程类型和进程优先级。实时进程重要性高于非实时进程,而实时进程又根据优先级而重要性不同。

    进程负荷权重保存在数据结构load_weight中:

    struct load_weight{
        unsignedlong weight, inv_weight;
    };
    其中不仅保存了负荷权重自身,还保存另一个数值inv_weight,用于计算被负荷权重除的结果,它们两者相乘大约等于一个定值。

    这个权值是针对普通进程而言的,nice值从-20-19对应有40个元素,这40个优先级对应的权重实现已经计算好了,放在数组prio_to_weight中:

    staticconstint prio_to_weight[40]={
    /* -20 */88761,71755,56483,46273,36291,
    /* -15 */29154,23254,18705,14949,11916,
    /* -10 */9548,7620,6100,4904,3906,
    /*  -5 */3121,2501,1991,1586,1277,
    /*  0 */1024,820,655,526,423,
    /*  5 */335,272,215,172,137,
    /*  10 */110,87,70,56,45,
    /*  15 */36,29,23,18,15,
    };
    进程权重在函数set_load_weight中设置:
    #define WEIGHT_IDLEPRIO             2
    #define WMULT_IDLEPRIO              (1<<32)
    <kernel/sched.c>
    static void set_load_weight(struct task_struct *p)
    {
        if(task_has_rt_policy(p)){
            p->se.load.weight = prio_to_weight[0]*2;
            p->se.load.inv_weight = prio_to_wmult[0]>>1;
        return;
        }
        /*
         * SCHED_IDLE tasks get minimal weight:
         */
        if(p->policy == SCHED_IDLE){
            p->se.load.weight = WEIGHT_IDLEPRIO;
            p->se.load.inv_weight = WMULT_IDLEPRIO;
        return;
        }
        p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
        p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
    }
    对于实时进程,它的权重是优先级最高的普通进程,即nice值为-20进程的权重的两倍;idle进程的权重最小。

    对于实时进程和idle进程,它们的调度不是基于权重的:实时进程基于实时优先级和时间片,而时间片不论优先级大小被赋予了一个定值;idle进程则完全没有时间片的概念,只要没有其它进程,它一直占据CPU运行。这里给它们也赋予权重主要是为了对每个CPU就绪队列struct rq中的负荷进行跟踪,对于负载均衡有重要意义。

    每次进程加入到就绪队列rq时,内核会调用相应的函数,将进程权重添加到就绪队列的权重中。如果进程是普通进程,还会增加cfs_rq中的队列权重值。


    6.4 调度器的实现

    由于我们的讨论中不涉及组调度,所以后面的内容中的进程和调度实体可以看做是一个概念。

    6.4.1 与进程调度相关的队列

    在进程被创建到消亡之前,它的状态主要有运行状态、就绪状态和睡眠状态。处于运行状态的进程此时被调度程序选择在CPU上运行;就绪状态的进程处于可运行的状态,但是由于多用户、多任务操作系统上同时运行的进程数据不会超过CPU个数,因此需要排队等待其它进程主动放弃CPU的使用权或者调度程序选中它作为下一个投入运行的进程;处于睡眠状态的进程正在等待某些事件的发生,在事件发生以前它们绝不会获得CPU的使用权。

    既然进程有不同的状态,那么就需要相应的数据结构来对它们进行合理的组织,以便实现对系统中大量进程进行管理。linux中使用了就绪队列和等待队列。

    (1)就绪队列

    通过6.1节对进程调度相关数据结构的讲解,对于就绪队列大家应该都有了比较深入的了解。就绪队列每CPU一个,但是它并不直接管理进程,进程的管理是委托给调度器类来管理的。普通进程由完全公平调度器类管理,所有这些非实时进程根据键值组织在一棵红黑树中;实时进程按实时优先级存放在100个双向链表中。

    需要注意:

    属于运行状态的普通进程,也就是当前正在使用CPU执行其程序的普通进程,不在对应CPU的红黑树中,但是用了一个标志来表示它目前确实是运行状态。换句话说,就绪队列只是保存正在等待使用CPU资源的进程。

    上述的就绪状态和运行状态是两个不同的状态,但是linux内核中使用了同一个状态TASK_RUNNING来表示它们,不能单从字面意思来理解它们。

    (2)等待队列

    在进程执行的过程中,可能需要等待某些事件的发生。例如进程需要从一个磁盘文件中读取数据,而磁盘I/O又是一个相对来说非常耗时的过程。如果在I/O的过程中,进程依旧占用CPU来等待I/O完成,那么对于CPU资源的利用率将会降低。所以目前通用的做法是将等待I/O的进程挂到一个相应的等待队列上,进程进入睡眠状态。当I/O完成后设备会向CPU发起中断,进而唤醒等待进程,重新加入就绪队列中等待调度。具体的过程这里就不详述了,在中断和设备驱动章节有详细介绍。

    6.4.2 核心调度器概述

    linux进程调度的核心和两个调度函数有关:scheduler_tick()和schedule()。两者分别称为周期性调度器(周期性调度函数)和主调度器(主调度函数)。两者结合在一起称作通用调度器(或核心调度器)。


    主调度器——真正完成进程切换的函数

    调度器最核心的功能是将CPU的使用权从一个进程切换到另一个进程。这个工作是由被称作主调度器的组件完成的。


    注:三个不同的长条分别表示CPU分配给进程A、B、C的时间。这里只是示意,进程切换不一定都是在CPU时间使用完才进行的。


    周期性调度器——只更新进程运行相关的统计信息,本身并不完成进程切换

    对于周期性调度器,我们需要关心的是单个进程的执行过程。假设进程A正在CPU上运行,那么在A运行的这段时间内,系统会定时调用周期性调度器,即scheduler_tick(),它只是更新进程运行过程中的统计信息,例如进程在CPU上运行的总时间。

    周期性调度器的调用频率为时钟中断频率,即HZ。每次硬件时钟中断都会调用该函数。




    6.4.3 linux中的调度器类

    linux中实现了三个调度器类

    • 完全公平调度器类

    • 实时调度器类

    • ilde调度器类

    它们都是对结构体sched_class的实例化,定义分别如下:

    <kernel/sched_fair.c>
    /*
     * All the scheduling class methods:
     */
    static const struct sched_class fair_sched_class ={
    	.next               = &idle_sched_class,
    	.enqueue_task       = enqueue_task_fair,
    	.dequeue_task       = dequeue_task_fair,
    	.yield_task         = yield_task_fair,
    	.check_preempt_curr = check_preempt_wakeup,
    	.pick_next_task     = pick_next_task_fair,
    	.put_prev_task      = put_prev_task_fair,
    	#ifdef CONFIG_SMP
    	.load_balance       = load_balance_fair,
    	.move_one_task      = move_one_task_fair,
    	#endif
    	.set_curr_task      = set_curr_task_fair,
    	.task_tick          = task_tick_fair,
    	.task_new           = task_new_fair,
    };
    <kernel/sched_rt.c>
    const struct sched_class rt_sched_class ={
    	.next               =&fair_sched_class,
    	.enqueue_task       = enqueue_task_rt,
    	.dequeue_task       = dequeue_task_rt,
    	.yield_task         = yield_task_rt,
    	.check_preempt_curr = check_preempt_curr_rt,
    	.pick_next_task     = pick_next_task_rt,
    	.put_prev_task      = put_prev_task_rt,
    	#ifdef CONFIG_SMP
    	.load_balance       = load_balance_rt,
    	.move_one_task      = move_one_task_rt,
    	#endif
    	.set_curr_task      = set_curr_task_rt,
    	.task_tick          = task_tick_rt,
    };
    <kernel/sched_idletask.c>
    /*
     * Simple, special scheduling class for the per-CPU idle tasks:
     */
    const struct sched_class idle_sched_class ={
    /* .next is NULL */
    /* no enqueue/yield_task for idle tasks */
    /* dequeue is not valid, we print a debug message there: */
    	.dequeue_task       = dequeue_task_idle,
    	.check_preempt_curr = check_preempt_curr_idle,
    	.pick_next_task     = pick_next_task_idle,
    	.put_prev_task      = put_prev_task_idle,
    	#ifdef CONFIG_SMP
    	.load_balance       = load_balance_idle,
    	.move_one_task      = move_one_task_idle,
    	#endif
    	.set_curr_task      = set_curr_task_idle,
    	.task_tick          = task_tick_idle,
    /* no .task_new for idle tasks */
    };
    现在我们不急于关注这些类中的各个方法是怎么实现的,需要注意的是它们排列的先后顺序:
    rt_sched_class->fair_sched_class->idle_sched_class
    这个顺序对于进程调度具有重要意义:先调度实时进程;没有实时进程就调度普通进程;如果没有可运行进程就选择idle进程来运行。


    6.4.4 完全公平调度类

    这里先对完全公平调度中相对比较独立的部分进行单独讲解,对于那些与主调度器和周期性调度器关联性比较强的部分,在后面分析主调度器和周期性调度器代码时再作分析。

    (1)一个完全理想的多任务处理器

    假设我们有一个理想的CPU,可以同时执行任意数量的进程,进程之间共享CPU的处理能力。若某个时刻有N个进程,那么每个进程获得总运算能力的1/N。

    举例来说:每个进程单独运行需要10分钟才能完成其工作,现在有5个进程在理想CPU上运行,每个会得到计算能力的20%,这意味着每个进程需要运行50分钟,而不是10分钟。但所有的5进程都会刚好在该时间段之后结束工作,没有哪个进程在此段时间内处于不活动状态。    

    (2)相关概念与操作

    上面的模型在真正的硬件上是无法实现的,一个CPU上只能同时运行一个进程,并通过在进程之间高频率切换来实现多任务。这样的话,相比于正在CPU上运行的进程,那些处于就绪队列的进程显然受到了不公平对待。而完全公平调度算法就是为了解决这个不公平问题,尽量使得每个进程能够根据其优先级获得应有的时间份额,在每个调度周期结束后,没有进程受到了亏待。


    调度周期与进程理想运行时间   

    • 由于系统中多数进程不是运行一小段时间就结束了,所以不能说只对所有进程调度一次,直到所有进程结束为止。这样就引入了调度周期的概念。完全公平调度根据当前系统中普通进程的数目对调度周期进行动态调整,在一个调度周期内,就绪队列中所有进程都能被调度执行一次。调度周期由函数__sched_period()计算:
      <kernel/sched_fair.c>
      /*
       * The idea is to set a period in which each task runs once.
       *
       * When there are too many tasks (sysctl_sched_nr_latency) we have to stretch
       * this period because otherwise the slices get too small.
       *
       * p = (nr <= nl) ? l : l*nr/nl
       */
      static u64 __sched_period(unsignedlong nr_running)
      {
          u64 period = sysctl_sched_latency;
          unsignedlong nr_latency = sched_nr_latency;
          if(unlikely(nr_running > nr_latency)){
              period *= nr_running;
              do_div(period, nr_latency);
          }
          return period;
      }
    • sched_nr_latency等于5,sysctl_sched_latency等于20ms。当系统中普通进程数目小于等于5个时,调度周期等于20ms。这样做的目的在于,此时的进程数量很少, 没有必要将调度周期设置得很小,这样可以减少过于频繁的进程切换带来的开销。
    • 当系统中普通进程数目大于5个时,则需要重新计算调度周期的值了,上面if语句完成的就是这个工作。本质上得到的效果就是:
      period = (sysctl_sched_latency / sched_nr_running) * nr_running
    • 即根据进程数据对调度周期进行扩大,这样一来平均每个进程能够得到的运行时间也有4ms。
    • 对于系统中的每个进程,在一个调度周期内CFS调度算法都承诺为它分配一定的CPU时间。对于分配给一个进程的时间,该进程不一定使用完。例如进程执行过程中睡眠或者主动放弃CPU。即使没有使用完,另一个进程也不能使用该时间,否则另一个进程就受到了优待,调度就不公平了。理想的情况是所有进程都用完了一个调度周期内CFS调度算法承若能够分配给它们的CPU时间,但由于进程本身行为的复杂性,该条件不可能时时刻刻都能满足。进程理想运行时间由函数sched_slice()计算:
      <kernel/sched_fair.c>
      /*
       * We calculate the wall-time slice from the period by taking a part
       * proportional to the weight.
       *
       * s = p*w/rw
       */
      static u64 sched_slice(struct cfs_rq *cfs_rq,struct sched_entity *se)
      {
          u64 slice = __sched_period(cfs_rq->nr_running);/* 计算这个调度波次的时间 */
          slice *= se->load.weight;
          do_div(slice, cfs_rq->load.weight);/* 根据权重计算调度实体se所占的运行时间 */
          return slice;
      }
    • 该函数的完成的工作就是根据进程自身的权重占普通进程所有权重的比例,得到一个调度周期内它能够获得的CPU使用时间的最大值,写成公式就是:
      slice = (se->load.weight / cfs_rq->load.weight) * __sched_period
    • 再强调一下:   前面对调度周期和进程理想运行时间的描述中我们说到,CFS算法根据系统中进程的数目计算一个调度周期,进程根据自己的权重瓜分这个调度周期。理想情况下,进程都会使用完自己的时间份额。但是实际情况并非如此,一个进程被调度执行,可能时间没有使用完就放弃CPU的使用权了。CFS调度算法只是承诺一定能够满足进程的运行时间需求,但是它不会将一个进程前一个调度周期没有用完的时间给它保留到下一个调度周期。到下一个调度周期的时候,又有了新的调度周期和每个进程的运行时间。那么对于那些没有将自己时间份额用完的进程显然是不公平的,那这中不公平性是怎么度量的呢?这就要说进程的虚拟运行时间了。
    虚拟运行时间
    • 这个概念对于CFS调度算法极为重要,是该算法得以实现公平性的关键。它的计算公式为:
      vruntime =实际运行时间* NICE_O_LOAD / se->load.weight
    • 可以看出 nice值为0的进程其虚拟运行时间和实际运行时间相等。
    • 如果每个进程都用完了调度算法承诺的能够分配给它的运行时间,那么,当进程运行结束时,实际运行时间等于它的理想运行时间,那么:
      vruntime = se->load.weight / cfs_rq->load.weight * __sched_period
                 * NICE_0_LOAD /  se->load.weight
               = __sched_period * NICE_O_LOAD / cfs_rq->load.weight
    • 即进程的虚拟运行时间在本调度周期结束以后是相同的,与单个进程的权重无关。
    • 可以看出,引入虚拟运行时间的作用就在于对进程的运行时间进行了“归一化”。从进程的实际运行时间来看,进程由于权重的不同该值肯定不同,单从时间值来看,这是不公平的;但是从虚拟运行时间来看,这确确实实是公平的!
    • 上面说的是理想情况,对进程调度用轮训的方式就能搞定了,根本用不着按vruntime将进程插入红黑树进行排序。
    • 系统中进程运行的实际情况要复杂得多,进程并非都能用完它在每一个调度周期内调度算法承诺给它的运行时间,因此积累了一定的不公平性。这种不公平性就是通过vruntime的相对大小表现出来的,vruntime越小的进程受到的不公平对待越严重,因此在红黑树中排在越左的位置,下一个调度周期就会越早被调度程序选择来投入运行。
    最小虚拟运行时间
    • 每个CFS就绪队列中都有一个最小运行时间min_vruntime,用于跟踪记录该队列上所有进程的最小虚拟运行时间。这个值是单调递增的,但不一定比最左边树节点的vruntime小,如进程唤醒时。
    • 为什么要引入这个参数呢?                                                                                                                           a、如果进程已经积累了较大的不公平性,用完了本调度周期自己的CPU时间后,它的虚拟运行时间还是最小的,那么它还会被CFS调度算法选择来运行,直到它的虚拟运行时间不是最小的那个为止。这样一来其它进程在这个调度周期就不会得到执行的机会,因为时间都用来补偿该虚拟运行时间太短的进程了。举一个实际的例子,如果进程在运行过程发起I/O请求,那么在它的I/O请求满足以后很可能已经过了很多个调度周期,由于它的vruntime大大小于其它进程,那么接下来的一段时间,它将一直运行,造成其它进程饥饿。对于这个一直执行的进程而言,这似乎是公平的;对于其它进程来说,又是不公平的。我们可以这样理解,进程虽然没有使用CPU资源,但是它用了I/O设备,因此不能过于偏袒它。我们可以调整这个进程,使它的vruntime最小,能够被首先调度执行,比如说将它的虚拟运行时间设置为min_vruntime,至于linux是怎么做的,后面再说。                                                                                                                         b、对于新创建的进程而言,它的vruntime等于0。那如果不对它的vruntime进行修正,那么它将会一直运行,直到它的vruntime赶上系统中原来vruntime最小的那个进程为止。对于一个已经运行了1年的服务器,如果不进行进程虚拟运行时间的修正,岂不是接下来的很长一段时间都要用来运行这个新进程,其它进程只有长时间等待的份了?换一个角度想,这个新建的进程过去根本就没有为系统或者用户做出过任何贡献,那么调度算法为什么要为它把过去的时间都弥补上来呢?就像你毕业去了一家公司上班,难不成还要人家把从公司成立到像你入职这段时间的工资给你补上?针对这种情况,也需要结合min_runtime进行时间的修正。
    时间记账
    • 对于每个进程,内核需要记录它已经运行的时间,CFS虽然没有使用时间片的概念,但时间概念还是不能少的。时间记账主要是更新进程的实际运行时间和虚拟运行时间,主要是由函数__update_rq_clock()/update_rq_clock()和update_curr()完成的,前者对就绪队列rq进行时间记账,后者对cfs_rq中的当前运行进程进行时间记账。
      <kernel/sched.c>
      /*
       * Update the per-runqueue clock, as finegrained as the platform can give
       * us, but without assuming monotonicity, etc.:
       */
      staticvoid __update_rq_clock(struct rq *rq)
      {
          u64 prev_raw = rq->prev_clock_raw;
          u64 now = sched_clock();
          s64 delta = now - prev_raw;
          u64 clock = rq->clock;
      #ifdef CONFIG_SCHED_DEBUG
          WARN_ON_ONCE(cpu_of(rq)!= smp_processor_id());
      #endif
          /*
           * Protect against sched_clock() occasionally going backwards:
           */
          if(unlikely(delta <0)){
              clock++;
              rq->clock_warps++;
          }else{
      	/*
               * Catch too large forward jumps too:
               */
              if(unlikely(clock + delta > rq->tick_timestamp + TICK_NSEC)){
      	if(clock < rq->tick_timestamp + TICK_NSEC)
                      clock = rq->tick_timestamp + TICK_NSEC;
      	else
                      clock++;
              rq->clock_overflows++;
      	}else{
      	    if(unlikely(delta > rq->clock_max_delta))
                      rq->clock_max_delta = delta;
                  clock += delta;
              }
          }
          rq->prev_clock_raw = now;
          rq->clock = clock;
      }
    • 不考虑其中的unlikely语句,可以看出该函数的主要功能是更新rq队列的时钟。
      <kernel/sched_fair.c>
      static void update_curr(struct cfs_rq *cfs_rq)
      {
          struct sched_entity *curr = cfs_rq->curr;
          u64 now = rq_of(cfs_rq)->clock;
          unsignedlong delta_exec;
          if(unlikely(!curr))
          return;
          /*
           * Get the amount of time the current task was running
           * since the last time we changed load (this cannot
           * overflow on 32 bits):
           */
          delta_exec =(unsignedlong)(now - curr->exec_start);
          __update_curr(cfs_rq, curr, delta_exec);
          curr->exec_start = now;
          if(entity_is_task(curr)){
          struct task_struct *curtask = task_of(curr);
              cpuacct_charge(curtask, delta_exec);
          }
      }
      <kernel/sched_fair.c>
      /*
       * Update the current task's runtime statistics. Skip current tasks that
       * are not in our scheduling class.
       */
      static inline void
      __update_curr(struct cfs_rq *cfs_rq,struct sched_entity *curr,
      		unsignedlong delta_exec)
      {
          unsignedlong delta_exec_weighted;
          u64 vruntime;
          schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
          curr->sum_exec_runtime += delta_exec;
          schedstat_add(cfs_rq, exec_clock, delta_exec);
          delta_exec_weighted = delta_exec;
          if(unlikely(curr->load.weight != NICE_0_LOAD)){
              delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
              	 	    &curr->load);
          }
          curr->vruntime += delta_exec_weighted;
          /*
           * maintain cfs_rq->min_vruntime to be a monotonic increasing
           * value tracking the leftmost vruntime in the tree.
           */
          if(first_fair(cfs_rq)){
              vruntime = min_vruntime(curr->vruntime,
                      __pick_next_entity(cfs_rq)->vruntime);
          }else
              vruntime = curr->vruntime;
          cfs_rq->min_vruntime =
              max_vruntime(cfs_rq->min_vruntime, vruntime);
      }
    • update_curr()函数更新当前正在运行进程实际已经运行的总时间和对应的虚拟运行时间。它首先计算rq队列的时钟与当前调度实体(姑且看做进程)的开始执行时间exec_start之间的时间差值,得到进程的实际运行时间的增量。然后调用该函数__update_curr():                                                             a、将该时间增量加到进程的总运行时间sum_exec_runtime上。                                                                                           b、根据进程权重计算虚拟运行时间的增量delta_exec_weighted。如果进程nice值不为零,则需要调用函数calc_delta_fair()。该函数本质上的工作就是计算delta_exec_weighted * NICE_0_LOAD /curr->load.weight,即根据进程权重对时间增量进行放缩,得到虚拟运行时间的增量。                               c、把delta_exec_weighted加到curr->cruntime上更新进程的虚拟运行时间。
    • 最后更新min_runtime,保证该值是递增的。
    从红黑树添加和删除进程
    • 该操作分别由函数__enqueue_entity()和__dequeue_entity()完成,将进程插入红黑树前还要调用函数entity_key()计算键值。
      <kernel/sched_fair.c>
      staticinline s64 entity_key(struct cfs_rq *cfs_rq,struct sched_entity *se)
      {
      	return se->vruntime - cfs_rq->min_vruntime;
      }
      <kernel/sched_fair.c>
      /*
       * Enqueue an entity into the rb-tree:
       */
      staticvoid __enqueue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se)
      {
      	struct rb_node **link =&cfs_rq->tasks_timeline.rb_node;
      	struct rb_node *parent = NULL;
      	struct sched_entity *entry;
      	s64 key = entity_key(cfs_rq, se);
      	int leftmost =1;
      	/*
      	 * Find the right place in the rbtree:
      	 */
      	while(*link){
      		parent =*link;
      		entry = rb_entry(parent,struct sched_entity, run_node);
      		/*
      		 * We dont care about collisions. Nodes with
      		 * the same key stay together.
      		 */
      		if(key < entity_key(cfs_rq, entry)){
      			link =&parent->rb_left;
      			leftmost = 1;
      		}else{
      			link =&parent->rb_right;
      			leftmost =0;
      		}
      	}
      	/*
      	 * Maintain a cache of leftmost tree entries (it is frequently
      	 * used):
      	 */
      	if(leftmost)
      		cfs_rq->rb_leftmost =&se->run_node;
      
      	rb_link_node(&se->run_node, parent, link);
      	rb_insert_color(&se->run_node,&cfs_rq->tasks_timeline);
      }
    • __enqueue_entity()函数的执行流程很简单:从cfs_rq的根节点开始,比较该节点代表的进程的键值和要插入进程的键值之间的大小,进而选择该节点的左子树或者右子树继续搜索。如果最后一次比较时该进程的键值仍然更小,说明它就是vruntime最小的进程,leftmost被置位,相应cfs_rq的rb_leftmost的指向也被更新。

      <kernel/sched_fair.c>
      staticvoid __dequeue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se)
      {
      	if(cfs_rq->rb_leftmost ==&se->run_node)
      		cfs_rq->rb_leftmost = rb_next(&se->run_node);
      	rb_erase(&se->run_node,&cfs_rq->tasks_timeline);
      }
    • __dequeue_entity()也只是简单地将调度实体从红黑树中删除,如果该节点还是最左边的叶子节点,则将leftmost的指向修改为它右边的那个叶子节点。

    6.4.5 实时调度类

    实时调度类的调度策略比较简单,使用SCHED_FIFO调度策略的实时进程没有时间片的概念,实时调度类没有调度周期的概念。只要有实时进程,就从优先级最高的开始调度,低优先级的实时进程和普通进程时钟得不到调度的机会,它不像CFS的处理,后者的调度策略中所有优先级的普通进程在一个调度周期内都能得到执行。这里对它只做简单讨论。

    可以看出实时调度是一种比较粗野的调度方式,只要系统中有实时进程,那么普通进程的响应肯定会受到影响。所以系统中实时进程的数目一般都很少。使用下面的命令可以查看系统中的所有实时进程,并显示它们的实时优先级:

    ps -eo pid,tid,class,rtprio,ni,pri,pcpu,stat,comm | awk '$4!~/-/{print $0}'

    下面是我在ubuntu12.04 LTS 32-bit上的测试结果:



    系统中有两个高优先级的实时进程,它们都是内核线程。migration线程完成线程在CPU之间的迁移,以实现负载均衡;watchdog线程则是在系统出现故障的时候重启系统。

    时间记账

    • 实时进程的时间记账也是通过调度实体中的sum_exec_runtime来进行的,它没有使用prev_sum_exec_runtime。CFS中使用了这两个成员是为了统计一个调度周期内每个普通进程实际运行的CPU时间(见周期性调度器),实时调度没有调度周期的概念,所以没有使用prev_sum_exec_runtime。
    • 实时进程的时间记账功能由函数update_curr_rt()完成:
      <kernel/sched_rt.c>
      /*
       * Update the current task's runtime statistics. Skip current tasks that
       * are not in our scheduling class.
       */
      staticvoid update_curr_rt(struct rq *rq)
      {
      struct task_struct *curr = rq->curr;
      	u64 delta_exec;
      if(!task_has_rt_policy(curr))
      return;
      	delta_exec = rq->clock - curr->se.exec_start;
      if(unlikely((s64)delta_exec <0))
      		delta_exec =0;
      	schedstat_set(curr->se.exec_max, max(curr->se.exec_max, delta_exec));
      	curr->se.sum_exec_runtime += delta_exec;
      	curr->se.exec_start = rq->clock;
      	cpuacct_charge(curr, delta_exec);
      }
    • 第一个if语句针对的是那些动态优先级临时提高到实时优先级的进程。
    • 然后根据所在rq队列的时钟计算从这次开始执行到现在的时间差值,加到sum_exec_runtime上,得到该实时进程的总运行时间。
    • 最后更新exec_start。

    6.4.6 周期性调度器——scheduler_tick()

    前面已经提到,周期性调度器并不负责进程的切换,它只是负责更新进程的相关统计信息。周期性调度器是由时钟中断触发的,周期性调度器执行过程中要关闭中断,执行完毕后再打开中断。

    下图是中断执行的过程,我们这里不具体讲解,只关注与时钟中断相关的部分。



    知道了周期性调度器是在哪儿被调用的,下面我们来分析一下scheduler_tick()的代码。

    <kernel/sched.c>
    /*
     * This function gets called by the timer code, with HZ frequency.
     * We call it with interrupts disabled.
     *
     * It also gets called by the fork code, when changing the parent's
     * timeslices.
     */
    void scheduler_tick(void)
    {
    	int cpu = smp_processor_id();
    	struct rq *rq = cpu_rq(cpu);
    	struct task_struct *curr = rq->curr;
    	u64 next_tick = rq->tick_timestamp + TICK_NSEC;
    	spin_lock(&rq->lock);
    	__update_rq_clock(rq);
    	/*
    	 * Let rq->clock advance by at least TICK_NSEC:
    	 */
    	if(unlikely(rq->clock < next_tick))
    		rq->clock = next_tick;
    	rq->tick_timestamp = rq->clock;
    	update_cpu_load(rq);
    	if(curr != rq->idle)/* FIXME: needed? */
    		curr->sched_class->task_tick(rq, curr);
    	spin_unlock(&rq->lock);
    #ifdef CONFIG_SMP
    	rq->idle_at_tick = idle_cpu(cpu);
    	trigger_load_balance(rq, cpu);
    #endif
    }

    周期性调度器首先调用函数__update_rq_clock()更新就绪队列rq的时钟。

    然后更新就绪队列rq的cpu_load[]数组,它保留了5个历史负载值。

    第二个if语句判断当前进程如果不是idle进程的话,则调用该进程的调度类中相应的方法task_tick更新进程的统计信息,包括进程总的运行时间和虚拟运行时间,如果进程用完了这个调度周期内分配给它的CPU时间的话,还要触发主调度器。

    最后,在SMP系统上,调用trigger_load_balance()进行负载均衡。有关负载均衡的话题后面讲解。

    不用的调度类,提供了不同的task_tick方法。对于普通进程,task_tick指向task_tick_fair();对于实时进程,task_tick指向task_tick_rt();对于ilde进程的调度器类,task_tick指向task_tick_idle()。该函数为空,而且不会被调用到。 

    • task_tick_fair
      <kernel/sched_fair.c>
      /*
       * scheduler tick hitting a task of our scheduling class:
       */
      static void task_tick_fair(struct rq *rq,struct task_struct *curr)
      {
      	struct cfs_rq *cfs_rq;
      	struct sched_entity *se =&curr->se;
      	for_each_sched_entity(se){
      		cfs_rq = cfs_rq_of(se);
      		entity_tick(cfs_rq, se);
      	}
      }
      <kernel/sched_fair.c>
      static void entity_tick(struct cfs_rq *cfs_rq,struct sched_entity *curr)
      {
      	/*
      	 * Update run-time statistics of the 'current'.
      	 */
      	update_curr(cfs_rq);
      	if(cfs_rq->nr_running >1||!sched_feat(WAKEUP_PREEMPT))
      		check_preempt_tick(cfs_rq, curr);
      }
      <kernel/sched_fair.c>
      /*
       * Preempt the current task with a newly woken task if needed:
       */
      staticvoid
      check_preempt_tick(struct cfs_rq *cfs_rq,struct sched_entity *curr)
      {
      	unsignedlong ideal_runtime, delta_exec;
      	ideal_runtime = sched_slice(cfs_rq, curr);
      	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
      	if(delta_exec > ideal_runtime)
      		resched_task(rq_of(cfs_rq)->curr);
      }

      a、linux实现了组调度,进程是最小的可调度实体,多个进程可以组成大的调度实体,而这些大的调度实体又可以组成更大的调度实体。for_each_sched_entity宏便是用来遍历直到最高层祖先的。我们这里不考虑组调度的情形,所以可以看成直接调用了entity_tick()。

      b、entity_tick()的工作是调用update_curr()更新当前运行进程的总运行时间和相应的虚拟运行时间,更新exec_start。如果该cfs_rq中的进程多余一个,还要调用check_preempt_tick()。

      c、check_preempt_tick()根据此前已经更新的CPU总运行时间,减去进程本调度周期内被pick_next_task_fair()选中执行时保存到prev_sum_exec_runtime中的运行时间,得到进程在当前调度周期内运行的总时间。如果该值大于通过sched_slice()计算得到的理想运行时间,则说明进程本调度周期内的时间用完了,从而调用resched_task()置位TIF_NEED_RESCHED标志,从而触发主调度器。


    • task_tick_rt

      <kernel/sched_rt.c>
      static void task_tick_rt(struct rq *rq, struct task_struct *p)
      {
      	update_curr_rt(rq);
      	/*
      	 * RR tasks need a special form of timeslice management.
      	 * FIFO tasks have no timeslices.
      	 */
      	if (p->policy != SCHED_RR)
      		return;
      	if (--p->time_slice)
      		return;
      	p->time_slice = DEF_TIMESLICE;
      	/*
      	 * Requeue to the end of queue if we are not the only element
      	 * on the queue:
      	 */
      	if (p->run_list.prev != p->run_list.next) { /* 不是该链表中的唯一进程 */
      		requeue_task_rt(rq, p);
      		set_tsk_need_resched(p);
      	}
      }
    • 实时进程的该方法相对简单:

      a、首先更新进程的实际运行时间。

      b、实时进程有两种调度策略:SCHED_RR和SCHED_FIFO。前者是内核给进程分配一个时间片,使用完了就调度将CPU使用权给到下一个实时进程,后者则是一直一直占用CPU,直到主动放弃CPU为止。函数中接下来对这两种调度策略有不同的处理方式:如果调度策略不是SCHED_RR,也就是SCHED_FIFO,那么直接返回。否则的话递减它的时间片,如果时间片没有用完也直接返回。时间用完了则需要重新赋值为DEF_TIMESLICE,然后判断该优先级的实时进程是不是只有这一个,如果不是的话则将该实时进程放到该优先级的链表的最后面,然后设置TIF_NEED_RESCHED标志,触发主调度器。

      注意: 正在运行的实时进程并没有从链表中删除!

      为了加深理解,下面分别给出针对普通进程和实时进程时的执行流程:




    6.4.7 主调度器——schedule()

    主调度器的工作在于完成进程的切换,将CPU的使用权从一个进程切换到另一个进程。schedule()函数的逻辑还是比较清晰的,下面我们来具体分析一下。

    <kernel/sched.c>
    /*
     * schedule() is the main scheduler function.
     */
    asmlinkage void __sched schedule(void)
    {
    	struct task_struct *prev, *next;
    	long *switch_count;
    	struct rq *rq;
    	int cpu;
    need_resched:
    	preempt_disable();
    	cpu = smp_processor_id();
    	rq = cpu_rq(cpu);
    	rcu_qsctr_inc(cpu);
    	prev = rq->curr;              
    	switch_count = &prev->nivcsw;  /* 用于记录当前进程的切换次数 */
    	release_kernel_lock(prev);
    need_resched_nonpreemptible:
    	schedule_debug(prev);
    	/*
    	 * Do the rq-clock update outside the rq lock:
    	 */
    	local_irq_disable();
    	__update_rq_clock(rq); 
    	spin_lock(&rq->lock);
    	clear_tsk_need_resched(prev); /* 清除TIF_NEED_RESCHED标志 */
            /* state: (-1, 不可运行   0,可运行  > 0 stopped) 
             * PREEMPT_ACTIVE标志表明调度是由抢占引起的 */
    	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
    		if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
    				unlikely(signal_pending(prev)))) {
    			prev->state = TASK_RUNNING;
    		} else {
    			deactivate_task(rq, prev, 1);  
                          		}
    		switch_count = &prev->nvcsw;
    	}
    	if (unlikely(!rq->nr_running))
    		idle_balance(cpu, rq);  
    	prev->sched_class->put_prev_task(rq, prev);
    	next = pick_next_task(rq, prev);
    	sched_info_switch(prev, next);
    	if (likely(prev != next)) {
    		rq->nr_switches++;
    		rq->curr = next;
    		++*switch_count;  
    		context_switch(rq, prev, next); /* unlocks the rq */
    	} else
    		spin_unlock_irq(&rq->lock);
    	if (unlikely(reacquire_kernel_lock(current) < 0)) {
    		cpu = smp_processor_id();
    		rq = cpu_rq(cpu);
    		goto need_resched_nonpreemptible;
    	}
    	preempt_enable_no_resched();
    	if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))   
    		goto need_resched;
    }

    主调度器完成了以下工作:

    首先调用__update_rq_clock()更新rq队列的时钟。

    清除进程的TIF_NEED_RESCHED标志。

    如果进程处于不可运行的状态,那么需要判断进程切换是不是抢占引起的。如果不是,且进程处于TASK_INTERRUPTABLE状态而且收到了信号,则将它的状态修改为TASK_RUNNING,不让进程睡眠。否则的话则需要调用deactivate_task()将进程从就绪队列中删除并清除on_rq标志,然后递减rq队列中的统计数据。
    deactivate_task()的代码如下:
    <kernel/sched.c>
    /*
     * deactivate_task - remove a task from the runqueue.
     */
    static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep)
    {
    	if (p->state == TASK_UNINTERRUPTIBLE)
    		rq->nr_uninterruptible++;
    	dequeue_task(rq, p, sleep);
    	dec_nr_running(p, rq);
    }
    该函数首先调用dequeue_task()从队列中删除进程,然后调用dec_nr_running()递减rq队列中的进程数目和进程权重之和。

    <kernel/sched.c>
    static void dequeue_task(struct rq *rq, struct task_struct *p, int sleep)
    {
    	p->sched_class->dequeue_task(rq, p, sleep);
    	p->se.on_rq = 0;
    }
    <kernel/sched.c>
    static void dec_nr_running(struct task_struct *p, struct rq *rq)
    {
    	rq->nr_running--;
    	dec_load(rq, p);
    }

    dequeue_task()调用进程所属调度类中的方法dequeue_task完成实际的进程出队的操作。对于CFS调度而言,该函数为dequeue_task_fair(),对于实时调度而言,该函数为dequeue_task_rt()。

    • dequeue_task_fair()
      <kernel/sched_fair.c>
      /*
       * The dequeue_task method is called before nr_running is
       * decreased. We remove the task from the rbtree and
       * update the fair scheduling stats:
       */
      staticvoid dequeue_task_fair(struct rq *rq,struct task_struct *p,int sleep)
      {
      <span style="white-space:pre">	</span>struct cfs_rq *cfs_rq;
      <span style="white-space:pre">	</span>struct sched_entity *se =&p->se;
      	for_each_sched_entity(se){
      		cfs_rq = cfs_rq_of(se);
      		dequeue_entity(cfs_rq, se, sleep);
      <span style="white-space:pre">	</span>    /* Don't dequeue parent if it has other entities besides us */
      <span style="white-space:pre">	</span>    if(cfs_rq->load.weight)
      <span style="white-space:pre">		</span>break;
      	    sleep =1;
      <span style="white-space:pre">	</span>}
      }

      我们同样不考虑组调度,该函数就相当于调用了dequeue_entity()。

      <kernel/sched_fair.c>
      staticvoid
      dequeue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se,int sleep)
      {
      <span style="white-space:pre">	</span>/*
      	 * Update run-time statistics of the 'current'.
      	 */
      	update_curr(cfs_rq);
      	update_stats_dequeue(cfs_rq, se);
      ...
      <span style="white-space:pre">	</span>if(se != cfs_rq->curr)
      		__dequeue_entity(cfs_rq, se);
      	account_entity_dequeue(cfs_rq, se);
      }

      该函数首先调用update_curr()更新它的运行统计信息;然后判断se是否等于cfs_rq->curr,一般它们应该是相等的。因为正在执行的进程不在红黑树中,所以就不会调用到__dequeue_entity()。最后调用account_entity_dequeue()递减该fsc_rq的权重load和进程数目nr_running,并将调度实体的on_rq标志清零。

    • dequeue_task_rt()
      kernel/sched_rt.c>
      /*
       * Adding/removing a task to/from a priority array:
       */
      static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int sleep)
      {
      	struct rt_prio_array *array = &rq->rt.active;
      	update_curr_rt(rq);
      	list_del(&p->run_list);
      	if (list_empty(array->queue + p->prio))
      		__clear_bit(p->prio, array->bitmap);
      }

      该函数的过程类似:首先调用update_curr_rt()更新进程统计信息;然后将该进程从对应优先级的链表中删除;最后判断该链表是否为空,如果是,将位图中对应的位清零。

    说完了deactivate_task(),我们接着schedule()的流程往下走。如果rq队列中没有进程可以运行了,则调用idle_balance()尝试从其他CPU的rq队列中迁移进程到本CPU运行。

    调用当前进程所在调度器类的put_prev_task方法处理要被撤销CPU的进程,也就是当前进程,CFS调度器对应函数为put_prev_task_fair(),实时进程对应的函数为put_prev_task_rt()。

    • put_prev_task_fair()
      <pre name="code" class="cpp"><kernel/sched_fair.c>
      /*
       * Account for a descheduled task:
       */
      static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
      {
      	struct sched_entity *se = &prev->se;
      	struct cfs_rq *cfs_rq;
      	for_each_sched_entity(se) {
      		cfs_rq = cfs_rq_of(se);
      		put_prev_entity(cfs_rq, se);
      	}
      }
      <kernel/sched_fair.c>
      static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
      {
      	/*
      	 * If still on the runqueue then deactivate_task()
      	 * was not called and update_curr() has to be done:
      	 */
      	if (prev->on_rq)
      		update_curr(cfs_rq);
      	check_spread(cfs_rq, prev);
      	if (prev->on_rq) {
      		update_stats_wait_start(cfs_rq, prev);
      		/* Put 'current' back into the tree. */
      		__enqueue_entity(cfs_rq, prev);
      	}
      	cfs_rq->curr = NULL;
      }
      
      

      不考虑组调度,直接考察put_prev_entity()。该函数先更新进程统计信息;然后判断进程的on_rq标志是否置位,因为前面我们看到如果进程处于不可运行的状态且不是抢占引起的,它的on_rq标志已经清除了,所以这里需要该判断。如果进程仍然处于可运行状态,则调动__enqueue_entity()将进程插入到红黑树中,以等待下次调度。

    • put_prev_task_rt()
      <kernel/sched_rt.c>
      static void put_prev_task_rt(struct rq *rq,struct task_struct *p)
      {
      	update_curr_rt(rq);
      	p->se.exec_start =0;
      }

      该函数首先调用update_curr_rt()更新它的统计信息,然后将exec_start清零。由于正在运行的实时进程是没有从队列中删除的,它不像 put_prev_task_fair() 一样,还要进程重新入队。

    上述对原来进程的处理完成后,调用pick_next_task()选择下一个要投入运行的进程
    <kernel/sched.c>
    /*
     * Pick up the highest-prio task:
     */
    static inline struct task_struct *
    pick_next_task(struct rq *rq, struct task_struct *prev)
    {
    	const struct sched_class *class;
    	struct task_struct *p;
    	/*
    	 * Optimization: we know that if all tasks are in
    	 * the fair class we can call that function directly:
    	 */
    	if (likely(rq->nr_running == rq->cfs.nr_running)) {
    		p = fair_sched_class.pick_next_task(rq);
    		if (likely(p))
    			return p;
    	}
    	class = sched_class_highest; //&rt_sched_class
    	for ( ; ; ) {
    		p = class->pick_next_task(rq);
    		if (p)
    			return p;
    		/*
    		 * Will never be NULL as the idle class always
    		 * returns a non-NULL p:
    		 */
    		class = class->next;
    	}
    }

    如果rq->nr_running等于cfs_rq->nr_running,说明该CPU的就绪队列中除了idle进程外全部都是普通进程,从而直接调用CFS调度器类 fair_sched_class 的 pick_next_task方法选择一个可以投入运行的进程。否则的话就要按照rt_sched_class  --->fair_sched_class --->idle_sched_class的顺序选择一个进程投入运行。该函数一定能返回一个进程描述符,因为有idle进程做备胎……

    对于上述的三个调度器类,pick_next_task方法分别对应函数 pick_next_task_rt(), pick_next_task_fair()和 pick_next_task_idle()。

    • pick_next_task_fair()
      <kernel/sched_fair.c>
      static struct task_struct *pick_next_task_fair(struct rq *rq)
      {
      	struct cfs_rq *cfs_rq = &rq->cfs;
      	struct sched_entity *se;
      	if (unlikely(!cfs_rq->nr_running))
      		return NULL;
      	do {
      		se = pick_next_entity(cfs_rq);
      		cfs_rq = group_cfs_rq(se);
      	} while (cfs_rq);
      	return task_of(se);
      }

      不考虑组调度,相当于调用函数pick_next_entity()

      <kernel/sched_fair.c>
      static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
      {
      	struct sched_entity *se = NULL;
      	if (first_fair(cfs_rq)) {
      		se = __pick_next_entity(cfs_rq);
      		set_next_entity(cfs_rq, se);
      	}
      	return se;
      }

      该函数通过first_fair()判断cfs_rq的left_most是否指向一个调度实体。如果是,则说明可以选择一个进程投入运行,从而调用__pick_next_entity()返回该最左边的调度实体:

      <kernel/sched_fair.c>
      static inline struct rb_node *first_fair(struct cfs_rq *cfs_rq)
      {
      	return cfs_rq->rb_leftmost;
      }
      static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
      {
      	return rb_entry(first_fair(cfs_rq), struct sched_entity, run_node);
      }

      然后调用set_next_entity()对选中的下一个调度实体完成相应的一些设置:

      <kernel/sched_fair.c>
      static void
      set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
      {
      	/* 'current' is not kept within the tree. */
      	if (se->on_rq) {
      		/*
      		 * Any task has to be enqueued before it get to execute on
      		 * a CPU. So account for the time it spent waiting on the
      		 * runqueue.
      		 */
      		update_stats_wait_end(cfs_rq, se);
      		__dequeue_entity(cfs_rq, se); 
      	}
      	update_stats_curr_start(cfs_rq, se); 
      	cfs_rq->curr = se;
      ...
      	se->prev_sum_exec_runtime = se->sum_exec_runtime; 
      }

      这里首先先判断选择的进程的on_rq标志是不是置位了的,既然进程能够被选择执行,那怎么会不在就绪队列上呢?当然该条件一般应该也是满足的,这时需要调用__dequeue_entity()将进程从红黑树中删除。

      接下来的一步很重要:调用update_stats_curr_start()将调度实体的exec_start更新为rq队列的时钟。对于一个被调度程序选中要投入运行的进程来说,它的exec_start是它被撤销CPU之前更新的,这个值与当前的rq->clock肯定是有一定的差值的,要准确计算进程重新被投入运行以后的运行总时间,则需要将它的exec_start更新到最新的值。

      更新cfs_rq->curr为新选择的进程。

      最后将sum_exec_runtime的值保存到prev_sum_exec_runtime中。我们前面已经看到,在周期性调度器中的时间记账完成以后,会判断该调度周期内当前进程的时间是否已经用完了,判断的标准之一就是此时保存到prev_sum_exec_runtime中的时间值。

    • pick_next_task_rt()
      <kernel/sched_rt.c>
      static struct task_struct *pick_next_task_rt(struct rq *rq)
      {
      	struct rt_prio_array *array = &rq->rt.active;
      	struct task_struct *next;
      	struct list_head *queue;
      	int idx;
      	idx = sched_find_first_bit(array->bitmap);
      	if (idx >= MAX_RT_PRIO)
      		return NULL;
      	queue = array->queue + idx;
      	next = list_entry(queue->next, struct task_struct, run_list);
      	next->se.exec_start = rq->clock;
      	return next;
      }

      该函数首先调用sched_find_first_bit()找到拥有进程的最高优先级链表,将其地址存放在queue中。

      然后将链表中第一个进程的进程描述符地址存放到next中。这里可以看出:对于实时进程,调度器的策略是优先调度排在链表前面的进程。

      和CFS一样,最后也要将exec_start更新为rq队列的时钟。

    • pick_next_task_idle
      <kernel/sched_idletask.c>
      static struct task_struct *pick_next_task_idle(struct rq *rq)
      {
      	schedstat_inc(rq, sched_goidle);
      	return rq->idle;
      }
      该函数直接返回本CPU的idle进程的进程描述符。

    选择了下一个要投入运行的进程以后,如果它是一个新的进程(可以说几乎都是这样的情况,因为系统中同时运行着大量的进程),则首先将rq->curr更新为新的进程描述符,然后调用contex_switch()完成上下文切换,该函数中会调用到switch_to(),此后CPU就到另一个进程的控制路径上去执行程序了。

    如果调度程序再次调度到本次本撤销CPU的进程,则该进程继续执行context_switch()之后的程序,如果此时该进程又被设置了TIF_NEED_RESCHED标志(可能有可运行的实时进程),那么又要重新选择新的进程来投入运行。

    对于不考虑进程因为I/O或者其它原因处于不可运行状态的情况,针对普通进程和实时进程,它们的主调度器schedule()的执行流程分别如下:




    下面是pick_next_task()的执行流程,在查找的过程中,如果找到了可以投入运行的下一个进程,则函数会提前结束,不过图中没有表示出来。


    6.4.8 新建进程的处理和睡眠进程的唤醒

    前面介绍最小虚拟运行时间已经为这部分作好了铺垫,那么我们直接来看linux进程调度时怎么处理这两种情形的。

    (1)首先来看函数place_entity() 

    <kernel/sched_fair.c>
    static void
    place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
    {
    	u64 vruntime;
    	vruntime = cfs_rq->min_vruntime;
        ...
    	/*
    	 * The 'current' period is already promised to the current tasks,
    	 * however the extra weight of the new task will slow them down a
    	 * little, place the new task so that it fits in the slot that
    	 * stays open at the end.
    	 */
    	if (initial && sched_feat(START_DEBIT)) 
    		vruntime += sched_vslice_add(cfs_rq, se);
    	if (!initial) {    
    		/* sleeps upto a single latency don't count. */
    		if (sched_feat(NEW_FAIR_SLEEPERS) && entity_is_task(se))
    			vruntime -= sysctl_sched_latency;
    		/* ensure we never gain time by being placed backwards. */
    		vruntime = max_vruntime(se->vruntime, vruntime);
    	}
    	se->vruntime = vruntime;
    }

    • 该函数会根据sched_feature()查询的结果来执行部分代码,这里保留该函数中我们关心的部分来研究。
    • place_entity()函数是用来调整进程的虚拟运行时间的,当新进程被创建或者进程被唤醒时都需要调整它的vruntime。参数initial表明该进程是不是新建进程。如果是,执行前面if语句的那部分代码;否则就是一个呗唤醒的进程,执行后面的if语句那部分代码。
    • 对于新建进程来说,它的vruntime被设置为min_vruntime + sched_vslice_add(cfs_rq, se),即在min_runtime的基础上加上一个调度周期的时间。这样做的目的有两个:                                                                                                                                                                                        a、如果将新进程的vruntime设置为min_vruntime,那么新进程将会第一个被调度,这样的系统容易受到攻击。只需要不断地fork子进程就可以让CPU忙于处理新进程而不去响应系统中已经存在的其它进程。                                                                                                                                       b、本调度周期内的CPU使用时间已经承诺分配给原本已经存在的进程了,新建进程需要等到下一个调度周期才能运行,不能再当前调度周期内去抢夺其它进程的CPU时间。                                                                                                                                                                                      c、单从这个函数来看,似乎子进程会在父进程之后执行。但是根据前面对fork系统调用的讨论,我们知道linux倾向于先调度子进程,以避免不必要的内存拷贝。那子进程是如何先被调度的呢?见6.4.8节处理新建进程部分。
    • 对于被唤醒的睡眠进程而言,它的vruntime被设置为min_runtime - syscrl_sched_latency。但设置的结果不能使得它的vruntime比原来的还小,否则就成了对该进程的奖励了。所以它的vruntime应该取二者中的最大值。    
    (2)check_preempt_curr()函数

    该函数的作用是判断进程p是否可以抢占当前正在运行的进程,具体操作由调度器类的check_preempt_curr方法完成。CFS调度器类对应的函数为check_preempt_wakeup(),实时调度类对应函数check_preempt_curr_rt(),idle调度类对应方法为check_preempt_curr_idle()。

    <kernel/sched.c>
    staticinlinevoid check_preempt_curr(struct rq *rq,struct task_struct *p)
    {
    	rq->curr->sched_class->check_preempt_curr(rq, p);
    }
    • check_preempt_wakeup()
      <pre name="code" class="cpp"><kernel/sched_fair.c>
      /*
       * Preempt the current task with a newly woken task if needed:
       */
      static void check_preempt_wakeup(struct rq *rq, struct task_struct *p)
      {
      	struct task_struct *curr = rq->curr;
      	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
      	struct sched_entity *se = &curr->se, *pse = &p->se;
      	unsigned long gran;
      	if (unlikely(rt_prio(p->prio))) {
      		update_rq_clock(rq);
      		update_curr(cfs_rq);  
      		resched_task(curr);  
      		return;
      	}
      	/*
      	 * Batch tasks do not preempt (their preemption is driven by
      	 * the tick):
      	 */
      	if (unlikely(p->policy == SCHED_BATCH))
      		return;
      	if (!sched_feat(WAKEUP_PREEMPT))
      		return;
      	... //省略和组调度相关的代码
      	gran = sysctl_sched_wakeup_granularity;
      	if (unlikely(se->load.weight != NICE_0_LOAD))
      		gran = calc_delta_fair(gran, &se->load);
      	if (pse->vruntime + gran < se->vruntime) 
      		resched_task(curr);
      }
      
      
      a、如果进程p是一个实时进程,那么立即请求重新调度,因为实时进程总会抢占普通进程。
      b、如果进程p的调度策略是SCHED_BATCH,那么直接返回,因为该类型的进程从来不抢占其它进程。
      c、接下来的工作很有意思。变量gran被赋值为sysctl_sched_wakeup_granularity,默认值为10ms,然后将gran根据进程的权重换算为虚拟时间得到一个最小时间限额。如果新唤醒进程的虚拟运行时间加上该最小时间限额仍然小于当前进程的虚拟运行时间,那么才请求调度。这样做的目的在于引入了一个“缓冲”,使得进程切换不至于太过频繁,将过多的时间用于上下文切换。
    • check_preempt_curr_rt()
      <kernel/sched_rt.c>
      /*
       * Preempt the current task with a newly woken task if needed:
       */
      static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p)
      {
      	if (p->prio < rq->curr->prio)
      		resched_task(rq->curr);
      }

      该函数比较简单,如果进程p的优先级大于当前进程的优先级,则调用resched_task()设置当前进程的TIF_NEED_RESCHED标志,触发主调度器。

    • check_preempt_curr_idle()
      <kernel/sched_idletask.c>
      /*
       * Idle tasks are unconditionally rescheduled:
       */
      static void check_preempt_curr_idle(struct rq *rq, struct task_struct *p)
      {
      	resched_task(rq->idle);
      }

      对于idle进程而言,只要系统中有其它可运行进程,则无条件放弃对CPU的使用权,所以该函数直接调用resched_task()。

    (3)处理新进程  

    CFS调度器类使用函数task_new_fair()处理新创建的进程,该函数的行为还受到sysctl_sched_child_runs_first的控制,用于判断新建子进程是否应该在父进程之前运行。
    <kernel/sched_fair.c>
    /*
     * Share the fairness runtime between parent and child, thus the
     * total amount of pressure for CPU stays equal - new tasks
     * get a chance to run but frequent forkers are not allowed to
     * monopolize the CPU. Note: the parent runqueue is locked,
     * the child is not running yet.
     */
    static void task_new_fair(struct rq *rq, struct task_struct *p)
    {
    	struct cfs_rq *cfs_rq = task_cfs_rq(p);
    	struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
    	int this_cpu = smp_processor_id();
    	sched_info_queued(p);
    	update_curr(cfs_rq);
    	place_entity(cfs_rq, se, 1);
    	/* 'curr' will be NULL if the child belongs to a different group */
    	if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
    			curr && curr->vruntime < se->vruntime) {
    		/*
    		 * Upon rescheduling, sched_class::put_prev_task() will place
    		 * 'current' within the tree based on its new key value.
    		 */
    		swap(curr->vruntime, se->vruntime);   
    	}
    	enqueue_task_fair(rq, p, 0);
    	resched_task(rq->curr);  
    }
    • 该函数首先调用update_curr()更新当前进程,也就是父进程的时间统计信息。
    • 然后调用place_entity(),初始化新进程的虚拟运行时间 。
    • 如果系统参数sysctl_sched_child_runs_first置位,说明需要使子进程先返回。如果父子进程处于同一个cpu,且父进程的虚拟运行时间更小,那么需要交换父子进程的vruntime,使得在红黑树中子进程排在前面,优先得到调度的机会。
    • 新建进程还要调用enqueue_task_fair()插入到cfs的就绪队列中,该函数最终会调用__enqueue_entity()。
    • 为了使得fork系统调用返回的时候子进程先运行,父进程需要放弃当前调度周期内它剩余的CPU使用时间,所以调用resched_task()设置了它的TIF_NEED_RESCHED标志,系统调用返回的时候主调度器schedule()将会将父进程从CPU上切换下来。
    • 父子进程交换了vruntime,子进程通过place_entity()插入到了红黑树中相应的位置。那么父进程是什么时候调整它的位置的呢?——在schedule()函数中调用put_prev_task方法完成的。
    实时调度器类没有实现task_new方法。

    linux的进程创建使用fork、clone或者vfork系统调用,它们最终都会调用do_fork()。下面列出do_fork()中我们比较关心的部分:
    <kernel/fork.c>
    /*
     *  Ok, this is the main fork-routine.
     *
     * It copies the process, and if successful kick-starts
     * it and waits for it to finish using the VM if required.
     */
    long do_fork(unsigned long clone_flags,
    	      unsigned long stack_start,
    	      struct pt_regs *regs,
    	      unsigned long stack_size,
    	      int __user *parent_tidptr,
    	      int __user *child_tidptr)
    {
    	struct task_struct *p;
    	int trace = 0;
    	long nr;
    	...
    	p = copy_process(clone_flags, stack_start, regs, stack_size,
    			child_tidptr, NULL);
    	/*
    	 * Do this prior waking up the new thread - the thread pointer
    	 * might get invalid after that point, if the thread exits quickly.
    	 */
    	if (!IS_ERR(p)) {
    		struct completion vfork;
    		...
    		if (!(clone_flags & CLONE_STOPPED))
    			wake_up_new_task(p, clone_flags);
    		else
    			p->state = TASK_STOPPED;
    		...
    	} else {
    		nr = PTR_ERR(p);
    	}
    	return nr;
    }
    • copy_process()完成进程创建的大部分工作,分配一个新的进程描述符,并完成一些初始化操作。该函数中又会调用sched_fork()来初始化与进程调度相关的信息:
      <kennel/sched.c>
      /*
       * fork()/clone()-time setup:
       */
      void sched_fork(struct task_struct *p, int clone_flags)
      {
      	int cpu = get_cpu();
      	__sched_fork(p);
      #ifdef CONFIG_SMP
      	cpu = sched_balance_self(cpu, SD_BALANCE_FORK);
      #endif
      	set_task_cpu(p, cpu);
      	/*
      	 * Make sure we do not leak PI boosting priority to the child:
      	 */
      	p->prio = current->normal_prio;   /* 设置p->prio为父进程的normal->prio */
      	if (!rt_prio(p->prio))
      		p->sched_class = &fair_sched_class;
      ...
      }

      a、调用__sched_fork()将进程统计信息清零,设置进程状态为TASK_RUNNING。

      b、将子进程的动态优先级p->prio设置为父进程的普通优先级。

      c、根据动态优先级设置调度类。

    • 如果进程创建时设置了标志CLONE_STOPPED,则将新建进程的状态设置为TASK_STOPPED;否则调用wake_up_new_task()唤醒新创建的进程:
      <kernel/sched.c>
      /*
       * wake_up_new_task - wake up a newly created task for the first time.
       *
       * This function will do some initial scheduler statistics housekeeping
       * that must be done for every newly created context, then puts the task
       * on the runqueue and wakes it.
       */
      void fastcall wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
      {
      	unsigned long flags;
      	struct rq *rq;
      	rq = task_rq_lock(p, &flags);
      	BUG_ON(p->state != TASK_RUNNING);
      	update_rq_clock(rq);
      	p->prio = effective_prio(p);
              
      	if (!p->sched_class->task_new || !current->se.on_rq) {
      		activate_task(rq, p, 0);  /* 参数0表示进程不是被唤醒的 */
      	} else {
      		/*
      		 * Let the scheduling class do new task startup
      		 * management (if any):
      		 */
      		p->sched_class->task_new(rq, p);
      		inc_nr_running(p, rq);
      	}
      	check_preempt_curr(rq, p);
      	task_rq_unlock(rq, &flags);
      }

      a、首先调用update_rq_clock()更新rq队列的时钟。

      b、调用effective_prio()计算进程的动态优先级。

      c、如果进程对应调度器类没有task_new方法,或者当前进程不在就绪队列上(后一个条件什么时候成立?)。那么调用activate_task()将进程加入队列中,对于实时进程就是这种情形。

      d、如果调度器类实现了task_new方法调用该方法将新建进程加入队列中,普通进程就是这种情形,它调用上面提到的task_new_fair()完成该操作。新进程插入红黑树以后,调用inc_nr_running()更新rq队列的进程数目和权重。
    • 上述操作完成以后,wake_up_new_task()调用check_preempt_curr(),后者调用相应调度器类的check_preempt_curr方法来检查并触发对当前进程的抢占。

    下面是新建进程的处理流程:

    • 普通进程

    • 实时进程


    • current为idle进程的情形比较简单,这里就不画图了。
    (4)唤醒抢占
    当使用try_to_wake_up()函数来唤醒一个睡眠进程时,内核使用check_preempt_curr()来判断唤醒进程是否可以抢占当前进程。
    <kernel/sched.c>
    static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
    {
    	int cpu, orig_cpu, this_cpu, success = 0;
    	unsigned long flags;
    	long old_state;
    	struct rq *rq;
    ...
    	update_rq_clock(rq);
    	activate_task(rq, p, 1);
    	check_preempt_curr(rq, p);
    	success = 1;
    out_running:
    	p->state = TASK_RUNNING;
    out:
    	task_rq_unlock(rq, &flags);
    	return success;
    }

    我们只保留了try_to_wakeup()中与进程调度相关的一小段代码。唤醒睡眠进程的主要步骤为:

    •     调用update_rq_clock()更新rq队列的时钟。
    •     调用activate_task()将待唤醒进程加入到就绪队列中。
    •     调用check_preempt_curr()来处理可能发生的进程抢占。

    这对实时进程的activate_task()处理流程上面已经提到过了,这里对普通进程的activate_task()执行流程做简要分析:



    6.4.9 进程的睡眠、退出与进程调度的关系

    我们知道进程从创建到退出可能会经历一系列的状态,前面的讨论中覆盖了进程状态转换中的一部分,如从新建进程从READY状态到RUNNING状态,从RUNNING状态到SLEEP状态,从SLEEP状态唤醒进入READY状态。

    这一节我们讨论另外两个重要的进程状态转换过程——进程从运行状态到睡眠状态和进程退出,以及它们是怎么调用核心调度器的。

    (1)进程的睡眠

    进程在访问临界区中的共享数据或者进行I/O时会进入睡眠状态,这里我们拿sleep_on()和inerruptable_sleep_on()来简单说明一下状态转换过程。这两个函数的不同之处在于。前者使进程进入UNINTERRUPTABLE状态,后者使进程进入INTERRUPTABLE状态。这两个函数实际都是调用sleep_on_common()完成的,只是给的参数不同。


    (2)进程退出


    以exit系统调用为例


    6.5 内核抢占和低延迟

    6.5.1 内核抢占

    内核抢占用来为用户提供更平滑的体验,特别是多媒体环境中。在不支持内核抢占的内核中,内核代码可以一直执行,到它完成为止。调度程序没有办法在一个内核级的任务正在执行的时候重新调度,内核代码一直要执行到完成(返回到用户空间)或明显的阻塞为止。在2.6版本的内核中引入了内核抢占。现在,只要内核是安全的,内核就可以在任何时间抢占正在执行的任务。

    那么,什么时候重新调度才是安全的呢?只要没有持有锁,内核就可以进行抢占。锁是非抢占区域的标志

    (1)抢占计数器

    为了支持内核抢占,每个进程的thread_info中引入了抢占计数器preempt_count。该计数器初始值为0,每当使用锁的时候值加1,释放锁的时候值减1。当其数值为0的时候,内核就可以执行抢占。

    preempt_count是一个32位的字段,这32位又做了如下划分:

    0  ~ 7 preempt_counter,内核抢占计数器(0-255)
    8  ~ 15 softirq counter,软中断计数器(0-255)
    16~ 27 hardirq counter,硬中断计数器(0-4096)
    28 PREEMPT_ACTIVE标志

    • 第一个计数表示内核进入临界区的次数。每次内核进入临界区都会增加该计数,退出临界区的时候又会递减该计数。
    • 第二个计数表示下半部被关闭的次数,也就是正在执行的软中断处理程序的个数,0标志没有软中软正在执行。
    • 第三个计数表示本地CPU中断嵌套的层数,irq_enter()增加该值,irq_exit()减小该值。
    • PREEMPT_ACTIVE标志置位的话,会使得抢占计数器有一个很大的值,这样就区别于普通的抢占计数器加1的影响了。它用于向主调度器schedule()表明,调度不是普通方式触发的,而是由于内核抢占。

    那什么时候会发生内核抢占呢?

    • 从中断返回内核空间的时候,内核会检查need_resched和preempt_count的值。如果TIF_NEED_RESCHED被设置,且preempt_count等于0的话,就会调用主调度器完成进程的切换,实现内核抢占。
    • 释放锁的代码在preempt_count为0的时候,检查need_resched是否被设置。如果设置的话,就会调用调度程序,实现内核抢占。
    • 内核中的进程被阻塞了,或者它显式地调用了schedule(),也会发生内核抢占。这种形式的内核抢占从来都是受支持的,但进程必须清楚自己是可以安全地被抢占的。
    (2)从中断返回内核空间时的内核抢占
    在开启中断的情况下,中断可以打断内核控制路径的运行。在执行完中断处理程序后,由ret_from_except()完成从从中断到内核的返回。流程如下:


    抢占是由preempt_schedule_ieq()完成的,在抢占内核之前,需要先设置进程的PREEMPT_ACTIVE标志,这样在调用schedule()时才能做相应的判断。

    (3)释放锁时的内核抢占
    释放锁的函数都会调用preempt_enable()来开启内核抢占:


    该函数的流程如下: 
    • 将抢占计数器减1.
    • 判断进程的TIF_NEED_RESCHED是否置位,如果是,继续。
    • 调用preempt_schedule()完成进程抢占。
    • 可以抢占的条件是抢占计数器为0且没有关闭中断。如不满足上面的条件,前者如进程还在临界区中;后者是因为中断执行的任务不能被打断,而且此时在执行中断处理函数,没有上下文。如果满足条件的话,设置PREEMPT_ACTIVE标志,并调用schedule()完成进程切换。
    • 在切换回该进程的时候,要需要将其PREEMPT_ACTIVE标志清除。
    (4)为什么要引入PREEMPT_ACTIVE

    在主调度器schedule()中有这么一个判断:

    <kernel/sched.c>
    asmlinkage void __sched schedule(void)
    {
    ...
    if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
    		if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
    				unlikely(signal_pending(prev)))) {
    			prev->state = TASK_RUNNING;
    		} else {
    			deactivate_task(rq, prev, 1);  
                            		}
    		switch_count = &prev->nvcsw;
    	}
    ...
    }

    不考虑进程在此时收到信号的情况,如果进程不是由于内核抢占引起的,才调用deactive_task()将进程从就绪队列中删除(对于CFS调度而器的curr进程就是清除on_rq标志而已,因为进程已经从红黑树中删除了)。那为什么有这个判断呢?

    还是考虑sleep_on_common:

    static long __sched
    sleep_on_common(wait_queue_head_t *q, int state, long timeout)
    {
    	unsigned long flags;
    	wait_queue_t wait;
    	init_waitqueue_entry(&wait, current);
    	__set_current_state(state);
    	spin_lock_irqsave(&q->lock, flags);
    	__add_wait_queue(q, &wait);
    	spin_unlock(&q->lock);
    	timeout = schedule_timeout(timeout);
    	spin_lock_irq(&q->lock);
    	__remove_wait_queue(q, &wait);
    	spin_unlock_irqrestore(&q->lock, flags);
    	return timeout;
    }

    我们考虑一种比较特殊的情况,在__set_current_state()将进程设置为不可运行状态以后,在没有将自己加入相应的等待队列之前,发生了一个中断。中断执行完成后会执行上面提到的preempt_schedule_irq(),并调用到schedule()。如果schedule()中不判断PREEMPT_ACTIVE是否置位,如果此时没有收到信号,则调用deactivate_task()将进程从运行队列删除。这样的话,进程既不存在于等待队列中也不存在于就绪队列中,此后就不可能被唤醒也不会被调度执行了。

    在schedule()函数中加入该判断后即可避免这种情况的发生,保证进程至少会存在于一个队列中,不论是等待队列还是就绪队列。

    总的来说,因为设置进程状态和进程调度之间是有时间间隙的,在这个过程中,内核可能发生很多事件从而发生内核抢占。为了避免已经处于非运行态的进程还没有加入睡眠队列的时候就被抢占然后剔除出运行队列,需要设置PREEMPT_ACTIVE标志,在主调度器中对它们做特殊处理。

    6.5.2 低延迟

    即使没有启用内核抢占,内核也关注提供良好的延迟时间。基本上,内核中耗时长的操作不应该完全占据操作系统。相反,它应该不时地检测是否有另一个进程变为可运行,并在必要的情况调用调度器选择一个相应的进程运行。该机制不依赖于内核抢占,即使内核编译时不支持抢占,也能够降低延迟。

    发起有条件重调度的函数是cond_resched(),其实现如下:

    int __sched cond_resched(void)
    {
    	if (need_resched() && !(preempt_count() & PREEMPT_ACTIVE) &&
    					system_state == SYSTEM_RUNNING) {
    		__cond_resched();
    		return 1;
    	}
    	return 0;
    }

    static void __cond_resched(void)
    {
    #ifdef CONFIG_DEBUG_SPINLOCK_SLEEP
    	__might_sleep(__FILE__, __LINE__);
    #endif
    	/*
    	 * The BKS might be reacquired before we have dropped
    	 * PREEMPT_ACTIVE, which could trigger a second
    	 * cond_resched() call.
    	 */
    	do {
    		add_preempt_count(PREEMPT_ACTIVE);
    		schedule();
    		sub_preempt_count(PREEMPT_ACTIVE);
    	} while (need_resched());
    }

    cond_resched()首先检查TIF_NEED_RESCHED标志是否设置,还要判断PREEMPT_ACTIVE标志是否设置。如果PREEMPT_ACTIVE置位,说明是支持内核抢占的,且进程即将被抢占,已经能保证低延迟了。

    __cond_resched()设置PREEMPT_ACTIVE标志并调用主调度器完成进程切换。

    那如何使用cond_resched()?考虑内核读取与给定内存映射相关的内存页的情况。这可以通过无限循环来完成,直至所有的数据读取完毕:

    for(;;)
    {
         /* 读入数据 */
         if(exit_condition)
                continue;
    }

    如果需要大量的读取操作,可能耗时会很长。由于进程在内核空间中,调度器器无法像在用户空间那样撤销其CPU,假定也没有启用内核抢占。通过在每个循环中调用cond_resched(),即可改进此种情况。

    for(;;)
    {
          cond_resched();
          /* 读入数据 */
          if(exit_condition)
               continue;
    }

    内核代码已经仔细检查过,以找出长时间运行的函数,并在适当之处插入cond_resched()的调用,即使没有显式内额和抢占,也能够保证较高的响应速度。

    总结成一句话就是,在长时间运行的函数中加入主动调度的功能,自己检查是否需要抢占,并在需要的时候完成进程切换。


    6.6 SMP调度

    多处理器系统上,内核必须考虑几个额外的问题,以确保良好的调度。

    • CPU负荷必须尽可能公平地在所有的处理器上共享。
    • 进程与系统中某些处理器的亲和性(affinity)必须是可设置的——绑定CPU。
    • 内核必须能够将进程从一个CPU迁移到另一个。但该选项必须谨慎使用,因为它会严重危害性能。
    进程对特定CPU的亲和性,定义在task_struct的cpus_allowed成员中。linux提供sched_setaffinity系统调用,可修改进程与CPU的现有分配关系。

    6.6.1 数据结构的扩展

    在SMP系统上,每个调度器类的调度方法必须增加两个额外的函数:
    <span style="font-size:10px;"><sched.h>
    #ifdef CONFIG_SMP
    	unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
    			struct rq *busiest, unsigned long max_load_move,
    			struct sched_domain *sd, enum cpu_idle_type idle,
    			int *all_pinned, int *this_best_prio);
    	int (*move_one_task) (struct rq *this_rq, int this_cpu,
    			      struct rq *busiest, struct sched_domain *sd,
    			      enum cpu_idle_type idle);
    #endif</span>

    虽然其名字称之为load_balance,但这些函数并不直接负责处理负载均衡。每当内核认为有必要重新均衡时,核心调度器代码都会调用这些函数。特定于调度器类的函数接下来建立一个迭代器,使得核心调度器能够遍历所有可能迁移到另一个队列的备选进程,但各个调度器类的内部结构不能因为迭代器而暴露给核心调度器。load_balance函数指针采用了一般性的函数load_balance,而move_one_task则使用了iter_move_one_task。这些函数用于不同的目的。

    • iter_move_one_task从最忙碌的就绪队列移出一个进程,迁移到当前CPU的就绪队列。
    • load_balance则允许从最忙的就绪队列分配多个进程到当前CPU,但移动的负荷不能比max_load_move更多。

    负载均衡处理过程是如何发起的?在SMP系统上,周期性调度器函数scheduler_tick按上文所述完成所有系统都需要的任务之后,会调用trigger_load_balance函数。这会引发SCHEDULE_ SOFTIRQ软中断softIRQ,该中断确保会在适当的时机执行run_rebalance_domains。该函数最终对当前CPU调用rebalance_domains,实现负载均衡。

    所有的就绪队列组织为调度域scheduling domain)。这可以将物理上邻近或共享高速缓存的CPU群集起来,应优先选择在这些CPU之间迁移进程。但在"普通"SMP系统上,所有的处理器都包含在一个调度域中。要提的一点是该结构包含了大量参数,可以通过/proc/sys/kernel/cpuX/domainY设置。其中包括了在多长时间之后发起负载均衡(包括最大/最小时间间隔),导致队列需要重新均衡的最小不平衡值,等等。此外该结构还管理一些字段,可以在运行时设置,使得内核能够跟踪记录上一次均衡操作在何时执行,下一次将在何时执行。
    rebalance_domains()从基本调度域开始从下往上遍历所有调度域,判断是否满足该调度域进行load_balance的一些限制条件。如果满足,就调用load_balance()进行进程迁移。


    为执行重新均衡的操作,内核需要更多信息。因此在SMP系统上,就绪队列增加了额外的字段:
    <span style="font-size:10px;"><kernel/sched.c>
    #ifdef CONFIG_SMP
    	struct sched_domain *sd;
    	/* For active balancing */
    	int active_balance;
    	int push_cpu;
    	/* cpu of this runqueue: */
    	int cpu;
    	struct task_struct *migration_thread;
    	struct list_head migration_queue;
    #endif</span>

    就绪队列是特定于CPU的,因此cpu表示了该就绪队列所属的处理器。内核为每个就绪队列提供了一个迁移线程,可以接收迁移请求,这些请求保存在链表migration_queue中。这样的请求通常发源于调度器自身,但如果进程被限制在某一特定的CPU集合上,而不能在当前执行的CPU上继续运行时,也可能出现这样的请求。内核试图周期性地均衡就绪队列,但如果对某个就绪队列效果不佳,则必须使用主动均衡(active balancing)。如果需要主动均衡,则将active_balance设置为非零值,而push_cpu则记录了从哪个处理器发起的主动均衡请求。

    那么load_balance做什么呢?该函数会检测在上一次重新均衡操作之后是否已经过去了足够的时间,在必要的情况下通过调用load_balance发起一轮新的重新均衡操作。该函数的代码流程图如下图所示。该图中描述的是一个简化的版本,因为SMP调度器必须处理大量边边角角的情况。如果都画出来,相关的细节会扰乱图中真正的实质性操作。


    首先该函数必须标识出哪个队列工作量最大。该任务委托给find_busiest_queue,后者对一个特定的就绪队列rq调用。函数迭代所有处理器的队列(或确切地说,当前调度组中的所有处理器),比较其负荷权重。最忙的队列就是最后找到的负荷值最大的队列。

    find_busiest_queue标识出一个非常繁忙的队列之后,如果至少有一个进程在该队列上执行(否则负载均衡就没多大意义),则使用 move_tasks将该队列中适当数目的进程迁移到当前队列。move_tasks函数接下来会调用特定于调度器类的load_balance方法。

    在选择被迁移的进程时,内核必须确保所述的进程:

    •     目前没有运行或刚结束运行,因为对运行进程而言,CPU高速缓存充满了进程的数据,迁移该进程则完全抵消了高速缓存带来的好处;
    •     根据其CPU亲合性,可以在与当前队列关联的处理器上执行。

    如果均衡操作失败(例如,远程队列上所有进程都有较高的内核内部优先级值,即较低的nice值),那么将唤醒负责最忙的就绪队列的迁移线程。为确保主动负载均衡执行得比上述方法更积极一点,load_balance会设置最忙的就绪队列的active_balance标志,并将发起请求的CPU记录到rq->cpu

     6.6.2 迁移线程

    迁移线程用于两个目的。一个是用于完成发自调度器的迁移请求(如迁移新建进程),另外一个是用于实现主动均衡。迁移线程是一个执行migration_thread的内核线程。该函数的代码流程图如下图所示。


    migration_thread内部是一个无限循环,在无事可做时进入睡眠状态。首先,该函数检测是否需要主动均衡。如果需要,则调用 active_load_balance满足该请求。该函数试图从当前就绪队列移出一个进程,且移至发起主动均衡请求CPU的就绪队列。它使用 move_one_task完成该工作,后者又对所有的调度器类,分别调用特定于调度器类的move_one_task函数,直至其中一个成功。注意,这些函数移动进程时会尝试比load_balance更激烈的方法。例如,它们不进行此前提到的优先级比较,因此它们更有可能成功。

    完成主动负载均衡之后,迁移线程会检测migrate_req链表中是否有来自调度器的待决迁移请求。如果没有,则线程发出重调度请求。否则,用__migrate_task完成相关请求,该函数会直接移出所要求的进程,而不再与调度器类进一步交互。


     6.6.3 核心调度器的改变

    除了上述增加的特性之外,在SMP系统上还需要对核心调度器的现存方法作一些修改。虽然到处都是一些小的细节变化,与单处理器系统相比最重要的差别如下所示。

    •  在用exec系统调用启动一个新进程时,是调度器跨越CPU移动该进程的一个良好的时机。事实上,该进程尚未执行,因此将其移动到另一个CPU不会带来对CPU高速缓存的负面效应。exec系统调用会调用挂钩函数sched_exec,其代码流程图如下图所示。
    •  sched_balance_self挑选当前负荷最少的CPU(而且进程得允许在该CPU上运行)。如果不是当前CPU,那么会使用sched_migrate_task,向迁移线程发送一个迁移请求。

    完全公平调度器的调度粒度与CPU的数目是成比例的。系统中处理器越多,可以采用的调度粒度就越大。sysctl_sched_min_granularity和sysctl_sched_latency都乘以校正因子1 +log2(nr_cpus),其中nr_cpus表示现有的CPU的数目。但它们不能超出200毫秒。sysctl_sched_wakeup_granularity也需要乘以该因子,但没有上界。



    6.7 关于CFS讨论的一个更正

    前面对CFS的讨论中提到处于TASK_RUNNING状态的进程在每个调度周期都会得到一次执行机会,这个说法是不对的,应该是最少一次。

    按照内核2.6.24的CFS调度算法,如果一个进程受到了很大的不公平对待,也就是它的vruntime相对来说很小,在这个进程被调度一次以后,它可能还是vruntime最小的那个进程,那么下一次调度器选择投入运行的进程还是它自己。这样,一个调度周期因此而延长了。

    所以存在调度器schedule()中调用pick_next_task()选中的进程还是当前进程的情况,但这种情况的出现概率比较低,其中就包括了上面提到的情况。内核代码也用likely(prev != next)做了优化。



    参考资料:

    TSS任务状态段   http://www.cnblogs.com/guanlaiy/archive/2012/10/25/2738355.html

    Linux进程管理之CFS调度器分析  http://blog.chinaunix.net/uid-20543183-id-1930843.html

    linux2.6.24内核,调度器章节的笔记 http://blog.csdn.net/janneoevans/article/details/8125106

    《深入linux内核架构》

    《linux内核设计与实现》





    展开全文
  • LINUX进程调度

    千次阅读 2012-02-05 21:59:47
    一,进程调度的作用: 顾名思义,进程调度就是对进程进行调度,即负责选择下一个要运行的进程.通过合理的调度,系统资源才能最大限度地发挥作用,多进程才会有并发执行的效果. 二,进度调度的目标和基本工作:...
    一,进程调度的作用:
    顾名思义,进程调度就是对进程进行调度,即负责选择下一个要运行的进程.通过合理的调度,系统资源才能最大限度地发挥作用,多进程才会有并发执行的效果.

    二,进度调度的目标和基本工作:
    进程调度最终要完成的目标就是为了最大限度的利用处理器时间.
    即,只要有可以执行的进程,那么就总会有进程正在执行.当进程数大于处理器个数时,某一时刻总会有一些进程进程不能执行.这些进程等待运行.在这些等待运行的进程中选择一个合适的来执行,是调度程序所需完成的基本工作.

    三,调度策略
    1,考虑到进程类型时:I/O消耗型进程 pk 处理器消耗型进程.
    I/O消耗型进程:指进程大部分时间用来提交I/O请求或者是等待I/O请求.
    处理器消耗型进程:与I/O消耗型相反,此类进程把时间大多用在执行代码上.
    此时调度策略通常要在两个矛盾的目标中寻找平衡:进程响应时间短(优先I/O消耗型进程)和最大系统利用率(优先处理器消耗型进程).
    linux为了保证交互式应用,所以对进程的响应做了优化,即更倾向于优先调度I/O消耗型进程.
    2,考虑到进程优先级时:
    调度算法中最基本的一类就是基于优先级的调度.调度程序总是选择时间片未用尽而且优先级最高的进程运行.
    linux实现了一种基于动态优先级的调度方法.即:一开始,先设置基本的优先级,然后它允许调度程序根据需要加,减优先级.
    eg:如果一个进程在I/O等待上消耗的时间多于运行时间,则明显属于I/O消耗型进程,那么根据1中的考虑,应该动态提高其优先级.
    linux提供了两组独立的优先级范围:
    1)nice值:范围从-20到+19.默认值是0,值越小,优先级越高.nice值也用来决定分配给进程的时间片的长短.
    2)实时优先级:范围为0到99.注意,任何实时进程的优先级都高于普通的进程.
    3,考虑到进程时间片时:
    时间片是一个数值,它表明进程在被抢占前所能持续运行的时间.调度策略必须规定一个默认的时间片.时间片过长,则会影响系统的交互性.时间片过短,则会明显增大因进程频繁切换所耗费的时间.
    调度程度提供较长的默认时间片给交互式程序.此外,linux调度程序还能根据进程的优先级动态调整分配给它的时间片,从而保证了优先级高的进程,执行的频率高,执行时间长.
    当一个进程的时间片耗尽时,则认为进程到期了,此时不能在运行.除非所有进程都耗尽了他们的时间片,此时系统会给所有进程重新计算时间片.

    四,linux调度算法
    下面为实现调度算法时的一些相关知识点和注意事项.
    1,可执行队列(runqueue)
    调度程序中最基本的数据结构是可执行队列(runqueue),其结构定义于kernel/sched.c中.可执行队列是给定处理器上的可执行进程的链表,每个处理器一个.
    获得可执行队列:
    cpu_rq(processor):    获得相关处理器的可执行队列.
    this_rq():            获得当前处理器的可执行队列.
    task_rq(task):        返回给定任务所在的可执行队列.
    在对可执行队列进行操作前,应该先锁住它.锁住运行队列的最常见情况发生在你想锁住的运行队列上恰巧有一个特定的任务在运行.如下:
    task_rq_lock();
    task_rq_unlock();

    struct runqueue *rq;
    unsigned long flags;

    rq = task_rq_lock(task,&flags); /*获得特定任务所对应的可执行队列*/
    /*对可执行队列rq进行操作*/
    task_rq_unlock(rq,&flags);

    锁住当前可执行队列:
    this_rq_lock();
    rq_unlock();
    注意:为了避免死锁,要锁住多个运行队列的代码必须总是按照同样的顺序获取这些锁.
    比如:给锁编号1,2,3,4,5.每次申请锁的次序都是1,2,3,4,5.在没取得1锁之前不可以申请2锁.(这个属于个人理解,不知道正确与否,如有错误,希望看到错误的大侠们给予指正.)
    2,优先级数组.
    每个可运行队列都有两个优先级数组,一个活跃的,一个过期的.优先级数组定义在kernel/sched.c中.
    优先级数组使得:每个优先级都对应一个队列,这个队列上包含着对应优先级的可执行进程链表.
    优先级数组由结构体prio_array描速.

    struct prio_array{
      int nr_active;    /*任务数目*/
      unsigned long bitmap[BITMAP_SIZE];   /*优先级位图*/
      struct list_head queue[MAX_PRIO];    /*优先级队列*/
    };

    每个优先级数组都要包含一个这样的位图成员,至少为每个优先级准备一位.一开始,所有的位都被置为0,当某个拥有一定优先级的进程开始准备执行时,图中相应的位就会被置为1.这样,查找系统中最高优先级就变成查找位图中被设置的第一个位.次功能可以由函数sched_find_first_bit()完成.
    3,重新计算时间片
    新的linux调度程序减少了对循环的依赖.取而代之的是为每个处理器维护两个优先级数组:活动数组和过期数组.活动数组内的进程都还有时间片剩余,而过期数组中的是时间片已经耗尽的进程.当一个进程的时间片耗尽时,它会被移至过期的数组,但在此之前,时间片已经重新计算好了.这样,当活动数组中的进程都已经消耗完时间片后,只需把活动数组和过期数组的指针互换就可以了,非常简单.
    4,schedule()
    schedule():选定下一个进程并切换到它去执行.当内核代码想要休眠或者有哪个进程被抢占,那么会调用该函数.函数实现如下:
    struct task_struct *prev, *next;
    struct list_head *queue;
    struct prio_array *array;
    int idx;
    
    prev = current;
    array = rq->active;
    idx = sched_find_first_bit(array->bitmap);  /*找到位图中第一个被设置的位*/
    queue = array->queue + idx;  /*最高位对应的进程链表*/
    next = list_entry(queue->next, struct task_struct, run_list);
    可以看到,schedule()首先在活动优先级数组中找到第一个被设置的位.该位对应着优先级最高的可执行进程列表,然后调度程序选择这个级别链表里的头一个进程运行.因为这个动作根本没用到循环来搜索链表里最适宜的进程,所以实际上,不存在任何影响schedule()执行瞬间长短的因素,它所用的时间是恒定的.(非常好)
    相关图如下:
    5,计算优先级和时间片
    前面说到,优先级和时间片可以影响调度程序作出决定.下面看看这些是如何设计的.
    进程拥有一个初始的优先级,即前面所说到的nice值.默认0,-20最高,+19最低.保存在进程task_struct的static_prio域中.起名为静态优先级.即,一开始由用户指定后,就不能改变.调度程序要用到的动态优先级存放在prio域里.
    可以通过effective_prio()函数返回一个进程的动态优先级.实现如下:
    动态优先级 = nice + (-5 到 +5)的进程交互性的奖励或罚分.
    那么这里涉及到一个判断进程的交互性强弱的问题.最明显的标准莫过于进程休眠的时间长短.如果一个进程的大部分时间是在休眠,则它就是I/O消耗型的.反之,如果一个进程执行的时间比休眠的时间长,那么它就是处理器消耗型的.
    为了支持这种机制,linux用task_struct中的sleep_avg域来记录一个进程用于休眠和用于执行的时间.范围从0到MAX_SLEEP_AVG.默认为10ms.当一个进程从休眠状态恢复到执行状态时,sleep_avg会根据它休眠的时间长短而增加.直到达到MAX_SLEEP_AVG为止.相反,进程每运行一个时钟节拍,sleep_avg就做相应的递减,到0为止.
    当一个任务的时间片用完之后,就要根据任务的静态优先级重新计算时间片.task_timeslice()函数为给定任务返回一个新的时间片.时间片的计算只需要把优先级按比例缩放,使其符合时间片的数值范围就可以了.
    调度程序还提供了另外一种机制以支持交互进程:如果一个进程的交互性非常强,那么当它时间片用完后,它会被再放置到活动数组而不是过期数组中.该逻辑在scheduler_tick()中实现:
    struct task_struct *task;
    struct runqueue *rq;

    task = current;
    rq = this_rq();

    if (!--task->time_slice) {
            if (!TASK_INTERACTIVE(task) || EXPIRED_STARVING(rq))
                    enqueue_task(task, rq->expired);
            else
                    enqueue_task(task, rq->active);
    }
    宏TASK_INTERACTIVE()根据进程的nice值来判定它是不是一个交互性特别强的进程(nice值越小,交互性越强).
    宏EXPIRED_STARVING()负责检查过期的数组内的进程是否处于饥饿状态,即是否已经较长时间没有切换数组了.如果有,则将进程放入过期数组中,以防止饥饿加重.
    6,休眠和唤醒
    休眠过程:进程把自己标记成休眠状态,把自己从可执行队列移出,放入等待队列,然后调用schedule()选择和执行一个其他进程.
    唤醒的过程刚好相反,即进程被设置为可执行状态,然后从等待队列中移至可执行队列中.
    等待队列的创建:
    静态:DECLARE_WAITQUEUE()
    动态:init_waitqueue_head()
    睡眠的简单代码如下:
    /* 'q' is the wait queue we wish to sleep on */
    DECLARE_WAITQUEUE(wait, current);

    add_wait_queue(q, &wait);
    while (!condition) {     /* condition is the event that we are waiting for */
            set_current_state(TASK_INTERRUPTIBLE); /* or TASK_UNINTERRUPTIBLE */
            if (signal_pending(current))
                    /* handle signal */
            schedule();
    }
    set_current_state(TASK_RUNNING);
    remove_wait_queue(q, &wait);
    唤醒的操作是通过函数wake_up进行的.它会唤醒指定的等待队列上的所有进程.通常哪段代码促使等待条件达成,它就要负责随后调用的wake_up()函数.
    休眠和唤醒之间的关系如图所示:
    7,负载平衡程序.
    针对对称多处理系统,调度程序通过负载平衡程序来提升整体的调度.负载平衡程序保证了每个处理器对应的可执行队列之间的负载处于均衡状态.注意,这是在SMP的情况下,在单处理器下,不会被调用.
    负载平衡程序由kernel/sched.c中的函数load_balance()来实现.
    load_balance()的调用时刻:  1) schedule().当前可执行队列为空时,调用. 2) 每隔一段时间一调用.
    负载平衡程序所做的工作大体可如下图所示.

    五,用户抢占与内核抢占
    用户抢占时:检查need_resched.如果设置了该位,则重新调度.否则返回执行当前进程.
    用户抢占可在以下情况时发生:
    1,从系统调用返回用户空间时.
    2,从中断处理程序返回用户空间时.
    内核抢占时:检查need_resched和preempt_count.如果need_resched被设置,preempt_count为0,则调用schedule().如果need_resched被设置,preempt_count非0,则返回执行当前进程.
    内核抢占可能会发生在以下情况时:
    1,当中断处理程序正在执行,且返回内核空间之前.
    2,当内核代码再一次具有可抢占性的时候.
    3,内核中的任务显式调用schedule()时.
    4,如果内核中的任务阻塞(这也同样会导致调用schedule()).
    展开全文
  • 很多工程师碰到一个共性的问题:Linux工程师很多,甚至有很多有多年工作经验,但是对一些Linux内存管理和linux进程管理关键概念的理解非常模糊,比如不理解CPU、内存资源等的真正分布,具体的工作机制,这使得他们对...

     

    《穆赫兰道》与《内陆帝国》

     

    我在多年的工程生涯中发现很多工程师碰到一个共性的问题:Linux工程师很多,甚至有很多有多年工作经验,但是对一些Linux内存管理和linux进程管理关键概念的理解非常模糊,比如不理解CPU、内存资源等的真正分布,具体的工作机制,这使得他们对很多问题的分析都摸不到方向。比如进程的调度延时是多少?Linux能否硬实时?多核下多线程如何执行?系统的内存究竟耗到哪里去了?我写的应用程序究竟耗了多少内存?什么是内存泄漏,如何判定内存是否真的泄漏?CPU速度、内存大小和系统性能的关联究竟是什么?内存和I/O存在着怎样的千丝万缕的联系?

    若不能回答上述问题,势必造成Linux开发过程中的抓瞎,出现关键bug和性能问题后丈二摸不着。从某种意义上来说,Linux进程调度和Linux内存管理之于Linux,类似任督两脉之于人体。任督两脉属于奇经八脉,任脉主血,为阴脉之海;督脉主气,为阳脉之海。任督两脉分别对十二正经脉中的手足六阴经与六阳经脉起着主导作用,任督通则百脉皆通。对Linux进程调度和Linux内存管理的理解,可以极大地打通我们对Linux系统架构,性能瓶颈,进程资源消耗等一系列问题的理解。

     

    但是,对这两个知识点的理解,本身有一定的难度,尤其是Linux内存管理,看资料都很难看懂。若调度器是悬疑惊悚片鬼才大卫·林奇的《穆赫兰道》,Linux内存管理则极似他的《内陆帝国》,为Linux最晦涩的部分。坦白讲,《穆赫兰道》给我的感觉是晦涩而惊艳,而《内陆帝国》让我感觉到自己在吃屎,实在是只有阴暗、晦涩、看不到希望。

    我在学习Linux内存管理的时候,同样有看《内陆帝国》的强烈不愉悦感,整部电影构造的弗洛伊德《梦的解析》的世界有太多苍白的细节,沉闷的对白,阴暗的画面,而没有一个最初层叠的整体概念。逃离这个噩梦,唯一的方法,我们势必应该以一种最简单可靠地方式来理解Linux进程调度和Linux内存管理的精髓,这个时候,细节已经显得不那么重要,而concept则需要吃透再吃透。很多人读Linux的书陷入了纷繁芜杂的细节,而没有理解concept,这个时候,细节会显得那么苍白无力和流离失所。所以,我们更有必要明确每一个工作机制,以及这些工作机制背后的原因,此后,细节只是一个具体的实现。细节是会变的,唯概念不破。

    带着问题上路

    一切的学习都是为了解决问题,而不是为了学习而学习。为了学习而学习,这种行为实在是太傻了,因为最终也学不好。所以我们要弄清楚Linux进程调度和Linux内存管理究竟能解决什么样的问题。

    Linux进程调度以及配套的进程管理回答如下问题:

     

    1.    Linux进程和线程如何创建、退出?进程退出的时候,自己没有释放的资源(如内存没有free)会怎样?

    2.    什么是写时拷贝?

    3.    Linux的线程如何实现,与进程的本质区别是什么?

    4.    Linux能否满足硬实时的需求?

    5.    进程如何睡眠等资源,此后又如何被唤醒?

    6.    进程的调度延时是多少?

    7.    调度器追求的吞吐率和响应延迟之间是什么关系?CPU消耗型和I/O消耗型进程的诉求?

    8.    Linux怎么区分进程优先级?实时的调度策略和普通调度策略有什么区别?

    9.    nice值的作用是什么?nice值低有什么优势?

    10.  Linux可以被改造成硬实时吗?有什么方案?

    11.  多核、多线程的情况下,Linux如何实现进程的负载均衡?

    12.  这么多线程,究竟哪个线程在哪个CPU核上跑?有没有办法把某个线程固定到某个CPU跑?

    13.  多核下如何实现中断、软中断的负载均衡?

    14.  如何利用cgroup对进行进程分组,并调控各个group的CPU资源?

    15.  CPU利用率和CPU负载之间的关系?CPU负载高一定用户体验差吗?

    Linux内存管理回答如下问题:

     

    1.    Linux系统的内存用掉了多少,还剩余多少?下面这个free命令每一个数字是什么意思?

     

    2.    为什么要有DMA、NORMAL、HIGHMEM zone?每个zone的大小是由谁决定的?

    3.    系统的内存是如何被内核和应用瓜分掉的?

    4.    底层的内存管理算法buddy是怎么工作的?它和内核里面的slab分配器是什么关系?

    5.    频繁的内存申请和释放是否会导致内存的碎片化?它的后果是什么?

    6.    Linux内存耗尽后,系统会发生怎样的情况?

    7.    应用程序的内存是什么时候拿到的?malloc()成功后,是否真的拿到了内存?应用程序的malloc()与free()与内核的关系究竟是什么?

    8.    什么是lazy分配机制?应用的内存为什么会延后以最懒惰的方式拿到?

    9.    我写的应用究竟耗费了多少内存?进程的vss/rss/pss/uss分别是什么概念?虚拟的,真实的,共享的,独占的,究竟哪个是哪个?

    10.  内存为什么要做文件系统的缓存?如何做?缓存何时放弃?

    11.  Free命令里面显示的buffers和cached分别是什么?二者有何区别?

    12.  交换分区、虚拟内存究竟是什么鬼?它们针对的是什么性质的内存?什么是匿名页?

    13.  进程耗费的内存、文件系统的缓存何时回收?回收的算法是不是类似LRU?

    14.  怎样追踪和判决发生了内存泄漏?内存泄漏后如何查找泄漏源?

    15.  内存大小这样影响系统的性能?CPU、内存、I/O三角如何互动?它们如何综合决定系统的一些关键性能?

    以上问题,如果您都能回答,那么恭喜您,您是一个概念清楚的人,Linux出现吞吐低、延迟大、响应慢等问题的时候,你可以找到一个可能的方向。如果您只能回答低于1/3的问题,那么,Linux对您仍然是一片空白,出现问题,您只会陷入瞎猫子乱抓,而捞不到耗子的困境,或者胡乱地意测问题,陷入不断的低水平重试。

    试图回答这些问题

    本文的目的不是回答这些问题,因为回答这些问题,需要洋洋洒洒数百页的文档,而本文档不会超过10页。所以,本文的目的是试图给出一个回答这些问题的思考问题的出发点,我们倡导面对任何问题的时候,先要弄明白系统的设计目标。

    吞吐vs.响应

    首先我们在思考调度器的时候,我们要理解任何操作系统的调度器设计只追求2个目标:吞吐率大和延迟低。这2个目标有点类似零和游戏,因为吞吐率要大,势必要把更多的时间放在做真实的有用功,而不是把时间浪费在频繁的进程上下文切换;而延迟要低,势必要求优先级高的进程可以随时抢占进来,打断别人,强行插队。但是,抢占会引起上下文切换,上下文切换的时间本身对吞吐率来讲,是一个消耗,这个消耗可以低到2us或者更低(这看起来没什么?),但是上下文切换更大的消耗不是切换本身,而是切换会引起大量的cache miss。你明明weibo跑的很爽,现在切过去微信,那么CPU的cache是不太容易命中微信的。