頁式存儲管理 頁式存儲管理的基本原理 分頁存儲器將主存劃分成多個大小相等的頁架，受頁架尺寸限制，程式的邏輯地址也自然分成頁，不同的頁可以放在不同頁架中，不需要連續，頁表用於維繫進程的主存完整性 頁式存儲管理中的地址 頁式存儲管理的邏輯地址由兩部分組成，頁號和單元號，邏輯地址形式：頁號，單元號 頁式存 ...
頁式存儲管理
頁式存儲管理的基本原理
分頁存儲器將主存劃分成多個大小相等的頁架，受頁架尺寸限制，程式的邏輯地址也自然分成頁，不同的頁可以放在不同頁架中，不需要連續，頁表用於維繫進程的主存完整性
頁式存儲管理中的地址
頁式存儲管理的邏輯地址由兩部分組成，頁號和單元號，邏輯地址形式：頁號，單元號
頁式存儲管理的物理地址也有兩部分組成：頁架號和單元號，物理地址形式：頁架號，單元號
地址轉換可以通過查頁表完成
頁式存儲管理的記憶體分配/去配
可用一張位示圖來記錄主存分配情況,建立進程頁表維護主存邏輯完整性
頁的共用
頁式存儲管理能夠實現多個進程共用程式和數據,數據共用：不同進程可以使用不同頁號共用數據頁,程式共用：不同進程必須使用相同頁號共用代碼頁,共用代碼頁中的(JMP<頁內地址>)指令，使用不同頁號是做不到
頁式存儲管理的地址轉換
頁式存儲管理的地址轉換代價
頁表放在主存:每次地址轉換必須訪問兩次主存,1.按頁號讀出頁表中的相應頁架號2.按計算出來的絕對地址進行讀寫,降低了存取速度,解決辦法：利用Cache存放部分頁表
頁式存儲管理的快表
為提高地址轉換速度，設置一個專用的高速存儲器，用來存放頁表的一部分,快表：存放在高速存儲器中的頁表部分,快表表項：頁號，頁架號,這種高速存儲器是聯想存儲器，即按照內容定址，而非按照地址訪問
引入快表後的地址轉換代價
採用快表後，可以加快地址轉換速度,假定主存訪問時間為200毫微秒，快表訪問時間為40毫微秒，查快表的命中率是90%，平均地址轉換代價為(200+40)*90%+(200+200)*10%=256毫微秒比兩次訪問主存的時間（400毫微秒）下降了36%
基於快表的地址轉換流程
按邏輯地址中的頁號查快表,若該頁已在快表中，則由頁架號和單元號形成絕對地址,若該頁不在快表中，則再查主存頁表形成絕對地址，同時將該頁登記到快表中,當快表填滿後，又要登記新頁時，則需在快表中按一定策略淘汰一個舊登記項
多道程式環境下的進程表
進程表中登記了每個進程的頁表,進程表中登記了每個進程的頁表,進程占有處理器運行時，其頁表起始地址和長度送入頁表控制寄存器
頁式虛擬存儲管理
頁式虛擬存儲管理的基本思想
把進程全部頁面裝入虛擬存儲器，執行時先把部分頁面裝入實際記憶體，然後，根據執行行為，動態調入不在主存的頁，同時進行必要的頁面調出,現代OS的主流存儲管理技術,首次只把進程第一頁信息裝入主存，稱為請求頁式存儲管理
頁式虛擬存儲管理的頁表
需要擴充頁表項，指出：每頁的虛擬地址、實際地址,主存駐留標誌、寫回標誌、保護標誌、引用標誌、可移動標誌
頁式虛擬存儲管理的實現
CPU處理地址:若頁駐留，則獲得塊號形成絕對地址,若頁不在記憶體，則CPU發出缺頁中斷
OS處理缺頁中斷:若有空閑頁架，則根據輔存地址調入頁，更新頁表與快表等,若無空閑頁架，則決定淘汰頁，調出已修改頁，調入頁，更新頁表與快表
頁面調度
當主存空間已滿而又需要裝入新頁時，頁式虛擬存儲管理必須按照一定的演算法把已在主存的一些頁調出去,選擇淘汰頁的工作稱為頁面調度,選擇淘汰頁的演算法稱為頁面調度演算法,頁面調度演算法設計不當，會出現（剛被淘汰的頁面立即又要調入，並如此反覆）,這種現象稱為抖動或顛簸
缺頁中斷率
假定進程P共n頁，系統分配頁架數m個,P運行中成功訪問次數為S，不成功訪問次數為F，總訪問次數A=S+F,缺頁中斷率定義為：f=F/A,缺頁中斷率是衡量存儲管理性能和用戶編程水平的重要依據
影響缺頁中斷率的因素
分配給進程的頁架數：可用頁架數越多，則缺頁中斷率就越低,頁面的大小：頁面尺寸越大，則缺頁中斷率就越低,,用戶的程式編製方法：在大數據量情況下，對缺頁中斷率也有很大影響
用戶編程的例子
OPT頁面調度演算法
理想的調度演算法是：當要調入新頁面時，首先淘汰以後不再訪問的頁，然後選擇距現在最長時間後再訪問的頁,該演算法由Belady提出，稱Belady演算法，又稱最佳演算法（OPT）,OPT只可模擬，不可實現
先進先出FIFO頁面調度演算法
總是淘汰最先調入主存的那一頁，或者說主存駐留時間最長的那一頁(常駐的除外),模擬的是程式執行的順序性，有一定合理性
最近最少用LRU頁面調度演算法
淘汰最近一段時間較久未被訪問的那一頁，即那些剛被使用過的頁面，可能馬上還要被使用到,模擬了程式執行的局部屬性，既考慮了迴圈性又兼顧了順序性,嚴格實現的代價大(需要維持特殊隊列)
LRU演算法的模擬實現
每頁建一個引用標誌，供硬體使用,設置一個時間間隔中斷：中斷時頁引用標誌置0,地址轉換時，頁引用標誌置1,,淘汰頁面時，從頁引用標誌為0的頁中間隨機選擇,時間間隔多長是個難點
最不常用LFU頁面調度演算法
淘汰最近一段時間內訪問次數較少的頁面，對OPT的模擬性比LRU更好,基於時間間隔中斷，並給每一頁設置一個計數器,時間間隔中斷發生後，所有計數器清0,每訪問頁1次就給計數器加1,選擇計數值最小的頁面淘汰
時鐘CLOCK頁面調度演算法
採用迴圈隊列機制構造頁面隊列，形成了一個類似於鐘錶面的環形表,隊列指針則相當於鐘錶面上的表針，指向可能要淘汰的頁面使用頁引用標誌位
CLOCK演算法的工作流程
頁面調入主存時，其引用標誌位置1,訪問主存頁面時，其引用標誌位置1,淘汰頁面時，從指針當前指向的頁面開始掃描迴圈隊列,把所遇到的引用標誌位是1的頁面的引用標誌位清0，並跳過,把所遇到的引用標誌位是0的頁面淘汰，指針推進一步
反置頁表
反置頁表的提出
頁表及相關硬體機制在地址轉換、存儲保護、虛擬地址訪問中發揮了關鍵作用，為頁式存儲管理設置專門硬體機構，記憶體管理單元MMU：CPU管理虛擬/物理存儲器的控制線路，把虛擬地址映射為物理地址，並提供存儲保護，必要時確定淘汰頁面，反置頁表IPT：MMU用的數據結構
反置頁表的基本設計思想
針對記憶體中的每個頁架建立一個頁表，按照塊號排序，表項包含：正在訪問該頁框的進程標識、頁號及特征位，和哈希鏈指針等，用來完成記憶體頁架到訪問進程頁號的對應，即物理地址到邏輯地址的轉換
反置頁表的頁表項
- 頁號：虛擬地址頁號
- 進程標誌符：使用該頁的進程號（頁號和進程標誌符結合起來標誌一個特定進程的虛擬地址空間的一頁）
- 標誌位：有效、引用、修改、保護和鎖定等標誌信息
- 鏈指針：哈希鏈
基於反置頁表的地址轉換過程
MMU通過哈希表把進程標識和虛頁號轉換成一個哈希值，指向IPT的一個表目，MMU遍歷哈希鏈找到所需進程的虛頁號，該項的索引就是頁架號，通過拼接位移便可生成物理地址，若遍歷整個反置頁表中未能找到匹配頁表項，說明該頁不在記憶體，產生缺頁中斷，請求操作系統調入
段式程式設計
每個程式可由若幹段組成，每一段都可以從“0”開始編址，段內的地址是連續的,分段存儲器的邏輯地址由兩部分組成,段號：單元號
段式存儲管理的基本思想
段式存儲管理基於可變分區存儲管理實現，一個進程要占用多個分區,硬體需要增加一組用戶可見的段地址寄存器（代碼段、數據段、堆棧段，附加段），供地址轉換使用,存儲管理需要增加設置一個段表，每個段占用一個段表項，包括：段始址、段限長，以及存儲保護、可移動、可擴充等標誌位
段的共用
通過不同進程段表中的項指向同一個段基址來實現,對共用段的信息必須進行保護，如規定只能讀出不能寫入，不滿足保護條件則產生保護中斷
段式虛擬存儲管理的基本思想
把進程的所有分段都存放在輔存中，進程運行時先把當前需要的一段或幾段裝入主存，在執行過程中訪問到不在主存的段時再把它們動態裝入,段式虛擬存儲管理中段的調進調出是由OS自動實現的，對用戶透明,與段覆蓋技術不同，它是用戶控制的主存擴充技術，OS不感知
段頁式存儲管理的基本思想
段式存儲管理可以基於頁式存儲管理實現,每一段不必占據連續的存儲空間，可存放在不連續的主存頁架中,能夠擴充為段頁式虛擬存儲管理,裝入部分段，或者裝入段中部分頁面
