華北電力大學計算機系內(nèi)容虛擬存儲器的基本概念請求分頁存儲管理方式頁面置換算法請求分頁系統(tǒng)的性能分析請求分段存儲管理方式存儲管理舉例第六章 虛擬存儲器華北電力大學計算機系目的及要求理解并掌握虛擬存儲器的概念和特征，初步領會虛擬存儲器的實現(xiàn)方式；了解請求分頁中的硬件支持，領會并理解頁面分配和置換的策略；熟練掌握最佳置換和先進先出頁面置換算法，理解并掌握最近最久未使用置換算法，了解Clock、最少使用和頁面緩沖置換算法；了解缺頁率對優(yōu)先訪問時間的影響，領會抖動產(chǎn)生的原因和預防方法；了解請求分段中的硬件支持，領會請求分段存儲管理方式中分段共享和保護；第六章 虛擬存儲器華北電力大學計算機系重點虛擬存儲器的概念和特征；最佳置換算法、先進先出頁面置換算法、最近最久未使用置換算法；抖動產(chǎn)生的原因和預防方法；請求分段存儲管理方式中分段共享和保護；難點虛擬存儲器的概念和特征；頁面分配和置換的策略；最佳置換算法、最近最久未使用置換算法；抖動的預防方法；請求分段存儲管理方式中分段共享和保護。第六章 虛擬存儲器華北電力大學計算機系6.1.1虛擬存儲器的引入6.1.2虛擬存儲器的實現(xiàn)方式6.1.3虛擬存儲器的特征6.1虛擬存儲器的基本概念華北電力大學計算機系局部性原理 早在1968年P．Denning就指出過，程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，即在一段時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區(qū)域內(nèi)。那么程序為什么會出現(xiàn)局部性規(guī)律呢？原因可以歸結為以下幾點：程序在執(zhí)行時，除了少部分的轉移和過程調用指令外，大多數(shù)仍是順序執(zhí)行的。子程序調用將會使程序的執(zhí)行由一部分內(nèi)存區(qū)域轉至另一部分區(qū)域。但在大多數(shù)情況下，過程調用的深度都不超過5。程序中存在許多循環(huán)結構，循環(huán)體中的指令被多次執(zhí)行。程序中還包括許多對數(shù)據(jù)結構的處理，如對連續(xù)的存儲空間——數(shù)組的訪問，往往局限于很小的范圍內(nèi)。6.1.1虛擬存儲器的引入華北電力大學計算機系所以局限性表現(xiàn)為：

時間局限性 如果程序中的某條指令一旦執(zhí)行，則不久的將來該指令可能再次被執(zhí)行；如果某個存儲單元被訪問，則不久以后該存儲單元可能再次被訪問。產(chǎn)生時間局限性的典型原因是在程序中存在著大量的循環(huán)操作。

空間局限性 一旦程序訪問了某個存儲單元，則在不久的將來，其附近的存儲單元也最有可能被訪問。即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)，其典型原因是程序是順序執(zhí)行的。6.1.1虛擬存儲器的引入華北電力大學計算機系虛擬存儲器的定義 根據(jù)局部性原理，一個作業(yè)在運行之前，沒有必要把全部作業(yè)裝入內(nèi)存，而僅將那些當前要運行的那部分頁面或段，先裝入內(nèi)存便可啟動運行，其余部分暫時留在磁盤上。 程序在運行時如果它所要訪問的頁（段）已調入內(nèi)存，便可繼續(xù)執(zhí)行下去；但如果程序所要訪問的頁（段）尚未調入內(nèi)存（稱為缺頁或缺段），此時程序應利用OS所提供的請求調頁（段）功能，將它們調入內(nèi)存，以使進程能繼續(xù)執(zhí)行下去。 如果此時內(nèi)存已滿，無法再裝入新的頁（段），則還須再利用頁（段）的置換功能，將內(nèi)存中暫時不用的頁（段）調出至磁盤上，騰出足夠的內(nèi)存空間后，再將所要訪問的頁（段）調入內(nèi)存，使程序繼續(xù)執(zhí)行下去。這樣，便可使一個大的用戶程序在較小的內(nèi)存空間中運行；也可使內(nèi)存中同時裝入更多的進程并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的內(nèi)存容量，將比實際內(nèi)存容量大得多，人們把這樣的存儲器稱為虛擬存儲器。6.1.1虛擬存儲器的引入華北電力大學計算機系 虛擬存儲器是具有請求調入和置換功能，能僅把作業(yè)的一部分裝入內(nèi)存便可運行，能從邏輯上對內(nèi)存容量進行擴充的一種存儲器系統(tǒng)。 其邏輯容量由內(nèi)存和外存容量之和所決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。

