Two-stage suspend operations

Two-stage suspend operations

[Simon Wright]

ARM D.10 says (since Ada95)

   This subclause describes a language-defined private semaphore
   (suspension object), which can be used for two-stage suspend
   operations and as a simple building block for implementing
   higher-level queues.

I've spent some time googling "two-stage suspend operations" and come up
empty. I did eventually think to look in the Ada 95 Rationale, and there
is an explanation in the corresponding section of Part 3 (which I will
have to think about some more):
http://www.adaic.org/resources/add_content/standards/95rat/rat95html/rat95-p3-d.html#10

Has anyone any other references?

Re: Two-stage suspend operations

[rieachus]

On Saturday, May 7, 2016 at 12:13:19 PM UTC-4, Simon Wright wrote:
> 
> I've spent some time googling "two-stage suspend operations" and come up
> empty... 
> 
> Has anyone any other references?

Try "two phase locking" you should get about a million hits, and the first few I looked at were all on topic.

Re: Two-stage suspend operations

[Simon Wright]

rieachus@comcast.net writes:

> On Saturday, May 7, 2016 at 12:13:19 PM UTC-4, Simon Wright wrote:
>> 
>> I've spent some time googling "two-stage suspend operations" and come
>> up empty...
>> 
>> Has anyone any other references?
>
> Try "two phase locking" you should get about a million hits, and the
> first few I looked at were all on topic.

I don't see the connection; they're all about database locking, e.g

   "A transaction is said to follow the two-phase locking protocol if
   all locking operations (read_lock, write_lock) precede the first
   unlock operation in the transaction. Such a transaction can be
   divided into two phases:"

Re: Two-stage suspend operations

[rieachus]

On Sunday, May 8, 2016 at 3:26:30 PM UTC-4, Simon Wright wrote:
> I don't see the connection; they're all about database locking, e.g...

The Ada Rationale is explaining an optimization based on having a single task/thread that can set the semaphore.  This allows the waiting on the semaphore to be combined into a single action--you don't need to acquire a read lock if this thread is the only one that can reset the semaphore.

In the more general database case, several processes may want write access to the semaphore--it is not owned by a single thread in a single process.  Now you need to acquire the read lock (preventing other writers) before acquiring the write lock.

If you think about the problem as efficiently guaranteeing that all requests are serviced, they are dealing with the same issue.  Take a particular example such as managing a log file and work it through.  The Ada solution discussed here is highly efficient (and works) if the file is owned (opened for writing) by a single thread.  The cost of the Ada solution is that you need a separate named protected object for each file or device managed.  You may be able to find discussions of this protocol in the context of file systems.  However, my experience is that file systems depend on tasks/threads not sharing files open for writing to avoid garbage.

Re: Two-stage suspend operations

[Simon Wright]

I see what you mean. It's just that the wording in the ARM made it sound
as though "two-stage suspend operations" was a phrase widely known in
the community, which clearly isn't the case.

Re: Two-stage suspend operations

[rieachus]

On Monday, May 9, 2016 at 4:56:15 AM UTC-4, Simon Wright wrote:
> I see what you mean. It's just that the wording in the ARM made it sound
> as though "two-stage suspend operations" was a phrase widely known in
> the community, which clearly isn't the case.

If you look at this article from Wikipedia: https://en.wikipedia.org/wiki/Two-phase_locking  and go down to "strong strict two-phase locking" you will see that it is not you, me or the Ada Rationale.  There are a lot of inconsistent names floating around in this area, and the Rationale apparently chose one that lost out. (Strong strict two-phase locking may not interest you, I just picked the article as one showing considerable name confusion in 2011.)

I'm curious as to why you are interested in this area.  Ada is a great language for implementing in memory databases.  At MITRE I worked on both ground based and in-flight radar systems.  The emphasis was on consistency and non-blocking. 

After a system crash or power failure, rather than reconstruct the previous state, the usual goal was to restart as fast as possible, so some or all of the previous data was ignored.  Restoring (name) tags to tracks was very much a nice to have, but couldn't be done until you had several detections to combine into a track, which took many seconds.  (Both airborne and ground radars often stop emitting for short periods for various reasons including incoming missiles.  In those restarts you may or may not be able to match tracks with the old data.  Big Waah! Extra work for operators is a small price to pay for survival.)   

