操作系統(tǒng)第七章

1、1內(nèi)存管理內(nèi)存管理 ( (Memory Management) )第第 7 章章2存儲(chǔ)管理存儲(chǔ)管理存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，所以存存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要組成部分，所以存儲(chǔ)器的管理是操作系統(tǒng)最主要的功能之一。儲(chǔ)器的管理是操作系統(tǒng)最主要的功能之一。程序的指令和數(shù)據(jù)只有被調(diào)入內(nèi)存（程序的指令和數(shù)據(jù)只有被調(diào)入內(nèi)存（RAM）里里才能被才能被CPU直接訪問，程序才能夠被執(zhí)行。直接訪問，程序才能夠被執(zhí)行。軟件系統(tǒng)需要的內(nèi)存容量在不斷地增加，所以軟件系統(tǒng)需要的內(nèi)存容量在不斷地增加，所以內(nèi)存的容量仍然是計(jì)算機(jī)硬件中最關(guān)鍵的、且內(nèi)存的容量仍然是計(jì)算機(jī)硬件中最關(guān)鍵的、且又是最緊張的又是最緊張的“瓶頸瓶頸”

2、資源。如何對(duì)存儲(chǔ)器進(jìn)資源。如何對(duì)存儲(chǔ)器進(jìn)行有效的管理，不僅直接影響到它的利用率，行有效的管理，不僅直接影響到它的利用率，而且還對(duì)系統(tǒng)的性能有重大影響。而且還對(duì)系統(tǒng)的性能有重大影響。存儲(chǔ)管理的主要對(duì)象是內(nèi)存。存儲(chǔ)管理的主要對(duì)象是內(nèi)存。 3教學(xué)要求教學(xué)要求熟悉熟悉存儲(chǔ)管理目的和存儲(chǔ)管理目的和功能，掌握地址重定位的概念。功能，掌握地址重定位的概念。熟悉熟悉固定分區(qū)分配、固定分區(qū)分配、動(dòng)態(tài)分區(qū)分配的動(dòng)態(tài)分區(qū)分配的實(shí)現(xiàn)實(shí)現(xiàn)原理；原理；掌握掌握可變分區(qū)分配的可變分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)和分配分配回收算法，回收算法，熟悉熟悉可變可變分區(qū)碎片和拼接技術(shù)分區(qū)碎片和拼接技術(shù) 。熟練掌握熟練掌握分頁存儲(chǔ)管理分頁

3、存儲(chǔ)管理原理，原理，熟練掌握熟練掌握分頁存儲(chǔ)管理分頁存儲(chǔ)管理基本的地址變換機(jī)構(gòu)和具有快表的地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu)和具有快表的地址變換機(jī)構(gòu)。掌握掌握分段存儲(chǔ)管理分段存儲(chǔ)管理原理和原理和分段地址變換機(jī)構(gòu)，分段地址變換機(jī)構(gòu)，掌握分掌握分頁和分段比較，熟頁和分段比較，熟悉悉分頁和分段的共享，掌握分頁和分段的共享，掌握段頁段頁式式存儲(chǔ)管理存儲(chǔ)管理原理和原理和地址變換機(jī)構(gòu)。地址變換機(jī)構(gòu)。4教學(xué)要求教學(xué)要求-1掌握掌握虛擬存儲(chǔ)器的虛擬存儲(chǔ)器的理論基礎(chǔ)和定義，理論基礎(chǔ)和定義，熟悉虛擬存熟悉虛擬存儲(chǔ)儲(chǔ)器器實(shí)現(xiàn)方式和實(shí)現(xiàn)方式和特征。特征。掌握請(qǐng)求分頁的頁表機(jī)制、缺頁中斷機(jī)構(gòu)和地址掌握請(qǐng)求分頁的頁表機(jī)制、缺

4、頁中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)，變換機(jī)構(gòu)，熟悉熟悉頁面的分配和置換策略、頁面的頁面的分配和置換策略、頁面的分配的算法。分配的算法。熟練掌握最佳置換算法、先進(jìn)先出（熟練掌握最佳置換算法、先進(jìn)先出（FIFOFIFO）置換置換算法、最近最久未使用置換算法算法、最近最久未使用置換算法LRULRU，熟悉熟悉ClockClock置換算法和置換算法和頁面緩沖算法；頁面緩沖算法；了解工作集概念。了解工作集概念。掌握請(qǐng)求分段的段表機(jī)制、缺段中斷機(jī)構(gòu)和地址掌握請(qǐng)求分段的段表機(jī)制、缺段中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)，變換機(jī)構(gòu)，熟悉熟悉分段的共享和保護(hù)。分段的共享和保護(hù)。5內(nèi)存管理內(nèi)存管理內(nèi)存通常被分為兩部分：操作系統(tǒng)和用戶程內(nèi)存

5、通常被分為兩部分：操作系統(tǒng)和用戶程序。序。內(nèi)存管理的核心是進(jìn)一步細(xì)分用戶可訪問的內(nèi)存管理的核心是進(jìn)一步細(xì)分用戶可訪問的內(nèi)存部分，以滿足多個(gè)進(jìn)程的要求。內(nèi)存部分，以滿足多個(gè)進(jìn)程的要求。如何分配內(nèi)存空間？如何分配內(nèi)存空間？必須有效地分配內(nèi)存以保證有適當(dāng)數(shù)目的必須有效地分配內(nèi)存以保證有適當(dāng)數(shù)目的就緒進(jìn)程可以運(yùn)行，以提高處理器的利用就緒進(jìn)程可以運(yùn)行，以提高處理器的利用率。率。6內(nèi)存管理的功能內(nèi)存管理的功能 1.1.內(nèi)存分配內(nèi)存分配 內(nèi)存分配的主要任務(wù)是：為每一道程序分配內(nèi)存空間，內(nèi)存分配的主要任務(wù)是：為每一道程序分配內(nèi)存空間，使它們使它們“各得其所各得其所”；當(dāng)程序撤消時(shí)，則收回它占用；當(dāng)程序撤消時(shí)，

6、則收回它占用的內(nèi)存空間。分配時(shí)注意提高存儲(chǔ)器的利用率。的內(nèi)存空間。分配時(shí)注意提高存儲(chǔ)器的利用率。2 2. .地址映射地址映射 目標(biāo)程序所訪問的地址是邏輯地址集合的地址空間，目標(biāo)程序所訪問的地址是邏輯地址集合的地址空間，而內(nèi)存空間是內(nèi)存中物理地址的集合，在多道程序環(huán)而內(nèi)存空間是內(nèi)存中物理地址的集合，在多道程序環(huán)境下，這兩者是不一致的，因此，存儲(chǔ)管理必須提供境下，這兩者是不一致的，因此，存儲(chǔ)管理必須提供地址映射功能，用于把程序地址空間中的邏輯地址轉(zhuǎn)地址映射功能，用于把程序地址空間中的邏輯地址轉(zhuǎn)換為內(nèi)存空間中對(duì)應(yīng)的物理地址。換為內(nèi)存空間中對(duì)應(yīng)的物理地址。 73 3. .存儲(chǔ)保護(hù)存儲(chǔ)保護(hù) 內(nèi)存保護(hù)的任

7、務(wù)是確保每道程序都在自己的內(nèi)存空內(nèi)存保護(hù)的任務(wù)是確保每道程序都在自己的內(nèi)存空間運(yùn)行，互不干擾。間運(yùn)行，互不干擾。保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯（有意或無意的），不允許用戶程序讀寫不屬于自（有意或無意的），不允許用戶程序讀寫不屬于自己地址空間的數(shù)據(jù)（系統(tǒng)區(qū)地址空間，其他用戶程己地址空間的數(shù)據(jù)（系統(tǒng)區(qū)地址空間，其他用戶程序的地址空間）。序的地址空間）。 4 4. .提高主存儲(chǔ)器的利用率提高主存儲(chǔ)器的利用率減少不可用的存儲(chǔ)空間（稱為減少不可用的存儲(chǔ)空間（稱為“碎片碎片”、“零零頭頭”），允許），允許多道程序多道程序動(dòng)態(tài)共享主存。動(dòng)態(tài)共享主存。5.內(nèi)存內(nèi)存擴(kuò)充擴(kuò)充 內(nèi)存內(nèi)存擴(kuò)充的

8、任務(wù)是從邏輯上來擴(kuò)充內(nèi)存容量，使用擴(kuò)充的任務(wù)是從邏輯上來擴(kuò)充內(nèi)存容量，使用戶認(rèn)為系統(tǒng)所擁有的內(nèi)存空間遠(yuǎn)比其實(shí)際的內(nèi)存空戶認(rèn)為系統(tǒng)所擁有的內(nèi)存空間遠(yuǎn)比其實(shí)際的內(nèi)存空間（硬件間（硬件RAMRAM）大的多。大的多。87.1.1 7.1.1 地址重定位地址重定位 1. 名字空間、地址空間和存儲(chǔ)空間名字空間、地址空間和存儲(chǔ)空間 在源程序中，是通過符號(hào)名來訪問子程序和數(shù)據(jù)在源程序中，是通過符號(hào)名來訪問子程序和數(shù)據(jù)的，我們把程序中符號(hào)名的集合稱為的，我們把程序中符號(hào)名的集合稱為“名字空間名字空間”。匯編語言源程序經(jīng)過匯編，或者高級(jí)語言源程序經(jīng)匯編語言源程序經(jīng)過匯編，或者高級(jí)語言源程序經(jīng)過編譯，過編譯，得到的

9、目標(biāo)程序是以得到的目標(biāo)程序是以“0”作為參考地址的作為參考地址的模塊模塊。然后多個(gè)目標(biāo)模塊由連接程序連接成一個(gè)具。然后多個(gè)目標(biāo)模塊由連接程序連接成一個(gè)具有統(tǒng)一地址的裝配模塊，以便最后裝入內(nèi)存中執(zhí)行。有統(tǒng)一地址的裝配模塊，以便最后裝入內(nèi)存中執(zhí)行。我們把目標(biāo)模塊中的地址稱為相對(duì)地址（或稱為我們把目標(biāo)模塊中的地址稱為相對(duì)地址（或稱為“邏輯地址邏輯地址”），而把相對(duì)地址的集合稱為），而把相對(duì)地址的集合稱為“相對(duì)相對(duì)地址空間地址空間/邏輯地址空間邏輯地址空間”或簡(jiǎn)稱為或簡(jiǎn)稱為“地址空間地址空間”。9將裝配模塊裝入內(nèi)存執(zhí)行時(shí)，需要確定裝入內(nèi)存的將裝配模塊裝入內(nèi)存執(zhí)行時(shí)，需要確定裝入內(nèi)存的實(shí)際物理地址，并修

10、改程序中與地址有關(guān)的代碼，實(shí)際物理地址，并修改程序中與地址有關(guān)的代碼，這一過程稱為地址重定位。這一過程稱為地址重定位。地址空間的程序和數(shù)據(jù)經(jīng)過地址重定位處理后，就地址空間的程序和數(shù)據(jù)經(jīng)過地址重定位處理后，就變成了可由變成了可由CPU直接執(zhí)行的絕對(duì)地址程序（物理地直接執(zhí)行的絕對(duì)地址程序（物理地址）。我們把這一地址集合稱為址）。我們把這一地址集合稱為“絕對(duì)地址空間絕對(duì)地址空間”或或“存儲(chǔ)空間存儲(chǔ)空間”。10程序的名字空間、地址空間和存儲(chǔ)空間程序的名字空間、地址空間和存儲(chǔ)空間 符號(hào)符號(hào)源程序源程序L o a d A,data1相 對(duì) 目 標(biāo)相 對(duì) 目 標(biāo)程 序 （ 裝程 序 （ 裝配模塊）配模塊）L

11、oad A,200絕對(duì)目標(biāo)絕對(duì)目標(biāo)程序程序Load A,55200名字空名字空間間 地址空間地址空間 相對(duì)地址相對(duì)地址/邏輯地址空間邏輯地址空間存儲(chǔ)空間存儲(chǔ)空間絕對(duì)地址絕對(duì)地址/物理地址空間物理地址空間匯編匯編/編編譯譯連連 接接地址重定地址重定位位裝裝 入入11邏輯地址、物理地址和地址映射邏輯地址、物理地址和地址映射地址映射地址映射BA=1000Load A 200 3456 。 。 。1200物理地址空間物理地址空間Load A data1data1 3456源程序源程序Load A 200 34560100200編譯連接編譯連接邏輯地址空間邏輯地址空間12地址地址邏輯地址邏輯地址 (Lo

12、gical)程序員訪問的地址，與當(dāng)前數(shù)據(jù)在內(nèi)存中的實(shí)際程序員訪問的地址，與當(dāng)前數(shù)據(jù)在內(nèi)存中的實(shí)際位置無關(guān)位置無關(guān)在進(jìn)行內(nèi)存訪問時(shí)，必須將其轉(zhuǎn)換成物理地址在進(jìn)行內(nèi)存訪問時(shí)，必須將其轉(zhuǎn)換成物理地址相對(duì)地址相對(duì)地址 (Relative)邏輯地址的特例邏輯地址的特例相對(duì)于某些已知點(diǎn)（通常的程序開始處）的存儲(chǔ)相對(duì)于某些已知點(diǎn)（通常的程序開始處）的存儲(chǔ)單元單元物理地址物理地址(Physical)也稱為絕對(duì)地址也稱為絕對(duì)地址是數(shù)據(jù)在主存中的實(shí)際位置是數(shù)據(jù)在主存中的實(shí)際位置132. 地址重定位的分類地址重定位的分類 地址重定位，也稱地址映射（地址重定位，也稱地址映射（map），它將相，它將相對(duì)地址轉(zhuǎn)換成內(nèi)存中

13、的絕對(duì)地址。按照重定位的對(duì)地址轉(zhuǎn)換成內(nèi)存中的絕對(duì)地址。按照重定位的時(shí)機(jī)，可分為靜態(tài)重定位和動(dòng)態(tài)重定位。時(shí)機(jī)，可分為靜態(tài)重定位和動(dòng)態(tài)重定位。靜態(tài)重定位靜態(tài)重定位 靜態(tài)重定位靜態(tài)重定位是在程序執(zhí)行之前進(jìn)行重定位。它是在程序執(zhí)行之前進(jìn)行重定位。它根據(jù)裝配模塊將要裝入的內(nèi)存起始地址，直接修根據(jù)裝配模塊將要裝入的內(nèi)存起始地址，直接修改裝配模塊中的有關(guān)使用地址的指令。改裝配模塊中的有關(guān)使用地址的指令。 在在圖中以圖中以“0”作為參考地址的裝配模塊，要作為參考地址的裝配模塊，要裝入以裝入以10000為起始地址的存儲(chǔ)空間。顯然在裝入為起始地址的存儲(chǔ)空間。顯然在裝入程序之前，程序必須做一些修改才能正確運(yùn)行。程序

14、之前，程序必須做一些修改才能正確運(yùn)行。14例如：例如：LOAD 1，2500 這條指令是把相對(duì)地址為這條指令是把相對(duì)地址為2500的的存儲(chǔ)單元的內(nèi)容存儲(chǔ)單元的內(nèi)容365裝入裝入1號(hào)累加器。而這時(shí)內(nèi)容為號(hào)累加器。而這時(shí)內(nèi)容為365的存儲(chǔ)單元的實(shí)際物理地址為的存儲(chǔ)單元的實(shí)際物理地址為12500（起始地址（起始地址10000+相對(duì)地址相對(duì)地址2500），所以），所以LOAD 1，2500 這條指令中的直這條指令中的直接地址碼要作相應(yīng)的修改，即改為接地址碼要作相應(yīng)的修改，即改為L(zhǎng)OAD 1，12500。 L O A D 1 ，25003650100：2500：2600：L O A D 1L O A D

15、 1 ，125001250036510000：10100：12500：12600：程序的地址空間程序的地址空間內(nèi)存的地址空間內(nèi)存的地址空間15靜態(tài)重定位雖然有無須硬件支持靜態(tài)重定位雖然有無須硬件支持的優(yōu)點(diǎn)，但是也存在明顯的缺點(diǎn)：的優(yōu)點(diǎn)，但是也存在明顯的缺點(diǎn)：一是程序重定位以后就不能在內(nèi)一是程序重定位以后就不能在內(nèi)存中移動(dòng)；二是要求程序的存儲(chǔ)存中移動(dòng)；二是要求程序的存儲(chǔ)空間是連續(xù)的，不能把程序存儲(chǔ)空間是連續(xù)的，不能把程序存儲(chǔ)到若干個(gè)不連續(xù)的區(qū)域中。到若干個(gè)不連續(xù)的區(qū)域中。在在重定位表重定位表中列出要修改的位置。中列出要修改的位置。如：重定位表的如：重定位表的150150表示相對(duì)地表示相對(duì)地址址1

16、50150處的內(nèi)容為相對(duì)地址處的內(nèi)容為相對(duì)地址( (即即100100為從為從0 0起頭的相對(duì)位置起頭的相對(duì)位置) )。在。在裝入時(shí)，要依據(jù)重定位后的起頭裝入時(shí)，要依據(jù)重定位后的起頭位置位置(2000)(2000)修改相對(duì)地址。修改相對(duì)地址。重定位修改：重定位表中的重定位修改：重定位表中的150-150-絕對(duì)地址絕對(duì)地址2150(=2000+150)2150(=2000+150)內(nèi)容修改：內(nèi)容內(nèi)容修改：內(nèi)容100100變成變成2100(=100+2000) 2100(=100+2000) 。jmp150100150.RelocationTable0jm200016動(dòng)態(tài)重

17、定位動(dòng)態(tài)重定位是指在程序執(zhí)行過程中進(jìn)行地址重定位，是指在程序執(zhí)行過程中進(jìn)行地址重定位，即在每次訪問內(nèi)存單元前才進(jìn)行地址變換。即在每次訪問內(nèi)存單元前才進(jìn)行地址變換。動(dòng)態(tài)重動(dòng)態(tài)重定位可使裝配模塊不加任何修改就裝入內(nèi)存，但是定位可使裝配模塊不加任何修改就裝入內(nèi)存，但是它需要硬件它需要硬件重定位寄存器的支持。重定位寄存器的支持。程序的目標(biāo)模塊在裝入內(nèi)存時(shí)，與地址有關(guān)的指令程序的目標(biāo)模塊在裝入內(nèi)存時(shí)，與地址有關(guān)的指令都無須進(jìn)行修改。當(dāng)該指令被操作系統(tǒng)取到中央處都無須進(jìn)行修改。當(dāng)該指令被操作系統(tǒng)取到中央處理器理器指令寄存器指令寄存器IRIR上執(zhí)行時(shí)，操作系統(tǒng)首先把該模上執(zhí)行時(shí)，操作系統(tǒng)首先把該模塊裝入的實(shí)

18、際起始地址減去目標(biāo)模塊的相對(duì)基地址，塊裝入的實(shí)際起始地址減去目標(biāo)模塊的相對(duì)基地址，然后將其差值裝入重定位寄存器。然后將其差值裝入重定位寄存器。當(dāng)當(dāng)CPU執(zhí)行該指令時(shí)，地址變換硬件邏輯自動(dòng)將指執(zhí)行該指令時(shí)，地址變換硬件邏輯自動(dòng)將指令中的邏輯地址與重定位寄存器中的值相加，令中的邏輯地址與重定位寄存器中的值相加，再根再根據(jù)和值作為內(nèi)存的絕對(duì)地址去訪問該單元的數(shù)據(jù)據(jù)和值作為內(nèi)存的絕對(duì)地址去訪問該單元的數(shù)據(jù)，讀入的數(shù)據(jù)送到讀入的數(shù)據(jù)送到寄存器寄存器1 1。完成地址變換硬件是屬。完成地址變換硬件是屬于于存儲(chǔ)管理部件存儲(chǔ)管理部件 MMUMMU，目前它已集成到目前它已集成到中央處理器中央處理器CPUCPU中。

19、中。 17動(dòng)態(tài)重定位動(dòng)態(tài)重定位L O A D 1 ，25003650：10025002600程序的地址空程序的地址空間間L O A D 1 ，2500365100001010012500物理地址內(nèi)存的地址空間重定位寄存重定位寄存器重定位寄存器中央處理器中央處理器CPUCPU指令寄存器指令寄存器LOAD LOAD 1,25001,25002500(2500(邏輯地址邏輯地址) )MMU(存儲(chǔ)管理部件存儲(chǔ)管理部件)CPU芯片+ +1000018動(dòng)態(tài)重定位的特性動(dòng)態(tài)重定位的特性動(dòng)態(tài)重定位是在指令執(zhí)行過程中動(dòng)態(tài)進(jìn)行，它由動(dòng)態(tài)重定位是在指令執(zhí)行過程中動(dòng)態(tài)進(jìn)行，它由硬件完成，硬件完成，這樣可以帶來兩個(gè)好處

20、：這樣可以帶來兩個(gè)好處：目標(biāo)程序裝入內(nèi)存時(shí)無需任何修改，所以裝入目標(biāo)程序裝入內(nèi)存時(shí)無需任何修改，所以裝入之后再移動(dòng)也不會(huì)影響其正確運(yùn)行，這便于存之后再移動(dòng)也不會(huì)影響其正確運(yùn)行，這便于存儲(chǔ)器用壓縮技術(shù)來解決碎片問題。儲(chǔ)器用壓縮技術(shù)來解決碎片問題。一個(gè)程序由若干個(gè)相對(duì)獨(dú)立的目標(biāo)模塊組成時(shí)，一個(gè)程序由若干個(gè)相對(duì)獨(dú)立的目標(biāo)模塊組成時(shí)，每個(gè)目標(biāo)模塊各裝入一個(gè)存儲(chǔ)區(qū)域，這些存儲(chǔ)每個(gè)目標(biāo)模塊各裝入一個(gè)存儲(chǔ)區(qū)域，這些存儲(chǔ)區(qū)域可以不相鄰接，只要各個(gè)模塊有自己對(duì)應(yīng)區(qū)域可以不相鄰接，只要各個(gè)模塊有自己對(duì)應(yīng)的重定位寄存器就可以了。的重定位寄存器就可以了。19例子例子一個(gè)程序包含一段重定位代碼，假設(shè)第一一個(gè)程序包含一段

21、重定位代碼，假設(shè)第一次讀進(jìn)內(nèi)存次讀進(jìn)內(nèi)存100的起始地址中。此時(shí)，程的起始地址中。此時(shí)，程序按下述地址進(jìn)行訪問：序按下述地址進(jìn)行訪問：150, 188和和244。如果該程序第二次讀進(jìn)內(nèi)存時(shí)，被重定位如果該程序第二次讀進(jìn)內(nèi)存時(shí)，被重定位到內(nèi)存到內(nèi)存150的起始地址中，為了正確地訪的起始地址中，為了正確地訪問數(shù)據(jù)，上述那些地址將如何調(diào)整？問數(shù)據(jù)，上述那些地址將如何調(diào)整？ Q:200,238,294207.2 內(nèi)存分區(qū)內(nèi)存分區(qū)內(nèi)存管理最基本的操作是內(nèi)存管理最基本的操作是由處理器將程序裝入主存由處理器將程序裝入主存中執(zhí)行。中執(zhí)行。 如何將程序裝入主存？如何將程序裝入主存？固定分區(qū)固定分區(qū) (Fixed

22、 Partitioning)動(dòng)態(tài)分區(qū)動(dòng)態(tài)分區(qū) (Dynamic Partitioning)簡(jiǎn)單分頁簡(jiǎn)單分頁 (Simple Paging)簡(jiǎn)單分段簡(jiǎn)單分段 (Simple Segmentation)虛擬分頁虛擬分頁 (Virtual-Memory Paging)虛擬分段虛擬分段 (Virtual-Memory Segmentation)21分區(qū)分區(qū)存儲(chǔ)管理方式存儲(chǔ)管理方式分區(qū)存儲(chǔ)管理是能夠滿足多道程序運(yùn)行的分區(qū)存儲(chǔ)管理是能夠滿足多道程序運(yùn)行的最簡(jiǎn)單的存儲(chǔ)器管理方案，最簡(jiǎn)單的存儲(chǔ)器管理方案，其基本思想是其基本思想是將內(nèi)存劃分成若干個(gè)連續(xù)的區(qū)域，稱為分將內(nèi)存劃分成若干個(gè)連續(xù)的區(qū)域，稱為分區(qū)區(qū)。每個(gè)

23、分區(qū)只能儲(chǔ)存一個(gè)程序，而且程序也每個(gè)分區(qū)只能儲(chǔ)存一個(gè)程序，而且程序也只能在它所駐留的分區(qū)中運(yùn)行。只能在它所駐留的分區(qū)中運(yùn)行。分區(qū)存儲(chǔ)管理根據(jù)分區(qū)個(gè)數(shù)及分區(qū)大小的分區(qū)存儲(chǔ)管理根據(jù)分區(qū)個(gè)數(shù)及分區(qū)大小的可變性分為固定分區(qū)和動(dòng)態(tài)分區(qū)兩種?？勺冃苑譃楣潭ǚ謪^(qū)和動(dòng)態(tài)分區(qū)兩種。22固定分區(qū)固定分區(qū)在作業(yè)裝入之前，系統(tǒng)管理員或操作系統(tǒng)在作業(yè)裝入之前，系統(tǒng)管理員或操作系統(tǒng)事先事先將內(nèi)將內(nèi)存劃分成若干個(gè)分區(qū)。一旦劃分完成，在系統(tǒng)運(yùn)行存劃分成若干個(gè)分區(qū)。一旦劃分完成，在系統(tǒng)運(yùn)行期間不再重新劃分，即分區(qū)的個(gè)數(shù)不可變，分區(qū)的期間不再重新劃分，即分區(qū)的個(gè)數(shù)不可變，分區(qū)的大小不可變，所以，固定式分區(qū)又稱為靜態(tài)分區(qū)。大小不可

24、變，所以，固定式分區(qū)又稱為靜態(tài)分區(qū)。可劃分為大小相等的分區(qū)可劃分為大小相等的分區(qū) (Equal-size partitions) 和大小不等的分區(qū)和大小不等的分區(qū)(Unequal-size partitions) 任何小于或等于分區(qū)大小的進(jìn)程都可以裝入到任任何小于或等于分區(qū)大小的進(jìn)程都可以裝入到任何可用的分區(qū)中。何可用的分區(qū)中。如果所有的分區(qū)都滿了，系統(tǒng)可以換出一個(gè)進(jìn)程，如果所有的分區(qū)都滿了，系統(tǒng)可以換出一個(gè)進(jìn)程，將其所占用的分區(qū)分配給另一個(gè)進(jìn)程使用。將其所占用的分區(qū)分配給另一個(gè)進(jìn)程使用。2324區(qū)號(hào)區(qū)號(hào) 大小大小 起址起址 標(biāo)志標(biāo)志 1 16KB 20K 已分配已分配 2 32KB 36K

25、已分配已分配 3 64KB 68K 已分配已分配 4 124KB 132K 未分配未分配 (a) 分區(qū)說明表分區(qū)說明表系統(tǒng)維護(hù)了一張分區(qū)說明表，系統(tǒng)維護(hù)了一張分區(qū)說明表，每個(gè)表目說明一個(gè)分區(qū)的大每個(gè)表目說明一個(gè)分區(qū)的大小、起始地址和是否已分配。小、起始地址和是否已分配。 0k： 20k： 36k： 68k： 132k： 256k 內(nèi)存分配圖內(nèi)存分配圖 操作系統(tǒng)作業(yè)A（16k）作業(yè)B（26k）作業(yè)C（56k）第第1分區(qū)（分區(qū)（16kb） （已分配）（已分配）第第2分區(qū)（分區(qū)（32kb） （已分配）（已分配）第第3分區(qū)（分區(qū)（64kb） （已分配）已分配）4分區(qū)（分區(qū)（124kb ） （未分配）未

26、分配） 25存在兩個(gè)問題存在兩個(gè)問題程序可能太大而不能放到一個(gè)分區(qū)中，必須使用覆程序可能太大而不能放到一個(gè)分區(qū)中，必須使用覆蓋技術(shù)，使得在任何時(shí)候該程序只有一部分放到主蓋技術(shù)，使得在任何時(shí)候該程序只有一部分放到主存中。存中。主存的利用率不高。任何進(jìn)程，即使很小，都需要主存的利用率不高。任何進(jìn)程，即使很小，都需要占據(jù)一個(gè)完整的分區(qū)。占據(jù)一個(gè)完整的分區(qū)。 一個(gè)進(jìn)程的大小不可能正一個(gè)進(jìn)程的大小不可能正好等于某個(gè)分區(qū)的大小，好等于某個(gè)分區(qū)的大小，所以每個(gè)被分配的分區(qū)內(nèi)所以每個(gè)被分配的分區(qū)內(nèi)總有一部分被浪費(fèi)，我們把這部分被浪費(fèi)的存儲(chǔ)區(qū)總有一部分被浪費(fèi)，我們把這部分被浪費(fèi)的存儲(chǔ)區(qū)稱為內(nèi)部碎片稱為內(nèi)部碎片(

27、 fragmentation)或內(nèi)零頭?；騼?nèi)零頭。如上圖所示中第3分區(qū)未分配的部分還有8KB，加上第4分區(qū)的124KB共計(jì)132KB，而且這132KB的內(nèi)存空間在物理上是一個(gè)連續(xù)的區(qū)域，這時(shí)如果有一個(gè)大小為130KB的作業(yè)申請(qǐng)內(nèi)存，卻被拒絕，因?yàn)榉謪^(qū)的大小是預(yù)先劃分好的，分區(qū)說明表中指出只有第4分區(qū)未分配（大小為124K），且不能改變分區(qū)的大小。26放置算法放置算法大小相等的分區(qū)大小相等的分區(qū)所有分區(qū)大小都相等，只要存在可用的分區(qū)，所有分區(qū)大小都相等，只要存在可用的分區(qū)，進(jìn)程就可以裝入進(jìn)程就可以裝入大小不等的分區(qū)大小不等的分區(qū)把每個(gè)進(jìn)程指定到足夠容納它的最小分區(qū)把每個(gè)進(jìn)程指定到足夠容納它的最小

28、分區(qū)每個(gè)分區(qū)維護(hù)一個(gè)隊(duì)列，保存該分區(qū)換出的進(jìn)程每個(gè)分區(qū)維護(hù)一個(gè)隊(duì)列，保存該分區(qū)換出的進(jìn)程可使每個(gè)分區(qū)內(nèi)的碎片最少可使每個(gè)分區(qū)內(nèi)的碎片最少改進(jìn)：把每個(gè)進(jìn)程指定到可容納它的最小可用改進(jìn)：把每個(gè)進(jìn)程指定到可容納它的最小可用分區(qū)中分區(qū)中所有分區(qū)只提供一個(gè)隊(duì)列所有分區(qū)只提供一個(gè)隊(duì)列2728固定分區(qū)的不足固定分區(qū)的不足分區(qū)的數(shù)目事先生成，因此限制了系統(tǒng)中分區(qū)的數(shù)目事先生成，因此限制了系統(tǒng)中活動(dòng)進(jìn)程的數(shù)目活動(dòng)進(jìn)程的數(shù)目小作業(yè)不能有效地利用分區(qū)空間小作業(yè)不能有效地利用分區(qū)空間存在內(nèi)部碎片問題存在內(nèi)部碎片問題29動(dòng)態(tài)分區(qū)動(dòng)態(tài)分區(qū) (Dynamic Partitioning )(1) (1) 動(dòng)態(tài)分區(qū)概述動(dòng)態(tài)分區(qū)

29、概述 動(dòng)態(tài)分區(qū)是指在作業(yè)裝入內(nèi)存時(shí)，從可用的內(nèi)存動(dòng)態(tài)分區(qū)是指在作業(yè)裝入內(nèi)存時(shí)，從可用的內(nèi)存中劃出一塊連續(xù)的區(qū)域分配給它，且中劃出一塊連續(xù)的區(qū)域分配給它，且分區(qū)大小正分區(qū)大小正好等于該作業(yè)的大小好等于該作業(yè)的大小。 動(dòng)態(tài)分區(qū)中分區(qū)的大小和分區(qū)的個(gè)數(shù)都是可變的，動(dòng)態(tài)分區(qū)中分區(qū)的大小和分區(qū)的個(gè)數(shù)都是可變的，而且是根據(jù)作業(yè)的大小和多少動(dòng)態(tài)地劃分，因此而且是根據(jù)作業(yè)的大小和多少動(dòng)態(tài)地劃分，因此又稱可變分區(qū)。又稱可變分區(qū)。 這種存儲(chǔ)管理技術(shù)是固定式分區(qū)的改進(jìn)，既可以這種存儲(chǔ)管理技術(shù)是固定式分區(qū)的改進(jìn)，既可以獲得較大的靈活性，又能提高內(nèi)存的利用率。獲得較大的靈活性，又能提高內(nèi)存的利用率。30 系統(tǒng)初始化后，

