On 14 October 2010 01:22, Tom Rushworth <tom_rushworth at mac.com> wrote:
>
> On 2010-Oct-13, at 14:28, Igor Stasenko wrote:
>
>> 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. :)
>
> So true.  There's a very strong "band wagon" effect :).
>
> (I may be being too English idomatic here.  English has an idiom "jump on the band wagon" for joining the currently popular fad or movement, so the "band wagon effect" is what happens when all the researchers see someone with a good idea, or even just a really good paper :).)
>>
>> 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"
> OK, at this point newItem is a single item circular list.
>> queueHead :=: newItem.
> Now queueHead is a single item circular list, and newItem is the old queue.  The single item circular list is the "guard" for flushing.
> ??? What happens if another thread (or threads) does a "Populate" right here, before the "Flush" grabs it, and before this Populate completes?  You end up with two circular lists, and two old queues in two different thread instances of temp - do they get re-assembled in the right way and does Flush handle it correctly?

Okay, lets see what happen.
Suppose we having P1, P2 - populating threads , and one F -
flushing/processing thread.

P1 swaps first:

head <= item1 (circular)
queue tail is known by P1 but not attached yet

now P2 interrupts P1

head <= item2 (circular)
queue tail, known by P2 points to item1


now F goes into play

head <= nil.
queue tail points to item2(circular)

- it spins until P2 finishes its work, and breaking the circular
reference by setting item2 next: item1
- now goes to item1
- again it spins until P1 finishes its work, and breaking the circular
reference by setting item1 next: old head


If F interrupts P1 before P2. Then P2 will see nil as queue tail, and
F will be able to process item2
on next flush iteration.

Looks like everything is fine.


-- 
Best regards,
Igor Stasenko AKA sig.