第4章存儲系統計算機組成原理2007.7.21計算機組成原理第4章存儲系統本章介紹了計算機中各種常見存儲器芯片的結構和工作原理，以及當存儲器芯片不滿足系統需求時，如何對存儲器進行擴展，采用何種方式對存儲器進行管理以提高存儲空間的利用率。2007.7.22計算機組成原理本章要點：存儲器分類及其工作原理芯片擴展方法存儲空間管理方法2007.7.23計算機組成原理

4.1計算機存儲系統組織方式

隨著計算機和網絡技術的發展，人們對計算機的要求逐漸提高，從最開始只需要計算機代替人進行計算，逐漸過渡到要求計算機系統能長時間保存大量信息，并且方便用戶進行異地查詢。為了滿足人們對各類信息的查詢要求，現在的計算機必須要配備容量較大的存儲系統。但是計算機存儲系統，特別是磁盤存儲系統，自身存在很難克服的缺陷，如讀取速度慢、尋道時間長等。然而，盡管存儲器速度提升緩慢，處理器的處理能力卻在快速提高。這就造成了新的矛盾，存儲器的數據傳輸速度遠遠小于處理器處理數據的速度，使得存儲器的性能成為計算機系統性能的瓶頸。2007.7.24計算機組成原理基于以上原因，計算機中配置存儲器時，需要考慮兩方面的問題：（1）如何利用有限的存儲空間盡可能多地存儲數據、方便快捷地讀出數據。（2）如何將慢速的磁盤存儲器和快速的處理器匹配起來。第1個問題的解決方法，我們將在4.5節中詳細介紹。下面簡單介紹第2個問題的解決方法。

為了同時滿足用戶對容量和速度的要求，計算機系統往往會采用以下的存儲器配置方法，如圖4-1所示。2007.7.25計算機組成原理2007.7.26計算機組成原理大容量磁盤存儲器處于存儲系統的最底層，其主要作用是給計算機系統提供一個較大的存儲容量，因此，對它的要求主要是存儲容量要盡可能大。在計算機中配置了磁盤存儲器后已經解決了容量問題，為什么還要加內存呢？原因在于匹配CPU和磁盤的速度。從前面的分析我們可以知道，計算機中，CPU的處理速度比磁盤的讀寫速度快得多，如果不進行速度匹配，則會出現CPU長時間等待磁盤輸入數據的情況，從而降低CPU利用率，影響系統性能。內存的讀寫速度比CPU的速度慢，但是比磁盤快，剛好可以起到速度匹配的作用，同時，因為內存解決的主要問題不是容量問題，所以對其容量的要求不是特別高。2007.7.27計算機組成原理寄存器和Cache都是CPU中的存儲器，但是二者作用卻不完全相同。寄存器的讀寫速度最快，主要用于直接提供CPU計算所需要的數據；Cache，又叫高速緩存，作用與內存相似，主要用于匹配相對低速的內存和高速的寄存器。由此可見，二者對速度的要求都很高，而對容量的要求則較小。基于以上的原因，目前市場上的主流磁盤容量都在160G以上，內存的容量大都是512M或1G，而Cache的容量則在1M左右。思考：聯系實際，一臺微型計算機存儲系統包含那些部件？它們分別存在于計算機那些地方？作用是什么？

2007.7.28計算機組成原理4.2半導體存儲器芯片介紹

目前，幾乎所有的存儲器都是用半導體材料做成的。但是根據存儲器的使用特性可以將存儲器分為兩類：隨機存取存儲器（RandomAccessMemory，RAM）和只讀存儲器（Read-OnlyMemory，ROM）。只讀存儲器跟隨機存儲器不同，用戶在使用時只能讀取其中的數據，如果要對ROM中的數據進行修改，則必須采用特殊的方法進行，因此ROM可以用于保存不需要經常改變的程序和數據，如：設備驅動程序等。同時，ROM有掉電保護功能，可用于制造磁盤等能長時間保存信息且不受斷電影響的存儲器。常用ROM有以下五類：2007.7.29計算機組成原理掩模式（Masked）ROM：該種ROM不允許用戶對其修改。可編程ROM（ProgrammableROM，PROM）：該種ROM允許用戶對其進行一次修改，一旦程序或數據寫入則不允許用戶再次修改。可擦除PROM（ErasablePROM，EPROM）：該種ROM允許用戶在第一次寫入數據后再次進行修改，但是修改時必須先用紫外光擦除原來的數據。電可擦除PROM（Electrically

ErasableROM，EEPROM又叫E2PROM）：該種存儲器與PROM一樣可以對數據進行多次修改，但是不同的是E2PROM不需要紫外光擦除，而是采用加電的方式進行擦除。閃存（Flash

memory）。閃存是電可擦除只讀存儲器（EEPROM）的變種，所不同的是，閃存的刪除寫入是以字節為單位，而EEPROM是以整塊芯片為單位。現在的U盤、MP3和MP4等都使用的是閃存。2007.7.210計算機組成原理4.2.1SRAM芯片的結構和工作原理1．內部存儲單元SRAM的一個存儲單元可以用來保存一位數據，即可保存一個“0”或一個“1”。電路如圖4-2所示。圖4-2SRAM內部存儲單元電路中使用的T1、T2、T3、T4均是NMOS管。X是單元行地址選擇線，Y是單元列地址選擇線。作為存儲單元電路,該電路至少應該有保持、寫入和讀出三種狀態。2007.7.211計算機組成原理（1）保持圖中T1、T2、T3、T4能構成一個雙穩態電路。T1和T2在某一時刻只能有一個處于導通狀態。當T1截止、T2導通時，節點A處于高電平狀態，節點B處于低電平狀態。A的高電平可以保證T2持續導通，B的低電平可以保證T1持續截止。反之亦然。如果沒有外界因素的影響，該電路的狀態將長時間保持。所以，SRAM不需要經常刷新。約定：T1截止、T2導通時表示該單元電路狀態為“1”，T1導通、T2截止時表示該單元電路狀態為“0”。從以上分析可以看出，A點的狀態即為單元電路保存的信息狀態，A為高電平時，單元信息為“1”，A為低電平時，單元信息為“0”。因此，讀出時，只需要讀出A點的狀態即可。2007.7.212計算機組成原理（2）寫入要對此單元進行寫入操作，要選中該單元，并且要將數據放在數據線上。選中時，該單元的行選擇線X和列選擇線Y都處于高電平狀態，X、Y的高電平，使得T5~T8全部導通。如果待寫入的數據是“0”，則I/0數據線被置為低電平，數據線被置為高電平，不管A、B之前的狀態如何，此時A點將被強制置為低電平，B點將被強制置為高電平，進而使得T1導通而T2截止。反之如果待寫入數據為“1”，使得T1截止而T2導通。2007.7.213計算機組成原理（3）讀出跟寫入一樣，讀出單元數據時，也要先選中該電源。不同的是，此時往數據線上放數據。選中時，該單元的行選擇線X和列選擇線Y都處于高電平狀態，X、Y的高電平，使得T5~T8全部導通。I/O數據線直接與A點相連，A兩點的狀態將通過數據線輸出。2007.7.214計算機組成原理4.2.2DRAM芯片的結構和工作原理相對于SRAM來說，DRAM具有容易集成、位價格低、容量大和功耗低等優點，但是由于受到器件的限制，DRAM的存取速度比SRAM慢，而且需要定時刷新。1．內部存儲單元跟SRAM一樣，DRAM的一個存儲單元也可以用來保存一位數據，即可保存一個“0”或一個“1”。常見的DRAM的基本存儲電路可以分為多管型和單管型，下面以單管型為例介紹電路原理。單管型存儲單元如圖4-4所示。2007.7.215計算機組成原理電路中的電容C和NMOS管T是電路的核心器件。單元存儲的信息是通過電容的高低電壓來表示的。電容充電后的高電位表示“1”，放電后的低電位表示“0”，讀出時只要能讀出C的電位即可。T管的柵極接行選擇信號，源極通過T2接數據線，其作用是控制對C的充電。當T管導通時，源極電位與電容電位相同。對單元電路的寫入、讀出和保持這三個基本操作的基本原理如下：2007.7.216計算機組成原理（1）寫入要對單元進行寫入，行列選擇信號必須有效，且待寫入數據需要放在數據線上。此時T1、T2導通，數據線與源極相連，而源極電位與電容電位相同，因此，數據線上的電位將強制修改電容的電位，從而完成寫入操作。（2）讀出該單元的行列選擇地址有效時，T1、T2導通，所以電容電位的高低能通過數據線輸出。（3）保持單元電路是通過C的高低電位表示信息，然而電容的電壓不能長時間保持，如果不定期對C的數據進行刷新，則其保存的信息“1”經過一段時間后將會變為“0”導致數據丟失。通常每1～2ms就需要對其狀態進行一次刷新。2007.7.217計算機組成原理2．典型芯片的工作原理下面我們以Intel2164A芯片為例介紹DRAM芯片的工作過程。（1）芯片簡介Intel2164A芯片存儲容量為64K×1位、最大存取時間為200ns、刷新時間間隔為2ms，采用雙列直插式封裝，有16個引腳，其引腳圖如圖4-5所示。各引腳功能：：行地址選通信號，用于鎖存行地址,低電平有效，兼作芯片選擇信號。為低電平時，表明芯片當前接收的是行地址；：列地址選通信號；地址總線上先送上行地址，后送上列地址，它們分別在RAS和CAS有效期間被鎖存芯片中。A0～A7：地址線；用來分時接收CPU送來的8位行、列地址；DIN：數據輸入；DOUT：數據輸出；NC：未用引腳;VCC：+5V電源引腳；GND：接地引腳；：讀寫允許控制信號輸入引腳，當其為低電平時，執行寫操作；否則，執行讀操作。2007.7.218計算機組成原理（2）工作原理2164A有64K×1位的存儲空間，需要16位地址線才能尋址，由于其存儲單元采用矩陣的方式設置，我們只要知道某個存儲單元的行列地址就可以對該單元進行讀寫，所以芯片16位地址線又可以分成8位行地址線和8為列地址線，為了節約成本和減少芯片引腳數量，芯片只用了8位地址線，采用分時的方式分別傳送行地址和列地址。傳送地址時，先傳送8位行地址，后傳送8位列地址。為了區別行列地址，芯片設置了兩個低電平有效的引腳（RowAddressStrobe）和（ColumnAddressStrobe）分別作為行地址選通信號和列地址選通信號。當信號為低電平時，把此時地址線上的8位地址信號送至內部的行地址鎖存器，同理當信號為低電平時，把此時地址線上的8位地址信號送至內部的列地址鎖存器。2007.7.219計算機組成原理與6116不同，2164A的輸入輸出數據線使用了不同的引腳，在實際使用時，常將這兩位數據線與數據總線的同一位相連。為了保證正確的接收數據和輸出數據，芯片設置了讀寫允許控制信號輸入引腳。當＝0時，芯片接收數據，并根據行列地址信號將此數據寫入到相應的存儲單元；當＝1時，芯片根據行列地址信號讀出相應的存儲單元的數據，并且輸出到數據總線上。2007.7.220計算機組成原理4.2.3ROM的結構和原理下面，我們以EPROM的典型芯片Intel2716為例介紹ROM芯片的工作原理。1．內部存儲單元EPROM的基本電路如圖4-6所示，其核心器件是浮置柵雪崩注入型場效管（FloatinggridAvalancheinjection，FAMOS）。圖4-6EPROM內部存儲單元在沒有被寫入數據前，FAMOS管的柵極沒有電子，源漏極間沒有形成導電溝道，不導通，此時保存的信息為“1”。對其進行寫入操作后，其柵極上被注入電子，源漏極間形成導電溝道，管子導通，此時保存的信息為“0”。2007.7.221計算機組成原理2．典型芯片的工作原理（1）芯片簡介Intel2716是容量為2K×8位，讀出時間在350ns～450ns，有24個引腳，采用雙列直插式封裝的芯片。芯片引腳圖如圖4-7所示。各引腳功能如下：Al0～A0：地址信號輸入引腳，可尋址芯片的2K個存儲單元；O7～O0：雙向數據信號輸入輸出引腳；：片選信號輸入引腳，低電平有效，只有當該引腳轉入低電平時，才能對相應的芯片進行操作；：數據輸出允許控制信號引腳，低電平時允許數據輸出；Vcc：+5V電源；VPP：+25V/+5V電源，用于在專用裝置上進行寫操作；GND：接地引腳。2007.7.222計算機組成原理（2）工作原理芯片有兩個電源輸入引腳VCC和VPP。引腳VCC作為芯片電源引腳，一直接高電平，即VCC＝1。引腳VPP用以控制是否對芯片進行寫操作。當VPP＝+5V時，不允許對寫芯片，但是當VPP＝+25V時，能對芯片讀操作也能進行寫操作。其工作原理如下：當VPP＝+5V、且時，允許對讀芯片，芯片將地址信號所指定的單元的信息放到輸出數據線O7～O0上；當VPP＝+5V、時，無論狀態如何，芯片都將進入保持狀態，此時不能對芯片進行讀寫，輸出數據線呈高阻狀態；當VPP＝+25V、為持續50ms的高電平、時，數據線上的信息將被寫入到地址信息確定的單元里，此時芯片處于編程寫入狀態，數據線處于輸入狀態；編程完成后，需要驗證寫入芯片的數據是否正確，因此，Intel2176芯片還能提供程序校驗功能，即當VPP＝+25V、、時，能對芯片內的存儲單元進行讀操作，根據讀出的數據判斷寫入的程序是否正確；當VPP＝+25V、、時，不允許寫芯片，此時數據線又將呈高阻狀態。2007.7.223計算機組成原理4.2.4相聯存儲器相聯存儲器（associative

memory）是一種根據存儲內容來進行存取的存儲器，也稱為按內容訪問存儲器（content

addressed

memory）。它跟一般的存儲器不同，一般存儲器進行讀寫時，需要控制芯片提供讀寫的單元地址，而相聯存儲器則是按順序寫入，根據需要讀取的內容讀出。嚴格地說，相聯存儲器是一種存取方法，而不是一種存儲器。2007.7.224計算機組成原理任何一個記錄都有很多的數據項，如學生的姓名、學號、聯系方式等，每個數據項都是不完全相同的，特別是同一所學校的學生的學號是不可能重復的，因此，在對這類數據進行讀出時，選定一個數據項作為相聯關鍵字來代表要查找的對象，如學生的學號。讀出時，根據中央處理單元給出的這個相聯關鍵字，用它和存儲器中所有單元中的一部分信息進行比較，如果相等，則將此單元中余下的信息讀出。這是實現存儲器并行操作的一種有效途徑，特別適合于信息的檢索和更新。現在的大部分數據庫都是采用這種方法實現的。為了進行正確比較，存儲器必須設置一定的機構來實現比較的過程，這些機構包括：比較寄存器，屏蔽寄存器，字選擇寄存器，查找結果寄存器等。各寄存器作用如下：2007.7.225計算機組成原理（1）比較寄存器用來存放檢索字，其位數和相聯存儲器的存儲單元位數相等。（2）屏蔽寄存器用來存放屏蔽碼，其位數和檢索寄存位數相同。當按內容進行檢索時，相應地把MR中要比較的位設置成“1”，不要比較的設置成“0”。置“1”的字段為關鍵字段。（3）查找結果寄存器：位數等于相聯存儲器的存儲單元位數，每一位對應一個存儲單元，位的序數即為相聯存儲器的單元地址。若比較結果第i個字滿足要求，則將第i位置為“1”，其余的均為“0”。2007.7.226計算機組成原理（4）字選擇寄存器：位數與記錄的數據項的數量相同，用以確定哪些字參與檢索，參與檢索的則相應位為“1”，其余的為“0”。思考：目前，我們使用的那些存儲產品采用的是半導體存儲技術？2007.7.227計算機組成原理4.3主存儲系統

