Re: [PATCH 1/1] Improved RTDS scheduler

[Tianyang Chen <tiche@seas.upenn.edu>]

On 1/4/2016 9:36 AM, Dario Faggioli wrote:
> On Mon, 2016-01-04 at 21:48 +0800, Meng Xu wrote:
>> On Mon, Jan 4, 2016 at 7:42 PM, Ian Campbell <ian.campbell@citrix.com
>>> wrote:
>>> On Thu, 2015-12-31 at 04:45 -0500, Tianyang Chen wrote:
>>>> Budget replenishment is now handled by a dedicated timer which is
>>>> triggered at the most imminent release time of all runnable
>>>> vcpus.
>>>>
>>>> Signed-off-by: Tianyang Chen <tiche@seas.upenn.edu>
>>>> Signed-off-by: Meng Xu <mengxu@cis.upenn.edu>
>>>> Signed-off-by: Dagaen Golomb <dgolomb@seas.upenn.edu>
>>>> ---
>>>>   0000-cover-letter.patch            |   16 +++
>>>>   0001-Improved-RTDS-scheduler.patch |  280
>>>> ++++++++++++++++++++++++++++++++++++
>>>>   bak                                |   62 ++++++++
>>>
>>> I assume you didn't actually intend to commit those ;-)
>>
>> No. This version was sent by mistake. Please ignore this version. :-(
>>
>> Tianyang sent another version (v2) with the subject "[PATCH V2 1/1]
>> Improved RTDS scheduler".
>>
> Indeed. BTW, I'm back today from Winter Holidays. I'll give a look at
> this series as soon as practical.
>
> I'll comment directly on V2, with the only exception of this very
> email.
>
> So, first of all, Cc list (which is the same here and in V2): how have
> the names of the people that are in there been picked?
>

Dario: I picked the names based on previous discussion threads between 
you, Meng and Dagaen. Now I have changed who will be cc'ed so they won't 
be bothered.

> The patch is only about xen/common/sched_rt.c. As per MAINTAINERS, the
> maintainer of the code hosted in that file is just me. Surely it's a
> good thing to also include George, as he's the other maintainer of
> scheduling in general.
>
> All the other people, though, should not be bothered by being copied
> directly... Especially IanC and IanJ, I'd say.
>
>>> (In general single patches do not require a separate cover letter
>>> unless
>>> the required context contains a large amount of information which
>>> is not
>>> appropriate for the commit message of the actual change, I'll leave
>>> it to
>>> you and the scheduler maintainers to decide how much of your cover
>>> letter
>>> it would be appropriate to move to the commit message).
>>
>> The cover letter is supposed to explain the design idea of the
>> improved RTDS scheduler so that reviewers could (potentially) save
>> time in reviewing the patch, we think. :-)
>> Probably, the commit message should be refined and self-contained?
>>
> That's true. In particular, the "context", defined as summary of what
> happened and have been discussed on the mailing list before, during
> previous submissions, etc., definitely belongs to a cover letter.
>

There are pages of discussions on the current design and we figured we 
should make a cover page to summarize it and put more details in.

> High level design ideas and concepts, also do, e.g., in order to avoid
> ending up with commit changelogs that are all several pages long! :-)
>
> All that being said, we certainly want patches' subject lines and
> changelogs to be descriptive of at least what is being done, and why.
> If we commit this as it is right now, here it is what we'll find in
> `git log':
>
>    Improved RTDS scheduler
>
>    Budget replenishment is now handled by a dedicated timer which is
>    triggered at the most imminent release time of all runnable vcpus.
>
> Which won't, I'm quite sure about it, be that much useful when looking
> at it, say, in 3 years! :-D
>
> I know, finding the proper balance of what's better put where is not
> always super easy, especially at the beginning... but that's part of
> the process of cooking a good patch (series) :-)
>

> A few suggestions:
>
>   - we want tags in the subject. E.g., in this case, something like
>     "xen: sched: Improved RTDS scheduler"
>
>   - avoid (in both subject and changelog) generic terms like "improve"
>     "fix", etc., unless you can explain more specifically to what they
>     refer... I mean, pretty much all commits that touch sched_rt.c can
>     have "Improve RTDS" as a subject, can't they? (Unless we decide to
>     commit something making things deliberately worse!! :-))
>


Good call.

>     In this case, e.g. (although, perhaps a bit long):
>       "xen: sched: convert RTDS from time to event driven model"
>
>   - as Ian said, there are information in the cover letter that can
>     well be moved in the changelog, making it a lot more useful, and
>     not less refined or self contained.
>

Here is what I propose, please let me know your thoughts:

Cover letter:
1. How this patch could improve RTDS
2. Summary of previous discussion

Current RTDS scheduler is time driven and is called every 1ms. During 
each scheduler call, the repl_update() scans both runq and depeletedq, 
which might not be necessary every 1ms.

Since each vcpu is implemented as a deferable server, budget is 
preserved during its period and refilled in the next. It is not 
necessary to check every 1ms as the current design does. The 
replenishment is needed at the nearest next period(nearest 
current_deadline) of all runnable vcpus.

This improved design tries to reduce scheduler invocation by using an 
event driven approach;rt_schedule() will return a value when the 
scheduler needs to be called next time. In addition, the sched_rt will 
have one dedicated timer to handle replenishment when necessary. In 
other words, the budget replenishment and scheduler 
decision(rt_schedule) are separated.
----------------------------------------------------------------------

Changelog:
1. Changed/removed functions
2. Function graphs for handler and rt_schedule

xen: sched: convert RTDS from time to event driven model

Budget replenishment and enforcement are separated by adding a 
replenishment timer, which fires at the next most imminent release time 
of all runnable vcpus.

repl_handler(): a timer handler which is reprogrammed to fire at the 
nearest vcpu deadline to replenish vcpus on runq and depeletedq. When 
the replenishment is done, each replenished vcpu in the runq should 
tickle a pcpu to see if it needs to preempt any running vcpus.

rt_schedule(): picks the highest runnable vcpu based on cpu affinity and 
ret.time will be passed to schedule(). repl_update() has been removed.

The following functions have major changes:

rt_vcpu_wake(): when a vcpu is awake, it tickles instead of picking one 
from runq.

rt_context_saved(): when context switching is finished, the preempted 
vcpu will be put back into the runq. Picking from runq and tickling are 
removed.

schedule.c SCHEDULE_SOFTIRQ:
     rt_schedule():
         [spin_lock]
         burn_budget(scurr)
         snext = runq_pick()
         [spin_unlock]


sched_rt.c TIMER_SOFTIRQ
     replenishment_timer_handler()
         [spin_lock]
         <for_each_depleted_vcpu(i, i.repl_time < NOW()) {
             replenish(i)
             runq_tickle(i)
         }>
         program_timer()
         [spin_lock]



Thanks,
Tianyang Chen
> Thanks and Regards,
> Dario
>