導入

多数の並列オブジェクト指向言語が提案されている(例えば [2], [9], [16], [18], [19], [21], [22], [26], [28], [29]). 並列オブジェクトを用いる主要な利点は, オブジェクトに 対するメソッド起動が, そのオブジェクトに対する原子的 (または瞬間的)な操作とみなされるからである. その挙動はしばしばメソッドの「原子性」や「瞬間性」と 呼ばれ, 複数のプロセスによって共有されたmutableなデータ構造を 扱う並列プログラミングを簡単化する. この概念は それがどう実装されるかには無関係である [14].

メソッドの原子性を達成する直接的な実装は一つのオブジェクトに 対するメソッドの起動を実際にserializeすることである. しかし, これは並列実行の機会を減らすだけではなく, 安全な(つまりデッドロックなしの)プログラムの範囲を狭める. プログラマはしばしば普通と違う方法でアルゴリズムを記述 することを余儀なくされる. 典型的な例は(メソッド起動を通じて) 他方のオブジェクトのインスタンス変数を読む二つの並列 オブジェクトである. もしこれらの二つの並列オブジェクトが 他方のオブジェクトをほぼ同時に読もうとするときには, 多くの並列オブジェクト指向言語においてシステムはデッドロックする.

本研究ではこれまでの並列オブジェクト指向言語よりも 広い範囲の一つのオブジェクトへのアクセスを保証する 並列オブジェクトモデルを提案する. そのモデルはこれまでの 並列オブジェクト指向言語においてデッドロックになっていた ほとんどの場合を除去すると信じる. 提案するオブジェクト指向の モデルは並列オブジェクト指向言語 ABCL/f   [27] に採用されている. ABCL/f のオブジェクトモデルによってサポートされている並列性の型は 次のものである.

ロックのいらない読みだしオンリーメソッド

受信オブジェクトを 更新しないメソッド(読みだしオンリーメソッド)は常に先に進行し, 例え他の(書き込みも含む)メソッドの存在があるとしても 受信オブジェクトの一貫性のない状態(インスタンス変数を 更新中の状態)を観測することはない.

書き込みメソッドの部分的なオーバーラップ

複数の更新を行なう メソッド(書き込みメソッド)がオーバーラップすることができる. アイデアは, 書き込みメソッドはそのオブジェクトに対する 最後の更新が終わるとすぐにそのオブジェクトのロックを解除する というものである. このようにして, 我々はデッドロックの機会を 減らす一方で, メソッドの原子性を維持することができる. アイデアはActor [1] に遡り, SYMPAL [2] やUFO [23] のような最近のいくつかの言語もこの並列性を保証している.

一つのオブジェクトに対し複数のメソッド起動間の並列性を許す並列オブジェ クト指向言語はほとんど新しくない. 一つのオブジェクトに対して並列なアク セスを許す多くの言語が提案されている [2], [5], [10], [28]. しかし, 最近までは, それらの多くは他の並列メソッドの存在の下ではメソッ ドの原子性を保証しないという意味で安全ではなかった [7], [27], [30]. それらはただ単にプロ グラマ自身リスクにおいて, 複数のメソッドが並列に実行されること許してい るのみである. 加えて, 著者らの知る限り, それらはどれもロックのいらない 読みだしオンリーメソッドを許していない. 読みだしオンリーメソッドは典型 的なアルゴリズムの自然な記述にとって重要である(これまでの研究とのより 詳細な比較は 2.2.2節に述べる).

サポートされる並列性(つまりデッドロックしないプログラムの範囲)の 量とそのセマンティクスを実現するために払われなければならない オーバヘッドの間にはトレードオフがある. 例えば, 一つのオブジェクトに対するメソッド実行をserializeする だけの伝統的な並列オブジェクト指向モデルは受け入れ可能な オーバヘッド(メソッド起動ごとのロック/ロック解除)で実装することが 可能である. しかしこれは多くの重要なプログラムでデッドロックを ひき起こす. もう一方の極端なやり方としては, 全てのメソッドを ロックがいらない とし, 割り込まれたメソッド実行は再試行するものがある. この方法では, 排他制御に起因するデッドロックを完全に避けることが できるが, 無限回の再試行を行なう可能性が残っており, また, 再試行への準備は大きなオーバヘッドを伴う.

我々はこのような実装のトレードオフを考慮して並列オブジェクト モデルを設計した. のちに2.2.5節で述べるように. 我々の並列 オブジェクト指向モデルはオブジェクトにつき 一つのロックで実装されており, 再試行は全く伴わない. さらに, 読みだしオンリーのメソッドは受信オブジェクトに対して いかなる排他制御, ストア命令も行なわない. これはすべてのメソッドがなんらかの形での排他制御(またはメッセージキューの 操作)を必要とする他のほとんどの並列オブジェクトの実装と好対照をなす.

本論文の残りは次のように構成される. 2.2.2節は これまでの並列オブジェクト指向 言語および並列プロセスによって共有されるデータ構造を実装するための すでに提案された技法を再考する. 2.2.3節は並列オブジェクト指向言語での 保証並列性に対するある特定の要求を示すいくつかの例を与える. 2.2.4節は 我々の提案する並列モデルとABCL/f で採用されている文法を紹介する. 2.2.5節では 少ないオーバヘッドで望ましい並列性を実現するための 実装方式を概観する. 最後に, 2.2.6節で我々の研究のまとめを行なう.