第四章存儲(chǔ)器管理

1、東北農(nóng)業(yè)大學(xué)東北農(nóng)業(yè)大學(xué)王艷王艷操作系統(tǒng)原理操作系統(tǒng)原理第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理進(jìn)程管理進(jìn)程管理處理機(jī)分配處理機(jī)分配內(nèi)存分配內(nèi)存分配第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理1 1 存儲(chǔ)器的多層結(jié)構(gòu)存儲(chǔ)器的多層結(jié)構(gòu)CPUCPU寄存器寄存器4.1.1 4.1.1 多層結(jié)構(gòu)的存儲(chǔ)器系統(tǒng)多層結(jié)構(gòu)的存儲(chǔ)器系統(tǒng)主存主存 輔存輔存n 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 高速緩存高速緩存主存主存磁盤緩存磁盤緩存可執(zhí)行存儲(chǔ)器，可執(zhí)行存儲(chǔ)器，OS管理管理可移動(dòng)存儲(chǔ)介質(zhì)可移動(dòng)存儲(chǔ)介質(zhì)磁盤磁盤設(shè)備管理設(shè)備管理第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理2 2 對(duì)比對(duì)比從上到下：從上到下：4.1.1 4.1.1 多級(jí)存

2、儲(chǔ)器結(jié)構(gòu)多級(jí)存儲(chǔ)器結(jié)構(gòu)n 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 訪問速度越來越慢訪問速度越來越慢存儲(chǔ)容量越來越大存儲(chǔ)容量越來越大價(jià)格越來越低價(jià)格越來越低第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理1 1 主存儲(chǔ)器主存儲(chǔ)器主存（內(nèi)存）主存（內(nèi)存）4.1.2 4.1.2 主存儲(chǔ)器與寄存器主存儲(chǔ)器與寄存器n 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 幾十幾十MBMB幾幾GBGB和和CPUCPU直接交換數(shù)據(jù)直接交換數(shù)據(jù)第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理2 2 寄存器寄存器4.1.2 4.1.2 主存儲(chǔ)器和寄存器主存儲(chǔ)器和寄存器n 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 速度最快，價(jià)格最貴速度最快，價(jià)格最貴

3、幾十個(gè)幾十個(gè)幾百個(gè)幾百個(gè)第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理1 1 高速緩存高速緩存4.1.3 4.1.3 高速緩存和磁盤緩存高速緩存和磁盤緩存n 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 容量、速度介于主存和寄存器之間容量、速度介于主存和寄存器之間利用程序執(zhí)行的局部性原理利用程序執(zhí)行的局部性原理多級(jí)高速緩存多級(jí)高速緩存?zhèn)浞葜鞔嬷休^常用的數(shù)據(jù)，減少主存訪問次數(shù)備份主存中較常用的數(shù)據(jù)，減少主存訪問次數(shù)第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理2 2 磁盤緩存磁盤緩存緩和磁盤的緩和磁盤的I/O速度遠(yuǎn)低于對(duì)主存的訪問速度速度遠(yuǎn)低于對(duì)主存的訪問速度4.1.3 4.1.3 高速緩存和磁盤緩存高速緩存和磁盤緩存n

4、4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 內(nèi)存的一部分內(nèi)存的一部分目的是減少訪問磁盤的次數(shù)目的是減少訪問磁盤的次數(shù)第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.2 程序的裝入和鏈接程序的裝入和鏈接 運(yùn)行程序運(yùn)行程序 創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程 程序數(shù)據(jù)裝入內(nèi)存程序數(shù)據(jù)裝入內(nèi)存 源程序源程序 目標(biāo)模塊目標(biāo)模塊 裝入模塊裝入模塊 可執(zhí)行程序可執(zhí)行程序 編譯編譯鏈接鏈接裝入裝入庫鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.2 程序的裝入和鏈接程序的裝入和鏈接 4.2.1 4.2.1 程序的裝入程序的裝入1 1 相對(duì)地址和絕對(duì)地址相對(duì)地址和絕對(duì)地址相

5、對(duì)相對(duì)地址：從地址：從0開始編號(hào)（邏輯地址）開始編號(hào)（邏輯地址）絕對(duì)絕對(duì)地址：內(nèi)存中存儲(chǔ)單元的物理地址（物理地地址：內(nèi)存中存儲(chǔ)單元的物理地址（物理地址）址）虛擬地址虛擬地址實(shí)際地址實(shí)際地址地址轉(zhuǎn)換的時(shí)期不同決定裝入方式的不同地址轉(zhuǎn)換的時(shí)期不同決定裝入方式的不同第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.2 程序的裝入和鏈接程序的裝入和鏈接 2 2 程序中的地址程序中的地址（1）指令地址：程序本身所處的地址）指令地址：程序本身所處的地址4.2.1 4.2.1 程序的裝入程序的裝入（2 2）數(shù)據(jù)中的地址：程序中涉及的地址）數(shù)據(jù)中的地址：程序中涉及的地址（3 3）例子）例子1000Load 1,250

6、025003655000數(shù)據(jù)中的地址數(shù)據(jù)中的地址指令地址指令地址第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.2 程序的裝入和鏈接程序的裝入和鏈接 3 3 裝入方式裝入方式（1）絕對(duì)裝入方式）絕對(duì)裝入方式4.2.1 4.2.1 程序的裝入程序的裝入前提：預(yù)先知道程序駐留內(nèi)存的什么位置前提：預(yù)先知道程序駐留內(nèi)存的什么位置過程：編譯時(shí)直接產(chǎn)生絕對(duì)地址；過程：編譯時(shí)直接產(chǎn)生絕對(duì)地址； 程序中所用的絕對(duì)地址可由程序員給出；程序中所用的絕對(duì)地址可由程序員給出； 或采用符號(hào)地址，編譯時(shí)轉(zhuǎn)換?；虿捎梅?hào)地址，編譯時(shí)轉(zhuǎn)換。優(yōu)缺點(diǎn)：優(yōu)缺點(diǎn)： 只適合于單道程序環(huán)境只適合于單道程序環(huán)境第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理

