[操作系統(tǒng)]4--非連續(xù)分配

1、北京交通大學(xué)海濱學(xué)院1操作系統(tǒng)操作系統(tǒng)第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理 * * 存儲(chǔ)器的層次：分為分為寄存器寄存器、主存（內(nèi)存）主存（內(nèi)存）和和 輔存（外存）輔存（外存）三個(gè)層次。三個(gè)層次。 主存：高速緩沖存儲(chǔ)器、主存儲(chǔ)器、磁盤(pán)緩沖存儲(chǔ)器，高速緩沖存儲(chǔ)器、主存儲(chǔ)器、磁盤(pán)緩沖存儲(chǔ)器， 主存又稱(chēng)為可執(zhí)行存儲(chǔ)器；主存又稱(chēng)為可執(zhí)行存儲(chǔ)器； 輔存：固定磁盤(pán)存儲(chǔ)器、可移動(dòng)的外部存儲(chǔ)器；固定磁盤(pán)存儲(chǔ)器、可移動(dòng)的外部存儲(chǔ)器； 其可長(zhǎng)期保存數(shù)據(jù)，但不能被處理器直接訪問(wèn)。其可長(zhǎng)期保存數(shù)據(jù)，但不能被處理器直接訪問(wèn)。 本章針對(duì)的是主存（內(nèi)存）的管理 * * 存儲(chǔ)器管理的主要功能 內(nèi)存（主存）空間的分配與回收內(nèi)存（主

2、存）空間的分配與回收 邏輯地址到物理地址的轉(zhuǎn)換邏輯地址到物理地址的轉(zhuǎn)換 內(nèi)存信息（數(shù)據(jù)）的共享與保護(hù)內(nèi)存信息（數(shù)據(jù)）的共享與保護(hù) 內(nèi)存的邏輯擴(kuò)充（虛擬存儲(chǔ)器的實(shí)現(xiàn)）內(nèi)存的邏輯擴(kuò)充（虛擬存儲(chǔ)器的實(shí)現(xiàn)）一、相關(guān)概念邏輯地址：目標(biāo)代碼的相對(duì)編址邏輯地址：目標(biāo)代碼的相對(duì)編址物理地址：內(nèi)存存儲(chǔ)單元的編址物理地址：內(nèi)存存儲(chǔ)單元的編址邏輯地址空間：目標(biāo)代碼用邏輯地址編址對(duì)應(yīng)的區(qū)域邏輯地址空間：目標(biāo)代碼用邏輯地址編址對(duì)應(yīng)的區(qū)域內(nèi)存存儲(chǔ)空間：內(nèi)存若干存儲(chǔ)單元用物理地址編址對(duì)應(yīng)內(nèi)存存儲(chǔ)空間：內(nèi)存若干存儲(chǔ)單元用物理地址編址對(duì)應(yīng) 的區(qū)域的區(qū)域重定位：邏輯地址轉(zhuǎn)換為物理地址的操作（過(guò)程）重定位：邏輯地址轉(zhuǎn)換為物理地址的

3、操作（過(guò)程） 為什么要進(jìn)行重定位例：例：地址空間地址空間0100025005000LOAD 1, 2500365存儲(chǔ)空間存儲(chǔ)空間 01000011000LOAD 1, 25001250015000365+1 0 0 0 0重定位寄存器重定位寄存器 若不進(jìn)行地址轉(zhuǎn)換，將會(huì)發(fā)生運(yùn)行錯(cuò)誤。若不進(jìn)行地址轉(zhuǎn)換，將會(huì)發(fā)生運(yùn)行錯(cuò)誤。 重定位的方式靜態(tài)重定位：目標(biāo)代碼裝入內(nèi)存時(shí)，一次性進(jìn)行目標(biāo)代碼裝入內(nèi)存時(shí)，一次性進(jìn)行 邏輯地址到物理地址的邏輯地址到物理地址的地址轉(zhuǎn)換。地址轉(zhuǎn)換。動(dòng)態(tài)重定位：目標(biāo)代碼裝入內(nèi)存時(shí)，先不進(jìn)行地址目標(biāo)代碼裝入內(nèi)存時(shí)，先不進(jìn)行地址 轉(zhuǎn)換（即原代碼裝入），在執(zhí)行時(shí)轉(zhuǎn)換（即原代碼裝入），在

4、執(zhí)行時(shí), , 再實(shí)施地址轉(zhuǎn)換。再實(shí)施地址轉(zhuǎn)換。 二、程序的鏈接與裝入 * * 程序的鏈接（模塊拼接）D靜態(tài)鏈接：裝入前先鏈接靜態(tài)鏈接：裝入前先鏈接D動(dòng)態(tài)鏈接：裝入時(shí)（或在執(zhí)行時(shí)）才進(jìn)行鏈接動(dòng)態(tài)鏈接：裝入時(shí)（或在執(zhí)行時(shí)）才進(jìn)行鏈接* * 程序的裝入D絕對(duì)裝入：目標(biāo)代碼與裝入位置地址相一致絕對(duì)裝入：目標(biāo)代碼與裝入位置地址相一致;D靜態(tài)重定位裝入：一邊裝入，一邊實(shí)現(xiàn)地址轉(zhuǎn)換靜態(tài)重定位裝入：一邊裝入，一邊實(shí)現(xiàn)地址轉(zhuǎn)換;D動(dòng)態(tài)重定位裝入：原代碼裝入，待執(zhí)行時(shí)再進(jìn)行動(dòng)態(tài)重定位裝入：原代碼裝入，待執(zhí)行時(shí)再進(jìn)行 地址轉(zhuǎn)換。地址轉(zhuǎn)換。 無(wú)論采用何種方式裝入，均涉及到內(nèi)存共享與分配問(wèn)題無(wú)論采用何種方式裝入，均涉及

