1、第五章 存 儲 管 理n存儲器的層次結構存儲器的層次結構n程序的鏈接和裝入程序的鏈接和裝入n分區法分區法n可重定位分區分配可重定位分區分配n對對 換換 技技 術術n分分 頁頁 技技 術術n分分 段段 技技 術術n段頁式技術段頁式技術第五章 存儲管理n虛擬存儲器虛擬存儲器n請求分頁技術請求分頁技術n頁面置換算法頁面置換算法n內存塊的分配和抖動內存塊的分配和抖動問題問題n請求分段技術請求分段技術第五章 存儲管理 5.15.1 引言引言5.1.1 存儲器的層次結構n在現代計算機系統中，在現代計算機系統中，存儲器是信息外理的存儲器是信息外理的來源與歸宿，占據重要位置。但是，在現有來源與歸宿，占據重要位

2、置。但是，在現有技術條件下，任何一種存儲裝置，都無法同技術條件下，任何一種存儲裝置，都無法同時從速度與容量兩方面，滿足用戶的需求。時從速度與容量兩方面，滿足用戶的需求。實際上它們組成了一個速度由快到慢，容量實際上它們組成了一個速度由快到慢，容量由小到大的存儲裝置層次。由小到大的存儲裝置層次。 5.1.1 存儲器的層次結構5.1.2 存儲管理的目的1)1)主存的分配和管理主存的分配和管理：當用戶需要內存時：當用戶需要內存時, ,系統為之分配相應的存儲空間；不需要系統為之分配相應的存儲空間；不需要時，及時回收，以供其它用戶使用。時，及時回收，以供其它用戶使用。2)2)存儲共享存儲共享：不僅能使多道

3、程序動態地共：不僅能使多道程序動態地共享主存，提高主存利用率，最好還能共享主存，提高主存利用率，最好還能共享主存中某個區域的信息。享主存中某個區域的信息。存儲管理的目的（續）3) 3) 存儲保護存儲保護：確保多道程序都在各自分配到存：確保多道程序都在各自分配到存儲區域內操作，互不干擾，防止一道程序破儲區域內操作，互不干擾，防止一道程序破壞其它作業或系統文件的信息。壞其它作業或系統文件的信息。4) “4) “擴充擴充”主存容量主存容量：為用戶提供比主存物理：為用戶提供比主存物理空間大得多的地址空間，以至使用戶感覺他空間大得多的地址空間，以至使用戶感覺他的作業是在這樣一個大的存儲器中運行。的作業是

4、在這樣一個大的存儲器中運行。5.1.3 用戶程序的主要處理階段5.1.3 用戶程序的主要處理階段 1編輯階段編輯階段 2編譯階段編譯階段 3連接階段連接階段 連接連接就是將編譯或匯編后得到的一組目標就是將編譯或匯編后得到的一組目標模塊及它們所需的庫函數裝配成一個完模塊及它們所需的庫函數裝配成一個完整的裝入模塊的過程。整的裝入模塊的過程。 調用調用B;返回返回調用調用C;返回返回返回返回長度長度L目標模塊目標模塊模塊模塊A模塊模塊B模塊模塊C長度長度M長度長度N0L-1LL+M-1L+ML+M+N-1模模塊塊A模模塊塊B模模塊塊C調用調用L調用調用L+M加載模塊加載模塊相對相對地址地址鏈鏈接接器

5、器000L-1M-1N-1相對相對地址地址5.1.3 用戶程序的主要處理階段4裝入階段裝入階段程序程序數據數據程序程序數據數據PCB棧棧目標代碼目標代碼主存中的進程映像主存中的進程映像鏈鏈接接器器庫存儲器庫存儲器模塊模塊#1模塊模塊#2模塊模塊#n加加載載模模塊塊加加載載器器x存存 儲儲 器器5.1.3 用戶程序的主要處理階段4裝入階段裝入階段n用戶程序經編譯之后的每個目標模塊都以用戶程序經編譯之后的每個目標模塊都以0為基地址順序編址，為基地址順序編址，其余指令中的地址都其余指令中的地址都相對于首地址而編址。相對于首地址而編址。這種地址稱為這種地址稱為相對相對地址或邏輯地址地址或邏輯地址；內存

6、中各物理存儲單元；內存中各物理存儲單元的地址是從統一的基地址開始順序編址的，的地址是從統一的基地址開始順序編址的，這種地址稱為這種地址稱為絕對地址或物理地址絕對地址或物理地址。邏輯地址空間邏輯地址空間物理地址空間物理地址空間5.1.3 用戶程序的主要處理階段4裝入階段裝入階段n程序裝入內存的方式有以下三種：程序裝入內存的方式有以下三種： 絕對裝入方式。絕對裝入方式。 可重定位裝入方式。可重定位裝入方式。 動態運行時裝入方式。動態運行時裝入方式。5運行階段運行階段 絕對裝入方式絕對裝入方式 程序中所使用的絕對地址，可在編譯或匯編時給程序中所使用的絕對地址，可在編譯或匯編時給出，出， 也可由程序員

7、直接賦予。也可由程序員直接賦予。 但在由程序員直接給但在由程序員直接給出絕對地址時，出絕對地址時， 不僅要求程序員熟悉內存的使用情不僅要求程序員熟悉內存的使用情況，而且一旦程序或數據被修改后，可能要改變程序況，而且一旦程序或數據被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉換地址，然后在編譯或匯編時，再將這些符號地址轉換為絕對地址。為絕對地址。 裝入方式裝入方式102414242224JUMP 1424LOAD 1, 2224DEC10程序程序數據數據絕對加載模塊1024存存 儲儲

8、 器器動態運行時裝入方式 為使內存的利用率最大，裝入內存的程序可為使內存的利用率最大，裝入內存的程序可以換出到磁盤上，以后再換到內存中，對換前后以換出到磁盤上，以后再換到內存中，對換前后內存中的位置可能不同。內存中的位置可能不同。裝入方式裝入方式 可重定位裝入方式圖圖 作業裝入內存時的情況作業裝入內存時的情況裝入方式裝入方式 5.1.4 重定位 把作業地址空間中使用的邏輯地址變換成內存空把作業地址空間中使用的邏輯地址變換成內存空間中的物理地址的過程。又稱地址映射。間中的物理地址的過程。又稱地址映射。 如下圖，作業如下圖，作業i i經過重定位，把地址集合映射到以經過重定位，把地址集合映射到以10

9、001000為始址的內存中，作為作業為始址的內存中，作為作業i i的存儲空間。的存儲空間。1. 重定位的類型n靜態重定位靜態重定位n動態重定位動態重定位1. 重定位的類型1)1)靜態重定位靜態重定位: :當用戶程序被裝入內存時，一次性當用戶程序被裝入內存時，一次性實現邏輯地址到物理地址的轉換，以后不再轉換實現邏輯地址到物理地址的轉換，以后不再轉換（一般在裝入內存時由軟件完成）（一般在裝入內存時由軟件完成）作業作業i i在執行前在執行前一次變址，直到該作業完成退出內存為止。一次變址，直到該作業完成退出內存為止。15001. 重定位的類型1)1)靜態重定位靜態重定位: :n優點：不需硬件支持，可以

10、裝入有限多道優點：不需硬件支持，可以裝入有限多道程序（如程序（如MS DOS中的中的TSR）。）。n缺點：一個程序通常需要占用連續的內存缺點：一個程序通常需要占用連續的內存空間，程序裝入內存后不能移動。不易實空間，程序裝入內存后不能移動。不易實現共享。現共享。1. 重定位的類型 2)2)動態重定位動態重定位: :在程序運行過程中要訪問數據時在程序運行過程中要訪問數據時再進行地址變換。由地址變換機構進行的地址再進行地址變換。由地址變換機構進行的地址變換，硬件上需要重定位寄存器的支持。變換，硬件上需要重定位寄存器的支持。1. 重定位的類型 2)2)動態重定位動態重定位: :n優點：優點：nOS可以

11、將一個程序分散存放于不連續的內存空間，可以將一個程序分散存放于不連續的內存空間，可以移動程序。可以移動程序。n有利用實現共享。有利用實現共享。n缺點：需要硬件支持缺點：需要硬件支持, OS實現較復雜。它是虛實現較復雜。它是虛擬存儲的基礎。擬存儲的基礎。第五章 存儲器管理 5.2 分區法 5.2 分區法n把內存分為一些大小相等或不等的分區把內存分為一些大小相等或不等的分區(partition)，每個進程占用一個分區。操作系統，每個進程占用一個分區。操作系統占用其中一個分區。占用其中一個分區。n特點：適用于多道程序系統和分時系統。特點：適用于多道程序系統和分時系統。n支持多個程序并發執行。支持多個

12、程序并發執行。n難以進行內存分區的共享。難以進行內存分區的共享。n分區分配是為支持多道程序運行而設計的一種最分區分配是為支持多道程序運行而設計的一種最簡單的存儲管理方式。簡單的存儲管理方式。 1. 基本思想基本思想n預先把可分配的主存儲器空間分割成預先把可分配的主存儲器空間分割成若干個連續區域，每個區域是一個分若干個連續區域，每個區域是一個分區。區。n內存中分區的內存中分區的個數固定個數固定不變，各個分不變，各個分區的區的大小也固定大小也固定不變，每個分區只可不變，每個分區只可裝入一個進程。裝入一個進程。 5.2.1 固定分區法n等分方式等分方式n差分方式差分方式 2. 分區大小 5.2.1

13、固定分區法固定分區法8 M8 M8 M8 M8 MOperating SystemOperating System8 M12 M8 M8 M6 M4 M2 M固定分區固定分區(大小相同大小相同)固定分區固定分區(多種大小多種大小)n對于分區等分方式，進程裝入內存很對于分區等分方式，進程裝入內存很簡單。簡單。n對于分區差分方式，為進程分配分區對于分區差分方式，為進程分配分區的方法有兩種。的方法有兩種。n多個輸入隊列法多個輸入隊列法n單一輸入隊列法單一輸入隊列法3. 存儲分配 5.2.1 固定分區法固定分區法圖圖5-6 固定分區內存分配固定分區內存分配4.內存分配表圖 固定分區使用表通過設置內存分

14、配表，內存分配簡單通過設置內存分配表，內存分配簡單缺點：內存利用率不高缺點：內存利用率不高 5.2.1 固定分區法固定分區法n優點：易于實現，開銷小。優點：易于實現，開銷小。n缺點：缺點：n分區總數固定，限制了并發執行的程序數分區總數固定，限制了并發執行的程序數目。目。n小作業不能充分利用分區空間小作業不能充分利用分區空間n內碎片造成浪費內碎片造成浪費 5.2.1 固定分區法固定分區法 5.2.2 動態分區法n 基本思想：內存不是預先劃分好的，基本思想：內存不是預先劃分好的，而是當進程裝入時，根據進程的需求而是當進程裝入時，根據進程的需求和內存空間的使用情況來決定是否分和內存空間的使用情況來決

15、定是否分配。若有足夠的空間，則按需要分割配。若有足夠的空間，則按需要分割一部分分區給該進程；否則令其等待一部分分區給該進程；否則令其等待主存空間主存空間 5.2.2 動態分區法n內存管理：設置內存空閑塊表內存管理：設置內存空閑塊表記記錄了空閑區起始地址和長度錄了空閑區起始地址和長度n內存分配：動態分配內存分配：動態分配n內存回收：當某一塊歸還后，前后空內存回收：當某一塊歸還后，前后空間合并，修改內存空閑塊表間合并，修改內存空閑塊表圖 MVT的內存分配和進程調度情況1. 數據結構n空閑分區表空閑分區表n空閑分區鏈空閑分區鏈 5.2.2 動態分區法圖 空閑分區表n空閑分區表空閑分區表n使用鏈指針將

