王珍玲，丁 春

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

0 引言

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

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

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

1 虛擬存儲器管理的相關(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ū)鏈。當空閑分區(qū)表或空閑分區(qū)鏈為空時，如果有進程的頁面要執(zhí)行，而該頁又屬于缺頁現(xiàn)象，則需要采用頁面置換算法從主存淘汰一個頁面。

1.2 頁表［3］

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

(1)物理頁架號:為進程的一個頁面存放的物理頁架號。

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

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

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

2 時鐘算法

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

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

圖1 時鐘算法

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

3 改進的時鐘算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 時鐘改進算法性能分析與測試

4.1 算法性能分析

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

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

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

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

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

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

(3)重新啟動該進程的時間。

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

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

4.2 算法的性能測試

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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