On Thu, Aug 09 2018, J. Bruce Fields wrote: > On Fri, Aug 10, 2018 at 08:12:43AM +1000, NeilBrown wrote: >> On Thu, Aug 09 2018, J. Bruce Fields wrote: >> >> > I think there's also a problem with multiple tasks sharing the same >> > lock owner. >> > >> > So, all locks are exclusive locks for the same range. We have four >> > tasks. Tasks 1 and 4 share the same owner, the others' owners are >> > distinct. >> > >> > - Task 1 gets a lock. >> > - Task 2 gets a conflicting lock. >> > - Task 3 gets another conflicting lock. So now we the tree is >> > 3->2->1. >> > - Task 1's lock is released. >> > - Before task 2 is scheduled, task 4 acquires a new lock. >> > - Task 2 waits on task 4's lock, we now have >> > 3->2->4. >> > >> > Task 3 shouldn't be waiting--the lock it's requesting has the same owner >> > as the lock task 4 holds--but we fail to wake up task 3. >> >> So task 1 and task 4 are threads in the one process - OK. >> Tasks 2 and 3 are threads in two other processes. >> >> So 2 and 3 conflict with either 1 or 4 equally - why should task 3 be >> woken? >> >> I suspect you got the numbers bit mixed up, > > Whoops. > >> but in any case, the "conflict()" function that is passed around takes >> ownership into account when assessing if one lock conflicts with >> another. > > Right, I know, but, let me try again: > > All locks are exclusive locks for the same range. Only tasks 3 and 4 > share the the same owner. > > - Task 1 gets a lock. > - Task 2 requests a conflicting lock, so we have 2->1. > - Task 3 requests a conflicting lock, so we have 3->2->1. > - Task 1 unlocks. We wake up task 2, but it isn't scheduled yet. > - Task 4 gets a new lock. > - Task 2 runs, discovers the conflict, and waits. Now we have: > 3->2->4. > > There is no conflict between the lock 3 requested and the lock 4 holds, > but 3 is not woken up. > > This is another version of the first problem: there's information we > need (the owners of the waiting locks in the tree) that we can't > determine just from looking at the root of the tree. > > I'm not sure what to do about that. You're good at this game! So, because a locker with the same "owner" gets a free pass, you can *never* say that any lock which conflicts with A also conflicts with B, as a lock with the same owner as B will never conflict with B, even though it conflicts with A. I think there is still value in having the tree, but when a waiter is attached under a new blocker, we need to walk the whole tree beneath the waiter and detach/wake anything that is not blocked by the new blocker. Thanks, NeilBrown
Attachment:
signature.asc
Description: PGP signature
