江蘇師范大學(xué)操作系統(tǒng)ppt第4章-1

1、第1/96頁 4.1 內(nèi)存管理功能內(nèi)存管理功能 4.2 分區(qū)管理分區(qū)管理 4.3 頁式管理頁式管理 4.4 段式管理段式管理 4.5 段頁式管理段頁式管理第2/96頁內(nèi)存空間的分配、回收內(nèi)存空間的分配、回收地址重定位地址重定位內(nèi)存空間的共享與保護內(nèi)存空間的共享與保護內(nèi)存空間的邏輯擴充內(nèi)存空間的邏輯擴充 第3/96頁 內(nèi)存分配按分配時機的不同，可分為兩種方式：內(nèi)存分配按分配時機的不同，可分為兩種方式： 靜態(tài)分配靜態(tài)分配 指內(nèi)存分配是在作業(yè)運行之前各目標(biāo)模塊連接后，把整個指內(nèi)存分配是在作業(yè)運行之前各目標(biāo)模塊連接后，把整個作業(yè)一次性全部裝入內(nèi)存，并在作業(yè)的整個運行過程中，不允許作業(yè)一次性全部裝入內(nèi)存

2、，并在作業(yè)的整個運行過程中，不允許作業(yè)再申請其他內(nèi)存，或在內(nèi)存中移動位置。也就是說，內(nèi)存分作業(yè)再申請其他內(nèi)存，或在內(nèi)存中移動位置。也就是說，內(nèi)存分配是在作業(yè)運行前一次性完成的。配是在作業(yè)運行前一次性完成的。 動態(tài)分配動態(tài)分配 作業(yè)要求的基本內(nèi)存空間是在目標(biāo)模塊裝入內(nèi)存時分配的，作業(yè)要求的基本內(nèi)存空間是在目標(biāo)模塊裝入內(nèi)存時分配的，但在作業(yè)運行過程中，允許作業(yè)申請附加的內(nèi)存空間，或是在內(nèi)但在作業(yè)運行過程中，允許作業(yè)申請附加的內(nèi)存空間，或是在內(nèi)存中移動，即分配工作可以在作業(yè)運行前及運行過程中逐步完成。存中移動，即分配工作可以在作業(yè)運行前及運行過程中逐步完成。第4/96頁內(nèi)存的物理地址內(nèi)存的物理地址

3、把內(nèi)存分成若干個大小相等把內(nèi)存分成若干個大小相等的存儲單元，每個單元給一個的存儲單元，每個單元給一個編號，這個編號稱為編號，這個編號稱為內(nèi)存地址內(nèi)存地址（物理地址、絕對地址、實地（物理地址、絕對地址、實地址址），存儲單元占），存儲單元占8位，稱作位，稱作字節(jié)（字節(jié)（byte）。）。物理地址空間物理地址空間 物理地址的集合稱為物理地址物理地址的集合稱為物理地址空間（主存地址空間），它是空間（主存地址空間），它是一個一維的線性空間。一個一維的線性空間。第5/96頁邏輯地址邏輯地址 目標(biāo)程序所用的地址（或稱程序地址目標(biāo)程序所用的地址（或稱程序地址 、虛地址、相對地址、虛地址、相對地址 ），），基本單

4、位可與內(nèi)存的基本單位相同，也可以不相同。它的編址基本單位可與內(nèi)存的基本單位相同，也可以不相同。它的編址總是從總是從0開始的。開始的。邏輯地址空間（程序地址空間、虛地址空間）邏輯地址空間（程序地址空間、虛地址空間） 由邏輯地址組成的集合稱為邏輯地址空間。由邏輯地址組成的集合稱為邏輯地址空間。源源 程程 序序編譯編譯目標(biāo)模塊目標(biāo)模塊庫庫.鏈接鏈接程序程序裝入模塊裝入模塊裝入裝入程序程序內(nèi)存內(nèi)存第6/96頁 將邏輯地址空間中使用的邏輯地址變換成主存中的將邏輯地址空間中使用的邏輯地址變換成主存中的地址的過程稱為地址的過程稱為地址映射或地址變換地址映射或地址變換，有時也稱為，有時也稱為地址重定位地址重定

5、位 。地址映射地址映射Load A 200 3456 1200物理地址空間物理地址空間Load A data1data1 3456源程序源程序Load A 200 34560100200編譯編譯連接連接邏輯地址空間邏輯地址空間BA=1000第7/96頁靜態(tài)重定位靜態(tài)重定位 在程序裝入內(nèi)存時，把程序中的邏輯地址全部轉(zhuǎn)換為絕對地址。在程序裝入內(nèi)存時，把程序中的邏輯地址全部轉(zhuǎn)換為絕對地址。地址轉(zhuǎn)換工作是在程序執(zhí)行前集中一次完成的）在程序執(zhí)行過程中地址轉(zhuǎn)換工作是在程序執(zhí)行前集中一次完成的）在程序執(zhí)行過程中就無須再進行地址轉(zhuǎn)換工作。就無須再進行地址轉(zhuǎn)換工作。映射方法映射方法v假定程序裝入內(nèi)存的首地址為假

6、定程序裝入內(nèi)存的首地址為BRBR，則地址映射按下式進行：，則地址映射按下式進行：物物理地址理地址=BR+=BR+邏輯地址邏輯地址 。v例如，程序裝入內(nèi)存的首地址為例如，程序裝入內(nèi)存的首地址為100100，則裝入程序就按，則裝入程序就按MR=100+VRMR=100+VR對程序中所有地址部分進行修改對程序中所有地址部分進行修改優(yōu)點優(yōu)點 實現(xiàn)簡單，不要硬件的支持。實現(xiàn)簡單，不要硬件的支持。缺點缺點 程序一旦裝入內(nèi)存，就不能移動；程序一旦裝入內(nèi)存，就不能移動； 程序必須占用連續(xù)的內(nèi)存空間。程序必須占用連續(xù)的內(nèi)存空間。0204060Load 1, 402340100140160120Load 1, 1

7、40234重定位裝入程序重定位裝入程序邏輯地址空間邏輯地址空間內(nèi)存空間內(nèi)存空間第8/96頁 動態(tài)重地位動態(tài)重地位是在程序執(zhí)行過程中，在是在程序執(zhí)行過程中，在CPUCPU訪問內(nèi)訪問內(nèi)存之前存之前, ,將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址。將要訪問的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址。 動態(tài)重定位依靠硬件地址變換機構(gòu)完成。動態(tài)重定位依靠硬件地址變換機構(gòu)完成。 Load 1,500Load 1,500Load 1,500Load 1,500物理地址物理地址= =邏輯地址邏輯地址+ +基址基址優(yōu)點優(yōu)點程序占用的內(nèi)存空間是動態(tài)可變的，當(dāng)程序從某個存儲區(qū)移到另程序占用的內(nèi)存空間是動態(tài)可變的，當(dāng)程序從某個存儲區(qū)

