【正文】 1號體 2號體 3號體 a00 a01 a02 a03 a10 a11 a12 a13 a20 a21 a22 a23 a30 a31 a32 a33 按對角線訪問有沖突的存儲方案 0號體 1號體 2號體 3號體 a00 a01 a02 a03 a13 a10 a11 a12 a22 a23 a20 a21 a31 a32 a33 a30 31 虛擬存儲器 ? 虛擬存儲器概念的提出： 1961年英國曼徹斯特大學的 Kilbrn等人提出。 ? 虛擬存儲器：由主存儲器和聯(lián)機工作的外部存儲器共同組成。 ? 目的：解決主存容量不足的問題。 32 虛擬存儲器與高速緩存的區(qū)別 Cache 虛擬存儲器 功能 提高了主存儲器的速度 擴大了主存儲器的容量 實現(xiàn)技術(shù) 硬件 以軟件為主 透明性 透明 不透明 地址轉(zhuǎn)換 簡單 復雜、速度慢 33 虛擬存儲器工作原理 CPU 存儲 管理 主 存 輔 存 I或 D I或 D VA PA 外存地址 虛擬存儲器中 CPU、 MM、輔存間關(guān)系 34 幾個概念 ? 虛空間： 程序所能利用的空間 。 ? 實地址： 主存物理空間的編址 。 ? 虛地址： 編程序時程序員所用的地址 ， 在編譯程序中由處理機生成 。 實頁號 p 頁內(nèi)偏移 d 主存地址的組成 用戶號 U 頁內(nèi)偏移 D 多用戶虛擬地址的組成 虛頁號 P 35 虛擬存儲器工作工程 磁盤地址 (Head,cyle,sect) 外部地址變換 Uid Pv D 內(nèi)部地址變換 P m D 0頁 1頁 ? ? 1 2 ? p 頁 I/O 處理機 I/O 通道 可用主存頁號 替換算法 主存頁面表 AV(多用戶虛地址 ) 0頁 0頁 1頁 0頁 1 2 n 1 2 ? n 不 命 中 主存 頁面實效 主 存 未 滿 主存滿 rollin rollin out rollin out rollin 虛擬存儲器 選 頁 X 用 戶 Y 用 戶 命中時 主頁空間 36 虛擬存儲器的特點 1）多用戶多進程可以共享主存空間 每個用戶或進程具有獨立存儲空間，多用戶和進程共享較小的存儲空間 2）程序員不必管理存儲器 程序自動覆蓋 3）采用動態(tài)再定位，簡化程序的裝入 37 虛擬存儲器需要解決的四個問題 映象規(guī)則 由于輔存一般是磁盤，當不命中時，失效開銷非常大。所以盡可能提高命中率。虛擬存儲器均采用全相聯(lián)映象。 查找算法與地址轉(zhuǎn)換 ? 查找算法與虛擬存儲器的管理方式相關(guān)； ? 存在外部地址轉(zhuǎn)換。 替換算法 基本使用最久未使用算法 LFU。 寫策略 盡量減少寫入磁盤。采用寫回策略，既被替換時寫入磁盤，并使用改寫標志位（臟標志位），避免不必要的寫盤操作。 38 虛擬存儲器的管理方式 1. 段式管理 2. 頁式管理 3. 段頁式管理 39 （ 1） 段式虛擬存儲器 ? 段： 按程序的邏輯功能來劃分，一個用戶的程序 (或一個進程 )可以包含多個功能不同的程序段 ，段大小不等。 ? 地址映象： 將虛存空間分段，主存的空間按這種段來分配和管理 。 ? 地址轉(zhuǎn)換： 主存地址格式： 段號 段內(nèi)地址 虛存地址格式： 用戶號 段號 段地址 40 段式虛擬存儲器 ——地址映象 段號 段長 起始地址 0 1K 8K 1 500 16K 2 200 9K 3 200 30K 0段 1段 2段 3段 0 8K 9K 段表 程序空間 主存 41 段式虛擬存儲器 段表的記錄項數(shù)和虛存中的程序段數(shù)對應。 當一個段調(diào)入主存中時，將該段在主存的起始地址和段長填入段表的對應記錄項。 當一個段調(diào)入主存時，需要尋找能容納下該段的存儲空間（包括被替換的段）。 多次段調(diào)入，可能造成主存空間碎片。 注：不同于磁盤碎片；磁盤碎片僅影響存取速度，而段碎片不能使用，需要定時整理存儲空間。 每個用戶一個段表。多用戶系統(tǒng)需要一個用戶表，每個用戶一條記錄，記錄中的指針指向該用戶段表起始位地址。 42 段式虛擬存儲器 ——地址變換 段表基地址 段表長度 As 5 訪問方式 段長 裝入位 起始地址 段號 5 4 3 2 1 段內(nèi)偏移 D 段號 S 用戶號 U 主存實地址 ＋ ＋ 多用戶虛地址 一個用戶的段表 As 用戶表（段表基址寄存器） 43 段式虛擬存儲器 ——分析 ? 優(yōu)點： ? 程序模塊化的性能好，各段在功能上是相互獨立的； ? 便于程序與數(shù)據(jù)的共享； ? 程序的動態(tài)鏈接比較容易； ? 便于實現(xiàn)存儲保護。 ? 缺點： ? 地址變換所需的時間比較長。 ? 主存的空間利用不充分（存在碎片）。 ? 對輔存 (磁盤 )的管理比較困難（磁盤按扇區(qū)管理）。 44 （ 2）頁式虛擬存儲器 ? 頁： 將主存空間與虛存空間按固定的大小劃分成塊 ，每塊稱為一頁 。 ? 虛頁： 虛存中的頁； ? 實頁： 實存中的頁。 ? 虛頁與實頁之間按全相聯(lián)方式映象。 虛存地址格式： 虛頁號 頁內(nèi)地址 主存地址格式： 實頁號 頁內(nèi)地址 45 頁式虛擬存儲器 ——地址變換 頁表基地址 ps 各種標志 主存頁號 修改位 裝入位 p 1 頁內(nèi)偏移 D 頁號 S 用戶號 U 實頁號 p 頁內(nèi)偏移 D ＋ 多用戶虛地址 用戶表（頁表基址寄存器） 一個用戶的頁表 ps 46 頁式虛擬存儲器 ——分析 ? 優(yōu)點： ? 主存儲器的空間利用率比較高。 ? 頁表的管理比較簡單，可以不考慮程序的長短，按固定塊長分配，管理，調(diào)度。 ? 地址映象與地址轉(zhuǎn)換速度比較快。 ? 按頁的管理方式，與對輔存的地址格式是一致的，因而管理起來比較容易。 ? 缺點： ? 頁表占用很大的存儲空間。 ? 程序的模塊化性能不好 (頁大小固定，程序段長度變化）。 47 段頁式虛擬存儲器 ? 段頁式管理： 將虛擬存儲空間按段式管理，而主存空間按頁式管理，存在虛空間的程序按邏輯關(guān)系分段，每一段又可分成固定大小的頁。主存則只分成若干相同大小的頁。 虛存地址格式： 用戶號 段號 段內(nèi)虛頁號 頁內(nèi)地址 主存地址格式 ： 實頁號 頁內(nèi)地址 地址轉(zhuǎn)換： 需要三層表 ， 記錄相關(guān)信息 ， 包括 段表基地址表 、 段表 、 頁表 。 48 段頁式虛擬存儲器 ——地址變換 段表基地址 段表長度 As 6 頁表地址 頁表長 標志 修改位 裝入位 Ap 0/1 1 虛頁號 P 頁內(nèi)偏移 D 段號 S 用戶號 U ＋ 多用戶虛地址 一個用戶段表 各種標志 修改位 實頁號 裝入位 0/1 p 1 實頁號 p 頁內(nèi)偏移 D ＋ 一個段的頁表 Ap 主存地址 用戶表 49 段頁式虛擬存儲器 ——分析 注意： 1）段表和頁表一個記錄項對應虛存的一個虛段和虛頁。 2）段表和頁表均可按地址方式查找。（取決于表的長度按虛地址或?qū)嵉刂吩O置） 3）由于段表和頁表較大，一般設在主存。 4）多級查表導致的多次訪問主存，平均訪存時間很低 。 50 地址變換 ? 內(nèi)部地址映象：把虛擬地址空間映象到主存物理地址空間。 ? 內(nèi)部地址變換 ：把虛擬地址變換成實地址。 ? 外部地址變換 ：把虛擬地址變換成輔存的物理地址。 1) 當發(fā)生段或頁失效時，需要從外部輔存裝入此段或頁的內(nèi)容。需要將虛擬地址轉(zhuǎn)成輔存的物理地址，以便訪問輔存。 2）輔存的物理地址形式隨輔存的類型而異。一般不同于主存地址形式。 3）一般情況下，發(fā)生段或頁失效將引發(fā)中斷，通過調(diào)用中斷服務程序處理。 51 外部地址變換 ? 每一個用戶有一張外頁表。 ? 裝入位 =1，表示在 HD中，否則表示不在 HD中，可能在 CD中。 ? 用戶號經(jīng)過變換形成外頁表的起始地址。 用戶號U 虛擬號 P 頁內(nèi)偏移 D磁盤號 柱面 H ead 塊號外部地址變換(用軟件實現(xiàn))1裝入位 磁盤實地址外頁表52 中斷引發(fā)的問題： 當一條指令跨越兩個頁，讀取該指令一半時發(fā)生頁失效； 一條指令執(zhí)行過程中讀取數(shù)據(jù)發(fā)生頁失效； 正常情況下，一條指令執(zhí)行完成后響應中斷，但這里必須立即相應。 斷點和現(xiàn)場的確定和處理。 53 斷點和現(xiàn)場的處理： 注：這里的 斷點 可能是剛讀入或正在執(zhí)行的指令； 現(xiàn)場 可能還包括指令寄存器、譯碼器結(jié)果等。不同于Call及 int是兩個指令之間的現(xiàn)場） ① 采用 register,將現(xiàn)場全部保存到 register中。 ② 只保存部分現(xiàn)場，如 PSW， IC等，在 Page fault 后，從頭開始執(zhí)行這條指令。 ③ 采用指令預判技術(shù)，對于可能要產(chǎn)生 Page fault 的指令，先將其調(diào)入 RAM，才開始執(zhí)行該條指令。 54 地址變換存在的問題 ? 由于段式、頁式或段頁式虛擬存儲管理中 ,需要訪問 23次 RAM才能真正訪問到實際的存儲單元。 ? 當頁表和段表的容量超過一個頁面的大小時 ,就有可能被映象到主存儲器的不連續(xù)的頁面位置。此時再通過基址＋頁表＋偏移方法獲得主存頁號就會發(fā)生錯誤。即按照圖 Pagetable1頁的大小 (4KB ) 。 55 加快內(nèi)部地址變換的方法 采用多級頁表 系統(tǒng)頁表(目錄表 )任務1的列表任務n的列表?任務1的列表56 分析 ???????????dppvNNNNn2222l o gl o gl o gl o g 頁表的級數(shù)其中： Nv表示 VM的大小，即 Nv= size(VM) Np 表示頁面的大小 Nd 表示存儲字的大小 例： Nv=4GB,Np=4KB,Nd=4B(386/486體系結(jié)構(gòu)中 ) ① 為了節(jié)省存儲空間，通常是一級頁表常駐 RAM,二級頁表 /三級頁表只有少量常用的常駐內(nèi)存。 ②采用多級頁表固然解決了頁表容量超過一頁而造成地址計算錯誤的問題，但有時減慢了訪問存儲單元的速度。 ③ 為了提高訪問頁表的速度，采取以下三種解決方法 。 57 提高查表速度 ——方法一：目錄表 ? 一個目錄表項對應一個主存頁 采用基于內(nèi)容訪問的相聯(lián)存儲器 (圖 ) ? （同 Cache中的全相聯(lián)映象） 存在的不足： 當主存容量增加時，目錄表的容量也將增加，此時查表的速度將減慢，因此不利于提高訪存的速度。 58 提高查表速度 ——方法二：快慢表 ? 采用程序局部性原理，進一步縮小目錄表的存儲容量。例如： 816個頁目表項。而且這些目錄項的訪問速度與 CPU的通用 register 相當