操作系統(tǒng)內(nèi)存管理

1、操作系統(tǒng)內(nèi)存管理 1. 內(nèi)存管理方法 內(nèi)存管理主要包括虛地址、地址變換、內(nèi)存分配和回收、內(nèi)存擴(kuò)充、內(nèi)存共享和保護(hù)等功能。 2. 連續(xù)分配存儲(chǔ)管理方式 連續(xù)分配是指為一個(gè)用戶程序分配連續(xù)的內(nèi)存空間。連續(xù)分配有單一連續(xù)存儲(chǔ)管理和分區(qū)式儲(chǔ)管理兩種方式。2.1 單一連續(xù)存儲(chǔ)管理 在這種管理方式中，內(nèi)存被分為兩個(gè)區(qū)域：系統(tǒng)區(qū)和用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。其特點(diǎn)是，最簡(jiǎn)單，適用于單用戶、單任務(wù)的操作系統(tǒng)。CPM和 DOS20以下就是采用此種方式。這種方式的最大優(yōu)點(diǎn)就是易于管理。但也存在著一些問(wèn)題和不足之處，例如對(duì)要求內(nèi)存空間少的程序，造成內(nèi)存浪費(fèi)；程序全部裝入，使得很少使用的程序部

2、分也占用定數(shù)量的內(nèi)存。2.2 分區(qū)式存儲(chǔ)管理 為了支持多道程序系統(tǒng)和分時(shí)系統(tǒng)，支持多個(gè)程序并發(fā)執(zhí)行，引入了分區(qū)式存儲(chǔ)管理。分區(qū)式存儲(chǔ)管理是把內(nèi)存分為一些大小相等或不等的分區(qū)，操作系統(tǒng)占用其中一個(gè)分區(qū)，其余的分區(qū)由應(yīng)用程序使用，每個(gè)應(yīng)用程序占用一個(gè)或幾個(gè)分區(qū)。分區(qū)式存儲(chǔ)管理雖然可以支持并發(fā)，但難以進(jìn)行內(nèi)存分區(qū)的共享。 分區(qū)式存儲(chǔ)管理引人了兩個(gè)新的問(wèn)題：內(nèi)碎片和外碎片。 內(nèi)碎片是占用分區(qū)內(nèi)未被利用的空間，外碎片是占用分區(qū)之間難以利用的空閑分區(qū)(通常是小空閑分區(qū))。 為實(shí)現(xiàn)分區(qū)式存儲(chǔ)管理，操作系統(tǒng)應(yīng)維護(hù)的數(shù)據(jù)結(jié)構(gòu)為分區(qū)表或分區(qū)鏈表。表中各表項(xiàng)一般包括每個(gè)分區(qū)的起始地址、大小及狀態(tài)(是否已分配)。 分

3、區(qū)式存儲(chǔ)管理常采用的一項(xiàng)技術(shù)就是內(nèi)存緊縮(compaction)。2.2.1 固定分區(qū)(nxedpartitioning)。 固定式分區(qū)的特點(diǎn)是把內(nèi)存劃分為若干個(gè)固定大小的連續(xù)分區(qū)。分區(qū)大小可以相等：這種作法只適合于多個(gè)相同程序的并發(fā)執(zhí)行(處理多個(gè)類(lèi)型相同的對(duì)象)。分區(qū)大小也可以不等：有多個(gè)小分區(qū)、適量的中等分區(qū)以及少量的大分區(qū)。根據(jù)程序的大小，分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。 優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開(kāi)銷(xiāo)小。 缺點(diǎn)主要有兩個(gè)：內(nèi)碎片造成浪費(fèi)；分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。2.2.2動(dòng)態(tài)分區(qū)(dynamic partitioning)。 動(dòng)態(tài)分區(qū)的特點(diǎn)是動(dòng)態(tài)創(chuàng)建分區(qū)：在裝入程序時(shí)按其初始要求

4、分配，或在其執(zhí)行過(guò)程中通過(guò)系統(tǒng)調(diào)用進(jìn)行分配或改變分區(qū)大小。與固定分區(qū)相比較其優(yōu)點(diǎn)是：沒(méi)有內(nèi)碎片。但它卻引入了另一種碎片外碎片。動(dòng)態(tài)分區(qū)的分區(qū)分配就是尋找某個(gè)空閑分區(qū)，其大小需大于或等于程序的要求。若是大于要求，則將該分區(qū)分割成兩個(gè)分區(qū)，其中一個(gè)分區(qū)為要求的大小并標(biāo)記為“占用”，而另一個(gè)分區(qū)為余下部分并標(biāo)記為“空閑”。分區(qū)分配的先后次序通常是從內(nèi)存低端到高端。動(dòng)態(tài)分區(qū)的分區(qū)釋放過(guò)程中有一個(gè)要注意的問(wèn)題是，將相鄰的空閑分區(qū)合并成一個(gè)大的空閑分區(qū)。下面列出了幾種常用的分區(qū)分配算法： 最先適配法(nrst-fit)：按分區(qū)在內(nèi)存的先后次序從頭查找，找到符合要求的第一個(gè)分區(qū)進(jìn)行分配。該算法的分配和釋放的

5、時(shí)間性能較好，較大的空閑分區(qū)可以被保留在內(nèi)存高端。但隨著低端分區(qū)不斷劃分會(huì)產(chǎn)生較多小分區(qū)，每次分配時(shí)查找時(shí)間開(kāi)銷(xiāo)便會(huì)增大。 下次適配法(循環(huán)首次適應(yīng)算法 next fit)：按分區(qū)在內(nèi)存的先后次序，從上次分配的分區(qū)起查找(到最后區(qū)時(shí)再?gòu)念^開(kāi)始，找到符合要求的第一個(gè)分區(qū)進(jìn)行分配。該算法的分配和釋放的時(shí)間性能較好，使空閑分區(qū)分布得更均勻，但較大空閑分區(qū)不易保留。 最佳適配法(best-fit)：按分區(qū)在內(nèi)存的先后次序從頭查找，找到其大小與要求相差最小的空閑分區(qū)進(jìn)行分配。從個(gè)別來(lái)看，外碎片較??；但從整體來(lái)看，會(huì)形成較多外碎片優(yōu)點(diǎn)是較大的空閑分區(qū)可以被保留。 最壞適配法(worst- fit)：按分區(qū)

6、在內(nèi)存的先后次序從頭查找，找到最大的空閑分區(qū)進(jìn)行分配?；静涣粝滦】臻e分區(qū)，不易形成外碎片。但由于較大的空閑分區(qū)不被保留，當(dāng)對(duì)內(nèi)存需求較大的進(jìn)程需要運(yùn)行時(shí)，其要求不易被滿足。 2.3 伙伴系統(tǒng) 固定分區(qū)和動(dòng)態(tài)分區(qū)方式都有不足之處。固定分區(qū)方式限制了活動(dòng)進(jìn)程的數(shù)目，當(dāng)進(jìn)程大小與空閑分區(qū)大小不匹配時(shí)，內(nèi)存空間利用率很低。動(dòng)態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)時(shí)需要進(jìn)行分區(qū)合并等，系統(tǒng)開(kāi)銷(xiāo)較大?；锇橄到y(tǒng)方式是對(duì)以上兩種內(nèi)存方式的一種折衷方案。 伙伴系統(tǒng)規(guī)定，無(wú)論已分配分區(qū)或空閑分區(qū)，其大小均為 2 的 k 次冪，k 為整數(shù)， lkm，其中： 21 表示分配的最小分區(qū)的大小， 2m 表示分配的最大分區(qū)的大

