Xen project Mailing List

Dear Dario

Thanks for feedback on the comment

In O.S. it is scheduling of processes where equal priority jobs are always handled with FCFS.

credit scheduler alsoÂfollows same thing where equal priority VCPUÂs are scheduled with FCFS.

In Credit Scheduler there are three priorities BOOST,UNDER,OVER

Local run queue is sorted on these priorities.

If we focus on UNDER priorityÂ,e.g. VCPU having 512 Credits and VCPU having 256 creditsÂwill have same priority

and First VCPU (512)will scheduled first and second VCPU (256) will have to wait though it has less credit.

In Such scenario instead of FCFS if will follow Shortest Credit Next it will reduce overall average waiting time and context switch time hence bit enhancement in performance is possible.

In OS limitation of SJF is calculation of process time but here in Credit Scheduler credits are already known and computed after every 10 milliseconds is additional advantage for implementation.

The fact is definitely useful if implemented successfully

Please Pass CommentsÂ for further motivations

Thanks and Regards

Rajendra

On Mon, May 18, 2015 at 8:23 PM, Dario Faggioli <dario.faggioli@xxxxxxxxxx> wrote:

[Adding George. In future, if you are interested in getting feedback on
a particular subsystem, look for it in the MAINTAINERS file, and Cc the
address(es) you find there]

On Mon, 2015-05-18 at 13:24 +0530, Rajendra Bele wrote:
> As per my knowledge.
> Credit scheduler sorts its queue of VCPUs with priority based on
> credit value.
>
Yes and no. :-)

This is probably formally correct, as:
Â1. when sorting it, we do rearrange the runq in priority order
Â2. the priority of a vCPU is _based_ on credits, as being in UNDER or
Â Â in OVER state does depend on credits

However, as stated here:

/*
Â* This is a O(n) optimized sort of the runq.
Â*
Â* Time-share VCPUs can only be one of two priorities, UNDER or OVER. We walk
Â* through the runq and move up any UNDERs that are preceded by OVERS. We
Â* remember the last UNDER to make the move up operation O(1).
Â*/
static void
csched_runq_sort(struct csched_private *prv, unsigned int cpu)

there are only two priorities, so, for Credit, "sorts its queue of VCPUs
with priority based on credit value" means "all the UNDER vCPUs come
before any OVER vCPU"... was that what you meant?

BTW, this is one of the differences between Credit and Credit2, as in
Credit2, the runqueues are kept sorted by credit order...

> It follows FCFS technique for equal priority if we apply SJF for equal
> priority
> will be helpful to reduce waiting time spend in the queue basically
> for the Under Priority (credits>0) VCPUs.
>
Yes, I think that treating the various vCPUs in UNDER differently,
basing on some parameter/state/etc. of them would be good... actually,
that's why I like Credit2, and why we're trying to make it usable in
production.

Doing the same in Credit is of course possible, but I fear it would
reveal really complex. Then, again, we already have Credit2 doing
something like that... So I think that anyone wanting a scheduler with a
similar property should invest time in Credit2, rather than trying to
tweak Credit1 into that.

But then, of course, I may be wrong, and you'll come up with a 15 lines
patch that does the trick! ;-P

Anyway, you're mentioning SJF, which would indeed be great, if it
weren't impossible to implement: "Another disadvantage of using shortest
job next is that the total execution time of a job must be known before
execution" (http://en.wikipedia.org/wiki/Shortest_job_next ) :-(

How where you thinking to approximate the execution time of upcoming
execution instance of a vCPU? I'm asking because, per my experience, the
method chosen for that purpose has quite a bit of influence in the
effectiveness of a particular SJF implementation.

> obliviously situation is rare but will make sense when large no of VM
> are active.
>
I'm not sure I'm getting what you mean here. What's rare, that there are
many vCPUs in UNDER? I don't think it is. Or, in any case, it certainly
is the typical situation in which a scheduler is important (if there is
less work than CPUs, the scheduler does not count that much!), so it's a
good scenario to consider and try to improve... Or were you referring to
something else?

> If anybody working on this wants his/her comments on this idea
>
I don't think there is anyone working on this particular item, but
scheduling is certainly receiving some attention, and we're always happy
to discuss potential new features, improvements, and alike! :-)

Regards,
Dario

Re: [Xen-devel] xen scheduler