操作系統(tǒng)課件r4-1)

1、第四章存儲(chǔ)器管理(1)第四章 存儲(chǔ)器管理4.1 4.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)4.2 4.2 程序的裝入和鏈接程序的裝入和鏈接 4.3 4.3 連續(xù)分配方式連續(xù)分配方式 第四章 存儲(chǔ)器管理 4.14.1 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu)4.1.1 存儲(chǔ)器的層次結(jié)構(gòu)1. 1. 存儲(chǔ)器的層次結(jié)構(gòu)存儲(chǔ)器的層次結(jié)構(gòu) 在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，存儲(chǔ)器是信息外理的來(lái)源與歸宿，占據(jù)重要位置。但是，在現(xiàn)有技術(shù)條件下，任何一種存儲(chǔ)裝置，都無(wú)法同時(shí)從速度與容量?jī)煞矫?，滿足用戶的需求。實(shí)際上它們組成了一個(gè)速度由快到慢，容量由小到大的存儲(chǔ)裝置層次。 存儲(chǔ)器的層次結(jié)構(gòu) 2.各種存儲(chǔ)器 高速緩存Cache： 少量的、

2、非?？焖?、昂貴、易變的 內(nèi)存RAM： 若干兆字節(jié)、中等速度、中等價(jià)格、易變的 磁盤： 數(shù)百兆或數(shù)千兆字節(jié)、低速、價(jià)廉、不易變的 由操作系統(tǒng)協(xié)調(diào)這些存儲(chǔ)器的使用 4.1.2 存儲(chǔ)管理的目的1)主存的分配和管理：當(dāng)用戶需要內(nèi)存時(shí),系統(tǒng)為之分配相應(yīng)的存儲(chǔ)空間；不需要時(shí)，及時(shí)回收，以供其它用戶使用。2)提高主存儲(chǔ)器的利用率：不僅能使多道程序動(dòng)態(tài)地共享主存，提高主存利用率，最好還能共享主存中某個(gè)區(qū)域的信息。存儲(chǔ)管理的目的（續(xù)）3)“擴(kuò)充”主存容量：為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺(jué)他的作業(yè)是在這樣一個(gè)大的存儲(chǔ)器中運(yùn)行。4)存儲(chǔ)保護(hù)：確保多道程序都在各自分配到存儲(chǔ)區(qū)域內(nèi)操作，互不干擾

3、，防止一道程序破壞其它作業(yè)或系統(tǒng)文件的信息。 4.1.3. 基本概念1.1.定位（存儲(chǔ)分配）定位（存儲(chǔ)分配）：為具體的程序和數(shù)據(jù)等分配存儲(chǔ)單元或存儲(chǔ)區(qū)工作。2.2.映射：映射：把邏輯地址轉(zhuǎn)換為相應(yīng)的物理地址的過(guò)程。3.3.隔離：隔離：按存取權(quán)限把合法區(qū)與非法區(qū)分隔，實(shí)現(xiàn)存儲(chǔ)保護(hù)。 4.名空間 程序員在程序中定義的標(biāo)識(shí)符 程序符號(hào)集合 由程序員自定義 沒(méi)有地址的概念符號(hào)指令數(shù)據(jù)說(shuō)明I/O說(shuō)明 地址空間及存儲(chǔ)空間5.5.地址空間地址空間 程序用來(lái)訪問(wèn)信息所用地址單元的集合 邏輯（相對(duì)）地址的集合 由編譯程序生成6.存儲(chǔ)空間 主存中物理單元的集合 物理（絕對(duì)）地址的集合 由裝配程序等生成地址映射地址

4、映射Load A 200 3456 。 。1200物理地址空間物理地址空間Load A data1data1 3456源程序源程序Load A 200 34560100200編譯編譯連接連接邏輯地址空間邏輯地址空間BA=1000圖41名空間、地址空間、存儲(chǔ)空間7.邏輯地址與物理地址 邏輯地址（相對(duì)地址，虛地址）： 用戶的程序經(jīng)過(guò)匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對(duì)地址的形式，其首地址為0，其余指令中的地址都相對(duì)于首地址而編址。 不能用邏輯地址在內(nèi)存中讀取信息 物理地址（絕對(duì)地址，實(shí)地址）內(nèi)存中存儲(chǔ)單元的地址，可直接尋址 8.存儲(chǔ)共享 內(nèi)存共享：兩個(gè)或多個(gè)進(jìn)程共用內(nèi)存中相同區(qū)域 目的：

5、節(jié)省內(nèi)存空間，提高內(nèi)存利用率 實(shí)現(xiàn)進(jìn)程通信（數(shù)據(jù)共享） 共享內(nèi)容： 代碼共享，要求代碼為純代碼 數(shù)據(jù)共享 9.存儲(chǔ)保護(hù)與安全保護(hù)目的： 為多個(gè)程序共享內(nèi)存提供保障,使在內(nèi)存中的各道程序, 只能訪問(wèn)它自己的區(qū)域，避免各道程序間相互干攏，特別是當(dāng)一道程序發(fā)生錯(cuò)誤時(shí), 不致于影響其他程序的運(yùn)行。通常由硬件完成保護(hù)功能，由軟件輔助實(shí)現(xiàn)。（特權(quán)指令不能完成存儲(chǔ)保護(hù)。）1) 存儲(chǔ)保護(hù) 保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯 （有意或無(wú)意的） 不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù) （系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）2) 保護(hù)過(guò)程-防止地址越界 每個(gè)進(jìn)程都有自己獨(dú)立的進(jìn)程空間，如果一個(gè)進(jìn)程在運(yùn)行時(shí)所產(chǎn)生的地

6、址在其地址空間之外，則發(fā)生地址越界。即當(dāng)程序要訪問(wèn)某個(gè)內(nèi)存單元時(shí)，由硬件檢查是否允許，如果允許則執(zhí)行，否則產(chǎn)生地址越界中斷，由操作系統(tǒng)進(jìn)行相應(yīng)處理。10.內(nèi)存“擴(kuò)充”通過(guò)虛擬存儲(chǔ)技術(shù)實(shí)現(xiàn) 用戶在編制程序時(shí)，不應(yīng)該受內(nèi)存容量限制，所以要采用一定技術(shù)來(lái)“擴(kuò)充”內(nèi)存的容量，使用戶得到比實(shí)際內(nèi)存容量大的多的內(nèi)存空間 具體實(shí)現(xiàn)是在硬件支持下，軟硬件相互協(xié)作，將內(nèi)存和外存結(jié)合起來(lái)統(tǒng)一使用。通過(guò)這種方法把內(nèi)存擴(kuò)充，使用戶在編制程序時(shí)不受內(nèi)存限制第四章 存儲(chǔ)器管理 4.2 程序的裝入和鏈接4.2 程序的裝入和鏈接圖 4-2-1 對(duì)用戶程序的處理步驟4.2.1 程序的裝入1. 絕對(duì)裝入方式絕對(duì)裝入方式程序中所使

7、用的絕對(duì)地址，可在編譯或匯編時(shí)給出，也可由程序員直接賦予。但在由程序員直接給出絕對(duì)地址時(shí)，不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號(hào)地址，然后在編譯或匯編時(shí)，再將這些符號(hào)地址轉(zhuǎn)換為絕對(duì)地址。 2. 可重定位裝入方式圖 4-2-2 作業(yè)裝入內(nèi)存時(shí)的情況3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn)換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此，裝入內(nèi)存后的所有地址都仍是相對(duì)地址。 4.2.2 程序的鏈接圖 4-2-3 程序鏈接示意圖1.靜態(tài)鏈

8、接方式2. 裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)：(1)便于修改和更新。(2)便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接這種鏈接方式是將對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)才執(zhí)行，即，在執(zhí)行過(guò)程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過(guò)程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過(guò)程，而且可節(jié)省大量的內(nèi)存空間。 4.2.3 重定位 把作業(yè)地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過(guò)程。又稱地址映射。如下圖，作業(yè)i經(jīng)過(guò)重定位，把地址集合映射到以1000為始址的內(nèi)存中，作為作

