1、2.直接映象及其變換 1)規(guī)則：主存中每一塊只能映像到Cache中唯一一個(gè)特定位置，如圖所示，主存的第i塊只能映像到第i mod2ncb塊位置上。如圖4.33所示：,Cache,塊位置0,1,2ncb-1,主存,塊0,1,2nmb-1,2ncb-1,塊2ncb+0,2ncb+1,22ncb-1,塊22ncb+0,32ncb-1,0區(qū),1區(qū),2區(qū),2nmbncb-1區(qū),圖 4.33 直接映象規(guī)則,2)變換過程,主存塊號(hào),塊內(nèi)地址,主存地址 nm,nmb,nmr,ncb,ncr,Cache地址 nc,2ncb項(xiàng),相聯(lián)比較,不等,塊失效,區(qū)號(hào),0,1,2ncb-1,相等,訪Cache,區(qū)號(hào) (按地址

2、訪問存儲(chǔ)器),由 2ncb 中 選 1,圖 4.34 直接映象的 地址變換過程,3)優(yōu)缺點(diǎn) 優(yōu)點(diǎn)： a)所需硬件簡單，只需要容量較小的按地址訪問 的區(qū)號(hào)標(biāo)志表存儲(chǔ)器和少量外比較電路，因此 成本低。 b)訪問Cache與訪問區(qū)號(hào)表、比較區(qū)號(hào)是否相符 的操作是同時(shí)進(jìn)行的。當(dāng)Cache命中時(shí)就意味著 省去了地址變換所花費(fèi)的時(shí)間。,缺點(diǎn)：直接映象法最致命的缺點(diǎn)就是Cache的塊 沖突率很高。只要有兩個(gè)或兩個(gè)以上經(jīng)常使用的塊 恰好被映象到Cache的同一個(gè)塊位置時(shí)，就會(huì)使得 Cache的命中率急劇下降。而且，即使此時(shí)Cache 中有大量的空閑塊存在，仍然會(huì)發(fā)生塊失效和塊沖 突，無法使用Cache中的空閑

3、塊，所以，Cache的 利用率很低。正是因?yàn)檫@個(gè)原因才使得目前采用直 接映象的Cache存儲(chǔ)器很少了。,3.組相聯(lián)映象及其變換 1)思想：簡要說明如下圖4.35所示，將Cache空間和主存空間都分組，每組S塊(S2s)。Cache一共2ncb個(gè)塊，分成Q組(Q= 2q)，整個(gè)Cache是一區(qū)。主存分成與Cache一樣大小的2nd個(gè)區(qū)，其地址按區(qū)號(hào)、組號(hào)、組內(nèi)塊號(hào)、塊內(nèi)地址分成對(duì)應(yīng)的4個(gè)字段。主存地址的組號(hào)、組內(nèi)塊號(hào)分別用q、s 字段表示，它們的寬度和位置與Cache地址的q、s是一致的。,2)規(guī)則：組相聯(lián)映象指的是各組之間直接映象，但組內(nèi)各塊間則是全相聯(lián)映象。如圖4.35所示。,組號(hào) q,組內(nèi)

4、塊號(hào) s,塊內(nèi)地址 ncr,組號(hào) q,組內(nèi)塊號(hào) s,塊內(nèi)地址 nmr,區(qū)號(hào) nd,1位,1位,2位,2位,1位,ncb,nmb,nc,nm,塊位置0,塊0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,9,10,11,12,13,14,15,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,0,1,2,3,第0組,第0組,第1組,第1組,第0組,第1組,第0區(qū) (Cache容量),第1區(qū) (Cache容量),Cache,主存,組內(nèi)全相聯(lián) 組間直接相聯(lián) 圖4.35 組相聯(lián)映象規(guī)則,3)討論 當(dāng)組相聯(lián)映象的S值大到等于Cache的塊數(shù)(即s= ncb)

5、時(shí)就變成了全相聯(lián)映象，而當(dāng)S值小到只有1塊(即無s 字段)時(shí)就變成了直接映象。因此全相聯(lián)映象和直接映 象只是組相聯(lián)映象的兩個(gè)極端。在Cache空間大小及 塊的大小都已經(jīng)確定的情況下，Cache的總塊數(shù)就定 了，但結(jié)構(gòu)設(shè)計(jì)者仍可以對(duì)S和Q值進(jìn)行選擇。Q和S 的選取主要依據(jù)對(duì)塊沖突概率、塊失效率、映象表復(fù) 雜性和成本、查表速度等的折衷權(quán)衡。組內(nèi)塊數(shù)S愈 多，塊沖突概率和塊失效率愈低，映象表愈復(fù)雜、成 本愈高，查表速度愈慢。所以通常采用在典型工作負(fù) 荷下進(jìn)行模擬而定。,4)地址變換,組號(hào) q,組內(nèi)塊號(hào) s,塊內(nèi)地址 nmr,區(qū)號(hào) nd,組號(hào) q,組內(nèi)塊號(hào) s,塊內(nèi)地址 ncr,nm,nc,直接,直接

6、,相聯(lián)比較,不等,塊失效,相等,相聯(lián)比較,nd,s,s,nd s,表的總?cè)萘繛?2ncb 2q2s行,2q 組 中 選 1,2s行,4.段相聯(lián)映象 在全相聯(lián)、直接相聯(lián)、組相聯(lián)映象的基礎(chǔ)上還可 以有各種變形，段相聯(lián)就是一例。段相聯(lián)實(shí)質(zhì)上是 組相聯(lián)的特例。他是采用組間全相聯(lián)、組內(nèi)直接映 象。為了與組相聯(lián)加以區(qū)別，將這種映象方式稱為 段相聯(lián)。就是說，段相聯(lián)映象是把主存和Cache分 成具有相同的Z塊的若干段，段與段之間采用全相 聯(lián)映象，而段內(nèi)各塊之間采用直接映象。如下圖所示：,補(bǔ)充知識(shí)：,塊0,塊1,塊2,Z1,Cache,主存,塊0,塊1,塊2,Z1,塊0,塊1,塊2,Z1,塊0,塊1,塊2,Z1

7、,塊0,塊1,塊2,Z1,段0,段0(Z個(gè)段),段1,段2nmb/Z1,段2ncb/Z1,具有每段Z個(gè)塊的段相聯(lián)映象,段間全相聯(lián) 段內(nèi)直接,4.3.3 替換算法的實(shí)現(xiàn) 當(dāng)訪存發(fā)生Cache塊失效，需要把主存塊按所采 用的映象規(guī)則裝入Cache時(shí)，如果又出現(xiàn)Cache塊沖 突，就必須按某種策略選擇將Cache中的哪一塊替 換出去。Cache主存存儲(chǔ)層次的替換算法與虛 擬存儲(chǔ)器的沒有什么不同，不外乎也是FIFO法或 LRU法，其中LRU法最為常用。,1.堆棧法 1)思想 我們?cè)?.2.2中講過，LRU法是堆棧型替換算法， 也講了對(duì)于LRU算法，堆棧St中由棧頂?shù)綏５椎母?項(xiàng)（行）恒反映出到t時(shí)刻，

8、實(shí)存中各頁被訪問過的 近遠(yuǎn)次序，以及每訪問一頁，堆棧St中各項(xiàng)的變換 過程。結(jié)果是此堆棧的棧頂恒存放近期最近訪問過 的頁的頁號(hào)，而棧底恒存放近期最久沒有方問過的 頁的頁號(hào)，即準(zhǔn)備被替換掉的頁的頁號(hào)。那么，我 們?cè)贑ache主存存儲(chǔ)層次中就可以按此思想實(shí) 際組成一個(gè)硬件堆棧。,2)過程,（塊號(hào)）,（塊號(hào)）,（塊號(hào)）,（塊號(hào)）,（塊號(hào)）,2ncb個(gè)寄存器,需重新排列的塊號(hào) 都下推一行,被訪問的塊號(hào) （經(jīng)相聯(lián)比較找到）,寄存器堆棧 壓入,ncb位,近期最近訪 問過的塊,近期最久沒有 訪問過的塊,全相聯(lián)映象LRU法經(jīng)堆棧實(shí)現(xiàn)（需要有相聯(lián)比較功能）,3)缺點(diǎn)： 這種硬件堆棧既要求具有相聯(lián)比較的功能，又要

9、 求能全下移、部分下移和從中間取出一項(xiàng)的功能， 成本較高，因此只適用于組相聯(lián)且組內(nèi)塊數(shù)較少的 LRU替換場合。 4)變形 上述這種堆棧，各塊被訪問的先后次序由該項(xiàng)在 堆棧中距離棧底是近還是遠(yuǎn)來反映。為了避免堆棧 中各行存放的內(nèi)容經(jīng)常同時(shí)進(jìn)行下移，以便節(jié)省成 本，我們采用另一種變形，即將存放塊號(hào)的寄存器 的幾何位置與Cache中的塊號(hào)對(duì)應(yīng)，而用寄存器存,放值的大小來表示已被訪問過的遠(yuǎn)近次序。以組相 聯(lián)為例，每一組均使用如圖4.39那樣的一個(gè)寄存器 組，由2s個(gè)寄存器組成，每個(gè)寄存器為s位寬，可以 存放表示從0到2s1的次序值。如果讓越是最近訪 問的，其次序值愈小，則只需通過相聯(lián)比較求最大 值（不

10、是相聯(lián)比較相符），找到該最大值所在的寄 存器號(hào)，這就是對(duì)應(yīng)Cache中應(yīng)該被替換掉的塊的 塊號(hào)。,第0塊的訪問次序,第1塊的訪問次序,第2塊的訪問次序,第2s-1塊的訪問次序,塊0,塊1,塊2,塊2s-1,2s個(gè) 寄存器,S位 （其中一組）,Cache存儲(chǔ)器 （其中一組）,圖 4.39 組相聯(lián)LRU法經(jīng)寄存器實(shí)現(xiàn) （每組一個(gè)，需要有相聯(lián)比較功能）,2.比較對(duì)法 1)思路 比較法的基本思路是讓各個(gè)塊成對(duì)組合，用一個(gè) 觸發(fā)器的狀態(tài)來表示該比較對(duì)內(nèi)兩塊訪問的遠(yuǎn)近次 序，再經(jīng)門電路就可以找到LRU塊。比如說有A B C三塊，互相之間可以組合成AB BA AC CA BC CB6對(duì)，其中AB和BA、AC

11、和CA、BC和CB是重復(fù) 的，所以TAB為“1”，表示A比B更近被訪問過； TAB 為“0”，則表示B比A更近被訪問過。TAC 、TBC也類 似定義。這樣，當(dāng)訪問過的次序?yàn)锳 B C，即最近,訪問過的為A，最久未被訪問過的為C，則這三個(gè)觸 發(fā)器狀態(tài)分別為TAB1，TAC1，TBC1。如果訪 問過的次序?yàn)锽 A C，C為最久未被訪問過的塊，則 此時(shí)必有TAB0，TAC1，TBC1。因此最久未被 訪問過的塊C作為被替換掉的塊的話，用布爾代數(shù) 式必有： CLRUTAB TACTBC +TAB TACTBC TACTBC 同理可得： BLRUTABTBC ； ALRUTAB TAC 因此，完全可以用門

12、、觸發(fā)器等硬件組合實(shí)現(xiàn)，如 圖4.40所示：,&,&,&,0,1,0,1,0,1,TAB,TAC,TBC,ALRU,BLRU,CLRU,訪問B,訪問C,訪問A,圖 4.40 用比較對(duì)法實(shí)現(xiàn)LRU算法,2)分析 我們來看比較對(duì)法所用的硬件量。由于每塊均可 能作為LRU塊，其信號(hào)需要用一個(gè)與門產(chǎn)生，例如 ALRU與門要有從TAB TAC來的輸入， BLRU門要有從 TAB ，TBC來的輸入，而與每塊有關(guān)的對(duì)數(shù)個(gè)數(shù)為塊 數(shù)減去1，所以與門的扇入數(shù)是塊數(shù)減去1。若p為 塊數(shù)，量量組合，比較對(duì)觸發(fā)器的個(gè)數(shù)應(yīng)為Cp2，即 為p(p-1)/2。表4.3給出了比較對(duì)法塊數(shù)p的取值與門 數(shù)、門的輸入端數(shù)及比較對(duì)

13、觸發(fā)器數(shù)的關(guān)系。,3)總結(jié) 替換算法實(shí)現(xiàn)的設(shè)計(jì)要圍繞下面兩點(diǎn)來考慮： a)如何對(duì)每次訪問進(jìn)行記錄（使用位法、堆棧法和比較對(duì)法所用的記錄方法都不同）； b)如何根據(jù)所記錄的信息來判定近期內(nèi)哪一塊最久沒有被訪問過。由此可見，實(shí)現(xiàn)方法和所用的映象方法密切相關(guān)。 例如，對(duì)于主存輔存存儲(chǔ)層次的全相聯(lián)映象 宜于采用使用位法或類似的方法，而不宜采用堆棧 法和比較對(duì)法；但對(duì)于Cache主存存儲(chǔ)層次的 組相聯(lián)映象，因?yàn)榻M內(nèi)塊數(shù)較少，就宜于采用比較,對(duì)法或堆棧法。替換算法的設(shè)計(jì)和實(shí)現(xiàn)也和器件的 發(fā)展密切相關(guān)，隨著器件技術(shù)的發(fā)展，尤其是高速 相聯(lián)存儲(chǔ)器片子的改進(jìn)，已經(jīng)而且必然會(huì)不斷研制 出新的更好的實(shí)現(xiàn)方法。,4.

14、3.4 Cache的透明性及性能分析 1.Cache的透明性分析 1)兩種問題的出現(xiàn) 雖然Cache是主存的一部分副本，主存中某單元的 內(nèi)容卻可能在一段時(shí)間里會(huì)與Cache中對(duì)應(yīng)單元的內(nèi) 容不一致。例如，CPU往Cache寫入，修改了Cache 中某單元的內(nèi)容，而在主存中對(duì)應(yīng)于此單元的內(nèi)容 卻可能仍是原來的，沒有改變。這時(shí)，如果CPU或 I/O處理機(jī)及其他處理機(jī)要經(jīng)主存交換信息，那么主 存內(nèi)容跟不上Cache對(duì)應(yīng)內(nèi)容變化的這種不一致就會(huì) 造成錯(cuò)誤。,同樣，I/O處理機(jī)或其他處理機(jī)已把新的內(nèi)容送入 主存某個(gè)區(qū)域，而Cache中對(duì)應(yīng)于此區(qū)域的副本內(nèi) 容卻仍可能是原來的。這時(shí)，如果CPU要從Cach

15、e 中讀取信息，也會(huì)因?yàn)檫@種Cache內(nèi)容跟不上主存 對(duì)應(yīng)內(nèi)容變化的不一致而造成錯(cuò)誤。因此，必須采 取措施解決好由于讀寫過程中產(chǎn)生的Cache和主存 對(duì)應(yīng)內(nèi)容不一致的問題。,2)寫回法 寫回法是在CPU執(zhí)行寫操作時(shí)，只是把信息寫入 Cache，僅當(dāng)需要被替換時(shí)，才將已經(jīng)被寫入過的 Cache塊先送回主存，然后再調(diào)入新塊。這種方法 也稱為抵觸修改法，類似于虛擬存儲(chǔ)器中進(jìn)行頁面 替換時(shí)的情況。因此，Cache主存存儲(chǔ)層次的 地址映象表中需對(duì)Cache中的每個(gè)塊設(shè)置一個(gè)“修改 位”，作為該塊裝入Cache后是否被修改過的標(biāo)志。 這樣在塊替換時(shí)，根據(jù)該塊的修改位是否位1，就可 以決定替換時(shí)是否先將該塊

16、存回主存原來的位置。,3)寫直達(dá)法 寫直達(dá)法也稱為存直達(dá)法，它利用Cache主 存存儲(chǔ)層次在處理機(jī)和主存之間的直接通路，每當(dāng) 處理機(jī)寫入Cache的同時(shí)，也通過此通路直接寫入 主存。這樣，在塊替換時(shí)，就不必先寫回主存，而 可以立即調(diào)入新頁。顯然，寫回法是把開銷花在每 次需要替換的時(shí)候，而寫直達(dá)法則把開銷花在每次 寫入Cache時(shí)都附加一個(gè)比寫Cache長的多的寫主存 時(shí)間。,4)寫不命中處理 當(dāng)出現(xiàn)寫不命中時(shí)，無論是寫回法還是寫直達(dá)法 都有一個(gè)在寫時(shí)是否取的問題。一種是不按寫分配 法，即當(dāng)Cache寫不命中時(shí)只寫入主存，該寫地址 單元所在塊不從主存調(diào)進(jìn)Cache。另一種是按寫分 配法，即當(dāng)Ca

17、che不命中時(shí)除寫入主存外，還把該 寫地址單元所在的塊由主存調(diào)入Cache。這兩種策 略對(duì)不同的主存修改算法，其效果不同，但命中率 差別不大。目前寫回法一般采用按寫分配法，而寫 直達(dá)法則一般采用不按寫分配法。,寫回法和寫直達(dá)法都需要有少量緩沖器。寫回法 中緩沖器用于暫存將要寫回的塊，使之不必等待被 替換塊寫回主存后才開始進(jìn)行Cache取。寫直達(dá)法 中緩沖器則用于緩沖由寫Cache所要求的寫回主存 的內(nèi)容，使CPU不必等待這些寫主存完成就能往下 運(yùn)行。緩沖器由要存的數(shù)據(jù)和要存入的目標(biāo)地址組 成。在寫直達(dá)系統(tǒng)中容量為4的緩沖器就可以顯著 改進(jìn)其性能，IBM 3033就是這樣用的。要注意的這 些緩沖

18、器對(duì)Cache和主存是透明的。在設(shè)計(jì)時(shí)，要 處理好可能由它們所引起的錯(cuò)誤(如另一個(gè)處理機(jī)要 訪問的主存單元的內(nèi)容正好仍在緩沖器中)。,5)兩種方法對(duì)比 a)寫回法有利于省去許多將中間結(jié)果寫入主存的無謂開銷。但是增加了Cache的復(fù)雜性。 b)可靠性上寫回法不如寫直達(dá)法好。 c)具體采用哪種方法還與系統(tǒng)使用場合有關(guān)。 d)如果讓多CPU共享主存交換信息改成共享Cache交換信息，信息的一致性就能得到保證。 e)對(duì)于共享主存的多CPU系統(tǒng)，絕大多數(shù)還是采用各個(gè)CPU都有自己的Cache的方式與共享主存連接。這樣的系統(tǒng)由于Cache的透明性，僅靠寫直達(dá)法并不能保證同一主存單元在各個(gè)Cache中的對(duì)應(yīng)

19、內(nèi)容都一致。如下圖：,要采取措施保證讓有此單元的各個(gè)Cache的內(nèi)容 都一致才行。,CPU A,Cache a,CPU B,Cache b,主存,圖 4.41 每個(gè)處理機(jī)都有Cache的共享多處理機(jī)系統(tǒng),解決辦法： 采用播寫法：即任何處理機(jī)要寫入Cache時(shí)，不僅要寫入自己Cache的目標(biāo)塊和主存中，還把信息或者播寫到所有Cache有此單元的地方，或者讓所有Cache有此單元的塊作廢以便下次訪問時(shí)按缺塊處理，從主存中重新調(diào)入。 控制某些共享信息（如信號(hào)燈或作業(yè)隊(duì)等）不等進(jìn)入Cache。 目錄表法：即在CPU讀/寫Cache不命中時(shí)，先查主存中的目錄表以判定目錄塊是否在別的Cache內(nèi)，以及是否

