計算機(jī)技術(shù)的成功很大程度上源自于存儲技術(shù)的巨大進(jìn)步。本章首先對一些基本的存儲技術(shù)進(jìn)行了介紹伟桅，然后介紹了編寫良好的程序所具有的局部性原理，最后介紹了存儲器的層次結(jié)構(gòu)叽掘，緩解了內(nèi)存速度過慢無法和處理器速度相匹配的問題楣铁。
CPU執(zhí)行指令，而存儲器系統(tǒng)為CPU存放指令和數(shù)據(jù)更扁。存儲器系統(tǒng)(memory system)是由具有不同容量盖腕、成本和訪問時間的存儲設(shè)備組成的層次結(jié)構(gòu)。
存儲器層次結(jié)構(gòu)對應(yīng)用程序的性能有巨大影響疯潭。如果數(shù)據(jù)存儲在寄存器中赊堪，那么0個始終周期內(nèi)就能訪問到它們；如果存儲在高速緩存中竖哩，則需要4 ~ 75個周期；如果存儲在主存中脊僚，則需要上百個周期相叁；如果存儲在磁盤上遵绰，則需要幾千萬個周期。
之所以會有這樣的差異增淹，是因為不同存儲器中使用的存儲技術(shù)不同椿访。基本的存儲技術(shù)包括SRAM存儲器虑润，DRAM存儲器成玫，ROM存儲器，磁盤以及固態(tài)硬盤拳喻。
存儲技術(shù)
隨機(jī)訪問存儲器
隨機(jī)訪問存儲器(Random-Access Memory, RAM)分為兩類：靜態(tài)的和動態(tài)的哭当。靜態(tài)RAM(SRAM)比動態(tài)RAM(DRAM)更快，但也更貴冗澈。SRAM常用來作為高速緩存存儲器钦勘，DRAM常用來作為主存以及圖形系統(tǒng)的幀緩沖區(qū)。
- SRAM：將每個位存儲在一個雙穩(wěn)態(tài)存儲器單元中亚亲，其中每個單元用一個六晶體管電路來實現(xiàn)彻采。雙穩(wěn)態(tài)是指該存儲器單元可以無限期地保持在兩個不同的電壓配置之一，其他任何狀態(tài)都是不穩(wěn)定的捌归。只要有電肛响，SRAM存儲器單元就會保持它的值，即使有干擾擾亂電壓惜索，當(dāng)干擾消除時電路就會恢復(fù)到穩(wěn)定值终惑。
- DRAM：將每個位存儲為對一個電容的充電。每個單元由一個電容柜和一個訪問晶體管組成门扇。與SRAM不同雹有，DRAM存儲器單元對干擾非常敏感，當(dāng)電容的電壓被擾亂之后臼寄，它就不會恢復(fù)了霸奕。暴露在光線下會導(dǎo)致電容電壓改變，實際上吉拳，數(shù)碼相機(jī)中的傳感器本質(zhì)上就是DRAM單元的陣列质帅。
非易失性存儲器
如果斷電，DRAM和SRAM會丟失它們的信息留攒，而非易失性存儲器即使在關(guān)電后煤惩，仍然保存著它們的信息。現(xiàn)在有很多種非易失性存儲器炼邀，雖然有的可以讀也可以寫魄揉，但整體上被稱為只讀存儲器(ROM)。
可編程ROM(PROM)只能被編程一次拭宁÷逋耍可擦除可編程ROM(EPROM)能夠被擦除和重編程的次數(shù)可達(dá)千次瓣俯。電子可擦除PROM(EEPROM)能夠被編程的次數(shù)可達(dá)次。
閃存(flash memory)是一種基于EEPROM的存儲技術(shù)兵怯，為大量的電子設(shè)備提供快速而持久的非易失性存儲彩匕。
磁盤存儲
RAM必須在有電的時候才能存取數(shù)據(jù)，而磁盤則能永久存儲大量數(shù)據(jù)媒区。磁盤是一種機(jī)械的非易失性存儲設(shè)備驼仪。不過從磁盤上讀數(shù)據(jù)的時間為毫秒級，比DRAM慢了10萬倍袜漩，比SRAM慢了100萬倍绪爸。
磁盤由盤片和主軸構(gòu)成。每個盤片有兩面(也稱表面)噪服，表面覆蓋著磁性記錄材料毡泻。盤片中央有一個可以旋轉(zhuǎn)的主軸，使得盤片以固定的旋轉(zhuǎn)速率旋轉(zhuǎn)粘优，通常為5400 ~ 15000轉(zhuǎn)每分鐘仇味。磁盤通常包含一個或多個疊放在一起的盤片，封裝在一個密封的包裝里雹顺。
盤片的每個表面由一組稱為磁道的同心圓組成丹墨。每個磁道被劃分為一組扇區(qū)。每個扇區(qū)包含相等數(shù)量的數(shù)據(jù)位(通常是512字節(jié))嬉愧，編碼在扇區(qū)上的磁性材料中贩挣。扇區(qū)之間由一些間隙隔開，間隙中不存儲數(shù)據(jù)位没酣，而是用來存儲標(biāo)識扇區(qū)的格式化位王财。
通常磁盤又被稱為旋轉(zhuǎn)磁盤或機(jī)械硬盤，以區(qū)別于基于閃存的固態(tài)硬盤裕便，固態(tài)硬盤是沒有移動部分的绒净。
一個磁盤上可以記錄的最大位數(shù)稱為磁盤容量。
磁盤通過讀寫頭來讀寫存儲在磁性表面的位偿衰。讀寫頭連接到一個傳動臂上挂疆，通過沿著半徑方向移動傳動臂，可以將讀寫頭定位在盤片的任何磁道上下翎。在這個過程中讀寫頭垂直排列缤言，一致行動。
磁盤讀寫數(shù)據(jù)(訪問扇區(qū))的時間主要受以下因素影響：
- 尋道時間：讀寫數(shù)據(jù)時视事，傳動臂首先要將讀寫頭定位到包含目標(biāo)扇區(qū)的磁道上胆萧，這個移動過程所花的時間稱為尋道時間。尋道時間主要依賴于讀寫頭的初始位置和傳動臂在盤面上移動的速度郑口。
- 旋轉(zhuǎn)時間：一旦讀寫頭移動到目標(biāo)磁道上鸳碧，就需要等待目標(biāo)扇區(qū)的第一個位旋轉(zhuǎn)到讀寫頭下盾鳞，這個過程所花的時間稱為旋轉(zhuǎn)時間犬性。最壞的情況下瞻离，讀寫頭剛錯過目標(biāo)扇區(qū)，必須等待磁盤轉(zhuǎn)一整圈乒裆。
- 傳送時間：當(dāng)目標(biāo)扇區(qū)的第一個位位于讀寫頭下時套利，驅(qū)動器開始讀或?qū)懺撋葏^(qū)的內(nèi)容。
邏輯磁盤塊：
為了對操作系統(tǒng)隱藏磁盤構(gòu)造的復(fù)雜性鹤耍，現(xiàn)代磁盤將它們的構(gòu)造呈現(xiàn)為一個簡單的視圖肉迫，一個B個扇區(qū)大小的邏輯塊的序列，編號為0,1稿黄，...喊衫，B-1。
磁盤封裝中有一個小的硬件設(shè)備杆怕，稱為磁盤控制器族购，維護(hù)著邏輯塊號與實際物理磁盤扇區(qū)之間的映射關(guān)系。
當(dāng)操作系統(tǒng)想要執(zhí)行一個I/O操作時陵珍，例如讀一個磁盤扇區(qū)的數(shù)據(jù)到主存寝杖，操作系統(tǒng)會發(fā)送一個命令到磁盤控制器，讓它讀某個邏輯塊號互纯∩唬控制器執(zhí)行一個快速表查找，將一個邏輯塊號翻譯成一個(盤面留潦、磁道只盹、扇區(qū))三元組，唯一標(biāo)識了對應(yīng)的物理扇區(qū)兔院≈潮埃控制器上的硬件會解釋這個三元組，將讀寫頭移到適當(dāng)?shù)闹娓讶椋却葏^(qū)移動到讀寫頭下懦鼠，將讀寫頭感知到的位放到控制器上的一個小緩沖區(qū)中，然后將它們復(fù)制到主存中屹堰。
固態(tài)硬盤
固態(tài)硬盤(Solid Sate Disk, SSD)是一種基于閃存的存儲技術(shù)肛冶，由一個或多個閃存芯片以及閃存翻譯層組成。閃存芯片替代了磁盤中的機(jī)械驅(qū)動器扯键，閃存翻譯層替代了磁盤控制器睦袖，將對邏輯塊的請求翻譯成對底層物理設(shè)備的訪問。
如圖所示荣刑，一個閃存由B個塊組成馅笙，每個塊又由P個頁組成伦乔。通常，頁的大小為512B ~ 4KB董习，塊的大小為16KB ~ 512KB烈和。
數(shù)據(jù)在SSD中是以頁為單位讀寫的。在寫入數(shù)據(jù)前皿淋，需要對一頁所屬的塊進(jìn)行擦除招刹，即將該塊中所有位都設(shè)置為1，而寫入操作其實就是將部分位置設(shè)置為0窝趣。
當(dāng)擦除次數(shù)過多后疯暑，塊會因磨損而損壞。為了減少這種磨損帶來的影響哑舒，閃存翻譯層使用一種平均磨損算法妇拯，來將擦除平均分布在所有塊上來最大化每個塊的壽命。
局部性原理
一個編寫良好的程序通常要求具有良好的局部性洗鸵。也就是它們傾向于引用最近被引用過的數(shù)據(jù)項鄰近的數(shù)據(jù)項越锈，或最近引用過的數(shù)據(jù)項本身，這種傾向被稱為局部性原理预麸，對硬件和軟件系統(tǒng)的設(shè)計和性能有極大影響瞪浸。
局部性分為時間局部性和空間局部性。時間局部性是指被引用過一次的數(shù)據(jù)項很可能在不遠(yuǎn)的將來再被多次引用吏祸《云眩空間局部性是指一個內(nèi)存位置被引用了一次，那么程序很可能在不遠(yuǎn)的將來引用它附近的內(nèi)存位置贡翘。
e.g. 比如遍歷讀取二維數(shù)組的每個元素時蹈矮，采樣行優(yōu)先順序讀的程序的空間局部性就比采用列優(yōu)先順序讀的程序的空間局部性好，因為二維數(shù)組在內(nèi)存中是按照行優(yōu)先順序存儲的鸣驱。
存儲器層次結(jié)構(gòu)
為了將不同存儲技術(shù)的差異性和計算機(jī)軟件對局部性的要求兩者結(jié)合起來泛鸟，人們構(gòu)造了存儲器層次結(jié)構(gòu)來組織存儲器系統(tǒng)。
存儲器層次結(jié)構(gòu)的中心思想是：每一層都緩存來自下一層的數(shù)據(jù)對象踊东。
數(shù)據(jù)總是以塊大小為傳送單元在第k層和第k+1層之間來回復(fù)制北滥。
- 緩存命中：當(dāng)程序需要第k+1層的某個數(shù)據(jù)對象d時，它首先在當(dāng)前存儲在第k層的塊中查找d闸翅，若d剛好緩存在第k層再芋，就是緩存命中。這時程序直接從第k層讀取d坚冀。
- 緩存不命中：如果第k層沒有緩存數(shù)據(jù)對象d济赎，就是緩存不命中。此時第k層的緩存從第k+1層緩存中取出包含d的那個塊，如果第k層的緩存已經(jīng)滿了司训，可能就會覆蓋現(xiàn)存的一個塊构捡。第k層從第k+1層取出目標(biāo)塊后，程序就可以像前面一樣從第k層讀出d了壳猜。
覆蓋現(xiàn)存的一個塊的過程稱為替換或驅(qū)逐這個塊勾徽。決定該替換哪個塊是由替換策略控制的，比如隨機(jī)替換策略蓖谢、最近最少被使用(LRU)替換策略捂蕴。
高速緩存
早期計算機(jī)系統(tǒng)的存儲器層次結(jié)構(gòu)只有三層：CPU寄存器譬涡、DRAM主存儲器和磁盤闪幽。但是，隨著CPU和主存之間的性能差距不斷增大涡匀，系統(tǒng)設(shè)計者被迫在CPU寄存器和主存之間插入了高速緩存存儲器盯腌。
讀的問題：
高速緩存關(guān)于讀的操作非常簡單。首先陨瘩，在高速緩存中查找所需字w的副本腕够，如果命中，立即返回字w給CPU舌劳；如果不命中帚湘，從存儲器層次結(jié)構(gòu)中較低層取出包含字w的塊，將這個塊存到某個高速緩存行中(可能會驅(qū)逐一個有效的行)甚淡，然后返回字w大诸。
寫的問題：
寫的情況要復(fù)雜一些。假設(shè)要寫一個已經(jīng)緩存了的字w (寫命中)贯卦，在高速緩存更新了w的副本之后资柔，還需要更新它在層次結(jié)構(gòu)下一層的副本。
- 直寫：立即將w的高速緩存塊寫回到下一層中撵割，缺點是每次寫都會引起總線流量贿堰。
- 寫回：盡可能推遲更新，直到替換算法要驅(qū)逐這個更新過的塊時才把它寫到下一層中啡彬。這樣顯著減少了總線流量羹与，但是增加了復(fù)雜性，因為這樣高速緩存行需要維護(hù)一個額外的修改位庶灿，表明這個高速緩存塊是否被修改過纵搁。
在寫的時候也會出現(xiàn)寫不命中的問題，這是有兩種方法：
- 寫分配：加載相應(yīng)的下一層中的塊到高速緩存中跳仿，然后更新這個高速緩存塊诡渴。寫分配試圖利用寫的空間局部性，但是缺點是每次不命中都會導(dǎo)致一個塊從低一層傳送到高速緩存。
- 非寫分配：避開高速緩存妄辩，直接把這個字寫到下一層中惑灵。
建議程序員在心里采用一個使用寫回和寫分配的高速緩存模型。
