2005/12/20

前回のおさらい（１）
前回のおさらい（１）z デッドロック（deadlock）

コンピュータシステムII（１１）– 「すでに確保した資源がありながら，他のプロセス（スレッド）が先に確保してしまったために待たされている資源がある」という状態にある一群のプロセス（スレッド）が，いずれも先に進めなくなって膠着状態に陥ること．
z ４つの必要条件
1. 相互排除（mutual exclusion）
2. 確保と待機（hold and wait）
3. 非プリエンプション（no preemption）
4. 巡回待機（circular wait）

情報基盤センター
天野 浩文

12

前回のおさらい（２）
前回のおさらい（２）

前回のおさらい（３）前回のおさらい（３）z デッドロックの抑止（prevention）

z 不幸にもデッドロックが起こってしまったら– そのままにしておいても自然に解消されることは絶対にない．
z デッドロックからの回復（recovery from a deadlock）– デッドロックの必要条件４つのうちのいずれかが成立しないように，プロセス（スレッド）からの資源要求の順序・タイミングに一定の制約を課す．
– 条件１：「相互排除」を取り除くのは一般には不可能なので，他の３つの条件のいずれかが成立しないようにする．
z デッドロックの回避（avoidance）– システム全体の資源の割り当て状況を監視しながら，デッドロックが発生する可能性のある資源割り当て要求が出されたら，それの処理を遅らせる．
– 資源の割り当て状況やプロセス相互の待機状況を常に監視しておかなければならない．
3

コンピュータシステムII（１１）– デッドロックに関与しているプロセス（スレッド）のいずれかを強制終了させる．
– デッドロックに関与しているプロセス（スレッド）のいずれかを，まだ実行開始していなかったことにする．
• やりかけた操作をすべて元の状態に戻して，最初から実行しなおす．

4

1

2005/12/20

前回のおさらい（４）前回のおさらい（４）前回のおさらい（５）前回のおさらい（５）z デッドロックの検出（detection）

z トランザクション（Transaction）– 「一つの意味的にまとまった仕事」– 途中まで実行されて中断・中止された状態では，意味のある（正しい）結果を残せない，ということ．
– データベース（database, DB）の分野で使われることが多く，「ひとまとまりの処理を構成するデータベース操作の集まり」などと定義されることもある．
z トランザクションの処理は，以下の４つの性質を満たさなければならない．
– ACID特性（ACID property）• 原子性（Atomicity）• 一貫性（Consistency）• 隔離性（Isolation）• 耐久性（Durability）– デッドロックの回避やデッドロックからの回復を行うために必要．
– 待ちグラフ（wait-forグラフ）を用いる方法– 時間切れ（timeout）方式
z ただし，並列処理・分散処理においては，単一プロセッサの場合よりも，より複雑で困難な問題になる．

5

6

前回のおさらい（６）
前回のおさらい（６）

前回のおさらい（７）
前回のおさらい（７）z 隔離性に関するより厳密な定義– 複数のトランザクションを並行処理（同時実行）した場合でも，その結果は• データベースの，可能なすべての初期状態に対して，• アクセスされるすべてのデータ項目について，• それらのトランザクションを何らかの順序で逐次処理した場合の結果（変化の履歴を含む）と一致しなければならない．
– 特定の初期状態のときだけ等価な直列スケジュールが存在する，というのではダメ．
– データ項目Aの上で観測されるトランザクション実行順とデータ項目Bの上で観測されるトランザクション実行順が異なるようなことも，あってはならない．

z いくつものデータ項目にアクセスするトランザクションがデータベースへの書き込みをその都度行っていると...
– 途中で止まったときに，すでに書き込まれた結果を元に戻すのは大変．
z そこで，通常は，以下のような方法が採られる．
– トランザクション実行中の書き込みは，当該データ項目の作業用コピーに対して行う．元のデータベースにはただちに反映させない．
– トランザクションが正常終了できるとわかったときに，初めて，すべての書き込み結果を，元のデータベースに反映させる⇒コミット（commit）操作– トランザクションが正常に終了できないとわかったときは，当該トランザクションを強制終了し，作業用コピーを捨てる．
（実行前の状態に戻ることができる）⇒アボート（abort）操作
z 広域分散システム上では…
– コミットすべきか，アボートすべきかの判断が困難– コミット・アボートが正常に終了することを保証することも困難

