策略：比例份额调度

彩票调度的概念

• 在现代，比例份额调度有一个很不错的例子，名为“彩票调度”
• 每个进程拥有一些彩票，它们的数量可以不一样。每隔一段时间，就会进行一次彩票抽奖，以确定接下来应该执行哪个进程。拥有彩票数量更多的进程，就会更频繁地进行
• 彩票调度提供了一些机制来灵活地管理彩票的分配与转移
• 彩票调度使用一个随机数生成器来生成彩票编号，然后通过遍历链表寻找拥有此编号的彩票的进程

彩票机制

• 彩票货币(Ticket Currency)
  • 彩票货币允许每个用户拥有一些彩票，这些用户可以以它们喜欢的方式将彩票分配给自己的工作
  • 系统拥有一个全局的、统一的彩票视图，在此视图下每个用户拥有的彩票数量相同。每个用户可以有自己的彩票货币，即它们的货币数量可以不同，但是它们在最终决策时会被换算为同一个单位，在此单位下每个用户的彩票数量数值相同，同样的，每个进程的彩票数也会被换算
  • 例：用户α拥有100张货币，两个进程A、B；用户β拥有10张货币，一个进程C。α将货币分给A50张，B50张；β将10张货币全部给C。最后系统在换算时会认为A50张彩票，B50张彩票，C100张彩票，总彩票数为200张
• 彩票转让(Ticket Transfer)
  • 一个进程可以临时把自己的彩票转让给另一个进程
  • 例：在一个C/S架构程序中，客户端给服务端发送消息后，很可能就会将自己的一些彩票转让给服务端，来让服务端有更多的机会处理自己的消息，服务端执行完毕后就会归还这些彩票
• 彩票通膨(Ticket Inflation)
  • 通过膨胀，一个进程可以临时提升或降低自己的彩票数量
  • 不过在竞争环境中，可能每个进程都会贪婪地膨胀自己的彩票，这会让机制毫无意义
  • 在相互信任的环境中，彩票膨胀才会有意义；需要膨胀的进程只需要告诉OS“我想增加我的彩票数量，我需要更多的运行时间”，然后它的彩票数量就会增加，这一点无需告知其它进程

彩票实现

1. 假设现在系统里有进程A（10张彩票），进程B（20张彩票），进程C（50张彩票），OS就会计算出彩票共有80张。于是给这些彩票分配编号0~79。
2. OS将进程放入链表中（放入时排列并不是必须的，不过降序排列可以更快速地命中目标编号区间。此处使用降序排列，记录它们的彩票编号末端）。进程C有049的，进程B有5069的，进程A有70~79的。C->59、B->69、A->79被记录下来了
3. 然后OS通过一个随机数生成器生成一个0~79内的数，假设它生成了编号75
4. OS开始正序遍历链表，首先看到C的末端是59，75>59，抽中的肯定不是C的彩票；然后看到B的末端是69,75>69，B也没中奖；再看A，75<79，说明编号75在A的彩票编号区间内，A中奖了，于是接下来执行A进程

彩票调度的特点

• 由于彩票调度依赖随机数，所以只能有概率上的公平，实际的频率会有所偏差

步长调度的概念

• 步长调度并不是通过随机值的方式确定接下来的进程，而是通过特定的一套算法来确定的
• 每个进程都有彩票数与步长(Stride)，步长与彩票数成反比
• 初始每个进程的行程(Pass)值都为0，每次调度时都选择行程值最小的进程运行（多个行程值都为最小则随机），运行完毕后设置它的：行程值 = 初始行程值+步长

步长调度的策略

1. 首先给每个进程分配彩票数，假设当前系统内有三个进程A、B、C，分别有100张、50张、250张彩票
2. 系统通过一个大数（比如10000）来整除这三个进程的彩票数，得到它们的步长分别为100、200、40
3. 初始每个进程的行程值都为0
4. 开始调度，现在选取一个行程值最小的进程，行程值最小的进程有3个，所以从它们中随机选择，假设选择到了A。让A运行，然后将A的行程值设置为初始行程值+A的步长，即0+100=100（此时步长A:B:C=100:0:0）
5. 下一次调度，选择行程值最小的进程，从B和C中随机选择了B，B运行，其行程值变为0+200=200（此时步长A:B:C=100:200:0）
6. 下一次调度，显然C行程值最小，C运行，行程值=0+40=40（此时步长A:B:C=100:200:40）
7. 下一次调度，还是C的行程值最小，则C运行，其行程值变为40+40=80（此时步长A:B:C=100:200:80）……

步长调度的特点

• 通过确定的算法，每个进程执行的机会都会按照彩票数量实现确定的比例，而不用像彩票调度那样担心随机数带来的比例偏差
• 不过彩票调度不需要一个“行程值”那样的初始状态，任何进程新加进来OS都可以像往常一样抽奖。而步长调度则需要考虑给新加入的进程设置一个初始行程值，如果简单地给它设置0的话那可能就会发生：原有的进程A行程值 : 新加入的进程B行程值=2147483647 : 0，那进程A就会饿肚子。不过此时有一种办法可能可行，就是将新加入的进程行程值设置为当前已存在程序的最小行程值