Re: [sv-ec] Semaphore Question - 2nd Request

>From: Cliff Cummings <cliffc@sunburst-design.com>
>
>Semaphore Question:
>
>An interesting question that I do not believe has been answered yet, nor
>well documented (the FIFO description might be problematic here).

Actually, I think this part is fairly clear.  FIFO means FIFO.


>Question: What will happen if there are no keys, process-A requests two
>keys (is put on the requesting FIFO) and later process-B requests one key?
>
>Is process-B put on the requesting FIFO behind process-A??

Yes.


>If one key is returned, does process-B come off the not-so-FIFO and become
>active??

No.  That would not be FIFO, as you noted.


>If two keys are returned instead of one key, does process-A become active
>before process-B?

Yes.  And if one key is returned, and then later another key is returned,
process-A becomes active before process-B.

Once the processes go on the semaphore wait queue, I think it is clear
they are given available keys in FIFO order.  What is unclear is when a
process is considered to go on the semaphore wait queue.

Arturo's interpretation is that this happens only if a process blocks
because insufficient keys are available.  But this leads to inconsistent
behavior.  If process-B requests a key and there is one available, it
goes before process-A, which was there first.  This is not-so-FIFO, as
you put it.  However, if one becomes available just after process-B
requested it, then process-B has to wait until after process-A.  This
is FIFO.  This is inconsistent.

My suggested interpretation was that all requests for keys go into the
semaphore wait queue, but may pass through and come out again immediately
without blocking if there is nothing else in the queue and there are 
sufficient keys.  This will always be FIFO.  I believe this interpretation
is not contradicted by text in the LRM, though it may not have been the
intent.

The other way to make the behavior consistent would be to use your
not-so-FIFO approach above, and let process-B bypass process-A when there
are enough keys for it.  But this is contradicted by the LRM text that
requires FIFO.  It would also be less efficient to implement, because
when a key was released, you would have to do something more than just
checking the first request in the queue.

Steven Sharp
sharp@cadence.com