自作OSのから見たメモリ管理概論

この記事は自作OS Advent Calendar 2017の17日目の記事として書かれました

そして、第7回 自作OSもくもく会 : ATNDでお話させていただいた内容の記事版です

はじめに

自作OSでメモリ管理するってなんだろう？って考えたことをまとめてみた

なぜメモリを管理する必要があるのか

ほぼすべての人がこんなことを尋ねるまでもなく知っていることと思いますが、改めて考えてみました
そして、そのために一旦メモリ管理をやめてみます

メモリ管理しないOSを考える

以下にメモリ管理をしないOSのメモリ空間の図を示します

• メリット

  • 実行中のユーザプログラムはOSが使わないメモリを全て使える！
  • OSを作るのが楽！
    • メモリ管理用のコードは不要！

• デメリット

  • マルチタスク不可
    • 実行可能ユーザプログラムは同時に一つ！
    • 組み込み用OSなら右図のような構成は普通にありそう
  • メモリが無駄
    • 一つのプログラムで毎回メモリ全域を使い切ることは無いはず

ここで一番のデメリットはマルチタスク不可、ということです
常にひとつのプログラムしか実行出来ません
マルチタスクをすることによって、リソースを有効活用しスループットを向上させることがOSの目的の一つです
例えば、ファイルIOの待ち、ユーザの入力待ち、といった時間に別なプログラムを実行させ、スループットを上げる、という例をよく見かけますね
なので、このデメリットはとても大きいです

しかし、組み込み機器のように1個のタスクしかしない、メモリも少ない、というか、多機能なOSはいらない、ということであれば、この構成は最適です
ここでは汎用OSを考えるのでメモリ管理をしていこうと思います

メモリ管理アルゴリズム

OSではメモリ管理が必要になる場所が大きく分けて以下の4箇所あります

1. 物理メモリ管理
2. 仮想メモリ管理
3. ヒープメモリ管理 (カーネル)
4. ヒープメモリ管理 (ユーザ)

この4箇所それぞれにメモリアロケータが必要になります
以降で紹介するのはどの部分でも使える基本的なメモリ管理アルゴリズムです
それらの良し悪しを見比べていきます

メモリアロケータの性能評価

良し悪しでは少し適当すぎるので、もう少し具体的に評価基準を設定します

1. 効率性
   • 搭載されているメモリを無駄なく使用する
   • 良し: フラグメンテーションが起きない
   • 悪し: フラグメンテーションが起きる
2. 応答性
   • メモリ要求に対して即座に応答する
   • 良し: O(1) - 定数時間オーダー
   • 悪し: O(n^2) - 2乗の速さでオーダーが増える
3. 安定性
   • 良し: サイズや要求回数に寄らず一定に動く
   • 悪し: サイズや要求回数が大きいと、効率性や応答性に影響する

フラグメンテーション

効率性の部分でフラグメンテーションが起きる起きないと書きました
フラグメンテーションとは、いわゆる断片化なのですが、3種類に別れます
そして、メモリ管理アルゴリズムの特性によってどのフラグメンテーションに強いか、などが変わってきます
それらを理解しやすくするために、まずはここで各種フラグメンテーションについて説明をします

フラグメンテーションとは

一言で言ってしまうと記憶領域を有効活用できなくなることです
これは、空き領域と使用領域が断片となり分散してしまうことにより発生します
時間が経てば経つほど、段々と効率性と応答性に影響を及ぼして性能が悪くなります

ちなみにメモリだけでなく、ディスクでも発生します
これはファイルの断片化ですね
Windowsのデフラグツールなどが馴染み深いと思います

そして、フラグメンテーションを再配置して解決することをデフラグメンテーション/メモリコンパクションといいます

以下のフラグメンテーションとデフラグメンテーションの具体例を示します

上のブロックでは全体で1024KBの空き領域がありますが、分断されているので、連続したメモリは最大512KBしか得られません
これでは1024KBの容量を持つ配列が欲しい！という要求には答えられません
これが効率がよくない、ということになります

下の図のように、空き領域をまとめてやることができれば、最大1024KBまでの要求に答える事ができます
(実際にメモリをどうやってデフラグメンテーションするか、調べられていないです)

3つのフラグメンテーション

フラグメンテーションには3種類あります

1. 内部フラグメンテーション

• 空き領域が分散すること
• 確保した領域の中で使用されないメモリが発生する
  • メモリをブロック単位で管理するときに発生する
  • 例えば、512KB単位でしかメモリの確保と解放が出来ないアロケータなど
• 単純な解決は難しく、アルゴリズムの改善と見直しが必要になる

1. 外部フラグメンテーション

• 空き領域が分散すること
• 上記の図を参照
• 管理下の空きメモリ全体では空いているのに、メモリ要求に答えられないことを言う

