[Scheduler] Before Schedule Takes Place

專門用語：

• 使用打字機（Courier New）字體表示原始碼。
• task/process即為Linux中的thread。
• 文中的Linux與Linux kernel指的皆為作業系統核心。
  
• 使用斜體字型標示Linux中的資料結構，macro，變數或函式名稱。
• PID即為TID。
  

Kernel版本：

• v2.6.24.3
  

假設我們遇到的是一般task，在schedule暫停current task並讓原本暫停中的task成為current task之前會呼叫put_prev_task_fair函式將current task¹讓出CPU的使用權，如果current task已執行完畢就會被從runqueue移除，否則重新放回runqueue等待下次輪到它使用CPU繼續執行。

static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
{
       struct sched_entity *se = &prev->se;
       struct cfs_rq *cfs_rq;

       for_each_sched_entity(se) {
               cfs_rq = cfs_rq_of(se);
               put_prev_entity(cfs_rq, se);
       }
}

這裡出現新的struct，一個名為sched_entity，這個struct跟sched_class一樣屬於task_struct的一個欄位，主要用來紀錄可以被schedule的task在執行時間方面的相關資訊與維持紅黑樹架構的rb_node；另一個名為cfs_rq²，cfs_rq是runqueue中用來處理fairness的一個欄位。put_prev_entity函式主要是將原本指到current task的指標（cfs_rq->curr）設為NULL，在此之前如果發現current task還沒有執行完畢³的話便將代表current task的schedule entity重新放回runqueue等待下次被scheduler挑選出來執行。

當current task讓出CPU使用權之後kernel的工作便是從runqueue中挑選出一個task讓它成為下一個current task，這個動作透過pick_next_task函式呼叫pick_next_task_fair函式完成。pick_next_task_fair函式呼叫__pick_next_entity函式從cfs_rq中將最左邊的schedule entity挑選為下一個current task。

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
       struct sched_entity *se = NULL;

       if (first_fair(cfs_rq)) {
               se = __pick_next_entity(cfs_rq);
               set_next_entity(cfs_rq, se);
       }

       return se;
}

確認新選出的current task與原本的current task並不是同一個task之後便呼叫context_switch函式備份原task的狀態並還原新task的狀態，待備份還原狀態完成之後便直接開始執行新的current task。

看到這裡大家應該都會有一些共同的疑問，例如，kernel是以什麼原則為依據將task放入cfs_rq的樹狀結構中，以及在current task沒有遭到preempt的狀況下kernel怎麼知道該呼叫schedule函式讓其他task也有機會執行。我會在下一篇文章中試著以我理解的程度解釋這些疑點。



1 current task指的是CPU正在執行的task。
2 cfs為complete fair scheduler的縮寫。
3 schedule entity中on_rq欄位的值為1。