第三章存儲器管理

1、第三章存儲器管理第三章 存儲器管理 3.13.1 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu)3.1.1 存儲器的層次結(jié)構(gòu)1. 1. 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) 在現(xiàn)代計算機(jī)系統(tǒng)中，存儲器是信息外理的來源與歸宿，占據(jù)重要位置。但是，在現(xiàn)有技術(shù)條件下，任何一種存儲裝置，都無法同時從速度與容量兩方面，滿足用戶的需求。實(shí)際上它們組成了一個速度由快到慢，容量由小到大的存儲裝置層次。 存儲器的層次結(jié)構(gòu) 2.各種存儲器 高速緩存Cache： 少量的、非?？焖?、昂貴、易變的 內(nèi)存RAM： 若干兆字節(jié)、中等速度、中等價格、易變的 磁盤： 數(shù)百兆或數(shù)千兆字節(jié)、低速、價廉、不易變的 由操作系統(tǒng)協(xié)調(diào)這些存儲器的使用 3.

2、1.2 存儲管理的目的1)主存的分配和管理：當(dāng)用戶需要內(nèi)存時,系統(tǒng)為之分配相應(yīng)的存儲空間；不需要時，及時回收，以供其它用戶使用。2)提高主存儲器的利用率：不僅能使多道程序動態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個區(qū)域的信息。存儲管理的目的（續(xù)）3)“擴(kuò)充”主存容量：為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺他的作業(yè)是在這樣一個大的存儲器中運(yùn)行。4)存儲保護(hù)：確保多道程序都在各自分配到存儲區(qū)域內(nèi)操作，互不干擾，防止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。 3.1.3. 基本概念1.1.定位（存儲分配）定位（存儲分配）：為具體的程序和數(shù)據(jù)等分配存儲單元或存儲區(qū)工作。2.2.

3、映射：映射：把邏輯地址轉(zhuǎn)換為相應(yīng)的物理地址的過程。3.3.隔離：隔離：按存取權(quán)限把合法區(qū)與非法區(qū)分隔，實(shí)現(xiàn)存儲保護(hù)。 4.名空間 程序員在程序中定義的標(biāo)識符 程序符號集合 由程序員自定義 沒有地址的概念符號指令數(shù)據(jù)說明I/O說明 地址空間及存儲空間5.5.地址空間地址空間 程序用來訪問信息所用地址單元的集合 邏輯（相對）地址的集合 由編譯程序生成6.存儲空間 主存中物理單元的集合 物理（絕對）地址的集合 由裝配程序等生成地址映射地址映射Load A 200 3456 。 。1200物理地址空間物理地址空間Load A data1data1 3456源程序源程序Load A 200 345601

4、00200編譯編譯連接連接邏輯地址空間邏輯地址空間BA=1000圖41名空間、地址空間、存儲空間7.邏輯地址與物理地址 邏輯地址（相對地址，虛地址）： 用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地址的形式，其首地址為0，其余指令中的地址都相對于首地址而編址。 不能用邏輯地址在內(nèi)存中讀取信息 物理地址（絕對地址，實(shí)地址）內(nèi)存中存儲單元的地址，可直接尋址 8.存儲共享 內(nèi)存共享：兩個或多個進(jìn)程共用內(nèi)存中相同區(qū)域 目的：節(jié)省內(nèi)存空間，提高內(nèi)存利用率 實(shí)現(xiàn)進(jìn)程通信（數(shù)據(jù)共享） 共享內(nèi)容： 代碼共享，要求代碼為純代碼 數(shù)據(jù)共享 9.存儲保護(hù)與安全保護(hù)目的： 為多個程序共享內(nèi)存提供保障,

5、使在內(nèi)存中的各道程序, 只能訪問它自己的區(qū)域，避免各道程序間相互干攏，特別是當(dāng)一道程序發(fā)生錯誤時, 不致于影響其他程序的運(yùn)行。通常由硬件完成保護(hù)功能，由軟件輔助實(shí)現(xiàn)。（特權(quán)指令不能完成存儲保護(hù)。）1) 存儲保護(hù) 保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯 （有意或無意的） 不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù) （系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）2) 保護(hù)過程-防止地址越界 每個進(jìn)程都有自己獨(dú)立的進(jìn)程空間，如果一個進(jìn)程在運(yùn)行時所產(chǎn)生的地址在其地址空間之外，則發(fā)生地址越界。即當(dāng)程序要訪問某個內(nèi)存單元時，由硬件檢查是否允許，如果允許則執(zhí)行，否則產(chǎn)生地址越界中斷，由操作系統(tǒng)進(jìn)行相應(yīng)處理。10.內(nèi)存“擴(kuò)充

6、”通過虛擬存儲技術(shù)實(shí)現(xiàn) 用戶在編制程序時，不應(yīng)該受內(nèi)存容量限制，所以要采用一定技術(shù)來“擴(kuò)充”內(nèi)存的容量，使用戶得到比實(shí)際內(nèi)存容量大的多的內(nèi)存空間 具體實(shí)現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來統(tǒng)一使用。通過這種方法把內(nèi)存擴(kuò)充，使用戶在編制程序時不受內(nèi)存限制第三章 存儲器管理 3.2 程序的裝入和鏈接3.2 程序的裝入和鏈接圖 4-2-1 對用戶程序的處理步驟3.2.1 程序的裝入1. 絕對裝入方式絕對裝入方式程序中所使用的絕對地址，可在編譯或匯編時給出，也可由程序員直接賦予。但在由程序員直接給出絕對地址時，不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程

7、序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉(zhuǎn)換為絕對地址。 2. 可重定位裝入方式圖 4-2-2 作業(yè)裝入內(nèi)存時的情況3. 動態(tài)運(yùn)行時裝入方式動態(tài)運(yùn)行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。因此，裝入內(nèi)存后的所有地址都仍是相對地址。 3.2.2 程序的鏈接圖 4-2-3 程序鏈接示意圖1.靜態(tài)鏈接方式2. 裝入時動態(tài)鏈接裝入時動態(tài)鏈接方式有以下優(yōu)點(diǎn)：(1)便于修改和更新。(2)便于實(shí)現(xiàn)對目標(biāo)模塊的共享。3. 運(yùn)行時動態(tài)鏈接這種鏈接方式是將對某些模塊的鏈接推

8、遲到執(zhí)行時才執(zhí)行，即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。 3.2.3 重定位 把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過程。又稱地址映射。如下圖，作業(yè)i經(jīng)過重定位，把地址集合映射到以1000為始址的內(nèi)存中，作為作業(yè)i的存儲空間。1. 重定位的類型 1)1)靜態(tài)重定位靜態(tài)重定位: :當(dāng)用戶程序被裝入內(nèi)存時，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時由軟

9、件完成）作業(yè)i在執(zhí)行前一次變址，直到該作業(yè)完成退出內(nèi)存為止。2)2)動態(tài)重定位動態(tài)重定位2)動態(tài)重定位 在程序運(yùn)行過程中要訪問數(shù)據(jù)時再進(jìn)行地址變換。由地址變換機(jī)構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持。2.動態(tài)重定位的實(shí)現(xiàn)方式 重定位寄存器重定位寄存器：在執(zhí)行一條指令取操作數(shù)時，要將指令給出的有效地址(500)與重定位寄存器中的內(nèi)容（1000）相加，得訪問地址（1500），從而實(shí)現(xiàn)了地址動態(tài)修改。 映象方式映象方式：采用頁表來描述虛、實(shí)頁面的對應(yīng)關(guān)系 。第三章 存儲器管理 3.3 連續(xù)分配存儲管理 3.3.1 單用戶存儲管理 在單道環(huán)境下，不管是單用戶系統(tǒng)還是單道批處理系統(tǒng)，進(jìn)程（作業(yè)）

10、執(zhí)行時除了系統(tǒng)占用一部分主存外，剩下的主存區(qū)域全部歸它占用。主存可以劃分為三部分：系統(tǒng)區(qū)、用戶區(qū)、空閑區(qū)。用戶占用區(qū)是一個連續(xù)的存儲區(qū)所以又稱單一連續(xù)區(qū)存儲管理。 單用戶系統(tǒng)在一段時間內(nèi)，只有一個進(jìn)程在內(nèi)存，故內(nèi)存分配管理十分簡單，內(nèi)存利用率低。內(nèi)存分為兩個區(qū)域，一個供操作系統(tǒng)使用，一個供用戶使用用戶程序用戶程序位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)0 xFFF.0位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序0ROM中的中的設(shè)備驅(qū)動程序設(shè)備驅(qū)動程序用戶程序用戶程序位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)0圖圖 4-3-1 4-3-1 單一連續(xù)區(qū)存儲分配示意圖單一連續(xù)區(qū)存儲分配示意圖工作

