先週の説明のガベージコレクタの補足説明として、 実装方法の他の方法としてコピー法などを紹介。

この後、リスト構造の応用の最後の説明として、mallocとfreeの実装方法を 説明する。ただし、順序良く理解をしてもらうために、 確保する領域サイズが固定の場合を説明する。

mallocで確保する領域サイズが一定であれば、 最後にfreeされたものを最初にmalloc用に使う…と考えれば、 freeされた領域を、リスト構造のスタックとすればいい。

struct HeapList {
struct HeapList* next ;
// データ領域
} ;
struct HeapList* freelist ;
void* my_malloc() {
struct HeapList* ans = freelist ;
freelist = freelist->next ;
return (void*)ans ;
}
void my_free( void* p ) {
struct HeapList* hp = (struct HeapList*)p ;
hp->next = freelist ;
freelist = hp ;
}

ただし、freelist は決められた領域のブロックをリストで連結しその先頭で初期化する。

ヒープ領域の断片化

実際のmalloc() , free() は、確保領域が自由な大きさを指定できる。 しかしながら、使用領域と開放領域が交互に並んだ状態で、 最初の使用領域よりも小さな領域の要求があると、 小さなメモリブロックが細切れで発生する。 この細切れで有効活用のできないメモリをヒープホールと呼ぶ。 また、このように細切れになることを断片化(フラグメンテーション) と言う。

関連する用語では、ハードディスクの断片化(フラグメンテーション)がある。 これは、ハードディスク内で散らばった小さなファイルが削除され、 この後に巨大なファイルが新規作成されると、1つのファイルが 分散して配置される。このような状態を断片化と呼び、 このファイルを読み出す場合、分散して配置されているため、 次の場所への移動で、シーク時間・回転待ち時間が余計に発生する。 これによりファイルの読み書き速度が遅くなる。 Windowsでは、これらの不連続状態の改善のために、 デフラグ機能がある。デフラグでは、ファイルの配置を入れ替え、 ファイルが連続して配置されるようにしてくれる。

福井県機械工業会との連携事業でエコ関連技術ネタで、 勉強会などに協力しているけど、昨日テレビで面白そうな番組をやっていた。 「夢への扉～NEXT DOOR～：ゼロエネルギービルを可能にする太陽光照明を広めて行きたい」(2010/12/19放送)にて、光ダクトという技術が紹介されていた。

一般住宅で太陽光の取り入れ窓というのは、最近では積極的に取り組まれているが、 光ダクトとは、オフィスビルで太陽光をうまく使うためのシステムで、 採光窓から、太陽光をダクトを使って反射させながら建物の中に取り入れ、 照明に使うための物。

建物の構造上、L字型に曲がった環境でも光をうまく 取り入れられるように、反射光シミュレータを使って施工するらしい。 特に、L字型でも光をうまく反射させるには、単純に角に平面鏡を設置しても、 太陽の入射角度の変化で、明るくはできないらしい。 このため、L字部分では、カーブを付けた鏡の方が重要だったりするとの内容であった。

ただし雲などの自然変化で光量の変化が無いように、光ダクトには光感応による 補助ライトも設置する。光の量は、500ルクス程度らしい。 んで、最近はビルだけでなく身近な場所での導入のためにコンビニに設置するのを 目標に開発されている新しい光ダクトの紹介をしていた。 コンビニでは、職場などより明るい光が必要で1000ルクス程度が要求されている。 1000ルクスは厳しいけど、一般的に10時から16時程度の時間帯で800ルクスを超える ことを目標に開発しているが、単純に光の量を増やせばいいという訳ではない。 夏場では光を取り入れすぎると、エアコンの冷房が必要になってきて、エコではなくなる。 この会社での取り組みでは、採光窓に徐々に角度を変えた反射板をつけておき、 高い角度での光はさえぎられて、朝夕の入射角の光をたくさん取り込むように工夫を していた。これにより、真昼でも室温上昇がすくなくかつ800ルクスを実現との内容であった。

• 光熱費がかからない自然光システム by Material House
• 光ダクトの特性

プログラミング応用の第4クオータとして、グラフィックスのネタで演習を行う。 GrWinを使って、基本的な命令で簡単な絵を描く処理を示した後、 関数グラフを描く処理を説明し、簡単な応用で穴埋めをしてもらう。

基礎的なネタだけど、実数を使うプログラミングでありがちなミスの説明もおこなう。

(( 実数を積算しても完全に正確な値とはかぎらない...))
#define PI 3.141592
float th ;
for( th = 0.0 ; th != 360.0/180.0*PI ; th += 5.0/180*PI ) {
:    // ループが止まらない...
}
(( 整数演算と実数が混ざると危険 ))
for( th = 0.0 ; th <= 360.0/180.0*PI ; th += 5/180 * PI ) {
:   // thの値が変化せず無限ループ
// 5/180 は int 型で計算され、0となる。
}

