本科生畢業(yè)論文cache(高速緩存)與主存一致性

1、<p>　　本科生畢業(yè)論文(設(shè)計)</p><p>　　Cache(高速緩存)與主存一致性初探</p><p>　　2012年3月25日</p><p>　院系名稱信息工程系</p><p>　姓　　名姓 名</p><p>　學(xué)　　號2008341142</p><p>　?！?/p>

2、　業(yè)計算機科學(xué)與技術(shù)專業(yè)</p><p>　指導(dǎo)教師導(dǎo)師 教授</p><p><b>　　摘　要</b></p><p>　　存儲器是具有“記憶”功能的部件，它在計算機系統(tǒng)中占有十分重要的地位。存儲器的基本功能是存放以二進制形式表示的程序與數(shù)據(jù)。如何設(shè)計容量大、速度快且造價低的存儲器，一直是計算機發(fā)展中的關(guān)鍵問題，目前還沒有哪一種存儲器功能

3、完全滿足計算機系統(tǒng)對存儲器的需求。因此，計算機系統(tǒng)通常配備分層結(jié)構(gòu)的存儲系統(tǒng)，以滿足容量、速度和造價等方面的要求。</p><p>　　衡量存儲器有三個指標：容量、速度和價格/位。一般地說，速度高的存儲器，每位價格也高，因此容量不能太大。所以存儲器設(shè)計的約束有容量、速度和價格。容量似乎沒有限制，不管容量多大，總要開發(fā)出應(yīng)用程序來使用。為了獲得更好的性能，存儲器的速度必須能夠跟上CPU，即當CPU執(zhí)行指令時，不想讓

4、他停下來等待指令或操作數(shù)。價格問題也必須考慮，對于實用的系統(tǒng)，存儲器的價格必須相對于其他部件是合理的。因此三個指標之間需要進行權(quán)衡。</p><p>　　高速緩存系統(tǒng)中能否確保高速緩沖存儲器和主存內(nèi)容一致性，這個問題直接關(guān)系到整個計算機系統(tǒng)的性能。這兩部分的數(shù)據(jù)一致性問題產(chǎn)生的原因有二：其一，由于CPU對高速緩沖存儲器的寫入導(dǎo)致它的內(nèi)容更新而主存內(nèi)容陳舊；其二，由于I/O處理機或多處理機系統(tǒng)中某一處理機修改了主存

5、內(nèi)容導(dǎo)致高速緩沖存儲器內(nèi)容陳舊。針對不同原因，分析了寫策略中七種解決方案，并就高速緩存系統(tǒng)采用的第二級脫片高速緩沖存儲器，以及第三級脫片高速緩沖存儲器結(jié)構(gòu)數(shù)據(jù)一致性問題進行初步探討。</p><p>　　本文通過對存儲器系統(tǒng)Cache（高速緩存）與主存的概念進行描述和目前兩者之間一致性存在的一些問題進行研究。并分析在多處理機系統(tǒng)中，主存與各處理機私有Cache之間及各私有Cache之間存在的數(shù)據(jù)不一致性。對解決不

6、一致性的方法：監(jiān)聽總線協(xié)議、基于目錄的Cache一致性協(xié)議、軟件控制方法等進行詳細的定性分析，并指出各種方法的優(yōu)缺點，供設(shè)計者參考；同時提出軟件和硬件相結(jié)合的方法，能有效解決Cache的一致性問題。</p><p>　　關(guān)鍵詞：存儲器；主存；緩存；一致性</p><p><b>　　Abstract</b></p><p>　　Memory i

7、s a " memory " function components , it in a computer system occupies a very important position . The basic function of memory is stored in binary form of said programs and data . How to design capacity ,

8、 speed is quick and low cost of memory , is always the key problems in the development of the computer , there is no memory function fully meet the needs of the memory of a computer system. Therefore, the computer

9、system usually equipped with a layered structure of storage sy</p><p>　　Measure memory has three index : capacity , speed and price/a. Generally speaking , the high speed of memory, every price is high , th

10、erefore capacity can not be too big . So memory design constraints capacity , speed and price . There seems to be no limit capacity , no matter how much capacity , the total to develop applications to use . In orde

11、r to obtain the better performance, the speed of the memory must be able to keep up with the CPU,and that is when the CPU executing instruct</p><p>　　Cache system can ensure cache memory and main m

12、emory contents consistency , the directly related to the entire computer system performance . The two parts of the data consistency issues of two reasons : first , because of the CPU cache memory write

13、 led to its contents to update the memory and out-of-date contents ; Second , because of I/O processor or multi-processor systems of a processor modified the main memory contents lead to cache content obsolete .

14、Accordin</p><p>　　This article through to the memory system Cache ( Cache ) and the concept of main storage describe between consistency and at present there are some problems. And analysis in multi

15、processor system , main memory with the processor Cache between the private and private Cache of inconsistency between data. To solve the inconsistency method: surveillance bus agreement, the Cache directory bas

16、ed on consistency agreement, software control method of detailed qualitative analysis , </p><p>　　Key Words: Memory , The main memory , Cache , The consistency</p><p><b>　　目　錄</b>

17、</p><p><b>　　1 引　言1</b></p><p>　　2 研究的背景和意義2</p><p>　　2.1 研究的背景2</p><p>　　2.1.1 主-輔存存儲層次2</p><p>　　2.1.2 Cache-主存存儲層次3</p><p>

18、;　　2.1.3 存儲器分層結(jié)構(gòu)3</p><p>　　2.2 研究的意義5</p><p>　　3 數(shù)據(jù)一致性問題的提出7</p><p>　　4 基于不同原因的寫策略解決方案9</p><p>　　4.1 基于原因1的解決辦法9</p><p>　　4.1.1 寫直達9</p><p

19、>　　4.1.2 寫回發(fā)9</p><p>　　4.2 基于原因2的解決辦法9</p><p>　　4.2.1 總線監(jiān)視法9</p><p>　　4.2.2 硬件監(jiān)視法10</p><p>　　4.2.3 劃出不可高速緩存存儲區(qū)法10</p><p>　　4.2.4 Cache清除法10</p&

20、gt;<p>　　4.3 基于原因3的解決辦法10</p><p>　　4.4 基于目錄的Cache一致性協(xié)議10</p><p>　　5 數(shù)據(jù)一致性問題的發(fā)展與展望13</p><p><b>　　6 結(jié)束語15</b></p><p><b>　　參考文獻16</b>&l

21、t;/p><p><b>　　致 謝18</b></p><p><b>　　1 引　言</b></p><p>　　高速緩沖存儲器是存在于主存與CPU之間的一級存儲器， 由靜態(tài)存儲芯片(SRAM)組成，容量比較小但速度比主存高得多， 接近于CPU的速度。在計算機存儲系統(tǒng)的層次結(jié)構(gòu)中，是介于中央處理器和主存儲器之間的高速小

22、容量存儲器。它和主存儲器一起構(gòu)成一級的存儲器。高速緩沖存儲器和主存儲器之間信息的調(diào)度和傳送是由硬件自動進行的。</p><p>　　高速緩沖存儲器的容量一般只有主存儲器的幾百分之一，但它的存取速度能與中央處理器相匹配。根據(jù)程序局部性原理，正在使用的主存儲器某一單元鄰近的那些單元將被用到的可能性很大。因而，當中央處理器存取主存儲器某一單元時，計算機硬件就自動地將包括該單元在內(nèi)的那一組單元內(nèi)容調(diào)入高速緩沖存儲器，中央

23、處理器即將存取的主存儲器單元很可能就在剛剛調(diào)入到高速緩沖存儲器的那一組單元內(nèi)。于是，中央處理器就可以直接對高速緩沖存儲器進行存取。在整個處理過程中，如果中央處理器絕大多數(shù)存取主存儲器的操作能為存取高速緩沖存儲器所代替，計算機系統(tǒng)處理速度就能顯著提高。</p><p>　　當然，計算機存儲系統(tǒng)中，高速緩沖存儲器系統(tǒng)的引入雖然為計算機系統(tǒng)處理數(shù)據(jù)的速度帶來了顯著地提高，但是隨之而來的Cache（高速緩存）與主存間數(shù)據(jù)

24、一致性問題也是日益凸顯出來。</p><p>　　存儲器中的一致性問題，是伴隨著存儲器結(jié)構(gòu)的概念而提出的，又一直是困擾著計算機設(shè)計者的一個重要問題，也是很多從事計算機體系結(jié)構(gòu)研究的人們所共同面對的一個熱門研究課題。特別是近年來出現(xiàn)的多處理系統(tǒng)，超并行機系統(tǒng)，超大規(guī)模計算機系統(tǒng)等采用DSM（Distributed Shared Memory）-分布式共享存儲器技術(shù)的大型系統(tǒng)中，都采用了多級Cache的存儲器層次結(jié)構(gòu)

25、。在Cache的數(shù)據(jù)一致性問題上，就更顯突出了。如在DSM多處理機系統(tǒng)結(jié)構(gòu)中，相鄰層之間和同一層之內(nèi)可能會出現(xiàn)數(shù)據(jù)不一致性。通過存儲器的共享數(shù)據(jù)，進程在同一算法下并行工作。為了減少內(nèi)存訪問延時和內(nèi)存總線的擁塞，要求Cache與每個處理器相關(guān)。這樣同一數(shù)據(jù)在不同的Cache中有多個副本。當處理機對共享存儲器某個單元在其本地Cache中的拷貝要進行維護時，只要對該單元的本地拷貝進行修改，這就有可能引起存儲器的全局不一致性等等。所以如何在維護

26、一致性情況下又保證處理機代價最小是這本論文討論的主要問題。</p><p>　　本文將在對計算機存儲系統(tǒng)存儲進行介紹的前提下，對高速緩存系統(tǒng)中Cache（高速緩存）與主存這兩部分的數(shù)據(jù)一致性問題產(chǎn)生的各種原因進行充分的分析和研究，并針對不同的原因，給予適當各種維護策略下的保證一致性的可行方案。</p><p>　　2 研究的背景和意義</p><p><b&g

27、t;　　2.1 研究的背景</b></p><p>　　存儲器是具有“記憶”功能的部件，它在計算機系統(tǒng)中占有十分重要的地位。存儲器的基本功能是存放以二進制形式表示的程序與數(shù)據(jù)。如何設(shè)計容量大、速度快且造價低的存儲器，一直是計算機發(fā)展中的關(guān)鍵問題，目前還沒有哪一種存儲器功能完全滿足計算機系統(tǒng)對存儲器的需求。因此，計算機系統(tǒng)通常配備分層結(jié)構(gòu)的存儲系統(tǒng)，以滿足容量、速度和造價等方面的要求。</p>

28、;<p>　　衡量存儲器有三個指標：容量、速度和價格/位。一般地說，速度高的存儲器，每位價格也高，因此容量不能太大。所以存儲器設(shè)計的約束有容量、速度和價格。容量似乎沒有限制，不管容量多大，總要開發(fā)出應(yīng)用程序來使用。為了獲得更好的性能，存儲器的速度必須能夠跟上CPU，即當CPU執(zhí)行指令時，不想讓他停下來等待指令或操作數(shù)。價格問題也必須考慮，對于實用的系統(tǒng)，存儲器的價格必須相對于其他部件是合理的。因此三個指標之間需要進行權(quán)衡。

29、</p><p>　　2.1.1 主-輔存存儲層次</p><p>　　由于計算機主存容量相對于程序員所需要的容量來說總是太小，程序與數(shù)據(jù)從輔存調(diào)入主存是由程序員自己安排的，程序員必須花費很大精力和時間把大程序預(yù)先分成塊，確定好這些程序塊在輔存中的位置和裝入主存的地址，而且還要預(yù)先安排好程序運行時各塊如何和何時調(diào)入調(diào)出，因此存在存儲空間的分配問題。操作系統(tǒng)的形成和發(fā)展使得程序員盡可能擺脫主

30、、輔存之間的地址定位，同時形成了支持這些功能的“輔助硬件”，通過軟件、硬件的結(jié)合，把主存和輔存統(tǒng)一成了一個整體，如圖2-1所示。這時，由主存、輔存形成了一個存儲層次，即存儲系統(tǒng)。從整體看，其速度接近于主存的速度，其容量則接近于輔存的容量，而每位的平均價格也接近于廉價的慢速的輔存平均價格。這種系統(tǒng)不斷發(fā)展和完善，就逐步形成了現(xiàn)在廣泛使用的虛擬存儲系統(tǒng)。在系統(tǒng)中，應(yīng)用程序員可用機器指令地址碼對整個程序統(tǒng)一編址，如同程序員具有對應(yīng)這個地址碼寬

