雑記

いち情報系大学生

OS学習メモ12 (MINIX本4.1-4.2章)

OS

メモリ管理の章です。
4.3（仮想記憶）は少し長いので区切りの良いところまで。

メモリ管理システムは２つに分類できる。一つはプロセスの実行中にその内容をメモリとディスク間で移動するページング方式で、もう片方の方式ではそれを行わない（後者の方が単純なのでそちらから見ていく）

 

4.1.1　スワップ,ページングを必要としない単一プログラミング

最も単純なメモリ管理方式は、プログラムとOSがメモリを共有して同時に一つのプログラムしか実行しない方式である。これには３つの方法があって、「RAMの一番下にOSを配置する」、「メモリ先頭のROMにOSをを配置する」、「メモリの先頭のROMにはデバイスドライバを入れて、システムの残り部分をRAMの下の方に配置する」のいずれかである。ユーザがコマンドを叩けば、OSは要求されたプロセスを主メモリに読んで、実行する。プロセスが完了したらOSは次のコマンド入力を待つ。次のコマンドが入力されたら、対応プログラムを前に使用したものに上書きして読み込むという流れになる。

 

4.1.2 固定パーディションによるマルチプログラミング

実は4.1.1の仕組みは今日ではほとんど使われていない。現在のほとんどのシステムでは複数のプロセスを同時実行できる。これを実現する最も簡単な方法は単純にメモリを分割するという方法で、ジョブが到着するとそのジョブが入る最も小さなパーティションの待ち行列にジョブを入れるということを行う。しかしこの方式では待ち行列の作り方によって、ジョブ中に使われない領域ができたり、大きなパーティションに小さなジョブを入れてメモリを無駄にしてしまうといった問題が発生する。これを解決する手段として、「小さなパーティションを持っておく」とか「実行待ちのジョブに実行件を与えてk回以上スキップされない規則にする」というのがある。

 

4.1.3再配置と記憶保護

マルチプログラミングの実現において解決すべきなのが再配置と記憶保護の問題。

あるプログラムをリンクする時、リンカはそのプログラムがどのアドレスから開始するかを知る必要がある。（例えば最初の命令が、リンカによって生成された、バイナリファイル内の絶対アドレス100番にあるサブルーチンコールだとすると、もしもそのプログラムがアドレス200K番地にロードされた場合200K+100番地にサブルーチンコールをする必要がある。もちろん、300K番地にロードされた場合は300K+100番地である。）これが再配置の問題である。

この解決方法の一つは、メモリにプログラムをロードした時点で命令を書き換える方法、つまりプログラムが200K番地のところにロードされたなら各アドレス部に200Kを加算するという方法である。だが、ローディング中の再配置は記憶保護の問題を解決できない。悪意のあるプログラムが常に新しい命令列を作って実行するかもしれない。このため、再配置と記憶保護の別の方法として、ベースレジスタと境界レジスタの２つの特殊なハードウェアレジスタを用いることがある。あるプロセスがスケジュールされると、ベースレジスタにはパーティションの先頭アドレス、境界レジスタにはパーティションの長さが入り、メモリアドレス生成の度に自動的にベースレジスタの内容がアクセス前に加算されるようになる。アドレスは現在のパーティション外のメモリにアクセスしないように境界レジスタによって保護されていて、これらは改竄されることもない。

 

4.2　スワッピング

スワッピングとは、プロセス全体を主記憶にロードして暫く実行させた後で、ディスクに吐き出してプロセスを停止するというのを繰り返す方法で、ここまでの固定パーティションの方式とは違ってパーティションの数や位置やサイズが動的に変化する。この分、柔軟性は高まったといえるけれども、メモリを割り当てたり開放するための管理の複雑さは増している。スワッピングを繰り返すとメモリの中に小さな空き領域が出来るので、プロセスを移動することによってそれらを一箇所にまとめることが出来る（これはメモリコンパクションと呼ばれる）。そして肝心のスワッピングだが、プロセスにどのくらいのメモリ量を割り当てるかは重要な問題である。

 

動的にメモリを割り当てる歳に、OSははそれを管理する必要がある。使用状況の管理には一般に２つの方法ービットマップによる管理とリストによる管理ーがある。

 

4.2.1　ビットマップによるメモリ管理

あらかじめ”単位”を決めてメモリを分割し（数ワードとか数KBとか）、その単位ごとに「空き」ならば0,「使用中」ならば1をつけて管理する方法。当然ながらこの”単位”を小さくすればするほどビットマップは大きくなる。この方法はメモリサイズと割り当てる単位によって決まるので、一定サイズのメモリを使って全メモリの管理を可能とする簡単な方法であるが、与えられたビットパターンをビットマップ上から探すのは一般的に処理が遅くなるという問題点がある。

 

4.2.2  リンクリストによるメモリ管理

パーティションをリスト構造にして連結して管理する方法。それぞれのリンクには「空き/使用中」「各パーティションの先頭アドレス」「各パーティションの長さ」「次のパーティションの情報」が入っている。以下はリストを管理するためのアルゴリズムである。

 

ファーストフィットは該当プロセスのメモリ容量を最初に満たす空きリストを見つけるまで探すもの。ネクストフィットはファーストフィットと同じように空きを探すが、見つかった位置を記憶しておいて、次にコールされるとそのリストの場所から求める空きリストを探す（ファーストフィットと違って最初からは探さない）。ベストフィットは、全リストを調べて空き容量が最小になるエントリを求める。ワーストフィットは、プロセスに割り当てた後で空きと成る部分で最大になるような選択法。クイックフィットは、比較的よく要求されるサイズごとに別々の空きリストを作って管理する。

 

4.3は今読んでいます。