第1章計算機組成與體系結構

1. 計算機系統組成

計算機系統是一個硬件和軟件的綜合體，可以把它看成按功能劃分的多級層次結構。

系統軟件支持應用軟件的運行，為用戶開發應用軟件提供平臺，用戶可以使用它，但不能隨意修改它。常用的系統軟件有操作系統、語言處理程序、連接程序、診斷程序和數據庫管理系統等。

1.1. 計算機硬件的組成

硬件通常是指一切看得見，摸得到的設備實體。原始的馮?諾依曼（VonNeumann）計算機在結構上是以運算器為中心的，而發展到現在，已轉向以存儲器為中心了。圖1-1所示為計算機最基本的組成框圖。

• 控制器?？刂破魇欠治龊蛨绦兄噶畹牟考彩墙y一指揮并控制計算機各部件協調工作的中心部件，所依據的是機器指令。控制器的組成包含如下。
  • 程序計數器PC：存儲下一條要執行指令的地址；
  • 指令寄存器IR：存儲即將執行的指令；
  • 指令譯碼器ID：對指令中的操作碼字段進行分析解釋；
  • 時序部件：提供時序控制信號。
• 運算器。運算器也稱為算術邏輯單元（ArithmeticandLogicUnit，ALU），其主要功能是在控制器的控制下完成各種算術運算和邏輯運算。運算器的組成包含如下。
  • 算術邏輯單元ALU：數據的算術運算和邏輯運算；
  • 累加寄存器AC：通用寄存器，為ALU提供一個工作區，用在暫存數據；
  • 數據緩沖寄存器DR：寫內存時，暫存指令或數據；
  • 狀態條件寄存器PSW：存狀態標志與控制標志（爭議點：也有將其歸為控制器的）。
• 主存儲器。主存儲器也稱為內存儲器（通常簡稱為“內存”或“主存”）。存儲現場操作的信息與中間結果，包括機器指令和數據。
• 輔助存儲器。輔助存儲器也稱為外存儲器，通常簡稱為外存或輔存。存儲需要長期保存的各種信息。
• 輸入設備。輸入設備的任務是把人們編好的程序和原始數據送到計算機中去，并且將它們轉換成計算機內部所能識別和接受的信息方式。按輸入信息的形態可分為字符（包括漢字）輸入、圖形輸入、圖像輸入及語音輸入等。目前，常見的輸入設備有鍵盤、鼠標、掃描儀等。
• 輸出設備。輸出設備的任務是將計算機的處理結果以人或其他設備所能接受的形式送出計算機。目前，最常用的輸出設備是打印機和顯示器。有些設備既可以是輸入設備，同時也可以是輸出設備，例如，輔助存儲器、自動控制和檢測系統中使用的數模轉換裝置等。

1.2. 計算機系統結構的分類

計算機的發展經歷了電子管和晶體管時代、集成電路時代（中小規模、大規模、超大規模、甚大規模、極大規模）。目前，世界最高水平的單片集成電路芯片上所容納的元器件數量已經達到80多億個。

• 存儲程序的概念
  • “存儲程序”的概念是馮?諾依曼等人于1946年6月首先提出來的，它可以簡要地概括為以下幾點：
  • 計算機（指硬件）應由運算器、存儲器、控制器、輸入設備和輸出設備五大基本部件組成。
  • 計算機內部采用二進制來表示指令和數據。
  • 將編好的程序和原始數據事先存入存儲器中，然后再啟動計算機工作。這就是存儲程序的基本含義。馮?諾依曼對計算機世界的最大貢獻在于“存儲程序控制”概念的提出和實現。六十多年來，雖然計算機的發展速度驚人，但就其結構原理來說，目前絕大多數計算機仍建立在存儲程序概念的基礎上。通常把符合存儲程序概念的計算機統稱為馮?諾依曼型計算機。當然，現代計算機與早期計算機相比，在結構上還是有許多改進的。隨著計算機技術的不斷發展，也暴露出了馮?諾依曼型計算機的主要弱點：存儲器訪問會成為瓶頸。目前，已出現了一些突破存儲程序控制的計算機，統稱為非馮?諾依曼型計算機，例如，數據驅動的數據流計算機、需求驅動的歸約計算機和模式匹配驅動的智能計算機等。
