第3章 存儲(chǔ)系統(tǒng)2課件

3.1.2存儲(chǔ)器的基本組織

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

3.3.1Cache的功能與基本原理1．設(shè)置Cache的必要性計(jì)算機(jī)有兩個(gè)核心器件，一個(gè)內(nèi)存，另外一個(gè)則是CPU。二者是否能較好配合，將直接影響計(jì)算機(jī)性能。早期的CPU跟內(nèi)存的速度相差不多，但是隨著計(jì)算機(jī)硬件技術(shù)的發(fā)展，CPU的速度提高的比內(nèi)存快，現(xiàn)在內(nèi)存和CPU的讀寫(xiě)速度相差2～3個(gè)數(shù)量級(jí)。如果僅僅依靠?jī)?nèi)存給CPU傳輸數(shù)據(jù)，那么CPU可能會(huì)長(zhǎng)時(shí)間等待，降低資源利用率。所以，必須對(duì)二者速度進(jìn)行匹配。33匹配內(nèi)存和CPU的速度有以下三個(gè)方法：（1）降低CPU速度；（2）采用高速的SRAM作為內(nèi)存的存儲(chǔ)器；（3）根據(jù)程序執(zhí)行的局部性原理，在二者之間設(shè)置一定的緩沖器。顯然，第一個(gè)方法降低了計(jì)算機(jī)性能，不可能采用；第二個(gè)方法需要用價(jià)格昂貴的SRAM來(lái)制作容量高達(dá)幾百兆的內(nèi)存，成本過(guò)高。因此第三個(gè)方法則呈了現(xiàn)代計(jì)算機(jī)的首選方法。34實(shí)際的計(jì)算機(jī)系統(tǒng)中，常常在CPU和內(nèi)存間設(shè)置一個(gè)容量不大（常常為幾十至幾百K）但是速度跟CPU速度相同的Cache作為緩沖器，把正在執(zhí)行的指令代碼單元附近的一部分指令代碼或數(shù)據(jù)存入Cache中，CPU需要數(shù)據(jù)時(shí)，直接從Cache中讀取，這種方法解決了速度不匹配的問(wèn)題，又不會(huì)大幅度增加成本。352.基本原理Cache又叫高速緩存，是高速緩沖存儲(chǔ)器（CacheMemory）的簡(jiǎn)稱(chēng)。作為一種存儲(chǔ)器，Cache有一定的存儲(chǔ)空間，但Cache的主要作用不是進(jìn)行數(shù)據(jù)存儲(chǔ)，所以其存儲(chǔ)空間較小。根據(jù)Cache所處位置的不同，可以將Cache分為一級(jí)Cache和二級(jí)Cache。與CPU集成在同一塊芯片中的是一級(jí)Cache（簡(jiǎn)稱(chēng)L1Cache），其容量常常為幾十KB～幾百KB；不與CPU集成在同一塊芯片中的是二級(jí)Cache（簡(jiǎn)稱(chēng)L2Cache），其容量常常為幾百KB～2MB。目前市場(chǎng)上比較高檔的CPU常常配有512KB、1MB或者2MB的Cache。配置了Cache的CPU和內(nèi)存之間的存儲(chǔ)結(jié)構(gòu)如圖4-13所示。3637在Cache控制器的作用下，CPU首先訪(fǎng)問(wèn)Cache，如其需要的數(shù)據(jù)在Cache中，則直接訪(fǎng)問(wèn)Cache即可，否則再訪(fǎng)問(wèn)內(nèi)存。如果設(shè)置了L2Cache，則系統(tǒng)將按照L1Cache、L2Cache、內(nèi)存的順序訪(fǎng)問(wèn)。值得注意的是：Cache不能被用戶(hù)直接訪(fǎng)問(wèn)，用戶(hù)不能使用Cache地址進(jìn)行編程。38Cache一般由SRAM、TRAM和控制器組成。其中，SRAM提供存儲(chǔ)空間，它的容量即為Cache的容量；TRAM保存Cache中的數(shù)據(jù)在主存中的地址；控制器則是實(shí)現(xiàn)比較和控制Cache的讀寫(xiě)操作等功能。當(dāng)CPU需要內(nèi)存中某一地址的數(shù)據(jù)時(shí)，控制器首先將該地址信號(hào)與TRAM中的地址進(jìn)行比較，如果找到相同的地址，說(shuō)明內(nèi)存中的數(shù)據(jù)在Cache中，則CPU直接訪(fǎng)問(wèn)Cache，否則CPU將訪(fǎng)問(wèn)內(nèi)存。當(dāng)CPU所需要的數(shù)據(jù)沒(méi)有在Cache中時(shí)，控制器還要完成對(duì)Cache的修改，將內(nèi)存中的數(shù)據(jù)讀取到Cache中，以保證Cache命中率盡可能高，提高數(shù)據(jù)訪(fǎng)問(wèn)速度。393.3.2地址映像Cache作為CPU和內(nèi)存間的緩沖存儲(chǔ)器，理想情況下，應(yīng)該保證CPU每次需要訪(fǎng)問(wèn)的數(shù)據(jù)都在Cache中。但是，用戶(hù)程序卻是按照內(nèi)存地址編寫(xiě)的，Cache所做的工作是在CPU訪(fǎng)問(wèn)內(nèi)存前，根據(jù)程序執(zhí)行的局部性原理，先將內(nèi)存中的數(shù)據(jù)讀出，當(dāng)CPU需要時(shí)再提供給它。所以，“Cache所保存的數(shù)據(jù)到底是內(nèi)存中的哪些數(shù)據(jù)，地址是什么？”就成了關(guān)鍵性問(wèn)題。這一問(wèn)題實(shí)際上也是Cache的存儲(chǔ)空間與內(nèi)存之間的地址映像問(wèn)題。40常用的地址映像方式有三種：直接映像,全相聯(lián)映像、和組相聯(lián)映像。1．全相聯(lián)映像所謂全相聯(lián)映像是指將內(nèi)存和Cache按找固定的相同的大小進(jìn)行分塊。內(nèi)存的塊和Cache的塊可以任意對(duì)應(yīng)，即內(nèi)存的任何一塊都可以映像到Cache的任何一塊，在Cache的存儲(chǔ)空間被占滿(mǎn)的情況下，也允許確實(shí)已被占滿(mǎn)的Cache存儲(chǔ)器中替換出任何一個(gè)舊塊。41這種映像方式的優(yōu)點(diǎn)是映像過(guò)程靈活，塊沖突率低，只有在Cache中的塊全部裝滿(mǎn)后才會(huì)出現(xiàn)沖突，Cache利用率高。缺點(diǎn)是塊表查找的速度慢，由于Cache的速度要求高，全部比較和替換策略都要用硬件實(shí)現(xiàn)，控制復(fù)雜，實(shí)現(xiàn)起來(lái)也比較困難，成本高。全相聯(lián)映像方式下內(nèi)存與Cache對(duì)應(yīng)的對(duì)應(yīng)關(guān)系如圖3-24所示：42432．直接映像跟全相聯(lián)映像一樣，直接映像先將Cache分成若干塊，每個(gè)塊的大小相同，并對(duì)每個(gè)塊進(jìn)行編號(hào)，同時(shí)根據(jù)Cache容量大小將內(nèi)存分成若干頁(yè)，每個(gè)頁(yè)的容量都跟Cache的容量相同，然后對(duì)內(nèi)存進(jìn)行分塊，每塊的大小跟Cache塊的大小相同，同樣對(duì)頁(yè)內(nèi)的塊進(jìn)行編號(hào)。映像時(shí)，內(nèi)存的某個(gè)頁(yè)的塊只能保存在與其塊號(hào)相同的內(nèi)存塊中。例如，如圖4-15所示，內(nèi)存各頁(yè)中的第0塊只能映像到Cache的第0塊，而不能映像到其他塊。4445直接映像的優(yōu)點(diǎn)是地址變換簡(jiǎn)單、速度快，缺點(diǎn)是映像不靈活，塊沖突率較高，Cache命中率低，特別是程序需要在兩個(gè)頁(yè)的相同塊號(hào)的塊之間往返執(zhí)行時(shí)，Cache命中率將降得非常低。463．組相聯(lián)映像為了解決直接映像的沖突問(wèn)題，組相聯(lián)映像方式，先將Cache分成大小相同的若干區(qū)，一般分為2個(gè)或4個(gè)區(qū)，對(duì)每個(gè)區(qū)按照直接映像的方式進(jìn)行分塊，并且編號(hào)，因此，Cache中有多個(gè)編號(hào)相同的塊。對(duì)內(nèi)存按照Cache區(qū)的大小進(jìn)行分頁(yè)，再對(duì)每頁(yè)按照Cache塊的大小進(jìn)行分塊，每個(gè)內(nèi)存塊可以對(duì)應(yīng)不同Cache區(qū)中的相同塊號(hào)的塊。例如，圖4-16中內(nèi)存第0頁(yè)的第0塊，可以對(duì)應(yīng)Cache的第0區(qū)的第0塊，也可以對(duì)應(yīng)第j區(qū)的第0塊。47組相聯(lián)映像的減小了直接映像方式下的頁(yè)沖突問(wèn)題，提高了Cache的命中率，且Cache的容量越大，分區(qū)的數(shù)量越多，命中率越高，但是這中映像方式控制電路復(fù)雜。值得注意的是，如果只對(duì)Cache分1個(gè)區(qū)時(shí)，則組相聯(lián)映像就是直接映像，因此，直接映像是組相聯(lián)映像的一種特殊情況。48494.4.3替換策略及更新策略1.替換策略不管采用何種映像方式，內(nèi)存的每個(gè)塊都對(duì)應(yīng)Cache的某一個(gè)塊。但是Cache容量遠(yuǎn)小于內(nèi)存容量，不能將內(nèi)存的所有塊全部保存。因此，如果需要往Cache中調(diào)入一個(gè)新塊，且Cache已經(jīng)被占滿(mǎn)時(shí)，就需要將Cache中的某一個(gè)塊調(diào)出，而將新塊調(diào)入Cache，這個(gè)過(guò)程就是替換。50采用不同的替換策略，將很大程度上影響Cache的命中率。常用的替換策略有：隨機(jī)替換法：任意選擇一個(gè)Cache塊，將其調(diào)出。先進(jìn)先出(FIFO)策略：替換出最先進(jìn)入Cache的塊近期最少使用(LRU)策略：這種替換策略需隨時(shí)記錄Cache存儲(chǔ)器中各個(gè)字塊的使用情況，以便確定哪個(gè)字塊是近期最少使用的字塊。這三種策略的算法將在4.5節(jié)中介紹，這里不再贅述。512.更新策略當(dāng)內(nèi)存數(shù)據(jù)被修改時(shí)，與之對(duì)應(yīng)的Cache的數(shù)據(jù)也需要相應(yīng)修改，這個(gè)過(guò)程就是更新。但是，進(jìn)行修改時(shí)，Cache無(wú)法向CPU提供數(shù)據(jù)，因此修改Cache的時(shí)機(jī)相當(dāng)重要。常用的更新策略有：52及時(shí)更新策略：修改內(nèi)存的同時(shí)對(duì)Cache進(jìn)行修改。周期更新策略：對(duì)Cache的修改周期進(jìn)行，修改周期到的時(shí)候，無(wú)論內(nèi)存數(shù)據(jù)是否改變，都將Cache數(shù)據(jù)更新為與內(nèi)存相同的數(shù)據(jù)。執(zhí)行時(shí)更新策略：當(dāng)CPU需要某個(gè)Cache塊的數(shù)據(jù)時(shí)，將此塊與內(nèi)存中與之對(duì)應(yīng)的塊進(jìn)行比較，二者不相同時(shí)，對(duì)Cache進(jìn)行更新。思考：目前市場(chǎng)上主流微處理器（CPU）和最新技術(shù)的微處理器（CPU）的Cache的容量分別是多少？533.4虛擬存儲(chǔ)系統(tǒng)

