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

CPU処理とI/O待ち

状態別の時間を集計し、CPUとI/Oのどちらを短縮すると完了が早まるかを計算します。

説明

処理の開始から終了までの経過時間には、CPUで計算した時間だけでなく、I/O完了やCPUの割当てを待つ時間も含まれます。CPU使用率だけを見ても、ある処理が遅い原因は分かりません。

一つの仕事がCPU処理、I/O待ち、CPUの実行待ちを順に通る記録を集計します。まず時間の内訳を求め、CPUだけを速くした場合とI/Oだけを短くした場合を比較します。最後に別の仕事をI/O待ち中へ配置し、装置全体の利用率と個々の完了時刻を分けて考えます。

1状態ごとの時間記録

各区間は(状態,開始ms,終了ms)です。CPUは実行中、IOはI/O待ち、READYはCPUを得るまでの待ちです。

trace = [('CPU',0,2),('IO',2,10),('READY',10,13),('CPU',13,15)]一つの仕事の状態遷移; print(trace)区間の記録

仕事は0から15 msまでかかっています。10 msでI/Oが終わっても、CPUを得るのは13 msです。I/O完了と再実行開始が同じ時刻とは限りません。

2CPU・I/O・実行待ちの合計

各状態に該当する区間の長さを合計します。

times = {state:sum(e-s for k,s,e in trace if k==state) for state in ('CPU','IO','READY')}状態ごとの長さ; print(times)内訳; print(sum(times.values()))全体との照合

CPUは4、I/O待ちは8、実行待ちは3 msで合計15 msです。この記録では区間が重ならず全経過時間を覆っています。複数スレッドの時間を合計する場合は、同じ壁時計時間に複数の区間が重なるので同じ足し方で経過時間を求められません。

3対象プロセスのCPU使用割合

この仕事のCPU時間4 msを経過15 msで割ります。1 CPUに対する割合です。

elapsed = trace[-1][2]-trace[0][1]開始から終了まで; print(round(100*times['CPU']/elapsed,2))対象仕事のCPU割合

約26.67%です。残る時間はこの仕事がCPUを使わなかった時間であり、装置全体のCPUが空いていたことまでは示しません。READYの間に他の仕事がCPUを使っている場合もあります。

4CPUだけを2倍にする

CPU区間を半分にし、I/Oと実行待ちの長さは一定と仮定します。

cpu_fast = times['CPU']/2 + times['IO'] + times['READY']CPU区間だけ短縮; print(cpu_fast, round(elapsed/cpu_fast,3))新しい時間と速度比

完了まで13 ms、速度比は約1.154倍です。CPU時間4 msを2 msへ縮めても、残る11 msはそのままです。実際には順序や競合も変わり得るため、これは他の区間を固定した比較です。

5I/O待ちだけを半分にする

次はCPU時間を元へ戻し、I/O待ち8 msだけを4 msへ縮めます。

io_fast = times['CPU'] + times['IO']/2 + times['READY']I/O区間だけ短縮; print(io_fast, round(elapsed/io_fast,3))新しい時間と速度比

完了まで11 ms、速度比は約1.364倍です。今回の内訳ではI/O待ちの比率が大きいため、同じ半減でもI/Oの改善がより大きく効きます。どの資源を増やすかはこのような内訳から判断します。

6待ち時間中に別の仕事を動かす

別の例としてAはCPU2・I/O8・CPU2 ms、BはCPU6 msを必要とし、両方時刻0から実行可能とします。AのI/O待ち中にBを置いたCPU記録を作ります。

cpu_trace = [('A',0,2),('B',2,8),('idle',8,10),('A',10,12)]CPUの担当と空き時間; print(cpu_trace)時間割; print(sum(e-s for n,s,e in cpu_trace if n!='idle'))CPU稼働時間

CPUは合計10 ms動き、全仕事は12 msで終了します。AのI/OとBのCPU処理を重ねられるため、Aを終えてからBを始める18 msより短くなります。I/O処理とCPU処理が別資源で進むことが条件です。

7装置全体と個々の完了を分ける

全体のCPU利用率とA・Bそれぞれの完了時刻を計算します。

busy = sum(e-s for n,s,e in cpu_trace if n!='idle')CPUが動いた区間; print(round(100*busy/12,2))全体利用率; print({n:max(e for x,s,e in cpu_trace if x==n) for n in ('A','B')})各仕事の完了

全体のCPU利用率は約83.33%、Aは12 ms、Bは8 msで完了します。高い利用率は待ち時間を有効に使ったことを示しますが、全プロセスが同時に早く終わるという指標ではありません。個別の応答や期限も別に測ります。

8I/O中も空回りした場合

AがI/O完了までCPUを占有してポーリングし、その間Bが走れない実行順と比較します。Aの計算は4 msのままですが、8 msの空回りがCPU時間へ加わります。

polling = [('A compute',2),('A poll',8),('A compute',2),('B compute',6)]CPUを保持する順序; polling_cpu = sum(length for _,length in polling)実行時間を集計; print(polling_cpu, busy)CPU消費の差; print('B completion:', polling_cpu, max(e for n,s,e in cpu_trace if n=='B'))Bの完了時刻を比較

CPUを使った時間は18 msと10 msです。空回りの例は利用率100%でもBの完了が18 msへ遅れています。実際のポーリングも割込みやスケジューリングの対象になり得ますが、この比較ではAがCPUを保持する条件を固定しています。

まとめ

経過時間をCPU・I/O待ち・実行待ちへ分けると、短縮の効果を計算できます。

対象プロセスのCPU割合と装置全体の利用率は別の指標です。

I/O待ち中に別の仕事を実行できれば資源を有効に使えますが、空回りによる高利用率が処理の速さを示すとは限りません。

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

Python 3

1
trace = [('CPU',0,2),('IO',2,10),('READY',10,13),('CPU',13,15)]; print(trace)
[('CPU', 0, 2), ('IO', 2, 10), ('READY', 10, 13), ('CPU', 13, 15)]
2
times = {state:sum(e-s for k,s,e in trace if k==state) for state in ('CPU','IO','READY')}; print(times); print(sum(times.values()))
{'CPU': 4, 'IO': 8, 'READY': 3}
15
3
elapsed = trace[-1][2]-trace[0][1]; print(round(100*times['CPU']/elapsed,2))
26.67
4
cpu_fast = times['CPU']/2 + times['IO'] + times['READY']; print(cpu_fast, round(elapsed/cpu_fast,3))
13.0 1.154
5
io_fast = times['CPU'] + times['IO']/2 + times['READY']; print(io_fast, round(elapsed/io_fast,3))
11.0 1.364
6
cpu_trace = [('A',0,2),('B',2,8),('idle',8,10),('A',10,12)]; print(cpu_trace); print(sum(e-s for n,s,e in cpu_trace if n!='idle'))
[('A', 0, 2), ('B', 2, 8), ('idle', 8, 10), ('A', 10, 12)]
10
7
busy = sum(e-s for n,s,e in cpu_trace if n!='idle'); print(round(100*busy/12,2)); print({n:max(e for x,s,e in cpu_trace if x==n) for n in ('A','B')})
83.33
{'A': 12, 'B': 8}
8
polling = [('A compute',2),('A poll',8),('A compute',2),('B compute',6)]; polling_cpu = sum(length for _,length in polling); print(polling_cpu, busy); print('B completion:', polling_cpu, max(e for n,s,e in cpu_trace if n=='B'))
18 10
B completion: 18 8

演習完了