操作系統(tǒng)-ch4

1、第第4 4章章 存儲器管理存儲器管理14.1 存儲器管理概述存儲器管理概述4.2 程序的裝入和鏈接程序的裝入和鏈接4.3 連續(xù)分配方式連續(xù)分配方式4.4 基本分頁存儲管理方式基本分頁存儲管理方式4.5 基本分段存儲管理方式基本分段存儲管理方式4.6 虛擬存儲器的基本概念虛擬存儲器的基本概念4.7 請求分頁存儲管理方式請求分頁存儲管理方式4.8 頁面置換算法頁面置換算法4.9 請求分段存儲管理方式請求分段存儲管理方式4.1 存儲器管理概述 1. 內(nèi)存分配 (內(nèi)存分配數(shù)據(jù)結(jié)構(gòu)、內(nèi)存分配功能(算法)、內(nèi)存回收功能 )2. 內(nèi)存保護(hù) (硬件檢查越界，軟件中斷處理)3. 地址映射 (邏輯、物理地址，硬件

2、支持)4. 內(nèi)存擴(kuò)充 (虛擬存儲技術(shù))2存儲器管理應(yīng)具有以下功能：存儲器管理應(yīng)具有以下功能： 本章按這一思路展開討論本章按這一思路展開討論對各種存儲分配管理對各種存儲分配管理方式，介紹它們的內(nèi)存分配、方式，介紹它們的內(nèi)存分配、內(nèi)存保護(hù)、地址映射內(nèi)存保護(hù)、地址映射和內(nèi)存擴(kuò)充等和內(nèi)存擴(kuò)充等知識。知識。4.1.1 存儲分配（管理）方式分區(qū)管理方式分頁（頁式）存儲管理方式 分段（段式）存儲管理方式段頁式存儲管理方式 虛擬存儲器請求分頁存儲管理方式請求分段存儲管理方式 3固定分區(qū)分配固定分區(qū)分配 動態(tài)分區(qū)分配動態(tài)分區(qū)分配 可重定位分區(qū)分配可重定位分區(qū)分配 連續(xù)分配方式連續(xù)分配方式離散分配方式離散分配方式

3、4.1.2 (地址)重定位 4目標(biāo)程序使用的地址單元稱為目標(biāo)程序使用的地址單元稱為邏輯地址邏輯地址( (相對地址或虛相對地址或虛地址地址) )，一個用戶作業(yè)的目標(biāo)程序的邏輯地址集合稱為該作，一個用戶作業(yè)的目標(biāo)程序的邏輯地址集合稱為該作業(yè)的邏輯地址空間。一維邏輯地址從業(yè)的邏輯地址空間。一維邏輯地址從0 0開始編號。二維邏輯開始編號。二維邏輯地址各段內(nèi)地址也從地址各段內(nèi)地址也從0 0開始。開始。主存中的實際存儲單元編號稱為主存中的實際存儲單元編號稱為物理地址物理地址( (絕對地址或內(nèi)絕對地址或內(nèi)存地址存地址) )。物理地址的總體構(gòu)成物理地址空間。物理地址的總體構(gòu)成物理地址空間。1. 邏輯地址與物理

4、地址邏輯地址與物理地址2. 重定位重定位(Relocation)（地址映射、地址轉(zhuǎn)換）（地址映射、地址轉(zhuǎn)換） 為了保證程序的正確執(zhí)行，必須把程序和數(shù)據(jù)的邏輯地為了保證程序的正確執(zhí)行，必須把程序和數(shù)據(jù)的邏輯地址轉(zhuǎn)換為物理地址，這一工作叫做址轉(zhuǎn)換為物理地址，這一工作叫做地址轉(zhuǎn)換地址轉(zhuǎn)換或或重定位重定位。重定位可分兩種：靜態(tài)重定位和動態(tài)重定位。重定位可分兩種：靜態(tài)重定位和動態(tài)重定位。5(1) 靜態(tài)地址重定位靜態(tài)地址重定位在裝入一個程序時，把程序中的指令地址全部在裝入一個程序時，把程序中的指令地址全部轉(zhuǎn)換轉(zhuǎn)換為為絕對地址絕對地址，地址轉(zhuǎn)換工作是，地址轉(zhuǎn)換工作是在程序執(zhí)行在程序執(zhí)行前集前集中一次完成的，

5、中一次完成的，在程序執(zhí)行在程序執(zhí)行過程中就無須再進(jìn)行地過程中就無須再進(jìn)行地址轉(zhuǎn)換工作。址轉(zhuǎn)換工作。(2) 動態(tài)地址重定位動態(tài)地址重定位動態(tài)地址重地位是在程序執(zhí)行過程中，在動態(tài)地址重地位是在程序執(zhí)行過程中，在CPUCPU執(zhí)行每條指令時執(zhí)行每條指令時, ,將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址。動態(tài)重定位依靠硬件地址變換機構(gòu)完成內(nèi)存地址。動態(tài)重定位依靠硬件地址變換機構(gòu)完成。成。舉例說明舉例說明指令或數(shù)據(jù)的內(nèi)存地址指令或數(shù)據(jù)的內(nèi)存地址PAPA與虛地址的關(guān)系為：與虛地址的關(guān)系為： PA=PA=基址基址(BR)+(BR)+虛地址虛地址4.2 程序的裝入和鏈接6創(chuàng)建進(jìn)程的第一件

