第四章存儲器管理 (2)ppt課件

1、遼東學(xué)院信息技術(shù)學(xué)院4/16/20221第四章第四章 存儲器管理存儲器管理 4.1 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu) 4.2程序的裝入和鏈接程序的裝入和鏈接 4.3連續(xù)分配方式連續(xù)分配方式4.4基本分頁存儲管理方式基本分頁存儲管理方式4.5基本分段存儲管理方式基本分段存儲管理方式4.6虛擬存儲器的基本概念虛擬存儲器的基本概念4.7請求分頁存儲管理方式請求分頁存儲管理方式4.8頁面置換算法頁面置換算法4.9請求分段存儲管理方式請求分段存儲管理方式 遼東學(xué)院信息技術(shù)學(xué)院4/16/20222速速度度容容量量小小大大低低高高4.1 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu)寄存器高速緩存主存磁盤緩存磁盤可移動存

2、儲介質(zhì)CPU寄存器主存輔存圖4-1 計算機系統(tǒng)存儲層次示意 4.1.1 多級存儲器結(jié)構(gòu)多級存儲器結(jié)構(gòu)遼東學(xué)院信息技術(shù)學(xué)院4/16/202234.1.2 主存儲器與寄存器主存儲器與寄存器CPU的控制部件只能從主存儲器中取得指令和數(shù)據(jù)主存儲器的訪問速度遠(yuǎn)低于CPU執(zhí)行指令的速度4.1.3 高速緩存和磁盤緩存高速緩存和磁盤緩存主存中一些經(jīng)常訪問的信息存放在高速緩存中，減少訪問主存儲器的次數(shù)，可大幅度提高程序執(zhí)行速度磁盤的I/O速度遠(yuǎn)低于對主存的訪問速度，因此將頻繁使用的一部分磁盤數(shù)據(jù)和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數(shù)(利用主存)遼東學(xué)院信息技術(shù)學(xué)院4/16/202244.2 程序的裝

3、入和鏈接程序的裝入和鏈接將用戶源程序變?yōu)榭稍趦?nèi)存中執(zhí)行的程序的步驟：編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個目標(biāo)模塊鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存，構(gòu)造PCB，形成進程(使用物理地址)遼東學(xué)院信息技術(shù)學(xué)院4/16/20225庫庫鏈接鏈接程序程序裝入裝入模塊模塊裝入裝入程序程序編譯編譯程序程序產(chǎn)生產(chǎn)生的目的目標(biāo)模標(biāo)模塊塊第一步第一步第二步第二步第三步第三步內(nèi)存內(nèi)存遼東學(xué)院信息技術(shù)學(xué)院4/16/202264.2.1程序的裝入程序的裝入1絕對裝入方式絕對裝入方式(Absolute Loading

4、Mode)在編譯時，編譯程序?qū)a(chǎn)生絕對在編譯時，編譯程序?qū)a(chǎn)生絕對地址的目標(biāo)代碼地址的目標(biāo)代碼-絕對裝入。絕對裝入。2可重定位裝入方式可重定位裝入方式(Relocation Loading Mode) 在多道程序環(huán)境下，所得到的目在多道程序環(huán)境下，所得到的目標(biāo)模塊的起始地址通常是從標(biāo)模塊的起始地址通常是從0開始開始的，程序中的其它地址也都是相對的，程序中的其它地址也都是相對于起始地址于起始地址0計算的。此時應(yīng)采用計算的。此時應(yīng)采用可重定位裝入方式?？芍囟ㄎ谎b入方式。 0100025005000LOAD 1,25003651000011000LOAD 1, 125001250036515000地

5、址變換在裝入時一次完成，以后不再改變遼東學(xué)院信息技術(shù)學(xué)院4/16/202273動態(tài)運行時裝入方式動態(tài)運行時裝入方式(Dynamic Run-time Loading) 在運行過程中它在內(nèi)存中的位置可能經(jīng)常要改變，此時就應(yīng)采用動態(tài)運在運行過程中它在內(nèi)存中的位置可能經(jīng)常要改變，此時就應(yīng)采用動態(tài)運行時裝入的方式。行時裝入的方式。 裝入內(nèi)存的所有地址都仍是相對地址，地址變換在運行時才執(zhí)行裝入內(nèi)存的所有地址都仍是相對地址，地址變換在運行時才執(zhí)行 BR=100000LOAD 1,25003651000011000LOAD 1, 25001250036515000250010005000遼東學(xué)院信息技術(shù)學(xué)院

6、4/16/202284.2.2 程序的鏈接程序的鏈接(一組目標(biāo)模塊一組目標(biāo)模塊)靜態(tài)鏈接：在程序運行前，將目標(biāo)模塊及所需的庫函數(shù)鏈靜態(tài)鏈接：在程序運行前，將目標(biāo)模塊及所需的庫函數(shù)鏈接成一個完整的裝配模塊，以后不再拆開。接成一個完整的裝配模塊，以后不再拆開。裝入時動態(tài)鏈接：指將用戶源程序編譯后所得的一組目標(biāo)裝入時動態(tài)鏈接：指將用戶源程序編譯后所得的一組目標(biāo)模塊，在裝入內(nèi)存時，采用邊裝入邊鏈接的鏈接方式。模塊，在裝入內(nèi)存時，采用邊裝入邊鏈接的鏈接方式。運行時動態(tài)鏈接：指對某些目標(biāo)模塊的鏈接，是在程序執(zhí)運行時動態(tài)鏈接：指對某些目標(biāo)模塊的鏈接，是在程序執(zhí)行中需要該目標(biāo)模塊時，才對它進行鏈接。行中需要該

7、目標(biāo)模塊時，才對它進行鏈接。遼東學(xué)院信息技術(shù)學(xué)院4/16/202291、靜態(tài)鏈接、靜態(tài)鏈接(static-linking)返回返回 *對相對地址進行修改; *變換外部調(diào)用符號 事先進行鏈接所形成的一個完整的裝入模塊，又稱為可執(zhí)行文件。通常都不再拆開它，要運行時可直接將它裝入內(nèi)存模塊模塊ACALL B;Return;0L-1模塊模塊BCALL C;Return;0M-1模塊模塊CReturn;0N-1模塊模塊AJSR “L”Return;0L-1模塊模塊BJSR “L+M”Return;LL+M-1模塊模塊CReturn;L+ML+M+N-1目標(biāo)模塊目標(biāo)模塊裝入模塊裝入模塊遼東學(xué)院信息技術(shù)學(xué)院4

