第4章存儲(chǔ)管理1

1、第四章第四章 存儲(chǔ)器管理存儲(chǔ)器管理 4.1 4.1 程序的裝入和鏈接程序的裝入和鏈接 4.2 4.2 連續(xù)分配方式連續(xù)分配方式 4.3 4.3 基本分頁存儲(chǔ)管理方式基本分頁存儲(chǔ)管理方式 4.4 4.4 基本分段存儲(chǔ)管理方式基本分段存儲(chǔ)管理方式 4.5 4.5 虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念 4.6 4.6 請求分頁存儲(chǔ)管理方式請求分頁存儲(chǔ)管理方式 4.7 4.7 頁面置換算法頁面置換算法 4.8 4.8 請求分段存儲(chǔ)管理方式請求分段存儲(chǔ)管理方式 地址映射地址映射Load A 200 3456 。 。1200物理地址空間物理地址空間Load A data1data1 3456源程序源程

2、序Load A 200 34560100200編譯編譯連接連接邏輯地址空間邏輯地址空間BA=100003456.LOAD A 200.0100200300.LOAD A 2003456110012001300200VR+1000BR4.1 程序的裝入和鏈接程序的裝入和鏈接 圖 4-1 對用戶程序的處理步驟 庫鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存4.1.1 程序的裝入程序的裝入1. 絕對裝入方式絕對裝入方式(Absolute Loading Mode) 程序中所使用的絕對地址，既可在編譯或匯編時(shí)給出， 也可由程序員直接賦予。 但在由程序員直接給出絕對地址時(shí)， 不僅

3、要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時(shí)，再將這些符號地址轉(zhuǎn)換為絕對地址。 2. 可重定位裝入方式可重定位裝入方式(Relocation Loading Mode) 圖 4-2 作業(yè)裝入內(nèi)存時(shí)的情況 LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作業(yè)地址空間內(nèi)存空間3. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式動(dòng)態(tài)運(yùn)行時(shí)裝入方式(Denamle Run-time Loading) 動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入

4、模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此， 裝入內(nèi)存后的所有地址都仍是相對地址。 4.1.2 程序的鏈接程序的鏈接 1. 靜態(tài)鏈接方式靜態(tài)鏈接方式(Static Linking) 圖 4-3 程序鏈接示意圖 模塊 ACALL B；Return；0L1模塊 BCALL C；Return；0M1模塊 CReturn；0N10模塊 AJSR“L”Return；L1模塊 BJSR“LM”Return；LLM1LMLMN1模塊 CReturn；(a) 目標(biāo)模塊(b) 裝入模塊 在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)問題： (1) 對相對地址進(jìn)行

5、修改。 (2) 變換外部調(diào)用符號。 2. 裝入時(shí)動(dòng)態(tài)鏈接裝入時(shí)動(dòng)態(tài)鏈接(Loadtime Dynamic Linking) 裝入時(shí)動(dòng)態(tài)鏈接方式有以下優(yōu)點(diǎn)： 便于修改和更新。 (2) 便于實(shí)現(xiàn)對目標(biāo)模塊的共享。 3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接(Run-time Dynamic Linking) 近幾年流行起來的運(yùn)行時(shí)動(dòng)態(tài)鏈接方式，是對上述在裝入時(shí)鏈接方式的一種改進(jìn)。這種鏈接方式是將對某些模塊的鏈接推遲到執(zhí)行時(shí)才執(zhí)行，亦即，在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該模塊并將之裝入內(nèi)存， 把它鏈接到調(diào)用者模塊上。凡在執(zhí)行過程中未被用到的目標(biāo)模塊，都不會(huì)被調(diào)入內(nèi)存和被鏈接

6、到裝入模塊上，這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。 4.2 連續(xù)分配方式連續(xù)分配方式4.2.1 單一連續(xù)分配單一連續(xù)分配 這是最簡單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。采用這種存儲(chǔ)管理方式時(shí)，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間， 提供給用戶使用。 4.2.2 固定分區(qū)分配固定分區(qū)分配 1. 劃分分區(qū)的方法劃分分區(qū)的方法 分區(qū)大小相等， 即使所有的內(nèi)存分區(qū)大小相等。 (2) 分區(qū)大小不等。 2. 內(nèi)存分配內(nèi)存分配 圖 4-4 固定分區(qū)使用表 4.2.3 動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)

