100220

箱作り運動続き。6個作りました。

今迄に作った箱を積み重ねるとこんなに。しかしまだまだ足りない。

FF13続き。一日一ダークマター運動。またやっと一個でた。現在四個。

無待機同期続き。

Wait-Free Synchronization

MAURICE HERLIHY

Digital Equipment Corporation

ACM Transactions on Programming Langages and Systems, vol.11, no.1,
January 1991,p124-149.


1. 導入

「並行物体」は並行処理によって共有されるデータ構造である。並行システム
において、並行物体を実装するアルゴリズムは多くの重要な問題の中心に位置
する。そのような物体を実装する伝統的な手法はきわどい領域を使うことに集
中していた: たった一つだけの処理が、その物体の操作をすることが許される。
それでも、きわどい領域は非同期、耐障害システムに適用するには貧弱である:も
しきわどい領域の中で欠陥のある処理が停止したり遅延した場合、欠陥のない
処理も進行できなくなってしまうだろう。無障害システムであっても、スケー
ジュール時間を使い尽したり、スワップアウトされるたり、ページフォルトや
キャッシュ落ちの結果として、予期しない遅延に遭遇する可能性がある。同様
の問題はいくつかのプロセッサは他のより速かったり、メモリの場所によって
はアクセス時間が遅いような、不均一なアーキテクチャにおいても起こる。

並行データ物体の無待機な実装はどの処理も他の処理の実行速度にかかわらず、
有限の数の処理でどのような操作も完了できることを保証する。無待機条件に
よって耐障害となる: どの処理も他の処理の失敗を検出できないこと、あるい
は、その処理の不定の速度の変化による、処理の完了から妨害されない。
無待機同期の基本の問題は以下に示すように表現される。

二つの並行物体XとYがあった時、YによるXの無待機実装は存在するか?

無待機処理が存在することを示すのは明解だ: それを表わせばいい。最近の文
献の多くはこの手法である。