7、n 4.2 程序的裝入和鏈接程序的裝入和鏈接 （2）可重定位裝入方式）可重定位裝入方式4.2.1 4.2.1 程序的裝入程序的裝入適用于多道程序環(huán)境下適用于多道程序環(huán)境下過程：過程：特點(diǎn)：特點(diǎn)： 易實(shí)現(xiàn)，無需硬件支持易實(shí)現(xiàn)，無需硬件支持 重定位后不能移動(dòng)重定位后不能移動(dòng) 程序在存儲(chǔ)空間中只能連續(xù)分配程序在存儲(chǔ)空間中只能連續(xù)分配 用戶很難共享同一程序，若共享，使用自己的副體用戶很難共享同一程序，若共享，使用自己的副體LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作業(yè)地址空間內(nèi)存空間1第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n

8、4.2 程序的裝入和鏈接程序的裝入和鏈接 （3）動(dòng)態(tài)運(yùn)行時(shí)裝入方式）動(dòng)態(tài)運(yùn)行時(shí)裝入方式4.2.1 4.2.1 程序的裝入程序的裝入適用于要求程序在內(nèi)存空間移動(dòng)適用于要求程序在內(nèi)存空間移動(dòng)過程：程序原封不動(dòng)裝入內(nèi)存過程：程序原封不動(dòng)裝入內(nèi)存 用寄存器記錄偏移地址用寄存器記錄偏移地址 在程序執(zhí)行時(shí)再轉(zhuǎn)換地址在程序執(zhí)行時(shí)再轉(zhuǎn)換地址例子例子 第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理（3）動(dòng)態(tài)運(yùn)行時(shí)裝入方）動(dòng)態(tài)運(yùn)行時(shí)裝入方式式4.2.1 4.2.1 程序的裝入程序的裝入327MOV AX, 100050100199100VR1000BR1100MR+327MOV AX, 1001000105011001199

9、200LR程序地址空間內(nèi)存空間第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.2 程序的裝入和鏈接程序的裝入和鏈接 1 靜態(tài)鏈接靜態(tài)鏈接4.2.2 4.2.2 程序的鏈接程序的鏈接（1）程序運(yùn)行之前進(jìn)行）程序運(yùn)行之前進(jìn)行（2）鏈接后，模塊不再拆開）鏈接后，模塊不再拆開（3）例子）例子 模塊 ACALL B；Return；0L-1模塊 BCALL C；Return；0M-1模塊 CReturn；0N-10模塊 AJSR“L”Return；L-1模塊 BJSR“LM”Return；LL+M-1L+ML+M+N-1模塊 CReturn；(a) 目標(biāo)模塊(b) 裝入模塊第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n

10、4.2 程序的裝入和鏈接程序的裝入和鏈接 2 裝入時(shí)鏈接裝入時(shí)鏈接4.2.2 4.2.2 程序的鏈接程序的鏈接（1）邊裝入邊鏈接）邊裝入邊鏈接（2）便于修改）便于修改（3）便于對(duì)目標(biāo)模塊共享）便于對(duì)目標(biāo)模塊共享第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.2 程序的裝入和鏈接程序的裝入和鏈接 3 運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接4.2.2 4.2.2 程序的鏈接程序的鏈接（1）無法了解用哪些模塊，全加載則低效）無法了解用哪些模塊，全加載則低效（2）運(yùn)行時(shí)用哪個(gè)模塊鏈接相應(yīng)模塊）運(yùn)行時(shí)用哪個(gè)模塊鏈接相應(yīng)模塊第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理CPUCPU寄存器寄存器主存主存 輔存輔存高速緩存高速緩存主存主

11、存磁盤緩存磁盤緩存可執(zhí)行存儲(chǔ)器，可執(zhí)行存儲(chǔ)器，OS管理管理可移動(dòng)存儲(chǔ)介質(zhì)可移動(dòng)存儲(chǔ)介質(zhì)磁盤磁盤設(shè)備管理設(shè)備管理程序的裝入和鏈接程序的裝入和鏈接第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 1 1 適用于單任務(wù)、單用戶的操作系統(tǒng)適用于單任務(wù)、單用戶的操作系統(tǒng)4.3.1 4.3.1 單一連續(xù)分配單一連續(xù)分配2 2作業(yè)操作系統(tǒng)未用32 KB64 KB160 KB分配給用戶作業(yè)的空間3 3 特點(diǎn)：特點(diǎn)： 單道單道 浪費(fèi)嚴(yán)重浪費(fèi)嚴(yán)重第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 1 1 思想：內(nèi)存劃定固定大小分區(qū)，每個(gè)分區(qū)一道作思想：內(nèi)存劃定固定大小分區(qū)，每個(gè)分區(qū)一道作

12、 業(yè)，建立一張注冊(cè)業(yè)，建立一張注冊(cè)表4.3.2 4.3.2 固定分區(qū)分配固定分區(qū)分配2 2 分區(qū)劃法分區(qū)劃法（1 1）分區(qū)大小相等）分區(qū)大小相等太小，裝不下，程序無法運(yùn)行太小，裝不下，程序無法運(yùn)行太大，內(nèi)存浪費(fèi)太大，內(nèi)存浪費(fèi)適于操作同類的多個(gè)任務(wù)適于操作同類的多個(gè)任務(wù)第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.2 4.3.2 固定分區(qū)分配固定分區(qū)分配（2 2）分區(qū)大小不等）分區(qū)大小不等多個(gè)小分區(qū)，若干個(gè)中分區(qū)，少量大分區(qū)多個(gè)小分區(qū)，若干個(gè)中分區(qū)，少量大分區(qū)3 內(nèi)存分配內(nèi)存分配（1）分區(qū)按大小排隊(duì)，建一張分區(qū)使用表）分區(qū)按大小排隊(duì)，建一張分區(qū)使用表（2）有程序使用時(shí)，

13、檢索表）有程序使用時(shí)，檢索表（3）例子）例子Page 23第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 分區(qū)號(hào)分區(qū)號(hào)容量容量起始地址起始地址狀態(tài)狀態(tài)1816已分配已分配21624未分配未分配33240已分配已分配46472未分配未分配5120136未分配未分配4.3.2 4.3.2 固定分區(qū)分配固定分區(qū)分配作業(yè)名作業(yè)名ABCDE容量容量423204090分配情況分配情況已分配已分配已分配已分配未分配未分配未分配未分配未分配未分配OS區(qū)區(qū) 016244072136255分區(qū)分區(qū)1分區(qū)分區(qū)2分區(qū)分區(qū)3分區(qū)分區(qū)4分區(qū)分區(qū)5作業(yè)作業(yè)A4KB作業(yè)作業(yè)B9KB作業(yè)作業(yè)C44KB作業(yè)作業(yè)D

