テクノロジ系

1つのCPUで何本ものアプリを動かす — パイプライン・キャッシュ・RAID・OS

パイプラインのクロック数、キャッシュの実効アクセス時間、仮想記憶とRAID、OSのプロセス管理とデッドロックを、計算表を作りながら学ぶ。

更新日 執筆: PassDojo 編集部

PR
目次読了目安 約9分
  1. 動画を見ながらSNSが開ける — 3つの層が支えている
  2. PCが次の命令を指す — 命令サイクルとパイプラインのクロック数
  3. キャッシュのヒット率で平均が変わる — 実効アクセス時間と仮想記憶
  4. ディスクが1台壊れても動く — RAIDの容量と耐障害性
  5. CPUの時間を分け合う — プロセスとラウンドロビン、デッドロック
  6. ここまでの要点 — CPU・メモリ・OSを5分で復習

動画を見ながらSNSが開ける — 3つの層が支えている

動画アプリで映像を流したまま、SNSを開き、地図アプリで待ち合わせ場所も調べてみましょう。1つのCPU(中央処理装置)が本当に同時に何本も処理しているわけではないのに、どのアプリも止まって見えないのはなぜでしょうか。

その答えは、3つの層の分業にあります。まずCPUは、命令を流れ作業(パイプライン)でこなし、同じ時間で終える命令を増やします。次にメモリとディスクは、速さと容量の違う記憶を階層に重ね、キャッシュで平均の待ち時間を縮め、RAIDで故障に備えます。そしてOSは、限られたCPUとメモリを、プロセスという単位で順番に分け合わせます。

この単元では、層ごとに計算を1つずつ手で解きます。表を作れば、電卓がなくても確実に解けます。

PCが次の命令を指す — 命令サイクルとパイプラインのクロック数

CPUは命令を1つずつ取り出して実行します。この流れが命令サイクルで、本単元ではフェッチ(主記憶から命令を読む)、デコード(解読する)、実行(演算する)、ライトバック(結果を書き戻す)の4段階で説明します。

プログラムカウンタ(PC)は次に実行する命令のアドレスを持つレジスタで、フェッチのたびに更新されます。フラグレジスタは演算結果の「ゼロ」「桁あふれ」などを記録し、条件分岐に使われます。

パイプラインは、この4段階を命令ごとに1クロックずつずらして並行処理する技術です。想定として、4段・6命令・ハザードなしの場合を表にします(F=フェッチ、D=デコード、E=実行、W=ライトバック)。

命令123456789
命令1FDEW-----
命令2-FDEW----
命令3--FDEW---
命令4---FDEW--
命令5----FDEW-
命令6-----FDEW

最初の命令が完了するまで4クロックかかり、その後は1クロックごとに1命令ずつ完了します。よって、N段でM個の命令なら N + M − 1 クロックです。4段・6命令は 4 + 6 − 1 = 9 クロックで、1命令ずつ処理する 4 × 6 = 24 クロックより速くなります。5段・10命令なら 5 + 10 − 1 = 14 クロックです(パイプラインなしは 5 × 10 = 50 クロック)。

ハザードが起きると、この表どおりには進みません。前の命令の結果を後続が先に読む「データハザード」、分岐先が決まるまで次を読めない「制御ハザード」、複数の命令が同じ回路を使おうとする「構造ハザード」の3種類があります。想定として、待ちが2クロック生じれば 9 + 2 = 11 クロックです。

キャッシュのヒット率で平均が変わる — 実効アクセス時間と仮想記憶

記憶装置は、速いものほど高価で小容量なので階層にします。レジスタ、キャッシュメモリ、主記憶、補助記憶の順に遅く大容量になり、キャッシュには高速なSRAM、主記憶には安価なDRAM(要リフレッシュ)を使います。

CPUが欲しいデータがキャッシュにあれば(ヒット)速く、なければ主記憶まで取りに行きます。ヒット率を h とすると、実効アクセス時間は次の式で求めます。

T = h × (キャッシュの時間)+ (1 − h) × (主記憶の時間)

ケースhキャッシュ主記憶計算式実効アクセス時間
A0.910ns100ns0.9 × 10 + 0.1 × 100 = 9 + 1019ns
B0.810ns90ns0.8 × 10 + 0.2 × 90 = 8 + 1826ns
C0.9910ns100ns0.99 × 10 + 0.01 × 100 = 9.9 + 110.9ns

ケースAとCを比べると、ヒット率が 0.9 から 0.99 に上がるだけで 19ns が 10.9ns になり、約4割短くなります((19 − 10.9) ÷ 19 ≒ 0.43)。ミス1回の代償が大きいため、わずかな差が平均に効きます。

仮想記憶は、プログラムをページという固定長の単位に分け、必要なページだけを主記憶に置く仕組みです。ページの大きさを4096バイトと想定すると、アドレス10000番は 10000 ÷ 4096 = 2 余り 1808 で、ページ2の1808バイト目です。必要なページがなければページフォールトが起き、補助記憶から読み込みます。この入れ替えばかりが続いて処理が進まない状態がスラッシングです。

