操作系統(tǒng)原理-第3章-存儲器管理ppt課件

1、第第3 3章章 存儲器管理存儲器管理n3.1 內(nèi)存管理概述次重點(diǎn)內(nèi)存管理概述次重點(diǎn)n3.2 分區(qū)存儲管理次重點(diǎn)分區(qū)存儲管理次重點(diǎn)n3.3 頁式存儲管理重點(diǎn)頁式存儲管理重點(diǎn)n3.4 段式存儲管理非重點(diǎn)段式存儲管理非重點(diǎn)n3.5 段頁式存儲管理自學(xué)段頁式存儲管理自學(xué)內(nèi)存管理的中心義務(wù)內(nèi)存管理的中心義務(wù)Cache、內(nèi)存、外存三級存儲構(gòu)造、內(nèi)存、外存三級存儲構(gòu)造程序程序和數(shù)和數(shù)據(jù)的據(jù)的長期長期保管保管程序和程序和數(shù)據(jù)進(jìn)數(shù)據(jù)進(jìn)入內(nèi)存入內(nèi)存才干被才干被處置處置緩存一緩存一些關(guān)鍵些關(guān)鍵數(shù)據(jù)數(shù)據(jù)如何讓容量有限的內(nèi)存被多義務(wù)平安高效地共享是現(xiàn)代操作如何讓容量有限的內(nèi)存被多義務(wù)平安高效地共享是現(xiàn)代操作系統(tǒng)內(nèi)存管理

2、的中心義務(wù)，也是本章引見的主要內(nèi)容。系統(tǒng)內(nèi)存管理的中心義務(wù)，也是本章引見的主要內(nèi)容。本章需掌握的知識要點(diǎn)本章需掌握的知識要點(diǎn)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ū)根本分頁根本分頁懇求分頁懇求分頁實(shí)存實(shí)存 與與 虛存虛存分頁分頁 與與 分段分段延續(xù)延續(xù) 與與 離散離散3.1 3.1 存儲管理的概念存儲管理的概念1、存儲管理戰(zhàn)略的分類、存儲管理戰(zhàn)略的分類 OS本身的程序和數(shù)據(jù)與其他程序一同共享主存，為平安起本身的程序和數(shù)據(jù)與其他程序一同共享主存，為平安起見，多道程序系統(tǒng)常由

3、見，多道程序系統(tǒng)常由OS把內(nèi)存初始化為系統(tǒng)區(qū)和用戶區(qū)兩大把內(nèi)存初始化為系統(tǒng)區(qū)和用戶區(qū)兩大部分：部分： 內(nèi)存 系統(tǒng)區(qū)存放系統(tǒng)區(qū)存放OSOS程序和數(shù)據(jù)程序和數(shù)據(jù) 用戶區(qū)存放用戶程序、數(shù)據(jù)用戶區(qū)存放用戶程序、數(shù)據(jù) 對用戶區(qū)內(nèi)存的管理可采取不同的戰(zhàn)略，這些戰(zhàn)略可以按照對用戶區(qū)內(nèi)存的管理可采取不同的戰(zhàn)略，這些戰(zhàn)略可以按照不同的方法進(jìn)展分類。不同的方法進(jìn)展分類。存儲管理戰(zhàn)略的分類存儲管理戰(zhàn)略的分類1靜態(tài)劃分及動態(tài)劃分靜態(tài)劃分及動態(tài)劃分 靜態(tài)劃分：固定分區(qū)、分頁、段頁式靜態(tài)劃分：固定分區(qū)、分頁、段頁式動態(tài)劃分：可變分區(qū)、分段、同伴系統(tǒng)動態(tài)劃分：可變分區(qū)、分段、同伴系統(tǒng)2實(shí)存管理與虛存管理實(shí)存管理與虛存管理

4、實(shí)存管理實(shí)存管理延續(xù)分配包括固定分區(qū)、可變分區(qū)和同伴系統(tǒng)延續(xù)分配包括固定分區(qū)、可變分區(qū)和同伴系統(tǒng)實(shí)分頁實(shí)分頁P(yáng)aging 實(shí)分段實(shí)分段Segmentation 虛存管理虛存管理懇求分頁懇求分頁(Demand paging)- 主流技術(shù)主流技術(shù)懇求分段懇求分段(Demand segmentation)段頁式段頁式 segmentation with paging 離散分配離散分配2 2、物理地址和邏輯地址、物理地址和邏輯地址l物理地址：存儲單元的地址編號，又稱絕對地址或?qū)嵉刂肺锢淼刂罚捍鎯卧牡刂肪幪?，又稱絕對地址或?qū)嵉刂穕-物理地址的集合稱為物理地址空間物理地址的集合稱為物理地址空間l邏輯地

5、址：用戶程序中運(yùn)用的地址，又稱相對地址或虛地址邏輯地址：用戶程序中運(yùn)用的地址，又稱相對地址或虛地址l-邏輯地址的集合稱為邏輯地址空間邏輯地址的集合稱為邏輯地址空間l-邏輯地址空間起始地址普通是邏輯地址空間起始地址普通是0l程序裝入內(nèi)存時(shí)后，必需將邏輯地址轉(zhuǎn)換成物理地址才干運(yùn)轉(zhuǎn)，普通采用可重定位方式：l靜態(tài)重定位：運(yùn)轉(zhuǎn)之前，由裝入程序完成重定位l動態(tài)重定位：運(yùn)轉(zhuǎn)時(shí)，由硬件地址變換機(jī)構(gòu)完成重定位裝入裝入Load 1, 1200 3456 1200物理地址空間物理地址空間Load 1, data1data1 3456源程序源程序Load 1, 200 34560100200編譯編譯銜接銜接邏輯地址空

6、間邏輯地址空間BA=10001100系統(tǒng)采用靜態(tài)重定位，系統(tǒng)采用靜態(tài)重定位，程序裝入內(nèi)存時(shí)的例如內(nèi)外存副本不一程序裝入內(nèi)存時(shí)的例如內(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)存時(shí)的例如內(nèi)外存副本程序裝入內(nèi)存時(shí)的例如內(nèi)外存副本一致：一致：10003456LOAD 1, 2000100200300LOAD 1, 2003456邏輯地址

7、空間邏輯地址空間110012001300物理地址空間物理地址空間200VR+1000BR運(yùn)轉(zhuǎn)時(shí)動態(tài)計(jì)算物理地址運(yùn)轉(zhuǎn)時(shí)動態(tài)計(jì)算物理地址顯然，采用動態(tài)重定位時(shí)，程序可在內(nèi)存中浮動。顯然，采用動態(tài)重定位時(shí)，程序可在內(nèi)存中浮動。3 3、程序的鏈接、程序的鏈接l程序經(jīng)編譯后，構(gòu)成一組目的模塊，再利用鏈接程序?qū)⑦@組目的模塊鏈接成裝入模塊可執(zhí)行文件。三種鏈接方式：靜態(tài)鏈接裝入時(shí)動態(tài)鏈接運(yùn)轉(zhuǎn)時(shí)動態(tài)鏈接4 4、存儲管理的功能、存儲管理的功能1內(nèi)存空間的分配與回收內(nèi)存空間的分配與回收記錄內(nèi)存的運(yùn)用情況記錄內(nèi)存的運(yùn)用情況 設(shè)置相應(yīng)的內(nèi)存分塊表內(nèi)存分配回收的設(shè)置相應(yīng)的內(nèi)存分塊表內(nèi)存分配回收的根據(jù)根據(jù)內(nèi)存空間劃分問題？

