第1章: オペレーティングシステムとファイル抽象化 - Unix I/Oの理論的基盤
1.1 オペレーティングシステムの起源
1.1.1 バッチ処理システムの時代 - 1950年代
現代のファイルI/Oを理解するためには、コンピュータの歴史を遡る必要がある。1950年代初頭、コンピュータはバッチ処理システムとして運用されていた。
1950年代のコンピュータ操作:
1. プログラマがパンチカードにプログラムを書く
↓
2. オペレータがカードをカードリーダーに投入
↓
3. コンピュータがプログラムを実行
↓
4. 結果がプリンタに出力
↓
5. 次のバッチへ
特徴:
- 人間がコンピュータを待つ
- 対話的な操作は不可能
- I/Oはハードウェアに直結
- オペレーティングシステムは存在しない
この時代、プログラマはハードウェアを直接操作していた。ファイルという概念すら存在せず、データはカードやテープに物理的に記録されていた。
1.1.2 Multicsプロジェクト - ファイルシステムの誕生（1964年）
1964年、MIT、AT&T Bell Labs、General Electricは、Multics（Multiplexed Information and Computing Service）プロジェクトを開始した。
Multicsの革命的な概念:
Multicsの設計思想:
1. タイムシェアリング
- 複数のユーザーが同時にコンピュータを使用
- CPUを時間分割して共有
2. 階層的ファイルシステム
- ディレクトリ（フォルダ）の概念
- ファイルのパス名
- 永続的なストレージの抽象化
3. メモリとストレージの統合
- セグメント化されたメモリ空間
- ファイルがメモリにマップされる
4. セキュリティ
- アクセス制御リスト
- ユーザー認証
階層的ファイルシステムの発明は、現代のすべてのOSに影響を与えた。ファイルは物理的なテープやカードではなく、論理的な実体として扱われるようになった。
1.1.3 Unixの誕生 - 「すべてはファイル」（1969年）
Multicsプロジェクトは複雑すぎて失敗したが、そこからUnixが生まれた。Ken ThompsonとDennis RitchieはAT&T Bell Labsで、Multicsの良い部分を残しながらシンプルな設計を目指した。
Unixの核心的哲学「すべてはファイル」:
Unix設計原則 - "Everything is a File"
通常ファイル:
/etc/passwd ← テキストファイル
/bin/ls ← 実行可能バイナリ
デバイス:
/dev/tty ← 端末（キーボード/スクリーン）
/dev/sda ← ハードディスク
/dev/null ← nullデバイス（ビットバケット）
プロセス間通信:
パイプ ← プロセス間のデータ転送
ソケット ← ネットワーク通信
すべてが同じインターフェースで操作できる:
open() - 開く
read() - 読む
write() - 書く
close() - 閉じる
この統一的な抽象化により、プログラマはデバイスの詳細を知らなくてもI/Oを行えるようになった。
1.1.4 C言語との共進化
Dennis Ritchieは1972年、Unixを記述するためにC言語を開発した。これは革命的だった：
/*
C言語以前: アセンブリ言語でOSを記述
例: PDP-11のread操作（アセンブリ）
MOV #fd, R0 ; ファイルディスクリプタ
MOV #buffer, R1 ; バッファアドレス
MOV #count, R2 ; バイト数
TRAP #3 ; システムコール（read）
*/
/*
C言語以後: 高水準言語でOSを記述
同じ操作をCで:
*/
ssize_t bytes = read(fd, buffer, count);
/*
この抽象化により:
1. 可読性の向上
2. 移植性の向上（アーキテクチャ非依存）
3. 開発効率の向上
*/
C言語のシステムコールラッパーは、プログラマとカーネルの間のインターフェースとなった。
1.2 システムコールの理論
1.2.1 ユーザーモードとカーネルモード
現代のCPUは、少なくとも2つの特権レベル（privilege level）を持つ。
メモリ空間の分離:
高位アドレス ─────────────────────────────────
│ │
│ カーネル空間 │
│ (Kernel Space) │
│ │
│ ・カーネルコード │
│ ・デバイスドライバ │
│ ・ファイルシステム │
│ ・プロセス管理 │
│ ・メモリ管理 │
│ │
├───────────────────────────────┤ ← カーネル/ユーザー境界
│ │
│ ユーザー空間 │
│ (User Space) │
│ │
│ ・アプリケーションコード │
│ ・ライブラリ │
│ ・ユーザーデータ │
│ │
低位アドレス ─────────────────────────────────
CPU特権レベル:
- Ring 0: カーネルモード（すべての命令を実行可能）
- Ring 3: ユーザーモード（制限された命令のみ）
なぜ分離が必要か？
- セキュリティ: 悪意あるプログラムがシステムを破壊できない
- 安定性: 一つのプログラムのクラッシュがシステム全体に影響しない
- 抽象化: ハードウェアの詳細をカーネルに隠蔽
1.2.2 システムコールのメカニズム
システムコールは、ユーザープログラムがカーネルにサービスを要求するための唯一の正規ルートである。
システムコールの実行フロー:
ユーザープログラム
│
│ read(fd, buf, count); ← C言語の関数呼び出し
↓
┌────────────────────────────────┐
│ Cライブラリ (libc) │
│ │
│ syscall(SYS_read, fd, ...) │
│ ・引数をレジスタに設定 │
│ ・システムコール番号を設定 │
│ ・trap命令 / syscall命令 │
└────────────────────────────────┘
│
│ ← CPU特権レベルの移行 (Ring 3 → Ring 0)
↓
┌────────────────────────────────┐
│ カーネル │
│ │
│ 1. システムコール番号を確認 │
│ 2. 引数を検証 │
│ 3. 適切なカーネル関数を呼ぶ │
│ 4. 結果を返す │
└────────────────────────────────┘
│
│ ← 特権レベルを戻す (Ring 0 → Ring 3)
↓
ユーザープログラムに戻る
システムコールのオーバーヘッド:
特権レベルの切り替えには、数百〜数千CPUサイクルのコストがかかる。これが、バッファリングが重要な理由の一つである。
1.2.3 Unixシステムコールの分類
Unixシステムコールは、大きく以下のカテゴリに分類される：
Unixシステムコールの分類:
1. ファイル操作
open(), close(), read(), write(), lseek()
dup(), dup2(), fcntl(), ioctl()
2. プロセス制御
fork(), exec(), wait(), exit()
getpid(), getppid(), kill()
3. メモリ管理
brk(), mmap(), munmap()
malloc()は直接のシステムコールではない
4. プロセス間通信
pipe(), socket(), send(), recv()
shmget(), semget(), msgget()
5. ファイルシステム操作
stat(), chmod(), chown()
mkdir(), rmdir(), link(), unlink()
6. シグナル
signal(), sigaction(), sigprocmask()
7. 時間
time(), gettimeofday(), nanosleep()
get_next_lineで直接使うのはread()のみだが、その背後には複雑なカーネル機構がある。
1.3 ファイルディスクリプタの理論
1.3.1 ファイルディスクリプタとは
ファイルディスクリプタ（File Descriptor, fd）は、開いているファイルやI/Oリソースを識別する非負の整数である。
ファイルディスクリプタの本質:
プログラマの視点:
int fd = 3; ← 単なる整数
カーネルの視点:
fd は以下のデータ構造へのインデックス:
プロセス
┌─────────────────────────────────────┐
│ ファイルディスクリプタテーブル │
│ │
│ [0] ──→ stdin (標準入力) │
│ [1] ──→ stdout (標準出力) │
│ [2] ──→ stderr (標準エラー出力) │
│ [3] ──→ ファイルテーブルエントリへ ──┤
│ [4] ──→ ... │
└─────────────────────────────────────┘
│
↓
┌────────────────────────┐
│ ファイルテーブル │
│ (システム全体で共有) │
│ │
│ ・ファイル位置 │
│ ・アクセスモード │
│ ・参照カウント │
│ ・vnode/inodeへのポインタ│
└────────────────────────┘
│
↓
┌────────────────────────┐
│ inode/vnode │
│ │
│ ・ファイルサイズ │
│ ・パーミッション │
│ ・タイムスタンプ │
│ ・データブロックへのポインタ│
└────────────────────────┘
1.3.2 標準ファイルディスクリプタ
Unixでは、すべてのプロセスは生成時に3つのファイルディスクリプタを持つ：
#define STDIN_FILENO 0 /* 標準入力 */
#define STDOUT_FILENO 1 /* 標準出力 */
#define STDERR_FILENO 2 /* 標準エラー出力 */
/*
歴史的背景:
1970年代、端末（テレタイプ）は3つのチャネルを持っていた:
1. キーボード入力 (入力)
2. 画面出力 (出力)
3. ベル/エラー (エラー通知)
この概念がUnixに継承された。
*/
/* シェルでのリダイレクト例 */
/* $ command < input.txt # stdinをファイルにリダイレクト */
/* $ command > output.txt # stdoutをファイルにリダイレクト */
/* $ command 2> error.txt # stderrをファイルにリダイレクト */
1.3.3 ファイル位置（File Offset）
各オープンファイル（正確には、各ファイルテーブルエントリ）は、現在の読み書き位置を持つ。
ファイル位置の概念:
ファイル内容: "Hello, World!\n"
バイト位置: 0123456789...
ファイル位置 = 0 (開始時):
[H][e][l][l][o][,][ ][W][o][r][l][d][!][\n]
↑
位置=0
read(fd, buf, 5) 実行後:
[H][e][l][l][o][,][ ][W][o][r][l][d][!][\n]
↑
位置=5（5バイト進んだ）
再度 read(fd, buf, 5) 実行後:
[H][e][l][l][o][,][ ][W][o][r][l][d][!][\n]
↑
位置=10
lseek(fd, 0, SEEK_SET) で位置を0に戻す
重要な性質:
read()とwrite()は、自動的にファイル位置を進める1.3.4 ファイルディスクリプタの共有
fork()によるプロセス複製やdup()によるfd複製では、ファイルテーブルエントリを共有する。
fork()の場合:
親プロセス 子プロセス
┌────────────┐ ┌────────────┐
│ fd[3] ────┼────────┐ ┌────┼──── fd[3] │
└────────────┘ │ │ └────────────┘
↓ ↓
┌───────────────┐
│ ファイル │
│ テーブル │
│ エントリ │
│ │
│ 位置: 100 │ ← 共有される
│ 参照カウント: 2 │
└───────────────┘
親がread()すると、子のファイル位置も変わる！
dup()の場合:
同一プロセス
┌────────────┐
│ fd[3] ─────┼───┐
│ │ │
│ fd[4] ─────┼───┤ ← 同じエントリを指す
└────────────┘ │
↓
┌───────────────┐
│ ファイル │
│ テーブル │
│ エントリ │
└───────────────┘
1.4 read()システムコールの深層
1.4.1 read()の正式な定義
POSIX標準におけるread()の定義:
#include <unistd.h>
ssize_t read(int fd, void *buf, size_t count);
/*
パラメータ:
fd : 読み取り用にオープンされたファイルディスクリプタ
buf : データを格納するバッファへのポインタ
count : 読み取りを試みる最大バイト数
戻り値:
成功時: 実際に読み取ったバイト数（0以上）
EOF時 : 0
失敗時: -1（errno設定）
型の説明:
ssize_t : 符号付きサイズ型（-1を返すため）
size_t : 符号なしサイズ型（バイト数は負にならない）
*/
1.4.2 read()の内部動作
カーネル内部でread()がどのように処理されるかを理解する：
read(fd, buf, count) の内部フロー:
1. システムコールエントリ
├── 引数の検証
│ ├── fd が有効か?
│ ├── buf がNULLでないか?
│ └── count が妥当か?
│
└── ファイルテーブルエントリの取得
2. ファイルタイプの判定
├── 通常ファイル → ページキャッシュ経由で読み取り
├── パイプ → パイプバッファから読み取り
├── ソケット → ネットワークバッファから読み取り
├── デバイス → デバイスドライバを呼び出し
└── ディレクトリ → エラー（EISDIRを返す）
3. 通常ファイルの場合:
ページキャッシュにデータがある?
│
├── YES → キャッシュからユーザーバッファにコピー
│
└── NO → ディスクから読み取り
├── I/Oスケジューラにリクエスト
├── DMA転送
├── ページキャッシュに保存
└── ユーザーバッファにコピー
4. ファイル位置の更新
position += bytes_read
5. 戻り値の設定
└── 読み取ったバイト数 または -1
1.4.3 read()の戻り値の意味
read()の戻り値は3つの状態を示す：
ssize_t bytes = read(fd, buffer, count);
if (bytes > 0)
{
/*
成功: データを読み取った
注意:
- bytes <= count（要求より少ないことがある）
- ファイルの終端に近い場合
- パイプで利用可能なデータが少ない場合
- シグナルによる中断後の再開
*/
buffer[bytes] = '\0'; /* 文字列として使う場合 */
}
else if (bytes == 0)
{
/*
EOF: ファイルの終端に達した
これ以上読むデータがない
*/
printf("End of file reached\n");
}
else /* bytes == -1 */
{
/*
エラー: 何か問題が発生
errno を確認して原因を特定
*/
if (errno == EINTR)
{
/* シグナルによる中断、再試行可能 */
}
else if (errno == EAGAIN || errno == EWOULDBLOCK)
{
/* 非ブロッキングI/Oでデータなし */
}
else
{
/* その他のエラー */
perror("read");
}
}
1.4.4 ショートリード（Short Read）
read()が要求より少ないバイト数を返すことをショートリードという：
/*
ショートリードの発生条件:
1. ファイルの終端に近い
- 残り100バイトで1000バイト要求
- → 100バイトが返る
2. パイプ/ソケットでデータが少ない
- パイプに50バイトしかない
- 1000バイト要求しても50バイト
3. シグナルによる中断
- 読み取り中にシグナル
- 一部読み取り後に返る
4. ターミナル入力
- 行単位で入力される
- Enter押下まで待ち、行を返す
*/
/* 正しいread()の使い方: 要求バイト数を読み切るまでループ */
ssize_t read_all(int fd, void *buf, size_t count)
{
size_t total = 0;
char *ptr = buf;
while (total < count)
{
ssize_t n = read(fd, ptr + total, count - total);
if (n == -1)
{
if (errno == EINTR)
continue; /* 中断された、再試行 */
return -1; /* 本当のエラー */
}
if (n == 0)
break; /* EOF */
total += n;
}
return total;
}
1.5 バッファリングの科学
1.5.1 メモリ階層とアクセス時間
コンピュータのメモリ階層を理解することで、バッファリングの重要性が明らかになる：
メモリ階層（2020年代の典型的な値）:
┌────────────────┐
│ CPUレジスタ │ ~0.3 ns
│ (数KB) │
└───────┬────────┘
│
┌───────┴────────┐
│ L1キャッシュ │ ~1 ns
│ (32-64KB) │
└───────┬────────┘
│
┌───────┴────────┐
│ L2キャッシュ │ ~4 ns
│ (256KB-1MB) │
└───────┬────────┘
│
┌───────┴────────┐
│ L3キャッシュ │ ~10 ns
│ (数MB-数十MB) │
└───────┬────────┘
│
┌───────┴────────┐
│ メインメモリ │ ~100 ns
│ (数GB-TB) │
└───────┬────────┘
│
┌───────┴────────┐
│ SSD │ ~10-100 μs
│ (数百GB-TB) │
└───────┬────────┘
│
┌───────┴────────┐
│ HDD │ ~5-10 ms
│ (数TB) │
└────────────────┘
注目すべき点:
- メモリ vs SSD: 約100倍の差
- メモリ vs HDD: 約10万倍の差
- システムコールオーバーヘッド: 約1-10μs
結論: ディスクアクセスを最小化することが性能の鍵
1.5.2 カーネルのページキャッシュ
Linuxカーネルは、ページキャッシュを使ってディスクI/Oを最適化する：
ページキャッシュの動作:
読み取り時:
┌────────────────────────────────────────────────┐
│ │
│ read(fd, buf, 4096) を呼び出し │
│ │ │
│ ↓ │
│ ┌──────────────────────────────────────┐ │
│ │ ページキャッシュにデータがある? │ │
│ └──────────────────────────────────────┘ │
│ │ │
│ YES ────┴──── NO │
│ │ │ │
│ ↓ ↓ │
│ キャッシュ ディスクから │
│ からコピー 読み取り │
│ │ │ │
│ │ ↓ │
│ │ キャッシュに保存 │
│ │ │ │
│ └────────────┘ │
│ │ │
│ ↓ │
│ ユーザーバッファにコピー │
│ │
└────────────────────────────────────────────────┘
メリット:
- 同じデータの再読み取りが高速
- 複数プロセスでキャッシュを共有
- 先読み（read-ahead）で連続読み取りを高速化
1.5.3 ユーザー空間バッファリング
ページキャッシュに加えて、ユーザー空間でもバッファリングが行われる：
標準Cライブラリのバッファリング:
FILE *fp = fopen("file.txt", "r");
char c;
/* fgetc()は1文字返すが、内部で4096バイトをread()している */
while ((c = fgetc(fp)) != EOF)
{
/* 処理 */
}
内部動作:
┌────────────────────────────────────────┐
│ ユーザープログラム │
│ │
│ fgetc() ← 1文字要求 │
│ ↓ │
│ ┌─────────────────────────────────┐ │
│ │ stdio バッファ (4096バイト) │ │
│ │ │ │
│ │ [データ][データ][..........空き...] │ │
│ │ ↑ │ │
│ │ 読み取り位置 │ │
│ └─────────────────────────────────┘ │
│ ↓ バッファが空になったら │
│ read(fd, buffer, 4096) │
└────────────────────────────────────────┘
バッファリングモード:
- 完全バッファリング（ファイル）: バッファが満杯で書き出し
- 行バッファリング（端末）: 改行で書き出し
- バッファリングなし（stderr）: 即座に書き出し
1.5.4 get_next_lineにおけるバッファリング戦略
get_next_lineでは、独自のバッファリングを実装する必要がある：
/*
get_next_lineのバッファリング戦略:
問題:
- read()は「指定バイト数まで」読む（行を意識しない）
- 改行で区切られた「行」を返す必要がある
- 行は複数のread()にまたがる可能性がある
- 1回のread()で複数行を含む可能性がある
解決策: 静的バッファを使った状態管理
*/
char *get_next_line(int fd)
{
static char *buffer; /* 静的: 呼び出し間で状態を保持 */
char tmp[BUFFER_SIZE + 1];
/*
動作:
1回目の呼び出し:
read() → "Hello\nWor" を読み取り
buffer = "Hello\nWor"
"Hello\n" を返す
buffer = "Wor" (残りを保持)
2回目の呼び出し:
buffer に "Wor" がある
read() → "ld\nBye\n" を追加
buffer = "World\nBye\n"
"World\n" を返す
buffer = "Bye\n"
3回目の呼び出し:
buffer に "Bye\n" がある（改行あり）
read() 不要
"Bye\n" を返す
buffer = "" (空)
*/
}
1.6 静的変数の計算機科学
1.6.1 記憶域クラス（Storage Class）
C言語の変数は、記憶域クラスによって寿命とスコープが決まる：
/*
記憶域クラスの分類:
1. 自動変数（auto）- スタック上
- 関数内で宣言された変数（デフォルト）
- 関数終了時に破棄
2. 静的変数（static）- データセグメント上
- static キーワードで宣言
- プログラム終了まで存続
3. 外部変数（extern）- データセグメント上
- グローバル変数
- 他のファイルからも参照可能
4. レジスタ変数（register）- CPUレジスタ
- コンパイラへのヒント（無視されることも）
- アドレスを取得できない
*/
void demonstrate_storage_classes(void)
{
int auto_var = 10; /* 自動変数（スタック） */
static int static_var = 20; /* 静的変数（データセグメント） */
auto_var++; /* 毎回初期化される */
static_var++; /* 値が保持される */
printf("auto: %d, static: %d\n", auto_var, static_var);
}
int main(void)
{
demonstrate_storage_classes(); /* auto: 11, static: 21 */
demonstrate_storage_classes(); /* auto: 11, static: 22 */
demonstrate_storage_classes(); /* auto: 11, static: 23 */
return 0;
}
1.6.2 メモリレイアウト
プロセスのメモリレイアウトを理解する：
典型的なプロセスのメモリレイアウト:
高位アドレス
┌────────────────────────────────┐
│ カーネル空間 │
├────────────────────────────────┤
│ スタック │ ← 自動変数、関数引数
│ ↓ │ 関数呼び出しで成長
│ (成長方向) │
├────────────────────────────────┤
│ │
│ (未使用領域) │
│ │
├────────────────────────────────┤
│ ↑ │
│ (成長方向) │ malloc()で成長
│ ヒープ │ ← 動的メモリ
├────────────────────────────────┤
│ BSS │ ← 未初期化の静的/グローバル変数
│ (Block Started by Symbol) │ ゼロ初期化される
├────────────────────────────────┤
│ データ │ ← 初期化済みの静的/グローバル変数
│ セグメント │ static int x = 42;
├────────────────────────────────┤
│ テキスト │ ← プログラムコード
│ セグメント │ 読み取り専用
└────────────────────────────────┘
低位アドレス
1.6.3 get_next_lineにおける静的変数
静的変数はget_next_lineの状態管理に使われる：
/*
なぜ静的変数が必要か?
問題: get_next_line()は複数回呼ばれる
各呼び出しで、前回の「残り」を覚えておく必要がある
解決策: 静的変数で状態を保持
*/
char *get_next_line(int fd)
{
/*
static 変数:
- 関数内でのみアクセス可能（スコープ）
- プログラム終了まで存続（寿命）
- 最初の呼び出し時に一度だけ初期化
*/
static char *stored_data = NULL;
/*
1回目: stored_data = NULL
2回目: stored_data = "前回の残り"
3回目: stored_data = "その次の残り"
...
*/
}
/*
注意: ボーナス課題では複数のfdを扱う
→ 静的変数の配列または連想配列が必要
*/
char *get_next_line_bonus(int fd)
{
static char *stored_data[MAX_FD]; /* fd毎に状態を保持 */
if (fd < 0 || fd >= MAX_FD)
return NULL;
/* stored_data[fd] を使用 */
}
1.7 文字列処理の計算機科学
1.7.1 null終端文字列の歴史
C言語の文字列はnull終端（null-terminated）形式を採用している：
/*
null終端文字列の起源:
1960年代、PDP-7とPDP-11は、文字列を効率的に処理するために
null終端を使用していた。
メモリレイアウト:
char str[] = "Hello";
アドレス: [0] [1] [2] [3] [4] [5]
内容: 'H' 'e' 'l' 'l' 'o' '\0'
↑
null終端
利点:
- メモリ効率が良い（長さを別に格納しない）
- 任意の長さの文字列を扱える
欠点:
- 長さを知るためにはスキャンが必要（O(n)）
- null文字自体をデータとして含められない
- バッファオーバーフローの原因になりやすい
*/
/* strlen()の実装 */
size_t ft_strlen(const char *s)
{
size_t len = 0;
while (s[len]) /* s[len] != '\0' と同等 */
len++;
return len;
}
/* 時間計算量: O(n) - 文字列全体をスキャン */
1.7.2 Pascal文字列との比較
別のアプローチとして、Pascal言語の文字列がある：
Pascal文字列（長さプレフィックス方式）:
str = "Hello"
アドレス: [0] [1] [2] [3] [4] [5]
内容: 5 'H' 'e' 'l' 'l' 'o'
↑
長さ（1バイト）
利点:
- 長さが即座にわかる（O(1)）
- null文字を含められる
欠点:
- 最大長が制限される（1バイト長なら255文字）
- 2つの長さ形式（1バイト/2バイト/4バイト）
現代の言語:
- Python: 長さとハッシュを保持
- Java: 長さを保持、char配列への参照
- Rust: 長さと容量を保持（スタック上）
1.7.3 get_next_lineでの文字列操作
get_next_lineで必要な文字列操作：
/*
必要な操作:
1. strlen - 長さを取得
2. strchr - 文字を検索（改行を探す）
3. strdup - 文字列を複製
4. strjoin - 2つの文字列を結合
5. substr - 部分文字列を抽出
*/
/* 改行を探す */
char *find_newline(const char *s)
{
if (!s)
return NULL;
while (*s)
{
if (*s == '\n')
return (char *)s;
s++;
}
return NULL;
}
/* 2つの文字列を結合（新しいメモリを割り当て） */
char *ft_strjoin(const char *s1, const char *s2)
{
char *result;
size_t len1;
size_t len2;
size_t i;
if (!s1 && !s2)
return NULL;
if (!s1)
return ft_strdup(s2);
if (!s2)
return ft_strdup(s1);
len1 = ft_strlen(s1);
len2 = ft_strlen(s2);
result = malloc(len1 + len2 + 1);
if (!result)
return NULL;
i = 0;
while (*s1)
result[i++] = *s1++;
while (*s2)
result[i++] = *s2++;
result[i] = '\0';
return result;
}
1.8 BUFFER_SIZEとパフォーマンス
1.8.1 システムコールのコスト分析
BUFFER_SIZEの選択は、パフォーマンスに直接影響する：
1000バイトのファイルを読む場合:
BUFFER_SIZE = 1:
- read()を1000回呼ぶ
- システムコールコスト: 1000 × ~2μs = ~2ms
- ユーザー/カーネル切り替え: 1000回
BUFFER_SIZE = 100:
- read()を10回呼ぶ
- システムコールコスト: 10 × ~2μs = ~20μs
- ユーザー/カーネル切り替え: 10回
BUFFER_SIZE = 4096:
- read()を1回呼ぶ
- システムコールコスト: 1 × ~2μs = ~2μs
- ユーザー/カーネル切り替え: 1回
結論: 大きなBUFFER_SIZEは効率的
1.8.2 ページサイズとアライメント
オペレーティングシステムは、メモリをページ単位で管理する：
ページサイズ（Linux/macOS）:
$ getconf PAGESIZE
4096
最適なBUFFER_SIZE:
- ページサイズの倍数が効率的
- 4096, 8192, 16384 など
- ページ境界でのI/Oは最適化される
理由:
- ページキャッシュはページ単位
- DMA転送はページ単位
- メモリ割り当てはページ境界
ただし、get_next_lineでは:
- 任意のBUFFER_SIZEで動作する必要がある
- 1から数百万まで対応
1.8.3 小さなBUFFER_SIZEでのテスト
42の評価では、極端なBUFFER_SIZEでテストされる：
/*
BUFFER_SIZE = 1 のシナリオ:
ファイル: "Hello\n"
read #1: 'H'
stored = "H"
改行なし → 続行
read #2: 'e'
stored = "He"
改行なし → 続行
read #3: 'l'
stored = "Hel"
...
read #6: '\n'
stored = "Hello\n"
改行発見 → "Hello\n" を返す
問題点:
- strjoin()が毎回呼ばれる（非効率）
- 多くのmalloc/free
- O(n²)の時間計算量になりやすい
最適化:
- バッファを倍々に拡張（償却O(n)）
- 一時バッファを再利用
*/
1.9 エラー処理の原則
1.9.1 防御的プログラミング
堅牢なコードは、すべてのエラーケースを考慮する：
/*
防御的プログラミングの原則:
1. 入力の検証
2. 関数の戻り値の確認
3. NULLポインタのチェック
4. 境界条件の処理
5. リソースの適切な解放
*/
char *get_next_line(int fd)
{
static char *stored = NULL;
char buffer[BUFFER_SIZE + 1];
ssize_t bytes;
/* 入力の検証 */
if (fd < 0)
return NULL;
if (BUFFER_SIZE <= 0)
return NULL;
/* read()のエラー処理 */
bytes = read(fd, buffer, BUFFER_SIZE);
if (bytes == -1)
{
/* エラー時はリソースを解放 */
free(stored);
stored = NULL;
return NULL;
}
/* malloc()のエラー処理 */
char *new_str = malloc(some_size);
if (!new_str)
{
free(stored);
stored = NULL;
return NULL;
}
/* ... */
}
1.9.2 エラー状態の伝搬
エラーは適切に伝搬される必要がある：
/*
エラー伝搬のパターン:
パターン1: NULLを返す（get_next_lineで使用）
- 成功時: 有効なポインタ
- 失敗時: NULL
- 呼び出し側が確認する必要がある
パターン2: errnoを設定
- システムコールの標準
- スレッドローカル変数
- perror()で人間が読める形式に
パターン3: 戻り値でエラーコード
- -1がエラー、0以上が成功
- read()、write()などで使用
*/
/* get_next_lineの呼び出し側 */
int main(void)
{
int fd;
char *line;
fd = open("file.txt", O_RDONLY);
if (fd == -1)
{
perror("open");
return 1;
}
while ((line = get_next_line(fd)) != NULL)
{
printf("%s", line);
free(line); /* 呼び出し側がfreeする責任 */
}
/* line == NULL は EOF またはエラー */
/* 区別するにはerrnoを確認（ただしget_next_lineは設定しない）*/
close(fd);
return 0;
}
1.10 get_next_lineプロジェクトの構造
1.10.1 必要なファイル
get_next_line/
├── get_next_line.c # メイン関数と主要ロジック
├── get_next_line.h # ヘッダーファイル
├── get_next_line_utils.c # ヘルパー関数
│
└── ボーナス/
├── get_next_line_bonus.c
├── get_next_line_bonus.h
└── get_next_line_utils_bonus.c
1.10.2 ヘッダーファイルの設計
/* get_next_line.h */
#ifndef GET_NEXT_LINE_H
# define GET_NEXT_LINE_H
# include <stdlib.h>
# include <unistd.h>
/* BUFFER_SIZEのデフォルト定義 */
# ifndef BUFFER_SIZE
# define BUFFER_SIZE 42
# endif
/* メイン関数 */
char *get_next_line(int fd);
/* ヘルパー関数（libftは使用不可） */
size_t ft_strlen(const char *s);
char *ft_strchr(const char *s, int c);
char *ft_strjoin(char const *s1, char const *s2);
char *ft_strdup(const char *s);
char *ft_substr(char const *s, unsigned int start, size_t len);
#endif
1.10.3 実装のアウトライン
/* get_next_line.c の構造 */
#include "get_next_line.h"
/*
静的ヘルパー関数（ファイル内部でのみ使用）
*/
static char *read_and_append(int fd, char *stored);
static char *extract_line(char *stored);
static char *update_stored(char *stored);
/*
メイン関数
*/
char *get_next_line(int fd)
{
static char *stored = NULL;
char *line;
/* 入力検証 */
if (fd < 0 || BUFFER_SIZE <= 0)
return NULL;
/* ファイルから読み取り、storedに追加 */
stored = read_and_append(fd, stored);
if (!stored)
return NULL;
/* storedから一行を抽出 */
line = extract_line(stored);
/* storedを更新（使った部分を削除）*/
stored = update_stored(stored);
return line;
}
まとめ
本章では、get_next_lineを実装するための理論的基盤を学んだ。
オペレーティングシステムの歴史:
- バッチ処理からタイムシェアリングへの進化
- MulticsからUnixへ
- 「すべてはファイル」の哲学
システムコールの理論:
- ユーザーモードとカーネルモードの分離
- システムコールのメカニズムとコスト
- read()の詳細な動作
ファイルディスクリプタ:
- カーネル内部のデータ構造
- ファイル位置とその共有
- 標準入出力の概念
バッファリングの科学:
- メモリ階層とアクセス時間
- ページキャッシュの役割
- ユーザー空間バッファリング
静的変数とメモリ:
- 記憶域クラスの理論
- プロセスのメモリレイアウト
- 状態管理への応用
次章では、ファイルディスクリプタの詳細な理論と、カーネルのファイル管理機構について深く掘り下げる。