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

1、第第4章章 內(nèi)存管理內(nèi)存管理4.1 4.1 內(nèi)存管理功能內(nèi)存管理功能4.2 4.2 分區(qū)管理分區(qū)管理4.3 4.3 頁式管理頁式管理 4.4 4.4 段式管理段式管理 4.5 4.5 段頁式管理段頁式管理 4.1 4.1 內(nèi)存管理的功能內(nèi)存管理的功能 內(nèi)存空間的分配和回收內(nèi)存空間的分配和回收地址轉(zhuǎn)換地址轉(zhuǎn)換內(nèi)存空間的共享和保護內(nèi)存空間的共享和保護內(nèi)存空間的邏輯擴充內(nèi)存空間的邏輯擴充4.1.1 4.1.1 內(nèi)存的分配與回收內(nèi)存的分配與回收內(nèi)存分配按分配時機的不同，可分為三種方式：內(nèi)存分配按分配時機的不同，可分為三種方式： 1.1.直接分配直接分配 采用物理內(nèi)存地址編寫程序。使用這種方式，采用物理

2、內(nèi)存地址編寫程序。使用這種方式，必必須事先劃定內(nèi)存的使用空間須事先劃定內(nèi)存的使用空間，因此，內(nèi)存利用率不高，因此，內(nèi)存利用率不高，用戶使用較困難。用戶使用較困難。 2.2.靜態(tài)分配靜態(tài)分配 在作業(yè)運行之前各目標(biāo)模塊連接后，把整個作業(yè)在作業(yè)運行之前各目標(biāo)模塊連接后，把整個作業(yè)一次性全部裝入內(nèi)存，并在作業(yè)的整個運行過程中，一次性全部裝入內(nèi)存，并在作業(yè)的整個運行過程中，不允許作業(yè)再申請其他內(nèi)存，或在內(nèi)存中移動位置。不允許作業(yè)再申請其他內(nèi)存，或在內(nèi)存中移動位置。也就是說，也就是說，內(nèi)存分配是在作業(yè)運行前一次性完成的。內(nèi)存分配是在作業(yè)運行前一次性完成的。 4.1.1 4.1.1 內(nèi)存的分配與回收內(nèi)存的分

3、配與回收3.3.動態(tài)分配動態(tài)分配 作業(yè)要求的基本內(nèi)存空間是在目標(biāo)模塊裝作業(yè)要求的基本內(nèi)存空間是在目標(biāo)模塊裝入內(nèi)存時分配的，但在作業(yè)運行過程中，允許入內(nèi)存時分配的，但在作業(yè)運行過程中，允許作業(yè)申請附加的內(nèi)存空間，或是在內(nèi)存中移動，作業(yè)申請附加的內(nèi)存空間，或是在內(nèi)存中移動，即即分配工作可以在作業(yè)運行前及運行過程中逐分配工作可以在作業(yè)運行前及運行過程中逐步完成。步完成。4.1.2 4.1.2 地址轉(zhuǎn)換地址轉(zhuǎn)換 把用戶程序裝入內(nèi)存時對有關(guān)指令的把用戶程序裝入內(nèi)存時對有關(guān)指令的地址部分的修改定義為從程序地址到內(nèi)存地地址部分的修改定義為從程序地址到內(nèi)存地址的址的地址轉(zhuǎn)換地址轉(zhuǎn)換，或稱為，或稱為地址重定位地

4、址重定位。1.1.物理地址與邏輯地址物理地址與邏輯地址 物理地址物理地址也稱內(nèi)存地址，它是用于唯一也稱內(nèi)存地址，它是用于唯一標(biāo)識一個內(nèi)存單元的編號。所有的物理地址標(biāo)識一個內(nèi)存單元的編號。所有的物理地址構(gòu)成了構(gòu)成了物理空間物理空間。4.1.2 4.1.2 地址轉(zhuǎn)換地址轉(zhuǎn)換 邏輯地址邏輯地址也稱也稱程序地址程序地址，它是指在源程序經(jīng)，它是指在源程序經(jīng)過匯編或編譯后形成的目標(biāo)代碼中，用于反映目過匯編或編譯后形成的目標(biāo)代碼中，用于反映目標(biāo)代碼中指令或數(shù)據(jù)的相對位置關(guān)系的地址。標(biāo)代碼中指令或數(shù)據(jù)的相對位置關(guān)系的地址。 邏輯地址都是以邏輯地址都是以“0”0”為基址順序進行編址的，為基址順序進行編址的，這樣

5、生成的目標(biāo)程序占據(jù)一定的地址空間，稱為這樣生成的目標(biāo)程序占據(jù)一定的地址空間，稱為程序的程序的邏輯地址空間邏輯地址空間，簡稱，簡稱邏輯空間邏輯空間。 用符號地址（符號名）表示的程序空間稱為用符號地址（符號名）表示的程序空間稱為名空間名空間。 地址重定位的原因是什么地址重定位的原因是什么? 因為程序在裝入內(nèi)存后，其邏輯地因為程序在裝入內(nèi)存后，其邏輯地址和物理地址不一致。址和物理地址不一致。地址映射地址映射Load A 200Load A 200 3456 3456 。 。12001200物理地址空間物理地址空間Load A data1Load A data1data1 3456data1 3456

6、源程序源程序Load A 200Load A 200 3456 34560 0100100200200編譯編譯連接連接邏輯地址空間邏輯地址空間BA=1000BA=1000（名空間）（名空間）靜態(tài)重定位靜態(tài)重定位 是在程序執(zhí)行之前由操作系統(tǒng)的連接裝入程序是在程序執(zhí)行之前由操作系統(tǒng)的連接裝入程序完成地址轉(zhuǎn)換。完成地址轉(zhuǎn)換。 優(yōu)點：不需要硬件的支持。優(yōu)點：不需要硬件的支持。 缺點：程序必須占用連續(xù)的內(nèi)存空間；缺點：程序必須占用連續(xù)的內(nèi)存空間； 一旦程序裝入后不能移動。一旦程序裝入后不能移動。 2.2.地址重定位的方式地址重定位的方式動態(tài)重定位動態(tài)重定位 在程序執(zhí)行期間進行的地址轉(zhuǎn)換，是由專門的在程序

7、執(zhí)行期間進行的地址轉(zhuǎn)換，是由專門的硬件機構(gòu)來完成的。硬件機構(gòu)來完成的。優(yōu)點：程序占用的內(nèi)存空間是動態(tài)可變的，當(dāng)程序從優(yōu)點：程序占用的內(nèi)存空間是動態(tài)可變的，當(dāng)程序從某個存儲區(qū)移到另一個區(qū)域時，只需要修改相應(yīng)的某個存儲區(qū)移到另一個區(qū)域時，只需要修改相應(yīng)的寄存器寄存器BRBR的內(nèi)容即可。的內(nèi)容即可。缺點：需要硬件的支持；缺點：需要硬件的支持； 實現(xiàn)存儲管理的軟件算法較為復(fù)雜。實現(xiàn)存儲管理的軟件算法較為復(fù)雜。03456.LOAD A 200.0100200300.LOAD A 2003456110012001300200VR+1000BR動態(tài)重定位示意圖動態(tài)重定位示意圖4.1.3 4.1.3 內(nèi)存的共

8、享和保護內(nèi)存的共享和保護4.1.3 4.1.3 內(nèi)存的共享和保護內(nèi)存的共享和保護 在實現(xiàn)內(nèi)存分配與共享時，必須解決內(nèi)存中信在實現(xiàn)內(nèi)存分配與共享時，必須解決內(nèi)存中信息的保護問題。存儲保護的工作一般由硬件和軟件息的保護問題。存儲保護的工作一般由硬件和軟件配合實現(xiàn)。配合實現(xiàn)。1.1.上、下界存儲保護上、下界存儲保護：系統(tǒng)可為每個作業(yè)設(shè)置一對：系統(tǒng)可為每個作業(yè)設(shè)置一對上、下界寄存器，分別用來存放當(dāng)前運行作業(yè)在內(nèi)上、下界寄存器，分別用來存放當(dāng)前運行作業(yè)在內(nèi)存空間的上、下邊界地址，用它們來限制用戶程序存空間的上、下邊界地址，用它們來限制用戶程序的活動范圍。的活動范圍。 2.2.基址限長存儲保護基址限長存儲

9、保護：上、下界保護的一個變種：上、下界保護的一個變種是采用基址是采用基址限長存儲保護。限長存儲保護。 4.1.3 4.1.3 內(nèi)存的保護內(nèi)存的保護4.1.4 4.1.4 內(nèi)存空間的邏輯擴充內(nèi)存空間的邏輯擴充 對內(nèi)存進行邏輯上的擴充，現(xiàn)在普遍采用覆蓋、對內(nèi)存進行邏輯上的擴充，現(xiàn)在普遍采用覆蓋、交換和虛擬存儲器技術(shù)。交換和虛擬存儲器技術(shù)。 虛擬存儲器虛擬存儲器是具有請求調(diào)入功能和置換功能，是具有請求調(diào)入功能和置換功能，能僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲能僅把作業(yè)的一部分裝入內(nèi)存便可運行作業(yè)的存儲器系統(tǒng)，它是一種能從邏輯上對內(nèi)存容量進行擴充器系統(tǒng)，它是一種能從邏輯上對內(nèi)存容量進行擴充的虛構(gòu)

10、的存儲器系統(tǒng)。的虛構(gòu)的存儲器系統(tǒng)。 虛擬存儲器的理論基礎(chǔ)是程序的局部性原理。虛擬存儲器的理論基礎(chǔ)是程序的局部性原理。包括包括時間局部性時間局部性和和空間局部性空間局部性。什么是時間局部性什么是時間局部性? ? 什么是空間局部性什么是空間局部性? ?4.1.4 4.1.4 內(nèi)存空間的邏輯擴充內(nèi)存空間的邏輯擴充 虛擬存儲器的基本思想虛擬存儲器的基本思想是把有限的內(nèi)存空間與是把有限的內(nèi)存空間與大容量的外存統(tǒng)一管理，構(gòu)成一個遠(yuǎn)大于實際內(nèi)存大容量的外存統(tǒng)一管理，構(gòu)成一個遠(yuǎn)大于實際內(nèi)存的、虛擬的存儲器。此時，外存是作為內(nèi)存的直接的、虛擬的存儲器。此時，外存是作為內(nèi)存的直接延伸，用戶并不會感覺到內(nèi)、外存的區(qū)

11、別，即把兩延伸，用戶并不會感覺到內(nèi)、外存的區(qū)別，即把兩級存儲器當(dāng)作一級存儲器來看待。級存儲器當(dāng)作一級存儲器來看待。 一個作業(yè)運行時，其全部信息裝入虛存，實際一個作業(yè)運行時，其全部信息裝入虛存，實際上可能只有當(dāng)前運行的必需一部分信息存入內(nèi)存，上可能只有當(dāng)前運行的必需一部分信息存入內(nèi)存，其他則存于外存，當(dāng)所訪問的信息不在內(nèi)存時，系其他則存于外存，當(dāng)所訪問的信息不在內(nèi)存時，系統(tǒng)自動將其從外存調(diào)入內(nèi)存。統(tǒng)自動將其從外存調(diào)入內(nèi)存。4.2.1 4.2.1 單分區(qū)管理單分區(qū)管理4.2.2 4.2.2 固定分區(qū)固定分區(qū)4.2.3 4.2.3 可變分區(qū)可變分區(qū)4.2.4 4.2.4 覆蓋與交換覆蓋與交換4.2

