操作系統(tǒng)課件6_1

1、第六章第六章 存儲管理存儲管理l又稱內(nèi)存管理、主存管理又稱內(nèi)存管理、主存管理l工作內(nèi)容和任務(wù)由內(nèi)存硬件提供的原始使用方式與用戶工作內(nèi)容和任務(wù)由內(nèi)存硬件提供的原始使用方式與用戶對內(nèi)存的使用要求這兩方面的差距所決定的對內(nèi)存的使用要求這兩方面的差距所決定的1第六章第六章 存儲管理存儲管理l有七種內(nèi)存管理模式有七種內(nèi)存管理模式 2第六章第六章 存儲管理存儲管理l從性能與價格的比較，存儲系統(tǒng)由多種不從性能與價格的比較，存儲系統(tǒng)由多種不同存儲介質(zhì)共同構(gòu)成，從而形成存儲層次同存儲介質(zhì)共同構(gòu)成，從而形成存儲層次3第六章第六章 存儲管理存儲管理l形成存儲層次的原因：形成存儲層次的原因：l由不同速度、價格、容量的

2、存儲介質(zhì)的分工由不同速度、價格、容量的存儲介質(zhì)的分工合作而構(gòu)成的存儲層次，使整個存儲子系統(tǒng)合作而構(gòu)成的存儲層次，使整個存儲子系統(tǒng)達(dá)到性能和價格的很好權(quán)衡。達(dá)到性能和價格的很好權(quán)衡。l內(nèi)存存放當(dāng)前正在運行的程序和數(shù)據(jù)。內(nèi)存存放當(dāng)前正在運行的程序和數(shù)據(jù)。l寄存器存放正在寄存器存放正在CPU上執(zhí)行的指令和數(shù)據(jù)。上執(zhí)行的指令和數(shù)據(jù)。l內(nèi)存中包含內(nèi)存中包含OS代碼和數(shù)據(jù)，用戶程序只有在代碼和數(shù)據(jù)，用戶程序只有在申請時占用內(nèi)存，執(zhí)行完則退出。申請時占用內(nèi)存，執(zhí)行完則退出。4第六章第六章 存儲管理存儲管理l對內(nèi)存的性能要求：對內(nèi)存的性能要求：l容量大足以裝下當(dāng)前正在執(zhí)行的程序和數(shù)據(jù)。容量大足以裝下當(dāng)前正在執(zhí)

3、行的程序和數(shù)據(jù)。l速度速度/容量與容量與CPU匹配，理想的應(yīng)比匹配，理想的應(yīng)比CPU快?？?。 l存放時間：只在開機(jī)時才使用，必須保證開存放時間：只在開機(jī)時才使用，必須保證開機(jī)時的穩(wěn)定和可靠。機(jī)時的穩(wěn)定和可靠。l要求與現(xiàn)實的矛盾：要求與現(xiàn)實的矛盾：l技術(shù)與經(jīng)濟(jì)的原因趕不上技術(shù)與經(jīng)濟(jì)的原因趕不上CPU的發(fā)展的發(fā)展（Parkinson理論）理論）l系統(tǒng)性能瓶頸必須要求系統(tǒng)性能瓶頸必須要求OS或各種輔存解決速或各種輔存解決速度問題。度問題。 5內(nèi)存硬件接口使用特性內(nèi)存硬件接口使用特性(微觀微觀 ) l任一程序在計算機(jī)上運行的順序為任一程序在計算機(jī)上運行的順序為 內(nèi)存內(nèi)存-CPU-I/O-文件文件l裝入

4、內(nèi)存的程序裝入內(nèi)存的程序l微觀上體現(xiàn)為內(nèi)存中的指令通過在處理機(jī)上微觀上體現(xiàn)為內(nèi)存中的指令通過在處理機(jī)上執(zhí)行而實現(xiàn)對內(nèi)存的存取執(zhí)行而實現(xiàn)對內(nèi)存的存取l宏觀上體現(xiàn)為程序（進(jìn)程）對空間和內(nèi)存空宏觀上體現(xiàn)為程序（進(jìn)程）對空間和內(nèi)存空間的概念。間的概念。6有關(guān)指令的構(gòu)成有關(guān)指令的構(gòu)成l指令由操作碼和地址碼兩部分組成指令由操作碼和地址碼兩部分組成l操作碼操作碼l指明指令所要完成的操作，如加法、減法、傳送、移指明指令所要完成的操作，如加法、減法、傳送、移位、轉(zhuǎn)移等。位、轉(zhuǎn)移等。l位數(shù)反映機(jī)器的操作種類，如操作碼七位，則機(jī)器最位數(shù)反映機(jī)器的操作種類，如操作碼七位，則機(jī)器最多包含多包含27=128條指令條指令l

5、地址碼地址碼l指出指令的源操作數(shù)的地址（一個或兩個）、結(jié)果地指出指令的源操作數(shù)的地址（一個或兩個）、結(jié)果地址以及下一條指令地址址以及下一條指令地址 l“地址地址”可以是主存地址、寄存器地址、可以是主存地址、寄存器地址、I/O設(shè)備地設(shè)備地址址 l程序在其生命周期各階段表現(xiàn)出不同的地址形式程序在其生命周期各階段表現(xiàn)出不同的地址形式7有關(guān)指令的構(gòu)成有關(guān)指令的構(gòu)成l以主存地址為例，分析指令的地址碼字段。以主存地址為例，分析指令的地址碼字段。l四地址指令四地址指令l地址字段有四個，其格式為：地址字段有四個，其格式為：lOP為操作碼；為操作碼；lA1 為第一操作數(shù)地址；為第一操作數(shù)地址；lA2 為第二操作

6、數(shù)地址；為第二操作數(shù)地址；lA3 為結(jié)果地址；為結(jié)果地址；lA4 為下一條指令的地址。為下一條指令的地址。 該指令完成該指令完成 (A1) OP (A2) A3的操的操作作 如果指令字長如果指令字長32位，操作碼位，操作碼8位，位，4個個地址字段各占地址字段各占6位，指令的直接尋址范位，指令的直接尋址范圍為：圍為：26 = 64。如果都是主存地址，完成一條四地址如果都是主存地址，完成一條四地址指令，需訪存四次指令，需訪存四次(取指令一次，取兩取指令一次，取兩個操作數(shù)兩次，存結(jié)果一次個操作數(shù)兩次，存結(jié)果一次) 8有關(guān)指令的構(gòu)成有關(guān)指令的構(gòu)成l由于大多數(shù)指令按順序執(zhí)行，由于大多數(shù)指令按順序執(zhí)行，P

7、C既能存放當(dāng)前既能存放當(dāng)前欲執(zhí)行指令的地址，又有計數(shù)功能，自動形成欲執(zhí)行指令的地址，又有計數(shù)功能，自動形成下一條指令地址。下一條指令地址。l指令字中的第四地址字段指令字中的第四地址字段A4可省去，得到三地可省去，得到三地址指令格式。址指令格式。l設(shè)指令字長不變，設(shè)指令字長不變，OP仍為仍為8位，則三地址字段位，則三地址字段各占各占8位，指令直接尋址范圍可達(dá)位，指令直接尋址范圍可達(dá)28 = 256。l若地址字段均為主存地址，完成一條三地址指若地址字段均為主存地址，完成一條三地址指令也需訪問四次存儲器。令也需訪問四次存儲器。 9有關(guān)指令的構(gòu)成有關(guān)指令的構(gòu)成l機(jī)器在運行過程中，中間結(jié)果可暫時存放在寄

8、機(jī)器在運行過程中，中間結(jié)果可暫時存放在寄存器中，得出二地址指令存器中，得出二地址指令l可完成可完成 (A1) OP (A2) A1的操作，的操作，A1既代表既代表源操作數(shù)的地址，又代表存放本次運算結(jié)果的源操作數(shù)的地址，又代表存放本次運算結(jié)果的地址地址 l完成一條指令仍需訪四次存儲器。完成一條指令仍需訪四次存儲器。l如果中間結(jié)果暫存于寄存器，只需三次訪存如果中間結(jié)果暫存于寄存器，只需三次訪存l指令直接尋址范圍可達(dá)：指令直接尋址范圍可達(dá)：212 = 4K 10有關(guān)指令的構(gòu)成有關(guān)指令的構(gòu)成l如果將一個操作數(shù)的地址隱含在運算器中，如果將一個操作數(shù)的地址隱含在運算器中，則指令字中只需給出一個地址碼，構(gòu)成

9、了則指令字中只需給出一個地址碼，構(gòu)成了一地址指令一地址指令l完成一條一地址指令只需兩次訪存。完成一條一地址指令只需兩次訪存。l在指令字長仍為在指令字長仍為32位、操作碼位數(shù)仍固定位、操作碼位數(shù)仍固定8位時，一地址指令直接尋址范圍達(dá)位時，一地址指令直接尋址范圍達(dá)224=16M。 11有關(guān)指令的構(gòu)成有關(guān)指令的構(gòu)成lPDP/11系列機(jī)指令字長系列機(jī)指令字長16位，其指令格位，其指令格式如下表所示式如下表所示 12內(nèi)存硬件接口使用特性內(nèi)存硬件接口使用特性(微觀微觀 )l從微觀角度看指令對內(nèi)存的使用從微觀角度看指令對內(nèi)存的使用l程序?qū)?nèi)存的使用體現(xiàn)為程序向內(nèi)存發(fā)出的程序?qū)?nèi)存的使用體現(xiàn)為程序向內(nèi)存發(fā)出的

10、一次次讀寫請求。一次次讀寫請求。l每條指令有若干次訪存，如執(zhí)行一條指令包括每條指令有若干次訪存，如執(zhí)行一條指令包括13內(nèi)存硬件接口使用特性內(nèi)存硬件接口使用特性(微觀微觀 ) l內(nèi)存接受的讀寫請求來自內(nèi)存接受的讀寫請求來自CPU或或DMA。l內(nèi)存看到的是一個內(nèi)存地址，不管這些地址從哪內(nèi)存看到的是一個內(nèi)存地址，不管這些地址從哪里來（里來（CPU、DMA）、如何產(chǎn)生（指令計數(shù)器、）、如何產(chǎn)生（指令計數(shù)器、基址、間址、變址等尋址方式）基址、間址、變址等尋址方式）l內(nèi)存最小使用單位：內(nèi)存最小使用單位：l從程序角度分為指令從程序角度分為指令l從內(nèi)存（硬件）角度分為從內(nèi)存（硬件）角度分為CPU或或DMA對內(nèi)

11、存發(fā)出對內(nèi)存發(fā)出的一次次讀寫請求的一次次讀寫請求14內(nèi)存硬件接口使用特性內(nèi)存硬件接口使用特性(宏觀宏觀)l基本概念基本概念l內(nèi)存空間：內(nèi)存空間：l內(nèi)存可看作是字節(jié)或字的一個大數(shù)組，每個字節(jié)內(nèi)存可看作是字節(jié)或字的一個大數(shù)組，每個字節(jié)或字都有自己的地址，形成一個地址內(nèi)存空間，或字都有自己的地址，形成一個地址內(nèi)存空間，簡稱內(nèi)存空間。簡稱內(nèi)存空間。l程序分為源程序、目標(biāo)程序、可執(zhí)行程序程序分為源程序、目標(biāo)程序、可執(zhí)行程序l程序空間：程序空間：l一個可執(zhí)行的目標(biāo)程序（包括一個可執(zhí)行的目標(biāo)程序（包括OS）所生成的所有）所生成的所有內(nèi)存地址的集合稱為程序地址空間，簡稱程序空內(nèi)存地址的集合稱為程序地址空間，簡

12、稱程序空間。間。l程序空間包括代碼和數(shù)據(jù)。程序空間包括代碼和數(shù)據(jù)。15內(nèi)存硬件接口使用特性內(nèi)存硬件接口使用特性(宏觀宏觀)16內(nèi)存硬件接口使用特性內(nèi)存硬件接口使用特性(宏觀宏觀)l第一階段（編譯或匯編階段）：將源程序第一階段（編譯或匯編階段）：將源程序轉(zhuǎn)換成機(jī)器指令，將符號地址轉(zhuǎn)換為內(nèi)存轉(zhuǎn)換成機(jī)器指令，將符號地址轉(zhuǎn)換為內(nèi)存地址。地址。l地址轉(zhuǎn)換問題：地址轉(zhuǎn)換問題：l轉(zhuǎn)換后的地址可能是相對地址。轉(zhuǎn)換后的地址可能是相對地址。l并不是所有符號地址都轉(zhuǎn)換為內(nèi)存地址，如調(diào)用并不是所有符號地址都轉(zhuǎn)換為內(nèi)存地址，如調(diào)用外部程序、外部變量等。外部程序、外部變量等。17內(nèi)存硬件接口使用特性內(nèi)存硬件接口使用特性(

13、宏觀宏觀)l第二階段（連接階段）：由目標(biāo)模塊連接第二階段（連接階段）：由目標(biāo)模塊連接形成一個可執(zhí)行的文件，主要工作為：形成一個可執(zhí)行的文件，主要工作為：l將各目標(biāo)模塊中相對地址統(tǒng)一轉(zhuǎn)換為相對該將各目標(biāo)模塊中相對地址統(tǒng)一轉(zhuǎn)換為相對該程序地址的位移。程序地址的位移。l將所有或部分未轉(zhuǎn)換的符號轉(zhuǎn)換為內(nèi)存地址。將所有或部分未轉(zhuǎn)換的符號轉(zhuǎn)換為內(nèi)存地址。l啟動程序時，必須將程序和數(shù)據(jù)裝入內(nèi)存，啟動程序時，必須將程序和數(shù)據(jù)裝入內(nèi)存，在裝入前要重新定位，重新計算偏移量（虛在裝入前要重新定位，重新計算偏移量（虛方式）或?qū)嶋H地址（實方式）。方式）或?qū)嶋H地址（實方式）。18內(nèi)存硬件接口使用特性內(nèi)存硬件接口使用特性(

14、宏觀宏觀)l第三階段：在執(zhí)行階段即執(zhí)行目標(biāo)程序時可能第三階段：在執(zhí)行階段即執(zhí)行目標(biāo)程序時可能需要重定位。需要重定位。l涉及的概念有動態(tài)重定位、動態(tài)地址映射、動態(tài)連接涉及的概念有動態(tài)重定位、動態(tài)地址映射、動態(tài)連接與裝入。與裝入。l第四階段：程序執(zhí)行完畢應(yīng)釋放空間，并以可第四階段：程序執(zhí)行完畢應(yīng)釋放空間，并以可執(zhí)行文件形式保存在外存上。執(zhí)行文件形式保存在外存上。l以上從一個階段到下一個階段都是從一個地址以上從一個階段到下一個階段都是從一個地址空間到另一個地址空間的映射，并且絕對地址空間到另一個地址空間的映射，并且絕對地址一再推遲一再推遲。l指令地址與相對地址、絕對地址的區(qū)別見圖指令地址與相對地址、

15、絕對地址的區(qū)別見圖19指令地址與相對地址、絕對地址的區(qū)別指令地址與相對地址、絕對地址的區(qū)別20指令地址與相對地址、絕對地址的區(qū)別指令地址與相對地址、絕對地址的區(qū)別21第六章第六章 存儲管理存儲管理l6.1 存儲管理功能存儲管理功能l6.2 內(nèi)存資源管理內(nèi)存資源管理l6.3 存儲管理方式存儲管理方式l6.4 外存空間管理外存空間管理l6.5 虛擬存儲系統(tǒng)虛擬存儲系統(tǒng) 226.1 存儲管理功能存儲管理功能l存儲分配和去配存儲分配和去配l為實現(xiàn)存儲資源的分配和收回為實現(xiàn)存儲資源的分配和收回, 操作系統(tǒng)需記錄內(nèi)操作系統(tǒng)需記錄內(nèi)存和外存資源的使用情況，需要兩個表：存和外存資源的使用情況，需要兩個表：l分

16、配表：記錄已經(jīng)分配的區(qū)域分配表：記錄已經(jīng)分配的區(qū)域l空閑表：記錄尚未分配的區(qū)域空閑表：記錄尚未分配的區(qū)域l在虛擬存儲系統(tǒng)中在虛擬存儲系統(tǒng)中, 內(nèi)存和外存各需一個分配表和內(nèi)存和外存各需一個分配表和空閑表空閑表. l分配去配對象分配去配對象l內(nèi)存、外存內(nèi)存、外存(相同方法相同方法)l分配去配時刻分配去配時刻l進(jìn)程創(chuàng)建、撤銷、交換、長度變化進(jìn)程創(chuàng)建、撤銷、交換、長度變化236.1 存儲管理功能存儲管理功能l存儲共享存儲共享l指兩個或多個進(jìn)程共用內(nèi)存中相同的區(qū)域指兩個或多個進(jìn)程共用內(nèi)存中相同的區(qū)域l共享目的：節(jié)省內(nèi)存、相互通訊共享目的：節(jié)省內(nèi)存、相互通訊l共享內(nèi)容：代碼、數(shù)據(jù)共享內(nèi)容：代碼、數(shù)據(jù)l存儲

17、保護(hù)存儲保護(hù)l防止地址越界防止地址越界l防止操作越權(quán)防止操作越權(quán)246.1 存儲管理功能存儲管理功能l存儲擴(kuò)充存儲擴(kuò)充l將內(nèi)存與外存空間有機(jī)結(jié)合將內(nèi)存與外存空間有機(jī)結(jié)合, 形成一個容量相當(dāng)于外形成一個容量相當(dāng)于外存存, 速度接近于內(nèi)存的虛擬存儲系統(tǒng)速度接近于內(nèi)存的虛擬存儲系統(tǒng)l地址映射地址映射l在多道程序系統(tǒng)中在多道程序系統(tǒng)中, 程序產(chǎn)生的地址為程序產(chǎn)生的地址為邏輯地址邏輯地址, 需轉(zhuǎn)需轉(zhuǎn)換為內(nèi)存的換為內(nèi)存的物理地址物理地址, 該轉(zhuǎn)換過程稱該轉(zhuǎn)換過程稱地址映射地址映射l地址映射需要軟件與硬件相結(jié)合來實現(xiàn)地址映射需要軟件與硬件相結(jié)合來實現(xiàn)l硬件支持硬件支持l基址寄存器基址寄存器(base)、限長

