永続性

情報システム概論 I 

                               システム情報工学研究科CS専攻、電子・情報工学系
                               新城 靖
                               <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.coins.tsukuba.ac.jp/~yas/coins/compsys1-2006/2007-02-19
あるいは、次のページから手繰っていくこともできます。
http://www.coins.tsukuba.ac.jp/~yas/
http://www.cs.tsukuba.ac.jp/~yas/

■復習

オペレーティング・システムのカーネルの役割
２種類の記憶のためのハードウェア
- メインメモリ
- ハードディスク

プログラミング言語で記述しているのは、主記憶（メインメモリ）の内容を書き換えること。内容を書き換えられるのは、主記憶だけ。

■記憶のためのハードウェア

◆記憶の持続性からみた時の記憶ハードウェア分類

速度、容量以外の性質。

揮発的 (volatile): 電源を切ると消えてしまう。メインメモリとして使われるRAM(Random Access Memory)など。
永続的 (persistent)、不揮発的 (non volatile): 電源を切っても残っている。ハード・ディスク、{CD,DVD}-{ROM,R,RW,RAM}、USBフラッシュメモリ・ディスクなど。

仮想記憶は、揮発的なメモリの「容量」を事実上拡大したもの。キャッシュ・メモリは、RAMの「速度」を、高速化したもの。

永続的なメモリを仮想化して使いやすくしたものが、ファイルやデータベース。

■ファイル

ハードディスク、CD-ROM、USB フラッシュメモリ等の永続的な記憶媒体をオペレーティング・システムの働きにより仮想化して使いやすくしたもの。

バイト単位でデータを保存できる。
物理媒体に依存しない、統一的な扱いができる。
情報に名前がつけらる。
情報に対してアクセス制御が行える。

ファイルには、名前がある。名前を保存いるための特殊なファイルを、「ディレクトリ(directory)」という。「フォルダ(folder)」ということもある。

もしも、ファイルに名前がつけられなかったら・・・・。

◆ファイルがどう見えるか

シェルから。Unix ls コマンド、MacOSX Finder、Windows Explore
プログラムから。ストリームとランダムアクセス。

◆ストリーム

もともとは、流れの意味。通信でよくつかう。

TCP層は、ストリーム転送サービスを提供する。
動画像のストリーミング転送では、データ全体の転送を待たずに再生を開始できる。データを保存させないで再生できる。

プログラムから見た時、ファイルを先頭のバイトから順にアクセスする方法がある。

Unix のシステムコール。read(), write() 。
C 言語のライブラリ関数。fread(), fwrite(), fgets(), getchar(), fprintf().

FOPEN(3)                 BSD Library Functions Manual                 FOPEN(3)

NAME
     fopen, fdopen, freopen -- stream open functions

LIBRARY
     Standard C Library (libc, -lc)

SYNOPSIS
     #include <stdio.h>

     FILE *
     fopen(const char * restrict path, const char * restrict mode);

     FILE *
     fdopen(int fildes, const char *mode);

     FILE *
     freopen(const char *path, const char *mode, FILE *stream);

DESCRIPTION
     The fopen() function opens the file whose name is the string pointed to
     by path and associates a stream with it.

なぜ、先頭から順にアクセスするのか。

磁気テープ、紙テープのように、先頭から順にしかアクセスできない記憶媒体があった。
人間（プログラムを書く人）にとって、わかりやすい。
通信との融合が可能。Unix のパイプとファイルを統一的に扱える。

ストリームといっても、早送り、巻戻しくらいはできるものもある。fseek(), lseek()。

◆ランダムアクセス

ハードディスクは、セクタの集まり。１セクタは、512バイト程度の大きさ。先頭から順ではなくても、セクタの番号を指定すれば、どんな順番でもアクセスできる。（アクセスするのに、３つの番号（面の番号、シリンダ番号、シリンダ内のセクタ番号）を個別に指定する必要があるディスクもあった。）

ハードディスク上に作られたファイルは、（テープ上に作られたファイルと違って）、先頭から順にアクセスだけでなく、メインメモリと同様に、任意の順番に配列のようにアクセスすることができる。

API

pread(), pwrite() システムコール
mmap() システムコール
(fseek() ライブラリ関数, lseek() システムコールを使う)

■プログラミング言語から見た永続性

基本的には、プログラミング言語は、メインメモリ（揮発的なメモリ）しかあつかえない。永続性なメモリを扱いたい時には、ファイル入出力を通じて扱うことになる。

◆配列

プログラミング言語で、メインメモリを抽象化したもの。連続した番地におかれた一様なデータ。

もの	指すもの	内容
メインメモリ	番地（数）	バイト単位
配列	添字(index)（数）	任意のデータ単位

◆連想配列(associative array)

添字として、（文字列など）数以外のものが使える。数でも、連続ではなくて、粗(sparse)なものが使える。

