存儲(chǔ)管理及內(nèi)存的基本相關(guān)知識(shí)

第4章

存儲(chǔ)管理

本章學(xué)習(xí)目標(biāo)

4.1存儲(chǔ)管理的功能

4.2實(shí)存管理

4.3虛擬存儲(chǔ)器管理

4.4碎片與抖動(dòng)問(wèn)題

開(kāi)始本章學(xué)習(xí)目標(biāo)

本章首先介紹了存儲(chǔ)管理的研究對(duì)象和目的，明確了存儲(chǔ)管理的基本功能和有關(guān)的基本概念；然后從實(shí)存和虛存兩個(gè)角度，分別介紹了常用的幾種存儲(chǔ)管理方案；最后對(duì)各種存儲(chǔ)管理方案存在的問(wèn)題，主要是碎片和抖動(dòng)問(wèn)題進(jìn)行了總結(jié)。

返回本章首頁(yè)本章的主要內(nèi)容如下：(1)存儲(chǔ)管理的目的和四大基本功能。

(2)實(shí)存管理中講述了固定分區(qū)存儲(chǔ)管理、可變式分區(qū)存儲(chǔ)管理、純分頁(yè)存儲(chǔ)管理三種存儲(chǔ)管理方案的實(shí)現(xiàn)原理(3)虛存管理以請(qǐng)求式分頁(yè)存儲(chǔ)管理為重點(diǎn)

(4)總結(jié)各種存儲(chǔ)管理方案中存在的碎片和抖動(dòng)問(wèn)題及解決方法下一頁(yè)圖4.1多級(jí)存儲(chǔ)器體系示意圖4.1存儲(chǔ)管理的功能4.1.1內(nèi)存的分配與回收

4.1.2地址重定位4.1.3存儲(chǔ)保護(hù)

4.1.4虛擬存儲(chǔ)器

返回本章首頁(yè)4.1.1內(nèi)存的分配與回收內(nèi)存分配按分配時(shí)機(jī)的不同，可分為兩種方式。（1）靜態(tài)存儲(chǔ)分配：指內(nèi)存分配是在作業(yè)運(yùn)行之前各目標(biāo)模塊連接后，把整個(gè)作業(yè)一次性全部裝入內(nèi)存，并在作業(yè)的整個(gè)運(yùn)行過(guò)程中，不允許作業(yè)再申請(qǐng)其他內(nèi)存，或在內(nèi)存中移動(dòng)位置。也就是說(shuō)，內(nèi)存分配是在作業(yè)運(yùn)行前一次性完成的。（2）動(dòng)態(tài)存儲(chǔ)分配：作業(yè)要求的基本內(nèi)存空間是在目標(biāo)模塊裝入內(nèi)存時(shí)分配的，但在作業(yè)運(yùn)行過(guò)程中，允許作業(yè)申請(qǐng)附加的內(nèi)存空間，或是在內(nèi)存中移動(dòng)，即分配工作可以在作業(yè)運(yùn)行前及運(yùn)行過(guò)程中逐步完成。返回本節(jié)4.1.2地址重定位1．內(nèi)存空間（或物理空間）2．邏輯空間3．地址重定位下一頁(yè)1．內(nèi)存空間（或物理空間）內(nèi)存是由若干個(gè)存儲(chǔ)單元組成的，每個(gè)存儲(chǔ)單元有一個(gè)編號(hào)，這種編號(hào)可唯一標(biāo)識(shí)一個(gè)存儲(chǔ)單元，稱為內(nèi)存地址（或物理地址）。下一頁(yè)2．邏輯空間源程序經(jīng)過(guò)匯編或編譯后，形成目標(biāo)程序，每個(gè)目標(biāo)程序都是以0為基址順序進(jìn)行編址的，原來(lái)用符號(hào)名訪問(wèn)的單元用具體的數(shù)據(jù)——單元號(hào)取代。這樣生成的目標(biāo)程序占據(jù)一定的地址空間，稱為作業(yè)的邏輯地址空間，簡(jiǎn)稱邏輯空間。在邏輯空間中每條指令的地址和指令中要訪問(wèn)的操作數(shù)地址統(tǒng)稱為邏輯地址。下一頁(yè)圖4.2作業(yè)的名空間、邏輯地址空間和裝入后的物理空間下一頁(yè)3．地地址重重定位位(1)靜態(tài)態(tài)地址址重定定位靜態(tài)地地址重重定位位是在在程序序執(zhí)行行之前前由操操作系系統(tǒng)的的重定定位裝裝入程程序完完成的的。(2)動(dòng)態(tài)態(tài)地址址重定定位動(dòng)態(tài)地地址重重定位位是在在程序序執(zhí)行行期間間進(jìn)行行的。。下一頁(yè)頁(yè)（b））采用用動(dòng)態(tài)態(tài)重定定位時(shí)時(shí)內(nèi)存存空間間及地地址重重定位位示意意圖（a））采用用靜態(tài)態(tài)重定定位后后的內(nèi)內(nèi)存空空間圖4.3靜靜態(tài)地地址重重定位位和動(dòng)動(dòng)態(tài)地地址重重定位位示意意圖返回本本節(jié)存存儲(chǔ)儲(chǔ)保護(hù)護(hù)（1）上、、下界界存儲(chǔ)儲(chǔ)保護(hù)護(hù)：上上、下下界保保護(hù)是是一種種簡(jiǎn)單單的存存儲(chǔ)保保護(hù)技技術(shù)。。系統(tǒng)統(tǒng)可為為每個(gè)個(gè)作業(yè)業(yè)設(shè)置置一對(duì)對(duì)上、、下界界寄存存器，，分別別用來(lái)來(lái)存放放當(dāng)前前運(yùn)行行作業(yè)業(yè)在內(nèi)內(nèi)存空空間的的上、、下邊邊界地地址，，用它它們來(lái)來(lái)限制制用戶戶程序序的活活動(dòng)范范圍。。（2）基址址—限長(zhǎng)存存儲(chǔ)保保護(hù)：：上、、下界界保護(hù)護(hù)的一一個(gè)變變種是是采用用基址址—限長(zhǎng)存存儲(chǔ)保保護(hù)。。圖4.4界界限寄寄存器器的兩兩種存存儲(chǔ)保保護(hù)方方式返回本本節(jié)虛虛擬擬存儲(chǔ)儲(chǔ)器對(duì)內(nèi)存存進(jìn)行行邏輯輯上的的擴(kuò)充充，現(xiàn)現(xiàn)在普普遍采采用虛虛擬存存儲(chǔ)管管理技技術(shù)。。虛擬存存儲(chǔ)技技術(shù)的的基本本思想想是把把有限限的內(nèi)內(nèi)存空空間與與大容容量的的外存存統(tǒng)一一管理理起來(lái)來(lái)，構(gòu)構(gòu)成一一個(gè)遠(yuǎn)遠(yuǎn)大于于實(shí)際際內(nèi)存存的、、虛擬擬的存存儲(chǔ)器器。此此時(shí)，，外存存是作作為內(nèi)內(nèi)存的的直接接延伸伸，用用戶并并不會(huì)會(huì)感覺(jué)覺(jué)到內(nèi)內(nèi)、外外存的的區(qū)別別，即即把兩兩級(jí)存存儲(chǔ)器器當(dāng)作作一級(jí)級(jí)存儲(chǔ)儲(chǔ)器來(lái)來(lái)看待待。一一個(gè)作作業(yè)運(yùn)運(yùn)行時(shí)時(shí)，其其全部部信息息裝入入虛存存，實(shí)實(shí)際上上可能能只有有當(dāng)前前運(yùn)行行的必必需一一部分分信息息存入入內(nèi)存存，其其他則則存于于外存存，當(dāng)當(dāng)所訪訪問(wèn)的的信息息不在在內(nèi)存存時(shí)，，系統(tǒng)統(tǒng)自動(dòng)動(dòng)將其其從外外存調(diào)調(diào)入內(nèi)內(nèi)存。。返回本本節(jié)4.2實(shí)實(shí)存存管理理固定分分區(qū)存存儲(chǔ)管管理可變式式分區(qū)區(qū)存儲(chǔ)儲(chǔ)管理理純分頁(yè)頁(yè)存儲(chǔ)儲(chǔ)管理理返回本本章首首頁(yè)固固定定分區(qū)區(qū)存儲(chǔ)儲(chǔ)管理理固定分分區(qū)存存儲(chǔ)管管理是是實(shí)現(xiàn)現(xiàn)多道道程序序設(shè)計(jì)計(jì)的最最簡(jiǎn)單單的一一種存存儲(chǔ)管管理技技術(shù)。。其基基本思思想是是，在在作業(yè)業(yè)未進(jìn)進(jìn)入內(nèi)內(nèi)存之之前，，就由由操作作員或或操作作系統(tǒng)統(tǒng)把內(nèi)內(nèi)存可可用空空間劃劃分成成若干干個(gè)固固定大大小的的存儲(chǔ)儲(chǔ)區(qū)，，除操操作系系統(tǒng)占占用一一個(gè)區(qū)區(qū)域外外，其其余區(qū)區(qū)域?yàn)闉橄到y(tǒng)統(tǒng)中多多個(gè)用用戶共共享，，因?yàn)闉樵谙迪到y(tǒng)運(yùn)運(yùn)行期期間，，分區(qū)區(qū)大小小、數(shù)數(shù)目都都不變變，所所以固固定式式分區(qū)區(qū)也稱稱為靜靜態(tài)分分區(qū)。。圖4.5固固定式式分區(qū)區(qū)內(nèi)存存分配配示意意圖（（a））和（（b））固定定式分分區(qū)說(shuō)說(shuō)明表表返回本本節(jié)可可變變式分分區(qū)存存儲(chǔ)管管理1．空閑閑分區(qū)區(qū)的組組織形形式2．內(nèi)存存的分分配與與回收收3．常用用的分分配算算法4．可變變式分分區(qū)的的地址址重定定位下一頁(yè)頁(yè)圖4.6可可變式式分區(qū)區(qū)內(nèi)存存使用用情況況示意意圖下一頁(yè)頁(yè)1．空空閑分分區(qū)的的組織織形式式空閑分分區(qū)鏈鏈表的的組織織是這這樣的的：在在每個(gè)個(gè)空閑閑分區(qū)區(qū)的起起始部部分開(kāi)開(kāi)辟出出一個(gè)個(gè)單元元，存存放一一個(gè)鏈鏈表指指針和和該分分區(qū)的的大小小，鏈鏈表指指針指指向下下一個(gè)個(gè)空閑閑分區(qū)區(qū)。系系統(tǒng)中中用一一個(gè)固固定單單元作作為空空閑分分區(qū)鏈鏈表的的鏈表表頭指指針，，指向向第一一塊空空閑分分區(qū)首首地址址，最最后一一塊空空閑分分區(qū)的的鏈表表指針針存放放鏈尾尾標(biāo)志志。如如圖4.7（a）所示示。下一頁(yè)頁(yè)2．內(nèi)內(nèi)存的的分配配與回回收當(dāng)某一一個(gè)用用戶作作業(yè)完完成釋釋放所所占分分區(qū)時(shí)時(shí)，系系統(tǒng)應(yīng)應(yīng)進(jìn)行行回收收。在在可變變式分分區(qū)中中，應(yīng)應(yīng)該檢檢查回回收區(qū)區(qū)與內(nèi)內(nèi)存中中前后后空閑閑區(qū)是是否相相鄰，，若相相鄰，，則應(yīng)應(yīng)進(jìn)行行合并并，形形成一一個(gè)較較大的的空閑閑區(qū)，，并對(duì)對(duì)相應(yīng)應(yīng)的鏈鏈表指指針進(jìn)進(jìn)行修修改；；若不不相鄰鄰，應(yīng)應(yīng)將空空閑區(qū)區(qū)插入入到空空閑區(qū)區(qū)鏈表表的適適當(dāng)位位置。。下一頁(yè)頁(yè)圖4.7首首次適適應(yīng)算算法的的空閑閑分區(qū)區(qū)鏈表表組織織形式式下一頁(yè)頁(yè)3．常常用的的分配配算法法（1）首次次適應(yīng)應(yīng)算法法（2）最佳佳適應(yīng)應(yīng)算法法（3）最差差適應(yīng)應(yīng)算法法下一頁(yè)頁(yè)圖4.8最最佳適適應(yīng)算算法的的空閑閑分區(qū)區(qū)鏈表表組織織形式式下一頁(yè)頁(yè)圖4.9最最差適適應(yīng)算算法的的空閑閑分區(qū)區(qū)鏈表表組織織形式式下一頁(yè)頁(yè)圖4.10內(nèi)內(nèi)存存使用用情況況下一頁(yè)頁(yè)圖4.11用用三三種適適應(yīng)算算法處處理同同一作作業(yè)序序列下一頁(yè)頁(yè)4．可可變式式分區(qū)區(qū)的地地址重重定位位可變式式分區(qū)區(qū)的地地址重重定位位可采采用靜靜態(tài)重重定位位，也也可采采用動(dòng)動(dòng)態(tài)重重定位位。如如采用用靜態(tài)態(tài)重定定位，，因用用戶作作業(yè)進(jìn)進(jìn)入內(nèi)內(nèi)存后后，程程序的的邏輯輯地址址實(shí)現(xiàn)現(xiàn)了重重定位位，不不能在在內(nèi)存存中再再進(jìn)行行移動(dòng)動(dòng)，經(jīng)經(jīng)過(guò)一一段時(shí)時(shí)間的的運(yùn)行行，內(nèi)內(nèi)存中中不能能再分分配利利用的的小碎碎片會(huì)會(huì)越來(lái)來(lái)越多多。有有時(shí)可可能會(huì)會(huì)出現(xiàn)現(xiàn)這種種情況況，即即當(dāng)一一個(gè)作作業(yè)申申請(qǐng)一一定數(shù)數(shù)量的的內(nèi)存存時(shí)，，雖然然此時(shí)時(shí)空閑閑區(qū)的的總和和大于于新作作業(yè)的的內(nèi)存存要求求，但但卻沒(méi)沒(méi)有單單個(gè)的的空閑閑區(qū)足足以裝裝下該該作業(yè)業(yè)。采用動(dòng)動(dòng)態(tài)重重定位位的可可變式式分區(qū)區(qū)管理理技術(shù)術(shù)，在在執(zhí)行行內(nèi)存存分配配時(shí)，，如無(wú)無(wú)足夠夠大空空閑塊塊，應(yīng)應(yīng)考慮慮實(shí)現(xiàn)現(xiàn)緊湊湊操作作。其其分配配算法法如圖圖4.12所示示。下一一頁(yè)頁(yè)圖4.12采采用用動(dòng)動(dòng)態(tài)態(tài)重重定定位位的的可可變變式式分分區(qū)區(qū)分分配配算算法法返回回本本節(jié)節(jié)純純分分頁(yè)頁(yè)存存儲(chǔ)儲(chǔ)管管理理1．純純分分頁(yè)頁(yè)存存儲(chǔ)儲(chǔ)管管理理中中存存儲(chǔ)儲(chǔ)塊塊的的分分配配與與回回收收2．純純分分頁(yè)頁(yè)存存儲(chǔ)儲(chǔ)管管理理的的地地址址重重定定位位問(wèn)問(wèn)題題3．聯(lián)聯(lián)想想存存儲(chǔ)儲(chǔ)器器4．存存儲(chǔ)儲(chǔ)保保護(hù)護(hù)下一一頁(yè)頁(yè)1．．純純分分頁(yè)頁(yè)存存儲(chǔ)儲(chǔ)管管理理中中存存儲(chǔ)儲(chǔ)塊塊的的分分配配與與回回收收通常常有有兩兩種種記記錄錄空空閑閑存存儲(chǔ)儲(chǔ)塊塊的的方方法法：：位位圖圖法法和和鏈鏈表表法法。。（a））存存儲(chǔ)儲(chǔ)塊塊使使用用情情況況（（b））存存儲(chǔ)儲(chǔ)塊塊使使用用情情況況的的位位圖圖表表示示圖4-13存存儲(chǔ)儲(chǔ)塊塊的的位位圖圖管管理理法法2．．純純分分頁(yè)頁(yè)存存儲(chǔ)儲(chǔ)管管理理的的地地址址重重定定位位問(wèn)問(wèn)題題純分分頁(yè)頁(yè)存存儲(chǔ)儲(chǔ)管管理理中中的的地地址址重重定定位位是是非非常常重重要要的的，，要要使使不不連連續(xù)續(xù)的的、、分分散散的的用用戶戶程程序序能能正正常常運(yùn)運(yùn)行行，，須須采采用用動(dòng)動(dòng)態(tài)態(tài)地地址址重重定定位位。。此此時(shí)時(shí)，，可可采采用用重重定定位位寄寄存存器器方方式式，，如如分分頁(yè)頁(yè)太太多多，，則則重重定定位位寄寄存存器器用用得得太太多多。。通通常?？煽稍谠趦?nèi)內(nèi)存存中中為為每每個(gè)個(gè)作作業(yè)業(yè)開(kāi)開(kāi)辟辟一一塊塊特特定定區(qū)區(qū)域域，，建建立立起起作作業(yè)業(yè)的的邏邏輯輯頁(yè)頁(yè)與與存存儲(chǔ)儲(chǔ)塊塊之之間間的的對(duì)對(duì)應(yīng)應(yīng)表表格格關(guān)關(guān)系系，，這這種種表表常常稱稱為為頁(yè)頁(yè)面面映映象象表表，，簡(jiǎn)簡(jiǎn)稱稱頁(yè)頁(yè)表表。。下一一頁(yè)頁(yè)圖4.14純純分分頁(yè)頁(yè)存存儲(chǔ)儲(chǔ)管管理理示示意意圖圖下一一頁(yè)頁(yè)3．．聯(lián)聯(lián)想想存存儲(chǔ)儲(chǔ)器器從上上面面介介紹紹的的地地址址變變換換過(guò)過(guò)程程可可以以看看出出：：如如果果把把頁(yè)頁(yè)表表全全部部放放在在內(nèi)內(nèi)存存，，那那么么存存取取一一個(gè)個(gè)數(shù)數(shù)據(jù)據(jù)時(shí)時(shí)，，至至少少要要訪訪問(wèn)問(wèn)二二次次內(nèi)內(nèi)存存。。一一次次是是訪訪問(wèn)問(wèn)頁(yè)頁(yè)表表，，形形成成實(shí)實(shí)際際內(nèi)內(nèi)存存地地址址；；另另一一次次是是根根據(jù)據(jù)形形成成的的內(nèi)內(nèi)存存地地址址存存取取數(shù)數(shù)據(jù)據(jù)。。顯顯然然，，這這比比通通常常執(zhí)執(zhí)行行指指令令的的速速度度要要慢慢得得多多，，使使計(jì)計(jì)算算機(jī)機(jī)的的運(yùn)運(yùn)行行速速度度幾幾乎乎降降低低一一半半。。應(yīng)用用聯(lián)聯(lián)想想存存儲(chǔ)儲(chǔ)器器和和頁(yè)頁(yè)表表相相結(jié)結(jié)合合的的方方式式，，可可有有效效地地提提高高系系統(tǒng)統(tǒng)動(dòng)動(dòng)態(tài)態(tài)地地址址轉(zhuǎn)轉(zhuǎn)換換的的速速度度，，是是一一種種行行之之有有效效的的方方法法。。下一一頁(yè)頁(yè)圖4.15純純分分頁(yè)頁(yè)存存儲(chǔ)儲(chǔ)管管理理地地址址重重定定位位實(shí)實(shí)現(xiàn)現(xiàn)過(guò)過(guò)程程下一一頁(yè)頁(yè)圖4.16采采用用快快表表和和頁(yè)頁(yè)表表相相結(jié)結(jié)合合的的分分頁(yè)頁(yè)地地址址變變換換過(guò)過(guò)程程示示意意圖圖下一一頁(yè)頁(yè)4．．存存儲(chǔ)儲(chǔ)保保護(hù)護(hù)四種種保保護(hù)護(hù)方方式式：：①①禁禁止止做做任任何何操操作作，，②②只只能能執(zhí)執(zhí)行行，，③③只只能能讀讀，，④④能能讀讀/寫，，當(dāng)當(dāng)要要訪訪問(wèn)問(wèn)某某頁(yè)頁(yè)時(shí)時(shí)，，先先判判斷斷該該頁(yè)頁(yè)的的存存取取控控制制和和存存儲(chǔ)儲(chǔ)保保護(hù)護(hù)信信息息是是否否允允許許。。添加加了了存存取取控控制制信信息息的的頁(yè)頁(yè)表表表表目目如如下下圖圖所所示示：：返回回本本節(jié)節(jié)4.3虛虛擬擬存存儲(chǔ)儲(chǔ)器器管管理理虛擬擬存存儲(chǔ)儲(chǔ)器器的的概概念念請(qǐng)求求式式分分頁(yè)頁(yè)存存儲(chǔ)儲(chǔ)管管理理與與動(dòng)動(dòng)態(tài)態(tài)地地址址重重定定位位現(xiàn)代計(jì)算算機(jī)系統(tǒng)統(tǒng)改進(jìn)的的動(dòng)態(tài)地地址重定定位頁(yè)面置換換算法請(qǐng)求式分分頁(yè)存儲(chǔ)儲(chǔ)管理性性能分析析舉例請(qǐng)求式分分段存儲(chǔ)儲(chǔ)管理返回本章章首頁(yè)虛虛擬存存儲(chǔ)器的的概念（1）程程序中往往往會(huì)有有一些彼彼此互斥斥的部分分。（2）在在一個(gè)完完整的程程序中，，會(huì)有一一些諸如如出錯(cuò)處處理這樣樣的子程程序，在在作業(yè)正正常運(yùn)行行情況下下不會(huì)執(zhí)執(zhí)行這些些程序，，沒(méi)有必必要把它它們調(diào)入入內(nèi)存。?；诔绦蛐蚓植啃孕栽砗秃蜕鲜銮榍闆r，就就沒(méi)有必必要把一一個(gè)作業(yè)業(yè)一次性性全部裝裝入內(nèi)存存再開(kāi)始始運(yùn)行。。而是可可以把程程序當(dāng)前前執(zhí)行所所涉及的的信息放放入內(nèi)存存中，其其余部分分可根據(jù)據(jù)需要臨臨時(shí)調(diào)入入，由操操作系統(tǒng)統(tǒng)和硬件件相配合合來(lái)完成成主存和和輔存之之間信息息的動(dòng)態(tài)態(tài)調(diào)度。。這樣的的計(jì)算機(jī)機(jī)系統(tǒng)好好像為用用戶提供供了一個(gè)個(gè)存儲(chǔ)容容量比實(shí)實(shí)際主存存大得多多的存儲(chǔ)儲(chǔ)器，就就稱為虛虛擬存儲(chǔ)儲(chǔ)器。返回本節(jié)節(jié)請(qǐng)請(qǐng)求式式分頁(yè)存存儲(chǔ)管理理與動(dòng)態(tài)態(tài)地址重重定位請(qǐng)求式分分頁(yè)存儲(chǔ)儲(chǔ)管理與與純分頁(yè)頁(yè)存儲(chǔ)管管理在內(nèi)內(nèi)存塊的的分配與與回收，，存儲(chǔ)保保護(hù)某方方面都十十分相似似，不同同之處在在于地址址重定位位問(wèn)題。。在請(qǐng)求求式分頁(yè)頁(yè)存儲(chǔ)管管理的地地址重定定位時(shí)，，可能會(huì)會(huì)出現(xiàn)所所需頁(yè)面面不在主主存的情情況，此此時(shí)，系系統(tǒng)必須須解決以以下兩個(gè)個(gè)問(wèn)題：：（1）當(dāng)當(dāng)程序要要訪問(wèn)的的某頁(yè)不不在內(nèi)存存時(shí)，如如何發(fā)現(xiàn)現(xiàn)這種缺缺頁(yè)情況況？發(fā)現(xiàn)現(xiàn)后應(yīng)如如何處理理？（2）當(dāng)當(dāng)需要把把外存上上的某個(gè)個(gè)頁(yè)面調(diào)調(diào)入內(nèi)存存時(shí)，此此時(shí)內(nèi)存存中沒(méi)有有空閑塊塊應(yīng)怎么么辦？下一頁(yè)如圖4.17所所示是請(qǐng)請(qǐng)求式分分頁(yè)存儲(chǔ)儲(chǔ)管理的的存儲(chǔ)映映像下一頁(yè)為了幫助助操作系系統(tǒng)對(duì)要要置換出出內(nèi)存的的頁(yè)面進(jìn)進(jìn)行選擇擇，在頁(yè)頁(yè)表中還還可以增增加一個(gè)個(gè)引用位位，以反反映該頁(yè)頁(yè)最近的的使用情情況。一般來(lái)說(shuō)說(shuō)，一個(gè)個(gè)頁(yè)表的的表目通通?？砂ㄈ缦孪碌臄?shù)據(jù)據(jù)內(nèi)容：：下一頁(yè)請(qǐng)求式分分頁(yè)存儲(chǔ)儲(chǔ)管理中中的地址址重定位位和缺頁(yè)頁(yè)中斷處處理過(guò)程程如圖4.18所示。。返回本節(jié)節(jié)現(xiàn)現(xiàn)代計(jì)計(jì)算機(jī)系系統(tǒng)改進(jìn)進(jìn)的動(dòng)態(tài)態(tài)地址重重定位（1）如如何合理理地組織織管理相相當(dāng)大的的頁(yè)表？？在WindowsNT中，為解決決第一個(gè)問(wèn)題題，對(duì)頁(yè)表本本身進(jìn)行了改改進(jìn)，將龐大大的頁(yè)表本身身也采取分頁(yè)頁(yè)措施，采用用了兩級(jí)頁(yè)表表結(jié)構(gòu)。即把把頁(yè)表本身按按固定大小分分成一個(gè)個(gè)小小頁(yè)表，每個(gè)個(gè)小頁(yè)表由210=1024個(gè)個(gè)頁(yè)表表目構(gòu)構(gòu)成，每個(gè)表表目占4字節(jié)節(jié)，所以每個(gè)個(gè)小頁(yè)表剛好好占一個(gè)頁(yè)面面（頁(yè)面大小小為212=4kb）。。一共有210=1k個(gè)小頁(yè)頁(yè)表。為了對(duì)對(duì)這1k個(gè)小小頁(yè)表進(jìn)行管管理和索引查查找，設(shè)置了了一個(gè)頁(yè)表目目錄，也稱之之為頂級(jí)頁(yè)表表或一級(jí)頁(yè)表表，該頁(yè)目錄錄包含有1k個(gè)表目項(xiàng)，，分別指出每每個(gè)次級(jí)小頁(yè)頁(yè)表所在的物物理塊號(hào)和其其他有關(guān)狀態(tài)態(tài)信息。這樣樣，每個(gè)作業(yè)業(yè)有一個(gè)頁(yè)目目錄（一級(jí)頁(yè)頁(yè)表），它的的每個(gè)表目指指向一個(gè)二級(jí)級(jí)頁(yè)表。頁(yè)目目錄本身也剛剛好是一個(gè)頁(yè)頁(yè)面大?。?10=1k，每個(gè)個(gè)表目4個(gè)字字節(jié)）。下一頁(yè)圖4.19WindowsNT兩級(jí)頁(yè)表表地址變換示示意圖下一頁(yè)（2）面對(duì)大大的頁(yè)表，地地址的映射怎怎樣才能比較較快地實(shí)現(xiàn)？？（1）使用快表：：即利用前面面我們已介紹紹的高速緩沖沖存儲(chǔ)器來(lái)存存放經(jīng)常使用用的頁(yè)表表目目，以提高頁(yè)頁(yè)表的查詢速速度。（2）使用高速緩緩沖存儲(chǔ)器：：在微處理器器和主存之間間設(shè)置32kb或64kb的高速緩沖存存儲(chǔ)器，大部部分的指令和和數(shù)據(jù)取自高高速緩存（命命中率為98%），所以存取取數(shù)據(jù)和指令令速度相當(dāng)高高，達(dá)到與處處理器速度完完全相匹配。。返回本節(jié)頁(yè)頁(yè)面置換換算法1．最優(yōu)算法法（OPT算算法）2．先進(jìn)先出出算法（FIFO算法））3．最久未使使用頁(yè)面置換換算法（LRU算法）4．LRU近近似算法下一頁(yè)1．最優(yōu)算法法（OPT算算法）最理想的頁(yè)面面置換算法是是：從內(nèi)存中中移出以后不不再使用的頁(yè)頁(yè)面；如無(wú)這這樣的頁(yè)面，，則選擇以后后最長(zhǎng)時(shí)間內(nèi)內(nèi)不需要訪問(wèn)問(wèn)的頁(yè)。這就就是最優(yōu)算法法的思想。這種算法本身身不是一種實(shí)實(shí)際的方法，，因?yàn)轫?yè)面訪訪問(wèn)的順序是是很難預(yù)知的的。但是，可可把它作為一一種評(píng)價(jià)標(biāo)準(zhǔn)準(zhǔn)，比較其他他實(shí)用方法的的優(yōu)劣，所以以，最優(yōu)算法法只具有理論論上的意義。。下一頁(yè)2．先進(jìn)先出出算法（FIFO算法））這種算法的基基本思想是：：總是先淘汰汰那些駐留在在內(nèi)存時(shí)間最最長(zhǎng)的頁(yè)面，，即先進(jìn)入內(nèi)內(nèi)存的頁(yè)面先先被置換掉。。理由是：最最先進(jìn)入內(nèi)存存的頁(yè)面不再再被訪問(wèn)的可可能性最大。。下一頁(yè)圖4.20先先進(jìn)先出出算法存儲(chǔ)分分塊表構(gòu)造下一頁(yè)3．最久未使使用頁(yè)面置換換算法（LRU算法）這種算法的基基本思想是，，如果某一頁(yè)頁(yè)被訪問(wèn)了，，那么它很可可能馬上又被被訪問(wèn)；反之之，如果某一一頁(yè)很長(zhǎng)時(shí)間間沒(méi)有被訪問(wèn)問(wèn)，那么最近近也不太可能能會(huì)被訪問(wèn)。。這種算法考考慮了程序設(shè)設(shè)計(jì)的局部性性原理。其實(shí)實(shí)質(zhì)是，當(dāng)需需要置換一頁(yè)頁(yè)時(shí)，選擇在在最近一段時(shí)時(shí)間最久未使使用的頁(yè)面予予以淘汰。實(shí)現(xiàn)這種算法法可通過(guò)周期期性地對(duì)“引引用位”進(jìn)行行檢查，并利利用它來(lái)記錄錄一頁(yè)面自上上次被訪問(wèn)以以來(lái)所經(jīng)歷的的時(shí)間t，淘汰時(shí)選擇擇t最大的頁(yè)面。。下一頁(yè)4．LRU近近似算法這種算法，只只要在存儲(chǔ)分分塊表（或頁(yè)頁(yè)表）中設(shè)一一個(gè)“引用位位”，當(dāng)存儲(chǔ)儲(chǔ)分塊表中的的某一頁(yè)被訪訪問(wèn)時(shí)，該位位由硬件自動(dòng)動(dòng)置1，并由頁(yè)面管管理軟件周期期性把所有引引用位置0。這樣，在一一個(gè)時(shí)間周期期T內(nèi)，某些被訪訪問(wèn)過(guò)的頁(yè)面面其引用位為為1，而未被訪問(wèn)問(wèn)過(guò)的頁(yè)面其其引用位為0。因此，可根根據(jù)引用位的的狀態(tài)來(lái)判別別各頁(yè)面最近近的使用情況況。當(dāng)需要置置換一頁(yè)面時(shí)時(shí)，選擇其引引用位為0的頁(yè)，如圖4.21所示的算法。圖4.22是這種近似算算法的一個(gè)例例子。下一頁(yè)圖4.21LRU近似算法下一頁(yè)圖4.22LRU近近似算法舉例例返回本節(jié)請(qǐng)請(qǐng)求式分分頁(yè)存儲(chǔ)管理理性能分析舉舉例1．程序設(shè)計(jì)計(jì)的質(zhì)量2．頁(yè)面的大大小3．分配的內(nèi)內(nèi)存塊數(shù)4．頁(yè)面置換換算法性能下一頁(yè)【例1】主存塊數(shù)m=3，置換算法采采用FIFO算法，缺頁(yè)中中斷次數(shù)及缺缺頁(yè)率如圖4.23所示。在圖4.23中，P行表示頁(yè)面走走向，M行表示在主存存中的頁(yè)面號(hào)號(hào)，其中帶有有+的表示新調(diào)入入頁(yè)面，在M行的各列按調(diào)調(diào)入的順序排排列，帶有圓圓圈的數(shù)字表表示下一時(shí)刻刻將被淘汰頁(yè)頁(yè)面，F(xiàn)行表示是否引引起缺頁(yè)中斷斷，帶√號(hào)的表示引起起缺頁(yè)中斷。。從圖4.23可以看出，缺缺頁(yè)中斷頁(yè)數(shù)數(shù)為9次，缺頁(yè)率f=9/12=75%。下一頁(yè)圖4.23FIFO算法性能分分析（m=3）下一頁(yè)【例2】設(shè)m=4，仍采用FIFO算法，缺頁(yè)中中斷次數(shù)及缺缺頁(yè)率如圖4.24所示。可以算算出，在分配配給該作業(yè)的的內(nèi)存塊數(shù)增增加到4時(shí)，缺頁(yè)中斷斷由圖4.23的9次反而增加到到了10次，缺頁(yè)率由由75%增加到10/12=83%，這就是FIFO算法的一種異異?，F(xiàn)象。隨隨著分配的主主存塊數(shù)的增增加，缺頁(yè)中中斷次數(shù)不但但沒(méi)有降低，，反而增加了了。這與該算算法定全不考考慮程序的動(dòng)動(dòng)態(tài)特征有關(guān)關(guān)。下一頁(yè)圖4.24FIFO算法性能分分析（m=4）下一頁(yè)【例3】設(shè)m=3，采用LRU算法，缺頁(yè)中中斷次數(shù)及缺缺頁(yè)率如圖4.25所示。圖4.25LRU算算法性能分析析（m=3））下一頁(yè)【例4】設(shè)m=4，其余同例3，則缺頁(yè)中斷斷次數(shù)及缺頁(yè)頁(yè)率如圖4.26所示。圖4.26LRU算算法性能分析析（m=4））返回本節(jié)請(qǐng)請(qǐng)求式分分段存儲(chǔ)管理理為了能實(shí)現(xiàn)虛虛擬存儲(chǔ)，段段式邏輯地址址空間中的程程序段在運(yùn)行行時(shí)并不全部部裝入內(nèi)存，，而是如同請(qǐng)請(qǐng)求式分頁(yè)存存儲(chǔ)管理，首首先調(diào)入一個(gè)個(gè)或若干個(gè)程程序段運(yùn)行，，在運(yùn)行過(guò)程程中調(diào)用到哪哪段時(shí)，就根根據(jù)該段長(zhǎng)度度在內(nèi)存分配配一個(gè)連續(xù)的的分區(qū)給它使使用。若內(nèi)存存中沒(méi)有足夠夠大的空閑分分區(qū)，則考慮慮進(jìn)行段的緊緊湊或?qū)⒛扯味位蚰承┒翁蕴蕴鋈?。相相?yīng)于請(qǐng)求式式分頁(yè)存儲(chǔ)管管理，這種存存儲(chǔ)管理技術(shù)術(shù)稱為請(qǐng)求式式分段存儲(chǔ)管管理。下一頁(yè)圖4.27分分段的邏邏輯地址空間間下一頁(yè)請(qǐng)求式分段存存儲(chǔ)管理的地地址變換1．程序的邏輯輯地址結(jié)構(gòu)2．段表3．請(qǐng)求式分段段動(dòng)態(tài)地址變變換過(guò)程4．請(qǐng)求式分段段存儲(chǔ)管理的的優(yōu)、缺點(diǎn)下一頁(yè)1．程序的邏邏輯地址結(jié)構(gòu)構(gòu)請(qǐng)求式分段存存儲(chǔ)管理的邏邏輯地址結(jié)構(gòu)構(gòu)由段號(hào)s和段內(nèi)位移量量d組成，如下圖圖所示。下一頁(yè)2．段表類似于請(qǐng)求式式分頁(yè)存儲(chǔ)管管理的頁(yè)表，，為了實(shí)現(xiàn)動(dòng)動(dòng)態(tài)地址變換換和存儲(chǔ)保護(hù)護(hù)，系統(tǒng)要為為每一個(gè)作業(yè)業(yè)建立一張段段表。段表中中的每一個(gè)表表目對(duì)應(yīng)著作作業(yè)地址空間間的一個(gè)程序序段，其一般般格式為：下一頁(yè)3．請(qǐng)求式分分段動(dòng)態(tài)地址址變換過(guò)程圖4.28請(qǐng)請(qǐng)求式分分段動(dòng)態(tài)地址址下一頁(yè)請(qǐng)求式分段存存儲(chǔ)管理的地地址變換（1）可提供大容容量的虛存（2）允許動(dòng)態(tài)增增加段的長(zhǎng)度度（3）便于段的動(dòng)動(dòng)態(tài)鏈接（4）便于實(shí)現(xiàn)程程序段的共享享（5）便于實(shí)現(xiàn)存存儲(chǔ)保護(hù)返回本節(jié)4.4碎碎片與抖動(dòng)問(wèn)問(wèn)題1、碎片問(wèn)題題解決碎片問(wèn)題題的比較好的的方法是采用用分頁(yè)技術(shù)，，在純分頁(yè)存存儲(chǔ)管理系統(tǒng)統(tǒng)中，因存儲(chǔ)儲(chǔ)區(qū)劃分成固固定大小的塊塊，而用戶作作業(yè)也劃分成成與塊相等的的若干頁(yè)，每每個(gè)作業(yè)調(diào)入入內(nèi)存時(shí)，除除最后一個(gè)頁(yè)頁(yè)面可能有頁(yè)頁(yè)內(nèi)碎片出現(xiàn)現(xiàn)外，其余頁(yè)頁(yè)不存在碎片片問(wèn)題，一般般來(lái)說(shuō)，平均均每個(gè)作業(yè)可可能有半頁(yè)的的內(nèi)碎片。返回本章首頁(yè)頁(yè)2、抖動(dòng)現(xiàn)象象避免抖動(dòng)現(xiàn)象象最根本的方方法是控制多多道程序的道道數(shù)，使得每每個(gè)用戶作業(yè)業(yè)都有足夠的的內(nèi)存空間可可供使用。但但作業(yè)的個(gè)數(shù)數(shù)又不能太少少，否則，會(huì)會(huì)影響處理機(jī)機(jī)的利用率。。最好是使處處理機(jī)利用率率較高，又不不致于使系統(tǒng)統(tǒng)發(fā)生抖動(dòng)，，這是一個(gè)很很難解決的問(wèn)問(wèn)題，牽扯到到程序的局部部性問(wèn)題，并并需借助于工工作集模型。。返回本節(jié)THANKYOUVERYMUCH！！本章到此結(jié)束束，謝謝您的光臨臨！返回本章首頁(yè)頁(yè)結(jié)束放映9、靜夜四四無(wú)鄰，，荒居舊舊業(yè)貧。。。12月-2212月-22Friday,December23,202210、雨中黃黃葉樹(shù)，，燈下白白頭人。。。23:43:1923:43:1923:4312/23/202211:43:19PM11、以我獨(dú)獨(dú)沈久，，愧君相相見(jiàn)頻。。。12月-2223:43:1923:43Dec-2223-Dec-2212、故人江海別別，幾度隔山山川。。23:43:1923:43:1923:43Friday,December23,202213、乍見(jiàn)翻疑疑夢(mèng)，相悲悲各問(wèn)年。。。12月-2212月-2223:43:1923:43:19December23,202214、他鄉(xiāng)生白白發(fā)，舊國(guó)國(guó)見(jiàn)青山。。。23十二二月202211:43:19下下午23:43:1912月-2215、比比不不了了得得就就不不比比，，得得不不到到的的就就不不要要。。。。。十二二月月2211:43下下午午12月月-2223:43December23,202216、行行動(dòng)動(dòng)出出成成果果，，工工作作出出財(cái)財(cái)富富。。。。2022/12/2323:43:1923:43:1923December202217、做前，能夠夠環(huán)視四周；；做時(shí)，你只只能或者最好好沿著以腳為為起點(diǎn)的射線線向前。。11:43:19下午午11:43下下午23:43:1912月-229、沒(méi)有有失敗敗，只只有暫暫時(shí)停停止成成功！！。12月月-2212月月-22Friday,December23,202210、很多多事情情努力力了未未必有有結(jié)果果，但但是不不努力力卻什什么改改變也也沒(méi)有有。。。23:43:1923:43:1923:4312/23/202211:43:19PM11、成功功就是是日復(fù)復(fù)一日日那一一點(diǎn)點(diǎn)點(diǎn)小小小努力