20、正在被修改等，然后再?zèng)Q定如何讀寫此塊。,6)第二種問題 Cache內(nèi)容跟不上已變化了的主存內(nèi)容的問題，有 兩種解決辦法： a)當(dāng)I/O處理機(jī)未經(jīng)Cache往主存寫入新內(nèi)容的同時(shí)，由OS經(jīng)某個(gè)專用指令清除整個(gè)Cache。這種辦法的缺點(diǎn)是象我們?cè)谥v述用專用指令清除快表一樣，會(huì)使Cache對(duì)OS和系統(tǒng)程序員成為不透明的，因此并不好。 b)當(dāng)I/O處理機(jī)往主存某個(gè)區(qū)域?qū)懭胄聝?nèi)容時(shí)，由專用硬件自動(dòng)地將Cache內(nèi)對(duì)應(yīng)此區(qū)域地副本作廢，而不必由OS進(jìn)行任何干預(yù)，從而保持Cache的透明性。,2. Cache的取算法 1)預(yù)取法 為了便于硬件實(shí)現(xiàn)，通常只預(yù)取直接順序的下一 塊，即在訪問到主存的第i塊(不論是

21、否已取進(jìn)Cache) 時(shí)，只有第i1塊才是可能的預(yù)取塊。至于何時(shí)將 該塊取進(jìn)，可以有恒預(yù)取和不命中時(shí)預(yù)取兩種不同 的方法。恒預(yù)取指的是只要訪問到主存的第i塊的某 個(gè)字，不論Cache是否命中，恒發(fā)預(yù)取指令。不命 中時(shí)預(yù)取僅當(dāng)訪問第i塊不命中時(shí)，才發(fā)預(yù)取指令。,2)影響命中率的其它因素 a)塊的大?。?若每塊的字節(jié)數(shù)過少，預(yù)取的效果不明顯。從預(yù) 取的需要出發(fā)，希望塊盡可能大。但若每塊的字節(jié) 數(shù)過多，一方面可能會(huì)預(yù)取進(jìn)不需要的信息，另一 方面由于Cache容量有限，又可能把正在使用或近 期使用到的信息給替換出去，反而降低了命中率。 從模擬結(jié)果來看，每塊的字節(jié)數(shù)如果超過了256，就 會(huì)出現(xiàn)這種情況。

22、,b)預(yù)取開銷： 要預(yù)取就要有訪主存開銷和將它取進(jìn)Cache的訪 Cache開銷，還要加上把被替換的塊寫回主存的開 銷，這些開銷會(huì)增加主存和Cache的負(fù)擔(dān)，干擾和 延緩程序的執(zhí)行。 由上可知，采用預(yù)取法的效果不能只從命中率的 提高來衡量，還需要從所花費(fèi)的開銷多少來考慮。 而這種開銷的多少可以通過對(duì)按需取進(jìn)法的不命中 開銷與預(yù)取法的不命中開銷和預(yù)取開銷(包括訪存開 銷及對(duì)Cache的干擾影響)二者之和的比較來得到。,3)計(jì)算分析 設(shè)Dc為Cache不命中時(shí)，由主存調(diào)一塊進(jìn)Cache的 開銷，則： a)按需取進(jìn)法的不命中開銷為： Dc 不命中率(按需取進(jìn)法) b)預(yù)取法不命中的開銷為： Dc 不

23、命中率(預(yù)取法) 而預(yù)取法還應(yīng)有預(yù)取開銷，為此，我們?cè)O(shè)： 預(yù)取率：預(yù)取總塊數(shù)/訪存總塊數(shù) Pa ：預(yù)取訪主存和訪Cache的開銷,補(bǔ)充知識(shí)：,c)預(yù)取法取進(jìn)預(yù)取塊的開銷為： Pa 預(yù)取率 訪問率：訪Cache的總次數(shù)/程序訪Cache的總次數(shù)，即(程序訪Cache次數(shù)預(yù)取訪Cache次數(shù))/程序訪Cache次數(shù)。 Ac：由于預(yù)取訪Cache占用了Cache，延遲、干擾了程序?qū)ache的訪問的預(yù)取干擾開銷。 d)預(yù)取法對(duì)程序訪Cache的映象為： Ac(訪問率1) e)結(jié)論 由上計(jì)算可知，只有下式成立，即：,補(bǔ)充知識(shí)：,Dc 不命中率(按需取進(jìn)) Dc 不命中率(預(yù)取) Pa 預(yù)取率 Ac(訪

24、問率1) 時(shí)，預(yù)取法才是可取的。這里，采用緩沖器技術(shù)是 減少預(yù)取干擾的好辦法。Cache和主存都設(shè)置預(yù)取 專用緩沖器，使預(yù)取訪主存與訪Cache都盡可能在 主存、Cache空閑時(shí)進(jìn)行。,補(bǔ)充知識(shí)：,3.任務(wù)切換對(duì)失效率的影響 1)兩種失效率 a)冷啟動(dòng)(Coldstart)失效率： 從Cache為空(指新進(jìn)程所需的內(nèi)容都未裝入Cache 內(nèi))開始到Cache全部被裝滿這一期間的失效率。 b)熱啟動(dòng)(Warmstart)失效率： 從Cache為現(xiàn)行進(jìn)程裝滿之后測出的失效率。,補(bǔ)充知識(shí)：,2)影響失效率的因素 a)與任務(wù)的切換頻度(平均時(shí)間間隔Qsw)有關(guān) Qsw對(duì)失效率的影響和工作負(fù)荷有很大關(guān)系

25、。比 如，如果進(jìn)程切換發(fā)生在用戶程序因?yàn)橄到y(tǒng)需要運(yùn) 行管理程序來處理某個(gè)I/O中斷或時(shí)鐘中斷請(qǐng)求時(shí)， 則Qsw值愈小，表明由管理程序切換回原先的用戶程 序愈快，Cache中保留的原先程序的指令和數(shù)據(jù)就 愈多，即失效率愈低。但是如果進(jìn)程切換是在幾個(gè) 用戶程序之間進(jìn)行，且每個(gè)進(jìn)程都要更換掉Cache 中的大部分內(nèi)容時(shí)，Qsw值愈小就會(huì)使失效率愈高。,補(bǔ)充知識(shí)：,b)與Cache的容量有關(guān) Qsw值一定時(shí)，若容量過小，存不下該程序的工 作區(qū)，那么就會(huì)有很高的熱啟動(dòng)失效率。因此，增 大Cache的容量可使這個(gè)矛盾迅速緩解，而使失效率 急劇下降；但在容量增大到基本上保護(hù)得了足夠大 的工作區(qū)之后，容量大小