8、移到另 一個區(qū)域時，只需要修改相應(yīng)的重定位寄存器一個區(qū)域時，只需要修改相應(yīng)的重定位寄存器BRBR的內(nèi)容即可。的內(nèi)容即可。缺點缺點 需要硬件的支持；實現(xiàn)存儲管理的軟件算法較為復(fù)雜需要硬件的支持；實現(xiàn)存儲管理的軟件算法較為復(fù)雜第9/96頁內(nèi)存共享內(nèi)存共享 指兩個或多個進程共用內(nèi)存中相同的區(qū)域，即它們的內(nèi)指兩個或多個進程共用內(nèi)存中相同的區(qū)域，即它們的內(nèi)存空間有重疊的部分，這樣被共享的程序和數(shù)據(jù)，只需在內(nèi)存空間有重疊的部分，這樣被共享的程序和數(shù)據(jù)，只需在內(nèi)存中保留一個副本。存中保留一個副本。 程序共享程序共享 為了節(jié)省內(nèi)存空間，提高內(nèi)存利用率。為了節(jié)省內(nèi)存空間，提高內(nèi)存利用率。 數(shù)據(jù)共享數(shù)據(jù)共享 為了

9、實現(xiàn)進程間的通信。為了實現(xiàn)進程間的通信。 第10/96頁上、下界存儲保護上、下界存儲保護 系統(tǒng)可為每個進程設(shè)置一對上、下界寄存器，分別用來存系統(tǒng)可為每個進程設(shè)置一對上、下界寄存器，分別用來存放當(dāng)前運行進程在內(nèi)存空間的上、下邊界地址，用它們來限放當(dāng)前運行進程在內(nèi)存空間的上、下邊界地址，用它們來限制用戶程序的活動范圍。制用戶程序的活動范圍。 進程進程第11/96頁 基址限長存儲保護基址限長存儲保護 上、下界保護的一個變種是采用基址上、下界保護的一個變種是采用基址限長存儲保護。限長存儲保護。 進程進程第12/96頁物理存儲器的結(jié)構(gòu)是個一維的線性空間，容量是物理存儲器的結(jié)構(gòu)是個一維的線性空間，容量是有

10、限的。有限的。物理存儲器管理方式的特征：物理存儲器管理方式的特征： 一次性一次性：程序要全部一次性裝入內(nèi)存后才能運行程序要全部一次性裝入內(nèi)存后才能運行 駐留性駐留性：程序裝入內(nèi)存后，一直駐留在內(nèi)存中，程序裝入內(nèi)存后，一直駐留在內(nèi)存中，直至作業(yè)運行結(jié)速。直至作業(yè)運行結(jié)速。用戶程序的大小，可能比內(nèi)存容量小，也可能比用戶程序的大小，可能比內(nèi)存容量小，也可能比內(nèi)存容量大，有時候要大得多。內(nèi)存容量大，有時候要大得多。如何將大于物理內(nèi)存容量的用戶程序裝入運行？如何將大于物理內(nèi)存容量的用戶程序裝入運行？這就是提出研究虛擬存儲器的原因，或稱為虛擬這就是提出研究虛擬存儲器的原因，或稱為虛擬存儲技術(shù)發(fā)展的原動力。

11、存儲技術(shù)發(fā)展的原動力。第13/96頁 指程序在執(zhí)行過程中的一個較短時間內(nèi)，所執(zhí)行指程序在執(zhí)行過程中的一個較短時間內(nèi)，所執(zhí)行的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)的指令地址或操作數(shù)地址分別局限于一定的存儲區(qū)域中。又可細(xì)分時間局部性和空間局部性。域中。又可細(xì)分時間局部性和空間局部性。時間局部性時間局部性 一條指令被執(zhí)行了，則在不久的將來它可能再被一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行。執(zhí)行?？臻g局部性空間局部性 若某一存儲單元被使用，則在一定時間內(nèi)，與該若某一存儲單元被使用，則在一定時間內(nèi)，與該存儲單元相鄰的單元可能被使用。存儲單元相鄰的單元可能被使用。第14/96頁虛擬存儲器虛擬存

12、儲器 是采用是采用請求調(diào)入功能和置換功能請求調(diào)入功能和置換功能，把內(nèi)存與外存把內(nèi)存與外存有機的結(jié)合起來使用，從邏輯上有機的結(jié)合起來使用，從邏輯上為用戶提供一個比為用戶提供一個比物理主存容量大得多的，可尋址的一種物理主存容量大得多的，可尋址的一種“主存儲主存儲器器” ” ，這就是虛存。，這就是虛存。虛擬存儲器的容量虛擬存儲器的容量 是有限的；是有限的； 由內(nèi)存容量和外存容量之和所決定，受計算機的由內(nèi)存容量和外存容量之和所決定，受計算機的地址結(jié)構(gòu)限制。地址結(jié)構(gòu)限制。 以以CPU時間和外存空間換取昂貴內(nèi)存空間，這時間和外存空間換取昂貴內(nèi)存空間，這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)。

13、第15/96頁常規(guī)存儲器的特征常規(guī)存儲器的特征v一次性一次性v駐留性駐留性虛擬存儲器特征虛擬存儲器特征v多次性多次性v對換性對換性v虛擬性虛擬性第16/96頁實現(xiàn)虛擬存儲器必須解決好以下有關(guān)問題實現(xiàn)虛擬存儲器必須解決好以下有關(guān)問題v主存輔存統(tǒng)一管理問題主存輔存統(tǒng)一管理問題v邏輯地址到物理地址的轉(zhuǎn)換問題邏輯地址到物理地址的轉(zhuǎn)換問題v部分裝入和部分對換問題部分裝入和部分對換問題虛擬存儲管理主要采用以下技術(shù)實現(xiàn)虛擬存儲管理主要采用以下技術(shù)實現(xiàn)v頁式虛存管理頁式虛存管理v段式虛存管理段式虛存管理v段頁式虛存管理段頁式虛存管理第17/96頁 連續(xù)分配方式連續(xù)分配方式 a. 單一連續(xù)分配方式單一連續(xù)分配方

14、式(單分區(qū)管理單分區(qū)管理)； b. 分區(qū)管理方式：又分固定分區(qū)方式和可變分區(qū)方式。分區(qū)管理方式：又分固定分區(qū)方式和可變分區(qū)方式。 離散分配方式離散分配方式 a. 分頁存儲管理方式；分頁存儲管理方式； b. 分段存儲管理方式；分段存儲管理方式； c. 段頁式存儲管理方式。段頁式存儲管理方式。 虛擬存儲管理方式虛擬存儲管理方式 a. 請求分頁管理方式請求分頁管理方式 ； b. 請求分段管理方式；請求分段管理方式； c. 請求段頁式管理方式。請求段頁式管理方式。第18/96頁4.2.1 單分區(qū)管理單分區(qū)管理4.2.2 固定分區(qū)固定分區(qū)4.2.3 可變分區(qū)可變分區(qū)4.2.4 碎片問題碎片問題4.2.5

15、 覆蓋與交換覆蓋與交換 第19/96頁 單用戶單任務(wù)系統(tǒng)在一段時間內(nèi)，只有一個進程在內(nèi)單用戶單任務(wù)系統(tǒng)在一段時間內(nèi)，只有一個進程在內(nèi)存，故內(nèi)存分配管理十分簡單，內(nèi)存利用率低。內(nèi)存分存，故內(nèi)存分配管理十分簡單，內(nèi)存利用率低。內(nèi)存分為兩個區(qū)域，一個供操作系統(tǒng)使用，一個供用戶使用。為兩個區(qū)域，一個供操作系統(tǒng)使用，一個供用戶使用。v靜態(tài)重定位靜態(tài)重定位 v界限寄存器界限寄存器v重定位和存儲保護重定位和存儲保護操作系統(tǒng)區(qū)操作系統(tǒng)區(qū)作業(yè)作業(yè)i i的的程序、程序、數(shù)據(jù)等數(shù)據(jù)等界限地址界限地址界限寄存器界限寄存器作業(yè)作業(yè)2 2作業(yè)作業(yè)1 1界限地址界限地址 + + 邏輯地址邏輯地址裝入程序裝入程序第20/96

