計算機組織與結(jié)構(gòu)Ch6存儲器-Luke.ppt

第6章 存儲器 2 第6章目標(biāo) 掌握層次存儲器組織的概念 理解層次存儲器的每一級對系統(tǒng)性能的影響 以及如何衡量系統(tǒng)性能 掌握cache存儲 虛擬存儲 分段 分頁和地址轉(zhuǎn)換的概念 3 6 1介紹 存儲器是基于存儲程序的計算機的核心 本章重點學(xué)習(xí)存儲器的組織及原理 這對于系統(tǒng)性能分析是至關(guān)重要 4 6 2存儲器類型 兩種主存儲器 隨機存儲器 RAM 和只讀存儲器 ROM 兩種類型的RAM 動態(tài)RAM DRAM 和靜態(tài)RAM SRAM 動態(tài)RAM由電容器組成 電容器內(nèi)的電荷隨著時間會緩慢丟失 所以它們必須每隔幾微秒刷新一次 以阻止數(shù)據(jù)丟失 由于DRAM設(shè)計簡單 所以被稱為是 便宜的 存儲器 5 6 2存儲器類型 SRAM通常由D觸發(fā)器構(gòu)成 SRAM是非?？斓拇鎯ζ?它不需要像DRAM那樣刷新 Cache存儲器就是用SRAM構(gòu)造的 這個我們在后面會詳細討論 ROM也不需要刷新 實際上 它需要很少的電荷來保存信息 ROM用于永久性存儲 或者即使當(dāng)系統(tǒng)關(guān)閉后數(shù)據(jù)仍能保持的半永久存儲 6 6 3存儲器層次 通常 較快的存儲器比較慢的存儲器成本高 為了以最少的花費獲得最好的性能 存儲器以層次方式組織 容量小 速度快的存儲部件放在CPU中 較大的 較慢的主存通過數(shù)據(jù)總線來訪問 更大的永久存儲器以磁盤的形式或磁帶驅(qū)動形式存在于遠離CPU的位置 7 6 3存儲器層次 這種分層存儲組織結(jié)構(gòu)被認(rèn)為是一種金字塔形 8 6 3存儲器層次 為了存取數(shù)據(jù) CPU首先向它最近的存儲器發(fā)送請求 通常是cache 如果數(shù)據(jù)不在cache中 就要詢問主存 如果數(shù)據(jù)不在主存中 就要去詢問磁盤 一旦確定了數(shù)據(jù)的位置 數(shù)據(jù)和它附近的許多數(shù)據(jù)單元就被取到cache存儲器中 9 6 3存儲器層次 相關(guān)概念命中 hit CPU請求的數(shù)據(jù)就駐留在要訪問的存儲器層中 缺失 miss CPU請求的數(shù)據(jù)不在要訪問的存儲器層中 命中率 hitrate 訪問某個特定的存儲器層時 CPU不到所需數(shù)據(jù)的百分比 缺失率 missrate 訪問某個特定的存儲器層時 CPU找不到所需數(shù)據(jù)的百分比 缺失率 1 命中率 命中時間 hittime 是某個特定的存儲器層中 CPU取得所請求數(shù)據(jù)需要的時間 缺失損失 misspenalty CPU處理一次缺失事件所需時間 其中包括利用新的數(shù)據(jù)取代上層存儲器中的某個數(shù)據(jù)塊所需時間 再加上將所需數(shù)據(jù)傳遞給處理器所需的附加時間 10 6 3存儲器層次 一個完整的數(shù)據(jù)塊在命中后被復(fù)制 根據(jù)局部性原理 一旦字節(jié)被訪問 它附近的數(shù)據(jù)元素很快也會被訪問 局部性的三種形式 時間局部性 最近訪問的數(shù)據(jù)易于在不久的將來再次被訪問 空間局部性 對存儲器地址空間的訪問形成団簇的集中傾向 順序局部性 訪問存儲器的指令趨于被順序訪問 11 6 4Cache存儲器 cache存儲器是通過把最近使用過的數(shù)據(jù)存放在臨近CPU的位置而不把它存儲在主存中來提高存取速度 雖然cache比主存小很多 但它的存取速度比主存快很多 和主存不同 主存是通過地址來訪問 而cache是靠內(nèi)容來訪問的 所以常常稱cache為內(nèi)容可尋址存儲器 因此 并不是cache存儲器越大越好 容量太大則查找數(shù)據(jù)的時間就會很長 12 6 4Cache存儲器 主存儲器和cache的存儲空間都被劃分成大小相同的數(shù)據(jù)塊 主存儲器的許多塊映射到cache的一個塊 Cache中的不同塊由標(biāo)記域 tagfield 來區(qū)分 存儲器地址被劃分為多個域 field 如標(biāo)記域 字域 塊域等 這些域為較大的主存和較小的cache存儲器之間提供多對一映射關(guān)系 命中過程 根據(jù)主存地址中的塊域找到數(shù)據(jù)在cache中的位置判別有效位 validbit 比較cache中的標(biāo)記與主存地址的標(biāo)記域根據(jù)字域找到所需訪問的字 13 6 4Cache存儲器 最簡單的cache映射模式是直接映射 在cache中的N個塊和主存中的X個塊組成的直接映射 映射關(guān)系 Y XmodN 如果cache有10個塊 cache的第7塊可能含有主存中的第7 17 27 37 塊 一旦主存的一個塊被復(fù)制到cache的對應(yīng)塊中 就要為cache塊設(shè)置一個有效位 validbit 指示系統(tǒng)該塊中含有有效數(shù)據(jù) 如果沒有有效位會發(fā)生什么情況 14 6 4Cache存儲器 下圖是cache的一個示意圖 塊0含有來自主存儲器的多個字 并用標(biāo)記00000000來進行身份識別 塊1用11110101來標(biāo)記 其它的兩個塊是無效的 15 6 4Cache存儲器 一個存儲器地址被分成的每一個域的大小依賴于cache的大小 假如存儲器由214個字組成 cache有16 24個塊 并且每個塊有8個字 這樣 存儲器就分成了214 23 211個塊 主存地址域的劃分 4位用于塊域 3位用于字域 左面剩下的全部用于標(biāo)記域 16 6 4Cache存儲器 根據(jù)上面例子 假如一個程序產(chǎn)生了地址1AA 在14位二進制當(dāng)中 這個數(shù)字是00000110101010 這個地址的開始7位是標(biāo)志域 接著的4位是塊域 并且后3位表明塊中的字 17 6 4Cache存儲器 如果隨后該程序產(chǎn)生的地址是1AB 它將在塊0101中尋找數(shù)據(jù) 字位于快內(nèi)011位置 然而 如果該程序產(chǎn)生地址3AB 則地址1AA裝入的塊將會從cache中取出 而用與3AB相關(guān)的信息來置換 18 6 4Cache存儲器 假如一個程序產(chǎn)生了一系列的存儲地址 如1AB 3AB 1AB 3AB cache將持續(xù)的取出 并且進行塊的替換 在這種極端情況下 cache理論上的優(yōu)點就不存在了 這是直接映射cache的主要缺點 設(shè)計的其它的cache映射方案阻止了這種系統(tǒng)顛簸 19 6 4Cache存儲器 不為存儲塊設(shè)置明確的基于主存儲器地址的cache位置 我們可以允許一個塊存放在cache中的任何塊中 用這種方式 在任何塊被取走之前 cache必須是填滿的 這就是全關(guān)聯(lián)cache的工作原理 一個存儲地址僅被分成兩個域 標(biāo)記域和字域 20 6 4Cache存儲器 如前面例子 假如有一個14位存儲地址和一個擁有16個塊的cache 每一個塊的大小是8個字 則存儲地址格式是 當(dāng)搜索cache時 并行的搜索所有的標(biāo)記 來快速檢索數(shù)據(jù) 這需要特殊的 造價高的硬件 21 6 4Cache存儲器 回憶一下 無論何時另一個存儲器內(nèi)容需要那個塊時 直接映射cache都將把該塊刪除 對于全相連的cache當(dāng)中 不存在這種映射關(guān)系 所以我們必須設(shè)計一種算法來決定哪一個塊應(yīng)該從cache中刪除 被刪除的塊是犧牲塊 有許多種方法選擇犧牲塊 我們將會簡要討論 22 6 4Cache存儲器 組關(guān)聯(lián)cache兼?zhèn)渲苯佑成鋍ache和全關(guān)聯(lián)cache的思想 一個N路固定相連cache映射想直接映射cache 因為一個存儲器內(nèi)容映射到cache中的一個特殊位置 與直接映射cache不同 一個存儲內(nèi)容映射到一組cache塊 和全相連cache的工作方式相似 不映射整個cache 存儲內(nèi)容能夠映射到的僅是cache空間的子集 23 6 4Cache存儲器 在組關(guān)聯(lián)cache中 每一組的cache塊數(shù)目根據(jù)系統(tǒng)的總體設(shè)計變化 例如 一個二路的組相連cache能夠被概念化成下面的概要圖來說明 每一組都含有兩個不同的塊 24 6 4Cache存儲器 在組關(guān)聯(lián)cache映射中 存儲內(nèi)容被劃分為三個字段 標(biāo)志 組 和字 如下所示 像直接映射cache一樣 word字段選擇cache塊中的字 標(biāo)志字段唯一的標(biāo)識存儲地址 Set字段決定存儲塊映射到的組 25 6 4Cache存儲器 假設(shè)我們有一個214字節(jié)的主存這個存儲器映射到一個擁有16個塊 每個塊有8個字的一個2路組相連cache 因為這是一個2路cache 每一組由2塊組成 有8組 這樣 需要3位用于set 3位用于word 余下的左邊8位用于tag 26 6 4Cache存儲器 對于全關(guān)聯(lián)和組關(guān)聯(lián)cache 當(dāng)需要從cache中取出一個塊時 調(diào)用一種置換策略 一個最優(yōu)置換策略能夠預(yù)測將來哪一個塊最長時間不需使用 雖然執(zhí)行最優(yōu)置換算法是不可能的 但是可以作為評價任何其它算法的參考和標(biāo)準(zhǔn) 27 6 4Cache存儲器 我們選擇的置換策略依賴于我們試圖去優(yōu)化的局部性 常常 我們對時間局部性感興趣 最近最久未使用算法 LRU 保持跟蹤最后一次被評估的塊 并且取出最長時間未使用的塊 這種方法的缺點是它的復(fù)雜性 LRU不得不為每一個塊保持訪問史 這最終降低了cache的速度 28 6 4Cache存儲器 先進先出 FIFO 是一種廣泛應(yīng)用的cache替換策略 在FIFO中 已經(jīng)在cache中的塊最長 不管它是何時被最后使用的 隨機置換策略 顧名思義 它隨機選取塊并且用一個新塊替換它 隨機置換當(dāng)然可能取出一個將經(jīng)常用到或很快就用到的塊 但它從來都不會顛簸 thrashes 29 6 4Cache存儲器 層次存儲器的性能是用它的有效訪問時間 EAT 衡量的 EAT是一種考慮命中率和存儲器的逐級相關(guān)存取時間的加權(quán)平均值 一個兩級存儲器的EAT計算公式如下 EAT H AccessC 1 H AccessMM 其中 H是cache的命中率 AccessC和AccessMM分別是cache和主存的存取時間 30 6 4Cache存儲器 例如 考慮一個系統(tǒng) 這個系統(tǒng)主存的存取時間是200ns cache的存取時間是10ns 并且命中率是99 EAT是 0 99 10ns 0 01 200ns 9 9ns 2ns 11ns 這個決定有效存取時間的等式可以擴展到任意級的存儲器系統(tǒng) 31 6 4Cache存儲器 Cache置換策略必須考慮臟塊 dirtyblock 尤其當(dāng)它們在cache中已經(jīng)被更新時 臟塊一定要再被寫回存儲器 寫策略決定了如何做 有兩種類型的寫策略 寫通 writethrough 和回寫 writeback 在每一次寫時 寫通同時更新cache和主存 32 6 4Cache存儲器 僅當(dāng)塊被選中替換時 回寫 也稱為copyback 才更新存儲器 寫通的缺點是對于每一次cache寫存儲器必須更新 這就降低了更新的訪問時間 這種降低常常是可以忽略的 因為大多數(shù)的存取都是讀 不是寫 回寫的優(yōu)點是通信量被最小化 但是它的缺點是存儲器不總是與cache中的值一致 對于多用戶系統(tǒng) 常會發(fā)起問題 33 6 5虛擬存儲器 憑借著提供較快的存儲器存取速度 Cache存儲器提高了性能 憑借著提供較大的存儲容量 不增加主存的成本 虛擬存儲器提高了性能 磁盤驅(qū)動器的一部分是為擴展主存服務(wù)的 如果一個系統(tǒng)使用頁式技術(shù) 虛擬存儲分區(qū)主存儲器成各自管理的頁楨 當(dāng)不立即需要它們時 它們就被寫道磁盤上 34 6 5虛擬存儲器 物理地址是物理存儲的實際存儲地址 程序產(chǎn)生被存儲管理者映射到物理地址的虛擬地址 當(dāng)邏輯地址需要從磁盤中引入頁時 缺頁就發(fā)生了 當(dāng)分頁過程導(dǎo)致小的 不可用的存儲器地址簇時 存儲破碎就發(fā)生了 35 6 5虛擬存儲器 主存和虛擬存儲器被分成相等大小的頁 一種處理過程需要的整個地址空間 在主存中不立即需要 一些部分可能在磁盤上 而其它的可能在主存中 進一步說 分配給進程的頁不必連續(xù)存儲 或者部分頁在磁盤上 或者在存儲器中 用這種方法 任何時候 僅僅需要的頁在存儲器中 不需要的頁存儲在磁盤當(dāng)中 36 6 5虛擬存儲器 關(guān)于每一頁的位置的信息 既不在磁盤上 也不在存儲器中 而是保留在一種稱為頁表的數(shù)據(jù)結(jié)構(gòu)中 如下所示 對于每一活動過程 都有一個頁表 37 6 5虛擬存儲器 當(dāng)一種操作產(chǎn)生一個虛擬地址時 操作系統(tǒng)就把它翻譯成一個物理存儲地址 為了完成這一操作 虛擬地址被分成倆個字段 頁字段 和偏移量字段 頁字段決定地址的頁位置 偏移量表明頁中的地址位置 通過在頁表中查找 邏輯頁碼被翻譯成一種物理頁幀 38 6 5虛擬存儲器 如果邏輯地址在頁表中的有效位是零 這意味著頁不在存儲器中 要到磁盤上去存取 這是頁發(fā)生了錯誤 如果必要 頁需要從存儲器中取出 并且被磁盤上檢索的頁所取代 有效位被設(shè)置成1 如果有效位是1 虛擬頁的數(shù)字被物理楨的數(shù)字所取代 把偏移量加到物理楨的數(shù)字 來存取數(shù)據(jù) 39 6 5虛擬存儲器 如一個例子 假如一個系統(tǒng)擁有一個8K空間的虛擬地址和一個4K空間的物理地址 系統(tǒng)是用位尋址 我們有213 210 23的虛擬頁 虛擬地址13位 8K 213 3位用于頁字段 10位用于偏移量 因為頁的大小是1024 一個物理存儲地址需要12位 開始的兩位用于頁楨 尾隨的10位是偏移量 40 6 5虛擬存儲器 假如我們有下面的頁表 Whathappens當(dāng)CPU產(chǎn)生地址545910 10101010100112時 會發(fā)生什么 41 6 5虛擬存儲器 地址10101010100112轉(zhuǎn)化成物理地址為010101010011因為通過再也表中查找 頁字段101被楨的數(shù)字01取代 42 6 5虛擬存儲器 當(dāng)CPU產(chǎn)生地址10000000001002時會發(fā)生什么 43 6 5虛擬存儲器 我們早就說過有效存取時間 EAT 需要考慮存儲器的所有級 這樣 在計算當(dāng)中 虛擬存儲器也是一個因素 我們也不得不考慮頁表的存取時間 假如一個主存的存取需要200ns 頁的出錯率為1 它花費10ms從磁盤中裝入一頁 我們有 EAT 0 99 200ns 200ns 0 01 10ms 100 396ns 44 6 5虛擬存儲器 即使沒有頁錯誤 EAT將是400ns 因為存儲器總是讀兩次 第一次存取頁表 第二次從存儲器中裝入頁 因為頁表的讀始終都是一樣的 所以保持它們在一個特殊的稱為翻譯旁視緩沖 TLB 的寄存器中 是有意義的 TLBs是一種特殊相關(guān)寄存器 這種寄存器將虛擬頁的映射存儲到物理頁 下一張幻燈片展示這些部件是如何協(xié)調(diào)工作的 45 6 5虛擬存儲器 46 6 5虛擬存儲器 虛擬存儲器的另一種方法是使用分段 不將存儲器分成相等大小的頁 虛擬地址空間被分成可變長度的段 常常在程序員的控制之下 通過段表的入口 一個段被定位 它含有段的存儲位置和一個表明它大小的界限 發(fā)生缺頁時 操作系統(tǒng)在存儲器中尋找一個足夠大的位置存放從磁盤中檢索到的段 47 6 5虛擬存儲器 分頁和分段都會引起碎片 分頁產(chǎn)生的是內(nèi)部碎片 因為一個進程不可能恰好需要一頁當(dāng)中含有的全部地址空間 這樣 許多頁含有存儲器中未用過的碎片 分段產(chǎn)生的是外部碎片 在進行分段配置和解除分段時 存儲器中的自由空間塊會變得殘缺不完整 最后導(dǎo)致有許多長度較小的自由空間塊都不足以存放一整段程序 4