第三章 多層次的存儲器#
本章內容較多，主要包括各種存儲器及存儲方式存儲器，其中重點為存儲器基本概念、DRAM、SRAM、cache、命中率與平均訪問時間、主存與 cache 映射方式和虛存等
3.1 存儲器概述#
3.1.1 存儲器的分類#
- 存儲器是計算機系統中的記憶設備，用來存放程序和數據。
- 存儲介質：目前主要采用半導體器件和磁性材料。
- 存儲位元：一個雙穩態半導體電路或一個 CMOS 晶體管或磁性材料的存儲元，均可以存儲一位二進制代碼。這個二進制代碼位是存儲器中最小的存儲單位，稱為存儲位元
- 存儲單元：由若干個存儲位元組成一個存儲單元。由許多存儲單元組成一個存儲器。
根據存儲材料的性能和使用方法的不同，存儲器有不同分類方法
（1）根據存儲介質分類，分為磁表面/半導體存儲器
（2）根據存取方式分類，分為隨機/順序存取（磁帶）
（3）根據讀寫功能分類，分為只讀存儲器 (ROM) 和隨機讀寫存儲器 (RAM)
（4）根據信息的易失性分類：分為易失性和非易失性的
（5）根據存儲器系統中的作用分類：分為主 / 輔 / 緩 / 控
3.1.2 存儲器的分級#
當前存儲器的特點：
-
速度快的存儲器價格貴，容量小；
-
價格低的存儲器速度慢，容量大。
在計算機存儲器體系結構設計時，我們希望存儲器的容量大、速度快、價格低，那麼在存儲器系統設計時，應當在存儲器容量，速度和價格方面的因素作折中考慮，建立了多級存儲器體系結構，如下圖所示
-
高速緩衝存儲器簡稱cache，它是計算機系統中的一個高速小容量半導體存儲器
-
主存儲器簡稱主存，是計算機系統的主要存儲器，用來存放計算機運行期間的大量程序和數據。
-
外存儲器簡稱外存，它是大容量輔助存儲器。
3.1.3 主存儲器的技術指標#
- 字存儲單元：存放一個機器字的存儲單元，相應的單元地址叫字地址。
- 字節存儲單元：存放一個字節的單元，相應的地址稱為字節地址。
- 存儲容量：指一個存儲器中可以容納的存儲單元總數。存儲容量越大，能存儲的信息就越多。
- 存取時間（又稱存儲器訪問時間）：指一次讀操作命令發出到該操作完成，將數據讀出到數據總線上所經歷的時間。通常取寫操作時間等於讀操作時間，故稱為存儲器存取時間。
- 存儲周期：指連續啟動兩次讀操作所需間隔的最小時間。通常，存儲周期略大於存取時間，其時間單位為 ns。
- 存儲器帶寬：單位時間里存儲器所存取的信息量，通常以位 / 秒或字節 / 秒做度量單位。
3.2 SRAM 存儲器（靜態讀寫存儲器）#
目前廣泛使用的主存（內部存儲器）是半導體存儲器。根據信息存儲的機理不同可以分為兩類
- 靜態讀寫存儲器 (SRAM)：存取速度快、但存儲容量不如 DRAM 大
- 動態讀寫存儲器 (DRAM)：存取速度略慢、存儲容量比 SRAM 大。
3.2.1 基本的靜態存儲元陣列#
- 存儲位元: 一個鎖存器（觸發器）。只要直流供電電源一直加到這個記憶電路上，它就無限期地保持記憶的 1 狀態或 0 狀態。如果電源斷電，那麼存儲的數據（1 或 0）就會丟失。
- 三組信號線（重點）：地址線、數據線（行線、列線）、控制線
- 地址線：若為 6 條，則指定了存儲器的容量為 2^6^ = 64 個存儲單元
- 數據線：若為 4 條，則制定了存儲器的字長為 4 位，因此存儲位元總數為 64×4 = 256。
- 控制線：R/~W 控制線，指定了對存儲器進行讀還是寫
地址譯碼器輸出有 64 條選擇線，我們稱之為行線，它的作用是打開每個存儲位元的輸入與非門。
3.2.2 基本的 SRAM 邏輯結構#
-
SRAM 芯片大多采用雙譯碼方式，以便組織更大的存儲容量。
-
采用了二級譯碼：將地址分成 x 向、y 向兩部分如圖所示。
-
存儲體（256 行 ×128 列 ×8 位）存儲陣列
-
地址譯碼器
- 采用雙譯碼的方式（減少選擇線的數目）。
- A0~ A7 為行地址譯碼線
- A8~A14 為列地址譯碼線
-
雙向數據線為 8 條
3.2.3 讀 / 寫周期波形圖#
例 1: 圖為 SRAM 的寫入時序圖。其中 R/W 是讀 / 寫命令控制線，當 R/W 線為低電平時，存儲器按給定地址把數據線上的數據寫入存儲器。請指出圖中寫入時序中的錯誤，並畫出正確的寫入時序圖。
解：寫入存儲器的時序信號必須同步。通常，當 R/W 線加負脈衝時，地址線和數據線的電平必須是穩定的。當 R/W 線達到低電平時，數據立即被存儲。因此，當 R/W 線處於低電平時，如果數據線改變了數值，那麼存儲器將存儲新的數據⑤。同樣，當 R/W 線處於低電平時地址線如果發生了變化，那麼同樣數據將存儲到新的地址②或③。
正確的寫入時序圖見圖 (b)。
3.3 DRAM 存儲器（動態讀寫存儲器）#
SRAM 存儲器的存儲元是一個觸發器，它具有兩個穩定的狀態。
而 DRAM 存儲器的存儲元是由一個 MOS 晶體管和電容器組成的記憶電路。
MOS 管做為開關使用所存儲的信息為 1 或 0 則是由電容器上的電荷量來體現。
- 當電容器充滿電荷時，代表存儲了 1；
- 當電容器放電沒有電荷時，代表存儲了 0
DRAM 與 SRAM 不同的是
- 增加了行地址鎖存器和列地址鎖存器。由於 DRAM 存儲器容量很大，地址線寬度相應要增加，這勢必增加芯片地址線的管腳數目。為避免這種情況，採取的辦法是分時傳送地址碼。若地址總線寬度為 10 位，先傳送地址碼 A0～A9，由行選通信號 RAS 打入到行地址鎖存器；然後傳送地址碼 A10～A19，由列選通信號 CAS 打入到列地址鎖存器。芯片內部兩部分合起來，地址線寬度達 20 位，存儲容量為 1M×4 位。
- 增加了刷新計數器和相應的控制電路。DRAM 讀出後必須刷新，而未讀寫的存儲元也要定期刷新，而且要按行刷新，所以刷新計數器的長度等於行地址鎖存器。刷新操作與讀 / 寫操作是交替進行的，所以通過 2 選 1 多路開關來提供刷新行地址或正常讀 / 寫的行地址。
3.3.3 讀 / 寫周期、刷新周期（重點）#
讀 / 寫周期#
讀周期、寫周期的定義是從行選通信號 RAS 下降沿開始，到下個 RAS 信號的下降沿為止的時間，也就是連續兩個讀周期的時間間隔。通常為控制方便，讀周期和寫周期時間相等。
刷新周期#
DRAM 存儲位元是基於電容器上的電荷量存儲，這個電荷量隨著時間和溫度而減少，因此必須定期地刷新，以保持它們原來記憶的正确信息。
刷新操作有兩種刷新方式： 集中式刷新與分散式刷新
集中式刷新#
DRAM 的所有行在每一個刷新周期中都被刷新。 例如刷新周期為 8ms 的內存來說，所有行的集中式刷新必須每隔 8ms 進行一次。為此將 8ms 時間分為兩部分：前一段時間進行正常的讀 / 寫操作，後一段時間（8ms 至正常讀 / 寫周期時間）做為集中刷新操作時間。
分散式刷新#
每一行的刷新插入到正常的讀 / 寫周期之中。 例如 p70 圖 3.7 所示的 DRAM 有 1024 行，如果刷新周期為 8ms，則每一行必須每隔 8ms÷1024=7.8us 進行一次。分散式刷新不存在死時間！
3.4 只讀存儲器（ROM）和閃速存儲器 (FLASH)#
1、掩模 ROM（MROM)#
存儲內容固定的 ROM，由生產廠家提供產品。 一旦 ROM 芯片做成，就不能改變其中的存儲內容 用於存儲廣泛使用的具有標準功能的程序或數據，或用戶定做的具有特殊功能的程序或數據 （這些程序或數據均使用二進制碼）
- 優點：可靠性和集成度高，價格便宜
- 缺點：不能重寫
2、可編程 ROM#
用戶可修改其存儲內容
根據編程操作的不同，可編程 ROM 可分為
- 一次可編程 (PROM)
特點：用戶可自行改變產品中某些存儲元，用戶可編程一次。
優點：可以根據用戶需要編程
缺點：只能一次性改寫 - 光擦可編程 (EPROM)
存儲內容可以根據需要寫入，當需要更新時將原存儲內容抹去，再寫入新的內容。 - 電擦可編程 (EEPROM)
3、FLASH 存儲器#
- FLASH 存儲器也翻譯成閃速存儲器，它是高密度非易失性的讀 / 寫存儲器。
- 高密度意味著它具有巨大比特數目的存儲容量。
- 非易失性意味著存放的數據在沒有電源的情況下可以長期保存。
- 既有 RAM 的優點，又有 ROM 的優點，稱得上是存儲技術劃時代的進展。
FLASH 存儲器的基本操作有編程操作、讀取操作、擦除操作
3.5 並行存儲器（重點）#
- 由於 CPU 和主存儲器之間在速度上是不匹配的，這種情況成為限制高速計算機設計的主要問題。
- 為了提高 CPU 和主存之間的數據傳輸率，除了主存采用更高速的技術來縮短讀出時間外，還可以采用並行技術的存儲器。
- 雙端口存儲器 ——空間並行技術
- 多模塊交叉存儲器 ——時間並行技術
3.5.1 雙端口存儲器#
1、雙端口存儲器的邏輯結構#
雙端口存儲器由於同一個存儲器具有兩組相互獨立的讀寫控制電路而得名。
由於進行並行的獨立操作，因此是一種高速工作的存儲器，在科研和工程中非常有用。
舉例說明，雙端口存儲器 IDT7133 的邏輯框圖。如下頁圖。
2、無衝突讀寫控制#
- 當兩個端口的地址不相同時，在兩個端口上進行讀寫操作，一定不會發生衝突。
- 當任一端口被選中驅動時，就可對整個存儲器進行存取，每一個端口都有自己的片選控制 (CE) 和輸出驅動控制 (OE)。
- 讀操作時，端口的 OE (低電平有效) 打開輸出驅動器，由存儲矩陣讀出的數據就出現在 I/O 線上。
3、有衝突讀寫控制#
- 當兩個端口同時存取存儲器同一存儲單元時，便發生讀寫衝突。
- 為解決此問題，特設置了 BUSY 標志。在這種情況下，片上的判斷邏輯可以決定對哪個端口優先進行讀寫操作，而對另一個被延遲的端口置 BUSY 標志 (BUSY 變為低電平)，即暫時關閉此端口。
3.5.2 多模塊交叉存儲器#
1、存儲器的模塊化組織#
一個由若干個模塊組成的主存儲器是線性編址的。這些地址在各模塊中如何安排，有兩種方式：一種是順序方式，一種是交叉方式
[例] M0－M3 共四個模塊，則每個模塊 8 個字
順序方式： M0：0-7
M1：8-15
M2：16-23
M3：24-31
5 位地址組織如下： X X X X X
高位選模塊，低位選塊內地址
- 特點：某個模塊進行存取時，其他模塊不工作。
- 優點：某一模塊出現故障時，其他模塊可以照常工作，通過增添模塊來擴充存儲器容量比較方便。
- 缺點：各模塊串行工作，存儲器的帶寬受到了限制。
[例] M0－M3 共四個模塊，則每個模塊 8 個字
交叉方式： M0：0，4，…… 除以 4 餘數為 0
M1：1，5，…… 除以 4 餘數為 1
M2：2，6，…… 除以 4 餘數為 2
M3：3，7，…… 除以 4 餘數為 3
5 位地址組織如下： X X X X X
高位選塊內地址，低位選模塊
- 特點：連續地址分布在相鄰的不同模塊內，同一個模塊內的地址都是不連續的。
- 優點：對連續字的成塊傳送可實現多模塊流水式並行存取，大大提高存儲器的帶寬。使用場合為成批數據讀取。
2、多模塊交叉存儲器的基本結構#
下圖為四模塊交叉存儲器結構框圖。主存被分成 4 個相互獨立、容量相同的模塊 M0，M1，M2，M3，每個模塊都有自己的讀寫控制電路、地址寄存器和數據寄存器，各自以等同的方式與 CPU 傳送信息。在理想情況下，如果程序段或數據塊都是連續地在主存中存取，那麼將大大提高主存的訪問速度。
3.6 cache 存儲器（重點）#
3.6.1 cache 基本原理#
1、cache 的功能#
- 為了解決CPU 和主存之間的速度不匹配問題而采用的一項重要技術
- 介於 CPU 和主存之間的小容量高速緩衝存儲器
- 基於程序訪問的局部性原理
- 能高速地向 CPU 提供指令和數據，從而加快了程序的執行速度。
- 為追求高速，包括管理在內的全部功能由硬件實現。
程序訪問的局部性原理#
在一個較短的時間間隔內，程序對局部範圍的存儲器地址的頻繁訪問，而對局部範圍以外的地址訪問甚少的現象，稱為程序的局部性。
一般 cache 采用高速的 SRAM 製作，其價格比主存貴，但因其容量遠小於主存，因此能較好地解決速度和價格的矛盾。
2、cache 基本原理#
- cache 的設計依據這次訪問過的數據，下次有很大的可能也是訪問附近的數據。(程序訪問的局部性)
- CPU 與 Cache 之間的數據交換是以字為單位
- 主存與 Cache 之間的數據交換是以塊為單位
- CPU 讀取內存中一個字時，便發出此字的內存地址到 Cache 和主存。此時 Cache 控制邏輯依據地址判斷此字當前是否在 Cache 中。若是，此字立即傳送給 CPU; 若非，則用主存讀周期把此字從主存讀出送到 CPU，與此同時，把含有這個字的整個數據塊從主存讀出送到 cache 中。
下圖中，cache 分為 4 行，每行 4 個字。分配給 cache 的地址存在一個相聯存儲器 CAM中，它是按內容尋址的存儲器。當 CPU 執行訪存指令時，就把所要訪問的字的地址送到 CAM 和主存。送到 CAM 的地址按內容進行比較判斷，若該字不在 cache 中，則從主存找到這個字，並將該字從主存傳送到 CPU。與此同時，把包含該字的前後相繼的 4 個字的一行數據送入 cache。
3、cache 結構#
- Cache 的數據塊稱為行，用 L~i~ 表示，其中 i=0, 1, … , m-1
- 主存的數據塊稱為塊，用 B~j~ 表示，其中 j=0, 1, … , n-1
- 行與塊是等長的，每行 (塊) 包含 k 個主存字
- Cache 由數據存儲器和標籤存儲器組成
- 數據存儲器：存放主存一個數據塊的數據
- 標籤存儲器：保存數據所在主存的地址信息
4、命中與未命中#
命中：
- 主存塊調入緩存
- 主存塊與緩存塊建立了對應關係
- 用標記記錄與某緩存塊建立了對應關係的主存塊號
未命中：
- 主存塊未調入緩存
- 主存塊與緩存塊未建立對應關係
命中率：
- 從 CPU 來看，增加一個 cache 的目的，就是在性能上使主存的平均讀出時間盡可能接近 cache 的讀出時間。
- 為了達到這個目的，在所有的存儲器訪問中由 cache 滿足 CPU 需要的部分應占很高的比例，即 cache 的命中率應接近於 1。
- 在一個程序執行期間，設 Nc 表示cache 完成存取的總次數，Nm 表示主存完成存取的總次數，h定義為命中率，則有 h = Nc /（ Nc + Nm)
- 若Tc表示命中時的 cache 訪問時間，Tm表示未命中時的主存訪問時間，1-h表示未命中率，則 cache / 主存系統的平均訪問時間 Ta為：
- 我們追求的目標是，以較小的硬件代價使 cache / 主存系統的平均訪問時間 T~a~ 越接近 T~c~ 越好。
- 設r 表示主存慢於 cache 的倍率
e 表示訪問效率，則有
= \frac{T_c} {h*T_c +（1-h)*T_m }\\
= \frac{1} {h+（1-h）*r}\\
= \frac{1} {r+（1-r)*h}$$
即$$e = \frac{1} {r+（1-r)*h}$$
- 由表達式看出，為提高訪問效率，**命中率h越接近1越好，r值以5—10為宜**，不宜太大。
- 命中率h與程序的行為、cache的容量、組織方式、塊的大小有關。
例6:CPU執行一段程序時，cache完成存取的次數為1900次，主存完成存取的次數為100次，已知cache存取周期為50ns，主存存取周期為250ns，求cache/主存系統的效率和平均訪問時間。
解： h= Nc /（ Nc + Nm) =1900/(1900+100)=0.95
r= tm / tc =250ns/50ns=5
e=1/(r+(1-r)h)=1/(5+(1-5)×0.95=83.3%
e= tc /ta
ta= tc /e=50ns/0.833=60ns
### 3.6.2 主存與cache的地址映射
- 與主存相比，**cache的容量很小，保存的內容只是主存內容的一個子集**，且cache與主存的數據交換是以塊為單位。
- 為了把主存塊放到cache中，必須應用某種方法把主存地址定位到cache中，稱為**地址映射**。
- 無論選擇哪種映射方式，都要把主存和cache劃分為同樣大小的“塊”。
- 選擇哪種映射方式，要考慮：
- 硬件是否容易實現
- 地址變換的速度是否快
- 主存空間的利用率是否高
- 主存裝入一塊時，發生衝突的概率
- 以下我們介紹三種映射方法
- **全相聯映射、直接映射、組相聯映射**
#### 全相聯映射方式
主存中一個塊的地址(塊號)與塊的內容(字)一起存於cache的行中，其中塊地址存於cache行的標記部分主存的每一塊都可映射到cache任意一行中
- CPU訪存指令指定一個內存地址(由塊號和字組成)
- 為了快速檢索，主存地址中的塊號與Cache 中所有行的標記同時在比較器中進行比較。相同表示塊號命中，按字地址從cache中讀取一個字；如果塊號未命中，則按內存地址從主存中讀取這個字
- 轉換公式
- 主存地址長度＝(s+w)位
- 尋址單元數＝2^w^個字或字節
- 塊大小＝行大小＝2^w^個字或字節
- 主存的塊數＝2^s^
- 標記大小＝s位
- cache的行數＝不由地址格式確定
- 優點：可使主存的一個塊直接拷貝到cache中的任意一行上，**非常靈活**，cache空間的**利用率高**，cache的**塊衝突概率低**
- 缺點：**比較器難實現**，需要一個訪問速度很快代價高的相聯存儲器，**只適合於小容量cache**采用
#### 直接映射方式
- 一種**多對一**的映射關係
- **一個主存塊只能拷貝到cache的一個特定行位置上**
- Cache的行號i與主存的塊號j有如下函數關係
- i= j mod m （m為cache的總行數）
- 主存第j塊內容拷貝到Cache的i行
##### 直接映射方式的檢索過程
- 利用行號選擇相應行；
- 把行標記與CPU訪問地址進行比較。相同表示命中，訪問Cache；如果沒有命中，訪問主存，並將相應塊寫入Cache
**轉換公式**
- 主存地址長度 = (s+w)位
- 尋址單元數 = 2^s+w^個字或字節
- 塊大小 = 行大小 = 2^w^個字或字節
- 主存的塊數=2^s^
- cache的行數 = m =2^r^
- 標記大小=(s-r)位
優點：比較電路少m倍線路，所以**硬件實現簡單**，Cache地址為主存地址的低幾位，不需變換。
缺點：**衝突概率高**
應用場合：適合**大容量Cache**
#### 組相聯映射方式
全相聯映射和直接相聯映射兩種方式的優缺點正好相反，從存放位置的靈活性和命中率來看，前者為優；從比較器電路簡單及硬件投資來說，後者為佳
- 將cache分成u組，每組v行
- 主存塊與cache組之間采用直接映射方式，即**主存塊存放到哪個組是固定**的；每個組內部的行之間則采用全相聯的映射方式，即**主存塊可以映射到cache固定組的任一行**中
- Cache組號q與主存塊號j的關係為
- q= j mod u (u為cache的總組數)
- 主存第j塊內容拷貝到Cache的q組中的某行
- 地址變換
- 設主存地址x，看是不是在cache中，先y= x mod u，則在y組中一次查找
比全相聯容易實現，衝突低
若v=1，則為直接相聯映射方式
若u=1，則為全相聯映射方式
v的取值一般比較小， 一般是2的幂(典型值是2，4，8，16)，稱之為v路組相聯cache。
**轉換公式**
- 主存地址長度＝(s+w)位
- 尋址單元數＝2^s+w^個字或字節
- 塊大小＝行大小＝2^w^個字或字節
- 主存的塊數＝2^s^
- 每組的行數＝v
- 組數u＝2^d^
- cache的行數＝uv
- 標記大小＝(s-d)位
p96例6：一組相聯cache由64個行組成，每組4行，主存儲器包含4K個塊，每塊128字，請表示內存地址的格式。
解：塊大小 = 行大小 = 2^w^個字 = 128 = 2^7^ 所以w = 7
每組的行數 = v = 4
cache的行數 = uv = 64，故組數u = 16
u = 2^d^ = 16 = 2^4^，故d = 4
主存的塊數 = 2^s^ = 4K = 2^2^ * 2^10^ = 2^12^，故s = 12
地址格式如下：
| 標記s-d | 組號d | 字號w|
|--|--|--|
| 8位 | 4 位| 7位|
### 3.6.3 替換策略
- Cache工作原理要求盡量保存最新數據。
- 當一個新的內存塊需要拷貝到cache，而允許存放此塊的行位置都被其它主存塊占滿時，就需要替換。
- 直接映射方式：**直接替換**
- 全相連和組相連方式：從允許存放新主存塊的若干特定行中選取一行換出。
- 替換常用的三種算法:
- 最不經常使用(LFU)算法
- 近期最少使用(LRU)算法
- 隨機替換
#### 最不經常使用(LFU)算法
- 將**一段時間內被訪問次數最少的那行數據換出**。
- **每行設置一個計數器**。新行建立後從0開始計數，每訪問一次，被訪行的計數器增1。當需要替換時，將計數值最小的行換出，同時將這些行的計數器都清零
- 這種算法，計數周期限定在對特定行兩次替換之間的間隔時間內，**不能反映近期cache的訪問情況**
#### 近期最少使用(LRU)算法
- 將**近期內長久未被訪問過的行換出**。
- 每行也設置一個計數器，cache每命中一次，命中行計數器清零，其他各行計數器增1。當需要替換時，將計數值最大的行換出。
- 這種算法保護了剛拷貝到cache中的新數據行，**有較高的命中率**
#### 隨機替換
- 從特定的行位置中**隨機地選取一行**換出
- 這種策略在**硬件上容易實現**，且**速度也比前兩種策略快**
- 缺點是隨意換出的數據很可能馬上又要使用，從而**降低命中率和cache工作效率**。但這個不足隨著cache容量增大而減小。
-
## 3.7 虛擬存儲器（重點）
### 3.7.1 虛擬存儲器的基本概念
#### 1、實地址與虛地址
- 用戶**編制程序**時使用的地址稱為**虛地址或邏輯地址**，其對應的存儲空間稱為**虛存空間或邏輯地址空間**
- 計算**機物理內存**的訪問地址則稱為**實地址或物理地址**，其對應的存儲空間稱為**物理存儲空間或主存空間**。
- **程序進行虛地址到實地址轉換的過程稱為程序的重定位**。
#### 2、虛存的訪問過程
- 虛存空間的用戶程序按照虛地址編程並存放在**輔存**中。程序運行時，**由地址變換機構**依據當時分配給該程序的實地址空間把程序的一部分**調入實存**。
- 每次訪存時，首先判斷該虛地址所對應的部分是否在實存中：
- 如果是，則進行地址轉換並用實地址訪問主存；
- 否則，按照某種算法將輔存中的部分程序調度進內存，再按同樣的方法訪問主存。
- 由此可見，每個程序的虛地址空間可以遠大於實地址空間，也可以遠小於實地址空間。
- 前一種情況以**提高存儲容量**為目的，後一種情況則以**地址變換**為目的。
- 後者通常出現在多用戶或多任務系統中：實存空間較大，而單個任務並不需要很大的地址空間，較小的虛存空間則可以**縮短指令地址字段長度**。
- 每個程序就可以擁有一個虛擬的存儲器，它具有**輔存的容量**和**接近主存的訪問速度**。但這個虛存是由主存和輔存以及輔存管理部件構成的概念模型，不是實際的物理存儲器。虛存是在主存和輔存之外附加一些硬件和軟件實現的。
#### 3、cache與虛存的異同
- 從虛存的概念可以看出，主存-輔存的訪問機制與cache-主存的訪問機制是類似的。這是由cache存儲器、主存和輔存構成的三級存儲體系中的兩個層次。
- cache和主存之間以及主存和輔存之間分別有輔助硬件和輔助軟硬件負責地址變換與管理，以便各級存儲器能夠組成有機的三級存儲體系。
- **cache和主存構成了系統的內存，而主存和輔存依靠輔助軟硬件的支持構成了虛擬存儲器。**
在三級存儲體系中，cache-主存和主存-輔存這兩個存儲層次有許多相同點；
- **出發點相同** 二者都是為了**提高存儲系統的性能價格比**而構造的分層存儲體系，都力圖使存儲系統的性能接近高速存儲器，而價格和容量接近低速存儲器
- **原理相同** 都是**利用了程序運行時的局部性原理**把最近常用的信息塊從相對慢速而大容量的存儲器調入相對高速而小容量的存儲器。
但cache-主存和主存-輔存這兩個存儲層次也有許多不同之處:
- **側重點不同** **cache主要解決主存與CPU的速度差異問題**；而就性能價格比的提高而言，**虛存主要是解決存儲容量問題**，另外還包括存儲管理、主存分配和存儲保護等方面。
- **數據通路不同** **CPU與cache和主存之間均有直接訪問通路**，cache不命中時可直接訪問主存；而**虛存所依賴的輔存與CPU之間不存在直接的數據通路**，當主存不命中時只能通過調頁解決，CPU最終還是要訪問主存。
- **透明性不同** **cache的管理完全由硬件完成，對系統程序員和應用程序員均透明**；而虛存管理由軟件（操作系統）和硬件共同完成，由於軟件的介入，**虛存對**實現存儲管理的**系統程序員不透明，而只對應用程序員透明**（段式和段頁式管理對應用程序員“半透明”）。
- **未命中時的損失不同** 由於主存的存取時間是cache的存取時間的5～10倍，而**主存的存取速度通常比輔存的存取速度快上千倍**，故**主存未命中時系統的性能損失要遠大於cache未命中時的損失**。
#### 4、虛存機制要解決的關鍵問題
- **調度問題**——決定哪些程序和數據應被調入主存。
- **地址映射問題**——在訪問主存時把虛地址變為主存物理地址（這一過程稱為**內地址變換**），在訪問輔存時把虛地址變成輔存的物理地址（這一過程稱為**外地址變換**），以便換頁。此外還要解決主存分配、存儲保護與程序再定位等問題。
- **替換問題**——決定哪些程序和數據應被調出主存。
- **更新問題**——確保**主存與輔存的一致性**。在操作系統的控制下，硬件和系統軟件為用戶解決了上述問題，從而使應用程序的編程大大簡化。
### 3.7.2 頁式虛擬存儲器
#### 1、頁式虛存地址映射
- 頁式虛擬存儲系統中，虛地址空間被分成等長大小的頁，稱為**邏輯頁**；
- 主存空間也被分成同樣大小的頁，稱為**物理頁**。
- 虛地址分為兩個字段：**高字段為邏輯頁號，低字段為頁內地址（偏移量）**；
- 實存地址也分兩個字段：**高字段為物理頁號，低字段為頁內地址。**
- 通過**頁表**可以把虛地址（邏輯地址）轉換成物理地址。頁式虛擬存儲器的地址映射過程見下圖。
- 在大多數系統中，每個進程對應一個頁表。頁表中對應每一個虛存頁面有一個表項，表項的內容包含該虛存頁面所在的主存頁面的地址（物理頁號），以及指示該邏輯頁是否已調入主存的有效位。
- 地址變換時，**用邏輯頁號作為頁表內的偏移地址索引頁表（將虛頁號看作頁表數組下標）並找到相應物理頁號，用物理頁號作為實存地址的高字段，再與虛地址的頁內偏移量拼接**，就構成完整的物理地址。
- 每個進程所需的頁數並不固定，所以頁表的長度是可變的，因此通常的實現方法是把頁表的基地址保存在寄存器中，而頁表本身則放在主存中。由於虛存地址空間可以很大，因而每個進程的頁表有可能非常長為了節省頁表本身占用的主存空間，一些系統把頁表存儲在虛存中，因而頁表本身也要進行分頁。
- 當一個進程運行時，其頁表中一部分在主存中，另一部分則在輔存中保存。
- 另一些系統采用**二級頁表**結構。每個進程有一個頁目錄表，其中的每個表項指向一個頁表。因此，**若頁目錄表的長度（表項數）是m,每個頁表的最大長度（表項數）為n,則一個進程最多可以有m×n個頁。**
- 在頁表長度較大的系統中，還可以采用反向頁表實現物理頁號到邏輯頁號的反向映射。
#### 2、轉換後援緩衝器（快表TLB）
- 由於頁表通常在主存中，因而即使邏輯頁已經在主存中，也至少要訪問兩次物理存儲器才能實現一次訪存，這將使虛擬存儲器的存取時間加倍。
- 為了避免對主存訪問次數的增多，可以對頁表本身實行二級緩存，把頁表中的最活躍的部分存放在高速存儲器中，組成**快表**。
- 這個專用於頁表緩存的高速存儲部件通常稱為**轉換後援緩衝器(TLB)**。
- 保存在主存中的完整頁表則稱為**慢表**。
- TLB（快表）的地址映射過程見圖
- 
#### 3、內頁表和外頁表
- 頁表是**虛地址到主存**物理地址的變換表，通常稱為內頁表。
- 外頁表：用於**虛地址與輔存**地址之間的變換。
- 當主存缺頁時，調頁操作首先要定位輔存，而外頁表的結構與輔存的尋址機制密切相關。
- 例如對磁盤而言，輔存地址包括磁盤機號、磁頭號、磁道號和扇區號等。
頁式存儲主要優點：
- 主存儲器的利用率比較高
- 頁表相對比較簡單
- 地址變換的速度比較快
- 對磁盤的管理比較容易
主要缺點：
- 程序的模塊化性能不好
- 頁表很長，需要占用很大的存儲空間
### 3.7.3 段式虛擬存儲器和段頁式虛擬存儲器
#### 1、段式虛擬存儲器
- **段是按照程序的自然分界劃分的長度可以動態改變的區域。**
- 程序員把子程序、操作數和常數等不同類型的數據劃分到不同的段中，並且每個程序可以有多個相同類型的段。
- 在段式虛擬存儲系統中，**虛地址由段號和段內地址（偏移量）組成。**虛地址到實主存地址的變換通過**段表**實現。
- 每個程序設置一個段表，段表的每一個表項對應一個段。每個表項至少包含下面三個字段：
- **有效位**：指明該段是否已經調入實存。
- **段起址**：指明在該段已經調入實存的情況下，該段在實存中的首地址。
- **段長**：記錄該段的實際長度。設置段長字段的目的是為了保證訪問某段的地址空間時，段內地址不會超出該段長度導致地址越界而破壞其他段。 段表本身也是一個段，可以存在輔存中，但一般是駐留在主存中。
段式虛地址向實存地址的變換過程
段式虛擬存儲器有許多優點：
- ①段的**邏輯獨立性**使其易於編譯、管理、修改和保護，也**便於多道程序共享**。
- ②**段長可以根據需要動態改變**，允許自由調度，以便有效利用主存空間。
缺點：
- ①因為段的長度不固定，**主存空間分配比較麻煩**。
- ②容易在段間留下許多**外部碎片**，造成存儲空間利用率降低。
- ③由於段長不一定是2的整數次幂，因而不能簡單地像分頁方式那樣用虛地址和實地址的最低若干二進制位作為段內偏移量，並與段號進行直接拼接，必須用加法操作通過段起址與段內偏移量的求和運算求得物理地址。因此，段式存儲管理比頁式存儲管理方式**需要更多的硬件支持**。
#### 2、段頁式虛擬存儲器
- 段頁式虛擬存儲器是段式虛擬存儲器和頁式虛擬存儲器的結合。**實存被等分成頁。每個程序則先按邏輯結構分段，每段再按照實存的頁大小分頁**，程序按頁進行調入和調出操作，但可按段進行編程、保護和共享。
[例1] 假設有三道程序，基號用A、B和C表示，其基址寄存器的內容分別為S~A~、S~B~和S~C~。程序A由4個段構成，程序C由3個段構成。段頁式虛擬存儲系統的邏輯地址到物理地址的變換過程如圖所示。在主存中，每道程序都有一張段表，A程序有4段，C程序有3段，每段應有一張頁表，段表的每行就表示相應頁表的起始位置，而頁表內的每行即為相應的物理頁號。請說明虛實地址變換過程。
解：地址變換過程如下：
（1）由存儲管理部件根據基號C找到段表基址寄存器表第c個 表項，獲得程序C的段表基址SC。再根據段號S(=1)找到 程序C段表的第S個表項，得到段S的頁表起始地址b。
（2）根據段內邏輯頁號P(=2)檢索頁表，得到物理頁號（圖中 為10）。
（3）物理頁號與頁內地址偏移量拼接即得物理地址。 假如計算機系統中只有一個基址寄存器，則基號可不要。 多道程序切換時，由操作系統修改基址寄存器內容。
可以看出，段頁式虛擬存儲器的缺點是在由虛地址向主存地址的映射過程中需要多次查表，因而實現複雜度較高．
### 3.7.4 虛存的替換算法
當從輔存調頁至主存而主存已滿時，也需要進行主存頁面的替換。虛擬存儲器的替換算法與cache的替換算法類似：有FIFO算法、LRU算法、LFU算法等。
虛擬存儲器的替換算法與cache的替換算法不同的是：
- （1）cache的替換全部靠硬件實現，而虛擬存儲器的替換有操作系統的支持。
- （2）虛存缺頁對系統性能的影響比cache未命中要大得多，因為調頁需要訪問輔存，並且要進行任務切換。
- （3）虛存頁面替換的選擇餘地很大，屬於一個進程的任何頁面都可替換。
## 本章小結
- 對存儲器的要求是容量大、速度快、成本低。為了解決了這三方面的矛盾，計算機采用**多級存儲體系結構**，即cache、主存和外存。CPU能直接方問內存(cache、主存），但不能直接訪問外存。**存儲器的技術指標**有存儲容量、存取時間、存儲周期、存儲器帶寬。
- 廣泛使用的**SRAM和DRAM**都是半導體隨機讀寫存儲器，前者速度比後者快，但集成度不如後者高。二者的優點是體積小，可靠性高，價格低廉，缺點是斷電後不能保存信息。
- **只讀存儲器和閃速存儲器**正好彌補了SRAM和DRAM的缺點，即使斷電也仍然保存原先寫入的數據。特別是閃速存儲器能提供高性能、低功耗、高可靠性以及移動性，是一種全新的存儲器體系結構。
- **雙端口存儲器和多模塊交叉存儲器**屬於並行存儲器結構。前者采用空間並行技術，後者采用時間並行技術。這兩種類型的存儲器在科研和工程中大量使用。
- cache是一種高速緩衝存儲器，是為了解決CPU和主存之間速度不匹配而采用的一項重要的硬件技術，並且發展為多級cache體系，指令cache與數據cache分設體系。要求cache的命中率接近於1。主存與cache的地址映射有**全相聯、直接、組相聯**三種方式。其中組相聯方式是前二者的折衷方案，適度地兼顧了二者的優點又盡量避免其缺點，從靈活性、命中率、硬件投資來說較為理想，因而得到了普遍采用。
- 用戶程序按照虛地址（邏輯地址）編程並存放在輔存中。程序運行時，由地址變換機構依據當時分配給該程序的實地址空間把程序的一部分調入實存（物理存儲空間或主存空間）。由操作系統在硬件的支持下對程序進行虛地址到實地址的變換，這一過程稱為程序的再定位。**每次訪存時，首先判斷該虛地址所對應的部分是否在實存中：如果是，則進行地址轉換並用實地址訪問主存；否則，按照某種算法將輔存中的部分程序調度進內存，再按同樣的方法訪問主存。** 對應用程序而言，如果主存的命中率很高，虛存的訪問時間就接近於主存訪問時間，而虛存的大小僅僅依賴於輔存的大小。
- 虛存機制也要解決一些關鍵問題，包括**調度問題、地址映射問題和替換問題**等。在操作系統的控制下，硬件和系統軟件為用戶解決了上述問題，從而使應用程序的編程大大簡化。
- **頁式虛擬存儲系統**中，虛地址空間和主存空間都被分成大小相等的頁，通過頁表可以把虛地址轉換成物理地址。為了避免對主存訪問次數的增多，可以對頁表本身實行二級緩存，把頁表中的最活躍部分存放在轉換後援緩衝器（TLB）中。
- 分頁方式的缺點是頁長與程序的邏輯大小不相關，而分段方式則可按照程序的自然分界將內存空間劃分為長度可以動態改變的存儲區域。在**段式虛擬存儲系統**中，虛地址由段號和段內地址（偏移量）組成。虛地址到實主存地址的變換通過**段表**實現。
- **段頁式虛擬存儲器**是段式虛擬存儲器和頁式虛擬存儲器的結合，**程序按頁進行調入和調出操作，但可按段進行編程、保護和共享。** 虛擬存儲器還解決存儲保護等問題。在虛擬存儲系統中，通常采用頁表保護、段表保護和鍵式保護方法實現存儲區域保護。還可以結合對主存信息的使用方式實現訪問方式保護。