7

8

コンピュータシステムII（１１）22005/12/20

前回のおさらい（８）前回のおさらい（８）z 二相コミット（Two-Phase Commit）プロトコルの原理– 仮定• 各演算ノードごとに，そこのデータを管理する「リソースマネージャ」が１つ存在する．
• 個々のデータ項目の監視まではできないがリソースマネージャの「投票」の結果を管理できる「コーディネータ」が，システム全体で１つ存在する．
– １つの分散トランザクションの作業用コピーの上での処理が終了した後のコミット操作を，次の２つの段階に分割する．
• 第一段階クライアントサーバシステム
クライアントサーバシステム– 各演算ノードでコミットの準備ができたかどうかを確認する．

• 第二段階– 各演算ノードのリソースマネージャからの「投票」を受けて，コミット／アボートの判断を行い，各ノードでコミットを行う．
910

クライアントサーバモデル（１）クライアントサーバモデル（１）クライアントサーバモデル（２）クライアントサーバモデル（２）z サーバ（server）と，クライアント（client）によって，システムを構成する方式

z サーバとクライアントが通信するための規約（プロトコル，protocol）が，サービスごとに定められている．

– サーバ：あるサービスを提供するもの– クライアント：そのサービスを受けるもの
z 主な用途– ネットワーク上で動作するアプリケーションや，広域分散処理システム上のサービスに多く見られる．
• クライアントがサーバにサービスの実行を要求（処理を要求）し，• サーバがそれに応答する（実行結果を返す）．
– 通常は，ひとつのサーバがネットワーク上に分散する複数の（多数の）クライアントにサービスを提供することが多い．
• ただし，単一の計算機の内部でサーバプロセスとクライアントプロセスが動作する形態もある．

11

コンピュータシステムII（１１）– この規約に従うことにより，異なる製造元から提供されたサーバとクライアントが通信することも可能になる．

123

2005/12/20

クライアントとサーバの通信の例（１）クライアントとサーバの通信の例（１）クライアントとサーバの通信の例（２）クライアントとサーバの通信の例（２）z 要求と応答z サーバは，別のサービスのクライアントにもなりうる．

webブラウザ

webサーバwebブラウザ

webサーバ
要求

要求
要求の処理

結果を待つ

要求の処理

応答

要求
結果を待つ
応答

DBサーバ

要求
他のクライアントからの要求を処理してもよい

結果を待つ

結果を待つ

要求の処理

要求の処理

要求の処理
応答

応答
時間

時間

時間

13時間

時間

14

クライアントサーバシステム
クライアントサーバシステム

DNS
DNS

z クライアントサーバモデルに基づいてサービスを構築したシス
テムz クライアントサーバシステムによるサービスの例– DNS（Domain Name System）

z インターネット上のホスト名とIPアドレスを対応付けるサービス– 例：「isabelle.cc.kyushu-u.ac.jpのIPアドレスは？」⇒「133.5.7.33」• IPアドレス：インターネット上の計算機・通信機器に付与された番号のようなもの
z サーバ：DNSサーバ– 通常は，個人が所属する組織（大学等）または利用しているインターネットサービスプロバイダが提供する．
z 主なクライアント– リゾルバ（resolver）• 例：OSの中に用意された手続き gethostbyname• このサービスを必要とする他のサービスから呼び出されることが多く，これ自体が単体で使用されることは少ない．

– 電子メール– FTP（File Transfer Protocol）– World-Wide Web（WWW）– ソケット（socket）

15

コンピュータシステムII（１１）1642005/12/20

電子メール
電子メール

電子メールの運用形態の例（１）
電子メールの運用形態の例（１）z 最も古いネットワークアプリケーションの１つ
z いくつものプロトコルを組み合わせて運用されている．
– メッセージ転送プロトコルの例• SMTP（Simple Mail Transfer Protocol）• ESMTP（Extended SMTP）

z 送信（転送）– MUA（Mail User Agent）と呼ばれるクライアントプログラムからサーバ（SMTPサーバ）への転送– MTA（Mail Transfer Agent）間の転送もSMTPで