16、頁 基本思想基本思想 預(yù)先把可分配的主存儲器空間分割成若干個固預(yù)先把可分配的主存儲器空間分割成若干個固定大小的連續(xù)存儲區(qū)（存儲塊），稱為一個定大小的連續(xù)存儲區(qū)（存儲塊），稱為一個分區(qū)分區(qū)。每個分區(qū)的大小可以相同也可以不同。但分區(qū)大小每個分區(qū)的大小可以相同也可以不同。但分區(qū)大小固定不變，每個分區(qū)裝一個且只能裝一個作業(yè)。固定不變，每個分區(qū)裝一個且只能裝一個作業(yè)。 在系統(tǒng)運行期間，分區(qū)大小、數(shù)目都不變，所以在系統(tǒng)運行期間，分區(qū)大小、數(shù)目都不變，所以固定分區(qū)也稱為固定分區(qū)也稱為靜態(tài)分區(qū)靜態(tài)分區(qū)。第21/96頁OSOS區(qū)（區(qū)（20KB20KB）分區(qū)分區(qū)1 1（50KB50KB）分區(qū)分區(qū)2 2 （50KB

17、50KB）分區(qū)分區(qū)3 3 （50KB50KB）分區(qū)分區(qū)4 4 （50KB50KB）分區(qū)大小相等分區(qū)大小相等OSOS區(qū)（區(qū)（20KB20KB）分區(qū)分區(qū)1 1（10KB10KB）分區(qū)分區(qū)2 2 （30KB30KB）分區(qū)分區(qū)3 3 （50KB50KB）分區(qū)分區(qū)4 4 （110KB110KB）分區(qū)大小不相等分區(qū)大小不相等根據(jù)分區(qū)大小是否相等根據(jù)分區(qū)大小是否相等, ,可采用兩種方法劃分分區(qū)可采用兩種方法劃分分區(qū)第22/96頁124K256KOS20K28K60K 進程進程A（6K）進程進程B（25K）進程進程C（7K） 內(nèi)存的分配與回收，需要借助于內(nèi)存的分配與回收，需要借助于內(nèi)存分配表內(nèi)存分配表數(shù)據(jù)數(shù)據(jù)

18、結(jié)構(gòu)來實現(xiàn)，該數(shù)據(jù)結(jié)構(gòu)用于記錄各分區(qū)的分配和使結(jié)構(gòu)來實現(xiàn)，該數(shù)據(jù)結(jié)構(gòu)用于記錄各分區(qū)的分配和使用情況。用情況。內(nèi)存分配表內(nèi)存分配表區(qū)號區(qū)號分區(qū)長度分區(qū)長度起始地址起始地址狀態(tài)狀態(tài)1 18K8K20K20K空閑空閑2 232K32K28K28K空閑空閑3 364K64K60K60K空閑空閑4 4132K132K124K124K空閑空閑區(qū)號區(qū)號分區(qū)長度分區(qū)長度起始地址起始地址狀態(tài)狀態(tài)1 18K8K20K20K已分配已分配2 232K32K28K28K空閑空閑3 364K64K60K60K空閑空閑4 4132K132K124K124K空閑空閑區(qū)號區(qū)號分區(qū)長度分區(qū)長度起始地址起始地址狀態(tài)狀態(tài)1 18K8

19、K20K20K已分配已分配2 232K32K28K28K已分配已分配3 364K64K60K60K空閑空閑4 4132K132K124K124K空閑空閑區(qū)號區(qū)號分區(qū)長度分區(qū)長度起始地址起始地址狀態(tài)狀態(tài)1 18K8K20K20K已分配已分配2 232K32K28K28K已分配已分配3 364K64K60K60K已分配已分配4 4132K132K124K124K空閑空閑第23/96頁優(yōu)點優(yōu)點 能使多個程序并發(fā)執(zhí)行能使多個程序并發(fā)執(zhí)行 改善了單分區(qū)管理中內(nèi)存利用率低的問題改善了單分區(qū)管理中內(nèi)存利用率低的問題缺點缺點 不能充分利用內(nèi)存空間，會形成內(nèi)碎片不能充分利用內(nèi)存空間，會形成內(nèi)碎片 限制了并發(fā)執(zhí)行

20、的進程數(shù)目限制了并發(fā)執(zhí)行的進程數(shù)目 限制了裝入程序的大小限制了裝入程序的大小第24/96頁 基本思想基本思想 內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時，根據(jù)作內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。若有業(yè)的需求和內(nèi)存空間的使用情況來決定是否分配。若有足夠的空間，則按足夠的空間，則按需要分割需要分割一部分分區(qū)給該進程；否則一部分分區(qū)給該進程；否則令其等待主存空間。令其等待主存空間。OS進程進程A進程進程 A（8K）進程進程 C（64K）OS進程進程A進程進程B進程進程C進程進程 D（124K）OS進程進程A進程進程B進程進程C進程進程D進程進程 B

