1、 OPERSTERING SYSTEM第第4 4章章 存儲(chǔ)器管理存儲(chǔ)器管理 存儲(chǔ)管理是指存儲(chǔ)器資源（主要指內(nèi)存和外存）的管理。本章我們討論的內(nèi)容包括： 存儲(chǔ)器資源的組織（如內(nèi)存的組織方式） 地址變換（邏輯地址與物理地址的對(duì)應(yīng)關(guān)系） OPERSTERING SYSTEM存儲(chǔ)器的功能:保存數(shù)據(jù).存儲(chǔ)器的發(fā)展方向是高速、大容量和小體積。如：內(nèi)存在訪問(wèn)速度方面的發(fā)展：DRAM(動(dòng)態(tài)隨機(jī)存儲(chǔ)器 )、SDRAM(同步動(dòng)態(tài)隨機(jī)存儲(chǔ)器 )、DDRAM(DoubleDataRate )、RDRAM(存儲(chǔ)器總線(xiàn)式動(dòng)態(tài)隨機(jī)存儲(chǔ)器 )等；硬盤(pán)技術(shù)在大容量方面的發(fā)展：接口標(biāo)準(zhǔn)、存儲(chǔ)密度等；存儲(chǔ)組織的功能:存儲(chǔ)技術(shù)和CP

2、U尋址技術(shù)許可的范圍內(nèi)組織合理的存儲(chǔ)結(jié)構(gòu)，其依據(jù)是訪問(wèn)速度匹配關(guān)系、容量要求和價(jià)格。如：“寄存器-內(nèi)存-外存”結(jié)構(gòu)和“寄存器-緩存-內(nèi)存-外存”結(jié)構(gòu)；現(xiàn)在微機(jī)中的存儲(chǔ)層次組織：訪問(wèn)速度越來(lái)越慢，容量越來(lái)越大，價(jià)格越來(lái)越便宜；最佳狀態(tài)應(yīng)是各層次的存儲(chǔ)器都處于均衡的繁忙狀態(tài)(如：緩存命中率正好使主存讀寫(xiě)保持繁忙) OPERSTERING SYSTEM外存(secondary storage)DOS核心命令處理程序主存(primary storage)快速緩存(cache)寄存器(register) OPERSTERING SYSTEM存儲(chǔ)管理的功能(1) 存儲(chǔ)分配和回收：是存儲(chǔ)管理的主要內(nèi)容。討論

3、其算法和相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。(2) 地址變換：可執(zhí)行文件生成中的鏈接技術(shù)、程序加載時(shí)的重定位技術(shù)，進(jìn)程運(yùn)行時(shí)硬件和軟件的地址變換技術(shù)和機(jī)構(gòu)。(3) 存儲(chǔ)共享和保護(hù)：代碼和數(shù)據(jù)共享，對(duì)地址空間的訪問(wèn)權(quán)限（讀、寫(xiě)、執(zhí)行）。(4) 存儲(chǔ)器擴(kuò)充：它涉及存儲(chǔ)器的邏輯組織和物理組織；由應(yīng)用程序控制：覆蓋；由OS控制：交換（整個(gè)進(jìn)程空間），請(qǐng)求調(diào)入和預(yù)調(diào)入（部分進(jìn)程空間） OPERSTERING SYSTEM背景程序必須裝入到內(nèi)存并放置在該進(jìn)程擁有的內(nèi)存區(qū)域中才能執(zhí)行。輸入隊(duì)列 存放在磁盤(pán)上等待裝入內(nèi)存以便運(yùn)行的程序隊(duì)列集合。用戶(hù)程序在獲得執(zhí)行以前需要經(jīng)歷幾個(gè)步驟：生成源程序文件、生成目標(biāo)模塊、生成可加載模塊以

4、及在內(nèi)存中創(chuàng)建進(jìn)程。 OPERSTERING SYSTEM4.1 程序的裝入和鏈接 步驟：編譯、鏈接、裝入?？蓤?zhí)行文件的建立：源程序，編譯，成為目標(biāo)模塊多個(gè)目標(biāo)模塊或程序庫(kù)，鏈接，成為可執(zhí)行文件裝入，成為進(jìn)程編譯：高級(jí)語(yǔ)言的源程序機(jī)器指令 符號(hào)地址內(nèi)存地址（相對(duì)地址）鏈接：將各個(gè)目標(biāo)模塊中的相對(duì)地址統(tǒng)一轉(zhuǎn)成相對(duì)于各個(gè)模塊地址的位移。裝入：執(zhí)行程序時(shí)，將該程序和其所要處理的數(shù)據(jù)裝入內(nèi)存。 OPERSTERING SYSTEM庫(kù)鏈接程序裝入模塊裝入程序編譯程序產(chǎn)生的目標(biāo)模塊第一步第二步第三步內(nèi)存 OPERSTERING SYSTEM裝入：重定位：在可執(zhí)行文件裝入時(shí)需要解決可執(zhí)行文件中地址（指令和數(shù)

5、據(jù)）和內(nèi)存地址的對(duì)應(yīng)。由操作系統(tǒng)中的裝入程序loader來(lái)完成 OPERSTERING SYSTEM程序的裝入程序的裝入 三種方式：1. 絕對(duì)裝入(absolute loading)在可執(zhí)行文件中記錄內(nèi)存地址，裝入時(shí)直接定位在上述內(nèi)存地址。 程序中所使用的絕對(duì)地址，既可在編譯或匯編時(shí)給出， 也可由程序員直接賦予。 但在由程序員直接給出絕對(duì)地址時(shí)， 不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。 OPERSTERING SYSTEM一樣：一樣：意味著意味著OSOS只要讀入內(nèi)存即可只要讀入內(nèi)存即可絕對(duì)裝入。絕對(duì)裝入。所以：所以： 象象 JMP L1JMP

6、 L1 指令在變成可執(zhí)行代碼后，該指令的地址場(chǎng)的數(shù)據(jù)是指令在變成可執(zhí)行代碼后，該指令的地址場(chǎng)的數(shù)據(jù)是一定的。這就意味該程序只能放在固定的地方。一定的。這就意味該程序只能放在固定的地方。diskdiskJMP 200JMP 200loadloadJMP 200JMP 200MOV AX, 201MOV AX, 2011000100012001200 OPERSTERING SYSTEM優(yōu)點(diǎn)：裝入過(guò)程簡(jiǎn)單。缺點(diǎn)：過(guò)于依賴(lài)于硬件結(jié)構(gòu)，不適于多道程序系統(tǒng)。 OPERSTERING SYSTEM0000 .1000 . .11001102110411061108 . . . .物理內(nèi)存OS重定位的概念L

7、oad R1,106Add R1,108Store R1,110234128程序A的代碼000100102104106108Load R1,106Add R1,108Store R1,110234128Load R1,1106Add R1,1108Store R1,1110234128 OPERSTERING SYSTEM在裝入前鏈接所假設(shè)的程序地址與此時(shí)裝入的實(shí)際地址不一致。在可執(zhí)行文件中，列出各個(gè)需要重定位的地址單元和相對(duì)地址值，裝入時(shí)再根據(jù)所定位的內(nèi)存地址去修改每個(gè)重定位地址項(xiàng)，添加相應(yīng)偏移量。 可重定位裝入（靜態(tài)） (relocatable loading) OPERSTERING S

8、YSTEM重定位分類(lèi):靜態(tài)重定位Load R1,106Add R1,108Store R1,110234128程序A的代碼0001001021041061080000 .1000 . .11001102110411061108 . . . .物理內(nèi)存OSLoad R1,1106Add R1,1108Store R1,1110234128加載時(shí)定位Load R1,1106Add R1,1108Store R1,1110234128例：例：MZMZ10100201頭標(biāo)志頭標(biāo)志MOVE AX,MOVE AX,JMPJMP指令碼指令碼JMPJMP（200200）0100300300201頭部分頭部分代

9、碼部分代碼部分200MZMZ10100201頭部分頭部分例：例：MOVE AX,MOVE AX,JMPJMP指令碼指令碼JMPJMP（200200）0100300300201200MOVE AX,MOVE AX,JMPJMP指令碼指令碼JMPJMP(200)(200)0+1000100+1000300300201+10001000（2）裝入）裝入（1）頭部分由）頭部分由OS讀入讀入（3）OS根據(jù)讀入根據(jù)讀入的頭對(duì)內(nèi)存浮動(dòng)項(xiàng)的頭對(duì)內(nèi)存浮動(dòng)項(xiàng)裝配裝配MZMZ10100201頭部分頭部分例：例：MOVE,AXMOVE,AXJMPJMP指令碼指令碼JMPJMP（200200）0100300300201

10、200MOVE AX,MOVE AX,JMPJMP指令碼指令碼JMPJMP( (12001200) )0+1000100+1000300300201+10001000（2）裝入）裝入（1）頭部分由）頭部分由OS讀入讀入（3）OS根據(jù)讀入根據(jù)讀入的頭對(duì)內(nèi)存浮動(dòng)項(xiàng)的頭對(duì)內(nèi)存浮動(dòng)項(xiàng)裝配裝配MZMZ10100201頭部分頭部分例：例：MOVE AX,MOVE AX,JMPJMP指令碼指令碼JMPJMP（200200）0100300300201200MOVE AX,MOVE AX,JMPJMP指令碼指令碼JMPJMP( (12001200) )0+1000100+100013001300201+1000

11、1000（2）裝入）裝入（1）頭部分由）頭部分由OS讀入讀入（3）OS根據(jù)讀入根據(jù)讀入的頭對(duì)內(nèi)存浮動(dòng)項(xiàng)的頭對(duì)內(nèi)存浮動(dòng)項(xiàng)裝配裝配 OPERSTERING SYSTEMjmp150100150.RelocationTable0jm2000 OPERSTERING SYSTEM優(yōu)點(diǎn)：不需硬件支持，可以裝入有限多道程序.缺點(diǎn)：一個(gè)程序通常需要占用連續(xù)的內(nèi)存空間，程序裝入內(nèi)存后不能移動(dòng)。不易實(shí)現(xiàn)共享。 OPERSTERING SYSTEM 動(dòng)態(tài)運(yùn)行期裝入（動(dòng)態(tài)重地位）動(dòng)態(tài)運(yùn)行期裝入（動(dòng)態(tài)重地位）( (dynamic run-time loading)dynamic run-ti

12、me loading)在可執(zhí)行文件中記錄虛擬內(nèi)存地址，裝入和執(zhí)行時(shí)通過(guò)硬件地址變換機(jī)構(gòu)，完成虛擬地址到實(shí)際內(nèi)存地址的變換。 OPERSTERING SYSTEM重定位分類(lèi):動(dòng)態(tài)重定位Load R1,106Add R1,108Store R1,110234128程序A的代碼0001001021041061080000 .1000 . .11001102110411061108 . . . .物理內(nèi)存OSLoad R1,106Add R1,108Store R1,110234128重定位寄存器(位于CPU中)+1000 OPERSTERING SYSTEM OPERSTERING SYSTEM優(yōu)點(diǎn)

13、：OS可以將一個(gè)程序分散存放于不連續(xù)的內(nèi)存空間，可以移動(dòng)程序，有利用實(shí)現(xiàn)共享。能夠支持程序執(zhí)行中產(chǎn)生的地址引用，如指針變量（而不僅是生成可執(zhí)行文件時(shí)的地址引用）缺點(diǎn)：需要硬件支持（通常是CPU），OS實(shí)現(xiàn)較復(fù)雜是虛擬存儲(chǔ)的基礎(chǔ) OPERSTERING SYSTEM邏輯地址空間與物理地址空間將邏輯地址空間與物理地址空間相分離，是內(nèi)存管理的核心。邏輯地址邏輯地址 由CPU（指令譯碼器）生成的地址（程序員使用的地址或指令的地址碼部分最終確定的地址），也稱(chēng)虛地址虛地址 （ virtual address）。物理地址物理地址 內(nèi)存單元的地址。如果地址綁定工作在編譯階段或加載階段完成，那么邏輯地址與物理地

14、址是相同的。如果地址綁定工作在執(zhí)行階段完成，那么邏輯地址（虛地址）與物理地址是不相同的。 OPERSTERING SYSTEM存儲(chǔ)管理單元 (MMU)MMU是一個(gè)硬件裝置，它將虛地址映射（轉(zhuǎn)換）成物理地址。（MMU目前是作為CPU硬件的一個(gè)功能單元存在于CPU中）在使用 MMU 的方案中，用戶(hù)進(jìn)程每次產(chǎn)生的地址在送到存儲(chǔ)器（譯碼器）之前，都要加上存放在重定位寄存器（基地址寄存器）中的值（基地址），從而形成存儲(chǔ)器物理單元的地址，即物理地址。用戶(hù)程序中出現(xiàn)的地址都是邏輯地址；用戶(hù)程序不可能知道真實(shí)的物理地址是什么。 OPERSTERING SYSTEM OPERSTERING SYSTEM程序的鏈

15、接程序的鏈接 鏈接是指多個(gè)目標(biāo)模塊在執(zhí)行時(shí)的地址空間分配和相互引用。 鏈接分類(lèi)鏈接分類(lèi)靜態(tài)靜態(tài)鏈接鏈接動(dòng)態(tài)鏈接動(dòng)態(tài)鏈接載入時(shí)動(dòng)態(tài)鏈接載入時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接運(yùn)行時(shí)動(dòng)態(tài)鏈接 OPERSTERING SYSTEM靜態(tài)鏈接(static-linking)靜態(tài)鏈接是在生成可執(zhí)行文件時(shí)進(jìn)行的。在目標(biāo)模塊中記錄符號(hào)地址(symbolic address)，而在可執(zhí)行文件中改寫(xiě)為指令直接使用的數(shù)字地址。 OPERSTERING SYSTEMModule AModule Acall function10L-1Module BModule B0M-1function1().function1FModule

16、AModule Acall L+F0L-1Module BModule BLL+M-1function1().function1L+F對(duì)多用戶(hù)、多任務(wù)系統(tǒng)顯然有冗余，比如用戶(hù)用對(duì)多用戶(hù)、多任務(wù)系統(tǒng)顯然有冗余，比如用戶(hù)用sin(x)sin(x)，則則目標(biāo)代碼中都有這部分代碼，裝入到內(nèi)存則也都有這部分代目標(biāo)代碼中都有這部分代碼，裝入到內(nèi)存則也都有這部分代碼。碼。 OPERSTERING SYSTEM動(dòng)態(tài)鏈接(dynamic-linking)在裝入或運(yùn)行時(shí)進(jìn)行鏈接。通常被鏈接的共享代碼稱(chēng)為動(dòng)態(tài)鏈接庫(kù)(DLL)或共享庫(kù)(shared library)。 OPERSTERING SYSTEM優(yōu)點(diǎn)共享：多

17、個(gè)進(jìn)程可以共用一個(gè)DLL，節(jié)省內(nèi)存，減少文件交換。部分裝入：一個(gè)進(jìn)程可以將多種操作分散在不同的DLL中實(shí)現(xiàn)，而只將當(dāng)前操作相應(yīng)的DLL裝入內(nèi)存。便于局部代碼修改：即便于代碼升級(jí)和代碼重用；只要函數(shù)的接口參數(shù)（輸入和輸出）不變，則修改函數(shù)及其DLL，無(wú)需對(duì)可執(zhí)行文件重新編譯或鏈接。便于運(yùn)行環(huán)境適應(yīng)：調(diào)用不同的DLL，就可以適應(yīng)多種使用環(huán)境和提供不同功能。如：不同的顯示卡只需廠商為其提供特定的DLL，而OS和應(yīng)用程序不必修改。 OPERSTERING SYSTEM缺點(diǎn)：鏈接開(kāi)銷(xiāo)：增加了程序執(zhí)行時(shí)的鏈接開(kāi)銷(xiāo)；管理開(kāi)銷(xiāo)：程序由多個(gè)文件組成，增加管理復(fù)雜度。 OPERSTERING SYSTEM覆蓋任何

18、時(shí)候在內(nèi)存中僅保留需要的指令和數(shù)據(jù),將程序的必要部分的代碼和數(shù)據(jù)常駐內(nèi)存，可選部分平時(shí)存放在外存中，需要時(shí)裝入。當(dāng)進(jìn)程的大小比分配給他的內(nèi)存地址空間大時(shí)，可以考慮使用覆蓋技術(shù)誰(shuí)覆蓋誰(shuí)，由用戶(hù)實(shí)現(xiàn)，無(wú)需操作系統(tǒng)的支持，程序設(shè)計(jì)時(shí)程序員需要精心地考慮編寫(xiě)支持覆蓋的程序結(jié)構(gòu)。 OPERSTERING SYSTEM在一個(gè)兩趟匯編的匯編程序中使用覆蓋技術(shù) OPERSTERING SYSTEMA20KB50KC30KF30KD20KE40KResident20KOverlay 050KOverlay 140KTotal: 190KTotal: 110K OPERSTERING SYSTEM交換一個(gè)進(jìn)程可以

