hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

彩票调理算法——让历程们拼手气?

2019-11-18杂谈搜奇网24°c
A+ A-

这篇文章主要想引见下彩票调理(个人以为这个算法异常有意义~ ),另有随机算法相对传统算法的一点上风,毕竟如今绝大多数算法都是寻求肯定性,尤其在操作体系,人人都愿望统统可控,所以随机算法的涌现听起来有些“不合时宜”,但它确切能够处理某些传统算法难以处理的边角题目(算是给本身挖个坑,今后能够会写),也为我们供应了一种新的思绪。

以下是正文:

历程调理器本日倏忽调集大伙,说是要谈论一件主要的事变,问他他还卖关子:“你去了就晓得,我如今不通知你们。”

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

“调理器老哥,如今人也都来的差不多了,我们如今就最先吧,早点完毕人人伙儿好接着归去干活啊。”

调理器“嗯”了一声,起家走向白板,说:“我向人人先申明一下背景吧,我们本来的调理算法,比如先来先效劳短历程优先优先级调理等等,多数是为了优化周转时刻和相应时刻,结果也还不错。不过这些算法,有些能够会致使饥饿的题目,我想不少历程深有体会。”

tobe 注:关于这几种调理算法,能够看这篇文章——https://www.cnblogs.com/tobe98/p/11604483.html

饥饿题目确切搅扰操作体系很长时刻了,虽然饥饿不如死锁那末有破坏力,但照样影响到了历程家庭内部的调和。听调理器的意义,他是能处理这个题目?

几个低优先级历程最先小声谈论起来,像他们这类优先级别低的,总会由于高优先级历程“插队”而得不到 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 假造机,这时刻靠彩票调理就很方便了。

所以彩票调理机制照样有肯定运用代价的,说不定你今后在那里就用上了呢?

愿望你在看完我的文章以后有所收成,期待你的赞和转发!

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
彩票调理算法——让历程们拼手气?

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/282258.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>