操作系統(tǒng)第四章__存儲器管理(1)

1、2022-4-24第四章第四章 存儲器管理存儲器管理Memory ManagementMemory Management2022-4-24l存儲器存儲器重要資源重要資源 “瓶頸瓶頸” ：關(guān)鍵、資源緊張：關(guān)鍵、資源緊張l帕金森定律帕金森定律 內(nèi)存多大，程序多長內(nèi)存多大，程序多長存儲管理的目的存儲管理的目的l滿足用戶對內(nèi)存的使用要求滿足用戶對內(nèi)存的使用要求,能夠解決程序能夠解決程序空間比實(shí)際內(nèi)存空間大得問題空間比實(shí)際內(nèi)存空間大得問題l充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供存儲基礎(chǔ)存儲基礎(chǔ)l自動裝入用戶程序，用戶程序中不用考慮自動裝入用戶程序，用戶程序中不用考慮硬件

2、細(xì)節(jié)硬件細(xì)節(jié)l存儲保護(hù)和共享存儲保護(hù)和共享2022-4-24教學(xué)要求：教學(xué)要求：l 熟悉熟悉存儲管理存儲管理目的目的和和功能功能，掌握，掌握地址重定位地址重定位的概念。的概念。l 熟悉熟悉單一連續(xù)分配單一連續(xù)分配、固定分區(qū)分配固定分區(qū)分配、動態(tài)分區(qū)分配動態(tài)分區(qū)分配實(shí)現(xiàn)實(shí)現(xiàn)原理；原理；掌握掌握動態(tài)分區(qū)分配動態(tài)分區(qū)分配的的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)和分配分配回收算法，回收算法，掌握掌握可重定位分區(qū)分配可重定位分區(qū)分配實(shí)現(xiàn)實(shí)現(xiàn)原理和分配原理和分配算法。算法。l 了解了解覆蓋覆蓋和和對換對換的概念。的概念。l 熟練掌握熟練掌握分頁存儲管理分頁存儲管理原理，原理，熟練掌握熟練掌握基本的地址變換基本的地址變換機(jī)構(gòu)

3、和具有快表的地址變換機(jī)構(gòu)，機(jī)構(gòu)和具有快表的地址變換機(jī)構(gòu)，了解兩級頁表機(jī)制。了解兩級頁表機(jī)制。l 掌握掌握分段存儲管理分段存儲管理原理原理和和分段地址變換機(jī)構(gòu)，分段地址變換機(jī)構(gòu)，掌握分頁掌握分頁和分段比較，熟和分段比較，熟悉悉分頁和分段的共享，掌握分頁和分段的共享，掌握段頁式存儲段頁式存儲管理管理原理和原理和地址變換機(jī)構(gòu)。地址變換機(jī)構(gòu)。l 虛擬存儲器虛擬存儲器的要求的要求2022-4-24第四章第四章 存儲器管理存儲器管理4.1 存儲器管理概述4.2 連續(xù)分配存儲方式4.3 頁式存儲管理4.4 段式存儲管理4.5 虛擬存儲器的概念和實(shí)現(xiàn)2022-4-24（1 1）存儲器管理的層次結(jié)構(gòu)與功能）存儲

4、器管理的層次結(jié)構(gòu)與功能1 1、存儲器的層次結(jié)構(gòu)、存儲器的層次結(jié)構(gòu)2 2、存儲器管理的功能、存儲器管理的功能（2 2）程序的鏈接）程序的鏈接1 1、靜態(tài)鏈接、靜態(tài)鏈接2 2、裝入時動態(tài)鏈接、裝入時動態(tài)鏈接3 3、運(yùn)行時動態(tài)鏈接、運(yùn)行時動態(tài)鏈接（3 3）地址重定位）地址重定位1 1、絕對裝入、絕對裝入2 2、可重定位裝入、可重定位裝入3 3、動態(tài)運(yùn)行時裝入、動態(tài)運(yùn)行時裝入返回4.1 4.1 存儲器管理概述存儲器管理概述2022-4-24（1 1）存儲器管理的層次結(jié)構(gòu)與功能）存儲器管理的層次結(jié)構(gòu)與功能1. 1. 存儲器的層次結(jié)構(gòu)存儲器的層次結(jié)構(gòu)寄存器寄存器高速緩存高速緩存主存主存磁盤緩存磁盤緩存磁盤

5、磁盤可移動存儲介質(zhì)可移動存儲介質(zhì)計算機(jī)系統(tǒng)存儲層次示意計算機(jī)系統(tǒng)存儲層次示意CPU寄存器寄存器主存主存輔存輔存速度最快、價格昂貴，容量小速度最快、價格昂貴，容量小解決解決CPU與主存速度矛盾與主存速度矛盾CPU直接訪問、可執(zhí)行存儲器直接訪問、可執(zhí)行存儲器解決主存與輔存速度矛盾解決主存與輔存速度矛盾2022-4-24各種存儲器l 高速緩存高速緩存CacheCache： 少量的、非?？焖?、昂貴、易變的，存放經(jīng)常訪問的信少量的、非?？焖?、昂貴、易變的，存放經(jīng)常訪問的信息。一級緩存快、小，二級緩存稍慢、稍大。息。一級緩存快、小，二級緩存稍慢、稍大。l 內(nèi)存內(nèi)存RAMRAM： 若干兆字節(jié)、中等速度、中等

6、價格、易變的若干兆字節(jié)、中等速度、中等價格、易變的 l 磁盤：磁盤： 數(shù)百兆或數(shù)千兆字節(jié)、低速、價廉、不易變的，訪問需數(shù)百兆或數(shù)千兆字節(jié)、低速、價廉、不易變的，訪問需要通過要通過IOIO設(shè)備（通過中斷、設(shè)備驅(qū)動程序、物理設(shè)備），設(shè)備（通過中斷、設(shè)備驅(qū)動程序、物理設(shè)備），時間長。時間長。 l 由操作系統(tǒng)協(xié)調(diào)這些存儲器的使用由操作系統(tǒng)協(xié)調(diào)這些存儲器的使用2022-4-242 2、存儲器管理的功能：、存儲器管理的功能：l 地址變換地址變換：可執(zhí)行文件生成中的鏈接技術(shù)可執(zhí)行文件生成中的鏈接技術(shù)程序加載程序加載( (裝入裝入) )時的重定位技術(shù)時的重定位技術(shù)進(jìn)程運(yùn)行時硬件和軟件的地址變換技術(shù)和機(jī)構(gòu)進(jìn)程運(yùn)

7、行時硬件和軟件的地址變換技術(shù)和機(jī)構(gòu)l 存儲分配和回收存儲分配和回收：分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)l 存儲存儲共享和保護(hù)共享和保護(hù)：代碼和數(shù)據(jù)共享代碼和數(shù)據(jù)共享地址空間訪問權(quán)限（讀、寫、執(zhí)行）地址空間訪問權(quán)限（讀、寫、執(zhí)行）l 存儲器存儲器擴(kuò)充擴(kuò)充：由應(yīng)用程序控制：覆蓋；由應(yīng)用程序控制：覆蓋；由由OS控制：對換（整個進(jìn)程空間），虛擬存儲的請求調(diào)入控制：對換（整個進(jìn)程空間），虛擬存儲的請求調(diào)入和預(yù)調(diào)入（部分進(jìn)程空間）和預(yù)調(diào)入（部分進(jìn)程空間）2022-4-24（1 1）存儲器管理的層次結(jié)構(gòu)與功能）存儲器管理的層次結(jié)構(gòu)與功能1 1、存儲器的層次結(jié)構(gòu)、存儲器的層次結(jié)構(gòu)2