14、80KBE90未分配未分配內(nèi)存使用率：內(nèi)存使用率：87/256=0.34第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.2 4.3.2 固定分區(qū)分配固定分區(qū)分配4 4 特點(diǎn)特點(diǎn)（1）簡(jiǎn)單，實(shí)現(xiàn)了多道程序）簡(jiǎn)單，實(shí)現(xiàn)了多道程序（2）內(nèi)存利用率低）內(nèi)存利用率低 碎片多碎片多作業(yè)受分區(qū)大小限制作業(yè)受分區(qū)大小限制第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.3 4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配根據(jù)進(jìn)程實(shí)際需要，動(dòng)態(tài)的為之分配內(nèi)存根據(jù)進(jìn)程實(shí)際需要，動(dòng)態(tài)的為之分配內(nèi)存1 分區(qū)分配所用的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配所用的數(shù)據(jù)結(jié)構(gòu) （1）空閑分區(qū)表）空閑分區(qū)表 分區(qū)號(hào)

15、、分區(qū)起始地址、分區(qū)大小分區(qū)號(hào)、分區(qū)起始地址、分區(qū)大小（2）空閑分區(qū)鏈）空閑分區(qū)鏈前向指針0N 個(gè)字節(jié)可用后向指針0N+2N+2第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.3 4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配2 2 分區(qū)分配算法分區(qū)分配算法（1） 首次適應(yīng)算法首次適應(yīng)算法 （6 6） 伙伴系統(tǒng)伙伴系統(tǒng)（3 3） 最佳適應(yīng)算法最佳適應(yīng)算法（4 4） 最壞適應(yīng)算法最壞適應(yīng)算法（5 5） 快速適應(yīng)算法快速適應(yīng)算法（2 2） 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法（7 7） 哈希算法哈希算法基于順序搜索基于順序搜索基于索引搜索基于索引搜索第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n

16、4.3 連續(xù)分配連續(xù)分配 4.3.3 4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配3 3 分區(qū)分配操作分區(qū)分配操作（1） 分配內(nèi)存分配內(nèi)存從頭開始查表檢索完否？m.sizeu.size?m.size-u.sizesize?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請(qǐng)求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個(gè)表項(xiàng)將該分區(qū)從鏈中移出YNNYYN第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.3 4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配2 2 分區(qū)分配操作分區(qū)分配操作（2） 內(nèi)存回收內(nèi)存回收 回收區(qū)與插入點(diǎn)的前回收區(qū)與插入點(diǎn)的前一個(gè)空閑分區(qū)一個(gè)空閑分區(qū)F1相鄰接，相鄰接，見圖見圖

17、 (a)。此時(shí)應(yīng)將回收。此時(shí)應(yīng)將回收區(qū)與插入點(diǎn)的前一分區(qū)區(qū)與插入點(diǎn)的前一分區(qū)合并，不必為回收分區(qū)合并，不必為回收分區(qū)分配新表項(xiàng)，而只需修分配新表項(xiàng)，而只需修改其前一分區(qū)改其前一分區(qū)F1的大小。的大小。第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.3 4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配2 2 分區(qū)分配操作分區(qū)分配操作（2） 內(nèi)存回收內(nèi)存回收 回收分區(qū)與插入點(diǎn)的回收分區(qū)與插入點(diǎn)的后一空閑分區(qū)后一空閑分區(qū)F2相鄰接，相鄰接，見圖見圖(b)。此時(shí)也可將兩。此時(shí)也可將兩分區(qū)合并，形成新的空分區(qū)合并，形成新的空閑分區(qū)，但用回收區(qū)的閑分區(qū)，但用回收區(qū)的首址作為新空閑區(qū)的首首址作為

18、新空閑區(qū)的首址，大小為兩者之和。址，大小為兩者之和。 第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.3 4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配2 2 分區(qū)分配操作分區(qū)分配操作（2） 內(nèi)存回收內(nèi)存回收 回收區(qū)同時(shí)與插入點(diǎn)回收區(qū)同時(shí)與插入點(diǎn)的前、后兩個(gè)分區(qū)鄰接，的前、后兩個(gè)分區(qū)鄰接，見圖見圖(c)。此時(shí)將三個(gè)分。此時(shí)將三個(gè)分區(qū)合并，使用區(qū)合并，使用F1的表項(xiàng)的表項(xiàng)和和F1的首址，取消的首址，取消F2的的表項(xiàng)，大小為三者之和。表項(xiàng)，大小為三者之和。第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.3 4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配2 2 分區(qū)分配操

19、作分區(qū)分配操作（2） 內(nèi)存回收內(nèi)存回收 回收區(qū)既不與回收區(qū)既不與F1鄰接，又不與鄰接，又不與F2鄰接。這時(shí)應(yīng)為鄰接。這時(shí)應(yīng)為回收區(qū)單獨(dú)建立一新表項(xiàng)，填寫回收區(qū)的首址和大小，回收區(qū)單獨(dú)建立一新表項(xiàng)，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。 第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.4 4.3.4 基于順序搜索的動(dòng)態(tài)分區(qū)分配算法基于順序搜索的動(dòng)態(tài)分區(qū)分配算法1 首次適應(yīng)算法（首次適應(yīng)算法（FF） 基本思想基本思想空閑分區(qū)鏈以地址遞增的次序鏈接空閑分區(qū)鏈以地址遞增的次序鏈接從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能

20、滿足要求從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿足要求 的空閑分區(qū)為止；的空閑分區(qū)為止；從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的 空閑分區(qū)仍留在空閑鏈中空閑分區(qū)仍留在空閑鏈中若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿足要求的分若從鏈?zhǔn)字敝伶溛捕疾荒苷业揭粋€(gè)能滿足要求的分 區(qū)，則此次內(nèi)存分配失敗區(qū)，則此次內(nèi)存分配失敗第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 1 首次適應(yīng)算法（首次適應(yīng)算法（first fit） 優(yōu)點(diǎn)優(yōu)點(diǎn)釋放內(nèi)存時(shí)，有相鄰的就合并釋放內(nèi)存時(shí)，有相鄰的就合并大部分時(shí)間在低址操作，高地址有較大空間大部分時(shí)間在低址操作，高

