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;  
4.   
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個等鎖的人，然後這些人開始互相搶，搶到的人拿鎖進去，其他的人繼續等。自旋鎖不同，當他去拿鎖發現鎖被別人拿走了，他在那不睡覺的等，稍打個盹就看看自己主動看看鎖有沒有還回來。大家比較出優劣了嗎？  
3.   
4.   
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;  
14.   
15.   
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;  
23.   
24.   
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;  
11.   
12.   
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));  
27.   
28.   
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  
35.   
36.   
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.     }  
45.   
46.   
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;  
53.   
54.   
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);  
62.   
63.   
64.     spin_lock_irq(&rq->lock);  
65.   
66.   
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.     }  
85.   
86.   
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.     }  
116.   
117.   
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);  
131.   
132.   
133.     idx = sched_find_first_bit(array->bitmap);         找到優先級最高的隊列  
134.     queue = array->queue + idx;  
135.     next = list_entry(queue->next, task_t, run_list);  
136.   
137.   
138.     if (!rt_task(next) && next->activated > 0) {  
139.         unsigned long long delta = now - next->timestamp;  
140.   
141.   
142.         if (next->activated == 1)  
143.             delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;  
144.   
145.   
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));  
158.   
159.   
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;  
167.   
168.   
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;  
175.   
176.   
177.         prepare_arch_switch(rq, next);  
178.         prev = context_switch(rq, prev, next);              所以需要完成進程上下文切換，把之前的進程信息CACHE住  
179.         barrier();  
180.   
181.   
182.         finish_task_switch(prev);  
183.     } else  
184.         spin_unlock_irq(&rq->lock);  
185.   
186.   
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可以改變一組進程的優先級。