並行システム
システム情報工学研究科コンピュータサイエンス専攻、電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2009/2010-02-19
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/sie/
http://www.cs.tsukuba.ac.jp/~yas/
- 期末試験は行いません。期末レポートもありません。毎回のクイズとレポー
トで成績を付けます。
- レポート出していない人は Web ページから出してください。
- 休んだ回のクイズは、「紙(A4)」で提出してください。
- クイズ、または、レポートは、2月28日 までに全部提出してください。
- トランザクション、begin_transaction、commit、abort
- Argus
- 投機的実行
相互排除、デッドロックより高いレベルの抽象が欲しい。
ロックよりも楽にプログラムを作りたい。
特に分散では。集中でも、フォールト・トレランスの実現では必要。
商談は、成立するか、しないか。
all or nothing。
歴史:1960年代、テープの時代。
失敗したら、巻き戻す(rollback)。
銀行口座間の預金の移動。
- 口座1から出金
- 口座2に入金
- Begin_Transaction
- Commit (End Transaction)
- Abort
- Read
- Write
- Atomic
- 外の世界からみると1つ。中間状態が見えない。不可分。
- Consistency
- 不変量(invariant)を保つ。例:口座間の預金の移動。預金の総額は不変。
- Isolated
- 並行するトランザクションは、孤立している。直列化可能(serializable)
- Durable
- Commit すると永続的。
注意:Javaの serializable とは意味が全く違う。
複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク
ションの最終結果は、それらを「ある順序」で「逐次的に」実行した時と同じ結果
になる。
逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行
に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら
せるか、アボートする。

図? トランザクションの処理(並行実行)

図? トランザクションの処理(直列化の例その1)

図? トランザクションの処理(直列化の例その2)

図? トランザクションの処理(直列化の例その3)
航空券の乗り継ぎの予約のプログラムの例。
成田からサンフランシスコ経由でオーランドまで行きたい。
Begin_Transaction();
reserve("NRT-SFO");
reserve("SFO-MCO");
Commit();
プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的
には、ロックは行われる(ことがある)。
途中の reserve() が失敗したら、トランザクション全体を abort() する。
目的
親が abort されたら、子供が commit したものも無効になる。
- プライベート作業空間。書き換える前にコピーを作り、コピーを更新。
- 先行書き込みログ。更新作業をログに記録して、後で戻せる(rollback)
ようにする。
全てのデータをコピーすると重たい。
- 読み込みではコピーしない
- ファイル全体だけではなく、インデックス(inode)だけをコピーする。シャドー・ブロック。
実行予定リスト(intentions list)
シャドー・コピーを作らず、ファイルのその場所を書き換える。
その前に、次の情報を安定記憶にログとして書き込む。
コミットされると、何もしない。
アボートされると、ログを後ろから前に読み込み undo する。
クラッシュからの回復もできる。
- RAM
- 電源が落ちると消える
- ディスク
- ディスクヘッドのクラッシュで消える
- 安定記憶
- 洪水や地震でも生き残るように設計されている。
安定記憶の実現方法:2個のディスクの組みを使う(図?(a))。

