操作系統(tǒng)課件第4章

1、第四章存儲(chǔ)器管理4.1 存存 儲(chǔ)儲(chǔ) 器器 的的 層層 次次 結(jié)結(jié) 構(gòu)構(gòu)多級(jí)存儲(chǔ)器結(jié)構(gòu)多級(jí)存儲(chǔ)器結(jié)構(gòu)存儲(chǔ)層次：存儲(chǔ)層次：CPU寄存器寄存器，主存主存，輔存輔存。高檔計(jì)算機(jī)中：寄存器、高速緩存、主存儲(chǔ)器、磁盤緩存、固定高檔計(jì)算機(jī)中：寄存器、高速緩存、主存儲(chǔ)器、磁盤緩存、固定磁盤、可移動(dòng)存儲(chǔ)介質(zhì)。磁盤、可移動(dòng)存儲(chǔ)介質(zhì)。計(jì)算機(jī)系統(tǒng)存儲(chǔ)層次示意計(jì)算機(jī)系統(tǒng)存儲(chǔ)層次示意 在存儲(chǔ)層次中越往上，存儲(chǔ)在存儲(chǔ)層次中越往上，存儲(chǔ)介質(zhì)的訪問(wèn)速度越快，價(jià)格也介質(zhì)的訪問(wèn)速度越快，價(jià)格也越高，相對(duì)存儲(chǔ)容量也越小。越高，相對(duì)存儲(chǔ)容量也越小。CPU寄存器寄存器主存主存輔存輔存n3主存儲(chǔ)器主存儲(chǔ)器主存儲(chǔ)器主存儲(chǔ)器( (內(nèi)存內(nèi)存)

2、)保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)。保存進(jìn)程運(yùn)行時(shí)的程序和數(shù)據(jù)。 寄存器訪問(wèn)速度最快寄存器訪問(wèn)速度最快,協(xié)調(diào)協(xié)調(diào)CPU工作，價(jià)格昂貴，容量很小。工作，價(jià)格昂貴，容量很小。n1. 寄存器寄存器n2 2高速緩存高速緩存容量大于寄存器容量大于寄存器,小于主存。小于主存。 訪問(wèn)速度比主存快。將經(jīng)常訪訪問(wèn)速度比主存快。將經(jīng)常訪問(wèn)的信息存放在高速緩存中。問(wèn)的信息存放在高速緩存中。n4磁盤緩存磁盤緩存利用主存中的存儲(chǔ)空間，暫時(shí)存放從磁盤中讀出利用主存中的存儲(chǔ)空間，暫時(shí)存放從磁盤中讀出(或?qū)懭牖驅(qū)懭?的的信息。信息。臺(tái)式臺(tái)式PCPC機(jī)內(nèi)存插槽和內(nèi)存條機(jī)內(nèi)存插槽和內(nèi)存條4.2 程程 序序 的的 裝裝 入入 和和 鏈鏈

3、 接接 編譯，源代碼編譯，源代碼目標(biāo)模塊。目標(biāo)模塊。 鏈接，目標(biāo)模塊，庫(kù)函數(shù)鏈接，目標(biāo)模塊，庫(kù)函數(shù)裝入模塊。裝入模塊。 裝入，裝入模塊裝入，裝入模塊內(nèi)存。內(nèi)存。第一步第一步編譯程序編譯程序產(chǎn)生的目產(chǎn)生的目標(biāo)模塊標(biāo)模塊庫(kù)庫(kù)內(nèi)存內(nèi)存鏈接鏈接程序程序裝入裝入程序程序裝入模塊裝入模塊 第二步第二步第三步第三步 程序的裝入程序的裝入n1. 絕對(duì)裝入方式絕對(duì)裝入方式按照按照絕對(duì)地址絕對(duì)地址裝入。裝入。只適用于單道程序環(huán)境。只適用于單道程序環(huán)境。n2可重定位裝入方式可重定位裝入方式首址可以首址可以平移。平移。裝入時(shí)地裝入時(shí)地址修改。址修改。整體搬移整體搬移連續(xù)存放連續(xù)存放。n3動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝

4、入方式裝入內(nèi)存后的所有地址都是相對(duì)地址。地址修改推遲到程序執(zhí)裝入內(nèi)存后的所有地址都是相對(duì)地址。地址修改推遲到程序執(zhí)行時(shí)進(jìn)行行時(shí)進(jìn)行 ，動(dòng)態(tài)重定位。，動(dòng)態(tài)重定位。裝入裝入時(shí)地時(shí)地址不址不變，變，運(yùn)行運(yùn)行時(shí)地時(shí)地址修址修改。改。LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作 業(yè) 地 址 空 間內(nèi) 存 空 間程序的鏈接程序的鏈接 1. 靜態(tài)鏈接方式（在外存形成裝入模塊）靜態(tài)鏈接方式（在外存形成裝入模塊）模塊 ACALL B；Return；0L 1模塊 BCALL C；Return；0M 1模塊 CReturn；0N 10模

5、塊 AJSR“L”Return；L 1模塊 BJSR“L M”Return；LL M 1L ML M N 1模塊 CReturn；(a) 目標(biāo)模塊(b) 裝入模塊2. 裝入時(shí)動(dòng)態(tài)鏈接（進(jìn)內(nèi)存后形成裝入模塊）裝入時(shí)動(dòng)態(tài)鏈接（進(jìn)內(nèi)存后形成裝入模塊）裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)：裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)：便于修改和更新。便于修改和更新。 (1)(2) 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。 高檔操作高檔操作系統(tǒng)流行系統(tǒng)流行方式方式Windows Windows LinuxLinux等通等通用技術(shù)用技術(shù)OSOS下存有下存有大量的大量的DLLDLL動(dòng)態(tài)連接動(dòng)態(tài)連接庫(kù)文件。庫(kù)文件。3.

6、運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接執(zhí)行過(guò)程中，當(dāng)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，由執(zhí)行過(guò)程中，當(dāng)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，由OSOS找找到該模塊并將之裝入內(nèi)存，到該模塊并將之裝入內(nèi)存， 把它鏈接到調(diào)用者模塊上。把它鏈接到調(diào)用者模塊上。當(dāng)前不用的目標(biāo)模塊，都不會(huì)進(jìn)內(nèi)存。加快程序的裝入過(guò)當(dāng)前不用的目標(biāo)模塊，都不會(huì)進(jìn)內(nèi)存。加快程序的裝入過(guò)程，節(jié)省大量的內(nèi)存空間。程，節(jié)省大量的內(nèi)存空間。 高檔操作系統(tǒng)流行方式高檔操作系統(tǒng)流行方式Windows Windows 、LinuxLinux、SolarsSolars、MachMach等等OSOS通用的技術(shù)（使用通用的技術(shù)（使用DLLDLL文件）文件）4.3 連連

7、續(xù)續(xù) 分分 配配 方方 式式單一連續(xù)分配單一連續(xù)分配只能用于單用戶、單任務(wù)操作系統(tǒng)中。內(nèi)存分為系統(tǒng)區(qū)和用只能用于單用戶、單任務(wù)操作系統(tǒng)中。內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分。戶區(qū)兩部分。OSUSERAREA操作系統(tǒng)默認(rèn)存操作系統(tǒng)默認(rèn)存放在內(nèi)存低端放在內(nèi)存低端作業(yè)操作系統(tǒng)未用32 KB64 KB160 KB分配給用戶作業(yè)的空間每次一個(gè)作業(yè)，每次一個(gè)作業(yè)，上一個(gè)完成退上一個(gè)完成退出，下一個(gè)才出，下一個(gè)才能進(jìn)入能進(jìn)入利用率極低利用率極低固定分區(qū)分配固定分區(qū)分配用戶空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中裝入一用戶空間劃分為若干個(gè)固定大小的區(qū)域，在每個(gè)分區(qū)中裝入一道作業(yè)，允許幾道作業(yè)并發(fā)運(yùn)行。道作業(yè)，允

8、許幾道作業(yè)并發(fā)運(yùn)行。 簡(jiǎn)單、可靠，但產(chǎn)生分區(qū)簡(jiǎn)單、可靠，但產(chǎn)生分區(qū)“內(nèi)零頭內(nèi)零頭”，內(nèi)存利用效低。，內(nèi)存利用效低。系統(tǒng)區(qū)系統(tǒng)區(qū)分區(qū)分區(qū) 1 1分區(qū)分區(qū) 4 4分區(qū)分區(qū) 5 5分區(qū)分區(qū) 2 2分區(qū)分區(qū) 3 3區(qū)號(hào)/鍵大小起址狀態(tài)18 KB512K已分配232 KB520K已分配332 KB552K未分配4128 KB584K未分配5512 KB712K已分配系統(tǒng)區(qū)系統(tǒng)區(qū)作業(yè)作業(yè) 3 3分區(qū)分區(qū) 4 4作業(yè)作業(yè) 2 2作業(yè)作業(yè) 1 1分區(qū)分區(qū) 3 3動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。v 空閑分區(qū)表空閑分區(qū)表v 記錄每個(gè)空

