一種基于局部性原則的時(shí)鐘置換改進(jìn)算法

王珍玲，丁 春

(天津職業(yè)技術(shù)師范大學(xué)信息技術(shù)工程學(xué)院，天津 300222)

0 引言

操作系統(tǒng)虛擬存儲(chǔ)器管理技術(shù)的優(yōu)點(diǎn)具有很強(qiáng)的吸引力，現(xiàn)代操作系統(tǒng)從理論到實(shí)踐證明了這種技術(shù)是行之有效的，且已成為大多數(shù)操作系統(tǒng)的一個(gè)基本組成部分。虛擬存儲(chǔ)器的理論依據(jù)——局部性原理，是指程序在執(zhí)行過程中的一個(gè)較短時(shí)間內(nèi)，程序所執(zhí)行的指令地址和操作數(shù)的地址分別局限于一定的區(qū)域內(nèi)，它具體表現(xiàn)為時(shí)間局部性和空間局部性兩個(gè)方面［1］。

實(shí)現(xiàn)虛擬存儲(chǔ)器管理技術(shù)采用的頁面置換算法直接影響著計(jì)算機(jī)系統(tǒng)的性能。如果選用的算法不合適，可能會(huì)出現(xiàn)“抖動(dòng)”現(xiàn)象。也就是說，剛被置換出主存的頁面，不久又要被訪問，這樣又要把它調(diào)入主存，同時(shí)，又要將某一頁置換出主存。如果頻繁地進(jìn)行頁面從主存到輔存的置換，致使系統(tǒng)的大部分時(shí)間浪費(fèi)在頁面的調(diào)度上，從而影響整個(gè)系統(tǒng)的性能［2］。

由于數(shù)據(jù)結(jié)構(gòu)簡單，時(shí)鐘算法是操作系統(tǒng)常用的頁面置換算法，但是該算法在實(shí)現(xiàn)上淘汰頁面所進(jìn)行的I/O操作會(huì)產(chǎn)生較大的開銷。本文針對(duì)時(shí)鐘算法的這一缺陷，提出一種改進(jìn)的時(shí)鐘算法，可減少淘汰頁面時(shí)需要的I/O操作，以提高系統(tǒng)性能。

1 虛擬存儲(chǔ)器管理的相關(guān)技術(shù)

1.1 數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)即分區(qū)分配中所用的數(shù)據(jù)組織形式。常用的數(shù)據(jù)結(jié)構(gòu)有兩種形式:空閑分區(qū)表或空閑分區(qū)鏈。當(dāng)空閑分區(qū)表或空閑分區(qū)鏈為空時(shí)，如果有進(jìn)程的頁面要執(zhí)行，而該頁又屬于缺頁現(xiàn)象，則需要采用頁面置換算法從主存淘汰一個(gè)頁面。

1.2 頁表［3］

頁表是一個(gè)數(shù)組，每個(gè)表目對(duì)應(yīng)著進(jìn)程的一個(gè)虛頁，記錄著物理頁架號(hào)、修改位和訪問位等有關(guān)進(jìn)程的信息。

(1)物理頁架號(hào):為進(jìn)程的一個(gè)頁面存放的物理頁架號(hào)。

(2)修改位:有2個(gè)狀態(tài)。為“1”時(shí)，表示對(duì)應(yīng)的進(jìn)程頁面調(diào)入主存后內(nèi)容被修改過，置換出主存時(shí)，需修改交換區(qū)和相應(yīng)的文件;為“0”時(shí)，表示對(duì)應(yīng)的進(jìn)程頁面調(diào)入主存后內(nèi)容沒有修改過，置換出主存時(shí)，什么也不需要做。

(3)訪問位:有2個(gè)狀態(tài)。為“1”時(shí)，表示對(duì)應(yīng)的進(jìn)程頁面調(diào)入主存后被訪問過;為“0”時(shí)，表示對(duì)應(yīng)的進(jìn)程頁面調(diào)入主存后沒有被訪問過。

當(dāng)需要將進(jìn)程的某一頁裝入內(nèi)存時(shí)，如果空閑分區(qū)表或空閑分區(qū)鏈為空，則需要參照進(jìn)程的頁表，按照一定的頁面置換算法，從主存淘汰一個(gè)頁面。

2 時(shí)鐘算法

