search

kaist-cp / cs500

Moved to https://cp-git.kaist.ac.kr/jeehoon.kang/cs500
25 stars 7 forks source link

concurrent linked list insertion #60

Closed fairy-of-9 closed 5 years ago

fairy-of-9 commented 5 years ago

Hi...

제목 없음

I don't know what the letters in the red square are. I'm sorry... I didn't concentrate in a lecture...

Thanks

jeehoonkang commented 5 years ago

Succeeded

fairy-of-9 commented 5 years ago

Thank you...!!

giangnguyen2412 commented 5 years ago

@jeehoonkang in this case, if ThreadA succeeded, the Y.next will be changed from Z to new of ThreadA, then threadB executes, but we still keep the condition Y.next.compare_and_set(Z, new). I am supposing that threadB will always fail because Y.next is now new-of-threadA, not Z anymore.

Is this correct?

jeehoonkang commented 5 years ago

@luulinh90s I forget the context of this.. I assume two threads concurrently try to insert a node, right? Then yes, if thread A succeeded in CAS, then thread B will not be able to succeed in CAS too.

giangnguyen2412 commented 5 years ago

Then in the case of insertion, we will not try again at all, right? Furthermore, in case of removal and insertion are performed at the same time, if Insertion-thread (thread trying to insert) detects Z is marked to remove, we also don't need to try again because at this time, Insertion will always fail, am I right?