[Pharo-project] [squeak-dev] SharedQueue does scale (was: Re: SharedQueue doesn't scale)

Levente Uzonyi leves at elte.hu
Mon Oct 18 20:42:00 EDT 2010


On Tue, 19 Oct 2010, Igor Stasenko wrote:

> On 19 October 2010 02:06, Levente Uzonyi <leves at elte.hu> wrote:
>> On Mon, 18 Oct 2010, Igor Stasenko wrote:
>>
>> snip
>>
>>>
>>
>> Thanks, Levente for giving a feedback.
>> Please, feel free to shape my classes in more complete from (such as
>> proper naming),
>> to make them ready for inclusion in both Squeak's and Pharo cores.
>> I propose the following names:
>> AtomicQueue (base class) -> AtomicCollection
>> FIFOQueue -> AtomicQueue
>> LIFOQueue -> AtomicStack
>> If you, or anyone else having better suggestions, speak now :)
>>
>>
>>
>> I think these should be the names:
>>
>> FIFOQueue -> SharedQueue
>
> this name already used by Kernel.
> So, unless my class will fully replace it, i see no way how i could
> use this name in separate package.

Yes, it would be good to replace the implementation IMHO. The API seems to 
be complete to me (except for copying ;)).

>
> Also, i must stress, that behavior of FIFOQueue only attempts to
> closely resemble the SharedQueue behavior.
> However, there is a situations (related to how scheduling works and
> use of #yield), where using them could lead to deadlocks.
> In this regard, an AtomicSharedQueue (a subclass of FIFOQueue) is much
> better analogy to current SharedQueue.

If you mean the case: "if process A tries to read from an empty queue, 
later process B tries to do the same, then process A is guaranteed to 
read before process B", then that shouldn't be a problem. It would require 
an external synchronization step to make use of this feature with the 
current implementation. I doubt that anyone wrote such code ever.

>
> As i noted in another mail, i see that we might also provide a
> separate wait-free interface. So we can guarantee,
> that if you using only wait-free interface, a queue can never be the
> cause of deadlock.

That's great, and it can be a future addition even if we push the current 
implementation to the Trunk.


Levente

>
>> LIFOQueue -> SharedStack
>>
>> I don't know a really good name for AtomicQueue, maybe SharedList,
>> SharedCollection or SharedListStub.
>>
>>
>> Levente
>>
>>
>>
>> In any case, i'm am open to discuss further details and possible
>> caveats of using new classes
>> to anyone interested in using them.
>>
>> P.S. As a side note, i now can explain (to myself at first place), why
>> i intuitively choosed to used atomic swap
>> instead of CAS.
>> Because it fits better fits with smalltalk language semantics:
>>
>> A swap operation in smalltalk implemented as two assignments:
>> x := y. y := z.
>> An assignments is basic operation, which have nothing to do with
>> late-bound nature of language.
>> Unless we going to introduce a meta-object protocol(s), which could
>> turn a simple assignment
>> into some message sends under the hood, it will remain a basic,
>> early-bound operation.
>> And even if we do, it is highly unlikely, that even then we will throw
>> away the old,
>> simple assignment, which identifies an assignment source & target at
>> compile time.
>>
>> In contrast, a CAS operation , if written in smalltalk looks like:
>>
>> (a == b ) ifTrue: [ a := c ]
>>
>> so, it having two message sends (#== , #ifTrue:), and from strict,
>> pure language perspective,
>> this using a late-bound semantics (a message sends),
>> and as any message send, the message result and behavior cannot be
>> predicted at compile time
>> and therefore its wrong to assume that such statement could be an
>> atomic operation.
>>
>> Unless, of course, we introduce a new language syntax which will
>> denote a CAS operation explicitly.
>>
>>>
>>> Levente
>>>
>>>
>>> snip
>>>
>>
>>
>> --
>> Best regards,
>> Igor Stasenko AKA sig.
>>
>> _______________________________________________
>> Pharo-project mailing list
>> Pharo-project at lists.gforge.inria.fr
>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>>
>>
>
>
>
> -- 
> Best regards,
> Igor Stasenko AKA sig.
>
>




More information about the Pharo-dev mailing list