[squeak-dev] SharedQueue doesn't scale

Igor Stasenko siguctua at gmail.com
Sun Oct 17 10:42:50 UTC 2010


On 17 October 2010 12:01, Stéphane Ducasse <stephane.ducasse at inria.fr> wrote:
> Igor sorry we were busy running around :)
> So could you summarize
>        with pros and cons
>        with potential path for the next actions
>        May be we should schedule something for 1.3
>

The two implementations i made in Atomic-Collections package run
without using any kind of locking (i.e. semaphores).
However, we should make a difference between lock-free and wait-free algorithms.

Inserting items in queue (both FIFO and LIFO) using no wait-loops, and
can be considered a O(1) operation,
if we neglect the cost of allocating new queue item.

But to extract items, both FIFO and LIFO queues using a wait loops, if
queue is in the middle of extraction by
other process.
This means, that if there is only one process, which extracting items
from queue,
extraction will be always wait-free. But if you having more than one,
you should expect wait-loops to be used.
There is, however a way to give a quick answer without entering a
wait-loop at attempt
to extract a single item from queue. But it won't be deterministic answer:
 - #nextIfNone: will return nil if there either no items in queue or
queue is currently in the middle of extraction by
other process.

I think that there should be two distinct methods(protocol) for
accessing queue in wait-free way,
which not always guarantees deterministic answers, and methods, which
using wait loops.
Because currently, in order to match with SharedQueue protocol,
there is a mix of methods with wait-free and wait-loops to match the
SharedQueue behavior.

Then, applications, which using these queues, could have a guarantees
that any access to queue
are wait-free, if they can neglect that answers are non-deterministic,
or use methods with wait-loops to always have a deterministic answers.

> Stef
>
>
> On Oct 16, 2010, at 4:19 AM, Igor Stasenko wrote:
>
-- 
Best regards,
Igor Stasenko AKA sig.



More information about the Squeak-dev mailing list