Windows操作系統(tǒng)-存儲管理(上)

1、1 第四章第四章 存儲管理存儲管理( (上上) ) 存儲管理概述存儲管理概述 內(nèi)存管理的基本原理內(nèi)存管理的基本原理 Windows 的的內(nèi)存管理內(nèi)存管理 外存管理外存管理的基本原理的基本原理 Windows 的的外存管理外存管理 高速緩存管理高速緩存管理的基本原理的基本原理 Windows 的的高速緩存管理高速緩存管理 2 存儲體系存儲體系 存儲管理的功能存儲管理的功能 邏輯地址和物理地址邏輯地址和物理地址 重定位技術(shù)重定位技術(shù) 3 高速緩存：高速緩存： Data Cache TLB(Translation Lookaside Buffer) 內(nèi)存：內(nèi)存：DRAM, SDRAM等；等； 外存：

2、軟盤、硬盤、光盤、磁帶等；外存：軟盤、硬盤、光盤、磁帶等； 外存(secondary storage) DOS核心 命令處理程序 內(nèi)存(primary storage) 高速緩存(cache) 寄存器(register) 4 存儲分配和回收存儲分配和回收：分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。：分配和回收算法及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。 地址變換地址變換： 可執(zhí)行文件生成中的鏈接技術(shù)可執(zhí)行文件生成中的鏈接技術(shù) 程序加載程序加載(裝入裝入)時(shí)的重定位技術(shù)時(shí)的重定位技術(shù) 進(jìn)程運(yùn)行時(shí)硬件和軟件的地址變換技術(shù)和機(jī)構(gòu)進(jìn)程運(yùn)行時(shí)硬件和軟件的地址變換技術(shù)和機(jī)構(gòu) 存儲共享和保護(hù)存儲共享和保護(hù)： 代碼和數(shù)據(jù)共享代碼和數(shù)據(jù)共享

3、地址空間訪問權(quán)限（讀、寫、執(zhí)行）地址空間訪問權(quán)限（讀、寫、執(zhí)行） 存儲器擴(kuò)充存儲器擴(kuò)充：存儲器的邏輯組織和物理組織；：存儲器的邏輯組織和物理組織； 由應(yīng)用程序控制：覆蓋；由應(yīng)用程序控制：覆蓋； 由由OS控制：交換（整個(gè)進(jìn)程空間），虛擬存儲的請求調(diào)入和控制：交換（整個(gè)進(jìn)程空間），虛擬存儲的請求調(diào)入和 預(yù)調(diào)入（部分進(jìn)程空間）預(yù)調(diào)入（部分進(jìn)程空間） 5 邏輯地址邏輯地址（相對地址，虛地址）：用戶的程序經(jīng)過匯（相對地址，虛地址）：用戶的程序經(jīng)過匯 編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地編或編譯后形成目標(biāo)代碼，目標(biāo)代碼通常采用相對地 址的形式。址的形式。 其首地址為其首地址為0，其余指令中的地址

4、都相對于首地址來編址。，其余指令中的地址都相對于首地址來編址。 不能用邏輯地址在內(nèi)存中讀取信息。不能用邏輯地址在內(nèi)存中讀取信息。 物理地址物理地址（絕對地址，實(shí)地址）：內(nèi)存中存儲單元的（絕對地址，實(shí)地址）：內(nèi)存中存儲單元的 地址。物理地址可直接尋址。地址。物理地址可直接尋址。 地址映射地址映射：將用戶程序中的邏輯地址轉(zhuǎn)換為運(yùn)行時(shí)由：將用戶程序中的邏輯地址轉(zhuǎn)換為運(yùn)行時(shí)由 機(jī)器直接尋址的物理地址。機(jī)器直接尋址的物理地址。 當(dāng)程序裝入內(nèi)存時(shí)當(dāng)程序裝入內(nèi)存時(shí), 操作系統(tǒng)要為該程序分配一個(gè)合適的內(nèi)操作系統(tǒng)要為該程序分配一個(gè)合適的內(nèi) 存空間，由于存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致程序的邏

5、輯地址與分配到內(nèi)存物理地址不一致, 而而CPU執(zhí)行指令時(shí)，是按物理地址進(jìn)行的，所以要進(jìn)行地執(zhí)行指令時(shí)，是按物理地址進(jìn)行的，所以要進(jìn)行地 址轉(zhuǎn)換。址轉(zhuǎn)換。 6 地址映射地址映射 BA=1000 3456 。 。 。 。 。 。 1200 物理地址空間物理地址空間 mov ax, data1 data1 3456 源程序源程序 mov ax, 200 3456 0 100 200 編譯連接編譯連接 邏輯地址空間邏輯地址空間 mov ax, 1200 1000 1100 7 重定位：在可執(zhí)行文件裝入時(shí)需要解決可執(zhí)行文件重定位：在可執(zhí)行文件裝入時(shí)需要解決可執(zhí)行文件 中地址（指令和數(shù)據(jù)）和內(nèi)存地址的對應(yīng)

