Re: [sv-ec] Re: [sv-bc] Opinions on semaphores and suspend operations

John,

I'm not questioning the usability of the model you described, but I don't
think it should still be called FIFO - it is just a queue with priorities.
If the standard says that get() uses FIFO access model, then:
- either there should be no jump-aheads allowed
- or the standard should be changed to remove FIFO model references and call
it differently
'Queue with priorities' access model also requires clear definition of
priority and makes creation of efficient scheduler more difficult. Proper
definition of semaphores using this model would add yet another couple of
paragraphs to the standard.
One way or another - current status of the LRM description requires
clarification.

Jerry Kaczynski
Research Engineer
ALDEC, Inc.

On Wed, Jul 21, 2010 at 11:34 AM, John Michael Williams <john@svtii.com>wrote:

> Hi Jerry.
>
> You might like to think about the design of the 8087 coprocessor
> block of Intel i86 CPU's. This is a stack (LIFO) design which
> can be switched to a RAM register file (MMX, etc.). It isn't a FIFO,
> however.
>
> In an OS context, if one increases the priority of a process,
> the runtime "FIFO" has to be reorganized by "jumping ahead" a
> process with newly raised priority. This could be implemented
> by emptying the process "FIFO" and refilling it, of course. It
> would seem more efficient to allow (alternative) random access to the
> FIFO registers, than to require reading-out, in order, of the whole
> thing to other (RAM) registers, and then re-filling it.
>
> If a linked list can be reordered by relinking, why shouldn't a
> FIFO be allowed to do the same?
>
>
> On 07/21/2010 08:13 AM, Jarek Kaczynski wrote:
>
>> I agree with Gordon: allowing other processes to jump ahead of the one
>> already there creates so called 'weak semaphore' with serious danger of
>> hard
>> to resolve starvation. (If you use popular analogy to a restaurant, 'jump
>> ahead' model means that a customer with valid reservation for two tables
>> has
>> close to none chance of getting his tables if the restaurant has majority
>> of
>> one-table customers.)
>> Maintaining strict FIFO model of waiting processes creates 'strong
>> semaphore' that is less prone to starvation and generally recommended in
>> concurrent programming books.
>> Can anybody produce valid reason for using 'jump ahead' instead of 'strict
>> FIFO'? By 'valid' I mean an example of common system-level programming
>> practices, not the fact that vendor X implemented it that way.
>>
>> Jerry Kaczynski
>> Research Engineer
>> ALDEC, Inc.
>>
>> On Wed, Jul 21, 2010 at 7:47 AM, Gordon Vreugdenhil<gordonv@model.com
>> >wrote:
>>
>> But even that description is not what the LRM implies. It
>>> may be what some implementations actually do but it
>>> certainly isn't what all implementations do nor is it
>>> even implied to be correct per the LRM.
>>>
>>> Gord.
>>>
>>>
>>> Bresticker, Shalom wrote:
>>>
>>> Stuart Sutherland and Don Mills also discussed this in their first
>>>> Gotchas
>>>> paper, in the 2006 Boston SNUG, in Section 7.3.
>>>> The key paragraph is,
>>>>
>>>> "The get() method has a subtle, non-intuitive gotcha. If the number of
>>>> keys requested is not
>>>> available, then the request is put into a FIFO queue and will wait until
>>>> the number of keys
>>>> becomes available. If more than one process requests keys that are not
>>>> available, the requests are
>>>> queued in the order received. When keys become available, the requests
>>>> in
>>>> the queue are serviced
>>>> in the order in which the requests were received, First In, First Out.
>>>> The
>>>> gotcha is that, when
>>>> get() is called (a new request), an attempt will be immediately made to
>>>> retrieve the requested
>>>> keys, without first putting the request into the FIFO queue. Thus, a new
>>>> request for keys can be
>>>> serviced, even if other requests are waiting in the semaphore request
>>>> queue. The following
>>>> example demonstrates this gotcha."
>>>>
>>>> Regards,
>>>> Shalom
>>>>
>>>> -----Original Message-----
>>>>
>>>>> From: owner-sv-bc@eda.org [mailto:owner-sv-bc@eda.org] On Behalf Of
>>>>> Steven Sharp
>>>>> Sent: Tuesday, July 20, 2010 4:05 AM
>>>>> To: sv-ec@eda.org; sv-bc@eda.org; gordonv@model.com; sharp@cadence.com
>>>>> Subject: Re: [sv-bc] Opinions on semaphores and suspend operations
>>>>>
>>>>> OK, I found the other discussion that I was remembering. There were a
>>>>> couple of differences from what I remembered. One of them is that I
>>>>> did
>>>>> not initiate it. I thought that I did, because I had run into the
>>>>> issue
>>>>> before Jamie brought it up. The other is that it focused on whether a
>>>>> get(1) could bypass a waiting get(2) when there was 1 key available,
>>>>> and try_get() was only mentioned in passing. See
>>>>>
>>>>> http://www.eda-stds.org/sv-ec/hm/2651.html
>>>>>
>>>>> But most of the discussion seemed to be assuming that the single key
>>>>> was
>>>>> not taken by the get(2), and was still available for the get(1). The
>>>>> only question was whether the get(1) could bypass the queue and take
>>>>> it.
>>>>> If the get(2) was considered to be holding the single key already, then
>>>>> it would not be available. The issue of bypassing the queue would not
>>>>> come up (unless you wanted to allow races where the get(1) could grab
>>>>> the
>>>>> key only if a put happened at the same time as the get(1), and the
>>>>> get(1)
>>>>> happened to execute before the process at the front of the queue
>>>>> grabbed
>>>>> it).
>>>>>
>>>>> Overall, the viewpoint seemed to be that the keys were not taken until
>>>>> the entire request could be granted. That would eliminate option 1 in
>>>>> the suspend situation, since no partial requests would be held.
>>>>>
>>>>>
>>>>> Steven Sharp | Architect | Cadence
>>>>>
>>>>> P: 508.459.1436 M: 774.535.4149 www.cadence.com
>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> This message has been scanned for viruses and
>>>>> dangerous content by MailScanner, and is
>>>>> believed to be clean.
>>>>>
>>>>>
>>>> ---------------------------------------------------------------------
>>>> Intel Israel (74) Limited
>>>>
>>>> This e-mail and any attachments may contain confidential material for
>>>> the sole use of the intended recipient(s). Any review or distribution
>>>> by others is strictly prohibited. If you are not the intended
>>>> recipient, please contact the sender and delete all copies.
>>>>
>>>>
>>>>
>>>> --
>>> --------------------------------------------------------------------
>>> Gordon Vreugdenhil 503-685-0808
>>> Model Technology (Mentor Graphics) gordonv@model.com
>>>
>>>
>>>
>>> --
>>> This message has been scanned for viruses and
>>> dangerous content by MailScanner, and is
>>> believed to be clean.
>>>
>>>
>>>
>>
> --
> John Michael Williams
> Senior Adjunct Faculty
> Silicon Valley Technical Institute
>
> --
> This message has been scanned for viruses and
> dangerous content by MailScanner, and is
> believed to be clean.
>
>

-- 
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.