6、事，便是將程序和數(shù)據(jù)裝創(chuàng)建進(jìn)程的第一件事，便是將程序和數(shù)據(jù)裝入內(nèi)存。入內(nèi)存。4.2.1 程序的裝入程序的裝入將程序?qū)⒊绦?模塊模塊)裝入內(nèi)存時，可以有三種方式：裝入內(nèi)存時，可以有三種方式：1. 絕對裝入方式絕對裝入方式2. 可重定位裝入方式可重定位裝入方式3. 動態(tài)運行時裝入方式動態(tài)運行時裝入方式71.絕對裝入方式絕對裝入方式在編譯在編譯(或匯編或匯編)時，如果知道程序?qū)Ⅰv留在時，如果知道程序?qū)Ⅰv留在內(nèi)存的什么位置，那么，編譯程序?qū)a(chǎn)生絕對地內(nèi)存的什么位置，那么，編譯程序?qū)a(chǎn)生絕對地址的代碼。址的代碼。程序員通常寧可在程序中采用符號地址，然程序員通常寧可在程序中采用符號地址，然后在編譯或匯編時

7、后在編譯或匯編時，再將，再將這些符號地址轉(zhuǎn)換為絕這些符號地址轉(zhuǎn)換為絕對地址對地址n 絕對裝入程序按照裝入模塊中的絕對裝入程序按照裝入模塊中的( (絕對絕對) )地址，地址，將程序和數(shù)據(jù)裝入內(nèi)存。將程序和數(shù)據(jù)裝入內(nèi)存。n 由于程序中的邏輯地址與實際內(nèi)存地址完全由于程序中的邏輯地址與實際內(nèi)存地址完全相同，故裝入時不需對程序和數(shù)據(jù)的地址進(jìn)相同，故裝入時不需對程序和數(shù)據(jù)的地址進(jìn)行修改。行修改。只適用于單道環(huán)境只適用于單道環(huán)境82. 可重定位裝入方式可重定位裝入方式 在多道程序環(huán)境下，目標(biāo)模塊的起始在多道程序環(huán)境下，目標(biāo)模塊的起始地址通常是從地址通常是從0開始的，程序中的其它地址開始的，程序中的其它地址

8、都是相對于起始地址計算的。此時應(yīng)采用都是相對于起始地址計算的。此時應(yīng)采用可重定位裝入方式可重定位裝入方式，根據(jù)內(nèi)存的當(dāng)前情況，根據(jù)內(nèi)存的當(dāng)前情況，將裝入模塊裝入到適當(dāng)位置將裝入模塊裝入到適當(dāng)位置在裝入時，對目標(biāo)程序中的指令和數(shù)據(jù)在裝入時，對目標(biāo)程序中的指令和數(shù)據(jù)的地址作必要的修改的地址作必要的修改將邏輯地址改為絕將邏輯地址改為絕對地址對地址靜態(tài)重定位靜態(tài)重定位。93. 動態(tài)運行時裝入方式動態(tài)運行時裝入方式在把裝入模塊裝入內(nèi)存時，并不立即把在把裝入模塊裝入內(nèi)存時，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時是把這種地

9、址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行才進(jìn)行動態(tài)重定位動態(tài)重定位。為使地址轉(zhuǎn)換不影響指令的執(zhí)行速度，為使地址轉(zhuǎn)換不影響指令的執(zhí)行速度，需要一個重定位寄存器的支持。需要一個重定位寄存器的支持。動態(tài)重定位需要硬件支持動態(tài)重定位需要硬件支持。4.2.2 程序的鏈接10源程序經(jīng)編譯后，可得到一組目標(biāo)程序，再利源程序經(jīng)編譯后，可得到一組目標(biāo)程序，再利用鏈接程序?qū)⑦@組目標(biāo)模塊鏈接，形成裝入模塊。用鏈接程序?qū)⑦@組目標(biāo)模塊鏈接，形成裝入模塊。根據(jù)鏈接時間的不同，可把鏈接分成如下三種：根據(jù)鏈接時間的不同，可把鏈接分成如下三種： 靜態(tài)鏈接。在程序運行之前，先將各目標(biāo)模塊靜態(tài)鏈接。在程序運行之前，先將各目標(biāo)模塊及它們所

10、需的庫函數(shù)，鏈接成一個完整的裝配及它們所需的庫函數(shù)，鏈接成一個完整的裝配模塊，以后不再拆開。模塊，以后不再拆開。 裝入時動態(tài)鏈接。這是指將用戶源程序編譯得裝入時動態(tài)鏈接。這是指將用戶源程序編譯得到的一組目標(biāo)模塊，在裝入內(nèi)存時，采用邊裝到的一組目標(biāo)模塊，在裝入內(nèi)存時，采用邊裝入邊鏈接的鏈接方式。入邊鏈接的鏈接方式。 運行時動態(tài)鏈接。這是指對某些目標(biāo)模塊，是運行時動態(tài)鏈接。這是指對某些目標(biāo)模塊，是在程序執(zhí)行中需要該目標(biāo)在程序執(zhí)行中需要該目標(biāo)( (模塊模塊) )時，才對它進(jìn)時，才對它進(jìn)行鏈接。行鏈接。111. 靜態(tài)鏈接方式靜態(tài)鏈接方式實現(xiàn)靜態(tài)鏈接應(yīng)解決兩個問題實現(xiàn)靜態(tài)鏈接應(yīng)解決兩個問題： 對相對地址

11、進(jìn)行修改。編譯程序產(chǎn)生的所有目標(biāo)對相對地址進(jìn)行修改。編譯程序產(chǎn)生的所有目標(biāo)模塊中，起始地址都是模塊中，起始地址都是0，每個模塊中的地址都，每個模塊中的地址都是相對于起始地址計算的。在鏈接成一個模塊后，是相對于起始地址計算的。在鏈接成一個模塊后，后續(xù)模塊在裝入模塊的起始地址不再是后續(xù)模塊在裝入模塊的起始地址不再是0。 變換外部調(diào)用符號。將每個模塊中所用的外部調(diào)變換外部調(diào)用符號。將每個模塊中所用的外部調(diào)用符號也都變換為相對地址，例如，編譯得到用符號也都變換為相對地址，例如，編譯得到3個目標(biāo)模塊個目標(biāo)模塊A、B、C，它們的長度分別是，它們的長度分別是L、M和和N，則把，則把B的起始地址變換為的起始地

12、址變換為L，把，把C的起始地的起始地址變換為址變換為L+M。這種先進(jìn)行鏈接所形成的一個完這種先進(jìn)行鏈接所形成的一個完整的裝入模塊，又稱為可執(zhí)行文件。整的裝入模塊，又稱為可執(zhí)行文件。122. 裝入時動態(tài)鏈接方式裝入時動態(tài)鏈接方式邊裝入邊鏈接。邊裝入邊鏈接。優(yōu)點優(yōu)點：便于對某個模塊的修改和更新便于對某個模塊的修改和更新 。采用動。采用動態(tài)鏈接方式，由于態(tài)鏈接方式，由于各目標(biāo)模塊是分開存各目標(biāo)模塊是分開存放放的，所以要修改或更新各目標(biāo)模塊，的，所以要修改或更新各目標(biāo)模塊，是件非常容易的事。是件非常容易的事。便于實現(xiàn)對目標(biāo)模塊的共享。采用動態(tài)便于實現(xiàn)對目標(biāo)模塊的共享。采用動態(tài)鏈接方式，鏈接方式，OS很

13、容易將一個目標(biāo)模塊鏈很容易將一個目標(biāo)模塊鏈接到幾個應(yīng)用模塊上，實現(xiàn)多個應(yīng)用程接到幾個應(yīng)用模塊上，實現(xiàn)多個應(yīng)用程序?qū)υ撃K的共享。序?qū)υ撃K的共享。 133. 運行時動態(tài)連接運行時動態(tài)連接在許多情況下，應(yīng)用程序在運行時，每次要運行在許多情況下，應(yīng)用程序在運行時，每次要運行的模塊可能是不相同的。但由于事先無法知道本次要的模塊可能是不相同的。但由于事先無法知道本次要運行哪些模塊，故只能將所有可能要運行到的模塊都運行哪些模塊，故只能將所有可能要運行到的模塊都裝入內(nèi)存，并在裝入時全部鏈接在一起，這顯然是低裝入內(nèi)存，并在裝入時全部鏈接在一起，這顯然是低效的。效的。近幾年流行起來的運行時動態(tài)鏈接方式，是對上

14、近幾年流行起來的運行時動態(tài)鏈接方式，是對上述在裝入時鏈接方式的一種改進(jìn)。這種鏈接方式是將述在裝入時鏈接方式的一種改進(jìn)。這種鏈接方式是將對某個模塊的鏈接推遲到執(zhí)行時才執(zhí)行，亦即，在執(zhí)對某個模塊的鏈接推遲到執(zhí)行時才執(zhí)行，亦即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由立即由OS去找到該模塊并將它裝入內(nèi)存，把它鏈接到去找到該模塊并將它裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。調(diào)用者模塊上。優(yōu)點：優(yōu)點：n 加快模塊的裝入過程；加快模塊的裝入過程； n 節(jié)省大量內(nèi)存。節(jié)省大量內(nèi)存。 4.3 連續(xù)分配方式 是指一個用戶程序分配一個連續(xù)的內(nèi)存空間。又稱分區(qū)

15、管理方式。分區(qū)是指內(nèi)存中的一個連續(xù)區(qū)域。 14分區(qū)管理方式曾被廣泛應(yīng)用于分區(qū)管理方式曾被廣泛應(yīng)用于20世紀(jì)世紀(jì)6070年代的年代的OS中，至今仍在內(nèi)存分配方式中占一席中，至今仍在內(nèi)存分配方式中占一席之地。之地。 分區(qū)分配方式可分為：分區(qū)分配方式可分為：固定分區(qū)分配固定分區(qū)分配、動態(tài)分區(qū)動態(tài)分區(qū)分配分配、動態(tài)重定位分區(qū)分配動態(tài)重定位分區(qū)分配等。等。154.3.1 固定分區(qū)分配固定分區(qū)分配 最簡單的可運行多最簡單的可運行多道程序的存儲器管道程序的存儲器管理方式。理方式。 將內(nèi)存劃分為若干個固定大小的區(qū)域（分區(qū)），將內(nèi)存劃分為若干個固定大小的區(qū)域（分區(qū)），每個分區(qū)中裝入一道作業(yè)，允許幾道作業(yè)并發(fā)運行

16、。每個分區(qū)中裝入一道作業(yè)，允許幾道作業(yè)并發(fā)運行。當(dāng)有空閑分區(qū)時，便可從后備隊列中選擇一個作業(yè)當(dāng)有空閑分區(qū)時，便可從后備隊列中選擇一個作業(yè)裝入該分區(qū)。裝入該分區(qū)。 1. 劃分分區(qū)的方法劃分分區(qū)的方法 v 分區(qū)大小相等分區(qū)大小相等v 分區(qū)大小不等分區(qū)大小不等更合理更合理 2. 內(nèi)存分配16為了便于內(nèi)存分配，通常將為了便于內(nèi)存分配，通常將分區(qū)按大小排隊分區(qū)按大小排隊，建立一張分區(qū)使，建立一張分區(qū)使用表。表項：分區(qū)起始地址、大小、狀態(tài)（是否已分配用表。表項：分區(qū)起始地址、大小、狀態(tài)（是否已分配）分區(qū)號分區(qū)號 大小大小(K) 始址始址(K) 狀態(tài)狀態(tài) 132100已分配已分配 264132已分配已分配3

