頁(yè)面置換算法

過(guò)程運(yùn)轉(zhuǎn)時(shí)，若其拜訪的頁(yè)面不在內(nèi)存而需將其調(diào)入，但內(nèi)存已無(wú)閑暇空間時(shí)，就需求從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送入磁盤(pán)的對(duì)調(diào)區(qū)。
選擇調(diào)出頁(yè)面的算法就稱為頁(yè)面置換算法。好的頁(yè)面置換算法應(yīng)有較低的頁(yè)面改換頻率，也就是說(shuō)，應(yīng)將今后不會(huì)再拜訪或許今后較長(zhǎng)工夫內(nèi)不會(huì)再拜訪的頁(yè)面先調(diào)出。
罕見(jiàn)的置換算法有以下四種。

1. 最佳置換算法(OPT)

最佳(Optimal, OPT)置換算法所選擇的被鐫汰頁(yè)面將是今后永不運(yùn)用的，或許是在最長(zhǎng)工夫內(nèi)不再被拜訪的頁(yè)面,如許可以包管取得最低的缺頁(yè)率。但因?yàn)槿藗兘癯療o(wú)法預(yù)知過(guò)程在內(nèi)存下的若千頁(yè)面中哪個(gè)是將來(lái)最長(zhǎng)工夫內(nèi)不再被拜訪的，因此該算法無(wú)法完成。
最佳置換算法可以用來(lái)評(píng)價(jià)其他算法。假定零碎為某過(guò)程分派了三個(gè)物理塊，并思索有以下頁(yè)面號(hào)援用串：
    7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
過(guò)程運(yùn)轉(zhuǎn)時(shí)，先將7, 0, 1三個(gè)頁(yè)面順次裝入內(nèi)存。過(guò)程要拜訪頁(yè)面2時(shí)，發(fā)生缺頁(yè)中綴，依據(jù)最佳置換算法，選擇第18次拜訪才需調(diào)入的頁(yè)面7予以鐫汰。然后，拜訪頁(yè)面0時(shí)，由于已在內(nèi)存中所以不用發(fā)生缺頁(yè)中綴。拜訪頁(yè)面3時(shí)又會(huì)依據(jù)最佳置換算法將頁(yè)面1鐫汰……依此類(lèi)推，如圖3-26所示。從圖中可以看出釆用最佳置換算法時(shí)的狀況。
可以看到，發(fā)作缺頁(yè)中綴的次數(shù)為9，頁(yè)面置換的次數(shù)為6。

圖3-26  應(yīng)用最佳置換算法時(shí)的置換圖

2. 先輩先出(FIFO)頁(yè)面置換算法

優(yōu)先鐫汰最早進(jìn)入內(nèi)存的頁(yè)面，亦即在內(nèi)存中駐留工夫最久的頁(yè)面。該算法完成復(fù)雜，只需把調(diào)入內(nèi)存的頁(yè)面依據(jù)先后次第鏈接成隊(duì)列，設(shè)置一個(gè)指針總指向最早的頁(yè)面。但該算法與過(guò)程實(shí)踐運(yùn)轉(zhuǎn)時(shí)的紀(jì)律不順應(yīng)，由于在過(guò)程中，有的頁(yè)面常常被拜訪。

圖3-27  應(yīng)用FIFO置換算法時(shí)的置換圖

這里仍用下面的實(shí)例，釆用FIFO算法停止頁(yè)面置換。過(guò)程拜訪頁(yè)面2時(shí)，把最早進(jìn)入內(nèi)存的頁(yè)面7換出。然后拜訪頁(yè)面3時(shí)，再把2, 0, 1中最先輩入內(nèi)存的頁(yè)換出。由圖 3-27可以看出，應(yīng)用FIFO算法時(shí)停止了 12次頁(yè)面置換，比最佳置換算法正很多多少一倍。
FIFO算法還會(huì)發(fā)生當(dāng)所分派的物理塊數(shù)增大而頁(yè)毛病數(shù)不減反增的異常景象，這是由 Belady于1969年發(fā)現(xiàn)，故稱為Belady異常，如圖3-28所示。只要FIFO算法能夠呈現(xiàn)Belady 異常，而LRU和OPT算法永遠(yuǎn)不會(huì)呈現(xiàn)Belady異常。

圖 3-28   Belady 異常

3. 比來(lái)最久未運(yùn)用(LRU)置換算法

選擇比來(lái)最長(zhǎng)工夫未拜訪過(guò)的頁(yè)面予以鐫汰，它以為過(guò)來(lái)一段工夫內(nèi)未拜訪過(guò)的頁(yè)面，在比來(lái)的未來(lái)能夠也不會(huì)被拜訪。該算法為每一個(gè)頁(yè)面設(shè)置一個(gè)拜訪字段，來(lái)記載頁(yè)面自前次被拜訪以來(lái)所閱歷的工夫，鐫汰頁(yè)面時(shí)選擇現(xiàn)有頁(yè)面中值最大的予以鐫汰。
再對(duì)下面的實(shí)例釆用LRU算法停止頁(yè)面置換，如圖3-29所示。過(guò)程第一次對(duì)頁(yè)面2拜訪時(shí)，將比來(lái)最久未被拜訪的頁(yè)面7置換出去。然后拜訪頁(yè)面3時(shí)，將比來(lái)最久未運(yùn)用的頁(yè)面1換出。

