第4章 內(nèi)存管理

1、1北華大學(xué)北華大學(xué).計(jì)算機(jī)科學(xué)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)技術(shù)學(xué)院操作系統(tǒng)原理操作系統(tǒng)原理 課程課程 管管 理理 第第 4 章章操作系統(tǒng)原理操作系統(tǒng)原理 課程 第2張今天雖然主存價(jià)格已相當(dāng)便宜，但主存容量仍然是計(jì)今天雖然主存價(jià)格已相當(dāng)便宜，但主存容量仍然是計(jì)算機(jī)四大硬件資源中最關(guān)鍵而又最緊張的算機(jī)四大硬件資源中最關(guān)鍵而又最緊張的“瓶頸瓶頸”資源。資源。因此對主存的管理和有效使用仍然是今天操作系統(tǒng)十分重因此對主存的管理和有效使用仍然是今天操作系統(tǒng)十分重要的內(nèi)容。要的內(nèi)容。許多操作系統(tǒng)之間最明顯的區(qū)別特征之一往往是所使許多操作系統(tǒng)之間最明顯的區(qū)別特征之一往往是所使用的存儲管理方法不同。如用的存儲管理方法不同

2、。如OS/360-MFTOS/360-MFT采用采用固定分區(qū)固定分區(qū)存儲存儲管理技術(shù)，管理技術(shù)，OS/360-MTVOS/360-MTV是采用是采用可變分區(qū)可變分區(qū)存儲管理技術(shù)，存儲管理技術(shù)，OS/2OS/2，WindowsNT, WindowsNT, 是采用是采用虛擬存儲虛擬存儲管理技術(shù)。管理技術(shù)。主存儲器管理技術(shù)可分為兩大類：主存儲器管理技術(shù)可分為兩大類： 實(shí)存儲器實(shí)存儲器管理和管理和虛擬存儲器虛擬存儲器管理。管理。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第3張本章目標(biāo)本章目標(biāo)熟悉三級存儲器結(jié)構(gòu)：熟悉三級存儲器結(jié)構(gòu)：CPU寄存器、內(nèi)存、外存。寄存器、內(nèi)存、外存。記住用戶程序的主要處理階段：編輯、編

3、譯、鏈接、裝入、記住用戶程序的主要處理階段：編輯、編譯、鏈接、裝入、運(yùn)行。運(yùn)行。理解存儲器管理的功能（內(nèi)存分配與回收、地址映射、內(nèi)存理解存儲器管理的功能（內(nèi)存分配與回收、地址映射、內(nèi)存保護(hù)與共享、虛擬存儲）和虛擬存儲器的基本特征（離散分保護(hù)與共享、虛擬存儲）和虛擬存儲器的基本特征（離散分配、多次性、對換性、虛擬性）。配、多次性、對換性、虛擬性）。牢固掌握概念：邏輯地址、物理地址、重定位、碎片、虛擬牢固掌握概念：邏輯地址、物理地址、重定位、碎片、虛擬存儲器、抖動(dòng)、程序局部性原理等。存儲器、抖動(dòng)、程序局部性原理等。掌握分區(qū)、分頁、分段存儲管理技術(shù)的實(shí)現(xiàn)思想，如何實(shí)現(xiàn)掌握分區(qū)、分頁、分段存儲管理技術(shù)

4、的實(shí)現(xiàn)思想，如何實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換。從邏輯地址到物理地址的轉(zhuǎn)換。掌握虛擬頁式存儲中的頁面置換算法：先進(jìn)先出法掌握虛擬頁式存儲中的頁面置換算法：先進(jìn)先出法（FIFO）、最佳置換法（）、最佳置換法（OPT）、最近最少使用法（）、最近最少使用法（LRU） 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第4張存存儲儲器器管管理理 本章結(jié)構(gòu)本章結(jié)構(gòu)基礎(chǔ)知識、程序的裝入和鏈接基礎(chǔ)知識、程序的裝入和鏈接連續(xù)分配方式連續(xù)分配方式分頁存儲管理方式分頁存儲管理方式分段存儲管理方式分段存儲管理方式段頁式存儲管理方式段頁式存儲管理方式固定分區(qū)固定分區(qū)動(dòng)態(tài)分區(qū)動(dòng)態(tài)分區(qū)基本頁式基本頁式虛擬頁式虛擬頁式基本段式基本段式虛擬段

5、式虛擬段式操作系統(tǒng)原理操作系統(tǒng)原理 課程 第5張4.1 存儲器管理的基礎(chǔ)知識存儲器管理的基礎(chǔ)知識 一一. .存儲器的層次結(jié)構(gòu)：存儲器的層次結(jié)構(gòu)：（ 過去常見為三級結(jié)構(gòu)劃分，教材中為較細(xì)的劃分過去常見為三級結(jié)構(gòu)劃分，教材中為較細(xì)的劃分） CPU寄存器寄存器 用戶程序在運(yùn)行時(shí)應(yīng)存放在用戶程序在運(yùn)行時(shí)應(yīng)存放在中，以便處理機(jī)訪問。但是由中，以便處理機(jī)訪問。但是由于主存容量有限。所以把那些不馬上使用的程序、數(shù)據(jù)放在外部于主存容量有限。所以把那些不馬上使用的程序、數(shù)據(jù)放在外部存儲器中，當(dāng)用到時(shí)再把它們讀入主存。存儲器中，當(dāng)用到時(shí)再把它們讀入主存。如如IBM的緩存最大傳輸速度為的緩存最大傳輸速度為每雙字每雙

6、字120225毫微秒毫微秒，主存的傳輸速度，主存的傳輸速度每字每字1微秒微秒。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第6張1.CPU寄存器寄存器： 訪問速度最快，可與訪問速度最快，可與CPU協(xié)調(diào)工作、少量的、昂貴，用于加快協(xié)調(diào)工作、少量的、昂貴，用于加快存儲器的訪問速度，如存放操作數(shù)或作為地址寄存器。存儲器的訪問速度，如存放操作數(shù)或作為地址寄存器。 2.主主（內(nèi)內(nèi)）存存RAM： 處理機(jī)能直接訪問的存儲器處理機(jī)能直接訪問的存儲器。用來存放系統(tǒng)和用戶的程序和數(shù)。用來存放系統(tǒng)和用戶的程序和數(shù)據(jù)，其特點(diǎn)是存取速度快，存儲方式是以新?lián)Q舊，斷電信息丟據(jù)，其特點(diǎn)是存取速度快，存儲方式是以新?lián)Q舊，斷電信息丟失。失。

7、 3.輔存輔存（磁盤磁盤）： 處理機(jī)不能直接訪問的存儲器。用來存放用戶的各種信息，存處理機(jī)不能直接訪問的存儲器。用來存放用戶的各種信息，存取速度相對內(nèi)存而言要慢得多，但它可用來長期保存用戶信息。取速度相對內(nèi)存而言要慢得多，但它可用來長期保存用戶信息。4.1 存儲器管理的基礎(chǔ)知識存儲器管理的基礎(chǔ)知識 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第7張. .教材中的教材中的多級多級層次結(jié)構(gòu)：層次結(jié)構(gòu)：寄存器寄存器高速緩存高速緩存主主 存存磁盤緩存磁盤緩存磁磁 盤盤 可移動(dòng)存儲介質(zhì)可移動(dòng)存儲介質(zhì)4.1 存儲器管理的基礎(chǔ)知識存儲器管理的基礎(chǔ)知識 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第8張1： 物理地址是主存的真實(shí)地址