図? 安定記憶の実現
更新時:
- ディスク1のあるセクタに書き込む。
- ディスク1からそのセクタを読み込む。
- 内容を比較する。同じなら、ディスク2の同じ位置に書き込む。
3 の前にクラッシュしても、常にディスク1が正しい(図?(b))。
この場合は、ディスク1からディスク1へコピーする。
チェックサムエラーが起きた場合(図?(c))、他のディスクからコピーして回復する。
できるだけ効率のよい、直列化可能なスケジューリングを求める。
- ロッキング
- 楽観的並行性制御
- タイムスタンプ
- 2相コミット
もっとも単純な方法:
Begin Transaction で、ファイルをロックする。
Commit/Abort でアンロックする。
注意:プログラマは、ロックを意識しない。
制約が強すぎる。
読み取りロック:read lock と write lock を分ける。
ロックの粒度(granularity)が大事
- 小さくする
- 並列性が高まる。ロック自体のオーバヘッドが増える。
デッドロックが起こりやすくなる。
- 大きくする
- 逆
デッドロックが起きにくい、直列化可能な方法。
- 第1相(growing phase)
- ロックの数が増える一方
- 第2相
- ロックの数が減る一方
定理:トランザクションの実現で2相ロックを使うならば、インターリーブさ
れることで作られるスケジュールは直列化可能である。
実際のシステムでは、Commit/Abort するまで、一度確保したロックをはなさない。
第2相で、まとめて全部ロックを解放する(strict two-phase locking)。
利点
- 中間的な状態を外から見られることがない。無駄な計算が起きない。
- 連鎖アボート(cascaded abort)が起きない
- デッドロックの検出に時間切れが使えることがある。
2相ロックでも、デッドロックは起きる。
- ロックの順番を決める
- グラフのループを検出する
- 時間切れ
注意:2相ロックと2相コミットは別。
どんどんやって、後でまずかったことがわかった時点で abort する。
衝突が稀である時に有効。
実現(衝突時の対応):プライベート作業空間を使う実現が便利。
どんどんプライベート作業空間上のファイルを更新して、最後にコミットする
か削除する。
性質
- デッドロックがおきない。
- 並列性が高い。
- 衝突して失敗する確率が高くなると辛い。
操作にタイムスタンプを付けて、まずいものをアボートする。
アルゴリズム:
- ファイルには、読み取りのタイムスタンプと書き込みのタイムスタンプが付け
られる。
- あるプロセスがファイルをアクセスする時、
トランザクションのタイムスタンプとファイルのタイムスタンプを比較する。
ファイルの方が古ければ、問題なし。
- ファイルの方が新しければ、トランザクションをアボートする。
楽観的:同じファイルを独立したトランザクションで同時にアクセスすること
は、あまりない。
Lamport のアルゴリズム等でクロックが同期されていれば、分散システムでも
使える。
2相コミット(two-phase commit)は、分散システムにおけるトランザクション
の実装方法。(注意: 2相ロック(two-phase lock)ではない)。
2種類のプロセス
- コーディネータ・プロセス、1つ
- サブオーディネート(残りの関連するプロセス)。従属。
2つの相
- 第1相
- 全プロセスを Commit も Abort もできる状態にする。
- コーディネータは、ログに「準備」と書く。
- コーディネータは、サブオーディネートに「準備」メッセージを送る。
- サブオーディネートは、ログに「準備完了」と書く。
- サブオーディネートは、コーディネータに「準備完了」メッセージを送る。
- コーディネータは、全てのサブオーディネートからの応答を待つ。
- 第2相
- 実際に Commit する。
- コーディネータは、ログに「コミット」と書く。
- コーディネータは、サブオーディネートに「コミット」メッセージを送る。
- サブオーディネートは、ログに「コミット完了」と書く。
- サブオーディネートは、コーディネータに「コミット完了」メッセージを送る。
- コーディネータは、全てのサブオーディネートからの応答を待つ。
クラッシュした時には、ログから回復させる。
トランザクション機能を内部に含む言語。
発音は、英語読みでアーガス。ギリシャ神話読みでは、アルゴス。
Barbara Liskov: "Distributed programming in Argus", Communications of
the ACM, Vol.31, No.3, pp.300-312, 1988.
並行に動作するオブジェクト(現在の用語ではスレッド)を実現する。
- ハンドラ(handler)と呼ばれる
他のガーディアンから呼ぶことができる手続き(エントリ)を持つ。
- 初期化用にクリエータ(creator)と呼ばれるエントリを持つ。
ガーディアンは、2種類の局所変数を持つ。
- 安定(stable)
- クラッシュ(再起動)しても、生き残る。
- 揮発(volatile)
- クラッシュ(再起動)すると、値が失われる。
安定な変数に対するトランザクションを実現する。安定な変数を、整合性がと
れた状態から、次の整合性がとれた状態へ遷移させる。(
途中でクラッシュしたら、元に戻す。)
- トップアクション
- トップレベルのトランザクションを実現する。commit するか abort するか。
内部にサブアクションを持つ。
abort したら、内部のサブアクションもすべて abort。
- サブアクション
- ネストしたトランザクションを実現する。
他のガーディアンのハンドラの呼出し(遠隔手続き呼び出し)は、
サブアクションになる。
- 2相コミット
- 書込みロックで、作業用のコピーが作られる。
- 名前
- 生成ルーチン。引数の取得。
- 安定な変数
- 揮発的な変数
- ハンドラ手続き(外から呼ばれるエントリ)
- バックグランド・ルーチン。ガーディアン自身のプログラム。
- 復旧手続き。クラッシュ後に実行され、揮発的な変数を状態に戻す。
安定な変数については、システムが自動的に整合性が取れた状態に復旧する。
branch = guardian is create handles total, open, close, deposit, withdraw
% type definitions
htable = atomic_array[bucket]
bucket = atomic_array[pair]
pair = atomic_record[num: account_number, acct: acct_info]
acct_info = atomic_record[bal: int]
account_number = atomic_record[code: string, num: int]
intcell = atomic_record[val: int]
stable ht: htable % the table of accounts
stable code: string % the code for the branch
stable seed: intcell % the seed for generating new account numbers
create = creator (c: string, size: int) returns (branch)
code := c
seed.val := 0
ht := htable$new()
for i: int in int$from_to(1, size) do
htable$addh(ht, bucket$new())
end
return (self)
end create
total = handler () returns (int)
sum: int := 0
for b: bucket in htable$elements(ht) do
for p: pair in bucket$elements(b) do
sum := sum + p.acct.bal
end
end
return (sum)
end total
open = handler () returns (account_number)
intcell$write_lock(seed) % get a write lock on the seed
a: account_number := account_number${code: code, num: seed.val}
seed.val := seed.val + 1
bucket$addh(ht[hash(a.num)], pair${num: a, acct: acct_info${bal: 0}})
return (a)
end open
close = handler (a: account_number) signals (no_such_acct, positive_balance)
b: bucket := ht[hash(a.num)]
for i: int in bucket$indexes(b) do
if b[i].num != a then continue end
if b[i].acct.bal > 0 then signal positive-balance end
b[i] := bucket$top(b) % store topmost element in place of closed account
bucket$remh(b) % discard topmost element
return
end
signal no_such_acct
end close
lookup = proc (a: account_number) returns (acct_info) signals (no_such__acct)
for p: pair in bucket$elements(ht[hash(a.num)]) do
if p.num = a then return (p.acct) end
end
signal no_such_acct
end lookup
deposit = handler (a: account_number, amt: int) signals (no_such_acct,
negativ_amount)
if amt < 0 then signal negative_amount end
ainfo: acct_info := lookup(a) resignal no_such_acct
ainfo.bal := ainfo.bal + amt
end deposit
withdraw = handler (a: account_number, amt: int) signals (no_such_acct,
negative_amount, insufficient_funds)
if amt < 0 then signal negative amount end
ainfo: acct_info := lookup(a) resignal no_such_acct
if ainfo.bal < amt then signal insufficient_funds end
ainfo.bal := ainfo.bal - amt
end withdraw
end branch
- ガーディアンを定義し、branch という変数にバインド
- クリエータは、create()
- ハンドラは、total(), open(), close(), deposit(), withdraw()
- 型定義。record は、構造体の定義。
- atomic なので、システムによりトランザクションの対象となる。
- 変数定義。stable なので、全部安定。
揮発的な変数がないので、クラッシュからの回復コードはない。
- バックグランドの手続きもない。
- seed は、口座番号をユニークにするためのカウンタ。
投機的実行(speculative execution)、将来利用されるか利用されないか確定さ
れる前に実行を開始してしまうこと。楽観的(optimistic)とも言う。
if( a() ) {
b();
}
else {
c();
}
- 普通は、a() が true か false かを返すのを待ってから
b() 、または、c() を開始する。
- 投機的処理では、a() の完了を待たずに、先に、b()、または、c() また
は、b() と c() の両方を実行する。

