這篇文章主要想介紹下彩票調(diào)度（個人覺得這個算法非常有意思~ ），還有隨機算法相對傳統(tǒng)算法的一點優(yōu)勢，畢竟現(xiàn)在絕大多數(shù)算法都是追求確定性，尤其在操作系統(tǒng)，大家都希望一切可控，所以隨機算法的出現(xiàn)聽起來有些“不合時宜”，但它確實能夠解決某些傳統(tǒng)算法難以解決的邊角問題（算是給自己挖個坑，以后可能會寫），也為我們提供了一種新的思路。

以下是正文：

---

進程調(diào)度器今天突然召集大伙，說是要討論一件重要的事情，問他他還賣關(guān)子：“你去了就知道，我現(xiàn)在不告訴你們。”

還沒到約定時間，大伙兒就已經(jīng)來到了內(nèi)存家，只見進程調(diào)度器氣定神閑的坐在椅子上，翹著個二郎腿，好不自在。

“調(diào)度器老哥，現(xiàn)在人也都來的差不多了，咱們現(xiàn)在就開始吧，早點結(jié)束大家伙兒好接著回去干活啊。”

調(diào)度器“嗯”了一聲，起身走向白板，說：“我向大家先說明一下背景吧，咱們原來的調(diào)度算法，比如先來先服務(wù)，短進程優(yōu)先，優(yōu)先級調(diào)度等等，大都是為了優(yōu)化周轉(zhuǎn)時間和響應(yīng)時間，效果也還不錯。不過這些算法，有些可能會導(dǎo)致饑餓的問題，我想不少進程深有體會。”

tobe 注：關(guān)于這幾種調(diào)度算法，可以看這篇文章——

tobe的囈語：我是一個進程調(diào)度器?zhuanlan.zhihu.com

饑餓問題確實困擾操作系統(tǒng)很長時間了，雖然饑餓不如死鎖那么有破壞力，但還是影響到了進程家庭內(nèi)部的和諧。聽調(diào)度器的意思，他是能解決這個問題？

幾個低優(yōu)先級進程開始小聲議論起來，像他們這種優(yōu)先級別低的，總會因為高優(yōu)先級進程“插隊”而得不到 CPU 資源，心里早就憋著一口氣呢。忍不住問調(diào)度器：“現(xiàn)在是有什么好辦法了嗎？我們可受夠饑餓的生活了！”

調(diào)度器得意的說：“那當(dāng)然，不然我今天把你們大伙叫過來干什么？我最近想到一個好點子，咱們可以調(diào)整一下調(diào)度目標(biāo)，改成確保每個任務(wù)獲得一定比例的 CPU 時間，這樣只要我們提前約定好份額，每個人最后都可以享受到應(yīng)有的待遇，不可能出現(xiàn)某一進程獨占的現(xiàn)象！聽起來是不是很公平？我打算把這類算法叫「比例份額調(diào)度」或者「公平份額調(diào)度」。”

系統(tǒng)進程提出了質(zhì)疑：“公平？你別說大話了，這個目標(biāo)咱們又不是沒有追求過，也就時間片輪轉(zhuǎn)算法勉強達(dá)到了我們的要求，可一旦再劃分出優(yōu)先級（指的是多級優(yōu)先隊列調(diào)度），就可能會造成進程饑餓，追求公平可不是那么簡單的！”

“你先聽我說嘛，絕對的公平確實很難達(dá)到，我們現(xiàn)在退而求其次，追求一個相對公平——就是說短時間里可能會有些許不公平，但從長期來看，大家在 CPU 上運行的時間所占比例就是一開始約定好的。”

“聽起來很有道理，但是你打算怎么實現(xiàn)？”

“嘿嘿，我給這個方法取名叫「彩票調(diào)度」，咱們一開始的時候給每個進程發(fā)彩票——優(yōu)先級越高，發(fā)的彩票越多，然后每隔一段時間（一個時間片），舉行一次彩票抽獎，抽出來的號是誰的，誰就能運行~”

“哈哈哈哈，我還以為是什么厲害的算法呢”，一時間，大家都笑了出來，整個內(nèi)存里充滿了快活的氣息。調(diào)度器的臉唰的一下就紅了。

操作系統(tǒng)吐槽道：“調(diào)度器，你是不是跟那幫人類學(xué)壞了？在我們這兒還搞什么彩票，下一步是不是打算騙大家的時間片？再這么搞下去，小心我把你職位撤了啊！”