8、內(nèi)存空間劃分問題？靜態(tài)或動態(tài)，等長或不等長靜態(tài)或動態(tài)，等長或不等長確定分配算法確定分配算法思索延續(xù)性與離散性，駐留性與交換思索延續(xù)性與離散性，駐留性與交換性，一次性與多次性，靜態(tài)方式與動態(tài)方式性，一次性與多次性，靜態(tài)方式與動態(tài)方式內(nèi)存碎片問題及處理方法內(nèi)存碎片問題及處理方法確定回收戰(zhàn)略確定回收戰(zhàn)略 2地址轉(zhuǎn)換又稱地址重定位、地址映射地址轉(zhuǎn)換又稱地址重定位、地址映射指為了保證指為了保證CPU執(zhí)行指令時(shí)可正確訪問存儲單元，需執(zhí)行指令時(shí)可正確訪問存儲單元，需將用戶程序中的邏輯地址相對地址，虛地址轉(zhuǎn)換將用戶程序中的邏輯地址相對地址，虛地址轉(zhuǎn)換為運(yùn)轉(zhuǎn)時(shí)由機(jī)器直接尋址的物理地址絕對地址，實(shí)為運(yùn)轉(zhuǎn)時(shí)由機(jī)器直

9、接尋址的物理地址絕對地址，實(shí)地址的過程地址的過程3內(nèi)存的共享與維護(hù)內(nèi)存的共享與維護(hù)進(jìn)程共用一樣內(nèi)存區(qū)可節(jié)省空間，便于通訊，所共進(jìn)程共用一樣內(nèi)存區(qū)可節(jié)省空間，便于通訊，所共享的代碼應(yīng)為純代碼或者叫可重入的代碼享的代碼應(yīng)為純代碼或者叫可重入的代碼內(nèi)存維護(hù)限定程序只能訪問本人所在的內(nèi)存區(qū)，維內(nèi)存維護(hù)限定程序只能訪問本人所在的內(nèi)存區(qū)，維護(hù)了護(hù)了OS和其他程序和其他程序常用界限存放器對法和存常用界限存放器對法和存取控制字來實(shí)現(xiàn)取控制字來實(shí)現(xiàn)4內(nèi)存的擴(kuò)展內(nèi)存的擴(kuò)展常用覆蓋、交換和虛擬存儲技術(shù)等實(shí)現(xiàn)對內(nèi)存的邏常用覆蓋、交換和虛擬存儲技術(shù)等實(shí)現(xiàn)對內(nèi)存的邏輯擴(kuò)展，以使小內(nèi)存可以運(yùn)轉(zhuǎn)大程序輯擴(kuò)展，以使小內(nèi)存可以運(yùn)

10、轉(zhuǎn)大程序4 4、存儲管理的功能續(xù)、存儲管理的功能續(xù)1覆蓋技術(shù)覆蓋技術(shù)把內(nèi)存的同一區(qū)域分配給一道程序的的假設(shè)干個(gè)子程序或數(shù)據(jù)段把內(nèi)存的同一區(qū)域分配給一道程序的的假設(shè)干個(gè)子程序或數(shù)據(jù)段需求的時(shí)候?qū)⑵湔{(diào)入內(nèi)存需求的時(shí)候?qū)⑵湔{(diào)入內(nèi)存2交換技術(shù)交換技術(shù)將內(nèi)存中暫時(shí)不用的信息交換到外存上將內(nèi)存中暫時(shí)不用的信息交換到外存上將需求的數(shù)據(jù)從外存調(diào)入內(nèi)存將需求的數(shù)據(jù)從外存調(diào)入內(nèi)存3虛擬存儲虛擬存儲主流技術(shù)主流技術(shù)經(jīng)過軟件和硬件技術(shù)把內(nèi)存和外存構(gòu)成一個(gè)二級存儲體系經(jīng)過軟件和硬件技術(shù)把內(nèi)存和外存構(gòu)成一個(gè)二級存儲體系在用戶眼里是一個(gè)大容量存儲器速度是內(nèi)存的，容量是外存的在用戶眼里是一個(gè)大容量存儲器速度是內(nèi)存的，容量是外

11、存的也利用了覆蓋和交換技術(shù)也利用了覆蓋和交換技術(shù)5 5、內(nèi)存擴(kuò)展技術(shù)、內(nèi)存擴(kuò)展技術(shù) -以時(shí)間換空間以時(shí)間換空間覆蓋表示圖覆蓋表示圖主程序主程序(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ū)6 6、存儲管理分類、存儲管理分類按內(nèi)存劃分戰(zhàn)略按內(nèi)存劃分戰(zhàn)略n分區(qū)式存儲管理：操作系統(tǒng)對內(nèi)存進(jìn)展分區(qū)，規(guī)定每個(gè)分區(qū)只分區(qū)式存儲管理：操作系統(tǒng)對內(nèi)存進(jìn)展分區(qū)，規(guī)定每個(gè)分區(qū)只能裝入一個(gè)作業(yè)或進(jìn)程。能裝入一個(gè)作業(yè)或進(jìn)程。-包括單一延續(xù)

12、區(qū)、固定分區(qū)和可變分包括單一延續(xù)區(qū)、固定分區(qū)和可變分區(qū)。區(qū)。n分頁式存儲管理：內(nèi)存空間和虛存空間都分成大小相等的頁分頁式存儲管理：內(nèi)存空間和虛存空間都分成大小相等的頁如如4k，虛存空間每一頁可以按照某種戰(zhàn)略裝入內(nèi)存空間的某，虛存空間每一頁可以按照某種戰(zhàn)略裝入內(nèi)存空間的某一頁。一頁。-目前最常用的的內(nèi)存管理方式。目前最常用的的內(nèi)存管理方式。n分段式存儲管理：內(nèi)存以段為單位進(jìn)展動態(tài)分區(qū)，進(jìn)程的段可分段式存儲管理：內(nèi)存以段為單位進(jìn)展動態(tài)分區(qū)，進(jìn)程的段可以裝入存儲空間的一個(gè)分區(qū)。以裝入存儲空間的一個(gè)分區(qū)。-便于編程及程序共享便于編程及程序共享n段頁式存儲管理：結(jié)合段式和頁式優(yōu)點(diǎn)，先對進(jìn)程空間分段，段頁

13、式存儲管理：結(jié)合段式和頁式優(yōu)點(diǎn)，先對進(jìn)程空間分段，再對每個(gè)段進(jìn)展分頁。開銷比較大，適用于大型系統(tǒng)。再對每個(gè)段進(jìn)展分頁。開銷比較大，適用于大型系統(tǒng)。3.2 3.2 分區(qū)式存儲管理分區(qū)式存儲管理 早期的一類實(shí)存早期的一類實(shí)存管理技術(shù)管理技術(shù) 系統(tǒng)給每個(gè)作業(yè)或進(jìn)程分配一個(gè)延續(xù)的內(nèi)存系統(tǒng)給每個(gè)作業(yè)或進(jìn)程分配一個(gè)延續(xù)的內(nèi)存分區(qū)。分區(qū)。單一延續(xù)區(qū)分配靜態(tài)分區(qū)技術(shù)單一延續(xù)區(qū)分配靜態(tài)分區(qū)技術(shù)固定分區(qū)分配靜態(tài)分區(qū)技術(shù)固定分區(qū)分配靜態(tài)分區(qū)技術(shù)可變分區(qū)分配動態(tài)分區(qū)技術(shù)可變分區(qū)分配動態(tài)分區(qū)技術(shù)可重定位分區(qū)分配動態(tài)分區(qū)技術(shù)可重定位分區(qū)分配動態(tài)分區(qū)技術(shù)同伴系統(tǒng)動態(tài)分區(qū)技術(shù)同伴系統(tǒng)動態(tài)分區(qū)技術(shù)1. 單一延續(xù)區(qū)存儲管理單一延

14、續(xù)區(qū)存儲管理系統(tǒng)靜態(tài)地將內(nèi)存劃分系統(tǒng)靜態(tài)地將內(nèi)存劃分為兩個(gè)區(qū)域：為兩個(gè)區(qū)域：一個(gè)供操作系統(tǒng)運(yùn)用一個(gè)供操作系統(tǒng)運(yùn)用一個(gè)供用戶運(yùn)用，且每一個(gè)供用戶運(yùn)用，且每次只能裝入一個(gè)作業(yè)或進(jìn)次只能裝入一個(gè)作業(yè)或進(jìn)程程適用于單用戶單義務(wù)操適用于單用戶單義務(wù)操作系統(tǒng)。作系統(tǒng)。操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序0 xFFF.0系統(tǒng)預(yù)先把可分配的內(nèi)存空間分割成假設(shè)干個(gè)延續(xù)區(qū)域，每一系統(tǒng)預(yù)先把可分配的內(nèi)存空間分割成假設(shè)干個(gè)延續(xù)區(qū)域，每一區(qū)域稱為分區(qū)，每個(gè)分區(qū)的大小可以一樣也可以不同，分區(qū)的區(qū)域稱為分區(qū)，每個(gè)分區(qū)的大小可以一樣也可以不同，分區(qū)的個(gè)數(shù)與大小固定不變，每個(gè)分區(qū)每次只能裝一個(gè)作業(yè)。個(gè)數(shù)與大小固定不變，每個(gè)分區(qū)每次

15、只能裝一個(gè)作業(yè)。2. 2. 固定分區(qū)存儲管理固定分區(qū)存儲管理 單一延續(xù)區(qū)單一延續(xù)區(qū)在多道程序系統(tǒng)中的直接運(yùn)用在多道程序系統(tǒng)中的直接運(yùn)用OS0abcdjob2空空 內(nèi)存內(nèi)存當(dāng)前運(yùn)轉(zhuǎn)作當(dāng)前運(yùn)轉(zhuǎn)作業(yè)所在分區(qū)業(yè)所在分區(qū)下限存放器下限存放器上限存放器上限存放器2bcCPUjob3 設(shè)置設(shè)置“主存分配表，來管理主存空間的運(yùn)用主存分配表，來管理主存空間的運(yùn)用1 1主存空間分配與釋放主存空間分配與釋放區(qū)號區(qū)號起始地址起始地址長度長度(KB)占用標(biāo)志占用標(biāo)志1aS102bS2Job23cS3Job3三個(gè)分區(qū)的主存分配表三個(gè)分區(qū)的主存分配表主存分配：尋覓沒被主存分配：尋覓沒被占用且長度滿足進(jìn)程占用且長度滿足進(jìn)程要

16、求的分區(qū)。典型如要求的分區(qū)。典型如順序分配法。順序分配法。主存釋放：更改主存分配表相應(yīng)欄目。主存釋放：更改主存分配表相應(yīng)欄目。2 2地址轉(zhuǎn)換與存儲維護(hù)地址轉(zhuǎn)換與存儲維護(hù)l地址轉(zhuǎn)換地址轉(zhuǎn)換l常采用常采用“靜態(tài)重定位方法靜態(tài)重定位方法l作業(yè)在裝入時(shí)：物理地址作業(yè)在裝入時(shí)：物理地址=邏輯地址邏輯地址+分區(qū)下限地分區(qū)下限地址址l存儲存儲 維護(hù)維護(hù)l采用采用“界限存放器對法界限存放器對法l程序執(zhí)行時(shí)判別：下限地址程序執(zhí)行時(shí)判別：下限地址 = 物理地址物理地址 =L. b+頁號頁號p p 頁內(nèi)地址頁內(nèi)地址d dP d頁表地址存放器頁表地址存放器頁表長度存放器頁表長度存放器邏輯地址邏輯地址物理地址物理地址主

17、要問題：兩次內(nèi)存訪問主要問題：兩次內(nèi)存訪問引入快表引入快表 加快地址轉(zhuǎn)換加快地址轉(zhuǎn)換快表運(yùn)用聯(lián)想存儲器associative memory，也稱為相聯(lián)存儲器，在IBM系統(tǒng)中稱TLBTranslation lookaside buffers 用途：保管正在運(yùn)轉(zhuǎn)進(jìn)程的部分頁表項(xiàng)，以快速重定位快表表目內(nèi)容：頁號、內(nèi)存塊號、標(biāo)識位、淘汰位快表的特點(diǎn)：可按內(nèi)容并行查找快表命中率：曾經(jīng)證明，16個(gè)表目可達(dá)90%以上。 Intel 80 x86/Pentium有32項(xiàng)，SGI MIPS R4000有48項(xiàng)實(shí)際根據(jù)：程序的部分性；運(yùn)用快表進(jìn)展地址轉(zhuǎn)換運(yùn)用快表進(jìn)展地址轉(zhuǎn)換地址越界地址越界p 頁表頁表 L比較比較

18、P=Lpp .快表快表 b+頁號頁號p p 頁內(nèi)地址頁內(nèi)地址d dP d頁表地址存放器頁表地址存放器頁表長度存放器頁表長度存放器邏輯地址邏輯地址.物理地址物理地址統(tǒng)計(jì)闡明，統(tǒng)計(jì)闡明，16個(gè)表項(xiàng)，命中率個(gè)表項(xiàng)，命中率95%以上以上擴(kuò)展：多級頁表擴(kuò)展：多級頁表問題：問題：32位地址的邏輯地址空間，假設(shè)頁面大小為位地址的邏輯地址空間，假設(shè)頁面大小為4K，那，那么需求么需求1M個(gè)頁表表項(xiàng)，假設(shè)每個(gè)頁表表項(xiàng)個(gè)頁表表項(xiàng)，假設(shè)每個(gè)頁表表項(xiàng)1B，那么每個(gè)進(jìn)，那么每個(gè)進(jìn)程需求程需求1MB的延續(xù)內(nèi)存空間來存儲頁表。的延續(xù)內(nèi)存空間來存儲頁表。0111231頁號頁號P頁內(nèi)位移量頁內(nèi)位移量W編號編號01048575相對

19、地址相對地址0409564位邏輯地址空間呢？位邏輯地址空間呢？需求需求4096G個(gè)頁表項(xiàng)。個(gè)頁表項(xiàng)。一種處理方案：采用多級頁表，來使延續(xù)空間變成離散空間一種處理方案：采用多級頁表，來使延續(xù)空間變成離散空間二級頁表二級頁表 以以32位邏輯地址空間位邏輯地址空間為例為例0111231頁目錄號頁目錄號頁內(nèi)位移量頁內(nèi)位移量W頁表位移頁表位移22 21延續(xù)的內(nèi)延續(xù)的內(nèi)存分配變存分配變成了離散成了離散分配分配64位地址位地址空間能否空間能否可以采用可以采用二級頁表？二級頁表？頁目錄地址頁目錄地址目錄位移目錄位移頁表位移頁表位移頁位移頁位移虛擬地址虛擬地址頁表地址頁表地址.頁目錄每進(jìn)程一個(gè)頁目錄每進(jìn)程一個(gè)塊

20、號塊號. 頁頁 表表代碼或數(shù)據(jù)代碼或數(shù)據(jù).物理頁物理頁+二級頁表地址轉(zhuǎn)換未畫出快表二級頁表地址轉(zhuǎn)換未畫出快表0310/10/10/10/10/1017空閑塊數(shù)空閑塊數(shù)n空塊管理空塊管理位示圖位示圖(用于外存分配時(shí)用于外存分配時(shí)常叫盤圖常叫盤圖)運(yùn)用時(shí)需進(jìn)展字位號到塊號的轉(zhuǎn)換：運(yùn)用時(shí)需進(jìn)展字位號到塊號的轉(zhuǎn)換：b=i*w+jb：塊號，：塊號，i：字號，：字號，w：字的位數(shù)，：字的位數(shù)，j：字內(nèi)位數(shù)：字內(nèi)位數(shù)3. 頁的分配與回收頁的分配與回收內(nèi)存分配算法內(nèi)存分配算法計(jì)算一個(gè)作業(yè)所需求的總塊數(shù)N查位示圖，看看能否還有N個(gè)空閑塊假設(shè)有足夠的空閑塊，那么頁表長度設(shè)為N，填入PCB中；懇求頁表區(qū)，把頁表始址

21、填入PCB依次分配N個(gè)空閑塊，將塊號和頁號填入頁表修正位示圖4、頁的共享與維護(hù)、頁的共享與維護(hù)u頁的共享頁的共享u多個(gè)進(jìn)程的虛頁對應(yīng)同一個(gè)物理地址空間；多個(gè)進(jìn)程的虛頁對應(yīng)同一個(gè)物理地址空間；u共享不易實(shí)現(xiàn)共享不易實(shí)現(xiàn)(P93及圖及圖3-9)u頁的維護(hù)頁的維護(hù)u越界檢查：頁表長度存放器；越界檢查：頁表長度存放器；u存取控制檢查：頁表中設(shè)置有存取控制字段，普存取控制檢查：頁表中設(shè)置有存取控制字段，普通是通是“只讀、只讀、“可寫以及可寫以及“執(zhí)行三種權(quán)限執(zhí)行三種權(quán)限的組合。的組合。5、主存空間利用率、主存空間利用率u內(nèi)存利用率高，且對用戶透明，根本處理了內(nèi)存利用率高，且對用戶透明，根本處理了“碎碎片

22、問題片問題u每個(gè)空閑的內(nèi)存塊都是一個(gè)可分配的單位，徹底每個(gè)空閑的內(nèi)存塊都是一個(gè)可分配的單位，徹底消除了消除了“外碎片；外碎片；u雖然進(jìn)程最后一頁能夠存在雖然進(jìn)程最后一頁能夠存在“內(nèi)碎片，但頁面內(nèi)碎片，但頁面相對較小，內(nèi)碎片也很小。相對較小，內(nèi)碎片也很小。6. 實(shí)分頁存儲管理方式小結(jié)實(shí)分頁存儲管理方式小結(jié)n優(yōu)點(diǎn)：內(nèi)存利用率高，處理了碎片問題；優(yōu)點(diǎn)：內(nèi)存利用率高，處理了碎片問題；n 便于管理。便于管理。n缺陷：不易實(shí)現(xiàn)共享見缺陷：不易實(shí)現(xiàn)共享見P93；n 不便于頁面動態(tài)增長；不便于頁面動態(tài)增長；n 進(jìn)程仍受內(nèi)存可用空間大小的限進(jìn)程仍受內(nèi)存可用空間大小的限制；制；n 所需硬件支持較多。所需硬件支持較

23、多。3.3.2 虛擬頁式存儲管理虛擬頁式存儲管理u實(shí)分頁式存儲管理要求作業(yè)全部裝入內(nèi)存后才干運(yùn)實(shí)分頁式存儲管理要求作業(yè)全部裝入內(nèi)存后才干運(yùn)轉(zhuǎn)，存在以下問題：轉(zhuǎn)，存在以下問題：u當(dāng)作業(yè)所要求的內(nèi)存空間大于物理內(nèi)存總?cè)萘?，無當(dāng)作業(yè)所要求的內(nèi)存空間大于物理內(nèi)存總?cè)萘?，無法運(yùn)轉(zhuǎn)；法運(yùn)轉(zhuǎn)；u當(dāng)有大量作業(yè)要求運(yùn)轉(zhuǎn)，而內(nèi)存容量缺乏以包容一當(dāng)有大量作業(yè)要求運(yùn)轉(zhuǎn)，而內(nèi)存容量缺乏以包容一切作業(yè)，只能是少數(shù)作業(yè)先運(yùn)轉(zhuǎn)，其他大量的作業(yè)切作業(yè)，只能是少數(shù)作業(yè)先運(yùn)轉(zhuǎn)，其他大量的作業(yè)在外存等待。在外存等待。u處理方法處理方法u擴(kuò)展物理內(nèi)存：添加本錢；擴(kuò)展物理內(nèi)存：添加本錢；u虛擬存儲技術(shù)：允許作業(yè)僅部分裝入內(nèi)存即可運(yùn)轉(zhuǎn)，虛

24、擬存儲技術(shù)：允許作業(yè)僅部分裝入內(nèi)存即可運(yùn)轉(zhuǎn)，其實(shí)際根據(jù)是程序部分性原理。其實(shí)際根據(jù)是程序部分性原理。程序部分性原理程序部分性原理 -Denning，1968程序在執(zhí)行時(shí)呈現(xiàn)出高度的部分性特征；即在一較短的時(shí)間內(nèi)，程序的執(zhí)行僅局限于某個(gè)部分；相應(yīng)地，它所訪問的存儲空間也局限于某個(gè)區(qū)域。程序部分性表如今時(shí)間與空間兩個(gè)方面：時(shí)間部分性：一條指令被執(zhí)行了，那么在不久的未來它能夠再次被執(zhí)行；空間部分性：假設(shè)某一存儲單元被訪問，那么在不久之后，與該存儲單元相鄰的單元也能夠被訪問。因此，作業(yè)可以不用全部裝入內(nèi)存即可運(yùn)轉(zhuǎn)。因此，作業(yè)可以不用全部裝入內(nèi)存即可運(yùn)轉(zhuǎn)。虛擬存儲器概念虛擬存儲器概念1961年由英國曼徹

25、斯特大學(xué)的年由英國曼徹斯特大學(xué)的Fotheringham提出，今天的提出，今天的OS普遍采用這一技術(shù)管理內(nèi)存。普遍采用這一技術(shù)管理內(nèi)存。程序僅需將當(dāng)前要運(yùn)轉(zhuǎn)的頁或段裝入內(nèi)存即可運(yùn)轉(zhuǎn)；程序僅需將當(dāng)前要運(yùn)轉(zhuǎn)的頁或段裝入內(nèi)存即可運(yùn)轉(zhuǎn)；運(yùn)轉(zhuǎn)時(shí)，假設(shè)需求訪問的頁或段不在內(nèi)存中稱為缺頁或缺運(yùn)轉(zhuǎn)時(shí)，假設(shè)需求訪問的頁或段不在內(nèi)存中稱為缺頁或缺段，由段，由OS提供的懇求調(diào)頁段功能，將其調(diào)入內(nèi)存；提供的懇求調(diào)頁段功能，將其調(diào)入內(nèi)存；假設(shè)內(nèi)存已滿，那么需按照預(yù)定的置換戰(zhàn)略，將暫時(shí)不用的頁假設(shè)內(nèi)存已滿，那么需按照預(yù)定的置換戰(zhàn)略，將暫時(shí)不用的頁或段調(diào)出外存，騰出足夠的存儲空間，在裝入所缺的頁或段?；蚨握{(diào)出外存，騰出足夠

26、的存儲空間，在裝入所缺的頁或段。對于用戶而言，看到的是一個(gè)大容量的內(nèi)存容量是外存的，對于用戶而言，看到的是一個(gè)大容量的內(nèi)存容量是外存的，速度是內(nèi)存的，但實(shí)踐上是虛的，因此稱為虛擬存儲器。速度是內(nèi)存的，但實(shí)踐上是虛的，因此稱為虛擬存儲器。1 1、虛擬頁式存儲管理根本思想、虛擬頁式存儲管理根本思想實(shí)分頁和虛擬存儲技術(shù)的結(jié)合，也叫懇求分頁存儲管理。實(shí)分頁和虛擬存儲技術(shù)的結(jié)合，也叫懇求分頁存儲管理。按照實(shí)分頁方式進(jìn)展分頁和分塊；按照實(shí)分頁方式進(jìn)展分頁和分塊；進(jìn)程運(yùn)轉(zhuǎn)時(shí)，只需部分頁面在內(nèi)存；進(jìn)程運(yùn)轉(zhuǎn)時(shí)，只需部分頁面在內(nèi)存；當(dāng)進(jìn)程訪問的頁不在內(nèi)存時(shí)將產(chǎn)生缺頁中斷，由中斷效當(dāng)進(jìn)程訪問的頁不在內(nèi)存時(shí)將產(chǎn)生缺頁

27、中斷，由中斷效力程序把所缺頁裝入內(nèi)存力程序把所缺頁裝入內(nèi)存假設(shè)內(nèi)存空間已滿，需求根據(jù)頁面置換戰(zhàn)略頁面調(diào)度假設(shè)內(nèi)存空間已滿，需求根據(jù)頁面置換戰(zhàn)略頁面調(diào)度算法淘汰某個(gè)內(nèi)存頁面，再裝入所缺頁面。算法淘汰某個(gè)內(nèi)存頁面，再裝入所缺頁面。本節(jié)重點(diǎn)引見頁面調(diào)度算法。本節(jié)重點(diǎn)引見頁面調(diào)度算法。2. 地址轉(zhuǎn)換及相應(yīng)硬件支持地址轉(zhuǎn)換及相應(yīng)硬件支持1頁表機(jī)制頁表機(jī)制虛分頁地址轉(zhuǎn)換方式和實(shí)分頁類似，但也有所區(qū)別。虛分頁地址轉(zhuǎn)換方式和實(shí)分頁類似，但也有所區(qū)別。形狀位形狀位P：該頁面能否曾經(jīng)調(diào)入內(nèi)存：該頁面能否曾經(jīng)調(diào)入內(nèi)存訪問位訪問位A，記錄該頁被訪問過的標(biāo)志或被訪問過的次數(shù)，和修正位一同做，記錄該頁被訪問過的標(biāo)志或被訪

28、問過的次數(shù)，和修正位一同做為頁面置換的根據(jù)；為頁面置換的根據(jù)；修正位修正位W：該頁面在掉入內(nèi)存后能否被修正正，如被修正正，調(diào)出內(nèi)存時(shí)，：該頁面在掉入內(nèi)存后能否被修正正，如被修正正，調(diào)出內(nèi)存時(shí)，需先將其寫入內(nèi)存；需先將其寫入內(nèi)存；存取控制：對該頁的訪問權(quán)限，如只讀、可寫、可執(zhí)行，或三者的結(jié)合存取控制：對該頁的訪問權(quán)限，如只讀、可寫、可執(zhí)行，或三者的結(jié)合外存地址：該頁在外存上的地址，當(dāng)該頁面不在內(nèi)存時(shí)，據(jù)此從外存調(diào)入外存地址：該頁在外存上的地址，當(dāng)該頁面不在內(nèi)存時(shí)，據(jù)此從外存調(diào)入頁號頁號塊號塊號形狀位形狀位P訪問位訪問位A修正位修正位W外存地址外存地址存取控制存取控制2缺頁中斷缺頁中斷Page F

29、ault機(jī)構(gòu)機(jī)構(gòu)在地址映射過程中，所訪問的頁不在內(nèi)存時(shí)，便產(chǎn)生一缺頁中斷；OS接到此中斷信號后，就調(diào)出缺頁中斷處置程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，更新頁表，完成重定位。這期間能夠調(diào)用置換程序。缺頁中斷與常規(guī)中斷的不同之處：常規(guī)中斷是在一條指令執(zhí)行完之后呼應(yīng)與處置；缺頁中斷是在指令執(zhí)行期間產(chǎn)生和處置中斷信號；且在一條指令在執(zhí)行期間，能夠產(chǎn)生多次缺頁中斷。因此，對于缺頁中斷，普通按“缺點(diǎn)處置。3地址轉(zhuǎn)換地址轉(zhuǎn)換 首先檢索快表，假設(shè)找到，修正頁表項(xiàng)中的訪問位，然后利用頁表項(xiàng)中內(nèi)容，構(gòu)成物理地址。 假設(shè)在快表中未找到，那么檢索頁表，察看頁表項(xiàng)中的形狀位，假設(shè)該頁曾經(jīng)調(diào)入內(nèi)存，那么構(gòu)成物

30、理地址，并更新快表，當(dāng)快表滿時(shí)，應(yīng)淘汰一個(gè)頁表項(xiàng)； 假設(shè)該頁尚未調(diào)入內(nèi)存，那么產(chǎn)生缺頁中斷，懇求OS把該頁調(diào)入內(nèi)存，然后再完成重定位。3. 內(nèi)存分配戰(zhàn)略和分配算法內(nèi)存分配戰(zhàn)略和分配算法p 最小物理塊數(shù)確實(shí)定最小物理塊數(shù)確實(shí)定p 保證進(jìn)程正常運(yùn)轉(zhuǎn)所需的最少物理塊數(shù)；保證進(jìn)程正常運(yùn)轉(zhuǎn)所需的最少物理塊數(shù)；p 與指令的格式、功能和尋址方式有關(guān)。與指令的格式、功能和尋址方式有關(guān)。在為進(jìn)程分配內(nèi)存時(shí)，涉及到三個(gè)問題：1最小物理塊數(shù)確實(shí)定；2物理塊的分配戰(zhàn)略；3物理塊的分配算法。例：一條復(fù)雜指令能夠是2個(gè)或2個(gè)以上字節(jié)，能夠跨2個(gè)頁面，其源地址及目的地址所涉及的區(qū)域，能夠跨2個(gè)頁面，因此至少要為每個(gè)進(jìn)程分配

31、6個(gè)頁面，以保證指令的執(zhí)行。3. 內(nèi)存分配戰(zhàn)略和分配算法續(xù)內(nèi)存分配戰(zhàn)略和分配算法續(xù)p 物理塊的分配戰(zhàn)略物理塊的分配戰(zhàn)略p 固定分配部分置換：進(jìn)程分配的物理塊數(shù)不變，置換時(shí)從該固定分配部分置換：進(jìn)程分配的物理塊數(shù)不變，置換時(shí)從該進(jìn)程所占的物理塊中選擇換出對象；進(jìn)程所占的物理塊中選擇換出對象；p 可變分配全局置換：進(jìn)程占據(jù)的物理塊數(shù)由可變分配全局置換：進(jìn)程占據(jù)的物理塊數(shù)由OS根據(jù)進(jìn)程訪問根據(jù)進(jìn)程訪問的缺頁率進(jìn)展動態(tài)調(diào)整，置換時(shí)從一切進(jìn)程所占的物理塊中的缺頁率進(jìn)展動態(tài)調(diào)整，置換時(shí)從一切進(jìn)程所占的物理塊中選擇換出對象；選擇換出對象；p 可變分配部分置換：進(jìn)程占據(jù)的物理塊數(shù)由可變分配部分置換：進(jìn)程占據(jù)的

32、物理塊數(shù)由OS根據(jù)進(jìn)程訪問根據(jù)進(jìn)程訪問的缺頁率進(jìn)展動態(tài)調(diào)整，置換時(shí)從該進(jìn)程所占的物理塊中選的缺頁率進(jìn)展動態(tài)調(diào)整，置換時(shí)從該進(jìn)程所占的物理塊中選擇換出對象。擇換出對象。3. 內(nèi)存分配戰(zhàn)略和分配算法續(xù)內(nèi)存分配戰(zhàn)略和分配算法續(xù)p 物理塊的分配算法：采用固定分配戰(zhàn)略時(shí)，可采用以下算法物理塊的分配算法：采用固定分配戰(zhàn)略時(shí)，可采用以下算法確定進(jìn)程所能分配的物理塊。確定進(jìn)程所能分配的物理塊。p 平均分配算法平均分配算法p 按進(jìn)程長度比例分配按進(jìn)程長度比例分配p 按進(jìn)程優(yōu)先級分配按進(jìn)程優(yōu)先級分配p 按進(jìn)程長度和優(yōu)先級分配：一部分按進(jìn)程長度分配，一部分按進(jìn)程長度和優(yōu)先級分配：一部分按進(jìn)程長度分配，一部分按進(jìn)程優(yōu)

33、先級分配按進(jìn)程優(yōu)先級分配4. 頁面調(diào)入時(shí)機(jī)頁面調(diào)入時(shí)機(jī)將一個(gè)頁面從外存調(diào)入內(nèi)存的時(shí)機(jī)：將一個(gè)頁面從外存調(diào)入內(nèi)存的時(shí)機(jī)：懇求調(diào)入：當(dāng)發(fā)生缺頁頁面缺點(diǎn)時(shí)進(jìn)展，一次調(diào)入一頁；懇求調(diào)入：當(dāng)發(fā)生缺頁頁面缺點(diǎn)時(shí)進(jìn)展，一次調(diào)入一頁；實(shí)現(xiàn)簡單，但費(fèi)時(shí)。實(shí)現(xiàn)簡單，但費(fèi)時(shí)。預(yù)調(diào)入：頁面被訪問前就預(yù)先將其調(diào)入內(nèi)存；預(yù)調(diào)入：頁面被訪問前就預(yù)先將其調(diào)入內(nèi)存；懇求調(diào)入時(shí)，順便多調(diào)入幾頁；懇求調(diào)入時(shí)，順便多調(diào)入幾頁；進(jìn)程初次調(diào)入時(shí)，預(yù)先調(diào)入多頁進(jìn)程初次調(diào)入時(shí)，預(yù)先調(diào)入多頁5. 頁面調(diào)度淘汰頁面調(diào)度淘汰 / 置換算法置換算法n顛簸抖動顛簸抖動n OS頻繁進(jìn)展頁面調(diào)度，以致于調(diào)度頁面所需時(shí)間比頻繁進(jìn)展頁面調(diào)度，以致于調(diào)度頁面所

34、需時(shí)間比進(jìn)程實(shí)踐運(yùn)轉(zhuǎn)的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，進(jìn)程實(shí)踐運(yùn)轉(zhuǎn)的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)解體。這種景象稱為顛簸或抖動。甚至導(dǎo)致系統(tǒng)解體。這種景象稱為顛簸或抖動。n系統(tǒng)發(fā)生顛簸的緣由系統(tǒng)發(fā)生顛簸的緣由n頁面置換算法不合理頁面置換算法不合理n分配給進(jìn)程的物理頁面數(shù)太少分配給進(jìn)程的物理頁面數(shù)太少最正確最正確Optima，OPT算算法法淘汰以后不再需求的或最遠(yuǎn)的未來才會用到的頁面。淘汰以后不再需求的或最遠(yuǎn)的未來才會用到的頁面。這是一種理想算法，能保證最低缺頁率，但無法實(shí)現(xiàn)，這是一種理想算法，能保證最低缺頁率，但無法實(shí)現(xiàn)，普通作為衡量其他算法優(yōu)劣的一個(gè)規(guī)范。普通作為衡量其他算法優(yōu)

