計(jì)算機(jī)操作系統(tǒng)第7章 存儲(chǔ)器管理

1、第第7章章 存儲(chǔ)器管理存儲(chǔ)器管理7。1 有關(guān)概念有關(guān)概念n這里所說的存儲(chǔ)器指的是主存（內(nèi)存、隨機(jī)存儲(chǔ)器（這里所說的存儲(chǔ)器指的是主存（內(nèi)存、隨機(jī)存儲(chǔ)器（RAM：Random Access Memory）；）；n主存空間分為兩大部分：主存空間分為兩大部分：n系統(tǒng)區(qū)：用以存放操作系統(tǒng)及其工作區(qū)；系統(tǒng)區(qū)：用以存放操作系統(tǒng)及其工作區(qū)；n用戶區(qū)：由多個(gè)進(jìn)程分配使用；用戶區(qū)：由多個(gè)進(jìn)程分配使用；n系統(tǒng)區(qū)不存在管理問題，存儲(chǔ)管理的對象是用戶區(qū)；系統(tǒng)區(qū)不存在管理問題，存儲(chǔ)管理的對象是用戶區(qū)；n存儲(chǔ)器管理的目的是要使內(nèi)存空間得到充分有效和安全有存儲(chǔ)器管理的目的是要使內(nèi)存空間得到充分有效和安全有序的使用。序的使用。

2、系統(tǒng)區(qū)用戶區(qū)存儲(chǔ)管理的對象是主存的用戶區(qū)存儲(chǔ)器管理的功能存儲(chǔ)器管理的功能n空間分配：空間分配：在多個(gè)進(jìn)程之間分配和回收存儲(chǔ)空間；n地址變換：地址變換：將邏輯地址變換為物理地址；n存儲(chǔ)保護(hù)：存儲(chǔ)保護(hù)：防止因用戶程序錯(cuò)誤破壞系統(tǒng)或其他用戶，防止程序之間的相互干擾；n存儲(chǔ)擴(kuò)充：存儲(chǔ)擴(kuò)充：在邏輯上為用戶提供一個(gè)比實(shí)際內(nèi)存更大的存儲(chǔ)空間。地址及地址變換地址及地址變換n地址（地址（Address），），是存儲(chǔ)空間中某個(gè)可訪問單元的編號，它又分邏輯地址和物理地址； 邏輯地址：邏輯地址：編程時(shí)所使用的地址，又稱相對地址、虛地址； 邏輯空間：邏輯空間：邏輯地址的集合，有時(shí)就叫地址空間； 物理地址：物理地址：內(nèi)存

3、中的地址，又稱絕對地址、實(shí)地址； 物理空間：物理空間：物理地址的集合，也叫存儲(chǔ)空間，主存空間；n地址變換：地址變換：將邏輯地址轉(zhuǎn)換為物理地址，又稱地址映射、地址重定位。 地址變換分為兩類：n靜態(tài)地址變換；n動(dòng)態(tài)地址變換；靜態(tài)地址變換靜態(tài)地址變換 mov ax,500 mov ax,500 54321 54321 mov ax,1000+500 mov ax,1000+500 54321 54321 0100500999 0 1000 1100 1500 19991M-1程序的地址空間主存空間重定位裝入程序在程序裝入時(shí)一次完在程序裝入時(shí)一次完成，以后不再改變。成，以后不再改變。靜態(tài)重定位時(shí)只須修

4、改指令內(nèi)部的地址；修改后靜態(tài)重定位時(shí)只須修改指令內(nèi)部的地址；修改后CPU以物理地址執(zhí)行程序。以物理地址執(zhí)行程序。動(dòng)態(tài)地址變換動(dòng)態(tài)地址變換 mov ax,500mov ax,500 54321 54321 mov ax,500mov ax,500 54321 54321 0100500999 0 1000 1100 1500 19991M-1作業(yè)的地址空間存儲(chǔ)空間5001000邏輯地址重定位寄存器在程序執(zhí)行的過在程序執(zhí)行的過程中動(dòng)態(tài)地進(jìn)行。程中動(dòng)態(tài)地進(jìn)行。CPU以邏輯地址執(zhí)行程序，在執(zhí)行中動(dòng)態(tài)地將邏輯地址轉(zhuǎn)換成物理地址。以邏輯地址執(zhí)行程序，在執(zhí)行中動(dòng)態(tài)地將邏輯地址轉(zhuǎn)換成物理地址。7.2 分區(qū)存儲(chǔ)

5、管理分區(qū)存儲(chǔ)管理n本章講述的存儲(chǔ)管理方法包括分區(qū)管理、分頁管理、分段管理和段頁式管理等。這里先說分區(qū)管理；n分區(qū)存儲(chǔ)管理是多道程序系統(tǒng)中采用的一種最簡單的存儲(chǔ)管理方法。它把內(nèi)存的用戶空間劃分為若干大小不等的區(qū)域，每個(gè)進(jìn)程（每道程序）占用一個(gè)區(qū)域；n分區(qū)存儲(chǔ)管理又分為：n固定分區(qū)管理；n動(dòng)態(tài)分區(qū)管理；7。2。1 固定分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理n方法：方法：固定分區(qū)存儲(chǔ)管理方法將內(nèi)存空間劃分為若干個(gè)固定大小的分區(qū)，每個(gè)分區(qū)中可以裝入一道程序。分區(qū)的個(gè)數(shù)及每個(gè)分區(qū)的位置和大小在運(yùn)行期間不能改變；n管理：管理：系統(tǒng)需要建立一張分區(qū)使用表，以記錄系統(tǒng)中的分區(qū)數(shù)目、分區(qū)大小、分區(qū)起始地址及狀態(tài)；n分配：

