Problem with lock based implementation: if a process was trying to insert and had acquired lock. OS swapped it out. Other processes which are operating on the linked list now cannot use the linked list and move ahead.

I think the 'lock(list->lock)' is hard to realize at first. It ensures the correctness of locking. Cool!

Could someone please explain why the list->lock is needed?

If it is not there, every thread will be able to initialize its prev and cur. But only one of them will be able to proceed beyond lock(prev->lock) instruction. So it doesn't really matter to us if lock(list->lock) is used or not.

In line 4 of delete code, there should be a check before assigning list->head->next to cur: if(list->head != NULL)

Notice the subtle difference of the last line in insert and delete.

In insert, because of break in while loop, cur may not be null, therefore its lock need to be released in the end.

In delete, cur is null after while loop, so additional check and release is not necessary.

@pk267. w.r.t the comment about line 4. To keep things simple on the slide we skipped handling of any edge cases (such as an empty list).

Why I'm using a list lock here is a little subtle.

Imagine there is no list lock. Also imagine thread 1 has a lock on the head node N as part of a DELETE operation.

• Step T1.1. Thread 1 takes a lock on N
• Step T1.2. Thread 1 removes N from the list (list->head is now NULL)
• Step T1.3. Thread 1 releases the lock,
• Step T1.4. Thread 1 deletes N.

Now imagine thread 2 attempts to perform another operation on the data structure.

• Step T2.1. Thread 2 sets prev = list->head.
• Step T2.2. Thread 2 deferences prev to get at the lock lock(prev->lock).

If T2.1 happens before T1.2, then T2 has a reference to prev which is a node locked by T1. that node can be deleted out from under T2. So the step T2.2 might be referencing freed memory.

Note the invariant in the above code is that if a thread is deleting a node N, the thread has locks on N, as well as the node before N (let's call the node before N, node M). This is important, since it means that no other thread has a lock on M. And since no other thread can get a lock on M, that means that it will not proceed to an iteration where cur->next = N (and thus another thread will never be referencing a node that might be deleted.

The use of the list lock provides this invariant even for the first node in the list. (The list lock can be thought of as a lock on a "dummy node" at the start of the list.)

@kayvonf Hi Professor, I have a question:

Doesn't the insert code have a race in the case where we try to insert into a list of size 1? In that case, suppose that we have a list of size 1 with a node that contains value 3, and threads 0 and 1 would like to add values 4 and 5, respectively, to the list. Consider the following execution trace: thread 0 acquires the list_lock and it reads prev as the head, and curr as NULL. Thread 1 attempt to acquire list_lock but it cannot. Thread 0 acquires prev's lock and unlocks list_lock, at which point Thread 1 locks list_lock and reads prev as the head of the list and cur as NULL. It then attempts to lock prev's lock, but cannot, and thread 0 adds 4 to the list, unlocks, and returns, at which point thread 1 locks prev's lock, which is the head's lock, but curr is still NULL, which should not be the case; curr should've been pointing to the node that contains 4. As a result of this, thread 1 will make it such that the head points to 5, effectively deleting 4 from the list, and ending up with a linked list that is incorrect. I believe this is possible, or am I missing something?

In the deletion code, why could we release prev->lock (line 3 below) before we delete cur (line 5)? I thought that it is possible that right after line 4, there could be another thread that happens to grab both prev->lock and cur->lock, which causes an unexpected result.

1 if (cur->value == value) {  
2     prev->next = cur->next;  
3     unlock(prev->lock);  
4     unlock(cur->lock);  
5     delete cur;  
6     return;  
7 }

@lya Due to the nature of hand-over hand locking, another thread cannot grab both the locks at the same time. As to the question of releasing the prev->lock, you can notice that the prev node has been patched to the next node in line 2. So that should not cause a problem.

I agree with @blah329. The corret version should be:

lock(list->lock);
prev = list->head;
lock(prev->lock);
cur = prev->next;
unlock(list->lock);
if(cur) lock(cur->lock);

Otherwise, the cur may not point to the latest version. So 'cur' should be read after acquiring the head's lock.