圖3-29  LRU頁(yè)面置換算法時(shí)的置換圖

在圖3-29中，前5次置換的狀況與最佳置換算法相反，但兩種算法并無(wú)必定聯(lián)絡(luò)。實(shí)踐上，LRU算法依據(jù)各頁(yè)以前的狀況，是“向前看”的，而最佳置換算規(guī)律依據(jù)各頁(yè)今后的運(yùn)用狀況，是“向后看”的。
LRU功能較好，但需求存放器和棧的硬件支撐。LRU是客棧類(lèi)的算法。實(shí)際上可以證實(shí)，客棧類(lèi)算法弗成能呈現(xiàn)Belady異常。FIFO算法基于隊(duì)列完成，不是客棧類(lèi)算法。

4. 時(shí)鐘(CLOCK)置換算法

LRU算法的功能接近于OPT,然則完成起來(lái)比擬艱苦，且開(kāi)支大；FIFO算法完成復(fù)雜，但功能差。所以操作零碎的設(shè)計(jì)者測(cè)驗(yàn)考試了許多算法，試圖用比擬小的開(kāi)支接近LRU的功能，這類(lèi)算法多是CLOCK算法的變體。
復(fù)雜的CLOCK算法是給每一幀聯(lián)系關(guān)系一個(gè)附加位，稱為運(yùn)用位。當(dāng)某一頁(yè)初次裝入主存時(shí)，該幀的運(yùn)用位設(shè)置為1;當(dāng)該頁(yè)隨后再被拜訪到時(shí)，它的運(yùn)用位也被置為1。關(guān)于頁(yè)交換算法，用于交換的候選幀聚集看做一個(gè)輪回緩沖區(qū)，而且有一個(gè)指針與之相干聯(lián)。當(dāng)某一頁(yè)被交換時(shí)，該指針被設(shè)置成指向緩沖區(qū)中的下一幀。當(dāng)需求交換一頁(yè)時(shí)，操作零碎掃描緩沖區(qū)，以查找運(yùn)用位被置為0的一幀。每當(dāng)碰到一個(gè)運(yùn)用位為1的幀時(shí)，操作零碎就將該位從新置為0；假如在這個(gè)進(jìn)程開(kāi)端時(shí)，緩沖區(qū)中一切幀的運(yùn)用位均為0，則選擇碰到的第一個(gè)幀交換；假如一切幀的運(yùn)用位均為1,則指針在緩沖區(qū)中完好地輪回一周，把一切運(yùn)用位都置為0，而且逗留在最后的地位上，交換該幀中的頁(yè)。因?yàn)樵撍惴ㄝ喕氐胤词「黜?yè)面的狀況，故稱為CLOCK算法，又稱為比來(lái)未用(Not Recently Used, NRU)算法。
CLOCK算法的功能比擬接近LRU，而經(jīng)過(guò)添加運(yùn)用的位數(shù)量，可以使得CLOCK算法愈加高效。在運(yùn)用位的根底上再添加一個(gè)修正位，則失掉改良型的CLOCK置換算法。如許，每一幀都處于以下四種狀況之一：

1. 比來(lái)未被拜訪，也未被修正(u=0, m=0)。

2. 比來(lái)被拜訪，但未被修正(u=1, m=0)。

3. 比來(lái)未被拜訪，但被修正(u=0, m=1)。

4. 比來(lái)被拜訪，被修正(u=1, m=1)。

算法履行如下操作步調(diào)：

1. 從指針的以后地位開(kāi)端，掃描幀緩沖區(qū)。在此次掃描進(jìn)程中，對(duì)運(yùn)用位不做任何修正。選擇碰到的第一個(gè)幀(u=0, m=0)用于交換。

2. 假如第1)步掉敗，則從新掃描，查找(u=0, m=1)的幀。選擇碰到的第一個(gè)如許的幀用于交換。在這個(gè)掃描進(jìn)程中，對(duì)每一個(gè)跳過(guò)的幀，把它的運(yùn)用位設(shè)置成0。

3. 假如第2)步掉敗，指針將回到它的最后地位，而且聚集中一切幀的運(yùn)用位均為0。反復(fù)第1步，而且假如有需要，反復(fù)第2步。如許將可以找到供交換的幀。

改良型的CLOCK算法優(yōu)于復(fù)雜CLOCK算法之處在于交換時(shí)首選沒(méi)有變更的頁(yè)。因?yàn)樾拚^(guò)的頁(yè)在被交換之前必需寫(xiě)回，因此如許做會(huì)節(jié)儉工夫。