図? 普通のロック、読書きロック
xo
並行システム
システム情報工学研究科コンピュータサイエンス専攻、電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2007/2008-01-25
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/sie/
http://www.cs.tsukuba.ac.jp/~yas/
これを実現するものが、「複数読み手単一書き手ロック」、あるいは、
「読み書きロック」。
図? 普通のロック、読書きロック
読むだけでもロックする必要がある。さもないと、読んでいる途中で変化する ことがある。
クライアント・サーバ型の通信。
資料： 谷口 秀夫 (編), 谷口 秀夫, 佐藤一朗, 佐藤 文明, 柴田 義孝, 新城 靖, 横山 和俊 (著): "情報処理学会編集 IT Text 分散処理", オーム社 (2005年9月). ISBN: 4274201333.
第２章 基盤技術 (新城)
ネットワークで接続された複数のコンピュータ上で複数のプロセスを動作させ る。プロセスは、全体として１つの仕事を成し遂げる。
ノード：プロセス、あるいは、コンピュータ
メッセージ：ノード間で交換されるデータ
分散システムでは、次のような集中システムでは普通に使える共有資源が使えない。
信頼性性があるかないか。専門用語では、程度問題（高い低い）ではなく、有 るか無いか。
信頼性がある通信プリミティブを利用した場合、あるプロセスが送信したメッ セージは、途中で失われることはなく、有限時間以内に通信相手のプロセスに 送り届けられる。
分散システムでは、メッセージは、失われることがある。
図? 同期型sendと非同期型send
ほとんどの通信プリミティブは、間接。
直接の例：
問題：直接アドレス指定では、receiveする前にsendされると、どのプロセス にメッセージを送っていいのかわからない。
解決
send,receive それぞれ２種類ある。
非同期の方が、並列性が高い。しかし、、、
2. は、転送完了割り込みで解決可能。プログラミングが難しい。 割り込みよりは、マルチスレッドがよい。
プログラミングの選択
時間切れ(timeout)。同期で使われる。
同期、非同期とは直行しているとも言えるが、普通は同期の場合にはバッファ リングを省略してコピーを減らす。
メールボックスには、しばしば有限のバッファがもうけられる。
バッファがいっぱいだった時にどうするか。 いっぱいの時にだけ送信側をブロックさせる、という方法でいいのか。
通信の分類
グループ通信は、いろいろな分散アルゴリズムでよく使われる。
普通の固定電話の場合、64k bps の帯域保証がなされている。電話を掛ける人 が増えてきたとしても、それが 32k bps に減らされるようなことはない。そ の代りに、電話を掛けようとすると「通話中」というエラーが返り、通信その ものが行えなくなる。
| TCP | IP | UDP | イーサネット | 電話 | 郵便 | |
| send | 非同期 | 非同期 | 非同期 | 非同期 | 非同期 | 非同期 |
| receive | 同期 | (非同期)* | 同期 | (非同期)* | 同期 | 非同期 |
| 信頼性 | あり | なし | なし | なし | あり | なし |
| アドレス指定 | 間接 | 間接 | 間接 | 間接 | 間接 | 直接 |
| 結合 | あり | なし | なし | なし | あり | なし |
| 方向 | 双方向 | 単方向 | 単方向 | 単方向 | 双方向 | 単方向 |
| マルチキャスト | 不可 | 可能 | 可能 | 可能 | 可能 | 不可 |
| 帯域保証 | なし | なし | なし | なし | あり | なし |
図? marshalingとunmarshaling
４個の要素からなる構造体を整列化して送信している。ネットワーク上を流れている時には、整列化された データの先頭にはネットワークのヘッダが付加されている。
rpcgen というスタブ・コンパイラがある。 データ構造を与えると、marshaling の手続きを自動生成する。
SunRPC を使わなくて、XDR だけを使う方法もある。
Ｃ言語で扱える整数
2バイト、または、4バイトの整数をメモリに保存する方法 : メモリの下位番地に上位バイトを置くか下位バイトを置くか
図? バイト・オーダー
| 名前 | 方向 | ビット数 |
| htonl() | ホストからネットワークへ変換 | 32ビット |
| htons() | ホストからネットワークへ変換 | 16ビット |
| ntohl() | ネットワークからホストへ変換 | 32ビット |
| ntohs() | ネットワークからホストへ変換 | 16ビット |
long int hostlong, netlong; hostlong = 0x12345678 ; netlong = htonl( hostlong ); send(conn, &netlong, sizeof(netlong), 0);
思ったほど遅くはない。
注意：sscanf() は、整数をデコードするために使う分には問題ないが、 文字列を受け取るために使うとバッファ・オーバーフローが生じる可能性があるので、 使わない方がよい。
今後 TCP/IP 以外にも様々な通信プロトコルが開発され、Unix で利用できる ように設計されている。TCP/IP で使う時には、煩雑である。
| ドメイン | 型 | プロトコル |
| PF_INET | SOCK_STREAM | TCP(IPv4) |
| PF_INET | SOCK_DGRAM | UDP(IPv4) |
| PF_INET6 | SOCK_STREAM | TCP(IPv6) |
| PF_INET6 | SOCK_DGRAM | UDP(IPv6) |
| PF_UNIX | SOCK_STREAM | 同一ホスト内(UNIXドメイン)のストリーム |
| PF_UNIX | SOCK_DGRAM | 同一ホスト内(UNIXドメイン)のデータグラム |
| PF_NS | SOCK_STREAM | XNS のストリーム(SPP) |
| PF_NS | SOCK_SEQPACKET | XNS の順序付きパケット(IDP) |
| PF_NS | SOCK_RDM | XNSの信頼性のあるデータグラム(SPP) |
| 名前 | 説明 |
| socket() | 通信プロトコルに対応したソケット・オブジェクトを作成する |
| connect() | 結合(conection)を確立させる。サーバのアドレスを固定する。 |
| listen() | サーバ側で接続要求の待ち受けを開始する。 |
| accept() | サーバ側で接続されたソケットを得る。 |
| bind() | ソケットにアドレス(名前)を付ける。 |
| getpeername() | 通信相手のアドレス(名前)を得る。 |
| getsockname() | 自分のアドレス(名前)を得る。 |
| send(), sendto(), sendmsg() | メッセージを送信する。 |
| recv(), recvfrom(), recvmsg() | メッセージを受信する。 |
| shutdown() | 双方向の結合を部分的に切断する。 |
| getsockopt() | オプションの現在の値を取得する。 |
| setsockopt() | オプションを設定する。 |
| select(), poll() | 複数の入出力(通信を含む)を多重化する。 |
| write() | メッセージを送信する。 |
| read() | メッセージを受信する。 |
| close() | ファイル記述子を閉じる。他に参照しているファイル記述子がなければ、ソケット・オブジェクトを削除する。 |
| 名前 | 説明 |
| gethostbyname() | ホスト名から IP アドレスを調べる。 |
| getaddrinfo() | ホスト名から IP アドレスを調べる。IPv6対応。 |
| gethostbyaddr() | IPアドレスからホスト名を調べる。 |
| getnameinfo() | IPアドレスからホスト名を調べる。IPv6対応。 |
| freeaddrinfo() | getaddrinfo(), getnameinfo() で得られた構造体を解放する。 |
TCP/IP では、クラ イアント側とサーバ側でソケット・オブジェクトの作成するクラスが違ってい る。
| クラス名 | 説明 |
|---|---|
| Socket | TCP/IP のクライアント側のソケット |
| ServerSocket | TCP/IP のサーバ側のソケット |
| DatagramSocket | UDP/IP のソケット |
以後、ネットワークか ら文字列を入力するには、InputStreamReader や BufferedReader のオブジェ クトを生成して利用する。
出力側では、Socket クラスのオブジェクトに対して getOutputStream() して、 OutputStream クラスのオブジェクトを得て、 PrintStream オブジェクトを生成して利用できる。
通信を構造化。send()/receive() を直接使うのは、goto (jump) でプログラ ムを書くようなもの。call/if/while で書きたい。
プロセスを２種類に分類する。通信は、次のパタンを繰り返す。
図? 通信のパタンからみたクライアントとサーバの定義
構造化プログラミング：分かりにくいgoto文をつかわないで、わかりやすい goto文だけ使う。
図? サービスの授受によるクライアントとサーバの定義
図? 複数のクライアントによるサーバの共有
以上のように、クライアントとサーバは、いろいろな意味で使われる。これら の意味は、多くの場合、一致しているが、一致していないこともある。
通信を開始するパタンで、コンピュータ、プログラム、人間は、次の２つに分 類される。
図? 能動的なクライアントと受動的なサーバ
例：ＷＷＷサーバは、ＷＷＷクライアントから何か要求が来ない限り、ずっと 黙っている。
コンピュータを使う時には、人間が能動的になり、コンピュータが受動的にな る。
テレビを見ている時には、人間が受動的になり、テレビが能動的になる。
講義形式の授業では、サービスの授受では、教官がサーバで、学生がクライア ントになる。通信の開始の方法では、教官が能動的になり、学生が受動的にな る。
大学以上では、学生は、能動的になることが求められている。
混沌とした通信を 構造化 してわかりやすくしたものが、クライアント・サーバ・モデルである。
サーバあるシステムでは、サーバが落ちるとシステム全体が動作しなくなる。 このように複数の要素から構成されているシステムで、ある要素が故障した時 に、全体が動作しなくなるような場所を、単一障害個所(single point of failure) という。
コンピュータサイエンスでは、古くから、単一障害個所を避けるための研究が 行われてきている。もっとも成功している方法は、サーバを複数用意する方法 である。
サーバがないシステムでは、下手に作るとどの要素が故障してもシステム全体 が止まってしまうことになる。
サーバがないシステムで成功している例はある。
peer は、「対等の仲間」の意味。「通信相手」という意味もある。
検索は、サーバで索引を集めた方が速い。Web 上の検索エンジンなど。
サーバがない方法の利点(特徴)
クライアントが何かサーバにして欲しい時には、do_operation() で、サーバ に要求メッセージを送る。そして、サーバからの応答メッセージを待つ。
サーバは、要求メッセージを受けとると、何か仕事をして、send_reply() で、 クライアントに応答メッセージを返す。そして、再び次の要求メッセージ を待つ。
１つのサーバに複数のクライアントがアクセスすることがある。１つのクライ アントも、複数のサーバに同時にアクセスすることもできる。
図? クライアント・サーバ・モデルに基づく通信で使う３つの命令
例２：３種類（回数）
（＜−＞文化的には、TCP/IP上のテキストベースのプロトコルとは対照。）
RPCでは、別のアドレス空間の間でデータがやり取りされるので、基本的に 「ポインタ」を受け渡しすることはできない。しかし、SunRPC では、ポイン タの先を再帰的に「コピー」する機能がある。
このRPCの３つの命令は、システムコール、または、ライブラリで実現される。 SunRPCには、get_request() に相当する命令が定義されていない。
スタブ(stub) は、プロセス間通信を普通の手続き呼出しと全く同じ形式で行なうことができ るようにするためのプログラム。 もともとは木の切株の意味。
スタブの分類
図? rpcgenによるRPCプログラム開発で利用するファイル
name.x
name_client.c
name_server.c
% rpcgen name.x次の４つのファイルが生成される。![[←]](../icons/screen-return.gif)
name.h
name_clnt.c
name_xdr.c
name_svc.c
ハッシュ表
typedef string key_t<256>;
struct keyvalue_t {
key_t key;
int value ;
};
typedef key_t keyarray_t<>;
program HASHTABLE_PROG {
version HASHTABLE_VERSION {
int PUT(keyvalue_t) = 11 ;
int GETVALUE(key_t) = 12 ;
keyarray_t GETKEYS(void) = 13 ;
} = 1 ;
} = 0x20051001 ;
遠隔手続き呼出しでは、送受信できるデータは基本的には値だけであり、
ポインタを送ることはできない。
SunRPC では、ポインタの先の１要素だけコピーして送る機能がある。SunRPC では、ポインタによる単純なリストや木構造を送ることができる。
双方向リストなど、内部にループを含むものは SunRPC では送ることができな い。また、ポインタで実現された有向非循環グラフを送ると木構造に展開され てしまう。
ローカルの手続き呼出しでは、リンク時に固定される。
クライアントとサーバは１対１ではない。
binding のための命令
/etc/rpc
というファイルに含まれている。
TCP/IPまたはUDP/IPでデータを送るにはポート番号が必要になる。 サーバが動作しているホストには、 portmapper とよばれる特殊な RPC のサーバが動作している。 サーバは起動時に自分の＜プログラム番号, バージョン, プロトコル, ポート番号＞をPortmapper に登録する (pmap_set())。
クライアントは、実際にサーバに接続する前に、Portmapper に＜プ ログラム番号, バージョン, プロトコル＞を送り、 TCP/IPまたはUDP/IPのポート番号を得る(pmap_getport())。最終的には, この ポート番号を使ってメッセージを送る。
Portmapper 自身のポート番号は、111 に固定されている。
図? SunRPC での binding (portmapper)
例: 銀行預金転送。
対策:
ＲＰＣのセマンティクス
親（クライアント）がいない計算を孤児という。
対応方法
孤児が、ロックを持っていたら、孤児を消しただけでは話を終わらない。
例：
無状態サーバ(stateless server) とは、サーバ内部に状態を保持しないようなサーバ。
状態の例
RPCで冪等な操作や無状態サーバを実現すると、クラッシュに強いシステムを 作れる。クライアントは、サーバから応答がない場合、何度要求を再送信して もよい。
例：NFS Version 2
サーバは、ファイルに対する書き込み要求を受け付けると、ディスクへ の書き込みを完了してから応答を返す。 応答が返ってきた要求は、 ディスクへの書き込みが完了したことが保証されている。 この段階でサーバがクラッシュしたとしても、なにも失われない。
しかし、、、重たい。NFS Version 3 では、状態付きのサーバになった。
NFS ( Network File System ) は, Sun Microsystems 社が 開発したネットワーク・ファイル・システムの名前(固有名詞, 商標)。
その他のネットワーク・ファイル・システム(用のプロトコル)
NFSを使うと, ネットワークを通じて別のコンピュータ上のファイルシステム
の一部分を, ローカルディスク上にあるファイルシステムと同じように, 自分
のファイルシステムの木に
マウント(mount)
できる。
図? NFSによるファイルの共有
相互に参照し合える。
表? NFSで使われているRPCの手続き
| 手続き名 | 意味 | 関連するコマンド、 システムコール |
|---|---|---|
| null() | 何もしない | rpcinfo -u hostname nfs コマンド |
| getattr() | 属性の読み出し | ls -l コマンド, stat システムコール , open システムコール |
| setattr() | 属性の設定 | chmod , chown コマンド |
| lookup() | ファイルの検索 | open システムコール |
| readlink() | シンボリックリンクの読み出し | ls -l コマンド, readlink システムコール |
| read() | ファイルの読み出し | read システムコール |
| write() | ファイルの書き込み | write システムコール |
| create() | ファイルの作成 | creat システムコール, open システムコール |
| remove() | ハードリンクの削除 | rm コマンド, unlink システムコール |
| rename() | ファイル名前の変更 | mv コマンド, rename システムコール |
| link() | ハードリンクの作成 | ln コマンド, link システムコール |
| symlink() | シンボリックリンクの作成 | ln -s コマンド, symlink システムコール |
| mkdir() | ディレクトリの作成 | mkdir コマンド |
| rmdir() | ディレクトリの削除 | rmdir コマンド |
| readdir() | ディレクトリの読み出し | ls コマンド |
| statfs() | ファイルシステムの利用状況 | df コマンド, statfs システムコール |
| commit()* | ディスクへの書き込み | fsync システムコール |
| access()* | アクセス権のチェック | access システムコール |
| open()** | ファイルを開く。 | |
| close()** | ファイルを閉じる。 | |
| lock()** | ファイルのロック。 | |
| renew()** | ファイルのロックの更新。 | |
| compound()** | 複合手続き。複数の手続きをまとめて実行する。 |
NFS でファイルやディレクトリを区別するための識別子。32バイト。
const NFS_FHSIZE = 32;
...
/*
* File access handle
*/
struct nfs_fh {
opaque data[NFS_FHSIZE];
};
一番最初のNFSファイル・ハンドルをどうやって入手するか。
| 手続き名 | 意味 | 関連するコマンド、 システムコール |
|---|---|---|
| null() | 何もしない | rpcinfo -u hostname mount コマンド |
| mnt() | NFSファイルハンドルを返す | mount コマンド |
| dump() | マウント一覧表 | showmount hostname コマンド |
| umnt() | アンマウント | umount コマンド |
| umntall() | 全アンマウント | umount -h hostname コマンド |
| export() | アクセス可能なディレクトリのリストを返す |
2.2.5. Look Up File Name
diropres
NFSPROC_LOOKUP(diropargs) = 4;
If the reply "status" is NFS_OK, then the reply "file" and reply
"attributes" are the file handle and attributes for the file "name"
in the directory given by "dir" in the argument.
2.3.10. diropargs
struct diropargs {
fhandle dir;
filename name;
};
The "diropargs" structure is used in directory operations. The
"fhandle" "dir" is the directory in which to find the file "name".
A directory operation is one in which the directory is affected.
2.3.11. diropres
union diropres switch (stat status) {
case NFS_OK:
struct {
fhandle file;
fattr attributes;
} diropok;
default:
void;
};
The results of a directory operation are returned in a "diropres"
structure. If the call succeeded, a new file handle "file" and
the "attributes" associated with that file are returned along with
the "status".
2.2.7. Read From File
struct readargs {
fhandle file;
unsigned offset;
unsigned count;
unsigned totalcount;
};
union readres switch (stat status) {
case NFS_OK:
fattr attributes;
nfsdata data;
default:
void;
};
readres
NFSPROC_READ(readargs) = 6;
Returns up to "count" bytes of "data" from the file given by "file",
starting at "offset" bytes from the beginning of the file. The first
byte of the file is at offset zero. The file attributes after the
read takes place are returned in "attributes".
Notes: The argument "totalcount" is unused, and is removed in the
next protocol revision.
2.2.9. Write to File
struct writeargs {
fhandle file;
unsigned beginoffset;
unsigned offset;
unsigned totalcount;
nfsdata data;
};
attrstat
NFSPROC_WRITE(writeargs) = 8;
Writes "data" beginning "offset" bytes from the beginning of "file".
The first byte of the file is at offset zero. If the reply "status"
is NFS_OK, then the reply "attributes" contains the attributes of the
file after the write has completed. The write operation is atomic.
Data from this "WRITE" will not be mixed with data from another
client's "WRITE".
Notes: The arguments "beginoffset" and "totalcount" are ignored and
are removed in the next protocol revision.
RPC のようにコネクションが作られない通信サービスを使う時に冪等や無状態 といった性質を実現する時に必要になる技術。
例：NFSでのディレクトリの読み込み手続き nfsproc_readdir() で、１回の RPC で全部のデータを返せないことが起きる。 ディレクトリのどの位置まで読み込んだかを 示す中間状態を クッキー(cookie) という形でクライアントに返す。
クライアントは、次の RPC の呼び出しで、 前回受けとった応答の中のクッキーを、サーバへの要求に含めて送す。
const NFS_COOKIESIZE = 4; typedef opaque nfscookie[NFS_COOKIESIZE];
2.2.17. Read From Directory
struct readdirargs {
fhandle dir;
nfscookie cookie;
unsigned count;
};
struct entry {
unsigned fileid;
filename name;
nfscookie cookie;
entry *nextentry;
};
union readdirres switch (stat status) {
case NFS_OK:
struct {
entry *entries;
bool eof;
} readdirok;
default:
void;
};
readdirres
NFSPROC_READDIR (readdirargs) = 16;
Returns a variable number of directory entries, with a total size of
up to "count" bytes, from the directory given by "dir". If the
returned value of "status" is NFS_OK, then it is followed by a
variable number of "entry"s. Each "entry" contains a "fileid" which
consists of a unique number to identify the file within a filesystem,
the "name" of the file, and a "cookie" which is an opaque pointer to
the next entry in the directory. The cookie is used in the next
READDIR call to get more entries starting at a given point in the
directory. The special cookie zero (all bits zero) can be used to
get the entries starting at the beginning of the directory. The
"fileid" field should be the same number as the "fileid" in the the
attributes of the file. (See section "2.3.5. fattr" under "Basic
Data Types".) The "eof" flag has a value of TRUE if there are no
more entries in the directory.
nfsproc_readdir() で、１回目と２回目の RPC の間にディレクトリの内容が 更新された場合、どのような結果になるのか不明。
HTTP では、 TCP/IP というコネクションが作られる通信サービスが使われいるが、 １ページ１ページを転送する度にコネクションを切っているので、 複数ページ のアクセスの時にはコネクションが作られない通信サービスを使っているのと 論理的に同じ。
途中経過を保存したい時：
4. EXAMPLES
4.1 Example 1
Most detail of request and response headers has been omitted. Assume
the user agent has no stored cookies.
1. User Agent -> Server
POST /acme/login HTTP/1.1
[form data]
User identifies self via a form.
2. Server -> User Agent
HTTP/1.1 200 OK
Set-Cookie2: Customer="WILE_E_COYOTE"; Version="1"; Path="/acme"
Cookie reflects user's identity.
3. User Agent -> Server
POST /acme/pickitem HTTP/1.1
Cookie: $Version="1"; Customer="WILE_E_COYOTE"; $Path="/acme"
[form data]
User selects an item for "shopping basket".
4. Server -> User Agent
HTTP/1.1 200 OK
Set-Cookie2: Part_Number="Rocket_Launcher_0001"; Version="1";
Path="/acme"
Shopping basket contains an item.
5. User Agent -> Server
POST /acme/shipping HTTP/1.1
Cookie: $Version="1";
Customer="WILE_E_COYOTE"; $Path="/acme";
Part_Number="Rocket_Launcher_0001"; $Path="/acme"
[form data]
User selects shipping method from form.
6. Server -> User Agent
HTTP/1.1 200 OK
Set-Cookie2: Shipping="FedEx"; Version="1"; Path="/acme"
New cookie reflects shipping method.
7. User Agent -> Server
POST /acme/process HTTP/1.1
Cookie: $Version="1";
Customer="WILE_E_COYOTE"; $Path="/acme";
Part_Number="Rocket_Launcher_0001"; $Path="/acme";
Shipping="FedEx"; $Path="/acme"
[form data]
User chooses to process order.
8. Server -> User Agent
HTTP/1.1 200 OK
Transaction is complete.
The user agent makes a series of requests on the origin server, after
each of which it receives a new cookie. All the cookies have the
same Path attribute and (default) domain. Because the request-URIs
all path-match /acme, the Path attribute of each cookie, each request
contains all the cookies received so far.
普通のＷＷＷサーバでは、要求を送ってきたコンピュータのＩＰアドレスを記 録しているので、コンピュータ単位でのアクセス状況を記録することはできる が、個人を特定することはできない。
クッキーを利用することにより、コンピュータではなくどの個人がアクセスし てきたかを記録することができる。
クッキーから電子メールのアドレスや氏名まで調べることはできない。 しかし、インターネットをサーフしている間にどこかでそれを打ち込んだが最 後、クッキーと電子メール・アドレスや氏名との対応が記録されてしまう危険 性がある。
参考
RFC2965 HTTP State Management Mechanism
Netscape社によるＷＷＷにおけるクッキー実現の案
http://wp.netscape.com/newsref/std/cookie_spec.html
NFS非同期入出力デーモン
(
nfsiod (local NFS asynchronous I/O Daemon)
または
biod (asynchronous Block I/O Daemon)
)
は、NFSのクライアントホスト上で動き、NFSの非同期的な入出力を行う。
lockd
lockd は、受け取った要求をサーバ上の lockd に転送する。
サーバ・ホスト上の lockd は、クライアントの lockd から受け取っ
た要求をシステム・コールでカーネルに伝える。
statd
lockd は、クライアント・ホスト上の statd に問い合わせて、
クライアント・ホストがクラッシュしていないか調べる。
クライアント・ホストがクラッシュしたら、
そのクライアントから受け取っていたロック要求を解除する。
lockd には、当初からかなりバグが多かった。
初期の statd には、バッファ・オーバーフローのバグがあった。
commit() という手続きが追加。
それまでに行われた書き込みをディスクに行うように指示できる。
(NFS v2 では、write で必ずディスクに書き込む。)