第 10 章オペレーティングシステム¶

まえがき — コンピュータの「裏方の管理人」¶

PC の電源を入れると、なぜ複数のアプリが「同時に」動くの? メモリは 16 GB しかないのに、なぜ「無限に使える」ように見える? Ctrl + C でプロセスが止まるのはなぜ? Docker のコンテナってどうやってアプリを「閉じ込めて」いるの?

これらの謎を解くのが オペレーティングシステム (OS) です。

OS は「ハードウェアを使いやすく見せ、複数のプログラムが仲良く動けるよう調整する」存在。Windows、macOS、Linux、iOS、Android はすべて OS。OS を知らないと、低レイヤの不思議が一生「魔法」のまま になります。

🎯 章の目標

OS が「抽象化」と「資源管理」の 2 つを担うことを理解する

プロセス・スレッド・スケジューリング・同期・デッドロック・メモリ管理・ファイルシステムを語れる

システムコール、カーネル/ユーザ空間、コンテキストスイッチが何かが分かる

仮想化・コンテナ・並行プログラミングの基礎を獲得する

10.1 OS の役割¶

10.1.1 3 つの仕事¶

抽象化: CPU・メモリ・ディスク・ネットワークを 使いやすいインターフェース に変える
資源管理: 複数のプロセスに 公平・効率的 に資源を分配
隔離・保護: プロセス同士、ユーザー同士の干渉を防ぐ

10.1.2 例: ファイル¶

ハードディスクは本来「セクター（512 バイトのブロック）の集まり」。OS が「ファイル」「フォルダ」「パス」という抽象を提供してくれるから、open("hello.txt") で済みます。

10.1.3 カーネルとユーザ空間¶

┌──────────────────────────────────┐
│       ユーザ空間 (アプリ)           │
│  Chrome, VSCode, Python, ...     │
├──────────────────────────────────┤
│       カーネル空間 (OS の核)        │
│  メモリ管理, スケジューラ, FS, ...   │
├──────────────────────────────────┤
│         ハードウェア                 │
│  CPU, RAM, Disk, NIC, ...        │
└──────────────────────────────────┘

ユーザ空間からカーネルへ移るには システムコール。open, read, write, fork, exec などが代表。

CPU は 特権レベル（リング、モード）で 2 つの世界を分けています。アプリが暴走してもカーネルが守られる仕組み。

10.2 プロセスとスレッド¶

10.2.1 プロセス¶

「実行中のプログラム + その状態」。

各プロセスは: - 独自のアドレス空間 - ファイルディスクリプタ - 環境変数 - プロセス ID (PID)、親 PID

を持ちます。

$ ps aux
USER  PID  COMMAND
root    1  /sbin/init
user 1234  /usr/bin/firefox
user 5678  /usr/bin/code

10.2.2 fork / exec / wait¶

Unix の典型的な API。

pid_t pid = fork();
if (pid == 0) {
    // 子プロセス
    execlp("ls", "ls", "-l", NULL);
} else {
    // 親プロセス
    wait(NULL);
}

fork(): プロセスを複製
exec(): 別プログラムに置換
wait(): 子の終了を待つ

シェルの実行モデルは「fork して子で exec、親で wait」の繰り返しです。

10.2.3 スレッド¶

プロセス内の実行単位。同じアドレス空間を共有するので、データの受け渡しが楽だが、競合のリスクが大きい。

	プロセス	スレッド
メモリ	独立	共有
生成コスト	高	低
通信	IPC	直接共有
安全性	高	低 (要ロック)

実装: - POSIX threads (pthread) - Windows threads - ユーザレベルスレッド (緑色スレッド) は OS から見えない、軽量

10.2.4 コンテキストスイッチ¶

CPU を別プロセス/スレッドに切り替える操作。

「レジスタ・PC・スタック・ページテーブルを保存・復元」する。コストは数 µs。これが多発するとパフォーマンスが落ちます。

10.2.5 プロセスの状態¶

stateDiagram-v2
    [*] --> Ready: 生成
    Ready --> Running: スケジュール
    Running --> Ready: タイマー切れ
    Running --> Waiting: I/O 開始
    Waiting --> Ready: I/O 完了
    Running --> [*]: 終了

    note right of Running: CPU を使っている
    note left of Ready: CPU 待ち
    note right of Waiting: I/O 完了待ち

