三分钟基础：什么是彩票调度算法？让进程们拼手气？
- 2019 年 12 月 6 日
- 筆記
作者：tobe
这篇文章主要想介绍下彩票调度（个人觉得这个算法非常有意思~ ），还有随机算法相对传统算法的一点优势，毕竟现在绝大多数算法都是追求确定性，尤其在操作系统，大家都希望一切可控，所以随机算法的出现听起来有些“不合时宜”，但它确实能够解决某些传统算法难以解决的边角问题（算是给自己挖个坑，以后可能会写），也为我们提供了一种新的思路。
以下是正文：
进程调度器今天突然召集大伙，说是要讨论一件重要的事情，问他他还卖关子：“你去了就知道，我现在不告诉你们。”
还没到约定时间，大伙儿就已经来到了内存家，只见进程调度器气定神闲的坐在椅子上，翘着个二郎腿，好不自在。
“调度器老哥，现在人也都来的差不多了，咱们现在就开始吧，早点结束大家伙儿好接着回去干活啊。”
调度器“嗯”了一声，起身走向白板，说：“我向大家先说明一下背景吧，咱们原来的调度算法，比如先来先服务，短进程优先，优先级调度等等，大都是为了优化周转时间和响应时间，效果也还不错。不过这些算法，有些可能会导致饥饿的问题，我想不少进程深有体会。”
tobe 注：关于这几种调度算法，可以看这篇文章——三分钟基础：有哪些经典的进程调度算法？
饥饿问题确实困扰操作系统很长时间了，虽然饥饿不如死锁那么有破坏力，但还是影响到了进程家庭内部的和谐。听调度器的意思，他是能解决这个问题？
几个低优先级进程开始小声议论起来，像他们这种优先级别低的，总会因为高优先级进程“插队”而得不到 CPU 资源，心里早就憋着一口气呢。忍不住问调度器：“现在是有什么好办法了吗？我们可受够饥饿的生活了！”
调度器得意的说：“那当然，不然我今天把你们大伙叫过来干什么？我最近想到一个好点子，咱们可以调整一下调度目标，改成确保每个任务获得一定比例的 CPU 时间，这样只要我们提前约定好份额，每个人最后都可以享受到应有的待遇，不可能出现某一进程独占的现象！听起来是不是很公平？我打算把这类算法叫「比例份额调度」或者「公平份额调度」。”
系统进程质疑道：“公平？你别说大话了，这个目标咱们又不是没有追求过，也就时间片轮转算法勉强达到了我们的要求，可一旦再划分出优先级（指的是多级优先队列调度），就可能会造成进程饥饿，追求公平可不是那么简单的！”
“你先听我说嘛，绝对的公平确实很难达到，我们现在退而求其次，追求一个相对公平——就是说短时间里可能会有些许不公平，但从长期来看，大家在 CPU 上运行的时间所占比例就是一开始约定好的。”
“听起来很有道理，但是你打算怎么实现？”
“嘿嘿，我给这个方法取名叫「彩票调度」，咱们一开始的时候给每个进程发彩票——优先级越高，发的彩票越多，然后每隔一段时间（一个时间片），举行一次彩票抽奖，抽出来的号是谁的，谁就能运行~”
“哈哈哈哈，我还以为是什么厉害的算法呢”，一时间，大家都笑了出来，整个内存里充满了快活的气息。调度器的脸唰的一下就红了。
操作系统吐槽道：“调度器，你是不是跟那帮人类学坏了？在我们这儿还搞什么彩票，下一步是不是打算骗大家的时间片？再这么搞下去，小心我把你职位撤了啊！”
调度器赶紧为自己解释：”诶，我可是经过深思熟虑才想出来的，你们别误会啊！打个比方吧，假如有两个进程 A 和 B，我想让 A 占用 80% 的 CPU 时间，B 占用 20% 的 CPU 时间，我就给 A 发80 张彩票，给 B 发 20 张彩票。这样，每次抽奖的时候，A 就有 80% 的概率占用 CPU，从数学期望上讲，1 秒钟之内，A 能运行 800ms。我是打算利用随机性来达到按比例分配的目标的，可从没打算骗大家。“
操作系统看起来有点认可这个算法了，他点点头：“有点意思，你接着说下去。”
调度器松了一口气，继续说：“我觉得这种算法有个很好的地方——即使某进程只有一张彩票，经过多轮迭代，他总会获得 CPU 的使用权。所以饥饿的问题就能解决了~”
PS：可别跟现实的彩票等价啊，现实彩票中奖率低的吓人。。。没法比的（不信你自己算一算）。
那几个经常饥饿的进程听了，两眼放光，仿佛抓到了希望。
"别急，还没完呢！你们想想，咱们用过的「最短响应比优先」算法，还得记录每个进程在就绪队列等待了多长时间，多麻烦！我这个「彩票调度」，不需要记录任何状态，拿来就用，特别的轻量，而且这种随机方法很快，只要生成一个随机数，就能快速做出决策。为了向你们展示，我还特意写了段伪代码。"
//当进入时钟中断时运行 //counter 用来数哪个进程拿到了 winner 彩票 int counter = 0; //选出胜者，其中 totalticks 是彩票总数 int winner = randint(0, totaltickets); //指针，指向队列里的进程 job_t *current_job = head; while(current_job != null) { counter = counter + current_job->ticket; if (counter > winner)//说明当前进程拿到了 winner 彩票 break; current_job = current_job->next; } //切换至 current 指向的进程
操作系统看完了代码，赞叹道：“好家伙，确实是个简洁的调度算法，简洁的都有点儿不可思议了。不过你这个代码只解决了调度问题，最开始的彩票分配问题你打算怎么解决？”
调度器面露难色：“我这几天也在想这个问题，不过暂时没有想到好的解决方案，所以说要靠试运行来摸索嘛，如果找到好的分配方法，就可以长期运行下去了。”
“确实，我现在也觉得彩票调度这个方法值的一试，咱们明天就按这个调度算法来，看看效果能不能比上现有的算法！”
调度器高兴地叫出来：“好，太好了，我马上就去准备！”
实际上彩票调度并没有在 CPU 调度程序里广泛使用，一个原因是不能很好的适合 I/O（有论文研究过这个问题），另一个原因就是文中所提到的，票数分配问题没有确定的解决方式，比如你新打开了一个浏览器进程，那该给他分配多少票？票数少了，响应跟不上，票数多了，又会浪费 CPU 时间。
与此相比，常见的通用调度程序，比如多级优先队列，就做的很好，因此现在得到了广泛的应用。
但不代表这种思想就没有用了，在某些容易确定份额比例的领域里，比例份额调度程序就可能更有用——比如在虚拟数据中心，你可能希望 1/4 的 CPU 时间给 Windows 虚拟机，剩下的时间给 Linux 虚拟机，这时候靠彩票调度就很方便了。
所以彩票调度机制还是有一定应用价值的，说不定你以后在哪里就用上了呢？
