操作系統(tǒng)第三章課件

1、第第3 3章章 存儲器管理存儲器管理n3.1 內(nèi)存管理概述內(nèi)存管理概述（次重點）（次重點）n3.2 分區(qū)存儲管理分區(qū)存儲管理（次重點）（次重點）n3.3 頁式存儲管理頁式存儲管理（重點）（重點）n3.4 段式存儲管理段式存儲管理（非重點）（非重點）n3.5 段頁式存儲管理段頁式存儲管理（自學(xué)）（自學(xué)）本章需掌握的知識要點本章需掌握的知識要點n內(nèi)存管理任務(wù)內(nèi)存管理任務(wù)n三種內(nèi)存管理方式三種內(nèi)存管理方式n兩類算法（內(nèi)存分配、頁面置換）兩類算法（內(nèi)存分配、頁面置換）n三組區(qū)別三組區(qū)別可可重定位動態(tài)分區(qū)重定位動態(tài)分區(qū)基本分頁基本分頁請求分頁請求分頁實存實存 與與 虛存虛存分頁分頁 與與 分段分段連續(xù)連

2、續(xù) 與與 離散離散3.13.1 內(nèi)存管理概述內(nèi)存管理概述1. 存儲體系存儲體系三級存儲器三級存儲器內(nèi)存內(nèi)存( (主存主存) )：RAM、ROM外存外存( (輔存輔存) )：磁盤磁盤、磁帶、光盤等、磁帶、光盤等高速緩沖存儲器高速緩沖存儲器(cache) 另有寄存器級另有寄存器級 OS負(fù)責(zé)協(xié)調(diào)各存儲器的使用，負(fù)責(zé)協(xié)調(diào)各存儲器的使用，OS本身的程序和數(shù)據(jù)與其他本身的程序和數(shù)據(jù)與其他程序一起共享主存，為安全起見，多道程序系統(tǒng)常由程序一起共享主存，為安全起見，多道程序系統(tǒng)常由OS把內(nèi)存把內(nèi)存初始化為系統(tǒng)區(qū)和用戶區(qū)兩大部分：初始化為系統(tǒng)區(qū)和用戶區(qū)兩大部分： 內(nèi)存內(nèi)存 系統(tǒng)區(qū)（存放系統(tǒng)區(qū)（存放OSOS程序和

3、數(shù)據(jù)）程序和數(shù)據(jù)） 用戶區(qū)（存放用戶程序、數(shù)據(jù)）用戶區(qū)（存放用戶程序、數(shù)據(jù)）2. 存儲管理的目的存儲管理的目的n充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供存儲基礎(chǔ)充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供存儲基礎(chǔ)n盡可能方便用戶使用盡可能方便用戶使用 自動裝入用戶程序自動裝入用戶程序 用戶程序中不必考慮硬件細(xì)節(jié)用戶程序中不必考慮硬件細(xì)節(jié)n能夠解決小內(nèi)存運行大程序的問題能夠解決小內(nèi)存運行大程序的問題n支持程序在執(zhí)行時可以動態(tài)伸縮支持程序在執(zhí)行時可以動態(tài)伸縮n保證內(nèi)存存取速度快保證內(nèi)存存取速度快n實現(xiàn)存儲保護(hù)與安全實現(xiàn)存儲保護(hù)與安全n實現(xiàn)共享與通信實現(xiàn)共享與通信n了解有關(guān)資源的使用狀況了解有關(guān)資源的使用狀況n

4、權(quán)衡實現(xiàn)的性能和代價權(quán)衡實現(xiàn)的性能和代價3. 存儲管理的任務(wù)存儲管理的任務(wù)或功能或功能（1）內(nèi)存空間的管理、分配與回收）內(nèi)存空間的管理、分配與回收n記錄內(nèi)存的使用情況記錄內(nèi)存的使用情況 設(shè)置相應(yīng)的內(nèi)存分塊表（內(nèi)存分配回收的依據(jù)）設(shè)置相應(yīng)的內(nèi)存分塊表（內(nèi)存分配回收的依據(jù)）n內(nèi)存空間劃分問題？內(nèi)存空間劃分問題？靜態(tài)或動態(tài)，等長或不等長靜態(tài)或動態(tài)，等長或不等長n確定分配算法確定分配算法考慮連續(xù)性與離散性，駐留性與交換性，一次考慮連續(xù)性與離散性，駐留性與交換性，一次性與多次性，靜態(tài)方式與動態(tài)方式性與多次性，靜態(tài)方式與動態(tài)方式n內(nèi)存碎片問題及解決辦法內(nèi)存碎片問題及解決辦法n確定回收策略確定回收策略 （2

5、）地址轉(zhuǎn)換）地址轉(zhuǎn)換（又稱地址重定位、地址映射）（又稱地址重定位、地址映射）n指為了保證指為了保證CPU執(zhí)行指令時可正確訪問存儲單元，需將執(zhí)行指令時可正確訪問存儲單元，需將用戶程序中的用戶程序中的邏輯地址邏輯地址（相對地址，虛地址）（相對地址，虛地址）轉(zhuǎn)換為運行時轉(zhuǎn)換為運行時由機(jī)器直接尋址的由機(jī)器直接尋址的物理地址物理地址（絕對地址，實地址）的（絕對地址，實地址）的過程過程3. 存儲管理的任務(wù)（續(xù)）存儲管理的任務(wù)（續(xù)）n根據(jù)實施轉(zhuǎn)換的主體和轉(zhuǎn)換時機(jī)的不同，重定位具體分根據(jù)實施轉(zhuǎn)換的主體和轉(zhuǎn)換時機(jī)的不同，重定位具體分為兩種：為兩種：靜態(tài)重定位靜態(tài)重定位和和動態(tài)重定位動態(tài)重定位。后者更常用。后者更

6、常用n系統(tǒng)采用動態(tài)重定位后，程序在內(nèi)存系統(tǒng)采用動態(tài)重定位后，程序在內(nèi)存可浮動可浮動（3）內(nèi)存的共享與保護(hù)）內(nèi)存的共享與保護(hù)n進(jìn)程共用相同內(nèi)存區(qū)可節(jié)省空間，便于通信，所共享的進(jìn)程共用相同內(nèi)存區(qū)可節(jié)省空間，便于通信，所共享的代碼應(yīng)為代碼應(yīng)為純代碼純代碼（或者叫（或者叫可重入的代碼可重入的代碼）n內(nèi)存保護(hù)限定程序只能訪問自己所在的內(nèi)存區(qū)，保護(hù)了內(nèi)存保護(hù)限定程序只能訪問自己所在的內(nèi)存區(qū)，保護(hù)了OS和其他程序和其他程序常用界限寄存器對法和存取控制字來實現(xiàn)常用界限寄存器對法和存取控制字來實現(xiàn)（4）內(nèi)存的擴(kuò)充）內(nèi)存的擴(kuò)充n常用常用覆蓋覆蓋、交換交換和和虛擬存儲虛擬存儲技術(shù)等實現(xiàn)對內(nèi)存的邏輯擴(kuò)技術(shù)等實現(xiàn)對內(nèi)存

7、的邏輯擴(kuò)充，以使小內(nèi)存能夠運行大程序充，以使小內(nèi)存能夠運行大程序裝入裝入Load 1, 200 3456 1200物理地址空間物理地址空間Load 1, data1data1 3456源程序源程序Load 1, 200 34560100200編譯編譯連接連接邏輯地址空間邏輯地址空間BA=10001100系統(tǒng)采用動態(tài)重定位，系統(tǒng)采用動態(tài)重定位，程序裝入內(nèi)存時的示例程序裝入內(nèi)存時的示例（內(nèi)外存副本一致）（內(nèi)外存副本一致）：10003456LOAD 1, 2000100200300LOAD 1, 2003456邏輯地址空間邏輯地址空間110012001300物理地址空間物理地址空間200VR+100

8、0BR動態(tài)重定位示例：動態(tài)重定位示例：覆蓋示意圖覆蓋示意圖主程序主程序(30k)子程序子程序 A(8k)子程序子程序 B(10k)子程序子程序M(20k)子程序子程序N(25k)子程序子程序X(15k) 主程序（主程序（30k)覆蓋區(qū)覆蓋區(qū)1(25k)覆蓋覆蓋 區(qū)區(qū)0(10k)內(nèi)內(nèi)存存區(qū)區(qū)用戶的結(jié)構(gòu)化程序區(qū) 程序的裝入和鏈接程序的裝入和鏈接n源程序從編輯到運行要經(jīng)歷以下階段：源程序從編輯到運行要經(jīng)歷以下階段： 編輯編輯 編譯編譯 鏈接鏈接 裝入裝入 運行運行n靜態(tài)鏈接、動態(tài)鏈接靜態(tài)鏈接、動態(tài)鏈接n絕對地址裝入、靜態(tài)重定位裝入、動態(tài)絕對地址裝入、靜態(tài)重定位裝入、動態(tài)重定位裝入重定位裝入存儲管理策

9、略分類存儲管理策略分類n存儲管理策略存儲管理策略：n實存管理實存管理n連續(xù)連續(xù)區(qū)區(qū)分配分配（包括（包括固定分區(qū)固定分區(qū)、可變分區(qū)可變分區(qū)和和伙伴系統(tǒng)伙伴系統(tǒng)）n分頁分頁（Paging ）n分段分段（Segmentation ）n虛存管理虛存管理n請求分頁請求分頁(Demand paging)- 主流技術(shù)主流技術(shù)n請求分段請求分段(Demand segmentation)n段頁式段頁式（ segmentation with paging ）離散分配離散分配3.2 3.2 分區(qū)式存儲管理分區(qū)式存儲管理 早期的一類早期的一類實存實存管理技術(shù)管理技術(shù) 系統(tǒng)給每個作業(yè)或進(jìn)程分配一個系統(tǒng)給每個作業(yè)或進(jìn)程分

10、配一個連續(xù)連續(xù)的內(nèi)存分的內(nèi)存分區(qū)區(qū)。n單一連續(xù)區(qū)分配（靜態(tài)分區(qū)技術(shù)）單一連續(xù)區(qū)分配（靜態(tài)分區(qū)技術(shù)）n固定分區(qū)分配固定分區(qū)分配（靜態(tài)分區(qū)靜態(tài)分區(qū)技術(shù)）技術(shù)）n可變分區(qū)分配（動態(tài)分區(qū)技術(shù)）可變分區(qū)分配（動態(tài)分區(qū)技術(shù)）n可重定位可變分區(qū)分配可重定位可變分區(qū)分配（動態(tài)分區(qū)動態(tài)分區(qū)技術(shù)）技術(shù)）n伙伴系統(tǒng)伙伴系統(tǒng)（動態(tài)分區(qū)動態(tài)分區(qū)技術(shù)）技術(shù)）1. 單一連續(xù)區(qū)存儲管理單一連續(xù)區(qū)存儲管理 系統(tǒng)靜態(tài)地將內(nèi)存劃分為兩個區(qū)域，一個供操作系統(tǒng)使用，系統(tǒng)靜態(tài)地將內(nèi)存劃分為兩個區(qū)域，一個供操作系統(tǒng)使用，一個供用戶使用，且每次只能裝入一個作業(yè)或進(jìn)程，主要一個供用戶使用，且每次只能裝入一個作業(yè)或進(jìn)程，主要用于早期單道程序系統(tǒng)

11、和后來的用于早期單道程序系統(tǒng)和后來的PC操作系統(tǒng)。操作系統(tǒng)。特點特點是實現(xiàn)是實現(xiàn)簡單，但內(nèi)存利用率低，作業(yè)大小受限。簡單，但內(nèi)存利用率低，作業(yè)大小受限。操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序0 xFFF.0區(qū)號區(qū)號起始地址起始地址長度長度(KB)狀態(tài)狀態(tài)1aS102bS213cS30系統(tǒng)預(yù)先把可分配的內(nèi)存空間分割成若干個連續(xù)區(qū)域，每一區(qū)系統(tǒng)預(yù)先把可分配的內(nèi)存空間分割成若干個連續(xù)區(qū)域，每一區(qū)域稱為分區(qū)，每個分區(qū)的大小可以相同也可以不同，分區(qū)的個域稱為分區(qū)，每個分區(qū)的大小可以相同也可以不同，分區(qū)的個數(shù)與大小固定不變，每個分區(qū)每次只能裝一個作業(yè)。數(shù)與大小固定不變，每個分區(qū)每次只能裝一個作業(yè)。OS0abcd

12、空空 job2空空 內(nèi)存分塊表內(nèi)存分塊表(MBT)內(nèi)存內(nèi)存特點特點：實現(xiàn)簡單，可用于多道程序系：實現(xiàn)簡單，可用于多道程序系統(tǒng)，但內(nèi)存利用率低，作業(yè)大小受限。統(tǒng)，但內(nèi)存利用率低，作業(yè)大小受限。2. 2. 固定分區(qū)存儲管理固定分區(qū)存儲管理 單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應(yīng)用單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應(yīng)用3. 可變分區(qū)存儲管理可變分區(qū)存儲管理n基本思想基本思想內(nèi)存劃分是在作業(yè)或進(jìn)程進(jìn)入時動態(tài)進(jìn)行的，分區(qū)內(nèi)存劃分是在作業(yè)或進(jìn)程進(jìn)入時動態(tài)進(jìn)行的，分區(qū)的個數(shù)與大小都不是固定的的個數(shù)與大小都不是固定的作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情作業(yè)裝入時，根據(jù)作業(yè)的需求和內(nèi)存空間的使用情況來決定是否

13、分配況來決定是否分配若有足夠的空間，則把分配算法選中的那個分區(qū)直若有足夠的空間，則把分配算法選中的那個分區(qū)直接分配給該作業(yè)，或者從那個選中的分區(qū)中割下與接分配給該作業(yè)，或者從那個選中的分區(qū)中割下與該作業(yè)申請量等大小的一部分連續(xù)空間分給該作業(yè)；該作業(yè)申請量等大小的一部分連續(xù)空間分給該作業(yè)；否則令其等待。否則令其等待。n特點特點克服了固定分區(qū)管理的克服了固定分區(qū)管理的“內(nèi)碎片內(nèi)碎片”問題，但產(chǎn)生了問題，但產(chǎn)生了“外碎片外碎片”。怎樣解決怎樣解決碎片問題碎片問題呢？呢？改進(jìn)內(nèi)存釋放算法改進(jìn)內(nèi)存釋放算法在內(nèi)存中移動程序在內(nèi)存中移動程序變連續(xù)分配為離散分配變連續(xù)分配為離散分配4. 4. 可重定位可變分區(qū)

14、存儲管理可重定位可變分區(qū)存儲管理n基本思想基本思想相當(dāng)于引入了動態(tài)重定位和相當(dāng)于引入了動態(tài)重定位和內(nèi)存緊湊內(nèi)存緊湊（緊縮、拼接、緊致、?。ňo縮、拼接、緊致、浮動、搬家）動、搬家）（compaction）技術(shù)的可變分區(qū)存儲管理）技術(shù)的可變分區(qū)存儲管理n問題問題實現(xiàn)緊湊所花的代價與換來的提高了內(nèi)存空間利用率的實現(xiàn)緊湊所花的代價與換來的提高了內(nèi)存空間利用率的好處相比是否值？好處相比是否值？內(nèi)存緊湊的開銷、頻率、條件、時機(jī)？內(nèi)存緊湊的開銷、頻率、條件、時機(jī)？一經(jīng)緊湊，外碎片是否徹一經(jīng)緊湊，外碎片是否徹底消失？底消失？n特點特點消除了消除了內(nèi)碎片，提高了內(nèi)存利用率，便于動態(tài)申請內(nèi)存，內(nèi)碎片，提高了內(nèi)存利

15、用率，便于動態(tài)申請內(nèi)存， 便于共享內(nèi)存，便于動態(tài)鏈接，但會產(chǎn)生外碎片，而緊便于共享內(nèi)存，便于動態(tài)鏈接，但會產(chǎn)生外碎片，而緊湊內(nèi)存需要花費處理機(jī)大量時間，另外，還需要硬件重湊內(nèi)存需要花費處理機(jī)大量時間，另外，還需要硬件重定位機(jī)構(gòu)支持，作業(yè)大小也受內(nèi)存可用空間的限制。定位機(jī)構(gòu)支持，作業(yè)大小也受內(nèi)存可用空間的限制?？芍囟ㄎ豢勺兎謪^(qū)存儲管理（續(xù)可重定位可變分區(qū)存儲管理（續(xù)1）n內(nèi)存管理用主要數(shù)據(jù)結(jié)構(gòu)內(nèi)存管理用主要數(shù)據(jù)結(jié)構(gòu)空閑分區(qū)鏈空閑分區(qū)鏈（或空閑分區(qū)表）（或空閑分區(qū)表）n內(nèi)存分配算法內(nèi)存分配算法（順序查找分配，可能觸發(fā)（順序查找分配，可能觸發(fā)緊湊緊湊程序）程序）最先適應(yīng)最先適應(yīng)（First Fit）

16、下次適應(yīng)下次適應(yīng)（Next Fit）最佳適應(yīng)（最佳適應(yīng)（Best Fit）最壞適應(yīng)最壞適應(yīng)（Worst Fit）n內(nèi)存釋放內(nèi)存釋放/回收回收算法算法（考慮及時（考慮及時合并相鄰空閑區(qū)合并相鄰空閑區(qū)）先在空閑分區(qū)鏈中找到插入點，再考慮能否合并相鄰先在空閑分區(qū)鏈中找到插入點，再考慮能否合并相鄰空閑空閑區(qū)區(qū)數(shù)據(jù)結(jié)構(gòu)怎樣組織更有效？例例3.1 分區(qū)存儲管理算法分區(qū)存儲管理算法題題n采用可變分區(qū)方式管理內(nèi)存時，若內(nèi)存中按地址順采用可變分區(qū)方式管理內(nèi)存時，若內(nèi)存中按地址順序依次有五個大小依次為序依次有五個大小依次為15k、28k、10k、226k和和110k的的空閑區(qū)。現(xiàn)有五個作業(yè)空閑區(qū)?，F(xiàn)有五個作業(yè)Ja

17、、Jb、Jc、Jd和和Je，它們各需要內(nèi)存它們各需要內(nèi)存10k、15k、102k、26k和和180k。問：問：如果采用最先適應(yīng)分配算法，能將這五個作如果采用最先適應(yīng)分配算法，能將這五個作業(yè)業(yè)按按Ja Je的次序全部裝入內(nèi)存嗎？的次序全部裝入內(nèi)存嗎？用什么分配用什么分配算法裝入這算法裝入這5個作業(yè)可使內(nèi)存的利用率最高？個作業(yè)可使內(nèi)存的利用率最高？解答：解答： 按最先適應(yīng)分配算法，不能將這五個作業(yè)按最先適應(yīng)分配算法，不能將這五個作業(yè)按按Ja Je的次序全部裝入內(nèi)存。因為內(nèi)存中前兩個原先的空閑分區(qū)能的次序全部裝入內(nèi)存。因為內(nèi)存中前兩個原先的空閑分區(qū)能依次裝依次裝入入Ja(10k)和和Jb(15k)，

18、第，第3個個10KB的空閑區(qū)和剛剛劃的空閑區(qū)和剛剛劃分出來的兩個大小分別為分出來的兩個大小分別為5KB和和13KB的空閑區(qū)均無法分配，的空閑區(qū)均無法分配，第第4個空閑區(qū)可以分個空閑區(qū)可以分2次裝入作業(yè)次裝入作業(yè)Jc(102k)和和Jd(26k)，則作業(yè)，則作業(yè)Je(180k)無法裝入內(nèi)存。無法裝入內(nèi)存。 用最佳適應(yīng)分配算法裝入這用最佳適應(yīng)分配算法裝入這5個作業(yè)，可使內(nèi)存的利個作業(yè)，可使內(nèi)存的利用率最高。此時，原先的用率最高。此時，原先的5個空閑區(qū)依次裝入了個空閑區(qū)依次裝入了5個作業(yè)，它個作業(yè)，它們是：們是：Jb(15k)，Jd(26k)，Ja(10k)，Je(180k)和和Jc(102k)。1

19、5k28k10k226k110k5. 伙伴系統(tǒng)伙伴系統(tǒng)（buddy system）介于固定分區(qū)與可變分區(qū)之間的動態(tài)分區(qū)技術(shù)介于固定分區(qū)與可變分區(qū)之間的動態(tài)分區(qū)技術(shù)n伙伴系統(tǒng)可看作固定分區(qū)分配和可變分區(qū)分配的一種折中方案?；锇橄到y(tǒng)可看作固定分區(qū)分配和可變分區(qū)分配的一種折中方案。采用伙伴系統(tǒng)時，內(nèi)存是以采用伙伴系統(tǒng)時，內(nèi)存是以2的冪次個字節(jié)大小的空閑塊為分的冪次個字節(jié)大小的空閑塊為分配單位的。配單位的。系統(tǒng)初啟時，只有系統(tǒng)初啟時，只有1個最大的個最大的2的冪次的空閑塊，它的冪次的空閑塊，它就是整個可用的內(nèi)存空間。當(dāng)就是整個可用的內(nèi)存空間。當(dāng)1個進(jìn)程申請內(nèi)存時，系統(tǒng)就分個進(jìn)程申請內(nèi)存時，系統(tǒng)就分給它

20、給它1個大于或等于進(jìn)程所申請尺寸的最小的個大于或等于進(jìn)程所申請尺寸的最小的2的冪次的空閑塊。的冪次的空閑塊。例如，某進(jìn)程提出的例如，某進(jìn)程提出的5050KBKB的內(nèi)存請求，將首先被系統(tǒng)向上取整，轉(zhuǎn)化為對的內(nèi)存請求，將首先被系統(tǒng)向上取整，轉(zhuǎn)化為對1 1個個6464KBKB的空閑塊的請求。的空閑塊的請求。n伙伴系統(tǒng)的內(nèi)存分配過程伙伴系統(tǒng)的內(nèi)存分配過程在一開始不能找到合適的空閑塊時將在一開始不能找到合適的空閑塊時將把一個最小的比該空閑塊大的空閑塊把一個最小的比該空閑塊大的空閑塊對分成對分成2 2個個“伙伴伙伴”單位，單位，該對分過程可能會繼續(xù)，直到獲得合適的空閑塊為止。該對分過程可能會繼續(xù)，直到獲得

21、合適的空閑塊為止。n伙伴系統(tǒng)的內(nèi)存釋放過程伙伴系統(tǒng)的內(nèi)存釋放過程首先考慮將被釋放塊與其伙伴單位首先考慮將被釋放塊與其伙伴單位合合并并成成1 1個大的空閑塊，然后繼續(xù)合并下去，直到不能合并為止。個大的空閑塊，然后繼續(xù)合并下去，直到不能合并為止?；锇橄到y(tǒng)伙伴系統(tǒng)（續(xù)（續(xù)1） 為了實現(xiàn)伙伴系統(tǒng)為了實現(xiàn)伙伴系統(tǒng)，系統(tǒng)要為每一種可能的空閑塊維護(hù)，系統(tǒng)要為每一種可能的空閑塊維護(hù)1 1個空閑塊鏈表。設(shè)系統(tǒng)管理的可用內(nèi)存空間共為個空閑塊鏈表。設(shè)系統(tǒng)管理的可用內(nèi)存空間共為2 2N N個字個字節(jié)，則節(jié)，則1 1個伙伴系統(tǒng)最多需要維護(hù)個伙伴系統(tǒng)最多需要維護(hù)N N個空閑塊鏈表。由于個空閑塊鏈表。由于每種尺寸的空閑塊都

22、有一個空閑塊隊列，因此內(nèi)存的分每種尺寸的空閑塊都有一個空閑塊隊列，因此內(nèi)存的分配與釋放可以有效地進(jìn)行。配與釋放可以有效地進(jìn)行。 LinuxLinux維護(hù)維護(hù)6 6個鏈表個鏈表。 伙伴系統(tǒng)的最大缺陷伙伴系統(tǒng)的最大缺陷是不能有效地利用內(nèi)存，特別是內(nèi)是不能有效地利用內(nèi)存，特別是內(nèi)碎片嚴(yán)重。碎片嚴(yán)重。例如，例如，1 1個個257257KBKB的進(jìn)程需要占用的進(jìn)程需要占用1 1個個512512KBKB的分配單位，的分配單位，其中將產(chǎn)生其中將產(chǎn)生255255KBKB的內(nèi)碎片。的內(nèi)碎片。另外，另外，每次釋放內(nèi)存時都盡可能每次釋放內(nèi)存時都盡可能地合并伙伴單位的做法也會降低系統(tǒng)性能，因為剛合并地合并伙伴單位的做

23、法也會降低系統(tǒng)性能，因為剛合并好的塊可能馬上又要對分。一種改進(jìn)的做法是延遲合并好的塊可能馬上又要對分。一種改進(jìn)的做法是延遲合并的時機(jī)。的時機(jī)。伙伴系統(tǒng)伙伴系統(tǒng)（續(xù)（續(xù)2） 伙伴系統(tǒng)示意圖伙伴系統(tǒng)示意圖ActionMemoryStart1MA請求請求150kbA256k512kB請求請求100kbAB128k512kC請求請求50kbABC64k512k釋放釋放BAC64k512kD請求請求200kbAC64kD256kE請求請求60kbACED256k釋放釋放CA64kED256k釋放釋放A256k64kED256k釋放釋放E512kD256k釋放釋放D1M3.3 3.3 頁式存儲管理頁式存儲

24、管理 不用不用“緊湊緊湊”也能消除碎片的一種也能消除碎片的一種離散分配離散分配技術(shù)技術(shù)n實分頁式存儲管理（基本分頁）實分頁式存儲管理（基本分頁）n虛擬頁式存儲管理（請求分頁）虛擬頁式存儲管理（請求分頁）3.3.1 3.3.1 實分頁存儲管理實分頁存儲管理 似當(dāng)今磁盤空間的管理，我認(rèn)為在似當(dāng)今磁盤空間的管理，我認(rèn)為在PCPC上很有發(fā)展前途！上很有發(fā)展前途！1. 基本思想（基本思想（特殊的固定分區(qū)特殊的固定分區(qū)+離散分配離散分配）n系統(tǒng)自動地等分進(jìn)程地址空間和內(nèi)存空系統(tǒng)自動地等分進(jìn)程地址空間和內(nèi)存空間，每一等分單位分別叫頁間，每一等分單位分別叫頁（page）和塊和塊（frame，也叫頁幀、頁框、頁

25、架），也叫頁幀、頁框、頁架），頁與塊等大小，頁與塊等大小，且都從且都從0開始連續(xù)編號。進(jìn)程運行時，開始連續(xù)編號。進(jìn)程運行時，全部頁面必須裝入內(nèi)存，但邏輯上連續(xù)全部頁面必須裝入內(nèi)存，但邏輯上連續(xù)的各個頁所對應(yīng)的內(nèi)存塊可以不連續(xù)。的各個頁所對應(yīng)的內(nèi)存塊可以不連續(xù)。2. 相關(guān)概念相關(guān)概念n邏輯地址、頁面、頁內(nèi)碎片邏輯地址、頁面、頁內(nèi)碎片 分頁對用戶是透明的。頁面是內(nèi)存的劃分使用單位，似磁盤分頁對用戶是透明的。頁面是內(nèi)存的劃分使用單位，似磁盤的扇區(qū)或簇，也似的扇區(qū)或簇，也似CPU的時間片。一般，一的時間片。一般，一頁的大小頁的大小為為2的的整數(shù)次冪（整數(shù)次冪（k/24K16KB），也是個實驗統(tǒng)計值，不

26、能太），也是個實驗統(tǒng)計值，不能太大，也不能太小，大，也不能太小，為什么為什么？進(jìn)程的？進(jìn)程的地址空間是一維連續(xù)的地址空間是一維連續(xù)的，用一個記號即可表示一個邏輯地址，但為重定位方便，系用一個記號即可表示一個邏輯地址，但為重定位方便，系統(tǒng)常統(tǒng)常視視邏輯地址邏輯地址為為兩部分組成的，即把地址的高位部分視兩部分組成的，即把地址的高位部分視為頁號，低位部分視為頁內(nèi)偏移。進(jìn)程最后一頁中空閑的為頁號，低位部分視為頁內(nèi)偏移。進(jìn)程最后一頁中空閑的部分稱為部分稱為頁內(nèi)碎片頁內(nèi)碎片。0111231頁號頁號P頁內(nèi)位移量頁內(nèi)位移量W編號編號01048575相對地址相對地址04095該地址結(jié)構(gòu)限定的最大地址空間是多少？

27、最大頁表呢？3. 管理管理n頁表（頁表（page map table）：）： 系統(tǒng)為每個進(jìn)程建立一個頁表，頁表給出邏輯頁號和系統(tǒng)為每個進(jìn)程建立一個頁表，頁表給出邏輯頁號和具體內(nèi)存塊號相應(yīng)的關(guān)系具體內(nèi)存塊號相應(yīng)的關(guān)系(虛分頁系統(tǒng)中頁表表目的內(nèi)容更多虛分頁系統(tǒng)中頁表表目的內(nèi)容更多)。頁。頁表放在內(nèi)存，屬于進(jìn)程的現(xiàn)場信息。表放在內(nèi)存，屬于進(jìn)程的現(xiàn)場信息。 頁表源于一組動態(tài)重定位寄存器，今天的用途主要有頁表源于一組動態(tài)重定位寄存器，今天的用途主要有兩處：兩處：記錄進(jìn)程的內(nèi)存分配情況記錄進(jìn)程的內(nèi)存分配情況實現(xiàn)進(jìn)程運行時的動實現(xiàn)進(jìn)程運行時的動態(tài)重定位。態(tài)重定位。 為了解決要求連續(xù)內(nèi)存空間存放頁表的問題為了

28、解決要求連續(xù)內(nèi)存空間存放頁表的問題，可用對，可用對頁表分頁并將其各頁面離散存放的辦法來實現(xiàn)。這就形成頁表分頁并將其各頁面離散存放的辦法來實現(xiàn)。這就形成了了多級頁表多級頁表，目前最常用的是，目前最常用的是2級頁表，如級頁表，如Windows 2000和和Linux中。這時，原來的頁號部分，又被看成是兩部分：中。這時，原來的頁號部分，又被看成是兩部分：頁目錄偏移、頁表偏移。頁目錄偏移、頁表偏移。 另外，在另外，在IBM AS/400和和Mac OS中，使用更省內(nèi)存的中，使用更省內(nèi)存的反置頁表反置頁表,頁表表目為：頁表表目為：Pid、page、valid、point。下面是一個頁表示意圖。下面是一個

29、頁表示意圖。.01234560123456進(jìn)程的進(jìn)程的地址空間地址空間頁框頁框（物理塊）（物理塊）頁頁號號頁表頁表主存中頁框主存中頁框（物理塊）（物理塊）.頁表示意圖：頁表示意圖：0310/10/10/10/10/1017空閑塊數(shù)空閑塊數(shù)n空塊管理空塊管理位示圖位示圖(用于外存分配時常叫盤圖用于外存分配時常叫盤圖)使用時需進(jìn)行字位號到塊號的轉(zhuǎn)換：使用時需進(jìn)行字位號到塊號的轉(zhuǎn)換：(i,j)b，b=i*w+j。另外，找。另外，找n個連續(xù)的塊較慢。個連續(xù)的塊較慢。3. 管理（續(xù)管理（續(xù)1）3. 管理管理（續(xù)（續(xù)2）n內(nèi)存的分配內(nèi)存的分配與回收與回收計算一個作業(yè)所需要的總塊計算一個作業(yè)所需要的總塊數(shù)數(shù)