8、/16/2022102. 裝入時動態(tài)鏈接裝入時動態(tài)鏈接 (Load-time Dynamic Linking) 邊裝入邊鏈接。邊裝入邊鏈接。優(yōu)點：優(yōu)點： (1) 便于修改和更新便于修改和更新 (2) 便于實現(xiàn)對目標(biāo)模塊的共享便于實現(xiàn)對目標(biāo)模塊的共享3. 運行時動態(tài)鏈接運行時動態(tài)鏈接(Run-time Dynamic Linking)遼東學(xué)院信息技術(shù)學(xué)院4/16/2022114.3 連續(xù)分配方式連續(xù)分配方式 特點： 為每個用戶程序分配連續(xù)的內(nèi)存空間 方法 單一連續(xù)分配 固定分區(qū)分配 動態(tài)分區(qū)分配 可重定位分區(qū)分配遼東學(xué)院信息技術(shù)學(xué)院4/16/2022124.3.1 單一連續(xù)分配單一連續(xù)分配 最簡

9、單的一種存儲分配管理方法最簡單的一種存儲分配管理方法只能用于單用戶、單任務(wù)的操作系統(tǒng)只能用于單用戶、單任務(wù)的操作系統(tǒng)中中把內(nèi)存分為兩部分把內(nèi)存分為兩部分系統(tǒng)區(qū)：提供給系統(tǒng)區(qū)：提供給OS使用，內(nèi)存的低址使用，內(nèi)存的低址部分部分用戶區(qū)：提供給用戶使用。用戶區(qū)：提供給用戶使用。 內(nèi)存系統(tǒng)區(qū)（OS）用戶區(qū)0100k進程A進程B遼東學(xué)院信息技術(shù)學(xué)院4/16/2022134.3.2 固定分區(qū)分配固定分區(qū)分配(多道多道) 1. 劃分分區(qū)的方法劃分分區(qū)的方法 分區(qū)大小相等， 即使所有的內(nèi)存分區(qū)大小相等。 (2) 分區(qū)大小不等。 內(nèi)存 劃分為若干個固定大小的區(qū)域每個分區(qū)1個作業(yè) 遼東學(xué)院信息技術(shù)學(xué)院4/16/2

10、022142. 內(nèi)存分配內(nèi)存分配 內(nèi)存OS作業(yè)A作業(yè)B作業(yè)C作業(yè)D分區(qū)號大小(K) 起址(K)狀態(tài)11224已分配22436已分配33060未分配43590已分配540125未分配650165已分配7297215未分配0K24K90K36K60K165K125K215K進程F(70K)已分配進程G(70K)分區(qū)說明表分區(qū)說明表內(nèi)存分配程序遼東學(xué)院信息技術(shù)學(xué)院154.3.3 動態(tài)分區(qū)分配動態(tài)分區(qū)分配(根據(jù)實際需要根據(jù)實際需要) 1. 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 空閑分區(qū)表。 (2) 空閑分區(qū)鏈(可以雙向鏈)。 內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K0K35K111K77

11、K91K151K136K226K分區(qū)號 大小(K) 始址(K)242354209161513683022691202263015136遼東學(xué)院信息技術(shù)學(xué)院4/16/2022162. 分區(qū)分配算法分區(qū)分配算法 首次適應(yīng)算法首次適應(yīng)算法FF (2) 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法NF (3) 最佳適應(yīng)算法最佳適應(yīng)算法BF(4) 最壞適應(yīng)算法最壞適應(yīng)算法 WF(5) 快速適應(yīng)算法快速適應(yīng)算法QF遼東學(xué)院信息技術(shù)學(xué)院4/16/202217首次適應(yīng)法 要求空閑區(qū)按首址遞增的次序組成空閑區(qū)表鏈）,頭開始查找。 0K35K111K77K91K151K136K226K內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作

12、業(yè)D30K354291202263015136遼東學(xué)院信息技術(shù)學(xué)院4/16/2022180K35K111K77K91K151K136K226K內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K429135201361522630首次適應(yīng)算法FF1作業(yè)1請求內(nèi)存空間25K分配）2作業(yè)D完成回收）考慮：作業(yè)1完成回收）作業(yè)117K6017120K120遼東學(xué)院信息技術(shù)學(xué)院4/16/202219（1）30K作業(yè)作業(yè)A作業(yè)20K（2）30K作業(yè)A作業(yè)20K作業(yè)（3）作業(yè)30K作業(yè)作業(yè)A20K（4）作業(yè)30K作業(yè)A20K作業(yè)10030100305002010030500201003018020回收內(nèi)存的

13、四種情況20050首址200大小50K大小50K大小50K首址450大小50K80回收作業(yè)A4507010050020遼東學(xué)院信息技術(shù)學(xué)院4/16/202220分析 優(yōu)點：優(yōu)點： 優(yōu)先利用低地址空間，從而保證高址空優(yōu)先利用低地址空間，從而保證高址空間有較大的空閑區(qū)間有較大的空閑區(qū) 缺點：缺點： 低址部分被不斷劃分，留下許多難以利低址部分被不斷劃分，留下許多難以利用的、很小的空閑分區(qū)用的、很小的空閑分區(qū) 每次都從低址開始，查找開銷大每次都從低址開始，查找開銷大循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法NF 基于 首次使用算法FF 為進程分配內(nèi)存,從上次找到的空閑區(qū)的下一個空閑區(qū)開始查找. A 18, B

14、10遼東學(xué)院信息技術(shù)學(xué)院4/16/20222117913520136922610922363331023遼東學(xué)院信息技術(shù)學(xué)院4/16/202222最佳適應(yīng)法 要求按空閑區(qū)大小從小到大的次序組成空閑區(qū)表鏈）。 每次把能滿足作業(yè)要求，并且是最小的空閑分區(qū)分配給作業(yè)0K35K111K77K91K151K136K226K內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K136159120354230226遼東學(xué)院信息技術(shù)學(xué)院4/16/2022230K35K111K77K91K151K136K226K內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K最佳適應(yīng)算法1作業(yè)1請求內(nèi)存空間25K分配）2作業(yè)D完

15、成回收）考慮：作業(yè)1完成回收）作業(yè)15K90K136159120226303542251590遼東學(xué)院信息技術(shù)學(xué)院4/16/202224分析優(yōu)點：優(yōu)點：在系統(tǒng)中若存在一個與申請分區(qū)大小相等的空閑區(qū)，必在系統(tǒng)中若存在一個與申請分區(qū)大小相等的空閑區(qū)，必定會被選中，而首次適應(yīng)法則不一定。定會被選中，而首次適應(yīng)法則不一定。若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑區(qū)，則選中若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。大的空閑區(qū)。缺點：缺點：空閑區(qū)的大小一般與申請分區(qū)大小不相等，因此將其一空閑區(qū)的大小