5、到內(nèi)存共享與分配問(wèn)題 * * 分配方式 連續(xù)分配：為作業(yè)（進(jìn)程）分配地址連續(xù)的存儲(chǔ)空間連續(xù)分配：為作業(yè)（進(jìn)程）分配地址連續(xù)的存儲(chǔ)空間 離散分配：為作業(yè)（進(jìn)程）分配不連續(xù)存儲(chǔ)空間離散分配：為作業(yè)（進(jìn)程）分配不連續(xù)存儲(chǔ)空間 三、連續(xù)分配存儲(chǔ)管理方式D 單一連續(xù)分配單一連續(xù)分配D 固定分區(qū)分配固定分區(qū)分配D 可變（動(dòng)態(tài)）分區(qū)分配可變（動(dòng)態(tài)）分區(qū)分配D 可重定位分區(qū)分配可重定位分區(qū)分配內(nèi)內(nèi) 存存O.S0max用戶區(qū)用戶區(qū)1 1）單一連續(xù)分配適用于早期單用戶單任務(wù)適用于早期單用戶單任務(wù)OSOS2 2）固定分區(qū)分配* * 算法思想 內(nèi)存可用區(qū)劃分成若干個(gè)大小固定的存區(qū)，每個(gè)內(nèi)存可用區(qū)劃分成若干個(gè)大小固定的

6、存區(qū)，每個(gè)存區(qū)分別裝入一道作業(yè)的代碼（數(shù)據(jù)）。存區(qū)分別裝入一道作業(yè)的代碼（數(shù)據(jù)）。* * 算法實(shí)現(xiàn)建立分區(qū)說(shuō)明表，記錄各分區(qū)大小、地址及分配情況建立分區(qū)說(shuō)明表，記錄各分區(qū)大小、地址及分配情況 例：例：分配：查分區(qū)說(shuō)明表，找到一個(gè)足夠大分配：查分區(qū)說(shuō)明表，找到一個(gè)足夠大 的空閑分區(qū)分配之；的空閑分區(qū)分配之；回收：將回收分區(qū)對(duì)應(yīng)的分區(qū)說(shuō)明表狀回收：將回收分區(qū)對(duì)應(yīng)的分區(qū)說(shuō)明表狀態(tài)改為態(tài)改為“空閑空閑”。* * 優(yōu)、缺點(diǎn)：優(yōu)、缺點(diǎn)： 內(nèi)存可同時(shí)裝入多道作業(yè)代碼，算法實(shí)現(xiàn)簡(jiǎn)單；內(nèi)存可同時(shí)裝入多道作業(yè)代碼，算法實(shí)現(xiàn)簡(jiǎn)單； 存在浪費(fèi)（分區(qū)一次性全部分配出去）。存在浪費(fèi)（分區(qū)一次性全部分配出去）。O.S作業(yè)作

7、業(yè)A作業(yè)作業(yè)B作業(yè)作業(yè)C 空閑空閑內(nèi)存內(nèi)存20k32k64k128k256k0 3 3）動(dòng)態(tài)（可變）分區(qū)分配* * 算法思想 事先不劃分分區(qū)，待作業(yè)需要分配內(nèi)存時(shí)，再按需事先不劃分分區(qū)，待作業(yè)需要分配內(nèi)存時(shí)，再按需分配劃分分區(qū)（分區(qū)的大小及個(gè)數(shù)不固定）。分配劃分分區(qū)（分區(qū)的大小及個(gè)數(shù)不固定）。* * 算法實(shí)現(xiàn) 建立相關(guān)數(shù)據(jù)結(jié)構(gòu)，根據(jù)分配策略（或算法）設(shè)定建立相關(guān)數(shù)據(jù)結(jié)構(gòu)，根據(jù)分配策略（或算法）設(shè)定算法程序。算法程序。D 數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)表或空閑分區(qū)表或空閑分區(qū)鏈表空閑分區(qū)鏈表例：例：記錄空閑分區(qū)的大小、地址等數(shù)據(jù)記錄空閑分區(qū)的大小、地址等數(shù)據(jù)空閑分區(qū)鏈表情況：空閑分區(qū)鏈表情況：PL080k11

8、0k 50k350k 100k580k 60k分配：查空閑分區(qū)鏈表，找到第一個(gè)足夠大的分配：查空閑分區(qū)鏈表，找到第一個(gè)足夠大的 分區(qū)，將其一分為二分配之；分區(qū)，將其一分為二分配之；回收：先將回收分區(qū)與相鄰空閑分區(qū)合并再修回收：先將回收分區(qū)與相鄰空閑分區(qū)合并再修 改空閑分區(qū)鏈表。改空閑分區(qū)鏈表。例：回收作業(yè)例：回收作業(yè)4 4先與空閑區(qū)先與空閑區(qū)3 3合并，再修改鏈表合并，再修改鏈表080k110k160k300k350k450k500k580k640k80k50k100k60k作業(yè)作業(yè)3作業(yè)作業(yè)5作業(yè)作業(yè)9作業(yè)作業(yè)4作業(yè)作業(yè)7D 分配策略（算法） 首次適應(yīng)算法首次適應(yīng)算法循環(huán)首次適應(yīng)算法循環(huán)首次