10.3 スケジューリング — CPU をどう分けるか¶

10.3.1 評価指標¶

スループット (単位時間あたり完了数)
応答時間
ターンアラウンド時間
待機時間
公平性

10.3.2 古典アルゴリズム¶

名前	動作	長所	短所
FCFS	来た順	単純	長いジョブで詰まる
SJF	短いジョブ優先	平均待機最少	長いジョブが飢餓
Round Robin	時間切替	公平	切り替えコスト
優先度	順位づけ	重要を先に	飢餓
MLFQ	動的優先度	適応的	複雑

10.3.3 Linux CFS (Completely Fair Scheduler)¶

「仮想実行時間」を最小化する木構造で管理。各プロセスを「公平に少しずつ進める」発想。

赤黒木 (第 7 章) を使い、最小ノードを取り出すのが \(O(\log n)\)。

10.3.4 リアルタイムスケジューリング¶

ハードリアルタイム: 締切違反は致命 (医療、航空、自動運転)
ソフトリアルタイム: 望ましくないが許容 (動画再生)

EDF (Earliest Deadline First)、Rate Monotonic などの手法。

10.4 同期 — 並行プログラムの罠¶

10.4.1 競合状態 (Race Condition)¶

// グローバル変数 counter を 2 スレッドが操作
counter = counter + 1;   // ← 非アトミック！

実際は:

sequenceDiagram
    participant A as Thread A
    participant M as メモリ (counter)
    participant B as Thread B

    Note over M: counter = 5
    A->>M: read (5)
    B->>M: read (5)
    A->>M: write (5+1=6)
    B->>M: write (5+1=6)
    Note over M: counter = 6 (期待 7 なのに!)

両スレッドが「5 を読んでから書く」順序が交差して、結果が 1 つ失われています。これが 競合状態 (race condition)。

これが 競合状態。多くのバグの原因。

10.4.2 相互排他 (Mutual Exclusion)¶

「1 度に 1 スレッドだけが入れる領域」を作る:

TestAndSet, Compare-And-Swap (CAS)¶

ハードウェアの不可分命令。「読んで、比較して、書く」を 1 ステップで。

CAS(addr, expected, new):
    if *addr == expected:
        *addr = new
        return true
    return false

ミューテックス (Mutex)¶

import threading
lock = threading.Lock()

def increment():
    with lock:
        counter += 1

セマフォ¶

数値カウンタを持つロック。\(N\) 個までの同時アクセスを許可。リソースプール管理に。

モニタ¶

Java の synchronized、C# の lock。「メソッド全体を排他」する高水準仕組み。

スピンロック vs ブロッキングロック¶

スピンロック: ループで待つ（CPU 消費）。短い待ちなら効率的
ブロッキングロック: スリープして待つ（コンテキストスイッチ）。長い待ち向き

10.4.3 条件変数¶

「ある条件が成り立つまで待つ」仕組み:

not_empty = threading.Condition()

# 消費者
with not_empty:
    while queue_empty():
        not_empty.wait()
    item = queue.pop()

# 生産者
with not_empty:
    queue.push(item)
    not_empty.notify()

生産者-消費者問題、有限バッファで使います。

10.4.4 古典的な並行性問題¶

食事する哲学者問題¶

5 人の哲学者が円卓に座り、フォークが 5 本。両側のフォークを取らないと食べられない。全員が左を取った瞬間にデッドロック が起こる例。

対策: 「フォークの取得順を統一」「片方だけ右から取る」。

読者・書き手問題¶

「読者は同時に何人でも、書き手は 1 人だけ」。読み書きロック。

寝ている理髪師問題¶

「客がいるなら散髪、いないなら寝る」。条件変数の典型例。

10.4.5 メモリモデル¶

CPU はメモリ操作を 再順序化 します。複数スレッドで共有変数を扱うときは:

メモリバリア (std::atomic_thread_fence)
アトミック変数 (std::atomic, Java の volatile)
happens-before 関係

を意識する必要があります。

10.4.6 ロックフリー / Wait-free¶

CAS だけで構築する高度な同時並行データ構造。

メリット: デッドロックなし、優先度反転なしデメリット: 実装が極めて難しい

LMAX Disruptor、Java の ConcurrentHashMap などで採用。

10.5 デッドロック — 並行性の地獄¶

10.5.1 4 つの必要条件 (Coffman 条件)¶

相互排他
保持と待ち
横取り不可
循環待ち

すべて満たすとデッドロック発生可能。

    Thread A
    ┌───────┐
   持つ      待つ
    │        ↓
    A───→ Lock1
              ↑
    待つ      持つ
    │        │
    B───→ Lock2
    └───────┘
    Thread B

10.5.2 対処戦略¶

予防: 4 条件のいずれかを破る (例: ロック取得順を統一)
回避: 銀行家アルゴリズム
検出と回復: 待機グラフでサイクル検出 → プロセス kill
無視: 発生時に再起動 (ダチョウ算法、デスクトップ OS の現実解)

実務では「ロック取得順を統一」+「タイムアウト」が現実的解です。

10.6 メモリ管理¶

10.6.1 ページング (再掲)¶

仮想アドレス空間を 4 KB のページに分割し、物理フレームに対応付け。詳細は第 9 章。

10.6.2 ページ置換アルゴリズム¶

物理メモリ満杯時、どのページを追い出すか:

名前	動作
FIFO	最初に入ったもの
LRU	一番長く使われていないもの
LFU	一番使用頻度が低いもの
Clock	LRU の近似、効率的
ARC	LRU + LFU のハイブリッド
OPT	最適 (理論上、未来予知が必要)

10.6.3 スラッシング¶

物理メモリが足りず、ページフォルトばかり発生。プロセスを減らすかメモリを増やすしかない。

10.6.4 malloc 内部¶

C ランタイムが、OS から大きなブロックをもらい、malloc/free で細かく切り出す。

フリーリスト
ベストフィット / ファーストフィット
スラブアロケータ (カーネル)
jemalloc, tcmalloc (高性能)

10.6.5 ガベージコレクション¶

第 13 章で詳述。Java、Go、Python、JavaScript で使われます。

10.7 ファイルシステム¶

10.7.1 抽象¶

ファイル: バイトの並び + メタデータ
ディレクトリ: 名前 → ファイルの対応
リンク: ハード（同じ inode）/ シンボリック（別ファイル）

10.7.2 inode¶

ファイルのメタデータ: - サイズ - 所有者 - パーミッション - 作成・更新時刻 - データブロックのポインタ

ls -l で見える情報の元。

10.7.3 ext4 など¶

スーパーブロック → inode テーブル → データブロック

直接ブロック・間接ブロック・二重間接で大きなファイルにも対応。

10.7.4 ジャーナリング¶

書き込みを ログに先に書く ことで、クラッシュ時にも整合性を保つ。ext4, XFS, NTFS が採用。

10.7.5 COW (Copy-On-Write)¶

ZFS, Btrfs, APFS。スナップショットが安価。「書き換えるときだけコピー」する仕組み。

10.7.6 分散ファイルシステム¶

NFS, GFS, HDFS, Ceph。第 16 章 (分散) で詳述。

10.7.7 POSIX API¶

int fd = open("hello.txt", O_RDONLY);
char buf[1024];
read(fd, buf, sizeof(buf));
close(fd);

open, read, write, lseek, close, stat, unlink, mmap。

mmap は「ファイルを仮想アドレス空間にマップ」。read/write 不要で 直接アクセス。データベースや巨大ファイルで重要。

10.8 入出力モデル¶

10.8.1 同期 vs 非同期¶

同期 I/O: 完了まで呼び出しスレッドが待つ
非同期 I/O: 完了通知で続きを実行

# 同期
data = file.read()
process(data)

# 非同期 (asyncio)
data = await file.read()
process(data)

10.8.2 イベント駆動 (epoll, kqueue)¶

「1 スレッドで多数のソケット」を扱える仕組み。

select (古い、\(O(n)\))
poll
epoll (Linux), kqueue (BSD/macOS), io_uring (新)

Nginx、Node.js、Redis の高並列性の正体。1 万接続を 1 プロセス で処理可能 (C10K 問題の解)。

10.8.3 バッファリング¶

[ アプリ ] → [ ユーザバッファ ] → [ カーネルバッファ ] → [ ディスクキャッシュ ] → [ 物理ディスク ]

各層でバッファされ、性能と整合性が変わります。fsync() で強制的にディスクへ書く。

10.9 仮想化とコンテナ¶

10.9.1 仮想マシン (VM)¶