17、128196已分配已分配4128324未分配未分配 5188452未分配未分配 分區(qū)分配表分區(qū)分配表 操作系統(tǒng)操作系統(tǒng)作業(yè)作業(yè)A作業(yè)作業(yè)B作業(yè)作業(yè)C100K132K196K324K452K 內(nèi)存分配情況內(nèi)存分配情況 當(dāng)有一用戶程序要裝入時，由內(nèi)存分配程序檢索該表，當(dāng)有一用戶程序要裝入時，由內(nèi)存分配程序檢索該表，從中找出一個能滿足要求的、尚未分配的分區(qū)，將之分配給從中找出一個能滿足要求的、尚未分配的分區(qū)，將之分配給該程序，然后將該表項中的狀態(tài)置為該程序，然后將該表項中的狀態(tài)置為“已分配已分配”；若找不到；若找不到大小足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)存。大小足夠的分區(qū)，則拒絕為該用戶程序分配內(nèi)

18、存。3. 3. 固定分區(qū)方式的缺點固定分區(qū)方式的缺點1、大程序可能無法裝入；2、主存空間利用率不高作業(yè)往往不可能恰好填滿分區(qū)；3、作業(yè)動態(tài)擴(kuò)充主存困難；4、各分區(qū)作業(yè)要共享程序和數(shù)據(jù)也難實現(xiàn)；5、限制了多道運行的程序數(shù)。174.3.2 動態(tài)分區(qū)分配動態(tài)分區(qū)分配 181 1分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 可以有兩種形式：可以有兩種形式：空閑分區(qū)表、空閑分區(qū)鏈空閑分區(qū)表、空閑分區(qū)鏈 動態(tài)分區(qū)分配是根據(jù)進(jìn)程的實際需要，動態(tài)分區(qū)分配是根據(jù)進(jìn)程的實際需要，動態(tài)地動態(tài)地為之分為之分配內(nèi)存空間。在實現(xiàn)時，涉及配內(nèi)存空間。在實現(xiàn)時，涉及到到三三個個問題：問題：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)、分配算法分配算法、分配

19、及回收操作分配及回收操作。19操作系統(tǒng)操作系統(tǒng)100K2000K1) 1) 空閑分區(qū)表空閑分區(qū)表 分區(qū)號分區(qū)號分區(qū)始址分區(qū)始址分區(qū)長度分區(qū)長度1100KB128KB2800KB200KB31300KB700KB每個空閑分區(qū)占一個表目，表目包括：每個空閑分區(qū)占一個表目，表目包括：分區(qū)號、分區(qū)始址、分區(qū)大小分區(qū)號、分區(qū)始址、分區(qū)大小等等空閑區(qū)空閑區(qū)作業(yè)作業(yè)A228K作業(yè)作業(yè)B800K作業(yè)作業(yè)C1000K作業(yè)作業(yè)D1300K空閑區(qū)空閑區(qū)空閑區(qū)空閑區(qū)202) 2) 空閑分區(qū)鏈空閑分區(qū)鏈 每個分區(qū)的起始部分，每個分區(qū)的起始部分，本空閑分區(qū)長度及下本空閑分區(qū)長度及下一個空閑分區(qū)的起始一個空閑分區(qū)的起始地址

20、指針。地址指針。頭指針頭指針優(yōu)點優(yōu)點：自身不占用存儲空間。自身不占用存儲空間。缺點缺點：比空閑分區(qū)表管理復(fù)雜。比空閑分區(qū)表管理復(fù)雜。212 2分區(qū)分配算法分區(qū)分配算法 空閑分區(qū)表按地址遞增排序。分配時從表首開始順序查找，直至找到一個大小能滿足要求的空閑分區(qū)；然后按作業(yè)大小劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在表中。 由首次適應(yīng)算法演變而成。為進(jìn)程分配內(nèi)存時，不再是每次從表首開始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直至找到一個大小能滿足要求的空閑分區(qū)，從中劃出一塊與請求大小相等的分區(qū)分配給作業(yè)。為實現(xiàn)該算法，應(yīng)設(shè)置一起始查找指針。每次分配時，總是將能滿足要求的最小

21、分區(qū)分配給請求者。將空閑分區(qū)按其容量從小到大順序排列加快查找。 首次適首次適應(yīng)算法應(yīng)算法 循環(huán)首次循環(huán)首次適應(yīng)算法適應(yīng)算法 最佳適最佳適應(yīng)算法應(yīng)算法 最壞適應(yīng)算法最壞適應(yīng)算法例題22 在可變分區(qū)存儲管理下，按地址排列的內(nèi)存空閑區(qū)為：在可變分區(qū)存儲管理下，按地址排列的內(nèi)存空閑區(qū)為：100KB、500KB、200KB、300KB和和600KB。現(xiàn)有若干用?，F(xiàn)有若干用戶程序，其所需內(nèi)存依次分別為戶程序，其所需內(nèi)存依次分別為212KB、417KB、112KB和和426KB，分別用首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)，分別用首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法，將它們裝入到內(nèi)存的哪些空閑分區(qū)？哪個算

22、法能最有算法，將它們裝入到內(nèi)存的哪些空閑分區(qū)？哪個算法能最有效利用內(nèi)存？效利用內(nèi)存？解：采用首次適應(yīng)算法解：采用首次適應(yīng)算法 程序程序 空閑區(qū)空閑區(qū) 新空閑區(qū)新空閑區(qū)212KB500KB288KB417KB600KB183KB112KB288KB176KB426KB，無法裝入內(nèi)存，無法裝入內(nèi)存類似的分析可知類似的分析可知, ,最壞適應(yīng)算法也最壞適應(yīng)算法也不能將不能將426KB426KB的程的程序裝入內(nèi)存，而序裝入內(nèi)存，而最佳適應(yīng)算法可最佳適應(yīng)算法可將程序全部裝入將程序全部裝入內(nèi)存。內(nèi)存。233 3分區(qū)分配操作分區(qū)分配操作 1）分配內(nèi)存）分配內(nèi)存 當(dāng)某空閑分區(qū)滿足當(dāng)某空閑分區(qū)滿足m.sizeu.

