UNIX 6th code reading - スワッピング

はじめに

今回は14章の「プログラムスワッピング」を読み解いてきます。

スワッピング処理とは

高速であるが、高価・小容量である物理メインメモリ(コアメモリ)を効率よく使用するためにプログラムスワッピングという機構があります。

コアメモリが足りなくなったら、寝ていたり使っていないプロセスのデータセグメントを、ディスクなど低速だが大容量のスワップ領域に待避します(スワップアウト)。

スワップアウトしたデータが必要になったら、スワップ領域からコアメモリに戻します(スワップイン)。

絵にするとこんな感じです。

スワッピングの単位はデータセグメント、テキストセグメント単位のようです。なので、ページングと違い、コアメモリ以上に大きなプログラムは実行できないのではないかと思います。(スワッピングとページングは比較するものではない？)

共有テキストセグメントとは

プロセスが保持しているセグメントのうち、テキストセグメントはプログラムコードや定数など、プログラム実行中でも変更されることがないデータが入っています。

不変なデータなので、複数のプロセスで共有できます。共有することでメモリの使用効率を上がります。

プロセスが使用するテキストセグメントはproc構造体のp_textpで指定します。

絵にするとこんな感じです。

共有テキストセグメントを管理するためにtextという構造対の配列を使用しています。この配列は常にコアメモリに存在しているため、テキストセグメントの探索などは高速で行えます。

textにはテキストセグメントがいくつのプロセスから参照されているかを表すカウントを持っています。

text.x_ccountは、コアに存在するプロセスがそのテキストセグメントを参照しているプロセス数を表します。この数がゼロになるとそのテキストセグメントがコアから解放されます。

text.x_countはコアだけでなくスワップに存在するプロセスも含めて、そのテキストセグメントを参照しているプロセス数を表します。この数がゼロになるとそのテキストセグメントがスワップ領域から解放されます。

sched

sched( )はプロセススワッピングを行います。

スワップイン対象プロセスを探す

• 1958 : クロック割り込みによってp_time(後述)が加算されないように、プロセス優先度を６に上げる
• 1959-1970 : 実行可能で(SRUN), スワップアウトされていて(SLOAD = 0)プロセスの中で、一番長くスワップ領域にいるプロセス(p_time max)を探す。p_timeはスワップイン、スワップアウトされたときにリセットされ、クロック割り込みで1秒毎にカウントされる。よって、コア、もしくは、スワップ領域に存在する時間を表す。もし該当プロセスが見つからなかったら、runoutをインクリメントして寝る。runoutは実行可能なプロセスがスワップ領域に存在しないことを示すフラグ。つまり、スワップインさせることができるプロセスが存在しないことを表す。

コアメモリの空き領域を確保する

• 1979-1981 : スワップインするプロセスが保持しているテキストセグメントがコアにない場合、コアにテキストセグメントをコピーするためにプロセスのサイズをその分増やす
• 1982-1983 : スワップインするプロセスのためにコアメモリの領域を確保する。成功したらfound2(2031)へ飛ぶ

コア領域に空きがなかった場合、コアにあるプロセスをスワップアウトする

まずは、優先度ゼロ以上で寝ているかトレースのストップ状態にあるプロセスを探します。

sleep( )で寝るときの優先度はスワップアウトされやすさにも影響してくるようです。

• 1991-1994 : コアに存在し(SLOAD)、スワッピング中ではなく(!SLOCK)、システムプロセス(!SSYS, proc#0のこと?)ではないプロセスで、優先度ゼロ以上で寝ている(SWAIT)かトレースのストップ状態(SSTOP)であるものを探す。proc配列の先頭から探していくので、proc配列の前方にあるほどスワップアウトされやすい。見つかったらfound1(2021)へ

該当プロセスが見つからなかった場合、優先度負で寝ているか実行可能なプロセスのうち、最もコアに存在する時間が長いプロセスを探します。

ただし、スワップインしようとしているプロセスが、スワップアウトされてから3秒立っていない場合、もしくは、スワップアウトしようとしているプロセスがスワップインされてから、もしくは、生成されてから2秒たっていない場合は寝ます。これは、過度なスワッピングによる処理効率の低下を防いでいるのではないかと思います。

• 2003-2004 : スワップインしようとしているプロセスが、スワップアウトされてから3秒立っていない場合、sloop(1953)に戻って、runinをインクリメントし、寝る。runinは、スワップアウトされているプロセスの中に実行可能状態のものが存在するが、スワップアウトされてから3秒立っていないという状態、もしくは、スワップアウトしようとしているプロセスがスワップイン、もしくは、生成されてから2秒たっていない状態を表す
• 2006-2015 : コアに存在していて(SLOAD), スワッピング中ではなく(!SLOCK), システムプロセスではない(!SSYS)プロセスの中で実行可能状態(SRUN)か優先度負で寝ている(SSLEEP)もののうち、一番長くコアに存在しているプロセスを選ぶ。ただし、そのプロセスがコアに入ってから2秒立っていなかったらsloopに戻って寝る

スワップアウト処理

• 2022 : 優先度を0に戻す。この時点でスワップアウト対象のぷろせすがrpに保持されている
• 2023 : スワップアウトするプロセスのSLOAD(コアにいる)フラグをオフにする
• 2024 : xswap( )(4638)を呼び出してスワップアウトする。第二引数が1なので、プロセスはコアから解放される
• 2025 : loopへ戻ってスワップイン対象のプロセスを選び直す。まだコアの領域が足りないこともありうる？

スワップイン処理(テキストセグメント)

• 2032-2033 : p1にはスワップインするプロセスが保持されている。そのプロセスが共有テキストセグメントを保持していて、かつ、その共有テキストセグメントがコアに存在していなかったら。つまり、スワップ領域にしか存在しなかったら
  • 2034-2035 : swap( )(5196)を呼び出して、そのテキストセグメントをコアにスワップインする。aはプロセス固有領域の先頭アドレス。テキストセグメントはプロセス固有領域の先頭にロードされる。失敗したらpanic
  • 2036-2037 ; そのテキストセグメントにコアのアドレスを設定し、プロセス固有領域のアドレスをテキストセグメント分加算する
• 2038 : そのテキストセグメントの「コアに存在しいているプロセスからの参照数」をインクリメントする

スワップイン処理(データセグメント)

• 2042-2043 : スワップインするプロセス(のデータセグメント)ã‚’swap( )を呼ぶことでスワップイン。失敗したらpanic
• 2044 : スワップ領域のプロセス(のデータセグメント)を解放
• 2045-2048 : スワップインしたプロセスのパラメータを設定してloopへ戻る

xswap

xswapは引数で渡されたプロセスをスワップアウトする。実際にスワップアウト処理を行うのは内部で呼ばれているswap( )であり、xswap( )はswap( )のラッパーと言えるかもしれない。

• 4373-4374 : 第三引数のosが0ならば、osにはスワップアウトするプロセスのサイズを入れる。osはold sizeのことらしい
• 4375-4377 : スワップ領域をmallocで取得。失敗したらpanic
• 4378 : xccdec( )を呼び出して、スワップアウトするプロセスが参照しているテキストセグメントの「コアに存在するプロセスから参照されている数」をデクリメントする
• 4379 : スワップアウトするプロセスのSLOCK(スワッピング処理中を表す)フラグを立てる。sched( )(など？)で影響してくる
• 4380-4381 : swap( )を呼び出してスワップアウト処理。失敗したらエラー
• 4382-4383 : 第二引数ffが0以下でなければ、スワップアウトしたプロセスをコアから解放する。コメントによると、newproc( )時はffが0になっているようだ
• 4384-4386 : スワップアウトしたプロセスのアドレスをスワップ領域で確保したアドレスに差し替える。SLOAD, SLOCKフラグをオフにし、スワップ領域に存在している時間を表すp_timeã‚’0にする
• 4387-4390 : runout(スワップインさせられるプロセスが存在しない)フラグが立っていたら、runoutで寝ているプロセスを起こす

xalloc

xallocは共有テキストセグメントをプロセスに割り当てます。

u.u_arg[1]にバイト単位でのテキストセグメントのサイズが入っています。

text配列から空きエントリを探す。テキストセグメントが他のプロセスにより既に使われていたら、それを指すようにする

• 4439 : テキストセグメントのサイズが0ならばreturn
• 4440-4450 : text配列から、x_iptrがNULLのものを探す。既に引数で渡されたテキストセグメント(のinode)が別のプロセスによって使われていたら、そのテキストセグメントの参照カウント数をインクリメントし、カレントプロセスからそのテキストセグメントを指すようにし、out(4474)へ飛ぶ

テキストセグメントを新規に作成。スワップ領域にセットする

• 4451 : text配列に空きエントリがなければpanic
• 4452-4456 : テキストセグメントのパラメータを設定。テキストセグメントの参照カウント数を1にし、コアに存在するプロセスからの参照カウント数を0にする。テキストセグメントから引数で渡されたinodeを指すようにする。テキストセグメントのサイズを計算する
• 4457-4458 : テキストセグメントのためにスワップ領域を確保する。失敗したらpanic
• 4459-4460 : expand( ), estabur( )を使って、新たに作成したテキストセグメントを反映したメモリマッピングが行えるようにする
• 4461-4464 : テキストセグメントをアドレス0にロードする
• 4466 : カレントプロセスのSLOCKフラグを立てる
• 4467 : swap( )を呼び出して、カレントプロセスのデータセグメントをスワップアウトする。何のため？
• 4468 : SLOCKフラグを解除
• 4469 : カレントプロセスが新規に作成したテキストを指すようにする
• 4470-4472 : テキストセグメントのinode?のパラメータ設定。ITEXTフラグをたてて、参照カウントをインクリメント
• 4473 : expand( )を使って、データセグメントサイズを最小化(なんのため？)

テキストセグメントがコアにあるプロセスから参照されていなかったら

Lions本によると、データセグメントより先にテキストセグメントをスワップインする必要があるようです。そのため、ここの処理が必要だそうです。(まだあまりよく理解できていません)

• 4475 : テキストセグメントがコアにあるプロセスから参照されていなかったら
  • 4476-4477 : rsav, ssavにr5, r6を保存。なんのため？
  • 4478 : カレントプロセスをスワップアウト。コアから解放
  • 4479 : カレントプロセスのSSWAPフラグ(スワップアウトされた状態を表す？)を立てる
  • 4480 : swtch( )を呼び出して実行プロセスを切り替える
• 4483 : テキストセグメントの、コアに存在するプロセスからの参照数をインクリメントする

xfree

xfree( )はカレントプロセスの共有テキストセグメントを解放します。

• 4401 : カレントプロセスのテキストセグメントがNULLではなかったら。NULLならすぐreturn
  • 4402 : カレントプロセスのテキストセグメントがNULLを指すように
  • 4403 : xccdec( )を実行し、そのテキストセグメントのコアに存在しているプロセスからの参照カウント数をデクリメントする
  • 4404 : そのテキストセグメントの参照カウント数をデクリメントする。もし0になったら
    • 4405-4412 : テキストセグメントのinode?のスティッキービット(Lions本375P参照)が立っていなければ、そのテキストセグメントをスワップからも解放する。inodeのITEXTフラグをオフにして、iput( )を呼び出しinodeの参照カウント数をデクリメントする

Lions本によるとスティッキービット(ISVTX)フラグが立っていると、そのテキストセグメントを参照するプロセスが存在しなくなっても、スワップ領域から解放しないそうです。頻繁に参照されるようなテキストセグメントに、再作成のコストを抑えるためにセットされるのではないでしょうか。

終わりに

スワッピング処理を一通り見てきました。肝心のスワップ処理中核であるswap( )が次の章にならないと出てこないので、少しもやもや感が残っています。

テキストセグメントの生成から解放までのフローを絵にすると理解が深まるのではないかと思っています。時間があったら描きます。

細かい部分の理解や考察が追いついていない箇所があります。それらはLions本読書会#6で補おうと思っています。

次回のエントリでは15章を読み解いていきます。