データベースのロック割当て方式の解析

概要

論文の詳細を見る
Strategies for lock scheduling in a database system are discussed. A lock must be set in some mode when a database resource is accessed by a transaction, in order to prevent inconsistencies. This may cause a deadlock or significant queueing delays. In this paper a general model of wait-for graph is first developed. The model makes it possible to detect deadlocks for a multi-mode lock system, including artificial deadlocks. Though these artificial deadlocks may frequently occur under ordinary lock scheduling strategies, they have never been detected by the conventional wait-for graph model. Secondly, three lock scheduling strategies: First In First Out (FIFO), EXPediency (EXP), and First In Compatible First Out (FICOFO), are introduced and compared. Theoretical reasoning and simulations revealed the lowest and the highest deadlock frequency for EXP and FIFO, respectively. The deadlock frequency of FICOFO was between the two. In addition, EXP and FIFO each yielded the smallest and the largest queueing delays, for locks of high compatibility mode. However, for locks of low compatibility mode, significant queueing delays were observed in EXP, as compared with FICOFO and FIFO.
明治大学の論文