linux内核分析之调度算法（三）

so_brave

linux内核分析之调度算法（三）

1. struct sched_class {  
   
2.     /*會指向下一個Scheduling Class,以筆者所採用
   
3.     的Linux Kernel 2.6.38.6而言,Scheduling Class的順序為
   
4.     stop_sched_class->rt_sched_class->fair_sched_class->idle_sched_class*/  
   
5.     const struct sched_class *next;  
   
6.     /*當Task屬於Runnable狀態時,就會呼叫這個函式
   
7.     把Task配置到RunQueue RBTree中,進行排程動作,
   
8.     並呼叫inc_nr_running將RunQueue中nr_running的值
   
9.     加一.(nr_running用以代表目前RunQueue有多少
   
10.     Runnable Task進行排程)*/  
    
11.     void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);  
    
12.     /*當Task不需要執行時,就會呼叫這個函式
    
13.     把Task從RunQueue RBTree中移除,並呼叫
    
14.     dec_nr_running將RunQueue中nr_running的值減一.*/  
    
15.     void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);  
    
16.     /*用以暫停目前正在執行中的Task,如果
    
17.     sysctl_sched_compat_yield有設定,就會找出目前
    
18.     RBTree中最右邊的Task(也就是vrruntime最多
    
19.     的Task),讓目前Task的vrruntime值等於最右邊
    
20.     Task值的vrruntime加一(可參考:
    
21.     se->vruntime = rightmost->vruntime + 1),如此在下次
    
22.     排程觸發時就會透過函式put_prev_task把目前
    
23.     的Task放到RBTree的最右邊,也就等同於暫停
    
24.     Task,讓該Task下次被執行到的機會最低.*/  
    
25.     void (*yield_task) (struct rq *rq);  
    
26.     /*用以決定一個Task是否可以中斷目前正在
    
27.     運作的Task,取得執行權.以CFS本身的實作來說
    
28.     (in sched_fair.c).如果想要取代目前Task的Task本身
    
29.     的Scheduling Policy為 Batch或是Idle時,會直接返回,
    
30.     不會用來取代目前正在執行中的Task.反之,
    
31.     如果目前正在執行中的Task的Scheduling Policy
    
32.     為Idle,就會直接由所傳入的Task取代目前正
    
33.     在執行的Task.*/  
    
34.     void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);  
    
35.     /*用以在排程觸發時,從RunQueue RBTree中,
    
36.     取出符合目前Scheduling邏輯的下一個要
    
37.     被執行的Task.*/  
    
38.     struct task_struct * (*pick_next_task) (struct rq *rq);  
    
39.     /*用以在排程觸發時,把上一個執行完畢的
    
40.     Task放到目前RunQueue RBTree中對應的位置.*/  
    
41.     void (*put_prev_task) (struct rq *rq, struct task_struct *p);  
    
42.   
    
43. #ifdef CONFIG_SMP   
    
44.     /*通常用在執行一個新的程序,或是WakeUp
    
45.     一個Task時,會根據目前SMP下每個處理器的
    
46.     負荷,決定Task是否要切換到另一個處理器
    
47.     的RunQueue去執行,執行時會返回最後目標
    
48.     處理器的值.*/  
    
49.     int  (*select_task_rq)(struct task_struct *p, int sd_flag, int flags);  
    
50.   
    
51.     unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,  
    
52.             struct rq *busiest, unsigned long max_load_move,  
    
53.             struct sched_domain *sd, enum cpu_idle_type idle,  
    
54.             int *all_pinned, int *this_best_prio);  
    
55.   
    
56.     int (*move_one_task) (struct rq *this_rq, int this_cpu,  
    
57.                   struct rq *busiest, struct sched_domain *sd,  
    
58.                   enum cpu_idle_type idle);  
    
59.     void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);  
    
60.     void (*post_schedule) (struct rq *this_rq);  
    
