執筆者 : 小田 逸郎
※ 「OS徒然草」連載記事一覧はこちら
メモリ管理
今回はメモリ管理にまつわるお話です。メモリは、OSが管理するコンピュータリソースとしては、CPUと並んで最も重要なリソースです。メモリ管理は、OSの機能として必須のコアなコンポーネントであると言えます。
OSの仮想空間レイアウト
メモリ管理を設計する上で考慮すべき事項はいろいろとありますが、筆者は、OSの仮想アドレス空間(以下、単に仮想空間)のレイアウトがまずは気になってしまいます。その前に、そもそもOSを仮想空間で動かすのかということも一考の余地があります。と言うのも、筆者がOSに関わり始めた当初は、OSは実アドレス空間(ページングオフ)で動いており、プロセスだけが仮想空間で動いていました。かなり昔は、OSは実アドレスで動くものという暗黙の了解があった気がします。もう今では、OSも仮想空間で動かすのが常識になっています。仮想空間で動かすと何がいいかと言うと、大きな連続域の取り扱いが楽ですし、その他にもいろいろと便利なことがあるのです。
さて、今となってはこれも昔の話になってしまいますが、UNIX(System V release 4)のオリジナルコードでは、OSの仮想空間レイアウトは以下のようになっていました*1。
4GiB(32bitアーキテクチャ前提)を1GiBずつの4つの領域に分けていました。ストレートマップというのは、仮想アドレスと実アドレスが等しくなるようにマップした領域で、V=R領域*2とも呼ばれていました。こうしておくことにより、OSが仮想空間で動いていながら、実アドレスにアクセスするとまさにその実アドレスにアクセス出来てしまうという寸法です。ページテーブルなど実アドレスを扱うものもありますから、これは便利です。次の1GiB分は、ページキャッシュをマップする領域、その次に1GiB分は、user構造体(+カーネルスタック)*3用の領域で、ストレートマップ領域と合わせて、3GiB分がOSが使用する分となります。なお、OSのテキストやデータ領域は、ストレートマップ領域上に存在します。残りの1GiB分は、プロセス空間であり、OS空間とプロセス空間が同居する方式となっています。プロセスが切り替わると、仮想空間が切り替わることになりますが、仮想空間上の最初の3GiB分のマップ内容は同じで、最後の1GiB分だけ異なるということになります。プロセス空間は、0番地ではなく、0xc0000000番地から始まることになります。プロセスが0xc0000000番地よりも小さいアドレスにアクセスしようとすると、当然ながら例外となるようにします。同居方式の良いところは、OSからプロセス空間にアクセスするのが楽なことです。例えば、システムコールのパラメータやデータでプロセス空間のアドレスを指定されるのは良くあることですが、その領域にアクセスするのにOSがアドレス変換する必要ありません。OSの仮想空間が別(あるいは、実アドレス空間で動作)であれば、ページテーブルを追っかけて、プロセスの仮想空間アドレスの示す実アドレスを割り出した上でアクセスする必要がありますし、ページ境界を意識する必要もあります*4。Linux(x86 32bit)でも同居方式が採用されていますね。ただし、最初の3GiBがプロセス空間で、残りの1GiBがOS用ということで、OSの使える領域が少なくなっています。Linuxにもストレートマップ領域はありますが、V=Rではなく、V=R＋αとなっているので、ちょっと面倒です。
さて、筆者がUNIX(System V release 4)を載せようとしていた対象のハードと言えば、スパコン(、メインフレーム)のくせに仮想空間の大きさが2GiB(31bit)しかないという一方、さすがスパコンと言うべきか、実メモリを2GiB搭載できるという代物でした。と言うことは、実メモリすべてをストレートマップすると、その他のOS用領域やプロセス空間をマップすることができなくなってしまいます。少し補足しておくと、当時の2GiBというのは相当の大容量でした。オリジナルコードがストレートマップ領域を1GiB確保していたのは、それだけあれば、もう余裕のよっちゃんで全実メモリをマップできると考えていたからに他ありません。筆者らに課せられた要件としては、プロセス空間もまるまる2GiB使いたいというものもありました。そのため、プロセス空間とOS空間を別にすること(別居方式)を選択せざるを得ませんでした。それでもなお、OS空間のレイアウトが厳しいです。結局、ストレートマップする範囲を限定し、ページキャッシュ領域、user構造体領域とも1GiBよりは減らすことにしました。ストレートマップできなかった範囲にアクセスする場合は、一時的に仮想空間のどこかにマップした上でアクセスすることになります。スパコンでは、ベクトル機構を使用するためにはベクトルページ(ラージページと思って貰っていいです)を使用する必要があり、その領域を予めリザーブするようになっていたので、実メモリの後半部分に割り当てるようにしました。ベクトルページはプロセス空間で使用するもので、OSからアクセスすることはない状況であったため*5、ストレートマップからはみ出す部分がなるべくベクトルページになるようにしておくと都合が良かったのです。
そうした苦労を経験したので、OSの仮想空間レイアウトがついつい気になってしまうという訳です。Linux(x86 32bit)では、ストレートマップできる範囲(896MiB)をはみだした部分を扱うためのHIGHMEMという仕組みが導入されていて、ああ、同じようなことをしているんだな、と思ったものです。筆者がLinuxに関わり始めた頃には、搭載できる実メモリ量も結構増えており、ストレートマップをはみ出る状況は普通のこととなりつつありました。それどころか、仮想アドレス幅(32bit)よりも実アドレス幅(36bit)の方が大きいマシン(Intel PAE)まで出てくる始末です。実メモリの大きさに制限されず、広大なアドレス空間を使用できるというのが、仮想空間の良いところだったはずなのに、それはどうなってしまったのかと嘆いたものです。ああ、早く64bitアーキテクチャが普通にならないかな。そうしたら、こんな苦労はないのに、と思っていました。
今や、64bitが当たり前となりました。めでたしめでたし、と思いきや、アーキテクチャの仕様上、仮想アドレス幅よりも実アドレス幅の方が大きい場合も多いですね*6。まあ、そうは言っても、ストレートマップに収まり切らない実メモリを搭載するのはそうそうあるものではなさそうです*7。
実ページ管理
実メモリというリソースをどう管理するのかは、OSを設計する上で最も基本的なトピックと言えるでしょう。既にご存知のとおり、ハードウェアは実メモリを実ページという単位で取り扱っているので、実ページ単位で管理するのが自然です。実ページを管理する制御表(仮にpage構造体とする)を設け、実ページ数分の配列で確保するのが一般的です。実ページ数は起動時に分かりますし、配列で確保しておけば、実ページ番号をインデックスとして、対応する制御表にアクセスできるので便利です。Linuxもこの例に漏れません。
(注: 以下、文脈上紛らわしくなければ、実ページを単にページと記述しています。)
設計の選択肢として、複数連続したページの割り当てをサポートするかどうかがあります。単ページの割り当てだけで良いのであれば、空きページの管理は、空きページをリンクリストにつなげておくくらいのことで済みます。OSもプロセスも仮想空間で動作している以上、実ページが連続している必要はないので、連続ページ割り当ての必要もないはずです。実際、前述のUNIX(System V release 4)の移植時は、単ページ割り当てしかサポートしてませんでした。ベクトルページの取り扱いがありましたが、こちらは起動時に予め指定した数を固定してリザーブするようにしており、全く別扱いでした。
Linuxに関わり始めて、驚いたことのひとつに、連続ページ割り当てをサポートしていたことがあります。ご存知かもしれませんが、バディシステムというやつで、2のべき乗単位の連続ページを取り扱えるようになっています。うまいこと考えるなあ、と思う一方、こんな面倒なことやる必要あるのかと思ってました。何かのデバイスドライバとか、ネットワーク系のサブシステムが連続ページを使用していたでしょうか。DMAを行うデバイスで連続ページが必要なケースがもしかしてあったのかもしれませんが、本当に必要だったのでしょうかね。昔は、連続ページ割り当ての要求時に空きがなく、ページ解放処理が走るものの、フラグメンテーションが進んでいて、空き連続ページが確保できずに、ハングしてしまうようなインシデントが結構発生していた記憶があります。連続ページが本当に必要かどうかに関わらず、使えれば使ってしまうのが世の常です。エンジニアとしては、こうすれば実装できると思いつけば、実装したくなるものではありますが、一度実装してしまうと、後方互換のため、ずっとサポートする必要が出てきますので考え物です。また、品質確保の面からは、必要ない機能は極力入れないのが肝要です。筆者は元々商用ソフトの開発部隊の出ですので、その思いが強く出てしまう傾向があります。通常、新版の開発は旧版の保守をしながら行われることになります。誰しも、インシデント対応なんかよりも(、本能の赴くまま機能追加できるわけではないと言え)、新規開発の方が面白いものです。インシデント対応があると、新規開発の集中力は削がれるは、修正提供・報告書作成などの面倒な作業は増えるは(、開発工程を変更できる訳ではないので)、残業は増えるはで、何もいいことはありません。なので、品質確保に関するモチベーションは非常に高くなります(少なくとも筆者はそうでした)。翻ってOSSの世界はどうでしょうか。プロジェクトの性質にもよると思いますが、基本的には、好きでやっている人たちの集まりですから、実装ができると思いついた機能は、どんどん実装していく一方で、品質確保のモチベーションはあまり持ち合わせていないケースが多いかと思います。機能をどんどん実装することは、進歩のためには良いことですが、安定性とのトレードオフにはなります。OSSの採用は、こうした特性も考慮する必要があります。今やOSSなしでは済まない世の中に成りつつあります。なので、絶対止まらないシステムなぞ目指すより、落ちること前提で全体としてなんとか継続の考え方が主流になってきているのでしょうね。
閑話休題。
連続ページと関連して、ラージページの取り扱いも考えておく必要があります。搭載できるメモリ量も増えて来ましたし、使用できれば性能的に有利なケースも多いので、これから使用されるケースが多くなっていくと思います。前述のベクトルページの取り扱いと同様に、システム起動時に固定数リザーブというのが単純ではありますが、使われなければ、無駄となりますし、足りなくてもそれ以上は使えないということで、使い勝手は悪いです。動的に確保するにしても、システム起動直後ならいざ知らず、使用が進むにつれ、フラグメンテーションが進行して、ラージページ分の連続ページが空いていることは稀になってくるでしょう。使用しているページをスワップ(交換)するなどして、積極的にラージページを確保するような実装が必要となってくると思います。OSも仮想空間で動いていることですし、うまく設計することも可能かと思っています*8。
動的メモリ割り当て
OSが取り扱う制御表には、page構造体のように予め数が分かって確保できるものばかりではなく、必要となったときに動的に確保する必要があるものも多いです。アプリケーション開発からOS開発に来た人がまず戸惑うのが、OSにはmallocがないということではないでしょうか。では、mallocを使わずにどうやってメモリを確保するのでしょうか。良くある方法は、ページ単位で制御表を補充するというものです。すなわち、空き制御表がなくなったら、実ページを1ページ確保し、それを制御表の大きさで分割し、その制御表の空きリストにつなげるというものです。まあ、単純ですね。昔のOSは、大体こういう単純なことしかしていなかったです。Linuxでは、slabというものがありますが、非常にざっくり言うと、この方式を少し汎用化したものです。
制御表を動的に確保できるのは、便利ではありますが、性能やメモリ使用量の見積もりのし易さを考えると、静的に割り当てておく方が有利です。筆者が関わっていた当初のOSでは、主要な制御表(ex. Linuxでのtask構造体のようなものを含む)は、静的に確保するようになっていました。提供しているOSのバイナリは完成形ではなく、システムインストール時に最大プロセス数などのパラメータを入力して、OSの最終リンケージを完成させる作業をするようになっていました*9。その際に各種制御表が配列として静的に確保させる仕掛けでした。まあ、導入数が少ないかつ、そもそも導入自体が大がかりなメインフレームが対象だから出来たことで、不特定多数にインストール可能な製品では難しいかもしれません。このような方法もあるのだということでご参考まで。そもそも取り扱う制御表の種類がまだ少なかったというのもあるかもしれません。少し、話は変わって、eBPFネタとなりますが、最近のLinuxでは、BTFと言うデバッグ用のデータ構造が入るようになっていて、これを利用して、以下に示すコマンド実行で、Linuxで使用している構造体を網羅したヘッダを作成することができます。
bpftool btf dump file /sys/kernel/btf/vmlinux format c > vmlinux.h
できたヘッダ(上記では、vmlinux.h)の行数を数えてみると、なんと150Kくらいあります。以前、OS全体で20Kだったという話をしました*10が、今やヘッダだけで150Kですか。もう個々の制御表を静的に確保しようなどと言えるような数じゃあないですね。
閑話休題。
最初に立ち戻って、なぜ、OSにはmallocがないのでしょう。元々、実アドレス空間で動いていたり、仮想空間で動くようになっても、仮想空間の大きさが潤沢ではなかったというのが理由かと思います。64bitアーキテクチャでは、仮想空間は十分な大きさなので、OSの仮想空間にもヒープ領域を設けて、普通にmallocを実装することもできるかと思います。64bit前提で新規にOSを設計する際には選択肢のひとつとなるかと思います。
プロセス空間
以前、仮想空間の回*11のときに、機を改めていろいろなテクニックを紹介すると書いてしまった手前、ここで触れておきましょう。まず頭に思い浮かぶのは、なんと言ってもコピーオンライトでしょう。UNIXでは、プロセスを生成するのに、親プロセスのコピー(fork)を行う必要があります。初学者は、なぜ、わざわざ一旦コピーしないといけないのか、新規にプロセスを生成することができないのかと素朴な疑問を持つかもしれません。実は筆者はそれに対する明確な回答は持っていません。新規にプロセスを生成するシステムコールがあってもいいと思いますし、実際にそれを実装したこともあります*12。話をforkに戻しますと、原初のUNIXでは、ご丁寧に親プロセスが使用しているページ分のページを割り当てて、すべてのページをコピーしていました。という訳で、forkというのは大変重い操作でした。forkした直後にexecするケースでは、全く無駄な処理をしていることになるので、直後にexecすることを前提に、一時的に親の使用しているページを借りてexec処理を行う、vfork というシステムコールができたのもそういった背景があります。まず、ここで良く考えると、リードオンリーの領域に関しては、ページを共有すればよく、わざわざコピーしなくてもいいんじゃないかということに気が付きます。コピーするのはリードライト可能な領域だけで良くなりました。ここで、さらにずる賢い人が考えました、ライト可能であっても、アクセスしなかったり、リードアクセスだけだったら、コピーする必要ないんじゃないかと。そのような思考の過程を経て、コピーオンライトが編み出されたと想像します。コピーオンライトの実装としては、リードライト可能領域に関しても、一旦はページ共有しておき、ただし、ページのライト権を落としておきます。ページのライト権は、そのページをポイントするページテーブルエントリ上で設定できます。ページをポイントするすべてのページテーブル上でライト権を落としておきます。プロセスがリードアクセスしている分には何も問題は起きませんが、ライトアクセスしようとすると、例外が発生し、OSに制御が移ることになります。OSは、不正なアクセスであれば、もちろんSIGSEGVにする訳ですが、アドレスは正当でかつライト可能領域なのに、ライトアクセス例外が起きたことを以て、これはコピーオンライトだとピンと来るようになっているという寸法です。OSは、アクセスしたプロセスに新たなページを割り当て、コピーします。ライト権は戻した上で、例外処理を終え、プロセスは何事もなかったかのように処理を続けます。なお、共有していた相手に関しては、それが最後のひとつであれば、ライト権を戻しておけばよいでしょう。まとめると、はじめてライトアクセスされたときにページをコピーする、というのがコピーオンライトです。
話は変わりまして、これまた筆者がLinuxに関わり始めて驚いたことのひとつなのですが、oom killer の存在です。メモリが足りなくてにっちもさっちも行かなくなったら、プロセスをkillして、空きメモリを確保する(!?)。いやいや、いくらなんでもそれは乱暴すぎないかい。システム全体が止まってしまうより良いのは確かではあるが、まともなOS屋なら思いつかない発想だと思います。暴走してメモリを食いつぶしているプロセスがあるのであれば、killしてやりたい気持ちは分かりますが、そうだとは限りませんし、quotasを設定するとか別手段で対策しておくのも大事でしょう。スワップ領域を十分に確保しておくことも大事です。いざとなれば、プロセスが使用しているページをページアウトすることにより、空きメモリを確保できます。プロセスにページ割り当てする際、それに対するスワップ領域を必ず予約しておくということも考えられ、OSの実装によっては、安全側に倒して、これを採用していることもあります。これであれば、前述の暴走プロセスへの対策にもなります。ところで、弊社は、最近流行りの Kubernetes も取り扱っており、門外漢ながら筆者も少しは触っているのですが、気になる記述を見つけました。Kubernetesを使うには、スワップをオフにせよと。いやいやいやいや、それ危険すぎますよ、と声を大にして言いたいです。まあ、スワップが起きてしまうようでは、性能的には問題ありで、事前にスワップが起きないようリソース設計をきちんとしましょうというのは確かではありますが、いざと言うときの保険にスワップ領域は十分確保してオンにしておきましょう。
実ページの回収処理
スワップの話が出た流れで、ページの回収処理についても触れておきましょう。実ページの使用用途としては、OSが使用するもの、プロセスが使用するもの、ページキャッシュがあります。空きのページがなくなってきたときにどうするかですが、プロセスが使用しているものはページアウトすることにより、空きのページを得ることができますし、ページキャッシュに関しては、所詮キャッシュなので、いざとなったら解放すれば良いです。OSが使用しているものは基本的には解放することはできません。問題は、どのページを解放するかですが、できれば使われそうなページを残して、使われていないページを解放したいです。最も一般的に用いられる考え方は、最近使ったページはまた使われる可能性が高いだろう理論です*13。最近使ったかどうかを判断するために、ページテーブルエントリ上のアクセスビット*14を使用します。これは、ページへのアクセスがあったときにハードウェアが自動的に立ててくれます*15。ビットを落とすのはOSが任意のタイミングで行えます。OSの処理としては、定期的にアクセスビットをチェックし、立っていなかったら(例えば、page構造体に使われていない期間カウント用メンバを用意しておき)、カウントアップ、立っていたら、カウントをクリアし、ビットは落としておく、というようなことが考えられます。解放するページを選択する際にこのカウントを参考にするという訳です。
どのページを残すかは、性能面を考えると非常に重要で、メモリ管理を設計する上で十分に考慮すべき事項となります。なお、回収部分だけでなく、割り当て部分も合わせて設計する必要があることには注意しておきます。先ほどの理論は経験的には結構当たっていると考えられ、その判定のために使用できるハードウェア機能もありましたが、逆に言うと、そのくらいしかハードウェア機能がなかったとも言えます。何か他に良い選択手段があると良いのですが。最近はメモリの搭載量も増えており、したがってページ数も膨大なので、先ほどのビットチェック処理も非常に重くなってきています。ますます、他の良い手段が求められていると言えるでしょう。皆さんも考えて見ては如何でしょうか*16。
あとがき
メモリ管理の話題はこんなところです。見出しを見ると、旧解読室のメモリ管理の見出しと似ていることに気が付かれたかもしれません。旧解読室では、筆者が考えるメモリ管理の設計ポイントについて、Linuxではどう実装しているのだろうと調べた内容が書かれています。次回は、これまで封印してきたあの話題に触れたいと思います。ではまた次回。
*1:もうだいぶ曖昧になってきた記憶を基に書いていますので、違っているかもしれませんが、大体こんな感じだったはずです。
*2:Vは、virtualで、Rは、realです
*3:Linuxのtask_struct構造体(+カーネルスタック)にあたるものと考えれば良いです。
*4:注意しておくと、同居方式でもページアウトされていたときの考慮は必要で、そうそう単純ではありません。
*5:ファイルI/Oはページキャッシュを経由しないダイレクトI/Oが前提。
*6:例えば、RISC-V SV39、SV48。
*7:Linux(RISC-V SV48)では、ストレートマップ 64TiB 分確保されています。
*8:現在のLinuxの実装を知らずに言ってます。既に実装されているのであれば、りっぱです。
*9:SYSGEN(system generation)と呼んでいました。
*12:exec相当のパラメータも指定することになります。
*13:言い方を変えると、最近使われていない(Least Recently Used)ページを解放するということで、LRUと言うキーワードを耳にしたことがあるかもしれません。
*14:アーキテクチャにより、リード、ライト、実行の区別もできます。
*15:アーキテクチャにより、ビットが立っていないと例外が起きる、すなわち、ビットは、OSが立てないといけないものもあります。RISC-Vの場合、仕様書によると、ハードウェアとしてどちらの実装もOKとなっています。
*16:これも現在のLinuxの実装を知らずに言ってます。既に実装されているのであれば、りっぱです。