12、4.2 分區(qū)管理分區(qū)管理 4.2.1 4.2.1 單分區(qū)管理單分區(qū)管理 這是一種最簡單的連續(xù)存儲管理方式。但只能用于這是一種最簡單的連續(xù)存儲管理方式。但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。單用戶、單任務(wù)的操作系統(tǒng)中。系統(tǒng)區(qū)：僅提供給操作系統(tǒng)使用，通常設(shè)置在內(nèi)系統(tǒng)區(qū)：僅提供給操作系統(tǒng)使用，通常設(shè)置在內(nèi)存的低址部分；存的低址部分；用戶區(qū)：指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供用戶區(qū)：指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。給用戶使用。空閑區(qū)：指剩余部分存儲區(qū)。空閑區(qū)：指剩余部分存儲區(qū)。4.2.2 4.2.2 固定分區(qū)固定分區(qū) 把可用空間劃分成若干個固定大小的把可用空間劃分成若干個固定大小的存儲區(qū)

13、，除操作系統(tǒng)占用一個區(qū)域外，其存儲區(qū)，除操作系統(tǒng)占用一個區(qū)域外，其余區(qū)域為系統(tǒng)中多個用戶共享，因為在系余區(qū)域為系統(tǒng)中多個用戶共享，因為在系統(tǒng)運行期間，分區(qū)大小、數(shù)目都不變，所統(tǒng)運行期間，分區(qū)大小、數(shù)目都不變，所以固定分區(qū)也稱為以固定分區(qū)也稱為靜態(tài)分區(qū)靜態(tài)分區(qū)。分區(qū)說明表分區(qū)說明表4.2.3 4.2.3 可變分區(qū)可變分區(qū)1 1、基本思想：、基本思想：分區(qū)大小、數(shù)目可變，所以可變分區(qū)大小、數(shù)目可變，所以可變分區(qū)也稱為分區(qū)也稱為動態(tài)分區(qū)動態(tài)分區(qū)。 它是根據(jù)用戶作業(yè)的大小，在作業(yè)要求裝它是根據(jù)用戶作業(yè)的大小，在作業(yè)要求裝入主存時，動態(tài)地劃分分區(qū)，使分區(qū)的大小正入主存時，動態(tài)地劃分分區(qū)，使分區(qū)的大小正好

14、適應(yīng)作業(yè)的要求。好適應(yīng)作業(yè)的要求。 可變分區(qū)存儲管理方式必須解決三個問題：可變分區(qū)存儲管理方式必須解決三個問題：一是分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)；一是分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)；二是分區(qū)的分配算法；二是分區(qū)的分配算法；三是分區(qū)的分配和回收。三是分區(qū)的分配和回收。 可變分區(qū)內(nèi)存使用情況示意圖可變分區(qū)內(nèi)存使用情況示意圖2 2可變分區(qū)管理中的數(shù)據(jù)結(jié)構(gòu)可變分區(qū)管理中的數(shù)據(jù)結(jié)構(gòu) 最先適應(yīng)算法最先適應(yīng)算法 按空閑區(qū)地址遞增的次序分配按空閑區(qū)地址遞增的次序分配最優(yōu)適應(yīng)算法最優(yōu)適應(yīng)算法 按空閑區(qū)由小到大的次序分配按空閑區(qū)由小到大的次序分配最壞適應(yīng)算法最壞適應(yīng)算法 按空閑區(qū)由大到小的次序分配按空閑區(qū)由大到小的次序分配

15、3 3內(nèi)存的分配算法內(nèi)存的分配算法 （1 1）最先適應(yīng)分配算法（）最先適應(yīng)分配算法（FFFF） 它要求空閑分區(qū)表中的記錄它要求空閑分區(qū)表中的記錄按地址遞增的順序按地址遞增的順序排列排列。在每次分配主存時，總是從第。在每次分配主存時，總是從第1 1條記錄開始條記錄開始順序查找空閑分區(qū)表，找到第一個能滿足作業(yè)長度順序查找空閑分區(qū)表，找到第一個能滿足作業(yè)長度要求的空閑區(qū)，分割這個空閑區(qū)。一部分分配給作要求的空閑區(qū)，分割這個空閑區(qū)。一部分分配給作業(yè)，另一部分仍作為空閑區(qū)。業(yè)，另一部分仍作為空閑區(qū)。 特點是算法簡單，容易產(chǎn)生過多的主存碎片。特點是算法簡單，容易產(chǎn)生過多的主存碎片。 主存碎片主存碎片是指小

16、的不能使用的主存空間；這種是指小的不能使用的主存空間；這種算法把大的空閑區(qū)分成了小的空閑區(qū)，當(dāng)有大作業(yè)算法把大的空閑區(qū)分成了小的空閑區(qū)，當(dāng)有大作業(yè)要求分配時，不能滿足要求，降低了系統(tǒng)的效率。要求分配時，不能滿足要求，降低了系統(tǒng)的效率。 （2 2）最優(yōu)適應(yīng)分配算法（）最優(yōu)適應(yīng)分配算法（BFBF）（3 3）最壞適應(yīng)分配算法（）最壞適應(yīng)分配算法（WFWF） 有作業(yè)序列：作業(yè)有作業(yè)序列：作業(yè)A A要求要求18K18K；作業(yè)；作業(yè)B B要求要求25K25K，作業(yè)，作業(yè)C C要求要求30K30K。如下圖。如下圖。 系統(tǒng)中空閑區(qū)按三種算法組成的空系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊列如下，閑區(qū)隊列如下，經(jīng)分