16、所有空閑分區鏈接成一條鏈。使用鏈指針將所有空閑分區鏈接成一條鏈。狀態位狀態位分區大小分區大小n空閑分區鏈空閑分區鏈 2.分配算法n 尋找某個空閑分區，其大小需大于或等于程序的要求。尋找某個空閑分區，其大小需大于或等于程序的要求。若是大于要求，則將該分區分割成兩個分區，其中一若是大于要求，則將該分區分割成兩個分區，其中一個分區為要求的大小并標記為個分區為要求的大小并標記為“占用占用”，而另一個分，而另一個分區為余下部分并標記為區為余下部分并標記為“空閑空閑”。分區的先后次序通。分區的先后次序通常是從內存低端到高端。常是從內存低端到高端。n最先適應法最先適應法n最佳適應法最佳適應法n循環適應法循環

17、適應法 5.2.2 動態分區法 1)1)最先適應法最先適應法分配算法n空閑表按位置排列（空閑塊地址小，在表空閑表按位置排列（空閑塊地址小，在表中的序號也小）。中的序號也小）。n分配內存時，在各空閑分區中查找滿足大分配內存時，在各空閑分區中查找滿足大小要求的可用塊。找到第一個可滿足要求小要求的可用塊。找到第一個可滿足要求的空閑塊就停止查找，并進行分配。的空閑塊就停止查找，并進行分配。n若空閑空間全部占用則從空閑表取消該項，若空閑空間全部占用則從空閑表取消該項，若有剩余，則余下部分仍保留在空閑表中，若有剩余，則余下部分仍保留在空閑表中，并更新分區大小和分區地址。并更新分區大小和分區地址。n該算法的

18、分配和釋放的時間性能較好，較大的空閑分區該算法的分配和釋放的時間性能較好，較大的空閑分區可以被保留在內存高端。可以被保留在內存高端。n但隨著低端分區不斷劃分而產生較多小分區，每次分配但隨著低端分區不斷劃分而產生較多小分區，每次分配時查找時間開銷會增大。時查找時間開銷會增大。2)最佳適應算法n空閑表以空閑塊大小為序，按增量形空閑表以空閑塊大小為序，按增量形式排列。接到內存申請時，在空閑塊式排列。接到內存申請時，在空閑塊表中找到一個不小于請求的最小空閑表中找到一個不小于請求的最小空閑塊進行分配塊進行分配n為作業選擇分區時總是尋找其大小最為作業選擇分區時總是尋找其大小最接近于作業所要求的存儲區域。接

19、近于作業所要求的存儲區域。n特點：用最小空間滿足要求特點：用最小空間滿足要求n個別來看，碎片較小，但從整體來看，會形成個別來看，碎片較小，但從整體來看，會形成較多外碎片。較大的空閑分區可以被保留。較多外碎片。較大的空閑分區可以被保留。3)循環適應算法n接到內存申請時，在空閑塊表中，上接到內存申請時，在空閑塊表中，上次找到的可用分區的下一個空閑分區次找到的可用分區的下一個空閑分區開始查找可滿足大小要求的第一個空開始查找可滿足大小要求的第一個空閑分區。閑分區。n該算法的分配和釋放的時間性能較好，使該算法的分配和釋放的時間性能較好，使空閑分區分布得更均勻，但較大的空閑分空閑分區分布得更均勻，但較大的

20、空閑分區不易保留。區不易保留。4)最壞適應算法n找到最大的空閑分區找到最大的空閑分區.較大的空閑分區不被保留。較大的空閑分區不被保留。圖5-9 分配16 KB內存塊之前和之后的內存配置放置算法分析n這三種放置算法的優劣很難區分，要具體情況具體分析。n例如：某時刻系統中有三個空閑區n其大小和首址為：n(35KB，100KB)、(12KB，156KB)、(28KB，200KB)n有一作業系列：n(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)5.3 可重定位分區分配n經過一段時間的分配回收后，內存中存經過一段時間的分配回收后，內存中存在很多很小的空閑塊。它們每一個都很在很多很

21、小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片。足分配要求。這些空閑塊被稱為碎片。n造成存儲資源的浪費造成存儲資源的浪費1.碎片問題碎片問題n內部碎片與外部碎片內部碎片與外部碎片n在一個分區內部出現的碎片（即被浪費在一個分區內部出現的碎片（即被浪費的空間）稱做內部碎片，如固定分區法的空間）稱做內部碎片，如固定分區法會產生內部碎片。會產生內部碎片。n在所有分區之外新增的碎片稱做外部碎在所有分區之外新增的碎片稱做外部碎片片.1.碎片問題碎片問題1.碎片問題碎片問題內部碎片內部碎片1.碎片問題碎片問題外部碎片外部碎片2.