21、地址有較大空間低地址被反復(fù)劃分，留下很多難以利用的小空閑區(qū)低地址被反復(fù)劃分，留下很多難以利用的小空閑區(qū)搜索次數(shù)增加，工作效率低搜索次數(shù)增加，工作效率低缺點(diǎn)缺點(diǎn)4.3.4 4.3.4 基于順序搜索的動(dòng)態(tài)分區(qū)分配算法基于順序搜索的動(dòng)態(tài)分區(qū)分配算法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 2 循環(huán)首次適應(yīng)算法（循環(huán)首次適應(yīng)算法（next fit） 基本思想基本思想從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找從上次找到的空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找若最后一個(gè)空閑區(qū)仍不能滿足，返回第一個(gè)空閑區(qū)若最后一個(gè)空閑區(qū)仍不能滿足，返回第一個(gè)空閑區(qū)4.3.4 4.3.4 基于順序搜索的動(dòng)態(tài)

22、分區(qū)分配算法基于順序搜索的動(dòng)態(tài)分區(qū)分配算法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 2 循環(huán)首次適應(yīng)算法（循環(huán)首次適應(yīng)算法（next fit） 優(yōu)點(diǎn)優(yōu)點(diǎn)減少查找空閑分區(qū)的開銷減少查找空閑分區(qū)的開銷空閑分區(qū)分布均勻空閑分區(qū)分布均勻缺乏較大的空閑分區(qū)缺乏較大的空閑分區(qū)缺點(diǎn)缺點(diǎn)4.3.4 4.3.4 基于順序搜索的動(dòng)態(tài)分區(qū)分配算法基于順序搜索的動(dòng)態(tài)分區(qū)分配算法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 3 最佳適應(yīng)算法（最佳適應(yīng)算法（best fit） 基本思想基本思想每次把滿足需求，又是最小的空閑分區(qū)分給作業(yè)每次把滿足需求，又是最小的空閑分區(qū)分給作業(yè)空閑分

23、區(qū)按從小到大排序空閑分區(qū)按從小到大排序4.3.4 4.3.4 基于順序搜索的動(dòng)態(tài)分區(qū)分配算法基于順序搜索的動(dòng)態(tài)分區(qū)分配算法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 3 最佳適應(yīng)算法（最佳適應(yīng)算法（best fit） 優(yōu)點(diǎn)優(yōu)點(diǎn)平均而言，只要查找一半表格平均而言，只要查找一半表格若有正好滿足空白區(qū)，則它必被選中若有正好滿足空白區(qū)，則它必被選中剩余部分很小，以至于無法使用剩余部分很小，以至于無法使用缺點(diǎn)缺點(diǎn)較大空白被保留下來較大空白被保留下來4.3.4 4.3.4 基于順序搜索的動(dòng)態(tài)分區(qū)分配算法基于順序搜索的動(dòng)態(tài)分區(qū)分配算法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配

24、連續(xù)分配 4 最壞適應(yīng)算法（最壞適應(yīng)算法（worst fit） 基本思想基本思想空白區(qū)從大到小排序，依次分配空白區(qū)空白區(qū)從大到小排序，依次分配空白區(qū)4.3.4 4.3.4 基于順序搜索的動(dòng)態(tài)分區(qū)分配算法基于順序搜索的動(dòng)態(tài)分區(qū)分配算法優(yōu)點(diǎn)優(yōu)點(diǎn)速度快速度快一次分配后，剩余空間仍可能大，能滿足一般要求一次分配后，剩余空間仍可能大，能滿足一般要求不利于大作業(yè)不利于大作業(yè)缺點(diǎn)缺點(diǎn)第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.5 4.3.5 基于索引搜索的動(dòng)態(tài)分區(qū)分配算法基于索引搜索的動(dòng)態(tài)分區(qū)分配算法1 快速適應(yīng)算法（快速適應(yīng)算法（quick fit） 基本思想基本思想將空閑分區(qū)

25、按容量大小分類，每類形成一個(gè)分區(qū)鏈表將空閑分區(qū)按容量大小分類，每類形成一個(gè)分區(qū)鏈表設(shè)置一張管理索引表，每一記錄對(duì)應(yīng)一種空閑分區(qū)類設(shè)置一張管理索引表，每一記錄對(duì)應(yīng)一種空閑分區(qū)類 型及空閑分區(qū)鏈表的表頭型及空閑分區(qū)鏈表的表頭分類按分類按2K、4K、8K，其它的可就近歸類或?qū)ｉT的特殊，其它的可就近歸類或?qū)ｉT的特殊 空閑區(qū)鏈表中空閑區(qū)鏈表中第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 1 快速適應(yīng)算法（快速適應(yīng)算法（quick fit） 優(yōu)點(diǎn)優(yōu)點(diǎn)查找效率高查找效率高不會(huì)產(chǎn)生分割，能保留大分區(qū)不會(huì)產(chǎn)生分割，能保留大分區(qū)算法復(fù)雜，開銷大算法復(fù)雜，開銷大缺點(diǎn)缺點(diǎn)空間換時(shí)間空間換時(shí)間4.3.

26、5 4.3.5 基于索引搜索的動(dòng)態(tài)分區(qū)分配算法基于索引搜索的動(dòng)態(tài)分區(qū)分配算法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 2 2 伙伴系統(tǒng)伙伴系統(tǒng)（1） 分區(qū)大小均為分區(qū)大小均為2的的k次冪，次冪，k為整數(shù)，為整數(shù)，lkm（2 2）不斷的劃分內(nèi)存，形成若干個(gè)不連續(xù)的空不斷的劃分內(nèi)存，形成若干個(gè)不連續(xù)的空閑分區(qū)，根據(jù)分區(qū)的大小進(jìn)行分類，形成空閑閑分區(qū)，根據(jù)分區(qū)的大小進(jìn)行分類，形成空閑分區(qū)雙向鏈表分區(qū)雙向鏈表（3 3）分配一個(gè)長度為分配一個(gè)長度為n的存儲(chǔ)空間時(shí)，首先計(jì)的存儲(chǔ)空間時(shí)，首先計(jì)算一個(gè)算一個(gè)i值，使值，使2i1n2i，然后在空閑分區(qū)大小，然后在空閑分區(qū)大小為為2i的空閑分

