[Pharo-project] [squeak-dev] SharedQueue doesn't scale
siguctua at gmail.com
Sun Oct 17 06:44:52 EDT 2010
On 17 October 2010 13:42, Igor Stasenko <siguctua at gmail.com> wrote:
> 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.
oops.. #nextIfNone: , will evaluate a block if there is no items in queue,
it is a #nextOrNil, which answers nil if there are no items in queue.
> 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.
>> On Oct 16, 2010, at 4:19 AM, Igor Stasenko wrote:
> Best regards,
> Igor Stasenko AKA sig.
Igor Stasenko AKA sig.
More information about the Pharo-dev