仮想メモリでない環境でのmalloc freeのよいアルゴリズムを教えてください

ゲーム機の開発をしています。
仮想メモリがないので、mallocとfreeを不定の順序で繰り返しているとヒープ領域が断片化し、そのうちにメモリは不足していないはずなのにmallocできなくなります。ゲーム機のSDKにはそういうことを想定しているのか malloc、free の代替関数を設定できるようになっています。そこで、代替関数を用意しようと考えていると考えています。

完全に断片化をさけるには、mallocした逆順にfreeするとか使い方の工夫をしないと無理とは思いますが、通信系のライブラリにの内部などでmallocしていたりして完全にはこちらの思うとおりにはできません。テクスチャーなどの常駐でなるべく多くのメモリを使いたいので、ヒープ領域はできるだけ小さくすませたいのです。どんなアルゴリズムでも、ある程度の断片化はさけられないと思いますが、malloc、freeのよいアルゴリズムが紹介されているところがありましたら、御教えください。使われ方との相性があると思いますので、複数のアルゴリズムが紹介されていればうれしいです。

No.2 ベストアンサー 回答者： PROMETHEUS 回答日時： 2006/08/08 11:27

> 代替関数を用意しようと考えていると考えています。

　そうですね。メモリ管理は完全に乗っ取ってしまった方がいいでしょう。

> 完全に断片化をさけるには、mallocした逆順にfreeするとか使い方の工夫をしないと無理とは思います
　仰るとおり使う側で工夫するのが一番効率がいいです。
　例えば、使用用途毎にメモリブロックを分けてしまうというと管理は楽になるのではないでしょうか。
　その通信のライブラリが malloc/freeを直接呼んでしまうというのであれば、ゲーム起動時にそのライブラリが使用するだろうメモリサイズを除いてごっそり確保してしまい、ユーザは自前のルーチンからメモリを取得するようにすれば、通信ライブラリによる断片化は避けれられます。


> malloc、freeのよいアルゴリズムが紹介されているところがありましたら、御教えください
http://www.ylw.mmtr.or.jp/~trustno1/legos/legos_ …
　このページで簡単な説明をしているのを見つけました。

　ただ個人的にはメモリ管理のアルゴリズムは、アロケート数が多くなると空きブロックの検索にそれだけ時間がかかるようになるのでシンプルなのが一番いいような気がします。

この回答への補足

URL読ませていただきました。
質問をする前にいくつか自作してテストしていたのですが、普通に思いついたのはこのベストフィットと同じ方法でした。それが、ファーストフィットの方がよいとは驚きでした。やっぱり、質問してみるもんですね。たすかりました。自分なりに、ここにあるアルゴリズムでシミュレーション、テストしてみます。

補足日時：2006/08/08 14:08

この回答へのお礼

お礼ですが、シミュレーションの結果をレポートしておきます。
URLの記述とは違い、ベストフィットの方がよいという結論でした。
同一の seed値を使い、ランダムに確保、開放を繰り返して、確保に失敗するまでのループの回数を数えたのですが、ベストフィットの方が確保の失敗までのループ回数が多かったです。

お礼日時：2006/08/08 15:37

No.4 回答者： chirubou 回答日時： 2006/08/09 00:43

malloc/free のアルゴリズムは、もし、サイズに特長があって、それが事前に分かっているのなら可能ですが、これをやるには結構手間がかかります。

私だったら、小さいサイズの malloc はいくつかまとめて malloc し、free_list でつないで自分で管理するような my_malloc を作ります。

my_malloc では free_list が空の場合は新たに複数の領域をまとめて malloc し、それぞれを free_list に登録後、最初のひとつを返し、空でない場合は free_list からひとつ取り出します。my_free では領域を free_list につなぎます。

これはサイズが固定の場合ですが、可変の場合は、例えば、大、中、小、それぞれの free_list を持つ、というやり方も考えられます。特大（もしあれば）は malloc をそのまま呼んでしまえばいいでしょう。この場合 my_free に長さ指定を省略したい場合は、malloc 同様、my_malloc が返すアドレスの前に長さを入れておく等の小技が必要になり少し面倒になります。

この方が普通に malloc を呼ぶより速いし、小さい領域の malloc がなくなるので断片化を押さえることができます。

この回答への補足

今回の私の状況が説明不足でしたので説明いたします。

