Linux内核分析之调度算法


linux调度算法在2.6.32中采用调度类实现模块式的调度方式。这样，能够很好的加入新的调度算法。

linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类，他允许多种不同哦可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，调度代码会按照优先级遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那个程序。

linux上主要有两大类调度算法，CFS(完全公平调度算法）和实时调度算法。宏SCHED_NOMAL主要用于CFS调度，而SCHED_FIFO和SCHED_RR主要用于实时调度。如下面的宏定义：

  1. /* 
  2.  * Scheduling policies 
  3.  */  
  4.  /*支援Real-Time Task的排程,包括有SCHED_FIFO與SCHED_RR.  
  5.  */  
  6.    
  7.  /*(也稱為SCHED_OTHER): 主要用以排程 
  8.  一般目的的Task.*/  
  9. #define SCHED_NORMAL        0   
  10. #define SCHED_FIFO      1   
  11. /*task預設的 Time Slice長度為100 msecs*/  
  12. #define SCHED_RR        2   
  13. /*主要用以讓Task可以延長執行的時間 
  14. (Time Slice),減少被中斷發生Task Context-Switch 
  15. 的次數.藉此可以提高 Cache的利用率  
  16. (每次Context-Switch都會導致Cache-Flush). 比 
  17. 較適合用在固定週期執行的Batch Jobs任 
  18. 務主機上,而不適合用在需要使用者互 
  19. 動的產品 (會由於Task切換的延遲,而 
  20. 感覺到系統效能不佳或是反應太慢).*/  
  21. #define SCHED_BATCH     3   
  22. /* SCHED_ISO: reserved but not implemented yet */  
  23. /*為系統中的Idle Task排程.*/  
  24. #define SCHED_IDLE      5  

linux调度算法实现的高层数据结构主要有运行实体、调度类、运行队列，下面我们主要看看这几个数据结构的字段和意义。

运行实体，rq结构体每个cpu有一个，主要存储一些基本的用于调度的信息，包括实时调度的和CFS调度的

  1.  /*每个处理器都会配置一个rq*/  
  2. struct rq {  
  3.     /* runqueue lock: */  
  4.     spinlock_t lock;  
  5.   
  6.     /* 
  7.      * nr_running and cpu_load should be in the same cacheline because 
  8.      * remote CPUs use both these fields when doing load calculation. 
  9.      */  
  10.      /*用以记录目前处理器rq中执行task的数量*/  
  11.     unsigned long nr_running;  
  12.     #define CPU_LOAD_IDX_MAX 5   
  13.     /*用以表示处理器的负载，在每个处理器的rq中 
  14.     都会有对应到该处理器的cpu_load参数配置，在每次 
  15.     处理器触发scheduler tick时，都会呼叫函数 
  16.     update_cpu_load_active,进行cpu_load的更新。在系统初始化的时候 
  17.     会呼叫函数sched_init把rq的cpu_load array初始化为0. 
  18.     了解他的更新方式最好的方式是通过函数update_cpu_load,公式如下澹? 
  19.     cpu_load[0]会直接等待rq中load.weight的值。 
  20.     cpu_load[1]=(cpu_load[1]*(2-1)+cpu_load[0])/2 
  21.     cpu_load[2]=(cpu_load[2]*(4-1)+cpu_load[0])/4 
  22.     cpu_load[3]=(cpu_load[3]*(8-1)+cpu_load[0])/8 
  23.     cpu_load[4]=(cpu_load[4]*(16-1)+cpu_load[0]/16 
  24.     呼叫函数this_cpu_load时，所返回的cpu load值是cpu_load[0] 
  25.     而在进行cpu blance或migration时，就会呼叫函数 
  26.     source_load target_load取得对该处理器cpu_load index值， 
  27.     来进行计算*/  
  28.     unsigned long cpu_load[CPU_LOAD_IDX_MAX];  
  29. #ifdef CONFIG_NO_HZ   
  30.     unsigned long last_tick_seen;  
  31.     unsigned char in_nohz_recently;  
  32. #endif   
  33.     /* capture load from *all* tasks on this cpu: */  
  34.     /*load->weight值，会是目前所执行的schedule entity的 
  35.     load->weight的总和，也就是说rq的load->weight越高， 
  36.     也表示所负责的排程单元load->weight总和越高 
  37.     表示处理器所负荷的执行单元也越重*/  
  38.     struct load_weight load;  
  39.     /*在每次scheduler tick中呼叫update_cpu_load时， 
  40.     这个值就增加一，可以用来反馈目前cpu 
  41.     load更新的次数*/  
  42.     unsigned long nr_load_updates;  
  43.     /*用来累加处理器进行context switch的次数，会在 
  44.     函数schedule呼叫时进行累加，并可以通过函数 
  45.     nr_context_switches统计目前所有处理器总共的context switch 
  46.     次数，或是可以透过查看档案/proc/stat中的ctxt位得知目前 
  47.     整个系统触发context switch的次数*/  
  48.     u64 nr_switches;  
  49.       
  50.     u64 nr_migrations_in;  
  51.     /*为cfs fair scheduling class 的rq*/  
  52.     struct cfs_rq cfs;  
  53.     /*为real-time scheduling class 的rq*/  
  54.     struct rt_rq rt;  
  55.       
  56. /*用以支援可以group cfs tasks的机制*/  
  57. #ifdef CONFIG_FAIR_GROUP_SCHED   
  58.     /* list of leaf cfs_rq on this cpu: */  
  59.     /*在有设置fair group scheduling 的环境下， 
  60.     会基于原本cfs rq中包含有若干task的group 
  61.     所成的排程集合，也就是说当有一个group a 
  62.     就会有自己的cfs rq用来排程自己所属的tasks, 
  63.     而属于这group a的tasks所使用到的处理器时间 
  64.     就会以这group a总共所分的的时间为上限。 
  65.     基于cgroup的fair group scheduling 架构，可以创造出 
  66.     有阶层性的task组织，根据不同task的功能群组化 
  67.     在配置给该群主对应的处理器资源，让属于 
  68.     该群主下的task可以透过rq机制排程。使用属于 
  69.     该群主下的资源。 
  70.     这个变数主要是管理CFS RQ list，操作上可以透过函数 
  71.     list_add_leaf_cfs_rq把一个group cfs rq加入到list中，或透过 
  72.     函数list_del_leaf_cfs_rq把一个group cfs rq移除，并可以 
  73.     透过for_each_leaf_cfs_rq把一个rq上得所有leaf cfs_rq走一遍 
  74.     */  
  75.     struct list_head leaf_cfs_rq_list;  
  76. #endif   
  77. /*用以支援可以group real-time tasks的机制*/  
  78. #ifdef CONFIG_RT_GROUP_SCHED   
  79.     /*类似leaf_cfs_rq_list所扮演的角色，只是这里 
  80.     是针对属于real-time的task,在实际操作上可以 
  81.     透过函数list_add_leaf_rt_rq,list_del_leaf_rt_rq或 
  82.     巨集for_each_leaf_rt_rq*/  
  83.     struct list_head leaf_rt_rq_list;  
  84. #endif   
  85.   
  86.     /* 
  87.      * This is part of a global counter where only the total sum 
  88.      * over all CPUs matters. A task can increase this counter on 
  89.      * one CPU and if it got migrated afterwards it may decrease 
  90.      * it on another CPU. Always updated under the runqueue lock: 
  91.      */  
  92.      /*一般来说，linux kernel 的task状态可以为TASK_RUNNING 
  93.      TASK_INTERRUPTIBLE(sleep), 
  94.      TASK_UNINTERRUPTIBLE(Deactivate Task,此时Task会从rq中 
  95.      移除)或TASK_STOPPED. 
  96.      透过这个变数会统计目前rq中有多少task属于 
  97.      TASK_UNINTERRUPTIBLE的状态。当呼叫函数 
  98.      active_task时，会把nr_uninterruptible值减一，并透过 该函数 
  99.     enqueue_task把对应的task依据所在的scheduling class 
  100.     放在 对应的rq中，并把目前rq中nr_running值加一*/  
  101.     unsigned long nr_uninterruptible;  
  102.     /*curr:指向目前处理器正在执行的task; 
  103.     idle:指向属于idle-task scheduling class 的idle task; 
  104.     stop:指向目前最高等级属于stop-task scheduling class 
  105.     的task;*/  
  106.     struct task_struct *curr, *idle;  
  107.     /*基于处理器的jiffies值，用以记录下次进行处理器 
  108.     balancing 的时间点*/  
  109.     unsigned long next_balance;  
  110.     /*用以存储context-switch发生时，前一个task的memory management 
  111.     结构并可用在函数finish_task_switch中，透过函数mmdrop释放前一个 
  112.     task的记忆体资源*/      
  113.     struct mm_struct *prev_mm;  
  114.     /*用以记录目前rq的clock值，基本上该值会等于透过sched_clock_cpu 
  115.     (cpu_of(rq))的回传值，并会在每次呼叫scheduler_tick时透过 
  116.     函数update_rq_clock更新目前rq clock值。 
  117.     在实作部分，函数sched_clock_cpu会透过sched_clock_local或 
  118.     ched_clock_remote取得对应的sched_clock_data,而处理的sched_clock_data 
  119.     值，会透过函数sched_clock_tick在每次呼叫scheduler_tick时进行更新； 
  120.     */  
  121.     u64 clock;  
  122.     /*用以记录目前rq中有多少task处于等待i/o的sleep状态 
  123.     在实际的使用上，例如当driver接受来自task的调用，但处于等待i/o 
  124.     回复的阶段时，为了充分利用处理器的执行资源，这时 
  125.     就可以在driver中呼叫函数io_schedule，此时 
  126.     就会把目前rq中的nr_iowait加一，并设定目前task的io_wait为1 
  127.     然后触发scheduling 让其他task有机会可以得到处理器执行时间*/  
  128.     atomic_t nr_iowait;  
  129.   
  130. #ifdef CONFIG_SMP   
  131.     /*root domain是基于多核心架构下的机制， 
  132.     会由rq结构记住目前采用的root domain，其中包括了 
  133.     目前的cpu mask(包括span,online rt overload), reference count 跟cpupri 
  134.     当root domain有被rq参考到时，refcount 就加一，反之就减一。而cpu 
  135.     mask span表示rq可挂上的cpu mask,noline为rq目前已经排程的 
  136.     cpu mask cpu上执行real-time task.可以参考函数pull_rt_task，当一个rq中属于 
  137.     real-time的task已经执行完毕，就会透过函数pull_rt_task从该 
  138.     rq中属于rto_mask cpu mask 可以执行的处理器上，找出是否有一个处理器 
  139.     有大于一个以上的real-time task，若有就会转到目前这个执行完成 
  140.     real-time task 的处理器上 
  141.     而cpupri不同于Task本身有区分140個(0-139) 
  142.     Task Priority (0-99為RT Priority 而 100-139為Nice值 -20-19).  
  143.     CPU Priority本身有102個Priority (包括,-1 為Invalid, 
  144.     0為Idle,1為Normal,2-101對應到Real-Time Priority 0-99). 
  145.     參考函式convert_prio, Task Priority如果是 140就會對應到 
  146.     CPU Idle,如果是大於等於100就會對應到CPU Normal, 
  147.     若是Task Priority介於0-99之間,就會對應到CPU Real-Time Priority 101-2之間.)  
  148.     在實際的操作上,例如可以透過函式cpupri_find 
  149.     帶入一個要插入的Real-Time Task,此時就會依據cpupri中 
  150.     pri_to_cpu選擇一個目前執行Real-Time Task且該Task 
  151.     的優先級比目前要插入的Task更低的處理器, 
  152.     並透過CPU Mask(lowest_mask)返回目前可以選擇的處理器Mask. 
  153.     實作的部份可以參考檔案kernel/sched_cpupri.c. 
  154.     在初始化的過程中,會透過函式sched_init呼叫函式init_defrootdomain, 
  155.     對Root Domain與 CPU Priority機制進行初始化. 
  156.     */  
  157.     struct root_domain *rd;  
  158.     /*Schedule Domain是基於多核心架構下的機制. 
  159.     每個處理器都會有一個基礎的Scheduling Domain, 
  160.     Scheduling Domain可以有階層性的架構,透過parent 
  161.     可以找到上一層的Domain,或是透過child找到 
  162.     下一層的 Domain (NULL表示結尾.).並可透過span 
  163.     栏位,表示這個Domain所能涵蓋的處理器範圍. 
  164.     通常Base Domain會涵蓋系統中所有處理器的個數, 
  165.     而Child Domain所能涵蓋的處理器個數不超過它的 
  166.     Parent Domain. 而當在進行Scheduling Domain 中的Task Balance 
  167.     時,就會以該Domain所能涵蓋的處理器為最大範圍. 
  168.     同時,每個Schedule Domain都會包括一個或一個以上的 
  169.     CPU Groups (結構為struct sched_group),並透過next變數把 
  170.     CPU Groups串連在一起(成為一個單向的Circular linked list), 
  171.     每個CPU Group都會有變數cpumask來定义這個CPU Group 
  172.     所涵蓋的處理器範圍.並且CPU Group所包括的處理器 
  173.     範圍,必需涵蓋在所屬的Schedule Domain處理器範圍中. 
  174.     當進行Scheduling Domain的Balancing時,會以其下的CPU Groups 
  175.     為單位,根據cpu_power （會是該Group所涵蓋的處理器 
  176.     Tasks Loading的總和）來比較不同的CPU Groups的負荷, 
  177.     以進行Tasks的移動,達到Balancing的目的. 
  178.     在有支援SMP的架構下,會在函式sched_init中,呼叫open_softirq, 
  179.     註冊 SCHED_SOFTIRQ Software IRQ与其对应的 Callback函式  
  180.     run_rebalance_domains. 並會在每次呼叫函式scheduler_tick時, 
  181.     透過函式trigger_load_balance确认是否目前的jiffies值已經 
  182.     大於RunQueue下一次要觸發Load Balance的next_balance時間值, 
  183.     並透過函式raise_softirq觸發SCHED_SOFTIRQ Software IRQ.  
  184.     在Software IRQ觸發後,就會呼叫函式run_rebalance_domains, 
  185.     並在函式rebalance_domains中,進行后续處理器上的 
  186.     Scheduling Domain Load Balance動作. 
  187.     有關Scheduling Domain進一步的內容,也可以參考 
  188.     Linux Kernel文件 Documentation/scheduler/sched-domains.txt. 
  189.     */  
  190.     struct sched_domain *sd;  
  191.     /*這值會等於函式idle_cpu的返回值,如果為1表示 
  192.     目前CPU RunQueue中執行的為Idle Task. 反之為0, 
  193.     則表示處理器執行的不是Idle Task (也就是說 
  194.     處理器正在忙碌中.).*/  
  195.     unsigned char idle_at_tick;  
  196.     /* For active balancing */  
  197.     /*若這值不為0,表示會有在Schedule排程動作 
  198.     結束前,要呼叫的收尾函式. (实作為inline函式 
  199.     post_schedule in kernel/sched.c),目前只有Real-Time Scheduling  
  200.     Class有支援這個機制(會呼叫函式has_pushable_tasks  
  201.     in kernel/sched_rt.c).*/  
  202.     int post_schedule;  
  203.     /*當RunQueue中此值為1,表示這個RunQueue正在進行 
  204.     Fair Scheduling的Load Balance,此時會呼叫stop_one_cpu_nowait 
  205.     暫停該RunQueue所屬處理器的排程,並透過函式 
  206.     active_load_balance_cpu_stop,把Tasks從最忙碌的處理器, 
  207.     移到Idle的處理器上執行.*/  
  208.     int active_balance;  
  209.     /*用以儲存目前進入Idle且負責進行 Load Balance 
  210.     流程的處理器ID. 呼叫的流程為,在呼叫函式schedule時, 
  211.     若該處理器RunQueue的nr_running為0 (也就是目前沒有 
  212.     正在執行的Task),就會呼叫idle_balance,並觸發後續Load  
  213.     Balance流程.*/  
  214.     int push_cpu;  
  215.     /* cpu of this runqueue: */  
  216.     /*用以儲存目前运作這個RunQueue的處理器ID*/  
  217.     int cpu;  
  218.     /*為1表示目前此RunQueue有在對應的處理器掛上 
  219.     並執行.*/  
  220.     int online;  
  221.     /*如果RunQueue中目前有Task正在執行,這個值會 
  222.     等於目前該RunQueue的Load Weight除以目前RunQueue 
  223.     中Task數目的均值.  
  224.     (rq->avg_load_per_task = rq->load.weight / nr_running;).*/  
  225.     unsigned long avg_load_per_task;  
  226.   
  227.     struct task_struct *migration_thread;  
  228.     struct list_head migration_queue;  
  229.     /*這個值會由Real-Time Scheduling Class呼叫函式 
  230.     update_curr_rt,用以統計目前Real-Time Task執行時間的 
  231.     均值,在這函式中會以目前RunQueue的clock_task 
  232.     減去目前Task執行的起始時間,取得執行時間的 
  233.     Delta值. (delta_exec = rq->clock_task – curr->se.exec_start; ). 
  234.     在透過函式sched_rt_avg_update把這Delta值跟原本 
  235.     RunQueue中的rt_avg值取平均值. 以運作的週期來看, 
  236.     這個值可反應目前系統中Real-Time Task平均被 
  237.     分配到的執行時間值.*/  
  238.     u64 rt_avg;  
  239.     /*這個值主要在函式sched_avg_update更新,以笔者手中 
  240.     的Linux Kernel 2.6.38.6的實作來說,當RunQueue Clock 
  241.     減去age_stamp大於 0.5秒 (=sched_avg_period),就會把這值 
  242.     累加0.5秒 (單位都是nanoseconds). 從函式scale_rt_power 
  243.     的實作來說,age_stamp值離RunQueue Clock越遠,表示total 
  244.     值越大,available值也越大,而函式scale_rt_power返回的 
  245.     div_u64計算結果也越大,最終 RunQueue的cpu_power 
  246.     與Scheduling Domain中的Scheduling Group的cpu_power 
  247.     值也就越大. (可參考函式update_cpu_power的實作).*/  
  248.     u64 age_stamp;  
  249.     /*這值會在觸發Scheduling時,若判斷目前處理器 
  250.     RunQueue沒有正在運作的Task,就會透過函式 
  251.     idle_balance更新這值為為目前RunQueue的clock值. 
  252.     可用以表示這個處理器是何時進入到Idle的 
  253.     狀態*/  
  254.     u64 idle_stamp;  
  255.     /*會在有Task運作且idle_stamp不為0 (表示前一個 
  256.     狀態是在Idle)時以目前RunQueue的clock減去 
  257.     idle_stmp所計算出的Delta值為依據,更新這個值 
  258.     . 可反應目前處理器進入Idle狀態的時間長短*/  
  259.     u64 avg_idle;  
  260. #endif   
  261.   
  262.     /* calc_load related fields */  
  263.     /*用以記錄下一次計算CPU Load的時間,初始值 
  264.     為目前的jiffies加上五秒與1次的Scheduling Tick的 
  265.     間隔 (=jiffies + LOAD_FREQ,且LOAD_FREQ=(5*HZ+1))*/  
  266.     unsigned long calc_load_update;  
  267.     /*會等於RunQueue中nr_running與nr_uninterruptible的 
  268.     總和.（可參考函式calc_load_fold_active）.*/  
  269.     long calc_load_active;  
  270.   
  271. #ifdef CONFIG_SCHED_HRTICK   
  272. #ifdef CONFIG_SMP   
  273.     /*在函式init_rq_hrtick初始化RunQueue High-Resolution  
  274.     Tick時,此值預設為0. 
  275.     在函式hrtick_start中,會判斷目前觸發的RunQueue 
  276.     跟目前處理器所使用的RunQueue是否一致, 
  277.     若是,就直接呼叫函式hrtimer_restart,反之就會 
  278.     依據RunQueue中hrtick_csd_pending的值,如果 
  279.     hrtick_csd_pending為0,就會透過函式 
  280.     __smp_call_function_single讓RunQueue所在的另一個 
  281.     處理器執行rq->hrtick_csd.func 所指到的函式  
  282.     __hrtick_start. 並等待該處理器執行完畢後, 
  283.     才重新把hrtick_csd_pending設定為1. 
  284.     也就是說, RunQueue的hrtick_csd_pending是用來作為 
  285.     SMP架構下,由處理器A觸發處理器B執行 
  286.     _hrtick_start函式的一個保護機制.而有關在 
  287.     SMP下如何由一個處理器觸發另一個處理器 
  288.     執行函式的機制,可以參考kernel/smp.c中 
  289.     相關smp_call_function_xxxxxxx的實作.s*/  
  290.     int hrtick_csd_pending;  
  291.     /*用以儲存hrtick機制中,要跨處理器執行的 
  292.     函式結構.*/  
  293.     struct call_single_data hrtick_csd;  
  294. #endif   
  295.     /*為High-Resolution Tick的结构,會透過函式 
  296.     hrtimer_init初始化.*/  
  297.     struct hrtimer hrtick_timer;  
  298. #endif   
  299.   
  300. #ifdef CONFIG_SCHEDSTATS   
  301.     /* latency stats */  
  302.     /*為Scheduling Info.的統計結構,可以參考 
  303.     include/linux/sched.h中的宣告. 例如在每次觸發 
  304.     Schedule時,呼叫函式schedule_debug對上一個Task 
  305.     的lock_depth進行確認(Fork一個新的Process 時, 
  306.     會把此值預設為-1就是No-Lock,當呼叫 
  307.     Kernel Lock時, 就會把Current Task的lock_depth加一.), 
  308.     若lock_depth>=0,就會累加Scheduling Info.的bkl_count值, 
  309.     用以代表Task Blocking的次數.*/  
  310.     struct sched_info rq_sched_info;  
  311.     /*可用以表示RunQueue中的Task所得到CPU執行 
  312.     時間的累加值. 
  313.     在發生Task Switch時,會透過sched_info_switch呼叫 
  314.     sched_info_arrive並以目前RunQueue Clock值更新 
  315.     Task 的sched_info.last_arrival時間,而在Task所分配時間 
  316.     結束後,會在函式sched_info_depart中以現在的 
  317.     RunQueue Clock值減去Task的sched_info.last_arrival 
  318.     時間值,得到的 Delta作為變數rq_cpu_time的累 
  319.     加值.*/  
  320.     unsigned long long rq_cpu_time;  
  321.     /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */  
  322.   
  323.     /* sys_sched_yield() stats */  
  324.     /*用以統計呼叫System Call sys_sched_yield的次數.*/  
  325.     unsigned int yld_count;  
  326.   
  327.     /* schedule() stats */  
  328.     unsigned int sched_switch;  
  329.     /*可用以統計觸發Scheduling的次數. 在每次觸發 
  330.     Scheduling時,會透過函式schedule呼叫schedule_debug, 
  331.     呼叫schedstat_inc對這變數進行累加.*/  
  332.     unsigned int sched_count;  
  333.     /*可用以統計進入到Idle Task的次數. 會在函式 
  334.     pick_next_task_idle中,呼叫schedstat_inc對這變數進行 
  335.     累加.*/  
  336.     unsigned int sched_goidle;  
  337.   
  338.     /* try_to_wake_up() stats */  
  339.     /*用以統計Wake Up Task的次數.*/  
  340.     unsigned int ttwu_count;  
  341.     /*用以統計Wake Up 同一個處理器Task的次數.*/  
  342.     unsigned int ttwu_local;  
  343.   
  344.     /* BKL stats */  
  345.     unsigned int bkl_count;  
  346. #endif   
  347. };  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 下一页

相关内容