Yin-Fu Huang and Yeh-Hao Chin
Institute of Computer Science
National Tsing Hua University
Hsinchu, Taiwan 30043, Republic of China
A non-2PL and deadlock-free concurrency control method, called the Ascending Order Locking Protocol (AOLP), is proposed. Based on AOLP, a serializable and deadlock-free scheduler can be built and its correctness is proved. To show the merit of AOLP, 2PL and AOLP are evaluated mathematically on a factor called the "Average Lock Range" (ALR). The mathematical results indicate that the ALR for 2PL is the worst case of AOLP regardless of the access sequence of a 2PL-based transaction.
Keywords: concurrency control, locking protocol, deadlock, mathematical analysis
Received May 20, 1988; revised March 6, 1989.
Communicated by Lin-Shan Lee.
*This work was supported by the National Science Council under Grant NSC75-0408-E007-11 and Grant NSC76-0408-E007-13.