RM と EDF を awk で実装する
代表的なハードリアルタイムスケジューリングアルゴリズムである RM ( Rate Monotonic ) と EDF ( Earliest Deadline First ) を awk で実装してみた。
https://sourceforge.net/projects/rmvsedf/
git clone git://git.code.sf.net/p/rmvsedf/code rmvsedf-code
スケジューリングの勉強をしている方なら経験があるかもわからないが、意外と良いタスクセットの例を作るのが難しい。方眼紙やエクセルでスケジューリングの例を作っては、「意図通りに振る舞ってくれなかった」「実はスケジュール可能じゃなかった」と気づくことが多く、時間の無駄である。
$ cat ./samples/task_set2.txt
# RM ... miss
# EDF ... schedulablet1 = { 2, 5 }
t2 = { 4, 7 }
こんなタスクセットに対して、
$ awk -f ./sched.awk ./samples/task_set2.txt | awk -f show.awk
t1 = { 2, 5 }
t2 = { 4, 7 }
Utilization U = 0.971429t1 : |X X _ _ _|X X _ _ _|X X _ _ _|X X _ _ _|X X _ _ _|X X _ _ _|X X _ _ _|X _ _
t2 : |_ _ X X X _ _|X X X _ _ X _|X _ _ X X X _|_ X X X _ _ X|X X _ _ X X _|_ _ _
: ^
: |
: +--- DEADLINE MISS at period 7
RM だとスケジュール出来ないが、
hal@cobich-VAIO ~/src/rmvsedf-code
$ awk -f ./sched.awk -v edf=1 ./samples/task_set2.txt | awk -f show.awk
t1 = { 2, 5 }
t2 = { 4, 7 }
Utilization U = 0.971429t1 : |X X _ _ _|_ X X _ _|_ _ X X _|X X _ _ _|X X _ _ _|_ X X _ _|X X _ _ _|X _
t2 : |_ _ X X X X _|_ X X X X _ _|X _ _ X X X _|_ X X X X _ _|X X _ _ X X _|_ _
EDF だとスケジュール可能。
この例は Buttazzo の Hard Real-Time Computing Systems 3rd Edition の Figure-4.13 から拝借した。