26、對(duì)失效率的下降就趨于平 緩，也就是說增大容量對(duì)降低失效率已影響不大。,補(bǔ)充知識(shí)：,3)解決辦法 a)增大Cache容量 b)修改調(diào)度算法，使任務(wù)切換回來前，有用的信息仍能保留在Cache中而不被破壞。 c)設(shè)置多個(gè)Cache，例如設(shè)置兩個(gè)，一個(gè)專用于管理程序，一個(gè)專用于用戶程序。這樣，在管態(tài)和目態(tài)之間切換時(shí)，不會(huì)破壞各Cache中的內(nèi)容。 d)對(duì)于某些操作，例如長的向量運(yùn)算、長的字符行運(yùn)算等，可以不經(jīng)過Cache直接進(jìn)行，以避免這些操作由于使用Cache而從Cache中替換出大量更有希望將重新使用的數(shù)據(jù)。,補(bǔ)充知識(shí)：,4.影響Cache存儲(chǔ)器性能的因素 1)不命中率與Cache的容量、組的大小

27、和塊的大小的一般關(guān)系,不命中率1Hc,Cache容量,組的大小一定,塊的大小減小,(a),不命中率1Hc,Cache容量,塊的大小一定,組的大小減小,(b),圖4.42 塊的大小、組的大小與Cache容量對(duì)Cache命中率的影響,2)Cache主存存儲(chǔ)層次的等效速度與命中率的關(guān)系 設(shè)：tc為Cache的訪問時(shí)間； tm為主存周期； Hc為訪Cache的命中率； 則Cache存儲(chǔ)器的等效存儲(chǔ)周期為： taHc tc(1 Hc)tm 與主存輔存存儲(chǔ)層次不同的是一旦Cache不命 中，由于主存與CPU之間有直接通路，CPU對(duì)第二 級(jí)的訪問時(shí)間就是tm ，而不是調(diào)塊時(shí)間再加一個(gè)訪 Cache的時(shí)間了。

28、這樣，采用Cache比之于處理機(jī)直,接訪問主存，其速度提高的倍數(shù)為： tm / ta tm / (Hc tc(1 Hc)tm ) 1/(1(1tc/tm)Hc) 因?yàn)镠c總是小于1，可以令Hc/(+1)，代入 上式得： (+1) 顯然，不管Cache本身的速度有多高，只要Cache 的命中率有限，那么采用Cache主存存儲(chǔ)層次 后，速度能提高的最大值是有限的，不會(huì)超過+1 倍。,tm tm + tc,3)Cache的容量對(duì)機(jī)器速度的影響 對(duì)流水機(jī)器，機(jī)器速度與主存速度、CPU拍寬、 Cache容量的可能關(guān)系如圖4.49所示，機(jī)器的單位是 MIPS(每秒執(zhí)行百萬條指令)，主存采用多體交叉存 取。

29、 a)由圖可見，主存速度和CPU周期一定時(shí)，由不 用Cache到Cache容量從4KB增大到64KB，機(jī)器速 度有了顯著提高，尤其是在主存速度較低時(shí)。 b)還可以看出，Cache容量的增大，可以顯著降 低對(duì)主存速度的要求。,4)總結(jié) 總之，Cache本身的速度與容量都會(huì)影響Cache存 儲(chǔ)器的等效訪問速度。如果對(duì)Cache存儲(chǔ)器的等效 訪問速度不滿意，需要改進(jìn)的話就要作具體分析， 看看現(xiàn)在Cache的等效訪問速度是否已接近于第一 級(jí)Cache本身的訪問速度。如果尚差的較遠(yuǎn)，說明 Cache的命中率低，這個(gè)時(shí)時(shí)就不是去采用更高速 度的Cache片子來替換現(xiàn)有的Cache片子，而應(yīng)當(dāng)從 提高Cac

30、he的命中率入手，包括調(diào)整組的大小、替 換算法以及增大Cache容量等方面著手，否則該速 度是無法提高的。相反的，如果實(shí)際的等效訪問速,度已經(jīng)非常接近于Cache本身的訪問速度還不能滿 足速度要求時(shí)，就只有更換更高速的Cache片子。 否則，任何其它途徑也是不會(huì)有什么效果的。因此 我們不能盲目設(shè)計(jì)和改進(jìn)，否則花了很大代價(jià)，卻 反而降低了系統(tǒng)的性能價(jià)格比。,4.3.5 “Cache主存輔存”存儲(chǔ)層次 1.三級(jí)存儲(chǔ)層次的地址變換： CPU提供訪存的虛地址可能需要變換成Cache地 址、主存地址或輔存地址。 1)對(duì)應(yīng)于虛地址的單元已在Cache中 這時(shí)就需要把虛地址直接變換成Cache地址來訪問 C

31、ache，而不是先把虛地址變換成主存實(shí)地址，再 由主存實(shí)地址變換成Cache地址，這樣可以縮短地 址變換的時(shí)間。,補(bǔ)充知識(shí)：,2)對(duì)應(yīng)單元已在主存但尚未調(diào)入Cache 這時(shí)則需要把虛地址經(jīng)快表和慢表變換成主存實(shí) 地址去訪主存，對(duì)讀訪問以及采用按寫訪問還必須 進(jìn)行虛地址到Cache地址的映象或變換，以便把包 含對(duì)應(yīng)此單元所在的一塊調(diào)入或替換進(jìn)Cache。 3)對(duì)應(yīng)單元還不在主存 這時(shí)就需要把虛地址變換成輔存實(shí)地址去輔存調(diào) 頁，同時(shí)還要將虛地址映象變換成主存實(shí)地址將頁 調(diào)入主存，以及把虛地址映象變換成Cache地址， 將其中的一塊裝入Cache。,補(bǔ)充知識(shí)：,2.訪問Cache過程 在這三級(jí)存儲(chǔ)層

32、次中通常總是讓頁的大小恰好時(shí) 塊的2的冪倍，每一塊的大小又是字的2的冪倍。而 且每次用虛頁號(hào)查快表和慢表以取得主存實(shí)地址和 用虛地址對(duì)應(yīng)Cache塊號(hào)位置的虛塊號(hào)經(jīng)組相聯(lián)去 訪Cache(Cache中每個(gè)單元存放有主存實(shí)地址和對(duì) 應(yīng)的數(shù)據(jù))同時(shí)進(jìn)行。若能在快表中找到，就用由快 表來的主存實(shí)地址與由Cache中讀出的主存實(shí)地址 相比較。當(dāng)兩者相符，存在Cache中該單元的數(shù)據(jù) 就是要訪問的虛、實(shí)地址的內(nèi)容。寫Cache的過程 與此類似。,補(bǔ)充知識(shí)：,4.4 主存保護(hù),大多數(shù)計(jì)算機(jī)系統(tǒng)設(shè)計(jì)成讓其資源能被并行的多 個(gè)用戶所共享，就主存來說，就同時(shí)存有多個(gè)用戶 的程序和系統(tǒng)軟件。為使系統(tǒng)能正常工作，應(yīng)