6、分配：當(dāng)有用戶程序要裝入時(shí)，由內(nèi)存分配程序檢索分區(qū)使用表，從中找出一個(gè)能滿足要求的空閑分區(qū)分配給該程序，然后修改分區(qū)說明表中相應(yīng)表項(xiàng)的狀態(tài)；若找不到大小足夠的分區(qū)，則拒絕分配內(nèi)存；n回收：回收：當(dāng)某程序執(zhí)行完畢時(shí)，釋放程序占用的分區(qū)，管理程序只需將對應(yīng)分區(qū)的狀態(tài)置為未分配即可；n特點(diǎn)：特點(diǎn)：管理簡單但存儲(chǔ)空間利用率較低。固定分區(qū)管理舉例 操作系統(tǒng) 分區(qū)號 大小 起始地址 狀態(tài) 1 8KB 20KB 已分配 2 32KB 28KB 已分配 3 32KB 60KB 未分配 4 120KB 92KB 未分配 5 300KB 212KB 已分配 0 20KB 28KB 60KB 92KB 212KB5

7、12KB-1進(jìn)程A（6K）進(jìn)程B（24K）進(jìn)程C（128K）1 2 3 4 57。2。2 動(dòng)態(tài)分區(qū)存儲(chǔ)管理動(dòng)態(tài)分區(qū)存儲(chǔ)管理n動(dòng)態(tài)分區(qū)存儲(chǔ)管理又稱為可變分區(qū)存儲(chǔ)管理，這種管理方法是在系統(tǒng)的運(yùn)行過程中動(dòng)態(tài)地產(chǎn)生和回收分區(qū)。系統(tǒng)初啟時(shí)，整個(gè)用戶空間就是一個(gè)分區(qū)，然后根據(jù)運(yùn)行的需要，在分配和回收的過程中逐漸產(chǎn)生和合并新的分區(qū)。因此，在這種方法下，系統(tǒng)內(nèi)分區(qū)的個(gè)數(shù)及每個(gè)分區(qū)的大小都是動(dòng)態(tài)變化的。系統(tǒng)空間用戶空間系統(tǒng)初啟時(shí)，整個(gè)用戶空間就是一個(gè)分區(qū)。動(dòng)態(tài)分區(qū)管理中的數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)分區(qū)管理中的數(shù)據(jù)結(jié)構(gòu)n在動(dòng)態(tài)分區(qū)管理中常用的數(shù)據(jù)結(jié)構(gòu)有：n空閑分區(qū)表：空閑分區(qū)表：用一個(gè)空閑分區(qū)表來登記系統(tǒng)中的空閑分區(qū)，表項(xiàng)內(nèi)容

8、包括分區(qū)的大小和起始地址；n空閑分區(qū)鏈：空閑分區(qū)鏈：在空閑分區(qū)內(nèi)部拿出一點(diǎn)空間用以建立鏈表，將所有的空閑分區(qū)鏈接起來，構(gòu)成空閑分區(qū)鏈，供空間分配和回收時(shí)查詢；n比較而言，空閑分區(qū)表查詢起來速度較快，但需要額外的空間開銷；空閑分區(qū)鏈查詢起來較慢，但不需要額外的空間開銷，其用以建立鏈表的空間也可以供分配。空閑分區(qū)表示意圖空閑分區(qū)表示意圖分區(qū)號 大小 起始地址 1 8KB 24KB 2 12KB 128KB 3 8KB 248KB 4 5 操作系統(tǒng) 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K) 空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256

9、KB-1空閑分區(qū)鏈?zhǔn)疽鈭D空閑分區(qū)鏈?zhǔn)疽鈭D 操作系統(tǒng) 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K) 空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1 操作系統(tǒng) 空閑 (8K) 已分 (96K) 空閑 (12K) 已分 (108K) 空閑 (8K) 0 24KB 32KB 128KB 140KB 248KB256KB-1表頭指針分區(qū)分配算法分區(qū)分配算法n目前常用的分區(qū)分配算法有以下幾種：目前常用的分區(qū)分配算法有以下幾種：n首次適應(yīng)算法（FF：First Fit）；n循環(huán)首次適應(yīng)算法（RFF：Round First Fit）；n最佳適

10、應(yīng)算法（BF：Best Fit）；n最壞適應(yīng)算法（WF：Worst Fit）；首次適應(yīng)算法首次適應(yīng)算法n首次適應(yīng)算法又稱最先適應(yīng)算法，該算法要求空閑分區(qū)按首地址遞增的次序排列；n在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表（或空閑分區(qū)鏈）頭開始順序查找，直到找到第一個(gè)能滿足其大小要求的空閑分區(qū)為止；n然后，再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空間，要么作為新的空閑分區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中，要么作為碎片丟掉；n首次適應(yīng)法的特點(diǎn)首次適應(yīng)法的特點(diǎn)：優(yōu)先利用內(nèi)存低地址端，以便高地址端逐漸形成大的空閑區(qū)；但低地址端有許多小空閑分區(qū)時(shí)會(huì)增加查找開銷。循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)

11、算法n循環(huán)首次適應(yīng)算法又稱下次適應(yīng)算法，它是首次適應(yīng)算法的變形；n該算法在為進(jìn)程分配內(nèi)存空間時(shí)，從上次停下的位置開始查找，直到找到第一個(gè)能滿足其大小要求的空閑分區(qū)為止；n然后，再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空間要么作為新的空閑分區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中，要么作為碎片丟掉；n循環(huán)首次適應(yīng)法的特點(diǎn)：循環(huán)首次適應(yīng)法的特點(diǎn)：使存儲(chǔ)空間的利用更加均衡，但會(huì)使系統(tǒng)缺乏大的空閑分區(qū)。最佳適應(yīng)算法最佳適應(yīng)算法n最佳適應(yīng)算法要求空閑分區(qū)按容量大小遞增的次序排列；n在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表（或空閑分區(qū)鏈）頭開始順序查找，直到找到第一個(gè)能滿足其大小要求的空閑分區(qū)為

