先週説明した、ヒープ領域管理のオマケとして、 OSの主記憶管理についても、簡単に説明を加える。 主記憶管理でも、プロセスの起動・停止と共にメモリ領域の確保と解放が行われる。 OSでは、メモリ空間の断片化をしたら、大きなプロセスのための領域が使えないようでは、ダメ。 断片化の対策が必要かもしれないけど、 OSでは、論理アドレス・物理アドレス変換のための、メモリマップユニット(MMU)などが あるため、断片化対策はあまり重要ではない。

この後は、配列から固定領域は使いづらい点を紹介する。 しかし、最近の新しいプログラミング言語では、ハッシュ法などを用いて、keyから値を検索 してくれる連想配列が一般的になってきた。こういう言語では、配列サイズなども あまり気にする必要もなく、プログラムが記述できる。

この後に、単純リスト・循環リスト・双方向リスト・2分探索木・Ｂ木などの、 リスト構造の応用データについて改めて総括を行った。

ほぼ、解説する内容も終盤ということで、 データベースの内部構造の話の後半と、最近のデータベースの動向を説明し、授業を終える。 来週は、データベース設計の課題を作成する演習とする。

DBの内部構造

データベースのインデックスファイルの作り方として、先週説明したB木、B+木の さらなる高速化ということで、ハッシュ法を説明する。

4年の情報構造論の授業で説明しているので、簡単にオープンハッシュ法と、 チェイニング法を説明する。

また、データベースシステムでは、Tableのファイルとインデックスファイルを どう保存するかといった手法を説明。(a)各テーブル各インデックス毎に1ファイル という方式もあれば、(b)全テーブル・全インデックスで1ファイルという方式もある。 (c)全テーブルで1ファイル、全インデックスで1ファイルというのもある。

最近のデータベースシステムの動向

教科書としている本に記載されている、オブジェクト指向データベースを紹介。 といっても基本となるオブジェクト指向プログラミングの話として、 (a)クラス=オブジェクト+メソッド、 (b)追加データを扱う派生と継承、 (c)派生を応用した仮想関数 といった概念を紹介に留める。

昨年度の斉藤研で試行したデータベースでもあり、XMLデータベースも紹介。XMLは、タグによって記載されるデータであるが、属性を自由に追加できる 自由度の高いデータで、これを自在に扱えるようにしたものがXMLデータベース。

ただ、自在にデータを拡張できるものの、システム側では拡張要素を取り扱う処理を、後で追加できるようにする必要もあり、まだ発展途上のデータベースシステム。

最後に、最も注目されているものとして、NO-SQLを紹介する。 データベースでは分散処理が重要だけれど、同期や排他処理は面倒な処理。 そこで、データをKey-Valueだけで取り扱うようにしたものが、Key-Value型データベース。 これらのシステムは、Googleを代表とするクラウドコンピューティングの世界の データベースとして採用されている。 データの検索はKey参照をベースに行い、SQLなどの検索言語が無いことから、 NO-SQLといった言い方をすることが多い。

留学生とチューターによる合唱です。 最後にはけん玉の得意な留学生の演技もありました。 — http://tsaitoh.net/

高専では昨年末にタイ留学生を受け入れた。 その学生さんはFacebookを使うので友達登録したんだけど、 彼女たちが国の友達とのメッセージでは語尾に"555"とか"55555"とか付いている。 彼女たちに聞いたら、"5"が笑い声の"ハ"と同じらしい。

んで、タイ語の書き込みがあったので、 Facebookの機械語翻訳をかけたんだけど、 さっぱり解らない日本語に変換される。 そのくせ、"555"は"(笑)"に変換され、"55555"は"(爆笑)"に変換される。
# Being翻訳、頭がいいんだか、悪いんだか、よーわからん。

最近、スマホ携帯を机に置き忘れることが増えた(大抵はすぐに取りに戻るんだけど)。 この原因を改めて自分なりに考えたら、ネット端末を使うときの「適材適所」の 意味が「この仕事にはこのネット端末を使う」という意味から、 ユビキタスの恩恵なんだけど「いま居る場所で一番使いやすいネット端末を使う」 という適*在*適所に変わってる。

携帯は当たり前ながらネット端末

以前だったら、なんだかんだと席を離れる時にも常に携帯は肌身離さずだった。 しかしながら、ガラケーよりも格段に便利になったスマホ携帯なんだけど、 ガラケーよりも触る時間は減っているかもしれない。

携帯電話って、一番の売りは当然ながら「即時性」だろう。 だけどスマホになって、バイブ用のモータも小さくなったのか、 着信に気づかない時も増えた。だから、電話も着信を後で気づいて後に対応。 メールと同じじゃん、即時性が無い！
# それに触れば触るほど、バッテリー持たないし…