6、。由操作中地址（指令和數(shù)據(jù)）和內(nèi)存地址的對應(yīng)。由操作 系統(tǒng)中的裝入程序來完成。系統(tǒng)中的裝入程序來完成。 重定位方法：重定位方法： 絕對裝入絕對裝入 可重定位裝入可重定位裝入 動態(tài)裝入動態(tài)裝入 8 優(yōu)點(diǎn)：裝入過程簡單。優(yōu)點(diǎn)：裝入過程簡單。 缺點(diǎn)：過于依賴于硬件結(jié)構(gòu)，不適于多缺點(diǎn)：過于依賴于硬件結(jié)構(gòu)，不適于多 道程序系統(tǒng)。道程序系統(tǒng)。 在可執(zhí)行文件中記錄內(nèi)存地址，裝入時(shí)直接定在可執(zhí)行文件中記錄內(nèi)存地址，裝入時(shí)直接定 位在上述位在上述(即文件中記錄的地址即文件中記錄的地址)內(nèi)存地址。內(nèi)存地址。 9 優(yōu)點(diǎn)：不需硬件支持，可以裝入有限多道程序優(yōu)點(diǎn)：不需硬件支持，可以裝入有限多道程序 缺點(diǎn)：一個(gè)程序通常需

7、要占用連續(xù)的內(nèi)存空間，缺點(diǎn)：一個(gè)程序通常需要占用連續(xù)的內(nèi)存空間， 程序裝入內(nèi)存后不能移動。不易實(shí)現(xiàn)共享。程序裝入內(nèi)存后不能移動。不易實(shí)現(xiàn)共享。 在可執(zhí)行文件中，在可執(zhí)行文件中，列出列出各個(gè)需要重定位的地址單元和各個(gè)需要重定位的地址單元和 相對地址值。當(dāng)用戶程序被裝入內(nèi)存時(shí)，相對地址值。當(dāng)用戶程序被裝入內(nèi)存時(shí)，一次性一次性實(shí)現(xiàn)實(shí)現(xiàn) 邏輯地址到物理地址的邏輯地址到物理地址的轉(zhuǎn)換轉(zhuǎn)換，以后不再轉(zhuǎn)換（一般在，以后不再轉(zhuǎn)換（一般在 裝入內(nèi)存時(shí)由軟件完成）。即：裝入時(shí)根據(jù)所定位的裝入內(nèi)存時(shí)由軟件完成）。即：裝入時(shí)根據(jù)所定位的 內(nèi)存地址去修改每個(gè)重定位地址項(xiàng)，添加相應(yīng)偏移內(nèi)存地址去修改每個(gè)重定位地址項(xiàng)，添加

8、相應(yīng)偏移 量。量。 10 優(yōu)點(diǎn)：優(yōu)點(diǎn)： OS可以將一個(gè)程序分散存放于不連續(xù)的內(nèi)存空間，可以可以將一個(gè)程序分散存放于不連續(xù)的內(nèi)存空間，可以 移動程序，有利用實(shí)現(xiàn)共享。移動程序，有利用實(shí)現(xiàn)共享。 能夠支持程序執(zhí)行中產(chǎn)生的地址引用，如指針變量（而能夠支持程序執(zhí)行中產(chǎn)生的地址引用，如指針變量（而 不僅是生成可執(zhí)行文件時(shí)的地址引用）。不僅是生成可執(zhí)行文件時(shí)的地址引用）。 缺點(diǎn)：需要硬件支持（通常是缺點(diǎn)：需要硬件支持（通常是CPU），），OS實(shí)現(xiàn)較復(fù)實(shí)現(xiàn)較復(fù) 雜。它是虛擬存儲的基礎(chǔ)。雜。它是虛擬存儲的基礎(chǔ)。 在可執(zhí)行文件中記錄虛擬內(nèi)存地址，裝入和執(zhí)行時(shí)通在可執(zhí)行文件中記錄虛擬內(nèi)存地址，裝入和執(zhí)行時(shí)通 過硬

9、件地址變換機(jī)構(gòu)，完成虛擬地址到實(shí)際內(nèi)存地址過硬件地址變換機(jī)構(gòu)，完成虛擬地址到實(shí)際內(nèi)存地址 的變換。的變換。 11 單一連續(xù)區(qū)存儲管理單一連續(xù)區(qū)存儲管理 分區(qū)存儲管理分區(qū)存儲管理 頁式和段式存儲管理頁式和段式存儲管理 虛擬存儲器虛擬存儲器 12 內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用 戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，戶區(qū)。應(yīng)用程序裝入到用戶區(qū)， 可使用用戶區(qū)全部空間?？墒褂糜脩魠^(qū)全部空間。 最簡單，適用于單用戶、單任務(wù)最簡單，適用于單用戶、單任務(wù) 的的OS。 優(yōu)點(diǎn)優(yōu)點(diǎn)：易于管理。：易于管理。 缺點(diǎn)缺點(diǎn)：對要求內(nèi)存空間少的程序，：對要求內(nèi)存空間少的程序， 造成內(nèi)存浪費(fèi)；程序全部裝入，

10、造成內(nèi)存浪費(fèi)；程序全部裝入， 很少使用的程序部分也占用內(nèi)存。很少使用的程序部分也占用內(nèi)存。 用戶程序用戶程序 操作系統(tǒng)操作系統(tǒng) 0 xFFFF 0 x0000 13 把內(nèi)存分為一些大小相等或不等的分區(qū)把內(nèi)存分為一些大小相等或不等的分區(qū) (partition)，每個(gè)進(jìn)程占用一個(gè)或幾個(gè)分區(qū)。操，每個(gè)進(jìn)程占用一個(gè)或幾個(gè)分區(qū)。操 作系統(tǒng)占用其中一個(gè)分區(qū)。作系統(tǒng)占用其中一個(gè)分區(qū)。 特點(diǎn)：適用于多道程序系統(tǒng)和分時(shí)系統(tǒng)特點(diǎn)：適用于多道程序系統(tǒng)和分時(shí)系統(tǒng) 支持多個(gè)程序并發(fā)執(zhí)行支持多個(gè)程序并發(fā)執(zhí)行 難以進(jìn)行內(nèi)存分區(qū)的共享。難以進(jìn)行內(nèi)存分區(qū)的共享。 問題：可能存在內(nèi)碎片和外碎片。問題：可能存在內(nèi)碎片和外碎片。 內(nèi)

11、碎片：占用分區(qū)之內(nèi)未被利用的空間內(nèi)碎片：占用分區(qū)之內(nèi)未被利用的空間 外碎片：占用分區(qū)之間難以利用的空閑分區(qū)（通常是外碎片：占用分區(qū)之間難以利用的空閑分區(qū)（通常是 小空閑分區(qū)）。小空閑分區(qū)）。 14 分區(qū)大小相等：只適合于多個(gè)相分區(qū)大小相等：只適合于多個(gè)相 同程序的并發(fā)執(zhí)行（處理多個(gè)類同程序的并發(fā)執(zhí)行（處理多個(gè)類 型相同的對象）。型相同的對象）。 分區(qū)大小不等：多個(gè)小分區(qū)、適分區(qū)大小不等：多個(gè)小分區(qū)、適 量的中等分區(qū)、少量的大分區(qū)。量的中等分區(qū)、少量的大分區(qū)。 根據(jù)程序的大小，分配當(dāng)前空閑根據(jù)程序的大小，分配當(dāng)前空閑 的、適當(dāng)大小的分區(qū)。的、適當(dāng)大小的分區(qū)。 把內(nèi)存劃分為若干個(gè)固定大小的連續(xù)分區(qū)

12、。把內(nèi)存劃分為若干個(gè)固定大小的連續(xù)分區(qū)。 15 8 M 8 M 8 M 8 M 8 M Operating System Operating System 8 M 12 M 8 M 8 M 6 M 4 M 2 M 固定分區(qū)(大小相同) 固定分區(qū)(多種大小) 16 動態(tài)創(chuàng)建分區(qū)：在裝入程序時(shí)按動態(tài)創(chuàng)建分區(qū)：在裝入程序時(shí)按 其初始要求分配，或在其執(zhí)行過其初始要求分配，或在其執(zhí)行過 程中通過系統(tǒng)調(diào)用進(jìn)行分配或改程中通過系統(tǒng)調(diào)用進(jìn)行分配或改 變分區(qū)大小。變分區(qū)大小。 優(yōu)點(diǎn)：沒有內(nèi)碎片。優(yōu)點(diǎn)：沒有內(nèi)碎片。 缺點(diǎn)：有外碎片。缺點(diǎn)：有外碎片。 17 Operating System Process 1 32

13、0 K Process 2 Process 3 224 K 288 K 64 K Operating System Process 1 320 K Process 3 224 K 288 K 64 K Operating System Process 1 320 K Process 3288 K 64 K Process 4 128 K 96 K 18 尋找某個(gè)空閑分區(qū)，其大小需大于或等于程尋找某個(gè)空閑分區(qū)，其大小需大于或等于程 序的要求。若是大于要求，則將該分區(qū)分割序的要求。若是大于要求，則將該分區(qū)分割 成兩個(gè)分區(qū)，其中一個(gè)分區(qū)為要求的大小并成兩個(gè)分區(qū)，其中一個(gè)分區(qū)為要求的大小并 標(biāo)記為標(biāo)記

14、為“占用占用”，而另一個(gè)分區(qū)為余下部分，而另一個(gè)分區(qū)為余下部分 并標(biāo)記為并標(biāo)記為“空閑空閑”。分區(qū)的先后次序通常是。分區(qū)的先后次序通常是 從內(nèi)存低端到高端。從內(nèi)存低端到高端。 19 最先匹配法最先匹配法(first-fit)：按分區(qū)的先后次序，從頭查找，找到符按分區(qū)的先后次序，從頭查找，找到符 合要求的第一個(gè)分區(qū)合要求的第一個(gè)分區(qū) 該算法的分配和釋放的時(shí)間性能較好，較大的空閑分區(qū)可以被保留在內(nèi)該算法的分配和釋放的時(shí)間性能較好，較大的空閑分區(qū)可以被保留在內(nèi) 存高端。存高端。 但隨著低端分區(qū)不斷劃分而產(chǎn)生較多小分區(qū)，每次分配時(shí)查找時(shí)間開銷但隨著低端分區(qū)不斷劃分而產(chǎn)生較多小分區(qū)，每次分配時(shí)查找時(shí)間開