7、小， 通常 2m是整個(gè)可分配內(nèi)存的大小。 假設(shè)系統(tǒng)的可利用空間容量為2m個(gè)字， 則系統(tǒng)開(kāi)始運(yùn)行時(shí)， 整個(gè)內(nèi)存區(qū)是一個(gè)大小為2m的空閑分區(qū)。在系統(tǒng)運(yùn)行過(guò)中， 由于不斷的劃分，可能會(huì)形成若干個(gè)不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類(lèi)，對(duì)于每一類(lèi)具有相同大小的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表。這樣，不同大小的空閑分區(qū)形成了k(0km)個(gè)空閑分區(qū)鏈表。 分配步驟： 當(dāng)需要為進(jìn)程分配一個(gè)長(zhǎng)度為n 的存儲(chǔ)空間時(shí): 首先計(jì)算一個(gè)i 值，使 2(i1) <n 2i， 然后在空閑分區(qū)大小為2i的空閑分區(qū)鏈表中查找。 若找到，即把該空閑分區(qū)分配給進(jìn)程。 否則，表明長(zhǎng)度為2i的

8、空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為2(i1)的空閑分區(qū)鏈表中尋找。 若存在 2(i1)的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱(chēng)為一對(duì)伙伴，其中的一個(gè)分區(qū)用于配， 而把另一個(gè)加入分區(qū)大小為2i的空閑分區(qū)鏈表中。 若大小為2(i1)的空閑分區(qū)也不存在，則需要查找大小為2(i2)的空閑分區(qū)， 若找到則對(duì)其進(jìn)行兩次分割： 第一次，將其分割為大小為 2(i1)的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為 2(i1)的空閑分區(qū)鏈表中； 第二次，將第一次用于分配的空閑區(qū)分割為 2i的兩個(gè)分區(qū)，一個(gè)用于分配，一個(gè)加入到大小為 2i的空閑分區(qū)鏈表中。 若仍然找不到，則繼續(xù)查找大小為 2(i3)

9、的空閑分區(qū)，以此類(lèi)推。 由此可見(jiàn)，在最壞的情況下，可能需要對(duì) 2k的空閑分區(qū)進(jìn)行 k 次分割才能得到所需分區(qū)。 與一次分配可能要進(jìn)行多次分割一樣，一次回收也可能要進(jìn)行多次合并，如回收大小為2i的空閑分區(qū)時(shí)，若事先已存在2i的空閑分區(qū)時(shí)，則應(yīng)將其與伙伴分區(qū)合并為大小為2i1的空閑分區(qū)，若事先已存在2i1的空閑分區(qū)時(shí)，又應(yīng)繼續(xù)與其伙伴分區(qū)合并為大小為2i2的空閑分區(qū)，依此類(lèi)推。 在伙伴系統(tǒng)中，其分配和回收的時(shí)間性能取決于查找空閑分區(qū)的位置和分割、合并空閑分區(qū)所花費(fèi)的時(shí)間。與前面所述的多種方法相比較，由于該算法在回收空閑分區(qū)時(shí)，需要對(duì)空閑分區(qū)進(jìn)行合并，所以其時(shí)間性能比前面所述的分類(lèi)搜索算法差，但比順

10、序搜索算法好，而其空間性能則遠(yuǎn)優(yōu)于前面所述的分類(lèi)搜索法，比順序搜索法略差。 需要指出的是，在當(dāng)前的操作系統(tǒng)中，普遍采用的是下面將要講述的基于分頁(yè)和分段機(jī)制的虛擬內(nèi)存機(jī)制，該機(jī)制較伙伴算法更為合理和高效，但在多處理機(jī)系統(tǒng)中，伙伴系統(tǒng)仍不失為一種有效的內(nèi)存分配和釋放的方法，得到了大量的應(yīng)用。 2.4 內(nèi)存緊縮 內(nèi)存緊縮：將各個(gè)占用分區(qū)向內(nèi)存一端移動(dòng)，然后將各個(gè)空閑分區(qū)合并成為一個(gè)空閑分區(qū)。 這種技術(shù)在提供了某種程度上的靈活性的同時(shí)，也存在著一些弊端，例如：對(duì)占用分區(qū)進(jìn)行內(nèi)存數(shù)據(jù)搬移占用CPU時(shí)間；如果對(duì)占用分區(qū)中的程序進(jìn)行“浮動(dòng)”，則其重定位需要硬件支持。 緊縮時(shí)機(jī)：每個(gè)分區(qū)釋放后，或內(nèi)存分配找不

