linux内核分析之调度算法

1、linux内核分析之调度算法linux调度算法在2.6.32中采用调度类实现模块式的调度方式。这样，能够很好的加入新的调度算法。linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类，他允许多种不同哦可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，调度代码会按照优先级遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那个程序。linux上主要有两大类调度算法，CFS（完全公平调度算法）和实时调度算法。宏SCHED_NOMAL主要用于CFS调度，而SCHED_FIFO和SC

2、HED_RR主要用于实时调度。如下面的宏定义：/*SchedulingpoliciesTOC o 1-5 h z*/*支援Real-TimeTask的排程，包括有SCHED_FIFO與SCHED_RR.*/6./*（也稱為SCHED_OTHER）:主要用以排程一般目的的Task.*/#defineSCHED_NORMAL0#defineSCHED_FIFO1/*task預設的TimeSlice長度為100msecs*/#defineSCHED_RR2/*主要用以讓Task可以延長執行的時間（TimeSlice）,減少被中斷發生TaskContext-Switch的次數.藉此可以提高Cache的

3、利用率（每次Context-Switch都會導致Cache-Flush）.比較適合用在固定週期執行的BatchJobs任務主機上,而不適合用在需要使用者互動的產品儈由於Task切換的延遲，而感覺到系統效能不佳或是反應太慢）.*/#defineSCHED_BATCH3/*SCHED_ISO:reservedbutnotimplementedyet*/*為系統中的IdleTask排程.*/#defineSCHED_IDLE5/*eliliies*/*支援Real-Time*/4Task的排程，包括linux调度算法实现的高层数据结构主要有运行实体、调度类、运行队列，下面我们主要看看这几个数据结构的

4、字段和意义。运行实体，rq结构体每个cpu有一个，主要存储一些基本的用于调度的信息，包括实时调度的和CFS调度的/*每个处理器都会配置一个rq*/structrq/*runqueuelock:*/spinlock_tlock;5./*nr_runningandcpu_loadshouldbeinthesamecachelinebecause*remoteCPUsuseboththesefieldswhendoingloadcalculation.*/*用以记录目前处理器rq中执行task的数量*/unsignedlongnr_running;#defineCPU_LOAD_IDX_MAX5/*

5、用以表示处理器的负载，在每个处理器的rq中都会有对应到该处理器的cpu_load参数配置，在每次处理器触发schedulertick时，都会呼叫函数update_cpuoad_active,进行cpu_load的更新。在系统初始化的时候会呼叫函数schednit把rq的cpuoadarray初始化为0.了解他的更新方式最好的方式是通过函数update_cpuoad,公式如下澹？cpuoad0会直接等待rq中load.weight的值。cpu_load1=(cpu_load1*(2-1)+cpu_load0)/2cpu_load2=(cpu_load2*(4-1)+cpu_load0)/4cpu