15、銷 會增大。會增大。 下次匹配法下次匹配法(next-fit)：按分區(qū)的先后次序，從上次分配的分區(qū)按分區(qū)的先后次序，從上次分配的分區(qū) 起查找（到最后分區(qū)時(shí)再回到開頭），找到符合要求的第一個(gè)起查找（到最后分區(qū)時(shí)再回到開頭），找到符合要求的第一個(gè) 分區(qū)分區(qū) 該算法的分配和釋放的時(shí)間性能較好，使空閑分區(qū)分布得更均勻，但較該算法的分配和釋放的時(shí)間性能較好，使空閑分區(qū)分布得更均勻，但較 大的空閑分區(qū)不易保留。大的空閑分區(qū)不易保留。 最佳匹配法最佳匹配法(best-fit)：找到其大小與要求相差最小的空閑分區(qū)找到其大小與要求相差最小的空閑分區(qū) 從個(gè)別來看，外碎片較小，但從整體來看，會形成較多外碎片。較大的

16、從個(gè)別來看，外碎片較小，但從整體來看，會形成較多外碎片。較大的 空閑分區(qū)可以被保留?？臻e分區(qū)可以被保留。 最壞匹配法最壞匹配法(worst-fit)：找到最大的空閑分區(qū)找到最大的空閑分區(qū) 基本不留下小空閑分區(qū)，但較大的空閑分區(qū)不被保留。基本不留下小空閑分區(qū)，但較大的空閑分區(qū)不被保留。 20 簡單頁式簡單頁式 簡單段式簡單段式 段頁式段頁式 頁式和段式存儲管理是通過引入進(jìn)程的邏輯地頁式和段式存儲管理是通過引入進(jìn)程的邏輯地 址，把進(jìn)程地址空間與實(shí)際存儲位置分離，從址，把進(jìn)程地址空間與實(shí)際存儲位置分離，從 而增加存儲管理的靈活性。而增加存儲管理的靈活性。 21 1. 簡單頁式管理的基本原理簡單頁式管

17、理的基本原理 將程序的邏輯地址空間和物理內(nèi)存劃分為將程序的邏輯地址空間和物理內(nèi)存劃分為固定大小固定大小的的 頁或頁面頁或頁面(page or page frame)，程序加載時(shí)，分配其，程序加載時(shí)，分配其 所需的所有頁，這些頁不必連續(xù)。所需的所有頁，這些頁不必連續(xù)。 需要需要CPU的硬件支持。的硬件支持。 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A.0 A.1 A.2 A.3 B.0 B.1 B.2 C.0 C.1 C.2 C.3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A.0 A.1 A.2 A.3 C.0 C.1 C.2 C

18、.3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A.0 A.1 A.2 A.3 C.0 C.1 C.2 C.3 D.0 D.1 D.2 D.3 D.4 23 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 沒有外碎片，每個(gè)內(nèi)碎片不超過頁大小。沒有外碎片，每個(gè)內(nèi)碎片不超過頁大小。 一個(gè)程序不必連續(xù)存放。一個(gè)程序不必連續(xù)存放。 便于改變程序占用空間的大小。即隨著程序運(yùn)便于改變程序占用空間的大小。即隨著程序運(yùn) 行而動態(tài)生成的數(shù)據(jù)增多，地址空間可相應(yīng)增行而動態(tài)生成的數(shù)據(jù)增多，地址空間可相應(yīng)增 長。長。 缺點(diǎn)：程序全部裝入內(nèi)存。缺點(diǎn)：程序全部裝入內(nèi)存。 24 進(jìn)程頁表進(jìn)程頁表：每個(gè)進(jìn)程有一個(gè)頁表，描述該進(jìn)程：

19、每個(gè)進(jìn)程有一個(gè)頁表，描述該進(jìn)程 占用的物理頁面及邏輯排列順序；占用的物理頁面及邏輯排列順序； 邏輯頁號（本進(jìn)程的地址空間）邏輯頁號（本進(jìn)程的地址空間）物理頁面號物理頁面號 （實(shí)際內(nèi)存空間）；（實(shí)際內(nèi)存空間）； 物理頁面表物理頁面表：整個(gè)系統(tǒng)有一個(gè)物理頁面表，描：整個(gè)系統(tǒng)有一個(gè)物理頁面表，描 述物理內(nèi)存空間的分配使用狀況。述物理內(nèi)存空間的分配使用狀況。 數(shù)據(jù)結(jié)構(gòu)：位示圖，空閑頁面鏈表；數(shù)據(jù)結(jié)構(gòu)：位示圖，空閑頁面鏈表； 請求表請求表：整個(gè)系統(tǒng)有一個(gè)請求表，描述系統(tǒng)內(nèi)：整個(gè)系統(tǒng)有一個(gè)請求表，描述系統(tǒng)內(nèi) 各個(gè)進(jìn)程頁表的位置和大小，用于地址轉(zhuǎn)換，各個(gè)進(jìn)程頁表的位置和大小，用于地址轉(zhuǎn)換， 也可以結(jié)合到各進(jìn)

20、程的也可以結(jié)合到各進(jìn)程的PCB里；里； 25 指令所給出地址分為兩部分：邏輯頁號，頁內(nèi)指令所給出地址分為兩部分：邏輯頁號，頁內(nèi) 偏移地址偏移地址 查進(jìn)程頁表，得物理頁號查進(jìn)程頁表，得物理頁號物理地址物理地址 為縮短查找時(shí)間，可以將頁表從內(nèi)存裝入到快為縮短查找時(shí)間，可以將頁表從內(nèi)存裝入到快 表表(TLB, Translation Lookaside Buffer)，按內(nèi)，按內(nèi) 容查找容查找(associative mapping)，即邏輯頁號，即邏輯頁號 物理頁號物理頁號 頁號頁內(nèi)地址 091019 邏輯地址邏輯地址 26 頁式地址變換 ProgramPagingMain Memory Logi

21、cal Address Register Page Table Page Frame Offset P# Frame # Page Table Ptr Page #OffsetFrame #Offset + 27 1. 簡單段式管理的基本原理簡單段式管理的基本原理 將程序的地址空間劃分為若干個(gè)段將程序的地址空間劃分為若干個(gè)段 (segment)，程序加載時(shí)，分配其所需的所有，程序加載時(shí)，分配其所需的所有 段（內(nèi)存分區(qū)），這些段不必連續(xù)；物理內(nèi)段（內(nèi)存分區(qū)），這些段不必連續(xù)；物理內(nèi) 存的管理采用動態(tài)分區(qū)。存的管理采用動態(tài)分區(qū)。 28 程序通過分段程序通過分段(segmentation)劃分為多個(gè)

22、模劃分為多個(gè)模 塊，如代碼段、數(shù)據(jù)段、共享段。塊，如代碼段、數(shù)據(jù)段、共享段。 可以分別可以分別編寫和編譯編寫和編譯 可以針對不同類型的段采取不同的可以針對不同類型的段采取不同的保護(hù)保護(hù) 可以按段為單位來進(jìn)行可以按段為單位來進(jìn)行共享共享，包括通過動態(tài)鏈，包括通過動態(tài)鏈 接進(jìn)行代碼共享接進(jìn)行代碼共享 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 沒有內(nèi)碎片，外碎片可以通過內(nèi)存緊縮來消除。沒有內(nèi)碎片，外碎片可以通過內(nèi)存緊縮來消除。 便于改變進(jìn)程占用空間的大小。便于改變進(jìn)程占用空間的大小。 缺點(diǎn)：缺點(diǎn)： 進(jìn)程全部裝入內(nèi)存。進(jìn)程全部裝入內(nèi)存。 29 B 0 S A 0 N Y 0 L X 0 P M 0 K 邏輯段號邏輯段號 0 1

23、2 3 4 進(jìn)程進(jìn)程的地址空間的地址空間 1000 3200 5000 6000 8000 P K S L N 主存主存 K 3200 P 1500 L 6000 N 8000 S 5000 長度長度 段地址段地址 0 1 2 3 4 操作系統(tǒng)操作系統(tǒng) 30 進(jìn)程段表進(jìn)程段表：描述組成進(jìn)程地址空間的各：描述組成進(jìn)程地址空間的各 段，可以是指向系統(tǒng)段表中表項(xiàng)的索引。段，可以是指向系統(tǒng)段表中表項(xiàng)的索引。 每段有段基址每段有段基址(base address)和段長度和段長度 系統(tǒng)段表系統(tǒng)段表：系統(tǒng)內(nèi)所有占用段：系統(tǒng)內(nèi)所有占用段 空閑段表空閑段表：內(nèi)存中所有空閑段，可以結(jié)：內(nèi)存中所有空閑段，可以結(jié) 合

24、到系統(tǒng)段表中合到系統(tǒng)段表中 31 Base + d ProgramSegmentationMain Memory Logical Address Register Segment Table Segment d S# Length Base Seg Table Ptr Seg #Offset = d Segment Table + + 32 分頁是出于分頁是出于系統(tǒng)管理系統(tǒng)管理的需要，分段是出于的需要，分段是出于用戶應(yīng)用用戶應(yīng)用 的需要。的需要。 一條指令或一個(gè)操作數(shù)可能會跨越兩個(gè)頁的分界處，而一條指令或一個(gè)操作數(shù)可能會跨越兩個(gè)頁的分界處，而 不會跨越兩個(gè)段的分界處。不會跨越兩個(gè)段的分界處。

25、頁大小頁大小是系統(tǒng)固定的，而是系統(tǒng)固定的，而段大小段大小則通常不固定。則通常不固定。 邏輯地址表示：邏輯地址表示： 分頁是一維的，各個(gè)模塊在鏈接時(shí)必須組織成同一個(gè)地分頁是一維的，各個(gè)模塊在鏈接時(shí)必須組織成同一個(gè)地 址空間；址空間； 分段是二維的，各個(gè)模塊在鏈接時(shí)可以每個(gè)段組織成一分段是二維的，各個(gè)模塊在鏈接時(shí)可以每個(gè)段組織成一 個(gè)地址空間。個(gè)地址空間。 通常段比頁大，因而段表比頁表短，可以縮短查找通常段比頁大，因而段表比頁表短，可以縮短查找 時(shí)間，提高訪問速度。時(shí)間，提高訪問速度。 33 局部性原理局部性原理 虛擬存儲器的原理虛擬存儲器的原理 虛擬存儲技術(shù)的種類虛擬存儲技術(shù)的種類 頁面調(diào)度策略

26、頁面調(diào)度策略 置換算法置換算法 34 局部性原理局部性原理(principle of locality)：指程序在：指程序在 執(zhí)行過程中的一個(gè)較短時(shí)期，所執(zhí)行的指令執(zhí)行過程中的一個(gè)較短時(shí)期，所執(zhí)行的指令 地址和指令的操作數(shù)地址，分別局限于一定地址和指令的操作數(shù)地址，分別局限于一定 區(qū)域。還可以表現(xiàn)為：區(qū)域。還可以表現(xiàn)為： 時(shí)間局部性時(shí)間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，：一條指令的一次執(zhí)行和下次執(zhí)行， 一個(gè)數(shù)據(jù)的一次訪問和下次訪問都集中在一個(gè)較一個(gè)數(shù)據(jù)的一次訪問和下次訪問都集中在一個(gè)較 短時(shí)期內(nèi)；短時(shí)期內(nèi)； 空間局部性空間局部性：當(dāng)前指令和鄰近的幾條指令，當(dāng)前：當(dāng)前指令和鄰近的幾條指令，當(dāng)

27、前 訪問的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個(gè)較小區(qū)域訪問的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個(gè)較小區(qū)域 內(nèi)。內(nèi)。 35 在程序裝入時(shí)，不必將其全部讀入到內(nèi)存，而在程序裝入時(shí)，不必將其全部讀入到內(nèi)存，而只需只需 將當(dāng)前需要執(zhí)行的部分頁或段讀入到內(nèi)存將當(dāng)前需要執(zhí)行的部分頁或段讀入到內(nèi)存，就可讓，就可讓 程序開始執(zhí)行。程序開始執(zhí)行。 在程序執(zhí)行過程中，如果需執(zhí)行的指令或訪問的數(shù)在程序執(zhí)行過程中，如果需執(zhí)行的指令或訪問的數(shù) 據(jù)尚未在內(nèi)存（稱為據(jù)尚未在內(nèi)存（稱為缺頁或缺段缺頁或缺段），則由處理器通），則由處理器通 知操作系統(tǒng)將相應(yīng)的頁或段知操作系統(tǒng)將相應(yīng)的頁或段調(diào)入調(diào)入到內(nèi)存，然后繼續(xù)到內(nèi)存，然后繼續(xù) 執(zhí)行程序。執(zhí)行

28、程序。 另一方面，操作系統(tǒng)將內(nèi)存中另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的頁或段暫時(shí)不使用的頁或段 調(diào)出保存在外存調(diào)出保存在外存上，從而騰出空間存放將要裝入的上，從而騰出空間存放將要裝入的 程序以及將要調(diào)入的頁或段。只需程序的一部分在程序以及將要調(diào)入的頁或段。只需程序的一部分在 內(nèi)存就可執(zhí)行。內(nèi)存就可執(zhí)行。 36 大程序大程序：可在較小的可用內(nèi)存中執(zhí)行較大：可在較小的可用內(nèi)存中執(zhí)行較大 的用戶程序；的用戶程序； 大的用戶空間大的用戶空間：提供給用戶可用的虛擬內(nèi)：提供給用戶可用的虛擬內(nèi) 存空間通常大于物理內(nèi)存存空間通常大于物理內(nèi)存(real memory) 并發(fā)并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行

29、；：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行； 37 虛擬頁式虛擬頁式 虛擬段式虛擬段式 段頁式段頁式 38 需要在進(jìn)程頁表中添加若干項(xiàng)需要在進(jìn)程頁表中添加若干項(xiàng) 標(biāo)志位：存在位（標(biāo)志位：存在位（present bit，內(nèi)存頁和外存，內(nèi)存頁和外存 頁），修改位頁），修改位(modified bit) 訪問統(tǒng)計(jì)：在近期內(nèi)被訪問的次數(shù)，或最近一訪問統(tǒng)計(jì)：在近期內(nèi)被訪問的次數(shù)，或最近一 次訪問到現(xiàn)在的時(shí)間間隔次訪問到現(xiàn)在的時(shí)間間隔 外存地址外存地址 在簡單頁式存儲管理的基礎(chǔ)上，增加請求調(diào)頁在簡單頁式存儲管理的基礎(chǔ)上，增加請求調(diào)頁 和頁面置換功能。和頁面置換功能。 對進(jìn)程頁表的修改對進(jìn)程頁表的修改 39 Vir

30、tual Address Page Table Entry Page NumberOffset P M Frame Number Other Control Bits 虛擬頁式的進(jìn)程頁表 40 需要在進(jìn)程段表中添加若干項(xiàng)：需要在進(jìn)程段表中添加若干項(xiàng)： 標(biāo)志位：存在位標(biāo)志位：存在位(present bit)，修改位，修改位(modified bit/dirty bit)，增長位（該段是否增長過，在虛擬頁式中沒有該，增長位（該段是否增長過，在虛擬頁式中沒有該 位）位） 訪問統(tǒng)計(jì)：如使用位訪問統(tǒng)計(jì)：如使用位(use bit) 存取權(quán)限：如讀存取權(quán)限：如讀R，寫，寫W，執(zhí)行，執(zhí)行X 外存地址外存地址

31、地址變換和缺段中斷：指令和操作數(shù)必定不會跨地址變換和缺段中斷：指令和操作數(shù)必定不會跨 越在段邊界上越在段邊界上 在簡單段式存儲管理的基礎(chǔ)上，增加請求調(diào)段和段置換功能。在簡單段式存儲管理的基礎(chǔ)上，增加請求調(diào)段和段置換功能。 41 Virtual Address Segment Table Entry Segment NumberOffset P MOther Control BitsLengthSegment Base 虛擬段式管理的段表 42 存儲管理的分配單位是：段，頁存儲管理的分配單位是：段，頁 邏輯地址的組成：段號，頁號，頁內(nèi)偏移邏輯地址的組成：段號，頁號，頁內(nèi)偏移 地址。地址。 地址變

