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

I realize now that "tail" is ambiguous, and can also refer to what I
called trailing node.

            // Never unlink trailing node.

On Sun, Aug 16, 2020 at 4:13 PM Alex Otenko <[email protected]> wrote:
>
> Thanks. I realize that. I was merely trying to come up with a bullet-point-like explanation of what is wrong with unlinking the last element of the queue.
>
> So moving tail "up" to point to prev atomically with the unlinking of the last node is one - without atomicity of such update can't ensure the actual last element of the queue remains reachable from the tail.
>
> And even in "tailless" designs there is a problem: last node remains attachable even after unlinking - concurrent attempts to add elements to the queue can be modifying next after the node is unlinked.
>
> Alex
>
> On Sun, 16 Aug 2020, 20:55 Martin Buchholz, <[email protected]> wrote:
>>
>> On Sat, Aug 15, 2020 at 1:24 AM Alex Otenko <[email protected]> wrote:
>> >
>> > Great. But still head and tail point to nodes in the same chain, right?
>>
>> java.util.concurrent is where data structure intuition goes to die.
>>
>>     /**
>>      * A node from which the last node on list (that is, the unique
>>      * node with node.next == null) can be reached in O(1) time.
>>      * Invariants:
>>      * - the last node is always reachable from tail via succ()
>>      * - tail != null
>>      * Non-invariants:
>>      * - tail.item may or may not be null.
>>      * - it is permitted for tail to lag behind head, that is, for tail
>>      *   to not be reachable from head!
>>      * - tail.next may or may not be self-linked.
>>      */
>>     private transient volatile Node<E> tail;
>>
>>
>> >
>> > Alex
>> >
>> > On Sat, 15 Aug 2020, 08:02 Martin Buchholz, <[email protected]> wrote:
>> >>
>> >> I did more work on ConcurrentLinkedQueue, including recording the
>> >> invariants, notably:
>> >>
>> >>      * Invariants:
>> >>      * - all live nodes are reachable from head via succ()
>> >>      * - head != null
>> >>      * - (tmp = head).next != tmp || tmp != head
>> >>      * Non-invariants:
>> >>      * - head.item may or may not be null.
>> >>      * - it is permitted for tail to lag behind head, that is, for tail
>> >>      *   to not be reachable from head!
>> >>
>> >> On Fri, Aug 14, 2020 at 11:23 PM Alex Otenko via Concurrency-interest
>> >> <[email protected]> wrote:
>> >> >
>> >> > Yes. There is an unspoken invariant that head and tail make progress in one direction. That is pretty much the only way to make sure the head never passes the tail. Then deleting tail cannot be done without moving the tail backwards to pred. This breaks the unspoken invariant in the presence of concurrent modifications of head.
>> >> >
>> >> > Alex
>> >> >
>> >> > On Sat, 15 Aug 2020, 07:18 Liu, <[email protected]> wrote:
>> >> >>
>> >> >> Thanks. I just think about it, it is kind of difficult to keep the correctness of tail.
>> >> >
>> >> > _______________________________________________
>> >> > Concurrency-interest mailing list
>> >> > [email protected]
>> >> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
_______________________________________________
Concurrency-interest mailing list
[email protected]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest