ホーム » 2010

年別アーカイブ: 2010

2019年9月
« 8月    
1234567
891011121314
15161718192021
22232425262728
2930  

最近の投稿(電子情報)

アーカイブ

カテゴリー

2010年12月26日(第196回)

  • 英語の囃子 第38回  吉田先生、電子情報5年丸山さん
    英語プレゼンテーションコンテストについて
    eng101226.mp3
  • 数学の部屋 第55回 長水先生、MMM同好会の皆さん
    math101226.mp3

photo101226.jpg
スタジオの隣の誠照寺も雪景色になっていました。

mallocとfreeの実装の導入部

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

この後、リスト構造の応用の最後の説明として、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では、これらの不連続状態の改善のために、 デフラグ機能がある。デフラグでは、ファイルの配置を入れ替え、 ファイルが連続して配置されるようにしてくれる。

OpenKinectが使えた…

Kinectを来年の卒研用に購入したので、手持ちのMac OS Xで使えるか、 試してみた。 参考にというか、この記事をそのまんま実験しただけ。 参考記事

環境を準備するために、gitとcmakeが必要みたい。 参考Webではmacportを使っているけど、 先日finkにしたので、finkにてインストール。

(( 必要なツールをインストール ))
$ su root
# fink install git
# fink install cmake
(( ソースコードのダウンロード ))
$ git clone https://github.com/OpenKinect/libfreenect.git
$ git clone git://git.libusb.org/libusb.git
(( libusbのインストール ))
$ cd libusb/
$ chmod +x autogen.sh
$ patch -p1 < ../libfreenect/platform/osx/libusb-osx-kinect.diff
patching file libusb/libusbi.h
patching file libusb/os/darwin_usb.c
patching file libusb/os/darwin_usb.h
patch unexpectedly ends in middle of line
Hunk #2 succeeded at 147 with fuzz 1.
(( 参考資料とautogenの実行順序逆だったな... ))
$ ./autogen.sh
$ ./configure
$ make
$ su root
# make install
(( OpenKinectのインストール ))
$ cd ..
$ mkdir libfreenect/build
$ cd libfreenect/build
$ ccmake ..
$ cmake ..
$ make
$ su root
# make install
$ cd ../examples
$ cp ../include/* .
$ cmake .
$ make

#include の <libfreenext.h> "libfreenect.h" といったPATH の違いでコンパイルエラーがでたけど、適当に直しながらコンパイルして動いた。

ゼロエネルギービルの可能性

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

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

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

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

2010年12月19日(第195回)

収録した模様をお送りしました。

  • 学生インタビュー デザインコンペティション2010に参加した学生さん
    専攻科生産システム工学専攻2年 松谷さん、環境都市工学科5年 佐藤さん、脇本さん
    desicom101210.mp3
  • にしにしの部屋沖縄分室 沖縄高専 正木先生、福井高専 奥田先生
    nishi101210.mp3 

GrWinでグラフィックス基礎演習

プログラミング応用の第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となる。
}

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

留学生との懇談会

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

緊急連絡システムの組織間連携分析

丹南地区向けの緊急連絡システムでは、同胞通信で受信した記事をそのまま自組織向けに 再送が簡単にできる機能を設けている。 越前市や鯖江市ではこの機能を利用し、市役所が各学校長向けに安全防災情報を送り、 学校長が保護者にすぐに通知すべきと判断すると、記事が再配信される。 これ以外にも近隣の学校での害獣などの情報を自校向けに再配信といった使われ方もしている。

そこで、各組織間でどういった記事が再配信されるのか分析を行った。 再配信の際には、各学校で若干の編集を加えて配信する場合も多いため、 各記事の内容を単語分割し、最大マッチした単語数で記事の一致性を数値化し、 一定値以上の類似記事とみなされた件数と発生時期をグラフ化した。

ただし配信テストのような記事は、あらかじめ除外した。

他組織へ転送された内容

他組織で再配信された記事の分類結果をしたグラフを以下に示す。 不審者や害獣に関する情報は、市全域で安全を共有する観点で、70%が再配信 されている。 訃報は、転属が多い学校において学校関係者間の連絡として使われているものである。

面白い特徴発見! 不審者や害獣情報は組織間で転送されている頻度が高い。 しかしながら前分析で第3位の利用頻度であった感染に関係する情報は、 転送される頻度が不審者・害獣情報に比べて極めて少ない。

感染の情報は、保護者向けには学校の状況を伝えるために高頻度で利用されているが、 じわじわと拡大していくために時間的な緊急性が低くく、 他組織に転送する必要性が低いと認識されていると思われる。

他組織への転送の頻度

記事が他組織で再配信された時期と、再配信された組織数で時系列に示したグラフを 以下に示す。 害獣や感染に関係する情報は季節性が予想されたが、不審者情報も含めると、 時期との関連性は顕著にあらわれていない様に思われる。

2010/12/15追記: 上の分析では、あまり状況が解らなかったので、記事の種類に応じてマーカーを 色分けしてみた。 これを見てみると、害獣ネタの季節性が見えてきた。 また、不審者に関する情報は、2010年度は減ってきていることが解る。 その反面、平和だからこそなのかもしれないけど、学校の先生間の訃報の連絡 の頻度が高まっているようである。 また、2009年度は新型インフルエンザの影響で、広く配信された記事が見受けられる。 このほかにも、2006年の福井豪雨や害獣の情報が広く配信されたことが分かる。