Package: Util.Tasking.Locks

Dependencies

with Ada.Task_Identification;

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:
Various useful lock types. Note that in general it's better to encapsulate your shared data properly in protected objects than using explicit lock POs, which always are in some sense an abstraction inversion. Code using explicit locks may be prone to suffer from priority inversions. However, there are situations in which you just cannot use PO encapsulation, e.g. when one of the protected operations should do potentially blocking calls such as any I/O. In such cases, you need to use explicit locks, and this package provides the most commonly needed ones.

Also see package Util.Tasking.Protectors for some controlled types that help using these locks in an exception- and ATC-safe way.

Storage Semantics
No dynamic storage allocation.
Tasking Semantics
Fully task- and abortion-safe. Only the Task_Lock locks handle deserters; other lock types don't, and it's the application's business to ensure that such locks are properly released even in the presence of exceptions and ATC.

Header

package Util.Tasking.Locks is
 
pragma Elaborate_Body;

Type Summary

Lock (protected type)
Read_Write_Lock (protected type)
Task_Lock (protected type)

Other Items:

protected type Lock is
 
A simple lock. Once locked, any subsequent calls to Acquire including ones by the task that holds the lock will block until the lock is released.

This type of lock does not keep track of its lock holder: the task holding the lock and the one releasing it may be different. It's the application's responsibility to ensure correct sequencing of calls to Acquire and Release.

procedure Get (Granted : out Boolean);
Try to acquire the lock. If the lock is currently not held, the calling tasks obtains the lock and Granted is True, otherwise Granted is False.

entry     Acquire;
Tries to obtain the lock. If the lock is currently held, this call blocks until the lock is released and then obtains the lock.

procedure Release;
Unlocks the lock. A no-op if the lock is not currently held.

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

private

Locked : Boolean := False;
end Lock;

protected type Read_Write_Lock is
 
A fair reader-writer lock, allowing multiple readers but only one writer.

A Read_Write_Lock guarantees to starve neither readers nor writers. To avoid starvation, a Read_Write_Lock puts all requests onto the same queue. A read request is granted if the lock is not currently held by a writer, otherwise it is queued. A write request is granted only if the lock is currently not held at all. Since all requests end up on the same queue, read requests arriving after a write request that is blocked because the lock is currently held are blocked, too, even if the lock is held by readers only. This ensures that readers cannot starve writers. And since we assume that the current lock holder(s) eventually terminate and release the lock, such a blocked writer will eventually get the lock, and once it finishes and releases the lock, the waiting readers may then get the lock. Hence writers cannot starve readers, either.

All this is true if we disregard task priorities. If tasks have different priorities, it is still possible for higher-priority tasks to crowd out requests from lower-priority ones, but that is in the spirit of Ada tasking, and so I consider this to be ok.

Like the simple lock above, this type of lock does not keep track of the task that currently holds it. (As there may be several readers holding the lock simultaneously, that wouldn't make much sense anyway.)

procedure Get
  (Read_Write : in     Boolean;
   Granted    :    out Boolean);
Tries to obtain the lock. This only succeeds if the lock currently isn't held, and there are no pending calls to Acquire. The latter condition is to ensure that calls to Get cannot overtake pending calls to Acquire.

entry     Acquire (Read_Write : in Boolean := False);
Blocks until the lock can be obtained for read-only or read-write access.

procedure Release;
Releases the lock. If there is currently a writer, it is assumed that the read-write lock is to be released. If there are only readers, it is assumed that one reader releases the lock. If there are neither reader not writers, the call has no effect.

function  Queued  return Natural;
Returns the total number of tasks waiting to obtain the lock in either mode.

private

Readers : Natural := 0;

Writer  : Boolean := False;

Change  : Boolean := False;

entry Wait (Boolean) (Read_Write : in Boolean);
Wait (Active_Queue) is the queue that queues up all requests for obtaining the lock in either mode. Requests queued here are processed whenever the lock is not currently held by a writer. For more information, see the comments in the implementation.

Active_Queue : Boolean := False;

Pass_Through : Boolean := False;
end Read_Write_Lock;

protected type Task_Lock is
 
A lock which keeps track of who currently holds the lock. The same task may acquire the same lock several times, but must also release it that many times. If a task tries to release a lock it doesn't hold, the exception Tasking_Error is raised.

Locks of this type do attempt to handle deserters gracefully. A deserter is a task that terminates while still holding the lock. In Get and Acquire, a Task_Lock checks whether the current lock holder (if any) has terminated, and if so resets the lock. Note however that a task that is blocked awaiting the termination of its children is not terminated yet, and that this waiting occurs as the first step in the finalization of a task body. Hence the lock may be held by a completed task. However, we cannot force a release in this case because other finalization of the task might still need the lock. So you still have to be a bit careful, for it is still possible to get into troubles in some pathological cases if you have deserters that have dependent tasks which use the same lock.

entry     Get (Granted : out Boolean);
Try to obtain the lock. If the lock is currently not held, the calling tasks obtains the lock and Gotten is True, otherwise Gotten is False. This call never blocks; it's an entry solely to be able to get the caller's task ID.

entry     Acquire;
Tries to obtain the lock. If the lock is currently held by another task, this call blocks until the lock is released and then obtains the lock.

entry     Abandon;
Unlock the lock exactly the number of times it had been obtained. If the lock is currently not held by the calling task, the exception Tasking_Error is raised. Never blocks; it's an entry solely to get the caller's task ID.

entry     Release;
Never blocks; it's an entry solely to get the caller's task ID. If nobody currently holds the lock, this is a no-op. If the lock is held by some other task, Tasking_Error is raised.

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

function  Holder return Ada.Task_Identification.Task_Id;
Returns the current lock holder's task ID, or Null_Task_Id if the lock is currently not held.

private

entry Wait;

Owner : Ada.Task_Identification.Task_Id :=
  Ada.Task_Identification.Null_Task_Id;

Count : Natural := 0;
end Task_Lock;
end Util.Tasking.Locks;