30、內(nèi)存被劃分成兩塊，一塊用系統(tǒng)初始化后，內(nèi)存被劃分成兩塊，一塊用于常駐的操作系統(tǒng)，另一塊則是完整的空閑區(qū)于常駐的操作系統(tǒng)，另一塊則是完整的空閑區(qū)（用戶區(qū)）。對(duì)于調(diào)入的若干個(gè)作業(yè)，劃分幾個(gè)（用戶區(qū)）。對(duì)于調(diào)入的若干個(gè)作業(yè)，劃分幾個(gè)大小不等的分區(qū)給它們，隨著作業(yè)的調(diào)入和撤除，大小不等的分區(qū)給它們，隨著作業(yè)的調(diào)入和撤除，相應(yīng)的分區(qū)被劃分和釋放，原來整塊的存儲(chǔ)區(qū)形相應(yīng)的分區(qū)被劃分和釋放，原來整塊的存儲(chǔ)區(qū)形成空閑區(qū)和已分配區(qū)相間的局面。成空閑區(qū)和已分配區(qū)相間的局面。下圖給出了動(dòng)態(tài)分區(qū)的示例，下圖給出了動(dòng)態(tài)分區(qū)的示例，512512KBKB內(nèi)存中除內(nèi)存中除20KB操作系統(tǒng)外，裝入作業(yè)操作系統(tǒng)外，裝入作業(yè)2、3

31、、4、6四個(gè)，四個(gè)，有空閑區(qū)有空閑區(qū)1、2、3三個(gè)。三個(gè)。 31動(dòng)態(tài)分區(qū)示例動(dòng)態(tài)分區(qū)示例 序號(hào)序號(hào)P P大小大小起址起址狀態(tài)狀態(tài) 1 13232k k20k20k空閑空閑 2 25656k k260k260k空閑空閑 3 116 3 116k k396k396k空閑空閑 4 4空表目空表目 5 5空表目空表目 （a）空閑分區(qū)表前向指針前向指針 N+2 00后向指針后向指針 N+2 00N個(gè)字可用 （b）空閑鏈結(jié)構(gòu)空閑區(qū)（空閑區(qū)（56k）作業(yè)作業(yè)6（80k）空閑區(qū)（空閑區(qū)（116k）空閑區(qū)（空閑區(qū)（32k）作業(yè)作業(yè)2（64k）作業(yè)作業(yè)3（48k）作業(yè)作業(yè)4（96k）操作系統(tǒng)操作系統(tǒng)(20K)0

32、02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K512K返回32可變式分區(qū)的分配和釋放的基本思想是：在分配可變式分區(qū)的分配和釋放的基本思想是：在分配時(shí)，首先找到一個(gè)足夠大的空閑分區(qū)，即這個(gè)空時(shí)，首先找到一個(gè)足夠大的空閑分區(qū)，即這個(gè)空閑區(qū)的大小比作業(yè)要求的要大，系統(tǒng)則將這個(gè)空閑區(qū)的大小比作業(yè)要求的要大，系統(tǒng)則將這個(gè)空閑分區(qū)分成兩部分：一部分成為已分配的分區(qū)閑分區(qū)分成兩部分：一部分成為已分配的分區(qū)（大小正好等于作業(yè)要求的大小），剩余的部分（大小正好等于作業(yè)要求的大?。?，剩余的部分仍作為空閑區(qū)。仍作為空閑區(qū)。在回收撤除作業(yè)所占領(lǐng)的分

33、區(qū)時(shí)，要檢查回收的在回收撤除作業(yè)所占領(lǐng)的分區(qū)時(shí)，要檢查回收的分區(qū)是否與前后空閑的分區(qū)相鄰接，若是，則加分區(qū)是否與前后空閑的分區(qū)相鄰接，若是，則加以合并，使之成為一個(gè)連續(xù)的大空間。以合并，使之成為一個(gè)連續(xù)的大空間。 隨著作業(yè)的不斷分配和撤除，內(nèi)存中會(huì)產(chǎn)生越來隨著作業(yè)的不斷分配和撤除，內(nèi)存中會(huì)產(chǎn)生越來越多的碎片越多的碎片（外部碎片）（外部碎片），內(nèi)存的利用率下降，內(nèi)存的利用率下降，因此，必須定期使用因此，必須定期使用壓縮技術(shù)壓縮技術(shù)(compaction)，移動(dòng)進(jìn)程，使進(jìn)程所占用的空間連續(xù)，并且所有移動(dòng)進(jìn)程，使進(jìn)程所占用的空間連續(xù)，并且所有空閑空間連成一片?？臻e空間連成一片。33外部碎片外部碎片3

34、4動(dòng)態(tài)動(dòng)態(tài)/可變式分區(qū)分配可變式分區(qū)分配(2) (2) 動(dòng)態(tài)分區(qū)的動(dòng)態(tài)分區(qū)的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 空閑區(qū)表空閑區(qū)表形式形式 空閑分區(qū)表為每個(gè)尚未分配的分區(qū)設(shè)置一個(gè)表項(xiàng)，空閑分區(qū)表為每個(gè)尚未分配的分區(qū)設(shè)置一個(gè)表項(xiàng)，包括分區(qū)的序號(hào)、大小、始址和狀態(tài)。包括分區(qū)的序號(hào)、大小、始址和狀態(tài)?？臻e區(qū)鏈空閑區(qū)鏈形式形式 為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，在每個(gè)分區(qū)的為了實(shí)現(xiàn)對(duì)空閑分區(qū)的分配和鏈接，在每個(gè)分區(qū)的起始部分，設(shè)置一些用于控制分區(qū)分配的信息（如分起始部分，設(shè)置一些用于控制分區(qū)分配的信息（如分區(qū)的大小和狀態(tài)位），以及用于鏈接其它分區(qū)的前向區(qū)的大小和狀態(tài)位），以及用于鏈接其它分區(qū)的前向指針；在分區(qū)尾部，則設(shè)置了

35、一個(gè)后向指針，為了檢指針；在分區(qū)尾部，則設(shè)置了一個(gè)后向指針，為了檢索方便也設(shè)置了控制分區(qū)分配的信息。然后，通過前、索方便也設(shè)置了控制分區(qū)分配的信息。然后，通過前、后向指針將所有的分區(qū)鏈接成一個(gè)雙向鏈表。后向指針將所有的分區(qū)鏈接成一個(gè)雙向鏈表。35(3) (3) 動(dòng)態(tài)分區(qū)分配算法動(dòng)態(tài)分區(qū)分配算法 (Partitioning Placement Algorithm)1)1)最佳適應(yīng)算法最佳適應(yīng)算法BFBF（Best FitBest Fit）：）：它從全部空閑區(qū)中找出它從全部空閑區(qū)中找出能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能滿足作業(yè)要求的、且大小最小的空閑分區(qū)，這種方法能使碎片盡量小。為

36、適應(yīng)這種算法，空閑分區(qū)表（空閑能使碎片盡量小。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要區(qū)鏈）中的空閑分區(qū)要按大小按大小從小到大進(jìn)行排序，從小到大進(jìn)行排序，自表自表頭開始查找到第一個(gè)滿足要求的自由分區(qū)分配。頭開始查找到第一個(gè)滿足要求的自由分區(qū)分配。該算法該算法保留大的空閑區(qū)，但造成許多小的空閑區(qū)。保留大的空閑區(qū)，但造成許多小的空閑區(qū)。2)2)首次適應(yīng)算法首次適應(yīng)算法FFFF（First FitFirst Fit）：）：從從空閑分區(qū)表空閑分區(qū)表的第一的第一個(gè)表目起查找該表個(gè)表目起查找該表，把最先能夠滿足要求的空閑區(qū)分配，把最先能夠滿足要求的空閑區(qū)分配給作業(yè)，這種方法目的在于減少查找時(shí)間

37、。為適應(yīng)這種給作業(yè)，這種方法目的在于減少查找時(shí)間。為適應(yīng)這種算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址算法，空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)要按地址由低到高進(jìn)行排序。由低到高進(jìn)行排序。該算法該算法優(yōu)先使用低址部分空閑區(qū)，優(yōu)先使用低址部分空閑區(qū)，在低址空間造成許多小的空閑區(qū)，在高地址空間保留大在低址空間造成許多小的空閑區(qū)，在高地址空間保留大的空閑區(qū)。的空閑區(qū)。363)循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法/鄰近算法鄰近算法NF(Next Fit)：該算法該算法是首次適應(yīng)算法的變種，它把是首次適應(yīng)算法的變種，它把空閑分區(qū)表（空閑空閑分區(qū)表（空閑區(qū)鏈）中的空閑分區(qū)按地址遞增構(gòu)成一個(gè)區(qū)鏈）中的空閑分