19、從內(nèi)存臨時(shí)交換到后備存儲(chǔ)器（外存）上存放，其后需要執(zhí)行時(shí)再將其調(diào)入內(nèi)存中。后備存儲(chǔ)器 快速的磁盤(pán)，需要有足夠的存儲(chǔ)空間用來(lái)存放所有用戶(hù)在內(nèi)存的存儲(chǔ)映像，同時(shí)必須提供對(duì)這些內(nèi)存映像的直接訪問(wèn)。滾出（Roll out），滾進(jìn)（ roll in） 交換技術(shù)的一個(gè)變種，被用在基于優(yōu)先權(quán)調(diào)度算法的系統(tǒng)中；低優(yōu)先權(quán)進(jìn)程被換出，而高優(yōu)先權(quán)進(jìn)程便可以裝入執(zhí)行。交換所花費(fèi)時(shí)間的主要部分是傳輸時(shí)間，傳輸時(shí)間與需要交換的內(nèi)存單元的數(shù)量成正比.在許多操作系統(tǒng)中，例如UNIX, Linux和 Windows 都有各種形式交換存在。 OPERSTERING SYSTEM交換示意圖 OPERSTERING SYSTEM4.

20、2 4.2 連續(xù)分配存儲(chǔ)管理方式連續(xù)分配存儲(chǔ)管理方式 連續(xù)分配是指為一個(gè)用戶(hù)程序分配一個(gè)連續(xù)的內(nèi)存空間。 因?yàn)槌绦虻膱?zhí)行是根據(jù)指令計(jì)數(shù)器順序執(zhí)行,在執(zhí)行本指令時(shí),它已是下條指令的位置,跳轉(zhuǎn)指令會(huì)自動(dòng)置為跳轉(zhuǎn)的目標(biāo)地址,所以決定了程序必須占有連續(xù)的一段存儲(chǔ)區(qū),連續(xù)分配是指為一個(gè)用戶(hù)程序分配一個(gè)連續(xù)的內(nèi)存空間。 OPERSTERING SYSTEM連續(xù)內(nèi)存分配法(1) 內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用戶(hù)區(qū)。應(yīng)用程序裝入到用戶(hù)區(qū)，可使用用戶(hù)區(qū)全部空間。(2) 最簡(jiǎn)單，適用于單用戶(hù)、單任務(wù)的OS。CP/M和DOS 2.0以下。 OPERSTERING SYSTEM單道連續(xù)區(qū)管理000020KB100KB2

21、56KBOS用戶(hù)程序需80KB存儲(chǔ)空間空閑區(qū)一次只能裝入一個(gè)作業(yè) OPERSTERING SYSTEM內(nèi)存內(nèi)存+重定位寄存器物理頁(yè)面號(hào)（實(shí)際內(nèi)存空間）；每個(gè)進(jìn)程有一個(gè)頁(yè)表，描述該進(jìn)程占用的物理頁(yè)面及邏輯排列順序；物理頁(yè)面表：整個(gè)系統(tǒng)有一個(gè)物理頁(yè)面表，描述物理內(nèi)存空間的分配使用狀況。數(shù)據(jù)結(jié)構(gòu)：位示圖，空閑頁(yè)面鏈表；請(qǐng)求表：整個(gè)系統(tǒng)有一個(gè)請(qǐng)求表，描述系統(tǒng)內(nèi)各個(gè)進(jìn)程頁(yè)表的位置和大小，用于地址轉(zhuǎn)換，也可以結(jié)合到各進(jìn)程的PCB里； OPERSTERING SYSTEM用戶(hù)程序0 頁(yè)1 頁(yè)2 頁(yè)3 頁(yè)4 頁(yè)5 頁(yè)n 頁(yè)頁(yè)表頁(yè)號(hào)塊號(hào)02132638495內(nèi)存012345678910 OPERSTERING

22、SYSTEM三、頁(yè)面大小的選擇通常是：幾KB到幾十KB。和目前計(jì)算機(jī)的物理內(nèi)存大小有關(guān)：4MB到256MB，不太大。較小的頁(yè)面，減小內(nèi)碎片，但加大頁(yè)表的長(zhǎng)度，從而形成新的開(kāi)銷(xiāo)并增加換入、換出的開(kāi)銷(xiāo)；較大的頁(yè)面，減小頁(yè)表的長(zhǎng)度，加大內(nèi)碎片；管理開(kāi)銷(xiāo)小，交換時(shí)對(duì)外存I/O效率高。兩者的折中。計(jì)算機(jī)頁(yè)大小(byte)Intel 804864096IBM AS/400512VAX-11/780128Motorola680404096 OPERSTERING SYSTEM四、優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： 沒(méi)有外碎片，每個(gè)內(nèi)碎片不超過(guò)頁(yè)大小。 一個(gè)程序不必連續(xù)存放。便于改變程序占用空間的大?。ㄖ饕鸽S著程序運(yùn)行而動(dòng)態(tài)生

23、成的數(shù)據(jù)增多，要求地址空間相應(yīng)增長(zhǎng)，通常由系統(tǒng)調(diào)用完成而不是操作系統(tǒng)自動(dòng)完成）。 缺點(diǎn)： 程序全部裝入內(nèi)存。 OPERSTERING SYSTEM地址變換機(jī)構(gòu)地址變換機(jī)構(gòu) 邏輯地址物理地址地址變換機(jī)構(gòu)邏輯頁(yè)號(hào)物理塊號(hào) OPERSTERING SYSTEM一、一、基本地址變換機(jī)構(gòu)指令所給出地址分為兩部分：邏輯頁(yè)號(hào)，頁(yè)內(nèi)偏移地址,通過(guò)查進(jìn)程頁(yè)表，得物理頁(yè)號(hào)，從而形成物理地址。 OPERSTERING SYSTEM頁(yè)表始址頁(yè)表始址 頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度作業(yè)名作業(yè)名A A頁(yè)表始址頁(yè)表始址xxxxxxxxxxxx頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度3 3作業(yè)表作業(yè)表塊號(hào)塊號(hào)比較比較頁(yè)號(hào)頁(yè)號(hào) 頁(yè)內(nèi)地址頁(yè)內(nèi)地址塊號(hào)塊號(hào) 頁(yè)內(nèi)地址頁(yè)

24、內(nèi)地址頁(yè)表頁(yè)表頁(yè)表控制寄存器頁(yè)表控制寄存器絕對(duì)地址絕對(duì)地址邏輯地址邏輯地址地址越界地址越界 OPERSTERING SYSTEM分頁(yè)存儲(chǔ)管理原理頁(yè)號(hào)2頁(yè)內(nèi)地址452邏輯地址2500頁(yè)表基址寄存器頁(yè)表起址頁(yè)長(zhǎng)021425.頁(yè)號(hào) 塊號(hào)頁(yè)表塊號(hào)5塊內(nèi)地址452越界中斷+物理地址55725*1024+452純分頁(yè)系統(tǒng)的基本地址轉(zhuǎn)換機(jī)構(gòu)設(shè)每頁(yè)1KB(1024) OPERSTERING SYSTEM OPERSTERING SYSTEM某虛擬存儲(chǔ)器的用戶(hù)編程空間共32個(gè)頁(yè)面，每頁(yè)為1KB，內(nèi)存為16KB。假定某時(shí)刻一用戶(hù)頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面的頁(yè)號(hào)和物理塊號(hào)的對(duì)照表如下：則邏輯地址0A5C(H)所對(duì)應(yīng)的物

