操作系統(tǒng)課件(第五章)

操作系統(tǒng)

OperatingSystems

操作系統(tǒng)課程組南京郵電大學WINDOWSUNIXLINUXOS2VxWorksMacOS教材：《操作系統(tǒng)教程》，人民郵電出版社

，2009年出版1第五章存儲管理

5.1存儲管理中的概念5.2分區(qū)存儲管理5.3頁式存儲管理5.4式存儲管理5.5段頁式存儲管理5.6虛擬存儲管理5.7Linux系統(tǒng)存儲管理小結(jié)25.1存儲管理中的概念5.1.1存儲管理的目的和功能

5.1.2存儲分配的方式

5.1.3重定位

35.1.1存儲管理的目的和功能

1、存儲管理的目的：2、存儲管理的功能：OS為用戶使用存儲器提供方便充分發(fā)揮內(nèi)存的利用率內(nèi)存的分配與回收地址轉(zhuǎn)換信息的共享與保護內(nèi)存擴充45.1存儲管理中的概念5.1.1存儲管理的目的和功能

5.1.2存儲分配的方式

5.1.3重定位

55.1.2存儲分配的方式1、靜態(tài)分配：在生成可執(zhí)行程序的過程中進行的缺點：使得存儲管理變得很簡單，但同時也缺少靈活性，不僅不能有效地利用內(nèi)存空間，而且不支持動態(tài)數(shù)據(jù)和程序結(jié)構(gòu)，不能滿足作業(yè)動態(tài)地增長存儲空間的需求。

2、動態(tài)分配：可以根據(jù)需要動態(tài)地增加附加分配存儲空間優(yōu)點：這種分配機制支持不可預測的分配與釋放存儲區(qū)域的請求，表現(xiàn)出更大的靈活性。65.1存儲管理中的概念5.1.1存儲管理的目的和功能

5.1.2存儲分配的方式

5.1.3重定位

75.1.3重定位1、靜態(tài)靜態(tài)重定位：靜態(tài)重定位是在程序裝入后且在運行之前，一次將需要轉(zhuǎn)換的邏輯地址轉(zhuǎn)換為物理地址重定位原理

缺點是：程序的存儲空間只能是連續(xù)的一片區(qū)域，而且在重定位之后就不能移動，這不利于內(nèi)存空間的有效使用；各個用戶進程很難共享內(nèi)存中的同一程序的副本。85.1.3重定位2、動態(tài)重定位：動態(tài)重定位是在程序執(zhí)行期間每次訪問內(nèi)存之前進行重定位的。優(yōu)點：（1）程序占用的內(nèi)存空間動態(tài)可變，也不必連續(xù)存放在一起；（2）比較容易實現(xiàn)幾個進程對同一程序副本的共享使用。缺點：需要附加的硬件支持，增加了機器成本，而且實現(xiàn)存儲管理的軟件算法比較復雜。95.2分區(qū)存儲管理5.2.1固定分區(qū)

5.2.2可變分區(qū)5.2.3分配和釋放算法5.2.4分區(qū)移動技術(shù)

5.2.5覆蓋與交換技術(shù)5.2.6分區(qū)的存儲保護5.2.7分區(qū)存儲管理的主要優(yōu)缺點105.2.1固定分區(qū)

1．分區(qū)劃分

2．內(nèi)存分配3．地址轉(zhuǎn)換115.2.1固定分區(qū)1．分區(qū)劃分

固定分區(qū)（fixedpartition）存儲管理又稱定長分區(qū)或靜態(tài)分區(qū)模式，固定分區(qū)將內(nèi)存空間劃分為若干個固定大小的分區(qū)，可用下述兩種方法。（1）分區(qū)大小相等使所有的內(nèi)存分區(qū)都大小相等。缺點:當程序太小時，會造成內(nèi)存空間的浪費；當程序太大時，可能因分區(qū)的大小尚不足以裝入該程序，而使該程序無法運行。（2）分區(qū)大小不等為了克服分區(qū)大小相等分配方法的缺點，可在內(nèi)存中劃分出多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)。對于小程序，可為之分配小分區(qū)；同樣，當大、中程序到來時，就可以找到大的分區(qū)，將程序裝人內(nèi)存并運行。125.2.1固定分區(qū)2．內(nèi)存分配

為了能對內(nèi)存分區(qū)劃分和使用情況進行有效的管理，系統(tǒng)應(yīng)建立一個分區(qū)說明表，以記錄可以用于分配的分區(qū)號、分區(qū)大小、分區(qū)起始地址及狀態(tài)等。為了管理系統(tǒng)中所有作業(yè)使用內(nèi)存分區(qū)的情況，系統(tǒng)在作業(yè)表中應(yīng)有說明作業(yè)占用內(nèi)存分區(qū)的說明信息，包括作業(yè)號、作業(yè)大小、作業(yè)占用分區(qū)號等。

135.2.1固定分區(qū)3．地址轉(zhuǎn)換

固定分區(qū)存儲管理的地址轉(zhuǎn)換可以采用靜態(tài)定位方式，裝入程序在進行地址轉(zhuǎn)換時檢查其絕對地址是否落在指定的分區(qū)中，若是，則可把程序裝入，否則不能裝入，且應(yīng)歸還所分得的存儲區(qū)域。

固定分區(qū)存儲管理的地址轉(zhuǎn)換也可以采用動態(tài)定位方式，如圖。14B下限寄存器邏輯地址CPU絕對地址操作系統(tǒng)區(qū)用戶分區(qū)1用戶分區(qū)2用戶分區(qū)3B+L2上限寄存器B+L2越界中斷用戶分區(qū)4用戶分區(qū)5用戶分區(qū)6155.2分區(qū)存儲管理5.2.1固定分區(qū)

5.2.2可變分區(qū)5.2.3分配和釋放算法5.2.4分區(qū)移動技術(shù)

5.2.5覆蓋與交換技術(shù)5.2.6分區(qū)的存儲保護5.2.7分區(qū)存儲管理的主要優(yōu)缺點165.2.2可變分區(qū)下面從兩個方面分析可變分區(qū)：1．基本原理；2．地址轉(zhuǎn)換；175.2.2可變分區(qū)1．基本原理