6、_load3=(cpu_load3*(8-1)+cpu_load0)/8cpu_load4=(cpu_load4*(16-1)+cpu_load0/16呼叫函数this_cpu_load时，所返回的cpuload值是cpu_load025.而在进行cpublance或migration时，就会呼叫函数26.source_loadtarget_load取得对该处理器cpu_loadindex值，27.来进行计算*/unsignedlongcpu_loadCPU_LOAD_IDX_MAX;#ifdefCONFIG_NO_HZunsignedlonglast_tick_seen;unsignedch

7、arin_nohz_recently;#endif/*captureloadfrom*all*tasksonthiscpu:*/*load-weight值，会是目前所执行的scheduleentity的load-weight的总和，也就是说rq的load-weight越高，也表示所负责的排程单元load-weight总和越高表示处理器所负荷的执行单元也越重*/structload_weightload;/*在每次schedulertick中呼叫update_cpu_load时，40.这个值就增加一，可以用来反馈目前cpuload更新的次数*/unsignedlongnr_load_update

8、s;43./*用来累加处理器进行contextswitch的次数，会在44.函数schedule呼叫时进行累加，并可以通过函数45.nr_context_switches统计目前所有处理器总共的contextswitch次数，或是可以透过查看档案/proc/stat中的ctxt位得知目前整个系统触发contextswitch的次数*/u64nr_switches;49.u64nr_migrations_in;/*为cfsfairschedulingclass的rq*/structcfs_rqcfs;/*为real-timeschedulingclass的rq*/structrt_rqrt;55

9、./*用以支援可以groupcfstasks的机制*/#ifdefCONFIG_FAIR_GROUP_SCHED/*listofleafcfs_rqonthiscpu:*/*在有设置fairgroupscheduling的环境下，60.会基于原本cfsrq中包含有若干task的group61.所成的排程集合，也就是说当有一个groupa62.就会有自己的cfsrq用来排程自己所属的tasks,63.而属于这groupa的tasks所使用到的处理器时间64.就会以这groupa总共所分的的时间为上限。65.基于cgroup的fairgroupscheduling架构，可以创造出有阶层性的task

10、组织，根据不同task的功能群组化在配置给该群主对应的处理器资源，让属于该群主下的task可以透过rq机制排程。使用属于该群主下的资源。这个变数主要是管理CFSRQlist，操作上可以透过函数Iist_addeaf_cfs_rq把一个groupcfsrq加入到list中，或透过函数list_del_leaf_cfs_rq把一个groupcfsrq移除，并可以透过for_each_leaf_cfs_rq把一个rq上得所有leafcfs_rq走一遍*/structlist_headleaf_cfs_rq_list;#endif/*用以支援可以groupreal-timetasks的机制*/#ifd

11、efCONFIG_RT_GROUP_SCHED/*类似leaf_cfs_rqist所扮演的角色，只是这里是针对属于real-time的task，在实际操作上可以透过函数list_add_leaf_rt_rq,list_del_leaf_rt_rq或巨集for_each_leaf_rt_rq*/structlist_headleaf_rt_rq_list;#endif85./*Thisispartofaglobalcounterwhereonlythetotalsum*overallCPUsmatters.Ataskcanincreasethiscounteron*oneCPUandifitgo

12、tmigratedafterwardsitmaydecrease*itonanotherCPU.Alwaysupdatedundertherunqueuelock:*/*一般来说，linuxkernel的task状态可以为TASK_RUNNINGTASK_INTERRUPTIBLE(sleep),TASK_UNINTERRUPTIBLE(DeactivateTask,此时Task会从rq中移除)或TASK_STOPPED.透过这个变数会统计目前rq中有多少task属于TASK_UNINTERRUPTIBLE的状态。当呼叫函数active_task时，会把nr_uninterruptible值减

13、一，并透过该函数enqueue_task把对应的task依据所在的schedulingclass放在对应的rq中，并把目前rq中nr_running值加一*/unsignedlongnr_uninterruptible;/*curr:指向目前处理器正在执行的task;idle:指向属于idle-taskschedulingclass的idletask;stop:指向目前最高等级属于stop-taskschedulingclass的task;*/structtask_struct*curr,*idle;/*基于处理器的jiffies值，用以记录下次进行处理器balancing的时间点*/unsi

14、gnedlongnext_balance;/*用以存储context-switch发生时，前一个task的memorymanagement结构并可用在函数finish_task_switch中，透过函数mmdrop释放前一个task的记忆体资源*/structmm_struct*prev_mm;/*用以记录目前rq的clock值，基本上该值会等于透过sched_clock_cpu(cpu_of(rq)的回传值，并会在每次呼叫scheduler_tick时透过函数update_rq_clock更新目前rqclock值。在实作部分，函数sched_clock_cpu会透过sched_clock_l

15、ocal或ched_clock_remote取得对应的sched_clock_data,而处理的sched_clock_data值，会透过函数sched_clock_tick在每次呼叫scheduler_tick时进行更新;*/u64clock;/*用以记录目前rq中有多少task处于等待i/o的sleep状态在实际的使用上，例如当driver接受来自task的调用，但处于等待i/o回复的阶段时，为了充分利用处理器的执行资源，这时就可以在driver中呼叫函数io_schedule，此时就会把目前rq中的nr_iowait加一，并设定目前task的io_wait为1然后触发scheduling

16、让其他task有机会可以得到处理器执行时间*/atomic_tnr_iowait;129.#ifdefCONFIG_SMP/*rootdomain是基于多核心架构下的机制，会由rq结构记住目前采用的rootdomain,其中包括了目前的cpumask(包括span,onlinertoverload),refereneecount跟cpupri当rootdomain有被rq参考到时，refcount就加一，反之就减一。而cpumaskspan表示rq可挂上的cpumask,noline为rq目前已经排程的cpumaskcpu上执行real-timetask.可以参考函数pull_rt_task,

17、当一个rq中属于real-time的task已经执行完毕，就会透过函数pull_rt_task从该rq中属于rto_maskcpumask可以执行的处理器上，找出是否有一个处理器有大于一个以上的real-timetask，若有就会转到目前这个执行完成real-timetask的处理器上而cpupri不同于Task本身有区分140個(0-139)TaskPriority(0-99為RTPriority而100-139為Nice值-20-19).CPUPriority本身有102個Priority(包括,-1為Invalid,0為Idle,1為Normal,2-101對應到Real-TimePri

18、ority0-99).參考函式convert_prio,TaskPriority如果是140就會對應到CPUIdle，如果是大於等於100就會對應到CPUNormal,若是TaskPriority介於0-99之間，就會對應到CPUReal-TimePriority101-2之間.)在實際的操作上，例如可以透過函式cpupri_find帶入一個要插入的Real-TimeTask，此時就會依據cpupri中pri_to_cpu選擇一個目前執行Real-TimeTask且該Task的優先級比目前要插入的Task更低的處理器，並透過CPUMask(lowest_mask)返回目前可以選擇的處理器Mas