17、析可知：最佳適應(yīng)經(jīng)分析可知：最佳適應(yīng)法對這個作業(yè)序列是合適的，而其它兩法對這個作業(yè)序列是合適的，而其它兩種對該作業(yè)序列是不合適的。種對該作業(yè)序列是不合適的。舉例舉例 有作業(yè)序列：作業(yè)有作業(yè)序列：作業(yè)A A要求要求21K21K；作業(yè)；作業(yè)B B要求要求30K30K，作業(yè)作業(yè)C C要求要求25K25K，分析使用哪種分配算法最佳？，分析使用哪種分配算法最佳？課堂練習(xí)：課堂練習(xí)：4 4內(nèi)存的回收內(nèi)存的回收 當(dāng)某一個用戶作業(yè)完成釋放所占分區(qū)當(dāng)某一個用戶作業(yè)完成釋放所占分區(qū)時，系統(tǒng)應(yīng)進行回收。時，系統(tǒng)應(yīng)進行回收。 在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與在可變式分區(qū)中，應(yīng)該檢查回收區(qū)與內(nèi)存中前后空閑區(qū)是否相鄰：內(nèi)

18、存中前后空閑區(qū)是否相鄰： 若相鄰，則應(yīng)進行合并，形成一個較若相鄰，則應(yīng)進行合并，形成一個較大的空閑區(qū)，并對相應(yīng)的鏈表指針進行修大的空閑區(qū)，并對相應(yīng)的鏈表指針進行修改；若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)改；若不相鄰，應(yīng)將空閑區(qū)插入到空閑區(qū)鏈表的適當(dāng)位置。鏈表的適當(dāng)位置。n回收的分區(qū)前后沒有相鄰的空閑分區(qū)?；厥盏姆謪^(qū)前后沒有相鄰的空閑分區(qū)。 n回收分區(qū)的前面有相鄰的空閑分區(qū)?；厥辗謪^(qū)的前面有相鄰的空閑分區(qū)。 n回收分區(qū)的后面有相鄰的空閑分區(qū)?；厥辗謪^(qū)的后面有相鄰的空閑分區(qū)。 n回收分區(qū)的前后都有相鄰的空閑分區(qū)?；厥辗謪^(qū)的前后都有相鄰的空閑分區(qū)。5 5、分區(qū)保護、分區(qū)保護 存儲保護是為了防止一個作業(yè)破

19、壞操作系統(tǒng)或存儲保護是為了防止一個作業(yè)破壞操作系統(tǒng)或其他作業(yè)。其他作業(yè)。1. 1. 上、下界寄存器保護法：上、下界寄存器保護法：上界寄存器上界寄存器物理地址物理地址下界寄存器，超出這個范圍便產(chǎn)生保護性中斷。下界寄存器，超出這個范圍便產(chǎn)生保護性中斷。2. 2. 基址、限長寄存器保護法：基址、限長寄存器保護法：基址寄存器基址寄存器物理地物理地址址基址寄存器基址寄存器+ +限長寄存器，如果超過了限長，限長寄存器，如果超過了限長，則發(fā)出越界中斷信號，并停止作業(yè)的運行。則發(fā)出越界中斷信號，并停止作業(yè)的運行。3. 3. 存儲保護鍵方法：存儲保護鍵方法： 系統(tǒng)為每個分區(qū)設(shè)一個保護鍵，在程序狀態(tài)字系統(tǒng)為每個分

20、區(qū)設(shè)一個保護鍵，在程序狀態(tài)字中也設(shè)同樣的保護鍵字段，訪問內(nèi)存時檢查鍵的配中也設(shè)同樣的保護鍵字段，訪問內(nèi)存時檢查鍵的配對情況，如果不匹配則產(chǎn)生保護性中斷。對情況，如果不匹配則產(chǎn)生保護性中斷。 4.2.4 碎片問題及其解決辦法碎片問題及其解決辦法 在分區(qū)分配方式中經(jīng)過不斷地分配和釋放后，在分區(qū)分配方式中經(jīng)過不斷地分配和釋放后，內(nèi)存中空閑分區(qū)會變得越來越多和越來越小，產(chǎn)生內(nèi)存中空閑分區(qū)會變得越來越多和越來越小，產(chǎn)生了許多碎片。了許多碎片。 所謂所謂碎片碎片是指內(nèi)存中出現(xiàn)的一些零散的小空閑是指內(nèi)存中出現(xiàn)的一些零散的小空閑區(qū)域。區(qū)域。 由于碎片都很小，故無法再利用。如果內(nèi)存中由于碎片都很小，故無法再利用

21、。如果內(nèi)存中碎片很多，將會造成嚴(yán)重的存儲資源浪費。碎片很多，將會造成嚴(yán)重的存儲資源浪費。 4.2.4 碎片問題及其解決辦法碎片問題及其解決辦法移動移動( (緊湊緊湊/ /緊縮緊縮/ /拼接拼接) )技術(shù)：技術(shù)： 解決碎片的方法是移動所有的占用區(qū)域，使所解決碎片的方法是移動所有的占用區(qū)域，使所有的空閑區(qū)合并成一片連續(xù)區(qū)域，這一技術(shù)稱為有的空閑區(qū)合并成一片連續(xù)區(qū)域，這一技術(shù)稱為移移動技術(shù)（拼接）動技術(shù)（拼接）。 移動技術(shù)可解決碎片問題，從而提高內(nèi)存的利移動技術(shù)可解決碎片問題，從而提高內(nèi)存的利用率。用率。 移動技術(shù)可以集中分散的空閑區(qū)，便于作業(yè)動移動技術(shù)可以集中分散的空閑區(qū)，便于作業(yè)動態(tài)擴充內(nèi)存。態(tài)

