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.
This comment was marked helpful 0 times.
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.
This comment was marked helpful 0 times.
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.
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.
This comment was marked helpful 0 times.
Another thing that could happen is that the
insert
anddelete
are happening at the same time. Insideinsert
, it could be that nodes pointed to byprev
orcur
are deleted (memory is freed) bydelete
. This can lead to weird errors if the freed memory is reallocated, and is being used by some other thread.This comment was marked helpful 0 times.
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.
This comment was marked helpful 0 times.