8、2、存儲器管理的功能、存儲器管理的功能（2 2）程序的鏈接）程序的鏈接1 1、靜態(tài)鏈接、靜態(tài)鏈接2 2、裝入時動態(tài)鏈接、裝入時動態(tài)鏈接3 3、運(yùn)行時動態(tài)鏈接、運(yùn)行時動態(tài)鏈接（3 3）地址重定位）地址重定位1 1、絕對裝入、絕對裝入2 2、可重定位裝入、可重定位裝入3 3、動態(tài)運(yùn)行時裝入、動態(tài)運(yùn)行時裝入4.1 4.1 存儲器管理概述存儲器管理概述2022-4-24（2 2）程序的鏈接程序的鏈接l程序在成為進(jìn)程前的準(zhǔn)備工作程序在成為進(jìn)程前的準(zhǔn)備工作編輯編輯：形成源文件：形成源文件( (符號地址符號地址) )編譯編譯：形成目標(biāo)模塊：形成目標(biāo)模塊( (模塊內(nèi)符號地址解析，模塊內(nèi)符號地址解析，邏輯地址邏

9、輯地址) )鏈接鏈接：由多個目標(biāo)模塊或程序庫生成可執(zhí)行：由多個目標(biāo)模塊或程序庫生成可執(zhí)行文件文件( (模塊間符號地址解析，邏輯地址模塊間符號地址解析，邏輯地址) )裝入裝入：將可執(zhí)行文件裝入內(nèi)存，構(gòu)造：將可執(zhí)行文件裝入內(nèi)存，構(gòu)造PCBPCB，形成進(jìn)程形成進(jìn)程( (使用物理地址使用物理地址) )2022-4-24圖 4-2 對用戶程序的處理步驟2022-4-24邏輯地址、物理地址和地址映射邏輯地址、物理地址和地址映射l 邏輯地址邏輯地址（相對地址，虛地址）：用戶的程序經(jīng)過匯編或編（相對地址，虛地址）：用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地址的形式。譯后形成目標(biāo)代碼，目標(biāo)代

10、碼通常采用相對地址的形式。其首地址為其首地址為0 0，其余指令中的地址都相對于首地址來編址，其余指令中的地址都相對于首地址來編址，稱為邏輯地址。稱為邏輯地址。該地址空間不受實(shí)際內(nèi)存的限制。該地址空間不受實(shí)際內(nèi)存的限制。l 物理地址物理地址（絕對地址，實(shí)地址）：內(nèi)存中存儲單元的地址。絕對地址，實(shí)地址）：內(nèi)存中存儲單元的地址。物理地址可直接尋址。物理地址可直接尋址。l 地址映射地址映射：將用戶程序中的邏輯地址轉(zhuǎn)換為物理地址。將用戶程序中的邏輯地址轉(zhuǎn)換為物理地址。當(dāng)程序裝入內(nèi)存時, 操作系統(tǒng)要為該程序分配一個合適的內(nèi)存空間，由于程序的邏輯地址程序的邏輯地址( (從從0 0開始開始) )與分配到內(nèi)存與

11、分配到內(nèi)存物理地址物理地址( (起始地址不從起始地址不從0 0開始開始) )不一致不一致, 而CPU執(zhí)行指令時，是按物理地址從內(nèi)存中取數(shù)據(jù)和指令，所以要進(jìn)行地址轉(zhuǎn)換。2022-4-24邏輯地址、物理地址和地址映射地址映射地址映射BA=1000Load A 1200 3456。1200物理地址空間物理地址空間Load A data1data1 3456源程序源程序Load A 200 34560100200編譯鏈接編譯鏈接邏輯地址空間邏輯地址空間11002022-4-24(2)程序的鏈接 1. 1. 靜態(tài)鏈接靜態(tài)鏈接( (static-linking)static-linking) 靜態(tài)鏈接是在

12、程序運(yùn)行之前，先將各目標(biāo)模塊及靜態(tài)鏈接是在程序運(yùn)行之前，先將各目標(biāo)模塊及他們所需的庫函數(shù)，鏈接成一個完整的可執(zhí)行文件，他們所需的庫函數(shù)，鏈接成一個完整的可執(zhí)行文件，以后不再拆開。以后不再拆開。 鏈接所需做的工作：鏈接所需做的工作：1）對相對地址進(jìn)行修改2）變換外部調(diào)用符號：將每個模塊中所用的外部調(diào)用符號都變換為相對地址。2022-4-24靜態(tài)鏈接示意圖靜態(tài)鏈接示意圖目標(biāo)模塊可執(zhí)行文件Module AModule Acall function10L-1Module BModule B0M-1function1().function1FModule AModule Acall L+F0L-1Mod

13、ule BModule BLL+M-1function1().function1L+F程序的鏈接程序的鏈接模塊模塊 ACALL B；Return；0L1模塊模塊 BCALL C；Return；0M1模塊模塊 CReturn；0N1(a) 目標(biāo)模塊目標(biāo)模塊( (外存外存) )裝入前裝入前鏈接修鏈接修改地址改地址0模塊模塊 AJSR“L”Return；L1模塊模塊 BJSR“LM”Return；LLM1LMLMN1模塊模塊 CReturn；(b) 裝入模塊裝入模塊（外存）（外存）2022-4-242. 2. 裝入時動態(tài)鏈接裝入時動態(tài)鏈接(load-time dynamic-linking)(loa

14、d-time dynamic-linking)l優(yōu)點(diǎn)優(yōu)點(diǎn)便于修改和更新便于修改和更新。便于實(shí)現(xiàn)對目標(biāo)模塊的共享便于實(shí)現(xiàn)對目標(biāo)模塊的共享。 在裝入內(nèi)存時，邊裝入邊鏈接在裝入內(nèi)存時，邊裝入邊鏈接。即在裝入一個。即在裝入一個目標(biāo)模塊時，若發(fā)生一個外部模塊調(diào)用事件，則裝目標(biāo)模塊時，若發(fā)生一個外部模塊調(diào)用事件，則裝入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)入程序去找出相應(yīng)的外部目標(biāo)模塊，并將它裝入內(nèi)存。存。模塊模塊 ACALL B；Return；0L1模塊模塊 BCALL C；Return；0M1模塊模塊 CReturn；0N1外存外存0模塊模塊 AJSR“L”Return；L1模塊模塊 BJSR“L

15、M”Return；LLM1LMLMN1模塊模塊 CReturn；內(nèi)存內(nèi)存程序的鏈接程序的鏈接裝入時裝入時鏈接修鏈接修改地址改地址2022-4-243. 3. 運(yùn)行時動態(tài)鏈接運(yùn)行時動態(tài)鏈接(dynamic-linking)(dynamic-linking)l 優(yōu)點(diǎn)優(yōu)點(diǎn)共享共享：多個進(jìn)程可以共用一個：多個進(jìn)程可以共用一個DLLDLL，節(jié)省內(nèi)存，減少文，節(jié)省內(nèi)存，減少文件交換件交換部分裝入部分裝入：一個進(jìn)程可以將多種操作分散在不同的：一個進(jìn)程可以將多種操作分散在不同的DLLDLL中實(shí)現(xiàn)，而只將當(dāng)前操作相應(yīng)的中實(shí)現(xiàn)，而只將當(dāng)前操作相應(yīng)的DLLDLL裝入內(nèi)存，加快程裝入內(nèi)存，加快程序的裝入過程序的裝入過

16、程l 缺點(diǎn)：缺點(diǎn)：鏈接開銷鏈接開銷：增加了程序執(zhí)行時的鏈接開銷：增加了程序執(zhí)行時的鏈接開銷管理開銷管理開銷：若程序由多個文件組成，增加管理復(fù)雜度。：若程序由多個文件組成，增加管理復(fù)雜度。 在運(yùn)行時進(jìn)行鏈接在運(yùn)行時進(jìn)行鏈接。通常被鏈接的共享代碼稱。通常被鏈接的共享代碼稱為動態(tài)鏈接庫為動態(tài)鏈接庫( (DLL, Dynamic-Link Library)DLL, Dynamic-Link Library)或共享或共享庫庫( (shared library)shared library)。模塊模塊 ACALL B；Return；0L1模塊模塊 BCALL C；Return；0M1模塊模塊 CRetur

17、n；0N1外存外存0模塊模塊 AJSR“L”Return；L1內(nèi)存內(nèi)存執(zhí)行時執(zhí)行時鏈接修鏈接修改地址改地址2022-4-24什么是什么是DLL ？l DLL文件即動態(tài)鏈接庫文件，是一種可執(zhí)行文件，它允許程序共享執(zhí)行特殊任務(wù)所必需的代碼和其他資源。Windows提供的DLL文件中包含了允許基于Windows的程序在Windows環(huán)境下操作的許多函數(shù)和資源。l DLL多數(shù)情況下是帶有DLL擴(kuò)展名的文件，但也可能是EXE或其他擴(kuò)展名。它們向運(yùn)行于Windows操作系統(tǒng)下的程序提供代碼、數(shù)據(jù)或函數(shù)。l DLL可在“C:/Windows”目錄“C:/Windows/System”目錄和程序的安裝目錄中找

18、到。如果啟動程序，但一個或多個DLL文件丟失或毀壞，則會收到出錯消息，如“找不到xyz.dll”。如果啟動的程序帶有一個過期的DLL文件或不匹配的DLL文件，則會出現(xiàn)“未定義的動態(tài)鏈接調(diào)用”消息。這時，你可在其他電腦上找到正確的DLL文件并將它拷貝到適當(dāng)?shù)哪夸浵拢绦蚓湍苷_運(yùn)行。2022-4-24（1 1）存儲器管理的層次結(jié)構(gòu)與功能）存儲器管理的層次結(jié)構(gòu)與功能1 1、存儲器的層次結(jié)構(gòu)、存儲器的層次結(jié)構(gòu)2 2、存儲器管理的功能、存儲器管理的功能（2 2）程序的鏈接）程序的鏈接1 1、靜態(tài)鏈接、靜態(tài)鏈接2 2、裝入時動態(tài)鏈接、裝入時動態(tài)鏈接3 3、運(yùn)行時動態(tài)鏈接、運(yùn)行時動態(tài)鏈接（3 3）地址重定

19、位）地址重定位1 1、絕對裝入、絕對裝入2 2、可重定位裝入、可重定位裝入3 3、動態(tài)運(yùn)行時裝入、動態(tài)運(yùn)行時裝入返回4.1 4.1 存儲器管理概述存儲器管理概述2022-4-24（3 3）地址重定位）地址重定位l重定位：在可執(zhí)行文件裝入裝入時需要解決可可執(zhí)行程序中地址執(zhí)行程序中地址（指令和數(shù)據(jù)）和內(nèi)存地內(nèi)存地址址的轉(zhuǎn)換轉(zhuǎn)換。由操作系統(tǒng)中的裝入程序loader來完成。l重定位方法：絕對裝入可重定位裝入動態(tài)運(yùn)行時裝入2022-4-241. 絕對裝入絕對裝入(absolute loading)l 優(yōu)點(diǎn)：裝入過程簡單。優(yōu)點(diǎn)：裝入過程簡單。l 缺點(diǎn)：過于依賴于硬件結(jié)構(gòu)，不適于多道程序系缺點(diǎn)：過于依賴于硬

20、件結(jié)構(gòu)，不適于多道程序系統(tǒng)，統(tǒng)，只適用于單道程序系統(tǒng)。只適用于單道程序系統(tǒng)。若編譯時已知道放在內(nèi)存的地址，則由編若編譯時已知道放在內(nèi)存的地址，則由編譯程序產(chǎn)生絕對地址的目標(biāo)代碼。由于譯程序產(chǎn)生絕對地址的目標(biāo)代碼。由于此時程此時程序中的邏輯地址與內(nèi)存中的物理地址完全相同序中的邏輯地址與內(nèi)存中的物理地址完全相同，故裝入時故裝入時不須對程序和數(shù)據(jù)的地址進(jìn)行修改不須對程序和數(shù)據(jù)的地址進(jìn)行修改。2.2.可重定位裝入可重定位裝入(relocatable loading)(relocatable loading)靜態(tài)地址重定位靜態(tài)地址重定位在在程序執(zhí)行之前程序執(zhí)行之前由專門的重定位裝配程由專門的重定位裝配程

21、序序完成地址映射完成地址映射。 優(yōu)點(diǎn)：優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，不要硬件的支持。實(shí)現(xiàn)簡單，不要硬件的支持。 缺點(diǎn)：缺點(diǎn)：程序分配的內(nèi)存空間必須為連續(xù)空間，程序在程序分配的內(nèi)存空間必須為連續(xù)空間，程序在執(zhí)行過程中不能移動；執(zhí)行過程中不能移動；無法實(shí)現(xiàn)虛擬存儲器；無法實(shí)現(xiàn)虛擬存儲器；程序和數(shù)據(jù)難以共享。程序和數(shù)據(jù)難以共享。2022-4-24地址映射地址映射BA=1000Load A 1200 3456。1200物理地址空間物理地址空間Load A 200 34560100200邏輯地址空間邏輯地址空間11002. 可重定位裝入可重定位裝入(relocatable loading)2022-4-243. 動態(tài)

22、運(yùn)行時裝入動態(tài)運(yùn)行時裝入(dynamic run-time loading) 在把裝入模塊裝入內(nèi)存時，并不立即把裝入模在把裝入模塊裝入內(nèi)存時，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要轉(zhuǎn)換推遲到程序真正要執(zhí)行時執(zhí)行時才進(jìn)行。這種地址轉(zhuǎn)才進(jìn)行。這種地址轉(zhuǎn)換稱為換稱為動態(tài)重定位動態(tài)重定位。所需硬件：所需硬件：基地址寄存器基地址寄存器BRBR和和邏輯地址（虛地址）寄存器邏輯地址（虛地址）寄存器VRVR 內(nèi)存物理地址內(nèi)存物理地址MAMA與邏輯地址的轉(zhuǎn)換關(guān)系為：與邏輯地址的轉(zhuǎn)換關(guān)系為： MAMA（BRBR）（）（VRVR）

23、2022-4-24動態(tài)地址重定位動態(tài)地址重定位動態(tài)地址重定位過程動態(tài)地址重定位過程動態(tài)運(yùn)行時裝入的優(yōu)點(diǎn)：動態(tài)運(yùn)行時裝入的優(yōu)點(diǎn)：（1 1）可以實(shí)現(xiàn)可以實(shí)現(xiàn)對內(nèi)存的非連續(xù)分配對內(nèi)存的非連續(xù)分配。（2 2）動態(tài)地址映射在執(zhí)行時完成的，程序動態(tài)地址映射在執(zhí)行時完成的，程序中中不執(zhí)行的程序就不做地址映射的工作不執(zhí)行的程序就不做地址映射的工作，這樣既節(jié)省了這樣既節(jié)省了CPUCPU的時間，又提供了實(shí)的時間，又提供了實(shí)現(xiàn)虛擬存儲器的可能性?，F(xiàn)虛擬存儲器的可能性。（3 3）有利于程序和數(shù)據(jù)的共享有利于程序和數(shù)據(jù)的共享。2022-4-244.2 連續(xù)分配存儲方式連續(xù)分配存儲方式連續(xù)分配方式，是指連續(xù)分配方式，是指