9、閑分區(qū)的情況。記錄每個(gè)空閑分區(qū)的情況。 (2) 空閑分區(qū)鏈空閑分區(qū)鏈將所有的空閑分區(qū)鏈接成一個(gè)將所有的空閑分區(qū)鏈接成一個(gè)雙向鏈雙向鏈。前向指針0N個(gè)字節(jié)可用后向指針0N+2N+2當(dāng)分區(qū)被分配出去以后，把狀態(tài)當(dāng)分區(qū)被分配出去以后，把狀態(tài)位由位由“0”改為改為“1”，此時(shí)，前、，此時(shí)，前、后向指針已無(wú)意義。后向指針已無(wú)意義。OS區(qū)區(qū)Job1Job2Job3Job4Job5Job6OS區(qū)區(qū)Job1Job2Job3Job4Job5空閑分區(qū)鏈空閑分區(qū)鏈頭指針頭指針Job6分區(qū)分配算法分區(qū)分配算法1) 首次適應(yīng)算法首次適應(yīng)算法(first fit) 空閑分區(qū)鏈空閑分區(qū)鏈以地址遞增的次序以地址遞增的次序鏈接

10、。從鏈?zhǔn)组_始順序查找，直鏈接。從鏈?zhǔn)组_始順序查找，直至找到一個(gè)大小能滿足要求的空閑分區(qū)為止；然后再按照作業(yè)至找到一個(gè)大小能滿足要求的空閑分區(qū)為止；然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給作業(yè)，余下的空的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給作業(yè)，余下的空閑分區(qū)仍留在空閑鏈中。閑分區(qū)仍留在空閑鏈中。 該算法的優(yōu)缺點(diǎn)：該算法的優(yōu)缺點(diǎn)：為大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。為大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。低址部分不斷被劃分，會(huì)留下許多難以利用的、很小的空閑低址部分不斷被劃分，會(huì)留下許多難以利用的、很小的空閑分區(qū)。分區(qū)。新作業(yè)裝入內(nèi)存時(shí)，按照一定的分配算法，從空閑分區(qū)表或新作業(yè)裝入內(nèi)存

11、時(shí)，按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。常用的分配算法：空閑分區(qū)鏈中選出一分區(qū)分配給該作業(yè)。常用的分配算法： 2) 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法(next fit) 將所有的將所有的空閑分區(qū)構(gòu)成一個(gè)循環(huán)鏈表空閑分區(qū)構(gòu)成一個(gè)循環(huán)鏈表。采用循環(huán)查找。采用循環(huán)查找方式，設(shè)置一個(gè)起始查尋指針，用于指示下一次起始查方式，設(shè)置一個(gè)起始查尋指針，用于指示下一次起始查尋的空閑分區(qū)。尋的空閑分區(qū)。該算法的優(yōu)缺點(diǎn)：該算法的優(yōu)缺點(diǎn)：能使內(nèi)存中的空閑分區(qū)分布得更均能使內(nèi)存中的空閑分區(qū)分布得更均勻，從而減少了查找空閑分區(qū)時(shí)的開銷，但這樣會(huì)缺乏勻，從而減少了查找空閑分區(qū)時(shí)的開銷，但這

12、樣會(huì)缺乏大的空閑分區(qū)。大的空閑分區(qū)。為進(jìn)程分配內(nèi)存時(shí)，不再是每次都從鏈?zhǔn)组_始查找，而是從為進(jìn)程分配內(nèi)存時(shí)，不再是每次都從鏈?zhǔn)组_始查找，而是從上次找到空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直到找到上次找到空閑分區(qū)的下一個(gè)空閑分區(qū)開始查找，直到找到一個(gè)能滿足要求的空閑分區(qū)。一個(gè)能滿足要求的空閑分區(qū)。3) 最佳適應(yīng)算法最佳適應(yīng)算法( (best fit) )將所有的空閑分區(qū)將所有的空閑分區(qū)按容量以從小到大的順序形成空閑分區(qū)鏈按容量以從小到大的順序形成空閑分區(qū)鏈。該算法的優(yōu)缺點(diǎn)：該算法的優(yōu)缺點(diǎn)：為大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條為大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。每次分配后所切割下來(lái)的剩余部分總是最小的，這

13、樣，件。每次分配后所切割下來(lái)的剩余部分總是最小的，這樣，在存儲(chǔ)器中會(huì)留下許多難以利用的小空閑區(qū)。在存儲(chǔ)器中會(huì)留下許多難以利用的小空閑區(qū)。把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)。把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)。 4) 最壞適應(yīng)算法最壞適應(yīng)算法( (worst fit) ) 該算法要掃描整個(gè)空閑分區(qū)表或鏈表，總是挑選一個(gè)該算法要掃描整個(gè)空閑分區(qū)表或鏈表，總是挑選一個(gè)最最大的空閑區(qū)大的空閑區(qū)分割給作業(yè)使用，其優(yōu)點(diǎn)是可使剩下的空閑區(qū)不分割給作業(yè)使用，其優(yōu)點(diǎn)是可使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，但查找效率很高。至于太小，產(chǎn)生碎片的幾率最小，但查找效率很高。所有的空閑分區(qū)按容量

14、從大到小的順序形成空閑分區(qū)鏈，查所有的空閑分區(qū)按容量從大到小的順序形成空閑分區(qū)鏈，查找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。該算法的找時(shí)只要看第一個(gè)分區(qū)能否滿足作業(yè)要求。該算法的缺點(diǎn)缺點(diǎn)是是它會(huì)使存儲(chǔ)器中缺乏大的空閑分區(qū)。它會(huì)使存儲(chǔ)器中缺乏大的空閑分區(qū)。 最壞適應(yīng)算法與首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最最壞適應(yīng)算法與首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法一起，也稱為佳適應(yīng)算法一起，也稱為順序搜索法順序搜索法。 5) 快速適應(yīng)算法快速適應(yīng)算法( (quick fit) ) 該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大該算法又稱為分類搜索法，是將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類，對(duì)于每一類具

15、有相同容量的所有空閑分區(qū)，小進(jìn)行分類，對(duì)于每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，這樣，系統(tǒng)中存在多個(gè)單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表，這樣，系統(tǒng)中存在多個(gè)空閑空閑分區(qū)鏈表分區(qū)鏈表，同時(shí)在內(nèi)存中設(shè)立一張，同時(shí)在內(nèi)存中設(shè)立一張管理索引表管理索引表。 該算法的該算法的優(yōu)點(diǎn)優(yōu)點(diǎn)是查找效率高，僅需要根據(jù)進(jìn)程的長(zhǎng)度，是查找效率高，僅需要根據(jù)進(jìn)程的長(zhǎng)度，找到能容納它的最小空閑區(qū)鏈表即可；另外不會(huì)對(duì)任何分找到能容納它的最小空閑區(qū)鏈表即可；另外不會(huì)對(duì)任何分區(qū)產(chǎn)生分割，滿足對(duì)大空間的需求，不會(huì)產(chǎn)生內(nèi)存碎片。區(qū)產(chǎn)生分割，滿足對(duì)大空間的需求，不會(huì)產(chǎn)生內(nèi)存碎片。 缺點(diǎn)缺點(diǎn)是在分區(qū)歸還主存時(shí)算法復(fù)雜，系統(tǒng)開

16、銷較大。是在分區(qū)歸還主存時(shí)算法復(fù)雜，系統(tǒng)開銷較大?？芍囟ㄎ环謪^(qū)分配可重定位分區(qū)分配操作系統(tǒng)用戶程序1用戶程序310 KB30 KB用戶程序614 KB用戶程序926 KB操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序980 KB(a) 緊湊前(b) 緊湊后經(jīng)過(guò)緊湊后，用戶程序在經(jīng)過(guò)緊湊后，用戶程序在內(nèi)存中的位置發(fā)生了變化，內(nèi)存中的位置發(fā)生了變化，所以必須對(duì)移動(dòng)了的程序所以必須對(duì)移動(dòng)了的程序或數(shù)據(jù)進(jìn)行重定位?；驍?shù)據(jù)進(jìn)行重定位。緊湊技術(shù)緊湊技術(shù),也稱為也稱為“拼湊拼湊”技術(shù)，解決可變分區(qū)中產(chǎn)生的技術(shù)，解決可變分區(qū)中產(chǎn)生的“外零頭外零頭”。移動(dòng)某些已分。移動(dòng)某些已分配分區(qū)，使配分區(qū)，使“外零頭外零頭