8、物理地址是主存的真實(shí)地址 ，是存儲控制部件能夠識別的主存，是存儲控制部件能夠識別的主存單元編號。把內(nèi)存分成若干個(gè)大小相等的存儲單元，每個(gè)單元給單元編號。把內(nèi)存分成若干個(gè)大小相等的存儲單元，每個(gè)單元給一個(gè)編號，這個(gè)編號稱為一個(gè)編號，這個(gè)編號稱為內(nèi)存地址內(nèi)存地址（物理地址物理地址、絕對地址絕對地址、實(shí)地實(shí)地址址），存儲單元占），存儲單元占8位，稱作字節(jié)（位，稱作字節(jié)（byte）。）。2.： 物理地址的集合稱為物理地址空間（主存地址空間），它是一物理地址的集合稱為物理地址空間（主存地址空間），它是一個(gè)一維的線性空間。個(gè)一維的線性空間。 內(nèi)存內(nèi)存014.1 存儲器管理的基礎(chǔ)知識存儲器管理的基礎(chǔ)知識 操

9、作系統(tǒng)原理操作系統(tǒng)原理 課程 第9張1.： 用戶編程序時(shí)所用的地址（或稱用戶編程序時(shí)所用的地址（或稱邏輯地址邏輯地址 、相對地址相對地址、虛地址虛地址 ），），是指相對于某個(gè)基準(zhǔn)量編址時(shí)所使用的地址，常用于程序編寫和是指相對于某個(gè)基準(zhǔn)量編址時(shí)所使用的地址，常用于程序編寫和編譯過程中?；締挝豢膳c內(nèi)存的基本單位相同，也可以不相同。編譯過程中?；締挝豢膳c內(nèi)存的基本單位相同，也可以不相同。（用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地址的（用戶的程序經(jīng)過匯編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地址的形式，其首地址為形式，其首地址為0 0，其余指令中的地址都相對于首地址而編址

10、。），其余指令中的地址都相對于首地址而編址。）2.（邏輯地址空間、虛地址空間）（邏輯地址空間、虛地址空間）： 用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從0開開始的，可以是一維線性空間，也可以是多維空間。始的，可以是一維線性空間，也可以是多維空間。 4.1 存儲器管理的基礎(chǔ)知識存儲器管理的基礎(chǔ)知識 虛地址空間虛地址空間010124.2 程序的裝入和鏈接程序的裝入和鏈接 程序和數(shù)據(jù)程序和數(shù)據(jù)裝入內(nèi)存裝入內(nèi)存創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程運(yùn)行程序運(yùn)行程序源程序源程序轉(zhuǎn)換為可執(zhí)行文件轉(zhuǎn)換為可執(zhí)行文件編譯編譯 將源代碼編譯成若干將源代碼編譯成若干obj模塊

11、模塊;鏈接鏈接 由鏈接程序?qū)⒂涉溄映绦驅(qū)bj模塊鏈接在一起模塊鏈接在一起,形成裝入模塊形成裝入模塊;裝入裝入 裝入程序?qū)⒀b入模塊裝入內(nèi)存裝入程序?qū)⒀b入模塊裝入內(nèi)存如何將一個(gè)用戶源程序變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序？如何將一個(gè)用戶源程序變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序？源程序源程序目標(biāo)模塊目標(biāo)模塊裝入程序裝入程序裝入模塊裝入模塊編譯編譯鏈接鏈接裝入裝入4.2 程序的裝入和鏈接程序的裝入和鏈接 庫鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存操作系統(tǒng)原理操作系統(tǒng)原理 課程 第12張4.2.1 程序的裝入程序的裝入1. 絕對裝入方式絕對裝入方式(Absolute Loading M

12、ode) 程序中所使用的程序中所使用的絕對地址絕對地址，既可在編譯或匯編時(shí)給出，既可在編譯或匯編時(shí)給出， 也可由程序員直接賦予。也可由程序員直接賦予。 但在由程序員直接給出絕對地址時(shí)，但在由程序員直接給出絕對地址時(shí)， 不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時(shí)，再將這些符號地程序中采用符號地址，然后在編譯或匯編時(shí)，再將這些符號地址轉(zhuǎn)換為絕對地址。址轉(zhuǎn)換為絕對地址。 由于程序中的邏輯地址

13、與實(shí)際內(nèi)存地址完全相同，故不須對由于程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同，故不須對程序和數(shù)據(jù)地址進(jìn)行修改。但這種情況很少，一般只適于程序和數(shù)據(jù)地址進(jìn)行修改。但這種情況很少，一般只適于單道單道環(huán)境環(huán)境。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第13張2. 可重定位裝入方式可重定位裝入方式4.2.1 程序的裝入程序的裝入 由裝入程序由裝入程序根據(jù)內(nèi)存當(dāng)時(shí)的實(shí)際使用情況根據(jù)內(nèi)存當(dāng)時(shí)的實(shí)際使用情況，將裝入模塊裝，將裝入模塊裝入到入到內(nèi)存的適當(dāng)?shù)胤絻?nèi)存的適當(dāng)?shù)胤?。由于編譯程序不能預(yù)知所編譯的目標(biāo)。由于編譯程序不能預(yù)知所編譯的目標(biāo)模塊在內(nèi)存的什么位置，因此，會使裝入模塊中的所有模塊在內(nèi)存的什么位置，因此，會使裝

14、入模塊中的所有邏輯邏輯地址與實(shí)際地址不同。地址與實(shí)際地址不同。 在裝入時(shí)，將根據(jù)實(shí)際裝入的起始位置，相應(yīng)調(diào)整所有的相在裝入時(shí)，將根據(jù)實(shí)際裝入的起始位置，相應(yīng)調(diào)整所有的相對地址。在裝入時(shí)對目標(biāo)程序中的指令和數(shù)據(jù)地址的修改過程對地址。在裝入時(shí)對目標(biāo)程序中的指令和數(shù)據(jù)地址的修改過程稱為稱為重定位重定位。又因?yàn)榈刂方粨Q只是在裝入時(shí)一次完成，以后不。又因?yàn)榈刂方粨Q只是在裝入時(shí)一次完成，以后不在改變，故稱為在改變，故稱為靜態(tài)重定位靜態(tài)重定位。 圖圖 4-2重定位方式重定位方式作業(yè)裝入內(nèi)存時(shí)的情況作業(yè)裝入內(nèi)存時(shí)的情況 LOAD 1,2500365LOAD 1,250036510000110001250015

15、0005000250010000作業(yè)地址空間內(nèi)存空間操作系統(tǒng)原理操作系統(tǒng)原理 課程 第15張3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式 (Denamle Run-time Loading) 動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)程序真正要執(zhí)行時(shí)才進(jìn)行。因此，才進(jìn)行。因此， 裝入內(nèi)裝入內(nèi)存后的所有地址都仍是相對地址。存后的所有地址都仍是相對地址。 4.2.1 程序的裝入程序的裝入為使地址轉(zhuǎn)

