【正文】 計算機(jī)系統(tǒng)結(jié)構(gòu) 1 第 7章 存儲層次（ P188） Memory Hirarchy 長期存在的問題：在合理的總價格限制下，單一型主存器件的速度跟不上 CPU的發(fā)展，容量不能滿足軟件尺寸擴(kuò)大。 本章學(xué)習(xí)提高主存系統(tǒng)性能 /價格比的幾種結(jié)構(gòu)化方法，重點(diǎn)是“ Cache主存層次 ” ，焦點(diǎn)問題是 如何使流水線每拍完成一次訪存 。 本章基本公式： (1)平均時間 T = P1 T1 + P2 T2 其中 P1 + P2 = 100%，并且 T1 和 T2 都可以再用該式迭代展開，復(fù)雜 時，可用概率樹來表示（全概率公式）； (2)實(shí)際時間 T = 理想時間 + P3 每次額外開銷時間 其中 P3 是不利事件發(fā)生概率。 1 P 1 P 2 P 11 P 12 P 21 P 22 計算機(jī)系統(tǒng)結(jié)構(gòu) 2 存儲層次原理及性能指標(biāo)（ P188） 基本原理 ? “ 存儲層次 ” 的定義： （ 參見 P189第 3段 ） 由 2種或多種存儲部件構(gòu)成的復(fù)合存儲系統(tǒng) ， 通過內(nèi)部管理機(jī)構(gòu)的 自動更換機(jī)制 ， 能夠不斷將大容量低速存儲部件中的活躍內(nèi)容復(fù)制到小容量高速存儲部件中 （ 后者作為前者的 局部副本 ） 。 它既能滿足 CPU的快速存取需要 ， 又有很大的存儲容量 ， 平均單位價格也很低 ， 等效于同時滿足 3方面要求的理想單一存儲部件 。 ? 依據(jù)：程序訪問的局部化原理 （ 時間局部化 ， 空間局部化 ） 。 ? 模型：如右圖所示 ， 存儲層次由 n層組成 ， 滿足 3個不等式： TAiTAi+1， cici+1， SiSi+1 。 CPU M 1 M 2 M n 圖 存儲層次模型 計算機(jī)系統(tǒng)結(jié)構(gòu) 3 存儲層次的基本術(shù)語 邏輯地址 （ 又稱為相對地址 、 虛地址 ） 是程序員在編寫和編譯一個程序模塊時分配指令和數(shù)據(jù)的空間單位序號 ， 總是從 0開始 （ 可以按字節(jié)編址 、 按CPU字編址等 ） 。 邏輯地址的取值范圍稱為邏輯地址空間 、 虛空間或虛存 。 物理地址 （ 又稱為絕對地址 、 實(shí)地址 ） 是任一級存儲器為全部存儲單元分配的序號 。 物理地址的取值范圍稱為物理地址空間 、 實(shí)空間或?qū)嵈?。 從 M1到 Mn各層都有自己的物理地址空間 ， 而對當(dāng)前執(zhí)行的程序模塊來說 ，邏輯地址空間只有一個 。 地址映象方式 指的是虛頁集合與實(shí)頁集合的對應(yīng)規(guī)則，或者說是約束關(guān)系。 地址變換 （又叫虛實(shí)變換）指邏輯地址到物理地址的變換過程或者算法。 頁失效 指當(dāng)前被訪問存儲級中沒有所需的信息，也就是不命中現(xiàn)象。 實(shí)頁爭用 又叫實(shí)頁沖突，指虛頁調(diào)入時，根據(jù)地址映象方式劃定的實(shí)空間范圍內(nèi)已沒有空閑實(shí)頁的狀況。 頁和塊 ：前者用于主 輔層次，后者用于 Cache主存層次，意義相同。 計算機(jī)系統(tǒng)結(jié)構(gòu) 4 存儲層次的管理方式 (P230) 根據(jù)程序的局部化性質(zhì)，存儲層次機(jī)構(gòu)對用戶文件的管理應(yīng)該劃分成較小的基本調(diào)度單位來進(jìn)行。依劃分標(biāo)準(zhǔn)不同，存在 3種存儲層次管理方式。 目前在主存 —輔存層次實(shí)現(xiàn)中，具體機(jī)器可能采用 3種方式中的某 1種，而 Cache主存層次普遍只采用第 2種，因?yàn)樗唵?，便于硬件?shí)現(xiàn)。 (1)段式管理。段是程序中的一個邏輯單位，可以是一個程序模塊，或者是一個數(shù)據(jù)結(jié)構(gòu)。段的長度不一，但段內(nèi)所有數(shù)據(jù)的信息屬性一般是相同的，便于統(tǒng)一進(jìn)行信息保護(hù)。 每段使用獨(dú)立的邏輯地址空間 ， 即都從 0開始計算地址 。 段式管理方法的主要缺點(diǎn)是各段長短不一 ， 調(diào)進(jìn)調(diào)出之后容易形成大量不規(guī)則的零碎空間 。 段式管理方法的虛實(shí)變換算法是查段表 。 因其實(shí)現(xiàn)較復(fù)雜 ， 僅用于主存 —輔存層次 。 計算機(jī)系統(tǒng)結(jié)構(gòu) 5 存儲層次的管理方式 (續(xù) ) (2)頁式管理。頁是系統(tǒng)規(guī)定的固定長度單位。按頁劃分用戶文件可以避免上述零碎空間浪費(fèi)。 我們把用戶文件劃分得到的一個長度單位稱為 “ 虛頁 ” ，因?yàn)樗捻撎柺窃谔摰刂房臻g中編排的；實(shí)地址空間按頁的大小劃分得到的一個長度單位稱為 “ 實(shí)頁 ” 。 頁式管理方法的主要缺點(diǎn)是按固定長度分出來的同一頁內(nèi)常有不同屬性的信息，不便于信息保護(hù)的實(shí)現(xiàn)。 頁式管理方法的虛實(shí)變換算法是查頁表 。 兩種層次都用此技術(shù) 。 (3)段頁式管理 。 它把上述兩種管理方式結(jié)合起來 ， 首先將整個文件分段 ，然后在各段內(nèi)分頁 ， 所以有一個段表和若干個頁表 。 其虛實(shí)變換算法是先查段表 ， 查出該段的頁表起始地址再查相應(yīng)的頁表 。 段頁式管理的主要缺點(diǎn)是多查一次表 ， 虛實(shí)變換費(fèi)時較多 ， 占用空間也較大 。 它的實(shí)現(xiàn)最復(fù)雜 ， 僅用于主存 —輔存層次 。 段頁式管理方法的最小調(diào)度單位仍是頁 ， 基本操作可歸于頁式管理 。 計算機(jī)系統(tǒng)結(jié)構(gòu) 6 課堂練習(xí) 一個頁式虛擬存儲器按字節(jié)編址，頁面大小為 1K字節(jié)，每個數(shù)據(jù)的字長為 4個字節(jié)?，F(xiàn)有一個程序的頁表如下： 虛頁號 裝入標(biāo)志 主存頁號 修改標(biāo)志 訪問方式 0 1 2 0 RW 1 1 3 0 R 2 0 0 0 R 3 1 1 0 X 4 0 0 0 RW 5 1 0 0 R 6 0 0 0 X 表中的裝入標(biāo)志為 “ 1” 表示該虛頁已經(jīng)裝入主存，為 “ 0” 則表示還未裝入主存。修改標(biāo)志為 “ 0” 表示該頁還沒有被修改過，為 “ 1” 則表示該頁已經(jīng)被修改過。訪問方式 “ RW‖表示該頁可以讀可以寫，但不能作為指令來執(zhí)行； “ R‖表示該頁只能讀，不能寫和執(zhí)行； “ X‖表示該頁只能作為指令來執(zhí)行，不能讀和寫。 計算機(jī)系統(tǒng)結(jié)構(gòu) 7 課堂練習(xí) （續(xù) ） 虛地址經(jīng)變址尋址和基址尋址 (B)+(X)+D形成?，F(xiàn)有一個程序，出現(xiàn)下列訪問主存的操作： 虛存地址 序號 操作 ( B ) ( X ) D 1 取數(shù) 124 30 50 2 取數(shù) 2021 1000 60 3 存數(shù) 4000 2021 600 4 存數(shù) 1200 4600 60 5 取數(shù) 3000 640 100 6 取數(shù) 4096 500 20 7 加并存數(shù) 400 1200 80 8 加并存數(shù) 36 360 64 9 轉(zhuǎn)移 2500 600 100 10 轉(zhuǎn)移 3600 1200 56 (1)列出產(chǎn)生主存頁面失效的操作序號。 (2)如果不發(fā)生主存頁面失效的話，計算訪問主存的物理地址。 (3)列出非法操作的序號。 (4)列出被修改過的主存頁面號。 計算機(jī)系統(tǒng)結(jié)構(gòu) 8 “主 ─輔”層次與“ Cache─主存”層次的對比 （ P192表 ， P231表 ） ? “ 主存 輔存 ” 層次 目的：提高等效容量。 基本調(diào)度單位：頁，幾百 Byte到幾千 Byte。 速度比：幾萬倍。 虛實(shí)轉(zhuǎn)換：頁表（以虛頁號為索引） ? “Cache主存 ” 層次 目的：提高等效速度。 基本調(diào)度單位：塊，幾十 Byte。 速度比：幾倍。 虛實(shí)轉(zhuǎn)換：目錄表（以實(shí)頁號為索引） 計算機(jī)系統(tǒng)結(jié)構(gòu) 9 存儲層次的基本問題 (P192) ①映象規(guī)則 ——一個虛塊（頁）被允許放到哪些實(shí)塊（頁）上； ②查找算法 ——如何在實(shí)存中找到指定的虛塊（頁）（主要是虛實(shí)變換）； ③替換算法 ——塊（頁）爭用時，調(diào)出哪個虛塊（頁）； ④寫策略 ——寫存儲層次的具體操作。 典型存儲層次（ PC計算機(jī)，以 Intel芯片組為例） 名稱 容量 二進(jìn)制 訪問時間 頁（塊）尺寸 路數(shù) 一級 Cache 3 2 KB 2 2 15 1 n s = 1 10 9 1 6 B = 2 4 2 二級 Cache 2 M B 混合 2 20 2 n s = 2 10 9 16 主存 1 GB 2 30 3 0 n s = 3 10 8 4 KB = 2 12 硬盤 5 0 0 GB 2 39 3 m s = 3 10 3 計算機(jī)系統(tǒng)結(jié)構(gòu) 10 存儲層次的性能指標(biāo)（ P189） 先以 2級存儲層次為例進(jìn)行公式推導(dǎo) ， 并且只考慮各級存儲器件自身的操作 ， 忽略控制機(jī)構(gòu)的附加開銷 。 多級層次以及附加開銷留到以后討論 。 (1) 容量： S = S2 （ 理論上 ） (2) 單價： （ 美分 /bit） 2021212121221121l i m1ccSSccSSSSScSccSS???????????它的最小值是 計算機(jī)系統(tǒng)結(jié)構(gòu) 11 (3) 速度 表現(xiàn)訪問速度的參數(shù)較多。 ? 命中率 H： 被訪問數(shù)據(jù)事先已在 M1的概率 ? 不命中率 F： 不命中的概率，又稱失效率， F = 1 H ? 平均訪存時間：命中時的訪存時間為 TA1， 不命中時的訪存時間為 TA2， 平均訪存時間則是它們的概率均值 其中 TM是失效開銷， TM = TA2 + TB2 10211 ???? HNN NH ，MAMAAMAATFTTHTTTHTHT?????????????1111)1()()1(1%1 00lim AAH TT ?? 計算機(jī)系統(tǒng)結(jié)構(gòu) 12 ? 訪問效率 e（ 補(bǔ)充） 。， ?????? ereH e r = 1 r = 9 0 1 H H 和 r 對 e 的作用 訪問效率 e 受 H 和 r 的影響（參見右圖）： 是鄰級速度比）。（，其中 rTTreAA 11012 ????rFTFTTTTeAAAAA???????112111 e 是一個相對值，便于不同系統(tǒng)之間的比較。 計算機(jī)系統(tǒng)結(jié)構(gòu) 13 假設(shè)： TAi表示第 i級器件讀 /寫時間； TBi表示第 i級向上級傳送時間 。 根據(jù)模型有： 命中 M1時： TA = TA1 命中 M2時： TA = TA1 + TA2 + TB2 ≈ TA2 …… 命中 Mn時： TA = TA1 + TA2 + TB2 + …… + TAn + TBn ≈ Tan 區(qū)別： ? 單次訪問總時間近似等于本次到達(dá)的最低一層的訪問時間，因?yàn)槊繉佣贾辉L問一次； ? 大量訪問的平均時間則由各層訪問時間共同構(gòu)成，因?yàn)檩^高層的一次訪問時間雖短，但它們被訪問的百分比遠(yuǎn)遠(yuǎn)大于較低層。 多級存儲層次的單次訪問時間 CPU M 1 M 2 M n 圖 存儲層次模型 計算機(jī)系統(tǒng)結(jié)構(gòu) 14 課堂練習(xí) 設(shè)計 “Cache主存 ” 層次， Cache的容量有三種選擇，如上表所示。忽略平均訪存時間 TA公式中的 TB。 (1) 分別計算三種方案的等效訪問時間； (2) 分別計算三種方案每 KB的平均價格； (3) 分別根據(jù)等效訪問時間、每 KB的平均價格排序； (4) 根據(jù)等效訪問時間和平均價格的乘積排序。 方案 1 方案 2 方案 3 訪問時間 T Ai 單價 c 容量 S 1 64K 128K 256K 命中率 H 1 0. 7 0. 9 0. 98 20 ns 4. 0 元 /K B 容量 S 2 4096K 200 ns 0. 2 元 /K B 計算機(jī)系統(tǒng)結(jié)構(gòu) 15 多級存儲層次的平均訪問時間 1 M1 103B TA1=1us 103B M2 106B TA2=10us M3 109B TA3=100us 109B (a) (b) 例 有一個 109字節(jié)的程序被裝入右圖所示的 M3準(zhǔn)備運(yùn)行。假定指令字長 =1字節(jié)，程序中無轉(zhuǎn)移指令和內(nèi)存讀 /寫指令。忽略傳送時間 TB。 (1)按圖 (a)求 TA和 e； (2)按圖 (b)推導(dǎo)三層體系的 TA公式； (3)按圖 (b)求 TA和 e； (4)比較 (1)(3)結(jié)果，有何結(jié)論？ 解