LRU 簡易シミュレーション｜コードで実践

LRU 簡易シミュレーション

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

上の実装は 配列の線形検索 を使うので、各操作 O(n)、全体で O(N * capacity) です

物理メモリは有限なので、OS は ページ置換アルゴリズム で どの古いページを追い出すか を決めています

ページアクセスの列 pages と、キャッシュ容量 capacity を受け取り、ページフォルト (キャッシュミス) の合計回数を返す関数を作ります

LRU 簡易シミュレーションとは

ページアクセス列から LRU 方式のキャッシュミス回数を求める。本レッスンでは、LRU 簡易シミュレーションの基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

物理メモリは有限なので、OS は ページ置換アルゴリズム で どの古いページを追い出すか を決めています。代表格が LRU (Least Recently Used)、つまり 最も長く使われていないページを捨てる 戦略です。

LRU は 直近で使われていないものは、今後も使われない という経験則に基づきます。CPU キャッシュ、ブラウザのリソースキャッシュ、Redis の maxmemory-policy まで、現代システムの至るところで使われます。

シミュレーションの設計

ページアクセスの列 pages と、キャッシュ容量 capacity を受け取り、ページフォルト (キャッシュミス) の合計回数を返す関数を作ります。

手順は次の通り進みます。

キャッシュは 配列 で表現し、先頭が古い 末尾が新しい という規約
各ページについて、キャッシュ内にあれば その要素を末尾に移動 (使われたとマーク)
無ければ miss をカウントし、追加。容量超過なら 先頭 を削除

Python

def lruMisses(pages, capacity):
    cache = []
    misses = 0
    for p in pages:
        if p in cache:
            cache.remove(p)
            cache.append(p)
        else:
            misses += 1
            cache.append(p)
            if len(cache) > capacity:
                cache.pop(0)
    return misses

JavaScript

function lruMisses(pages, capacity) {
  const cache = [];
  let misses = 0;
  for (const p of pages) {
    const idx = cache.indexOf(p);
    if (idx >= 0) {
      cache.splice(idx, 1);
      cache.push(p);
    } else {
      misses += 1;
      cache.push(p);
      if (cache.length > capacity) cache.shift();
    }
  }
  return misses;
}

計算量と本番実装

上の実装は 配列の線形検索 を使うので、各操作 O(n)、全体で O(N * capacity) です。本物の OS や Redis では ハッシュマップ + 双方向連結リスト で O(1) を実現します。シンプルさを優先する学習段階では配列で十分です。

本番のデータ構造 は O(1)、勉強用の実装 は O(n)。計算量を意識 してコードを読むと中身が見えてきます。

LRU の挙動を図で追う

capacity = 3 で pages = [1, 2, 3, 1, 4] を流すと、以下のように動きます。

diagram (will load when visible)

図のポイント (テキスト併記)

最終的に misses = 4 です

最終的に misses = 4 です。1 を再アクセス したことで 2 が一番古く なり、4 を入れるタイミングで 2 が追い出された 点がポイントです。

LRU が使われている場所

Redis の maxmemory-policy allkeys-lru は名前そのままで LRU を採用しています。Linux カーネルの ページキャッシュ も近似 LRU (2nd chance algorithm) で動きます。Web ブラウザ のリソースキャッシュも実質 LRU、CDN のエッジサーバーも LRU 系のアルゴリズムを多用しています。スマホの アプリスイッチャー で 古いアプリ がメモリから落とされる挙動も LRU の親戚です。

スラッシングとワーキングセット

キャッシュ容量がワーキングセット (同時にアクセスされるデータの集合) より小さいと、LRU を使っても 毎回 miss の スラッシング 状態になります。pages = [1,2,3,1,2,3] capacity = 2 のように、周期的アクセス のサイズが capacity + 1 のときが最悪です。FIFO と違い LRU はスタックアルゴリズムのため Belady の異常を起こさず、容量を増やせば必ずミスは減ります。ただし周期的アクセスのようにアクセスパターン自体がキャッシュ容量に合わない場合は、LRU でもスラッシングは避けられません。

LRU は万能ではない。アクセスパターンが 周期的 のときは LFU や Adaptive Replacement Cache (ARC) の方が向くこともある。

よくある間違い

hit のときに 末尾へ移動 を忘れて 単なる FIFO になっている
capacity を超えた直後ではなく、追加前にチェックして 1 個足りない 状態になる
pages が空の配列のときに misses を 0 で返す処理を忘れる

LRU は アクセスのたびに順序が動く のがミソ。hit でも cache を更新する ことを忘れないように。

やってみよう

FIFO 方式 (hit でも順序を変えない) の関数も書いて、ミス数の差を比較する
LFU (最も使われていないものを捨てる) の関数を書いてみる
OrderedDict (Python) や Map (JS) を使った O(1) 実装に書き換える
ヒット率も一緒に返す版を書いて、本章の cacheHitRate と組み合わせる

よくある質問

Q. このトピックを覚える意味は何ですか？

A. キャッシュ設計やメモリ枯渇時の挙動を理解する土台になります。Redis の maxmemory-policy を適切に選ぶにも、アプリ内キャッシュを実装するにも、LRU の動作原理を知っているかどうかで判断の質が変わります。実務でのパフォーマンスチューニングや障害対応のスピードが格段に上がります。

Q. 実務でこの知識を使う場面は？

A. Redis の maxmemory-policy 設定、アプリケーション内のインメモリキャッシュ実装、CDN やブラウザキャッシュの動作分析など、キャッシュ戦略を議論するあらゆる場面で直接使える知識です。キャッシュのミス率が高い原因を特定する際にも、アルゴリズムレベルで考えられるかどうかが問われます。

Q. 他の章とどう繋がりますか？

A. データ構造の章で扱う双方向連結リストとハッシュマップは、LRU の O(1) 実装に直結します。OS のメモリ管理章では仮想メモリやページテーブルと組み合わせて理解が深まります。また本章で登場した「ワーキングセット」の概念は、JVM や Node.js のメモリチューニングにも繋がります。

次のレッスン

次は エンディアンの入れ替え (uint32) に進みましょう。

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

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

理解度チェック (30 秒)

Q. LRU 簡易とは何か、1 文で説明してください。

この章のポイント

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

関連レッスン

LRU 簡易シミュレーション