Re: Why SynchronousQueue.TransferQueue#clean() not clean the last node

What I meant to point out, was the subtle difference between the two cases.
Your second picture makes it look like the first case.

The first way for this to go wrong. No atomic update of tail - cannot
guarantee it may not guarantee tail may not refer to a chain with some
nodes reachable from head. Reasoning locally (an important tool in
analyzing algorithms) - that is, considering the unlinking logic alone - we
can prove that updating tail cannot be done safely, if it is not atomic
with unlinking. A breaking case is unlinking B and C concurrently.

The second way for this to go wrong assumes we solve the atomicity of tail
update in some way. (For the sake of argument, assume tail always points to
one or two nodes before last; appending is still O(1)) Even in this case
removing the last node is not correct, because updating B.next (unlinking
C) and C.next (enqueue D) is concurrent. But this seems to require
reasoning about other methods (not local).

Alex

On Mon, 17 Aug 2020, 07:17 Alex Otenko, <[email protected]> wrote:

> Correct. In addition, notice that updating tail to point to B can't be
> done atomically with unlinking of C. Then it's possible for head and tail
> to point to chains with no common nodes.
>
> Alex
>
> On Mon, 17 Aug 2020, 03:14 Liu, <[email protected]> wrote:
>
>>
>> I try to understand what you guys are saying.
>>
>> Firstly,    A -> B -> C(tail) -> null, and if C should be cleaned,
>>  it should become A -> B(tail)  -> null. but there is No such atomic
>> operation.
>>
>> Secondly, some threads may see A -> B  -> null and C(tail), and may
>> append node
>> after C which is wrong.
>>
>>
>>
>>
>>
>>
>

_______________________________________________
Concurrency-interest mailing list
[email protected]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest