并行存儲器-奧鵬教育

奧鵬遠(yuǎn)程教育中心心系天下求學(xué)人PagePAGE1ofNUMPAGES179專業(yè)專注周到細(xì)致高校名稱：福建師范大學(xué)課程名稱：《計算機體系結(jié)構(gòu)》心系天下求學(xué)人PagePAGE176ofNUMPAGES179專業(yè)專注周到細(xì)致目錄TOC\o"1-1"\h\z\u第一章概論課堂筆記 3第一章概論關(guān)鍵詞匯 12第一章概論FAQ 13第一章緒論拓展資源 14第二章存儲系統(tǒng)課堂筆記 15第二章存儲系統(tǒng)關(guān)鍵詞匯 34第二章存儲系統(tǒng)FAQ 35第二章存儲系統(tǒng)拓展資源 36第三章輸入輸出系統(tǒng)課堂筆記 38第三章輸入輸出系統(tǒng)關(guān)鍵詞匯 54第三章輸入輸出系統(tǒng)FAQ 55第三章輸入輸出系統(tǒng)拓展資源 57第四章數(shù)據(jù)表示和指令系統(tǒng)課堂筆記 64第四章數(shù)據(jù)表示和指令系統(tǒng)關(guān)鍵詞匯 87第四章數(shù)據(jù)表示和指令系統(tǒng)FAQ 88第四章數(shù)據(jù)表示和指令系統(tǒng)拓展資源 89第五章流水線處理技術(shù)課堂筆記 91第五章流水線處理技術(shù)關(guān)鍵詞匯 118第五章流水線處理技術(shù)FAQ 119第五章流水線處理技術(shù)拓展資源 120第六章并行處理技術(shù)和多處理機課堂筆記 121第六章并行處理技術(shù)和多處理機關(guān)鍵詞匯 141第六章并行處理技術(shù)和多處理機FAQ 141第六章并行處理技術(shù)和多處理機拓展資源 142第七章互聯(lián)網(wǎng)絡(luò)課堂筆記 144第七章互聯(lián)網(wǎng)絡(luò)關(guān)鍵詞匯 161第七章互聯(lián)網(wǎng)絡(luò)FAQ 162第七章互聯(lián)網(wǎng)絡(luò)拓展資源 163第八章非馮·諾依曼計算機結(jié)構(gòu)課堂筆記 164第八章非馮·諾依曼計算機結(jié)構(gòu)關(guān)鍵詞匯 176第八章非馮·諾依曼計算機結(jié)構(gòu)FAQ 176第八章非馮·諾依曼計算機結(jié)構(gòu)拓展資源 177第一章概論課堂筆記主要知識點掌握程度本章主要內(nèi)容包括：介紹了現(xiàn)代計算機系統(tǒng)的構(gòu)成和層次結(jié)構(gòu)；了解計算機系統(tǒng)結(jié)構(gòu)的定義及結(jié)構(gòu)劃分，重點掌握計算機系統(tǒng)設(shè)計的原則、任務(wù)、方法和性能評價指標(biāo)。知識點整理一、現(xiàn)代計算機系統(tǒng)自1946年第一臺電子數(shù)字計算機問世以來，已經(jīng)過了半個世紀(jì)，計算機經(jīng)歷了五次更新?lián)Q代，各代劃分的主要標(biāo)志是硬件和軟件技術(shù)的明顯變革。從所用的器件而言，它經(jīng)歷了由電子管、晶體管到集成電路，由繼電器存儲，磁介質(zhì)存儲到集成電路，乃至大規(guī)模和超大規(guī)模集成電路存儲的發(fā)展過程。從結(jié)構(gòu)的發(fā)展而言，它經(jīng)歷了由單個CPU組成的單機系統(tǒng)到流水線機、多處理機到大規(guī)模的并行處理機的發(fā)展過程，從技術(shù)的發(fā)展上而言，它不斷引入變址技術(shù)、中斷技術(shù)、微程序技術(shù)、緩沖技術(shù)共享、重用技術(shù)、虛擬技術(shù)。從語言和應(yīng)用方面而言，它經(jīng)歷了由匯編到高級語言，從單用戶到多用戶，到并行處理的語言、編譯、操作系統(tǒng)，直到如今計算機網(wǎng)絡(luò)、異構(gòu)系統(tǒng)處理等等這一發(fā)展過程。隨著硬、軟件的發(fā)展。展示在人們面前的計算機也已大大不同于50年前的樣子，而且仍然在不停地迅速發(fā)展和變化著。（一）現(xiàn)在計算機的構(gòu)成計算機系統(tǒng)不只是最明顯的硬件設(shè)備，還應(yīng)包括與它不可分割的系統(tǒng)軟件、應(yīng)用軟件、用戶接口等，它們形成一個集成系統(tǒng)，如圖1.1.1所示。（二）計算機系統(tǒng)層次結(jié)構(gòu)計算機系統(tǒng)由硬件／器件和軟件組成，按功能可以劃分成以下7級層次結(jié)構(gòu)：級別計算機系統(tǒng)人實現(xiàn)方式6應(yīng)用語言級用戶軟件5高級語言級高級語言程序員軟件4匯編語言級匯編程序師軟件3操作系統(tǒng)級操作員軟件2傳統(tǒng)機器語言級機器語言程序員軟硬件接口1微程序機器級邏輯設(shè)計員固件0電子線路級硬件設(shè)計員硬件其中，第0級由硬件實現(xiàn)，第1級由微程序（固件）實現(xiàn)，第2級至第6級由軟件實現(xiàn)?？梢?，計算機系統(tǒng)結(jié)構(gòu)是指在計算機系統(tǒng)軟、硬件的分接口上，機器所表現(xiàn)出的外特性。二、計算機系統(tǒng)結(jié)構(gòu)（一）計算機系統(tǒng)結(jié)構(gòu)定義概念：計算機系統(tǒng)結(jié)構(gòu)就是計算機的機器語言程序員或編譯程序編寫者所看到的外特性，是硬件子系統(tǒng)的概念結(jié)構(gòu)及其功能特性。系統(tǒng)結(jié)構(gòu)一般應(yīng)包括以下幾個方面：機器內(nèi)的數(shù)據(jù)表示、尋址方式、寄存器定義、指令系統(tǒng)、中斷機構(gòu)、存儲體系和管理、機器工作狀態(tài)的定義和切換、輸入輸出結(jié)構(gòu)、信息保護(hù)等。在計算機技術(shù)中，一種本來存在的事物或?qū)傩裕珡哪撤N角度看似乎不存在，這稱為透明性。（二）計算機系統(tǒng)結(jié)構(gòu)、組成與實現(xiàn)計算機系統(tǒng)結(jié)構(gòu)是機器語言程序員所了解的計算機的屬性，即外特性。系統(tǒng)結(jié)構(gòu)設(shè)計者的主要任務(wù)是研究軟件、硬件功能分配和對軟件、硬件界面的確定，即哪些功能由軟件完成，哪些功能由硬件完成。包括：數(shù)據(jù)表示、尋址方式、寄存器定義、指令系統(tǒng)、中斷機構(gòu)、存儲體系和管理、機器工作狀態(tài)的定義和切換、輸入輸出結(jié)構(gòu)、信息保護(hù)等。計算機組成是計算機系統(tǒng)結(jié)構(gòu)的邏輯實現(xiàn)，計算機組成的任務(wù)是在計算機系統(tǒng)結(jié)構(gòu)確定分配給硬件子系統(tǒng)的功能及其概念結(jié)構(gòu)之后，研究各組成部分的內(nèi)部構(gòu)造和相互聯(lián)系，以實現(xiàn)機器指令級的各種功能和特性。具體包括：數(shù)據(jù)通路的寬度、專用部件的設(shè)置、各功能部件操作部件的并行度和共享程度、控制機構(gòu)的組成方式、緩沖技術(shù)排隊技術(shù)的采用、可靠性技術(shù)的采用和方式的選擇、預(yù)估預(yù)判優(yōu)化處理。計算機實現(xiàn)即計算機邏輯設(shè)計之后的物理實現(xiàn)，包括：處理機，主存部件的物理結(jié)構(gòu)，器件的集成度，速度的選擇，模塊、插件、底板的劃分與連接，電源、冷卻，以及整機的裝配技術(shù)等。（三）計算機系統(tǒng)結(jié)構(gòu)的分類計算機系統(tǒng)的分類常見分類方法：1、按大小劃分種類：巨型機、大型機、中型機、小型機、微型機等。2、按用途劃分種類：科學(xué)計算、事務(wù)處理、實時控制、工作站、服務(wù)器、家用計算機等。3、按數(shù)據(jù)類型劃分種類：定點機、浮點機、向量機、堆棧機等。4、按處理機個數(shù)和種類劃分種類：單處理機、并行處理機、多處理機、分布處理機、關(guān)聯(lián)處理機、超標(biāo)量處理機、超流水線處理機、SMP（對稱多處理機）、MPP（大規(guī)模并行處理機）、機群（Cluster）系統(tǒng)等。5、按所使用的器件劃分種類：第一代：電子管計算機(Valve)第二代：晶體管計算機(Transistor)第三代：集成電路計算機(LSI)第四代：大規(guī)模集成電路計算機(VLSI)第五代：智能計算機等6、佛林（Flynn）分類法1966年由Michael.J.Flynn提出，按照指令流和數(shù)據(jù)流的多倍性特征對計算機系統(tǒng)進(jìn)行分類。指令流（instructionstream）：機器執(zhí)行的指令序列；數(shù)據(jù)流（datastream）：由指令流調(diào)用的數(shù)據(jù)序列，包括輸入數(shù)據(jù)和中間結(jié)果；多倍性（multiplicity）：在系統(tǒng)性能瓶頸部件上同時處于同一執(zhí)行階段的指令或數(shù)據(jù)的最大可能個數(shù)。種類：(1)單指令流單數(shù)據(jù)流SISD(SingleInstructionSingleDatastream)(2)單指令流多數(shù)據(jù)流SIMD(SingleInstructionMultipleDatastream)(3)多指令流單數(shù)據(jù)流MISD(MultipleInstructionSingleDatastream)(4)多指令流多數(shù)據(jù)流MIMS(MultipleInstructionMultipleDatastream)CU：控制部件PU：處理部件MM：內(nèi)存模塊IS：指令流DS：數(shù)據(jù)流圖1.2.1Flynn分類法各類機器結(jié)構(gòu)7、馮澤云分類法1972年美籍華人馮澤云提出用最大并行度來對計算機系統(tǒng)進(jìn)行分類。最大并行度：指在單位時間內(nèi)能夠處理的最大二進(jìn)制位數(shù)。字寬：在一個字中同時處理的二進(jìn)制的位數(shù)。位寬：在一個位片中能同時處理的字?jǐn)?shù)。例如：同時處理的字寬為n，位寬為m，則最大并行度定義為：圖1.2.2按最大并行度的馮氏分類法由圖1.2.2可得出4類不同處理方法的計算機系統(tǒng)結(jié)構(gòu)：種類：(1)字符串位串WSBS(WordSerialandBitSerial)串行計算機；m＝1，n＝1；例如：EDVAC(1，1)(2)字并位串WPBS(WordParallelandBitSerial)傳統(tǒng)的單處理機；m＝1，n＞1；例如：Pentium(32，1)(3)字符串位并WSBP(WordSerialandBitParallel)并行計算機、MPP、相聯(lián)計算機；m＞1，n＝1；例如：MPP(1，16384)，STARAN(1，256)，DAP(4)字并位并WPBP(WordParallelandBitParallel)全并行計算機；m＞1，n＞1；例如：IILIACIV(64，64)，ASC(64，32)，PEPE，Cmmp8、漢德勒分類法由WolfganHandler于1977年根據(jù)并行度和流水線提出的一種分類方法。又稱為ESC(ErlangeClassificationScheme)分類法。根據(jù)并行度和流水線分類，計算機硬件結(jié)構(gòu)分成三個層次，并分別考慮它們的可并行性和流水處理程度。這三個層次是：(1)程序級k：程控部件(PCU)的個數(shù)；(2)操作級d：算術(shù)邏輯部件(ALU)或處理部件(PU)的個數(shù)；(3)邏輯級w：每個算術(shù)邏輯部件包含的邏輯線路(ELC)的套數(shù)。據(jù)此可以把計算機系統(tǒng)的結(jié)構(gòu)用公式t(系統(tǒng)型號)＝(k，d，w)表示。例如：t(EDVAC)＝(1，1，1) t(Pentium)＝(1，1，32)t(STARAN)＝(1，8192，1)t(ILLIACⅣ)＝(1，64，64)t(Cmmp)＝(16，1，16)為了表示流水線，采用：t(系統(tǒng)型號)＝(k×k'，d×d'，w×w')其中：k'表示宏流水線中程控部件的個數(shù)d'表示指令流水線中算術(shù)邏輯部件的個數(shù)w'表示操作流水線中基本邏輯線路的套數(shù)例如：Cray1有1個CPU，12個相當(dāng)于ALU或PE的處理部件，最多８級流水線，字長為64位，可以實現(xiàn)1～14位流水線。表示為：t(Cray1)＝(1，12×8，64(1～14)）又例如：t(PEPE)＝(1×3，288，32）t(TIASC)＝(1，4，64×8)三、計算機系統(tǒng)設(shè)計計算機系統(tǒng)結(jié)構(gòu)的設(shè)計是整個計算機系統(tǒng)設(shè)計當(dāng)中極為重要的內(nèi)容，因此也必須遵守計算機系統(tǒng)設(shè)計的原則方法和步驟。下面介紹目前在計算機系統(tǒng)設(shè)計中應(yīng)該遵守的定量原理。（一）計算機系統(tǒng)的設(shè)計原則1、加快經(jīng)常性事件的速度(Makethecommoncasefast)這是最重要也是被廣泛采用的設(shè)計準(zhǔn)則。道理十分明顯，使經(jīng)常性事件的處理速度加快能明顯提高整個系統(tǒng)的性能。2、Amdahl定律IBM公司的設(shè)計師Amdahl在1967年提出的Amdahl定律告訴我們：系統(tǒng)中某一部件由于采用某種更快的執(zhí)行方式后整個系統(tǒng)性能的提高與這種執(zhí)行方式的使用頻率或占總執(zhí)行時間的比例有關(guān)。性能提高的衡量指標(biāo)為加速比，其定義為：在Amdahl定律中，加速比與兩個因素有關(guān)：一是被改進(jìn)部分的使用頻率的大小即可改進(jìn)部分所占時間的百分比：二是被改進(jìn)部分本身在改進(jìn)后所取得的效果，即改進(jìn)部分的加速比，也可以用時間參量來表示：改進(jìn)之后整個任務(wù)的執(zhí)行時間為（改進(jìn)前時間－（改進(jìn)前可改時間－改進(jìn)后可改時間））：其中T0為改進(jìn)前的整個任務(wù)的執(zhí)行時間。改進(jìn)后整個系統(tǒng)的加速比達(dá)到：其中(1-Fe)表示不可改進(jìn)部分，顯然當(dāng)Fe為0，即沒有改進(jìn)部分時，Sn為1，所以性能的提高受改進(jìn)部分所占比例的限制。當(dāng)Se→∞時，則Sn=1/(1-Fe)，因此，可獲取性能改善極限值受Fe值的約束。3、訪問局部性原理程序訪問局部性原理說明了計算機在程序執(zhí)行過程中呈現(xiàn)出的一種規(guī)律，即程序往往重復(fù)使用它剛剛使用過的數(shù)據(jù)和指令。局部性分為時間上的局部性和空間上的局部性兩種。所謂時間局部性是指近期被訪問的代碼，很可能不久又將再次被訪問；空間局部性是指地址上相鄰近的代碼可能會被連續(xù)地訪問。目前存儲系統(tǒng)層次結(jié)構(gòu)的設(shè)計就是以此為理論基礎(chǔ)。（二）計算機系統(tǒng)設(shè)計的主要任務(wù)1、確定用戶對計算機系統(tǒng)的功能、價格和性能要求功能要求包括：應(yīng)用領(lǐng)域、軟件兼容性、操作系統(tǒng)的要求、各種通用國際標(biāo)準(zhǔn)的要求。價格要求：考慮用戶或市場對計算機功能和性能要求的前提下，盡量降低成本。性能要求包括：速度、容量、輸入／輸出的種類、可靠性、可維護(hù)性、安全性、容錯能力、人機交互的能力等等。2、軟硬件的平衡硬件實現(xiàn)：速度快、成本高；靈活性差、占用內(nèi)存少。軟件實現(xiàn)：速度低、復(fù)制費用低；靈活性好、占用內(nèi)存多。設(shè)計必須考慮硬件和軟件的合理分配，同時還應(yīng)考慮設(shè)計的復(fù)雜性及軟硬件實現(xiàn)的難易程度。3、設(shè)計出符合今后發(fā)展方向的系統(tǒng)結(jié)構(gòu)一個成功的系統(tǒng)結(jié)構(gòu)應(yīng)該能經(jīng)得住軟、硬件技術(shù)的發(fā)展以及應(yīng)用的變化。因此設(shè)計者必須特別注意計算機應(yīng)用和計算機技術(shù)的發(fā)展趨勢，這樣才能延長一種機器的使用壽命。發(fā)展趨勢：硬件實現(xiàn)的比例越來越高，軟件所占的成本越來越高。（三）計算機系統(tǒng)設(shè)計的主要方法基于計算機系統(tǒng)層次結(jié)構(gòu)的基礎(chǔ)上，其設(shè)計方法可以有以下的三種：1、由上向下（Top-Down）設(shè)計過程：面向應(yīng)用的數(shù)學(xué)模型→面向應(yīng)用的高級語言→面向這種應(yīng)用的操作系統(tǒng)→面向操作系統(tǒng)和高級語言的機器語言→面向機器語言的微指令系統(tǒng)和硬件實現(xiàn)。應(yīng)用場合：專用計算機的設(shè)計（早期計算機的設(shè)計）。特點：對于所面向的應(yīng)用領(lǐng)域，性能（性能價格比）很高。隨著通用計算機價格降低，目前已經(jīng)很少采用。2、由下向上（Bottom-Up）（通用計算機系統(tǒng)的一種設(shè)計方法）設(shè)計過程：根據(jù)當(dāng)時的器件水平，設(shè)計微程序機器級和傳統(tǒng)機器級。根據(jù)不同的應(yīng)用領(lǐng)域設(shè)計多種操作系統(tǒng)、匯編語言、高級語言編譯器等。最后設(shè)計面向應(yīng)用的虛擬機器級。應(yīng)用場合：在計算機早期設(shè)計中（60～70年代）廣為采用。特點：容易使軟件和硬件脫節(jié)，整個計算機系統(tǒng)的效率降低。3、中間開始（Middle-Out）設(shè)計過程：首先定義軟硬件的分界面。然后各個層次分別進(jìn)行設(shè)計。應(yīng)用場合：用于系列機的設(shè)計。特點：軟硬件的分界面在上升，硬件比例在增加。硬件價格下降，軟件價格上升。軟硬件人員結(jié)合共同設(shè)計。四、計算機的性能評價（一）CPU性能CPU的性能是指CPU執(zhí)行程序所用時間，也就是CPU連續(xù)地執(zhí)行一條條指令的時間，不包括I/O等待時間。CPU的性能取決于三個要素：①時鐘頻率；②每條指令所花的時鐘周期數(shù)CPI；③指令條數(shù)IC。則：其中Ii表示i指令在程序中執(zhí)行的次數(shù)，CPIi表示i指令所需的平均時鐘周期數(shù)，n為指令種類數(shù)。（二）MIPS和MFLOPS1、MIPS（millioninstructionspersecond）它表示每秒百萬條指令數(shù)，對于一個給定的程序，MIPS定義為：程序的執(zhí)行時間為：其中：Te為程序執(zhí)行時間，CPI為每條指令的平均時鐘周期，時鐘頻率為每秒周期數(shù)即每周期的時間的倒數(shù)。顯然，機器愈快其MIPS愈高，但MIPS對指令系統(tǒng)和程序的依賴性很大，故在某些情況下不能準(zhǔn)確反映系統(tǒng)的性能。2、MFLOPS（millionfloatingpointoperationspersecond）表示每秒百萬次浮點操作次數(shù)，MFLOPS定義為：顯然，MFLOPS可以用來衡量機器浮點操作的性能，因為同一程序在不同機器上執(zhí)行的指令可能不同，但執(zhí)行的浮點運算卻是完全相同的。但是，MFLOPS不能體現(xiàn)機器的整體性能；MFLOPS取決于機器和程序兩個方面，因為不同機器浮點運算集不同，因此不同的浮點操作類型運算時間不同。（三）系統(tǒng)性能測試為了能進(jìn)行合理的評價，通常采用不同類型的程序進(jìn)行測試，經(jīng)過實踐選擇出的這些程序稱為基準(zhǔn)測試程序。1、基準(zhǔn)測試程序（1）實際應(yīng)用程序：例如C語言的編譯程序，Tex正文處理程序，SpiceCAD工具軟件等。（2）核心程序：從實際程序中抽取小量關(guān)鍵的循環(huán)程序段，例如Livermore24Loop（24個循環(huán)段）、Linpack（解線性方程組）。（3）綜合測試程序：它類似于核心程序，但考慮到各種不同的操作和不同種類的程序。如Whetstone和Dhrystone等。2、性能評價結(jié)果處理根據(jù)哪個數(shù)據(jù)來確定機器的性能呢？一般有以下三個：假設(shè)有n個測試程序，Ri為第i個測試程序的速率；Ti為第i個測試程序所需的時間，則：速率算術(shù)平均值A(chǔ)m：速率幾何平均值Gm：通常用于各機器之間的比較，可以以某一機器為標(biāo)準(zhǔn)，對其他機器進(jìn)行規(guī)格化，再求其幾何平均值的比。速率加權(quán)平均值A(chǔ)m：其中，ωi是第i個程序在任務(wù)中所占的比重。五、計算機系統(tǒng)結(jié)構(gòu)的發(fā)展（一）馮·諾依曼機型及其演變1946年普林斯頓高級研究所數(shù)學(xué)家馮·諾依曼(VanNenmann)提出了一個完整的現(xiàn)代計算機雛形，它由運算器、控制器、存儲器、輸入輸出四部分組成，主要特點是程序存儲，指令驅(qū)動，集中控制，見圖1.5.1所示。一般認(rèn)為其主要特征有以下幾點：(1)機器以運算器為中心。除了完成運算以外，機器內(nèi)部的數(shù)據(jù)傳輸都經(jīng)過運算器。各部件的操作以及它們之間的協(xié)調(diào)由控制器集中控制。(2)存儲器按一維線性編址，順序訪問存儲器地址單元，每個存儲單元的位數(shù)固定。(3)程序存儲，指令和數(shù)據(jù)無區(qū)別存放在存儲器中，指令和數(shù)據(jù)一樣可以送到運算器中進(jìn)行運算，指令與數(shù)據(jù)的區(qū)別主要在于地址區(qū)域不同。(4)指令在存儲器中按其執(zhí)行順序存放，由一個順序控制器（亦稱程序計數(shù)器或指令計數(shù)器）指定即將被執(zhí)行的指令地址。每讀取一條指令后，計數(shù)器自動按順序遞增。(5)指令由操作碼和地址碼組成，操作碼指明操作類型，地址碼指明操作數(shù)的地址和結(jié)果地址。(6)數(shù)據(jù)以二進(jìn)制表示。經(jīng)歷幾十年的不斷改進(jìn)與發(fā)展，現(xiàn)代的計算機雖然仍然以馮·諾依曼的結(jié)構(gòu)為基礎(chǔ)，但已有了許多重大改進(jìn)，主要改進(jìn)是：存儲器為中心，總線結(jié)構(gòu)，分散控制。具體表現(xiàn)在下列幾個方面。(1)計算機處理的數(shù)據(jù)類型不斷增加新的表示形式，除了通常的定點數(shù)、浮點數(shù)、十進(jìn)制數(shù)、邏輯數(shù)字符等基本數(shù)據(jù)類型外，還有向量、堆棧、自定義數(shù)據(jù)、漢字等。(2)指令種類與尋址方式增加，增加了支持操作系統(tǒng)與語言編譯的指令，增加了多種尋址方式如變址尋址、間接尋址、相對尋址、基址尋址以及為了存儲管理而采用的頁面尋址等方式。(3)改變了以CPU為中心的數(shù)據(jù)傳送方式，以存儲器為中心，存儲系統(tǒng)中采用了虛擬存儲，高速緩存，為了提高速度出現(xiàn)了多存儲體的并行存取或交叉存儲的結(jié)構(gòu)，改變了一維線性編址的方式。采用了指令與數(shù)據(jù)分體的存儲方式，以有利于并行操作。(4)處理器采用了多種新技術(shù)，如堆棧的采用、支持過程調(diào)用及遞歸、表達(dá)式的計算，采用指令流水、操作流水的技術(shù)與多功能部件，多處理器的并行技術(shù)，提高了CPU的功能，改進(jìn)并行性能。（二）系統(tǒng)結(jié)構(gòu)并行技術(shù)的發(fā)展計算機系統(tǒng)結(jié)構(gòu)發(fā)展的重要方向就是并行處理。并行處理技術(shù)的發(fā)展經(jīng)過以下幾個階段：1、串行階段傳統(tǒng)的程序存儲計算機。2、先行處理最初的并行，通過預(yù)取指令使取指令與指令執(zhí)行操作重疊。3、功能并行(1)采用并行多功能部件；(2)中斷技術(shù)，使輸入輸出與CPU操作并行；(3)多體存儲器交叉并行訪問技術(shù)，使存儲器與存儲器及CPU并行；(4)整數(shù)運算，浮點運算以及指令執(zhí)行的取指、譯碼、讀操作數(shù)由各自獨立的功能部件完成。4、流水線技術(shù)(1)一個任務(wù)分成多個子任務(wù)同時執(zhí)行；(2)用軟件控制循環(huán)執(zhí)行，稱為標(biāo)量流水線處理機。5、向量處理機(1)以硬件或固件的結(jié)構(gòu)執(zhí)行，稱為顯式向量處理機；(2)實現(xiàn)存儲器到存儲器和寄存器到寄存器之間的并行處理。6、SIMD、MIMD如陣列機、聯(lián)想機、多處理機與多計算機。（三）影響計算機系統(tǒng)結(jié)構(gòu)的因素1、軟件對系統(tǒng)結(jié)構(gòu)的影響由于軟件相對于硬件的成本越來越貴，并且已積累了大量成熟的系統(tǒng)軟件和應(yīng)用軟件，用戶希望能在性能更好的機器上運行原來開發(fā)的軟件，以便保護(hù)軟件開發(fā)投資，為此采用以下幾種措施。(1)系列機與兼容機：所謂系列機是指同一廠家生產(chǎn)的具有相同系統(tǒng)結(jié)構(gòu)，但采取了不同的組成和實現(xiàn)技術(shù)的一系列計算機系統(tǒng)。如IBM系列機具有以下結(jié)構(gòu)特點：相同的指令系統(tǒng)，采用順序執(zhí)行、重迭、流水和并行處理方式。相同的32位字長，數(shù)據(jù)通路寬度為8位、16位、32位、64位。采用系列機方法的主要優(yōu)點：系列機之間軟件兼容，可移植性好；插件、接口等相互兼容；便于實現(xiàn)機間通信；便于維修、培訓(xùn)；有利于提高產(chǎn)量、降低成本。采用系列機方法的主要缺點：限制了計算機系統(tǒng)結(jié)構(gòu)的發(fā)展。如PC系列機，其系統(tǒng)結(jié)構(gòu)最落后，使用也最普及(2)模擬和仿真：用軟件的方法在一臺現(xiàn)有的計算機系統(tǒng)上實現(xiàn)另一臺計算機的指令系統(tǒng)叫模擬。被模擬的機器是不存在的，稱為虛擬機，執(zhí)行模擬程序的機器稱為宿主機。用微程序（即用硬件、固件或軟件、硬件、固件混合）的方法在一臺現(xiàn)有的計算機系統(tǒng)上實現(xiàn)另一臺計算機的指令系統(tǒng)叫仿真。執(zhí)行微程序的機器稱為宿主機，被實現(xiàn)的稱為目標(biāo)機。模擬是用宿主機的指令編寫出一段程序來解釋虛擬機上的一條指令；仿真是直接用宿主機的一段微程序解釋執(zhí)行目標(biāo)機的每條指令。從而實現(xiàn)軟件的移植。(3)統(tǒng)一標(biāo)準(zhǔn)高級語言：采用同一種不依賴于任何具體機器的高級語言編寫系統(tǒng)軟件和應(yīng)用軟件。但至今還沒有這樣一種高級語言。2、應(yīng)用需求對系統(tǒng)結(jié)構(gòu)的影響應(yīng)用的需求一直是計算機發(fā)展的動力。3、器件對系統(tǒng)結(jié)構(gòu)的影響在相當(dāng)長的一段時間內(nèi)，器件的改進(jìn)是提高計算機速度的主要途徑，器件發(fā)展對提高處理機主頻（Fz）起決定性作用。器件發(fā)展的特點：集成度迅速提高、速度已接近極限、價格直線下降、可靠性越來越高。第一章概論關(guān)鍵詞匯1、計算機系統(tǒng)結(jié)構(gòu)計算機系統(tǒng)結(jié)構(gòu)就是計算機的機器語言程序員或編譯程序編寫者所看到的外特性，是硬件子系統(tǒng)的概念結(jié)構(gòu)及其功能特性。系統(tǒng)結(jié)構(gòu)一般應(yīng)包括以下幾個方面：機器內(nèi)的數(shù)據(jù)表示、尋址方式、寄存器定義、指令系統(tǒng)、中斷機構(gòu)、存儲體系和管理、機器工作狀態(tài)的定義和切換、輸入輸出結(jié)構(gòu)、信息保護(hù)等。2、指令流機器執(zhí)行的指令序列。3、數(shù)據(jù)流由指令流調(diào)用的數(shù)據(jù)序列，包括輸入數(shù)據(jù)和中間結(jié)果。4、多倍性在系統(tǒng)性能瓶頸部件上同時處于同一執(zhí)行階段的指令或數(shù)據(jù)的最大可能個數(shù)。5、Amdahl定律IBM公司的設(shè)計師Amdahl在1967年提出的Amdahl定律告訴我們：系統(tǒng)中某一部件由于采用某種更快的執(zhí)行方式后整個系統(tǒng)性能的提高與這種執(zhí)行方式的使用頻率或占總執(zhí)行時間的比例有關(guān)。性能提高的衡量指標(biāo)為加速比，其定義為：6、字寬在一個字中同時處理的二進(jìn)制的位數(shù)。7、位寬在一個位片中能同時處理的字?jǐn)?shù)。8、MIPS它表示每秒百萬條指令數(shù)，對于一個給定的程序，MIPS定義為：9、MFLOPS表示每秒百萬次浮點操作次數(shù)，MFLOPS定義為：10、CPU的性能是指CPU執(zhí)行程序所用時間，也就是CPU連續(xù)地執(zhí)行一條條指令的時間。11、程序訪問局部性原理程序訪問局部性原理說明了計算機在程序執(zhí)行過程中呈現(xiàn)出的一種規(guī)律，即程序往往重復(fù)使用它剛剛使用過的數(shù)據(jù)和指令。局部性分為時間上的局部性和空間上的局部性兩種。所謂時間局部性是指近期被訪問的代碼，很可能不久又將再次被訪問；空間局部性是指地址上相鄰近的代碼可能會被連續(xù)地訪問。12、最大并行度指在單位時間內(nèi)能夠處理的最大二進(jìn)制位數(shù)。13、透明性在計算機技術(shù)中，一種本來存在的事物或?qū)傩裕珡哪撤N角度看似乎不存在，這稱為透明性。14、系列機所謂系列機是指同一廠家生產(chǎn)的具有相同系統(tǒng)結(jié)構(gòu)，但采取了不同的組成和實現(xiàn)技術(shù)的一系列計算機系統(tǒng)。15、模擬用軟件的方法在一臺現(xiàn)有的計算機系統(tǒng)上實現(xiàn)另一臺計算機的指令系統(tǒng)叫模擬，是用宿主機的指令編寫出一段程序來解釋虛擬機上的一條指令；16、仿真用微程序（即用硬件、固件或軟件、硬件、固件混合）的方法在一臺現(xiàn)有的計算機系統(tǒng)上實現(xiàn)另一臺計算機的指令系統(tǒng)叫仿真，是直接用宿主機的一段微程序解釋執(zhí)行目標(biāo)機的每條指令。第一章概論FAQ一、實現(xiàn)程序移植的主要途徑有什么?答：統(tǒng)一高級語言、系列機、模擬、和仿真。二、提高計算機系統(tǒng)并行性的主要技術(shù)途徑有什么？答：提高計算機系統(tǒng)并行性的主要技術(shù)途徑有時間重疊、資源重復(fù)和資源共享。三、計算機系統(tǒng)的Flynn（弗林）分類法是按什么來分類的？共分哪幾類？解釋其含義。弗林分類法是按指令流、數(shù)據(jù)流以及多倍性分類的。共分四類。SISD——指令部件只對一條指令處理，只控制一個操作部件操作。如一般的串行單處理機。SIMD——由單一指令部件同時控制多個重復(fù)設(shè)置的處理單元，執(zhí)行同一指令下不同數(shù)據(jù)的操作。如陣列處理機。MISD——多個指令部件對同一數(shù)據(jù)的各個處理階段進(jìn)行操作。這種機器很少見。MIMD——多個獨立或相對獨立的處理機分別執(zhí)行各自的程序、作業(yè)或進(jìn)程。例如多處理機。四、假設(shè)高速緩存Cache工作速度為主存的5倍，且Cache被訪問命中的概率為90％，則采用Cache后，能使整個存儲系統(tǒng)獲得多高的加速比？能使整個存儲系統(tǒng)獲得3.57的加速比。第一章緒論拓展資源—計算機系統(tǒng)結(jié)構(gòu)的發(fā)展現(xiàn)狀和方向一、從CISC到RISC70年代以前的CBC結(jié)構(gòu)下的計算機，將許多復(fù)雜指令通過硬件來實現(xiàn)，很大程度簡化了目標(biāo)程序，CISC指令長度不一，可以接節(jié)省存儲空間，而且，CISC指令可以直接對存儲器操作。從80年代，隨著VLSI技術(shù)的發(fā)展，電路集成度大大提高，而由于CISC中指令系統(tǒng)龐大尋址方式，指令格式較多且長度不一，許多復(fù)雜指令的控制邏輯及其不規(guī)整，用VLSI工藝實現(xiàn)存在很大困難，增加了硬件復(fù)雜度和設(shè)計成本，同時大量DRAM做主存儲器，主存與控存速度相當(dāng)，復(fù)雜指令用微程序?qū)崿F(xiàn)和簡單指令的子程序?qū)崿F(xiàn)效率相當(dāng)，而且，大量的數(shù)字統(tǒng)計表明20%指令占據(jù)了80%的處理機時間，許多指令使用頻度低。針對以上這些問題，1980年，PATTERSON和DITZEL提出了精簡指令系統(tǒng)計算機的設(shè)想，通過精簡，指令系統(tǒng)使計算機結(jié)構(gòu)變得簡單，合理，有效。IBM在1980年推出了PC/XT，然后又推出了RISC系統(tǒng)/6000。SUN也在其SPARC處理器中采用了這個概念。二、RISC技術(shù)的主要內(nèi)容一般來說，CPU的執(zhí)行速度受程序中的指令數(shù)L，每條指令執(zhí)行所需的周期數(shù)CPI和每個周期的時間T3個因素的影響。RISC技術(shù)主要從減少CP入手，采取了以下措施:(1)精簡指令系統(tǒng)。大多數(shù)典型的RISC指令系統(tǒng)通過采用寄存器堆減少緩存次數(shù)，減少CPI來提高CPU速度。同時，采用簡單的指令格式，固定的指令字長和簡單的尋址方式，讓指令的執(zhí)行盡可能安排在一個周期內(nèi)完成。(2)流水線和延遲轉(zhuǎn)移技術(shù)。采用流水線技術(shù)的方式工作，取指令和執(zhí)行指令并行進(jìn)行，雖然一條指令的執(zhí)行需要幾個周期的時間，但從平均效應(yīng)來看，每條指令的周期數(shù)大大減少，甚至達(dá)到每條指令只需一個周期。同時為了避免轉(zhuǎn)移指令中出現(xiàn)重疊方式預(yù)取的下一條指令作廢的浪費，提出了延遲轉(zhuǎn)移的思想，在這兩類指令之后分別安排一條與它們不存在依賴關(guān)系的可立即執(zhí)行的指令，確保流水線的高效運行。(3)采用LOAD，STORE結(jié)構(gòu)和高速緩存結(jié)構(gòu)。RISC技術(shù)只允許LOAD指令和STORE指令執(zhí)行存儲器操作，其他指令只能對寄存器進(jìn)行操作，使大多數(shù)指令的功能得到簡化?？s短了執(zhí)行時間。同時，RISC機器還設(shè)置了較大容量的高速緩存，以擴展存儲器的帶寬，滿足CPU頻繁取指的需要，提高流水線的效率。(4)重疊寄存器窗口技術(shù)。重疊寄存窗口技術(shù)的基本思想是:在機器中配置一個很大的寄存器群，將其劃分給若干個過程使用，每個過程所用的一組寄存器又可分為三部分，第一部分用來與高一級(本過程的主調(diào)過程)交換參數(shù);第二部分只供本過程使用;第三部分用來與低一級過程(本過程的受調(diào)過程)交換參數(shù)。每個過程的第三部分寄存器與低一級的第一部分寄存器合用相同的物理寄存器，以達(dá)到寄存器的重疊使用。利用該重疊窗口進(jìn)行過程的參數(shù)交換沒有任何延遲。(5)在邏輯上采用以硬件為主，軟件為輔的技術(shù)。RISC控制器采用組合邏輯部件，而不采用微程序控制。首先微程序?qū)ξ⒋a的解釋和執(zhí)行很難在一個機器周期內(nèi)完成，這與RISC機器在一個機器周期內(nèi)執(zhí)行一條指令的思想是相違背的;其次，RISC采用硬布線控制邏輯的控制部件所占面積要比微程序存儲器少得多，可以利用所節(jié)余的面積安放寄存器組或其它邏輯電路。(6)采用優(yōu)化編譯程序。RISC指令集的簡化使用CPU執(zhí)行同樣一個程序所需的指令數(shù)I比CISC所需的指令數(shù)I多，但通過優(yōu)化編譯程序和其他方法可減少指令數(shù)I。另外，還可優(yōu)化調(diào)整指令的執(zhí)行順序，以盡量減少機器的空等時間。(7)指令流調(diào)整技術(shù)。為了使RISC處理機中的指令流水線高效地工作。當(dāng)發(fā)現(xiàn)指令流有斷流可能時，調(diào)整指令序列，可以通過重命名來取消數(shù)據(jù)相關(guān)等，從而提高流水線執(zhí)行效率。(8)指令取消技術(shù)。在使用指令取消技術(shù)的處理機里，所有指令都可以決定下面待執(zhí)行的指令是否應(yīng)該取消，如果取消，相當(dāng)于執(zhí)行一條空指令，不影響程序執(zhí)行環(huán)境。三、RISC技術(shù)的優(yōu)缺點實踐證明，采用RISC結(jié)構(gòu)可以帶來如下好處:(1)精簡指令系統(tǒng)設(shè)計適合超大規(guī)模集成電路實現(xiàn)。指令條數(shù)相對較少，尋址方式簡單，指令格式規(guī)整，控制器的譯碼和執(zhí)行硬件相對簡單，VLSI片中用于實現(xiàn)控制器的這部分面積所占的比例明顯減少。(2)可以提供直接支持高級語言的能力，簡化編譯程序的設(shè)計。指令總數(shù)的減少，縮小了編譯過程中對功能類似的機器指令進(jìn)行選擇的范圍，減輕了對各種尋址方式進(jìn)行選擇，分析和變換的負(fù)擔(dān)，易于更換或取消指令，調(diào)整指令順序，提高程序的運行速度。而且，由于主要操作在寄存器間進(jìn)行，及寄存器重疊窗口的采用，直接支持子程序和過程調(diào)用的高級語言處理。(3)可提高機器的執(zhí)行速度和效率，降低設(shè)計成本，提高系統(tǒng)的可靠性。指令系統(tǒng)的精簡可以加快指令的譯碼，控制器的簡化可以縮短指令的執(zhí)行延時等等，這些都可以提高程序執(zhí)行的速度。同時也縮短了設(shè)計周期，減少了設(shè)計錯誤，降低了設(shè)計成本，提高了系統(tǒng)的可靠性。四、計算機系統(tǒng)結(jié)構(gòu)的新發(fā)展VLIWVLIW(VERYLONGINSTRUCTIONWORD)超長指令集架構(gòu)，是微處理器設(shè)計領(lǐng)域中的一種越來越流行的技術(shù)，采用了先進(jìn)的EPIC(清晰并行指令)設(shè)計。這種類型的CPU芯片能從應(yīng)用程序中提取高度并行且長度稍短的指令組成定長長指令數(shù)據(jù)，并把這些機器指令均勻地分配給芯片中的眾多執(zhí)行單元。VLIW最大優(yōu)點是通過編譯器靜脈調(diào)度發(fā)掘程序中潛在的并行性，簡化了處理器的結(jié)構(gòu)，刪除了處理器內(nèi)部許多復(fù)雜的控制電路，這些電路通常是超標(biāo)量芯片(CISC和RISC)協(xié)調(diào)并行工作時必須使用的。VLIW的結(jié)構(gòu)簡單，也能夠使其芯片制造成本降低，價格低廉，能耗少，而且性能也要比超標(biāo)量芯片高得多。目前基于這種指令架構(gòu)的微處理器主要有INTEL的IA-64和AMD的X86-64兩種。第二章存儲系統(tǒng)課堂筆記主要知識點掌握程度本章重點介紹了存儲系統(tǒng)的相關(guān)知識，包括存儲系統(tǒng)的層次結(jié)構(gòu)及特征，重點介紹了并行存儲器、高速緩沖存儲器、虛擬存儲器的功能/結(jié)構(gòu)及原理，最后簡要介紹了存儲保護(hù)的常用方法。知識點整理一、存儲系統(tǒng)概述（一）存儲系統(tǒng)的形成在計算機系統(tǒng)中，存在著許多個不同介質(zhì)、不同性能，不同工作方式的存儲器，其目的都是存放計算機系統(tǒng)中所需要處理的程序和數(shù)據(jù)。儲存系統(tǒng)是隨計算機技術(shù)的不斷發(fā)展而逐步形成的。首先由于計算機的結(jié)構(gòu)由以CPU為中心轉(zhuǎn)變到以主儲存器為中心，使得訪問存儲器的部件不只是單一通路的CPU，而且還有輸入輸出設(shè)備，有時還需要接受多個CPU，多個I/O部件的訪問，因此對主存的訪問速度要求越來越高；其次由于計算機應(yīng)用的不斷發(fā)展，程序越來越大，數(shù)據(jù)越來越多，對機器處理能力的要求不斷提高，主存的容量要求也急劇增加；第三，由于半導(dǎo)體技術(shù)的不斷發(fā)展，CPU速度改進(jìn)很快，主存儲器要與其合理地匹配。計算機系統(tǒng)對存儲器的希望是速度高，能與CPU速度匹配；容量大，能存放下盡可能多的程序數(shù)據(jù)，系統(tǒng)軟件；同時希望價格低廉。一種解決辦法是致力于對存儲器的介質(zhì)、器件組成技術(shù)的研究，以提供性能良好的新型存儲器；另一種解決辦法是通過對各種不同性能的存儲器之間尋求一種相互聯(lián)系、缺陷互補的方法，使其組成存儲器的系統(tǒng)以滿足高性能的要求。所以存儲系統(tǒng)是兩個或兩個以上的速度、容量、價格不同的存儲器采用硬件，軟件或軟、硬件結(jié)合的辦法聯(lián)結(jié)成一個系統(tǒng)，使得整個系統(tǒng)看起來像一個存儲器，其速度接近其中最快的一個，容量接近其中最大的一個，價格接近其中最便宜的一個。（二）存儲系統(tǒng)的層次結(jié)構(gòu)通用寄存器：CPU的一部分，匯編和編譯器可支配，速度最快。高速緩沖存儲器：Cache置于主存儲器與CPU之間，對匯編透明，速度比主存快得多。主存儲器：存儲系統(tǒng)的核心，是用戶的編程空間。輔助存儲器：軟盤、硬盤等，容量大，價格低。脫機大容量存儲：磁帶機，光盤等?，F(xiàn)代計算機的存儲系統(tǒng)中，主要采取了以下2種技術(shù)：1.在主存與CPU之間增加了一級高速緩沖存儲器，使得CPU在對主存訪問時，所面對的存儲器具有高速緩存的速度和主存的容量。2.在主存與輔存之間采用了虛擬存儲技術(shù)，使得CPU在訪問主存時，所見到的存儲器速度接近主存，容量接近輔存。（三）存儲系統(tǒng)的局部性、包含性、一致性局部性：根據(jù)局部性原理即程序往往重復(fù)訪問它剛剛使用過的數(shù)據(jù)和指令，就有可能將最近期和最經(jīng)常被訪問的那一部分指令和數(shù)據(jù)預(yù)取出來存放到速度更高的存儲器中，然后將執(zhí)行完成或不經(jīng)常訪問的指令和數(shù)據(jù)不斷地替換出去放到容量大而速度慢的存儲器中。包含性：是指在容量小的存儲器中（稱上層）所存放的內(nèi)容一定是其下層存儲器內(nèi)容的一部分，也就是說在容量大的存儲器中，一定能找到上層存儲信息的副本。一致性：由于同一信息在各個層次中都存放了它的內(nèi)容，當(dāng)在某一層存儲器中被修改后，也必須使其在其他存儲器的副本，都進(jìn)行修改，以保持同一信息的一致性。二、并行存儲器（一）多體并行訪問存儲器一個多體的主寄存器結(jié)構(gòu)圖如圖2.2.1所示，存儲器是由m個體組成，設(shè)m＝2a，每個存儲體的容量為n，則n＝2b由上述結(jié)構(gòu)可以看出該存儲器的頻帶寬度（指單位時間內(nèi)所能訪問的數(shù)據(jù)量）B＝mW/T，即可以同時訪問m條指令或m個數(shù)據(jù)，但取出的m個數(shù)不一定都有用，產(chǎn)生這一缺陷的主要原因是地址寄存器共用一個，每次訪問的地址碼各體內(nèi)相同。如果每個存儲體分別具有自己的地址寄存器那么上述缺陷可以大大改善。（二）多體并行交叉訪問存儲器所謂交叉訪問是指當(dāng)存在多個訪問源時，這些訪問源可以同時向多個體中的任何一個發(fā)出訪問請求。依據(jù)編址方式的不同，可分為高位交叉訪問與低位交叉訪問兩種。1、高位交叉訪問圖2.2.2示出了高位交叉訪問的存儲器結(jié)構(gòu)（高位連續(xù)地址分別處于不同體中），圖中結(jié)構(gòu)具有m個體，每個體內(nèi)容量為n個字，存儲單元的地址由兩部分組成，地址碼的低位部分為各體內(nèi)地址，由0～(n-1)；高位字段表示了各體的體號，由0～(m-1)。尋址時，地址的高位字段指出尋址的體，低位字段送到該體的地址寄存器(MAR)。存儲器的總?cè)萘繛閙×n個字，地址碼長度為log2(m×n)位，其中，地址的高字段為log2m位，低位字段為log2由于程序局部性原理，近期所用到的指令和數(shù)據(jù)往往都集中在一個體內(nèi)，從而出現(xiàn)了并行訪問沖突，如果在多任務(wù)多用戶的應(yīng)用狀態(tài)下，訪問沖突較少。2、低位交叉訪問圖2.2.3示出了低位交叉訪問存儲器結(jié)構(gòu)（低位連續(xù)地址分別處于不同體中），地址碼的低位字段為存儲體號，高位字段為存儲體內(nèi)的地址，低位字段譯碼后決定選擇哪個存儲體的數(shù)據(jù)。由于編址方式采用連續(xù)地址分布在不同存儲體中，因此并行性比較好，可以有效地拓寬存儲器的頻帶。為了達(dá)到提高主存儲器速度的目的，采用了低位交叉方式的存儲器，在一個存儲器周期內(nèi)，m個存儲體必須分時啟動，實際上是一種采用流水線方式工作，因而被廣泛地采用，特別是在多處理機，流水線處理機中，一般都采用了這種低位交叉訪問的多體存儲器。在低位交叉訪問的存儲器中，影響其性能提高的因素有二點：一是轉(zhuǎn)移指令的出現(xiàn)；二是數(shù)據(jù)訪問時同體產(chǎn)生沖突，兩者比較起來，后者的影響更為嚴(yán)重。如何才能減少這種沖突呢？下面以一維數(shù)組和二維數(shù)組為例，說明解決沖突的方法。（1）一維數(shù)組（向量）的無沖突訪問存儲器按連續(xù)地址訪問，沒有沖突，按位移量為2的變址方式訪問，頻帶寬度降低一半……方法：存儲體的個數(shù)取質(zhì)數(shù)，且m≥向量長度。例如：Burroughs公司巨型機BSP，存儲體個數(shù)為17；CRAY-1機存儲體個數(shù)為31；我國研制的銀河巨型機，存儲體的個數(shù)為37。（2）二維數(shù)組的無沖突訪問存儲器要求：一個n×n的二維數(shù)組，按行、列、對角線以及反對角線訪問，并且在不同的變址位移量情況下，都能實現(xiàn)無沖突訪問。順序存儲：按行、對角線訪問沒有沖突，但按列訪問每次沖突。方法：存儲體的個數(shù)大于或等于向量長度（數(shù)組列數(shù)）且取質(zhì)數(shù)，并錯位存放。三、高速緩沖存儲器（Cache）（一）高速緩沖存儲器的功能、結(jié)構(gòu)與工作原理高速緩沖存儲器是存在于主存與CPU之間的一級存儲器，由靜態(tài)存儲芯片(SRAM)組成，容量比較小但速度比主存高得多，接近于CPU的速度。Cache的功能是用來存放那些近期需要運行的指令與數(shù)據(jù)。目的是提高CPU對存儲器的訪問速度。為此需要解決2個技術(shù)問題：一是主存地址與緩存地址的映象及轉(zhuǎn)換；二是按一定原則對Cache的內(nèi)容進(jìn)行替換。Cache的結(jié)構(gòu)和工作原理如圖2.3.1所示。主要由三大部分組成：Cache存儲體：存放由主存調(diào)入的指令與數(shù)據(jù)塊。地址轉(zhuǎn)換部件：建立目錄表以實現(xiàn)主存地址到緩存地址的轉(zhuǎn)換。替換部件：在緩存已滿時按一定策略進(jìn)行數(shù)據(jù)塊替換，并修改地址轉(zhuǎn)換部件。（二）地址映象與轉(zhuǎn)換概念：地址映象是指某一數(shù)據(jù)在內(nèi)存中的地址與在緩沖中的地址，兩者之間的對應(yīng)關(guān)系。下面介紹三種地址映象的方式。1、全相聯(lián)方式地址映象規(guī)則：主存的任意一塊可以映象到Cache中的任意一塊(1)主存與緩存分成相同大小的數(shù)據(jù)塊。(2)主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間中。全相聯(lián)方式的對應(yīng)關(guān)系如圖2.3.2所示。如果Cache的塊數(shù)為Cb，主存的塊數(shù)為Mb，則映象關(guān)系共有Cb×Mb種。圖2.3.3示出了目錄表的格式及地址變換規(guī)則。目錄表存放在相關(guān)（聯(lián)）存儲器中，其中包括三部分：數(shù)據(jù)塊在主存的塊地址、存入緩存后的塊地址、及有效位（也稱裝入位）。由于是全相聯(lián)方式，因此，目錄表的容量應(yīng)當(dāng)與緩存的塊數(shù)相同。舉例：某機主存容量為1M，Cache的容量為32KB，每塊的大小為16個字（或字節(jié)）。劃出主、緩存的地址格式、目錄表格式及其容量。容量：與緩沖塊數(shù)量相同即211＝2048（或32K/16＝2048）。優(yōu)點：命中率比較高，Cache存儲空間利用率高。缺點：訪問相關(guān)存儲器時，每次都要與全部內(nèi)容比較，速度低，成本高，因而應(yīng)用少。2、直接相聯(lián)方式地址映象規(guī)則：主存儲器中一塊只能映象到Cache的一個特定的塊中。(1)主存與緩存分成相同大小的數(shù)據(jù)塊。(2)主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。(3)主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的位置。圖2.3.4示出了直接相聯(lián)映象規(guī)則?？梢姡鞔嬷懈鲄^(qū)內(nèi)相同塊號的數(shù)據(jù)塊都可以分別調(diào)入緩存中塊號相同的地址中，但同時只能有一個區(qū)的塊存入緩存。由于主、緩存塊號相同，因此，目錄登記時，只記錄調(diào)入塊的區(qū)號即可。圖2.3.5示出了主、緩沖地址格式、目錄表的格式及地址變換規(guī)則。主、緩存塊號及塊內(nèi)地址兩個字段完全相同。目錄表存放在高速小容量存儲器中，其中包括二部分：數(shù)據(jù)塊在主存的區(qū)號和有效位。目錄表的容量與緩存的塊數(shù)相同。地址變換過程：用主存地址中的塊號B去訪問目錄存儲器，把讀出來的區(qū)號與主存地址中的區(qū)號E進(jìn)行比較，比較結(jié)果相等，有效位為1，則Cache命中，可以直接用塊號及塊內(nèi)地址組成的緩沖地址到緩存中取數(shù)；比較結(jié)果不相等，有效位為1，可以進(jìn)行替換，如果有效位為0，可以直接調(diào)入所需塊。優(yōu)點：地址映象方式簡單，數(shù)據(jù)訪問時，只需檢查區(qū)號是否相等即可，因而可以得到比較快的訪問速度，硬件設(shè)備簡單。缺點：替換操作頻繁，命中率比較低。舉例：上例中，主存容量為1M，Cache的容量為32KB，每塊的大小為16個字（或字節(jié)）。劃出主、緩存的地址格式、目錄表格式及其容量。容量：與緩沖塊數(shù)量相同即211＝2048（或32K/16＝2048）。3、組相聯(lián)映象方式組相聯(lián)的映象規(guī)則：(1)主存和Cache按同樣大小劃分成塊。(2)主存和Cache按同樣大小劃分成組。(3)主存容量是緩存容量的整數(shù)倍，將主存空間按緩沖區(qū)的大小分成區(qū)，主存中每一區(qū)的組數(shù)與緩存的組數(shù)相同。(4)當(dāng)主存的數(shù)據(jù)調(diào)入緩存時，主存與緩存的組號應(yīng)相等，也就是各區(qū)中的某一塊只能存入緩存的同組號的空間內(nèi)，但組內(nèi)各塊地址之間則可以任意存放，即從主存的組到Cache的組之間采用直接映象方式；在兩個對應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。圖2.3.6示出了組相聯(lián)的映象關(guān)系，圖中緩存共分Cg個組，每組包含有Gb塊；主存是緩存的Me倍，所以共分有Me個區(qū)，每個區(qū)有Cg組，每組有Gb塊。那么，主存地址格式中應(yīng)包含4個字段：區(qū)號、區(qū)內(nèi)組號、組內(nèi)塊號和塊內(nèi)地址。而緩存中包含3個字段：組號、組內(nèi)塊號、塊內(nèi)地址。主存地址與緩存地址的轉(zhuǎn)換有兩部分，組地址是按直接映象方式，按地址進(jìn)行訪問，而塊地址是采用全相聯(lián)方式，按內(nèi)容訪問。組相聯(lián)的地址轉(zhuǎn)換部件也是采用相關(guān)存儲器實現(xiàn)，見圖2.3.7。相關(guān)存儲器中每個單元包含有：主存地址中的區(qū)號E與組內(nèi)塊號B，兩者結(jié)合在一起，其對應(yīng)的字段是緩存塊地址b。相關(guān)存儲器的容量，應(yīng)與緩存的塊數(shù)相同。當(dāng)進(jìn)行數(shù)據(jù)訪問時，先根據(jù)組號，在目錄表中找到該組所包含的各塊的目錄，然后將被訪數(shù)據(jù)的主存區(qū)號與組內(nèi)塊號，與本組內(nèi)各塊的目錄同時進(jìn)行比較。如果比較相等，而且有效位為“1”則命中?？蓪⑵鋵?yīng)的緩存塊地址b送到緩存地址寄存器的塊地址字段，與組號及塊內(nèi)地址組裝即形成緩存地址。如果比較不相等，說明沒命中，所訪問的數(shù)據(jù)塊尚沒有進(jìn)入緩存，則進(jìn)行組內(nèi)替換；如果有效位為0，則說明緩存的該塊尚未利用，或是原來數(shù)據(jù)作廢，可重新調(diào)入新塊。優(yōu)點：塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。缺點：實現(xiàn)難度和造價要比直接映象方式高。（三）替換策略根據(jù)程序局部性規(guī)律可知：程序在運行中，總是頻繁地使用那些最近被使用過的指令和數(shù)據(jù)。這就提供了替換策略的理論依據(jù)。綜合命中率、實現(xiàn)的難易及速度的快慢各種因素，替換策略可有隨機法、先進(jìn)先出法、最近最少使用法等。1、隨機法（RAND法）隨機法是隨機地確定替換的存儲塊。設(shè)置一個隨機數(shù)產(chǎn)生器，依據(jù)所產(chǎn)生的隨機數(shù)，確定替換塊。這種方法簡單、易于實現(xiàn)，但命中率比較低。2、先進(jìn)先出法（FIFO法）先進(jìn)先出法是選擇那個最先調(diào)入的那個塊進(jìn)行替換。當(dāng)最先調(diào)入并被多次命中的塊，很可能被優(yōu)先替換，因而不符合局部性規(guī)律。這種方法的命中率比隨機法好些，但還不滿足要求。先進(jìn)先出方法易于實現(xiàn)，例如Solar－16/65機Cache采用組相聯(lián)方式，每組4塊，每塊都設(shè)定一個兩位的計數(shù)器，當(dāng)某塊被裝入或被替換時該塊的計數(shù)器清為0，而同組的其它各塊的計數(shù)器均加1，當(dāng)需要替換時就選擇計數(shù)值最大的塊被替換掉。3、最近最少使用法（LRU法）LRU法是依據(jù)各塊使用的情況，總是選擇那個最近最少使用的塊被替換。這種方法比較好地反映了程序局部性規(guī)律。實現(xiàn)LRU策略的方法有多種。下面簡單介紹計數(shù)器法、寄存器棧法及硬件邏輯比較對法的設(shè)計思路。計數(shù)器方法：緩存的每一塊都設(shè)置一個計數(shù)器，計數(shù)器的操作規(guī)則是：(1)被調(diào)入或者被替換的塊，其計數(shù)器清“0”，而其它的計數(shù)器則加“1”。(2)當(dāng)訪問命中時，所有塊的計數(shù)值與命中塊的計數(shù)值要進(jìn)行比較，如果計數(shù)值小于命中塊的計數(shù)值，則該塊的計數(shù)值加“1”；如果塊的計數(shù)值大于命中塊的計數(shù)值，則數(shù)值不變。最后將命中塊的計數(shù)器清為0。(3)需要替換時，則選擇計數(shù)值最大的塊被替換。例如IBM370/65機的Cache用組相聯(lián)方式，每組4塊，每一塊設(shè)置一個2位的計數(shù)器，其工作狀態(tài)如表2.3.1。表2.3.1計數(shù)器法實現(xiàn)LRU策略主存塊地址塊4塊2塊3塊5塊號計數(shù)器塊號計數(shù)器塊號計數(shù)器塊號計數(shù)器Cache塊0110111111500Cache塊1301310300301Cache塊2400401410411Cache塊3空XX200201210操作起始狀態(tài)調(diào)入命中替換寄存器棧法：設(shè)置一個寄存器棧，其容量為Cache中替換時參與選擇的塊數(shù)。如在組相聯(lián)方式中，則是同組內(nèi)的塊數(shù)。堆棧由棧頂?shù)綏５滓来斡涗浿鞔鏀?shù)據(jù)存入緩存的塊號，現(xiàn)以一組內(nèi)4塊為例說明其工作情況，如表2.3.2所示，表中1～4為緩存中的一組的4個塊號。表2.3.2寄存器棧法實現(xiàn)緩存操作初始狀態(tài)調(diào)入2命中塊4替換塊1寄存器03241寄存器14324寄存器21432寄存器3空113(1)當(dāng)緩存中尚有空閑時，如果不命中，則可直接調(diào)入數(shù)據(jù)塊，并將新訪問的緩沖塊號壓入堆棧，位于棧頂。其他棧內(nèi)各單元依次由頂向下順壓一個單元，直到空閑單元為止。(2)當(dāng)緩存已滿，如果數(shù)據(jù)訪問命中，則將訪問的緩存塊號壓入堆棧，其他各單元內(nèi)容由頂向底逐次下壓直到被命中塊號的原來位置為止。如果訪問不命中，說明需要替換，此時棧底單元中的塊號即是最久沒有被使用的。所以將新訪問塊號壓入堆棧，棧內(nèi)各單元內(nèi)容依次下壓直到棧底，自然，棧底所指出的塊被替換。比較對法：比較對法是用一組硬件的邏輯電路來記錄各塊使用的時間與次數(shù)。假設(shè)Cache的每組中有4塊，替換時，是比較4塊中那一塊是最久沒使用的，4塊之間兩兩相比可以有6種比較關(guān)系。如果每兩塊之間的對比關(guān)系用一個RS觸發(fā)器，則需要6個觸發(fā)器（T12，T13，T14，T23，T24，T34），設(shè)T12＝0表示塊1比塊2最久沒使用，T12＝1表示塊2比塊1最久沒有被使用。在每次訪問命中或者新調(diào)入塊時，與該塊有關(guān)的觸發(fā)器的狀態(tài)都要進(jìn)行修改。按此原理，由6個觸發(fā)器組成的一組編碼狀態(tài)可以指出應(yīng)被替換的塊。例如，塊1被替換的條件是：T12＝0，T13＝0，T14＝0；塊2被替換的條件是：T12＝1，T23＝0，T24＝0等等。（四）Cache的一致性問題Cache的內(nèi)容是主存內(nèi)容的一部分，是主存的副本，內(nèi)容應(yīng)該與主存一致。由于：(1)CPU寫Cache，沒有立即寫主存；(2)I/O處理機或I/O設(shè)備寫主存。從而造成Cache與主存內(nèi)容的不一致，如圖2.3.8所示。對Cache進(jìn)行寫操作時引起的不一致的解決方法：1、全寫法亦稱寫直達(dá)法（WT法-Writethrough）方法：在對Cache進(jìn)行寫操作的同時，也對主存該內(nèi)容進(jìn)行寫入。優(yōu)點：可靠性較高，操作過程比較簡單。缺點：寫操作速度得不到改善，與寫主存的速度相同。2、寫回法（WB法-Writeback）方法：在CPU執(zhí)行寫操作時，只寫入Cache，不寫入主存。優(yōu)點：速度較高。缺點：可靠性較差，控制操作比較復(fù)雜。（五）Cache性能分析1、Cache系統(tǒng)的加速比存儲系統(tǒng)采用Cache技術(shù)的主要目的是提高存儲器的訪問速度，加速比是其重要的性能參數(shù)。Cache存儲系統(tǒng)的加速比SP（Speedup）為：其中：Tm為主存儲器的訪問周期，Tc為Cache的訪問周期，T則為Cache存儲系統(tǒng)的等效訪問周期，H為命中率?？梢钥闯?，加速比的大小與兩個因素有關(guān)：命中率H及Cache與主存訪問周期的比值Tc/Tm，命中率越高加速比越大。圖2.3.9示出了加速比與命中率的關(guān)系。2、Cache的命中率影響Cache命中率的因素很多，如Cache的容量，塊的大小，映象方式，替換策略以及程序執(zhí)行中地址流的分布情況等等。一般地說，Cache容量越大則命中率越高，當(dāng)容量達(dá)到一定程度后，容量的增加命中率的改善并不大；Cache塊容量加大，命中率也明顯增加，但增加到一定值之后反而出現(xiàn)命中率下降的現(xiàn)象；直接映象法命中率比較低，全相聯(lián)方式命中率比較高，在組相聯(lián)方式中，組數(shù)分得越多，則命中率下降。四、虛擬存儲器（一）概述目的：虛擬存儲器是由主存儲器和輔助存儲器組成，通過必須的軟件和硬件的支持，使得CPU可以訪問的存儲器具有近似于主存的速度和近似于輔存的容量。虛擬存儲器通過存儲管理部件，使輔存中的內(nèi)容動態(tài)地調(diào)入主存，以滿足程序?qū)Υ笕萘看鎯ζ鞯囊?。工作過程：CPU訪問主存時所給出的是虛地址VA，必須通過存儲管理部件進(jìn)行轉(zhuǎn)換。如果訪問命中主存，則將VA轉(zhuǎn)換成主存的物理地址PA，到主存存取數(shù)據(jù)或指令（D或I）；如果不命中，則說明所需的I或D尚在輔存，則將VA轉(zhuǎn)換成輔存地址，進(jìn)行輔存與主存之間的信息傳輸。主要技術(shù)問題：虛實地址映象與轉(zhuǎn)換，主存內(nèi)容的替換（與高速緩存存儲器相同）。（二）虛擬存儲器的管理方式1、段式管理（1）地址映象：一個用戶程序可以包含多個功能不同的程序段，例如主程序、各個子程序、數(shù)據(jù)塊、表格、向量等等。各段的大小可以不同。因此，可以將虛存空間分段，當(dāng)程序從輔存調(diào)入主存時，按段調(diào)入，按段分配足夠的空間，段內(nèi)地址連續(xù)，只要主存具有足夠的連續(xù)空間，新調(diào)入的段可以存放在內(nèi)存的任意空間。如圖2.4.1所示。為了記錄地址映象關(guān)系，每一個應(yīng)用程序（或進(jìn)程）都建立一個段表。段表的內(nèi)容主要應(yīng)包括段長度及在主存的起始地址。每個程序段調(diào)入時，應(yīng)填入段表相應(yīng)內(nèi)容。（2）地址轉(zhuǎn)換：主存與虛存的地址格式如下：如圖2.4.2所示，當(dāng)CPU進(jìn)行訪問時，給出的是虛地址VA，首先根據(jù)用戶號對基址寄存器進(jìn)行訪問找到用戶號，取出其段首地址，然后與VA中的段號相加，即得到所要訪問的段號，根據(jù)此段記錄的主存首地址與段內(nèi)地址相加即可得主存實地址。（3）主要優(yōu)點：程序模塊化的性能好，各段在功能上是相互獨立的。便于編制、修改和調(diào)試，對某一段的處理對其他各段沒有影響。便于程序和數(shù)據(jù)的共享。因為功能上獨立而完整，所以當(dāng)其他程序需要共享時，可以在主段中裝入此段，在段表中列入它的主存首址即可享用。程序的動態(tài)鏈接比較容易。便于實現(xiàn)存儲保護(hù)。（4）主要缺點：地址變換所需的時間比較長。主存的空間利用不充分。對輔存（磁盤）的管理比較困難。2、頁式管理（1）地址映象：頁式管理是將主存空間與虛存空間按固定的大小劃分成塊，每塊稱為一頁。頁的大小和劃分與程序的邏輯功能無關(guān)，由操作系統(tǒng)軟件來執(zhí)行。一般而言，一頁的大小應(yīng)該是512Bit的整數(shù)倍，因為輔助磁盤存儲的物理塊的大小為512Bit。虛頁中的頁稱為虛頁，實存中的各頁稱為實頁，各虛頁與實頁之間按全相聯(lián)方式映象，也就是虛頁中的一頁，可以存入主存中的任意一頁的位置，如圖2.4.3所示。（2）地址轉(zhuǎn)換：主存地址與虛存地址只是頁號不同，也就是頁的首地址不同，而頁內(nèi)地址是相同的。其地址格式如下：圖2.4.4示出了地址轉(zhuǎn)換過程，當(dāng)CPU給出所要訪問的虛地址后，根據(jù)用戶號訪問基址寄存器，求得用戶的頁表首地址Pa，然后與虛地址中的虛頁號P相加，得到該頁的表目，由此表目中得到該頁存入主存中的實頁號為p，將該頁號讀出與頁內(nèi)地址組裝即可得到主存的實際地址。（3）主要優(yōu)點：主存儲器的空間利用率比較高，不得已而浪費的空間每個用戶不到一頁。頁表的管理比較簡單，可以不考慮程序的長短；頁表的結(jié)構(gòu)也比較簡單。地址映象與地址轉(zhuǎn)換速度比較快。按頁的管理方式，與對輔存的地址格式是一致的，因而管理起來比較容易。（4）主要缺點：由于頁的長度一般比段小，所以虛空間的頁數(shù)就很多，頁表長度很大，占用很大的存儲空間（幾MB～幾十MB）。程序的模塊化性能不好。3、段頁式管理（1）地址映象：段頁式管理是將虛擬存儲空間按段式管理，而主存空間按頁式管理，存在于虛空間的程序按邏輯關(guān)系分段，每一段又可分為固定大小的頁；主存則只分成若干相同大小的頁。段頁式地址映象的方式是虛存的任意一段的任意一頁，可以存入主存的任意一個實頁空間。如圖2.4.5所示。（2）地址轉(zhuǎn)換：為了記錄下這種映象關(guān)系和進(jìn)行地址轉(zhuǎn)換，需要三層表：段表基地址表，段表和頁表。每個用戶在段表基址表中占一行，在段表基地址表中給出該用戶的段表長度和段表首地址；每個用戶一張段表，每個程序段在段表中占一行，在段表中給出該程序段的頁表長度和頁表的起始地址；每一段都有一張頁表，頁表中給出這個程序段的每一頁在主存儲器中的實頁號。圖2.4.6示出了段頁式管理地址轉(zhuǎn)換過程，CPU根據(jù)虛地址用戶號U，查找段表基地址表得到該用戶的段表首地址As，然后與虛地址中的段號S相加，在段表中查找到頁表的首地址，然后再與虛地址中的虛頁號P相加，在頁表中找到該頁在內(nèi)存的實際頁首地址p，再與虛地址中的頁內(nèi)地址組合得到所要訪問的主存地址。（3）主要優(yōu)缺點：綜合了段式、頁式的優(yōu)點，但多了一次查表過程，因而降低了速度。（三）虛擬存儲器的工作過程在說明虛擬存儲器工作過程之前需要先說明兩個問題，一是為了加快查表速度所采取的措施；二是虛地址與輔存地址，也就是磁盤地址的轉(zhuǎn)換。下面以頁式管理為例。1、快表和目錄表為了提高地址轉(zhuǎn)換速度，縮短查表時間，采用一個小容量的、高速的相關(guān)存儲部件，用來存放當(dāng)前最經(jīng)常用到的那一部分頁表，采取按內(nèi)容相聯(lián)方式進(jìn)行訪問。這樣，查頁表的時間就相當(dāng)于訪問小容量的相關(guān)存儲器的時間，從而大大地提高了速度，這個小容量相關(guān)存儲器稱為快表，存放在主存的頁表稱為慢表?？毂淼膬?nèi)容包括兩部分即虛地址與實地址的對應(yīng)關(guān)系。虛地址中包括用戶號及虛頁號，對應(yīng)的是它存入主存的實頁號。當(dāng)進(jìn)行地址轉(zhuǎn)換時，將虛地址中的用戶號和虛頁號做為模式與快表中的各表目進(jìn)行比較。同時也送往主存，查找慢表。如果快表命中，立即可以得到對應(yīng)的實頁號。如果不命中，則由慢表中求出實頁號。然后替換快表內(nèi)容。如圖2.4.7所示。目錄表法是采用一個小容量的高速存儲器（按照內(nèi)容訪問的相關(guān)存儲器，稱為目錄表），把那些已經(jīng)調(diào)入的頁的地址對應(yīng)關(guān)系存入其中。因為頁表的容量是整個虛空間的頁數(shù)，但實際上被用到的頁表內(nèi)容占整個頁表容量的比例很小，因此可以把裝入位為“1”的頁表表目存入高速的目錄表中。在CPU訪問時，可先查目錄表，凡已入駐主存的地址都記錄在此目錄表中，一般情況下都可查到它的主存地址。如果在目錄表中沒有查到，則說明此頁尚未進(jìn)入主存。此時需要由輔存將要訪問的頁全部送入主存。如圖2.4.8所示。2、虛存與外存地址的轉(zhuǎn)換當(dāng)CPU訪問主存時，虛地址通過頁表轉(zhuǎn)換成主存地址。當(dāng)該虛地址所在的頁尚沒有調(diào)入主存時，就應(yīng)當(dāng)按照虛地址到輔存中尋找到該頁，并通過輸入輸出操作調(diào)入主存。因此需要將虛地址轉(zhuǎn)換成輔存地址。虛地址與磁盤地址（輔存地址）的轉(zhuǎn)換也是建立一個對應(yīng)關(guān)系表稱為外頁表，它記錄了虛地址與磁盤實地址的對應(yīng)關(guān)系，轉(zhuǎn)換過程如圖2.4.9所示。外頁表的表目是按虛存頁號順序排放的，每個表目內(nèi)只記錄了該虛頁對應(yīng)的磁盤地址及裝入位。每一個用戶具有一張外頁表，外頁表存放在主存中，通過執(zhí)行軟件進(jìn)行表目的查找。外頁表的首地址根據(jù)虛地址中的用戶號來查找，再根據(jù)虛頁號到外頁表中查找該頁對應(yīng)的磁盤地址。3、頁式管理虛擬存儲器工作過程(1)系統(tǒng)中每個用戶都有自己的頁表基址寄存器，頁表（慢表）及快表，當(dāng)CPU需要訪問時，首先查快表，如果命中則可以得到實頁號，然后與頁內(nèi)地址組裝成為主存的實際地址。(2)如果在快表中不命中，則通過查慢表得出實頁號，同時修改快表內(nèi)容。(3)如果慢表中仍然沒有命中，則說明該頁尚未進(jìn)入主存，發(fā)生頁面實效，出現(xiàn)缺頁中斷，系統(tǒng)轉(zhuǎn)入中斷處理。在中斷處理程序中需完成兩項工作：一是查外頁表，進(jìn)行虛地址與磁盤地址的轉(zhuǎn)換，并到磁盤中讀取該頁。二是查詢主存使用狀態(tài)，如果主存沒有存滿，則直接將磁盤信息調(diào)入，并修改頁表及快表；如果主存已滿，則需要進(jìn)行替換。為了方便查詢主存占用情況，通常建立一個幀頁表（幀頁號，內(nèi)容，虛地址，狀態(tài)位），其中幀頁號字段是指主存的實際頁號，內(nèi)容字段存放用戶名或程序名，虛地址字段記錄存入該頁的虛頁號，狀態(tài)頁字段指明虛頁的信息是否已調(diào)入主存。（四）頁面替換策略當(dāng)發(fā)生頁面失效時，要從磁盤中調(diào)入一頁到主存。如果主存儲器的所有頁面都已經(jīng)被占用，必須從主存儲器中淘汰掉一個不常使用的頁面，以便騰出主存空間來存放新調(diào)入的頁面。由于虛擬存儲器技術(shù)的理論依據(jù)與高速緩沖存儲器相同，都是程序局部性原理，所以替換策略基本上是相同的。即：(1)隨機算法（RANDrandomalgorithm）(2)先進(jìn)先出算法（FIFOfirst-infirst-outalgorithm）(3)近期最少使用算法(LFUleastfrequentlyusedalgorithm)(4)最久沒有使用算法（LRUleastrecentlyusedalgorithm）（五）虛擬存儲器的性能分析虛擬存儲器技術(shù)，改善了主存容量不足的缺陷，使用戶可以使用到近似于輔存的空間，希望獲得近似于主存的訪問速度。影響訪問速度的主要因素是訪問快表和頁表的命中率，訪問虛存的等效訪問周期Tv可以用下式計算：其中：Hv是訪問主存的命中率；T1是訪問主存的時間；T2是磁盤存儲器的訪問速度。影響命中率的因素有下列幾方面：1.頁面大?。寒?dāng)頁面比較小時，隨著頁面的增大，命中率明顯提高，但當(dāng)頁面增大到一定值時，命中率不再增大，而隨著頁面的增大而下降。2.主存容量：當(dāng)主存容量增加時，命中率不斷提高；當(dāng)容量增大到一定程度后，命中率的提高就不大了。3.頁面調(diào)度方式：頁面的調(diào)度都是發(fā)生在產(chǎn)生缺頁中斷時進(jìn)行，因此在程序剛開始運行時命中率很低，為此可以采用預(yù)取式調(diào)度法，提高命中率。五、存儲保護(hù)在采用了多用戶虛擬存儲技術(shù)后，在主存中存放的有系統(tǒng)程序也有用戶程序，甚至是多個用戶的程序。為了防止各用戶程序之間訪問錯誤，保護(hù)系統(tǒng)程序免受破壞，就要設(shè)法使各用戶之間，用戶與系統(tǒng)程序之間隔離開。下面介紹三種存儲保護(hù)方式。（一）加界保護(hù)方式在采用段式管理的方式下，程序段在內(nèi)存是連續(xù)存放的，因此可以在CPU中設(shè)置多個界限寄存器，每一個程序占用一對界限寄存器。當(dāng)調(diào)入時，可以將其上界、下界存入界限寄存器中，當(dāng)程序運行過程中，每當(dāng)訪問主存時，首先將訪問地址與上下界寄存器進(jìn)行比較，如果在此區(qū)域內(nèi)，則允許訪問，否則不允許訪問。這種保護(hù)方式是對存儲區(qū)的保護(hù)，運用于段式管理。（二）鍵保護(hù)方式在頁式或段頁式管理中，主存是按頁面管理的。將主存的每一頁都設(shè)置一個存儲鍵，給予一個鍵號，此鍵號存放在快表的表目中。對于每個用戶程序的各頁，也設(shè)置一個程序鍵，給予一個鍵號。當(dāng)該頁由輔存調(diào)入主存時，就將其調(diào)入的實頁號及其鍵號登記在快表中，將程序鍵號，送入程序狀態(tài)字中。每次訪問主存，首先進(jìn)行鍵號比較，如果鍵號相等才允許訪問，存儲鍵與程序鍵鍵號的分配，由操作系統(tǒng)完成。（三）環(huán)保護(hù)方式將系統(tǒng)程序和各用戶程序按其功能的性質(zhì)和要求分為幾個級別，分別授予不同的權(quán)限。各級之間如同同心環(huán)的關(guān)系由內(nèi)層向外層級別逐漸降低，各層的環(huán)號由操作系統(tǒng)給定，每個程序都具有一個環(huán)號，此環(huán)號說明該程序只能訪問它的同級或低級的程序。為了進(jìn)一步對信息進(jìn)行保護(hù)，對于那些可以訪問頁面的訪問方式也給予了授權(quán)，對內(nèi)存的信息可以有三種訪問操作，即讀、寫、執(zhí)行，訪問方式就是對這三種訪問操作的規(guī)定。第二章存儲系統(tǒng)關(guān)鍵詞匯1、通用寄存器CPU的一部分，匯編和編譯器可支配，速度最快。2、高速緩沖存儲器Cache置于主存儲器與CPU之間，對匯編透明，速度比主存快得多。3、主存儲器存儲系統(tǒng)的核心，是用戶的編程空間。4、輔助存儲器軟盤、硬盤等，容量大，價格低。5、脫機大容量存儲磁帶機，光盤等。6、地址映象指某一數(shù)據(jù)在內(nèi)存中的地址與在緩沖中的地址，兩者之間的對應(yīng)關(guān)系。7、全相聯(lián)方式地址映象地址映象規(guī)則：主存的任意一塊可以映象到Cache中的任意一塊(1)主存與緩存分成相同大小的數(shù)據(jù)塊。(2)主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間中。8、直接相聯(lián)方式地址映象地址映象規(guī)則：主存儲器中一塊只能映象到Cache的一個特定的塊中。(1)主存與緩存分成相同大小的數(shù)據(jù)塊。(2)主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。(3)主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的位置。9、組相聯(lián)映象方式地址映象組相聯(lián)的映象規(guī)則：(1)主存和Cache按同樣大小劃分成塊。(2)主存和Cache按同樣大小劃分成組。(3)主存容量是緩存容量的整數(shù)倍，將主存空間按緩沖區(qū)的大小分成區(qū)，主存中每一區(qū)的組數(shù)與緩存的組數(shù)相同。(4)當(dāng)主存的數(shù)據(jù)調(diào)入緩存時，主存與緩存的組號應(yīng)相等，也就是各區(qū)中的某一塊只能存入緩存的同組號的空間內(nèi)，但組內(nèi)各塊地址之間則可以任意存放，即從主存的組到Cache的組之間采用直接映象方式；在兩個對應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。第二章存儲系統(tǒng)FAQ一、主存實際頻寬與模數(shù)m的關(guān)系是什么？出現(xiàn)這種現(xiàn)象的原因是什么？指令流與數(shù)據(jù)流完全隨機時，主存實際頻寬與模塊數(shù)m有什么關(guān)系？答：并行主存系統(tǒng)的實際頻寬隨模數(shù)m的增加會提高，但不是線性增加，隨模數(shù)m增大，其實際頻寬的增量越來越小。這是因為程序中的指令和數(shù)據(jù)并不是完全順序放置和被訪問的。程序會有轉(zhuǎn)移，數(shù)據(jù)分布有一定的隨機性。如果指令流和數(shù)據(jù)流完全隨機時，主存的實際頻寬將隨模數(shù)m的增大，大致成平方根的關(guān)系增大。二、在頁式虛擬儲存器中，什么叫頁面失效？什么叫頁面爭用？什么時候兩者同時發(fā)生？什么時候兩者不同時發(fā)生？答：要訪問的虛頁不再實際主存中時，就會發(fā)生頁面失效。當(dāng)頁面調(diào)入主存，主存中的頁面位置全部已被其它虛頁占用時，就會發(fā)生頁面增用。當(dāng)分配給程序的內(nèi)存已被全部占用之后，只要發(fā)生頁面失效，就一定會發(fā)生頁面爭用。反之，發(fā)生頁面失效，并不會發(fā)生頁面爭用。三、什么是堆棧型的替換算法（用式子描述）？答：能滿足下列兩個關(guān)系式的替換算法就是堆棧型的替換算法。即其中，n為分配給程序的實頁數(shù)，Bt(n)為t時刻在n個實頁中的頁面集合，Lt為t時刻已處理過的不同虛頁的頁面數(shù)。四、對于二級虛擬存儲層次，其等效訪問時間與主、輔存的訪問時間有什么關(guān)系？需提高存儲層次的等效訪問速度，可采取的措施有哪些？答：存儲層次的等效訪問時間是主、輔訪問時間T1和T2的概率加權(quán)平均和，即式中，H為主存命中率。要提高存儲層次等效訪問速度，可采取的措施有：①當(dāng)?shù)刃гL問時間遠(yuǎn)遠(yuǎn)大于主訪問周期時，可采取提高主存命中率的方法，如，改進(jìn)替換算法、增大主存容量、調(diào)整頁面大小、改進(jìn)頁面調(diào)度算法等。②當(dāng)主存命中率H已經(jīng)很高時，可提高主存的訪問速度，以降低T1。③加快內(nèi)部地址映象和變換，如采用快－慢表層次、增大快表命中率等等。五、CPU寫Cache時，會發(fā)生Cache與主存的對應(yīng)復(fù)本內(nèi)容不一致的現(xiàn)象，解決這個問題有什么方法？各需要增加什么開銷？答：寫回法：CPU只寫入Cache，不寫入主存，僅當(dāng)Cache快替換時，才寫回主存后在替換。這種方法要求對每個Cache塊增加一個修改位的資源開銷。寫直達(dá)法：CPU每次寫Cache的同時，也經(jīng)寫直達(dá)通路寫入主存。這種方法要增加寫主存的時間開銷。第二章存儲系統(tǒng)拓展資源——綠色存儲綠色存儲系統(tǒng)的流行已經(jīng)成為一個不爭的事實。那么，選擇綠色存儲系統(tǒng)時，需要考慮哪些要素？綠色存儲系統(tǒng)的技術(shù)將走向哪里？衡量綠色數(shù)據(jù)中心的標(biāo)準(zhǔn)目前，如何建立一個標(biāo)準(zhǔn)、理想的綠色數(shù)據(jù)中心還沒有一個明確的定義。規(guī)劃一個理想的綠色數(shù)據(jù)中心是一個非常復(fù)雜的系統(tǒng)工程，涉及的因素較多，在沒有明確的模板、標(biāo)準(zhǔn)的情況下可以從數(shù)據(jù)中心建筑物本身和數(shù)據(jù)中心內(nèi)部設(shè)施兩個方面進(jìn)行考慮。首先要保證數(shù)據(jù)中心建筑物本身的綠色、環(huán)保，可以參考美國綠色建筑委員會（USGBC）倡議的有關(guān)能源與環(huán)境設(shè)計的標(biāo)準(zhǔn)——LEED標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)從熱島效應(yīng)、節(jié)能、再生能源、暴雨管理、建筑物再利用、建筑廢料管理、地方材料和創(chuàng)新設(shè)計等方面，給出了明確的建議和評判標(biāo)準(zhǔn)。其次，對于數(shù)據(jù)中心內(nèi)部的運行設(shè)備，可以參考Sun公司制訂的有關(guān)下一代Internet服務(wù)器的評價標(biāo)準(zhǔn)，即SWaP標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)從設(shè)備占用的空間、消耗的電力、最終提供的服務(wù)性能三個維度給出了一個簡單的評測計算公式，既SWaP=P/（S*W）。其中P為基準(zhǔn)性能測試工具獲得的測試值，S為設(shè)備在數(shù)據(jù)中心機架中占用的高度，W為服務(wù)器在基準(zhǔn)測試時的功耗。什么是綠色存儲？綠色存儲是一個系統(tǒng)設(shè)計方案，在方案的每個設(shè)計環(huán)節(jié)都以降低能耗為宗旨，該方案涉及到存儲數(shù)據(jù)的產(chǎn)品、數(shù)據(jù)存儲的技術(shù)、文件系統(tǒng)和軟件配置等多方面的因素，其最終目的是用最少的存儲容量來滿足業(yè)務(wù)的需求，從而消耗最低的能源。綠色存儲產(chǎn)品實際上在產(chǎn)品設(shè)計、開發(fā)之初就融入了一些環(huán)保、節(jié)能的理念以保障產(chǎn)品在最低的能耗下提供最佳的效率。下面將從五個方面剖析綠色存儲產(chǎn)品的一些設(shè)計特點或選擇要素，以幫助讀者在選擇存儲產(chǎn)品時進(jìn)行綜合考慮。綠色存儲產(chǎn)品的系統(tǒng)設(shè)計存儲產(chǎn)品結(jié)構(gòu)設(shè)計的合理性決定了產(chǎn)品的穩(wěn)定性、產(chǎn)品的壽命和產(chǎn)品的能耗。在評價一個產(chǎn)品是否屬于綠色存儲產(chǎn)品時，首先要觀察產(chǎn)品中各個部件設(shè)計位置的合理性，因為部件的位置直接