可見，虛擬存儲技術是一種性能非常優(yōu)越的存儲器管理技術，故被廣泛地應用于大、中、小型機器和微型機中。6.1.1虛擬存儲器的引入華北電力大學計算機系請求分頁系統(tǒng)它是在分頁系統(tǒng)的基礎上，增加了請求調頁功能和頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。它允許只裝入若干頁（而非全部程序）的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再通過調頁功能和頁面置換功能，陸續(xù)把將要運行的頁面調入內(nèi)存，同時把暫不運行的頁面置換到外存上，置換時以頁面為單位。6.1.2虛擬存儲器的實現(xiàn)方式華北電力大學計算機系請求分段系統(tǒng)它是在分段系統(tǒng)的基礎上，增加了請求調段和分段置換功能所形成的段式虛擬存儲系統(tǒng)。它允許只裝入若干段（而非全部段）的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再通過調段功能和置換功能將不運行的段調出，同時調入將要運行的段，置換以段為單位請求段頁式系統(tǒng) 它是在段頁式系統(tǒng)的基礎上，增加了請求調頁和頁面置換功能所形成的段頁式虛擬存儲系統(tǒng)。6.1.2虛擬存儲器的實現(xiàn)方式華北電力大學計算機系離散性：指在內(nèi)存分配時采用離散的分配方式，它是虛擬存儲器的最基本的特征。多次性：指一個作業(yè)被分成多次調入內(nèi)存運行，即在作業(yè)運行時沒有必要將其全部裝入，只須將當前要運行的那部分程序和數(shù)據(jù)裝入內(nèi)存即可。對換性：指允許在作業(yè)的運行過程中在內(nèi)存和外存的對換區(qū)之間換進、換出。虛擬性：指能夠從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠大于實際內(nèi)存容量。 它是虛擬存儲器最重要的特征。6.1.3虛擬存儲器的特征華北電力大學計算機系6.2.1請求分頁中的硬件支持6.2.2頁面分配6.2.3頁面調入策略6.2請求分頁存儲管理方式華北電力大學計算機系 它是在純分頁系統(tǒng)的基礎上，增加了請求調頁功能、頁面置換功能所形成的頁式虛擬存儲系統(tǒng)，它是目前常用的一種虛擬存儲器的方式。頁表機制

它是在純分頁的頁表機制上形成的，由于只將應用程序的一部分調入內(nèi)存，還有一部分仍在磁盤上，故需在頁表中再增加若干項，供程序(數(shù)據(jù))在換進、換出時參考。在請求分頁系統(tǒng)中的每個頁表項如圖所示。6.2.1請求分頁中的硬件支持華北電力大學計算機系其中各字段說明如下：狀態(tài)位（存在位P）：用于指示該頁是否已調入內(nèi)存，供程序訪問時參考。訪問字段A：用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或最近已有多長時間未被訪問，提供給置換算法選擇換出頁面時參考。修改位M：表示該頁在調入內(nèi)存后是否被修改過。由于內(nèi)存中的每一頁都在外存上保留一份副本，因此，若未被修改，在置換該頁時就不需將該頁寫回到外存上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本。外存地址：用于指出該頁在外存上的地址，通常是物理塊號，供調入該頁時使用。6.2.1請求分頁中的硬件支持物理塊號狀態(tài)位P訪問字段A修改位M外存地址華北電力大學計算機系6.2.1請求分頁中的硬件支持缺頁中斷機構

在請求分頁系統(tǒng)中，每當所要訪問的頁面不在內(nèi)存時，便要產(chǎn)生一缺頁中斷，請求OS將所缺頁調入內(nèi)存。與一般中斷的主要區(qū)別在于：缺頁中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號。缺頁中斷返回到該指令的開始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。華北電力大學計算機系6.2.1請求分頁中的硬件支持地址變換機構 請求分頁系統(tǒng)中的地址變換機構，是在分頁系統(tǒng)的地址變換機構的基礎上，再為實現(xiàn)虛擬存儲器而增加了某些功能所形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁的功能等等，下圖給出了請求分頁系統(tǒng)的地址變換過程。華北電力大學計算機系6.2.1請求分頁中的硬件支持開始（程序請求訪問一頁)越界中斷CPU檢索快表頁表項是否在快表中？訪問頁表頁是否在內(nèi)存中？修改快表修改訪問位和修改位形成物理地址

地址變換結束保留CPU現(xiàn)場

從外存中找到缺頁

頁號>頁表長度？

內(nèi)存滿否？選擇一頁該頁是否被修改？

將該頁寫回外存

將一頁從外存換入內(nèi)存

修改頁表

Os命令CPU從外存讀缺頁

啟動I/O硬件

是否是否是否否是是否缺頁中斷處理產(chǎn)生缺頁中斷請求調頁華北電力大學計算機系最少物理塊數(shù)

在為進程分配物理塊時，首先應該考慮的問題是：能保證進程能正常運行所需的最少物理塊數(shù)（稱為最小物理塊數(shù)）。若系統(tǒng)為某進程所分配的物理塊數(shù)少于此值時，進程將無法運行，這取決于指令的格式、功能和尋址方式。頁面的分配和置換策略

在請求分頁系統(tǒng)中，可采取兩種分配策略——固定和可變分配策略。在進行置換時，也可采取兩種策略——全局置換和局部置換。于是可組合成以下三種策略。6.2.2頁面分配華北電力大學計算機系固定分配局部置換

(FixedAllocation，LocalReplacement) 它基于進程的類型（交互型或批處理型等），或根據(jù)程序員、系統(tǒng)管理員的建議，為每個進程分配一固定數(shù)目的物理塊，在整個運行期間都不再改變。如果進程在運行中發(fā)現(xiàn)缺頁，則只能從固定物理塊中選出一頁換出，然后再調入另一頁，保證分配給該進程的內(nèi)存空間不變。物理塊數(shù)目難以確定太少：缺頁中斷頻繁，吞吐量降低太多：進程數(shù)目少，資源利用率低；進程對換耗時6.2.2頁面分配華北電力大學計算機系可變分配全局置換

(VariableAllocation，GlobalReplacement)

系統(tǒng)為每個進程分配一定數(shù)目的物理塊，而OS本身也保持一個空閑物理塊隊列。當某進程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊列中，取出一物理塊分配給該進程，并將欲調入的缺頁裝入其中。當空閑物理塊隊列中的物理塊用完時，OS才能從內(nèi)存中選擇一頁調出，該頁可能是系統(tǒng)中任一進程的頁。6.2.2頁面分配華北電力大學計算機系可變分配局部置換 (VariableAllocation，LocalReplacement) 根據(jù)進程的類型或程序員的要求，為每個進程分配一定數(shù)目的內(nèi)存空間；但當某進程發(fā)生缺頁時，只允許從該進程在內(nèi)存的頁面中選出一頁換出，而不影響其它進程的運行。系統(tǒng)根據(jù)該進程運行中缺頁率的高低來增加或減少分配給該進程的物理塊。6.2.2頁面分配華北電力大學計算機系頁面分配算法