16、換不影響指令的運(yùn)行速度，需要為使地址轉(zhuǎn)換不影響指令的運(yùn)行速度，需要重定位寄存器重定位寄存器支持。支持。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第16張4.2.2 程序的鏈接程序的鏈接 1. 靜態(tài)鏈接方式靜態(tài)鏈接方式(Static Linking) 模塊 ACALL B；Return；0L1模塊 BCALL C；Return；0M1模塊 CReturn；0N10模塊 AJSR“L”Return；L1模塊 BJSR“LM”Return；LLM1LMLMN1模塊 CReturn；(a) 目標(biāo)模塊(b) 裝入模塊操作系統(tǒng)原理操作系統(tǒng)原理 課程 第17張 在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解在將這幾個(gè)目

17、標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)問題：決以下兩個(gè)問題： (1) 對相對地址進(jìn)行修改對相對地址進(jìn)行修改。 (2) 變換外部調(diào)用符號變換外部調(diào)用符號。 4.2.2 程序的鏈接程序的鏈接 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第18張2. 裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接(Loadtime Dynamic Linking) 裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)：裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)： （1） 便于修改和更新便于修改和更新。 （2）便于實(shí)現(xiàn)對目標(biāo)模塊的共享便于實(shí)現(xiàn)對目標(biāo)模塊的共享。 4.2.2 程序的鏈接程序的鏈接 在裝入目標(biāo)模塊時(shí)，若在裝入目標(biāo)模塊時(shí)，若發(fā)現(xiàn)一個(gè)外部模塊調(diào)用事件發(fā)現(xiàn)一個(gè)外部模塊調(diào)用事

18、件，由裝入程序找出相應(yīng)的模塊。由裝入程序找出相應(yīng)的模塊。 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第19張 近幾年流行起來的運(yùn)行時(shí)動(dòng)態(tài)鏈接方式，是對上述在近幾年流行起來的運(yùn)行時(shí)動(dòng)態(tài)鏈接方式，是對上述在裝入時(shí)鏈接方式的一種改進(jìn)。這種鏈接方式是將裝入時(shí)鏈接方式的一種改進(jìn)。這種鏈接方式是將對某些模對某些模塊的鏈接推遲到執(zhí)行時(shí)才執(zhí)行塊的鏈接推遲到執(zhí)行時(shí)才執(zhí)行，亦即，在執(zhí)行過程中，當(dāng)，亦即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該去找到該模塊并將之裝入內(nèi)存，模塊并將之裝入內(nèi)存， 把它鏈接到調(diào)用者模塊上。凡在執(zhí)把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程

19、中未被用到的目標(biāo)模塊，都不會被調(diào)入內(nèi)存和被鏈行過程中未被用到的目標(biāo)模塊，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且接到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間?？晒?jié)省大量的內(nèi)存空間。 4.2.2 程序的鏈接程序的鏈接 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第20張1.地址映射地址映射將程序地址空間中使用的將程序地址空間中使用的邏輯地址邏輯地址變換成變換成主存中的地址主存中的地址的過程的過程稱為稱為地址映射地址映射。有時(shí)也稱為。有時(shí)也稱為地址重定位地址重定位 。補(bǔ)補(bǔ)：存儲管理的功能存儲管理的功能 2.主存分配與回收主存分配與回收按照一定的算法把某

20、一空閑的主存區(qū)分配給作業(yè)或進(jìn)程。按照一定的算法把某一空閑的主存區(qū)分配給作業(yè)或進(jìn)程。在多道程序設(shè)計(jì)的環(huán)境中，內(nèi)存分配的功能包括：在多道程序設(shè)計(jì)的環(huán)境中，內(nèi)存分配的功能包括：制定分配策略制定分配策略、構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)構(gòu)造分配用的數(shù)據(jù)結(jié)構(gòu)、響應(yīng)系統(tǒng)的內(nèi)存分配響應(yīng)系統(tǒng)的內(nèi)存分配的請求的請求和和回收系統(tǒng)釋放的內(nèi)存區(qū)回收系統(tǒng)釋放的內(nèi)存區(qū)。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第21張內(nèi)存管理策略內(nèi)存管理策略有三種有三種:1）放置策略放置策略 決定內(nèi)存中放置信息的區(qū)域（或位置），即如何在若干個(gè)決定內(nèi)存中放置信息的區(qū)域（或位置），即如何在若干個(gè)空閑區(qū)中選擇一個(gè)或幾個(gè)空閑區(qū)的原則；空閑區(qū)中選擇一個(gè)或幾個(gè)空閑區(qū)的原

21、則；2）調(diào)入策略調(diào)入策略 決定信息裝入內(nèi)存的時(shí)機(jī)，有兩種：在用戶請求時(shí)調(diào)入，稱決定信息裝入內(nèi)存的時(shí)機(jī)，有兩種：在用戶請求時(shí)調(diào)入，稱為為請調(diào)請調(diào)；根據(jù)某種算法，確定系統(tǒng)將要使用的信息，并在執(zhí)行；根據(jù)某種算法，確定系統(tǒng)將要使用的信息，并在執(zhí)行前預(yù)先調(diào)入內(nèi)存，稱為前預(yù)先調(diào)入內(nèi)存，稱為預(yù)調(diào)預(yù)調(diào) ；3）淘汰策略淘汰策略 當(dāng)內(nèi)存不足時(shí)，決定將某些信息調(diào)出內(nèi)存的策略當(dāng)內(nèi)存不足時(shí)，決定將某些信息調(diào)出內(nèi)存的策略 。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第22張3.存儲保護(hù)與共享存儲保護(hù)與共享保證用戶程序保證用戶程序(或進(jìn)程映象或進(jìn)程映象)在各自存儲區(qū)域內(nèi)操作，互不干擾。在各自存儲區(qū)域內(nèi)操作，互不干擾。補(bǔ)：補(bǔ)：存儲管理

22、的功能存儲管理的功能 常用的存儲保護(hù)有兩種常用的存儲保護(hù)有兩種:上下界保護(hù)上下界保護(hù)下界寄存器下界寄存器: 存放程序裝入內(nèi)存后的開始地址（首址）存放程序裝入內(nèi)存后的開始地址（首址）上界寄存器上界寄存器: 存放程序裝入內(nèi)存后的末地址存放程序裝入內(nèi)存后的末地址判別式：判別式： 下界寄存器下界寄存器 物理地址物理地址 上界寄存器上界寄存器基址、限長寄存器保護(hù)基址、限長寄存器保護(hù)基址寄存器基址寄存器: 存放程序裝入內(nèi)存后的開始地址（首址）存放程序裝入內(nèi)存后的開始地址（首址）限長寄存器限長寄存器: 存放限制訪問的最大相對長度存放限制訪問的最大相對長度判別式：判別式：基址寄存器基址寄存器 物理地址物理地址