33、防止 由于一個(gè)用戶程序出錯(cuò)而破壞主存中其它用戶的程 序或系統(tǒng)軟件，還要防止一個(gè)用戶程序不合法地訪 問不是分配給它的主存區(qū)域，哪怕這種訪問不會(huì)引 起系統(tǒng)破壞。因此，系統(tǒng)結(jié)構(gòu)需要為主存的使用提 供存儲(chǔ)保護(hù)，它是多道程序和多處理機(jī)系統(tǒng)所必不 可少的。,補(bǔ)充知識(shí)：,1.存儲(chǔ)區(qū)域的保護(hù) 1)主存系統(tǒng)的保護(hù) 對(duì)于不是虛擬存儲(chǔ)器的主存系統(tǒng)可采用第二章講 過的界限寄存器方式，由系統(tǒng)軟件經(jīng)特權(quán)指令置定 上、下界寄存器，從而劃定每個(gè)用戶程序的區(qū)域， 禁止它越界訪問。由于用戶程序不能改變上、下界 的值，因此不論它如何出錯(cuò)，也只能破壞該用戶自 身的程序，侵犯不到別的用戶程序及系統(tǒng)軟件。,補(bǔ)充知識(shí)：,2)虛擬存儲(chǔ)系統(tǒng)

34、由于界限寄存器方式只適用于每個(gè)用戶程序占用 主存一個(gè)或幾個(gè)(當(dāng)有多對(duì)上、下界寄存器時(shí))連續(xù) 的區(qū)域；而對(duì)于虛擬存儲(chǔ)系統(tǒng)，由于一個(gè)用戶的各 頁能離散地分布于主存內(nèi)，從而無法使用這種保護(hù) 方式。對(duì)虛擬存儲(chǔ)系統(tǒng)的主存區(qū)域保護(hù)就需要采用 頁表保護(hù)和鍵式保護(hù)等方式。,補(bǔ)充知識(shí)：,a)頁表保護(hù) 每個(gè)程序都有自己的頁表，其行數(shù)等于該程序的 虛頁數(shù)。例如它有4頁，則只能有0、1、2、3這4個(gè) 虛頁號(hào)。設(shè)由OS建立的程序也表，這4個(gè)虛頁號(hào)分 別對(duì)應(yīng)于實(shí)頁號(hào)4、8、10、14，則不論虛地址如何 出錯(cuò)，總只能影響主存中分配給該程序的第4、8 、 10、14號(hào)實(shí)頁。假設(shè)虛頁號(hào)錯(cuò)成5，肯定不可能在該 程序的頁表中找到，

35、也就訪問不了主存，當(dāng)然就不 會(huì)映象主存中其它程序的區(qū)域。這正是虛擬存儲(chǔ)系 統(tǒng)本身固有的保護(hù)機(jī)能，也是它的一大優(yōu)點(diǎn)。為了 便于實(shí)現(xiàn)這種保護(hù)，還可以在段表中的每行內(nèi)，不,補(bǔ)充知識(shí)：,僅設(shè)置頁表起點(diǎn)，還設(shè)置段長(頁數(shù))項(xiàng)。若出現(xiàn)該 段內(nèi)的虛頁號(hào)大于段長，則可以發(fā)越界中斷。 這種頁表保護(hù)是在沒有形成主存實(shí)地址前進(jìn)行的 保護(hù)，使之無法形成能侵犯別的程序區(qū)域的主存地 址。然而，若地址形成環(huán)節(jié)由于軟、硬件方面的故 障而形成了不屬于本程序區(qū)域的錯(cuò)誤主存地址時(shí)， 則上述這種保護(hù)就無能為力了。因此，還應(yīng)采取進(jìn) 一步的保護(hù)措施，鍵方式就是其中成功的一種。,補(bǔ)充知識(shí)：,b)鍵方式 是由OS按當(dāng)時(shí)主存的使用分配狀況給主

36、存的每 頁配一個(gè)鍵，稱為存儲(chǔ)鍵，它相當(dāng)于一把“鎖”。所 有頁的存儲(chǔ)鍵存在于相應(yīng)的快速寄存器內(nèi)，每個(gè)用 戶(任務(wù))的各實(shí)頁的頁存儲(chǔ)鍵都相同。為了打開這 把鎖，需要有把“鑰匙”，稱為訪問鍵。每個(gè)用戶的 訪問鍵由OS給定，存在處理機(jī)的程序狀態(tài)字(PSW) 或控制寄存器中。程序每次訪存前，要核對(duì)主存地 址所在頁的存儲(chǔ)鍵是否與該道程序的訪問鍵相符， 只有相符才準(zhǔn)訪問。這樣，就是錯(cuò)誤地形成了侵犯 別的程序的主存地址，也因?yàn)檫@種鍵保護(hù)而仍然不 允許訪問。,補(bǔ)充知識(shí)：,c)環(huán)狀保護(hù) 環(huán)狀保護(hù)把系統(tǒng)程序和用戶程序按其重要性及對(duì) 整個(gè)系統(tǒng)能否正常工作的影響程度分層，如圖4.50 所示。設(shè)0、1、2三層是系統(tǒng)程序的

37、，之外的各層是 同一用戶程序的分層。環(huán)號(hào)大小表示保護(hù)的級(jí)別， 環(huán)號(hào)愈大，等級(jí)愈低。在現(xiàn)行程序運(yùn)行前，先由OS 定好程序各頁的環(huán)號(hào)，并置入也表。而后把該道程 序的開始環(huán)號(hào)送入處理機(jī)內(nèi)的現(xiàn)行環(huán)號(hào)寄存器，并 且把OS規(guī)定給該程序的上限環(huán)號(hào)(規(guī)定該程序所能 進(jìn)入的最內(nèi)層環(huán)號(hào))也置入相應(yīng)的寄存器。,補(bǔ)充知識(shí)：,若是Pi在某一時(shí)候?qū)儆趇層各頁的集合，則當(dāng)進(jìn)程 執(zhí)行PPi頁內(nèi)的程序時(shí)，允許訪問FPj頁，這里 對(duì)應(yīng)的是ji。但是如果是ji時(shí)，則需由OS環(huán)控制 例行程序判定這個(gè)內(nèi)向訪問是否允許和是否正確之 后才能訪問，否則就是出錯(cuò)，進(jìn)入保護(hù)處理。但j值 肯定不能小于給定的上限環(huán)號(hào)。只要ji，就進(jìn)入 中斷，若允許

