プロセス

分散システムのアーキテクチャ・

プロセス

分散システム

2014年10月20日

アーキテクチャ

• ソフトウェアアーキテクチャ

– どのようなソフトウェアコンポーネントで構成され，ど

のように相互作用が行われるか

– アーキテクチャのスタイル

• システムアーキテクチャ

– 集中アーキテクチャ

– 分散アーキテクチャ

– ハイブリッドアーキテクチャ

• 自立的システム（autonomic systems）

– フィードバック制御

システムアーキテクチャ

• システムアーキテクチャ

– コンポーネントの相互作用と配置の方法

• クライアントサーバモデル

クライアントサーバモデル

• コネクションレスの通信（例：UDP，user datagram protocol）

– LANなど高信頼な環境では効率的

– クライアントはメッセージ（サービスと引数）をサーバに送信，

サーバは返事を送信

– 信頼性のない環境，リクエストorレスポンスが失われる可能性

• 信頼性のあるコネクション指向の通信（例：TCP，

transmission control protocol）

– 広域環境のような低信頼な環境

– コネクションを確立してリクエストを発行

– コネクション（再）接続のコスト

アプリケーションのレイヤリング

• （データベースをアクセスする）クライアント

サーバアプリケーションは三層の階層からな

る

– ユーザインタフェース層（user-interface level）

• クライアント（キャラクタ，グラフィックス）

– 処理層（processing level）

• それぞれのアプリケーション処理

– データ層（data level）

• ファイルシステム，データベース

• 永続性（persistency）をもつ

インターネット検索エンジンの例

ユーザインタフェース

二層アーキテクチャ

• 三層レイヤをクライアントとサーバに分ける

ユーザインタフェース

アプリケーション

データベース

多層アーキテクチャ

ユーザインタフェース

アプリケーション

データベース

分散アーキテクチャ

• 垂直分散（vertical distribution）

– 機能単位を複数マシンで分散

• 水平分散（horizontal distribution）

– 同一機能を複数マシンで分散

– 複数マシンで負荷を分散

– Cf. P2P（peer-to-peer）システム

• P2Pシステム

– （概念的には）P2Pを構成するプロセスは同一

– プロセス間の相互作用は対称的，クライアントでもありサーバ

でもある（サーバント，servent）

– オーバレイネットワーク（overlay network）

構造化P2Pアーキテクチャ

• オーバレイネットワークを決定的手続きで構成

• 分散ハッシュ表（distributed hash table, DHT）を

構成

– ハッシュキーは128ビット（MD5），160ビット（SHA1）な

どの広いID空間

– 複数のノードでハッシュ表を分割

• ノードのハッシュ値によりID空間を分割

• データをLOOKUPするとき，そのデータが割当て

られているノードを返す

– データが割当てられているノードにルーティングする

Chord [Stoica et al., 2003]

{ 0, 1 }

{ 2, 3, 4 }

{ 5, 6, 7 }

{ 8, 9, 10, 11, 12 }

{13, 14, 15 }

• succ(k)は最小のノードid



k

• LOOKUP(k)でsucc(k)を返す

（アルゴリズムは後の講義だ

が，O(log N)ステップで検索）

• メンバシップ管理

（前後のノードに知らせる）

非構造化P2Pアーキテクチャ

• 乱数アルゴリズムでオーバレイネットワークを

構築

• データもランダムに配置

• 検索はリクエストをフラッディング（ブロード

キャスト）

• ランダムグラフの生成が目標

– それぞれのノードが，生きているノードの内ランダ

ムにcノードの情報を知っている

スーパピア（Superpeers）

• 非構造P2Pではデータ検索は基本フラッディングなた

め，ピア数の増加に対し問題がある

• CDN（コンテンツデリバリネットワーク）等の応用ではコ

ンテンツを高速に発見したいという要求がある

• インデックスを保持し，ブローカ（仲介）となるノード＝

スーパピア

_{の導入（cf. Sun JXTA）}

ハイブリッドアーキテクチャ

• 協力的（collaborative）分散システム

• BitTorrentファイル共有システム[Cohen, 2003]

– 協力的なP2Pファイルダウンロード

• ファイルのダウンロードは，コンテンツを提供するノー

ドだけが可能

– .torrentファイルはトラッカ（tracker）を示す。トラッ

カはファイルのチャンクを保有するアクティブな

ノードを保持

– アクティブノードは現在ほかのファイルをダウン

ロードしているノード

アーキテクチャのまとめ

• ソフトウェアアーキテクチャ＝ソフトウェアの論理的な構成

• システムアーキテクチャ＝コンポーネントがどのように異な

るマシンに配置されるか

• アーキテクチャのスタイル

– レイヤ，オブジェクト指向，イベント指向，データスペース指向

アーキテクチャ

