第4章存儲(chǔ)管理

第4章存儲(chǔ)管理

在計(jì)算機(jī)系統(tǒng)中，內(nèi)存是關(guān)鍵資源，對(duì)內(nèi)存如何處理在很大程度上將影響整個(gè)系統(tǒng)的性能。存儲(chǔ)管理目前仍是人們研究操作系統(tǒng)的中心問題之一，甚至操作系統(tǒng)的命名也往往取決于存儲(chǔ)管理的策略。學(xué)習(xí)目標(biāo)1、掌握：動(dòng)態(tài)分區(qū)法，分頁(yè)的概念和地址映射，分段的概念；請(qǐng)求分頁(yè)存儲(chǔ)管理技術(shù)，常用頁(yè)面置換算法。

2、理解：重定位、固定分區(qū)法，碎片和抖動(dòng)。3、了解：存儲(chǔ)器層次；用戶程序地址空間；程序的裝入方式。本章要點(diǎn)●連續(xù)分配存儲(chǔ)管理方式

●段式存儲(chǔ)管理

●頁(yè)式存儲(chǔ)管理

●虛擬頁(yè)式存儲(chǔ)管理

第4章基本存儲(chǔ)管理4.1地址空間與重定位內(nèi)存（MainMemory或PrimaryMemory或RealMemory）也稱主存，是指CPU能直接存取指令和數(shù)據(jù)的存儲(chǔ)器。內(nèi)存在計(jì)算機(jī)系統(tǒng)中的地位4.1.1用戶程序的地址空間1．存儲(chǔ)器的層次2．用戶程序的地址空間■主要處理階段

編輯編譯連接裝入運(yùn)行■有關(guān)概念●裝入程序——其功能是將程序模塊放入內(nèi)存，并進(jìn)行重定位?！裣鄬?duì)地址或邏輯地址

●絕對(duì)地址或物理地址2．用戶程序的地址空間■程序裝入內(nèi)存的方式

①絕對(duì)裝入方式②可重定位裝入方式③動(dòng)態(tài)運(yùn)行時(shí)裝入方式4.1.2重定位概念邏輯地址空間（簡(jiǎn)稱地址空間）

由程序中邏輯地址組成的地址范圍。內(nèi)存空間（也稱物理空間或絕對(duì)空間）由內(nèi)存中一系列存儲(chǔ)單元所限定的地址范圍。重定位程序和數(shù)據(jù)裝入內(nèi)存時(shí)，需對(duì)目標(biāo)程序中的地址進(jìn)行修改。這種把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存物理地址的過程稱作重定位。重定位方式(1)

靜態(tài)重定位(2)動(dòng)態(tài)重定位1．靜態(tài)重定位：目標(biāo)程序裝入內(nèi)存時(shí)進(jìn)行地址變換程序裝入內(nèi)存時(shí)的情況

靜態(tài)重定位示意圖

1．靜態(tài)重定位

目標(biāo)程序裝入內(nèi)存時(shí)進(jìn)行地址變換。▲優(yōu)點(diǎn)：無(wú)需增加硬件地址轉(zhuǎn)換機(jī)構(gòu)?！裰饕秉c(diǎn)：位置“釘死”；不便共享。2．動(dòng)態(tài)重定位：程序執(zhí)行期間進(jìn)行重定位●主要優(yōu)點(diǎn)：位置可變，不必連續(xù)；易于共享?！饕秉c(diǎn)：需要附加硬件支持。4.1.3對(duì)換技術(shù)對(duì)換兩個(gè)進(jìn)程示意圖

4.1.3對(duì)換技術(shù)早期的對(duì)換技術(shù)用于單用戶系統(tǒng)。

●主要優(yōu)點(diǎn)：利用外存來(lái)解決內(nèi)存不足的問題。

▲主要缺點(diǎn)：效率很低；不能保證充分利用內(nèi)存。在多道程序環(huán)境中也采用對(duì)換技術(shù)！4.2分區(qū)管理技術(shù)4.2.1分區(qū)法分區(qū)分配是為支持多道程序運(yùn)行而設(shè)計(jì)的一種最簡(jiǎn)單的存儲(chǔ)管理方式。1．固定分區(qū)法分區(qū)個(gè)數(shù)固定不變，各個(gè)分區(qū)的大小固定不變，不同分區(qū)的大小可以不同。系統(tǒng)建立一張分區(qū)說明表。每個(gè)分區(qū)對(duì)應(yīng)表中的一項(xiàng)。各表項(xiàng)包含每個(gè)分區(qū)的起始地址、分區(qū)大小以及狀態(tài)（是否正被使用）。▲分區(qū)的申請(qǐng)和釋放

（1）單一分區(qū)存儲(chǔ)管理

單一分區(qū)存儲(chǔ)管理的系統(tǒng)，任何時(shí)刻只有一個(gè)用戶程序駐留內(nèi)存。因此內(nèi)存為兩個(gè)部分?！罟┎僮飨到y(tǒng)使用的系統(tǒng)區(qū);☆供用戶程序使用的用戶區(qū)。

(2)用戶區(qū)分為“使用區(qū)”和“空閑區(qū)”兩部分。使用區(qū)是用戶作業(yè)程序真正占用的連續(xù)存儲(chǔ)區(qū)域；空閑區(qū)是分配給了用戶、但未被用戶使用的區(qū)域，稱為“內(nèi)部碎片”。

單一分區(qū)存儲(chǔ)管理系統(tǒng)的特點(diǎn)：(1)總是把一個(gè)連續(xù)的用戶區(qū)分配給一個(gè)用戶使用。

