ホーム » 2010 » 1月 » 08

日別アーカイブ: 2010年1月8日

2010年1月
« 12月   2月 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最近の投稿(電子情報)

アーカイブ

カテゴリー

サンプリングデータの積分・微分など

専攻科1年の実験の補足説明の時間があったので、 Arduinoの制御実験の結果を受け、制御用のサンプリングデータの数学的話をする。 モータ制御で、速度値を積算すれば速度の積分で距離になる話や、 加速度センサーの値を積分し速度、さらに積分で距離という話。 こういった2重積分でセンサー誤差の蓄積による問題点を解説する。

また、サンプリングデータの平滑化として、単純移動平均や指数移動平均などの話をする。 積分の逆の話として、データの直前値との差が微分といった話と、 幅広く説明した。 さすがに専攻科生だけあって、データのノイズ対策について質問したら、 フーリエ変換してフィルタリング…といった話も出てきたが、 簡単な計算でも何ができるのかという点で、興味を持って聞いてくれたみたい。

バックアップ

参照カウンタ法の雑談として、ジャーナリングについて話す。 システムの急な停止によって、参照カウンタが壊れると、まさにマーク&スイープ法で 参照カウンタの修正が行われるが、巨大なファイル容量であれば極めて時間がかかる。 このため、ファイルシステムへの書き込みの際には、修復用のヒントも同時に書き込まれ、 正常書き込みで修復データを消すが、急なシステムダウンの時は、修復ヒントをつかって ハードディスクを復旧する。こういった対策が「ジャーナリング」

ただし、ジャーナリングされていても、ハードディスクは壊れるので、壊れる際の対策も必要。 んで、一般的にはRAIDが使われる。 RAID1のミラーリングや、RAID5での分散書き込みで1台壊れても復旧!という考え方を説明。 でもでも、間違ったデータが自動的に書き込まれたら終わりなので、 定期的なバックアップも重要と解説する。

S.M.A.R.T差分バックアップホットスワップ

参照カウンタ法とガベージコレクタ

前回テスト解説で少し説明をしているけど、参照カウンタ法とガベージコレクタについて解説。

参照カウンタ法

例えばリスト操作で、リストの開放を下記のようなコードで作った場合、 データに共有が発生しているため、「持っているデータを free で全部捨てる」 といったコードを書くと、共有部分は2回捨てられる処理となり、 プログラムが異常動作してしまう。

struct List* union( struct List* l1 , struct List* l2 ) {
struct List* ans = l2 ;
for( struct List* p = l1 ; p != NULL ; p = p->next ) {
// find(A,L) : AがリストLに含まれていればTrue
if ( ! find( p->data , l2 ) )
ans = cons( p->data , ans ) ;
}
return ans ;
}
void free_all_list( struct List* p ) {
if ( p != NULL ) {
free_all_list( p->next ) ;
free( p ) ;
}
}
void main() {
struct List* a = リスト ;
struct List* b = リスト ;
struct List* c = union( a , b ) ;
:
なんらかのしょり ;
:
free_all_list( c ) ; // cの後半はbのはず
free_all_list( b ) ; // free_all_list(c)でbは既に捨てられている
free_all_list( a ) ;
}

こういう共有が発生している場合の対処方法として、参照カウンタ法がある。 共有されるデータには、すべてカウンタを設け、共有が発生する場合には、 カウンタを増やし、freeの際には、カウンタを減らし0の場合だけ 本当に捨てるという処理にすればよい。

struct List {
int   refc ; // 初期値1、共有されるたびに+1,共有が解除されれば-1
int   data ; // refc = 0 で、本当に free() を実行する。
struct List* next ;
}

ちなみに、この参照カウンタ法は、unix におけるリンク機能(1つのファイル実体に複数のファイル名をつける場合[ハードリンク])でも使われており、新しくハードリンクを貼れば+1し、 ファイルを消すと-1して、0になれば本当に消す。 ただし、OSの異常停止などで、参照カウンタがおかしくなる場合があるため、unix では、 異常停止からの回復時には fsck で参照カウンタの修正などが行われる。 最近はジャーナリング機能付きファイルシステムが普通なので、fsck 実行は減ったけど….

ガベージコレクタ

上記の参照カウンタは、便利そうに見えるけど、循環リストには対応できない。 こうなってくると、データを本当に捨てるか捨てないかは、プログラマーの判断では極めて難しい。そこで、最近のシステムでは、不要になったデータを捨てる判断は、ガベージコレクタ(ゴミ拾い)に任せるようになってきた。 ガベージコレクタを持った処理系では、free() は存在しない。メモリが不足した場合に、 システムが不要なメモリを回収してくれる。

回収方法としては、古くはマーク&スイープ法が有名。 メモリが不足した時に、全メモリには最初にマークを消しておき、使用中のメモリからたどりながら、実際に使用されているデータには、「使用中マーク」をつけていく。 最後に使用中マークの無いデータを回収する。

しかしながら、この方法はメモリが無くなった時に、処理を全部中断して、時間をかけたメモリ回収(ガベージコレクタ)が起動するため、利用者にしてみるとシステムが突如フリーズしたように 感じる。最近では、このガベージコレクタは、システム処理に並行して実行できるように工夫されている。

最近の新しい言語処理系 Java などはガベージコレクタが搭載されている。 しかし、C,C++ はガベージコレクタが無いので動的メモリを使ったプログラミングでは、 注意深く対応するしかない。

調べてみると、最近のJavaでのGCは、世代別GCという方法が使われているらしい。 若い世代、古い世代、永続的な世代に分け、生存時間順に随時永続側にコピーされていく。 局所変数のデータは、若い世代の場所に置かれ、 関数終了時に不要ならばガンガン消されていく。