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

 Although there may have been an intent to give more flexibility
to the modeler, the inconsistent behavior Gord is pointing out
can make it harder to predictably use semaphores. That is 
sometimes there is a FIFO ordering and sometimes smaller requests
are fulfilled prior to larger requests. The shift between the
two is not directly controllable by the User (it depends on whether 
the pool is empty).

I also agree that the LRM is currently ambiguous.

I would prefer that the behavior is either always FIFO, or
always greedy (possibly user selectable?).

- Ray

> -----Original Message-----
> From: owner-sv-ec@eda.org [mailto:owner-sv-ec@eda.org] On 
> Behalf Of Gordon Vreugdenhil
> Sent: Thursday, September 15, 2005 4:38 PM
> To: Neil.Korpusik@Sun.com
> Cc: sv-ec@eda.org
> Subject: Re: [sv-ec] [sv-bc] Semaphore question
> 
> 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
> >>>
> >>>
> >>
> >>
> > 
> 
> --
> --------------------------------------------------------------------
> Gordon Vreugdenhil                                503-685-0808
> Model Technology (Mentor Graphics)                gordonv@model.com
>