30、N查位示圖，看看是否還有查位示圖，看看是否還有N個空閑塊個空閑塊如果有足夠的空閑塊，則頁表長度設(shè)為如果有足夠的空閑塊，則頁表長度設(shè)為N，可填入可填入PCB中；申請頁表區(qū)，把頁中；申請頁表區(qū)，把頁表始表始址填入址填入PCB依次分配依次分配N個空閑塊，將塊號和頁號填入個空閑塊，將塊號和頁號填入頁表頁表修改位示圖修改位示圖4. 硬件支持硬件支持n系統(tǒng)設(shè)置一對寄存器：系統(tǒng)設(shè)置一對寄存器： 頁表始址寄存器頁表始址寄存器（用于重定位時查頁表）（用于重定位時查頁表） 頁表長度寄存器頁表長度寄存器（用于重定位時內(nèi)存保護(hù)校驗，頁表目還常有控制位）（用于重定位時內(nèi)存保護(hù)校驗，頁表目還常有控制位）n聯(lián)想存儲器聯(lián)想存

31、儲器（associative memory）快表快表（cache結(jié)構(gòu)，結(jié)構(gòu)，為提高地址變?yōu)樘岣叩刂纷儞Q速度而引入換速度而引入，在，在IBM系統(tǒng)系統(tǒng)中稱中稱TLB（Translation lookaside buffers） 用途：保存正在運行進(jìn)程的部分頁表項，以快速重定位用途：保存正在運行進(jìn)程的部分頁表項，以快速重定位快表表目內(nèi)容：頁號、內(nèi)存塊號、標(biāo)識位、淘汰位快表表目內(nèi)容：頁號、內(nèi)存塊號、標(biāo)識位、淘汰位快表的特點：可按內(nèi)容并行查找快表的特點：可按內(nèi)容并行查找快表命中率：已經(jīng)證明，快表命中率：已經(jīng)證明，16個表目可達(dá)個表目可達(dá)90%以上。以上。 Intel 80 x86/Pentium有有32

32、項，項，SGI MIPS R4000有有48項。項。下面是快表在地址轉(zhuǎn)換過程中應(yīng)用的示意圖。下面是快表在地址轉(zhuǎn)換過程中應(yīng)用的示意圖。分頁地址映射過程示意圖分頁地址映射過程示意圖地址越界地址越界p 頁表頁表 l比較比較P=1pp .快表快表 b+頁號頁號p p 頁內(nèi)地址頁內(nèi)地址dP d頁表地址寄存器頁表地址寄存器頁表長度寄存器頁表長度寄存器邏輯地址邏輯地址.物理地址物理地址頁目錄地址頁目錄地址目錄位移目錄位移頁表位移頁表位移頁位移頁位移虛擬地址虛擬地址頁表地址頁表地址.頁目錄（每進(jìn)程一個）頁目錄（每進(jìn)程一個）塊號塊號. 頁頁 表表代碼或數(shù)據(jù)代碼或數(shù)據(jù).物理頁物理頁+二級頁表結(jié)構(gòu)及地址映射過程二級

33、頁表結(jié)構(gòu)及地址映射過程（未畫出快表）（未畫出快表）5. 實分頁存儲管理方式小結(jié)實分頁存儲管理方式小結(jié)n優(yōu)點：優(yōu)點：內(nèi)存利用率高內(nèi)存利用率高，解決了碎片問題；，解決了碎片問題； 便于管理。便于管理。n缺點：缺點：不易不易實現(xiàn)實現(xiàn)共享共享（見（見P93）；）； 不便于不便于頁面頁面動態(tài)增長動態(tài)增長； 進(jìn)程仍受內(nèi)存可用空間大小的限制；進(jìn)程仍受內(nèi)存可用空間大小的限制； 所需硬件支持較多。所需硬件支持較多。3.3.2 虛擬虛擬頁式存儲管理頁式存儲管理1. 基本思想基本思想實分頁實分頁+對換和請求裝入功能對換和請求裝入功能系統(tǒng)等分進(jìn)程地址空間和內(nèi)存空間，每一等分單位系統(tǒng)等分進(jìn)程地址空間和內(nèi)存空間，每一等分

34、單位分別叫頁和塊，頁與塊等大小，且都從分別叫頁和塊，頁與塊等大小，且都從0開始連開始連續(xù)編號。續(xù)編號。進(jìn)程運行時，進(jìn)程運行時，只需部分頁面在內(nèi)存只需部分頁面在內(nèi)存，且，且邏輯上連續(xù)的頁所對應(yīng)的內(nèi)存塊可以不連續(xù)。當(dāng)邏輯上連續(xù)的頁所對應(yīng)的內(nèi)存塊可以不連續(xù)。當(dāng)進(jìn)程訪問的頁不在內(nèi)存時將產(chǎn)生進(jìn)程訪問的頁不在內(nèi)存時將產(chǎn)生缺頁中斷缺頁中斷，由服，由服務(wù)程序把所缺頁裝入內(nèi)存，此時若內(nèi)存空間已滿，務(wù)程序把所缺頁裝入內(nèi)存，此時若內(nèi)存空間已滿，則又需要則又需要對換對換進(jìn)程根據(jù)進(jìn)程根據(jù)頁面調(diào)度算法頁面調(diào)度算法淘汰某個內(nèi)淘汰某個內(nèi)存頁面，再裝入所缺頁面。存頁面，再裝入所缺頁面。2. 虛擬存儲器的概念虛擬存儲器的概念n實

35、存管理方式的特征實存管理方式的特征： 一次性；駐留性一次性；駐留性；連續(xù)性。；連續(xù)性。n虛擬存儲器是虛擬存儲器是為了為了邏輯擴(kuò)充內(nèi)存，以解決小內(nèi)存無法運行大邏輯擴(kuò)充內(nèi)存，以解決小內(nèi)存無法運行大程序的問題而程序的問題而引入引入的，是一種以的，是一種以CPU時間和外存空間換取內(nèi)時間和外存空間換取內(nèi)存空間的技術(shù)（是存空間的技術(shù)（是OS中的資源轉(zhuǎn)換技術(shù)），也是迄今為止邏中的資源轉(zhuǎn)換技術(shù)），也是迄今為止邏輯擴(kuò)充內(nèi)存程度最徹底的技術(shù)（遠(yuǎn)強(qiáng)于覆蓋和交換技術(shù)）。輯擴(kuò)充內(nèi)存程度最徹底的技術(shù)（遠(yuǎn)強(qiáng)于覆蓋和交換技術(shù)）。n虛擬存儲器是在虛擬存儲器是在1961年由英國曼徹斯特大學(xué)的年由英國曼徹斯特大學(xué)的Fotherin

36、gham提出，并在該校的提出，并在該校的atlas機(jī)器上實現(xiàn)的一種存儲技術(shù)。從機(jī)器上實現(xiàn)的一種存儲技術(shù)。從1970年后被廣泛應(yīng)用，今天的年后被廣泛應(yīng)用，今天的OS普遍采用這一技術(shù)管理內(nèi)存普遍采用這一技術(shù)管理內(nèi)存，但，但我們?nèi)詰?yīng)辨證地看待它我們?nèi)詰?yīng)辨證地看待它。n虛擬存儲器的基本思想虛擬存儲器的基本思想是：是：程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存程序、數(shù)據(jù)、堆棧的大小可以超過內(nèi)存的大小，的大小，OS把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分保存在磁把程序當(dāng)前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時在內(nèi)存和磁盤之間動態(tài)交換。盤上，并在需要時在內(nèi)存和磁盤之間動態(tài)交換。n虛擬存儲器支

37、持多道程序設(shè)計技術(shù)。虛擬存儲器支持多道程序設(shè)計技術(shù)。虛存管理方式的特征虛存管理方式的特征：多次性；對換性；虛擬性多次性；對換性；虛擬性；離散性；離散性2. 虛擬存儲器的概念（續(xù)虛擬存儲器的概念（續(xù)1） 1968年美國年美國MIT的的Denning提出程序局部性原理提出程序局部性原理是對虛擬存儲器有力的理論支持。是對虛擬存儲器有力的理論支持。n程序局部性原理程序局部性原理 程序在執(zhí)行時呈現(xiàn)出高度的局部性特征，即在一較短程序在執(zhí)行時呈現(xiàn)出高度的局部性特征，即在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應(yīng)地，的時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應(yīng)地，它所訪問的存儲空間也局限于某個區(qū)域。程序執(zhí)