38、區(qū)按地址遞增構(gòu)成一個(gè)循環(huán)鏈。循環(huán)鏈。在分配內(nèi)存空間時(shí)，不再每次從表頭（鏈?zhǔn)祝╅_在分配內(nèi)存空間時(shí)，不再每次從表頭（鏈?zhǔn)祝╅_始查找，始查找，而是從上次找到的空閑區(qū)的下一個(gè)空閑而是從上次找到的空閑區(qū)的下一個(gè)空閑區(qū)開始查找區(qū)開始查找，直到找到第一個(gè)能滿足要求的的空，直到找到第一個(gè)能滿足要求的的空閑區(qū)為止，并從中劃出一塊與請(qǐng)求大小相等的內(nèi)閑區(qū)為止，并從中劃出一塊與請(qǐng)求大小相等的內(nèi)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑區(qū)存空間分配給作業(yè)。該算法能使內(nèi)存中的空閑區(qū)分布得比較均勻。分布得比較均勻。(4)最壞適應(yīng)法：最壞適應(yīng)法：從所有未分配的分區(qū)中挑選最大的從所有未分配的分區(qū)中挑選最大的且大于和等于作業(yè)大小的

39、分區(qū)分給要求的作業(yè)；且大于和等于作業(yè)大小的分區(qū)分給要求的作業(yè)；空閑空閑分區(qū)按大小由大到小排序。分區(qū)按大小由大到小排序。該算法使該算法使小的空小的空閑區(qū)減少，但造成大的空閑區(qū)不夠大。閑區(qū)減少，但造成大的空閑區(qū)不夠大。37Lastallocatedblock (14K)BeforeAfter8K8K12K12K22K18K6K6K8K8K14K14K6K2K36K20KNext FitFree blockAllocated blockBest FitFirst Fit例：分配一個(gè)例：分配一個(gè)16KB分區(qū)分區(qū)38（4 4） 可變分區(qū)回收算法可變分區(qū)回收算法 當(dāng)一個(gè)作業(yè)運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)釋放

40、區(qū)當(dāng)一個(gè)作業(yè)運(yùn)行完畢釋放內(nèi)存時(shí)，系統(tǒng)根據(jù)釋放區(qū)的首地址，從空閑區(qū)說明表中找到相應(yīng)的插入點(diǎn)，的首地址，從空閑區(qū)說明表中找到相應(yīng)的插入點(diǎn)，此時(shí)可能出現(xiàn)下列四種情況（如下圖此時(shí)可能出現(xiàn)下列四種情況（如下圖所示，其中所示，其中F1F1，F(xiàn)2F2表示回收區(qū)的前、后空閑區(qū)）表示回收區(qū)的前、后空閑區(qū)）：(1)(1)當(dāng)回收區(qū)既不與當(dāng)回收區(qū)既不與F1F1領(lǐng)接，又不與領(lǐng)接，又不與F2F2領(lǐng)接時(shí)領(lǐng)接時(shí)，應(yīng)為應(yīng)為回收區(qū)單獨(dú)建立一項(xiàng)新表目，填寫回收區(qū)的起址回收區(qū)單獨(dú)建立一項(xiàng)新表目，填寫回收區(qū)的起址和大小，并根據(jù)其起址，插入到空閑區(qū)說明表的和大小，并根據(jù)其起址，插入到空閑區(qū)說明表的適當(dāng)位置。適當(dāng)位置。(2)(2)當(dāng)回收區(qū)

41、只與插入點(diǎn)的前一個(gè)分區(qū)當(dāng)回收區(qū)只與插入點(diǎn)的前一個(gè)分區(qū)F1F1相領(lǐng)接時(shí)相領(lǐng)接時(shí)，應(yīng)將回收區(qū)與插入點(diǎn)的前一個(gè)分區(qū)合并，不再為應(yīng)將回收區(qū)與插入點(diǎn)的前一個(gè)分區(qū)合并，不再為回收區(qū)分配新的表目，而只需修改回收區(qū)分配新的表目，而只需修改F1F1分區(qū)表目的分區(qū)表目的大小即可。大小即可。 39(3)(3)當(dāng)回收區(qū)只與插入點(diǎn)的后一個(gè)分區(qū)當(dāng)回收區(qū)只與插入點(diǎn)的后一個(gè)分區(qū)F2F2相領(lǐng)接時(shí)相領(lǐng)接時(shí)，將把兩個(gè)空閑區(qū)合并，修改將把兩個(gè)空閑區(qū)合并，修改F2F2分區(qū)的表目，把回分區(qū)的表目，把回收區(qū)的起址作為新空閑區(qū)的起址，大小為兩個(gè)分收區(qū)的起址作為新空閑區(qū)的起址，大小為兩個(gè)分區(qū)之和。區(qū)之和。(4)(4)當(dāng)回收區(qū)與插入點(diǎn)的前、后兩

42、個(gè)分區(qū)（當(dāng)回收區(qū)與插入點(diǎn)的前、后兩個(gè)分區(qū)（F1F1和和F2F2）都相領(lǐng)接時(shí)都相領(lǐng)接時(shí)，合并三個(gè)分區(qū)，用合并三個(gè)分區(qū)，用F1F1表目的起址作表目的起址作為新空閑區(qū)的起址，修改其大小為三塊分區(qū)之和，為新空閑區(qū)的起址，修改其大小為三塊分區(qū)之和，最后取消最后取消F2F2的表目。的表目。 40作業(yè)作業(yè)3回收前后回收前后序號(hào)序號(hào)P P大小大小起址起址狀態(tài)狀態(tài) 1 13232k k20k20k空閑空閑 2 25656k k260k260k空閑空閑 3 116 3 116k k396k396k空閑空閑 4 4空表目空表目 5 5空表目空表目 （a）空閑分區(qū)表序號(hào)序號(hào)P P 大小大小 起址起址 狀態(tài)狀態(tài) 1 1

43、 32 32k 20k k 20k 空閑空閑 2 2 4848k 116k k 116k 空閑空閑 3 3 56 56k 260k k 260k 空閑空閑 4 4 116 116k 396k k 396k 空閑空閑 5 5 空表目空表目 空閑分區(qū)表空閑區(qū)空閑區(qū)2（56k）作業(yè)作業(yè)6（80k）空閑區(qū)空閑區(qū)3（116k）空閑區(qū)空閑區(qū)1（32k）作業(yè)作業(yè)2（64k）作業(yè)作業(yè)3（48k） 回收區(qū)回收區(qū)作業(yè)作業(yè)4（96k）操作系統(tǒng)操作系統(tǒng)(20K)0 02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K512K空閑區(qū)空閑區(qū)3（56k）作業(yè)作

44、業(yè)6（80k）空閑區(qū)空閑區(qū)4（116k）空閑區(qū)空閑區(qū)1（32k） 作業(yè)作業(yè)2（64k）空閑區(qū)空閑區(qū)2（48k）作業(yè)作業(yè)4（96k）操作系統(tǒng)操作系統(tǒng)(20K)0 02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K512K 回收前回收前 回收后回收后41空閑區(qū)空閑區(qū)2（56k）作業(yè)作業(yè)6（80k）空閑區(qū)空閑區(qū)3（116k）作業(yè)作業(yè)3 （48k）作業(yè)作業(yè)4（96k）操作系統(tǒng)操作系統(tǒng)(20K)0 02020K K116K116K164K164K260K260K316K316K396K396K512K512K空閑區(qū)空閑區(qū)2（56k）作業(yè)作

45、業(yè)6（80k）空閑區(qū)空閑區(qū)3（116k）空閑區(qū)空閑區(qū)1（32k）作業(yè)作業(yè)2（64k） 回收區(qū)回收區(qū)作業(yè)作業(yè)3（48k） 作業(yè)作業(yè)4（96k）操作系統(tǒng)操作系統(tǒng)(20K)0 02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K512K 回收前回收前 回收后回收后作業(yè)作業(yè)2回收前后回收前后序號(hào)序號(hào)P P大小大小起址起址狀態(tài)狀態(tài) 1 13232k k20k20k空閑空閑 2 25656k k260k260k空閑空閑 3 116 3 116k k396k396k空閑空閑 4 4空表目空表目 5 5空表目空表目 （a）空閑分區(qū)表序號(hào)序號(hào)P P