SMTP– 最終配送プロトコルの例• POP3（Post Office Protocol Version 3）• IMAP（Internet Message Access Protocol）

MUA– アルファベットだけでは表現できないデータをメッセージに埋め込むためのプロトコル• MIME（Multipurpose Internet Mail Extensions）

z 受信（最終配送）

SMTP

MTA

FTPサービス
FTPサービスz Webと組み合わせたサービス

z インターネット上の計算機間でファイルを転送するサービス– サーバ：FTPサーバ

Webサーバ– クライアントの例：• OSに備わっている ftp コマ
ンドz プロトコルの名前がFTP

SMTP

Webブラウザz ほぼ同格の計算機間の転送にも，多数のクライアントが共通の「ファイル置き場」を利用するようなサービスにも用いられる．
– クライアントから見て，ファイルを送るのが"put"，受け取るのが"get"WebサーバSMTP（POP3,IMAP）

MTA

HTTP
Webブラウザ

MUA

メール配送経路の最終端のMTA
は，ユーザごとのメールを蓄積保存していて，MUAからアクセスされるのを待っている．

電子メールの運用形態の例（２）
電子メールの運用形態の例（２）

SMTP

MTA

SMTP

17

SMTP

MTA

– POP3またはIMAPによってMUAへz 他のサービスと組み合わせて提供されることもある．
– Webメール• 例：GraceMail

HTTP

SMTP

SMTP

POP3
（IMAP）
18

FTPサーバ

"put"
"get"

クライアントクライアント

実際には，標準のWebサーバにはこの機能が備わっていないので，新たなプログラムを追加する必要がある．（例：GraceMail）
19

コンピュータシステムII（１１）20

52005/12/20

W
WW
WW
W

現在のWebサービス
現在のWebサービス

z 誕生は1989年...
– ヨーロッパの原子核研究機構で，報告書・論文・画像・観測データなどのさまざまなデータファイルを多くの研究者がネットワーク共有するためのサービスとして始まった．
– その後の爆発的な普及と，広汎な機能拡張
z インターネット上の数百万ものサーバ上の文書をリンクで結んだ「ハイパーテキスト（hypertext）」を共有するしくみ– ハイパーテキストのコンセプトは元からあった．
• Webサービスのためのハイパーテキストの文法がHTML（hypertext markup language）– クライアントがハイパーテキストの転送を要求したり，サーバがクライアントにデータを転送するためのプロトコルがHTTP（hypertext transfer protocol）

z HTML＋HTTPだけではなくなった．
– 今やHTMLはページの外枠だけ，などということも– さまざまなコンテンツタイプのサポート
実際には，ペー• 音楽，動画，etc.
ジ生成以上のこと– サーバ側による動的Webページ生成も実行可能．
• CGI（Common Gateway Interface）• PHP（PHP: Hypertext Preprocessor）• JSP（Java Sever Pages），ASP（Active Server Pages）– クライアントによる動的Webページ生成
実際には，ペー• JavaScript
ジ生成以上のこと

2122

ソケットソケットも実行可能．

– プログラミング言語 Java のサブセット• Active-X– 事実上，プログラムにできることなら何でも実行可能

典型的なソケット通信の流れ
典型的なソケット通信の流れ

z プロセスとプロセスが通信するための最も基礎的なサービス– バークレイ・ソケット（Berkeley socket）と呼ばれることがある．
• Berkeley UNIXで最初に採り入れられたため．
• 現在は，他の多くのOSでも提供されている．
– 他の多くのネットワークサービスが，これを用いて実現されている．
z ほぼ対等な２つのプロセスのうち，一方がサーバ，他方がクライアントとなる．
– サーバは，「ソケット」と呼ばれる「通信口」を用意し，そのソケットを自分が動作している計算機のIPアドレスに対応付けて，クライアントからの接続要求を待つ．
• 自分のIPアドレスを取得するためにリゾルバを利用– クライアントは，自分の側のソケットを用意した後，サーバが用意しているはずのソケットへの接続を要求する．
• 相手のIPアドレスを取得するためにリゾルバを利用– 接続確立後は，サーバとクライアントが対称的に send/recvを行うことができる．

23

