第4章存儲(chǔ)管理1

1、第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理 存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要資源存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要資源, 雖然雖然存儲(chǔ)器的容量迅速增加存儲(chǔ)器的容量迅速增加, 但軟件的需求也同但軟件的需求也同樣在急劇膨脹樣在急劇膨脹, 存儲(chǔ)器仍然是緊俏資源。存存儲(chǔ)器仍然是緊俏資源。存儲(chǔ)器管理是操作系統(tǒng)的最重要部分。儲(chǔ)器管理是操作系統(tǒng)的最重要部分?！捌款i瓶頸”：關(guān)鍵、緊張：關(guān)鍵、緊張帕金森定律帕金森定律(你用的人多你用的人多,你需要的人員更多你需要的人員更多) 內(nèi)存多大，程序多長內(nèi)存多大，程序多長4.1 概述概述4.1.1 存儲(chǔ)體系存儲(chǔ)體系cache主存主存磁盤磁盤存儲(chǔ)器的層次結(jié)構(gòu)：存儲(chǔ)器的層次結(jié)構(gòu)：高速緩存高速緩存cac

2、he： 數(shù)百數(shù)百k字節(jié)、非?？焖佟嘿F、易變字節(jié)、非?？焖?、昂貴、易變內(nèi)存內(nèi)存ram： 數(shù)數(shù)m到數(shù)百到數(shù)百m字節(jié)、中等速度、中等價(jià)格、易變字節(jié)、中等速度、中等價(jià)格、易變 磁盤：磁盤： 數(shù)數(shù)m到數(shù)百到數(shù)百g字節(jié)、低速、價(jià)廉、斷電仍保存字節(jié)、低速、價(jià)廉、斷電仍保存 內(nèi)存空間內(nèi)存空間: 是由存儲(chǔ)單元是由存儲(chǔ)單元(字節(jié)或字字節(jié)或字)組成的一維組成的一維連續(xù)的地址空間連續(xù)的地址空間; 內(nèi)存空間用來存放當(dāng)前正在運(yùn)行程內(nèi)存空間用來存放當(dāng)前正在運(yùn)行程序的代碼及數(shù)據(jù)序的代碼及數(shù)據(jù), 是程序中指令本身地址所指的存儲(chǔ)是程序中指令本身地址所指的存儲(chǔ)器、亦即程序計(jì)數(shù)器所指的存儲(chǔ)器。器、亦即程序計(jì)數(shù)器所指的存儲(chǔ)器。 內(nèi)存

3、的要求內(nèi)存的要求: 能直接存取能直接存取, 訪問速度盡量快訪問速度盡量快, 應(yīng)與應(yīng)與cpu 取指速度相匹配取指速度相匹配, 足夠大足夠大, 能裝下當(dāng)前運(yùn)行的程能裝下當(dāng)前運(yùn)行的程序和數(shù)據(jù)序和數(shù)據(jù), 否則否則cpu執(zhí)行速度就會(huì)受到內(nèi)存速度和容執(zhí)行速度就會(huì)受到內(nèi)存速度和容量的影響而得不到充分發(fā)揮。量的影響而得不到充分發(fā)揮。 內(nèi)存可以分為：內(nèi)存可以分為： 系統(tǒng)區(qū)：用于存放操作系統(tǒng)系統(tǒng)區(qū)：用于存放操作系統(tǒng) 用戶區(qū)：用于裝入并存放用戶程序和數(shù)據(jù)用戶區(qū)：用于裝入并存放用戶程序和數(shù)據(jù)。4.1.2 存儲(chǔ)管理目的存儲(chǔ)管理目的1. 充分利用內(nèi)存充分利用內(nèi)存, 為多道程序并發(fā)執(zhí)行提供存儲(chǔ)基礎(chǔ)為多道程序并發(fā)執(zhí)行提供存儲(chǔ)