可變分區(qū)（variablepartition）存儲管理又稱變長分區(qū)，是按作業(yè)的大小來劃分分區(qū)，但劃分的時間、大小、位置都是動態(tài)的。

圖5-6可變分區(qū)內(nèi)存分配18

可以看出，內(nèi)存中分區(qū)的數(shù)目和大小隨作業(yè)的執(zhí)行而不斷改變。為了方便內(nèi)存的分配和釋放，內(nèi)存分配表可由兩張表格組成，一張是已分配區(qū)表，另一張是未分配區(qū)表，如表5-1和表5-2所示。195.2.2可變分區(qū)2．地址轉(zhuǎn)換

又稱地址重定位、地址映射

邏輯地址（相對地址，虛地址）物理地址（絕對地址，實地址）OS205.2.2可變分區(qū)2．地址轉(zhuǎn)換

當作業(yè)占有CPU運行后，操作系統(tǒng)可把該區(qū)的開始地址和長度送入基址寄存器和限長寄存器，啟動作業(yè)執(zhí)行時由硬件根據(jù)基址寄存器進行地址轉(zhuǎn)換得到絕對地址，地址轉(zhuǎn)換如圖5-7所示。

當邏輯地址小于限長值時，則邏輯地址加基址寄存器值就可獲得絕對值地址；當邏輯地址大于限長值時，表示作業(yè)欲訪問的地址超出了所在分區(qū)的區(qū)域，這時不允許訪問，達到了保護的目的。

215.2分區(qū)存儲管理5.2.1固定分區(qū)

5.2.2可變分區(qū)5.2.3分配和釋放算法5.2.4分區(qū)移動技術(shù)

5.2.5覆蓋與交換技術(shù)5.2.6分區(qū)的存儲保護5.2.7分區(qū)存儲管理的主要優(yōu)缺點225.2.3分配和釋放算法1．分配算法2．釋放算法235.2.3分配和釋放算法1．分配算法常見的內(nèi)存分配算法有以下幾種:①首次適應(yīng)算法（firstfit）。②循環(huán)首次適應(yīng)算法（nextfit）。③最佳適應(yīng)算法（bestfit）。④最壞適應(yīng)算法（worstfit）。

OS245.2.3分配和釋放算法③

回收分區(qū)上、下鄰接空閑分區(qū)。此時應(yīng)將回收分區(qū)、上鄰接分區(qū)及下鄰接分區(qū)合并成一個連續(xù)的空閑區(qū)，合并分區(qū)的首地址為上鄰接空閑區(qū)的首地址，大小為三者之和，且應(yīng)把下鄰接空閑區(qū)從未分配區(qū)表（或空閑分區(qū)鏈）中刪去。④

回收分區(qū)不與任何空閑分區(qū)鄰接。此時應(yīng)為回收分區(qū)單獨建立一個新表項，將回收分區(qū)的起始地址及大小填入表項中，并將其加入到未分配區(qū)表（或空閑分區(qū)鏈）中?；厥辗謪^(qū)與已有空閑區(qū)的相鄰情況有4種情況:①回收分區(qū)上鄰接一個空閑分區(qū)。此時應(yīng)將回收分區(qū)與上鄰接分區(qū)合并成一個連續(xù)的空閑區(qū)。合并分區(qū)的首地址為上鄰接空閑區(qū)的首地址，大小為二者之和。②回收分區(qū)下鄰接一個空閑分區(qū)。此時應(yīng)將回收分區(qū)與下鄰接分區(qū)合并成一個連續(xù)的空閑區(qū)，合并分區(qū)的首地址為回收分區(qū)的首地址，大小為二者之和。2．釋放算法255.2分區(qū)存儲管理5.2.1固定分區(qū)

5.2.2可變分區(qū)5.2.3分配和釋放算法5.2.4分區(qū)移動技術(shù)

5.2.5覆蓋與交換技術(shù)5.2.6分區(qū)的存儲保護5.2.7分區(qū)存儲管理的主要優(yōu)缺點265.2.4分區(qū)移動技術(shù)

移動技術(shù)的示例如下圖所示

275.2分區(qū)存儲管理5.2.1固定分區(qū)

5.2.2可變分區(qū)5.2.3分配和釋放算法5.2.4分區(qū)移動技術(shù)

5.2.5覆蓋與交換技術(shù)5.2.6分區(qū)的存儲保護5.2.7分區(qū)存儲管理的主要優(yōu)缺點285.2.5覆蓋與交換技術(shù)1．覆蓋2．交換技術(shù)

295.2.5覆蓋與交換技術(shù)1．覆蓋覆蓋技術(shù)要求編程人員提供一個清楚的覆蓋結(jié)構(gòu)，即程序員要把一個程序劃分成不同的程序段，并規(guī)定程序段的執(zhí)行和覆蓋順序。操作系統(tǒng)根據(jù)程序員提供的覆蓋結(jié)構(gòu)，完成程序段之間的覆蓋。引入覆蓋技術(shù)的目的是使在較小的可用內(nèi)存空間上運行較大的。程序成為可能，該技術(shù)常與分區(qū)存儲管理技術(shù)配合使用305.2.5覆蓋與交換技術(shù)1．覆蓋

如某進程的程序正文由A，B，C，D，E和F等6個程序段組成。它們之間的調(diào)用關(guān)系如圖5-10（a）所示。程序段A只調(diào)用程序段B和C，程序段B調(diào)用D，程序段C調(diào)用E和F。因此，程序段B和C就無需同時在內(nèi)存中，程序段E和F也無需同時在內(nèi)存中。進程可按如圖5-10（b）所示的方式分配程序段。進程正文段所需要的內(nèi)存空間是：A+B+C+D+E+F=200（KB）。而采用了覆蓋技術(shù)后，只需要100KB內(nèi)存空間就行了。315.2.5覆蓋與交換技術(shù)1．覆蓋

325.2.5覆蓋與交換技術(shù)1．覆蓋

覆蓋技術(shù)的優(yōu)點是：①由于執(zhí)行前裝入的數(shù)據(jù)和程序變少，程序的裝入加快；②不需操作系統(tǒng)額外的硬件支持，只需增加一些I/O操作。覆蓋技術(shù)的缺點是：①編程人員必須設(shè)計和編寫正確的覆蓋結(jié)構(gòu)，必須劃分程序模塊并確定程序模塊間的覆蓋關(guān)系，編程復雜度增加；②必須有重定位算法和鏈接程序支持覆蓋驅(qū)動程序讀入代碼的過程；③覆蓋技術(shù)是通過程序執(zhí)行時間的延長來換取空間的節(jié)省?；谶@些缺點，覆蓋技術(shù)的使用并不是很廣泛，但當缺乏對先進技術(shù)的硬件支持時，采用這種策略比較有效335.2.5覆蓋與交換技術(shù)2．交換技術(shù)

交換技術(shù)（Swapping），也稱為對換或滾入/滾出（roll-in/roll-out），是指把內(nèi)存中暫時不能運行的進程或暫時不用的程序和數(shù)據(jù)，換出到外存，以騰出足夠的內(nèi)存空間，把已具備運行條件的進程，或進程所需要的程序和數(shù)據(jù)，換入內(nèi)存運行。

345.2.5覆蓋與交換技術(shù)2．交換技術(shù)

按交換單位的不同，可分為整體交換和部分交換。

1.整體交換也稱為進程交換，是指交換整個進程，這是為解決內(nèi)存緊張問題提出的，也可進一步提高內(nèi)存利用率。2.部分交換指交換以“頁”或“段”為單位進行，可分別稱為“頁面交換”和“分段交換”，這是在虛存的請求分頁和請求分段存儲管理基礎(chǔ)上提出的技術(shù)。355.2.5覆蓋與交換技術(shù)2．交換技術(shù)與覆蓋技術(shù)相比:1.交換技術(shù)不要求編程人員給出程序段之間的覆蓋結(jié)構(gòu)，它主要是在進程或作業(yè)之間進行，而覆蓋技術(shù)則主要是在同一個進程或作業(yè)之間進行。2.交換技術(shù)的運用，可以在較小的存儲空間中運行較多的作業(yè)或進程，覆蓋技術(shù)的運用，可以在較小的存儲空間中運行比其容量大的作業(yè)或進程。365.2.5覆蓋與交換技術(shù)2．交換技術(shù)

交換技術(shù)常與分區(qū)存儲管理配合使用,其:

優(yōu)點:是可以增加并發(fā)運行的程序數(shù)目，并給用戶提供了適當?shù)捻憫?yīng)時間

缺點:上下文切換的開銷非常大，沒有考慮程序執(zhí)行過程中地址訪問的統(tǒng)計特性，而且在交換過程中需考慮程序換入時的重定位問題和交換中傳送信息量多少的問題。375.2分區(qū)存儲管理5.2.1固定分區(qū)

5.2.2可變分區(qū)5.2.3分配和釋放算法5.2.4分區(qū)移動技術(shù)

5.2.5覆蓋與交換技術(shù)5.2.6分區(qū)的存儲保護5.2.7分區(qū)存儲管理的主要優(yōu)缺點385.2.6分區(qū)的存儲保護1．界限寄存器方式2．保護鍵方式

395.2.6分區(qū)的存儲保護1．界限寄存器方式

界限寄存器方式可以采用上下界寄存器和基址、限長寄存器兩種方式實現(xiàn)存儲保護。界限寄存器保護法是一種常用的硬件保護法。在上下界存儲保護技術(shù)中要求為每個進程設(shè)置一對上下界寄存器。上下界寄存器中裝有被保護程序和數(shù)據(jù)段的起始地址和終止地址。在程序執(zhí)行過程中，在對內(nèi)存進行訪問操作時首先進行訪址合法性檢查，即檢查經(jīng)過重定位后的內(nèi)存地址是否在上下界寄存器所規(guī)定的范圍之內(nèi)，如在該范圍內(nèi)，則訪問是合法的；否則是非法的，并產(chǎn)生訪址越界中斷。

405.2.6分區(qū)的存儲保護2．保護鍵方式

保護鍵方式為每一個被保護存儲塊分配一個單獨的保護鍵，它相當于一把鎖。在程序狀態(tài)字中則設(shè)置相應(yīng)的保護鍵開關(guān)字段，它相當于一把鑰匙，對不同的進程賦予不同的開關(guān)代碼以和被保護的存儲塊中的保護鍵匹配。當作業(yè)運行時，檢查鑰匙和鎖是否一致，如果二者不匹配表示不允許對存儲區(qū)域訪問，則系統(tǒng)發(fā)出保護性中斷信號。保護鍵可設(shè)置成對讀寫同時保護的，或只對讀、寫進行單項保護的。415.2分區(qū)存儲管理5.2.1固定分區(qū)

5.2.2可變分區(qū)5.2.3分配和釋放算法5.2.4分區(qū)移動技術(shù)

5.2.5覆蓋與交換技術(shù)5.2.6分區(qū)的存儲保護5.2.7分區(qū)存儲管理的主要優(yōu)缺點425.2.7分區(qū)存儲管理的主要優(yōu)缺點分區(qū)存儲管理的主要優(yōu)點：①實現(xiàn)了多道程序設(shè)計，從而提高了系統(tǒng)資源的利用率；②分區(qū)管理要求的硬件支持少，管理算法簡單,因而容易實現(xiàn)。分區(qū)存儲管理的主要缺點：①內(nèi)存利用率仍然不高，因為分區(qū)管理要求用戶作業(yè)必須裝入到內(nèi)存連續(xù)的存儲空間中，當系統(tǒng)空閑區(qū)的長度小于用戶要求時就無法分配；②無法實現(xiàn)虛擬存儲，內(nèi)存擴充只能采用覆蓋與交換技術(shù)；③難以實現(xiàn)各分區(qū)的信息共享。

435.3頁式存儲管理5.3.1頁式基本原理5.3.2頁式管理表5.3.3頁式地址轉(zhuǎn)換5.3.4快表

5.3.5頁面分配策略5.3.6頁面的共享與保護5.3.7多級頁表5.3.8反置頁表445.3.1頁式基本原理

