比例份额调度

评价:
0
(0用户)

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

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

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

彩票数(ticket)代表了进程(或用户或其他)占用了某个资源的份额。例如:假设两个进程 A 和 B,A 拥有 75 张彩票,B 拥有 25 张。因此我们希望 A 占用 75% 的 CPU 时间,而 B 占用 25%。 <!– more –> 我们可以将彩票进行编号,例如:进程 A 拥有 0 到 74 共 75 张彩票,而进程 B 拥有 75 到 99 共 25 张,然后使用随机数来决定运行哪个进程。

彩票机制

彩票货币(ticket currency):

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

彩票转让(ticket transfer)

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

彩票通胀(ticket inflation)

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

实现

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

截屏2021-07-17 下午5.03.40

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;
}

一个例子

截屏2021-07-17 下午5.17.22

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

为什么是不确定的

随机性并不总是产生正确的比例。基于这个原因,之后 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) 数据中心中,比例分配的方式可以更简单高效。

注册并通过认证的用户才可以进行评价!

发表评论