4、基礎(chǔ)2. 盡可能方便用戶使用盡可能方便用戶使用 自動(dòng)裝入用戶程序自動(dòng)裝入用戶程序 用戶程序中不必考慮硬件細(xì)節(jié)用戶程序中不必考慮硬件細(xì)節(jié)3. 系統(tǒng)能夠解決程序空間比實(shí)際內(nèi)存空間大的問題系統(tǒng)能夠解決程序空間比實(shí)際內(nèi)存空間大的問題4. 程序在執(zhí)行時(shí)可以動(dòng)態(tài)伸縮程序在執(zhí)行時(shí)可以動(dòng)態(tài)伸縮5. 存儲(chǔ)保護(hù)與安全存儲(chǔ)保護(hù)與安全6. 共享與通信共享與通信7. 了解有關(guān)資源的使用狀況了解有關(guān)資源的使用狀況8. 實(shí)現(xiàn)的性能和代價(jià)實(shí)現(xiàn)的性能和代價(jià), 性能高時(shí)空開銷小性能高時(shí)空開銷小 4.1.3 存儲(chǔ)管理的內(nèi)容存儲(chǔ)管理的內(nèi)容1. 內(nèi)存空間的管理、分配與回收內(nèi)存空間的管理、分配與回收 記錄內(nèi)存的使用情況（內(nèi)存分配回收的依

5、據(jù)）記錄內(nèi)存的使用情況（內(nèi)存分配回收的依據(jù)） 設(shè)置相應(yīng)的內(nèi)存分配表設(shè)置相應(yīng)的內(nèi)存分配表 內(nèi)存空間劃分內(nèi)存空間劃分: 等長或不等長等長或不等長 確定分配算法確定分配算法, 實(shí)施內(nèi)存分配實(shí)施內(nèi)存分配 回收內(nèi)存回收內(nèi)存 分配回收方式分配回收方式: 靜態(tài)分配與動(dòng)態(tài)分配靜態(tài)分配與動(dòng)態(tài)分配2. 存儲(chǔ)共享存儲(chǔ)共享內(nèi)存共享：兩個(gè)或多個(gè)進(jìn)程共用內(nèi)存中相同區(qū)域內(nèi)存共享：兩個(gè)或多個(gè)進(jìn)程共用內(nèi)存中相同區(qū)域 目的：節(jié)省內(nèi)存空間，提高內(nèi)存利用率目的：節(jié)省內(nèi)存空間，提高內(nèi)存利用率 實(shí)現(xiàn)進(jìn)程通信實(shí)現(xiàn)進(jìn)程通信(數(shù)據(jù)共享數(shù)據(jù)共享) 共享內(nèi)容：共享內(nèi)容： 代碼共享，要求代碼為純代碼代碼共享，要求代碼為純代碼 數(shù)據(jù)共享數(shù)據(jù)共享3.

6、存儲(chǔ)保護(hù)與安全存儲(chǔ)保護(hù)與安全 為多個(gè)程序共享內(nèi)存提供保障為多個(gè)程序共享內(nèi)存提供保障,使內(nèi)存中的各道程使內(nèi)存中的各道程序只能訪問它自己的區(qū)域序只能訪問它自己的區(qū)域, 避免各道程序間相互干攏避免各道程序間相互干攏, 特別是當(dāng)一道程序發(fā)生錯(cuò)誤時(shí)特別是當(dāng)一道程序發(fā)生錯(cuò)誤時(shí), 不致于影響其他程序不致于影響其他程序的運(yùn)行。通常由硬件完成保護(hù)功能的運(yùn)行。通常由硬件完成保護(hù)功能, 由軟件輔助實(shí)現(xiàn)。由軟件輔助實(shí)現(xiàn)。保護(hù)范圍保護(hù)范圍 保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯(有意或無意的有意或無意的) 不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù) (系統(tǒng)區(qū)地址空

7、間系統(tǒng)區(qū)地址空間, 其他用戶程序的地址空間其他用戶程序的地址空間)保護(hù)方法保護(hù)方法防止地址越界防止地址越界 每個(gè)進(jìn)程都有自己的地址空間每個(gè)進(jìn)程都有自己的地址空間, 應(yīng)防止發(fā)生地址應(yīng)防止發(fā)生地址越界越界; 當(dāng)程序要訪問某內(nèi)存單元時(shí)當(dāng)程序要訪問某內(nèi)存單元時(shí), 由硬件檢查是否由硬件檢查是否越界越界, 如未越界則執(zhí)行如未越界則執(zhí)行, 否則產(chǎn)生地址越界中斷。否則產(chǎn)生地址越界中斷。 硬件提供一對(duì)寄存器硬件提供一對(duì)寄存器: (上界寄存器上界寄存器/下界寄存器下界寄存器) 基址寄存器基址寄存器: 存起始地址。存起始地址。 限長寄存器限長寄存器: 存長度存長度權(quán)限保護(hù)權(quán)限保護(hù): 對(duì)于多進(jìn)程共享的存儲(chǔ)區(qū)域?qū)τ诙噙M(jìn)

