# OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か > むき出しのハードウェアで何が困るのかから出発し、特権モードとシステムコール、CPU スケジューリング（SJF の最適性）、ページングと仮想記憶（多段ページテーブル・TLB・LRU のスタック性）、デッドロックの必要条件までを証明付きで解説する。 > https://rikai.mugen-giken.com/computer-science/cs-basics/operating-systems ## 0. この記事の要点 - OS の仕事は突き詰めると 2 つです。ハードウェアの面倒な差異を隠す**抽象化**と、有限の資源を複数のプログラムに配る**資源管理**。この 2 つが「複数のプログラムが同時に、しかも互いを壊さずに動く」という日常を支えています。 - 抽象化と管理を強制するには、ハードウェア側の協力が要ります。**特権モード**と**割り込み**がその協力の実体で、プログラムから OS への入口が**システムコール**です。 - CPU の配分（スケジューリング）は数理的に扱えます。全ジョブが同時に到着する 1 CPU の非割り込みモデルでは、**短いジョブ優先（SJF）が平均待ち時間を最小にします**（）。ただし実際の OS が SJF を使わないのには理由があります。 - メモリの配分は**ページング**で行います。仮想アドレスを固定長のページ単位で物理フレームに写す仕組みで、多段ページテーブルと TLB がこれを実用的な速度と容量に収めます（、）。 - 置き換えアルゴリズムの良し悪しも定理になります。FIFO はメモリを増やすと性能が落ちることがあり（）、LRU にはこの異常が起きません（）。 - 同時実行の安全性はデッドロックの回避に帰着します。デッドロックが起きるには 4 つの条件がすべて必要で（）、どれか 1 つを崩せば防げます。 ## 1. 動機：むき出しのハードウェアで何が困るのか [コンピュータアーキテクチャと CPU の構造](/computer-science/cs-basics/computer-architecture) で見たように、CPU は「メモリから命令を取り、デコードし、実行する」という単純なループを回しているだけの機械です（、）。では、OS が無い状態、つまり電源を入れると自分のプログラムだけが CPU を独占する状態を考えてみてください。1970 年代以前の多くの計算機、あるいは今日のごく小さな組み込み機器はまさにそうなっています。何が困るでしょうか。素朴に数え上げると、少なくとも 4 つの困りごとがあります。 **第一に、ハードウェアの差異がプログラムに漏れます。** ディスクに 1 バイト書くには、そのディスクコントローラのレジスタ配置と手順を知らなければなりません。コントローラが変われば、プログラムを書き直すことになります。同じ「ファイルに保存する」という意図が、機種ごとに別のコードになるのは明らかに不合理です。 **第二に、資源が奪い合いになります。** 2 つのプログラムを同時に動かしたいとして、CPU は 1 つ（あるいは数個）しかありません。物理メモリも有限です。誰がいつ CPU を使うのか、どのプログラムがどの番地を使ってよいのかを、誰かが決めなければなりません。 **第三に、隔離がありません。** プログラム A のバグが番地を踏み外してプログラム B のデータを壊したとき、あるいは悪意あるプログラムが他人のパスワードを読みに行ったとき、それを止めるものが何もありません。 **第四に、暴走を止められません。** 無限ループに入ったプログラムがあると、CPU は永遠にそれを実行し続けます。他のプログラムに実行の機会が回ってきません。 OS（オペレーティングシステム）は、これら 4 つに一度に答えるソフトウェアです。第一の困りごとには**抽象化**（ファイル、ソケット、プロセスといった、ハードウェアに依存しない概念を提供する）で、第二には**資源管理**（スケジューリングとメモリ管理）で、第三と第四には**保護**（特権モードと割り込みを使った強制）で答えます。 ## 2. 準備：特権モードと割り込み OS が「境界」を強制できるのは、OS が偉いからではありません。CPU が 2 つの実行モードを持っているからです。 CPU は状態レジスタの 1 ビット（以上）で表される**実行モード**を持つ。 - **カーネルモード**（特権モード、supervisor mode）では、すべての命令を実行でき、すべての物理メモリと入出力デバイスにアクセスできる。 - **ユーザモード**では、**特権命令**（メモリ管理ユニットの設定変更、割り込みの禁止、入出力ポートへの直接アクセス、モードビット自体の書き換えなど）の実行が禁止され、実行しようとするとハードウェアが**例外**を発生させる。またアクセスできるメモリは、後述のアドレス変換機構が許可した範囲に限られる。ユーザモードからカーネルモードへの遷移は、ハードウェアが定めたごく限られた入口（トラップ・割り込み・例外）を通じてのみ起こり、遷移先の番地は事前にカーネルが設定したベクタで決まる。最後の一文が保護の要です。ユーザプログラムは「カーネルモードになる」ことはできても、「カーネルモードで自分の好きなコードを走らせる」ことはできません。遷移すると必ず OS が用意した番地に飛ばされるからです。もう 1 つの道具が割り込みです。**タイマ割り込み**は一定周期（多くの OS で 1〜10 ミリ秒程度）で CPU の実行を強制的に中断し、カーネルに制御を移します。これがあるおかげで、無限ループするプログラムからも OS は CPU を取り返せます。第四の困りごとへの答えがこれです。ユーザモードのプログラムが OS のサービスを要求するための、規定された手続き。ISA（）が定める専用命令（x86-64 の `syscall`、RISC-V の `ecall`、ARM の `svc`）を実行すると、CPU はカーネルモードに切り替わり、あらかじめ設定されたトラップハンドラの番地から実行を再開する。引数はレジスタまたはメモリを介して渡され、要求の種類はシステムコール番号で指定される。処理を終えたカーネルは復帰命令（RISC-V の `sret` など）でユーザモードに戻す。