12、止；n如果該空閑分區(qū)大于作業(yè)的大小，則從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，將剩余空間要么作為新的空閑區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中，要么作為碎片丟掉；n最佳適應(yīng)算法的特點(diǎn)：最佳適應(yīng)算法的特點(diǎn)：按最佳適應(yīng)算法為作業(yè)分配內(nèi)存，就能把既滿足要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)，這樣就可以保留大的空閑區(qū)以備大作業(yè)使用，但分割后的剩余空閑區(qū)很小，往往會(huì)被作為碎片丟掉。最壞適應(yīng)算法最壞適應(yīng)算法n最壞適應(yīng)算法要求空閑分區(qū)按容量大小遞減的次序排列；n在進(jìn)行內(nèi)存分配時(shí)，只檢查空閑分區(qū)表（或空閑分區(qū)鏈）中的第一個(gè)空閑分區(qū)，若第一個(gè)空閑分區(qū)小于作業(yè)要求的大小，則分配失??；n否則從該空閑分區(qū)中劃出與

13、作業(yè)大小相等的一塊內(nèi)存空間分配給請求者，余下的空間要么作為新的空閑分區(qū)仍然留在空閑分區(qū)表（或空閑分區(qū)鏈）中，要么作為碎片丟掉；n最壞適應(yīng)法的特點(diǎn)：最壞適應(yīng)法的特點(diǎn)：剩下的空閑區(qū)比較大，但當(dāng)大作業(yè)到來時(shí)，其存儲(chǔ)空間的申請往往得不到滿足。舉例舉例n下表給出了某系統(tǒng)的空閑分區(qū)表，系統(tǒng)采用可變式分區(qū)存儲(chǔ)管理策略。現(xiàn)有以下作業(yè)序列：96K、20K、200K。若用首次適應(yīng)算法首次適應(yīng)算法和最佳適應(yīng)算法最佳適應(yīng)算法來處理這些作業(yè)序列，試問哪一種算法可以滿足該作業(yè)序列的請求?分區(qū)號 大小起始地址132K100K210K150K35K200K4218K220K596K530K采用最佳適應(yīng)算法分配采用最佳適應(yīng)算法

14、分配1n申請96K，n選中4號分區(qū)，4號分區(qū)大小與申請空間大小一致，應(yīng)從空閑分區(qū)表中刪去該表項(xiàng) ，5號記錄順序上移；分區(qū)號 大小起始地址15K200K210K150K332K100K496K530K5218K220K分區(qū)號 大小起始地址15K200K210K150K332K100K4218K220K采用最佳適應(yīng)算法分配采用最佳適應(yīng)算法分配2n申請20K，n選中3號分區(qū)，分配后還剩下12K；分區(qū)號 大小起始地址15K200K210K150K332K100K4218K220K分區(qū)號 大小起始地址15K200K210K150K312K100K4218K220K采用最佳適應(yīng)算法分配采用最佳適應(yīng)算法分配

15、3n申請200K,n選中4號分區(qū)，分配后剩下18K；n可見，采用最佳適應(yīng)法是可以滿足分配要求的。分區(qū)號 大小起始地址15K200K210K150K312K100K4218K220K分區(qū)號 大小起始地址15K200K210K150K312K100K418K220K采用首次適應(yīng)算法分配采用首次適應(yīng)算法分配1n申請96K，n選中4號分區(qū)，進(jìn)行分配后還剩下122K；分區(qū)號 大小起始地址132K100K210K150K35K200K4218K220K596K530K分區(qū)號 大小起始地址132K100K210K150K35K200K4122K220K596K530K采用首次適應(yīng)算法分配采用首次適應(yīng)算法分配

16、2n申請20K，n選中1號分區(qū)，分配后剩下12K；分區(qū)號 大小起始地址132K100K210K150K35K200K4122K220K596K530K分區(qū)號 大小起始地址112K100K210K150K35K200K4122K220K596K530K采用首次適應(yīng)算法分配采用首次適應(yīng)算法分配3n申請200K，n現(xiàn)有的五個(gè)分區(qū)都無法滿足要求，該作業(yè)等待；n顯然采用首次適應(yīng)算法顯然采用首次適應(yīng)算法進(jìn)行內(nèi)存分配，無法滿進(jìn)行內(nèi)存分配，無法滿足該作業(yè)序列的需求。足該作業(yè)序列的需求。分區(qū)號 大小起始地址112K100K210K150K35K200K4122K220K596K530K空間分配程序空間分配程序n

17、以首次適應(yīng)以首次適應(yīng)算法及空閑算法及空閑鏈表為例，鏈表為例，申請分區(qū)大申請分區(qū)大小為小為x， e是是“碎片碎片”大大小的閥值。小的閥值。將剩余量作為“碎片”丟掉開始查表是鏈表尾？本次無法分配，返回YN空閑區(qū)容量x?N繼續(xù)檢查下一項(xiàng)容量xe?YYN將剩余量作為新的分區(qū)留在鏈表中將空間分配給請求者，修改鏈表分配舉例分配舉例n假設(shè)x=40k，e=2k，t為分得空間的始地址；操作系統(tǒng)用戶空間20K42K24Khead40k注意注意:本程序是將高地址部分本程序是將高地址部分的的40K分出去，為什么分出去，為什么要這樣做呢？要這樣做呢？2KP=head=16KP指向的分區(qū)為20K，不夠分；Q=P=16K；

