ホーム » 2019 (ページ 5)
年別アーカイブ: 2019
高専祭・電子情報の展示
今日10/18(金)から、19(土),20(日)にかけて、高専祭が始まりました。
電子情報の5年生が頑張って自作のゲームなどを展示しています。
nfsのソフトマウント
自室の Linux サーバでは、自分が管理している Azure 上のサーバのデータバックアップを取っているが、ハードディスク容量が巨大な訳でもないので、iMac に接続された Drobo (複数ディスクの改良RAID?) に保存させている。
このネットワーク越しのバックアップでのディスクアクセスになるが、iMac を時々再起動させると、その間に icinga のディスクチェック処理が走った際に、アクセスできないために df プロセスが大量に残るトラブルが発生していた。リトライするため CPU 負荷も高い状態で、一番簡単なのは サーバの再起動。(iMacを再起動したら、その後にLinuxサーバを再起動….無駄や…)
最初は、check_disk 処理で余計なところを見させないために、特定マウント先を無視するオプションを加えていたが、df がマウント先をしつこくアクセスをリトライするのが原因。
よく考えたら、ネットワーク越しのマウントだから、ハードマウント(ディスクアクセスに失敗したら何度もリトライ)ではなく、ソフトマウント(複数回リトライしたら諦める)にする必要がある。
ということで、automount オプションに、”soft” オプションを加えて解決。
2分探索木
配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり)
// 2分探索法 int array[ 8 ] = { 11, 13 , 27, 38, 42, 64, 72 , 81 } ; int bin_search( int a[] , int key , int L , int R ) { // Lは、範囲の左端 // Rは、範囲の右端+1 (注意!!) while( R > L ) { int m = (L + R) / 2 ; if ( a[m] == key ) return key ; else if ( a[m] > key ) R = m ; else L = m + 1 ; } return -1 ; // 見つからなかった } void main() { printf( "%d¥n" , bin_search( array , 0 , 8 ) ) ; }
一方、リスト構造ではデータ列の真ん中のデータを取り出すには、先頭からアクセスするしかないのでO(N)の処理時間がかかり、極めて効率が悪い。リスト構造のようにデータの追加が簡単な特徴をもったまま、もっとデータを高速に探すことはできないものか?
2分探索木
ここで、データを探すための効率の良い方法として、2分探索木(2分木)がある。以下の木のデータでは、分離する部分に1つのデータと、左の枝(下図赤)と右の枝(下図青)がある。
この枝の特徴は何だろうか?この枝では、中央のデータ例えば42の左の枝には、42未満の数字の枝葉が繋がっている。同じように、右の枝には、42より大きな数字の枝葉が繋がっている。この構造であれば、64を探したいなら、42より大きい→右の枝、72より小さい→左の枝、64が見つかった…と、いう風にデータを探すことができる。
特徴としては、1回の比較毎にデータ件数は、(N-1)/2件に減っていく。よって、この方法であれば、O(log N)での検索が可能となる。これを2分探索木とよぶ。
このデータ構造をプログラムで書いてみよう。
struct Tree { struct Tree* left ; int data ; struct Tree* right ; } ; // 2分木を作る補助関数 struct Tree* tcons( struct Tree* L , int d , struct Tree* R ) { struct Tree* n = (struct Tree*)malloc( sizeof( struct Tree ) ) ; if ( n != NULL ) { /* (A) */ n->left = L ; n->data = d ; n->right = R ; } return n ; } // 2分探索木よりデータを探す int tree_search( struct List* p , int key ) { while( p != NULL ) { if ( p->data == key ) return key ; else if ( p->data > key ) p = p->left ; else p = p->right ; } return -1 ; // 見つからなかった } struct Tree* top = NULL ; void main() { // 木構造をtcons()を使って直接生成 (B) top = tcons( tcons( tcons( NULL , 13 , NULL ) , 27 , tcons( NULL , 38 , NULL ) ) , 42 , tcons( tcons( NULL , 64 , NULL ) , 72 , tcons( NULL , 81 , NULL ) ) ) ; printf( "%d¥n" , tree_search( top , 64 ) ) ; }
この方式の注目すべき点は、struct Tree {…} で宣言しているデータ構造は、2つのポインタと1つのデータを持つという点では、双方向リストとまるっきり同じである。データ構造の特徴の使い方が違うだけである。
理解度確認
- 上記プログラム中の、補助関数tcons() の(A)の部分 “if ( n != NULL )…” の判定が必要な理由を答えよ。
- 同じくmain() の (B) の部分 “top = tcons(…)” において、末端部に NULL を入れる理由を答えよ。
2分木に対する処理
2分探索木に対する簡単な処理を記述してみよう。
// データを探す int search( struct Tree* p , int key ) { // 見つかったらその値、見つからないと-1 while( p != NULL ) { if ( p->data == key ) return key ; else if ( p->data > key ) p = p->left ; else p = p->right ; } return -1 ; } // データを全表示 void print( struct Tree* p ) { if ( p != NULL ) { print( p->left ) ; printf( "%d¥n" , p->data ) ; print( p->right ) ; } } // データ件数を求める int count( struct Tree* p ) { if ( p == NULL ) return 0 ; else return 1 + count( p->left ) + count( p->right ) ; } // データの合計を求める int sum( struct Tree* p ) { if ( p == NULL ) return 0 ; else return p->data + count( p->left ) + count( p->right ) ; } // データの最大値 int max( struct Tree* p ) { while( p->right != NULL ) p = p->right ; return p->data ; }
これらの関数では、木構造の全てに対する処理を実行する場合には、再帰呼び出しが必要となる。
データベースの用語など
データベースの機能
データベースを考える時、利用者の視点で分類すると、(1) データベースの管理者(データベース全体の管理)、(2) 応用プログラマ(SQLなどを使って目的のアプリケーションに合わせた処理を行う)、(3) エンドユーザ(データベース処理の専門家でなく、DBシステムのGUIを使ってデータベースを操作する)となる。
データベース管理システム(DBMS)では、データとプログラムを分離してプログラムを書けるように、データ操作言語(SQL)で記述する。
また、データは独立して扱えるようにすることで、データへの物理的なアクセス方法があっても、プログラムの変更が不要となるようにします。
データベースは、利用者から頻繁に不定期にアクセスされる。このため、データの一貫性が重要となる。これらを満たすためには、(a) データの正当性の確認、(b) 同時実行制御(排他制御)、(c) 障害回復の機能が重要となる。
これ以外にも、データベースからデータを高速に扱えるためには、検索キーに応じてインデックスファイルを管理してくれる機能や、データベースをネットワーク越しに使える機能などが求められる。
データベースに対する視点
実体のデータをそれぞれの利用者からデータベースを記述したものはスキーマと呼ばれる。そのスキーマも3つに分けられ、これを3層スキーマアーキテクチャと呼ぶ。
- 外部スキーマ – エンドユーザからどんなデータに見えるのか
- 概念スキーマ – 応用プログラマからは、どんな表の組み合わせで見えるのか、表の中身はどんなものなのか。
- 内部スキーマ – データベース管理者から、どんなファイル名でどんな形式でどう保存されているのか
データモデル
データを表現するモデルには、いくつかのモデルがある。
- 階層モデル – 木構造で枝葉に行くにつれて細かい内容
- ネットワークモデル – データの一部が他のデータ構造と関係している。
- 関係モデル – すべてを表形式で表す
データベースの基礎
データベースは、1970年頃に、E.F.コッド博士によりデータベースのための数学的な理論が確立された。
- 集合 A, B – 様々なデータ
- 直積 A✕B = { (x,y) | x∈A , y∈B } 集合A,Bのすべての組み合わせ
- 関係 R(A,B) すべての組み合わせのうち、関係があるもの。直積A,Bの部分集合
例えば、A={ s,t,u } , B={ p,q } (定義域) なら、
A✕B = { (s,p) , (s,q) , (t,p) , (t,q) , (u,p) , (u,q) }
このうち、Aが名前(sさん,tさん,uさん)、Bが性別(p=男性,q=女性)を表すなら、
R(A,B) = { (s,p) , (t,q) , (u,p) } (例)
(例):(sさん,男性) , (tさん,女性) , (uさん,男性)
理解確認
- データベースにおける3層スキーマアーキテクチャについて説明せよ
- 集合A,Bが与えられた時、関係R(A,B) はどのようなものか、数学定義や実例をあげて説明せよ。
双方向リスト
リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣言してしまうと、実際のデータ数が少ない場合、メモリの無駄も発生する。しかし、想定件数と実データ件数がそれなりに一致していれば、無駄も必要最小限となる。リスト構造では、次のデータへのポインタを必要とすることから、常にポインタ分のメモリは、データにのみ注目すれば無駄となる。
シーケンシャルアクセス・ランダムアクセス
もう1つの欠点がシーケンシャルアクセスとなる。テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす必要があり、データ件数に比例したアクセス時間を要する。このような N番目 データ参照に、O(N)の時間を要するものは、シーケンシャルアクセスと呼ばれる。
一方、配列はどの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。
このため、プログラム・エディタの文字データの管理などに単純リストを用いた場合、1つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、大量の行数の編集では、使いものにならない。ここで、シーケンシャルアクセスでも1つ前にもどるだけでも処理時間を改善してみよう。
単純リストから双方向リストへ
ここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、1つ後ろのデータ(N番目からN+1番目)をアクセスするのは簡単だけど、1つ前のデータ(N-1番目)を参照しようと思ったら、先頭から(N-1)番目を辿るしかない。でも、これは O(N) の処理であり時間がかかる処理。
ではどうすればよいのか?
この場合、一つ前のデータの場所を覚えているポインタがあれば良い。
// 双方向リストの宣言 struct BD_List { struct BD_List* prev ; // 1つ前のデータへのポインタ int data ; struct BD_List* next ; // 次のデータへのポインタ } ;
このデータ構造は、双方向リスト(bi-directional list)と呼ばれる。では、簡単なプログラムを書いてみよう。双方向リストのデータを簡単に生成するための補助関数から書いてみる。
// リスト生成補助関数 struct BD_List* bd_cons( struct BD_List* p , int d , struct BD_List* n ) { struct BD_List* ans ; ans = (struct BD_List*)malloc( sizeof( struct BD_List ) ) ; if ( ans != NULL ) { ans->prev = p ; ans->data = d ; ans->next = n ; } return ans ; } void main() { struct BD_List* top ; struct BD_List* p ; // 順方向のポインタでリストを生成 top = bd_cons( NULL , 1 , bd_cons( NULL , 2 , bd_cons( NULL , 3 , NULL ) ) ) ; // 逆方向のポインタを埋める top->next->prev = top ; top->next->next->prev = top->gt;next ; // リストを辿る処理 for( p = top ; p->next != NULL ; p = p->next ) printf( "%d\n" , p->data ) ; for( ; p->prev != NULL ; p = p->prev ) printf( "%d\n" , p->data ) ; }
双方向リストの関数作成
以上の説明で、双方向の基礎的なプログラムの意味が分かった所で、練習問題。
先のプログラムでは、1,2,3 を要素とするリストを、ナマで記述していた。実際には、どんなデータがくるか分からないし、指定したポインタ p の後ろに、データを1件挿入する処理 bd_insert( p , 値 ) , また、p の後ろのデータを消す処理 bd_delete( p ) を書いてみよう。
// 双方向リストの指定場所 p の後ろに、値 d を要素とするデータを挿入せよ。 void bd_insert( struct BD_List* p , int d ) { struct BD_List*n = bd_cons( p , d , p->next ) ; if ( n != NULL ) { p->next->prev = n ; p->next = n ; } } // 双方向リストの指定場所 p の後ろのデータを消す処理は? void bd_delete( struct BD_List* p ) { struct BD_List* d = p->next ; d->next->prev = p ; p->next = d->next ; free( d ) ; } // この手のリスト処理のプログラムでは、命令の順序が重要となる。 // コツとしては、修正したい箇所の遠くの部分を操作する処理から // 書いていくと間違いが少ない。
番兵と双方向循環リスト
前述の bd_insert() だが、データの先頭にデータを挿入したい場合は、どう呼び出せば良いだろうか?
bd_insert() で、末尾にデータを挿入する処理は、正しく動くだろうか?
同じく、bd_delete() だが、データの先頭のデータを消したい場合は、どう呼び出せば良いだろうか?
また、データを消す場合、最後の1件のデータが消えて、データが0件になる場合、bd_delete() は正しく動くだろうか?
こういった問題が発生した場合、データが先頭・末尾で思ったように動かない時、0件になる場合に動かない時、特別処理でプログラムを書くことは、プログラムを読みづらくしてしまう。そこで、一般的には 循環リストの時にも紹介したが、番兵(Sentinel) を置くことが多い。
しかし、先頭用の番兵、末尾用の番兵を2つ用意するぐらいなら、循環リストにした方が便利となる。このような双方向リストでの循環した構造は、双方向循環リスト(bi-directional ring list)と呼ばれる。
この双方向循環リストを使うと、(1)先頭にデータを挿入(unshift)、(2)先頭のデータを取り出す(shift)、(3)末尾にデータを追加(push)、(4)末尾のデータを取り出す(pop)、といった処理が簡単に記述できる。この4つの処理を使うと、単純リスト構造で説明した、待ち行列(queue)やスタック(stack) が実現できる。この特徴を持つデータ構造は、先頭・末尾の両端を持つ待ち行列ということで、deque (double ended queue) とも呼ばれる。
理解確認
- 双方向リストとはどのようなデータ構造か図を示しながら説明せよ。
- 双方向リストの利点と欠点はなにか?
- 番兵を用いる利点を説明せよ。
- deque の機能と、それを実現するためのデータをリストを用いて実装するには、どうするか?
- 双方向リストが使われる処理の例としてどのようなものがあるか?
2019データベース・ガイダンス
インターネットの情報量
インターネット上の情報量の話として、2010年度に281EB(エクサバイト)=281✕1018B(参考:kMGTPEZY)で、今日改めて探したら、2013年度で、1.2 ZB(ゼタバイト)=1.2✕1021B という情報があった。ムーアの法則2年で2倍の概算にも、それなりに近い。 では、今年2019年であれば、どのくらいであろうか?
そして、これらの情報をGoogleなどで探す場合、すぐにそれなりに情報を みつけてくれる。これらは、どの様に実装されているのか?
Webシステムとデータベース
まず、指定したキーワードの情報を見つけてくれるものとして、 検索システムがあるが、このデータベースはどのようにできているのか?
Web創成期の頃であれば、Yahooがディレクトリ型の検索システムを構築 してくれている。(ページ作者がキーワードとURLを登録する方式) しかし、ディレクトリ型では、自分が考えたキーワードではページが 見つからないことが多い。
そこで、GoogleはWebロボット(クローラー)による検索システムを構築した。 Webロボットは、定期的に登録されているURLをアクセスし、 そのページ内の単語を分割しURLと共にデータベースに追加する。 さらに、ページ内にURLが含まれていると、そのURLの先で、 同様の処理を再帰的に繰り返す。
これにより、巨大なデータベースが構築されているが、これを少ない コンピュータで実現すると、処理速度が足りず、3秒ルール/5秒ルール (Web利用者は次のページ表示が3秒を越えると、次に閲覧してくれない) これを処理するには負荷分散が重要となる。
一般的に、Webシステムを構築する場合には、 1段:Webサーバ、2段:動的ページ言語、3段:データベースとなる場合も 多い。この場合、OS=Linux,Web=Apache,DB=MySQL,動的ページ生成言語=PHPの組合せで、 LAMP構成とする場合も多い。
一方で、大量のデータを処理するDBでは、フロントエンド,スレーブDB,マスタDBのWebシステムの3段スキーマ構成となることも多い。
データベースシステム
データベースには、ファイル内のデータを扱うためのライブラリの、 BerkleyDBといった場合もあるが、複雑なデータの問い合わせを実現する 場合には、リレーショナル・データベース(RDB)を用いる。 RDBでは、データをすべて表形式であらわし、SQLというデータベース 問い合わせ言語でデータを扱う。 また、問い合わせは、ネットワーク越しに実現可能であり、こういった RDBで有名なものとして、Oracle , MySQL , PostgreSQL などがある。 単一コンピュータ内でのデータベースには、SQLite などがある。
データベースシステムと呼ばれるには、ACID特性が重要となる。
- A: 原子性 (Atomicity) – 処理はすべて実行するか / しない のどちらか。
- C: 一貫性 (Consistency) – 整合性とも呼ばれ、与えられたデータのルールを常に満たすこと。
- I: 独立性 (Isolation) – 処理順序が違っても結果が変わらない。それぞれの処理が独立している。
- D: 永続性 (Durability) – データが失われることがない(故障でデータが無くならないとか)
しかし、RDBでは複雑なデータの問い合わせはできるが、 大量のデータ処理のシステムでは、フロントエンドDB,スレーブDB,マスタDB の同期が問題となる。この複雑さへの対応として、最近は NoSQL が 注目されている。
データベースが無かったら
これらのデータベースが無かったら、どのようなプログラムを作る 必要があるのか?
情報構造論ではC言語でデータベースっぽいことをしていたが、 大量のデータを永続的に扱うのであれば、ファイルへのデータの読み書き 修正ができるプログラムが必要となる。
こういったデータをファイルで扱う場合には、1件のデータ長が途中で 変化すると、N番目のデータは何処?といった現象が発生する。 このため、簡単なデータベースを自力で書くには、1件あたりのデータ量を 固定し、lseek() , fwrite() , fread() などの 関数でランダムアクセスのプログラムを書く必要がある。
また、データの読み書きが複数同時発生する場合には、排他処理も 重要となる。例えば、銀行での預け金10万の時、3万入金と、2万引落としが 同時に発生したらどうなるか? 最悪なケースでは、 (1)入金処理で、残金10万を読み出し、 (2)引落し処理で、残金10万を読み出し、 (3)入金処理で10万に+3万で、13万円を書き込み、 (4)引落し処理で、残金10万-2万で、8万円を書き込み。 で、本来なら11万になるべき結果が、8万になるかもしれない。
さらに、コンピュータといってもハードディスクの故障などは発生する。 障害が発生してもデータの一貫性を保つためには、バックアップや 障害対応が重要となる。
hogeはメタ構文変数
成績締め切りも近い中、レポートの出ない学生さんに確認したら、メールで送ったそうな。届いてないので確認してもらったら、前記事の福井高専のドメイン名の説明で、hoge@fukui-nct.ac.jp と書いてあったのを私の正式メールアドレスと勘違いしたらしい。
“hoge” は、正式にはメタ構文変数というけど、人に例として説明するときの適当につける名前(例えば太郎とか花子)。英語圏では、foo , bar , baz を使い、私もプログラム例では、foo() を使う。
んで hoge は、日本で使われるメタ構文変数で、hoge, fuga, piyo かな。
由来は、諸説色々あるけど個人的には、バラエティ番組の「ぴったしカンカン」で、司会者の久米宏が伏せ文字的に「◯◯は…」みたいなのを「hogehogeは…」みたいに話したのが元だと思ってる。
piyo は「めぞん一刻」の大家さんのエプロンだろうな。
福井高専のドメイン名
そろそろ前期期末の成績締め切り。学生さんがレポート課題提出で先生にメールを送ることも多いが、メールアドレスの書き間違いでメールがエラーになって届かないトラブルがちらほら。
メールアドレスをどう書き間違えているのか確認すると、hoge@fukui-nct–ac.jp と書いていたりする。高専機構のドメイン名は、hoge@fukui.kosen-ac.jp で、ac の前がハイフンに間違えてるんだろうな。
まずは結論
高専機構(福井)のメールアドレスは、hoge@fukui.kosen–ac.jp です。
福井高専のメールアドレスは、hoge@fukui–nct.ac.jp です。
ということで、以下解説。
ドメイン名の一般ルール
ちなみに、日本のドメイン名は古くは、組織ドメイン.種別ドメイン.国ドメイン の形式。
組織ドメイン=fukui-nct , 種別ドメイン=ac(教育機関) , 国ドメイン=jp(日本)
種別ドメインには、.co.jp(会社) , .ne.jp(ネットワークサービス) , .or.jp(団体) , .go.jp(政府機関) といったものがあるが、企業のサービスだと、.co.jp なのか .ne.jp なのか曖昧だったりするので、最近は省略したものを申請できるようになっている。
国ドメインは、アメリカはネットを作った所なので、国ドメインは省略され、.us(アメリカ) を使うことはめったに無い。一方、国ドメインも、.jp(日本) , .uk(イギリス) , .ch(中国) とかあっても、世界中に拠点を持つ企業では、.jp なのかよくわからないので、国ドメインを持たない種別ドメイン .com (企業) を取得することも多い。
高専機構のドメイン名
日本では最近様々な形式の学校が出てきたため、.ac.jp のドメインを取る時の審査は厳しくなっている。
このため、高専機構では、kosen.ac.jp を取得したいが審査が通らず、しかたがないので kosen–ac.jp を取得している。
組織ドメイン=kosen-ac , 種別ドメイン=なし , 国ドメイン=jp(日本)
ちなみに、”-ac.jp” といった変則的なドメイン名は、教育機関を偽装したドメイン名と勘違いされやすく、kosen-ac.jp のドメイン名を見て「怪しい…」と思う人も多い。
福井高専のドメイン名
一方、高専機構ができた後の福井高専の英語の正式名称は、“National Institute of Technology, Fukui College” であり、福井高専のドメイン名としては、本来 “nit-fukui.ac.jp” を取得したい。
組織ドメインの綴りのルールは無いので、大学でも 大学名-u.ac.jp だったり u-大学名.ac.jp など色々あるが、最近は後者が主流となっている。(福井大学も以前は、fukui-u.ac.jp だったが、最近は u-fukui.ac.jp に変更されている)
しかし、.ac.jp の審査が厳しく、高専機構の1組織っぽい nit-fukui.ac.jp は審査が通らない可能性が非常に高く、どの高専も以前のドメイン名をそのまま使用しているのが現状である。
CTF講座・K-SEC第3ブロック学生向け講習会に参加
高専機構の情報セキュリティ人材育成プロジェクトの一環として、岐阜大学サテライトキャンパス(岐阜高専主幹)にて8/28(水)に開催された、CTF講座・K-SEC第3ブロック学生向け講習会に3EI学生1名が参加しました。
CTFとは
CTFとは、Capture The Flags という、情報セキュリティの知識を使ってクイズを解く競技です。
例えば、簡単なものでは、
- PGS{fnzcyr} からフラグを見つけよ。# rot13暗号化
- SQLインジェクションでデータ漏洩が発生するWebシステムが用意されていて、SQLインジェクションが発生するようなデータを入力させて情報を見る。
といった問題があります。複雑な問題では、
- C言語で生成された機械語があって、通常では何も表示されないけど、逆アセンブルして条件判断の一部をバイパスさせて、データを表示させる。
といった、OSや機械語の知識が要求されるものもあります。
初心者には大変だったかな
今回、4年はインターンシップなどで参加者があつまらず、初心者の3年の学生さんに参加してもらいました。CTFの初心者向け講習会ということで、基礎的演習もあるかと思いましたが、いきなりの簡易版CTF大会となりました。知識が不足していて、苦労していましたが基礎的問題をいくつか解けていたようです。
最後に、講習会の修了証をもらいました。