16、一般與申請分區(qū)大小不相等，因此將其一分為二，留下來的空閑區(qū)總是最小的，以致無法使用。分為二，留下來的空閑區(qū)總是最小的，以致無法使用。隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，從隨著時間的推移，系統(tǒng)中的小空閑區(qū)會越來越多，從而造成存儲區(qū)的大量浪費。而造成存儲區(qū)的大量浪費。 遼東學(xué)院信息技術(shù)學(xué)院4/16/202225最壞適應(yīng)法 每次把能滿足作業(yè)要求，并且是最大的空閑分區(qū)分配給作業(yè) 要求空閑區(qū)按大小遞減的順序組織空閑區(qū)表或鏈）。 0K35K111K77K91K151K136K226K內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K354222630136152091遼東學(xué)院信息技術(shù)學(xué)院4/16/

17、2022260K35K111K77K91K151K136K226K內(nèi)存OS42K作業(yè)B20K作業(yè)C15K作業(yè)D30K最壞適應(yīng)算法1作業(yè)1請求內(nèi)存空間25K分配）2作業(yè)D完成回收）考慮：作業(yè)1完成回收）作業(yè)117K120K3542226309120136156017136120遼東學(xué)院信息技術(shù)學(xué)院4/16/202227分析最壞適應(yīng)法看起來似乎有些荒唐，但在嚴(yán)密地考察后，還是有它的優(yōu)點：當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑區(qū)還可能相當(dāng)大，還能裝下較大的程序。另一方面分配時每次僅作一次查詢工作。遼東學(xué)院信息技術(shù)學(xué)院4/16/202228三種策略比較 上述三種放置策略各有利弊，到底哪種最好不能一

18、概而論，而應(yīng)針對具體作業(yè)序列來分析。 對于某一作業(yè)序列來說，某種算法能將該作業(yè)序列中所有作業(yè)安置完畢，那么我們說該算法對這一作業(yè)序列是合適的。 對于某一算法而言，如它不能立即滿足某一要求，而其它算法卻可以滿足此要求，則這一算法對該作業(yè)序列是不合適的。 快速適應(yīng)算法(分類搜索)n 對于相同容量的空閑區(qū),單獨設(shè)立一個空閑分區(qū)鏈表,2k,4kn 算法優(yōu)點: n (1)查找效率高，僅需要根據(jù)進程的長度，尋找到能容納它的最小空閑區(qū)鏈表，并取下第一塊進行分配即可。n (2)另外該算法在進行空閑分區(qū)分配時，不會對任何分區(qū)產(chǎn)生分割，所以能保留大的分區(qū)，滿足對大空間的需求，也不會產(chǎn)生內(nèi)存碎片n 缺點：歸還分區(qū)算

19、法復(fù)雜 遼東學(xué)院信息技術(shù)學(xué)院4/16/2022293 3分區(qū)分配操作分區(qū)分配操作 1) 分配內(nèi)存 設(shè)請求的分區(qū)大小為u.size，表中每個空閑分區(qū)的大小可表示為m.size。若m.size-u.sizesize(size是事先規(guī)定的不再切割的剩余分區(qū)的大小)，說明多余部分太小，可不再切割，將整個分區(qū)分配給請求者； 否則(即多余部分超過size)，從該分區(qū)中按請求的大小劃分出一塊內(nèi)存空間分配出去，余下的部分仍留在空閑分區(qū)鏈(表)中。然后，將分配區(qū)的首址返回給調(diào)用者。遼東學(xué)院信息技術(shù)學(xué)院4/16/202230 2) 2) 回收內(nèi)存回收內(nèi)存 當(dāng)進程運行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首址，從當(dāng)進程運

20、行完畢釋放內(nèi)存時，系統(tǒng)根據(jù)回收區(qū)的首址，從空閑區(qū)鏈空閑區(qū)鏈( (表表) )中找到相應(yīng)的插入點，此時可能出現(xiàn)以下四中找到相應(yīng)的插入點，此時可能出現(xiàn)以下四種情況之一：種情況之一： (1) (1) 回收區(qū)與插入點的前一個空閑分區(qū)回收區(qū)與插入點的前一個空閑分區(qū)F1F1相鄰接相鄰接 (2) (2) 回收分區(qū)與插入點的后一空閑分區(qū)回收分區(qū)與插入點的后一空閑分區(qū)F2F2相鄰接。相鄰接。 (3) (3) 回收區(qū)同時與插入點的前、后兩個分區(qū)鄰接回收區(qū)同時與插入點的前、后兩個分區(qū)鄰接 (4) (4) 回收區(qū)既不與回收區(qū)既不與F1F1鄰接，又不與鄰接，又不與F2F2鄰接。這時應(yīng)為回收鄰接。這時應(yīng)為回收區(qū)單獨建立一新

21、表項，填寫回收區(qū)的首址和大小，并根據(jù)區(qū)單獨建立一新表項，填寫回收區(qū)的首址和大小，并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置。其首址插入到空閑鏈中的適當(dāng)位置。 遼東學(xué)院信息技術(shù)學(xué)院4/16/2022314/16/2022遼東學(xué)院信息技術(shù)學(xué)院32舉例 例1：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。畫出空閑區(qū)鏈并分析一下哪個算法最合適此序列？經(jīng)分析可知：最佳適應(yīng)法對這個作業(yè)序列是合適的，而其它兩種對該作業(yè)序列是不合適的。OS30作業(yè)20作業(yè)5作業(yè)46首次最正確最壞20501001201601652100203010020210465160160510020210463020210

22、4620301605201004/16/2022遼東學(xué)院信息技術(shù)學(xué)院33練習(xí) 有作業(yè)序列：作業(yè)A要求21K；作業(yè)B要求30K，作業(yè)C要求25K。4/16/2022遼東學(xué)院信息技術(shù)學(xué)院34考慮 用動態(tài)分區(qū)分配方式管理主存時,假定主存中按地址順序依次有5個空閑區(qū),空閑區(qū)的大小依次為32K,10K,5K,228K和100K,現(xiàn)有5個作業(yè)A,B,C,D,E.它們各需主存1K,10K,108K,28K和115K.若采用首次適應(yīng)算法能把這5個作業(yè)按順序全部裝入主存嗎?你認(rèn)為怎樣的次序裝入這5個作業(yè)可使主存的利用率最高?4.3.44.3.4伙伴系統(tǒng)伙伴系統(tǒng)分區(qū)大小均為2的k次冪，k為整數(shù)，lkm.相同大小的