8、程共享的存儲(chǔ)區(qū)域, 各進(jìn)程都有各進(jìn)程都有自己的自己的訪問權(quán)限訪問權(quán)限; 如果越權(quán)訪問如果越權(quán)訪問, 則發(fā)生讀寫保護(hù)。則發(fā)生讀寫保護(hù)。4. 內(nèi)存內(nèi)存“擴(kuò)充擴(kuò)充” 通過虛擬存儲(chǔ)技術(shù)實(shí)現(xiàn)通過虛擬存儲(chǔ)技術(shù)實(shí)現(xiàn) 用戶在編制程序時(shí)，不應(yīng)該受內(nèi)存容量限制，所用戶在編制程序時(shí)，不應(yīng)該受內(nèi)存容量限制，所以要采用一定技術(shù)來以要采用一定技術(shù)來擴(kuò)充擴(kuò)充內(nèi)存的容量，使用戶得到內(nèi)存的容量，使用戶得到比實(shí)際內(nèi)存容量大的多的內(nèi)存空間。比實(shí)際內(nèi)存容量大的多的內(nèi)存空間。 具體實(shí)現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將具體實(shí)現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用。通過這種方法把內(nèi)存內(nèi)存和外存結(jié)合起來統(tǒng)一使用。通

9、過這種方法把內(nèi)存擴(kuò)充，使用戶在編制程序時(shí)不受內(nèi)存限制。擴(kuò)充，使用戶在編制程序時(shí)不受內(nèi)存限制。5. 程序的裝入程序的裝入 創(chuàng)建進(jìn)程的第一件事創(chuàng)建進(jìn)程的第一件事, 就是將程序和數(shù)據(jù)裝入內(nèi)就是將程序和數(shù)據(jù)裝入內(nèi)存。對(duì)不同的地址映射方式對(duì)應(yīng)有多種裝入方式存。對(duì)不同的地址映射方式對(duì)應(yīng)有多種裝入方式4.2 程序的裝入和鏈接程序的裝入和鏈接源程序源程序編譯程序編譯程序或匯編程序或匯編程序目標(biāo)目標(biāo)模塊模塊鏈接程序鏈接程序裝入裝入模塊模塊裝入程序裝入程序裝入階段裝入階段編譯階段編譯階段內(nèi)存中內(nèi)存中可執(zhí)行可執(zhí)行代碼代碼鏈接階段鏈接階段對(duì)用戶程序的處理過程對(duì)用戶程序的處理過程4.2.1 地址映射地址映射地址映射有稱

10、為地址重定位地址映射有稱為地址重定位, 地址變換地址變換 邏輯地址邏輯地址 地址映射地址映射 物理地址物理地址(相對(duì)地址相對(duì)地址, 虛地址虛地址) (絕對(duì)地址絕對(duì)地址, 實(shí)地址實(shí)地址)地址映射地址映射ba=1000.load a 200 3456 1100物理地址空間物理地址空間load a d1d1 3456源程序源程序load a 200 3456000100200編譯連接編譯連接邏輯地址空間邏輯地址空間1200(1)邏輯地址（相對(duì)地址，虛地址）邏輯地址（相對(duì)地址，虛地址） 用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼, 目目標(biāo)代碼通常采用相對(duì)地址的形式標(biāo)代

