[haiku-development] Re: The new locking primitives and boosting -- I need some guidance here :)

  • From: "Jorge G. Mare" <kokitomare@xxxxxxxxx>
  • To: haiku-development@xxxxxxxxxxxxx
  • Date: Tue, 24 Jun 2008 19:34:30 -0700

Welcome back André!

Just curious: is this part of the still to be finished "Create a thread scheduler with CPU affinity" GSoC 2007 project, or is this something new?



André Braga wrote:

Back when I was pretty active and keyboard-happy on the mailing lists
and blog, I mentioned that I wished to tweak the locking primitives a
little with an extra parameter, which I called the "brand" of the
primitive (back then I was thinking of semaphores, but I'm afraid this
may no longer be the case). I wanted to add this parameter so the
thread wakeup code would boost said thread when the locking primitive
is branded as belonging to an interactive subsystem, like the GUI. The
reason for doing this is to avoid littering the scheduler code with
heuristic interactivity detection algorithms that most other OSs that
I know of use (in fact I can't name a single example of an OS that
follows my approach -- this might be an all-original idea cooking
here! :D). Linux, for example, has some explicit checks in its
scheduler code for X11-like behaviour and tries to boost the threads
it detects as such.

However, Linux depends on X11 for the GUI, and the X11 people can't
assume much regarding the underlying operating system, its role --
server, desktop, embedded --, its threading model, not to mention the
locking primitives it uses. On the other hand, we own the whole widget
here, and we can use this to our advantage.

Traditionally, the heuristic approach to improve the responsiveness of
interactive processes is to try to infer that said processes are
interactive based on their CPU usage patterns. More concretely
speaking, the amount of time a process spends sleeping is compared to
the amount of time it spends using the CPU, and chances are that if
the process is sleeping a lot, it's probably waiting on interactive
input, or on I/O, or otherwise something that common wisdom suggests
that makes said process a good candidate for boosting, so that it gets
a better chance of running again soon instead of making it wait -- and
potentially hold other processes back that contend for the same
resources said process has acquired exclusive access to -- for some
CPU hog.

I agree with the reasoning, but not with the traditional approach. As
I wrote time and time again, those are heuristics. Heuristics do fail.
They might fire on some inappropriate moment. They might fail to fire
when appropriate. They add to code complexity (I'm not disputing that
they are extremely useful when you try to approximate some optimal
algorithm with a prohibitive order of complexity for a given task).
And really, if we strive for a modern, lean, fast scheduler with quick
context switches, if we can do away with running heuristics inside it,
we should.

Ideally, we would trace every single piece of code that would ever run
on an OS to see if it's acting interactive and if there are no better
candidates around to be graced with CPU time, and the scheduler would
use this knowledge to make its decisions. Some extremely critical
embedded real-time OSs actually do this: every code path is exercised
and get its timings measured and the scheduler is fed with all this
knowledge before the system is deployed.

This is not feasible at all for a general-purpose OS like Haiku.

However, tracing is not the only way to know what code paths a process
follows. When a process (or a thread) blocks, it blocks on a specific
semaphore, a specific mutex, a specific condvar. We could use this
knowledge to boost processes that we *know* to be interactive, because
they blocked on a locking primitive that was declared on a code path
that has to do with interactivity. But instead of feeding the
scheduler with this information directly, we could make the process
wakeup code itself adjust the process priority right before it gets
inserted into the scheduler queues. As soon as this "privileged"
scheduling round is finished, the process either blocks again on a
locking primitive and gets boosted accordingly the next time it wakes
up, or gets demoted back to its actual priority level.

I believe this is an incredibly lightweight, robust and precise way to
detect interactivity, since it's not based on any heuristics, but the
actual code path a process follows. If said process sometimes behaves
CPU-bound and sometimes behaves interactive, it won't be boosted at
the wrong moments; this is much better than *trying* to predict the
future by using some CPU usage history window. Not to mention that
there's zero code overhead except for an extra private call that
creates a branded semaphore, a single numeric variable that holds the
desired boosting level, and a couple extra lines of code on the wakeup
code that tweaks the priority prior to reinserting the thread on the
scheduler queues. And the subsystems can be gradually modified to use
branded locking primitives: nothing in the system will be disturbed at
all, except that the more key locking primitives are converted, the
more responsive the system gets.

I actually can't find a single disadvantage in this approach.

What I don't quite know so far is if this is at all feasible for R1.
I'm not sure how the message-passing synchronisation harmonises with
lower-level locking primitives (i.e., which messages to interactive
subsystems are blocking and which aren't). I don't know if the new
locking primitives that Ingo recently introduced permit such branding
(although I don't quite see any reason it couldn't; I'm just being

Anyway, I'd like to receive feedback regarding this idea I had, and if
possible I'd love to implement it for the R1 timeframe, as I'm on the
verge of becoming free of any college duties that held me back for the
past several months. If we find out it's not feasible for R1, I'd
really like to have it considered for R2.

I'm eagerly waiting for your feedback.

Thanks for your attention!

Other related posts: