Linux內核調度算法

為什麼要了解內核的調度策略呢？呵呵，因為它值得我們學習，不算是廢話吧。內核調度程序很先進很強大，管理你的LINUX上跑的大量的亂七八糟的進程，同時還保持著對用戶操作的高靈敏響應，如果可能，為什麼不把這種思想放到自己的應用程序裡呢？或者，有沒有可能更好的實現自己的應用，使得操作系統能夠以自己的意志來分配資源給自己的進程？

帶著這兩個問題來看看KERNEL。首先回顧上我們開發應用程序，基本上就兩種類型，1、IO消耗型：比如Hadoop上的trunk服務，很明顯它的消耗主要在IO上，包括網絡IO磁盤IO等等。2、CPU消耗型，比如mapreduce或者其他的需要對大量數據進行計算處理的組件，就象對高清視頻壓縮成適合手機觀看分辨率的進程，他們的消耗主要在CPU上。當兩類進程都在一台SERVER上運行時，操作系統會如何調度它們呢？現在的服務器都是SMP多核的，那麼一個進程在多CPU時會來回切換嗎？如果我有一個程序，既有IO消耗又有CPU消耗，怎麼讓多核更好的調度我的程序呢？


又多了幾個問題。來看看內核調度程序吧，我們先從它的優先隊列談起吧。調度程序代碼就在內核源碼的kernel/sched.c的schedule函數中。
首先看下面的優先級隊列，每一個runqueue都有。runqueue是什麼？下面會詳細說下，現在大家可以理解為，內核為每一顆CPU分配了一個runqueue，用於維護這顆CPU可以運行的進程。runqueue裡，有幾個成員是prio_array類型，這個東東就是優先隊列，先看看它的定義：
[cpp]

1. struct prio_array {
2. unsigned int nr_active; 表示等待執行的進程總數
3. unsigned long bitmap[BITMAP_SIZE]; 一個unsigned long在內核中只有32位哈，大家要跟64位OS上的C程序中的long區分開，那個是64位的。那麼這個bitmap是干什麼的呢？它是用位的方式，表示某個優先級上有沒有待處理的隊列，是實現快速找到最高待處理優先進程的關鍵。如果我定義了四種優先級，我只需要四位就能表示某個優先級上有沒有進程要運行，例如優先級是2和3上有進程，那麼就應該是0110.......非常省空間，效率也快，不是嗎？
4. struct list_head queue[MAX_PRIO]; 與上面的bitmap是對應的，它存儲所有等待運行的進程。
5. };

看看BITMAP_SIZE是怎麼算出來的：#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
那麼，LINUX默認配置（如果你用默認選項編譯內核的話）MAX_PRIO是140，就是說一共內核對進程一共定義了140種優先級。等待某個CPU來處理的進程中，可能包含許多種優先級的進程，但，LINUX是個搶占式調度算法的操作系統，就是說，需要調度時一定是找到最高優先級的進程執行。上面的BITMAP_SIZE值根據MAX_PRIO算出來為5，那麼bitmap實際是32*5=160位，這樣就包含了MAX_PRIO的140位。優先級隊列是怎麼使用的？看2649行代碼：idx = sched_find_first_bit(array->bitmap);這個方法就用來快速的找到優先級最高的隊列。看看它的實現可以方便我們理解這個優先級位的設計：
[cpp]

1. static inline int sched_find_first_bit(unsigned long *b)
2. {
3. if (unlikely(b[0]))
4. return __ffs(b[0]);
5. if (unlikely(b[1]))
6. return __ffs(b[1]) + 32;
7. if (unlikely(b[2]))
8. return __ffs(b[2]) + 64;
9. if (b[3])
10. return __ffs(b[3]) + 96;
11. return __ffs(b[4]) + 128;
12. }

那麼__ffs是干什麼的？
[cpp]

1. static inline int __ffs(int x)
2. {
3. int r = 0;
5. if (!x)
6. return 0;
7. if (!(x & 0xffff)) {
8. x >>= 16;
9. r += 16;
10. }
11. if (!(x & 0xff)) {
12. x >>= 8;
13. r += 8;
14. }
15. if (!(x & 0xf)) {
16. x >>= 4;
17. r += 4;
18. }
19. if (!(x & 3)) {
20. x >>= 2;
21. r += 2;
22. }
23. if (!(x & 1)) {
24. x >>= 1;
25. r += 1;
26. }
27. return r;
28. }

sched_find_first_bit返回值就是最高優先級所在隊列的序號，與queue是對應使用的哈，queue = array->queue + idx;這樣就取到了要處理的進程隊列。這個設計在查找優先級時是非常快的，非常值得我們學習。


好，優先級隊列搞明白了，現在來看看runqueue，每個runqueue包含三個優先級隊列。
[cpp]

