この記事について

AWS認定を持っていても、「OSが内部で何をしているか」は一度も体系的に学んでいない——という人は多いはず。SAAやDVAが教えてくれるのは「マネージドサービスの使い方」であって、その裏で動いているLinuxカーネルの中身ではない。EC2インスタンスが急に重くなったとき、「なんとなくスケールアップする」のと「CPU待ちなのかメモリなのかI/Oなのかを切り分けてから対処する」のとでは、エンジニアとしての解像度がまったく違う。

このシリーズは、資格試験ではカバーされないOS/コマンド/ネットワークの土台を1からやり直すための連載。第1回のテーマは「OSは結局何をしているのか」というド直球の問い。

ただし単なる用語集にはしたくない。「なぜその設計になったのか」を実際の論文や技術文書まで遡って理解するのがこの記事の狙い。丸暗記ではなく、一度理解したら忘れない知識にする。

全体像:OSの仕事は3つしかない

OSの仕事は突き詰めると3つ。誰が(プロセス管理)・どこに(メモリ管理)・どう残すか(ファイルシステム)。この3語で全部覚えられる。

それぞれ「何が問題だったか→どう解決したか→その解決策の限界は何か→今はどうなっているか」の順で見ていく。

① プロセス管理:「誰が」CPUを使うか

プロセスとスケジューリング

1つのCPUコアは同時に1命令列しか実行できないが、手元のPCやサーバーでは何十ものプロセスが同時に動いているように見える。これは錯覚で、OSがミリ秒単位でプロセスを切り替えている(コンテキストスイッチ)。次にどのプロセスへCPUを渡すかを決めるのがスケジューラの仕事。

CFSの仕組み:vruntimeと赤黒木

2007年、Linux kernel 2.6.23でIngo Molnarが実装したCompletely Fair Scheduler(CFS)は、長らくLinuxの標準スケジューラだった。各タスクに**vruntime(仮想実行時間)**という値を持たせ、「常にvruntimeが最小のタスクを次に実行する」というルール一本で公平性を実現する。CPUを使えば使うほどvruntimeは増えていくが、その増加ペースは優先度(nice値)によって重み付けされていて、nice値が低い(優先度が高い)タスクほどvruntimeの増え方が緩やかになる仕組み。

実装上は、全実行可能タスクを赤黒木(Red-Black Tree)で管理し、vruntime最小のタスク=木の一番左のノードをO(log n)で選び出す。この発想のルーツは実はネットワークの世界にある。パケットスイッチングで帯域を公平に配分するfair queuingという概念をCPU時間の配分に輸入したのがCFSの理論的背景で、その中間にはstride schedulingという手法も存在した。

なぜCFSは「完全に」公平ではなかったのか

CFSは名前に反して、実際には多くのチューニングパラメータを抱えることになった。より本質的な弱点は、vruntimeの大小しか見ていないため緊急性(latency)の概念がないこと。I/O待ちから起きたばかりのタスクはvruntimeが小さいので結果的にすぐ実行されるが、これは「たまたまそうなる」だけで、そのタスクが本当に緊急かどうかをCFSは判断できない。ネットワークパケット処理のように本当に低遅延が必要なタスクと、たまたまスリープから復帰しただけのバッチタスクを、CFSは区別できなかった。

よくある誤解:「nice値を変えれば処理そのものが速くなる」わけではない。niceはあくまでCPU時間の配分比率(相対的な優先度)を変えるだけで、シングルスレッドの処理速度自体を引き上げる魔法ではない。CPUが空いている状況では、nice値をどう変えても体感速度は変わらないことも多い。

【改善案】EEVDF — 2023年、CFSはこう置き換えられた

この弱点を解決したのが、Linux kernel 6.6(2023年10月)でPeter Zijlstraが実装したEarliest Eligible Virtual Deadline First(EEVDF)。理論的な土台はIon StoicaとHussein Abdel-Wahabが1995年に発表した論文「Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation」で、発表から28年後にようやく主要OSへ実装されたことになる。

EEVDFはvruntimeに加えて2つの概念を導入した。

