Previous | Next --- Slide 2 of 30
Back to Lecture Thumbnails
yrkumar

In the insert case, suppose thread A acquires the prev and cur pointers before it is descheduled and thread B takes over. Then, thread B can acquire the same prev/cur pointers and insert a node between the two. Now, when thread A is rescheduled, it simply uses the same prev and cur pointers that it had before, effectively overwriting the node inserted by thread B.

In the delete case, the same exact scenario could occur but would result in a deletion of a node that was no longer in the linked list.

jinsikl

Another thing that could happen is that the insert and delete are happening at the same time. Inside insert, it could be that nodes pointed to by prev or cur are deleted (memory is freed) by delete. This can lead to weird errors if the freed memory is reallocated, and is being used by some other thread.

moon

In general, without inserting locks, we run the risk of race conditions, especially when we try to change elements of data structures that are heavily dependent on other elements. Depending on the order in which the threads execute instructions, we can produce wildly different results, such as those described above.