61.     void (*task_wake_up) (struct rq *this_rq, struct task_struct *task);  
    
62.   
    
63.     void (*set_cpus_allowed)(struct task_struct *p,  
    
64.                  const struct cpumask *newmask);  
    
65.   
    
66.     void (*rq_online)(struct rq *rq);  
    
67.     void (*rq_offline)(struct rq *rq);  
    
68. #endif   
    
69.     /*這個函式用以改變Task目前所屬的Scheduling
    
70.     Class與改變Task Group.*/  
    
71.     void (*set_curr_task) (struct rq *rq);  
    
72.     /*這是Scheduler的 Timer Tick來源,系統中觸發的
    
73.     Scheduling Tick會呼叫這個函式 (看HZ設定多少,
    
74.     100就是每秒呼叫這函式100次,1000就是每秒
    
75.     呼叫這函式1000次),
    
76.     用以讓排程機制可以決定哪些Task應該要配
    
77.     執行與哪些Task應該要被移出RunQueue.*/  
    
78.     void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);  
    
79.     void (*task_new) (struct rq *rq, struct task_struct *p);  
    
80.   
    
81.     void (*switched_from) (struct rq *this_rq, struct task_struct *task,  
    
82.                    int running);  
    
83.     void (*switched_to) (struct rq *this_rq, struct task_struct *task,  
    
84.                  int running);  
    
85.     void (*prio_changed) (struct rq *this_rq, struct task_struct *task,  
    
86.                  int oldprio, int running);  
    
87.   
    
88.     unsigned int (*get_rr_interval) (struct task_struct *task);  
    
89.   
    
90. #ifdef CONFIG_FAIR_GROUP_SCHED   
    
91.     void (*moved_group) (struct task_struct *p);  
    
92. #endif   
    
93. };  
    
94. /*CFS排程機制在設計時,考慮到排程機制的
    
95. 彈性,定義了Scheduler Class的機制,讓排程機制
    
96. 可以根據設計的需求,延伸不同的排程模
    
97. 組進來,每個新加入的排程機制都必須要
    
98. 提供Scheduler Class的實作,結構為 struct sched_class*/
    
99. struct sched_class {
    
100.         /*會指向下一個Scheduling Class,以筆者所採用
     
101.         的Linux Kernel 2.6.38.6而言,Scheduling Class的順序為
     
102.         stop_sched_class->rt_sched_class->fair_sched_class->idle_sched_class*/
     
103.         const struct sched_class *next;
     
104.         /*當Task屬於Runnable狀態時,就會呼叫這個函式
     
105.         把Task配置到RunQueue RBTree中,進行排程動作,
     
106.         並呼叫inc_nr_running將RunQueue中nr_running的值
     
107.         加一.(nr_running用以代表目前RunQueue有多少
     
108.         Runnable Task進行排程)*/
     
109.         void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
     
110.         /*當Task不需要執行時,就會呼叫這個函式
     
111.         把Task從RunQueue RBTree中移除,並呼叫
     
112.         dec_nr_running將RunQueue中nr_running的值減一.*/
     
113.         void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
     
114.         /*用以暫停目前正在執行中的Task,如果
     
115.         sysctl_sched_compat_yield有設定,就會找出目前
     
116.         RBTree中最右邊的Task(也就是vrruntime最多
     
117.         的Task),讓目前Task的vrruntime值等於最右邊
     
118.         Task值的vrruntime加一(可參考:
     
119.         se->vruntime = rightmost->vruntime + 1),如此在下次
     
120.         排程觸發時就會透過函式put_prev_task把目前
     
121.         的Task放到RBTree的最右邊,也就等同於暫停
     
122.         Task,讓該Task下次被執行到的機會最低.*/
     
123.         void (*yield_task) (struct rq *rq);
     
124.         /*用以決定一個Task是否可以中斷目前正在
     
125.         運作的Task,取得執行權.以CFS本身的實作來說
     
126.         (in sched_fair.c).如果想要取代目前Task的Task本身
     
127.         的Scheduling Policy為 Batch或是Idle時,會直接返回,
     
128.         不會用來取代目前正在執行中的Task.反之,
     
129.         如果目前正在執行中的Task的Scheduling Policy
     
130.         為Idle,就會直接由所傳入的Task取代目前正
     
131.         在執行的Task.*/
     
132.         void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
     
133.         /*用以在排程觸發時,從RunQueue RBTree中,
     
134.         取出符合目前Scheduling邏輯的下一個要
     
135.         被執行的Task.*/
     
136.         struct task_struct * (*pick_next_task) (struct rq *rq);
     
137.         /*用以在排程觸發時,把上一個執行完畢的
     
138.         Task放到目前RunQueue RBTree中對應的位置.*/
     
139.         void (*put_prev_task) (struct rq *rq, struct task_struct *p);
     
140. 
     
141. #ifdef CONFIG_SMP
     
142.         /*通常用在執行一個新的程序,或是WakeUp
     
143.         一個Task時,會根據目前SMP下每個處理器的
     
144.         負荷,決定Task是否要切換到另一個處理器
     
145.         的RunQueue去執行,執行時會返回最後目標
     
146.         處理器的值.*/
     
147.         int  (*select_task_rq)(struct task_struct *p, int sd_flag, int flags);
     
148. 
     
149.         unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
     
150.                         struct rq *busiest, unsigned long max_load_move,
     
151.                         struct sched_domain *sd, enum cpu_idle_type idle,
     
152.                         int *all_pinned, int *this_best_prio);
     