22、擴充內(nèi)存。4.2.5 覆蓋與交換覆蓋與交換n覆蓋覆蓋：一個作業(yè)的若干程序段，或幾個作業(yè)的某：一個作業(yè)的若干程序段，或幾個作業(yè)的某些部分共享某一個存儲空間。些部分共享某一個存儲空間。n程序段先保存在磁盤上，當(dāng)有關(guān)程序段的前一部程序段先保存在磁盤上，當(dāng)有關(guān)程序段的前一部分執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面分執(zhí)行結(jié)束，把后續(xù)程序段調(diào)入內(nèi)存，覆蓋前面的程序段。的程序段。n一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，程一般要求作業(yè)各模塊之間有明確的調(diào)用結(jié)構(gòu)，程序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后由操作系統(tǒng)完序員要向系統(tǒng)指明覆蓋結(jié)構(gòu)，然后由操作系統(tǒng)完成自動覆蓋。成自動覆蓋。A8KE4KF10KC10KB8KD

23、12K作業(yè)作業(yè)X的調(diào)用結(jié)構(gòu)的調(diào)用結(jié)構(gòu)作業(yè)作業(yè)X X的常駐區(qū)的常駐區(qū) A A（8K8K）覆蓋區(qū)覆蓋區(qū)0（10K）覆蓋區(qū)覆蓋區(qū)1（12K） BC C D E F為什么引入交換技術(shù)？為什么引入交換技術(shù)？ 當(dāng)內(nèi)存空間緊張時，系統(tǒng)將內(nèi)存中某當(dāng)內(nèi)存空間緊張時，系統(tǒng)將內(nèi)存中某些進程暫時移到外存，把外存中某些進程換些進程暫時移到外存，把外存中某些進程換進內(nèi)存，占據(jù)前者所占用的區(qū)域，這種技術(shù)進內(nèi)存，占據(jù)前者所占用的區(qū)域，這種技術(shù)是進程在內(nèi)存與外存之間的動態(tài)調(diào)度。是進程在內(nèi)存與外存之間的動態(tài)調(diào)度。 多用于分時系統(tǒng)中。多用于分時系統(tǒng)中。2.2.交換交換 與覆蓋技術(shù)相比，交換技術(shù)不要求用戶與覆蓋技術(shù)相比，交換技術(shù)不要

24、求用戶給出程序段之間的邏輯覆蓋結(jié)構(gòu)。給出程序段之間的邏輯覆蓋結(jié)構(gòu)。交換與覆蓋的不同之處：交換與覆蓋的不同之處： 交換發(fā)生在進程或作業(yè)之間，而覆蓋發(fā)生在交換發(fā)生在進程或作業(yè)之間，而覆蓋發(fā)生在同一進程或作業(yè)內(nèi)。同一進程或作業(yè)內(nèi)。 覆蓋只能覆蓋那些與覆蓋段無關(guān)的程序段。覆蓋只能覆蓋那些與覆蓋段無關(guān)的程序段。2.2.交換交換4.3 4.3 頁式管理頁式管理 4.3.14.3.1 頁式管理概述頁式管理概述1.1.基本原理：基本原理： 分頁存儲管理是將一個進程的分頁存儲管理是將一個進程的地址空間地址空間劃分劃分成若干個大小相等的區(qū)域，稱為成若干個大小相等的區(qū)域，稱為頁頁。 相應(yīng)地，將相應(yīng)地，將內(nèi)存空間內(nèi)存

25、空間劃分成與頁相同大小的劃分成與頁相同大小的若干個物理塊，稱為若干個物理塊，稱為塊或頁幀塊或頁幀。 在為進程分配內(nèi)存時，將進程中若干頁分別在為進程分配內(nèi)存時，將進程中若干頁分別裝入多個不相鄰接的塊中。裝入多個不相鄰接的塊中。 4.3.1 4.3.1 頁式管理概述頁式管理概述2.2.地址結(jié)構(gòu)：地址結(jié)構(gòu)： 分頁系統(tǒng)的地址結(jié)構(gòu)由兩部分組成：前一部分分頁系統(tǒng)的地址結(jié)構(gòu)由兩部分組成：前一部分為為頁號頁號P P；后一部分為位移量；后一部分為位移量W W，即，即頁內(nèi)位移頁內(nèi)位移。 在下圖中地址為在下圖中地址為3232位，其中位，其中0 01111位為頁內(nèi)位位為頁內(nèi)位移（每頁的大小為移（每頁的大小為4K4K）

26、，），12123131位為頁號，所以允位為頁號，所以允許地址空間的大小最多為許地址空間的大小最多為1M1M個頁。個頁。 地址結(jié)構(gòu)示例地址結(jié)構(gòu)示例 31 12 11 0 頁號頁號 P 位移量位移量W4.3.2 4.3.2 靜態(tài)分頁靜態(tài)分頁 基本思想是必須裝入作業(yè)的全部頁面后才能基本思想是必須裝入作業(yè)的全部頁面后才能執(zhí)行該作業(yè)。執(zhí)行該作業(yè)。 1. 1. 頁表：頁表：系統(tǒng)為每個進程建立了一張系統(tǒng)為每個進程建立了一張頁面映射表頁面映射表，簡稱簡稱頁表頁表。 每個頁在頁表中占一個表項，記錄該頁在內(nèi)每個頁在頁表中占一個表項，記錄該頁在內(nèi)存中對應(yīng)的物理塊號。進程在執(zhí)行時，通過查找存中對應(yīng)的物理塊號。進程在執(zhí)

