On Wed, Aug 08 2018, Frank Filz wrote: >> On Wed, Aug 08, 2018 at 03:54:45PM -0400, J. Bruce Fields wrote: >> > On Wed, Aug 08, 2018 at 11:51:07AM +1000, NeilBrown wrote: >> > > If you have a many-core machine, and have many threads all wanting >> > > to briefly lock a give file (udev is known to do this), you can get >> > > quite poor performance. >> > > >> > > When one thread releases a lock, it wakes up all other threads that >> > > are waiting (classic thundering-herd) - one will get the lock and >> > > the others go to sleep. >> > > When you have few cores, this is not very noticeable: by the time >> > > the 4th or 5th thread gets enough CPU time to try to claim the lock, >> > > the earlier threads have claimed it, done what was needed, and > released. >> > > With 50+ cores, the contention can easily be measured. >> > > >> > > This patchset creates a tree of pending lock request in which >> > > siblings don't conflict and each lock request does conflict with its > parent. >> > > When a lock is released, only requests which don't conflict with >> > > each other a woken. >> > >> > Are you sure you aren't depending on the (incorrect) assumption that >> > "X blocks Y" is a transitive relation? >> > >> > OK I should be able to answer that question myself, my patience for >> > code-reading is at a real low this afternoon.... >> >> In other words, is there the possibility of a tree of, say, exclusive > locks with >> (offset, length) like: >> >> (0, 2) waiting on (1, 2) waiting on (2, 2) waiting on (0, 4) >> >> and when waking (0, 4) you could wake up (2, 2) but not (0, 2), leaving a > process >> waiting without there being an actual conflict. > > That implies that the order the locks were received in was: > > (0,4) > (2,2) > (1,2) > (0,2) > > But couldn't (0,2) have been made only dependent on (0,4)? Correct. (0,2) would be a child if (0,4), but a sibling of (2,2). > Of course then > (1,2) is dependent on BOTH (2,2) and (0,2). Does this tree logic handle that > case? No, there is no support for double dependencies. It is still possible for a lock request to be woken up which, which still cannot be satisfied. When one block lock is unlocked, a pending request might then be queued against a different blocking lock. > > On the other hand, there might be a fairness reason to make (0,2) wait for > (1,2) even though it could have been granted concurrently with (2,2) since > this dependency tree also preserves some of the order of lock requests. The locking API doesn't promise fairness, and I don't think we should try too hard to achieve it. Certainly we shouldn't actively fight it (so no LIFO queuing) but if we try harder than that I suspect it would just be needless complexity. Thanks, NeilBrown > > Frank
Attachment:
signature.asc
Description: PGP signature