46、 大小大小 起址起址 狀態(tài)狀態(tài) 1 1 96 96k k 20k 20k 空閑空閑 2 2 56 56k 260k k 260k 空閑空閑 3 3 116 116k 396k k 396k 空閑空閑 4 4 空表目空表目 5 5 空表目空表目 空閑分區(qū)表空閑區(qū)空閑區(qū)1（96k）42作業(yè)作業(yè)4回收前后回收前后序號(hào)序號(hào)P P大小大小起址起址狀態(tài)狀態(tài) 1 13232k k20k20k空閑空閑 2 25656k k260k260k空閑空閑 3 116 3 116k k396k396k空閑空閑 4 4空表目空表目 5 5空表目空表目 （a）空閑分區(qū)表序號(hào)序號(hào)P P 大小大小 起址起址 狀態(tài)狀態(tài) 1 1

47、32 32k 20k k 20k 空閑空閑 2 2 152152k 164kk 164k 空閑空閑 3 3 116 116k 396k k 396k 空閑空閑 4 4 空表目空表目 5 5 空表目空表目 空閑分區(qū)表空閑區(qū)空閑區(qū)2（56k）作業(yè)作業(yè)6（80k）空閑區(qū)空閑區(qū)3（116k）空閑區(qū)空閑區(qū)1（32k）作業(yè)作業(yè)2（64k）作業(yè)作業(yè)3（48k） 作業(yè)作業(yè)4（96k） 回收區(qū)回收區(qū)操作系統(tǒng)操作系統(tǒng)(20K)0 02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K512K空閑區(qū)空閑區(qū)2（152k）作業(yè)作業(yè)6（80k）空閑區(qū)空閑區(qū)3（

48、116k）空閑區(qū)空閑區(qū)1（32k）作業(yè)作業(yè)2（64k）作業(yè)作業(yè)3 （48k）操作系統(tǒng)操作系統(tǒng)(20K)0 02020K K52K52K116K116K164K164K316K316K396K396K512K512K 回收前回收前 回收后回收后43作業(yè)作業(yè)6回收前后回收前后序號(hào)序號(hào)P P大小大小起址起址狀態(tài)狀態(tài) 1 13232k k20k20k空閑空閑 2 25656k k260k260k空閑空閑 3 116 3 116k k396k396k空閑空閑 4 4空表目空表目 5 5空表目空表目 （a）空閑分區(qū)表序號(hào)序號(hào)P P 大小大小 起址起址 狀態(tài)狀態(tài) 1 1 32 32k 20k k 20k 空

49、閑空閑 2 2 252252k k 260k 260k 空閑空閑 3 3 空表目空表目 4 4 空表目空表目 5 5 空表目空表目 空閑分區(qū)表作業(yè)作業(yè)6（80k）空閑區(qū)空閑區(qū)4（116k）空閑區(qū)空閑區(qū)2（56k）作業(yè)作業(yè)6-80k回收回收區(qū)區(qū)空閑區(qū)空閑區(qū)3（116k）空閑區(qū)空閑區(qū)1（32k）作業(yè)作業(yè)2（64k）作業(yè)作業(yè)3（48k） 作業(yè)作業(yè)4（96k）操作系統(tǒng)操作系統(tǒng)(20K)0 02020K K52K52K116K116K164K164K260K260K316K316K396K396K512K512K空閑區(qū)空閑區(qū)2（252k）空閑區(qū)空閑區(qū)1（32k）作業(yè)作業(yè)2（64k）作業(yè)作業(yè)3 （48k）

50、作業(yè)作業(yè)4（96k）操作系統(tǒng)操作系統(tǒng)(20K)0 02020K K52K52K116K116K164K164K260K260K512K512K 回收前回收前 回收后回收后44( (5) 5) 分區(qū)的存儲(chǔ)保護(hù)分區(qū)的存儲(chǔ)保護(hù) 分區(qū)的存儲(chǔ)保護(hù)是用戶程序只能訪問自己的用戶分區(qū)，分區(qū)的存儲(chǔ)保護(hù)是用戶程序只能訪問自己的用戶分區(qū)，不能訪問系統(tǒng)分區(qū)和其它程序的分區(qū)。分區(qū)存儲(chǔ)保護(hù)常不能訪問系統(tǒng)分區(qū)和其它程序的分區(qū)。分區(qū)存儲(chǔ)保護(hù)常用方法是界地址法或界限寄存器。用方法是界地址法或界限寄存器。系統(tǒng)設(shè)置一對(duì)上、下界寄存器，每當(dāng)選中某個(gè)作業(yè)運(yùn)行系統(tǒng)設(shè)置一對(duì)上、下界寄存器，每當(dāng)選中某個(gè)作業(yè)運(yùn)行時(shí)，先將它的界地址裝入這對(duì)寄存

51、器中，作業(yè)運(yùn)行時(shí)形時(shí)，先將它的界地址裝入這對(duì)寄存器中，作業(yè)運(yùn)行時(shí)形成的每一個(gè)訪問存儲(chǔ)器的地址都要同這兩個(gè)寄存器的內(nèi)成的每一個(gè)訪問存儲(chǔ)器的地址都要同這兩個(gè)寄存器的內(nèi)容進(jìn)行比較，若超過這個(gè)指定范圍，就產(chǎn)生越界中斷。容進(jìn)行比較，若超過這個(gè)指定范圍，就產(chǎn)生越界中斷。系統(tǒng)也可以設(shè)置一對(duì)基址、限長(zhǎng)寄存器，此時(shí)基址寄存系統(tǒng)也可以設(shè)置一對(duì)基址、限長(zhǎng)寄存器，此時(shí)基址寄存器還起著重定位寄存器的作用，運(yùn)行進(jìn)程所在分區(qū)的始器還起著重定位寄存器的作用，運(yùn)行進(jìn)程所在分區(qū)的始址和大小分別裝入基址和限長(zhǎng)寄存器。界限址和大小分別裝入基址和限長(zhǎng)寄存器。界限寄存器用硬寄存器用硬件實(shí)現(xiàn)，它是存儲(chǔ)管理部件件實(shí)現(xiàn)，它是存儲(chǔ)管理部件MMU

52、MMU的一部分。的一部分。45程序開始地址程序開始地址程序終止位置程序終止位置若不在界限范圍內(nèi)，若不在界限范圍內(nèi)，則產(chǎn)生中斷則產(chǎn)生中斷基地址寄存器基地址寄存器+相對(duì)地址相對(duì)地址46伙伴系統(tǒng)伙伴系統(tǒng) (Buddy System)可用于分配的整個(gè)內(nèi)存空間看做一個(gè)大小為可用于分配的整個(gè)內(nèi)存空間看做一個(gè)大小為2U的塊的塊如果請(qǐng)求分配的空間大小如果請(qǐng)求分配的空間大小s滿足滿足2U-1 s = 2U, 則分配整個(gè)空間塊（則分配整個(gè)空間塊（2U） 否則，將否則，將2U 一分為二，分為兩個(gè)大小相等一分為二，分為兩個(gè)大小相等的伙伴，大小均為的伙伴，大小均為2U-1 這個(gè)過程一直繼續(xù)，直到產(chǎn)生大于或等于這個(gè)過程一

53、直繼續(xù)，直到產(chǎn)生大于或等于s的最小塊，并分配給該請(qǐng)求。的最小塊，并分配給該請(qǐng)求?？捎枚鏄鋪肀硎荆瑯涞娜~節(jié)點(diǎn)表示內(nèi)存中的可用二叉樹來表示，樹的葉節(jié)點(diǎn)表示內(nèi)存中的當(dāng)前分區(qū)。如果兩個(gè)伙伴都是葉節(jié)點(diǎn)且都未分當(dāng)前分區(qū)。如果兩個(gè)伙伴都是葉節(jié)點(diǎn)且都未分配，則必須將它們合成一個(gè)更大的塊。配，則必須將它們合成一個(gè)更大的塊。474849存儲(chǔ)器的離散分配存儲(chǔ)器的離散分配 連續(xù)分配要求程序必須分配到連續(xù)的地址空間即連續(xù)分配要求程序必須分配到連續(xù)的地址空間即分區(qū)中，因而會(huì)形成許多分區(qū)中，因而會(huì)形成許多“碎片碎片”（內(nèi)部碎片和（內(nèi)部碎片和外部碎片）外部碎片）如何減少碎片？如何減少碎片？將程序劃分成若干個(gè)大小相等的頁（分

