嵌入式系統設計師考試複習筆記之存儲管理篇

引言
    2007年下半年通過了嵌入式系統設計師的考試，一大堆的複習資料都不知道扔那裡好，賣掉又有點可惜，送人又沒人要。與其讓當時的複習筆記沉淪書架底部，還不如整理一下讓大家評論評論。2008年11月的考試也快到了，如果能幫到有需要的人，那我真是樂壞了。看看06和07年的題目，在存儲管理方面的題目蠻多的，應該是一個重要考點。無論是概念、理論、分析和計算都相當容易出題。在我當時的複習筆記中這方面算最多了。這裡就先拿這個點說說吧，其他的以後有時間再寫了。 

1、存儲器系統的層次架構
計算機系統的存儲器被組織城一個金字塔的層次結構。
自上而下為：CPU內部寄存器、晶元內部高速緩存(cache)、晶元外部高速緩存(SRAM、SDRAM、DRAM)、主存儲器(FLASH、EEPROM)、外部存儲器(磁碟、光碟、CF卡、SD卡)和遠程二級存儲器(分散式文件系統、WEB伺服器)，6個層次的結構。
上述設備從上而下，依次速度更慢、容量更大、訪問頻率更小，造價更便宜。 

2、高速緩存(cache)
工作原理（參照嵌入式系統設計師考試教程126頁，博客畫不了圖）：主要利用了程序的局部性特點。

地址映象是指把主存地址空間映象到cache的地址空間。

地址變換是指當程序或數據已經裝入到cache后，在實際運行過程中，把主存地址如何編程cache空間的地址。

常用的地址映象和地址變換的方式有：（教程127頁）

直接映象和變換：速度快，造價低，但有局限性，不能充分利用cache的好處。

組相聯地址映象和變換：速度稍慢但是命中率高。

全相聯地址映象和變換：可以任意映射。

常用的cache替換演算法：輪轉法和隨機替換演算法。

高速緩存的分類：

統一cache和獨立的數據/指令cache

寫通cache和寫回cache

讀操作分配cache和寫操作分配cache 

3、存儲管理單元（MMU）
MMU在CPU和物理內存之間進行地址轉換，將地址從邏輯空間映射到物理空間，這個過程稱為內存映射。

MMU主要完成下面的工作：
    A.     虛擬存儲空間到物理空間的映射。
    B.     存儲器訪問許可權的控制。
    C.     設置虛擬存儲空間的緩衝特性。

嵌入式系統中常常採用頁式存儲管理。為了管理這些頁引入了頁表的概念。

頁表是位於內存中的表，它的每一行對應虛擬存儲空間的一個頁，該行包含了該虛擬內存頁對應的物理內存頁的地址、該頁的訪問許可權和該頁的緩衝特性等。

從虛擬地址到物理地址的變換過程就是查詢頁表的過程。

由於頁表存儲在內存中的，整個查詢過程需要付出很大的代價。根據程序局部性的特點，增加了一個小容量、高速度的存儲部件來存放當前訪問需要的地址變換條目，這個存儲部件稱為：地址轉換後備緩衝器(TLB)。

當CPU訪問內存時，首先在TLB中查找需要的地址變換條目，如果該條目不存在，CPU再從內存中的頁表中查詢，並把相應的結果添加到TLB中，更新它的內容。

嵌入式系統中虛擬存儲空間到物理空間的映射以內存塊為單位進行。即虛擬存儲空間中一塊連續的存儲空間被映射到物理存儲空間中同樣大小的一塊連續存儲空間。

在頁表和TLB中，每一個地址變換條目實際上記錄了一個虛擬存儲空間的內存塊的基地址與物理存儲空間相對應的一個內存塊的基地址之間的對應關係。

在MMU中實現虛擬地址到物理地址的映射是通過兩級頁表來實現的。

禁止MMU時，所有物理地址和虛擬地址相等，即使用平板存儲模式。

4、內存保護
操作系統通常利用MMU來實現操作系統內核與應用程序之間的隔離，以及應用程序與應用程序之間的隔離。

內存保護包含兩個方面的內容：

A.     防止地址越界，每個應用程序都有自己獨立的地址空間。
B.     防止越權操作，每個應用程序都有自己的訪問許可權。

5、實模式與保護模式
在嵌入式系統中，常見的存儲管理方案可以分為兩大類：實模式和保護模式。

實模式：內存的平面使用模式。特點有：

A.     不劃分“系統空間”與“用戶空間”，無須進行地址映射。
B.     操作系統與應用程序之間不再有物理的邊界。
C.     系統中的“任務”或“進程”，實際上全是內核線程。

在實模式下，內存布局可以分為5個段：

A.     代碼段：包含操作系統和應用程序的所有代碼。
B.     數據段：所有帶有初始值的全局變數。
C.     BSS段：所有未帶初始值的全局變數。
D.     堆空間：動態分配的內存空間。
E.     棧空間：保存上下文以及函數調用時的局部變數和形參。

在實模式存儲管理方案下，主要的工作在於堆空間的管理，即如何來管理空閑的堆空間、如何來分配內存、如何來回收內存等等。

保護模式：處理器中必須有MMU硬體並啟用。特點有：

A.     系統內核和用戶程序都有各自獨立的地址空間。
B.     每個應用程序只能訪問自己的地址空間，不能去破壞操作系統和其他應用程序的代碼和數據。 

6、分區存儲管理
為了實現多道程序系統而採用的最簡單的內存管理。

基本思路：把整個內存劃分為兩大區域，即系統區和用戶區，然後再把用戶區劃分為若干個分區，每個任務佔有其中的一個分區。這樣，在內存當中就同時保留多個任務，讓他們共享整個用戶區，從而實現多個任務的併發運行。

分區存儲管理又可以分為兩類：固定分區和可變分區。

固定分區：各個用戶分區的個數、位置和大小一旦確定后，就固定不變，不能再修改。

優點：易於實現，系統開銷較小。
缺點：內存利用率不高，分區總數固定。

可變分區：動態創建，在裝入一個程序時，系統將根據它的需求和內存空間的使用情況來決定是否分配。

優點：動態變化，非常靈活。
缺點：可能存在外碎片。

在實現可變存儲管理技術的時候，需要考慮三個方面的問題：

A.     內存管理的數據結構
B.     內存的分配演算法
C.     內存的回收演算法 

7、地址映射
地址映射也叫地址重定位。

邏輯地址和物理地址是完全不同的，不能用邏輯地址來直接訪問內存單元。

為了保證CPU在執行指令的時候，可以正確地訪問內存單元，需要將用戶程序中的邏輯地址轉換為運行時由機器直接定址的物理地址。這個過程稱為：地址映射。

地址映射由存儲管理單元MMU來完成。

地址映射主要有兩種方式：靜態地址映射和動態地址映射。

靜態地址映射：當用戶程序被裝入內存時，直接對指令代碼進行修改，一次性地實現邏輯地址到物理地址的轉換。
動態地址映射：當用戶程序被裝入內存時，不對指令代碼做任何修改，而是在程序的運行過程中，當它需要訪問內存單元的時候，再來進行地址轉換。

在具體實現時，這項轉換工作一般是由硬體的地址映射機制來完成的。通常設置一個基地址寄存器，或者叫重定位寄存器。當一個任務被調度運行時，就把它所在分區的起始地址裝入到整個寄存器中。然後，在程序運行的過程中，當需要訪問某個內存單元時，硬體就會自動地將其中的邏輯地址加上基地址寄存器中的內容，從而得到實際的物理地址，並且按照這個物理地址區執行。

這個基地址寄存器位於MMU的內部，整個地址映射過程是自動運行的。從理論上說，每訪問一次內存都要進行一次地址映射。

8、頁式存儲管理（重點）
基本思路：把物理內存劃分為許多固定大小的內存塊，稱為物理頁面；把邏輯地址空間也劃分為大小相同的塊，稱為邏輯頁面。當一個用戶程序被裝入內存時，不是以整個程序為單位，把它存放在一整塊連續的區域，而是以頁面為單位來進行分配的。對於一個大小為N的頁面程序，需要有N個空閑的物理頁面來把它裝載。這些物理頁面不一定是要連續的。

在頁式存儲管理中需要解決三個問題：數據結構、內存分配與回收、地址映射。

數據結構有兩個：頁表和物理頁面表。

A.     頁表：給出了任務邏輯頁面號和內存中物理頁面號之間的對應關係。
B.     物理頁面表：描述內存空間中，各個物理頁面的使用情況。

具體的例子請參考《教程》317頁（博客中畫不了圖，有興趣自己看）。

內存的分配過程：

A.     對於一個新來的任務，計算它所需要的頁面數N，然後查看位示圖，看是否還有N個空閑的物理頁面。
B.     如果有足夠的空閑物理頁面，就去申請一個頁表，其長度為N，並把頁表的起始地址填入到該任務的控制塊中。
C.     分配N個空閑的物理頁面，把他們的變換填到頁表中，建立邏輯頁面與物理頁面直接的對應關係。
D.     修改位示圖，對剛剛被佔用的那些物理頁面進行標記。

地址映射的基本思路：

A.     邏輯地址分析：對邏輯地址，找到它所在的邏輯頁面，以及它在頁面內的偏移地址。
B.     頁表查找：根據邏輯頁面號，從頁表中找出它對應的物理頁面號。
C.     物理地址合成：根據物理頁面號和頁內偏移地址，最終確定物理地址。

邏輯地址分析：

頁面的大小都是2的整數次冪。對於給定的一個邏輯地址，可以直接把它的高位部分作為邏輯頁面號，把它的低位部分作為頁內偏移地址。例如，假設頁面的大小是4KB，即2的12次冪，邏輯地址為32為，那麼在一個邏輯地址當中，最低12位為頁內偏移地址，而剩下的20位就是邏輯頁面號。

計算方法：

邏輯頁面號＝邏輯地址/頁面大小
頁內偏移量＝邏輯地址％頁面大小

頁表查找：

頁表作為操作系統的一個數據結構，通常保存在內核的地址空間中。

頁表基地址寄存器用來指向頁表的起始地址；頁表長度寄存器用來指示頁表的大小，即對於當前任務，它總共包含有多少個頁面。

物理地址合成：

假設物理頁面號為f，頁內偏移地址為offset，每個頁面大小為2n，那麼相應的物理地址為：f×2n +offset。

9、虛擬存儲管理
程序局部性原理：時間局限性和空間局限性。

虛擬頁式存儲管理：在頁式管理的基礎上，增加了請求調頁和頁面置換的功能。

基本思路：當一個用戶程序需要調入內存去運行時，不是將這個程序的所有頁面都裝入內存，而是只裝載部分的頁面，就可以啟動這個程序運行。在運行過程中，如果發現要執行的指令或者訪問的數據不在內存當中，就向系統發出缺頁中斷請求，然後系統在處理這個中斷請求時，就會將保存在外存中的相應頁面調入內存，從而使該程序能繼續運行。

在虛擬頁式存儲管理中，頁表包含：邏輯頁面號、物理頁面號、駐留位、保護位、修改位和訪問位。

常用的頁面置換演算法：

A.  最優頁面置換演算法：理想化演算法。
B.      最近最久未使用演算法：鏈表法和棧方法。尋找長時間沒有被訪問的頁面。
C.      最不常用演算法：每個頁面設置一個訪問計數器。
D.     先進先出演算法：性能比較差。
E.      時鐘頁面置換演算法：把頁面組成環形鏈表，類似時鐘面。

    一般來說，當一個任務剛剛啟動的時候，它會不斷去訪問一些新的頁面，然後逐步建立一個比較穩定的工作集。工作集是指當前任務正在使用的邏輯頁面的集合。如果分配給一個任務的物理頁面數太少，不能包含整個的工作集，任務將會造成很多缺頁中斷，需要頻繁地進行頁面置換，這種現象稱為“抖動”。

10、相關的考試真題

（1）2007年6題：
若內存地址區間為4000H～43FFH，每個存貯單元可存儲16位二進位數，該內存區域用4片存儲器晶元構成，則構成該內存所用的存儲器晶元的容量是 （6） 。
（6）A. 512×16bit       B. 256×8bit     C. 256×16bit     D. 1024×8bit

<答案>：C
首先計算內容空間的大小：43FFH-4000H=3FFH，其大小為1024×16bit
接著計算存儲晶元的容量：(1024×16bit)/4=256×16bit=512×8bit
根據選項提供的內容，只有256×16bit符合提綱的要求。

（2）2007年23題：
頁式存儲系統的邏輯地址是由頁號和頁內地址兩部分組成，地址變換過程如下圖所示。假定頁面的大小為8K，圖中所示的十進位邏輯地址9612經過地址變換后，形成的物理地址a應為十進位 （23） 。
(博客不能顯示圖像)
（23）A. 42380          B. 25996       C. 9612          D. 8192

<答案>：B
8K＝1024×8＝8192
邏輯頁面號＝9612/8192=1（1號頁號對應的物理地址塊號為3）
頁內偏移量＝9612％8192＝1420
物理地址＝3×8192＋1420＝25996

（3）2007年24題
某匯流排有104根信號線，其中數據匯流排（DB）32根，若匯流排工作頻率為33MHz，則其理論最大傳輸率為 （24） 。（註：本題答案中的B表示Byte）
（24）A. 33 MB/s            B. 64MB/s     C. 132 MB/s        D. 164 MB/s

<答案>：C
每個位元組8位，需要8根數據線。
數據匯流排有32跟，每次可以并行傳輸32/8=4個位元組。
匯流排工作頻率為33MHz，那麼理論最大傳輸率為33×4＝132MHz。

（4）2007年26題
某存儲器數據匯流排寬度為32bit，存取周期為250ns，則該存儲器帶寬為 （26） 。（註：本題答案中的B表示Byte）
（26）A. 8×106B/s       B. 16×106B/s   C. 16×108B/s      D. 32×106B/s

<答案>：B
存取頻率為：1/0.00000025s=4000000
匯流排寬度為：32bit/8=4byte
存儲器帶寬：4×4000000＝16000000＝16×106B/s

（5）2007年29～31題
在嵌入式處理器中，CACHE的主要功能由 （29） 實現；某32位計算機的CACHE容量為16KB（B：位元組），CACHE塊的大小為16B（B：位元組），若主存與CACHE地址映像採用直接映像方式，則主存地址為0x1234E8F8的單元裝入CACHE的地址 （30） ；在下列CACHE替換演算法中,平均命中率最高的是 （31） 。
（29）A. 硬體                           B. 軟體
C. 操作系統                               D. 應用程序

（30）A. 00010001001101               B. 01000100011010
C. 10100011111000                     D. 11010011101000

（31）A. 先入后出演算法（FILO）         B. 隨機替換演算法（RAND）
C. 先入先出演算法（FIFO）         D. 近期最少使用演算法（LRU）

<答案>：A、C、D
29：Cache的主要功能由硬體實現，這個《教程》有介紹。
30：cache容量為16KB,即邏輯地址的低14位
    由於採用的是直接映象,所以cache的地址為:主存地址的低14位。
31：相比較說，D的命中率最低。

（6）2007年34題
在嵌入式系統的存儲結構中，存取速度最快的是 （34） 。
（34）A. 內存           B. 寄存器組    C. Flash          D. Cache

<答案>：B
寄存器組>cache>內存>flash

（7）2007年41題
操作系統中的“抖動”是指 （41） 的現象。
（41）A. 根據一定的頁面置換演算法，將頁面調出
B. 由於選擇了長期未被訪問的頁進行置換，導致系統更換頁面
C. 頁面調入不久就被導出，導出不久又被調入，導致系統頻繁更換頁面
D. 根據系統運行情況決定將哪個頁面調出，而不是由頁面置換演算法決定更換哪個頁面

<答案>：C
《教程》中328頁有對“抖動”的介紹。

（8）2006年1題
若內存按位元組編址，用存儲容量為32K×8比特的存儲器晶元構成地址編號A0000H到DFFFFH的內存空間，則至少需要（1）片。
（1）A. 4     B. 6    C. 8      D. 10

<答案>：C
DFFFF=-A0000H=256KB。
256/32=8片

（9）2006年22題
從下表關於操作系統存儲管理方案1、方案2和方案3的相關描述可以看出，他們分別對應（22）存儲管理方案。
方案1：在系統進行初始化的時候就已經將主存儲空間劃分成大小相等或不等的塊，並且這些塊的大小在此後是不可以改變的。系統將程序分配在聯繫的區域中。
方案2：主儲存空間和程序按固定大小大單位進行分割，程序可以分配在不連續的區域中。該方案當一個作業的程序地址空間大於主存可以使用的空間時也可以執行。
方案3：編程時必須劃分程序模塊和確定程序模塊之間的調用關係，不存在調用關係的模塊可以佔用相同的主存區。

（22）A. 固定分區、請求分頁和覆蓋
B. 覆蓋、請求分頁和固定分區
C. 固定分區、覆蓋和請求分頁
D. 請求分頁、覆蓋和固定分區

<答案>：A
《教程》中有相關概念的介紹。

（10）2006年28題
在32位匯流排系統中，若時鐘頻率為500MHz，傳送一個32位字需要5個時鐘周期，則該匯流排系統的數據傳輸速率為 （28） MB/s。
（28）A. 200           B. 400    C. 600          D. 800

<答案>：B
與2007年的24和26題考查的是相同的內容。
在32位匯流排系統中，每次可以傳送32位字，即4個BYTE。
時鐘頻率為500MHz，則傳輸32位的速率為100MHz。
也就是匯流排的數據傳輸速率為：4×100＝400MB/s。

（11）2006年29題
在CPU和物理內存之間進行地址轉換時， （29） 將地址從虛擬（邏輯）地址空間映射到物理地址空間。
（29）A. TCB           B. MMU    C. CACHE          D. DMA

<答案>：B
TCB：任務控制塊
MMU：存儲管理單元
CACHE：高速緩存
DMA：直接存儲

（12）2006年31題
下列存取速度最快的是（31）。
（31）A. flash存儲器     B. DRAM存儲器    C.高速緩存（CACHE）   D.磁碟

<答案>：C
    高速緩存（CACHE）> DRAM存儲器> flash存儲器、磁碟

（13）2006年51題
頁式存儲器當中的頁面是由（51）所感知的。
（51）A. 用戶     B. 操作系統    C. 編譯系統      D. 連接程序

<答案>：B
概念理解，看過就應該會做，不看過也能推理出來。

總的來看，07年考查內存管理方面的內容比06年多，深度也相應的增加了。
這次到此為止，以後有時間再寫，又問題可E我：ohy3686@qq.com。