《操作系統(tǒng)內(nèi)存管理.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《操作系統(tǒng)內(nèi)存管理.doc（26頁珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

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)是，最簡單，適用于單用戶、單任務(wù)的操作系統(tǒng)。CPM和 DOS20以下就是采用此種方式.這種方式的最大優(yōu)點(diǎ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è)新的問題：內(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è)類型相同的對(duì)象）。分區(qū)大小也可以不等：有多個(gè)小分區(qū)、適量的中等分區(qū)以及少量的大分區(qū)。根據(jù)程序的大小，分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。 優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開銷小. 缺點(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í)行過程中通過系統(tǒng)調(diào)用進(jìn)行分配或改變分區(qū)大小。與固定分區(qū)相比較其優(yōu)點(diǎn)是：沒有內(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ū)釋放過程中有一個(gè)要注意的問題是,將相鄰的空閑分區(qū)合并成一個(gè)大的空閑分區(qū)。下面列出了幾種常用的分區(qū)分配算法: 最先適配法(nrstfit）:按分區(qū)在內(nèi)存的先后次序從頭查找，找到符合要求的第一個(gè)分區(qū)進(jìn)行分配。該算法的分配和釋放的時(shí)

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

6、存的先后次序從頭查找，找到最大的空閑分區(qū)進(jìn)行分配。基本不留下小空閑分區(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)開銷較大?；锇橄到y(tǒng)方式是對(duì)以上兩種內(nèi)存方式的一種折衷方案。 伙伴系統(tǒng)規(guī)定，無論已分配分區(qū)或空閑分區(qū),其大小均為 2 的 k 次冪，k 為整數(shù)， lkm，其中： 21 表示分配的最小分區(qū)的大小， 2m 表示分配的最大分區(qū)的大小，

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

8、耗盡，則在分區(qū)大小為2（i1)的空閑分區(qū)鏈表中尋找。 若存在 2(i1)的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一對(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）的空閑分區(qū)，

9、以此類推。 由此可見，在最壞的情況下,可能需要對(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ū)，依此類推。 在伙伴系統(tǒng)中，其分配和回收的時(shí)間性能取決于查找空閑分區(qū)的位置和分割、合并空閑分區(qū)所花費(fèi)的時(shí)間。與前面所述的多種方法相比較，由于該算法在回收空閑分區(qū)時(shí)，需要對(duì)空閑分區(qū)進(jìn)行合并，所以其時(shí)間性能比前面所述的分類搜索算法差，但比順序搜索算法好

10、，而其空間性能則遠(yuǎn)優(yōu)于前面所述的分類搜索法，比順序搜索法略差。 需要指出的是，在當(dāng)前的操作系統(tǒng)中,普遍采用的是下面將要講述的基于分頁和分段機(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ǔ)過程中，不管哪個(gè)時(shí)刻，可利用空間都是一個(gè)地址連續(xù)的存儲(chǔ)區(qū),在編譯程序中稱之為堆”，每次分配都是從這個(gè)可利用空間中劃出一塊。其實(shí)現(xiàn)辦法是:設(shè)立一個(gè)指針,稱之為堆指針，始終指向堆的最低（或鍛聯(lián)）地址。當(dāng)用戶申請(qǐng)N個(gè)單位的存儲(chǔ)塊時(shí),堆指針向高地址（或 低地址）稱動(dòng)N個(gè)存儲(chǔ)單位，而移動(dòng)之前的堆指針的值就是分配給用戶的占用塊的初始地址。例如，某個(gè)串處理系統(tǒng)中有A、B、C、D這4個(gè)串，其串值長度分別為12,6，10和8。 假設(shè)堆指針free的初值為零，則分配給這4個(gè)串值的存儲(chǔ)空間的初始地址分別為0。12.18和28,如圖8。12(a)和（b

12、)所示，分配后的堆指針的值為36。 因此，這種堆結(jié)構(gòu)的存儲(chǔ)管理的分配算法非常簡單, 釋放內(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í)行過程中不回收用戶隨時(shí)釋放的存儲(chǔ)塊，直到可利用空同不夠分配或堆指針指向最高地址時(shí)才進(jìn)行存儲(chǔ)緊縮。此時(shí)緊縮的

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

14、 設(shè)立長度域（存儲(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ū)的最低地址)。 可見,存儲(chǔ)緊縮法比無用單元收集法更為復(fù)雜,前者不僅要傳送數(shù)據(jù)（進(jìn)行占用塊遷移）,而且還有需要修改所有占用塊中的指針值。因此，存儲(chǔ)緊縮也是個(gè)系統(tǒng)操作，且非不得已就不用。 3. 覆蓋和交換技術(shù) 3。1 覆蓋技術(shù) 引入覆蓋 （ove