Hi Tom,<br><br><div class="gmail_quote">On Wed, Oct 13, 2010 at 8:07 AM, Tom Rushworth <span dir="ltr"><<a href="mailto:tom_rushworth@mac.com">tom_rushworth@mac.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi all,<br>
<br>
Take a look through the literature for the "strength" of the various types of atomic operations with respect to doing various synchronization tasks. CAS is "universal" in the sense that it can simulate all of the others. (The simulation is wretched, O(N**3), so it isn't practical, but...)<br>
I doubt that your atomic swap is as strong.<br>
<br>
Pretty well every current HW architecture actually has the CAS instruction (or some minor variation) implemented as a single instruction, so making it a primitive should be relatively easy. It seems a terrible waste to pick a weak synchronization primitive when a much better one could be had for very little more work.<br>
<div class="im"><br>
On 2010-Oct-12, at 12:04, Igor Stasenko wrote:<br>
<br>
> CAS? Perhaps. If you wish to add it too, no problem.<br>
><br>
> I want at minimum swap, because with it i can easily implement<br>
> lock-free waiting:<br>
><br>
> [ | temp |<br>
> [ locked ] whileTrue.<br>
> temp := true.<br>
> locked :=: temp.<br>
> temp<br>
> ] whileTrue.<br>
<br>
</div>I think this is simpler (using Eliot's notation):<br>
<br>
[locked ?:= true : false] whileFalse.<br>
<br>
... locked here ...<br>
<br>
locked := false.<br>
<br>
No temp needed, single block. well understood atomic op :).<br>
I've used this pattern (expressed in C code) in a very heavily used parallel data processing application, so I can even claim to have tested it extensively :).<br></blockquote><div><br></div><div>Right. And because Smalltak can't reify variables and CAS is an operation on a variable CAS can't be implemented as a primitive on variables. There's no way to express "pass a variable to a primitive", only "pass an expression (which may be the value of a variable)" to a primitive". One could do it with a primitive on an object, e.g. thisContext at: tempIndex compareWith: match andSetTo: expr, or anObject instVarAt: varIndex compareWith: match andSetTo: expr but that's soooo ugly. Hence I think it is better done using a special assignment operator.</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div><div></div><div class="h5"><br>
><br>
> ... locked here ...<br>
><br>
> locked := false.<br>
><br>
> Proof:<br>
> In the above, thread having chance to exit from waiting loop only if<br>
> temp == false.<br>
> There is no way how more than one waiting threads can leave this loop<br>
> at same time,<br>
> because 'locked' value is not copied over (assigned) but swapped<br>
> (always with true).<br>
> So, first who succeed to swap false <-> true will obtain a lock,<br>
> others will unable to do so, and swap true<->true, and thus will keep<br>
> waiting in the loop.<br>
><br>
><br>
> On 12 October 2010 20:46, Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>> wrote:<br>
>><br>
>><br>
>> On Tue, Oct 12, 2010 at 8:28 AM, Tom Rushworth <<a href="mailto:tom_rushworth@mac.com">tom_rushworth@mac.com</a>><br>
>> wrote:<br>
>>><br>
>>> If you're going for atomic swap as a primitive, why not go for<br>
>>> Compare-And-Swap? That way all the various lock-free algorithms that use<br>
>>> the CAS machine instruction will translate easily.<br>
>><br>
>> +1.<br>
>> I want, e.g.<br>
>> (var ?== expr : match) evaluates to true and var == expr if var ==<br>
>> prev before the statement, and false and var unchanged if var ~~ match<br>
>> var ?= expr : match is more difficult to implement since = is not<br>
>> necessarily primitive.<br>
>> So one could write e.g.<br>
>> LinkedList subclass: #Semaphore<br>
>> instanceVariableNames: 'signals locked'<br>
>> Semaphore>>signal<br>
>> [locked ?== true : false] whileFalse.<br>
>> self isEmpty<br>
>> ifTrue: [signals := signals + 1]<br>
>> ifFalse: [self removeFirst resume].<br>
>> locked := false<br>
>>><br>
>>> CAS(variable,oldValue,newValue) is an atomic operation which returns a<br>
>>> boolean value (my ST syntax is rusty at the moment, too much Objective-C):<br>
>>><br>
>>> (variable == oldValue) ifTrue: [variable := newValue. ^true].<br>
>>> " variable not the same as oldValue, no swap performed "<br>
>>> ^false<br>
>>><br>
>>> On 2010-Oct-12, at 06:58, Igor Stasenko wrote:<br>
>>><br>
>>>> On 12 October 2010 16:51, Levente Uzonyi <<a href="mailto:leves@elte.hu">leves@elte.hu</a>> wrote:<br>
>>>>> On Tue, 12 Oct 2010, Igor Stasenko wrote:<br>
>>>>><br>
>>>>>> Hello, i just thought, that it would be cool to have a special<br>
>>>>>> bytecode,<br>
>>>>>> which guarantees atomicity for swapping values between two variables.<br>
>>>>>><br>
>>>>>> To swap two values, you usually do:<br>
>>>>>><br>
>>>>>> | var1 var2 temp |<br>
>>>>>><br>
>>>>>> temp := var1.<br>
>>>>>> var1 := var2.<br>
>>>>>> var2 := temp.<br>
>>>>>><br>
>>>>>> But since its non-atomic, a process can be interrupted and such<br>
>>>>>> operation<br>
>>>>>> is not thread-safe.<br>
>>>>>><br>
>>>>>> In order to make it thread safe, you must add even more boilerplate:<br>
>>>>>><br>
>>>>>> | var1 var2 temp |<br>
>>>>>><br>
>>>>>> semaphore critical: [<br>
>>>>>> temp := var1.<br>
>>>>>> var1 := var2.<br>
>>>>>> var2 := temp.<br>
>>>>>> ]<br>
>>>>><br>
>>>>> An alternative solution:<br>
>>>>><br>
>>>>> | a b |<br>
>>>>> a := 1.<br>
>>>>> b := 2.<br>
>>>>> [<br>
>>>>> | tmp |<br>
>>>>> tmp := a.<br>
>>>>> a := b.<br>
>>>>> b := tmp ] valueUnpreemptively<br>
>>>>><br>
>>>><br>
>>>> Yeah, another boilerplate under the hood, also highly dependent from<br>
>>>> scheduling nuances :)<br>
>>>><br>
>>>> valueUnpreemptively<br>
>>>> "Evaluate the receiver (block), without the possibility of<br>
>>>> preemption<br>
>>>> by higher priority processes. Use this facility VERY sparingly!"<br>
>>>> "Think about using Block>>valueUninterruptably first, and think<br>
>>>> about<br>
>>>> using Semaphore>>critical: before that, and think about redesigning<br>
>>>> your application even before that!<br>
>>>> After you've done all that thinking, go right ahead and use it..."<br>
>>>> | activeProcess oldPriority result |<br>
>>>> activeProcess := Processor activeProcess.<br>
>>>> oldPriority := activeProcess priority.<br>
>>>> activeProcess priority: Processor highestPriority.<br>
>>>> result := self ensure: [activeProcess priority: oldPriority].<br>
>>>> "Yield after restoring priority to give the preempted processes a<br>
>>>> chance to run"<br>
>>>> Processor yield.<br>
>>>> ^result<br>
>>>>><br>
>>>>> Levente<br>
>>>>><br>
>>>><br>
>>>><br>
>>>><br>
>>>> --<br>
>>>> Best regards,<br>
>>>> Igor Stasenko AKA sig.<br>
>>>><br>
>>><br>
>>> --<br>
>>> Tom Rushworth<br>
>>><br>
>>><br>
>>><br>
>>><br>
>><br>
>><br>
>><br>
>><br>
>><br>
><br>
><br>
><br>
> --<br>
> Best regards,<br>
> Igor Stasenko AKA sig.<br>
><br>
<br>
</div></div>--<br>
<font color="#888888">Tom Rushworth<br>
<br>
<br>
<br>
<br>
</font></blockquote></div><br>