(3)這種系統(tǒng)只適用于單用戶的情況。單一分區(qū)存儲(chǔ)管理系統(tǒng)的特點(diǎn)：(4)進(jìn)入內(nèi)存的作業(yè)，獨(dú)享系統(tǒng)中的所有資源，包括內(nèi)存中的整個(gè)用戶區(qū)。(5)由于整個(gè)用戶區(qū)都分配給了一個(gè)用戶，因此作業(yè)程序進(jìn)入用戶區(qū)后，沒有移動(dòng)的必要。所以采用這種存儲(chǔ)管理策略，對(duì)用戶程序?qū)嵭徐o態(tài)重定位。單一分區(qū)存儲(chǔ)管理系統(tǒng)的存儲(chǔ)保護(hù)

實(shí)行靜態(tài)重定位，不能阻止用戶有意無(wú)意地通過不恰當(dāng)?shù)闹噶铌J入操作系統(tǒng)所占用的存儲(chǔ)區(qū)域。

在單一分區(qū)存儲(chǔ)管理中，為有效阻止用戶程序指令中的地址闖入操作系統(tǒng)所占用的區(qū)域，在CPU中會(huì)設(shè)置一個(gè)用于存儲(chǔ)保護(hù)的專用寄存器——“界限寄存器”。

界限寄存器：存放內(nèi)存用戶區(qū)的起始地址。CPU在用戶態(tài)下工作時(shí)，對(duì)內(nèi)存的每一次訪問，都要將所訪問的地址與界限寄存器中的內(nèi)容進(jìn)行比較。一旦發(fā)現(xiàn)所訪問的地址小于界限寄存器中的地址，產(chǎn)生“地址越界”中斷，阻止這次訪問的進(jìn)行。(1)每次只能有一個(gè)作業(yè)進(jìn)入內(nèi)存，故不適用于多道程序設(shè)計(jì)，整個(gè)系統(tǒng)的工作效率不高，資源利用率低下；單一分區(qū)存儲(chǔ)管理的缺點(diǎn)：(2)只要作業(yè)比用戶區(qū)小，那么在用戶區(qū)里就會(huì)形成碎片，如果用戶作業(yè)很小，那么這種浪費(fèi)是巨大的；(3)若用戶作業(yè)的相對(duì)地址空間比用戶區(qū)大，那么該作業(yè)就無(wú)法投入運(yùn)行，因?yàn)榇笞鳂I(yè)無(wú)法在小內(nèi)存上運(yùn)行。（2）固定分區(qū)存儲(chǔ)管理

系統(tǒng)初啟時(shí)將內(nèi)存劃分成n個(gè)分區(qū)（尺寸大小可以不等），系統(tǒng)運(yùn)行過程中，分區(qū)的個(gè)數(shù)及尺寸保持不變，每個(gè)分區(qū)里只裝入一個(gè)作業(yè)運(yùn)行。這就是“固定分區(qū)”存儲(chǔ)管理。對(duì)作業(yè)的組織

系統(tǒng)可以為每個(gè)分區(qū)設(shè)置一個(gè)后備作業(yè)隊(duì)列，形成多隊(duì)列的管理方式：對(duì)作業(yè)的組織

對(duì)作業(yè)的組織

也可采用多個(gè)分區(qū)只設(shè)置一個(gè)后備作業(yè)隊(duì)列的辦法。在固定分區(qū)存儲(chǔ)管理中，每個(gè)分區(qū)只允許裝入一個(gè)作業(yè)，作業(yè)在運(yùn)行期間不會(huì)移動(dòng)。因此，這時(shí)應(yīng)該對(duì)程序?qū)嵭徐o態(tài)重定位。在固定分區(qū)存儲(chǔ)管理中，要防止用戶程序?qū)Σ僮飨到y(tǒng)形成的侵?jǐn)_，也要防止用戶程序與用戶程序之間形成的侵?jǐn)_。因此必須在CPU中設(shè)置一對(duì)專用的寄存器，用于實(shí)現(xiàn)存儲(chǔ)保護(hù)。固定分區(qū)管理的地址映射和存儲(chǔ)保護(hù)

兩個(gè)專用寄存器起名為“基址寄存器”和“界限寄存器”。調(diào)度程序調(diào)度某個(gè)作業(yè)運(yùn)行時(shí)，就把該作業(yè)所在分區(qū)的起始地址裝入基址寄存器，把分區(qū)長(zhǎng)度裝入界限寄存器。

固定分區(qū)存儲(chǔ)管理的特點(diǎn)：它是最簡(jiǎn)單的、具有“多道”色彩的存儲(chǔ)管理方案。

作業(yè)程序?qū)⒁淮涡缘厝勘谎b入到分配給它的連續(xù)分區(qū)里。(3)實(shí)行靜態(tài)重定位，在分區(qū)內(nèi)的程序不能隨意移動(dòng)，否則運(yùn)行就會(huì)出錯(cuò)。(4)每個(gè)分區(qū)都有可能產(chǎn)生內(nèi)部碎片，引起內(nèi)存資源的浪費(fèi)。(5)如果到達(dá)作業(yè)的尺寸比任何一個(gè)分區(qū)的長(zhǎng)度都大，那么它就無(wú)法運(yùn)行。固定分區(qū)管理示意圖

分區(qū)說明表

分區(qū)的管理動(dòng)態(tài)分區(qū)存儲(chǔ)管理的基本思想