11、到滿足條件的空閑分區(qū)時(shí)。 圖8.12 堆結(jié)構(gòu)的存儲(chǔ)管理的分配算法： 在動(dòng)態(tài)存儲(chǔ)過(guò)程中，不管哪個(gè)時(shí)刻，可利用空間都是-一個(gè)地址連續(xù)的存儲(chǔ)區(qū)，在編譯程序中稱(chēng)之為"堆"，每次分配都是從這個(gè)可利用空間中劃出一塊。其實(shí)現(xiàn)辦法是：設(shè)立一個(gè)指針，稱(chēng)之為堆指針，始終指向堆的最低（或鍛聯(lián)）地址。當(dāng)用戶申請(qǐng)N個(gè)單位的存儲(chǔ)塊時(shí)，堆指針向高地址（或 低地址）稱(chēng)動(dòng)N個(gè)存儲(chǔ)單位，而移動(dòng)之前的堆指針的值就是分配給用戶的占用塊的初始地址。例如，某個(gè)串處理系統(tǒng)中有A、B、C、D這4個(gè)串，其串值長(zhǎng)度分別為12,6,10和8. 假設(shè)堆指針free的初值為零，則分配給這4個(gè)串值的存儲(chǔ)空間的初始地址分別為0.12.

12、18和28,如圖8.12(a)和（b)所示，分配后的堆指針的值為36。 因此，這種堆結(jié)構(gòu)的存儲(chǔ)管理的分配算法非常簡(jiǎn)單， 釋放內(nèi)存空間執(zhí)行內(nèi)存緊縮： 回收用戶釋放的空閑塊就比較麻煩.由于系統(tǒng)的可利用空間始終是一個(gè)絕址連續(xù)的存儲(chǔ)塊，因此回收時(shí)必須將所釋放的空間塊合并到整個(gè)堆上去才 能重新使用，這就是"存儲(chǔ)策縮"的任務(wù).通常，有兩種做法： 一種是一旦有用戶釋放存儲(chǔ)塊即進(jìn)行回收緊縮，例始，圖8.12 (a)的堆，在c串釋放存儲(chǔ)塊時(shí)即回收緊縮，例如圖8.12 (c)的堆，同時(shí)修改串的存儲(chǔ)映像成圖8.12(d)的狀態(tài)； 另一種是在程序執(zhí)行過(guò)程中不回收用戶隨時(shí)釋放的存儲(chǔ)塊，直到可利用空同

13、不夠分配或堆指針指向最高地址時(shí)才進(jìn)行存儲(chǔ)緊縮。此時(shí)緊縮的目的是將堆中所有的空間塊連成一塊，即將所有的占用塊部集中到 可利用空間的低地地區(qū)，而剩余的高地址區(qū)成為一整個(gè)地繼連續(xù)的空閑塊，如圖8.13所示，其中（a）為緊縮前的狀態(tài)，(b)為緊縮后的狀態(tài)· 圖8.13 a 緊縮前 b緊縮后 和無(wú)用單元收集類(lèi)似，為實(shí)現(xiàn)存儲(chǔ)紫編,首先要對(duì)占用塊進(jìn)行“標(biāo)志”，標(biāo)志算法和無(wú)用單元收集類(lèi)同(存儲(chǔ)塊的結(jié)構(gòu)可能不同）,其次需進(jìn)行下列4步雄作： （1)計(jì)算占用塊的新地址。從最低地址開(kāi)始巡査整個(gè)存儲(chǔ)空間，對(duì)每一個(gè)占用塊找到它在緊縮后的新地址。 為此,需設(shè)立兩個(gè)指針隨巡查向前移動(dòng),這兩個(gè)指針?lè)謩e指示占用 塊在緊