27、行時，通過查找頁表，就可以找到每頁所對應(yīng)的物理塊號。頁表，就可以找到每頁所對應(yīng)的物理塊號。 頁表的作用是實現(xiàn)從頁號到物理塊號的地址頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射。映射。頁號頁號塊號塊號0 02 21 13 32 28 8頁表頁表用戶程序0 頁1 頁2 頁3 頁4 頁5 頁n 頁頁表頁號塊號02132638495內(nèi)存012345678910地址空間地址空間物理空間物理空間4.3.2 4.3.2 靜態(tài)分頁靜態(tài)分頁 2.2.靜態(tài)頁式管理的分配與回收：靜態(tài)頁式管理的分配與回收：內(nèi)存空間以塊為單位，內(nèi)存空間以塊為單位，要用數(shù)據(jù)結(jié)構(gòu)記錄內(nèi)存中塊的情況。要用數(shù)據(jù)結(jié)構(gòu)記錄內(nèi)存中塊的情況。1 1、位

28、示圖：、位示圖：每一位對應(yīng)一個塊，每一位對應(yīng)一個塊，0 0 空閑，空閑，1 1 已分配。已分配。2 2、空閑塊鏈：、空閑塊鏈：所有空閑塊組成一個空閑塊鏈，鏈?zhǔn)追炙锌臻e塊組成一個空閑塊鏈，鏈?zhǔn)追峙洌溛不厥?。配，鏈尾回收? 3、內(nèi)存分塊表：、內(nèi)存分塊表：表項包括塊號，進程號，頁號，狀態(tài)表項包括塊號，進程號，頁號，狀態(tài)等。狀態(tài)為等。狀態(tài)為0 0，空閑，空閑，1 1，已分配。，已分配。 4.3.2 4.3.2 靜態(tài)分頁靜態(tài)分頁3.3.地址轉(zhuǎn)換：地址轉(zhuǎn)換： 當(dāng)進程要訪問某個邏輯地址當(dāng)進程要訪問某個邏輯地址M M中的數(shù)據(jù)時，需中的數(shù)據(jù)時，需做如下地址變換：做如下地址變換：1 1、將地址空間的邏輯地址

29、、將地址空間的邏輯地址M M轉(zhuǎn)換為轉(zhuǎn)換為頁式邏輯地址頁式邏輯地址；2 2、以頁號、以頁號P P為索引去檢索頁表，找到相對應(yīng)表項為索引去檢索頁表，找到相對應(yīng)表項頁表始址頁號頁表始址頁號P P； 從中讀出對應(yīng)的物理塊號從中讀出對應(yīng)的物理塊號B B；3 3、計算物理地址、計算物理地址B B頁長頁內(nèi)位移頁長頁內(nèi)位移W W。 求出有效地址求出有效地址20442044所對應(yīng)的物理地址，要所對應(yīng)的物理地址，要求寫出地址轉(zhuǎn)換過程。求寫出地址轉(zhuǎn)換過程。頁式邏輯地址：頁號：頁式邏輯地址：頁號：2044/1024=1 2044/1024=1 ，頁，頁內(nèi)位移量：內(nèi)位移量：2044 MOD 1024=10202044

30、MOD 1024=1020物理地址：物理地址：5 5* *1024+1020=61401024+1020=6140在采用頁面存儲管理的系統(tǒng)中，某作業(yè)在采用頁面存儲管理的系統(tǒng)中，某作業(yè)的邏輯地址空間為的邏輯地址空間為4 4頁（每頁頁（每頁1k1k），且已知），且已知該作業(yè)的頁表如下：該作業(yè)的頁表如下：頁號頁號塊號塊號0 07 71 15 52 23 33 39 9分頁中的地址轉(zhuǎn)換機構(gòu)分頁中的地址轉(zhuǎn)換機構(gòu)頁表始址頁表始址頁表長度頁表長度頁表寄存器頁表寄存器頁號頁號P P頁內(nèi)地址頁內(nèi)地址W W頁式邏輯地址頁式邏輯地址越界中斷越界中斷 =Lpp. . .快表快表 b+頁號頁號p 頁內(nèi)地址頁內(nèi)地址dPd

31、物理地址物理地址頁表地址寄存器頁表地址寄存器頁表長度寄存器頁表長度寄存器邏輯地址邏輯地址4.4.引入快表的地址轉(zhuǎn)換引入快表的地址轉(zhuǎn)換5 5頁的共享和保護頁的共享和保護（1 1）頁的共享。）頁的共享。頁的共享可以節(jié)省主存空間。頁式頁的共享可以節(jié)省主存空間。頁式存儲管理能方便地實現(xiàn)多個作業(yè)共享程序和數(shù)據(jù)。存儲管理能方便地實現(xiàn)多個作業(yè)共享程序和數(shù)據(jù)。 共享的方法是共享的方法是使各自頁表中的有關(guān)表目指向使各自頁表中的有關(guān)表目指向共享信息的主存塊。共享信息的主存塊。（2 2）頁的保護。）頁的保護。在頁式存儲管理方式下的保護有三在頁式存儲管理方式下的保護有三種情況：種情況： 共享頁的保護、不同作業(yè)所占空間

