Re: Fast locking (Was Re: Java vs Ada 95)

[geert@fozzie.sun3.iaf.nl (Geert Bosch)]

Larry Kilgallen writes:
`` My presumption is that those folks have portable Ada code in mind.
   The machine semantics of test-and-set on whatever machine you are
   describing would seem to be somewhat different from the Alpha AXP
   load-locked/store-conditional semantics.  A higher level construct
   which supports portable programs seems better to me than something
   specific to test-and-set hardware semantics. ''

The Systems Programming Annex of the RM specifically advises atomic
read-modify-write operations like test and set, compare and swap etc.

I can't imagine there are many systems around these days that do not
provide efficient test-and-set semantics. Even the 8088 processor that
does not directly have a test-and-set instruction can easily emulate
one by doing an atomic swap between a processor register and a memory
location. On very simple processors it is almost always possible to
block all interrupts while doing the test-and-set.

Of course machines that do not have any instructions that can be used
to efficiently implement hardware-assisted locking will not have a
test-and-set intrinsic sub-program, but of course nobody expects to
magically be able to use hardware locking support when the target
platform does not have it. The point is that *when* it is available,
it should be usable in a consistent way.

Note that although test-and-set kind of mutual exclusion is a
very fast solution for locking resources for which is almost
never any contention, it certainly doesn't replace high-level
high-overhead locking provided by protected types.

The difference is that protected types provide strictly 
priority-based FIFO queuing which makes fair sharing of scarce
resources possible. It would be a good idea however to use
fast test-and-set locks in these as well.

The example below shows how to do this, when there is hardware
test-and-increment and decrement-and-test. Assumptions are
that the standard queuing is expensive (expensive system calls
involved) and non-queuing but blocking event semaphores are much
cheaper. I've verified that these assumptions hold on OS/2, but
I guess the situation is the same for other operating systems.

Implementing the solution below causes slightly more expensive
blocking/unblocking and essentially free locking/unlocking in absence
of contention for the lock. The semantics of the Fast_Queuing_Mutex
are exactly the same as for the Slow_Queuing_Mutex, although some
bookkeeping should be added to record the priority for the task
owning the fast-lock in case of Ceiling_Locking policy.

Example: (untested incomplete code, details might be wrong)

type Fast_Queuing_Mutex is record
   Slow_Lock	        : Slow_Queuing_Mutex; 
   Fast_Lock    	: Integer := 0;
   Fast_Lock_Ready      : Event_Semaphore := Not_Posted;
   Have_Slow_Lock	: Boolean := False;
end record;

procedure Request (L : in out Fast_Queuing_Mutex) is
   Was_Zero	: Boolean;
begin
   Test_And_Increment(L.Fast_Lock, Was_Zero);
   if Was_Zero then
      -- We have lock without any overhead
      return;
   else
      -- The fast lock already was in use.
      -- Now wait in the queue for the Mutex,
      -- (No wait if we're first)
      Request_Mutex(L.Slow_Lock);   
      -- We also have to wait for the fast lock
      -- This can be done using a non-priority based
      -- event semaphore
      Wait_Event(L.Fast_Lock_Ready);
      -- Can't set this before fast lock is released
      L.Have_Slow_Lock := True;
   end if;
end Request;

Article Unavailable