每日一博 | 彩票调度算法,让进程们拼手气
这篇文章主要想介绍下彩票调度(个人觉得这个算法非常有意思~ ),还有随机算法相对传统算法的一点优势,毕竟现在绝大多数算法都是追求确定性,尤其在操作系统,大家都希望一切可控,所以随机算法的出现听起来有些“不合时宜”,但它确实能够解决某些传统算法难以解决的边角问题(算是给自己挖个坑,以后可能会写),也为我们提供了一种新的思路。
以下是正文:
进程调度器今天突然召集大伙,说是要讨论一件重要的事情,问他他还卖关子:“你去了就知道,我现在不告诉你们。”
还没到约定时间,大伙儿就已经来到了内存家,只见进程调度器气定神闲的坐在椅子上,翘着个二郎腿,好不自在。
“调度器老哥,现在人也都来的差不多了,咱们现在就开始吧,早点结束大家伙儿好接着回去干活啊。”
调度器“嗯”了一声,起身走向白板,说:“我向大家先说明一下背景吧,咱们原来的调度算法,比如先来先服务,短进程优先,优先级调度等等,大都是为了优化周转时间和响应时间,效果也还不错。不过这些算法,有些可能会导致饥饿的问题,我想不少进程深有体会。”
饥饿问题确实困扰操作系统很长时间了,虽然饥饿不如死锁那么有破坏力,但还是影响到了进程家庭内部的和谐。听调度器的意思,他是能解决这个问题?
几个低优先级进程开始小声议论起来,像他们这种优先级别低的,总会因为高优先级进程“插队”而得不到 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 虚拟机,这时候靠彩票调度就很方便了。
所以彩票调度机制还是有一定应用价值的,说不定你以后在哪里就用上了呢?
希望你在看完我的文章之后有所收获,期待你的赞和转发!
如果本文对你有帮助,欢迎关注我的公众号 tobe的呓语 ,带你深入计算机的世界~ 公众号后台回复关键词【计算机】有惊喜哦~
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Python 取代了 Excel 在银行业务中的地位?
在金融领域,一个初级银行家或者交易员,所具备的能力包括了解 Excel 中所有关于金融建模的知识。但是,现在已经不再是这样了,他们还更应该掌握Python。根据最近在伦敦的 Quant 会议上Nomura(野村证券)的副首席数字官 Matthew Hampson所说: Python已经取代了 Excel。在交易大厅里,你可以看到很多人都在编写 Python代码,在未来三到四年内,这种情况将变得更加普遍。 野村证券,一家日本大券商,也是最早拓展中国金融和投资业务的境外机构之一。1925 年成立的野村证券现为日本第一大券商,目前在全球 28 个国家和地区有办事机构。野村证券有一支新的、不断发展的电子交易团队,成立于 2019年 5月。该团队的任务是通过将人工智能集成到银行系统的证券市场平台,将野村证券的固定收益交易收入提高 15%。 Hampson表示,Python是一门用处非常广的编程语言,同样适用于金融分析和科学计算,让银行的创新速度更快。金融服务业里的快速创新概念非常强烈,此前是通过Excel 电子表格来驱动,但现在有了一种新的工具:Python。 Wall Streetoasis(...
- 下一篇
"双十一"将至,Check Point强势助力企业迎接安全大考
【51CTO.com原创稿件】一年一度的"双十一"大促活动马上来临,与此同时电商、新零售企业将迎来安全大考。面对严峻的安全威胁,在这一特殊时期,电商和新零售企业该如何做好安全防护,以保证活动的正常进行,给用户更好的购物体验? 近日,51CTO记者走访了Check Point技术总监王跃霖先生。他表示:"在"双十一"这样的特殊时期,电商、新零售企业如果仍将安全寄托于云服务商或运营商一方,企业自身没有针对业务的高级防护,一旦发生安全事故,将会产生严重后果。" 移动端及云上应用安全风险加剧 王跃霖先生首先通过分享近期CheckPoint发布的安全报告,对当前的安全威胁形势进行了分析,该报告显示,无论是从全球还是中国范围来看,网络安全威胁正在发生两大变化:一是,针对移动端的安全威胁日益增多。二是,云上应用的安全风险也在加剧。 这十分契合中国的实际情况。一方面,因为中国的手机用户量比较大,用户经常在手机端进行购物等操作。相对于全球市场来说,中国移动端安全威胁更为突出。另一方面,随着企业数字化转型进程的推进,越来越多的企业将业务上云。针对云应用程序和基础设施的第五代网络威胁,需要得到足够重视。 "...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS7设置SWAP分区,小内存服务器的救世主
- Docker快速安装Oracle11G,搭建oracle11g学习环境