第三章存儲器管理操作系統(tǒng)課件

1、第第3 3章章 存儲器管理存儲器管理CPU內(nèi)存I/O系統(tǒng)設備內(nèi)存是現(xiàn)代計算機系統(tǒng)的中心，內(nèi)存是現(xiàn)代計算機系統(tǒng)的中心，是是CPU能直接存取指令能直接存取指令和數(shù)據(jù)的存儲器，如上圖所示，和數(shù)據(jù)的存儲器，如上圖所示，CPU和和I/O 都需要和內(nèi)都需要和內(nèi)存打交道。存打交道。CPU根據(jù)程序計數(shù)器根據(jù)程序計數(shù)器PC的值從內(nèi)存中提取指令，這些的值從內(nèi)存中提取指令，這些指令可能會引起進一步的對特定內(nèi)存地址的讀取和寫入。指令可能會引起進一步的對特定內(nèi)存地址的讀取和寫入。例如，例如，一個典型的指令執(zhí)行周期是：一個典型的指令執(zhí)行周期是：首先從內(nèi)存中讀取首先從內(nèi)存中讀取指令，接著該指令被解碼，且可能需要從內(nèi)存中讀取

2、操指令，接著該指令被解碼，且可能需要從內(nèi)存中讀取操作數(shù)，在指令對操作數(shù)執(zhí)行后，其執(zhí)行結果又被寫回到作數(shù)，在指令對操作數(shù)執(zhí)行后，其執(zhí)行結果又被寫回到內(nèi)存中。內(nèi)存中。內(nèi)存在計算機系統(tǒng)中的地位內(nèi)存在計算機系統(tǒng)中的地位：（補充）（補充）第第3 3章章 存儲器管理存儲器管理n程序和數(shù)據(jù)可以長期保存在容量最大的外存程序和數(shù)據(jù)可以長期保存在容量最大的外存中，但是，他們只有中，但是，他們只有。為了改善。為了改善 CPU的利用率和提供程序的利用率和提供程序的響應速度，計算機必須在內(nèi)存中保留多個進的響應速度，計算機必須在內(nèi)存中保留多個進程，程，也也是本章介紹的主要內(nèi)容。是本章介紹的主要內(nèi)容。第第3 3章章 存儲器

3、管理存儲器管理n3.1 存儲存儲管理概述管理概述（次重點）（次重點）n3.2 分區(qū)存儲管理分區(qū)存儲管理（次重點）（次重點）n3.3 頁式存儲管理頁式存儲管理（重點）（重點）n3.4 段式存儲管理段式存儲管理（非重點）（非重點）n3.5 段頁式存儲管理段頁式存儲管理（自學）（自學）3.1 3.1 存儲管理概念存儲管理概念1. 存儲體系存儲體系（補充）（補充）三級存儲器三級存儲器內(nèi)存內(nèi)存( (主存主存) )：RAM、ROM外存外存( (輔存輔存) )：磁盤磁盤、磁帶、光盤等、磁帶、光盤等高速緩沖存儲器高速緩沖存儲器(cache) OS負責協(xié)調各存儲器的使用，負責協(xié)調各存儲器的使用，OS本身的程序和

4、數(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ū)用戶區(qū)用戶區(qū)，為多道程序并發(fā)執(zhí)行提供存儲基礎，為多道程序并發(fā)執(zhí)行提供存儲基礎 n能夠解決能夠解決的問題的問題n保證保證n實現(xiàn)存儲保護與安全實現(xiàn)存儲保護與安全n實現(xiàn)共享與通信實現(xiàn)共享與通信n了解有關資源的使用狀況了解有關資源的使用狀況3.1 3.1 存儲管理概念存儲管理概念實際存儲單元在內(nèi)存實際存儲單元在內(nèi)存中的物理位置中的物理位置 內(nèi)存中實際的物理地址的集合內(nèi)存中實際的

5、物理地址的集合（范圍）。（范圍）。用戶程序中使用的地用戶程序中使用的地址（一般從址（一般從“0”開始的）開始的）用戶程序中所使用的邏輯地址用戶程序中所使用的邏輯地址的集合（范圍）。的集合（范圍）。 3.1 存儲管理的概念存儲管理的概念3.1 存儲管理的概念存儲管理的概念n動態(tài)重定位：動態(tài)重定位： OS將程序裝入內(nèi)存以后，將程序裝入內(nèi)存以后，把目標程序中的邏輯地址轉換為物理地址，把目標程序中的邏輯地址轉換為物理地址，n優(yōu)點：優(yōu)點： 可以將程序分配到不連續(xù)的存儲區(qū)域中可以將程序分配到不連續(xù)的存儲區(qū)域中 有利于實現(xiàn)程序段的共享有利于實現(xiàn)程序段的共享缺點：缺點： 需要附加的硬件支持需要附加的硬件支持（

6、重定位寄存器存放（重定位寄存器存放程序程序/數(shù)據(jù)數(shù)據(jù)在內(nèi)在內(nèi)存中起始地址）存中起始地址） 相應的軟件算法也比較復雜相應的軟件算法也比較復雜操作數(shù)和指令地址并操作數(shù)和指令地址并不在程序裝入時確定不在程序裝入時確定多用戶程序只需知道被共享程序的邏輯地址多用戶程序只需知道被共享程序的邏輯地址3.1 存儲管理的概念存儲管理的概念 區(qū)號區(qū)號起始地址起始地址長度長度(KB)狀態(tài)狀態(tài)1aS1空閑空閑2bS2已分配已分配3cS3空閑空閑固定分區(qū)內(nèi)存分配表固定分區(qū)內(nèi)存分配表指為了保證指為了保證CPU執(zhí)行指令時可正確訪問存執(zhí)行指令時可正確訪問存儲單元，需將用戶程序中的儲單元，需將用戶程序中的邏輯地址邏輯地址（相對

7、地（相對地址，虛地址）轉換為運行時由機器直接尋址的址，虛地址）轉換為運行時由機器直接尋址的物理地址物理地址（絕對地址，實地址）的過程（絕對地址，實地址）的過程。 內(nèi)存保護限定程序只能訪問自己所在的內(nèi)存區(qū)，內(nèi)存保護限定程序只能訪問自己所在的內(nèi)存區(qū)，保保護了護了OS和其他程序。一般來說，對內(nèi)存區(qū)域的保護和其他程序。一般來說，對內(nèi)存區(qū)域的保護可采取如下措施：可采取如下措施：n定義：定義：當用戶運行比內(nèi)存大的程序時采取軟件的當用戶運行比內(nèi)存大的程序時采取軟件的方法來對內(nèi)存進行邏輯擴充，達到方法來對內(nèi)存進行邏輯擴充，達到常用常用覆蓋覆蓋、交換交換和和虛擬存儲虛擬存儲技術。技術。在硬件的配合下，將部分外存