18、P=P-link=64K；P指向的分區(qū)夠分，分出40K；P-size=P-size-40K=2K；2K=閥值，作為新的空閑分區(qū)留在鏈表內(nèi)；t=P+P-size=64K+2K=66K，返回給申請者；16K64K128KnVoid cmalloc(node * head, int x)n node *p, *q, *t;n p=head;n while ( p-sizelink; n if ( p!=nil )n p -size= p-size-x;n if (p-size link= p- link;n else t=p+ p-size;n n else t=0; printf （“本次無法分配

19、！”n）；n return (t);n 分區(qū)回收程序分區(qū)回收程序n回收分區(qū)時(shí)，如果回收區(qū)鄰接空閑區(qū)，則應(yīng)將它們合并，回收分區(qū)時(shí)，如果回收區(qū)鄰接空閑區(qū)，則應(yīng)將它們合并，鄰接有四種情況，見鄰接有四種情況，見P129。找到回收區(qū)在鏈表中的位置回收區(qū)上、下都鄰接空閑區(qū)嗎？三區(qū)合并下鄰接嗎？兩區(qū)合并上鄰接嗎？兩區(qū)合并回收區(qū)插入鏈表ynynny返回內(nèi)存保護(hù)內(nèi)存保護(hù)n存儲(chǔ)保護(hù)的主要含義是防止程序間的相互干擾和破壞，方法是禁止越界訪問；n常用的存儲(chǔ)保護(hù)方法有：n上下界寄存器法；n基址限長寄存器法；n上下界寄存器法：n用上、下界寄存器分別存放作業(yè)存儲(chǔ)空間的結(jié)束地址和開始地址；n在作業(yè)運(yùn)行過程中，將每一個(gè)訪問內(nèi)存

20、的地址都同這兩個(gè)寄存器的內(nèi)容進(jìn)行比較，若超出了上下界寄存器的范圍則產(chǎn)生越界中斷；n基址、限長寄存器法：n用基址和限長寄存器分別存放作業(yè)存儲(chǔ)空間的起始地址及作業(yè)長度；n當(dāng)作業(yè)執(zhí)行時(shí)，將每一個(gè)訪問內(nèi)存的相對地址和這個(gè)限長寄存器比較，若邏輯地址超過限長則產(chǎn)生越界中斷。7。2。3 碎片問題及拼接技術(shù)碎片問題及拼接技術(shù)n分區(qū)存儲(chǔ)管理中，必須把作業(yè)裝入到一片連續(xù)的內(nèi)存空間中。這種分配方法能滿足多道程序設(shè)計(jì)的需要，但存在碎片問題； n碎片也可稱為零頭，是指內(nèi)存中無法被利用的存儲(chǔ)空間；n碎片分內(nèi)部碎片和外部碎片： 內(nèi)部碎片是指分配給作業(yè)的存儲(chǔ)空間中未被利用的部分；外部碎片是指系統(tǒng)中無法利用的小存儲(chǔ)塊；n解決碎

21、片問題的方法之一，是通過移動(dòng)把多個(gè)分散的小碎片拼接成一個(gè)大的空閑區(qū)，也可稱為緊縮或緊湊；n拼接的時(shí)空開銷較大。拼接示意圖拼接示意圖n拼接前 拼接后 操作系統(tǒng) 進(jìn)程5 空閑（10KB） 進(jìn)程4 空閑（30KB） 進(jìn)程3 空閑（26KB） 0 40KB 90KB 100KB 170KB 200KB 230KB256KB-1 操作系統(tǒng) 進(jìn)程5 進(jìn)程4 進(jìn)程3 空閑（66KB） 0 40KB 90KB 160KB 190KB 256KB-1拼接需要的技術(shù)支持拼接需要的技術(shù)支持n動(dòng)態(tài)重定位：動(dòng)態(tài)重定位：拼接后程序在內(nèi)存的位置發(fā)生變化，因此需要?jiǎng)討B(tài)重定位技術(shù)支持；n空閑區(qū)放在何處：空閑區(qū)放在何處：拼接后的

22、空閑區(qū)放在何處不能一概而論，應(yīng)根據(jù)移動(dòng)信息量的多少來決定；n拼接的時(shí)機(jī)：拼接的時(shí)機(jī)：n回收分區(qū)時(shí)拼接：只有一個(gè)空閑區(qū)，但拼接頻率過高增加系統(tǒng)開銷；n找不到足夠大的空閑區(qū)且系統(tǒng)空閑空間總量能滿足要求時(shí)：拼接頻率小于前者，空閑區(qū)管理稍復(fù)雜。也可以只拼接部分空閑區(qū)。7.3 伙伴系統(tǒng)伙伴系統(tǒng)n固定分區(qū)存儲(chǔ)管理限制了內(nèi)存中的進(jìn)程數(shù)，動(dòng)態(tài)分區(qū)的拼接需要大量時(shí)間，而伙伴系統(tǒng)是一種較為實(shí)用的動(dòng)態(tài)存儲(chǔ)管理辦法；n伙伴系統(tǒng)采用伙伴算法對空閑內(nèi)存進(jìn)行管理。系統(tǒng)初啟時(shí)，整個(gè)用戶區(qū)就是一個(gè)空閑塊，然后，在運(yùn)行的過程中通過不斷對分大的空閑塊來獲得小的空閑塊，對分出來的空閑塊稱為“伙伴”（Buddy），每個(gè)空閑塊的大小為2

23、i；n當(dāng)內(nèi)存塊釋放時(shí)，應(yīng)盡可能合并它的伙伴空閑塊；n伙伴系統(tǒng)的主要優(yōu)點(diǎn)是分配和回收空間的時(shí)間開銷比最佳適應(yīng)法和首次適應(yīng)法要小，其缺點(diǎn)是可能浪費(fèi)許多存儲(chǔ)空間?；锇橄到y(tǒng)的分配和回收伙伴系統(tǒng)的分配和回收n伙伴系統(tǒng)的存儲(chǔ)分配方法是：伙伴系統(tǒng)的存儲(chǔ)分配方法是： 當(dāng)進(jìn)程申請大小為n的空間時(shí)，設(shè)2i-1n2i，則為進(jìn)程分配大小為2i的空間；如系統(tǒng)不存在大小為2i的空閑塊，則查找系統(tǒng)中是否存在大于2i的空閑塊，若找到則對其進(jìn)行對半劃分，直到產(chǎn)生大小為2i的空閑塊為止。n伙伴系統(tǒng)的存儲(chǔ)回收方法是：伙伴系統(tǒng)的存儲(chǔ)回收方法是： 當(dāng)進(jìn)程釋放存儲(chǔ)空間時(shí)，應(yīng)檢查釋放塊的伙伴是否空閑，若空閑則合并；這個(gè)較大的空閑塊也可能存

24、在空閑伙伴，此時(shí)也應(yīng)合并；重復(fù)上述過程，直至沒有可以合并的伙伴為止?；锇榈刂酚?jì)算公式伙伴地址計(jì)算公式n設(shè)某空閑塊的開始地址為d，長度為2K，其伙伴的開始地址為：nBuddy（k，d）=d+2k，若d % 2k+1=0nBuddy（k，d）=d-2k， 若d % 2k+1= 2kn如果參與分配的2m個(gè)單元從a開始，則長度為2K、開始地址為d的塊，其伙伴的開始地址為：nBuddy（k，d）=d+2k，若（d-a）% 2k+1=0nBuddy（k，d）=d-2k， 若（d-a）% 2k+1= 2k伙伴系統(tǒng)分配及回收的舉例伙伴系統(tǒng)分配及回收的舉例n設(shè)系統(tǒng)中初始內(nèi)存空間大小為1MB，進(jìn)程請求和釋放空間的