在采用固定分配策略時，可采用以下幾種物理塊分配方法平均分配算法 將系統(tǒng)中所有可供分配的物理塊，平均分配給各個進程。按比例分配算法 這是根據(jù)進程的大小按比例分配物理塊?？紤]優(yōu)先權的分配算法 該方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例分配給各進程；另一部分則根據(jù)各進程的優(yōu)先權，適當?shù)卦黾悠湎鄳蓊~后，分配給各進程。6.2.2頁面分配華北電力大學計算機系

為能使進程運行，必須事先將一部分要執(zhí)行的程序和數(shù)據(jù)調入內(nèi)存。何時調入頁面請求調頁策略 是指當進程在運行中發(fā)生缺頁時，就立即提出請求，由系統(tǒng)將缺頁調入內(nèi)存。目前的虛擬存儲器中，大多采用此策略。但這種策略在調頁時須花費較大的系統(tǒng)開銷，如需頻繁啟動磁盤I/O。預調頁策略 是一種主動的缺頁調入策略，即將那些預計在不久的將來會被訪問的程序或數(shù)據(jù)所在的頁面，預先調入內(nèi)存。6.2.3頁面調入策略華北電力大學計算機系從何處調入頁面

在虛擬存儲系統(tǒng)中，外存（硬盤）常常被分成兩部分；文件區(qū)（用于存放文件）和對換區(qū)（用于存放對換頁面）。通常，對換區(qū)的磁盤I/O速度比文件區(qū)要高。每當進程發(fā)出缺頁請求時，系統(tǒng)應從何處將缺頁調入內(nèi)存呢？系統(tǒng)擁有足夠的對換區(qū)空間，全部從對換區(qū)調入所需頁面。系統(tǒng)缺少足夠的對換區(qū)空間，不會被修改的頁面，從文件區(qū)調入，可能被修改的頁面，從對換區(qū)調入、換出。在UNIX系統(tǒng)中，對于從未運行過的頁面，都應從硬盤文件區(qū)調入；對于曾經(jīng)運行過而又被換出的頁面，可以從對換區(qū)調入；6.2.3頁面調入策略華北電力大學計算機系 在進程運行過程中，如果發(fā)生缺頁，此時內(nèi)存中又無空閑塊時，為了保證進程能正常運行，就必須從內(nèi)存中調出一頁程序或數(shù)據(jù)送磁盤的對換區(qū)。

但將哪個頁面調出，則須根據(jù)一定的頁面置換算法（PageReplacementAlgorithms）來確定。 置換算法的好壞將直接影響系統(tǒng)的性能，不適當?shù)乃惴赡軙е逻M程發(fā)生“抖動”（Thrashing)。即剛被換出的頁很快又被訪問，需重新調入，導致系統(tǒng)頻繁地更換頁面，以致一個進程在運行中把大部分時間花費在完成頁面置換的工作上，我們稱該進程發(fā)生了“抖動”。6.3頁面置換算法華北電力大學計算機系6.3.1最佳置換算法和先進先出算法6.3.2最近最久未使用LRU置換算法6.3.3

Clock置換算法6.3.4最少使用置換算法6.3.5頁面緩沖算法6.3頁面置換算法華北電力大學計算機系最佳（Optimal）置換算法

即選擇那些永不使用的，或者是在最長時間內(nèi)不再被訪問的頁面置換出去。 它是一種理想化的算法，性能最好，但在實際上難于實現(xiàn)。

但是要確定哪一個頁面是未來最長時間內(nèi)不再被訪問的，目前來說是很難估計的，所以該算法通常用來評價其它算法。6.3.1最佳置換算法和先進先出算法華北電力大學計算機系6.3.1最佳置換算法和先進先出算法例：假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串

設作業(yè)執(zhí)行中訪問頁面的總次數(shù)為A，其中有F次訪問的頁面尚未裝入主存，故產(chǎn)生了F次缺頁中斷。現(xiàn)定義缺頁中斷率為： f=F/A發(fā)生6次頁面置換，9次頁面中斷。缺頁中斷率為：

f=F/A=9/20=45%70120304230321201701777222222222222227770000004440000000111111333333331111000華北電力大學計算機系6.3.1最佳置換算法和先進先出算法先進先出（FIFO）頁面置換算法

該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。它是一種最直觀，性能最差的算法。發(fā)生了12次頁面置換，缺頁次數(shù)15次，缺頁中斷率為： f=F/A=15/20=75%

70120304230321201701777222244400000007770000333222221111100111100033333222221華北電力大學計算機系6.3.2最近最久未使用LRU置換算法LRU(LeastRecentlyUsed)算法的描述

選擇內(nèi)存中最近最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。但由于需要記錄頁面使用時間的先后關系，硬件開銷太大。發(fā)生了9次面置換，缺頁次數(shù)12次，缺頁中斷率為： f=F/A=12/20=60%70120304230321201701777222244400011111110000000033333300000111333222222222777華北電力大學計算機系6.3.2最近最久未使用LRU置換算法LRU算法的硬件支持寄存器

每個內(nèi)存頁面設置一個移位寄存器：被訪問時左邊最高位置1，定期右移并且最高位補0，于是寄存器數(shù)值最小的是最久未使用頁面。棧

把被訪問的頁面移到棧頂，于是棧底的是最久未使用頁面。70120304230321201701701203042303212017017012030423032120170701223042203312017華北電力大學計算機系

也稱最近未使用算法(NRU,NotRecentlyUsed)，它是LRU(最近最久未使用算法)和FIFO的折衷。每頁有一個使用標志位(usebit)，若該頁被訪問則置userbit=1。置換時采用一個指針，從當前指針的下一個位置開始按地址先后檢查各頁，尋找usebit=0的頁面作為被置換頁。指針經(jīng)過的userbit=1的頁都修改userbit=0，最后指針停留在被置換頁。6.3.3

Clock置換算法華北電力大學計算機系6.3.3

Clock置換算法查尋指針前進一步，指向下一個表目入口頁面訪問位=0?置頁面訪問位為0選擇該頁面淘汰返回否是華北電力大學計算機系6.3.3

Clock置換算法華北電力大學計算機系6.3.3

Clock置換算法華北電力大學計算機系 最少使用置換算法LFU（LeastFrequentlyUsed)選擇到當前時間為止被訪問次數(shù)最少的頁面被置換；每頁設置訪問計數(shù)器，每當頁面被訪問時，該頁面的訪問計數(shù)器加1；發(fā)生缺頁中斷時，淘汰計數(shù)值最小的頁面，并將所有計數(shù)清零；每個頁面設立移位寄存器：被訪問時左邊最高位置1，定期右移并且最高位補0，于是寄存器各位之和最小的是最少使用頁面。6.3.4最少使用置換算法華北電力大學計算機系 頁面緩沖算法(PageBufferingAlgorithm)是對FIFO算法的發(fā)展，通過被置換頁面的緩沖，有機會找回剛被置換的頁面； 該算法在頁面分配時，采用可變分配和局部置換的方式。 被置換頁面的選擇和處理：用FIFO算法選擇被置換頁，把被置換的頁面放入兩個鏈表之一。如果頁面未被修改，就將其歸入到空閑頁面鏈表的末尾否則將其歸入到已修改頁面鏈表。6.3.5頁面緩沖算法華北電力大學計算機系 需要調入新的物理頁面時，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一項所指的頁面，然后將第一項刪除。 空閑頁面和已修改頁面，仍停留在內(nèi)存中一段時間，如果這些頁面被再次訪問，只需較小開銷，而被訪問的頁面可以返還作為進程的內(nèi)存頁。 當已修改頁面達到一定數(shù)目后，再將它們一起調出到外存，然后將它們歸入空閑頁面鏈表，這樣能大大減少I/O操作的次數(shù)。6.3.5頁面緩沖算法華北電力大學計算機系6.4.1缺頁率對有效訪問時間的影響6.4.2工作集6.4.3抖動產(chǎn)生的原因和預防方法6.4請求分頁系統(tǒng)的性能分析華北電力大學計算機系在請求分頁系統(tǒng)中，假設存儲器的訪問時間ma為100ns（一般為10ns～幾百ns），缺頁率為p，缺頁中斷時間為25ms，則有效訪問時間就可以表示為： 有效訪問時間=（1一p）×ma十p×缺頁中斷時間

=（1一p）×0.1十p×25000=0.1十24999.9p

由上式可以看出，有效訪問時間與缺頁率成正比。 如果缺頁率為0.1%，則有效訪問時間約為25μs，與直接訪問存儲器的有效訪問時間（0.1μs）相比的時間，程序執(zhí)行的性能將受到嚴重的影響。 如果希望在缺頁時，僅使有效訪問時間延長不超過10%，則可計算出缺頁率p=0.0000004，由此得出，要求在2500000次的訪問中才發(fā)生一頁缺頁，即請求分頁方式應保持非常低的缺頁率；否則，將使程序執(zhí)行速度受到嚴重影響。6.4.1缺頁率對有效訪問時間的影響華北電力大學計算機系缺頁率 拐點

所分得的物理塊數(shù) 程序在運行中所產(chǎn)生的缺頁情況，會影響程序的運行速度及系統(tǒng)性能，而缺頁率的高低又將是與每個進程所占用的物理塊數(shù)目有關。這里我們簡單地分析一下應為每個進程分配多少個物理塊，才能把缺頁率保持在一個合理的水平上。6.4.2工作集華北電力大學計算機系 工作集的理論是在1968年由Denning提出來的。他認為，程序在運行時對頁面的訪問是不均勻的，即往往在某段時間內(nèi)的訪問僅局限于較少的若干個頁面，如果能夠預知程序在某段時間間隔內(nèi)要訪問哪些頁面，并能將它們提前調入內(nèi)存，將會大大地降低缺頁率，從而減少置換工作，提高CPU的利用率。6.4.2工作集華北電力大學計算機系

所謂工作集是指，在某段時間間隔（Δ）里，進程實際要訪問的頁面的集合。Denning認為，雖然程序只需有少量的幾頁在內(nèi)存就可以運行，但為了使程序能夠有效地運行，較少地產(chǎn)生缺頁、就必須使程序的工作集全部在內(nèi)存中。把某進程在時間t的工作集記為w（t，Δ），把變量Δ稱為工作集“窗口尺寸”（WindowsSize）。正確選擇工作集窗口（Δ）的大小，對存儲器的有效利用和系統(tǒng)吞吐量的提高，都將產(chǎn)生重要的影響。6.4.2工作集華北電力大學計算機系抖動產(chǎn)生的原因

預防方法局部置換策略引入工作集算法L=S準則掛起若干進程等6.4.3抖動產(chǎn)生的原因和預防方法CPU利用率多道程序度華北電力大學計算機系 請求分段系統(tǒng)在分段系統(tǒng)的基礎上實現(xiàn)的虛擬存儲器，是以分段為單位進行換入、換出的。在程序運行之前只要先調入若干個分段（不必調入所有的分段），便可啟動運行。當所訪問的段不在內(nèi)存時可請求OS將所缺的段調入內(nèi)存。為實現(xiàn)請求分段存儲管理方式，同樣需要一定的硬件支持和相應的軟件，有段表機制、缺段中斷機構以及地址變換機構。6.5.1請求分段中的硬件支持6.5.2分段共享與保護6.5請求分段存儲管理方式華北電力大學計算機系段表機制

在請求分段式管理中在段表中增加若干項，以供程序在調進、調出時參考。請求分段的段表項如下： 在段表項中，除了段名(號)、段長、段在內(nèi)存的起始地址外，還增加了以下幾項：存取方式：用于標識本分段的存取屬性是只執(zhí)行、只讀，還是允許讀／寫。訪問字段A：用于記錄該段被訪問的頻繁程度。修改位M：用于表示該段進入內(nèi)存后，是否已被修改過。存在位P：說明本段是否已調入內(nèi)存。增補位：用于表示本段在運行過程中，是否進行過動態(tài)增長。外存起址：指示本段在外存中的起始地址，即起始盤塊號。6.5.1請求分段中的硬件支持段段段的存取訪問修改存在增補外存名長基址方式字段A位M位P位起址華北電力大學計算機系缺段中斷機構 在請求分段系統(tǒng)中，采用的是請求調段策略。即當進程所要訪問的段未調入內(nèi)存時，便由缺段中斷機構產(chǎn)生一缺段中斷信號，由缺斷中斷處理程序將所需的段調入內(nèi)存。

缺段中斷的處理過程與缺頁中斷處理的過程類似，但比缺頁中斷更復雜。因為段長不固定，可能需要替換一個或多個段才能形成一個合適的空閑分區(qū)。 缺段中斷的處理過程如下圖：6.5.1請求分段中的硬件支持華北電力大學計算機系6.5.1請求分段中的硬件支持拼接后形成合適大小的空閑區(qū)淘汰一個或幾個段以形成合適大小的空閑區(qū)虛段不在內(nèi)存中阻塞請求的進程內(nèi)存中有合適的空閑區(qū)？從外存讀入段修改段表和內(nèi)存空閑鏈喚醒請求進程返回空閑區(qū)大小總和能否滿足？NNYY華北電力大學計算機系地址變換機構

請求分段系統(tǒng)中的地址變換機構，是在分段系統(tǒng)地址變換機構的基礎上形成的。

由于被訪問的段并非全在內(nèi)存，所以在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內(nèi)存時，必須先將所缺的段調入內(nèi)存，并修改了段表之后，才能再利用段表進行地址變換。為此，在地址變換機制中又增加了某些功能，如缺段中斷的請求及其處理等。6.5.1請求分段中的硬件支持華北電力大學計算機系

6.5.1請求分段中的硬件支持訪問[s][w]s<=段長？符合存取方式？段s在主存？修改訪問字段形成主存地址(A)=(主存始址)+(位移量w)返回分段越界中斷分段保護中斷缺段中斷是是是否否否華北電力大學計算機系 分段存儲管理方式實現(xiàn)分段的共享和保護須在每個進程的段表中，用相應的表項來指向共享段在內(nèi)存中的起始地址。為了實現(xiàn)分段共享，應配置相應的共享段表，用來對共享段進行操作。共享段表 在系統(tǒng)中，用共享段表來記錄了每一個共享段的段號和段長、內(nèi)存始址、存在位等信息，并記錄共享此分段的每個進程的情況。共享段表如下圖所示。6.5.2分段共享與保護華北電力大學計算機系其中：共享進程計數(shù)器COUNT：記錄有多少個進程需要共享該分段。存取控制字段：說明不同的進程對該分段不同的存取權限。段號：對于同一個共享段，不同的進程可以使用不同的段號去共享該段。6.5.2分段共享與保護段名段長內(nèi)存起址狀態(tài)外存起址共享進程計數(shù)器COUNT狀態(tài)進程名進程號段號存取控制華北電力大學計算機系 共享段的分配與回收共享段的分配第一個進程請求共享段為該共享段分配一物理區(qū)，把共享段調入該區(qū)，同時將該區(qū)的始址填入該進程的段表的相應項在共享段的段表中增加一個表項，填寫有關數(shù)據(jù)count置為1其它進程請求共享段已調入內(nèi)存，無需分配進程段表中加一表項，填入共享段的物理地址在共享段的段表中，填入調用進程名、存取控制等count=count+16.5.2分段共享與保護華北電力大學計算機系 共享段的分配與回收共享段的回收取消進程段表中該共享段所對應的表項count=count-1若count=0，則回收物理內(nèi)存，取消共享段表中該段的表項6.5.2分段共享與保護華北電力大學計算機系 分段保護越界檢查存取控制檢查環(huán)保護機構 處理器狀態(tài)分為多個環(huán)(ring)，分別具有不同的存儲訪問特權級別(privilege)，通常是級別高的在內(nèi)環(huán)，編號?。ㄈ?環(huán)）級別最高；一個程序可訪問同環(huán)或更低級別環(huán)的數(shù)據(jù)；一個程序可調用同環(huán)或更高級別環(huán)的服務。6.5.2分段共享與保護華北電力大學計算機系6.5.2分段共享與保護對同環(huán)或更高級別環(huán)服務的調用 對同環(huán)或更低級環(huán)數(shù)據(jù)的訪問華北電力大學計算機系6.6.1Solaris中的存儲管理6.6.2WindowsNT中的存儲管理6.6存儲管理舉例華北電力大學計算機系 由于UNIX可在多種平臺上運行，其存儲管理差異十分大。這里我們介紹Solaris2.x的存儲管理系統(tǒng)。Solaris的存儲管理系統(tǒng)分成兩部分：對換系統(tǒng)（pagingsystem） 為進程和磁盤緩存提供頁式虛擬存儲管理；內(nèi)核存儲分配器（kernelmemoryallocator） 為內(nèi)核提供內(nèi)存分配服務；6.6.1Solaris中的存儲管理華北電力大學計算機系對換系統(tǒng)對換系統(tǒng)的數(shù)據(jù)結構頁表(pagetable)：每個進程有一個頁表，進程邏輯空間的每頁對應頁表中的一個表項；頁面號(pageframenumber)：物理內(nèi)存頁面的位置；有效標志(valid)：表示該頁是否在內(nèi)存中。未訪問時間(age)：表示該頁面未被訪問的時間；長度與內(nèi)容都與處理機類型相關，不同的置換算法對該字段的使用也不同；修改標志(modify)：表示該頁面被修改過。引用標志(reference)：表示該頁面被訪問過。該標志在裝入時清0，并且會被頁置換算法周期性清0。訪問保護標志(protect)：表示該頁是否允許寫操作。寫時復制標志(copyonwrite)：多個進程共享該頁面時，設置該標志；某進程在向該頁面寫入前，必須先復制該頁后再寫入。這種做法可把復制操作延遲到寫入數(shù)據(jù)前進行，從而避免不必要的復制。6.6.1Solaris中的存儲管理華北電力大學計算機系硬盤塊描述表(diskblockdescriptor)： 該表表項與頁表表項一一對應，描述該頁在磁盤上的副本；對換設備號(swapdevicenumber)：該頁對應外存頁所在設備的邏輯設備號。該字段的使用允許在一個系統(tǒng)中使用多個對換分區(qū)。設備塊號(deviceblocknumber)：該頁對應外存頁在對換分區(qū)中的位置。存儲類型(typeofstorage)：表示該頁對應外存頁位于對換分區(qū)或可執(zhí)行文件。利用可執(zhí)行文件創(chuàng)建進程時，只有部分代碼和數(shù)據(jù)被裝入內(nèi)存；出現(xiàn)缺頁時再裝入其他部分，并在對換區(qū)中建立相應頁面副本。6.6.1Solaris中的存儲管理華北電力大學計算機系頁面表(pageframedatetable)：按物理頁面號排序，描述每個物理頁面；頁面狀態(tài)(framestate)：指示該頁面是否空閑。被占用狀態(tài)又分成：與對換分區(qū)對應、與可執(zhí)行文件對應和正在進行對換；引用計數(shù)(referencecount)：表示引用該頁的進程數(shù)目；邏輯設備號(logicaldevice)：表示包含本頁面復本的邏輯設備號；設備塊號(blocknumber)：表示頁面副本在邏輯設備上的位置；空閑頁面表項指針(pfdatapointer)：指向其他空閑頁面表項的指針；用于空閑頁面鏈表；6.6.1Solaris中的存儲管理華北電力大學計算機系對換區(qū)表(swap-usetable)：每個磁盤對換區(qū)有一個對換表，該對換區(qū)上的每個頁副本對應一個表項；引用計數(shù)(referencecount)：指向該頁的頁表表項數(shù)目；頁標識(page/storageunitnumber)：存儲單元對應的頁標識；6.6.1Solaris中的存儲管理華北電力大學計算機系6.6.1Solaris中的存儲管理雙指針輪轉置換算法

(Two-HandedClockReplacementAlgorithm)

該算法利用頁面表上的幾個指針維護一個空閑頁面表。當空閑頁面數(shù)少于一定閾值時，該算法置換一些頁面加入空閑頁面表。該算法是一種改進的輪轉算法。華北電力大學計算機系6.6.1Solaris中的存儲管理華北電力大學計算機系算法數(shù)據(jù)結構我們把頁面表視為一個環(huán)形鏈每個頁面對應一個引用位（referencebit）描述該頁面的引用情況；在頁面表上定義兩個指針前指針（fronthand）后指針（backhand）；算法操作：系統(tǒng)在訪問一個頁面時，把相應引用位置1；前指針在掃描頁面表時，把各頁面的引用位清0；后指針在掃描頁面表時，把引用位為0的頁面對換到外存，其他頁面的引用位清0；6.6.1Solaris中的存儲管理華北電力大學計算機系算法參數(shù)：OS在一定范圍內(nèi)調節(jié)兩個參數(shù)。當空閑頁較少時，加快掃描速度或縮小掃描窗口；反之，放慢掃描速度或加大掃描窗口。掃描速度（scanrate）：前后指針掃描頁面表的速度，單位為每秒掃描的頁面數(shù)；掃描窗口（handspread）：前指針與后指針間的頁面數(shù)，描述頁面引用的統(tǒng)計范圍；6.6.1Solaris中的存儲管理華北電力大學計算機系內(nèi)核存儲分配器內(nèi)核存儲分配特征內(nèi)核需要分配和釋放小內(nèi)存塊，用于內(nèi)核的數(shù)據(jù)結構和緩沖區(qū)；這些內(nèi)存塊通常比物理頁面要小許多；這些內(nèi)存塊的分配和釋放要求快速進行；分配和釋放的內(nèi)存塊的大小變化是緩慢的；這是一個分析結果。6.6.1Solaris中的存儲管理華北電力大學計算機系SVR4的惰性動態(tài)分區(qū)算法（lazybuddysystem）惰性動態(tài)分區(qū)算法：該算法是一種動態(tài)分區(qū)算法。分配的分區(qū)大小可變，但只能為2K(LKU)。釋放的分區(qū)并不馬上合并，而是維持一定數(shù)目的各種大小的空閑分區(qū)；當空閑分區(qū)超過一定數(shù)目時，才合并。該算法維護的參數(shù)：Ni表示大小為2i的分區(qū)數(shù)目；Ai表示大小為2i的已分配分區(qū)數(shù)目；Gi表示大小為2i的適合合并空閑（globallyfree）分區(qū)數(shù)目；兩個可合并成一個2i+1分區(qū)相鄰的2i分區(qū)將合并成一個；Li表示大小為2i的不適合合并空閑（locallyfree）分區(qū)數(shù)目；有如下關系：Ni=Ai+Gi+Li

