要完全實現(xiàn)最近最少用置換算法是一件非常困難事情因...

1、l要完全實現(xiàn)最近最少用置換算法是一件非常困難的事情。因為需要對每一頁被訪問的情況進行實時記錄和更新，這顯然要花費巨大的系統(tǒng)開銷，所以在實際系統(tǒng)中往往使用LRU的近似算法。lLRU近似算法是在頁表中為每一頁增加一個“引用位”，當該頁被訪問時，由硬件將它的引用位置為“1”，操作系統(tǒng)選擇一個時間周期T，每隔一個周期T，將頁表中所有頁面的引用位置“0”，這樣，在時間周期T內(nèi)，被訪問過的頁面，其引用位為1，而沒有被訪問過的頁面，其引用位仍為0。這樣，當產(chǎn)生缺頁中斷時，可以從引用位為0的頁面中選擇一頁調(diào)出，同時將所有頁面的引用位全部置零。這種近似算法實現(xiàn)比較簡單，但關(guān)鍵在于時間周期T大小的確定。T太大，可

2、能所有的引用位都變成1，找不出最近最少使用的頁面淘汰；T太小，引用位為0的頁面可能很多，而無法保證所選擇的頁面是最近最少使用的。圖3-39給出了以O(shè)PT算法中的例子采用LRU近似算法時，保留在主存中頁面的變化情況，該進程執(zhí)行過程中，共產(chǎn)生了12次缺頁中斷，缺頁中斷率為60%，頁面淘汰的順序為7，1，2，3，0，4，0，3，2。l（4）最近最不常用頁面置換算法（Least Frequently UsedLFU）l最近最不常用置換算法總是選擇被訪問次數(shù)最少的頁面調(diào)出，即認為在過去的一段時間里被訪問次數(shù)多的頁面可能經(jīng)常需要訪問。l一種簡單的實現(xiàn)方法是為每一頁設(shè)置一個計數(shù)器，頁面每次被訪問后其對應(yīng)的計

3、數(shù)器加1，每隔一定的時間周期T，將所有計數(shù)器全部清零。這樣，在發(fā)生缺頁中斷時，選擇計數(shù)器值最小的對應(yīng)頁面淘汰，顯然它是最近最不常用的頁面，同時把所有計數(shù)器清零。這種算法實現(xiàn)比較簡單，但代價很高，同時有一個關(guān)鍵問題是如何選擇一個合適的時間周期T。l3缺頁中斷率分析缺頁中斷率分析l虛擬存儲系統(tǒng)解決了有限主存貯器的容量限制問題，能使更多的作業(yè)同時多道運行，從而提高了系統(tǒng)的效率，但缺頁中斷處理需要系統(tǒng)的額外開銷，影響系統(tǒng)效率，因此應(yīng)盡可能地減少缺頁中斷的次數(shù)，降低缺頁中斷率。l假定一個作業(yè)共有n頁，系統(tǒng)分配給它的主存塊是m塊（m、n均為正整數(shù)，且1mn）。因此，該作業(yè)最多有m頁可同時被裝入主存。如果作

4、業(yè)執(zhí)行中訪問頁面的總次數(shù)為A，其中有F次訪問的頁面尚未裝入主存，故產(chǎn)生了F次缺頁中斷?，F(xiàn)定義：lfF/A，l則f稱為“缺頁中斷率”。l顯然，缺頁中斷率與缺頁中斷的次數(shù)有關(guān)。因此影響缺頁中斷率的因素有：l（1）分配給作業(yè)的主存塊數(shù)l系統(tǒng)分配給作業(yè)的主存塊數(shù)多，則同時裝入主存的頁面數(shù)就多，那么缺頁中斷次數(shù)就少，缺頁中斷率就低，反之，缺頁中斷率就高。 l從理論上說，在虛擬存儲器的環(huán)境下，每個作業(yè)只要獲得一塊主存空間就可以開始執(zhí)行，這樣可以增加在主存中多道執(zhí)行的作業(yè)數(shù)，但是每個作業(yè)將頻繁地發(fā)生缺頁中斷，效率非常低下，如圖3-40示出了處理器的利用率與多道程序之間的關(guān)系。如果為每個作業(yè)分配很多主存塊，則

