作業因子法(Work Factor plan)
マウスやタッチパネル操作の分析に関係したテーマで 特別研究をしている学生さんの、修了認定試験の仮想問題のネタで、 雑談。 こんな問題出るかもよ…ということで、 「操作対象が小さくなると、作業時間にどう影響でるか?」という質問をしてみた。
こんな話をするのは、高専就職前の職場では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 ) ; }
こういったプログラムであれば、リストを捨てる処理が気軽に書けなくなってしまう。 根本の原因は、データ間で共有されている部分が発生しているため。 この解決方法の1つが参照カウンタ法。
/* 参照カウンタ法を使うリスト */ 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は処理の遅延になるので、嫌われていた。 最近のガベージコレクタでは、参照カウンタ法も併用した方式がとられるため、 早い段階で不要な領域の回収が可能となり、処理の遅延が問題になることはなくなってきた。
留学生との懇談会
例年より規模を縮小でしたが、ホストファミリーを交え楽しく歓談できました。