• Flynn分類
  1966年，Michael．J．Flynn提出根據指令流、數據流的多倍性特征對計算機系統進行分類（通常稱為Flynn分類法），有關定義如下。
  • 指令流：指機器執行的指令序列；
  • 數據流：指由指令流調用的數據序列，包括輸入數據和中間結果，但不包括輸出數據。
  • Flynn根據不同的指令流-數據流組織方式，把計算機系統分成以下四類:
    • 單指令流單數據流（SingleInstructionstreamandSingleDatastream，SISD）：SISD其實就是傳統的順序執行的單處理器計算機，其指令部件每次只對一條指令進行譯碼，并只對一個操作部件分配數據。
    • 單指令流多數據流（SingleInstructionstreamandMultipleDatastream，SIMD）：SIMD以并行處理機（矩陣處理機）為代表，并行處理機包括多個重復的處理單元，由單一指令部件控制，按照同一指令流的要求為它們分配各自所需的不同數據。
    • 多指令流單數據流（MultipleInstructionstreamandSingleDatastream，MISD）：MISD具有n個處理單元，按n條不同指令的要求對同一數據流及其中間結果進行不同的處理。一個處理單元的輸出又作為另一個處理單元的輸入。這類系統實際上很少見到。有文獻把流水線看作多個指令部件，稱流水線計算機是MISD。
    • 多指令流多數據流（MultipleInstructionstreamandMultipleDatastream，MIMD）：MIMD是指能實現作業、任務、指令等各級全面并行的多機系統。如多核處理器、多處理機屬于MIMD。

1.3. 復雜指令集系統與精簡指令集系統

在計算機系統結構發展的過程中，指令系統的優化設計有兩個截然相反的方向，一個是增強指令的功能，設置一些功能復雜的指令，把一些原來由軟件實現的、常用的功能改用硬件的指令系統來實現，這種計算機系統稱為復雜指令系統計算機（ComplexInstructionSetComputer，CISC）；另一個是盡量簡化指令功能，只保留那些功能簡單，能在一個節拍內執行完成指令，較復雜的功能用一段子程序來實現，這種計算機系統稱為精簡指令系統計算機（ReducedInstructionSetComputer，RISC）。

• CISC指令系統的特點
  CISC指令系統的主要特點如下：

  • 指令數量眾多。指令系統擁有大量的指令，通常有100～250條。
  • 指令使用頻率相差懸殊。最常使用的是一些比較簡單的指令，僅占指令總數的20%，但在程序中出現的頻率卻占80%。而大部分復雜指令卻很少使用。
  • 支持很多種尋址方式。支持的尋址方式通常為5～20種。
  • 變長的指令。指令長度不是固定的，變長的指令增加指令譯碼電路的復雜性。
  • 指令可以對主存單元中的數據直接進行處理。典型的CISC通常都有指令能夠直接對主存單元中的數據進行處理，其執行速度較慢。
  • 以微程序控制為主。CISC的指令系統很復雜，難以用硬布線邏輯（組合邏輯）電路實現控制器，通常采用微程序控制。

• RISC指令系統的特點
  RISC要求指令系統簡化，操作在單周期內完成，指令格式力求一致，尋址方式盡可能減少，并提高編譯的效率，最終到加快機器處理速度的目的。RISC指令系統的主要特點
  如下。

  • 指令數量少。優先選取使用頻率最高的一些簡單指令和一些常用指令，避免使用復雜指令。只提供了LOAD（從存儲器中讀數）和STORE（把數據寫入存儲器）兩條指令對存儲器操作，其余所有的操作都在CPU的寄存器之間進行。
  • 指令的尋址方式少。通常只支持寄存器尋址方式、立即數尋址方式和相對尋址方式。
  • 指令長度固定，指令格式種類少。因為RISC指令數量少、格式少、相對簡單，其指令長度固定，指令之間各字段的劃分比較一致，譯碼相對容易。
  • 以硬布線邏輯控制為主。為了提高操作的執行速度，通常采用硬布線邏輯（組合邏輯）來構建控制器。
  • 單周期指令執行，采用流水線技術。因為簡化了指令系統，很容易利用流水線技術，使得大部分指令都能在一個機器周期內完成。少數指令可能會需要多周期，例如，LOAD/STORE指令因為需要訪問存儲器，其執行時間就會長一些。
  • 優化的編譯器：RISC的精簡指令集使編譯工作簡單化。因為指令長度固定、格式少、尋址方式少，編譯時不必在具有相似功能的許多指令中進行選擇，也不必為尋址方式的選擇而費心，同時易于實現優化，從而可以生成高效率執行的機器代碼。
  • CPU中的通用寄存器數量多，一般在32個以上，有的可達上千個。大多數RISC采用了Cache方案，使用Cache來提高取指令的速度。而且，有的RISC使用兩個獨立的Cache來改善性能。一個稱為指令Cache，另一個稱為數據Cache。這樣，取指令和取數據可以同時進行，互不干擾。

1.4. 總線

總線是一組能為多個部件分時共享的公共信息傳送線路。共享是指總線上可以掛接多個部件，各個部件之間相互交換的信息都可以通過這組公共線路傳送；分時是指同一時刻只允許有一個部件向總線發送信息，如果出現兩個或兩個以上部件同時向總線發送信息，勢必導致信號沖突。當然，在同一時刻，允許多個部件同時從總線上接收相同的信息。

按總線相對于CPU或其他芯片的位置可分為內部總線和外部總線兩種。在CPU內部，寄存器之間和算術邏輯部件ALU與控制部件之間傳輸數據所用的總線稱為內部總線；外部總線是指CPU與內存RAM、ROM和輸入/輸出設備接口之間進行通信的通路。由于CPU通過總線實現程序取指令、內存/外設的數據交換，在CPU與外設一定的情況下，總線速度是制約計算機整體性能的最大因素。

按總線功能來劃分，又可分為地址總線、數據總線、控制總線三類，人們通常所說的總線都包括這三個組成部分，地址總線用來傳送地址信息，數據總線用來傳送數據信息，控制
總線用來傳送各種控制信號。

2. 存儲器系統

存儲器是用來存放程序和數據的部件，它是一個記憶裝置，也是計算機能夠實現“存儲程序控制”的基礎。在計算機系統中，規模較大的存儲器往往分成若干級，稱為存儲器系統。

傳統的存儲器系統一般分為高速緩沖存儲器（Cache）、主存、輔存三級。主存可由CPU直接訪問，存取速度快，但容量較小，一般用來存放當前正在執行的程序和數據。輔存設置在主機外部，它的存儲容量大，價格較低，但存取速度較慢，一般用來存放暫時不參與運行的程序和數據，CPU不可以直接訪問輔存，輔存中的程序和數據在需要時才傳送到主存，因此它是主存的補充和后援。當CPU速度很高時，為了使訪問存儲器的速度能與CPU的速度相匹配，又在主存和CPU間增設了一級Cache。Cache的存取速度比主存更快，但容量更小，用來存放當前最急需處理的程序和數據，以便快速地向CPU提供指令和數據。因此，計算機采用多級存儲器體系，確保能夠獲得盡可能高的存取速率，同時保持較低的成本。

多層級的存儲體系之所以能用低投入換來較高的存取速率，得益于局部性原理。局部性原理是指程序在執行時呈現出局部性規律，即在一較短的時間內，程序的執行僅局限于某個部分。相應地，它所訪問的存儲空間也僅局限于某個區域。程序局部性包括時間局部性和空間局部性，時間局部性是指程序中的某條指令一旦執行，不久以后該指令可能再次執行。產生時間局部性的典型原因是由于程序中存在著大量的循環操作；空間局部性是指一旦程序訪問了某個存儲單元，不久以后，其附近的存儲單元也將被訪問，即程序在一段時間內所訪問的地址可能集中在一定的范圍內，其典型情況是程序順序執行。

存儲器中數據常用的存取方式有順序存取、直接存取、隨機存取和相聯存取四種。

• 順序存?。捍鎯ζ鞯臄祿杂涗浀男问竭M行組織。對數據的訪問必須按特定的線性順序進行。磁帶存儲器采用順序存取的方式。
• 直接存?。号c順序存取相似，直接存取也使用一個共享的讀寫裝置對所有的數據進行訪問。但是，每個數據塊都擁有唯一的地址標識，讀寫裝置可以直接移動到目的數據塊所在位置進行訪問。存取時間也是可變的。磁盤存儲器采用直接存取的方式。
• 隨機存取：存儲器的每一個可尋址單元都具有自己唯一的地址和讀寫裝置，系統可以在相同的時間內對任意一個存儲單元的數據進行訪問，而與先前的訪問序列無關。主存儲器采用隨機存取的方式。
• 相聯存?。合嗦摯嫒∫彩且环N隨機存取的形式，但是選擇某一單元進行讀寫是取決于其內容而不是其地址。與普通的隨機存取方式一樣，每個單元都有自己的讀寫裝置，讀寫時間也是一個常數。使用相聯存取方式，可以對所有的存儲單元的特定位進行比較，選擇符合條件的單元進行訪問。為了提高地址映射的速度，Cache采取相聯存取的方式。

2.1. 主存儲器

主存用來存放計算機運行期間所需要的程序和數據，CPU可直接隨機地進行讀/寫。主存具有一定容量，存取速度較高。由于CPU要頻繁地訪問主存，所以主存的性能在很大程度上影響了整個計算機系統的性能。根據工藝和技術不同，主存可分為隨機存取存儲器和只讀存儲器。

• 隨機存取存儲器

  隨機存取存儲器（RandomAccessMemory，RAM）既可以寫入也可以讀出，但斷電后信息無法保存，因此只能用于暫存數據。RAM又可分為DRAM（DynamicRAM，動態RAM）和SRAM（StaticRAM，靜態RAM）兩種，DRAM的信息會隨時間逐漸消失，因此需要定時對其進行刷新維持信息不丟失；SRAM在不斷電的情況下信息能夠一直保持而不會丟失。DRAM的密度大于SRAM且更加便宜，但SRAM速度快，電路簡單（不需要刷新電路），然而容量小，價格高。

• 只讀存儲器

  只讀存儲器（ReadOnlyMemory，ROM）可以看作RAM的一種特殊形式，其特點是：存儲器的內容只能隨機讀出而不能寫入。這類存儲器常用來存放那些不需要改變的信息。由于信息一旦寫入存儲器就固定不變了，即使斷電，寫入的內容也不會丟失，所以又稱為固定存儲器。ROM一般用于存放系統程序BIOS（BasicInputOutputSystem，基本輸入輸出系統）。

• 內存編址方法在計算機系統中，存儲器中每個單元的位數是相同且固定的，稱為存儲器編址單位。

  不同的計算機，存儲器編址的方式不同，主要有字編址和字節編址。
  內存一般以字節（8位）為單位，或者以字為單位（字的長度可大可小，例如16位或者32位等，在這類試題中，一般會給出字的大?。?br> 例如，內存地址從AC000H到C7FFFH，則共有C7FFFFH-AC000H=1BFFFH個地址單元（轉換為十進制后，為112KB）。如果該內存地址按字（16bit）編址，則共有112KB - 16位。假設該內存由28片存儲器芯片構成，已知構成此內存的芯片每片有16KB個存儲單元，則該芯片每個存儲單元存儲（112KB-16）/（28-16KB）=4位。

