Package: Util.Tasking.Complex_Locks

Dependencies

with Ada.Finalization;
with Ada.Task_Identification;
with Ada.Unchecked_Deallocation;

Description

Copyright © 2002 by Thomas Wolf.
This piece of software is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This software is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License with this distribution, see file "GPL.txt". If not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
As a special exception from the GPL, if other files instantiate generics from this unit, or you link this unit with other files to produce an executable, this unit does not by itself cause the resulting executable to be covered by the GPL. This exception does not however invalidate any other reasons why the executable file might be covered by the GPL.

Version: 1.1

Author:
Thomas Wolf (TW) <twolf AT acm DOT org>
Purpose:
Provides a read-write lock type that fully supports lock promotion and demotion, keeps track of the tasks currently holding a lock, and that handles deserters. Conflicts arising when more than one task requests a lock promotion from shared to exclusive mode can be handled through a user-defined conflict resolution policy.

This type of lock is provided in a separate package because it is rather complex, and we want to avoid dragging in all these complexities when only the way simpler locks from package Util.Tasking.Locks are needed.

Storage Semantics
Dynamic memory allocation in the standard storage pool(s).
Tasking Semantics
Fully task- and abortion-safe; deserters are handled.

Header

package Util.Tasking.Complex_Locks is
 
pragma Elaborate_Body;

Exceptions

Promotion_Error
May be raised if several tasks request a lock promotion from shared to exclusive access on the same Task_Read_Write_Lock.

Type Summary

Conflict_Resolver (abstract type)
Primitive Operations:  Decide
Lock_Holder_Mode
Lock_Mode derived from Lock_Holder_Mode
Task_Read_Write_Lock (protected type)
Task_Read_Write_Lock_Protector derived from Limited_Controlled
Overridden Operations:  Finalize, Initialize
TRWL_Data (limited type)

Constants and Named Numbers

Read_Only : constant Lock_Mode := Shared;
Read_Write : constant Lock_Mode := Exclusive;
"Renamings" for convenience.

Other Items:

type Conflict_Resolver is abstract tagged private;
A Conflict_Resolver is used as the "hook" to install a user-defined lock promotion conflict resolution policy in a Task_Read_Write_Lock.

function Decide
  (Self        : access Conflict_Resolver;
   Queued_Task : in     Ada.Task_Identification.Task_Id;
   New_Task    : in     Ada.Task_Identification.Task_Id)
  return Boolean
  is abstract;
If Decide returns True, a Task_Read_Write_Lock raises the exception Promotion_Error in New_Task, otherwise it raises it in the queued call to Acquire from Queued_Task. This gives you the leverage to implement your own application dependent conflict resolution for multiple lock promotion requests.

Note that Decide will be invoked from within a protected action; it therefore must not do any potentially blocking operations (such as I/O, or entry calls).


type Lock_Holder_Mode  is (Not_Holder, Shared, Exclusive, Shared_Exclusive);
A task can either not hold a given lock at all (Not_Holder), hold it in Shared or Exclusive mode, or hold it in shared mode but be waiting to get a promotion request granted (Shared_Exclusive).

type Lock_Mode         is new Lock_Holder_Mode range Shared .. Exclusive;
A lock can be held either in Shared or in Exclusive mode.

type TRWL_Data is limited private;
We just need to declare this type here because it will be needed in the private part of the protected type below. It is not intended to be used anywhere else, and therefore, you won't find any operations on it here.

protected type Task_Read_Write_Lock is
 
A Task_Read_Write_Lock is the most sophisticated type of lock the Util subsystem provides. Like the Read_Write_Lock, it can be locked for exclusive (read-write) or shared (read-only) access. It also keeps track of the tasks that currently hold the lock (its holders). A holder may Acquire a lock several times and must Release it a corresponding number of times. A holder that holds the lock in shared mode is called a reader; an exclusive holder is called a writer. A Task_Read_Write_Lock does handle deserters, i.e. tasks that terminate while still holding the lock.