9、適應(yīng)算法最佳適應(yīng)算法最佳適應(yīng)算法最差適應(yīng)算法最差適應(yīng)算法D 分配程序?qū)崿F(xiàn)分配的算法程序?qū)崿F(xiàn)分配的算法程序D 回收算法前鄰接合并前鄰接合并后鄰接合并后鄰接合并前、后鄰接合并前、后鄰接合并不鄰接處理不鄰接處理實(shí)為空閑分區(qū)的排列方法實(shí)為空閑分區(qū)的排列方法 * * 優(yōu)、缺點(diǎn)按需分配，可解決浪費(fèi)問(wèn)題；按需分配，可解決浪費(fèi)問(wèn)題；分配算法復(fù)雜，會(huì)產(chǎn)生碎片；分配算法復(fù)雜，會(huì)產(chǎn)生碎片； 鄰接合并系統(tǒng)開(kāi)銷(xiāo)大。鄰接合并系統(tǒng)開(kāi)銷(xiāo)大。 * * 碎片問(wèn)題 碎片: :可變分區(qū)分配過(guò)程中形成的若干個(gè)非常小的無(wú)法可變分區(qū)分配過(guò)程中形成的若干個(gè)非常小的無(wú)法 再利用的小分區(qū)。再利用的小分區(qū)。 解決方法:自然消除（鄰接合并）自然消除

10、（鄰接合并）拼接技術(shù)（可重定位分區(qū)分配）拼接技術(shù)（可重定位分區(qū)分配）離散分配（分頁(yè)或分段分配）離散分配（分頁(yè)或分段分配）4 4）可重定位分區(qū)分配 * * 算法思想 在可變分區(qū)分配算法的基礎(chǔ)上，采用動(dòng)態(tài)重在可變分區(qū)分配算法的基礎(chǔ)上，采用動(dòng)態(tài)重定位方式裝入程序（數(shù)據(jù)）。當(dāng)無(wú)足夠大的分區(qū)定位方式裝入程序（數(shù)據(jù)）。當(dāng)無(wú)足夠大的分區(qū)供分配時(shí)，供分配時(shí)，若總空閑存儲(chǔ)容量夠用若總空閑存儲(chǔ)容量夠用，則將各分區(qū)，則將各分區(qū)中的內(nèi)容向內(nèi)存一端移動(dòng)（緊湊），使另一端形中的內(nèi)容向內(nèi)存一端移動(dòng)（緊湊），使另一端形成一個(gè)大的空閑分區(qū)，然后再分配。成一個(gè)大的空閑分區(qū)，然后再分配。例：前例若要為作業(yè)例：前例若要為作業(yè)1010

11、分配分配120k120k的存儲(chǔ)空間，因無(wú)足夠的存儲(chǔ)空間，因無(wú)足夠 大分區(qū)（總空閑容量大分區(qū)（總空閑容量290k290k），則先進(jìn)行合并處理。），則先進(jìn)行合并處理。030k170k220k270k350k640k作業(yè)作業(yè)3作業(yè)作業(yè)5作業(yè)作業(yè)9作業(yè)作業(yè)4作業(yè)作業(yè)7290k合并后空閑分區(qū)鏈為：合并后空閑分區(qū)鏈為：350k290k PL此時(shí)，就可為作業(yè)此時(shí)，就可為作業(yè)1010分配分區(qū)空間分配分區(qū)空間 * * 算法實(shí)現(xiàn)D 為每個(gè)作業(yè)（分區(qū)）設(shè)置一個(gè)重定位寄存器，用以為每個(gè)作業(yè)（分區(qū)）設(shè)置一個(gè)重定位寄存器，用以 存放對(duì)應(yīng)分區(qū)首地址；在進(jìn)行移動(dòng)拼接后，只需將存放對(duì)應(yīng)分區(qū)首地址；在進(jìn)行移動(dòng)拼接后，只需將 重定

12、位寄存器的值修改為新的地址即可；重定位寄存器的值修改為新的地址即可；D 為方便移動(dòng)（搬家）建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)（靜態(tài)鏈表、為方便移動(dòng)（搬家）建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)（靜態(tài)鏈表、作業(yè)表等）。作業(yè)表等）。 * * 優(yōu)、缺點(diǎn) 既可實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配，又適時(shí)解決了碎片問(wèn)題；既可實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配，又適時(shí)解決了碎片問(wèn)題； 但移動(dòng)內(nèi)存需增加系統(tǒng)開(kāi)銷(xiāo)。但移動(dòng)內(nèi)存需增加系統(tǒng)開(kāi)銷(xiāo)。 可采用離散分配方式解決此問(wèn)題四、基本分頁(yè)存儲(chǔ)管理方式 1 1）算法思想和算法實(shí)現(xiàn) * * 算法思想D作業(yè)（進(jìn)程）地址空間被分成大小相同的若干頁(yè)作業(yè)（進(jìn)程）地址空間被分成大小相同的若干頁(yè)D內(nèi)存存儲(chǔ)空間被分成大小與頁(yè)相同的若干塊內(nèi)存存儲(chǔ)空間被分成大

