Previous | Next --- Slide 31 of 35
Back to Lecture Thumbnails
fleventyfive

From the first paper by Harris et al., the way in which the simultaneous insertion and deletion can be handled, is by breaking up the deletion into two atomic CASs instead of one. They propose adding a flag to the node to be deleted i.e. node B. When we know that the node is to be deleted, we just set the flag in node B, marking it for deletion. At this point, the node is said to be "logically deleted" from the list, although it may still be physically present in the list. Now when it is time for the insertion, the thread first checks whether the flag is set, and if it is, it first attempts to actually remove the node from the list, also termed as "physical deletion", and then it retries the insert operation from the beginning.