①頁框：把內(nèi)存空間劃分成大小相等的若干存儲區(qū)域，每個區(qū)稱為一塊，又稱頁框。從0開始連續(xù)編號。②頁面：程序邏輯地址空間按頁框大小分為若干片，不足一頁的部分補齊為一頁，依序從0、1……編號，稱為頁面，每個區(qū)稱一個頁面，又稱頁；③邏輯地址形式：與此對應(yīng)，分頁存儲器的邏輯地址由兩部分組成，即頁號和頁內(nèi)地址。邏輯地址格式如下圖所示。455.3.1頁式基本原理

將物理內(nèi)存劃分成頁框的特點是：

分頁是為了管理，物理內(nèi)存沒有按用戶作業(yè)分區(qū)的概念，分頁僅僅是為了信息管理構(gòu)造用，為了便于提高工作效率；用戶不可見，物理內(nèi)存沒有真正隔離，一頁中的地址必須連續(xù)；分頁是一種物理劃分而不是邏輯劃分單位。OS465.3.1頁式基本原理

將用戶邏輯地址空間分成頁面的特點：

用戶可用地址大小受物理地址大小以及地址總線的限制；

虛頁號可大于實頁號；

最后一頁經(jīng)常不滿，從概率來看有半頁浪費，因為可能遇到只有一個字節(jié)也要占一頁。

OS475.3.1頁式基本原理

頁面與頁框?qū)?yīng)關(guān)系如下圖所示

485.3頁式存儲管理5.3.1頁式基本原理5.3.2頁式管理表5.3.3頁式地址轉(zhuǎn)換5.3.4快表

5.3.5頁面分配策略5.3.6頁面的共享與保護5.3.7多級頁表5.3.8反置頁表495.3.2頁式管理表1．頁表

2．請求表3．存儲頁面表

OS505.3.2頁式管理表1．頁表在頁表中每頁有相應(yīng)的表目，它們分別指出該頁在內(nèi)存中的頁框號，如表5-3所示。頁表是在進程裝入內(nèi)存時，由系統(tǒng)根據(jù)內(nèi)存分配情況建立的。在多道程序系統(tǒng)中，為了便于管理和保護，系統(tǒng)為每個裝入內(nèi)存的進程建立一張相應(yīng)的頁表。

頁

面

號頁

框

號031628515.3.2頁式管理表2．請求表請求表用來確定進程的地址空間的各頁在內(nèi)存中的實際位置關(guān)系。為了完成這個任務(wù)，系統(tǒng)必須知道每個進程的頁表起始地址和長度，以進行內(nèi)存分配和地址變換。另外，請求表中還應(yīng)包括每個進程所要求的頁面數(shù)。請求表整個系統(tǒng)一張，如表5-4所示。

進

程

號請求頁面數(shù)頁

表

始

址頁

表

長

度狀

態(tài)120102420已分配234104434已分配525.3.2頁式管理表3．存儲頁面表

存儲頁面表是整個系統(tǒng)一張，存儲頁面表指出內(nèi)存各頁面是否已被分配出去，以及未分配頁面的總數(shù)。存儲頁面表有兩種構(gòu)成方法：位示圖和空閑頁面鏈。

位示圖方法是在內(nèi)存中劃分一塊固定存儲區(qū)域，每個內(nèi)存單元的每個比特代表一個頁面。如果該頁面已被分配，則對應(yīng)比特位置1，否則置0。這種方法稱為位示圖法。位示圖的例子如圖5-13所示。

535.3頁式存儲管理5.3.1頁式基本原理5.3.2頁式管理表5.3.3頁式地址轉(zhuǎn)換5.3.4快表

5.3.5頁面分配策略5.3.6頁面的共享與保護5.3.7多級頁表5.3.8反置頁表545.3.3頁式地址轉(zhuǎn)換物理地址=頁框號×頁長+頁內(nèi)地址。

555.3頁式存儲管理5.3.1頁式基本原理5.3.2頁式管理表5.3.3頁式地址轉(zhuǎn)換5.3.4快表

5.3.5頁面分配策略5.3.6頁面的共享與保護5.3.7多級頁表5.3.8反置頁表565.3.4快表

具有快表的地址變換過程是如下:①

讀出CPU給出的有效邏輯地址，分成頁號和頁內(nèi)地址，由地址變換機構(gòu)自動將頁號與快表中的頁號比較，這種比較是同時進行的。②

若其中有相匹配的頁號，表示快表存在所要訪問的頁表項，直接讀出對應(yīng)的頁框號，送物理地址寄存器形成物理地址。③

若在快表中未找到對應(yīng)的頁表項，則訪問內(nèi)存中的頁表，找到頁框號送地址寄存器形成物理地址；同時，將此頁表項存入快表中的一個寄存器單元中，即修改快表。④

若快表已滿，則系統(tǒng)根據(jù)某種算法找到一個不再需要的頁表項換出。

575.3頁式存儲管理5.3.1頁式基本原理5.3.2頁式管理表5.3.3頁式地址轉(zhuǎn)換5.3.4快表

5.3.5頁面分配策略5.3.6頁面的共享與保護5.3.7多級頁表5.3.8反置頁表585.3.5頁面分配策略頁式存儲管理把內(nèi)存的可分配區(qū)域按頁面大小分成若干頁框，內(nèi)存分配以頁框為單位。存儲管理采用位示圖或空閑頁面鏈方法記錄空閑區(qū)域。頁式存儲管理分配算法如圖：595.3頁式存儲管理5.3.1頁式基本原理5.3.2頁式管理表5.3.3頁式地址轉(zhuǎn)換5.3.4快表

5.3.5頁面分配策略5.3.6頁面的共享與保護5.3.7多級頁表5.3.8反置頁表605.3.6頁面的共享與保護1．頁面共享

2．頁面的保護機制

OS615.3.6頁面的共享與保護1．頁面共享

實現(xiàn)頁面共享引起的主要問題是：當共享頁從內(nèi)存中淘汰或被重新裝入內(nèi)存時，共享此頁的所有進程頁表中的相應(yīng)“頁面存在”位都必須更新

625.3.6頁面的共享與保護1．頁面共享具體實現(xiàn)時可采用如下技術(shù):①

把共享某一頁的所有作業(yè)之頁表的相應(yīng)表目鏈在一起。當該頁需要交換時，沿著這個鏈掃描所有的頁表，尋找和更新相應(yīng)頁表的表目。②