図? 投機的実行
この例では、a() が完了した時には、b()、c() が終わっていた時には、見かけ
上、即座に終わる。
- CPU が遊んでいる時には有効。近年の省電力とは、やや相反する。
- 通信遅延の隠ぺいに使える。
- then 部や else 部の処理に、副作用がない(関数型)の時には、
実装は楽。
- 副作用がある時には、トランザクション的な実装が求められる。
- 最近のCPUは、分岐予測をして、条件分岐命令の先まで先に実行する。条
件が満たされない時には結果は捨てられる。
新城の研究成果。
- 根路銘, 當眞, 新城, 喜屋武, 翁長: "粗粒度投機的並列処理を支援
するオペレーティング・システムの構想", SWoPP'94, 情報処理学会研究会報
告94-ARC-107-12, Vol.94,No.66, pp.89-96 (1994年7月).
- 石井 孝衛, 新城 靖, 板野 肯三: "プロセストレース機能を用いた世界
OSの実現",情報処理学会論文誌, Vol.43, No.6, pp.1702-1714 (2002年6月).
- 今里邦夫, 鈴木真一, 新城靖, 板野肯三: "動的リンクとパケットフィル
タを用いた世界OS のネットワーク機能の実現",日本ソフトウェア科学会第6回
プログラミングおよび応用のシステムに関するワークショップ(SPA 2004), ポ
スターセッション (2004年3月1-3日).
SF (Science Fiction) のパラレルワールド(parallel world, parallel
universe)を、オペレーティング・システムのレベルで実現する。

