一覧OS-06-1 · スケジューリング

FCFSとラウンドロビンスケジューリング

同じCPU処理を二つの方針で実行し、最初の応答・完了・待ち時間を計算します。

説明

CPUが一つなら、実行可能な仕事が複数あっても、同時に実行できるのは一つです。スケジューラは次に実行する仕事を選び、必要に応じて実行中の仕事からCPUを取り上げます。

Aは6 ms、Bは2 ms、Cは1 msのCPU処理を必要とし、すべて時刻0に到着するとします。I/O待ちはありません。先着順ではA・B・Cの順、ラウンドロビンでは一定時間ずつ交替させ、同じ仕事の応答時間と完了時刻を比べます。

1仕事とCPU時間

仕事名と必要なCPU時間を辞書へ入れます。このモデルでは到着順が辞書の並びA・B・Cと同じです。

jobs = {'A': 6, 'B': 2, 'C': 1}仕事とCPU時間; print(jobs)入力条件; print(sum(jobs.values()))総CPU時間

合計は9 msです。順番を変えても必要なCPU処理の合計は同じです。これから計算する完了時刻や応答時間は、どの仕事をいつ実行したかによって変わります。

2先着順の実行区間

先着順では仕事を途中で交替させず、順に終了まで実行します。開始・終了時刻を累積します。

def fcfs(work):先着順の計算 t = 0; trace = []時刻と記録を初期化 for name, length in work.items():入力順に選ぶ trace.append((name, t, t + length)); t += length区間を記録して時刻を進める return trace時系列を返す

区間は(仕事名, 開始, 終了)で保存します。終了時刻と次の開始時刻が同じでも、境界の瞬間を二重に実行するという意味ではありません。区間の終端を含まない表し方です。

3長い仕事の後で待つ時間

先着順の記録を出し、開始時刻を平均します。全件が時刻0に来て途中で交替しないため、開始時刻が待ち時間と最初の応答時間に一致します。

fifo = fcfs(jobs)先着順を計算; print(fifo)実行区間; print(sum(start for _, start, _ in fifo) / len(fifo))平均待ち時間

Aは0〜6、Bは6〜8、Cは8〜9 msです。平均待ち時間は約4.67 msで、1 msで終わるCも8 ms待ちます。短い仕事が長い仕事の後ろで待つ状態が分かります。

4時間片ごとの交替

ラウンドロビンは先頭の仕事を時間片qまで実行し、残りがあれば列の末尾へ戻します。到着はすべて時刻0に済んでいる条件です。

def rr(work, q):ラウンドロビン from collections import deque実行待ちの列 queue = deque(work); left = dict(work); t = 0; trace = []残時間と記録 while queue:仕事が残る間 name = queue.popleft(); run = min(q, left[name])先頭へ時間片を割り当てる trace.append((name, t, t + run)); t += run; left[name] -= run実行区間と残時間 if left[name]: queue.append(name)未完了なら末尾へ return trace時系列を返す

残り時間が0になった仕事は列へ戻しません。実際のOSではI/O待ちや新規到着も列を変えますが、この例では時間片の効果に絞っています。

52 msずつ実行した結果

q=2で実行します。仕事ごとの最初の開始時刻と最後の終了時刻を求めます。

trace = rr(jobs, 2)時間片2で実行; first = {n: min(s for x,s,e in trace if x==n) for n in jobs}最初の実行時刻; end = {n: max(e for x,s,e in trace if x==n) for n in jobs}完了時刻; print(trace); print(first); print(end)区間・応答・完了

最初の応答はA=0、B=2、C=4 msです。完了はA=9、B=4、C=5 msで、BとCが早く応答・完了する代わりにAの完了は遅れます。最後のAの二つの区間には他の仕事が挟まっていません。

6応答時間と待ち時間

待ち時間は完了までの9・4・5 msから、それぞれのCPU時間6・2・1 msを引いて求めます。I/O待ちがない条件での計算です。

waiting = {n: end[n] - jobs[n] for n in jobs}総待ち時間; print(waiting)仕事別の値; print(sum(first.values())/3, sum(waiting.values())/3)平均応答と平均待ち