32、的保護、共享頁的保護、不同作業(yè)所占空間的保護、邏輯地址轉(zhuǎn)換成物理地址的保護。邏輯地址轉(zhuǎn)換成物理地址的保護。4.3.3 4.3.3 動態(tài)分頁動態(tài)分頁( (請求分頁請求分頁) ) 1.1.基本思想：基本思想： 采用采用虛擬存儲技術(shù)虛擬存儲技術(shù)，只需裝入作業(yè)的部分，只需裝入作業(yè)的部分頁面就能啟動作業(yè)的運行。頁面就能啟動作業(yè)的運行。 以后再通過調(diào)頁功能和頁面置換功能，陸以后再通過調(diào)頁功能和頁面置換功能，陸續(xù)把將要運行的頁面調(diào)入內(nèi)存，同時把暫不運續(xù)把將要運行的頁面調(diào)入內(nèi)存，同時把暫不運行的頁面置換到外存上，置換時以頁面為單位。行的頁面置換到外存上，置換時以頁面為單位。 2.2.擴充的頁表結(jié)構(gòu)擴充的頁表結(jié)

33、構(gòu) 0 0 1 1 0 0 0 0修改位修改位 1 1 220220 3 3 1 1 0 0 200200 1515 0 0 0 0 5050 1414 1 1 1 1 112112 1010 1 1訪問位訪問位外存地址外存地址塊號塊號駐留位駐留位 3 3 2 2 1 1 0 0頁號頁號3.3.缺頁中斷缺頁中斷 在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在在請求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存時，便要產(chǎn)生一內(nèi)存時，便要產(chǎn)生一缺頁中斷缺頁中斷，請求，請求OSOS將所缺頁調(diào)將所缺頁調(diào)入內(nèi)存。入內(nèi)存。與一般中斷的主要區(qū)別在于：與一般中斷的主要區(qū)別在于： 缺頁中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號，缺

34、頁中斷在指令執(zhí)行期間產(chǎn)生和處理中斷信號，而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信而一般中斷在一條指令執(zhí)行完后檢查和處理中斷信號。號。 缺頁中斷返回到該指令的開始重新執(zhí)行該指令，缺頁中斷返回到該指令的開始重新執(zhí)行該指令，而一般中斷返回到該指令的下一條指令執(zhí)行。而一般中斷返回到該指令的下一條指令執(zhí)行。 一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。4.4.地址變換機構(gòu)地址變換機構(gòu) 請求分頁系統(tǒng)中的地址變換機構(gòu)，是請求分頁系統(tǒng)中的地址變換機構(gòu)，是在分頁系統(tǒng)的地址變換機構(gòu)的基礎(chǔ)上，再在分頁系統(tǒng)的地址變換機構(gòu)的基礎(chǔ)上，再為實現(xiàn)虛擬存儲器而增加了某些功能所形為實現(xiàn)

35、虛擬存儲器而增加了某些功能所形成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)成的，如產(chǎn)生和處理缺頁中斷，以及從內(nèi)存中換出一頁的功能等等。存中換出一頁的功能等等。5.5.頁面置換算法頁面置換算法 最優(yōu)置換算法（最優(yōu)置換算法（OPTOPT算法）算法） 從內(nèi)存中移出以后不再使用的頁面；如無這從內(nèi)存中移出以后不再使用的頁面；如無這樣的頁面，則選擇以后最長時間內(nèi)不需要訪問的樣的頁面，則選擇以后最長時間內(nèi)不需要訪問的頁。這就是最優(yōu)算法的思想。這種算法本身不是頁。這就是最優(yōu)算法的思想。這種算法本身不是一種實際的方法，因為頁面訪問的順序是很難預(yù)一種實際的方法，因為頁面訪問的順序是很難預(yù)知的。知的。 先進先出算法（先進先

36、出算法（FIFOFIFO算法）算法） 總是先淘汰那些駐留在內(nèi)存時間最長的頁面，總是先淘汰那些駐留在內(nèi)存時間最長的頁面，即先進入內(nèi)存的頁面先被置換掉。即先進入內(nèi)存的頁面先被置換掉。 理由是：最先進入內(nèi)存的頁面不再被訪問的理由是：最先進入內(nèi)存的頁面不再被訪問的可能性最大?？赡苄宰畲?。 最近最少使用算法（最近最少使用算法（LRULRU算法）算法） 當(dāng)需要置換一頁時，選擇在最近一段時間當(dāng)需要置換一頁時，選擇在最近一段時間最少使用的頁面予以淘汰。最少使用的頁面予以淘汰。 ClockClock置換算法置換算法 需要硬件支持，實現(xiàn)代價較大。需要硬件支持，實現(xiàn)代價較大。如何評價算法如何評價算法? ?缺頁中斷率

37、缺頁中斷率= =不成功的訪問次數(shù)不成功的訪問次數(shù)/ /訪問總次數(shù)訪問總次數(shù) =缺頁中斷次數(shù)中斷次數(shù)/ /訪問總次數(shù)訪問總次數(shù)OPTOPT算法性能分析（算法性能分析（M=3M=3）時刻時刻 012345678910 11 12頁面頁面走向走向531525423525塊塊1塊塊2塊塊3缺頁缺頁中斷中斷OPTOPT算法性能分析（算法性能分析（M=3M=3）時刻時刻 012345678910 11 12頁面頁面走向走向531525423525塊塊1555555444555塊塊233333333333塊塊31122222222缺頁缺頁中斷中斷缺頁率缺頁率6/12=0.5=50%FIFOFIFO算法性能分

38、析（算法性能分析（m=3m=3）時刻時刻012345678910 11 12頁面頁面走向走向531525423525塊塊1塊塊2塊塊3缺頁缺頁中斷中斷FIFOFIFO算法性能分析（算法性能分析（m=3m=3）缺頁率缺頁率9/12=75%時刻時刻012345678910 11 12頁面頁面走向走向531525423525塊塊1555522223333塊塊233335555522塊塊31111444445缺頁缺頁中斷中斷LRULRU算法性能分析（算法性能分析（M=3M=3）時刻時刻 012345678910 11 12頁面頁面走向走向531525423525塊塊1塊塊2塊塊3缺頁缺頁中斷中斷LRU