23、所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)雙向鏈表。遼東學(xué)院信息技術(shù)學(xué)院4/16/202235 1.分配一個長度為n的存儲空間時，首先計算一個i值，使2i1n2i，然后在空閑分區(qū)大小為2i的空閑分區(qū)鏈表中查找。若找到，即把該空閑分區(qū)分配給進程; 2 .否則，則在分區(qū)大小為2i1的空閑分區(qū)鏈表中尋找。若存在2i1的一個空閑分區(qū)，則把該空閑分區(qū)分為相等的兩個分區(qū)，這兩個分區(qū)稱為一對伙伴，其中的一個分區(qū)用于分配，而把另一個加入分區(qū)大小為2i的空閑分區(qū)鏈表中; 3.若大小為2i1的空閑分區(qū)也不存在，則需要查找大小為2i2的空閑分區(qū)，若找到則對其進行兩次分割;2i+k 分割 K次. 4.3.5 哈希算法遼東學(xué)院

24、信息技術(shù)學(xué)院4/16/202236 哈希算法就是利用哈希快速查找的優(yōu)點，以及空閑分區(qū)在可利用空間表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每一個表項記錄了一個對應(yīng)的空閑分區(qū)鏈表表頭指針。當(dāng)進行空閑分區(qū)分配時，根據(jù)所需空閑分區(qū)大小，通過哈希函數(shù)計算，即得到在哈希表中的位置，從中得到相應(yīng)的空閑分區(qū)鏈表，實現(xiàn)最佳分配策略。 遼東學(xué)院信息技術(shù)學(xué)院4/16/2022374.3.6 可重定位分區(qū)分配可重定位分區(qū)分配 OS作業(yè)110作業(yè)230作業(yè)314作業(yè)426分區(qū)號起址大小35010512030716514923026 空閑分區(qū)表 20506012015016517923

25、0作業(yè)A(40)80 長度 重定位寄存器重定位寄存器作業(yè)120作業(yè)260作業(yè)3150作業(yè)4179306015512050110125176 9 216 404/16/2022382動態(tài)重定位的實現(xiàn)必須有硬件地址變換機構(gòu)的支持-重定位寄存器，用它來存放程序(數(shù)據(jù))在內(nèi)存中的起始地址。 程序在執(zhí)行時，真正訪問的內(nèi)存地址=相對地址+重定位寄存器中的地址. 動態(tài)重定位:地址變換過程是在程序執(zhí)行期間，隨著對每條指令或數(shù)據(jù)的訪問自動進行的，故稱為動態(tài)重定位。LOAD1,25003650100250050002500相對地址10000重定位寄存器LOAD1,2500365100001010012500150

26、00作業(yè)J處理機一側(cè)存儲器一側(cè)主存遼東學(xué)院信息技術(shù)學(xué)院4/16/2022394.3.7 對換對換(Swapping) 1. 對換的引入對換的引入 所謂“對換”， 是指把內(nèi)存中暫時不能運行的進程或者暫時不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運行條件的進程或進程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對換是提高內(nèi)存利用率的有效措施。 遼東學(xué)院信息技術(shù)學(xué)院4/16/2022402. 對換空間的管理對換空間的管理 為了能對對換區(qū)中的空閑盤塊進行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個表目中應(yīng)包含兩項， 即對換區(qū)的首址及其大小，它們的單位是

27、盤塊號和盤塊數(shù)。 遼東學(xué)院信息技術(shù)學(xué)院4/16/2022413. 進程的換出與換入進程的換出與換入 (1) 進程的換出。進程的換出。 系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，然后啟動系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，然后啟動盤塊，將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。盤塊，將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。 (2) 進程的換入。進程的換入。 系統(tǒng)應(yīng)定時地查看所有進程的狀態(tài)，從中找出系統(tǒng)應(yīng)定時地查看所有進程的狀態(tài)，從中找出“就緒狀態(tài)但已換出的就緒狀態(tài)但已換出的進程，將其中換出時間進程，將其中換出時間(換出到磁盤上換出到磁盤上)最久的進程作為換入進

28、程，將之換入，最久的進程作為換入進程，將之換入，直至已無可換入的進程或無可換出的進程為止。直至已無可換入的進程或無可換出的進程為止。 遼東學(xué)院信息技術(shù)學(xué)院4/16/2022424.4 基本分頁存儲管理方式基本分頁存儲管理方式 1頁面和塊定義1) 頁面和物理塊分頁存儲管理是將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號，從0開始，如第0頁、第1頁等。 相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)，也同樣為它們加以編號，如0#塊、1#塊等等。 在為進程分配內(nèi)存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理

29、塊中。由于進程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內(nèi)碎片”。 4.4.14.4.1頁面與塊頁面與塊遼東學(xué)院信息技術(shù)學(xué)院4/16/202243頁面大小頁面大小頁面大小應(yīng)選地適中，應(yīng)是頁面大小應(yīng)選地適中，應(yīng)是2的冪，通常是的冪，通常是512B8KB。2. 地址結(jié)構(gòu)地址結(jié)構(gòu)位移量位移量W頁號頁號P31 12 11 0地址長度地址長度32位位:0 11位為位移量位為位移量(頁內(nèi)地址頁內(nèi)地址)，即每頁的大小為，即每頁的大小為4KB12 31位為頁號，地址空間最多允許有位為頁號，地址空間最多允許有1M頁頁遼東學(xué)院信息技術(shù)學(xué)院4/16/202244 若給定一個邏輯地址空間中的地址為若給

30、定一個邏輯地址空間中的地址為A，頁面大小為，頁面大小為L，那么，那么: 頁號頁號P=INTA/L 頁內(nèi)地址頁內(nèi)地址d=A MOD L 例如：系統(tǒng)頁面大小為例如：系統(tǒng)頁面大小為1KB，設(shè)，設(shè)A=2170B，那么，那么: P=2，d=1224/16/2022453頁表系統(tǒng)又為每個進程建立了一張頁面映像表，稱頁表。記錄了相應(yīng)頁在內(nèi)存中對應(yīng)的物理塊號 。在配置了頁表后，進程執(zhí)行時，通過查找該表，即可找到每頁在內(nèi)存中的物理塊號?？梢?，頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射。 用戶程序0 頁1 頁2 頁3 頁4 頁5 頁n 頁頁表頁號塊號02132638495內(nèi)存012345678910遼東學(xué)院信息技

31、術(shù)學(xué)院4/16/2022464.4.2 地址變換機構(gòu)地址變換機構(gòu)1. 基本的地址變換機構(gòu)基本的地址變換機構(gòu) 頁表可以由一組專門的寄存器來實現(xiàn)，頁表可以由一組專門的寄存器來實現(xiàn)，一個頁表項用一個寄存器。但寄存器成本一個頁表項用一個寄存器。但寄存器成本高，系統(tǒng)頁表可能很大，所以頁表大多常高，系統(tǒng)頁表可能很大，所以頁表大多常駐內(nèi)存。駐內(nèi)存。 在系統(tǒng)中只設(shè)置一個頁表寄存器在系統(tǒng)中只設(shè)置一個頁表寄存器PTR，在其中存放頁表在內(nèi)存中的始址和頁表的在其中存放頁表在內(nèi)存中的始址和頁表的長度。長度。遼東學(xué)院信息技術(shù)學(xué)院4/16/202247頁表長度頁表長度頁表始址頁表始址頁表寄存器頁表寄存器頁內(nèi)地址頁內(nèi)地址頁號