lag:そのタスクが「本来もらえるはずのCPU時間」に対して貸し・借りがどれだけあるか
virtual deadline:そのタスクが次にいつまでにCPUをもらうべきかという仮想的な締め切り

lagが0以上(=まだ十分にCPUをもらっていない、eligibleな状態)のタスクに絞り込み、その中でvirtual deadlineが最も早いものを選ぶ。「最小vruntimeを選ぶ」から「最も差し迫ったタスクを選ぶ」に変わったことで、レイテンシに敏感なタスクを理論的根拠を持って優先できるようになった。

余談だが、EEVDFはCFSの内部実装(負荷計算・cgroup連携など)の大半をそのまま引き継いだ「進化形」で、ゼロから作り直したわけではない。カーネル内部では今もfair_sched_classという名前が使われ続けていて、「CFS」という名前だけが実態と少しズレたまま生き残っている——地味に豆知識として覚えやすいポイント。

手を動かす

# CPU使用率順にプロセスを見る
ps aux --sort=-%cpu | head -10

# 自分のシェルのスケジューリング詳細(vruntime, deadlineなどが見える)
cat /proc/$$/sched

/proc/$$/schedを実行すると、実際にse.vruntimeや(kernel 6.6以降なら)deadline関連のフィールドが数値で見える。理論を読んだだけで終わらせず、自分のプロセスの数値を一度眺めてみると記憶に残りやすい。

3行まとめ
・CFSは「vruntime最小のタスクを選ぶ」だけのシンプルな仕組みだったが、緊急性を判断できなかった
・EEVDFは「virtual deadline」と「lag」を導入し、2023年にCFSを置き換えた(理論は1995年の論文が土台)
・nice値は速度を上げる魔法ではなく、あくまでCPU時間配分の相対比率を変えるだけ

② メモリ管理:「足りない」を「足りているように見せる」技術

仮想メモリという発明

物理メモリ(RAM)には限りがあるが、OSは各プロセスに「自分専用の広大なメモリ空間を独占している」かのような錯覚を見せる。実現手段がページング——仮想アドレスを固定サイズの「ページ」単位に区切り、ページテーブルを介して物理メモリの「フレーム」に対応させる。CPUは変換の高速化のためTLB(Translation Lookaside Buffer)というキャッシュを持っていて、ページテーブルの参照を毎回メモリアクセスしなくて済むようにしている。仮想アドレスに対応する物理ページがまだメモリに載っていなければページフォルトが発生し、OSがディスク(スワップ)から該当ページを読み込んでから処理を再開する。

全ページを常に物理メモリに載せておく必要はなく、今使っていないページはスワップに追い出しておいて必要な瞬間に呼び戻せばいい——これが「足りないメモリを足りているように見せる」からくり。

スラッシングという病、そしてワーキングセットモデル

このやり方には落とし穴がある。「必要になったら呼び戻す」を繰り返しすぎると、CPUがページの出し入れ(スワップイン/アウト)だけに時間を費やし、肝心の計算がほぼ進まなくなる。この現象に**スラッシング(thrashing)**と名付け、原因と対策を理論化したのが、Peter J. Denningが1968年に発表した2本の論文。

「Thrashing: Its Causes and Prevention」(Fall Joint Computer Conference 1968)
「The Working Set Model for Program Behavior」(Communications of the ACM, 11(5), 323–333)

Denningが提唱したワーキングセットモデルの核心は、「プロセスは直近の時間窓τの中で、実はごく一部のページしか繰り返し使っていない」という観察(局所性の原理、locality of reference)。直近τの間に参照されたページ集合W(t, τ)を「ワーキングセット」と呼び、これをまるごと物理メモリに載せておければスラッシングは起きない、というのがDenningの主張だった。

重要なのは、ワーキングセットより小さいメモリしか割り当てないと、理論的に必ずスラッシングが起きるということ。メモリ不足によるパフォーマンス劣化は「気合が足りない」系の問題ではなく、数学的に説明できる必然の現象ということになる。AWSでmemory-optimizedなインスタンスタイプ(Rシリーズなど)を選ぶべき場面があるのも、突き詰めればワークロードのワーキングセットのサイズに見合ったメモリを確保しているかどうかの話。