13、小與頁(yè)相同的若干塊D將連續(xù)的頁(yè)分配并存放到不連續(xù)的若干內(nèi)存塊中將連續(xù)的頁(yè)分配并存放到不連續(xù)的若干內(nèi)存塊中D建立頁(yè)表，記錄每一頁(yè)對(duì)應(yīng)的存儲(chǔ)塊的塊號(hào)建立頁(yè)表，記錄每一頁(yè)對(duì)應(yīng)的存儲(chǔ)塊的塊號(hào) 例：例：作業(yè)作業(yè)0頁(yè)頁(yè)1頁(yè)頁(yè)2頁(yè)頁(yè)3頁(yè)頁(yè)0塊塊1塊塊2塊塊3塊塊4塊塊5塊塊8塊塊內(nèi)存內(nèi)存 * * 算法實(shí)現(xiàn)D 建立輔助數(shù)據(jù)結(jié)構(gòu)頁(yè)表：每個(gè)作業(yè)（進(jìn)程）一張表每個(gè)作業(yè)（進(jìn)程）一張表空閑塊鏈表：記錄所有未分配空閑塊情況（供分配用）記錄所有未分配空閑塊情況（供分配用）存儲(chǔ)分塊表：記錄內(nèi)存每一塊的使用情況記錄內(nèi)存每一塊的使用情況D 確定分頁(yè)的頁(yè)面大小太大：存在頁(yè)內(nèi)碎片存在頁(yè)內(nèi)碎片太小：頁(yè)表占用空間太多頁(yè)表占用空間太多D

14、采用動(dòng)態(tài)重定位裝入作業(yè)（進(jìn)程）代碼 即在執(zhí)行時(shí)才進(jìn)行地址轉(zhuǎn)換即在執(zhí)行時(shí)才進(jìn)行地址轉(zhuǎn)換2 2）地址變換過(guò)程和地址變換機(jī)構(gòu)* * 工作原理考察邏輯地址考察邏輯地址20562056，假定一頁(yè)大小為，假定一頁(yè)大小為1K1K（1024B1024B）可計(jì)算得到物理地址：可計(jì)算得到物理地址：邏輯地址邏輯地址/ /頁(yè)大小頁(yè)大小 取整取整頁(yè)號(hào)頁(yè)號(hào) 塊號(hào)塊號(hào)邏輯地址邏輯地址/ /頁(yè)大小頁(yè)大小 取余取余頁(yè)內(nèi)位移量頁(yè)內(nèi)位移量 塊號(hào)塊號(hào)* *頁(yè)大小頁(yè)大小+ +頁(yè)內(nèi)位移量頁(yè)內(nèi)位移量 物理地址物理地址查頁(yè)表10232047204830710頁(yè)頁(yè)1頁(yè)頁(yè)2頁(yè)頁(yè)3頁(yè)頁(yè)0塊塊8塊塊01024307220562048205682頁(yè)頁(yè)

15、819282002056內(nèi)存內(nèi)存物理地址物理地址8192+8=82002056位于第位于第2頁(yè)頁(yè)相對(duì)偏差（位移）為相對(duì)偏差（位移）為8 * * 轉(zhuǎn)換過(guò)程分析 邏輯地址機(jī)內(nèi)表示（以邏輯地址機(jī)內(nèi)表示（以1616位為例）位為例）若用塊號(hào)值代替高位的頁(yè)號(hào)值，則0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 01510 90整體整體16位的值為位的值為8200物理地址物理地址0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 020561511 10 9 81 00 0 0 0 1 0 0 0 0 0 0 0 1 0 0 01510 9高位=2低位=8頁(yè)號(hào)頁(yè)內(nèi)位移量0無(wú)需計(jì)算，只需用

16、塊號(hào)代替高位的頁(yè)號(hào)，就可立即得無(wú)需計(jì)算，只需用塊號(hào)代替高位的頁(yè)號(hào)，就可立即得到對(duì)應(yīng)的物理地址到對(duì)應(yīng)的物理地址頁(yè)號(hào)頁(yè)號(hào)頁(yè)內(nèi)位移量頁(yè)內(nèi)位移量塊號(hào)塊號(hào) 頁(yè)內(nèi)位移量頁(yè)內(nèi)位移量 * * 地址變換機(jī)構(gòu)頁(yè)表寄存器頁(yè)表寄存器頁(yè)表始址頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度+越界中斷越界中斷頁(yè)號(hào)頁(yè)號(hào)塊號(hào)塊號(hào)02132538頁(yè)號(hào)頁(yè)號(hào)P頁(yè)內(nèi)位移量頁(yè)內(nèi)位移量W塊號(hào)塊號(hào)W邏輯地址邏輯地址物理地址物理地址頁(yè)表頁(yè)表拼接拼接 * * 地址變換過(guò)程及改進(jìn)的地址變換機(jī)構(gòu) 邏輯地址邏輯地址截取高位獲得頁(yè)號(hào)截取高位獲得頁(yè)號(hào)用頁(yè)號(hào)查頁(yè)表，用頁(yè)號(hào)查頁(yè)表， 得到塊號(hào)得到塊號(hào)拼接地址拼接地址 此過(guò)程需增加一次內(nèi)存訪問(wèn)此過(guò)程需增加一次內(nèi)存訪問(wèn)（查頁(yè)表）（查頁(yè)

17、表） 利用快表（具有并行查尋能力的一組高速緩沖寄存器）利用快表（具有并行查尋能力的一組高速緩沖寄存器） 存放頁(yè)表（或存放常用的部分表項(xiàng)）存放頁(yè)表（或存放常用的部分表項(xiàng)） 具有快表的地址變換機(jī)構(gòu)如P133P133圖4-144-14所示：* * 兩級(jí)和多級(jí)頁(yè)表（不要求）3 3）內(nèi)存的分配與回收 * * 分配過(guò)程 計(jì)算作業(yè)（進(jìn)程）所需的頁(yè)面數(shù)計(jì)算作業(yè)（進(jìn)程）所需的頁(yè)面數(shù)查存儲(chǔ)分塊表，查存儲(chǔ)分塊表，是否有足夠塊數(shù)的內(nèi)存供分配是否有足夠塊數(shù)的內(nèi)存供分配 查空閑塊鏈表，分配查空閑塊鏈表，分配內(nèi)存塊內(nèi)存塊分配頁(yè)表空間，建立頁(yè)表分配頁(yè)表空間，建立頁(yè)表 修改存儲(chǔ)分塊表修改存儲(chǔ)分塊表對(duì)應(yīng)表項(xiàng)數(shù)據(jù)。對(duì)應(yīng)表項(xiàng)數(shù)據(jù)。

