lkml.org 
[lkml]   [2018]   [Aug]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    Date
    SubjectRE: [PATCH 0/4] locks: avoid thundering-herd wake-ups
    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
    [unhandled content-type:application/pgp-signature]
    \
     
     \ /
      Last update: 2018-08-09 00:34    [W:2.518 / U:0.032 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site