主存儲器主要有以下幾個性能指標：存儲容量：所謂存儲容量即存儲器能夠保存的數據的數量。常用的單位有GB、MB、KB等。1GB=1024MB,1MB=1024KB,1KB=1024B。也可以用乘積的方式表示，公式為：容量＝字數×字長如1KB可以表示為1K×8位，1MB可以表示為1M×8位等。存取速度：所謂存取速度即是單位時間內存儲器能讀寫的位數或字節數。該參數跟存儲器的時鐘頻率有關。一般情況下，時鐘頻率越高，存取速度越快。如果用位數衡量，常用單位有Kb/s、Mb/s等；如果用字節數衡量，常用單位有KB/s、MB/s等。2007.7.228計算機組成原理讀寫周期：所謂讀寫周期是指讀寫一位或一個字節所需要的時間。該參數與存取速度成反比。存取速度越快，周期越短，反之亦然。前面我們介紹了幾種常用的存儲器芯片的結構、電路和工作原理。但是不同的應用場合會對芯片提出不同的要求。現有的芯片往往不能完全滿足系統的需要，因此如何用現有的芯片來實現系統的性能要求就成為了存儲系統必須解決的重要問題之一。芯片不滿足使用的需要主要有以下幾個方面：2007.7.229計算機組成原理1．位數不夠如系統需要的存儲容量為128K×8位，可選的芯片卻只有128K×1位或者128K×4位的芯片。這種情況下，芯片能夠滿足128K的要求，而位數卻不能滿足8位的要求。此時需要對位數進行擴展，即位擴展。2007.7.230計算機組成原理2．字數不夠如系統需要的存儲容量為256K×8位，可選的芯片卻只有64K×8位或者128K×8位的芯片。這種情況下，芯片能滿足8位的要求，但卻不能滿足容量256K的要求。此時需要對字進行擴展，即字擴展。2007.7.231計算機組成原理3．字數位數均不夠如系統需要的存儲容量為256K×8位，可選的芯片卻只有64K×4位或者128K×4位等芯片。這種情況下，芯片既不能滿足8位的要求，又不能滿足容量256K的要求。此時需要對位數和字同時進行擴展，即字位擴展。當芯片不能直接滿足系統需求時，設計者就需要對存儲器進行擴展。上述三種情況是對存儲器進行擴展時的三種主要情況，因此對存儲器的擴展又主要有位擴展、字擴展和字位擴展。2007.7.232計算機組成原理值得一提的是，如果發生下述情況：系統需要的存儲容量為128K×8位，可選的芯片只有256K×8位的芯片，這時不需要進行芯片擴展，只需要在編程時僅使用低地址空間即可；系統需要的存儲容量為128K×8位，可選的芯片只有128K×16位的芯片，這時也不需要進行芯片擴展，只需要在編程時只使用輸出數據的低8位，高8位懸空或者置零即可。所以只有當可選芯片的字或位不夠用時才需要進行芯片擴展。2007.7.233計算機組成原理4.3.1位擴展所謂位擴展，就是當單個芯片的容量能滿足要求，但是輸出位數不滿足系統對存儲器輸出位數的要求時，通過幾個芯片同時輸出的方式對存儲器的輸出位數進行擴展。根據前面的介紹，我們知道了何時需要進行位擴展，那么如何用位數較少的芯片來擴展位數較多的存儲器呢？比如，系統需要的存儲容量為128K×8位，可選的芯片卻只有128K×4位的芯片。其擴展過程如下：2007.7.234計算機組成原理（1）確定擴展類型：仔細分析系統要求可知，系統需要的容量跟芯片容量剛好相等，但是位數不同，因此我們需要進行位擴展；（2）需要確定所需芯片的數量，系統要求存儲器每次輸出8位數據，而一片芯片每次只能輸出4位，則為了滿足系統需求，每次要兩片芯片同時輸出，因此在對芯片進行選擇時，這兩片芯片的片選信號和地址線必須相同，實際連接電路時只需要將片選信號和地址線連在一起即可；（3）因為擴展時需要由兩個4位組成一個8位進行輸出，所以要確定哪4位為高4位，哪4位為低4位。根據以上步驟，可以得出如圖4-8所示的擴展電路圖。2007.7.235計算機組成原理2007.7.236計算機組成原理圖中，兩芯片的片選信號、讀寫控制信號和地址信號連在一起，當系統需要進行讀寫時，兩塊芯片將同時工作。現以讀地址為1024的單元為例介紹擴展后的存儲器工作過程：控制芯片將其與片選信號相連的引腳置為低電平；將與讀寫控制線相連的引腳置為低電平；將待讀取地址（00100H）通過地址總線傳送給存儲器，因為兩塊芯片的以上三個信號相同，它們將同時把其1024單元中的地址放到數據線上輸出，兩組輸出數據線分別連接控制芯片的數據線的高4位和低4位，所以控制器在發出一個讀信號后，將收到一組8位的數據。從而實現了用兩片4位輸出芯片擴展為一個8位輸出的存儲器。2007.7.237計算機組成原理4.3.2字擴展所謂字擴展，就是當單個芯片輸出位數滿足系統要求，而容量不滿足要求時，用多個芯片采用地址分段的方式對存儲容量進行擴展，參與擴展的每個芯片的地址范圍不同。注意：在學習本節內容的過程中，大家一定要注意字擴展和位擴展方法的不同。2007.7.238計算機組成原理下面用一個例子解釋字擴展的方法：系統需要的存儲容量為256K×8位，可選的芯片只有64K×8位。其擴展的步驟如下：（1）確定擴展類型分析系統要求可知，芯片輸出數據的位數與系統需求一致，所以不需要進行位擴展；芯片容量只有系統需求的四分之一，所以本例中，為了滿足系統需求，需要用多個小容量芯片組成一個較大容量的存儲器，即字擴展。2007.7.239計算機組成原理（2）確定芯片數量系統需要256K的容量，如果用64K的芯片則需要4片才能滿足系統需求。所以本例中，參加擴展的芯片數量為4。注意：如果實際需要的容量不是芯片容量的整數倍，則擴展后的容量不能比系統需要的容量小。（3）選擇合適的擴展方法字擴展時常采用的方法有線選法、數字邏輯法和譯碼法。2007.7.240計算機組成原理下面分別對以上三種方法進行介紹。線選法：所謂線選法就是在產生片選信號（低電平有效）時，不是由幾位地址線的組合狀態經過運算后得出，而是用直接將控制器的一根地址線與芯片使能端相連。線選法是字擴展中最簡單的方法，其優點是片選信號的產生過程簡單，不容易出現錯誤。但是由于每個芯片都占用一根地址線，當芯片數量增多時要求控制器地址線數量很多，而且此方法會嚴重浪費控制器的邏輯地址空間，限制了程序的規模。2007.7.241計算機組成原理采用線選法對上述例子進行字擴展的電路圖如圖4-9所示。圖中芯片的地址信號都是使用的A15～A0這16位低地址線，但是芯片的片選信號都分別占用了A16～A19中的一根地址線，則每個芯片的地址見表4-3所示。假設控制器的地址線共有20根，即A19～A0，尋址空間大小為1M。從上表中我們可以看出，被浪費的地址空間是00000H~6FFFFH、80000H~AFFFFH、C0000H~CFFFFH和F0000~FFFFFH四個范圍，地址空間大小占768K，占控制器尋址空間的75％，對地址空間造成了嚴重的浪費，且當系統需求增大時，被浪費的地址也無法再被利用。2007.7.242計算機組成原理芯片編號A15～A0A19～A16地址范圍10000H～FFFFH1110BE0000H～EFFFFH20000H～FFFFH1101BD0000H～DFFFFH30000H～FFFFH1011BB0000H～BFFFFH40000H～FFFFH0111B70000H～7FFFFH2007.7.243計算機組成原理2007.7.244計算機組成原理為了克服線選法對地址空間的浪費，我們常采用數字邏輯法和譯碼法進行字擴展。數字邏輯法：所謂數字邏輯法即用數字邏輯電路對兩位高地址進行邏輯運算產生片選信號。各個芯片的存儲單元的地址情況：256K的容量需要18根地址線（A17～A0），而64K的容量需要16根地址線，因此只需要從系統的18根地址線中取出低16位(A15～A0）即可對芯片內的每個存儲單元進行尋址，剩余的兩位高地址（A17、A16）有4種組合，每一種組合剛好可以用作產生片選信號。每個芯片的地址范圍見表4-4所示。2007.7.245計算機組成原理芯片編號地址范圍低16位地址范圍（A15～A0）高2位地址（A17A16）100000H～0FFFFH0000H～FFFFH00B210000H～1FFFFH0000H～FFFFH01B320000H～2FFFFH0000H～FFFFH10B430000H～3FFFFH0000H～FFFFH11B2007.7.246計算機組成原理2007.7.247計算機組成原理從上述例子中，我們可以看出：邏輯運算法克服了線選法的缺點，地址空間的利用率達到了100％，同時也節省了兩根地址線，所以存儲器的容量還可以進一步擴展。但是片選信號的產生復雜，容易出現錯誤。隨著擴展時所需芯片數量的增加，電路的復雜性將會成級數方式增加。為了達到地址空間100％的利用率和使用的地址線盡可能少的要求，克服邏輯運算法產生片選信號過程復雜的缺點，實際進行字擴展時常常采用第三種方法，即譯碼法。2007.7.248計算機組成原理譯碼法：所謂譯碼法就是對幾根地址線的組合狀態用譯碼器譯碼后產生片選信號。其原理與邏輯運算法類似，不同之處在于片選信號的產生方法，邏輯運算法是對地址狀態經過組合邏輯電路運算后得出片選信號，而譯碼法則是用譯碼器譯碼產生。根據參與譯碼的地址線的數量，可以將譯碼法分為：完全譯碼法和部分譯碼法。完全譯碼法是指所有地址線狀態都作為譯碼器輸入的方法。部分譯碼法是指部分地址線狀態作為譯碼器輸入的方法。2007.7.249計算機組成原理譯碼法進行字擴展時，各芯片的地址空間跟邏輯運算法的芯片地址空間一樣，如表4-5所示，因此只需要對兩位地址通過2-4譯碼器譯碼，即可產生4塊芯片需要的片選信號，所以采用的譯碼方法是部分譯碼法，芯片擴展后的電路圖如圖4-11所示。2007.7.250計算機組成原理2007.7.251計算機組成原理與邏輯運算法相比，譯碼法產生片選信號時，用譯碼器替代了復雜的數字組合邏輯電路。片選信號的產生簡單明了，不容易出現錯誤，更降低了成本。譯碼法不僅繼承了邏輯運算法的優點、克服了邏輯運算法的缺點，還方便存儲容量再次擴展。比如：現在需要將系統容量從256K提高到512K，譯碼法只需要將2-4譯碼器更改為3-8譯碼器，然后將譯碼器輸出與各芯片片選引腳相連即可；而采用邏輯運算時，需要重新計算每個片選信號與地址輸入信號的關系，然后根據此關系式選擇正確的門電路畫出組合邏輯電路圖，最后將每個組合邏輯電路的輸出與各芯片片選信號相連。因此，譯碼法是較方便且不容易出錯的字擴展方法。2007.7.252計算機組成原理4.3.3字位擴展所謂字位擴展，就是當單個芯片的輸出位數和容量同時不滿足系統要求時，用多個芯片結合位擴展和字擴展的方法對存儲器進行擴展。在實際芯片擴展時，常常會需要用到這種擴展。2007.7.253計算機組成原理例子：如系統需要的存儲容量為256K×8位，可選的芯片容量只有128K×4位。在這種情況下，存儲器需要一次輸出8位，而芯片卻只能一次輸出4位，需要進行位擴展；存儲器要求容量為256K，而芯片容量卻只有128K，需要進行字擴展。擴展過程中，需要用到位擴展的方法，也會用到字擴展的方法。擴展步驟如下：2007.7.254計算機組成原理（1）位擴展：根據位擴展的原理，此處需要兩個芯片同時輸出才能滿足系統對位數的要求，因此，連接電路時，這兩塊芯片的片選引腳必須接同一個片選信號，保證兩塊芯片同時被選中。2007.7.255計算機組成原理（2）字擴展：位擴展時，雖然是兩塊128K的芯片同時工作，但是存儲器容量仍然是128K，只是輸出變成了8位，構成了128K×8位的芯片。因此要構成256K×8位的存儲器，必須先將兩塊芯片構成一組，此時，這一組芯片可以當成一個128K×8位的芯片使用，然后由兩組芯片組成系統需要的存儲器。此處只需要兩組就可以達到要求，所以片選信號產生時，沒有用到譯碼器，而選擇了一個非門；如果需要多組，則需要通過譯碼芯片產生片選信號。（3）連接數據輸出線。字位擴展后的電路圖如圖4-12所示。2007.7.256計算機組成原理2007.7.257計算機組成原理電路中的4塊芯片從左向右編號分別為1、2、3、4，其中1、2號芯片構成一組，3、4號芯片構成一組。從圖中，我們可以看見每組芯片輸出都是8位，地址線A16～A0能對組內128K的地址范圍進行尋址。A17作為片選信號，當A17為低電平時，芯片1、2被選中，當A17為高電平時，芯片3、4被選中。因此，芯片1、2構成的芯片組地址范圍是00000H～1FFFFH，2、3構成的芯片組地址范圍是20000H～3FFFFH。2007.7.258計算機組成原理綜上所述，可以得到以下結論，假定系統需要的存儲容量為M×N位，可選的存儲芯片容量只有x×y位（x<M，y<N），此時需要在字向和位向同時進行擴展，共需（M/x）×（N/y）塊存儲芯片。思考：假如計算機存儲系統中單片ROM容量為4K×8，單片RAM容量為8K×8，請設計計算機存儲系統電路圖，要求ROM為16KB，RAM容量為64KB。2007.7.259計算機組成原理4.4高速緩沖存儲器Cache

4.4.1Cache基本原理1．設置Cache的必要性計算機有兩個核心器件，一個內存，另外一個則是CPU。二者是否能較好配合，將直接影響計算機性能。早期的CPU跟內存的速度相差不多，但是隨著計算機硬件技術的發展，CPU的速度提高的比內存快，現在內存和CPU的讀寫速度相差2～3個數量級。如果僅僅依靠內存給CPU傳輸數據，那么CPU可能會長時間等待，降低資源利用率。所以，必須對二者速度進行匹配。2007.7.260計算機組成原理匹配內存和CPU的速度有以下三個方法：（1）降低CPU速度；（2）采用高速的SRAM作為內存的存儲器；（3）根據程序執行的局部性原理，在二者之間設置一定的緩沖器。顯然，第一個方法降低了計算機性能，不可能采用；第二個方法需要用價格昂貴的SRAM來制作容量高達幾百兆的內存，成本過高。因此第三個方法則呈了現代計算機的首選方法。2007.7.261計算機組成原理實際的計算機系統中，常常在CPU和內存間設置一個容量不大（常常為幾十至幾百K）但是速度跟CPU速度相同的Cache作為緩沖器，把正在執行的指令代碼單元附近的一部分指令代碼或數據存入Cache中，CPU需要數據時，直接從Cache中讀取，這種方法解決了速度不匹配的問題，又不會大幅度增加成本。2007.7.262計算機組成原理2.基本原理Cache又叫高速緩存，是高速緩沖存儲器（CacheMemory）的簡稱。作為一種存儲器，Cache有一定的存儲空間，但Cache的主要作用不是進行數據存儲，所以其存儲空間較小。根據Cache所處位置的不同，可以將Cache分為一級Cache和二級Cache。與CPU集成在同一塊芯片中的是一級Cache（簡稱L1Cache），其容量常常為幾十KB～幾百KB；不與CPU集成在同一塊芯片中的是二級Cache（簡稱L2Cache），其容量常常為幾百KB～2MB。目前市場上比較高檔的CPU常常配有512KB、1MB或者2MB的Cache。配置了Cache的CPU和內存之間的存儲結構如圖4-13所示。2007.7.263計算機組成原理2007.7.264計算機組成原理在Cache控制器的作用下，CPU首先訪問Cache，如其需要的數據在Cache中，則直接訪問Cache即可，否則再訪問內存。如果設置了L2Cache，則系統將按照L1Cache、L2Cache、內存的順序訪問。值得注意的是：Cache不能被用戶直接訪問，用戶不能使用Cache地址進行編程。2007.7.265計算機組成原理Cache一般由SRAM、TRAM和控制器組成。其中，SRAM提供存儲空間，它的容量即為Cache的容量；TRAM保存Cache中的數據在主存中的地址；控制器則是實現比較和控制Cache的讀寫操作等功能。當CPU需要內存中某一地址的數據時，控制器首先將該地址信號與TRAM中的地址進行比較，如果找到相同的地址，說明內存中的數據在Cache中，則CPU直接訪問Cache，否則CPU將訪問內存。當CPU所需要的數據沒有在Cache中時，控制器還要完成對Cache的修改，將內存中的數據讀取到Cache中，以保證Cache命中率盡可能高，提高數據訪問速度。2007.7.266計算機組成原理4.4.2地址映像

Cache作為CPU和內存間的緩沖存儲器，理想情況下，應該保證CPU每次需要訪問的數據都在Cache中。但是，用戶程序卻是按照內存地址編寫的，Cache所做的工作是在CPU訪問內存前，根據程序執行的局部性原理，先將內存中的數據讀出，當CPU需要時再提供給它。所以，“Cache所保存的數據到底是內存中的哪些數據，地址是什么？”就成了關鍵性問題。這一問題實際上也是Cache的存儲空間與內存之間的地址映像問題。2007.7.267計算機組成原理常用的地址映像方式有三種：全相聯映像、直接映像和組相聯映像。1．全相聯映像所謂全相聯映像是指將內存和Cache按找固定的相同的大小進行分塊。內存的塊和Cache的塊可以任意對應，即內存的任何一塊都可以映像到Cache的任何一塊，在Cache的存儲空間被占滿的情況下，也允許確實已被占滿的Cache存儲器中替換出任何一個舊塊。2007.7.268計算機組成原理這種映像方式的優點是映像過程靈活，塊沖突率低，只有在Cache中的塊全部裝滿后才會出現沖突，Cache利用率高。缺點是塊表查找的速度慢，由于Cache的速度要求高，全部比較和替換策略都要用硬件實現，控制復雜，實現起來也比較困難，成本高。全相聯映像方式下內存與Cache對應的對應關系如圖4-14所示：2007.7.269計算機組成原理2007.7.270計算機組成原理2．直接映像跟全相聯映像一樣，直接映像先將Cache分成若干塊，每個塊的大小相同，并對每個塊進行編號，同時根據Cache容量大小將內存分成若干頁，每個頁的容量都跟Cache的容量相同，然后對內存進行分塊，每塊的大小跟Cache塊的大小相同，同樣對頁內的塊進行編號。映像時，內存的某個頁的塊只能保存在與其塊號相同的內存塊中。例如，如圖4-15所示，內存各頁中的第0塊只能映像到Cache的第0塊，而不能映像到其他塊。2007.7.271計算機組成原理2007.7.272計算機組成原理直接映像的優點是地址變換簡單、速度快，缺點是映像不靈活，塊沖突率較高，Cache命中率低，特別是程序需要在兩個頁的相同塊號的塊之間往返執行時，Cache命中率將降得非常低。2007.7.273計算機組成原理3．組相聯映像為了解決直接映像的沖突問題，組相聯映像方式，先將Cache分成大小相同的若干區，一般分為2個或4個區，對每個區按照直接映像的方式進行分塊，并且編號，因此，Cache中有多個編號相同的塊。對內存按照Cache區的大小進行分頁，再對每頁按照Cache塊的大小進行分塊，每個內存塊可以對應不同Cache區中的相同塊號的塊。例如，圖4-16中內存第0頁的第0塊，可以對應Cache的第0區的第0塊，也可以對應第j區的第0塊。2007.7.274計算機組成原理組相聯映像的減小了直接映像方式下的頁沖突問題，提高了Cache的命中率，且Cache的容量越大，分區的數量越多，命中率越高，但是這中映像方式控制電路復雜。值得注意的是，如果只對Cache分1個區時，則組相聯映像就是直接映像，因此，直接映像是組相聯映像的一種特殊情況。2007.7.275計算機組成原理2007.7.276計算機組成原理4.4.3替換策略及更新策略1.替換策略不管采用何種映像方式，內存的每個塊都對應Cache的某一個塊。但是Cache容量遠小于內存容量，不能將內存的所有塊全部保存。因此，如果需要往Cache中調入一個新塊，且Cache已經被占滿時，就需要將Cache中的某一個塊調出，而將新塊調入Cache，這個過程就是替換。2007.7.277計算機組成原理采用不同的替換策略，將很大程度上影響Cache的命中率。常用的替換策略有：隨機替換法：任意選擇一個Cache塊，將其調出。先進先出(FIFO)策略：替換出最先進入Cache的塊近期最少使用(LRU)策略：這種替換策略需隨時記錄Cache存儲器中各個字塊的使用情況，以便確定哪個字塊是近期最少使用的字塊。這三種策略的算法將在4.5節中介紹，這里不再贅述。2007.7.278計算機組成原理2.更新策略當內存數據被修改時，與之對應的Cache的數據也需要相應修改，這個過程就是更新。但是，進行修改時，Cache無法向CPU提供數據，因此修改Cache的時機相當重要。常用的更新策略有：2007.7.279計算機組成原理及時更新策略：修改內存的同時對Cache進行修改。周期更新策略：對Cache的修改周期進行，修改周期到的時候，無論內存數據是否改變，都將Cache數據更新為與內存相同的數據。執行時更新策略：當CPU需要某個Cache塊的數據時，將此塊與內存中與之對應的塊進行比較，二者不相同時，對Cache進行更新。思考：目前市場上主流微處理器（CPU）和最新技術的微處理器（CPU）的Cache的容量分別是多少？2007.7.280計算機組成原理4.5虛擬存儲系統

程序要運行，需要CPU運算，而在計算機存儲中，CPU只能從內存中讀取數據，因此要運行的程序必須首先進入內存。此時，如果程序運行所需要的內存容量大于計算機配置的內存容量，則程序無法運行。而當前，很多的計算機軟件對內存的需求都大于實際的內存容量，如果不采用一定的方法對內存進行擴充，則計算機的應用范圍將受到很大限制。在4.3節中，我們學習了如何依靠芯片數量的增加來增大存儲器容量的方法，能在一定程度上解決系統容量的問題，但是芯片數量的增加必然導致成本的急劇提高。因此如何在現有的存儲容量基礎上，通過對程序進出內存的方法進行設計以提高存儲器利用率，讓計算機能運行比自身內存大得多的程序便成了首要任務，于是虛擬技術便應運而生。2007.7.281計算機組成原理所謂虛擬存儲，就是采用一定的方法將一定的外存容量模擬成內存，同時對程序進出內存的方式進行管理，從而得到一個比實際內存容量大得多的內存空間，使得程序的運行不受內存大小的限制。虛擬存儲方法的實現依賴于程序的特性：2007.7.282計算機組成原理順序性。所謂程序的順序性，是指程序運行過程中，如果要運行第N＋1行語句，則大多數情況下需要先運行第N行語句，即程序是在順序執行。局部性。為了減小程序的規模，很多的程序設計語言都會設計循環結構，如C語言中的for語句和while語句就是典型的循環語句，程序在執行這類循環語句時，程序的執行范圍就限定在循環體中，而不會執行循環體外的語句。執行的語句限定在很小的范圍內，即在局部范圍內執行，這種情況經常會發生，這就是程序的局部性。2007.7.283計算機組成原理根據程序的以上兩個特性，需要運行的程序不需要完全進入內存也可運行。具體方法如下：根據程序的順序性和局部性原理，如果將程序分成幾塊，當前面一個塊快運行結束時再將下一個塊調入內存，則程序的執行將不會受到影響，而且程序所需要的內存容量也將變小。本節的幾種虛擬存儲實現的方法都是基于這一原理。2007.7.284計算機組成原理4.5.1頁式存儲系統在學習頁式存儲方法之前，我們先了解一下最簡單的兩種存儲器分配方式。1.單一連續分配在單道環境下，計算機只允許一個作業運行，此時所有的計算機資源被該作業獨占，包括存儲器。所謂單一，是指此方式下，計算機只為一個作業分配存儲空間。所謂連續，是指出了操作系統占用的存儲空間外，剩余的內存空間將全部分配給作業，因此作業占用的存儲空間不間斷。其內存分配情況圖4-17所示。2007.7.285計算機組成原理2007.7.286計算機組成原理系統運行必須要操作系統統一管理，因此盡管計算機只運行一個作業，也要將操作系統運行的內存空間留出來。但是不管操作系統是如圖4-17（a）一樣占據低地址空間，還是如圖4-17（b）一樣占據高地址空間，作業所占的地址都是連續的，而且除操作系統占用的那一部分內存外，剩余的所有內存空間均被作業獨占。這種分配方式很容易造成內存空間的浪費。因為作業的大小跟剩余空間的大小往往不相等。如圖4-17的兩個圖所示，內存容量為128KB，操作系統占用32KB，剩余空間內存96KB。如果作業大小為20KB，則剩余76KB的存儲空間在該作業退出系統前將不會被利用。2007.7.287計算機組成原理為了解決單一分配時的空間浪費問題，在給作業分配存儲空間之前，先將剩余空間分成若干區域，各區域大小可以相同也可以不同，然后再根據作業的需要進行分配，即分區分配。2007.7.288計算機組成原理2．分區分配根據分區分配時，區域的大小是否固定，分區分配又可以分為固定分區分配和可變分區分配。（1）固定分區分配。所謂固定分區分配，是指先將內存分成若干固定區域，區域大小一經確定將永遠不再改變，每個作業占用一個區域。2007.7.289計算機組成原理分區過程中，要給作業分配內存，必須首先要知道哪些分區是空閑（未分配）的，這些空閑區的容量是多大。因此系統需要設置一種表格來紀錄這些信息，常常采用的方法是分區分配表。為了滿足正常分配的要求，分區分配表應該包含每個分區的起始地址、大小和分配情況等信息。分配前，系統先查找分區分配表，如果能找到一個滿足作業要求的的分區，則將此分區分配給作業。在固定分區中，分區分配表直接決定了是否能正確給各作業分配存儲空間，所以為了保證分區的正確性，需要隨時更新分區分配表的信息。2007.7.290計算機組成原理常用的分區方法一般有兩種：最佳適應法和最先適應法。所謂最佳適應法，是指在給作業分配空間時，首先遍查分區分配表找到一個能滿足作業要求的最小分區分配給該作業。而最先適應法則是指在分區時，按地址從低到高查找分區分配表，將找到的第一個能滿足作業運行要求的分區分配給作業。流程圖分別如圖4-20和圖4-21所示2007.7.291計算機組成原理2007.7.292計算機組成原理2007.7.293計算機組成原理假如在圖4-19（a）所示的情況下，又有一個需要23KB運行空間的作業3進入內存。如果采用最佳適應法進行分配，則通過查找分區分配表可知：能滿足該作業要求的分區的序號分別為2、3和5，三個分區的大小分別為30KB、25KB和35KB，很顯然分區3是容量最小的分區，則系統將此分區分配給作業3，同時將其分配狀態和標志分別修改為已分配和作業3。如果采用最先適應算法進行分配，在查找分區分配表時，找到的第一個能滿足作業要求的分區是分區2，則將該分區分配給作業3，同時跟最佳適應法一樣修改分區2對應的分配情況和標志。2007.7.294計算機組成原理從上述分區過程中，我們不難看出，最佳適應法給作業分配的空間是最合適作業運行的空間，這就是“最佳”的原因，但是分配的速度較慢，在分配前系統要查找分區分配表的所有表項，然后才能找到最佳的分區，隨著內存容量的增大、分區的增多，此查找過程所需要的時間將會很長；而最先適應算法分配空間的速度最快，不需要查找所有的表項，但是最先適應算法容易造成空間的浪費，如前所述，給作業3分配的分區為分區2，根據固定分區的思想，該分區的剩余空間不能在分配給其他作業，則作業2占用的空間為30KB，浪費的空間為7KB，如果再有一個28KB的作業進入系統，則勢必將作業5分配給該作業，又再次造成7KB的空間浪費，降低了存儲空間的利用率。因此，無論采用那種分配方式，固定分區都不能完全滿足系統對速度和空間利用率的要求。2007.7.295計算機組成原理（2）可變分區分配所謂可變分區分配是指先不給內存分區，給作業分配時，根據作業運行時對內存的需要再從剩余空間中分出一部分給該作業。經過一段時間的分配后內存也將分為若干區域，因此，在可變分區中也需要設置分區分配表。2007.7.296計算機組成原理假設內存容量為256KB，有以下申請和釋放內存的操作順序：作業1申請20KB，作業2申請30KB，作業3申請40KB，作業4申請30KB，作業1釋放20KB，作業3釋放40KB。則其內存的分布情況如下所述。當4個作業申請完內存之后，內存分布情況如圖4-22（a）所示，跟固定分區一樣，為了對內存進行有效地管理，每次分區后也將對分區分配表進行修改，從而得到圖4-22（b）所示的分區分配表。2007.7.297計算機組成原理20KB（作業1）30KB（作業2）40KB（作業3）30KB（作業4）136KB2007.7.298計算機組成原理分區序號起始地址（K）分區大小（KB）分配狀態標志1020已分配作業122030已分配作業235040已分配作業349030已分配作業45120136未分配02007.7.299計算機組成原理與固定分區時的分區情況相同，給作業分配空間后，內存都被分成了很多大小不同的分區。但是他們的區別是：每個分區的大小的確定方法不同。固定分區中每個分區的大小在給作業分配之前就已經確定好了，而可變分區中每個分區的大小是在分配時根據作業的大小確定。空閑分區不同。固定分區中，空閑區要按分區前的分區大小分成幾個空閑區，而可變分區中，空閑分區可能是一個連續的區域。作業1和作業3釋放空間后的內存分配情況和分區分配表如圖4-23所示。2007.7.2100計算機組成原理20KB30KB（作業2）40KB30KB（作業4）136KB2007.7.2101計算機組成原理分區序號起始地址（K）分區大小（KB）分配狀態標志1020未分配022030已分配作業235040未分配049030已分配作業25120136未分配02007.7.2102計算機組成原理圖4-23（a）所示的分區情況如果不加以修改，則會出現以下兩種情況：如果還有一個需要140KB的運行空間的作業5進入系統。此時剩余空閑區的總和為196KB，比作業所需要的空間大，但是因此時的空閑空間被分成了三個區，每個區都不足以給作業5分配，從而導致作業5無法運行。如果還有一個需要38KB的運行空間的作業6進入系統，則系統將會從40KB空閑空間中分出38KB分配給作業6，產生2KB的剩余空間，但是因為空間太小，這2KB的剩余空間可能無法滿足任何作業的運行需求，從而成為“碎片”。系統進行多次內存分配后，碎片問題將會越來越嚴重，導致內存空間被浪費，降低內存的利用率。2007.7.2103計算機組成原理因此，在采用可變分區方式的系統中，常常會采用以下方法來解決上述兩個問題：（1）移動。如果內存中，有多段不連續的空閑區域，則將分配區域向低地址方向或高地址方向移動，使得空閑區域構成一個連續的區域。移動后，圖4-23所示的內存分配將變成圖4-24所示的內存分配情況。2007.7.2104計算機組成原理30KB（作業2）30KB（作業4）20KB40KB136KB2007.7.2105計算機組成原理分區序號起始地址（K）分區大小（KB）分配狀態標志1030已分配作業223030已分配作業436020未分配048040未分配05120136未分配02007.7.2106計算機組成原理（2）合并。將空閑區域合并成一個較大的空閑區域。以便再次分配，滿足作業要求。合并后的分區情況如圖4-25所示。30KB（作業2）30KB（作業4）206KB2007.7.2107計算機組成原理分區序號起始地址（K）分區大小（KB）分配狀態標志1030已分配作業223030已分配作業4360206未分配02007.7.2108計算機組成原理經過移動和合并之后，內存的所有不連續的小的空閑區組成了一個連續的大的空閑區，保證后面進入系統的作業能正常分配空間。然而，這種方法在能解決碎片問題和空閑區不連續的問題的同時，會產生一個新的問題，即移動時機的選擇問題。對內存進行整體移動所需要花費的時間非常長，移動過程中，CPU將停止工作。所以，如果移動時機選擇不當，將會嚴重影響系統性能。前面介紹的幾種分區分配方式，都有自己的優點和不足，分配方法也各不相同，但是他們有一個共同點，就是：一個作業占用一段連續的內存空間，當空閑空間比作業運行所需要的空間小時，作業將無法進入系統。2007.7.2109計算機組成原理3.分頁虛擬存儲在可變分區分配中，為了解決空閑區不連續問題而采用了移動作業的內存空間的方法，系統開銷非常大，而且采用的方法是讓硬件適應軟件的方法。其實解決上述問題的也可以從另一方面入手，那就是讓軟件去適應硬件。這里所說的軟件是作業，硬件是內存。既然移動內存需要花費很多CPU時間，那就將作業劃分為幾個部分，每個部分存在一個空閑區域中，這樣，要保存一個較大的作業就不需要找到一個比作業空間大的空閑空間，而只需要多個空閑塊的容量之和大于作業容量即可。2007.7.2110計算機組成原理為了方便內存管理，人們首先想到的是將作業按統一的大小劃分成多個“頁”，同時也將內存按頁面大小劃分成若干個“物理塊”（簡稱“塊”），并對頁和塊按地址從低到高的順序編號。分配內存時，因為頁的大小與塊的大小相同，所以每個頁就對應一個塊。此時，只要剩余塊的數量不小于作業頁的數量，則不需要作業占用的所有塊地址都連續。也就不需要將內存的所有空閑區域移動到一起了。2007.7.2111計算機組成原理采用分頁存儲能用不連續的存儲空間存儲作業，但是也將引出新的問題，那就是如何讓頁的邏輯關系不變，即當前面的頁運行完的時候，如何尋找下一個應該運行的頁。為了解決這一問題，在分頁存儲中，需要一種新的數據結構――頁表。頁表的結構見表4-6所示。2007.7.2112計算機組成原理頁號塊號010145250325415……2007.7.2113計算機組成原理頁表的每一行就是一個頁面的信息，分為兩項，第一項是頁號，第二項是該頁對應的塊。作業執行時，所有程序和數據必須從內存塊中取得。因此在執行某一個塊的程序前，系統按頁號從低到高的順序查找頁表，根據頁表的記錄找到該頁對應的物理塊，進而執行塊中的程序和數據。分頁時是按邏輯地址進行的，頁的順序就是程序執行的先后順序，因此，盡管將一個作業分成很多頁，作業的執行順序也不會受到影響。然而，程序員是按照邏輯地址編程，程序卻是按照其物理地址執行，因此，在分頁式存儲管理系統中，邏輯地址是否能轉換為正確的物理地址，將直接影響作業執行的正確性。邏輯地址結構如圖4-26所示。頁號頁內地址2007.7.2114計算機組成原理作業頁的大小和物理塊的大小相同，在地址轉換時，頁內地址可以直接作為塊內地址。但是，頁號和物理塊號并不能一一對應，如表4-6中，0號頁面對應于10號塊，1號頁面對應于45號塊等等，因此不能用頁號直接訪問物理塊。因為頁表記錄這頁與塊的對應關系，所以作業執行時，系統需要經常通過訪問頁表將邏輯地址轉換為物理地址。其過程如圖4-27所示。2007.7.2115計算機組成原理2007.7.2116計算機組成原理分頁系統雖然克服了前面幾種分區方法的缺點，很好地克服了碎片問題，但是系統的空閑物理塊數量必須不小于作業的頁數量時，否則作業也將無法運行。根據程序的順序性和局部性原理，程序要執行并不需要所有的頁面同時進入內存，只需要正在運行或馬上即將運行的頁面在內存中即可，即只允許少量頁面進入內存，作業一樣能運行。其中最簡單可行的辦法就是請求分頁存儲系統。2007.7.2117計算機組成原理4.請求分頁虛擬存儲所謂“請求”，是指不將作業的所有頁同時放入內存，而是作業在運行過程中需要某個頁時，如果該頁沒有在內存中，則請求中斷，讓系統將該頁從外存放入內存。因此，在給作業分配空間時，不需要按作業的頁數分配物理塊，而是只給作業分配少量的物理塊，然后通過一定的置換機制實現用少量的物理塊運行較大的作業。所謂“置換”是指當作業需要某個沒有在內存中的頁時，如果系統分配給作業的幾個物理塊已經全部被占滿，則根據一定的算法將內存中的頁面調到外存，而將馬上要運行的頁調入內存。比如：系統分配給某作業三個物理塊，此三個物理塊分別保存作業的2、4和6號頁，當作業需要運行5號頁時，因為系統分配給該作業的三個塊已經被占滿，則需要從2、4和6號頁中選擇淘汰一個，將其調出內存，而將5號頁面放入內存運行。如果置換算法設計不當，則頁將會頻繁地調入調出內存，增大系統開銷，降低系統性能，特別是“顛簸”問題的存在，給置換算法提出了很高的要求。2007.7.2118計算機組成原理“顛簸”是指剛調出內存的頁，由于馬上又運行，則需要重新將此頁面調入內存。所以選擇何種置換算法將直接影響請求分頁虛擬存儲的性能。常用的頁面置換算法主要有：先進先出置換算法、最久不用置換算法和最近最久未用置換算法。2007.7.2119計算機組成原理（1）先進先出置換算法采用先進先出（FIFO）置換算法，淘汰的頁是最先進入內存的頁先進先出置換算法利用了隊列的特點得以實現。隊列就是一種先進先出的數據結構，最先進入隊列的元素排在隊首，第二進來的元素排在隊首后面，依此類推，最后進入的隊列的元素排在隊尾。不管隊列中的元素如何變化，隊首元素永遠是隊列所有元素中最先進入的，因此在采用隊列的方法時，要淘汰一個頁面的時候只需要將隊首元素淘汰，此時第二個元素將成為新的隊首元素，然后將作業需要的新頁放在隊尾位置，如此循環就可以實現新老頁的替換。2007.7.2120計算機組成原理置換過程中要注意缺頁和置換發生的時機。缺頁是在作業要執行的頁沒有在內存中時發生，跟系統分配給作業的幾個塊是否被占滿無關。而置換則是在作業要執行的頁沒有在系統中，且分配給作業的塊已經被占滿的時候發生。本例中的前3個頁進入內存時，內存塊沒有被占滿，所以只發生了缺頁，沒有發生置換；后面的新頁進入內存時，內存塊已經被占滿，所以將同時發生缺頁和置換。當然，實現FIFO還有其他方法，不過用隊列實現FIFO，方法簡單、不容易出錯，建議讀者熟悉此方法。2007.7.2121計算機組成原理（2）最久不用置換算法FIFO置換算法中，置換的頁是最先進入內存的頁，這種方法雖然實現簡單，但是性能卻并不好，容易出現“顛簸”現象。理論上，在相同的頁面使用順序時，最久不用置換算法是性能最好的算法，但是，實際上，作業執行過程中，很難確定頁的使用順序，也就無法確定內存中的哪個頁為將來最久不會使用的頁，因此該算法是無法實現的。2007.7.2122計算機組成原理（3）最近最久未用置換算法（LeastRecentlyUsed，LRU）FIFO置換算法雖然實現起來非常簡單，但是性能較差；最久不用置換算法性能最好，但是無法實現。在實際使用時，這兩種算法都很少使用，經常使用的是最近最近未用置換算法。2007.7.2123計算機組成原理根據程序執行的順序性和局部性，當一個頁剛剛被使用過，則該頁被再次使用的幾率較高；相反，越早使用過的頁，被再次使用的幾率越低。最近最久未用算法就是基于作業的這一特性設計的。最近最久未用置換算法在進行頁面置換時，總是將處于內存的幾個頁中，最后一次使用時間距離當前時間最久的那一個頁淘汰。在用該算法進行頁面置換時，必須首先要確定哪個頁是最后被使用的。2007.7.2124計算機組成原理4.5.2段式虛擬存儲通過前面的學習，我們知道，頁式虛擬存儲因為頁的大小跟物理塊的大小相同，所以很大程度上解決了存儲管理的碎片問題。但是按照固定的大小對作業進行分頁，往往會破壞作業本身的邏輯結構，因為現在的程序大都按其功能分為很多的子程序，而子程序的大小各不相同，更不會是剛好頁大小的整數倍，所以如果單純對作業進行分頁，則有的頁可能會包含有一個子程序的結尾部分和另外一個頁的開始部分。這就完全破壞了程序的模塊化。然而模塊化思想解決軟件危機的最基本的思想，編程序時要注意程序模塊化，存儲管理時更要注意保持子程序的完整性。2007.7.2125計算機組成原理1.分段原理程序模塊化的最基本的思想是為每一個功能都編制一段程序，比如學生學籍管理系統可以分為數據輸入、數據維護、用戶檢索等功能，不同功能由不同的模塊完成，模塊間可能會互相調用。為了保證程序的正常執行和模塊間的正確調用，每一個模塊都必須有自己的標識符，系統也可以通過標識符區分不同功能的模塊，因此可以用模塊所完成的功能對模塊進行命名，將模塊名作為標識符，并對各模塊進行編號。2007.7.2126計算機組成原理程序的每一個模塊都可以作為一個段，模塊的編號可以作為段的編號。為了對模塊內的語句進行正確尋址，也需要有一個段內地址。因此，分段存儲管理下，地址結構如圖4-32所示。段號段內地址2007.7.2127計算機組成原理要對某個子程序中的某個語句進行訪問，首先知道該語句所在的子程序的編號，即段號，其次要知道該語句相對于子程序的起始地址的偏移量，即段內地址。在如圖4-32所示的結構中，當知道某個語句的地址時，系統將首先取出地址中的段號，根據段號找到相應的子程序，然后再通過地址中的段內地址找到語句。2007.7.2128計算機組成原理2.存儲空間分配段式存儲管理系統中，由于按照邏輯關系將作業分成了若干段，所以沒有必要給作業分配一個連續的地址空間，只需要給每個段分配一個連續的空間即可。因此在段式存儲管理方式下，邏輯相鄰的段可能在物理地址上不連續。如圖4-33所示。2007.7.2129計算機組成原理2007.7.2130計算機組成原理圖4-33中，作業分成了4段，各段占用不連續的內存空間。段1大小為20KB，占用起始地址為80KB的空間；段2大小為30KB，占用起始地址為160KB的空間；段3大小為10KB，占用起始地址為130KB的空間；段4大小為40KB，占用起始地址為250KB的空間。2007.7.2131計算機組成原理3.段表圖4-33中，假如作業按照段1、段2、段3、段4的順序執行，段空間不連續，當作業執行完前一個段后，如何知道下一個段的內存起始地址呢？因此必須有種數據結構來保存各段對應的物理空間，其中應該包括段號、分給該段的空間的起始地址和長度等信息，段表就是這樣一種數據結構，能記錄段的空間的各種信息。圖4-33所示的段空間分配狀態所對應的段表如表4-7所示。2007.7.2132計算機組成原理段號起始地址（K）長度（KB）180202160303130104250402007.7.2133計算機組成原理設置段表后，當作業開始運行時，首先查找段表，找到第一個段的內存起始地址，并根據起始地址和長度計算出終止地址，當作業執行到第一段的終止地址時，根據段表記錄再去查找第二個段對應的內存地址，如此反復，即可在段表的輔助下將作業的4個段正確執行。2007.7.2134計算機組成原理上述過程實際是將作業的邏輯地址轉換成物理地址的過程。作業根據將要執行的語句的邏輯地址計算出段號和段內地址，然后根據邏輯地址查找段表，得到相應的內存段的起始地址，將此起始地址加上段內地址即是該語句的物理地址。此地址變換過程跟分頁式存儲管理地址變換過程類似，如圖4-34所示。2007.7.2135計算機組成原理2007.7.2136計算機組成原理圖中4-31所示地址轉換過程中的最后一步是進行地址計算，意思是將段內地址和查段表得到與段對應的內存區的起始地址相加得到將要訪問的語句的物理地址，從而實現邏輯地址到物理地址的轉換。2007.7.2137計算機組成原理4.5.2段頁式虛擬存儲段式存儲管理保證了程序的邏輯性不遭破壞，但是每個段需要占用一段連續的空間，因此，單純的段式存儲具有連續分配的缺點，即作業的空閑空間之和大于作業所需要的空間，但是每一個小的空閑空間不一定能滿足各個段的需要。如圖4-33所示，作業的4個段分別需要10KB、20KB、30KB和40KB