計算機組織與結構Ch6存儲器-Luke.ppt

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