例：Rubyの連想配列。「{}」で空の連想配列が作られる。その後は、普通の配列と同様に代入できる。 [ruby-assoc.rb]

#!/usr/bin/ruby

aa = {};
aa["apple"] = 100;
aa["orange"] = 120;
printf("apple == %d\n", aa["apple"] );
printf("orange == %d\n", aa["orange"] );

実行例:

% ./ruby-assoc.rb 
apple == 100
orange == 120
%

連想配列のことを、プログラミング言語によっては、ハッシュ表(Hash table) ということもある。

キー (key): 表を検索する時に使うもの。配列の添字相当。
値 (value): 検索の結果得られるもの。

連想配列には含まれていないデータを検索すると、「見つからない」という結果がかえってくる。

◆連想メモリ

ハードウェアでも、（番地を入れたら値が出てくるのではなく）値を入れると別の値が出てくる少容量のメモリ(連想メモリ)が使われる。

CPU のキャッシュ
MMU のアドレス変換。(この講義では話をしていない。)

◆ファイルを連想配列として考える

ファイルには名前がある。ファイル名を入れると、内容が得られる連想配列として考えることができる。

◆変数の寿命とスコープ

プログラミング言語の変数には、スコープと寿命がある。

スコープ: 空間的な概念。プログラムの字面上、どの範囲から使えるか。プログラムで、スコープにない変数をアクセスするとコンパイル時にエラーになる。
寿命: 時間的な概念。「いつ」、その変数がアクセス可能になり、「いつ」、アクセスできなくなるのか。実行時のタイミング。無効になった変数を無理やり使うと、何が起るかわからない。（Ｃ言語では、ポインタを通じて、無効になった変数をアクセスできてしまうことがある。）

int x;

f()
{
    int y ;
    static int z ;
}

種類	スコープ	寿命
外部変数	全プログラム	プログラムの実行開始から終了まで
普通の局所変数	関数内	その関数の実行中とそこから別の関数を呼んでいる間
staticな局所変数	関数内	プログラムの実行開始から終了まで
static変数(関数の外に定義)	同一ファイル内	プログラムの実行開始から終了まで
(C言語にはない)	(いろいろ)	プログラムの終了後も残る

◆永続的な変数

普通のプログラミング言語で記述できるのは、寿命がいくら長くても、プログラムの実行開始から終了まで。

プログラムの実行開始前にも有効で、終了後にも有効な変数を考えてみる。これを永続的な変数という。

プログラミング言語で永続的な変数を支援しているものがある。

オブジェクト指向データベースといっしょに使うオブジェクト指向言語
Perl tie

一般の言語からは、ライブラリ関数で「永続的なハッシュ表（連想配列）」として扱うことが多い。

◆永続的なハッシュ表を扱うライブラリ

Berkeley DB (dbopen(3), btree(3), hash(3), recno(3) )
DBM, NDBM, ODBM, GDBM, SDBM

DB は、Database の略だが、情報学類でこれらをデータベースと呼ぶと怒られる。固有名詞として扱うと安全。

◆永続的なハッシュ表を扱うライブラリ(Ruby DBM)

Ruby では、DBM というライブラリを使うと、 NDBM (Berkeley DB) をハッシュ表のように扱える。ただし、キーもデータも文字列。(文字列を入れると文字列がかえって来る。)

保存するプログラム [ruby-dbm-store.rb]

#!/usr/local3/bin/ruby

require 'dbm';
db = DBM::open("fruits",0666);
db["apple"] = 100;
db["orange"] = 120;
db.close();

保存されたデータを利用するプログラム [ruby-dbm-print.rb]

#!/usr/local3/bin/ruby

require 'dbm';
db = DBM::open("fruits");
printf("%d\n", db["apple"] );
db.close();

実行例:

% ls fruits.db 
ls: fruits.db: No such file or directory
% ./ruby-dbm-store.rb 
% ls fruits.db 
fruits.db
% file fruits.db 
fruits.db: Berkeley DB (Hash, version 7, native byte-order)
% ./ruby-dbm-print.rb  
100
%

■データベース

複数の応用目的で共有を意図して組織的かつ永続的に格納されたデータ群。

ファイルと同様に、永続的な記憶媒体を仮想化して使いやすくしたもの。

ファイルと違い

プログラムから独立している(データ独立性)
整合性(integrity)を保ったデータしか入っていない
複数のプログラムから同時アクセスにつよい機能がある(トランザクション)
障害回復の機能がある(トランザクション)

データベースは、データベース管理システム(DBMS, DataBase Management System)の働きにより作られる。

◆データモデル

DBMSが提供する、対象データとそれに対する操作を規定した共通の枠組み。例

関係データモデル
階層データモデル
ネットワーク型データモデル