マウスやタッチパネル操作の分析に関係したテーマで 特別研究をしている学生さんの、修了認定試験の仮想問題のネタで、 雑談。 こんな問題出るかもよ…ということで、 「操作対象が小さくなると、作業時間にどう影響でるか？」という質問をしてみた。

こんな話をするのは、高専就職前の職場ではIE課という所で、 作業効率化のためのコンピュータ導入ネタをやっていた。 ただ、本来の生産管理(IE:Industrial Engineering)では、 行程作業者の作業のムダの分析も重要な仕事。 んで、その課の勉強会では、作業因子法(Work Factor plan)という分析手法を 習っていた。 んで今回のタッチパネル操作の研究テーマだと、 ターゲットまでの距離や大きさや注意の必要性を考えれば、 Work Factor法でパネル操作に要する標準時間が求められるはず…。 というアドバイスをしてあげたかったんだけど、 IE仕事をしてたのは、ほぼ20年前の話。 Work Factor法という単語にたどり着くのに、ずいぶんとググらなければいけなかった。

データ構造に関係するアルゴリズム説明が一通り終わったので、 ここからは動的メモリの管理方法の解説。 まずは最初に、参照カウンタ法とガベージコレクタについて説明する。

参照カウンタ法

データにポインタによって共有が発生すると、 不要になったデータの廃棄が問題になるという例を示す。

/* 共有の発生するリストによる和集合 */
struct List* set_or( struct List* p , struct List* q ) {
struct List* n = q ;
for( ; p != NULL ; p = p->next ) {
if ( ! find( q , p->data ) )
n = cons( p->data , n ) ;
}
return n ;
}
/* リストを全部捨てる関数 */
void list_free( struct List* p ) {
if ( p != NULL ) {
list_free( p->next ) ;
free( p ) ;
}
}
void main() {
struct List* a = 適当なリスト生成 ;
struct List* b = 適当なリスト生成 ;
struct List* c = set_or( a , b ) ;
list_free( c ) ;
list_free( b ) ;  // 実はリストは前処理で捨てられている
list_free( a ) ;
}

こういったプログラムであれば、リストを捨てる処理が気軽に書けなくなってしまう。 根本の原因は、データ間で共有されている部分が発生しているため。 この解決方法の１つが参照カウンタ法。

/* 参照カウンタ法を使うリスト */
struct List {
int refc ; //参照カウンタ。生成時は1で初期化
int data ;
struct List* next ;
} ;
/* コピー(共有?)が発生する時にはこれを使え! */
struct List* share( struct List* p ) {
if ( p != NULL )
p->refc ++ ;
}
/* 共有の発生するリストによる和集合 */
struct List* set_or( struct List* p , struct List* q ) {
struct List* n = share( q ) ; // カウントアップ
for( ; p != NULL ; p = p->next ) {
if ( ! find( q , p->data ) )
n = cons( p->data , n ) ;
}
return n ;
}
/* リストを全部捨てる関数 */
void list_free( struct List* p ) {
if ( p != NULL ) {
p->refc-- ; // カウントダウン
if ( p->refc == 0 ) {
list_free( p->next ) ;
free( p ) ;
}
}
}

このような参照カウンタは、ハードディスクでのファイル管理でも使われている。 ハードディスクでは、障害時に参照カウンタ管理が異常になるとゴミデータが残るようになる。 このため障害復旧時には、全HDD領域の参照カウンタの異常チェックが重要。 しかしながら、復旧処理に時間がかかるようになるので、ジャーナリングという方法がとられる。

一方、参照カウンタ法の問題点として、循環リストのようなデータの場合、カウンタが0にならないけど、 他のデータから孤立したデータが発生してしまう。

ガベージコレクタ

参照カウンタ法は単純だけど、万能ではないため、不要となったデータ領域の回収は、 どうするのが理想的なのか？ ひとつの解決方法はガベージコレクタ。 ガベージコレクタ(Garbage Collector)では、不要となったデータ領域はあえて回収しない。 (free()関数は使わない) しかしこのままではメモリ空間がゴミだらけになってしまう。 そこで、メモリ空間がゴミであふれたら、ゴミ回収(Garbage Collect)を行う。 マーク＆スイープ法では、ゴミであふれたら使用中のメモリ空間をたどりながら、 使用中目印をつける(marking)。　その後、目印のついていない領域は回収(sweep)。

ただし、GCが起動すると、他の処理ができなくなるので、処理の中断が発生する。 対話的なシステムでは、GCは処理の遅延になるので、嫌われていた。 最近のガベージコレクタでは、参照カウンタ法も併用した方式がとられるため、 早い段階で不要な領域の回収が可能となり、処理の遅延が問題になることはなくなってきた。

例年より規模を縮小でしたが、ホストファミリーを交え楽しく歓談できました。