Browse Prior Art Database

Extended Older Priority Concurrency Control

IP.com Disclosure Number: IPCOM000107366D
Original Publication Date: 1992-Feb-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 3 page(s) / 105K

Publishing Venue

IBM

Related People

Franaszek, PA: AUTHOR [+3]

Abstract

Disclosed is a method for dynamic deadlock-free concurrency control in a transaction processing system that has fewer restarts than some other previously known dynamic deadlock-free methods.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 51% of the total text.

Extended Older Priority Concurrency Control

       Disclosed is a method for dynamic deadlock-free
concurrency control in a transaction processing system that has fewer
restarts than some other previously known dynamic deadlock-free
methods.

      Two such previously known methods are as follows.
1.   The older priority (OP) method (see (1)) can be defined in this
fashion: on a lock conflict, the transaction issuing the lock request
is made to wait on all conflicting transactions with higher priority,
and all conflicting transactions with lesser priority are restarted.
If priority is defined by a starting timestamp (with earlier starting
times giving higher priority), this is equivalent to the "wound-wait"
method of concurrency control, in which arbitrarily long wait chains
are allowed provided they are in timestamp order.
2.   The WDL method of concurrency control (see (2,3)), a member of
WDL(1) (the family of methods in which wait depth is limited to one),
can be summarized as follows: on a lock conflict, (a) construct a
(possibly temporary) wait graph in which the transaction T issuing
the lock request waits on all conflicting transactions, (b) if the
depth of the graph exceeds one, then let X be the singleton set {T}
if T has transactions waiting on it, otherwise let X be the set of
transactions T is waiting on, (c) restart the transactions in X
unless the "combined length" of X is sufficiently large, in which
case, restart the set of transactions being waited on by transactions
in X. Note that in both cases of step (c) the wait depth is reduced
to one by restarting one or more transactions.

      In both the OP and WDL methods deadlocks are avoided without
global wait graph analysis.  This is accomplished by different
techniques: under OP cycles are avoided since waiting is permitted
only in priority order, and under WDL cycles are avoided since wait
chains of at most length one are allowed (and the smallest cycle has
length two). However, both of these methods accomplish this by
restarts which could be overly expensive in some systems.  The basic
idea of the new method disclosed here is to avoid deadlocks with
fewer restarts than either of these methods by using techniques of
both methods in an appropriate way.

      More precisely, in the Extended Older Priority (EOP) method,
wait chains of arbitrary length are permitted in priority order, and
in addition wait chains of length one are allowed regardless of
priority.  For simplic...