38、訪問，則需經(jīng)特權(quán)指令把現(xiàn)行環(huán)號(hào)寄 存器的值由i改為j。,補(bǔ)充知識(shí)：,這種環(huán)式保護(hù)既能保證由于用戶程序的出錯(cuò)不至 于侵犯系統(tǒng)程序，也能保證由于同一用戶程序內(nèi)的 低級(jí)(環(huán)號(hào)大)的部分的出錯(cuò)而不致破壞其高級(jí)(環(huán)號(hào) 小)的部分。這種環(huán)式保護(hù)對(duì)系統(tǒng)程序的研究和調(diào)試 運(yùn)行特別有利，因?yàn)榭梢宰龅侥苄薷南到y(tǒng)程序的某 些部分而不必?fù)?dān)心會(huì)影響到系統(tǒng)程序已設(shè)計(jì)好并調(diào) 好的核心部分。 至于如何控制ji的跨層訪問，有的機(jī)器規(guī)定只 能由規(guī)定的轉(zhuǎn)移指令執(zhí)行，且對(duì)和ji和ji分別只能 用不同的轉(zhuǎn)移指令。,補(bǔ)充知識(shí)：,2.訪問方式的保護(hù) 上述種種區(qū)域保護(hù)，如判越界、判建相符、判環(huán) 號(hào)相符、判不超出段長等等，都是經(jīng)硬件實(shí)現(xiàn)的，

39、因此速度可以是很快的。這些區(qū)域保護(hù)是對(duì)允許訪 問的區(qū)域可以進(jìn)行任何形式的訪問，而對(duì)允許區(qū)域 之外，則任何形式的訪問都不允許。但在實(shí)際中， 只是這種限制往往適應(yīng)不了各種應(yīng)用的要求，因此 還得加上訪問方式的保護(hù)(限制)。,補(bǔ)充知識(shí)：,1)對(duì)主存信息的使用可以有讀R、寫W和執(zhí)行E三 種方式。相應(yīng)的就有R、W、E訪問方式保護(hù)，這3 者的邏輯組合可以反映出各種應(yīng)用要求，如： RWE不允許進(jìn)行任何訪問； RWE可以進(jìn)行任何訪問； RWE只能進(jìn)行讀訪問； RWE只能按數(shù)據(jù)進(jìn)行讀寫； RWE只能執(zhí)行，不能作為數(shù)據(jù)使用； REW只能進(jìn)行寫訪問； REW不準(zhǔn)寫訪問。,補(bǔ)充知識(shí)：,2)對(duì)前面講過的各種區(qū)域保護(hù)，都可

40、以加上相應(yīng)的 訪問方式位以實(shí)現(xiàn)這種訪問限制。 3)至于環(huán)式保護(hù)和也表保護(hù)，可以把R、W、E等 訪問方式位設(shè)在各個(gè)程序的段、頁表的各行內(nèi)，使 得同一環(huán)內(nèi)或同一段內(nèi)的各頁可以有上述種種不同 的訪問保護(hù)，以增強(qiáng)靈活性。 4)在某些應(yīng)用中，我么既要求能實(shí)現(xiàn)多個(gè)用戶可 讀、寫訪問共享的數(shù)據(jù)，但又要保證只當(dāng)一個(gè)用戶 訪問完該數(shù)據(jù)后，別的用戶才可以訪問，以防止在 一個(gè)用戶還未把某個(gè)共享文件寫好之前，別的用戶 卻能把它讀了去?？梢圆捎谩皽y試與置定”和“比較與 交換”指令實(shí)現(xiàn)這點(diǎn)。所以這也是一種保護(hù)方法。,補(bǔ)充知識(shí)：,第4章 小結(jié),4.1 存儲(chǔ)體系的形成與性能 1.存儲(chǔ)器的性能要求 1)大容量 2)低價(jià)格 3)

41、高速度 訪問時(shí)間TA 存儲(chǔ)周期TM 存儲(chǔ)器頻寬,4)結(jié)論 由于存儲(chǔ)器的價(jià)格、速度和容量的要求是相互矛 盾的，為了同時(shí)滿足三方面的要求，在一個(gè)完整的 存儲(chǔ)體系中，必須采用不同工藝的存儲(chǔ)器，使得信 息以各種方式分布于不同的存儲(chǔ)體。 2.并行主存系統(tǒng)頻寬的分析 1)類型 單體單字 單體多字 多體單字交叉 多體多字交叉,2)分析結(jié)論 由于程序的轉(zhuǎn)移概率不會(huì)很低，數(shù)據(jù)分布的離散 性較大，所以單純靠增大m來提高并行主存系統(tǒng)的頻 寬是有限的，而且性價(jià)比還會(huì)隨m的增大而下降。如 果采用并行主存系統(tǒng)仍不能滿足速度上的要求，就 必須從系統(tǒng)結(jié)構(gòu)上改進(jìn)，采用存儲(chǔ)體系。 3.存儲(chǔ)體系的形成與分支 1)容量需求 主存輔存

42、存儲(chǔ)層次 程序局部性,2)速度需求 Cache主存存儲(chǔ)層次 程序局部性 3)多級(jí)存儲(chǔ)層次 4.存儲(chǔ)體系的性能參數(shù) 1)存儲(chǔ)體系的每位平均價(jià)格c 2)命中率H=R1/(R1+R2) 3)等效訪問時(shí)間 TA=HTA1+(1-H)TA2,4.2虛擬存儲(chǔ)器 1.管理方式 1)段式管理 a)思想： 根據(jù)程序的模塊性，把一個(gè)復(fù)雜的大程序分解成 多個(gè)邏輯上相對(duì)獨(dú)立的模塊。 b)段表 為了進(jìn)行段式管理，每道程序都由一個(gè)段表(映像 表)，以存放該程序各程序段裝入主存的狀況信息。,段名(號(hào))：實(shí)際由于段號(hào)與行對(duì)應(yīng)，省略掉 裝入位：表征是(1)否(0)已調(diào)入主存 地址：調(diào)入主存時(shí)，在主存的起始(絕對(duì))地址 段長：段

43、的大小，限制偏移越界 訪問方式：只讀、可寫、只執(zhí)行，提供訪問保護(hù) c)段表基址寄存器 段表長度:該道程序的段數(shù)(段表行數(shù)) 段表基地址:程序的段表在主存中的起始地址,d)虛擬地址 基號(hào)(程序號(hào)):段表在段表基址寄存器的位置 段號(hào):段在段表中的位置 段內(nèi)位移:所訪問單元在段內(nèi)的偏移 e)實(shí)主存管理表 占用區(qū)域表 可用區(qū)域表 f)可用區(qū)域分配算法 首先分配算法 最佳分配算法,2)頁式管理 思想： 把主存空間和程序空間都機(jī)械的等分成固 定大小的頁(頁面大小因機(jī)器不同而異，一般在512 到幾kB)然后按頁順序編號(hào)。 3)段頁式管理 思想：把內(nèi)存機(jī)械的等分成固定大小的頁，把程 序按模塊分段，每個(gè)段分成與

