On 17 October 2010 12:01, Stéphane Ducasse <stephane.ducasse@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.