第四章存儲要點課件

第四章存儲管理

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

1.存儲分配問題

2.地址再定位

3.存儲保護

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

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

邏輯地址

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

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

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

=有效地址

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

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

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

20k80kPd100k60kPe170k100kPc

空

……始址長度占用

160k10k有效

270k730k有效空

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

可變分區(qū)分區(qū)說明表內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)1)分區(qū)說明表由兩張表格組成2)空閑區(qū)鏈將分區(qū)分配信息附加在分區(qū)中,記錄存儲空間的使用情況。將表格信息放在每個分區(qū)的首尾兩個字節(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ū)的算法分配算法（入口參數(shù)：申請長度）

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

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

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

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

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

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

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

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

指令格式為LR1X2B2D207811121516192031該指令的有效地址為24位。

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

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

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

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

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

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

20K

16K

12K

8K

4K

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

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

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

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

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

0000101001011100

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

01000000000000

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

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

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

1.用戶程序劃分程序的地址空間按自身的邏輯關(guān)系劃分為若干個段,每個段定義了一組邏輯信息。例如:主程序段Main,子程序段X,子程序段Y,數(shù)據(jù)段D,堆棧段S等;每個段都有自己的名字,可用段號來代替段名,段號從0開始編號。每個段內(nèi)都也從0開始編址,段內(nèi)地址空間是連續(xù)的,各段的長度不等。整個程序的地址空間是二維的,段號維和段內(nèi)地址維。程序邏輯地址:段號段內(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)存空間被動態(tài)的劃分為若干個長度不相同的物理段,每個物理段由起始地址和長度確定。3.內(nèi)存分配

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

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