9、業(yè)i的存儲(chǔ)空間。1. 重定位的類型 1)1)靜態(tài)重定位靜態(tài)重定位: :當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在裝入內(nèi)存時(shí)由軟件完成）作業(yè)i在執(zhí)行前一次變址，直到該作業(yè)完成退出內(nèi)存為止。2)2)動(dòng)態(tài)重定位動(dòng)態(tài)重定位2)動(dòng)態(tài)重定位 在程序運(yùn)行過(guò)程中要訪問(wèn)數(shù)據(jù)時(shí)再進(jìn)行地址變換。由地址變換機(jī)構(gòu)進(jìn)行的地址變換，硬件上需要重定位寄存器的支持。2.動(dòng)態(tài)重定位的實(shí)現(xiàn)方式 重定位寄存器重定位寄存器：在執(zhí)行一條指令取操作數(shù)時(shí)，要將指令給出的有效地址(500)與重定位寄存器中的內(nèi)容（1000）相加，得訪問(wèn)地址（1500），從而實(shí)現(xiàn)了地址動(dòng)態(tài)修改。 映象方式映象方式：采用頁(yè)表來(lái)

10、描述虛、實(shí)頁(yè)面的對(duì)應(yīng)關(guān)系 。第四章 存儲(chǔ)器管理 4.3 連續(xù)分配存儲(chǔ)管理 4.3.1 單用戶存儲(chǔ)管理 在單道環(huán)境下，不管是單用戶系統(tǒng)還是單道批處理系統(tǒng)，進(jìn)程（作業(yè)）執(zhí)行時(shí)除了系統(tǒng)占用一部分主存外，剩下的主存區(qū)域全部歸它占用。主存可以劃分為三部分：系統(tǒng)區(qū)、用戶區(qū)、空閑區(qū)。用戶占用區(qū)是一個(gè)連續(xù)的存儲(chǔ)區(qū)所以又稱單一連續(xù)區(qū)存儲(chǔ)管理。 單用戶系統(tǒng)在一段時(shí)間內(nèi)，只有一個(gè)進(jìn)程在內(nèi)存，故內(nèi)存分配管理十分簡(jiǎn)單，內(nèi)存利用率低。內(nèi)存分為兩個(gè)區(qū)域，一個(gè)供操作系統(tǒng)使用，一個(gè)供用戶使用用戶程序用戶程序位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)0 xFFF.0位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序0ROM中的中

11、的設(shè)備驅(qū)動(dòng)程序設(shè)備驅(qū)動(dòng)程序用戶程序用戶程序位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)0圖圖 4-3-1 4-3-1 單一連續(xù)區(qū)存儲(chǔ)分配示意圖單一連續(xù)區(qū)存儲(chǔ)分配示意圖工作流程 單一連續(xù)區(qū)分配采用靜態(tài)分配和靜態(tài)重定位方式，亦即作業(yè)或進(jìn)程一旦進(jìn)入主存，就一直等到它運(yùn)行結(jié)束后才能釋放主存。如下圖所示的主存分配與回收法。并且由裝入程序檢查其絕對(duì)地址是否超越，即可達(dá)到保護(hù)系統(tǒng)的目的。工作流程(續(xù))單用戶系統(tǒng)缺點(diǎn) 不支持多道。 主存利用率不高。 程序的運(yùn)行受主存容量限制。存儲(chǔ)保護(hù) 自動(dòng)地址修改例如，存儲(chǔ)器的地址空間為，而操作系統(tǒng)位于低址端的內(nèi)。對(duì)于這樣的系統(tǒng)，我們給用戶一個(gè)位的地址空間，并對(duì)其每個(gè)存儲(chǔ)器訪問(wèn)自動(dòng)