コンピュータシステムII（１１）– プログラミング言語 Java とは別物

• Java applet

クライアントサーバ
socket( )ソケットの用意socket( )bind( )
listen( )接続要求

connect( )accept( )接続を解放

send( )

recv( )

recv( )

send( )

close( )close( )ソケットの用意
ローカルアドレスのソケットへの「取り付け」
接続受け入れ意志のアナウンス
接続要求が来るまでここで待ち続ける

接続を解放

24

6

2005/12/20

サーバ側のソケット
サーバ側のソケット

単一ソケットに対する複数の接続要求
単一ソケットに対する複数の接続要求

z サーバは，１つのソケットに対して複数の接続要求を受け入れるように構成することもできる．
– SMTPサーバやWebサーバはそのような接続要求を受け入れるシステムの例

z サーバは，どの要求がどのクライアントから来たか，知っている．
– 複数の要求を受け付けても，それぞれ正しいクライアントに応答を返すことができる．

webサーバ（133.5.7.33）

webクライアント（133.5.7.34）

webクライアント（133.5.7.35）
25

26

ポート
ポート

単一の計算機が複数のサービスを提供するとき
単一の計算機が複数のサービスを提供するとき

z １つの計算機が，いずれもソケットを用いて実現された複数のサービス（ソフトウェアとしてのサーバ）を動かしている場合，クライアントは，どうやって自分が必要とするサービスを受けられるか？
– ポート（port）• ソケットを作成するときに，1～65535（16ビット）の番号を指定する．
• クライアントは目的のサーバが指定したのと同じポート番号を指定すれば，そのサーバに接続できる．
z ソケットとは，IPアドレスとポート番号を組み合わせたもの

z クライアントは，サーバ計算機のIPアドレスと，受けたいサービスのポート番号を合わせて指定する．
– 同じ計算機から，異なるサービスを指定して受けられる．

27

コンピュータシステムII（１１）（133.5.7.33）

webサーバ
port: 80
FTPサーバ
port: 21

webサービスを要求（133.5.7.33の80番）
FTPサービスを要求（133.5.7.35の21番）

28

72005/12/20

予約されているポート
予約されているポート

inetdデーモン
inetdデーモンz 1024未満のポート番号は，よく知られているネットワークサービ
ス用で使用されている．
– 予約されている番号の例• 21：FTP• 25：SMTP• 80：HTTP• 110：POP3– 自分で新たなサービス用のプログラムを構築する場合には，1024以上の番号を使用する．
• ただし，1024～49151も，ユーザの利便性のため登録制になっている．
• プライベートなネットワークのクライアントに一時的なポートを割り当てる場合などは，49152～65535を使用すべき．

z OSに標準的に備わっているネットワークサービスは，クライアン
トからの接続を常時待ち続ける．
– 無限ループの形をしたプログラムが，プロセスとして動き続ける．
• このようなプロセスをデーモン（daemon）という．
• しかし，利用頻度の低いものでも，デーモンとして動作させ続けると，資源（メモリ空間，CPU時間）を消費する．
z inetdデーモン– 常時動作させるほど利用頻度の高くないサービスを，要求があるたびに新たなプロセスとして起動するためのデーモン– inetdデーモンは，あらかじめ設定されたポートへの接続要求を常時監視しており，要求がきたら，該当するサーバをプロセスとして起動することができる．

2930

ピアツーピアピアツーピア
z クライアントサーバシステムの特徴– 非対称• 固定されたサーバと，（不特定多数の）クライアント– サーバは「ずっとそこにいる」が，クライアントは「必要なときだけ出てくる」だけでよい．

ピアツーピアシステム
ピアツーピアシステム• 1990年代くらいまでは，ネットワークサービスを構築する方法はこれだけで十分かとも思われていたのだが...
z ピアツーピア（peer-to-peer，P2P）– ネットワークサービスを構築するもうひとつの方法• どの端末も対等な立場で参加• サービスを受けたり，提供したり• PCの性能向上が背景に– 1999年ごろから，Napsterと呼ばれる音楽データ交換サービスで注目を浴びるようになった．
31

コンピュータシステムII（１１）3282005/12/20

P2Pシステムに固定的なクライアント・サーバはない
P2Pシステムに固定的なクライアント・サーバはない

