CFS負責處理普通非實時進程, 這類進程是我們linux中最普遍的進程
CFS調度算法的思想
理想狀態下每個進程都能獲得相同的時間片，並且同時運行在CPU上，但實際上一個CPU同一時刻運行的進程只能有一個。也就是說，當一個進程占用CPU時，其他進程就必須等待。CFS為了實現公平，必須懲罰當前正在運行的進程，以使那些正在等待的進程下次被調度.
當在try_to_wake_up/wake_up_process和wake_up_new_task中喚醒進程時, 內核使用全局check_preempt_curr看看是否進程可以搶占當前進程可以搶占當前運行的進程. 請注意該過程不涉及核心調度器.
每個調度器類都因應該實現一個check_preempt_curr函數, 在全局check_preempt_curr中會調用進程其所屬調度器類check_preempt_curr進行搶占檢查, 對於完全公平調度器CFS處理的進程, 則對應由check_preempt_wakeup函數執行該策略.
新喚醒的進程不必一定由完全公平調度器處理, 如果新進程是一個實時進程, 則會立即請求調度, 因為實時進程優先極高, 實時進程總會搶占CFS進程.
在Linux中，僅等待CPU時間的進程稱為就緒進程，它們被放置在一個運行隊列中，一個就緒進程的狀 態標志位為TASK_RUNNING. 一旦一個運行中的進程時間片用完, Linux 內核的調度器會剝奪這個進程對CPU的控制權, 並且從運行隊列中選擇一個合適的進程投入運行.
當然，一個進程也可以主動釋放CPU的控制權. 函數schedule()是一個調度函數, 它可以被一個進程主動調用, 從而調度其它進程占用CPU. 一旦這個主動放棄CPU的進程被重新調度占用CPU, 那麼它將從上次停止執行的位置開始執行, 也就是說它將從調用schedule()的下一行代碼處開始執行.
有時候,進程需要等待直到某個特定的事件發生,例如設備初始化完成、I/O 操作完成或定時器到時等. 在這種情況下, 進程則必須從運行隊列移出, 加入到一個等待隊列中, 這個時候進程就進入了睡眠狀態.
Linux 中的進程睡眠狀態有兩種
一種是可中斷的睡眠狀態，其狀態標志位TASK_INTERRUPTIBLE.
可中斷的睡眠狀態的進程會睡眠直到某個條件變為真, 比如說產生一個硬件中斷、釋放進程正在等待的系統資源或是傳遞一個信號都可以是喚醒進程的條件.
另一種是不可中斷的睡眠狀態，其狀態標志位為TASK_UNINTERRUPTIBLE.
不可中斷睡眠狀態與可中斷睡眠狀態類似, 但是它有一個例外, 那就是把信號傳遞到這種睡眠 狀態的進程不能改變它的狀態, 也就是說它不響應信號的喚醒. 不可中斷睡眠狀態一般較少用到, 但在一些特定情況下這種狀態還是很有用的, 比如說: 進程必須等待, 不能被中斷, 直到某個特定的事件發生.
在現代的Linux操作系統中, 進程一般都是用調用schedule的方法進入睡眠狀態的, 下面的代碼演示了如何讓正在運行的進程進入睡眠狀態。
sleeping_task = current;
set_current_state(TASK_INTERRUPTIBLE);
schedule();
func1();
/* Rest of the code ... */
在第一個語句中, 程序存儲了一份進程結構指針sleeping_task, current 是一個宏，它指向正在執行的進程結構。set_current_state()將該進程的狀態從執行狀態TASK_RUNNING變成睡眠狀態TASK_INTERRUPTIBLE.
如果schedule是被一個狀態為TASK_RUNNING的進程調度，那麼schedule將調度另外一個進程占用CPU;
如果schedule是被一個狀態為TASK_INTERRUPTIBLE 或TASK_UNINTERRUPTIBLE 的進程調度，那麼還有一個附加的步驟將被執行：當前執行的進程在另外一個進程被調度之前會被從運行隊列中移出，這將導致正在運行的那個進程進入睡眠，因為它已經不在運行隊列中了.
當在try_to_wake_up/wake_up_process和wake_up_new_task中喚醒進程時, 內核使用全局check_preempt_curr看看是否進程可以搶占當前進程可以搶占當前運行的進程. 請注意該過程不涉及核心調度器.
我們可以使用wake_up_process將剛才那個進入睡眠的進程喚醒, 該函數定義在kernel/sched/core.c, line 2043.
int wake_up_process(struct task_struct *p)
{
return try_to_wake_up(p, TASK_NORMAL, 0);
}
在調用了wake_up_process以後, 這個睡眠進程的狀態會被設置為TASK_RUNNING，而且調度器會把它加入到運行隊列中去. 當然， 這個進程只有在下次被調度器調度到的時候才能真正地投入運行.
try_to_wake_up函數通過把進程狀態設置為TASK_RUNNING, 並把該進程插入本地CPU運行隊列rq來達到喚醒睡眠和停止的進程的目的.
例如: 調用該函數喚醒等待隊列中的進程, 或恢復執行等待信號的進程.
static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
該函數接受的參數有: 被喚醒進程的描述符指針(p), 可以被喚醒的進程狀態掩碼(state), 一個標志wake_flags，用來禁止被喚醒的進程搶占本地CPU上正在運行的進程.
try_to_wake_up函數定義在kernel/sched/core.c, line 1906
void wake_up_new_task(struct task_struct *p)
該函數定義在[kernel/sched/core.c, line 2421
](http://lxr.free-electrons.com/source/kernel/sched/core.c?v=4.6
)
之前進入睡眠狀態的可以通過try_to_wake_up和wake_up_process完成喚醒, 而我們fork新創建的進程在完成自己的創建工作後, 可以通過wake_up_new_task完成喚醒工作, 參見Linux下進程的創建過程分析(_do_fork/do_fork詳解)–Linux進程的管理與調度（八）
使用fork創建進程的時候, 內核會調用_do_fork(早期內核對應do_fork)函數完成內核的創建, 其中在進程的信息創建完畢後, 就可以使用wake_up_new_task將進程喚醒並添加到就緒隊列中等待調度. 代碼參見kernel/fork.c, line 1755
wake_up_new_task中喚醒進程時, 內核使用全局check_preempt_curr看看是否進程可以搶占當前進程可以搶占當前運行的進程.
check_preempt_curr(rq, p, WF_FORK);
函數定義在kernel/sched/core.c, line 905
void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
const struct sched_class *class;
if (p->sched_class == rq->curr->sched_class)
{
rq->curr->sched_class->check_preempt_curr(rq, p, flags);
}
else
{
for_each_class(class) {
if (class == rq->curr->sched_class)
break;
if (class == p->sched_class) {
resched_curr(rq);
break;
}
}
}
/*
* A queue event has occurred, and we're going to schedule. In
* this case, we can save a useless back to back clock update.
*/
if (task_on_rq_queued(rq->curr) && test_tsk_need_resched(rq->curr))
rq_clock_skip_update(rq, true);
}
幾乎在所有的情況下, 進程都會在檢查了某些條件之後, 發現條件不滿足才進入睡眠. 可是有的時候進程卻會在判定條件為真後開始睡眠, 如果這樣的話進程就會無限期地休眠下去, 這就是所謂的無效喚醒問題.
在操作系統中, 當多個進程都企圖對共享數據進行某種處理, 而最後的結果又取決於進程運行的順序時, 就會發生競爭條件, 這是操作系統中一個典型的問題, 無效喚醒恰恰就是由於競爭條件導致的.
設想有兩個進程A 和B, A 進程正在處理一個鏈表, 它需要檢查這個鏈表是否為空, 如果不空就對鏈表裡面的數據進行一些操作, 同時B進程也在往這個鏈表添加節點. 當這個鏈表是空的時候, 由於無數據可操作, 這時A進程就進入睡眠, 當B進程向鏈表裡面添加了節點之後它就喚醒A進程, 其代碼如下:
A進程:
spin_lock(&list_lock);
if(list_empty(&list_head))
{
spin_unlock(&list_lock);
set_current_state(TASK_INTERRUPTIBLE);
schedule();
spin_lock(&list_lock);
}
/* Rest of the code ... */
spin_unlock(&list_lock);
}
B進程:
spin_lock(&list_lock);
list_add_tail(&list_head, new_node);
spin_unlock(&list_lock);
wake_up_process(A);
這裡會出現一個問題，假如當A進程執行到第4行後第5行前的時候, B進程被另外一個處理器調度投入運行. 在這個時間片內, B進程執行完了它所有的指令, 因此它試圖喚醒A進程, 而此時的A進程還沒有進入睡眠, 所以喚醒操作無效.
在這之後, A進程繼續執行, 它會錯誤地認為這個時候鏈表仍然是空的, 於是將自己的狀態設置為TASK_INTERRUPTIBLE然後調用schedule()進入睡眠. 由於錯過了B進程喚醒, 它將會無限期的睡眠下去, 這就是無效喚醒問題, 因為即使鏈表中有數據需要處理, A進程也還是睡眠了.
如何避免無效喚醒問題呢?
我們發現無效喚醒主要發生在檢查條件之後和進程狀態被設置為睡眠狀態之前, 本來B進程的wake_up_process提供了一次將A進程狀態置為TASK_RUNNING的機會，可惜這個時候A進程的狀態仍然是TASK_RUNNING，所以wake_up_process將A進程狀態從睡眠狀態轉變為運行狀態的努力沒有起到預期的作用.
要解決這個問題, 必須使用一種保障機制使得判斷鏈表為空和設置進程狀態為睡眠狀態成為一個不可分割的步驟才行, 也就是必須消除競爭條件產生的根源, 這樣在這之後出現的wake_up_process就可以起到喚醒狀態是睡眠狀態的進程的作用了.
找到了原因後, 重新設計一下A進程的代碼結構, 就可以避免上面例子中的無效喚醒問題了.
A進程
set_current_state(TASK_INTERRUPTIBLE);
spin_lock(&list_lock);
if(list_empty(&list_head))
{
spin_unlock(&list_lock);
schedule();
spin_lock(&list_lock);
}
set_current_state(TASK_RUNNING);
/* Rest of the code ... */
spin_unlock(&list_lock);
可以看到，這段代碼在測試條件之前就將當前執行進程狀態轉設置成TASK_INTERRUPTIBLE了, 並且在鏈表不為空的情況下又將自己置為TASK_RUNNING狀態.
這樣一來如果B進程在A進程進程檢查了鏈表為空以後調用wake_up_process, 那麼A進程的狀態就會自動由原來TASK_INTERRUPTIBLE變成TASK_RUNNING, 此後即使進程又調用了schedule, 由於它現在的狀態是TASK_RUNNING, 所以仍然不會被從運行隊列中移出, 因而不會錯誤的進入睡眠，當然也就避免了無效喚醒問題.
在Linux操作系統中, 內核的穩定性至關重要, 為了避免在Linux操作系統內核中出現無效喚醒問題, 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創建一個等待隊列的項, 然後調用add_wait_queue()把自己加入到等待隊列中, 並且將進程的狀態設置為 TASK_INTERRUPTIBLE或者TASK_INTERRUPTIBLE.
然後循環檢查條件是否為真: 如果是的話就沒有必要睡眠, 如果條件不為真, 就調用schedule
當進程檢查的條件滿足後, 進程又將自己設置為TASK_RUNNING並調用remove_wait_queue將自己移出等待隊列.
從上面可以看到, Linux的內核代碼維護者也是在進程檢查條件之前就設置進程的狀態為睡眠狀態,
然後才循環檢查條件. 如果在進程開始睡眠之前條件就已經達成了, 那麼循環會退出並用set_current_state將自己的狀態設置為就緒, 這樣同樣保證了進程不會存在錯誤的進入睡眠的傾向, 當然也就不會導致出現無效喚醒問題.
內核中有很多地方使用了避免無效喚醒的時候, 最普遍的地方是內核線程的, 因為內核線程的主要功能是輔助內核完成一定的工作的, 大多數情況下他們處於睡眠態, 當內核發現有任務要做的時候, 才會喚醒它們.
下面讓我們用linux內核中的實例來看看Linux 內核是如何避免無效睡眠的, 我還記得2號進程吧, 它的主要工作就是接手內核線程kthread的創建, 其工作流程函數是kthreadd
代碼在kernel/kthread.c, kthreadd函數, line L514
for (;;) {
set_current_state(TASK_INTERRUPTIBLE);
if (list_empty(&kthread_create_list))
schedule();
__set_current_state(TASK_RUNNING);
spin_lock(&kthread_create_lock);
/* ==do_something start== */
while (!list_empty(&kthread_create_list)) {
struct kthread_create_info *create;
create = list_entry(kthread_create_list.next,
struct kthread_create_info, list);
list_del_init(&create->list);
spin_unlock(&kthread_create_lock);
create_kthread(create);
/* ==do_something end == */
spin_lock(&kthread_create_lock);
}
spin_unlock(&kthread_create_lock);
kthread_worker/kthread_work是一種內核工作的更好的管理方式, 可以多個內核線程在同一個worker上工作, 共同完成work的工作, 有點像線程池的工作方式.
內核提供了kthread_worker_fn函數一般作為 kthread_create或者 kthread_run函數的 threadfn 參數運行, 可以將多個內核線程附加的同一個worker上面，即將同一個worker結構傳給kthread_run 或者kthread_create當作threadfn的參數就可以了.
其kthread_worker_fn函數作為worker的主函數框架, 也包含了避免無效喚醒的代碼, kernel/kthread.c, kthread_worker_fn函數, line573, 如下所示
int kthread_worker_fn(void *worker_ptr)
{
/* ......*/
set_current_state(TASK_INTERRUPTIBLE); /* mb paired w/ kthread_stop */
if (kthread_should_stop()) {
__set_current_state(TASK_RUNNING);
spin_lock_irq(&worker->lock);
worker->task = NULL;
spin_unlock_irq(&worker->lock);
return 0;
}
/* ......*/
}
此外內核的__kthread_parkme函數中也包含了類似的代碼
通過上面的討論, 可以發現在Linux 中避免進程的無效喚醒的關鍵是
在進程檢查條件之前就將進程的狀態置為TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE
並且如果檢查的條件滿足的話就應該將其狀態重新設置為TASK_RUNNING.
這樣無論進程等待的條件是否滿足, 進程都不會因為被移出就緒隊列而錯誤地進入睡眠狀態, 從而避免了無效喚醒問題.
set_current_state(TASK_INTERRUPTIBLE);
spin_lock(&list_lock);
if(list_empty(&list_head))
{
spin_unlock(&list_lock);
schedule();
spin_lock(&list_lock);
}
set_current_state(TASK_RUNNING);
/* Rest of the code ... */
spin_unlock(&list_lock);
