linux 内核调度算法_linux内核调度算法 - CSDN
精华内容
参与话题
  • Linux内核(2.6)进程调度算法

    千次阅读 2015-05-31 22:42:42
    在Sched.h(include\linux)中定义了进程的状态。 /*  *Task state bitmask. NOTE! These bits are also  *encoded in fs/proc/array.c: get_task_state().  *  * Wehave two separate sets of flags: task

    1.1      进程状态

    在Sched.h(include\linux)中定义了进程的状态。

    /*

     *Task state bitmask. NOTE! These bits are also

     *encoded in fs/proc/array.c: get_task_state().

     *

     * Wehave two separate sets of flags: task->state

     * isabout runnability, while task->exit_state are

     *about the task exiting. Confusing, but this way

     *modifying one set can't modify the other one by

     *mistake.

     */

    #define TASK_RUNNING           0

    #define TASK_INTERRUPTIBLE       1

    #define TASK_UNINTERRUPTIBLE  2

    #define __TASK_STOPPED        4

    #define __TASK_TRACED          8

    /* in tsk->exit_state */

    #define EXIT_ZOMBIE        16

    #define EXIT_DEAD           32

    /* in tsk->state again */

    #define TASK_DEAD          64

    #define TASK_WAKEKILL         128

    #define TASK_WAKING            256

    其实我们只要关心这几个就行了

    #define TASK_RUNNING           0

    #define TASK_INTERRUPTIBLE       1

    #define TASK_UNINTERRUPTIBLE  2

    1.1.1       TASK_RUNNING

    运行态:或者是当前正在运行,或者是在一个等待运行的队列里。运行态的进程可以分为3种情况:内核运行态、用户运行态、就绪态。

    当一个任务(进程)执行系统调用而陷入内核代码中执行时,我们就称进程处于内核运行态(或简称为内核态)。此时处理器处于特权级最高的(0级)内核代码中执行。当进程处于内核态时,执行的内核代码会使用当前进程的内核栈。每个进程都有自己的内核栈。当进程在执行用户自己的代码时,则称其处于用户运行态(用户态)。即此时处理器在特权级最低的(3级)用户代码中运行。当正在执行用户程序而突然被中断程序中断时,此时用户程序也可以象征性地称为处于进程的内核态。因为中断处理程序将使用当前进程的内核栈。这与处于内核态的进程的状态有些类似。 
    内核态与用户态是操作系统的两种运行级别,跟intel cpu没有必然的联系, intel cpu提供Ring0-Ring3三种级别的运行模式,Ring0级别最高,Ring3最低。Linux使用了Ring3级别运行用户态,Ring0作为 内核态,没有使用Ring1和Ring2。Ring3状态不能访问Ring0的地址空间,包括代码和数据。Linux进程的4GB地址空间,3G-4G部 分大家是共享的,是内核态的地址空间,这里存放在整个内核的代码和所有的内核模块,以及内核所维护的数据。用户运行一个程序,该程序所创建的进程开始是运行在用户态的,如果要执行文件操作,网络数据发送等操作,必须通过write,send等系统调用,这些系统调用会调用内核中的代码来完成操作,这时,必须切换到Ring0,然后进入3GB-4GB中的内核地址空间去执行这些代码完成操作,完成后,切换回Ring3,回到用户态。这样,用户态的程序就不能 随意操作内核地址空间,具有一定的安全保护作用。

    用户态切换到内核态的3种方式

    A)    系统调用

    这是用户态进程主动要求切换到内核态的一种方式,用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作,比如前例中fork()实际上就是执行了一个创建新进程的系统调用。而系统调用的机制其核心还是使用了操作系统为用户特别开放的一个中断来实现,例如Linux的int 80h中断。

    B) 异常

    当CPU在执行运行在用户态下的程序时,发生了某些事先不可知的异常,这时会触发由当前运行进程切换到处理此异常的内核相关程序中,也就转到了内核态,比如缺页异常。

    C) 外围设备的中断

    当外围设备完成用户请求的操作后,会向CPU发出相应的中断信号,这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序,如果先前执行的指令是用户态下的程序,那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成,系统会切换到硬盘读写的中断处理程序中执行后续操作等。

    这3种方式是系统在运行时由用户态转到内核态的最主要方式,其中系统调用可以认为是用户进程主动发起的,异常和外围设备中断则是被动的。

    1.1.2       TASK_INTERRUPTIBLE

    可中断的睡眠态。进程被阻塞,它在等待某些条件来执行。

    1.1.3       TASK_UNINTERRUPTIBLE

    不可中断的睡眠态。这个状态只能被wake_up()唤醒。

    1.1.4       TASK_STOPPED

    停止态:这种情况发生在进程收到SIGSTOP, SIGTSTP, SIGTTIN或SIGTTOU信号,或者在它被调试的时候收到任何信号的时候。可向其发送SIGCONT信号让进程转换到可运行状态。

    1.2      进程调度算法

    1.2.1       抢占型多任务

    调度器背后的思想是为了最好的利用处理器资源。假设系统中可运行的进程的数量大于系统处理器的数量,那么必须决定哪个进程需要优先运行,这其实是选出最优先的k个进程的问题,k就是处理器的数目。而调度器就是解决这个问题的。

    世界上的多任务操作系统分为两种风格:合作型多任务和抢占型多任务。Linux,像所有Unix和大多数现代操作系统一样,提供抢占型多任务。调度器一旦决定运行一个进程,它就会毫无情面的挂起一个当前正在运行的进程。这样的动作称为抢占。一个进程在抢占之前运行的时间是预设好的,叫做时间片。管理时间片是调度算法的一部分。

    而在合作型多任务中,任务切换只能依靠一个任务去主动放弃CPU。这种主动放弃叫做yield----就像pthread中的一样。目前的系统很少有采用这种调度策略的。

    从kernel 2.5开始,调度器的算法做了很大的调整,时间复杂度降到了O(1)。下面我们来看它的设计和实现

    1.2.2       时间片

    时间片是决定了一个任务在没有被抢占的理想情况下可以运行多久。时间片的长度很难确定:时间片太长会导致系统交互性能不好,时间片太短会导致进程切换频繁,浪费系统资源。而且还需要考虑进程的目的,比如偏于IO交互的进程(比如响应触摸屏操作的进程)和偏于处理器运算的进程(比如视频解码进程)设计目的是不一样的,UNIX系统认为,偏于IO的进程需要快速响应,这种策略也影响了时间片的分配策略。

    另外调度系统需要满足两个自相矛盾的目标:最小化的进程响应时间,最大化的系统工作效率。前者倾向于IO消耗型进程,后者倾向于CPU消耗型进程。

    进程调度算法是基于优先级的,而优先级基于进程对处理器时间的需求和他们自己的价值。高优先级的进程会优先得到调度,而相同优先级的进程会排队循环的得到调度。优先级和时间片的关系也是比较微妙,有的系统是正相关的,比如Linux。也就是说,优先级越高,时间片越大。

    1.2.3       优先级

    Linux的进程分普通进程和实时进程,而实时进程又分SCHED_FIFOSCHED_RR,它们只有静态优先级,范围从099,而普通进程的优先级是从100139,所以实时进程比普通进程的优先级高。

    #define SCHED_NORMAL    0      //非实时进程,基于优先级的轮回法(Round Robin)

    #define SCHED_FIFO      1      //实时进程,先进先出

    #define SCHED_RR        2      //实时进程,基于优先级的轮回法(Round Robin)

    对相同优先级的任务,SCHED_RR是分配给每个任务一个特定的时间片,然后轮转依次执行;而SCHED_FIFO则是让一个任务执行完再调度下一个任务,而顺序就是按照创建的先后。当一个FIFO进程变得可以运行时,它会持续的跑直到阻塞或自己放弃了CPU,只有高优先级的实时进程可以抢占它。

    SCHED_RR和SCHED_FIFO唯一不同的地方是拥有了时间片。当时间片用完时,不管这个线程优先级有多高,都不会在运行,而是进入就绪队列,等待下一个时间片到来。可以这么说,因为有了时间片,RR进程多了一些可以被中断的机会。

    SCHED_NORMAL就是普通进程,它不仅有静态优先级,还有动态优先级。

    在定义进程的时候就定义了它的静态优先级,这是用nice值换算出来的。nice值从-20到19,它决定了优先级和时间片,19是最低的而-20最高。所以我们也可以认为nice值就是静态优先级。普通进程的静态优先级范围从100(最高优先级)到139(最低优先级)。

    NICE值和静态优先级的关系:

    /*

     * Convertuser-nice values [ -20 ... 0 ... 19 ]

     * tostatic priority [ MAX_RT_PRIO..MAX_PRIO-1 ],

     * andback.

     */

    #define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)

    #define PRIO_TO_NICE(prio)  ((prio) - MAX_RT_PRIO - 20)

    #define TASK_NICE(p)            PRIO_TO_NICE((p)->static_prio)

    动态优先级是由静态优先级和“bonus”一起算出来的,下面这个宏计算某进程的bonus:

    #define CURRENT_BONUS(p) \

           (NS_TO_JIFFIES((p)->sleep_avg)* MAX_BONUS / \

                  MAX_SLEEP_AVG)

    Bonus是用sleep_avg来算出来的,它随着进程的睡眠而增长,随着进程的运行而减少,可以认为Bonus是平均睡眠时间的一种表达形式,IO倾向的进程会得到调度程序的奖励, 即Bonus为正,CPU倾向的进程会得到调度程序的处罚,即Bonus为负。

    而计算动态优先级的函数是

    static int effective_prio(task_t *p)

    {

           intbonus, prio;

           if(rt_task(p))

                  return p->prio;

           bonus= CURRENT_BONUS(p) - MAX_BONUS / 2;

           prio= p->static_prio - bonus;

           if(prio < MAX_RT_PRIO)

                  prio= MAX_RT_PRIO;

           if(prio > MAX_PRIO-1)

                  prio= MAX_PRIO-1;

           returnprio;

    }

    通常说的优先级指的是动态优先级。

    下面的函数用来重新计算时间片,注意是用静态优先级计算的,实时进程的时间片相对普通进程要大一些。所有进程的时间片和优先级成正比,比如-20对应800ms,0对应100ms,19对应5ms,反正无论一个进程优先级多低,它都会有时间片资源的。

    #define SCALE_PRIO(x, prio) \

           max(x* (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE)

    static unsigned int task_timeslice(task_t*p)

    {

           if(p->static_prio < NICE_TO_PRIO(0))

                  returnSCALE_PRIO(DEF_TIMESLICE*4, p->static_prio);

           else

                  returnSCALE_PRIO(DEF_TIMESLICE, p->static_prio);

    }

    1.2.4       进程调度

    /*

     *This is the main, per-CPU runqueue data structure.

     *

     *Locking rule: those places that want to lock multiple runqueues

     *(such as the load balancing or the thread migration code), lock

     * acquireoperations must be ordered by ascending &runqueue.

     */

    struct runqueue {

           spinlock_tlock;

           /*

            * nr_running and cpu_load should be in thesame cacheline because

            * remote CPUs use both these fields when doingload calculation.

            */

           unsignedlong nr_running;

    #ifdef CONFIG_SMP

           unsignedlong cpu_load;

    #endif

           unsignedlong long nr_switches;

           /*

            * This is part of a global counter where onlythe total sum

            * over all CPUs matters. A task can increasethis counter on

            * one CPU and if it got migrated afterwards itmay decrease

            * it on another CPU. Always updated under therunqueue lock:

            */

           unsignedlong nr_uninterruptible;

           unsignedlong expired_timestamp;

           unsignedlong long timestamp_last_tick;

           task_t*curr, *idle;

           structmm_struct *prev_mm;

           prio_array_t*active, *expired, arrays[2];

           intbest_expired_prio;

           atomic_tnr_iowait;

    #ifdef CONFIG_SMP

           structsched_domain *sd;

           /*For active balancing */

           intactive_balance;

           intpush_cpu;

           task_t*migration_thread;

           structlist_head migration_queue;

    #endif

    };


    注意里面定义的prio_array_t *active, *expired, arrays[2]; 它定义了活跃的和过期的两个进程数组,分别对应处于TASK_RUNNING状态的有时间片的进程和消耗尽时间片的进程

    typedef struct prio_array prio_array_t;

    struct prio_array {

           unsignedint nr_active;

           unsignedlong bitmap[BITMAP_SIZE];

           structlist_head queue[MAX_PRIO];

    };

    注意,BITMAP_SIZE是5,也就是5*32=160个bit,MAX_PRIO是140。而queue里包含了每一种优先级进程组成的链表,一共有140个。Sched.c (kernel)中有一个数据结构是runqueues,每个CPU都有一个runqueue,为了避免死锁,试图锁住很多runqueue的代码需要按照相同的顺序去加锁和解锁,比如采用递增的顺序。例如:

       /* to lock ... */

       if (rq1 < rq2) {

           spin_lock(&rq1->lock);

           spin_lock(&rq2->lock);

        }else {

           spin_lock(&rq2->lock);

           spin_lock(&rq1->lock);

        }

       /* manipulate both runqueues ... */

       /* to unlock ... */

       spin_unlock(&rq1->lock);

       spin_unlock(&rq2->lock);

    O(1)算法的实现在于对bitmap的操作,初始情况下所有bit为0,当一个进程状态变为TASK_RUNNING时,active数组中的bitmap对应的位被设置为1。因此寻找哪个优先级的进程可运行的问题就转化为了寻找bitmap中第一个置为1的bit的位置的问题。这个问题显然是个O(1)的问题,函数为sched_find_first_bit。找到这个优先级后,再找到这个优先级对应的进程队列,按照“roundrobin”的方式去找到当前需要运行哪个进程。这种方式是个术语,其实就是指优先级相同的进程公平的获得运行的机会。这段代码是:

    idx =sched_find_first_bit(array->bitmap);

    queue = array->queue + idx;

    next = list_entry(queue->next, task_t,run_list);

    queue->next是采用迭代器的方式返回的链表的下一个元素。

    时间片算法。很多操作系统会在所有能运行的进程时间片都达到0的时候,统一的,一次性的重新计算时间片。而Linux的算法是一旦某进程时间片耗尽,在送到耗尽数组之前,重算它的时间片。这样,耗尽数组中的进程其实都是有一个新的时间片的,这样,当活跃数组中的进程数达到0时,直接交换active和expire指针即可。 这段代码在schedule函数里:

    if (unlikely(!array->nr_active)) {

                  /*

                   * Switch the active and expired arrays.

                   */

                  schedstat_inc(rq,sched_switch);

                  rq->active= rq->expired;

                  rq->expired= array;

                  ……

           }

    这个交换保证整个调度算法O(1)的重要部分。

    总结:Linux的调度策略其实是:优先选择处于运行态且有时间片的进程中优先级最高的那个。

    1.2.5       scheduler_tick

    函数scheduler_tick()会被时钟中断调到, 它更新当前进程的time_slice,并根据time_slice的使用情况(剩余还是耗尽),来做进一步处理。另外,在fork调用中,当改变父进程的时间片时,也会调到这个函数。

    如果是实时进程,先判断是否是RR进程,若是,递减它的时间片。如果时间片已经耗尽,则根据静态优先级重新计算时间片,然后仍然把它塞到活跃数组尾部,如此一来它还有可能被调度到。如果是FIFO进程

    如果是普通进程,需要递减时间片,更新它的动态优先级,根据静态优先级重填时间片,然后判断此进程是否是一个交互性质的进程。若是,还加入到活跃数组中。

     

    1.3      抢占(preemption)

    这篇文章写得很好:http://blog.csdn.net/sailor_8318/article/details/2870184

    Linux为了增加自身的实时性,在2.6版本中支持了内核抢占。当一个进程进入running状态后,内核会检查它的优先级是否大于当前运行的进程的优先级,若是,在一定时间内切换,不管当前进程运行在内核态还是用户态。

    上面讲的是策略,那么,下面看看具体在什么时候切换。

    内核提供了一个标志位need_resched来表示是否需要切换,这个标志位在如下情况下被设置:

    1.  scheduler_tick()检查到一个进程耗尽了它的时间片

    2.  try_to_wake_up()唤醒一个进程

    一旦回到用户态,或者从中断恢复时,内核会去检查这个标志位,若被设置则调用schedule()。从中断可以恢复到用户态,也可以恢复到内核态。

    注意,有几种情况Linux内核不应该被抢占,

    1.   内核正进行中断处理。在Linux内核中进程不能抢占中断(中断只能被其他中断中止、抢占,进程不能中止、抢占中断),在中断例程中不允许进行进程调度。进程调度函数schedule()会对此作出判断,如果是在中断中调用,会打印出错信息。

    2.   内核正在进行中断上下文的Bottom Half(中断的底半部)处理。硬件中断返回前会执行软中断,此时仍然处于中断上下文中。

    3.   内核的代码段正持有spinlock自旋锁、writelock/readlock读写锁等锁,处干这些锁的保护状态中。内核中的这些锁是为了在SMP系统中短时间内保证不同CPU上运行的进程并发执行的正确性。当持有这些锁时,内核不应该被抢占,否则由于抢占将导致其他CPU长期不能获得锁而死等。

    4.   内核正在执行调度程序Scheduler。抢占的原因就是为了进行新的调度,没有理由将调度程序抢占掉再运行调度程序。

    5.   内核正在对每个CPU“私有”的数据结构操作(Per-CPU date structures)。在SMP中,对于per-CPU数据结构未用spinlocks保护,因为这些数据结构隐含地被保护了(不同的CPU有不一样的per-CPU数据,其他CPU上运行的进程不会用到另一个CPU的per-CPU数据)。但是如果允许抢占,但一个进程被抢占后重新调度,有可能调度到其他的CPU上去,这时定义的Per-CPU变量就会有问题,这时应禁抢占。

    为保证Linux内核在以上情况下不会被抢占,抢占式内核使用了一个变量preempt_count,称为内核抢占锁。这一变量被设置在进程的PCB结构task_struct中。每当内核要进入以上几种状态时,变量preempt_count就加1,指示内核不允许抢占。每当内核从以上几种状态退出时,变量preempt_count就减1,同时进行可抢占的判断与调度。

    由于在某些情况下无法进行内核抢占,所以我们说Linux是软实时性的,也就是一般保证实时,但极少情况下可能无法做到。

     

    展开全文
  • Linux内核调度算法

    2017-02-04 15:12:37
    Linux内核调度算法 ================================快速找到最高优先级进程=================== 为什么要了解内核的调度策略呢?呵呵,因为它值得我们学习,不算是废话吧。内核调度程序很先


    转载自  http://www.linuxidc.com/Linux/2012-02/53369.htm


    Linux内核调度算法




    ================================快速找到最高优先级进程===================

    为什么要了解内核的调度策略呢?呵呵,因为它值得我们学习,不算是废话吧。内核调度程序很先进很强大,管理你的LINUX上跑的大量的乱七八糟的进程,同时还保持着对用户操作的高灵敏响应,如果可能,为什么不把这种思想放到自己的应用程序里呢?或者,有没有可能更好的实现自己的应用,使得操作系统能够以自己的意志来分配资源给自己的进程?

    带着这两个问题来看看KERNEL。首先回顾上我们开发应用程序,基本上就两种类型,1、IO消耗型:比如Hadoop上的trunk服务,很明显它的消耗主要在IO上,包括网络IO磁盘IO等等。2、CPU消耗型,比如mapreduce或者其他的需要对大量数据进行计算处理的组件,就象对高清视频压缩成适合手机观看分辨率的进程,他们的消耗主要在CPU上。当两类进程都在一台SERVER上运行时,操作系统会如何调度它们呢?现在的服务器都是SMP多核的,那么一个进程在多CPU时会来回切换吗?如果我有一个程序,既有IO消耗又有CPU消耗,怎么让多核更好的调度我的程序呢?


    又多了几个问题。来看看内核调度程序吧,我们先从它的优先队列谈起吧。调度程序代码就在内核源码的kernel/sched.c的schedule函数中。
    首先看下面的优先级队列,每一个runqueue都有。runqueue是什么?下面会详细说下,现在大家可以理解为,内核为每一颗CPU分配了一个runqueue,用于维护这颗CPU可以运行的进程。runqueue里,有几个成员是prio_array类型,这个东东就是优先队列,先看看它的定义:
    [cpp]
    1. struct prio_array {  
    2.     unsigned int nr_active;    表示等待执行的进程总数  
    3.     unsigned long bitmap[BITMAP_SIZE];    一个unsigned long在内核中只有32位哈,大家要跟64位OS上的C程序中的long区分开,那个是64位的。那么这个bitmap是干什么的呢?它是用位的方式,表示某个优先级上有没有待处理的队列,是实现快速找到最高待处理优先进程的关键。如果我定义了四种优先级,我只需要四位就能表示某个优先级上有没有进程要运行,例如优先级是2和3上有进程,那么就应该是0110.......非常省空间,效率也快,不是吗?  
    4.     struct list_head queue[MAX_PRIO];     与上面的bitmap是对应的,它存储所有等待运行的进程。  
    5. };  
    看看BITMAP_SIZE是怎么算出来的:#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
    那么,LINUX默认配置(如果你用默认选项编译内核的话)MAX_PRIO是140,就是说一共内核对进程一共定义了140种优先级。等待某个CPU来处理的进程中,可能包含许多种优先级的进程,但,LINUX是个抢占式调度算法的操作系统,就是说,需要调度时一定是找到最高优先级的进程执行。上面的BITMAP_SIZE值根据MAX_PRIO算出来为5,那么bitmap实际是32*5=160位,这样就包含了MAX_PRIO的140位。优先级队列是怎么使用的?看2649行代码:idx = sched_find_first_bit(array->bitmap);这个方法就用来快速的找到优先级最高的队列。看看它的实现可以方便我们理解这个优先级位的设计:
    [cpp]
    1. static inline int sched_find_first_bit(unsigned long *b)  
    2. {  
    3.     if (unlikely(b[0]))  
    4.         return __ffs(b[0]);  
    5.     if (unlikely(b[1]))  
    6.         return __ffs(b[1]) + 32;  
    7.     if (unlikely(b[2]))  
    8.         return __ffs(b[2]) + 64;  
    9.     if (b[3])  
    10.         return __ffs(b[3]) + 96;  
    11.     return __ffs(b[4]) + 128;  
    12. }  
    那么__ffs是干什么的?
    [cpp]
    1. static inline int __ffs(int x)  
    2. {  
    3.     int r = 0;  
    4.   
    5.     if (!x)  
    6.         return 0;  
    7.     if (!(x & 0xffff)) {  
    8.         x >>= 16;  
    9.         r += 16;  
    10.     }  
    11.     if (!(x & 0xff)) {  
    12.         x >>= 8;  
    13.         r += 8;  
    14.     }  
    15.     if (!(x & 0xf)) {  
    16.         x >>= 4;  
    17.         r += 4;  
    18.     }  
    19.     if (!(x & 3)) {  
    20.         x >>= 2;  
    21.         r += 2;  
    22.     }  
    23.     if (!(x & 1)) {  
    24.         x >>= 1;  
    25.         r += 1;  
    26.     }  
    27.     return r;  
    28. }  
    sched_find_first_bit返回值就是最高优先级所在队列的序号,与queue是对应使用的哈,queue = array->queue + idx;这样就取到了要处理的进程队列。这个设计在查找优先级时是非常快的,非常值得我们学习。


    好,优先级队列搞明白了,现在来看看runqueue,每个runqueue包含三个优先级队列。
    [cpp]
    1. struct runqueue {  
    2.     spinlock_t lock;   这是个自旋锁,nginx里解决惊群现象时也是用这个。与普通锁的区别就是,使用普通锁时,你去试图拿一把锁,结果发现已经被别人拿走了,你就在那睡觉,等别人锁用完了叫你起来。所以如果有一个人拿住锁了,一百个人都在门前睡觉等。当之前的人用完锁回来后,会叫醒所有100个等锁的人,然后这些人开始互相抢,抢到的人拿锁进去,其他的人继续等。自旋锁不同,当他去拿锁发现锁被别人拿走了,他在那不睡觉的等,稍打个盹就看看自己主动看看锁有没有还回来。大家比较出优劣了吗?  
    3.   
    4.   
    5.     /* 
    6.      * nr_running and cpu_load should be in the same cacheline because 
    7.      * remote CPUs use both these fields when doing load calculation. 
    8.      */  
    9.     unsigned long nr_running;  
    10. #ifdef CONFIG_SMP   
    11.     unsigned long cpu_load;  
    12. #endif   
    13.     unsigned long long nr_switches;  
    14.   
    15.   
    16.     /* 
    17.      * This is part of a global counter where only the total sum 
    18.      * over all CPUs matters. A task can increase this counter on 
    19.      * one CPU and if it got migrated afterwards it may decrease 
    20.      * it on another CPU. Always updated under the runqueue lock: 
    21.      */  
    22.     unsigned long nr_uninterruptible;  
    23.   
    24.   
    25.     unsigned long expired_timestamp;  
    26.     unsigned long long timestamp_last_tick;  
    27.     task_t *curr, *idle;  
    28.     struct mm_struct *prev_mm;  
    29.     prio_array_t *active, *expired, arrays[2];上面说了半天的优先级队列在这里,但是在runqueue里,为什么不只一个呢?这个在下面讲。  
    30.     int best_expired_prio;  
    31.     atomic_t nr_iowait;  
    32.     ... ...  
    33. };  
    LINUX是一个时间多路复用的系统,就是说,通过把CPU执行时间分成许多片,再分配给进程们使用,造成即使单CPU系统,也貌似允许多个任务在同时执行。那么,时间片大小假设为100ms,过短过长,过长了有些不灵敏,过短了,连切换进程时可能都要消耗几毫秒的时间。分给100个进程执行,在所有进程都用完自己的时间片后,需要重新给所有的进程重新分配时间片,怎么分配呢?for循环遍历所有的run状态进程,重设时间片?这个性能无法容忍!太慢了,跟当前系统进程数相关。那么2.6内核怎么做的呢?它用了上面提到的两个优先级队列active和expired,顾名思义,active是还有时间片的进程队列,而expired是时间片耗尽必须重新分配时间片的进程队列。


    这么设计的好处就是不用再循环一遍所有进程重设时间片了,看看调度函数是怎么玩的:
    [cpp]
    1. array = rq->active;  
    2. if (unlikely(!array->nr_active)) {  
    3.     /* 
    4.      * Switch the active and expired arrays. 
    5.      */  
    6.     schedstat_inc(rq, sched_switch);  
    7.     rq->active = rq->expired;  
    8.     rq->expired = array;  
    9.     array = rq->active;  
    10.     rq->expired_timestamp = 0;  
    11.     rq->best_expired_prio = MAX_PRIO;  
    12. else  
    13.     schedstat_inc(rq, sched_noswitch);  
    当所有运行进程的时间片都用完时,就把active和expired队列互换指针,没有遍历哦,而时间片耗尽的进程在出acitve队列入expired队列时,已经单独的重新分配好新时间片了。


    再看一下schedule(void)调度函数,当某个进程休眠或者被抢占时,系统就开始调试schedule(void)决定接下来运行哪个进程。上面说过的东东都在这个函数里有体现哈。
    [cpp]
    1. asmlinkage void __sched schedule(void)  
    2. {  
    3.     long *switch_count;  
    4.     task_t *prev, *next;  
    5.     runqueue_t *rq;  
    6.     prio_array_t *array;  
    7.     struct list_head *queue;  
    8.     unsigned long long now;  
    9.     unsigned long run_time;  
    10.     int cpu, idx;  
    11.   
    12.   
    13.     /* 
    14.      * Test if we are atomic.  Since do_exit() needs to call into 
    15.      * schedule() atomically, we ignore that path for now. 
    16.      * Otherwise, whine if we are scheduling when we should not be. 
    17.      */  
    18.     if (likely(!(current->exit_state & (EXIT_DEAD | EXIT_ZOMBIE)))) {先看看当前运行进程的状态  
    19.         if (unlikely(in_atomic())) {  
    20.             printk(KERN_ERR "scheduling while atomic: "  
    21.                 "%s/0x%08x/%d\n",  
    22.                 current->comm, preempt_count(), current->pid);  
    23.             dump_stack();  
    24.         }  
    25.     }  
    26.     profile_hit(SCHED_PROFILING, __builtin_return_address(0));  
    27.   
    28.   
    29. need_resched:  
    30.     preempt_disable();  
    31.     prev = current;  
    32.     release_kernel_lock(prev);  
    33. need_resched_nonpreemptible:  
    34.     rq = this_rq();      这行找到这个CPU对应的runqueue,再次强调,每个CPU有一个自己的runqueue  
    35.   
    36.   
    37.     /* 
    38.      * The idle thread is not allowed to schedule! 
    39.      * Remove this check after it has been exercised a bit. 
    40.      */  
    41.     if (unlikely(current == rq->idle) && current->state != TASK_RUNNING) {  
    42.         printk(KERN_ERR "bad: scheduling from the idle thread!\n");  
    43.         dump_stack();  
    44.     }  
    45.   
    46.   
    47.     schedstat_inc(rq, sched_cnt);  
    48.     now = sched_clock();  
    49.     if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG))  
    50.         run_time = now - prev->timestamp;  
    51.     else  
    52.         run_time = NS_MAX_SLEEP_AVG;  
    53.   
    54.   
    55.     /* 
    56.      * Tasks with interactive credits get charged less run_time 
    57.      * at high sleep_avg to delay them losing their interactive 
    58.      * status 
    59.      */  
    60.     if (HIGH_CREDIT(prev))  
    61.         run_time /= (CURRENT_BONUS(prev) ? : 1);  
    62.   
    63.   
    64.     spin_lock_irq(&rq->lock);  
    65.   
    66.   
    67.     if (unlikely(current->flags & PF_DEAD))  
    68.         current->state = EXIT_DEAD;  
    69.     /* 
    70.      * if entering off of a kernel preemption go straight 
    71.      * to picking the next task. 
    72.      */  
    73.     switch_count = &prev->nivcsw;  
    74.     if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {  
    75.         switch_count = &prev->nvcsw;  
    76.         if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&  
    77.                 unlikely(signal_pending(prev))))  
    78.             prev->state = TASK_RUNNING;  
    79.         else {  
    80.             if (prev->state == TASK_UNINTERRUPTIBLE)  
    81.                 rq->nr_uninterruptible++;  
    82.             deactivate_task(prev, rq);  
    83.         }  
    84.     }  
    85.   
    86.   
    87.     cpu = smp_processor_id();  
    88.     if (unlikely(!rq->nr_running)) {  
    89. go_idle:  
    90.         idle_balance(cpu, rq);  
    91.         if (!rq->nr_running) {  
    92.             next = rq->idle;  
    93.             rq->expired_timestamp = 0;  
    94.             wake_sleeping_dependent(cpu, rq);  
    95.             /* 
    96.              * wake_sleeping_dependent() might have released 
    97.              * the runqueue, so break out if we got new 
    98.              * tasks meanwhile: 
    99.              */  
    100.             if (!rq->nr_running)  
    101.                 goto switch_tasks;  
    102.         }  
    103.     } else {  
    104.         if (dependent_sleeper(cpu, rq)) {  
    105.             next = rq->idle;  
    106.             goto switch_tasks;  
    107.         }  
    108.         /* 
    109.          * dependent_sleeper() releases and reacquires the runqueue 
    110.          * lock, hence go into the idle loop if the rq went 
    111.          * empty meanwhile: 
    112.          */  
    113.         if (unlikely(!rq->nr_running))  
    114.             goto go_idle;  
    115.     }  
    116.   
    117.   
    118.     array = rq->active;  
    119.     if (unlikely(!array->nr_active)) {       上面说过的,需要重新计算时间片时,就用已经计算好的expired队列了  
    120.         /* 
    121.          * Switch the active and expired arrays. 
    122.          */  
    123.         schedstat_inc(rq, sched_switch);  
    124.         rq->active = rq->expired;  
    125.         rq->expired = array;  
    126.         array = rq->active;  
    127.         rq->expired_timestamp = 0;  
    128.         rq->best_expired_prio = MAX_PRIO;  
    129.     } else  
    130.         schedstat_inc(rq, sched_noswitch);  
    131.   
    132.   
    133.     idx = sched_find_first_bit(array->bitmap);         找到优先级最高的队列  
    134.     queue = array->queue + idx;  
    135.     next = list_entry(queue->next, task_t, run_list);  
    136.   
    137.   
    138.     if (!rt_task(next) && next->activated > 0) {  
    139.         unsigned long long delta = now - next->timestamp;  
    140.   
    141.   
    142.         if (next->activated == 1)  
    143.             delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;  
    144.   
    145.   
    146.         array = next->array;  
    147.         dequeue_task(next, array);  
    148.         recalc_task_prio(next, next->timestamp + delta);  
    149.         enqueue_task(next, array);  
    150.     }  
    151.     next->activated = 0;  
    152. switch_tasks:  
    153.     if (next == rq->idle)  
    154.         schedstat_inc(rq, sched_goidle);  
    155.     prefetch(next);  
    156.     clear_tsk_need_resched(prev);  
    157.     rcu_qsctr_inc(task_cpu(prev));  
    158.   
    159.   
    160.     prev->sleep_avg -= run_time;  
    161.     if ((long)prev->sleep_avg <= 0) {  
    162.         prev->sleep_avg = 0;  
    163.         if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev)))  
    164.             prev->interactive_credit--;  
    165.     }  
    166.     prev->timestamp = prev->last_ran = now;  
    167.   
    168.   
    169.     sched_info_switch(prev, next);  
    170.     if (likely(prev != next)) {              表面现在正在执行的进程,不是选出来的优先级最高的进程  
    171.         next->timestamp = now;  
    172.         rq->nr_switches++;  
    173.         rq->curr = next;  
    174.         ++*switch_count;  
    175.   
    176.   
    177.         prepare_arch_switch(rq, next);  
    178.         prev = context_switch(rq, prev, next);              所以需要完成进程上下文切换,把之前的进程信息CACHE住  
    179.         barrier();  
    180.   
    181.   
    182.         finish_task_switch(prev);  
    183.     } else  
    184.         spin_unlock_irq(&rq->lock);  
    185.   
    186.   
    187.     prev = current;  
    188.     if (unlikely(reacquire_kernel_lock(prev) < 0))  
    189.         goto need_resched_nonpreemptible;  
    190.     preempt_enable_no_resched();  
    191.     if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))  
    192.         goto need_resched;  
    193. }  
    当然,在我们程序中,也可以通过执行以下系统调用来改变自己进程的优先级。nice系统调用可以改变某个进程的基本优先级,setpriority可以改变一组进程的优先级。linux








    =========================CPU时间片如何分配===========================


    内核在微观上,把CPU的运行时间分成许多分,然后安排给各个进程轮流运行,造成宏观上所有的进程仿佛同时在执行。双核CPU,实际上最多只能有两个进程在同时运行,大家在top、vmstat命令里看到的正在运行的进程,并不是真的在占有着CPU哈。

    所以,一些设计良好的高性能进程,比如nginx,都是实际上有几颗CPU,就配几个工作进程,道理就在这。比如你的服务器有8颗CPU,那么nginx worker应当只有8个,当你多于8个时,内核可能会放超过多个nginx worker进程到1个runqueue里,会发生什么呢?就是在这颗CPU上,会比较均匀的把时间分配给这几个nginx worker,每个worker进程运行完一个时间片后,内核需要做进程切换,把正在运行的进程上下文保存下来。假设内核分配的时间片是100ms,做进程切换的时间是5ms,那么进程性能下降还是很明显的,跟你配置的worker有关,越多下降得越厉害。

    当然,这是跟nginx的设计有关的。nginx是事件驱动的全异步进程,本身设计上就几乎不存在阻塞和中断,nginx的设计者就希望每一个nginx worker可以独占CPU的几乎全部时间片,这点就是nginx worker数量配置的依据所在。


    当然,实际的运行进程里,大部分并不是nginx这种希望独占CPU全部时间片的进程,许多进程,比如vi,它在很多时间是在等待用户输入,这时vi在等待IO中断,是不占用时间片的,内核面对多样化的进程,就需要技巧性的分配CPU时间片了。


    内核分配时间片是有策略和倾向性的。换句话说,内核是偏心的,它喜欢的是IO消耗型进程,因为这类进程如果不能及时响应,用户就会很不爽,所以它总会下意识的多分配CPU运行时间给这类进程。而CPU消耗进程内核就不太关心了。这有道理吗?太有了,CPU消耗型慢一点用户感知不出来,电信号和生物信号运转速度差距巨大。虽然内核尽量多的分配时间片给IO消耗型进程,但IO消耗进程常常在睡觉,给它的时间片根本用不掉。很合理吧?


    那么内核具体是怎么实现这种偏心呢?通过动态调整进程的优先级,以及分配不同长短的CPU时间处来实现。先说内核如何决定时间片的长度。

    对每一个进程,有一个整型static_prio表示用户设置的静态优先级,内核里它与nice值是对应的。看看进程描述结构里的static_prio成员。

    [cpp]
    1. struct task_struct {  
    2.     int prio, static_prio;  
    3. ......}  

    nice值是什么?其实就是优先级针对用户进程的另一种表示法,nice的取值范围是-20到+19,-20优先级最高,+19最低。上篇曾经说过,内核优先级共有140,而用户能够设置的NICE优先级如何与这140个优先级对应起来呢?看代码:

    [cpp]
    1. #define MAX_USER_RT_PRIO    100   
    2. #define MAX_RT_PRIO     MAX_USER_RT_PRIO   
    3. #define MAX_PRIO        (MAX_RT_PRIO + 40)  
    可以看到,MAX_PRIO就是140,也就是内核定义的最大优先级了。

    [cpp]
    1. #define USER_PRIO(p)        ((p)-MAX_RT_PRIO)   
    2. #define MAX_USER_PRIO       (USER_PRIO(MAX_PRIO))  
    而MAX_USER_PRIO就是40,意指,普通进程指定的优先级别最多40,就像前面我们讲的那样-20到+19。


    [cpp]
    1. #define NICE_TO_PRIO(nice)  (MAX_RT_PRIO + (nice) + 20)  
    nice值是-20表示最高,对应着static_prio是多少呢?NICE_TO_PRIO(0)就是120,NICE_TO_PRIO(-20)就是100。


    当该进程刚被其父进程fork出来时,是平分其父进程的剩余时间片的。这个时间片执行完后,就会根据它的初始优先级来重新分配时间片,优先级为+19时最低,只分配最小时间片5ms,优先级为0时是100ms,优先级是-20时是最大时间片800ms。我们看看内核是如何计算时间片长度的,大家先看下task_timeslice时间片计算函数:

    [cpp]
    1. #define SCALE_PRIO(x, prio) \   
    2.     max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE)  
    3.   
    4. static unsigned int task_timeslice(task_t *p)  
    5. {  
    6.     if (p->static_prio < NICE_TO_PRIO(0))  
    7.         return SCALE_PRIO(DEF_TIMESLICE*4, p->static_prio);  
    8.     else  
    9.         return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);  
    10. }  
    这里有一堆宏,我们把宏依次列出看看它们的值:
    [cpp]
    1. # define HZ     1000       
    2. #define DEF_TIMESLICE       (100 * HZ / 1000)  
    所以,DEF_TIMESLICE是100。假设nice值是-20,那么static_prio就是100,那么SCALE_PRIO(100*4, 100)就等于800,意味着最高优先级-20情形下,可以分到时间片是800ms,如果nice值是+19,则只能分到最小时间片5ms,nice值是默认的0则能分到100ms。


    貌似时间片只与nice值有关系。实际上,内核会对初始的nice值有一个-5到+5的动态调整。这个动态调整的依据是什么呢?很简单,如果CPU用得多的进程,就把nice值调高点,等价于优先级调低点。CPU用得少的进程,认为它是交互性为主的进程,则会把nice值调低点,也就是优先级调高点。这样的好处很明显,因为1、一个进程的初始优先值的设定未必是准确的,内核根据该进程的实时表现来调整它的执行情况。2、进程的表现不是始终如一的,比如一开始只是监听80端口,此时进程大部分时间在sleep,时间片用得少,于是nice值动态降低来提高优先级。这时有client接入80端口后,进程开始大量使用CPU,这以后nice值会动态增加来降低优先级。


    思想明白了,代码实现上,优先级的动态补偿到底依据什么呢?effective_prio返回动态补偿后的优先级,注释非常详细,大家先看下。

    [cpp]
    1. /* 
    2.  * effective_prio - return the priority that is based on the static 
    3.  * priority but is modified by bonuses/penalties. 
    4.  * 
    5.  * We scale the actual sleep average [0 .... MAX_SLEEP_AVG] 
    6.  * into the -5 ... 0 ... +5 bonus/penalty range. 
    7.  * 
    8.  * We use 25% of the full 0...39 priority range so that: 
    9.  * 
    10.  * 1) nice +19 interactive tasks do not preempt nice 0 CPU hogs. 
    11.  * 2) nice -20 CPU hogs do not get preempted by nice 0 tasks. 
    12.  * 
    13.  * Both properties are important to certain workloads. 
    14.  */  
    15. static int effective_prio(task_t *p)  
    16. {  
    17.     int bonus, prio;  
    18.   
    19.     if (rt_task(p))  
    20.         return p->prio;  
    21.   
    22.     bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;  
    23.   
    24.     prio = p->static_prio - bonus;  
    25.     if (prio < MAX_RT_PRIO)  
    26.         prio = MAX_RT_PRIO;  
    27.     if (prio > MAX_PRIO-1)  
    28.         prio = MAX_PRIO-1;  
    29.     return prio;  
    30. }  
    可以看到bonus会对初始优先级做补偿。怎么计算出这个BONUS的呢?

    [cpp]
    1. #define CURRENT_BONUS(p) \   
    2.     (NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \  
    3.         MAX_SLEEP_AVG)  
    可以看到,进程描述符里还有个sleep_avg,动态补偿完全是根据它的值来运作的。sleep_avg就是关键了,它表示进程睡眠和运行的时间,当进程由休眠转到运行时,sleep_avg会加上这次休眠用的时间。在运行时,每运行一个时钟节拍sleep_avg就递减直到0为止。所以,sleep_avg越大,那么就会给到越大的动态优先级补偿,达到MAX_SLEEP_AVG时会有nice值-5的补偿。


    内核就是这么偏爱交互型进程,从上面的优先级和时间片分配上都能看出来。实际上,内核还有方法对交互型进程搞优待。上篇说过,runqueue里的active和expired队列,一般的进程时间片用完后进expired队列,而对IO消耗的交互型进程来说,则会直接进入active队列中,保证高灵敏的响应,可见什么叫万千宠爱于一身了















    ===============多核系统的负载均衡==================


    多核CPU现在很常见,那么问题来了,一个程序在运行时,只在一个CPU核上运行?还是交替在多个CPU核上运行呢?LINUX内核是如何在多核间调度进程的呢?又是内核又是CPU核,两个核有点绕,下面称CPU处理器来代替CPU核。

    实际上,如果你没有对你的进程做过特殊处理的话,LINUX内核是有可能把它放到多个CPU处理器上运行的,这是内核的负载均衡。上文说过,每个处理器上有一个runqueue队列,表示这颗处理器上处于run状态的进程链表,在多处理器的内核中,就会有多个runqueue,而如果他们的大小很不均衡,就会触发内核的load_balance函数。这个函数会把某个CPU处理器上过多的进程移到runqueue元素相对少的CPU处理器上。

    举个例子来简单说明这个过程吧。当我们刚fork出一个子进程时,子进程也还在当前CPU处理器的runqueue里,它与父进程均分父进程的时间片。当然,时间片与多处理器间的负载均衡没有关系。假设我们的系统是双核的,父进程运行在cpu0上,那么这个fork出来的进程也是在cpu0的runqueue中。

    那么,什么时候会发生负载均衡呢?

    1、当cpu1上的runqueue里一个可运行进程都没有的时候。这点很好理解,cpu1无事可作了,这时在cpu1上会调用load_balance,发现在cpu0上还有许多进程等待运行,那么它会从cpu0上的可运行进程里找到优先级最高的进程,拿到自己的runqueue里开始执行。

    2、第1种情形不适用于运行队列一直不为空的情况。例如,cpu0上一直有10个可运行进程,cpu1上一直有1个可运行进程,显然,cpu0上的进程们得到了不公平的对待,它们拿到cpu的时间要小得多,第1种情形下的load_balance也一直不会调用。所以,实际上,每经过一个时钟节拍,内核会调用scheduler_tick函数,而这个函数会做许多事,例如减少当前正在执行的进程的时间片,在函数结尾处则会调用rebalance_tick函数。rebalance_tick函数决定以什么样的频率执行负载均衡。

    [cpp]
    1. static void rebalance_tick(int this_cpu, runqueue_t *this_rq,  
    2.                enum idle_type idle)  
    3. {  
    4.     unsigned long old_load, this_load;  
    5.     unsigned long j = jiffies + CPU_OFFSET(this_cpu);  
    6.     struct sched_domain *sd;  
    7.   
    8.     /* Update our load */  
    9.     old_load = this_rq->cpu_load;  
    10.     this_load = this_rq->nr_running * SCHED_LOAD_SCALE;  
    11.     /* 
    12.      * Round up the averaging division if load is increasing. This 
    13.      * prevents us from getting stuck on 9 if the load is 10, for 
    14.      * example. 
    15.      */  
    16.     if (this_load > old_load)  
    17.         old_load++;  
    18.     this_rq->cpu_load = (old_load + this_load) / 2;  
    19.   
    20.     for_each_domain(this_cpu, sd) {  
    21.         unsigned long interval;  
    22.   
    23.         if (!(sd->flags & SD_LOAD_BALANCE))  
    24.             continue;  
    25.   
    26.         interval = sd->balance_interval;  
    27.         if (idle != SCHED_IDLE)  
    28.             interval *= sd->busy_factor;  
    29.   
    30.         /* scale ms to jiffies */  
    31.         interval = msecs_to_jiffies(interval);  
    32.         if (unlikely(!interval))  
    33.             interval = 1;  
    34.   
    35.         if (j - sd->last_balance >= interval) {  
    36.             if (load_balance(this_cpu, this_rq, sd, idle)) {  
    37.                 /* We've pulled tasks over so no longer idle */  
    38.                 idle = NOT_IDLE;  
    39.             }  
    40.             sd->last_balance += interval;  
    41.         }  
    42.     }  
    43. }  
    当idle标志位是SCHED_IDLE时,表示当前CPU处理器空闲,就会以很高的频繁来调用load_balance(1、2个时钟节拍),反之表示当前CPU并不空闲,会以很低的频繁调用load_balance(10-100ms)。具体的数值要看上面的interval了。

    当然,多核CPU也有许多种,例如INTEL的超线程技术,而LINUX内核对一个INTEL超线程CPU会看成多个不同的CPU处理器。

    上面说过,如果你没有对你的进程做过特殊处理的话,LINUX内核是有可能把它放到多个CPU处理器上运行的,但是,有时我们如果希望我们的进程一直运行在某个CPU处理器上,可以做到吗?内核提供了这样的系统调用。系统调用sched_getaffinity会返回当前进程使用的cpu掩码,而sched_setaffinity则可以设定该进程只能在哪几颗cpu处理器上执行。当我们对某些进程有强烈的期待,或者想自己来考虑CPU间的负载均衡,可以这么试试哈。





    PS,  引起CPU上下文切换的原因有哪些?

              对于抢占式操作系统而言, 大体有几种:

              1、当前任务的时间片用完之后,系统CPU正常调度下一个任务;

              2、当前任务碰到IO阻塞,调度线程将挂起此任务,继续下一个任务;

              3、多个任务抢占锁资源,当前任务没有抢到,被调度器挂起,继续下一个任务;

              4、用户代码挂起当前任务,让出CPU时间;

              5、硬件中断;

    另外关于性能相关的分析工具有个LMbench, 详细可参考链接:

    http://www.tuicool.com/articles/MjyANr

























    展开全文
  • linux内核的三种主要调度策略

    千次阅读 2017-10-20 14:20:14
    linux内核的三种主要调度策略:1,SCHED_OTHER 分时调度策略, 2,SCHED_FIFO实时调度策略,先到先服务 3,SCHED_RR实时调度策略,时间片轮转 实时进程将得到优先调用,实时进程根据实时优先级决定调度权值。...

    linux内核的三种主要调度策略:

    1SCHED_OTHER 分时调度策略, 

    2SCHED_FIFO实时调度策略,先到先服务 

    3SCHED_RR实时调度策略,时间片轮转

      

    实时进程将得到优先调用,实时进程根据实时优先级决定调度权值。分时进程则通过nicecounter值决定权值,nice越小,counter越大,被调度的概率越大,也就是曾经使用了cpu最少的进程将会得到优先调度。

     

    SHCED_RRSCHED_FIFO的不同:

         当采用SHCED_RR策略的进程的时间片用完,系统将重新分配时间片,并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。     

        SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。

        如果有相同优先级的实时进程(根据优先级计算的调度权值是一样的)已经准备好,FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。

      

    相同点:

        RRFIFO都只用于实时任务。

        创建时优先级大于0(1-99)

        按照可抢占优先级调度算法进行。

        就绪态的实时任务立即抢占非实时任务。

     

    所有任务都采用linux分时调度策略时:

    1,创建任务指定采用分时调度策略,并指定优先级nice(-20~19)

    2,将根据每个任务的nice值确定在cpu上的执行时间(counter)

    3,如果没有等待资源,则将该任务加入到就绪队列中。

    4,调度程序遍历就绪队列中的任务,通过对每个任务动态优先级的计算权值(counter+20-nice)结果,选择计算结果最大的一个去运行,当这个时间片用完后(counter减至0)或者主动放弃cpu时,该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。

    5,此时调度程序重复上面计算过程,转到第4步。

    6,当调度程序发现所有就绪任务计算所得的权值都为不大于0时,重复第2步。

     

    所有任务都采用FIFO时:

    1,创建进程时指定采用FIFO,并设置实时优先级rt_priority(1-99)

    2,如果没有等待资源,则将该任务加入到就绪队列中。

    3,调度程序遍历就绪队列,根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu,该FIFO任务将一直占有cpu直到有优先级更高的任务就绪(即使优先级相同也不行)或者主动放弃(等待资源)

    4,调度程序发现有优先级更高的任务到达(高优先级任务可能被中断或定时器任务唤醒,再或被当前运行的任务唤醒,等等),则调度程序立即在当前任务堆栈中保存当前cpu寄存器的所有数据,重新从高优先级任务的堆栈中加载寄存器数据到cpu,此时高优先级的任务开始运行。重复第3步。

    5,如果当前任务因等待资源而主动放弃cpu使用权,则该任务将从就绪队列中删除,加入等待队列,此时重复第3步。

     

    所有任务都采用RR调度策略时:

    1,创建任务时指定调度参数为RR,并设置任务的实时优先级和nice(nice值将会转换为该任务的时间片的长度)

    2,如果没有等待资源,则将该任务加入到就绪队列中。

    3,调度程序遍历就绪队列,根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu

    4,如果就绪队列中的RR任务时间片为0,则会根据nice值设置该任务的时间片,同时将该任务放入就绪队列的末尾。重复步骤3

    5,当前任务由于等待资源而主动退出cpu,则其加入等待队列中。重复步骤3

     

    系统中既有分时调度,又有时间片轮转调度和先进先出调度: 

    1RR调度和FIFO调度的进程属于实时进程,以分时调度的进程是非实时进程。

    2,当实时进程准备就绪后,如果当前cpu正在运行非实时进程,则实时进程立即抢占非实时进程。

    3RR进程和FIFO进程都采用实时优先级做为调度的权值标准,RRFIFO的一个延伸。FIFO时,如果两个进程的优先级一样,则这两个优先级一样的进程具体执行哪一个是由其在队列中的未知决定的,这样导致一些不公正性(优先级是一样的,为什么要让你一直运行?),如果将两个优先级一样的任务的调度策略都设为RR,则保证了这两个任务可以循环执行,保证了公平。

     

    Ingo Molnar-实时补丁

    为了能并入主流内核,Ingo Molnar的实时补丁也采用了非常灵活的策略,它支持四种抢占模式:
    1.No Forced Preemption (Server),这种模式等同于没有使能抢占选项的标准内核,主要适用于科学计算等服务器环境。
    2.Voluntary Kernel Preemption (Desktop),这种模式使能了自愿抢占,但仍然失效抢占内核选项,它通过增加抢占点缩减了抢占延迟,因此适用于一些需要较好的响应性的环境,如桌面环境,当然这种好的响应性是以牺牲一些吞吐率为代价的。
    3.Preemptible Kernel (Low-Latency Desktop),这种模式既包含了自愿抢占,又使能了可抢占内核选项,因此有很好的响应延迟,实际上在一定程度上已经达到了软实时性。它主要适用于桌面和一些嵌入式系统,但是吞吐率比模式2更低。
    4.Complete Preemption (Real-Time),这种模式使能了所有实时功能,因此完全能够满足软实时需求,它适用于延迟要求为100微秒或稍低的实时系统。
     
    实现实时是以牺牲系统的吞吐率为代价的,因此实时性越好,系统吞吐率就越低。
    展开全文
  • linux内核分析——CFS(完全公平调度算法) 1.1&amp;nbsp;CFS原理 &amp;nbsp;&amp;nbsp;&amp;nbsp;&amp;nbsp;cfs定义了一种新的模型,它给cfs_rq(cfs的run&amp;nbsp;queue)中...

    linux内核分析——CFS(完全公平调度算法)

    1.1 CFS原理

        cfs定义了一种新的模型,它给cfs_rq(cfs的run queue)中的每一个进程安排一个虚拟时钟,vruntime。如果一个进程得以执行,随着时间的增长(也就是一个个tick的到来),其vruntime将不断增大。没有得到执行的进程vruntime不变。
        而调度器总是选择vruntime跑得最慢的那个进程来执行。这就是所谓的“完全公平”。为了区别不同优先级的进程,优先级高的进程vruntime增长得慢,以至于它可能得到更多的运行机会。

    1.2 CFS基本设计思路

    CFS思路很简单,就是根据各个进程的权重分配运行时间(权重怎么来的后面再说)。
    进程的运行时间计算公式为:
    分配给进程的运行时间 = 调度周期 * 进程权重 / 所有进程权重之和   (公式1)
        调度周期很好理解,就是将所有处于TASK_RUNNING态进程都调度一遍的时间,差不多相当于O(1)调度算法中运行队列和过期队列切换一次的时间(对O(1)调度算法看得不是很熟,如有错误还望各位大虾指出)。举个例子,比如只有两个进程A, B,权重分别为1和2,调度周期设为30ms,那么分配给A的CPU时间为:30ms * (1/(1+2)) = 10ms而B的CPU时间为30ms * (2/(1+2)) = 20ms那么在这30ms中A将运行10ms,B将运行20ms。
        公平怎么体现呢?它们的运行时间并不一样阿?
    其实公平是体现在另外一个量上面,叫做virtual runtime(vruntime),它记录着进程已经运行的时间,但是并不是直接记录,而是要根据进程的权重将运行时间放大或者缩小一个比例
    我们来看下从实际运行时间到vruntime的换算公式
    vruntime = 实际运行时间 * 1024 / 进程权重 。 (公式2)
        为了不把大家搞晕,这里我直接写1024,实际上它等于nice为0的进程的权重,代码中是NICE_0_LOAD。也就是说,所有进程都以nice为0的进程的权重1024作为基准,计算自己的vruntime增加速度。还以上面AB两个进程为例,B的权重是A的2倍,那么B的vruntime增加速度只有A的一半。现在我们把公式2中的实际运行时间用公式1来替换,可以得到这么一个结果:
    vruntime = (调度周期 * 进程权重 / 所有进程总权重) * 1024 / 进程权重 = 调度周期 * 1024 / 所有进程总权重 
    看出什么眉目没有?没错,虽然进程的权重不同,但是它们的 vruntime增长速度应该是一样的 ,与权重无关。好,既然所有进程的vruntime增长速度宏观上看应该是同时推进的,
    那么就可以用这个vruntime来选择运行的进程,谁的vruntime值较小就说明它以前占用cpu的时间较短,受到了“不公平”对待,因此下一个运行进程就是它。这样既能公平选择进程,又能保证高优先级进程获得较多的运行时间。这就是CFS的主要思想了。

    或者可以这么理解:CFS的思想就是让每个调度实体(没有组调度的情形下就是进程,以后就说进程了)的vruntime互相追赶,而每个调度实体的vruntime增加速度不同,权重越大的增加的越慢,这样就能获得更多的cpu执行时间。

        再补充一下权重的来源,权重跟进程nice值之间有一一对应的关系,可以通过全局数组prio_to_weight来转换,nice值越大,权重越低

    1.3 CFS数据结构

    介绍代码之前先介绍一下CFS相关的结构
    第一个是调度实体sched_entity,它代表一个调度单位,在组调度关闭的时候可以把他等同为进程。每一个task_struct中都有一个sched_entity,进程的vruntime和权重都保存在这个结构中。那么所有的sched_entity怎么组织在一起呢?红黑树。所有的sched_entity以vruntime为key(实际上是以vruntime-min_vruntime为key,是为了防止溢出反正结果是一样的)插入到红黑树中,同时缓存树的最左侧节点,也就是vruntime最小的节点,这样可以迅速选中vruntime最小的进程。
        注意只有等待CPU的就绪态进程在这棵树上,睡眠进程和正在运行的进程都不在树上。

     

    \

     

     

    1.4 Vruntime溢出问题

        之前说过红黑树中实际的作为key的不是vruntime而是vruntime-min_vruntimemin_vruntime是当前红黑树中最小的key。这是为什么呢,我们先看看vruntime的类型,是usigned long类型的,再看看key的类型,是signed long类型的,因为进程的虚拟时间是一个递增的正值,因此它不会是负数,但是它有它的上限,就是unsigned long所能表示的最大值,如果溢出了,那么它就会从0开始回滚,如果这样的话,结果会怎样?结果很严重啊,就是说会本末倒置的,比如以下例子,以unsigned char说明问题:

    unsigned char a = 251,b = 254;

    b += 5;//到此判断a和b的大小

    看看上面的例子,b回滚了,导致a远远大于b,其实真正的结果应该是b比a大8,怎么做到真正的结果呢?改为以下:

    unsigned char a = 251,b = 254;

    b += 5;

    signed char c = a - 250,d = b - 250;//到此判断c和d的大小

    结果正确了,要的就是这个效果,可是进程的vruntime怎么用unsigned long类型而不处理溢出问题呢?因为这个vruntime的作用就是推进虚拟时钟,并没有别的用处,它可以不在乎,然而在计算红黑树的key的时候就不能不在乎了,于是减去一个最小的vruntime将所有进程的key围绕在最小vruntime的周围,这样更加容易追踪。运行队列的min_vruntime的作用就是处理溢出问题的

     

    1.5 组调度

        关于组调度,详见:《linux组调度浅析 》。简单来说,引入组调度是为了实现做一件事的一组进程与做另一件事的另一组进程的隔离。每件“事情”各自有自己的权重,而不管它需要使用多少进程来完成。在cfs中,task_group和进程是同等对待的,task_group的优先级也由用户来控制(通过cgroup文件cpu.shares)。
    实现上,task_group和进程都被抽象成schedule_entity(调度实体,以下简称se),上面说到的vruntime、load、等这些东西都被封装在se里面。而task_group除了有se之外,还有cfs_rq。属于这个task_group的进程就被装在它的cfs_rq中(“组”不仅是一个被调度的实体,也是一个容器)。组调度引入以后,一系列task_group的cfs_rq组成了一个树型结构。树根是cpu所对应的cfs_rq(也就是root group的cfs_rq)、树的中间节点是各个task_group的cfs_rq、叶子节点是各个进程。
    在一个task_group的两头,是两个不同的世界,就像《盗梦空间》里不同层次的梦境一样。
    \

    以group-1为例,它所对应的se被加入到父组(cpu_rq)的cfs_rq中,接受调度。这个se有自己的load(由对应的cpu.shares文件来配置),不管group-1下面有多少个进程,这个load都是这个值。父组看不到、也不关心group-1下的进程。父组只会根据这个se的load和它执行的时间来更新其vruntime。当group-1被调度器选中后,会继续选择其下面的task-11或task-12来执行。这里又是一套独立的体系,task-11与task-12的vruntime、load、等这些东西只影响它们在group-1的cfs_rq中的调度情况。树型结构中的每一个cfs_rq都是独立完成自己的调度逻辑。不过,从cpu配额上看,task_group的配额会被其子孙层层瓜分。
        例如上图中的task-11,它所在的group-1对应se的load是8,而group-1下两个进程的load是9和3,task-11占其中的3/4。于是,在group-1所对应的cfs_rq内部看,task-11的load是9,而从全局来看,task-11的load是8*3/4=6。而task_group下的进程的时间片也是这样层层瓜分而来的,比如说group-1的cfs_rq下只有两个进程,计算得来的调度延迟是20ms。但是task-11并非占其中的3/4(15ms)。因为group-1的se的load占总额的8/(8+3+5)=1/2,所以task-11的load占总额的1/2*3/4=3/8,时间片是20ms*3/8=7.5ms。
    这样的瓜分有可能使得task_group里面的进程分得很小的时间片,从而导致频繁re-schedule。不过好在这并不影响task_group外面的其他进程,并且也可以尽量让task_group里面的进程在每个调度延迟内都执行一次。
        cfs曾经有过时间片不层层瓜分的实现,比如上图中的task-11,时间片算出来是15ms就是15ms,不用再瓜分了。这样做的好处是不会有频繁的re-schedule。但是task_group里的进程可能会很久才被执行一次。瓜分与不瓜分两种方案的示例如下(还是继续上图的例子,深蓝色代表task-11、浅蓝色是task-12,空白是其他进程):
    \
         两种方案好像很难说清孰优孰劣,貌似cfs也在这两种方案间纠结了好几次。
    在进程用完其时间片之前,有可能它所在的task_group的se先用完了时间片,而被其父组re-schedule掉。这种情况下,当这个task_group的se再一次被其父组选中时,上次得到执行、且尚未用完时间片的那个进程将继续运行,直到它用完时间片。(cfs_rq->last会记录下这个尚未用完时间片的进程。)

    1.6 CFS小结

        CFS还有一个重要特点,即调度粒度小。CFS之前的调度器中,除了进程调用了某些阻塞函数而主动参与调度之外,每个进程都只有在用完了时间片或者属于自己的时间配额之后才被抢占。而CFS则在每次tick都进行检查,如果当前进程不再处于红黑树的左边,就被抢占。在高负载的服务器上,通过调整调度粒度能够获得更好的调度性能。

     

    文章出处: https://www.cnblogs.com/tianguiyu/articles/6091378.html

    展开全文
  • linux内核调度机制

    千次阅读 2018-04-26 15:33:30
    linux内核调度机制linux内核调度机制抢占式内核与非抢占式内核linux抢占式内核与实时系统的关系一个好的系统的进程调度机制,要兼顾三种不同的应用的需求: 1交互式应用。这种应用,着重于系统的响应速度,当...
  • linux内核调度详解

    千次阅读 2018-06-20 15:03:44
    本文档基于Linux3.141、 概述
  • 内核在微观上,把CPU的运行时间分成许多分,然后安排给各个进程轮流运行,造成宏观上所有的进程仿佛同时在执行。双核CPU,实际上最多只能有两个进程在同时运行,大家在top、vmstat命令里看到的正在运行的进程,并不...
  • linux内核调度算法(3)--多核系统的负载均衡 原文:http://blog.csdn.net/russell_tao/article/details/7102297 作者:陶辉  多核CPU现在很常见,那么问题来了,一个程序在运行时,只在一个CPU核上运行?还是...
  • linux内核调度算法(1)--快速找到最高优先级进程 分类: 技术分享 linux 为什么要了解内核的调度策略呢?呵呵,因为它值得我们学习,不算是废话吧。内核调度程序很先进很强大,管理你的LINUX上跑的...
  • Molnar,Ingo Molnar本人也是linux内核调度模块的负责人。 但在CFS调度算法引入之前,linux使用的调度器也是由Ingo Molnar写的复杂度为O(1)的另一种调度算法,据说是Ingo Molnar为了解决JVM虚拟机
  • LINUX内核调度原理

    2020-07-30 23:32:59
    这是 LINUX 内核调度 的基本原理和算法 理解内核调度 可以好好看设备驱动了
  • Linux 调度器 - Volker Seeker · 爱丁堡大学 2013.05.12本文档包含了Linux内核如何处理进程调度注意事项。 它们涵盖一般调度器框架、调度类、完全公平调度(CFS)算法、软实时调度以及负载均衡的实时和CFS。 在此...
  • linux内核中提供了两种实时调度策略:SCHED_FIFO和SCHED_RR,其中RR是带有时间片的FIFO。这两种调度算法实现的都是静态优先级。内核不为实时进程计算动态优先级。这能保证给定优先级别的实时进程总能抢占优先级比他...
  • Linux调度时机主要有: 1、进程状态转换的时刻:进程终止、进程睡眠; 2、当前进程的时间片用完时(current->counter=0); 3、设备驱动程序主动调用schedule; 4、进程从中断、异常及系统调用返回到用户态时; ...
  • Linux 内核包含4个IO调度器,分别是 Noop IO scheduler、Anticipatory IO scheduler、Deadline IO ...通常磁盘的读写影响是由磁头到柱面移动造成了延迟,解决这种延迟内核主要采用两种策略:缓存和IO调度算法来进行...
  • linux内核编程4部曲之三:修改O(1)调度算法 linux内核编程4部曲之四:模块编程   一、实验目的  修改O(1)调度程序,使交互性非常强的程序(IO密集型)在时间片用完后,不放置到活动数组,而放入过期数组(与...
  • Linux进程调度算法分析

    千次阅读 2012-10-09 14:36:43
    Linux进程调度算法分析 摘要 :基于X86平台Linux2.6.26内核进程调度部分代码,刨析Linux进程调度算法,对算法的原理,实现和复杂度进行了分析并提出了算法改进措施。 关键字:Linux内核 进程调度 算法   1. ...
  • linux进程调度算法

    2018-10-28 15:51:00
    一:什么是进程调度 ...二:在linux操作系统中都有哪些进程调度算法  1. 先进先出算法(FIFO):  按照进程进入就绪队列的先后次序来选择。即每当进入进程调度,总是把就绪队列的队首进程投入运行。  ...
1 2 3 4 5 ... 20
收藏数 38,805
精华内容 15,522
关键字:

linux 内核调度算法