第六章 存儲器層次結構
本章概況：了解儲存設備的類型和特點。重點了解局部性原理和緩存思想在存儲層次結構中的應用。 6.0前言
1、存儲器系統是一個具有不同容量、成本和通路時間的儲存設備的層次結構。CPU寄存器儲存着最常用的資料。靠近CPU的小的、快速地高速緩存存儲器作為一部分存儲在相對慢速的主存儲器中的資料和指令的緩沖區域。主存暫時存放在容量較大的、慢速磁盤上的資料，而這些磁盤常常又作為存儲在通過網絡連接配接的其他機器的磁盤或錄音帶上的資料的緩沖區域。
2、資料是存儲在CPU寄存器中的，那麼在指令的執行期間，在零個周期内就能通路到它們。如果存儲在高速緩存中，需要1-30個周期。如果存儲在主存中，需要50-200個周期，如果存儲在磁盤上，需要大約幾千萬個周期。
3、計算機系統中的一個基本而持久的思想：若能了解系統是如何将資料存儲在存儲器層次結構中上上下下移動的，那麼你就可以編寫你的應用程式，使得它們的資料項存儲在層次結構中較高的地方，在哪裡CPU能更快地通路它們。這個思想圍繞着計算機程式一個稱為局部性的基本屬性。
4、本章會提及基本的存儲技術：SRAM存儲器、DRAM存儲器、ROM存儲器、旋轉的和固态的硬碟。
5、高速緩存存儲器是作為CPU和主存之間的緩存區域，因為它們對應用程式的性能的影響最大。
存儲器山：是一種描繪某台機器上存儲器層次結構的性能的有趣方法。，它給出的讀通路時間是局部性的一個函數。
6.1存儲技術
本節要求：
了解三種常見存儲技術：RAM、ROM、磁盤；
RAM有SRAM、DRAM，特點及應用；
ROM有PROM、EPROM、E2PROM、FLASH；
磁盤是重點，涉及到後面的I/O和檔案系統，要求做好相關練習；
磁盤結構：盤片、磁道、扇區、間隙、柱面；
磁盤驅動器；
磁盤容量；
通路時間：尋道、旋轉、傳送；
邏輯磁盤塊：這個很重要，記憶體可以看成字組數組、磁盤可以看成塊數組。
1、随機通路存儲器
随機通路存儲器分為兩類：靜态和動态。靜态RAM（即SRAM）比動态RAM（即DRAM）更快，但也貴得多。SRAM用來作為高速緩存存儲器，既可以在CPU晶片上，也可以在片下。DRAM用來作為主存以及圖形系統的幀緩沖區。
1)靜态RAM
a.SRAM将每個位存儲在一個雙穩态的存儲器單元裡。每個單元是用一個六半導體電路來實作的。可以無限期地保持在兩個不同的電壓配置或狀态之一。其他任何狀态都是不穩定的——從不穩定狀态開始，電路會迅速轉移到兩個穩定狀态中的一個。
b.原理類似于“倒轉的鐘擺”。
c.SRAM存儲器單元的雙穩态特性，隻要有電，他就會永遠保持它的值。
2)動态RAM
DRAM将每個位存儲為對一個電容的充電。DRAM存儲器單元對幹擾非常敏感。
3)傳統的DRAM
DRAM晶片中的單元（位）被分成d個超單元，每個超單元都由w個DRAM單元組成。
每個d*w的DRAM共有dw位資訊。超單元呗組織稱一個r行c列的長方形陣列，這裡rc=d。每個超單元有形如（i,j）的位址，這裡i代表行，j代表列。
資訊通過稱為引腳的外部連結器流入和流出晶片，每個引腳攜帶一個1位的信号。
每個DRAM晶片被連接配接到某個稱為存儲控制器的電路，這個電路可以一次傳送w位到每個DRAM晶片或一次從每個DRAM晶片傳出w位。為了讀出超單元（i,j）的内容發回給控制器作為響應。
電路設計者将DRAM組織稱二維陣列而不是線性數組的一個原因是降低晶片上位址引腳的數量。
二維陣列組織的缺點是必須分兩步發送位址，這增加了通路時間。
4）存儲器子產品
DRAM晶片包裝在存儲器子產品中，它是插到主機闆的擴充槽上的。常見包裝包括168個引腳的雙列直插存儲器子產品，它以64位為塊傳送資料到存儲控制器和從存儲控制器傳出資料，還包括72個引腳的單列直插存儲器子產品，它以32位為塊傳送資料。
通過将多個存儲器子產品連接配接到存儲控制器，能夠聚合主存。
5）增強的DRAM
>>快頁模式DRAM
>>擴充資料輸出DRAM
>>同步DRAM
>>雙倍資料速率同步DRAM
>>RambusDRAM（RDRAM）
>>視訊RAM
6）非易失性存儲器
a.RAM斷電丢失資料，是易失的；ROM是非易失的，統稱為隻讀存儲器。共有以下幾種類型：
PROM-可程式設計ROM，隻能被程式設計一次
EPROM-可擦寫可程式設計ROM，能夠被擦除和編寫的次數的數量級大概為1000次
EEPROM，電子可擦除PROM，能夠被程式設計的次數的數量級在100000次
b.閃存FLASH
基于EEPROM，為大量的電子裝置提供快速而持久的非易失性存儲。
應用場合：數位相機、手機、音樂播放器、PDA、筆記本、桌上型電腦、伺服器計算機系統。
c.存儲在ROM裝置中的程式通常被稱為固件，當一個計算機系統通電以後，他會運作存儲在ROM中的固件。
7）通路主存
a.總線是一組并行的導線，能攜帶位址、資料和控制信号。
b.總線的種類：
①系統總線——連接配接CPU和I/O橋
②存儲器總線——連接配接I/O橋和主存
③I/O總線：I/O橋将系統總線的電子信号翻譯成存儲器總線的電子信号，也将系統總線和存儲器總線連接配接到I/O總線。
2、磁盤存儲
磁盤是廣為應用的大量資料的儲存設備。
1）磁盤構造
>>盤片
>>表面：每個盤片有兩個表面
>>主軸：盤片中央，可旋轉
>>旋轉速率：通常5400~15000/min
>>磁道：同心圓
>>扇區：每個磁道被劃分為一組扇區
>>資料位：每個扇區包含相等數量的資料位，通常為512位元組
>>間隙：存儲用來辨別扇區的格式化位
>>磁盤驅動器-磁盤-旋轉磁盤
>>柱面：所有盤片表面上到主軸中心的距離相等的磁道的集合。 2）磁盤容量：一個磁盤上可以記錄的最大位數。決定因素如下：
記錄密度：位/英寸
磁道密度：道/英寸
面密度：位/平方英寸
其中，提高面密度即可提高容量。 磁盤容量計算公式：
3）磁盤操作
磁盤以扇區大小的塊來讀寫資料。
通路時間由三部分組成，通路一個磁盤扇區内容的平均時間為平均尋道時間，平均旋轉延遲和平均傳送時間之和。
a.尋道時間
即移動傳動臂所用的時間。
依賴于讀/寫頭以前的位置和傳動臂在盤面上移動的速度。
通常為3-9ms，最大可達20ms。 b.旋轉時間
即驅動器等待目标扇區的第一個位旋轉到讀/寫頭下
依賴于盤面位置和旋轉速度。
最大旋轉延遲=1/RPM X 60secs/1min (s)
平均旋轉時間是最大值的一半。 c.傳送時間
依賴于旋轉速度和每條磁道的扇區數目
平均傳送時間= 1/RPM x 1/(平均扇區數/磁道) x 60s/1min 4）邏輯磁盤塊
盤面，磁道，扇區，這個三元組唯一的辨別了對應的實體扇區。 5）連接配接到I/O裝置（I/O總線）
I/O總線連接配接了CPU，主存和I/O裝置。
通用串行總線USB：2.0最大帶寬60MB/S，3.0最大帶寬600MB/S
圖形卡（擴充卡）
主機總線擴充卡 6）通路磁盤
DMA：直接存儲器通路。裝置可以自己執行讀或者寫總線事務，而不需要CPU幹涉的過程。
CPU使用一種稱為存儲器映射I/O的技術來向I/O裝置發出指令。
3、固體磁盤
固态硬碟是一種基于閃存的存儲技術。差別于旋轉磁盤，固态磁盤沒有移動的部分。
1）結構
一個SSD包由一個或多個閃存晶片和閃存翻譯層組成：
閃存晶片——對應旋轉磁盤中機械驅動器
閃存翻譯層（硬體/固件裝置）——對應磁盤控制器 2）特點
由半導體構成，沒有移動的零件
随機通路時間比旋轉磁盤要快
能耗更低
更結實
更容易磨損
更貴 4、存儲技術優勢
不同的存儲技術有不同的價格和性能折中
不同存儲技術的價格和性能屬性以截然不同的速率變化着
增加密度進而降低成本比降低通路時間更容易
DRAM和磁盤的性能滞後于cpu的性能
6.2局部性
本節要求：
局部性原理：時間局部性，空間局部性（p429最後一段“存儲器山”）；
資料引用局部性；
取指令局部性。 局部性原理：一個編寫良好的計算機程式，常常傾向于引用臨近于其他最近引用過的資料項的資料項，或者最近引用過的資料項本身。其中包含空間局部性和時間局部性。 >>不同領域的應用
①硬體層：通過引入高速緩存存儲器來儲存最近被引用的指令和資料項，進而提高對主存的通路速度。
②作業系統級：系統使用主存作為虛拟位址空間最近被引用塊的高速緩存，用主存來緩存磁盤檔案系統中最近被使用的磁盤塊
③應用程式中：Web浏覽器将最近被引用的文檔放在本地磁盤上。 1、對程式資料引用的局部性
1）步長為k的引用模式：一個連續變量中，每隔k個元素進行通路，就被稱為步長為k的引用模式。
步長為1的引用模式：就是順序通路一個向量的每個元素，有時也被稱為順序引用模式，它是程式中 空間局部性常見和重要的來源。
>>一般來說，随着步長增加，空間局部性下降。 2）多元數組：見書中例子。
2、取指令的局部性
程式指令是存放在存儲器中的，CPU必須取出（讀出）這些指令。
但是代碼差別于程式資料的一個重要屬性是：在運作時它是不能被修改的。 3、局部性小結
量化評價一個程式中局部性的簡單原則：
①重複引用同一個變量的程式有良好的時間局部性
②對于具有步長為k的引用模式的程式，步長越小，空間局部性越好
③對于取指令來說，循環有好的時間和空間局部性。循環體越小，循環疊代次數越多，局部性越好。
6.3存儲器層次結構
本節要求：
系統觀“1+1>2”（舉一反三：對稱不對稱加密形成的混合加密系統，混合動力汽車）；
中心思想：每層儲存設備都下一層的“緩存”。 1、緩存
高速緩存：是一個小而快速的儲存設備，它作為存儲在更大、更慢的裝置中的資料對象的緩沖區域。
緩存：使用高速緩存的過程稱為緩存。
資料總是以塊大小為傳送單元在第k層與第k+1層之間來回拷貝。任一對相鄰的層次之間塊大小是固定的，但是其他的層次對之間可以有不同的塊大小。
特點：層越低，塊越大。 1）緩存命中
當程式需要第k+1層的某個資料對象d時，首先在目前存儲在第k層的一個塊中查找d，如果d剛好緩存在第k層中，就稱為緩存命中。
該程式直接從第k層讀取d，比從第k+1層中讀取d更快。 2）緩存不命中
即第k層中沒有緩存資料對象d。
這時第k層緩存會從第k+1層緩存中取出包含d的那個塊。如果第k層緩存已滿，就可能會覆寫現存的一個塊 <<替換（覆寫、驅逐）政策：
随機替換政策-随機犧牲一個塊
最近最少被使用替換政策LRU-犧牲最後被通路的時間距離現在最遠的塊。
3)緩存不命中的種類
a.強制性不命中/冷不命中
即第k層的緩存是空的（稱為冷緩存），對任何資料對象的通路都不會命中。 b.沖突不命中
由于一個放置政策：将第k+1層的某個塊限制放置在第k層塊的一個小的子集中，這就會導緻緩存沒有滿，但是那個對應的塊滿了，就會不命中。 c.容量不命中
當工作集的大小超過緩存的大小時，緩存會經曆容量不命中，就是說緩存太小了，不能處理這個工作集。 4）緩存管理
某種形式的邏輯必須管理緩存，而管理緩存的邏輯可以是硬體、軟體，或者兩者的集合。
2、存儲器層次結構概念小結
6.4高速緩存存儲器
本節要求：
高速緩存結構（S，E，B，m），高速緩存組，高速緩存行、塊；映射、命中、緩存管理。 ①L1高速緩存：位于CPU寄存器檔案和主存之間，通路速度2-4個時鐘周期
②L2高速緩存：位于L1高速緩存和主存之間，通路速度10個時鐘周期
③L3高速緩存：位于L2高速緩存和主存之間，通路速度30或40個時鐘周期
1、通用的高速緩存存儲器結構
高速緩存是一個高速緩存組的數組，它的結構可以用元組（S,E,B,m）來描述：
S：這個數組中有S=2^s個高速緩存組
E：每個組包含E個高速緩存行
B：每個行是由一個B=2^b位元組的資料塊組成的
m：每個存儲器位址有m位，形成M=2^m個不同的位址 除此之外還有标記位和有效位：
有效位：每個行有一個有效位，指明這個行是否包含有意義的資訊
标記位：t=m-(b+s)個，唯一的辨別存儲在這個高速緩存行中的塊
組索引位：s
塊偏移位：b 高速緩存的結構将m個位址劃分成了t個标記位，s個組索引位和b個塊偏移位。
1）高速緩存的大小/容量C：指所有塊的大小的和，不包括标記位和有效位，是以：
C=S*E*B 2）工作過程
S,B将m個位址位分為了三個字段：
先通過s個組索引位找到這個字必須存儲在哪個組中
然後t個标記位告訴我們這個組中的哪一行包含這個字（當且僅當設定了有效位并且該行的标記位與位址中的标記位相比對時）
b個塊偏移位給出來在B個位元組的資料塊中的字偏移 2、直接映射高速緩存
根據E（每個組的高速緩存行數）劃分高速緩存為不同的類，E=1的稱為直接映射高速緩存。
高速緩存确定一個請求是否命中，然後取出被請求的字的過程，分為三步：
1.組選擇
2.行比對
3.字抽取 1）組選擇
高速緩存從w的位址中間抽取出s個組索引位
組索引位：一個對應于一個組号的無符号整數。
類比：高速緩存-關于組的一位數組，組索引位就是到這個數組的索引。 2）行比對
判斷緩存命中的兩個充分必要條件：
該行設定了有效位
高速緩存行中的标記和w的位址中的标記相比對 3）字選擇
塊-關于位元組的數組，位元組偏移是到這個數組的一個索引。 4）緩存不命中時的行替換
5）後運作中的直接映射高速緩存
标記位和索引位連起來唯一的辨別了存儲器中的每個塊
映射到同一個高速緩存組的塊由标記位唯一地辨別 >>CPU執行讀的一系列動作
1.先利用索引位，确定是針對哪個組
2.然後看對應的組是否有效：
1）如果無效則緩存不命中，高速緩存從存儲器或低一層中取出要找的塊，存儲在對應的組中，再把有效位置1，傳回需要的值
2）如果有效，再根據标記找是否有比對的标記：
①如果有，則緩存命中，傳回需要的值
②如果沒有，則替換行，然後傳回。 6）直接映射高速緩存中的沖突不命中
抖動：高速緩存反複的加載和驅逐相同的高速緩存塊的組
原因：這些塊被映射到了同一個高速緩存組。
解決方法：在每個數組的結尾放B位元組的填充進而使得他們映射到不同的組。 3、組相聯高速緩存
E路組相聯高速緩存：1<E<C/B 1）組選擇
2）行比對和字選擇：形式是(key, value)，用key作為标記和有效位去比對，比對上了之後傳回value。
重要思想：組中的任意一行都可以包含任何映射到這個組的存儲器塊，是以告訴緩存必須搜尋組中的每一行。 判斷比對的标準依舊是兩個充分必要條件：①
有效②
标記比對
3）行替換：有空行替換空行，沒有空行，應用替換政策:
随機替換
最不常使用政策LFU：替換在過去某個時間視窗内引用次數最少的那一行。
最近最少使用政策LRU：替換最後一次通路時間最久遠的那一行。
4、全相聯高速緩存（E=C/B）
1）組選擇：隻有一個組，預設組0，沒有索引位，位址隻被劃分成了一個标記和一個塊偏移。
2）行比對和字選擇：同組相聯。
<<隻适合做小的高速緩存。
5、寫
1）寫命中時，更新低一層中的拷貝的方法：
a.直寫，立即将w的高速緩存塊協會到緊接着的低一層中.但是每次寫都會引起總線流量。
b.寫回，隻有當替換算法要驅逐更新過的塊時，才寫到緊接着的低一層中。符合局部性原理，顯著的減少總線流量。但是增加了複雜性，必須為每個高速緩存行維護一個額外的修改位。
2）寫不命中的處理方法
a.寫配置設定---通常寫回對應:加載相應的低一層中的塊到高速緩存中，然後更新這個高速緩存塊。
b.非寫配置設定---通常直寫對應:避開高速緩存，直接把這個字寫在低一層中。 6、真實的高速緩存層次結構
高速緩存既儲存資料，也儲存指令。
隻儲存指令的：i-cache
隻儲存程式資料的：d-cache
既儲存指令又儲存資料的：統一的高速緩存 7、高速緩存參數的性能影響
1）性能：
不命中率 = 不命中數量/引用數量
命中率 = 1 - 不命中率
命中時間
不命中處罰：因為不命中所需要的額外的時間 2）具體影響
高速緩存大小：命中率+，命中時間+
塊大小：空間局部性+，命中率+，高速緩存行數-，時間局部性-，不命中處罰+
相聯度：E值大，抖動-，價格+，命中時間+，不命中處罰+，控制邏輯+【折中為不命中處罰低的，相聯度低，不命中處罰高的，使用高相聯度】
寫政策：越往下，越可能用寫回而不是直寫
6.5編寫高速緩存友好的代碼
1.基本方法
讓最常見的情況運作的快
在每個循環内部緩存不命中數量最小 2.重要問題
對局部變量的反複引用是好的（時間局部性）
步長為1的引用模式是好的（空間局部性） 6.6存儲器山
這是一個重要的了解概念。幫助我們了解計算機系統底層存儲的結構。
======================================================================
遇到的問題
6.11/6.12/6.13不太能夠了解解題思路，覺得有點費解。前面的題目比較好了解，對照一些圖、公式、表格裡的小結就能做好。這種數學型的計算題還是我比較擅長的。我一直認為學習的時候了解學到的東西永遠要比記憶的來的知識要牢固。但是對于底層的一些比較抽象的概念我還是不太懂，也很少能夠在平時學習用到，不知道學習它的意義何在，是以學起來一直會走神，效率特别低，完全是因為要求學才去學。希望之後會有一些對代碼什麼的感悟實踐能去動手操作讓我進入狀态吧。
另外，總線的部分以前在學彙編的時候緒論那節課老師有稍微提到一些，ROM、RAM的差別在上上學期的數字邏輯電路最後一章也有稍微提及。但由于不是考核重點，學過也就忘了，這次的再次學習讓我對計算機學科的内部綜合有了一些了解，明白了有的東西不考核不代表就不重要，沒學紮實的話，欠下的債總是要還的TAT。後面補學起來還是很費勁的。
參考文獻
1、《深入了解作業系統》pdf
2、闫佳歆同學的部落格總線部分的圖以及後兩節的知識概括（部落格連結：http://www.cnblogs.com/20135202yjx/p/4907828.html）
3、《數字邏輯電路》（用于參照了解）
轉載于:https://www.cnblogs.com/paperfish/p/4909669.html