8、空間虛在硬件的配合下，將部分外存空間虛擬為內(nèi)存空間，并將內(nèi)存和外存有機結合起來，擬為內(nèi)存空間，并將內(nèi)存和外存有機結合起來，得到一個得到一個、價、價格十分便宜的虛擬存儲系統(tǒng)。格十分便宜的虛擬存儲系統(tǒng)。n貢獻：貢獻：內(nèi)存擴充技術打破了進程必須內(nèi)存擴充技術打破了進程必須內(nèi)內(nèi)存才能運行的慣例。存才能運行的慣例。（從邏輯上擴充內(nèi)存容量）（從邏輯上擴充內(nèi)存容量）具有具有功能，能功能，能的一種存儲器系統(tǒng)。其邏輯容量由的一種存儲器系統(tǒng)。其邏輯容量由所決定，運行速度接近內(nèi)存，每位成本接近外存。所決定，運行速度接近內(nèi)存，每位成本接近外存。進程開始運行時只需要進程開始運行時只需要裝入內(nèi)存即可，當要訪問裝入內(nèi)存即可，

9、當要訪問自己地址空間中的內(nèi)容不在內(nèi)存時，將產(chǎn)生自己地址空間中的內(nèi)容不在內(nèi)存時，將產(chǎn)生，由服務程，由服務程序把所缺的內(nèi)容序把所缺的內(nèi)容，若此時內(nèi)存沒有空間，則用，若此時內(nèi)存沒有空間，則用，如果這部分信息，如果這部分信息來自該進程所在的內(nèi)存區(qū)，則換入時相當于使用了自動覆蓋來自該進程所在的內(nèi)存區(qū)，則換入時相當于使用了自動覆蓋技術。技術。虛擬存儲虛擬存儲存儲管理策略分類存儲管理策略分類n存儲管理策略存儲管理策略：n實存模式實存模式要求進程運行時要求進程運行時全部在全部在內(nèi)存內(nèi)存n虛存模式虛存模式只要求進程運行時只要求進程運行時部分在部分在內(nèi)存即可內(nèi)存即可存儲管理分類存儲管理分類按照對內(nèi)存的劃分使用策略

10、不同來分類，按照對內(nèi)存的劃分使用策略不同來分類，可分為：可分為：3.2 3.2 分區(qū)式存儲管理分區(qū)式存儲管理 實存實存管理技術（管理技術（進程運行全部裝入內(nèi)存進程運行全部裝入內(nèi)存） 系統(tǒng)給每個作業(yè)或進程分配一個系統(tǒng)給每個作業(yè)或進程分配一個。n單一連續(xù)區(qū)分配（靜態(tài)分區(qū)技術）單一連續(xù)區(qū)分配（靜態(tài)分區(qū)技術）n可變分區(qū)分配（動態(tài)分區(qū)技術）可變分區(qū)分配（動態(tài)分區(qū)技術）1. 單一連續(xù)區(qū)存儲管理單一連續(xù)區(qū)存儲管理 系統(tǒng)靜態(tài)地將系統(tǒng)靜態(tài)地將，一個供操作系統(tǒng)使用，一個供操作系統(tǒng)使用，一個供用戶使用，且每次只能裝入一個作業(yè)或進程，主要一個供用戶使用，且每次只能裝入一個作業(yè)或進程，主要用于早期單道程序系統(tǒng)和后來的用

11、于早期單道程序系統(tǒng)和后來的PC操作系統(tǒng)。操作系統(tǒng)。操作系統(tǒng)操作系統(tǒng)用戶程序用戶程序0 xFFF.0系統(tǒng)預先把可分配的內(nèi)存空間分割成若干個連續(xù)區(qū)系統(tǒng)預先把可分配的內(nèi)存空間分割成若干個連續(xù)區(qū)域，域，每一區(qū)域稱為分區(qū)，每個分區(qū)的大小可以相同也每一區(qū)域稱為分區(qū)，每個分區(qū)的大小可以相同也可以不同，可以不同，一旦劃分好分區(qū)之后一旦劃分好分區(qū)之后，這種分區(qū)法屬于一種這種分區(qū)法屬于一種靜態(tài)分區(qū)靜態(tài)分區(qū)。 或進程。等待進入或進程。等待進入內(nèi)存的作業(yè)排成一個作業(yè)隊列，當內(nèi)存中有空閑的分內(nèi)存的作業(yè)排成一個作業(yè)隊列，當內(nèi)存中有空閑的分區(qū)時，依次從作業(yè)隊列中選擇一個能裝入該分區(qū)的作區(qū)時，依次從作業(yè)隊列中選擇一個能裝入該

12、分區(qū)的作業(yè)。當所有的分區(qū)都已裝有作業(yè)，則其他的作業(yè)暫時業(yè)。當所有的分區(qū)都已裝有作業(yè)，則其他的作業(yè)暫時不能再裝入。不能再裝入。已經(jīng)裝入內(nèi)存的作業(yè)在獲得處理機運行時，已經(jīng)裝入內(nèi)存的作業(yè)在獲得處理機運行時，要要3.2.1 3.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用區(qū)號區(qū)號起始地址起始地址長度長度(KB)狀態(tài)狀態(tài)1aS102bS2job23cS30設置一張設置一張“內(nèi)存分配表內(nèi)存分配表”來管理內(nèi)存空間的使用。來管理內(nèi)存空間的使用。OS0abcd空空 job2空空 內(nèi)存分配表內(nèi)存分配表內(nèi)存內(nèi)存3.2.1 3.2.1 固定分區(qū)存儲

13、管理固定分區(qū)存儲管理 單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用：3.2.1 3.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用重新置成重新置成0。3.2.1 3.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用固定分區(qū)管理，分區(qū)固定且只能裝入一個作業(yè)固定分區(qū)管理，分區(qū)固定且只能裝入一個作業(yè)，作業(yè)在執(zhí)行過程中不會改變存放區(qū)域。，作業(yè)在執(zhí)行過程中不會改變存放區(qū)域。u存儲保護采用存儲保護采用“”方法方法當某作業(yè)占用處理機時，進程調度程序

14、必須把當某作業(yè)占用處理機時，進程調度程序必須把該作業(yè)所在分區(qū)下限地址該作業(yè)所在分區(qū)下限地址（最小地址）（最小地址）和上限和上限地址地址（最大地址）（最大地址）存入處理機的下限寄存器和存入處理機的下限寄存器和上限寄存器，當上限寄存器，當下限地址下限地址物理地址物理地址上限地址上限地址時訪問物理主存，時訪問物理主存，否則形成否則形成3.2.1 3.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用3.2.1 3.2.1 固定分區(qū)存儲管理固定分區(qū)存儲管理 單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應用v內(nèi)存空間

