目標
修改 linux kernel，在 kernel/sched.} 相關 scheduler 部分增加 Weighted Round-Robin scheduler、Shortest Job First scheduler 以及 Rate-monotonic scheduler。最後藉由 Project 1 的練習撰寫測試程序驗證 scheduler 是否符合預期結果。
修改檔案列表
|
|
特別注意到，若編譯環境為 x86_64 則需要額外修改 arch/x86/include/asm/unistd_64.h 複製 arch/x86/include/asm/unistd_32.h 增加的 syscall。 同理，增加自己定義的 syscall 時，需要修改 arch/x86 下的那三個檔案 (如果發現編譯 kernel 時，出現 WARNING: syscall NOT IMPLEMENTION. 大多數都是這個造成)。
在 include/linux/sched.h 中，增加 task 的成員變數，提供接下來針對 task 操作需要的參數，特別的是在 struct sched_rt_entity; 中，相較於一般資料結構的寫法，linux 採用倒過來將節點訊息放在資料內部中，利用 #define container_of(ptr, type, member) 取得物件訊息，這種寫法方便解決 task 在數個 scheduler 中轉換。
因為 syscall 的方式設定 task weighted，增加一個全區變數 int weighted_rr_time_slice;，每一次 syscall 去設定這一個全區變數值，然後 task 建立時，經過 sched_fork，直接利用被修改全區變數作為這一個 task 的 weight。若要特別針對 task 設定 weighted round-robin，在建立前都要呼叫 syscall 設定全區變數。
|
|
Part 1. Weighted Round-Robin Scheduler
enqueue_task_weighted_rr()
函數將會給予 task 和 rq，將 task 根據 rq 的資料結構重新將 task 放入。若按照list結構，直接模擬 queue 即可，由於 linux 提供 list 本身為雙向串列，直接加入尾端只需要 $\mathcal{O}(1)$ 時間。並且運行rq->weighted_rr.nr_running++;增加 rq 中的計數，隨後用來在回報該 scheduler 中有沒有存在 task 需要運行，方便在 $\mathcal{O}(1)$ 時間內完成，由於 Weighted round-robin 只需要確認 list 是否為空，那麼也可以利用 linux 提供的list_empty()確認。dequeue_task_weighted_rr()
當 task 完成任務時，都要呼叫update_curr_weighted_rr進行統計運行多久，並且更新與 task 相關的排程權重。接著將 task 從 rq 串列中移除，並且更新 scheduler 的 task 計數 (rq->weighted_rr.nr_running--;)。時間複雜度 $\mathcal{O}(1)$requeue_task_weighted_rr()
將一個 task 出列，在 Weighted round-robin 只需要直接對將task.weighted_rr_list_item移到串列最尾端，由於採用雙向串列，直接跟 scheduler 取得 list head (linux list 的 head 是不存放任何資訊) 直接加入尾端即可。時間複雜度 $\mathcal{O}(1)$yield_task_weighted_rr()
直接運行 \lstinline{requeue} 即可。pick_next_task_weighted_rr()
當最上層分配一段時間給 scheduler 運行，運行時會調用這個函數，並拿取要執行的 task，但並不用將其移除串列，並執行next->se.exec_start = rq->clock;紀錄 task 的開始運行時間，再呼叫void update_curr_weighted_rr(struct rq *)。若不更新時間，則計算的相對運行時間會錯誤。task_tick_weighted_rr()
當 scheduler 運行時，每隔一段固定的時間會呼叫此函數。若程序執行量超過 scheduler 的設定，則需要更新串列，特別注意到if (p->task_time_slice && --p->task_time_slice)在原本預設是unsigned int型態，處理不當會造成 overflow，另一種情況會是一開始 quantum 設定為 0 所導致。
需根據不同的 task 要補充不同的量p->weighted_time_slice，不只要讓這支程式重進進入串列，同時需要呼叫set_tsk_need_resched(p)(參考kernel/sched_rt.c代碼)，藉以重新呼叫pick_next_task_weighted_rr(struct rq*)，否則這支程序會運行到結束。
Part 2. Shortest Job First Scheduler
enqueue_task_weighted_rr()
與 Weighted round-robin 類似，利用 list 做插入排序，可以在最慘 $\mathcal{O}(n)$ 時間內維護一個優先權由高至低的 list。需要 task 時，直接將串列的首元素移除。dequeue_task_weighted_rr()
類同 Weighted round-robin。requeue_task_weighted_rr()
在最短工作優先排程中，由於 task 優先權會變動，不方便確定執行過一陣子的 task 要移動到哪裡，最簡單的實作方式採用dequeue後再一次enqueue。時間複雜度 $\mathcal{O}(n)$yield_task_weighted_rr()
直接運行 \lstinline{requeue} 即可。pick_next_task_weighted_rr()
類同 Weighted round-robin。task_tick_weighted_rr()
在最短工作優先排程中若按照 Weighted round-robin 的寫法且不補充 quantum，則會變成 non-preemptive SJF。相反地，若要實作 preemptive SJF，需要在check_preempt_curr_weighted_rr(struct rq*, struct task_struct*, int)檢查執行的程序是不是串列的首元素，意即是不是最高優先權，如果不是最高優先權，則呼叫resched_task()即可完成 (詳見 Bonus RMS 的寫法)。
Bonus RMS
額外增加 syscall，修改三個檔案 unistd_32.h, unistd_64.h, syscall_table_32.S。增加 Rate-monotonic scheduler 的額外週期 (period) 和 syscall 函數主題，修改兩個檔案 sched.h, sched.c。
程式碼細節 sched_weighted_rr.c
enqueue_task_weighted_rr
使用與最短工作優先排程相同寫法，但利用週期 (period) 進行由優先權高到低排序。check_preempt_curr_weighted_rr
週期程式可能會搶之前正在運行程式，若發現運行程式的優先權低於要進入排程器的程式優先權，呼叫resched_task()重新排程。- 其餘類同 SJF。
測試程序 test_rms.c
參考 Project 1 的寫法，linux 針對每一個 thread 有各自計時的計時器，當 thread 被 context-switch 時，計時器也會隨之停止。
利用 main thread 產生週期性程式，pthread_create 並不會馬上將 thread 立即執行，迫使 main thread 的方式使用 sleep(1)，以秒為單位產生週期性程式。由於要考慮週期程式的執行時間，又能在輸出緩衝區觀察順序關係，利用 thread 的計時器，盡可能接近 1ms 才進行一次印出，但這也會造成幾毫秒的誤差，對於一支程序一秒大約印出 1000 個字元，測試程式中，將連續相同字元計數，若相同字元取用四捨五入到秒才進行印出，計時誤差部分就不予輸出。