25、操作序列為：n進(jìn)程A申請200KB；B申請120KB；C申請240KB； D申請100KB；n進(jìn)程B釋放；E申請60KB；n進(jìn)程A、C釋放；n進(jìn)程D釋放；進(jìn)程E釋放。E A釋放分配過程示意圖分配過程示意圖n 0 128K 256K 384K 512K 640K 768K 896K 1M初始狀態(tài)A申請200B申請120C申請240D申請100 B釋放 E申請60 C釋放 D釋放 E釋放512K256KAA512K128KBAB256KCAB256KCDA256KCD128KA256KCD64E256KCD64E256KD64256K512KE64256K512K128K128K伙伴系統(tǒng)的二叉樹表

26、示伙伴系統(tǒng)的二叉樹表示n可以用二叉樹表示內(nèi)存分配情況。葉結(jié)點(diǎn)表示存儲(chǔ)器中的當(dāng)前分區(qū)，如果兩個(gè)伙伴是葉子，則至少有一個(gè)被分配。n右圖表示A（200）、B（120）、C（240）、D（100）分配之后的情況。ABDC1M512K256K128K7.4 分頁存儲(chǔ)管理分頁存儲(chǔ)管理7。4。1 基本原理基本原理n分區(qū)管理中，要求將一道程序裝在內(nèi)存的一片連續(xù)的空間，這有可能降低空間的利用率，或者加大緊湊和拼接的時(shí)間開銷。為了克服這種缺點(diǎn)，提出了分頁管理的思想和方法；n在分頁存儲(chǔ)管理中，將程序的邏輯地址空間和主存的物理空間按同樣的大小劃分成若干個(gè)頁面（塊），為了區(qū)分，邏輯空間的叫“頁”（page），物理空間的

27、叫“塊”（block）。然后，以塊（頁）為單位為進(jìn)程分配空間。這樣，同一道程序就可以裝在若干個(gè)不連續(xù)的頁面內(nèi)，從而提高內(nèi)存空間的利用率。程序邏輯空間內(nèi)存物理空間012301234567從圖示的分配方法可以看出，一道程序在內(nèi)存是以頁面為單位存放的，同一道程序的頁面之間可以是不連續(xù)的，次序也是隨意的。7。4。2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)n為了支持分頁存儲(chǔ)管理，虛要建立以下數(shù)據(jù)結(jié)構(gòu)：為了支持分頁存儲(chǔ)管理，虛要建立以下數(shù)據(jù)結(jié)構(gòu)： 1，頁表（PT：Page Table）； 2，存儲(chǔ)分塊表（MBT：Memory Blocking Table）； 3，進(jìn)程請求表（PRT：Process Request Table）

28、； 下面逐一說明。下面逐一說明。頁表（頁表（PT）n頁表每個(gè)進(jìn)程一張，記錄該進(jìn)程每個(gè)頁面所分得的物頁表每個(gè)進(jìn)程一張，記錄該進(jìn)程每個(gè)頁面所分得的物理塊。理塊。內(nèi)存空間程序的地址空間頁表 0頁1頁2頁n頁 0 2 1 4 2 7 頁號 塊號01234567頁面大小的選擇頁面大小的選擇n頁面的大小應(yīng)適中。若頁面太大，以至和一般進(jìn)程大小相差無幾，則頁面分配退化為分區(qū)分配，同時(shí)頁內(nèi)碎片也較大。若頁面太小，雖然可減少頁內(nèi)碎片，但會(huì)導(dǎo)致頁表增長。因此，頁面大小應(yīng)適中，通常為2的冪，一般在512B到4KB之間。n頁表一般存放在內(nèi)存中。也可以在頁表中設(shè)置存取控制字段，以實(shí)現(xiàn)存儲(chǔ)保護(hù)。存儲(chǔ)分塊表（存儲(chǔ)分塊表（MB