27、區(qū)鏈表中查找。若找到，即把該的空閑分區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進(jìn)程空閑分區(qū)分配給進(jìn)程4.3.5 4.3.5 基于索引搜索的動(dòng)態(tài)分區(qū)分配算法基于索引搜索的動(dòng)態(tài)分區(qū)分配算法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 （4 4）否則，表明長度為否則，表明長度為2i的空閑分區(qū)已經(jīng)耗盡，的空閑分區(qū)已經(jīng)耗盡，則在分區(qū)大小為則在分區(qū)大小為2i1的空閑分區(qū)鏈表中尋找。的空閑分區(qū)鏈表中尋找。若存在若存在2i1的一個(gè)空閑分區(qū)，則把該空閑分區(qū)的一個(gè)空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一對(duì)伙分為相等的兩個(gè)分區(qū)，這兩個(gè)分區(qū)稱為一對(duì)伙伴，其中的一個(gè)分區(qū)用于分配，而

28、把另一個(gè)加伴，其中的一個(gè)分區(qū)用于分配，而把另一個(gè)加入分區(qū)大小為入分區(qū)大小為2i的空閑分區(qū)鏈表中。的空閑分區(qū)鏈表中。2 2 伙伴系統(tǒng)伙伴系統(tǒng)4.3.5 4.3.5 基于索引搜索的動(dòng)態(tài)分區(qū)分配算法基于索引搜索的動(dòng)態(tài)分區(qū)分配算法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 設(shè)系統(tǒng)中初始內(nèi)存空間大小為設(shè)系統(tǒng)中初始內(nèi)存空間大小為1MB，進(jìn)程請(qǐng)，進(jìn)程請(qǐng)求釋放存儲(chǔ)空間的操作序列為：求釋放存儲(chǔ)空間的操作序列為：進(jìn)程進(jìn)程A申請(qǐng)申請(qǐng)200KB，B申請(qǐng)申請(qǐng)120KB，C申請(qǐng)申請(qǐng)240KB，D申請(qǐng)申請(qǐng)100KB進(jìn)程進(jìn)程B釋放，釋放，E申請(qǐng)申請(qǐng)60KB進(jìn)程進(jìn)程A，C釋放釋放進(jìn)程進(jìn)程D釋放釋放進(jìn)程進(jìn)程E

29、釋放釋放寫出上述操作序列內(nèi)存伙伴變化的情況寫出上述操作序列內(nèi)存伙伴變化的情況2 2 伙伴系統(tǒng)伙伴系統(tǒng)4.3.5 4.3.5 基于索引搜索的動(dòng)態(tài)分區(qū)分配算法基于索引搜索的動(dòng)態(tài)分區(qū)分配算法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理 例子例子512K01M-10256K512K1M-1A0256K512K1M-1A384KB第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理 例子例子0256K512K768K1M-1A384KBC0256K512K768K1M-1A384KBCD0256K512K768K1M-1A384KCD第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理2 2 例子例子0256K512K768K1M-1A384KCD

30、E320K0256K512K1M-1384KDE320K0256K512K1M-1384KE320K第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理2 2 例子例子0256K512K1M-1384KE320K0256K512K1M-1384K0256K512K1M-1第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理 例子例子0512K1M-101M-1第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理 例子例子1MB512KB256KB128KB第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)（1） 空間性能優(yōu)于分類算法空間性能優(yōu)于分類算法（2 2）時(shí)間性能優(yōu)于順序搜索算法時(shí)間性能優(yōu)于順序搜索算法（3 3）回

31、收開銷大回收開銷大2 2 伙伴系統(tǒng)伙伴系統(tǒng)4.3.5 4.3.5 基于索引搜索的動(dòng)態(tài)分區(qū)分配算法基于索引搜索的動(dòng)態(tài)分區(qū)分配算法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.6 4.3.6 可重定位分區(qū)分配可重定位分區(qū)分配1 1 引入引入 零碎小分區(qū)的總和零碎小分區(qū)的總和大于作業(yè)大小，如何大于作業(yè)大小，如何裝入裝入2 2 解決方案解決方案 移動(dòng)所有被分配的分移動(dòng)所有被分配的分區(qū)，形成大的空白區(qū)域。區(qū)，形成大的空白區(qū)域。（以時(shí)間換空間）（以時(shí)間換空間）操作系統(tǒng)用戶程序1用戶程序310 KB30 KB用戶程序614 KB用戶程序926 KB操作系統(tǒng)用戶程序1用戶程序3用戶程

32、序6用戶程序980 KB(a) 緊湊前(b) 緊湊后第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.6 4.3.6 可重定位分區(qū)分配可重定位分區(qū)分配3 3 實(shí)現(xiàn)實(shí)現(xiàn)相對(duì)地址轉(zhuǎn)換為物理地址推遲到指令真正執(zhí)行時(shí)相對(duì)地址轉(zhuǎn)換為物理地址推遲到指令真正執(zhí)行時(shí)重定位寄存器：存放程序（數(shù)據(jù)）在內(nèi)存中的重定位寄存器：存放程序（數(shù)據(jù)）在內(nèi)存中的 起始地址起始地址訪問地址訪問地址=相對(duì)地址相對(duì)地址+重定位寄存器中的地址重定位寄存器中的地址第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.6 4.3.6 可重定位分區(qū)分配可重定位分區(qū)分配4 4 例子例子LOAD1,250

33、03650100250050002500相對(duì)地址10000重定位寄存器LOAD1,250036510000101001250015000作業(yè)J處理機(jī)一側(cè) 存儲(chǔ)器一側(cè)主存第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.6 4.3.6 可重定位分區(qū)分配可重定位分區(qū)分配5 5 靠攏時(shí)間靠攏時(shí)間某個(gè)分區(qū)作業(yè)完成某個(gè)分區(qū)作業(yè)完成沒有足夠大空白區(qū)時(shí)沒有足夠大空白區(qū)時(shí)6 優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)解決了碎片問題解決了碎片問題需硬件支持需硬件支持降低計(jì)算機(jī)速度降低計(jì)算機(jī)速度第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.3 連續(xù)分配連續(xù)分配 4.3.6 4.3.6 可重定位分區(qū)分配可重定位分區(qū)分配請(qǐng)求分配

