応用情報技術者 2013年 秋期 午後 問02

　 　与えられたメモリ空間（以下、ヒープ領域という）の中に、可変長のメモリブロックを動的に割り当てるためのデータ構造及びアルゴリズムを考える。 　ヒープ領域は、一つ以上の連続したメモリブロックで構成する。メモリブロックは、固定長のヘッダ部分と可変長のデータ部分で構成される。ヘッダ部分は構造体で、prev, next, status及びsizeのメンバによって構成される。メモリブロックの構造を図1に、ヘッダ部分のメンバの意味を表1にそれぞれ示す。メモリブロックを指すポインタ変数には、メモリブロックの先頭アドレスをセットする。あるメモリブロックを指すポインタ変数をqとするとき、そのメンバprevの参照は、q->prevと表記する。また、ヘッダ部分のバイト数は、HSIZEとする。

　ヘッダ部分と同じ構造体の変数EDGEをヒープ領域の外に定義する。そのメンバprev及びnextには、それぞれヒープ領域の最後尾及び先頭のメモリブロックの先頭アドレスをセットする。ヒープ領域の先頭のメモリブロックのメンバprevと最後尾のメモリブロックのメンバnextには、ともにEDGEの先頭アドレスをセットする。これによって、EDGEを含むメモリブロックが双方向の循環リストを構成する。EDGEにはデータ部分はなく、メンバsizeには0が設定されている。データ構造の全体像を図2に示す。

〔メモリ割当ての関数〕 　メモリ割当ての関数は、割り当てたいバイト数（msize）を引数とし、そのバイト数以上の大きさのデータ部分をもつメモリブロックを、ヒープ領域から探索する。このアルゴリズムを次のように考えた。 　(1) ポインタ変数qを定義し、初期値として変数EDGEのnextの値をセットする。 　(2) qがアと等しい場合は、ヒープ領域には十分な空きメモリをもったメモリブロックが無かったことを意味する。関数の戻り値にNULLをセットして終了する。それ以外の場合は、次の(3)～(5)を実行する。 　(3) q->イが'A'の場合、又はq->sizeがmsize未満である場合は、qにq->ウをセットして(2)に戻る。 　(4) q->sizeがHSIZE+msize以下の場合は、q->イに'A'をセットし、関数の戻り値にqの値をセットして終了する。 　(5) q->sizeがHSIZE+msizeよりも大きい場合は、そのメモリブロックを割当て済みのメモリブロックと、残りの空きメモリブロックの二つに分割する（図3参照）。ポインタ変数rを定義し、初期値としてq+HSIZE+msizeをセットする。q->イに'A'をセットし、r->イに'F'をセットする。r->sizeにq->size-HSIZE-msizeをセットし、q->sizeにmsizeをセットする。r->prevにはエを、r->nextにはオを、q->next->prevにはrを、q->nextにはrを順にセットする。関数の戻り値にqの値をセットして終了する。

〔メモリ解放の関数〕 　メモリ解放の関数freememは、解放したいメモリブロックの先頭アドレスを引数とし、そのメモリブロックを空きメモリブロックの状態に変更する。このとき、できるだけ大きな連続した空きメモリが後で確保できるよう、その前後のメモリブロックも空きメモリブロックかどうかを確認する。空きメモリブロックが連続する場合には、それらをまとめて一つの空きメモリブロックにする。 　関数freememのプログラムを図4に示す。この関数を正しく動作させるためには、変数EDGEのメンバstatusの値はカである必要がある。 　 ↩設問2(2)

〔メモリコンパクション〕 　メモリの確保や解放の処理を繰り返すと、サイズの小さな空きメモリが分散してしまい、サイズの大きな空きメモリの確保が難しくなることがある。このような現象をコと呼ぶ。このとき、割当て済みのメモリブロックが連続するようにメモリブロックを移動し、移動したメモリブロックの後ろに大きな空きメモリを確保することをメモリコンパクションという（図5参照）。

　ヒープ領域が図6のように左上から右下にかけて連続する構成の場合、メモリコンパクションを実行すると、サバイトの空きメモリができる。 　メモリコンパクションを実行すると、①メモリコンパクション前に実行したメモリ割当て関数の戻り値は、メモリ解放の関数の引数としては使えなくなる場合がある。