第四章 存儲器管理課件

4存儲管理

第四章存儲器管理

4.1概述4.2存儲管理的功能4.3分區(qū)存儲管理4.4頁式存儲管理4.5段式系統(tǒng)4.6段頁式存儲管理4.7UNIX系統(tǒng)的存儲管理4存儲管理4.1概述存儲器storage,memmory能接收數(shù)據(jù)和保存數(shù)據(jù)、而且能根據(jù)命令提供這些數(shù)據(jù)的裝置。4存儲管理存儲器分成兩類：內(nèi)存儲器（簡稱內(nèi)存、主存、物理存儲器）處理機(jī)能直接訪問的存儲器。用來存放系統(tǒng)和用戶的程序和數(shù)據(jù)，其特點是存取速度快，存儲方式是以新?lián)Q舊，斷電信息丟失。外存儲器（簡稱外存、輔助存儲器）處理機(jī)不能直接訪問的存儲器。用來存放用戶的各種信息，存取速度相對內(nèi)存而言要慢得多，但它可用來長期保存用戶信息。在文件系統(tǒng)中介紹。4存儲管理1.內(nèi)存的物理組織物理地址：把內(nèi)存分成若干個大小相等的存儲單元，每個單元給一個編號，這個編號稱為內(nèi)存地址（物理地址、絕對地址、實地址），存儲單元占8位，稱作字節(jié)（byte）。物理地址空間：物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維的線性空間。4存儲管理2.程序的邏輯結(jié)構(gòu)程序地址：用戶編程序時所用的地址（或稱邏輯地址、虛地址），基本單位可與內(nèi)存的基本單位相同，也可以不相同。程序地址空間（邏輯地址空間、虛地址空間）:用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從0開始的，可以是一維線性空間，也可以是多維空間。4存儲管理4.2存儲管理的功能1.存儲管理功能(1)地址映射將程序地址空間中使用的邏輯地址變換成主存中的地址的過程(2)主存分配

按照一定的算法把某一空閑的主存區(qū)分配給作業(yè)或進(jìn)程。(3)

存儲保護(hù)保證用戶程序(或進(jìn)程映象)在各自的存儲區(qū)域內(nèi)操作，互不干擾。(4)提供虛擬存儲技術(shù)使用戶程序的大小和結(jié)構(gòu)不受主存容量和結(jié)構(gòu)的限制，即使在用戶程序比實際主存容量還要大的情況下，程序也能正確運行．4存儲管理

4.2.1地址映射一、地址映射將程序地址空間中使用的邏輯地址變換成主存中的地址的過程稱為地址映射。有時也稱為地址重定位。4存儲管理二、地址映射方式地址映射的功能就是要建立虛實地址的對應(yīng)關(guān)系，實現(xiàn)地址映射有三種方式：1.編程或編譯時確定地址映射關(guān)系2.靜態(tài)地址映射3.動態(tài)地址映射4存儲管理1.編程或編譯時確定地址映射關(guān)系編程時確定虛－實地址的關(guān)系是指在用機(jī)器指令編程時，程序員直接按物理內(nèi)存地址編程，這種程序在系統(tǒng)中是不能做任何移動的，否則就會出錯。4存儲管理2.靜態(tài)地址映射靜態(tài)地址映射是在程序裝入內(nèi)存時完成從邏輯地址到物理地址的轉(zhuǎn)換的。在一些早期的系統(tǒng)中都有一個裝入程序（加載程序），它負(fù)責(zé)將用戶程序裝入系統(tǒng)，并將用戶程序中使用的訪問內(nèi)存的邏輯地址轉(zhuǎn)換成物理地址。評價:優(yōu)點是實現(xiàn)簡單，不要硬件的支持。缺點是程序一旦裝入內(nèi)存，移動就比較困難。有時間上的浪費。在程序裝入內(nèi)存時要將所有訪問內(nèi)存的地址轉(zhuǎn)換成物理地址。4存儲管理4存儲管理3.動態(tài)地址映射動態(tài)地址映射是在程序執(zhí)行時由系統(tǒng)硬件完成從邏輯地址到物理地址的轉(zhuǎn)換的。

系統(tǒng)中設(shè)置了重定位寄存器。4存儲管理動態(tài)地址映射是由硬件地執(zhí)行時完成的，程序中不執(zhí)行的程序就不做地址映射的工作，這樣節(jié)省了CPU的時間。重定位寄存器的內(nèi)容由操作系統(tǒng)用特權(quán)指令來設(shè)置，比較靈活。實現(xiàn)動態(tài)地址映射必須有硬件的支持，并有一定的執(zhí)行時間延遲。現(xiàn)代計算機(jī)系統(tǒng)中都采用動態(tài)地址映射技術(shù)。動態(tài)地址映射技術(shù)能滿足以下目標(biāo)：（1）具有給一個用戶程序任意分配內(nèi)存區(qū)的能力；（2）可實現(xiàn)虛擬存儲；（3）具有重新分配的能力（4）對于一個用戶程序，可以分配到多個不同的存儲區(qū)4存儲管理4.2.2內(nèi)存分配

在多道程序設(shè)計的環(huán)境中，內(nèi)存分配的功能包括：制定分配策略、構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)、響應(yīng)系統(tǒng)的內(nèi)存分配的請求和回收系統(tǒng)釋放的內(nèi)存區(qū)。內(nèi)存管理策略有三種：1、放置策略決定內(nèi)存中放置信息的區(qū)域（或位置），即如何在若干個空閑區(qū)中選擇一個或幾個空閑區(qū)的原則；2、調(diào)入策略決定信息裝入內(nèi)存的時機(jī)，有兩種：在用戶請求時調(diào)入，稱為請調(diào)；根據(jù)某種算法，確定系統(tǒng)將要使用的信息，并在執(zhí)行前預(yù)先調(diào)入內(nèi)存，稱為預(yù)調(diào)；3、淘汰策略當(dāng)內(nèi)存不足時，決定將某些信息調(diào)出內(nèi)存的策略。4存儲管理4.2.3提供虛存物理存儲器的結(jié)構(gòu)是個一維的線性空間，容量是有限的。用戶程序結(jié)構(gòu)：一維空間

一個用戶程序就是一個程序，并且程序和數(shù)據(jù)是不分離的；二維空間程序由主程序和若干個子程序（或函數(shù)）組成，并且程序與數(shù)據(jù)是分離的；n維空間即一個大型程序，由一個主模塊和多個子模塊組成，其中，各子模塊又由主程序和子程序（或函數(shù)）組成。用戶程序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容量大，有時候要大得多。1、問題的提出4存儲管理

如何將與物理內(nèi)存結(jié)構(gòu)不同，且大于物理內(nèi)存容量的用戶程序裝入運行？這就是提出研究虛擬存儲器的原因，或稱為虛擬存儲技術(shù)發(fā)展的原動力。4存儲管理2.虛擬存儲器概念為用戶提供一種不受物理存儲器結(jié)構(gòu)和容量限制的存儲器的技術(shù)稱為虛擬存儲器，或稱虛擬存儲技術(shù)。它是用戶編程時所使用的一種用戶思維中的存儲器，它可以是任何結(jié)構(gòu)（一維線性空間、二維空間、乃至n維空間），并沒有容量的限制?，F(xiàn)代計算機(jī)操作系統(tǒng)都采用了這種技術(shù)，使得用戶編程序時不需要考慮物理內(nèi)存的結(jié)構(gòu)和容量，極大地方便了用戶。虛擬存儲器需要大容量的外存儲器的支持，或稱物資基礎(chǔ)。4存儲管理4.2.4存儲保護(hù)在多道程序設(shè)計的環(huán)境下，系統(tǒng)中有系統(tǒng)程序和多個用戶程序同時存在，如何保證用戶程序不破壞系統(tǒng)程序，用戶程序之間不相互干擾？這就是存儲保護(hù)所要解決的問題。常用的存儲保護(hù)有兩種。4存儲管理1.上下界保護(hù)下界寄存器存放程序裝入內(nèi)存后的開始地址（首址）上界寄存器存放程序裝入內(nèi)存后的末地址判別式：下界寄存器≤物理地址＜上界寄存器4存儲管理例：有一程序裝入內(nèi)存的首地址是500，末地址是1500，訪問內(nèi)存的邏輯地址是500、345、1000。

下界寄存器：500

上界寄存器：1500

邏輯地址＋裝入內(nèi)存的首地＝物理地址

1、500＋500＝1000500≤1000＜1500√2、345＋500＝845500≤845＜1500√

3、1000＋500＝1500500≤1500＜1500×4存儲管理2.基址、限長寄存器保護(hù)例：有一程序裝入內(nèi)存的首地址是500，末地址是1500，訪問內(nèi)存的邏輯地址是500、345、1000。

下界寄存器：500

上界寄存器：1500

1、500≤500＜1000√2、500≤345＜1000√

3、500≤1000＜1000×4存儲管理3.兩種存儲保護(hù)技術(shù)的區(qū)別

區(qū)別：1、寄存器的設(shè)置不同；2、判別式中用的判別條件不同上下界寄存器保護(hù)法用的是物理地址基址、限長寄存器保護(hù)法用的是程序的邏輯地址對于合法的訪問地址這兩者的效率是相同的，對不合法的訪問地址來說，上下界存儲保護(hù)浪費的CPU時間相對來說要多些。4存儲管理4.3分區(qū)存儲管理分區(qū)存儲管理是滿足多道程序設(shè)計的最簡單的一種存儲管理方法，它允許多個用戶程序同時存在系統(tǒng)內(nèi)存中，即共享內(nèi)存空間。最早期的分區(qū)存儲管理采用固定分區(qū)的方法，把內(nèi)存空間分成若干個大小不等的區(qū)域，稱為分區(qū)。每個用戶程序（作業(yè)、進(jìn)程）調(diào)入內(nèi)存后，占用其中一個分區(qū)，程序運行完成后釋放該分區(qū)。這種存儲管理的方法的主要問題是內(nèi)存使用效率極低，很快就被淘汰了。4.3.1概述4存儲管理動態(tài)分區(qū)存儲管理技術(shù)系統(tǒng)生成后，操作系統(tǒng)占用內(nèi)存的一部分，一般在物理內(nèi)存的開始處，比如，一個操作系統(tǒng)占20KB，裝入系統(tǒng)后占用0～20KB的內(nèi)存空間，剩下的部分作為一個空閑區(qū)，當(dāng)一個用戶程序（作業(yè)、進(jìn)程）調(diào)入內(nèi)存時，把這個空閑區(qū)的低地址部分的區(qū)域分配給它.4存儲管理當(dāng)有作業(yè)完成后釋放所占用的存儲區(qū)。在系統(tǒng)運行的過程中，系統(tǒng)中形成多個空閑的不連續(xù)的存儲區(qū)，稱主空閑。4存儲管理分區(qū)存儲管理技術(shù)的實現(xiàn)：1、地址映射2、動態(tài)存儲管理的機(jī)構(gòu)（數(shù)據(jù)結(jié)構(gòu)）3、分區(qū)的分配和回收4、三種基本的放置策略4存儲管理4.3.2用基地址寄存器實現(xiàn)動態(tài)地址映射在這種存儲管理技術(shù)中，系現(xiàn)設(shè)置一個專用寄存器，稱為基地址寄存器，當(dāng)一個進(jìn)程（或程序、作業(yè)）被調(diào)度運行時，系統(tǒng)首先從PCB中取出該進(jìn)程的首地址裝入基地址寄存器中，在該進(jìn)程運行的過程中實現(xiàn)動態(tài)地址映射。4存儲管理

4.3.3分區(qū)分配機(jī)構(gòu)分區(qū)存儲管理使用的數(shù)據(jù)結(jié)構(gòu)主要是空閑區(qū)表、空閑區(qū)隊列兩種。4存儲管理4.3.4分區(qū)的分配與回收

內(nèi)存分配程序包括分配一個內(nèi)存塊（分區(qū)）和釋放一個內(nèi)存塊（分區(qū)）兩個函數(shù)，當(dāng)進(jìn)程需要一個大小為size的內(nèi)存時，可以通過系統(tǒng)調(diào)用向系統(tǒng)申請。調(diào)用形式：request(size)

返回：成功為分區(qū)的首地址，失敗為0。進(jìn)程釋放一個分區(qū)時，調(diào)用：

release(釋放區(qū)首地址）返回：無4存儲管理一、分配算法1、分配算法中切割空閑區(qū)是從低地址開始的，例如，一個空閑區(qū)大小是100KB，首址是230KB，一申請者要求80KB，分配時將從230KB開始的80KB分配給申請者，剩下的部分仍作為一個空閑區(qū)，其首址是310KB，大小是20KB。2、門限值是切割空閑區(qū)后剩下的區(qū)域若小于門限值，就不切割該空閑區(qū)，統(tǒng)統(tǒng)分給申請者。4存儲管理4存儲管理二、回收算法當(dāng)一個進(jìn)程（或程序）釋放某內(nèi)存區(qū)時，要調(diào)用存儲區(qū)釋放算法release,它將首先檢查釋放區(qū)是否與空閑區(qū)表（隊列）中的其它空閑區(qū)相鄰，若相鄰則合并成一個空閑區(qū)，否則，將釋放為一個空閑區(qū)插入空閑區(qū)表（或隊列）中的適當(dāng)位置。

空閑釋放區(qū)與空閑區(qū)相鄰有四種情況。試用C語言寫出動態(tài)分區(qū)的回收算法。4存儲管理A、將r合并到f1，f1.addr；f1.size+r.size=>f.sizeB、將r合并到f2,r.addr；r.size+r.size=>f2.sizeC、f1、r、f2合并到f1,f1.addr；

f1.size+r.size+f2.size=>f1.size撤消f2空閑區(qū)D、r作為一個空閑區(qū)，并插入到空閑區(qū)表的適當(dāng)位置。4存儲管理4.3.5幾種放置策略

分區(qū)分配和回收是對空閑區(qū)表（或空閑區(qū)隊列）數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作，空閑區(qū)表的組織有兩種方法：1、按空閑區(qū)大小的升序（降序）組織；2、按空閑區(qū)首址升序（降序）組織。根據(jù)空閑區(qū)表組織的方法的不同，有不同的放置策略，它們是最佳適應(yīng)算法、首次適應(yīng)算法和最壞適應(yīng)算法三種。4存儲管理首次適應(yīng)算法的表是按空閑區(qū)首址升序的（即空閑區(qū)表是按空閑區(qū)首址從小到大）方法組織的。一、首次適應(yīng)算法4存儲管理分配時從表首開始，以請求內(nèi)存區(qū)的大小逐個與空閑區(qū)進(jìn)行比較，找到第一個滿足要求的空閑后，若空閑區(qū)大小與請求區(qū)的大小相等，則將該空閑區(qū)分配給請求者，并撤消該空閑區(qū)所在表目；若大于請求區(qū)，就將該空閑區(qū)的一部分分配給請求者，然后，修改空閑區(qū)的大小和首址。4存儲管理切割空閑區(qū)有兩種方法：

·從空閑區(qū)頭開始

·從空閑區(qū)尾開始空閑區(qū)大小50KB，首址156KB，申請34KB。4存儲管理

這種算法的實質(zhì)是盡可能地利用低地址部分的空閑區(qū)，而盡量地保證高地址部分的大空閑區(qū)，使其不被切削成小的區(qū)，其目的是保證在以有有大的作業(yè)的到來有足夠大的空閑區(qū)來滿足請求者。回收時，首先考察釋放區(qū)是否與系統(tǒng)中的某個空閑區(qū)相鄰，若相鄰則合并成一個空閑區(qū)，否則，將釋放區(qū)作為一個空閑區(qū)按首址升序的規(guī)則插入到空閑區(qū)表適當(dāng)?shù)奈恢谩?存儲管理最佳適應(yīng)算法是將申請者放入與其大小最接近的空閑區(qū)中。切割后的空閑區(qū)最小，若系統(tǒng)中有與申請區(qū)大小相等的空閑區(qū)，這種算法肯定能將這種空閑區(qū)分配給申請者。（首次適應(yīng)法則不一定）。二、最佳適應(yīng)算法4存儲管理最佳適應(yīng)算法的空閑區(qū)表按空閑區(qū)大小升序方法組織。分配時，按申請的大小逐個與空閑區(qū)大小進(jìn)行比較，找到一個滿足要求的空閑區(qū)，就說明它是最適合的（即最佳的）。這種算法最大的缺點是分割后的空閑區(qū)將會很小，直至無法使用，而造成浪費。4存儲管理為了克服最佳適應(yīng)算法把空閑區(qū)切割得大小的缺點，人們提出了一種最壞