23、sizem.sizeu.size時，執(zhí)行如下操作：時，執(zhí)行如下操作： 當(dāng)當(dāng)m.size-u.sizesizem.size-u.sizesize時，將時，將整個分區(qū)分配給請求者；整個分區(qū)分配給請求者；否則，按作業(yè)大小劃出一塊內(nèi)存否則，按作業(yè)大小劃出一塊內(nèi)存空間分配給請求者，余下的空閑分空間分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表（鏈）中。區(qū)仍留在空閑分區(qū)表（鏈）中。 將分配區(qū)的首地址返回給調(diào)用者。將分配區(qū)的首地址返回給調(diào)用者。 從頭開始查表從頭開始查表檢索完否？檢索完否？m.sizeu.sizem.sizeu.size? ?m.size-u.sizesize?m.size-u.sizesiz

24、e?從該分區(qū)中劃出從該分區(qū)中劃出u.sizeu.size大小的分區(qū)大小的分區(qū)將該分區(qū)分配給請求者將該分區(qū)分配給請求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回返回返回繼續(xù)檢索下繼續(xù)檢索下一個表項一個表項將該分區(qū)從表將該分區(qū)從表（鏈）中劃出（鏈）中劃出NYYYNN分配內(nèi)存過程如分配內(nèi)存過程如圖所圖所示。示。圖中假設(shè)：圖中假設(shè)：v請求分區(qū)大小請求分區(qū)大小u. .size；v分區(qū)大小為分區(qū)大小為m. .size； v不再切割的剩余分區(qū)大小為不再切割的剩余分區(qū)大小為size。242）回收內(nèi)存）回收內(nèi)存 根據(jù)回收區(qū)的首地址，在空閑分區(qū)表（鏈）找到插入點，此時可能出現(xiàn)根據(jù)回收區(qū)的首地址，在空閑分區(qū)表（鏈）找

25、到插入點，此時可能出現(xiàn)4種情況之一（假設(shè)空閑分區(qū)表按地址從低到高順序排列）：種情況之一（假設(shè)空閑分區(qū)表按地址從低到高順序排列）： 回收區(qū)與插入點的前一個空閑分區(qū)回收區(qū)與插入點的前一個空閑分區(qū)F1相鄰接相鄰接( (學(xué)生考慮判斷條件學(xué)生考慮判斷條件) )：將回：將回收區(qū)與前一區(qū)合并，不必增加新表項，只需修改收區(qū)與前一區(qū)合并，不必增加新表項，只需修改F1的大小為兩者之和。的大小為兩者之和。作業(yè)作業(yè)A AF1F1回收區(qū)回收區(qū)作業(yè)作業(yè)B B作業(yè)作業(yè)A A回收區(qū)回收區(qū)F2F2作業(yè)作業(yè)B B作業(yè)作業(yè)A AF1F1回收區(qū)回收區(qū)F2F2作業(yè)作業(yè)B B作業(yè)作業(yè)A A回收區(qū)回收區(qū)作業(yè)作業(yè)B B回收區(qū)與高地址回收區(qū)與

26、高地址F2分區(qū)鄰接：此時將回收分區(qū)與該分區(qū)合并，回收區(qū)分區(qū)鄰接：此時將回收分區(qū)與該分區(qū)合并，回收區(qū)的首地址為新分區(qū)的首地址，大小為兩者之和。的首地址為新分區(qū)的首地址，大小為兩者之和?；厥諈^(qū)與前后分區(qū)回收區(qū)與前后分區(qū)F1和和F2都鄰接：將此都鄰接：將此3個分區(qū)合并，個分區(qū)合并，F(xiàn)1（前鄰接區(qū)）（前鄰接區(qū)）的首地址為新分區(qū)的首址，大小為三者之和，取消的首地址為新分區(qū)的首址，大小為三者之和，取消F2表項。表項?；厥諈^(qū)與任何空閑區(qū)都不鄰接：在插入點建立一個新表項，填寫回收區(qū)的回收區(qū)與任何空閑區(qū)都不鄰接：在插入點建立一個新表項，填寫回收區(qū)的首地址和大小。插入到空閑區(qū)表的適當(dāng)位置（后移插入點后的各個表項）

27、首地址和大小。插入到空閑區(qū)表的適當(dāng)位置（后移插入點后的各個表項）4.3.6 可重定位分區(qū)分配可重定位分區(qū)分配 1 1動態(tài)重定位的引入動態(tài)重定位的引入 目的：為了解決內(nèi)存“碎片”問題。2 2動態(tài)重定位的實現(xiàn)動態(tài)重定位的實現(xiàn) 為使地址轉(zhuǎn)換不會影響到指令執(zhí)行速度，必須有硬件地址變換機構(gòu)專設(shè)兩個控制寄存器：基址寄基址寄存器存器和和限長寄存器限長寄存器 物理地址物理地址 = = 邏輯地址邏輯地址 + + 基址寄存器中的地址值基址寄存器中的地址值 外部碎片外部碎片方法：移動作業(yè)，稱為“拼接”或“緊湊” 需要動態(tài)重定位4.3.64.3.6 可重定位分區(qū)分配可重定位分區(qū)分配 26物理地址物理地址 = = 邏輯

28、地址邏輯地址 + + 基址寄存器中的地址值基址寄存器中的地址值 010025005000作業(yè)作業(yè)J1000010000LOAD I 2500LOAD I 2500365365主存主存邏輯地址邏輯地址2500基址寄存器基址寄存器10000101001250015000物理地址物理地址LOAD I 2500365限長寄存器限長寄存器50005000頁表長度？頁表長度？越界中斷越界中斷CPUCPU檢索快表檢索快表頁表項在快表中？頁表項在快表中？訪問頁表訪問頁表頁在內(nèi)存？頁在內(nèi)存？修改快表修改快表修改訪問位和修改位修改訪問位和修改位形成物理地址形成物理地址地址變換結(jié)束地址變換結(jié)束保留保留CPUCPU現(xiàn)