7、分區(qū)分配 1. 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu) 空閑分區(qū)表。 (2) 空閑分區(qū)鏈。 圖 4-5 空閑鏈結(jié)構(gòu) 前向指針N20N個(gè)字節(jié)可用后向指針N202. 分區(qū)分配算法分區(qū)分配算法 首次適應(yīng)算法FF。 (2) 循環(huán)首次適應(yīng)算法，該算法是由首次適應(yīng)算法演變而成的。(3) 最佳適應(yīng)算法。(4) 最壞適應(yīng)算法 。3. 分區(qū)分配操作分區(qū)分配操作 1) 分配內(nèi)存 從頭開始查表檢索完否？m.sizeu.size?m.sizeu.sizesize?從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)分配給請求者修改有關(guān)數(shù)據(jù)結(jié)構(gòu)返回返回繼續(xù)檢索下一個(gè)表項(xiàng)將該分區(qū)從鏈中移出YNNYYN圖 4-6 內(nèi)存分配流程2

8、) 回收內(nèi)存 圖 4-7 內(nèi)存回收時(shí)的情況 4.2.4 可重定位分區(qū)分配可重定位分區(qū)分配 1. 動(dòng)態(tài)重定位的引入動(dòng)態(tài)重定位的引入 圖 4-8 緊湊的示意 操作系統(tǒng)用戶程序1用戶程序310 KB30 KB用戶程序614 KB用戶程序926 KB操作系統(tǒng)用戶程序1用戶程序3用戶程序6用戶程序980 KB(a) 緊湊前(b) 緊湊后2. 動(dòng)態(tài)重定位的實(shí)現(xiàn)動(dòng)態(tài)重定位的實(shí)現(xiàn) 圖 4-9 動(dòng)態(tài)重定位示意圖 LOAD1,25003650100250050002500相對地址10000重定位寄存器LOAD1,250036510000101001250015000作業(yè)J處理機(jī)一側(cè) 存儲(chǔ)器一側(cè)主存3. 動(dòng)態(tài)重定位

9、分區(qū)分配算法動(dòng)態(tài)重定位分區(qū)分配算法 圖 4-10 動(dòng)態(tài)分區(qū)分配算法流程圖 請求分配u.size分區(qū)檢索空閑分區(qū)鏈(表)找到大于u.size的可用區(qū)否?按動(dòng)態(tài)分區(qū)方式進(jìn)行分配修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)返回分區(qū)號及首批空閑分區(qū)總和u.size?進(jìn)行緊湊形成連續(xù)空閑區(qū)修改有關(guān)的數(shù)據(jù)結(jié)構(gòu)否是無法分配返回否4.2.5 對換對換(Swapping) 1. 對換的引入對換的引入 所謂“對換”， 是指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)，調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)，調(diào)入內(nèi)存。對換是提高內(nèi)存利用率的有效措施。 2. 對換空間的管理對換空間的管理

10、為了能對對換區(qū)中的空閑盤塊進(jìn)行管理，在系統(tǒng)中應(yīng)配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，以記錄外存的使用情況。其形式與內(nèi)存在動(dòng)態(tài)分區(qū)分配方式中所用數(shù)據(jù)結(jié)構(gòu)相似，即同樣可以用空閑分區(qū)表或空閑分區(qū)鏈。在空閑分區(qū)表中的每個(gè)表目中應(yīng)包含兩項(xiàng)， 即對換區(qū)的首址及其大小，它們的單位是盤塊號和盤塊數(shù)。 3. 進(jìn)程的換出與換入進(jìn)程的換出與換入 (1) 進(jìn)程的換出。 每當(dāng)一進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等情況發(fā)生時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換出。 其過程是：系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進(jìn)程作為換出進(jìn)程，然后啟動(dòng)盤塊，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送過程未出現(xiàn)錯(cuò)誤，便可回收該進(jìn)程所占用的內(nèi)