39、LRU算法性能分析（算法性能分析（M=3M=3）缺頁率缺頁率7/12=58.3%時刻時刻 012345678910 11 12頁面頁面走向走向531525423525塊塊1555555553333塊塊233322222222塊塊31111444555缺頁缺頁中斷中斷4.4 4.4 段式管理段式管理 引入段式存儲管理方式的原因：引入段式存儲管理方式的原因：1 1、一個作業(yè)是由若干自然段組成，用戶希望能把自、一個作業(yè)是由若干自然段組成，用戶希望能把自己的作業(yè)按照邏輯關(guān)系劃分為若干段，可以通過每己的作業(yè)按照邏輯關(guān)系劃分為若干段，可以通過每段的名字和長度來訪問。段的名字和長度來訪問。2 2、分段共享。

40、程序和數(shù)據(jù)的共享是以信息的邏輯單、分段共享。程序和數(shù)據(jù)的共享是以信息的邏輯單位為基礎(chǔ)的，若段的劃分也與信息的邏輯單位相對位為基礎(chǔ)的，若段的劃分也與信息的邏輯單位相對應(yīng)，則易實現(xiàn)共享。應(yīng)，則易實現(xiàn)共享。3 3、分段保護。在多道程序環(huán)境下，對主存信息的保、分段保護。在多道程序環(huán)境下，對主存信息的保護，同樣也是以信息的邏輯單位為基礎(chǔ)的。護，同樣也是以信息的邏輯單位為基礎(chǔ)的。4 4、動態(tài)鏈接也要求以段作為管理的單位。、動態(tài)鏈接也要求以段作為管理的單位。5 5、動態(tài)增長。、動態(tài)增長。4.4.1 4.4.1 段式管理概述段式管理概述 1 1、用戶程序劃分、用戶程序劃分 按程序自身的邏輯關(guān)系劃分為若干個程序

41、段，按程序自身的邏輯關(guān)系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。每個程序段都有一個段名，且有一個段號。 段號從段號從0 0開始，每一段段內(nèi)也從開始，每一段段內(nèi)也從0 0開始編址，段開始編址，段內(nèi)地址是連續(xù)的。內(nèi)地址是連續(xù)的。3 3、內(nèi)存分配、內(nèi)存分配 以段為單位分配內(nèi)存，每一個段在內(nèi)存以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機分割，需要多少中占據(jù)連續(xù)空間（內(nèi)存隨機分割，需要多少分配多少），但各段之間可以不連續(xù)存放。分配多少），但各段之間可以不連續(xù)存放。段號 段內(nèi)地址2 2、邏輯地址結(jié)構(gòu)：二維、邏輯地址結(jié)構(gòu)：二維4. 4. 段表段表 在段式存儲管理方式中，系統(tǒng)為

42、每個段分配一個在段式存儲管理方式中，系統(tǒng)為每個段分配一個連續(xù)的分區(qū)，而進程中的各個段可以離散放入內(nèi)存中連續(xù)的分區(qū)，而進程中的各個段可以離散放入內(nèi)存中不同的分區(qū)中。不同的分區(qū)中。 像頁式存儲管理方式那樣，在系統(tǒng)中為每個進程像頁式存儲管理方式那樣，在系統(tǒng)中為每個進程建立一個段映射表，稱為建立一個段映射表，稱為“段表段表”。 段表可以存放在一組寄存器中，可以提高轉(zhuǎn)換速段表可以存放在一組寄存器中，可以提高轉(zhuǎn)換速度；也可以將段表放在內(nèi)存中。段表的作用是實現(xiàn)了度；也可以將段表放在內(nèi)存中。段表的作用是實現(xiàn)了從邏輯段到物理內(nèi)存區(qū)的映射。從邏輯段到物理內(nèi)存區(qū)的映射。 4. 4. 段表段表作業(yè)空間(MAIN) 0

43、030K(X) 1020K(D) 2015K(S) 3010K30K20K15K10K40K80K120K150K段長基址段號(MAIN) 030K(X) 120K(D) 215K(S) 310K040K80K120K150K段表內(nèi)存空間01234.4.2 4.4.2 地址轉(zhuǎn)換地址轉(zhuǎn)換4.4.2 4.4.2 地址轉(zhuǎn)換地址轉(zhuǎn)換控制寄存器段表始址段表長度2100段號 S越界1 K段長600段號01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址4.4.4 4.4.4 段的共享段的共享4.4.4 4.4.4 段的共享段的共享editor進程1da

44、ta 1進程2editordata 2段表段長 基址16080402401608040380editordata 1data 2802402803804204.4.5 4.4.5 分段與分頁的區(qū)別分段與分頁的區(qū)別 (1) (1) 頁是信息的物理單位，分頁是為實現(xiàn)離頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率。或者說，分頁僅僅是由于系統(tǒng)管理的需利用率。或者說，分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。要而不是用戶的需要。 段則是信息的邏輯單位，它含有一組其意義段則是信息的邏輯單位，它含有一組其意義相對完整的信息。相對完整的信息。 分段的目的是為了能更好地分段的目的是為了能更好地滿足用戶的滿足用戶的需要。需要。 (2) (2) 頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機器硬輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機器硬件實現(xiàn)的；件實現(xiàn)的； 而段的長度卻不固定，決定于用戶所編寫的程而段的長度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進行編譯時，根據(jù)序，通常由編譯程序在對源程序進行編譯時，根據(jù)信息的性質(zhì)來劃分。信息的性質(zhì)來劃分。(3) (3) 分頁的作業(yè)地址空間是一維的，即單一的線分頁的作業(yè)地址空間是一維的，即