第四章存儲(chǔ)要點(diǎn)課件

第四章存儲(chǔ)管理

存儲(chǔ)管理的基本概念早期的存儲(chǔ)管理分頁(yè)存儲(chǔ)管理請(qǐng)求分頁(yè)存儲(chǔ)管理分段存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理存儲(chǔ)器是計(jì)算機(jī)系統(tǒng)的重要資源,雖然存儲(chǔ)器的容量迅速增加,但軟件的需求也同樣在急劇膨脹,存儲(chǔ)器仍然是緊俏資源。存儲(chǔ)器管理是操作系統(tǒng)的最重要部分。外存——容量巨大、價(jià)格便宜，但存取速度低于內(nèi)存，且CPU不能直接存取外存上的信息高速緩存——存取速度比內(nèi)存快，CPU可直接存取其中的信息，但成本遠(yuǎn)遠(yuǎn)高于內(nèi)存的成本，且容量小內(nèi)存——容量、存取速度和價(jià)格介于外存和高速緩存之間，CPU可直接存取其中的信息存儲(chǔ)器的層次結(jié)構(gòu)Cache主存磁盤4.1存儲(chǔ)管理的基本概念一、存儲(chǔ)管理研究的課題

1.存儲(chǔ)分配問題

2.地址再定位

3.存儲(chǔ)保護(hù)

4.存儲(chǔ)擴(kuò)充1.充分利用內(nèi)存,為多道程序并發(fā)執(zhí)行提供存儲(chǔ)基礎(chǔ)2.盡可能方便用戶使用自動(dòng)裝入用戶程序用戶程序中不必考慮硬件細(xì)節(jié)3.系統(tǒng)能夠解決程序空間比實(shí)際內(nèi)存空間大的問題4.程序在執(zhí)行時(shí)可以動(dòng)態(tài)伸縮5.存儲(chǔ)保護(hù)與安全6.共享與通信7.了解有關(guān)資源的使用狀況8.實(shí)現(xiàn)的性能和代價(jià),性能高,時(shí)空開銷小二、存儲(chǔ)管理的目的方便用戶，使用戶減少甚至擺脫對(duì)存儲(chǔ)器使用的管理；提高內(nèi)存資源的利用率，關(guān)鍵是實(shí)現(xiàn)內(nèi)存共享。三、地址再定位在多道程序環(huán)境下，程序要運(yùn)行必須為之創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程的第一件事，就是要將程序和數(shù)據(jù)裝入內(nèi)存。如何將一個(gè)用戶源程序變?yōu)橐粋€(gè)可在內(nèi)存中執(zhí)行的程序，通常要經(jīng)過以下幾步：編譯：由編譯程序(Compile)將用戶源代碼譯成若干個(gè)目標(biāo)模塊(ObjectModule);鏈接：由鏈接程序(Linker)將編譯后形成的目標(biāo)模塊以及它們所需要的庫(kù)函數(shù)，鏈接在一起，形成一個(gè)裝入模塊(LoadModule);裝入：由裝入程序(Loader)將裝入模塊裝入內(nèi)存。源程序編譯程序或匯編程序目標(biāo)模塊鏈接程序裝配模塊裝配程序裝配階段編譯階段內(nèi)存中可執(zhí)行代碼鏈接階段三、地址再定位邏輯地址：用戶程序經(jīng)編譯鏈接之后形成的裝配模塊都以0為基地址順序編址，這種地址稱為相對(duì)地址或邏輯地址。不能用邏輯地址直接在內(nèi)存中讀取信息。物理地址：內(nèi)存中各物理存儲(chǔ)單元的地址是從統(tǒng)一的基地址順序編址，這種地址稱為絕對(duì)地址或物理地址。三、地址再定位地址空間：（邏輯地址空間）

由程序中邏輯地址組成的地址范圍。存儲(chǔ)空間：（物理地址空間）由內(nèi)存中一系列存儲(chǔ)單元所限定的地址范圍。內(nèi)存空間用來(lái)存放當(dāng)前正在運(yùn)行程序的代碼及數(shù)據(jù),是程序中指令本身地址所指的、亦即程序計(jì)數(shù)器所指的存儲(chǔ)器。名空間：程序中由符號(hào)名組成的空間。提供給程序員使用的。三、地址再定位

邏輯地址

物理地址(相對(duì)地址,虛地址)(絕對(duì)地址,實(shí)地址)地址映射BA=1000....LoadA200…3456…1100物理地址空間…LoadAd1……d13456…源程序…LoadA200……3456…000100200編譯鏈接邏輯地址空間1200地址映射地址映射的原因

