（反轉(zhuǎn)樓梯最后期限調(diào)度算法）The Rotating Staircase Deadline Scheduler 簡(jiǎn)稱RSDL
CPU調(diào)度似乎是那些永遠(yuǎn)未完成的工作之一。開(kāi)發(fā)人員可以在CPU調(diào)度器上工作一段時(shí)間踱阿，并使其工作得更好，但總有一些工作負(fù)載不能像用戶希望的那樣得到很好的服務(wù)歼冰。交互系統(tǒng)的用戶尤其傾向于對(duì)調(diào)度器延遲敏感吞彤。作為回應(yīng)蔬咬，當(dāng)前的調(diào)度器已經(jīng)發(fā)展出一組精心設(shè)計(jì)的啟發(fā)式算法粤咪，它們?cè)噲D檢測(cè)哪些進(jìn)程是真正交互的谚中，并在CPU中給予它們優(yōu)先級(jí)。結(jié)果是復(fù)雜的代碼——人們?nèi)匀槐г菇换ナ巾憫?yīng)寥枝。
Con Kolivas一直致力于改善交互性藏杖。他最新的提議是旋轉(zhuǎn)樓梯截止時(shí)間調(diào)度程序(RSDL)，它試圖通過(guò)相對(duì)簡(jiǎn)單的設(shè)計(jì)脉顿、完全的公平性和有限的延遲來(lái)提供良好的交互式響應(yīng)。這項(xiàng)工作借鑒了Con早期的樓梯調(diào)度程序(2004年6月)点寥，但采用了一種明顯不同的方法艾疟。
與許多調(diào)度器一樣，RSDL維護(hù)一個(gè)優(yōu)先級(jí)數(shù)組敢辩，如圖所示蔽莱。在每個(gè)級(jí)別上都有一個(gè)當(dāng)前希望以該優(yōu)先級(jí)運(yùn)行的進(jìn)程列表;每個(gè)進(jìn)程都有一個(gè)時(shí)間配額，允許它以該優(yōu)先級(jí)執(zhí)行戚长。為具有最高優(yōu)先級(jí)的進(jìn)程分配時(shí)間片盗冷，調(diào)度器使用典型的輪循算法在它們之間進(jìn)行輪換。當(dāng)一個(gè)進(jìn)程在給定的優(yōu)先級(jí)級(jí)別上使用它的配額時(shí)同廉，它將下降到下一個(gè)優(yōu)先級(jí)并被賦予一個(gè)新的配額仪糖。因此柑司，該進(jìn)程可以繼續(xù)運(yùn)行，但必須在高優(yōu)先級(jí)進(jìn)程依次運(yùn)行之后锅劝。當(dāng)進(jìn)程沿著階梯向下移動(dòng)時(shí)攒驰，它們必須越來(lái)越多地與那些在較低層次上耐心等待的較低優(yōu)先級(jí)的進(jìn)程進(jìn)行競(jìng)爭(zhēng)。最終的結(jié)果是故爵，即使是優(yōu)先級(jí)最低的進(jìn)程最終也至少會(huì)占用一點(diǎn)CPU時(shí)間玻粪。
這個(gè)調(diào)度器的一個(gè)有趣特性是，每個(gè)優(yōu)先級(jí)級(jí)別都有自己的配額诬垂。一旦最高優(yōu)先級(jí)使用了它的配額劲室，在該級(jí)別上運(yùn)行的所有進(jìn)程都會(huì)被推到下一個(gè)更低的級(jí)別，而不管它們是否消耗了各自的CPU時(shí)間配額结窘。由于這種“小輪詢”機(jī)制很洋，在較低優(yōu)先級(jí)級(jí)別上等待的進(jìn)程只需要在有限的時(shí)間內(nèi)等待，然后所有其他進(jìn)程就會(huì)在其級(jí)別上運(yùn)行晦鞋。因此蹲缠，等待運(yùn)行的任何進(jìn)程的最大延遲是有界的，并且可以計(jì)算;這個(gè)調(diào)度器不會(huì)出現(xiàn)饑餓悠垛。
當(dāng)進(jìn)程用完它們的時(shí)間時(shí)线定，它們被移動(dòng)到第二個(gè)數(shù)組，稱為“過(guò)期”數(shù)組确买，在那里它們被放回到原來(lái)的優(yōu)先級(jí)斤讥。過(guò)期數(shù)組中的進(jìn)程不會(huì)運(yùn)行;它們將被冷落，直到?jīng)]有更多的進(jìn)程留在當(dāng)前活動(dòng)數(shù)組中湾趾，或者直到所有進(jìn)程由于輕微的旋轉(zhuǎn)而被推離活動(dòng)數(shù)組的底部芭商。在這一點(diǎn)上，一個(gè)“大輪換”發(fā)生了:活動(dòng)和過(guò)期的數(shù)組被交換搀缠，整個(gè)事件系列從頭開(kāi)始重新開(kāi)始铛楣。
當(dāng)前調(diào)度器試圖通過(guò)跟蹤每個(gè)進(jìn)程的睡眠頻率來(lái)定位交互任務(wù);那些被認(rèn)為具有互動(dòng)性的人會(huì)得到優(yōu)先級(jí)提升的獎(jiǎng)勵(lì)。RSDL消除了這一切艺普。相反簸州，處于睡眠狀態(tài)的進(jìn)程不會(huì)把所有的時(shí)間都用在更高的優(yōu)先級(jí)上。當(dāng)它們運(yùn)行時(shí)歧譬，它們自然比那些需要大量cpu的競(jìng)爭(zhēng)對(duì)手更有優(yōu)勢(shì)岸浑。如果一個(gè)進(jìn)程在大周期中處于休眠狀態(tài)，那么它的配額將返回到運(yùn)行隊(duì)列特定于優(yōu)先級(jí)的配額值中瑰步。因此矢洲，即使在此期間運(yùn)行的其他高優(yōu)先級(jí)進(jìn)程通過(guò)輕微的輪換被推到較低的優(yōu)先級(jí)，它也能夠以高優(yōu)先級(jí)運(yùn)行缩焦。所有這一切都應(yīng)該使交互式應(yīng)用程序能夠快速響應(yīng)读虏。