23、 基址寄存器基址寄存器+限長寄存器限長寄存器操作系統(tǒng)原理操作系統(tǒng)原理 課程 第23張1）常規(guī)存儲器管理方式的特征常規(guī)存儲器管理方式的特征 一次性。一次性。 (2) 駐留性。駐留性。 4.提供虛擬存儲技術(shù)提供虛擬存儲技術(shù)補(bǔ)：補(bǔ)：存儲管理的功能存儲管理的功能 早在早在1968年，年， Denning.P就曾指出：就曾指出： (1) 程序執(zhí)行時(shí)，程序執(zhí)行時(shí)， 除了少部分的轉(zhuǎn)移和過程調(diào)用指令外，除了少部分的轉(zhuǎn)移和過程調(diào)用指令外， 在大多數(shù)情況在大多數(shù)情況下仍是順序執(zhí)行的。下仍是順序執(zhí)行的。 (2) 過程調(diào)用將會使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，過程調(diào)用將會使程序的執(zhí)行軌跡由一部分區(qū)域轉(zhuǎn)至另

24、一部分區(qū)域， 但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5。 (3) 程序中存在許多循環(huán)結(jié)構(gòu)，程序中存在許多循環(huán)結(jié)構(gòu)， 這些雖然只由少數(shù)指令構(gòu)成，這些雖然只由少數(shù)指令構(gòu)成， 但是它們但是它們將多次執(zhí)行。將多次執(zhí)行。 (4) 程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理，程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理， 如對數(shù)組進(jìn)行操作，如對數(shù)組進(jìn)行操作， 它們往它們往往都局限于很小的范圍內(nèi)。往都局限于很小的范圍內(nèi)。 2）局部性原理局部性原理 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第24張 (1) 時(shí)間局限性時(shí)間局限性。如果程序中的某條指令一旦執(zhí)行，。如果程序中的某條指

25、令一旦執(zhí)行， 則不久以則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過，后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過， 則不久以后該則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因，是由于在數(shù)據(jù)可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。程序中存在著大量的循環(huán)操作。 (2) 空間局限性空間局限性。一旦程序訪問了某個(gè)存儲單元，在不久之后，。一旦程序訪問了某個(gè)存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序在一段時(shí)間內(nèi)所訪問的其附近的存儲單元也將被訪問，即程序在一段時(shí)間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順地址，可能集中在一定

26、的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。序執(zhí)行。 局限性又表現(xiàn)在下述兩個(gè)方面：局限性又表現(xiàn)在下述兩個(gè)方面：操作系統(tǒng)原理操作系統(tǒng)原理 課程 第25張 使用戶程序的大小和結(jié)構(gòu)使用戶程序的大小和結(jié)構(gòu)不受主存容量和結(jié)構(gòu)的限制不受主存容量和結(jié)構(gòu)的限制，即使在，即使在用戶程序比實(shí)際主存容量還要大的情況下，程序也能正確運(yùn)行。用戶程序比實(shí)際主存容量還要大的情況下，程序也能正確運(yùn)行。問題的提出問題的提出物理存儲器物理存儲器的結(jié)構(gòu)是個(gè)的結(jié)構(gòu)是個(gè)一維一維的線性空間，容量是的線性空間，容量是有限有限的。的。用戶程序用戶程序結(jié)構(gòu)：結(jié)構(gòu)：一維空間一維空間： 一個(gè)用戶程序就是一個(gè)程序，并且程序和數(shù)據(jù)是不分離的；一個(gè)用戶程

27、序就是一個(gè)程序，并且程序和數(shù)據(jù)是不分離的；二維空間二維空間： 程序由主程序和若干個(gè)子程序（或函數(shù)）組成，并且程序程序由主程序和若干個(gè)子程序（或函數(shù)）組成，并且程序 與數(shù)據(jù)是分離的；與數(shù)據(jù)是分離的； n n維空間維空間： 即一個(gè)大型程序，由一個(gè)主模塊和多個(gè)子模塊組成，其中，即一個(gè)大型程序，由一個(gè)主模塊和多個(gè)子模塊組成，其中，各各 子模塊又由主程序和子程序（或函數(shù)）組成。子模塊又由主程序和子程序（或函數(shù)）組成。 用戶程序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容量大，有時(shí)候要大用戶程序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容量大，有時(shí)候要大得多。得多。 虛擬存儲技術(shù)虛擬存儲技術(shù)操作系統(tǒng)原理操作系統(tǒng)原

28、理 課程 第26張 虛擬存儲概念虛擬存儲概念 為用戶提供一種不受物理存儲器結(jié)構(gòu)和容量限制的存儲器的技術(shù)為用戶提供一種不受物理存儲器結(jié)構(gòu)和容量限制的存儲器的技術(shù)稱為虛擬存儲技術(shù)。稱為虛擬存儲技術(shù)。 所謂所謂虛擬存儲器虛擬存儲器，是指具有，是指具有請求調(diào)入請求調(diào)入功能和功能和置換置換功能，能從邏輯功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)，其邏輯容量由內(nèi)、外存上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)，其邏輯容量由內(nèi)、外存容量之和來決定，其運(yùn)行速度接近內(nèi)存，成本接近外存。容量之和來決定，其運(yùn)行速度接近內(nèi)存，成本接近外存。 虛擬存儲器的特征：虛擬存儲器的特征： 多次性多次性對換性對換性虛擬性虛擬性

29、 0. 離散分配離散分配 虛擬存儲技術(shù)虛擬存儲技術(shù)操作系統(tǒng)原理操作系統(tǒng)原理 課程 第27張回顧：回顧：4.3 連續(xù)分配方式連續(xù)分配方式1.存儲管理的基本功能：存儲管理的基本功能：內(nèi)存分配與回收內(nèi)存分配與回收地址映射地址映射內(nèi)存保護(hù)與共享內(nèi)存保護(hù)與共享虛擬存儲虛擬存儲（內(nèi)存擴(kuò)充內(nèi)存擴(kuò)充）2.程序的虛擬地址空間（程序的虛擬地址空間（邏輯地址邏輯地址） 內(nèi)存的物理地址空間（內(nèi)存的物理地址空間（物理地址物理地址）操作系統(tǒng)原理操作系統(tǒng)原理 課程 第28張4.3 連續(xù)分配方式連續(xù)分配方式4.3.1 單一連續(xù)分配單一連續(xù)分配 分區(qū)存儲管理分區(qū)存儲管理 OS系統(tǒng)區(qū)系統(tǒng)區(qū)占用區(qū)占用區(qū)空閑區(qū)空閑區(qū) 用用 戶戶 區(qū)

