Previous | Next --- Slide 2 of 31
Back to Lecture Thumbnails
kayvonf

Question: In class we talked about a scenario where two threads are inserting into the list at the same time, and a scenario where two threads were deleting from the list at the same time. For each case, describe a possible race condition and a corresponding undesirable outcome.

cube

Insertion: If both threads try to insert between the same two nodes at the same time, it's possible for one of the new nodes to be completely dropped.

Deletion: If threads try to delete a node and its successor, then a race condition could result in one of the nodes not being deleted, because a thread could read the sequence before a node is deleted and end up reconstructing a deleted path. This would be bad because the deleted node would likely already have been freed.

muyangya

@cube Actually I think race condition in deleting may cause something more severe.

If we consider a linked list 3-->5-->10-->11-->more nodes afterwards If thread 1 is deleting node 5, what it does is to let {5.next = null; 3.next = 10} If a the same time thread 2 is deleting 10, what it does is to let {5.next = 11; 10.next = null}

So it ends up with a linked list 3-->10-->null. Then all the nodes after 11 is thrown away. It causes more trouble in real time.