Frequency-based Constraint Relaxation for Private Query

IR IPSJ HANDLE Web Site Open Access

Bibliographic Information

Other Title
  • 抽象状態同期による高機能ロックの実装と評価
  • チュウショウ ジョウタイ ドウキ ニ ヨル コウキノウ ロック ノ ジッソウ ト ヒョウカ

Search this article

Description

抽象状態とは，データ構造ないしオブジェクトの状態を複数の（あまり多くない，抽象化された）集合に排他的に分割し，現在の状態がそのいずれに含まれるかを明示的に管理する方式をいう．抽象状態同期とは，排他領域によってガードされる対象の抽象状態を同期機構側で保持し，スレッドなどの実行主体が排他領域に入れる条件を抽象状態の集合として表現する方式である．筆者らは先行研究において，抽象状態同期をOSカーネル内で実装することで，従来の実装方式では難しかった，可読性と効率を両立させた条件同期記述が可能であることを示した．本論文では，読み書きロックやバリア同期に代表される，単純な排他領域よりも込み入ったセマンティクスを持つ同期機構が，抽象状態同期を用いて簡潔かつ効率良く実装可能であり，抽象状態同期がさまざまな同期機構を効率良く実装するための基本的枠組みとしての特性を備えることを示す．

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 similary managed, and an activity can enter the region only when the current state is included in the pre-specified set. In our previous research, we have implemented AST-sync inside an OS-kernel and have shown its effectiviness (in readability and performance) for standard conditional synchronization (aka. bounded buffers). In this paper, we demonstrate use of AST-sync to construct more complex synchronization mechanisms such as read-write locks or barriers, in simple and efficient manner.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top