35、劣的一個(gè)規(guī)范。先進(jìn)先出先進(jìn)先出FIFO算法算法總是淘汰最先進(jìn)入內(nèi)存的頁面。總是淘汰最先進(jìn)入內(nèi)存的頁面。效率不高，而且還有效率不高，而且還有Belady異常景象：即添加內(nèi)存塊數(shù)異常景象：即添加內(nèi)存塊數(shù)后進(jìn)程的缺頁率能夠不降反增。后進(jìn)程的缺頁率能夠不降反增。Belady異常異常近期最少運(yùn)用近期最少運(yùn)用LRU算法算法選擇最后一次訪問時(shí)間間隔當(dāng)前時(shí)間最長的一頁并淘汰之。選擇最后一次訪問時(shí)間間隔當(dāng)前時(shí)間最長的一頁并淘汰之。計(jì)時(shí)法：在頁表中記錄該頁最后一次被訪問的時(shí)間計(jì)時(shí)法：在頁表中記錄該頁最后一次被訪問的時(shí)間堆棧法：最近訪問的頁面放入棧頂，最久未被訪問的自堆棧法：最近訪問的頁面放入棧頂，最久未被訪問的自

36、然就到了棧底。然就到了棧底。LRU的幾種近似算法的幾種近似算法LRU算法實(shí)際上性能很好，但實(shí)現(xiàn)代價(jià)高，常采用算法實(shí)際上性能很好，但實(shí)現(xiàn)代價(jià)高，常采用LRU近似算法。近似算法。二次時(shí)機(jī)二次時(shí)機(jī)Second Chance，SC淘汰算法淘汰算法時(shí)鐘時(shí)鐘clock淘汰算法淘汰算法最近未用最近未用Not Recently Used，NRU淘汰算法淘汰算法二次時(shí)機(jī)二次時(shí)機(jī)SC置換算法置換算法u實(shí)現(xiàn)：實(shí)現(xiàn)：u頁表目中設(shè)置訪問位頁表目中設(shè)置訪問位A，初值為，初值為0，頁面訪問時(shí)置，頁面訪問時(shí)置1。u需置換時(shí)，需置換時(shí)，OS按照按照FIFO置換算法選擇某一頁面，置換算法選擇某一頁面，檢查其訪問位，假設(shè)為檢查其訪