適在適所

んで、ネット端末も携帯電話、タブレット端末、ノートパソコン、デスクトップ（自宅＆職場）と色々なパソコンを使うけど、Gmail,Dropbox,メールもIMAP…どのネット端末でも、 クラウドのおかげで、それなりに情報が共有され、それなりに仕事が継続できる。

さらに、視力の低下もあるもんだから、手元にタブレット端末があれば、見やすい方を使う、 つまり「いまそこにある端末で一番使いやすいネット端末」という使い方。

以前だったら、学生さんへの連絡は携帯。仕事はデスクトップみたいに、 相手や仕事に応じて端末を使い分けるという「適材適所」だったけど、 「材」が「在」に変わってる…

今日の４年の授業は、他の先生に授業風景を見てもらう公開授業であった。 たった３名とはいえ、チェック目線でしゃべりを見られるのは、 緊張であった…

授業風景では、 (a)授業の程度、(b)学生の理解度、(c)黒板の使い方、(d)シラバスとの一致、 (e)学生参加意欲の向上のさせ方、(f)その他… という点で評価を受ける。

こういう時に、新しい授業方法の模索的な方法を公開授業で見せる人もいるかも知れないけど、 いつもどおりを評価してもらうべきとの思いもあり、 いつも通りのやり方での授業で望んだ。 唯一違うのは、授業メモの blog への記録は、授業後なんだけど、今回は ネタのヌケも恥ずかしいし、昨日中に記載しておいて、blog メモを見ながら…(^_^;

見学してくれた先生からの指摘は、長年慣れた科目でもあり大きな問題の指摘は なく無事に終わった。あったとすれば、テンポが早いかな…という点と、プログラムのコードを示すためやむ終えない だろうとの指摘の上で、字が小さいとのアドバイス。 でも、こればかりは、大講義室の上げ下げできる黒板じゃなきゃ、無理っす。 後は、黒板のチョークの色使い。といっても、テンポよく復習を説明した後に、 自分でも気づいていたけども、黄色のチョークで書き始めてしまったのよ…(T_T; んで、テンポが乱れるのもイヤだったので、 説明が一区切りするまで、黄色で通したのがまずかった。 見学が終わった後の後半でも、ちょろちょろ色使いは困ったりしたけど、 処理前後の違いを強調するために、色を替えても、白・黄・赤と使いきれば、 そろそろ限界。改めて、同じ図を書きなおしたりしながらの説明だった。(それまたいつもどおり…)

いつもどおりの授業の進め方で、それなりに好評化をもらえたので一安心でしたが、 いつもになく緊張した２コマ授業であった。 さて、この後は、指摘された改善点を、改善＆実践したというレポートを含め、 提出しなければいけないのが、ちょっと面倒だけれども、いい刺激にはなったかな。

データベースの内部構造の説明を行う。

最初に、元概念となる2分木の説明を交え、O(log N)にて検索できる利点を説明し、 そのN分木のようなものということで、4年情報構造論での"B木"の説明を行う。

しかし、2分木ではデータ追加の際に、末端にデータが次々と追加され、 追加順番によっては、左右の木の段数が不均衡となった木が生成される可能性がある。

B木は、この問題に対応し、位数(d)の場合、１つの節は2d個のデータ保存場所と、 2d+1個の次の節へのポインタで構成する。 データを収納する場合には、d個以上2d個以内を収納する。 さらに、データを追加してオーバーフローが起こった場合、 中央値のデータを上部ノードに移行し、節を２つに分割する方法をとる。 中央値で分割するため、不均衡が発生しづらい点が特徴。

Wikipedia B木より引用。

B+木

B木では、節が下に行くにつれ分割される。このため、全データに対する逐次処理 を行う場合には、再帰呼び出しが必須となる。しかしながら、再帰は処理も大変であり、 これらを簡単にするためにB+木が使われる。

B+木は、末端の節の先に逐次処理のための線形リストを設け、末端の節を横断できる ようにリストでつないでおく。

Wikipedia B+木より引用。

動的メモリの管理手法として、参照カウンタ法・ガベージコレクタ法の説明の最後として、 ヒープメモリの管理手法について説明する。 いつもはこういった講義メモは、授業後に作成しているけど、 今回は他の先生に授業方法開演のために見てもらう『公開授業』となるため、 授業前にメモを記載しておく。

ヒープメモリの必要性

必要に応じてメモリ領域を確保する場合、一般的にはmalloc()+free()を用いる。 メモリは有限でもあり、free()で返却されたメモリ空間の再利用が重要となる。 確保したメモリが不要となるタイミングが『最後に確保したメモリが最初に不要となる』という条件を満たすのであれば、スタックを用いればいい。 スタックを用いるメモリ確保命令は、alloca(int) であり、その仕組みを my_alloca() にて 説明すると、内部はおおよそ、以下のような処理である。

#define HUGE_SIZE (大きな領域サイズ)
char u_stack[ HUGE_SIZE ] ;
char *u_sp = stack + HUGE_SIZE ; // 領域の末尾アドレスで初期化
char* my_alloca( int size ) {
u_sp -= size ;
return u_sp ;
}

あとは、関数呼び出し時に、戻り番地(プログラムカウンタ:PC)の保存と共に u_sp を保存し、関数を終え元処理に復帰する(PCの復帰)の際に u_sp を復帰すればいい。

ヒープメモリのブロックが固定サイズなら

alloca() では、「最後に確保したメモリが最初に不要となる』の条件が重要であり、 不要となるタイミングが予測できない場合は、どうすればいいか？ 基本は、free() で開放したメモリを再利用すればいいのだから、 free() で開放したメモリをリスト構造で連結したスタック(free_list)としておいて、 malloc()の際は、free_listに保存しておいたメモリ領域のリストの先頭を使えばいい。

動作原理を説明する、模式的なプログラムを以下にしめす。 ただし、malloc() の引数で指定するメモリブロックサイズが不均一だと、 処理が分かりにくいので、ブロックサイズは固定で説明する。

#define BLK_SIZE (適当な大きさ)
struct MemList {
struct MemList* next ;
char memory_block[ BLK_SIZE - (nextのサイズ) ] ;
} ;
// heap内は全てがリストで繋がるように初期化する。
struct MemList heap[ HUGE_SIZE ] ;
struct MemList* free_list = (heapの先頭) ;
char* my_malloc() {
char* ans = free_list ; // 型キャストは省略
free_list = free_list->next ;
return ans ;
}
void my_free( char* p ) {
p->next = free_list ; // リストの先頭に入れる
free_list = p ;
}

可変長ブロックのヒープメモリ管理

上記のプログラムでは、説明のために確保するメモリブロックは固定サイズとしたが、 実際には色々なサイズが使われる。この場合、おおまかに以下のような方法がとられる。

ヒープメモリで管理する個々のメモリブロックには、 管理用にそれぞれ (1)次のメモリブロックへのポインタと、 (2)メモリブロックのサイズ を記録する。

struct HeapList {
struct HeapList* next ;
int              size ;
char*            memory[ (size) ] ; // 説明用の記述、C言語ではエラー
} ;

管理するメモリ領域は、最初１つの巨大なメモリブロックとして初期化し、 そのブロックの先頭を free_list に入れておく。

malloc() では、

1. free_list の先頭から、要求サイズよりも十分な大きさのメモリブロックを探す。
2. そのメモリブロックの大きさと要求サイズが同じなら、free_list からそのブロックを切り離し、そのブロックをユーザに使ってもらう。
3. 十分に大きい場合は、そのメモリブロックの末尾を、要求サイズ分に切り分ける。
   • つまり、そのブロックのsizeを、要求サイズ分だけ減らし、
   • 分割した末尾部分のアドレスをmallocの返り値として、ユーザに使ってもらう。

free()で、メモリブロックが返却された場合は、 基本的に free_list に連結すればいい。 ただし、このままでは、freeとmallocを繰り返すうちに、メモリブロックは小さく細切れになる一方で、最終的に大きなメモリブロックが使えなくなる。

この対策として、不要となったブロックを free_list につなぐ場合、ブロックはメモリアドレス順に並ぶようにする。 さらに、free_list につなぐ際に、リストの前後のメモリブロックと隣接する場合は、 next と size を調整して1つの大きなメモリブロックとなるように併合を行う。

ヒープホールと断片化

上記のようなmallocとfreeであれば、mallocの呼び出しで細切れにされたメモリブロックも、freeの呼び出し時の併合により、大きなメモリブロックに戻る。 しかしながら、最悪の順序でmallocとfreeを繰り返すと、一連のヒープ領域が「使用・不要・使用・不要・使用」のように交互になった場合、全体では不要メモリの総量は大きくても、mallocの要求メモリサイズの領域を見つけられなくなる可能性がある。

このような、細切れになった状態を断片化(フラグメンテーション)と呼び、 その細分化された不要領域はメモリ領域の小さな穴ということで、ヒープホールと呼ばれる。

毎年、このネタでは鉄板なんだけど、フラグメンテーション解消のデフラグ ということで、ハードディスクのフラグメンテーションの説明とデフラグ処理の 説明を行う。