C|进程调度|公平调度Lottery&CFS

除了上一篇文章提到的MLFQ外，另一种调度名为proportional-share/fair-share，这种调度policy的目标是控制每个进程占用CPU时间的比例。这种policy的一种早期实现名为lottery scheduling，意思是应该运行更久的进程会更有机会获得lottery（彩票中奖，喻CPU使用）。linux内部则使用CFS作为另一种实现。

How can we design a scheduler to share the CPU in a proportional manner? What are the key mechanisms for doing so? How effective are they？

基本概念：票券=份额

进程所持有的Ticket，用于表征进程所应有的资源份额（share of resource）。

调度器将会随机选出一则中奖券，拥有中奖券的进程就被调度。尽管抽取的过程是随机的，但是大数定律表明在长期运行的情况下，被调度概率将会趋近于ticket的比例。

Mechanism

Ticket Currency（货币）

不同User可以分发自己手头的货币给自己的job，这些货币最后会折算成全局的Ticket。

Ticket Transfer（转移）

进程可以暂时地转移自己的票券给另一个进程，以处理突发的需求（如server突然处理信息）

Ticket Inflation（通胀/通缩）

进程可以暂时地增加或减少自己的票券，通常用于一组互相信任的进程之间，这样资源短期分配改变就无需通信了。

Implementation

//伪代码
// counter: used to track if we’ve found the winner yet
int counter = 0;

// winner: use some call to a random number generator to
// get a value, between 0 and the total # of tickets
int winner = getrandom(0, totaltickets);

// current: use this to walk through the list of jobs
node_t *current = head;
while (current) {
counter = counter + current->tickets;
if (counter > winner)
break; // found the winner
current = current->next;
}
// ’current’ is the winner: schedule it...

就是单纯生成一个随机数...然后遍历所有进程，看随机数处于哪个进程里面。

但是，计算机生成的随机数在取模到某个区间后是不均匀分布的，所以需要其他算法，如。

// Assumes 0 <= max <= RAND_MAX
// Returns in the closed interval [0, max]
long random_at_most(long max) {
  unsigned long
    // max <= RAND_MAX < ULONG_MAX, so this is okay.
    num_bins = (unsigned long) max + 1,
    num_rand = (unsigned long) RAND_MAX + 1,
    bin_size = num_rand / num_bins,
    defect   = num_rand % num_bins;

  long x;
  do {
   x = random();
  }
  // This is carefully written not to overflow
  while (num_rand - defect <= (unsigned long)x);

  // Truncated division is intentional
  return x/bin_size;
}

为了尽可能减少遍历链表的次数，应该把ticket多的进程放在表前，因此链表最好有序。

Ticket Assignment

依赖于具体实现，如何allocate这些ticket

Stride Scheduling

假设一共100张票，ABC分别为10/5/25,那么stride步长为10/20/4（名为stride）

同时维护另一个变量，每次进程运行，计数器将会自增（名为pass）

调度方法：

每次挑pass最小的进程，自增量为stride。

curr = remove_min(queue); // pick client with min pass
schedule(curr); // run for quantum
curr->pass += curr->stride; // update pass using stride
insert(queue, curr); // return curr to queue

然而，这样虽然减少了生成随机数的开销，但是pass值就很尴尬，假如加入新的进程，那么pass的值就不好设置了。因此这种策略不容易实现。

The Linux Completely Fair Scheduler (CFS)

Linux使用了CFS作为调度算法，为了按比例分配CPU，它使用了基于计数的virtual runtime技巧。

正常情况，进程vruntime增长将会和物理时间增长速度成正比，操作系统将会选择vruntime最小的进程进行调度，并对每个进程划分相应的time slice。但这也导致了一个问题，什么时候切换出去呢？有这样几个参数。

sched latency

进程应该跑多久（通常48ms/进程数）

min granularity

进程最小的time slice

由于使用了time counter，因此这些运行时间将会和中断周期成整数倍。尽管实际运行时间不一定是整数倍，但是因为vruntime的存在，记录的时间还是精确的。

weighting（Niceness）

每个进程的nice值从-19到20，并被映射到不同的权重。然后按比例分配time slice即可。注意这里的比例基本是近似于等比增长

static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};

R-B Tree

linux使用红黑树存储所有正在运行的进程的节点（不包含sleeping进程），目的是可以在找到vruntime最小的进程并调度后，插入时仍然可以

为了防止苏醒的进程的vruntime远远落后于其他进程而导致starvation，当进程苏醒之后，vruntime将会是树中最小的vruntime。当然这会牺牲一定的公平性。