24、為一個用戶程序分配一個連續(xù)的內(nèi)為一個用戶程序分配一個連續(xù)的內(nèi)存空間存空間。分為四種方式：分為四種方式：（1）單一連續(xù)分配）單一連續(xù)分配（2）固定分區(qū)分配）固定分區(qū)分配（3）動態(tài)）動態(tài)/可變分區(qū)分配可變分區(qū)分配1、可變式分區(qū)數(shù)據(jù)結(jié)構(gòu)、可變式分區(qū)數(shù)據(jù)結(jié)構(gòu)2、分區(qū)分配算法、分區(qū)分配算法3、分配算法框圖、分配算法框圖4、回收算法、回收算法（4）動態(tài)重定位分區(qū)分配）動態(tài)重定位分區(qū)分配返回（1 1）單一連續(xù)分配）單一連續(xù)分配內(nèi)存分為兩個區(qū)域：內(nèi)存分為兩個區(qū)域：系統(tǒng)區(qū)，用戶區(qū)系統(tǒng)區(qū)，用戶區(qū)。應(yīng)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間?？臻g。最簡單，適用于單用戶、單任務(wù)

25、的最簡單，適用于單用戶、單任務(wù)的OS。優(yōu)點(diǎn)優(yōu)點(diǎn)：易于管理。易于管理。缺點(diǎn)缺點(diǎn)：只能存放單道應(yīng)用程序；對要求內(nèi)存空間少只能存放單道應(yīng)用程序；對要求內(nèi)存空間少的程序，造成內(nèi)存浪費(fèi)；程序全部裝入，很少使的程序，造成內(nèi)存浪費(fèi)；程序全部裝入，很少使用的程序部分也占用內(nèi)存。用的程序部分也占用內(nèi)存。2022-4-24用戶程序用戶程序位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)0 xFFF.0位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序0ROM中的中的設(shè)備驅(qū)動程序設(shè)備驅(qū)動程序用戶程序用戶程序位于位于RAM中的中的操作系統(tǒng)操作系統(tǒng)0單一連續(xù)區(qū)存儲管理單一連續(xù)區(qū)存儲管理2022-4-24（2 2）固定分區(qū)分配

26、）固定分區(qū)分配(Fixed Partitioning) 基本思想：基本思想：把內(nèi)存空間分成若干個把內(nèi)存空間分成若干個固定固定大小大小的分區(qū)。每個的分區(qū)。每個分區(qū)裝入一作業(yè)或進(jìn)程。分區(qū)裝入一作業(yè)或進(jìn)程。劃分工作可以由系統(tǒng)劃分工作可以由系統(tǒng)管理員完成，也可以由操作系統(tǒng)實(shí)現(xiàn)。然而一管理員完成，也可以由操作系統(tǒng)實(shí)現(xiàn)。然而一旦劃分完成，旦劃分完成，在系統(tǒng)運(yùn)行期間不再重新劃分在系統(tǒng)運(yùn)行期間不再重新劃分 固定：分區(qū)的大小、分區(qū)的個數(shù)，一旦劃分就固定：分區(qū)的大小、分區(qū)的個數(shù)，一旦劃分就不再變化。不再變化。劃分分區(qū)的方法如下：劃分分區(qū)的方法如下：l 分區(qū)大小相等：只適合于多個相同程序的并發(fā)執(zhí)分區(qū)大小相等：只適合

27、于多個相同程序的并發(fā)執(zhí)行（處理多個類型相同的對象），否則會缺乏靈行（處理多個類型相同的對象），否則會缺乏靈活性?；钚?。太大：浪費(fèi)太大：浪費(fèi)太?。翰粔蛴锰。翰粔蛴胠 分區(qū)大小不等：多個小分區(qū)、適量的中等分區(qū)、分區(qū)大小不等：多個小分區(qū)、適量的中等分區(qū)、少量的大分區(qū)。少量的大分區(qū)。根據(jù)程序的大小，分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。根據(jù)程序的大小，分配當(dāng)前空閑的、適當(dāng)大小的分區(qū)。大班在大教室、小班在小教室大班在大教室、小班在小教室2022-4-248 M8 M8 M8 M8 MOperating SystemOperating System8 M12 M8 M8 M6 M4 M2 M固定分區(qū)(大小相同

28、)固定分區(qū)(多種大小)2022-4-24固定分區(qū)分配固定分區(qū)分配數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 分區(qū)說明表分區(qū)說明表 系統(tǒng)有一張系統(tǒng)有一張分區(qū)說明表分區(qū)說明表，每個表目說明一個，每個表目說明一個分區(qū)的分區(qū)的大小大小、起始地址起始地址和和是否已分配是否已分配的使用的使用標(biāo)志。分區(qū)說明表和內(nèi)存分配圖如下所示：標(biāo)志。分區(qū)說明表和內(nèi)存分配圖如下所示：2022-4-24區(qū)號 大小 起址 標(biāo)志 1 16KB 20K 已分配 2 32KB 36K 已分配 3 64KB 68K 已分配 4 124KB 132K 未分配0k： 20k： 第1分區(qū)( 16kb )36k： 第2分區(qū)(32kb)(已分配) 68k： 第3分區(qū)(6

29、4kb) (已分配)132k： 第4分區(qū)(124kb)(未分配) 256k：（b）內(nèi)存分配圖固定分區(qū)分配 (a) 分區(qū)說明表 操作系統(tǒng)作業(yè)A（16k）作業(yè)B（26k）作業(yè)C（56k）分區(qū)的分配分區(qū)的分配 按作業(yè)按作業(yè)/ /進(jìn)程長度查分區(qū)說明表，找進(jìn)程長度查分區(qū)說明表，找“未分未分配配”且滿足長度要求的分區(qū)進(jìn)行分配，之后且滿足長度要求的分區(qū)進(jìn)行分配，之后修改分區(qū)說明表（將該分區(qū)修改成已分修改分區(qū)說明表（將該分區(qū)修改成已分配）。配）。 分區(qū)的回收分區(qū)的回收 釋放一分區(qū)，將分區(qū)說明表的對應(yīng)狀態(tài)標(biāo)釋放一分區(qū)，將分區(qū)說明表的對應(yīng)狀態(tài)標(biāo)志置為志置為“未分配未分配”2022-4-24固定分區(qū)分配的優(yōu)缺點(diǎn)固定

30、分區(qū)分配的優(yōu)缺點(diǎn)l優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開銷小。優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開銷小。l缺點(diǎn)：缺點(diǎn)：分區(qū)內(nèi)剩余空間分區(qū)內(nèi)剩余空間不能利用造成浪費(fèi)不能利用造成浪費(fèi)分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目。返回問題：并發(fā)進(jìn)程數(shù)受分區(qū)個數(shù)的制約！問題：并發(fā)進(jìn)程數(shù)受分區(qū)個數(shù)的制約！出現(xiàn)：有內(nèi)存卻不能運(yùn)行程序或大進(jìn)程無法運(yùn)行！出現(xiàn)：有內(nèi)存卻不能運(yùn)行程序或大進(jìn)程無法運(yùn)行！2022-4-24（3 3）動態(tài)）動態(tài)/ /可變式可變式 (Dynamic Partitioning) (Dynamic Partitioning)分區(qū)分配分區(qū)分配 基本思想：基本思想：作業(yè)執(zhí)行前系統(tǒng)只有一個分區(qū)，根作業(yè)