把調(diào)入主存的進(jìn)程的各個(gè)頁面，按調(diào)入主存的時(shí)間順序用鏈指針進(jìn)行鏈接，選擇淘汰頁時(shí)，從鏈頭開始查找。按照局部性原理，剛剛被訪問的頁很快還要被訪問的可能性很大［4］。在尋找淘汰頁的時(shí)候，為了避免剛剛訪問的頁被淘汰，以避免“抖動(dòng)”現(xiàn)象的出現(xiàn)，頁面鏈表頭的訪問位為1的頁面，不斷被移動(dòng)到鏈尾［5］，這樣將增大系統(tǒng)的開銷。

時(shí)鐘算法［6］是將進(jìn)程需要訪問的所有頁構(gòu)成像時(shí)鐘一樣的環(huán)形鏈表，用一個(gè)指針指向調(diào)入主存最早的頁。當(dāng)產(chǎn)生缺頁中斷時(shí)，先檢測(cè)指針指向的頁。如果它的訪問位為0，則淘汰該頁。新裝入的頁插入到這個(gè)位置，然后指針向前移動(dòng)一個(gè)位置;如果它的訪問位為1，則清除為0，同時(shí)將指針向前移動(dòng)一個(gè)位置，繼續(xù)檢查訪問位，直到找到第一個(gè)訪問位為0的頁面。時(shí)鐘算法如圖1所示。

圖1 時(shí)鐘算法

按照時(shí)鐘置換算法，當(dāng)選擇出淘汰頁后，由于該頁調(diào)入主存有可能被修改過，這樣，置換出主存時(shí)要相應(yīng)地修改交換區(qū)和相應(yīng)的文件［7-8］。

3 改進(jìn)的時(shí)鐘算法

為了盡量避免按照時(shí)鐘置換算法將調(diào)入主存后被修改過的頁置換出去，從而增加系統(tǒng)修改交換區(qū)和相應(yīng)的文件帶來的開銷，在選擇淘汰頁時(shí)，可同時(shí)參考頁表的訪問位和修改位的狀態(tài)。在遵循局部性原則的基礎(chǔ)上，在出現(xiàn)缺頁現(xiàn)象時(shí)，優(yōu)先淘汰訪問位和修改位都為0的頁面。

當(dāng)運(yùn)行一個(gè)進(jìn)程時(shí)，由操作系統(tǒng)設(shè)置進(jìn)程所有頁的訪問位和修改位初值為0。每次調(diào)入主存時(shí)，該頁的訪問位置為1;如果調(diào)入主存又被修改，該頁的修改位置為1。訪問位被定期(如間隔某個(gè)時(shí)間)清0。

進(jìn)程的所有頁面，按照訪問位和修改位的值可分為 4 類［6，9］。

(1)a類:最近未訪問過，未修改。值為00。

(2)b類:最近未訪問過，已修改。值為01。

(3)c類:最近訪問過，未修改。值為10。

(4)d類:最近訪問過，已修改。值為11。

改進(jìn)的時(shí)鐘算法同樣將進(jìn)程需要訪問的所有頁構(gòu)成像時(shí)鐘一樣的環(huán)形鏈表，用一個(gè)指針指向調(diào)入主存最早的頁。當(dāng)產(chǎn)生缺頁中斷時(shí)，掃描環(huán)形鏈表，首先檢查指針指向的最早頁屬于哪一類，來確定淘汰頁。具體執(zhí)行過程如下。

(1)從指針指向的鏈頭開始，循環(huán)掃描環(huán)形鏈表，尋找第一個(gè)a類頁，即訪問位為0，修改位為0，則該頁為選定的淘汰頁，而在第一輪掃描期間不改變?cè)擁摰脑L問位。

(2)如果第(1)步失敗，即沒有找到a類頁，則重新開始第二輪掃描。在第二輪掃描期間，尋找第一個(gè)b類頁，即訪問位為0，修改位為1，遇到的第一個(gè)b類頁為選定的淘汰頁。在第二輪掃描期間，將所經(jīng)過的每一頁的訪問位都置為0。

(3)如果第(2)步也失敗，即沒有找到b類頁，則將指針返回初始位置，且將環(huán)型鏈表中所有頁面的訪問位清0;然后，返回第(1)步，繼續(xù)執(zhí)行。此時(shí)，一定能夠找到被淘汰的頁。