15、的利用率：內(nèi)存空間的利用率：“內(nèi)碎內(nèi)碎片片”。特點：實現(xiàn)簡單，可用于多道程序系統(tǒng)，但內(nèi)特點：實現(xiàn)簡單，可用于多道程序系統(tǒng)，但內(nèi)存利用率低，作業(yè)大小受限。存利用率低，作業(yè)大小受限。v基本思想基本思想3.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理n當某作業(yè)執(zhí)行結束后，它所占的分區(qū)必須被當某作業(yè)執(zhí)行結束后，它所占的分區(qū)必須被3.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理3.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理v內(nèi)存空間的分配內(nèi)存空間的分配內(nèi)存分配表用內(nèi)存分配表用組成，組成，“”和和“”。查空閑分區(qū)表，按照查空閑分區(qū)表，按照進行分配后，對空閑分區(qū)表進行修改?？臻e分區(qū)表僅當被進行分配后，對空閑分區(qū)表進行

16、修改?？臻e分區(qū)表僅當被選中分區(qū)的尺寸與作業(yè)需求相等時才將相應表目狀態(tài)置成選中分區(qū)的尺寸與作業(yè)需求相等時才將相應表目狀態(tài)置成“空空”，根據(jù)空閑分區(qū)表把已分配分區(qū)表根據(jù)空閑分區(qū)表把已分配分區(qū)表中的一個空表目改為一個標志為某作業(yè)名的相應表目，并中的一個空表目改為一個標志為某作業(yè)名的相應表目，并調整起始地址和長度。（調整起始地址和長度。（3.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理區(qū)號區(qū)號起始地址起始地址長度長度(KB)標志位標志位1aS1空空2bS2job23cS3空空OS0abcd空空 job2空空 已分配分區(qū)表已分配分區(qū)表內(nèi)存內(nèi)存區(qū)號區(qū)號起始地址起始地址長度長度(KB)標志位標志位1aS1未分配

17、未分配2bS2空空3cS3未分配未分配空閑分區(qū)表空閑分區(qū)表3.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理3.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理 空閑分區(qū)表的表目按相應分區(qū)的空閑分區(qū)表的表目按相應分區(qū)的以以，分配時，順序查找空閑分區(qū)表，找到第一個能滿足作，分配時，順序查找空閑分區(qū)表，找到第一個能滿足作業(yè)要求的空閑分區(qū)，若該空閑分區(qū)比作業(yè)長度大，則分割業(yè)要求的空閑分區(qū)，若該空閑分區(qū)比作業(yè)長度大，則分割這個空閑分區(qū)，一部分分配給作業(yè)，另一部分仍為空閑分這個空閑分區(qū)，一部分分配給作業(yè)，另一部分仍為空閑分區(qū)；若該空閑分區(qū)長度與作業(yè)大小相等，則直接把它分給區(qū)；若該空閑分區(qū)長度與作業(yè)大小相等，則直接把它

18、分給作業(yè)。作業(yè)。（因為每一次都從低地址搜索）（因為每一次都從低地址搜索）3.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理空閑分區(qū)表的表目按相應空閑分區(qū)表的表目按相應分區(qū)的大小分區(qū)的大小。找到的第一個能滿足作業(yè)要求的空閑分區(qū)一定是個最找到的第一個能滿足作業(yè)要求的空閑分區(qū)一定是個最小的空閑分區(qū)，即其長度最接近或最適合作業(yè)要求的小的空閑分區(qū)，即其長度最接近或最適合作業(yè)要求的空閑分區(qū)，這樣可保證不去分割一個更大的區(qū)域，以空閑分區(qū)，這樣可保證不去分割一個更大的區(qū)域，以利于以后到來的大作業(yè)。利于以后到來的大作業(yè)。3.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理空閑分區(qū)表的表目按相應分區(qū)的空閑分區(qū)表的表目按相應分區(qū)

19、的。找到的第一個能滿足作業(yè)要求的空閑分區(qū)一定是。找到的第一個能滿足作業(yè)要求的空閑分區(qū)一定是個個，即其長度與作業(yè)要求，即其長度與作業(yè)要求，這樣可保證每次分割后的剩余部分不至于太小，仍可這樣可保證每次分割后的剩余部分不至于太小，仍可被分配使用，被分配使用，例例3.1 分區(qū)存儲管理算法題分區(qū)存儲管理算法題n采用可變分區(qū)方式管理內(nèi)存時，若內(nèi)存中按采用可變分區(qū)方式管理內(nèi)存時，若內(nèi)存中按依次有五個大小依次為依次有五個大小依次為15k、37k、14k、220k和和103k的的?，F(xiàn)有五個作業(yè)?，F(xiàn)有五個作業(yè)Ja、Jb、Jc、Jd和和Je，它它們各需要內(nèi)存?zhèn)兏餍枰獌?nèi)存12k、14k、103k、36k和和190k。

20、問：。問：如果采用最先適應分配算法，能將這五個作業(yè)按如果采用最先適應分配算法，能將這五個作業(yè)按Ja Je的次序全部裝入內(nèi)存嗎？用什么分配算法裝入的次序全部裝入內(nèi)存嗎？用什么分配算法裝入這這5個作業(yè)可使內(nèi)存的利用率最高？個作業(yè)可使內(nèi)存的利用率最高？解答：解答： 按最先適應分配算法，不能將這五個作業(yè)按按最先適應分配算法，不能將這五個作業(yè)按Ja Je的次序全部裝入內(nèi)存。因為內(nèi)存中前兩個原先的空閑分區(qū)能的次序全部裝入內(nèi)存。因為內(nèi)存中前兩個原先的空閑分區(qū)能依次裝入依次裝入Ja(15k)和和Jb(37k)，Jc(220K)之后，第四個分區(qū)還剩之后，第四個分區(qū)還剩117K , Jd (117K)之后，第四個

21、分區(qū)還剩之后，第四個分區(qū)還剩81K, Je190K的任務的任務已經(jīng)沒有分區(qū)能夠滿足了。已經(jīng)沒有分區(qū)能夠滿足了。 用最佳適應分配算法裝入這用最佳適應分配算法裝入這5個作業(yè)，可使內(nèi)存的利個作業(yè)，可使內(nèi)存的利用率最高。此時，原先的用率最高。此時，原先的5個空閑區(qū)依次裝入了個空閑區(qū)依次裝入了5個作業(yè)，它個作業(yè)，它們是：們是：Jb(15k)，Jd(37k)，Ja(14k)，Je(220k)和和Jc(103k)。15k37k14k220k103k3.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理v內(nèi)存空間的釋放內(nèi)存空間的釋放釋放后釋放后將相應表目的狀態(tài)置成將相應表目的狀態(tài)置成“空空”；3.2.2 可變分區(qū)存儲管