この論文は1968年のACMベストペーパー賞を受賞し、以降のあらゆる階層キャッシュ設計——CPUキャッシュ、ページキャッシュ、CDN、ブラウザキャッシュ——の理論的な原型になっている。LRU(Least Recently Used)系アルゴリズムの正当性も、突き詰めればこの局所性の原理に行き着く。半世紀以上前の論文が今も現役という意味では、CS分野で最も息の長い理論の1つ。

【現代の実装】Linuxはワーキングセットをどう近似しているか

Linuxカーネルは正確なワーキングセットを常時計算するコストを嫌い、active/inactiveという2つのLRUリストでこれを近似している。よく使われるページはactiveリストに、しばらく使われていないページはinactiveリストに移され、メモリが逼迫するとinactiveリストから優先的に回収(reclaim)される。

それでもメモリが足りなくなった場合の最終防衛ラインがOOM Killer——スコア(oom_score)が最も高い、つまり「殺しても被害が少なそうな」プロセスを強制終了してシステム全体の停止を防ぐ。コンテナ環境ではさらにcgroups v2のmemory.maxでコンテナごとに上限を設け、あるコンテナのメモリ不足が他のコンテナを巻き込まないよう隔離している。

よくある誤解:free -hのavailableが少ない=メモリ不足、とは限らない。Linuxは空いているメモリを積極的にページキャッシュ(buff/cache)として使い切る設計になっていて、これは「使われてはいるが必要なら即座に手放せる」領域。本当の逼迫を見るならavailable列と、vmstatのswap in/out(si/so)を見るべきで、buff/cacheが多いこと自体はむしろ健全な状態。

手を動かす

# メモリ使用状況の全体像(available列を見る)
free -h

# 仮想メモリの詳細統計。si/soの値が動いていたらスラッシングの兆候
vmstat 1 5

# 特定プロセスの実メモリ使用量
cat /proc/$$/status | grep VmRSS

3行まとめ
・仮想メモリは「足りないメモリを足りているように見せる」ための仕組み(ページング+TLB)
・スラッシングとワーキングセットモデルは1968年のDenningの論文が起源、半世紀経った今も現役理論
・Linuxはactive/inactiveリストで近似し、最終手段としてOOM Killerが動く。free -hのavailableで判断すること

③ ファイルシステム:なぜ電源を急に切ってもデータが壊れないのか

inodeという分離の発想

ファイルシステムは、ファイル名とその中身(データブロック)を分離して管理している。この「メタデータ」を持つ管理単位がinode。ファイル名からinode番号を引き、inodeからデータブロックの場所を辿る、という2段構えになっている。

電源断でなぜデータが壊れるのか

ファイルへの書き込みは実は「データブロックを書く」「inodeを更新する」「ディレクトリエントリを更新する」など複数のステップに分かれている。この途中で電源が落ちると、一部だけ更新されて残りが未更新という中途半端な状態が生まれ、最悪の場合ファイルシステム自体が読めなくなる。

ジャーナリングという発明

この問題への回答がジャーナリング。データベースのWrite-Ahead Logging(WAL)と発想は同じで、実際の構造を更新する前に「これから何をするか」をまずジャーナル(ログ)へ書き込んでおく。

クラッシュ後の起動時にはジャーナルの内容を頭から再生(replay)するだけで済むので、ディスク全体をスキャンするfsckのような重い整合性チェックが基本的に不要になる。

ext3/ext4の3つのモード、安全性と速度のトレードオフ

ext3/ext4のジャーナリングには3段階のモードがあり、「何をジャーナルに書くか」で安全性と速度が変わる。

モード	ジャーナル対象	安全性	速度
journal	メタデータ+データ本体の両方	最も高い	最も遅い
ordered(デフォルト)	メタデータのみ、ただしデータを先に書いてからコミット	中	中
writeback	メタデータのみ、順序保証なし	低い	最も速い

典型的な「一貫性 vs 性能」のトレードオフで、DBのisolation levelの考え方とも通じる。

よくある誤解:「ジャーナリングがあれば絶対にデータは失われない」わけではない。journalモードでもファイルシステムの構造が壊れないことは保証されるが、モードによっては保存したはずのファイルの中身が失われることはあり得る。「壊れない」のはあくまで構造の整合性であって、書き込み内容そのものではない点は誤解されやすい。

XFSという別系統、なぜRHEL系はXFSを選んだのか

ext系とは独立に発展したのがXFS。1993年、SGIがワークステーションOS IRIX向けに開発した高性能ジャーナリングファイルシステムで、後にLinuxへ移植された。大容量ファイルや並列I/Oに強い設計が特徴で、RHEL7以降ではデフォルトファイルシステムに採用されている。SI業界でRHEL系サーバーを触る機会が多いなら、ext4だけでなくXFSの存在も知っておいて損はない。

【改善案/別解】ジャーナリングを使わないCoWという発想

ジャーナリングとは根本的に異なるアプローチも存在する。BtrfsやZFSが採用する**Copy-on-Write(CoW)**は、既存データを上書きするのではなく、変更内容を常に新しい場所へ書き込み、最後にメタデータのポインタだけを新しい場所に切り替える。

上書きが発生しないので、途中で電源が落ちても「新しい書き込みが中途半端に残っているだけ」で、古いデータへのポインタは無傷のまま——ジャーナリングとは異なる方法で同じ整合性の問題を解決している。副産物として、ポインタを切り替える前の状態を保持しておくだけでスナップショット機能がほぼタダで手に入るのもCoW系の強み。

手を動かす

# ファイルシステムの種類を確認
df -Th

# マウントオプションを確認(ジャーナリングモードもここに出る)
mount | grep " / "

# ext4のジャーナリング設定を直接見る
sudo dumpe2fs -h /dev/sda1 | grep -i journal

3行まとめ
・ジャーナリングは「変更内容を先にログへ書く」ことでクラッシュ後の高速な整合性復元を実現する仕組み
・ext4は3モードで安全性と速度をトレードオフできる、XFSは別系統で大容量・並列I/Oに強い
・Btrfs/ZFSのCoWはジャーナリングとは違う発想で同じ問題を解決し、スナップショットも実現する

全体まとめ

領域	解決する問題	中核の概念	起点となった論文/技術	現在のLinux実装
①プロセス管理	複数タスクへのCPU時間の公平配分	vruntime → virtual deadline	Stoica & Abdel-Wahab (1995)	CFS → EEVDF(kernel 6.6〜)
②メモリ管理	仮想空間の提供とスラッシング回避	ワーキングセット	Denning (1968)	active/inactive LRU, OOM Killer, cgroups
③ファイルシステム	クラッシュ時のデータ整合性	ジャーナリング / CoW	XFS(1993, SGI), ext3(2001〜)	ext4/XFS, Btrfs/ZFS

3つに共通しているのは、「理論(論文)が先にあり、実装が何年〜何十年か遅れて追いついてくる」という構図。EEVDFは28年、ワーキングセットモデルに至っては半世紀以上、現役の設計思想として生き続けている。誰が(プロセス)・どこに(メモリ)・どう残すか(ファイルシステム)——この3語をキーに、迷ったら本記事に戻ってくれば思い出せるはず。

次回予告

次回はブートプロセス編。電源ボタンを押してからログインプロンプトが出るまでに、BIOS/UEFI→ブートローダ→カーネル→systemdの間で何が起きているかを追う。

参考文献

Denning, P.J. (1968). "The Working Set Model for Program Behavior." Communications of the ACM, 11(5), 323–333.
Denning, P.J. (1968). "Thrashing: Its Causes and Prevention." Proceedings of the Fall Joint Computer Conference (FJCC'68), 915–922.
Stoica, I., & Abdel-Wahab, H. (1995). "Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation." Technical Report.
Linux Kernel Documentation, "EEVDF Scheduler" (docs.kernel.org/scheduler/sched-eevdf.html)
Linux Kernel 6.6 リリース関連(2023年10月、EEVDFマージ)