29、T）n存儲(chǔ)分塊表用來記錄內(nèi)存中各物理塊的使用情況及未分配物理塊總數(shù)。n存儲(chǔ)分塊表可用下述方式表示：n位示圖：利用二進(jìn)制的一位表示一個(gè)物理塊的狀態(tài)，1表示一分配，0表示未分配。所有物理塊狀態(tài)位的集合構(gòu)成位示圖。n空閑存儲(chǔ)塊鏈：將所有的空閑存儲(chǔ)塊用鏈表鏈接起來，利用空閑物理塊中的單元存放指向下一個(gè)物理塊的指針。存儲(chǔ)分塊表（存儲(chǔ)分塊表（MBT）n存儲(chǔ)分塊表用來記錄內(nèi)存中各物理塊的使用情況及未分配物理塊總數(shù)；n存儲(chǔ)分塊表可用下述方式表示：n位示圖：位示圖：利用二進(jìn)制的一位表示一個(gè)物理塊的狀態(tài)，1表示已分配，0表示未分配。所有物理塊狀態(tài)位的集合構(gòu)成位示圖；n空閑存儲(chǔ)塊鏈：空閑存儲(chǔ)塊鏈：利用空閑物理塊中的

30、單元存放指向下一個(gè)物理塊的指針，將所有的空閑存儲(chǔ)塊用鏈表鏈接起來。 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4進(jìn)程請求表進(jìn)程請求表n請求表用來登記每個(gè)進(jìn)程的頁表在內(nèi)存中的物理位置及每個(gè)頁表的長度、狀態(tài)等。如下圖所示。進(jìn)程號 請求頁面數(shù)頁表始址頁表長度狀態(tài)010102410已分120103420已分215105415已分328未分 7。4。3 存儲(chǔ)空間的分配

31、及回收存儲(chǔ)空間的分配及回收n頁面分配：頁面分配：計(jì)算進(jìn)程所需頁面數(shù)，然后在請求表中登記進(jìn)程號、請求頁面數(shù)等。如存儲(chǔ)分塊表中有足夠的空閑塊可供進(jìn)程使用，則在系統(tǒng)中取得頁表始址，并在頁表中登記頁號及其對應(yīng)的物理塊號。否則無法分配；（見P138的程序）n頁面回收：頁面回收：將存儲(chǔ)分塊表中相應(yīng)的物理塊改為未分配，或?qū)⒒厥諌K加入到空閑存儲(chǔ)塊鏈中，并釋放頁表，修改請求表中的頁表始址及狀態(tài)；7。4。4 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)n地址變換機(jī)構(gòu)的任務(wù)是實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)地址變換機(jī)構(gòu)的任務(wù)是實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，即在程序動(dòng)態(tài)執(zhí)行的過程中，將換，即在程序動(dòng)態(tài)執(zhí)行的過程中，將CPU的訪存邏輯的訪存邏輯

32、地址變換成內(nèi)存的物理地址；地址變換成內(nèi)存的物理地址；n分頁地址變換機(jī)構(gòu)自動(dòng)地將邏輯地址分為頁號和頁內(nèi)分頁地址變換機(jī)構(gòu)自動(dòng)地將邏輯地址分為頁號和頁內(nèi)位移，例如，邏輯地址的長度為位移，例如，邏輯地址的長度為20位（邏輯空間的大位（邏輯空間的大小為小為220=1M），頁面大小為），頁面大小為1K，則頁內(nèi)位移量，則頁內(nèi)位移量W=10位（位（90，210=1K，注意：頁的大小一定是注意：頁的大小一定是2的整數(shù)次方的整數(shù)次方），頁號），頁號P=10位（位（1910），如下圖所），如下圖所示：示：19 10 9 019 10 9 0 頁頁 號號 P 頁頁 內(nèi)內(nèi) 位位 移移W地址變換過程地址變換過程n將頁號與

33、頁表長度進(jìn)行比較，如果頁號超過了頁表長度，則表示本次所訪問的地址已超越進(jìn)程的地址空間，系統(tǒng)產(chǎn)生地址越界中斷；n若未出現(xiàn)越界，則由頁表始址和頁號計(jì)算出相應(yīng)頁表項(xiàng)的位置，從中得到該頁的物理塊號；n將邏輯地址中的頁內(nèi)位移與上面得到的物理塊號拼接在一起，就形成了訪問主存的物理地址；地址變換示意圖地址變換示意圖n為什么是拼接而不是相加？為什么是拼接而不是相加？頁表寄存器頁表始址 頁表長度越界中斷邏輯地址 頁號（2） 頁內(nèi)位移（452）頁號 塊號2385101234 8 452物理地址頁表地址變換舉例地址變換舉例n設(shè)邏輯地址為20位，頁面大小為1K字節(jié)，作業(yè)的0、1、2頁分別存放在第2、3、8塊中。則邏輯

34、地址2500的頁號及頁內(nèi)地址分別為：2500/1024=2（頁號）；2500 %1024452（頁內(nèi)地址）；n查頁表可知第2頁對應(yīng)的物理塊號為8；n將塊號8與頁內(nèi)地址452拼接得到物理地址為： 810244528644；8644就是本次CPU訪存的物理地址。n2500（10）的二進(jìn)制表示是：的二進(jìn)制表示是：0000000010 0111000100 P W聯(lián)想（相聯(lián)）存儲(chǔ)器及快表聯(lián)想（相聯(lián)）存儲(chǔ)器及快表n因頁表放在主存中，故存取指令或數(shù)據(jù)時(shí)CPU至少要訪問兩次主存。降低了內(nèi)存訪問速度。n為了提高地址變換速度，可在地址變換機(jī)構(gòu)中增設(shè)一個(gè)具有并行查找能力的高速緩沖存儲(chǔ)器（又稱聯(lián)想存儲(chǔ)器或快表），用