2.2. 輔助存儲器

• 磁帶存儲器磁帶存儲器是一種順序存取的設備，其特點包括：存取時間較長，但存儲容量大，便于攜帶，價格便宜。磁帶應用的場景越來越少，目前主要用于資料的歸檔保存。

• 硬盤存儲器在硬盤中，信息分布呈以下層次：記錄面、圓柱面、磁道和扇區，如圖1-2所示。
  

  一臺硬盤驅動器中有多個磁盤片，每個盤片有兩個記錄面，每個記錄面對應一個磁頭，所以記錄面號就是磁頭號，如圖1-2（a）所示。所有的磁頭安裝在一個公用的傳動設備或支架上，磁頭一致地沿盤面徑向移動，單個磁頭不能單獨地移動。在記錄面上，一條條磁道形成一組同心圓，最外圈的磁道為0號，往內則磁道號逐步增加，如圖1-2（b）所示。在一個盤組中，各記錄面上相同編號（位置）的各磁道構成一個柱面，如圖1-2（c）所示。

  若每個磁盤片有m個磁道，則該硬盤共有m個柱面。引入柱面的概念是為了提高硬盤的存儲速度。當主機要存入一個較大的文件時，若一條磁道存不完，就需要存放在幾條磁道上。這時，應首先將一個文件盡可能地存放在同一柱面中。如果仍存放不完，再存入相鄰的柱面內。

  通常將一條磁道劃分為若干個段，每個段稱為一個扇區或扇段，每個扇區存放一個定長信息塊（例如，512個字節），如圖1-2（b）所示。一條磁道劃分多少扇區，每個扇區可存放多少字節，一般由操作系統決定。磁道上的扇區編號從1開始，不像磁頭或柱面編號從0開始。

  在磁盤上進行信息的讀寫時，首先需要定位到目標磁道，這個過程稱之為尋道，尋道所消耗的時間稱為尋道時間，定位到目標磁道后，需要定位到目標扇區，此過程通過旋轉盤片完成，平均旋轉半圈可到目標位置。故磁盤訪問時間為：
  磁盤訪問時間（存取時間)=尋道時間+旋轉延遲時間

2.3. Cache存儲器

Cache的功能是提高CPU數據輸入輸出的速率，突破所謂的“馮?諾依曼瓶頸”，即CPU與存儲系統間數據傳送帶寬限制。高速存儲器能以極高的速率進行數據訪問，但因其價格高昂，如果計算機的內存完全由這種高速存儲器組成，則會大大增加計算機的成本。通常在CPU和內存之間設置小容量的Cache。Cache容量小但速度快，內存速度較低但容量大，通過優化調度算法，系統的性能會大大改善，仿佛其存儲系統容量與內存相當而訪問速度近似Cache。

Cache通常采用相聯存儲器（ContentAddressableMemory，CAM）。CAM是一種基于數據內容進行訪問的存儲設備。當對其寫入數據時，CAM能夠自動選擇一個未用的空單元進行存儲；當要讀出數據時，不是給出其存儲單元的地址，而是直接給出該數據或者該數據的一部分內容，CAM對所有存儲單元中的數據同時進行比較，并標記符合條件的所有數據以供讀取。由于比較是同時、并行進行的，所以，這種基于數據內容進行讀寫的機制，其速度比基于地址進行讀寫的方式要快很多。