P2Pは紛争のタネ？
P2Pは紛争のタネ？
z 決して「P2P＝音楽ファイル共有」ではないのだが...
– P2Pがこれで有名になってしまった．
– データ共有以外に，今のところあまり有望な応用が見つかっていない．
• インターネット電話，インスタントメッセンジャーなどをP2Pの応用先と考える人もいるようだが…普及度は？
– データがコピーできるということになると，「カネを払わずに有料のコンテンツを」と考える人間が出るのは世の常で...

33

34

歴史的経緯
歴史的経緯

法的論争
法的論争

z 第一世代のP2Pアプリケーション（Napsterなど）– 「会員」は，自分のハードディスクにあるデータファイルを，中央のサーバに登録する．
• どこかの会員が「欲しい」と思ったデータが中央のデータベースで見つかれば，その会員のハードディスクから直接ダウンロードすることができる．
– 「音楽ファイル」の交換に使われてしまった．
• 裁判所からNapster社の運営停止命令が出る騒ぎに
z 第二世代（Gnutellaなど）– 中央のデータベースが不要に– すべて端末同士のやりとりだけで– 著作権保有者は誰を相手に裁判を？
• 当然，誰か次に簡単に突き止められる相手をやり玉に• 「犯人」の所属する大学・企業，「犯人」が使用したインターネットサービスプロバイダなど

z 家庭用VCRのメーカがテレビ局の著作権を侵害していることにはならない（米国で判例あり）．
– 留守番録画して自分が楽しむのが普通であり，不特定多数の人に配ったりは簡単にはできないからz 「P2PソフトウェアもVCRと同じで，使用者のモラルの問題だ」という主張は，どうも通らないようだ．
– 不特定多数の会員に公開されてしまう．
– いったん登録されアクセス可能になったデータの拡散のス
ピードが異常に速い．
z 「自分は著作権フリーのデータしか公開していない」という主張– 一部のP2Pソフトは，「こっそり」ユーザのハードディスクを中継データの一時的な格納場所に使用する．
– 知らないうちに不法行為の片棒をかつぐことに

35

36コンピュータシステムII（１１）92005/12/20

組織の自己防衛組織の自己防衛九州大学では九州大学ではz 音楽ファイルあるいはビデオファイルの交換は，非常に大きな通信負荷を伴う．
– 組織（大学・企業等）を外部のネットワークにつなぐ回線の通信速度は有限– 接続サービスを提供するインターネットサービスプロバイダにとっても脅威となる．
– これを理由にP2Pソフトウェアの利用を禁止する動き
z 「匿名性」をうたうP2Pソフトウェアであっても...

z WinMX，Winny のようなP2P型ファイル共有（交換）ソフトウェアの学内LANでの利用を禁止– 著作権保護団体が同じソフトウェアを利用すれば，違法なファイルがどの組織から流れているかは検知可能– 不作為を問われる訴訟の恐れ• 2003年11月には，日本レコード協会が全国約1200の国公私立大学・短大に対し、学内ネットワークを使用した音楽の不正利用を防止するよう要請する文書を送付• 「知らなかった」では済まない状況に– 特定の（固定された）メンバの間での合法的なファイル共有なら，他にも方法があること．
– 知らない間に不法なファイル交換の共犯になるのを防ぐ方法が他にないこと．
– 特定のポートをファイヤウォールで封鎖するという方法では遮断できないこと．

37

38

まとめ
まとめ

次回（来年1月10日）
次回（来年1月10日）

z クライアントサーバシステム– サーバ（あるサービスを提供するもの）と，クライアント（そのサービスの提供を受けるものから構成される．
– サービスごとに，サーバとクライアントの間の通信規約が定められている．
• 例：DNS，電子メール，FTP，WWW，ソケットなど

z 演習の第2回をやります．
– 持ち込みその他の条件は，前回と同じです．
– 出題範囲は，第9回～第11回（今回）の講義で扱った内容とします．

z ピアツーピアシステム– 固定的なサーバ・クライアントが存在しない．
• サービスを提供したり，受けたり– 残念ながら，今のところ，ほとんど『悪者』扱い

39

コンピュータシステムII（１１）4010