• クライアントサーバモデル

– 集中アーキテクチャとなりやすい

• P2Pシステム

– プロセスは等しく振る舞う

– オーバレイネットワーク＝ほかのピアの局所リストを持つ論理

的なネットワーク

– 構造化P2Pと非構造化P2P

演習問題

• ソフトウェアアーキテクチャ、システムアーキ

テクチャとは何か？

• 国際標準化機構（ISO）が定めたOSI（Open

Systems Interconnection）参照モデルを調べ

よ

• 構造化P2PにおけるDHTはChordの他にどの

ようなものが提案されているか？それぞれの

特徴をまとめよ。

プロセス

• 独立したプログラムの実行

– 互いに影響を及ぼさない（同一CPUを透明に利用，

並行透明性）

– 独立した論理アドレス空間をもつ

• プロセステーブル

CPUレジスタ

メモリマップ

オープンファイル

アカウント情報

権限（privileges）

プロセス生成とプロセス切替

• プロセス生成

– 論理アドレス空間の生成

• メモリセグメントの初期化（データセグメントをゼロクリア，テ

キストセグメントにプログラムをロード，スタック領域の設

定）

• プロセス切替

– CPUコンテキストの保存

• レジスタ，プログラムカウンタ，スタックポインタなど

– メモリ管理ユニット（MMU）のレジスタの修正と

translation lookaside buffer（TLB）の無効化

– （メモリ不足の場合）プロセスのスワップイン

スレッドとは？

• プロセス内の＊独立した＊プログラム実行

– 同一プロセスID

• プロセスほど高い透明性を持たない

– 論理メモリ空間を共有

– ファイルディスクリプタなどプロセス資源を共有

• 一般にスレッド生成はプロセス生成より軽い

スレッド切替

• スレッドコンテキスト

– CPUコンテキスト

• レジスタ，プログラムカウンタ，スタックポインタなど

– スレッド管理情報

• ほかの情報は持たない

– 同一プロセスのスレッド間のデータ保護は開発者に任せ

られる

• マルチスレッドプログラムの性能はシングルスレッドに

比べ悪くならない

– 多くの場合で性能向上が見込まれる

• スレッドは保護されない

プロセスvsスレッド

スレッド

プロセス

生成、実行オーバ

ヘッド

小

大

メモリ

共有

別々

プロセス資源

共有

別々

データ共有

_{メモリのポインタ渡}

し（コピーは不必要）

パイプ、ソケット、

ファイルなど

保護

_{他スレッドのメモリ、}

資源を破壊する可

能性あり。スレッド

の実行制御が必要

他プロセスのメモリ、

資源は保護される

非分散システムにおける

スレッドの利用

• プログラム構造の単純化

– 表計算における入力処理（スレッド１）と合計値など

の値更新（スレッド２）

スレッド１は入力を処理、スレッド２は変更を待ち変更

があれば更新

• マルチプロセッサでは並列に実行可能

• プロセス間通信のオーバヘッド削減

– （名前付）パイプ，メッセージキュー，共有メモリセグメ

ント

– カーネル経由のためコンテキスト切替のコスト大

main(int argc, char *argv[]) {

for (i = 1; i < argc; ++i) {

if (i == 1)

/* get the first picture */

buf = get_next_pic(argv[i]);

else

/* wait for the previous process */

pthread_join(tid, &buf);

if (i < argc – 1)

/* get the next picture */

pthread_create(&tid, NULL,

get_next_pic, argv[i + 1]);

display_buf(buf);

/* display the picture */

free(buf);

if (getchar() == EOF)

break;

}

}

スライドショウのプログラム例

表示している合間に次の

画像を読込

スレッドの実装

• スレッドの生成と解放，mutexロック，条件変数

• ユーザレベルスレッド

– 軽い（カーネル経由ではない）

– 入力待ちや無限ループでブロックするとプロセス全体がブ

ロックしてしまう

• カーネルレベルスレッド

– スレッドスケジューリングはカーネルが行うため、ブロック

しても大丈夫

– スレッド操作のコスト大（システムコール）

• ハイブリッド

– ユーザレベルスレッドとカーネルレベルLightweight

processes（LWP）

並列性の制御の必要性

• スレッド間でメモリ、プロセス資源を共有しているた

め、破壊してしまう可能性がある

• 例：共有カウンタのインクリメント

counter++

1.

counterの値をレジスタにロード

2.

レジスタの値をインクリメント

3.

レジスタの値をcounterにストア

スレッド１

1.

counterの値をレジスタにロード

2.

レジスタの値をインクリメント

3.

レジスタの値をcounterにストア

スレッド２

1.

counterの値をレジスタにロード

2.

レジスタの値をインクリメント

3.

レジスタの値をcounterにストア

共有カウンタのインクリメントの例