當(dāng)程序裝入內(nèi)存時(shí),操作系統(tǒng)要為該程序分配一個(gè)合適的內(nèi)存空間,由于程序的邏輯地址與分配到內(nèi)存物理地址不一致,而CPU執(zhí)行指令時(shí),是按物理地址進(jìn)行的,所以要進(jìn)行地址轉(zhuǎn)換。地址再定位為了保證CPU執(zhí)行指令時(shí)可正確訪問存儲(chǔ)單元,需將用戶程序中的邏輯地址,轉(zhuǎn)換為運(yùn)行時(shí)由機(jī)器直接尋址的物理地址,這一過程稱為地址映射，即地址再定位或地址重定位。地址重定位可分為靜態(tài)重定位和動(dòng)態(tài)重定位兩種。靜態(tài)再定位在目標(biāo)程序裝入內(nèi)存時(shí)，由裝入程序?qū)δ繕?biāo)程序中的指令和數(shù)據(jù)的地址進(jìn)行修改，即把程序的邏輯地址都改成實(shí)際的內(nèi)存地址。（在程序執(zhí)行之前進(jìn)行）特點(diǎn)：這種地址轉(zhuǎn)換在裝入時(shí)一次完成，在程序運(yùn)行期間不再進(jìn)行重定位。優(yōu)點(diǎn)：容易實(shí)現(xiàn)，無(wú)需硬件支持，由專門設(shè)計(jì)的程序(link或load)來(lái)完成。缺點(diǎn)：程序的存儲(chǔ)空間只能是連續(xù)的一片區(qū)域，而且在重定位之后就不能再移動(dòng)。這不利于內(nèi)存空間的有效利用。各個(gè)用戶程序很難共享內(nèi)存中同一程序的副本。動(dòng)態(tài)再定位

在程序運(yùn)行過程中要訪問數(shù)據(jù)時(shí)再進(jìn)行地址變換(在逐條指令執(zhí)行時(shí)完成地址映射;為了提高效率,此工作一般由硬件地址映射機(jī)制來(lái)完成;硬件支持,軟硬件結(jié)合完成),硬件上需要一對(duì)寄存器的支持（再定位寄存器（基址寄存器），界限寄存器（變址寄存器））。（在程序運(yùn)行過程中進(jìn)行）主存實(shí)際地址

=有效地址

+再定位寄存器內(nèi)容

優(yōu)點(diǎn)：程序占用的內(nèi)存空間動(dòng)態(tài)可變，不必連續(xù)存放在一處，有利于內(nèi)存的充分利用。程序不必連續(xù)存放在內(nèi)存中，可以分散在內(nèi)存的若干個(gè)不同區(qū)域，只需增加幾對(duì)基址-限長(zhǎng)寄存器，每對(duì)寄存器對(duì)應(yīng)一個(gè)區(qū)域。比較容易實(shí)現(xiàn)幾個(gè)進(jìn)程對(duì)同一程序副本的共享使用03456......LoadA200......0100200300.........LoadA2003456邏輯地址空間110012001300物理地址空間200VR┼1000BR地址重定位四、虛擬存儲(chǔ)器問題的提出

程序大于總內(nèi)存多個(gè)程序要運(yùn)行而內(nèi)存只能容納部分作業(yè)程序執(zhí)行的特點(diǎn)一個(gè)程序（進(jìn)程）在執(zhí)行過程中，一段時(shí)間內(nèi)總是集中在某些代碼段上執(zhí)行，其余大量代碼和數(shù)據(jù)并不需要訪問。考慮將不會(huì)馬上執(zhí)行的代碼和數(shù)據(jù)暫時(shí)存放在外存，節(jié)省內(nèi)存空間?；舅枷耄撼绦?、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大小，操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分存在磁盤上，需要時(shí)在內(nèi)存和磁盤之間動(dòng)態(tài)對(duì)換。虛擬存儲(chǔ)器：把內(nèi)存與外存有機(jī)的結(jié)合起來(lái)使用，從而得到一個(gè)容量很大的“內(nèi)存”，這就是虛存。虛存實(shí)際上是一個(gè)地址空間。實(shí)現(xiàn)思想：當(dāng)進(jìn)程運(yùn)行時(shí)，先將一部分程序裝入內(nèi)存，另一部分暫時(shí)留在外存，當(dāng)要執(zhí)行的指令不在內(nèi)存時(shí)，由系統(tǒng)自動(dòng)完成將它們從外存調(diào)入內(nèi)存工作?；竟ぷ髟碓谶M(jìn)程開始運(yùn)行之前，不是裝入全部頁(yè)面，而是裝入一個(gè)或零個(gè)頁(yè)面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁(yè)面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁(yè)面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁(yè)面，以便裝入新的頁(yè)面。虛擬存儲(chǔ)器支持多道程序設(shè)計(jì)技術(shù)。在多道程序環(huán)境下，一個(gè)系統(tǒng)可以為每個(gè)用戶建立一個(gè)虛存，每個(gè)用戶可以在自己的地址空間內(nèi)編程?；咎卣魈摂M擴(kuò)充——不是物理上，而是邏輯上擴(kuò)充了內(nèi)存容量部分裝入——每個(gè)作業(yè)不是全部一次裝入離散分配——不必占用連續(xù)的內(nèi)存空間多次對(duì)換——所需的全部程序和數(shù)據(jù)要分成多次調(diào)入內(nèi)存一個(gè)虛存的最大容量由計(jì)算機(jī)的地址結(jié)構(gòu)確定段頁(yè)式邏輯地址結(jié)構(gòu)由三部分組成：4.2早期的存儲(chǔ)管理主要采用如下的存儲(chǔ)管理方案：?jiǎn)我贿B續(xù)分配——適用于單道程序分區(qū)分配——為滿足多道程序設(shè)計(jì)需要的一種簡(jiǎn)單的存儲(chǔ)管理技術(shù)固定式分區(qū)法可變式分區(qū)法可再定位式分區(qū)法多重分區(qū)分配分區(qū)的保護(hù)措施分區(qū)分配方案的評(píng)價(jià)一、單一的連續(xù)分配思想：?jiǎn)斡脩粝到y(tǒng)在一段時(shí)間內(nèi),只有一個(gè)進(jìn)程在內(nèi)存,故內(nèi)存分配管理十分簡(jiǎn)單,內(nèi)存利用率低。內(nèi)存分為兩個(gè)區(qū)域,一個(gè)供操作系統(tǒng)使用,一個(gè)供用戶使用。優(yōu)點(diǎn)：方法簡(jiǎn)單，易于實(shí)現(xiàn)缺點(diǎn)：僅適用于單道程序，因而不能使處理機(jī)和主存得到充分利用。二、分區(qū)分配系統(tǒng)把內(nèi)存用戶區(qū)劃分為若干分區(qū),分區(qū)大小可以相等,也可以不等。一個(gè)進(jìn)程占據(jù)一個(gè)分區(qū)。按照分區(qū)的劃分方式，可分為固定式分區(qū)、可變式分區(qū)、可再定位式分區(qū)和多重分區(qū)四種。1.固定式分區(qū)法基本思想：預(yù)先把可分配的主存儲(chǔ)器空間分割成若干個(gè)連續(xù)區(qū)域,稱為一個(gè)分區(qū);每個(gè)分區(qū)的大小可以相同也可以不同,但分區(qū)個(gè)數(shù)固定不變,每個(gè)分區(qū)的大小也固定不變，每個(gè)分區(qū)中只可裝一個(gè)作業(yè)。具體實(shí)現(xiàn)：內(nèi)存分配：用戶提出其作業(yè)所需的最大容量，然后由系統(tǒng)找到一個(gè)足夠大的空閑分區(qū)分配給它。內(nèi)存回收：很簡(jiǎn)單。管理：增加設(shè)置內(nèi)存分配表，結(jié)構(gòu)如下：缺點(diǎn)：內(nèi)存利用率不高。狀態(tài)分區(qū)號(hào)起始地址長(zhǎng)度進(jìn)程名分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)700K400K100K02.可變式分區(qū)基本思想:內(nèi)存不是預(yù)先劃分好的，而是當(dāng)作業(yè)裝入時(shí)，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來(lái)決定是否分配。若有足夠的空間，則按需要分割一部分分區(qū)給該進(jìn)程；否則令其等待主存空間?？勺兪椒謪^(qū)的使用情況，其中，陰影部分為空閑區(qū)Pa(120k)操作系統(tǒng)(a)Pa(120k)操作系統(tǒng)(b)Pb(30k)Pc(100k)1M140k0操作系統(tǒng)(c)Pb(30k)Pc(100k)270k170kPd(80k)操作系統(tǒng)(d)Pc(100k)70kPd(80k)操作系統(tǒng)(e)Pc(100k)10kPe(60k)20kPd(80k)始址長(zhǎng)度占用標(biāo)志

