Previous | Next --- Slide 5 of 35
Back to Lecture Thumbnails
RX

At least 3 problems of this code

#1 Insert may be lost, suppose two threads try to update the successor of the same node, the last one will succeed, the first thread's insertion will be lost

#2 Delete on already deleted node. A thread can be deleting a node that was deleted by another thread.

#3 Insertion on deleted node.

captainFlint

Simultaneous inserts can cause loss of data (one node), the node that updates prev->next second wins, that is, its the one whose update survives. On the other hand, simultaneous deletes can break the linked list, that is we can potentially lose a large portion of the list. Another issue with simultaneous delete is that we can have segmentation fault (since we might call delete/free on the same node twice).

PID_1

In class there was some discussion of whether or not it was possible to "break" the link list in a race condition only involving inserts. I do not think it is, and here is why:

First note that we set next before we set prev. This means that while we loop to find the insert location, we will not reach a false dead end because of an unfinished insert. Then in the batch of new nodes we are inserting, some node must be the last to set prev->next. This node will definitely be in the list. Because there are no false dead ends, n has also already set it's n->next to some node in the list. This may represent a state of the list before one of the other inserts happening concurrently, but it means it cannot discard the entire tail.

eknight7

There is another case, when we insert when head is empty i.e. list == NULL. If thread_1 inserts 6 and thread_2 inserts 7, (where code would simply be "n->next = NULL; list->head = n"), so only one of the two nodes remain. This is a simpler example to show data loss.

@PID_1 Your summary is apt, but I think its possible to break the list if this was a doubly linked list. Suppose you have the list 1<=>2<=>5<=>10 and thread t1 inserts a 6 and t2 tries to insert a 7. Due to race condition we can end up with the list 1<=>2<=>5<=>6->10->7->5. Basically now we have 5 <=> 6 -> 10 and 5 <- 7 <=>10 so the doubly linked list invariant fails and a bridge to one half of the list is lost after 6 and before 7. Here is some code I wrote for a sorted doubly linked list

leis1

Here's another answer for insert and delete mix:

We can ignore the look up codes. Essentially,

list: ...-prev-cur-...-

"insert" wants to "n->next = cur; prev->next=n;"

"delete" wants to "prev->next=cur->next; delete cur;"

They will run in parallel (It's just like a normal multi-thread problems). Given a list 1-2-4-5. When insert 3 and delete 4 happens at the same time, we could have 1-2-5 or 1-2-3 as result.