A Task_Read_Write_Lock allows several readers, but only one writer (and no readers while there is a writer) at any time. It is a fair lock, i.e. it is starvation-free. (Well, nearly; higher priority tasks may still keep crowding out lower priority ones, but that is in the spirit of Ada tasking, and so I consider this to be acceptable. See the comments in Util.Tasking.Locks on the Read_Write_Lock for more details of the mechanism used.

A Task_Read_Write_Lock supports lock promotions: a reader may request exclusive access (by calling Acquire (Exclusive)) and may be granted exclusive access and thus become a writer without relinquishing the lock. A lock promotion is thus atomic.

Lock promotions on read/write locks are a source of either deadlocks or general confusion. A lock promotion is only possible when the requesting reader is the only lock holder. If there are two different holders both requesting a lock promotion, either a deadlock would occur, or lock promotion wouldn't be atomic anymore and thus not offer any advantages over simply giving up the read lock and re-acquiring it again in exclusive mode.

(To see this, consider a case where two reader tasks request lock promotion to exclusive access on the same lock. They'd both block until they were the only two readers on the lock, and then one of them would have its request granted. When it then finished and released the lock, the other reader would get its promotion request granted, but in the meantime, the first task has had exclusive (write) access to the protected resource, and thus the second task couldn't rely on the resource's state still being the same as it was at the time it issued its promotion request: the promotion wouldn't be atomic anymore.)

Therefore, there can be only one lock promotion request. A promotion request blocks the requesting reader until it is the only reader left, and is then granted, at which moment the reader becomes the writer. The question now is what to do if a second promotion request arrives from some other reader, while the first reader's promotion request is still blocked.

A Task_Read_Write_Lock gives the user control over this: it uses a user-defineable conflict resolution policy to decide which of the two requests shall be aborted by raising a Promotion_Error exception. The default policy is to accept only the first request, and to abort all others, regardless of the task priorities of the two reader tasks. However, one may install a Promoter conflict resolver overriding this default behavior. E.g. to accept the request of the task with the higher priority, one might use:

     type Priority_Conflict_Resolver is
       new Conflict_Resolver with null record;

     function Decide
       (Self        : access Priority_Conflict_Resolver;
        Queued_Task : in     Ada.Task_Identification.Task_Id;
        New_Task    : in     Ada.Task_Identification.Task_Id)
       return Boolean
     is
        use type System.Any_Priority;
     begin
        return Ada.Dynamic_Priorities.Get_Priority (New_Task) <=
               Ada.Dynamic_Priorities.Get_Priority (Queued_Task);
     end Decide;
  

and install an object of this type as the conflict resolution policy of the lock. In fact, because this particular policy may be used often, it is provided in package Conflict_Resolvers .

Lock demotions also are supported: if the writer task calls Demote, it gives up its exclusive access and retains the lock only in Shared mode, i.e. it becomes a reader. Again, lock demotion is atomic: no other waiting writer can acquire the lock. (If there are waiting readers, these will then acquire the lock in shared mode, too.)

A lock request through Get or Acquire is granted if:

  • the calling task is not currently a holder:
    if Mode = Shared
    if there are only readers.
    if Mode = Exclusive
    if there are no readers and no writer.
  • the calling task is currently a reader:
    if Mode = Shared
    always.
    if Mode = Exclusive
    if the calling task is the only reader (lock promotion).
  • the calling task is currently the writer:
    if Mode = Shared
    always (the lock remains locked for exclusive access).
    if Mode = Exclusive
    always.

(But note that all requests are queued, and the queue is processed in order. So if there's an exclusive or promotion request at the head of the queue, and that request cannot be granted, requests later in the queue remain blocked even if they could be granted. Hence jumping the queue is forbidden to avoid starvation of writers. The only exception to this is promotion requests: even if the request at the front of the queue cannot be granted, a promotion request later in the queue will be granted (if it can). This, too, is necessary because otherwise we'd deadlock when a writer and a promotion request were on the queue. Yet this cannot starve a writer, because there can be at most one promotion request on the queue at any time.)

If a lock holder acquires a lock several times (including lock promotions), it must also release the lock the same number of times to relinquish it. Lock demotions don't count, though. Hence after

My_Lock.Acquire (Exclusive); My_Lock.Demote;

there needs to be one call to Release, not two. Basically, a task needs a Release for each Acquire that doesn't raise an exception, and for each Get that returns Granted = True.

procedure Set_Conflict_Resolution
  (Resolver : in Conflict_Resolver'Class);
This installs a copy of Resolver in the lock to be used to resolve conflicting lock promotion requests.

procedure Set_Default_Conflict_Resolution;
Reverts to the default conflict resolution policy.

entry     Get
  (Mode    : in     Lock_Mode;
   Granted :    out Boolean);
Try to obtain the lock. If there are no pending calls to Acquire and the lock can be granted for the given Mode, the calling task obtains the lock in the given Mode and Granted is True, else Granted is False. This call never blocks; it's an entry solely to be able to get the caller's task ID. Note that if the Mode indicates a lock promotion (i.e. the calling task is a reader and Mode = Exclusive), and there already is a waiting promotion request from another reader, Get returns with Granted = False; the installed conflict resolution policy (if any) does not come into effect in this case.

entry     Acquire
  (Mode : in Lock_Mode := Shared);
Tries to obtain the lock in the indicated Mode. The call blocks if the request cannot be granted right away, until it can. Note that if the mode indicates a lock promotion (the calling task is a reader and Mode = Exclusive), the call may also propagate the exception Promotion_Error either immediately of after having been blocked for some time (if a user-defined conflict resolution policy later decides to abort the queued request).

entry     Abandon;
Never blocks; it's an entry solely to get the caller's task ID. If the calling task is not a lock holder, Tasking_Error is raised. Otherwise, release the lock as many times as the calling task had acquired it.

entry     Release;
Never blocks; it's an entry solely to get the caller's task ID. If the calling task is not a lock holder, Tasking_Error is raised. Otherwise, releases the lock once without changing the lock mode of the calling task.

entry     Demote;
Never blocks; it's an entry solely to get the caller's task ID. If the calling task is a writer, a lock demotion occurs: the writer atomically becomes a reader (i.e., holds the lock in shared mode henceforth), thus allowing other waiting readers to also acquire the lock. If the calling task is a reader, this is a no-op, and if it isn't a holder of the lock at all, Tasking_Error is raised.

function  Queued return Natural;
Returns the number of callers waiting to obtain the lock.

function  Writer return Ada.Task_Identification.Task_Id;
If there is a writer, returns that task's task ID, or Null_Task_Id if there is no such task.

entry     Holding (Mode : out Lock_Holder_Mode);
Returns in Mode whether or not the calling task is a holder of the lock, and if so, in which mode it holds the lock. This is an entry solely to get the caller's task ID; the entry never blocks.

function  Holds
  (TID : in Ada.Task_Identification.Task_Id)
  return Lock_Holder_Mode;
As Holder, but it checks whether the task denoted by TID is a holder of the lock. Returns Shared_Exclusive if the that task is a reader waiting for a lock promotion to exclusive access.

private

entry Wait (Boolean) (Mode : in Lock_Mode);
Regular requests by non-holders end up here. Only one of the two queues is ever active. (When we check, but cannot service a request here, we requeue all requests to the other queue to avoid problems with queue ordering because we will already have taken the frontmost request off the queue when we check. If we'd requeue on the same queue, ordering might go wrong.)

entry New_Promotion;
A new promotion request will be "parked" here, if there already is a waiting promotion request on the 'Promote' queue and the conflict resolution policy decided to abort the already queued request. A request will be parked here only temporarily, until the other request has been killed. Then it is moved over to the 'Promote' queue.

entry Promote;
A waiting promotion request will be queued here.

Data : TRWL_Data;
end Task_Read_Write_Lock;

type Task_Read_Write_Lock_Protector
  (Lock : access Task_Read_Write_Lock;
   Mode :        Lock_Mode)
is
  new Ada.Finalization.Limited_Controlled with null record;

procedure Initialize (Self : in out Task_Read_Write_Lock_Protector);

procedure Finalize   (Self : in out Task_Read_Write_Lock_Protector);

private

   --  Implementation-defined ...
end Util.Tasking.Complex_Locks;