38、行的它所訪問的存儲空間也局限于某個區(qū)域。程序執(zhí)行的局部性表現(xiàn)在時間與空間兩個方面：局部性表現(xiàn)在時間與空間兩個方面：時間局部性時間局部性 一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行空間局部性空間局部性 若某一存儲單元被訪問，則在不久之后，與該存儲單若某一存儲單元被訪問，則在不久之后，與該存儲單元相鄰的單元也可能被訪問元相鄰的單元也可能被訪問2. 虛擬存儲器的概念（續(xù)虛擬存儲器的概念（續(xù)2）n虛擬存儲器定義虛擬存儲器定義（至今沒有統(tǒng)一定義，我認(rèn)為以下前（至今沒有統(tǒng)一定義，我認(rèn)為以下前3種比較重要）種比較重要）n虛假的存儲器；虛假的存儲器；n進(jìn)程能夠

39、訪問的虛擬地址空間；進(jìn)程能夠訪問的虛擬地址空間；n具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。加以擴(kuò)充的一種存儲器系統(tǒng)。n把內(nèi)存與外存有機(jī)的結(jié)合起來使用，從而得到一個容量把內(nèi)存與外存有機(jī)的結(jié)合起來使用，從而得到一個容量很大的很大的“內(nèi)存內(nèi)存”，這就是虛存，這就是虛存n虛擬存儲器是把內(nèi)存與外存這兩級存儲器并用做一級存儲器虛擬存儲器是把內(nèi)存與外存這兩級存儲器并用做一級存儲器的結(jié)果，是邏輯擴(kuò)充內(nèi)存的最佳手段的結(jié)果，是邏輯擴(kuò)充內(nèi)存的最佳手段n虛擬存儲器的容量虛擬存儲器的容量取決于內(nèi)存與外存的容量之和，但實際最取決于內(nèi)存與外存

40、的容量之和，但實際最大尺寸取決于系統(tǒng)的地址結(jié)構(gòu)大尺寸取決于系統(tǒng)的地址結(jié)構(gòu)2. 虛擬存儲器的概念（續(xù)虛擬存儲器的概念（續(xù)3） 虛擬存儲器虛擬存儲器是建立在離散分配的內(nèi)存管理技術(shù)基礎(chǔ)上是建立在離散分配的內(nèi)存管理技術(shù)基礎(chǔ)上的，它主要有以下的，它主要有以下3種實現(xiàn)方法種實現(xiàn)方法：n請求分頁系統(tǒng)請求分頁系統(tǒng)虛擬分頁系統(tǒng)虛擬分頁系統(tǒng)n基本分頁系統(tǒng)基本分頁系統(tǒng) + 請求分頁功能請求分頁功能 + 頁面置換功能頁面置換功能n硬硬/軟件支持軟件支持：請求分頁的頁表機(jī)制、缺頁中斷機(jī)構(gòu)、動態(tài)地址變換：請求分頁的頁表機(jī)制、缺頁中斷機(jī)構(gòu)、動態(tài)地址變換機(jī)構(gòu)、對換機(jī)制、大容量外存。機(jī)構(gòu)、對換機(jī)制、大容量外存。n請求分段系統(tǒng)請

41、求分段系統(tǒng)虛擬分段系統(tǒng)虛擬分段系統(tǒng)n基本分段系統(tǒng)基本分段系統(tǒng) + 請求分段功能請求分段功能 + 分段置換功能；分段置換功能；n硬硬/軟件支持：請求分段的段表機(jī)制、缺段中斷機(jī)構(gòu)、動態(tài)地址變換軟件支持：請求分段的段表機(jī)制、缺段中斷機(jī)構(gòu)、動態(tài)地址變換機(jī)構(gòu)、對換機(jī)制、大容量外存。機(jī)構(gòu)、對換機(jī)制、大容量外存。n請求段頁式系統(tǒng)請求段頁式系統(tǒng)虛擬段頁式系統(tǒng)虛擬段頁式系統(tǒng)n請求分頁系統(tǒng)請求分頁系統(tǒng) + 請求分段系統(tǒng)請求分段系統(tǒng)n硬硬/軟件支持：頁表機(jī)制、缺頁中斷機(jī)構(gòu)、段表機(jī)制、缺段中斷機(jī)構(gòu)、軟件支持：頁表機(jī)制、缺頁中斷機(jī)構(gòu)、段表機(jī)制、缺段中斷機(jī)構(gòu)、動態(tài)地址變換機(jī)構(gòu)、對換機(jī)制、大容量外存動態(tài)地址變換機(jī)構(gòu)、對換機(jī)

42、制、大容量外存。2. 虛擬存儲器的概念（續(xù)虛擬存儲器的概念（續(xù)4） 要辨證地看待虛擬存儲器管理要辨證地看待虛擬存儲器管理n問題問題1：windows98為何常提示為何常提示“內(nèi)存不足內(nèi)存不足”？n問題問題2：當(dāng)今：當(dāng)今OS幾乎都用虛擬內(nèi)存技術(shù)，有幾乎都用虛擬內(nèi)存技術(shù)，有必要嗎？必要嗎？n虛擬存儲器管理的主要優(yōu)點虛擬存儲器管理的主要優(yōu)點 擴(kuò)充了內(nèi)存，解決了小內(nèi)存無法運行大程序的問擴(kuò)充了內(nèi)存，解決了小內(nèi)存無法運行大程序的問題，提高了內(nèi)存的利用率和多道程度題，提高了內(nèi)存的利用率和多道程度n虛擬存儲器管理的主要缺點虛擬存儲器管理的主要缺點 實現(xiàn)開銷大，程序運行比實模式下慢實現(xiàn)開銷大，程序運行比實模式下

43、慢3. 虛分頁所需的硬件支持虛分頁所需的硬件支持n頁表機(jī)制頁表機(jī)制（似實分頁的，只是擴(kuò)充了頁表目內(nèi)容）（似實分頁的，只是擴(kuò)充了頁表目內(nèi)容）n用于地址轉(zhuǎn)換；用于地址轉(zhuǎn)換；n擴(kuò)充頁表項：頁號、頁架號、狀態(tài)位、訪問字段擴(kuò)充頁表項：頁號、頁架號、狀態(tài)位、訪問字段/位、位、修改位、外存地址修改位、外存地址n缺頁中斷（缺頁中斷（Page Fault）機(jī)構(gòu)）機(jī)構(gòu)n在地址映射過程中，所訪問的頁不在內(nèi)存時，便產(chǎn)在地址映射過程中，所訪問的頁不在內(nèi)存時，便產(chǎn)生一缺頁中斷；生一缺頁中斷；OS接到此中斷信號后，就調(diào)出缺頁接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，將該中斷處理程序，根據(jù)頁表中給出

44、的外存地址，將該頁調(diào)入內(nèi)存，更新頁表，完成重定位，使進(jìn)程繼續(xù)頁調(diào)入內(nèi)存，更新頁表，完成重定位，使進(jìn)程繼續(xù)運行下去。這期間可能調(diào)用置換程序。運行下去。這期間可能調(diào)用置換程序。n與常規(guī)中斷的不同之處：與常規(guī)中斷的不同之處：n在指令執(zhí)行期間產(chǎn)生和處理中斷信號；在指令執(zhí)行期間產(chǎn)生和處理中斷信號；n一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。3. 虛分頁所需的硬件支持（續(xù)虛分頁所需的硬件支持（續(xù)1）n地址變換機(jī)構(gòu)地址變換機(jī)構(gòu)（似實分頁的，但重定位過程中可（似實分頁的，但重定位過程中可能觸發(fā)缺頁中斷）能觸發(fā)缺頁中斷）n首先檢索快表，若找到，修改頁表項中的訪首先檢索快