11、流程 單一連續(xù)區(qū)分配采用靜態(tài)分配和靜態(tài)重定位方式，亦即作業(yè)或進(jìn)程一旦進(jìn)入主存，就一直等到它運(yùn)行結(jié)束后才能釋放主存。如下圖所示的主存分配與回收法。并且由裝入程序檢查其絕對地址是否超越，即可達(dá)到保護(hù)系統(tǒng)的目的。工作流程(續(xù))單用戶系統(tǒng)缺點(diǎn) 不支持多道。 主存利用率不高。 程序的運(yùn)行受主存容量限制。存儲保護(hù) 自動地址修改例如，存儲器的地址空間為，而操作系統(tǒng)位于低址端的內(nèi)。對于這樣的系統(tǒng)，我們給用戶一個位的地址空間，并對其每個存儲器訪問自動加上。如果操作系統(tǒng)占用高址端的，則我們?nèi)∶恳粋€存儲訪問，而實(shí)際上，其地址為（）。從而實(shí)現(xiàn)了對操作系統(tǒng)的保護(hù)。存儲保護(hù)（續(xù)） 頁、頁尋址通過對每個用戶生成的地址左端拼

12、接上一位來實(shí)現(xiàn)區(qū)與用戶區(qū)。把操作系統(tǒng)確定在頁，而把用戶作業(yè)放在頁。 界限寄存器通過增加界限寄存器，劃分區(qū)與用戶區(qū)。 3.3.2 固定分區(qū)分配 分區(qū)式管理是滿足多道程序的最簡單的存儲管理方案。它的基本思想是將內(nèi)存劃分成若干個連續(xù)區(qū)域，稱為分區(qū)。每個分區(qū)只能存儲一個程序，而且程序也只能在它所駐留的分區(qū)中運(yùn)行。 預(yù)先把可分配的主存儲器空間分割成若干個連續(xù)區(qū)域，稱為一個分區(qū)。每個分區(qū)的大小可以相同也可以不同，如圖所示。但分區(qū)大小固定不變，每個分區(qū)裝一個且只能裝一個作業(yè) 存儲分配：如果有一個空閑區(qū), 則分配給進(jìn)程 1. 固定分區(qū)分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)多個等待隊列多個等待

13、隊列單個等待隊列單個等待隊列分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)圖 4-3-2 固定分區(qū)示意圖 2.內(nèi)存分配管理圖 4-3-3 固定分區(qū)使用表通過設(shè)置內(nèi)存分配表，內(nèi)存分配簡單缺點(diǎn)：內(nèi)存利用率不高 3.3.2 可變分區(qū)分配 基本思想：內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)程；否則令其等待主存空間 內(nèi)存管理：設(shè)置內(nèi)存空閑塊表記錄了空閑區(qū)起始地址和長度 內(nèi)存分配：動態(tài)分配 內(nèi)存回收：當(dāng)某一塊歸還后，前后空間合并，修改內(nèi)存空閑塊表1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)(1) 分區(qū)分配表（見圖4-3-5

14、）(2)空閑分區(qū)鏈圖4-3-4空閑鏈結(jié)構(gòu)0K15K38K48K68K80K110K120K空閑區(qū)表空閑區(qū)表已分配區(qū)表已分配區(qū)表始址長度標(biāo)志15K23K未分配48K20K未分配80K30K未分配空空始址長度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分區(qū)分配表分區(qū)分配表：圖4-3-5分區(qū)分配表分區(qū)分配表0K15K38K48K68K80K110K120K空閑區(qū)表空閑區(qū)表已分配區(qū)表已分配區(qū)表始址長度標(biāo)志15K23K未分配48K20K未分配98K12K未分配空空始址長度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K9

