abortion/retry conditions for concurrent linked list

[qkrclrl701]

In the lecture, it is explained that if compare&set is failed or if node is already marked as deleted , then insertion/deletion will be retried.

I couldn't find those conditions in the slides, if anyone wrote down or took picture of them, could you please share it?

Also, do those retries work without changing arguments of insertion/deletion?

One more question, given X->Y->Z and trying to delete Y, we need to know predecessor of Y to delete Y, so X and Y should be given as an argument, right?

[jeehoonkang]

• Yes, to delete Y, it's necessary to know X as well.
• Insertion is regarded as successful if its CAS succeeds. Deletion is regarded as successful if its first CAS succeeds. If an operation is not successful, the user of the data structure should retry with other arguments.

[HaritzPuerto]

@jeehoonkang

Deletion is regarded as successful if its first CAS succeeds.

First CAS? I thought there is only 1 CAS. This is what I have on my notes and on the slides. You mean that delete is successful if marking is done correctly, right? But Marking is not done using a CAS operation, right? It is a fetch_or. I think fetch_add would also work too

Thank you!

[jeehoonkang]

@HaritzPuerto Thank you for pointing out my mistake. Yes, a node is regarded as deleted when the first RMW that marks the node succeeds.

[qkrclrl701]

@jeehoonkang

You mean checking if first RMW and CAS for deletion/insertion is enough??

When given X->Y->Z and trying to delete Y and inserting new node between Y and Z, if Y's next is marked, for insertion, next = Y.next is Z with marked 1.
If we don't check if it is marked, new node will set its next as marked Z, which makes new node already deleted as soon as it is inserted. As I remember, insertion should check if Y is marked as deleted or not, at the beginning of insertion.

For deletion, think about the situation that tries to remove Y and inserting new node next X. Even if deletion successfully marks Y's next as deleted, a node can be inserted between X and Y successfully and X's next can be changed before deletion completes. Then, second CAS of deletion, trying to set X.next = Y to X.next = Z fails, since X.next is changed to new node.

I think their success are not simply checked with only first RMW and CAS, but checking if a node is marked as deleted should be done, too.

[jeehoonkang]

@qkrclrl701 I couldn't understand your question... 혹시 한국어로 먼저 얘기할 수 있을까요?

[qkrclrl701]

@jeehoonkang

1. X->Y->Z, Y를 지우고, Y와 Z 사이에 새로운 node를 insert하는 것이 동시에 일어나는 상황
   deletion에서 Y의 next를 deleted로 mark한 이후에 insertion이 시작되는 상황을 가정하면, new node W의 next는 Y의 next로 설정될텐데, Y의 next는 mark가 된 상황이니 W.next = marked Z가 될 것입니다. 이 상황에서 insertion의 두번째 CAS는 성공하고, Y.next = W로 설정되어 insertion이 성공할텐데, W의 next는 처음의 Y.next, 즉 mark 된 Z로 설정될테니 X->Y->W-/>Z가 되어, 지우지도 않은 W를 지웠다고 mark하게 될 것 같습니다.

따라서, insertion의 처음에 Y.next가 mark 되었는지 확인하고, mark 되었다면 abort 해야할 것 같습니다.

2. X->Y->Z, Y를 지우고 X와 Y 사이에 새로운 node를 insert 하는 것이 동시에 일어나는 상황
   처음에 deletion에서 Y의 next를 mark 하는것이 성공한다고 하더라도, insertion은 아무 문제 없이 성공하여 X->W->Y-/>Z가 될것이고, deletion의 두번째 CAS는 X.next를 Y에서 Z로 바꾸려고 할 것입니다. 그런데, X.next가 이미 W로 바뀌었으니 CAS가 실패하고 deletion이 실패할 것입니다.

답변주신 내용에서는 deletion의 첫 RMW가 성공하면 deletion이 성공한 것이라고 하셨는데, 첫 RMW가 성공하더라도 deletion이 실패하는 상황인 것 같습니다.

단순히 RMW, CAS의 성공 여부만이 아니라, next가 mark 되었는지 또한 확인해야 할 것 같습니다.

[jeehoonkang]

• Insertion은 CAS를 한번만 실행합니다.
• 말씀하신대로 Insertion은 Y.next가 mark되었다면 abort합니다.
• Deletion에서 marking하는 RMW가 성공하면 deletion 자체가 성공한 것입니다. 리스트에 물리적으로 Y가 남아있더라도, 논리적으로는 없는 것으로 취급됩니다.

[qkrclrl701]

@jeehoonkang

명쾌한 답변 감사합니다. 그렇다면, iterate 할 때 delete된 node가 여러 개 있는 경우도 존재할 것 같은데요,
V->W-/>X-/>Y->Z

이러한 경우에는 V 이후에 바로 Y로 이동해야 할텐데, 수업시간에 말씀하신대로 W의 next가 mark된지 확인한 뒤에 mark되었으면 W.next로 이동하는 것이 아니라 while loop로 next가 mark 되지 않은 첫번째 node를 찾아 그 node로 이동해야 할 것 같은데 맞나요?

[CauchyComplete]

I think two deletion case is not handled in our algorithm. There was a question about it some days ago but it was buried.
See the concurrent deletion section on link below.
https://en.m.wikipedia.org/wiki/Non-blocking_linked_list

[jeehoonkang]

@qkrclrl701 Yes, during iteration, a thread should (1) skip the marked-as-deleted node, or (2) try to remove the marked-as-deleted node and proceed.

[jeehoonkang]

@CauchyComplete

I think two deletion case is not handled in our algorithm.

May I ask if you can elaborate on it?

[HaritzPuerto]

@CauchyComplete

I think two deletion case is not handled in our algorithm.

May I ask if you can elaborate on it?

Hello @jeehoonkang ,
here #63 (comment)

[CauchyComplete]

Yeah I was referring that issue. And think it is not that simple to handle