操作系統(tǒng)_第4章_存儲器管理

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

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

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

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

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

6、 L1 指令在變成可執(zhí)行代碼后，該指令的地址場的數(shù)據(jù)是指令在變成可執(zhí)行代碼后，該指令的地址場的數(shù)據(jù)是一定的。這就意味該程序只能放在固定的地方。一定的。這就意味該程序只能放在固定的地方。diskdiskJMP 200JMP 200loadloadJMP 200JMP 200MOV AX, 201MOV AX, 2011000100012001200 OPERSTERING SYSTEM優(yōu)點：裝入過程簡單。缺點：過于依賴于硬件結構，不適于多道程序系統(tǒng)。 OPERSTERING SYSTEM0000 .1000 . .11001102110411061108 . . . .物理內存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在裝入前鏈接所假設的程序地址與此時裝入的實際地址不一致。在可執(zhí)行文件中，列出各個需要重定位的地址單元和相對地址值，裝入時再根據(jù)所定位的內存地址去修改每個重定位地址項，添加相應偏移量。 可重定位裝入（靜態(tài)） (relocatable loading) OPERSTERING S

8、YSTEM重定位分類:靜態(tài)重定位Load R1,106Add R1,108Store R1,110234128程序A的代碼0001001021041061080000 .1000 . .11001102110411061108 . . . .物理內存OSLoad R1,1106Add R1,1108Store R1,1110234128加載時定位Load R1,1106Add R1,1108Store R1,1110234128例：例：MZMZ10100201頭標志頭標志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ù)讀入的頭對內存浮動項的頭對內存浮動項裝配裝配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ù)讀入的頭對內存浮動項的頭對內存浮動項裝配裝配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ù)讀入的頭對內存浮動項的頭對內存浮動項裝配裝配 OPERSTERING SYSTEMjmp150100150.RelocationTable0jm2000 OPERSTERING SYSTEM優(yōu)點：不需硬件支持，可以裝入有限多道程序.缺點：一個程序通常需要占用連續(xù)的內存空間，程序裝入內存后不能移動。不易實現(xiàn)共享。 OPERSTERING SYSTEM 動態(tài)運行期裝入（動態(tài)重地位）動態(tài)運行期裝入（動態(tài)重地位）( (dynamic run-time loading)dynamic run-ti

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

55、有關：單地址且直接尋址：2個頁面；若支持間接尋址：則至少需要3個頁面；如上，最多至少需要6個。 OPERSTERING SYSTEM二、頁面分配和置換策略1 固定分配局部置換（Fixed Allocation, Local Replacement） 給每個進程分配固定數(shù)目的頁框，當發(fā)生缺頁中斷缺頁中斷時，只考慮從該進程所屬的頁框中調出舊的頁面，從而換入新的頁面。 困難在于分配多少個頁框合適？少了中斷頻繁，多了內存裝入的進程減少。 2 可變分配全局置換（Variable Allocation, Global Replacement） 預分配給進程一定數(shù)目的頁框，OS控制一定數(shù)量的空閑頁框，在進程

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

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

58、依據(jù)過去的統(tǒng)計數(shù)據(jù)進行預測；相反會有“抖動”。(3) 頁面鎖定(frame locking)：用于描述必須常駐內存的操作系統(tǒng)的關鍵部分或時間關鍵(time-critical)的應用進程。實現(xiàn)方法為在頁表中加上鎖定標志位(lock bit)。 OPERSTERING SYSTEM1.先來先服務（先來先服務（FIFO）在內存時間最長的頁最先被淘汰. 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)象的描述：一個進程P要訪問M個頁，OS分配N個內存頁面給進程P；對一個訪問序列S，發(fā)生缺頁次數(shù)為PE（S,N）。當N增大時，PE(S, N)時而增大，時而減小。Belady現(xiàn)象的原因：FIFO算法的置換特征與進程訪問內存的動態(tài)特征是矛盾的，即被置換的頁面并不是進程不會訪問的。 OPERSTERING SYSTEM引用