[Barrelfish-users] Proposal: separate thread scheduling policy

Kornilios Kourtis kornilios.kourtis at inf.ethz.ch
Thu Apr 4 10:53:27 CEST 2013


Here are my 2 cents: I like the separation of the scheduling decision
from everything else in this patch, and I believe is in the right
direction for a more generic solution. As Andrew said, we can apply this
part regardless.

I'm wondering if applications really need to do their own scheduling.
Another (slightly different) approach is to provide pluggable and tunable
schedulers that can be set by the application.

The interface can look something like this:
 // set scheduler
 thread_set_scheduler(THR_SCHEDULER_RR, flags)
 // tune parameters to scheduler
 // set scheduling parameters to threads (e.g., priority, deadlines)

It might be a bit difficult to get the interface right, but we can start
small and simple and build up as needed.

The benefits of this approach is that we don't have to worry about the
application running on the dispatcher stack while disabled, and I believe
we can cover most of the interesting use-cases. If at some point we want
applications acctually doing their own scheduling, we can have a
scheduler (e.g., THR_SCHEDULER_APP) that enables that.


On Wed, Apr 03, 2013 at 08:55:49PM +0000, Andrew Baumann wrote:
> Hi Zaheer,
> Thanks for the patch! While I'm keen to decouple the scheduler from the
> internals of thread management, I don't think this patch is the right
> way to do it. In particular, I'm uneasy about making it easy for
> applications to write code that runs on the dispatcher stack while
> disabled. There are so many ways to shoot oneself in the foot in this
> context it's not funny, so I don't think that directly calling out to
> an application-defined callback from thread_schedule_next_disabled is a
> good idea.
> It's also not clear to me that this callout is sufficient. Presumably a
> non-round-robin scheduler might need to maintain its own data structure
> of threads (not just a circular linked list), and interpose on thread
> creation and destruction in order to do so. A generic interface for
> scheduler-specific thread state would be better than exposing the full
> private internals of the thread structure to the scheduler.
> I'm wondering if we can come up with a safer and more general way of
> making this happen. Here's a strawman: in oldschool L4, user-mode
> schedulers worked by running at high priority (so they were always
> picked) but then yielding the CPU to the thread they really wanted to
> schedule. This should be relatively cheap for us to implement, since we
> do the yield in user-mode anyway. Another idea would be to give
> applications control over the order of threads in the run queue, but
> still do the actual dispatch round-robin. Both of these have obvious
> shortcomings, but they might be good enough for some use-cases?
> Note that the UMS APIs you linked to have a callout for the scheduler,
> but they invoke it on a proper thread context, and they have a defined
> queuing mechanism for delivering events to the scheduler.
> Other comments on the patch:
>  * thread_scheduler_func_t should take a dispatcher handle type.
>  dispatcher_generic is a wonky internal type that shouldn't be exposed.
>  * Why can't the default policy be defined as a callout function
>  conforming to the same API provided to applications?
> By the way, the part of the patch that puts in explicit calls to the
> scheduler where there was previously code to immediately dispatch the
> next thread looks like a good thing to apply regardless.
> Andrew
> -----Original Message-----
> From: Chothia Zaheer [mailto:zchothia at student.ethz.ch] 
> Sent: Wednesday, 3 April 2013 08:22
> To: barrelfish-users at lists.inf.ethz.ch
> Subject: [Barrelfish-users] Proposal: separate thread scheduling policy
> Hello,
> Context: the threads package implements a hard-coded policy for selecting the
> next runnable thread and this logic is spread over several functions.
> (Current default is round-robin with uniform priorities.)
> Objective: consolidate this in a single function and implement an interface so
> applications can easily implement their own policy.
> Notes:
> * I initially thought this interface would serve two distinct aspects:
>   1. Receive notification of interesting events (e.g. thread created/blocked,
>      something now eligible to run, ...)
>   2. Whenever necessary, select the next thread to run (new time slice, yield).
>   In reality though, dispatch occurs immediately in response to an event so the
>   separation isn't quite as clear.
> * Attached is an initial patch which enables an application to override
>   scheduling decisions - for example, I tried co-operative multitasking.
>   - Downside: application now depends on threading internals <threads_priv.h>.
>   - Reason parameter is not of much use on its own; perhaps a payload should
>     also be passed (thread that yielded, duration of new time-slice).
> * Windows 7 has User-Mode Scheduling (UMS) [1, 2] which implements a similar
>   mechanism and makes for an interesting comparison.  It is used in the
>   implementation of their Concurrency Runtime (ConcRT).
> I am interested in any feedback, especially regarding other use cases for
> application-level schedulers and what would be required from such an interface.
> Conclusion: this change will allow applications to implement their own
> scheduling policy without having to duplicate the threads package.
> --Zaheer
> [1] http://msdn.microsoft.com/en-us/library/windows/desktop/dd627187.aspx
> [2] http://indico.cern.ch/getFile.py/access?resId=0&materialId=slides&confId=62731
> _______________________________________________
> Barrelfish-users mailing list
> Barrelfish-users at lists.inf.ethz.ch
> https://lists.inf.ethz.ch/mailman/listinfo/barrelfish-users

Kornilios Kourtis

More information about the Barrelfish-users mailing list