1. struct runqueue {
2. spinlock_t lock; 這是個自旋鎖，nginx裡解決驚群現象時也是用這個。與普通鎖的區別就是，使用普通鎖時，你去試圖拿一把鎖，結果發現已經被別人拿走了，你就在那睡覺，等別人鎖用完了叫你起來。所以如果有一個人拿住鎖了，一百個人都在門前睡覺等。當之前的人用完鎖回來後，會叫醒所有100個等鎖的人，然後這些人開始互相搶，搶到的人拿鎖進去，其他的人繼續等。自旋鎖不同，當他去拿鎖發現鎖被別人拿走了，他在那不睡覺的等，稍打個盹就看看自己主動看看鎖有沒有還回來。大家比較出優劣了嗎？
5. /*
6. * nr_running and cpu_load should be in the same cacheline because
7. * remote CPUs use both these fields when doing load calculation.
8. */
9. unsigned long nr_running;
10. #ifdef CONFIG_SMP
11. unsigned long cpu_load;
12. #endif
13. unsigned long long nr_switches;
16. /*
17. * This is part of a global counter where only the total sum
18. * over all CPUs matters. A task can increase this counter on
19. * one CPU and if it got migrated afterwards it may decrease
20. * it on another CPU. Always updated under the runqueue lock:
21. */
22. unsigned long nr_uninterruptible;
25. unsigned long expired_timestamp;
26. unsigned long long timestamp_last_tick;
27. task_t *curr, *idle;
28. struct mm_struct *prev_mm;
29. prio_array_t *active, *expired, arrays[2];上面說了半天的優先級隊列在這裡，但是在runqueue裡，為什麼不只一個呢？這個在下面講。
30. int best_expired_prio;
31. atomic_t nr_iowait;
32. ... ...
33. };

LINUX是一個時間多路復用的系統，就是說，通過把CPU執行時間分成許多片，再分配給進程們使用，造成即使單CPU系統，也貌似允許多個任務在同時執行。那麼，時間片大小假設為100ms，過短過長，過長了有些不靈敏，過短了，連切換進程時可能都要消耗幾毫秒的時間。分給100個進程執行，在所有進程都用完自己的時間片後，需要重新給所有的進程重新分配時間片，怎麼分配呢？for循環遍歷所有的run狀態進程，重設時間片？這個性能無法容忍！太慢了，跟當前系統進程數相關。那麼2.6內核怎麼做的呢？它用了上面提到的兩個優先級隊列active和expired，顧名思義，active是還有時間片的進程隊列，而expired是時間片耗盡必須重新分配時間片的進程隊列。


這麼設計的好處就是不用再循環一遍所有進程重設時間片了，看看調度函數是怎麼玩的：
[cpp]

1. array = rq->active;
2. if (unlikely(!array->nr_active)) {
3. /*
4. * Switch the active and expired arrays.
5. */
6. schedstat_inc(rq, sched_switch);
7. rq->active = rq->expired;
8. rq->expired = array;
9. array = rq->active;
10. rq->expired_timestamp = 0;
11. rq->best_expired_prio = MAX_PRIO;
12. } else
13. schedstat_inc(rq, sched_noswitch);

當所有運行進程的時間片都用完時，就把active和expired隊列互換指針，沒有遍歷哦，而時間片耗盡的進程在出acitve隊列入expired隊列時，已經單獨的重新分配好新時間片了。


再看一下schedule(void)調度函數，當某個進程休眠或者被搶占時，系統就開始調試schedule(void)決定接下來運行哪個進程。上面說過的東東都在這個函數裡有體現哈。
[cpp]