22、緊縮緊縮n移動某些已分配區的內容，使所有進程移動某些已分配區的內容，使所有進程的分區緊挨在一起，而把空閑區留在另的分區緊挨在一起，而把空閑區留在另一端。這種技術稱為緊縮（或拼湊）。一端。這種技術稱為緊縮（或拼湊）。圖 可重定位分區的緊縮n什么時候進行緊縮？有兩種方案什么時候進行緊縮？有兩種方案n當進程結束、釋放所占用的分區時當進程結束、釋放所占用的分區時n在分配進程的分區時進行在分配進程的分區時進行2.緊縮緊縮3. 動態重定位動態重定位n動態重定位經常用硬件實現。動態重定位經常用硬件實現。n硬件支持硬件支持n重定位寄存器重定位寄存器 為為了防止一道作業有意或無意地破壞了防止一道作業有意或無意地

23、破壞操作系統或其它作業。一般說來，采用操作系統或其它作業。一般說來，采用硬件支持，實現有效的存儲保護。通常硬件支持，實現有效的存儲保護。通常可采取可采取界限寄存器方式進行保護。界限寄存器方式進行保護。存儲保護存儲保護3. 動態重定位動態重定位n硬件支持硬件支持n基址寄存器：基址寄存器：存放用戶程序在內存的起始存放用戶程序在內存的起始地址地址n限長寄存器：限長寄存器：存放用戶程序邏輯地址的最存放用戶程序邏輯地址的最大范圍大范圍存儲保護防止地址越界n60K 60K 訪問地址訪問地址 =124K =124K，則產生訪問則產生訪問地址越界中斷地址越界中斷存儲保護防止地址越界n相對地址相對地址 限長寄存

24、器的值，則產生訪限長寄存器的值，則產生訪問地址越界中斷問地址越界中斷圖 動態重定位的實現過程存儲保護防止操作越權 對于允許多個進程共享的存儲區對于允許多個進程共享的存儲區域，每個進程都有自己的訪問權限。域，每個進程都有自己的訪問權限。如果一個進程對共享區域的訪問違如果一個進程對共享區域的訪問違反了權限規定，則發生操作越權，反了權限規定，則發生操作越權，即讀寫保護。即讀寫保護。4. 可重定位分區法的優缺點可重定位分區法的優缺點n優點優點:可以消除碎片，能夠分配更多的分可以消除碎片，能夠分配更多的分區，有助于多道程序設計，提高內存的區，有助于多道程序設計，提高內存的利用率。利用率。n缺點缺點：緊縮

25、花費了大量緊縮花費了大量CPU時間；當進時間；當進程大于整個空閑區時，仍要浪費一定的程大于整個空閑區時，仍要浪費一定的內存；進程的存儲區內可能放有從未使內存；進程的存儲區內可能放有從未使用的信息；進程之間無法對信息共享。用的信息；進程之間無法對信息共享。5.4 對 換 技 術圖5-12 對換兩個進程圖5-13 多道程序對換技術示例思考n在一個使用交換技術的系統中，按地址在一個使用交換技術的系統中，按地址從低到高排列的空閑內存空間長度是從低到高排列的空閑內存空間長度是10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, 15KB。對于下列順序的段請求。對于下列順序的段請求

26、(1) 12KB (2) 10KB (3)15KB (4) 18KB (5) 12KB分別使用首次適配、最佳適配和下次適分別使用首次適配、最佳適配和下次適配算法說明空間的使用情況，并說明對配算法說明空間的使用情況，并說明對暫不能分配情況的處理方法。暫不能分配情況的處理方法。思考n首次適配首次適配n(1) 12KB 2n(2) 10KB 0n(3) 15KB 3n(4) 18KB 失敗失敗n(5) 12KB 6思考n最佳適配最佳適配n(1) 12KB 6n(2) 10KB 0n(3) 15KB 7n(4) 18KB 3n(5) 12KB 2思考n下次適配下次適配n(1) 12KB 2n(2) 1

