Xen Credit调度算法

wangluo010

　　Credit调度算法的基本原理



Credit调度算法是自Xen3.0版本以来使用的缺省的调度算法，其为一种按比例公平共享的非抢占式调度算法。Credit调度算法为每一个Guest操作系统设置二元组(weight，cap)，各个Guest操作系统之间weight的比例决定它们各自占用CPU时间片的比例；而cap决定一个Guest操作系统用CPU时间的上限值，比如cap=50，表示Guest操作系统只能最多只能占用半个物理CPU的所有时间，cap=100，表示Guest操作系统只能最多只能占用一个物理CPU的所有时间。


Credit调度算法将各个虚拟CPU分为两个队列，under队列和over队列，它只调度Under队列中的虚拟CPU。最开始所有的虚拟CPU都在under队列，每个domain的初始Credit为其对应的weight值；每当虚拟CPU被调度时，这个虚拟CPU对应的domain的Credit就被减小，当发现虚拟CPU对应的domain的Credit为负数时，这个虚拟CPU就被放入over队列；当所有的虚拟CPU都在over队列中时，Credit调度算法按比例为所有的domain的Credit加上最初为domain设置的weight值，并把对应的虚拟CPU入至under队列；周而复始。系统每次调度处于队首且优先级为under的VCPU运行。当一个处理器空闲时或该处理器的就绪VCPU队列中无under优先级的VCPU时，它将查看其它处理器以找到一个可运行的VCPU到本处理器上运行。



目前，对Credit算法的研究主要集中在该算法对系统性能影响方面。其中，Ludmila Cherkasova对该算法在Xen虚拟机管理器中上应用时的磁盘读写速度，网络吞吐量和CPU分配精度的影响进行了分析；Diego Ongaro分析了Credit算法对Xen上虚拟机I/O性能的影响。　　
　　Credit调度算法的优缺点



Credit调度算法的最大优点在于，它可以全局管理多个物理CPU，从而将CPU时间公平高效地分配给各个虚拟CPU。它可以用SMP的方式将各个物理CPU分配给务个虚拟CPU，实现负载平衡：它可以通过调节Guest操作系统的cap参数很好的实现Non-Working-Conserving(NWC)调度模式，使得管理员可以很容易地控制物理CPU的分配情况。

Credit调度算法的缺点在于不能保证实时性，响应速度要求较高的应用中，事件响应延迟与其所处的队列位置密切相关，响应延迟 普遍较长且波动明显。该算法的全局负载平衡策略过于简单，仍易导致处理器因进程未就绪而空闲的情况。由于全局分配而产生的CPU分配错误率比较高，使得管理更加复杂。



Each VM is assigned a weight and a cap. If the cap is 0, then
the VM can receive any extra CPU (WC-mode). A non-zero cap
(expressed as a percentage) limits the amount of CPU a VM receives
(NWC-mode). The Credit scheduler uses 30 ms time slices for CPU
allocation. A VM (VCPU) receives 30 ms before being preempted
to run another VM. Once every 30 ms, the priorities (credits) of all
runnable VMs are recalculated. The scheduler monitors resource
usage every 10 ms. To some degree, Credit’s computation of credits
resembles virtual time computation in BVT. However, BVT has a
context switch allowance C for defining a different size of the basic
time slice (time quantum), and an additional low-latency support (via
warp) for real-time applications.
In summary, Credit has the following features:
? non-preemptive, WC and NWC modes;
? global load balancing on multiprocessors.
In the next section, we present results of a performance study comparing
these schedulers and their features in more detail.
Domain有两种状态，UNDER和OVER。OVER表示虚拟机的credit值已用完，UNDER表示credit值还有剩余。在进行调度时，调度器只关心虚拟机所处的状态，而不会进一步关心其剩余的credit值，处于UNDER状态的虚拟机优先于OVER状态的虚拟机被调度，只有当UNDER状态的虚拟机都无法运行时才会调度到OVER状态的虚拟机，所以，只有当处理器空闲时才允许破坏credit的公平性调度策略。处于相同状态的虚拟机按照先进先出的方式运行，当处于队列首部的虚拟机被调度到时，在其credit值足够的情况下，允许其运行三个调度时长，即30ms。系统每隔10ms触发一次调度中断，当前正在运行的虚拟机会被减掉100个credit，当所有虚拟机的credit值总和变为负值时，为所有虚拟机重新分配credit:
1.每个物理CPU下面都有一个虚拟CPU的运行队列
2.每个运行队列中的VCPU都有一个credit值
3. credit表示VCPU的priority的价值
4.CPU调度的是最先入队的处于under状态下的VCPU
5.每10msec 为一个时间片，相应一次中断。如果被调度的VCPU的credit处于OVER状态那么它将不再被继续调度，重新计算credit值，调度后面的处于under状态下的第一个VCPU
6.如果进行了3个时间片也就是30msec时，原先的VCPU还是没有处于OVER状态，那么这个VCPU也将不被继续调度，credit值的重计算，同5后面的步骤
7.代码中的计算公式VCPU的credit = credit –CSCHED_CREDITS_PER_TICK （100）+30msec/n(VCPU的数)
8.处于OVER状态的VCPU credit的值不被增加。