22、理可變分區(qū)存儲管理n特點特點克服了固定分區(qū)管理的克服了固定分區(qū)管理的“內(nèi)碎片內(nèi)碎片”問題，但問題，但產(chǎn)生了產(chǎn)生了“外碎片外碎片”。怎樣解決怎樣解決碎片問題碎片問題呢？呢？改進內(nèi)存釋放算法改進內(nèi)存釋放算法在內(nèi)存中移動程序在內(nèi)存中移動程序3.2.2 可變分區(qū)存儲管理可變分區(qū)存儲管理移動技術和內(nèi)存緊縮移動技術和內(nèi)存緊縮移動技術和內(nèi)存緊縮移動技術和內(nèi)存緊縮采用采用裝入程序裝入程序基址基址-限長寄存器限長寄存器地址轉換與存儲保護地址轉換與存儲保護作業(yè)執(zhí)行過程中，處理機每執(zhí)行一條指令都要取出該指作業(yè)執(zhí)行過程中，處理機每執(zhí)行一條指令都要取出該指令的邏輯地址；當令的邏輯地址；當小于小于限長寄存器的值時，則把限

23、長寄存器的值時，則把邏輯地址與邏輯地址與的值相加得到的值相加得到。當當限長寄存器的值時，表示欲訪問限長寄存器的值時，表示欲訪問的主存地址超出了所分配的分區(qū)范圍，形成的主存地址超出了所分配的分區(qū)范圍，形成“地址越界地址越界”地址轉換與存儲保護地址轉換與存儲保護3.2 分區(qū)存儲管理分區(qū)存儲管理限長基址寄存器保護法限長基址寄存器保護法3.2 分區(qū)存儲管理分區(qū)存儲管理n主要在于連續(xù)分配的限制，即它要求每主要在于連續(xù)分配的限制，即它要求每個作業(yè)在內(nèi)存必須占用一個連續(xù)的區(qū)域。個作業(yè)在內(nèi)存必須占用一個連續(xù)的區(qū)域。3.3 3.3 頁式存儲管理頁式存儲管理 不用不用“緊湊緊湊”也能消除碎片的一種也能消除碎片的一

24、種技術技術由于要求每個作業(yè)在內(nèi)存必須占用由于要求每個作業(yè)在內(nèi)存必須占用一個連續(xù)的區(qū)域，因此最大缺點是一個連續(xù)的區(qū)域，因此最大缺點是結合固定分區(qū)和離散存儲的思想產(chǎn)生的結合固定分區(qū)和離散存儲的思想產(chǎn)生的允許一個進程在內(nèi)存中占有允許一個進程在內(nèi)存中占有因此因此基本解決了碎片問題基本解決了碎片問題，是目前內(nèi)存，是目前內(nèi)存利用率最高的一種存儲管理方式。分為：利用率最高的一種存儲管理方式。分為：3.3 頁式存儲管理頁式存儲管理n基本原理基本原理將將分成大小相分成大小相同的若干個存儲塊，從同的若干個存儲塊，從“0”開始編號開始編號將一個進程的將一個進程的分分成與物理塊成與物理塊的片，從的片，從“0”開始編號

25、開始編號n以頁為單位分配內(nèi)存，一頁分配一個塊，每以頁為單位分配內(nèi)存，一頁分配一個塊，每頁可以不連續(xù)頁可以不連續(xù)地址結構地址結構 頁號（頁號（P）：）：指明該地址在指明該地址在的哪的哪一頁一頁 頁內(nèi)偏移量（頁內(nèi)偏移量（D）：）：表明該地址在該頁內(nèi)的相對表明該地址在該頁內(nèi)的相對地址。地址。 頁號和頁內(nèi)偏移量的計算頁號和頁內(nèi)偏移量的計算 頁號：頁號：P=INTA/L 頁內(nèi)偏移量：頁內(nèi)偏移量：D=A MOD L A：邏輯地址：邏輯地址 L：頁面大小：頁面大小3.3.1 實頁式存儲管理實頁式存儲管理n舉例舉例n設頁面大小為設頁面大小為L=1 kB，邏輯地址，邏輯地址A=2170B，計，計算邏輯地址對應的

26、頁號和頁內(nèi)偏移量算邏輯地址對應的頁號和頁內(nèi)偏移量 n頁表頁表n系統(tǒng)為每一個進程建立一張系統(tǒng)為每一個進程建立一張 頁表，存放在內(nèi)存。頁表，存放在內(nèi)存。n每一個頁表項記錄了相應頁每一個頁表項記錄了相應頁 在內(nèi)存中對應的物理塊號在內(nèi)存中對應的物理塊號3.3.1 實頁式存儲管理實頁式存儲管理3.3.1 實頁式存儲管理實頁式存儲管理n舉例：舉例：n一邏輯地址為一邏輯地址為3120，頁面大小，頁面大小L1kB，頁，頁表如右圖所示，求其對應的表如右圖所示，求其對應的 物理地址物理地址=7*1024+48 =7216 邏輯地址邏輯地址1000對應的物理地址對應的物理地址 邏輯地址邏輯地址5670對應的物理地址

27、對應的物理地址頁號塊號011425374103.3.1 實頁式存儲管理實頁式存儲管理地址轉換地址轉換3.3.1 實頁式存儲管理實頁式存儲管理n具有快表的具有快表的地址變換地址變換n聯(lián)想寄存器（快表）的引入聯(lián)想寄存器（快表）的引入n地址變換過程地址變換過程 地址變換機構同時查找快表和頁表，如果在快表地址變換機構同時查找快表和頁表，如果在快表中有與之相匹配的頁號，可中有與之相匹配的頁號，可 如果在快表中沒有找到與之對應的頁表項，繼續(xù)如果在快表中沒有找到與之對應的頁表項，繼續(xù)訪問主存中的頁表，從頁表中讀出與頁號對應的訪問主存中的頁表，從頁表中讀出與頁號對應的物理塊號，同時將此頁表項存入快表中的寄存器

28、物理塊號，同時將此頁表項存入快表中的寄存器單元中單元中 如果快表已滿，則操作系統(tǒng)必須找到一個認為不如果快表已滿，則操作系統(tǒng)必須找到一個認為不再需要的頁表項將之移出再需要的頁表項將之移出 3.3.1 實頁式存儲管理實頁式存儲管理3.3.1 實頁式存儲管理實頁式存儲管理n頁的分配與回收頁的分配與回收3.3.1 實頁式存儲管理實頁式存儲管理0310/10/10/10/10/1017空閑塊數(shù)空閑塊數(shù)位示圖位示圖主存儲器可分配區(qū)域被分成主存儲器可分配區(qū)域被分成256塊，則需要一個塊，則需要一個33個字節(jié)的位示圖來作為個字節(jié)的位示圖來作為主存分配表。其中主存分配表。其中8個字長為個字長為32位的字來描述全

