【文章內(nèi)容簡介】 立一個頁表，頁表給出邏輯頁號和具體內(nèi)存塊號相應(yīng)的關(guān)系。頁表放在內(nèi)存，屬于進程的現(xiàn)場信息。 頁表主要用于：①記錄進程的內(nèi)存分配情況②實現(xiàn)進程運行時的動態(tài)重定位。 . . . 0 1 2 3 4 5 6 0 1 2 3 4 5 6 進程的 地址空間 頁框 （物理塊） 頁號 頁表 主存中頁框（物理塊） . . . . 頁表示意圖： 分頁存儲管理示意圖 0 11 12 31 頁號 P 頁內(nèi)位移量 W 編號 0~1048575 相對地址 0~4095 討論 為什么頁的大小既不能太大，也不能太小？ 2. 地址轉(zhuǎn)換 – 動態(tài)重定位 地址越界 p180。 頁表 L 比較 p=L . b + 頁號 p 頁內(nèi)地址 d P180。 d 頁表地址寄存器 頁表長度寄存器 邏輯地址 物理地址 主要問題：兩次內(nèi)存訪問 引入快表 – 加快地址轉(zhuǎn)換 快表使用聯(lián)想存儲器 （ associative memory，也稱為相聯(lián)存儲器） ，在 IBM系統(tǒng)中稱 TLB（ Translation lookaside buffers） ? 用途：保存正在運行進程的部分頁表項，以快速重定位 ? 快表表目內(nèi)容：頁號、內(nèi)存塊號、標(biāo)識位、淘汰位 ? 快表的特點：可按內(nèi)容并行查找 ? 快表命中率：已經(jīng)證明， 16個表目可達 90%以上。 Intel 80x86/Pentium有 32項， SGI MIPS R4000有 48項 ? 理論依據(jù)：程序的局部性； 使用快表進行地址轉(zhuǎn)換 地址越界 p180。 頁表 L 比較 P=L p p180。 . 快表 b + 頁號 p 頁內(nèi)地址 d P180。 d 頁表地址寄存器 頁表長度寄存器 邏輯地址 . . 物理地址 統(tǒng)計表明， 16個表項，命中率 95%以上 擴展：多級頁表 問題： 32位地址的邏輯地址空間，如果頁面大小為 4K，則需要 1M個頁表表項，假設(shè)每個頁表表項 1B，則 每個進程需要1MB的連續(xù)內(nèi)存空間來存儲頁表 。 0 11 12 31 頁號 P 頁內(nèi)位移量 W 編號 0~1048575 相對地址 0~4095 64位邏輯地址空間呢？ 需要 4096G個頁表項。 一種解決方案：采用多級頁表，來使連續(xù)空間變成離散空間 二級頁表 – 以 32位邏輯地址空間為例 0 11 12 31 頁目錄號 頁內(nèi)位移量 W 頁表位移 22 21 連續(xù)的內(nèi)存分配變成了離散分配 64位地址空間是否可以采用二級頁表？ 頁目錄地址 目錄位移 頁表位移 頁位移 虛擬地址 頁表地址 . . . 頁目錄（每進程一個） 塊號 . . . 頁 表 代碼或數(shù)據(jù) . . . 物理頁 + + 二級頁表地址轉(zhuǎn)換 （未畫出快表） 0 31 0/1 0/1 0/1 0/1 0/1 0 1 7 …… 空閑塊數(shù) …… ?空塊管理 ——位示圖 (用于外存分配時常叫盤圖 ) 使用時需進行字位號到塊號的轉(zhuǎn)換： b=i*w+j b：塊號， i：字號， w：字的位數(shù)， j：字內(nèi)位數(shù) 3. 頁的分配與回收 內(nèi)存分配算法 ? 計算一個作業(yè)所需要的總塊數(shù) N ? 查位示圖，看看是否還有 N個空閑塊 ? 如果有足夠的空閑塊，則頁表長度設(shè)為 N，填入PCB中；申請頁表區(qū)，把頁表始址填入 PCB ? 依次分配 N個空閑塊，將塊號和頁號填入頁表 ? 修改位示圖 頁的共享與保護 ? 頁的共享 ? 多個進程的虛頁對應(yīng)同一個物理地址空間； ? 共享不易實現(xiàn) (P93及圖 39) ? 頁的保護 ? 越界檢查：頁表長度寄存器； ? 存取控制檢查：頁表中設(shè)置有存取控制字段，一般是“ 只讀 ”、“ 可寫 ”以及“ 執(zhí)行 ”三種權(quán)限的組合。 主存空間利用率 ? 內(nèi)存利用率高，且對用戶透明，基本解決了“碎片”問題 ? 每個空閑的內(nèi)存塊都是一個可分配的單位，徹底消除了“ 外碎片 ”； ? 雖然進程最后一頁可能存在“ 內(nèi)碎片 ”，但頁面相對較小， 內(nèi)碎片 也很小。 6. 實分頁存儲管理方式小結(jié) ? 優(yōu)點： 內(nèi)存利用率高 ，解決了碎片問題； 便于管理。 ? 缺點： 不易 實現(xiàn) 共享 （見 P93）； 不便于 頁面 動態(tài)增長 ； 進程仍受內(nèi)存可用空間大小的限制； 所需硬件支持較多。 虛擬 頁式存儲管理 ? 實分頁式存儲管理 要求作業(yè) 全部裝入內(nèi)存 后才能運行， 存在以下問題 ： ? 當(dāng)作業(yè)所要求的內(nèi)存空間大于物理內(nèi)存總?cè)萘?，無法運行 ； ? 當(dāng)有大量作業(yè)要求運行，而內(nèi)存容量不足以容納所有作業(yè)，只能是少數(shù)作業(yè)先運行，其他大量的作業(yè)在外存等待。 ? 解決方法 ? 擴充物理內(nèi)存：增加成本； ? 虛擬存儲技術(shù) ：允許作業(yè)僅 部分裝入內(nèi)存 即可運行，其理論依據(jù)是 程序局部性原理 。 程序局部性原理 Denning， 1968 程序在執(zhí)行時呈現(xiàn)出 高度的局部性特征 ；即在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分 ；相應(yīng)地， 它所訪問的存儲空間也局限于某個區(qū)域 。程序局部性表現(xiàn)在 時間 與 空間 兩個方面： ? 時間局部性 ：一條指令被執(zhí)行了，則在不久的將來它可能再次被執(zhí)行； ? 空間局部性 ：若某一存儲單元被訪問，則在不久之后，與該存儲單元相鄰的單元也可能被訪問。 因此，作業(yè)可以不必全部裝入內(nèi)存即可運行。 虛擬存儲器概念 1961年由英國曼徹斯特大學(xué)的 Fotheringham提出，今天的 OS普遍采用這一技術(shù)管理內(nèi)存。 ? 程序僅需將當(dāng)前要運行的 頁或段 裝入內(nèi)存即可運行； ? 運行時，如果需要訪問的 頁或段 不在內(nèi)存中（稱為 缺頁或缺段 ），由 OS提供的請求 調(diào)頁（段） 功能，將其調(diào)入內(nèi)存； ? 如果內(nèi)存已滿，則需按照預(yù)定的 置換策略 ，將暫時不用的 頁或段 調(diào)出外存，騰出足夠的存儲空間，在裝入所缺的 頁或段 。 對于用戶而言，看到的是一個大容量的內(nèi)存 （容量是外存的，速度是內(nèi)存的） ，但實際上是虛的，因此稱為 虛擬存儲器 。 虛擬 頁式存儲管理 基本思想 實分頁和虛擬存儲技術(shù)的結(jié)合，也叫 請求分頁存儲管理。 ? 按照 實分頁 方式進行分頁和分塊； ? 進程運行時，只需 部分頁面 在內(nèi)存； ? 當(dāng)進程訪問的頁不在內(nèi)存時將產(chǎn)生 缺頁中斷 ， 由中斷服務(wù)程序把所缺頁裝入內(nèi)存 ? 若內(nèi)存空間已滿，需要根據(jù) 頁面置換策略（頁面調(diào)度算法） 淘汰某個內(nèi)存頁面，再裝入所缺頁面。 本節(jié)重點介紹頁面調(diào)度算法。 2. 地址轉(zhuǎn)換及相應(yīng)硬件支持 1）頁表機制 虛分頁地址轉(zhuǎn)換方式和實分頁類似，但也有所區(qū)別。 ?狀態(tài)位 P：該頁面是否已經(jīng)調(diào)入內(nèi)存 ?訪問位 A，記錄該頁被訪問過的標(biāo)志或被訪問過的次數(shù)，和修改位一起做為頁面置換的依據(jù)； ?修改位 W：該頁面在掉入內(nèi)存后是否被修改過，如被修改過，調(diào)出內(nèi)存時，需先將其寫入內(nèi)存； ?存取控制 ：對該頁的訪問權(quán)限，如只讀、可寫、可執(zhí)行，或三者的結(jié)合 ?外存地址 ：該頁在外存上的地址，當(dāng)該頁面不在內(nèi)存時，據(jù)此從外存調(diào)入 頁號 塊號 狀態(tài)位 P 訪問位 A 修改位 W 外存地址 存取控制 2）缺頁中斷（ Page Fault）機構(gòu) 在地址映射過程中，所訪問的頁不在內(nèi)存時，便產(chǎn)生一 缺頁中斷 ； OS接到此中斷信號后，就調(diào)出 缺頁中斷處理程序 ，根據(jù)頁表中給出的 外存地址 ，將該頁調(diào)入內(nèi)存，更新頁表，完成重定位。這期間可能 調(diào)用置換程序 。 缺頁中斷與常規(guī)中斷的不同之處： ? 常規(guī)中斷是在一條指令執(zhí)行完之后響應(yīng)與處理； ? 缺頁中斷是在指令執(zhí)行期間產(chǎn)生和處理中斷信號；且在一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。 ? 因此，對于 缺頁中斷 ，一般按“ 故障 ”處理。 3）地址轉(zhuǎn)換 ? 首先檢索快表， 若找到 ，修改頁表項中的訪問位，然后利用頁表項中內(nèi)容，形成物理地址。 ? 如果在快表中 未找到 ，則檢索頁表，察看頁表項中的狀態(tài)位，若該頁已經(jīng)調(diào)入內(nèi)存，則形成物理地址，并更新快表，當(dāng)快表滿時，應(yīng)淘汰一個頁表項； ? 若該頁尚未調(diào)入內(nèi)存，則 產(chǎn)生缺頁中斷 ，請求 OS把該頁調(diào)入內(nèi)存，然后再完成重定位。 3. 內(nèi)存分配策略和分配算法 ?最小物理塊數(shù)的確定 ? 保證進程正常運行所需的最少物理塊數(shù)； ? 與指令的格式、功能和尋址方式有關(guān)。 在為進程分配內(nèi)存時，涉及到三個問題： 1）最小物理塊數(shù)的確定； 2）物理塊的分配策略； 3）物理塊的分配算法。 例：一條復(fù)雜 指令 可能是 2個或 2個以上字節(jié)，可能 跨