29、場現(xiàn)場從外存中找到缺頁從外存中找到缺頁內(nèi)存滿否？內(nèi)存滿否？選擇一頁換出選擇一頁換出該頁被修改否？該頁被修改否？將該頁寫回外存將該頁寫回外存OSOS命令命令CPUCPU從外存讀缺頁從外存讀缺頁啟動啟動I/OI/O硬件硬件將一頁從外存讀入內(nèi)存將一頁從外存讀入內(nèi)存修改頁表修改頁表缺頁中斷處理缺頁中斷處理產(chǎn)生缺頁中產(chǎn)生缺頁中斷請求調(diào)頁斷請求調(diào)頁否否是是是是是是是是是是否否否否否否 請求分頁中的地址變換過程請求分頁中的地址變換過程請求分頁中的地址變換過程74頁號頁號 頁內(nèi)地址頁內(nèi)地址運行進(jìn)程頁表基址運行進(jìn)程頁表基址邏輯地址邏輯地址CPU邏輯空間邏輯空間快表快表進(jìn)程切換進(jìn)程切換時裝入時裝入運行進(jìn)程頁表運行

30、進(jìn)程頁表(主存系統(tǒng)區(qū)主存系統(tǒng)區(qū))查頁表查頁表分解分解地址地址查快表查快表命中命中不命中不命中裝入、裝入、改表改表塊號塊號 頁內(nèi)地址頁內(nèi)地址頁表命中頁表命中缺頁中斷缺頁中斷缺頁中斷處理缺頁中斷處理調(diào)頁調(diào)頁裝入裝入快表快表物理地址物理地址MMU運行進(jìn)運行進(jìn)程映象程映象主存主存(用戶區(qū)用戶區(qū))訪問訪問輔存輔存MMU：主存管理單元：主存管理單元4.7.2 內(nèi)存分配策略和分配算法 為進(jìn)程分配內(nèi)存時，涉及到3個問題： 1 1、最小物理塊數(shù)的確定、最小物理塊數(shù)的確定 取決于指令的格式、功能和尋址方式 2 2、物理塊的分配策略、物理塊的分配策略 固定分配局部置換 可變分配全局置換最易于實現(xiàn)的物理塊分配和置換策

31、略，已用于若干OS中 可變分配局部置換 3 3、物理塊分配算法、物理塊分配算法 平均分配算法顯然不太合理 按比例分配算法 考慮優(yōu)先權(quán)的分配算法一部分按比例；另一部分根據(jù)各進(jìn)程的優(yōu)先權(quán)合理 754.7.3 調(diào)頁策略 何時調(diào)入頁面 預(yù)調(diào)頁策略請求調(diào)頁策略 從何處調(diào)入頁面系統(tǒng)有足夠的對換區(qū)全部從對換區(qū)調(diào)入系統(tǒng)缺少對換區(qū)從文件區(qū)或?qū)Q區(qū)調(diào)入 UNIX方式凡未運行的頁面，從文件區(qū)調(diào)入；曾經(jīng)運行過又被調(diào)出的頁面，從對換區(qū)調(diào)入。共享頁面有時無須調(diào)入 頁面調(diào)入過程 缺頁率764.8 頁面置換算法 好的頁面置換算法，應(yīng)具有較低的頁面更換頻率4.8.14.8.1最佳置換算法和先進(jìn)先出置換算法1最佳置換算法（OPT

32、） 一種理論上的算法。 選擇以后永不使用的或者是未來最長時間內(nèi)不再使用的頁面淘汰。774.8 頁面置換算法 78【例題例題1】假定系統(tǒng)為某進(jìn)程分配了假定系統(tǒng)為某進(jìn)程分配了3個物理塊，并考個物理塊，并考慮以下的頁面引用串：慮以下的頁面引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 引用串引用串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 11 11 11 11 11 11 11 13 33 33 33 33 33 33 33 31 11 11 10 00 00 00 00 00 00 00 00 00 04 44 44 40

33、 00 00 00 00 00 07 77 77 72 22 22 22 22 22 22 22 22 22 22 22 22 22 27 77 77 7 7 1 0 4 3 2 利用最佳頁面置換算法的置換圖利用最佳頁面置換算法的置換圖被置換的頁被置換的頁物理塊物理塊發(fā)生發(fā)生6次頁面置換次頁面置換 4.8 頁面置換算法792先進(jìn)先出（先進(jìn)先出（FIFO）頁面置換算法）頁面置換算法 選擇在內(nèi)存中駐留時間最長的頁面淘汰。 設(shè)置一個指針，指向最老的頁面。 4.8.14.8.1最佳置換算法和先進(jìn)先出置換算法4.8 頁面置換算法80進(jìn)行了進(jìn)行了12次頁面置換次頁面置換 引用串引用串 7 0 1 2 0

34、3 0 4 2 3 0 3 2 1 2 0 1 7 0 11 12 22 22 22 22 23 33 33 33 33 30 00 00 01 11 11 11 10 00 01 11 11 11 11 12 22 22 22 22 23 33 33 30 00 00 00 07 77 77 70 00 00 00 00 00 00 04 44 44 42 22 22 22 27 77 77 7 7 0 1 2 3 0 4 2 3 0 1 2 利用利用FIFO頁面置換算法時的置換圖頁面置換算法時的置換圖被置換的頁被置換的頁物理塊物理塊【例例1】假定系統(tǒng)為某進(jìn)程分配了假定系統(tǒng)為某進(jìn)程分配了3個

