グラフィカルな説明 | Linux メモリリサイクル LRU アルゴリズム

[[421791]]

メモリは、オペレーティングシステムにとって非常に重要なリソースです。オペレーティングシステムがプログラムを実行するには、まずプログラムコードセグメントの命令とデータセグメントの変数をハードディスクからメモリにロードしてから実行する必要があります。次の図に示すように:

しかし、メモリリソースには限りがあります。システム内で実行されるプロセスが増えるにつれて、システム内で使用可能なメモリは少なくなります。では、利用可能なメモリが少ない場合、Linux カーネルはどのように状況を処理するのでしょうか?

この記事では、使用可能なメモリが不足している状況を Linux カーネルがどのように処理するかについて説明します。

1. メモリ不足の対処方法

システムの使用可能なメモリが不足し、プロセスがメモリを要求し続けると何が起こるか考えてみましょう。

システムの使用可能なメモリが不足している場合、カーネルはメモリをリサイクルして、プロセスに十分なメモリが使用可能であることを確認します。メモリのリサイクルには主に次の手順が含まれます。

特定の操作 (ファイル I/O など) を高速化するために、カーネルは操作の結果をキャッシュし (ファイルページキャッシュなど)、キャッシュによって使用されたメモリを再利用できます。したがって、使用可能なメモリが少ない場合は、カーネルキャッシュが最初に再利用されます。
カーネルキャッシュがリサイクルされた後もシステムの使用可能なメモリがまだ不足している場合。次に、カーネルはスワップメカニズムをトリガーします。スワップメカニズムは、特定のプロセスによって使用されるメモリをハードディスクにスワップ (書き込み) し、その後メモリを解放して、システムで使用できるメモリを増やします。この記事では、スワップメカニズムに焦点を当てます。
スワップメカニズムがトリガーされた後もシステムの使用可能なメモリがシステム要件を満たせない場合は、OOM (Out Of Memory) メカニズムがトリガーされます。 OOM メカニズムは、いくつかのプロセスを選択して終了し、より多くのメモリを利用できるようにします。

メモリを再利用する方法は 3 つあるため、この記事ではスワップメカニズムを分析対象として重点的に取り上げ、メモリが不足したときにカーネルがどのようにメモリを再利用するかを紹介します。

2. スワップメカニズムの原理

スワップメカニズムの実装を分析する前に、まずスワップメカニズムの原理を紹介します。

この記事では Linux-2.6.23 カーネルを使用します。

スワップという言葉は交換を意味します。名前が示すように、特定のプロセスによって占有されているメモリをハードディスクに交換 (書き込み) し、その後、オペレーティングシステムがより多くのメモリを使用できるようにメモリをオペレーティングシステムに解放することを意味します。次の図に示すように:

スワップメカニズムの本質は、プロセスによって占有されているメモリをハードディスクに書き込み、その後メモリを解放することだからです。次に、どのプロセスのメモリをハードディスクにスワップするかが問題になります。

各プロセスは、占有しているメモリがハードディスクにスワップされることを望みません。メモリがハードディスクにスワップされた後、プロセスがこのメモリを使用する場合、そのメモリを引き続き使用する前に、まずハードディスクからメモリにロードする必要があるため、プロセスのパフォーマンスが大幅に低下します。このため、カーネルは、プロセスのパフォーマンスへの影響を最小限に抑えながら、ディスクにスワップするメモリを選択するための最適なソリューションを提供する必要があります。

プロセスのメモリ空間は、コードセグメント、データセグメント、mmap セグメント、ヒープセグメント、スタックセグメントなどの複数のセグメントに分割されているためです。では、メモリのどのセグメントがハードディスクにスワップされるのでしょうか?

答えは、メモリのすべてのセグメントをハードディスクにスワップできるということです。ただし、コードセグメントや mmap セグメントなど、ファイルにマップされているメモリ領域の場合は、データをファイルに書き戻すだけで済みます (コードセグメントの内容は変更されないため、書き戻す必要はありません)。

データセグメント、ヒープセグメント、スタックセグメント内のメモリページはファイルにマップされないため (匿名メモリページと呼ばれる)、カーネルはこれらのメモリページのデータを格納するためのファイル (またはハードディスクパーティション) を提供する必要があります。このファイル (またはハードディスクパーティション) はスワップパーティションと呼ばれます。

上記の分析から、2 つの重要なメッセージを引き出すことができます。

匿名メモリページ: どのファイルにもマップされていないメモリページ。

