C言語では、動的メモリ領域をどのように管理していくのか解説する。

動的メモリ領域とフリーリスト

動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借り、free()関数で使わなくなったメモリを返却する。

この借りるタイミングと返却するタイミングが、「Last In First Out」最後に確保したメモリを最初に開放してくれるのであれば、スタックを使えばいいが malloc や free のタイミングは、LIFO の順番のようにはならない。

この返却されたメモリ領域は、改めて malloc() が呼び出されたときに再利用を行う。この再利用するメモリ領域は、簡単に扱えるようにリスト構造にして保存する。この free された再利用候補のリスト構造は、free_list と呼ばれる。

mallocが一定サイズの場合

free_list の考え方を説明するために、malloc() でのメモリサイズが一定として説明を行う。

malloc() が呼び出される度に、free_list の先頭から貸し出すメモリを取り出し(a=malloc(),b=malloc(),c=malloc()まで)、free() が呼び出されると、返却されたメモリは、free_list の先頭につないでおく。

任意サイズのメモリ確保の場合

malloc() で、指定されたサイズのものが、free_list の中にあれば、それを使う。

丁度いいサイズが無い場合は、それより大きいメモリブロックの後半を切り分けて、貸し出す。

使用されていたメモリブロックが free() で返却された場合は、free_list につないでいく。ただし、単純にリストに繋ぐだけであれば、malloc(),free() を繰り返すと、小さなメモリブロックばかりになってしまい、malloc()ができなくなる。

そこで、free() で返却される際には、隣り合うメモリブロックと併合できるかを確認し、大きなメモリブロックになるような処理を行う。

ヒープメモリの断片化

ヒープメモリの malloc() , free() を繰り返すと、最悪、以下の図の様に、使用中領域(赤)とfreeされた未使用領域(黒)が交互に並ぶ状態が発生するかもしれない。この場合、全体の未使用領域の合計では十分なサイズでも、小さなメモリブロックばかりとなって、大きなメモリブロックを要求されても十分な大きさのメモリが見つからない状態が発生する場合がある。

この状態をヒープメモリの断片化といい、使用しづらい小さなメモリブロックはヒープホールと呼ばれる。

ハッシュ法について演習ができていなかったので、前半座学(ガベージコレクタ)と後半演習(ハッシュ法)

ガベージコレクタ

前回、malloc などで使用を終えたデータを free で開放する際に発生する問題について説明し、その問題の解決法として参照カウンタ法を説明した。しかし、参照カウンタ法は循環リストなどが含まれる場合、free で開放できない状態が発生する場合があることを説明した。

このため、malloc で確保したデータ領域を、free で開放する処理は、複雑なデータ構造の場合かなり処理の記述が大変になる。

そこで最近のプログラム言語では、ガベージコレクタがある。この方法では、プログラムが malloc で確保した動的データ領域は、データが不要となっても開放処理 free は行わない。

しかし、このままでは、不要となったデータ領域がメモリに溢れ、メモリ不足が発生してしまう。そこで、一定量のメモリを使い切ったら、不要なメモリ(ゴミ=ガベージ)を回収(コレクタ)する。

マーク&スイープ法

ガベージコレクタの方法には、色々あるが、マーク&スイープ法では、

1. 処理を一旦停止し、
2. 動的メモリの領域すべてに「未使用マーク」をつける。
3. 実際に使用している変数や、その変数が指している領域には「使用中マーク」をつける。
4. マーク処理が終わったら「未使用マーク」の付いているデータは誰も使っていないので回収する。

他にも、コピー法といった方法もあるが説明は割愛する。

上で述べた様に、ガベージコレクタはプログラムを一旦停止し、全動的メモリ領域を検査するという手間のかかる作業を行うため、通常は「一時的にプログラムが止まる」ことからリアルタイムに処理を行うような場合には、極めて不都合が多い。

このため、最近では参照カウンタ法の技術なども取り入れ、局所変数は参照カウンタ法の技法を中心に回収し、大域変数はガベージコレクタの技法で回収する。

CやC++言語では、ガベージコレクタは基本的には利用できず、ガベージコレクタが取り入れられた言語としては、Java が有名。Java では、ガベージコレクタが実装されているため、通常のプログラミングでは、free や delete といった処理は不要である。しかし、処理速度や突発的な一時停止を避ける場合には、適切なタイミングで変数に null を代入するといった処理を明記するなどのテクニックが重要となる。

局所変数とスタック

局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。

関数の中で関数が呼び出されると、スタックには戻り番地情報を保存し、関数に移動する。最初の処理で局所変数領域が確保され、関数を終えると局所変数は開放される。
この局所変数の確保と開放は、最後に確保された領域を最初に開放されることから、スタック上に保存される。

演習(ハッシュ法)

ハッシュ法のプログラム(オープンアドレス法もしくはチェイン法)を用いて、
(1)名前と電話番号,(2)名前と住所,(3)名前と誕生日について、名前をキーとして検索するプログラムを作成せよ。

「出席番号 % 3 + 1」の番号のテーマに取り組むこと。

レポートを作成する際には、ハッシュ関数を変更してどういった変化があるか確認せよ。
ハッシュサイズは、10〜20件程度で良い。

意志決定木

2分木の応用で最も単純な物として、意志決定木がある。

yes/no の答えを回答すると、最終的に「あなたの性格は✕✕です」と表示するようなヤツ。

struct Tree {
    char*        q_a ;
    struct Tree* yes ;
    struct Tree* no ;
} ;
               top
                  ＼
        　　  あなたは勉強が好き？
              ／yes　　　　　＼no
    ものづくりは好き？    人と話すのが好き？
     ／yes　　  ＼no      ／yes    ＼no
技術者タイプ    ◯◯◯  営業タイプ  ◯◯◯

(さらに…)

先週までで、2分探索木の説明を終えたので、今日は演習を行う。

課題テーマ(基本)

2分探索木を使ったプログラムの作成。データ構造は、以下の中から出席番号にて選ぶ。(出席番号%3)

0. 名前と生年月日(年月日は別要素が望ましい)
1. 名前と電話番号
2. 学科・学年・出席番号・名前の名簿

上記のデータ構造にて、データを入力し「保存」、その後「検索」し目的のデータを表示する機能を実装せよ。

定番ではあるが、(a)プログラム説明、(b)プログラムリスト、(c)動作検証、(d)動作考察の観点で評価を行う。

課題テーマ(オプション)

上記の基本テーマは簡単であるため、オプションテーマを以下に示す。基本テーマの代わりにオプションテーマにてレポートを提出せよ。

数値をデータとする2分木を、その構造がイメージできるようにアスキーアート的に、あるいはグラフィック的に表示するプログラムを作成せよ。

(例1)            (例2)　　{[29] 51 [(60) 75 (80)]}
　　51
　／　＼          (例3)          51
29　　　75　                     |
　　　／　＼　　　　　　　+------+-------+
    60      80            |              |
                         29              75
                                         |
                                     +---+---+
                                     |       |
                                    60       80

(さらに…)

2分木へのデータの追記

前回の授業で、2分探索木のデータに対する処理を説明したので、今回は木にデータを追加する処理。

struct Tree {
    int data ;
    struct Tree* left ;
    struct Tree* right ;
} ;
struct Tree* tcons( int x, struct Tree*L, struct Tree*R )
{
    struct Tree* ans ;
    ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
    if ( ans != NULL ) {
        ans->data  = x ;
        ans->left  = L ;
        ans->right = R ;
    }
    return ans ;
}
struct Tree* top = NULL ;
void insert( int x )
{
    struct Tree** tail = &top ; // 書換えるべき末端ポインタへのポインタ
    while( (*tail) != NULL ) {
        if ( (*tail)->data == x )
            break ; // 同じデータは重複するので、追加処理は行わない
        else if ( (*tail)->data > x )
            tail = &( (*tail)->left ) ; // 左の枝を降りていく
        else
            tail = &( (*tail)->right ) ; // 右の枝を降りていく
    }
    if ( (*tail) == NULL )
        (*tail) = tcons( x , NULL , NULL ) ;
}

単純リストの時は、2重ポインタの混ざった式の部分的に、型を意識する説明をした。今回は、”tail = &( (*tail)->left )“の赤のカッコが省略されたら、青のカッコが省略されたら、どちらが文法エラーかを「演算子の優先順位」の話を交えながら説明する。 (さらに…)