32、頁號(3)邏輯地址邏輯地址L物理地址物理地址b1塊號塊號頁號頁號01234+越界中斷越界中斷頁表頁表分頁系統(tǒng)的地址變換機構(gòu)：分頁系統(tǒng)的地址變換機構(gòu)：邏輯地址邏輯地址1023：1023/1K得頁號為得頁號為0，頁內(nèi)地址為，頁內(nèi)地址為1023，查頁表找，查頁表找到對應(yīng)得物理塊為到對應(yīng)得物理塊為2，故物理地址為，故物理地址為2*1K+1023=3071。邏輯地址邏輯地址2500：2500/1K得頁號為得頁號為2，頁內(nèi)地址為，頁內(nèi)地址為452，查頁表找到，查頁表找到對應(yīng)得物理塊為對應(yīng)得物理塊為6，故物理地址為，故物理地址為6*1K+452=6596。邏輯地址邏輯地址4500：4500/1K得頁號為得頁

33、號為4，頁內(nèi)地址為，頁內(nèi)地址為404，頁號大于頁，頁號大于頁表長度，產(chǎn)生越界中斷表長度，產(chǎn)生越界中斷 某分頁系統(tǒng)，主存容量為某分頁系統(tǒng)，主存容量為64K，頁面大小為，頁面大小為1K，對一個對一個4頁大的作業(yè)，其頁大的作業(yè)，其0、1、2、3頁分別被頁分別被分配到主存的分配到主存的2、4、6、7塊中。塊中。將十進制的邏輯地址將十進制的邏輯地址1023、2500、4500轉(zhuǎn)換為轉(zhuǎn)換為物理地址物理地址 遼東學(xué)院信息技術(shù)學(xué)院4/16/202248頁式地址變換舉例頁式地址變換舉例頁表始址頁表長度頁表寄存器頁號頁面號有效地址02132821C4物理地址81C44/16/2022遼東學(xué)院信息技術(shù)學(xué)院49例：設(shè)

34、頁長為例：設(shè)頁長為1K1K，程序地址字長為，程序地址字長為1616位，用戶程位，用戶程序空間和頁表如圖，求用戶程序中序空間和頁表如圖，求用戶程序中MoveMove指令中相指令中相對地址對應(yīng)的絕對地址。對地址對應(yīng)的絕對地址。用戶程序Move r1,250001001K2K25003K-1頁表頁號塊號021427內(nèi)存01K2K3K4K5K6K7K8K9K10K-1課堂練習(xí)課堂練習(xí)4/16/2022遼東學(xué)院信息技術(shù)學(xué)院50 假定某頁式管理系統(tǒng)，主存為假定某頁式管理系統(tǒng)，主存為64KB，分成，分成16塊，塊號為塊，塊號為0，1，2，15。設(shè)某作業(yè)有。設(shè)某作業(yè)有4頁，頁，其頁號為其頁號為0，1，2，3，

35、被分別裝入主存的，被分別裝入主存的2、4、1、6塊。試問：塊。試問：該作業(yè)的總長度是多少字節(jié)？該作業(yè)的總長度是多少字節(jié)？寫出該作業(yè)每一頁在主存中的起始地址；寫出該作業(yè)每一頁在主存中的起始地址；對多個邏輯地址對多個邏輯地址0，100、1，50、2，0、3，60，試計算出相應(yīng)的內(nèi)存地址。，試計算出相應(yīng)的內(nèi)存地址。課堂練習(xí)課堂練習(xí)4/16/2022遼東學(xué)院信息技術(shù)學(xué)院51例：設(shè)虛地址為(357101)8 每一塊為128字節(jié)，求出頁號及頁內(nèi)地址偏移量）12827(357101)8(011, 101, 111, 00 1, 000, 001)21 6 74101偏移為(101)8, 頁號為(1674)8

36、塊號由頁表指定，偏移不變遼東學(xué)院信息技術(shù)學(xué)院4/16/2022522. 具有快表的地址變換機構(gòu)具有快表的地址變換機構(gòu)CPU在每存取一個數(shù)據(jù)時，需要兩次訪問內(nèi)存：在每存取一個數(shù)據(jù)時，需要兩次訪問內(nèi)存：第一次：訪問頁表，找到指定頁的物理塊號，第一次：訪問頁表，找到指定頁的物理塊號，將塊號與頁內(nèi)偏移量拼接形成物理地址。將塊號與頁內(nèi)偏移量拼接形成物理地址。第二次：從第一次所得地址中獲得所需數(shù)據(jù)，第二次：從第一次所得地址中獲得所需數(shù)據(jù)，或向此地址中寫入數(shù)據(jù)。或向此地址中寫入數(shù)據(jù)。處理速度降低！處理速度降低！解決方法：在地址變換機構(gòu)中，增設(shè)一個具有解決方法：在地址變換機構(gòu)中，增設(shè)一個具有并行查尋能力的特殊

37、高速緩沖寄存器，稱為并行查尋能力的特殊高速緩沖寄存器，稱為“聯(lián)想存儲器或聯(lián)想存儲器或“快表快表”。遼東學(xué)院信息技術(shù)學(xué)院4/16/202253頁表長度頁表長度頁表始址頁表始址頁表寄存器頁表寄存器頁內(nèi)地址頁內(nèi)地址頁號頁號(3)邏輯地址邏輯地址Ldb物理地址物理地址+越界中斷越界中斷b1塊號塊號頁號頁號頁表頁表具有快表的分頁系統(tǒng)的地址變換機構(gòu)：具有快表的分頁系統(tǒng)的地址變換機構(gòu)：b塊號塊號頁號頁號快表快表輸入寄存器輸入寄存器遼東學(xué)院信息技術(shù)學(xué)院4/16/202254假定快表的命中率為98%,快表的訪問時間為20ns,內(nèi)存的一次訪問時間為100ns,則有效訪問時間為:課堂練習(xí)課堂練習(xí)EAT(Effect

38、ive Access Time)=98%(20+100)+2%(20+200)=122ns遼東學(xué)院信息技術(shù)學(xué)院4/16/2022554.4.3 兩級和多級頁表兩級和多級頁表 現(xiàn)代計算機系統(tǒng)都支持非常大的邏現(xiàn)代計算機系統(tǒng)都支持非常大的邏輯地址空間輯地址空間(232264)，頁表就非常大，頁表就非常大，需占用較大的地址空間。需占用較大的地址空間。例如：一個具有例如：一個具有32位邏輯地址空間的分頁位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為系統(tǒng)，規(guī)定頁面大小為4KB即即212B，則，則每個進程頁表的頁表項可達每個進程頁表的頁表項可達1M個，若個，若每個頁表項占用每個頁表項占用4個字節(jié)，則每個進程個字節(jié)

