[Pharo-project] [squeak-dev] SharedQueue does scale (was: Re: SharedQueue doesn't scale)
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:
>> 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.
>> LIFOQueue -> SharedStack
>> I don't know a really good name for AtomicQueue, maybe SharedList,
>> SharedCollection or SharedListStub.
>> 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.
>> Best regards,
>> Igor Stasenko AKA sig.
>> Pharo-project mailing list
>> Pharo-project at lists.gforge.inria.fr
> Best regards,
> Igor Stasenko AKA sig.
More information about the Pharo-dev