21、（16K）OS進程進程A進程進程B第25/96頁OSA（8K）24K空閑區(qū)空閑區(qū)B（16K）C (64K）D（124K）OSA（8K）8K空閑區(qū)空閑區(qū)B（16K）E（50K）D（124K）14K空閑區(qū)空閑區(qū)F（16K）OSA（8K）8K空閑區(qū)空閑區(qū)空閑區(qū)空閑區(qū)16KE（50K）F（16K）空閑合并空閑合并124+14=138K進程進程E（50K）進程進程F（16K）進入內(nèi)存進入內(nèi)存進程進程B（16K）進程進程D（124K）完成完成C完成（完成（64K）空閑區(qū)空閑區(qū)內(nèi)存分配變化過程內(nèi)存分配變化過程:第26/96頁空閑分區(qū)表空閑分區(qū)表空閑分區(qū)鏈空閑分區(qū)鏈5 735 73若須分配若須分配25K25K

22、第27/96頁首次適應(yīng)算法首次適應(yīng)算法循環(huán)首次適應(yīng)算法循環(huán)首次適應(yīng)算法最佳適應(yīng)算法最佳適應(yīng)算法最壞適應(yīng)算法最壞適應(yīng)算法第28/96頁 基本思想：基本思想：空閑區(qū)按地址大小遞增順序排列，在分配時，空閑區(qū)按地址大小遞增順序排列，在分配時，從頭開始順序查找到第一個大小能滿足要求的空閑區(qū)。從頭開始順序查找到第一個大小能滿足要求的空閑區(qū)。 特點：特點：簡單簡單第29/96頁優(yōu)點優(yōu)點v盡可能地利用低地址空間，從而保證高地址空間盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區(qū)。有較大的空閑區(qū)。缺點缺點v低地址部分不斷劃分，形成很多難以利用的小塊低地址部分不斷劃分，形成很多難以利用的小塊v每次從頭開始

23、找，增加了查找的時間每次從頭開始找，增加了查找的時間第30/96頁基本思想基本思想 每次分配時每次分配時,從上一次找到的空閑分區(qū)的下一個開始查從上一次找到的空閑分區(qū)的下一個開始查找找,找到第一個大小滿足要求的空閑分區(qū)為止找到第一個大小滿足要求的空閑分區(qū)為止.優(yōu)點優(yōu)點 小的空閑分區(qū)均勻分布小的空閑分區(qū)均勻分布 減少了查找時間減少了查找時間缺點缺點 不能保留大的空閑區(qū)不能保留大的空閑區(qū)第31/96頁 基本思想基本思想：空閑區(qū)按空閑區(qū)大小升序方法組織。分：空閑區(qū)按空閑區(qū)大小升序方法組織。分配時，按申請的大小逐個與空閑區(qū)大小進行比較，找到配時，按申請的大小逐個與空閑區(qū)大小進行比較，找到一個滿足要求的空

24、閑區(qū)，就分配給它。一個滿足要求的空閑區(qū)，就分配給它。所謂最佳即選中所謂最佳即選中的空閑區(qū)是滿足要求的最小空閑區(qū)。的空閑區(qū)是滿足要求的最小空閑區(qū)。 特點：特點： 用最小空間滿足要求用最小空間滿足要求第32/96頁優(yōu)點優(yōu)點v在系統(tǒng)中若存在一個與申請分區(qū)大小相等的空閑在系統(tǒng)中若存在一個與申請分區(qū)大小相等的空閑區(qū)，必定會被選中，而首次適應(yīng)法則不一定。區(qū)，必定會被選中，而首次適應(yīng)法則不一定。v若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑區(qū)，若系統(tǒng)中不存在與申請分區(qū)大小相等的空閑區(qū)，則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不則選中的空閑區(qū)是滿足要求的最小空閑區(qū)，而不致于毀掉較大的空閑區(qū)。致于毀掉較大的空閑區(qū)。缺

25、點缺點v分割后的空閑區(qū)將會很小，直至無法使用，而造分割后的空閑區(qū)將會很小，直至無法使用，而造成浪費。成浪費。v分配和回收后要對空閑區(qū)表（隊列）重新排序。分配和回收后要對空閑區(qū)表（隊列）重新排序。第33/96頁 基本思想：基本思想：與最佳適應(yīng)算法相反，空閑區(qū)按容量遞減與最佳適應(yīng)算法相反，空閑區(qū)按容量遞減順序排列。當(dāng)接到內(nèi)存申請時，如第一順序排列。當(dāng)接到內(nèi)存申請時，如第一 個空區(qū)滿足要求個空區(qū)滿足要求就進行分配，就進行分配，修改空閑區(qū)的大小，并將它插入到空閑區(qū)修改空閑區(qū)的大小，并將它插入到空閑區(qū)表的適當(dāng)位置；表的適當(dāng)位置；否則分配失敗。否則分配失敗。 特點：特點：當(dāng)分配后剩下的空區(qū)仍可為較大空區(qū)當(dāng)

26、分配后剩下的空區(qū)仍可為較大空區(qū)第34/96頁 優(yōu)點優(yōu)點v當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑區(qū)當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑區(qū)還可能相當(dāng)大，還能裝下較大的程序。還可能相當(dāng)大，還能裝下較大的程序。v另一方面每次僅作一次查詢工作另一方面每次僅作一次查詢工作第35/96頁 某時刻系統(tǒng)中有三個空閑區(qū)，大小和首址為：某時刻系統(tǒng)中有三個空閑區(qū)，大小和首址為： (35KB(35KB，100KB)100KB)、(12KB(12KB，156KB)156KB)、(28KB(28KB，200KB)200KB) 有一作業(yè)系列：有一作業(yè)系列： (JOB1(JOB1，12KB)12KB)、(JOB2(J

27、OB2，30KB)30KB)、(JOB3(JOB3，28KB)28KB)第36/96頁作業(yè)序列：作業(yè)作業(yè)序列：作業(yè)A A要求要求21K21K；作業(yè)；作業(yè)B B要求要求30K30K，作業(yè)，作業(yè)C C要求要求25K25K。第37/96頁 當(dāng)某個進程釋放某存儲區(qū)時，系統(tǒng)首先檢查釋放當(dāng)某個進程釋放某存儲區(qū)時，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個空閑并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個空閑區(qū)插入到空閑區(qū)表的適當(dāng)位置。區(qū)插入到空閑區(qū)表的適當(dāng)位置。 A X B A B A X A X B

28、B x 變?yōu)樽優(yōu)樽優(yōu)樽優(yōu)樽優(yōu)樽優(yōu)樽優(yōu)樽優(yōu)閄終止前終止前X終止后終止后第38/96頁釋放區(qū)不與任何空閑區(qū)相鄰釋放區(qū)不與任何空閑區(qū)相鄰 將釋放區(qū)作為一個空閑區(qū)，將其大小和首址插入到空閑區(qū)鏈的適當(dāng)將釋放區(qū)作為一個空閑區(qū)，將其大小和首址插入到空閑區(qū)鏈的適當(dāng)位置。位置。釋放區(qū)與后空閑區(qū)相鄰釋放區(qū)與后空閑區(qū)相鄰 則把釋放區(qū)合并到后空閑，首地址為釋放區(qū)首地址，大小為二者大則把釋放區(qū)合并到后空閑，首地址為釋放區(qū)首地址，大小為二者大小之和。小之和。釋放區(qū)與前空閑區(qū)相鄰釋放區(qū)與前空閑區(qū)相鄰 將釋放區(qū)與前空閑區(qū)合并為一個空閑區(qū)。其首址仍為前空閑區(qū)首址，將釋放區(qū)與前空閑區(qū)合并為一個空閑區(qū)。其首址仍為前空閑區(qū)首址，大小

29、為釋放區(qū)大小與空閑區(qū)大小之和。大小為釋放區(qū)大小與空閑區(qū)大小之和。釋放區(qū)與前后兩個空閑區(qū)相鄰釋放區(qū)與前后兩個空閑區(qū)相鄰 將這三個區(qū)合為一個空閑區(qū)，其首址為前空閑區(qū)首址，大小為這三將這三個區(qū)合為一個空閑區(qū)，其首址為前空閑區(qū)首址，大小為這三個區(qū)大小之和，并取消原后空閑區(qū)結(jié)點。個區(qū)大小之和，并取消原后空閑區(qū)結(jié)點。第39/96頁碎片（零頭）碎片（零頭）v經(jīng)過一段時間的分配回收后，內(nèi)存中存在很多很小的經(jīng)過一段時間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求，空閑塊。它們每一個都很小，不足以滿足分配要求，這些空閑塊被稱為這些空閑塊被稱為碎片碎片。但它們的總和可以滿足作業(yè)。但

30、它們的總和可以滿足作業(yè)的要求。的要求。v碎片的出現(xiàn)造成了存儲空間的浪費。碎片的出現(xiàn)造成了存儲空間的浪費。解決碎片的方法解決碎片的方法v移動技術(shù)（緊湊技術(shù)、動態(tài)地址重定位）移動技術(shù)（緊湊技術(shù)、動態(tài)地址重定位）例例第40/96頁移動技術(shù)移動技術(shù)v若需裝入若需裝入95K的程序的程序v通過在內(nèi)存移動程序，將所通過在內(nèi)存移動程序，將所有小的空閑區(qū)域合并為大的有小的空閑區(qū)域合并為大的空閑區(qū)域?？臻e區(qū)域。但這種方法的系但這種方法的系統(tǒng)開銷太大。統(tǒng)開銷太大。 問題問題v移動條件和移動時機移動條件和移動時機 操作系統(tǒng)操作系統(tǒng)進程進程1 1空閑區(qū)空閑區(qū)60K60K進程進程2 2空閑區(qū)空閑區(qū)30K30K進程進程3