153. 
     
154.         int (*move_one_task) (struct rq *this_rq, int this_cpu,
     
155.                               struct rq *busiest, struct sched_domain *sd,
     
156.                               enum cpu_idle_type idle);
     
157.         void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
     
158.         void (*post_schedule) (struct rq *this_rq);
     
159.         void (*task_wake_up) (struct rq *this_rq, struct task_struct *task);
     
160. 
     
161.         void (*set_cpus_allowed)(struct task_struct *p,
     
162.                                  const struct cpumask *newmask);
     
163. 
     
164.         void (*rq_online)(struct rq *rq);
     
165.         void (*rq_offline)(struct rq *rq);
     
166. #endif
     
167.         /*這個函式用以改變Task目前所屬的Scheduling
     
168.         Class與改變Task Group.*/
     
169.         void (*set_curr_task) (struct rq *rq);
     
170.         /*這是Scheduler的 Timer Tick來源,系統中觸發的
     
171.         Scheduling Tick會呼叫這個函式 (看HZ設定多少,
     
172.         100就是每秒呼叫這函式100次,1000就是每秒
     
173.         呼叫這函式1000次),
     
174.         用以讓排程機制可以決定哪些Task應該要配
     
175.         執行與哪些Task應該要被移出RunQueue.*/
     
176.         void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
     
177.         void (*task_new) (struct rq *rq, struct task_struct *p);
     
178. 
     
179.         void (*switched_from) (struct rq *this_rq, struct task_struct *task,
     
180.                                int running);
     
181.         void (*switched_to) (struct rq *this_rq, struct task_struct *task,
     
182.                              int running);
     
183.         void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
     
184.                              int oldprio, int running);
     
185. 
     
186.         unsigned int (*get_rr_interval) (struct task_struct *task);
     
187. 
     
188. #ifdef CONFIG_FAIR_GROUP_SCHED
     
189.         void (*moved_group) (struct task_struct *p);
     
190. #endif
     
191. };
     

复制代码

调度实体，调度实体用于调度时间记账，linux中CFS和实时调度使用不同的调度实体。调度运行队列，对于不用的调度算法同样运用不用的运行队列，对于CFS调度，运用的是红黑树，而对于实时调度为组链表。在后面具体的调度算法介绍中我们会看到他们的运用。

阳光的扣子

谢谢分享