[RFC] More efficient RTDS scheduler for Xen 4.6

[RFC] More efficient RTDS scheduler for Xen 4.6

[Dagaen Golomb]

[-- Attachment #1.1: Type: text/plain, Size: 2031 bytes --]

Hello everyone,

I'd like to solicit comments on improvements to the RTDS scheduler for Xen
4.6.

The following regards changes to the RTDS scheduler, in line with our
expected next steps as mentioned on the feature wiki page:
http://wiki.xenproject.org/wiki/RTDS-Based-Scheduler#Features_that_are_planned_to_be_developed_after_Xen_4.5
.

[Goal]
The current RTDS scheduler is invoked every 1 millisecond. It does so
without knowing if a new scheduling decision will be made. The proposed
improvement is to redesign the scheduler to be event-driven, so that it is
only invoked at times after an event which may change the schedule has
occurred.

[Motivation]
This change will increase the efficiency of the scheduler by eliminating
invocations when no scheduling decision will be made. The scheduler is
currently ran every 1 millisecond. If no tasks have terminated or budgets
been depleted/replenished since the last scheduling, no changes will be
made. Due to this, the scheduler is currently called at times when no new
action will be taken, wasting processing resources. With the vital role
that the scheduler plays and the frequency at which it is invoked, this
design shift is a relatively important improvement.

[Design Sketch]
To move the scheduler from periodic to event-driven, we plan to add a timer
queue to hold times at which the scheduler should be invoked due to a job
release/termination or budget depletion/replenishment. The scheduler will
schedule jobs as it does currently; however, before finishing it will set
the timer interrupt for re-invoking the scheduler according to the earliest
time in the timer queue. Note that the scheduler will still run right away
for events that require immediate attention, such as when new VCPUs are
inserted, when interrupts for these events are received.

This improvement will only require changes to the RTDS scheduler file
(sched_rt.c) and will not require changes to any other Xen subsystems.

Discussion, comments, and suggestions are welcome.

Regards,
Dagaen Golomb

[-- Attachment #1.2: Type: text/html, Size: 2430 bytes --]

[-- Attachment #2: Type: text/plain, Size: 126 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

Re: [RFC] More efficient RTDS scheduler for Xen 4.6

[Meng Xu]

[Add some quick clarification]
[Add Jan in the cc list]

Thank you Dagaen! :-)

2015-02-22 0:31 GMT-05:00 Dagaen Golomb <dgolomb@seas.upenn.edu>:
> Hello everyone,
>
> I'd like to solicit comments on improvements to the RTDS scheduler for Xen
> 4.6.
>
> The following regards changes to the RTDS scheduler, in line with our
> expected next steps as mentioned on the feature wiki page:
> http://wiki.xenproject.org/wiki/RTDS-Based-Scheduler#Features_that_are_planned_to_be_developed_after_Xen_4.5.
>
> [Goal]
> The current RTDS scheduler is invoked every 1 millisecond.

The current rt_schedule() returns
      ret.time = MIN(snext->budget, MAX_SCHEDULE); /* sched quantum */
where MAX_SCHEDULE is 1ms.
To simply the explanation, we just say the scheduler is invoked every
1ms. But obviously, it may be invoked must faster.

When VCPUs have very large budget value, the next vcpu selected by
rt_schedule() is usually the same as the currently running one. So we
want to reduce the unnecessary invocation of scheduler here.

Let's call the current scheduler as quantum based scheduling.

> It does so
> without knowing if a new scheduling decision will be made. The proposed
> improvement is to redesign the scheduler to be event-driven, so that it is
> only invoked at times after an event which may change the schedule has
> occurred.

Event-driven here means the scheduler should be invoked only at some
specific events, such as when VCPU's budget is depleted, when a VCPU's
next period arrives. We need to set up the timers for the events, so
the proposed scheduler can also be called timer-based scheduling.

>
> [Motivation]
> This change will increase the efficiency of the scheduler by eliminating
> invocations when no scheduling decision will be made. The scheduler is
> currently ran every 1 millisecond. If no tasks have terminated or budgets
> been depleted/replenished since the last scheduling, no changes will be
> made. Due to this, the scheduler is currently called at times when no new
> action will be taken, wasting processing resources. With the vital role that
> the scheduler plays and the frequency at which it is invoked, this design
> shift is a relatively important improvement.
>
> [Design Sketch]
> To move the scheduler from periodic to event-driven, we plan to add a timer
> queue to hold times at which the scheduler should be invoked due to a job
> release/termination or budget depletion/replenishment. The scheduler will
> schedule jobs as it does currently; however, before finishing it will set
> the timer interrupt for re-invoking the scheduler according to the earliest
> time in the timer queue. Note that the scheduler will still run right away
> for events that require immediate attention, such as when new VCPUs are
> inserted, when interrupts for these events are received.
>
> This improvement will only require changes to the RTDS scheduler file
> (sched_rt.c) and will not require changes to any other Xen subsystems.
>
> Discussion, comments, and suggestions are welcome.
>
> Regards,
> Dagaen Golomb


Best,

Meng

-----------
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania

Re: [RFC] More efficient RTDS scheduler for Xen 4.6

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 1504 bytes --]

On Sun, 2015-02-22 at 00:31 -0500, Dagaen Golomb wrote:
> Hello everyone,
>
Hello,

> I'd like to solicit comments on improvements to the RTDS scheduler for
> Xen 4.6.
>
My first comment is that I'm happy that you guys are working on
this! :-)


> [Motivation]
> 
> This change will increase the efficiency of the scheduler by
> eliminating invocations when no scheduling decision will be made. The
> scheduler is currently ran every 1 millisecond. If no tasks have
> terminated or budgets been depleted/replenished since the last
> scheduling, no changes will be made. Due to this, the scheduler is
> currently called at times when no new action will be taken, wasting
> processing resources. With the vital role that the scheduler plays and
> the frequency at which it is invoked, this design shift is a
> relatively important improvement.
>
I don't have much to say about this: I'm the one that suggested to go
for this approach, and I still think it is a goog idea... Looking
forward to see it implemented.

The only possible problem that comes to my mind is the need for a lot of
timers. How many, it will depend on the actual implementation. Using
fewer timer(s) would mean less overhead, but more issues on the event
queue(s).

The only way, I think, we have is just to get down and implement one
solution and see how fast it runs, and whether there are
overhead/scalability issue s(and address them at that time, if it will
be the case).

Regards,
Dario


[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 181 bytes --]

[-- Attachment #2: Type: text/plain, Size: 126 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel