學校課程/即時系統

即時系統 加入排程器

contents

  1. 1. 目標
    1. 1.1. 修改檔案列表
    2. 1.2. Part 1. Weighted Round-Robin Scheduler
    3. 1.3. Part 2. Shortest Job First Scheduler
    4. 1.4. Bonus RMS
      1. 1.4.1. 程式碼細節 sched_weighted_rr.c
      2. 1.4.2. 測試程序 test_rms.c
    5. 1.5. Github

目標

修改 linux kernel，在 kernel/sched.} 相關 scheduler 部分增加 Weighted Round-Robin scheduler、Shortest Job First scheduler 以及 Rate-monotonic scheduler。最後藉由 Project 1 的練習撰寫測試程序驗證 scheduler 是否符合預期結果。

修改檔案列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
.
├── README.md
├── arch
│   └── x86
│       ├── include
│       │   └── asm
│       │       ├── unistd_32.h
│       │       └── unistd_64.h
│       └── kernel
│           └── syscall_table_32.S
├── include
│   └── linux
│       ├── sched.h
│       └── syscalls.h
└── kernel
    ├── sched.c
    ├── sched_fair.c
    ├── sched_rt.c
    └── sched_weighted_rr.c

特別注意到，若編譯環境為 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 設定全區變數。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct sched_rt_entity {
    ...
    //+ RTS Proj2: weighted_rr
    struct list_head weighted_rr_list_item;
    ...
};
...
struct task_struct {
    ...
    //+ RTS Proj2: weighted_rr
    unsigned int task_time_slice;
    //+ RTS Proj2: weighted_rr_prio
    unsigned int weighted_time_slice;
    //+ RTS Proj2: bonus RMS
    int period;
    ...
};
...
//+ RTS Proj2: weighted_rr
extern int weighted_rr_time_slice;

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 個字元，測試程式中，將連續相同字元計數，若相同字元取用四捨五入到秒才進行印出，計時誤差部分就不予輸出。

Github

https://github.com/morris821028/hw-realtime-system