虛擬存儲管理

虛擬存儲管理第1頁，共81頁，2023年，2月20日，星期二引言

上一章介紹了實存儲管理技術，各種實存儲管理技術有一個共同的特點，即它們都要求把進程全部裝入內(nèi)存才能運行。在運行過程中，往往可能出現(xiàn)兩種情況：要求運行的進程所需的內(nèi)存空間之和大于系統(tǒng)的內(nèi)存空間，只能有部分進程能夠裝入內(nèi)存運行，而其它進程只有留在外存中等待；邏輯地址空間大于存儲空間的進程無法在系統(tǒng)中運行。為了解決以上問題，可有兩種解決方案：一是從物理上增加內(nèi)存容量。但這受到機器尋址能力的限制，不能無限擴充，而且無疑會增加系統(tǒng)成本；二是從邏輯上擴充內(nèi)存容量，這就是本章所要討論的“虛擬存儲”管理技術。第2頁，共81頁，2023年，2月20日，星期二8．1虛擬存儲器的基本概念

虛擬存儲管理要研究的問題是：

1.作業(yè)信息不全部裝入主存，能否保證作業(yè)的正確運行？回答是肯定的,1968年P.Denning研究了程序執(zhí)行時的局部性原理。

2.以CPU時間和外存空間換取昂貴內(nèi)存空間，如何進行動態(tài)調(diào)度？第3頁，共81頁，2023年，2月20日，星期二8．1虛擬存儲器的基本概念程序的局部性原理：

指程序在執(zhí)行過程中的一個較短時間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)域中。具體地表現(xiàn)為時間局部性和空間局部性。第4頁，共81頁，2023年，2月20日，星期二8．1．1局部性原理

程序執(zhí)行呈現(xiàn)局部性規(guī)律的原因：程序執(zhí)行時，大多數(shù)情況下是順序執(zhí)行的。很少出現(xiàn)連續(xù)的過程調(diào)用，相反，程序中過程調(diào)用的深度限制在小范圍內(nèi)，一段時間內(nèi)，指令引用被局限在很少幾個過程中。程序中有許多循環(huán)語句，這些語句會重復多次執(zhí)行。程序中對數(shù)據(jù)結構的操作，往往局限在很小的范圍內(nèi)。第5頁，共81頁，2023年，2月20日，星期二8．1．1局部性原理

局部性原理的表現(xiàn)形式：時間局限性：如果某條指令被執(zhí)行，則在不久的將來，該指令可能被再次執(zhí)行；如果某個數(shù)據(jù)結構被訪問，則在不久的將來，該數(shù)據(jù)結構可能再次被訪問。產(chǎn)生時間局限性的主要原因是程序中存在著大量的循環(huán)操作?？臻g局限性：一旦程序訪問了某個存儲單元，則在不久的將來，其附近的存儲單元也可能被訪問，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)。產(chǎn)生空間局限性的主要原因是程序的順序執(zhí)行。實現(xiàn)虛擬存儲器的理論基礎：局部性原理。第6頁，共81頁，2023年，2月20日，星期二8．1．2虛擬存儲器

實現(xiàn)方法：一個進程在運行之時，沒有必要全部裝入內(nèi)存，而只把當前運行所需要的頁（段）裝入內(nèi)存便可啟動運行，而其余部分則存放在磁盤上。程序在運行時，如果所需要的頁（段）已經(jīng)調(diào)入內(nèi)存，便可以繼續(xù)執(zhí)行下去。如果所需要的頁（段）不在內(nèi)存，此時程序應利用操作系統(tǒng)所提供的請求調(diào)頁（段）功能，將該頁（段）調(diào)入內(nèi)存，以使程序能夠運行下去。如果此時分配給該程序的內(nèi)存已全部占用，不能裝入新的頁（段），則需要利用系統(tǒng)的置換功能，把內(nèi)存中暫時不用的頁（段）調(diào)出至磁盤上，騰出足夠的內(nèi)存空間，再將所要裝入的頁（段）調(diào)入內(nèi)存，使程序能夠繼續(xù)運行下去。第7頁，共81頁，2023年，2月20日，星期二8．1．2虛擬存儲器

虛擬存儲器的定義：是指僅把進程的一部分裝入內(nèi)存便可運行的存儲器系統(tǒng)，它具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲器系統(tǒng)。虛擬存儲器的邏輯容量：虛擬存儲器的邏輯容量由系統(tǒng)的尋址能力和外存容量之和所決定。

第8頁，共81頁，2023年，2月20日，星期二8．1．2虛擬存儲器虛擬存儲管理主要采用以下技術實現(xiàn)：

?請求分頁虛擬存儲管理

?請求分段虛擬存儲管理