31、3空閑區(qū)空閑區(qū)26K26K操作系統(tǒng)操作系統(tǒng)進程進程1 1進程進程2 2進程進程3 3空閑區(qū)空閑區(qū)116K116K操作系統(tǒng)操作系統(tǒng)進程進程1 1進程進程2 2進程進程3 3空閑區(qū)空閑區(qū)25K25K進程進程4 495K95K第41/96頁引入引入 分區(qū)存儲管理的主要問題是分區(qū)存儲管理的主要問題是碎片問題碎片問題。動態(tài)重定位。動態(tài)重定位是解決存儲器碎片問題的一種途徑，但要移動大量是解決存儲器碎片問題的一種途徑，但要移動大量信息花去不少處理機時間信息花去不少處理機時間, ,代價比較高。這是因為這代價比較高。這是因為這種分配要求把作業(yè)必須安置在一連續(xù)存儲區(qū)內(nèi)的緣種分配要求把作業(yè)必須安置在一連續(xù)存儲區(qū)內(nèi)的

32、緣故故, ,而分頁存儲管理正是要避開這種連續(xù)性要求。而分頁存儲管理正是要避開這種連續(xù)性要求。離散分配方式離散分配方式v分頁存儲管理方式分頁存儲管理方式v分段存儲管理方式分段存儲管理方式v段頁式存儲管理方式段頁式存儲管理方式 第42/96頁頁面頁面 把一個進程的邏輯地址空間劃分成若干個大小相等的片，稱為把一個進程的邏輯地址空間劃分成若干個大小相等的片，稱為頁頁（pagepage）或頁面）或頁面 。從。從0 0開始編制開始編制頁號頁號，頁內(nèi)地址是相對于，頁內(nèi)地址是相對于0 0編址。編址。塊塊 內(nèi)存空間按頁的大小劃分為大小相等的區(qū)域，稱為內(nèi)存空間按頁的大小劃分為大小相等的區(qū)域，稱為頁框或內(nèi)存頁框或內(nèi)

33、存塊或物理塊塊或物理塊。從。從0 0開始編制開始編制塊號塊號，塊內(nèi)地址是相對于，塊內(nèi)地址是相對于0 0編址。編址。 頁大小頁大小= =塊大小塊大小 例例頁內(nèi)碎片頁內(nèi)碎片 有時由于進程的最后一頁裝不滿一塊，就形成了不可利用的碎有時由于進程的最后一頁裝不滿一塊，就形成了不可利用的碎片，稱為片，稱為頁內(nèi)碎片頁內(nèi)碎片。頁面大小頁面大小 在劃分頁面時，其大小要適中。在劃分頁面時，其大小要適中。太?。嚎梢詼p少內(nèi)存碎片，提高利用率，但占用頁面較多，頁表太?。嚎梢詼p少內(nèi)存碎片，提高利用率，但占用頁面較多，頁表過長，占用大量內(nèi)存空間。過長，占用大量內(nèi)存空間。太大：可以減少頁表長度，但增大頁內(nèi)碎片。太大：可以減少

34、頁表長度，但增大頁內(nèi)碎片。 一般頁面大小為一般頁面大小為512B8KB，應(yīng)是，應(yīng)是2m第43/96頁用戶進程空間用戶進程空間頁大小頁大小=1K=1K0頁頁1頁頁2頁頁0B0B1024B1024B2048B2048B3000B3000BOS0塊塊1塊塊2塊塊3塊塊N塊塊內(nèi)存空間內(nèi)存空間第44/96頁邏輯地址邏輯地址 地址結(jié)構(gòu)：地址結(jié)構(gòu)： 用戶程序的劃分是由系統(tǒng)自動完成的，對用戶是用戶程序的劃分是由系統(tǒng)自動完成的，對用戶是透明的。透明的。 地址的高位部分為頁號，低位部分為頁內(nèi)地址。地址的高位部分為頁號，低位部分為頁內(nèi)地址。頁號頁號 頁內(nèi)地址頁內(nèi)地址0111223頁號頁號P頁內(nèi)位移量頁內(nèi)位移量W編號

35、編號04095B相對地址相對地址04095B第45/96頁邏輯地址以十進制數(shù)給出邏輯地址以十進制數(shù)給出 a.a.頁號邏輯地址頁大小頁號邏輯地址頁大小 b.b.頁內(nèi)地址邏輯地址頁內(nèi)地址邏輯地址 mod mod 頁大小頁大小例例 頁面大小是頁面大小是1KB，邏輯地址是，邏輯地址是12574B 頁號頁號P=12，頁內(nèi)地址，頁內(nèi)地址W=286例例 頁面大小是頁面大小是2KB，邏輯地址是，邏輯地址是12574B 頁號頁號P=6，頁內(nèi)地址，頁內(nèi)地址W=286第46/96頁邏輯地址（程序地址）以十六進制的形式給出邏輯地址（程序地址）以十六進制的形式給出 a.a.將邏輯地址轉(zhuǎn)換成二進制的數(shù)；將邏輯地址轉(zhuǎn)換成二

36、進制的數(shù)； b.b.按頁的大小分離出頁號和頁內(nèi)地址（低位部分是頁內(nèi)地址，高位按頁的大小分離出頁號和頁內(nèi)地址（低位部分是頁內(nèi)地址，高位部分是頁號）；部分是頁號）；第47/96頁內(nèi)存分配思想內(nèi)存分配思想 要求程序全部裝入內(nèi)存后，才能開始運行。系統(tǒng)以要求程序全部裝入內(nèi)存后，才能開始運行。系統(tǒng)以塊塊為單位進為單位進行分配，并按作業(yè)的頁數(shù)多少來分配。邏輯上相鄰的頁，物理行分配，并按作業(yè)的頁數(shù)多少來分配。邏輯上相鄰的頁，物理上不一定相鄰。上不一定相鄰。第48/96頁頁表頁表 靜態(tài)頁式存儲管理的數(shù)據(jù)結(jié)構(gòu)，指出頁面與內(nèi)存塊的靜態(tài)頁式存儲管理的數(shù)據(jù)結(jié)構(gòu)，指出頁面與內(nèi)存塊的對應(yīng)關(guān)系。其作用是實現(xiàn)從頁號到物理塊號的

37、地址映對應(yīng)關(guān)系。其作用是實現(xiàn)從頁號到物理塊號的地址映射。射。頁表結(jié)構(gòu)頁表結(jié)構(gòu)v頁號：登記程序地址空間的頁號。頁號：登記程序地址空間的頁號。v塊號：登記相應(yīng)的頁所對應(yīng)的內(nèi)存塊號。塊號：登記相應(yīng)的頁所對應(yīng)的內(nèi)存塊號。系統(tǒng)為系統(tǒng)為每個進程建立一個頁表每個進程建立一個頁表，頁表的長度和首地址，頁表的長度和首地址存放在該進程的進程控制塊（存放在該進程的進程控制塊（PCBPCB）中。）中。頁表必須駐留在內(nèi)存。頁表必須駐留在內(nèi)存。第49/96頁作業(yè)名BA頁表始址XXXXXX頁表長度XXXX第50/96頁 在靜態(tài)頁式管理中在靜態(tài)頁式管理中, ,內(nèi)存的分配以內(nèi)存的分配以塊塊為單為單位位, ,應(yīng)設(shè)置一個數(shù)據(jù)結(jié)構(gòu)來

