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

 

I believe the LRM is clear about this. The LRM does not mention anything


about "all threads going through the semaphore queue" because it was

not intended. The two statements made by the LRM are:

    (1) If the specified number of keys are available, the method
returns and 

         execution continues.

    (2) The semaphore waiting queue is First-In First-Out (FIFO).

 

Note that (1) above makes on mention on whether there are any other
processes

in the queue at that time. A process is only entered in the queue if its
request can

not be satisfied, and once in the queue, those requests are handled in
FIFO order.

 

The intended behavior is exactly as Jamie surmised:

 

    semaphore c = new(1);

    initial c.get(2);    // process 1 blocks

    initial #1 c.get(1); // process 2 executes without blocking

    initial #2 c.put(2); // causes process 2 to execute

 

What Cliff and Steve are proposing is another plausible implementation,
but,

nonetheless, different from the one defined by the LRM. The semantics of
the

semaphore as currently defined by the LRM do not guarantee fairness,
thus,

they allows a process to acquire keys ahead of other processes waiting
on the

same semaphore. Generally, a semaphore used to control access to a
shared 

resource requires fairness in order to ensure that no process is
prevented from 

accessing the resource (and BTW that is the case if all processes
request the

same number of keys). However, for certain types of synchronization
control,

the throughput advantages offered by non-fair process ordering are often
much 

more important than the fairness considerations. Some systems may
provide a

"fairness" parameters to allow users to explicitly define this behavior.
For example,

the constructor of a Java semaphore accepts an optional "fair" argument
to 

specify this behavior.

 

            Arturo

 

-----Original Message-----
From: owner-sv-ec@eda.org [mailto:owner-sv-ec@eda.org] On Behalf Of
Steven Sharp
Sent: Thursday, September 15, 2005 12:45 PM
To: sv-ec@eda.org; Dave_Rich@mentor.com
Subject: Re: [sv-ec] [sv-bc] Semaphore question

 

I assume that the intent was that all processes conceptually go through

the semaphore waiting queue, even if they don't end up blocking there.

So all processes requesting keys would be constrained by the FIFO order.

 

The statement that the method returns if the specified number of keys is

available would then be misleading.  Either it needs the additional
condition

"and there are no earlier processes in the semaphore waiting queue", or

perhaps the keys are not considered "available" to the new process,
because

the earlier requesting processes have priority claim on them.

 

I agree that it is unclear, and could be interpreted the way that Jamie

suggested, and that this is undesirable.

 

Steven Sharp

sharp@cadence.com