まず、いままで私はゲーム機でのプログラミングの場合は標準のmallocはいっさい使っておりません。経験的にMMUが搭載されていないマシンでのmallocはそのうちメモリの断片化のためにひどいことになることがわかっているからです。そのため、起動直後にmallocではなくheapからメモリを確保する関数でスタックに必要な分を残して全メモリを確保しています。この領域の先頭をheap_topに入れておいて、メモリを確保する場合はheap_topを返し、heap_top += size します。free する場合は、heap_topを元に戻すだけという方法です。非常に単純なので、問題はめったに起きません。ただし、こういうやりかたをしている場合は基本的に標準のmallocとの併用は不可能です。ところが、通信ライブラリがmallocを使うのでmallocが必要になりました。救いはmallocが置き換え可能であるということです。そのため、他のテクスチャー領域などと同じようにmalloc領域を確保し、自前のmallocでそれを使うことにしました。したがって、mallocを使うのは私ではなく通信ライブラリのみなのでどんな確保のされ方をするのか事前にはわかりません。ただ、自分のmallocに使用状況をダンプするデバッグ用関数を用意して、だいたいのことは分かるかもしれません。
free_listをサイズごとにわけるというのはいいアイデアですね。free_listのサーチの時間が減りますね。

補足日時：2006/08/09 11:47

No.3 回答者： rinkun 回答日時： 2006/08/08 11:42

断片化しないmallocは不可能ではないですよ。

メモリ利用効率は悪いですけど。

基本は固定長メモリブロックを使うことです。たとえば一回のmallocで要求する最大サイズが4KBだとしたら、メモリを4KB単位のブロックで扱い何バイトの要求でも必ず4KBのブロックを返すようにします。これならmalloc順序による断片化はしません。無駄は多いですけど。
まあこれではあんまりなので、固定長メモリブロックをサイズごとに幾つか用意します。8バイト、32バイト、128バイト、1KB、4KBとか。各サイズのブロックをいくつ用意するかはシステムでの使用状況に合せて設定します。
そしてmallocでは要求サイズ以上のサイズの空きブロックを探して返します。上記例では4バイト要求されても8バイト要求されても8バイトのブロックを返し、10バイトの要求があれば32バイトのブロックを返します。
# 例では2冪サイズで書きましたが、特定サイズの要求が多いことが分かっていればそのサイズの固定長メモリブロックを用意する方が効率的です

この回答への補足

断片化はしませんが、サイズが一致しない分は結局むだになってしまいますよね。今回の一番重要な課題はメモリの使用効率のアップなので、今回は目的に合わないようです。しかし、同じような大きさの小さな領域を大量に確保するような用途では、このアルゴリズムはサーチする必要が無いので非常に強力ですね。

補足日時：2006/08/08 14:23

No.1 回答者： Qwerty-36 回答日時： 2006/08/08 10:22

ともかく、組み込み系の人間なので、mallocは大嫌い(^^;)です。

>ゲーム機のSDKにはそういうことを想定しているのか malloc、free の代替関数を設定できるようになっています。
　　↓
ゲーム機(embedded)の場合、メモリマップは固定ですから、あまりmalloc、freeのお世話にならない様にします。どうしても必要な場合は、そのボードのメモリマップに合わせて自分の責任でmalloc、freeを実装します。

ということで、mallocを使わない様にアルゴリズムを見直すことが肝要かと思います。どうしても使わなければいけないのであれば、一定の時間ごとにgarbage collectionを行うのが良いかと思います。
通信ライブラリの中で、最大、どの程度のバッファ領域をmallocし消費するか、見積もって、そこをメモリマップの一番端に持ってくる様にしてください。(最悪は、その通信ライブラリの使用を見直さないといけないですね。)

この回答への補足

私もmallocは大嫌いです。仮想記憶の無いシステムでmallocがまともに動くとはとても思えません。ですから、いままではゲームの開始直後にスタックに必要な分を除いて全ヒープメモリを確保してこちらの管理下でメモリを使うようにしていました。ところが、通信ライブラリが malloc を使うために今回どうしてもmallocを使わなくてはいけなくなりました。ライブラリは認証などが含まれているので、使わないわけには行きません。救いは、mallocが置き換え可能なので、最適なアルゴリズムとheap領域とサイズが指定できることです。それでこの質問をしております。
なお、ガベージコレクションは無理と思います。ライブラリに確保したポインタが変化したことを伝えることができないからです。これも仮想記憶が無いことによる問題ですね。

補足日時：2006/08/08 12:44