19、k.實作的部份可以參考檔案kernel/sched_cpupri.c.在初始化的過程中，會透過函式sched_init呼叫函式init_defrootdomain,對RootDomain與CPUPriority機制進行初始化.*/structroot_domain*rd;/*ScheduleDomain是基於多核心架構下的機制.每個處理器都會有一個基礎的SchedulingDomain,SchedulingDomain可以有階層性的架構，透過parent可以找到上一層的Domain,或是透過child找到下一層的Domain（NULL表示結尾.）.並可透過span栏位,表示這個Domain所能

20、涵蓋的處理器範圍.通常BaseDomain會涵蓋系統中所有處理器的個數,而ChildDomain所能涵蓋的處理器個數不超過它的ParentDomain.而當在進行SchedulingDomain中的TaskBalanee時，就會以該Domain所能涵蓋的處理器為最大範圍.同時,每個ScheduleDomain都會包括一個或一個以上的CPUGroups（結構為structsched_group）,並透過next變數把CPUGroups串連在一起（成為一個單向的Circularlinkedlist）,每個CPUGroup都會有變數cpumask來定义這個CPUGroup所涵蓋的處理器範圍並且CPU

21、Group所包括的處理器範圍，必需涵蓋在所屬的ScheduleDomain處理器範圍中.當進行SchedulingDomain的Balancing時,會以其下的CPUGroups為單位，根據cpu_power（會是該Group所涵蓋的處理器TasksLoading的總和）來比較不同的CPUGroups的負荷，以進行Tasks的移動,達到Balancing的目的.在有支援SMP的架構下，會在函式sched_init中，呼叫open_softirq，註冊SCHED_SOFTIRQSoftwareIRQ与其对应的Callback函式run_rebalance_domains.並會在每次呼叫函式sch

22、eduler_tick時，透過函式trigger_load_balance确认是否目前的jiffies值已經大於RunQueue下一次要觸發LoadBalanee的next_balanee時間值,並透過函式raise_softirq觸發SCHED_SOFTIRQSoftwareIRQ.在SoftwareIRQ觸發後，就會呼叫函式run_rebalance_domains,並在函式rebalance_domains中,進行后续處理器上的SchedulingDomainLoadBalance動作.有關SchedulingDomain進一步的內容，也可以參考LinuxKernel文件Document

23、ation/scheduler/sched-domains.txt.*/structsched_domain*sd;/*這值會等於函式idle_cpu的返回值,如果為1表示目前CPURunQueue中執行的為IdleTask.反之為0，則表示處理器執行的不是IdleTask（也就是說194.195.196.197.198.199.200.201.202.203.204.205.206.207.208.209.210.211.212.213.214.215.216.217.218.219.220.221.222.223.224.225.226.227.228.處理器正在忙碌中.）.*/unsig