動(dòng)態(tài)分區(qū)存儲(chǔ)管理的基本思想是：作業(yè)要求裝入內(nèi)存時(shí)，若內(nèi)存有足夠的連續(xù)存儲(chǔ)空間供使用，那就依作業(yè)相對(duì)地址空間的大小，劃分出一個(gè)分區(qū)分配給它。2．動(dòng)態(tài)分區(qū)法圖（a）表明后備作業(yè)隊(duì)列里，作業(yè)A需要內(nèi)存15KB，作業(yè)B需要20KB，作業(yè)C需要10KB，等等。圖（b）表示系統(tǒng)初啟時(shí)的情形，整個(gè)系統(tǒng)里沒有作業(yè)運(yùn)行，用戶區(qū)空閑。圖（c）表示作業(yè)A裝入內(nèi)存時(shí)，為它劃分了尺寸為15KB的分區(qū)。用戶區(qū)被分成兩個(gè)分區(qū)，一個(gè)是已分配的，一個(gè)是空閑區(qū)。圖（d）表示作業(yè)B裝入內(nèi)存時(shí)，為它劃分了尺寸為20KB的分區(qū)，此時(shí)的用戶區(qū)被分成了三個(gè)分區(qū)；圖（e）表示作業(yè)C裝入內(nèi)存時(shí)，為它劃分了一個(gè)尺寸為10KB的分區(qū)，此時(shí)的用戶區(qū)被分成了四個(gè)分區(qū)。⑴動(dòng)態(tài)分區(qū)的分配隨著作業(yè)對(duì)存儲(chǔ)區(qū)域的不斷申請(qǐng)與釋放，發(fā)展趨勢(shì)是：分區(qū)的數(shù)目會(huì)逐漸增加，有的分區(qū)尺寸在逐漸減小，甚至有可能出現(xiàn)內(nèi)存里有空閑區(qū)、但每個(gè)都滿足不了作業(yè)程序的要求而無(wú)法分配出去的情形。在存儲(chǔ)管理中，把那些無(wú)法滿足作業(yè)存儲(chǔ)請(qǐng)求的空閑區(qū)稱為“外部碎片”。動(dòng)態(tài)分區(qū)存儲(chǔ)管理模式引發(fā)了許多新的問題。只有解決這些問題，動(dòng)態(tài)分區(qū)存儲(chǔ)管理才能付之以實(shí)現(xiàn)。實(shí)行動(dòng)態(tài)分區(qū)存儲(chǔ)管理必須解決的問題：

(1)采用地址動(dòng)態(tài)重定位技術(shù)，使程序能在內(nèi)存中移動(dòng)，為空閑區(qū)的合并提供保證。(2)

記住各個(gè)分區(qū)的使用情況，當(dāng)一個(gè)分區(qū)被釋放時(shí)，能方便地判定它的前、后分區(qū)是否為空閑區(qū)。若是空閑區(qū)，就進(jìn)行合并，形成一個(gè)大的空閑區(qū)。

(3)給出分區(qū)分配算法?！駝?dòng)態(tài)分區(qū)的優(yōu)點(diǎn)

管理方式簡(jiǎn)單，所需操作系統(tǒng)軟件和處理開銷都小。▲動(dòng)態(tài)分區(qū)的缺點(diǎn)

①內(nèi)存空間利用率不高，碎片嚴(yán)重；②活動(dòng)進(jìn)程數(shù)目受限；③無(wú)法預(yù)知所需內(nèi)存大小。動(dòng)態(tài)分區(qū)法舉例動(dòng)態(tài)分區(qū)法舉例（2）數(shù)據(jù)結(jié)構(gòu)常用的數(shù)據(jù)結(jié)構(gòu)形式有以下兩種：

①空閑分區(qū)表⑵數(shù)據(jù)結(jié)構(gòu)②空閑分區(qū)鏈：使用鏈指針把所有的空閑分區(qū)鏈接成一條鏈。（3）動(dòng)態(tài)分區(qū)管理中空閑區(qū)的合并

內(nèi)存中一個(gè)分區(qū)被釋放時(shí)，與它前后相鄰接的分區(qū)會(huì)有四種關(guān)系，如圖所示。約定：位于一個(gè)分區(qū)左邊的分區(qū)，稱為它的“后鄰接”分區(qū)，位于一個(gè)分區(qū)右邊的分區(qū)，稱為它的“前鄰接”分區(qū)。（3）動(dòng)態(tài)分區(qū)管理中空閑區(qū)的合并

圖(a)表示釋放區(qū)的前、后鄰接分區(qū)都是使用區(qū)，不存在合并問題。此時(shí)釋放區(qū)形成一個(gè)新空閑區(qū)，該空閑區(qū)的起址就是該釋放區(qū)的起址，長(zhǎng)度就是該釋放區(qū)的長(zhǎng)度。

圖(b)表示釋放區(qū)的前鄰接分區(qū)是空閑區(qū)，后鄰接分區(qū)是使用區(qū)，釋放區(qū)應(yīng)和前鄰接的空閑區(qū)合并成新的空閑區(qū)，它的起址是該釋放區(qū)的起址，長(zhǎng)度是這兩個(gè)合并分區(qū)的長(zhǎng)度之和。

圖(c)表示釋放區(qū)的前鄰接分區(qū)是使用區(qū)，后鄰接分區(qū)是空閑區(qū)，釋放區(qū)應(yīng)和后鄰接的空閑區(qū)合并成為新的空閑區(qū)，它的起址是原前鄰接空閑區(qū)的起址，長(zhǎng)度是這兩個(gè)合并分區(qū)的長(zhǎng)度之和。

圖(d)表示釋放區(qū)的前、后鄰接分區(qū)都是空閑區(qū)，釋放區(qū)應(yīng)該和這兩個(gè)鄰接的空閑區(qū)合并成新的空閑區(qū)，它的起址是原后鄰接空閑區(qū)的起址，長(zhǎng)度是這三個(gè)合并分區(qū)的長(zhǎng)度之和。（4）分配算法①最先適應(yīng)算法（First-fit）空閑表是按地址排列的（即空閑塊地址小的，在表中的序號(hào)也?。?。②最佳適應(yīng)算法（Best-fit）空閑表是以空閑分區(qū)的大小為序、按增量形式排列的，即小塊在前，大塊在后。（4）分配算法③循環(huán)適應(yīng)算法（Next-fit）最先適應(yīng)算法的變種。它不從空閑表的開頭查找，而從上次找到的可用分區(qū)的下一個(gè)空閑分區(qū)開始查找，從中選擇滿足大小要求的第一個(gè)空閑分區(qū)。④最壞適應(yīng)算法（Worst-fit）空閑表是以空閑塊的大小為序，且大塊在前、小塊在后。

（5）硬件支持通常用一對(duì)寄存器分別表示用戶進(jìn)程在內(nèi)存空間的上界地址值和下界地址值。這對(duì)寄存器是所有用戶進(jìn)程共用的。（6）碎片“碎片”或“零頭”：內(nèi)存中這種容量太小、無(wú)法利用的小分區(qū)。內(nèi)部碎片：在一個(gè)分區(qū)內(nèi)部出現(xiàn)的碎片（即被浪費(fèi)的空間），如固定分區(qū)法會(huì)產(chǎn)生內(nèi)部碎片。外部碎片：在所有分區(qū)之外新增的碎片。（7）總結(jié)分區(qū)分配的優(yōu)缺點(diǎn)

●主要優(yōu)點(diǎn)：有利于多道程序設(shè)計(jì)，所需硬件支持很少，管理算法簡(jiǎn)單，易于實(shí)現(xiàn)。

▲主要缺點(diǎn)：碎片問題嚴(yán)重，內(nèi)存利用率低，不利于大作業(yè)運(yùn)行，作業(yè)大小受內(nèi)存總量限制。作業(yè)一次性地全部裝入到內(nèi)存中；固定分區(qū)實(shí)行指令地址的靜態(tài)重定位；動(dòng)態(tài)分區(qū)實(shí)行指令地址的動(dòng)態(tài)重定位；

4.2.2可重定位分區(qū)分配■緊縮（或拼湊）——移動(dòng)某些已分配區(qū)的內(nèi)容，使所有進(jìn)程的分區(qū)緊挨在一起，而把空閑區(qū)留在另一端。■可重定位分區(qū)法動(dòng)態(tài)重定位經(jīng)常是用硬件實(shí)現(xiàn)的。緊縮時(shí)機(jī) ●釋放所占分區(qū)時(shí) ●分配進(jìn)程分區(qū)時(shí)

動(dòng)態(tài)重定位分區(qū)分配算法

址可重定位分區(qū)分配中的進(jìn)程移動(dòng)■動(dòng)態(tài)重定位的實(shí)現(xiàn)過程動(dòng)態(tài)重定位經(jīng)常用硬件實(shí)現(xiàn)硬件支持

基址寄存器（下界地址值）限長(zhǎng)寄存器（上界地址值=下界+長(zhǎng)度）■動(dòng)態(tài)重定位的實(shí)現(xiàn)過程■可重定位分區(qū)法的優(yōu)缺點(diǎn)●優(yōu)點(diǎn)

可以消除碎片，能夠分配更多的分區(qū)，有助于多道程序設(shè)計(jì)，提高內(nèi)存的利用率。▲缺點(diǎn)

◎緊縮花費(fèi)了大量CPU時(shí)間；

◎當(dāng)進(jìn)程大于整個(gè)空閑區(qū)時(shí)，仍要浪費(fèi)一定的內(nèi)存；

◎進(jìn)程的存儲(chǔ)區(qū)內(nèi)可能放有從未使用的信息；

◎進(jìn)程之間無(wú)法對(duì)信息共享。4.3分頁(yè)技術(shù)4.3.1分頁(yè)的基本概念■分頁(yè)存儲(chǔ)管理的基本方法

①邏輯空間分頁(yè)——若干大小相等的頁(yè)面。②內(nèi)存空間分塊——又稱內(nèi)存塊或頁(yè)框，由硬件（系統(tǒng)）確定。③邏輯地址表示。

④內(nèi)存分配原則

⑤設(shè)立頁(yè)表

⑥建立內(nèi)存塊表4.3.1分頁(yè)的基本概念分頁(yè)技術(shù)的地址結(jié)構(gòu)示意圖

▲給定的邏輯地址是A，頁(yè)面的大小為L(zhǎng)，則頁(yè)號(hào)p和頁(yè)內(nèi)地址d可按下式求得：

p=INT(A/L),

d=AMODL式中，INT是向下整除的函數(shù)，MOD是取余函數(shù)。

④內(nèi)存分配原則

▲以塊為單位；▲每個(gè)頁(yè)面對(duì)應(yīng)一個(gè)內(nèi)存塊；▲分配的內(nèi)存塊可不連續(xù)。分頁(yè)存儲(chǔ)管理系統(tǒng)示意圖

⑤設(shè)立頁(yè)表——系統(tǒng)為每個(gè)進(jìn)程設(shè)立一張頁(yè)面映像表，簡(jiǎn)稱頁(yè)表

●實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射⑥建立內(nèi)存塊表整個(gè)系統(tǒng)有一個(gè)內(nèi)存塊表。每個(gè)內(nèi)存塊在內(nèi)存塊表中占一項(xiàng)，表明該塊當(dāng)前空閑還是已分出去了。內(nèi)存頁(yè)幀使用情況圖(a)內(nèi)存塊表圖(b)4.3.2分頁(yè)系統(tǒng)中的地址映射分頁(yè)系統(tǒng)的地址轉(zhuǎn)換機(jī)構(gòu)▲每個(gè)進(jìn)程平均有半個(gè)頁(yè)面的內(nèi)部碎片。4.3.3頁(yè)的共享和保護(hù)頁(yè)面共享共享的方法是使這些相關(guān)進(jìn)程的邏輯空間中的頁(yè)指向相同的內(nèi)存塊（該塊中放有共享程序或數(shù)據(jù)）

★在分頁(yè)系統(tǒng)中實(shí)現(xiàn)頁(yè)的共享比較困難！2.頁(yè)面保護(hù)（1）利用頁(yè)表本身進(jìn)行保護(hù)；（2）設(shè)置存取控制位；（3）設(shè)置合法標(biāo)志。4.3.4頁(yè)表的構(gòu)造1．多級(jí)頁(yè)表

大多數(shù)現(xiàn)代計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空間，如232～264。在這種情況下，只用一級(jí)頁(yè)表會(huì)使頁(yè)表變得非常大。一種方法是利用兩級(jí)頁(yè)表，即把頁(yè)表本身也分頁(yè)。

兩級(jí)頁(yè)表地址結(jié)構(gòu)示意圖兩級(jí)頁(yè)表結(jié)構(gòu)示意圖

兩級(jí)頁(yè)表結(jié)構(gòu)的地址轉(zhuǎn)換2．散列頁(yè)表（HashedPageTable）以頁(yè)號(hào)作為參數(shù)形成散列值。散列表中每一項(xiàng)有一個(gè)鏈表，它把有相同散列值的元素鏈接起來(lái)。每個(gè)鏈表元素由三部分組成：①頁(yè)號(hào)；②對(duì)應(yīng)的內(nèi)存塊號(hào)；③指向鏈表中下一個(gè)元素的指針。散列頁(yè)表構(gòu)成及地址轉(zhuǎn)換過程

2．散列頁(yè)表（HashedPageTable）3．倒置頁(yè)表它是按內(nèi)存塊號(hào)排序的，每個(gè)內(nèi)存塊占有一個(gè)表項(xiàng)。每個(gè)表項(xiàng)包括存放在該內(nèi)存塊中頁(yè)面的虛擬頁(yè)號(hào)和擁有該頁(yè)面的進(jìn)程標(biāo)識(shí)符。倒置頁(yè)表構(gòu)成及地址轉(zhuǎn)換過程

4.4分段技術(shù)4.4.1分段的基本概念分段地址空間1．分段▲段是一組邏輯信息的集合?！慷味加凶约旱拿帧㈤L(zhǎng)度和▲段號(hào)。2．程序的地址結(jié)構(gòu)邏輯地址要用兩個(gè)成分來(lái)表示：

段號(hào)：s和段內(nèi)地址：d進(jìn)程的邏輯地址空間是二維的。分段技術(shù)地址結(jié)構(gòu)示意圖

4.4.1分段的基本概念3．段表和段表地址寄存器系統(tǒng)為每個(gè)進(jìn)程建立一個(gè)段映射表，簡(jiǎn)稱“段表”。每個(gè)段在段表中占有一項(xiàng)，段表項(xiàng)中包含段號(hào)、段長(zhǎng)和段起始地址（又稱“基址”）等。系統(tǒng)還要建立一個(gè)段表地址寄存器。有兩部分：●該段表在內(nèi)存的起始地址

●該段表的長(zhǎng)度。4.4.1分段的基本概念4．分頁(yè)和分段的主要區(qū)別①頁(yè)是信息的物理單位；

段是信息的邏輯單位。②頁(yè)的大小是由系統(tǒng)確定的；

段的長(zhǎng)度因段而異。③分頁(yè)的進(jìn)程地址空間是一維的；

分段的進(jìn)程地址空間是二維的。④分頁(yè)系統(tǒng)很難實(shí)現(xiàn)過程和數(shù)據(jù)的分離；

分段系統(tǒng)卻可以很容易實(shí)現(xiàn)這些功能。4.4.2分段系統(tǒng)中的地址映射分段地址轉(zhuǎn)換過程

分段地址轉(zhuǎn)換過程

4.4.3段的共享和保護(hù)1．段的共享共享是在段一級(jí)實(shí)現(xiàn)的，任何共享信息可以單獨(dú)成為一段。也可以只共享部分程序。2．段的保護(hù)段的保護(hù)措施包括以下三種：①存取控制②段表本身可起保護(hù)作用

●表項(xiàng)中設(shè)置該段的長(zhǎng)度限制；

●段表地址寄存器中有段表長(zhǎng)度的信息；③保護(hù)環(huán)2．段的保護(hù)段的保護(hù)措施包括以下三種：③保護(hù)環(huán)一個(gè)程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)。一個(gè)程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。環(huán)保護(hù)機(jī)構(gòu)

4.5虛擬存儲(chǔ)管理4.5.1虛擬存儲(chǔ)器的概念▲進(jìn)程在執(zhí)行之前要全部裝入內(nèi)存，這種限制是不合理的。

①程序中往往含有不會(huì)被執(zhí)行的代碼；②分配的內(nèi)存空間會(huì)大于它們的實(shí)際需要；③一個(gè)程序的某些選項(xiàng)和特性可能很少使用。程序的執(zhí)行過程也顯示出局部性。按需分別調(diào)入內(nèi)存會(huì)帶來(lái)兩點(diǎn)好處：①用戶編制程序時(shí)不必考慮內(nèi)存容量的限制；②在一定容量的內(nèi)存中就可同時(shí)裝入更多的進(jìn)程。虛擬存儲(chǔ)器（VirtualMemory）

●用戶能作為可編址內(nèi)存對(duì)待的虛擬存儲(chǔ)空間，它使用戶邏輯存儲(chǔ)器與物理存儲(chǔ)器分離，是操作系統(tǒng)給用戶提供的一個(gè)比真實(shí)內(nèi)存空間大得多的地址空間。實(shí)現(xiàn)虛擬存儲(chǔ)技術(shù)的物質(zhì)基礎(chǔ)

●二級(jí)存儲(chǔ)器結(jié)構(gòu)；

●動(dòng)態(tài)地址轉(zhuǎn)換機(jī)構(gòu)（DAT）。虛擬存儲(chǔ)器實(shí)質(zhì)上是把用戶地址空間和實(shí)際的存儲(chǔ)空間區(qū)分開來(lái)。它主要受到兩方面的限制

①指令中表示地址的字長(zhǎng)②外存的容量。4.5.2虛擬存儲(chǔ)器的特征①虛擬擴(kuò)充；②部分裝入；③離散分配；④多次對(duì)換。

4.6請(qǐng)求分頁(yè)技術(shù)4.6.1請(qǐng)求分頁(yè)的基本思想是在單純分頁(yè)技術(shù)基礎(chǔ)上發(fā)展起來(lái)的。二者的根本區(qū)別在于請(qǐng)求分頁(yè)提供虛擬存儲(chǔ)器。★基本思想：當(dāng)一個(gè)進(jìn)程的部分頁(yè)面在內(nèi)存時(shí)就可調(diào)度它運(yùn)行；在運(yùn)行過程中若用到的頁(yè)面尚未在內(nèi)存，則把它們動(dòng)態(tài)換入內(nèi)存。▲如果地址轉(zhuǎn)換機(jī)構(gòu)遇到一個(gè)具有“N”狀態(tài)的頁(yè)表項(xiàng)時(shí)，便產(chǎn)生一個(gè)缺頁(yè)中斷。4.6.2硬件支持及缺頁(yè)處理1．頁(yè)表機(jī)制★頁(yè)表項(xiàng)不僅要包含該頁(yè)在內(nèi)存的基址，還含有下列信息：

①每一項(xiàng)增加一個(gè)狀態(tài)位，指示該頁(yè)面是否在內(nèi)存中。②還要記載該頁(yè)面在外存的地址（又稱文件地址）。③在頁(yè)表中還要增加一些位，記錄該頁(yè)的使用情況。頁(yè)表項(xiàng)通常包含下列信息：典型的頁(yè)表表項(xiàng)示意圖

頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問字段A修改位M外存地址2．缺頁(yè)中斷機(jī)構(gòu)指令執(zhí)行步驟與缺頁(yè)中斷處理過程

3．頁(yè)面置換過程

▲實(shí)現(xiàn)請(qǐng)求分頁(yè)必須解決內(nèi)存塊的分配算法和頁(yè)面置換算法兩個(gè)主要問題。主要包括以下4個(gè)步驟：①找出所需頁(yè)面在磁盤上的位置。②找出一個(gè)空閑內(nèi)存塊。③把所需頁(yè)面讀入內(nèi)存塊（剛剛得到的空閑塊），修改頁(yè)表和存儲(chǔ)塊表。④重新啟動(dòng)該用戶進(jìn)程。頁(yè)面置換流程示例

4．具有快表的地址轉(zhuǎn)換機(jī)構(gòu)在內(nèi)存中放置頁(yè)表也帶來(lái)存取速度下降的矛盾?？毂恚ɑ騎ranslationLookasideBuffer,TLB）：專用的、高速小容量的聯(lián)想存儲(chǔ)器。快表每項(xiàng)包括鍵號(hào)和值兩部分。程序局部化：一個(gè)程序在一段時(shí)間內(nèi)總是相對(duì)集中在一個(gè)有限地址空間的某個(gè)區(qū)域中執(zhí)行。

4．具有快表的地址轉(zhuǎn)換機(jī)構(gòu)請(qǐng)求分頁(yè)中的地址變換過程

4.6.3頁(yè)面置換算法1．有效存取時(shí)間和頁(yè)面走向⑴有效存取時(shí)間缺頁(yè)率p：表示缺頁(yè)中斷的概率（0≤p≤1）

等于缺頁(yè)次數(shù)與全部訪問內(nèi)存次數(shù)之比有效存取時(shí)間可表示為：

有效存取時(shí)間=(1-p)×ma+p×缺頁(yè)處理時(shí)間▲缺頁(yè)中斷處理所花費(fèi)的時(shí)間主要有以下三部分：①處理缺頁(yè)中斷的時(shí)間。②調(diào)入該頁(yè)的時(shí)間。③重新啟動(dòng)該進(jìn)程的時(shí)間?！鴮㈨?yè)面從盤上讀到內(nèi)存所花費(fèi)的時(shí)間包括：

●磁盤尋道時(shí)間（即磁頭從當(dāng)前磁道移至指定磁道所用的時(shí)間）

●旋轉(zhuǎn)延遲時(shí)間（即磁頭從當(dāng)前位置落到指定扇區(qū)開頭所用的時(shí)間）

●數(shù)據(jù)傳輸時(shí)間典型磁盤的旋轉(zhuǎn)延遲時(shí)間約為8ms，尋道時(shí)間約為15ms，傳輸時(shí)間是1ms。⑵頁(yè)面走向抖動(dòng)頻繁地更換頁(yè)面,以致系統(tǒng)的大部分時(shí)間花費(fèi)在頁(yè)面的調(diào)度和傳輸上。

盡量避免系統(tǒng)“抖動(dòng)”。存儲(chǔ)訪問序列也叫頁(yè)面走向

①對(duì)于給定的頁(yè)面大小，僅考慮其頁(yè)號(hào)，不關(guān)心完整的地址。②如果當(dāng)前對(duì)頁(yè)面p進(jìn)行了訪問，那么，馬上又對(duì)該頁(yè)訪問就不會(huì)缺頁(yè)。這樣連續(xù)出現(xiàn)的同一頁(yè)號(hào)就簡(jiǎn)化為一個(gè)頁(yè)號(hào)。⑵頁(yè)面走向存儲(chǔ)訪問序列也叫頁(yè)面走向▲如下地址序列（用十進(jìn)制數(shù)表示）：

0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105

若每頁(yè)100個(gè)字節(jié)，則頁(yè)面走向簡(jiǎn)化為：1，4，1，6，1，6，1，6，1，6，1一般，隨著可用塊數(shù)的增加，缺頁(yè)數(shù)將減少。缺頁(yè)量與內(nèi)存塊數(shù)關(guān)系圖▲統(tǒng)一采用下述頁(yè)面走向：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1并且，假定每個(gè)作業(yè)只有三個(gè)內(nèi)存塊可供使用。2．常用的頁(yè)面置換算法⑴先進(jìn)先出總是淘汰在內(nèi)存中停留時(shí)間最長(zhǎng)（年齡最老）的一頁(yè)，即先進(jìn)入內(nèi)存的頁(yè)，先被換出。FIFO頁(yè)面置換序列

▲總共有15次缺頁(yè)！2．常用的頁(yè)面置換算法⑴先進(jìn)先出●優(yōu)點(diǎn)：容易理解，方便程序設(shè)計(jì)?！秉c(diǎn)：性能并不很好，效率不高；存在Belady異常現(xiàn)象，即缺頁(yè)率隨內(nèi)存塊增加而增加。⑵最佳置換法最佳置換算法（OptimalReplacement,OPT）其實(shí)質(zhì)是：為調(diào)入新頁(yè)面而必須預(yù)先淘汰某個(gè)老頁(yè)面時(shí)，所選擇的老頁(yè)面應(yīng)在將來(lái)不被使用，或者是在最遠(yuǎn)的將來(lái)才被訪問?！ＷC有最小缺頁(yè)率！

▲OPT算法在實(shí)現(xiàn)上有困難！最佳頁(yè)面置換序列僅出現(xiàn)9次缺頁(yè)中斷！

⑶最近最少使用置換法以“最近的過去”作為“不久將來(lái)”的近似，把最近最長(zhǎng)一段時(shí)間里不曾使用的頁(yè)面淘汰掉。實(shí)質(zhì)是：當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間里最久沒有使用過的頁(yè)面予以淘汰。最近最少使用算法頁(yè)面置換序列

▲產(chǎn)生12次缺頁(yè)！LRU算法需要實(shí)際硬件的支持。實(shí)現(xiàn)時(shí)的問題是：怎樣確定最后訪問以來(lái)所經(jīng)歷時(shí)間的順序。有以下兩種可行的辦法：①計(jì)數(shù)器②棧。利用棧記錄目前訪問最多的頁(yè)面示例

⑷最近未使用置換法最近未使用（NotRecentlyUsed，NRU）算法是LRU算法的近似方法。

不(5)Clock置換算法(6)改進(jìn)型Clock置換算法

由訪問位A和修改位M可以組合成下面四種類型的頁(yè)面：1類(A=0,M=0):表示該頁(yè)最近既未被訪問，又未被修改，是最佳淘汰頁(yè)。2類(A=0,M=1):表示該頁(yè)最近未被訪問，但已被修改，并不是很好的淘汰頁(yè)。3類(A=1,M=0)：最近已被訪問，但未被修改，該頁(yè)有可能再被訪問。4類(A=1,M=1):最近已被訪問且被修改，該頁(yè)可能再被訪問。(6)改進(jìn)型Clock置換算法

由訪問位A和修改位M可以組合成下面四種類型的頁(yè)面,其執(zhí)行過程可分成以下三步：(1)從當(dāng)前位置開始掃描循環(huán)隊(duì)列，尋找A=0且M=0的頁(yè)面，將所遇到的第一個(gè)頁(yè)面作為所選中的淘汰頁(yè)。在第一次掃描期間不改變?cè)L問位A。(2)如果查找一周后未遇到第一類頁(yè)面，則開始第二輪掃描，尋找A=0且M=1的頁(yè)面，將遇到的第一個(gè)這類頁(yè)面作為淘汰頁(yè)。將所有掃描過的頁(yè)面的訪問位都置0。(3)如果第二步也失敗，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁(yè)。4.7內(nèi)存塊分配和抖動(dòng)問題4.7.1內(nèi)存塊分配

1．最少內(nèi)存塊數(shù)分給每個(gè)進(jìn)程的最少內(nèi)存塊數(shù)是指保證進(jìn)程正常運(yùn)行所需的最少內(nèi)存塊數(shù)，它是由指令集結(jié)構(gòu)決定的。2．內(nèi)存塊的分配

①固定分配策略分配給進(jìn)程的內(nèi)存塊數(shù)是固定的，且在最初裝入時(shí)（即進(jìn)程創(chuàng)建時(shí)）確定塊數(shù)。②可變分配策略允許分給進(jìn)程的內(nèi)存塊數(shù)隨進(jìn)程的活動(dòng)而改變。3.頁(yè)面置換范圍

●全局置換允許一個(gè)進(jìn)程從全體存儲(chǔ)塊的集合中選取淘汰塊，盡管該塊當(dāng)前分配給其他進(jìn)程，還是能強(qiáng)行占用?！窬植恐脫Q是每個(gè)進(jìn)程只能從分給它的一組內(nèi)存塊中選擇淘汰塊?！鼍植恐脫Q可與固定分配策略相結(jié)合；■局部置換可與可變分配策略相結(jié)合；

■全局置換只能與可變分配策略相結(jié)合。

4．分配算法（1）等分法——內(nèi)存塊按進(jìn)程平分。

