Process Scheduling
Linux Kernel is a multi-tasking kernel，由process scheduler協調process執行share CPU equally among all currently running process，pick appropriate process to run next if required,considering scheduling class/policy and process priorities balance process between multiple core in SMP system
task_struct 包含所有Linux task所有資訊 (完整程式碼請見：task_struct)
#define 用來定義的，而#undef 是用來消除定義
例如:
#define TURBOC
int main()
{
#ifdef TURBOC (因為上頭有定義TURBOC所以此條件成立)
printf("Borland C compiler.\n");
#endif (結束#ifdef)
#undef TURBOC (消除TURBOC定義)
#ifndef TURBOC (因為TURBOC沒被定義所以此條件成立)
printf("MircoSoft C compiler.\n");
#endif (結束#ifdef)
}
執行結果 :
Borland C compiler.
MircoSoft C compiler.
Task Classification(分類)
CPU Bound & I/O Bound
有些Thread花很多時間在CPU運算上面，有些thread花很多時間在等待相對比較慢的I/O運算。I/O運算主要是在等待使用者輸入、硬體和網路傳輸。
Scheduler需要回應I/O Bound工作和有效率的CPU Bound，如果tasks run在longer period time，可以完成比較多工作但是反應較慢。如果task run在short period time，可以較快速反應I/O事件但花很多時間在task switches，所以scheduler需要平衡兩種情境。
- Real Time & Normal
- Priority
- Scheduling Classes
Linux scheduler是模組化的，不同的工作啟用不一樣的演算法。所有的algo 包在sched_class中(Kernel/sched/sched.h) (完整程式碼請看：sched_class)
stop_sched_class→deadline_sched_class→ rt_sched_class → fair_sched_class → idle_sched_class → NULL
- stop_sched_class:常用於每個CPU要停止task當插隊的task做任何事和停止被插隊的task
- idle_sched_class:使用在每個CPU沒其他task在run的時候
- rt_sched_class & fair_sched_class:用在real time 和 normal task
- deadline_sched_class:主要用於有時間限制的task
- SCHED_NORMAL (也稱為SCHED_OTHER): 主要用以排程一般目的的Task。
- SCHED_BATCH: 主要用以讓Task可以延長執行的時間(Time Slice),減少被中斷發生Task Context-Switch的次數.藉此可以提高 Cache的利用率 (每次Context-Switch都會導致Cache-Flush). 比較適合用在固定週期執行的Batch Jobs任務主機上,而不適合用在需要使用者互動的產品 (會由於Task切換的延遲,而感覺到系統效能不佳或是反應太慢).
- Real-Time Scheduler Class (實作在檔案 sched_rt.c中):
- 支援Real-Time Task的排程,包括有SCHED_FIFO與SCHED_RR. (SCHED_RR task預設的 Time Slice長度為100 msecs.).
- Idle Task Scheduler Class (實作在檔案 sched_idletask.c中):
- 支援SCHED_IDLE,為系統中的Idle Task排程.
- Stop Scheduler Class (實作在檔案 sched_stoptask.c中):屬於 Stop-Task Scheduling Class的Task是屬於系統中最高權限的Task,會中斷所有任務的執行,並且不會被其他任務所中斷.
- 追蹤所有可執行的工作並分配到特定的CPU
- 管理各個棑程，使CPU的附載達到平衡
- lock同步排程運算：raw_spinlock_t lock;
- pointer currently running,idle和stop到task_struct struct task_struct *curr, *idle, *stop;
目前系統中,Scheduling Class的優先級順序為 Stop-Task > Real-Time > Fair > Idle-Task,開發者可以根據自己的設計需求,來把所屬的Task配置到不同的Scheduling Class中.
Main Runqueue
(關於 runqueue程式碼請看：struct_rq)
Scheduler Skeleton
- (關於__schedule()程式碼說明請看：__schedule())
- 找下一個要執行的工作
- 分配下一個要執行的工作到(next)變數
- 對新工作做context switch
- schedule function 會呼叫 preempt_disable()來關閉插隊狀態
- 當前的CPU只允許一個thread在同一時間修改run queue
- schedule function在prev檢查先前執行task的狀態。如果該task沒在運作和被插隊的task沒在kernel mode，則該task會被移除出run queue
- 如果task是non blocked且在等待，會改成TASK_RUNNING狀態且離開run queue
- remove process會呼叫 deactivate_task()函數內部的dequeue_task()
- 相對應的class pick_next_task() 是挑選適合的process到CPU的排程內，當發現大多數的process都在fair_sched_class，則會直接呼叫這個function (關於pick_next_task()程式碼請看：pick_next_task())
- need_resched 是一個flag，會定期的檢查kernel，會告訴kernel哪些process先run，且schedule()應該快速執行。
- 最後，reay queue 會解鎖而插隊的狀態會開啟，如果有process再次發出插隊請求，schedule() function再次被執行
- 規律的時間更新正確的scheduled process scheduler_tick()，這個function會定期的呼叫interrupt，目的為對正確的runnung process更新ready queue的clock、CPU 讀取和執行時間的記數。 (關於scheduler_tick()程式碼請看：scheduler_tick())
- 正確的讓執行中的process go to sleep (include/linux/wait.h, line 468)，Linux kernel是multiple的且當有特定事件發生時，process會去sleep。如果要讓事件不立即發生，會呼叫schedule() function和go to sleep，會把task從ready queue移除。當條件成立時，task才會離開wait queue讓睡著的task wack up try_to_wake_up
- 這個function通常為呼叫wake_up() function，主要是做三件事情
- 把task叫醒讓他回到ready queue
- 設定TASK_RUNNING來喚醒task
- 如果被喚醒的task 優先權比正在running的task還要高，會設定need_resched來引用schedule()
- 公式一:vruntime-"cfs_rq→min_vruntime"
- 公式二:vruntime+=(Delta_exec*NICE_0_LOAD)/(se_load.weight)
- 公式三:(CPU真正的工作時間)Delta_exec= (se_load.weight*period)/(cfs_rq→load.weight)
ready-to-run 的process是放在run queue裡面，當Linux kernel is preemptive，低優先權的task會強迫被高優先權的task插隊，那些被插隊的task放在unfinished kernel space 須等下次的scheduled才能繼續。
有三個主要場合會呼叫schedule()
在一些初始化檢查和一些SMP ，會呼叫ttwu_queue() function(kernel/sched/core.c, line 1621)
來確實喚醒工作。這個function會lock ready queue，接下來呼叫ttwu_do_activate()這個function。ttwu_do_activate()這個function接著會呼叫enqueue_task()所對應的scheduling class並put task到ready queue中。
ttwu_do_wakeup()這個function會檢查在ready queue中需要被插隊的task並喚醒他，check_preempt_curr這個function會呼叫對應的schedule class並可能會設定內部的need_resched()這個flag，之後，當完成wack up 這個process之後，該task的狀態會設定成TASK_RUNNING。
Completely Fair Scheduler (CFS)
定義:不再區分interactive process，而將所有行程公平對待，讓所有工作平等被執行
實作理論:每次的排成選取"目前獲得CPU執行時間最少的工作(time slice)"，並且使用紅黑樹演算法依CPU時間做排序
實際運作:為了避免發生data overflow,真正的紅黑樹鍵值會先減去所有等待的工作中已使用的最小CPU時間,因此真正的鍵值:
總結:CFS的排程主要由vruntime所決定，而vruntime的運算則又受到權重值等因素影響，在將公式 二和公式三合併後可得公式四: vruntime+= (period*常數)/(cfs_rq→load.weight)，由公式四可看出，實際上影響vruntime的相關參數為目前排程的工作數及其所相對應的權重值和，因此，每個工作每次將增加相同的vruntime，看起來相當公平，但事實上，由於vruntime並不是真正獲得的CPU工作時間，而是依照當前工作的權重值來調整vruntime和真正CPU工作時間的比例，所以雖增加相同的vruntime，但實際上權重值大的工作是可以獲得較多的CPU真正工作時間的，也因此可以對優先權較高的工作進行偏袒，雖然CFS標榜完全公平，但事實上對各個不同的優先權工作仍是有所區別的。
沒有留言:
張貼留言