文档章节

彩票调度算法——让进程们拼手气?

tobe的呓语
 tobe的呓语
发布于 11/04 16:10
字数 2207
阅读 2991
收藏 41

这篇文章主要想介绍下彩票调度(个人觉得这个算法非常有意思~ ),还有随机算法相对传统算法的一点优势,毕竟现在绝大多数算法都是追求确定性,尤其在操作系统,大家都希望一切可控,所以随机算法的出现听起来有些“不合时宜”,但它确实能够解决某些传统算法难以解决的边角问题(算是给自己挖个坑,以后可能会写),也为我们提供了一种新的思路。

以下是正文:


进程调度器今天突然召集大伙,说是要讨论一件重要的事情,问他他还卖关子:“你去了就知道,我现在不告诉你们。”

还没到约定时间,大伙儿就已经来到了内存家,只见进程调度器气定神闲的坐在椅子上,翘着个二郎腿,好不自在。

“调度器老哥,现在人也都来的差不多了,咱们现在就开始吧,早点结束大家伙儿好接着回去干活啊。”

调度器“嗯”了一声,起身走向白板,说:“我向大家先说明一下背景吧,咱们原来的调度算法,比如先来先服务短进程优先优先级调度等等,大都是为了优化周转时间和响应时间,效果也还不错。不过这些算法,有些可能会导致饥饿的问题,我想不少进程深有体会。”

饥饿问题确实困扰操作系统很长时间了,虽然饥饿不如死锁那么有破坏力,但还是影响到了进程家庭内部的和谐。听调度器的意思,他是能解决这个问题?

几个低优先级进程开始小声议论起来,像他们这种优先级别低的,总会因为高优先级进程“插队”而得不到 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的呓语 ,带你深入计算机的世界~ 公众号后台回复关键词【计算机】有惊喜哦~

© 著作权归作者所有

tobe的呓语
粉丝 49
博文 11
码字总数 22359
作品 0
西安
私信 提问
加载中

评论(3)

松仁普
松仁普
加权随机包了个软文
张恒强
张恒强
类似,但不是!
make_money
make_money
有趣!
安卓或IOS平台辅助程序

【项目背景】 微信辅助程序:主要功能体现于,在同一部设备,多开微信号的情况下,微信号A先领取拼手气红包,微信号B通过微信号A领取红包的数据,自动计算拼手气红包最后一个红包的金额数值,...

颓废de微笑
2017/05/10
23
0
活动招募——Python开发趣味应用

活动招募——Python开发趣味应用 Python,一门有趣的语言,有人说它是胶水语言,有人说它是最美的语言 今天,我们列举了4个场景,来使用Python进行相应的简单小应用开发,解决实际的问题 第一...

宋庆离
2017/08/17
5.4K
14
php秒杀、红包、二维码扩展--php秒杀、红包、二维码扩展

php扩展zqf (兼容php7) 全局变量适用于高并发抢购、秒杀,红包生成,数组算法处理等,由于添加了二维码生成功能,安装本扩展之前需要安装libqrencode, 红包生成算法(拼手气红包和普通红包...

qieangel
2015/09/14
3.3K
0
Linux小知识-5:内核结构

Linux内核主要由五个部分组成:进程调度,内存管理,虚拟文件系统,网络接口,进程间通信。 稍微加以理解:CPU资源——内存资源——外存资源——外部资源——通信。 进程调度(SCHED):控制进...

lp_king
2013/09/28
270
0
细说进程五种状态的生老病死——双胞胎兄弟Java线程

java线程的五种状态其实要真正高清,只需要明白计算机操作系统中进程的知识,原理都是相同的。 系统根据PCB结构中的状态值控制进程。 单CPU系统中,任一时刻处于执行状态的进程只有一个。 进...

刘洋intsmaze
2016/04/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊rocketmq的pullThresholdForTopic

序 本文主要研究一下rocketmq的pullThresholdForTopic pullThresholdForTopic rocketmq-client-4.5.2-sources.jar!/org/apache/rocketmq/client/consumer/DefaultMQPushConsumer.java publi......

go4it
19分钟前
6
0
sqlplus / as sysdba 没有权限

想通过如下命令登陆,这种方式是以操作系统权限认证的oracle sys管理员登陆 sqlplus / as sysdba BUT.... 提示我没有权限, 百度下是由于当前用户不在ora_dba用户组中 (我的环境是win10) ...

1只特立独行的猪
32分钟前
6
0
[2019好程序员大数据教程]SparkGraphx从入门到精通(33集视频+源码+笔记)

1、什么是Spark GraphX? Spark GraphX是一个分布式的图处理框架。社交网络中,用户与用户之间会存在错综复杂的联系,如微信、QQ、微博的用户之间的好友、关注等关系,构成了一张巨大的图,单...

好程序员官网
今天
9
0
DDD(十)--仓储

1、引言 DDD中的Repository(仓储):协调领域和数据映射层,利用类似与集合的接口来访问领域对象。——《领域驱动设计-软件核心复杂性应对之道》 仓储是DDD中产生的概念,也就是说,如果应...

MrYuZixian
今天
10
0
Jenkins的多种迁移方法

说明 Jenkins有时需要进行迁移,主目录会发生改变,本文主要讲解如何更改主目录。由于jenkins安装方式的不同,主目录也不一样。 本测试环境:Centos7.6 X64。注意:在更改主目录之前,请一定...

Elson
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部