計算量はどう求めれば良いですか？

ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。

覚えるべき定番アルゴリズムは何ですか？

二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。

仮想メモリ

このレッスンで分かること

仮想メモリは「物理 RAM の上に 論理的な広いアドレス空間 を被せる」仕組みです

各プロセスは自分専用の連続した空間を見ているように振る舞え、実際の物理メモリの場所は OS が管理します

仮想メモリのおかげで プロセス間隔離・メモリ共有・スワップ・Copy-on-Write が成立します

仮想メモリとは

仮想メモリ。本レッスンでは、仮想メモリの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

仮想メモリの目的

物理 RAM は CPU から見ると 1 本のアドレス空間（0 番地から始まる一直線）ですが、複数のプロセスが同居するとき直接そのまま使うといくつも問題があります。番地が衝突する、悪意のプロセスが他人のデータを読む、RAM 容量を超えるプログラムは動かせない――等です。

仮想メモリはこれを 2 段階のアドレス変換 で解決します。プロセスが扱う 仮想アドレス をカーネル + MMU（Memory Management Unit）が 物理アドレス に翻訳します。プロセス側から見ると、自分専用にテラバイト級（x86-64 の一般的な構成ではユーザー空間が約 128TB）の広大な空間が連続して存在しているように見えます。

アドレス変換の図解

diagram (will load when visible)

仮想アドレスは ページ（典型 4KB）単位で物理ページに対応付けられ、その対応表が ページテーブル です。

プロセスのメモリレイアウト

64bit Linux でのプロセス空間の典型は下記です。

領域	アドレス例	内容
カーネル空間	上位（プロセスからは見えない）	カーネルコード
スタック	上位から下に伸びる	ローカル変数、戻りアドレス
メモリマップ	スタック直下	mmap、共有ライブラリ
ヒープ	低位から上に伸びる	malloc / new で確保
BSS	下位	初期化なしのグローバル変数
データ	下位	初期化済みのグローバル変数
テキスト	下位	機械語のコード（読み取り専用）

スタックとヒープは互いに向かって成長し、ぶつかると有名な「スタックオーバーフロー」になります。

具体例

#include <stdio.h>
#include <stdlib.h>

int g = 1;        // データ
int g_bss;        // BSS

int main() {
    int local = 2;          // スタック
    int *h = malloc(4);     // ヒープ
    printf("&g     = %p\n", (void*)&g);
    printf("&g_bss = %p\n", (void*)&g_bss);
    printf("&local = %p\n", (void*)&local);
    printf("h      = %p\n", (void*)h);
    return 0;
}

実行すると、変数ごとに異なるアドレス範囲に住んでいることが確認できます。Linux では cat /proc/self/maps を実行すると、現在プロセスの全領域マップが見られます。

メリット

プロセス隔離 プロセス A の仮想アドレス 0x1000 と B の 0x1000 は別の物理ページに対応し、互いに読めない
メモリ共有 ライブラリの読み取り専用ページは複数プロセスから同じ物理ページに mmap でき、RAM 節約
スワップ あまり使われないページをディスクに退避し、必要時に読み戻すことで RAM 容量超のプログラムも動く
Copy-on-Write fork 後、親と子は最初同じ物理ページを共有し、書き込まれたページだけ複製

トレードオフ

アドレス変換のために MMU を通る分、わずかなオーバーヘッドがある（TLB で緩和）
スワップが頻発するとディスク I/O が支配的になり性能が壊滅する。これを スラッシング と呼ぶ
ページテーブル自体も RAM を食う。64bit 環境では多段テーブル（4 ～ 5 レベル）が普通

よくある誤解

「仮想メモリ = スワップ領域」は誤解です。スワップはあくまで仮想メモリの 機能の 1 つ で、スワップ無しでも仮想メモリは動きます
「ポインタの値はメモリの物理位置」も誤解で、C のポインタはあくまで仮想アドレスです

やってみよう

ターミナル

cat /proc/self/maps | head -20

自分の今打ったシェルやプロセスの仮想メモリレイアウトが、領域ごとにずらりと並んでいるのが見えます。rwxp のフラグでアクセス権が分かります。

よくある質問

Q. このトピックは実務でどう役立ちますか？

A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。

Q. ページフォールトとは何ですか？

A. プロセスがアクセスした仮想アドレスに対応する物理ページがまだ割り当てられていない（またはスワップアウトされている）とき、CPU が OS に割り込みを発生させる仕組みです。OS はページフォールトハンドラで物理ページを割り当て（またはディスクから読み戻し）、処理を再開します。

Q. スワップが多発しているか確認する方法はありますか？

A. Linux では vmstat 1 や cat /proc/vmstat | grep pgmajfault でメジャーフォールト（ディスクから読み戻しが発生したページフォールト）の発生数を確認できます。数値が継続的に増加している場合はスラッシングの兆候です。

次のレッスン

次は ページングとスワップ で、仮想メモリを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

仮想メモリの要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 仮想メモリとは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン