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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、 覆蓋與交換覆蓋與交換 第19/96頁(yè) 單用戶(hù)單任務(wù)系統(tǒng)在一段時(shí)間內(nèi)，只有一個(gè)進(jìn)程在內(nèi)單用戶(hù)單任務(wù)系統(tǒng)在一段時(shí)間內(nèi)，只有一個(gè)進(jìn)程在內(nèi)存，故內(nèi)存分配管理十分簡(jiǎn)單，內(nèi)存利用率低。內(nèi)存分存，故內(nèi)存分配管理十分簡(jiǎn)單，內(nèi)存利用率低。內(nèi)存分為兩個(gè)區(qū)域，一個(gè)供操作系統(tǒng)使用，一個(gè)供用戶(hù)使用。為兩個(gè)區(qū)域，一個(gè)供操作系統(tǒng)使用，一個(gè)供用戶(hù)使用。v靜態(tài)重定位靜態(tài)重定位 v界限寄存器界限寄存器v重定位和存儲(chǔ)保護(hù)重定位和存儲(chǔ)保護(hù)操作系統(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ù)先把可分配的主存儲(chǔ)器空間分割成若干個(gè)固預(yù)先把可分配的主存儲(chǔ)器空間分割成若干個(gè)固定大小的連續(xù)存儲(chǔ)區(qū)（存儲(chǔ)塊），稱(chēng)為一個(gè)定大小的連續(xù)存儲(chǔ)區(qū)（存儲(chǔ)塊），稱(chēng)為一個(gè)分區(qū)分區(qū)。每個(gè)分區(qū)的大小可以相同也可以不同。但分區(qū)大小每個(gè)分區(qū)的大小可以相同也可以不同。但分區(qū)大小固定不變，每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)。固定不變，每個(gè)分區(qū)裝一個(gè)且只能裝一個(gè)作業(yè)。 在系統(tǒng)運(yùn)行期間，分區(qū)大小、數(shù)目都不變，所以在系統(tǒng)運(yùn)行期間，分區(qū)大小、數(shù)目都不變，所以固定分區(qū)也稱(chēng)為固定分區(qū)也稱(chēng)為靜態(tài)分區(qū)靜態(tài)分區(qū)。第21/96頁(yè)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頁(yè)124K256KOS20K28K60K 進(jìn)程進(jìn)程A（6K）進(jìn)程進(jìn)程B（25K）進(jìn)程進(jìn)程C（7K） 內(nèi)存的分配與回收，需要借助于內(nèi)存的分配與回收，需要借助于內(nèi)存分配表內(nèi)存分配表數(shù)據(jù)數(shù)據(jù)

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

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

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

21、（16K）OS進(jìn)程進(jìn)程A進(jìn)程進(jìn)程B第25/96頁(yè)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進(jìn)程進(jìn)程E（50K）進(jìn)程進(jìn)程F（16K）進(jìn)入內(nèi)存進(jìn)入內(nèi)存進(jìn)程進(jìn)程B（16K）進(jìn)程進(jìn)程D（124K）完成完成C完成（完成（64K）空閑區(qū)空閑區(qū)內(nèi)存分配變化過(guò)程內(nèi)存分配變化過(guò)程:第26/96頁(yè)空閑分區(qū)表空閑分區(qū)表空閑分區(qū)鏈空閑分區(qū)鏈5 735 73若須分配若須分配25K25K

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

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

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

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

26、分配后剩下的空區(qū)仍可為較大空區(qū)第34/96頁(yè) 優(yōu)點(diǎn)優(yōu)點(diǎn)v當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑區(qū)當(dāng)程序裝入內(nèi)存中最大的空閑區(qū)后，剩下的空閑區(qū)還可能相當(dāng)大，還能裝下較大的程序。還可能相當(dāng)大，還能裝下較大的程序。v另一方面每次僅作一次查詢(xún)工作另一方面每次僅作一次查詢(xún)工作第35/96頁(yè) 某時(shí)刻系統(tǒng)中有三個(gè)空閑區(qū)，大小和首址為：某時(shí)刻系統(tǒng)中有三個(gè)空閑區(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è)序列：作業(yè)A A要求要求21K21K；作業(yè)；作業(yè)B B要求要求30K30K，作業(yè)，作業(yè)C C要求要求25K25K。第37/96頁(yè) 當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí)，系統(tǒng)首先檢查釋放當(dāng)某個(gè)進(jìn)程釋放某存儲(chǔ)區(qū)時(shí)，系統(tǒng)首先檢查釋放區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合區(qū)是否與系統(tǒng)中的空閑區(qū)相鄰，若相鄰則把釋放區(qū)合并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個(gè)空閑并到相鄰的空閑區(qū)中去，否則把釋放區(qū)作為一個(gè)空閑區(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頁(yè)釋放區(qū)不與任何空閑區(qū)相鄰釋放區(qū)不與任何空閑區(qū)相鄰 將釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址插入到空閑區(qū)鏈的適當(dāng)將釋放區(qū)作為一個(gè)空閑區(qū)，將其大小和首址插入到空閑區(qū)鏈的適當(dāng)位置。位置。釋放區(qū)與后空閑區(qū)相鄰釋放區(qū)與后空閑區(qū)相鄰 則把釋放區(qū)合并到后空閑，首地址為釋放區(qū)首地址，大小為二者大則把釋放區(qū)合并到后空閑，首地址為釋放區(qū)首地址，大小為二者大小之和。小之和。釋放區(qū)與前空閑區(qū)相鄰釋放區(qū)與前空閑區(qū)相鄰 將釋放區(qū)與前空閑區(qū)合并為一個(gè)空閑區(qū)。其首址仍為前空閑區(qū)首址，將釋放區(qū)與前空閑區(qū)合并為一個(gè)空閑區(qū)。其首址仍為前空閑區(qū)首址，大小

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

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

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

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

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

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

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

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

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

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

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

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

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

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

43、的頁(yè)表稱(chēng)為快表快表（也稱(chēng)為聯(lián)想寄存（也稱(chēng)為聯(lián)想寄存器），把存放在內(nèi)存中的頁(yè)表稱(chēng)為器），把存放在內(nèi)存中的頁(yè)表稱(chēng)為慢表慢表。快表是頁(yè)表（慢表）的一個(gè)子集快表是頁(yè)表（慢表）的一個(gè)子集第59/96頁(yè)pp頁(yè)表頁(yè)表地址越界地址越界比較比較P=1P=1p ppp. . . .快表快表+頁(yè)號(hào)頁(yè)號(hào)P P 頁(yè)內(nèi)地址頁(yè)內(nèi)地址d dPPd d物理地址物理地址頁(yè)表寄存器頁(yè)表寄存器邏輯地址（有效地址寄存器）邏輯地址（有效地址寄存器）P Pb b頁(yè)表始址頁(yè)表始址b b頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度l l第60/96頁(yè)當(dāng)調(diào)度程序調(diào)度到某個(gè)進(jìn)程時(shí)，要從該進(jìn)程的當(dāng)調(diào)度程序調(diào)度到某個(gè)進(jìn)程時(shí)，要從該進(jìn)程的PCBPCB中把該進(jìn)程的頁(yè)表始中把該進(jìn)程的

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

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

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

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

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

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

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

51、法是：擴(kuò)充頁(yè)表擴(kuò)充頁(yè)表的內(nèi)容，增加駐留標(biāo)志位和頁(yè)面輔存的內(nèi)容，增加駐留標(biāo)志位和頁(yè)面輔存的地址等信息的地址等信息。通過(guò)產(chǎn)生通過(guò)產(chǎn)生缺頁(yè)中斷缺頁(yè)中斷來(lái)處理來(lái)處理. .前進(jìn)前進(jìn)第68/96頁(yè)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、 虛頁(yè)虛頁(yè)頁(yè)框頁(yè)框返回返回第69/96頁(yè) 頁(yè)號(hào)、內(nèi)存塊號(hào)、駐留位、外存地址、訪問(wèn)位、修改位頁(yè)號(hào)、內(nèi)存塊號(hào)、駐留位、外存地址、訪問(wèn)位、修改位v駐留位（中斷位）：表示該頁(yè)是在內(nèi)存還是在外存駐留位（中斷位）：表示該頁(yè)是在內(nèi)存還是在外存v訪問(wèn)位：根據(jù)訪問(wèn)位來(lái)決定淘汰哪頁(yè)（由不同的算法決訪問(wèn)位：根據(jù)訪問(wèn)位來(lái)決定淘汰哪頁(yè)（由不同的算法決定）定）v修改位：查看此頁(yè)是否在內(nèi)存中被修改過(guò)修改位：查看此頁(yè)是否在內(nèi)存中被修改過(guò)頁(yè)號(hào)頁(yè)號(hào)駐留位駐留位輔存地址輔存地址訪問(wèn)位訪問(wèn)位 修改位修改位內(nèi)存塊號(hào)內(nèi)存塊號(hào)第70/96頁(yè)1 11 10 00 01 11 11 10 00 00 00 00 00 01 11 1駐留位駐留

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

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

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

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

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

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

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

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