【文件属性】：
文件名称：基于信用度的调度算法实例-含有导频的ofdm信号子载波的调制方式识别方法
文件大小：279KB
文件格式：PDF
更新时间：2021-06-07 17:51:33
Xen VCPU调度
3.2 基于信用度调度算法的基本原理
在基于信用度的调度算法中，每个物理 CPU 都关联一个
由多个VCPU组成的运行队列，每个VCPU都设置有一个 credit
值，信用度 credit 表示 VCPU 的优先值，VCPU 按照 credit 值从
大到小的顺序组成一个链表依次排列。
VCPU 有两种运行状态，UNDER(预设值 1)和 OVER(预
设值-2)。UNDER 表示 VCPU 的 credit 值还有剩余，OVER 表示
VCPU 的 credit 值已经用完。
调度时，物理 CPU 每次选择调度的是队首并且运行状态
处于 UNDER 状态下的 VCPU，并给选择的 VCPU 分配 30msec
的时间片。VCPU 运行时，每 10msec 产生一次中断。中断时，
当前正在运行的 VCPU的 credit值减少 100，如果其 credit 值用
完，那么将其运行状态改为 OVER 状态，它将不再被继续调
度，并重新计算 credit值，重排运行队列，调度链表后面的处于
UNDER 状态下的第一个 VCPU。
如果进行了 3 个时间片 (30ms)，原先的 VCPU 还是处于
UNDER 状态，那么这个 VCPU 也将不被继续调度，重新计算
其 credit 值，调度器选择下一个 VCPU 进行调度。
当所有 VCPU的 credit 值总和变为负值时，将会重新分配
所有的 credit 值。每结算一次 credit 值，VCPU 运行队列就要
重排一次。
在算法的最初设计中，接受到 I/O 等事件的虚拟机的
VCPU 总是被置于队列尾部，虽然调度器会立即重置调度顺
序，但是它总是必须等待它前面所有 VCPU 调度完成后才会
被调度。在响应敏感类应用中，此类调度响应延迟波动明显
且延迟较长。为了解决这个问题，在新设计的基于信用度调
度算法中，为VCPU新加入了一个BOOST运行状态，处于BO-
OST状态的VCPU有最高的优先级，可以优先获得调度。VCPU
通过事件通道接受到一个事件后，进入 BOOST 状态，具有最
高的优先级，如果调度器准许立刻重新调度，那么此VCPU将
会立即被调度。
经实践证明，Credit 算法加入 BOOST 状态后可以大大降
低响应延迟的平均值，对 I/O 带宽也有明显改进。
3.3 调度算法相关数据结构
为了有效监控物理处理器上运行的参与调度的VCPU的
运行状态，调度算法为每个物理处理器定义了 shedule_data[8]数
据结构，用来保存一些相关调度信息，包括一个保护当前
VCPU 的自旋锁、物理处理器上当前运行的 VCPU、物理处理
器空闲时运行的空闲 VCPU 以及一个调度计时器。
struct schedule_data {
spinlock_t schedule_lock; /* 保护当前 VCPU 的自旋锁*/
struct vcpu *curr; /* 当前运行的 VCPU*/
struct vcpu *idle; /* 空闲 VCPU*/
void *sched_priv;
struct timer s_timer; /* 调度计时器*/
} __cacheline_aligned;
调度算法为每个虚拟机设置了一个 csched_dom 数据结
构，用来保存一些与调度相关的信息，其中设置了两个主要的
参数：weight、cap。Weight 值的大小表示虚拟机调度的重要性，
例如，weight 值等于 512 的虚拟机所使用的物理处理器资源
weight 值等于 256 的虚拟机得到的资源的两倍，weight 默认值
为 256；cap表示虚拟机可用 CPU 资源的上限，100 表示上限为
1 个 CPU，60 表示 0.6 个，如果为 0 表示没有上限。
struct csched_dom {
struct list_head active_vcpu;
struct list_head active_sdom_elem;
struct domain *dom;
uint16_t active_vcpu_count; /*域中活动 VCPU 数量*/
uint16_t weight; /*虚拟机调度的相对重要性*/
uint16_t cap; /*虚拟机可用物理 CPU 资源上限*/
};
3.4 基于信用度的调度算法实例
下面以一个实例说明 credit 调度算法：
每个物理CPU都可以保持一个虚拟CPU队列，这些虚拟
CPU 是按照权值从大到小以双向链表的形式组织的。每次需
要调度的时候就从虚拟 CPU 队列中选择合适的虚拟 CPU，并
停止当前虚拟CPU的运行，给其分配运行的时间片进行调度。
一个简单的调度实例如下：
如图 2 所示，物理CPU关联着一个VCPU运行队列，队列
中包含 3 个VCPU，它们按照 credit值从大到小依次排列(credit
值分别为 1200、700、200)。此时，物理 CPU 分配给 VCPU0 运
行，VPCU0 获得调度，其当前 credit 值为 1500。
VCPU0 运行 30msec后，它的 credit值减少为 1200，失去物
理 CPU 的使用权，并按照 credit 值的大小插入到队列的合适
位置(如图 3 所示)。
调度器从队列首部重新选择合适的 VCPU 调度，如图 4
所示，VCPU1 排在队头，credit 值最高，VCPU1 获得调度，得到
物理 CPU 的使用权，开始新一轮调度。
3.5 基于信用度的调度算法关于 SMP 负载平衡
在 SMP 平台上，当某个物理 CPU 对应的虚拟 CPU 队列
中的首个虚拟 CPU 不可调度时，该队列中的所有虚拟 CPU 都
是不可调度的(credit 值从大到小排列)，所以当前物理 CPU 没
有可以调度的 VCPU，此时需要考虑负载平衡。调度算法将从
其它物理处理器对应虚拟CPU队列中找到一个合适的可以调
图 1 虚拟机调度对象
VCPU1 VCPU2 VCPU3 VCPU4 VCPU5 VCPU6 VCPU7
虚拟机 1 虚拟机 2 虚拟机 3
调度器
图 2 虚拟 CPU 调度-当前调度的虚拟 CPU
VCPU0
1500
PCPU head VCPU1 VCPU2 VCPU3
1300 700 200