35、以存放當(dāng)前訪問的那些頁表項(xiàng)；n地址變換機(jī)構(gòu)自動(dòng)將頁號與快表中的所有頁號進(jìn)行并行比較，若其中有與此匹配的頁號，則取出該頁對應(yīng)的塊號，與頁內(nèi)地址拼接形成物理地址；n若頁號不在快表中，則再到主存頁表中取出物理塊號，與頁內(nèi)地址拼接形成物理地址；n同時(shí)還應(yīng)將這次所查到的頁表項(xiàng)存入快表中，若快表已滿，則必須按某種原則淘汰出一個(gè)表項(xiàng)以騰出位置。具有聯(lián)想存儲(chǔ)器（快表）的地址變換具有聯(lián)想存儲(chǔ)器（快表）的地址變換n頁表與快表有何不同？快表該多大？頁表與快表有何不同？快表該多大？頁表寄存器 頁表始址 頁表長度越界中斷邏輯地址 頁號 頁內(nèi)位移頁號 塊號 01234 物理地址頁表頁號 塊號快表7。4。5 多級頁表及反向

36、頁表多級頁表及反向頁表n現(xiàn)代計(jì)算機(jī)系統(tǒng)都支持非常大的邏輯地址空間，致使頁表很大，用連續(xù)空間存放頁表顯然不現(xiàn)實(shí)；n如邏輯地址32位，頁面大小4KB，則頁表項(xiàng)為1M，若每個(gè)頁表項(xiàng)占4字節(jié)，則頁表共需要4MB內(nèi)存空間；n解決方案：n用離散方式存儲(chǔ)頁表n僅將當(dāng)前需要的部分頁表項(xiàng)放在內(nèi)存，其余放在磁盤上，需要時(shí)再調(diào)入。兩級頁表及多級頁表兩級頁表及多級頁表n將頁表再分頁，使每頁與內(nèi)存物理塊大小相同，并為它們進(jìn)行編號0、1、，同時(shí)還為離散存放的頁表建立一張頁表。n例如：32位地址可以劃分為31 22 21 12 11 0 一級頁號p1 二級頁號p2 頁內(nèi)地址w兩級頁表結(jié)構(gòu)兩級頁表結(jié)構(gòu)第0頁頁表內(nèi)存空間一級頁

37、表 200020242700 2 7 0123456785901411012n 0 1 2 1023 85 90 第1頁頁表 0 1 21023 1411 0 1 21023第n頁頁表具有兩級頁表的地址變換機(jī)構(gòu)具有兩級頁表的地址變換機(jī)構(gòu) n利用邏輯地址中的一級頁號作為索引訪問一級頁表，找到第二級頁表的起利用邏輯地址中的一級頁號作為索引訪問一級頁表，找到第二級頁表的起始地址；始地址；n再利用第二級頁號找到指定頁表項(xiàng)，從中取出塊號與頁內(nèi)地址拼接形成物再利用第二級頁號找到指定頁表項(xiàng)，從中取出塊號與頁內(nèi)地址拼接形成物理地址。理地址。 第一級頁表寄存器邏輯地址+二級頁表一級頁表 b w物理地址一級頁號

38、二級頁號 頁內(nèi)地址 p1 p2 wb反向頁表及其地址變換反向頁表及其地址變換n為解決頁表占用大量存儲(chǔ)空間的問題，另一種創(chuàng)新思路是引入反向頁表；n反向頁表為每個(gè)物理塊設(shè)置一個(gè)頁表項(xiàng)，并將它們按物理塊號大小排序，表項(xiàng)內(nèi)容為頁號及其所屬進(jìn)程的標(biāo)識號（如果已分配）；n利用進(jìn)程標(biāo)識號及頁號檢索反向頁表，若找到相應(yīng)的頁表項(xiàng)，則將其物理塊號與頁內(nèi)地址拼接；否則請求調(diào)入該進(jìn)程相應(yīng)頁，在無調(diào)頁功能的系統(tǒng)中則出錯(cuò)；n由于反向頁表中沒有存放進(jìn)程中尚未調(diào)入頁，因此必須為每個(gè)進(jìn)程建立一張傳統(tǒng)頁表并存放在外存中，當(dāng)所訪問頁不在內(nèi)存時(shí)使用這張頁表。頁表中包含各頁在外存的地址。反向頁表的地址變換反向頁表的地址變換n反向頁表有

39、什么不足？反向頁表有什么不足？邏輯地址邏輯地址進(jìn)程標(biāo)識號進(jìn)程標(biāo)識號 頁號頁號反向頁表反向頁表 b w物理地址物理地址 頁號頁號 頁內(nèi)地址頁內(nèi)地址 p w pid ppid p進(jìn)程標(biāo)識號進(jìn)程標(biāo)識號pid 0 1 2 bn n7.4.6 存儲(chǔ)保護(hù)存儲(chǔ)保護(hù)n分頁存儲(chǔ)管理采用兩種方式保護(hù)內(nèi)存：n地址越界保護(hù)：頁表長度與邏輯地址中的頁號比較；n存取控制保護(hù)：在頁表中增加保護(hù)位；7。5 分段管理分段管理n7。5。1 原理原理n由于分頁按物理單位進(jìn)行，沒有考慮程序段的邏輯完由于分頁按物理單位進(jìn)行，沒有考慮程序段的邏輯完整性，給程序段的共享和保護(hù)帶來不便，另外動(dòng)態(tài)鏈整性，給程序段的共享和保護(hù)帶來不便，另外動(dòng)態(tài)

40、鏈接及段的動(dòng)態(tài)增長也要求以邏輯上完整的程序段為單接及段的動(dòng)態(tài)增長也要求以邏輯上完整的程序段為單位管理，于是提出分段管理；位管理，于是提出分段管理；n在分段存儲(chǔ)管理系統(tǒng)中，作業(yè)的地址空間由若干個(gè)邏在分段存儲(chǔ)管理系統(tǒng)中，作業(yè)的地址空間由若干個(gè)邏輯分段組成，每個(gè)分段是一組邏輯意義相對完整的信輯分段組成，每個(gè)分段是一組邏輯意義相對完整的信息集合，每個(gè)分段都有自己的名字，每個(gè)分段都從息集合，每個(gè)分段都有自己的名字，每個(gè)分段都從0開開始編址，每個(gè)分段都有一個(gè)編號，從而形成一個(gè)二維始編址，每個(gè)分段都有一個(gè)編號，從而形成一個(gè)二維的地址空間；的地址空間；n在進(jìn)行存儲(chǔ)分配時(shí)，以段為單位分配內(nèi)存，每段分在在進(jìn)行存儲(chǔ)

