Linuxメモリ管理の最先端を探る

小崎 資広
2008/5/22

　この記事では、Linux Kernel Watchの番外編として、Linuxの最近のメモリ管理周りの動きと、その背景のモチベーションについてお伝えしたいと思います。

　メモリ管理は変更時のインパクトが大きいため、通常、Stable Tree（安定ツリー）ではあまり変更はなされません。しかし、Linuxカーネルメーリングリスト（LKML）の議論では「もうカーネル2.7は出ない」ともいわれており、十分なテストがなされたものであれば、アグレッシブなパッチでも受け入れられるようになっています。

　また、メモリの急速な大容量化により、いままで問題にならなかった部分にスケーラビリティ上の問題が発生したという報告もちらほら出てきました。それを解消するためのさまざまな改善が提案されています。

　こうした背景により、2007年から2008年にかけては相当面白いパッチが出てきました。この記事では、独断と偏見に基づいて興味深いパッチをいくつか選び、その機能と開発背景を解説したいと思います。

注意：残念ながらカーネルハッカーの面々にはものぐさな人も多く、コードはクールなのに、そのパッチの必要性が十分説明されていない場合がしばしばあります。その場合、わたしが想像力で補って解説していますが、背景の理解不足のため間違っていることもあるかもしれません。申し訳ありませんが、その旨、あらかじめご了承ください。

フラグメンテーションに対する改善

　DOS時代に「コンベンショナルメモリが分断されてメモリが確保できない……」などと枕を涙で濡らした経験のある読者もいらっしゃるかと思います。Linuxカーネルも同じ悩みを抱えています。

　何日もリブートせずにシステムを動作させていると、見えないところでメモリのフラグメンテーションがどんどん進んでいき、いざページサイズを超えるメモリ要求がきたときにメモリ確保が失敗してしまうのです。

　カーネルの中で、ページサイズを超える連続領域を必要とする部分は少ないのですが、いくつかのドライバはハードウェア的な制約により、連続した物理メモリを必要とします（特にビデオカードとギガビットイーサネットは問題に遭遇することが多いようです）。

　このフラグメンテーション問題が、ここ半年で大きく改善されました。

■Lumpy Reclaim

　Linuxでは、メモリが不足してくるとページフレーム回収処理のプロセスが走り、不要なキャッシュを捨てる仕組みになっています。このとき、通常は最も使われていないページから順に捨てられていきます。ところが、回収されるページフレームは、常に物理メモリ上で連続しているわけではありません。たいていは必要なメモリの数倍のメモリを解放して初めて、物理メモリ上に必要なサイズの連続した空き領域ができるわけです。

Lumpyがない場合のページ解放

　フラグメンテーションが進んでくると、困ったことに、これが数倍では済まず、数百倍〜数万倍になるなんてことも十分あり得ます。

　それはさすがに無駄だろうということで、Peter ZijlstraとAndy Whitcroftがパッチを提案しました。ページフレーム回収の契機となったメモリ確保要求のサイズがある閾値（現在はページサイズの8倍に設定されています）を超えた場合は、破棄されることになったページフレームの物理アドレスと隣接した物理アドレスを持つキャッシュページを、ページへのアクセス率に関係なく無理やり回収してしまうというものです（力業ここに極まるという感じですね）。

Lumpyがあると効率的にページを回収できる

　この方法では、ものすごく頻繁に使われるページが回収されてしまう可能性もあるわけで、若干リスキーな方法ともいえます。ですが、前述の何万倍ものメモリ解放の無駄に比べれば、かなりの性能向上が見込めます。このパッチは2.6.23でマージされました。

■Anti Fragmentation

　これは、Lumpy Reclaimのようにフラグメントした後の対処ではなく、最初からフラグメントしにくいようにメモリ割り当て方式を改善するというMel Gormanによる提案です。

　基本的なコンセプトは単純です。典型的なフラグメンテーションは、連続したメモリA、B、Cが確保され、AとCが解放されたにもかかわらずBが解放されない、という状況で発生します。逆にいうと、隣り合ったメモリがだいたい同時期に解放されるような仕組みがあればいいわけです。

　そこでAnti Fragmentationは、カーネルで使われるメモリには短命なものと長命なものとに大きな差があることを利用します。

　カーネルが内部的なデータ構造のために確保するメモリは、半永久的に解放されないこともまれではありません。逆に、ユーザープロセス用のメモリは一般的に短命です。なぜなら、UNIX系システムの特性として短命プロセスが多いというのもありますし、プロセス自体が長命であっても、プロセスのメモリはスワップアウトさせることができるからです。

　そのため、メモリ確保要求を用途ごとに分別し、似たような用途のページが物理アドレス的に近くなるように割り当てます。これにより、半永久的に解放されないページが、キャッシュとキャッシュを分断するようなすごく邪魔な場所に確保され連続領域が取れない！ という事態を防ぐことができるというわけです。

　Anti Fragmentationパッチは、メモリを「UNMOVABLE」「RECLAIMABLE」「MOVABLE」「RESERVE」の4種類に分類します。