15、8K 2. 分區(qū)分配操作 1) 分配內(nèi)存分配內(nèi)存圖4-3-6內(nèi)存分配流程 2) 回收內(nèi)存圖 4-3-7 內(nèi)存回收時的情況 3.空閑分區(qū)鏈表 為了實(shí)現(xiàn)動態(tài)分配，系統(tǒng)設(shè)立空閑分區(qū)鏈表：每個空閑塊的前后兩個單元，放置必要的說明信息和指針。系統(tǒng)只要設(shè)立一個鏈?zhǔn)字羔?，指向第一個空閑塊即可。分配程序可以依照自由塊鏈表，來查找適合的空閑塊進(jìn)行分配。（如下圖） 4.分配算法 按空閑塊鏈接的方式不同，可以有以下四種算法： 最佳適應(yīng)法 最壞適應(yīng)法 首次適應(yīng)法 下次適應(yīng)法（循環(huán)首次適應(yīng)法）1)最佳適應(yīng)算法 接到內(nèi)存申請時，在空閑塊表中找到一個不小于請求的最小空塊進(jìn)行分配 為作業(yè)選擇分區(qū)時總是尋找其大小最接近于作業(yè)所

16、要求的存儲區(qū)域。 特點(diǎn)：用最小空間滿足要求2)最壞適應(yīng)算法 接到內(nèi)存申請時，在空閑塊表中找到一個不小于請求的最大空塊進(jìn)行分配，與最佳適應(yīng)法相反，它在作業(yè)選擇存儲塊時，總是尋找最大的空白區(qū)。 特點(diǎn)：當(dāng)分割后空閑塊仍為較大空塊分配算法（續(xù)）3)首次適應(yīng)法： 為作業(yè)選擇分區(qū)時總是按地址從高到低搜索，只要找到可以容納該作業(yè)的空白塊，就把該空白塊分配給該作業(yè)。4)下次適應(yīng)法 類似首次適應(yīng)法每次分區(qū)時，總是從上次查找結(jié)束的地方開始，找到一個足夠大的空白區(qū)分配。5.碎片問題 經(jīng)過一段時間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片

17、 造成存儲資源的浪費(fèi)碎片問題的解決碎片問題的解決 緊湊技術(shù)：通過在內(nèi)存移動程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域 （緊縮技術(shù)，緊致技術(shù)，浮動技術(shù)，搬家技術(shù)） 問題：開銷大；移動時機(jī)優(yōu)點(diǎn)： 便于動態(tài)申請內(nèi)存 便于共享內(nèi)存 便于動態(tài)鏈接缺點(diǎn)：碎片問題(外碎片)，內(nèi)存利用率不高，受實(shí)際內(nèi)存容量限制6.分區(qū)式存儲管理的優(yōu)缺點(diǎn) 3.3.3 可重定位分區(qū)分配1. 動態(tài)重定位的引入動態(tài)重定位的引入圖 4-3-1 緊湊的示意2. 動態(tài)重定位的實(shí)現(xiàn)圖 4-3-2 動態(tài)重定位示意圖3. 動態(tài)重定位分區(qū)分配算法圖 4-3-3 動態(tài)分區(qū)分配算法流程圖 4.可重定位分區(qū)的優(yōu)缺點(diǎn) 優(yōu)點(diǎn):解決了可變分區(qū)分配所引入的“外零頭”問題。消除內(nèi)存碎片，提高內(nèi)存利用率。 缺點(diǎn):提高硬件成本，緊湊時花費(fèi)時間。 5.多重分區(qū) 以上討論都是基于一個作業(yè)在主存中占據(jù)的是一個連續(xù)分區(qū)的假定。為了支持結(jié)構(gòu)化程序設(shè)計，操作系統(tǒng)往往把一道作業(yè)分成若干片段如子程序、主程序、數(shù)據(jù)組等）。這樣，片段之間就不需要連續(xù)了。只要增加一些重定位寄存器，就可以有效地控制一道作業(yè)片段之間的調(diào)用。 如下圖所示，作業(yè)、分別被分成兩個片段放進(jìn)互不相連的存儲區(qū)域中。由兩個變址寄存器實(shí)現(xiàn)控制。多重分區(qū)分配 6.分區(qū)的保護(hù) 為了防止一首作業(yè)有