17、”合并為一個(gè)大的連續(xù)空閑區(qū)。合并為一個(gè)大的連續(xù)空閑區(qū)。以時(shí)間和技術(shù)換以時(shí)間和技術(shù)換內(nèi)存空間。內(nèi)存空間。作業(yè)7(256 KB)(a)(b)(c)作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (24 KB)作業(yè)1 (8 KB)OS作業(yè)7 (256 KB)作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (24 KB)作業(yè)1(8 KB)OS01024 KB504 KB352 KB320 KB312 KB888 KB652 KB376 KB作業(yè)6 (256 KB)作業(yè)5 (128 KB)作業(yè)4 (24 KB)作業(yè)1 (8 KB)OS可以裝入作業(yè)可以裝入作業(yè)7暫不能裝入暫不能裝入J7重定

18、位寄存器重定位寄存器，存放程序，存放程序(數(shù)據(jù)數(shù)據(jù))在內(nèi)存中的起始地址。程序在執(zhí)在內(nèi)存中的起始地址。程序在執(zhí)行時(shí)，真正訪問(wèn)的內(nèi)存地址是相對(duì)地址與重定位寄存器中的行時(shí)，真正訪問(wèn)的內(nèi)存地址是相對(duì)地址與重定位寄存器中的地址相加而形成的。地址相加而形成的。動(dòng)態(tài)重定位的實(shí)現(xiàn)原理動(dòng)態(tài)重定位的實(shí)現(xiàn)原理365365LOAD 1,2500LOAD 1,2500500050002500250010001000365365LOAD 1,2500LOAD 1,250015000150001250012500100001000011000110002500相對(duì)地址相對(duì)地址10000重定位重定位寄存器寄存器處理機(jī)一側(cè)處理

19、機(jī)一側(cè) 存儲(chǔ)器一側(cè)存儲(chǔ)器一側(cè)作業(yè)作業(yè)J內(nèi)存內(nèi)存重定位是一種運(yùn)算尋址，需硬件支持重定位是一種運(yùn)算尋址，需硬件支持4.4基基 本本 分分 頁(yè)頁(yè) 存存 儲(chǔ)儲(chǔ) 管管 理理 方方 式式 將一個(gè)將一個(gè)進(jìn)程的邏輯地址空間進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的分成若干個(gè)大小相等的片，稱為片，稱為頁(yè)頁(yè)，并為各頁(yè)編號(hào)。，并為各頁(yè)編號(hào)。 把把內(nèi)存空間內(nèi)存空間分成與頁(yè)相同大小的若干個(gè)存儲(chǔ)塊，稱分成與頁(yè)相同大小的若干個(gè)存儲(chǔ)塊，稱為為塊塊，同樣予以編號(hào)。，同樣予以編號(hào)。 頁(yè)的大小通常為頁(yè)的大小通常為512 B8 KB。若干個(gè)頁(yè)分別裝入可以不相鄰接的物理塊中。最后一若干個(gè)頁(yè)分別裝入可以不相鄰接的物理塊中。最后一頁(yè)經(jīng)常裝不滿

20、一塊形成頁(yè)經(jīng)常裝不滿一塊形成“頁(yè)內(nèi)碎片頁(yè)內(nèi)碎片”。 頁(yè)式最先實(shí)現(xiàn)了作業(yè)空間的離散分配！頁(yè)式最先實(shí)現(xiàn)了作業(yè)空間的離散分配！地址結(jié)構(gòu)地址結(jié)構(gòu) 頁(yè)號(hào)頁(yè)號(hào) P 位移量位移量 W3112 110前一部分為前一部分為頁(yè)號(hào)頁(yè)號(hào)P，后一部分為位移量，后一部分為位移量W(或稱為或稱為頁(yè)內(nèi)地址頁(yè)內(nèi)地址)。例：地址長(zhǎng)度為例：地址長(zhǎng)度為32位，位，011位為頁(yè)內(nèi)地址，位為頁(yè)內(nèi)地址，1231位為頁(yè)號(hào)。位為頁(yè)號(hào)。 若邏輯地址為若邏輯地址為A A，頁(yè)的大小為，頁(yè)的大小為L(zhǎng) L，則頁(yè)號(hào)，則頁(yè)號(hào)P P和頁(yè)內(nèi)地址和頁(yè)內(nèi)地址d d可按下式求得：可按下式求得： APIN TLdA M O D L頁(yè)號(hào)：頁(yè)號(hào)：頁(yè)面地址：頁(yè)面地址：作業(yè)分