14、縮之前和之后的原地址和新地址。因此,在每個(gè)占用塊的第-·個(gè)存儲(chǔ)單位中，除了 設(shè)立長(zhǎng)度域(存儲(chǔ)該占用換的大小）和標(biāo)志域(存儲(chǔ)區(qū)別該存儲(chǔ)塊是占用塊或空閑塊的標(biāo) 志）之外，還需設(shè)立一個(gè)新地址城，以存儲(chǔ)占用塊在緊縮后應(yīng)有的新地址，即建立一張新， 舊地址的對(duì)照表m (2)修改用戶觸初始變量表，以便在存儲(chǔ)緊縮后用戶程序能繼續(xù)正常運(yùn)行*。 (3)檢查每個(gè)占用塊中存儲(chǔ)的數(shù)據(jù)， 若有指向其他存儲(chǔ)換的指針，則需作相應(yīng)修改. (4)將所有占用塊遷移到新地址走，這實(shí)質(zhì)上是作傳送數(shù)據(jù)的工作。 至此，完成了存儲(chǔ)緊縮的操作，最后,將堆指針賦以新值（即緊縮后的空閑存儲(chǔ)區(qū)的最低地址）。 可見(jiàn),存儲(chǔ)緊縮法比無(wú)用單元收集

15、法更為復(fù)雜，前者不僅要傳送數(shù)據(jù)（進(jìn)行占用塊遷移），而且還有需要修改所有占用塊中的指針值。因此，存儲(chǔ)緊縮也是個(gè)系統(tǒng)操作，且非不得已就不用。 3. 覆蓋和交換技術(shù) 3.1 覆蓋技術(shù) 引入覆蓋 (overlay)技術(shù)的目標(biāo)是在較小的可用內(nèi)存中運(yùn)行較大的程序。這種技術(shù)常用于多道程序系統(tǒng)之中，與分區(qū)式存儲(chǔ)管理配合使用。 覆蓋技術(shù)的原理：一個(gè)程序的幾個(gè)代碼段或數(shù)據(jù)段，按照時(shí)間先后來(lái)占用公共的內(nèi)存空間。將程序必要部分(常用功能)的代碼和數(shù)據(jù)常駐內(nèi)存；可選部分(不常用功能)平時(shí)存放在外存(覆蓋文件)中，在需要時(shí)才裝入內(nèi)存。不存在調(diào)用關(guān)系的模塊不必同時(shí)裝入到內(nèi)存，從而可以相互覆蓋。 在任何時(shí)候只在內(nèi)存中保留所需

16、的指令和數(shù)據(jù)；當(dāng)需要其它指令時(shí)，它們會(huì)裝入到剛剛不再需要的指令所占用的內(nèi)存空間； 如在同一時(shí)刻，CPU只能執(zhí)行B，C中某一條。B，C之間就可以做覆蓋。 覆蓋技術(shù)的缺點(diǎn)是編程時(shí)必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加編程復(fù)雜度；從外存裝入覆蓋文件，以時(shí)間延長(zhǎng)換取空間節(jié)省。 覆蓋的實(shí)現(xiàn)方式有兩種：以函數(shù)庫(kù)方式實(shí)現(xiàn)或操作系統(tǒng)支持。3.2 交換技術(shù) 交換 (swapping)技術(shù)在多個(gè)程序并發(fā)執(zhí)行時(shí)，可以將暫時(shí)不能執(zhí)行的程序（進(jìn)程）送到外存中，從而獲得空閑內(nèi)存空間來(lái)裝入新程序（進(jìn)程），或讀人保存在外存中而處于就緒狀態(tài)的程序。交換單位為整個(gè)進(jìn)程的地址空間。交換技術(shù)常用于多道程序系統(tǒng)或小型分時(shí)系

17、統(tǒng)中，因?yàn)檫@些系統(tǒng)大多采用分區(qū)存儲(chǔ)管理方式。與分區(qū)式存儲(chǔ)管理配合使用又稱(chēng)作“對(duì)換”或“滾進(jìn)滾出”(roll-inroll-out)。 原理：暫停執(zhí)行內(nèi)存中的進(jìn)程，將整個(gè)進(jìn)程的地址空間保存到外存的交換區(qū)中（換出swap out），而將外存中由阻塞變?yōu)榫途w的進(jìn)程的地址空間讀入到內(nèi)存中，并將該進(jìn)程送到就緒隊(duì)列（換入swap in）。 交換技術(shù)優(yōu)點(diǎn)之一是增加并發(fā)運(yùn)行的程序數(shù)目，并給用戶提供適當(dāng)?shù)捻憫?yīng)時(shí)間；與覆蓋技術(shù)相比交換技術(shù)另一個(gè)顯著的優(yōu)點(diǎn)是不影響程序結(jié)構(gòu)。交換技術(shù)本身也存在著不足，例如：對(duì)換人和換出的控制增加處理器開(kāi)銷(xiāo)；程序整個(gè)地址空間都進(jìn)行對(duì)換，沒(méi)有考慮執(zhí)行過(guò)程中地址訪問(wèn)的統(tǒng)計(jì)特性。3.3 覆蓋

