Linux の LRU リストについてのメモ
前提: Reclaimation
メモリは階層的に管理される。ページキャッシュは多くの場合 CPU キャッシュ (L1/L2/L3)、 RAM 、ディスク (の swap 領域) に保存される可能性がある。この階層は、上位の媒体ほど高速だが容量が小さく、下位ほど低速で容量が大きいという特徴がある。 頻繁に利用されるページキャッシュに高速でアクセスできるよう、 CPU キャッシュや RAM で保持したい。逆に、メモリが不足する場合は、アクセスしないページキャッシュをディスクに追い出す (evict) ことも必要となる。
Traditional Linux LRU lists
従来の kswapd は 2つの LRU リストを持つ。
- active_list: すべてのプロセスの active なページキャッシュのリスト
- inactive_list: reclaim の候補となるページキャッシュのリスト
ページキャッシュは allocate されると inactive_list に繋がれる。アクセスが発生すると active_list に移動される。 active_list の末尾の要素が inactive_list に移動することで reclaim の対象となる。 なお、 active_list -> inactive_list 移動の対象となったページキャッシュは、その参照などもチェックされ、たとえば対象ページへの参照があれば active_list に戻されたりするようだ。 単純な LRU リストではなく active_list / inactive_list の 2つのリストを使用している理由は、 reclaim してはならないページキャッシュと可能なそれを分けるためだと思われる。
LRU-like な方法でうまくいかない場合があるとのこと。例えば:
- inactive_list にあるページが anonymous pages の場合。 anonymous ページを RAM からディスクへ swap するのはコピーする時間がかかる。もともとディスクにデータがある (例えば、プログラムコード) ページ (file-backed page) ではこの作業が必要ない。
- 一つのプロセスが大量の file-backed page に書き込みを行った場合。書き込まれたページ (dirty page) の内容は、swap の前に本体のファイルに書き込まれる必要がある。その間にまたページへの書き込みが行われ、 active_list に戻ったりする。
参考:
次
- Multi-Gen LRU (MGLRU)
#public