1. データフラグメンテーション

• 使用領域が分散
• データがメモリ上で分散してしまい、局所性が下がるため性能に影響が出る
• ファイルの断片化はこれ

これらのフラグメンテーションをどうやって抑えていくか、もメモリアロケータの目標の一つです

メモリ管理アルゴリズム紹介

やっと本題です
以下のとおりに分類をしてみました
殆どはブロック方式に分類されると思います

1. 管理しない
2. WaterMark方式
3. ブロック方式
   • 固定長ブロックと可変長ブロック
   • メモリ領域表現
   • 探索方式

管理しない

冒頭で触れた管理方式です
単純ですのでさらっと書くだけにします

• メリット
  • 実装が楽
• デメリット
  • 内部フラグメントが非常に激しい (メモリ領域が大体余る)
  • マルチタスクができない
• 使い所
  • シングルタスクで十分なとき

WaterMark方式

WaterMarkとは水位計のことです

以下が具体例です。

この方式は変数二つ(topとbottom)で実装することができるのでとても簡単です
topのことをWaterMarkといい、現在までに使用したメモリアドレスを指します
bottomは使用可能なメモリ領域の終端アドレスを指します

この方式ではメモリ要求に対し、topから要求されたサイズ分のメモリをbottom方向へ確保して返します
例では、512KBのメモリ領域を返しています

• メリット
  • 実装が楽
    • 必要な変数は2つ
    • top, bottom
  • 内部フラグメントが起きない
    • 要求サイズにピッタリのメモリ領域を必ず返すので
• デメリット
  • メモリ解放を考えていない
  • なので、外部フラグメンテーションが多発
  • しかも検知用の機構を作ろうとすると少し面倒
  • もしくは、メモリが解放されたときにデフラグメンテーションを行うことも考えられる
  • しかし、再配置コストは高いし、実行が難しそうなので現実的ではない
• 使いどころ
  • OS起動時のメモリアロケータ初期化用アロケータなど
  • 一度確保したら絶対に解放されない、という用途では直ぐに実装出来て最適

ブロック方式

殆どのメモリ管理アルゴリズムはこの方式に分類されるはずです

そして、ブロックの作り方で以下の三種類に分類されます

1. 固定長ブロック
2. 可変長ブロック
3. 半固定長ブロック

また、それらのブロックをどのようにして保存するかでも色々と種類があります

• 配列
• 連結リスト
• ツリー
• 優先度付きキュー
• タグ埋め込み

固定長ブロック

• メリット
  • なんと言っても、単純さ
  • サイズ固定なので、要求サイズ分を切り出すなどの計算が不要
  • サイズ管理しないので、その分の管理用メモリを節約できる
• デメリット
  • 内部フラグメンテーションが多発、そして、これは解決が簡単ではない
  • メモリアロケータの多段化が解決作の一つ
  • 要求サイズがバラバラだと外部フラグメンテーションも発生しやすい
• 使いどころ
  • 任意の一つの構造体の動的メモリ確保しか行わないアロケータ
  • 例えば、弾幕ゲーで、弾を一つの構造体としたら、これが便利かも？
    • これなら内部フラグメンテーションは発生しないし、外部フラグメンテーションも起きない

可変長ブロック

• メリット
  • 固定長方式に比べると内部フラグメンテーションが抑えめ
    • 要求サイズに合わせて最適に合わせられるから
  • なので、汎用性も固定長より高い
• デメリット
  • 外部フラグメンテーション発生率が上がる
    • どのようにメモリが確保/解放されるかわからないから
  • 最適なブロックを見つけるための探索が必要になる
  • 応答性能に影響が出る
    • 例: 3000個の使用済みブロックの後に目的のブロックがあったら？
• 使いどころ
  • どんなサイズで要求が来るかわからない場合 (通常はこちらのほうが多い)
  • プロセスの確保が良い例、実行されるユーザプログラムのサイズをOSは知らない

半固定長ブロック方式

これは勝手にそう呼んでいるだけです
もっと広く知られた名前があれば教えていただけると幸いです

• メリット
  • 効率性と応答性のいいとこ取りができる
  • 要求に最も近いサイズを選ぶことで、内部フラグメントを抑制
  • 同じサイズをまとめることで、探索コストを削減
• デメリット
  • 前者2つと比べると実装が難しい
  • そのため、アルゴリズムも複雑化する
  • 管理のために使用するメモリも当然増える
• 使いどころ
  • より汎用的にしたいとき

このアルゴリズムの具体例としては有名なBuddySystemやSlab Allocatorが挙げられると思います

ブロックの集合表現

メモリをブロックとして分割したあとに、それらの集まりをどうやって管理するか、についても簡単にまとめてみます