31、度的全部虛存空間一樣。該空間可以比主存實際空間大得多，以致可以存得下整個程序。這種指令地址碼稱為虛地址（虛存地址、虛擬地址）或邏輯地址，其對應(yīng)的存儲容量稱為虛存容量或虛存空間；而把實際主存的地址稱為物理地址、實（存）地址，其對應(yīng)的存儲容量稱</p><p>　　圖2-1 主-輔存存儲層次</p><p>　　2.1.2 CACHE-主存存儲層次</p><p>　　

32、當用虛地址訪問主存時，機器自動地把它經(jīng)輔助軟件、硬件變換成主存實地址。察看這個地址所對應(yīng)的單元內(nèi)容是否已經(jīng)裝入主存，如果在主存就進行訪問，如果不在主存內(nèi)就經(jīng)輔助軟件、硬件把它所在的那塊程序和數(shù)據(jù)由輔存調(diào)入主存，而后進行訪問。這些操作都不必由程序員來安排，也就是說，對應(yīng)用程員員是透明的。</p><p>　　主-輔存層次解決了存儲器大容量要求和低成本之間的矛盾。</p><p>　　在速度方

33、面，計算機的主存和CPU直保持了大約一個數(shù)量級的差距。顯然這個差距限制了CPU速度潛力的發(fā)揮。為了彌合這個差距，僅采用一種工藝的單一存儲器是行不通的，必須進一步從計算機系統(tǒng)結(jié)構(gòu)和組織上去研究。設(shè)置高速緩沖存儲器（Cache）是解決存取速度的重要方法。在CPU和主存中間設(shè)置高速緩沖存儲器，構(gòu)成高速緩存（Cache）-主存層次，要求Cache在速度上能跟得上CPU的要求。Cache-主存間的地址映象和調(diào)度吸取了比它較早出現(xiàn)的主-輔存存儲層次

34、的技術(shù)，不同的是因其速度要求高，不是由軟、硬件結(jié)合而完全由硬件來實現(xiàn)，如圖2-2所示。</p><p>　　圖2-2 Cache-主存存儲層次</p><p>　　2.1.3 存儲器分層結(jié)構(gòu)</p><p>　　從CPU的角度看，Cache-主存層次的速度接近于Cache，容量與每位價格接近于主存，因此，解決了速度與成本之間的矛盾。</p><p

35、>　　綜上所述，計算機的存儲系統(tǒng)是采用了存儲器的分層結(jié)構(gòu)，而不只是依賴單一的存儲部件或技術(shù)。圖2-3給出了一個通用分層結(jié)構(gòu)，圖中從上到下出現(xiàn)情況如下：</p><p>　　1>每位的價格降低；</p><p><b>　　2>容量增大；</b></p><p><b>　　3>存取時間增大；</b>

36、</p><p>　　4>CPU存取存儲器的頻度降低。</p><p>　　圖2-3 存儲器分層結(jié)構(gòu)</p><p>　　因此，較小、較貴、較快的存儲器可作為較大、較便宜、較慢的存儲器的補充。這個結(jié)構(gòu)成功的關(guān)鍵是最后一項，即存取頻度降低。</p><p>　　如果能夠根據(jù)以上的1>到3>項來組織存儲器，而且數(shù)據(jù)和指令能夠根據(jù)

37、4>分布在存儲器中，很顯然，這個方案在保證給定的性能水平的情況下能降低總體價格。下面用一個簡單的例子來說明這一點。</p><p>　　假設(shè)CPU能夠存取二級的存儲器，第1級包含1000個字并有1微秒的存取時間，第2級包含1000000個字并有10微秒的存取時間。假設(shè)要存取的一個字在第1級，那么CPU能直接存取它；假設(shè)它在第2級，則這個字首先傳到第1級，然后再由CPU存取它。為了簡化，不考慮CPU確定這個字

38、在第1級還是在第2級所需的時間。圖2-4表示了平均總存取時間和在第1級中存取字所需的時間占總的百分比的函數(shù)關(guān)系?？梢姡?級存取百分比高時，平均總的存取時間接近于第1級的存取時間。此例說明了這種策略工作的原理。如果條件1>到4>都滿足，則它能工作。</p><p>　　圖2-4 簡單的兩級存儲性能</p><p>　　條件4>有效的基礎(chǔ)是訪問局部性原理。在程序執(zhí)行過程中，

39、處理器訪問存儲器中的指令和數(shù)據(jù)傾向于成塊進行。程序通常包含許多迭代循環(huán)的子程序，一旦進入了一個循環(huán)或子程序，則需重復(fù)訪問一小組指令。同樣，對于表和數(shù)組的操作，包含存取一塊塊的數(shù)據(jù)字。在一長段時間內(nèi)，使用的塊是變化的，而在一小段時間內(nèi)，處理器主要訪問存儲器中的固定塊。</p><p>　　因此，通過分層結(jié)構(gòu)組織數(shù)據(jù)，有可能使存取較低層的存取時間百分比低于存取高層的百分比。根據(jù)上面給出的二級例子，讓第2級的存儲器包含

40、所有程序的指令和數(shù)據(jù)，當前的塊臨時放在第1級，第1級某些塊回不時地交換回第2級。然而，多數(shù)是對第1級中的指令和數(shù)據(jù)的訪問。</p><p>　　這個原理可以應(yīng)用到兩級以上的存儲器。考慮如圖2-3所示的分層結(jié)構(gòu)，最快、最小和最貴的存儲器是處理器的內(nèi)部存儲器。通常一個處理器包含幾十個寄存器，雖然有些機器包含幾百個寄存器。向下跳二層是主存儲器。主存儲器通常用一個速度更快、容量更小的高速緩存來擴充。高速緩存是透明的，它在