pthread_mutex_t count_mutex = PTHREAD_MUTEX_INITIALIZER; int count；

void increment_count() {

pthread_mutex_lock(&count_mutex); // ensure atomic increment count++;

pthread_mutex_unlock(&count_mutex);

}

int get_count() { int c;

pthread_mutex_lock(&count_mutex); // guarantee memory is synchronized c = count; pthread_mutex_unlock(&count_mutex); return (c); } データ競合領域 データ競合領域

仮想化

• （異なるシステムのインターフェースをもち）異

なるシステムのように振る舞う

• 既存ソフトウェア（legacy software）の実行

• 他OS，アーキテクチャのプログラムの実行

– IBM 370[1970]の仮想マシン

– Cygwin, Wine

– VMWare，Xen，KVM

コンピュータのインターフェース

仮想化は上記のインターフェースを模擬すること

仮想マシンのアーキテクチャ

プロセス仮想マシン

仮想マシンモニタ

(ハイパーバイザ）

サーバ設計における一般的なこと

• サーバ

– クライアントからのリクエストを待ち，実行する

• 反復サーバ（iterative server）

– サーバがリクエストを実行し，レスポンスを返す

• 並行サーバ（concurrent server）

– 別のスレッドorプロセスにリクエストを依頼

– 直ちに次のリクエストを待つ

分散システムにおけるスレッド

• プロセスをブロックさせないでブロッキングシ

ステムコールを呼べる

• 複数のコネクションの管理に有用

• マルチスレッドクライアント

– 広域ネットワークの遅延（数百ミリ秒～数秒）隠蔽

– （例）Webブラウザ

• ページ内複数ドキュメントの並列受信

• 受信しながら表示

マルチスレッドサーバ

• 典型的なマルチスレッドサーバの例

サーバのコンタクト先

• クライアントはサーバのエンドポイント（end

point）orポート（port）にリクエストを発行

• TCP，UDPのポート番号

– Internet Assigned Numbers Authority (IANA)が管

理

範囲 種類 備考

0～1023 Well Known Ports 登録なしに利用不可

UNIXではroot権限が必要 1024～49151 Registered Ports 登録なしに利用不可

49152～65535 Dynamic and/or Private Ports

代表的なポート番号

（サービス）

番号 説明

ftp-data 20/tcp, 20/udp, 20/sctp File Transfer [Default Data] ftp 21/tcp, 21/udp, 21/sctp File Transfer [Control]

ssh 22/tcp, 22/udp, 22/sctp Secure Shell, RFC 4251, 4960 telnet 23/tcp, 23/udp Telnet

smtp 25/tcp, 25/udp Simple mail transfer http 80/tcp, 80/udp, 80/sctp World Wide Web HTTP

imap 143/tcp, 143/udp Internet Message Access Protocol https 443/tcp, 443/udp, 443/sctp http protocol over TLS/SSL

imaps 993/tcp, 993/udp Imap4 protocol over TLS/SSL

http://www.iana.org/assignments/port-numbers

http://www.rfc-editor.org/

HTTPサーバへのアクセス例

Date: Mon, 14 Dec 2009 22:37:09 GMT Server: Apache/2.2.3 (CentOS)

…

Content-Length: 451 Connection: close

Content-Type: text/html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <HTML>

…

</HTML>

Connection closed by foreign host.

HTTPサーバへの リクエスト HTTPサーバからの レスポンス telnetコマンドでwww.tsukuba.ac.jpの port 80/TCPに接続 （リターンを2回） HTTPサーバが接続を切断

その他の事項

• 割込

– 例：FTPサーバへの大きなファイル転送を取り消したい

– コネクションの切断

– Out-of-band（OOB）データの送信

• 状態

– ステートレスサーバ

– ステートフルサーバ

セッション状態（session state）

• 単一ユーザの状態を一定の期間保持

– 永遠ではない

– 失われてもまたやり直せばよい

• Webブラウザのクッキー（cookie）

– クライアント側にサーバの状態を保持

– 消去してもまたやり直せばよい

まとめ

• 特に分散システムでは、スレッドは有用

– ブロッキングI/O操作を行いながらCPUを活用

– ただし、データ競合を起こさないよう並列性の制

御が必要

• 仮想化により既存アプリケーション，他OSの

アプリケーションが実行可能に

– VMMでは実行環境ごと保存，移動が可能

• サーバ設計に関しての一般的事項

演習問題

• プロセスとスレッドの違いは何か？

• XenとKVMはそれぞれどのように仮想化を実

現しているか？

• telnetでwww.cs.tsukuba.ac.jpのhttpポートに

アクセスしてみよ

• telnetでpoplar.cs.tsukuba.ac.jpのsmtpポート

にアクセスし，VRFY tatebe，EXPN c-sotsuken，

QUITを入力してみよ