21、頁(yè)，內(nèi)存分塊作業(yè)分頁(yè)，內(nèi)存分塊頁(yè)塊等大，對(duì)應(yīng)存放頁(yè)塊等大，對(duì)應(yīng)存放建立頁(yè)表，查表訪問(wèn)建立頁(yè)表，查表訪問(wèn)頁(yè)表頁(yè)表頁(yè)表放在內(nèi)存中，它的頁(yè)表放在內(nèi)存中，它的作用作用是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。是實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的地址映射。 用戶程序0 頁(yè)1 頁(yè)2 頁(yè)3 頁(yè)4 頁(yè)5 頁(yè)n 頁(yè)頁(yè)表頁(yè)號(hào)塊號(hào)02132638495內(nèi)存012345678910頁(yè)表的作用頁(yè)表的作用 分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)頁(yè)表頁(yè)表物理地址物理地址頁(yè)表始址頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度頁(yè)表寄存器頁(yè)表寄存器5201832018邏輯地址邏輯地址越界中斷越界中斷+塊號(hào)塊號(hào)頁(yè)號(hào)頁(yè)號(hào)5332712054.5

22、基基 本本 分分 段段 存存 儲(chǔ)儲(chǔ) 管管 理理 方方 式式作業(yè)的地址空間劃分為若干個(gè)段，每個(gè)段都有自己的名字。通作業(yè)的地址空間劃分為若干個(gè)段，每個(gè)段都有自己的名字。通常用一個(gè)段號(hào)來(lái)代替段名，每個(gè)段都是從常用一個(gè)段號(hào)來(lái)代替段名，每個(gè)段都是從0開始編址的。開始編址的。地址結(jié)構(gòu)地址結(jié)構(gòu) 段號(hào)段號(hào)S 段內(nèi)位移量段內(nèi)位移量W31 16 15 0 段表段表分段地址變換由段表實(shí)現(xiàn)，在作業(yè)被調(diào)入時(shí)，為其建立一張段表。分段地址變換由段表實(shí)現(xiàn)，在作業(yè)被調(diào)入時(shí)，為其建立一張段表。作業(yè)空間(MAIN)=0030 K(X)=1020 K(D)=2015 K(S)=3010 K30 K20 K15 K10 K40 K80

23、 K段長(zhǎng) 基址段號(hào)(MAIN)=030 K(X)=120 K(D)=215 K(S)=310 K040 K80 K120 K150 K段表內(nèi)存空間0123120 K150 K利用段表實(shí)現(xiàn)利用段表實(shí)現(xiàn) 地址映射地址映射每個(gè)段在表中占有一每個(gè)段在表中占有一個(gè)表項(xiàng)，其中記錄了個(gè)表項(xiàng)，其中記錄了該段在內(nèi)存中的起始該段在內(nèi)存中的起始地址地址( (又稱為又稱為“基址基址”) )和段的長(zhǎng)度和段的長(zhǎng)度程序按段存放程序按段存放運(yùn)行查段表進(jìn)行運(yùn)行查段表進(jìn)行地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)分段系統(tǒng)的地址變換過(guò)程分段系統(tǒng)的地址變換過(guò)程 n 段號(hào)段號(hào)S 段表長(zhǎng)度段表長(zhǎng)度TL- 訪問(wèn)越界。否則，從段表訪問(wèn)越界。否則，從段表項(xiàng)中讀

24、出該段在內(nèi)存的起始地址。項(xiàng)中讀出該段在內(nèi)存的起始地址。n 段內(nèi)地址段內(nèi)地址d 段長(zhǎng)段長(zhǎng)SL-越界中斷。否則，基址越界中斷。否則，基址 + 段內(nèi)地址段內(nèi)地址d = 內(nèi)存物理地址。內(nèi)存物理地址。段表始址段表始址段表長(zhǎng)度段表長(zhǎng)度2100段表寄存器段表寄存器邏輯地址邏輯地址越界中斷越界中斷段長(zhǎng)段長(zhǎng) 基址基址段表段表段號(hào)段號(hào)01238292物理地址物理地址段號(hào)段號(hào)S S位移量位移量W W92002008K5004K6006K1K0111101110100000頁(yè)號(hào)頁(yè)號(hào)位移量位移量011001200011010001010頁(yè)表頁(yè)表0111101110011000不變不變(a)分頁(yè)分頁(yè)頁(yè)號(hào)頁(yè)號(hào) 塊號(hào)塊號(hào)00

