這篇文章主要想介紹下彩票調度（個人覺得這個演算法非常有意思~ ），還有隨機演算法相對傳統演算法的一點優勢，畢竟現在絕大多數演算法都是追求確定性，尤其在作業系統，大家都希望一切可控，所以隨機演算法的出現聽起來有些“不合時宜”，但它確實能夠解決某些傳統演算法難以解決的邊角問題（算是給自己挖個坑，以后可能會寫），也為我們提供了一種新的思路，
以下是正文：
行程調度器今天突然召集大伙，說是要討論一件重要的事情，問他他還賣關子：“你去了就知道，我現在不告訴你們，”
還沒到約定時間，大伙兒就已經來到了記憶體家，只見行程調度器氣定神閑的坐在椅子上，翹著個二郎腿，好不自在，
“調度器老哥，現在人也都來的差不多了，咱們現在就開始吧，早點結束大家伙兒好接著回去干活啊，”
調度器“嗯”了一聲，起身走向白板，說：“我向大家先說明一下背景吧，咱們原來的調度演算法，比如先來先服務，短行程優先，優先級調度等等，大都是為了優化周轉時間和回應時間，效果也還不錯，不過這些演算法，有些可能會導致饑餓的問題，我想不少行程深有體會，”
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 虛擬機，這時候靠彩票調度就很方便了，
所以彩票調度機制還是有一定應用價值的，說不定你以后在哪里就用上了呢？
希望你在看完我的文章之后有所識訓，期待你的贊和轉發！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/65017.html
標籤：C
上一篇：資料結構入門