為了便于共享，減少開銷，把正在被共享的頁“鎖”在內(nèi)存中。為此，在頁表的表目中增加一個“引用計數(shù)”（其初值為“0”）。當一個進程要使用共享頁時，使相應(yīng)的引用計數(shù)加1；若共享此頁的一個進程撤離時，則引用計數(shù)減1。當系統(tǒng)要求置換內(nèi)存中的頁面時，凡是其引用計數(shù)值大于或等于2的頁面不予調(diào)出。③

為了減少共享頁面之進程頁表的更新操作，可為那些被共享的頁面獨立設(shè)置一張頁表——公共頁表，如圖5-17所示。當某個被共享的頁面與輔存之間交換時，只需對這個“公共”頁表的表目加以更新，至于有共享頁面的進程之頁表，其相應(yīng)表目設(shè)有一指針，指向該頁在公共頁表中的表目即可。

63

實現(xiàn)頁面共享，必須使共享的頁面具有相同的頁號，或者要在地址之間重疊，這將帶來麻煩，因此，分頁不利于共享。這可以在段式存儲管理中得到改進。

645.3.6頁面的共享與保護2．頁面的保護機制

實現(xiàn)信息共享引起的另一個問題是：要求提供附加的保護措施，對共享信息加以必要的保護。通常的辦法是在頁表中增加一些標志位，用來指出該頁的信息可讀/寫、只讀、只可執(zhí)行及不可訪問等，指令執(zhí)行時進行核對此信息。例如，要想向只讀塊寫入信息則指令停止執(zhí)行，產(chǎn)生中斷信號。另外，也可采取存儲保護鍵作為保護機制，系統(tǒng)為每個進程分配一個存儲保護鍵，為某進程分配內(nèi)存時根據(jù)它分得的保護鍵，由系統(tǒng)為它寫到分配的頁框保護鍵中。程序執(zhí)行時將程序狀態(tài)字PSW中的控制鍵和訪問頁的存儲保護鍵進行核對，相符時才可訪問該塊，用這種辦法來實現(xiàn)存儲保護。655.3頁式存儲管理5.3.1頁式基本原理5.3.2頁式管理表5.3.3頁式地址轉(zhuǎn)換5.3.4快表

5.3.5頁面分配策略5.3.6頁面的共享與保護5.3.7多級頁表5.3.8反置頁表665.3.7多級頁表每個進程建一張頁目錄表，它的每個表項指出一個頁表頁，頁表頁的長度被限制成等于一頁，而頁表頁的每個表項給出了頁面和頁框的對應(yīng)關(guān)系，頁目錄表是一級頁表，頁表頁是二級頁表，共同構(gòu)成了二級頁表機制。二級頁表實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換過程如圖：675.3頁式存儲管理5.3.1頁式基本原理5.3.2頁式管理表5.3.3頁式地址轉(zhuǎn)換5.3.4快表

5.3.5頁面分配策略5.3.6頁面的共享與保護5.3.7多級頁表5.3.8反置頁表685.3.8反置頁表在反置頁表中，為每個頁框設(shè)置一個頁表項，并按頁框號排序，反置頁表中的內(nèi)容是正在訪問該頁框的進程標識、頁號及特征位，和哈希鏈指針等。695.4段式存儲管理5.4.1段式基本原理5.4.2段式地址轉(zhuǎn)換5.4.3內(nèi)存分配與釋放5.4.4段的共享與保護5.4.5段式和頁式的比較705.4.1段式基本原理段式存儲管理將進程對應(yīng)程序和數(shù)據(jù)按照其本身的特性分成若干個段，每個段定義了一組有意義的邏輯信息單位，程序的分段結(jié)構(gòu)如圖：

715.4.1段式基本原理實現(xiàn)步驟:①

將作業(yè)的地址空間劃分為若干個段，每個段定義一組邏輯信息。如主程序段、子程序段、數(shù)據(jù)段及工作區(qū)段等，每個段設(shè)置段名，并從0連續(xù)編號，0，1，2，…。②分段裝入程序，并為每個分段分配段號。③

系統(tǒng)以段為單位分配內(nèi)存，每一段分配連續(xù)的分區(qū)，段表保存進程的各段進入內(nèi)存后的情況，設(shè)置段表地址寄存器，保存當前執(zhí)行進程段表的起始地址和長度。

725.4段式存儲管理5.4.1段式基本原理5.4.2段式地址轉(zhuǎn)換5.4.3內(nèi)存分配與釋放5.4.4段的共享與保護5.4.5段式和頁式的比較735.4.2段式地址轉(zhuǎn)換為使程序能正常運行，亦即能從物理內(nèi)存中找出每個邏輯段所對應(yīng)的位置，存儲管理為每個進程建立一張段映射表，稱之為段表。

段

號段

始

址段

長

度0

1

2

745.4.2段式地址轉(zhuǎn)換類似于頁式存儲管理那樣，段式存儲管理也設(shè)置一個段表控制寄存器，用來存放當前占用處理器進程的段表始址和長度。段式存儲管理的地址轉(zhuǎn)換和存儲保護流程如圖：755.4.2段式地址轉(zhuǎn)換段式存儲管理與頁式存儲管理相同，段表存放在內(nèi)存，每訪問一次數(shù)據(jù)，都必須訪問兩次內(nèi)存，從而成倍地降低了處理速率。解決方法和頁式系統(tǒng)類似，增設(shè)相聯(lián)存儲器，用于保存最近常用的段表項。一般情況下，段表項數(shù)目比頁表項數(shù)目少，其所需的相聯(lián)存儲器也相對較小，因此可以顯著地減少存取數(shù)據(jù)的時間。765.4段式存儲管理5.4.1段式基本原理5.4.2段式地址轉(zhuǎn)換5.4.3內(nèi)存分配與釋放5.4.4段的共享與保護5.4.5段式和頁式的比較775.4.3內(nèi)存分配與釋放段式管理中以段為單位分配內(nèi)存，每段分配一個連續(xù)的內(nèi)存區(qū)。由于各段長度不等，所以這些存儲區(qū)的大小不一。而且，同一進程所包含的各段之間不要求連續(xù)。段式管理的內(nèi)存分配與釋放在進程的執(zhí)行過程中動態(tài)進行。事實上，我們可以采用和動態(tài)分區(qū)管理相同的空閑區(qū)管理方法。即把內(nèi)存各空閑區(qū)按物理地址從低到高排列，或按空閑區(qū)大小從小到大或從大到小排列。分區(qū)管理中所用的幾種分配算法：首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法都可用來進行空閑區(qū)分配。當然，分區(qū)管理時用到的內(nèi)存釋放方法也可以在段式管理中使用。785.4段式存儲管理5.4.1段式基本原理5.4.2段式地址轉(zhuǎn)換5.4.3內(nèi)存分配與釋放5.4.4段的共享與保護5.4.5段式和頁式的比較795.4.4段的共享與保護1．共享段表2．段的保護OS805.4.4段的共享與保護