41、分配時(shí)，以段為單位分配內(nèi)存，每段分在一個(gè)連續(xù)的內(nèi)存區(qū)，但各段之間不要求連續(xù)。一個(gè)連續(xù)的內(nèi)存區(qū)，但各段之間不要求連續(xù)。分段管理的邏輯地址結(jié)構(gòu)和二維空間分段管理的邏輯地址結(jié)構(gòu)和二維空間n在分段管理下，CPU訪存的邏輯地址由段號S和段內(nèi)位移量W兩部分組成，如下圖所示的邏輯地址，共有64K個(gè)段，每個(gè)段的長度為64K字節(jié)。010101010段1段2段3段代碼段數(shù)據(jù)段棧段擴(kuò)展段程序的二維程序的二維地址空間地址空間31 16 15 0 段 號 S 段 內(nèi) 位 移 W7。5。2 實(shí)現(xiàn)實(shí)現(xiàn)一一 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)n段表：段表：每個(gè)進(jìn)程建立一個(gè)段表，段表的每個(gè)表項(xiàng)記錄該進(jìn)程一段的相關(guān)信息，包括：n段號；n段長；n段

42、在內(nèi)存的起始地址；n其他信息；n空閑塊表或空閑塊鏈：空閑塊表或空閑塊鏈：形式與分區(qū)管理相同，用來記錄空閑段的現(xiàn)狀；段表的作用段表的作用內(nèi)存空間作業(yè)的地址空間段表 30K 40K 20K 80K 15K 120K 10K 150K段號 段長 基址040K80K120K150K(MAIN)=0030K(X)=1020K(D)=2015K(S)=3020K0123 (MAIN)=0 30K (X)=1 20K (D)=2 15K (S)=3 15K二二 地址變換地址變換n為實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換，在系統(tǒng)中設(shè)置了段表為實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換，在系統(tǒng)中設(shè)置了段表寄存器，用于存放段表始址和

43、段表長度；寄存器，用于存放段表始址和段表長度；n為了提高內(nèi)存的訪問速度，段表也可以存放在快表內(nèi)；為了提高內(nèi)存的訪問速度，段表也可以存放在快表內(nèi)；n進(jìn)行地扯變換時(shí)，系統(tǒng)將邏輯地址中的段號與段表長度進(jìn)行進(jìn)行地扯變換時(shí)，系統(tǒng)將邏輯地址中的段號與段表長度進(jìn)行比較，若段號超過了段表長度則產(chǎn)生越界中斷；比較，若段號超過了段表長度則產(chǎn)生越界中斷；n否則根據(jù)段表始址和段號計(jì)算出該段對應(yīng)段表項(xiàng)的位置，從否則根據(jù)段表始址和段號計(jì)算出該段對應(yīng)段表項(xiàng)的位置，從中讀出該段在內(nèi)存的起始地址；中讀出該段在內(nèi)存的起始地址；n然后再檢查段內(nèi)地址是否超過該段的段長，若超過則同樣發(fā)然后再檢查段內(nèi)地址是否超過該段的段長，若超過則同樣

44、發(fā)出越界中斷信號；出越界中斷信號；n若未越界，則將該段的起始地址與段內(nèi)位移相加，從而得到若未越界，則將該段的起始地址與段內(nèi)位移相加，從而得到要訪問的內(nèi)存物理地址。要訪問的內(nèi)存物理地址。地址變換示意圖地址變換示意圖n設(shè)作業(yè)分為設(shè)作業(yè)分為3段，段，0、1、2段長度分別為段長度分別為1K、800、600，分別存放在內(nèi)存分別存放在內(nèi)存6K、4K、8K開始的內(nèi)存區(qū)域；開始的內(nèi)存區(qū)域；nCPU訪存的邏輯地址（訪存的邏輯地址（2，100）的段號為）的段號為2，段內(nèi)位移，段內(nèi)位移為為100；n查段表可知第查段表可知第2段在內(nèi)存的起始地址為段在內(nèi)存的起始地址為8K；n將起始地址與段內(nèi)位移相加，將起始地址與段內(nèi)位

45、移相加，8K1008292，得到得到物理地址為物理地址為8292。段表寄存器 段表始址 段表長度越界中斷邏輯地址 段號（2）段內(nèi)位移（100）段號 段長 始址 1K 6K800 4K600 8K012物理地址8292三三 空間的分配與回收空間的分配與回收n分段管理可以看作是分區(qū)管理的擴(kuò)充，而分區(qū)管理可以看作是分段管理的特例。因此，這兩種管理方法的空間分配和回收程序是類似的：分區(qū)管理為一道程序只分配和回收一段空間，而分段管理要為一道程序分配和回收多段空間，僅次而已。7。5。3 分段與分頁的主要區(qū)別分段與分頁的主要區(qū)別n分頁管理與分段管理有許多相似之處，但兩者在概念上也有分頁管理與分段管理有許多相似之處，但兩者在概念上也有很多區(qū)別，主要表現(xiàn)在：很多區(qū)別，主要表現(xiàn)在：n頁是信息的物理單位，是為了減少內(nèi)存碎片及提高內(nèi)存利頁是信息的物理單位，是為了減少內(nèi)存碎片及提高內(nèi)存利用率，是系統(tǒng)管理的需要。段是信息的邏輯單位，它含有用率，是系統(tǒng)管理的需要。段是信息的邏輯單位，它含有一組意義相對完整的信息，分段的目的是為了更好地滿足一組意義相對完整的信息，分段的目的是為了更好地滿足用戶編程的需要；用戶編程的需要；n頁的