Anyway it was much, much easier to "roll your own" Ada database than use a commercial database.  Why?  Commercial databases are not real-time systems.  In a radar system you may need transactions to complete in N milliseconds for a relatively small N, while commercial databases consider 2 seconds average response times good enough.  With this particular Ada "trick" each track record could have its own lock, and threads could cache the address of the record and lock it only when necessary.  Transaction times were on average microseconds, with 2 or 3 milliseconds being worst case.

Re: Two-stage suspend operations

[Simon Wright]

rieachus@comcast.net writes:

> On Monday, May 9, 2016 at 4:56:15 AM UTC-4, Simon Wright wrote:
>> I see what you mean. It's just that the wording in the ARM made it sound
>> as though "two-stage suspend operations" was a phrase widely known in
>> the community, which clearly isn't the case.
>
> If you look at this article from Wikipedia:
> https://en.wikipedia.org/wiki/Two-phase_locking and go down to "strong
> strict two-phase locking" you will see that it is not you, me or the
> Ada Rationale.  There are a lot of inconsistent names floating around
> in this area, and the Rationale apparently chose one that lost
> out. (Strong strict two-phase locking may not interest you, I just
> picked the article as one showing considerable name confusion in
> 2011.)

Yes. I think part of my confusion is that the example in the Rationale
doesn't actually involve locking at all.

> I'm curious as to why you are interested in this area.  Ada is a great
> language for implementing in memory databases.  At MITRE I worked on
> both ground based and in-flight radar systems.  The emphasis was on
> consistency and non-blocking.

I'm looking at a system[1] where I'm assured that we need to run a
drone's motor controller at 20 kHz, and SOs seemed a possibility. Of
course, if you need to avoid concurrency problems between a timer-driven
ISR and tasking code, using SOs isn't going to work! so we are looking
at swing-buffering or possibly GNAT's Lock_Free pragma/aspect[2].

[1] http://adapilot.likeabird.eu/index.html
[2] https://gcc.gnu.org/onlinedocs/gnat_rm/Pragma-Lock_005fFree.html

Re: Two-stage suspend operations

[rieachus]

> I'm looking at a system[1] where I'm assured that we need to run a 
> drone's motor controller at 20 kHz, and SOs seemed a possibility. Of 
> course, if you need to avoid concurrency problems between a timer-driven 
> ISR and tasking code, using SOs isn't going to work! so we are looking 
> at swing-buffering or possibly GNAT's Lock_Free pragma/aspect[2].

It sounds like you need rate-monotonic scheduling: https://en.wikipedia.org/wiki/Rate-monotonic_scheduling  Usually you would run one clock at the highest priority and dispatch lower priority tasks every N ticks for some N.  The Liu Sha and John Goodenough paper tells how to implement RMS in Ada.  Notice though that there is a lot of math for you to do to assign priorities and prove that your system does not exceed a load limit.

Note BTW, that the GNAT pragma specifically allows the protected objects that only run in the context of another task/thread, have a high enough priority not to be interrupted, and do not reference any lower priority protected objects.

This is a sufficient but not necessary condition to insure that these POs are not involved in deadlocks.  To need POs you will have multiple (Ada) tasks, and you need a different way to prove they are deadlock free.  Also are you planning to allow running on more than one physical processor?  From experience you need to test on one, two, and three or more logical CPUs to verify deadlock and livelock free operation.  SPARK can do most of this for you. but sometimes the run-time or OS contain surprises.  Fortunately, when they do, they tend to be in your face rather than a once a year kind of thing.  (I found my share of bugs in Solaris. Only one of them was explicitly real-time related, but they all showed up within a few seconds.)

Re: Two-stage suspend operations

[Simon Wright]

rieachus@comcast.net writes:

Thanks for the notes.

