Path: sranha!katsu From: katsu@sra.co.jp (WATANABE Katsuhiro) Message-ID: Date: 3 Jun 91 18:43:32 Organization: Software Research Associates, Inc.,Japan In-reply-to: hasei@sra.co.jp's message of 27 May 91 14:16:55 GMT Newsgroups: sra.os.unix Followup-To: sra.os.unix Subject: Re: BSD malloc(3) and Swap Space Distribution: sra References: malloc() の実装に関しての話です。 記事 で hasei@sra.co.jp (Tomoyuki Hasei) さんいはく > ふつうは、malloc に 5 MB 要求すると、malloc は、8MB のフリーリス > トを見て、空ならば、system に memory を要求する。アロケートできな > ければ、それでおしまい、NULL pointer を返す。 > と、なるんですが、アロケートできなかったら、5 MB ではなく、16MB > 要求されたと思って、それに見合うフリーリストから探す、という…… > ソースを少し見た限りでは、比較的簡単にできそうですよ。 　長谷井さんが考えているのは、 （Ａ）16MB の領域をそのまま 8MB の領域のために使う。（後ろ半分無駄） （Ｂ）16MB を半分にして、片方は使い、もう片方はフリーリストにつなぐ のどちらでしょう？Ｂの方を考えているのだと思うのですが、……… > ようするに、そこまで考慮していないのか、起こりそうにないケースと > して、無視したか、ということかも知れません。 　実は 4.3BSD の malloc() では、記憶域を単純な２の冪乗の大きさ単位で 管理していないので、Ｂを効率良く実装することはできません。 　malloc によって得られた各々の領域の直前には、管理のための領域が 数バイト付随しています。よって malloc の中での記憶域の管理単位を ２の冪乗単位にしてしまうと、例えば malloc(2^23) を呼び出した時には malloc 内部で 2^24 バイトの領域が確保されてしまいます。 （「2^23 + 数バイト」が収まるための最小の２の冪乗は 2^24 だから） 　berkeley の人たちは、malloc の引数が２の冪乗になる確率は高いと 考えたのでしょう。BSD の malloc の内部では、大きい領域の確保は 「２の冪乗＋ページサイズ」で行なわれます。これなら malloc(2^23) も 「2^23 + ページサイズ」の領域だけしかとられません。 　しかし一方、上で書いたＢのように、8M の記憶域が欲しいけど 16M の記憶域しか余ってないような場合に、16M(2^24 + ページサイズ) の 領域を 8M の領域(2^23 + ページサイズ) ２つに分割するようなことは （ページひとつぶんのために）できなくなってしまっているというわけです。 > bsd43, gnu, perl のいずれの > malloc.c もほぼ同じアルゴリズムを使ってるようなんですが、微妙に > implement （後処理、前処理？）が違っていて、 　gnu や perl の malloc() の場合は、空き領域が２の冪乗そのままなので 簡単に半分に割ることができます。よってＡはもちろん、Ｂのような実装は 簡単だと思います。 -- ----____----____ 渡邊克宏＠ソフトウェア工学研究所