UNIX 6th code reading - malloc

はじめに

最近Lions' Commentary on UNIXを読み始めました。
読み進めるだけでは理解が浅いと感じたので、メモをこのブログに書いていこうと思います。

Lions’ Commentary on UNIX (Ascii books)

Lions’ Commentary on UNIX (Ascii books)

対象は第五章以降の予定。途中で挫折しないことが最大の目標。

malloc

メモリリソースの種類
coremap
メインメモリ。32word(64byte)単位で読み書き
swapmap
ディスクスワップ領域。256word(512byte)単位で読み書き

malloc, mfreeにはどちらかが渡される。ルーチン自体は扱っているリソースがどちらかを把握する必要がない。

メモリ割り当てロジック

first fitを採用している。イメージはこんな感じ。

OSの基礎と応用P96-97によると、first fitはnext fit, best fitなどよりも高速でメモリ使用効率も良いっぽい。この時代のメモリ領域は大して大きくないはずなので、first fitのシンプルなアルゴリズムが最も適しているんだろう。

OSの基礎と応用―設計から実装、DOSから分散OS Amoebaまで

OSの基礎と応用―設計から実装、DOSから分散OS Amoebaまで

  • 作者: A.S.タネンバウム,Andrew S. Tanenbaum,引地信之,引地美恵子
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2000/04
  • メディア: 単行本
  • 購入: 4人 クリック: 151回
  • この商品を含むブログ (13件) を見る

上の画像はイメージで、実際のロジックは下の画像に近い。空いている領域(map structure)が配列になっている。

最後尾にはsize 0の領域があり、探索はwhileでsize 0が来るまでループすることで実現されている(所謂「番兵」「見張り」)。配列要素数をforで回すよりも、配列要素数(ひいてはメモリの大きさ)に対して柔軟性がある、と思う。

要求サイズが空き領域と同じだった場合は、その領域は取り除かれ、後ろの領域が一つずつ前方にシフトされる。

returnされる値は、確保した領域の相対アドレス。確保できなかった場合は0が返される。

map
struct map {
  char *m_size ; /* サイズ */
  char *m_addr ; /* 相対アドレス */
} ;

coremap, swapmapはそれぞれint配列として定義されている。しかしルーチン内ではmap structureの配列として扱われている。coremap, swapmapの要素数はCMAPSIZ, SMAPSIZとして定義されているが、実際の要素数はCMAPSIZ/2, SMAPSIZ2となる。
(偶数版目の要素がm_size, 奇数版目の要素がm_addrに対応する? int(32bit??)がchar(8bit??)として扱われる際、内部ではどう処理している?)

その他の疑問

  • 分断された小さい空き領域が増えてきたらどうするんだろう。どこかでガベージコレクションするのか?
  • メインメモリ、ディスクスワップ領域はそれぞれどれくらいの大きさなんだろう?

次回

次回はmfreeを予定。