[Barrelfish-users] Proposal: separate thread scheduling policy

[Andrew Baumann]

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