• Cache基本原理

  使用Cache改善系統性能的依據是程序的局部性原理。根據程序的局部性原理，最近的、未來要用的指令和數據大多局限于正在用的指令和數據，或是存放在與這些指令和數據位置上鄰近的單元中。這樣，就可以把目前常用或將要用到的信息預先放在Cache中。當CPU需要讀取數據時，首先在Cache中查找是否有所需內容，如果有，則直接從Cache中讀??；若沒有，再從內存中讀取該數據，然后同時送往CPU和Cache。如果CPU需要訪問的內容大多都能在Cache中找到（稱為訪問命中），則可以大大提高系統性能。

  如果以h代表對Cache的訪問命中率（“1-h”稱為失效率，或者稱為未命中率），t1表示cache的周期時間，t2表示內存的周期時間，以讀操作為例，使用“Cache+主存儲器”的系統的平均周期為t3。則：t3=t1′h+t2′(1-h)

  系統的平均存儲周期與命中率有很密切的關系，命中率的提高即使很小也能導致性能上的較大改善。

  例如，設某計算機主存的讀/寫時間為l00ns，有一個指令和數據合一的Cache，已知該Cache的讀/寫時間為10ns，取指令的命中率為98%，取數的命中率為95%。在執行某類程序時，約有1/5指令需要存/取一個操作數。假設指令流水線在任何時候都不阻塞，則設置Cache后，每條指令的平均訪存時間約為：(2%′100ns+98%′10ns)+1/5′(5%′100ns+95%′10ns)=14.7ns

• 映射機制

  當CPU發出訪存請求后，存儲器地址先被送到Cache控制器以確定所需數據是否已在Cache中，若命中則直接對Cache進行訪問。這個過程稱為Cache的地址映射（映像）。在Cache的地址映射中，主存和Cache將均分成容量相同的塊（頁）。常見的映射方法有直接映射、全相聯映射和組相聯映射。

  • 直接映像

    直接映像方式以隨機存取存儲器作為Cache存儲器，硬件電路較簡單。在進行映像時，主存地址被分成三個部分，從高到低依次為：區號、頁號以及頁內地址，如圖1-3所示。
    

    在本例中，內存容量為1GB，Cache容量為8MB，頁面的大小為512KB。直接映像中，先分區，再分頁。一個區的大小就是Cache容量的大小，所以一共分：1GB/8MB=128個區，區號7位。每個區分：8MB/512KB=16個頁，所以頁號為4位。

    在直接映像方式中，每個主存頁只能復制到某一固定的Cache頁中，如圖1-4所示。直接映像方式的映像規律是：主存中每個區的第0頁，只能進入到Cache的第0頁。即：若當前時刻Cache中0號頁已被占據，而1-15號頁空閑，現在要將1區第0頁（即內存的16頁）調入Cache是會發生沖突的。所以直接映像的塊沖突率非常高。

    在Cache中，為每一個頁設立一個Cache標記，該標記用于識別當前的Cache塊來自于哪個內存頁。直接映像中，由于每個區的N號頁，都必須進入到Cache的N號頁，所以只需要記錄區號即可。所以此時標記位的長度是7位。

    直接映像方式的優點是比較容易實現，缺點是不夠靈活，有可能使Cache的存儲空間得不到充分利用。

  • 全相聯映像

    全相聯映像使用相聯存儲器組成的Cache存儲器。在全相聯映像方式中，主存的每一頁可以映像到Cache的任一頁。如果淘汰Cache中某一頁的內容，則可調入任一主存頁的內容，因而較直接映像方式靈活。

    在全相聯映像方式中，主存地址分為兩個部分，分別為地址部分（主存頁標記）和數據部分（頁內地址）。數據部分用于存放數據，而地址部分則存放該數據的存儲器地址。如圖1-5所示。

    全相聯映像方式的Cache組織如圖1-6所示。

    當進行映像時，在我們給定的例子中，當程序訪存時，則高11位給出主存頁號，低19位給出頁內地址。因為每個Cache頁可映像到2048個主存頁中的任一頁，所以每頁的Cache標記也需要11位，以表明它現在所映像的主存頁號。因此，Cache標記信息位數增加，比較邏輯成本隨之增加。

    在全相聯映像方式中，主存地址不能直接提取Cache頁號，而是需要將主存頁標記與Cache各頁的標記逐個比較，直到找到標記符合的頁（訪問Cache命中），或者全部比較完后仍無符合的標記（訪問Cache失敗）。因此這種映像方式速度很慢，失掉了高速緩存的作用，這是全相聯映像方式的最大缺點。如果讓主存頁標記與各Cache標記同時比較，則成本又太高。全相聯映像方式因比較器電路難于設計和實現，只適用于小容量Cache。

  • 組相聯映

    組相聯映像（頁組映像）介于直接映像和全相聯映像之間，是這兩種映像的一種折衷方案。全相聯映像方式以頁為單位，可自由映像，沒有固定的對應關系。直接映像方式中，主存分組，主存組內的各頁與Cache的頁之間采取的是固定的映像關系，但各組均可映像到

    Cache中。在組相聯映像方式中，主存與Cache都分組，主存中一個組內的頁數與Cache的分組數相同，如圖1-7所示。

    在圖1-7給出的例子中，主存分128個區，每個區8個組，每個組2個頁。組相聯映像方式的主存地址組織如圖1-8所示。

    組相聯映像的規則是：主存中的組與Cache的組形成直接映像關系，而每個組內的頁是全相聯映像關系。如主存1區0頁，他在0組中，所以只能進入Cache的0組中，至于進入到Cache的0組0頁，還是0組1頁，并無強制要求，可任意放置。

    在組相聯映像中，Cache中每一頁的標記位長度為8位，因為此時除了要記錄區號，還得記錄組號，即區號7位加組號1位等于8位。

    容易看出，如果Cache中每組只有一頁，則組相聯映像方式就變成了直接映像方式。如果Cache中每組頁數為16頁（即Cache只分一組），則就是全相聯映像。因此，在具體設計組相聯映像時，可以根據設計目標選取某一折衷值。

    在組相聯映像中，由于Cache中每組有若干可供選擇的頁，因而它在映像定位方面較直接映像方式靈活；每組頁數有限，因此付出的代價不是很大，可以根據設計目標選擇組內頁數。