37、問位，假設(shè)為0，那么淘汰該頁；，那么淘汰該頁；u假設(shè)為假設(shè)為1，那么將該位置，那么將該位置0，把該頁放到，把該頁放到FIFO隊(duì)列隊(duì)列的尾端，給它第二次駐留時(shí)機(jī)，再檢查的尾端，給它第二次駐留時(shí)機(jī)，再檢查FIFO隊(duì)列隊(duì)列中的下一個(gè)頁面。中的下一個(gè)頁面。u假設(shè)查到假設(shè)查到FIFO隊(duì)列尾還未找到置換對象，那么再隊(duì)列尾還未找到置換對象，那么再從鏈?zhǔn)组_場，進(jìn)展第從鏈?zhǔn)组_場，進(jìn)展第2趟掃描檢查。趟掃描檢查。u優(yōu)缺陷優(yōu)缺陷u優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，且性能比優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，且性能比FIFO好很多；好很多；u缺陷：運(yùn)轉(zhuǎn)效率低，時(shí)間開銷大。缺陷：運(yùn)轉(zhuǎn)效率低，時(shí)間開銷大。時(shí)鐘時(shí)鐘Clock置換算法置換算法SC算法由于常需把給

38、予二次駐留時(shí)機(jī)的頁面移到鏈尾而降低效率，假設(shè)把其所用的內(nèi)存頁面單向鏈表改為循環(huán)鏈表，那么就不用在鏈中挪動頁面了。這種改良的SC法就是Clock法。顯然，Clock算法的頁面調(diào)度性能與SC法一樣，但其本身的運(yùn)轉(zhuǎn)效率比SC法高，因此比SC法更常用。最近未運(yùn)用最近未運(yùn)用NRU置換算法置換算法選擇在最近一段時(shí)間內(nèi)未運(yùn)用過的一頁并淘汰之。選擇在最近一段時(shí)間內(nèi)未運(yùn)用過的一頁并淘汰之。實(shí)現(xiàn)實(shí)現(xiàn)頁表目中設(shè)置訪問位頁表目中設(shè)置訪問位A，修正位，修正位M。A、M初始置初始置0，隨后，隨后A被定被定期清零。期清零。根據(jù)根據(jù)A、M的值，內(nèi)存頁面分為的值，內(nèi)存頁面分為4類：類：00、 01、 10、 11類。類。00：