11、存空間，并對該進(jìn)程的進(jìn)程控制塊做相應(yīng)的修改。 (2) 進(jìn)程的換入。 系統(tǒng)應(yīng)定時(shí)地查看所有進(jìn)程的狀態(tài)，從中找出“就緒”狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間(換出到磁盤上)最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn)程或無可換出的進(jìn)程為止。 4.3 基本分頁存儲(chǔ)管理方式基本分頁存儲(chǔ)管理方式 4.3.1 頁面與頁表頁面與頁表 1. 頁面頁面 1) 頁面和物理塊 分頁存儲(chǔ)管理，是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁面或頁，并為各頁加以編號，從0開始，如第0頁、第1頁等。相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個(gè)存儲(chǔ)塊，稱為(物理)塊或頁框(frame)， 也同樣為它們加以編

12、號，如0塊、1塊等等。在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干個(gè)頁分別裝入到多個(gè)可以不相鄰接的物理塊中。由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內(nèi)碎片”。 2) 頁面大小 在分頁系統(tǒng)中的頁面其大小應(yīng)適中。頁面若太小，一方面雖然可使內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間， 有利于提高內(nèi)存利用率，但另一方面也會(huì)使每個(gè)進(jìn)程占用較多的頁面，從而導(dǎo)致進(jìn)程的頁表過長，占用大量內(nèi)存； 此外，還會(huì)降低頁面換進(jìn)換出的效率。然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進(jìn)換出的速度，但卻又會(huì)使頁內(nèi)碎片增大。因此，頁面的大小應(yīng)選擇得適中，且頁面大小應(yīng)是2的冪，通常為51

13、2 B8 KB。 2. 地址結(jié)構(gòu)地址結(jié)構(gòu) 分頁地址中的地址結(jié)構(gòu)如下： 3112110 對某特定機(jī)器，其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內(nèi)地址d可按下式求得： MODLAdLAINTP3. 頁表頁表 圖 4-11 頁表的作用 用戶程序0 頁1 頁2 頁3 頁4 頁5 頁n 頁頁表頁號塊號02132638495內(nèi)存0123456789104.3.2 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 1. 基本的地址變換機(jī)構(gòu)基本的地址變換機(jī)構(gòu) 圖 4-12 分頁系統(tǒng)的地址變換機(jī)構(gòu) 頁表寄存器頁表始址頁表長度頁號(3)頁內(nèi)地址邏輯地址L越界中斷1塊號b頁表頁號012物理地址3

14、2. 具有快表的地址變換機(jī)構(gòu)具有快表的地址變換機(jī)構(gòu) 圖 4-13 具有快表的地址變換機(jī)構(gòu) 頁表寄存器頁表始址頁表長度頁號頁內(nèi)地址邏輯地址L越界中斷塊號b頁表頁號頁號輸入寄存器塊號bb快表d物理地址4.3.3 兩級和多級頁表兩級和多級頁表 現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。例如，對于一個(gè)具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4 KB即212 B，則在每個(gè)進(jìn)程頁表中的頁表項(xiàng)可達(dá)1兆個(gè)之多。又因?yàn)槊總€(gè)頁表項(xiàng)占用一個(gè)字節(jié)， 故每個(gè)進(jìn)程僅僅其頁表就要占用4 KB的內(nèi)存空間，而且還要求是連續(xù)的。 可以采用

15、這樣兩個(gè)方法來解決這一問題： 采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題： 只將當(dāng)前需要的部分頁表項(xiàng)調(diào)入內(nèi)存， 其余的頁表項(xiàng)仍駐留在磁盤上，需要時(shí)再調(diào)入。 1. 兩級頁表兩級頁表(Two-Level Page Table) 邏輯地址結(jié)構(gòu)可描述如下： 圖 4-14 兩級頁表結(jié)構(gòu) 101110780121742n第0頁頁表1460121023第1頁頁表114115011023外部頁表012345671141151468第n頁頁存空間圖 4-15 具有兩級頁表的地址變換機(jī)構(gòu) 外部頁號P1P2外部頁內(nèi)地址頁內(nèi)地址d邏輯地址外部頁表寄存器外部頁表db頁表頁表物理地