25、00111101001000段號(hào)段號(hào)段內(nèi)地址段內(nèi)地址段表段表0000100011000100(a)分段分段0001011101110000001000000000010111100111100010000000100000段號(hào)段號(hào) 段長(zhǎng)段長(zhǎng) 基址基址分頁(yè)和分段的主要區(qū)別分頁(yè)和分段的主要區(qū)別分分 頁(yè)頁(yè)分 段信息的物理單位信息的邏輯單位出于系統(tǒng)管理的需要出于用戶的需要大小固定由系統(tǒng)確定長(zhǎng)度不固定由編譯確定作業(yè)地址空間一維作業(yè)地址空間二維頁(yè)內(nèi)碎片外部碎片不易共享易共享頁(yè)表較長(zhǎng)，查找費(fèi)時(shí)段表較短，查找速度快段頁(yè)式存儲(chǔ)管理方式段頁(yè)式存儲(chǔ)管理方式 將分頁(yè)管理和分段管理的優(yōu)點(diǎn)集中起來(lái)。將分頁(yè)管理和分段管理的

26、優(yōu)點(diǎn)集中起來(lái)。 即即對(duì)作業(yè)的地址空間分段，段內(nèi)再分頁(yè)對(duì)作業(yè)的地址空間分段，段內(nèi)再分頁(yè)。該作業(yè)有三個(gè)段，頁(yè)面大小為該作業(yè)有三個(gè)段，頁(yè)面大小為4KB。 0 4k 8k12k15k16k一段一段頁(yè)頁(yè)1 1頁(yè)頁(yè)2 2頁(yè)頁(yè)3 3頁(yè)頁(yè)三段三段 0 4k 8k10k12k0 0頁(yè)頁(yè)1 1頁(yè)頁(yè)2 2頁(yè)頁(yè)二段二段 0 4k 8k0 0頁(yè)頁(yè)1 1頁(yè)頁(yè)段號(hào) 狀態(tài) 頁(yè)表大小 頁(yè)表始址0111213041頁(yè)號(hào) 狀態(tài)存儲(chǔ)塊#0111213041操作系統(tǒng)主存頁(yè)表段表段表大小 段表始址段表寄存器段頁(yè)式地址結(jié)構(gòu)段頁(yè)式地址結(jié)構(gòu) 由段號(hào)由段號(hào)S、段內(nèi)頁(yè)號(hào)、段內(nèi)頁(yè)號(hào)P和頁(yè)內(nèi)地址和頁(yè)內(nèi)地址W三部分組成。三部分組成。通常，分段由程序員完

27、成，分頁(yè)由系統(tǒng)自動(dòng)完成。通常，分段由程序員完成，分頁(yè)由系統(tǒng)自動(dòng)完成。利用段表和頁(yè)表實(shí)現(xiàn)地址映射利用段表和頁(yè)表實(shí)現(xiàn)地址映射 地址變換過(guò)程地址變換過(guò)程段表寄存器段表始址段表長(zhǎng)度段號(hào)S頁(yè)號(hào)P段超長(zhǎng)段表0123頁(yè)內(nèi)地址頁(yè)表0123b塊號(hào) b塊內(nèi)地址頁(yè)表始址頁(yè)表長(zhǎng)度 段表寄存器段表寄存器 段段 表表 始始 址址段表長(zhǎng)度段表長(zhǎng)度TL段號(hào)段號(hào)S段頁(yè)式系統(tǒng)中獲得一條數(shù)據(jù)或指令，需訪問(wèn)內(nèi)存幾次？段頁(yè)式系統(tǒng)中獲得一條數(shù)據(jù)或指令，需訪問(wèn)內(nèi)存幾次？三次三次4.6 虛虛 擬擬 存存 儲(chǔ)儲(chǔ) 器器 的的 基基 本本 概概 念念常規(guī)存儲(chǔ)器管理方式的特征常規(guī)存儲(chǔ)器管理方式的特征1. 一次性一次性2.駐留性駐留性資源實(shí)體性和有限

28、性資源實(shí)體性和有限性局部性原理局部性原理在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域。它訪問(wèn)的存儲(chǔ)空間也局限于某個(gè)區(qū)域。(1)時(shí)間局部性時(shí)間局部性: 一個(gè)數(shù)據(jù)結(jié)構(gòu)被訪問(wèn)，不久可能再次被訪問(wèn)。一個(gè)數(shù)據(jù)結(jié)構(gòu)被訪問(wèn)，不久可能再次被訪問(wèn)。 典型原因：典型原因： 程序中存在大量的循環(huán)操作。程序中存在大量的循環(huán)操作。(2)空間局部性空間局部性:一段時(shí)間訪問(wèn)的地址可能集中在一定范圍一段時(shí)間訪問(wèn)的地址可能集中在一定范圍 。典型原因：程序順序執(zhí)行典型原因：程序順序執(zhí)行局部性原理是虛擬內(nèi)存得以實(shí)現(xiàn)的本質(zhì)局部性原理是虛擬

