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?
Cheers, Koki André Braga wrote:
Hello! 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 cautious). 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! André