18、與交換比較 1）與覆蓋技術(shù)相比，交換不要求程序員給出程序段之間的覆蓋結(jié)構(gòu)。 2）交換主要是在進(jìn)程與作業(yè)之間進(jìn)行，而覆蓋則主要在同一作業(yè)或進(jìn)程內(nèi)進(jìn)行。 另外覆蓋只能覆蓋那些與覆蓋程序段無(wú)關(guān)的程序段。4. 頁(yè)式和段式存儲(chǔ)管理 在前面的幾種存儲(chǔ)管理方法中，為進(jìn)程分配的空間是連續(xù)的，使用的地址都是物理地址。如果允許將一個(gè)進(jìn)程分散到許多不連續(xù)的空間，就可以避免內(nèi)存緊縮，減少碎片?；谶@一思想，通過(guò)引入進(jìn)程的邏輯地址，把進(jìn)程地址空間與實(shí)際存儲(chǔ)空間分離，增加存儲(chǔ)管理的靈活性。地址空間和存儲(chǔ)空間兩個(gè)基本概念的定義如下：地址空間：將源程序經(jīng)過(guò)編譯后得到的目標(biāo)程序，存在于它所限定的地址范圍內(nèi)，這個(gè)范圍稱(chēng)為地址空間

19、。地址空間是邏輯地址的集合。存儲(chǔ)空間：指主存中一系列存儲(chǔ)信息的物理單元的集合，這些單元的編號(hào)稱(chēng)為物理地址存儲(chǔ)空間是物理地址的集合。根據(jù)分配時(shí)所采用的基本單位不同，可將離散分配的管理方式分為以下三種：頁(yè)式存儲(chǔ)管理、段式存儲(chǔ)管理和段頁(yè)式存儲(chǔ)管理。其中段頁(yè)式存儲(chǔ)管理是前兩種結(jié)合的產(chǎn)物。 5. 頁(yè)式存儲(chǔ)管理4.1 基本原理 將程序的邏輯地址空間劃分為固定大小的頁(yè)(page)，而物理內(nèi)存劃分為同樣大小的頁(yè)框(pageframe)。程序加載時(shí)，可將任意一頁(yè)放人內(nèi)存中任意一個(gè)頁(yè)框，這些頁(yè)框不必連續(xù)，從而實(shí)現(xiàn)了離散分配。該方法需要CPU的硬件支持，來(lái)實(shí)現(xiàn)邏輯地址和物理地址之間的映射。在頁(yè)式存儲(chǔ)管理方式中地址結(jié)

