[Barrelfish-users] Proposal: separate thread scheduling policy

[Chothia Zaheer]

Hi Kornilios and Andrew,

Thanks for the valuable input.  Given that I am still exploring how to exploit
this from the application side, I will hold off on something concrete for the
moment.  As pointed out, a more general mechanism will need to address the
safety concerns and expose internal state in a more controlled fashion.
Nonetheless, attached is a revised patch with just the policy separation.

Cheers,

--Zaheer

> -----Original Message-----
> From: Kornilios Kourtis
> Sent: 04 April 2013 10:53
> To: Andrew Baumann
> Cc: Chothia Zaheer; barrelfish-users at lists.inf.ethz.ch
> Subject: Re: [Barrelfish-users] Proposal: separate thread scheduling policy
> 
> Hi,
> 
> 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
>  thread_set_secheduler_params(flags)
>  // set scheduling parameters to threads (e.g., priority, deadlines)
>  thread_set_sched_param(flags)
> 
> 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.
> 
> cheers,
> Kornilios.
> 
> 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: thread_consolidate_scheduling_policy.diff
Type: application/octet-stream
Size: 8238 bytes
Desc: thread_consolidate_scheduling_policy.diff
Url : https://lists.inf.ethz.ch/pipermail/barrelfish-users/attachments/20130408/2a4db243/attachment.obj