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

こんな話をするのは、高専就職前の職場では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は処理の遅延になるので、嫌われていた。 最近のガベージコレクタでは、参照カウンタ法も併用した方式がとられるため、 早い段階で不要な領域の回収が可能となり、処理の遅延が問題になることはなくなってきた。

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