第4章存儲系統(tǒng)課件

第4章存儲系統(tǒng)計(jì)算機(jī)組成原理2007.7.21計(jì)算機(jī)組成原理第4章存儲系統(tǒng)本章介紹了計(jì)算機(jī)中各種常見存儲器芯片的結(jié)構(gòu)和工作原理，以及當(dāng)存儲器芯片不滿足系統(tǒng)需求時，如何對存儲器進(jìn)行擴(kuò)展，采用何種方式對存儲器進(jìn)行管理以提高存儲空間的利用率。2007.7.22計(jì)算機(jī)組成原理本章要點(diǎn)：存儲器分類及其工作原理芯片擴(kuò)展方法存儲空間管理方法2007.7.23計(jì)算機(jī)組成原理

4.1計(jì)算機(jī)存儲系統(tǒng)組織方式

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

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

2007.7.28計(jì)算機(jī)組成原理4.2半導(dǎo)體存儲器芯片介紹

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

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

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

memory）是一種根據(jù)存儲內(nèi)容來進(jìn)行存取的存儲器，也稱為按內(nèi)容訪問存儲器（content

addressed

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

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

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

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

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