41、主存和處理器寄存器之間傳送數(shù)據(jù)以提高性能。</p><p><b>　　2.2 研究的意義</b></p><p>　　高速緩沖存儲器是存在于主存與CPU之間的一級存儲器， 由靜態(tài)存儲芯片(SRAM)組成，容量比較小但速度比主存高得多， 接近于CPU的速度。在計算機存儲系統(tǒng)的層次結(jié)構(gòu)中，介于中央處理器和主存儲器之間的高速小容量存儲器。它和主存儲器一起構(gòu)成一級的存儲器。

42、高速緩沖存儲器和主存儲器之間信息的調(diào)度和傳送是由硬件自動進行的。</p><p>　　高速緩沖存儲器的容量一般只有主存儲器的幾百分之一，但它的存取速度能與中央處理器相匹配。根據(jù)程序局部性原理，正在使用的主存儲器某一單元鄰近的那些單元將被用到的可能性很大。因而，當中央處理器存取主存儲器某一單元時，計算機硬件就自動地將包括該單元在內(nèi)的那一組單元內(nèi)容調(diào)入高速緩沖存儲器，中央處理器即將存取的主存儲器單元很可能就在剛剛調(diào)入

43、到高速緩沖存儲器的那一組單元內(nèi)。于是，中央處理器就可以直接對高速緩沖存儲器進行存取。在整個處理過程中，如果中央處理器絕大多數(shù)存取主存儲器的操作能為存取高速緩沖存儲器所代替，計算機系統(tǒng)處理速度就能顯著提高。</p><p>　　在由主存和高速緩存組成的存儲器層次結(jié)構(gòu)中，主存是多處理機共享，而高速緩存是每個處理機私有的。主存和高速緩存都以塊為單位進行劃分，以映射的方式來檢索。映射的方法有直接映射、組關(guān)聯(lián)映射、區(qū)段關(guān)聯(lián)

44、映射和全相聯(lián)映射。在主存和高速緩存之間，是以塊為單位進行搬送。主存中保存有各高速緩存的副本，高速緩存的目錄中，存放相應(yīng)主存的塊號及一些標志。通過對目錄的檢索來尋找高速緩存中的數(shù)據(jù)。當處理機發(fā)出一個訪問主存地址時，如果包含這個地址在內(nèi)的模塊在高速緩存中，則稱之為命中，該高速緩存可以使用。如果不在高速緩存中，則稱之為未命中（或Cache失效），這時，必須把這個模塊從主存搬到高速緩存中，叫做塊搬送。如果高速緩存已滿，則必須按一定的置換算法挑出

45、一個模塊搬出高速緩存到主存，這叫置換。置換算法有FIFO算法，URL算法等。</p><p>　　計算機高速緩存系統(tǒng)的發(fā)展為計算機設(shè)計者提出了一個重要課題：數(shù)據(jù)在Cache（高速緩沖存儲器）和主存之間交換時必須滿足數(shù)據(jù)一致的要求，隨著多任務(wù)系統(tǒng)的采用，數(shù)據(jù)一致性問題越來越突出，以往關(guān)于這方面的著述具有了很大的局限性，例如，對于486以上機種出現(xiàn)的第二級托片Cache、第三級托片Cache如何保存數(shù)據(jù)一致的問題尚未

46、見于專門的論述。為了探索更適合于當前計算機發(fā)展的趨勢，必須適時追溯數(shù)據(jù)一致性問題出現(xiàn)和發(fā)展的歷史軌跡，步入多任務(wù)系統(tǒng)的解決方案。</p><p>　　因此高速緩存系統(tǒng)中能否確保高速緩沖存儲器和主存內(nèi)容一致性，這個問題直接關(guān)系到整個計算機系統(tǒng)的性能。對于計算機整體性能的提升有十分重要的意義。</p><p>　　3 數(shù)據(jù)一致性問題的提出</p><p>　　高速緩存是

47、旨在改善存儲器平均響應(yīng)時間的小型快速存儲器，它在系統(tǒng)中位于微處理器和主存之間，使得系統(tǒng)從CPU看具有Cache的速度，主存的容量。圖3-1為一高速緩沖存儲器系統(tǒng)框圖，它將微處理器頻繁向主存請求的代碼和數(shù)據(jù)予以拷貝。</p><p>　　圖3-1 高速緩存框圖</p><p>　　Cachc的操作與存儲器一樣具有讀/寫兩種模式，其中讀操作主要局限在不命中時更新Cache內(nèi)容，只影響存儲系統(tǒng)工

48、作速度。寫操作不僅工作時間比讀操作長，而且更新主存內(nèi)容，直接影響機器性能，據(jù)李學(xué)干、蘇東莊在《計算機系統(tǒng)結(jié)構(gòu)》一書中借典型程序的統(tǒng)計可知，所有訪存中約有10%~34%甚至更多的是寫操作。寫操作是直接導(dǎo)致數(shù)據(jù)一致性問題產(chǎn)生的原因。</p><p>　　在一個系統(tǒng)中，同一個數(shù)據(jù)的多個拷貝可以同時存在，如果一個拷貝改變了而其它的沒變，那么兩組不同的數(shù)據(jù)便與主存的同一地址有關(guān)。Cache必須包含一個更新系統(tǒng)以防止老數(shù)據(jù)(

49、陳舊數(shù)據(jù))被使用，即解決一致性問題。分析產(chǎn)生數(shù)據(jù)一致性問題的原因主要有三個：</p><p>　　1> 同樣一個數(shù)據(jù)可能既存于Cache中，也存于主存中，這樣可能前者己更新，后者未更新，造成數(shù)據(jù)丟失。</p><p>　　2> 在有DMA系統(tǒng)或多處理器系統(tǒng)中，有多個部件可以訪問主存，這時可能其中有些部件是直接訪問主存，也可能每個DMA部件和每個處理器配一個Cache，這樣主存的

50、一塊區(qū)域可能對應(yīng)于多個Cache中的各1個塊區(qū)，產(chǎn)生主存中的數(shù)據(jù)被某個總線主控部件更新過，而某個Cache中的內(nèi)容未更新，造成Cache中數(shù)據(jù)過時。</p><p>　　3> 當主存中同時有多道程序運行時，Cache中均有相應(yīng)的數(shù)據(jù)副本與每道程序相對應(yīng)；對于共享數(shù)據(jù)，每道程序都有各自的Cache數(shù)據(jù)與主存數(shù)據(jù)相一致。當某道更新了其相應(yīng)的Cache數(shù)據(jù)和主存數(shù)據(jù)，而其它程序的Cache數(shù)據(jù)也有此頁內(nèi)容.則其內(nèi)