11、碼通常采用相對(duì)地址的形式, 其首地址為其首地址為0, 其余其余指令中的地址都相對(duì)于首地址而編址。指令中的地址都相對(duì)于首地址而編址。 不能用邏輯地址直接在內(nèi)存中讀取信息。不能用邏輯地址直接在內(nèi)存中讀取信息。(2)物理地址（絕對(duì)地址，實(shí)地址）物理地址（絕對(duì)地址，實(shí)地址） 內(nèi)存中存儲(chǔ)單元的地址內(nèi)存中存儲(chǔ)單元的地址, 可直接尋址。可直接尋址。(3)地址映射地址映射 為了保證為了保證 cpu執(zhí)行指令時(shí)可正確訪問存儲(chǔ)單元執(zhí)行指令時(shí)可正確訪問存儲(chǔ)單元, 需將用戶程序中的邏輯地址需將用戶程序中的邏輯地址, 轉(zhuǎn)換為運(yùn)行時(shí)由機(jī)器直轉(zhuǎn)換為運(yùn)行時(shí)由機(jī)器直接尋址的物理地址接尋址的物理地址, 這一過程稱為地址映射。這一過

12、程稱為地址映射。03456.load a 200.0100200300.load a 2003456邏輯地址空間邏輯地址空間110012001300物理地址空間物理地址空間200vr1000br地址重定位地址重定位地址映射的原因地址映射的原因 當(dāng)程序裝入內(nèi)存時(shí)當(dāng)程序裝入內(nèi)存時(shí), 操作系統(tǒng)要為該程序分配一操作系統(tǒng)要為該程序分配一個(gè)合適的內(nèi)存空間個(gè)合適的內(nèi)存空間, 由于程序的邏輯地址與分配到內(nèi)由于程序的邏輯地址與分配到內(nèi)存物理地址不一致存物理地址不一致, 而而cpu執(zhí)行指令時(shí)執(zhí)行指令時(shí), 是按物理地是按物理地址進(jìn)行的址進(jìn)行的, 所以要進(jìn)行地址轉(zhuǎn)換。所以要進(jìn)行地址轉(zhuǎn)換。靜態(tài)重定位靜態(tài)重定位 當(dāng)用戶程

13、序被裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時(shí)由軟件完成）。內(nèi)存時(shí)由軟件完成）。動(dòng)態(tài)重定位動(dòng)態(tài)重定位 在程序運(yùn)行過程中要訪問數(shù)據(jù)時(shí)再進(jìn)行地址變?cè)诔绦蜻\(yùn)行過程中要訪問數(shù)據(jù)時(shí)再進(jìn)行地址變換換(在逐條指令執(zhí)行時(shí)完成地址映射在逐條指令執(zhí)行時(shí)完成地址映射; 為了提高效率為了提高效率, 此工作一般由硬件地址映射機(jī)制來完成此工作一般由硬件地址映射機(jī)制來完成; 硬件支持硬件支持,軟硬件結(jié)合完成軟硬件結(jié)合完成), 硬件上需要一對(duì)寄存器的支持。硬件上需要一對(duì)寄存器的支持。程序的裝入方式程序的裝入

14、方式1. 絕對(duì)裝入方式：絕對(duì)裝入方式：編譯產(chǎn)生的是絕對(duì)地址編譯產(chǎn)生的是絕對(duì)地址, 按此按此絕對(duì)地址裝入程序和數(shù)據(jù)。絕對(duì)地址裝入程序和數(shù)據(jù)。2. 可重定位裝入方式：可重定位裝入方式：將邏輯地址將邏輯地址映射為映射為物理物理地址裝入地址裝入, 一次地址變換不再改變稱靜態(tài)重定一次地址變換不再改變稱靜態(tài)重定位。地址變換在裝入階段完成。位。地址變換在裝入階段完成。3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式：動(dòng)態(tài)運(yùn)行時(shí)裝入方式：程序運(yùn)行過程中程序運(yùn)行過程中, 在內(nèi)在內(nèi)存中的位置可以改變存中的位置可以改變, 因此邊運(yùn)行因此邊運(yùn)行, 邊裝入。邊裝入。稱動(dòng)態(tài)重定位。地址變換在運(yùn)行階段完成。稱動(dòng)態(tài)重定位。地址變換在運(yùn)行階段完成。4