5、減少了可同時多道執(zhí)行的作業(yè)數(shù)，影響系統(tǒng)的吞吐量。模擬試驗表明，一個程序運行時發(fā)生的缺頁中斷次數(shù)是存放頁 面的實際存儲容量的函數(shù)，圖3-41所示存儲容量與缺頁中斷次數(shù)的關(guān)系。l當然圖3-41的曲線是與程序的結(jié)構(gòu)有關(guān)的，每個程序均有自己唯一的曲線。但圖3-41的曲線形狀十分典型，一個程序面對較小的主存容量時，發(fā)生的缺頁中斷次數(shù)就多，當主存容量增加時，缺頁中斷次數(shù)就減少。但從圖中可以看出，主存容量增加到80K以后，隨著主存容量的增加，缺頁中斷次數(shù)的減少就不明顯了。大多數(shù)程序都有一個特定點，在這個特定點以后再增加主存容量，缺頁中斷次數(shù)的減少并不明顯。據(jù)試驗分析表明，對每個程序來說，要使其有效工作，它在

6、主存中的頁面數(shù)應(yīng)不低于它的總頁面數(shù)的一半。如果一個有n頁的作業(yè)，當主存至少分配n/2主存空間塊時進入主存執(zhí)行，系統(tǒng)可以獲得高效率。l（2）頁面的大小l頁面的大小影響頁表的長度、頁表的檢索時間、置換頁面的時間、可能的頁內(nèi)零頭的大小等，對缺頁中斷的次數(shù)也有一定的影響。如果劃分的頁面大，一個作業(yè)的頁面數(shù)就少，頁表所占用的主存空間少且查表速度快，在系統(tǒng)分配相同主存塊的情況下，發(fā)生缺頁中斷的次數(shù)減少，降低了缺頁中斷率，但是一次換頁需要的時間延長，可能產(chǎn)生的頁內(nèi)零頭所帶來的空間浪費較大。反之，頁面小，一次換頁需要的時間就短，可能產(chǎn)生的頁內(nèi)零頭少，空間利用率提高，但是一個作業(yè)的頁面數(shù)多，頁表所占用的主存空間

7、長且查表速度慢，在系統(tǒng)分配相同主存塊的情況下，發(fā)生缺頁中斷的次數(shù)增多，增加了缺頁中斷率。l因此，頁面的大小應(yīng)根據(jù)實際確定，對不同的計算機系統(tǒng)，頁面大小不同。一般頁面大小在1K至4K字節(jié)之間。l（3）程序編制方法l程序編制的方法不同，對缺頁中斷的次數(shù)也有很大影響。缺頁中斷率與程序的局部化程度密切相關(guān)。一般，希望編制的程序能經(jīng)常集中在幾個頁面上進行訪問，以減少缺頁中斷次數(shù)，降低缺頁中斷率。l例如，一個程序要將128128數(shù)組置初值“0”。現(xiàn)假設(shè)分配給該程序的主存塊數(shù)只有一塊，頁面的大小為每頁128個字，數(shù)組中每一行元素存放在一頁中。l開始時，第一頁已經(jīng)調(diào)入主存。若程序如下編制：lA:array1.

8、128 of array1.128 of integer;l for j:=1 to 128l do for i:=1 to 128l do Aij:=0;l則每執(zhí)行一次Aij：=0就要產(chǎn)生一次缺頁中斷，總共需要產(chǎn)生（128*128-1）次缺頁中斷。l如果重新編制這個程序：lA:array1.128 of array1.128 of integer;l for i:=1 to 128l l do for j:=1 to 128l do Aij:=0;l則總共產(chǎn)生（128-1）次缺頁中斷。l（4）頁面調(diào)度算法l頁面調(diào)度算法對缺頁中斷率的影響也很大，如果選擇不當，有可能產(chǎn)生抖動現(xiàn)象。理想的調(diào)度算法