27、0KB 3n(3) 15KB 7n(4) 18KB 失敗失敗n(5) 12KB 6思考n當出現暫時不能分配情況時，系統可以當出現暫時不能分配情況時，系統可以采用緊湊技術，將內存中的進程移動到采用緊湊技術，將內存中的進程移動到存儲器的一端，使夾雜于其間的空閑小存儲器的一端，使夾雜于其間的空閑小空間移動到另一端，形成一個較大的可空間移動到另一端，形成一個較大的可用空間，以滿足用戶的需求。用空間，以滿足用戶的需求。5.5 分 頁 技 術5.5.1 分頁技術的引入5.5.2 分頁存儲管理的基本概念5.5.3 分頁系統中的地址映射5.5.4 頁面尺寸5.5.5 硬件支持5.5.6 保護方式5.5.7 頁

28、表的構造5.5.8 頁面共享5.5 分 頁 技 術1. 分頁技術的引入分頁技術的引入n在在動態分區的存儲空間中，動態分區的存儲空間中， 存在存在“ “碎片碎片” ”問題。盡管采用問題。盡管采用“ “緊湊緊湊” ”技術可以解決這技術可以解決這個問題，但要為移動大量信息花去不少個問題，但要為移動大量信息花去不少的處理機時間，代價較高的處理機時間，代價較高。n分頁技術：允許一個進程的存儲空間不分頁技術：允許一個進程的存儲空間不必連續，可以分散地放在各個空閑的內必連續，可以分散地放在各個空閑的內存區域中。解決了碎片，并提高了內存存區域中。解決了碎片，并提高了內存的利用率。的利用率。5.5 分 頁 技

29、術5.5.2 分頁存儲管理的基本概念分頁存儲管理的基本概念（1 1）邏輯空間）邏輯空間分頁分頁（2 2）內存空間）內存空間分塊分塊（3 3）邏輯地址表示）邏輯地址表示（4 4）內存分配原則）內存分配原則（5 5）頁表）頁表（6 6）內存塊表）內存塊表5.5 分 頁 技 術2. 分頁存儲管理的基本概念分頁存儲管理的基本概念n(1)邏輯空間分頁邏輯空間分頁n把進程的邏輯地址空間劃分成若干個大小把進程的邏輯地址空間劃分成若干個大小相等的部分，每個部分稱為頁。相等的部分，每個部分稱為頁。n每個頁有一個編號。從每個頁有一個編號。從0 0開始編制頁號。開始編制頁號。n頁內地址是相對于頁內地址是相對于0 0

30、編址。編址。5.5 分 頁 技 術0頁2頁3頁4頁n-1頁1頁進程進程1的邏輯地址空間的邏輯地址空間5.5 分 頁 技 術2. 分頁存儲管理的基本概念分頁存儲管理的基本概念n(2)(2)內存空間分塊內存空間分塊n內存按頁的大小劃分為大小相等的區域，內存按頁的大小劃分為大小相等的區域，稱為內存塊稱為內存塊n每個塊有一個編號。從每個塊有一個編號。從0 0開始編制塊號。開始編制塊號。5.5 分 頁 技 術0塊2塊3塊4塊m-1塊1塊內存物理地址空間內存物理地址空間5.5 分 頁 技 術n頁面（或塊）的大小是由硬件（系統）頁面（或塊）的大小是由硬件（系統）確定的。確定的。n一般，頁面大小應是一般，頁面

31、大小應是2的若干次冪的若干次冪(3) 邏輯地址表示n對某特定機器，其地址結構是一定的。對某特定機器，其地址結構是一定的。若給定一個邏輯地址空間中的地址為若給定一個邏輯地址空間中的地址為A，頁面的大小為頁面的大小為L，則頁號，則頁號P和頁內地址和頁內地址d可按下式求得：可按下式求得：np = INTA/L , d = A MOD L例1：設某系統的頁面大小為1KB，給定的邏輯地址為3456,請給出該邏輯地址的頁號和頁內地址。解：頁的大小 L=1KB 邏輯地址A=3456則：頁號p= INTA/L = INT3456/1024=3頁內地址d = 3456 MOD 1024 =384(4)內存分配原

32、則內存分配原則n在為進程分配內存時，以塊為單位將在為進程分配內存時，以塊為單位將進程中的若干個頁分別裝入到多個可進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。以不相鄰接的物理塊中。圖 分頁存儲管理系統5 頁進程進程1地址空間地址空間圖 分頁存儲管理系統5 頁進程進程1地址空間地址空間5 頁n 頁表的作用頁表的作用是實現從頁號到物理塊號的地址映射。(5)頁表頁表頁表圖 分頁存儲管理系統n整個系統有一個內存塊表。每個內存塊整個系統有一個內存塊表。每個內存塊在內存塊表中占一項，表明該塊當前空在內存塊表中占一項，表明該塊當前空閑還是已分出去了。閑還是已分出去了。(6)內存塊表內存塊表3. 分頁

33、系統中的地址映射每個進程平均有半個頁面的內部碎片每個進程平均有半個頁面的內部碎片3. 分頁系統中的地址映射n采用分頁技術不存在外部碎片。采用分頁技術不存在外部碎片。n每個進程平均有半個頁面的內部碎片每個進程平均有半個頁面的內部碎片4. 頁面尺寸即，由頁表和內部碎片帶來的總開銷是：即，由頁表和內部碎片帶來的總開銷是： s . e /p+p/2對對p求導，令其等于求導，令其等于0，得到方程：，得到方程： - s . e /p2 + 1/2=0設進程的平均大小為設進程的平均大小為s字節，頁面尺寸為字節，頁面尺寸為p字節，字節，每個頁表項占每個頁表項占e字節字節由頁表和內部碎片帶來的總開銷是：由頁表和

34、內部碎片帶來的總開銷是： 頁表大小頁表大小+內部碎片大小內部碎片大小s . e /pp/2esp2 得出最佳頁面尺寸公式（僅考慮上述兩個因素）：如果s = 1 MB，e = 8 B，則最佳頁面尺寸是4 KB。4. 頁面尺寸5. 硬件支持n通常將頁表保存在內存中，由一個頁表通常將頁表保存在內存中，由一個頁表基址寄存器基址寄存器PTBR指向該頁表。整個系指向該頁表。整個系統只有一個統只有一個PTBR。n帶來存取速度下降的矛盾。帶來存取速度下降的矛盾。n快表（或快表（或Translation Lookaside Buffer, TLB）。快表每項包括鍵號和值兩部分，）。快表每項包括鍵號和值兩部分，鍵

35、號是當前進程正在使用的某個頁面號，鍵號是當前進程正在使用的某個頁面號，值是該頁面所對應的物理塊號。值是該頁面所對應的物理塊號。圖 利用頁表實現地址轉換圖 利用快表實現地址轉換6. 保護方式（1）利用頁表本身進行保護）利用頁表本身進行保護（2）設置存取控制位）設置存取控制位（3）設置合法標志）設置合法標志7. 頁表的構造(1) 多級頁表多級頁表(2) 散列頁表散列頁表(3) 倒置頁表倒置頁表7. 頁表的構造（1 1）多級頁表多級頁表n大多數現代計算機系統都支持非常大的大多數現代計算機系統都支持非常大的邏輯地址空間，如邏輯地址空間，如232 264。在這種情況。在這種情況下，只用一級頁表會使頁表變得非常大。下，只用一級頁表會使頁表變得非常大。n一種方法是利用兩級頁表，即把頁表本一種方法是利用兩級頁表，即把頁表本身也分頁。身也分頁。 圖 兩級頁表地址結構圖5-19 兩級頁表結構圖5-20 兩級頁表結構的地址轉換aap1p1rrp2p2圖5-21 三級頁表地址結構（2）散列頁表n以頁號作為參數形成散列值。散列表中每一以頁號作為參數形成散列值。散列表中每一項有一個鏈表，它把有相同散列值的元素鏈項有一個鏈表，它把有相同散列值的元素鏈接起來。每個鏈表元素由三部分組成：接起來。每個鏈表元素由三部分組成：n頁號；頁號；n對應的內存塊號