51、容不會改變(例如寫直達法約束)。這道程序再次讀到的內(nèi)容就會因是原先的內(nèi)容而出錯。</p><p>　　寫策略是Cache使用的保證數(shù)據(jù)一致性的方法，保持系統(tǒng)主存更新，處理陳舊數(shù)據(jù)。</p><p>　　高速緩存一致性是指要求同一個信息項與后繼存儲器層次上的副本是一致的。如果在高速緩存中的一個字被修改過，那么在所有更高層上該字的副本也必須立即或最后加以修改。對于多處理機系統(tǒng)的存儲器層次結(jié)構(gòu)，

52、相鄰層之間和同層之間可能會出現(xiàn)數(shù)據(jù)不一致性。比如某個處理機修改了該處理機的Cache的某個數(shù)據(jù)，則該數(shù)據(jù)塊可能在別的處理機上有相同的拷貝，由于該數(shù)據(jù)塊得到了最新的修改，所以如果其它相同的拷貝不及時得到修改的話，被其它處理機訪問以后，可能出現(xiàn)錯誤。這也就是所謂的Cache不一致性。我們用圖3-2一致性定義圖來直觀的表示：</p><p>　　圖3-2 一致性定義圖</p><p>　　但是這

53、種只對本地拷貝進行修改的方法就可能導(dǎo)致存儲器的全局不一致性，也就是這些拷貝并不一致。如何能夠讓處理器訪問不會出錯，并且維護一致性的代價最小是研究高速緩存一致性和同步機制的主要研究課題。</p><p>　　4 基于不同原因的寫策略解決方案</p><p>　　4.1 基于原因1的解決辦法</p><p>　　原因1導(dǎo)致的數(shù)據(jù)一致性問題是建立在Cache內(nèi)容與主存內(nèi)容

54、一一對應(yīng)基礎(chǔ)上，不能相關(guān)更新造成的數(shù)據(jù)丟失，解決方法首先解決Cache與主存的相關(guān)動作。</p><p><b>　　4.1.1 寫直達</b></p><p>　　它利用Cache-主存貯層次在處理機和主存之間的直接通路，每當處理機寫入Cache的同時，也通過此通路直接寫入主存。從而主存隨時跟蹤Cache的最新版本，也就不會有主存將數(shù)據(jù)丟失的問題但缺點也顯而易見，它

55、把開銷花費在每次寫Cache時就有對主存的寫入，造成總線活動繁忙。</p><p><b>　　4.1.2 寫回發(fā)</b></p><p>　　這種方法是在CPU執(zhí)行寫操作時，信息只寫入Cache，僅當需要被替換時，才將已被寫入過的Cache塊先送回主存，然后再調(diào)入新塊。Cache-主存的地址映象表中需對Cache中每個塊設(shè)置一個“修改位”，作為該塊裝入Cache后是

56、否被修改過的標志，只要修改過，就使該標志位置成“1”。它的開銷花在每次需要替換時，增加了Cache的復(fù)雜性。</p><p>　　以上兩種解決方法的采用沒有嚴格約束，從可靠性講寫直達法優(yōu)于寫回法，Cache出錯時可由主存來糾錯。而寫回法因有效塊只在Cache中，故需在Cache中采用糾錯碼，增力了冗余信息；從成本上講，寫回法低于寫直達法，寫直達法要花費大量緩沖器和其它輔助邏輯。所以方法的采用主要山應(yīng)用場合決定，單

57、處理機系統(tǒng)以節(jié)省成本為主，多采用寫直達法。對共享主存的多處理系統(tǒng)，以可靠性為主，多采用寫直達法。</p><p>　　4.2 基于原因2的解決辦法</p><p>　　原因2是由于主存區(qū)塊更新而Cache未更新產(chǎn)生的數(shù)據(jù)過時錯誤，解決方法應(yīng)首重主存內(nèi)容的約束。</p><p>　　4.2.1 總線監(jiān)視法</p><p>　　在這種方法中，由C

58、ache控制器隨時監(jiān)視系統(tǒng)的地址總線，如其它部件將數(shù)據(jù)寫到主存，并且寫入的主存區(qū)塊正好是Cache中的區(qū)塊對應(yīng)的位置，那么Cache控制器會自動將Cache中的區(qū)塊標為“無效”。</p><p>　　4.2.2 硬件監(jiān)視法</p><p>　　如果把主存映象到Cache的區(qū)塊稱為已映象區(qū)塊，硬件監(jiān)視法就是通過外加硬件電路，使Cache本身能觀察到主存中已映象區(qū)塊的所有存取操作。解決辦法是所

59、有部件對主存的存取都通過同一個Cache完成或每個部件配備各自的Cache，當一個Cache有寫操作時，新數(shù)據(jù)既拷貝到主存，也拷貝到其它Cache(播寫法)。</p><p>　　4.2.3 劃出不可高速緩存存儲區(qū)法</p><p>　　這種方法是控制某些共享信息(如信號燈或作業(yè)隊等)不得進入Cache。即要在主存中劃出一個區(qū)域作為各部件共享區(qū)，CPU對此區(qū)域的訪問必須是直接的，避免了主存

60、中1個區(qū)塊映象到多個Cache。的情況。</p><p>　　4.2.4 CACHE清除法</p><p>　　這種方法是將Cache中所有己更新的數(shù)據(jù)寫回到主存時，由專用硬件自動地將Cache內(nèi)對應(yīng)此區(qū)域的副本作廢，或清除Cache中的所有數(shù)據(jù)，使Cache內(nèi)容取決于內(nèi)存內(nèi)容的變動，保持Cache的透明性。</p><p>　　當然以上幾種方法并不是全部解決措施，

61、還有目錄表法等應(yīng)用。無論何利，萬法，本質(zhì)上的要求都是透明性要求，視具體應(yīng)用場合采取適當措施。</p><p>　　4.3 基于原因3的解決辦法</p><p>　　原因3本質(zhì)上是原因2的補充，前述解決了Cache數(shù)據(jù)過時引起數(shù)據(jù)不一致的問題，而對于多任務(wù)系統(tǒng)仍存在著主存內(nèi)容過時引起的數(shù)據(jù)不一致性。只寫存儲器方式就是這樣的一種解決方案。</p><p>　　在這種方式