18、寄存器、限長寄存器(limit)、快表、快表l使用上述寄存器完成地址映射使用上述寄存器完成地址映射l不能正常完成地址映射時產(chǎn)生中斷不能正常完成地址映射時產(chǎn)生中斷256.2 內(nèi)存資源管理內(nèi)存資源管理l6.2.1 內(nèi)存分區(qū)內(nèi)存分區(qū) l6.2.2 內(nèi)存分配內(nèi)存分配266.2.1 內(nèi)存分區(qū)內(nèi)存分區(qū)l內(nèi)存空間的劃分，可能是靜態(tài)的內(nèi)存空間的劃分，可能是靜態(tài)的, 也可能也可能是動態(tài)的是動態(tài)的; l可能是等長的可能是等長的, 也可能是異長的也可能是異長的276.2.1 內(nèi)存分區(qū)內(nèi)存分區(qū)l靜態(tài)分區(qū)與動態(tài)分區(qū)靜態(tài)分區(qū)與動態(tài)分區(qū)l靜態(tài)分區(qū)：在系統(tǒng)運行前將內(nèi)存空間劃分為靜態(tài)分區(qū)：在系統(tǒng)運行前將內(nèi)存空間劃分為若干個區(qū)域

19、。若干個區(qū)域。l當(dāng)進(jìn)程需要內(nèi)存空間時當(dāng)進(jìn)程需要內(nèi)存空間時, 系統(tǒng)按照某種分配原則系統(tǒng)按照某種分配原則為其分配一個或多個滿足要求的區(qū)域。為其分配一個或多個滿足要求的區(qū)域。l通常通常, 分配給進(jìn)程的內(nèi)存區(qū)域可能比進(jìn)程實際所分配給進(jìn)程的內(nèi)存區(qū)域可能比進(jìn)程實際所需的區(qū)域長。需的區(qū)域長。l動態(tài)分區(qū)：在系統(tǒng)運行過程中劃分內(nèi)存空間。動態(tài)分區(qū)：在系統(tǒng)運行過程中劃分內(nèi)存空間。l通常通常, 系統(tǒng)可按進(jìn)程所需空間的大小為其分配恰系統(tǒng)可按進(jìn)程所需空間的大小為其分配恰好滿足要求的一個或多個區(qū)域好滿足要求的一個或多個區(qū)域286.2.1 內(nèi)存分區(qū)內(nèi)存分區(qū)l等長分區(qū)與異長分區(qū)等長分區(qū)與異長分區(qū)l等長分區(qū)：將存儲空間劃分為若干

20、個長度相等長分區(qū)：將存儲空間劃分為若干個長度相同的區(qū)域同的區(qū)域. l當(dāng)進(jìn)程需要存儲空間時當(dāng)進(jìn)程需要存儲空間時, 系統(tǒng)為其分配一個或多個系統(tǒng)為其分配一個或多個區(qū)域。分為區(qū)域。分為2i個分區(qū)。個分區(qū)。l 異長分區(qū)：將存儲空間劃分為若干個長度不異長分區(qū)：將存儲空間劃分為若干個長度不同的區(qū)域同的區(qū)域. 當(dāng)進(jìn)程需要內(nèi)存時當(dāng)進(jìn)程需要內(nèi)存時, 系統(tǒng)為其分配系統(tǒng)為其分配一個或多個區(qū)域。一個或多個區(qū)域。l根據(jù)程序、程序單位、對象大小來分區(qū)。根據(jù)程序、程序單位、對象大小來分區(qū)。296.2.1 內(nèi)存分區(qū)內(nèi)存分區(qū)l通常作法：通常作法：l靜態(tài)靜態(tài)+等長（頁式、段頁式）：等長（頁式、段頁式）：l有字位映象圖、空閑頁面表和

21、空閑頁面鏈三種方有字位映象圖、空閑頁面表和空閑頁面鏈三種方法。法。l動態(tài)動態(tài)+異長（段式、界地址）：異長（段式、界地址）：l有最先適應(yīng)有最先適應(yīng) (First Fit)、最佳適應(yīng)、最佳適應(yīng) (Best Fit)和最和最壞適應(yīng)壞適應(yīng) (Worst Fit)三種方法三種方法306.2.2 內(nèi)存分配內(nèi)存分配l 靜態(tài)等長分區(qū)的分配靜態(tài)等長分區(qū)的分配l 字位映象圖字位映象圖l 空閑頁面表空閑頁面表l 空閑頁面鏈空閑頁面鏈l動態(tài)異長分區(qū)的分配動態(tài)異長分區(qū)的分配l最先適應(yīng)最先適應(yīng) (First Fit)l最佳適應(yīng)最佳適應(yīng) (Best Fit)l最壞適應(yīng)最壞適應(yīng) (Worst Fit)31字位映象圖（字位映象

22、圖（bit map）1 0 0 1 . 1 0第第0 頁頁第第2 頁頁第第1 頁頁第第 k 頁頁第第 n 頁頁.分配：分配：自頭尋找第一個為自頭尋找第一個為0的位，改為的位，改為1，返回頁號，返回頁號去配：去配：頁號對應(yīng)的位頁號對應(yīng)的位(bit)置為置為0。用一個用一個bit代表一頁狀態(tài)，代表一頁狀態(tài)，0空閑，空閑，1占用。占用。32空閑頁面表空閑頁面表首頁號首頁號空頁數(shù)空頁數(shù).1204特點：可以分配連續(xù)頁面。特點：可以分配連續(xù)頁面。占用占用占用占用120頁頁121頁頁122頁頁123頁頁 . .33空閑頁面鏈空閑頁面鏈占用占用占用占用占用占用Head:將所有的空閑頁面連成一個鏈將所有的空閑頁

23、面連成一個鏈分配時取鏈頭的頁面分配時取鏈頭的頁面去配時將被釋放的頁面連入鏈去配時將被釋放的頁面連入鏈頭頭. 該方法適用內(nèi)存頁面的分配該方法適用內(nèi)存頁面的分配外存頁面的分配因分配和去配外存頁面的分配因分配和去配均需執(zhí)行一次均需執(zhí)行一次I/O傳輸傳輸, 速度較慢速度較慢 優(yōu)點：節(jié)省空間優(yōu)點：節(jié)省空間34動態(tài)異長分區(qū)的分配動態(tài)異長分區(qū)的分配l用于界地址存儲管理方式與段式存儲管理用于界地址存儲管理方式與段式存儲管理方式中方式中l(wèi)存儲空間被動態(tài)地劃分為若干個長度不等存儲空間被動態(tài)地劃分為若干個長度不等的區(qū)域的區(qū)域l系統(tǒng)使用空閑區(qū)域表系統(tǒng)使用空閑區(qū)域表, 表中記錄所有當(dāng)前表中記錄所有當(dāng)前未被進(jìn)程占用的空閑

24、區(qū)域未被進(jìn)程占用的空閑區(qū)域l沒有記錄于表中的區(qū)域是被進(jìn)程所占用的沒有記錄于表中的區(qū)域是被進(jìn)程所占用的非空閑區(qū)域。非空閑區(qū)域。 35動態(tài)異長分區(qū)的分配動態(tài)異長分區(qū)的分配空閑區(qū)首址空閑區(qū)首址空閑區(qū)長度空閑區(qū)長度.25001500數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：Criteria: 盡量使空閑區(qū)域連續(xù)。盡量使空閑區(qū)域連續(xù)。初始時一個連續(xù)空閑區(qū)。初始時一個連續(xù)空閑區(qū)。長度長度=0為表尾。為表尾。36最先適應(yīng)算法（最先適應(yīng)算法（First Fit）空閑區(qū)首址空閑區(qū)首址空閑區(qū)長度空閑區(qū)長度128641024256322560.空閑區(qū)：首址遞增排列；空閑區(qū)：首址遞增排列；申請：取第一個可滿足區(qū)域；申請：取第一個可滿足區(qū)域

25、；優(yōu)點：盡量使用低地址空間，優(yōu)點：盡量使用低地址空間，高區(qū)保持大空閑區(qū)域。高區(qū)保持大空閑區(qū)域。缺點：可能分割大空閑區(qū)。缺點：可能分割大空閑區(qū)。Eg. 申請申請32將分割第一個區(qū)將分割第一個區(qū)域。域。37最佳適應(yīng)算法（最佳適應(yīng)算法（Best Fit）空閑區(qū)：空閑區(qū)：空閑長度空閑長度遞增排列；遞增排列；申請：取最小可滿足區(qū)域；申請：取最小可滿足區(qū)域；優(yōu)點：盡量使用小空閑區(qū)，優(yōu)點：盡量使用小空閑區(qū)， 保持大空閑區(qū)。保持大空閑區(qū)。缺點：可能形成碎片缺點：可能形成碎片 (fragment)。 Eg. 申請申請30將留下長將留下長 度為度為2的空閑區(qū)。的空閑區(qū)。 空閑區(qū)首址空閑區(qū)首址空閑區(qū)長度空閑區(qū)長度2

26、56321024256641280.38最壞適應(yīng)算法（最壞適應(yīng)算法（Worst Fit）空閑區(qū)：空閑區(qū)：空閑長度遞減排列空閑長度遞減排列；申請：取最大可滿足區(qū)域；申請：取最大可滿足區(qū)域；優(yōu)點：防止形成碎片。優(yōu)點：防止形成碎片。缺點：分割大空閑區(qū)域。缺點：分割大空閑區(qū)域。當(dāng)當(dāng)遇到較長存儲空間的申請時遇到較長存儲空間的申請時, 無法滿足的可能性較大無法滿足的可能性較大 空閑區(qū)首址空閑區(qū)首址空閑區(qū)長度空閑區(qū)長度102425625632641280.396.2.3 碎片處理碎片處理l動態(tài)異長分區(qū)存儲分配可能形成很小的空動態(tài)異長分區(qū)存儲分配可能形成很小的空閑區(qū)域，稱為碎片閑區(qū)域，稱為碎片(fragmen

27、t)。如果碎片。如果碎片很多，將造成嚴(yán)重的存儲資源浪費。很多，將造成嚴(yán)重的存儲資源浪費。l緊湊：移動占用區(qū)域，使所有空閑區(qū)域連緊湊：移動占用區(qū)域，使所有空閑區(qū)域連成一片（開銷很大）成一片（開銷很大）406.2.3 碎片處理碎片處理 OS P1(248k) P2(250k) 8k 6k 4k256k:512k:768k:264k:518k: P1 OS P2256k:504k:754k:18k41UNIX存儲分配存儲分配-FFstruct map char *m_size; char *m_addr;struct map coremapCMAPSIZ;struct map swapmapSMAP

28、SIZ;define CMAPSIZ 100define SMAPSIZ 10042malloc(mp,size)struct map, *mp; register int a; register struct map *bp; for(bp = mp; bp-m_size; bp+) if (bp-m_size = size) a=bp-m_addr; bp-m_addr =+ size; if (bp-m_size =- size) = 0) do bp+; (bp-1)-m_addr = bp-m_addr; while(bp-1)-m_size = bp-m_size); return

29、(a); return(0);43mfree(mp,size,aa)struct map *map; register struct map bp; register int t,a; a = aa; for(bp=mp; bp-m_addrm_size !=0; bp+); if(bpmp & (bp-1)-m_addr+(bp-1)-m_size = a) /與前合并與前合并 (bp-1)-m_size =+ size; if (a+size = bp-m_addr) /前后合并前后合并 (bp-1)-m_size =+ bp-m_size; while (bp-m_size) b

30、p+; (bp-1)-m_addr = bp-m_addr; (bp-1)-m_size = bp-m_size; 44 else if (a+size = bp-m_addr & bp-m_size) /與后合并與后合并 bp-m_addr =- size; bp-m_size =+ size; else if (size) do /無合并無合并 t = bp-m_addr; bp-m_addr = a; a = t; t = bp-m_size; bp-m_size = size; bp+; while (size = t); 456.3 存儲管理方式存儲管理方式l存儲管理方式有：

31、存儲管理方式有： l界地址管理方式（一維地址）界地址管理方式（一維地址）l頁式管理方式（一維地址）頁式管理方式（一維地址）l段式管理方式（二維地址）段式管理方式（二維地址）l段頁式管理方式（二維地址）段頁式管理方式（二維地址）l6.3.1 單一連續(xù)區(qū)存儲管理單一連續(xù)區(qū)存儲管理l6.3.2 分頁式存儲管理分頁式存儲管理(paging)l6.3.3 分段式存儲管理分段式存儲管理(segmentation)l6.3.4 段頁式存儲管理段頁式存儲管理(segmentation with paging)466.3.1 單一連續(xù)區(qū)存儲管理單一連續(xù)區(qū)存儲管理l單一連續(xù)區(qū)單一連續(xù)區(qū)(single contig

32、uous region)也稱也稱單對界存儲管理方式單對界存儲管理方式l一個進(jìn)程在內(nèi)存空間的地址由兩個參數(shù)確一個進(jìn)程在內(nèi)存空間的地址由兩個參數(shù)確定：進(jìn)程的起始地址和長度，稱作一個對定：進(jìn)程的起始地址和長度，稱作一個對界界l6.3.1.1 基本原理基本原理 l6.3.1.2 雙對界雙對界l6.3.1.3 交換與重定位交換與重定位 l6.3.1.4 覆蓋技術(shù)覆蓋技術(shù)476.3.1.1 基本原理基本原理 l內(nèi)存空間劃分：內(nèi)存空間劃分：l采用動態(tài)異長分區(qū)方法采用動態(tài)異長分區(qū)方法, 整個內(nèi)存被動態(tài)地劃整個內(nèi)存被動態(tài)地劃分為若干個長度不同的區(qū)域分為若干個長度不同的區(qū)域.l進(jìn)程空間劃分：進(jìn)程空間劃分：l一個進(jìn)