34、u.size分區(qū)檢索空閑分區(qū)鏈(表)找到大于u.size的可用區(qū)否?按動(dòng)態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號(hào)及首批空閑分區(qū)總和u.size?進(jìn)行緊湊形成連續(xù)空閑區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)否是無法分配返回否第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.4 對(duì)換對(duì)換 4.4.14.4.1 多道程序環(huán)境下的對(duì)換技術(shù)多道程序環(huán)境下的對(duì)換技術(shù)1 1 引入引入一方面，某些進(jìn)程占用內(nèi)存卻被阻塞一方面，某些進(jìn)程占用內(nèi)存卻被阻塞另一方面，某些進(jìn)程等待卻無法占用內(nèi)存另一方面，某些進(jìn)程等待卻無法占用內(nèi)存整體對(duì)換：進(jìn)程對(duì)換（分時(shí)系統(tǒng)）整體對(duì)換：進(jìn)程對(duì)換（分時(shí)系統(tǒng)） 頁面對(duì)換：頁面對(duì)換：“頁頁”或或“段段”的對(duì)換（虛擬

35、存儲(chǔ)）的對(duì)換（虛擬存儲(chǔ)）進(jìn)程對(duì)換：對(duì)換空間的管理，進(jìn)程的換入、換出進(jìn)程對(duì)換：對(duì)換空間的管理，進(jìn)程的換入、換出2 2 對(duì)換類型對(duì)換類型第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.4 對(duì)換對(duì)換4.4.24.4.2 對(duì)換空間的管理對(duì)換空間的管理1 1 對(duì)換空間管理的主要目標(biāo)對(duì)換空間管理的主要目標(biāo)文件區(qū)文件區(qū) 用于存放文件，主要目標(biāo)是提高文件存儲(chǔ)用于存放文件，主要目標(biāo)是提高文件存儲(chǔ)空間的利用率?？臻g的利用率。對(duì)換區(qū)對(duì)換區(qū) 用于存放從內(nèi)存換出的進(jìn)程；用于存放從內(nèi)存換出的進(jìn)程； 由于進(jìn)程在對(duì)換區(qū)駐留的時(shí)間是短暫的，而由于進(jìn)程在對(duì)換區(qū)駐留的時(shí)間是短暫的，而其操作又較頻繁，故對(duì)對(duì)換空間的管理的主要其操作又較頻繁

36、，故對(duì)對(duì)換空間的管理的主要目標(biāo)是提高進(jìn)程換入和換出的速度。目標(biāo)是提高進(jìn)程換入和換出的速度。第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.4 對(duì)換對(duì)換 4.4.24.4.2 對(duì)換空間的管理對(duì)換空間的管理2 2 對(duì)換空間管理中的數(shù)據(jù)結(jié)構(gòu)對(duì)換空間管理中的數(shù)據(jù)結(jié)構(gòu)配以數(shù)據(jù)結(jié)構(gòu)，記錄外存對(duì)換區(qū)使用情況。空配以數(shù)據(jù)結(jié)構(gòu)，記錄外存對(duì)換區(qū)使用情況?？臻e分區(qū)表或空閑分區(qū)鏈。閑分區(qū)表或空閑分區(qū)鏈。4.4.3 進(jìn)程的換入與換出進(jìn)程的換入與換出1 進(jìn)程的換出進(jìn)程的換出（1） 時(shí)機(jī)：當(dāng)進(jìn)程創(chuàng)建子進(jìn)程而需要更多內(nèi)存空間，但又時(shí)機(jī)：當(dāng)進(jìn)程創(chuàng)建子進(jìn)程而需要更多內(nèi)存空間，但又 無足夠內(nèi)存空間時(shí)。無足夠內(nèi)存空間時(shí)。（2） 過程：選擇

37、處于阻塞且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)過程：選擇處于阻塞且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn) 程，然后啟動(dòng)磁盤，將進(jìn)程的程序和數(shù)據(jù)傳送到磁盤程，然后啟動(dòng)磁盤，將進(jìn)程的程序和數(shù)據(jù)傳送到磁盤 的對(duì)換區(qū)上。的對(duì)換區(qū)上。第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.4 對(duì)換對(duì)換 4.4.34.4.3 進(jìn)程的換入與換出進(jìn)程的換入與換出（3）結(jié)果：若傳送過程中未出現(xiàn)錯(cuò)誤，便可回收內(nèi)存，并）結(jié)果：若傳送過程中未出現(xiàn)錯(cuò)誤，便可回收內(nèi)存，并對(duì)對(duì) 進(jìn)程的進(jìn)程的PCB做相應(yīng)修改。做相應(yīng)修改。 2 進(jìn)程的換入進(jìn)程的換入 系統(tǒng)定時(shí)查看進(jìn)程狀態(tài)，從中找出系統(tǒng)定時(shí)查看進(jìn)程狀態(tài)，從中找出“就緒就緒”狀態(tài)，但已狀態(tài)，但已換出的進(jìn)程，將其中換

38、出時(shí)間最長的作為換入進(jìn)程。換出的進(jìn)程，將其中換出時(shí)間最長的作為換入進(jìn)程。第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理內(nèi)存分配方法：內(nèi)存分配方法：1 1 單一連續(xù)分配單一連續(xù)分配 2 2 固定分區(qū)分配固定分區(qū)分配3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配4 伙伴系統(tǒng)伙伴系統(tǒng)5 可重定位分區(qū)分配可重定位分區(qū)分配離散分配離散分配連續(xù)分配連續(xù)分配碎片碎片 分頁存儲(chǔ)管理：分頁存儲(chǔ)管理： 分段存儲(chǔ)管理分段存儲(chǔ)管理 基本分頁（純分頁）存儲(chǔ)管理基本分頁（純分頁）存儲(chǔ)管理第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 1 1 頁面與物理塊頁面與物理塊4.5.1 4.5.1 分頁存儲(chǔ)管理的基本方法分頁存儲(chǔ)

