High Concurrency of Resource Allocation with Provision for Fairness

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;
             ...