第4章-存儲(chǔ)系統(tǒng)

計(jì)算機(jī)體系結(jié)構(gòu) 講授人 蔡娟 第四章存儲(chǔ)體系 3 1存儲(chǔ)系統(tǒng)的基本要求和并行主存系統(tǒng)4 1存儲(chǔ)體系的概念4 2虛擬存儲(chǔ)器4 3高速緩沖存儲(chǔ)器4 4Cache 主存 輔存三級(jí)層次4 5主存保護(hù) 第4章存儲(chǔ)體系 現(xiàn)代計(jì)算機(jī)系統(tǒng)都以存儲(chǔ)器為中心 在計(jì)算機(jī)運(yùn)行過(guò)程中 存儲(chǔ)器是各種信息存儲(chǔ)和交換的中心 3 1存儲(chǔ)系統(tǒng)的基本要求 3 1 1存儲(chǔ)系統(tǒng)的基本要求 存儲(chǔ)系統(tǒng)的基本要求 大容量 高速度和低價(jià)格 存儲(chǔ)器的主要性能 速度 容量 價(jià)格 速度 用存儲(chǔ)器的訪問(wèn)周期 讀出時(shí)間 頻帶寬度等表示 容量 用字節(jié)B 千字節(jié)KB 兆字節(jié)MB和千兆字節(jié)GB等單位表示價(jià)格 用單位容量的價(jià)格表示 如元 bit 存儲(chǔ)器容量SM 存儲(chǔ)器容量SM W L m 其中 W 為存儲(chǔ)體的字長(zhǎng) 單位是位或字節(jié) L 為存儲(chǔ)體的字?jǐn)?shù) m 為并行工作的存儲(chǔ)體數(shù) 速度可以用下面的參數(shù)表示 訪問(wèn)時(shí)間TA 是從存儲(chǔ)器從接收訪存讀申請(qǐng)至信息被讀到數(shù)據(jù)總線上的時(shí)間 這是處理機(jī)啟動(dòng)訪存后必須等待的時(shí)間 它是確定處理機(jī)與存儲(chǔ)器時(shí)間關(guān)系的一個(gè)重要參數(shù) 存儲(chǔ)時(shí)間TM 連續(xù)啟動(dòng)一個(gè)存儲(chǔ)體所需要的間隔時(shí)間 它一般比TA大 速度可以用下面的參數(shù)表示 頻寬 帶寬 Bm 是存儲(chǔ)器可提供的數(shù)據(jù)傳送速率 用每秒傳送的信息位數(shù)或字節(jié)數(shù)來(lái)衡量 最大頻寬 是存儲(chǔ)器連續(xù)訪問(wèn)時(shí)的頻寬 實(shí)際頻寬由于存儲(chǔ)器不一定能滿負(fù)荷工作 因此實(shí)際頻寬往往低于最大頻寬 價(jià)格可以用下面的參數(shù)表示 包含了存儲(chǔ)體以及為該存儲(chǔ)器操作所必需的外圍電路的價(jià)格 可用總價(jià)格C和每位價(jià)格c來(lái)表示 有SM位的存儲(chǔ)器每位價(jià)格c C SM 在計(jì)算機(jī)系統(tǒng)中 希望存儲(chǔ)器的速度能和CPU匹配 使得CPU的高性能能得以發(fā)揮 存儲(chǔ)器的價(jià)格 速度和容量的要求是相互沖突的 在存儲(chǔ)器件一定的條件下 容量越大 因其延遲增大 速度越低 容量越大 存儲(chǔ)器總價(jià)會(huì)越高 存儲(chǔ)器速度越高 價(jià)格越高 由于主存速度的改進(jìn)跟不上CPU的速度的提高 CPU與主存儲(chǔ)器的速度差距越來(lái)越大 從20世紀(jì)70年代起 在合理的成本下 足夠容量的主存其存儲(chǔ)周期已比CPU拍寬大了一個(gè)數(shù)量級(jí) 為了彌補(bǔ)與存儲(chǔ)器在速度行的差距 解決這一問(wèn)題的辦法之一就是引入并行和重疊技術(shù) 構(gòu)成并行主存系統(tǒng) 可以在每位價(jià)格不變的情況下 使主存的頻寬得到較大的提高 但是單靠這種并行主存的方法提高的頻寬是有限的 必須從系統(tǒng)結(jié)構(gòu)進(jìn)行上改進(jìn) 發(fā)展第4章中介紹的存儲(chǔ)體系是非常必要的 3 1 2并行主存系統(tǒng)1單體單字2單體多字3多體單字4多體多字并行主存系統(tǒng) 我們把能并行讀出多個(gè)CPU字的單體多字 多體單字和多體多字的交叉防衛(wèi)貯存系統(tǒng)統(tǒng)稱為并行主存系統(tǒng) 單體單字假設(shè)一個(gè)字長(zhǎng)為W位的單體主存 一次可以訪問(wèn)一個(gè)存儲(chǔ)器字 主存最大頻寬Bm W TM 假設(shè)存儲(chǔ)器字長(zhǎng)W與CPU所要訪問(wèn)的字 數(shù)據(jù)字或指令字 簡(jiǎn)稱CPU字 的字長(zhǎng)W相同 則CPU從主存獲得信息的速度為W TM 讀出寄存器 W位 地址寄存器 圖3 1單體單字存儲(chǔ)器 單體多字在一個(gè)存儲(chǔ)周期內(nèi)就可以讀出4個(gè)CPU字 相當(dāng)于CPU從主存中獲得信息的最大速率提高為原來(lái)的4倍 即頻寬Bm W 4 TM W位 地址寄存器 圖3 2單體多字 m 4 存儲(chǔ)器 1 4 W位 W位 W位 W位 單字長(zhǎng)寄存器 3多體單字CPU字在主存中可按模m交叉編址 根據(jù)應(yīng)用特點(diǎn) 這種交叉又分為高位交叉和低位交叉高位交叉訪問(wèn)存儲(chǔ)器主要目的 擴(kuò)大存儲(chǔ)器容量實(shí)現(xiàn)方法 用地址碼的高位區(qū)分存儲(chǔ)體號(hào)低位交叉訪問(wèn)存儲(chǔ)器主要目的 提高存儲(chǔ)器訪問(wèn)速度實(shí)現(xiàn)方法 用地址碼的低位區(qū)分存儲(chǔ)體號(hào) 1高位交叉訪問(wèn)存儲(chǔ)器主要目的 擴(kuò)大存儲(chǔ)器容量實(shí)現(xiàn)方法 用地址碼的高位區(qū)分存儲(chǔ)體號(hào)參數(shù)計(jì)算方法 l 每個(gè)存儲(chǔ)體的容量m 總共的存儲(chǔ)體個(gè)數(shù)i 存儲(chǔ)體的體內(nèi)地址 i 0 1 2 l 1j 存儲(chǔ)體的體號(hào) j 0 1 2 m 1存儲(chǔ)器的地址 A j l i存儲(chǔ)器的體內(nèi)地址 Ai Amodl存儲(chǔ)器的體號(hào) Aj 向下取整 A l MBR 存儲(chǔ)體0 MAR MBR 存儲(chǔ)體n 1 MAR MBR 存儲(chǔ)體1 MAR 譯碼器 高位 存儲(chǔ)器地址寄存器 低位 1 6 10 13 0 4 8 12 3 5 11 15 2 7 9 14 主存儲(chǔ)器數(shù)據(jù)寄存器 體內(nèi)地址 2位 模塊地址 2位 存貯體0 存貯體1 存貯體2 存貯體3 存儲(chǔ)器的地址 A j l i 存儲(chǔ)器的體號(hào) Aj 向下取整 A l 存儲(chǔ)器的體內(nèi)地址 Ai Amodl 2低位交叉訪問(wèn)存儲(chǔ)器主要目的 提高存儲(chǔ)器訪問(wèn)速度實(shí)現(xiàn)方法 用地址碼的低位區(qū)分存儲(chǔ)體號(hào)參數(shù)計(jì)算方法 存儲(chǔ)器地址A的計(jì)算公式為 A m i j存儲(chǔ)器的體內(nèi)地址 Ai 向下取整 A m 存儲(chǔ)器的體號(hào) Aj Amodm地址是編碼方法 由8個(gè)存儲(chǔ)體構(gòu)成的主存儲(chǔ)器的低位交叉編址方式 MBR 存儲(chǔ)體0 MAR MBR 存儲(chǔ)體n 1 MAR MBR 存儲(chǔ)體1 MAR 存儲(chǔ)器地址寄存器 高位 譯碼器 低位 8 9 12 13 14 15 0 1 2 3 4 5 6 7 24 31 16 23 32 39 40 47 48 55 56 63 主存儲(chǔ)器數(shù)據(jù)寄存器 體內(nèi)地址 3位 模塊地址 3位 10 11 m個(gè)存儲(chǔ)體分時(shí)啟動(dòng)實(shí)際上是一種采用流水線方式工作的并行存儲(chǔ)器理論上 存儲(chǔ)器的速度可望提高m倍每存儲(chǔ)體的啟動(dòng)間隔t為 其中 m為存儲(chǔ)體個(gè)數(shù)Tm為每個(gè)存儲(chǔ)體的訪問(wèn)周期 多體單字與單體多字的比較 多體單字的實(shí)際頻寬可以比較高 這是因?yàn)槎囿w單字只要m個(gè)地址不發(fā)生分體沖突 沒有發(fā)生兩個(gè)以上的地址屬于同一個(gè)分體 即使地址之間不是順序的 仍可以并行讀出來(lái) 而單體多字要想并行讀出的m個(gè)字必須是地址順序且處于同一主存單元 4多體多字把多體單字并行存取與單體多字相結(jié)合 構(gòu)成多體多字交叉存儲(chǔ)器 來(lái)進(jìn)一步的提高頻寬 提高模m值 是能提高主存系統(tǒng)的最大頻寬 但主存實(shí)際頻寬并不是隨m值增大而線形提高 即實(shí)際頻寬提高的并不像所希望的那樣高 原因 1實(shí)際程序中的指令不總是順序執(zhí)行的 一旦出現(xiàn)轉(zhuǎn)移 效率就會(huì)下降 2在工程實(shí)現(xiàn)上由于模m越高 存儲(chǔ)器數(shù)據(jù)總線越長(zhǎng) 總線上并聯(lián)的負(fù)載越重 有時(shí)還不得不增加門的級(jí)別 這會(huì)使傳輸延遲增加 4 1存儲(chǔ)體系的概念4 1 1存儲(chǔ)體系及其分支4 1 2存儲(chǔ)器的構(gòu)成依據(jù)4 1 3存儲(chǔ)體系的性能參數(shù) 4 1 1存儲(chǔ)體系及其分支在一臺(tái)計(jì)算機(jī)中 通常有多種存儲(chǔ)器種類 主存儲(chǔ)器 Cache 通用寄存器 先行緩沖存儲(chǔ)器 磁盤存儲(chǔ)器 磁帶存儲(chǔ)器 光盤存儲(chǔ)器等材料工藝 ECL TTL MOS 磁表面 激光 SRAM DRAM訪問(wèn)方式 直接譯碼 先進(jìn)先出 隨機(jī)訪問(wèn) 相聯(lián)訪問(wèn) 塊傳送 文件組 存儲(chǔ)器的層次結(jié)構(gòu)多個(gè)層次的存儲(chǔ)器 RegisterFiles Buffers Lookahead Cache MainMemory OnlineStorage Off lineStorage 訪問(wèn)速度越來(lái)越快 每位的價(jià)格越來(lái)越便宜存儲(chǔ)容量越來(lái)越大 CPU內(nèi)部 各級(jí)存儲(chǔ)器的主要性能特性 存儲(chǔ)器層次 通用寄存器 緩沖棧 Cache 存儲(chǔ)周期 10ns 10ns 10 60ns 存儲(chǔ)容量 512B 512B 8K 2MB 價(jià)格 c KB 1200 80 3 2 訪問(wèn)方式 直接譯碼 先進(jìn)先出 相聯(lián)訪問(wèn) 材料工藝 ECL ECL SRAM 分配管理 編譯器分配 硬件調(diào)度 硬件調(diào)度 帶寬 400 8000 400 1200 200 800 待續(xù) 各級(jí)存儲(chǔ)器的主要性能特性 續(xù) 存儲(chǔ)器層次 磁盤存儲(chǔ)器 主存儲(chǔ)器 存儲(chǔ)周期 10 30ms 60 300ns 存儲(chǔ)容量 1G 1TB 32M 1GB 價(jià)格 c KB 0 01 0 36 訪問(wèn)方式 塊訪問(wèn) 隨機(jī)訪問(wèn) 材料工藝 磁表面 DRAM 分配管理 系統(tǒng) 用戶 操作系統(tǒng) 帶寬 10 100 80 160 脫機(jī)存儲(chǔ)器 2 20min 5G 10TB 0 0001 文件組 磁 光等 系統(tǒng) 用戶 0 2 0 6 存儲(chǔ)系統(tǒng)的關(guān)鍵是如何組織好速度 容量和價(jià)格均不相同的存儲(chǔ)器 使這個(gè)存儲(chǔ)器的速度接近速度最快的那個(gè)存儲(chǔ)器 存儲(chǔ)容量與容量最大的那個(gè)存儲(chǔ)器相等 單位容量的價(jià)格接近最便宜的那個(gè)存儲(chǔ)器 1 存儲(chǔ)體系 存儲(chǔ)系統(tǒng) 存儲(chǔ)層次 的定義所謂存儲(chǔ)體系 就是讓構(gòu)成存儲(chǔ)系統(tǒng)的n種不同的存儲(chǔ)器 M1 Mn 之間 配上輔助軟 硬硬件或輔助硬件 使之從應(yīng)用程序員來(lái)看 它們?cè)谶壿嬌鲜且粋€(gè)整體 讓存儲(chǔ)層次的等效是接近于M1 Mn的 每位價(jià)格是接近于Mn的 這個(gè)系統(tǒng)對(duì)應(yīng)用程序員透明 并且 從應(yīng)用程序員看 它是一個(gè)存儲(chǔ)器 這個(gè)存儲(chǔ)器的速度接近速度最快的那個(gè)存儲(chǔ)器 存儲(chǔ)容量與容量最大的那個(gè)存儲(chǔ)器相等 單位容量的價(jià)格接近最便宜的那個(gè)存儲(chǔ)器 存儲(chǔ)體系的兩個(gè)不同的分支 在一般計(jì)算機(jī)系統(tǒng)中主要有兩種存儲(chǔ)系統(tǒng)虛擬存儲(chǔ)系統(tǒng) 由主存儲(chǔ)器和磁盤存儲(chǔ)器 輔存 構(gòu)成主要目的 擴(kuò)大存儲(chǔ)器容量Cache存儲(chǔ)系統(tǒng)由Cache和主存儲(chǔ)器構(gòu)成主要目的 提高存儲(chǔ)器速度 主存儲(chǔ)器 虛擬存儲(chǔ)系統(tǒng) 磁盤存儲(chǔ)器 從應(yīng)用程序員的角度看 速度接近主存儲(chǔ)器的速度容量是虛擬地址空間價(jià)格接近磁盤存儲(chǔ)器主存的訪問(wèn)時(shí)間約是磁盤的訪問(wèn)時(shí)間的105倍 虛擬存儲(chǔ)器 虛地址 在虛擬存儲(chǔ)器中 程序員可用機(jī)器指令的地址對(duì)整個(gè)程序統(tǒng)一編址 稱該地址為虛地址 程序地址 實(shí)地址 而把實(shí)際主存地址稱為實(shí)地址 實(shí)存地址 當(dāng)虛存空間 程序空間 遠(yuǎn)遠(yuǎn)大于實(shí)地址空間 實(shí)存空間 時(shí) 只需將程序空間分割成較小的段或頁(yè) 由系統(tǒng)程序按需要調(diào)入物理主存 并用輔助映射表建立其虛 實(shí)地址空間的對(duì)應(yīng)關(guān)系 在用虛地址訪問(wèn)主存時(shí) 由系統(tǒng)硬盤查看 這個(gè)虛地址所對(duì)應(yīng)的單元的內(nèi)容是否已裝入主存 如果在主存內(nèi) 就變換成主存實(shí)地址去訪問(wèn) 如果不在主存內(nèi) 就經(jīng)輔助軟 硬件將含所要訪問(wèn)的單元在內(nèi)的那個(gè)段 或頁(yè) 的程序塊由輔存調(diào)入主存 建立好映射關(guān)系 再進(jìn)行訪問(wèn) 不論虛 實(shí)地址的變換還是程序由輔存調(diào)入主存都不必由應(yīng)用程序員安排 即這些操作和輔助軟 硬件對(duì)應(yīng)用程序員來(lái)講是透明的 事實(shí)上 只要是存儲(chǔ)層次 這些都必須對(duì)應(yīng)用程序員是透明的 Cache Cache存儲(chǔ)系統(tǒng) 主存儲(chǔ)器 從系統(tǒng)程序員的角度看 速度接近Cache的速度存儲(chǔ)容量是主存的容量每位價(jià)格接近主存儲(chǔ)器 由于那個(gè)用CPU與主存的速度只差一個(gè)數(shù)量級(jí) 信息在Cache與主存之間的傳送就只能全部用輔助硬件實(shí)現(xiàn) 因此 Cache存儲(chǔ)器不僅對(duì)應(yīng)用程序員是透明的 而且對(duì)系統(tǒng)程序員也是透明的 由二級(jí)存儲(chǔ)層次可組合如下圖所示的多級(jí)存儲(chǔ)層次 并且希望從CPU看 速度接近最高層M1的速度 容量接近于最低層Mn的容量 價(jià)格接近于最低層Mn的每位價(jià)格 M1 TA1 S1 C1 從外部看 M2 TA2 S2 C2 Mn TAn Sn Cn T min TA1 TA2 TAn 用訪問(wèn)時(shí)間表示S max S1 S2 Sn 用MB或GB表示C min C1 C2 Cn 用每位的價(jià)格表示 4 1 2存儲(chǔ)體系的構(gòu)成依據(jù) 為了使存儲(chǔ)體系能有效地工作 當(dāng)CPU要用到某個(gè)地址的內(nèi)容時(shí) 總希望它已在速度最快的M1中 這就要求未來(lái)被訪問(wèn)信息的地址能預(yù)知 這對(duì)存儲(chǔ)體系的構(gòu)成是非常關(guān)鍵的 這種預(yù)知的可能性是基于計(jì)算機(jī)程序具有局部性 包括時(shí)間上的局部性和空間的局部性 時(shí)間上的局部性 在最近的未來(lái)要用到的信息很可能是現(xiàn)在正在使用的信息 這是因?yàn)槌绦虼嬖谘h(huán) 空間上的局部性 在最近的未來(lái)要用到的信息很可能與現(xiàn)在正在使用的信息在空間上是鄰近的 這是因?yàn)橹噶钔ǔＪ琼樞虼娣?順序執(zhí)行 數(shù)據(jù)通常是以向量 陣列 樹 表格等多種形式簇聚地存放 所以程序直轄市要用到的指令和數(shù)據(jù)是相對(duì)簇聚成自然的塊或頁(yè) 存儲(chǔ)器中較小的連續(xù)單元區(qū) 這樣 在一個(gè)由M1 M2組成的兩級(jí)存儲(chǔ)系統(tǒng)中 速度等于M1的速度 容量等于M2存儲(chǔ)器的容量 價(jià)格等于M2的價(jià)格 層級(jí)M1級(jí)不必存入整個(gè)程序 只需將近期使用過(guò)的塊或頁(yè) 根據(jù)時(shí)間的局部性 存入即可 在從M2級(jí)取所要訪問(wèn)字送M1時(shí) 一并把該字所在的塊或頁(yè)整個(gè)取來(lái) 根據(jù)空間的局部性 就能使要用的信息已在M1中的概率顯著增大 這就是存儲(chǔ)層次構(gòu)成的主要依據(jù) 預(yù)知的準(zhǔn)確性是存儲(chǔ)層次設(shè)計(jì)好壞的重要標(biāo)志 很大程度上取決于所用的算法和地址映射變換的方式 在虛擬存儲(chǔ)器中 一旦出現(xiàn)被訪問(wèn)的信息不在M1中時(shí) 原先申請(qǐng)?jiān)L存的程序就暫停執(zhí)行或被掛起 直至所需要的信息被調(diào)到M1為止 在Cache中 一旦出現(xiàn)被訪問(wèn)的信息不在M1中時(shí) 原先申請(qǐng)?jiān)L存的程序就暫停執(zhí)行 等待信息調(diào)入M1 為了縮短CPU空等的時(shí)間 讓CPU和Cache和主存都有直接通路 虛擬存儲(chǔ)器只能適用于多道程序 多用戶 的環(huán)境 Cache存儲(chǔ)器可以是單用戶也可以是多用戶環(huán)境 4 1 3存儲(chǔ)體系的性能參數(shù) 在一個(gè)由M1 M2組成的兩級(jí)存儲(chǔ)系統(tǒng)中 速度等于M1的速度 容量等于M2存儲(chǔ)器的容量 價(jià)格等于M2的價(jià)格 S2 S1時(shí) C C2 但S2與S1不能相差太大 存儲(chǔ)系統(tǒng)的單位容量平均價(jià)格計(jì)算公式 速度可以用下面的參數(shù)表示 訪問(wèn)時(shí)間TA 是從存儲(chǔ)器從接收訪存讀申請(qǐng)至信息被讀到數(shù)據(jù)總線上的時(shí)間 這是處理機(jī)啟動(dòng)訪存后必須等待的時(shí)間 它是確定處理機(jī)與存儲(chǔ)器時(shí)間關(guān)系的一個(gè)重要參數(shù) 存儲(chǔ)時(shí)間TM 連續(xù)啟動(dòng)一個(gè)存儲(chǔ)體所需要的間隔時(shí)間 它一般比TA大 速度可以用下面的參數(shù)表示 頻寬 帶寬 Bm 是存儲(chǔ)器可提供的數(shù)據(jù)傳送速率 用每秒傳送的信息位數(shù)或字節(jié)數(shù)來(lái)衡量 最大頻寬 是存儲(chǔ)器連續(xù)訪問(wèn)時(shí)的頻寬 實(shí)際頻寬由于存儲(chǔ)器不一定能滿負(fù)荷工作 因此實(shí)際頻寬往往低于最大頻寬 命中率H定義 CPU產(chǎn)生的邏輯地址在M1存儲(chǔ)器中訪問(wèn)到的概率R1 信息能在M1中的訪問(wèn)到的次數(shù)R2 信息能在M2中的訪問(wèn)到的次數(shù)顯然命中率H與程序的地址流 所采用的地址預(yù)判算法及M1的容量都有很多的關(guān)系 我們總希望命中率H越大越好 即H越接近于1越好 不命中率 失效率 是指CPU產(chǎn)生的邏輯地址在M1存儲(chǔ)器中訪問(wèn)不到的概率 對(duì)于二級(jí)存儲(chǔ)層次 不命中率為1 H 等效訪問(wèn)時(shí)間與命中率的關(guān)系 TA HTA1 1 H TA2當(dāng)命中率H 1時(shí) T TA1存儲(chǔ)系統(tǒng)的訪問(wèn)效率 存儲(chǔ)系統(tǒng)的訪問(wèn)效率主要與命中率和兩級(jí)存儲(chǔ)器的速度之比有關(guān) 例1 假設(shè)TA2 5TA1 在命中率H為0 9和0 99兩種情況下 分別計(jì)算存儲(chǔ)系統(tǒng)的訪問(wèn)效率 解 當(dāng)H 0 9時(shí) e1 1 0 9 5 1 0 9 0 72當(dāng)H 0 99時(shí) e2 1 0 99 5 1 0 99 0 96 提高存儲(chǔ)系統(tǒng)速度的兩條途徑 一是提高命中率H 二是兩個(gè)存儲(chǔ)器的速度不要相差太大 其中第二條有時(shí)做不到 如虛擬存儲(chǔ)器 主要依靠提高命中率 例3 2 在虛擬存儲(chǔ)系統(tǒng)中 兩級(jí)存儲(chǔ)器的速度相差特別懸殊TA2 105TA 如果要使訪問(wèn)效率e 0 9 問(wèn)需要有多高的命中率 解 0 9H 90000 1 H 189999 1H 89999得 H 0 999998888877777 0 999999 采用預(yù)取技術(shù)提高命中率方法 不命中時(shí) 把M2存儲(chǔ)器中相鄰幾個(gè)單元組成的一個(gè)數(shù)據(jù)塊都取出來(lái)送入M1存儲(chǔ)器中 計(jì)算公式 其中 H 是采用預(yù)取技術(shù)后的命中率 H是原來(lái)的命中率 n為數(shù)據(jù)塊大小與數(shù)據(jù)重復(fù)使用次數(shù)的乘積 證明 采用預(yù)取技術(shù)之后 不命中率降低n倍 也可以采用另外一種證明方法 在原有命中率計(jì)算公式中 把訪問(wèn)次數(shù)擴(kuò)大到n倍 這時(shí) 由于采用了預(yù)取技術(shù) 命中次數(shù)為 nN1 n 1 N2 不命中次數(shù)仍為N2 因此新的命中率為 例3 在一個(gè)Cache存儲(chǔ)系統(tǒng)中 當(dāng)Cache的塊大小為一個(gè)字時(shí) 命中率H 0 8 假設(shè)數(shù)據(jù)的重復(fù)利用率為5 計(jì)算塊大小為 個(gè)字時(shí) Cache存儲(chǔ)系統(tǒng)的命中率是多少 假設(shè)T2 5T1 分別計(jì)算訪問(wèn)效率 解 n 4 5 20 采用預(yù)取技術(shù)后 命中率提高到 Cache塊為1個(gè)字大時(shí) H 0 8 訪問(wèn)效率為 Cache塊為4個(gè)字大時(shí) H 0 99 訪問(wèn)效率為 例4 在一個(gè)虛擬存儲(chǔ)系統(tǒng)中 T2 105T 原來(lái)的命中率只有0 8 如果訪問(wèn)磁盤存儲(chǔ)器的數(shù)據(jù)塊大小為4K字 并要求訪問(wèn)效率不低于0 9 計(jì)算數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率至少為多少 解 假設(shè)數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率為m 根據(jù)前面的給出關(guān)系 解方程組得m 44 即數(shù)據(jù)在主存儲(chǔ)器中的重復(fù)利用率至少為44次 第4章存儲(chǔ)體系 現(xiàn)代計(jì)算機(jī)系統(tǒng)都以存儲(chǔ)器為中心在計(jì)算機(jī)運(yùn)行過(guò)程中 存儲(chǔ)器是各種信息存儲(chǔ)和交換的中心4 1存儲(chǔ)體系的概念4 2虛擬存儲(chǔ)器4 3高速緩沖存儲(chǔ)器4 4Cache 主存 輔存三級(jí)層次4 5主存保護(hù) 虛擬存儲(chǔ)器1961年英國(guó)曼徹斯特大學(xué)Kilbrn等人提出70年代廣泛地應(yīng)用于大中型計(jì)算機(jī)系統(tǒng)中目前許多微型機(jī)也開始使用虛擬存儲(chǔ)器1虛擬存儲(chǔ)器工作原理2地址的映象和變換方法3加快內(nèi)部地址變換速度的方法4頁(yè)面替換算法及其實(shí)現(xiàn)方法5提高主存命中率的方法 內(nèi)部地址變換 多用戶虛擬地址變換成主存實(shí)地址 外部地址變換 首先查外頁(yè)表得到磁盤存儲(chǔ)器實(shí)地址把磁盤存儲(chǔ)器實(shí)地址和主存儲(chǔ)器實(shí)頁(yè)號(hào)送入輸入輸出處理機(jī) 把要訪問(wèn)數(shù)據(jù)所在的一整頁(yè)都從磁盤存儲(chǔ)器調(diào)入到主存儲(chǔ)器 1地址的映象與變換三種地址空間 虛擬地址空間 主存儲(chǔ)器地址空間 輔存地址空間地址映象 把虛擬地址空間映象到主存地址空間地址變換 在程序運(yùn)行時(shí) 把虛地址變換成主存實(shí)地址因地址映象和變換方法不同 有三種虛擬存儲(chǔ)器 段式虛擬存儲(chǔ)器 頁(yè)式虛擬存儲(chǔ)器 段頁(yè)式虛擬存儲(chǔ)器 2虛擬存儲(chǔ)器工作原理 1 段式虛擬存儲(chǔ)器地址映象方法 根據(jù)程序的模塊性 每個(gè)程序段都是一個(gè)單獨(dú)的程序段 每個(gè)程序段都從0地址開始編址 長(zhǎng)度可長(zhǎng)可短 可以在程序執(zhí)行過(guò)程中動(dòng)態(tài)改變程序段的長(zhǎng)度 主存按段分配的存儲(chǔ)管理方式稱為段式管理方式 為了進(jìn)行段式管理 每道程序在系統(tǒng)中都有一個(gè)段表 映射表 用以存放該道程序段裝入主存的狀況信息 段表中的每一項(xiàng) 對(duì)應(yīng)表中的每一行 用來(lái)描述該道程序的一個(gè)程序段的基本信息 假設(shè)一個(gè)系統(tǒng)中最多可同時(shí)有N道程序在主存中 為此可以設(shè)置N個(gè)段表基址寄存器 對(duì)應(yīng)于每道程序 由基號(hào)指明使用哪個(gè)段表基址寄存器段表基址寄存器中的段表基址字段指向該道程序的段表在主存中的起始地址 段表長(zhǎng)度字段指明該道程序所用段表的行數(shù) 即程序段的段數(shù) 主程序 0段 1k 1段 2段 3段 0 500 0 200 0 200 0 段號(hào) 段長(zhǎng) 起址 0 1k 8k 1 500 16k 2 200 9k 3 200 30k 0 8k 9k 16k 30k 程序空間 主存儲(chǔ)器 基號(hào) 程序號(hào) 段號(hào)段內(nèi)位移 用戶號(hào)U 段號(hào)S 段內(nèi)偏移D 多用戶虛地址 0 段表長(zhǎng)度 段表基址 6 As 段名 起始地址 裝入位 段長(zhǎng) 訪問(wèn)方式 用戶號(hào)U 段號(hào)S 段內(nèi)偏移D 多用戶虛地址 主存實(shí)地址 4 3 2 1 0 1 n 1 As 段表基址寄存器 一個(gè)用戶 一道作業(yè) 的段表 段式虛擬存儲(chǔ)器地址變換方法 由用戶號(hào)找到基址寄存器從基址寄存器中讀出段表的起始地址把起始地址與多用戶虛地址中段號(hào)相加得到段表地址把段表中給出的起始地址與段內(nèi)偏移D相加就能得到主存實(shí)地址 段式虛擬存儲(chǔ)器的主要優(yōu)點(diǎn) 1 程序的模塊化性能好 2 分段便于幾道程序共享已在主存的程序和數(shù)據(jù) 3 分段方法能使大程序分模塊編制 從而可以多個(gè)程序員并行編程 從而縮短編程時(shí)間 在執(zhí)行或編譯過(guò)程種對(duì)不斷變化得可變長(zhǎng)段也便于處理 便于修改 增添 4 由于各段式按其邏輯特點(diǎn)組合的 容易以段為單位實(shí)現(xiàn)存儲(chǔ)保護(hù) 便于實(shí)現(xiàn)信息保護(hù) 段式虛擬存儲(chǔ)器的主要缺點(diǎn) 1 地址變換所花費(fèi)的時(shí)間比較長(zhǎng) 做兩次加法運(yùn)算 2 主存儲(chǔ)器的利用率往往比較低 3 對(duì)輔存 磁盤存儲(chǔ)器 的管理比較困難 為了進(jìn)行段式管理 處理系統(tǒng)需要為每道程序分別設(shè)置段映射表外 還得由操作系統(tǒng)為整個(gè)主存系統(tǒng)建立一個(gè)實(shí)主存管理表 它包括占用區(qū)域表和可用區(qū)域表兩部分 占用區(qū)域表的每一行 用來(lái)指明主存中哪些區(qū)域已被占用 被哪道程序得哪個(gè)段占用以及該段在主存的起點(diǎn)和長(zhǎng)度 以及可以設(shè)置如該段是否進(jìn)入主存后被改寫過(guò)的字段 以便該段由主存中釋放時(shí) 決定是否還要將其寫回輔存中原先得位置來(lái)減少輔存得操作 可用區(qū)域表得每一行 則指明每一個(gè)未被占用區(qū)的基地址和區(qū)域大小 當(dāng)一個(gè)段從輔存裝入主存時(shí) 操作系統(tǒng)就在占用區(qū)域表中增加一項(xiàng) 并修改可用區(qū)域表 當(dāng)一個(gè)段從主存中退出時(shí) 就將其在占用區(qū)域表中行移入可用區(qū)域表中 并進(jìn)行有關(guān)它是否可與其他可用區(qū)歸并處理 并修改可用區(qū)域表 當(dāng)某道程序全部執(zhí)行完畢結(jié)束或是被優(yōu)先級(jí)級(jí)別更高的程序所取代時(shí) 也應(yīng)將該道程序的全部段的行從占用區(qū)域表移入可用區(qū)域表并作相應(yīng)的處理 在段式虛擬管理方式中 正因?yàn)楦鞫蔚拈L(zhǎng)度不相同 所以通?？梢圆捎?首次分配 算法或 最佳分配 算法對(duì)實(shí)存可用區(qū)進(jìn)行分配 首次分配算法 首次分配算法順序掃視可用區(qū)域表 當(dāng)找到第一個(gè)不小于要調(diào)入段長(zhǎng)度的可用區(qū)時(shí) 就立即進(jìn)行分配 最佳分配算法 最佳分配算法則先掃視全部可用區(qū)域表 然后尋找一個(gè)可用區(qū)進(jìn)行分配 使之分配后段間可用區(qū)零頭最小 兩種算法的比較 兩種算法各有優(yōu)缺點(diǎn) 首次分配算法的分配速度快 而且由于首先分配主存地址的低區(qū) 造成可用區(qū)零頭數(shù)少 同時(shí)容易在主存高區(qū)保留大的可用區(qū) 以容納大的程序段 最佳分配算法雖然考慮了盡量減少每一段間可用區(qū)的零頭 但會(huì)使段間可用區(qū)零頭數(shù)較多 一旦頻繁請(qǐng)求分配的段長(zhǎng)都較大時(shí) 可能會(huì)出現(xiàn)沒有一個(gè)可用區(qū)的零頭可以容納下要求的調(diào)入段 而采用首次分配則可以裝入 主存程序主存 a 需依次調(diào)入 b 首次分配算法D E F段 A D B 0 5k 0 3k 7k 8k 10k C E F 1k 2 5k 2k 0 5k 0 3k 7k 8k 10k D E 6 5k B F C A 2 頁(yè)式虛擬存儲(chǔ)器主要優(yōu)點(diǎn) 1 主存儲(chǔ)器的利用率比較高 2 頁(yè)表相對(duì)比較簡(jiǎn)單 3 地址變換的速度比較快 4 便于存儲(chǔ)管理和減少段間零頭的浪費(fèi) 主要缺點(diǎn) 1 程序的模塊化性能不好 2 頁(yè)表很長(zhǎng) 需要占用很大的存儲(chǔ)空間 例如 虛擬存儲(chǔ)空間4GB 頁(yè)大小1KB 則頁(yè)表的容量為4M字 16MB 2頁(yè)式存儲(chǔ)器工作原理把主存儲(chǔ)器 磁盤存儲(chǔ)器和程序空間都機(jī)械等分成固定大小的頁(yè) 頁(yè)面大小隨機(jī)器而異 實(shí)頁(yè) 主存儲(chǔ)器的頁(yè)稱為實(shí)頁(yè) 一個(gè)主存地址np由兩部分組成 實(shí)頁(yè)號(hào)nv和頁(yè)內(nèi)偏移nr虛頁(yè) 虛擬存儲(chǔ)器中的頁(yè)稱為虛頁(yè) 一個(gè)虛地址Ns由三部分組成 用戶號(hào)U 虛頁(yè)號(hào)N v和頁(yè)內(nèi)偏移Nr 虛頁(yè)號(hào)N v 頁(yè)內(nèi)偏移Nr 頁(yè)內(nèi)偏移nr 實(shí)頁(yè)號(hào)nv 用戶號(hào)U 系統(tǒng)設(shè)置相應(yīng)的頁(yè)表 映射 表 保存虛頁(yè)裝入實(shí)頁(yè)時(shí)的頁(yè)面對(duì)應(yīng)關(guān)系 就可以由給頂?shù)某绦?虛 地址查頁(yè)表變換成相應(yīng)的實(shí) 主 存地址 而訪問(wèn)主存 由于虛存和實(shí) 存 的頁(yè)面大小一樣 所以頁(yè)表中只需記錄虛頁(yè)號(hào)N v和實(shí) 主 存頁(yè)號(hào)nv的對(duì)應(yīng)關(guān)系即可 不用保存頁(yè)內(nèi)位移 由虛地址查頁(yè)表變換成實(shí)地址的過(guò)程中 頁(yè)式管理只需要將主存實(shí)頁(yè)號(hào)與頁(yè)內(nèi)位移拼裝在一起 跟段式管理方式相比 可以大大加快地址變換的速度 也利于提高形成實(shí)地址的可靠性 假設(shè)一個(gè)系統(tǒng)中最多可同時(shí)有N道程序在主存中 對(duì)每道程序都由一個(gè)頁(yè)表 由用戶號(hào)U指明該道程序使用那個(gè)頁(yè)表基址寄存器 從而可以找到該道程序的頁(yè)表在主存中的起點(diǎn) 在程序裝入和運(yùn)行過(guò)程中 頁(yè)表基址寄存器和頁(yè)表的內(nèi)容全部由存儲(chǔ)層次來(lái)完成置定和修改 對(duì)用戶完全透明 為了對(duì)整個(gè)主存空間進(jìn)行管理 與段式類似 頁(yè)式管理方式中 系統(tǒng)還設(shè)置專門的主存頁(yè)面管理表 以指明主存中每個(gè)頁(yè)面位置的使用情況及其他信息 注意主存頁(yè)面 管理 表與頁(yè)表的區(qū)別兩者相同點(diǎn) 都是存儲(chǔ)于主存 區(qū)別 1 目的不同 主存頁(yè)面表是操作系統(tǒng)為了實(shí)現(xiàn)主存管理而設(shè)置的 其中每一行用來(lái)記錄主存中各頁(yè)的使用狀況的 而頁(yè)表是用來(lái)存儲(chǔ)映象關(guān)系和實(shí)現(xiàn)地址變換的 2 對(duì)象不同主存頁(yè)面表是對(duì)主存而言的 整個(gè)主存只有一個(gè) 而頁(yè)表是對(duì)用戶程序空間而言的 每道程序都有一個(gè) 頁(yè)表的介紹 虛頁(yè)號(hào)與頁(yè)表的行號(hào)是對(duì)應(yīng)的 不用設(shè)置專門的虛頁(yè)號(hào)字段 由于頁(yè)面大小固定 頁(yè)長(zhǎng)字段頁(yè)省了 這樣簡(jiǎn)化了映象表硬件 也利于加快查表 頁(yè)表也必須設(shè)置裝入位字段以表示該頁(yè)是否已裝入主存 當(dāng)裝入位為 1 時(shí) 實(shí)頁(yè)號(hào)字段中的內(nèi)容才是有效的 否則無(wú)效 為了方便存儲(chǔ)保護(hù) 頁(yè)表中也可以設(shè)置相應(yīng)的訪問(wèn)方式等字段 0頁(yè) 1頁(yè) 2頁(yè) 3頁(yè) 頁(yè)號(hào) 主存頁(yè)號(hào) 0 1 2 3 用戶程序 主存儲(chǔ)器 頁(yè)表 頁(yè)式虛擬存儲(chǔ)器的地址映象 Pa 裝入 修改 主存頁(yè)號(hào) 標(biāo)志 用戶號(hào)U 虛頁(yè)號(hào)N v 頁(yè)內(nèi)偏移Nr 頁(yè)內(nèi)偏移nr 2 p Pa 頁(yè)表基址 頁(yè)表 實(shí)頁(yè)號(hào)nv 3 段頁(yè)式虛擬存儲(chǔ)器用戶按照程序段來(lái)編寫程序 每個(gè)程序段分成幾個(gè)固定大小的頁(yè) 地址變換方法 1 先查段表 得到該程序段的頁(yè)表起始地址和頁(yè)表長(zhǎng)度 2 再查頁(yè)表找到要訪問(wèn)的主存實(shí)頁(yè)號(hào) 3 最后把實(shí)頁(yè)號(hào)p與頁(yè)內(nèi)偏移d拼接得到主存的實(shí)地址 裝入 修改 實(shí)頁(yè)號(hào) 標(biāo)志 用戶號(hào)U 段號(hào)S 頁(yè)內(nèi)偏移d 頁(yè)內(nèi)偏移 0 1 1 p A 實(shí)頁(yè)號(hào)p 虛頁(yè)號(hào)P As 裝入 1 修改 0 1 頁(yè)表地址 Ap As 造成虛擬存儲(chǔ)器速度降低的主要原因 1 要訪問(wèn)主存儲(chǔ)器須先查段表或頁(yè)表 2 可能需要多級(jí)頁(yè)表頁(yè)表級(jí)數(shù)的計(jì)算公式 假設(shè)程序虛地址為24位 其中頁(yè)內(nèi)地址Nr 10位 即程序虛地址 則頁(yè)表需要2N v行 即214行 而頁(yè)面大小只有2Nr 210 因此頁(yè)表本身需要分存在16 24 個(gè)頁(yè)面 所以要建立多級(jí)頁(yè)表 用頁(yè)表基址寄存器指明第一級(jí)頁(yè)表的基址 用第一級(jí)頁(yè)表中的各行的地址字段指明第二級(jí)各個(gè)頁(yè)表的基址 以此類推 用樹的概念很容易得出這種頁(yè)表級(jí)數(shù)i和N vNr之間的關(guān)系 虛頁(yè)號(hào)N v 14位 頁(yè)內(nèi)偏移Nr 10位 頁(yè)表級(jí)數(shù)的計(jì)算公式 其中 Nr為頁(yè)面的大小N v為虛擬存儲(chǔ)空間大小如果頁(yè)表中每一行需要Be個(gè)編址單位 而Be是2的冪 則Be需要Ne log2Be個(gè)地址位來(lái)表示 則例如 虛擬存儲(chǔ)空間大小N v 26位 則映射表中每一行需要2個(gè)字節(jié) 即Ne 1 Nr 10 所以表的級(jí)數(shù)為 外部地址變換在操作系統(tǒng)中 把頁(yè)面失效當(dāng)作一種異常故障來(lái)處理 每個(gè)用戶程序都有一張外頁(yè)表 虛擬地址空間中的每一頁(yè)或每個(gè)程序段 在外頁(yè)表中都有對(duì)應(yīng)的一個(gè)存儲(chǔ)字 每一個(gè)存儲(chǔ)字除了磁盤存儲(chǔ)器的地址之外 至少還包括一個(gè)裝入位 裝入 磁盤實(shí)地址 用戶號(hào) 頁(yè)內(nèi)偏移 1 虛頁(yè)號(hào) 外部地址變換 軟件實(shí)現(xiàn) 磁盤號(hào) 柱面號(hào) 磁頭號(hào) 塊號(hào) 多用戶虛地址 外頁(yè)表 3加快內(nèi)部地址變換的方法 造成虛擬存儲(chǔ)器速度降低的主要原因 1 要訪問(wèn)主存儲(chǔ)器須先查段表或頁(yè)表 2 可能需要多級(jí)頁(yè)表頁(yè)表級(jí)數(shù)的計(jì)算公式 假設(shè)程序虛地址為24位 其中頁(yè)內(nèi)地址Nr 10位 即程序虛地址 則頁(yè)表需要2N v行 即214行 而頁(yè)面大小只有2Nr 210 因此頁(yè)表本身需要分存在16 24 個(gè)頁(yè)面 所以要建立多級(jí)頁(yè)表 用頁(yè)表基址寄存器指明第一級(jí)頁(yè)表的基址 用第一級(jí)頁(yè)表中的各行的地址字段指明第二級(jí)各個(gè)頁(yè)表的基址 以此類推 用樹的概念很容易得出這種頁(yè)表級(jí)數(shù)i和N vNr之間的關(guān)系 虛頁(yè)號(hào)N v 14位 頁(yè)內(nèi)偏移Nr 10位 3加快內(nèi)部地址變換的方法 頁(yè)表級(jí)數(shù)的計(jì)算公式 其中 Nr為頁(yè)面的大小N v為虛擬存儲(chǔ)空間大小如果頁(yè)表中每一行需要Be個(gè)編址單位 而Be是2的冪 則Be需要Ne log2Be個(gè)地址位來(lái)表示 則例如 虛擬存儲(chǔ)空間大小N v 26位 則映射表中每一行需要2個(gè)字節(jié) 即Ne 1 Nr 10 所以表的級(jí)數(shù)為 計(jì)算得到頁(yè)表的級(jí)數(shù) 3 即除了段表 頁(yè)表二級(jí)表還不夠 而必須采用三級(jí)表 通常在段頁(yè)式虛擬存儲(chǔ)器存儲(chǔ)器上運(yùn)行程序時(shí) 為了節(jié)省存放映象表的主存空間 通常只將1級(jí)頁(yè)表駐留在主存儲(chǔ)器中 其他各級(jí)頁(yè)表則需要才調(diào)入 大部分仍放在輔存中 1 目錄表基本思想 用一個(gè)小容量高速存儲(chǔ)器存放頁(yè)表 把頁(yè)表壓縮成只存放已裝入主存的那些虛頁(yè) 用基號(hào)b和N v與實(shí)頁(yè)位置 nv 的對(duì)應(yīng)關(guān)系 地址變換過(guò)程 把多用戶虛地址中b與Nv 拼接起來(lái) 相聯(lián)訪問(wèn)目錄表 讀出主存實(shí)頁(yè)號(hào)nv 把nv與多用戶虛地址中的Nr拼接得到主存實(shí)地址 如果相聯(lián)訪問(wèn)失敗 發(fā)出頁(yè)面失效請(qǐng)求 訪問(wèn)方式不同 按內(nèi)容訪問(wèn)相聯(lián)訪問(wèn)按地址訪問(wèn)的隨機(jī)訪問(wèn) 實(shí)頁(yè)號(hào) 其它標(biāo)志 基號(hào)b 頁(yè)內(nèi)偏移Nr nv 虛頁(yè)號(hào)Nv 多用戶虛地址 目錄表 按內(nèi)容訪問(wèn)的相聯(lián)存儲(chǔ)器 頁(yè)內(nèi)偏移nr Nr 實(shí)頁(yè)號(hào)nv 多用戶虛頁(yè)號(hào) b Nv 修改 0 1 主存實(shí)地址 相聯(lián)訪問(wèn) 主要優(yōu)點(diǎn) 與頁(yè)表放在主存中相比 查表速度快 主要缺點(diǎn) 可擴(kuò)展性比較差 主存儲(chǔ)器容量增加時(shí) 目錄表的造價(jià)高 速度降低 2 快慢表快表TLB TranslationLookasideBuffer 小容量 幾 幾十個(gè)字 高速硬件實(shí)現(xiàn) 采用相聯(lián)方式訪問(wèn)慢表 當(dāng)快表中查不到時(shí) 從存放在主存儲(chǔ)器中的慢表中查找按地址訪問(wèn) 用軟件實(shí)現(xiàn) 快表與慢表也構(gòu)成了一個(gè)兩級(jí)存儲(chǔ)系統(tǒng) 實(shí)頁(yè)號(hào) 用戶號(hào)U 頁(yè)內(nèi)偏移D p 虛頁(yè)號(hào)P 多用戶虛地址 快表 按內(nèi)容相聯(lián)訪問(wèn) 頁(yè)內(nèi)偏移d 實(shí)頁(yè)號(hào)p 多用戶虛頁(yè)號(hào) U P 主存實(shí)地址 實(shí)頁(yè)號(hào) p 裝入 1 慢表 3 散列函數(shù)目的 把相聯(lián)訪問(wèn)變成按地址訪問(wèn) 從而加大快表容量散列 Hashing 函數(shù) Ah H Pv 20位左右 5 8位采用散列變換實(shí)現(xiàn)快表按地址訪問(wèn)避免散列沖突 采用相等比較器地址變換過(guò)程 相等比較與訪問(wèn)存儲(chǔ)器同時(shí)進(jìn)行 實(shí)頁(yè)號(hào) 用戶號(hào)U 頁(yè)內(nèi)偏移D p 虛頁(yè)號(hào)P 多用戶虛地址 按地址訪問(wèn)的快表 頁(yè)內(nèi)偏移d 實(shí)頁(yè)號(hào)p 多用戶虛頁(yè)號(hào) Pv 主存實(shí)地址 散列變換 硬件實(shí)現(xiàn) 相等比較 多用戶虛頁(yè)號(hào) 查慢表 快表地址 Ah 快表命中 5 虛擬存儲(chǔ)器舉例例子 IMB370 168計(jì)算機(jī)的虛擬存儲(chǔ)器快表結(jié)構(gòu)及地址變換過(guò)程 虛擬地址長(zhǎng)36位 頁(yè)面大小為4KB 每個(gè)用戶最多占用4K個(gè)頁(yè)面 最多允許16G個(gè)用戶 但同時(shí)上機(jī)的用戶數(shù)一般不超過(guò)6個(gè) 采用了兩項(xiàng)新的措施 一是采用兩個(gè)相等比較器二是用相聯(lián)寄存器組把24位用戶號(hào)U壓縮成3位 4頁(yè)面替換算法及其實(shí)現(xiàn)方法頁(yè)面替換發(fā)生時(shí)間 當(dāng)發(fā)生頁(yè)面失效時(shí) 要從磁盤中調(diào)入一頁(yè)到主存 如果主存所有頁(yè)面都已經(jīng)被占用 必須從主存儲(chǔ)器中淘汰掉一個(gè)不常使用的頁(yè)面 以便騰出主存空間來(lái)存放新調(diào)入的頁(yè)面 評(píng)價(jià)頁(yè)面替換算法好壞的標(biāo)準(zhǔn) 一是命中率要高二是算法要容易實(shí)現(xiàn) 頁(yè)面替換算法的使用場(chǎng)合 1 虛擬存儲(chǔ)器中 主存頁(yè)面的替換 一般用軟件實(shí)現(xiàn) 2 Cache塊替換一般用硬件實(shí)現(xiàn) 3 虛擬存儲(chǔ)器的快慢表中 快表存儲(chǔ)字的替換 用硬件實(shí)現(xiàn) 4 虛擬存儲(chǔ)器中 用戶基地址寄存器的替換 用硬件實(shí)現(xiàn) 5 在有些虛擬存儲(chǔ)器中目錄表的替換1 頁(yè)面替換算法 1 隨機(jī)算法 RANDRandomalgorithm 算法簡(jiǎn)單 容易實(shí)現(xiàn) 沒有利用歷史信息 沒有反映程序的局部性 命中率低 2 先進(jìn)先出算法 FIFOFirst InFirst Outalgorithm 比較容易實(shí)現(xiàn) 利用了歷史信息 沒有反映程序的局部性 最先調(diào)入主存的頁(yè)面 很可能也是經(jīng)常要使用的頁(yè)面 3 近期最少使用算法 LFULeastFrequentlyUsedalgorithm 既充分利用了歷史信息 又反映了程序的局部性 實(shí)現(xiàn)起來(lái)非常困難 4 最久沒有使用算法 LRULeastRecentlyUsedalgorithm 把LRU算法中的 多 與 少 簡(jiǎn)化成 有 與 無(wú) 實(shí)現(xiàn)起來(lái)比較容易 5 最優(yōu)替換算法 OPTOPTimalreplacemantalgorithm 是一種理想化的算法 用來(lái)作為評(píng)價(jià)其它頁(yè)面替換算法好壞的標(biāo)準(zhǔn) 在虛擬存儲(chǔ)器中 實(shí)際上有可能采用只有FIFO和LRU兩種算法 例8 一個(gè)程序共有5個(gè)頁(yè)面組成 程序執(zhí)行過(guò)程中的頁(yè)地址流如下 1 2 1 5 4 1 3 4 2 4假設(shè)分配給這個(gè)程序的主存儲(chǔ)器共有3個(gè)頁(yè)面 給出FIFO LRU OPT三種頁(yè)面替換算法對(duì)這3頁(yè)主存的使用情況 包括調(diào)入 替換和命中等 例9 一個(gè)程序共有5個(gè)頁(yè)面組成 程序執(zhí)行過(guò)程中的頁(yè)地址流如下 2 3 2 1 5 2 4 5 3 2 5 2假設(shè)分配給這個(gè)程序的主存儲(chǔ)器共有3個(gè)頁(yè)面 給出FIFO LRU OPT三種頁(yè)面替換算法對(duì)這3頁(yè)主存的使用情況 包括調(diào)入 替換和命中等 命中率與頁(yè)地址流也有關(guān)系 例如一個(gè)循環(huán)程序當(dāng)所需頁(yè)數(shù)大于分配給它的主存頁(yè)數(shù)時(shí) 無(wú)論是FIFO算法還是LRU算法的命中率都明顯低于OPT算法 命中率還與分配給程序的實(shí)頁(yè)數(shù)有關(guān)系 這個(gè)題目將實(shí)頁(yè)數(shù)增加1頁(yè) 命中率就都增大到4次 例10 一個(gè)循環(huán)程序 依次使用1 2 3 4四個(gè)頁(yè)面 分配給這個(gè)程序的主存頁(yè)面數(shù)為3個(gè) FIFO LRU和OPT三種頁(yè)面替換算法對(duì)主存頁(yè)面的調(diào)度情況如下圖所示 在FIFO和LRU算法中 總是發(fā)生下次就要使用的頁(yè)面本次被替換出去的情況 這就是 顛簸 現(xiàn)象 命中率還與分配給程序的實(shí)頁(yè)數(shù)有關(guān)系 這個(gè)題目將實(shí)頁(yè)數(shù)增加1頁(yè) 命中率就都增大到4次 一般來(lái)說(shuō) 分配給程序的主存頁(yè)數(shù)越多 虛頁(yè)裝入主存的機(jī)會(huì)就越大 命中率就可能提高 但是否能提高命中率還和算法有關(guān)系 例如FIFO算法就不一定符合這個(gè)規(guī)律 例11 一個(gè)程序共有5個(gè)頁(yè)面組成 程序執(zhí)行過(guò)程中的頁(yè)地址流如下 1 2 3 4 1 2 5 1 2 3 4 5假設(shè)分配給這個(gè)程序的主存儲(chǔ)器有3個(gè)頁(yè)面n 3和分配給這個(gè)程序的主存儲(chǔ)器有4個(gè)頁(yè)面n 4 的時(shí)候FIFO算法對(duì)主存的使用情況 對(duì)于FIFO算法分配 主存頁(yè)數(shù)由3頁(yè)增到4頁(yè) 命中率而由3 12下降到2 12 而LRU算法則不會(huì)出現(xiàn)這種情況 隨著分配給程序主存的頁(yè)數(shù)的增加 命中率一般都能提高 至少不下降 因此從衡量替換算法好壞的命中率高低來(lái)考慮 如果對(duì)影響命中率的主存頁(yè)數(shù)n取不同的值都模擬一次 工作量非常大 于是提出了使用堆棧技術(shù)處理的分析模型 它適用于采用堆棧型替換算法的系統(tǒng) 可以大大減少模擬的工作量 2 堆棧型替換算法假設(shè)A是長(zhǎng)度為L(zhǎng)的任意一個(gè)頁(yè)地址流 t為已處理過(guò)t 1個(gè)頁(yè)面的時(shí)間點(diǎn) n為分配給該地址流的主存頁(yè)數(shù) Bt n 表示在t時(shí)間點(diǎn) 在n頁(yè)的主存中的頁(yè)面集合 Lt表示到t時(shí)間點(diǎn)已遇到過(guò)的地址流中相異頁(yè)的頁(yè)數(shù) 如果替換算法滿足 n Lt時(shí) Bt n Bt n 1 n Lt時(shí) Bt n Bt n 1 則這類算法稱為堆棧型替換算法 LRU算法在主存中保留的是n個(gè)最近使用的頁(yè) 它們又總是被包含在n 1個(gè)最近使用的頁(yè)中 所以LRU算法是堆棧型的算法 OPT也是堆棧型的算法 而FIFO不是 上例就可以看出FIFO算法不具備任何時(shí)刻都滿足上述性質(zhì) 堆棧型算法的特點(diǎn) 命中率隨著主存頁(yè)面的增加值由可能提高 至少不會(huì)下降 所以只要是堆棧型的算法 只需采用堆棧處理技術(shù)對(duì)地址流模擬一次 即可同時(shí)求得對(duì)此地址流在不同主存頁(yè)頁(yè)數(shù)時(shí)的命中率 假設(shè)在堆棧模擬時(shí) 主存在t時(shí)間點(diǎn)的狀況用堆棧St來(lái)表示 不同的堆棧型替換算法 St各項(xiàng)的改變過(guò)程不同 對(duì)于LRU算法是把主存中剛訪問(wèn)過(guò)的頁(yè)號(hào)置于棧頂 而把最久未被使用的頁(yè)號(hào)置于棧底 設(shè)t時(shí)間點(diǎn)訪問(wèn)的頁(yè)為At 若AtSt 1 則把At壓入棧頂使之成為St 1 St 1各項(xiàng)都下推一個(gè)位置 若At St 1 則將它由St 1中取出壓入棧頂使之成為St 1 在At之下的各項(xiàng)位置不變 而在At之上的各項(xiàng)都下推一個(gè)位置 例如 例12 例9 一個(gè)程序共有5個(gè)頁(yè)面組成 程序執(zhí)行過(guò)程中的頁(yè)地址流如下 2 3 2 1 5 2 4 5 3 2 5 2假設(shè)使用LRU替換算法為了獲得最高命中率 至少分配給該程序的幾個(gè)實(shí)頁(yè)數(shù) 其可能的命中率是多少 請(qǐng)畫出對(duì)應(yīng)這個(gè)地址流 主存頁(yè)數(shù)n取1 2 3 4 5等不同值的情況下的命中率 堆棧型算法的共有的基本特點(diǎn) 隨著分配給程序的主存頁(yè)面數(shù)增加 主存的命中率也提高 至少不下降 隨著分配給該道程序的實(shí)頁(yè)數(shù)n的增加 命中率H會(huì)單掉上升 作業(yè) 課本P1444 6第1種要求 假設(shè)分配給該道程序的實(shí)頁(yè)數(shù)是3頁(yè) 1 給出FIFO LRU OPT三種頁(yè)面替換算法對(duì)這3頁(yè)主存的使用情況 包括調(diào)入 替換和命中等 2 計(jì)算每種替換算法的命中率是多少 第2種要求 如書內(nèi)容 使用LRU算法對(duì)該程序的頁(yè)地址流進(jìn)堆棧模擬處理的 5提高主存命中率的方法影響主存命中率的主要因素 1 程序執(zhí)行過(guò)程中的頁(yè)地址流分布情況 2 所采用的頁(yè)面替換算法 3 頁(yè)面大小 4 主存儲(chǔ)器的容量 5 所采用的頁(yè)面調(diào)度算法以下 對(duì)后三個(gè)因素進(jìn)行分析 1 頁(yè)面大小與命中率的關(guān)系頁(yè)面大小SP為某個(gè)值時(shí) 命中率達(dá)到最大 頁(yè)面大小與命中率關(guān)系的解釋 假設(shè)At和At 1是相鄰兩次訪問(wèn)主存的邏輯地址 d At At 1 如果 Sp 隨著Sp的增大 At和At 1在同一頁(yè)面的可能性增加 即 隨著Sp的增大而提高 如果 Sp At和At 1一定不在同一個(gè)頁(yè)面內(nèi) 隨著Sp的增大 主存頁(yè)面數(shù)減少 頁(yè)面替換將更加頻繁 隨著Sp的增大而降低 當(dāng)Sp比較小的時(shí)候 前一種情況是主要的 隨著Sp的增大而提高 當(dāng)Sp達(dá)到某一個(gè)最大值之后 后一種情況成為主要的 隨著Sp的增大而降低 當(dāng)頁(yè)面大小增大時(shí) 造成的浪費(fèi)也要增加 當(dāng)頁(yè)面大小減小時(shí) 頁(yè)表和頁(yè)面表在主存儲(chǔ)器中所占的比例將增加 2 主存容量與命中率的關(guān)系主存命中率H隨著分配給該程序的主存容量S的增加而單調(diào)上升 在S比較小的時(shí)候 H提高得非常快 隨著S的逐漸增加 H提高的速度逐漸降低 當(dāng)S增加到某一個(gè)值之后 H幾乎不再提高 3 頁(yè)面調(diào)度方式與命中率的關(guān)系請(qǐng)求式 當(dāng)使用到的時(shí)候 再調(diào)入主存預(yù)取式 在程序重新開始運(yùn)行之前 把上次停止運(yùn)行前一段時(shí)間內(nèi)用到的頁(yè)面先調(diào)入到主存儲(chǔ)器 然后才開始運(yùn)行程序 可以避免在程序開始運(yùn)行時(shí) 頻繁發(fā)生頁(yè)面失效的情況 如果調(diào)入的頁(yè)面用不上 浪費(fèi)了調(diào)入的時(shí)間 占用了主存資源 第4章存儲(chǔ)系統(tǒng) 現(xiàn)代計(jì)算機(jī)系統(tǒng)都以存儲(chǔ)器為中心在計(jì)算機(jī)運(yùn)行過(guò)程中 存儲(chǔ)器是各種信息存儲(chǔ)和交換的中心4高速緩沖存儲(chǔ)器 Cache 高速緩沖存儲(chǔ)器 Cache 1基本工作原理2地址映象與變換方法3Cache替換算法及其實(shí)現(xiàn)4Cache的一致性問(wèn)題5Cache的預(yù)取算法 存儲(chǔ)系統(tǒng) 兩級(jí)存儲(chǔ)器速度比 Cache 虛擬存儲(chǔ)器 要達(dá)到的目標(biāo) 提高速度 擴(kuò)大容量 實(shí)現(xiàn)方法 全部硬件 軟件為主硬件為輔 3 10倍 105倍 頁(yè) 塊 大小 1 16字 1KB 16KB 等效存儲(chǔ)容量 主存儲(chǔ)器 虛擬存儲(chǔ)器 透明性 對(duì)系統(tǒng)和應(yīng)用程序員 僅對(duì)應(yīng)用程序員 不命中時(shí)處理方式 等待主存儲(chǔ)器 任務(wù)切換 Cache存儲(chǔ)系統(tǒng)與虛擬存儲(chǔ)系統(tǒng)比較 1基本工作原理 塊號(hào)B 塊內(nèi)地址W 主存 Cache地址變換 塊號(hào)b 塊內(nèi)地址w Cache Cache替換策略 儲(chǔ)器 主存 替換塊 裝入塊 已滿 未滿 未命中 命中 數(shù)據(jù)送CPU 主存地址來(lái)自CPU 2地址映象與變換方法地址映象 把存放在主存中的程序按照某種規(guī)則裝入到Cache中 并建立主存地址與Cache地址之間的對(duì)應(yīng)關(guān)系地址變換 當(dāng)程序已經(jīng)裝入到Cache之后 在實(shí)際運(yùn)行過(guò)程中 把主存地址變換成Cache地址在選取地址映象方法要考慮的主要因素 地址變換的硬件容易實(shí)現(xiàn) 地址變換的速度要快 主存空間利用率要高 發(fā)生塊沖突的概率要小 1 全相聯(lián)映象及其變換映象規(guī)則 主存中的任意一塊都可以映象到Cache中的任意一塊 如果Cache的塊數(shù)為Cb 主存的塊數(shù)為Mb 映象關(guān)系共有 Cb Mb種 用硬件實(shí)現(xiàn)非常復(fù)雜在虛擬存儲(chǔ)器中 全部用軟件實(shí)現(xiàn) 塊0 Cache 塊1 塊Cb 1 塊0 塊1 塊i 塊Mb 1 主存儲(chǔ)器 全相聯(lián)映象方式 為了加快主存 Cache的地址變換 不能使用類似虛擬存儲(chǔ)器中的頁(yè)表法來(lái)存放主存 Cache的映射關(guān)系 因?yàn)檫@個(gè)塊表會(huì)很大 造價(jià)大 速度慢 所以采用的方式是目錄表硬件方式來(lái)實(shí)現(xiàn) i 地址變換過(guò)程是給出主存地址時(shí) 將其主存塊號(hào)與目錄表中的所有各項(xiàng)同時(shí)相聯(lián)比較 若有相同 就將對(duì)應(yīng)行的Cache塊號(hào)取出 拼接上塊內(nèi)地址就形成Cache地址 然后訪問(wèn)Cache 若沒有相同的 表示該主存塊未裝入Cache 發(fā)生Cache塊失效 由硬件調(diào)塊 有效位 塊號(hào)B 塊內(nèi)地址 主存地址 目錄表 由相聯(lián)存儲(chǔ)器組成 共Cb個(gè)字 主存塊號(hào)B B 塊號(hào)b 塊內(nèi)地址w Cache塊號(hào)b b 相聯(lián)比較 命中 Cache地址 全相聯(lián)映射法的優(yōu)點(diǎn)是塊沖突概率最低 只有當(dāng)Cache全部裝滿才可能出現(xiàn)塊沖突 所以Cache的空間利用率最高 但是要是使用相聯(lián)存儲(chǔ)器 其代價(jià)太大 而且Cache容量很大時(shí) 其查表速度很難提高 所以提出了直接映像方式 這樣縮小和簡(jiǎn)化了映像機(jī)構(gòu)表 映象規(guī)則 把主存空間按Cache大小等分成區(qū) 主存中每個(gè)區(qū)內(nèi)的各塊只能按位置一一對(duì)應(yīng)到Cache的相應(yīng)塊的位置上 計(jì)算公式 b BmodCb 其中 b為Cache的塊號(hào) B是主存的塊號(hào) Cb是Cache的塊數(shù) 整個(gè)Cache地址與主存地址的低位部分完全相同 2 直接映象及其變換 塊0 Cache 塊1 塊Cb 1 塊0 塊Cb 1 主存儲(chǔ)器 直接相聯(lián)映象方式 塊Cb 塊2Cb 1 塊Mb Cb 塊Mb 1 區(qū)0 區(qū)1 區(qū)Me 1 i 按直接映射的規(guī)則 裝入Cache中的某塊位置的主存塊可能來(lái)自主存不同的區(qū) 為了區(qū)分裝入Cache的塊到底是哪一個(gè)主存區(qū)的 需用一個(gè)按地址訪問(wèn)的表存儲(chǔ)器來(lái)存放Cache中每一塊位置 目前是被主存中哪個(gè)區(qū)的塊所占用的區(qū)號(hào) 假設(shè)當(dāng)主存中的第i塊按直接映像裝入Cache中第j塊時(shí) 應(yīng)將第i塊所在區(qū)號(hào)裝入第j塊對(duì)應(yīng)的區(qū)號(hào)標(biāo)志字段中 用處理機(jī)給出主存地址nm訪問(wèn)主存時(shí) 截取與nc對(duì)應(yīng)的部分作為Cache地址訪問(wèn)Cache 同時(shí)取ncb部分作為地址訪問(wèn)區(qū)號(hào)標(biāo)志表存儲(chǔ)器 讀出原先所存的區(qū)號(hào)標(biāo)志與主存地址對(duì)應(yīng)的區(qū)號(hào)部分比較 比較結(jié)果相等 則Cache命中 讓Cache的訪問(wèn)繼續(xù)進(jìn)行 并中止訪內(nèi)存 比較結(jié)果不相等 表示Cache失效 此時(shí)讓Cache的訪問(wèn)中止 而讓主存的訪問(wèn)繼續(xù)進(jìn)行 并由硬件自動(dòng)將主存中該塊調(diào)入Cache 地址變換過(guò)程 有效位 區(qū)號(hào) 塊內(nèi)地址nmr 1 主存地址nm 按地址訪問(wèn)的區(qū)表存儲(chǔ)器 區(qū)號(hào) 按地址訪問(wèn) 塊號(hào)ncb 塊內(nèi)地址ncr 命中 Cache地址nc 塊號(hào)nmb 相等比較 不相等塊失效 比較相等且有效位為1 訪問(wèn)Cache 相等 提高Cache速度的一種方法 把區(qū)號(hào)存儲(chǔ)器與Cache合并成一個(gè)存儲(chǔ)器直接映象方法的主要優(yōu)點(diǎn) 硬件實(shí)現(xiàn)很簡(jiǎn)單 只需容量較小的按地址訪問(wèn)的區(qū)號(hào)標(biāo)志表存儲(chǔ)器和少量外比較電路 成本很低 訪問(wèn)Cache與訪問(wèn)區(qū)表號(hào) 比較區(qū)號(hào)是否相符的操作同時(shí)進(jìn)行的 當(dāng)Cache命中時(shí)意味著省略了地址變換的時(shí)間 不做地址變換 所以訪問(wèn)速度也比較快 直接映象方式的主要缺點(diǎn) 塊的沖突率很高 只要有兩個(gè)或兩個(gè)以上經(jīng)常使用的塊恰好被映射到Cache同一塊位置時(shí) 就會(huì)使Cache命中率急劇下降 即使此時(shí)Cache中有大量空閑塊也無(wú)法利用 所以Cache的利用率很低 因此 目前已很少使用直接映像規(guī)則了 可以看出 全相聯(lián)映像和直接映像的優(yōu)缺點(diǎn)正好相反 可以將兩者結(jié)合 這種新的映射方式即能減少塊沖突概率 提Cache空間利用率 又能使地址映像機(jī)構(gòu)及地址變換速度比全相聯(lián)的簡(jiǎn)單和快速 組組相聯(lián)映像就是這樣的一種映射規(guī)則 映象規(guī)則 主存和Cache按同樣大小劃分成塊 還按同樣大小劃分成組 從主存的組到Cache的組之間采用直接映象方式 在兩個(gè)對(duì)應(yīng)的組內(nèi)部采用全相聯(lián)映象方式 3 組相聯(lián)映象及其變換 組相聯(lián)映象方式 組相聯(lián)映象方式的優(yōu)點(diǎn) 塊的沖突概率比較低 塊的利用率大幅度提高塊失效率明顯降低 組組相聯(lián)映像比全相聯(lián)映像在成本上要低得多 而性能上仍可以接近于全相聯(lián)映像 所以得到廣泛應(yīng)用 組相聯(lián)映象方式的缺點(diǎn) 實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高 查表速度慢 用主存地址的組號(hào)G按地址訪問(wèn)塊表存儲(chǔ)器把讀出來(lái)的一組區(qū)號(hào)和塊號(hào)與主存地址中的區(qū)號(hào)和塊號(hào)進(jìn)行相聯(lián)比較如果有相等的 表示Cache命中如果沒有相等的 表示Cache沒有命中 地址變換過(guò)程 有效位 區(qū)號(hào) 塊內(nèi)地址w 1 按地址訪問(wèn)的Cache 區(qū)號(hào) E 塊號(hào)b 塊內(nèi)地址w 相等 塊號(hào)B 相等比較 訪主存 數(shù)據(jù)0 D0 數(shù)據(jù)1 D1 數(shù)據(jù)w 1 Dw 1 1 w 送CPU 實(shí)際上是組組聯(lián)的一種特例 映