39、管理的基本方法（1）邏輯地址空間分成若干大小相等的片，稱為頁或者頁面）邏輯地址空間分成若干大小相等的片，稱為頁或者頁面（2）內(nèi)存空間劃分成與頁面大小相等的塊，稱為（物理）塊）內(nèi)存空間劃分成與頁面大小相等的塊，稱為（物理）塊（3）進(jìn)程的若干頁，分別裝入可以不相鄰的物理塊中，最后）進(jìn)程的若干頁，分別裝入可以不相鄰的物理塊中，最后 一頁中存在一頁中存在“頁內(nèi)碎片頁內(nèi)碎片”第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理1 1 頁面頁面（4 4）頁面大?。╉撁娲笮√。核槠瑴p少，頁表過長太小：碎片減少，頁表過長太大：頁表短，碎片增大太大：頁表短，碎片增大適應(yīng)大小：適應(yīng)大?。?12B8KBn 4.5 分頁存儲(chǔ)管理方式

40、分頁存儲(chǔ)管理方式 4.5.1 4.5.1 分頁存儲(chǔ)管理的基本方法分頁存儲(chǔ)管理的基本方法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理2 2 地址結(jié)構(gòu)地址結(jié)構(gòu) 圖中的地址長度為圖中的地址長度為3232位，其中位，其中0 - 110 - 11位為頁內(nèi)地位為頁內(nèi)地址，即每頁的大小為址，即每頁的大小為4 KB4 KB；12 - 3112 - 31位為頁號(hào)，地址位為頁號(hào)，地址空間最多允許有空間最多允許有1 M1 M頁頁n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.1 4.5.1 分頁存儲(chǔ)管理的基本方法分頁存儲(chǔ)管理的基本方法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理2 2 地址結(jié)構(gòu)地址結(jié)構(gòu) 對(duì)于某特定機(jī)器，其地址結(jié)構(gòu)

41、是一定的。若給對(duì)于某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為定一個(gè)邏輯地址空間中的地址為A A，頁面的大小為，頁面的大小為L L，則頁號(hào)則頁號(hào)P P和頁內(nèi)地址和頁內(nèi)地址d d可按下式求得：可按下式求得：AMODLdLAINTP例如，其系統(tǒng)的頁面大小為例如，其系統(tǒng)的頁面大小為1 KB，設(shè)，設(shè)A = 2170 B，則由上式可以求得則由上式可以求得P = 2，d = 122。n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.1 4.5.1 分頁存儲(chǔ)管理的基本方法分頁存儲(chǔ)管理的基本方法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理3 3 頁表頁表用戶程序0 頁1 頁2 頁3 頁4 頁5

42、頁n 頁頁表頁號(hào)塊號(hào)02132638495內(nèi)存012345678910n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.1 4.5.1 分頁存儲(chǔ)管理的基本方法分頁存儲(chǔ)管理的基本方法第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.2 4.5.2 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)基本任務(wù)：基本任務(wù)： 實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換1 1 基本的地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu)頁內(nèi)地址與塊內(nèi)地址一一對(duì)應(yīng)頁內(nèi)地址與塊內(nèi)地址一一對(duì)應(yīng)頁號(hào)轉(zhuǎn)換為塊號(hào)：借助于頁表頁號(hào)轉(zhuǎn)換為塊號(hào)：借助于頁表 頁表駐留內(nèi)存，設(shè)置一個(gè)頁表寄存器頁表駐留內(nèi)存，設(shè)置一個(gè)頁

43、表寄存器PTR，存放頁表在內(nèi)存中的始址和頁表長度，平時(shí)存在存放頁表在內(nèi)存中的始址和頁表長度，平時(shí)存在PCB中，調(diào)度進(jìn)程時(shí)才裝入中，調(diào)度進(jìn)程時(shí)才裝入PTR。第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.2 4.5.2 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)頁表寄存器頁表始址頁表長度頁號(hào)(3)頁內(nèi)地址邏輯地址L越界中斷1塊號(hào)b頁表頁號(hào)012物理地址3第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.2 4.5.2 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)2 2 具有快表的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu) 成本的關(guān)系，快表一般很小，通常只存放成本的

44、關(guān)系，快表一般很小，通常只存放16 16 512 512個(gè)頁表項(xiàng)個(gè)頁表項(xiàng)頁表在內(nèi)存頁表在內(nèi)存兩次訪問內(nèi)存兩次訪問內(nèi)存聯(lián)想寄存器（快表）：并行查詢能力聯(lián)想寄存器（快表）：并行查詢能力快表雖然很小，但命中率可達(dá)快表雖然很小，但命中率可達(dá)90%以上，可將因以上，可將因地址變換機(jī)構(gòu)而造成的速度損失減少到地址變換機(jī)構(gòu)而造成的速度損失減少到10%以下以下第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.2 4.5.2 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)頁表寄存器頁表始址頁表長度頁號(hào)頁內(nèi)地址邏輯地址L越界中斷塊號(hào)b頁表頁號(hào)頁號(hào)輸入寄存器塊號(hào)bb快表d物理地址第四章第四章 存儲(chǔ)器管

45、理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.3 4.5.3 訪問內(nèi)存的有效時(shí)間訪問內(nèi)存的有效時(shí)間1 1 定義定義 從進(jìn)程發(fā)出指定邏輯地址的訪問請(qǐng)求，經(jīng)過從進(jìn)程發(fā)出指定邏輯地址的訪問請(qǐng)求，經(jīng)過地址變換，到在內(nèi)存中找到對(duì)應(yīng)的實(shí)際物理地址地址變換，到在內(nèi)存中找到對(duì)應(yīng)的實(shí)際物理地址單元并取出數(shù)據(jù)，所花費(fèi)的時(shí)間總和。單元并取出數(shù)據(jù)，所花費(fèi)的時(shí)間總和?；痉猪摚夯痉猪摚篍AT=t+t=2t引入快表：引入快表：EAT=a +(t+ )(1-a)+t第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.4 4.5.4 兩級(jí)和多級(jí)頁表兩級(jí)和多級(jí)頁表1 1