1. asmlinkage void __sched schedule(void)
2. {
3. long *switch_count;
4. task_t *prev, *next;
5. runqueue_t *rq;
6. prio_array_t *array;
7. struct list_head *queue;
8. unsigned long long now;
9. unsigned long run_time;
10. int cpu, idx;
13. /*
14. * Test if we are atomic. Since do_exit() needs to call into
15. * schedule() atomically, we ignore that path for now.
16. * Otherwise, whine if we are scheduling when we should not be.
17. */
18. if (likely(!(current->exit_state & (EXIT_DEAD | EXIT_ZOMBIE)))) {先看看當前運行進程的狀態
19. if (unlikely(in_atomic())) {
20. printk(KERN_ERR "scheduling while atomic: "
21. "%s/0x%08x/%d\n",
22. current->comm, preempt_count(), current->pid);
23. dump_stack();
24. }
25. }
26. profile_hit(SCHED_PROFILING, __builtin_return_address(0));
29. need_resched:
30. preempt_disable();
31. prev = current;
32. release_kernel_lock(prev);
33. need_resched_nonpreemptible:
34. rq = this_rq(); 這行找到這個CPU對應的runqueue，再次強調，每個CPU有一個自己的runqueue
37. /*
38. * The idle thread is not allowed to schedule!
39. * Remove this check after it has been exercised a bit.
40. */
41. if (unlikely(current == rq->idle) && current->state != TASK_RUNNING) {
42. printk(KERN_ERR "bad: scheduling from the idle thread!\n");
43. dump_stack();
44. }
47. schedstat_inc(rq, sched_cnt);
48. now = sched_clock();
49. if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG))
50. run_time = now - prev->timestamp;
51. else
52. run_time = NS_MAX_SLEEP_AVG;
55. /*
56. * Tasks with interactive credits get charged less run_time
57. * at high sleep_avg to delay them losing their interactive
58. * status
59. */
60. if (HIGH_CREDIT(prev))
61. run_time /= (CURRENT_BONUS(prev) ? : 1);
64. spin_lock_irq(&rq->lock);
67. if (unlikely(current->flags & PF_DEAD))
68. current->state = EXIT_DEAD;
69. /*
70. * if entering off of a kernel preemption go straight
71. * to picking the next task.
72. */
73. switch_count = &prev->nivcsw;
74. if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
75. switch_count = &prev->nvcsw;
76. if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
77. unlikely(signal_pending(prev))))
78. prev->state = TASK_RUNNING;
79. else {
80. if (prev->state == TASK_UNINTERRUPTIBLE)
81. rq->nr_uninterruptible++;
82. deactivate_task(prev, rq);
83. }
84. }
87. cpu = smp_processor_id();
88. if (unlikely(!rq->nr_running)) {
89. go_idle:
90. idle_balance(cpu, rq);
91. if (!rq->nr_running) {
92. next = rq->idle;
93. rq->expired_timestamp = 0;
94. wake_sleeping_dependent(cpu, rq);
95. /*
96. * wake_sleeping_dependent() might have released
97. * the runqueue, so break out if we got new
98. * tasks meanwhile:
99. */
100. if (!rq->nr_running)
101. goto switch_tasks;
102. }
103. } else {
104. if (dependent_sleeper(cpu, rq)) {
105. next = rq->idle;
106. goto switch_tasks;
107. }
108. /*
109. * dependent_sleeper() releases and reacquires the runqueue
110. * lock, hence go into the idle loop if the rq went
111. * empty meanwhile:
112. */
113. if (unlikely(!rq->nr_running))
114. goto go_idle;
115. }
118. array = rq->active;
119. if (unlikely(!array->nr_active)) { 上面說過的，需要重新計算時間片時，就用已經計算好的expired隊列了
120. /*
121. * Switch the active and expired arrays.
122. */
123. schedstat_inc(rq, sched_switch);
124. rq->active = rq->expired;
125. rq->expired = array;
126. array = rq->active;
127. rq->expired_timestamp = 0;
128. rq->best_expired_prio = MAX_PRIO;
129. } else
130. schedstat_inc(rq, sched_noswitch);
133. idx = sched_find_first_bit(array->bitmap); 找到優先級最高的隊列
134. queue = array->queue + idx;
135. next = list_entry(queue->next, task_t, run_list);
138. if (!rt_task(next) && next->activated > 0) {
139. unsigned long long delta = now - next->timestamp;
142. if (next->activated == 1)
143. delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
146. array = next->array;
147. dequeue_task(next, array);
148. recalc_task_prio(next, next->timestamp + delta);
149. enqueue_task(next, array);
150. }
151. next->activated = 0;
152. switch_tasks:
153. if (next == rq->idle)
154. schedstat_inc(rq, sched_goidle);
155. prefetch(next);
156. clear_tsk_need_resched(prev);
157. rcu_qsctr_inc(task_cpu(prev));
160. prev->sleep_avg -= run_time;
161. if ((long)prev->sleep_avg <= 0) {
162. prev->sleep_avg = 0;
163. if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev)))
164. prev->interactive_credit--;
165. }
166. prev->timestamp = prev->last_ran = now;
169. sched_info_switch(prev, next);
170. if (likely(prev != next)) { 表面現在正在執行的進程，不是選出來的優先級最高的進程
171. next->timestamp = now;
172. rq->nr_switches++;
173. rq->curr = next;
174. ++*switch_count;
177. prepare_arch_switch(rq, next);
178. prev = context_switch(rq, prev, next); 所以需要完成進程上下文切換，把之前的進程信息CACHE住
179. barrier();
182. finish_task_switch(prev);
183. } else
184. spin_unlock_irq(&rq->lock);
187. prev = current;
188. if (unlikely(reacquire_kernel_lock(prev) < 0))
189. goto need_resched_nonpreemptible;
190. preempt_enable_no_resched();
191. if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
192. goto need_resched;
193. }

當然，在我們程序中，也可以通過執行以下系統調用來改變自己進程的優先級。nice系統調用可以改變某個進程的基本優先級，setpriority可以改變一組進程的優先級。