45、表，若找到，修改頁表項中的訪問位，然后利用頁表項中給出的頁架號和頁問位，然后利用頁表項中給出的頁架號和頁內(nèi)地址，形成物理地址。內(nèi)地址，形成物理地址。n如果在快表中未找到相應(yīng)的頁表項，則檢索如果在快表中未找到相應(yīng)的頁表項，則檢索內(nèi)存中的頁表，察看頁表項中的狀態(tài)位，若內(nèi)存中的頁表，察看頁表項中的狀態(tài)位，若該頁已經(jīng)調(diào)入內(nèi)存，則形成物理地址，并更該頁已經(jīng)調(diào)入內(nèi)存，則形成物理地址，并更新快表，當(dāng)快表滿時，應(yīng)淘汰一個頁表項；新快表，當(dāng)快表滿時，應(yīng)淘汰一個頁表項；若該頁尚未調(diào)入內(nèi)存，則若該頁尚未調(diào)入內(nèi)存，則產(chǎn)生缺頁中斷產(chǎn)生缺頁中斷，請，請求求OS把該頁調(diào)入內(nèi)存，然后再完成重定位。把該頁調(diào)入內(nèi)存，然后再完成重

46、定位。4. 內(nèi)存分配策略和分配算法內(nèi)存分配策略和分配算法n最小物理塊（頁架）數(shù)的確定最小物理塊（頁架）數(shù)的確定n保證進(jìn)程正常運行所需的最少頁架數(shù)；保證進(jìn)程正常運行所需的最少頁架數(shù)；n與指令的格式、功能和尋址方式有關(guān)。與指令的格式、功能和尋址方式有關(guān)。n頁架的分配策略頁架的分配策略n固定分配局部置換固定分配局部置換：進(jìn)程占據(jù)的內(nèi)存頁架數(shù)不變；：進(jìn)程占據(jù)的內(nèi)存頁架數(shù)不變；置換時在該進(jìn)程所占頁架中選則換出對象。系統(tǒng)給置換時在該進(jìn)程所占頁架中選則換出對象。系統(tǒng)給各進(jìn)程分配固定數(shù)目的頁架時，可考慮各進(jìn)程分配固定數(shù)目的頁架時，可考慮按比例分按比例分、平均分、結(jié)合工作集、結(jié)合優(yōu)先權(quán)分配等策略。平均分、結(jié)合工

47、作集、結(jié)合優(yōu)先權(quán)分配等策略。n可變分配全局置換：可變分配全局置換：初始時先給進(jìn)程分配一定數(shù)目的頁架，初始時先給進(jìn)程分配一定數(shù)目的頁架，當(dāng)進(jìn)程缺頁率較高或較低時，能由當(dāng)進(jìn)程缺頁率較高或較低時，能由OS對其占據(jù)的頁架數(shù)加以對其占據(jù)的頁架數(shù)加以調(diào)整，置換時在整個內(nèi)存用戶區(qū)的頁架中選則換出對象。調(diào)整，置換時在整個內(nèi)存用戶區(qū)的頁架中選則換出對象。n可變分配局部置換：可變分配局部置換：可變分配同上，置換時在運行進(jìn)程所可變分配同上，置換時在運行進(jìn)程所占頁架中選則換出對象。占頁架中選則換出對象。4. 內(nèi)存分配策略和分配算法（續(xù)內(nèi)存分配策略和分配算法（續(xù)1）n工作集（工作集（Working Set）模型）模型D

48、enning在在1968年研究缺頁率與頁架數(shù)的關(guān)系時提出年研究缺頁率與頁架數(shù)的關(guān)系時提出工作集的概念，旨在降低進(jìn)程的缺頁率。工作集的概念，旨在降低進(jìn)程的缺頁率。n一個進(jìn)程當(dāng)前使用的頁的集合叫它的一個進(jìn)程當(dāng)前使用的頁的集合叫它的工作集工作集。更形。更形式化的定義是：對于給定的頁面訪問序列選取定長式化的定義是：對于給定的頁面訪問序列選取定長的區(qū)間，稱為工作集窗口，落在工作集窗口中的頁的區(qū)間，稱為工作集窗口，落在工作集窗口中的頁面集合稱為面集合稱為工作集。工作集。例如，某訪問序列為：例如，某訪問序列為： 26157775162341234443434441327 | |t1 | |t2 則則ws(t

49、1)=1,2,5,6,7，ws(t2)=3,4n盡量保持進(jìn)程的工作集在內(nèi)存可以降低進(jìn)程的盡量保持進(jìn)程的工作集在內(nèi)存可以降低進(jìn)程的缺頁率，這種方法叫缺頁率，這種方法叫工作集模型工作集模型。依據(jù)是。依據(jù)是局部局部性原理性原理。借助該模型，可實現(xiàn)可變分配、改進(jìn)。借助該模型，可實現(xiàn)可變分配、改進(jìn)時鐘置換算法等。時鐘置換算法等。n Windows 2000Windows 2000在系統(tǒng)初始化時，計算進(jìn)程的在系統(tǒng)初始化時，計算進(jìn)程的最小和最大工作集值，當(dāng)物理內(nèi)存大于最小和最大工作集值，當(dāng)物理內(nèi)存大于32MB32MB（serverserver大于大于64MB64MB）時，進(jìn)程缺省最小工作）時，進(jìn)程缺省最小工

50、作集為集為5050頁，最大工作集為頁，最大工作集為345345頁。頁。4. 內(nèi)存分配策略和分配算法（續(xù)內(nèi)存分配策略和分配算法（續(xù)2）n內(nèi)存分配算法內(nèi)存分配算法n同基本分頁，管理物理頁幀同基本分頁，管理物理頁幀/空閑內(nèi)存塊的數(shù)據(jù)結(jié)空閑內(nèi)存塊的數(shù)據(jù)結(jié)構(gòu)也是位示圖構(gòu)也是位示圖 5. 調(diào)頁策略調(diào)頁策略n請求調(diào)頁策略請求調(diào)頁策略（demand paging）n進(jìn)程運行過程中靠缺頁中斷程序裝入所需訪問的進(jìn)程運行過程中靠缺頁中斷程序裝入所需訪問的不在內(nèi)存的頁面。實現(xiàn)簡單，用得廣，但費時。不在內(nèi)存的頁面。實現(xiàn)簡單，用得廣，但費時。n預(yù)調(diào)頁策略預(yù)調(diào)頁策略（prepaging）n進(jìn)程運行之前預(yù)先裝入一些頁面。主要

51、用于進(jìn)程進(jìn)程運行之前預(yù)先裝入一些頁面。主要用于進(jìn)程的首次調(diào)入時，并且多涉及工作集模型的實現(xiàn)。的首次調(diào)入時，并且多涉及工作集模型的實現(xiàn)。5. 調(diào)頁策略調(diào)頁策略（續(xù)（續(xù)1）n問題問題n從何處調(diào)入頁面？從何處調(diào)入頁面？ 外存文件區(qū)、外存對換區(qū)、內(nèi)存區(qū)外存文件區(qū)、外存對換區(qū)、內(nèi)存區(qū)（共享頁面（共享頁面或或Buffer中頁面的及時再利用）中頁面的及時再利用）n頁面的調(diào)入過程？頁面的調(diào)入過程？先由中斷服務(wù)程序調(diào)內(nèi)存分配程序先由中斷服務(wù)程序調(diào)內(nèi)存分配程序（可能觸發(fā)對（可能觸發(fā)對換程序）換程序）獲得一內(nèi)存塊，獲得一內(nèi)存塊，再查頁表，把所缺頁從外存調(diào)入內(nèi)存，并修再查頁表，把所缺頁從外存調(diào)入內(nèi)存，并修改頁表。改頁

52、表。這是在重定位過程中實現(xiàn)的，對用戶透明。這是在重定位過程中實現(xiàn)的，對用戶透明。6. 頁面置換頁面置換（淘汰（淘汰 / 調(diào)度）調(diào)度）算法算法 Page Replacement Algorithmsn顛簸（抖動）顛簸（抖動） 在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時間比進(jìn)程實際運行的時間至于調(diào)度頁面所需時間比進(jìn)程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)還多，此時系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為崩潰。這種現(xiàn)象稱為顛簸顛簸或或抖動抖動。例如，一個。例如，一個每隔幾條指令就發(fā)生一次頁面故障的進(jìn)程稱為每隔幾條指令