?請求段頁式虛擬存儲管理第9頁，共81頁，2023年，2月20日，星期二8．2請求分頁式存儲管理方式

請求分頁式存儲管理是在分頁式存儲管理的基礎上，增加了請求調(diào)頁功能、頁面置換功能而形成的頁式虛擬存儲系統(tǒng)。它是目前常用的一種虛擬存儲器的方式。第10頁，共81頁，2023年，2月20日，星期二8．2請求分頁式存儲管理方式基本原理：在請求分頁式存儲管理系統(tǒng)中，進程運行之前將一部分頁面裝入內(nèi)存，另外一部分頁面則裝入外存。在進程運行過程中，如果所訪問的頁面不在內(nèi)存中，則發(fā)生缺頁中斷，進入操作系統(tǒng)，由操作系統(tǒng)進行頁面的動態(tài)調(diào)度。系統(tǒng)需要解決下面三個問題：系統(tǒng)如何獲知進程當前所需頁面不在主存。當發(fā)現(xiàn)缺頁時，如何把所缺頁面調(diào)入主存。當主存中沒有空閑的頁框時，為了要接受一個新頁，需要把老的一頁淘汰出去，根據(jù)什么策略選擇欲淘汰的頁面。第11頁，共81頁，2023年，2月20日，星期二8．2．1請求分頁式存儲管理的基本概念

其方法如下：找到被訪問頁面在外存中的地址；在內(nèi)存中找一個空閑塊，如果沒有，則按照淘汰算法選擇一個內(nèi)存塊，將此塊內(nèi)容寫回外存，修改頁表；讀入所需的頁面，修改頁表；重新啟動進程，執(zhí)行被中斷的指令。

第12頁，共81頁，2023年，2月20日，星期二8．2．1請求分頁式存儲管理的基本概念

頁表機制：純分頁的頁表只有兩項：頁號和物理塊。而請求分頁存儲管理增加了調(diào)入功能和置換功能，故需在頁表中增加若干項，供程序在換進換出時參考。下面所示是一請求分頁系統(tǒng)中的頁表：頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址狀態(tài)位P：記錄該頁是否在內(nèi)存。P=0該頁在內(nèi)存；

P=1該頁不在內(nèi)存。訪問字段A：記錄該頁多長時間沒有被訪問。修改位M：記錄該頁在內(nèi)存期間是否被修改過。

M=1該頁調(diào)入內(nèi)存后被修改過；

M=0該頁調(diào)入內(nèi)存后未被修改過。外存地址：該頁在外存上的地址第13頁，共81頁，2023年，2月20日，星期二8．2．1請求分頁式存儲管理的基本概念

請求分頁存儲管理示意圖：物理地址空間頁面映射表存儲空間頁號塊號狀態(tài)作業(yè)10110430001作業(yè)20123作業(yè)30123410610329011011103212700412345678910111213第14頁，共81頁，2023年，2月20日，星期二8．2．1請求分頁式存儲管理的基本概念

地址變換機構：請求分頁系統(tǒng)中的地址變換機構，是在分頁系統(tǒng)的地址變換機構的基礎上，為實現(xiàn)虛擬存儲器而增加了產(chǎn)生和處理缺頁中斷、頁面置換等功能而形成的。下圖給出了請求分頁系統(tǒng)的地址變換過程。第15頁，共81頁，2023年，2月20日，星期二8．2．1請求分頁式存儲管理的基本概念

否否否是是產(chǎn)生缺頁中斷否是否是程序請求訪問一頁頁號>頁表長度？越界中斷CPU檢索快表頁表項是否在快表中？訪問頁表頁是否在內(nèi)存中？修改快表修改訪問位和修改位保留CPU現(xiàn)場缺頁中斷處理從外存中找到該頁內(nèi)存滿否？選擇一頁換出該頁修改否？將該頁寫回外存CPU從外存讀缺頁啟動I/O硬件形成物理地址地址變換結束將一頁從外存換入內(nèi)存修改頁表是第16頁，共81頁，2023年，2月20日，星期二查快表有登記無登記查頁表登記入快表發(fā)缺頁中斷在主存在輔存形成絕對地址繼續(xù)執(zhí)行指令重新執(zhí)行被中斷指令恢復現(xiàn)場調(diào)整頁表和主存分配表裝入所需頁面主存有空閑塊保護現(xiàn)場有選擇調(diào)出頁面該頁是否修改未修改已修改把該頁寫回輔存相應位置操作系統(tǒng)硬件邏輯地址無第17頁，共81頁，2023年，2月20日，星期二8．2．2頁面分配策略

內(nèi)存頁面分配策略：平均分配：將內(nèi)存中的所有可供分配的物理塊，平均分配給各個進程。這是最簡單的分配方式，它看起來很公平，但實際上很不公平，因為它沒有考慮進程的大小等因素。按進程大小比例分配：系統(tǒng)按進程的大小按比例分配物理塊。若m為可用物理塊總和，S為各進程頁面總和，si為第i個進程的頁面數(shù)，則為第i個進程分配的頁面數(shù)為：按進程優(yōu)先級比例分配：為照顧重要的、緊迫的進程，使其能夠盡快的完成，可以為其分配較多的內(nèi)存物理塊。

第18頁，共81頁，2023年，2月20日，星期二8．2．2頁面分配策略

外存塊的分配策略：靜態(tài)分配：一個進程在運行前，將其所有頁面全部裝入外存。當某一外存頁面被調(diào)入內(nèi)存時，所占用外存頁面并不釋放。這樣，當該頁面以后被淘汰時，如果它在內(nèi)存中未被修改過，則不必寫回外存，因為外存中有一個和它完全相同的副本，這可以減少因頁面調(diào)度而引起的系統(tǒng)開銷，代價是犧牲一定的外存空間。動態(tài)分配：一個進程在運行前，僅將未裝入內(nèi)存的那部分頁面裝入外存。當某一外存頁面被調(diào)入內(nèi)存，釋放所占用的外存空間。這樣，當該頁面以后被淘汰時，不管它在內(nèi)存中是否被修改過，都必須重新為其申請外存物理塊，將該頁重新寫回外存。這種方法的優(yōu)點是節(jié)省外存空間，但會增加由頁面調(diào)度而引起的系統(tǒng)開銷。第19頁，共81頁，2023年，2月20日，星期二8．2．3頁面調(diào)入時機

請求調(diào)頁策略：發(fā)生缺頁時，調(diào)入內(nèi)存。根據(jù)局部性原理,一段時間后,缺頁中斷會下降到很低水平,程序進入相對平穩(wěn)階段。

缺點：處理缺頁中斷和調(diào)頁的系統(tǒng)開銷較大，每次僅調(diào)一頁,增加了磁盤I/O次數(shù)。預調(diào)頁策略：預計要訪問的頁，提前調(diào)入內(nèi)存。每次調(diào)入若干頁面,而不是僅調(diào)一頁。一次調(diào)入多頁能減少磁盤I/O啟動次數(shù)。缺點：如果調(diào)入的一批頁面中多數(shù)未被使用,則效率就很低了，可見預調(diào)頁要建立在預測的基礎上第20頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法目標：把未來不再使用的或短時間內(nèi)不再使用的頁調(diào)出。最佳置換算法OPT先進先出置換算法FIFO最近最久未使用置換算法LRU時鐘置換算法第21頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

最佳置換算法（OPT，Optimal）：最佳置換算法置換那些以后永不再使用的或者在最長的時間以后才會用到的頁面。顯然，這種算法的缺頁率最低。然而，該算法只是一種理論上的算法，因為很難估計哪一個頁面是以后永遠不再使用或在最長時間以后才會用到的頁面，所以，這種算法是不能實現(xiàn)的。盡管如此，該算法仍然是有意義的，可以把它作為衡量其它算法優(yōu)劣的一個標準。第22頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

【例8-1】假定系統(tǒng)為某進程分配了3個物理塊，頁面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最佳置換算法，計算缺頁中斷次數(shù)和缺頁中斷率。解：頁面置換過程如下表所示：頁面訪問序列50120304230321201501501113333333322225555000004440000000000522222222221111111++++-+-+--+--+---+--缺頁中斷次數(shù)=9缺頁中斷率=9/20=45%

第23頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

先進先出置換算法（FIFO，F(xiàn)irst-InFirst-Out）

：先進先出置換算法總是置換最先進入內(nèi)存的頁面。該算法實現(xiàn)簡單，只須把一個進程已調(diào)入內(nèi)存的頁面，按照進入內(nèi)存的先后順序排成一個隊列，當一個頁面由外存調(diào)入內(nèi)存時排入隊尾，需要淘汰時取隊首的頁面。第24頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

【例8-2】假定系統(tǒng)為某進程分配了3個物理塊，頁面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用先進先出置換算法，計算缺頁中斷次數(shù)和缺頁中斷率。解：頁面置換過程如下表所示：頁面訪問序列50120304230321201501501223042300012225015011230423330111250500123042223000125++++-++++++--++--+++缺頁中斷次數(shù)=15缺頁中斷率=15/20=75%

第25頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

Belady異?，F(xiàn)象：一般而言，分配給進程的物理塊越多，運行時的缺頁次數(shù)應該越少。但是Belady在1969年發(fā)現(xiàn)了一個反例，使用FIFO算法時，四個物理塊時的缺頁次數(shù)比三個物理塊時的多，這種反常的現(xiàn)象稱為Belady異常。如下面兩表所示，一個進程有5個頁面，頁面訪問序列如下：Belady異常現(xiàn)象（3個物理塊的FIFO現(xiàn)象）

第26頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

Belady異?，F(xiàn)象（4個物理塊的FIFO現(xiàn)象）

由表中可見，3個物理塊時缺頁次數(shù)是9次，缺頁中斷率為9/12=75%；而4個物理塊時的缺頁次數(shù)是10次，缺頁中斷率為10/12≈83.3%。第27頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

最近最久未使用置換算法（LRU，LeastRecentlyUsed）：該算法的基本思想是：如果某一頁面被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁面很久沒有被訪問，那么最近也不會再次被訪問。因此，該算法為每一個頁面設置一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，當須淘汰一個頁面時，選擇現(xiàn)有頁面中t值最大的，即最近最久未使用的頁面予以淘汰。LRU的實現(xiàn)：記時法：系統(tǒng)為每一頁面增設一個記時器。每當一個頁面被訪問時，當時的絕對時鐘內(nèi)容被拷貝到對應的記時器中，這樣系統(tǒng)記錄了內(nèi)存所有頁面最后一次被訪問的時間。淘汰頁面時，選取記時器中值最小的頁面淘汰。第28頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

堆棧法：用一個棧保留頁號。每當訪問一個頁面時，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放最新被訪問頁面的頁面號，而棧底放著最近最久未使用的頁面號。由于要從棧的中間移走一項，所以要用具有頭尾指針的雙向鏈連起來。注意：不是通常意義上的棧

第29頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

LRU的缺點：雖然LRU在理論上是可以實現(xiàn)的，但代價太高。為了實現(xiàn)LRU，需要在內(nèi)存維持一個包含所有頁的鏈表，最近使用的頁面在表頭，最近未使用的頁面在表尾。而每次訪問頁面時都需要對鏈表進行更新。在鏈表中找到所需的頁，將它移動到表頭是一個非常費時的操作，即使使用硬件實現(xiàn)也是一樣。

第30頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

【例8-3】假定系統(tǒng)為某進程分配了3個物理塊，頁面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最近最久未使用置換算法，計算缺頁中斷次數(shù)和缺頁中斷率。解：頁面置換過程如下表所示：頁面訪問序列50120304230321201501501203042303212015015012030423032120150501223042203312015++++-+-++++--+-+-+--缺頁中斷次數(shù)=12缺頁中斷率=12/20=60%

第31頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

Clock置換算法（最近未使用算法

(NRU)）：最近最久未使用置換算法是一種比較合理的算法，但它經(jīng)常要在鏈表中移動頁面，大大降低了系統(tǒng)效率。為了克服這個缺陷，把所有的頁面保存在一個類似時鐘表面的環(huán)形鏈表中，用一個表針指向可能淘汰的頁面，如下圖所示ABCDEFGHIJK設置一個訪問位:0表示最近未使用

1表示最近使用過第32頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

當發(fā)生缺頁時，該算法首先檢查表針指向的頁面，如果其訪問位是0，則淘汰該頁，并把新的頁面插入到這個位置，然后把表針前移一個位置；如果訪問位是1則把其置0，暫不換出，并把表針前移一個位置，重復這個過程直到找到一個訪問位為0的頁為止。了解了這個算法的工作方式，我們就知道這種算法為什么被稱為Clock算法了。但因該算法只有一位訪問位，只能用它表示該頁是否使用過，而置換時將未使用過的頁面換出去，故又把該算法稱為最近未使用算法（NRU）。ABCDEFGHIJK第33頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法CLOCK算法執(zhí)行過程第34頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

改進CLOCK置換算法事實上，時鐘算法不但希望淘汰最近未訪問的頁，而且還希望被挑選的頁在內(nèi)存駐留期間，其頁面內(nèi)的數(shù)據(jù)未被修改過。淘汰該頁時，由于該頁未被修改過，因此不必寫盤，從而減少了磁盤的I/O操作次數(shù)。為此，要為每頁增設兩個硬件位：訪問位和修改位：第35頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

訪問位A=0：該頁尚未被訪問過

=1：該頁已經(jīng)被訪問過修改位M=0：該頁尚未被修改過

=1：該頁已經(jīng)被修改過訪問位和修改位的組合有以下四種：1類（A=0，M=0）：表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁；2類（A=0，M=1）：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁；3類（A=1，M=0）：最近已被訪問，但未被修改，該頁有可能再次被訪問；4類（A=1，M=1）：最近已被訪問且被修改，該頁可能再次被訪問。第36頁，共81頁，2023年，2月20日，星期二8．2．4頁面置換算法

改進CLOCK算法執(zhí)行過程①從當前位置掃描循環(huán)隊列，尋找<1>類頁面,找到后立即置換

。②若步驟①失敗，開始第二輪掃描，尋找<2>類頁面找到后立即置換

。并將所經(jīng)過的頁面的訪問位置0。③若步驟②也失敗，重復步驟①，若仍失敗，再重復步驟②。第37頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析

請求分頁式存儲管理系統(tǒng)的性能優(yōu)越，較好地解決了存儲擴充問題。因此，它是目前最常用的存儲管理方式。但進程在運行時所產(chǎn)生的缺頁中斷，會影響程序的運行速度及系統(tǒng)性能。而缺頁率的高低又與分配給進程的物理塊數(shù)直接相關。因此，本節(jié)所要介紹的主要內(nèi)容是分析:

1.缺頁率對系統(tǒng)性能的影響程度

2.為每個進程分配多少物理塊數(shù)目，才能把缺頁率保持在一個合理的水平上。第38頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析

缺頁率對有效訪問時間的影響

：有效訪問時間：設p為缺頁率，t為存儲器訪問時間，則有效訪問時間為：

有效訪問時間=（1－p）×t+p×缺頁中斷時間缺頁中斷時間的組成：缺頁中斷時間主要由三部分組成：缺頁中斷服務時間；將所缺的頁讀入的時間；進程重新執(zhí)行時間。第39頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析

缺頁中斷率對訪問時間的影響：其中缺頁中斷服務時間和進程重新執(zhí)行時間之和可以不超過1ms,而將一磁盤塊讀入內(nèi)存的時間大概是24ms。所以缺頁中斷時間約為25ms。如果存儲器的平均訪問時間為100ns，于是可得：有效訪問時間=（1－p）×0.1+p×25000=0.1+24999.9p

如果希望在缺頁時，僅使有效訪問時間延長不超過10%，則可計算出缺頁率p0.1×(1+10%)0.1+24999.9p即第40頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析

由此可知，要求在2500000次的訪問中，才發(fā)生一次缺頁，即請求分頁式存儲管理應保持非常低的缺頁率，否則將使程序的執(zhí)行速度受到嚴重影響。此外，提高磁盤I/O速度，對改善請求分頁系統(tǒng)的性能至關重要。為此，應選用高速磁盤和高速磁盤接口。第41頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析例：現(xiàn)有一請求調(diào)頁系統(tǒng)，頁表保存在寄存器中。若有一個被替換的頁未被修改過，則處理一個缺頁中斷需要8ms；若被替換的頁被修改過，則處理一個缺頁中斷需要20ms。內(nèi)存存取時間為1s,訪問頁表的時間可以忽略不計。假設70%被替換的頁被修改過，為保證有效存取時間不超過2s，則可接受的最大缺頁率是多少？p*(0.7*20+0.3*8)+(1-p)*0.001<=0.002P<=1/163990.00006第42頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析“抖動”問題在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動原因：頁面淘汰算法不合理分配給進程的物理頁面數(shù)太少第43頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析駐留集

虛擬頁式存儲管理中給進程分配的物理塊的集合；駐留集大小即是這個集合的元素個數(shù)駐留集大小與系統(tǒng)效率每個進程的駐留集越小，則同時駐留內(nèi)存的進程就越多，CPU利用率越高進程的駐留集太小的話，則缺頁率高，使調(diào)頁的開銷增大進程的駐留集大小達到一定數(shù)目之后，再給它分配更多頁面，缺頁率不再明顯下降第44頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析

拐點物理塊數(shù)n缺頁率第45頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析

工作集：

1968年由Denning提出，引入工作集的目的是依據(jù)進程在過去的一段時間內(nèi)訪問的頁面來調(diào)整駐留集大小工作集定義：工作集就是進程在某段時間段Δ里實際要訪問的頁面的集合。第46頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析工作集（WorkingSet）模型

基本思想：根據(jù)程序的局部性原理，一般情況下，進程在一段時間內(nèi)總是集中訪問一些頁面，這些頁面稱為活躍頁面，如果分配給一個進程的物理頁面數(shù)太少了，使該進程所需的活躍頁面不能全部裝入內(nèi)存，則進程在運行過程中將頻繁發(fā)生中斷抖動

進程要有效地運行，其工作集必須在內(nèi)存中第47頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析

工作集：工作集就是進程在某段時間段Δ里實際要訪問的頁面的集合。具體地說，運行進程在時間t－Δ到t這個時間段內(nèi)所訪問的頁面的集合稱為該進程在時間t的工作集，記為，變量Δ稱為工作集“窗口尺寸”（WindowsSize）。通常還把工作集中所包含的頁面數(shù)稱為“工作集尺寸”，記為例：

26157775162341234443434441327||t1||t2ws(t1,△)={1,2,5,6,7}ws(t2,△)={3,4}第48頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析△大小確定如果△過大，甚至把作業(yè)地址空間全包括在內(nèi)，就成了實存管理;如果△過小，則會引起頻繁缺頁,降低了系統(tǒng)的效率。第49頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析工作集大小的變化

進程開始執(zhí)行后，隨著訪問新頁面逐步建立較穩(wěn)定的工作集。當內(nèi)存訪問的局部性區(qū)域的位置大致穩(wěn)定時，工作集大小也大致穩(wěn)定；局部性區(qū)域的位置改變時，工作集快速擴張和收縮過渡到下一個穩(wěn)定值。第50頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析利用工作集來進行駐留集調(diào)整的策略：記錄一個進程的工作集變化定期刪除駐留集中不在工作集中的頁面總是讓駐留集包含工作集（不能包含時則增大駐留集）第51頁，共81頁，2023年，2月20日，星期二8．2．5請求分頁系統(tǒng)的性能分析影響缺頁次數(shù)的因素(1)分配給進程的物理塊數(shù) 一個程序運行時遇到缺頁中斷的次數(shù)，是和分配給該道程序的物理塊數(shù)成反比的，但當主存容量達到某個值時，缺頁次數(shù)減少不再明顯。多數(shù)程序都有一個確定值——拐點(2)頁面本身的大小 頁面大，頁表小，省空間且查找快；缺頁次數(shù)相對也少；一次換頁的時間長，頁內(nèi)碎片空間浪費的可能性較大。頁面小則相反.(3)頁面置換算法(頁面淘汰算法)

選擇最合適的置換算法。(4)程序的編制方法 盡可能使編出的程序具有高度的局部性，則執(zhí)行時可經(jīng)常集中在幾個頁面上進行訪問，減少缺頁率.第52頁，共81頁，2023年，2月20日，星期二8．3請求分段式存儲管理方式

請求分段存儲管理系統(tǒng)是在分段存儲管理系統(tǒng)的基礎上實現(xiàn)的虛擬存儲器。它以段為單位進行換入換出。在程序運行之前不必調(diào)入所有的段，而只調(diào)入若干個段，便可啟動運行。當所訪問的段不在內(nèi)存時可請求操作系統(tǒng)將所缺的段調(diào)入內(nèi)存。為實現(xiàn)請求分段存儲管理，與請求分頁存儲管理類似，需要硬件的支持和相應的軟件。第53頁，共81頁，2023年，2月20日，星期二8．3．1請求分段存儲管理的基本概念

基本原理：在請求分段式存儲管理系統(tǒng)中，進程運行之前一部分段裝入內(nèi)存，另外一部分段則裝入外存。在進程運行過程中，如果所訪問的段不在內(nèi)存中，則發(fā)生缺段中斷，進入操作系統(tǒng)，由操作系統(tǒng)進行段的動態(tài)調(diào)度。段表機制：請求分段的段表是在純分段的段表機制的基礎上形成的。需在段表中增加若干項，供程序在換進換出時參考。下面所示是一請求分段系統(tǒng)中的段表：段名段長段基址存取方式訪問字段修改位存在位增補位外存地址第54頁，共81頁，2023年，2月20日，星期二8．3．1請求分段存儲管理的基本概念

存取方式：用于標識本段的存取屬性，存取屬性包括只執(zhí)行、只讀還是讀/寫；訪問字段：用于記錄該段在一段時間內(nèi)被訪問的次數(shù)，或最近已有多長時間未被訪問，供置換算法選擇段時參考；修改位：表示該段在調(diào)入內(nèi)存后是否被修改過。由于內(nèi)存中的每一段都在外存上保留一個副本，因此，若未被修改，在置換該段時就不需將該段寫回到磁盤上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該段重寫回磁盤上，以保證磁盤上所保留的始終是最新副本；第55頁，共81頁，2023年，2月20日，星期二8．3．1請求分段存儲管理的基本概念

存在位：說明本段是否已調(diào)入內(nèi)存；增補位：用于表示本段在運行過程中，是否進行過動態(tài)增長；外存地址：用于指出該段在外存上的起始地址，通常是起始物理塊號，供調(diào)入該段時使用。第56頁，共81頁，2023年，2月20日，星期二8．3．1請求分段存儲管理的基本概念

請求分段存儲管理系統(tǒng)的示意圖：200K存儲空間030K90K150K(MAIN)=020K（X）=18K（S）=310K作業(yè)空間10K0（S）=312K0（D）=28K0（X）=120K0（MAIN）=0狀態(tài)段表基址段長段號20K030K8K190K12K2150K10K3200K0010第57頁，共81頁，2023年，2月20日，星期二8．3．1請求分段存儲管理的基本概念

地址變換機構：請求分段系統(tǒng)中的地址變換機構，是在分段系統(tǒng)的地址變換機構的基礎上形成的。由于被訪問的段并非全在內(nèi)存，所以在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內(nèi)存時，必須先將所缺的段調(diào)入內(nèi)存，在修改了段表之后，才能利用段表進行地址變換。下圖給出了請求分段系統(tǒng)的地址變換過程。第58頁，共81頁，2023年，2月20日，星期二8．3．1請求分段存儲管理的基本概念

是訪問（s，w）w段表長？否越界中斷處理符合存取方式？保護中斷處理否是段s在主存？缺段中斷處理否是修改訪問字段，如果寫訪問，置修改位=1形成訪問內(nèi)存地址：（A）=內(nèi)存始址+偏移量w返回第59頁，共81頁，2023年，2月20日，星期二8．3．2分段共享與保護

分段共享：在系統(tǒng)中配置一張共享段表，所有共享段都在共享段表中占有一個表項。共享段表除具有段表中的表項外，還記錄有共享此段的每個進程的情況，其中包括：共享進程數(shù)count：記錄共享該段的進程數(shù)，只有當count為0時，才由系統(tǒng)回收該段所占存儲區(qū)；存取控制字段：記錄不同進程的不同存取權限。如對于擁有該段的進程，則允許讀和寫，而對于其它進程，則可能只允許讀，或者只允許執(zhí)行。段名段長段基址狀態(tài)外存始址共享進程計數(shù)count狀態(tài)進程名進程號段號存取控制……第60頁，共81頁，2023年，2月20日，星期二8．3．2分段共享與保護

分段保護：由于進程的每個段在邏輯上是獨立的，因而比較容易實現(xiàn)信息保護。常用的分段保護方法有越界檢查和存取控制檢查等。越界檢查：在進行存儲訪問時，首先將邏輯地址空間的段號與段表長度進行比較，如果段號等于或大于段表長度，將發(fā)出地址越界中斷信號；其次，還要檢查段內(nèi)地址是否等于或大于段長，若是等于或大于段長，將產(chǎn)生地址越界中斷信號，從而保證了每個進程只能在自己的地址空間內(nèi)運行。存取控制檢查：在段表的每個表項中，都設置了一個“存取控制”字段，用于規(guī)定該段的訪問方式。通常有只讀、只執(zhí)行和讀/寫等三種。第61頁，共81頁，2023年，2月20日，星期二練習：一個程序的段表如下表，其中存在位為0表示段在內(nèi)存，存取控制字段中W表示可寫，R表示可讀，E表示可執(zhí)行。對下面的5條指令，在執(zhí)行時會產(chǎn)生什么樣的結果？（0表示在內(nèi)存中，1表示在外存）STORER1,[0,70]STORER1,[1,20]LOADR1,[3,20]LOADR1,[3,100]JMP[2,100]段號存在位內(nèi)存始址段長存取控制01500100W10100030R203000200E30800080R41500040R缺段中斷只讀，保護性中斷合法，形成物理地址8020，將該單元內(nèi)容讀入寄存器R1中越界中斷合法，跳到3100處繼續(xù)執(zhí)行答：第62頁，共81頁，2023年，2月20日，星期二8．4Linux存儲管理

Linux操作系統(tǒng)采用虛擬存儲管理機制，即置換和請求分頁存儲管理技術。盡管Linux的存儲管理的基本原理與前面所論述的存儲管理方法是相同的，但它也有自己獨特的特點?？傮w而言，Linux的存儲管理方案非常復雜。下面就其存儲管理的主要特征進行簡單的論述。第63頁，共81頁，2023年，2月20日，星期二8．4．1Linux的內(nèi)存空間在x86平臺的Linux系統(tǒng)中，地址碼采用32位，因此每個進程的虛存空間可以達到4GB。Linux內(nèi)核將這4GB的空間分為兩部分：最高地址的1GB是系統(tǒng)空間，供內(nèi)核本身使用；而較低地址的3GB空間是用戶空間。系統(tǒng)空間由所有進程共享，而用戶空間理論上雖然可以達到3GB，但實際的用戶空間要受到物理存儲器（包括內(nèi)存和磁盤的交換空間）和用戶競爭存儲器的限制。第64頁，共81頁，2023年，2月20日，星期二8．4．2Linux的頁表機制頁表：在Linux系統(tǒng)中，頁的大小為4KB，因此每個進程的虛存空間要有1M個頁面。如果采用一級頁表描述這種映射關系，每個進程的頁表就要有1M個表項。顯然，用大量的內(nèi)存資源來存放頁表的方法是不可取的，所以，Linux采用三級頁表的方式。頁目錄（PGD）：第一級頁表為頁目錄，每個活動進程有一個頁目錄。頁目錄的大小為一頁的尺寸，頁目錄的每一項指向頁中間目錄中的一頁。每個活動進程的頁目錄都必須在內(nèi)存中。頁中間目錄（PMD）：第二級頁表為頁中間目錄。頁中間目錄可以有多個頁，頁中間目錄的每一項指向頁表中的一頁。頁表（PT）：第三級目錄為頁表。頁表也可以有多個頁，頁表中的每一項指向該進程的一個虛擬頁。