16、址 2. 多級頁表多級頁表 對于32位的機(jī)器，采用兩級頁表結(jié)構(gòu)是合適的；但對于64位的機(jī)器，如果頁面大小仍采用4 KB即212 B，那么還剩下52位， 假定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號。此時(shí)在外層頁表中可能有4096 G個(gè)頁表項(xiàng)， 要占用16384 GB的連續(xù)內(nèi)存空間。 必須采用多級頁表，將外層頁表再進(jìn)行分頁，也是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關(guān)系。 對于64位的計(jì)算機(jī)，如果要求它能支持2(=1844744 TB)規(guī)模的物理存儲(chǔ)空間，則即使是采用三級頁表結(jié)構(gòu)也是難以辦到的；而在當(dāng)前的實(shí)際應(yīng)用中也無此必要。例

17、：設(shè)虛地址為(357101)8 每一塊為128字節(jié)12827(357101)8(011, 101, 111, 00 1, 000, 001)21 6 74101偏移為(101)8, 頁號為(1674)8塊號由頁表指定，偏移不變4.4 基本分段存儲(chǔ)管理方式基本分段存儲(chǔ)管理方式 4.4.1 分段存儲(chǔ)管理方式的引入分段存儲(chǔ)管理方式的引入 引入分段存儲(chǔ)管理方式， 主要是為了滿足用戶和程序員的下述一系列需要： 1) 方便編程 2) 信息共享 3) 信息保護(hù) 4) 動(dòng)態(tài)增長 5) 動(dòng)態(tài)鏈接 4.4.2 分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理 1. 分段分段 分段地址中的地址具有如下結(jié)構(gòu)： 31 16 15

