論文紹介: Language Support for Lightweight Transactions
久野靖∗

2004.6.3

1

はじめに□ 紹 介 論 文:

• get() と put() はある程度並行できるはずなのにこの方法ではできない

Tim Harris, Keir Fraser, Languate□ 本 論 文 で は Hoare の CCR(Conditional Critical

Support for Lightweight Transactions, OOPSLA
2003, pp.388-402.

Region) に立ち帰る□ 並行言語、並行制御→昔からある研究分野• CCR では「どの操作群を並行アクセスから保護するか」を指定可能 (?)• ガード (「どの条件が満たせたら入っていいか」) が指定可能• 並行制御の機能とかある程度出尽くした感もあるし…
• 現在は「スレッドがあればいいや」であまり顧みられていない

public int get() {atomic(items != 0) {items--;
return buffer[items];}}□ この論文→ CCR+トランザクション。

• 実装のセンスもいいし実用性高い。なるほどと思わせるところがある• 一番すごいのは「ブロックしなくてよい」こと。ウ □ 問題はよい実現方法が知られていないことだった
ソ?!って感じ• CCR 中で何と何にアクセスするかは分からない• いつガードが空くか分からない

2

INTRODUCTION• → CCR を全部排他実行しガードを毎回再評価→当然ながらのろい→現在のような条件変数による制御が□ 1970 年代以降、主流言語では「並行」の分野の発展は行われるようになった

止まっている□ 今日の技術進歩→非停止並行データ構造に基づく新しい□ たいていは→マルチスレッド+排他+条件変数 (Java が実装そう)□ これには問題点がある:□ CCR を STM(Software Transaction Memory) に対応させる

public synchronized int get() {int result;while(items == 0) wait();items--;
result = buffer[items];
notifyAll();
return result;}• 2〜106CPU のマシンで評価の結果、単純な排他制御より優れているとの結果。十分工夫された排他制御と同程度□ 本論文の 3 つの貢献:• CCR ではじめて (i) 動的に衝突のない操作を並行実行可能、(ii) 条件の再評価は共有変数が更新された• while で繰り返し wait() がなぜ必要なのか忘れられたり理解されてなかったりする

場合のみ、(iii) 非停止な実現→デッドロックしない• データアクセスが保護されているかどうかを検査す• 現代の OOPL と STM をはじめて融合。さまざまな興る仕組みなし

味深い問題∗ 筑波大学大学院経営システム科学専攻1• word サイズのデータをそのまま利用可能 (予約等不要)、かつ原子的更新だけでなくスレッド同期まで考4.2□ 非停止アルゴリズム→排他の問題を避けるために多く慮した最初の実現

3

Non-blocking algorithms

研究• 定義:MOTIVATION

スレッドいくつが死んでも残りのシステムが停止することはないような構成→ nonblocking• 当然、ロックは除外されることに□ cc-NUMA や SMP の普及→並行性は当り前のものに• しかし多くのプログラマは考えたくないと思っている□ obstruction-free:• ロック単位の粒度→大きいと性能低下、小さいと構築が大変

文もこれを前提とする

nonblocking の 1 つのクラス。

他のスレッドと競合しない限り進捗が保証される。本論• livelock はあり得る→ exponential backoff など□ 内部でロックを含むデータ構造の構成→難しい問題の回避手段• SPECjbb の get()、put()、remov() →並行利用可能□ メモリ上で直接非停止なシステムを作るのは大変→抽象• では removeLeast() は→自分でロックを操作しない化の方向を模索とできない、全体をロックしてしまうとせっかくの並行性がなくなる• transactional memory →一群のメモリアクセスをトランザクションに (commit/abort)。ハードウェア□ デッドロックの防止→システム全体の状況を知らないとを想定。

できない• Shavit、Touitou がソフトウェア TM を提唱。ただ□ 優先順の場合→ priority inheritance →やはり全体し制約が強い

知識必要• Herlihy らが CAS(compare and swap 命令) で済む実用的な方法を考案。Java への実装も。ただし open

□ 手動でロックを掛けたり外したりするスタイルに問題があるとトランザクションに参加するオブジェクトの同定などが必要→本論文ではこれらの制約も解消

4

RELATED WORK

□ 並行制御のためのプログラミング言語機能

5

LANGUAGE INTEGRATION□ 非停止アルゴリズム、STM□ Java に前述の atomic 文を入れた。設計方針:• CCR は内部のコードにできるだけ制約を課さないよ4.1

うに←単一スレッド用のコードでも簡単に CCR で囲Language features

める□ JVM、CLR、POSIX スレッド→排他+条件変数• CCR が使われてない部分に大きなオーバヘッドがないように。たとえば全オブジェクトに追加のフィー□ CCR 型の機能→ DP、Edison、Lynx の await 文□ Rem --- セマフォで CCR を実現→前述の弱点。Schmid

ルドを設けるなどは避ける→静的解析による再評価の軽減、ただし制約が大□ Argus --- トランザクション機能 (enter/leave) を導

5.1

入した言語

Identifying CCR□ 構文は次の通り□ Flanagan, Quader --- Java 上で atomic 構文

atomic(条件) { 文… }□ Lomet --- aciton 文。本論文に最も近い。本論文はこれに (i)2PL を不要にしデッドロックをなくした、(ii)• 実行するスレッドにとっては通常の単一スレッド実行と同じ同期に用いる変数を明示しなくて済むようにした、という改良を行っている• 他のスレッドにとっては atomic に起こる2• exactly once セ マ ン ティク ス 。単 純 の た め 。atmost once や timeout は避けた

5.7

Consistency model□ Java でのメモリモデルとの関係も検討しておく必要• 中からでも普通に例外を投げてよい。

□ Java ではスレッド間で共有するメモリは (i) 排他領域に入れるか、(2)volatile 指定、によって順序が保証

5.2

Data accessible to CCRs

□ これに CCR も自然な形で追加□ CCR 内からはどのクラスのどのフィールドでもアクセスしてもよい

6• 特定の継承階層のオブジェクト等だとコードの再利用ができない

SOFTWARE
TIONS

TRANSAC-□ CCR 用の STM の実装について• この方針から→ word-based STM• ソフトによる実装だがハードでも同様

5.3• word サイズの CAS 命令 (ないし同等のもの) が前提

Native methods□ STM の特徴

□ CCR 中での native method 実行は禁止している。実行すると例外• 特別な場所を予約する必要がない。32 ビット全部使える• 標準クラスのものもなのでやや不便→問題ないもの• word 幅の atomic access だけ保証されれば doubleは許可できるようにしたい

5.4

等も問題なし• 制御用データ構造は静的に割り当て可能。作業領域
は普通のヒープでよい

Nested CCRs

• read は共有メモリの書き込みなしで実現できる→□ 動的に CCR が入れ子になってよい (CCR の中で CCR を含キャッシュが有効むものを呼ぶ等)• 動くように設計することはプログラマの責任

5.5

6.1

□ メモリアクセス群に対し nest しないトランザクション機能を提供

Existing synchronization mechanisms

void STMStart() --- trans 開始
void STMAbort() --- アボート
boolean STMCommit() --- コミット
boolean STMValidate() --- コミット可能?
void STMWait() --- 競合 trans 完了を待って abort□ CCR と既存の同期機構の係わりを検討しておく必要□ CCR 中でロックを獲得する場合→ CCR 入口で atomic に獲得。従って CCR どうしの通信に排他オブジェクトを使うことは可能□ CCR 中では wait() は無意味→ wait() と notify()、□ atmic ブロック (入れ子なし) の実現
boolean done = false;
while(!done) {STMStart();try {if(条件) {本体動作;
done = STMCommit();} else {STMWait();}} catch(Throwable t) {done = STMCommit();if(done) throw t;}}

notifyAll() を禁止

5.6

STM interface

Class loading□ Java では初めてクラスにアクセスしたときローディン
グ/初期化• CCR 中で初めてアクセスした場合は→ CCR 中で初期化等が実行されるのは問題あり• CCR 中で初めてアクセスした場合、まずローディング等が起き、その後で CCR の atomic 部分が実行
3

• LS1: orec が変化してなければヒープ上の値も変わっていない□ 入れ子 CCR は 1 つの trans で実現□ メモリ読み書き用のインタフェースも用意• LS2〜LS3:

stm_word STMRead(addr a) --- メモリ読み
void STMWrite(addr a, stm_word w) --- 書き

エントリは一度用意されたら変わらない。状態は ACTIVE からその他の 1 つに 1 回だけ変化し得る

6.2• 以上から読み出した snapshot は整合性がある

Heap structure□ データ構造は 3 つある (図 2)

6.3□ application heap --- 普通のヒープ

STM operations□ orec は通常はバージョンのみ保持□ orecs (ownership records) --- trans 制御のため□ orec が ディス ク リ プ タ を 参 照 す る の は trans が• ownership 関数でヒープアドレスから orecs へのCOMMIT または SLEEP になろうとする時だけ。つまりマッピング定義

STMCommit、STMWait の直前までは trans は独立に動いている (変更内容はディスクリプタに累積)• orec はバージョン番号または current owner を格納• ヒープ内容が更新されるごとに番号は増える (当面 □ commit
で再利用なしと仮定)
algorithm を適用

multi word compare and swap

□ transaction descriptors• 生きているトランザクションごとに 1 つ (当面再利 6.4 STMStart用なしと仮定)□ 新しいディスクリプタを割り当て ACTIVE に• ヒ ー プ 上 の 更 新 を 記 録: transaction entry =(アドレス, 旧バージョン, 旧値, 新バージョン, 新値)
• 状態:

6.5

ACCTIVE、COMMITED、ABORTED、ASLEEP• well formed:

STMAbort(i) エントリが 1 つだけ、または □ 状態を ABORTED にするだけ(2) 全エントリで新旧バージョン番号がすべて一致□ ヒープ上のアドレスの logical state = (値, バージョ

6.6ン) を考える。次の 3 つの状況がある (排他)• LS1:

バージョン番号は orec、値はヒープ• LS2:

ディスクリプタにそのアドレスのエントリが□ 既にアドレスのエントリがある→新しい値を返す□ ない→エントリを作る。ディスクリプタに同じ orec のエントリがあればそのバージョン番号をコピー、そうで含まれる• LS3:

STMReadなければ旧バージョンを使う

そのアドレスのエントリがない。この場合は同じ orec に対応する他のアドレスのエントリを探6.7し、バージョン番号はそのアドレスのバージョン番号

STMWrite(ないし COMMITED ならそれ+1)、値はヒープ。well □ アドレスのエントリがなければ作る (read すればよい)。
formed であれば LS3 の値も一意に決まる
書く値は new-value に、new-version は old-versin +1 (他のエントリも同じに更新する --- well formed□ あるアドレスの logical state は直接 LS1〜LS3 で求を維持)

められる• 再利用なしなので、計算後変更がないか再チェックで大丈夫
do {orec = orec_of(addr);
アドレスの logical state を orec から求める} while(orec_of(addr) != orec);

4

6.8

6.10

STMCommit

STMWait□ 必要なすべての orec を acquire →成功したら→すべて □ すべて acquire するまでは COMMIT と同じ。その後、自分の状態を ASLEEP にして寝る。他人が STMCommit() しCOMITTED に→ヒープ内容を更新→すべて release

ようとして BUSY なので分かる→起こしてもらえる□ 鍵は acquire と release。いずれもディスクリプタ tdとその中のエントリの番号 i を受け取る
acquire(trans_desc *td, int i) {tarns_entry te = td.entries[i];orec seen = CAS(orec_of(te.addr),te.old_version, td);if(seen == te.old_version || seen == td)
return TRUE; /*1 成功 or 既に所有*/
else if(holds_version_number(seen))
return FALSE; /*2 バージョン相違:失敗*/
else
return BUSY; /*3 他人が所有*/}• CAS(a, x, y) :6.11Optimization□ ここまでの方式はいくつか不経済な点• (i) 1 つの orec で最大 1 人しか寝られない• (ii) read も write もエントリを探索する必要• (iii) 読み出しのみアクセスでも orec を 2 回更新• (iv) BUSY で再試行では non-blocking でない

アドレス a の内容が x であるな

6.12

ら、それを y に変更 (もちろん atomic に)。返値はMultiple sleeping threads□ 眠る場所を 1 つでなく連結リストにすればよい

アドレス a の内容□ acquire で FALSE に遭遇→状態を ABORTED にしてすべ

6.13て release

Read sharing□ acquire で BUSY に遭遇→誰かが owner になって使用中 □ cacheを 汚 さ な い た め に STMCommit
acquire/release での書き込みを何とかしたい• owner を ABORT するの□ た と え ば 次 の よ う に す る?

(i) 更 新 す る 場 所 だ
け acquire す る 、(ii) 読 む 場 所 が old value と• owner が STMWait() で停止中なら起こす• 自分は ABORT して再試行にold version のままであることを確認、(iii)COMMITにする←実際は atomic にならない□ すべて acquire 成功→状態を COMMITED にする (論理的にはこれによってすべての値が更新される)□ 新しい状態 READ PHASE を追加し、その状態で (ii) を実行• 値をヒープに書き戻す (この間にアクセスしてきた人はディスクリプタ側の値を見るのでタイミングは □ 他の trans は READ PHASE に遭遇したらその trans を問題にならない)
アボート (実際には READ PHASE は極めて短くほとんど• 最後に release
遭遇できない)release(trans_desc *td, int i) {trans_entry te = td.entries[i];if(td.status == COMMITED)
CAS(orec_of(te.addr), td, te.new_version)
elseCAS(orec_of(te.addr), td, te.old_version)}

6.14

Avoiding Searching□ 各トランザクションのアクセスには時間局所性→ orecからエントリをマップする表に最近アクセスしたものをキャッシュ。読んで書く場合に効果的

6.9

STMValidate
6.15□ 現在の trans のアクセス対象がすべて想定するバージョ

Non-blocking commit□ STMCommit() はこれまでのところ、他人が orec を取っン番号を持つかチェックていたらそれが終わるのを待つしかなかった→所有権を「盗む」ことで non-blocking 化。問題は次の 2 点5□ 盗人がどの場所の論理的な値も変更しないようにする