15、.2.2 程序的裝入程序的裝入程序的鏈接方式程序的鏈接方式1. 靜態(tài)鏈接方式：靜態(tài)鏈接方式：裝入前進(jìn)行鏈接裝入前進(jìn)行鏈接, 將所有將所有模塊的相對(duì)地址鏈接起來模塊的相對(duì)地址鏈接起來, 形成整個(gè)程序形成整個(gè)程序的連續(xù)的邏輯地址。的連續(xù)的邏輯地址。2. 裝入時(shí)動(dòng)態(tài)鏈接：裝入時(shí)動(dòng)態(tài)鏈接：邊裝入、邊鏈接邊裝入、邊鏈接, 各模各模塊獨(dú)立分開裝入內(nèi)存的不同位置塊獨(dú)立分開裝入內(nèi)存的不同位置, 便于修便于修改改, 便于共享。便于共享。3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接：運(yùn)行時(shí)動(dòng)態(tài)鏈接：邊運(yùn)行、邊裝入邊運(yùn)行、邊裝入, 有些有些模塊往往不會(huì)運(yùn)行到模塊往往不會(huì)運(yùn)行到(如錯(cuò)誤處理如錯(cuò)誤處理), 不必裝不必裝入，效率高節(jié)省內(nèi)存。入，

16、效率高節(jié)省內(nèi)存。4.2.3 程序的鏈接程序的鏈接4.3 各種存儲(chǔ)管理方案各種存儲(chǔ)管理方案單用戶單用戶(連續(xù)區(qū)連續(xù)區(qū))存儲(chǔ)管理：存儲(chǔ)管理： 單用戶系統(tǒng)在一段時(shí)間內(nèi)單用戶系統(tǒng)在一段時(shí)間內(nèi), 只有一個(gè)進(jìn)程在內(nèi)存只有一個(gè)進(jìn)程在內(nèi)存, 故內(nèi)存分配管理十分簡(jiǎn)單故內(nèi)存分配管理十分簡(jiǎn)單, 內(nèi)存利用率低。內(nèi)存分為內(nèi)存利用率低。內(nèi)存分為兩個(gè)區(qū)域兩個(gè)區(qū)域, 一個(gè)供操作系統(tǒng)使用一個(gè)供操作系統(tǒng)使用, 一個(gè)供用戶使用。一個(gè)供用戶使用。用戶程序用戶程序ram中的中的操作系統(tǒng)操作系統(tǒng)0 xfff0ram中的中的操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序0rom中的設(shè)中的設(shè)備驅(qū)動(dòng)程序備驅(qū)動(dòng)程序用戶程序用戶程序ram中的中的操作系統(tǒng)操作系

17、統(tǒng)04.3.1 分區(qū)存儲(chǔ)管理方案分區(qū)存儲(chǔ)管理方案 系統(tǒng)把內(nèi)存用戶區(qū)劃分為若干分區(qū)系統(tǒng)把內(nèi)存用戶區(qū)劃分為若干分區(qū), 分區(qū)大小分區(qū)大小可以相等可以相等, 也可以不等。一個(gè)進(jìn)程占據(jù)一個(gè)分區(qū)。也可以不等。一個(gè)進(jìn)程占據(jù)一個(gè)分區(qū)。固定分區(qū)固定分區(qū): 預(yù)先把可分配的主存儲(chǔ)器空間分割成若干個(gè)連預(yù)先把可分配的主存儲(chǔ)器空間分割成若干個(gè)連續(xù)區(qū)域續(xù)區(qū)域, 稱為一個(gè)分區(qū)稱為一個(gè)分區(qū); 每個(gè)分區(qū)的大小可以相同也每個(gè)分區(qū)的大小可以相同也可以不同可以不同, 但固定不變但固定不變, 每個(gè)分區(qū)裝一個(gè)作業(yè)。每個(gè)分區(qū)裝一個(gè)作業(yè)。存儲(chǔ)分配：存儲(chǔ)分配：如果有一個(gè)空閑區(qū)如果有一個(gè)空閑區(qū), 則分配給進(jìn)程。則分配給進(jìn)程。內(nèi)存管理：內(nèi)存管理：設(shè)

18、置內(nèi)存分配表設(shè)置內(nèi)存分配表內(nèi)存分配內(nèi)存分配: 查找分配表查找分配表, 找到合適的分區(qū)找到合適的分區(qū); 回收回收:簡(jiǎn)單簡(jiǎn)單缺點(diǎn)：缺點(diǎn)：內(nèi)存利用率不高內(nèi)存利用率不高分區(qū)號(hào)分區(qū)號(hào)起始地址起始地址長度長度狀態(tài)狀態(tài)進(jìn)程名進(jìn)程名分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)700k400k100k04.3.2 可變分區(qū)可變分區(qū)1、基本思想、基本思想 內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時(shí)，內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。若有足夠的空間，則按需要分割一是否分配。若有足夠的空間，則按需要分割一部分分區(qū)給