合并的判斷條件：要求LiAi；依據(jù)它們的差來決定是否合并：差為0或1時進行合并，大于1時不合并。6.6.1Solaris中的存儲管理華北電力大學計算機系SVR4的惰性動態(tài)分區(qū)算法算法的實現(xiàn)

定義變量Di=Ai–Li=Ni–2Li–Gi Di的初值為0； 在分配和釋放一個大小為2i的分區(qū)時，對Di進行更新； 在分配分區(qū)時，進行的操作為：

如果有相應大小的空閑分區(qū)，選擇一個空閑分區(qū)進行分配；

如果被分配的空閑分區(qū)不適合合并， 則Di加2(即Ai加1的同時Li減1)，

否則Di加1；(即Ai加1的同時Li不變)

否則先找一個大小為2i+1的分區(qū)，把它分成兩個較小的分區(qū)；

分配其中的一個分區(qū)，另一個標記為不適合合并分區(qū)；

Di保持不變；

6.6.1Solaris中的存儲管理華北電力大學計算機系在釋放分區(qū)時，進行的操作為：按Di的大小分成三種情況分別進行處理：Di大于等于2時：標記被釋放分區(qū)為不適合合并；Di減2；(即Ai減1的同時Li加1)Di等于1時：標記被釋放分區(qū)為適合合并，進行可能的合并；Di改為0；(即Ai減1的同時LI不變)Di等于0時：標記被釋放分區(qū)為適合合并，進行可能的合并；找一個不適合合并的分區(qū)，改為適合合并，進行可能的合并；Di不變；(即Ai減1的同時LI減1)注：為了提高系統(tǒng)分配和釋放分區(qū)的速度，通常把空閑分區(qū)按大小組織成不同的雙向鏈表；每個鏈表中的分區(qū)大小都是相同的；不適合合并的分區(qū)放在隊頭，適合合并的分區(qū)放在隊尾。這樣，通常情況下分配和釋放的分區(qū)都是不適合合并的分區(qū)。6.6.1Solaris中的存儲管理華北電力大學計算機系Solaris2.4的slab分配器

slab分配器的特點：改進分配器的性能和內(nèi)存利用率；利用對象復用，優(yōu)化內(nèi)存的分配和初始化；分配器對內(nèi)核對象的操作順序：分配內(nèi)存構造(初始化)對象使用對象釋放對象釋放內(nèi)存在某些情況下，對象在釋放前又恢復到初始化后的狀態(tài)；緩存并利用對象比分配內(nèi)存并初始化要好；6.6.1Solaris中的存儲管理華北電力大學計算機系利用數(shù)據(jù)對齊，優(yōu)化高速緩存的的利用率；由于下列原因，高速緩存的某些列競爭激烈，而其余部分利用率很低；高速緩存是按區(qū)對齊，分列存放的。如IntelPentium的L1cache中每個2KB的區(qū)就分成32列。A10至A6相同的塊一定在同一列。內(nèi)核中的內(nèi)存分配大小為2的整次冪，并按相應尺寸對齊；大部分內(nèi)核對象都在對象的開始部分保存經(jīng)常訪問的數(shù)據(jù)；6.6.1Solaris中的存儲管理華北電力大學計算機系slab分配器的改進之處設置一組對象緩存，每個緩存保存一種對象類型；每個緩存分為前端和后端兩部分。前端與客戶交互，后端與頁面級分配器交互?？蛻魪木彺嬷蝎@取構造好的對象，返回用完的對象；后端與頁面級分配器交換頁面。6.6.1Solaris中的存儲管理華北電力大學計算機系通過把內(nèi)核小對象組織成內(nèi)核頁面結構，使對象的基址分布均衡，從而提高和均衡高速緩存和總線的使用率。內(nèi)核頁面結構分成：kmem_slab結構、對象集和不用空間；kmem_slab結構中記錄本塊內(nèi)的使用對象計數(shù)、塊內(nèi)空閑對象的單向鏈表和同緩存塊間的雙向鏈；對象集中記錄對象和空閑對象鏈表指針；"不用空間"的選擇可用于控制對象基址的分布；6.6.1Solaris中的存儲管理華北電力大學計算機系同一緩存中的所有內(nèi)核頁面塊構成的雙向slab鏈表中，所有對象都在使用的頁面塊排在前，部分對象在使用的頁面塊居中，空閑的頁面塊排在最后。在分配對象時，最后使用完全空閑的頁面塊；頁面級分配器回收頁面時，首先回收完全空閑的頁面塊；6.6.1Solaris中的存儲管理華北電力大學計算機系虛擬地址空間布局NT使用的頁面大小為4KB（212）。每個NT進程地址空間為4GB（232），其中：用戶存儲區(qū)：在用戶態(tài)和核心態(tài)都可訪問的用戶存儲區(qū)為2GB；用戶存儲區(qū)為頁交換區(qū)，可對換到外存；用戶存儲區(qū)的內(nèi)容包括：專用進程地址空間：用戶代碼、數(shù)據(jù)和堆棧；線程環(huán)境塊（TEB）：用戶態(tài)代碼可修改的線程控制信息；進程環(huán)境塊（PEB）：用戶態(tài)代碼可修改的進程控制信息；共享用戶數(shù)據(jù)頁：系統(tǒng)存儲區(qū)映像，為用戶態(tài)可訪問的系統(tǒng)空間，目的在于避免用戶態(tài)與核心態(tài)的頻繁切換；如：系統(tǒng)時間。6.6.2WindowsNT中的存儲管理華北電力大學計算機系系統(tǒng)存儲區(qū)：在核心態(tài)可訪問的系統(tǒng)存儲區(qū)為2GB；按交換特征，系統(tǒng)存儲區(qū)可分為：固定頁面區(qū)：永不被換出內(nèi)存的頁面；如：HAL特定的數(shù)據(jù)結構；頁交換區(qū)：非常駐內(nèi)存的系統(tǒng)代碼和數(shù)據(jù)；如：進程頁表和頁目錄；直接映射區(qū)：常駐內(nèi)存且尋址由硬件直接變換的頁面，訪問速度最快；用于存放內(nèi)核中頻繁使用且要求快速響應的代碼。6.6.2WindowsNT中的存儲管理華北電力大學計算機系6.6.2WindowsNT中的存儲管理華北電力大學計算機系x86下Windows2000的系統(tǒng)空間劃分6.6.2WindowsNT中的存儲管理華北電力大學計算機系Windows2000的內(nèi)存共享6.6.2WindowsNT中的存儲管理華北電力大學計算機系寫時復制6.6.2WindowsNT中的存儲管理華北電力大學計算機系Windows2000的地址空間擴展利用窗口映射(AWE,AddressWindowingExtensions)方法可在一個進程中使用大于2GB或3GB的物理內(nèi)存空間。使用步驟分成3步：分配物理內(nèi)存(可大于2GB)；在進程虛擬地址空間創(chuàng)建一個窗口區(qū)域(小于2GB)；把物理內(nèi)存空間的一個區(qū)域映射到窗口區(qū)域，從而可訪問在區(qū)域的內(nèi)存；6.6.2WindowsNT中的存儲管理華北電力大學計算機系6.6.2WindowsNT中的存儲管理華北電力大學計算機系地址轉換機構