53、就發(fā)生一次頁面故障的進(jìn)程稱為在顛簸在顛簸（因為一條指令的執(zhí)行只需幾納秒，而每從磁盤上讀入（因為一條指令的執(zhí)行只需幾納秒，而每從磁盤上讀入一個頁面則常需幾十毫秒）一個頁面則常需幾十毫秒）。n系統(tǒng)發(fā)生顛簸的原因系統(tǒng)發(fā)生顛簸的原因頁面置換算法不合理頁面置換算法不合理分配給進(jìn)程的物理頁面數(shù)太少分配給進(jìn)程的物理頁面數(shù)太少6. 頁面置換算法（續(xù)頁面置換算法（續(xù)1）n最佳最佳（OPTimal）置換算法）置換算法 淘汰以后不再需要的或最遠(yuǎn)的將來才會用到的頁面淘汰以后不再需要的或最遠(yuǎn)的將來才會用到的頁面。1966年年Belady提出的理想算法，但無法實現(xiàn)，主要用于提出的理想算法，但無法實現(xiàn)，主要用于評價其他置換

54、算法。評價其他置換算法。n先進(jìn)先出（先進(jìn)先出（FIFO）置換算法）置換算法 選擇在內(nèi)存中駐留時間最長的頁并淘汰之選擇在內(nèi)存中駐留時間最長的頁并淘汰之。它實現(xiàn)簡單它實現(xiàn)簡單：只需把進(jìn)程在內(nèi)存的頁面按先后次序鏈成只需把進(jìn)程在內(nèi)存的頁面按先后次序鏈成1個隊列，并個隊列，并設(shè)置設(shè)置1個替換指針，使它總是指向內(nèi)存中最老的頁面。個替換指針，使它總是指向內(nèi)存中最老的頁面。缺點：缺點：效率不高效率不高，因為它與進(jìn)程實際的運行規(guī)律不相適，因為它與進(jìn)程實際的運行規(guī)律不相適應(yīng)，比如常用的全局變量所在的頁面或者循環(huán)體所在頁應(yīng)，比如常用的全局變量所在的頁面或者循環(huán)體所在頁面都可能被它選為淘汰對象。另外，它面都可能被它選

55、為淘汰對象。另外，它還有還有Belady異常異?，F(xiàn)象現(xiàn)象（考慮頁面訪問序列為（考慮頁面訪問序列為14，12，5，15的進(jìn)程分別獲得的進(jìn)程分別獲得3塊塊內(nèi)存和內(nèi)存和4塊內(nèi)存請求裝入執(zhí)行時的缺頁情況塊內(nèi)存請求裝入執(zhí)行時的缺頁情況）。6. 頁面置換算法頁面置換算法（續(xù)（續(xù)2）n最近最少使用最近最少使用（LRU, Least Recently Used ）置換算法置換算法 選擇最后一次訪問時間距離當(dāng)前時間最長的一頁并淘汰之。選擇最后一次訪問時間距離當(dāng)前時間最長的一頁并淘汰之。該算法理論上性能好，但實現(xiàn)代價高該算法理論上性能好，但實現(xiàn)代價高（需硬件支持需硬件支持，如：為進(jìn)程每個，如：為進(jìn)程每個內(nèi)存頁面設(shè)

56、一內(nèi)存頁面設(shè)一計時器計時器或或寄存器寄存器，或為進(jìn)程所有內(nèi)存頁面設(shè)一，或為進(jìn)程所有內(nèi)存頁面設(shè)一棧棧/鏈表，鏈表，P98）。LRU的軟件解決方案的軟件解決方案（LRU的近似算法）的近似算法）：二次機(jī)會二次機(jī)會(SC, Second Chance）置換算法置換算法時鐘時鐘(Clock)置換算法置換算法最近未使用最近未使用（NRU, Not Recently Used ）置換算法置換算法6. 頁面置換算法（頁面置換算法（續(xù)續(xù)3）n二次機(jī)會二次機(jī)會(SC, Second Chance）置換算法置換算法 FIFO法的一種改進(jìn)實現(xiàn)法的一種改進(jìn)實現(xiàn)實現(xiàn)實現(xiàn)：頁表目中增設(shè)訪問位頁表目中增設(shè)訪問位R，初值為，初

57、值為0，頁面訪問時置，頁面訪問時置1。發(fā)生缺頁中斷需置換發(fā)生缺頁中斷需置換時，時，OS按照按照先進(jìn)先出先進(jìn)先出置換算置換算法選擇某一頁面，檢查其法選擇某一頁面，檢查其訪問位訪問位，如果為，如果為0，則淘汰該，則淘汰該頁，如果為頁，如果為1，則將該位置，則將該位置0，把該頁放到內(nèi)存頁面鏈，把該頁放到內(nèi)存頁面鏈表的尾端，給它第二次駐留機(jī)會，再檢查內(nèi)存頁面鏈表的尾端，給它第二次駐留機(jī)會，再檢查內(nèi)存頁面鏈上的下一個頁面。如果查到鏈尾還未找到置換對象，上的下一個頁面。如果查到鏈尾還未找到置換對象，則再從鏈?zhǔn)组_始，進(jìn)行第則再從鏈?zhǔn)组_始，進(jìn)行第2趟掃描檢查。趟掃描檢查。優(yōu)點優(yōu)點：實現(xiàn)簡單，且性能比實現(xiàn)簡單，

58、且性能比FIFO好很多；好很多；缺點缺點：運行效率低，時間開銷大。運行效率低，時間開銷大。6. 頁面置換算法（續(xù)頁面置換算法（續(xù)4）n時鐘時鐘(Clock)置換算法置換算法 SC的一種改進(jìn)實現(xiàn)的一種改進(jìn)實現(xiàn)SC算法因為常需把給予二算法因為常需把給予二次駐留機(jī)會的頁面移到鏈尾次駐留機(jī)會的頁面移到鏈尾而降低效率，若把其所用的而降低效率，若把其所用的內(nèi)存頁面單向鏈表改為循環(huán)內(nèi)存頁面單向鏈表改為循環(huán)鏈表，則就不必在鏈中移動鏈表，則就不必在鏈中移動頁面了。這種改進(jìn)的頁面了。這種改進(jìn)的SC法法就是就是Clock法。法。顯然，顯然，Clock算法的頁面調(diào)度性能與算法的頁面調(diào)度性能與SC法一樣，但其自法一樣，

59、但其自身的運行效率比身的運行效率比SC法高，因而比法高，因而比SC法更常用。其實，法更常用。其實，Clock法法從某種角度從某種角度也可看作一種也可看作一種LRU近似算法。近似算法。6. 頁面置換算法頁面置換算法（續(xù)（續(xù)5）n最近未使用最近未使用（NRU, Not Recently Used ）置換算法置換算法 選擇在最近一段時間內(nèi)未使用過的一頁并淘汰之。選擇在最近一段時間內(nèi)未使用過的一頁并淘汰之。 實現(xiàn)實現(xiàn)：頁表目中增設(shè)訪問位：頁表目中增設(shè)訪問位R，修改位，修改位M。啟動進(jìn)程時，。啟動進(jìn)程時，R、M置置0，隨后，隨后R被定期清零。根據(jù)被定期清零。根據(jù)R、M的值，進(jìn)程在的值，進(jìn)程在內(nèi)存的頁面分

60、為內(nèi)存的頁面分為4類：類：00類、類、 01類、類、 1 10類、類、 1111類。發(fā)生類。發(fā)生缺頁中斷需置換時缺頁中斷需置換時，OS從編號最小的非空類中隨機(jī)選擇一從編號最小的非空類中隨機(jī)選擇一頁淘汰。頁淘汰。 特點特點：易實現(xiàn)，性能上也夠用：易實現(xiàn)，性能上也夠用。 其他置換算法其他置換算法（僅作一般了解）（僅作一般了解）n最少使用頻率最少使用頻率（LFU, Least Frequently Used ）置換置換算法算法 選擇在最近時期使用頻率最少的頁面淘汰。選擇在最近時期使用頻率最少的頁面淘汰。n頁面緩沖置換算法頁面緩沖置換算法 =FIFO+page-buffer+write-delay 該