進(jìn)程和線程在調(diào)度時(shí)候出現(xiàn)過(guò)很多算法，這些算法的設(shè)計(jì)背景是當(dāng)一個(gè)計(jì)算機(jī)是多道程序設(shè)計(jì)系統(tǒng)時(shí)，會(huì)頻繁的有很多進(jìn)程或者線程來(lái)同時(shí)競(jìng)爭(zhēng) CPU 時(shí)間片。那么如何選擇合適的進(jìn)程/線程運(yùn)行是一項(xiàng)藝術(shù)。當(dāng)兩個(gè)或兩個(gè)以上的進(jìn)程/線程處于就緒狀態(tài)時(shí)，就會(huì)發(fā)生這種情況。如果只有一個(gè) CPU 可用，那么必須選擇接下來(lái)哪個(gè)進(jìn)程/線程可以運(yùn)行。操作系統(tǒng)中有一個(gè)叫做?調(diào)度程序(scheduler)?的角色存在，它就是做這件事兒的，調(diào)度程序使用的算法叫做?調(diào)度算法(scheduling algorithm)?。
CPU 利用率(CPU utilization)??通常作為批處理系統(tǒng)上的指標(biāo)。即使如此，CPU 利用率也不是一個(gè)好的度量指標(biāo)，真正有價(jià)值的衡量指標(biāo)是系統(tǒng)每小時(shí)可以完成多少作業(yè)（吞吐量），以及完成作業(yè)需要多長(zhǎng)時(shí)間（周轉(zhuǎn)時(shí)間）。
現(xiàn)在考慮使用最短作業(yè)優(yōu)先算法運(yùn)行 4 個(gè)作業(yè)，如上圖 b 所示，目前的周轉(zhuǎn)時(shí)間分別為 4、8、12、20，平均為 11 分鐘，可以證明最短作業(yè)優(yōu)先是最優(yōu)的。考慮有 4 個(gè)作業(yè)的情況，其運(yùn)行時(shí)間分別為 a、b、c、d。第一個(gè)作業(yè)在時(shí)間 a 結(jié)束，第二個(gè)在時(shí)間 a + b 結(jié)束，以此類推。平均周轉(zhuǎn)時(shí)間為 (4a + 3b + 2c + d) / 4 。顯然 a 對(duì)平均值的影響最大，所以 a 應(yīng)該是最短優(yōu)先作業(yè)，其次是 b，然后是 c ，最后是 d 它就只能影響自己的周轉(zhuǎn)時(shí)間了。
最短作業(yè)優(yōu)先的搶占式版本被稱作為?最短剩余時(shí)間優(yōu)先(Shortest Remaining Time Next)?算法。使用這個(gè)算法，調(diào)度程序總是選擇剩余運(yùn)行時(shí)間最短的那個(gè)進(jìn)程運(yùn)行。當(dāng)一個(gè)新作業(yè)到達(dá)時(shí)，其整個(gè)時(shí)間同當(dāng)前進(jìn)程的剩余時(shí)間做比較。如果新的進(jìn)程比當(dāng)前運(yùn)行進(jìn)程需要更少的時(shí)間，當(dāng)前進(jìn)程就被掛起，而運(yùn)行新的進(jìn)程。這種方式能夠使短期作業(yè)獲得良好的服務(wù)。
一種最古老、最簡(jiǎn)單、最公平并且最廣泛使用的算法就是?輪詢算法(round-robin)。每個(gè)進(jìn)程都會(huì)被分配一個(gè)時(shí)間段，稱為時(shí)間片(quantum)，在這個(gè)時(shí)間片內(nèi)允許進(jìn)程運(yùn)行。如果進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換。輪詢算法比較容易實(shí)現(xiàn)。調(diào)度程序所做的就是維護(hù)一個(gè)可運(yùn)行進(jìn)程的列表，就像下圖中的 a，當(dāng)一個(gè)進(jìn)程用完時(shí)間片后就被移到隊(duì)列的末尾，就像下圖的 b。
一種方式是根據(jù)進(jìn)程過(guò)去的行為進(jìn)行推測(cè)，并執(zhí)行估計(jì)運(yùn)行時(shí)間最短的那一個(gè)。假設(shè)每個(gè)終端上每條命令的預(yù)估運(yùn)行時(shí)間為?T0，現(xiàn)在假設(shè)測(cè)量到其下一次運(yùn)行時(shí)間為?T1，可以用兩個(gè)值的加權(quán)來(lái)改進(jìn)估計(jì)時(shí)間，即aT0+ (1- 1)T1。通過(guò)選擇 a 的值，可以決定是盡快忘掉老的運(yùn)行時(shí)間，還是在一段長(zhǎng)時(shí)間內(nèi)始終記住它們。當(dāng) a = 1/2 時(shí)，可以得到下面這個(gè)序列
一種完全不同的調(diào)度方法是對(duì)用戶做出明確的性能保證。一種實(shí)際而且容易實(shí)現(xiàn)的保證是：若用戶工作時(shí)有 n 個(gè)用戶登錄，則每個(gè)用戶將獲得 CPU 處理能力的 1/n。類似地，在一個(gè)有 n 個(gè)進(jìn)程運(yùn)行的單用戶系統(tǒng)中，若所有的進(jìn)程都等價(jià)，則每個(gè)進(jìn)程將獲得 1/n 的 CPU 時(shí)間。
其基本思想是為進(jìn)程提供各種系統(tǒng)資源（例如 CPU 時(shí)間）的彩票。當(dāng)做出一個(gè)調(diào)度決策的時(shí)候，就隨機(jī)抽出一張彩票，擁有彩票的進(jìn)程將獲得該資源。在應(yīng)用到 CPU 調(diào)度時(shí)，系統(tǒng)可以每秒持有 50 次抽獎(jiǎng)，每個(gè)中獎(jiǎng)?wù)邔@得比如 20 毫秒的 CPU 時(shí)間作為獎(jiǎng)勵(lì)。
為了阻止這種情況的出現(xiàn)，一些系統(tǒng)在調(diào)度前會(huì)把進(jìn)程的擁有者考慮在內(nèi)。在這種模型下，每個(gè)用戶都會(huì)分配一些CPU 時(shí)間，而調(diào)度程序會(huì)選擇進(jìn)程并強(qiáng)制執(zhí)行。因此如果兩個(gè)用戶每個(gè)都會(huì)有 50% 的 CPU 時(shí)間片保證，那么無(wú)論一個(gè)用戶有多少個(gè)進(jìn)程，都將獲得相同的 CPU 份額。
實(shí)時(shí)系統(tǒng)中的調(diào)度
實(shí)時(shí)系統(tǒng)(real-time)?對(duì)于時(shí)間有要求的系統(tǒng)。實(shí)時(shí)系統(tǒng)可以分為兩類，硬實(shí)時(shí)(hard real time)?和?軟實(shí)時(shí)(soft real time)?系統(tǒng)，前者意味著必須要滿足絕對(duì)的截止時(shí)間；后者的含義是雖然不希望偶爾錯(cuò)失截止時(shí)間，但是可以容忍。在這兩種情形中，實(shí)時(shí)都是通過(guò)把程序劃分為一組進(jìn)程而實(shí)現(xiàn)的，其中每個(gè)進(jìn)程的行為是可預(yù)測(cè)和提前可知的。這些進(jìn)程一般壽命較短，并且極快的運(yùn)行完成。在檢測(cè)到一個(gè)外部信號(hào)時(shí)，調(diào)度程序的任務(wù)就是按照滿足所有截止時(shí)間的要求調(diào)度進(jìn)程。
實(shí)時(shí)系統(tǒng)中的事件可以按照響應(yīng)方式進(jìn)一步分類為周期性(以規(guī)則的時(shí)間間隔發(fā)生)事件或?非周期性(發(fā)生時(shí)間不可預(yù)知)事件。一個(gè)系統(tǒng)可能要響應(yīng)多個(gè)周期性事件流，根據(jù)每個(gè)事件處理所需的時(shí)間，可能甚至無(wú)法處理所有事件。例如，如果有 m 個(gè)周期事件，事件 i 以周期 Pi 發(fā)生，并需要 Ci 秒 CPU 時(shí)間處理一個(gè)事件，那么可以處理負(fù)載的條件是
只有滿足這個(gè)條件的實(shí)時(shí)系統(tǒng)稱為可調(diào)度的，這意味著它實(shí)際上能夠被實(shí)現(xiàn)。一個(gè)不滿足此檢驗(yàn)標(biāo)準(zhǔn)的進(jìn)程不能被調(diào)度，因?yàn)檫@些進(jìn)程共同需要的 CPU 時(shí)間總和大于 CPU 能提供的時(shí)間。
到目前為止，我們隱含的假設(shè)系統(tǒng)中所有進(jìn)程屬于不同的分組用戶并且進(jìn)程間存在相互競(jìng)爭(zhēng) CPU 的情況。通常情況下確實(shí)如此，但有時(shí)也會(huì)發(fā)生一個(gè)進(jìn)程會(huì)有很多子進(jìn)程并在其控制下運(yùn)行的情況。例如，一個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)進(jìn)程會(huì)有很多子進(jìn)程。每一個(gè)子進(jìn)程可能處理不同的請(qǐng)求，或者每個(gè)子進(jìn)程實(shí)現(xiàn)不同的功能（如請(qǐng)求分析、磁盤訪問(wèn)等）。主進(jìn)程完全可能掌握哪一個(gè)子進(jìn)程最重要（或最緊迫），而哪一個(gè)最不重要。但是，以上討論的調(diào)度算法中沒(méi)有一個(gè)算法從用戶進(jìn)程接收有關(guān)的調(diào)度決策信息，這就導(dǎo)致了調(diào)度程序很少能夠做出最優(yōu)的選擇。
如果硬件沒(méi)有這些位，那么可以使用操作系統(tǒng)的缺頁(yè)中斷和時(shí)鐘中斷機(jī)制來(lái)進(jìn)行模擬。當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)，將其所有的頁(yè)面都標(biāo)記為不在內(nèi)存；一旦訪問(wèn)任何一個(gè)頁(yè)面就會(huì)引發(fā)一次缺頁(yè)中斷，此時(shí)操作系統(tǒng)就可以設(shè)置?R 位(在它的內(nèi)部表中)，修改頁(yè)表項(xiàng)使其指向正確的頁(yè)面，并設(shè)置為?READ ONLY?模式，然后重新啟動(dòng)引起缺頁(yè)中斷的指令。如果頁(yè)面隨后被修改，就會(huì)發(fā)生另一個(gè)缺頁(yè)異常。從而允許操作系統(tǒng)設(shè)置 M 位并把頁(yè)面的模式設(shè)置為?READ/WRITE。
可以用 R 位和 M 位來(lái)構(gòu)造一個(gè)簡(jiǎn)單的頁(yè)面置換算法：當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)，操作系統(tǒng)將其所有頁(yè)面的兩個(gè)位都設(shè)置為 0。R 位定期的被清零（在每個(gè)時(shí)鐘中斷）。用來(lái)將最近未引用的頁(yè)面和已引用的頁(yè)面分開(kāi)。
當(dāng)出現(xiàn)缺頁(yè)中斷后，操作系統(tǒng)會(huì)檢查所有的頁(yè)面，并根據(jù)它們的 R 位和 M 位將當(dāng)前值分為四類：
第 0 類：沒(méi)有引用 R，沒(méi)有修改 M
第 1 類：沒(méi)有引用 R，已修改 M
第 2 類：引用 R ，沒(méi)有修改 M
第 3 類：已被訪問(wèn) R，已被修改 M
盡管看起來(lái)好像無(wú)法實(shí)現(xiàn)第一類頁(yè)面，但是當(dāng)?shù)谌愴?yè)面的 R 位被時(shí)鐘中斷清除時(shí)，它們就會(huì)發(fā)生。時(shí)鐘中斷不會(huì)清除 M 位，因?yàn)樾枰@個(gè)信息才能知道是否寫回磁盤中。清除 R 但不清除 M 會(huì)導(dǎo)致出現(xiàn)一類頁(yè)面。
我們上面學(xué)到的 FIFO 鏈表頁(yè)面有個(gè)缺陷，那就是出鏈和入鏈并不會(huì)進(jìn)行 check?檢查，這樣就會(huì)容易把經(jīng)常使用的頁(yè)面置換出去，為了避免這一問(wèn)題，我們對(duì)該算法做一個(gè)簡(jiǎn)單的修改：我們檢查最老頁(yè)面的?R 位，如果是 0 ，那么這個(gè)頁(yè)面就是最老的而且沒(méi)有被使用，那么這個(gè)頁(yè)面就會(huì)被立刻換出。如果 R 位是 1，那么就清除此位，此頁(yè)面會(huì)被放在鏈表的尾部，修改它的裝入時(shí)間就像剛放進(jìn)來(lái)的一樣。然后繼續(xù)搜索。
這種算法叫做?第二次機(jī)會(huì)(second chance)算法，就像下面這樣，我們看到頁(yè)面 A 到 H 保留在鏈表中，并按到達(dá)內(nèi)存的時(shí)間排序。
a）按照先進(jìn)先出的方法排列的頁(yè)面；b）在時(shí)刻 20 處發(fā)生缺頁(yè)異常中斷并且 A 的 R 位已經(jīng)設(shè)置時(shí)的頁(yè)面鏈表。
假設(shè)缺頁(yè)異常發(fā)生在時(shí)刻 20 處，這時(shí)最老的頁(yè)面是 A ，它是在 0 時(shí)刻到達(dá)的。如果 A 的 R 位是 0，那么它將被淘汰出內(nèi)存，或者把它寫回磁盤（如果它已經(jīng)被修改過(guò)），或者只是簡(jiǎn)單的放棄（如果它是未被修改過(guò)）。另一方面，如果它的 R 位已經(jīng)設(shè)置了，則將 A 放到鏈表的尾部并且重新設(shè)置裝入時(shí)間為當(dāng)前時(shí)刻（20 處），然后清除 R 位。然后從 B 頁(yè)面開(kāi)始繼續(xù)搜索合適的頁(yè)面。
尋找第二次機(jī)會(huì)的是在最近的時(shí)鐘間隔中未被訪問(wèn)過(guò)的頁(yè)面。如果所有的頁(yè)面都被訪問(wèn)過(guò)，該算法就會(huì)被簡(jiǎn)化為單純的?FIFO 算法。具體來(lái)說(shuō)，假設(shè)圖 a 中所有頁(yè)面都設(shè)置了 R 位。操作系統(tǒng)將頁(yè)面依次移到鏈表末尾，每次都在添加到末尾時(shí)清除 R 位。最后，算法又會(huì)回到頁(yè)面 A，此時(shí)的 R 位已經(jīng)被清除，那么頁(yè)面 A 就會(huì)被執(zhí)行出鏈處理，因此算法能夠正常結(jié)束。
當(dāng)缺頁(yè)錯(cuò)誤出現(xiàn)時(shí)，算法首先檢查表針指向的頁(yè)面，如果它的 R 位是 0 就淘汰該頁(yè)面，并把新的頁(yè)面插入到這個(gè)位置，然后把表針向前移動(dòng)一位；如果 R 位是 1 就清除 R 位并把表針前移一個(gè)位置。重復(fù)這個(gè)過(guò)程直到找到了一個(gè) R 位為 0 的頁(yè)面位置。了解這個(gè)算法的工作方式，就明白為什么它被稱為?時(shí)鐘(clokc)算法了。
在最單純的分頁(yè)系統(tǒng)中，剛啟動(dòng)進(jìn)程時(shí)，在內(nèi)存中并沒(méi)有頁(yè)面。此時(shí)如果 CPU 嘗試匹配第一條指令，就會(huì)得到一個(gè)缺頁(yè)異常，使操作系統(tǒng)裝入含有第一條指令的頁(yè)面。其他的錯(cuò)誤比如?全局變量和?堆棧?引起的缺頁(yè)異常通常會(huì)緊接著發(fā)生。一段時(shí)間以后，進(jìn)程需要的大部分頁(yè)面都在內(nèi)存中了，此時(shí)進(jìn)程開(kāi)始在較少的缺頁(yè)異常環(huán)境中運(yùn)行。這個(gè)策略稱為?請(qǐng)求調(diào)頁(yè)(demand paging)，因?yàn)轫?yè)面是根據(jù)需要被調(diào)入的，而不是預(yù)先調(diào)入的。
在一個(gè)大的地址空間中系統(tǒng)的讀所有的頁(yè)面，將會(huì)造成很多缺頁(yè)異常，因此會(huì)導(dǎo)致沒(méi)有足夠的內(nèi)存來(lái)容納這些頁(yè)面。不過(guò)幸運(yùn)的是，大部分進(jìn)程不是這樣工作的，它們都會(huì)以局部性方式(locality of reference)?來(lái)訪問(wèn)，這意味著在執(zhí)行的任何階段，程序只引用其中的一小部分。
一個(gè)進(jìn)程當(dāng)前正在使用的頁(yè)面的集合稱為它的?工作集(working set)，如果整個(gè)工作集都在內(nèi)存中，那么進(jìn)程在運(yùn)行到下一運(yùn)行階段（例如，編譯器的下一遍掃面）之前，不會(huì)產(chǎn)生很多缺頁(yè)中斷。如果內(nèi)存太小從而無(wú)法容納整個(gè)工作集，那么進(jìn)程的運(yùn)行過(guò)程中會(huì)產(chǎn)生大量的缺頁(yè)中斷，會(huì)導(dǎo)致運(yùn)行速度也會(huì)變得緩慢。因?yàn)橥ǔＶ恍枰獛准{秒就能執(zhí)行一條指令，而通常需要十毫秒才能從磁盤上讀入一個(gè)頁(yè)面。如果一個(gè)程序每 10 ms 只能執(zhí)行一到兩條指令，那么它將需要很長(zhǎng)時(shí)間才能運(yùn)行完。如果只是執(zhí)行幾條指令就會(huì)產(chǎn)生中斷，那么就稱作這個(gè)程序產(chǎn)生了?顛簸(thrashing)。
在多道程序的系統(tǒng)中，通常會(huì)把進(jìn)程移到磁盤上（即從內(nèi)存中移走所有的頁(yè)面），這樣可以讓其他進(jìn)程有機(jī)會(huì)占用 CPU 。有一個(gè)問(wèn)題是，當(dāng)進(jìn)程想要再次把之前調(diào)回磁盤的頁(yè)面調(diào)回內(nèi)存怎么辦？從技術(shù)的角度上來(lái)講，并不需要做什么，此進(jìn)程會(huì)一直產(chǎn)生缺頁(yè)中斷直到它的工作集?被調(diào)回內(nèi)存。然后，每次裝入一個(gè)進(jìn)程需要 20、100 甚至 1000 次缺頁(yè)中斷，速度顯然太慢了，并且由于 CPU 需要幾毫秒時(shí)間處理一個(gè)缺頁(yè)中斷，因此由相當(dāng)多的 CPU 時(shí)間也被浪費(fèi)了。
因此，不少分頁(yè)系統(tǒng)中都會(huì)設(shè)法跟蹤進(jìn)程的工作集，確保這些工作集在進(jìn)程運(yùn)行時(shí)被調(diào)入內(nèi)存。這個(gè)方法叫做?工作集模式(working set model)。它被設(shè)計(jì)用來(lái)減少缺頁(yè)中斷的次數(shù)的。在進(jìn)程運(yùn)行前首先裝入工作集頁(yè)面的這一個(gè)過(guò)程被稱為?預(yù)先調(diào)頁(yè)(prepaging)，工作集是隨著時(shí)間來(lái)變化的。
根據(jù)研究表明，大多數(shù)程序并不是均勻的訪問(wèn)地址空間的，而訪問(wèn)往往是集中于一小部分頁(yè)面。一次內(nèi)存訪問(wèn)可能會(huì)取出一條指令，也可能會(huì)取出數(shù)據(jù)，或者是存儲(chǔ)數(shù)據(jù)。在任一時(shí)刻 t，都存在一個(gè)集合，它包含所有最近 k 次內(nèi)存訪問(wèn)所訪問(wèn)過(guò)的頁(yè)面。這個(gè)集合?w(k,t)?就是工作集。因?yàn)樽罱?k = 1次訪問(wèn)肯定會(huì)訪問(wèn)最近 k > 1 次訪問(wèn)所訪問(wèn)過(guò)的頁(yè)面，所以?w(k,t)?是 k 的單調(diào)遞減函數(shù)。隨著 k 的增大，w(k,t)?是不會(huì)無(wú)限變大的，因?yàn)槌绦虿豢赡茉L問(wèn)比所能容納頁(yè)面數(shù)量上限還多的頁(yè)面。
事實(shí)上大多數(shù)應(yīng)用程序只會(huì)任意訪問(wèn)一小部分頁(yè)面集合，但是這個(gè)集合會(huì)隨著時(shí)間而緩慢變化，所以為什么一開(kāi)始曲線會(huì)快速上升而 k 較大時(shí)上升緩慢。為了實(shí)現(xiàn)工作集模型，操作系統(tǒng)必須跟蹤哪些頁(yè)面在工作集中。一個(gè)進(jìn)程從它開(kāi)始執(zhí)行到當(dāng)前所實(shí)際使用的 CPU 時(shí)間總數(shù)通常稱作?當(dāng)前實(shí)際運(yùn)行時(shí)間。進(jìn)程的工作集可以被稱為在過(guò)去的 t 秒實(shí)際運(yùn)行時(shí)間中它所訪問(wèn)過(guò)的頁(yè)面集合。
算法的工作流程如下，假設(shè)硬件要設(shè)置 R 和 M 位。同樣的，在每個(gè)時(shí)鐘周期內(nèi)，一個(gè)周期性的時(shí)鐘中斷會(huì)使軟件清除?Referenced(引用)位。在每個(gè)缺頁(yè)異常，頁(yè)表會(huì)被掃描以找出一個(gè)合適的頁(yè)面把它置換。
隨著每個(gè)頁(yè)表項(xiàng)的處理，都需要檢查 R 位。如果 R 位是 1，那么就會(huì)將當(dāng)前時(shí)間寫入頁(yè)表項(xiàng)的?上次使用時(shí)間域，表示的意思就是缺頁(yè)異常發(fā)生時(shí)頁(yè)面正在被使用。因?yàn)轫?yè)面在當(dāng)前時(shí)鐘周期內(nèi)被訪問(wèn)過(guò)，那么它應(yīng)該出現(xiàn)在工作集中而不是被刪除（假設(shè) t 是橫跨了多個(gè)時(shí)鐘周期）。
如果 R 位是 0 ，那么在當(dāng)前的時(shí)鐘周期內(nèi)這個(gè)頁(yè)面沒(méi)有被訪問(wèn)過(guò)，應(yīng)該作為被刪除的對(duì)象。為了查看是否應(yīng)該將其刪除，會(huì)計(jì)算其使用期限（當(dāng)前虛擬時(shí)間 - 上次使用時(shí)間），來(lái)用這個(gè)時(shí)間和 t 進(jìn)行對(duì)比。如果使用期限大于 t，那么這個(gè)頁(yè)面就不再工作集中，而使用新的頁(yè)面來(lái)替換它。然后繼續(xù)掃描更新剩下的表項(xiàng)。
然而，如果 R 位是 0 但是使用期限小于等于 t，那么此頁(yè)應(yīng)該在工作集中。此時(shí)就會(huì)把頁(yè)面臨時(shí)保存起來(lái)，但是會(huì)記生存時(shí)間最長(zhǎng)（即上次使用時(shí)間的最小值）的頁(yè)面。如果掃描完整個(gè)頁(yè)表卻沒(méi)有找到適合被置換的頁(yè)面，也就意味著所有的頁(yè)面都在工作集中。在這種情況下，如果找到了一個(gè)或者多個(gè) R = 0 的頁(yè)面，就淘汰生存時(shí)間最長(zhǎng)的頁(yè)面。最壞的情況下是，在當(dāng)前時(shí)鐘周期內(nèi)，所有的頁(yè)面都被訪問(wèn)過(guò)了（也就是都有 R = 1），因此就隨機(jī)選擇一個(gè)頁(yè)面淘汰，如果有的話最好選一個(gè)未被訪問(wèn)的頁(yè)面，也就是干凈的頁(yè)面。
工作集時(shí)鐘頁(yè)面置換算法的操作：a) 和 b) 給出 R = 1 時(shí)所發(fā)生的情形；c) 和 d) 給出 R = 0 的例子
最初的時(shí)候，該表是空的。當(dāng)裝入第一個(gè)頁(yè)面后，把它加載到該表中。隨著更多的頁(yè)面的加入，它們形成一個(gè)環(huán)形結(jié)構(gòu)。每個(gè)表項(xiàng)包含來(lái)自基本工作集算法的上次使用時(shí)間，以及 R 位（已標(biāo)明）和 M 位（未標(biāo)明）。
與時(shí)鐘算法一樣，在每個(gè)缺頁(yè)異常時(shí)，首先檢查指針指向的頁(yè)面。如果 R 位被是設(shè)置為 1，該頁(yè)面在當(dāng)前時(shí)鐘周期內(nèi)就被使用過(guò)，那么該頁(yè)面就不適合被淘汰。然后把該頁(yè)面的 R 位置為 0，指針指向下一個(gè)頁(yè)面，并重復(fù)該算法。該事件序列化后的狀態(tài)參見(jiàn)圖 b。
現(xiàn)在考慮指針指向的頁(yè)面 R = 0 時(shí)會(huì)發(fā)生什么，參見(jiàn)圖 c，如果頁(yè)面的使用期限大于 t 并且頁(yè)面為被訪問(wèn)過(guò)，那么這個(gè)頁(yè)面就不會(huì)在工作集中，并且在磁盤上會(huì)有一個(gè)此頁(yè)面的副本。申請(qǐng)重新調(diào)入一個(gè)新的頁(yè)面，并把新的頁(yè)面放在其中，如圖 d 所示。另一方面，如果頁(yè)面被修改過(guò)，就不能重新申請(qǐng)頁(yè)面，因?yàn)檫@個(gè)頁(yè)面在磁盤上沒(méi)有有效的副本。為了避免由于調(diào)度寫磁盤操作引起的進(jìn)程切換，指針繼續(xù)向前走，算法繼續(xù)對(duì)下一個(gè)頁(yè)面進(jìn)行操作。畢竟，有可能存在一個(gè)老的，沒(méi)有被修改過(guò)的頁(yè)面可以立即使用。
原則上來(lái)說(shuō)，所有的頁(yè)面都有可能因?yàn)?/span>磁盤I/O?在某個(gè)時(shí)鐘周期內(nèi)被調(diào)度。為了降低磁盤阻塞，需要設(shè)置一個(gè)限制，即最大只允許寫回 n 個(gè)頁(yè)面。一旦達(dá)到該限制，就不允許調(diào)度新的寫操作。
現(xiàn)在已經(jīng)知道了哪些目錄和文件必須被轉(zhuǎn)儲(chǔ)了，這就是上圖 b 中標(biāo)記的內(nèi)容，第三階段算法將以節(jié)點(diǎn)號(hào)為序，掃描這些 inode 并轉(zhuǎn)儲(chǔ)所有標(biāo)記為需轉(zhuǎn)儲(chǔ)的目錄，如下圖所示
電梯算法需要維護(hù)一個(gè)二進(jìn)制位，也就是當(dāng)前的方向位：UP(向上)或者是?DOWN(向下)。當(dāng)一個(gè)請(qǐng)求處理完成后，磁盤或電梯的驅(qū)動(dòng)程序會(huì)檢查該位，如果此位是 UP 位，磁盤臂或者電梯倉(cāng)移到下一個(gè)更高跌未完成的請(qǐng)求。如果高位沒(méi)有未完成的請(qǐng)求，則取相反方向。當(dāng)方向位是?DOWN時(shí)，同時(shí)存在一個(gè)低位的請(qǐng)求，磁盤臂會(huì)轉(zhuǎn)向該點(diǎn)。如果不存在的話，那么它只是停止并等待。
每當(dāng)有資源請(qǐng)求時(shí)就去檢測(cè)，這種方式會(huì)占用昂貴的 CPU 時(shí)間。
每隔 k 分鐘檢測(cè)一次，或者當(dāng) CPU 使用率降低到某個(gè)標(biāo)準(zhǔn)下去檢測(cè)?？紤]到 CPU 效率的原因，如果死鎖進(jìn)程達(dá)到一定數(shù)量，就沒(méi)有多少進(jìn)程可以運(yùn)行，所以 CPU 會(huì)經(jīng)?？臻e。
