Can we assume that the scheduler will prioritize putting threads that hold locks onto a processor? Otherwise, what happens when if in this example T0 is not scheduled and T1 has to wait on it to be scheduled again to do anything?
As another question, if we can assume the above, what happens when we extend this hand-over-hand locking principle to more threads (say 8). Do threads 1-7 speed all depend on how fast Thread 0 finishes its traversal through the linked list?
@MichaelJordan - You are right! Nobody can go past T0 and the other threads will have to wait. If the operations are spaced out and there aren't many threads processing the list then this could work. Otherwise, as Kayvon mentioned in class, we can implement fine-grained locking on each node in a segment and different threads can work on different segments. That will be a reasonable solution to this problem!
@MichaelJordan To your first point, that's why implementation of synchronization is often tied to the scheduler. For those who've written a task scheduler, it makes a lot of sense to schedule tasks based on whether the task is blocked on a mutex (or on I/O, or if it's sleep()-ing, etc.).