18、* * 回收過(guò)程 根據(jù)頁(yè)表，回收（釋放）各內(nèi)存塊根據(jù)頁(yè)表，回收（釋放）各內(nèi)存塊 回收頁(yè)表回收頁(yè)表 修改存儲(chǔ)分塊表等表格。修改存儲(chǔ)分塊表等表格。 若夠若夠4 4）分頁(yè)分配不足之處 分割分配并存放，使邏輯上完整的模塊物理上不完整分割分配并存放，使邏輯上完整的模塊物理上不完整 不利于內(nèi)存信息（數(shù)據(jù)）共享和保護(hù)。主程序主程序子程序子程序數(shù)據(jù)數(shù)據(jù)0頁(yè)頁(yè)1頁(yè)頁(yè)2頁(yè)頁(yè)3頁(yè)頁(yè)五、基本分段存儲(chǔ)管理方式 1 1）算法思想D 作業(yè)（進(jìn)程）地址空間按用戶設(shè)計(jì)的邏輯結(jié)構(gòu)分成作業(yè)（進(jìn)程）地址空間按用戶設(shè)計(jì)的邏輯結(jié)構(gòu)分成若干自然段（每一段邏輯上是完整的）；若干自然段（每一段邏輯上是完整的）；D 采用可變分區(qū)分配算法為每一段

19、分配分區(qū)空間，段采用可變分區(qū)分配算法為每一段分配分區(qū)空間，段與段之間不一定連續(xù)存放；與段之間不一定連續(xù)存放；D 建立段表，記錄每一段的段長(zhǎng)及段在內(nèi)存的起始地建立段表，記錄每一段的段長(zhǎng)及段在內(nèi)存的起始地址（又稱(chēng)基址）。址（又稱(chēng)基址）。例：例：0段段1段段2段段作業(yè)作業(yè)030k018k025k0段段1段段2段段10k50k75k0內(nèi)存內(nèi)存2 2）地址結(jié)構(gòu)和地址變換機(jī)構(gòu) * * 地址空間與地址結(jié)構(gòu) 二維空間和地址：二維空間和地址：段號(hào)段號(hào)段內(nèi)地址段內(nèi)地址例：例：112k物理地址：物理地址：50k+12k=62k50k+12k=62k * * 地址變換機(jī)構(gòu) * * 改進(jìn)的地址變換機(jī)構(gòu) 與分頁(yè)系統(tǒng)類(lèi)似，

20、即用一組寄存器存放段表（快表）與分頁(yè)系統(tǒng)類(lèi)似，即用一組寄存器存放段表（快表）段表寄存器段表寄存器段表始址段表始址段表長(zhǎng)度段表長(zhǎng)度+越界中斷越界中斷段號(hào)段號(hào)段長(zhǎng)段長(zhǎng)02118k30k段號(hào)段號(hào)段內(nèi)地址段內(nèi)地址邏輯地址邏輯地址物理地址物理地址段段 表表25k段始址段始址10k50k75k+相加相加3 3）分頁(yè)與分段存儲(chǔ)管理的相同與不同之處 * *共同點(diǎn)：采用離散分配解決采用離散分配解決“碎片碎片”問(wèn)題問(wèn)題采用動(dòng)態(tài)重定位及地址變換機(jī)構(gòu)實(shí)現(xiàn)地址轉(zhuǎn)換采用動(dòng)態(tài)重定位及地址變換機(jī)構(gòu)實(shí)現(xiàn)地址轉(zhuǎn)換 * *不同之處（138138補(bǔ)充）分頁(yè)分段D 地址空間劃分物理（系統(tǒng)）物理（系統(tǒng)）邏輯（用戶）邏輯（用戶）D 存儲(chǔ)空

21、間分配不連續(xù)的塊不連續(xù)的塊不連續(xù)的分區(qū)不連續(xù)的分區(qū)D 地址空間結(jié)構(gòu)一維一維二維二維D 地址變換塊號(hào)與頁(yè)內(nèi)位塊號(hào)與頁(yè)內(nèi)位段始地址與段內(nèi)段始地址與段內(nèi)移量拼接移量拼接相對(duì)地址相加相對(duì)地址相加D 碎片問(wèn)題基本解決基本解決仍存在碎片仍存在碎片D 共享（保護(hù)）不利于共享不利于共享利于共享（保護(hù)）利于共享（保護(hù)）六、段頁(yè)式存儲(chǔ)管理方式* *算法思想D 作業(yè)地址空間先分段，每段再分頁(yè)作業(yè)地址空間先分段，每段再分頁(yè)D 內(nèi)存存儲(chǔ)空間按頁(yè)的大小分塊內(nèi)存存儲(chǔ)空間按頁(yè)的大小分塊D 為每段的若干頁(yè)分配存儲(chǔ)塊空間，并分塊存放為每段的若干頁(yè)分配存儲(chǔ)塊空間，并分塊存放D 建立段表、頁(yè)表記錄作業(yè)段、頁(yè)與內(nèi)存塊的對(duì)應(yīng)信息建立段表

