応用情報技術者 試験情報＆徹底解説

リストによるメモリ管理に関する次の記述を読んで，設問1～3に答えよ。

　与えられたメモリ空間(以下，ヒープ領域という)の中に，可変長のメモリブロックを動的に割り当てるためのデータ構造及びアルゴリズムを考える。
　ヒープ領域は，一つ以上の連続したメモリブロックで構成する。メモリブロックは，固定長のヘッダー部分と可変長のデータ部分で構成される。ヘッダー部分は構造体で，prev，next，status 及び size のメンバーによって構成される。メモリブロックの構造を図1に，ヘッダー部分のメンバーの意味を表1にそれぞれ示す。メモリブロックを指すポインタ変数には，メモリブロックの先頭アドレスをセットする。あるメモリブロックを指すポインタ変数を q とするとき，そのメンバー prev の参照は，q->prevと表記する。また，ヘッダー部分のバイト数は，HSIZE とする。　ヘッダー部分と同じ構造体の変数 EDGE をヒープ領域の外に定義する。そのメンバー prev 及び next には，それぞれヒープ領域の最後尾及び先頭のメモリブロックの先頭アドレスをセットする。ヒープ領域の先頭のメモリブロックのメンバー prev と最後尾のメモリブロックのメンバー next には，ともに EDGE の先頭アドレスをセットする。これによって，EDGE を含むメモリブロックが双方向の循環リストを構成する。 EDGE にはデータ部分はなく，メンバー size には 0 が設定されている。データ構造の全体像を図2に示す。〔メモリ割当ての関数〕
　メモリ割当ての関数は，割り当てたいバイト数(msize)を引数とし，そのバイト数以上の大きさのデータ部分をもつメモリブロックを，ヒープ領域から探索する。このアルゴリズムを次のように考えた。

• ポインタ変数 q を定義し，初期値として変数 EDGE の next の値をセットする。
• q がアと等しい場合は，ヒープ領域には十分な空きメモリをもったメモリブロックが無かったことを意味する。関数の戻り値に NULL をセットして終了する。それ以外の場合は，次の(3)～(5)を実行する。
• q->イが'A'の場合，又は q->size が msize 未満である場合は，q に q->ウをセットして(2)に戻る。
• q->size が HSIZE＋msize 以下の場合は，q->イに'A'をセットし，関数の戻り値に q の値をセットして終了する。
• 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 の値はカである必要がある。〔メモリコンパクション〕
　メモリの確保や解放の処理を繰り返すと，サイズの小さな空きメモリが分散してしまい，サイズの大きな空きメモリの確保が難しくなることがある。このような現象をコと呼ぶ。このとき，割当て済みのメモリブロックが連続するようにメモリブロックを移動し，移動したメモリブロックの後ろに大きな空きメモリを確保することをメモリコンパクションという(図5参照)。　ヒープ領域が図6のように左上から右下にかけて連続する構成の場合，メモリコンパクションを実行すると，サバイトの空きメモリができる。
　メモリコンパクションを実行すると，①メモリコンパクション前に実行したメモリ割当て関数の戻り値は，メモリ解放の関数の引数としては使えなくなる場合がある。

〔メモリ割当ての関数〕について，(1)，(2)に答えよ。

• 本文中のア～ウに入れる適切な字句を答えよ。
• 本文中のエ，オに入れる適切な字句を，ポインタ変数qを用いて答えよ。

〔メモリ解放の関数〕について，(1)，(2)に答えよ。

• 本文中のカに入れる適切な字句を答えよ。
• 図4中のキ～ケに入れる適切な字句を答えよ。

〔メモリコンパクション〕について，(1)～(3)に答えよ。

• 本文中のコに入れる適切な字句をカタカナで答えよ。
• 本文中のサに入れる適切な式を答えよ。
• 本文中の下線①の理由を25字以内で述べよ。