62、中，進行寫操作時，把數(shù)據(jù)只寫入到主存儲器的對應(yīng)位置上，同時通過查頁表，如果發(fā)現(xiàn)Cache中有與主存被修改頁面相同的頁號，則清除Cache中對應(yīng)數(shù)據(jù)的有效位，即使某頁作廢。這樣在下次進行此頁數(shù)據(jù)的讀操作時，由于Cache中對應(yīng)的有效位無效，處于不命中狀態(tài)，CPU肯定要從主存儲器讀寫數(shù)據(jù)，同時把數(shù)據(jù)交換進Cache中，保證了數(shù)據(jù)的一致性。</p><p>　　4.4 基于目錄的CACHE一致性協(xié)議</p>

63、<p>　　基于目錄的協(xié)議用于網(wǎng)絡(luò)連接的處理機系統(tǒng)。當某臺處理機采用寫無效協(xié)議正在更新一個變量并且其他的處理機也試圖讀該變量時，則會發(fā)生讀缺失并可能導(dǎo)致總線的流量大大增加。另外，寫更新協(xié)議可以更新遠程高速緩存中的數(shù)據(jù)，而其他處理機可能永遠也不會使用這些數(shù)據(jù)。因此，這些問題使采用總線來構(gòu)造大型多處理機系統(tǒng)受到限制。當用多級網(wǎng)絡(luò)來構(gòu)造有數(shù)百臺處理機的大型系統(tǒng)時，就必須修改高速緩存的監(jiān)聽協(xié)議以適應(yīng)網(wǎng)絡(luò)的性能。由于在多級網(wǎng)絡(luò)上實現(xiàn)

64、廣播功能的代價很大，所以把一致性命令只發(fā)給存放塊拷貝的高速緩存。這樣就產(chǎn)生了用于網(wǎng)絡(luò)連接的多處理機系統(tǒng)的基于目錄的協(xié)議。</p><p>　　由共享存儲器的控制器來管理狀態(tài)信息，當需要維持數(shù)據(jù)一致時，檢索這些狀態(tài)，直接使有關(guān)的Cache中的模塊無效化，并在共享主存中建立一個目錄，就叫目錄法。</p><p>　　在多級網(wǎng)絡(luò)中，用高速緩存目錄存放有關(guān)高速緩存塊拷貝駐留在哪里的信息，從而支持高

65、速緩存一致性。各種基于目錄協(xié)議的不同之處主要是目錄如何維護信息和存放什么信息。Tang（1976）提出了第一個目錄方案，用一個中心目錄存放所有高速緩存目錄的拷貝。中心目錄能提供為保證一致性所需要的所有信息。因此，它的容量非常大而且必須采用聯(lián)想方法來檢索，這和單個高速緩存的目錄類似。在大型處理機系統(tǒng)采用中心目錄將存在出現(xiàn)沖突和檢索時間長兩個缺點。</p><p>　　Censier和Feautrier（1978）提

66、出分布式目錄方案。每個存儲器模塊維護各自的目錄，目錄中記錄著每個存儲塊的狀態(tài)和當前的信息。狀態(tài)信息是本地的，但當前的信息指明哪些高速緩存才有該存儲器塊的拷貝。不用廣播的高速緩存一致性協(xié)議必須將所有高速緩存中每個共享數(shù)據(jù)塊拷貝的地址存儲起來。這張高速緩存地址表，不管它是集中的還是分布的，都稱為高速緩存目錄。每個數(shù)據(jù)塊的目錄項包含大量的指針，用來指明塊拷貝的地址。每個目錄項還包含一個重寫位，用來說明高速緩存允許把有關(guān)的數(shù)據(jù)塊寫入。</

67、p><p>　　不同類型的目錄協(xié)議可分為三類：全映射（full-map）目錄、有限（limited）目錄和鏈式（chained）目錄。全映射目錄存放與全局存儲器中每個塊有關(guān)的數(shù)據(jù)。這樣，系統(tǒng)中的每個高速緩存可以同時存儲任何數(shù)據(jù)塊的拷貝，即每個目錄項包含N個指針，N是系統(tǒng)中處理機的數(shù)目。</p><p>　　有限目錄與全映射目錄不同之處是不管系統(tǒng)規(guī)模有多大，它的每個目錄項含有固定數(shù)目的指針。鏈式

68、目錄將目錄分布都各個高速緩存，其余與全映射目錄相同。對三種高速緩存目錄的討論詳見Chaiken，F(xiàn)ields，Kwihara和Agarwal（1990）文獻。</p><p><b>　　4.5軟件控制法</b></p><p>　　軟件解決Cache數(shù)據(jù)一致性問題的方法是以通過編譯進行事先分析的辦法為主流。最簡單的方法是：可寫的共享數(shù)據(jù)都不放在Cache中，但這樣對

69、很多數(shù)據(jù)來講，就失去了Cache的意義。隨著編譯分析技術(shù)的發(fā)展，把程序分成計算單位，每個參數(shù)上都附上Cache可與Cache不可的標志。編譯識別這些標志，再給模塊附上狀態(tài)，由硬件來檢查這些狀態(tài)，進行一致性處理。但這種方法給用戶和編譯帶來麻煩。另外還有循環(huán)分割法等，這些方法都是使Cache整體無效化，但有效的數(shù)據(jù)也全被無效了。于是又提出只把的確要無效化的模塊（或參數(shù)）無效化。把每一個參數(shù)的層次進一步細分為Post（寫回），Invalida

70、te（無效化）和Flush（兩方）等的Cache控制，與寫回Cache控制組合起來，進行更細的控制。還有采用通過編譯來分析共享存儲器的讀信息，注意這時Cache中的數(shù)據(jù)的有效性，分別判斷是從Cache中讀出，還是從共享主存中讀出。這種方法是用硬件來幫助由編譯分析不出來的地方。這樣一來，使用Cache中的數(shù)據(jù)的機會就增多了。同樣為幫助編譯進行分析，而給每個參數(shù)都帶上新編號，運行時對此進行管理，也需要復(fù)雜的硬件開銷。除了編譯</p&g