「関係」とは、２次元の表。関係データモデルでは、表の集合としてデータベースを構築する。
サークル
サークル名部屋番号電話番号

テニス 101 1011

サッカー 203 4423

社員
社員番号氏名基本給与住所

001 筑波太郎 400 つくば市×××

002 土浦次郎 450 土浦市△△△

003 水戸三郎 450 水戸市○○○

所属
サークル名社員番号役職

テニス 001 代表

テニス 002 会計

サッカー 001 一般部員

サッカー 003 幹事

サークル
サークル名	部屋番号	電話番号
テニス	101	1011
サッカー	203	4423

社員
社員番号	氏名	基本給与	住所
001	筑波太郎	400	つくば市×××
002	土浦次郎	450	土浦市△△△
003	水戸三郎	450	水戸市○○○

所属
サークル名	社員番号	役職
テニス	001	代表
テニス	002	会計
サッカー	001	一般部員
サッカー	003	幹事

◆関係データベースに対する操作

和 (Union)
差 (Diff). R-S=={t|t∈R ∧ ￢t∈S}
直積
射影
選択
結合
共通部分
商

◆問い合わせ言語

データベースに対して、一般ユーザが操作しやすいように設計された言語。

◆SQL

関係データベースに対する、標準化された問い合わせ言語。

集合ではなくて、重複も許す（マルチ集合）
データの順序に意味がある

例：データベースの定義(create table)、データの挿入(insert)、検索(select)

% sqlite3 company1.db 
SQLite version 3.1.3
Enter ".help" for instructions
sqlite> create table circles( name char(20), room char(3), phone char(4));
sqlite> insert into circles values('ukouken', '123', '4444');
sqlite> select * from circles where room='123';
ukouken|123|4444
sqlite> .quit
% ls -l company1.db  
-rw-r--r--   1 yas  prof  2048 Feb 15 16:36 company1.db
%

挿入したデータは、消す(delete)まで使える。

% sqlite3 company1.db  
SQLite version 3.1.3
Enter ".help" for instructions
sqlite> select * from circles where phone='4444';
ukouken|123|4444
sqlite> .quit
%

■並行プログラミング

複数のプログラムが共有しているデータを同時に操作しようとしたら何がおきるのか。

複数のプロセスが同じファイルを開く
複数のプロセスが同じデータベースの表を操作する
複数のスレッドが同じ変数を操作する

スレッドとは、１つのプログラムの中に含まれる並列処理の単位。スレッドの数だけ、複数の関数が（論理的に）同時に実行される。

◆相互排除

相互排除(mutual exclusion): ある資源（ファイル、変数、表など）をアクセスできるプロセス（またはスレッド）の数を多くても１つにする。
際どい部分(critical section) (クリティカルセクション): プログラムの字面上、相互排除が必要な部分

◆ロック

もっとも基本的な命令は、lock と unlock

lock();
  相互排除したい部分。
unlock();

あるファイルや関係データベースの表を、１人で、かつ、一度に１つのプログラムでしか操作しないなら、ロックは不用。それ以外の時には、必要。

◆デッドロック

複数の資源を相互排除した時に、いくつかの条件が重なるとロックを保持したまま先に進めないプログラムが出てきてしまう。

◆トランザクションの目的

データベースの整合性を保ちたい。
障害から回復させたい。
相互排除、デッドロックより高いレベルの抽象が欲しい。
ロックよりも楽にプログラムを作りたい。

◆トランザクションの意味

商談は、成立するか、しないか。 all or nothing。

歴史：１９６０年代、テープの時代。失敗したら、巻き戻す(rollback)。

銀行口座間の預金の移動。

口座１から出金
口座２に入金

◆トランザクション・プリミティブ

Begin_Transaction
Commit (End Transaction)
Abort
Read
Write

◆特性(ACID)

Atomic: 外の世界からみると１つ。中間状態が見えない。不可分。
Consistency: 不変量(invariant)を保つ。例：口座間の預金の移動。預金の総額は不変。
Isolated: 並行するトランザクションは、孤立している。直列化可能(serializable)
Durable: Commit すると永続的。

◆直列化可能(serializable)

注意：Javaの serializable とは意味が全く違う。

複数のトランザクションは、並行に実行可能。しかし、その複数のトランザクションの最終結果は、それらを「ある順序」で「逐次的に」実行した時と同じ結果になる。

逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅らせるか、アボートする。

◆トランザクションの例

航空券の乗り継ぎの予約のプログラム

Begin_Transaction();
  reserve("NRT-SFO");
  reserve("SFO-JFK");
Commit();

プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的には、ロックは行われる（ことがある）。

途中の reserve() が失敗したら、トランザクション全体を abort() する。

Last updated: 2007/02/15 17:12:55

Yasushi Shinjo / <yas@is.tsukuba.ac.jp>

永続性

■復習

■目標