46、 引入引入頁表離散分配頁表離散分配頁表龐大，需要占用相當(dāng)大的連續(xù)內(nèi)存空間頁表龐大，需要占用相當(dāng)大的連續(xù)內(nèi)存空間2 解決方案解決方案將當(dāng)前需要的頁表調(diào)入內(nèi)存，其余留在磁盤將當(dāng)前需要的頁表調(diào)入內(nèi)存，其余留在磁盤第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.4 4.5.4 兩級(jí)和多級(jí)頁表兩級(jí)和多級(jí)頁表3 3 兩級(jí)頁表兩級(jí)頁表將頁表分頁，離散存儲(chǔ)將頁表分頁，離散存儲(chǔ) 32位邏輯地址空間，頁面大小為位邏輯地址空間，頁面大小為4KB，頁表占，頁表占用用1MB。（1）離散分配）離散分配為頁表頁面建立頁表，稱為外層頁表為頁表頁面建立頁表，稱為外層頁表第四章第四章 存儲(chǔ)

47、器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.4 4.5.4 兩級(jí)和多級(jí)頁表兩級(jí)和多級(jí)頁表外層頁號(hào)外層頁內(nèi)地址頁內(nèi)地址P1P2d31222112110第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.4 4.5.4 兩級(jí)和多級(jí)頁表兩級(jí)和多級(jí)頁表101110780121742n第0頁頁表1460121023第1頁頁表114115011023外部頁表012345671141151468第n頁頁存空間第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.4 4.5.4 兩級(jí)和多級(jí)

48、頁表兩級(jí)和多級(jí)頁表外部頁號(hào)P1P2外部頁內(nèi)地址 頁內(nèi)地址d邏輯地址外部頁表寄存器外部頁表db頁表頁表物理地址第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 分頁存儲(chǔ)管理方式分頁存儲(chǔ)管理方式 4.5.4 4.5.4 兩級(jí)和多級(jí)頁表兩級(jí)和多級(jí)頁表（2 2）分級(jí)調(diào)入）分級(jí)調(diào)入邏輯地址邏輯地址6464位，采用兩級(jí)頁表，頁面大小位，采用兩級(jí)頁表，頁面大小4KB4KB 運(yùn)行的進(jìn)程，外部頁表調(diào)入內(nèi)存。頁表調(diào)入一運(yùn)行的進(jìn)程，外部頁表調(diào)入內(nèi)存。頁表調(diào)入一頁或幾頁即可。設(shè)置狀態(tài)位頁或幾頁即可。設(shè)置狀態(tài)位S。4 多級(jí)頁表多級(jí)頁表頁表分頁大小頁表分頁大小4KB。外層頁表大小。外層頁表大小242（16384GB）第四章第

49、四章 存儲(chǔ)器管理存儲(chǔ)器管理固定分區(qū)固定分區(qū)動(dòng)態(tài)分區(qū)動(dòng)態(tài)分區(qū)分頁管理分頁管理提高內(nèi)存利用率提高內(nèi)存利用率分段存儲(chǔ)管理分段存儲(chǔ)管理滿足用戶編程和使用滿足用戶編程和使用第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.6 基本分段存儲(chǔ)管理基本分段存儲(chǔ)管理 1 1 分區(qū)分配：碎片分區(qū)分配：碎片4.6.1 4.6.1 分段管理方式的引入分段管理方式的引入 頁式分配：連續(xù)虛頁上的內(nèi)容不是邏輯意義上的頁式分配：連續(xù)虛頁上的內(nèi)容不是邏輯意義上的 完整信息單位完整信息單位2 優(yōu)點(diǎn)優(yōu)點(diǎn)方便編程方便編程信息共享信息共享信息保護(hù)信息保護(hù)動(dòng)態(tài)增長動(dòng)態(tài)增長動(dòng)態(tài)鏈接動(dòng)態(tài)鏈接第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 基本分段存儲(chǔ)

50、管理基本分段存儲(chǔ)管理 1 1 分段分段4.5.2 4.5.2 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理 每個(gè)作業(yè)的地址空間按程序本身的自然邏輯關(guān)系每個(gè)作業(yè)的地址空間按程序本身的自然邏輯關(guān)系分成若干段。每個(gè)段有自己的段名，且都是從分成若干段。每個(gè)段有自己的段名，且都是從0 0開始，開始，長度任意。地址由段號(hào)長度任意。地址由段號(hào)S S和段內(nèi)偏移量和段內(nèi)偏移量WW構(gòu)成，每個(gè)構(gòu)成，每個(gè)段占一個(gè)分區(qū)。段占一個(gè)分區(qū)。第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 基本分段存儲(chǔ)管理基本分段存儲(chǔ)管理 2 2 段表段表4.5.2 4.5.2 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理 系統(tǒng)為進(jìn)程的每個(gè)分段分配一個(gè)連續(xù)分區(qū)，

51、而系統(tǒng)為進(jìn)程的每個(gè)分段分配一個(gè)連續(xù)分區(qū)，而進(jìn)程中的各個(gè)段可以離散地移入內(nèi)存中不同的分區(qū)進(jìn)程中的各個(gè)段可以離散地移入內(nèi)存中不同的分區(qū)中。中。每個(gè)進(jìn)程一張段表，用于實(shí)現(xiàn)從邏輯段到物理內(nèi)存每個(gè)進(jìn)程一張段表，用于實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。區(qū)的映射。第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理n 4.5 基本分段存儲(chǔ)管理基本分段存儲(chǔ)管理 2 2 段表段表4.5.2 4.5.2 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理作業(yè)空間(MAIN)=0030 K(X)=1020 K(D)=2015 K(S)=3010 K30 K20 K15 K10 K40 K80 K段長基址段號(hào)(MAIN)=030 K(X)=120 K(

52、D)=215 K(S)=310 K040 K80 K120 K150 K段表內(nèi)存空間0123120 K150 K第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理3 3 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)段表寄存器：存放段表始址和段表長度段表寄存器：存放段表始址和段表長度控制寄存器段表始址段表長度2100段號(hào)S越界1 K段長600段號(hào)01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理地址變換示例地址變換示例第0段第1段第2段段長段起始地址20KB50KB40KB110KB20KB75KB段號(hào)012作業(yè)第0段作業(yè)第2段作業(yè)第1段 50KB70KB75KB95KB110KB150KBSMT