7.2

こと

Memory management□ ディスクリプタは普通に GC されるヒープに。

• 持ち主を ABORT して持ち主のディスクリプタの内容• 評価実験では再利用可能なディスクリプタをスレッを自分のものにマージする

ドローカルにプールする方式 [13]。ディスクリプタ□ 持ち主が COMMIT していた場合は書き戻し終わってからの割り当て/開放は STM 操作に掛かる時間の 2%。

新しい持ち主が書くことを保証すること• orec は静的割り当て。

• 全員の書き込みが終わって値が最後のトランザクショ• 評価実験では 65535 個を割り当てアドレスのビット2〜18 を対応させた。4096 に減らしても 1%未満の違ンのものになっていることを確認してから releaseいだった。

する→ orec にカウンタを用意して acquire で up、release で down する。自分が所有権を盗まれたことが分かった時は「新しい」所有者の更新を実行する

7.3□ STMWait() は non-blocking でない (今のところ)。変Version number□ 奇数の整数を使用 (orec へのポインタと区別のため)。

更も可能• オーバフローは考慮しなかったが、たとえば全スレッドを止めてトランザクションは ABORT させ 1 に戻す

7IMPLEMENTATIONEVALUATION

ANDとか (GC でもどうせ止めるし)• CAS は 2 ワード (カウンタも必要なため)□ Sun JVM 1.2.2 を改造して実装。比較対象は JVM でも7.4改良された版

Performance□ 共有メモリ MP ではキャッシュの競合を避けることが性

7.1

能向上のポイント。アプリケーションコードについては

Modifications to the JVM and compilers

プログラマの責任 (CCR であってもなくても)。
□ 実装に際してはよくあるケースを特別化。

□ バイトコードへの翻訳とバイトコードから native への• 例: STMCommit() はまず楽観的に競合なしと思って実行し、他人のディスクリプタが見つかったら通変換の 2 つを併せて実装 (.class ファイルのフォーマットは変更なし)

常の方法に変更 (1%未満)• atomic ブロックはメソッド単位となっている (メソッ

ドになってないものは翻訳時にメソッドとして抽出)。 □ コミットまではどのトランザクションもローカルに動けることに注意
名前に印をつける• この中でローカル変数は通常通りアクセス。フィー □ 競合がない場合、r 箇所を読み w 箇所を書く trans は← CAS × w、読み× r、ステータス更新× 2、書き× w、ルドアクセス、配列要素アクセスは STMRead()、CAS × w。
STMWrite() に。
• 各クラスに 2 つ目のメソッドテーブルを追加。トラ
ンザクション版のメソッド (必要に応じて変換) を7.5キャッシュ。

Experimental set-up• native へ の ト ラ ン ス レ ー タ は ル ー プ 中 に □ Hashtable、Compound、Wait の 3 つの設定で実験STMValidate() チェックを挿入 (図 4 の例参照)□ CCR と JVM の条件変数とを比較• volatile フィールド読み書きは小さい trans とし □ 3 秒間実行し回数計測、5 回のメディアンを取るて実行

67.6• atomic 文以外…reflective (トランザクション中か、何にアクセスしているか、など見たりする)

Small systems□ 4CPU SunFire v480

• I/O のようなもの (副作用) →トランザクションの中• ConcurrentHashMap(複雑な実装) がよいが、CCR も悪くない。競合が増えると CCR の方がよくなってくる

7.7

断/再開とか callback とか□ Implementation-level interface• word level vs object level とか入れ子トランザクションとかLarge sytems□ 106CPU SunFire e15k (ccNUMA)□ Alternative STM implementations• ConcurrentHashMap がよい場合もわずかにあるが• 現在の実装が不得手な場面でうまく動く実装とかCCR が一貫してよい。

□ Hardware support

7.8• どんなハードがあるといいかとかソフトとのインタフェースとかSTM performance summary□ 競合しないトランザクションは完全に並行□ Summary□ 競合が少なければ単一ロックが「その場で操作」できる□ Acknowledgement

ので速い□ 細粒度ロックはロックの数が増えすぎなければ速い□ CCR は STM インターフェースを常に使うから最初はコストがかさむが動的な競合がない限り並列に実行可能なので最もスケーラブル• 「likely to be dynamically non-conflicting」
なものに向く• hot spot を避けるプログラミングに該当

7.9

Ease of programming□ CCR 型のプログラミングスタイルはいいか?

• 昔からよく使われている、分かりやすい• データベースのトランザクションとの類似性→簡潔なセマンティクス• Java で考えると…wait/notify 不要なものは同じ(性能は CCR が上)、必要なものはずっと分かりやすい

8

DISCUSSION AND FUTURE
WORK□ Benchimarking and evaluation• さまざまなデータ構造、ベンチマークで…
□ Language-level interface

7