改進(jìn)的時(shí)鐘算法在執(zhí)行過程中，循環(huán)掃描環(huán)型鏈表中所有頁，優(yōu)先淘汰的頁是最近沒有被訪問過且沒有被修改過的頁。它的優(yōu)點(diǎn)在于，在滿足局部性原則的基礎(chǔ)上，選擇出的淘汰頁不必對(duì)交換區(qū)和相應(yīng)的文件進(jìn)行修改。如果第一輪沒有找到淘汰頁，進(jìn)入第二輪尋找。在第二輪尋找的過程中，按照局部性原則，選擇出的淘汰頁屬于最近沒有被訪問的頁。如果第二輪也沒有找到淘汰頁，就把環(huán)型鏈表中的所有頁的訪問位都清0，然后，返回第(1)步，循環(huán)上述過程，肯定能夠找到要淘汰的頁［10］。

改進(jìn)的時(shí)鐘算法在算法的實(shí)現(xiàn)性能上比時(shí)鐘置換算法有較好的改進(jìn)。為了實(shí)現(xiàn)虛擬存儲(chǔ)器管理技術(shù)，當(dāng)進(jìn)程訪問的頁不在主存時(shí)，系統(tǒng)需要將輔存的頁面調(diào)入主存，從而需要啟動(dòng)I/O操作，而在這一活動(dòng)中將要消耗近10%的CPU工作時(shí)間。置換算法的基本目的是力求減少I/O操作的次數(shù)和減少一次I/O操作的開銷［11-12］。改進(jìn)的時(shí)鐘算法在出現(xiàn)缺頁現(xiàn)象時(shí)，通過參考頁表中訪問位和修改位，減少了缺頁時(shí)需要的I/O操作，從而減少了CPU機(jī)時(shí)的消耗，提高了CPU的工作效率。

駐留主存中頁面所構(gòu)成的環(huán)型鏈表及頁面的所屬類如圖2所示［13］。按照改進(jìn)的時(shí)鐘算法，淘汰頁的順序依次為:1頁、9頁、4頁、2頁、3頁、5頁、6頁、7頁、8頁、10頁、0頁。

圖2 環(huán)型頁面鏈表

4 時(shí)鐘改進(jìn)算法性能分析與測(cè)試

4.1 算法性能分析

當(dāng)發(fā)生缺頁中斷時(shí)，首先要從輔存讀入該頁，然后再進(jìn)行內(nèi)存存取。有效的頁面存取時(shí)間［6］可以表示為:

有效的頁面存取時(shí)間=(1-p)×m+p×缺頁處理時(shí)間

其中:p代表缺頁中斷概率;m代表內(nèi)存存取時(shí)間。

在任何情況下，缺頁中斷處理所花費(fèi)的時(shí)間基本上由3部分組成:

(1)處理缺頁中斷的時(shí)間;

(2)從輔存調(diào)入該頁的時(shí)間;

(3)重新啟動(dòng)該進(jìn)程的時(shí)間。

操作系統(tǒng)可以通過代碼的設(shè)計(jì)使第(1)、(3)項(xiàng)的執(zhí)行時(shí)間控制在1～100 μs，而在第(2)項(xiàng)花費(fèi)的時(shí)間將近25 ms。從輔存調(diào)入該頁的時(shí)間，即啟動(dòng)一次I/O操作的時(shí)間直接影響著缺頁處理時(shí)間，并與有效的頁面存取時(shí)間成正比關(guān)系。

改進(jìn)的時(shí)鐘算法在實(shí)現(xiàn)頁面置換的過程中，優(yōu)先淘汰的頁面是主存中訪問位和修改位為0的頁面，選擇這樣的頁面優(yōu)先淘汰既遵循了局部性原則，又避免了對(duì)輔存相應(yīng)的頁面進(jìn)行修改，所以可以避免啟動(dòng)I/O操作;其次選擇的淘汰頁面為訪問位為0、修改位為1的頁面，這樣的頁面選擇遵循了局部性原則，從而避免了剛剛淘汰的頁又要被訪問，需要啟動(dòng)I/O操作，減少了進(jìn)程在運(yùn)行過程中消耗在缺頁處理的時(shí)間。這樣縮短了有效的頁面存取時(shí)間，提高了系統(tǒng)的性能。

4.2 算法的性能測(cè)試

駐留主存頁面及頁面訪問屬性如圖2所示。假設(shè)出現(xiàn)5次缺頁中斷，需要進(jìn)行5次淘汰頁面的情況下:

(1)采用時(shí)鐘算法。選擇出的淘汰頁面依次為:1頁、2頁、3頁、4頁和5頁。由于2頁、3頁和5頁的訪問位均為1，屬于最近剛剛訪問的頁面，根據(jù)局部性原則，短時(shí)間還要訪問的可能性很大，這樣又需要從輔存調(diào)入主存，則需要啟動(dòng)3次I/O操作。