39、A=0，M=0，直接淘汰，直接淘汰01：A=0，M=1，寫入外存后淘汰，寫入外存后淘汰10：A=1，M=0，直接淘汰，直接淘汰11：A=1，M=1，寫入外存后淘汰，寫入外存后淘汰需置換時(shí)，從編號最小的非空類中隨機(jī)選擇一頁淘汰。需置換時(shí)，從編號最小的非空類中隨機(jī)選擇一頁淘汰。 特點(diǎn)：易實(shí)現(xiàn)，性能上也夠用。特點(diǎn)：易實(shí)現(xiàn)，性能上也夠用。設(shè)某懇求分頁系統(tǒng)采用固定分配部分置換戰(zhàn)略，一進(jìn)程的頁面走向?yàn)樵O(shè)某懇求分頁系統(tǒng)采用固定分配部分置換戰(zhàn)略，一進(jìn)程的頁面走向?yàn)?、3、2、1、4、3、5、4、3、2、1、5，該進(jìn)程分得，該進(jìn)程分得3個(gè)頁架，初始為空，試計(jì)算個(gè)頁架，初始為空，試計(jì)算分別采用分別采用FIFO、L

40、RU、OPT置換算法時(shí)該進(jìn)程訪問過程中所發(fā)生的缺頁次置換算法時(shí)該進(jìn)程訪問過程中所發(fā)生的缺頁次數(shù)和依次被換出的頁面。數(shù)和依次被換出的頁面。解：解： FIFO 4 3 2 1 4 3 5 4 3 2 1 5 4 4 4 1 1 1 5 5 5 5 5 5 3 3 3 4 4 4 4 4 2 2 2 2 2 2 3 3 3 3 3 1 1 能否命中能否命中 x x x x x x x x x 所以該進(jìn)程運(yùn)轉(zhuǎn)時(shí)共發(fā)生缺頁中斷所以該進(jìn)程運(yùn)轉(zhuǎn)時(shí)共發(fā)生缺頁中斷9次，被換出的頁面依次是次，被換出的頁面依次是4、3、2、1、4、3。頁面置換例如頁面置換例如1頁架頁架1頁架頁架2頁架頁架3 LRU 4 3 2 1

41、 4 3 5 4 3 2 1 5棧：棧： 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 4 3 2 1 4 3 2 1 4 3 5 4 3 2 能否命中能否命中 x x x x x x x x x x 所以該進(jìn)程運(yùn)轉(zhuǎn)時(shí)共發(fā)生缺頁中斷所以該進(jìn)程運(yùn)轉(zhuǎn)時(shí)共發(fā)生缺頁中斷10次，被換出的次，被換出的頁面依次是頁面依次是4、3、2、1、5、4、3。頁面置換例如頁面置換例如1 OPT 4 3 2 1 4 3 5 4 3 2 1 5頁架頁架1 4 4 4 4 4 4 4 4 4 2 2 2頁架頁架2 3 3 3 3 3 3 3 3 3 1 1頁架頁架3 2 1 1 1 5 5 5

42、 5 5 5 能否命中能否命中 x x x x x x x 所以該進(jìn)程運(yùn)轉(zhuǎn)時(shí)共發(fā)生缺頁中斷所以該進(jìn)程運(yùn)轉(zhuǎn)時(shí)共發(fā)生缺頁中斷7次，被換出的次，被換出的頁面依次是頁面依次是2、1、4、3。頁面置換例如頁面置換例如1n分配給進(jìn)程的物理頁面數(shù)分配給進(jìn)程的物理頁面數(shù)n頁面本身的大小頁面本身的大小n程序的編制方法程序的編制方法n頁面淘汰算法頁面淘汰算法例子例子3.3設(shè)某懇求分頁系設(shè)某懇求分頁系統(tǒng)采用固定分配部分置統(tǒng)采用固定分配部分置換戰(zhàn)略，置換算法為換戰(zhàn)略，置換算法為LRU。進(jìn)程分得。進(jìn)程分得3頁架，頁架，初始時(shí)全空，以下代碼初始時(shí)全空，以下代碼占占1頁，頁面大小為頁，頁面大小為128個(gè)整數(shù)；矩陣個(gè)整數(shù)；矩

43、陣A128X128在邏輯地址空間中按行在邏輯地址空間中按行存放。存放。程序編制方法程序編制方法1： For j:=1 to 128 For i:=1 to 128 Ai,j:=0;程序編制方法程序編制方法2： For i:=1 to 128 For j:=1 to 128 Ai,j:=0;那么該進(jìn)程在兩種編程方法下的缺頁次數(shù)分別為：那么該進(jìn)程在兩種編程方法下的缺頁次數(shù)分別為：128*128+1和和128+1。6、影響缺頁率的主要要素、影響缺頁率的主要要素3.4 3.4 段式存儲管理段式存儲管理需用需用“緊湊才干消除碎片的一種緊湊才干消除碎片的一種離散分配技術(shù)，但便于代碼共享與增離散分配技術(shù)，但

44、便于代碼共享與增長長段式存儲管理：結(jié)合可變分區(qū)和離散存儲思想段式存儲管理：結(jié)合可變分區(qū)和離散存儲思想程序分段：代碼段、數(shù)據(jù)段、堆棧段等；程序分段：代碼段、數(shù)據(jù)段、堆棧段等；按可變分區(qū)方法為各段動態(tài)分區(qū)；按可變分區(qū)方法為各段動態(tài)分區(qū)；各段在內(nèi)存中可以不延續(xù)；各段在內(nèi)存中可以不延續(xù)；根據(jù)程序運(yùn)轉(zhuǎn)時(shí)，能否需求全部調(diào)入內(nèi)存，分為：根據(jù)程序運(yùn)轉(zhuǎn)時(shí)，能否需求全部調(diào)入內(nèi)存，分為：實(shí)分段式存儲管理根本分段實(shí)分段式存儲管理根本分段虛擬段式存儲管理懇求分段虛擬段式存儲管理懇求分段3.4.1 實(shí)分段式存儲管理實(shí)分段式存儲管理1. 根本思想根本思想進(jìn)程地址空間劃分進(jìn)程地址空間劃分 按程序本身的邏輯關(guān)系劃分為假設(shè)干個(gè)程

