Multithreading – thread safe deletion of linked list nodes using fine-grained methods

Why is it not thread safe to delete the following code snippet of a node in a linked list?

Edit: note that each node has its own lock

// ... lock acquisition here
// ... assumption found to be valid here
prev->next = p->next;
p->next = NULL;
p->deleted = 1;

Solution

It is thread safe, assuming that the scope of your lock (meaning what it locks, independent of the official term "scope" used in C) is large enough

If it only locks the current node P, you can't rely on other threads to enter and use prev (or head or tail) and weaken you

If it locks the entire structure, then yes, it is thread safe

We can't tell you the scope of the lock from the code given, but I'll mention another (irrelevant) thing

You should probably release P or add it to the free list for reuse By setting its next pointer to null and its deleted flag to 1, it cannot be found when it needs to be reused This will cause a memory leak It may be that the code for doing so is not shown, but I think I'll mention it just in case

Based on your edits, you declare that you are using a fine-grained method (one lock per node):

If you lock all three "nodes" you are using or changing and lock them in the same direction, it is still thread safe

I put "node" in quotation marks because it also applies to head and tail pointers For example, if you want to delete the first node in the ten node list, you need to lock the header variable and the first and second nodes in order To delete the last node in the single node list, you need to lock both the head and tail variables and the node

Locking all three "nodes" will prevent threads from adversely affecting each other

Locking them in the same direction (e.g. head to tail) will prevent deadlock

But you have to lock all three before trying to change anything

This will even prevent it from performing concurrent insert operations, as long as the insert locks the two "nodes" on both sides of the insertion point, which, of course, lock them in the same direction

I'm not sure how much I iterate on the list You may be able to use a system where you first lock the head variable and the first node, and then release the head

Then, when you finish the node, lock the next node before releasing the current node In this way, you should be able to traverse the list without being affected by insertion or deletion, which can only be done in areas you are not currently using

But most importantly, you can ensure thread safety even with fine - grained locking scopes