>> I'm looking at a system[1] where I'm assured that we need to run a 
>> drone's motor controller at 20 kHz, and SOs seemed a possibility. Of 
>> course, if you need to avoid concurrency problems between a timer-driven 
>> ISR and tasking code, using SOs isn't going to work! so we are looking 
>> at swing-buffering or possibly GNAT's Lock_Free pragma/aspect[2].
>
> It sounds like you need rate-monotonic scheduling:
> https://en.wikipedia.org/wiki/Rate-monotonic_scheduling Usually you
> would run one clock at the highest priority and dispatch lower
> priority tasks every N ticks for some N.  The Liu Sha and John
> Goodenough paper tells how to implement RMS in Ada.  Notice though
> that there is a lot of math for you to do to assign priorities and
> prove that your system does not exceed a load limit.

It turns out that the 20 kHz is in a separate processor from the main
application.

Nothing like an enthuse-potential-volunteers description of a project
for generating confusion.

> Note BTW, that the GNAT pragma specifically allows the protected
> objects that only run in the context of another task/thread, have a
> high enough priority not to be interrupted, and do not reference any
> lower priority protected objects.

Can you tell me where this is documented?

Also, there seems very little difference between using Lock_Free and
Atomic: you can't have entries, and, when 'Contents' is an array of
integers,

lock_free.adb:3:07: illegal body when Lock_Free given
lock_free.adb:3:58: type of "Contents" must support atomic operations

> This is a sufficient but not necessary condition to insure that these
> POs are not involved in deadlocks.  To need POs you will have multiple
> (Ada) tasks, and you need a different way to prove they are deadlock
> free.  Also are you planning to allow running on more than one
> physical processor?  From experience you need to test on one, two, and
> three or more logical CPUs to verify deadlock and livelock free
> operation.

Only mono-processor at the moment.

I didn't mention that we are using Ravenscar, I thought that precluded
deadlock?

Re: Two-stage suspend operations

[rieachus]

On Saturday, May 7, 2016 at 12:13:19 PM UTC-4, Simon Wright wrote:
>
>It turns out that the 20 kHz is in a separate processor from the main 
>application. 

>Nothing like an enthuse-potential-volunteers description of a project 
>for generating confusion.

 Good, fifty microseconds is not a lot of time with a full tasking system.

>> Note BTW, that the GNAT pragma specifically allows the protected 
>> objects that only run in the context of another task/thread, have a 
>> high enough priority not to be interrupted, and do not reference any 
>> lower priority protected objects. 

> Can you tell me where this is documented?

It really isn't. You have to know how you expect a particular PO to map to say the RMW instructions provided by your particular hardware.  If it does?  Fine.  If not you have work to do to figure out what is confusing the compiler, or where you are confused.

When someone goes to port the software to new hardware?  It may work "right out of the box", or they may need to find what the equivalent primitive is for the new hardware and how to get the compiler to see it their way. )-: 

> Also, there seems very little difference between using Lock_Free and 
> Atomic: you can't have entries, and, when 'Contents' is an array of 
> integers, 

> lock_free.adb:3:07: illegal body when Lock_Free given 
> lock_free.adb:3:58: type of "Contents" must support atomic operations

I know the issue of an array of integers not supporting atomic updates was discussed in the ARG, but I don't believe it was ever "fixed."  To map the issue from theory to actual hardware, there is no guarantee that integers (of whatever size) can be updated atomically without affecting adjacent array entries.  Hmmm.  Try:
 type Foo is aliased limited new Integer -- is that the right order?
 Bar: array (Integer range 1..10) of Foo;

Better may be an array of protected integers?    

> Only mono-processor at the moment.

In computer science almost everything used three numbers, zero, one, and many.  In this area the numbers are zero, one, and many.  It is difficult to generate a deadlock that requires two processors, but livelock situations are often dual-processor related, and starvation can easily occur with many processors.

> I didn't mention that we are using Ravenscar, I thought that precluded 
> deadlock?

One of those good news bad news things.  Ravenscar can show that your main program is deadlock free--as long as you make promises about the non-Ada code in things like device drivers and the OS.  Choosing the right OS or implementing on bare metal takes care of 99% of that. But gotchas can turn up anywhere.  For example a processor with microcode that was back-patching missing instructions so that they only caused interrupts once.  Finding the right set of compiler directives fixed that, but of course, the hardware documentation had no clue...