30、區(qū) 低址低址高址高址用于用于單用戶單用戶、單任務(wù)單任務(wù)的的OSOS中中 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第29張4.3.2 固定分區(qū)分配固定分區(qū)分配 2. 劃分分區(qū)的方法劃分分區(qū)的方法： 分區(qū)大小分區(qū)大小相等相等 4.3 連續(xù)分配方式連續(xù)分配方式1.原理原理：OS區(qū)用用戶戶區(qū)區(qū)OS區(qū)用用戶戶區(qū)區(qū)(2) 分區(qū)大小分區(qū)大小不等不等分區(qū)分區(qū)1分區(qū)分區(qū)2分區(qū)分區(qū)3分區(qū)分區(qū)4分區(qū)分區(qū)2分區(qū)分區(qū)1分區(qū)分區(qū)3分區(qū)分區(qū)4操作系統(tǒng)原理操作系統(tǒng)原理 課程 第30張3.3.涉及的數(shù)據(jù)結(jié)構(gòu)涉及的數(shù)據(jù)結(jié)構(gòu)分區(qū)說明表分區(qū)說明表（內(nèi)存分配表）（內(nèi)存分配表） 4.3.2 固定分區(qū)分配固定分區(qū)分配 4.3 連續(xù)分配方式連續(xù)分配

31、方式操作系統(tǒng)原理操作系統(tǒng)原理 課程 第31張3.3.內(nèi)存分配內(nèi)存分配4.3.2 固定分區(qū)分配固定分區(qū)分配 4.3 連續(xù)分配方式連續(xù)分配方式 由由內(nèi)存分配程序內(nèi)存分配程序?qū)Ψ謪^(qū)說明表分區(qū)說明表進(jìn)行檢索，如果有一個(gè)空閑區(qū)符進(jìn)行檢索，如果有一個(gè)空閑區(qū)符合用戶要求的大小合用戶要求的大小, 則分配給進(jìn)程。即則分配給進(jìn)程。即將將寫入寫入PCB，并，并置該分區(qū)的狀態(tài)為已分置該分區(qū)的狀態(tài)為已分“1”。4.4.內(nèi)存回收內(nèi)存回收 將對應(yīng)分區(qū)的狀態(tài)設(shè)為空將對應(yīng)分區(qū)的狀態(tài)設(shè)為空閑，即閑，即“0”。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第32張5.5.地址轉(zhuǎn)換地址轉(zhuǎn)換4.3.2 固定分區(qū)分配固定分區(qū)分配 4.3 連續(xù)分配方

32、式連續(xù)分配方式 系統(tǒng)采用系統(tǒng)采用“技術(shù)，將作業(yè)裝入所分配的分區(qū)中，技術(shù)，將作業(yè)裝入所分配的分區(qū)中，且在執(zhí)行過程中不會被改變存放區(qū)域，由裝入程序按如下計(jì)算得且在執(zhí)行過程中不會被改變存放區(qū)域，由裝入程序按如下計(jì)算得出物理地址。出物理地址。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第33張6.6.存儲保護(hù)存儲保護(hù)4.3.2 固定分區(qū)分配固定分區(qū)分配 4.3 連續(xù)分配方式連續(xù)分配方式常采用常采用“基址、限長寄存器保護(hù)法基址、限長寄存器保護(hù)法”操作系統(tǒng)原理操作系統(tǒng)原理 課程 第34張4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 4.3 連續(xù)分配方式連續(xù)分配方式1）內(nèi)存空間劃分內(nèi)存空間劃分： 將內(nèi)存空間除將內(nèi)存空間除OS區(qū)

33、外，區(qū)外，。當(dāng)一個(gè)作。當(dāng)一個(gè)作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。（若有足夠的空間，則按需要配。（若有足夠的空間，則按需要一部分分區(qū)給該進(jìn)程；否一部分分區(qū)給該進(jìn)程；否則令其等待主存空間）則令其等待主存空間）分區(qū)，分區(qū)，。1.原理原理：2）虛擬空間劃分：虛擬空間劃分：空間空間 3）分配原則：分配原則： 尋找一個(gè)滿足大小的空閑區(qū)，按程序大小分割后，程序?qū)ふ乙粋€(gè)滿足大小的空閑區(qū)，按程序大小分割后，程序，。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第35張4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 2. 分配中的數(shù)據(jù)結(jié)構(gòu)分配中的數(shù)據(jù)結(jié)構(gòu)

34、(1) 空閑分區(qū)表空閑分區(qū)表前向指針N20N個(gè)字節(jié)可用后向指針N20區(qū)號區(qū)號長度長度始址始址(2) 空閑分區(qū)鏈空閑分區(qū)鏈 (3) 資源請求表資源請求表 進(jìn)程號進(jìn)程號請求內(nèi)存長度請求內(nèi)存長度P113kP220k分區(qū)號分區(qū)號 分區(qū)大小分區(qū)大小 后繼指針后繼指針分區(qū)號分區(qū)號 分區(qū)大小分區(qū)大小 后繼指針后繼指針操作系統(tǒng)原理操作系統(tǒng)原理 課程 第36張3. 內(nèi)存分配適應(yīng)（配）算法內(nèi)存分配適應(yīng)（配）算法4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 適適應(yīng)應(yīng)法法適適應(yīng)應(yīng)法法適適應(yīng)應(yīng)法法適適應(yīng)應(yīng)法法適適應(yīng)應(yīng)法法操作系統(tǒng)原理操作系統(tǒng)原理 課程 第37張3. 內(nèi)存分配適應(yīng)（配）算法內(nèi)存分配適應(yīng)（配）算法(1) 首次適應(yīng)算

35、法首次適應(yīng)算法FF最先適配法最先適配法 4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 (2) 最佳適應(yīng)算法最佳適應(yīng)算法BF 當(dāng)接到內(nèi)存申請時(shí)，查空閑塊表，找到當(dāng)接到內(nèi)存申請時(shí)，查空閑塊表，找到起始地址最小起始地址最小的不小于請求的的不小于請求的空塊，將其分割并分配。該算法要求空閑塊空塊，將其分割并分配。該算法要求空閑塊按起始地址按起始地址遞增遞增排序排序。 評價(jià)評價(jià)：簡單，傾向于優(yōu)先利用內(nèi)存簡單，傾向于優(yōu)先利用內(nèi)存低址低址部分的空閑區(qū)，后期查找低速。部分的空閑區(qū)，后期查找低速。 當(dāng)接到內(nèi)存申請時(shí)，在空閑塊表中找到一個(gè)不小于請求的當(dāng)接到內(nèi)存申請時(shí)，在空閑塊表中找到一個(gè)不小于請求的最小空閑塊最小空閑塊進(jìn)進(jìn)

36、行行 分配。該算法要求空閑塊分配。該算法要求空閑塊按長度遞增排序按長度遞增排序。評價(jià)評價(jià)：用最小空間滿足要求用最小空間滿足要求 ，避免，避免“大材小用大材小用”，但會存在切割后無法，但會存在切割后無法再利用的再利用的“碎片碎片”。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第38張3. 內(nèi)存分配適應(yīng)（配）算法內(nèi)存分配適應(yīng)（配）算法(3) 最差適應(yīng)算法最差適應(yīng)算法WF4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 (4) 循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法NF 當(dāng)接到內(nèi)存申請時(shí)，在空閑塊表中找到一個(gè)不小于請求的當(dāng)接到內(nèi)存申請時(shí)，在空閑塊表中找到一個(gè)不小于請求的最大空閑塊最大空閑塊進(jìn)進(jìn)行分配。該算法要求空閑塊行分配。該算