39、，則每個進程的頁表就要占據(jù)的頁表就要占據(jù)4MB的內(nèi)存空間，而且的內(nèi)存空間，而且要求連續(xù)存放。要求連續(xù)存放。遼東學(xué)院信息技術(shù)學(xué)院4/16/2022561. 兩級頁表兩級頁表 例如：例如： 32位邏輯地址空間，頁面大小為位邏輯地址空間，頁面大小為4KB(即即12位位)，若，若采用一級頁表機構(gòu)，應(yīng)有采用一級頁表機構(gòu)，應(yīng)有20位頁號，即頁表項應(yīng)有位頁號，即頁表項應(yīng)有1M個；個；在采用兩級頁表機構(gòu)時，再對頁表進行分頁，使每頁包含在采用兩級頁表機構(gòu)時，再對頁表進行分頁，使每頁包含210(即即1024)個頁表項，最多允許有個頁表項，最多允許有210個頁表分頁。即個頁表分頁。即頁內(nèi)地址頁內(nèi)地址外層頁內(nèi)地址外層

40、頁內(nèi)地址外層頁號外層頁號dp2p1 31 22 21 12 11 0 遼東學(xué)院信息技術(shù)學(xué)院4/16/202257012345671141151468內(nèi)存空間內(nèi)存空間641第第0頁頁表頁頁表0121023115114第第1頁頁表頁頁表01210231468第第n頁頁表頁頁表0121023174210781011012n外部頁表外部頁表兩級分頁結(jié)構(gòu)兩級分頁結(jié)構(gòu)遼東學(xué)院信息技術(shù)學(xué)院4/16/202258外部頁表寄存器外部頁表寄存器外部頁表外部頁表頁表頁表db物理地址物理地址+dP2P1邏輯地址邏輯地址外部頁號外部頁號外部頁內(nèi)地址外部頁內(nèi)地址頁內(nèi)地址頁內(nèi)地址具有兩級頁表的地址變換機構(gòu)：具有兩級頁表的地

41、址變換機構(gòu)：遼東學(xué)院信息技術(shù)學(xué)院4/16/202259 上述方法用離散分配空間解決了大頁表無需大片存儲空上述方法用離散分配空間解決了大頁表無需大片存儲空間的問題，但并未減少頁表所占的內(nèi)存空間。間的問題，但并未減少頁表所占的內(nèi)存空間。 解決方法是把當(dāng)前需要的一批頁表項調(diào)入內(nèi)存，以后解決方法是把當(dāng)前需要的一批頁表項調(diào)入內(nèi)存，以后再根據(jù)需要陸續(xù)調(diào)入。再根據(jù)需要陸續(xù)調(diào)入。2. 多級頁表多級頁表 兩級頁表對兩級頁表對32位機器適用，位機器適用，64位呢？位呢？ 頁面大小為頁面大小為4KB即即212B，還剩，還剩52位，按物理塊大小位，按物理塊大小212位來劃分頁表，則剩余位來劃分頁表，則剩余40位用于外

42、層頁號，此時外層頁表位用于外層頁號，此時外層頁表可能有可能有1024G個頁表項，要占用個頁表項，要占用4096GB的連續(xù)存儲空間的連續(xù)存儲空間 解決方法：采用多級頁表，將外層頁表再進行分頁。解決方法：采用多級頁表，將外層頁表再進行分頁。遼東學(xué)院信息技術(shù)學(xué)院4/16/202260.166.111.2.85166810.81.61118560929Virtual AddressReal Address進程頁表首地址多級頁表地址映射多級頁表地址映射遼東學(xué)院信息技術(shù)學(xué)院4/16/2022614.5 基本分段存儲管理方式基本分段存儲管理方式 4.5.1 分段存儲管理方式的引入分段存儲管理方式的引入 引入

43、分段存儲管理方式， 主要是為了滿足用戶和程序員的下述一系列需要： 1) 方便編程Load r1,A,100 Store r2,B,500 2) 信息共享 3) 信息保護 4) 動態(tài)增長 5) 動態(tài)鏈接 遼東學(xué)院信息技術(shù)學(xué)院4/16/202262頁式管理是把內(nèi)存視為一維線性空間；而段式管理是頁式管理是把內(nèi)存視為一維線性空間；而段式管理是把內(nèi)存視為二維空間，與進程邏輯相一致。把內(nèi)存視為二維空間，與進程邏輯相一致。將程序的地址空間劃分為若干個段將程序的地址空間劃分為若干個段(segment)，程，程序加載時，分配其所需的所有段內(nèi)存分區(qū)），序加載時，分配其所需的所有段內(nèi)存分區(qū)），這些段不必連續(xù)；物理內(nèi)

44、存的管理采用動態(tài)分區(qū)。這些段不必連續(xù)；物理內(nèi)存的管理采用動態(tài)分區(qū)。需要硬件支持。需要硬件支持。4.5.2 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理遼東學(xué)院信息技術(shù)學(xué)院4/16/202263v 程序通過分段程序通過分段(segmentation)劃分為多個模塊，如代碼段、數(shù)據(jù)劃分為多個模塊，如代碼段、數(shù)據(jù)段、共享段。段、共享段。v 可以分別編寫和編譯可以分別編寫和編譯v 可以針對不同類型的段采取不同的保護可以針對不同類型的段采取不同的保護v 可以按段為單位來進行共享，包括通過動態(tài)鏈接進行代碼共享可以按段為單位來進行共享，包括通過動態(tài)鏈接進行代碼共享v 優(yōu)點：優(yōu)點：v 沒有內(nèi)碎片，外碎片可以通過內(nèi)存緊

45、縮來消除。沒有內(nèi)碎片，外碎片可以通過內(nèi)存緊縮來消除。v 便于改變進程占用空間的大小。便于改變進程占用空間的大小。v 缺點：進程全部裝入內(nèi)存。缺點：進程全部裝入內(nèi)存。4.5.2 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理遼東學(xué)院信息技術(shù)學(xué)院4/16/202264B0SA0NY0LX0PM0K邏輯段號邏輯段號01234作業(yè)作業(yè)1的地址空間的地址空間10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000長度長度 段地址段地址01234操作系統(tǒng)操作系統(tǒng)段號段號段表段表遼東學(xué)院信息技術(shù)學(xué)院4/16/202265 所需表目所需表目(1) 段表：每進