22、、頁(yè)表記錄作業(yè)段、頁(yè)與內(nèi)存塊的對(duì)應(yīng)信息* *算法實(shí)現(xiàn)D 段表存放段號(hào)、對(duì)應(yīng)頁(yè)表始址和頁(yè)表長(zhǎng)度段表存放段號(hào)、對(duì)應(yīng)頁(yè)表始址和頁(yè)表長(zhǎng)度D 邏輯地址采用二維結(jié)構(gòu)邏輯地址采用二維結(jié)構(gòu)D 建立地址變換機(jī)構(gòu)實(shí)現(xiàn)地址轉(zhuǎn)換建立地址變換機(jī)構(gòu)實(shí)現(xiàn)地址轉(zhuǎn)換 * *地址變換機(jī)構(gòu)段表寄存器段表寄存器段表始址段表始址段表長(zhǎng)度段表長(zhǎng)度+越界中斷越界中斷段號(hào)段號(hào)頁(yè)表始址頁(yè)表始址頁(yè)表頁(yè)表頁(yè)號(hào)頁(yè)號(hào)頁(yè)號(hào)頁(yè)號(hào)塊號(hào)塊號(hào)段號(hào)段號(hào)頁(yè)內(nèi)位移量頁(yè)內(nèi)位移量邏輯地址邏輯地址物理地址物理地址段段 表表塊號(hào)塊號(hào)頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度+頁(yè)內(nèi)位移量頁(yè)內(nèi)位移量存儲(chǔ)分配與管理方式小結(jié)D 連續(xù)分配：?jiǎn)我贿B續(xù)分配單一連續(xù)分配固定分區(qū)分配固定分區(qū)分配 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)

23、分配 可重定位分區(qū)分配可重定位分區(qū)分配D 離散分配：基本分頁(yè)分配基本分頁(yè)分配 基本分段分配基本分段分配 段頁(yè)式分配段頁(yè)式分配共同點(diǎn)：作業(yè)必須一次性全部裝入內(nèi)存作業(yè)必須一次性全部裝入內(nèi)存D 問(wèn)題：容量超過(guò)內(nèi)存總?cè)萘康淖鳂I(yè)無(wú)法運(yùn)行；容量超過(guò)內(nèi)存總?cè)萘康淖鳂I(yè)無(wú)法運(yùn)行； 多道作業(yè)總?cè)萘砍^(guò)內(nèi)存容量，無(wú)法同時(shí)多道作業(yè)總?cè)萘砍^(guò)內(nèi)存容量，無(wú)法同時(shí)裝入內(nèi)存運(yùn)行。裝入內(nèi)存運(yùn)行。D 解決：物理擴(kuò)充存儲(chǔ)器（容量）；物理擴(kuò)充存儲(chǔ)器（容量）； 邏輯擴(kuò)充內(nèi)存邏輯擴(kuò)充內(nèi)存虛擬存儲(chǔ)器。虛擬存儲(chǔ)器。七、虛擬存儲(chǔ)器的基本概念與實(shí)現(xiàn)1 1）局部性原理 在一段時(shí)間內(nèi)，運(yùn)行的作業(yè)程序僅訪問(wèn)（涉及到）在一段時(shí)間內(nèi)，運(yùn)行的作業(yè)程序僅訪問(wèn)

24、（涉及到）一部分作業(yè)代碼，即不會(huì)涉及整個(gè)地址空間。一部分作業(yè)代碼，即不會(huì)涉及整個(gè)地址空間。 即在一段時(shí)間間隔內(nèi)，僅裝入一部分代碼即在一段時(shí)間間隔內(nèi)，僅裝入一部分代碼, ,作業(yè)照作業(yè)照樣能正常運(yùn)行樣能正常運(yùn)行2 2）虛擬存儲(chǔ)器的引入 作業(yè)（進(jìn)程）運(yùn)行時(shí)，僅裝入其代碼的一部分到內(nèi)作業(yè)（進(jìn)程）運(yùn)行時(shí)，僅裝入其代碼的一部分到內(nèi)存，待需要時(shí)再裝入其余部分，同時(shí)還可將不再運(yùn)行的存，待需要時(shí)再裝入其余部分，同時(shí)還可將不再運(yùn)行的部分調(diào)出內(nèi)存。部分調(diào)出內(nèi)存。 變相地?cái)U(kuò)充了內(nèi)存容量變相地?cái)U(kuò)充了內(nèi)存容量, ,即實(shí)現(xiàn)了即實(shí)現(xiàn)了虛擬存儲(chǔ)器虛擬存儲(chǔ)器。3 3）虛存的概念與定義 呈現(xiàn)在用戶面前的比實(shí)際內(nèi)存大得多的經(jīng)邏輯呈現(xiàn)

25、在用戶面前的比實(shí)際內(nèi)存大得多的經(jīng)邏輯擴(kuò)充的存儲(chǔ)器。擴(kuò)充的存儲(chǔ)器。 或： 僅將作業(yè)（進(jìn)程）的一部分調(diào)入內(nèi)存，通過(guò)調(diào)僅將作業(yè)（進(jìn)程）的一部分調(diào)入內(nèi)存，通過(guò)調(diào)進(jìn)、調(diào)出操作（交換技術(shù)），確保作業(yè)正常運(yùn)行的進(jìn)、調(diào)出操作（交換技術(shù)），確保作業(yè)正常運(yùn)行的存儲(chǔ)器系統(tǒng)。存儲(chǔ)器系統(tǒng)。4 4）虛存的實(shí)現(xiàn)D 覆蓋與交換技術(shù)覆蓋與交換技術(shù)D 請(qǐng)求分頁(yè)存儲(chǔ)管理請(qǐng)求分頁(yè)存儲(chǔ)管理D 請(qǐng)求分段存儲(chǔ)管理請(qǐng)求分段存儲(chǔ)管理例：例：主程序主程序A20KB子程序子程序B50KB子程序子程序C30KB子程序子程序F30KB子程序子程序D20KB子程序子程序E40KB總需求容量總需求容量190KB作業(yè)常駐區(qū)作業(yè)常駐區(qū)A（20KB）覆蓋區(qū)覆蓋