図 SFのパラレルワールド
SFでは、時々別の世界にジャンプしたり人が入れ替わったりする。
Undo とは、do の効果を打ち消して、もともと do しなかったことにする。
(do not とは違う。)
世界OSでは、ファイルの内容を変更すると、2つの世界ができる。

図 世界OSで使える世界の操作
実際には、先に世界を作り、その中でファイルの内容を書き換える。うまくいっ
たら、融合する。失敗すれば削除して、変更の結果を無効にする。
普通の仮想計算機では、融合はできない。継承のコストが大きい。
- クラックキング、攻撃による破壊からの迅速な回復。攻撃される
可能性があるプログラム、
怪しいプログラムを子世界で実行して、破壊されたら削除して回復させる。
- 投機的処理/楽観的処理。実行しろと命じられる前に先行的に実行する。
投機的make。
- 「差分」を first class object として扱う。
複数のPCでのファイル内容の統一。複数の世界の内容を比較して
更新された部分を反映させる。
C. Cowan and H. L. Lutfiyya: "A wait-free algorithm for optimistic
programming: Hope realized", In Proceedings of the 16th International
Conference on Distributed Computing Systems(ICDCS), pages 484-493,
1996.
RPCの遅延を隠す。
2つの銀行口座の間で送金するプログラムの概略を、トランザクションを使って
簡単に書きなさい。基本となる言語としては、C言語、Java言語、または、それ
に類するものを使いなさい。変数宣言の欠如や型の不一致等のコンパイラが検
出するような誤りは、減点しない。
問題(1001) で、ロックを使う方法と比較して、トラン
ザクションを用いる方法の利点を示しなさい。
Argus 言語のガーディアンと次のどれかと対比しなさい。類似点と相違点を述
べなさい。
- Java のスレッド
- Java の synchronized によるモニタ
- Pthread の mutex によるモニタ
- Concurrent Pascal のモニタ
- Ada のタスク
- CSP のプロセス
- Actorのアクタ
- その他、この講義で述べた言語の類似の機能
Last updated: 2010/02/19 11:30:13
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>