44、主存頁面大小相同的 頁，每道程序通過一個(gè)段表和相應(yīng)于每段的一組頁 表來進(jìn)行定位。 問題：二次查表，費(fèi)時(shí)間,2.頁式虛擬存儲(chǔ)器的構(gòu)成 1)地址映像與變換 a)地址映像 就是將虛存單元按某種規(guī)則裝入(定位于)實(shí)存， 即建立多用戶虛地址NS與實(shí)存地址np的對(duì)應(yīng)關(guān)系。 b)地址變換 指的是程序按這種映像關(guān)系裝入實(shí)存后，在執(zhí)行 時(shí)多用戶虛地址NS如何變換成對(duì)應(yīng)的實(shí)地址np。 c)全相聯(lián)映像 讓每道程序的任何虛頁可以映像裝入到主存的任何 實(shí)頁位置,2)替換算法 a)目的 當(dāng)輔存中的頁面調(diào)入主存發(fā)生頁面爭用時(shí)，只有 強(qiáng)制騰出主存中某頁后才能接納從輔存調(diào)來的新頁 面。替換算法就是解決具體從主存中選擇哪一頁作

45、為被替換的頁。 b)原則 有高的主存命中率 算法便于實(shí)現(xiàn) 輔助軟、硬件成本盡量低,c)常用算法 隨機(jī)算法(Random,RAND) 先進(jìn)先出算法(First In First Out,FIFO) 近期最少使用算法(Least Recently Used,LRU) 優(yōu)化替換算法(OPT)衡量標(biāo)準(zhǔn) d)堆棧型替換算法 保證命中率隨主存頁數(shù)的增加只可能提高，至少 不會(huì)下降。 e)頁面失效頻率法(PFF) 根據(jù)各道程序運(yùn)行中的主存頁面失效率的高低,由 OS來動(dòng)態(tài)調(diào)節(jié)分配給每道程序的實(shí)頁數(shù)。,3)影響命命中率的因素 a)與替換算法有關(guān) b)命中率與頁地址流有關(guān) c)與主存容量(即分配給程序的主存頁數(shù))有

46、關(guān) 4)虛擬存儲(chǔ)器工作的全過程 P92圖4.13頁式虛擬存儲(chǔ)器工作原理,3.頁式虛擬存儲(chǔ)器實(shí)現(xiàn)中的問題 1)頁面失效處理 后援寄存器技術(shù) 預(yù)判技術(shù) 解決方法 替換算法 頁面大小不能過大 2)提高虛擬存儲(chǔ)器等效訪問速度的措施 快表慢表 散列快表硬件實(shí)現(xiàn)散列函數(shù),3)影響主存命中率和CPU效率的某些因素 a)與Sp有關(guān) P108圖4.28 頁面大小Sp 、容量S1與命中率H的關(guān) 系曲線圖 b)命中率與主存容量S1有關(guān) P109圖4.29命中率H與容量S1的關(guān)系圖 c)與所采用的頁面調(diào)度策略有關(guān),4.3高速緩沖存儲(chǔ)器(Cache) 1.基本結(jié)構(gòu) 特點(diǎn)：9個(gè)方面(與虛擬存儲(chǔ)器對(duì)比) 2.地址的映像與變

47、換 1)全相聯(lián)映像和變換 a)規(guī)則：主存中的任意一塊均可映像裝入到Cache 內(nèi)的任意一塊的位置。 b)地址變換過程 c)優(yōu)缺點(diǎn) 塊沖突率低；代價(jià)大，查表速度難以提高。,2)直接映像及其變換 規(guī)則：主存中每一塊只能映像到Cache中唯一一個(gè) 特定位置：主存的第i塊只能映像到第imod2ncb塊位 置上。相當(dāng)于把主存空間按Cache空間分區(qū)，每區(qū) 內(nèi)各塊只能按位置一一對(duì)應(yīng)到Cache相應(yīng)位置上。 3)組相聯(lián)映象及其變換 規(guī)則：把主存按Cache大小分區(qū)，整個(gè)Cache是一 區(qū)，每個(gè)區(qū)再分成相等的組，組內(nèi)分塊。組間直接 映象，組內(nèi)各塊全相聯(lián)映象。,4)段相聯(lián)映象 規(guī)則：把主存和Cache分成具有相

48、同的Z塊的若干 段，段與段之間采用全相聯(lián)映象，而段內(nèi)各塊之間 采用直接映象，實(shí)質(zhì)上就是組相聯(lián)映象的特例。 3.替換算法的實(shí)現(xiàn) 1)堆棧法 思想：棧頂恒存放近期最久訪問過的頁的頁號(hào)， 而棧底恒存放近期最久沒有訪問過的頁的頁號(hào)，即 準(zhǔn)備被替換掉的頁的頁號(hào)。按此思想組成一個(gè)硬件 堆棧。,2)比較對(duì)法 思路：讓各個(gè)塊成對(duì)組合，用一個(gè)觸發(fā)器的狀態(tài) 來表示該比較對(duì)內(nèi)兩塊訪問的遠(yuǎn)近次序，再經(jīng)門電 路就可以找到LRU塊。 4. Cache的透明性及性能分析 1)Cache的透明性分析 a)寫回法 在CPU執(zhí)行寫操作時(shí)，只是把信息寫入Cache， 僅當(dāng)需要被替換時(shí)，才將已經(jīng)被寫入過的Cache塊 先送回主存，然

49、后再調(diào)入新塊。,b)寫直達(dá)法 也稱為存直達(dá)法，它利用Cache主存存儲(chǔ)層 次在處理機(jī)和主存之間的直接通路，每當(dāng)處理機(jī)寫 入Cache的同時(shí)，也通過此通路直接寫入主存。 2) Cache的取算法 a)預(yù)取法 b)塊的大小 c)預(yù)取開銷 3)任務(wù)切換對(duì)失效率的影響 a)與任務(wù)的切換頻度(平均時(shí)間間隔Qsw)有關(guān) b)與Cache的容量有關(guān),4)影響Cache存儲(chǔ)器性能的因素 a)不命中率與Cache的容量、組的大小和塊的大小 的一般關(guān)系 看P121圖4.42塊的大小、組的大小與Cache容量對(duì) Cache命中率的影響。 b)Cache主存存儲(chǔ)層次的等效速度與命中率的 關(guān)系 5.Cache主存輔存存儲(chǔ)層次 1)對(duì)應(yīng)于虛地址的單元已在Cache中 2)對(duì)應(yīng)單元已在主存但尚未調(diào)入Cache 3)對(duì)應(yīng)單元還不在主存,4.4主存保護(hù) 1.存儲(chǔ)區(qū)域的保護(hù) 1)頁表保護(hù) 2)鍵方式 3)環(huán)式保護(hù) 2.訪問方式的保護(hù),第4章 習(xí)題,1.某虛擬存儲(chǔ)器共8個(gè)