コピーオンライトとその周辺の復習をする
2019/1/25
最近になって少しGCの本を読み始めました。
Mark Sweep GCという基本的なGCのデメリットに「コピーオンライトとの相性が良くない」というのがあるのですが、コピーオンライトってなんですかって。
ちょっと復習してみます。
コピーオンライトとその周辺について。
仮想記憶とページテーブル
何がしたいって、まぁ、プロセスにメモリを割り当てたいのです。
ソフトウェア上で何らかの命令を実行するとなると、とりあえず一旦メモリ上にそれらをロードします。 プロセスも同じで、プロセスは起動するとOSからメモリをもらいます。
ですが、これをそのままパソコンに乗っかっている物理的なメモリ上に割り当てていくと問題が起きてしまいます。
直接的に物理メモリに割り当てた場合
物理的なメモリのことを「物理メモリ」と呼びますが、以下の図のように1ブロックが1GBを表すような物理メモリを考えてみます。
黒が使用中の部分、白は空いている部分です。
今は、5GBが使用中のようです。
https://gyazo.com/63de17809b01607bfe1faf34cfe3a27a
ここから、さらに割り当てたり、解放したりを繰り返して以下のようになりました。
4GB空いていますが、飛び飛びになってしまいました。
https://gyazo.com/e5ac5661fa7d2c955cdd3804a92a27ca
ここでユーザーが2GBのオブジェクトを割り当てたいと思ってもできなくなってしまいます。
これをメモリの断片化といいます。
GCの話でもよく出てくる話題です。
https://gyazo.com/eb105f960956e3ce5857d8b506aa96e3
物理メモリを直接扱うと、メモリの断片化の他にも問題が起きてしまいます。
例えばこのままでは、あるプロセスは、他のプロセスやカーネルが使っているメモリ領域にもアクセスすることができるので、システムが脆弱になってしまいます。
なんらかのアプリケーションを起動するとOSが乗っ取られるのです。やばいですね。
そこで仮想記憶ですよお兄さん
ってのが不便だってことで仮想記憶というものを使います。 仮想的なメモリのアドレスを使って物理メモリ上のアドレスへ間接的にアクセスします。
こうすると物理メモリ上では飛び飛びのオブジェクトも、隣り合ったように扱うことができます。
これでメモリの断片化の問題は解消されそうですね。
https://gyazo.com/f50a7595531ba08c6c2f5f8fdb65e162
物理メモリ上のアドレスのことを「物理アドレス」と呼び、同様に仮想的なメモリ上のアドレスは「仮想アドレス」と呼びます。
僕らがコマンドの実行などで見るアドレスは、すべてこの仮想アドレスの方になります。
では、どうやって物理アドレスと仮想アドレスを対応付けるのかと言うと、そうです、お察しの通り「ページテーブル」というものを使います。 「仮想アドレスの300番は、ふむふむ、物理アドレスの800番ですわ」的なことをページテーブルを見て確認し、アドレス変換(Address Translation)をするわけです。
ちなみに、ページテーブルの個々の項目のことを「ページテーブルエントリ(PTE)」といいます。
https://gyazo.com/4286ee649769e9d5b462434fe99a76ae
「何で『ページ』やねん、Webページかなんかと関係あるんか？」って最初思ってしまいましたが、「ページ」というのはメモリを管理する単位のことです。
メモリ全体は一つ4KBのページに分割して管理されています。
つまり、この記事にあるメモリの図は1ブロック1GBなのでだいぶ雑なのです。
メモリにアクセスするたびにこのページテーブルを見ていると遅くなりそうですが、ここではTLB(Tlanslation Lookaside Buffer)というPTE専用のキャッシュを使用したりすることで高速化しています。
【参考】
プロセスと仮想記憶
アドレスによってアクセスすることのできる範囲のことを「アドレス空間」といいます。
そして、仮想アドレス空間はプロセスごとに独立して作られます。
同時に、各プロセスが自分のページテーブルを持っています。
この仕組みにより、あるプロセスが使用しているメモリ空間に、別のプロセスがアクセスしてくることを防ぐことができるわけです。
ちなみに、ページテーブル自体もメモリ上に置いてあります。
ただし、それは端っこの方にあるカーネルが使用するメモリ領域上にです。
計算が速い方はお察しの通り、そのままフラットなテーブルを用意するだけだとページテーブルのサイズはめちゃくちゃ大きくなってしまうので、それを避けるために階層型のページテーブルを用いたりもします。
が、早くコピーオンライトの話に行きたいのでここでは省略します。
コピーオンライト
やっときましたコピーオンライト。
ちょっと前の記事でも少し書きましたが、もう少し詳しく書いてみます。
「Copy on Write」。
WriteしたときにCopyする。
そのまんまの意味ですね。
“CoW”と略記されることも多いようです。
一言で言うと、fork()によって作られたプロセスが、書き込み時に物理メモリ上で親子別々になる仕組みのことです。
ちょっと簡潔に言い過ぎました。
もう少し丁寧に書いてみます。
「新しくプロセスを作りたい」って思った時にどうするかというと、基本的には、すでにあるプロセスを複製することで実現します。
この時に使うのがfork()システムコールです。fork()システムコールを使って、親プロセスから子プロセスを作ります。
親プロセスと全く同じ内容の子が生まれるのです。
無性生殖みたいなやつです。
しかし、実は複製されてないんですよね。
いや、してるのはしてるんですけど、まだ物理メモリ上は同じところを見ています。
各プロセスが各自のページテーブルを持っていることは先に述べましたが、このfork時にはこのページテーブルのみがコピーされます。
https://gyazo.com/2a5fd6b22fcd8044f3301ea145ba4475
では、一体どのタイミングで物理メモリ上でも複製されるのでしょうか。
それは「書き込みがあったタイミング」です。
親か子、いずれかプロセスのアドレス空間に対して書き込みがあったタイミングで、完全にコピーされます。
この仕組みこそが「コピーオンライト」ってやつです。
もうすこし具体的に手順を見てみる
まず最初にfork()システムコールが呼ばれると、そのプロセスのページテーブルがコピーされます。
このページテーブル自体は、カーネルのメモリ上に作られます。
そして、この状態ではこの2つのプロセスの全ページに対する書き込み権限が無効化されています。
そしてこのメモリのどちらかに対して書き込みが行われると、CPU上でページフォールトが発生します。
書き込み権限がないのに、書き込もうとしたからですね。
すると、このページフォールトを検知してカーネルのページフォールトハンドラが仕事を始めます。
まず、アクセスされたページを物理メモリ上の別の場所にコピーします。
ここで初めてコピーされるのですね。
そして、新たなページに対応するようにページテーブルエントリを更新します。
https://gyazo.com/4842c9287d707780b6d0c9a037be17d2
これで準備は整ったので、新しく紐付けられた物理メモリ上に、先ほど中断された書き込み処理を行います。
その後、別の方のプロセスでも書き込み権限を有効化します。
なにが嬉しくてこんなにややこしいことをするのか
CoWによるメリットはパフォーマンスの面で得られます。
メモリ内のデータを丸ごと複製すること自体はとても時間的コストの掛かる処理です。
仮にCoWがない場合のことを考えてみましょう。
プロセスをforkした瞬間に丸ごと複製することになりますが、ここで作られたものは読み込みのみに使われて役目を終えるかもしれません。
https://gyazo.com/6a476c50869f8ddf8b1e245880b3d268
そうすると、わざわざコストを払ってしたコピーが無駄になってしまいます。
書き込みがあって、本当に必要になった時にコピーすることで、その無駄を省くことができます。
関数型言語の遅延評価に似た効果が得られるわけです。
また、時間的コストだけでなく、無駄に物理メモリが消費されないので、資源面のメリットもあります。
逆に、デメリットは実装が複雑になることが挙げられます。
所感
仮想記憶やページテーブルやコピーオンライトについてちょっと復習してみました。
限られた資源をいかに有効活用するか、そのアイディアに圧倒されますね。
GCについて見ていくとこの辺のことはばんばん出てくるので、しっかり頭に入れておきたいです。
参考