18、02. 段表段表 圖 4-16 利用段表實(shí)現(xiàn)地址映射 作業(yè)空間(MAIN)0030K(X)1020K(D)2015K(S)3010K30K20K15K10K40K80K120K150K段長基址段號(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表內(nèi)存空間0123控制寄存器段表始址段表長度2100段號S越界1 K段長600段號01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址圖 4-17 分段系統(tǒng)的地址變換過程 3. 地址變換機(jī)構(gòu) 4. 分頁和分段的主要區(qū)別分頁和分段的主要區(qū)別 (1) 頁是信息

19、的物理單位，分頁是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭， 提高內(nèi)存的利用率?；蛘哒f， 分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對完整的信息。 分段的目的是為了能更好地滿足用戶的需要。 (2) 頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機(jī)器硬件實(shí)現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面；而段的長度卻不固定， 決定于用戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。 (3) 分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個(gè)記憶符，即可表示一個(gè)地址； 而分段的作業(yè)地址空間則是二

20、維的，程序員在標(biāo)識一個(gè)地址時(shí)，既需給出段名， 又需給出段內(nèi)地址。 4.4.3 信息共享信息共享 ed 1ed 2ed 40data 1data 10進(jìn)程12122606170頁表ed 1ed 2ed 40data 1data 10進(jìn)程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180頁表圖 4-18 分頁系統(tǒng)中共享editor的示意圖圖 4-19 分段系統(tǒng)中共享editor的示意圖 editor進(jìn)程1data 1進(jìn)程2editordata 2段表段長基址16080402401608040380editordat

21、a 1data 2802402803804204.4.4 段頁式存儲(chǔ)管理方式段頁式存儲(chǔ)管理方式 1. 基本原理基本原理 圖 4-20 作業(yè)地址空間和地址結(jié)構(gòu) 04K8K12K15K16K子 程 序 段04K8K數(shù) 據(jù) 段04K8K10K12K(a)段 號 (S)段 內(nèi) 頁 號 (P)段 內(nèi) 地 址 (W)(b)主 程 序 段圖 4-21 利用段表和頁表實(shí)現(xiàn)地址映射 段號狀態(tài)頁表大小頁表始址0111213041頁號狀態(tài)存儲(chǔ)塊#0111213041操作系統(tǒng)主存頁表段表段表大小段表始址段表寄存器2. 地址變換過程地址變換過程 圖 4-22 段頁式系統(tǒng)中的地址變換機(jī)構(gòu) 段表寄存器段表始址段表長度段號S

22、頁號P段超長段表0123頁內(nèi)地址頁表0123b塊號 b塊內(nèi)地址頁表始址頁表長度例: 段表如下：回答下列問題：1計(jì)算該作業(yè)訪問 0，432，1，10，2，500，3，400 時(shí)的絕對地址2總結(jié)段式存儲(chǔ)管理的地址轉(zhuǎn)換過程。4.5 虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念 4.5.1 虛擬存儲(chǔ)器的引入虛擬存儲(chǔ)器的引入 1. 常規(guī)存儲(chǔ)器管理方式的特征常規(guī)存儲(chǔ)器管理方式的特征 一次性。 (2) 駐留性。 2. 局部性原理局部性原理 早在1968年， Denning.P就曾指出： (1) 程序執(zhí)行時(shí)， 除了少部分的轉(zhuǎn)移和過程調(diào)用指令外， 在大多數(shù)情況下仍是順序執(zhí)行的。 (2) 過程調(diào)用將會(huì)使程序的執(zhí)行軌跡

23、由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域， 但經(jīng)研究看出，過程調(diào)用的深度在大多數(shù)情況下都不超過5。 (3) 程序中存在許多循環(huán)結(jié)構(gòu)， 這些雖然只由少數(shù)指令構(gòu)成， 但是它們將多次執(zhí)行。 (4) 程序中還包括許多對數(shù)據(jù)結(jié)構(gòu)的處理， 如對數(shù)組進(jìn)行操作， 它們往往都局限于很小的范圍內(nèi)。 局限性又表現(xiàn)在下述兩個(gè)方面： (1) 時(shí)間局限性。如果程序中的某條指令一旦執(zhí)行， 則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過， 則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時(shí)間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。 (2) 空間局限性。一旦程序訪問了某個(gè)存儲(chǔ)單元，在不久之后，其附近的存儲(chǔ)單元也將被訪問，即程序在一段時(shí)

24、間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。 3. 虛擬存儲(chǔ)器定義虛擬存儲(chǔ)器定義 所謂虛擬存儲(chǔ)器， 是指具有請求調(diào)入功能和置換功能， 能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運(yùn)行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存?？梢姡摂M存儲(chǔ)技術(shù)是一種性能非常優(yōu)越的存儲(chǔ)器管理技術(shù)，故被廣泛地應(yīng)用于大、 中、 小型機(jī)器和微型機(jī)中。 4.5.2 虛擬存儲(chǔ)器的實(shí)現(xiàn)方法虛擬存儲(chǔ)器的實(shí)現(xiàn)方法 1. 分頁請求系統(tǒng)分頁請求系統(tǒng) 硬件支持。 請求分頁的頁表機(jī)制，它是在純分頁的頁表機(jī)制上增加若干項(xiàng)而形成的，作為請求分頁的數(shù)據(jù)結(jié)構(gòu)； 缺

25、頁中斷機(jī)構(gòu)，即每當(dāng)用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時(shí) 便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存； 地址變換機(jī)構(gòu)， 它同樣是在純分頁地址變換機(jī)構(gòu)的基礎(chǔ)上發(fā)展形成的。 (2) 實(shí)現(xiàn)請求分頁的軟件。4.5.3 虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征 多次性多次性 對換性對換性3. 虛擬性虛擬性 4.6 請求分頁存儲(chǔ)管理方式請求分頁存儲(chǔ)管理方式 4.6.1 請求分頁中的硬件支持請求分頁中的硬件支持 1. 頁表機(jī)制頁表機(jī)制 2. 缺頁中斷機(jī)構(gòu)缺頁中斷機(jī)構(gòu) 圖 4-23 涉及6次缺頁中斷的指令 頁面B：A：654321指令copy ATO B3. 地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 缺頁中斷處理保留CPU現(xiàn)場從外存

26、中找到缺頁內(nèi)存滿否？選擇一頁換出該頁被修改否？將該頁寫回外存OS命令CPU從外存讀缺頁啟動(dòng)I/O硬件將一頁從外存換入內(nèi)存修改頁表否是是否頁表項(xiàng)在快表中？CPU檢索快表訪問頁表否頁在內(nèi)存？修改訪問位和修改位形成物理地址地址變換結(jié)束否頁號頁表長度?開始程序請求訪問一頁產(chǎn)生缺頁中斷請求調(diào)頁修改快表是越界中斷是是圖 4-24 請求分頁中的地址變換過程 4.6.2 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法 1. 最小物理塊數(shù)的確定最小物理塊數(shù)的確定 是指能保證進(jìn)程正常運(yùn)行所需的最小物理塊數(shù)。當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將無法運(yùn)行。進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指

27、令的格式、 功能和尋址方式。對于某些簡單的機(jī)器，若是單地址指令且采用直接尋址方式，則所需的最少物理塊數(shù)為2。其中，一塊是用于存放指令的頁面，另一塊則是用于存放數(shù)據(jù)的頁面。如果該機(jī)器允許間接尋址時(shí)，則至少要求有三個(gè)物理塊。對于某些功能較強(qiáng)的機(jī)器， 其指令長度可能是兩個(gè)或多于兩個(gè)字節(jié)，因而其指令本身有可能跨兩個(gè)頁面，且源地址和目標(biāo)地址所涉及的區(qū)域也都可能跨兩個(gè)頁面。2. 物理塊的分配策略物理塊的分配策略 在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進(jìn)行置換時(shí)， 也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。 1) 固定分配局部置換(Fixed All

28、ocation, Local Replacement) 2) 可變分配全局置換(Variable Allocation, Global Replacement) 3) 可變分配局部置換(Variable Allocation, Local Replacemen 3. 物理塊分配算法物理塊分配算法 1) 平均分配算法 這是將系統(tǒng)中所有可供分配的物理塊，平均分配給各個(gè)進(jìn)程。 例如，當(dāng)系統(tǒng)中有100個(gè)物理塊，有5個(gè)進(jìn)程在運(yùn)行時(shí)，每個(gè)進(jìn)程可分得20個(gè)物理塊。這種方式貌似公平，但實(shí)際上是不公平的，因?yàn)樗纯紤]到各進(jìn)程本身的大小。如有一個(gè)進(jìn)程其大小為200頁，只分配給它20個(gè)塊，這樣，它必然會(huì)有很高的缺頁