38、記錄內(nèi)存中塊的使應(yīng)設(shè)置一個數(shù)據(jù)結(jié)構(gòu)來記錄內(nèi)存中塊的使用情況用情況, ,以便實現(xiàn)內(nèi)存的分配和回收以便實現(xiàn)內(nèi)存的分配和回收. .位示圖位示圖空閑塊鏈空閑塊鏈內(nèi)存分塊表內(nèi)存分塊表第51/96頁 位示圖由內(nèi)存中的若干個字節(jié)組成，位示圖中的每一位示圖由內(nèi)存中的若干個字節(jié)組成，位示圖中的每一位對應(yīng)內(nèi)存中的一個塊。位對應(yīng)內(nèi)存中的一個塊。 0 0表示空閑表示空閑 1 1表示已分配表示已分配例如：內(nèi)存空間劃分為例如：內(nèi)存空間劃分為128128塊，則位示圖應(yīng)由塊，則位示圖應(yīng)由1616個字節(jié)組成個字節(jié)組成第52/96頁 順序掃描位示圖，從中找出一個或一組其值為順序掃描位示圖，從中找出一個或一組其值為“0”的二的二

39、進制位進制位(“0”表示空閑時表示空閑時)。 將所找到的一個或一組二進制位，將所找到的一個或一組二進制位， 轉(zhuǎn)換成與之相應(yīng)的轉(zhuǎn)換成與之相應(yīng)的 塊號。假定找到的其值為塊號。假定找到的其值為“0”的二進制位，位于位示圖的二進制位，位于位示圖 的第的第i行、第行、第j列，則其相應(yīng)的塊號應(yīng)按下式計算：列，則其相應(yīng)的塊號應(yīng)按下式計算： b=n(i-1)+j-1 式中，式中， n代表每行的位數(shù)。代表每行的位數(shù)。 修改位示圖，修改位示圖， 令令mapi,j=1。 第53/96頁 將回收塊的塊號轉(zhuǎn)換成位示圖中的行號和列號。將回收塊的塊號轉(zhuǎn)換成位示圖中的行號和列號。 轉(zhuǎn)換公轉(zhuǎn)換公式為：式為： i=b DIV n

40、+1 j=b MOD n+1 修改位示圖。修改位示圖。 令令map i,j=0。 第54/96頁將所有將所有空閑塊空閑塊鏈接成一個空閑塊鏈。鏈接成一個空閑塊鏈。分配時，從鏈?zhǔn)滓来畏峙淙舾蓚€空閑塊。分配時，從鏈?zhǔn)滓来畏峙淙舾蓚€空閑塊?；厥諘r，將空閑塊插入鏈尾?；厥諘r，將空閑塊插入鏈尾。 第55/96頁 用于記錄內(nèi)存中用于記錄內(nèi)存中所有塊所有塊的使用情況，包含塊號、進程的使用情況，包含塊號、進程號、頁號和狀態(tài)等信息。號、頁號和狀態(tài)等信息。 狀態(tài)為狀態(tài)為0 0表示空閑表示空閑 狀態(tài)為狀態(tài)為1 1表示已分配表示已分配 第56/96頁頁表頁表頁表寄存器頁表寄存器物理地址物理地址頁表始址頁表始址 頁表長度

41、頁表長度進程名進程名A A頁表始址頁表始址xxxxxxxxxxxx頁表長度頁表長度5050PCBPCB塊號塊號比較比較頁號頁號 頁內(nèi)地址頁內(nèi)地址塊號塊號 塊內(nèi)地址塊內(nèi)地址邏輯地址邏輯地址地址越界地址越界第57/96頁判斷頁號是否越界判斷頁號是否越界CPU給出邏輯地址給出邏輯地址由分頁地址機構(gòu)把它分為兩部分：頁號和頁內(nèi)由分頁地址機構(gòu)把它分為兩部分：頁號和頁內(nèi)地址地址根據(jù)頁表始址，以頁號為索引，找到頁所對應(yīng)根據(jù)頁表始址，以頁號為索引，找到頁所對應(yīng)的塊號的塊號將塊號與頁內(nèi)地址拼接在一起，形成了訪問主將塊號與頁內(nèi)地址拼接在一起，形成了訪問主存的物理地址。存的物理地址。 第58/96頁問題的提出問題的提

42、出 在前述的頁地址變換過程中有一個嚴(yán)重的問題，那就在前述的頁地址變換過程中有一個嚴(yán)重的問題，那就是每一次對內(nèi)存的訪問都要訪問頁表，頁表是放在內(nèi)存中是每一次對內(nèi)存的訪問都要訪問頁表，頁表是放在內(nèi)存中的，也就是說每一次訪問內(nèi)存的指令至少要的，也就是說每一次訪問內(nèi)存的指令至少要訪問兩次內(nèi)存訪問兩次內(nèi)存，運行速度要下降一半。運行速度要下降一半。問題的解決問題的解決 一種方法是把頁表中最近常用的部分表目放在一組一種方法是把頁表中最近常用的部分表目放在一組高高速存儲器速存儲器中（中（Cache），從而加快訪問內(nèi)存的速度。我們），從而加快訪問內(nèi)存的速度。我們把這種高速存儲器組成的頁表稱為把這種高速存儲器組成

43、的頁表稱為快表快表（也稱為聯(lián)想寄存（也稱為聯(lián)想寄存器），把存放在內(nèi)存中的頁表稱為器），把存放在內(nèi)存中的頁表稱為慢表慢表?？毂硎琼摫恚恚┑囊粋€子集快表是頁表（慢表）的一個子集第59/96頁pp頁表頁表地址越界地址越界比較比較P=1P=1p ppp. . . .快表快表+頁號頁號P P 頁內(nèi)地址頁內(nèi)地址d dPPd d物理地址物理地址頁表寄存器頁表寄存器邏輯地址（有效地址寄存器）邏輯地址（有效地址寄存器）P Pb b頁表始址頁表始址b b頁表長度頁表長度l l第60/96頁當(dāng)調(diào)度程序調(diào)度到某個進程時，要從該進程的當(dāng)調(diào)度程序調(diào)度到某個進程時，要從該進程的PCBPCB中把該進程的頁表始中把該進程的

44、頁表始址和頁表長度放入址和頁表長度放入頁表寄存器頁表寄存器。當(dāng)進程要訪問某個邏輯地址中的數(shù)據(jù)時，分頁地址機構(gòu)自動將邏輯地當(dāng)進程要訪問某個邏輯地址中的數(shù)據(jù)時，分頁地址機構(gòu)自動將邏輯地址分為頁號和頁內(nèi)地址兩部分，放入址分為頁號和頁內(nèi)地址兩部分，放入有效地址寄存器有效地址寄存器。用頁號與頁表長度進行比較，當(dāng)頁號用頁號與頁表長度進行比較，當(dāng)頁號 頁表長度，則表示該地址已超出頁表長度，則表示該地址已超出進程的地址空間，產(chǎn)生越界中斷錯誤。進程的地址空間，產(chǎn)生越界中斷錯誤。否則，查找快表，若能找到與該頁號匹配的頁表項，直接從快表中獲否則，查找快表，若能找到與該頁號匹配的頁表項，直接從快表中獲得該頁對應(yīng)的物理

