オペレーティングシステムはどのようにメモリを管理しているのか？
はじめに
オペレーティングシステムがどのようにメモリを管理しているのか学習を行ったので、備忘として記事にまとめます。
学習には以下の書籍を用いました。
松尾啓志（2018）「オペレーティングシステム【第 2 版】」森北出版株式会社
なぜメモリの管理を行うのか
コンピュータがプログラムを実行する際、そのデータは主記憶上に展開されて実行されます。
一般的なコンピュータでは主記憶上に複数のプロセスが同時に存在（マルチプログラミング）していますが、メモリ管理が機能していないと以下のような不具合が発生します。
- 自プロセス以外の領域にアクセスし、書き換えを行ってしまう。もしオペレーティングシステム領域への書き込みを行うと、瞬時に停止につながる。
- メモリ量が主記憶の大きさに制限される。メモリ管理によって、プロセスは主記憶の物理的な大きさに関係なく、必要とするメモリ量を確保できることが望ましい。
上記二点の問題を回避するために、各プロセスは主記憶の物理アドレスではなく独立した論理アドレス空間を持つことが重要となります。
論理アドレス空間から主記憶上の物理アドレス空間への変換は主記憶管理部（memory management unit : MMU）と呼ばれるハードウェアで行われます。
理想的な論理アドレスが持つべき条件としては、次の四つがあります。
- 大きさが無制限
- プロセスごとに固有の空間をつくり、他のプロセスからのアクセスから守る
- プログラム部、データ部、スタック部などが分離する
- 必要時にはプロセス間でアドレスを共有する
主記憶上の意図しない領域の書き換えを防ぐための手法として下限レジスタ機構とロック／キー機構を紹介します。
この二つは現在ではほとんど利用されていませんが、現代で使われている手法の基礎となっています。
下限レジスタ機構
- 主記憶をオペレーティングシステム領域とユーザー領域を下限レジスタの示す境界で分離する手法
ロック／キー機構
- 下限レジスタ機構が境界を一つしか持たないのに対して、ロック／キー機構は複数の境界をもつ
- この機構はプログラムが指定したアドレス領域内で、上位部と下位部に分けて考える
- 上位部（キー）は主記憶ブロックのアドレスの格納だけでなく、主記憶ブロックへのアクセス権が格納されているロックデータ（配列）の添字として用いられる
メモリ領域割り当て
プログラムの実行には、二次記憶から主記憶へのデータ転送と、その過程で必要な主記憶領域の確保が必要です。
プログラムが主記憶領域を要求するタイミングとしては次の二つがあります。
- 実行開始時にプログラムおよびデータを転送するために必要な領域を確保する（静的な領域要求）
- 実行中に必要となったメモリを確保する（動的な領域要求）
様々なプロセスが主記憶上の領域を要求してくるので、それに対応して領域を割り当てていく必要があります。
その方法として大きく分けると固定区画方式と可変区画方式がり、それぞれ以下の特徴を持ちます。
固定区画方式
- あらかじめ決められた領域をプロセスに割り当てる方式
- 割り当てのコストは小さいが、必要のない領域まで割り当ててしまうこともあり効率は悪い
可変区画方式
- プロセスが必要な領域を必要なだけ要求する方式
- 固定区画方式と比較して、領域を割り当てるためのコストが高くなる
- またプロセスが使えないような小さな領域が大量に残ってしまうメモリフラグメンテーション（メモリの断片化）という問題が発生する
- メモリフラグメンテーションを解消する方法としてメモリコンパクションと呼ばれる空き容量を詰める方法があるが、全てのプロセスを一時的に止める必要があり、実際には困難なケースが多い。
可変区画方式の中でも割り当ての方式は以下のようなものがあります。
- ベストフィット方式：割り当てたあとの残り領域が一番小さくなる領域を割り当てる。
- ファーストフィット方式：最初に見つかった要求された量が収まる領域を割り当てる
- ワーストフィット方式：ベストフィット方式の逆。割り当てたあとの残り領域が割り当てたあとの残り領域が一番大きい領域を割り当てる。
プログラムが主記憶の領域を要求した際に、空いている領域を割り当てる必要がありますが、その空き領域を管理する手法としては次の二つが主流となります。
リスト方式
- 主記憶状の空き領域の先頭アドレス、大きさ、次情報へのポインタの三つの情報を格納した構造体をもつ方式
- リストを追加する際に、アドレス順または大きさ順が考えられ、それぞれファーストフィット方式、ベストフィット方式の実現ができる
- リスト方式は検索時に上から辿っていくため情報へアクセスするコストが高くなりやすい
ビットマップ方式
- 主記憶の使用状況を配列で管理する手法
- 配列に対して添字を指定することで直接要素を参照することができるため、リスト方式と比較して高速である
- ただし空き領域の検索自体は順に行うため、コストが高くなりやすい
ページングとセグメンテーション
主記憶の管理手法として主流なものにページングとセグメンテーション、そしてその二つを組み合わせたページ化セグメンテーションがあり、それぞれ異なる特徴を持ちます。
ページング
主記憶の動的再配置を行うことで仮想記憶を実現する手法をページングと呼びます。
主記憶の動的再配置とは、現在実行中のプログラムおよび直近にアクセスしたデータ領域のみを主記憶上に配置して、それ以外の領域は二次記憶上に配置する手法です。
動的再配置を実行するには二つの動作が必要となります。
- スワップイン：プログラムが必要とする領域を、二次記憶から主記憶に転送する
- スワップアウト：スワップイン時に必要となる領域を確保するために、現在必要としない領域を二次記憶上に転送する
ページングは上述のロック／キー機構に動的再配置機能を加えた方式です。
仮想アドレスを複数のページ、物理アドレスはページフレームと呼ばれる固定長のブロック単位に分割されます。
ページは主記憶上のフレームだけでなく、二次記憶上にもマッピングされます。
ページ番号からページフレーム番号へのマッピングを行うテーブルをページテーブルと呼び、ページテーブルは V フラグ、P フラグ、C フラグというフラグを持ちます。
それぞれのフラグは以下の機能を持ちます。
- V：仮想アドレスのページが、主記憶上にあるか、二次記憶上にあるかのフラグ
- P：アクセス制御フラグ（001：読込可、010：書込可、100：実行可能）
- C：スワップイン後の書き込み有無のフラグ
ページングのメリット
- ページングはプロセスがページ単位でメモリを要求するため、結果としてメモリフラグメンテーションの問題が発生しない
- ただし最後に割り当てられたページの一部が使用されない、内部フラグメンテーションは発生する（無視して問題ないレベル）
- 主記憶にアクセスする際に、ページテーブルの P フラグを参照するため、アクセス制御が容易
- ページテーブル上のページフレーム番号を書き換えることで、仮想アドレスの変更なしにページの動的再配置が可能
ページングの問題点
- ページテーブルの大きさが無視できない
- （解決策）ページフレーム番号が二次記憶上を指す場合は、ページテーブルの部分領域を二次記憶上に配置する。さらにハッシュ関数によって高速にページ番号の変換を行う。
- メモリアクセスが増大する（ページテーブルが主記憶内に存在するため、主記憶アクセスのたびにページテーブルにアクセスする必要がある）
- （解決策）直近に行われたページ番号の変換を、CPU 内の連想レジスタに保存する。主記憶にアクセスすることと比較し、CPU へのアクセスは高速に行うことができる。
セグメンテーション
ページングでは理想的な論理アドレスが求める条件のうち、以下のものが満たせません。
- 一つのプロセスに複数の一次元アドレス空間を用意し、論理アドレス空間を、プログラム部、データ部、スタック部などに分離する機能
- 複数のプロセス間で、一部アドレス空間を共有する共有メモリ
これらを解決するためにセグメントと呼ばれる論理的に独立し、かつそれぞれの論理アドレス空間の大きさを自由に増減可能な領域割り当て手法であるセグメンテーションが考案されました。
ページングと同様に、セグメンテーションでは仮想アドレスが上位のセグメントテーブルのインデックス値と下位のオフセット部に分けられます。
そして、プログラムからは仮想アドレスをプログラム領域、データ領域、スタック領域の三つの空間として認識されます。
セグメントテーブルには、ページテーブルと同様に様々なフラグ、主記憶上の開始アドレス、そのサイズが格納されています。
これにより、プログラムは増減可能な一次元アドレスを複数確保することが可能となります。
さらに、セグメントテーブルを使用することで、他のプロセスが独立に定義したセグメントと主記憶の任意の領域を共有することも可能になります。
ただしセグメンテーション単体ではメモリフラグメンテーションの問題を解決することができません。
ページングとセグメンテーションの利点を組み合わせた手法としてページ化セグメンテーションが考案されました。
ページ化セグメンテーション
ページ化セグメンテーションは、セグメンテーションの手法で発生するメモリフラグメンテーションの問題を解決するために考案された手法であり、現在の主記憶管理手法の主流となっています。
この手法では、仮想アドレスがセグメント番号部、ページ番号部、およびオフセット部に分けられ、複数のページテーブルがセグメントテーブルで管理されます。
一つの特徴として、すべてのページテーブルを主記憶上で管理する必要がないため、ページングで問題となっていたページテーブルの大きさの問題が解決します。
また、主記憶をページ単位で管理することにより、セグメンテーションで問題となっていたメモリフラグメンテーションの問題も解決します。
Discussion