Hi all,

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...)
I doubt that your atomic swap is as strong.

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.

On 2010-Oct-12, at 12:04, Igor Stasenko wrote:

> CAS? Perhaps. If you wish to add it too, no problem.
> 
> I want at minimum swap, because with it i can easily implement
> lock-free waiting:
> 
> [ | temp |
>  [ locked ] whileTrue.
>    temp := true.
>    locked :=: temp.
>    temp
> ] whileTrue.

I think this is simpler (using Eliot's notation):

  [locked ?:= true : false] whileFalse.

   ... locked here ...

   locked := false.

No temp needed, single block. well understood atomic op :).
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 :).

> 
> ... locked here ...
> 
> locked := false.
> 
> Proof:
> In the above, thread having chance to exit from waiting loop only if
> temp == false.
> There is no way how more than one waiting threads can leave this loop
> at same time,
> because 'locked' value is not copied over (assigned) but swapped
> (always with true).
> So, first who succeed to swap  false <-> true will obtain a lock,
> others will unable to do so, and swap true<->true, and thus will keep
> waiting in the loop.
> 
> 
> On 12 October 2010 20:46, Eliot Miranda <eliot.miranda at gmail.com> wrote:
>> 
>> 
>> On Tue, Oct 12, 2010 at 8:28 AM, Tom Rushworth <tom_rushworth at mac.com>
>> wrote:
>>> 
>>> If you're going for atomic swap as a primitive, why not go for
>>> Compare-And-Swap?  That way all the various lock-free algorithms that use
>>> the CAS machine instruction will translate easily.
>> 
>> +1.
>> I want, e.g.
>>        (var ?== expr : match) evaluates to true and var == expr if var ==
>> prev before the statement, and false and var unchanged if var ~~ match
>> var ?= expr : match is more difficult to implement since = is not
>> necessarily primitive.
>> So one could write e.g.
>> LinkedList subclass: #Semaphore
>>     instanceVariableNames: 'signals locked'
>> Semaphore>>signal
>>     [locked ?== true : false] whileFalse.
>>     self isEmpty
>>         ifTrue: [signals := signals + 1]
>>         ifFalse: [self removeFirst resume].
>>     locked := false
>>> 
>>> CAS(variable,oldValue,newValue) is an atomic operation which returns a
>>> boolean value (my ST syntax is rusty at the moment, too much Objective-C):
>>> 
>>> (variable == oldValue) ifTrue: [variable := newValue. ^true].
>>> " variable not the same as oldValue, no swap performed "
>>> ^false
>>> 
>>> On 2010-Oct-12, at 06:58, Igor Stasenko wrote:
>>> 
>>>> On 12 October 2010 16:51, Levente Uzonyi <leves at elte.hu> wrote:
>>>>> On Tue, 12 Oct 2010, Igor Stasenko wrote:
>>>>> 
>>>>>> Hello, i just thought, that it would be cool to have a special
>>>>>> bytecode,
>>>>>> which guarantees atomicity for swapping values between two variables.
>>>>>> 
>>>>>> To swap two values, you usually do:
>>>>>> 
>>>>>> | var1 var2 temp |
>>>>>> 
>>>>>> temp := var1.
>>>>>> var1 := var2.
>>>>>> var2 := temp.
>>>>>> 
>>>>>> But since its non-atomic, a process can be interrupted and such
>>>>>> operation
>>>>>> is not thread-safe.
>>>>>> 
>>>>>> In order to make it thread safe, you must add even more boilerplate:
>>>>>> 
>>>>>> | var1 var2 temp |
>>>>>> 
>>>>>> semaphore critical: [
>>>>>>  temp := var1.
>>>>>>  var1 := var2.
>>>>>>  var2 := temp.
>>>>>> ]
>>>>> 
>>>>> An alternative solution:
>>>>> 
>>>>> | a b |
>>>>> a := 1.
>>>>> b := 2.
>>>>> [
>>>>>        | tmp |
>>>>>        tmp := a.
>>>>>        a := b.
>>>>>        b := tmp ] valueUnpreemptively
>>>>> 
>>>> 
>>>> Yeah, another boilerplate under the hood, also highly dependent from
>>>> scheduling nuances :)
>>>> 
>>>> valueUnpreemptively
>>>>       "Evaluate the receiver (block), without the possibility of
>>>> preemption
>>>> by higher priority processes. Use this facility VERY sparingly!"
>>>>       "Think about using Block>>valueUninterruptably first, and think
>>>> about
>>>> using Semaphore>>critical: before that, and think about redesigning
>>>> your application even before that!
>>>>       After you've done all that thinking, go right ahead and use it..."
>>>>       | activeProcess oldPriority result |
>>>>       activeProcess := Processor activeProcess.
>>>>       oldPriority := activeProcess priority.
>>>>       activeProcess priority: Processor highestPriority.
>>>>       result := self ensure: [activeProcess priority: oldPriority].
>>>>       "Yield after restoring priority to give the preempted processes a
>>>> chance to run"
>>>>       Processor yield.
>>>>       ^result
>>>>> 
>>>>> Levente
>>>>> 
>>>> 
>>>> 
>>>> 
>>>> --
>>>> Best regards,
>>>> Igor Stasenko AKA sig.
>>>> 
>>> 
>>> --
>>> Tom Rushworth
>>> 
>>> 
>>> 
>>> 
>> 
>> 
>> 
>> 
>> 
> 
> 
> 
> -- 
> Best regards,
> Igor Stasenko AKA sig.
> 

--
Tom Rushworth