Re: [sv-ec] [sv-bc] Semaphore question

From: Neil Korpusik <Neil.Korpusik_at_.....>
Date: Thu Sep 15 2005 - 17:03:14 PDT
The concept of priority would be something that the user would be adding on
top of the basic functionality described in the LRM. If it was indeed the
test bench writer's intent to create the illusion of true priority he would
need to think it through very carefully to ensure that the type of behavior
that he expected is really what he has coded. The semantic of the semaphore
is quite simple but the semaphore itself can be used in somewhat complicated
ways.

The pitfalls already pointed out by others on this thread need to be taken
into account by the person that is architecting the testbench. The semaphore
itself is just part of the total solution. It is up to the testbench writer
to wrap enough code around it such that the desired outcome is acheived.

I would imagine that most testbenches would use a semaphore that only hold a
single key. This is the simplest usage model and the easiest one to think
about. Getting more tricky by varying the number of keys used by different
threads could require quite a bit more code to be written to ensure that
everything works properly. Using the interpretation that Arturo has outlined
allows for the testbench writer to be more creative in how he uses the
basic semaphore construct.

One could imagine a situation where a semaphore contains 3 keys. Most
threads request 2 keys, but there is one thread that only requests a
single key. We also could specify that the thread that requests 1 key is not
allowed to make an additional request until its existing request (if any)
has completed. This setup then allows that one thread that only requires a
single key to get ahead of any other pending requests that require 2 keys.
One can argue as to whether this case makes sense or not, but it is setups
such as this that are allowed to be created when the algorithm that Arturo
described is adopted.


Gordon Vreugdenhil wrote On 09/15/05 16:38,:
> Thanks for giving the rationale Neil.  This is a somewhat odd
> use of a counted semaphore.  It does not of course really
> make a prioritized semaphore (is that really the intent?).
> If I have run out of keys, a "get(1)" will be queued and will
> remain queued behind a queued "get(50)".  If a single key is
> released, a new request for "get(1)" will succeed and the
> queued "get(1)" could starve.
> 
> Essentially any request, no matter what the priority, could
> starve behind one "low priority" (large number of keys) request.
> 
> Or is this really supposed to be prioritized?   Are we really
> supposed to pick all low number requests first?  That is certainly
> not implied at all in the spec.
> 
> Gord.
> 
> 
> Neil Korpusik wrote:
> 
> 
>>I agree with Steven that the LRM could be made more explicit in this regard.
>>
>>What Arturo is suggesting is that there are different user requirements that
>>can be met when applying the algorithm he has described. In some situations
>>it is desirable to enforce fairness and in other situations some threads
>>should have priority. If each thread requests the same number of keys then
>>fairness is enforced. A priority scheme can be created by having different
>>threads request different numbers of keys.
>>
>>Using the approach described by Arturo allows for more flexibility. With this
>>approach the user is allowed to decide how to use the semaphore to achieve the
>>objective he has in mind. I can understand how Cliff came to the conclusion
>>that he did given the existing text in the LRM but I believe that what Arturo
>>has described is preferable and what was originally intended.
>>
>>
>>Gordon Vreugdenhil wrote On 09/15/05 15:31,:
>>
>>
>>>I'm with Steven.
>>>
>>>This issue is why counting semaphores traditionally only
>>>allow a single request even though you can do a multiple
>>>release.  Allowing a multi-request can cause process
>>>starvation if you have high-frequency single requests
>>>that never allow the count to reach the number of the
>>>multi-request.  Allowing only single requests means
>>>that a request for N iterates and could block multiple
>>>times but will eventually succeed if progress is being
>>>made in the system.
>>>
>>>I don't like the semantics that Arturo is suggesting.  Do
>>>we really want to increase the chances of starvation
>>>in sytems?
>>>
>>>Gord.
>>>
>>>
>>>Steven Sharp wrote:
>>>
>>>
>>>
>>>
>>>>Arturo,
>>>>
>>>>Then what is the point of specifying the FIFO order for the semaphore
>>>>wait queue, if you are going to leave this hole?  With this hole, it
>>>>doesn't provide fairness, potentially leaving processes starved forever.
>>>>It doesn't provide determinism either, since arrival time is not
>>>>necessarily deterministic.
>>>>
>>>>Regardless of the intent, I don't agree that the text is unambiguous.
>>>>I think that my suggested interpretation is plausible from the existing
>>>>text, and is supported by the apparent desire for fairness indicated by
>>>>the FIFO ordering.  If the text had said that "the process is added to
>>>>the semaphore waiting queue and blocks until the keys become available"
>>>>then it would have been clear.  That would have indicated that the
>>>>semaphore waiting queue consists only of processes that blocked.
>>>>
>>>>Steven Sharp
>>>>sharp@cadence.com
>>>>
>>>>
>>>
>>>
> 

-- 
---------------------------------------------------------------------
Neil Korpusik                                     Tel: 408-720-4852
Staff Engineer                                    Fax: 408-720-4850
Frontend Technologies - ASICs & Processors (FTAP)
Sun Microsystems
email: neil.korpusik@sun.com
---------------------------------------------------------------------
Received on Thu Sep 15 17:03:31 2005

This archive was generated by hypermail 2.1.8 : Thu Sep 15 2005 - 17:03:49 PDT