優先度スケジューリングと処理期限
固定優先度と待ち時間による補正を比較し、期限に間に合う実行順を計算します。
説明
優先度は、実行可能な仕事の中から何を先に選ぶかを決める条件です。高優先度の仕事が続くと低優先度の仕事が待ち続ける場合があります。期限付きの仕事では、優先度だけでなく「いつまでに終えるか」も判断材料になります。
1 msの仕事が続けて到着する列を使い、固定優先度とエージングを比べます。次にロックによる優先度逆転を時系列で確認し、最後に同時到着した二つの仕事の完了時刻を期限と照合します。すべて単一CPUでのモデルです。
1優先度で仕事を並べる
この教材では数字の大きい方を高優先度と定義します。L=1、M=2、H=3を高い順に並べます。
priority = {'L': 1, 'M': 2, 'H': 3}このモデルの優先度; print(sorted(priority, key=priority.get, reverse=True))高い順に並べるH、M、Lの順です。優先度の数値の向きは仕組みによって異なります。例えばLinuxのnice値は小さい方が優遇されるので、この表の数値をそのままnice値として使うことはできません。
2到着と待ち時間を含む選択
Lは時刻0から待ち、各時刻に1 msで終わるHが一つ到着します。aging=Trueなら待ち2 msごとに有効優先度を1増やします。同点なら先に到着した仕事を選びます。
def schedule(aging):選択規則
queue = [('L',0,1)]; trace = []Lの到着と記録
for t in range(8):8 msを計算
queue.append(('H'+str(t),t,3))高優先度の仕事が到着
chosen = min(queue, key=lambda j: (-(j[2]+((t-j[1])//2 if aging else 0)),j[1]))有効優先度と到着時刻で選ぶ
queue.remove(chosen); trace.append((t,chosen[0]))選んだ仕事を1 ms実行
return trace選択結果固定優先度とエージングで変えるのは選択式だけです。全仕事は1 msで完了し、処理途中の中断はありません。経過時間による補正を含め、採用する規則を関数にしています。
3固定優先度で待ち続ける仕事
補正なしで8 msの実行記録を作り、Lが実行されたかを調べます。
fixed = schedule(False)固定優先度; print(fixed)時刻ごとの仕事; print(any(name=='L' for _,name in fixed))Lに実行機会があるか毎回Hが選ばれ、Lは一度も実行されません。この到着が無期限に続くならLは待ち続けます。有限の8 msの出力だけで永久の待ちを観測したわけではなく、同じ条件が続く規則から導いています。
4待ち時間で優先度を補正
エージングを有効にし、同じ到着列を計算します。
aged = schedule(True)待ち時間を優先度に反映; print(aged)同じ到着列の実行順; print([t for t,name in aged if name=='L'])Lの開始時刻Lは時刻4に選ばれます。有効優先度が1+4÷2=3となり、その時刻に到着したH4と同点なので先着のLが優先されます。どの程度待たせるかは補正幅や間隔、同点時の規則に依存します。
5ロックによる優先度逆転
時刻1でHが、Lの持つロックを待つ場面を考えます。Lには解放まで2 msの処理が残り、無関係なMが4 ms動けます。Lの優先度をそのままにする場合と、待つHの優先度を引き継ぐ場合を計算します。
blocked_at = 1Hが待ち始める時刻; no_inherit = [('M',4),('L',2),('H',1)]継承なしの順序; inherit = [('L',2),('H',1),('M',4)]Lが優先度を継承; print(blocked_at+sum(n for name,n in no_inherit[:2]))MとLが終わる時刻; print(blocked_at+inherit[0][1])Lの解放時刻ロックを取得できる時刻は継承なしで7、ありで3です。高優先度Hが直接Mより優先されても、ロックを持つLがMに押しのけられるとHも待ちます。優先度継承はLを一時的に高くして解放を進めますが、ロック処理そのものの時間を消す仕組みではありません。
6完了時刻と期限を比較する関数
次は時刻0に到着するA・Bです。Aは3 ms必要で期限7、Bは2 ms必要で期限3です。各仕事が終了した時刻と期限を比較する関数を作ります。
def deadlines(order, work):指定順で完了を計算
t = 0; rows = []開始時刻
for name in order:順番に実行
cost, due = work[name]; t += cost; rows.append((name,t,due,t<=due))完了時刻と期限内判定
return rows結果表最後のTrue・Falseは期限内に終わったかを表します。締切ちょうどの完了も期限内としています。到着は同時で、依存関係やI/O待ち、交替費用はない条件です。
7期限の近い仕事を先にする
入力順A・Bと、期限の近い順B・Aを比較します。この同時到着の例では、期限順がEDFの選択と一致します。
work = {'A':(3,7),'B':(2,3)}CPU時間と期限; print(deadlines(list(work),work))入力順; order = sorted(work,key=lambda n:work[n][1])期限順; print(deadlines(order,work))順序変更後A・BではBが時刻5に終わり、期限3を超えます。B・AではB=2、A=5で両方期限内です。総CPU時間は5 msのままで、順序変更が期限達成を変えています。
8順序を変えても足りないCPU時間
Bの処理を4 msへ増やし、期限3は保ちます。期限順でもB単独の要求を満たせるか調べます。
overloaded = {'A':(3,7),'B':(4,3)}Bの必要時間を増やす; print(deadlines(['B','A'],overloaded))期限順の結果; print(overloaded['B'][0] > overloaded['B'][1])単独の時間不足Bは時刻4に終わり、期限3を超えます。単独でも必要時間4が期限までの3より長いため、順序変更だけでは解決できません。優先度を上げることと、処理能力や実行時間を確保することは別の対策です。
まとめ
固定優先度では到着条件によって待ち続ける仕事が生じ、エージングは待ち時間を選択へ反映します。
高優先度の仕事がロックを待つ場合、ロック保持者の実行も進める必要があります。
期限の近い仕事を先にしても、必要なCPU時間自体が不足すれば期限を守れません。
操作履歴と解説を振り返れます。
Python 3
priority = {'L': 1, 'M': 2, 'H': 3}; print(sorted(priority, key=priority.get, reverse=True))['H', 'M', 'L']
def schedule(aging):
queue = [('L',0,1)]; trace = []
for t in range(8):
queue.append(('H'+str(t),t,3))
chosen = min(queue, key=lambda j: (-(j[2]+((t-j[1])//2 if aging else 0)),j[1]))
queue.remove(chosen); trace.append((t,chosen[0]))
return tracefixed = schedule(False); print(fixed); print(any(name=='L' for _,name in fixed))[(0, 'H0'), (1, 'H1'), (2, 'H2'), (3, 'H3'), (4, 'H4'), (5, 'H5'), (6, 'H6'), (7, 'H7')] False
aged = schedule(True); print(aged); print([t for t,name in aged if name=='L'])[(0, 'H0'), (1, 'H1'), (2, 'H2'), (3, 'H3'), (4, 'L'), (5, 'H4'), (6, 'H5'), (7, 'H6')] [4]
blocked_at = 1; no_inherit = [('M',4),('L',2),('H',1)]; inherit = [('L',2),('H',1),('M',4)]; print(blocked_at+sum(n for name,n in no_inherit[:2])); print(blocked_at+inherit[0][1])7 3
def deadlines(order, work):
t = 0; rows = []
for name in order:
cost, due = work[name]; t += cost; rows.append((name,t,due,t<=due))
return rowswork = {'A':(3,7),'B':(2,3)}; print(deadlines(list(work),work)); order = sorted(work,key=lambda n:work[n][1]); print(deadlines(order,work))[('A', 3, 7, True), ('B', 5, 3, False)]
[('B', 2, 3, True), ('A', 5, 7, True)]overloaded = {'A':(3,7),'B':(4,3)}; print(deadlines(['B','A'],overloaded)); print(overloaded['B'][0] > overloaded['B'][1])[('B', 4, 3, False), ('A', 7, 7, True)]
True演習完了