24、nedcharidle_at_tick;/*Foractivebalancing*/*若這值不為0,表示會有在Schedule排程動作結束前,要呼叫的收尾函式.（实作為inline函式post_scheduleinkernel/sched.c）,目前只有Real-TimeSchedulingClass有支援這個機制（會呼叫函式has_pushable_tasksinkernel/sched_rt.c）.*/intpost_schedule;/*當RunQueue中此值為1,表示這個RunQueue正在進行FairScheduling的LoadBalanee,此時會呼叫stop_one_cpu_

25、nowait暫停該RunQueue所屬處理器的排程,並透過函式active_load_balance_cpu_stop，把Tasks從最忙碌的處理器，移到Idle的處理器上執行*/intactive_balance;/*用以儲存目前進入Idle且負責進行LoadBalance流程的處理器ID.呼叫的流程為，在呼叫函式schedule時，若該處理器RunQueue的nr_running為0（也就是目前沒有正在執行的Task），就會呼叫idle_balanee,並觸發後續LoadBalance流程.*/intpush_cpu;/*cpuofthisrunqueue:*/*用以儲存目前运作這個Run

26、Queue的處理器ID*/intcpu;/*為1表示目前此RunQueue有在對應的處理器掛上並執行.*/intonline;/*如果RunQueue中目前有Task正在執行，這個值會等於目前該RunQueue的LoadWeight除以目前RunQueue中Task數目的均值.（rq-avg_load_per_task=rq-load.weight/nr_running;）.*/unsignedlongavg_load_per_task;structtask_struct*migration_thread;structlist_headmigration_queue;229.230.231.2

27、32.233.234.235.236.237.238.239.240.241.242.243.244.245.246.247.248.249.250.251.252.253.254.255.256.257.258.259.260.261.262.263./*這個值會由Real-TimeSchedulingClass呼叫函式update_curr_rt，用以統計目前Real-TimeTask執行時間的均值,在這函式中會以目前RunQueue的clock_task減去目前Task執行的起始時間，取得執行時間的Delta值.（delta_exec=rq-clock_taskcurr-se.exec_

28、start;）.在透過函式sched_rt_avg_update把這Delta值跟原本RunQueue中的rt_avg值取平均值.以運作的週期來看，這個值可反應目前系統中Real-TimeTask平均被分配到的執行時間值.*/u64rt_avg;/*這個值主要在函式sched_avg_update更新，以笔者手中的LinuxKernel2.6.38.6的實作來說，當RunQueueClock減去age_stamp大於0.5秒（=sched_avg_period）,就會把這值累加0.5秒（單位都是nanoseconds）.從函式scale_rt_power的實作來說,age_stamp值離Run

29、QueueClock越遠，表示total值越大,available值也越大,而函式scale_rt_power返回的div_u64計算結果也越大，最終RunQueue的cpu_power與SchedulingDomain中的SchedulingGroup的cpu_power值也就越大.（可參考函式update_cpu_power的實作）.*/u64age_stamp;/*這值會在觸發Scheduling時，若判斷目前處理器RunQueue沒有正在運作的Task，就會透過函式idle_balance更新這值為為目前RunQueue的clock值.可用以表示這個處理器是何時進入到Idle的狀態*/