35、物理塊，并考慮個物理塊，并考慮以下的頁面引用串：以下的頁面引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 仍以仍以例例1 1為例。為例。4.8.2 最近最久未使用（LRU）置換算法 81選擇最近最久未使用的頁面進(jìn)行淘汰。選擇最近最久未使用的頁面進(jìn)行淘汰。用用“最近的過最近的過去去”作為作為“最近的將來最近的將來”的近似。的近似。 LRULRU頁面置換算法的演算過程可以頁面置換算法的演算過程可以借助借助“棧棧”來完成來完成：棧頂始終是最新的，棧底是最近最久未使用的頁面號。棧頂始終是最新的，棧底是最近最久未使用的頁面號。 引用串引用串 7 0 1 2 0 3

36、 0 4 2 3 0 3 2 1 2 0 1 7 0 17 71 10 02 21 13 33 30 02 22 24 40 03 32 22 21 10 07 77 77 70 07 71 10 02 21 12 23 30 03 32 24 40 03 30 02 21 10 00 01 10 07 71 10 02 21 12 23 30 03 32 24 40 03 30 02 21 1 7 1 2 3 0 4 0 3 2 被置換的頁被置換的頁物理塊物理塊 LRU頁面置換算法的置換圖頁面置換算法的置換圖發(fā)生發(fā)生9 9次頁面置換次頁面置換 仍以仍以例例1 1為例。為例。82v為每個頁設(shè)置

37、一個多位寄存器，開始時，所有計為每個頁設(shè)置一個多位寄存器，開始時，所有計數(shù)器全部清數(shù)器全部清0。v當(dāng)頁面被訪問時，將它對應(yīng)的寄存器的最左邊位當(dāng)頁面被訪問時，將它對應(yīng)的寄存器的最左邊位(最高位最高位)置置1。每隔一定時間。每隔一定時間t，將所有頁的寄存器，將所有頁的寄存器右移一位；右移一位；v 在發(fā)生缺頁中斷時，可選擇最小數(shù)值的寄存器對在發(fā)生缺頁中斷時，可選擇最小數(shù)值的寄存器對應(yīng)頁面淘汰。應(yīng)頁面淘汰。該算法也稱做老化算法該算法也稱做老化算法, ,例題詳見例題詳見圖圖5-6.5-6.LRULRU頁面置換算法的演算過程還可以頁面置換算法的演算過程還可以借助借助“寄存器寄存器”來完成來完成; ; 具體

38、思路如下具體思路如下: : 4.8.3 Clock置換算法 當(dāng)發(fā)生頁面當(dāng)發(fā)生頁面置換置換時，首先檢查指針時，首先檢查指針?biāo)傅捻撁?，若它的所指的頁面，若它的A位是位是0就淘汰該就淘汰該頁面，并把新頁面插入這個位置，指頁面，并把新頁面插入這個位置，指針前移一個位置；針前移一個位置； 若若A位是位是1，就清除，就清除A位，并把指針位，并把指針前移一個位置；重復(fù)這個過程，直到前移一個位置；重復(fù)這個過程，直到找到一個找到一個A位是位是0的頁面為止。的頁面為止。83需為每頁設(shè)置一個需為每頁設(shè)置一個訪問位訪問位A。在內(nèi)存中的頁面鏈接成一個循環(huán)隊在內(nèi)存中的頁面鏈接成一個循環(huán)隊列，有一個指針指向最老的頁面。列

39、，有一個指針指向最老的頁面。如如圖所圖所示。示。A AB BC CD DE EF FG GH HI IJ JK KH H 時鐘頁面置換算法時鐘頁面置換算法Clock置換算法舉例84引用串引用串 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 11 1* *2 22 22 2* *2 2* *2 2* *0 00 0* *0 0* *0 0* *3 3* *3 33 33 3* *3 3* *1 11 11 1* *7 7* *7 7* *7 7* *1 1* *1 1* *1 1* *1 1* *2 2* *2 22 22 2* *2 2* *0 00 0* *0

40、00 0* *0 00 0* *0 0* *0 0* *0 0* *0 00 0* *0 0* *3 33 33 3* *3 3* *4 44 4* *4 4* *4 4* *2 2* *2 2* *2 2* *2 2* *7 7* *7 7* *7 7* * 7 1 2 0 3 4 2 0 3 1 2被置換的頁被置換的頁物理塊物理塊 Clock頁面置換算法的置換圖頁面置換算法的置換圖仍以仍以例例1 1為例：為例：發(fā)生發(fā)生1111次頁面置換次頁面置換 假定系統(tǒng)為某進(jìn)程分配了假定系統(tǒng)為某進(jìn)程分配了3個物理塊，并考慮以下的頁面引用個物理塊，并考慮以下的頁面引用串：串：7，0，1，2，0，3，0，4

41、，2，3，0，3，2，1，2，0，1，7，0，1。采用。采用Clock置換算法，計算其頁面置換次數(shù)。置換算法，計算其頁面置換次數(shù)。蘭色為指針位置，蘭色為指針位置，* *為訪問標(biāo)志為訪問標(biāo)志改進(jìn)型Clock置換算法(UNIX SVR4采用此算法) 淘汰被修改過的頁面時，需將其寫回淘汰被修改過的頁面時，需將其寫回磁盤磁盤(置換代價高置換代價高)，因此應(yīng)淘汰既未被訪問又未被，因此應(yīng)淘汰既未被訪問又未被修改的頁面。為此，每個頁面除了有修改的頁面。為此，每個頁面除了有訪問位A外，外，還增加一個還增加一個修改位M。由訪問位由訪問位A與修改位與修改位M可以可以組成下面組成下面4種類型的頁面：種類型的頁面：