調(diào)度器趕緊為自己解釋：”誒，我可是經(jīng)過深思熟慮才想出來的，你們別誤會啊！打個比方吧，假如有兩個進程 A 和 B，我想讓 A 占用 80% 的 CPU 時間，B 占用 20% 的 CPU 時間，我就給 A 發(fā)80 張彩票，給 B 發(fā) 20 張彩票。這樣，每次抽獎的時候，A 就有 80% 的概率占用 CPU，從數(shù)學(xué)期望上講，1 秒鐘之內(nèi)，A 能運行 800ms。我是打算利用隨機性來達(dá)到按比例分配的目標(biāo)的，可從沒打算騙大家。“

操作系統(tǒng)看起來有點認(rèn)可這個算法了，他點點頭：“有點意思，你接著說下去。”

調(diào)度器松了一口氣，繼續(xù)說：“我覺得這種算法有個很好的地方——即使某進程只有一張彩票，經(jīng)過多輪迭代，他總會獲得 CPU 的使用權(quán)。所以饑餓的問題就能解決了~”

PS：可別跟現(xiàn)實的彩票等價啊，現(xiàn)實彩票中獎率低的嚇人。。。沒法比的（不信你自己算一算）。

那幾個經(jīng)常饑餓的進程聽了，兩眼放光，仿佛抓到了希望。

"別急，還沒完呢！你們想想，咱們用過的「最短響應(yīng)比優(yōu)先」算法，還得記錄每個進程在就緒隊列等待了多長時間，多麻煩！我這個「彩票調(diào)度」，不需要記錄任何狀態(tài)，拿來就用，特別的輕量，而且這種隨機方法很快，只要生成一個隨機數(shù)，就能快速做出決策。為了向你們展示，我還特意寫了段偽代碼。"

//當(dāng)進入時鐘中斷時運行//counter 用來數(shù)哪個進程拿到了 winner 彩票 int counter = 0;//選出勝者，其中 totalticks 是彩票總數(shù) int winner = randint(0, totaltickets);//指針，指向隊列里的進程 job_t *current_job = head;while(current_job != null) {counter = counter + current_job->ticket;if (counter > winner)//說明當(dāng)前進程拿到了 winner 彩票break;current_job = current_job->next; }//切換至 current 指向的進程

操作系統(tǒng)看完了代碼，贊嘆道：“好家伙，確實是個簡潔的調(diào)度算法，簡潔的都有點兒不可思議了。不過你這個代碼只解決了調(diào)度問題，最開始的彩票分配問題你打算怎么解決？”

調(diào)度器面露難色：“我這幾天也在想這個問題，不過暫時沒有想到好的解決方案，所以說要靠試運行來摸索嘛，如果找到好的分配方法，就可以長期運行下去了。”

“確實，我也覺得這個方法有的一試，咱們明天就按這個調(diào)度算法來，看看效果能不能比上現(xiàn)有的算法！”

調(diào)度器高興地叫出來：“好，太好了，我馬上就去準(zhǔn)備！”

---

實際上彩票調(diào)度并沒有在 CPU 調(diào)度程序里廣泛使用，一個原因是不能很好的適合 I/O（有論文研究過這個問題），另一個原因就是文中所提到的，票數(shù)分配問題沒有確定的解決方式，比如你新打開了一個瀏覽器進程，那該給他分配多少票？票數(shù)少了，響應(yīng)跟不上，票數(shù)多了，又會浪費 CPU 時間。

與此相比，常見的通用調(diào)度程序，比如多級優(yōu)先隊列，就做的很好，因此現(xiàn)在得到了廣泛的應(yīng)用。

但不代表這種思想就沒有用了，在某些容易確定份額比例的領(lǐng)域里，比例份額調(diào)度程序就更有用——比如在虛擬數(shù)據(jù)中心，你可能希望 1/4 的 CPU 時間給 Windows 虛擬機，剩下的時間給 Linux 虛擬機，這時候靠彩票調(diào)度就很方便了。

所以彩票調(diào)度機制還是有一定應(yīng)用價值的，說不定你以后在哪里就用上了呢？

希望你在看完我的文章之后有所收獲，期待你的贊和評論！

總結(jié)

以上是生活随笔為你收集整理的使用轮转算法求时间片_彩票调度算法，让进程们拼手气？ --当操作系统遇上随机算法...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。