|"ecall / syscall 命令"| T["トラップ処理（カーネルが設定した番地）"] T --> K["カーネルモード：OS のサービス実行"] K -->|"sret / sysret 命令"| U H["タイマ・デバイス"] -.->|"割り込み"| T E["不正な番地アクセス・特権命令"] -.->|"例外"| T`} /> C 言語で `read(fd, buf, n)` と書いたとき、実際に起きているのはこの往復です。ライブラリ関数 `read` は引数をレジスタに詰めて `syscall` 命令を実行し、カーネルがファイル記述子 `fd` を解決し、ディスクドライバに読み出しを依頼し、結果を `buf` にコピーして戻ってきます。プログラム側はディスクコントローラのことを何も知りません。これが第一の困りごとへの答えです。 ## 3. プロセス：実行中のプログラムという抽象 **プロセス**とは、実行中のプログラムを表す OS の抽象であり、次の情報の組として実現される。 1. **アドレス空間**：そのプロセスが見る仮想アドレスの全体と、その各領域（コード、データ、ヒープ、スタック）の内容。 2. **CPU の実行文脈**：プログラムカウンタ、汎用レジスタ、スタックポインタ、状態レジスタの値。 3. **カーネルが管理する資源**：開いているファイル記述子の表、シグナルの設定、親子関係、資源利用の統計など。 4. **状態**：実行中（running）、実行可能（ready）、待ち（blocked）のいずれか。これらをまとめて保持するカーネル内のデータ構造を**プロセス制御ブロック**（PCB）と呼ぶ。プロセスという抽象が与えるものは 2 つあります。1 つは**CPU の仮想化**で、実際には 1 つの CPU を時分割しているのに、各プロセスからは自分専用の CPU があるように見えます。もう 1 つは**メモリの仮想化**で、これは以降で扱います。実行中のプロセス $P$ から別のプロセス $Q$ へ CPU を移す操作。カーネルは (a) $P$ のレジスタ群を $P$ の PCB に退避し、(b) メモリ管理ユニットのページテーブル基底レジスタを $Q$ のものに切り替え、(c) $Q$ の PCB からレジスタ群を復元し、(d) $Q$ のユーザモードへ復帰する。コンテキストスイッチには直接費用（レジスタの退避と復元、数マイクロ秒未満）と間接費用（キャッシュと TLB の内容が新しいプロセスのものに入れ替わるまでの性能低下、しばしば直接費用より大きい）があります。この費用があるために、「タイムスライスをいくらでも細かくすればよい」とはなりません。 ## 4. CPU スケジューリング実行可能なプロセスが複数あるとき、どれを次に走らせるかを決めるのがスケジューラです。まず評価指標を定めます。プロセス $i$ が時刻 $a_i$ に到着し、CPU を合計 $t_i$ だけ必要とし（この $t_i$ を**バースト時間**という）、時刻 $c_i$ に完了したとします。 - **待ち時間** $w_i = (c_i - a_i) - t_i$：実行可能なのに走れなかった時間の合計。 - **応答時間** $r_i$：到着してから初めて CPU を得るまでの時間。 - **ターンアラウンド時間** $c_i - a_i$。対話的な用途では応答時間が、バッチ処理では平均待ち時間が重視されます。この 2 つは同時には最適化できません。まず平均待ち時間について、はっきりした答えがあります。 $n$ 個のプロセスがすべて時刻 $0$ に到着し、バースト時間 $t_1, \ldots, t_n > 0$ が既知であるとする。CPU は 1 個、いったん実行を始めたプロセスは完了するまで中断しない（非プリエンプティブ）ものとし、コンテキストスイッチの費用は $0$ とする。このとき、バースト時間の昇順に実行する順序（最短ジョブ優先、SJF）は平均待ち時間を最小にする。実行順序を全単射 $\pi : \{1,\ldots,n\} \to \{1,\ldots,n\}$ で表し、$\pi(k)$ を $k$ 番目に実行するプロセスとします。すべて時刻 $0$ に到着し中断が無いので、$k$ 番目に実行されるプロセスの待ち時間は、それより前に実行されたプロセスのバースト時間の総和です。すなわち $$ w_{\pi(k)} = \sum_{j=1}^{k-1} t_{\pi(j)} . $$ 総待ち時間 $W(\pi) = \sum_{k=1}^{n} w_{\pi(k)}$ を、和の順序を入れ替えて $j$ について整理します。$t_{\pi(j)}$ が現れるのは $k = j+1, j+2, \ldots, n$ の $n-j$ 個の項なので $$ W(\pi) = \sum_{k=1}^{n}\sum_{j=1}^{k-1} t_{\pi(j)} = \sum_{j=1}^{n} (n-j)\, t_{\pi(j)} . $$ ここで、$\pi$ が昇順でないと仮定します。すると隣り合う位置 $j, j+1$ で $a := t_{\pi(j)} > t_{\pi(j+1)} =: b$ となるものが存在します（もし隣接するすべての組で $t_{\pi(j)} \le t_{\pi(j+1)}$ なら列全体が昇順だからです）。この 2 つを入れ替えた順序を $\pi'$ とすると、$j, j+1$ 以外の項は変わらないので $$ W(\pi') - W(\pi) = \bigl[(n-j)b + (n-j-1)a\bigr] - \bigl[(n-j)a + (n-j-1)b\bigr] = b - a < 0 . $$ つまり入れ替えると総待ち時間が真に減ります。順序は有限個（$n!$ 通り）しかないので最小値を取る順序が存在し、いま示したことからそれは昇順でなければなりません。逆に昇順の順序は（バースト時間が等しいものの並べ方を除いて）一意で、値はすべて等しくなります。平均待ち時間は $W(\pi)/n$ なので、同じ順序が平均も最小にします。は美しいのですが、実際の OS はそのままでは使えません。理由は 2 つあります。第一に、バースト時間 $t_i$ は事前には分かりません（分かるならプログラムの停止性が分かってしまいます。プログラムを走らせずにその実行時のふるまいを言い当てることの原理的な限界についてはを参照）。第二に、長いジョブが**飢餓**（starvation）に陥ります。短いジョブが到着し続ける限り、長いジョブは永遠に走れません。実用のスケジューラは、過去のバースト長の指数移動平均で $t_i$ を推定したり、待たされた時間に応じて優先度を上げる**エイジング**を組み合わせたりします。対話的な応答時間を保証するには、時間で強制的に切り上げる方式を使います。ラウンドロビン方式（実行可能プロセスを循環キューに並べ、各プロセスに一定の**タイムクォンタム** $q > 0$ ずつ CPU を与え、使い切ったらキューの末尾に戻す）を考える。実行可能なプロセスが常に高々 $n$ 個であり、1 回のコンテキストスイッチに時間 $s \ge 0$ かかるとする。このとき、実行可能になったどのプロセスも、$(n-1)(q+s)$ 以内に必ず最初の CPU 時間を得る。また、どのプロセスもクォンタムを使い切る（実行の途中で終了したり待ちに入ったりしない）ならば、CPU の実効利用率は $q/(q+s)$ である。あるプロセス $P$ がキューの末尾に入った瞬間を考えます。$P$ の前には高々 $n-1$ 個のプロセスがいます。ラウンドロビンでは各プロセスは 1 回の順番につき最大 $q$ しか CPU を占有せず、その後に 1 回のコンテキストスイッチ（時間 $s$）が入るので、$P$ の前の 1 個あたりに費やされる時間は高々 $q + s$ です。前のプロセスがクォンタムを使い切らずに終了または待ちに入る場合はそれより短くなります。したがって $P$ が CPU を得るまでの時間は高々 $(n-1)(q+s)$ です。利用率については、キューが空でない限り、時間軸は「実行 $q$」と「切り替え $s$」の繰り返しで埋まります。よって CPU が有用な仕事に使われる割合は $q/(q+s)$ です。なお、クォンタムを使い切らずに終了または待ちに入るプロセスがあると、切り替えの回数はそのままで実行部分だけが短くなるので、この比率は下がりえます。この 2 つの主張が、クォンタム $q$ の設計指針を与えます。$q$ を小さくすると応答時間の上界 $(n-1)(q+s)$ は改善しますが、利用率 $q/(q+s)$ が落ちます。$s = 5\ \mu\mathrm{s}$、$q = 1\ \mathrm{ms}$ なら利用率は $1000/1005 \approx 99.5\%$、$q = 50\ \mu\mathrm{s}$ なら $50/55 \approx 91\%$ です。実際の Linux の CFS は固定クォンタムではなく「各プロセスの実行済み時間（仮想実行時間）が最小のものを選ぶ」方式ですが、思想は同じで、最小粒度を設けて切り替えすぎを防いでいます。時刻 $0$ に 4 つのプロセスが到着し、バースト時間が $t_1 = 24,\ t_2 = 3,\ t_3 = 3,\ t_4 = 6$（単位はミリ秒）だとします。切り替え費用は $0$ とします。 **FCFS（到着順、$P_1 \to P_2 \to P_3 \to P_4$）**：待ち時間は $0,\ 24,\ 27,\ 30$ なので $$ \bar{w} = \frac{0+24+27+30}{4} = \frac{81}{4} = 20.25 . $$ 応答時間も同じ $0, 24, 27, 30$ で平均 $20.25$ です。 **SJF（$P_2 \to P_3 \to P_4 \to P_1$）**：待ち時間は $0,\ 3,\ 6,\ 12$ なので $$ \bar{w} = \frac{0+3+6+12}{4} = \frac{21}{4} = 5.25 . $$ の通り、これが最小です。 **ラウンドロビン（$q = 4$）**：実行の様子を追うと、$[0,4)$ が $P_1$（残 20）、$[4,7)$ で $P_2$ 完了、$[7,10)$ で $P_3$ 完了、$[10,14)$ が $P_4$（残 2）、$[14,18)$ が $P_1$（残 16）、$[18,20)$ で $P_4$ 完了、以降 $[20,36)$ で $P_1$ が完了します。完了時刻は $c = (36, 7, 10, 20)$ なので待ち時間は $c_i - t_i$ より $12,\ 4,\ 7,\ 14$、平均は $$ \bar{w} = \frac{12+4+7+14}{4} = \frac{37}{4} = 9.25 . $$ 応答時間は $0,\ 4,\ 7,\ 10$ で平均 $5.25$。平均待ち時間では SJF に負けますが、**応答時間は FCFS の $20.25$ から $5.25$ へ約 4 分の 1 に縮んでいます**。対話的なシステムがラウンドロビン系を選ぶ理由がここにあります。 ## 5. メモリ管理と仮想記憶 CPU の次はメモリです。複数のプロセスを同時にメモリに置くとき、素朴に「プロセス A は物理番地 0x1000 から、B は 0x9000 から」と割り当てると、3 つの問題が起きます。(i) A が番地を踏み外すと B を壊す。(ii) A をコンパイルする時点で配置先を知っていなければならない。(iii) 物理メモリより大きなプログラムが動かせない。これらを一度に解くのがアドレス変換です。仮想アドレス空間と物理アドレス空間を、同じ大きさ $2^{p}$ バイトの**ページ**／**フレーム**に分割する（典型的には $2^{12} = 4$ KiB）。$b$ ビットの仮想アドレス $v$ を $$ v = \underbrace{\lfloor v / 2^{p} \rfloor}_{\text{仮想ページ番号 } \mathrm{VPN}} \cdot 2^{p} + \underbrace{(v \bmod 2^{p})}_{\text{オフセット}} $$ と分解し、プロセスごとに用意された**ページテーブル** $T$（VPN から物理フレーム番号 PFN への部分写像）を使って物理アドレスを $$ \mathrm{phys}(v) = T(\mathrm{VPN}) \cdot 2^{p} + (v \bmod 2^{p}) $$ で定める。各ページテーブル項目（PTE）は PFN に加えて、有効ビット、読み書き実行の許可ビット、ユーザモードからのアクセス可否、参照済みビット、変更済みビットを持つ。$T$ が VPN に対して未定義（有効ビットが $0$）のアドレスに触れると、CPU は**ページフォルト**例外を起こしてカーネルに制御を移す。この変換はメモリ管理ユニット（MMU）がハードウェアで行い、ページテーブルの先頭物理アドレスは特権レジスタ（x86-64 の CR3、RISC-V の `satp`）が保持する。オフセットが変換されないのが要点です。ページ内の連続性は保たれ、変換の単位はページ単位で済みます。

32 ビット仮想アドレス、ページサイズ 4 KiB（$p = 12$）とします。仮想アドレス $v = \mathtt{0x00403ABC}$ を変換します。オフセットは下位 12 ビット、つまり 16 進で下 3 桁なので $\mathtt{0xABC} = 2748$ です。仮想ページ番号は $$ \mathrm{VPN} = \lfloor \mathtt{0x00403ABC} / 2^{12} \rfloor = \mathtt{0x00403} = 1027 . $$ ページテーブルの第 $1027$ 項を引いたところ、有効ビットが $1$、PFN が $\mathtt{0x1F2} = 498$、書き込み許可ありだったとします。すると物理アドレスは $$ \mathrm{phys}(v) = 498 \cdot 4096 + 2748 = 2039808 + 2748 = 2042556 = \mathtt{0x001F2ABC} . $$ 16 進で見ると、上位 5 桁が $\mathtt{00403} \to \mathtt{001F2}$ に置き換わり、下 3 桁 $\mathtt{ABC}$ はそのまま残っていることが確認できます。この仕組みが冒頭の 3 つの問題を解きます。(i) ページテーブルに載っていない物理フレームには物理的に触れられないので、プロセスは互いに隔離されます。(ii) すべてのプロセスが同じ仮想アドレスから始めてよいので、配置先を知らずにコンパイルできます。(iii) 有効ビットを $0$ にしてページの内容をディスクに退避しておき、アクセス時のページフォルトで読み戻せば、物理メモリより大きな仮想アドレス空間が使えます。これが**仮想記憶**です。 ### 5.1. ページテーブルが大きすぎる問題をそのまま実装すると容量が破綻します。32 ビット・4 KiB ページなら VPN は 20 ビットなので $2^{20}$ 項、1 項 4 バイトとして $4$ MiB。これを**プロセスごとに**常駐させる必要があり、100 プロセスで 400 MiB です。64 ビットではまったく不可能です。解決は、ページテーブル自身をページングすることです。VPN をさらに分割し、木構造にします。 32 ビット仮想アドレス、ページサイズ 4 KiB、PTE 4 バイトの 2 段ページテーブルを考える。仮想アドレスを上位 10 ビット（1 段目の添字）、次の 10 ビット（2 段目の添字）、下位 12 ビット（オフセット）に分割する。あるプロセスが実際に使っている仮想ページの集合を $S$ とし、$S$ に属するページの 1 段目添字の集合を $I = \{\lfloor \mathrm{VPN}/2^{10}\rfloor : \mathrm{VPN} \in S\}$ とする。このとき、そのプロセスのページテーブルが占める容量はちょうど $(1 + |I|) \times 4\ \mathrm{KiB}$ である。 1 段目の表は $2^{10} = 1024$ 項、各 4 バイトなので $1024 \times 4 = 4096$ バイト $= 4$ KiB。ちょうど 1 ページに収まり、これは常に 1 つ必要です。 2 段目の表も同様に 1024 項 $\times$ 4 バイト $=$ 4 KiB です。2 段目の表は 1 段目の添字ごとに 1 つ用意されますが、その添字を持つ仮想ページが 1 つも使われていなければ、1 段目の該当項の有効ビットを $0$ にしておけばよく、表そのものを確保する必要がありません。逆に、その添字を持つ仮想ページが 1 つでも使われていれば表を 1 つ確保します。したがって確保される 2 段目の表の個数はちょうど $|I|$ 個です。合計 $(1 + |I|) \times 4$ KiB。典型的な小さなプロセスが、コード・データ領域を $\mathtt{0x00400000}$ 付近に、スタックを $\mathtt{0xBFFFF000}$ 付近に持つとします。の 1 段目添字は仮想アドレスを $2^{22} = 4$ MiB で割った商です。 $$ \left\lfloor \frac{\mathtt{0x00400000}}{4194304} \right\rfloor = \frac{4194304}{4194304} = 1, \qquad \left\lfloor \frac{\mathtt{0xBFFFF000}}{4194304} \right\rfloor = \left\lfloor \frac{3221221376}{4194304} \right\rfloor = 767 . $$ （後者は $767 \times 4194304 = 3217031168$、$768 \times 4194304 = 3221225472 > 3221221376$ から確かめられます。）よって $I = \{1, 767\}$、$|I| = 2$ で、ページテーブルの容量は $$ (1 + 2) \times 4\ \mathrm{KiB} = 12\ \mathrm{KiB} . $$ 1 段構成の $4$ MiB に対して約 $1/341$ です。x86-64 は同じ発想を 4 段（$9+9+9+9+12 = 48$ ビット）に拡張し、RISC-V の Sv39 は 3 段（$9+9+9+12 = 39$ ビット）を使います。 ### 5.2. 変換が遅すぎる問題段数を増やすと容量は減りますが、1 回のメモリアクセスのために表を段数回たどることになります。4 段なら、データ 1 回のアクセスに合計 5 回のメモリアクセスです。これでは 5 倍遅くなります。対策は変換結果のキャッシュで、これを **TLB**（Translation Lookaside Buffer）と呼びます。TLB は VPN から PFN への最近の対応を数十〜数千項保持する連想メモリで、MMU の中にあります。 TLB の参照に時間 $\varepsilon$、主記憶の 1 回のアクセスに時間 $m$ かかるとする。ページテーブルは 1 段とし、TLB のヒット率を $h$（$0 \le h \le 1$）、ページフォルトは起きないものとする。このとき、データ 1 語を読むまでの平均時間（実効アクセス時間）は $$ \mathrm{EAT} = \varepsilon + m + (1-h)\, m $$ である。どちらの場合も、まず TLB を引くので $\varepsilon$ がかかります。 TLB ヒットのとき（確率 $h$）、PFN が即座に得られるので、あとは目的のデータを主記憶から読む 1 回だけで、合計 $\varepsilon + m$ です。 TLB ミスのとき（確率 $1-h$）、ページテーブルを主記憶から読む 1 回（$m$）と、目的のデータを読む 1 回（$m$）が必要で、合計 $\varepsilon + 2m$ です。期待値を取ると $$ \mathrm{EAT} = h(\varepsilon + m) + (1-h)(\varepsilon + 2m) = \varepsilon + m\bigl[h + 2(1-h)\bigr] = \varepsilon + m(2 - h) = \varepsilon + m + (1-h)m . $$ $\varepsilon = 1$ ns、$m = 100$ ns とします。TLB が無ければ 1 段でも $2m = 200$ ns、つまりアクセスのたびに 2 倍の時間がかかります。ヒット率 $h = 0.98$ ならより $$ \mathrm{EAT} = 1 + 100 + 0.02 \times 100 = 103\ \mathrm{ns}, $$ つまり変換の追加費用はわずか $3\%$ です。$h = 0.90$ に落ちると $\mathrm{EAT} = 1 + 100 + 10 = 111$ ns（$11\%$ 増）。$h$ が数 % 変わるだけで体感が変わるので、TLB を溢れさせないことは性能上きわめて重要です。大きなページ（2 MiB の huge page）が使われるのは、同じ TLB 項数でカバーできるメモリ量を 512 倍にするためです。なお、コンテキストスイッチ（）はページテーブルを切り替えるので、素朴には TLB を全部無効化する必要があります。現代の CPU が TLB 項にアドレス空間識別子（ASID／PCID）を持たせているのは、この一括無効化を避けるためです。 ### 5.3. どのページを追い出すか物理メモリが足りなくなると、どのページをディスクに追い出すかを決めなければなりません。理論上の最適解は「次に使われるのが最も遠い先のページを追い出す」（Belady の最適アルゴリズム）ですが、未来が必要なので実装できません。実用の候補は FIFO（最も古く読み込んだものを追い出す）と LRU（最後に参照されたのが最も古いものを追い出す）です。直感的には「フレーム数を増やせばページフォルトは減る」と思えます。しかし FIFO ではそうなりません。参照列 $\sigma = 1,2,3,4,1,2,5,1,2,3,4,5$ を、最初は空のメモリに対して FIFO で処理します。 **フレーム 3 個**（角括弧は読み込んだ順、左が最古）： | 参照 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---|---|---|---|---|---|---|---| | 判定 | F | F | F | F | F | F | F | H | H | F | F | H | $4$ で最古の $1$ を追い出して $[2,3,4]$、次の $1$ で $2$ を追い出して $[3,4,1]$、次の $2$ で $3$ を追い出して $[4,1,2]$、$5$ で $4$ を追い出して $[1,2,5]$。ここで $1$ と $2$ が連続ヒットします。その後 $3$ で $1$ を追い出して $[2,5,3]$、$4$ で $2$ を追い出して $[5,3,4]$、最後の $5$ はヒット。フォルトは **9 回**です。 **フレーム 4 個**： | 参照 | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---|---|---|---|---|---|---|---| | 判定 | F | F | F | F | H | H | F | F | F | F | F | F | 最初の 4 つで $[1,2,3,4]$ が埋まり、$1, 2$ はヒットします。しかし $5$ で最古の $1$ を追い出した瞬間から歯車が狂い、以降は追い出したばかりのものを次に要求する、という状態が続いて $7$ 回目以降すべてフォルトします。フォルトは **10 回**。フレームを 1 個増やしたのにフォルトが 9 回から 10 回に**増えました**。これが Belady の異常です。原因は、FIFO の「メモリ内容」がフレーム数について包含関係を持たないことにあります。デマンドページング（参照されたページだけを読み込み、最初メモリは空とする）のもとで LRU を用いる。参照列 $\sigma = \sigma(1)\sigma(2)\cdots$ に対し、フレーム数 $m$ で $t$ 回目の参照を処理した直後にメモリにあるページの集合を $S_m(t)$、$t$ 回目までのページフォルト回数を $F_m(t)$ と書く。このとき、すべての $m \ge 1$ とすべての $t \ge 0$ に対し $$ S_m(t) \subseteq S_{m+1}(t) $$ が成り立ち、その帰結としてすべての $t$ で $F_{m+1}(t) \le F_m(t)$ が成り立つ。 **第 1 段：$S_m(t)$ の特徴づけ。** $\sigma(1),\ldots,\sigma(t)$ に現れる相異なるページを、最後に参照された時刻の遅い順（新しい順）に並べたものを $q_1(t), q_2(t), \ldots, q_{d_t}(t)$ とします（$d_t$ は相異なるページ数）。主張は $$ S_m(t) = \{ q_1(t), \ldots, q_{\min(m, d_t)}(t) \} $$ です。これを $t$ についての帰納法で示します。 $t = 0$ のときメモリは空で $d_0 = 0$、両辺とも空集合です。 $t$ で成り立つとし、$p := \sigma(t+1)$ を参照します。参照後の新しい順序 $q_\bullet(t+1)$ は、$p$ が先頭に来て、それ以外のページの相対順序は変わりません。3 つの場合に分けます。 (a) $p \in S_m(t)$ のとき。ヒットなのでメモリの中身は変わらず $S_m(t+1) = S_m(t)$。一方、帰納法の仮定より $p$ は新しい順で $\min(m,d_t)$ 位以内にいたので、$p$ を先頭に移しても上位 $\min(m,d_t)$ 個の**集合**は変わりません。また $d_{t+1} = d_t$。よって主張は保たれます。 (b) $p \notin S_m(t)$ かつ $|S_m(t)| < m$ のとき。帰納法の仮定より $|S_m(t)| = d_t < m$、つまりメモリには過去に現れた相異なるページがすべて入っているので、$p$ は初出です。フォルトして $p$ を空きフレームに入れるので $S_m(t+1) = S_m(t) \cup \{p\}$。他方 $d_{t+1} = d_t + 1 \le m$ で、上位 $\min(m, d_{t+1}) = d_{t+1}$ 個は過去に現れた全ページに $p$ を加えたものです。一致します。 (c) $p \notin S_m(t)$ かつ $|S_m(t)| = m$ のとき。フォルトし、LRU は最後の参照が最も古いページ、すなわち帰納法の仮定より $q_m(t)$ を追い出して $p$ を入れます。よって $$ S_m(t+1) = \bigl(\{q_1(t),\ldots,q_m(t)\} \setminus \{q_m(t)\}\bigr) \cup \{p\} = \{p, q_1(t), \ldots, q_{m-1}(t)\}. $$ 一方、新しい順序では $p$ が 1 位、$q_1(t),\ldots,q_{m-1}(t)$ が順に 2 位から $m$ 位に繰り下がるので、上位 $m$ 個はまさにこの集合です。一致します。以上で第 1 段が示せました。 **第 2 段：包含関係。** 第 1 段より $S_m(t)$ は「新しい順で上位 $\min(m,d_t)$ 個」、$S_{m+1}(t)$ は「上位 $\min(m+1,d_t)$ 個」です。$\min(m,d_t) \le \min(m+1,d_t)$ で、どちらも同じ順序 $q_\bullet(t)$ の先頭からの切り出しなので $S_m(t) \subseteq S_{m+1}(t)$。 **第 3 段：フォルト回数の単調性。** $t+1$ 回目の参照 $p = \sigma(t+1)$ が $m$ フレームでヒットする、すなわち $p \in S_m(t)$ ならば、第 2 段より $p \in S_{m+1}(t)$ なので $m+1$ フレームでもヒットします。対偶を取れば「$m+1$ フレームでフォルトするなら $m$ フレームでもフォルトする」。したがって各時刻でのフォルトの指示関数について $\mathbf{1}[m+1 \text{ でフォルト}] \le \mathbf{1}[m \text{ でフォルト}]$ が成り立ち、$t$ まで足し合わせて $F_{m+1}(t) \le F_m(t)$ を得ます。第 1 段の (c) が、FIFO では成り立たない部分です。FIFO は追い出す対象を「読み込んだ順」で選ぶため、メモリの中身が「参照の新しさ順の上位 $m$ 個」という $m$ について入れ子になる形にならず、包含関係が壊れます。はその具体的な現れです。 ## 6. 同時実行の安全性：相互排除とデッドロックプロセスやスレッドが同じデータを触り始めると、新しい種類の誤りが生まれます。複数の実行主体が共有する状態を読み書きするコード領域を**クリティカルセクション**という。任意の時刻に高々 1 つの実行主体しかクリティカルセクションを実行していないことを保証する性質を**相互排除**（mutual exclusion）という。相互排除に加えて、(i) クリティカルセクションに入りたい主体が存在し、中に誰もいなければ有限時間内に誰かが入れる（進行性）、(ii) 入りたい主体が無限に待たされない（有限待ち）、が満たされるとき、その排他機構は正しいという。たとえば `counter = counter + 1` は、翻訳器（）が生成する機械語では「読む・足す・書く」の 3 命令であり、2 つのスレッドが交互に実行すると更新が 1 回失われます。この 3 命令をクリティカルセクションとして守る必要があります。OS はそのためにミューテックスやセマフォを提供し、その実装には CPU のアトミック命令（compare-and-swap など）と、待ち状態のプロセスをスケジューラから外す仕組みを使います。排他機構を導入すると、今度は互いに待ち合って進まなくなる状態が生じます。プロセスの集合 $D \ne \emptyset$ が**デッドロック**しているとは、$D$ のどのプロセスも、$D$ の別のプロセスが保持している資源の解放を待っており、その解放が起こり得ない状態をいう。**待ちグラフ**（wait-for graph）を、頂点をプロセス、辺 $P \to Q$ を「$P$ が要求している資源を $Q$ が保持している」と定めた有向グラフとする。有限有向グラフ $G$ のすべての頂点の出次数が $1$ 以上ならば、$G$ は有向閉路を含む。頂点を 1 つ選んで $v_0$ とします。すべての頂点の出次数が $1$ 以上なので、$v_0$ から出る辺を 1 本選んで行き先を $v_1$、同様に $v_1$ から $v_2$、と無限に歩き続けられます。$G$ の頂点数は有限の $N$ 個なので、鳩の巣原理より $v_0, v_1, \ldots, v_N$ の $N+1$ 個の中に同じ頂点が 2 度現れます。すなわち $i < j$ で $v_i = v_j$ となる組があります。このとき $v_i \to v_{i+1} \to \cdots \to v_j = v_i$ は有向閉路です。デッドロック（）が発生しているならば、次の 4 条件がすべて成り立っている。 1. **相互排除**：少なくとも 1 種類の資源は、同時に 1 つのプロセスしか保持できない。 2. **保持と待ち**：あるプロセスが少なくとも 1 つの資源を保持したまま、別の資源の解放を待っている。 3. **横取り不可**：資源は保持しているプロセスが自発的に解放するまで、外部から取り上げられない。 4. **循環待ち**：プロセスの列 $P_1, P_2, \ldots, P_k$（$k \ge 2$）が存在し、各 $i$ について $P_i$ は $P_{i+1}$ が保持する資源を待っている（添字は $\bmod\ k$、すなわち $P_k$ は $P_1$ を待つ）。デッドロックしているプロセスの集合を $D$ とします。 **1 について。** もしすべての資源が任意個のプロセスに同時に保持できるなら、資源の要求は常に即座に満たされるので、どのプロセスも待ち状態になりません。これは $D$ の各プロセスが待っているというに反します。よって少なくとも 1 種類の資源は排他的です。 **2 について。** より $D$ の各プロセス $P$ は他のプロセスの資源解放を待っています。もし $P$ が何も保持していないなら、$P$ が待っている相手 $Q \in D$ を考えます。$Q$ もまた誰かを待っており、その連鎖をたどると（第 4 項で示すように）閉路が生じますが、閉路上のプロセスはすべて「他から待たれている」ので資源を保持しています。よって $D$ の中に、資源を保持しながら待っているプロセスが必ず存在します。 **3 について。** 資源を横取りできるなら、待っているプロセスに資源を割り当てることで待ちを解消できます。すると「解放が起こり得ない」というの条件が成り立たなくなります。よって横取り不可です。 **4 について。** $D$ の要素を頂点とする待ちグラフの誘導部分グラフ $G$ を考えます。より、$D$ の各プロセスは $D$ の別のプロセスが保持する資源を待っています。すなわち $G$ のすべての頂点の出次数は $1$ 以上です。$D$ は有限集合なので、より $G$ は有向閉路 $P_1 \to P_2 \to \cdots \to P_k \to P_1$ を含みます。辺 $P_i \to P_{i+1}$ の定義がまさに「$P_i$ は $P_{i+1}$ が保持する資源を待つ」なので、これが循環待ちです。なお閉路の長さは $2$ 以上です（自分が保持している資源を自分で待つことは、同一資源の再帰的取得を許さない通常のミューテックスでは循環待ちの一種として同様に扱えます）。は「4 条件が必要」と言っているので、対偶として**どれか 1 つを成り立たなくすればデッドロックは起きません**。実務での対策はこの 4 つのどれを崩すかで分類できます。 | 崩す条件 | 手法 | 代償 | |---|---|---| | 相互排除 | 読み取り専用資源、ロックフリーデータ構造 | 適用できる資源が限られる | | 保持と待ち | 必要な資源を最初に一括取得する | 資源の利用効率が落ちる、事前に全要求を知る必要がある | | 横取り不可 | 取得に失敗したら保持中の資源を手放してやり直す | ライブロックの危険、処理のやり直し費用 | | 循環待ち | 資源に全順序を定め、常に昇順に取得する | 設計時に全順序を定める規律が要る | 最後の行が実装上もっとも使われる方法で、Linux カーネルのロック順序の規約はまさにこれです。正しさはで証明してもらいます。 ## 7. 演習 32 ビットの仮想アドレス空間、ページサイズ 8 KiB、1 つのページテーブル項目が 4 バイトの計算機を考えます。1 段のページテーブルを使うとき、1 プロセスあたりのページテーブルの容量を求めてください。また、ページサイズを 4 KiB にしたときと比べて何倍になるかを述べてください。 $8\ \mathrm{KiB} = 2^{13}$ なのでオフセットは 13 ビット、仮想ページ番号は $32 - 13 = 19$ ビットです。項数は $2^{19} = 524288$、1 項 4 バイトなので $$ 2^{19} \times 4 = 2^{21} = 2097152\ \text{バイト} = 2\ \mathrm{MiB}. $$ ページサイズ 4 KiB のときは VPN が 20 ビットで $2^{20} \times 4 = 4$ MiB でした。したがって $2\ \mathrm{MiB} / 4\ \mathrm{MiB} = 1/2$ 倍、つまり半分になります。ページを大きくするとページテーブルは小さくなりますが、代わりに 1 ページ内の使われない部分（内部断片化）が平均してページサイズの半分だけ増えます。この綱引きが、ページサイズが 4 KiB 前後に落ち着いている理由です。時刻 $0$ に 4 つのプロセスが到着し、バースト時間が $t_1 = 8,\ t_2 = 4,\ t_3 = 9,\ t_4 = 5$ であるとします。切り替え費用は $0$ とします。(a) FCFS（到着順）、(b) SJF、(c) ラウンドロビン（$q = 4$、キューの初期順序は $P_1, P_2, P_3, P_4$、クォンタムを使い切ったプロセスはキューの末尾に戻る）のそれぞれについて平均待ち時間を求め、(c) が (a) より悪くなり得ることを確認してください。 **(a) FCFS**：実行順は $P_1, P_2, P_3, P_4$。待ち時間は $0,\ 8,\ 12,\ 21$ なので $$ \bar{w} = \frac{0+8+12+21}{4} = \frac{41}{4} = 10.25 . $$ **(b) SJF**：バースト昇順は $P_2(4), P_4(5), P_1(8), P_3(9)$。待ち時間は $0,\ 4,\ 9,\ 17$ なので $$ \bar{w} = \frac{0+4+9+17}{4} = \frac{30}{4} = 7.5 . $$ よりこれが最小です。 **(c) ラウンドロビン $q=4$**：実行を順に追います。 | 区間 | 実行 | 残り | 実行後のキュー | |---|---|---|---| | $[0,4)$ | $P_1$ | 4 | $P_2, P_3, P_4, P_1$ | | $[4,8)$ | $P_2$ | 0（完了） | $P_3, P_4, P_1$ | | $[8,12)$ | $P_3$ | 5 | $P_4, P_1, P_3$ | | $[12,16)$ | $P_4$ | 1 | $P_1, P_3, P_4$ | | $[16,20)$ | $P_1$ | 0（完了） | $P_3, P_4$ | | $[20,24)$ | $P_3$ | 1 | $P_4, P_3$ | | $[24,25)$ | $P_4$ | 0（完了） | $P_3$ | | $[25,26)$ | $P_3$ | 0（完了） | — | 完了時刻は $c = (20, 8, 26, 25)$。到着が $0$ なので待ち時間は $c_i - t_i$ より $12,\ 4,\ 17,\ 20$ で $$ \bar{w} = \frac{12+4+17+20}{4} = \frac{53}{4} = 13.25 . $$ FCFS の $10.25$ より悪くなりました。バースト時間が近い値ばかりの場合、ラウンドロビンは全員の完了を一様に後ろへずらすだけで、平均待ち時間には不利に働きます。一方で応答時間は FCFS の $(0+8+12+21)/4 = 10.25$ に対し $(0+4+8+12)/4 = 6$ に改善しており、の趣旨どおりです。と同じ参照列 $\sigma = 1,2,3,4,1,2,5,1,2,3,4,5$ を、今度は LRU で処理してください。フレーム 3 個の場合とフレーム 4 個の場合のページフォルト回数をそれぞれ求め、と整合することを確かめてください。 **フレーム 3 個**（集合の中身を新しい順で書きます）。 $1$：F、$[1]$。$2$：F、$[2,1]$。$3$：F、$[3,2,1]$。$4$：F、最も古い $1$ を追い出して $[4,3,2]$。$1$：F、$2$ を追い出して $[1,4,3]$。$2$：F、$3$ を追い出して $[2,1,4]$。$5$：F、$4$ を追い出して $[5,2,1]$。$1$：H、$[1,5,2]$。$2$：H、$[2,1,5]$。$3$：F、$5$ を追い出して $[3,2,1]$。$4$：F、$1$ を追い出して $[4,3,2]$。$5$：F、$2$ を追い出して $[5,4,3]$。フォルトは **10 回**です。 **フレーム 4 個**。 $1,2,3,4$：4 回とも F、$[4,3,2,1]$。$1$：H、$[1,4,3,2]$。$2$：H、$[2,1,4,3]$。$5$：F、最も古い $3$ を追い出して $[5,2,1,4]$。$1$：H、$[1,5,2,4]$。$2$：H、$[2,1,5,4]$。$3$：F、$4$ を追い出して $[3,2,1,5]$。$4$：F、$5$ を追い出して $[4,3,2,1]$。$5$：F、$1$ を追い出して $[5,4,3,2]$。フォルトは **8 回**です。 $8 \le 10$ なのでフレームを増やすとフォルトは減っており、の $F_{m+1} \le F_m$ と整合します。さらに各時点でのメモリ内容を比べると、たとえば 7 回目（$5$ の参照後）は 3 フレームで $\{5,2,1\}$、4 フレームで $\{5,2,1,4\}$ となっており、包含関係 $S_3 \subseteq S_4$ も確かめられます。資源の全体集合 $R$ に全順序 $\prec$ を定め、すべてのプロセスが次の規律に従うとします：**あるプロセスが資源 $r$ を要求するとき、そのプロセスが現在保持しているどの資源 $r'$ についても $r' \prec r$ である**（つまり資源は必ず $\prec$ の昇順にしか取得しない）。このとき、デッドロックは決して発生しないことを証明してください。背理法で示します。デッドロックが発生したとすると、の条件 4 より、プロセスの列 $P_1, P_2, \ldots, P_k$（$k \ge 2$）が存在して、各 $i$ について $P_i$ は $P_{i+1}$ が保持している資源を待っています（添字は $\bmod\ k$）。 $P_i$ が待っている資源を $r_{i+1}$ と書きます（これは $P_{i+1}$ が保持しています）。添字を合わせると、各 $i$ について次の 2 つが同時に成り立ちます。 - $P_i$ は資源 $r_{i+1}$ を要求している。 - $P_i$ は資源 $r_i$ を保持している（$r_i$ は $P_{i-1}$ が待っている資源であり、$P_i$ が保持しているものです）。規律より、要求する資源は保持している資源より $\prec$ で真に大きいので $$ r_i \prec r_{i+1} \qquad (i = 1, 2, \ldots, k,\ \text{添字は} \bmod k). $$ これを $i = 1$ から順に連ねると $$ r_1 \prec r_2 \prec \cdots \prec r_k \prec r_1 $$ となり、$\prec$ の推移律から $r_1 \prec r_1$ を得ます。$\prec$ は全順序なので反射的でなく（$r \prec r$ は成り立たない）、矛盾です。よってデッドロックは発生しません。 **補足**：この論法はが保証する閉路の存在を、$\prec$ という「一方向にしか進めない量」の存在と衝突させています。同じ構造は、有限の半順序集合に無限下降列が存在しないことを使う議論一般に現れます。実務ではこの $\prec$ を「ロックの取得順序の規約」として文書化し、Linux カーネルの lockdep のような検証機構で違反を実行時に検出します。 ## 参考文献 - R. H. Arpaci-Dusseau, A. C. Arpaci-Dusseau, *Operating Systems: Three Easy Pieces*, Arpaci-Dusseau Books, 2018 — 仮想化（プロセス・スケジューリング・ページング）と並行性の章。全文が [公式サイト](https://pages.cs.wisc.edu/~remzi/OSTEP/) で公開されています。 - A. Silberschatz, P. B. Galvin, G. Gagne, *Operating System Concepts*, 10th ed., Wiley, 2018 — プロセスとスレッド、CPU スケジューリング、メインメモリと仮想記憶、デッドロックの各章。 - A. S. Tanenbaum, H. Bos, *Modern Operating Systems*, 4th ed., Pearson, 2015 — プロセスとスレッド、メモリ管理の章。 - L. A. Belady, R. A. Nelson, G. S. Shedler, "An anomaly in space-time characteristics of certain programs running in a paging machine", *Communications of the ACM* 12 (1969), 349–353. [doi:10.1145/363011.363155](https://doi.org/10.1145/363011.363155) - E. G. Coffman, M. J. Elphick, A. Shoshani, "System Deadlocks", *ACM Computing Surveys* 3 (1971), 67–78. [doi:10.1145/356586.356588](https://doi.org/10.1145/356586.356588) - A. Waterman, K. Asanović (eds.), *The RISC-V Instruction Set Manual, Volume II: Privileged Architecture* — 特権モード（M/S/U）、`ecall` と `sret`、`satp` レジスタと Sv39 のページテーブル形式。[RISC-V 仕様ページ](https://riscv.org/technical/specifications/) ## Appendix: 特権モードの実際 **x86-64 の場合。** 歴史的経緯から 4 つの特権レベル（リング 0〜3）を持ちますが、実際に使われるのはリング 0（カーネル）とリング 3（ユーザ）の 2 つだけです。システムコールは `syscall` 命令で、復帰は `sysret`。ページテーブルの基底は CR3 レジスタが保持し、4 段（PML4 → PDPT → PD → PT）をたどって 48 ビットの仮想アドレスを変換します。仮想化支援（VT-x）が導入されてからは、リング 0 のさらに下に「ルートモード」が加わり、ハイパーバイザがゲスト OS のカーネルを管理できるようになりました。 **RISC-V の場合。** 設計が新しいぶん整理されており、マシンモード（M）、スーパーバイザモード（S）、ユーザモード（U）の 3 段階です。M モードはブートとファームウェアが使い、OS のカーネルは S モードで動きます。システムコールは `ecall` 命令で、U モードから実行すると S モードのトラップハンドラ（`stvec` レジスタが指す番地）へ飛びます。復帰は `sret`。ページテーブルの基底とアドレス変換方式は `satp` レジスタが一体で持ち、Sv39（3 段、39 ビット仮想アドレス）、Sv48（4 段）、Sv57（5 段）から選べます。仕様書が短く読み通せるので、この記事で扱った仕組みが実際のハードウェアでどう規定されているかを確かめるには、RISC-V の特権仕様が最良の教材だと思います。 **なぜ 2〜3 段階で足りるのか。** 特権レベルを細かく分けても、結局は「境界が破れないこと」だけが本質だからです。境界を 1 枚引ければ、その内側でさらに細かい保護をしたいときは、同じ仕組みを再帰的に適用する（仮想機械を作る、あるいはユーザ空間でサンドボックスを作る）ほうが単純で、検証もしやすくなります。次章の [プログラミング言語論](/computer-science/cs-basics/programming-language-theory) では、この「境界を引く」という発想が言語の型システム（）という別の形でも現れることを見ます。