29、部位的字來描述全部256個塊的分配使用情況，個塊的分配使用情況，另有一個字節(jié)記錄當前剩余的空閑塊數(shù)。如下圖：另有一個字節(jié)記錄當前剩余的空閑塊數(shù)。如下圖：3.3.1 實頁式存儲管理實頁式存儲管理0310/10/10/10/10/1017空閑塊數(shù)空閑塊數(shù)需進行需進行的轉換：的轉換：=字號字號*字長字長+位號位號(255=732+31)3.3.1 實頁式存儲管理實頁式存儲管理1 初始化時把操作系統(tǒng)已經(jīng)占用塊對應的位置成初始化時把操作系統(tǒng)已經(jīng)占用塊對應的位置成1，其余位均置成其余位均置成0，剩余空閑塊為可分配空閑塊總數(shù)。，剩余空閑塊為可分配空閑塊總數(shù)。2 使用時，先查看空閑塊數(shù)是否滿足作業(yè)要求，若不使

30、用時，先查看空閑塊數(shù)是否滿足作業(yè)要求，若不滿足不進行分配，否則找出一些值為滿足不進行分配，否則找出一些值為0的位將其置的位將其置1，從空閑塊中減去本次占用塊數(shù)，按公式轉換：從空閑塊中減去本次占用塊數(shù)，按公式轉換：3 執(zhí)行結束后，應執(zhí)行結束后，應，根據(jù)歸還的塊號，按公式：，根據(jù)歸還的塊號，按公式：字號字號=塊號塊號div字長字長（7=255/32）位號位號=塊號塊號mod字長字長(31=255%32)3.3.1 實頁式存儲管理實頁式存儲管理ed1ed2ed40data1data22122606162進程進程1頁表頁表ed1ed2ed40data1data2進程進程23132707172頁表頁表.

31、OSed1ed2ed40data1data2data1data2011125051525354主存主存3.3.1 實頁式存儲管理實頁式存儲管理n只有純的頁面只有純的頁面才能共享才能共享n一般分頁常采用一般分頁常采用技術（要求有目標技術（要求有目標模塊拷貝）因此無法實現(xiàn)共享模塊拷貝）因此無法實現(xiàn)共享n頁塊按地址空間劃分，頁內(nèi)信息不完整，頁塊按地址空間劃分，頁內(nèi)信息不完整，3.3.1 實頁式存儲管理實頁式存儲管理n越界檢查越界檢查3.3.1 實頁式存儲管理實頁式存儲管理01111141102910036101頁號頁號塊號塊號可讀可讀可寫可寫可執(zhí)行可執(zhí)行圖圖3.1 3.1 帶有存取控制字段的頁表帶有

32、存取控制字段的頁表存取控制字段存取控制字段3.3.1 實頁式存儲管理實頁式存儲管理3.3.2 3.3.2 虛擬頁式存儲管理虛擬頁式存儲管理n虛擬頁式存儲管理的引入：虛擬頁式存儲管理的引入： 當一個進程的地址空間大于整個內(nèi)存空當一個進程的地址空間大于整個內(nèi)存空間時，若采用實分頁式存儲管理，那么間時，若采用實分頁式存儲管理，那么1. 虛擬存儲器的概念虛擬存儲器的概念n虛擬存儲器是虛擬存儲器是為了為了邏輯擴充內(nèi)存，以解決邏輯擴充內(nèi)存，以解決而而引入引入的，是一種以的，是一種以（是（是OS中的資源轉換技術），也是迄今為止邏輯中的資源轉換技術），也是迄今為止邏輯擴充內(nèi)存程度最徹底的技術。擴充內(nèi)存程度最徹

33、底的技術。n虛擬存儲器是在虛擬存儲器是在1961年由英國曼徹斯特大學的年由英國曼徹斯特大學的Fotheringham提出，并在該校的提出，并在該校的atlas機器上實現(xiàn)的一種存儲技術。從機器上實現(xiàn)的一種存儲技術。從1970年后被廣泛應用，今天的年后被廣泛應用，今天的OS普遍采用這一技術管理內(nèi)存。普遍采用這一技術管理內(nèi)存。n虛擬存儲器的基本思想虛擬存儲器的基本思想是：是：OS把程序當前使用的部分保留在內(nèi)存，而把把程序當前使用的部分保留在內(nèi)存，而把其它部分保存在磁盤上，并在需要時在內(nèi)存和磁盤之間其它部分保存在磁盤上，并在需要時在內(nèi)存和磁盤之間1. 虛擬存儲器的概念（續(xù)虛擬存儲器的概念（續(xù)1）196

34、8年美國年美國MIT的的Denning提出程序局部性原理是對提出程序局部性原理是對虛擬存儲器有力的理論支持。虛擬存儲器有力的理論支持。 程序在執(zhí)行時呈現(xiàn)出高度的局部性特征，即在一較短程序在執(zhí)行時呈現(xiàn)出高度的局部性特征，即在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應地，的時間內(nèi)，程序的執(zhí)行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區(qū)域。程序執(zhí)行的它所訪問的存儲空間也局限于某個區(qū)域。程序執(zhí)行的局部性表現(xiàn)在時間與空間兩個方面：局部性表現(xiàn)在時間與空間兩個方面： 如果某個參數(shù)被引用，那它不久將再次被引用。程序如果某個參數(shù)被引用，那它不久將再次被引用。程序往往在短時間內(nèi)多次引用同一個參

35、數(shù)。往往在短時間內(nèi)多次引用同一個參數(shù)。 若某一存儲單元被訪問，則在不久之后，與該存儲單若某一存儲單元被訪問，則在不久之后，與該存儲單元相鄰的單元也可能被訪問。元相鄰的單元也可能被訪問。1. 虛擬存儲器的概念（續(xù)虛擬存儲器的概念（續(xù)1） 按照局部性原理，一個進程運行時，可不必將其按照局部性原理，一個進程運行時，可不必將其全部裝載到內(nèi)存中，只需把全部裝載到內(nèi)存中，只需把隨著進程運行的不斷隨著進程運行的不斷推進，其中部分程序和數(shù)據(jù)可隨時裝入，這樣做可實推進，其中部分程序和數(shù)據(jù)可隨時裝入，這樣做可實現(xiàn)現(xiàn)的設想。的設想。 1. 虛擬存儲器的概念（續(xù)虛擬存儲器的概念（續(xù)2）n虛擬存儲器定義虛擬存儲器定義（