• 配列

  • メリット
    • 簡単
    • 大抵の言語に配列は組み込まれている
  • デメリット
    • 探索コスト
    • リストに比べると挿入が高コストなど、取り回しづらさがある
    • 例えば、半固定長のとき、余ったメモリを別サイズの集合に入れたいとき不便

• 連結リスト

  • メリット
    • 取り回しやすい
    • 連結すれば動的に無限に増やせる
  • デメリット
    • 実装コスト
    • 探索コスト(データフラグメントが起きると配列より悪い場合も)

• ツリー

  • メリット
    • 取り回しやすい
    • 上2つより探索しやすい
  • デメリット
    • 実装コスト
    • アドレス基準かサイズ基準かで性能の差が出る

• 優先度付きキュー

  • メリット
    • ツリーとほとんど同じ？
    • でも実装はツリーよりしやすい
  • デメリット
    • ツリーより取り回しづらい
    • キューの実装方式で性能差が出る(配列を使うか、リストを使うか)

• タグ埋め込み

  • メモリ領域内にサイズや次のブロックのアドレスを埋め込んでしまう
  • boundary tag algorithmと言われる
  • メリット
    • ブロックのマージが容易、データ構造のサイズが減る
  • デメリット
    • 使用される領域のすぐ横に管理情報があるので、破壊されないか心配

ブロックの探索

データ構造に詰め込んだとあれば、探索も必要になりますね
特にメモリアロケータの汎用性を高めた場合(どんなサイズ要求にも答えてほしい場合)効率性のために探索は不可欠です

以降では配列か連結リストを使って空き領域を探索する、ということを想定しています

• First-fit方式
  • 要求を満たすブロックを順に探索していき、1番はじめに見つかったブロックを使用する
  • メリット: 最も簡単、余分な探索がないので高速
  • デメリット: 内部フラグメンテーションが多い、外部フラグメンテーションも起きるが大きな空き領域が生まれやすいので最悪というほどでもない
• Next-fit方式
  • 前回探索した場所を覚えておくようにしたFirst-fit方式
  • メリット: うまくいけばFirst-fitより高速 (固定長のときは明らかにFirst-fitより速い)
  • デメリット: First-fitと同じ、参考文献によればFirst-fitより若干性能が悪いらしい(要調査)
• Best-fit方式
  • 最も適したサイズのブロックを使用する
  • メリット: 内部フラグメンテーションを抑える、外部フラグメンテーションは変わらないはず
  • デメリット: 必ず全域を探索しないといけないのでコストがかかる、意外にもfirst-fit/next-fitよりも、外部フラグメンテーションが起きやすく、メモリの無駄が多いらしい(要調査)
• Worst-fit方式
  • 名前の通り、最も大きな空きブロックから割り当てていく
  • メリット: メモリ解放時に大きな空き領域ができやすい
  • デメリット: 内部フラグメントがすごいことになる
• Quick-fit方式
  • 半固定長ブロック方式
  • モダンオペレーティング・システムではブロック探索の最後で紹介されている
  • 個人的にはなんか違うのでは、という感じ
  • メリット: 高速
  • デメリット: 実装コスト、ブロック結合コスト

まとめ

浅いことをさらーっと書いた、という記事でした
以下がまとめです

• メモリ管理しないとマルチタスクできない
• 管理する対象のメモリ
  • 物理メモリ管理
  • 仮想メモリ管理
  • ヒープメモリ管理 (カーネル)
  • ヒープメモリ管理 (ユーザ)
• メモリアロケータの性能評価
  • 効率性、応答性、安定性
• フラグメンテーション
  • 内部フラグメンテーション、外部フラグメンテーション、データフラグメンテーション
• Watermark方式
• ブロック方式による実装にも様々な種類が！
  • 固定長、可変長、半固定長
  • 配列、連結リスト、ツリー、キュー
  • First-fit, Next-fit, Best-fit, Worst-fit, Quick-fit

目的に応じて適切なアルゴリズムを選ぶことが大切！
ということでこの記事のまとめとさせていただきます

参考文献

モダンオペレーティングシステム 第2版, アンドリュー・S・タネンバウム
OSDev.org wiki
http://wiki.osdev.org/Brendan%27s_Memory_Management_Guide
http://wiki.osdev.org/Memory_Allocation
Wikipedia
https://en.wikipedia.org/wiki/Fragmentation_(computing)
https://ja.wikipedia.org/wiki/%E5%8F%82%E7%85%A7%E3%81%AE%E5%B1%80%E6%89%80%E6%80%A7
その他
https://courses.cs.vt.edu/csonline/OS/Lessons/MemoryAllocation/index.html
http://www.tera.ics.keio.ac.jp/person/tera/os/2004/OS-07-20041116.pdf