[M3devel] FreeSlots/lookup slot locking

[Tony Hosking]

What's more, volatile has very poorly defined semantics.
We do now expose CAS/CASP in experimental form, and those have the  
desirable behavior on most targets.

Antony Hosking | Associate Professor | Computer Science | Purdue  
University
305 N. University Street | West Lafayette | IN 47907 | USA
Office +1 765 494 6001 | Mobile +1 765 427 5484




On 12 Nov 2009, at 14:50, jay.krell at cornell.edu wrote:

> Yes volatile can be useful, but Modula-3 does not really expose it.
>
> - Jay (phone)
>
> On Nov 12, 2009, at 9:28 AM, hendrik at topoi.pooq.com wrote:
>
>> On Thu, Nov 12, 2009 at 04:17:12AM +0000, Jay K wrote:
>>>
>>> I do currently still use the critical section "throughout 'all' of  
>>> AssignSlot".
>>>
>>> The memory barrier doesn't replace it there. Just makes it carefully
>>> ordered so other readers see things reasonably well.
>>
>> Just curious:  C had "volatile" variables, meaning variables whose
>> writes and reads cannot be reordered or deleted by an optimiser.
>> They're intended for things like memory-mapped I/O.  Wouldn't they be
>> the kinds of things we need here?  How does the gcc intermediate code
>> represent them? By memory barriers? Or by some other means?
>>
>> -- hendrik
>>
>>>
>>>
>>>
>>> I DO suspect the locking in AssignSlot can be reduced but haven't  
>>> done so yet.
>>>
>>> Maybe it doesn't work out.
>>>
>>>
>>>
>>> - Jay
>>>
>>>
>>>
>>>
>>> From: hosking at cs.purdue.edu
>>> To: jay.krell at cornell.edu
>>> Date: Wed, 11 Nov 2009 09:23:59 -0500
>>> CC: m3devel at elegosoft.com
>>> Subject: Re: [M3devel] FreeSlots/lookup slot locking
>>>
>>>
>>>
>>>
>>>
>>> It's not the allocation I worry about.
>>> How do you avoid two threads getting the same slot?
>>>
>>>
>>> On 11 Nov 2009, at 01:11, Jay K wrote:
>>>
>>> Tony:
>>>
>>>> Also, I am unconvinced that the current implementation of  
>>>> AssignSlot can ever
>>>> be correct without the critical section. It requires atomic  
>>>> update of both
>>>> the slots array pointer (with the new slots) *and* the array  
>>>> elements. This
>>>> requires a proper CS instead of non-blocking synchronization.
>>>
>>>
>>> I don't see it.
>>> I could be wrong.
>>>
>>> The writes are done within a critical section, to avoid racing  
>>> with other writers.
>>>
>>> Writes interact with readers in that:
>>>
>>>           SUBARRAY (new_slots^, 0, n) := slots^;
>>> finish writing to the array elements
>>> MemoryBarrier
>>>           slots := new_slots;
>>>
>>>
>>> so readers don't see slots unless it has been fully initialized.
>>>
>>> AssignSlots should also be able to be lock free via  
>>> InterlockedCompareExchangePointer.
>>>
>>>
>>> - Jay
>>>
>>>
>>>
>>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20091112/0a129a48/attachment-0002.html>