並行システム
システム情報系情報工学域,
システム情報工学研究科コンピュータサイエンス専攻
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2011/2011-12-22
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/
ネットワークで接続された複数のコンピュータ上で複数のプロセスを動作させ る。プロセスは、全体として１つの仕事を成し遂げる。
ノード：プロセス、あるいは、コンピュータ
メッセージ：ノード間で交換されるデータ
分散システムでは、次のような集中システムでは普通に使える共有資源が使えない。
信頼性性があるかないか。専門用語では、程度問題（高い低い）ではなく、有 るか無いか。
信頼性がある通信プリミティブを利用した場合、あるプロセスが送信したメッ セージは、途中で失われることはなく、有限時間以内に通信相手のプロセスに 送り届けられる。
分散システムでは、メッセージは、失われることがある。
図? 結合が作られる通信プリミティブと結合が作られない通信プリミティブ
着信側
make_port(); // 受付端の登録。
accept(); // 実際の受付。connect() と対応。
receive();
send();
receive();
send();
close(); // 接続の切断。
発信側
connect(); // 接続要求。accept() と対応。
send();
receive();
send();
receive();
close(); // 接続の切断。
プロセスＡ
receive();
send();
receive();
send();
プロセスＢ
send();
receive();
send();
receive();
ほとんどの通信プリミティブは、間接。
直接の例：
問題：直接アドレス指定では、receiveする前にsendされると、どのプロセス にメッセージを送っていいのかわからない。
解決
send,receive それぞれ２種類ある。
非同期の方が、並列性が高い。しかし、、、
2. は、転送完了割り込みで解決可能。プログラミングが難しい。 割り込みよりは、マルチスレッドがよい。
プログラミングの選択
時間切れ(timeout)。同期で使われる。
同期、非同期とは直行しているとも言えるが、普通は同期の場合にはバッファ リングを省略してコピーを減らす。
メールボックスには、しばしば有限のバッファがもうけられる。
バッファがいっぱいだった時にどうするか。 いっぱいの時にだけ送信側をブロックさせる、という方法でいいのか。
普通の固定電話の場合、64k bps の帯域保証がなされている。電話を掛ける人 が増えてきたとしても、それが 32k bps に減らされるようなことはない。そ の代りに、電話を掛けようとすると「通話中」というエラーが返り、通信その ものが行えなくなる。
| TCP | IP | UDP | イーサネット | 電話 | 郵便 | |
| send | 非同期 | 非同期 | 非同期 | 非同期 | 非同期 | 非同期 |
| receive | 同期 | (非同期)* | 同期 | (非同期)* | 同期 | 非同期 |
| 信頼性 | あり | なし | なし | なし | あり | なし |
| アドレス指定 | 間接 | 間接 | 間接 | 間接 | 間接 | 直接 |
| 結合 | あり | なし | なし | なし | あり | なし |
| 方向 | 双方向 | 単方向 | 単方向 | 単方向 | 双方向 | 単方向 |
| マルチキャスト | 不可 | 可能 | 可能 | 可能 | 可能 | 不可 |
| 帯域保証 | なし | なし | なし | なし | あり | なし |
図? marshalingとunmarshaling
４個の要素からなる構造体を整列化して送信している。ネットワーク上を流れている時には、整列化された データの先頭にはネットワークのヘッダが付加されている。
Ｃ言語で扱える整数
2バイト、または、4バイトの整数をメモリに保存する方法 : メモリの下位番地に上位バイトを置くか下位バイトを置くか
図? バイト・オーダー
| 名前 | 方向 | ビット数 |
| uint32_t htonl(uint32_t hostlong) | ホストからネットワークへ変換 | 32ビット |
| uint16_t htons(uint16_t hostshort) | ホストからネットワークへ変換 | 16ビット |
| uint32_t ntohl(uint32_t netlong) | ネットワークからホストへ変換 | 32ビット |
| uint16_t ntohs(uint16_t netshort) | ネットワークからホストへ変換 | 16ビット |
unsigned long int hostlong, netlong; hostlong = 0x12345678 ; netlong = htonl( hostlong ); send(conn, &netlong, sizeof(netlong), 0);
送信側:
char buf[BUFSIZE];
hostlong = 0x12345678 ;
snprintf(buf,BUFSIZE,"%d\n",hostlong );
send(conn, buf, strlen(buf), 0);
思ったほど遅くはない。
注意：sscanf() は、整数をデコードするために使う分には問題ないが、 文字列を受け取るために使うとバッファ・オーバーフローが生じる可能性があるので、 使わない方がよい。
rpcgen というスタブ・コンパイラがある。 データ構造を与えると、marshaling を行う手続きを自動生成する。
SunRPC を使わなくて、XDR だけを使う方法もある。
通信を構造化。send()/receive() を直接使うのは、goto (jump) でプログラ ムを書くようなもの。call/if/while で書きたい。
プロセスを２種類に分類する。通信は、次のパタンを繰り返す。
図? 通信のパタンからみたクライアントとサーバの定義
構造化プログラミング：分かりにくいgoto文をつかわないで、わかりやすい goto文だけ使う。
図? サービスの授受によるクライアントとサーバの定義
図? 複数のクライアントによるサーバの共有
以上のように、クライアントとサーバは、いろいろな意味で使われる。これら の意味は、多くの場合、一致しているが、一致していないこともある。
通信を開始するパタンで、コンピュータ、プログラム、人間は、次の２つに分 類される。
図? 能動的なクライアントと受動的なサーバ
例：ＷＷＷサーバは、ＷＷＷクライアントから何か要求が来ない限り、ずっと 黙っている。
コンピュータを使う時には、人間が能動的になり、コンピュータが受動的にな る。
テレビを見ている時には、人間が受動的になり、テレビが能動的になる。
講義形式の授業では、サービスの授受では、教官がサーバで、学生がクライア ントになる。通信の開始の方法では、教官が能動的になり、学生が受動的にな る。
大学以上では、学生は、能動的になることが求められている。
混沌とした通信を 構造化 してわかりやすくしたものが、クライアント・サーバ・モデルである。
サーバあるシステムでは、サーバが落ちるとシステム全体が動作しなくなる。 このように複数の要素から構成されているシステムで、ある要素が故障した時 に、全体が動作しなくなるような場所を、単一障害個所(single point of failure) という。
コンピュータサイエンスでは、古くから、単一障害個所を避けるための研究が 行われてきている。もっとも成功している方法は、サーバを複数用意する方法 である。
サーバがないシステムでは、下手に作るとどの要素が故障してもシステム全体 が止まってしまうことになる。
サーバがないシステムで成功している例はある。
peer は、「対等の仲間」の意味。「通信相手」という意味もある。
検索は、サーバで索引を集めた方が速い。Web 上の検索エンジンなど。
サーバがない方法の利点(特徴)
今後 TCP/IP 以外にも様々な通信プロトコルが開発され、Unix で利用できる ように設計されている。TCP/IP で使う時には、煩雑である。
int socket = socket(int domain, int type, int protocol)
主に domain と type で利用するプロトコルを指定する。
最後の引数 protocol は、普段は 0 を指定する。
| ドメイン(domain) | 型(type) | プロトコル(protocol) |
| 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_acc_port( int portno ) (サーバ側)
int tcp_connect( char *server, int portno ) (クライアント側)
accept() をそのまま使う。
accept() は、１つのクライアントから接続要求を受け付ける。
第1引数の socket は、tcp_acc_port() で作成したソケットを渡す。
TCP/IP では、クラ イアント側とサーバ側でソケット・オブジェクトの作成するクラスが違ってい る。
| クラス名 | 説明 |
|---|---|
| Socket | TCP/IP のクライアント側のソケット |
| ServerSocket | TCP/IP のサーバ側のソケット |
| DatagramSocket | UDP/IP のソケット |
以後、ネットワークか ら文字列を入力するには、InputStreamReader や BufferedReader のオブジェ クトを生成して利用する。
出力側では、Socket クラスのオブジェクトに対して getOutputStream() して、 OutputStream クラスのオブジェクトを得て、 PrintStream オブジェクトを生成して利用できる。
例：手続き put()。ハッシュ表にデータを格納する手続きで、引数にキーとな
る文字列と値となる整数を取る。
図? スタブによるRPCの実現
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 ;
インタフェース定義をスタブ生成器に与えると、クライアント側スタブ、サー
バ側スタブが自動的に生成される。
インタフェース記述の内容
| intなど基本型 | 構造体 | オブジェクト | 配列 | |
| C言語 | 値 | 値 | - | 自動ポインタ値化* |
| Java | 値 | - | 参照 | 参照 |
言語が持つ意味を、RPCでは再現できないことがある。
1: #include <stdio.h>
2:
3: int square( int a ) {
4: a = a * a ;
5: return( a );
6: }
7:
8: main() {
9: int x, y, result;
10: x = 10;
11: y = 20;
12: result = square( x );
13: printf("x==%d, result==%d\n", x, result);
14: result = square( y++ );
15: printf("y==%d, result==%d\n", y, result);
16: }
実行結果
% make square-value ![[←]](../icons/screen-return.gif)
cc square-value.c -o square-value
% ./square-value
x==10, result==100
y==21, result==400
% ![[]](../icons/screen-cursor.gif)
1: #include <stdio.h>
2:
3: int square( int &a ) {
4: a = a * a ;
5: return( a );
6: }
7:
8: main() {
9: int x, y, result;
10: x = 10;
11: y = 20;
12: result = square( x );
13: printf("x==%d, result==%d\n", x, result);
14: // result = square( y++ );
15: // printf("y==%d, result==%d\n", y, result);
16: }
実行結果。引数で渡した変数 x の値が書き換えられている。
% make square-ref
g++ square-ref.cc -o square-ref
% ./square-ref
x==100, result==100
%
C++の参照型では、引数には、変数しかかけない。y++ のような式では、コンパ
イル時にエラーになる。
% cat -n square-ref.cc
1 #include <stdio.h>
2
3 int square( int &a ) {
4 a = a * a ;
5 return( a );
6 }
7
8 main() {
9 int x, y, result;
10 x = 10;
11 y = 20;
12 result = square( x );
13 printf("x==%d, result==%d\n", x, result);
14 result = square( y++ );
15 printf("y==%d, result==%d\n", y, result);
16 }
% make square-ref
g++ square-ref.cc -o square-ref
square-ref.cc: In function 'int main()':
square-ref.cc:14: error: invalid initialization of non-const reference of type 'int&' from a temporary of type 'int'
square-ref.cc:3: error: in passing argument 1 of 'int square(int&)'
make: *** [square-ref] Error 1
C++の参照型は、プログラムが読みにくくなるので使ってはいけない。
main() {
int x ;
x = 10 ;
f( x );
printf("%d\n",x);
}
C言語のレベルでは、f(x) と呼んでも、決して x の値は、変化しない。C++の
参照型を使えば、f() の型宣言を見ないと、変化するか変化しないかわからな
い。「型宣言を見る」という手間の分だけ、プログラムが読みにくくなる。
全部の関数について、見ていたら疲れる。
1: #include <stdio.h>
2:
3: int square( int *a ) {
4: *a = *a * *a ;
5: return( *a );
6: }
7:
8: main() {
9: int x, y, result, *xp, *yp;
10: x = 10; xp = &x;
11: y = 20; yp = &y;
12: result = square( xp );
13: printf("x==%d, result==%d, &x==0x%x, xp==0x%x\n",
14: x, result, &x, xp);
15: result = square( yp++ );
16: printf("y==%d, result==%d, &y==0x%x, yp==0x%x\n",
17: y, result, &y, yp);
18: }
% make square-pointer
cc square-pointer.c -o square-pointer
% ./square-pointer
x==100, result==100, &x==0xbffff534, xp==0xbffff534
y==400, result==400, &y==0xbffff538, yp==0xbffff53c
%
C++の参照型は、プログラムが読みにくくなるので使ってはいけないが、
C言語のポインタ渡しは、使ってもよい。
main() {
int x ;
x = 10 ;
f( &x );
printf("%d\n",x);
}
C言語のレベルでは、f(&x) と&を付けた段階で、
f() の内容を知らなくてもx の値が変化することが推察される。値が変化する
可能性について、ポインタを渡している関数だけ注意すればよい。
main() {
int a[10] ;
f( a );
f( &a );
f( &a[0] );
}
配列を自動的にポインタに変換する歴史的な理由
1: #include <stdio.h>
2:
3: #define square( a ) ((a)*(a))
4:
5: main() {
6: int x, y, result;
7: x = 10;
8: y = 20;
9: result = square( x );
10: printf("x==%d, result==%d\n", x, result);
11: result = square( y++ );
12: printf("y==%d, result==%d\n", y, result);
13: }
実行結果。y++ と 1 度書いただけなのに、2 増えている。
% make square-macro
cc square-macro.c -o square-macro
% ./square-macro
x==10, result==100
y==22, result==400
%
マクロ展開だけして止めてみるとわかる。
% cc -E square-macro.c > square-macro.i
% wc square-macro.i
421 1135 9164 square-macro.i
% tail -13 square-macro.i
# 2 "square-macro.c" 2
main() {
int x, y, result;
x = 10;
y = 20;
result = ((x)*(x));
printf("x==%d, result==%d\n", x, result);
result = ((y++)*(y++));
printf("y==%d, result==%d\n", y, result);
}
%
1: #include <stdio.h>
2:
3: int square_a;
4: int square() {
5: square_a = square_a * square_a ;
6: return( square_a );
7: }
8:
9: main() {
10: int x, y, result;
11: x = 10;
12: y = 20;
13: square_a = x ; result = square(); x = square_a ;
14: printf("x==%d, result==%d\n", x, result);
15: square_a = y++ ; result = square(); y = square_a ;
16: printf("y==%d, result==%d\n", y, result);
17: }
実行結果。
% make square-copy-restore
cc square-copy-restore.c -o square-copy-restore
% ./square-copy-restore
x==100, result==100
y==400, result==400
%
ssize_t read(int fd, void *buf, size_t nbytes)
buf は、結果を受け取る場所を示したもので、RPCで遠隔に送る意味は
ない。
方法１。インタフェースを変える。
struct read_result_t {
ssize_t read_bytes;
void *buf;
};
read_result_t read(int fd, size_t nbytes)
方法２: スタブで違いを吸収する。
ssize_t read(int fd, void *buf, size_t nbytes)
{
fd, buf(nbytes分), nbytes を整列化する。
サーバへ要求メッセージとして送る。
サーバから応答メッセージを受け取る。
応答メッセージを非整列化して、結果の read_bytes と読んだ内容を取り出す。
読んだ内容を buf read_bytes 分へコピーする。
return read_bytes ;
}
単純に行えば、上のように余計なコピーが入ることがある。
スタブで最適化すれば、クライアントからサーバへのコピーを減らせる。
図? RPCのバインディング
クライアント側のプログラムとサーバ側のプログラムの対応はもはや１対１で はない。XML-RPC, SOAPなど、テキストを使う RPC もある。
unsigned long int hostlong, netlong;
receive(conn, /*(A)*/, /*(B)*/, 0);
/*(C)*/ = /*(D)*/ ;
printf("%d\n",hostlong ); // 受け取ったデータの表示。