（2）比例法設(shè)進(jìn)程pi的地址空間大小為si，則總地址空間為：

S=∑si若可用塊的總數(shù)是m，則分給進(jìn)程pi的塊數(shù)是：

ai

≈m.si

/S（3）優(yōu)先權(quán)法——給高優(yōu)先級(jí)進(jìn)程分配較多內(nèi)存。

4.7.2抖動(dòng)問題■整個(gè)系統(tǒng)的頁(yè)面替換非常頻繁，以致大部分機(jī)器時(shí)間都用在來(lái)回進(jìn)行的頁(yè)面調(diào)度上，只有一小部分時(shí)間用于進(jìn)程的實(shí)際運(yùn)算。這種局面稱為系統(tǒng)“抖動(dòng)（Thrashing）”。1．產(chǎn)生抖動(dòng)的原因▲內(nèi)存不足；▲多道程序度高；▲CPU的利用率太低。

CPU利用率與多道程序度之間的關(guān)系2．防止抖動(dòng)的方法

①采用局部置換策略②利用工作集策略防止抖動(dòng)③掛起某些進(jìn)程④采用缺頁(yè)頻度法（PageFaultFrequency,PFF）缺頁(yè)頻度的上限和下限

4.8段式虛擬存儲(chǔ)器4.8.1基本工作過程

▲一個(gè)進(jìn)程的所有分段的副本都保存在外存上。當(dāng)它運(yùn)行時(shí)，先把當(dāng)前需要的一段或幾段裝入內(nèi)存，其他段僅在調(diào)用時(shí)才裝入。

▲當(dāng)所訪問的段不在內(nèi)存時(shí)，便產(chǎn)生缺段中斷各段表項(xiàng)中要增加一位，以表明該段的存在狀態(tài)。還要增加另外一些控制位，如：

▲修改位；▲保護(hù)位；▲共享位缺段中斷機(jī)構(gòu)--請(qǐng)求分段系統(tǒng)中的中斷處理過程

4.8.2動(dòng)態(tài)鏈接和鏈接中斷處理1．動(dòng)態(tài)鏈接僅當(dāng)用到某個(gè)分段時(shí)才對(duì)它進(jìn)行鏈接，從而避免不必要的鏈接。間接編址間接字鏈接故障指示位

4.8.2動(dòng)態(tài)鏈接和鏈接中斷處理直接編址與間接編址示意圖

2．鏈接中斷處理段的動(dòng)態(tài)鏈接示意圖

程序MAIN中有一條指令LOAD*1，3|100

方式功能單一連續(xù)區(qū)分區(qū)式頁(yè)式段式段頁(yè)式固定動(dòng)態(tài)適用環(huán)境單道多道多道多道多道虛擬空間一維一維一維二維二維重定位方式靜態(tài)靜態(tài)動(dòng)態(tài)動(dòng)態(tài)動(dòng)態(tài)動(dòng)態(tài)分配方式連續(xù)連續(xù)非連續(xù)非連續(xù)非連續(xù)釋放全部分區(qū)淘汰算法淘汰算法淘汰算法保護(hù)界限寄存器界限寄存器對(duì)頁(yè)表段表、段長(zhǎng)段表、段長(zhǎng)、頁(yè)表內(nèi)存擴(kuò)充覆蓋與交換覆蓋與交換虛存虛存虛存共享不能不能較難方便方便硬件支持保護(hù)保護(hù)地址變換機(jī)構(gòu)、保護(hù)地址變換機(jī)構(gòu)、保護(hù)地址變換機(jī)構(gòu)、保護(hù)4.9工作集

測(cè)試表明，虛擬存儲(chǔ)系統(tǒng)的有效操作依賴于程序中訪問的局部化程度。

1.局部性模型時(shí)間局部化是指一旦某條指令或數(shù)據(jù)被訪問過，它往往很快又被再次訪問?？臻g局部化是指一旦某個(gè)位置被訪問過，它附近的位置也可能很快要用到。4.9工作集2.工作集模型工作集，就是一個(gè)進(jìn)程在某一小段時(shí)間內(nèi)訪問頁(yè)面的集合。工作集模型

▲工作集依賴于程序的行為，并且其大小與的取值有關(guān)。每個(gè)進(jìn)程的工作集大小為WSSi，那么D就是系統(tǒng)中全部（n個(gè)）進(jìn)程對(duì)內(nèi)存塊的總請(qǐng)求量?！绻?qǐng)求值D大于可用內(nèi)存塊的總量m(D＞m)，將出現(xiàn)抖動(dòng)。

伙伴系統(tǒng)是對(duì)固定分區(qū)和可變分區(qū)兩種存儲(chǔ)管理“揚(yáng)長(zhǎng)避短”后，提出的一種折中方案。

伙伴系統(tǒng)中，可用內(nèi)存分區(qū)的大小為： 2K，L≤K≤U其中：2L表示分配的最小分區(qū)的尺寸；2U表示分配的最大分區(qū)的尺寸。伙伴系統(tǒng)

C(64KB)64KBA(128KB)128KBB(256KB)512KBA(128KB)B(256KB)512KBA(128KB)128KB256KB512KB1MBC(64KB)64KBA(128KB)B(256KB)D(256KB)C(64KB)64KBA(128KB)256KBD(256KB)256KB256KBC(64KB)64KB128KB256KBD(256KB)256KBC(64KB)64KBE(128KB)256KBD(256KB)256KBE(128KB)128KB256KBD(256KB)256KB512KBD(256KB)256KB1MB1MB初啟：A請(qǐng)求100KB：B請(qǐng)求240KB：C請(qǐng)求64KB：D請(qǐng)求256KB：B釋放256KB：A釋放128KB：E請(qǐng)求128KB：C釋放64KB：E釋放