专栏首页苦逼的码农三分钟基础:什么是彩票调度算法?让进程们拼手气?

三分钟基础:什么是彩票调度算法?让进程们拼手气?

来源:tobe的呓语

作者: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 虚拟机,这时候靠彩票调度就很方便了。

所以彩票调度机制还是有一定应用价值的,说不定你以后在哪里就用上了呢?

本文分享自微信公众号 - 苦逼的码农(di201805)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-12-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【性能】计算首屏白屏时间

    后面会把前端进阶的课程内容都总结一遍。有些都是很常见的知识,但是为了梳理自己的知识树,所以尽量模糊的地方都会记录

    神仙朱
  • 比 rm -rf /* 还骚的 Linux 19 个装 B 的命令!

    原文链接:http://www.cnblogs.com/sukai/archive/2013/06/08/312703...

    业余草
  • 剖析Focal Loss损失函数: 消除类别不平衡+挖掘难分样本 | CSDN博文精选

    论文名称:《 Focal Loss for Dense Object Detection 》

    AI科技大本营
  • 交换与选择类排序

    各种排序算法所需辅助空间 1、 所有的简单排序方法(包括:直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1);

    _DIY
  • Java中实现多线程继承Thread类与实现Runnable接口的区别

    1. 通过继承Thread类,重写Thread的run()方法,将线程运行的逻辑放在其中

    爱学习的孙小白
  • 插入类排序—(折半)插入排序、希尔排序

    你或许在写一个sql的order by按照某组进行排序,又或者你在刷一道题时候、常常遇到贪心+自定义排序求解的思路题,或者变态的面试官让你手写快排,又或者是ap...

    用户4372098
  • [PHP] PHP PDO与mysql的连接单例防止超时情况处理

    这个数据库类主要处理了单例模式下创建数据库对象时,如果有两次较长时间的间隔去执行sql操作,再次处理会出现连接失败的问题,利用一个cache数组存放pdo对象与...

    陶士涵
  • 经典面试题-请列出你所了解的若干个不同类型的runtime exception

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java
  • IDEA Debug 无法进入断点的解决方法

    某个多模块项目中使用多个版本的 Spring,如 Spring 4,Spring 5,在使用 IDEA Debug 过程中发现,Spring 部分 jar 如 ...

    andyxh
  • 经典面试题-String s = new String('abc')请问有几个String对象?分别是

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    cwl_java

扫码关注云+社区

领取腾讯云代金券