Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Integrated Concurrency Control/CPU Scheduling

IP.com Disclosure Number: IPCOM000119563D
Original Publication Date: 1991-Feb-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 180K

Publishing Venue

IBM

Related People

Franaszek, PA: AUTHOR [+3]

Abstract

Disclosed is a method for integrating the functions of concurrency control and CPU scheduling in online transaction processing systems. This method is expected to be more robust (in terms of achieving optimal performance) than any methods currently in use or that previously have been proposed, since it dynamically adapts to the CPU and IO requirements of transactions and to the level of contention in the system.

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

Integrated Concurrency Control/CPU Scheduling

      Disclosed is a method for integrating the functions of
concurrency control and CPU scheduling in online transaction
processing systems.  This method is expected to be more robust (in
terms of achieving optimal performance) than any methods currently in
use or that previously have been proposed, since it dynamically
adapts to the CPU and IO requirements of transactions and to the
level of contention in the system.

      All existing and previously proposed approaches to the problem
of concurrency control in transaction processing systems have
separated the functions of concurrency control and CPU scheduling.
For example, using a locking approach (the method in most widespread
use today), a lock manager determines some subset of transactions
runnable (the remaining transactions are blocked by a lock request),
and it is then up to the CPU scheduler to actually run these
transactions on an available processor.

      In the future, the separation of functions described above
could lead to severe problems.  This is because the optimal
concurrency control policy depends on a combination of various system
parameters, including the CPU and IO requirements of transactions,
the transaction mix, the total CPU processing capability available
(system MIPS), the number of processors, the IO bandwidth and IO
delay, and the level of contention.  For example, for low levels of
contention and low system MIPS, locking policies are generally
optimal among known practical concurrency control methods, since they
generate the least amount of wasted work.  However, increasing system
MIPS while holding other parameters constant, it will eventually
become impossible to fully utilize the processors in the system using
a locking policy, as has been shown in (1).  At various points other
policies will become optimal, such as those involving running
priority (1), optimistic methods (2), and two-phase processing and
simulation mode (3).

      First, disregarding simulation modes and two-phase processing,
in general there is a spectrum of concurrency control policies that
can be ordered by the size of the runnable set of transactions
determined by that policy.  A simple spectrum consisting of three
policies is as follows: (1)  standard locking determines a
transaction as runnable if for each data item accessed by that
transaction, either there is no conflict or else the transaction was
first among the set of conflicting transactions to request access to
that item; (2)  running priority adds to the runnable set those
transactions that have a conflict with a transaction that was blocked
by a member of the runnable set under standard locking; and (3)
optimistic methods determine all transactions as runnable.

      The basic idea is to assign each transaction a CPU priority
based on the depth of the lowest level runnable set of which it is a
member in such a spectrum of concurrency control polic...