46、程一個段表：每進程一個段首址段首址段長度段長度100k40k80k60k段號段號 0: 1: 2: 3:20k200k320k300k(2) 空閑表：系統(tǒng)一個空閑表：系統(tǒng)一個 array of (addr,size)遼東學(xué)院信息技術(shù)學(xué)院4/16/202266 所需寄存器所需寄存器(1) 段表寄存器：段表寄存器：bl段表首址段表首址 段表長度段表長度系統(tǒng)一個系統(tǒng)一個(2) 快表：系統(tǒng)一組：快表：系統(tǒng)一組： 段號段號 段首址段首址 段長度段長度.ls.b.遼東學(xué)院信息技術(shù)學(xué)院4/16/2022674.5.2 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理 1. 分段分段 分段地址中的地址具有如下結(jié)構(gòu)： 段號

47、段內(nèi)地址31 16 15 0該地址結(jié)構(gòu)允許一個作業(yè)最長有該地址結(jié)構(gòu)允許一個作業(yè)最長有64K個段，每段的個段，每段的最大長度為最大長度為64KB。遼東學(xué)院信息技術(shù)學(xué)院4/16/2022682. 段表段表 段表可以存放在寄存器中，但更多的是段表可以存放在寄存器中，但更多的是存放在內(nèi)存中。存放在內(nèi)存中。 段表可以實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的段表可以實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。映射。遼東學(xué)院信息技術(shù)學(xué)院4/16/202269 利用段表實現(xiàn)地址映射 M (0)30KX(1)20KD(2)15KF(3)10K用戶作業(yè)作業(yè)空間內(nèi)存空間M (0)30KX(1)20KD(2)15KF(3)10K040K80K

48、120K150K30K40K20K80K15K120K10K150K段表 段長 基址0123遼東學(xué)院信息技術(shù)學(xué)院4/16/202270分段系統(tǒng)的地址變換過程 3. 地址變換機構(gòu) 段號S位移量W210K控制寄存器段表始址200K段表長度4越界+30K40K20K80K15K 120K10K 150K段長 基址+內(nèi)存040K80K120K150K越界4/16/2022遼東學(xué)院信息技術(shù)學(xué)院71例: 段表如下：回答下列問題：1計算該作業(yè)訪問 0，432，1，10，2，500，3，400 時的絕對地址2總結(jié)段式存儲管理的地址轉(zhuǎn)換過程。段號段長主存起始地址0123466014010058096022193

49、30090123719594/16/2022遼東學(xué)院信息技術(shù)學(xué)院72 段表如下：計算該作業(yè)訪問 0，216，1，120，2，210，3，456 時的絕對地址段號段長主存起始地址01234660140100580960221933009012371959課堂練習(xí)課堂練習(xí)遼東學(xué)院信息技術(shù)學(xué)院4/16/202273 注意：當(dāng)段表存放在內(nèi)存中時，每訪注意：當(dāng)段表存放在內(nèi)存中時，每訪問一個數(shù)據(jù)，都需訪問兩次內(nèi)存，降問一個數(shù)據(jù)，都需訪問兩次內(nèi)存，降低了計算機的速率。低了計算機的速率。 解決方法：設(shè)置聯(lián)想寄存器，用于保解決方法：設(shè)置聯(lián)想寄存器，用于保存最近常用的段表項。存最近常用的段表項。遼東學(xué)院信息技術(shù)學(xué)

50、院4/16/2022744. 分頁和分段的主要區(qū)別分頁和分段的主要區(qū)別相似點：采用離散分配方式，通過地址映射機構(gòu)實現(xiàn)地址變換相似點：采用離散分配方式，通過地址映射機構(gòu)實現(xiàn)地址變換不同點：不同點：頁是信息的物理單位，分頁是為了滿足系統(tǒng)的需要；段是信息的頁是信息的物理單位，分頁是為了滿足系統(tǒng)的需要；段是信息的邏輯單位，含有一組意義相對完整的信息，分段是為了滿足用邏輯單位，含有一組意義相對完整的信息，分段是為了滿足用戶的需要。戶的需要。頁的大小固定且由系統(tǒng)確定，由系統(tǒng)把邏輯地址分為頁號和頁內(nèi)頁的大小固定且由系統(tǒng)確定，由系統(tǒng)把邏輯地址分為頁號和頁內(nèi)地址，由機器硬件實現(xiàn)；段的長度不固定，取決于用戶程序，

51、地址，由機器硬件實現(xiàn)；段的長度不固定，取決于用戶程序，編譯程序?qū)υ闯绦蚓幾g時根據(jù)信息的性質(zhì)劃分。編譯程序?qū)υ闯绦蚓幾g時根據(jù)信息的性質(zhì)劃分。分頁的作業(yè)地址空間是一維的；分段的作業(yè)地址空間是二維的。分頁的作業(yè)地址空間是一維的；分段的作業(yè)地址空間是二維的。遼東學(xué)院信息技術(shù)學(xué)院4/16/2022754.5.3 信息共享信息共享 分頁系統(tǒng)中共享editor的示意圖（頁面大小為1K）兩個進程共享文本編輯程序Editor，程序大小4K，另每個進程自身的數(shù)據(jù)2K進程1ed1ed2ed3ed4data1data2進程2ed1ed2ed3ed4data1data2頁表202122234041頁表202122235

52、051主存0Ed120Ed221Ed322ed423data1 40data2 41data1 50data2 51遼東學(xué)院信息技術(shù)學(xué)院4/16/202276分段系統(tǒng)中共享editor的示意圖進程1editordata1進程2editordata2段表段長基址4K20K2K40K段表段長基址4K20K2K50K主存020editor40data150data2分段系統(tǒng)的一個突出優(yōu)點是易于實現(xiàn)段的共享，允許若干個進程共享一個或多個分段，且對段的保護十分簡單易行?？芍厝氪a可重入代碼(純代碼純代碼):是一個允許多個進程同時訪問是一個允許多個進程同時訪問的代碼的代碼.純代碼不允許任何進程對其修改純代

53、碼不允許任何進程對其修改遼東學(xué)院信息技術(shù)學(xué)院4/16/2022774.5.4 段頁式存儲管理段頁式存儲管理 (segmentation with paging) 段式優(yōu)于頁式段式優(yōu)于頁式 便于共享和保護便于共享和保護 頁式優(yōu)于段式頁式優(yōu)于段式 消除消除“外碎片問題外碎片問題 段頁式：結(jié)合二者優(yōu)點段頁式：結(jié)合二者優(yōu)點 每個進程包含若干段每個進程包含若干段 每個段包含若干頁每個段包含若干頁遼東學(xué)院信息技術(shù)學(xué)院4/16/2022781. 基本原理基本原理 圖 4-20 作業(yè)地址空間和地址結(jié)構(gòu) 04K8K12K15K16K子程序段04K8K數(shù)據(jù)段04K8K10K12K(a)段號(S)段內(nèi)頁號(P)段內(nèi)