20k80kPd100k60kPe170k100kPc

空

……始址長(zhǎng)度占用

160k10k有效

270k730k有效空

……(a)已分配區(qū)表(b)未分配區(qū)表

可變分區(qū)分區(qū)說明表內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)1)分區(qū)說明表由兩張表格組成2)空閑區(qū)鏈將分區(qū)分配信息附加在分區(qū)中,記錄存儲(chǔ)空間的使用情況。將表格信息放在每個(gè)分區(qū)的首尾兩個(gè)字節(jié)中,利用表格自己管理自己。表格存放如下一些信息：

(1)狀態(tài)信息:“0”表示該區(qū)空閑,“1”表示已分配。

(2)該區(qū)的大小(以字或塊為單位)。

(3)指針信息:構(gòu)成空閑區(qū)鏈。狀態(tài)位

分區(qū)大?。∟+2）前向指針大小為N的已分配區(qū)或空閑區(qū)狀態(tài)位分區(qū)大?。∟+2）后向指針請(qǐng)求分配分區(qū)的算法分配算法（入口參數(shù)：申請(qǐng)長(zhǎng)度）

a.找下一個(gè)空白區(qū)：若找到，轉(zhuǎn)b，否則本次無(wú)法分配；

b.檢測(cè)空白區(qū)>=申請(qǐng)長(zhǎng)度？若是，則轉(zhuǎn)c，否則轉(zhuǎn)a；

c.修改相應(yīng)表目（空白區(qū)、已分配區(qū)）；

d.返回，返回前需給出相應(yīng)回答信息（分配的起始地址）回收分區(qū)a.檢查回收的內(nèi)容是否有鄰接區(qū)：若無(wú)，轉(zhuǎn)c，否則轉(zhuǎn)b；b.有鄰接區(qū)，判斷是上鄰接，下鄰接，還是上下鄰接，然后合并；c.修改相應(yīng)表目（空白區(qū)，已分配區(qū)）。空白區(qū)排列方法對(duì)應(yīng)的算法1）最佳適應(yīng)算法：存儲(chǔ)區(qū)（空白區(qū)）的數(shù)據(jù)結(jié)構(gòu)：空白區(qū)按其容量大小遞增連接起來(lái)，即：X1X2X3….Xn。設(shè)請(qǐng)求分配的容量為S，則從X1開始比較，直至SXi，然后，從Xi中減去S，如有剩余，則此空白區(qū)插入適當(dāng)位置，否則（S>Xn），則分配失敗。剩余空白區(qū)的處理：如果Xi-SG(參數(shù))，則Xi全部給作業(yè)，否則，Xi-S插入適當(dāng)位置。特點(diǎn)：用最小空間滿足要求缺點(diǎn)：容易產(chǎn)生許多非常小的空白區(qū)（即碎片）2）最差適應(yīng)算法空白區(qū)按容量遞減次序排列。即：x1>=x2>=...>=xn如果要求分配的容量為S，且x1>=S，則分配，否則分配失敗。特點(diǎn)：當(dāng)分割后空閑塊仍為較大空塊。缺點(diǎn)：各空白區(qū)比較均勻地減小，工作一段時(shí)間后就不能滿足對(duì)于較大空白區(qū)的分配要求。3）最先適應(yīng)算法空白區(qū)按地址大小遞增順序排列特點(diǎn)：簡(jiǎn)單、快速分配缺點(diǎn)：在低地址部分集中了許多的小空白區(qū)，因而在空白區(qū)分配時(shí)，搜索次數(shù)增加，影響了工作效率。固定式分區(qū)和可變式分區(qū)總結(jié)優(yōu)點(diǎn)：有助于多道；硬件要求少；算法簡(jiǎn)單，易于實(shí)現(xiàn)。缺點(diǎn)：1.會(huì)產(chǎn)生很多碎片，降低了存儲(chǔ)器的效率；2.分區(qū)大小受主存容量限制，無(wú)法擴(kuò)充主存容量。3.可再定位分區(qū)分配碎片問題：經(jīng)過一段時(shí)間的分配回收后,內(nèi)存中存在很多很小的空閑塊。它們每一個(gè)都很小,不足以滿足分配要求,但其總和滿足分配要求;這些空閑塊被稱為碎片。造成存儲(chǔ)資源的浪費(fèi)碎片問題的解決：緊湊技術(shù)（緊縮技術(shù),浮動(dòng)技術(shù),搬家技術(shù)）通過在內(nèi)存移動(dòng)程序,將所有小的空閑區(qū)域合并為大的空閑區(qū)域。問題:開銷大,移動(dòng)時(shí)機(jī)。

基本思想：定時(shí)的或根據(jù)一定條件將小的空白區(qū)合并成一個(gè)連續(xù)的空白區(qū)。解決程序的可再定位（浮動(dòng)）的方法：1）使用模塊裝入程序，將程序的裝配模塊重新裝入到指定位置，并從頭開始執(zhí)行。2）動(dòng)態(tài)再定位技術(shù)通過再定位寄存器實(shí)現(xiàn)動(dòng)態(tài)重定位分區(qū)分配算法

在動(dòng)態(tài)分區(qū)分配算法基礎(chǔ)上增加了緊湊功能按動(dòng)態(tài)分區(qū)分配修改有關(guān)數(shù)據(jù)結(jié)構(gòu)進(jìn)行緊湊形成連續(xù)分區(qū)修改有關(guān)數(shù)據(jù)結(jié)構(gòu)檢索空閑分區(qū)鏈空閑和>u.size?找到>u.size?返回分區(qū)號(hào)失敗返回請(qǐng)求分配u.size分區(qū)YNYN合并時(shí)機(jī)當(dāng)某個(gè)分區(qū)內(nèi)的作業(yè)一完成，立即靠攏；某一作業(yè)請(qǐng)求分區(qū)時(shí)，現(xiàn)有空白區(qū)沒有滿足的，各空白區(qū)之和可以滿足，則合并。評(píng)價(jià)優(yōu)點(diǎn)：消除碎片，便于大作業(yè)運(yùn)行，提高了存儲(chǔ)器的使用效率缺點(diǎn)：提高了成本，降低了速度；拼接時(shí)很浪費(fèi)時(shí)間4.多重分區(qū)分配

基本思想：一個(gè)作業(yè)由一些相對(duì)獨(dú)立的程序段和數(shù)據(jù)段組成，段內(nèi)在邏輯上必須是連續(xù)的，但相應(yīng)的各分區(qū)卻不要求是連續(xù)的，給一個(gè)作業(yè)分配一個(gè)以上分區(qū)評(píng)價(jià)優(yōu)點(diǎn)：存儲(chǔ)空間的利用率提高了缺點(diǎn)：硬件費(fèi)用高，管理也比較復(fù)雜5.分區(qū)的保護(hù)措施思想：為防止一個(gè)作業(yè)有意或無(wú)意地破壞操作系統(tǒng)或其他作業(yè)，應(yīng)對(duì)各分區(qū)采取保護(hù)措施，通常采用界地址寄存器（或用基址、限長(zhǎng)寄存器）的方法。優(yōu)點(diǎn)：實(shí)現(xiàn)了主存的共享，因而有助于多道程序設(shè)計(jì)，更有效地利用了處理機(jī)和I/O設(shè)備。相對(duì)分頁(yè)、分段的存儲(chǔ)管理方式，占用存儲(chǔ)容量較少，算法簡(jiǎn)單。實(shí)現(xiàn)存儲(chǔ)保護(hù)的措施也比較簡(jiǎn)單。多重分區(qū)分配方案能實(shí)現(xiàn)對(duì)子程序、數(shù)據(jù)段的共享。6.分區(qū)分配方案的評(píng)價(jià)缺點(diǎn)：主存仍不能充分利用，存在嚴(yán)重的碎片問題。不能實(shí)現(xiàn)對(duì)主存的擴(kuò)充。和單一連續(xù)分配一樣，要求一個(gè)作業(yè)在執(zhí)行之前必須全部裝入主存，因此在主存中可能包含從未使用過的信息。采用靠攏方法，雖能解決碎片問題，但有時(shí)需移動(dòng)大量信息，從而損失了處理機(jī)時(shí)間。除多重分區(qū)外，幾個(gè)并行作業(yè)之間不能共享存入主存的單一信息副本（如共用子程序，數(shù)據(jù)段等）。4.3分頁(yè)存儲(chǔ)管理一、分頁(yè)原理1.目的：解決系統(tǒng)里出現(xiàn)的碎片問題。2.原理：(1)把目標(biāo)程序按邏輯地址劃分成大小相等的部分,稱為頁(yè)面(邏輯頁(yè))。(2)把物理地址空間（貯存）劃分成和頁(yè)面大小相同的片，稱為物理塊。(3)把主存以塊為單位分給用戶作業(yè)。

頁(yè)號(hào)P頁(yè)內(nèi)位移量W0111223編號(hào)0~4095相對(duì)地址0~4095邏輯地址用戶程序的劃分是由系統(tǒng)自動(dòng)完成的,對(duì)用戶是透明的。一頁(yè)的大小一般為2的整數(shù)次冪,地址的高位部分為頁(yè)號(hào),低位部分為頁(yè)內(nèi)地址(頁(yè)內(nèi)位移量)3.地址映射：建立頁(yè)面變換表PMT（簡(jiǎn)稱頁(yè)表）,給出邏輯地址頁(yè)號(hào)和內(nèi)存物理塊號(hào)對(duì)應(yīng)的關(guān)系,通過它進(jìn)行地址映射。0頁(yè)1頁(yè)2頁(yè)3頁(yè)4頁(yè)5頁(yè)6頁(yè)0123456進(jìn)程的地址空間塊號(hào)頁(yè)號(hào)頁(yè)表主存中頁(yè)框（物理塊）存取控制二、地址變換機(jī)構(gòu)1、動(dòng)態(tài)地址變換機(jī)構(gòu)DAT例：指令LR1，D2(X2，B2）

指令格式為L(zhǎng)R1X2B2D207811121516192031該指令的有效地址為24位。

每個(gè)作業(yè)都有一個(gè)頁(yè)面變換表PMT，通常PMT放在OS的一個(gè)工作區(qū)中，由頁(yè)面變換地址寄存器PMTAR指出作業(yè)的起始地址。P112圖4.16PMTAR、PMT、頁(yè)面和塊之間的關(guān)系分頁(yè)系統(tǒng)地址變換機(jī)構(gòu)b頁(yè)號(hào)塊號(hào)越界中斷頁(yè)表長(zhǎng)度l比較P>=l頁(yè)表始址p0+頁(yè)號(hào)p頁(yè)內(nèi)地址dbd物理地址寄存器頁(yè)表寄存器邏輯地址頁(yè)表01..0080034C82AC4C8比較0123+2AC2、高速頁(yè)面變換寄存器為了實(shí)現(xiàn)從作業(yè)地址空間到物理地址空間的變換，采用硬件實(shí)現(xiàn)的高速寄存器來(lái)實(shí)現(xiàn)。將一個(gè)作業(yè)分成若干頁(yè)，運(yùn)行時(shí)將頁(yè)號(hào)與塊號(hào)的對(duì)應(yīng)關(guān)系存儲(chǔ)到高速寄存器中。3、聯(lián)想寄存器（快表）（1）由于在DAT中，PMT存放于主存，由OS來(lái)管理，作業(yè)執(zhí)行時(shí)每條指令都要進(jìn)行地址變換。因此每條指令必須兩次訪問存儲(chǔ)器：一次是將頁(yè)號(hào)變?yōu)閴K號(hào)，另一次才是真正的取數(shù)或指令。因此增加了指令執(zhí)行的時(shí)間。（2）聯(lián)想寄存器它是介于內(nèi)存與寄存器之間的存儲(chǔ)機(jī)制,為加快地址變換速度而設(shè)置;它的訪問速度比頁(yè)表快一個(gè)數(shù)量級(jí),它保存著正在運(yùn)行進(jìn)程的頁(yè)表的子集(部分表項(xiàng))。實(shí)現(xiàn)上采用“雙管齊下”的方法。存放當(dāng)前頻繁訪問的那些頁(yè)表項(xiàng),表項(xiàng)含:1)頁(yè)號(hào)2)頁(yè)在內(nèi)存的塊號(hào)3)標(biāo)識(shí)(狀態(tài))位4)淘汰位b頁(yè)號(hào)塊號(hào)越界中斷頁(yè)表長(zhǎng)度l比較P>=lpb快表頁(yè)號(hào)塊號(hào)頁(yè)表始址p0+頁(yè)號(hào)p頁(yè)內(nèi)地址dbd物理地址寄存器頁(yè)表寄存器邏輯地址地址映射機(jī)制頁(yè)表01...

CPU給出有效邏輯地址后,自動(dòng)將頁(yè)號(hào)與快表中的所有頁(yè)號(hào)進(jìn)行比較有則直接讀出對(duì)應(yīng)的物理塊號(hào)送物理地址寄存器中無(wú)則繼續(xù)按頁(yè)號(hào)檢索頁(yè)表,在頁(yè)表中讀出物理塊號(hào)送物理地址寄存器中并同時(shí)修改快表,使快表中始終保持著最近頻繁訪問的頁(yè)信息。實(shí)際上快表和頁(yè)表檢索同時(shí)進(jìn)行快表查到則終止檢索頁(yè)表,沒查到則繼續(xù)檢索頁(yè)表上述過程全部由硬件實(shí)現(xiàn),并行性好速度快。

CPU給出有效邏輯地址后,自動(dòng)將頁(yè)號(hào)與快表中的所有頁(yè)號(hào)進(jìn)行比較,有則直接讀出對(duì)應(yīng)的物理塊號(hào)送物理地址寄存器中,無(wú)則繼續(xù)按頁(yè)號(hào)檢索頁(yè)表,在頁(yè)表中讀出對(duì)應(yīng)的物理塊號(hào)送物理地址寄存器中,并同時(shí)修改快表,使快表中始終保持著最近頻繁訪問的頁(yè)信息。實(shí)際上快表和頁(yè)表檢索是同時(shí)進(jìn)行的,快表查到則終止檢索頁(yè)表,沒查到則繼續(xù)檢索頁(yè)表。上述過程全部由硬件實(shí)現(xiàn),并行性好速度快。其中:物理塊號(hào)b的地址=頁(yè)表始址+頁(yè)號(hào)*頁(yè)表項(xiàng)長(zhǎng)度物理地址=物理塊號(hào)*頁(yè)的大小+頁(yè)內(nèi)地址快表的命中率一般為：80%~90%三、分頁(yè)存儲(chǔ)管理算法1、數(shù)據(jù)結(jié)構(gòu)作業(yè)表（JT）：整個(gè)系統(tǒng)一張作業(yè)編號(hào)頁(yè)表的長(zhǎng)度頁(yè)表的起始地址狀態(tài)

存儲(chǔ)分塊表（MBT）：整個(gè)系統(tǒng)一張

塊號(hào)狀態(tài)該表中一個(gè)表目對(duì)應(yīng)一個(gè)存儲(chǔ)塊，記錄了該塊的狀態(tài)：已分配或空閑。頁(yè)面變換表（PMT）：每個(gè)作業(yè)一張2、實(shí)現(xiàn)過程由作業(yè)調(diào)度程序決定哪個(gè)作業(yè)應(yīng)該得到主存；由分頁(yè)存儲(chǔ)管理程序來(lái)檢查是否能滿足作業(yè)的要求。假如滿足：給出回答信息，填寫頁(yè)表和作業(yè)表，修改存儲(chǔ)分塊表。如不滿足，給出回答信息，本次無(wú)法分配；作業(yè)完成后，修改存儲(chǔ)分塊表、作業(yè)表，刪除頁(yè)面變換表。四、分頁(yè)存儲(chǔ)管理方案的評(píng)價(jià)1、采用動(dòng)態(tài)地址變換會(huì)增加計(jì)算機(jī)成本和降低處理機(jī)的速度；2、各種表格要占用一定容量的主存空間，同時(shí)要花費(fèi)一部分處理機(jī)時(shí)間來(lái)建立和管理表格；3、作業(yè)的最后一段都有不能充分利用的空白區(qū)；4、存儲(chǔ)擴(kuò)充問題未得到解決。4.4請(qǐng)求分頁(yè)存儲(chǔ)管理目的：進(jìn)一步發(fā)揮機(jī)器的效率，實(shí)現(xiàn)虛擬存儲(chǔ)，擴(kuò)充存儲(chǔ)空間，引進(jìn)了請(qǐng)求分頁(yè)技術(shù)，它為用戶提供的虛擬存儲(chǔ)空間遠(yuǎn)比主存的存儲(chǔ)空間大?；驹恚涸谶M(jìn)程開始運(yùn)行之前,不是裝入全部頁(yè)面,而是裝入一個(gè)或零個(gè)頁(yè)面,之后根據(jù)進(jìn)程運(yùn)行的需要,動(dòng)態(tài)裝入其它頁(yè)面;當(dāng)內(nèi)存空間已滿,而又需要裝入新的頁(yè)面時(shí),則根據(jù)某種算法淘汰某個(gè)頁(yè)面,以便裝入新的頁(yè)面。

虛頁(yè)：作業(yè)地址空間劃分的頁(yè)實(shí)頁(yè)：主存中的頁(yè)一、討論問題1、如果沒有將一個(gè)作業(yè)全部放入主存，那么該作業(yè)是否能開始運(yùn)行并運(yùn)行一段時(shí)間？3、若系統(tǒng)已發(fā)現(xiàn)某虛頁(yè)不在實(shí)存，就應(yīng)將其裝入實(shí)存。那么從何處裝入，裝入到何處，如果實(shí)存空間已滿怎么辦？2、作業(yè)運(yùn)行了一段時(shí)間之后，要訪問沒有裝入的頁(yè)面，系統(tǒng)如何發(fā)現(xiàn)該頁(yè)不在主存？二、硬件支持及工作過程1、頁(yè)表機(jī)制內(nèi)存塊號(hào)狀態(tài)位訪問位修改位外存地址頁(yè)號(hào)狀態(tài)位P：表示該頁(yè)是在內(nèi)存還是在外存訪問位：記錄該頁(yè)在一段時(shí)間內(nèi)被訪問的次數(shù)修改位：查看此頁(yè)是否在內(nèi)存中被修改過...44KX40KX36K532KX28KX24K320K416K012KX8K14K20K虛地址空間物理地址空間}虛頁(yè)頁(yè)框

20K

16K

12K

8K

4K

0K...24K2、缺頁(yè)中斷機(jī)構(gòu)在地址映射過程中,在頁(yè)表中發(fā)現(xiàn)所要訪問的頁(yè)不在內(nèi)存,則產(chǎn)生缺頁(yè)中斷。操作系統(tǒng)接到此中斷信號(hào)后,就調(diào)出缺頁(yè)中斷處理程序,根據(jù)頁(yè)表中給出的外存地址,將該頁(yè)調(diào)入內(nèi)存,使進(jìn)程繼續(xù)運(yùn)行下去。如果內(nèi)存中有空閑塊,則分配一頁(yè)將新調(diào)入頁(yè)裝入內(nèi)存,并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號(hào)。若此時(shí)內(nèi)存中沒有空閑塊,則要淘汰某頁(yè),若該頁(yè)在內(nèi)存期間被修改過,則要將其寫回外存。影響缺頁(yè)次數(shù)的因素(1)分配給進(jìn)程的物理頁(yè)面數(shù)(2)頁(yè)面本身的大小(3)程序的編制方法(4)頁(yè)面淘汰算法三、頁(yè)面置換算法1、先進(jìn)先出算法（FIFO）基本思想：總是淘汰那些駐留在主存時(shí)間最長(zhǎng)的頁(yè)面。思想基礎(chǔ)：最先調(diào)入主存的頁(yè)面比最近調(diào)入主存的頁(yè)面不再訪問的可能性大。實(shí)現(xiàn)：方法1.建立隊(duì)列表和替換指針設(shè)分配給一個(gè)作業(yè)的實(shí)頁(yè)數(shù)為m，則要建立一個(gè)由m個(gè)元素組成的隊(duì)列表和一個(gè)替換指針。

Q(0),Q(1),…Q(m-1)其中Q(i)是作業(yè)的虛頁(yè)號(hào)。實(shí)現(xiàn)過程：為分配給作業(yè)的存儲(chǔ)塊建立一個(gè)隊(duì)列；給該隊(duì)列建立一個(gè)指針，指針指向最老的頁(yè)；若需淘汰，則淘汰掉指針?biāo)傅捻?yè)；新頁(yè)放在淘汰掉的位置，指針下移；當(dāng)指針指向最底層時(shí)，移上去再去置換。方法2.

利用存儲(chǔ)分塊表，按照頁(yè)的順序建立鏈表指針，指向緊跟它之后調(diào)入主存的頁(yè)對(duì)應(yīng)的塊號(hào)；建立替換指針，指向最老的一頁(yè)；按鏈表指針的順序逐個(gè)替換；置換后修改指針。算法評(píng)價(jià)：適用于線性順序訪問地址空間的情況；常用的頁(yè)容易被置換出去。2、最近最久未用置換算法（LRU）

思想：如果某一頁(yè)被訪問了，可能馬上還要被訪問；長(zhǎng)時(shí)間不被訪問的頁(yè)，最近也不會(huì)訪問。實(shí)現(xiàn)：（1）對(duì)每一個(gè)存儲(chǔ)塊增加一個(gè)引用位，當(dāng)這一頁(yè)被訪問時(shí)，引用位由硬件置“1”；（2）給存儲(chǔ)塊再增加一個(gè)數(shù)據(jù)項(xiàng)，記錄每一頁(yè)從上次被訪問以來(lái)的時(shí)間t；（3）淘汰時(shí)選擇被訪問以來(lái)時(shí)間最長(zhǎng)的頁(yè)淘汰。評(píng)價(jià)：常用的頁(yè)不容易被置換出去，適用于各種類型程序；周期t過一段時(shí)間被計(jì)算一次，耽誤時(shí)間，增加成本。3、LRU近似算法實(shí)現(xiàn)：給存儲(chǔ)分塊表MBT增加一個(gè)引用位，當(dāng)這一頁(yè)被訪問時(shí)，引用位由硬件置“1”；管理軟件周期性地將引用位逐個(gè)置“0”；淘汰時(shí)選擇引用位為0的頁(yè)淘汰，碰到引用位為1的，置為0。評(píng)價(jià)：比LRU算法簡(jiǎn)單；周期選擇困難。4、其它算法隨機(jī)算法（RAND)、近期最少使用算法（LFU）、最優(yōu)替換算法（OPT）等。例1：設(shè)頁(yè)面走向?yàn)镻=4，3，2，1，4，3，5，4，3，2，1，5，試寫出主存容量M分別為3和4時(shí)，采用的算法分別為FIFO和LRU時(shí)的缺頁(yè)率和缺頁(yè)中斷次數(shù)，并比較結(jié)果。例2：某虛擬存儲(chǔ)器的用戶編程空間共64KB，內(nèi)存為16KB。假定每一頁(yè)大小為１K,某時(shí)刻一用戶頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面的頁(yè)號(hào)和物理塊號(hào)的對(duì)照表如下： 頁(yè)號(hào) 物理塊號(hào)

0 5 1 10 2 4 3 7則邏輯地址0A5C（H）所對(duì)應(yīng)的物理地址是什么？答：邏輯地址0A5CH所對(duì)應(yīng)的二進(jìn)制表示形式是：

