Having one lock while traversing (for a short period of time), seems to be alright.

In the case where you are traversing the list and have not found a goal node, you will be able to release the prev node because you definitely do not care about it. You are guaranteed not to care about the previous nodes and how they are modified because the earliest node you could care about is the single node you have a lock for.

goal node: d

operation: delete

->(a)->(b)->(c)->(d)->(e)->

->(a)->(b*)->(c)->(d)->(e)-> [we don't care about a because we haven't found d]

->(a)->(b)->(c)->(d)->(e)->

->(a)->(b)->(c*)->(d)->(e)-> [we don't care about b, guaranteed]

->(a)->(b)->(c)->(d)->(e)-> [d was found]

->(a)->(b)->(c*)->(e)-> [d deleted]

->(a)->(b)->(c)->(e)-> [release c]

goal node: d

operation: insert before d

->(a)->(b)->(c)->(d)->(e)->

->(a)->(b*)->(c)->(d)->(e)->

->(a)->(b)->(c)->(d)->(e)->

->(a)->(b)->(c*)->(d)->(e)-> [we don't care about b, guaranteed]

->(a)->(b)->(c)->(d)->(e)-> [d was found]

->(a)->(b)->(c)->(i)->(d)->(e)-> [i inserted before d]

->(a)->(b)->(c)->(i)->(d)->(e)-> [release c,d]

I think these demonstrate that as you hold at least one lock you are guaranteeing that no other threads pass your lock. Holding one lock at a time implies that you are still searching for the goal node and thus do not care about the previous node.

This comment was marked helpful 2 times.

It seems to me that, in the release-prev-then-lock-next order of lock/unlock, you should maintain three invariants:

1. You are not interested in any nodes before the "cur" node (ie, the first node in the list that you have locked). I believe this implies that whatever changes happen before cur, you don't care about.
2. No otter threads can "leapfrog" you in their traversal, because they need you to unlock cur before they can lock/access it.
3. The earlier of the two nodes you have locked will not be deleted, so the "following" thread will never have a pointer to a to-be-deleted node.

As a result, if you are the "leading" thread, you do not care about modifications to the list you've already seen. If you are the "following" thread, you cannot grab a node until it is done being modified. So it seems that having a single lock may not be a problem.

It looks like this code implements the 3 lock-2 lock-3 lock style of traversal, as illustrated in the following slides.

Since you're deleting cur, you may even be able to get away without the line
unlock(cur->lock);
in the delete while loop.

EDIT: Comment race condition, sorry @bwasti.

This comment was marked helpful 0 times.

One performance problem inherent in this implementation is that if one thread is updating something near the beginning of the list, other threads won't be able to get past it to update something completely different at the end.

Perhaps when a node is locked, an additional pointer can be put on the first locked node to allow other threads to "skip past" the locked region? This additional pointer would also carry information about the value of the first node past the locked region so threads know whether they should skip, or wait for the region to be unlocked because they also need to work with it.

This comment was marked helpful 0 times.

I believe the potential problem that could arise from having pointers that allow skipping past locked nodes is that when updating a node in the list, you would also have to also update all of the extra pointers that point to it, which could call for even more locks and overshadow any performance gains from the skip pointers.

This comment was marked helpful 0 times.

After class it was determined that everyone else was correct, and I was not. It is sufficient to release the lock for old_prev prior to acquiring the lock for cur.

The code presented in lecture was correct code, but it was conservative about what lock needed to be held. I've updated the code above to release the lock for old_prev then acquire the lock for cur as the above discussion begun by @bwasti suggests. Good job everyone.

Side note: Last year I presented the never-hold-more-than-two-locks at a time algorithm as discussed above, but this year when preparing for lecture I thought I determined a case where it could lead to a race, and so I changed it to more conservative variant. Dumb professors.

You may also want to see the discussion on slide 10, where we're continuing the optimize this code even further.

This comment was marked helpful 0 times.

Note that simply eliminating the prev->lock code from the above would produce multiple problems.

1 - 2 - 3 - 4 - 5

T1: delete 3 T2: delete 3

T1 acquires L3 (lock 3). T2, sitting at cur = 2, sets cur = cur->next, so cur = 3. T2 acquires L2.

T1 sets 2 -> 4, unlocks L3.

Here, we have two bad scenarios: 1. T1 deletes L3. T2 then attempts to read L3 which is now unallocated, segfault. 2. T2 gets the lock on L3, then T1 deletes L3. Now T2 attempts to read node 3, segfault.

This comment was marked helpful 0 times.

Is there a good way to ensure that you aren't missing a race condition? Or is the only way to be absolutely sure brute-force checking the states of all threads when they are attempting to modify the same data. It seems very easy to show that something does have a race condition, but not to be completely certain that it doesn't have race conditions when working with fine grain locks.

This comment was marked helpful 0 times.

Not really. Some tools do try to find race conditions, but none of them can work all of the time.

This comment was marked helpful 0 times.

Can somebody explain why we need a list lock here? I do not see why lock the head and the next of head needs to be in lock step.

This comment was marked helpful 1 times.

@yanzhan2 I think it's because we need to assign the prev pointer to the start of the list (list->head). If the node is to be inserted at the head of the list, then you need to make sure that only one thread had the previous head of the list.

Otherwise, you could have two threads trying to insert to the front of the list at the same time; they may then both store the original head of the list. When one thread completes its insertion, the other thread won't recognize the changed head.

Could you clarify where you intend to place the lock? My understanding is that when you lock a node, you can't go past the node, but you can still assign a pointer to that node.

This comment was marked helpful 0 times.

@yanzhan2, to give a simple example, consider the list A → B.

• P1 does prev = list->head = A
• P2 does delete(A -> B, A)
• P1 does cur = list->head->next

The third step segfaults, as A has been deleted.

This comment was marked helpful 0 times.

@wcrichto,A has been deleted? P2 delete A or B?

This comment was marked helpful 0 times.

@yanzhan2 I believe that is what Will is saying here. P2 deletes A from the list (and the list is just A -> B), so when P1 does cur = list->head->next, the head of the list (A) has been deleted, so there is no next, and a segfault occurs.

This comment was marked helpful 0 times.

@arjunh, but the existence of list->lock cannot prevent two threads from starting from the same old head.

@wcrichto, the comment said "assume the case of delete head handled here". So I guess deleting the head should not be handled here.

This comment was marked helpful 0 times.