19、該進(jìn)程；否則令其等待主存空間部分分區(qū)給該進(jìn)程；否則令其等待主存空間可變式分區(qū)的使用情況，其中，陰影部分為空閑區(qū)可變式分區(qū)的使用情況，其中，陰影部分為空閑區(qū)pa(120k)操作系統(tǒng)操作系統(tǒng)(a)pa(120k)操作系統(tǒng)操作系統(tǒng)(b)pb(30k)pc(100k)1m140k0操作系統(tǒng)操作系統(tǒng)(c)pb(30k)pc(100k)270k170kpd(80k)操作系統(tǒng)操作系統(tǒng)(d)pc(100k)70kpd(80k)操作系統(tǒng)操作系統(tǒng)(e)pc(100k)10kpe(60k)20k 始址始址 長度長度 占用標(biāo)志占用標(biāo)志 20k 80k pd20k 80k pd 110k 60k pe 110k 60k

20、 pe 170k 100k pc 170k 100k pc 空空 始址始址 長度長度 占用占用 100k 10k 100k 10k 有效有效 270k 730k 270k 730k 有效有效 空空 (a)已分配區(qū)表已分配區(qū)表 (b)未分配區(qū)表未分配區(qū)表 2、內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)、內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)1)可變分區(qū)分區(qū)表可變分區(qū)分區(qū)表分區(qū)說明表由兩張表格組成分區(qū)說明表由兩張表格組成2) 空閑分區(qū)鏈空閑分區(qū)鏈 （p 108 圖圖 4-5） 將分區(qū)分配信息附加在分區(qū)中將分區(qū)分配信息附加在分區(qū)中, 記錄存貯空間的記錄存貯空間的使用情況。將表格信息放在每個(gè)分區(qū)的首尾兩個(gè)字中使用情況。將表格信息放在每個(gè)分區(qū)的首

21、尾兩個(gè)字中, 利用表格自己管理自己。表格存放如下一些信息：利用表格自己管理自己。表格存放如下一些信息： (1) 狀態(tài)信息狀態(tài)信息: “0”表示該區(qū)空閑表示該區(qū)空閑, “1”表示已分配。表示已分配。 (2) 該區(qū)的大小該區(qū)的大小(以字或塊為單位以字或塊為單位)。 (3) 指針信息指針信息: 構(gòu)成空閑區(qū)鏈。構(gòu)成空閑區(qū)鏈。狀態(tài)位狀態(tài)位 分區(qū)大?。ǚ謪^(qū)大?。╪+2） 前向指針前向指針大小為大小為n的已分配區(qū)或空閑區(qū)的已分配區(qū)或空閑區(qū)狀態(tài)位狀態(tài)位 分區(qū)大?。ǚ謪^(qū)大?。╪+2） 后向指針后向指針3.分區(qū)分配算法：分區(qū)分配算法：首先適配算法首先適配算法: (特點(diǎn)特點(diǎn):簡(jiǎn)單、快速分配簡(jiǎn)單、快速分配) 當(dāng)接到內(nèi)

22、存申請(qǐng)時(shí)當(dāng)接到內(nèi)存申請(qǐng)時(shí), 查空閑塊表查空閑塊表, 找到第一個(gè)不找到第一個(gè)不小于請(qǐng)求的空塊小于請(qǐng)求的空塊, 將其分割并分配。將其分割并分配。最佳適配算法最佳適配算法: (特點(diǎn)特點(diǎn):用最小空間滿足要求用最小空間滿足要求) 接到內(nèi)存申請(qǐng)時(shí)接到內(nèi)存申請(qǐng)時(shí), 在空閑塊表中找到一個(gè)不小于在空閑塊表中找到一個(gè)不小于請(qǐng)求的最小空塊進(jìn)行分配。請(qǐng)求的最小空塊進(jìn)行分配。最壞適配算法最壞適配算法: (特點(diǎn)特點(diǎn):分割后空閑塊仍較大分割后空閑塊仍較大) 接到內(nèi)存申請(qǐng)時(shí)接到內(nèi)存申請(qǐng)時(shí), 在空閑塊表中找到一個(gè)不小于在空閑塊表中找到一個(gè)不小于請(qǐng)求的最大空塊進(jìn)行分配。請(qǐng)求的最大空塊進(jìn)行分配。最佳適配算法的實(shí)現(xiàn)：最佳適配算法的實(shí)