(2)采用改進(jìn)的時(shí)鐘算法。選擇出的淘汰頁面依次為:1頁、9頁、4頁、2頁和3頁。與時(shí)鐘算法相比，不需要淘汰第5頁，增加了第9頁，而第9頁屬于a類頁，既滿足了局部性原則，又不需要對(duì)輔存相應(yīng)的頁面進(jìn)行修改，這樣相對(duì)于時(shí)鐘算法，減少了1次I/O操作，同時(shí)輔存相應(yīng)的頁面不需要修改，也避免了1次I/O操作。

由以上分析可以說明，在淘汰頁面的時(shí)候，改進(jìn)的時(shí)鐘算法相對(duì)于時(shí)鐘算法，在產(chǎn)生的I/O操作次數(shù)和對(duì)輔存相應(yīng)的頁面進(jìn)行修改的次數(shù)均有所減少，從而減少了系統(tǒng)在頁面置換上的消耗，提高了系統(tǒng)的性能。

5 結(jié)束語

改進(jìn)的時(shí)鐘算法，延續(xù)了時(shí)鐘算法的數(shù)據(jù)結(jié)構(gòu)，充分利用了頁表表項(xiàng)訪問位和修改位，具有數(shù)據(jù)組織結(jié)構(gòu)簡單、明了，使用便利等優(yōu)點(diǎn);同時(shí)在優(yōu)先考慮先來先服務(wù)的原則及遵循局部性原則的基礎(chǔ)上，利用訪問位和修改位的狀態(tài)值，在主存空間出現(xiàn)缺頁現(xiàn)象時(shí)，優(yōu)先選擇出淘汰頁面，既避免了“抖動(dòng)”現(xiàn)象，又可最大限度地減少系統(tǒng)淘汰頁面帶來的開銷，從而提高了實(shí)現(xiàn)虛擬存儲(chǔ)管理的性能。

［1］黃水松，黃干平，曾平，等.計(jì)算機(jī)操作系統(tǒng)［M］.武漢:武漢大學(xué)出版社，2003:156-158.

［2］曹先彬，陳香蘭.操作系統(tǒng)原理與設(shè)計(jì)［M］.北京:機(jī)械工業(yè)出版社，2009:180-187.

［3］湯小丹，梁紅兵，哲鳳屏，等.計(jì)算機(jī)操作系統(tǒng)(第3版)［M］.西安:西安電子科技大學(xué)出版社，2007:153-154.

［4］徐宗元.操作系統(tǒng)(第2版)［M］.北京:高等教育出版社，2005:120.

［5］［美］Lubomir F Bic，Alan C Shaw.操作系統(tǒng)原理［M］.梁洪亮，等譯.北京:清華大學(xué)出版社，2005:214-215.

［6］孟慶昌.操作系統(tǒng)［M］.北京:電子工業(yè)出版社，2004:186-187.

［7］諶衛(wèi)軍，王浩娟.操作系統(tǒng)［M］.北京:清華大學(xué)出版社，2012:115-117.

［8］許日濱，孫英華，程亮.操作系統(tǒng)［M］.北京:北京郵電大學(xué)出版社，2005:154-158.

［9］劉振鵬，王煜，張明.操作系統(tǒng)(第3版)［M］.北京:中國鐵道出版社，2007:174-175.

［10］［美］William Stallings.操作系統(tǒng):精髓與設(shè)計(jì)原理［M］.陳向群，陳渝譯.北京:機(jī)械工業(yè)出版社，2010:248-249.

［11］李占勝，畢會(huì)娟，李艷平，等.一種對(duì)LRFU置換策略的自適應(yīng)改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44(17):153-157.

［12］魏文國，趙慧民，莊林凱，等.一種基于時(shí)鐘自適應(yīng)的改進(jìn)緩存替換算法［J］.中山大學(xué)學(xué)報(bào):自然科學(xué)版，2012，51(6):54-57，62.

［13］［荷］Andrew S Tanenbaum.現(xiàn)代操作系統(tǒng)(第3版)［M］.陳向群，馬洪兵譯.北京:機(jī)械工業(yè)出版，2009:120-121.

［14］劉智臣，孟益民，余俊杰.一種時(shí)鐘改進(jìn)算法的分析與實(shí)現(xiàn)［J］.計(jì)算機(jī)工程，2006，32(14):63-65.