From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,3ccb707f4c91a5f2
X-Google-Attributes: gid103376,public
From: geert@fozzie.sun3.iaf.nl (Geert Bosch)
Subject: Re: Fast locking (Was Re: Java vs Ada 95)
Date: 1996/11/06
Message-ID: <55r16k$m00@fozzie.sun3.iaf.nl>
X-Deja-AN: 195014066
references: <325BC3B3.41C6@hso.link.com>
 <EACHUS.96Nov1103759@spectre.mitre.org> <E07Dwq.5L@world.std.com>
 <55gkch$gg6@fozzie.sun3.iaf.nl> <E0B6CL.84r@world.std.com>
 <dewar.847053681@merv> <55o4g4$ki8@fozzie.sun3.iaf.nl>
 <1996Nov5.235745.1@eisner>
organization: La Calandre Infortunee
newsgroups: comp.lang.ada
Date: 1996-11-06T00:00:00+00:00
List-Id: <comp.lang.ada>


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