54、地址(W)(b)主程序段頁遼東學(xué)院信息技術(shù)學(xué)院4/16/202279 基本原理基本原理 內(nèi)存空間劃分：內(nèi)存空間劃分：( (同頁式同頁式) ) 靜態(tài)等長，靜態(tài)等長，2i, 2i, 稱為一頁。稱為一頁。 物理地址物理地址=(=(塊號塊號, ,塊內(nèi)地塊內(nèi)地址址)=(f,w)=(f,w) 進程空間劃分：進程空間劃分： 一個進程一個進程若干個段若干個段 一個段一個段若干個頁若干個頁 邏輯地址邏輯地址=(=(段號段號, , 邏輯頁號邏輯頁號, , 頁內(nèi)地址頁內(nèi)地址)=(s,p,w)=(s,p,w)遼東學(xué)院信息技術(shù)學(xué)院4/16/202280利用段表和頁表實現(xiàn)地址映射主程序段0123子程序段01數(shù)據(jù)段012段

55、號 狀態(tài)頁表大小頁表始址041001220023400段表頁號 狀態(tài)存儲塊#020122223324頁表頁號 狀態(tài)存儲塊#040142頁表頁號 狀態(tài)存儲塊#050151252頁表主存02021222324404142505152遼東學(xué)院信息技術(shù)學(xué)院4/16/202281段表長度段表長度段表始址段表始址段表寄存器段表寄存器塊內(nèi)地址塊內(nèi)地址塊號塊號f物理地址物理地址+段超長段超長2.段頁式系統(tǒng)的地址變換機構(gòu)段頁式系統(tǒng)的地址變換機構(gòu)(3次訪問內(nèi)存次訪問內(nèi)存)頁內(nèi)地址頁內(nèi)地址頁號頁號P段號段號Sf1塊號塊號頁號頁號頁表頁表0123+段表段表0123頁表長度頁表長度頁表始址頁表始址遼東學(xué)院信息技術(shù)學(xué)院4

56、/16/2022824.6 虛擬存儲器的基本概念虛擬存儲器的基本概念 4.6.1 4.6.1 引入引入 1.1.常規(guī)存儲管理的特征：常規(guī)存儲管理的特征： 一次性指全部裝入）一次性指全部裝入） 駐留性指駐留在內(nèi)存不換出駐留性指駐留在內(nèi)存不換出, ,即使即使I/OI/O） 2 2、局部性原理、局部性原理 早在早在19681968年，年，Denning.PDenning.P就曾指出：程序在執(zhí)行時將就曾指出：程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律呈現(xiàn)出局部性規(guī)律 (1) (1) 程序執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指程序執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的。令外，在大多數(shù)情

57、況下仍是順序執(zhí)行的。 1M內(nèi)存 : 可以運行2M進程? 3個作業(yè)共需2.8M內(nèi)存, 運行?4/16/202283 時間局部性：執(zhí)行過的指令不久后可能再被執(zhí)行時間局部性：執(zhí)行過的指令不久后可能再被執(zhí)行 空間局部性：訪問過的存儲單元空間局部性：訪問過的存儲單元, ,不久后附近存儲單元也會不久后附近存儲單元也會被訪問。被訪問。(2) 過程調(diào)用將會使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5。這就是說，程序?qū)谝欢螘r間內(nèi)都局限在這些過程的范圍內(nèi)運行。(3) 程序中存在許多循環(huán)結(jié)構(gòu)，這些雖然只由少數(shù)指令構(gòu)成，但是它們將多次執(zhí)行。(4) 程序中還包括

58、許多對數(shù)據(jù)結(jié)構(gòu)的處理，如對數(shù)組進行操作，它們往往都局限于很小的范圍內(nèi)。 4/16/202284 3 3虛擬存儲器的定義虛擬存儲器的定義 基于局部性原理，部分裝入。缺頁基于局部性原理，部分裝入。缺頁/ /段，將它們段，將它們調(diào)入內(nèi)存。如果此時內(nèi)存已滿，利用頁調(diào)入內(nèi)存。如果此時內(nèi)存已滿，利用頁( (段段) )的置換功的置換功能。能。虛擬存儲器虛擬存儲器:具有請求調(diào)入和置換功能具有請求調(diào)入和置換功能,能從能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)統(tǒng).其容量其容量=內(nèi)存內(nèi)存+外存外存,速度速度-內(nèi)存內(nèi)存,本錢本錢-外存外存遼東學(xué)院信息技術(shù)學(xué)院4/16/20228

59、5引入虛擬存儲技術(shù)的好處引入虛擬存儲技術(shù)的好處大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；序；大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間通大的用戶空間：提供給用戶可用的虛擬內(nèi)存空間通常大于物理內(nèi)存常大于物理內(nèi)存(real memory)并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時的程易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時的程序結(jié)構(gòu)序結(jié)構(gòu)遼東學(xué)院信息技術(shù)學(xué)院4/16/202286 需要動態(tài)重定位需要動態(tài)重定位 1 1、請求分頁系統(tǒng)、請求分頁系統(tǒng): :以頁為單位轉(zhuǎn)換以頁為單位轉(zhuǎn)

60、換 需硬件：需硬件： （1 1請求分頁的頁表機制請求分頁的頁表機制 （2 2缺頁中斷缺頁中斷 （3 3地址變換機構(gòu)地址變換機構(gòu) 需實現(xiàn)請求分頁機制的軟件置換軟件等）需實現(xiàn)請求分頁機制的軟件置換軟件等） 2 2、請求分段系統(tǒng)、請求分段系統(tǒng): :以段為單位轉(zhuǎn)換以段為單位轉(zhuǎn)換: : （1 1請求分段的段表結(jié)構(gòu)請求分段的段表結(jié)構(gòu) （2 2缺段中斷缺段中斷 （3 3地址變換機構(gòu)地址變換機構(gòu) 需實現(xiàn)請求分段機制的軟件置換軟件等）需實現(xiàn)請求分段機制的軟件置換軟件等）遼東學(xué)院信息技術(shù)學(xué)院4/16/202287多次性：一個作業(yè)被分成多次調(diào)入內(nèi)存運行多次性：一個作業(yè)被分成多次調(diào)入內(nèi)存運行對換性：允許在作業(yè)的運行過