12、加上。如果操作系統(tǒng)占用高址端的，則我們?nèi)∶恳粋€(gè)存儲(chǔ)訪問(wèn)，而實(shí)際上，其地址為（）。從而實(shí)現(xiàn)了對(duì)操作系統(tǒng)的保護(hù)。存儲(chǔ)保護(hù)（續(xù)） 頁(yè)、頁(yè)尋址通過(guò)對(duì)每個(gè)用戶生成的地址左端拼接上一位來(lái)實(shí)現(xiàn)區(qū)與用戶區(qū)。把操作系統(tǒng)確定在頁(yè)，而把用戶作業(yè)放在頁(yè)。 界限寄存器通過(guò)增加界限寄存器，劃分區(qū)與用戶區(qū)。 4.3.2 固定分區(qū)分配 分區(qū)式管理是滿足多道程序的最簡(jiǎn)單的存儲(chǔ)管理方案。它的基本思想是將內(nèi)存劃分成若干個(gè)連續(xù)區(qū)域，稱為分區(qū)。每個(gè)分區(qū)只能存儲(chǔ)一個(gè)程序，而且程序也只能在它所駐留的分區(qū)中運(yùn)行。 預(yù)先把可分配的主存儲(chǔ)器空間分割成若干個(gè)連續(xù)區(qū)域，稱為一個(gè)分區(qū)。每個(gè)分區(qū)的大小可以相同也可以不同，如圖所示。但分區(qū)大小固定不變，每

13、個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè) 存儲(chǔ)分配：如果有一個(gè)空閑區(qū), 則分配給進(jìn)程 1. 固定分區(qū)分區(qū)分區(qū)4分區(qū)分區(qū)3分區(qū)分區(qū)2分區(qū)分區(qū)1操作系統(tǒng)操作系統(tǒng)多個(gè)等待隊(duì)列多個(gè)等待隊(duì)列單個(gè)等待隊(duì)列單個(gè)等待隊(duì)列分區(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ū)使用表通過(guò)設(shè)置內(nèi)存分配表，內(nèi)存分配簡(jiǎn)單缺點(diǎn)：內(nèi)存利用率不高 4.3.2 可變分區(qū)分配 基本思想：內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來(lái)決定是否分配。若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)程；否則令其等待主存空間 內(nèi)存管理：設(shè)置內(nèi)存空閑塊

14、表記錄了空閑區(qū)起始地址和長(zhǎng)度 內(nèi)存分配：動(dòng)態(tài)分配 內(nèi)存回收：當(dāng)某一塊歸還后，前后空間合并，修改內(nèi)存空閑塊表1.分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)(1) 分區(qū)分配表（見(jiàn)圖4-3-5）(2)空閑分區(qū)鏈圖4-3-4空閑鏈結(jié)構(gòu)0K15K38K48K68K80K110K120K空閑區(qū)表空閑區(qū)表已分配區(qū)表已分配區(qū)表始址長(zhǎng)度標(biāo)志15K23K未分配48K20K未分配80K30K未分配空空始址長(zhǎng)度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ4空空分區(qū)分配表分區(qū)分配表：圖4-3-5分區(qū)分配表分區(qū)分配表0K15K38K48K68K80K110K120K空閑區(qū)表空閑區(qū)表已分配區(qū)表已分配區(qū)表始址長(zhǎng)度標(biāo)志15K2

15、3K未分配48K20K未分配98K12K未分配空空始址長(zhǎng)度標(biāo)志0K15KJ138K10KJ268K12KJ3110K10KJ480K5KJ585K13KJ685K98K 2. 分區(qū)分配操作 1) 分配內(nèi)存分配內(nèi)存圖4-3-6內(nèi)存分配流程 2) 回收內(nèi)存圖 4-3-7 內(nèi)存回收時(shí)的情況 3.空閑分區(qū)鏈表 為了實(shí)現(xiàn)動(dòng)態(tài)分配，系統(tǒng)設(shè)立空閑分區(qū)鏈表：每個(gè)空閑塊的前后兩個(gè)單元，放置必要的說(shuō)明信息和指針。系統(tǒng)只要設(shè)立一個(gè)鏈?zhǔn)字羔?，指向第一個(gè)空閑塊即可。分配程序可以依照自由塊鏈表，來(lái)查找適合的空閑塊進(jìn)行分配。（如下圖） 4.分配算法 按空閑塊鏈接的方式不同，可以有以下四種算法： 最佳適應(yīng)法 最壞適應(yīng)法 首次