1．共享段表①段表信息，即共享段的信息，包括段名、段長、內(nèi)存始址、狀態(tài)、外存始址等信息。②共享進程計數(shù)，用于描述多少個進程同時共享該共享段。當某進程不再需要共享時，系統(tǒng)將計數(shù)值減1，只有共享進程計數(shù)值為0，系統(tǒng)才回收該段所占內(nèi)存空間。③存取控制字段，用于描述不同進程對該共享段的存取權(quán)限。④進程信息，即共享該段的進程的信息，包括進程名和進程號。⑤段號，用于描述不同進程共享該段的段號。

815.4.4

段的共享與保護

2．段的保護①越界檢查，段表寄存器中存放段表長度信息，每個段表項包含段長字段，在邏輯地址轉(zhuǎn)換為物理地址時需經(jīng)過兩步檢查：第一步，判斷段號是否越界，第二步，判斷段內(nèi)偏移量是否越界，從而保證每個進程只能在自己的地址空間中運行。②存取控制檢查，段表的每個表項中設(shè)置了存取控制字段，用于規(guī)定對該段的訪問方式，包括只讀、只執(zhí)行和讀/寫權(quán)限。這樣可以保證不同權(quán)限的進程對段的正確使用，以及信息的安全性。特別是對于共享段，該字段顯得尤為重要。③環(huán)保護機制825.4段式存儲管理5.4.1段式基本原理5.4.2段式地址轉(zhuǎn)換5.4.3內(nèi)存分配與釋放5.4.4段的共享與保護5.4.5段式和頁式的比較835.4.5段式和頁式的比較共同點:兩者都采用離散分配方式區(qū)別:①頁是信息的物理單位，頁式管理是為實現(xiàn)離散分配方式，以減少內(nèi)存的外碎片，提高內(nèi)存的利用率，或者說，頁式管理是出于系統(tǒng)管理的需要。而段是信息的邏輯單位，含有一組意義相對完整的信息，段式管理的目的是為了能更好地滿足用戶的需要。②頁的大小固定且由系統(tǒng)確定，邏輯地址由頁號和頁內(nèi)地址組成，可由機器硬件實現(xiàn)。段長不固定，取決于用戶所編寫的程序，通常由編譯程序在對源程序進行編譯時，根據(jù)信息的性質(zhì)來劃分。③頁式管理中，進程地址空間是一維的，是單一的線性地址空間。

845.5段頁式存儲管理5.5.1段頁式基本原理5.5.2段頁式地址轉(zhuǎn)換OS855.5.1段頁式基本原理①

虛地址以程序的邏輯結(jié)構(gòu)劃分成段，這是段頁式存儲管理的段式特征。②

實地址劃分成位置固定、大小相等的頁框（塊），這是段頁式存儲管理的頁式特征。③

將每一段的線性地址空間劃分成與頁框大小相等的頁面，于是形成了段頁式存儲管理的特征。865.5.1段頁式基本原理段頁式系統(tǒng)的基本原理是段式和頁式原理的組合。這種方法的基本思想是，用分段方法來分配和管理地址空間，用分頁方法來分配和管理存儲空間。具體如圖：875.5段頁式存儲管理5.5.1段頁式基本原理5.5.2段頁式地址轉(zhuǎn)換OS885.5.2段頁式地址轉(zhuǎn)換地址變換過程如下。①

由控制寄存器得到該進程的段表在內(nèi)存中存放的起始地址。②

由邏輯地址給出的段號和控制寄存器中的段表長度相比較，以確定其訪問的有效性，并以索引查找段表。校驗該段的存取控制方式，以確保本次存儲訪問的正確性。得出該段所對應(yīng)的頁表在內(nèi)存中存放的起始地址。③

由邏輯地址中的頁號與該段頁表長度相比較，以確保其訪問的有效性，以索引查找頁表，其后處理同頁式處理過程一樣。895.5.2段頁式地址轉(zhuǎn)換下圖給出了段頁式存儲管理中的地址轉(zhuǎn)換過程。從地址轉(zhuǎn)換過程中可以看到，要對內(nèi)存中指令或數(shù)據(jù)進行一次存取的話，至少要訪問三次以上的內(nèi)存。

905.6虛擬存儲管理5.6.1相關(guān)基本概念5.6.2請求頁式存儲管理5.6.3頁面置換算法5.6.4請求頁式管理性能分析

5.6.5請求段式存儲管理5.6.6請求段頁式存儲管理915.6.1相關(guān)基本概念1．程序訪問局部性原理2．虛擬存儲器3．虛擬存儲器的特征4．虛擬存儲器的實現(xiàn)方法OS925.6.1相關(guān)基本概念1．程序訪問局部性原理①

時間局部性。由于程序存在循環(huán)結(jié)構(gòu)、臨時變量和子程序調(diào)用，如果某條指令被執(zhí)行或某個數(shù)據(jù)結(jié)構(gòu)被訪問，則在不久的一段時間內(nèi)該指令可能再次執(zhí)行，該數(shù)據(jù)結(jié)構(gòu)可能再次被訪問。②空間局部性。若某個存儲單元被訪問，則在不久之后，其附近的存儲單元也可能被訪問。即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍內(nèi)。③順序局部性。通常情況下，CPU跟蹤程序的執(zhí)行是按照在內(nèi)存中的連續(xù)地址進行的。只有在遇到轉(zhuǎn)移指令時，才會跳轉(zhuǎn)到一個不連續(xù)的地址空間，但跳轉(zhuǎn)到新的地址空間后，指令又是順序執(zhí)行。935.6.1相關(guān)基本概念2．虛擬存儲器

