To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
State Abstraction-based Synchronization for Thread Libraries |
|
Author |
Atsuo Ohki, Yasushi Kuno |
| Citation |
Vol. 7 No. 6 pp. 36-44 |
|
Abstract |
“State Abstraction” is a framework in which states of a data structure (or an object) are divided into small number of exclusive sets (“Abstract States,” or AST), and current abstract state is explicitly managed by the code. In “State Abstraction-based Synchronization” (or AST-sync), abstract states of the data structure guarded by a critical region are similarly managed, and an activities can enter the region only when current state is included in the pre-specified set. For example, in a bounded buffer, “get” operation can proceed only in “full” or “mid” state, but not in “empty” state. AST-sync can express conditional synchronization in concise and readable manner, and can be efficiently implemented. Today, 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 in those APIs, complex conditional synchronization using 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. In this scheme, all threads are woken up on each event and have to check for their continuing conditions repeatedly, leading to large overhead. Thus, we are proposing an alternative conditional synchronization scheme and associated API for thread libraries based on AST-sync. In our scheme, every mutex acquisition are guarded by a set of abstract states on which the processing can continue. In this paper, we report our kernel-level implementation of AST-sync based on multiprocessor-capable POSIX thread library bundled in FreeBSD 6.0-RELEASE, and its performance evaluation using micro benchmarks. As the result, we have observed 2--3 times speedups against popular “repeated tests” type synchronization code for some cases. |
|
Keywords |
Conditional Synchronization, Thread Libraries, Condition Variables, Guards |
|
URL |