30、u64idle_stamp;/*會在有Task運作且idle_stamp不為0（表示前一個狀態是在Idle）時以目前RunQueue的clock減去idle_stmp所計算出的Delta值為依據，更新這個值.可反應目前處理器進入Idle狀態的時間長短*/u64avg_idle;#endif/*calc_loadrelatedfields*/*用以記錄下一次計算CPULoad的時間，初始值為目前的jiffies加上五秒與1次的SchedulingTick的間隔(=jiffies+LOAD_FREQ,且L0AD_FREQ=(5*HZ+1)*/unsignedlongcalc_load_update

31、;/*會等於RunQueue中nr_running與nr_uninterruptible的總和.(可參考函式calc_loadold_active).*/longcalc_load_active;270.#ifdefCONFIG_SCHED_HRTICK#ifdefCONFIG_SMP/*在函式init_rq_hrtick初始化RunQueueHigh-ResolutionTick時,此值預設為0.在函式hrtick_start中,會判斷目前觸發的RunQueue跟目前處理器所使用的RunQueue是否一致,若是，就直接呼叫函式hrtimer_restart，反之就會依據RunQueue中hr

32、tick_csd_pending的值,如果hrtick_csd_pending為0，就會透過函式_smp_call_function_single讓RunQueue所在的另一個處理器執行rq-hrtick_csd.func所指到的函式_hrtick_start.並等待該處理器執行完畢後，才重新把hrtick_csd_pending設定為1.也就是說，RunQueue的hrtick_csd_pending是用來作為SMP架構下，由處理器A觸發處理器B執行_hrtick_start函式的一個保護機制.而有關在SMP下如何由一個處理器觸發另一個處理器執行函式的機制，可以參考kernel/smp.c中

33、相關smp_call_function_xxxxxxx的實作.s*/inthrtick_csd_pending;/*用以儲存hrtick機制中，要跨處理器執行的函式結構.*/structcall_single_datahrtick_csd;#endif/*為High-ResolutionTick的结构，會透過函式hrtimer_init初始化.*/structhrtimerhrtick_timer;#endif299.#ifdefCONFIG_SCHEDSTATS/*latencystats*/為SchedulingInfo.的統計結構，可以參考include/linux/sched.h中的宣

34、告.例如在每次觸發Schedule時，呼叫函式schedule_debug對上一個Task的lock_depth進行確認(Fork個新的Process時，會把此值預設為-1就是No-Lock，當呼叫KernelLock時，就會把CurrentTask的lock_depth加一.)，若lock_depth=0,就會累加SchedulingInfo.的bkl_count值，用以代表TaskBlocking的次數.*/structsched_inforq_sched_info;/*可用以表示RunQueue中的Task所得到CPU執行時間的累加值.在發生TaskSwitch時,會透過schednfo

35、_switch呼叫schednfo_arrive並以目前RunQueueClock值更新Task的sched_info.last_arrival時間，而在Task所分配時間結束後，會在函式sched_info_depart中以現在的RunQueueClock值減去Task的schednfo.last_arrival時間值，得到的Delta作為變數rq_cpu_time的累加值.*/unsignedlonglongrq_cpu_time;/*couldaboveberq-cfs_rq.exec_clock+rq-rt_rq.rt_runtime?*/322./*sys_sched_yield()

36、stats*/*用以統計呼叫SystemCallsys_sched_yield的次數.*/unsignedintyld_count;326./*schedule()stats*/unsignedintsched_switch;/*可用以統計觸發Scheduling的次數.在每次觸發Scheduling時，會透過函式schedule呼叫schedule_debug,呼叫schedstat_inc對這變數進行累加.*/unsignedintsched_count;/*可用以統計進入到IdleTask的次數.會在函式334.pick_next_task_idle中，呼叫schedstat_inc對這

37、變數進行335.累加.*/336.unsignedintsched_goidle;337.338./*try_to_wake_up()stats*/339./*用以統計WakeUpTask的次數.*/340.unsignedintttwu_count;341./*用以統計WakeUp冋一個處理器Task的次數.*/342.unsignedintttwu_local;343.344./*BKLstats*/345.unsignedintbkl_count;346.#endif347.;/*每个处理器都会配置-rrq/*rq-个rq*/*/-_J/*调度类，sched_class为对模块编程的上层