虛擬存儲器（virtualmemory），就是用戶對待作為可編址內(nèi)存的存儲空間，是由操作系統(tǒng)提供的一個假想的存儲器，它不是實際的內(nèi)存，而是操作系統(tǒng)對物理內(nèi)存的邏輯擴充。OS945.6.1相關(guān)基本概念3．虛擬存儲器的特征4個基本特征：離散性、多次性、對換性和虛擬性；4．虛擬存儲器的實現(xiàn)方法①請求頁式存儲管理。②請求段式存儲管理。③請求段頁式存儲管理。

955.6虛擬存儲管理5.6.1相關(guān)基本概念5.6.2請求頁式存儲管理5.6.3頁面置換算法5.6.4請求頁式管理性能分析

5.6.5請求段式存儲管理5.6.6請求段頁式存儲管理965.6.2

請求頁式存儲管理1．實現(xiàn)的基本原理2．地址轉(zhuǎn)換3．頁面調(diào)入策略和清除策略4．頁面分配策略975.6.2請求頁式存儲管理1．實現(xiàn)的基本原理實現(xiàn)一個頁式的虛擬存儲系統(tǒng)，需要解決下面三個具體問題:①

系統(tǒng)如何獲知進程當前所需頁面不在內(nèi)存中。②

當發(fā)現(xiàn)缺頁時，如何把所缺頁面調(diào)入內(nèi)存。③

當內(nèi)存中沒有空閑頁面時，為了接收一個新頁，需要把老的淘汰出去，這又根據(jù)什么策略選擇淘汰頁面。985.6.2請求頁式存儲管理1．實現(xiàn)的基本原理擴充后的頁表表項結(jié)構(gòu):995.6.2請求頁式存儲管理1．實現(xiàn)的基本原理擴充后頁表項的用途如下:①頁號和頁框號。其作用與頁式存儲管理相同，是地址轉(zhuǎn)換所必須的。②中斷位，或稱狀態(tài)位。用于指示頁是否在內(nèi)存中。每當進程內(nèi)存訪問時，根據(jù)該位判斷要訪問的頁面是否在內(nèi)存，若不在內(nèi)存中，則產(chǎn)生缺頁中斷。③訪問位。用于記錄該頁在一段時間內(nèi)被訪問的次數(shù)，或記錄最近已經(jīng)有多長時間未被訪問，提供給置換算法在選擇換出頁面時參考。④修改位。表示該頁在調(diào)入內(nèi)存后是否被修改過。當CPU以寫的方式訪問頁面時，設(shè)置該頁的修改位，在置換該頁時必須將該頁重寫到外存上，以保證外存中所保留的始終是最新副本；若沒修改，則在置換時不需將該頁寫回外存，從而減少系統(tǒng)的開銷和啟動磁盤的次數(shù)。⑤外存地址。用于指出該頁在外存上的地址，供調(diào)入該頁時使用。1005.6.2請求頁式存儲管理①存儲管理單元接受CPU傳送過來的邏輯地址并自動按頁面大小把邏輯地址從某位起分解成兩部分：頁號和頁內(nèi)地址；②以頁號為索引搜索快表；③如果在快表中命中，立即送出頁框號，并與頁內(nèi)地址拼接成物理地址，然后，進行權(quán)限檢查，如獲通過進程就可以訪問物理地址了；④如果在快表中不命中，以頁號為索引搜索進程頁表，頁表的始址由硬件頁表控制寄存器指出；⑤如果在頁表中找到此頁面，說明訪問頁面己在內(nèi)存，那么，可送出頁框號，并與頁內(nèi)地址拼接成物理地址，然后，進行權(quán)限檢查，如獲通過進程就可以訪問物理地址了；2．地址轉(zhuǎn)換，過程如下：⑥同時要把這個頁面的信息裝入快表，以備再次訪問；⑦如果發(fā)現(xiàn)頁表中對應(yīng)頁面頁失效，存儲管理單元就發(fā)出一個缺頁中斷，請求系統(tǒng)進行處理，存儲管理單元工作己經(jīng)結(jié)束；⑧這時由存儲管理軟件按置換策略進行調(diào)頁；⑨接著把該頁面裝入內(nèi)存，修改頁表，返回用戶進程重新執(zhí)行被中斷的指令。1015.6.2請求頁式存儲管理2．地址轉(zhuǎn)換請求頁式管理中的地址變換如圖：

1025.6.2請求頁式存儲管理2．地址轉(zhuǎn)換請求頁式管理中的地址變換流程：1035.6.2請求頁式存儲管理2．地址轉(zhuǎn)換

缺頁中斷是一種特殊的中斷，它與一般的中斷相比，有著明顯的區(qū)別，主要表現(xiàn)如下:①在指令執(zhí)行期間產(chǎn)生和處理中斷信號。通常，CPU都是在一條指令執(zhí)行完后去檢查是否有中斷請求到達。若有，便去響應(yīng)；否則繼續(xù)執(zhí)行下一條指令。然而，缺頁中斷是在指令執(zhí)行期間，發(fā)現(xiàn)所要訪問的指令或數(shù)據(jù)不在內(nèi)存時產(chǎn)生和處理的。②一條指令執(zhí)行期間，可能產(chǎn)生多次缺頁中斷?；谶@些特征，系統(tǒng)的硬件機構(gòu)應(yīng)能保存多次中斷時的狀態(tài)，并保證最后能返回到中斷前產(chǎn)生缺頁中斷的指令處，繼續(xù)執(zhí)行。

1045.6.2

請求頁式存儲管理3．頁面調(diào)入策略和清除策略

頁面調(diào)入策略決定何時把一個頁面裝入內(nèi)存，有兩種策略可供選擇：請頁式調(diào)入和預調(diào)式調(diào)入。

清除策略是與調(diào)入策略相對的，它要考慮何時把一個修改過的頁面寫回外存，常用的兩種方法是：請頁式清除和預約式清除。