25、理地址是什么？ 頁(yè)號(hào)物理塊號(hào)031721138 OPERSTERING SYSTEM邏輯地址0A5C(H)所對(duì)應(yīng)的二進(jìn)制表示形式是： 0000 1010 0101 1100 所對(duì)應(yīng)的頁(yè)號(hào)是： 2 （十進(jìn)制） 查頁(yè)表，得到物理塊號(hào)是： 11 （十進(jìn)制） 拼接后，得到物理地址： 0010 1110 0101 1100 即：2E5C(H) OPERSTERING SYSTEM頁(yè)表的實(shí)現(xiàn)頁(yè)表通常被存放在主存中.頁(yè)表基地址寄存器頁(yè)表基地址寄存器（ PTBR， Page-table base register） 用來(lái)指示頁(yè)表在內(nèi)存的起始位置.頁(yè)表長(zhǎng)度寄存器頁(yè)表長(zhǎng)度寄存器（ PRLR， Page-table

26、 length register ）用來(lái)指示頁(yè)表的大小.每次CPU對(duì)內(nèi)存中的指令或數(shù)據(jù)的訪問(wèn)都需要訪問(wèn)兩次內(nèi)存，第一次訪問(wèn)頁(yè)表，第二次才是訪問(wèn)指令或數(shù)據(jù).為了解決上述問(wèn)題，通常在CPU中設(shè)置一個(gè)容量不大的專(zhuān)門(mén)用于快速查找（頁(yè)框起始地址）的Cache，即一種聯(lián)想存儲(chǔ)器（ associative memory ），稱(chēng)作翻譯對(duì)照緩沖存儲(chǔ)器（translation look-aside buffers ，TLBs） OPERSTERING SYSTEM二、具有快表的地址變換機(jī)構(gòu)為縮短查找時(shí)間，可以將頁(yè)表從內(nèi)存裝入到關(guān)聯(lián)存儲(chǔ)器(TLB, Translation Lookaside Buffer)：按內(nèi)容

27、查找,即邏輯頁(yè)號(hào)物理頁(yè)號(hào)。 聯(lián)想存儲(chǔ)器(快表):具有并行查尋能力的特殊高速緩沖存儲(chǔ)器,一種硬件機(jī)構(gòu),由若干個(gè)寄存器組成。 聯(lián)想存儲(chǔ)器速度快但成本高,通常由16512個(gè)單元組成,例如Intel 80486只有32個(gè)聯(lián)想寄存器，對(duì)于大型作業(yè)，其頁(yè)表有一部分必須放在內(nèi)存。 OPERSTERING SYSTEM頁(yè)表寄存器頁(yè)表始址頁(yè)表長(zhǎng)度頁(yè)號(hào)頁(yè)內(nèi)地址邏輯地址L越界中斷塊號(hào)b頁(yè)表頁(yè)號(hào)頁(yè)號(hào)輸入寄存器塊號(hào)bb快表d物理地址 OPERSTERING SYSTEM頁(yè)號(hào)2頁(yè)內(nèi)地址425邏輯地址2500頁(yè)表基址寄存器頁(yè)表起址頁(yè)長(zhǎng)021425.頁(yè)號(hào) 塊號(hào)頁(yè)表塊號(hào)5塊內(nèi)地址425越界中斷+物理地址55725*1024+4

28、52具有快表的分頁(yè)地址轉(zhuǎn)換機(jī)構(gòu)設(shè)每頁(yè)1KB(1024) 543725快表 OPERSTERING SYSTEM 媽媽新開(kāi)了個(gè)淘寶店，歡迎前來(lái)捧場(chǎng)媽媽新開(kāi)了個(gè)淘寶店，歡迎前來(lái)捧場(chǎng) 媽媽的淘寶點(diǎn)開(kāi)了快半年了，主要賣(mài)的是毛絨玩具、坐墊、抱枕之類(lèi)的，媽媽的淘寶點(diǎn)開(kāi)了快半年了，主要賣(mài)的是毛絨玩具、坐墊、抱枕之類(lèi)的，但生意一直不是很好，感覺(jué)媽媽還是很用心的，花了不少功夫，但是就是沒(méi)但生意一直不是很好，感覺(jué)媽媽還是很用心的，花了不少功夫，但是就是沒(méi)有人氣，所以我也來(lái)出自己的一份力，幫忙宣傳一下。有人氣，所以我也來(lái)出自己的一份力，幫忙宣傳一下。 并且媽媽總是去五亭龍?zhí)糇詈玫耐婢哒怼l(fā)貨，質(zhì)量絕對(duì)有保證。并且

29、媽媽總是去五亭龍?zhí)糇詈玫耐婢哒怼l(fā)貨，質(zhì)量絕對(duì)有保證。 另外我家就在揚(yáng)州五亭龍玩具城旁邊，貨源豐富，質(zhì)量可靠，價(jià)格便宜。另外我家就在揚(yáng)州五亭龍玩具城旁邊，貨源豐富，質(zhì)量可靠，價(jià)格便宜。 歡迎大家來(lái)逛逛歡迎大家來(lái)逛逛【揚(yáng)州五亭龍玩具總動(dòng)員】 個(gè)人小廣告：個(gè)人小廣告： OPERSTERING SYSTEM兩級(jí)和多級(jí)頁(yè)表兩級(jí)和多級(jí)頁(yè)表 現(xiàn)代計(jì)算機(jī)系統(tǒng)，CPU都支持非常大的邏輯地址空間（ -2）。這樣可想而知頁(yè)表會(huì)非常大。例如:如果邏輯地址寬度為32bit，假設(shè)頁(yè)面大小為4K（即 ），頁(yè)表項(xiàng)達(dá)1M之多，每個(gè)頁(yè)表項(xiàng)為4個(gè)BYTE，僅頁(yè)表項(xiàng)就要占用4MB的連續(xù)內(nèi)存空間。解決方法：分散存儲(chǔ)；當(dāng)前需要的放在

30、內(nèi)存，其余的暫存于磁盤(pán)。643222 122 OPERSTERING SYSTEM一、兩級(jí)頁(yè)表（Two Level Page Table）分散存儲(chǔ)：將頁(yè)表分頁(yè)，每個(gè)頁(yè)面的大小與物理塊的大小相同。解決難于找到大的連續(xù)的物理內(nèi)存的問(wèn)題。相應(yīng)的機(jī)制：增加頁(yè)表的頁(yè)表外層頁(yè)表（頁(yè)表目錄）。邏輯地址結(jié)構(gòu)： OPERSTERING SYSTEM兩級(jí)頁(yè)表結(jié)構(gòu)： P1（目錄位移）P2（頁(yè)表位移）d（頁(yè)內(nèi)位移）外層頁(yè)號(hào)（頁(yè)表目錄）外層頁(yè)內(nèi)地址（頁(yè)表）頁(yè)內(nèi)地址3122 2112 110 OPERSTERING SYSTEM頁(yè)目錄012n3011023第0頁(yè)頁(yè)表01第1頁(yè)頁(yè)表1023頁(yè)表起始地址頁(yè)框號(hào)頁(yè)框號(hào) OPER

31、STERING SYSTEM地址變換機(jī)構(gòu)： 外部頁(yè)號(hào)P1P2外部頁(yè)內(nèi)地址 頁(yè)內(nèi)地址d邏輯地址外部頁(yè)表寄存器外部頁(yè)表db頁(yè)表頁(yè)表物理地址 OPERSTERING SYSTEM二、多級(jí)頁(yè)表對(duì)于64位字長(zhǎng)的機(jī)器，虛擬地址空間很大而每頁(yè)比較小，則進(jìn)程頁(yè)表太長(zhǎng)。宜采用兩級(jí)或多級(jí)頁(yè)表。例如SUN的SPARC處理器，支持3級(jí)頁(yè)表；而Motorola的68030處理器甚至支持4級(jí)頁(yè)表。 OPERSTERING SYSTEM.166.111.2.85166810.81.61118560929Virtual AddressReal Address OPERSTERING SYSTEM為縮短查找時(shí)間，多級(jí)頁(yè)表中的每

32、級(jí)都可以裝入到關(guān)聯(lián)存儲(chǔ)器（即頁(yè)表的高速緩存）中，并按照cache的原理進(jìn)行更新。多級(jí)頁(yè)表結(jié)構(gòu)中，指令所給出的地址除偏移地址之外的各部分全是各級(jí)頁(yè)表的頁(yè)表號(hào)或頁(yè)號(hào)，而各級(jí)頁(yè)表中記錄的全是物理頁(yè)號(hào)，指向下級(jí)頁(yè)表或真正的被訪問(wèn)頁(yè)。 OPERSTERING SYSTEM某計(jì)算機(jī)有32位虛地址空間，且頁(yè)大小為1024字節(jié)。每個(gè)頁(yè)表項(xiàng)長(zhǎng)4個(gè)字節(jié)。因?yàn)槊總€(gè)頁(yè)表都必須包含在一頁(yè)中，所以使用多級(jí)頁(yè)表，問(wèn)共需要幾級(jí)？ OPERSTERING SYSTEM反置頁(yè)表（反置頁(yè)表（Inverted Page TableInverted Page Table） 以上方法，每個(gè)進(jìn)程一張頁(yè)表，頁(yè)表按照進(jìn)程的邏輯地址順序排序，內(nèi)

33、容為物理塊號(hào)（頁(yè)框號(hào)）。反置頁(yè)表則按物理塊號(hào)的順序排序，內(nèi)容為隸屬的進(jìn)程ID及其頁(yè)號(hào)。實(shí)例：IBM AS/100、IBM RISC SYSTEM 6000等。在利用反置頁(yè)表進(jìn)行地址變換時(shí)，是利用進(jìn)程ID和頁(yè)號(hào)，檢索反置頁(yè)表，實(shí)際上可利用聯(lián)想存儲(chǔ)器來(lái)檢索。 OPERSTERING SYSTEMPIDP（頁(yè)號(hào)）d（頁(yè)內(nèi)偏移）反置頁(yè)表PIDP頁(yè)框號(hào)物理地址邏輯地址d（聯(lián)想存儲(chǔ)器） OPERSTERING SYSTEM pid page offset進(jìn)程標(biāo)識(shí)進(jìn)程標(biāo)識(shí) 特征位特征位 頁(yè)面號(hào)頁(yè)面號(hào) B offsetB反置頁(yè)表反置頁(yè)表物理地址物理地址邏輯地址邏輯地址 OPERSTERING SYSTEM哈希

34、頁(yè)表目前指令的地址位數(shù)普遍 32 位.頁(yè)號(hào)被散列到頁(yè)表。對(duì)具有相同散列值的頁(yè)表項(xiàng)，可一通過(guò)鏈表實(shí)現(xiàn)在一個(gè)位置上存放多個(gè)頁(yè)框號(hào)。頁(yè)號(hào)與鏈表中的鏈接元素包含的頁(yè)號(hào)依次比較，如果匹配即可取得相應(yīng)的物理頁(yè)框號(hào)。 OPERSTERING SYSTEM哈希頁(yè)表 OPERSTERING SYSTEM4.4 4.4 分段存儲(chǔ)管理分段存儲(chǔ)管理 分頁(yè)管理的方法，提高內(nèi)存的利用率，對(duì)程序員是透明的；分段管理的方法，滿(mǎn)足了程序員在編程和使用上的要求，適應(yīng)軟件工程開(kāi)發(fā)上的要求。將程序的地址空間劃分為若干個(gè)段(segment)，程序加載時(shí)，分配其所需的所有段（內(nèi)存分區(qū)），這些段不必連續(xù)；物理內(nèi)存的管理采用動(dòng)態(tài)分區(qū)。需要C

35、PU的硬件支持。 OPERSTERING SYSTEM分段系統(tǒng)的基本原理分段系統(tǒng)的基本原理 一、分段 邏輯地址：32 最大段長(zhǎng)： ； 最多有 個(gè)段 162162段號(hào)段內(nèi)地址0151631 OPERSTERING SYSTEM二、段表：由段基址和段長(zhǎng)組成。 作業(yè)空間(MAIN)0030K(X)1020K(D)2015K(S)3010K30K20K15K10K40K80K120K150K段長(zhǎng)基址段號(hào)(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表內(nèi)存空間0123 OPERSTERING SYSTEM三、地址變換機(jī)構(gòu) ：控制寄存器段表始址段表長(zhǎng)度210

36、0段號(hào)S越界1 K段長(zhǎng)600段號(hào)01236 K4 K5002008 K9200基址位移量 W82928K82928692主存物理地址有效地址 OPERSTERING SYSTEM段表始址段表始址 段表長(zhǎng)度段表長(zhǎng)度作業(yè)名作業(yè)名A段表始址段表始址xxxxxx段表長(zhǎng)度段表長(zhǎng)度3作業(yè)表作業(yè)表限長(zhǎng)限長(zhǎng)比較比較段號(hào)段號(hào) 段內(nèi)地址段內(nèi)地址段表段表段表控制寄存器段表控制寄存器絕對(duì)地址絕對(duì)地址邏輯地址邏輯地址地址越界地址越界始址始址+ OPERSTERING SYSTEM四、分頁(yè)和分段的主要區(qū)別 (1) 頁(yè)是物理單位，而段是邏輯單位。分頁(yè)是出于系統(tǒng)管理的需要，分段是出于用戶(hù)應(yīng)用的需要。因此，一條指令或一個(gè)操作數(shù)

37、可能會(huì)跨越兩個(gè)頁(yè)的分界處，而不會(huì)跨越兩個(gè)段的分界處。 (2) 頁(yè)大小是系統(tǒng)固定的，而段大小則通常不固定。 (3) 邏輯地址表示：分頁(yè)是一維的，各個(gè)模塊在鏈接時(shí)必須組織成同一個(gè)地址空間；而分段是二維的，各個(gè)模塊在鏈接時(shí)可以每個(gè)段組織成一個(gè)地址空間。 在分頁(yè)中，只需要一個(gè)標(biāo)識(shí)符，即可表示一個(gè)地址，是一維的。分段時(shí)，既要給出段名，又需要給出段內(nèi)地址，是二維的。 (4) 通常段比頁(yè)大，因而段表比頁(yè)表短，可以縮短查找時(shí)間，提高訪問(wèn)速度。 OPERSTERING SYSTEM分段存儲(chǔ)管理方式的引入分段存儲(chǔ)管理方式的引入 1.方便編程按邏輯關(guān)系劃分段：有獨(dú)立的段名，邏輯地址均從0開(kāi)始。程序通過(guò)分段(segm

38、entation)劃分為多個(gè)模塊，如代碼段、數(shù)據(jù)段、共享段?？梢苑謩e編寫(xiě)和編譯。2. 分段共享：可以按段為單位來(lái)進(jìn)行共享3. 分段保護(hù)：可以針對(duì)不同類(lèi)型的段采取不同的保護(hù)4.動(dòng)態(tài)鏈接：通過(guò)動(dòng)態(tài)鏈接進(jìn)行代碼共享5.動(dòng)態(tài)增長(zhǎng) OPERSTERING SYSTEM6. 優(yōu)點(diǎn)：沒(méi)有內(nèi)碎片，外碎片可以通過(guò)內(nèi)存緊縮來(lái)消除。便于改變進(jìn)程占用空間的大小。7.缺點(diǎn)：進(jìn)程全部裝入內(nèi)存。8. 段式管理的數(shù)據(jù)結(jié)構(gòu)：進(jìn)程段表：描述組成進(jìn)程地址空間的各段，可以是指向系統(tǒng)段表中表項(xiàng)的索引。每段有段基址(base address)系統(tǒng)段表：系統(tǒng)內(nèi)所有占用段空閑段表：內(nèi)存中所有空閑段，可以結(jié)合到系統(tǒng)段表中 OPERSTERIN

39、G SYSTEM共享與保護(hù)共享與保護(hù) 比分頁(yè)系統(tǒng)更容易共享代碼。例如頁(yè)尺寸為4K，160K的程序需要維護(hù)40個(gè)頁(yè)表項(xiàng)，而分段系統(tǒng)只需要維護(hù)1個(gè)段表項(xiàng)。 OPERSTERING SYSTEM OPERSTERING SYSTEM段頁(yè)式存儲(chǔ)管理方式段頁(yè)式存儲(chǔ)管理方式 結(jié)合分段和分頁(yè)的優(yōu)點(diǎn)。一、基本原理段內(nèi)分頁(yè)管理。邏輯地址：段號(hào)S段內(nèi)頁(yè)號(hào)P頁(yè)內(nèi)偏移地址W OPERSTERING SYSTEM段表及其頁(yè)表： 段號(hào)狀態(tài)頁(yè)表大小頁(yè)表始址0111213041頁(yè)號(hào)狀態(tài)存儲(chǔ)塊#0111213041操作系統(tǒng)主存頁(yè)表段表段表大小段表始址段表寄存器 OPERSTERING SYSTEM二、地址變換過(guò)程 段表始 地址

40、段表長(zhǎng)度段表寄存器頁(yè)內(nèi)地址段號(hào)有效地址越界中斷+頁(yè)表長(zhǎng)度頁(yè)表始址段表頁(yè)號(hào)頁(yè)框物理地址頁(yè)表頁(yè)號(hào)段號(hào)+ OPERSTERING SYSTEM4.5 4.5 虛擬存儲(chǔ)器虛擬存儲(chǔ)器 前一章所介紹的各種存儲(chǔ)器管理方式，其共同的特點(diǎn)是要求將一個(gè)作業(yè)全部裝入內(nèi)存方能運(yùn)行，因而難以適應(yīng)：（1）作業(yè)的尺寸大于實(shí)際內(nèi)存的容量；（2）有大量的作業(yè)等待運(yùn)行，但實(shí)際內(nèi)存容量不足以及其全部裝入。因此必須找到一種合適的方法解決此類(lèi)問(wèn)題，從而引入了虛擬存儲(chǔ)器。 OPERSTERING SYSTEM虛擬存儲(chǔ)器的基本概念 實(shí)存：作業(yè)一次性全部裝入內(nèi)存，作業(yè)不能大于內(nèi)存的實(shí)際尺寸，大于往往采用覆蓋技術(shù)。程序的駐留性：阻塞時(shí)也在內(nèi)存

41、，交換技術(shù)，但裝入內(nèi)存的程序和數(shù)據(jù)不一定馬上使用。 OPERSTERING SYSTEM具體體現(xiàn)程序在執(zhí)行時(shí)，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過(guò)程調(diào)用指令。過(guò)程調(diào)用的嵌套深度一般不超過(guò)5，因此執(zhí)行的范圍不超過(guò)這組嵌套的過(guò)程。程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，而被多次執(zhí)行。程序中存在相當(dāng)多對(duì)一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，往往局限在較小范圍內(nèi)。 OPERSTERING SYSTEM虛擬存儲(chǔ)器的引入虛擬存儲(chǔ)器的引入 局部性原理(1) 局部性原理(principle of locality)：指程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域

42、。可以表現(xiàn)為：時(shí)間局部性，即一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問(wèn)和下次訪問(wèn)都集中在一個(gè)較短時(shí)期內(nèi)；空間局部性，即當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問(wèn)的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個(gè)較小區(qū)域內(nèi)。 OPERSTERING SYSTEM虛存的定義在一個(gè)操作系統(tǒng)下，如果不要求任意用戶(hù)程序?qū)嶋H占用的物理地址空間，大于或等于用戶(hù)程序的邏輯地址空間，而且這種功能的實(shí)現(xiàn)對(duì)用戶(hù)來(lái)說(shuō)是透明的，這稱(chēng)該操作系統(tǒng)實(shí)現(xiàn)了虛擬存儲(chǔ)管理技術(shù)，相應(yīng)的用戶(hù)進(jìn)程空間稱(chēng)為虛存空間或虛地址空間。其大小由指令的有效地址的寬度決定。虛擬存儲(chǔ)器是一種借助于外存空間，從而允許一個(gè)進(jìn)程在其運(yùn)行過(guò)程中部分地裝入內(nèi)存的技術(shù)。 OPERSTE

43、RING SYSTEM虛擬存儲(chǔ)的基本原理在程序裝入時(shí)，不需要將其全部讀入到內(nèi)存，而只需將當(dāng)前需要執(zhí)行的部分頁(yè)或段讀入到內(nèi)存，就可讓程序開(kāi)始執(zhí)行。在程序執(zhí)行過(guò)程中，如果需執(zhí)行的指令或訪問(wèn)的數(shù)據(jù)尚未在內(nèi)存（稱(chēng)為缺頁(yè)或缺段），則由處理器通知操作系統(tǒng)將相應(yīng)的頁(yè)或段調(diào)入到內(nèi)存，然后繼續(xù)執(zhí)行程序。另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的頁(yè)或段調(diào)出保存在外存上，從而騰出空間存放將要裝入的程序以及將要調(diào)入的頁(yè)或段具有請(qǐng)求調(diào)入和置換功能，只需程序的一部分在內(nèi)存就可執(zhí)行，對(duì)于動(dòng)態(tài)鏈接庫(kù)也可以請(qǐng)求調(diào)入 OPERSTERING SYSTEM引入虛擬存儲(chǔ)技術(shù)的好處可在較小的可用內(nèi)存中執(zhí)行較大的用戶(hù)程序；可在內(nèi)存中容納更多

44、程序并發(fā)執(zhí)行；不必影響編程時(shí)的程序結(jié)構(gòu)（與覆蓋技術(shù)比較）提供給用戶(hù)可用的虛擬內(nèi)存空間通常大于物理內(nèi)存(real memory) OPERSTERING SYSTEM虛擬存儲(chǔ)器的實(shí)現(xiàn)方式虛擬存儲(chǔ)器的實(shí)現(xiàn)方式 建立在離散分配存儲(chǔ)管理方式的基礎(chǔ)上請(qǐng)求分頁(yè)系統(tǒng)純分頁(yè)系統(tǒng)+請(qǐng)求調(diào)頁(yè)+頁(yè)面置換頁(yè)式虛擬存儲(chǔ)器實(shí)現(xiàn)機(jī)制：（1）請(qǐng)求分頁(yè)的頁(yè)表（2） 缺頁(yè)中斷（3） 地址變換需CPU MMU 支持 OPERSTERING SYSTEM請(qǐng)求分段系統(tǒng)純分段系統(tǒng)+請(qǐng)求調(diào)段+分段置換段式虛擬存儲(chǔ)器（1）請(qǐng)求分段的段表（2）缺段中斷（3） 地址變換需CPU MMU 支持段頁(yè)式虛擬存儲(chǔ)器 OPERSTERING SYSTEM

45、虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征 離散性、多次性、對(duì)換性、虛擬性。 物理內(nèi)存分配的不連續(xù)，虛擬地址空間使用的不連續(xù)（數(shù)據(jù)段和棧段之間的空閑空間，共享段和動(dòng)態(tài)鏈接庫(kù)占用的空間） 與交換的比較：調(diào)入和調(diào)出是對(duì)部分虛擬地址空間進(jìn)行 通過(guò)物理內(nèi)存和快速外存相結(jié)合，提供大范圍的虛擬地址空間 范圍大，但占用容量不超過(guò)物理內(nèi)存和外存交換區(qū)容量之和 占用容量包括：進(jìn)程地址空間中的各個(gè)段，操作系統(tǒng)代碼 OPERSTERING SYSTEM4.6 4.6 請(qǐng)求分頁(yè)存儲(chǔ)器管理方式請(qǐng)求分頁(yè)存儲(chǔ)器管理方式 在簡(jiǎn)單頁(yè)式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能,最常用方式。重要的數(shù)據(jù)結(jié)構(gòu)：頁(yè)表增加若干項(xiàng)，供os實(shí)現(xiàn)虛擬

46、存儲(chǔ)功能時(shí)參考。 OPERSTERING SYSTEM OPERSTERING SYSTEM請(qǐng)求分頁(yè)中的硬件支持請(qǐng)求分頁(yè)中的硬件支持 一、頁(yè)表機(jī)制增加換入換出所要求的必要信息。 頁(yè)號(hào)物理塊號(hào)狀態(tài)位P訪問(wèn)字段A修改位M外存地址狀態(tài)位P：存在位（present bit，內(nèi)存頁(yè)和外存頁(yè)）修改位M(modified bit):是否被修改過(guò)訪問(wèn)字段A：在近期內(nèi)被訪問(wèn)的次數(shù)，或最近一次訪問(wèn)到 現(xiàn)在的時(shí)間間隔外存地址：磁盤(pán)上的地址 ，供調(diào)入該頁(yè)時(shí)使用 OPERSTERING SYSTEM二、缺頁(yè)中斷機(jī)構(gòu)由處理器的地址變換機(jī)構(gòu)產(chǎn)生缺頁(yè)中斷，然后調(diào)用操作系統(tǒng)提供的中斷處理例程。缺頁(yè)中斷的特殊性： 缺頁(yè)中斷在指令

47、執(zhí)行期間產(chǎn)生和進(jìn)行處理，而不是在一條指令執(zhí)行完畢之后。所缺的頁(yè)面調(diào)入之后，重新執(zhí)行被中斷的指令。一條指令的執(zhí)行可能產(chǎn)生多次缺頁(yè)中斷， 如：swap A, B 而指令本身和兩個(gè)操作數(shù)A, B都跨越相鄰?fù)獯骓?yè)的分界處，則產(chǎn)生5次缺頁(yè)中斷（不可能出現(xiàn)指令本身的兩次缺頁(yè)）。必須由CPU硬件確保對(duì)多個(gè)現(xiàn)場(chǎng)的保存。 OPERSTERING SYSTEM頁(yè)面0123456SAWP A,BAB OPERSTERING SYSTEM OPERSTERING SYSTEM三、地址變換機(jī)構(gòu) OPERSTERING SYSTEM缺頁(yè)處理過(guò)程小結(jié)：缺頁(yè)處理過(guò)程小結(jié)：(1)(1)硬件陷阱進(jìn)入核心，保存硬件陷阱進(jìn)入核心，保

48、存PCPC到棧中，大多數(shù)機(jī)器將當(dāng)前各種狀態(tài)保存到棧中，大多數(shù)機(jī)器將當(dāng)前各種狀態(tài)保存在特殊的寄存器中。在特殊的寄存器中。(2)(2)啟動(dòng)一個(gè)匯編程序代碼保存通用寄存器和其它重要的動(dòng)態(tài)信息，以免啟動(dòng)一個(gè)匯編程序代碼保存通用寄存器和其它重要的動(dòng)態(tài)信息，以免被操作系統(tǒng)破壞。被操作系統(tǒng)破壞。(3)(3)操作系統(tǒng)發(fā)現(xiàn)一個(gè)缺頁(yè)時(shí)，查找需要哪個(gè)虛頁(yè)。（通常一個(gè)硬件寄存操作系統(tǒng)發(fā)現(xiàn)一個(gè)缺頁(yè)時(shí)，查找需要哪個(gè)虛頁(yè)。（通常一個(gè)硬件寄存器含有該信息）器含有該信息）(4)(4)一旦知道了發(fā)生缺頁(yè)的虛擬地址，操作系統(tǒng)檢查這個(gè)地址是否有效，一旦知道了發(fā)生缺頁(yè)的虛擬地址，操作系統(tǒng)檢查這個(gè)地址是否有效，如無(wú)效，向進(jìn)程發(fā)一個(gè)信號(hào)或

49、殺死進(jìn)程（如無(wú)效，向進(jìn)程發(fā)一個(gè)信號(hào)或殺死進(jìn)程（UNIXUNIX）；）；若有效也沒(méi)有保護(hù)錯(cuò)誤若有效也沒(méi)有保護(hù)錯(cuò)誤發(fā)生，系統(tǒng)則從空閑頁(yè)框中選一個(gè)頁(yè)框分配，如果沒(méi)有空閑頁(yè)框，執(zhí)行頁(yè)發(fā)生，系統(tǒng)則從空閑頁(yè)框中選一個(gè)頁(yè)框分配，如果沒(méi)有空閑頁(yè)框，執(zhí)行頁(yè)面置換算法找一個(gè)頁(yè)淘汰。面置換算法找一個(gè)頁(yè)淘汰。(5)(5)若選擇淘汰的頁(yè)框不若選擇淘汰的頁(yè)框不“臟臟”，直接到，直接到(6),(6),否則該頁(yè)寫(xiě)回磁盤(pán)，并發(fā)生否則該頁(yè)寫(xiě)回磁盤(pán)，并發(fā)生一次進(jìn)程切換（暫停本進(jìn)程，讓其它進(jìn)程運(yùn)行到頁(yè)面寫(xiě)完成，在這期間，一次進(jìn)程切換（暫停本進(jìn)程，讓其它進(jìn)程運(yùn)行到頁(yè)面寫(xiě)完成，在這期間，該頁(yè)框標(biāo)志忙，以免被占用）該頁(yè)框標(biāo)志忙，以免被占用

50、）(6)(6)頁(yè)框頁(yè)框 “ “干凈干凈”后，操作系統(tǒng)查找磁盤(pán)上所需調(diào)入的頁(yè)，通過(guò)磁盤(pán)操作后，操作系統(tǒng)查找磁盤(pán)上所需調(diào)入的頁(yè)，通過(guò)磁盤(pán)操作策略將其裝入。（在這期間，產(chǎn)生缺頁(yè)的進(jìn)程仍然掛起，而其它正在運(yùn)行策略將其裝入。（在這期間，產(chǎn)生缺頁(yè)的進(jìn)程仍然掛起，而其它正在運(yùn)行的進(jìn)程也依然在運(yùn)行）的進(jìn)程也依然在運(yùn)行） OPERSTERING SYSTEM(7)(7)當(dāng)傳送完成，磁盤(pán)發(fā)生中斷，表明該頁(yè)已經(jīng)裝入，更新頁(yè)表有關(guān)項(xiàng)以當(dāng)傳送完成，磁盤(pán)發(fā)生中斷，表明該頁(yè)已經(jīng)裝入，更新頁(yè)表有關(guān)項(xiàng)以表明正確的狀態(tài)。表明正確的狀態(tài)。(8)(8)恢復(fù)發(fā)生缺頁(yè)指令以前的狀態(tài)，程序計(jì)數(shù)器重新指向這條指令?；謴?fù)發(fā)生缺頁(yè)指令以前的狀態(tài)

51、，程序計(jì)數(shù)器重新指向這條指令。(9)(9)缺頁(yè)進(jìn)程恢復(fù)，操作系統(tǒng)返回調(diào)用它的匯編語(yǔ)言例程。缺頁(yè)進(jìn)程恢復(fù)，操作系統(tǒng)返回調(diào)用它的匯編語(yǔ)言例程。(10)(10)該例程恢復(fù)寄存器和其它重要的動(dòng)態(tài)信息，回到用戶(hù)空間繼續(xù)執(zhí)行，該例程恢復(fù)寄存器和其它重要的動(dòng)態(tài)信息，回到用戶(hù)空間繼續(xù)執(zhí)行，就好象缺頁(yè)沒(méi)有發(fā)生過(guò)一樣就好象缺頁(yè)沒(méi)有發(fā)生過(guò)一樣 OPERSTERING SYSTEM查快表查快表有登記有登記無(wú)登記無(wú)登記查頁(yè)表查頁(yè)表登記入快表登記入快表發(fā)缺頁(yè)中斷發(fā)缺頁(yè)中斷在主存在主存在輔存在輔存形成絕對(duì)地址形成絕對(duì)地址繼續(xù)執(zhí)行指令繼續(xù)執(zhí)行指令重新執(zhí)行重新執(zhí)行被中斷指令被中斷指令恢復(fù)現(xiàn)場(chǎng)恢復(fù)現(xiàn)場(chǎng)調(diào)整頁(yè)表和調(diào)整頁(yè)表和主存分配

52、表主存分配表裝入所需頁(yè)面裝入所需頁(yè)面主存有空閑塊主存有空閑塊保護(hù)現(xiàn)場(chǎng)保護(hù)現(xiàn)場(chǎng)有有選擇調(diào)出頁(yè)面選擇調(diào)出頁(yè)面該頁(yè)是否修改該頁(yè)是否修改未修改未修改已修改已修改把該頁(yè)寫(xiě)回把該頁(yè)寫(xiě)回輔存相應(yīng)位置輔存相應(yīng)位置操作系統(tǒng)操作系統(tǒng)硬件硬件邏輯地址邏輯地址無(wú)無(wú) OPERSTERING SYSTEM OPERSTERING SYSTEM頁(yè)面分配策略?xún)?nèi)存分配策略包括： 分配時(shí)機(jī) 分配數(shù)量 分配位置 調(diào)度策略 OPERSTERING SYSTEM何時(shí)分配與裝入立即調(diào)頁(yè)：在進(jìn)程開(kāi)始執(zhí)行之前分配與裝入。請(qǐng)求調(diào)頁(yè)：只有在實(shí)際訪問(wèn)某頁(yè)時(shí)才通過(guò)發(fā)生缺頁(yè)中斷處理程序分配。優(yōu)點(diǎn)：容易實(shí)現(xiàn)。缺點(diǎn)：對(duì)外存I/O次數(shù)多，開(kāi)銷(xiāo)較大，要求I/