36、至今沒有統(tǒng)一定義，我認為以下前（至今沒有統(tǒng)一定義，我認為以下前3種比較重要）種比較重要）n虛假的存儲器；虛假的存儲器；n進程能夠訪問的虛擬地址空間；進程能夠訪問的虛擬地址空間；n虛擬存儲器是把虛擬存儲器是把內(nèi)存與外存這兩級存儲器并用做一級存儲器內(nèi)存與外存這兩級存儲器并用做一級存儲器的結果，是邏輯擴充內(nèi)存的最佳手段的結果，是邏輯擴充內(nèi)存的最佳手段n虛擬存儲器的容量虛擬存儲器的容量取決于取決于，但實際最，但實際最大尺寸取決于系統(tǒng)的地址結構（大尺寸取決于系統(tǒng)的地址結構（）基本思想基本思想2. 兩個問題兩個問題 1）進程運行時，）進程運行時，那那么在內(nèi)存容量和進程數(shù)量確定的前提下，么在內(nèi)存容量和進程數(shù)

37、量確定的前提下，應當如何把內(nèi)存分配給諸進程呢？應當如何把內(nèi)存分配給諸進程呢？ 2）當進程訪問的頁不在內(nèi)存時將產(chǎn)生）當進程訪問的頁不在內(nèi)存時將產(chǎn)生缺頁缺頁中斷中斷，由服務程序把所缺頁裝入內(nèi)存。如，由服務程序把所缺頁裝入內(nèi)存。如何為所缺頁面分配內(nèi)存？何為所缺頁面分配內(nèi)存？2. 主存頁面分配策略主存頁面分配策略問題問題1：既然進程開始運行時只需要一部分內(nèi)存，：既然進程開始運行時只需要一部分內(nèi)存，那么在內(nèi)存容量和進程數(shù)量確定的前提下，應當那么在內(nèi)存容量和進程數(shù)量確定的前提下，應當如何把內(nèi)存物理塊分配給諸進程？如何把內(nèi)存物理塊分配給諸進程？將內(nèi)存所有塊等分給進入系統(tǒng)中將內(nèi)存所有塊等分給進入系統(tǒng)中的進程。

38、的進程。2）按進程）按進程比例分配。比例分配。3）按進程）按進程分配。分配。4）按進程）按進程分配。分配。2. 主存頁面分配策略主存頁面分配策略問題問題2：進程運行過程中訪問不在內(nèi)存的頁面發(fā)生：進程運行過程中訪問不在內(nèi)存的頁面發(fā)生缺頁中斷時，如何為所缺頁面分配內(nèi)存？缺頁中斷時，如何為所缺頁面分配內(nèi)存？進程在內(nèi)存占據(jù)進程在內(nèi)存占據(jù)，置換時總是從這一部，置換時總是從這一部分區(qū)域中找淘汰對象。分區(qū)域中找淘汰對象。開始時為進程分配一定數(shù)目的內(nèi)存塊，此后當進程訪問開始時為進程分配一定數(shù)目的內(nèi)存塊，此后當進程訪問所缺頁面時，若該進程所占內(nèi)存已經(jīng)裝滿頁面，則只能從中所缺頁面時，若該進程所占內(nèi)存已經(jīng)裝滿頁面，

39、則只能從中選擇一頁換出，然后再調入所缺的頁面，以保證分配給該進選擇一頁換出，然后再調入所缺的頁面，以保證分配給該進程的程的只能從當前進程所占的內(nèi)存空間中找淘汰對象只能從當前進程所占的內(nèi)存空間中找淘汰對象 ，因，因此一個進程缺頁此一個進程缺頁不會影響其他進程。不會影響其他進程。2. 主存頁面分配策略主存頁面分配策略 進程在內(nèi)存占據(jù)的空間進程在內(nèi)存占據(jù)的空間，一般是由系統(tǒng)定時，一般是由系統(tǒng)定時地根據(jù)進程訪問的缺頁率的高低而動態(tài)調整，置換時從地根據(jù)進程訪問的缺頁率的高低而動態(tài)調整，置換時從用戶進程所占的內(nèi)存空間中找淘汰對象用戶進程所占的內(nèi)存空間中找淘汰對象。一個進程缺頁會影響其他進程。一個進程缺頁會

40、影響其他進程。2. 主存頁面分配策略主存頁面分配策略3. 頁面調入時機頁面調入時機n請求調頁策略請求調頁策略（demand paging）n進程運行過程中，進程訪問不在內(nèi)存的頁面，引進程運行過程中，進程訪問不在內(nèi)存的頁面，引發(fā)發(fā)，靠缺頁中斷程序裝入所需訪問的不，靠缺頁中斷程序裝入所需訪問的不在內(nèi)存的頁面。在內(nèi)存的頁面。n實現(xiàn)簡單，用得廣，但費時。實現(xiàn)簡單，用得廣，但費時。n預調頁策略預調頁策略（prepaging）n一個頁面被訪問前已預先裝入內(nèi)存，以減少今后一個頁面被訪問前已預先裝入內(nèi)存，以減少今后的缺頁率。主要用于的缺頁率。主要用于n有的系統(tǒng)結合請求調入使用，即每次缺頁時裝入有的系統(tǒng)結合請求

41、調入使用，即每次缺頁時裝入多個頁面。多個頁面。虛分頁所需的硬件支持（補充）虛分頁所需的硬件支持（補充）n頁表機制頁表機制n頁表基本作用是將用戶地址空間中的頁表基本作用是將用戶地址空間中的轉換為內(nèi)存轉換為內(nèi)存空間中的空間中的由于引入虛擬存儲技術的分頁存儲管由于引入虛擬存儲技術的分頁存儲管理模式只需將應用程序的理模式只需將應用程序的，另一部分仍在，另一部分仍在磁盤上，需在頁表中增加若干項，供程序換進（出）做參磁盤上，需在頁表中增加若干項，供程序換進（出）做參考?？?。n標志位（狀態(tài)位）標志位（狀態(tài)位）P:指示該頁是否調入內(nèi)存指示該頁是否調入內(nèi)存n訪問字段訪問字段A：記錄本頁在一段時間內(nèi)被訪問的次數(shù)記

42、錄本頁在一段時間內(nèi)被訪問的次數(shù)n修改位修改位M：該頁在調入內(nèi)存后是否被修改過，若修改還需該頁在調入內(nèi)存后是否被修改過，若修改還需寫回外存。寫回外存。n外存地址：外存地址：指出該頁在外存上的地址指出該頁在外存上的地址頁號頁號物理塊號物理塊號虛分頁所需的硬件支持虛分頁所需的硬件支持n缺頁中斷（缺頁中斷（Page Fault）機構）機構n在地址映射過程中，所訪問的頁不在內(nèi)存時，便產(chǎn)在地址映射過程中，所訪問的頁不在內(nèi)存時，便產(chǎn)生一缺頁中斷；生一缺頁中斷；OS接到此中斷信號后，就調出缺頁接到此中斷信號后，就調出缺頁中斷處理程序，根據(jù)頁表中給出的中斷處理程序，根據(jù)頁表中給出的外存地址外存地址，將該，將該頁

