資訊安全系統設計基礎第七周學習總結

【學習時間：7小時】

【學習任務：《深入了解計算機系統》第六章——存儲技術及高速緩存部分】

一、課本内容

1.存儲器系統是一個具有不同容量、成本和通路時間的儲存設備的層次結構。

2.随機通路存儲器

SRAM（靜态）：高速緩存存儲器。将每個位存儲在一個雙穩态的存儲器單元裡面。（每個單元用一個六半導體電路來實作；其屬性是可以無限期保持在兩個不同的典雅配置或者狀态之一，其他的任何狀态都是不穩定的）
DRAM（動态）：将每個位存儲為對一個電容的充電（這個電容很小）。存儲單元對幹擾（如光線、噪音等）很敏感；當電容的電壓被擾亂之後就永遠不會恢複。優勢是密集度低，成本低。

3.關于DRAM

DRAM的晶片中的單元被分成d個超單元，每個超單元都由w個DRAM單元組成。一個d*w的DRAM總共存儲了dw位的資訊。超單元被組織成一個r行c列的長方形陣列，這裡rc = d。資訊通過引腳的外部連接配接器流入和流出晶片。
每個DRAM晶片被連接配接到某個稱為存儲控制器的電路，這個電路可以一次傳送w位到每個DRAM晶片或者依次從每個晶片傳出w位。電路設計者将DRAM組織成二維而不是線性數組的一個原因是降低晶片上位址引腳的數量。
DRAM晶片包裝在存儲器子產品中，它是插到主版的擴充槽上的。

4.非易失型存儲器：即使在關電後，也仍然儲存着它們的資訊；稱為ROM。包括：

PROM：隻能被程式設計一次。
可擦可寫程式設計ROM（EPROM）：被擦除和重寫的次數可以達到10^3次
電子可擦除PROM（EEPROM）：能夠被程式設計的次數可以達到10^3次。
閃存：基于EEPROM。基于此的磁盤驅動器稱為固态硬碟存儲在ROM裝置中的程式通常稱為固件；當一個計算機系統通電之後，它會運作存儲在ROM中的固件

5.資料流通過總線的共享電子電路在處理器和DRAM之間來回；包括讀事務（從主存到CPU）和寫事務。總線是一股并行的線，可以攜帶資料、控制信号和位址（資料總線，位址總線，控制總線）。

6.I/O橋、晶片組、主存

前兩者之間通過系統總線連接配接；後兩者通過存儲器主線連接配接。在讀寫事務中，均是分三步完成。

7.磁盤結構

磁盤是儲存大量資料的儲存設備；但讀取速度慢。
磁盤有若幹盤片組成，密封在容器（磁盤驅動器）内；每個盤片的兩個表面都有一組被稱為磁道的同心圓；每個同心圓由一些間隙分隔成一組等容量磁道（通常是512位元組），間隙中存儲的是辨別扇區的格式化位。
柱面：所有盤片表面到主軸中心距離相等的磁道的集合

8.磁盤容量

容量是指一個磁盤上可以記錄的最大位數。決定因素：
記錄密度；磁道密度；面密度（前兩者乘積）

9.磁盤操作

讀寫通過連在傳動臂一段的讀寫頭完成；可以定位在盤面上的任何磁道上；這樣的機械運動稱為尋道。每個盤面對應一個讀寫頭。所有的讀寫頭一緻行動，即在任意時刻，所有的讀寫都發生在同一盤面上
對扇區的通路主要有三個部分：
- 尋道：将讀寫頭定位到包含目标扇區的磁道上。Tseek取決于它以前的位置和傳動臂在盤面上的移動速度。時間通常為3——9ms。
- 旋轉：一旦讀寫頭定位到了期望的磁道，驅動器等待目标扇區的第一個位旋轉到讀寫頭下面。平均旋轉時間是最大時間（等磁盤旋轉一圈）
- 傳送：驅動器開始寫或者讀扇區的内容；時間長短取決于旋轉速度和每條磁道的扇區數目。平均時延為 Tavg=1/RPM1/(平均扇區數/磁道)60secs/1min
- 補充：通路一個磁盤扇區的512位元組的主要時間在于尋道和旋轉延遲。通路時間：磁盤>DRAM>SRAM

10.邏輯磁盤塊

目的是為了向作業系統隐蔽磁盤的結構複雜性。磁盤将其呈現為一個有B個扇區的邏輯塊的序列；磁盤中有一個固件裝置——磁盤控制器，維護者邏輯酷愛号和實際磁盤扇區之間的映射關系。作業系統是以邏輯塊号為機關進行尋址操作的。

11.（I/O）裝置是通過I/O總線（例如intel的PCI）連接配接到CPU和主存的。雖然它比系統總線和存儲器總線要慢，但是可以容納種類衆多的第三方I/O裝置。比如：通用串行總線；圖形卡；主機總線擴充卡

12.CPU使用一種稱為存儲器映射I/O的技術來向I/O裝置發出指令的。在使用其的系統中，位址空間中，有一塊位址是為與I/O裝置通信保留的；叫做I/O端口

13.局部性

計算機程式傾向于引用鄰近于其他最近引用過的資料項的資料或其本身；這種傾向性，被稱為局部性原理。包括：時間局部性，空間局部性。有良好局部性的程式比局部性差的程式運作的更快。
展現：在硬體層，局部性原理允許計算機設計者通過引入稱為高速緩存器的小而快的存儲器來儲存最近被引用的指令和資料項；在作業系統級，局部性原理允許系統使用主存作為虛拟位址空間最近被使用的磁盤塊。
重複引用一個變量的程式具有良好的時間局部性；對于取指令來說，循環具有良好的時間和空間局部性。循環體越小，循環疊代次數越多，局部性越好。

14.存儲器層次結構——緩存

存儲器層次結構的中心思想是：對于每個k，位于k層的更快更小的儲存設備作為位于（k+1）層的更大更慢的儲存設備的緩存。
第（k+1）層的存儲器被劃分成連續的資料對象片，稱為塊；資料總是以塊大小為傳送單元在相鄰兩層之間來回拷貝的；在任何時刻，第k層的緩存包括第（k+1）層塊的一個子集的拷貝。

15.緩存命中及緩存不命中

緩存命中：當程式需要第(k+1)層的資料對象d的時候，首先會在第k層找d；如果d剛好緩存在第k層，那麼就叫做緩存命中；反之，不命中
如果緩存不命中，那麼第k層緩存就從第（k+1）層取出包含該資料的塊，有可能會覆寫現有的塊。覆=決定替換哪個塊是由緩存的替換政策來控制的；例如，一個具有随機替換政策的緩存會随機選擇；而LRU替換政策會選擇被通路時間距今最遠的塊

16.緩存管理

在每一層上，某種形式的邏輯必須管理緩存；可以是硬體也可以是硬體、軟體的結合。

16.高速緩存存儲器（S,E,B,m）

作用：連接配接CPU和主存
每個存儲器位址有m位，形成M=2^m個不同位址。這m位被劃分成t個标記位、s個組索引位和b個塊偏移位。
這樣一個機器的高速緩存被組織成S=2^s個高速緩存組的數組；每個數組包含E個高速緩存行；每行由一個B=2^b位元組的資料塊、一個有效位（指明這個行是否包含有效資訊）、t=m-(b+s)個标記位（唯一辨別存儲在這個高速緩存行中的塊）組成

【了解：從高向低來看，M=2^m個位址平均分給S=2^s個組，每組獲得2^(m-s)個位址，即（m-s）位；減去t位用于标記塊，還有2^(m-t-s)個位址可以表示一個塊，也就是說，一個塊可以有2^(m-t-s)個位元組的資訊】 - 高速緩存的大小為C=SEB

17.直接映射高速緩存

高速緩存确定一個請求是否命中，然後抽搐被請求字的過程，分為：組選擇，行比對，字抽取
組選擇：從w的位址中抽取組索引；這些位被解釋成對應于一個組号的無符号整數
行比對：對于直接映射高速緩存，行比對是容易而且快的；因為每個組隻有一行
字比對：塊偏移提供的是這個字的第一個位元組是從哪個位置開始的

18.根據P413圖6-32，可以得出：

标記位和索引位連起來唯一地辨別了存儲器中的每個塊
當儲存塊多于緩存組（每組一行）的時候，多個塊映射到一個組；這樣的塊由标記位唯一辨別（可能會産生沖突不命中）

二、練習題篩選

1.P391 6.2

【計算這樣一個磁盤的容量。它有2個盤片，10 000個柱面，每條磁道平均有400個扇區，每個扇區平均有512個位元組】磁盤容量 = 512位元組/扇區400扇區/磁道10 000磁道/表面2表面/盤片2盤片/磁盤 = 8 192 000 000 位元組 = 8.192GB

2.P393 6.3

【估計通路下面的一個磁盤上的一個扇區需要的時間（以ms為機關）。旋轉速率：15000RPM；Taveseek = 8ms;每條磁道的平均扇區數：500】通路時間 = Taveseek+Taverotation+Tavetransfer = 8ms+0.51/15000RPM60secs.min1000ms/s+1/15000RPM1/50060secs/min1000ms/s=8ms+2ms+0.008ms=10.008ms

3.P394 6.4

【假設1MB的檔案由512位元組的邏輯塊組成，存儲在有如下特性的磁盤驅動器上（旋轉速率：10 000RPM，Taveseek=5ms，平均扇區/磁道 = 1000）。

（1）最好的情況：給定邏輯塊到磁盤扇區的最好的可能的映射（即，順序的），估計讀這個檔案需要的最優時間

（2）随機的情況：如果塊是随機地映射到磁盤扇區的，估計讀這個檔案需要的時間】

首先明确：1MB=2^20位元組，即資料存儲在2000個邏輯塊中；對于磁盤，Taverotation=0.51/10000RPM60secs/1min*1000ms/s=3ms

則：（1）T=Taveseek+Taverotation+2Tmaxrotation=5ms+3ms+26ms=20ms

(2)在這種情況下，塊被随機的映射到扇區上，讀2000塊的每一塊都需要Taveseek+Tavgrotation=8ms。是以讀這個檔案的總時間為T = 8ms*2000=16000ms=16s

4.P404 6.8

【改變下面函數中的循環順序，使得它以步長為1的引用模式掃描三維數組a】

int sumarray3d(int a[N][N][N])
{
    int i,j,k,sum=0;
    for(i=0;i<N;i++)
    {
        for(j =0;j<N;j++)
        {
            for(k=0;k<N;k++)
            {
                sum+=a[k][i][j];
            }
        }
    }
    return sum;
}

隻需要對三層嵌套循環體的順序進行調整即可：

int sumarray3d(int a[N][N][N])
{
    int i,j,k,sum=0;
    for(i=0;k<N;i++)
    {
        for(j =0;i<N;j++)
        {
            for(k=0;j<N;k++)
            {
                sum+=a[k][i][j];
            }
        }
    }
    return sum;
}

5.P415 6.11

【在前面dotprod的例子中，在我們對數組x做了填充之後，所有對x和y的引用的命中率是多少？】在填充了之後，對于x和y數組，隻有在引用第0個和第4個元素的時候發生不命中。因而命中率為75%

6.P415 6.12

【一般而言，如果一個位址的高s位被用作組索引，那麼存儲塊連續的片會映射到同一個高速緩存組。

1.每個這樣連續的數組有片多少個塊？

2.考慮下面的代碼；它運作在一個高速緩存形式為（S,E,B,m）=（512，1，32，32）的系統上

int array[4096]
for(i=0;i<4096;i++)
    sum+=array[i];

在任意時刻，存儲在高速緩存中的數組塊的最大數量是多少？】 1.2^t個塊

【這道題揭示了我們為什麼不用高s位做組索引；這樣的話，前2^t個位址都映射到一個組中（詳細解釋見下）】

2.如果位址的前s=9位做組索引，那麼之後的t=18位做标記位；高速緩存容量是512個32位元組的塊。數組隻需要（4096*4）/32=512個塊；這些塊均會被映射到組0中（數組是連續存放的），是以，在任何時刻，高速緩存中隻能儲存一個數組塊（盡管它的容量可以存放數組）。這樣極大降低了高速緩存使用率。

疑問

1.P383

有些系統也使用糾錯碼，其中計算機的字會被多編碼幾個位（例如，32位的字可能用38位來編碼），這樣一來，電路可以發現并糾正一個字中任何單個的錯誤位。并不明白，這樣前後有什麼因果關系？

2.P402

另一方面，因為sum是标量，對于sum來說，沒有空間局部性。為什麼标量沒有空間局部性（如果一個存儲位置被引用了一次，那麼程式很可能在不遠的将來被引用附近的一個存儲器位置）

3.P403

圖6-20中

int sumaraycols(int a[M][N])
{
    ……
    for(i=0;i<N;j++)
        for(j=0;j<M;j++)
            sum+=a[i][j];
    ……
}

這裡，為什麼是"i<N","j<M"？是不是應該對調一下變成"i<M"，"j<N"？

心得

【本次學習過程總體來說較上一次輕松；因為概念性知識點并不晦澀；而代碼部分也并不困難。同時，本章節各部分之間的聯系性增強，我經常要把課本“翻來覆去”地去讀——因為前面的内容并沒有形成很深刻的短期記憶，而後面的内容有與之前相照應。另外，讓我越來越感興趣的就是讀一段代碼（彙編代碼或者C）然後一點點了解，就好像将一件寶貝從深埋它的土中發掘出來。】