45、塊號，送入物理寄存器。得該頁對應(yīng)的物理塊號，送入物理寄存器。若在快表中找不到對應(yīng)的頁表項，再訪問內(nèi)存中的頁表，得到該頁的若在快表中找不到對應(yīng)的頁表項，再訪問內(nèi)存中的頁表，得到該頁的物理塊號。同時把該頁表項存入快表的一個寄存器單元中，若快表已物理塊號。同時把該頁表項存入快表的一個寄存器單元中，若快表已滿，從中找一個不再需要的頁表項換出。滿，從中找一個不再需要的頁表項換出。第61/96頁需要說明的是，快表的地址轉(zhuǎn)換是非常快的，需要說明的是，快表的地址轉(zhuǎn)換是非?？斓?，因為它是將頁號與快表中的因為它是將頁號與快表中的各行同時比較各行同時比較，從而大大減少了地址變換時間，基本上克服從而大大減少了地址變換

46、時間，基本上克服了兩次訪問主存的缺點。了兩次訪問主存的缺點。但由于快表成本很高，不能做得很大，通常但由于快表成本很高，不能做得很大，通常只存放只存放16512個頁表項。個頁表項。第62/96頁 1. 數(shù)據(jù)共享數(shù)據(jù)共享 2. 程序共享程序共享 第63/96頁 多級頁表的引入多級頁表的引入 頁表存儲開銷太大：頁表存儲開銷太大： CPUCPU具有具有3232位地址時位地址時 , ,使用使用2 23232邏輯地址空間的分頁系統(tǒng)邏輯地址空間的分頁系統(tǒng), ,規(guī)定頁面規(guī)定頁面4KB4KB時時, ,每個進每個進程頁表的表項有程頁表的表項有1 1兆兆(2(22020) )個個, ,若表項占用若表項占用4 4個字

47、節(jié)個字節(jié), ,則每則每個進程需要占用個進程需要占用4MB4MB連續(xù)內(nèi)存空間存放頁表。連續(xù)內(nèi)存空間存放頁表。 兩級頁表兩級頁表 當(dāng)頁表項很多時，僅采用一級頁表需要大片連續(xù)空當(dāng)頁表項很多時，僅采用一級頁表需要大片連續(xù)空間，可將頁表也分頁，并對頁表建立一張外層頁表，間，可將頁表也分頁，并對頁表建立一張外層頁表，由此構(gòu)成由此構(gòu)成二級頁表二級頁表。 多級頁表多級頁表 更進一步可形成更進一步可形成多級頁表多級頁表。第64/96頁多級頁表概念多級頁表概念 頁表和頁面一樣也進行分頁，內(nèi)存僅存放當(dāng)前使用的頁表頁表和頁面一樣也進行分頁，內(nèi)存僅存放當(dāng)前使用的頁表, ,暫時暫時不用部分放在磁盤上不用部分放在磁盤上,

48、,待用到時再行調(diào)進。待用到時再行調(diào)進。具體做法具體做法 把整個頁表進行分頁把整個頁表進行分頁, ,分成一張張小頁表分成一張張小頁表( (稱為稱為頁表頁面頁表頁面) ) , ,每個每個頁表頁面的大小與物理塊相同，為進行索引查找頁表頁面的大小與物理塊相同，為進行索引查找, ,應(yīng)該為這些頁應(yīng)該為這些頁表頁面建一張頁表表頁面建一張頁表, ,稱為稱為外層頁表外層頁表，其表項指出頁表頁面所在物，其表項指出頁表頁面所在物理塊號及相關(guān)信息。理塊號及相關(guān)信息。 系統(tǒng)為每個進程建一張外層頁表，它的每個表項對應(yīng)一個頁表頁系統(tǒng)為每個進程建一張外層頁表，它的每個表項對應(yīng)一個頁表頁面面, ,而頁表頁面的每個表項給出了頁面

49、和塊號的對應(yīng)關(guān)系而頁表頁面的每個表項給出了頁面和塊號的對應(yīng)關(guān)系, ,外層頁外層頁表是一級頁表表是一級頁表, ,頁表頁面是二級頁表。頁表頁面是二級頁表。邏輯地址結(jié)構(gòu)邏輯地址結(jié)構(gòu) 外層頁號、外層頁內(nèi)地址、頁內(nèi)地址外層頁號、外層頁內(nèi)地址、頁內(nèi)地址第65/96頁外層頁表寄存器外層頁表寄存器外層頁號外層頁號外層頁內(nèi)地址外層頁內(nèi)地址 頁內(nèi)地址頁內(nèi)地址邏輯地址邏輯地址頁表地址頁表地址.外層頁表（每進程一個）外層頁表（每進程一個）塊號塊號.頁表頁表代碼或數(shù)據(jù)代碼或數(shù)據(jù).內(nèi)存塊內(nèi)存塊+塊號塊號 塊內(nèi)地址塊內(nèi)地址物理地址物理地址第66/96頁優(yōu)點優(yōu)點 解決了碎片問題解決了碎片問題 便于管理便于管理缺點缺點 不易實

50、現(xiàn)存儲共享不易實現(xiàn)存儲共享 存在頁內(nèi)碎片存在頁內(nèi)碎片第67/96頁基本原理基本原理 在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面。個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面。 當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。淘汰某個頁面，以便裝入新的頁面。 例例怎樣才能發(fā)現(xiàn)頁面不在內(nèi)存中呢怎樣才能發(fā)現(xiàn)頁面不在內(nèi)存中呢? ?怎樣處理這種情況怎樣處理這種情況呢呢? ? 采用的辦法是：采用的辦

51、法是：擴充頁表擴充頁表的內(nèi)容，增加駐留標(biāo)志位和頁面輔存的內(nèi)容，增加駐留標(biāo)志位和頁面輔存的地址等信息的地址等信息。通過產(chǎn)生通過產(chǎn)生缺頁中斷缺頁中斷來處理來處理. .前進前進第68/96頁151413121110987654321060K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虛地址空間虛地址空間物理地址空間物理地址空間

52、 虛頁虛頁頁框頁框返回返回第69/96頁 頁號、內(nèi)存塊號、駐留位、外存地址、訪問位、修改位頁號、內(nèi)存塊號、駐留位、外存地址、訪問位、修改位v駐留位（中斷位）：表示該頁是在內(nèi)存還是在外存駐留位（中斷位）：表示該頁是在內(nèi)存還是在外存v訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）定）v修改位：查看此頁是否在內(nèi)存中被修改過修改位：查看此頁是否在內(nèi)存中被修改過頁號頁號駐留位駐留位輔存地址輔存地址訪問位訪問位 修改位修改位內(nèi)存塊號內(nèi)存塊號第70/96頁1 11 10 00 01 11 11 10 00 00 00 00 00 01 11 1駐留位駐留

53、位第71/96頁 在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生不在內(nèi)存，則產(chǎn)生缺頁中斷缺頁中斷。操作系統(tǒng)接到此中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，準(zhǔn)備將該頁調(diào)入內(nèi)存。出的外存地址，準(zhǔn)備將該頁調(diào)入內(nèi)存。v此時應(yīng)將缺頁的進程掛起（調(diào)頁完成喚醒）此時應(yīng)將缺頁的進程掛起（調(diào)頁完成喚醒）v如果內(nèi)存中有空閑塊，則分配一個塊，將要調(diào)入如果內(nèi)存中有空閑塊，則分配一個塊，將要調(diào)入的頁裝入該塊，并修改頁表中相應(yīng)頁表項目的駐的頁裝入該塊，并修改頁表中相應(yīng)頁表項目的駐留位及

