Comparison of the Three CPU Schedulers in Xen

http://hi.baidu.com/ctgu_xujie/blog/item/af5b67d4b61d3f2306088b26.html

Note: Mostly From the paper:Comparisonof the Three CPUSchedulersinXen

Xen的CPU调度算法主要有3种，BVT（borrowed virtual time）调度算法、SEDF（simple earliest deadline first）调度算法、以及Credit调度算法。

一、BVT调度算法

1.BVT调度算法的基本原理 BVT算法由 KermethJ.Duda于1999年提出。BVT是一种公平性优先的调度算法。该算法将时间分为实际时间和虚拟时间:真实时间为硬件计时器记录的时间;虚拟时间为对真实时间经过某种规则计算后得到的时间值。该算法用虚拟时间来监控进程的执行时间，每次总是调度具有最早的有效虚拟时间的VCPU。这这种调度算法考虑到了运行实时和交互件的戍用程序的一些Guest操作系统，允许这些操作系统“借”一些时间片，就是说：在一定范围内将未来分配给它运行的时问片先“借”过来用一段时间。这种“借”过来的虚拟时间片只能是当前真实的时间片中的某个虚拟时间片，不能借下一个真实时间片中的虚拟时问片。在系统初始化时，每个VCPU将分配一个权值来代表该VCPU能获得的处理器份额。VCPU根据其权值来实现处理器的公平共享。系统用实际虚拟时间和有效虚拟时间来记录VCPU运行状态。其计算方式如下: Ai =At + t/wi Ei <— Ai - (warp?wi:0) 其中，t表示VCPU实际运行时长(由真实时间计算);wi表示该VCPU的权值大小;Ei表示有效虚拟时间;Ai表示实际虚拟时间;warp为时间偏移标记，表示VCPU能否提前运行;矶为VCPU能提前运行的虚拟时间长度。 BVT算法是一种抢占式的working-conserving模式算法。该算法通过warp值来调整EVT使VCPU获得处理器的时间提前，即VCPU从预定的有效虚拟时间中借用了一定的虚拟时间以获得更高的调度优先级。此外，该算法还用Li和Ui来限制VCPU的warp值的大小及进行warp操作的频率，以防止进程过度借用虚拟时间。

2.BVT的优缺点 BVT调度算法的优点在于可以将物理时间片公平、均匀地分配给各个Guest操作系统，每个Guest操作系统两次被调度的时间间隔不会超过一个真实的时间片；能够满足I/O密集型和实时应用的低时延要求，能较好地调度某些实时性要求比较高的操作系统；在单CPU和多CPU环境下的调度开销都比较小。 BVT调度算法的缺点有以下几点。首先，BVT不支持non-working-conserving。也就是说，每当当前domain被加载运行时，它将获得整个CPU。用户不能把某个将某个domain对CPU的使用限制在某个比例以下。其次，每个Guest OS只能借用分给它的时间片部分，而不会剥夺其他Guest OS的时间片。即当确定了各个domain的时间片分配比例后，这个比例在下次分配之前不会改变。

二、SEDF调度算法

1.SEDF调度算法的基本原理 SEDF算法源于C.L.Liu在1973年提出的最早截止期限(EDF:Earliest DeadlineFirst)调度算法。Xen中的每个VCPU在初始化时，将由调度算法为该VCPU设定一个截止期限作为其被调度时的参考因素。当进行VCPU调度时，调度程序将优先调度截止期限最早的VCPU。与Credit算法一样，当前对SEDF算法的研究还仅限于对配置有该算法的Xen的性能(磁盘读写速度、网络吞吐量、CPU分配精度、I/O性能)影响进行了分析。 SEDF算法为一种动态优先级调度算法。VCPU的优先级随着其绝对截止期限的变化而改变。在任何时刻，具有最早绝对截止期限的VCPU优先级最高。当处理器进行VCPU调度时，将总是调度具有最早绝对截止期限的VCPU到该处理器上运行。 SEDF调度算法是这样工作的：它为每个Guest操作系统设置一个三元组(s，p，x)，其中s，p指的是在p毫秒内，Guest操作系统至少运行s毫秒，而x指的是如果在p时间片内，还有空余时间的话，是否允许该Guest操作系统占用这些空余的时间片；而每个Guest操作系统都有一个“最迟调度时间”(例如，0-100ms这个时间片内，若Guest操作系统至少运行30ms那么它的最迟运行时间是70ms)，调度算法选择“最迟调度时间”最早的Guest操作系统进行调度：如果Guest A操作系统还任运行，Guest B操作系统的调度时间片已经到来，那么Xen将选用Guest B进行调度。 SEDF支持working-conserving和non-working-conserving。即可以分配部分CPU给一个Guest OS.

2.SEDF调度算法的优缺点

优点：

a. 可以通过配置各Guest操作系统的配置参数调节它们的优先级(一个Guest操作系统的p越小，优先级就越高)。

b. 这个算法效率很高、实现容易；易于推断及计算；

c. 支持working-conserving和non-working-conserving；

d. 支持实时性较强的应用；

e. 当系统负载较轻时，其处理器的利用率最高可达100%.

缺点：

a. 在SEDF算法中，一旦VCPU的调度参数被初始化后，就不能根据该VCPU的运行状况进行修改。

b. SEDF调度算法是根据任务满足截止期限的紧迫性，来修改任务的优先级，以保证最紧迫的任务能够及时完成。当系统的负载相对较低时，这种算法非常有效；但是当系统负载极端沉重时，这就会使大量的任务发生时问错误(misSing the deadline)，因此很可能使一些进程困错过截止期，来不及处理而夭折；甚至可能导致CPU时间大量花费在调度上，这时系统的性能还不如FIFO方法。根据计算，当系统负载超过50％时系统性能会急剧下降，其主要问题在于：如何使进程按照到达最后期限的时间排序。因为进程到达期限的时间在执行期间是变化的，这样进程就无法给予事先排序，每一个进程结束时，优先级都必须重新计算。 还有一个重要缺点，这种算法只能对单个CPU进行SEDF调度，没有多CPU间负载平衡的控制。例如存在如下分配： 分配CPU1: dom1 --- 80% CPU，分配CPU2: dom2 --- 80% CPU，如果此时有dom3，需要30% CPU 空间，那么dom3将无法被分配和加载。即使两个CPU的剩余部分相加起来足够dom3的使用，但是由于每个CPU的剩余部分都不足，dom3只能等待。

三、Credit调度算法

1.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性能的影响。

2.Credit调度算法的优缺点 Credit调度算法的最大优点在于，它可以全局管理多个物理CPU，从而将CPU时间公平高效地分配给各个虚拟CPU。它可以用SMP的方式将各个物理CPU分配给务个虚拟CPU，实现负载平衡：它可以通过调节Guest操作系统的cap参数很好的实现Non-Working-Conserving(NWC)调度模式，使得管理员可以很容易地控制物理CPU的分配情况。 Credit调度算法的缺点在于不能保证实时性，响应速度要求较高的应用中，事件响应延迟与其所处的队列位置密切相关，响应延迟普遍较长且波动明显。该算法的全局负载平衡策略过于简单，仍易导致处理器因进程未就绪而空闲的情况。由于全局分配而产生的CPU分配错误率比较高，使得管理更加复杂。