ハイパーバイザがハードウェアをエミュレート: - タイプ 1: ベアメタル (Xen, KVM, ESXi) - タイプ 2: ホスト OS の上 (VirtualBox) - ハードウェア支援 (Intel VT-x, AMD-V) で高速

10.9.2 コンテナ¶

OS カーネルを共有 し、ファイルシステム・ネットワーク・PID 空間だけ隔離。

Linux 名前空間 (namespace): PID, NET, MNT, USER...
cgroup: CPU・メモリの上限管理
chroot / pivot_root: ルートファイルシステムの切替

Docker, Podman, containerd はこれらを組み合わせます。

10.9.3 VM vs コンテナ¶

	VM	コンテナ
起動	数十秒	1 秒以下
容量	GB	MB
隔離	強い	弱い (カーネル共有)
性能	やや劣る	ほぼネイティブ
用途	OS の異なる環境	アプリのパッケージ

10.10 ブートとカーネル構造¶

10.10.1 ブートシーケンス¶

電源 ON → BIOS/UEFI → ブートローダ (GRUB) → カーネル → init (systemd) → ログイン

10.10.2 カーネルの種類¶

モノリシックカーネル: Linux, BSD。すべてカーネル空間
マイクロカーネル: Mach, L4, seL4。最小限のカーネル + ユーザ空間サービス
ハイブリッド: Windows NT、macOS

10.11 セキュリティと隔離¶

ユーザ・グループ・パーミッション (rwx)
能力 (capability)、ACL
SELinux, AppArmor
システムコール制限 (seccomp)
ASLR, DEP/NX、スタックカナリア

詳細は第 15 章で。

10.12 並行プログラミングの実践¶

10.12.1 主要なライブラリ¶

# Python: threading
import threading
t = threading.Thread(target=worker)
t.start()

# Python: multiprocessing
from multiprocessing import Process
p = Process(target=worker)
p.start()

# Python: asyncio
import asyncio
async def worker():
    await asyncio.sleep(1)
asyncio.run(worker())

10.12.2 言語別の哲学¶

Java の synchronized, Lock, Concurrent パッケージ
Go の goroutine + channel: 「メモリ共有でなく通信」
Erlang のアクター: 完全分離
Rust の所有権 + Send/Sync: コンパイル時にレース防止

「共有メモリで並行は危険、メッセージで並行は安全」というアクター/CSP の哲学を覚えておくとよいです。

10.13 演習問題¶

fork() 後の親と子の挙動を、PID と変数の値で説明せよ。
Round Robin (タイムスライス 4) で次のジョブ群の実行順序を求めよ: A=10, B=4, C=8。
食事する哲学者問題で、フォークの取得順を統一すればデッドロックを避けられる理由を説明せよ。
ページサイズ 4 KB、仮想アドレス 32 ビット、物理メモリ 1 GB のとき、単一段ページテーブルのサイズを計算せよ。
LRU と Clock の動作を簡単な参照列で比較せよ。
strace ls を実行し、出力されるシステムコールを 10 個分類せよ。
Linux の epoll と select の計算量を比較し、なぜ高並列で epoll が選ばれるか説明せよ。
Docker コンテナと VM のセキュリティ境界の違いを述べよ。
Python の threading と multiprocessing で、CPU バウンド処理の性能を比較するスクリプトを書け。
Linux で ps, top, htop, iotop をそれぞれ使い、何が確認できるかまとめよ。

10.14 この章のまとめ¶

OS は「ハードウェアを使いやすく見せ、資源を巧妙に分配する」中間層。

機能	出番
プロセス・スレッド	並行処理
スケジューリング	CPU の分配
同期	競合状態を防ぐ
メモリ管理	仮想空間の維持
ファイルシステム	データの永続化
I/O モデル	高並列性
仮想化	複数環境を同居

man 2 syscall をすぐ引ける状態を目指しましょう。

10.15 次に読むもの¶

Silberschatz, Galvin, Gagne, Operating System Concepts — 定番
Tanenbaum, Modern Operating Systems
Arpaci-Dusseau, Operating Systems: Three Easy Pieces — 無料、名著
Love, Linux Kernel Development
xv6 (MIT) — 教育用 Unix、ソースを読みながら学ぶ

🌟 メッセージ OS は CS で最も実践的な分野の 1 つ。xv6 を 1 周 すると、自分で書いたカーネルが動く感動を味わえます。

第 10 章 オペレーティングシステム¶