31、執(zhí)行前系統(tǒng)只有一個分區(qū)，根據(jù)裝入作業(yè)據(jù)裝入作業(yè)/進(jìn)程的大小進(jìn)行分區(qū)。改變了小作進(jìn)程的大小進(jìn)行分區(qū)。改變了小作業(yè)占據(jù)大分區(qū)的浪費(fèi)現(xiàn)象。業(yè)占據(jù)大分區(qū)的浪費(fèi)現(xiàn)象。分區(qū)的大小和個數(shù)由裝入作業(yè)分區(qū)的大小和個數(shù)由裝入作業(yè)/進(jìn)程的大小和個進(jìn)程的大小和個數(shù)決定，且是隨時改變的。數(shù)決定，且是隨時改變的。l優(yōu)點(diǎn)：沒有分區(qū)內(nèi)碎片。l缺點(diǎn)：有外碎片；如果分區(qū)大小不是任意的，也可能出現(xiàn)內(nèi)碎片。內(nèi)存初始分配情況內(nèi)存初始分配情況 內(nèi)存分配變化過程內(nèi)存分配變化過程 但隨著進(jìn)程的執(zhí)行，內(nèi)存分區(qū)的分配和釋放，也但隨著進(jìn)程的執(zhí)行，內(nèi)存分區(qū)的分配和釋放，也會出現(xiàn)內(nèi)存碎片。會出現(xiàn)內(nèi)存碎片。2022-4-24Operating Syst

32、em128 K896 KOperating SystemProcess 1320 K576 KOperating SystemProcess 1320 KProcess 2224 K352 K可變分區(qū)分配可變分區(qū)分配(首次適應(yīng)算法首次適應(yīng)算法)2022-4-24Operating SystemProcess 1320 KProcess 2Process 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3288 K64 KProces

33、s 4128 K96 K2022-4-24OperatingSystem320 KProcess 3288 K64 KProcess 4128 K96 KOperatingSystemProcess 3288 K64 KProcess 4128 K96 KProcess 5224 k96 K1.1.可變式分區(qū)數(shù)據(jù)結(jié)構(gòu)可變式分區(qū)數(shù)據(jù)結(jié)構(gòu) 分區(qū)說明表分區(qū)說明表 可用分區(qū)表可用分區(qū)表/ /可用分區(qū)自由鏈可用分區(qū)自由鏈2022-4-24N個字節(jié)可 用前向指針N+20前向指針N+20后向指針N+20空閑分區(qū)鏈(雙向鏈表)2022-4-242. 2. 分區(qū)分配算法分區(qū)分配算法根據(jù)空閑區(qū)表組織的方法的不同，

34、有不同的根據(jù)空閑區(qū)表組織的方法的不同，有不同的放置策略，它們是：放置策略，它們是：首次首次適應(yīng)算法：適應(yīng)算法：空閑區(qū)按空閑區(qū)按物理地址遞增物理地址遞增排列。排列。最佳最佳適應(yīng)算法：適應(yīng)算法：空閑區(qū)按空閑區(qū)按空間大小遞增空間大小遞增排列。排列。最壞最壞適應(yīng)算法：適應(yīng)算法：空閑區(qū)按空閑區(qū)按空間大小遞減空間大小遞減排列排列。 首次適應(yīng)算法（首次適應(yīng)算法（First FitFirst Fit） 最先適應(yīng)算法的空閑區(qū)是按空閑區(qū)首址從最先適應(yīng)算法的空閑區(qū)是按空閑區(qū)首址從小到大組織的。小到大組織的。( (下圖中紅色為空閑區(qū)下圖中紅色為空閑區(qū)) ) 思路：思路：分配時從表首開始，找到第一個滿足要求的分配時從表

35、首開始，找到第一個滿足要求的空閑區(qū)，若空閑區(qū)大于請求的長度，就將該空閑區(qū)空閑區(qū)，若空閑區(qū)大于請求的長度，就將該空閑區(qū)的一部分分配給請求者，剩余部分成為新的空閑區(qū)。的一部分分配給請求者，剩余部分成為新的空閑區(qū)。特點(diǎn)：盡量利用低地址部分的空閑區(qū)，使高地址部特點(diǎn)：盡量利用低地址部分的空閑區(qū)，使高地址部分保留大的空閑區(qū)，保證在大作業(yè)到來時有足夠大分保留大的空閑區(qū)，保證在大作業(yè)到來時有足夠大的空閑區(qū)來滿足請求者。的空閑區(qū)來滿足請求者。 但找到的第一個空閑區(qū)并非最合適。但找到的第一個空閑區(qū)并非最合適。2022-4-24循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法(Next Fit)(Next Fit)l 循環(huán)首次適應(yīng)

36、算法循環(huán)首次適應(yīng)算法：在分配內(nèi)存空間時，不再在分配內(nèi)存空間時，不再每次從表頭（鏈?zhǔn)祝╅_始查找，而是從上次找每次從表頭（鏈?zhǔn)祝╅_始查找，而是從上次找到的空閑區(qū)的下一個空閑區(qū)開始查找（并采用到的空閑區(qū)的下一個空閑區(qū)開始查找（并采用循環(huán)查找的方式。循環(huán)查找的方式。l 特點(diǎn)：特點(diǎn)：該算法的分配和釋放的時間性能較好，使空閑該算法的分配和釋放的時間性能較好，使空閑分區(qū)分布得更均勻分區(qū)分布得更均勻但較大的空閑分區(qū)不易保留但較大的空閑分區(qū)不易保留最佳適應(yīng)算法最佳適應(yīng)算法p 最佳適應(yīng)算法的空閑區(qū)表按大小升序組織。最佳適應(yīng)算法的空閑區(qū)表按大小升序組織。 缺點(diǎn)：分割后的空閑區(qū)將會很小，直至無法使用，缺點(diǎn)：分割后的空

37、閑區(qū)將會很小，直至無法使用，而造成浪費(fèi)。而造成浪費(fèi)。最壞適應(yīng)算法最壞適應(yīng)算法p 空閑區(qū)按大小降序排列（由大到?。？臻e區(qū)按大小降序排列（由大到?。?。p 分配時總是取表中的第一個表目。分配時總是取表中的第一個表目。p 他的剩余部分稱為新的空閑區(qū)，按大小插入到他的剩余部分稱為新的空閑區(qū)，按大小插入到適當(dāng)位置。適當(dāng)位置。p 若第一個不能滿足申請者的要求，則表示系統(tǒng)若第一個不能滿足申請者的要求，則表示系統(tǒng)中無滿足要求的空閑區(qū)，分配失敗。中無滿足要求的空閑區(qū)，分配失敗。特點(diǎn)：使剩余部分足夠大，可再作分配特點(diǎn)：使剩余部分足夠大，可再作分配; ; 但有時遇到大程序無法裝入內(nèi)存。但有時遇到大程序無法裝入內(nèi)存。

38、 【例例】某時刻系統(tǒng)中有三個空閑區(qū)某時刻系統(tǒng)中有三個空閑區(qū)其大小和首址為：其大小和首址為：(35KB(35KB，100KB)100KB)、(12KB(12KB，156KB)156KB)、(28KB(28KB，200KB)200KB)有一作業(yè)系列：有一作業(yè)系列：(JOB1(JOB1，12KB)12KB)、(JOB2(JOB2，30KB)30KB)、(JOB3(JOB3，28KB)28KB) 分別使用分別使用首次適應(yīng)、最佳適應(yīng)和最壞適應(yīng)首次適應(yīng)、最佳適應(yīng)和最壞適應(yīng)算法對下列作業(yè)進(jìn)行分配，根據(jù)分配的結(jié)果對算法對下列作業(yè)進(jìn)行分配，根據(jù)分配的結(jié)果對這這3 3種算法進(jìn)行比較。種算法進(jìn)行比較。2022-4-

39、243.分配算法框圖申請分配一個u.size大小的分區(qū)從頭開始查表是否檢索完畢？本次無法分配 返回m.sizeu.size m.size-u.sizesize？從該分區(qū)中劃出u.size大小的分區(qū)繼續(xù)檢索下一個表項將該表目以下的所有表目上移一格將該分區(qū)分配給申請者修改有關(guān)的數(shù)據(jù)結(jié)構(gòu) 返 回YNNYY2022-4-24當(dāng)一個進(jìn)程釋放某內(nèi)存區(qū)時，將首先檢查當(dāng)一個進(jìn)程釋放某內(nèi)存區(qū)時，將首先檢查釋放區(qū)是否與其它空閑區(qū)相鄰，釋放區(qū)是否與其它空閑區(qū)相鄰，若相鄰則合并成若相鄰則合并成一個空閑區(qū)，否則，將釋放為一個空閑區(qū)插入空一個空閑區(qū)，否則，將釋放為一個空閑區(qū)插入空閑區(qū)表中的適當(dāng)位置閑區(qū)表中的適當(dāng)位置。 釋

40、放的空閑區(qū)有四種情況：釋放的空閑區(qū)有四種情況：4.回收算法2022-4-24回收算法框圖是否否是是否將該表目以下的所有表將該表目以下的所有表目下移一格，并插入新目下移一格，并插入新釋放的可用區(qū)表目釋放的可用區(qū)表目順序地檢索空閑分區(qū)表順序地檢索空閑分區(qū)表/ /鏈直至找到某表鏈直至找到某表目的目的m.addraam.addraa或或m.size=0m.size=0不是第一個表目與前一空閑區(qū)相 鄰？與后一空閑分區(qū)相鄰且不為空表目？ 把所釋放的空閑區(qū) 與前一分區(qū)合并所釋放的可用區(qū)與后一空閑區(qū)合并所釋放可用區(qū)的size=0?與后一空閑 區(qū) 相鄰？ 與后一可用區(qū)合并將該表目以下的所有表目上移一格 返 回是

41、否返回2022-4-24（4）可重定位分區(qū)分配）可重定位分區(qū)分配1.拼接拼接/ /緊湊緊湊l 在系統(tǒng)不斷地分配和回收中，必定會出現(xiàn)一些不連在系統(tǒng)不斷地分配和回收中，必定會出現(xiàn)一些不連續(xù)的小的空閑區(qū)，稱為續(xù)的小的空閑區(qū)，稱為外碎片外碎片/ /外零頭外零頭。它們每一個。它們每一個都很小，不足以滿足分配要求；但其總和滿足分配都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片。要求。這些空閑塊被稱為碎片。l 解決零頭的方法是解決零頭的方法是拼接拼接（或稱（或稱緊湊緊湊），即向一個方），即向一個方向（例如向低地址端）移動已分配的作業(yè)，使那些向（例如向低地址端）移動已分配的作業(yè)，使那些

42、零散的小空閑區(qū)在另一方向連成一片。零散的小空閑區(qū)在另一方向連成一片。l 分區(qū)的拼接技術(shù)，一方面是要求能夠?qū)ψ鳂I(yè)進(jìn)行重分區(qū)的拼接技術(shù)，一方面是要求能夠?qū)ψ鳂I(yè)進(jìn)行重定位，另一方面系統(tǒng)在拼接時要耗費(fèi)較多的時間。定位，另一方面系統(tǒng)在拼接時要耗費(fèi)較多的時間。2022-4-24緊湊的示意 操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序910KB30KB14KB26KB緊湊前 操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序980KB緊湊后2022-4-24（4）可可重定位分區(qū)分配2. 動態(tài)重定位動態(tài)重定位實(shí)現(xiàn)實(shí)現(xiàn)l 只有具有動態(tài)重定位硬件機(jī)構(gòu)的計算機(jī)系統(tǒng)只有具有動態(tài)重定位硬件機(jī)構(gòu)的計算機(jī)系統(tǒng)，才，才有可能采

43、取動態(tài)重定位可變分區(qū)多道管理技術(shù)，有可能采取動態(tài)重定位可變分區(qū)多道管理技術(shù)，系統(tǒng)的硬件包括重定位寄存器和加法器。系統(tǒng)的硬件包括重定位寄存器和加法器。LOAD1,25003650100250050002500相相 對對 地地 址址10000重重 定定 位位 寄寄 存存 器器LOAD1,250036510000101001250015000作作 業(yè)業(yè) J處處 理理 機(jī)機(jī) 一一 側(cè)側(cè)存存 儲儲 器器 一一 側(cè)側(cè)主主 存存 動態(tài)重定位分區(qū)分配算法，與動態(tài)分區(qū)分配算法基本上相動態(tài)重定位分區(qū)分配算法，與動態(tài)分區(qū)分配算法基本上相同；同； 差別僅在于：在這種分配算法中，增加了差別僅在于：在這種分配算法中，增加

44、了功能，功能，通常是在找不到足夠大的空閑分區(qū)來滿足用戶需求時，進(jìn)行通常是在找不到足夠大的空閑分區(qū)來滿足用戶需求時，進(jìn)行緊湊。緊湊。 2022-4-24動態(tài)重定位分區(qū)分配3動態(tài)重定位分區(qū)分配算法動態(tài)重定位分區(qū)分配算法動態(tài)重定位分區(qū)管理中何時進(jìn)行存儲器緊縮動態(tài)重定位分區(qū)管理中何時進(jìn)行存儲器緊縮? ?l在某個分區(qū)被釋放后立即進(jìn)行緊縮在某個分區(qū)被釋放后立即進(jìn)行緊縮，系統(tǒng)，系統(tǒng)總是只有一個連續(xù)的分區(qū)而無碎片，此法很總是只有一個連續(xù)的分區(qū)而無碎片，此法很花費(fèi)機(jī)時。花費(fèi)機(jī)時。l當(dāng)當(dāng)“請求分配模塊請求分配模塊”找不到足夠大的自由分找不到足夠大的自由分區(qū)分給用戶時區(qū)分給用戶時再進(jìn)行緊縮再進(jìn)行緊縮.l采用此法的動

45、態(tài)重定位分區(qū)分配算法框圖采用此法的動態(tài)重定位分區(qū)分配算法框圖如下：如下：2022-4-24動態(tài)重定位分區(qū)分配算法框圖請求分配請求分配u.size分區(qū)分區(qū)檢索空閑分區(qū)鏈（表）檢索空閑分區(qū)鏈（表）無 法 分無 法 分配配 返返 回回空閑分區(qū)總空閑分區(qū)總和和u.size找 到 大 于找 到 大 于u.size的可用的可用區(qū)否？區(qū)否？ 進(jìn)行緊湊形成進(jìn)行緊湊形成 連續(xù)空閑區(qū)連續(xù)空閑區(qū) 修改有關(guān)的修改有關(guān)的 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 按動態(tài)分區(qū)方式按動態(tài)分區(qū)方式 進(jìn)行分配進(jìn)行分配 修改有關(guān)的修改有關(guān)的 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首址返回分區(qū)號及首址yy2022-4-244.3 覆蓋與交換（1） 覆蓋(overl

46、ay)（2） 交換(swapping)返回2022-4-24（1） 覆蓋(overlay)l 引入：其目標(biāo)是在引入：其目標(biāo)是在較小的可用內(nèi)存中運(yùn)行較大的程序較小的可用內(nèi)存中運(yùn)行較大的程序。常用于多道程序系統(tǒng)，與固定分區(qū)存儲管理配合使用。常用于多道程序系統(tǒng)，與固定分區(qū)存儲管理配合使用。l 原理：一個程序的幾個代碼段或數(shù)據(jù)段占用公共原理：一個程序的幾個代碼段或數(shù)據(jù)段占用公共的內(nèi)存空間。的內(nèi)存空間。將程序的必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)將程序的必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存；存；可選部分（不常用功能）在其他程序模塊中實(shí)現(xiàn)，平可選部分（不常用功能）在其他程序模塊中實(shí)現(xiàn)，平時存放在外存

47、中（覆蓋文件），在需要用到時才裝入時存放在外存中（覆蓋文件），在需要用到時才裝入到內(nèi)存；到內(nèi)存；不存在調(diào)用關(guān)系的模塊不必同時裝入到內(nèi)存，從而可不存在調(diào)用關(guān)系的模塊不必同時裝入到內(nèi)存，從而可以相互覆蓋。以相互覆蓋。( (即不同時用的模塊可共用一個分區(qū)即不同時用的模塊可共用一個分區(qū)) )2022-4-24A20KB50KC30KF30KD20KE40KResident20KOverlay 050KOverlay 140KTotal: 190KTotal: 110K注：另一種覆蓋方法：注：另一種覆蓋方法：(100K)覆蓋技術(shù)覆蓋技術(shù)2022-4-24l缺點(diǎn)：缺點(diǎn)：編程時必須劃分程序模塊和確定程序模塊

48、之編程時必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加編程復(fù)雜度。間的覆蓋關(guān)系，增加編程復(fù)雜度。從外存裝入覆蓋文件，以時間延長來換取空從外存裝入覆蓋文件，以時間延長來換取空間節(jié)省。間節(jié)省。l實(shí)現(xiàn)：函數(shù)庫（操作系統(tǒng)對覆蓋不得實(shí)現(xiàn)：函數(shù)庫（操作系統(tǒng)對覆蓋不得知），或操作系統(tǒng)支持。知），或操作系統(tǒng)支持。返回2022-4-24（2）對換(swapping)l 將將暫時不能執(zhí)行的程序送到外存的交換區(qū)暫時不能執(zhí)行的程序送到外存的交換區(qū)中（換出中（換出swap outswap out），從而獲得空閑內(nèi)存空間。而將外存中），從而獲得空閑內(nèi)存空間。而將外存中由阻塞變?yōu)榫途w的進(jìn)程的地址空間讀入到內(nèi)存中，由阻塞

49、變?yōu)榫途w的進(jìn)程的地址空間讀入到內(nèi)存中，并將該進(jìn)程送到就緒隊列（換入并將該進(jìn)程送到就緒隊列（換入swap inswap in）。）。l 交換單位為整個進(jìn)程的地址空間。常用于多道程序交換單位為整個進(jìn)程的地址空間。常用于多道程序系統(tǒng)或小型分時系統(tǒng)中，與分區(qū)存儲管理配合使用。系統(tǒng)或小型分時系統(tǒng)中，與分區(qū)存儲管理配合使用。程序暫時不能執(zhí)行的可能原因：處于阻塞狀態(tài)，低優(yōu)先級程序暫時不能執(zhí)行的可能原因：處于阻塞狀態(tài)，低優(yōu)先級（確保高優(yōu)先級程序執(zhí)行）；（確保高優(yōu)先級程序執(zhí)行）；2022-4-24l 優(yōu)點(diǎn)：優(yōu)點(diǎn)：增加并發(fā)運(yùn)行的程序數(shù)目增加并發(fā)運(yùn)行的程序數(shù)目。l 缺點(diǎn)：缺點(diǎn)：對換入和換出的控制增加處理機(jī)開銷對換入

50、和換出的控制增加處理機(jī)開銷. l 考慮的問題：考慮的問題：程序換入時的重定位；程序換入時的重定位；減少交換中傳送的信息量，特別是對大程序；減少交換中傳送的信息量，特別是對大程序；返回分區(qū)存儲管理的共享與保護(hù)分區(qū)存儲管理的共享與保護(hù)l常用的存儲保護(hù)方法有常用的存儲保護(hù)方法有3種：種：l1) 上下界寄存器（硬件）；上下界寄存器（硬件）；l2) 存儲保護(hù)鍵法（軟件）；存儲保護(hù)鍵法（軟件）；l3) 兩種措施，或二者兼而有之。兩種措施，或二者兼而有之。1)1)上下界寄存器保護(hù)法上下界寄存器保護(hù)法下界寄存器：下界寄存器：存放程序在內(nèi)存的起始地址存放程序在內(nèi)存的起始地址上界寄存器：上界寄存器：存放程序在內(nèi)存

51、的終止地址存放程序在內(nèi)存的終止地址判別式：判別式：上界寄存器上界寄存器 物理地址物理地址 下界寄存器下界寄存器例：有一程序裝入內(nèi)存的首地址是例：有一程序裝入內(nèi)存的首地址是500，末地，末地址是址是1500，訪問內(nèi)存的邏輯，訪問內(nèi)存的邏輯/虛地址是虛地址是500、345、1010，判斷是否合法。，判斷是否合法。 解：解： 邏輯地址裝入內(nèi)存的首地址邏輯地址裝入內(nèi)存的首地址 物理地址物理地址 1、500500 1000 500 1000 1500（） 2、345500 845 500 845 1500（） 3、1010500 1510 500 1510 1500（）（）2)2)存儲保護(hù)鍵法存儲保護(hù)鍵

52、法l為每個被保護(hù)的存儲塊設(shè)置一個保護(hù)鍵為每個被保護(hù)的存儲塊設(shè)置一個保護(hù)鍵（鎖鎖），在程序狀態(tài)字中提供相應(yīng)的），在程序狀態(tài)字中提供相應(yīng)的keykey值值（鑰匙鑰匙），），OSOS檢查檢查keykey是否與保護(hù)鍵的相匹是否與保護(hù)鍵的相匹配，若匹配或存儲塊未受保護(hù)則可以訪問，配，若匹配或存儲塊未受保護(hù)則可以訪問，否則訪問出錯。否則訪問出錯。l常用保護(hù)方式：常用保護(hù)方式： R R讀保護(hù)（不可讀）讀保護(hù)（不可讀） W W寫保護(hù)（不可寫）寫保護(hù)（不可寫） 2 .程序狀態(tài)字程序狀態(tài)字正確訪問：正確訪問：LOAD A, 5000STORE A, 5200非正確訪問：非正確訪問：LOAD A, 25002022

53、-4-244.4 4.4 頁式存儲管理頁式存儲管理問題的提出問題的提出 分區(qū)存儲管理的主要問題是碎片問題和分區(qū)存儲管理的主要問題是碎片問題和進(jìn)進(jìn)程大小受分區(qū)大小的限制程大小受分區(qū)大小的限制。 造成這個問題的主要原因是用戶程序裝入內(nèi)存時造成這個問題的主要原因是用戶程序裝入內(nèi)存時是是整體裝入整體裝入的，從而出現(xiàn)主存有足夠的空間但由的，從而出現(xiàn)主存有足夠的空間但由于不連續(xù)而導(dǎo)致的不能分配的現(xiàn)象。于不連續(xù)而導(dǎo)致的不能分配的現(xiàn)象。 解決問題的思路：解決問題的思路：程序適應(yīng)主存，程序適應(yīng)主存，將程序分開存放將程序分開存放分頁存分頁存儲管理技術(shù)。儲管理技術(shù)。 頁式存儲管理1。 純分頁純分頁(simple p

54、aging)全部程序裝入內(nèi)存全部程序裝入內(nèi)存1）分頁存儲管理基本原理）分頁存儲管理基本原理2）地址結(jié)構(gòu)）地址結(jié)構(gòu)3）頁表）頁表4）地址變換機(jī)構(gòu)）地址變換機(jī)構(gòu)5）兩級頁表機(jī)制）兩級頁表機(jī)制6）純分頁的特點(diǎn)）純分頁的特點(diǎn)2。 動態(tài)頁式管理動態(tài)頁式管理裝入部分運(yùn)行需要的程序裝入部分運(yùn)行需要的程序1）調(diào)頁策略）調(diào)頁策略 2）置換算法）置換算法2022-4-241。純分頁存儲管理1）分頁存儲管理基本原理分頁存儲管理基本原理q程序分頁：程序分頁：分頁存儲管理是將一個進(jìn)程的分頁存儲管理是將一個進(jìn)程的邏輯地址空間劃分成若干個大小相等的區(qū)邏輯地址空間劃分成若干個大小相等的區(qū)域，稱為域，稱為頁頁。q內(nèi)存分塊：內(nèi)存

55、分塊：將內(nèi)存空間劃分成與頁相同大將內(nèi)存空間劃分成與頁相同大小的若干個物理塊，稱為小的若干個物理塊，稱為塊塊或或頁框頁框。q運(yùn)行時，將進(jìn)程中若干頁分別裝入多個不運(yùn)行時，將進(jìn)程中若干頁分別裝入多個不相鄰接的塊中（所謂相鄰接的塊中（所謂“離散離散” ）。）。2022-4-24FrameNumber0123456789101112131401234567891011121314A.0A.1A.2A.301234567891011121314 A.0 A.1 A.2 A.3B.0B.1B.2t0t1t2分頁存儲管理的內(nèi)存分配過程分頁存儲管理的內(nèi)存分配過程2022-4-240123456789101112

56、1314A.0A.1A.2A.3B.0B.1B.2C.0C.1C.2C.301234567891011121314A.0A.1A.2A.3C.0C.1C.2C.301234567891011121314A.0A.1A.2A.3C.0C.1C.2C.3D.0D.1D.2D.3D.4t3t5t4分頁存儲管理的內(nèi)存分配過程分頁存儲管理的內(nèi)存分配過程進(jìn)程進(jìn)程3進(jìn)程進(jìn)程1進(jìn)程進(jìn)程2進(jìn)程進(jìn)程3進(jìn)程進(jìn)程1進(jìn)程進(jìn)程1進(jìn)程進(jìn)程2進(jìn)程進(jìn)程2進(jìn)程進(jìn)程2頁式存儲管理的內(nèi)存分配示意圖頁式存儲管理的內(nèi)存分配示意圖頁面與頁表頁面與頁表n主存分配q把用戶程序的任一頁分配到內(nèi)存中的任一物理塊，從而實(shí)現(xiàn)非連續(xù)的內(nèi)存分配。n問題q

57、如何管理、如何進(jìn)行地址變換?2022-4-242）頁表作用：保證能在內(nèi)存中找到每個頁面所對應(yīng)作用：保證能在內(nèi)存中找到每個頁面所對應(yīng)的物理塊。實(shí)現(xiàn)從頁號到物理塊號的地址映射。的物理塊。實(shí)現(xiàn)從頁號到物理塊號的地址映射。每個進(jìn)程至少有一個頁表。每個進(jìn)程至少有一個頁表。進(jìn)程在執(zhí)行時，進(jìn)程在執(zhí)行時，通過查找頁表，就可以找到每頁所對應(yīng)的物理通過查找頁表，就可以找到每頁所對應(yīng)的物理塊號。塊號。2022-4-24頁表的作用. 0 2 1 4 2 11 3 13 4 18 5 22 6 2401234561000作業(yè)的作業(yè)的地址空間地址空間頁框頁框（物理塊）（物理塊）頁號頁號頁表頁表主存中頁框主存中頁框（物理塊

58、）（物理塊）1000頁表始址頁表始址1001100210031004100510062022-4-243）地址結(jié)構(gòu)）地址結(jié)構(gòu)頁內(nèi)地址W0111231頁號P分頁系統(tǒng)的地址可以劃分為兩部分：第一部分為分頁系統(tǒng)的地址可以劃分為兩部分：第一部分為頁頁號號P；后一部分為后一部分為位移量位移量W，即即頁內(nèi)地址頁內(nèi)地址。 頁號的位數(shù)決定了所劃分的頁面數(shù)頁號的位數(shù)決定了所劃分的頁面數(shù)頁內(nèi)地址的位數(shù)取決于頁面的大小頁內(nèi)地址的位數(shù)取決于頁面的大小假設(shè)假設(shè)CPUCPU字長為字長為1616位，頁的長度為位，頁的長度為1KB1KB，則地址的分割，則地址的分割為：為：P = A/L W=A MOD L 對某特定機(jī)器其地址

59、結(jié)構(gòu)是一定的。若給定一個邏輯地址對某特定機(jī)器其地址結(jié)構(gòu)是一定的。若給定一個邏輯地址為為A，頁面大小為頁面大小為L，則頁號則頁號P和頁內(nèi)地址和頁內(nèi)地址W可按下式求得：可按下式求得：頁內(nèi)地址W0111231頁號P地址結(jié)構(gòu)地址結(jié)構(gòu)n例：系統(tǒng)頁面大小為1KB，邏輯地址為2170，求頁號與頁內(nèi)偏移量q頁號 P=INT2170/1024=2q頁內(nèi)偏移量d=2170 mod 1024 =122n第0頁 01023n第1頁 10242047n第2頁 20483071q表示為(2,122)2022-4-244）地址變換）地址變換 a） 基本的地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu)l地址變換機(jī)構(gòu)：地址變換機(jī)構(gòu)：2022-

60、4-24b) 地址變換過程：地址變換過程：按頁的大小按頁的大小分離出頁號和頁內(nèi)地址分離出頁號和頁內(nèi)地址，并放入邏輯，并放入邏輯地址寄存器中；再以頁號為索引查找頁表；地址寄存器中；再以頁號為索引查找頁表；將頁號與頁表長度進(jìn)行比較，如果頁號大于頁表將頁號與頁表長度進(jìn)行比較，如果頁號大于頁表長度，則越界中斷；長度，則越界中斷；將頁表始址與頁號和頁表項長度的乘積相加，便將頁表始址與頁號和頁表項長度的乘積相加，便得到該表項在頁表中的位置得到該表項在頁表中的位置，于是可從中得到該，于是可從中得到該頁的物理塊號；頁的物理塊號；將該物理塊號裝入物理地址寄存器的高地址部分；將該物理塊號裝入物理地址寄存器的高地址