37、法要求空閑塊按長度按長度遞減遞減排序排序。評價(jià)評價(jià)：當(dāng)分割后空閑塊仍為較大空塊，可再次利用；但同時(shí)會造成無大當(dāng)分割后空閑塊仍為較大空塊，可再次利用；但同時(shí)會造成無大 的空閑區(qū)情況。的空閑區(qū)情況。 首次適應(yīng)法的改進(jìn)，區(qū)別在于搜索時(shí)不是每次都從鏈?zhǔn)组_始，而是從上首次適應(yīng)法的改進(jìn)，區(qū)別在于搜索時(shí)不是每次都從鏈?zhǔn)组_始，而是從上次找到的下一個(gè)空閑區(qū)開始查找。需設(shè)置一個(gè)尋查指針，用以指示下一次次找到的下一個(gè)空閑區(qū)開始查找。需設(shè)置一個(gè)尋查指針，用以指示下一次查詢的分區(qū)。查詢的分區(qū)。(5) 快速適應(yīng)算法快速適應(yīng)算法QF 將空閑分區(qū)按容量大小分類，相同容量空閑分區(qū)單獨(dú)成一個(gè)鏈表，并設(shè)將空閑分區(qū)按容量大小分類，相

38、同容量空閑分區(qū)單獨(dú)成一個(gè)鏈表，并設(shè)立管理索引表，索引表每一項(xiàng)對應(yīng)一類鏈表，并記錄每類空閑鏈的指針。立管理索引表，索引表每一項(xiàng)對應(yīng)一類鏈表，并記錄每類空閑鏈的指針。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第39張3.內(nèi)存分配分配過程內(nèi)存分配分配過程 從頭開始查表檢索完否？m.size u.size?m.size u.sizesize?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個(gè)表項(xiàng)將該分區(qū)從鏈中移出YNNYYN操作系統(tǒng)原理操作系統(tǒng)原理 課程 第40張F(tuán)1回收區(qū)4.內(nèi)存的回收內(nèi)存的回收4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 視情況進(jìn)行釋放區(qū)與其前、后空閑空間

39、的視情況進(jìn)行釋放區(qū)與其前、后空閑空間的合并合并 a) 回收區(qū)回收區(qū)F的前一個(gè)區(qū)的前一個(gè)區(qū)F1也為空閑區(qū)。也為空閑區(qū)。F1回收區(qū)FF1b) 回收區(qū)回收區(qū)F的后一個(gè)區(qū)的后一個(gè)區(qū)F2也為空閑區(qū)。也為空閑區(qū)。F2回收區(qū)FF2回收區(qū)FF2“二合一二合一”不必新增空閑區(qū)表項(xiàng)，只修改不必新增空閑區(qū)表項(xiàng)，只修改F1即可。即可。 F1的大小為的大小為F1和和F之和之和 其余分量不變其余分量不變“二合一二合一”不必新增空閑區(qū)表項(xiàng)，只修改不必新增空閑區(qū)表項(xiàng)，只修改F2即可。即可。將將F的首地址作為新空閑區(qū)的首地址的首地址作為新空閑區(qū)的首地址新區(qū)的大小為新區(qū)的大小為F2和和F之和之和 其余分量不變其余分量不變操作系統(tǒng)

40、原理操作系統(tǒng)原理 課程 第41張4.內(nèi)存的回收內(nèi)存的回收4.3.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配 c) 回收區(qū)回收區(qū)F的前后兩個(gè)區(qū)的前后兩個(gè)區(qū)F1、F2都為空閑區(qū)。都為空閑區(qū)。b) 回收區(qū)回收區(qū)F的前后兩個(gè)區(qū)都不是空閑區(qū)。的前后兩個(gè)區(qū)都不是空閑區(qū)?；厥諈^(qū)FF1回收區(qū)FF2F1回收區(qū)FF2F1回收區(qū)FF“三合一三合一”使用使用F1的表項(xiàng)，刪除的表項(xiàng)，刪除F2的表項(xiàng)。的表項(xiàng)。F1的大小為的大小為F1、F和和F2之和之和F1后繼指針改為后繼指針改為F2的后繼指針的后繼指針新增空閑區(qū)表項(xiàng)，新增空閑區(qū)表項(xiàng)，填寫空閑區(qū)首地址和大小，填寫空閑區(qū)首地址和大小，并插入到空閑鏈的適當(dāng)位置并插入到空閑鏈的適當(dāng)位置1.1

41、.空閑區(qū)個(gè)數(shù)變化？空閑區(qū)個(gè)數(shù)變化？2.2.碎片問題？碎片問題？操作系統(tǒng)原理操作系統(tǒng)原理 課程 第42張 通過在內(nèi)存移動(dòng)程序，將所有小的空閑區(qū)域合并為大的空通過在內(nèi)存移動(dòng)程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域。（緊縮技術(shù)，緊致技術(shù)，浮動(dòng)技術(shù)，搬家技術(shù)）閑區(qū)域。（緊縮技術(shù)，緊致技術(shù)，浮動(dòng)技術(shù)，搬家技術(shù)） 碎片問題的解決碎片問題的解決緊湊技術(shù)緊湊技術(shù)碎片問題：碎片問題： 經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑經(jīng)過一段時(shí)間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都很小，不足以滿足分配要求；但其總和滿足塊。它們每一個(gè)都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊

42、被稱為分配要求。這些空閑塊被稱為碎片碎片（內(nèi)內(nèi)、外外）。）。 問題問題：開銷大；移動(dòng)時(shí)機(jī)：開銷大；移動(dòng)時(shí)機(jī)有關(guān)碎片有關(guān)碎片操作系統(tǒng)原理操作系統(tǒng)原理 課程 第43張4.3.6 可重定位分區(qū)分配可重定位分區(qū)分配 1. 動(dòng)態(tài)重定位的引入動(dòng)態(tài)重定位的引入 用戶程序用戶程序1用戶程序用戶程序6用戶程序用戶程序310KB30KB14KB用戶程序用戶程序926KBa)緊湊前緊湊前用戶程序用戶程序1用戶程序用戶程序6用戶程序用戶程序3用戶程序用戶程序980KBb)緊湊后緊湊后操作系統(tǒng)原理操作系統(tǒng)原理 課程 第44張2. 動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位的實(shí)現(xiàn) “設(shè)置一個(gè)設(shè)置一個(gè)重定位寄存器重定位寄存器，存放內(nèi)存的初

43、始地址，存放內(nèi)存的初始地址 ” LOAD1,25003650100250050002500相對地址10000重定位寄存器LOAD1,250036510000101001250015000作業(yè)J處理機(jī)一側(cè) 存儲器一側(cè)主存4.3.6 可重定位分區(qū)分配可重定位分區(qū)分配 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第45張3. 動(dòng)態(tài)重定位分區(qū)分配算法動(dòng)態(tài)重定位分區(qū)分配算法 請求分配u.size分區(qū)檢索空閑分區(qū)鏈(表)找到大于u.size的可用區(qū)否?按動(dòng)態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首批空閑分區(qū)總和u.size?進(jìn)行緊湊形成連續(xù)空閑區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)否是無法分配返回否4.3.6 可重定位分區(qū)分配

