原文地址: https://blog.csdn.net/zhangzheng_1986/article/details/81945084

1.任務調度原則：

• 先執(zhí)行優(yōu)先級高的任務乙漓，再執(zhí)行優(yōu)先級低的任務蘑斧。

• 優(yōu)先級相同的任務按時間片輪轉的方式調度舷手。

  
  
  這里寫圖片描述

  Runqueueu 數(shù)組的每一項對應一種優(yōu)先級慎璧，數(shù)據(jù)越小卓嫂，優(yōu)先級越高瓮具。只有存在就緒任務的 Runqueue數(shù)組項才被鏈接到以 runqueue_head 為頭的鏈表當中槽袄。系統(tǒng)進行任務調度時，通過 runqueue_head 尋找優(yōu)先級最高的隊列毫捣，然后從該隊列中尋找第一個 TCB 進行調度详拙。當同一個優(yōu)先級存在多個任務時帝际，則首先調度第一個 TCB 運行，當其運行完自己的時間片后饶辙，將它放入到鏈表的最后蹲诀，這樣使同一級別的其他任務能得到調度機會，從而實現(xiàn)時間片輪轉調度弃揽。

2.時間片輪轉概念：

在早期的時間片輪轉法中脯爪，系統(tǒng)將所有就緒態(tài)進程按先來先服務的原則，排成一個隊列矿微。每次調度時痕慢，把CPU分配給隊首進程，并令其執(zhí)行一個時間片涌矢。時間片的大小從幾ms到幾百ms掖举。當執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求娜庇，調度程序便據(jù)此信號來停止該進程的執(zhí)行塔次，并將它送往就緒隊列的末尾;然后，再把處理機分配給就緒隊列中新的隊首進程名秀，同時也讓它執(zhí)行一個時間片励负。這樣就可以保證就緒隊列中的所有進程，在一給定的時間內匕得，均能獲得一時間片的處理機執(zhí)行時間熄守。

這里寫圖片描述

在單 CPU 系統(tǒng)中，處于運行態(tài)的任務只有一個耗跛，而在多 CPU 系統(tǒng)中，每個CPU 都有一個處于運行態(tài)的任務攒发，處于就緒態(tài)和等待狀態(tài)的任務則可能有多個调塌。

這里寫圖片描述

如果在時間片結束時進程還在運行，則CPU將被剝奪并分配給另一個進程惠猿。如果進程在時間片結束前阻塞或結束(內部調用schedule())羔砾，則CPU當即進行切換。調度程序所要做的就是維護一張就緒進程列表偶妖，當進程用完它的時間片后姜凄，它被移到隊列的末尾。

對于 TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE 補充說明一下：

在Linux中捐友，僅等待CPU時間的進程稱為就緒進程淫半，它們被放置在一個就緒隊列中，一個就緒進程的狀態(tài)標志位為TASK_RUNNING匣砖。一旦一個運行中的進程時間片用完科吭， Linux 內核的調度器會剝奪這個進程對CPU的控制權，并且從就緒隊列中選擇一個優(yōu)先級最高的首進程投入運行猴鲫。
? 當然对人，一個進程也可以主動釋放CPU的控制權。函數(shù) schedule()是一個調度函數(shù)变隔，它可以被一個進程主動調用规伐，從而調度其它進程占用CPU。一旦這個主動放棄CPU的進程被重新調度占用 CPU匣缘，那么它將從上次停止執(zhí)行的位置開始執(zhí)行猖闪，也就是說它將從調用schedule()的下一行代碼處開始執(zhí)行。
有時候肌厨，進程需要等待直到某個特定的事件發(fā)生培慌，例如設備初始化完成、I/O 操作完成或定時器到時等柑爸。在這種情況下吵护，進程則必須從運行隊列移出（設置當前進程狀態(tài)為TASK_INTERRUPTIBLE），加入到一個等待隊列中（調用schedule()函數(shù)）表鳍，這個時候進程就進入了睡眠狀態(tài)馅而。

3.Linux中進程狀態(tài)睡眠分類

在現(xiàn)代的Linux操作系統(tǒng)中，進程一般都是用調用schedule()的方法進入睡眠狀態(tài)的譬圣，下面的代碼演示了如何讓正在運行的進程進入睡眠狀態(tài)瓮恭。

sleeping_task = current;
set_current_state(TASK_INTERRUPTIBLE);
schedule();
func1();
/* Rest of the code ... */