53、O速度快。預(yù)先調(diào)頁(yè)：由操作系統(tǒng)根據(jù)一定的算法，動(dòng)態(tài)預(yù)測(cè)將來(lái)最近時(shí)間最可能要訪問(wèn)那些頁(yè)，并在這些頁(yè)實(shí)際訪問(wèn)之前預(yù)先調(diào)入。 發(fā)生的時(shí)機(jī)：缺頁(yè)中斷時(shí) 頁(yè)簇化優(yōu)點(diǎn)：提高調(diào)頁(yè)的I/O效率。缺點(diǎn)：基于預(yù)測(cè)，若調(diào)入的頁(yè)在以后很少被訪問(wèn)，則效率低。常用于程序裝入時(shí)的調(diào)頁(yè) OPERSTERING SYSTEM從何處調(diào)入頁(yè)面文件區(qū)或交換區(qū)。 外存通常分為外存通常分為文件區(qū)和和交換區(qū)。通常外存交換區(qū)的。通常外存交換區(qū)的I/OI/O效效率比文件區(qū)的高（通過(guò)采取文件連續(xù)存放，加大物理塊容率比文件區(qū)的高（通過(guò)采取文件連續(xù)存放，加大物理塊容量等措施）。量等措施）。關(guān)于調(diào)入頁(yè)面的來(lái)源，這里有幾種做法：進(jìn)程裝入時(shí)，將其全部頁(yè)面

54、復(fù)制到交換區(qū)，以后總是從交換區(qū)調(diào)入。執(zhí)行時(shí)調(diào)入速度快，要求交換區(qū)空間較大。凡不會(huì)修改的頁(yè)面或是未被修改的頁(yè)面，直接從文件區(qū)調(diào)入，換出時(shí)不必寫(xiě)回磁盤(pán)，下次仍從文件區(qū)調(diào)入。已被修改的頁(yè)面，被置換時(shí)需調(diào)出到交換區(qū)，以后從交換區(qū)調(diào)入。節(jié)省交換區(qū)空間。UNIX方式，未運(yùn)行過(guò)的頁(yè)面，直接從文件區(qū)調(diào)入，而曾經(jīng)運(yùn)行過(guò)的頁(yè)面，換出時(shí)放在對(duì)換區(qū)，下次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。在進(jìn)程結(jié)束時(shí)，更新文件區(qū)內(nèi)容。 OPERSTERING SYSTEM頁(yè)面分配分配數(shù)量頁(yè)面分配分配數(shù)量 為每個(gè)進(jìn)程分配多少個(gè)頁(yè)框？如何分？目的：減少缺頁(yè)中斷。一、最小物理塊數(shù)保證進(jìn)程運(yùn)行的至少要分配的物理塊數(shù)，少了則無(wú)法運(yùn)行。如何預(yù)測(cè)？與指令系統(tǒng)

55、有關(guān)：?jiǎn)蔚刂非抑苯訉ぶ罚?個(gè)頁(yè)面；若支持間接尋址：則至少需要3個(gè)頁(yè)面；如上，最多至少需要6個(gè)。 OPERSTERING SYSTEM二、頁(yè)面分配和置換策略1 固定分配局部置換（Fixed Allocation, Local Replacement） 給每個(gè)進(jìn)程分配固定數(shù)目的頁(yè)框，當(dāng)發(fā)生缺頁(yè)中斷缺頁(yè)中斷時(shí)，只考慮從該進(jìn)程所屬的頁(yè)框中調(diào)出舊的頁(yè)面，從而換入新的頁(yè)面。 困難在于分配多少個(gè)頁(yè)框合適？少了中斷頻繁，多了內(nèi)存裝入的進(jìn)程減少。 2 可變分配全局置換（Variable Allocation, Global Replacement） 預(yù)分配給進(jìn)程一定數(shù)目的頁(yè)框，OS控制一定數(shù)量的空閑頁(yè)框，在進(jìn)程

56、的執(zhí)行過(guò)程中，發(fā)生缺頁(yè)時(shí)，OS就分配給該進(jìn)程一個(gè)空閑的頁(yè)框，當(dāng)空閑的頁(yè)框用完時(shí)，OS可根據(jù)需要從任意的進(jìn)程中調(diào)出一個(gè)頁(yè)框。會(huì)有不公平。 OPERSTERING SYSTEM3 可變分配局部置換（Variable Allocation, Local Replacement） 預(yù)分配給進(jìn)程一定數(shù)目的頁(yè)框，OS控制一定數(shù)量的空閑頁(yè)框，在進(jìn)程的執(zhí)行過(guò)程中，發(fā)生缺頁(yè)時(shí)，首先考慮從該進(jìn)程所屬的頁(yè)框中調(diào)出舊的頁(yè)面，若發(fā)現(xiàn)該進(jìn)程頻繁發(fā)生缺頁(yè)中斷，這時(shí)可分配新的頁(yè)框給該進(jìn)程。統(tǒng)計(jì)進(jìn)程的缺頁(yè)中斷率系統(tǒng)會(huì)有開(kāi)銷(xiāo)。 OPERSTERING SYSTEM三、分配算法1. 平均分配2. 按比例分配3. 按優(yōu)先權(quán)分配mSs

57、pamsSpsiiiiii分配的頁(yè)框數(shù)為進(jìn)程總共可用的頁(yè)框數(shù)的大小進(jìn)程 5964137127564137101271064212aassmi OPERSTERING SYSTEM頁(yè)長(zhǎng)和頁(yè)簇化頁(yè)大小通常為2的指數(shù)冪簡(jiǎn)化計(jì)算 例如：頁(yè)長(zhǎng)為2NB，則邏輯地址的低N位即為頁(yè)內(nèi)位移，剩余的高位是邏輯頁(yè)號(hào)。頁(yè)長(zhǎng)的確定 OPERSTERING SYSTEM4.3 4.3 頁(yè)面置換算法頁(yè)面置換算法 (1) 功能：需要調(diào)入頁(yè)面時(shí)，選擇內(nèi)存中哪個(gè)物理頁(yè)面被置換。稱(chēng)為replacement policy。(2) 目標(biāo)（出發(fā)點(diǎn)）：降低頁(yè)面更換率，應(yīng)把未來(lái)不再使用的或短期內(nèi)較少使用的頁(yè)面調(diào)出，通常只能在局部性原理指導(dǎo)下

58、依據(jù)過(guò)去的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行預(yù)測(cè)；相反會(huì)有“抖動(dòng)”。(3) 頁(yè)面鎖定(frame locking)：用于描述必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分或時(shí)間關(guān)鍵(time-critical)的應(yīng)用進(jìn)程。實(shí)現(xiàn)方法為在頁(yè)表中加上鎖定標(biāo)志位(lock bit)。 OPERSTERING SYSTEM1.先來(lái)先服務(wù)（先來(lái)先服務(wù)（FIFO）在內(nèi)存時(shí)間最長(zhǎng)的頁(yè)最先被淘汰. Time t | 0| 1 2 3 4 5 6 7 8 9 10 11 12RS | | a b c d a b e a b c d e Frame 0| | a a a d d d e e e e e eFrame 1| | b b b a a a

59、a a c c cFrame 2| | c c c b b b b b d d IN | | a b c d a b e c dOUT | | a b c d a b OPERSTERING SYSTEMTime t | 0| 1 2 3 4 5 6 7 8 9 10 11 12RS | | a b c d a b e a b c d e Frame 0| |a a a a a a e e e e d dFrame 1| | b b b b b b a a a a eFrame 2| | c c c c c c b b b bFrame 3| | d d d d d d c c c IN |

60、| a b c d e a b c d eOUT | | a b c d e aMore Frames Fewer Page Faults?Beladys Anomaly: more frames more page faults OPERSTERING SYSTEMBelady現(xiàn)象的描述：一個(gè)進(jìn)程P要訪問(wèn)M個(gè)頁(yè)，OS分配N(xiāo)個(gè)內(nèi)存頁(yè)面給進(jìn)程P；對(duì)一個(gè)訪問(wèn)序列S，發(fā)生缺頁(yè)次數(shù)為PE（S,N）。當(dāng)N增大時(shí)，PE(S, N)時(shí)而增大，時(shí)而減小。Belady現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問(wèn)內(nèi)存的動(dòng)態(tài)特征是矛盾的，即被置換的頁(yè)面并不是進(jìn)程不會(huì)訪問(wèn)的。 OPERSTERING SYSTEM引用