20、構(gòu)由兩部構(gòu)成，前一部分是頁(yè)號(hào)，后一部分為頁(yè)內(nèi)地址w（位移量），如圖4所示： 頁(yè)式管理方式的優(yōu)點(diǎn)是： 1）沒(méi)有外碎片，每個(gè)內(nèi)碎片不超過(guò)頁(yè)大比前面所討論的幾種管理方式的最大進(jìn)步是， 2）一個(gè)程序不必連續(xù)存放。 3）便于改變程序占用空間的大小(主要指隨著程序運(yùn)行，動(dòng)態(tài)生成的數(shù)據(jù)增多，所要求的地址空間相應(yīng)增長(zhǎng))。 缺點(diǎn)是：要求程序全部裝入內(nèi)存，沒(méi)有足夠的內(nèi)存，程序就不能執(zhí)行。4.2 頁(yè)式管理的數(shù)據(jù)結(jié)構(gòu) 在頁(yè)式系統(tǒng)中進(jìn)程建立時(shí)，操作系統(tǒng)為進(jìn)程中所有的頁(yè)分配頁(yè)框。當(dāng)進(jìn)程撤銷(xiāo)時(shí)收回所有分配給它的頁(yè)框。在程序的運(yùn)行期間，如果允許進(jìn)程動(dòng)態(tài)地申請(qǐng)空間，操作系統(tǒng)還要為進(jìn)程申請(qǐng)的空間分配物理頁(yè)框。操作系統(tǒng)為了完成這些

21、功能，必須記錄系統(tǒng)內(nèi)存中實(shí)際的頁(yè)框使用情況。操作系統(tǒng)還要在進(jìn)程切換時(shí)，正確地切換兩個(gè)不同的進(jìn)程地址空間到物理內(nèi)存空間的映射。這就要求操作系統(tǒng)要記錄每個(gè)進(jìn)程頁(yè)表的相關(guān)信息。為了完成上述的功能，個(gè)頁(yè)式系統(tǒng)中，一般要采用如下的數(shù)據(jù)結(jié)構(gòu)。 進(jìn)程頁(yè)表：完成邏輯頁(yè)號(hào)(本進(jìn)程的地址空間)到物理頁(yè)面號(hào)(實(shí)際內(nèi)存空間，也叫塊號(hào))的映射。 每個(gè)進(jìn)程有一個(gè)頁(yè)表，描述該進(jìn)程占用的物理頁(yè)面及邏輯排列順序，如圖： 圖4-1 頁(yè)表 物理頁(yè)面表：整個(gè)系統(tǒng)有一個(gè)物理頁(yè)面表，描述物理內(nèi)存空間的分配使用狀況，其數(shù)據(jù)結(jié)構(gòu)可采用位示圖和空閑頁(yè)鏈表。 對(duì)于位示圖法，即如果該頁(yè)面已被分配，則對(duì)應(yīng)比特位置1，否置0. 圖4-2 頁(yè)面表 請(qǐng)求

22、表：整個(gè)系統(tǒng)有一個(gè)請(qǐng)求表，描述系統(tǒng)內(nèi)各個(gè)進(jìn)程頁(yè)表的位置和大小，用于地址轉(zhuǎn)換也可以結(jié)合到各進(jìn)程的PCB(進(jìn)程控制塊)里。如圖： 圖4-3 請(qǐng)求表4.3 頁(yè)式管理地址變換 在頁(yè)式系統(tǒng)中，指令所給出的地址分為兩部分：邏輯頁(yè)號(hào)和頁(yè)內(nèi)地址。 原理：CPU中的內(nèi)存管理單元(MMU)按邏輯頁(yè)號(hào)通過(guò)查進(jìn)程頁(yè)表得到物理頁(yè)框號(hào)，將物理頁(yè)框號(hào)與頁(yè)內(nèi)地址相加形成物理地址(見(jiàn)圖4-4)。 邏輯頁(yè)號(hào)，頁(yè)內(nèi)偏移地址>查進(jìn)程頁(yè)表，得物理頁(yè)號(hào)>物理地址： 圖4-4 頁(yè)式管理的地址變換 上述過(guò)程通常由處理器的硬件直接完成，不需要軟件參與。通常，操作系統(tǒng)只需在進(jìn)程切換時(shí)，把進(jìn)程頁(yè)表的首地址裝入處理器特定