0000101001011100

，由于1K=210，下劃線部分前的編碼為000010，表示該邏輯地址對(duì)應(yīng)的頁(yè)號(hào)為2,查頁(yè)表，得到物理塊號(hào)是4（十進(jìn)制），即物理塊地址為：

01000000000000

，拼接塊內(nèi)地址1001011100，得 01001001011100，即125C（H）。

四、性能分析1、抖動(dòng)在虛存中,頁(yè)面在內(nèi)存與外存之間頻繁調(diào)度,以至于調(diào)度頁(yè)面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多,此時(shí)系統(tǒng)效率急劇下降,甚至導(dǎo)致系統(tǒng)崩潰,這種現(xiàn)象為抖動(dòng)。產(chǎn)生原因：頁(yè)面淘汰算法不合理分配給進(jìn)程的工作集窗口尺寸太小出現(xiàn):CPU利用率下降→調(diào)入新的進(jìn)程→從其它進(jìn)程獲得物理塊→缺頁(yè)中斷次數(shù)增加→

CPU利用率進(jìn)一步下降的惡性循環(huán)2、程序設(shè)計(jì)的質(zhì)量主要指程序的局部性程度3、設(shè)計(jì)請(qǐng)求分頁(yè)存儲(chǔ)系統(tǒng)時(shí)，頁(yè)面大小也是一個(gè)重要參數(shù)4、缺頁(yè)中斷與存儲(chǔ)容量有關(guān)5、運(yùn)行程序與頁(yè)面置換算法有關(guān)五、請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)的評(píng)價(jià)：優(yōu)點(diǎn)：提供了多個(gè)大容量的虛存，作業(yè)地址空間不再受主存容量的限制；更有效的利用了主存；更加有利于多道程序的運(yùn)行，提高了系統(tǒng)效率；方便了用戶，尤其是大用戶作業(yè)。缺點(diǎn)：為處理缺頁(yè)中斷，增加了處理機(jī)時(shí)間的開銷；系統(tǒng)抖動(dòng)；為防止抖動(dòng)，可能會(huì)增加系統(tǒng)的復(fù)雜性。4.5分段存儲(chǔ)管理一、分段原理

1.用戶程序劃分程序的地址空間按自身的邏輯關(guān)系劃分為若干個(gè)段,每個(gè)段定義了一組邏輯信息。例如:主程序段Main,子程序段X,子程序段Y,數(shù)據(jù)段D,堆棧段S等;每個(gè)段都有自己的名字,可用段號(hào)來(lái)代替段名,段號(hào)從0開始編號(hào)。每個(gè)段內(nèi)都也從0開始編址,段內(nèi)地址空間是連續(xù)的,各段的長(zhǎng)度不等。整個(gè)程序的地址空間是二維的,段號(hào)維和段內(nèi)地址維。程序邏輯地址:段號(hào)段內(nèi)地址...0S堆棧段[S]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N數(shù)據(jù)段[D]12345...例如：2.內(nèi)存物理空間的劃分內(nèi)存空間被動(dòng)態(tài)的劃分為若干個(gè)長(zhǎng)度不相同的物理段,每個(gè)物理段由起始地址和長(zhǎng)度確定。3.內(nèi)存分配

以段為單位分配內(nèi)存,每個(gè)段在內(nèi)存中占據(jù)連續(xù)空間(內(nèi)存隨機(jī)分割,需要多少分配多少),但各段之間可以不連續(xù)存放。4.通過段表進(jìn)行地址映射段表記錄各段的首(地)址和長(zhǎng)度.....S0RD0NY0LX0PM0K邏輯段號(hào)進(jìn)程1的地址空間PKRLN主存K320kP150kL600kN800kR500k長(zhǎng)度段首址操作系統(tǒng)100k320k500k600k800k150k段表二、管理1、段變換表SMT：每個(gè)作業(yè)一張段號(hào)容量存取權(quán)限狀態(tài)起始地址訪問位修改位增補(bǔ)位2、內(nèi)存的分配算法：首先適配；最佳適配；最壞適配3、地址變換機(jī)制相聯(lián)寄存器—快表(并行快速查找)段表長(zhǎng)度Cl段表始址Cb+段號(hào)S位移量d比較b+d比較段表段號(hào)

段長(zhǎng)基址S>=Cl快表物理地址寄存器控制寄存器有效邏輯地址lbSlbd>=l地址映射及存儲(chǔ)保護(hù)機(jī)制地址越界地址越界01...三、分頁(yè)和分段的主要區(qū)別頁(yè)是物理單位,分頁(yè)是為了消減內(nèi)存的外零頭以提高內(nèi)存的利用率,僅僅是系統(tǒng)的需要。段是邏輯單位,分段是為了更好地滿足用戶需要。頁(yè)的大小固定且由系統(tǒng)確定,分頁(yè)由硬件實(shí)現(xiàn)。段的長(zhǎng)度不固定,由編譯時(shí)根據(jù)程序信息來(lái)劃分。分頁(yè)的作業(yè)地址空間是一維的線性空間。標(biāo)識(shí)地址時(shí),只需給出一個(gè)邏輯地址。分段的作業(yè)地址空間是二維的,標(biāo)識(shí)地址時(shí),必須給出段名和段內(nèi)地址