ディスクが1台壊れても動く — RAIDの容量と耐障害性

RAIDは、複数のディスクを1台のように束ねて速度や信頼性を高める技術です。ストライピング(分けて書く)、ミラーリング(同じ内容を書く)、パリティ(復元用の検査情報)を組み合わせます。

想定として、1TBのディスク4台で作った場合の容量を表にします。RAID 1は2台で見ます。

方式使う台数計算使える容量耐えられる故障
RAID 04台4 × 1TB4TBなし
RAID 12台同じ内容を2台に書く1TB1台
RAID 54台(4 − 1) × 1TB3TB1台
RAID 64台(4 − 2) × 1TB2TB2台

パリティはXOR(排他的論理和)で作ります。データ 1011 と 0110 のXORは 1101 で、1011 が失われても、1101 と 0110 のXORで 1011 を取り戻せます。RAID 6はパリティを2種類持つので、2台まで復元できます。

ただしRAIDは故障への備えで、誤って消したファイルを戻すバックアップの代わりにはなりません。

CPUの時間を分け合う — プロセスとラウンドロビン、デッドロック

実行中のプログラムがプロセスで、OSは実行可能状態(CPU待ち)、実行状態、待ち状態(入出力待ち)の間で切り替えて管理します。スレッドは同じプロセスのメモリ空間を共有するので、切り替えの負担が軽くなります。

CPUの渡し方がスケジューリングで、到着順のFCFS、短い順のSJF、優先度順、一定時間ずつ回すラウンドロビンなどがあります。ラウンドロビンをトレースしてみましょう。

想定:A(5秒)、B(3秒)、C(2秒)がこの順に並び、タイムスライスは2秒、切り替えの時間は無視します。残りがあるプロセスは待ち行列の最後に回ります。

区間(秒)実行残り完了待ち行列
0〜2A5 − 2 = 3なしB、C、A
2〜4B3 − 2 = 1なしC、A、B
4〜6C2 − 2 = 0C(6秒)A、B
6〜8A3 − 2 = 1なしB、A
8〜9B1 − 1 = 0B(9秒)A
9〜10A1 − 1 = 0A(10秒)なし

合計は 5 + 3 + 2 = 10秒で、Aの完了は10秒後です(Cは6秒、Bは9秒)。最初にCPUを得るまでの待ちは、FCFSならCが8秒、ラウンドロビンなら4秒です。

デッドロックは、資源を取り合って互いに待ち続ける状態です。たとえば、Pがプリンタを持ってスキャナを待ち、Qがスキャナを持ってプリンタを待つと、どちらも進めません。次の4条件がすべて同時に成り立つと起き、1つでも崩せば防げます。

条件意味崩し方の例
相互排除資源を同時に使えるのは1つのプロセスだけ共有できるようにする
占有待機資源を持ったまま別の資源を待つ必要な資源を一括して確保する
非剥奪持っている資源を強制的には取り上げられない取り上げられるようにする
循環待機待ちの関係が輪になる資源に番号を付け、小さい順に確保する

混同しやすいのが、飢餓(スターベーション)と優先度逆転です。飢餓は、高い優先度のプロセスが続いて、低い優先度のプロセスがいつまでも実行されない状態です。優先度逆転は、低い優先度のプロセスが持つ資源を高い優先度のプロセスが待つ間に、中間の優先度のプロセスが割り込み、高い優先度のプロセスが長く待たされる現象です。どちらもデッドロックとは別の現象です。

低速な出力装置への出力をいったん蓄えて後で出すスプーリングも覚えておきましょう。

出典:IPA『基本情報技術者試験 シラバス Ver.9.2』https://www.ipa.go.jp/shiken/syllabus/omgdg50000005kpe-att/syllabus_fe_ver9_2.pdf (用語例にパイプライン、RAID、ラウンドロビンなどがあります。)

出典:Patterson ほか『A Case for Redundant Arrays of Inexpensive Disks (RAID)』1987 https://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/Archive/CSD-87-391.pdf (RAIDの原論文です。)

ここまでの要点 — CPU・メモリ・OSを5分で復習

  • パイプラインのクロック数は N + M − 1(4段・6命令なら 4 + 6 − 1 = 9)で、段数 × 命令数ではありません。
  • ハザードは3種類です。データ、制御、構造です。
  • 実効アクセス時間は h × キャッシュ + (1 − h) × 主記憶です。h=0.8(10ns と 90ns)なら 26ns です。
  • 4台×1TBの容量は、RAID 0が4TB、RAID 5が3TB、RAID 6が2TBです。
  • ラウンドロビンは時刻の表で追います。A5秒・B3秒・C2秒、タイムスライス2秒なら、Aの完了は10秒後です。
  • デッドロックは4条件がすべてそろうと発生し、飢餓や優先度逆転とは別の現象です。
  • 試験では、クロック数や実効アクセス時間の計算、RAIDの容量、ラウンドロビンの完了時刻、デッドロックの条件が問われます。