26、區(qū)1（50KB）覆蓋區(qū)覆蓋區(qū)2（40KB）只需分配只需分配110KB存儲(chǔ)空間存儲(chǔ)空間八、請(qǐng)求分頁(yè)存儲(chǔ)管理 1 1）算法思想與實(shí)現(xiàn)* * 算法思想算法思想D作業(yè)分頁(yè)，內(nèi)存分塊，頁(yè)與塊的大小相等作業(yè)分頁(yè)，內(nèi)存分塊，頁(yè)與塊的大小相等D先裝入部分頁(yè)到內(nèi)存先裝入部分頁(yè)到內(nèi)存D待運(yùn)行需要時(shí)再調(diào)入新的頁(yè)，淘汰舊的頁(yè)（交換）待運(yùn)行需要時(shí)再調(diào)入新的頁(yè)，淘汰舊的頁(yè)（交換） * * 算法實(shí)現(xiàn)算法實(shí)現(xiàn)軟、硬件支持： 系統(tǒng)有足夠大的外存及內(nèi)存；增加相關(guān)管理軟件。系統(tǒng)有足夠大的外存及內(nèi)存；增加相關(guān)管理軟件。D 擴(kuò)充頁(yè)表功能（增加頁(yè)表表項(xiàng)）擴(kuò)充頁(yè)表功能（增加頁(yè)表表項(xiàng)）D 增加缺頁(yè)中斷和缺頁(yè)中斷處理功能增加缺頁(yè)中斷和缺頁(yè)中斷

27、處理功能擴(kuò)充后的頁(yè)表表項(xiàng)如下： * * 地址變換及缺頁(yè)中斷處理地址變換及缺頁(yè)中斷處理地址變換流程：截取邏輯地址頁(yè)號(hào)截取邏輯地址頁(yè)號(hào)頁(yè)號(hào)頁(yè)號(hào)頁(yè)表長(zhǎng)度？頁(yè)表長(zhǎng)度？越界中斷越界中斷YN用頁(yè)號(hào)檢索快表用頁(yè)號(hào)檢索快表查到？查到？N查頁(yè)表（慢表）查頁(yè)表（慢表）及對(duì)應(yīng)表項(xiàng)及對(duì)應(yīng)表項(xiàng)在內(nèi)存？在內(nèi)存？缺頁(yè)中斷缺頁(yè)中斷NY該表項(xiàng)復(fù)制到快表該表項(xiàng)復(fù)制到快表修改頁(yè)表表項(xiàng)內(nèi)容修改頁(yè)表表項(xiàng)內(nèi)容用塊號(hào)與位移量拼接用塊號(hào)與位移量拼接成物理地址成物理地址Y 缺頁(yè)中斷處理流程：保存保存CPU現(xiàn)場(chǎng)信息現(xiàn)場(chǎng)信息內(nèi)存有空內(nèi)存有空閑塊？閑塊？YN選擇一頁(yè)淘汰（換出）選擇一頁(yè)淘汰（換出）被淘汰被淘汰頁(yè)修改過(guò)？頁(yè)修改過(guò)？YN將該頁(yè)寫(xiě)回到外存

28、將該頁(yè)寫(xiě)回到外存根據(jù)外存地址讀入新的頁(yè)根據(jù)外存地址讀入新的頁(yè)修改對(duì)應(yīng)頁(yè)表表項(xiàng)內(nèi)容修改對(duì)應(yīng)頁(yè)表表項(xiàng)內(nèi)容返回返回1 1）內(nèi)存塊的分配 所分配的最小內(nèi)存塊數(shù)應(yīng)能保證進(jìn)程的正常運(yùn)行所分配的最小內(nèi)存塊數(shù)應(yīng)能保證進(jìn)程的正常運(yùn)行。 * * 分配策略（物理塊的分配策略）D 固定分配，局部置換固定分配，局部置換D 可變分配，全局置換可變分配，全局置換D 可變分配，局部置換可變分配，局部置換。* * 分配方法（物理塊的分配方法） 平均分配平均分配 按比例分配按比例分配 根據(jù)優(yōu)先權(quán)分配根據(jù)優(yōu)先權(quán)分配分配策略、方法的好壞直接影響到系統(tǒng)的工作效率。分配策略、方法的好壞直接影響到系統(tǒng)的工作效率。2 2）頁(yè)的調(diào)進(jìn)時(shí)機(jī)D預(yù)調(diào)