42、1類(A=0,M=0)，是最佳淘汰頁； 2類(A=0,M=1) ； 3類(A=1,M=0) ； 4類(A=1,M=1) ，最近被訪問且被修改過的頁，最不應(yīng)該淘汰。85改進(jìn)型Clock置換算法(UNIX SVR4采用此算法)86(1) 從從指針當(dāng)前位置開始，掃描循環(huán)隊列，尋找指針當(dāng)前位置開始，掃描循環(huán)隊列，尋找A=0且且M=0的第的第1類頁面，將所遇到的第一個頁面淘汰。類頁面，將所遇到的第一個頁面淘汰。(2) 若若第第1步查找一周后未遇到第步查找一周后未遇到第1類頁面，則尋找類頁面，則尋找A=0且且M=1的第的第2類頁面，將所遇到的第一個頁面淘類頁面，將所遇到的第一個頁面淘汰。第汰。第2輪掃描中

43、將所有掃描過的頁面的訪問位輪掃描中將所有掃描過的頁面的訪問位A清清0。(3)若第若第2輪掃描失敗，則返回輪掃描失敗，則返回(1)，若仍失敗，再重，若仍失敗，再重復(fù)第復(fù)第(2)步，此時就一定能找到被淘汰的頁。步，此時就一定能找到被淘汰的頁。淘汰原淘汰原3 3類頁類頁淘汰原淘汰原4 4類頁類頁4.8.4 頁面緩沖算法(PBA)87VAX/VMS操作系統(tǒng)采用頁面緩沖算法。操作系統(tǒng)采用頁面緩沖算法。v采用可變分配局部置換方式，置換算法采用采用可變分配局部置換方式，置換算法采用FIFO；v將一個淘汰的頁放入兩個鏈表之一將一個淘汰的頁放入兩個鏈表之一空閑鏈表或已修改頁空閑鏈表或已修改頁面鏈表；面鏈表；v當(dāng)

44、該進(jìn)程以后再次訪問這些頁時，只需花費較小的開銷，使當(dāng)該進(jìn)程以后再次訪問這些頁時，只需花費較小的開銷，使這些頁面又返回到該進(jìn)程的駐留集中。這些頁面又返回到該進(jìn)程的駐留集中。v當(dāng)被修改的頁數(shù)目達(dá)到一定值時，例如當(dāng)被修改的頁數(shù)目達(dá)到一定值時，例如64個頁面時，再將個頁面時，再將它們一起寫回磁盤，從而減少了磁盤它們一起寫回磁盤，從而減少了磁盤I/O操作次數(shù)。操作次數(shù)。MACH操作系統(tǒng)采用類似算法，只是沒有區(qū)分修改與未修改操作系統(tǒng)采用類似算法，只是沒有區(qū)分修改與未修改頁面。頁面。Windows 2000/XP也是采用可變分配局部置換方式，置也是采用可變分配局部置換方式，置換算法采用換算法采用FIFO，但

45、它設(shè)有，但它設(shè)有4個鏈表：已修改頁面鏈表、后個鏈表：已修改頁面鏈表、后備頁面鏈表、空閑頁面鏈表、清零頁面鏈表。備頁面鏈表、空閑頁面鏈表、清零頁面鏈表。練習(xí)題881. 有一個頁式虛存系統(tǒng)，某進(jìn)程占用有一個頁式虛存系統(tǒng)，某進(jìn)程占用3個內(nèi)存塊，開個內(nèi)存塊，開始時內(nèi)存為空，執(zhí)行如下訪問頁號序列：始時內(nèi)存為空，執(zhí)行如下訪問頁號序列：0，1，2，3，4，1，2，0，5，1，0，1，2，3，2，4，5 (1) 采用先進(jìn)先出（采用先進(jìn)先出（FIFO）置換算法，缺頁次數(shù)是多）置換算法，缺頁次數(shù)是多少？少？(2) 采用采用LRU置換算法，缺頁次數(shù)是多少？置換算法，缺頁次數(shù)是多少？ (3) 若用最優(yōu)（若用最優(yōu)（OP

46、T）算法呢？）算法呢？2. 在一個請求分頁系統(tǒng)中，采用在一個請求分頁系統(tǒng)中，采用LRU頁面置換算法時，頁面置換算法時，假如一個作業(yè)的頁面走向為假如一個作業(yè)的頁面走向為1、3、2、1、1、3、5、1、3、2、1、5，當(dāng)分配給該作業(yè)的物理塊數(shù)，當(dāng)分配給該作業(yè)的物理塊數(shù)M分別為分別為3和和4時，試計算在訪問過程中所發(fā)生的缺頁次數(shù)和缺時，試計算在訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并比較所得結(jié)果。頁率，并比較所得結(jié)果。 4.9 請求分段存儲管理方式 在請求分段系統(tǒng)中，程序運行之前，只需調(diào)入若干分段（不必調(diào)入所有分段），便可啟動運行。當(dāng)所訪問的段不在內(nèi)存時，可請求OS將所缺的段調(diào)入內(nèi)存。像請求分頁系統(tǒng)一樣，為實現(xiàn)請求分段存儲管理功能，同樣需要一定的硬件支持和相應(yīng)的軟件。894.9.1 請求分段中的硬件支持901. 段表機制段表機制v請求分段式管理中，所需的最主要數(shù)據(jù)結(jié)構(gòu)是請求分段式管理中，所需的最主要數(shù)據(jù)結(jié)構(gòu)是段表段表。v由于應(yīng)用程序的段，只有一部分裝入內(nèi)存，故需在段表由于應(yīng)用程序的段，只有一部分裝入內(nèi)存，故需在段表 中增加若干項，以供程序在調(diào)進(jìn)、調(diào)出時參考。中增加若干項，以供程序在調(diào)進(jìn)、調(diào)出時參考。段名段名 段長段長段的段的基址基址存取存取方式方式訪問訪問字段字段A修改修改位位M存在存在位位P增補增補位位外存外存始址始址增加了以下諸項：增加了以下諸項：存取方式存取方式：用于標(biāo)識本分段的存