1. スレッドライブラリへの抽象状態同期の導入
- Author
-
Ohki, Atsuo and Kuno, Yasushi
- Subjects
ComputingMethodologies_DOCUMENTANDTEXTPROCESSING - Abstract
application/pdf, スレッドライブラリは共有メモリ型マルチプロセサシステムにおいて並行プログラミングを行う標準的な手法の1つである.現在世の中に普及しているスレッドAPIであるPOSIX Thread準拠のものをはじめとする多くのライブラリでは,スレッド間の条件同期の方法として,条件変数(condition variables)を採用している.しかし,条件変数を用いたコード記述は読解しにくく誤りの原因となりやすい.このため,条件変数を1つだけ用意し, すべての条件同期をこの1つの条件変数で待ち合わせる方法が使われることが多い.Java言語における標準の待合せ機構も実質的にはこれに相当する.しかし,この方法ではすべてのスレッドが条件イベントごとに実行を再開し,自分が続行できる条件でない場合は再度待合せに入るため,オーバヘッドが大きい.本論文では,筆者らが考案した抽象状態同期と呼ばれる同期機構をスレッドライブラリAPIに組み込むことを提案する.抽象状態同期では,排他領域により守られているデータ構造の状態を数個の状態に抽象化して考え,そのどれとどれに相当する場合に各操作が領域内に入れるかを指定することで読みやすく効率的なコードを作成できる.本論文では具体的なAPIの提案,その試験実装,性能評価,コードの書きやすさなどについても報告する. Thread libraries are widely used for concurrent programming on shared-memory multiprocessors. On POSIX Thread and other well-known thread libraries, condition variables are used for conditional inter-thread synchronization. However, code with multiple condition variables are difficult to understand and error-prone. Hence, programming style with single condition variable is widely used. Standard synchronization scheme on Java programming languages is effectively designed likewise. However in this scheme, all threads are woken up on each event and have to check for their continuing conditions repeatedly, leading to large overhead. In this paper we propose to incorporate state abstraction-based synchronization into thread libraries. In our scheme, state of the data structure guarded by an mutex is mapped to small number of "abstract states." Every mutex acquisition are guarded by a set of abstract states on which the processing can continue. We also report our API proposal, along with experimental implementation, performance evaluation and some discussion on code readability.
- Published
- 2006