比例份额调度

比例份额(proportional-share)调度程序，也称公平份额(fair-share)调度程序。比例份额算法基于一个简单的想法：调度程序的最终目标是，确保每个工作获得一定比例的 CPU 时间，而不是优化周转时间和响应时间。

彩票调度是一个非常优秀的比例调度程序。

基本概念：彩票数表示份额

彩票数(ticket)代表了进程(或用户或其他)占用了某个资源的份额。例如：假设两个进程 A 和 B，A 拥有 75 张彩票，B 拥有 25 张。因此我们希望 A 占用 75% 的 CPU 时间，而 B 占用 25%。

我们可以将彩票进行编号，例如：进程 A 拥有 0 到 74 共 75 张彩票，而进程 B 拥有 75 到 99 共 25 张，然后使用随机数来决定运行哪个进程。

彩票机制

彩票货币(ticket currency):

运行拥有一组彩票的用户以它们喜欢的某种货币，将彩票分给自己的不同工作，之后操作系统自动将这些货币兑换为正确的全局彩票。

彩票转让(ticket transfer)

通过转让，一个进程可以临时将自己的彩票交给另一个进程。适用于客户端/服务端。

彩票通胀(ticket inflation)

利用通胀，一个进程可以临时提升或降低自己拥有的彩票数量。如果一个进程知道它需要更多 CPU 时间，可以将自己的需求告诉 操作系统，就可以增加自己的彩票。

实现

假定我们用列表记录进程。下面的例子中有 A，B，C 这 3 个进程，每个进程有一定数量的彩票。

int counter = 0;          

int winner = getrandom(0,totaltickets);

node_t *current = head;

while(current){
	counter = counter + cuttent->tickets;
	if(counter > winner)
		break;
	current = current->next;
}

一个例子

只有当工作执行非常多的时间片，彩票调度算法才得到期望的结果。

为什么是不确定的

随机性并不总是产生正确的比例。基于这个原因，之后 Waldspurger 提出了步长调度(stride scheduling)，一个确定性的公平分配算法。

在步长调度中，每个工作都有自己的步长，这个值与票数成反比。在上面的例子中，A，B，C这 3 个工作的票数分别是 100，50和 250，我们通过使用一个大数分别除以它们的票数来获得每个进程的步长。比如用 10000 除以票数值，得到 3 个进程的步长分别为 100，200和40。

每次进程运行后，我们让它的计数器[称为形成(pass)值]增加它的步长，记录它的总体进展。当需要进行调度时，选择目前拥有最小行程值的进程，并且在运行后将该进程的行程值增加一个步长。

current = remove_min(queue);
schedule(current);
current->pass += current->stride;
insert(queue,current);

小结

比例份额调度有两种实现：彩票调度和步长调度。

两者没有得到广泛运行，一方面是不能很好地适合 I/O，另一个原因是最难的票数分配问题没有确定的解决方式。

比例份额调度程序适用于：容易确定份额比例的场合。例如：在虚拟机(virtualized) 数据中心中，比例分配的方式可以更简单高效。