程序要運(yùn)行，需要CPU運(yùn)算，而在計(jì)算機(jī)存儲(chǔ)中，CPU只能從內(nèi)存中讀取數(shù)據(jù)，因此要運(yùn)行的程序必須首先進(jìn)入內(nèi)存。此時(shí)，如果程序運(yùn)行所需要的內(nèi)存容量大于計(jì)算機(jī)配置的內(nèi)存容量，則程序無(wú)法運(yùn)行。而當(dāng)前，很多的計(jì)算機(jī)軟件對(duì)內(nèi)存的需求都大于實(shí)際的內(nèi)存容量，如果不采用一定的方法對(duì)內(nèi)存進(jìn)行擴(kuò)充，則計(jì)算機(jī)的應(yīng)用范圍將受到很大限制。在4.3節(jié)中，我們學(xué)習(xí)了如何依靠芯片數(shù)量的增加來(lái)增大存儲(chǔ)器容量的方法，能在一定程度上解決系統(tǒng)容量的問(wèn)題，但是芯片數(shù)量的增加必然導(dǎo)致成本的急劇提高。因此如何在現(xiàn)有的存儲(chǔ)容量基礎(chǔ)上，通過(guò)對(duì)程序進(jìn)出內(nèi)存的方法進(jìn)行設(shè)計(jì)以提高存儲(chǔ)器利用率，讓計(jì)算機(jī)能運(yùn)行比自身內(nèi)存大得多的程序便成了首要任務(wù)，于是虛擬技術(shù)便應(yīng)運(yùn)而生。54所謂虛擬存儲(chǔ)，就是采用一定的方法將一定的外存容量模擬成內(nèi)存，同時(shí)對(duì)程序進(jìn)出內(nèi)存的方式進(jìn)行管理，從而得到一個(gè)比實(shí)際內(nèi)存容量大得多的內(nèi)存空間，使得程序的運(yùn)行不受內(nèi)存大小的限制。虛擬存儲(chǔ)方法的實(shí)現(xiàn)依賴(lài)于程序的特性：55順序性。所謂程序的順序性，是指程序運(yùn)行過(guò)程中，如果要運(yùn)行第N＋1行語(yǔ)句，則大多數(shù)情況下需要先運(yùn)行第N行語(yǔ)句，即程序是在順序執(zhí)行。局部性。為了減小程序的規(guī)模，很多的程序設(shè)計(jì)語(yǔ)言都會(huì)設(shè)計(jì)循環(huán)結(jié)構(gòu)，如C語(yǔ)言中的for語(yǔ)句和while語(yǔ)句就是典型的循環(huán)語(yǔ)句，程序在執(zhí)行這類(lèi)循環(huán)語(yǔ)句時(shí)，程序的執(zhí)行范圍就限定在循環(huán)體中，而不會(huì)執(zhí)行循環(huán)體外的語(yǔ)句。執(zhí)行的語(yǔ)句限定在很小的范圍內(nèi)，即在局部范圍內(nèi)執(zhí)行，這種情況經(jīng)常會(huì)發(fā)生，這就是程序的局部性。56根據(jù)程序的以上兩個(gè)特性，需要運(yùn)行的程序不需要完全進(jìn)入內(nèi)存也可運(yùn)行。具體方法如下：根據(jù)程序的順序性和局部性原理，如果將程序分成幾塊，當(dāng)前面一個(gè)塊快運(yùn)行結(jié)束時(shí)再將下一個(gè)塊調(diào)入內(nèi)存，則程序的執(zhí)行將不會(huì)受到影響，而且程序所需要的內(nèi)存容量也將變小。本節(jié)的幾種虛擬存儲(chǔ)實(shí)現(xiàn)的方法都是基于這一原理。574.5.1頁(yè)式存儲(chǔ)系統(tǒng)在學(xué)習(xí)頁(yè)式存儲(chǔ)方法之前，我們先了解一下最簡(jiǎn)單的兩種存儲(chǔ)器分配方式。1.單一連續(xù)分配在單道環(huán)境下，計(jì)算機(jī)只允許一個(gè)作業(yè)運(yùn)行，此時(shí)所有的計(jì)算機(jī)資源被該作業(yè)獨(dú)占，包括存儲(chǔ)器。所謂單一，是指此方式下，計(jì)算機(jī)只為一個(gè)作業(yè)分配存儲(chǔ)空間。所謂連續(xù)，是指出了操作系統(tǒng)占用的存儲(chǔ)空間外，剩余的內(nèi)存空間將全部分配給作業(yè)，因此作業(yè)占用的存儲(chǔ)空間不間斷。其內(nèi)存分配情況圖4-17所示。5859系統(tǒng)運(yùn)行必須要操作系統(tǒng)統(tǒng)一管理，因此盡管計(jì)算機(jī)只運(yùn)行一個(gè)作業(yè)，也要將操作系統(tǒng)運(yùn)行的內(nèi)存空間留出來(lá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的兩個(gè)圖所示，內(nèi)存容量為128KB，操作系統(tǒng)占用32KB，剩余空間內(nèi)存96KB。如果作業(yè)大小為20KB，則剩余76KB的存儲(chǔ)空間在該作業(yè)退出系統(tǒng)前將不會(huì)被利用。60為了解決單一分配時(shí)的空間浪費(fèi)問(wèn)題，在給作業(yè)分配存儲(chǔ)空間之前，先將剩余空間分成若干區(qū)域，各區(qū)域大小可以相同也可以不同，然后再根據(jù)作業(yè)的需要進(jìn)行分配，即分區(qū)分配。612．分區(qū)分配根據(jù)分區(qū)分配時(shí)，區(qū)域的大小是否固定，分區(qū)分配又可以分為固定分區(qū)分配和可變分區(qū)分配。（1）固定分區(qū)分配。所謂固定分區(qū)分配，是指先將內(nèi)存分成若干固定區(qū)域，區(qū)域大小一經(jīng)確定將永遠(yuǎn)不再改變，每個(gè)作業(yè)占用一個(gè)區(qū)域。62分區(qū)過(guò)程中，要給作業(yè)分配內(nèi)存，必須首先要知道哪些分區(qū)是空閑（未分配）的，這些空閑區(qū)的容量是多大。因此系統(tǒng)需要設(shè)置一種表格來(lái)紀(jì)錄這些信息，常常采用的方法是分區(qū)分配表。為了滿(mǎn)足正常分配的要求，分區(qū)分配表應(yīng)該包含每個(gè)分區(qū)的起始地址、大小和分配情況等信息。分配前，系統(tǒng)先查找分區(qū)分配表，如果能找到一個(gè)滿(mǎn)足作業(yè)要求的的分區(qū)，則將此分區(qū)分配給作業(yè)。在固定分區(qū)中，分區(qū)分配表直接決定了是否能正確給各作業(yè)分配存儲(chǔ)空間，所以為了保證分區(qū)的正確性，需要隨時(shí)更新分區(qū)分配表的信息。633.4.1.分頁(yè)虛擬存儲(chǔ)在可變分區(qū)分配中，為了解決空閑區(qū)不連續(xù)問(wèn)題而采用了移動(dòng)作業(yè)的內(nèi)存空間的方法，系統(tǒng)開(kāi)銷(xiāo)非常大，而且采用的方法是讓硬件適應(yīng)軟件的方法。其實(shí)解決上述問(wèn)題的也可以從另一方面入手，那就是讓軟件去適應(yīng)硬件。這里所說(shuō)的軟件是作業(yè)，硬件是內(nèi)存。既然移動(dòng)內(nèi)存需要花費(fèi)很多CPU時(shí)間，那就將作業(yè)劃分為幾個(gè)部分，每個(gè)部分存在一個(gè)空閑區(qū)域中，這樣，要保存一個(gè)較大的作業(yè)就不需要找到一個(gè)比作業(yè)空間大的空閑空間，而只需要多個(gè)空閑塊的容量之和大于作業(yè)容量即可。64為了方便內(nèi)存管理，人們首先想到的是將作業(yè)按統(tǒng)一的大小劃分成多個(gè)“頁(yè)”，同時(shí)也將內(nèi)存按頁(yè)面大小劃分成若干個(gè)“物理塊”（簡(jiǎn)稱(chēng)“塊”），并對(duì)頁(yè)和塊按地址從低到高的順序編號(hào)。分配內(nèi)存時(shí)，因?yàn)轫?yè)的大小與塊的大小相同，所以每個(gè)頁(yè)就對(duì)應(yīng)一個(gè)塊。此時(shí)，只要剩余塊的數(shù)量不小于作業(yè)頁(yè)的數(shù)量，則不需要作業(yè)占用的所有塊地址都連續(xù)。也就不需要將內(nèi)存的所有空閑區(qū)域移動(dòng)到一起了。65采用分頁(yè)存儲(chǔ)能用不連續(xù)的存儲(chǔ)空間存儲(chǔ)作業(yè)，但是也將引出新的問(wèn)題，那就是如何讓頁(yè)的邏輯關(guān)系不變，即當(dāng)前面的頁(yè)運(yùn)行完的時(shí)候，如何尋找下一個(gè)應(yīng)該運(yùn)行的頁(yè)。為了解決這一問(wèn)題，在分頁(yè)存儲(chǔ)中，需要一種新的數(shù)據(jù)結(jié)構(gòu)――頁(yè)表。頁(yè)表的結(jié)構(gòu)見(jiàn)表4-6所示。66頁(yè)號(hào)塊號(hào)010145250325415……67頁(yè)表的每一行就是一個(gè)頁(yè)面的信息，分為兩項(xiàng)，第一項(xiàng)是頁(yè)號(hào)，第二項(xiàng)是該頁(yè)對(duì)應(yīng)的塊。作業(yè)執(zhí)行時(shí)，所有程序和數(shù)據(jù)必須從內(nèi)存塊中取得。因此在執(zhí)行某一個(gè)塊的程序前，系統(tǒng)按頁(yè)號(hào)從低到高的順序查找頁(yè)表，根據(jù)頁(yè)表的記錄找到該頁(yè)對(duì)應(yīng)的物理塊，進(jìn)而執(zhí)行塊中的程序和數(shù)據(jù)。分頁(yè)時(shí)是按邏輯地址進(jìn)行的，頁(yè)的順序就是程序執(zhí)行的先后順序，因此，盡管將一個(gè)作業(yè)分成很多頁(yè)，作業(yè)的執(zhí)行順序也不會(huì)受到影響。然而，程序員是按照邏輯地址編程，程序卻是按照其物理地址執(zhí)行，因此，在分頁(yè)式存儲(chǔ)管理系統(tǒng)中，邏輯地址是否能轉(zhuǎn)換為正確的物理地址，將直接影響作業(yè)執(zhí)行的正確性。邏輯地址結(jié)構(gòu)如圖4-26所示。頁(yè)號(hào)頁(yè)內(nèi)地址68作業(yè)頁(yè)的大小和物理塊的大小相同，在地址轉(zhuǎn)換時(shí)，頁(yè)內(nèi)地址可以直接作為塊內(nèi)地址。但是，頁(yè)號(hào)和物理塊號(hào)并不能一一對(duì)應(yīng)，如表4-6中，0號(hào)頁(yè)面對(duì)應(yīng)于10號(hào)塊，1號(hào)頁(yè)面對(duì)應(yīng)于45號(hào)塊等等，因此不能用頁(yè)號(hào)直接訪(fǎng)問(wèn)物理塊。因?yàn)轫?yè)表記錄這頁(yè)與塊的對(duì)應(yīng)關(guān)系，所以作業(yè)執(zhí)行時(shí)，系統(tǒng)需要經(jīng)常通過(guò)訪(fǎng)問(wèn)頁(yè)表將邏輯地址轉(zhuǎn)換為物理地址。其過(guò)程如圖4-27所示。6970分頁(yè)系統(tǒng)雖然克服了前面幾種分區(qū)方法的缺點(diǎn)，很好地克服了碎片問(wèn)題，但是系統(tǒng)的空閑物理塊數(shù)量必須不小于作業(yè)的頁(yè)數(shù)量時(shí)，否則作業(yè)也將無(wú)法運(yùn)行。根據(jù)程序的順序性和局部性原理，程序要執(zhí)行并不需要所有的頁(yè)面同時(shí)進(jìn)入內(nèi)存，只需要正在運(yùn)行或馬上即將運(yùn)行的頁(yè)面在內(nèi)存中即可，即只允許少量頁(yè)面進(jìn)入內(nèi)存，作業(yè)一樣能運(yùn)行。其中最簡(jiǎn)單可行的辦法就是請(qǐng)求分頁(yè)存儲(chǔ)系統(tǒng)。714.請(qǐng)求分頁(yè)虛擬存儲(chǔ)所謂“請(qǐng)求”，是指不將作業(yè)的所有頁(yè)同時(shí)放入內(nèi)存，而是作業(yè)在運(yùn)行過(guò)程中需要某個(gè)頁(yè)時(shí)，如果該頁(yè)沒(méi)有在內(nèi)存中，則請(qǐng)求中斷，讓系統(tǒng)將該頁(yè)從外存放入內(nèi)存。因此，在給作業(yè)分配空間時(shí)，不需要按作業(yè)的頁(yè)數(shù)分配物理塊，而是只給作業(yè)分配少量的物理塊，然后通過(guò)一定的置換機(jī)制實(shí)現(xiàn)用少量的物理塊運(yùn)行較大的作業(yè)。所謂“置換”是指當(dāng)作業(yè)需要某個(gè)沒(méi)有在內(nèi)存中的頁(yè)時(shí)，如果系統(tǒng)分配給作業(yè)的幾個(gè)物理塊已經(jīng)全部被占滿(mǎn)，則根據(jù)一定的算法將內(nèi)存中的頁(yè)面調(diào)到外存，而將馬上要運(yùn)行的頁(yè)調(diào)入內(nèi)存。比如：系統(tǒng)分配給某作業(yè)三個(gè)物理塊，此三個(gè)物理塊分別保存作業(yè)的2、4和6號(hào)頁(yè)，當(dāng)作業(yè)需要運(yùn)行5號(hào)頁(yè)時(shí)，因?yàn)橄到y(tǒng)分配給該作業(yè)的三個(gè)塊已經(jīng)被占滿(mǎn)，則需要從2、4和6號(hào)頁(yè)中選擇淘汰一個(gè)，將其調(diào)出內(nèi)存，而將5號(hào)頁(yè)面放入內(nèi)存運(yùn)行。如果置換算法設(shè)計(jì)不當(dāng)，則頁(yè)將會(huì)頻繁地調(diào)入調(diào)出內(nèi)存，增大系統(tǒng)開(kāi)銷(xiāo)，降低系統(tǒng)性能，特別是“顛簸”問(wèn)題的存在，給置換算法提出了很高的要求。72“顛簸”是指剛調(diào)出內(nèi)存的頁(yè)，由于馬上又運(yùn)行，則需要重新將此頁(yè)面調(diào)入內(nèi)存。所以選擇何種置換算法將直接影響請(qǐng)求分頁(yè)虛擬存儲(chǔ)的性能。常用的頁(yè)面置換算法主要有：先進(jìn)先出置換算法、最久不用置換算法和最近最久未用置換算法。73（1）先進(jìn)先出置換算法采用先進(jìn)先出（FIFO）置換算法，淘汰的頁(yè)是最先進(jìn)入內(nèi)存的頁(yè)先進(jìn)先出置換算法利用了隊(duì)列的特點(diǎn)得以實(shí)現(xiàn)。隊(duì)列就是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，最先進(jìn)入隊(duì)列的元素排在隊(duì)首，第二進(jìn)來(lái)的元素排在隊(duì)首后面，依此類(lèi)推，最后進(jìn)入的隊(duì)列的元素排在隊(duì)尾。不管隊(duì)列中的元素如何變化，隊(duì)首元素永遠(yuǎn)是隊(duì)列所有元素中最先進(jìn)入的，因此在采用隊(duì)列的方法時(shí)，要淘汰一個(gè)頁(yè)面的時(shí)候只需要將隊(duì)首元素淘汰，此時(shí)第二個(gè)元素將成為新的隊(duì)首元素，然后將作業(yè)需要的新頁(yè)放在隊(duì)尾位置，如此循環(huán)就可以實(shí)現(xiàn)新老頁(yè)的替換。74置換過(guò)程中要注意缺頁(yè)和置換發(fā)生的時(shí)機(jī)。缺頁(yè)是在作業(yè)要執(zhí)行的頁(yè)沒(méi)有在內(nèi)存中時(shí)發(fā)生，跟系統(tǒng)分配給作業(yè)的幾個(gè)塊是否被占滿(mǎn)無(wú)關(guān)。而置換則是在作業(yè)要執(zhí)行的頁(yè)沒(méi)有在系統(tǒng)中，且分配給作業(yè)的塊已經(jīng)被占滿(mǎn)的時(shí)候發(fā)生。本例中的前3個(gè)頁(yè)進(jìn)入內(nèi)存時(shí)，內(nèi)存塊沒(méi)有被占滿(mǎn)，所以只發(fā)生了缺頁(yè)，沒(méi)有發(fā)生置換；后面的新頁(yè)進(jìn)入內(nèi)存時(shí)，內(nèi)存塊已經(jīng)被占滿(mǎn)，所以將同時(shí)發(fā)生缺頁(yè)和置換。當(dāng)然，實(shí)現(xiàn)FIFO還有其他方法，不過(guò)用隊(duì)列實(shí)現(xiàn)FIFO，方法簡(jiǎn)單、不容易出錯(cuò)，建議讀者熟悉此方法。75（2）最久不用置換算法FIFO置換算法中，置換的頁(yè)是最先進(jìn)入內(nèi)存的頁(yè)，這種方法雖然實(shí)現(xiàn)簡(jiǎn)單，但是性能卻并不好，容易出現(xiàn)“顛簸”現(xiàn)象。理論上，在相同的頁(yè)面使用順序時(shí)，最久不用置換算法是性能最好的算法，但是，實(shí)際上，作業(yè)執(zhí)行過(guò)程中，很難確定頁(yè)的使用順序，也就無(wú)法確定內(nèi)存中的哪個(gè)頁(yè)為將來(lái)最久不會(huì)使用的頁(yè)，因此該算法是無(wú)法實(shí)現(xiàn)的。76（3）最近最久未用置換算法（LeastRecentlyUsed，LRU）FIFO置換算法雖然實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單，但是性能較差；最久不用置換算法性能最好，但是無(wú)法實(shí)現(xiàn)。在實(shí)際使用時(shí)，這兩種算法都很少使用，經(jīng)常使用的是最近最近未用置換算法。77根據(jù)程序執(zhí)行的順序性和局部性，當(dāng)一個(gè)頁(yè)剛剛被使用過(guò)，則該頁(yè)被再次使用的幾率較高；相反，越早使用過(guò)的頁(yè)，被再次使用的幾率越低。最近最久未用算法就是基于作業(yè)的這一特性設(shè)計(jì)的。最近最久未用置換算法在進(jìn)行頁(yè)面置換時(shí)，總是將處于內(nèi)存的幾個(gè)頁(yè)中，最后一次使用時(shí)間距離當(dāng)前時(shí)間最久的那一個(gè)頁(yè)淘汰。在用該算法進(jìn)行頁(yè)面置換時(shí)，必須首先要確定哪個(gè)頁(yè)是最后被使用的。783.4.2段式虛擬存儲(chǔ)通過(guò)前面的學(xué)習(xí)，我們知道，頁(yè)式虛擬存儲(chǔ)因?yàn)轫?yè)的大小跟物理塊的大小相同，所以很大程度上解決了存儲(chǔ)管理的碎片問(wèn)題。但是按照固定的大小對(duì)作業(yè)進(jìn)行分頁(yè)，往往會(huì)破壞作業(yè)本身的邏輯結(jié)構(gòu)，因?yàn)楝F(xiàn)在的程序大都按其功能分為很多的子程序，而子程序的大小各不相同，更不會(huì)是剛好頁(yè)大小的整數(shù)倍，所以如果單純對(duì)作業(yè)進(jìn)行分頁(yè)，則有的頁(yè)可能會(huì)包含有一個(gè)子程序的結(jié)尾部分和另外一個(gè)頁(yè)的開(kāi)始部分。這就完全破壞了程序的模塊化。然而模塊化思想解決軟件危機(jī)的最基本的思想，編程序時(shí)要注意程序模塊化，存儲(chǔ)管理時(shí)更要注意保持子程序的完整性。791.分段原理程序模塊化的最基本的思想是為每一個(gè)功能都編制一段程序，比如學(xué)生學(xué)籍管理系統(tǒng)可以分為數(shù)據(jù)輸入、數(shù)據(jù)維護(hù)、用戶(hù)檢索等功能，不同功能由不同的模塊完成，模塊間可能會(huì)互相調(diào)用。為了保證程序的正常執(zhí)行和模塊間的正確調(diào)用，每一個(gè)模塊都必須有自己的標(biāo)識(shí)符，系統(tǒng)也可以通過(guò)標(biāo)識(shí)符區(qū)分不同功能的模塊，因此可以用模塊所完成的功能對(duì)模塊進(jìn)行命名，將模塊名作為標(biāo)識(shí)符，并對(duì)各模塊進(jìn)行編號(hào)。80程序的每一個(gè)模塊都可以作為一個(gè)段，模塊的編號(hào)可以作為段的編號(hào)。為了對(duì)模塊內(nèi)的語(yǔ)句進(jìn)行正確尋址，也需要有一個(gè)段內(nèi)地址。因此，分段存儲(chǔ)管理下，地址結(jié)構(gòu)如圖4-32所示。段號(hào)段內(nèi)地址81要對(duì)某個(gè)子程序中的某個(gè)語(yǔ)句進(jìn)行訪(fǎng)問(wèn)，首先知道該語(yǔ)句所在的子程序的編號(hào)，即段號(hào)，其次要知道該語(yǔ)句相對(duì)于子程序的起始地址的偏移量，即段內(nèi)地址。在如圖3-32所示的結(jié)構(gòu)中，當(dāng)知道某個(gè)語(yǔ)句的地址時(shí)，系統(tǒng)將首先取出地址中的段號(hào)，根據(jù)段號(hào)找到相應(yīng)的子程序，然后再通過(guò)地址中的段內(nèi)地址找到語(yǔ)句。822.存儲(chǔ)空間分配段式存儲(chǔ)管理系統(tǒng)中，由于按照邏輯關(guān)系將作業(yè)分成了若干段，所以沒(méi)有必要給作業(yè)分配一個(gè)連續(xù)的地址空間，只需要給每個(gè)段分配一個(gè)連續(xù)的空間即可。因此在段式存儲(chǔ)管理方式下，邏輯相鄰的段可能在物理地址上不連續(xù)。如圖4-33所示。8384圖3-33中，作業(yè)分成了4段，各段占用不連續(xù)的內(nèi)存空間。段1大小為20KB，占用起始地址為80KB的空間；段2大小為30KB，占用起始地址為160KB的空間；段3大小為10KB，占用起始地址為130KB的空間；段4大小為40KB，占用起始地址為250KB的空間。853.段表圖3-33中，假如作業(yè)按照段1、段2、段3、段4的順序執(zhí)行，段空間不連續(xù)，當(dāng)作業(yè)執(zhí)行完前一個(gè)段后，如何知道下一個(gè)段的內(nèi)存起始地址呢？因此必須有種數(shù)據(jù)結(jié)構(gòu)來(lái)保存各段對(duì)應(yīng)的物理空間，其中應(yīng)該包括段號(hào)、分給該段的空間的起始地址和長(zhǎng)度等信息，段表就是這樣一種數(shù)據(jù)結(jié)構(gòu)，能記錄段的空間的各種信息。圖4-33所示的段空間分配狀態(tài)所對(duì)應(yīng)的段表如表4-7所示。86段號(hào)起始地址（K）長(zhǎng)度（KB）1802021603031301042504087設(shè)置段表后，當(dāng)作業(yè)開(kāi)始運(yùn)行時(shí)，首先查找段表，找到第一個(gè)段的內(nèi)存起始地址，并根據(jù)起始地址和長(zhǎng)度計(jì)算出終止地址，當(dāng)作業(yè)執(zhí)行到第一段的終止地址時(shí)，根據(jù)段表記錄再去查找第二個(gè)段對(duì)應(yīng)的內(nèi)存地址，如此反復(fù)，即可在段表的輔助下將作業(yè)的4個(gè)段正確執(zhí)行。88上述過(guò)程實(shí)際是將作業(yè)的邏輯地址轉(zhuǎn)換成物理地址的過(guò)程。作業(yè)根據(jù)將要執(zhí)行的語(yǔ)句的邏輯地址計(jì)算出段號(hào)和段內(nèi)地址，然后根據(jù)邏輯地址查找段表，得到相應(yīng)的內(nèi)存段的起始地址，將此起始地址加上段內(nèi)地址即是該語(yǔ)句的物理地址。此地址變換過(guò)程跟分頁(yè)式存儲(chǔ)管理地址變換過(guò)程類(lèi)似，如圖4-34所示。8990圖中3-31所示地址轉(zhuǎn)換過(guò)程中的最后一步是進(jìn)行地址計(jì)算，意思是將段內(nèi)地址和查段表得到與段對(duì)應(yīng)的內(nèi)存區(qū)的起始地址相加得到將要訪(fǎng)問(wèn)的語(yǔ)句的物理地址，從而實(shí)現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換。913.4.3段頁(yè)式虛擬存儲(chǔ)段式存儲(chǔ)管理保證了程序的邏輯性不遭破壞，