UNIX 6th code reading - malloc
はじめに
最近Lions' Commentary on UNIXを読み始めました。
読み進めるだけでは理解が浅いと感じたので、メモをこのブログに書いていこうと思います。
Lions’ Commentary on UNIX (Ascii books)
- 作者: ジョンライオンズ,John Lions,岩本信一
- 出版社/メーカー: アスキー
- 発売日: 1998/07
- メディア: 単行本
- 購入: 13人 クリック: 807回
- この商品を含むブログ (33件) を見る
対象は第五章以降の予定。途中で挫折しないことが最大の目標。
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まで
- 作者: 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を予定。