Hi Tom,

On Wed, Oct 13, 2010 at 8:07 AM, Tom Rushworth <tom_rushworth at mac.com>wrote:

> 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 :).
>

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.


> >
> > ... 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
>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20101013/4e53a916/attachment.htm