• 替換算法

  當Cache產生了一次訪問未命中之后，相應的數據應同時讀入CPU和Cache。但是當Cache已存滿數據后，新數據必須替換（淘汰）Cache中的某些舊數據。最常用的替換算法有以下三種：

  • 隨機算法。這是最簡單的替換算法。隨機法完全不管Cache塊過去、現在及將來的使用情況，簡單地根據一個隨機數，選擇一塊替換掉。
  • 先進先出（FirstInandFirstOut，FIFO）算法。按調入Cache的先后決定淘汰的順序，即在需要更新時，將最先進入Cache的塊作為被替換的塊。這種方法要求為每塊做一記錄，記下它們進入Cache的先后次序。這種方法容易實現，而且系統開銷小。其缺點是可能會把一些需要經常使用的程序塊（如循環程序）替換掉。
  • 近期最少使用（LeastRecentlyUsed，LRU）算法。LRU算法是把CPU近期最少使用的塊作為被替換的塊。這種替換方法需要隨時記錄Cache中各塊的使用情況，以便確定哪個塊是近期最少使用的塊。LRU算法相對合理，但實現起來比較復雜，系統開銷較大。通常需要對每一塊設置一個稱為“年齡計數器”的硬件或軟件計數器，用以記錄其被使用的情況。

• 寫操作

  因為需要保證緩存在Cache中的數據與內存中的內容一致，相對讀操作而言，Cache的寫操作比較復雜，常用的有以下幾種方法。

  • 寫直達（writethrough）。當要寫Cache時，數據同時寫回內存，有時也稱為寫通。當某一塊需要替換時，也不必把這一塊寫回到主存中去，新調入的塊可以立即把這一塊覆蓋掉。這種方法實現簡單，而且能隨時保持主存數據的正確性，但可能增加多次不必要的主存寫入，會降低存取速度。
  • 寫回（writeback）。CPU修改Cache的某一塊后，相應的數據并不立即寫入內存單元，而是當該塊從cache中被淘汰時，才把數據寫回到內存中。在采用這種更新策略的cache塊表中，一般有一個標志位，當一塊中的任何一個單元被修改時，標志位被置“1”。在需要替換掉這一塊時，如果標志位為“1”，則必須先把這一塊寫回到主存中去之后，才能再調入新的塊；如果標志位為“0”，則這一塊不必寫回主存，只要用新調入的塊覆蓋掉這一塊即可。這種方法的優點是操作速度快，缺點是因主存中的字塊未隨時修改而有可能出錯。
  • 標記法。對Cache中的每一個數據設置一個有效位。當數據進入Cache后，有效位置“1”；而當CPU要對該數據進行修改時，數據只需寫入內存并同時將該有效位置“0”。當要從Cache中讀取數據時需要測試其有效位，若為“l”則直接從Cache中取數，否則，從內存中取數。