29、率；而另一個(gè)進(jìn)程只有10頁，卻有10個(gè)物理塊閑置未用。 2) 按比例分配算法 這是根據(jù)進(jìn)程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)為Si，則系統(tǒng)中各進(jìn)程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個(gè)進(jìn)程所能分到的物理塊數(shù)為bi，將有：b應(yīng)該取整，它必須大于最小物理塊數(shù)。 niiSS1mSSbii 3) 考慮優(yōu)先權(quán)的分配算法 在實(shí)際應(yīng)用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成， 應(yīng)為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；另一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)，適當(dāng)?shù)卦黾悠湎鄳?yīng)份額后，分配給各進(jìn)程

30、。在有的系統(tǒng)中，如重要的實(shí)時(shí)控制系統(tǒng)，則可能是完全按優(yōu)先權(quán)來為各進(jìn)程分配其物理塊的。 4.6.3 調(diào)頁策略調(diào)頁策略 1. 何時(shí)調(diào)入頁面何時(shí)調(diào)入頁面 預(yù)調(diào)頁策略 2) 請求調(diào)頁策略 2. 從何處調(diào)入頁面從何處調(diào)入頁面 在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。通常，由于對換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁請求時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況： (1) 系統(tǒng)擁有足夠的對換區(qū)空間，這時(shí)可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。為此，在進(jìn)程運(yùn)行前， 便須將與該進(jìn)程有關(guān)的

31、文件，從文件區(qū)拷貝到對換區(qū)。 (2) 系統(tǒng)缺少足夠的對換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁面時(shí)，由于它們未被修改而不必再將它們換出，以后再調(diào)入時(shí)，仍從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時(shí)，便須調(diào)到對換區(qū)，以后需要時(shí)，再從對換區(qū)調(diào)入。 (3) UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁面，都應(yīng)從文件區(qū)調(diào)入。而對于曾經(jīng)運(yùn)行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面共享，因此， 某進(jìn)程所請求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無須再從對換區(qū)調(diào)入。 3. 頁面調(diào)