38、支持，对于每个linux新添加进来的调度算法都需要有自己的调度类实例。/*CFS排程機制在設計時，考慮到排程機制的彈性，定義了SchedulerClass的機制，讓排程機制可以根據設計的需求,延伸不同的排程模組進來，每個新加入的排程機制都必須要提供SchedulerClass的實作，結構為structsched_class*/structsched_class/*會指向下一個SchedulingClass,以筆者所採用的LinuxKernel2.6.38.6而言,SchedulingClass的順序為stop_sched_class-rt_sched_class-fair_sched_clas

39、s-idle_sched_class*/conststructsched_class*next;/*當Task屬於Runnable狀態時，就會呼叫這個函式把Task配置到RunQueueRBTree中,進行排程動作,並呼叫inc_nr_running將RunQueue中nr_running的值加一.(nr_running用以代表目前RunQueue有多少RunnableTask進行排程)*/void(*enqueue_task)(structrq*rq,structtask_struct*p,intwakeup);/*當Task不需要執行時,就會呼叫這個函式把Task從RunQueueRBTr

40、ee中移除,並呼叫dec_nr_running將RunQueue中nr_running的值減一.*/void(*dequeue_task)(structrq*rq,structtask_struct*p,intsleep);/*用以暫停目前正在執行中的Task，如果sysctl_sched_compat_yield有設定,就會找出目前RBTree中最右邊的Task(也就是vrruntime最多的Task)，讓目前Task的vrruntime值等於最右邊Task值的vrruntime加一(可參考:se-vruntime=rightmost-vruntime+1)，如此在下次排程觸發時就會透過函式

41、put_prev_task把目前的Task放到RBTree的最右邊，也就等同於暫停Task,讓該Task下次被執行到的機會最低*/void(*yield_task)(structrq*rq);/*用以決定一個Task是否可以中斷目前正在運作的Task，取得執行權以CFS本身的實作來說(insched_fair.c).如果想要取代目前Task的Task本身的SchedulingPolicy為Batch或是Idle時,會直接返回，不會用來取代目前正在執行中的Task.反之，如果目前正在執行中的Task的SchedulingPolicy為Idle,就會直接由所傳入的Task取代目前正在執行的Task

42、.*/void(*check_preempt_curr)(structrq*rq，structtask_struct*p，intflags);/*用以在排程觸發時，從RunQueueRBTree中，取出符合目前Scheduling邏輯的下一個要被執行的Task.*/structtask_struct*(*pick_next_task)(structrq*rq);/*用以在排程觸發時，把上一個執行完畢的Task放到目前RunQueueRBTree中對應的位置.*/void(*put_prev_task)(structrq*rq，structtask_struct*p);47.#ifdefCONFIG_SMP/*通常用在執行一個新的程序，或是WakeUp一個Task時，會根據目前SMP下每個處理器的負荷，決定Task是否要切換到另一個處理器的RunQueue去執行，執行時會返回最後目標處理器的值.*/int(*select_task_rq)(structtask_struct*p，intsd_flag，intflags);55.unsignedlong(*load_balance)(structrq*this_rq，intthis_cpu，structrq*busiest，unsignedlongmax_load_move，structsche