16、適應(yīng)法 下次適應(yīng)法（循環(huán)首次適應(yīng)法）1)最佳適應(yīng)算法 接到內(nèi)存申請(qǐng)時(shí)，在空閑塊表中找到一個(gè)不小于請(qǐng)求的最小空塊進(jìn)行分配 為作業(yè)選擇分區(qū)時(shí)總是尋找其大小最接近于作業(yè)所要求的存儲(chǔ)區(qū)域。 特點(diǎn)：用最小空間滿足要求2)最壞適應(yīng)算法 接到內(nèi)存申請(qǐng)時(shí)，在空閑塊表中找到一個(gè)不小于請(qǐng)求的最大空塊進(jìn)行分配，與最佳適應(yīng)法相反，它在作業(yè)選擇存儲(chǔ)塊時(shí)，總是尋找最大的空白區(qū)。 特點(diǎn)：當(dāng)分割后空閑塊仍為較大空塊分配算法（續(xù)）3)首次適應(yīng)法： 為作業(yè)選擇分區(qū)時(shí)總是按地址從低到高搜索，只要找到可以容納該作業(yè)的空白塊，就把該空白塊分配給該作業(yè)。4)下次適應(yīng)法 類似首次適應(yīng)法每次分區(qū)時(shí)，總是從上次查找結(jié)束的地方開(kāi)始，找到一個(gè)足夠

17、大的空白區(qū)分配。5.碎片問(wèn)題 經(jīng)過(guò)一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片 造成存儲(chǔ)資源的浪費(fèi)碎片問(wèn)題的解決碎片問(wèn)題的解決 緊湊技術(shù)：通過(guò)在內(nèi)存移動(dòng)程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域 （緊縮技術(shù)，緊致技術(shù)，浮動(dòng)技術(shù)，搬家技術(shù)） 問(wèn)題：開(kāi)銷大；移動(dòng)時(shí)機(jī)優(yōu)點(diǎn)： 便于動(dòng)態(tài)申請(qǐng)內(nèi)存 便于共享內(nèi)存 便于動(dòng)態(tài)鏈接缺點(diǎn)：碎片問(wèn)題(外碎片)，內(nèi)存利用率不高，受實(shí)際內(nèi)存容量限制6.分區(qū)式存儲(chǔ)管理的優(yōu)缺點(diǎn) 4.3.3 可重定位分區(qū)分配1. 動(dòng)態(tài)重定位的引入動(dòng)態(tài)重定位的引入圖 4-3-1 緊湊的示意2. 動(dòng)態(tài)重定位的實(shí)

18、現(xiàn)圖 4-3-2 動(dòng)態(tài)重定位示意圖3. 動(dòng)態(tài)重定位分區(qū)分配算法圖 4-3-3 動(dòng)態(tài)分區(qū)分配算法流程圖 4.可重定位分區(qū)的優(yōu)缺點(diǎn) 優(yōu)點(diǎn):解決了可變分區(qū)分配所引入的“外零頭”問(wèn)題。消除內(nèi)存碎片，提高內(nèi)存利用率。 缺點(diǎn):提高硬件成本，緊湊時(shí)花費(fèi)時(shí)間。 5.多重分區(qū) 以上討論都是基于一個(gè)作業(yè)在主存中占據(jù)的是一個(gè)連續(xù)分區(qū)的假定。為了支持結(jié)構(gòu)化程序設(shè)計(jì)，操作系統(tǒng)往往把一道作業(yè)分成若干片段如子程序、主程序、數(shù)據(jù)組等）。這樣，片段之間就不需要連續(xù)了。只要增加一些重定位寄存器，就可以有效地控制一道作業(yè)片段之間的調(diào)用。 如下圖所示，作業(yè)、分別被分成兩個(gè)片段放進(jìn)互不相連的存儲(chǔ)區(qū)域中。由兩個(gè)變址寄存器實(shí)現(xiàn)控制。多重分區(qū)分配 6.分區(qū)的保護(hù) 為了防止一首作業(yè)有意或無(wú)意