43、頁調入內(nèi)存調入內(nèi)存，更新頁表更新頁表，完成重定位，使進程繼續(xù)，完成重定位，使進程繼續(xù)運行下去。運行下去。3.3 虛分頁式存儲管理虛分頁式存儲管理n硬件地址轉換機構根據(jù)頁表（控制）寄存器找到頁硬件地址轉換機構根據(jù)頁表（控制）寄存器找到頁表首地址表首地址n再由頁表首址找到頁表中要訪問的頁面號再由頁表首址找到頁表中要訪問的頁面號Xn查找頁表對應頁號查找頁表對應頁號X的標志位的標志位n當當X頁標志為頁標志為0時，產(chǎn)生一缺頁中斷時，產(chǎn)生一缺頁中斷n操作系統(tǒng)中斷處理程序在主存中找空閑頁（操作系統(tǒng)中斷處理程序在主存中找空閑頁（需置換需置換的頁的頁）n將輔存地址將輔存地址Y指向的頁面指向的頁面XX插入主存插入

44、主存n修改標志位為修改標志位為1和填寫物理塊號，并修改訪問位為和填寫物理塊號，并修改訪問位為1，若是寫指令，還要置修改位為若是寫指令，還要置修改位為1 （需寫會到內(nèi)存）（需寫會到內(nèi)存）3.3 頁式存儲管理頁式存儲管理頁表地址頁表地址訪問訪問X頁面頁面頁表長度頁表長度頁號頁號 標志標志頁框頁框訪問訪問修改修改輔存地址輔存地址.XY.0缺頁中斷處理程序缺頁中斷處理程序Y0頁面頁面控制寄存器控制寄存器輔存作業(yè)地址空間輔存作業(yè)地址空間輔存（磁盤）輔存（磁盤）存儲器示意圖存儲器示意圖頁表頁表頁面調入過程頁面調入過程1XX缺頁中斷XX虛分頁所需的硬件支持（續(xù)虛分頁所需的硬件支持（續(xù)1）n借助快表借助快表地

45、址變換過程與實分頁類似，但地址變換過程與實分頁類似，但n首先根據(jù)頁號檢索首先根據(jù)頁號檢索，若找到，修改頁表項中，若找到，修改頁表項中的的標志標志（表示該頁已調入內(nèi)存），（表示該頁已調入內(nèi)存），然后利用頁然后利用頁表項中給出的表項中給出的物理塊號物理塊號以及邏輯地址中的以及邏輯地址中的頁內(nèi)地頁內(nèi)地址址，形成物理地址。，形成物理地址。n如果在快表中未找到相應的頁表項，則檢索如果在快表中未找到相應的頁表項，則檢索，察看頁表項中的狀態(tài)位，若該頁已經(jīng)，察看頁表項中的狀態(tài)位，若該頁已經(jīng)調入內(nèi)存，則形成物理地址，并調入內(nèi)存，則形成物理地址，并更新快表更新快表，當快，當快表滿時，應淘汰一個頁表項；若該頁尚未調

46、入內(nèi)表滿時，應淘汰一個頁表項；若該頁尚未調入內(nèi)存，則存，則產(chǎn)生缺頁中斷產(chǎn)生缺頁中斷，請求，請求OSOS把該頁調入內(nèi)存，把該頁調入內(nèi)存，然后再完成重定位。然后再完成重定位。3.3 3.3 頁式存儲管理頁式存儲管理n抖動（抖動（thrashingthrashing）：）：又稱為顛簸，指由又稱為顛簸，指由于缺頁中斷頻繁，于缺頁中斷頻繁，CPUCPU忙于在內(nèi)外存之間忙于在內(nèi)外存之間調頁，很少執(zhí)行有效的任務調頁，很少執(zhí)行有效的任務n缺頁率缺頁率n定義定義 假定作業(yè)共有假定作業(yè)共有n n頁，而系統(tǒng)分配的主存物理塊數(shù)目為頁，而系統(tǒng)分配的主存物理塊數(shù)目為m m，且且1mn1mn。如果作業(yè)在運行過程中成功訪問主

47、存的次數(shù)為。如果作業(yè)在運行過程中成功訪問主存的次數(shù)為S S（所訪問頁在主存中），（所訪問頁在主存中），不成功不成功的訪問次數(shù)為的訪問次數(shù)為F F，總訪總訪問次數(shù)問次數(shù)為為A A，那么缺頁率為，那么缺頁率為f=F/A f=F/A 4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法 Page Replacement Algorithms （淘汰（淘汰 / 置換）置換）n最佳頁面置換算法（最佳頁面置換算法（OPTOPT） 由由Belady于于1966年提出的一種理論上的算法年提出的一種理論上的算法 淘汰淘汰，或是在，或是在最長時間內(nèi)不被訪問的頁最長時間內(nèi)不被訪問的頁面面 是一種理想化的算法

48、，具有最好的性能，但是在實是一種理想化的算法，具有最好的性能，但是在實際上難于實現(xiàn)際上難于實現(xiàn)4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法最佳置換算法頁面淘汰序列最佳置換算法頁面淘汰序列次數(shù)次數(shù) t訪問頁面訪問頁面P=物理塊物理塊M=3失敗失敗F=012345678910 11 1244444443444111111222223333343333355555555F=7缺頁率缺頁率f=7/12=58%21434. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法 先進先出頁面替換算法（先進先出頁面替換算法（FIFOFIFO） 最早的一種頁面置換算法，實現(xiàn)起來比較容易最早的

49、一種頁面置換算法，實現(xiàn)起來比較容易 淘汰在內(nèi)存中駐留時間最久的頁面淘汰在內(nèi)存中駐留時間最久的頁面 在在分頁分頁式式虛擬存儲器虛擬存儲器管理中，發(fā)生缺頁時的置換算法管理中，發(fā)生缺頁時的置換算法采用采用FIFO算法時，如果對一個進程未分配它所要求的算法時，如果對一個進程未分配它所要求的有時就會出現(xiàn)分配的有時就會出現(xiàn)分配的4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法頁塊數(shù)為頁塊數(shù)為3的先進先出置換算法頁面淘汰序列的先進先出置換算法頁面淘汰序列次數(shù)次數(shù) t頁面蹤跡頁面蹤跡P=頁框頁框M=3失敗失敗F=012345678910 11 124441122333554412335551214

50、41233335225521344434 F=9f=9/12=75% 4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法頁塊數(shù)為頁塊數(shù)為4的先進先出置換算法頁面淘汰序列的先進先出置換算法頁面淘汰序列次數(shù)次數(shù)t頁面蹤頁面蹤跡跡P=頁框頁框M=4失敗失敗F=012345678910111244411223335541234123551142322412351433324235121344445F=10f=10/12=83%4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法3 最近最少使用算法最近最少使用算法(LRU)(LRU) 用進程過去對頁面的使用情況來預測其將來的行為用進程

