[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

Re: Newbie question on mutexes



Perez-Gonzalez, Inaky wrote:
> > Or even better for RT applications: you could do strict ownership
> > transferral when it is to a strictly higher priority RT scheduling
> > class, but keep scheduler heuristics in control when the highest
> > priority wakee is in the same scheduling class as the waker.
> 
> You mean priorities or scheduling classes? I can see doing that if
> the first wakee is RT (strict) or if it is _OTHER (non-strict), but if
> the first wakee is RT, lower prio, I still want to do strict to
> avoid the time window where you are open to priority inversion in 
> an SMP system (when a _OTHER or lower prio RT could sneak in).

I mean what you are thinking - priorities, with SCHED_OTHER all being
a single priority.

> OTOH, you can only do that from inside the kernel, as it is the only
> place where you can, atomically speaking, get the first wakee and
> what kind of guy he is.

Yes, in the kernel is exactly what I meant.

> As another OTOH, not being strict also breaks a little bit the guarantee
> of robustness that RTNPTL+fusyn offers, having a little window of time
> where you can be left in the water.

I don't see why that is OTOH.  I'm suggesting strict ownership
transferral when it's to a higher priority RT task, no (or stochastic)
ownership transferral when it's not.  Among non-RT tasks or RT tasks
of the same priority, you are indeed left in the water until another
task takes the mutex.  It may not even be a little window, it could be
many seconds if that's how long it takes another task to run on a busy
system.

Not doing ownership transferral is essential to avoid excessive scheduling.

(For those reading who need to see why that is important, consider a
producer thread with an operation like "queue_add" which pushs an
object onto a list, a consumer thread with "queue_remove" removing
them, and a mutex to protect the data structure.  If both threads are
looping doing this, then with strict ownership transferral of the
mutex you will alternate between the threads at every queue operation,
preventing the queue from filling and preventing batching the
calculations of each thread.  Performance sucks!)

> > One clean and general way to implement general ownership transferral
> > may be a combined wake+wait kernel primitive: you tell the kernel to
> > wait on a futex until the word has a certain matching value (and
> > futex_wake is called), then the kernel substitutes a different value
> > and wakes you.  You specify both values.
> 
> That's more or less the basis of fulocks :)

Oh, you mean we can just add the function to futex and slip it in
quietly that way? :)

> > mentioned above.  Also it could stochastically prevent starvation,
> > without forcing slow convoys, by occasionally deciding to transfer
> > ownership for non-RT tasks based on a random number.
> 
> But that breaks the determinism you want for RT applications. In RT
> you want to force a guy to starve. If it is starving and I don't know 
> why, then I have a bigger problem.

I mean (this is with a bit more detail to help the SMP case):

    - Ownership transferral is made possible using a futex wait+modify
      operation.  The modify part can fail, either if the word doesn't
      have the correct comparison value, or if the waker decides not
      to do ownership transferral.

    - futex_wake always does ownership transferal when there's a
      higher RT priority waiter, and to the highest priority one of
      course.

    - Otherwise, when the selected waiter has higher _dynamic_
      priority, do ownership transferral.  For UP this makes no
      difference - the task is very likely to run and acquire the
      mutex in userspace anyway.  But for SMP, it is essential so that
      when the kernel decides the task is worthy to be run
      immediately, that scheduler policy decision means the task does
      actually acquire the mutex - without kernel help in this case,
      it is very likely to wake up on another CPU and lose the race if
      there is a race.  [ The exact policy for this might be something
      different than comparing dynamic priority values, something more
      appropriate for SMP.  The principle is to allow the kernel's
      scheduling policy decisions to carry over to userspace's ability
      to acquire a mutex. ]

    - Otherwise, if some non-determinatic criterion says to, do
      ownership transferral.  Most times it should not; the occasional
      transferral is there to prevent starvation scenarios.  [ This
      may not be needed.  We may find that applying the kernel's
      dynamic scheduling policy as in the previous point is enough to
      prevent starvation. ]

    - Otherwise, don't do ownership transferral.  The waiter is woken
      but not given the mutex.  It will try to grab the mutex when it
      actually runs, which may be in the kernel (naturally the second
      part of the wait+modify operation), or it may be in userspace.

I think you and I are thinking on similar lines.

-- Jamie




[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]