電子情報工学科

PTAMを使って、マーカ・レスでロボット制御の卒研を期待して、 MacBookAirを購入。PTAMを動くようにしてみたけど、制御にまで 話を続けるために、もう少し基礎勉強。 解説サイトがあるので、以下にまとめる。

• PTAMの解析-1
• PTAMの解析-4 動画の公開

先週に引き続き、動的メモリ領域の管理法の説明を行う。 最初に先週の領域サイズが固定ならば、freelist で管理可能という話と、 「最後に確保したメモリが最初に不要となる…」というのであれば、 スタックで管理が可能という話をしておく。

自由な領域サイズでのmalloc+freeでは、一般的に 次の領域へのポインタと、そのブロックのサイズを使って管理を行う。 このブロックをfreelist でリスト構造にして保存している。

mallocの処理

mallocでは、freelistの中から、要求サイズより十分大きいブロックを探すか、 要求サイズと同じサイズのメモリブロックを検索する。

要求サイズと同じブロックが見つかった場合は、そのブロックを迂回するようにポインタをつなぎかえる。(上図の青) 要求サイズより大きなブロックが見つかった場合は、その領域の後半を切り分けてユーザにメモリを貸し出す。この場合は、ブロックサイズの修正だけ。(上図の赤)

freeの処理

freeでは、返却された領域をfreelistに接続すればいいが、 このままではメモリ領域が細切れになるだけで、 最終的に大きなメモリを確保できなくなってしまう。 このため、返却されたメモリブロックは、freelist内に隣接する領域が無いか検索され、 隣接するメモリブロックと併合する。

一般的に次のメモリブロックへのポインタは、昇順方向になるように接続する。 また、mallocやfreeの処理での freelist 内の検索が行われるため、ヒープホールが 大量発生しているような状況では、処理効率の悪さが問題となる。 この辺の処理を簡単にするために、freelist をメモリブロックの大きさ毎に複数使う方法もある。

補足説明として、実際にユーザが要求したメモリとは別に、nextポインタとブロックサイズを 記憶する必要があるため、小さいメモリ領域をmallocで使うとメモリ使用効率が悪いことを 説明する。また、メモリブロックのサイズは、ワード境界のことを考慮して、4の倍数(32bitコンピュータならば)に切り上げられることを説明する。

ワードアライメントやheap管理データの領域が無駄といった話だけだと、 メモリ倹約至上主義で時代遅れと言われかねない。 補足説明として、メモリ増設もマザーボードから変えなきゃムリって場合はハードウェアの価格に影響が出ることと、 メモリ浪費で仮想メモリが使われだすとスラッシングで処理速度の低下の弊害を説明する。

H22秋の基本情報技術者試験の問題の解説サイトをみていると、 情報構造論の出題ネタにも使えそうな出題がチラホラ。 通常の私の出題傾向とは違うけど、アリかもな…

• 配列で表した木構造の葉の数を求めよ
• 5桁の数をハッシュ法を用いて配列に格納せよ

例年夏休み最後の時期に技術系高校の先生を対象とした、 制御関連の実習中心の講習会ということで、H8を使ったライントレース(H20),Arduinoをつかったライントレース(H21)と協力してきた。 次年度も引き受けるお話になっているけど、 H22年度は、中学校の技術家庭科の先生も含めた講習会を実施できないかとの依頼で、 以下のような講習会(案)となった。

中学校の「プログラムによる計測・制御」とは？

んで、新しく中学校の先生も対象とすることで、依頼元の教育研究所さんからは、 プログラム言語がBASICで習っている…とのお話があり、できればBASICという 要望もあるけど、ArduinoでわざわざBASICというのも変だし、やっぱりそこはC言語。

ただ、中学校の技術家庭科ではH24年度から「プログラムによる計測・制御」が 始まるとのことなので、内容をしらべてみた。

　新学習指導要領・生きる力
　 第2章　各教科 第8節 技術家庭
　 第2 各分野の目標及び内容
　   [技術分野]-2内容-D情報に関する技術
　   （3）　プログラムによる計測・制御について，次の事項を指導する。
　     ア　コンピュータを利用した計測・制御の基本的な仕組みを知ること。
　     イ　情報処理の手順を考え，簡単なプログラムが作成できること。
　別資料によれば、
　    計測・制御システムは，センサ，コンピュータ，アクチュエータなどの要素で
　    構成されていることや，計測・制御システムの中では一連の情報が
　    プログラムによって処理されていることを知ることができるようにする。

基本、ライントレースであればどれも体験できることだけど、 指導要領の別項には、 「（1）のアについては，情報のディジタル化の方法と情報の量についても扱うこと。」 との記載もある。 なので、求められていることは違うかもしれないけど、 ちょっとA/D変換や量子化の説明を増やしてみようかな…

関連の先生の教育系の発表資料をみると、 順序を覚えさせることが中心のシーケンス制御と、 電子回路でのセンサーと関連させたフィードバック制御の違いといったネタもある。 ライントレースの実験の前に、『自走ロボットを指定距離進んで、指定角度方向を変えて…』 というシーケンス処理っぽいプログラムを書いてもらって、フィードバックが無いとダメという 話を強調するのもありかもしれない。 動いている途中でタイヤがスリップとか、電池がヘタルとか、何か別のものがぶつかるとか…の 外乱なども交えながら…

年度末も近づき、学科予算での未執行分での購入物品の相談を受けていたが、 最終的な案を提示する。 WiFi環境の改善ということで、各フロアのAPをハイパワー11n対応…これはすんなり 皆さんも納得しそう。 WiFiの上流に設置しているFERECルータだけど、最近故障修理をした所なので、 購入なんだけど、後継機種がでていないので、躊躇している。 見積もり価格も30万そのまんまだし…

高久先生と雑談していたら、学科サーバの更新もいいのではないかとの案が浮上。 パソコン工房さんで、サーバ用をちょちょいと構成を考えて、33万円。 ちなみに、学科サーバmaisyちゃんは(長男が保育園時代に気に入っていたキャラクター ということで命名しているので….)軽く5年は経過。 サーバの/bootディレクトリをのぞくと、2003/4/1というファイルがある。ということで、約8年… 途中でHDD入れ替えは一度あったけど、確かに長生き。 しかしながら、学科実験用サーバsherryも控えているので、maisy→sherryの移行も可能 だし、悩みどころ。

ということで、WiFi用ルータをとるか、サーバ更新をとるか…と考えていた。 しかし、今日の校長年頭あいさつにて「機構より各教員+5万の研究費」という お年玉があったようなので、学科の教員研究費を持ち寄って、両方買えば…という案も出てきた…

自分の携帯もIS03に機種変更して自宅サーバなどのWebページのスマートフォン対策は それなりにやったけど、緊急連絡システムもよく考えりゃ、対応していない。 このためスマートフォンの人は、最初に小さい文字で出てきたのを、わざわざ拡大することになる。

ということで、緊急連絡システムのスマートフォン対策を行う。 といっても、PHPスクリプトの先頭に、iPhone対策の定番の下記のタグを埋め込んだだけだけど…

<meta name="viewport" content="width=240, initial-scale=1.0,
user-scalable=yes, maximum-scale=3.0, minimum-scale=1.0">

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

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