【正文】 調(diào)度算法。 虛擬 頁式存儲管理 基本思想 實分頁和虛擬存儲技術(shù)的結(jié)合，也叫 請求分頁存儲管理。 ? 程序僅需將當(dāng)前要運行的 頁或段 裝入內(nèi)存即可運行； ? 運行時，如果需要訪問的 頁或段 不在內(nèi)存中（稱為 缺頁或缺段 ），由 OS提供的請求 調(diào)頁（段） 功能，將其調(diào)入內(nèi)存； ? 如果內(nèi)存已滿，則需按照預(yù)定的 置換策略 ，將暫時不用的 頁或段 調(diào)出外存，騰出足夠的存儲空間，在裝入所缺的 頁或段 。 因此，作業(yè)可以不必全部裝入內(nèi)存即可運行。 程序局部性原理 Denning， 1968 程序在執(zhí)行時呈現(xiàn)出 高度的局部性特征 ；即在一較短的時間內(nèi)，程序的執(zhí)行僅局限于某個部分 ；相應(yīng)地， 它所訪問的存儲空間也局限于某個區(qū)域 。 虛擬 頁式存儲管理 ? 實分頁式存儲管理 要求作業(yè) 全部裝入內(nèi)存 后才能運行， 存在以下問題 ： ? 當(dāng)作業(yè)所要求的內(nèi)存空間大于物理內(nèi)存總?cè)萘?，無法運行 ； ? 當(dāng)有大量作業(yè)要求運行，而內(nèi)存容量不足以容納所有作業(yè)，只能是少數(shù)作業(yè)先運行，其他大量的作業(yè)在外存等待。 6. 實分頁存儲管理方式小結(jié) ? 優(yōu)點： 內(nèi)存利用率高 ，解決了碎片問題； 便于管理。 一種解決方案：采用多級頁表，來使連續(xù)空間變成離散空間 二級頁表 – 以 32位邏輯地址空間為例 0 11 12 31 頁目錄號 頁內(nèi)位移量 W 頁表位移 22 21 連續(xù)的內(nèi)存分配變成了離散分配 64位地址空間是否可以采用二級頁表？ 頁目錄地址 目錄位移 頁表位移 頁位移 虛擬地址 頁表地址 . . . 頁目錄（每進(jìn)程一個） 塊號 . . . 頁 表 代碼或數(shù)據(jù) . . . 物理頁 + + 二級頁表地址轉(zhuǎn)換 （未畫出快表） 0 31 0/1 0/1 0/1 0/1 0/1 0 1 7 …… 空閑塊數(shù) …… ?空塊管理 ——位示圖 (用于外存分配時常叫盤圖 ) 使用時需進(jìn)行字位號到塊號的轉(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個空閑塊，將塊號和頁號填入頁表 ? 修改位示圖 頁的共享與保護(hù) ? 頁的共享 ? 多個進(jìn)程的虛頁對應(yīng)同一個物理地址空間； ? 共享不易實現(xiàn) (P93及圖 39) ? 頁的保護(hù) ? 越界檢查：頁表長度寄存器； ? 存取控制檢查：頁表中設(shè)置有存取控制字段，一般是“ 只讀 ”、“ 可寫 ”以及“ 執(zhí)行 ”三種權(quán)限的組合。 d 頁表地址寄存器 頁表長度寄存器 邏輯地址 . . 物理地址 統(tǒng)計表明， 16個表項，命中率 95%以上 擴(kuò)展：多級頁表 問題： 32位地址的邏輯地址空間，如果頁面大小為 4K，則需要 1M個頁表表項，假設(shè)每個頁表表項 1B，則 每個進(jìn)程需要1MB的連續(xù)內(nèi)存空間來存儲頁表 。 頁表 L 比較 P=L p p180。 d 頁表地址寄存器 頁表長度寄存器 邏輯地址 物理地址 主要問題：兩次內(nèi)存訪問 引入快表 – 加快地址轉(zhuǎn)換 快表使用聯(lián)想存儲器 （ associative memory，也稱為相聯(lián)存儲器） ，在 IBM系統(tǒng)中稱 TLB（ Translation lookaside buffers） ? 用途：保存正在運行進(jìn)程的部分頁表項，以快速重定位 ? 快表表目內(nèi)容：頁號、內(nèi)存塊號、標(biāo)識位、淘汰位 ? 快表的特點：可按內(nèi)容并行查找 ? 快表命中率：已經(jīng)證明， 16個表目可達(dá) 90%以上。 . . . 0 1 2 3 4 5 6 0 1 2 3 4 5 6 進(jìn)程的 地址空間 頁框 （物理塊） 頁號 頁表 主存中頁框（物理塊） . . . . 頁表示意圖： 分頁存儲管理示意圖 0 11 12 31 頁號 P 頁內(nèi)位移量 W 編號 0~1048575 相對地址 0~4095 討論 為什么頁的大小既不能太大，也不能太小？ 2. 地址轉(zhuǎn)換 – 動態(tài)重定位 地址越界 p180。頁表放在內(nèi)存，屬于進(jìn)程的現(xiàn)場信息。 2）邏輯地址轉(zhuǎn)換為物理地址，需要建立頁號和塊號的映射關(guān)系表： 頁表 。 2） 在實分頁存儲管理中 ， 進(jìn)程運行時，全部頁面必須裝入內(nèi)存，但 邏輯上連續(xù)的各個頁所對應(yīng)的內(nèi)存塊可以不連續(xù) 。 頁式存儲管理 ——不用 “ 緊湊 ” 也能消除碎片的一種 離散分配 技術(shù) 程序虛擬地址 （分頁） V1 V2 V3 Vn …… 物理主存 （分塊） P1 P2 Pm …… 頁表 P2 offset P3 V3 offset 虛擬頁 物理塊 其他信息 V1 P5 V2 P3 V3 P2 … … Vn Px 實分頁和虛分頁存儲管理方式 按程序運行時，是否要求全部調(diào)入內(nèi)存，可分為實分頁和虛分頁 兩種存儲管理方式。 ? 另外， 每次釋放內(nèi)存時都盡可能地合并伙伴單位的做法 也會降低系統(tǒng)性能，因為剛合并好的塊可能馬上又要對分。 ? 伙伴系統(tǒng)的主要問題 ? 最大缺陷 是不能有效地利用內(nèi)存，特別是“內(nèi)碎片”嚴(yán)重。 ? Linux維護(hù) 6個鏈表 ，對應(yīng)長為 1 32個頁幀的內(nèi)存塊。 伙伴系統(tǒng)示例 Action Memory Start 1M A請求 150kb A 256k 512k B請求 100kb A B 128k 512k C請求 50kb A B C 64k 512k 釋放 B A C 64k 512k D請求 200kb A C 64k D 256k E請求 60kb A C E D 256k 釋放 C A 64k E D 256k 釋放 A 256k 64k E D 256k 釋放 E 512k D 256k 釋放 D 1M 伙伴系統(tǒng) ? 伙伴系統(tǒng)數(shù)據(jù)結(jié)構(gòu) ? 系統(tǒng)要為每一種可能的空閑塊維護(hù) 1個空閑塊鏈表。 ? 伙伴系統(tǒng)的內(nèi)存分配過程 ? 如不能找到合適的空閑塊，則把一個最小的比該空閑塊大的空閑塊 對分成2個 “ 伙伴 ” 單位 ? 該對分過程可能會繼續(xù)，直到獲得合適的空閑塊為止。 ? 當(dāng) 1個進(jìn)程申請內(nèi)存時，系統(tǒng)就分給它 1個大于或等于進(jìn)程所申請尺寸的 最小的 2的冪次的空閑塊 。此時，原先的 5個空閑區(qū)依次裝入了 5個作業(yè)，它們是：Jb(15k)， Jd(26k)， Ja(10k)， Je(180k)和 Jc(102k)。因為內(nèi)存中 前兩個 原先的空閑分區(qū)能依次裝入 Ja(10k)和 Jb(15k)， 第 3個 10KB的空閑區(qū)和剛剛劃分出來的兩個大小分別為 5KB和 13KB的空閑區(qū)均無法分配， 第 4個空閑區(qū)可以分 2次裝入作業(yè) Jc(102k)和 Jd(26k)，則作業(yè) Je(180k)無法裝入內(nèi)存。現(xiàn)有五個作業(yè) Ja、 Jb、 Jc、 Jd和 Je，它們各需要內(nèi)存 10k、 15k、102k、 26k和 180k。 緊縮 ?消除了“外碎片” ?需要較大開銷，以“時間”換“空間” ?一般在 連續(xù)空閑區(qū)不滿足某個作業(yè)需求，而 空閑區(qū)之和能滿足要求時進(jìn)行。 （ 1） 最先 適應(yīng)分配算法 ?空閑分區(qū)表按 分區(qū)地址大小 以遞增順序排列 ?順序查找 空閑分區(qū)表，找到 第一個 滿足作業(yè)要求的空閑分區(qū) ?優(yōu)點 ：易于合并相鄰的空閑分區(qū)，盡可能 保留高地址端 的空閑分區(qū) ?缺點 ：搜索次數(shù)多，影響工作效率 三種主存分配算法 （ 2） 最佳 適應(yīng)分配算法 ?空閑分區(qū)表按 分區(qū)的大小 以遞增順序排列 ?找到 第一個 滿足作業(yè)要求的空閑分區(qū)，一定是 最小、且長度接近或合適作業(yè)要求 的空閑分區(qū) ?優(yōu)點 ：盡可能 保留較大 的空閑分區(qū) ?缺點 ：產(chǎn)生非常小的空閑分區(qū)（外碎片） 三種主存分配算法（續(xù)） （ 3） 最壞 適應(yīng)分配算法 ?空閑分區(qū)表按 分區(qū)的大小 以 遞減 順序排列 ?找到 第一個 滿足作業(yè)要求的空閑分區(qū)，一定是 最大 、且長度與作業(yè)要求 差別最大 的空閑分區(qū) ?優(yōu)點 ：分割后產(chǎn)生的空閑分區(qū)一般仍可供以后分配使用 ?缺點 ：工作一段時間后， 不能滿足大作業(yè) 對空閑分區(qū)的請求 主存空間的釋放 增加了合并相鄰空閑區(qū)的操作，主要是為了盡量及時簡單地減少“外碎片”。 主存分配： 尋找沒被占用且長度滿足進(jìn)程要求的空閑分區(qū)，并對其進(jìn)行“ 分割 ”。 事先 不分配 Job1 Job2,Job3 Job2完成 克服了固定分區(qū)管理的“ 內(nèi)碎片 ”問題，但