32、換：先查段表，再查該段的頁表。地址變換：先查段表，再查該段的頁表。 缺段中斷和缺頁中斷。缺段中斷和缺頁中斷。 是虛擬頁式和虛擬段式存儲管理的結(jié)合。是虛擬頁式和虛擬段式存儲管理的結(jié)合。 43 Virtual Address Segment Table Entry Page Entry Table Segment NumberPage NumberOffset Other Control Bits LengthSegment Base P M Other Control Bits Frame Number 虛擬段頁式管理中的段表和頁表 44 Main Memory Page Frame Offse

33、t Paging Page Table P# + Frame #Offset Seg Table Ptr + S # SegmentationProgram Segment Table Seg #Page #Offset 段頁式地址變換 45 請求調(diào)頁請求調(diào)頁(demand paging)：只調(diào)入發(fā)生：只調(diào)入發(fā)生缺頁時(shí)缺頁時(shí) 所需的頁面。所需的頁面。 優(yōu)點(diǎn)：容易優(yōu)點(diǎn)：容易實(shí)現(xiàn)實(shí)現(xiàn)。 缺點(diǎn)：對外存缺點(diǎn)：對外存I/O次數(shù)次數(shù)多，多，開銷開銷較大較大 預(yù)調(diào)頁預(yù)調(diào)頁(prepaging)：在發(fā)生缺頁需要調(diào)入某頁：在發(fā)生缺頁需要調(diào)入某頁 時(shí)，時(shí)，一次調(diào)入該頁以及相鄰的幾個(gè)頁一次調(diào)入該頁以及相鄰的幾個(gè)頁。

34、 優(yōu)點(diǎn)：提高調(diào)頁的優(yōu)點(diǎn)：提高調(diào)頁的I/O效率效率。 缺點(diǎn)：基于預(yù)測，若調(diào)入的頁在以后很少被訪問，則缺點(diǎn)：基于預(yù)測，若調(diào)入的頁在以后很少被訪問，則 效率效率低。常用于低。常用于程序裝入時(shí)程序裝入時(shí)的調(diào)頁。的調(diào)頁。 1. 調(diào)入策略調(diào)入策略 (fetch policy) 調(diào)入策略確定在外存中的頁面調(diào)入策略確定在外存中的頁面調(diào)入時(shí)機(jī)調(diào)入時(shí)機(jī)。在虛擬頁式。在虛擬頁式 管理中有兩種常用策略。管理中有兩種常用策略。 46 在虛擬段式管理中，如何對物理內(nèi)存進(jìn)在虛擬段式管理中，如何對物理內(nèi)存進(jìn) 行分配，可采用最佳適應(yīng)、最先適應(yīng)等。行分配，可采用最佳適應(yīng)、最先適應(yīng)等。 在虛擬頁式和段頁式管理中，地址變換在虛擬頁式

35、和段頁式管理中，地址變換 最后通過頁表進(jìn)行，因此不必考慮分配最后通過頁表進(jìn)行，因此不必考慮分配 策略。策略。 47 請求清除請求清除(demand cleaning)：該頁被置換時(shí)才調(diào)出，該頁被置換時(shí)才調(diào)出， 把清除推遲到最后一刻把清除推遲到最后一刻。 缺點(diǎn)：調(diào)入所缺頁面之前還要調(diào)出已修改頁面，缺頁進(jìn)缺點(diǎn)：調(diào)入所缺頁面之前還要調(diào)出已修改頁面，缺頁進(jìn) 程的程的等待時(shí)間較長等待時(shí)間較長， 預(yù)清除預(yù)清除(precleaning)：該頁被置換之前就調(diào)出，因該頁被置換之前就調(diào)出，因 而可以而可以成批調(diào)出成批調(diào)出多個(gè)頁面。多個(gè)頁面。 缺點(diǎn)：可能形成缺點(diǎn)：可能形成不必要的開銷不必要的開銷。已修改頁面被調(diào)出之

36、后。已修改頁面被調(diào)出之后 仍停留在內(nèi)存，如果這些頁面被置換之前就被再次修改，仍停留在內(nèi)存，如果這些頁面被置換之前就被再次修改， 則這些頁面可以返還到進(jìn)程的常駐集，而之前所做的調(diào)則這些頁面可以返還到進(jìn)程的常駐集，而之前所做的調(diào) 出操作就成為不必要的開銷。這種策略發(fā)展成為頁面緩出操作就成為不必要的開銷。這種策略發(fā)展成為頁面緩 沖算法沖算法(page buffering)。 在虛擬頁式管理中，何時(shí)將已修改頁面調(diào)出到外存上。在虛擬頁式管理中，何時(shí)將已修改頁面調(diào)出到外存上。 有兩種常用清除策略：有兩種常用清除策略： 48 需要需要調(diào)入頁面時(shí)調(diào)入頁面時(shí)，選擇內(nèi)存中哪個(gè)物理頁面被置換。，選擇內(nèi)存中哪個(gè)物理頁

