Linux喚醒搶占----Linux進程的管理與調度(二十三）

1. 喚醒搶占當在try_to_wake_up/wake_up_process和wake_up_new_task中喚醒進程時, 內核使用全局check_preempt_curr看看是否進程可以搶占當前進程可以搶占當前運行的進程. 請註意該過程不涉及核心調度器. 每個調度器類都因應該實現一個chec ...

1. 喚醒搶占

當在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進程.

2 Linux進程的睡眠

在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 ... */

3 linux進程的喚醒

當在try_to_wake_up/wake_up_process和wake_up_new_task中喚醒進程時, 內核使用全局check_preempt_curr看看是否進程可以搶占當前進程可以搶占當前運行的進程. 請註意該過程不涉及核心調度器.

3.1 wake_up_process

我們可以使用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，而且調度器會把它加入到運行隊列中去. 當然，這個進程只有在下次被調度器調度到的時候才能真正地投入運行.

3.2 try_to_wake_up

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

3.3 wake_up_new_task

void wake_up_new_task(struct task_struct *p)

該函數定義在kernel/sched/core.c, line 2421

之前進入睡眠狀態的可以通過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

3.4 check_preempt_curr

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);
}

4 無效喚醒

4.1 無效喚醒的概念

幾乎在所有的情況下, 進程都會在檢查了某些條件之後, 發現條件不滿足才進入睡眠. 可是有的時候進程卻會在判定條件為真後開始睡眠, 如果這樣的話進程就會無限期地休眠下去, 這就是所謂的無效喚醒問題.

在操作系統中, 當多個進程都企圖對共用數據進行某種處理, 而最後的結果又取決於進程運行的順序時, 就會發生競爭條件, 這是操作系統中一個典型的問題, 無效喚醒恰恰就是由於競爭條件導致的.

設想有兩個進程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進程繼續執行, 它會錯誤地認為這個時候鏈表仍然是空的, 於是將自己的狀態設置為TASK_INTERRUPTIBLE然後調用schedule()進入睡眠. 由於錯過了B進程喚醒, 它將會無限期的睡眠下去, 這就是無效喚醒問題, 因為即使鏈表中有數據需要處理, A進程也還是睡眠了.

4.2 無效喚醒的原因

如何避免無效喚醒問題呢?

我們發現無效喚醒主要發生在檢查條件之後和進程狀態被設置為睡眠狀態之前, 本來B進程的wake_up_process提供了一次將A進程狀態置為TASK_RUNNING的機會，可惜這個時候A進程的狀態仍然是TASK_RUNNING，所以wake_up_process將A進程狀態從睡眠狀態轉變為運行狀態的努力沒有起到預期的作用.

4.3 避免無效搶占

要解決這個問題, 必須使用一種保障機制使得判斷鏈表為空和設置進程狀態為睡眠狀態成為一個不可分割的步驟才行, 也就是必須消除競爭條件產生的根源, 這樣在這之後出現的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, 所以仍然不會被從運行隊列中移出, 因而不會錯誤的進入睡眠，當然也就避免了無效喚醒問題.

5 Linux內核的例子

5.1 一個最基本的例子

在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將自己的狀態設置為就緒, 這樣同樣保證了進程不會存在錯誤的進入睡眠的傾向, 當然也就不會導致出現無效喚醒問題.

內核中有很多地方使用了避免無效喚醒的時候, 最普遍的地方是內核線程的, 因為內核線程的主要功能是輔助內核完成一定的工作的, 大多數情況下他們處於睡眠態, 當內核發現有任務要做的時候, 才會喚醒它們.

5.2 2號進程的例子-避免無效搶占

下麵讓我們用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);

5.2 kthread_worker_fn

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函數中也包含了類似的代碼

6 總結

通過上面的討論, 可以發現在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);