在第一個語句中，程序存儲了一份進程結構指針sleeping_task厘熟，current 是一個宏屯蹦，它指向正在執(zhí)行的進程結構。set_current_state()將該進程的狀態(tài)從執(zhí)行狀態(tài)TASK_RUNNING 變成睡眠狀態(tài)TASK_INTERRUPTIBLE绳姨。
1. 如果schedule()是被一個狀態(tài)為TASK_RUNNING 的進程調度登澜，那么schedule()將調度另外一個進程占用CPU，當前進程會進入就緒狀態(tài)飘庄，等待下次時間輪轉調度脑蠕。(運行結果會發(fā)現(xiàn)，執(zhí)行當前進程占用的時間會非常少跪削，因為一進來執(zhí)行到schedule就調度出去了空郊。)
2. 如果schedule()是被一個狀態(tài)為TASK_INTERRUPTIBLE 或TASK_UNINTERRUPTIBLE 的進程調度份招，這將導致正在運行的進程進入睡眠，因為它已經(jīng)不在運行狀態(tài)中了狞甚，被移到了等待狀態(tài)锁摔。（比如運行安裝一個驅動程序.ko，結果發(fā)現(xiàn)在用戶態(tài)執(zhí)行rmmod無法卸載哼审，因為執(zhí)行卸載的函數(shù)進程睡眠了谐腰。）
我們可以使用下面的這個函數(shù)將剛才那個進入睡眠的進程喚醒:
?wake_up_process(sleeping_task);
在調用了wake_up_process()以后，這個睡眠進程的狀態(tài)會被設置為TASK_RUNNING涩盾，而且調度器會把它加入到就緒狀態(tài)中去十气，等待運行。當然春霍，這個進程只有在下次被調度器調度到的時候才能真正地投入運行砸西。

注意：如果當前進程只設置了狀態(tài)，比如set_current_state(TASK_INTERRUPTIBLE)址儒，而沒有執(zhí)行調度（schedule()）芹枷，那么時間到達之后仍會將它添加到就緒狀態(tài)隊列，并重置set_current_state(TASK_RUNNING)莲趣。

3.1無效喚醒

設想有兩個進程 A和B鸳慈，A進程正在處理一個鏈表，它需要檢查這個鏈表是否為空喧伞，如果不空就對鏈表里面的數(shù)據(jù)進行一些操作走芋，同時B進程也在往這個鏈表添加節(jié)點。當這個鏈表是空的時候潘鲫，由于無數(shù)據(jù)可操作翁逞，這時A進程就進入睡眠，當B進程向鏈表里面添加了節(jié)點之后它就喚醒A進程溉仑，其代碼如下：
A進程：

1 spin_lock(&list_lock);
2 if(list_empty(&list_head)) {
3     spin_unlock(&list_lock);
4     set_current_state(TASK_INTERRUPTIBLE);
5     schedule();
6     spin_lock(&list_lock);
7 }
10 /* Rest of the code ... */
11 spin_unlock(&list_lock);

B進程：

spin_lock(&list_lock);
list_add_tail(&list_head,new_node);
spin_unlock(&list_lock);
wake_up_process(processa_task);

這里會出現(xiàn)一個問題熄攘，假如當A進程執(zhí)行到第3行后第4行前的時候，B進程被另外一個處理器調度投入運行彼念。在這個時間片內，B進程執(zhí)行完了它所有的指令浅萧，因此它試圖喚醒A進程逐沙，而此時的A進程還沒有進入睡眠，所以喚醒操作無效洼畅。在這之后吩案，A進程繼續(xù)執(zhí)行，它會錯誤地認為這個時候鏈表仍然是空的帝簇，于是將自己的狀態(tài)設置為TASK_INTERRUPTIBLE然后調用schedule()進入睡眠徘郭。由于錯過了B進程喚醒靠益，它將會無限期的睡眠下去，這就是無效喚醒問題残揉，因為即使鏈表中有數(shù)據(jù)需要處理胧后，A 進程也還是睡眠了。

3.2避免無效喚醒