第65頁，共81頁，2023年，2月20日，星期二8．4．2Linux的頁表機制頁目錄（PGD）：第一級頁表為頁目錄，每個活動進程有一個頁目錄。頁目錄的大小為一頁的尺寸，頁目錄的每一項指向頁中間目錄中的一頁。每個活動進程的頁目錄都必須在內(nèi)存中。頁中間目錄（PMD）：第二級頁表為頁中間目錄。頁中間目錄可以有多個頁，頁中間目錄的每一項指向頁表中的一頁。第66頁，共81頁，2023年，2月20日，星期二8．4．2Linux的頁表機制地址轉(zhuǎn)換：Linux虛擬內(nèi)存的地址轉(zhuǎn)換分為四步，如下圖所示：PMD寄存器PGD下標PMD下標PT下標頁內(nèi)偏移量虛擬地址PGD……PT…物理頁面…PGD基地址++++第67頁，共81頁，2023年，2月20日，星期二8．4．2Linux的頁表機制把虛擬地址中的最高位段與寄存器中的PGD基地址相加，在PGD中找到相應的表項，該表項指向相應的PMD基地址；把虛擬地址中的第二個位段與PMD的基地址相加，在PMD中找到相應的表項，該表項指向相應的PT基地址；把虛擬地址中的第三個位段與PT的基地址相加，在PT中找到相應的表項，該表項指向相應的物理頁面；把虛擬地址中的最低位段與物理頁面的基地址相加，得到相應的物理地址。第68頁，共81頁，2023年，2月20日，星期二8．4．3Linux內(nèi)存頁的分配為了提高往內(nèi)存中讀入頁和從內(nèi)存中寫出頁的效率，Linux采用了一種機制，即把連續(xù)的頁映射到連續(xù)的物理塊中?；谶@個目的，它采用了一種伙伴系統(tǒng)。內(nèi)核維護一系列大小固定的連續(xù)物理塊組，一組可以包含1、2、4、8、16或32個物理塊。當一頁在內(nèi)存中被分配或被釋放時，可用的組使用伙伴算法被分割或合并。第69頁，共81頁，2023年，2月20日，星期二8．4．4Linux內(nèi)存頁的置換算法

Linux的頁面置換算法采用最近最少使用置換算法（NRU）。在簡單的最近最少使用置換算法中，內(nèi)存中的每一頁都有一個訪問位和一個修改位。在Linux系統(tǒng)中，用一個8位的age變量取代了訪問位。每當一頁被訪問時，age變量增1。在后臺，Linux周期性地掃描全局頁池，并將所有大于0的age變量減1。age的值為0的頁在較長一段時間內(nèi)未被訪問過，是用于置換的最佳候選頁。age的值越大，該頁最近被使用的頻率越高，從而越不適合于被置換。第70頁，共81頁，2023年，2月20日，星期二8．5Windows存儲管理

Windows有一個非常成功的虛擬存儲系統(tǒng)。有大量的Win32函數(shù)和六個內(nèi)核線程在進行存儲管理。它采用的是頁式虛擬存儲管理。第71頁，共81頁，2023年，2月20日，星期二8．5．1Windows的虛擬地址空間在Windows中，每一個用戶進程都有自己的虛擬地址空間。虛擬地址的長度是32位，因此每個進程有4GB（232B）的虛擬地址空間。低2GB為用戶地址空間，用于進程代碼和數(shù)據(jù)；高2GB為核心地址空間，它處于保護模式。其中的用戶地址空間可被用戶態(tài)和核心態(tài)線程存取，并且對每個進程都是不同的；而核心地址空間只能被核心態(tài)線程存取，并且對每個線程都是相同的。這兩個地址空間的布局如圖12．6所示。虛擬地址空間采用分頁存儲管理，每一頁的大小是固定的（Pentium是4KB）。第72頁，共81頁，2023年，2月20日，星期二8．5．1Windows的虛擬地址空間2GB04GB非頁池頁池用戶頁表棧、數(shù)據(jù)等HAL+操作系統(tǒng)用戶地址空間第73頁，共81頁，2023年，2月20日，星期二8．5．2頁面狀態(tài)