High Concurrency of Resource Allocation with Provision for Fairness
Original Publication Date: 1991-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Publishing Venue
IBM
Related People
Smet, AD: AUTHOR [+2]
Abstract
A resource allocation scheme with high concurrency bias will continue to grant new requests for internal locks to tasks, without regard to internal lock waiters. Disclosed is a method for delaying otherwise grantable internal lock requests in favor of requests of qualified lock waiters. This method avoids deadlock and only delays internal lock requests for tasks that have recently held internal locks on the resources waited on by the qualified lock waiters.
High Concurrency of Resource Allocation with Provision for Fairness
A resource
allocation scheme with high concurrency bias
will continue to grant new requests for internal locks to tasks,
without regard to internal lock waiters.
Disclosed is a method for
delaying otherwise grantable internal lock requests in favor of
requests of qualified lock waiters. This method avoids deadlock and
only delays internal lock requests for tasks that have recently held
internal locks on the resources waited on by the qualified lock
waiters.
A lock
discussed here is one which is internal to the operating
system, and is obtained and released only within operating system
functions. If a task is in between
operating system functions, then
no internal locks are held by the task.
A lock request may consist
of single or multiple internal locks.
In a
particular case when a resource is already allocated with
shared locks, a steady arrival rate of requests for shared locks and
for shared unlocks will cause a task requesting an exclusive lock to
repeatedly conflict and retry its request.
Such a task is considered
to be treated unfairly for it may have to wait a very long time to
have its exclusive lock request granted while new requests for shared
locks are granted. The task that is
treated unfairly must continue
waiting until the number of shared locks on the object is zero.
A method is
needed to reduce the high number of internal locks
on the resource involved. This implies
placing some tasks into a
wait state at appropriate points of execution so that the window of
resource availability is (temporarily) open for any task that is
treated unfairly. When placing some tasks into a wait state, deadlock
must be avoided as well as undue performance degradation brought
about by forcing a wait state onto tasks not involved with the
resource contention.
The
determination as to when a task has been treated unfairly
can be based on two criteria: the number
of times the task has
unsuccessfully retried its internal lock request, and/or the total
wait time of the request. The bias
toward high concurrency and
throughput can be controlled by adjusting the thresholds of these two
criteria.
The following
pseudocode describes the proposed solution:
Path used by task found to be
treated unfairly
UNFAIR := TRUE;
Do until internal lock request
is successful
Issue internal lock
request
If internal lock request
was unsuccessful then
MARK the task owning the
conflicting internal lock
End do;
UNFAIR := FALSE;
Release any waiters on FAIR
WAIT queue
Path used by all tasks for Internal
Lock Request
If UNFAIR = TRUE then
do;
...