54、頁）或?qū)⒊绦騽澐殖扇舾蓚€(gè)大小相等的頁（分頁）或大小不等的段（分段）大小不等的段（分段）以頁或段為單位來分配，將一個(gè)程序的若干頁以頁或段為單位來分配，將一個(gè)程序的若干頁或若干段離散地分配到內(nèi)存的多個(gè)不相鄰的區(qū)或若干段離散地分配到內(nèi)存的多個(gè)不相鄰的區(qū)域中。域中。 507 73 3分頁分頁(Paging)(Paging)存儲(chǔ)管理方式存儲(chǔ)管理方式1分頁存儲(chǔ)管理分頁存儲(chǔ)管理原理原理 分頁存儲(chǔ)管理是將一個(gè)進(jìn)程的地址空間劃分成若干分頁存儲(chǔ)管理是將一個(gè)進(jìn)程的地址空間劃分成若干個(gè)大小相等的片，稱為頁面或個(gè)大小相等的片，稱為頁面或頁頁，相應(yīng)地，將內(nèi)存，相應(yīng)地，將內(nèi)存空間劃分成與頁相同大小的若干個(gè)塊，稱為（物理）空

55、間劃分成與頁相同大小的若干個(gè)塊，稱為（物理）幀（塊）幀（塊）或頁幀。在為進(jìn)程分配內(nèi)存時(shí)，將進(jìn)程中或頁幀。在為進(jìn)程分配內(nèi)存時(shí)，將進(jìn)程中的若干頁離散地裝入不相鄰接的物理幀中。的若干頁離散地裝入不相鄰接的物理幀中。頁面的大小通常在頁面的大小通常在512512B B到到4 4KBKB之間，每塊物理塊可之間，每塊物理塊可離散地分配給進(jìn)程的一頁，這樣不斷地分配，直到離散地分配給進(jìn)程的一頁，這樣不斷地分配，直到剩余的物理塊數(shù)不能滿足一個(gè)進(jìn)程的要求為止。而剩余的物理塊數(shù)不能滿足一個(gè)進(jìn)程的要求為止。而對(duì)每個(gè)進(jìn)程只有最后一頁經(jīng)常裝不滿一塊，平均產(chǎn)對(duì)每個(gè)進(jìn)程只有最后一頁經(jīng)常裝不滿一塊，平均產(chǎn)生半頁生半頁“頁內(nèi)碎片頁

56、內(nèi)碎片”。由此可知，分頁存儲(chǔ)管理。由此可知，分頁存儲(chǔ)管理解解決了決了“碎片碎片”問題，提高了存儲(chǔ)器的利用率問題，提高了存儲(chǔ)器的利用率。51將進(jìn)程頁分配到內(nèi)存幀中將進(jìn)程頁分配到內(nèi)存幀中52操作系統(tǒng)如何知道進(jìn)程中的某一頁具體被分配到操作系統(tǒng)如何知道進(jìn)程中的某一頁具體被分配到哪個(gè)物理幀中？哪個(gè)物理幀中？系統(tǒng)在內(nèi)存為每個(gè)進(jìn)程建立了一張頁面映射表，簡(jiǎn)系統(tǒng)在內(nèi)存為每個(gè)進(jìn)程建立了一張頁面映射表，簡(jiǎn)稱稱頁表頁表（page table） 每個(gè)頁在頁表中占一個(gè)表項(xiàng)，記錄該頁在內(nèi)存中對(duì)每個(gè)頁在頁表中占一個(gè)表項(xiàng)，記錄該頁在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)或幀號(hào)（頁號(hào)可以省略，通常默認(rèn)從應(yīng)的物理塊號(hào)或幀號(hào)（頁號(hào)可以省略，通常默認(rèn)從

57、0 0開始）。開始）。進(jìn)程在執(zhí)行時(shí)，通過查找頁表，就可以找到每頁所進(jìn)程在執(zhí)行時(shí)，通過查找頁表，就可以找到每頁所對(duì)應(yīng)的物理塊號(hào)或幀號(hào)。對(duì)應(yīng)的物理塊號(hào)或幀號(hào)。可見，頁表的作用是實(shí)現(xiàn)從頁號(hào)到物理塊號(hào)的地址可見，頁表的作用是實(shí)現(xiàn)從頁號(hào)到物理塊號(hào)的地址映射。映射。 53頁表頁表 0 1 2 3 0 1 2 3 4 5 6 7 用 戶 程 序 頁 表 內(nèi) 存頁 號(hào) 塊 號(hào) 0 2 1 4 2 5 3 754圖圖7.9 (f)狀態(tài)下各進(jìn)程的頁表示例狀態(tài)下各進(jìn)程的頁表示例每頁對(duì)應(yīng)一個(gè)幀位置空閑幀列表55分頁存儲(chǔ)管理系統(tǒng)的地址結(jié)構(gòu)分頁存儲(chǔ)管理系統(tǒng)的地址結(jié)構(gòu)分頁系統(tǒng)的地址結(jié)構(gòu)如下圖分頁系統(tǒng)的地址結(jié)構(gòu)如下圖所示所示

58、，它由兩部分，它由兩部分組成：前一部分為組成：前一部分為頁號(hào)頁號(hào)P P；后一部分為后一部分為頁內(nèi)位移頁內(nèi)位移量量W W，即頁內(nèi)地址，由頁的大小決定。即頁內(nèi)地址，由頁的大小決定。圖中的地址長(zhǎng)度為圖中的地址長(zhǎng)度為1616位，其中位，其中0 09 9位為頁內(nèi)地位為頁內(nèi)地址（每頁的大小為址（每頁的大小為1 1KBKB），），10101515位為頁號(hào)，所位為頁號(hào)，所以允許地址空間的大小最多為以允許地址空間的大小最多為6464個(gè)頁（個(gè)頁（2 26 6）。）。 頁號(hào)頁號(hào)P P 位移量位移量W W15 10 9 015 10 9 056地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 基本任務(wù)：利用硬件實(shí)現(xiàn)查頁表把用戶程序中的邏輯地

59、址變換成基本任務(wù)：利用硬件實(shí)現(xiàn)查頁表把用戶程序中的邏輯地址變換成內(nèi)存中的物理地址。內(nèi)存中的物理地址。為了實(shí)現(xiàn)地址變換功能，在系統(tǒng)中設(shè)置頁表寄存器，用來存放頁為了實(shí)現(xiàn)地址變換功能，在系統(tǒng)中設(shè)置頁表寄存器，用來存放頁表的始址和頁表的長(zhǎng)度。在進(jìn)程未執(zhí)行時(shí)，每個(gè)進(jìn)程對(duì)應(yīng)的頁表表的始址和頁表的長(zhǎng)度。在進(jìn)程未執(zhí)行時(shí)，每個(gè)進(jìn)程對(duì)應(yīng)的頁表的始址和長(zhǎng)度存放在進(jìn)程的的始址和長(zhǎng)度存放在進(jìn)程的PCBPCB中，當(dāng)該進(jìn)程被調(diào)度時(shí)，就將它中，當(dāng)該進(jìn)程被調(diào)度時(shí)，就將它們裝入頁表寄存器。們裝入頁表寄存器。在進(jìn)行地址變換時(shí)，系統(tǒng)將邏輯地址截成頁號(hào)和頁內(nèi)地址二部分，在進(jìn)行地址變換時(shí)，系統(tǒng)將邏輯地址截成頁號(hào)和頁內(nèi)地址二部分，將頁號(hào)與

60、頁表長(zhǎng)度進(jìn)行比較，如果頁號(hào)大于等于頁表寄存器中的將頁號(hào)與頁表長(zhǎng)度進(jìn)行比較，如果頁號(hào)大于等于頁表寄存器中的頁表長(zhǎng)度，則訪問越界，產(chǎn)生越界中斷。如未出現(xiàn)越界，則根據(jù)頁表長(zhǎng)度，則訪問越界，產(chǎn)生越界中斷。如未出現(xiàn)越界，則根據(jù)頁表寄存器中的頁表始址和頁號(hào)計(jì)算出該頁在頁表項(xiàng)中的位置，頁表寄存器中的頁表始址和頁號(hào)計(jì)算出該頁在頁表項(xiàng)中的位置，查頁表得到該頁的物理塊號(hào)，查頁表得到該頁的物理塊號(hào)，將物理塊號(hào)與邏輯地址中頁內(nèi)地址將物理塊號(hào)與邏輯地址中頁內(nèi)地址二者拼接成物理地址二者拼接成物理地址，這樣便完成了從邏輯地址到物理地址的變，這樣便完成了從邏輯地址到物理地址的變換。換。 57分頁系統(tǒng)的分頁系統(tǒng)的地址變換機(jī)構(gòu)示