NT使用2級頁表結構轉換虛擬地址，第一級稱為頁目錄（每個進程一個頁目錄），第二級稱為頁表。每個頁目錄或頁表有1024(210)個表項，每個表項為4字節(jié)。由于每個頁面為4KB，每個進程的地址空間可為4GB（210*210*212）。6.6.2WindowsNT中的存儲管理華北電力大學計算機系6.6.2WindowsNT中的存儲管理華北電力大學計算機系6.6.2WindowsNT中的存儲管理華北電力大學計算機系6.6.2WindowsNT中的存儲管理華北電力大學計算機系物理地址擴展(PAE,PhysicalAddressExtension)每個PDE和PTE表項都是8個字節(jié)，物理頁面號為24Bit，可訪問的物理地址空間可達64GB。6.6.2WindowsNT中的存儲管理華北電力大學計算機系頁面狀態(tài) WindowsNT和Windows2000的頁面有8種狀態(tài)。有效狀態(tài)(activeorvalid)：某進程正在使用該頁面，也可能不屬于任何進程(如不可對換的內(nèi)核頁面)；過渡狀態(tài)(transition)：頁面處于不屬于任何進程的過渡狀態(tài)，用于避免頁面沖突。如正在進行頁面與I/O設備間的數(shù)據(jù)傳送。清零狀態(tài)(zeroed)：空閑且已被清零；空閑狀態(tài)(free)：空閑但尚未被清零；修改狀態(tài)(modified)：已標記為無效，但對該頁面內(nèi)容的修改尚未寫入外存，可快速回到有效狀態(tài)；不保存的修改狀態(tài)(modifiedno-write)：已標記不需要寫入外存的修改狀態(tài)。如，該狀態(tài)可用于NTFS的事務交易日志狀態(tài)的記錄過程。備用狀態(tài)(standby)：已標記為無效，但可快速回到有效狀態(tài)；壞頁狀態(tài)(bad)：該頁面產(chǎn)生硬件錯，不能再用；6.6.2WindowsNT中的存儲管理華北電力大學計算機系6.6.2WindowsNT中的存儲管理華北電力大學計算機系6.6.2WindowsNT中的存儲管理華北電力大學計算機系頁面調度策略

頁面調度策略包括取頁策略、置頁策略和淘汰策略。取頁策略：NT采用按進程需要進行的請求取頁和按集群方法進行的提前取頁。集群方法是指在發(fā)生缺頁時，不僅裝入所需的頁，而且裝入該頁附近的一些頁。置頁策略：在線性存儲結構中，簡單地把裝入的頁放在未分配的物理頁面即可。淘汰策略：采用局部FIFO置換算法。在本進程范圍內(nèi)進行局部置換，利用FIFO算法把駐留時間最長的頁面淘汰出去。6.6.2WindowsNT中的存儲管理華北電力大學計算機系工作集策略

NT根據(jù)內(nèi)存負荷和進程缺頁情況自動調整工作集。進程創(chuàng)建時，指定一個最小工作集（可用SetProcessWorkingSetSize函數(shù)指定）；當內(nèi)存負荷不太大時，允許進程擁有盡可能多的頁面；系統(tǒng)通過自動調整保證內(nèi)存中有一定的空閑頁面存在；6.6.2WindowsNT中的存儲管理華北電力大學計算機系虛擬存貯管理系統(tǒng)的基礎是程序的局部性理論。此理論的基本含義是﹎﹎A﹎﹎。局部