44、可重定位分區(qū)分配 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第46張4.3.7 覆蓋與對換技術(shù)覆蓋與對換技術(shù)1. 覆蓋技術(shù)覆蓋技術(shù) 它是基于這樣一種思想提出來的，即一個(gè)程序并不需要一開它是基于這樣一種思想提出來的，即一個(gè)程序并不需要一開始就把它的全部指令和數(shù)據(jù)都裝入內(nèi)存后再執(zhí)行。始就把它的全部指令和數(shù)據(jù)都裝入內(nèi)存后再執(zhí)行。 覆蓋是指一個(gè)作業(yè)的若干程序段，或幾個(gè)作業(yè)的某些部分共覆蓋是指一個(gè)作業(yè)的若干程序段，或幾個(gè)作業(yè)的某些部分共享某一個(gè)存儲空間。享某一個(gè)存儲空間。把程序劃分為若干個(gè)功能上相對獨(dú)立的程把程序劃分為若干個(gè)功能上相對獨(dú)立的程序段，按照其自身的邏輯結(jié)構(gòu)將那些不會同時(shí)執(zhí)行的程序段共序段，按照其自身的

45、邏輯結(jié)構(gòu)將那些不會同時(shí)執(zhí)行的程序段共享同一塊內(nèi)存區(qū)域。享同一塊內(nèi)存區(qū)域。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第47張4.3.7 覆蓋與對換技術(shù)覆蓋與對換技術(shù)1. 覆蓋技術(shù)覆蓋技術(shù) 程序段先保存在磁盤上，當(dāng)有關(guān)程序段的先頭部分執(zhí)行結(jié)束，程序段先保存在磁盤上，當(dāng)有關(guān)程序段的先頭部分執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段（內(nèi)存把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段（內(nèi)存“擴(kuò)大擴(kuò)大”了）。了）。 一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，程序員要向系一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，程序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后由由操作系統(tǒng)完成自動(dòng)覆蓋。統(tǒng)指明覆蓋結(jié)構(gòu)，然后由由操作系統(tǒng)完成自動(dòng)覆蓋。 缺點(diǎn)

46、缺點(diǎn)：對用戶不透明，增加了用戶負(fù)擔(dān)。：對用戶不透明，增加了用戶負(fù)擔(dān)。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第48張4.3.7 覆蓋與對換技術(shù)覆蓋與對換技術(shù)2. 對換對換 所謂所謂“對換對換”， 是指把是指把不能運(yùn)行的進(jìn)程或者不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，暫時(shí)不用的程序和數(shù)據(jù)，上，以便騰出足夠的內(nèi)上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，數(shù)據(jù)，。對換是提高內(nèi)存利用率的有效措施。對換是提高內(nèi)存利用率的有效措施。 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第49張 二者之比較二者之比較 與覆蓋技術(shù)相比，交換技術(shù)不要求用

47、戶給出程序段之間與覆蓋技術(shù)相比，交換技術(shù)不要求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)。而且，交換發(fā)生在進(jìn)程或作業(yè)之間，而的邏輯覆蓋結(jié)構(gòu)。而且，交換發(fā)生在進(jìn)程或作業(yè)之間，而覆蓋發(fā)生在同一進(jìn)程或作業(yè)內(nèi)。此外，覆蓋只能覆蓋那些覆蓋發(fā)生在同一進(jìn)程或作業(yè)內(nèi)。此外，覆蓋只能覆蓋那些與覆蓋段無關(guān)的程序段。與覆蓋段無關(guān)的程序段。4.3.7 覆蓋與對換技術(shù)覆蓋與對換技術(shù)操作系統(tǒng)原理操作系統(tǒng)原理 課程 第50張4.7 請求分頁存儲管理請求分頁存儲管理 虛擬頁式管理虛擬頁式管理引入引入： 1. 常規(guī)存儲器管理方式常規(guī)存儲器管理方式(實(shí)模式實(shí)模式)的特征的特征 一次性。一次性。 (2) 駐留性。駐留性。 (1) 間局限性間

48、局限性(2) 間局限性間局限性2.局部性原理局部性原理操作系統(tǒng)原理操作系統(tǒng)原理 課程 第51張3. 虛擬存儲器虛擬存儲器 是指具有是指具有請求調(diào)入請求調(diào)入功能和功能和置換置換功能，功能， 能能從邏輯上對內(nèi)存容量加以從邏輯上對內(nèi)存容量加以擴(kuò)充擴(kuò)充的一種存儲器系統(tǒng)。其邏輯容量由的一種存儲器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和內(nèi)存容量和外存容量之和所決所決定，其運(yùn)行定，其運(yùn)行速度接近于內(nèi)存速度接近于內(nèi)存速度，而每位的速度，而每位的成本卻又接近于外存成本卻又接近于外存。引入引入： 4.7 請求分頁存儲管理請求分頁存儲管理4. 實(shí)現(xiàn)頁式虛擬存儲的硬件支持實(shí)現(xiàn)頁式虛擬存儲的硬件支持 請求分頁的頁表機(jī)制

49、請求分頁的頁表機(jī)制：它是在純分頁的頁表機(jī)制上：它是在純分頁的頁表機(jī)制上而形成而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)。的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)。 缺頁中斷機(jī)構(gòu)缺頁中斷機(jī)構(gòu)：即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時(shí)便產(chǎn)生：即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時(shí)便產(chǎn)生一缺頁中斷，以請求一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存。將所缺的頁調(diào)入內(nèi)存。 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)： 它同樣是在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成它同樣是在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的的操作系統(tǒng)原理操作系統(tǒng)原理 課程 第52張4.7.1 基本工作原理基本工作原理 在進(jìn)程開始運(yùn)行之前，在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面不是

50、裝入全部頁面，而是裝入一個(gè)，而是裝入一個(gè)或零個(gè)頁面，之后或零個(gè)頁面，之后根據(jù)根據(jù)進(jìn)程運(yùn)行的進(jìn)程運(yùn)行的需要需要，動(dòng)態(tài)裝入動(dòng)態(tài)裝入其它其它頁面頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則根據(jù)某種算法當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則根據(jù)某種算法淘汰淘汰某個(gè)頁面，以便裝入新的頁面。某個(gè)頁面，以便裝入新的頁面。 根據(jù)頁面調(diào)入的時(shí)機(jī)，又分為根據(jù)頁面調(diào)入的時(shí)機(jī)，又分為請請求求調(diào)入調(diào)入頁式管理和頁式管理和預(yù)調(diào)入預(yù)調(diào)入頁頁式管理。式管理。4.7 請求分頁存儲管理請求分頁存儲管理操作系統(tǒng)原理操作系統(tǒng)原理 課程 第53張4.7.2 請求分頁存儲的硬件機(jī)制請求分頁存儲的硬件機(jī)制4.7 請求分頁存儲管理請

