第四章 存儲(chǔ)器管理 4.1-4.5

1、第四章 存儲(chǔ)器管理 Memory Management,為多道程序的運(yùn)行提供良好的環(huán)境 提高存儲(chǔ)器的利用率 從邏輯上擴(kuò)充存儲(chǔ)器 存儲(chǔ)共享和保護(hù),4.1 存儲(chǔ)體系4.2 程序的鏈接和裝入 4.3 連續(xù)分配方式 4.4 基本分頁存儲(chǔ)管理方式 4.5 基本分段存儲(chǔ)管理方式 4.6 虛擬存儲(chǔ)器的基本概念 4.7 請(qǐng)求分頁存儲(chǔ)管理方式 4.8 頁面置換算法 4.9 請(qǐng)求分段存儲(chǔ)管理方式,本章主要內(nèi)容,

2、§4.1 存儲(chǔ)體系,§4.1 存儲(chǔ)體系,存儲(chǔ)層次結(jié)構(gòu),無限容量大，速度無限快，價(jià)格便宜。,金錢、性能,,存儲(chǔ)管理,,使主存儲(chǔ)器在成本、速度和規(guī)模之間獲得較好的權(quán)衡。,§4.2 程序的鏈接和裝入Program Linking and Loading,一、用戶程序的主要處理階段 二、程序的裝入 三、程序的鏈接,一、用戶程序的主要處理階段,將一個(gè)用戶程序變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過以下幾步：

3、(1) 編譯(Compiling ) Source code ---> Object Module (2)鏈接(Linking) Object Modules + Library function--->Load Module (3)裝入(Loading) Load Module--->Internal Memory；構(gòu)造PCB，形成進(jìn)程(使用物理地址),庫,圖4-1 對(duì)用戶程序的處理步驟,編譯器只能在

4、一個(gè)模塊內(nèi)部完成符號(hào)名到地址的轉(zhuǎn)換，不同模塊間的符號(hào)解析由鏈接器來完成的。,地址映射,Load A 1200 3456 。 。,1200,物理地址空間,Load A data1data1 3456,源程序,,Load A 200 3456,0,100,200,編譯連接,邏輯地址空間,,,,BA=1000,符號(hào)地址、相對(duì)地址、絕對(duì)地址,基本概念（Basic Concept）,地址映射（重定位）：

5、把邏輯地址空間中使用的邏輯地址變換成內(nèi)存空間中的物理地址的過程。物理地址：內(nèi)存是一塊存儲(chǔ)區(qū)域，存儲(chǔ)單位是字節(jié)（字），每個(gè)字節(jié)都有地址。這種地址稱為物理地址（絕對(duì)地址）。所有的物理地址集合構(gòu)成物理地址空間。邏輯地址：源程序經(jīng)過編譯連接形成可執(zhí)行文件中的地址，通常從0開始，程序中其余指令中的地址都相對(duì)于首地址而編址，這種地址稱為邏輯地址（相對(duì)地址、虛地址）。所有邏輯地址的集合構(gòu)成邏輯地址空間。符號(hào)地址：源程序中用字母和數(shù)字組成的符號(hào)代

6、表存儲(chǔ)器的地址。,二、 程序的裝入Program Loading,一個(gè)程序運(yùn)行裝入到內(nèi)存時(shí)，可有三種裝入方式： (1)絕對(duì)裝入方式 (Absolute Loading Mode) (2)可重定位方式 (Relocatable Loading Mode) (3)動(dòng)態(tài)運(yùn)行時(shí)裝入方式(dynamic Run-Time Loading),1 絕對(duì)裝入方式 (Absolute Loading Mode),由裝入程序根據(jù)裝入模塊中的地

7、址，將程序和數(shù)據(jù)裝入內(nèi)存。裝入模塊的地址是編譯時(shí)由編譯程序產(chǎn)生的，是絕對(duì)地址。裝入程序按裝入模塊裝入內(nèi)存時(shí)，不需修改地址。絕對(duì)地址可由程序員直接給出，或在編譯或匯編時(shí)給出。這種方式要求事先已知程序?qū)⒀b入內(nèi)存的位置。一般只在單道程序的環(huán)境才有可能實(shí)現(xiàn)。 優(yōu)點(diǎn)：裝入過程簡單。 缺點(diǎn)：過于依賴硬件結(jié)構(gòu)，不適于多道程序系統(tǒng)。,例 如：,裝入,2 可重定位裝入方式 (Relocatable Loading Mode),由裝入程序

8、根據(jù)內(nèi)存當(dāng)時(shí)的實(shí)際使用情況，將裝入模塊裝入到內(nèi)存的適當(dāng)?shù)胤健Ｄ繕?biāo)模塊中為相對(duì)地址(邏輯地址) 。裝入模塊中的邏輯地址與實(shí)際裝入內(nèi)存的物理地址不同。裝入內(nèi)存時(shí)，要進(jìn)行 可重定裝入方式采用的靜態(tài)重定位。其地址變換方式為：,物理地址=相對(duì)地址+內(nèi)存起始地址,優(yōu)點(diǎn)：不需硬件支持，可以裝入有限多道程序。 缺點(diǎn)：一個(gè)程序通常需要占用連續(xù)的內(nèi)存空間，程序裝入內(nèi)存后不能移動(dòng)。,重定位,,MOV ax , [2500],,365,

9、,,,,,,,,,0,1000,2500,10000,11000,12500,,MOV ax , [2500],,365,,邏輯空間,內(nèi)存空間,0,[12500],12500 ＝ 10000+2500,物理地址,基地址,相對(duì)地址,例 如：,裝入模塊為相對(duì)地址，在裝入內(nèi)存時(shí)，并不立即變?yōu)槲锢淼刂罚ń^對(duì)地址），即裝入后仍為相對(duì)地址。只有在程序真正執(zhí)行到某一步時(shí)才對(duì)它進(jìn)行地址轉(zhuǎn)換（動(dòng)態(tài)重定位）。 優(yōu)點(diǎn)：OS可以將一個(gè)程序分散存放于不連續(xù)的內(nèi)

10、存空間，可以移動(dòng)程序，有利用實(shí)現(xiàn)共享。 缺點(diǎn)：該方式需要一定特殊硬件的支持，OS實(shí)現(xiàn)較復(fù)雜。,3、動(dòng)態(tài)運(yùn)行時(shí)裝入方式(dynamic Run-Time Loading),是實(shí)現(xiàn)虛擬存儲(chǔ)的基礎(chǔ)。,作業(yè)1,,處理機(jī)一側(cè),存儲(chǔ)器一側(cè),＋,1000,,,500,,例 如：,重定位寄存器,相對(duì)地址,幾個(gè)重要概念Several important concepts,絕對(duì)地址(Absolute Address)、物理地址(Physical A

11、ddress)相對(duì)地址(Relative Address)、邏輯地址(Logical Address)符號(hào)地址(Symbol Address)地址空間(Address Space)、邏輯地址空間存儲(chǔ)空間(storage space )、主存空間、物理地址空間重定位(Relocation):在把程序的目標(biāo)程序裝入到內(nèi)存時(shí)的地址修改過程，即LA-->PA.靜態(tài)重定位(Static Relocation)動(dòng)態(tài)重定位(Dyn

12、amic Relocation),,重定位,概念：程序和數(shù)據(jù)裝入內(nèi)存時(shí)，需要對(duì)目標(biāo)程序中的地址進(jìn)行修改，這種把邏輯地址轉(zhuǎn)換為內(nèi)存物理地址的過程叫做重定位。類型：根據(jù)重定位時(shí)間和技術(shù)的不同，分為：靜態(tài)重定位：程序執(zhí)行前，一次性將該作業(yè)中程序的指令地址和數(shù)據(jù)地址全部轉(zhuǎn)換成絕對(duì)地址，裝入內(nèi)存，且以后不能移動(dòng)。動(dòng)態(tài)重定位：在程序執(zhí)行過程中動(dòng)態(tài)地進(jìn)行地址轉(zhuǎn)換，由地址變換機(jī)構(gòu)（硬件）自動(dòng)執(zhí)行。,三、程序的鏈接Program Linking,

13、源程序經(jīng)過編譯后，可得到一組目標(biāo)模塊，利用鏈接程序?qū)⑦@組目標(biāo)模塊鏈接，形成裝入模塊。鏈接階段產(chǎn)生的可執(zhí)行目標(biāo)程序在不運(yùn)行時(shí)，通常作為一個(gè)二進(jìn)制可執(zhí)行文件駐留在硬盤上。 根據(jù)鏈接時(shí)間的不同，可把鏈接分成如下三種： （1）靜態(tài)鏈接 Static linking （2）裝入時(shí)動(dòng)態(tài)鏈接 Load-time dynamic linking （3）運(yùn)行時(shí)動(dòng)態(tài)鏈接 Ru

14、n-time dynamic linking,在裝入內(nèi)存之前進(jìn)行，鏈接后形成一固定的裝入模塊（也稱為可執(zhí)行程序），不再拆開。,此方式需要解決：1）修改相對(duì)地址。 2）變換外部調(diào)用符號(hào)。,圖 4-4程序靜態(tài)鏈接示意,,printf( “ OK” );,,目標(biāo)模塊1,庫模塊,void printf(…){},0,0,1200H,,printf( “ OK” );,,void printf(…){},裝入模

15、塊,0,call 1200H,1. 靜態(tài)鏈接,,void printf(…){},目標(biāo)模塊在裝入內(nèi)存時(shí)邊裝入邊鏈接。,2.裝入時(shí)動(dòng)態(tài)鏈接,,printf( “ OK” );,,主模塊,庫模塊,void printf(…){},0,0,裝入,,printf( “ OK” );,,21200H,call 21200H,20000H,內(nèi)存,1）便于修改和更新：由于各目標(biāo)模塊分開存放，只需對(duì)要修改的模塊修改后編譯即可，保證所有的

16、軟件同步升級(jí)。,優(yōu) 點(diǎn)：,每次都要鏈接裝入所有的模塊，不論是否用到。 例如：IF THEN S1 ELSE S2;,缺 點(diǎn)：,2）便于實(shí)現(xiàn)目標(biāo)模塊的共享：通常被鏈接的共享代碼稱為動(dòng)態(tài)鏈接庫(DLL, Dynamic-Link Library)或共享庫(shared library)。實(shí)現(xiàn)多個(gè)模塊共享一個(gè)DLL 而不要每個(gè)程序都含有該模塊的拷貝。 3) 便于運(yùn)行環(huán)境適應(yīng)：調(diào)用不同的DLL，就可適應(yīng)多種使用環(huán)境

17、和提供不同功能。如：不同的顯卡只需廠商為其提供特定DLL，而OS和應(yīng)用程序不必修改。,,3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接,,printf( “ OK” );,,,,printf( “ OK” );,,主模塊,庫模塊,void printf(…){},0,0,裝入模塊,void printf(…){},裝入,,printf( “ OK” );,,執(zhí)行,33600H,call 33600H,內(nèi)存,一開始只鏈接裝入部分模塊，在運(yùn)行過程中，若發(fā)

18、現(xiàn)被調(diào)用模塊不在內(nèi)存，則發(fā)出請(qǐng)求，由OS查找、裝入并鏈接到調(diào)用模塊。,通常鏈接和裝入是一體的，其發(fā)展過程可分為三個(gè)階段： 1． 靜態(tài)鏈接、靜態(tài)裝入,2． 靜態(tài)鏈接、動(dòng)態(tài)裝入,3． 動(dòng)態(tài)鏈接、動(dòng)態(tài)裝入,4.3 連續(xù)分配方式 Contiguous Memory Allocation,連續(xù)分配指為用戶程序分配一個(gè)連續(xù)的內(nèi)存空間。,一、單一連續(xù)分配 二、分區(qū)式分配,一、單一連續(xù)分配Single Continuous Allocation

19、,內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。單一連續(xù)分配：內(nèi)存中僅駐留一道程序，整個(gè)用戶區(qū)為一個(gè)用戶獨(dú)占。,適用于單用戶、單任務(wù)的OS。優(yōu)點(diǎn)：簡單，易于管理。缺點(diǎn)：內(nèi)存中只裝入一道作業(yè)運(yùn)行，內(nèi)存空間浪費(fèi)大，資源利用率低。,為了防止OS受到用戶程序有意或無意的破壞，可以設(shè)置保護(hù)機(jī)構(gòu)：如基址(重定位)寄存器和界限寄存器。,內(nèi)存的保護(hù),二、分區(qū)式分配 Partition Allocation,固定分區(qū)分配 動(dòng)態(tài)分區(qū)分配 可重定位分區(qū)分配

20、 伙伴系統(tǒng),為了支持多道程序運(yùn)行，提出了分區(qū)式分配存儲(chǔ)管理方式。該方式中，內(nèi)存用戶區(qū)共多個(gè)用戶程序使用，劃分成若干分區(qū)，每個(gè)分區(qū)容納一個(gè)作業(yè)。按照分區(qū)的劃分和分配方式，常見的分區(qū)式分配有如下幾種：,,1、 固定分區(qū)分配 (Fixed Partition Allocation),1)基本原理：將內(nèi)存空間分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)裝入一道作業(yè)。劃分通常是在系統(tǒng)初使化時(shí)執(zhí)行。,2）劃分分區(qū)的方法 分區(qū)大小相同：主要用于控制多個(gè)相同對(duì)

21、象的場合。即各處理對(duì)象的大小基本相同。 分區(qū)大小不同：一般可劃分多個(gè)小分區(qū)，適量中等分區(qū)，少量大分區(qū)?？蛇m應(yīng)多種類型的作業(yè)。,3） 內(nèi)存分配 數(shù)據(jù)結(jié)構(gòu)：將分區(qū)按大小順序 排列； 建立一張分區(qū)使用表，包含分區(qū)起始地址、大小、狀態(tài)等。 分配過程：有內(nèi)容要裝入時(shí)，在分區(qū)使用表中查找大小能滿足且未分配出去的分區(qū)，若找到，則實(shí)施分配且修改分區(qū)表中的狀態(tài)。否則，拒絕分配。,,,OS(8K),用戶分區(qū)1(16K),用戶分區(qū)2(16K),用戶分區(qū)

22、3(32K),主存分配表,Job1(20K),0,Job1,例 如：,,內(nèi)存中已分配給作業(yè)但未被利用的區(qū)域稱為 “內(nèi)零頭”（ internal fragment ） 固定分區(qū)分配會(huì)有內(nèi)零頭產(chǎn)生。,固定分區(qū)分配方法小結(jié),優(yōu)點(diǎn)：簡單。 缺點(diǎn)： 實(shí)際系統(tǒng)運(yùn)行時(shí)，往往無法預(yù)知分區(qū)大?。ㄌ螅韧凇皢斡脩舴謪^(qū)模式”）； 主存空間利用率仍然較低； 分區(qū)數(shù)目預(yù)先確定，限制了多道運(yùn)行程序的數(shù)量。,如今，幾乎沒有哪一種操作系統(tǒng)支持這種模

23、式。,,2、動(dòng)態(tài)分區(qū)分配（Dynamic Partition Allocation）,在實(shí)現(xiàn)動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理方式時(shí)，必須解決下述三個(gè)問題： 動(dòng)態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)； 分區(qū)分配算法； 分區(qū)的分配和回收。,1）基本原理： 內(nèi)存不預(yù)先劃分好，當(dāng)進(jìn)程裝入時(shí)，根據(jù)進(jìn)程的需求和內(nèi)存空間的使用情況來決定是否分配。 若空間足夠，則按需要?jiǎng)討B(tài)為之分配連續(xù)的內(nèi)存空間； 否則，令其等待主存空間 例如：,1）空閑分區(qū)表：用表記錄內(nèi)

24、存中的所有空閑分區(qū)。每一分區(qū)占一表目?？砂ㄐ蛱?hào)、大小、始址等。 2）空閑分區(qū)鏈：用鏈方式記錄每一空閑分區(qū)。鏈上每一分區(qū)中存儲(chǔ)有指向前后分區(qū)的指針及本分區(qū)的大小、狀態(tài)（0表示可用，1表示已用）。,2) 動(dòng)態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 系統(tǒng)必須記錄內(nèi)存的使用情況，為分配提供依據(jù)。,,空閑分區(qū)鏈結(jié)點(diǎn)示意圖,空閑分區(qū)表,空閑分區(qū)鏈,3） 動(dòng)態(tài)分區(qū)分配算法,將作業(yè)裝入內(nèi)存時(shí)，選擇哪個(gè)的內(nèi)存分區(qū)進(jìn)行分配。常用的算法有如下幾種：,首次適應(yīng)算

25、法（First-Fit Algorithm ） 循環(huán)首次適應(yīng)算法（Next-fit Algorithm ） 最佳適應(yīng)算法（Best-fit Algorithm ） 最壞適應(yīng)算法（Worst-fit Algorithm ） 快速適應(yīng)算法（Quick-fit Algorithm ） （作業(yè)）,Ⅰ. 首次適應(yīng)算法（First-Fit Algorithm ）,要求：空閑分區(qū)以地址遞增的次序鏈接。 分配：從鏈?zhǔn)醉樞虿檎遥敝琳业揭粋€(gè)能

26、滿足大小的空閑分區(qū)為止。按需要對(duì)其進(jìn)行劃分，分配、保留。例： 傾向：利用低址分區(qū)。 優(yōu)點(diǎn)：分區(qū)組織簡單；高址部分可容納大作業(yè)。 缺點(diǎn)：低址處外零頭（external fragment）多，查找越來越困難。,空閑分區(qū)表,解：按首次適應(yīng)算法， 申請(qǐng)作業(yè)100k，分配3號(hào)分區(qū)，剩下分區(qū)為20k，起始地址160K ；,例 如： 系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及7K。給出按首次適應(yīng)

27、算法的內(nèi)存分配情況及分配后空閑分區(qū)表。,20k,160k,申請(qǐng)作業(yè)30k， 分配1號(hào)分區(qū)，剩下分區(qū)為2k，起始地址50K ；,申請(qǐng)作業(yè)7k， 分配2號(hào)分區(qū)，剩下分區(qū)為1k，起始地址59K ；,2k,50k,1k,59k,,,,,,作業(yè)1,作業(yè)2,作業(yè)3,作業(yè)4,,,,2,3,4,,1,,0,,0,,1,,0,,2,3,4,1,5,0,在低地址部分會(huì)積累大量外零頭,,0,2,3,4,5,1,要求：空閑分區(qū)以地址遞增的次序鏈接；且做

28、成環(huán)形。設(shè)置一個(gè)起始查尋指針。 分配：從上次找到的空閑分區(qū)的下一個(gè)分區(qū)開始查找，直至找到一個(gè)能滿足大小要求的空閑分區(qū)。劃分。例： 傾向：平衡利用內(nèi)存。 優(yōu)點(diǎn)：空閑分區(qū)組織簡單；查找簡單。 缺點(diǎn)：無大的空閑分區(qū)，難滿足大作業(yè)的要求。,Ⅱ. 循環(huán)首次適應(yīng)算法（Next-fit Algorithm ）,空閑分區(qū)表,解：按循環(huán)首次適應(yīng)算法， 申請(qǐng)作業(yè)100k，分配3號(hào)分區(qū)，剩下分區(qū)為20k，起始地址160K ；,

29、例 如： 系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及7K。給出按循環(huán)首次適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。,20k,160k,申請(qǐng)作業(yè)30k， 分配4號(hào)分區(qū)，剩下分區(qū)為301k，起始地址210K ；,申請(qǐng)作業(yè)7k， 分配1號(hào)分區(qū)，剩下分區(qū)為25k，起始地址27K ；,25k,27k,301k,210k,Ⅲ. 最佳適應(yīng)算法（Best-fit Algorithm ）,要求：空閑分

30、區(qū)按大小從小到大進(jìn)行鏈接。 分配：從鏈表頭進(jìn)行順序查找，直至第一個(gè)大小能滿足的分區(qū)。則為能滿足且最接近需要大小的分區(qū)。劃分。 例如： 優(yōu)點(diǎn)：避免“大材小用”。 缺點(diǎn)：外零頭嚴(yán)重；分區(qū)組織、回收復(fù)雜。,空閑分區(qū)表,解：按最佳適應(yīng)算法， 申請(qǐng)作業(yè)100k，分配3號(hào)分區(qū)，剩下分區(qū)為20k，起始地址160K ；,例如 ： 系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30

31、K及7K。給出按最佳適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。,申請(qǐng)作業(yè)30k， 分配3號(hào)分區(qū)，剩下分區(qū)為2k，起始地址50K ；,申請(qǐng)作業(yè)7k， 分配2號(hào)分區(qū)，剩下分區(qū)為1k，起始地址59K ；,20k,160k,2k,50k,59k,1k,2k,50k,1k,59k,要求：空閑分區(qū)按從大到小鏈接。 分配：從頭順序查找，找到大小能滿足的。則為能滿足且劃分后剩余空間最大的分區(qū)。劃分。 例如： 優(yōu)點(diǎn)：外零

32、頭較少。 缺點(diǎn)：難滿足大作業(yè)的要求；分區(qū)組織、空閑分區(qū)回收復(fù)雜。,Ⅳ. 最壞適應(yīng)算法（Worst-fit Algorithm）,空閑分區(qū)表,例 如： 系統(tǒng)中的空閑分區(qū)表如下，現(xiàn)有三個(gè)作業(yè)分配申請(qǐng)內(nèi)存空間100K、30K及7K。給出按最壞適應(yīng)算法的內(nèi)存分配情況及分配后空閑分區(qū)表。,解：按最壞適應(yīng)算法， 申請(qǐng)作業(yè)100k，分配1號(hào)分區(qū)，剩下分區(qū)為231k，起始地址280K ；,申請(qǐng)作業(yè)30k， 分配1號(hào)分

33、區(qū)，剩下分區(qū)為201k，起始地址310K ；,申請(qǐng)作業(yè)7k， 分配1號(hào)分區(qū)，剩下分區(qū)為194k，起始地址317K ；,231k,280k,201k,310k,194k,317k,分區(qū)分配算法的性能看其時(shí)間、空間復(fù)雜性而定。就算法本身來說，它們的復(fù)雜性由排序（地址大小、空閑區(qū)大?。┖筒檎遥ú檎宜枳杂蓞^(qū)）兩項(xiàng)決定。 搜索速度：FF最佳。BF或WF要求按空間大小進(jìn)行排序，因此速度較慢。 回收過程：FF最佳，因?yàn)镕F算法回收時(shí)不

34、用改變空閑區(qū)位置，只需修改大小和起始地址。 空閑區(qū)：BF最佳。但某些情況下會(huì)降低內(nèi)存利用率。 碎片：WF基于不留碎片空間為出發(fā)點(diǎn)。,FF\BF\WF三種算法比較,上述三種分配算法各有利弊，好壞不能一概而論，應(yīng)針對(duì)具體作業(yè)序列來分析。 對(duì)某作業(yè)序列來說，若某算法能將該作業(yè)中所有作業(yè)安置完畢，則稱該算法對(duì)這一作業(yè)序列是合適的。 對(duì)某一算法而言，若不能立即滿足作業(yè)序列的某一要求，則該算法對(duì)該作業(yè)序列是不合適的。,FF算法以其簡單、

35、快速特性，在實(shí)際的操作系統(tǒng)中用得較多；其次是最佳適應(yīng)算法。,FF\BF\WF三種算法比較（續(xù)）,動(dòng)態(tài)分區(qū)管理方式中，主要操作是內(nèi)存分配和回收。 Ⅰ. 分配內(nèi)存 (Memory Allocation) ① 按某種算法根據(jù)請(qǐng)求的大小，在表或鏈中進(jìn)行查找合適空閑區(qū)； ② 找不到則結(jié)束；找到則劃分。為減少外零頭，可設(shè)一下限。若劃分后零頭小于該下限，則不劃分直接分配。 ③修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。 u.size: 請(qǐng)求的分

36、區(qū)大小； m.size: 表中每個(gè)空閑分區(qū)的大?。?size: 事先規(guī)定的不再切割的剩余分區(qū)的大小。,4）動(dòng)態(tài)分區(qū)的分配和回收,按照分區(qū)分配算法,在空閑分區(qū)中查詢,m.size – u.size>size？,m.size:空閑區(qū)大小u.size:請(qǐng)求分區(qū)大小size:分區(qū)大小下限,m.size=m.size–u.size,將分區(qū)分配給用戶，從空閑分區(qū)表（鏈）中移出,查找下一個(gè),,,,,,N,Y,內(nèi)存分配過程

37、,m.size >u.size？,檢索完否？,m分區(qū)整塊分配給u,,,,,N,Y,,,N,返回,可能形成外零頭,存在內(nèi)零頭,按照分區(qū)分配算法,Y,當(dāng)內(nèi)存運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)回收區(qū)的首址在相應(yīng)的數(shù)據(jù)結(jié)構(gòu)中查找插入點(diǎn)。 此時(shí)可能出現(xiàn)四種情況之一： ① 回收區(qū)上鄰接一個(gè)空閑分區(qū)：合并、改大小。 ② 回收區(qū)下鄰接一個(gè)空閑分區(qū)相鄰：合并、改始址、大小。 ③ 回收區(qū)上下鄰接區(qū)相鄰：合并、共用上空閑分區(qū)

38、首址、改大小、取消下空閑分區(qū)。 ④ 回收區(qū)不鄰接空閑分區(qū)：單獨(dú)建一表項(xiàng)。,Ⅱ. 回收內(nèi)存 (Return Memory),回收內(nèi)存舉例,P1運(yùn)行結(jié)束,,P3運(yùn)行結(jié)束,,P1所占分區(qū)的上下都不空閑，在空閑分區(qū)鏈中添加一項(xiàng),P3所占分區(qū)下邊的分區(qū)F1空閑，應(yīng)進(jìn)行合并。在空閑分區(qū)鏈中找到F1節(jié)點(diǎn)，修改其起始地址和長度,,P2運(yùn)行結(jié)束,P2所占分區(qū)上邊的分區(qū)F1空閑，應(yīng)進(jìn)行合并。在空閑鏈表中找到F1節(jié)點(diǎn)，修改其長度,P2,P1,P3,F

39、1,F2,P1運(yùn)行結(jié)束,,P1所占分區(qū)上下邊的分區(qū)F1和F2都空閑，應(yīng)進(jìn)行合并。在空閑鏈表中找到F1節(jié)點(diǎn)，修改其長度為F1、F2和P2所占分區(qū)的長度和。刪除F2節(jié)點(diǎn),,動(dòng)態(tài)分區(qū)分配舉例：,某計(jì)算機(jī)有2560K內(nèi)存，采用可變分區(qū)模式管理內(nèi)存，操作系統(tǒng)占用低地址的400K空間，剩余2160K的空間為用戶區(qū)。分區(qū)分配采用首次適應(yīng)算法。最初整個(gè)用戶區(qū)為空閑，即只有一個(gè)分區(qū)。隨著用戶程序的創(chuàng)建和撤銷，分區(qū)的個(gè)數(shù)和大小位置開始變化。 分配回收過

40、程如下所示：,內(nèi)存的初始狀態(tài),1000K,1560K,P1，600K,P1來，600K,P2來，1000K,560K,2000K,P2，1000K,P3來，300K,2300K,260K,P2結(jié)束,1000K,P4來，700K,1700K,P4，700K,300K,P3，300K,P1結(jié)束,600K,P5來，500K,900K,100K,P5，500K,P4結(jié)束,1100K,,3、可重定位分區(qū)分配Relocatable partiti

41、on allocation,1 ）引入,緊湊：將內(nèi)存中的作業(yè)進(jìn)行移動(dòng)，使它們相鄰接，將分散的小分區(qū)拼接成一個(gè)大分區(qū)，從而利于作業(yè)的裝入。（以時(shí)間換空間）,動(dòng)態(tài)分區(qū)分配中，經(jīng)多次劃分后，常會(huì)出現(xiàn)大量的太小而無法利用的區(qū)域（外零頭）。為了充分利用內(nèi)存空間，可采用緊湊（compaction）技術(shù)。,緊湊后的作業(yè)在內(nèi)存中位置發(fā)生了變化，則應(yīng)對(duì)其中程序、數(shù)據(jù)等的地址做相應(yīng)的修改，即重定位。,,P1,10K,P3,(a),P7,P8,操作系統(tǒng),15

42、K,30K,,P1,10K,P3,P8,操作系統(tǒng),15K,25K,30K,P7,55K,(b),(a)緊湊前; (b)緊湊后,2） 動(dòng)態(tài)重定位的實(shí)現(xiàn)The implementation of dynamic Relocation,為支持作業(yè)在內(nèi)存中的移動(dòng)，應(yīng)采用動(dòng)態(tài)運(yùn)行時(shí)裝入方式。因此，允許作業(yè)在運(yùn)行過程中在內(nèi)存中移動(dòng)的技術(shù)，必須獲得硬件地址變換機(jī)構(gòu)的支持。在系統(tǒng)中設(shè)置一個(gè)重定位寄存器 。用于存放作業(yè)在內(nèi)存中的起始地址。運(yùn)

43、行時(shí)，相對(duì)地址執(zhí)行： 物理地址=重定位寄存器+相對(duì)地址 得到它在內(nèi)存中的實(shí)際地址。如圖所示.,緊湊時(shí)，只需修改重定位寄存器值，使之存放新起始地址。,3） 可重定位分區(qū)分配算法 Dynamic Relocation Partition Allocation Algorithm,修改有關(guān)的數(shù)據(jù)結(jié)構(gòu),檢索空閑分區(qū)鏈(表),進(jìn)行緊湊形成連續(xù)空閑區(qū),修改有關(guān)的數(shù)據(jù)結(jié)構(gòu),按動(dòng)態(tài)分區(qū)方式進(jìn)行分配,找到大于u.size

44、的可用區(qū)否?,空閑分區(qū)總和>u.size?,返回分區(qū)號(hào)及首址,無法分配返回,請(qǐng)求分配u.size分區(qū),,否,,否,,是,,,,,,,,,,,是,動(dòng)態(tài)分區(qū)分配算法流程,可重定位分區(qū)分配小結(jié),☆ 進(jìn)程結(jié)束，釋放分區(qū)時(shí)，如不與空閑區(qū)相鄰，則緊湊，保持空閑區(qū)連續(xù)，花費(fèi)多。,☆ 分配進(jìn)程分區(qū)時(shí)，若不滿足，則緊湊?？臻e區(qū)管理復(fù)雜。,優(yōu)點(diǎn): 消除內(nèi)存碎片，提高內(nèi)存利用率。 缺點(diǎn): 提高硬件成本。 緊湊時(shí)花費(fèi)CPU時(shí)間，開銷大。

45、 緊湊的時(shí)機(jī),,4. 伙伴系統(tǒng)（Buddy System）,固定分區(qū)和動(dòng)態(tài)分區(qū)方式都有不足之處。伙伴系統(tǒng)方式是對(duì)以上兩種內(nèi)存方式的一種折衷方案。伙伴系統(tǒng)規(guī)定： 1）內(nèi)存分區(qū)大小均為2的k次冪，k為整數(shù)(l≤k≤m)，其中：21表示分配的最小分區(qū)的大小，2m表示最大分區(qū)的大小，通常為系統(tǒng)開始運(yùn)行時(shí)可分配內(nèi)存的大小。 2） 該方法通過不斷劃分大的空閑區(qū)來獲得小的空閑區(qū)，直到獲得所需內(nèi)存塊。空閑塊的分配和合并均使用2的冪次方算法。

46、3）當(dāng)一個(gè)空閑塊被對(duì)分后，其中一部分稱為另一部分的伙伴。,伙伴系統(tǒng)空閑塊的組織,空閑分區(qū)根據(jù)分區(qū)的大小進(jìn)行分類，對(duì)于每一類具有相同大小的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)雙向鏈表。這樣，不同大小的空閑分區(qū)形成了k(0≤k≤m)個(gè)空閑分區(qū)鏈表。,伙伴系統(tǒng)內(nèi)存的分配和回收,1M block,1M,Request 100K,512K,256K,128K,A=128K,128K,Request 240K,A=128K,128K,256K,512

47、K,B=256K,Request 64K,A=128K,128K,64K,64K,B=256K,C=64,Request 256K,A=128K,512K,C=64K,64K,B=256K,256K,256K,D=256K,Releset B,A=128K,C=64K,64K,B=256K,256K,D=256K,256K,Releset A,A=128K,B=256K,128K,C=64K,64K,256K,D=256K,256K,5

48、12K,Request 75K,B=256K,128K,E=128K,C=64K,64K,256K,D=256K,256K,Releset C,E=128K,C=64K,64K,64K,Releset E,128K,128K,256K,256K,512K,256K,512K,D=256K,Releset D,256K,256K,512K,1M,伙伴系統(tǒng)內(nèi)存的分配和回收（續(xù)）,伙伴系統(tǒng)小結(jié),Easy to partition Eas

49、y to combine Internal fragmentation existing，No external fragmentation The buddy system is used for Linux kernel memory allocation.,在內(nèi)存分區(qū)分配中考慮兩個(gè)問題：,1、若進(jìn)程在運(yùn)行過程中長度發(fā)生變化。 則如果鄰接內(nèi)存區(qū)域?yàn)榭瞻?，可再分配。若鄰接為一進(jìn)程，則需要移動(dòng)、等待、交換或撤銷。

50、2、作業(yè)調(diào)度時(shí)內(nèi)存空間是否滿足。 因此，作業(yè)調(diào)度算法應(yīng)同分區(qū)內(nèi)存管理相結(jié)合。即在考慮調(diào)度順利時(shí)，還要考慮到內(nèi)存空間是否能滿足。,例 如：,作業(yè)到來次序 所需存儲(chǔ)量 運(yùn)行時(shí)間,1 60KB 10s,2 100KB 5s,3

51、 30KB 20s,4 70KB 8s,5 50KB 15s,OS,,,0 39 40 256,J1,J2

52、,J3,,,26K,100K,J4,30K,60K,J5,10K,,110K,,,主存總?cè)萘繛?57K，OS占40K。系統(tǒng)采用FCFS作業(yè)調(diào)度，進(jìn)程調(diào)度采用時(shí)間片(5s)輪轉(zhuǎn)。,216K,,三、對(duì)換（Swapping ）,,1. 對(duì)換的引入（Introduction of Swapping ）,,對(duì)換：把內(nèi)存中暫不能運(yùn)行的進(jìn)程或暫不用的程序、數(shù)據(jù)換到外存，以騰出足夠內(nèi)存空間，把已具備運(yùn)行條件的進(jìn)程，或進(jìn)程所需要的程序和數(shù)據(jù)，換入內(nèi)存。

53、,原因：多道程序環(huán)境下，內(nèi)存中某些進(jìn)程占據(jù)大量內(nèi)存空間但無法運(yùn)行，而外存中尚有許多作業(yè)，因無內(nèi)存而不能運(yùn)行。,對(duì)換是提高內(nèi)存的利用率的有效措施。,原因：1、處于阻塞狀態(tài) 2、低優(yōu)先級(jí)（確保高優(yōu)先級(jí)進(jìn)程運(yùn)行） 3、時(shí)間片用完,暫停執(zhí)行內(nèi)存中的進(jìn)程，將要換出的進(jìn)程的地址空間保存到外存的對(duì)換區(qū)中（換出），而將外存中由阻塞變?yōu)榫途w的進(jìn)程的地址空間讀入內(nèi)存，并將該進(jìn)程送到就緒隊(duì)列（換入）。,原理：,

54、1）“整體對(duì)換”或“進(jìn)程對(duì)換”。對(duì)換以整個(gè)進(jìn)程為單位，用于分時(shí)系統(tǒng)，以解決內(nèi)存緊張，提高內(nèi)存利用率。 2） “頁面對(duì)換”或“分段對(duì)換”。對(duì)換以“頁”或“段”為單位進(jìn)行“部分對(duì)換”。支持虛存系統(tǒng)。,√,可在系統(tǒng)中設(shè)一對(duì)換進(jìn)程，以執(zhí)行換進(jìn)內(nèi)存、換出至外存操作。,實(shí)現(xiàn)：,對(duì)換是系統(tǒng)行為,分類：,系統(tǒng)提供的功能：,對(duì)換空間的管理（Management of Swapping Space） 進(jìn)程的換入（Swap in of Process

55、） 進(jìn)程的換出（Swap out of Process ）,為實(shí)現(xiàn)對(duì)換，系統(tǒng)需要三方面的功能：,,引入對(duì)換后， 外存被分為兩部分：文件區(qū)和對(duì)換區(qū)。 文件區(qū)：用于存放文件，其管理目標(biāo)為提高存儲(chǔ)空間的利用率。因此采取離散分配方式。,對(duì)換區(qū)：存放從內(nèi)存換出的進(jìn)程，它們在外存的存放時(shí)間較短，換入、換出頻繁。其管理目標(biāo)為提高進(jìn)程換入換出的速度。因此采用連續(xù)分配方式。,即一個(gè)文件可根據(jù)當(dāng)前外存的使用情況，被分成多塊，分別存到不鄰接的多個(gè)內(nèi)

56、存存儲(chǔ)區(qū)域中。,即把一個(gè)換出的進(jìn)程存放到一個(gè)連續(xù)的存儲(chǔ)空間中。,2. 對(duì)換空間的管理（Management of Swapping Space）,對(duì)對(duì)換區(qū)的管理類似于內(nèi)存的動(dòng)態(tài)分區(qū)分配方式。,,進(jìn)程的換入和換出由對(duì)換進(jìn)程完成。(1) 進(jìn)程的換出實(shí)質(zhì)：把活動(dòng)阻塞、就緒狀態(tài)的進(jìn)程轉(zhuǎn)掛起狀態(tài)。步驟：換出過程分以下兩步：step1. 選擇被換出的進(jìn)程 處于阻塞狀態(tài)的、優(yōu)先級(jí)最低的進(jìn)程。 無阻塞：選擇優(yōu)先級(jí)低的就緒進(jìn)程。 考慮優(yōu)

57、先級(jí)低產(chǎn)生“換進(jìn)、再換出”，兼顧內(nèi)存駐留時(shí)間。 非共享的程序和數(shù)據(jù)段。若為共享，只能引用數(shù)為零后才能被換出。,3. 進(jìn)程的換入與換出（Swap in and Swap out of Process ）,step2. 換出過程 ①申請(qǐng)對(duì)換空間，成功則執(zhí)行②，否則，重新選擇； ②將程序和數(shù)據(jù)寫入對(duì)換區(qū)，檢查寫入的正確性； ③無誤，則調(diào)用釋放內(nèi)存過程，釋放原內(nèi)存； ④修改PCB、內(nèi)存分配表等； ⑤若內(nèi)存仍不足或仍有可換

58、出進(jìn)程，則回到①,(2) 進(jìn)程的換入實(shí)質(zhì)：把掛起狀態(tài)->活動(dòng)就緒或阻塞。步驟：換入過程分以下兩步：,step2. 換入過程 ①從 PCB集合中查找“就緒且換出”的進(jìn)程，有多個(gè)，則選擇換出時(shí)間最長的。 ②根據(jù)進(jìn)程大小申請(qǐng)內(nèi)存，成功則讀入，否則要先執(zhí)行換出，再換入。 ③若還有可換入進(jìn)程，則轉(zhuǎn)向①。直至無“就緒且換出”進(jìn)程或無法獲得足夠內(nèi)存空間為止。,step1. 選擇換入進(jìn)程 有足夠的內(nèi)存空間； “就緒掛起”優(yōu)先于“阻

59、塞掛起”； 同一隊(duì)列中，優(yōu)先級(jí)高、掛起時(shí)間長的優(yōu)先換入。,離散內(nèi)存分配方式,把用戶的程序空間劃分成若干部分（化整為零），它們可以離散分配到內(nèi)存中非連續(xù)的存儲(chǔ)區(qū)域中，充分利用內(nèi)存。即離散分配方式。 根據(jù)程序劃分時(shí)的基本單位不同，可分為三種：,基本分頁存儲(chǔ)管理方式 基本分段存儲(chǔ)管理方式 段頁式存儲(chǔ)管 理方式,4.4 基本分頁存儲(chǔ)管理方式Basic Paged Memory Management,一、基本分頁存儲(chǔ)

60、管理原理 二、基本概念 三、內(nèi)存分配和回收 四、地址變換 五、兩級(jí)和多級(jí)頁表,一、基本分頁存儲(chǔ)管理原理,將程序的邏輯地址空間劃分為固定大小的頁（頁面）(page or page frame)；將物理內(nèi)存劃分為與頁面大小相等的物理塊（block）；程序加載時(shí)，按頁分配其所需的塊，連續(xù)頁面所分得物理塊不必連續(xù)。需要CPU的硬件支持。,內(nèi)存,第2頁,第1頁,第4頁,第3頁,第5頁,,,用戶作業(yè),02K-1,第2頁（頁長2

61、K）,,,02K-1,4號(hào)塊（塊長2K）,,,頁內(nèi)碎片,第0頁,基本分頁存儲(chǔ)管理示意圖,把用戶程序的邏輯地址空間劃分成若干大小相等的“頁”，各頁從0開始依次編頁號(hào)0，1，2，……。 頁內(nèi)地址相對(duì)于0編址。因此，分頁系統(tǒng)中，每個(gè)邏輯地址都可用二元組（頁號(hào)，頁內(nèi)地址）表示。,二、 基本概念（Basic Concept）,把內(nèi)存空間劃分成若干和“頁”大小相同的塊，稱為物理塊(Block)或頁框(frame)。同樣為它

62、們編號(hào)0，1……。物理地址同樣用二元組（塊號(hào)，塊內(nèi)地址）表示。,,2. 頁面大小（ Page Size）,分頁系統(tǒng)中頁面大小由機(jī)器地址結(jié)構(gòu)決定，因此，機(jī)器的頁面大小固定。用戶程序頁面劃分由系統(tǒng)自動(dòng)完成，一般為2的整數(shù)次冪。例如，IBM AS/400的頁面大小為512B。小頁面 優(yōu)點(diǎn)：減少碎片，提高內(nèi)存利用率。 缺點(diǎn)：頁表過長，占用較多內(nèi)存空間。且以頁為單位進(jìn)行換進(jìn)、換出時(shí)效率低。大頁面優(yōu)點(diǎn)：頁表小，換進(jìn)換出時(shí)效率高。缺點(diǎn)：頁

63、內(nèi)碎片相應(yīng)較大。頁面的大小通常在512B~4KB之間。,,3. 邏輯地址形式（Logic Address）,在分頁存儲(chǔ)管理方式中，程序經(jīng)過頁面劃分后，任一個(gè)邏輯地址都可轉(zhuǎn)變 （頁號(hào)，頁內(nèi)位移量）。,如：一個(gè)32位的邏輯地址，可轉(zhuǎn)化為如下方式：,例如：有邏輯地址為：2170，頁面大小為1KB，則 P=INT[2170/1024]=2； W=2170 MOD 1024=122,邏輯地址A，在分頁存儲(chǔ)管理方式中，需

64、要被轉(zhuǎn)換成（頁號(hào)，頁內(nèi)偏移）二元組地址形式。若頁面大小為L，則轉(zhuǎn)換過程為：,邏輯地址轉(zhuǎn)換過程：,頁號(hào) P=INT[A/L]；頁內(nèi)位移量 W=A MOD L,若邏輯地址為二進(jìn)制呢？,變換通常由系統(tǒng)中的某些硬件完成（MMU，內(nèi)存管理單元）,設(shè)有一頁式存儲(chǔ)管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁，每頁2048字節(jié)，內(nèi)存總共有8個(gè)存儲(chǔ)塊，試問邏輯地址至少應(yīng)為多少位？內(nèi)存空間有多大？,問？,三、內(nèi)存的分配與回收 Memory Allo

65、cation and Return,1.數(shù)據(jù)結(jié)構(gòu)（Data Structer）,作用：描述進(jìn)程頁面存放在內(nèi)存中所對(duì)應(yīng)的物理塊。 內(nèi)容：頁表中主要包括頁號(hào)、物理塊號(hào)。還可有存取控制字段，實(shí)現(xiàn)對(duì)存儲(chǔ)塊中內(nèi)容的保護(hù)。如： 注意：每個(gè)進(jìn)程一個(gè)頁表。全部頁表集中存放在內(nèi)存的系統(tǒng)專用區(qū)中，只有系統(tǒng)有權(quán)訪問頁表，保證安全。例：,1）進(jìn)程頁表/頁表（Page Table）,3）空閑塊表：記錄內(nèi)存當(dāng)前空閑塊，全系統(tǒng)1張。,2）虛空間表(作業(yè)表)：

66、記錄進(jìn)程空間的情況。一個(gè)進(jìn)程一個(gè)表項(xiàng)。記錄進(jìn)程頁表在內(nèi)存的存放情況。全系統(tǒng)僅1張。,1、進(jìn)程頁表放在哪兒？2、進(jìn)程頁表的首地址和長度放在哪兒？,問？,內(nèi)存,進(jìn)程PCB,,2. 內(nèi)存分配過程 (Memory Allocation),,3. 內(nèi)存回收過程(Memory Return),根據(jù)進(jìn)程頁表的內(nèi)容，把空閑塊表中對(duì)應(yīng)的物理頁改為空閑； 撤銷該進(jìn)程的進(jìn)程頁表。,四、地址變換Address Transform Mechanism,功

67、能：將邏輯地址轉(zhuǎn)變?yōu)槲锢淼刂贰?頁號(hào)到物理塊號(hào)的轉(zhuǎn)換，借助頁表。,進(jìn)程頁表,頁號(hào) 塊號(hào),,,>＝,,,,,,,,,越界中斷,,,6,87,1. 基本地址變換機(jī)構(gòu)(Basic Address Transform Mechanism ),分頁系統(tǒng)的地址變換機(jī)構(gòu)示意圖,1）分頁地址變換機(jī)構(gòu)將相對(duì)地址分為（頁號(hào)，頁內(nèi)地址）； 2）讀取PTR中的頁表長度。 IF 頁號(hào)<頁表長度 THEN GOTO 3）ELSE

68、越界中斷； 3）讀取PTR中的頁表始址，計(jì)算： 頁表始址+頁號(hào)×頁表項(xiàng)長度 得到該頁表項(xiàng)在頁表中的位置，對(duì)應(yīng)得到該頁的物理塊號(hào)。裝入物理地址寄存器。 4）將邏輯地址中的頁內(nèi)地址送入物理地址寄存器的塊內(nèi)地址字段，拼接，得到最后的物理地址。例如,地址變換過程,要解決的問題,主要考慮兩個(gè)問題： 加速邏輯地址到物理地址的變換問題； 大頁表問題。如果邏輯地址空間很大，頁表也會(huì)很大。現(xiàn)代