3. 流水線

流水線技術把一個任務分解為若干順序執行的子任務，不同的子任務由不同的執行機構 負責執行，而這些機構可以同時并行工作。在任一時刻，任一任務只占用其中一個執行機構，這樣就可以實現多個任務的重疊執行，以提高工作效率。

3.1. 流水線周期

流水線應用過程中，會將需要處理的工作分為 N 個階段，最耗時的那一段所消耗的時 間為流水線周期。如：使用流水線技術執行 100 條指令，每條指令取指 2ms，分析 4ms，執行 1ms，則流水線周期為 4ms。

3.2. 計算流水線執行時間

延續上面的場景，將 1 個任務的執行過程可分成 N 個階段， 假設每個階段完成時間 為 t，則完成該任務所需的時間即為 Nt。若以傳統的方式，則完成 k 個任務所需的時間是 kNt；而使用流水線技術執行， 且花費的時間是 Nt+(k-1)t。也就是說， 除了第 1 個任務需要 完整的時間外，其他都通過并行，節省下了大量的時間。所以流水線的執行時間可通俗的表達為：流水線執行時間=第 1 條指令的執行時間+（n-1）流水線周期
注：n代表需要處理的任務數量。

在考試時，又需要特別注意一個細節問題，流水線的執行時間計算，其實進一步可以分理論情況與實踐情況兩種不同的處理方式。下面以實例進行說明。
例：某計算機系統， 一條指令的執行需要經歷取指（2ms）、分析（4ms）、執行（1ms）三個階段， 現要執行 100 條指令，利用流水線技術需要多長時間?

理論上來說，1 條指令的執行時間為：2ms+4ms+1ms=7ms。所以： 理論流水線執行時間=2ms+4ms+1ms+(100-1)4=403ms。

而實際上，真正做流水線處理時，考慮到處理的復雜性，會將指令的每個執行階段的時 間都統一為流水線周期， 即 1 條指令的執行時間為：4ms+4ms+4ms=12ms 。 所以： 實際流水線執行時間=4ms+4ms+4ms+(100-1)-4=408ms。

3.3. 流水線的吞吐率

流水線的吞吐率（Though Put rate ，TP）是指在單位時間內流水線所完成的任務數量或 輸出的結果數量。有些文獻也稱為平均吞吐率、實際吞吐率。計算流水線吞吐率的最基本的公式如下：

3.4. 流水線的加速比

在流水線中，因為在同一時刻，有多個任務在重疊地執行，雖然完成一個任務的時間與單獨執行該任務相近（甚至由于分段的緣故，可能更多一些），但是從整體上看完成多個任務所需的時間則大大減少。

完成同樣一批任務，不使用流水線所用的時間與使用流水線所用的時間之比稱為流水線 的加速比（speedup ratio）。如果不使用流水線，即順序執行所用的時間為T0，使用流水線的執行時間為Tk，則計算流水線加速比的基本公式如下：

如果流水線各個流水段的執行時間都相等（設為Dt），則一條k段流水線完成n個連續任務所需要的時間為(k+n-1)Dt。如果不使用流水線，即順序執行這n個任務，則所需要的時間為nkDt。因此，各個流水段執行時間均相等的一條k段流水線完成n個連續任務時的實際加速比為

源文來自：https://daimajiangxin.cn/