心的距離

原文: Sleeping in the Kernel

在多處理器(SMP)和hyperthreading的時代，sleep_on()這個function已經無法保證其可靠性了。以下為讓一個process安全以及跨平台的sleep方式。

Linux kernel有好些時候一個process會需要wait，直到某些事情發生，或是process需要醒來做一些事情。

使用schedule()

ready-to-run的process是放在run queue裡，其state是TASK_RUNNING。當一個process的timeslice結束，scheduler就從這個queue裡挑另一個process，並把CPU allocate給他。這是用完CPU的case。

在timeslice還沒結束前，process也可自動放棄CPU--使用schedule()。這個function告訴scheduler，可以把 CPU給其他的process。當放棄CPU的這個process再一次的被scheduler選中，會從停下來的點繼續執行，也就是 schedule()的下一行。

通常process需要等待某些event發生才繼續，如初始化某個device後，I/O complete後，或者是timer expire。此即該process sleep on that event。process藉由schedule()來sleep，如下例

sleeping_task = current;
set_current_state(TASK_INTERRUPTIBLE);
schedule();
func1();
/* The rest of the code */

current是 kernel裡的一個macro，其型態為task_struct，通常的用法為struct task_struct *xxx = current。可把current想成是一個kernel的global symbol，以存取當前process的狀態。而set_current_state(TASK_INTERRUPTIBLE)就是設定該process的狀態為TASK_INTERRUPTIBLE，表示其等待某個event或resource，等到event發生或resource available，即可將狀態變為TASK_RUNNING，等待schedule (TASK_UNINTERRUPTIBLE表示有只能藉由kernel本身wake up)。而TASK_INTERRUPTIBLE是比較prefer的方式。

當設定成TASK_INTERRUPTIBLE後，schedule()就應該要schedule另一個process了。但這只有在原來的process state是TASK_RUNNING。怎麼說呢?

若state是TASK_INTERRUPTIBLE或是TASK_UNINTERRUPTIBLE，此時呼叫schedule()，會比state為TASK_RUNNING多做一件事: 移出run queue。移出run queue後，就不會再被schedule，即進入sleep。換言之，TASK_RUNNING只是立刻放棄CPU，等待下一個timeslice的來臨，本身還是在run queue的，並沒有進到sleep。

wakeup

wake_up_process(sleeping_task);

這個動作就是把state設定TASK_RUNNING後，放進run queue。

Lost Wake-Up Problem

通常process檢查完某些條件後，決定進入sleep。而Lost Wake-Up Problem就發生在當process處於這種條件式sleep的race condition。舉例如下:

process A是consumer，而process B是feeder。當list為空，則A睡覺。當B餵東西時，叫醒A。

Process 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  }
8
9  /* Rest of the code ... */
10 spin_unlock(&list_lock);

Process B:
100  spin_lock(&list_lock);
101  list_add_tail(&list_head, new_node);
102  spin_unlock(&list_lock);
103  wake_up_process(processa_task);

問題發生在當A執行完第3行後，CPU被搶走，此時B執行所有的code，包括 wake_up_process。然後回到A，A執行第4行，把自己設為TASK_INTERRUPTIBLE後，離開run_queue，儘管此時B已經餵了。因此修改如下:

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

在測試條件前，先設定state，若條件不成立，再重設state。這樣就可保證當wake_up_process被呼叫時，被叫起的process還沒執行scheule(表示他還沒睡)，則其狀態會被重設為TASK_RUNNING。此時執行schedule()只是放棄了CPU，還是可在run queeu裡等待下一次schedule。

以下是實例: 2.6.11/kernel/sched.c: 4254

4253  /* Wait for kthread_stop */
4254  set_current_state(TASK_INTERRUPTIBLE);
4255  while (!kthread_should_stop()) {
4256          schedule();
4257          set_current_state(TASK_INTERRUPTIBLE);
4258  }
4259  __set_current_state(TASK_RUNNING);
4260 return 0;

條件為kernel_should_stop()，在檢查之前已將state設定TASK_INTERRUPTIBLE。因此，在條件檢查後的wakeup event不會lost。