Linux内核分析之调度算法.doc

Linux内核分析之调度算法inux调度算法在2.6.32中采用调度类实现模块式的调度方式。这样，能够很好的加入新的调度算法。linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类，他允许多种不同哦可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，调度代码会按照优先级遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那个程序。linux上主要有两大类调度算法，CFS(完全公平调度算法）和实时调度算法。宏SCHED_NOMAL主要用于CFS调度，而SCHED_FIFO和SCHED_RR主要用于实时调度。如下面的宏定义：/**Schedulingpolicies*//*支援Real-TimeTask的排程,包括有SCHED_FIFO與SCHED_RR.*//*(也稱為SCHED_OTHER):主要用以排程一般目的的Task.*/#defineSCHED_NORMAL0#defineSCHED_FIFO1/*task預設的TimeSlice長度為100msecs*/#defineSCHED_RR2/*主要用以讓Task可以延長執行的時間(TimeSlice),減少被中斷發生TaskContext-Switch的次數.藉此可以提高Cache的利用率(每次Context-Switch都會導致Cache-Flush).比較適合用在固定週期執行的BatchJobs任務主機上,而不適合用在需要使用者互動的產品(會由於Task切換的延遲,而感覺到系統效能不佳或是反應太慢).*/#defineSCHED_BATCH3/*SCHED_ISO:reservedbutnotimplementedyet*//*為系統中的IdleTask排程.*/#defineSCHED_IDLE5linux调度算法实现的高层数据结构主要有运行实体、调度类、运行队列，下面我们主要看看这几个数据结构的字段和意义。运行实体，rq结构体每个cpu有一个，主要存储一些基本的用于调度的信息，包括实时调度的和CFS调度的/*每个处理器都会配置一个rq*/structrq{/*runqueuelock:*/spinlock_tlock;/**nr_runningandcpu_loadshouldbeinthesamecachelinebecause*remoteCPUsuseboththesefieldswhendoingloadcalculation.*//*用以记录目前处理器rq中执行task的数量*/unsignedlongnr_running;#defineCPU_LOAD_IDX_MAX5/*用以表示处理器的负载，在每个处理器的rq中都会有对应到该处理器的cpu_load参数配置，在每次处理器触发schedulertick时，都会呼叫函数update_cpu_load_active,进行cpu_load的更新。在系统初始化的时候会呼叫函数sched_init把rq的cpu_loadarray初始化为0.了解他的更新方式最好的方式是通过函数update_cpu_load,公式如下澹?cpu_load[0]会直接等待rq中load.weight的值。cpu_load[1]=(cpu_load[1]*(2-1)+cpu_load[0])/2cpu_load[2]=(cpu_load[2]*(4-1)+cpu_load[0])/4cpu_load[3]=(cpu_load[3]*(8-1)+cpu_load[0])/8cpu_load[4]=(cpu_load[4]*(16-1)+cpu_load[0]/16呼叫函数this_cpu_load时，所返回的cpuload值是cpu_load[0]而在进行cpublance或migration时，就会呼叫函数source_loadtarget_load取得对该处理器cpu_loadindex值，来进行计算*/unsignedlongcpu_load[CPU_LOAD_IDX_MAX];#ifdefCONFIG_NO_HZunsignedlonglast_tick_seen;unsignedcharin_nohz_recently;#endif/*captureloadfrom*all*tasksonthiscpu:*//*load->weight值，会是目前所执行的scheduleentity的load->weight的总和，也就是说rq的load->weight越高，也表示所负责的排程单元load->weight总和越高表示处理器所负荷的执行单元也越重*/structload_weightload;/*在每次sche