Xen CPU调度算法

SEDF (Simple earliest deadline first) SEDF是按照最早截止日期优先调度的算法。 其基本思想： 每一个vm都有一个三元组（s,p,x）p表示周期的时间，s表示一个周期需要完成的任务数，x表示完成指定任务后等待还是直接进入下一个周期工作，x的取值只有0或者是1，0表示等待一个周期的全部执行才进入下一个周期，1则表示不用等待直接进入下一个周期。在CPU执行的每一个时刻会重新统计每个vm的最早截止日期并执行最早截止的vm. SEDF Example vm1(1,2,0) vm1(2,7,0) 注：<<表示正无穷，优先级变为最低， vm1 vm2 都为正无穷的时候 表示cpu不会执行，等待下一个时刻的计算。 vm1 的CPU的利用率 50% vm2的CPU的利用率为 4/7 总的CPU利用率为 11/14

当三元组的x为1的时候 CPU不再等待，工作完成直接进入下一个周期 总的CPU利用率为100%

优点是：效率很高、实现容易；易于推断及计算；支持working-conserving和non-working-conserving；支持实时性较强的应用；当系统负载较轻时，其处理器的利用率最高可达100%。

2.BVT(Borrowed Virtual Time) BVT是一种公平性优先的调度算法 计算方法为Vi =Vt + t/wi At为上一时刻的计算值， t为一个时间片 wi为每一个vm的权值 BVT example

vm1: t1 = 0 + 1/0.1 = 10 vm2 : 0 + 1/0.05=20 < vm1 执行 vm1 t2= 10 + 1/0.1=20 vm2: 0+1/0.05=20 =vm1 随意执行 假设执行vm2 t3=10 + 1/0.1=20 vm2: 20+1/0.05=40