54、相應(yīng)的內(nèi)存塊號留位及相應(yīng)的內(nèi)存塊號v若此時內(nèi)存中沒有空閑塊，則要淘汰某頁（若被若此時內(nèi)存中沒有空閑塊，則要淘汰某頁（若被淘汰頁在內(nèi)存期間被修改過，則要將其寫回外存）淘汰頁在內(nèi)存期間被修改過，則要將其寫回外存）第72/96頁缺頁中斷和一般中斷都是中斷。缺頁中斷和一般中斷都是中斷。相同點：相同點：v保護現(xiàn)場保護現(xiàn)場 、中斷處理、中斷處理、 恢復(fù)現(xiàn)場恢復(fù)現(xiàn)場不同點：不同點：v一般中斷是一般中斷是一條指令完成后一條指令完成后檢查和處理中斷信號，缺頁檢查和處理中斷信號，缺頁中斷是中斷是一條指令執(zhí)行時一條指令執(zhí)行時產(chǎn)生和處理中斷信號。產(chǎn)生和處理中斷信號。v缺頁中斷缺頁中斷返回到該指令的開始返回到該指令的開

55、始重新執(zhí)行該指令，而一般重新執(zhí)行該指令，而一般中斷返回到該指令的中斷返回到該指令的下一條指令下一條指令執(zhí)行。執(zhí)行。v一條指令執(zhí)行時可能產(chǎn)生多個缺頁中斷。如指令可能訪一條指令執(zhí)行時可能產(chǎn)生多個缺頁中斷。如指令可能訪問多個內(nèi)存地址，這些地址在不同的頁中。問多個內(nèi)存地址，這些地址在不同的頁中。 第73/96頁系統(tǒng)為進程分配主存，需考慮因素系統(tǒng)為進程分配主存，需考慮因素: :v分給進程的空間越小，同一時間處于內(nèi)存的進程就越分給進程的空間越小，同一時間處于內(nèi)存的進程就越多，至少有一個進程處于就緒態(tài)的可能性就越大多，至少有一個進程處于就緒態(tài)的可能性就越大v如果進程只有小部分在主存里，即使局部性很好，缺如果

56、進程只有小部分在主存里，即使局部性很好，缺頁中斷率還會相當(dāng)高頁中斷率還會相當(dāng)高. .v因程序的局部性原理，分給進程的內(nèi)存超過一定限度因程序的局部性原理，分給進程的內(nèi)存超過一定限度后，再增加內(nèi)存空間，不會明顯降低進程的缺頁中斷后，再增加內(nèi)存空間，不會明顯降低進程的缺頁中斷率。率。 基于這些因素，在頁式虛存系統(tǒng)中，可采用兩種策基于這些因素，在頁式虛存系統(tǒng)中，可采用兩種策略分配頁框給進程。略分配頁框給進程。第74/96頁內(nèi)存分配策略分為兩種內(nèi)存分配策略分為兩種 進程保持頁框數(shù)進程保持頁框數(shù)固定不變固定不變，稱固定分配，稱固定分配; ;進程分得的頁框數(shù)可進程分得的頁框數(shù)可變，稱變，稱可變分配可變分配。

57、固定分配固定分配 進程創(chuàng)建時，根據(jù)進程類型和程序員的要求決定頁框數(shù)，只進程創(chuàng)建時，根據(jù)進程類型和程序員的要求決定頁框數(shù)，只要有一個缺頁中斷產(chǎn)生，進程就會有一頁被替換。即使內(nèi)存中要有一個缺頁中斷產(chǎn)生，進程就會有一頁被替換。即使內(nèi)存中有空閑的物理塊，也不分配給該進程。有空閑的物理塊，也不分配給該進程?？勺兎峙淇勺兎峙?先為每個進程分配一定數(shù)目的物理塊，進程執(zhí)行的某階段缺先為每個進程分配一定數(shù)目的物理塊，進程執(zhí)行的某階段缺頁率較高，說明目前局部性較差，系統(tǒng)可多分些頁框以降低缺頁率較高，說明目前局部性較差，系統(tǒng)可多分些頁框以降低缺頁率，反之說明進程目前局部性較好，可減少分給進程的頁框頁率，反之說明進程

58、目前局部性較好，可減少分給進程的頁框數(shù)。數(shù)。第75/96頁固定分配缺少靈活性，而可變分配的性能會更好些，固定分配缺少靈活性，而可變分配的性能會更好些，被許多操作系統(tǒng)采用。被許多操作系統(tǒng)采用。采用可變分配策略的困難在于操作系統(tǒng)要經(jīng)常監(jiān)視采用可變分配策略的困難在于操作系統(tǒng)要經(jīng)常監(jiān)視活動進程的行為和進程缺頁中斷率的情況，會增加活動進程的行為和進程缺頁中斷率的情況，會增加系統(tǒng)的開銷。系統(tǒng)的開銷。第76/96頁全局置換全局置換v如果頁面置換算法的作用范圍是整個系統(tǒng)，稱全如果頁面置換算法的作用范圍是整個系統(tǒng)，稱全局頁面置換算法，它可以在運行進程間動態(tài)地分局頁面置換算法，它可以在運行進程間動態(tài)地分配頁框。被

59、置換的頁可以是內(nèi)存中任一進程的頁。配頁框。被置換的頁可以是內(nèi)存中任一進程的頁。局部置換局部置換v如果頁面置換算法的作用范圍局限于本進程，稱如果頁面置換算法的作用范圍局限于本進程，稱為局部頁面置換算法，它實際上需要為每個進程為局部頁面置換算法，它實際上需要為每個進程分配固定的頁框。始終保持分配給該進程的物理分配固定的頁框。始終保持分配給該進程的物理塊數(shù)不變。塊數(shù)不變。第77/96頁固定分配局部置換策略固定分配局部置換策略 進程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進程的頁面進程分得的頁框數(shù)不變，發(fā)生缺頁中斷，只能從進程的頁面中選頁置換，保證進程的頁框總數(shù)不變。中選頁置換，保證進程的頁框總數(shù)不變。

60、策略難點策略難點 應(yīng)給每個進程分配多少頁框應(yīng)給每個進程分配多少頁框? ? 給少了，缺頁中斷率高；給多了，給少了，缺頁中斷率高；給多了，使內(nèi)存中能同時執(zhí)行的進程數(shù)減少，進而造成處理器和其它設(shè)使內(nèi)存中能同時執(zhí)行的進程數(shù)減少，進而造成處理器和其它設(shè)備空閑。備空閑。采用固定分配算法，系統(tǒng)把頁框分配給進程，采用：采用固定分配算法，系統(tǒng)把頁框分配給進程，采用：1)1)平均分配平均分配2)2)按比例分配按比例分配3)3)優(yōu)先權(quán)分配優(yōu)先權(quán)分配第78/96頁先每個進程分配一定數(shù)目頁框，先每個進程分配一定數(shù)目頁框，osos保留若干空閑保留若干空閑頁框，進程發(fā)生缺頁中斷時，從系統(tǒng)空閑頁框中頁框，進程發(fā)生缺頁中斷時，