スワップパーティション: 匿名メモリページデータを格納するために使用されるファイルまたはハードディスクパーティション。

以下では、主にカーネルがプロセスの匿名メモリページをスワップパーティションに書き込み、システムのメモリが不足しているときにこれらの匿名メモリページをリサイクルする方法について説明します。

1. LRUメモリ削除アルゴリズム

システムメモリが不足し、スワップメカニズムがトリガーされた場合、カーネルはどの匿名メモリページをスワップパーティションに書き込むように選択する必要がありますか? 一部の匿名メモリページがランダムに選択されてスワップパーティションに書き込まれると、次の問題が発生する可能性があります。

プロセスの匿名メモリページをスワップパーティションに書き込んだ後、プロセスはすぐにこのメモリページにアクセスするため、このメモリページをスワップパーティションからメインメモリに読み込む必要があります。これにより、システム負荷が増加するだけで、システムメモリ不足の問題は解決されません。

この問題を解決するために、Linux カーネルは LRU メモリ削除アルゴリズムを導入しました。Memcached または Redis を使用したことがある学生は、LRU アルゴリズムに精通しているはずです。システムのメモリが不足すると、Memcached と Redis はどちらも LRU アルゴリズムを使用してメモリを削除します。

LRU (Least Recently Used) は、中国語では「最も最近使われていない」と翻訳されます。その原理は、メモリが不足している場合、システム内で最も使用されていないメモリが削除されるため、システムパフォーマンスの低下が最小限に抑えられるというものです。

LRU アルゴリズムを実装するために、カーネルは active_list と inactive_list という 2 つの二重リンクリストを維持します。以下では、これら 2 つのリンクリストの機能について説明します。

active_list: アクティブなメモリページリスト。つまり、プロセスはこのリンクリスト内のメモリページに頻繁にアクセスするため、メモリが削除されても、このリンクリスト内のメモリページは削除されません。
inactive_list: 非アクティブなメモリページのリスト。つまり、プロセスがこのリンクリスト内のメモリページにアクセスすることはほとんどないため、メモリが削除されるときは、主にこのリンクリスト内のメモリページが削除されます。

Linux カーネルでは、各メモリゾーンは active_list と inactive_list を維持します。メモリ領域は、メモリ管理におけるオブジェクトです。より明確な説明のために、カーネル内にメモリ領域が 1 つだけあると仮定します。つまり、カーネル内には active_list と inactive_list が 1 つだけ維持されていると仮定します。次の図に示すように:

さらに、各メモリページには PG_referenced フラグがあり、メモリページがアクセスされたかどうかを示します。このフラグは、メモリ回復プロセスで重要な役割を果たします。

プロセスが匿名メモリページを要求すると、カーネルはそのメモリページをアクティブメモリページリスト (active_list) に追加し、PG_referenced フラグを 0 に設定します。次の図に示すように:

プロセスによって匿名メモリページがアクセスされると、メモリページが配置されている LRU リンクリストに応じて異なる操作が実行されます。

メモリページが元々アクティブなリンクリストにあった場合、このメモリページの PG_referenced は 1 に設定されます。
メモリページが元々非アクティブリストにあり、PG_referenced が 0 の場合。次に、メモリページの PG_referenced フラグを 1 に設定します。
メモリページが元々非アクティブリストにあり、PG_referenced が 1 の場合。その後、メモリページは非アクティブリストからアクティブリストに移動され、PG_referenced は 0 に設定されます。

次の図は、上記の状況の流れを示しています。

システムのメモリが不足している場合は、メモリ削除プロセスが必要になります。メモリページ削除プロセスは、上記のプロセスと正反対です。次に、メモリページ削除プロセスを紹介します。

メモリが削除される場合、非アクティブなリンクリストからのみ削除できます。削除プロセスは次のとおりです。

メモリの削除は、非アクティブなリンクリストの末尾から始まります。メモリページの PG_referenced フラグが 1 の場合、このメモリページはスキップされ、このメモリページの PG_referenced フラグは 0 に設定されます。
メモリページの PG_referenced フラグが 0 の場合、メモリページはスワップパーティションに書き込まれ、メモリページへのすべてのマッピングがバインド解除され、メモリページが解放されます。

上記のプロセスは、次の図に示すように、shrink_inactive_list 関数によって完了します。

さらに、アクティブなリンクリスト内のメモリページにも減少プロセスがあり、減少プロセスは次のとおりです。