[squeak-dev] Re: [Pharo-project] How about atomic value-swap bytecode?

Igor Stasenko siguctua at gmail.com
Wed Oct 13 21:28:27 UTC 2010


On 14 October 2010 00:07, Tom Rushworth <tom_rushworth at mac.com> wrote:
>
> On 2010-Oct-13, at 12:58, Igor Stasenko wrote:
>
>>>
>>> Is it, or does it also rely on uninterruptbility?  Is this right?
>>>     v1 :=: v2
>>> is equivalent to
>>>     [ | scratch |
>>>      scratch := v1.
>>>      v1 ?= v2 : scratch] whileFalse.
>>>      v2 := scratch.
>>>
>>
>> Nope! Not in all cases.
>>
>> If v1 and v2 having equal significance in algorithm, not just v1,
>> then it won't work.
>> I mean, if the above will be interrupted after leaving the loop but
>> before you assign to v2 (v2 := scratch)
>> and your code expects that not only v1 swapped correctly, but v2 as well,
>> then you're in trouble.
>>
>> Swap is symmetric, i.e. v1 :=: v2 should be semantically equal to v2 :=: v1.
>> But its not achievable unless its also atomic.
>>
>> So, i must confess (again), that CAS cannot serve as a complete
>> replacement for atomic swap.
>
> I hadn't thought about both v1 and v2 being "global" (in the sense that they are both visible to other threads).  For the sake of the discussion I'll use a little C syntax to the lvalue/rvalue distinction is clear.
>
> CAS looks like: boolean CAS(int *var, int match, int newVal) // only one lvalue
>
> ASWP looks like: void ASWP(int *var1, int *var2) // two lvalues !!
>
> If the second lvalue is thread-local, you can simulate ASWP with CAS.  If it isn't you need to step up to DCAS (Double Compare And Swap - two simultaneous, non-adjacent CAS ops as one atomic op), which is a much rarer bird. (I'm not aware of any actual HW that supports it.)  Another option might be STM (software transactional memory (I think)), but that's not really common either.
>
> So, given how rare DCAS is, I'd have to say it isn't something we should be doing in Squeak, which leads to the question of just how often you expect to have an algorithm using ASWP where both v1 and v2 are "global" ?  I've spent a couple of months over the last few years reading papers on lock free data structures and there are lots of papers using CAS, but none I remember for an atomic swap, so I still think CAS is a better thing to add to Squeak than ASWP.  If you can come up with good examples for algorithms that need both v1 and v2 global then you might have a good argument, but I know there are good examples for algorithms using CAS, so you sort of need to match them :).

I think you won't find any papers about ASWP, because all researchers
thinking in a way:
 - okay, i have a CAS, now how i implement X using it. :)

Lets get back to my LIFO queue, its seems i found how to make it right
using ASWP:

Populating:

| temp |
temp := newItem := QueueItem new.
newItem next: newItem. "note this"
queueHead :=: newItem.
temp next: newItem.


Flushing and processing the queue:

| oldHead |
oldHead := nil.
queueHead :=: oldHead.

[ oldHead notNil ] whileTrue: [
  oldHead next == oldHead ifFalse: [
    "process the queue item here"
  oldHead := oldHead next. ]
]

in this way, a processing thread will loop with no-operation,
until thread, who populating new item will finish its job, i.e. attach
a rest of queue (or nil).

>>
>
> --
> Tom Rushworth
>
>
>
>
>



-- 
Best regards,
Igor Stasenko AKA sig.



More information about the Squeak-dev mailing list