![[hrb Wiki]](hrblogo1.gif "[hrb Wiki]")
|
lea/10_memoryhttp://hrb.osask.jp/wiki/?lea/10_memory |
メモリ管理(この記事は2008年8月21日に出現しました)今の実装
今日の料理とりあえずメモリは限られてるんだし、メモリ管理をもう少し真面目にやるか 失われたメモリ、どうするよ？あの有名な黄緑本の初版で言うところの189ページ(9章4節)に短く
ここでふと疑問が浮かびます。確か「最初の方法」は「今使ってる凄く速い方法」よりメモリを食うはず・・・
しかもそんな手抜きを修正しなくても、やっぱり領域のサイズは可変長。管理用の新たな構造体が入る保証はありません。
ということで、「構造体のサイズがとても小さい」と「複雑ではない」、それに「実用的な時間で動く」を struct SinglyLinkedList {
int data; // 格納しているデータ
struct SinglyLinkedList *next; // 自分と同じ構造体へのポインタ
};
struct MEMLIST {
void* addr; // 失われた空き領域へのアドレス
unsigned int size; // とそのサイズ
struct MEMLIST *next;
};
よく考えよう。少し考えてみてください。この構造体は一体どこに配置される事になるかを。 struct MEMLIST {
unsigned int size; // 失われた空き領域のサイズ
struct MEMLIST *next;
};
struct MEMMAN {
int frees, maxfrees, lostsize, losts;
struct FREEINFO free[MEMMAN_FREES];
struct MEMLIST *list; // リストの先頭へのポインタ
};
man->list=LIST_END; // 解放に失敗した領域を復元させるためのヒント(LIST_ENDはヘッダかどこかで定数として定義。)
#define LIST_END 0
/* 後ろにずらせなかった */
// 最も小さな空き領域を探す(ここから追記)
unsigned int lostaddr,lostsize;
lostsize=size;// 今開放要求が来た奴より小さい奴を探せばいい。
j=-1;
for(i=0;i<MEMMAN_FREES;i++){
if(lostsize>man->free[i].size){
lostsize=man->free[i].size;
j=i;
}
}
if(j==-1){// 要求された奴が実は一番小さい奴だった
lostaddr=addr;
man->losts++;
man->lostsize+=lostsize;
}else{
lostaddr=man->free[j].addr;
// 最も小さな空き領域を握りつぶす
for (i=j;i<MEMMAN_FREES-1;i++) {
man->free[i]=man->free[i+1];
}
man->frees--;
man->losts++;
man->lostsize+=lostsize;
// 最も小さな空き領域を潰した分、管理領域が空いたのでfree可能の筈
memman_free(man,addr,size);
}
// あとでメモリを復活できるように細工
struct MEMLIST *t;
if(man->list==LIST_END){// リストが空なら、ただ追加する
man->list=(struct MEMLIST *)lostaddr;// 誰も使わない領域の先頭部分
man->list->size=lostsize;
man->list->next=LIST_END;
}else{// 片方向リストの先頭に挿入する
t=(struct MEMLIST *)lostaddr;// 誰も使わない領域の先頭部分
t->size=lostsize;
t->next=man->list;
man->list=t;
}
void memman_GarbageCollection(struct MEMMAN *man){
if(/* 復活させるべきものがないならば */){
return;
}
// 解放した時空き領域を潰さないなら、解放していく(この関数の実行中にman->listの中身が変わるとややこしいので。)
while(-1){
if(/* メモリ管理領域に余裕があり、かつ復活させるべきものがあるならば */){
/* それを解放 */
}
if(/* もし復活させるべきものがなくなってしまったならば */) break;
// この時点でメモリ管理領域に余裕はないはず
if(/* 前後どちらかでまとめる事ができるものがあるならば */){
/* それを解放 */
}
// 前後どちらかでまとめる事ができた時、メモリ管理領域に少し余裕が生まれるかもしれない。
if(/* メモリ管理領域に余裕があり、かつ復活させるべきものがまだあるならば */){
continue;//もう一周。
}else{
break;//もう何も出来る事がない
}
}
return;
}
さて実装こんな感じかな。 void memman_GarbageCollection(struct MEMMAN *man){
struct MEMLIST *t,*k;
if((int)man->list==LIST_END){//復活させるべきものがない
return;
}
// 解放した時空き領域を潰さないなら、解放していく(この関数の実行中にman->listの中身が変わるとややこしいので。)
while(-1){
// メモリ管理領域に余裕があり、かつ復活させるべきものがあるならば順次解放
while(man->frees<MEMMAN_FREES&&(int)man->list!=LIST_END){
t=man->list;
man->list=t->next;// 解放可能な存在をリストから削除
memman_free(man,t,t->size);
}
// 復活させるべきものがなくなったらループを抜ける
if((int)man->list==LIST_END) break;
// メモリ管理領域に余裕がなくても、前後どちらかでまとめる事が出来るならそれを解放
while((int)man->list!=LIST_END){// 先頭は特別扱い
t=man->list;
if(memman_canfree(man,t,t->size)){// まとめられるような状態なら
man->list=t->next;// 解放可能な存在をリストから削除
memman_free(man,t,t->size);
}else{
break;
}
}
k=man->list;
while((int)k->next!=LIST_END){
t=k->next;
if(memman_canfree(man,t,t->size)){// まとめられるような状態なら
k->next=t->next;// 解放可能な存在をリストから削除
memman_free(man,t,t->size);
}else{
k=k->next;
}
}
// まとめる事によってメモリ管理領域に余裕が出来て、かつ復活させるべきものがまだ存在するならもう1周
if(man->frees<MEMMAN_FREES&&(int)man->list!=LIST_END){
continue;// もう一周。
}else{
break;// もう何も出来る事がない
}
}
return;
}
int memman_canfree(struct MEMMAN *man,void* addr,unsigned int size){// 既存の空間とまとめる事ができるかどうかを判定
int i;
for(i=0;i<man->frees;i++){
if(man->free[i].addr>addr){
break;
}
}
if(i>0&&man->free[i-1].addr+man->free[i-1].size==addr) return -1;// 前とまとめられる
if(i<man->frees&&addr+size==man->free[i].addr) return -1;// 後ろとまとめられる
return 0;
}
int memman_alloc(struct MEMMAN *man,unsigned int size){
unsigned int i, a;
// サイズを8byte単位に切り上げ
size=(size+(8-1))&(-8);
/* (省略) */
return 0; // あきがない
}
注意事項(懸案事項)��memman_freeする時に、何も考えずにリストの先頭に入れていったため、例えば次のような場合にうまく全部解放できないかもしれません。 簡易投票(今回のメモリ管理に関する記事について。)どの程度役に立った？ 説明は適切？ ソースコード中のコメントは？ あの「cdr関数」をよく使う、括弧地獄とも言われる某言語について何か知ってる？ コメント
|