　UNMOVABLEはカーネルが内部的に使うメモリで、カーネルは物理アドレスをポインタとして保持しているので勝手に移動させることはできません。これは一般的に長命なメモリです。RECLAIMABLEはページキャッシュ・inodeキャッシュなどのキャッシュ類であり、どちらかというと短命メモリです。MOVABLEはユーザープロセス用のメモリで、これも短命メモリです。

　RESERVEはちょっと特殊で、空きメモリが逼迫（ひっぱく）しない限り使われない虎の子メモリを表しています。たいていの場合カーネルは、pages min（/proc/zoneinfoで表示されます）と同量のメモリにRESERVEマークを付け、普段は絶対に使わないメモリとして扱います。こうすることで、いざメモリが逼迫してきたときには、RESERVEのfree listを探すと都合よく連続メモリが残っており、メモリ確保が成功する、という巧妙な仕組みになっているのです。

　この活動は当初、デフラグ嫌いのLinusから「そんなものは仮想化でやれ」などとといわれ、紆余（うよ）曲折がありましたが、2.6.24で無事マージされました。

■Slab Defragmentation

　上記2つのパッチは、複数のページが必要なときに連続領域が確保できない「外部断片化」という問題に対する対処でした。これに対しSlab Defragmentationのパッチは、ページ内部でのやりくりがうまくいかず、ページ内部に未使用領域が増えてしまうという「内部断片化」という問題に対する改善で、Christoph Lameterにより提案されました。

　Linuxにおいて、ページサイズ未満のメモリはSLAB（スラブ）という仕組みで管理されています（関連記事）。

　SLABは、メモリ割り当て時、部分的に使用中のページがあればそこから優先的にメモリを割り当てる仕組みを持っています。このため、SLABを用いた確保と解放が交互に動いているような状況では、無駄な領域はほとんど発生しません。

　しかし、メモリ確保が非常にたくさん連続して発生した後に、メモリ解放がこれまた連続して発生すると、部分的に使用中のメモリが大量にできてしまうことになります。これがSLABのフラグメンテーションと呼ばれる問題です。

　SLABのヘビーユーザーには、inodeキャッシュとdentryキャッシュがあります。それぞれ、ファイルのメタデータとパス名をキャッシュするものですが、不幸なことにこの2つでは、findやupdatedbコマンドによって簡単に上記のワーストケースが発生してしまいます。

　そのため、SLABのフラグメント率を監視し、あるフラグメント率（デフォルトでは30％です）を超えたら、メモリ不足時の回収処理の延長でデフラグルーチンが作動し、その結果空いたページを解放する仕組みが実装されました。名前に反してSLUB（注1）にしか実装されていないのはご愛嬌（あいきょう）というところです。

Slab Defragmentationの仕組み

　SLUBは実装上、断片化が発生しにくいよう考慮されています。このため、上記のようなワーストケースを除き、通常はそこまでフラグメントが進むことはないので、一般的なワークロードでは性能オーバーヘッドも発生しません。

　このパッチは最近、Andrew Mortonが管理する-mmツリーにマージされましたが、まだupstreamにはマージされていません。おそらく2.6.27前後でマージされるものと思われます。

注1：SLUBとはChristoph Lameterにより実装されたSLABの改良版です。より高速化されており、2.6.23以降はデフォルトのアロケーターとなっています

1/2

Index Linux Kernel Watch　番外編 　Linuxメモリ管理の最先端を探る

Page 1 　フラグメンテーションに対する改善 　 Page 2 　VM（仮想メモリ）の改善 　仮想化関連の改善 　期待の新機能、memcgroup

連載 Linux Kernel Watch

---

Linux Squareフォーラム Linuxカーネル関連記事

	連載：Linux Kernel Watch（連載中） Linuxカーネル開発の現場ではさまざまな提案や議論が交わされています。その中からいくつかのトピックをピックアップしてお伝えします
	連載：Linuxファイルシステム技術解説 ファイルシステムにはそれぞれ特性がある。本連載では、基礎技術から各ファイルシステムの特徴、パフォーマンスを検証する
	特集：全貌を現したLinuxカーネル2.6［第1章］ エンタープライズ向けに刷新されたカーネル・コア ついに全貌が明らかになったカーネル2.6。6月に正式リリースされる予定の次期安定版カーネルの改良点や新機能を詳しく解説する
	特集：/procによるLinuxチューニング［前編］ /procで理解するOSの状態 Linuxの状態確認や挙動の変更で重要なのが/procファイルシステムである。/procの概念や/procを利用したOSの状態確認方法を解説する
	特集：仮想OS「User Mode Linux」活用法 Linux上で仮想的なLinuxを動かすUMLの仕組みからインストール／管理方法やIPv6などに対応させるカーネル構築までを徹底解説
	Linuxのカーネルメンテナは柔軟なシステム カーネルメンテナが語るコミュニティとIA-64 Linux IA-64 LinuxのカーネルメンテナであるBjorn Helgaas氏。同氏にLinuxカーネルの開発体制などについて伺った
	more

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）