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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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