32、入過程頁面調(diào)入過程 每當(dāng)程序所要訪問的頁面未在內(nèi)存時(shí)，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后， 轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后， 如果此時(shí)內(nèi)存能容納新頁，則啟動(dòng)磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準(zhǔn)備換出；如果該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改， 則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存， 并修改頁表中的相應(yīng)表項(xiàng)，置其存在位為“1”，并將此頁表項(xiàng)寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表， 去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)

33、。 4.7 頁面置換算法頁面置換算法 4.7.1 最佳置換算法和先進(jìn)先出置換算法最佳置換算法和先進(jìn)先出置換算法 1. 最佳(Optimal)置換算法 最佳置換算法是由Belady于1966年提出的一種理論上的算法。 其所選擇的被淘汰頁面，將是以后永不使用的， 或許是在最長(未來)時(shí)間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。 假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊， 并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 進(jìn)程運(yùn)行時(shí)， 先將7，0，1三個(gè)頁面裝入內(nèi)存。 以后， 當(dāng)進(jìn)程要訪問頁面2時(shí)， 將會(huì)產(chǎn)生缺頁中斷。此時(shí)O

34、S根據(jù)最佳置換算法， 將選擇頁面7予以淘汰。 引用率70770170122010320304243230321201201770101頁框(物理塊）203圖 4-25 利用最佳頁面置換算法時(shí)的置換圖 2. 先進(jìn)先出先進(jìn)先出(FIFO)頁面置換算法頁面置換算法 引用率70770170122010323104430230321013201770201頁框2304204230230127127011圖 4-26 利用FIFO置換算法時(shí)的置換圖 4.7.2 最近最久未使用最近最久未使用(LRU)置換算法置換算法 1. LRU(Least Recently Used)置換算法的描述置換算法的描述 圖 4

35、-27 LRU頁面置換算法 引用率70770170122010320304403230321132201710701頁框4024320321022. LRU置換算法的硬件支持置換算法的硬件支持 1) 寄存器寄存器 為了記錄某進(jìn)程在內(nèi)存中各頁的使用情況，須為每個(gè)在內(nèi)存中的頁面配置一個(gè)移位寄存器，可表示為 R=Rn-1Rn-2Rn-3 R2R1R0 圖 4-28 某進(jìn)程具有8個(gè)頁面時(shí)的LRU訪問情況 2) 棧棧 圖 4-29 用棧保存當(dāng)前使用頁面時(shí)棧的變化情況 44747074070471704101740107412107421207412107426210764.7.3 Clock置換算法置換

36、算法 1. 簡單的簡單的Clock置換算法置換算法 圖 4-30 簡單Clock置換算法的流程和示例 入口查尋指針前進(jìn)一步，指向下一個(gè)表目頁面訪問位 0?選擇該頁面淘汰是返回置頁面訪問位“ 0”否塊號頁號訪問位指針0124034215650711替換指針2. 改進(jìn)型改進(jìn)型Clock置換算法置換算法 由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示該頁最近既未被訪問， 又未被修改， 是最佳淘汰頁。 2類(A=0, M=1)： 表示該頁最近未被訪問， 但已被修改， 并不是很好的淘汰頁。 3類(A=1, M=0)： 最近已被訪問， 但未被修改， 該頁有可能再被訪問

37、。 4類(A=1, M=1): 最近已被訪問且被修改， 該頁可能再被訪問。 其執(zhí)行過程可分成以下三步： (1) 從指針?biāo)甘镜漠?dāng)前位置開始， 掃描循環(huán)隊(duì)列， 尋找A=0且M=0的第一類頁面， 將所遇到的第一個(gè)頁面作為所選中的淘汰頁。 在第一次掃描期間不改變訪問位A。 (2) 如果第一步失敗，即查找一周后未遇到第一類頁面， 則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個(gè)這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。 (3) 如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復(fù)0。 然后重復(fù)第一步，如果仍失敗，必要時(shí)再重復(fù)第二步，此時(shí)就一定能找到被淘汰的頁。 4.7.4 其它置換算