23、的寄存器中即可。一般來(lái)說(shuō)，頁(yè)表存儲(chǔ)在主存之中。這樣處理器每訪問(wèn)一個(gè)在內(nèi)存中的操作數(shù)，就要訪問(wèn)兩次內(nèi)存： 第一次用來(lái)查找頁(yè)表將操作數(shù)的 邏輯地址變換為物理地址； 第二次完成真正的讀寫(xiě)操作。 這樣做時(shí)間上耗費(fèi)嚴(yán)重。為縮短查找時(shí)間，可以將頁(yè)表從內(nèi)存裝入CPU內(nèi)部的關(guān)聯(lián)存儲(chǔ)器(例如，快表) 中，實(shí)現(xiàn)按內(nèi)容查找。此時(shí)的地址變換過(guò)程是：在CPU給出有效地址后，由地址變換機(jī)構(gòu)自動(dòng)將頁(yè)號(hào)送人快表，并將此頁(yè)號(hào)與快表中的所有頁(yè)號(hào)進(jìn)行比較，而且這 種比較是同時(shí)進(jìn)行的。若其中有與此相匹配的頁(yè)號(hào)，表示要訪問(wèn)的頁(yè)的頁(yè)表項(xiàng)在快表中。于是可直接讀出該頁(yè)所對(duì)應(yīng)的物理頁(yè)號(hào)，這樣就無(wú)需訪問(wèn)內(nèi)存中的頁(yè)表。由于關(guān)聯(lián)存儲(chǔ)器的訪問(wèn)速度比內(nèi)

24、存的訪問(wèn)速度快得多。 5. 段式存儲(chǔ)管理5.1 基本原理 在段式存儲(chǔ)管理中，將程序的地址空間劃分為若干個(gè)段(segment)，這樣每個(gè)進(jìn)程有一個(gè)二維的地址空間。在前面所介紹的動(dòng)態(tài)分區(qū)分配方式中，系統(tǒng)為整個(gè)進(jìn)程分配一個(gè)連續(xù)的內(nèi)存空間。而在段式存儲(chǔ)管理系統(tǒng)中，則為每個(gè)段分配一個(gè)連續(xù)的分區(qū)，而進(jìn)程中的各個(gè)段可以不連續(xù)地存放在內(nèi)存的不同分區(qū)中。程序加載時(shí)，操作系統(tǒng)為所有段分配其所需內(nèi)存，這些段不必連續(xù)，物理內(nèi)存的管理采用動(dòng)態(tài)分區(qū)的管理方法。 在為某個(gè)段分配物理內(nèi)存時(shí)，可以采用首先適配法、下次適配法、最佳適配法等方法。 在回收某個(gè)段所占用的空間時(shí)，要注意將收回的空間與其相鄰的空間合并。 段式存儲(chǔ)管理也需

25、要硬件支持，實(shí)現(xiàn)邏輯地址到物理地址的映射。 程序通過(guò)分段劃分為多個(gè)模塊，如代碼段、數(shù)據(jù)段、共享段： 可以分別編寫(xiě)和編譯 可以針對(duì)不同類(lèi)型的段采取不同的保護(hù) 可以按段為單位來(lái)進(jìn)行共享，包括通過(guò)動(dòng)態(tài)鏈接進(jìn)行代碼共享 這樣做的優(yōu)點(diǎn)是：可以分別編寫(xiě)和編譯源程序的一個(gè)文件，并且可以針對(duì)不同類(lèi)型的段采取不同的保護(hù)，也可以按段為單位來(lái)進(jìn)行共享。 總的來(lái)說(shuō)，段式存儲(chǔ)管理的優(yōu)點(diǎn)是：沒(méi)有內(nèi)碎片，外碎片可以通過(guò)內(nèi)存緊縮來(lái)消除；便于實(shí)現(xiàn)內(nèi)存共享。缺點(diǎn)與頁(yè)式存儲(chǔ)管理的缺點(diǎn)相同，進(jìn)程必須全部裝入內(nèi)存。5.2 段式管理的數(shù)據(jù)結(jié)構(gòu) 為了實(shí)現(xiàn)段式管理，操作系統(tǒng)需要如下的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)進(jìn)程的地址空間到物理內(nèi)存空間的映射，并跟蹤物理內(nèi)存的使用情況，以便在裝入新的段的時(shí)候，合理地分