37、面被置換。 目標(biāo)：把目標(biāo)：把未來不再使用未來不再使用的或的或短期內(nèi)較少使用短期內(nèi)較少使用的頁面調(diào)的頁面調(diào) 出，通常只能在出，通常只能在局部性原理局部性原理指導(dǎo)下依據(jù)過去的統(tǒng)計(jì)數(shù)指導(dǎo)下依據(jù)過去的統(tǒng)計(jì)數(shù) 據(jù)進(jìn)行據(jù)進(jìn)行預(yù)測預(yù)測； 頁面鎖定頁面鎖定(frame locking)：用于描述必須用于描述必須常駐內(nèi)存常駐內(nèi)存的的 操作系統(tǒng)的關(guān)鍵部分或時(shí)間關(guān)鍵操作系統(tǒng)的關(guān)鍵部分或時(shí)間關(guān)鍵(time-critical)的應(yīng)用的應(yīng)用 進(jìn)程。實(shí)現(xiàn)方法為在頁表中加上進(jìn)程。實(shí)現(xiàn)方法為在頁表中加上鎖定標(biāo)志位鎖定標(biāo)志位(lock bit)。 49 最佳算法最佳算法(OPT, optimal) 最近最久未使用算法最近最久未使

38、用算法(LRU, Least Recently Used) 先進(jìn)先出算法先進(jìn)先出算法(FIFO) 輪轉(zhuǎn)算法輪轉(zhuǎn)算法(clock) 最不常用算法最不常用算法(LFU, Least Frequently Used) 頁面緩沖算法頁面緩沖算法(page buffering) 50 選擇選擇“未來不再使用的未來不再使用的”或或“在離當(dāng)前最遠(yuǎn)位置上出現(xiàn)在離當(dāng)前最遠(yuǎn)位置上出現(xiàn)的的” 頁面被置換。頁面被置換。 這是一種理想情況，是實(shí)際執(zhí)行中這是一種理想情況，是實(shí)際執(zhí)行中無法預(yù)知無法預(yù)知的，因而不能實(shí)的，因而不能實(shí) 現(xiàn)。可用作性能現(xiàn)。可用作性能評價(jià)的依據(jù)評價(jià)的依據(jù)。 51 一個(gè)特殊的棧：把被訪問的頁面移到棧頂

39、，于是一個(gè)特殊的棧：把被訪問的頁面移到棧頂，于是 棧底棧底的是最久未使用頁面。的是最久未使用頁面。 每個(gè)頁面設(shè)立移位寄存器：被訪問時(shí)左邊最高位每個(gè)頁面設(shè)立移位寄存器：被訪問時(shí)左邊最高位 置置1，定期右移并且最高位補(bǔ)，定期右移并且最高位補(bǔ)0，于是，于是寄存器數(shù)值寄存器數(shù)值 最小最小的是最久未使用頁面。的是最久未使用頁面。 選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原選擇內(nèi)存中最久未使用的頁面被置換。這是局部性原 理的合理近似，性能接近最佳算法。但由于需要記錄理的合理近似，性能接近最佳算法。但由于需要記錄 頁面使用時(shí)間的先后關(guān)系，硬件開銷太大。硬件機(jī)構(gòu)頁面使用時(shí)間的先后關(guān)系，硬件開銷太大。硬件機(jī)

40、構(gòu) 如：如： 52 選擇選擇建立最早建立最早的頁面被置換。可以通過的頁面被置換?？梢酝ㄟ^鏈表鏈表來表示各來表示各 頁的建立時(shí)間先后。頁的建立時(shí)間先后。 性能較差性能較差: 較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些較早調(diào)入的頁往往是經(jīng)常被訪問的頁，這些 頁在頁在FIFO算法下被反復(fù)調(diào)入和調(diào)出。并且可能出現(xiàn)算法下被反復(fù)調(diào)入和調(diào)出。并且可能出現(xiàn) Belady現(xiàn)象?，F(xiàn)象。 Belady現(xiàn)象現(xiàn)象：采用：采用FIFO算法時(shí)，如果對一個(gè)進(jìn)程算法時(shí)，如果對一個(gè)進(jìn)程未分配它所未分配它所 要求的全部頁面要求的全部頁面，有時(shí)就會出現(xiàn)分配的，有時(shí)就會出現(xiàn)分配的頁面數(shù)增多頁面數(shù)增多，缺頁率缺頁率 反而提高反而提高的異?，F(xiàn)

41、象。的異?，F(xiàn)象。 53 進(jìn)程P有5頁, 程序訪問頁的順序?yàn)椋?, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； 如果在內(nèi)存中分配3個(gè)頁面，則缺頁情況如下： 12次訪問中有缺頁9次； FIFO123412512345 頁 0123412555344 頁 112341222533 頁 21234111255 缺 頁xxxxxxxxX 54 如果在內(nèi)存中分配4個(gè)頁面，則缺頁情況如下： 12次訪問中有缺頁10次； FIFO123412512345 頁 0123444512345 頁 112333451234 頁 21222345123 頁 3111234512 缺 頁xxxxxxxxxx 進(jìn)程P有5頁, 程序訪問頁的順序?yàn)椋?, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； Belady現(xiàn)象的原因現(xiàn)象的原因：FIFO算法的算法的置換特征置換特征與進(jìn)程與進(jìn)程訪問內(nèi)存訪問內(nèi)存 的動態(tài)特征的動態(tài)特