33、程空間由一個連續(xù)的區(qū)域構(gòu)成一個進(jìn)程空間由一個連續(xù)的區(qū)域構(gòu)成. 設(shè)進(jìn)程設(shè)進(jìn)程長度為長度為L, 則邏輯地址為則邏輯地址為: 0L-1l進(jìn)程空間與內(nèi)存空間的對應(yīng)關(guān)系進(jìn)程空間與內(nèi)存空間的對應(yīng)關(guān)系l一個進(jìn)程在內(nèi)存中占有一個連續(xù)的區(qū)域一個進(jìn)程在內(nèi)存中占有一個連續(xù)的區(qū)域l設(shè)進(jìn)程的長度為設(shè)進(jìn)程的長度為L,在內(nèi)存中的起始地址為在內(nèi)存中的起始地址為b, 則其則其物理地址為物理地址為: bb+L-1486.3.1.1 基本原理基本原理 .0:l-1:.b:lb+l-1:進(jìn)程空間進(jìn)程空間內(nèi)存空間內(nèi)存空間l所需表目：所需表目：l內(nèi)存分配表內(nèi)存分配表: 記錄內(nèi)存中所有已被分配的區(qū)域。有時記錄內(nèi)存中所有已被分配的區(qū)域。有時

34、該表可以省略該表可以省略, 此時各分配區(qū)域分別登記在占有進(jìn)程此時各分配區(qū)域分別登記在占有進(jìn)程的的PCB中中l(wèi)空閑區(qū)域表空閑區(qū)域表: 用于記錄內(nèi)存中所有尚未分配的區(qū)域用于記錄內(nèi)存中所有尚未分配的區(qū)域496.3.1.1 基本原理基本原理l所需寄存器：所需寄存器：l基址寄存器基址寄存器: 整個系統(tǒng)一個整個系統(tǒng)一個, 用于保存正在運用于保存正在運行進(jìn)程的起始地址行進(jìn)程的起始地址l限長寄存器限長寄存器: 整個系統(tǒng)一個整個系統(tǒng)一個, 用于保存正在運用于保存正在運行進(jìn)程的長度行進(jìn)程的長度 當(dāng)進(jìn)程被調(diào)度將運行時當(dāng)進(jìn)程被調(diào)度將運行時, 系統(tǒng)將其起系統(tǒng)將其起始地址和長度由內(nèi)存分配表中或進(jìn)程始地址和長度由內(nèi)存分配表

35、中或進(jìn)程PCB 中分別取出并送入首址寄存器和限長寄存中分別取出并送入首址寄存器和限長寄存器中器中506.3.1.1 基本原理基本原理l地址映射：需將程序所產(chǎn)生的邏輯地址變地址映射：需將程序所產(chǎn)生的邏輯地址變換為內(nèi)存中的物理地址，即完成如下映射：換為內(nèi)存中的物理地址，即完成如下映射： s：（：（a）（b+a） la為邏輯地址為邏輯地址lb為進(jìn)程起始地址為進(jìn)程起始地址l當(dāng)當(dāng)a所對應(yīng)的物理地址不存在時所對應(yīng)的物理地址不存在時(越界越界)，映射，映射沒有意義，結(jié)果為沒有意義，結(jié)果為Wl地址映射的關(guān)系如圖地址映射的關(guān)系如圖 65 所示所示51地址映射的關(guān)系地址映射的關(guān)系0:l-1:.b:lb+l-1:l

36、b邏輯地址邏輯地址CP+aa+b步驟：步驟：(1) 由程序確定邏輯地址由程序確定邏輯地址a； (2) a與與l比較判斷是否越界，比較判斷是否越界， 不滿足：不滿足：0 a l-1，越界；，越界； (3) a與與b相加得到物理地址。相加得到物理地址。進(jìn)程空間進(jìn)程空間內(nèi)存空間內(nèi)存空間526.3.1.2 雙對界雙對界l雙對界允許一個進(jìn)程在內(nèi)存中占有兩個連雙對界允許一個進(jìn)程在內(nèi)存中占有兩個連續(xù)的區(qū)域續(xù)的區(qū)域l這兩個區(qū)域一個用于保存代碼這兩個區(qū)域一個用于保存代碼, 一個用于一個用于保存數(shù)據(jù)保存數(shù)據(jù)l代碼區(qū)域可被多個進(jìn)程所共享代碼區(qū)域可被多個進(jìn)程所共享l數(shù)據(jù)區(qū)域則為進(jìn)程所獨享數(shù)據(jù)區(qū)域則為進(jìn)程所獨享536.3.1.3 交換與重定位交換與重定位l主要針對程序多、空間小、裝不下的問題主要針對程序多、空間小、裝不下的問題而提出的。而提出的。l交換交換(swapping)也稱換入換出也稱換入換出(swap-in swap-out)或滾入滾出或滾入滾出(roll-in, roll-out)l指進(jìn)程在內(nèi)存與外存空間之間的動態(tài)調(diào)度，指進(jìn)程在內(nèi)存與外存空間之間的動態(tài)調(diào)度，它是緩解內(nèi)存空間緊張矛盾的一種有效方法。它是緩解內(nèi)存空間緊張矛盾的一種有效方法。546