23、現(xiàn)：存儲(chǔ)區(qū)（空白區(qū)）的數(shù)據(jù)結(jié)構(gòu)：空白區(qū)按其容量大小存儲(chǔ)區(qū)（空白區(qū)）的數(shù)據(jù)結(jié)構(gòu)：空白區(qū)按其容量大小遞增連接起來遞增連接起來 即：即：x1 x2 x3 . xn設(shè)請(qǐng)求分配的容量為設(shè)請(qǐng)求分配的容量為s，則從，則從x1開始比較，直至開始比較，直至s xi，然后，從然后，從xi中減去中減去s，如有剩余，則處于空白區(qū)插入，如有剩余，則處于空白區(qū)插入適當(dāng)位置，否則（適當(dāng)位置，否則（ssn），則分配失敗。），則分配失敗。剩余空白區(qū)的處理：如果剩余空白區(qū)的處理：如果xi-s g(參數(shù)參數(shù))，則，則xi全部給全部給作業(yè)，否則，作業(yè)，否則，xi-s插入適當(dāng)位置。插入適當(dāng)位置?？雌饋碜罴眩瑢?shí)際怎么樣？看起來最佳，實(shí)際

24、怎么樣？4.分區(qū)分配操作分區(qū)分配操作1)分配內(nèi)存分配內(nèi)存 p 110 圖圖 4-6 自己看自己看2)回收內(nèi)存回收內(nèi)存 根據(jù)釋放的回收區(qū)首址，從空閑分區(qū)鏈中找到相應(yīng)根據(jù)釋放的回收區(qū)首址，從空閑分區(qū)鏈中找到相應(yīng)的插入點(diǎn)，按回收區(qū)與空閑分區(qū)相鄰情況分為的插入點(diǎn)，按回收區(qū)與空閑分區(qū)相鄰情況分為4種情種情況分別處理，能合并的則合并，見況分別處理，能合并的則合并，見p 110 圖圖4-7 。1.動(dòng)態(tài)重定位的引入動(dòng)態(tài)重定位的引入 碎片問題：碎片問題：經(jīng)過一段時(shí)間的分配回收后經(jīng)過一段時(shí)間的分配回收后, 內(nèi)存中內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都很小存在很多很小的空閑塊。它們每一個(gè)都很小, 不足以不足以滿足

25、分配要求滿足分配要求, 但其總和滿足分配要求但其總和滿足分配要求; 這些空閑塊被這些空閑塊被稱為碎片。稱為碎片。 造成存儲(chǔ)資源的浪費(fèi)造成存儲(chǔ)資源的浪費(fèi) 碎片問題的解決：碎片問題的解決： 緊湊技術(shù)緊湊技術(shù): (緊縮技術(shù)緊縮技術(shù), 浮動(dòng)技術(shù)浮動(dòng)技術(shù), 搬家技術(shù)搬家技術(shù)) 通過在內(nèi)存移動(dòng)程序通過在內(nèi)存移動(dòng)程序, 將所有小的空閑區(qū)域合并將所有小的空閑區(qū)域合并為大的空閑區(qū)域。問題為大的空閑區(qū)域。問題: 開銷大開銷大, 移動(dòng)時(shí)機(jī)。移動(dòng)時(shí)機(jī)。 2.動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位的實(shí)現(xiàn)4.3.3 可重定位分區(qū)分配可重定位分區(qū)分配動(dòng)態(tài)重定位示意圖動(dòng)態(tài)重定位示意圖01234.load a 200.0100200300