45、按程序本身的邏輯關(guān)系劃分為假設(shè)干個(gè)程序段，每個(gè)程序段都有一個(gè)段名，且有一序段，每個(gè)程序段都有一個(gè)段名，且有一個(gè)段號。段號從個(gè)段號。段號從0開場，每一段也從開場，每一段也從0開場開場編址，段內(nèi)地址是延續(xù)的。編址，段內(nèi)地址是延續(xù)的。(分段是由用戶分段是由用戶或編譯器擔(dān)任或編譯器擔(dān)任邏輯地址留意：分段地址空間是真正二維邏輯地址留意：分段地址空間是真正二維的的段號段號 段內(nèi)地址段內(nèi)地址0116N.0S任務(wù)區(qū)段任務(wù)區(qū)段B主程序段主程序段M.0EP子程序段子程序段X0K.CALL X E.CALL Y FCALL A 116.0FL子程序段子程序段Y數(shù)組數(shù)組A12345.進(jìn)程地址空間分段表示圖：進(jìn)程地址空

46、間分段表示圖：1. 根本思想續(xù)根本思想續(xù)n內(nèi)存空間劃分內(nèi)存空間劃分n 內(nèi)存空間以段為單位被動態(tài)地劃分為假設(shè)干個(gè)長內(nèi)存空間以段為單位被動態(tài)地劃分為假設(shè)干個(gè)長度不一樣的區(qū)域，稱為物理段，每個(gè)物理段由起始度不一樣的區(qū)域，稱為物理段，每個(gè)物理段由起始地址和長度確定，相當(dāng)于可變分區(qū)管理中的一個(gè)分地址和長度確定，相當(dāng)于可變分區(qū)管理中的一個(gè)分區(qū)。區(qū)。n內(nèi)存分配內(nèi)存分配n 以段為單位分配內(nèi)存，每一個(gè)段在內(nèi)存中占據(jù)一以段為單位分配內(nèi)存，每一個(gè)段在內(nèi)存中占據(jù)一個(gè)延續(xù)區(qū)域，但同一進(jìn)程的各段對應(yīng)的物理段可以個(gè)延續(xù)區(qū)域，但同一進(jìn)程的各段對應(yīng)的物理段可以不延續(xù)。不延續(xù)。n進(jìn)程運(yùn)轉(zhuǎn)時(shí)，其各段必需全部裝入內(nèi)存進(jìn)程運(yùn)轉(zhuǎn)時(shí)，其各

47、段必需全部裝入內(nèi)存2. 地址映射及轉(zhuǎn)換地址映射及轉(zhuǎn)換n段表段表n 記錄了進(jìn)程的每個(gè)邏輯段及其物理段的對應(yīng)關(guān)系。記錄了進(jìn)程的每個(gè)邏輯段及其物理段的對應(yīng)關(guān)系。n 每個(gè)進(jìn)程設(shè)置一個(gè)段表，放在內(nèi)存，屬于其現(xiàn)場每個(gè)進(jìn)程設(shè)置一個(gè)段表，放在內(nèi)存，屬于其現(xiàn)場信息。信息。段號段號012物理段首址物理段首址段長度段長度58K20K100K110K260K140K段表表示圖：段表表示圖：B0SA0NY0LX0PM0K邏輯段號邏輯段號01234進(jìn)程進(jìn)程1的地址空間的地址空間10003200500060008000PKSLN內(nèi)存內(nèi)存K 3200P 1500L 6000N 8000S 5000段長段長 段始址段始址012

48、34操作系統(tǒng)操作系統(tǒng).段表段表 Cl Cb+段號段號S S 段內(nèi)地址段內(nèi)地址d d比較比較b + d段表段表S= Cl快表快表物理地址物理地址段表始址存放器段表始址存放器段表長度存放器段表長度存放器邏輯地址邏輯地址lb.Slb地址越界地址越界d=1分段地址映射及存儲維護(hù)機(jī)制分段地址映射及存儲維護(hù)機(jī)制地址越界地址越界比較比較+3、段的共享與維護(hù)、段的共享與維護(hù)u段的共享段的共享u多個(gè)進(jìn)程的某個(gè)段對應(yīng)同一個(gè)物理段；多個(gè)進(jìn)程的某個(gè)段對應(yīng)同一個(gè)物理段；u段的信息具有完好的邏輯意義，比頁的共享更容段的信息具有完好的邏輯意義，比頁的共享更容易些易些u段的維護(hù)段的維護(hù)u段表長度存放器以及段表表目中的段長比較

49、；段表長度存放器以及段表表目中的段長比較；u存取控制檢查：段表中設(shè)置有存取控制字段，普存取控制檢查：段表中設(shè)置有存取控制字段，普通是通是“只讀、只讀、“可寫以及可寫以及“執(zhí)行三種權(quán)限執(zhí)行三種權(quán)限的組合。的組合。4、分段與分頁的區(qū)別、分段與分頁的區(qū)別u頁是信息的物理單位，頁的內(nèi)容通常無完好意義；段是信息的邏輯單位，段的內(nèi)容具有完好邏輯意義；u分頁是靜態(tài)的，分段是動態(tài)的；u頁的大小固定，段的大小取決于用戶所寫的程序；u分頁主要是為了節(jié)省內(nèi)存，分段主要為了滿足用戶需求；u分頁進(jìn)程地址空間是一維線性延續(xù)的，分段進(jìn)程地址空間是二維的；u分頁是對用戶透明的，而分段是用戶可見的。1. 根本原理根本原理實(shí)分段

50、與虛擬存儲技術(shù)的結(jié)合。程序運(yùn)轉(zhuǎn)前，不用實(shí)分段與虛擬存儲技術(shù)的結(jié)合。程序運(yùn)轉(zhuǎn)前，不用調(diào)入一切分段，當(dāng)所訪問的段不在內(nèi)存中，那么調(diào)入一切分段，當(dāng)所訪問的段不在內(nèi)存中，那么將其動態(tài)調(diào)入。將其動態(tài)調(diào)入。相比于實(shí)分段，虛擬段式的頁表進(jìn)展了一些擴(kuò)展相比于實(shí)分段，虛擬段式的頁表進(jìn)展了一些擴(kuò)展:3.4.2 虛擬段式存儲管理虛擬段式存儲管理段長、段基址、存取控制同實(shí)分段頁表項(xiàng)；段長、段基址、存取控制同實(shí)分段頁表項(xiàng)；增長位：能否允許段動態(tài)增長增長位：能否允許段動態(tài)增長其他信息同虛擬頁式存儲管理的頁表項(xiàng)其他信息同虛擬頁式存儲管理的頁表項(xiàng)段段名名段段長長形狀位形狀位P訪問位訪問位A修正位修正位W外存地址外存地址存取存

51、取控制控制段基段基址址增長增長位位2 缺段中斷與越界中斷缺段中斷與越界中斷u缺段中斷缺段中斷u當(dāng)所需求的段不在內(nèi)存中時(shí)，產(chǎn)生當(dāng)所需求的段不在內(nèi)存中時(shí)，產(chǎn)生“缺段中斷，缺段中斷，調(diào)用缺段中斷效力程序進(jìn)展調(diào)段：調(diào)用缺段中斷效力程序進(jìn)展調(diào)段：u如假設(shè)內(nèi)存中有足有的延續(xù)空閑空間，那么裝入如假設(shè)內(nèi)存中有足有的延續(xù)空閑空間，那么裝入該段該段u如沒有，那么檢查空閑區(qū)總和能否滿足要求，如如沒有，那么檢查空閑區(qū)總和能否滿足要求，如滿足，那么應(yīng)采用滿足，那么應(yīng)采用“緊縮技術(shù)，否那么，需求緊縮技術(shù)，否那么，需求淘汰一些段。淘汰一些段。u越界中斷越界中斷u進(jìn)程在執(zhí)行過程中，有時(shí)需求擴(kuò)展分段，如數(shù)據(jù)進(jìn)程在執(zhí)行過程中，有

52、時(shí)需求擴(kuò)展分段，如數(shù)據(jù)段。由于要訪問的地址超出原有的段長，產(chǎn)生段。由于要訪問的地址超出原有的段長，產(chǎn)生“越界中斷。越界中斷。u操作系統(tǒng)處置中斷時(shí)操作系統(tǒng)處置中斷時(shí) ，首先判別該段的，首先判別該段的“增長增長位，如可擴(kuò)展，那么添加段的長度；否那么按位，如可擴(kuò)展，那么添加段的長度；否那么按出錯(cuò)處置。出錯(cuò)處置。大型程序包含：假設(shè)干程序段，假設(shè)干數(shù)據(jù)大型程序包含：假設(shè)干程序段，假設(shè)干數(shù)據(jù)段，這些段沒有必要同時(shí)調(diào)入內(nèi)存。段，這些段沒有必要同時(shí)調(diào)入內(nèi)存。 進(jìn)程的某些程序段在進(jìn)程運(yùn)轉(zhuǎn)期間能夠根本進(jìn)程的某些程序段在進(jìn)程運(yùn)轉(zhuǎn)期間能夠根本不用，如某些錯(cuò)誤處置分支；不用，如某些錯(cuò)誤處置分支； 互斥執(zhí)行的程序段沒有必要同時(shí)駐留內(nèi)存；互斥執(zhí)行的程序段沒有必要同時(shí)駐留內(nèi)存； 有些程序段執(zhí)行一次后不再用到。有些程序段執(zhí)行一次后不再用到。3. 段的動態(tài)鏈接段的動態(tài)鏈接n靜態(tài)鏈接：在程序運(yùn)轉(zhuǎn)之前，由鏈接裝配程序把它靜態(tài)鏈接：在程序運(yùn)轉(zhuǎn)之前，由