1055.6.2請求頁式存儲管理4．頁面分配策略在請求頁式存儲管理中，可采用兩種策略分配頁框給進程：固定分配和可變分配。固定分配策略:缺少靈活性可變分配:性能會更好些，采用可變分配策略的困難在于操作系統(tǒng)要經(jīng)常監(jiān)視活動進程的行為和進程缺頁中斷率的情況，這會增加操作系統(tǒng)的開銷。在進行頁面置換時，也可采用兩種策略：局部置換和全局置換。固定分配往往和局部置換策略配合使用可變分配往往和全局置換策略配合使用

1065.6虛擬存儲管理5.6.1相關(guān)基本概念5.6.2請求頁式存儲管理5.6.3頁面置換算法5.6.4請求頁式管理性能分析

5.6.5請求段式存儲管理5.6.6請求段頁式存儲管理1075.6.3頁面置換算法頁面置換算法是指在需要調(diào)入頁面且內(nèi)存已滿時，確定將要換出頁面的算法。

一個理論算法:假定進程P共計N頁，而系統(tǒng)分配給它的內(nèi)存塊只有M塊（M，N均為正整數(shù)，且１≤M≤N）。如果進程P在運行中成功的訪問次數(shù)為S（即所訪問的頁在內(nèi)存中），不成功的訪問次數(shù)為F（即缺頁中斷次數(shù)），則缺頁中斷率為：R=F/(S+F)1085.6.3頁面置換算法1．最佳置換算法2．先進先出置換算法3．最近最久未使用置換算法4．時鐘置換算法5．最少使用置換算法1095.6.3頁面置換算法1．最佳置換算法

最佳置換算法（OPT）即選擇永不使用的或者在最長時間內(nèi)不再被訪問的頁面進行置換。

三種頁面置換算法示例1105.6.3頁面置換算法2．先進先出置換算法先進先出置換算法（FIFO）選擇最先進入內(nèi)存的頁面進行置換，即選擇在內(nèi)存中駐留時間最久的頁面進行淘汰。優(yōu)點:直觀，實現(xiàn)簡單，可通過鏈表按時間先后順序鏈接。缺點:它與進程實際運行的規(guī)律不相適應(yīng)，性能較差，將出現(xiàn)Belady現(xiàn)象，即當分配頁面數(shù)增加，缺頁率和缺頁次數(shù)反而提高的異?，F(xiàn)象，故實際應(yīng)用極少。1115.6.3頁面置換算法3．最近最久未使用置換算法

最近最久未使用置換算法（LRU）即選擇最近一段時間內(nèi)最長時間沒有被訪問過的頁面進行置換。

缺點:系統(tǒng)開銷和硬件開銷增

1125.6.3頁面置換算法4．時鐘置換算法時鐘置換算法（Clock）又稱最近未使用算法（NRU），是LRU和FIFO的折衷算法由于該算法是循環(huán)地檢查各頁面的使用情況，故稱為Clock算法。1135.6.3頁面置換算法5．最少使用置換算法最少使用置換算法（LFU）的基本思想是把到當前為止被訪問次數(shù)最少的頁面淘汰。

類似于LRU算法，該算法為內(nèi)存的每個頁面設(shè)置訪問計數(shù)器，用來記錄該頁面被訪問的頻率。當頁面被訪問，該頁面計數(shù)器加1，發(fā)生缺頁中斷時，淘汰計數(shù)值最小的頁面，并將所有計數(shù)清零。1145.6虛擬存儲管理5.6.1相關(guān)基本概念5.6.2請求頁式存儲管理5.6.3頁面置換算法5.6.4請求頁式管理性能分析

5.6.5請求段式存儲管理5.6.6請求段頁式存儲管理1155.6.4請求頁式管理性能分析

性能分析從如下兩個方面進行：1．缺頁率和有效訪問時間2．工作集OS1165.6.4請求頁式管理性能分析

1．缺頁率和有效訪問時間缺頁率是指出現(xiàn)缺頁的概率，或是缺頁時間間隔的概率有效訪問時間可表示為：

有效訪問時間=(1?p)存儲器訪問時間+p缺頁中斷時間要使缺頁率不至于對有效訪問時間造成過大的影響，必須保證虛存請求分頁管理方式非常低的缺頁率；否則，程序的執(zhí)行速度將受到嚴重影響。此外，提高磁盤I/O的速度，對改善虛存頁式管理系統(tǒng)的性能至關(guān)重要，應(yīng)盡量選用高速磁盤和高速磁盤接口。

1175.6.4請求頁式管理性能分析

2．工作集工作集是指在某段時間間隔?里，進程實際要訪問的頁面的集合。

具體地說，便是把某進程在時間t的工作集記為w(t,?)，把變量?稱為工作集“窗口尺寸”。圖5-31缺頁率與進程工作集的關(guān)系

如圖5-31所示給出了缺頁率與進程工作集的關(guān)系。

1185.6虛擬存儲管理5.6.1相關(guān)基本概念5.6.2請求頁式存儲管理5.6.3頁面置換算法5.6.4請求頁式管理性能分析

5.6.5請求段式存儲管理5.6.6請求段頁式存儲管理1195.6.5請求段式存儲管理請求段式存儲管理從下面兩個分析：1．實現(xiàn)的基本原理2．地址轉(zhuǎn)換OS1205.6.5請求段式存儲管理1．實現(xiàn)的基本原理

請求段式存儲管理是在段式存儲管理的基礎(chǔ)上建立的。其基本思想和段式存儲管理類似，只是在請求段式管理中，程序運行前只需先裝入若干段，便可啟動運行，在執(zhí)行過程中，進程可請求系統(tǒng)將所缺的段調(diào)入內(nèi)存。同樣，請求分段存儲管理方式需要有硬件支持。1215.6.5請求段式存儲管理1．實現(xiàn)的基本原理

請求段式管理中所設(shè)置的主要數(shù)據(jù)結(jié)構(gòu)仍是段表，但因為進程的只有一部分段裝入內(nèi)存，其余仍在外存上，故需在段表中增加若干項，以供程序在缺段中斷時使用。如圖5-32所示給出了段表中的段表項。圖5-32請求段式存儲管理的段表1225.6.5請求段式存儲管理2．地址轉(zhuǎn)換請求段式存儲管理的地址轉(zhuǎn)換流程如圖5-33所示。1235.6