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