9、是當要裝入一個新頁而必須調(diào)出一個頁面時，所選擇的調(diào)出頁應(yīng)該是以后再也不使用的頁或者是距離當前最長時間以后才使用的頁。這樣的調(diào)度算法能使缺頁中斷率最低。l3.7.3請求分段式存儲管理請求分段式存儲管理 l請求分段式存儲管理以段式存儲管理為基礎(chǔ)，為用戶提供比主存實際容量更大的虛擬空間。請求分段式存儲管理把作業(yè)的各個分段信 息保留在磁盤上，當作業(yè)被調(diào)度進入主存時，首先把當前需要的一段或幾段裝入主存，便可啟動執(zhí)行，當所要訪問的段已在主存，則將邏輯地址轉(zhuǎn)換成絕對地址；如果所要訪問的段尚未調(diào)入主存，則產(chǎn)生一個“缺段中斷”，請求操作系統(tǒng)將所要訪問的段調(diào)入。為實現(xiàn)請求分段式存儲管理，需要有一定的硬件支持和相應(yīng)

10、的軟件。l請求分段式存儲管理所需要的硬件支持有段表機制、缺段中斷機構(gòu)，以及地址變換機構(gòu)等。l1段表機制段表機制 在請求分段式存儲管理中，段表是進行段調(diào)度的主要依據(jù)。在段表中需要增設(shè)段是否在主存，各段在磁盤上的存儲位置，已在主存的段需要指出該段在主存中的起始地址和占用主存區(qū)的長度，還可設(shè)置該段是否被修改，是否可擴充等標志信息。請求分段式存儲管理 的段表結(jié)構(gòu)如下：l其中：“存取方式”標識本段的存取屬性（只執(zhí)行或只讀或讀/寫）；“訪問字段A”記錄該段被訪問的頻繁程度；“修改位M”表示該段進入主存后，是否已被修改，供置換段時參考；“狀態(tài)位P”指示本段是否已調(diào)入主存，若已調(diào)入，則“段的基址”給出該段在主

11、存中的起始地址，否則在“輔存始址”中指示出本段在輔存中的起始地址；“擴充位”是請求分段式存儲管理中所特有的字段，表示本段在運行過程中是否有動態(tài)增長。l2缺段中斷機構(gòu)缺段中斷機構(gòu)l在請求分段式存儲管理中，當所要訪問的段尚未調(diào)入主存時，則由缺段中斷機構(gòu)產(chǎn)生一個“缺段中斷”信號，請求操作系統(tǒng)將所要訪問的段調(diào)入主存。操作系統(tǒng)處理缺段中斷的步驟如下：l（1）空間分配：查主存分配表，找出一個足夠大的連續(xù)區(qū)以容納該分段，如果找不到足夠大的連續(xù)區(qū)，則檢查主存中空閑區(qū)的總和，若空閑區(qū)總和能滿足該段要求，那么進行適當移動將分散的空閑區(qū)集中；若空閑區(qū)總和不能滿足該段要求，則可選擇將主存中的一段或幾段調(diào)出，然后把當前

12、要訪問的段裝入主存。l（2）修改段表：段被移動、調(diào)出和裝入后都要對段表中的相應(yīng)表目作修改。l（3）新的段被裝入后應(yīng)讓作業(yè)重新執(zhí)行被中斷的指令，這時就能在主存中找到所要訪問的段，可以繼續(xù)執(zhí)行下去。l3地址變換機構(gòu)地址變換機構(gòu)l請求分段式存儲管理方式中的地址變換在分段式存儲管理系統(tǒng)的地址變換機構(gòu)的基礎(chǔ)上增加缺段中段請求及處理等形成。圖3-42示出了請求分段式存儲管理系統(tǒng)的地址變換過程。l請求分段式存儲管理還是以段為單位進行主存空間的分配，整段信息的裝入、調(diào)出，有時需要主存空間的移動，這些都增加了系統(tǒng)的開銷。如果按段頁式存儲管理方式，每個作業(yè)仍然按邏輯分段，把每一段再分成若干頁面，這樣，在請求式存儲管理中，每一段不必占用連續(xù)的存儲空間，可按頁存放在不連續(xù)的主存塊中，甚至當主存塊不足時，可以將一段中的部分頁面裝入主存。這種管理方式稱 為“請求段頁式存儲管理”。l采用請求段頁式存儲管理，需要對每一個裝入主存的作業(yè)建立一張段表，對每一段建立一張頁表，段表中指出該段對應(yīng)頁表所存放的起始地址及其長度，頁表中應(yīng)指出該段的每一頁在磁盤上的位置以及該頁是否在主存，若在主存，則填上占用的主存塊號。作業(yè)執(zhí)行時按段號