如何避免無效喚醒問題呢抱环？我們發(fā)現(xiàn)無效喚醒主要發(fā)生在檢查條件之后和進程狀態(tài)被設置為睡眠狀態(tài)之前壳快， 本來B進程的wake_up_process()提供了一次將A進程狀態(tài)置為TASK_RUNNING 的機會，可惜這個時候A進程的狀態(tài)仍然是TASK_RUNNING镇草，所以wake_up_process()將A進程狀態(tài)從睡眠狀態(tài)轉變?yōu)檫\行狀態(tài)的努力 沒有起到預期的作用眶痰。要解決這個問題，必須使用一種保障機制使得判斷鏈表為空和設置進程狀態(tài)為睡眠狀態(tài)成為一個不可分割的步驟才行梯啤，也就是必須消除競爭條件產(chǎn)生的根源竖伯，這樣在這之后出現(xiàn)的wake_up_process ()就可以起到喚醒狀態(tài)是睡眠狀態(tài)的進程的作用了。找到了原因后因宇，重新設計一下A進程的代碼結構七婴，就可以避免上面例子中的無效喚醒問題了。
A進程:

1 set_current_state(TASK_INTERRUPTIBLE);
2 spin_lock(&list_lock);
3 if(list_empty(&list_head)) {
4 spin_unlock(&list_lock);
5 schedule();
6 spin_lock(&list_lock);
7 }
8 set_current_state(TASK_RUNNING);
9
10 /* Rest of the code ... */
11 spin_unlock(&list_lock);

可以看到羽嫡，這段代碼在測試條件之前就將當前執(zhí)行進程狀態(tài)轉設置成TASK_INTERRUPTIBLE了本姥，并且在鏈表不為空的情況下又將自己置為TASK_RUNNING狀態(tài)。這樣一來如果B進程在A進程進程檢查了鏈表為空以后調用wake_up_process()杭棵，那么A進程的狀態(tài)就會自動由原來TASK_INTERRUPTIBLE變成TASK_RUNNING婚惫，此后即使進程又調用了schedule()，由于它現(xiàn)在的狀態(tài)是TASK_RUNNING魂爪，所以仍然不會被從運行隊列中移出先舷，因而不會錯誤的進入睡眠，當然也就避免了無效喚醒問題滓侍。

3.3Linux內核的例子

在Linux操作系統(tǒng)中蒋川，內核的穩(wěn)定性至關重要，為了避免在Linux操作系統(tǒng)內核中出現(xiàn)無效喚醒問題撩笆，Linux內核在需要進程睡眠的時候應該使用類似如下的操作：

/* ‘q’是我們希望睡眠的等待隊列 */
DECLARE_WAITQUEUE(wait,current);
add_wait_queue(q, &wait);
set_current_state(TASK_INTERRUPTIBLE);
/* 或TASK_INTERRUPTIBLE */
while(!condition) /* ‘condition’ 是等待的條件*/
schedule();
set_current_state(TASK_RUNNING);
remove_wait_queue(q, &wait);

上面的操作捺球，使得進程通過下面的一系列步驟安全地將自己加入到一個等待隊列中進行睡眠：首先調用DECLARE_WAITQUEUE ()創(chuàng)建一個等待隊列的項，然后調用add_wait_queue()把自己加入到等待隊列中夕冲，并且將進程的狀態(tài)設置為 TASK_INTERRUPTIBLE 或者TASK_INTERRUPTIBLE氮兵。然后循環(huán)檢查條件是否為真：如果是的話就沒有必要睡眠，如果條件不為真歹鱼，就調用schedule()泣栈。當進程 檢查的條件滿足后，進程又將自己設置為TASK_RUNNING 并調用remove_wait_queue()將自己移出等待隊列。
?從上面可以看到南片，Linux的內核代碼維護者也是在進程檢查條件之前就設置進程的狀態(tài)為睡眠狀態(tài)掺涛，然后才循環(huán)檢查條件。如果在進程開始睡眠之前條件就已經(jīng)達成了疼进，那么循環(huán)會退出并用set_current_state()將自己的狀態(tài)設置為就緒薪缆，這樣同樣保證了進程不會存在錯誤的進入睡眠的傾向，當然也就不會導致出現(xiàn)無效喚醒問題颠悬。

4.總結

通過上面的討論矮燎，可以發(fā)現(xiàn)在Linux 中避免進程的無效喚醒的關鍵是在進程檢查條件之前就將進程的狀態(tài)置為TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE，并且如果檢查的條件滿足的話就應該將其狀態(tài)重新設置為TASK_RUNNING赔癌。這樣無論進程等待的條件是否滿足诞外， 進程都不會因為被移出就緒隊列而錯誤地進入睡眠狀態(tài)，從而避免了無效喚醒問題灾票。