71、t;<p>　　5 數(shù)據(jù)一致性問題的發(fā)展與展望</p><p>　　隨著計算機吞吐能力的增強，單靠在CPU與主存之間增加一級Cache已遠遠滿足不了工作需要，從486機種開始出現(xiàn)了二級Cache結(jié)構(gòu)，即第一級Cache與CPU集成在一起成為在片Cache，另外單獨在中央處理器與主存之間增加第二級脫片Cache，而目前已發(fā)展到三級Cache結(jié)構(gòu)，將第一、二級Cache均集成在中央處理器內(nèi)，另增設(shè)第三級

72、脫片Cache，從而數(shù)據(jù)一致性問題又有了新的發(fā)展.這二級(三級)Cache與主存之間如何保持數(shù)據(jù)的協(xié)調(diào)一致呢？</p><p>　　1> 穿透LOOK THROUGH；</p><p>　　2> 旁視LOOK ASIDE</p><p>　　穿透結(jié)構(gòu)的優(yōu)點是減少對DRAM系統(tǒng)主存的請求數(shù)目，只有在Cache未命中情況下，來自微處理器的存諸器請求才從Cac

73、he送往主存；旁視結(jié)構(gòu)的優(yōu)點是來自微處理器的存儲器請求同時送到Cache與主存，訪問時微處理器若在Cache中命中則訪問Caehe，同時取消送往主存的存儲器請求，若未命中，那么Cache便不工作，由系統(tǒng)主存完成該存儲器請求。如圖3-3 Cache讀結(jié)構(gòu)。</p><p>　　圖3-3 Cache讀結(jié)構(gòu)</p><p>　　這兩種Cache讀結(jié)構(gòu)其實也就是Cache的組織結(jié)構(gòu)，可做如下設(shè)想：

74、二級Cache結(jié)構(gòu)中第一級Cache。采用穿透結(jié)構(gòu)，規(guī)模增大，采用交叉與多口結(jié)構(gòu)聯(lián)系第二級Cache與主存，配置超級流水線和預(yù)取支持。第二級Cache采用旁視結(jié)構(gòu)，容量有限制增長，負責(zé)對第一級Cache的預(yù)取操作，實質(zhì)上數(shù)據(jù)一致性問題即成為第二級Cache與主存之間的問題了，解決辦法就可借用前文提到的各種辦法：三級Cache結(jié)構(gòu)將第二級Cache也移入CPU，出現(xiàn)第三級脫片Cache，當微處理從第二級Cache仍取不到數(shù)據(jù)時，由第三級脫

75、片Cache的預(yù)取操作彌補二級Cache結(jié)構(gòu)中第一級Cache直接從主存提取的操作，以提高效率，故第一級Cache仍采用穿透結(jié)構(gòu)，第二、三級Cache均采用旁視結(jié)構(gòu)，到第三級的預(yù)取仍不能滿足命中時才與主存交換信息，這樣數(shù)據(jù)一致性問題成了第二、三級Cache與主存之間的問題了，而第二、三級Cache結(jié)構(gòu)完全一致，動作很容易協(xié)調(diào)，所以我們可以把它們看作一個整體。數(shù)據(jù)一致性問題的解決仍是借助前文論述的各種方法加以實現(xiàn)。</p>

76、<p><b>　　6 結(jié)束語</b></p><p>　　隨著半導(dǎo)體技術(shù)、通訊技術(shù)等計算機相關(guān)技術(shù)的發(fā)展，存儲系統(tǒng)的發(fā)展呈現(xiàn)出了新的層次結(jié)構(gòu)和典型的金字塔模型?，F(xiàn)今有關(guān)處理器內(nèi)部的高速緩存的層次結(jié)構(gòu)的前沿研究，主要集中在最后一級高速緩存的有效利用上。同時，多核技術(shù)帶來了計算機性能的飛速提升，為計算機的存儲結(jié)構(gòu)帶來了許多的機遇和挑戰(zhàn)，也為程序的快速運行提供了更多的途徑和可能。<

77、;/p><p>　　通過以上的分析可以看出：用硬件的方法不影響編譯和用戶程序，也不必意識到Cache的存在。但硬件變復(fù)雜了，同時要增加通信開銷和時間延遲。軟件的辦法，編譯負擔太重。由于程序的不確定性，分析的保守性，會造成不必要的Cache不命中。如果硬件變得簡單些，各處理機可以單單進行無效化，通信開銷就可大大減小了。還可以不依賴處理機臺數(shù)和通信方式。而在硬件方法中，總線型多機系統(tǒng)用監(jiān)視法好，而交叉開關(guān)和多級互連網(wǎng)絡(luò)的

78、多機系統(tǒng)中，還是目錄法好。到底作何取舍，每個設(shè)計者將根據(jù)自身的需求做一個合適的選擇。軟件和硬件相結(jié)合的方法，可能是解決Cache不一致性問題的更有效的方法。</p><p>　　目前，關(guān)于Cache一致性的研究還在繼續(xù)，主要方向有三個。一是如何實現(xiàn)這些維護一致性的方法，因為一些方法迄今為止還停留在建議的階段，要評價它們必須在實際實現(xiàn)中才是有效的。二是由于并行處理領(lǐng)域還不成熟，大型多處理機的實際應(yīng)用還很少，難以在實

79、際情況下評價這些方法。三是多處理機Cache的設(shè)計空間很大，而且涉及復(fù)雜的平橫。</p><p>　　高速緩存系統(tǒng)數(shù)據(jù)一致性問題是基于透明性要求產(chǎn)生的。隨著計算機系統(tǒng)結(jié)構(gòu)的發(fā)展，Cache經(jīng)歷了一級、二級、三級多次變革，每一次都帶來了新的問題，但解決方案的核心仍是寫策略，圍繞Cache與主存一致動作，及時更新Cache中過時數(shù)據(jù)和及時更新主存中過時數(shù)據(jù)三個方向發(fā)展。由于輔助硬件的使用寫策略也可以影響系統(tǒng)的性能，所

80、以高速緩存寫策略應(yīng)本著以下三個目標加以采用：</p><p>　　(1)維持存儲器的相關(guān)性。</p><p>　　(2)令微處理器存儲在寫主存上的等待態(tài)數(shù)目最少。</p><p>　　(3)令存儲器寫周期數(shù)最少。</p><p>　　當然，由于此課題本身較難，資料有限，再加上條件和自身水平的限制，而且本人學(xué)習(xí)存儲器系統(tǒng)一致性問題的時間也不是太

81、長，所以本文所講述的內(nèi)容還不能說是一個完整的體系。本文只是就此問題的提出、發(fā)展、以及解決方案和展望進行了初步探討，很多方面還需要進一步完善。因此今后還需要在存儲器系統(tǒng)一致性方面繼續(xù)學(xué)習(xí)，以便更好的進行研究。</p><p><b>　　參考文獻</b></p><p>　　[1] Guang R Gao，Vivek Sarkar. Location Consisten

82、cy–A New Memory Model and Cache Consistency Protocol[J].IEEE Transactions on Computer,2000,49(8). </p><p>　　[2] CWallace，GTremblay，JNAmaral. The Location Consistency memory modeland cache protocol: Specicati

83、on and verication [C]. Technical Report 01-01,ComputerScienceDepartment,MichiganTechnological University.2001.17.</p><p>　　[3] Stenstrom. A Survey of CacheCoherenceSchemes for Multiprocessors[J].IEEE Compute

84、r,1990,23(6):12-24.</p><p>　　[4] TomMiller.Managed DirectX(r)9 KickStart:Graphics and Game Programming.</p><p>　　[5] RSimoni,MHorowitz.DynamicPointer Allocationfor Scalable Cache Coherhence Dire

85、ctories[J].Pro of Intl Sympon Shared Memory Multiprocessing(ISSMM), Tokyo,1991,72-81.</p><p>　　[6] David Mosberger. Memory consistency models[J]. Operating Systems Review, 1993,7(1):18-26.</p><p&g

86、t;　　[7] Andrew S Tanenbaum.分布式操作系統(tǒng)[M].陸麗娜，等，校譯.北京：電子工業(yè)出版社，1999.</p><p>　　[8] 齊家月.CACHE結(jié)構(gòu)設(shè)計.微型機與應(yīng)用，1995,(4).</p><p>　　[9] 戴梅，史嘉權(quán).高速緩存系統(tǒng)的組成結(jié)構(gòu)和數(shù)據(jù)一致性問題的解決.微型機與應(yīng)用，1997，（3）.</p><p>　　[10]

87、 劉永軍.CACHE寫入方法的一點補充.中國電腦報，1998-01-21 .</p><p>　　[11] 薛勝軍.計算機組成原理[M].武漢：華中科技大學(xué)出版社，2000.</p><p>　　[12] 白中英.計算機組成原理[M].北京：科學(xué)版社，2001.</p><p>　　[13] 尹朝慶.計算機組成原理[M].武漢：華中科技大學(xué)出版社，2000. <

88、;/p><p>　　[14] 唐塑飛.計算機組成原理[M].北京：高等教育出版社，2000.</p><p>　　[15] 壟沛曾，陸慰民，楊志強編.《Visual Basic 程序設(shè)計簡明教程》.高等教育出版社.</p><p>　　[16] Kai Hwang.高等計算機系統(tǒng)結(jié)構(gòu)------并行性、可擴展性、可編程性[M].北京：清華大學(xué)出版社，1999.</

89、p><p>　　[17] 肖金立.微型計算機原理與應(yīng)用.電子工業(yè)出版社.</p><p>　　[18] 周明德.微型計算機硬件軟件及應(yīng)用.電子工業(yè)出版社.</p><p>　　[19] 張新榮，楊潔，張剛.計算機組成原理.天津大學(xué)出版社.</p><p>　　[20] 王愛英.計算機組成與結(jié)構(gòu).清華大學(xué)出版社.</p><p&

90、gt;<b>　　致 謝</b></p><p>　　四年的讀書生涯在這個季節(jié)即將劃上句號，而于我的人生卻僅僅只是一個逗號，我也將面對人生的又一次征程?；厥淄簦刑嗟氖伦屛译y以忘懷，有太多的人讓我感動……</p><p>　　首先感謝我的導(dǎo)師楊成衛(wèi)教授，我不是您最出色的學(xué)生，而您卻是我最尊敬的老師。身為一位老教授的您治學(xué)嚴謹，學(xué)識淵博，思想深邃，視野雄闊，為我營

91、造了一種良好的精神氛圍。授人以魚不如授人以漁，置身其間，耳濡目染，潛移默化間，使我不僅接受了全新的思想觀念，更樹立了宏偉的學(xué)術(shù)目標，領(lǐng)會了基本的思考方式。從論文題目的選定到論文寫作的指導(dǎo)經(jīng)由您悉心的點撥，再經(jīng)思考后的領(lǐng)悟，常常讓我有種“山重水復(fù)疑無路，柳暗花明又一村”的感覺。在此，再次感謝楊老師在學(xué)習(xí)、生活等各個方面的關(guān)心和指導(dǎo)，在以后的時間里，我會繼續(xù)努力，不辜負您的期望。</p><p>　　四年的求學(xué)生涯在

92、師長、親友的大力支持下，走得辛苦卻也收獲滿囊。</p><p>　　感謝08級計科一班的所有兄弟姐妹們，和他們相處的日子，我感到非常開心、快樂，也從他們身上學(xué)到了很多東西。希望在以后的日子里，大家能經(jīng)常聯(lián)系，相互幫助，共同進步，體現(xiàn)出我們08級計科一班的風(fēng)采來。</p><p>　　感謝我601的所有兄弟，四年來，有風(fēng)有雨，但我們共同走過，謝謝他們對我的關(guān)心、信任和鼓勵。我會滿懷信心，闖出

93、一片天空！</p><p>　　感謝我所有的老師，感謝他們在我求學(xué)的道路上給我的關(guān)心和幫助，是他們教會了我知識，教會了我成長。</p><p>　　也要特別感謝我的父親母親，焉得諼草，言樹之背，養(yǎng)育之恩，無以回報，你們永遠健康快樂是我最大的心愿。</p><p>　　同時也感謝學(xué)院為我提供良好的做畢業(yè)論文的環(huán)境。</p><p><b&