29、內(nèi)存得以實(shí)現(xiàn)的本質(zhì)虛擬存儲(chǔ)器虛擬存儲(chǔ)器實(shí)現(xiàn)思想實(shí)現(xiàn)思想：當(dāng)進(jìn)程運(yùn)行時(shí)，先將：當(dāng)進(jìn)程運(yùn)行時(shí)，先將一部分程序一部分程序裝入內(nèi)存，另一部裝入內(nèi)存，另一部分分暫時(shí)留在外存暫時(shí)留在外存，當(dāng)要執(zhí)行的指令不在內(nèi)存時(shí)，由系統(tǒng)自動(dòng)將，當(dāng)要執(zhí)行的指令不在內(nèi)存時(shí)，由系統(tǒng)自動(dòng)將它們它們從外存調(diào)入內(nèi)存從外存調(diào)入內(nèi)存。虛擬存儲(chǔ)器定義：具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上虛擬存儲(chǔ)器定義：具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。它把內(nèi)存與外存有對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。它把內(nèi)存與外存有機(jī)結(jié)合起來(lái)使用，構(gòu)成容量很大的機(jī)結(jié)合起來(lái)使用，構(gòu)成容量很大的“內(nèi)存內(nèi)存”。虛擬存儲(chǔ)器的特征虛擬存

30、儲(chǔ)器的特征1. 多次性多次性 2. 對(duì)換性對(duì)換性 3. 虛擬性虛擬性 4.7 請(qǐng)求分頁(yè)存儲(chǔ)管理方式請(qǐng)求分頁(yè)存儲(chǔ)管理方式 請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持 頁(yè)表機(jī)制頁(yè)表機(jī)制 頁(yè)號(hào)頁(yè)號(hào) 物理塊號(hào)物理塊號(hào) 狀態(tài)位狀態(tài)位P 訪問(wèn)字段訪問(wèn)字段A 修改位修改位M外存地址外存地址 主要是缺頁(yè)中斷機(jī)構(gòu)主要是缺頁(yè)中斷機(jī)構(gòu)地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 缺頁(yè)中斷處理保留CPU現(xiàn)場(chǎng)從外存中找到缺頁(yè)內(nèi)存滿否？選擇一頁(yè)換出該頁(yè)被修改否？將該頁(yè)寫回外存OS命令CPU從外存讀缺頁(yè)啟動(dòng)I/O硬件將一頁(yè)從外存換入內(nèi)存修改頁(yè)表否是是否頁(yè)表項(xiàng)在快表中？CPU檢索快表訪問(wèn)頁(yè)表否頁(yè)在內(nèi)存？修改訪問(wèn)位和修改位形成物理地址地址變換結(jié)束否

31、頁(yè)號(hào)頁(yè)表長(zhǎng)度?開始程序請(qǐng)求訪問(wèn)一頁(yè)產(chǎn)生缺頁(yè)中斷請(qǐng)求調(diào)頁(yè)修改快表是越界中斷是是最小物理塊數(shù)的確定最小物理塊數(shù)的確定 能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。頁(yè)面調(diào)入過(guò)程頁(yè)面調(diào)入過(guò)程當(dāng)程序要訪問(wèn)的頁(yè)面未在內(nèi)存時(shí)，向當(dāng)程序要訪問(wèn)的頁(yè)面未在內(nèi)存時(shí)，向CPU發(fā)出一缺頁(yè)中斷，中斷處理程序保發(fā)出一缺頁(yè)中斷，中斷處理程序保留留CPU環(huán)境，查找頁(yè)表，得到該頁(yè)在外存的物理塊。環(huán)境，查找頁(yè)表，得到該頁(yè)在外存的物理塊。如果此時(shí)內(nèi)存能容納新頁(yè)，則啟動(dòng)磁盤如果此時(shí)內(nèi)存能容納新頁(yè)，則啟動(dòng)磁盤I/O將所缺頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)將所缺頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。表。如果內(nèi)存已滿，選一頁(yè)換出；再把所缺的頁(yè)調(diào)入內(nèi)存，如果內(nèi)存已滿，選一頁(yè)換出；再把所缺的頁(yè)調(diào)入內(nèi)存， 并修改頁(yè)表。并修改頁(yè)表。4.8 頁(yè)面置換算法頁(yè)面置換算法