51、過去對頁面的使用情況來預測其將來的行為 需要一定的硬件成本以記錄各頁面所經(jīng)歷的訪問時間需要一定的硬件成本以記錄各頁面所經(jīng)歷的訪問時間 LRU LRU與與OPTOPT區(qū)別：區(qū)別：OPTOPT使用頁面將要訪問的時間，使用頁面將要訪問的時間，進程向后進程向后看，看，LRULRU使用頁面最后一次被訪問的時間，使用頁面最后一次被訪問的時間，進程向前看進程向前看。 實現(xiàn)算法：實現(xiàn)算法：4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法物理塊數(shù)為物理塊數(shù)為3的的LRU堆棧置換算法頁面淘汰序列堆棧置換算法頁面淘汰序列次數(shù)次數(shù) t頁面蹤頁面蹤跡跡P=頁框頁框M=3失敗失敗F=0123456789101

52、112444112233355444112233355444112233352134433452 F=10f=10/12=83% 4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法次數(shù)次數(shù) t0123456789101112頁面蹤頁面蹤跡跡P=432143543215頁框頁框M=4432143543215F=8f=8/12=67%43214354321432143543243 11 3失敗失敗F= 頁塊數(shù)為頁塊數(shù)為4的的LRU置換算法頁面淘汰序列置換算法頁面淘汰序列4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法最近最少使用最近最少使用置換算法理論上性能好，置換算法理論上

53、性能好，但實現(xiàn)代價高但實現(xiàn)代價高（需硬件支持需硬件支持，如：為進程每個內(nèi)存頁面設一，如：為進程每個內(nèi)存頁面設一計時器計時器或或寄存器寄存器，或為進程所有內(nèi)存頁面設一，或為進程所有內(nèi)存頁面設一棧棧/鏈表）。鏈表）。LRU的軟件解決方案的軟件解決方案（LRU的近似算法）的近似算法）：二次機會二次機會(SC, Second Chance）置換算法置換算法時鐘時鐘(Clock)置換算法置換算法最近未使用最近未使用（NRU, Not Recently Used ）置換算法置換算法4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法 實現(xiàn)實現(xiàn)：頁表目中增設訪問位頁表目中增設訪問位R，初值為，初值為

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

55、現(xiàn)簡單，且性能比FIFO好很多；好很多；缺點：缺點：運行效率低，時間開銷大。運行效率低，時間開銷大。4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法現(xiàn)有一進程訪問的頁面號序列為：現(xiàn)有一進程訪問的頁面號序列為：4,7,0,6,7,1,0,64. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法41474117741110007100660710176761011161101006111160n時鐘時鐘(Clock)置換算法置換算法 SC的一種改進實現(xiàn)的一種改進實現(xiàn)SC算法因為常需把給予二次駐留機算法因為常需把給予二次駐留機會的頁面移到鏈尾而降低效率，若把會的頁面移到鏈尾而降低效

56、率，若把其所用的內(nèi)存頁面單向鏈表改為循環(huán)其所用的內(nèi)存頁面單向鏈表改為循環(huán)鏈表，則就不必在鏈中移動頁面了。鏈表，則就不必在鏈中移動頁面了。這種改進的這種改進的SC法就是法就是Clock法。法。該算法首先檢測指針所指的頁面，若該算法首先檢測指針所指的頁面，若訪問位為訪問位為0，則，則淘汰該頁，淘汰該頁，新裝入的頁插入到此位置新裝入的頁插入到此位置，然后指針前進一個位置；，然后指針前進一個位置；如果它的如果它的訪問位為訪問位為1，則清除為，則清除為0，并將并將指針前進一個位置指針前進一個位置，繼續(xù)，繼續(xù)檢查訪問位。重復此過程，直到找到訪問位為檢查訪問位。重復此過程，直到找到訪問位為0的頁面為止。將的

57、頁面為止。將該頁替換為新頁面并置訪問位為該頁替換為新頁面并置訪問位為1。 4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法n最近未使用最近未使用（NRU, Not Recently Used ）置換算法置換算法頁表目中增設頁表目中增設啟動進程時，啟動進程時，R、M置置0；當對頁面執(zhí)行寫操作時，其當對頁面執(zhí)行寫操作時，其和和均由硬件置成均由硬件置成1；當對某頁面執(zhí)行讀操作時，只有訪問位被置成當對某頁面執(zhí)行讀操作時，只有訪問位被置成1，系統(tǒng)每隔固定時間將所有系統(tǒng)每隔固定時間將所有訪問位訪問位R都清都清0。當要淘汰某頁面時，按照當要淘汰某頁面時，按照選擇被淘汰的頁面，若狀選擇被淘汰的頁面

58、，若狀態(tài)位相同，淘汰先進入的頁面。態(tài)位相同，淘汰先進入的頁面。4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法n最近未使用最近未使用（NRU, Not Recently Used ）置換算法置換算法 訪問位訪問位=0=0，修改位，修改位=0=0；直接淘汰；直接淘汰 訪問位訪問位=0=0，修改位，修改位=1=1；寫回外存后淘汰（；寫回外存后淘汰（0 0為訪問位刷新后為訪問位刷新后經(jīng)過）經(jīng)過） 訪問位訪問位=1=1，修改位，修改位=0=0；直接淘汰；直接淘汰 訪問位訪問位=1=1，修改位，修改位=1=1；寫回外存后淘汰；寫回外存后淘汰特點特點：易實現(xiàn)，性能上也夠用。：易實現(xiàn)，性能上也夠

59、用。4. 頁面調度頁面調度（淘汰（淘汰 / 置換）置換）算法算法例例3.2 設某請求分頁系統(tǒng)采用固定分配局部置換策略，一進程的頁面走向設某請求分頁系統(tǒng)采用固定分配局部置換策略，一進程的頁面走向為為4、3、2、1、4、3、5、4、3、2、1、5，該進程分得，該進程分得3個頁塊，初始個頁塊，初始為空，試計算分別采用為空，試計算分別采用FIFO、LRU置換算法時該進程訪問過程中所發(fā)置換算法時該進程訪問過程中所發(fā)生的缺頁次數(shù)和依次被換出的頁面。生的缺頁次數(shù)和依次被換出的頁面。解解： FIFO 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 5 5 2 1 1 4 3 2 1

60、 4 3 3 3 5 2 2 4 3 2 1 4 4 4 3 5 5 是否命中是否命中 x x x x x x x x x 所以該進程運行時共發(fā)生缺頁中斷所以該進程運行時共發(fā)生缺頁中斷9次，被換出次，被換出的頁面依次是的頁面依次是4、3、2、1、4、3。5. 頁面置換算法舉例頁面置換算法舉例頁塊頁塊1頁塊頁塊2頁塊頁塊3 LRU 4 3 2 1 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 所以該進程運行時共發(fā)生