待ちはA=3、B=2、C=4 ms、平均3 msです。平均応答時間は2 msです。実行が何度も中断されると、最初にCPUを得るまでの応答時間と、全区間で待った合計は一致しません。

7交替にかかる時間

時間片1と2の記録で、実行する仕事名が変わる境界だけを数えます。交替1回に0.1 msかかるとし、処理時間9 msに加えます。

for q in (1,2):時間片を二通りに tr = rr(jobs,q)実行記録; switches = sum(a[0]!=b[0] for a,b in zip(tr,tr[1:]))仕事名が変わる回数; print(q, switches, round(9+switches*0.1,1))時間片・交替回数・総時間

時間片1では5回・9.5 ms、2では3回・9.3 msです。時間片の境界でも同じ仕事が続く箇所は数えていません。この計算では初回の開始や最後の終了処理の費用を除き、仕事間の交替費用だけを足しています。

8中断した仕事の実行位置を保存

コンテキスト切替では実行位置やレジスタを保存し、再開時に戻します。Aが2命令進んだ後、Bへ切り替える簡単な状態表を使います。

saved = {'A': {'PC': 0x1008, 'r0': 2}, 'B': {'PC': 0x2000, 'r0': 0}}仕事ごとの保存状態; cpu = dict(saved['B'])Bを復元; print(hex(cpu['PC']), cpu['r0'])Bの状態; cpu = dict(saved['A'])Aを復元; print(hex(cpu['PC']), cpu['r0'])Aの再開位置

Bは0x2000・r0=0、Aの再開は0x1008・r0=2です。Aを先頭からやり直すのではなく、保存した状態を復元して続けます。実際の保存対象はCPUやOSの実装によって増えます。

まとめ

実行順の変更で総CPU時間が同じでも応答・完了・待ち時間は変わります。

ラウンドロビンは短い時間片で早い応答を得やすい一方、交替費用との兼ね合いがあります。

中断した仕事は実行状態を保存し、再開時に復元します。

操作履歴と解説を振り返れます。

Python 3

1
jobs = {'A': 6, 'B': 2, 'C': 1}; print(jobs); print(sum(jobs.values()))
{'A': 6, 'B': 2, 'C': 1}
9
2
def fcfs(work): t = 0; trace = [] for name, length in work.items(): trace.append((name, t, t + length)); t += length return trace
3
fifo = fcfs(jobs); print(fifo); print(sum(start for _, start, _ in fifo) / len(fifo))
[('A', 0, 6), ('B', 6, 8), ('C', 8, 9)]
4.666666666666667
4
def rr(work, q):
 from collections import deque
 queue = deque(work); left = dict(work); t = 0; trace = []
 while queue:
  name = queue.popleft(); run = min(q, left[name])
  trace.append((name, t, t + run)); t += run; left[name] -= run
  if left[name]: queue.append(name)
 return trace
5
trace = rr(jobs, 2); first = {n: min(s for x,s,e in trace if x==n) for n in jobs}; end = {n: max(e for x,s,e in trace if x==n) for n in jobs}; print(trace); print(first); print(end)
[('A', 0, 2), ('B', 2, 4), ('C', 4, 5), ('A', 5, 7), ('A', 7, 9)]
{'A': 0, 'B': 2, 'C': 4}
{'A': 9, 'B': 4, 'C': 5}
6
waiting = {n: end[n] - jobs[n] for n in jobs}; print(waiting); print(sum(first.values())/3, sum(waiting.values())/3)
{'A': 3, 'B': 2, 'C': 4}
2.0 3.0
7
for q in (1,2):
 tr = rr(jobs,q); switches = sum(a[0]!=b[0] for a,b in zip(tr,tr[1:])); print(q, switches, round(9+switches*0.1,1))
1 5 9.5
2 3 9.3
8
saved = {'A': {'PC': 0x1008, 'r0': 2}, 'B': {'PC': 0x2000, 'r0': 0}}; cpu = dict(saved['B']); print(hex(cpu['PC']), cpu['r0']); cpu = dict(saved['A']); print(hex(cpu['PC']), cpu['r0'])
0x2000 0
0x1008 2
演習完了