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呼叫时进行累加，并可以通过函数 linux下的sleep函数
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: 

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。