29、入策略預(yù)調(diào)入策略D請(qǐng)求調(diào)入策略請(qǐng)求調(diào)入策略3 3）置換頁(yè)在外存的位置D 外存文件區(qū)外存文件區(qū)D 外存對(duì)換區(qū)外存對(duì)換區(qū)內(nèi)存內(nèi)存外存外存文件區(qū)文件區(qū)對(duì)換區(qū)對(duì)換區(qū)每次置換需查找文件每次置換需查找文件僅為內(nèi)存塊與盤(pán)塊的僅為內(nèi)存塊與盤(pán)塊的直接存取操作直接存取操作4 4）頁(yè)面置換（淘汰）算法 基本原則：被淘汰的頁(yè)今后或短時(shí)間內(nèi)不會(huì)再被調(diào)入被淘汰的頁(yè)今后或短時(shí)間內(nèi)不會(huì)再被調(diào)入常用算法：D 最佳算法最佳算法D 先進(jìn)先出（先進(jìn)先出（FIFOFIFO）算法）算法D 最近最久未使用（最近最久未使用（LRULRU）算法）算法D 最近最少使用（最近最少使用（LFULFU）算法）算法 * * 最佳算法舉例假設(shè)某作業(yè)訪問(wèn)頁(yè)

30、面引用序列為：假設(shè)某作業(yè)訪問(wèn)頁(yè)面引用序列為： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 10, 1, 7, 0, 1 采用固定分配，局部置換淘汰方式（分配三個(gè)內(nèi)存塊）77707012012032432032017010120 30423032120170 17被淘汰被淘汰淘汰淘汰1淘汰淘汰0淘汰淘汰4淘汰淘汰3淘汰淘汰2 * * 先進(jìn)先出算法舉例 77707012012312304304204230120 30043232120170

31、1淘汰淘汰7淘汰淘汰0淘汰淘汰1淘汰淘汰2淘汰淘汰3淘汰淘汰0023淘汰淘汰4023013淘汰淘汰2012淘汰淘汰3712淘汰淘汰0702淘汰淘汰1701淘汰淘汰2（接前行）（接前行）D 最佳算法置換最佳算法置換6 6次次，先進(jìn)先出算法置換先進(jìn)先出算法置換1212次次。 最佳算法需知曉頁(yè)面引用序列，難以實(shí)現(xiàn)；最佳算法需知曉頁(yè)面引用序列，難以實(shí)現(xiàn)； 先進(jìn)先出算法盡管簡(jiǎn)單、直觀，但性能較差。先進(jìn)先出算法盡管簡(jiǎn)單、直觀，但性能較差。 * * 最近最久未使用算法舉例7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1D 最近最久未使用最近最久未使用算法置換算法置換9 9次次。

32、 采用棧結(jié)構(gòu)實(shí)現(xiàn)，假定分配采用棧結(jié)構(gòu)實(shí)現(xiàn)，假定分配5 5個(gè)內(nèi)存塊個(gè)內(nèi)存塊頁(yè)面引用序列為：頁(yè)面引用序列為：4, 7, 0, 7, 1, 0, 1, 2, 1, 2, 64, 7, 0, 7, 1, 0, 1, 2, 1, 2, 6。4474704704401407410210120707076221117換到棧頂換到棧頂0換到棧頂換到棧頂淘汰淘汰4, 61換換換到棧頂換到棧頂2換換77417421074621071換換2換換棧底棧底請(qǐng)求分段存儲(chǔ)管理 1 1）算法思想與實(shí)現(xiàn) * * 算法思想算法思想 在基本分段存儲(chǔ)管理算法基礎(chǔ)上，增加“缺段”中斷及處理功能。 * * 算法實(shí)現(xiàn)算法實(shí)現(xiàn) 關(guān)鍵是擴(kuò)充段

33、表功能和缺段中斷處理。擴(kuò)充后的段表表項(xiàng)如下擴(kuò)充后的段表表項(xiàng)如下：段號(hào)段號(hào)段長(zhǎng)段長(zhǎng)段始址段始址存取存取方式方式訪問(wèn)訪問(wèn)字段字段修改修改位位存在位存在位外存外存地址地址 * * 地址變換及缺段中斷處理地址變換及缺段中斷處理 地址變換流程：段號(hào)段號(hào)段表長(zhǎng)段表長(zhǎng)？NY段內(nèi)地址段內(nèi)地址段長(zhǎng)？段長(zhǎng)？N越界中斷越界中斷分段越界中斷分段越界中斷Y符合符合存取方式？存取方式？N段存取保護(hù)中斷段存取保護(hù)中斷Y段在內(nèi)存？段在內(nèi)存？N缺段中斷缺段中斷Y地址變換處理地址變換處理 缺段中斷處理流程：阻塞訪問(wèn)進(jìn)程阻塞訪問(wèn)進(jìn)程內(nèi)存有合內(nèi)存有合適空閑區(qū)？適空閑區(qū)？NY分配分區(qū)，調(diào)入請(qǐng)求段分配分區(qū)，調(diào)入請(qǐng)求段修改段表及空閑分區(qū)鏈表修改段表及空閑分區(qū)鏈表喚醒對(duì)應(yīng)阻塞進(jìn)程喚醒對(duì)應(yīng)阻塞進(jìn)程返回返回空閑區(qū)總空閑區(qū)總?cè)萘繅蚍峙洌咳萘繅蚍峙?？NY進(jìn)行拼接處理進(jìn)行拼接處理選擇一段或若干選擇一段或若干段淘汰，以形成段淘汰，以形成足夠大空閑分區(qū)足夠大空閑分區(qū)2 2）段的保護(hù)D 越界檢查越界檢查D 存取控制存取控制D 其他措施其他措施 3 3）段的共享* * 基本共享方法基本共享方法段號(hào)段號(hào) 段長(zhǎng)段長(zhǎng) 段始址段始址MP1段表段表段號(hào)段號(hào) 段長(zhǎng)段長(zhǎng) 段始址段始址MP2段表段表某共享段某共享段內(nèi)存內(nèi)存M：要求：要求：D 共享段之代碼為共享段之代碼