51、求分頁存儲管理狀態(tài)位狀態(tài)位P：（：（駐留位駐留位、中斷位中斷位）表示該頁是在內(nèi)存還是在外存）表示該頁是在內(nèi)存還是在外存訪問位訪問位A：記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，以便根據(jù)訪問：記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，以便根據(jù)訪問 位來決定淘汰哪頁（由不同的算法決定）位來決定淘汰哪頁（由不同的算法決定）修改位修改位M：查看此頁是否在內(nèi)存中被修改過：查看此頁是否在內(nèi)存中被修改過外存地址外存地址：用于指出該頁在外存中的地址，供調(diào)入時(shí)參考：用于指出該頁在外存中的地址，供調(diào)入時(shí)參考 1.頁表機(jī)制擴(kuò)充頁表頁表機(jī)制擴(kuò)充頁表操作系統(tǒng)原理操作系統(tǒng)原理 課程 第54張2.缺頁中斷機(jī)構(gòu)缺頁中斷機(jī)構(gòu) 在地址映射過程中

52、，在頁表中發(fā)現(xiàn)所要訪問的頁在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存不在內(nèi)存，則則產(chǎn)生缺頁中斷產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中缺頁中斷處理程序斷處理程序，根據(jù)頁表中給出的外存地址，將該頁，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存調(diào)入內(nèi)存，使作業(yè)繼續(xù)運(yùn)行下去。使作業(yè)繼續(xù)運(yùn)行下去。 如果內(nèi)存中如果內(nèi)存中有空閑塊有空閑塊，則分配一頁，將新調(diào)入頁，則分配一頁，將新調(diào)入頁裝入裝入內(nèi)存，內(nèi)存，并修改頁表中相應(yīng)頁表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號。并修改頁表中相應(yīng)頁表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號。 若此時(shí)內(nèi)存中若此時(shí)內(nèi)存中沒有空閑塊沒有空閑塊，則要，

53、則要淘汰某頁淘汰某頁，若該頁在內(nèi)存，若該頁在內(nèi)存期間被修改過，則要將其寫回外存期間被修改過，則要將其寫回外存 。4.7 請求分頁存儲管理請求分頁存儲管理4.7.2 請求分頁存儲的硬件機(jī)制請求分頁存儲的硬件機(jī)制操作系統(tǒng)原理操作系統(tǒng)原理 課程 第55張涉涉及及6次次缺缺頁頁中中斷斷的的指指令令 頁面B：A：654321指令copy ATO B操作系統(tǒng)原理操作系統(tǒng)原理 課程 第56張3.地地址址變變換換機(jī)機(jī)構(gòu)構(gòu) 缺頁中斷處理保留CPU現(xiàn)場從外存中找到缺頁內(nèi)存滿否？選擇一頁換出該頁被修改否？將該頁寫回外存OS命令CPU從外存讀缺頁啟動(dòng)I/O硬件將一頁從外存換入內(nèi)存修改頁表否是是否頁表項(xiàng)在快表中？CPU

54、檢索快表訪問頁表否頁在內(nèi)存？修改訪問位和修改位形成物理地址地址變換結(jié)束否頁號頁表長度?開始程序請求訪問一頁產(chǎn)生缺頁中斷請求調(diào)頁修改快表是越界中斷是是請求分頁中的地址變換過程請求分頁中的地址變換過程 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第57張4.7.3 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法 1. 最小物理塊數(shù)的確定最小物理塊數(shù)的確定 是指能是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無法運(yùn)行。進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無法運(yùn)行。 進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決進(jìn)程應(yīng)獲得的最

55、少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、于指令的格式、 功能和尋址方式。功能和尋址方式。4.7 請求分頁存儲管理請求分頁存儲管理操作系統(tǒng)原理操作系統(tǒng)原理 課程 第58張2. 物理塊的分配策略物理塊的分配策略 在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時(shí)，變分配策略。在進(jìn)行置換時(shí)， 也可采取兩種策略，即全局置換也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。和局部置換。于是可組合出以下三種適用的策略。 1) 固定固定分配分配局部局部置換置換(Fixed Allocation,

56、Local Replacement) 2) 可變可變分配分配全局全局置換置換(Variable Allocation, Global Replacement) 3) 可變可變分配分配局部局部置換置換(Variable Allocation, Local Replacemen 4.7.3 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第59張3. 物理塊分配算法物理塊分配算法 1) 平均分配算法平均分配算法:這種方式貌似公平，但實(shí)際上是不公平的，因這種方式貌似公平，但實(shí)際上是不公平的，因?yàn)樗纯紤]到各進(jìn)程本身的大小。為它未考慮到各進(jìn)程本身的大小。4.7.3 內(nèi)存分

57、配策略和分配算法內(nèi)存分配策略和分配算法 2)按比例分配算法按比例分配算法:根據(jù)進(jìn)程的大小按比例分配物理塊。如果根據(jù)進(jìn)程的大小按比例分配物理塊。如果系統(tǒng)中共有系統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程所能分到的物，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為理塊數(shù)為bi，將有：，將有：bi應(yīng)該取整，它必須大于最小物理塊數(shù)。應(yīng)該取整，它必須大于最小物理塊數(shù)。niiSS1mSSbii操作系統(tǒng)原理操作系統(tǒng)原理 課程 第60張 3) 考慮優(yōu)先權(quán)的分配算法考

58、慮優(yōu)先權(quán)的分配算法 在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，成， 應(yīng)為它分配較多的內(nèi)存空間。應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：可供分配的所有物理塊分成兩部分：一部分按比例一部分按比例地分配給各地分配給各進(jìn)程；進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程。額后，分配給各進(jìn)程。 在有的系統(tǒng)中，如重要的實(shí)時(shí)控制系統(tǒng)，則可能是完全按優(yōu)在有的系統(tǒng)中，如重要的實(shí)時(shí)控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)

59、來為各進(jìn)程分配其物理塊的。先權(quán)來為各進(jìn)程分配其物理塊的。 3. 物理塊分配算法物理塊分配算法 4.7.3 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法 操作系統(tǒng)原理操作系統(tǒng)原理 課程 第61張4.7.4 調(diào)頁策略調(diào)頁策略 1. 何時(shí)調(diào)入頁面何時(shí)調(diào)入頁面 預(yù)調(diào)預(yù)調(diào)頁策略頁策略 2) 請請求求調(diào)調(diào)頁策略頁策略 4.7 請求分頁存儲管理請求分頁存儲管理2. 從何處調(diào)入頁面從何處調(diào)入頁面 在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)文件區(qū)和用于存放對換頁面的和用于存放對換頁面的對換區(qū)對換區(qū)。通常，由于對換區(qū)是。通常，由于對換區(qū)是采用連續(xù)分配方式

60、，而事件是采用離散分配方式，故對換區(qū)采用連續(xù)分配方式，而事件是采用離散分配方式，故對換區(qū)的磁盤的磁盤I/O速度比文件區(qū)的高。速度比文件區(qū)的高。操作系統(tǒng)原理操作系統(tǒng)原理 課程 第62張 每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)，便向每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)，便向CPUCPU發(fā)出一缺頁中斷，發(fā)出一缺頁中斷，中斷處理程序首先保留中斷處理程序首先保留CPUCPU環(huán)境，分析中斷原因后，環(huán)境，分析中斷原因后， 轉(zhuǎn)入缺頁中斷轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后，處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后， 如果此時(shí)內(nèi)存能容納新頁，則啟動(dòng)磁盤如果此時(shí)內(nèi)存能容納新頁，則