26、.load a 2001234程序地址空間程序地址空間110012001300物理地址空間物理地址空間1000重定位寄存器重定位寄存器.1000絕對(duì)地址絕對(duì)地址相對(duì)地址相對(duì)地址2003.動(dòng)態(tài)重定位動(dòng)態(tài)重定位分區(qū)分配算法分區(qū)分配算法 在動(dòng)態(tài)分區(qū)分配算法基礎(chǔ)上增加了緊湊功能在動(dòng)態(tài)分區(qū)分配算法基礎(chǔ)上增加了緊湊功能按動(dòng)態(tài)分區(qū)分配按動(dòng)態(tài)分區(qū)分配修改有關(guān)數(shù)據(jù)結(jié)構(gòu)修改有關(guān)數(shù)據(jù)結(jié)構(gòu)進(jìn)行緊湊進(jìn)行緊湊形成連續(xù)分區(qū)形成連續(xù)分區(qū)修改有關(guān)數(shù)據(jù)結(jié)構(gòu)修改有關(guān)數(shù)據(jù)結(jié)構(gòu)檢索空閑分區(qū)鏈檢索空閑分區(qū)鏈空閑和空閑和u.size?找到找到u.size?返回分區(qū)號(hào)返回分區(qū)號(hào)失敗返回失敗返回請(qǐng)求分配請(qǐng)求分配u.size分區(qū)分區(qū)4.3.4

27、對(duì)換技術(shù)對(duì)換技術(shù)1.對(duì)換的引入對(duì)換的引入 對(duì)換技術(shù)是在多道環(huán)境下擴(kuò)充內(nèi)存采用對(duì)換技術(shù)是在多道環(huán)境下擴(kuò)充內(nèi)存采用的方法的方法, 用以解決在較小的存儲(chǔ)空間中運(yùn)行較用以解決在較小的存儲(chǔ)空間中運(yùn)行較大程序時(shí)遇到的矛盾。大程序時(shí)遇到的矛盾。 對(duì)換技術(shù)被廣泛用于小型分時(shí)系統(tǒng)中對(duì)換技術(shù)被廣泛用于小型分時(shí)系統(tǒng)中, 對(duì)對(duì)換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn)換技術(shù)的發(fā)展導(dǎo)致了虛存技術(shù)的出現(xiàn) 當(dāng)內(nèi)存空間緊張時(shí)當(dāng)內(nèi)存空間緊張時(shí), 系統(tǒng)將內(nèi)存中某些進(jìn)系統(tǒng)將內(nèi)存中某些進(jìn)程暫時(shí)移到外存程暫時(shí)移到外存, 把外存中某些進(jìn)程換進(jìn)內(nèi)存把外存中某些進(jìn)程換進(jìn)內(nèi)存,占據(jù)前者所占用的區(qū)域占據(jù)前者所占用的區(qū)域, 這種技術(shù)是進(jìn)程在內(nèi)這種技術(shù)是進(jìn)程

28、在內(nèi)存與外存之間的動(dòng)態(tài)調(diào)度存與外存之間的動(dòng)態(tài)調(diào)度; 多用于分時(shí)系統(tǒng)中。多用于分時(shí)系統(tǒng)中。2.對(duì)換的單位：對(duì)換的單位：進(jìn)程對(duì)換進(jìn)程對(duì)換分段對(duì)換分段對(duì)換頁面對(duì)換頁面對(duì)換3.對(duì)換空間的管理對(duì)換空間的管理1.外存的劃分外存的劃分: 文件區(qū)和對(duì)換區(qū)文件區(qū)和對(duì)換區(qū)2.對(duì)換區(qū)的管理對(duì)換區(qū)的管理: 連續(xù)分配還是離散分配連續(xù)分配還是離散分配?3.內(nèi)存管理方式是否適合對(duì)換區(qū)的管理內(nèi)存管理方式是否適合對(duì)換區(qū)的管理?1) 換出進(jìn)程的選擇：換出進(jìn)程的選擇： 處于阻塞狀態(tài)、處于阻塞狀態(tài)、 優(yōu)先級(jí)最低且駐留時(shí)間最長優(yōu)先級(jí)最低且駐留時(shí)間最長2) 換出過程換出過程 只換出進(jìn)程非共享部分只換出進(jìn)程非共享部分,共享部分則將共共享部分則將共 享計(jì)數(shù)減享計(jì)數(shù)減1, 結(jié)果為結(jié)果為0時(shí)再將它換出。時(shí)再將它換出。3) 進(jìn)程