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

1、1 第四章第四章 存儲(chǔ)管理存儲(chǔ)管理( (上上) ) 存儲(chǔ)管理概述存儲(chǔ)管理概述 內(nèi)存管理的基本原理內(nèi)存管理的基本原理 Windows 的的內(nèi)存管理內(nèi)存管理 外存管理外存管理的基本原理的基本原理 Windows 的的外存管理外存管理 高速緩存管理高速緩存管理的基本原理的基本原理 Windows 的的高速緩存管理高速緩存管理 2 存儲(chǔ)體系存儲(chǔ)體系 存儲(chǔ)管理的功能存儲(chǔ)管理的功能 邏輯地址和物理地址邏輯地址和物理地址 重定位技術(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 存儲(chǔ)分配和回收存儲(chǔ)分配和回收：分配和回收算法及相應(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) 存儲(chǔ)共享和保護(hù)存儲(chǔ)共享和保護(hù)： 代碼和數(shù)據(jù)共享代碼和數(shù)據(jù)共享

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

4、都相對(duì)于首地址來編址。，其余指令中的地址都相對(duì)于首地址來編址。 不能用邏輯地址在內(nèi)存中讀取信息。不能用邏輯地址在內(nèi)存中讀取信息。 物理地址物理地址（絕對(duì)地址，實(shí)地址）：內(nèi)存中存儲(chǔ)單元的（絕對(duì)地址，實(shí)地址）：內(nèi)存中存儲(chǔ)單元的 地址。物理地址可直接尋址。地址。物理地址可直接尋址。 地址映射地址映射：將用戶程序中的邏輯地址轉(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)存地址的對(duì)應(yīng)

6、。由操作中地址（指令和數(shù)據(jù)）和內(nèi)存地址的對(duì)應(yīng)。由操作 系統(tǒng)中的裝入程序來完成。系統(tǒng)中的裝入程序來完成。 重定位方法：重定位方法： 絕對(duì)裝入絕對(duì)裝入 可重定位裝入可重定位裝入 動(dòng)態(tài)裝入動(dòng)態(tài)裝入 8 優(yōu)點(diǎn)：裝入過程簡(jiǎn)單。優(yōu)點(diǎn)：裝入過程簡(jiǎ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)存后不能移動(dòng)。不易實(shí)現(xiàn)共享。程序裝入內(nèi)存后不能移動(dòng)。不易實(shí)現(xiàn)共享。 在可執(zhí)行文件中，在可執(zhí)行文件中，列出列出各個(gè)需要重定位的地址單元和各個(gè)需要重定位的地址單元和 相對(duì)地址值。當(dāng)用戶程序被裝入內(nèi)存時(shí)，相對(duì)地址值。當(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)存空間，可以 移動(dòng)程序，有利用實(shí)現(xiàn)共享。移動(dòng)程序，有利用實(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ǔ)。雜。它是虛擬存儲(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ū)存儲(chǔ)管理單一連續(xù)區(qū)存儲(chǔ)管理 分區(qū)存儲(chǔ)管理分區(qū)存儲(chǔ)管理 頁(yè)式和段式存儲(chǔ)管理頁(yè)式和段式存儲(chǔ)管理 虛擬存儲(chǔ)器虛擬存儲(chǔ)器 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ū)全部空間。 最簡(jiǎn)單，適用于單用戶、單任務(wù)最簡(jiǎn)單，適用于單用戶、單任務(wù) 的的OS。 優(yōu)點(diǎn)優(yōu)點(diǎn)：易于管理。：易于管理。 缺點(diǎn)缺點(diǎn)：對(duì)要求內(nèi)存空間少的程序，：對(duì)要求內(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è)類 型相同的對(duì)象）。型相同的對(duì)象）。 分區(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 動(dòng)態(tài)創(chuàng)建分區(qū)：在裝入程序時(shí)按動(dòng)態(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、銷 會(huì)增大。會(huì)增大。 下次匹配法下次匹配法(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è)別來看，外碎片較小，但從整體來看，會(huì)形成較多外碎片。較大的

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

17、理的基本原理 將程序的邏輯地址空間和物理內(nèi)存劃分為將程序的邏輯地址空間和物理內(nèi)存劃分為固定大小固定大小的的 頁(yè)或頁(yè)面頁(yè)或頁(yè)面(page or page frame)，程序加載時(shí)，分配其，程序加載時(shí)，分配其 所需的所有頁(yè)，這些頁(yè)不必連續(xù)。所需的所有頁(yè)，這些頁(yè)不必連續(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)碎片不超過頁(yè)大小。沒有外碎片，每個(gè)內(nèi)碎片不超過頁(yè)大小。 一個(gè)程序不必連續(xù)存放。一個(gè)程序不必連續(xù)存放。 便于改變程序占用空間的大小。即隨著程序運(yùn)便于改變程序占用空間的大小。即隨著程序運(yùn) 行而動(dòng)態(tài)生成的數(shù)據(jù)增多，地址空間可相應(yīng)增行而動(dòng)態(tài)生成的數(shù)據(jù)增多，地址空間可相應(yīng)增 長(zhǎng)。長(zhǎng)。 缺點(diǎn)：程序全部裝入內(nèi)存。缺點(diǎn)：程序全部裝入內(nèi)存。 24 進(jìn)程頁(yè)表進(jìn)程頁(yè)表：每個(gè)進(jìn)程有一個(gè)頁(yè)表，描述該進(jìn)程：

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

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

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

22、模劃分為多個(gè)模 塊，如代碼段、數(shù)據(jù)段、共享段。塊，如代碼段、數(shù)據(jù)段、共享段。 可以分別可以分別編寫和編譯編寫和編譯 可以針對(duì)不同類型的段采取不同的可以針對(duì)不同類型的段采取不同的保護(hù)保護(hù) 可以按段為單位來進(jìn)行可以按段為單位來進(jìn)行共享共享，包括通過動(dòng)態(tài)鏈，包括通過動(dòng)態(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 邏輯段號(hào)邏輯段號(hào) 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 長(zhǎng)度長(zhǎng)度 段地址段地址 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)和段長(zhǎng)度和段長(zhǎng)度 系統(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 分頁(yè)是出于分頁(yè)是出于系統(tǒng)管理系統(tǒng)管理的需要，分段是出于的需要，分段是出于用戶應(yīng)用用戶應(yīng)用 的需要。的需要。 一條指令或一個(gè)操作數(shù)可能會(huì)跨越兩個(gè)頁(yè)的分界處，而一條指令或一個(gè)操作數(shù)可能會(huì)跨越兩個(gè)頁(yè)的分界處，而 不會(huì)跨越兩個(gè)段的分界處。不會(huì)跨越兩個(gè)段的分界處。

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

26、頁(yè)面調(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í)行的部分頁(yè)或段讀入到內(nèi)存將當(dāng)前需要執(zhí)行的部分頁(yè)或段讀入到內(nèi)存，就可讓，就可讓 程序開始執(zhí)行。程序開始執(zhí)行。 在程序執(zhí)行過程中，如果需執(zhí)行的指令或訪問的數(shù)在程序執(zhí)行過程中，如果需執(zhí)行的指令或訪問的數(shù) 據(jù)尚未在內(nèi)存（稱為據(jù)尚未在內(nèi)存（稱為缺頁(yè)或缺段缺頁(yè)或缺段），則由處理器通），則由處理器通 知操作系統(tǒng)將相應(yīng)的頁(yè)或段知操作系統(tǒng)將相應(yīng)的頁(yè)或段調(diào)入調(diào)入到內(nèi)存，然后繼續(xù)到內(nèi)存，然后繼續(xù) 執(zhí)行程序。執(zhí)行

28、程序。 另一方面，操作系統(tǒng)將內(nèi)存中另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的頁(yè)或段暫時(shí)不使用的頁(yè)或段 調(diào)出保存在外存調(diào)出保存在外存上，從而騰出空間存放將要裝入的上，從而騰出空間存放將要裝入的 程序以及將要調(diào)入的頁(yè)或段。只需程序的一部分在程序以及將要調(diào)入的頁(yè)或段。只需程序的一部分在 內(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 虛擬頁(yè)式虛擬頁(yè)式 虛擬段式虛擬段式 段頁(yè)式段頁(yè)式 38 需要在進(jìn)程頁(yè)表中添加若干項(xiàng)需要在進(jìn)程頁(yè)表中添加若干項(xiàng) 標(biāo)志位：存在位（標(biāo)志位：存在位（present bit，內(nèi)存頁(yè)和外存，內(nèi)存頁(yè)和外存 頁(yè)），修改位頁(yè)），修改位(modified bit) 訪問統(tǒng)計(jì)：在近期內(nèi)被訪問的次數(shù)，或最近一訪問統(tǒng)計(jì)：在近期內(nèi)被訪問的次數(shù)，或最近一 次訪問到現(xiàn)在的時(shí)間間隔次訪問到現(xiàn)在的時(shí)間間隔 外存地址外存地址 在簡(jiǎn)單頁(yè)式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)頁(yè)在簡(jiǎn)單頁(yè)式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)頁(yè) 和頁(yè)面置換功能。和頁(yè)面置換功能。 對(duì)進(jìn)程頁(yè)表的修改對(duì)進(jìn)程頁(yè)表的修改 39 Vir

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

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

32、換：先查段表，再查該段的頁(yè)表。地址變換：先查段表，再查該段的頁(yè)表。 缺段中斷和缺頁(yè)中斷。缺段中斷和缺頁(yè)中斷。 是虛擬頁(yè)式和虛擬段式存儲(chǔ)管理的結(jié)合。是虛擬頁(yè)式和虛擬段式存儲(chǔ)管理的結(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 虛擬段頁(yè)式管理中的段表和頁(yè)表 44 Main Memory Page Frame Offse

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

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

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

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

37、面被置換。 目標(biāo)：把目標(biāo)：把未來不再使用未來不再使用的或的或短期內(nèi)較少使用短期內(nèi)較少使用的頁(yè)面調(diào)的頁(yè)面調(diào) 出，通常只能在出，通常只能在局部性原理局部性原理指導(dǎo)下依據(jù)過去的統(tǒng)計(jì)數(shù)指導(dǎo)下依據(jù)過去的統(tǒng)計(jì)數(shù) 據(jù)進(jìn)行據(jù)進(jìn)行預(yù)測(cè)預(yù)測(cè)； 頁(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)方法為在頁(yè)表中加上進(jìn)程。實(shí)現(xiàn)方法為在頁(yè)表中加上鎖定標(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) 頁(yè)面緩沖算法頁(yè)面緩沖算法(page buffering) 50 選擇選擇“未來不再使用的未來不再使用的”或或“在離當(dāng)前最遠(yuǎn)位置上出現(xiàn)在離當(dāng)前最遠(yuǎn)位置上出現(xiàn)的的” 頁(yè)面被置換。頁(yè)面被置換。 這是一種理想情況，是實(shí)際執(zhí)行中這是一種理想情況，是實(shí)際執(zhí)行中無法預(yù)知無法預(yù)知的，因而不能實(shí)的，因而不能實(shí) 現(xiàn)。可用作性能現(xiàn)?？捎米餍阅茉u(píng)價(jià)的依據(jù)評(píng)價(jià)的依據(jù)。 51 一個(gè)特殊的棧：把被訪問的頁(yè)面移到棧頂

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

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

41、象。的異常現(xiàn)象。 53 進(jìn)程P有5頁(yè), 程序訪問頁(yè)的順序?yàn)椋?, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； 如果在內(nèi)存中分配3個(gè)頁(yè)面，則缺頁(yè)情況如下： 12次訪問中有缺頁(yè)9次； FIFO123412512345 頁(yè) 0123412555344 頁(yè) 112341222533 頁(yè) 21234111255 缺 頁(yè)xxxxxxxxX 54 如果在內(nèi)存中分配4個(gè)頁(yè)面，則缺頁(yè)情況如下： 12次訪問中有缺頁(yè)10次； FIFO123412512345 頁(yè) 0123444512345 頁(yè) 112333451234 頁(yè) 21222345123 頁(yè) 3111234512 缺 頁(yè)xxxxxxxxxx 進(jìn)程P有5頁(yè), 程序訪問頁(yè)的順序?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)存 的動(dòng)態(tài)特征的動(dòng)態(tài)特