第5章存儲(chǔ)體系及結(jié)構(gòu)04

1、計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理第第5章章5.1 存儲(chǔ)系統(tǒng)的組成存儲(chǔ)系統(tǒng)的組成5.2 主存儲(chǔ)器的組織主存儲(chǔ)器的組織5.3 半導(dǎo)體隨機(jī)存儲(chǔ)器和只讀存儲(chǔ)器半導(dǎo)體隨機(jī)存儲(chǔ)器和只讀存儲(chǔ)器5.4 主存儲(chǔ)器的連接與控制主存儲(chǔ)器的連接與控制5.5 提高提高主存讀寫(xiě)速度的主存讀寫(xiě)速度的技術(shù)技術(shù)5.6 多體交叉存儲(chǔ)技術(shù)多體交叉存儲(chǔ)技術(shù)5.7 高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器5.8 虛擬存儲(chǔ)器虛擬存儲(chǔ)器計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理存儲(chǔ)層次存儲(chǔ)層次 1. 主主-輔存存儲(chǔ)層次輔存存儲(chǔ)層次 ： 問(wèn)題：?jiǎn)栴}：計(jì)算機(jī)主存容量相對(duì)于程序員所需要的容量來(lái)說(shuō)總是太小，計(jì)算機(jī)主存容量相對(duì)于程序員所需要的容量來(lái)說(shuō)總是太小，程序與數(shù)據(jù)從輔存調(diào)

2、入主存如果由程序員自己安排的，程序員必須花費(fèi)程序與數(shù)據(jù)從輔存調(diào)入主存如果由程序員自己安排的，程序員必須花費(fèi)很大精力和時(shí)間把大程序預(yù)先分成塊，確定好這些程序塊在輔存中的位很大精力和時(shí)間把大程序預(yù)先分成塊，確定好這些程序塊在輔存中的位置和裝入主存的地址，而且還要預(yù)先安排好程序運(yùn)行時(shí)各塊如何和何時(shí)置和裝入主存的地址，而且還要預(yù)先安排好程序運(yùn)行時(shí)各塊如何和何時(shí)調(diào)入調(diào)出，因此存在存儲(chǔ)空間的分配問(wèn)題。調(diào)入調(diào)出，因此存在存儲(chǔ)空間的分配問(wèn)題。好在操作系統(tǒng)的形成和發(fā)展好在操作系統(tǒng)的形成和發(fā)展使得程序員盡可能擺脫主、輔存之間的地址定位使得程序員盡可能擺脫主、輔存之間的地址定位，同時(shí)形成了支持這些，同時(shí)形成了支持這

3、些功能的功能的“輔助硬件輔助硬件”，通過(guò)軟件、硬件的結(jié)合，把主存和輔存統(tǒng)一成了，通過(guò)軟件、硬件的結(jié)合，把主存和輔存統(tǒng)一成了一個(gè)整體，如圖所示。這時(shí)，由主存、輔存形成了一個(gè)存儲(chǔ)層次，即存一個(gè)整體，如圖所示。這時(shí)，由主存、輔存形成了一個(gè)存儲(chǔ)層次，即存儲(chǔ)系統(tǒng)。從整體看，其速度接近于主存的速度，其容量則接近于輔存的儲(chǔ)系統(tǒng)。從整體看，其速度接近于主存的速度，其容量則接近于輔存的容量，每位的平均價(jià)格也接近于廉價(jià)的慢速的輔存平均價(jià)格。這種系統(tǒng)容量，每位的平均價(jià)格也接近于廉價(jià)的慢速的輔存平均價(jià)格。這種系統(tǒng)不斷發(fā)展和完善，就逐步形成了現(xiàn)在廣泛使用的虛擬存儲(chǔ)系統(tǒng)。在系統(tǒng)不斷發(fā)展和完善，就逐步形成了現(xiàn)在廣泛使用的虛

4、擬存儲(chǔ)系統(tǒng)。在系統(tǒng)中，應(yīng)用程序員可用機(jī)器指令地址碼對(duì)整個(gè)程序統(tǒng)一編址，如同程序員中，應(yīng)用程序員可用機(jī)器指令地址碼對(duì)整個(gè)程序統(tǒng)一編址，如同程序員具有對(duì)應(yīng)這個(gè)地址碼寬度的全部虛存空間一樣。該空間可以比主存實(shí)際具有對(duì)應(yīng)這個(gè)地址碼寬度的全部虛存空間一樣。該空間可以比主存實(shí)際空間大得多，以致可以存得下整個(gè)程序。這種指令地址碼稱(chēng)為虛地址空間大得多，以致可以存得下整個(gè)程序。這種指令地址碼稱(chēng)為虛地址（虛存地址、虛擬地址）或邏輯地址，其對(duì)應(yīng)的存儲(chǔ)容量稱(chēng)為虛存容量（虛存地址、虛擬地址）或邏輯地址，其對(duì)應(yīng)的存儲(chǔ)容量稱(chēng)為虛存容量或虛存空間；而把實(shí)際主存的地址稱(chēng)為物理地址、實(shí)（存）地址，其對(duì)或虛存空間；而把實(shí)際主存的地

5、址稱(chēng)為物理地址、實(shí)（存）地址，其對(duì)應(yīng)的存儲(chǔ)容量稱(chēng)為主存容量、實(shí)存容量或?qū)崳ㄖ鳎┐婵臻g應(yīng)的存儲(chǔ)容量稱(chēng)為主存容量、實(shí)存容量或?qū)崳ㄖ鳎┐婵臻g計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理2. CACHE-主存存儲(chǔ)層次主存存儲(chǔ)層次當(dāng)用虛地址訪問(wèn)主存時(shí)，機(jī)器自動(dòng)地把它經(jīng)輔助軟件、硬件變換成主存當(dāng)用虛地址訪問(wèn)主存時(shí)，機(jī)器自動(dòng)地把它經(jīng)輔助軟件、硬件變換成主存實(shí)地址。查看這個(gè)地址所對(duì)應(yīng)的單元內(nèi)容是否已經(jīng)裝入主存，如果在主實(shí)地址。查看這個(gè)地址所對(duì)應(yīng)的單元內(nèi)容是否已經(jīng)裝入主存，如果在主存就進(jìn)行訪問(wèn)，如果不在主存內(nèi)就經(jīng)輔助軟件、硬件把它所在的那塊程存就進(jìn)行訪問(wèn)，如果不在主存內(nèi)就經(jīng)輔助軟件、硬件把它所在的那

6、塊程序和數(shù)據(jù)由輔存調(diào)入主存，而后進(jìn)行訪問(wèn)。這些操作都不必由程序員來(lái)序和數(shù)據(jù)由輔存調(diào)入主存，而后進(jìn)行訪問(wèn)。這些操作都不必由程序員來(lái)安排，也就是說(shuō)，對(duì)應(yīng)用程員員是透明的。安排，也就是說(shuō)，對(duì)應(yīng)用程員員是透明的。 主主-輔存層次解決了存儲(chǔ)器輔存層次解決了存儲(chǔ)器大容量要求和低成本之間的矛盾。大容量要求和低成本之間的矛盾。 在速度方面，計(jì)算機(jī)的主存和在速度方面，計(jì)算機(jī)的主存和CPU間間保持了大約一個(gè)數(shù)量級(jí)的差距。顯然這個(gè)差距限制了保持了大約一個(gè)數(shù)量級(jí)的差距。顯然這個(gè)差距限制了CPU速度潛力的發(fā)速度潛力的發(fā)揮。為了彌合這個(gè)差距，僅采用一種工藝的單一存儲(chǔ)器是行不通的，必?fù)]。為了彌合這個(gè)差距，僅采用一種工藝的單

7、一存儲(chǔ)器是行不通的，必須進(jìn)一步從計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)和組織上去研究。設(shè)置高速緩沖存儲(chǔ)器須進(jìn)一步從計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)和組織上去研究。設(shè)置高速緩沖存儲(chǔ)器（Cache）是解決存取速度的重要方法。在）是解決存取速度的重要方法。在CPU和主存中間設(shè)置高速緩和主存中間設(shè)置高速緩沖存儲(chǔ)器，構(gòu)成高速緩存（沖存儲(chǔ)器，構(gòu)成高速緩存（Cache）-主存層次，要求主存層次，要求Cache在速度上能在速度上能跟得上跟得上CPU的要求。的要求。Cache-主存間的地址映象和調(diào)度吸取了比它較早出主存間的地址映象和調(diào)度吸取了比它較早出現(xiàn)的主現(xiàn)的主-輔存存儲(chǔ)層次的技術(shù)，不同的是因其速度要求高，不是由軟、硬輔存存儲(chǔ)層次的技術(shù)，不同的是因其

8、速度要求高，不是由軟、硬件結(jié)合而完全由硬件來(lái)實(shí)現(xiàn)，如圖所示。件結(jié)合而完全由硬件來(lái)實(shí)現(xiàn)，如圖所示。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理1.程序的局部性原理程序的局部性原理 程序的局部性包括：時(shí)間局部性和空間局部程序的局部性包括：時(shí)間局部性和空間局部性。性。 時(shí)間局部性是指如果一個(gè)存儲(chǔ)單元被訪問(wèn)，時(shí)間局部性是指如果一個(gè)存儲(chǔ)單元被訪問(wèn)，則可能該單元會(huì)很快被再次訪問(wèn)。這是因?yàn)槌虅t可能該單元會(huì)很快被再次訪問(wèn)。這是因?yàn)槌绦虼嬖谥h(huán)。序存在著循環(huán)。 空間局部性是指如果一個(gè)存儲(chǔ)單元被訪問(wèn)，空間局部性是指如果一個(gè)存儲(chǔ)單元被訪問(wèn)，則該單元鄰近的單元也可能很快被訪問(wèn)。這是則該單元鄰近的單元也可

9、能很快被訪問(wèn)。這是因?yàn)槌绦蛑写蟛糠种噶钍琼樞虼鎯?chǔ)、順序執(zhí)行因?yàn)槌绦蛑写蟛糠种噶钍琼樞虼鎯?chǔ)、順序執(zhí)行的，數(shù)據(jù)一般也是以向量、數(shù)組、樹(shù)、表等形的，數(shù)據(jù)一般也是以向量、數(shù)組、樹(shù)、表等形式簇聚地存儲(chǔ)在一起的。式簇聚地存儲(chǔ)在一起的。5.7.1 高速存儲(chǔ)工作原理高速存儲(chǔ)工作原理 計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.7 高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器 高速緩沖技術(shù)就是利用程序的局部性高速緩沖技術(shù)就是利用程序的局部性原理，把程序中正在使用的部分存放在一原理，把程序中正在使用的部分存放在一個(gè)高速的容量較小的個(gè)高速的容量較小的Cache中，使中，使CPU的的訪存操作大多數(shù)針對(duì)訪存操作大多數(shù)針對(duì)Cache進(jìn)行，從而使進(jìn)行

10、，從而使程序的執(zhí)行速度大大提高。程序的執(zhí)行速度大大提高。2.Cache的基本結(jié)構(gòu)的基本結(jié)構(gòu) Cache和主存都被分成若干個(gè)大小相和主存都被分成若干個(gè)大小相等的塊，每塊由若干字節(jié)組成。由于等的塊，每塊由若干字節(jié)組成。由于Cache的容量遠(yuǎn)小于主存的容量，它保存的容量遠(yuǎn)小于主存的容量，它保存的信息只是主存中最活躍的若干塊的的信息只是主存中最活躍的若干塊的副本副本。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理 高速緩沖存儲(chǔ)器是存在于主存與高速緩沖存儲(chǔ)器是存在于主存與CPU之間的一級(jí)存儲(chǔ)之間的一級(jí)存儲(chǔ)器，器， 由靜態(tài)存儲(chǔ)芯片由靜態(tài)存儲(chǔ)芯片(SRAM)組成，容量比較小但速度比組成，容量比較小但速度比主存高得多，主存高得

11、多， 接近于接近于CPU的速度。的速度。主要由三大部分組成：主要由三大部分組成：Cache存儲(chǔ)體：存儲(chǔ)體： 存放由主存調(diào)入的指令與數(shù)據(jù)塊。存放由主存調(diào)入的指令與數(shù)據(jù)塊。地址轉(zhuǎn)換部件：建立目錄表以實(shí)現(xiàn)主存地址到緩存地址轉(zhuǎn)換部件：建立目錄表以實(shí)現(xiàn)主存地址到緩存 地址的轉(zhuǎn)換。地址的轉(zhuǎn)換。替換部件：在緩存已滿時(shí)按一定策略進(jìn)行數(shù)據(jù)塊替換，替換部件：在緩存已滿時(shí)按一定策略進(jìn)行數(shù)據(jù)塊替換， 并修改地址轉(zhuǎn)換部件。并修改地址轉(zhuǎn)換部件。Cache的結(jié)構(gòu)的結(jié)構(gòu)計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理Cache的工作原理的工作原理 高速緩沖存儲(chǔ)器通常由高速緩沖存儲(chǔ)器通常由高速存儲(chǔ)器、聯(lián)想存儲(chǔ)器、替換高

12、速存儲(chǔ)器、聯(lián)想存儲(chǔ)器、替換邏輯電路和相應(yīng)的控制線路組成。邏輯電路和相應(yīng)的控制線路組成。 在有高速緩沖存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，中央處理器存取在有高速緩沖存儲(chǔ)器的計(jì)算機(jī)系統(tǒng)中，中央處理器存取主存儲(chǔ)器的地址劃分為行號(hào)、列號(hào)和組內(nèi)地址三個(gè)字段。于主存儲(chǔ)器的地址劃分為行號(hào)、列號(hào)和組內(nèi)地址三個(gè)字段。于是，主存儲(chǔ)器就在邏輯上劃分為若干行；每行劃分為若干的是，主存儲(chǔ)器就在邏輯上劃分為若干行；每行劃分為若干的存儲(chǔ)單元組；每組包含幾個(gè)或幾十個(gè)字。高速存儲(chǔ)器也相應(yīng)存儲(chǔ)單元組；每組包含幾個(gè)或幾十個(gè)字。高速存儲(chǔ)器也相應(yīng)地劃分為行和列的存儲(chǔ)單元組。二者的列數(shù)相同，組的大小地劃分為行和列的存儲(chǔ)單元組。二者的列數(shù)相同，組的大小

13、也相同，但高速存儲(chǔ)器的行數(shù)卻比主存儲(chǔ)器的行數(shù)少得多。也相同，但高速存儲(chǔ)器的行數(shù)卻比主存儲(chǔ)器的行數(shù)少得多。 聯(lián)想存儲(chǔ)器用于地址聯(lián)想，有與高速存儲(chǔ)器相同行數(shù)和聯(lián)想存儲(chǔ)器用于地址聯(lián)想，有與高速存儲(chǔ)器相同行數(shù)和列數(shù)的存儲(chǔ)單元。當(dāng)主存儲(chǔ)器某一列某一行存儲(chǔ)單元組調(diào)入列數(shù)的存儲(chǔ)單元。當(dāng)主存儲(chǔ)器某一列某一行存儲(chǔ)單元組調(diào)入高速存儲(chǔ)器同一列某一空著的存儲(chǔ)單元組時(shí)，與聯(lián)想存儲(chǔ)器高速存儲(chǔ)器同一列某一空著的存儲(chǔ)單元組時(shí)，與聯(lián)想存儲(chǔ)器對(duì)應(yīng)位置的存儲(chǔ)單元就記錄調(diào)入的存儲(chǔ)單元組在主存儲(chǔ)器中對(duì)應(yīng)位置的存儲(chǔ)單元就記錄調(diào)入的存儲(chǔ)單元組在主存儲(chǔ)器中的行號(hào)。的行號(hào)。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理 當(dāng)中央處理器存取主存儲(chǔ)器時(shí)，硬件首先自動(dòng)

14、對(duì)存取當(dāng)中央處理器存取主存儲(chǔ)器時(shí)，硬件首先自動(dòng)對(duì)存取地址的列號(hào)字段進(jìn)行譯碼，以便將聯(lián)想存儲(chǔ)器該列的全部地址的列號(hào)字段進(jìn)行譯碼，以便將聯(lián)想存儲(chǔ)器該列的全部行號(hào)與存取主存儲(chǔ)器地址的行號(hào)字段進(jìn)行比較：若有相同行號(hào)與存取主存儲(chǔ)器地址的行號(hào)字段進(jìn)行比較：若有相同的，表明要存取的主存儲(chǔ)器單元已在高速存儲(chǔ)器中，稱(chēng)為的，表明要存取的主存儲(chǔ)器單元已在高速存儲(chǔ)器中，稱(chēng)為命中，硬件就將存取主存儲(chǔ)器的地址映射為高速存儲(chǔ)器的命中，硬件就將存取主存儲(chǔ)器的地址映射為高速存儲(chǔ)器的地址并執(zhí)行存取操作；若都不相同，表明該單元不在高速地址并執(zhí)行存取操作；若都不相同，表明該單元不在高速存儲(chǔ)器中，稱(chēng)為脫靶，硬件將執(zhí)行存取主存儲(chǔ)器操作并

15、自存儲(chǔ)器中，稱(chēng)為脫靶，硬件將執(zhí)行存取主存儲(chǔ)器操作并自動(dòng)將該單元所在的那一主存儲(chǔ)器單元組調(diào)入高速存儲(chǔ)器相動(dòng)將該單元所在的那一主存儲(chǔ)器單元組調(diào)入高速存儲(chǔ)器相同列中空著的存儲(chǔ)單元組中，同時(shí)將該組在主存儲(chǔ)器中的同列中空著的存儲(chǔ)單元組中，同時(shí)將該組在主存儲(chǔ)器中的行號(hào)存入聯(lián)想存儲(chǔ)器對(duì)應(yīng)位置的單元內(nèi)。行號(hào)存入聯(lián)想存儲(chǔ)器對(duì)應(yīng)位置的單元內(nèi)。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理 當(dāng)出現(xiàn)脫靶而高速存儲(chǔ)器對(duì)應(yīng)列中沒(méi)有空的位置時(shí)，當(dāng)出現(xiàn)脫靶而高速存儲(chǔ)器對(duì)應(yīng)列中沒(méi)有空的位置時(shí)，便淘汰該列中的某一組以騰出位置存放新調(diào)入的組，這稱(chēng)便淘汰該列中的某一組以騰出位置存放新調(diào)入的組，這稱(chēng)為替換。為替換。 確定替換的規(guī)則叫替換算法，常用的替換

16、算法有確定替換的規(guī)則叫替換算法，常用的替換算法有: 最近最少使用算法（最近最少使用算法（LRU）、）、 先進(jìn)先出法（先進(jìn)先出法（FIFO）、）、 隨機(jī)法（隨機(jī)法（RAND）等。）等。 替換邏輯電路就是執(zhí)行這個(gè)功能的。替換邏輯電路就是執(zhí)行這個(gè)功能的。 另外，當(dāng)執(zhí)行寫(xiě)主存儲(chǔ)器操作時(shí)，為保持主存儲(chǔ)器和另外，當(dāng)執(zhí)行寫(xiě)主存儲(chǔ)器操作時(shí)，為保持主存儲(chǔ)器和高速存儲(chǔ)器內(nèi)容的一致性，對(duì)命中和脫靶須分別處理。高速存儲(chǔ)器內(nèi)容的一致性，對(duì)命中和脫靶須分別處理。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.7 高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器5.7.2 Cache的讀寫(xiě)操作的讀寫(xiě)操作1. Cache的讀操作的讀操作 如果如果Cache命中

17、，就直接對(duì)命中，就直接對(duì)Cache進(jìn)行讀進(jìn)行讀操作，與主存無(wú)關(guān)；如果操作，與主存無(wú)關(guān)；如果Cache不命中，則不命中，則仍需訪問(wèn)主存，并把該塊信息一次從主存調(diào)仍需訪問(wèn)主存，并把該塊信息一次從主存調(diào)入入Cache內(nèi)。內(nèi)。2. Cache的寫(xiě)操作的寫(xiě)操作 如果如果Cache命中，需要進(jìn)行一定的寫(xiě)處命中，需要進(jìn)行一定的寫(xiě)處理，處理的方法有：寫(xiě)直達(dá)法和寫(xiě)回法，理，處理的方法有：寫(xiě)直達(dá)法和寫(xiě)回法，計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理Cache更新策略更新策略 為了解決為了解決Cache與主存不一致的問(wèn)題，與主存不一致的問(wèn)題，Cache必須必須更新。選擇合適的更新策略更新。選擇合適的更新策略計(jì)算機(jī)組成原理計(jì)算機(jī)組

18、成原理 目的：維護(hù)Cache、主存數(shù)據(jù)的一致性。 主要方式：3 寫(xiě)一次法： 上述兩種方法的結(jié)合，主要用于多個(gè)Cache數(shù)據(jù)不一致的維護(hù)，具體策略可參考體系結(jié)構(gòu)的相關(guān)內(nèi)容。Cache更新策略更新策略計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理從CPU發(fā)出的寫(xiě)信號(hào)送Cache的同時(shí)也寫(xiě)入主存。CPUCache主主 存存1、通寫(xiě)法、通寫(xiě)法計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理數(shù)據(jù)一般只寫(xiě)到Cache，當(dāng)Cache中的數(shù)據(jù)被再次更新時(shí)，將原更新的數(shù)據(jù)寫(xiě)入主存相應(yīng)單元，并接受新的數(shù)據(jù)。CPUCache主主 存存更新更新寫(xiě)入寫(xiě)入2、回寫(xiě)法、回寫(xiě)法 計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理3 3、寫(xiě)一次法、寫(xiě)一次法寫(xiě)一次法與回寫(xiě)法的寫(xiě)策略基本相

19、同，寫(xiě)一次法只是在第一次寫(xiě)命中時(shí)要同時(shí)寫(xiě)入主存。這是因?yàn)镃PU第一次寫(xiě)Cache命中時(shí)，CPU要在總線上啟動(dòng)一個(gè)存儲(chǔ)器寫(xiě)周期，其他Cache監(jiān)聽(tīng)到此主存塊地址及寫(xiě)信號(hào)后，即把他們各自保存的主存塊該保存到主存中就拷貝，該作廢的就作無(wú)效處理，以便維護(hù)全部Cache與主存的一致性。然后CPU對(duì)Cache的寫(xiě)命中則按照回寫(xiě)法的策略對(duì)待，這可以節(jié)省CPU的總線周期，有利于超標(biāo)量流水線的進(jìn)程，有利于提高系統(tǒng)的運(yùn)行速度計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.7 高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器5.7.3 地址映象地址映象地址映象是指某一數(shù)據(jù)在內(nèi)存中的地址與在緩沖中的地址映象是指某一數(shù)據(jù)在內(nèi)存中的地址與在緩沖中的地址，兩

20、者之間的對(duì)應(yīng)關(guān)系。地址，兩者之間的對(duì)應(yīng)關(guān)系。下面介紹三種地址映象的方式。下面介紹三種地址映象的方式。1. 全相聯(lián)映像全相聯(lián)映像 地址映象規(guī)則：地址映象規(guī)則：主存的任意一塊可以映象到主存的任意一塊可以映象到Cache中的任意一塊中的任意一塊(1) 主存與緩存分成相同大小的數(shù)據(jù)塊。主存與緩存分成相同大小的數(shù)據(jù)塊。(2) 主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間中。中。 計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理 如果如果Cache的塊數(shù)為的塊數(shù)為Cb，主存的塊數(shù)為，主存的塊數(shù)為Mb，則映象關(guān)系，則映象關(guān)系共有共有

21、CbMb種。種。目錄表存放在相關(guān)（聯(lián)）存儲(chǔ)器中，其中包括三部分：數(shù)據(jù)目錄表存放在相關(guān)（聯(lián)）存儲(chǔ)器中，其中包括三部分：數(shù)據(jù)塊在主存的塊地址、存入緩存后的塊地址、及有效位（也稱(chēng)塊在主存的塊地址、存入緩存后的塊地址、及有效位（也稱(chēng)裝入位）。由于是全相聯(lián)方式，因此，目錄表的容量應(yīng)當(dāng)與裝入位）。由于是全相聯(lián)方式，因此，目錄表的容量應(yīng)當(dāng)與緩存的塊數(shù)相同。緩存的塊數(shù)相同。優(yōu)點(diǎn)：靈活，命中率比較高，優(yōu)點(diǎn)：靈活，命中率比較高，Cache的塊沖突概率最低，的塊沖突概率最低，Cache存儲(chǔ)空間利用率高。存儲(chǔ)空間利用率高。缺點(diǎn)：訪問(wèn)相關(guān)存儲(chǔ)器時(shí)，每次都要與全部?jī)?nèi)容比較，速度缺點(diǎn)：訪問(wèn)相關(guān)存儲(chǔ)器時(shí)，每次都要與全部?jī)?nèi)容比

22、較，速度低，成本高，實(shí)現(xiàn)苦難，因而應(yīng)用少。低，成本高，實(shí)現(xiàn)苦難，因而應(yīng)用少。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理例：設(shè)訪問(wèn)存儲(chǔ)器地址的塊號(hào)序列為22、26、22、26、16、4、16、18，采用全相聯(lián)映射方式時(shí)，Cache行分配情況計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.7 高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器2. 直接映像直接映像 地址映象規(guī)則：地址映象規(guī)則： 主存儲(chǔ)器中一塊只能映象到主存儲(chǔ)器中一塊只能映象到Cache的一個(gè)特定的塊中。的一個(gè)特定的塊中。若這個(gè)位置已有內(nèi)容，則產(chǎn)生塊若這個(gè)位置已有內(nèi)容，則產(chǎn)生塊沖突，原來(lái)的塊將無(wú)條件地被替換出去。沖突，原來(lái)的塊將無(wú)條件地被替換出去。(1) 主存與緩存分成相同大小的數(shù)據(jù)

23、塊。主存與緩存分成相同大小的數(shù)據(jù)塊。(2) 主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。塊數(shù)相等。(3) 主存中某區(qū)的一塊存入緩存時(shí)只能存入緩存中塊主存中某區(qū)的一塊存入緩存時(shí)只能存入緩存中塊號(hào)相同的位置。號(hào)相同的位置。 計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理某一主存塊只能能映射到某一主存塊只能能映射到CacheCache的特定行的特定行 i = j mod m i = j mod m 其中：其中： i i：CacheCache的行號(hào)；的行號(hào)； j j：主存的塊號(hào)；

24、：主存的塊號(hào)； m m：CacheCache的總行數(shù)的總行數(shù) 計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理直接映射方式直接映射方式計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理 主存中各區(qū)內(nèi)相同塊號(hào)的數(shù)據(jù)塊都可以分別調(diào)入緩存中主存中各區(qū)內(nèi)相同塊號(hào)的數(shù)據(jù)塊都可以分別調(diào)入緩存中塊號(hào)相同的地址中，但同時(shí)只能有一個(gè)區(qū)的塊存入緩存。由塊號(hào)相同的地址中，但同時(shí)只能有一個(gè)區(qū)的塊存入緩存。由于主、緩存塊號(hào)相同，因此，目錄登記時(shí)，只記錄調(diào)入塊的于主、緩存塊號(hào)相同，因此，目錄登記時(shí)，只記錄調(diào)入塊的區(qū)號(hào)即可。主、緩存塊號(hào)及塊內(nèi)地址兩個(gè)字段完全相同。目區(qū)號(hào)即可。主、緩存塊號(hào)及塊內(nèi)地址兩個(gè)字段完全

25、相同。目錄表存放在高速小容量存儲(chǔ)器中，其中包括二部分：數(shù)據(jù)塊錄表存放在高速小容量存儲(chǔ)器中，其中包括二部分：數(shù)據(jù)塊在主存的區(qū)號(hào)和有效位。目錄表的容量與緩存的塊數(shù)相同。在主存的區(qū)號(hào)和有效位。目錄表的容量與緩存的塊數(shù)相同。優(yōu)點(diǎn)：地址映象方式簡(jiǎn)單，數(shù)據(jù)訪問(wèn)時(shí)，只需檢查區(qū)號(hào)是否優(yōu)點(diǎn)：地址映象方式簡(jiǎn)單，數(shù)據(jù)訪問(wèn)時(shí)，只需檢查區(qū)號(hào)是否相等即可，因而可以得到比較快的訪問(wèn)速度，硬件設(shè)備簡(jiǎn)單。相等即可，因而可以得到比較快的訪問(wèn)速度，硬件設(shè)備簡(jiǎn)單。缺點(diǎn)：替換操作頻繁，命中率比較低。缺點(diǎn)：替換操作頻繁，命中率比較低。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.7 高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器3. 3. 組相聯(lián)映像方式組相聯(lián)映像方式

26、 組相聯(lián)的映象規(guī)則：組相聯(lián)的映象規(guī)則：(1) (1) 主存和主存和CacheCache按同樣大小劃分成塊。按同樣大小劃分成塊。(2) (2) 主存和主存和CacheCache按同樣大小劃分成組。按同樣大小劃分成組。(3) (3) 主存容量是緩存容量的整數(shù)倍，將主存空間按緩沖區(qū)的大小主存容量是緩存容量的整數(shù)倍，將主存空間按緩沖區(qū)的大小分成區(qū)，主存中每一區(qū)的組數(shù)與緩存的組數(shù)相同。分成區(qū)，主存中每一區(qū)的組數(shù)與緩存的組數(shù)相同。(4) (4) 當(dāng)主存的數(shù)據(jù)調(diào)入緩存時(shí)，主存與緩存的組號(hào)應(yīng)相等，也就當(dāng)主存的數(shù)據(jù)調(diào)入緩存時(shí)，主存與緩存的組號(hào)應(yīng)相等，也就是各區(qū)中的某一塊只能存入緩存的同組號(hào)的空間內(nèi)，但組內(nèi)各塊是

27、各區(qū)中的某一塊只能存入緩存的同組號(hào)的空間內(nèi)，但組內(nèi)各塊地址之間則可以任意存放，即從主存的組到地址之間則可以任意存放，即從主存的組到CacheCache的組之間采用的組之間采用直接映象方式；在兩個(gè)對(duì)應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。直接映象方式；在兩個(gè)對(duì)應(yīng)的組內(nèi)部采用全相聯(lián)映象方式。 組相聯(lián)映像將組相聯(lián)映像將CacheCache空間分成大小相同的組，讓主存中的一空間分成大小相同的組，讓主存中的一塊直接映像裝入塊直接映像裝入CacheCache中對(duì)應(yīng)組的任何一塊位置上，即組間采取中對(duì)應(yīng)組的任何一塊位置上，即組間采取直接映像，而組內(nèi)采取全相聯(lián)映像。直接映像，而組內(nèi)采取全相聯(lián)映像。計(jì)算機(jī)組成原理計(jì)算機(jī)組成

28、原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理例例1 1：設(shè)：設(shè)CacheCache有有8 8個(gè)行，分成個(gè)行，分成2 2個(gè)組，設(shè)訪問(wèn)存儲(chǔ)器地址的塊號(hào)序個(gè)組，設(shè)訪問(wèn)存儲(chǔ)器地址的塊號(hào)序列為列為2222、2626、2222、2626、1616、4 4、1616、1818，采用組相聯(lián)映射方式時(shí)，采用組相聯(lián)映射方式時(shí)，CacheCache行分配情況行分配情況 計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理 主存地址與緩存地址的轉(zhuǎn)換有兩部分，組地址是按直主存地址與緩存地址的轉(zhuǎn)換有兩部分，組地址是按直接映象方式，按地址進(jìn)行訪問(wèn)，而塊地址是采用全相聯(lián)接映象方式，按地址進(jìn)行訪問(wèn)，而塊地址是采用全相聯(lián)方式，按內(nèi)容訪問(wèn)

29、。組相聯(lián)的地址轉(zhuǎn)換部件也是采用相方式，按內(nèi)容訪問(wèn)。組相聯(lián)的地址轉(zhuǎn)換部件也是采用相關(guān)存儲(chǔ)器實(shí)現(xiàn)。關(guān)存儲(chǔ)器實(shí)現(xiàn)。優(yōu)點(diǎn)：塊的沖突概率比較低，塊的利用率大幅度提高，優(yōu)點(diǎn)：塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。塊失效率明顯降低。缺點(diǎn)：實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。缺點(diǎn)：實(shí)現(xiàn)難度和造價(jià)要比直接映象方式高。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理比較比較:計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理 CPU在任一時(shí)刻從高速緩沖中直接可靠獲取數(shù)在任一時(shí)刻從高速緩沖中直接可靠獲取數(shù)據(jù)的幾率。據(jù)的幾率。 命中率越高命中率越高,直接獲取數(shù)據(jù)的可靠性就越大。直接獲取數(shù)據(jù)的可靠性就越大。 高速緩沖空間與主存空間在一定范圍

30、內(nèi)保持適當(dāng)高速緩沖空間與主存空間在一定范圍內(nèi)保持適當(dāng)比例的映射關(guān)系比例的映射關(guān)系, 可以使高速緩沖的命中率相當(dāng)高?？梢允垢咚倬彌_的命中率相當(dāng)高。 一般情況一般情況, 高速緩沖與內(nèi)存的空間比為高速緩沖與內(nèi)存的空間比為4:1000 即即128kB 高速緩沖可映射高速緩沖可映射32MB內(nèi)存內(nèi)存 256kB 高速緩沖可映射高速緩沖可映射64MB內(nèi)存內(nèi)存 在這種情況下，命中率都在在這種情況下，命中率都在90以上以上命中率命中率:計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理1 1隨機(jī)算法隨機(jī)算法2 2近期最少使用（近期最少使用（LRULRU）算法）算法3 3先進(jìn)先出（先進(jìn)先出（FIFOFIFO）算法）算法 三種替換策略（

31、算法）三種替換策略（算法）計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理PC機(jī)的機(jī)的Cache技術(shù)的實(shí)現(xiàn)技術(shù)的實(shí)現(xiàn)1.單單/ /多級(jí)多級(jí)CacheCache剛開(kāi)始Cache是單級(jí)的；后來(lái)發(fā)展后大多使用多級(jí)Cache（增加Cache的級(jí)數(shù)，將統(tǒng)一的Cache變成分開(kāi)的Cache）80386以前的Cache都是外部的；L1：容量幾十KB；速度與CPU相當(dāng)；L2：容量256KB2MB；速度與主板相當(dāng)；從PentiumPro，II開(kāi)始，L2和CPU封裝在一起，速度是CPU的1/2,2/5,1/3；目前，大部分L1/L2和CPU封裝在一個(gè)芯片內(nèi)，速度都可達(dá)核心速度。高端的如Itanium,將24MB的L3都集成到片內(nèi)，有

32、利于CPU效率的提高。多級(jí)Cache的訪問(wèn)：計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理2.統(tǒng)一統(tǒng)一Cache/Cache/分開(kāi)分開(kāi)CacheCache 統(tǒng)一統(tǒng)一CacheCache： 分開(kāi)分開(kāi)CacheCache： 8048680486以前的以前的CPUCPU都是一級(jí)都是一級(jí)CacheCache；從；從PentiumPentium開(kāi)始，由于開(kāi)始，由于CPUCPU采用了流水線控制技術(shù)，才將數(shù)據(jù)與指令采用了流水線控制技術(shù)，才將數(shù)據(jù)與指令CacheCache分開(kāi)，以滿足分開(kāi)，以滿足指令預(yù)取與執(zhí)行并行的需要；所以現(xiàn)在大多數(shù)指令預(yù)取與執(zhí)行并行的需要；所以現(xiàn)在大多數(shù)CPUCPU的的L1L1被分為被分為指令與數(shù)據(jù)指令與數(shù)

33、據(jù)CacheCache，成為典型的哈弗結(jié)構(gòu)，成為典型的哈弗結(jié)構(gòu). . 典型一級(jí)（典型一級(jí)（L1）緩存系統(tǒng)的）緩存系統(tǒng)的80的內(nèi)存申請(qǐng)都發(fā)生在的內(nèi)存申請(qǐng)都發(fā)生在CPU內(nèi)部。內(nèi)部。 只有只有20的內(nèi)存申請(qǐng)是與外部?jī)?nèi)存打交道。的內(nèi)存申請(qǐng)是與外部?jī)?nèi)存打交道。 而這而這20的外部?jī)?nèi)存申請(qǐng)中的的外部?jī)?nèi)存申請(qǐng)中的80又與二級(jí)（又與二級(jí)（L2）緩存打）緩存打交道。交道。 因此，只有因此，只有4的內(nèi)存申請(qǐng)定向到主存中。的內(nèi)存申請(qǐng)定向到主存中。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理CPU高速緩沖的重要性高速緩沖的重要性 PC系統(tǒng)的發(fā)展趨勢(shì)之一系統(tǒng)的發(fā)展趨勢(shì)之一: CPU主頻越做越高主頻越做越高, 系統(tǒng)系統(tǒng)架構(gòu)越做越先進(jìn)架構(gòu)

34、越做越先進(jìn), 而主存的結(jié)構(gòu)和存取時(shí)間改進(jìn)較慢。而主存的結(jié)構(gòu)和存取時(shí)間改進(jìn)較慢。因此在因此在PC系統(tǒng)中高速緩存越做越大。高速緩存已是評(píng)系統(tǒng)中高速緩存越做越大。高速緩存已是評(píng)價(jià)和選購(gòu)價(jià)和選購(gòu)PC系統(tǒng)的一個(gè)重要指標(biāo)。系統(tǒng)的一個(gè)重要指標(biāo)。 新一代的微處理器新一代的微處理器, 已實(shí)現(xiàn)設(shè)計(jì)了已實(shí)現(xiàn)設(shè)計(jì)了L1高速緩存高速緩存, L2 高速緩存和在主板上的高速緩存和在主板上的L3高速緩存。高速緩存。 比如比如:在在Intel Pentium III中中, L1高速緩存為高速緩存為 32 KB, L2可從可從512 KB到到1 MB。而。而AMD K6-III的的L1為為64KB，L2可達(dá)可達(dá)256KB, 外部

35、外部L3 高速緩存可達(dá)高速緩存可達(dá)1 MB。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理第第5章章5.1 存儲(chǔ)系統(tǒng)的組成存儲(chǔ)系統(tǒng)的組成5.2 主存儲(chǔ)器的組織主存儲(chǔ)器的組織5.3 半導(dǎo)體隨機(jī)存儲(chǔ)器和只讀存儲(chǔ)器半導(dǎo)體隨機(jī)存儲(chǔ)器和只讀存儲(chǔ)器5.4 主存儲(chǔ)器的連接與控制主存儲(chǔ)器的連接與控制5.5 提高提高主存讀寫(xiě)速度的主存讀寫(xiě)速度的技術(shù)技術(shù)5.6 多體交叉存儲(chǔ)技術(shù)多體交叉存儲(chǔ)技術(shù)5.7 高速緩沖存儲(chǔ)器高速緩沖存儲(chǔ)器5.8 虛擬存儲(chǔ)器虛擬存儲(chǔ)器計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.8 虛擬存儲(chǔ)器虛擬存儲(chǔ)器5.8.1 虛擬存儲(chǔ)器的基本概念虛擬存儲(chǔ)器的基本概念 1. 問(wèn)題的提出問(wèn)題的提出 程序大于總內(nèi)存程序大于總內(nèi)存 多道程序要

36、運(yùn)行內(nèi)存只能容納部分作業(yè)多道程序要運(yùn)行內(nèi)存只能容納部分作業(yè) 要解決上述問(wèn)題必須改變常規(guī)存儲(chǔ)器管理方式中要解決上述問(wèn)題必須改變常規(guī)存儲(chǔ)器管理方式中作業(yè)作業(yè)一次性裝入一次性裝入和運(yùn)行時(shí)的和運(yùn)行時(shí)的駐留性駐留性。 OS把程序當(dāng)前使用的部分代碼和數(shù)據(jù)保留在內(nèi)存把程序當(dāng)前使用的部分代碼和數(shù)據(jù)保留在內(nèi)存中中, 而把其它部分存在磁盤(pán)上而把其它部分存在磁盤(pán)上, 需要時(shí)在內(nèi)存和磁盤(pán)需要時(shí)在內(nèi)存和磁盤(pán)之間動(dòng)態(tài)對(duì)換之間動(dòng)態(tài)對(duì)換, 以解決上述問(wèn)題以解決上述問(wèn)題; 這就是虛擬存儲(chǔ)器這就是虛擬存儲(chǔ)器的基本思想。的基本思想。 計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理2. 程序局部性程序局部性 在一段時(shí)間內(nèi)一個(gè)程序的執(zhí)行往往呈現(xiàn)出高度的

37、在一段時(shí)間內(nèi)一個(gè)程序的執(zhí)行往往呈現(xiàn)出高度的局部性局部性, 順序執(zhí)行的多順序執(zhí)行的多, 過(guò)程調(diào)用過(guò)程調(diào)用, 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu), 對(duì)數(shù)組操對(duì)數(shù)組操作等等。表現(xiàn)為作等等。表現(xiàn)為: 時(shí)間局部性：時(shí)間局部性： 一條指令被執(zhí)行了，則在不久的將來(lái)它可能再被一條指令被執(zhí)行了，則在不久的將來(lái)它可能再被執(zhí)行。執(zhí)行?？臻g局部性：空間局部性： 若某一存儲(chǔ)單元被使用，則在一定時(shí)間內(nèi)若某一存儲(chǔ)單元被使用，則在一定時(shí)間內(nèi), 與該與該存儲(chǔ)單元附近的單元可能被使用。存儲(chǔ)單元附近的單元可能被使用。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理3. 虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)技術(shù) 以以CPU時(shí)間和外存空間換取昂貴內(nèi)存空間時(shí)間和外存空間換取昂貴內(nèi)存空間,

38、這這是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)。是操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)。實(shí)現(xiàn)思想實(shí)現(xiàn)思想: 當(dāng)進(jìn)程運(yùn)行時(shí)當(dāng)進(jìn)程運(yùn)行時(shí), 先將一部分程序裝入內(nèi)先將一部分程序裝入內(nèi)存存, 另一部分暫時(shí)留在外存另一部分暫時(shí)留在外存, 當(dāng)要執(zhí)行的指令不在當(dāng)要執(zhí)行的指令不在內(nèi)存時(shí)內(nèi)存時(shí), 由系統(tǒng)自動(dòng)將它們從外存調(diào)換到內(nèi)存。即由系統(tǒng)自動(dòng)將它們從外存調(diào)換到內(nèi)存。即具有請(qǐng)求調(diào)入和置換功能具有請(qǐng)求調(diào)入和置換功能。虛擬存儲(chǔ)器定義虛擬存儲(chǔ)器定義: 具有請(qǐng)求調(diào)入和置換功能具有請(qǐng)求調(diào)入和置換功能,對(duì)內(nèi)對(duì)內(nèi)存容量擴(kuò)充存容量擴(kuò)充, 得到一個(gè)邏輯容量等于內(nèi)存與外存容得到一個(gè)邏輯容量等于內(nèi)存與外存容量之和的量之和的“虛內(nèi)存虛內(nèi)存”。計(jì)算機(jī)組成原理計(jì)算機(jī)組

39、成原理 頁(yè)頁(yè) 號(hào)號(hào) P P 頁(yè)頁(yè) 內(nèi)內(nèi) 位位 移移 量量 W W31 11 04. 虛擬地址結(jié)構(gòu)虛擬地址結(jié)構(gòu)頁(yè)的大小頁(yè)的大小= =？頁(yè)的多少頁(yè)的多少= =？虛存的大小虛存的大小= =？計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理CPUMMU內(nèi)存內(nèi)存磁盤(pán)磁盤(pán)控制器控制器總線總線CPU把虛地址送給把虛地址送給MMU MMU把物理地址送給存儲(chǔ)器把物理地址送給存儲(chǔ)器計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.8 虛擬存儲(chǔ)器虛擬存儲(chǔ)器 虛擬存儲(chǔ)器由主存儲(chǔ)器和聯(lián)機(jī)工作的輔虛擬存儲(chǔ)器由主存儲(chǔ)器和聯(lián)機(jī)工作的輔助存儲(chǔ)器（通常為磁盤(pán)存儲(chǔ)器）共同組成，助存儲(chǔ)器（通常為磁盤(pán)存儲(chǔ)器）共同組成，這兩個(gè)存儲(chǔ)器在硬件和系統(tǒng)軟件的共同管理這兩個(gè)存儲(chǔ)器在硬

40、件和系統(tǒng)軟件的共同管理下工作，對(duì)于應(yīng)用程序員，可以把它們看作下工作，對(duì)于應(yīng)用程序員，可以把它們看作是一個(gè)單一的存儲(chǔ)器。是一個(gè)單一的存儲(chǔ)器。 虛擬存儲(chǔ)器將主存或輔存的地址空間統(tǒng)虛擬存儲(chǔ)器將主存或輔存的地址空間統(tǒng)一編址，形成一個(gè)龐大的存儲(chǔ)空間。在這個(gè)一編址，形成一個(gè)龐大的存儲(chǔ)空間。在這個(gè)大空間里，用戶可以自由編程，完全不必考大空間里，用戶可以自由編程，完全不必考慮程序在主存是否裝得下以及這些程序?qū)?lái)慮程序在主存是否裝得下以及這些程序?qū)?lái)在主存中的實(shí)際存放位置。在主存中的實(shí)際存放位置。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.8 虛擬存儲(chǔ)器虛擬存儲(chǔ)器 在實(shí)際的物理存儲(chǔ)層次上，所編程序和數(shù)據(jù)在操在實(shí)際的物理存儲(chǔ)

41、層次上，所編程序和數(shù)據(jù)在操作系統(tǒng)管理下，先送入磁盤(pán)，然后操作系統(tǒng)將當(dāng)前運(yùn)作系統(tǒng)管理下，先送入磁盤(pán)，然后操作系統(tǒng)將當(dāng)前運(yùn)行所需要的部分調(diào)入主存，供行所需要的部分調(diào)入主存，供CPU使用。使用。 程序運(yùn)行時(shí)，程序運(yùn)行時(shí)，CPU以虛地址來(lái)訪問(wèn)主存，由輔助以虛地址來(lái)訪問(wèn)主存，由輔助硬件找出虛地址和實(shí)地址之間的對(duì)應(yīng)關(guān)系，并判斷這硬件找出虛地址和實(shí)地址之間的對(duì)應(yīng)關(guān)系，并判斷這個(gè)虛地址指示的存儲(chǔ)單元內(nèi)容是否已裝入主存。如果個(gè)虛地址指示的存儲(chǔ)單元內(nèi)容是否已裝入主存。如果已在主存中，則通過(guò)地址變換，已在主存中，則通過(guò)地址變換，CPU可直接訪問(wèn)主存可直接訪問(wèn)主存的實(shí)際單元；如果不在主存中，則把包含這個(gè)字的一的實(shí)際單

42、元；如果不在主存中，則把包含這個(gè)字的一頁(yè)或一個(gè)程序段調(diào)入主存后再由頁(yè)或一個(gè)程序段調(diào)入主存后再由CPU訪問(wèn)。如果主存訪問(wèn)。如果主存已滿，則由替換算法從主存中將暫不運(yùn)行的一頁(yè)或一已滿，則由替換算法從主存中將暫不運(yùn)行的一頁(yè)或一段調(diào)回輔存，再?gòu)妮o存調(diào)入新的一頁(yè)或一段到主存。段調(diào)回輔存，再?gòu)妮o存調(diào)入新的一頁(yè)或一段到主存。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.8 虛擬存儲(chǔ)器虛擬存儲(chǔ)器5.8.2 頁(yè)式虛擬存儲(chǔ)器頁(yè)式虛擬存儲(chǔ)器 以頁(yè)為基本單位的虛擬存儲(chǔ)器叫頁(yè)式以頁(yè)為基本單位的虛擬存儲(chǔ)器叫頁(yè)式虛擬存儲(chǔ)器。各類(lèi)計(jì)算機(jī)頁(yè)面大小不等，虛擬存儲(chǔ)器。各類(lèi)計(jì)算機(jī)頁(yè)面大小不等，一般為一般為512B到幾到幾KB。主存空間和虛存空間。

43、主存空間和虛存空間都劃分成若干個(gè)大小相等的頁(yè)。主存即實(shí)都劃分成若干個(gè)大小相等的頁(yè)。主存即實(shí)存的頁(yè)稱(chēng)為實(shí)頁(yè)，虛存的頁(yè)稱(chēng)為虛頁(yè)。存的頁(yè)稱(chēng)為實(shí)頁(yè)，虛存的頁(yè)稱(chēng)為虛頁(yè)。 頁(yè)式虛擬存儲(chǔ)器的每頁(yè)長(zhǎng)度是固定的，頁(yè)式虛擬存儲(chǔ)器的每頁(yè)長(zhǎng)度是固定的，頁(yè)表的建立很方便，新頁(yè)的調(diào)入也容易實(shí)頁(yè)表的建立很方便，新頁(yè)的調(diào)入也容易實(shí)現(xiàn)。但是由于程序不可能正好是頁(yè)面的整現(xiàn)。但是由于程序不可能正好是頁(yè)面的整倍數(shù)，最后一頁(yè)的零頭將無(wú)法利用而造成倍數(shù)，最后一頁(yè)的零頭將無(wú)法利用而造成浪費(fèi)。同時(shí)，頁(yè)不是邏輯上獨(dú)立的實(shí)體，浪費(fèi)。同時(shí)，頁(yè)不是邏輯上獨(dú)立的實(shí)體，使程序的處理、保護(hù)和共享都比較麻煩。使程序的處理、保護(hù)和共享都比較麻煩。計(jì)算機(jī)組成原

44、理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.8 虛擬存儲(chǔ)器虛擬存儲(chǔ)器5.8.3 段段式虛擬存儲(chǔ)器式虛擬存儲(chǔ)器 段式虛擬存儲(chǔ)器中的段是按照程序的段式虛擬存儲(chǔ)器中的段是按照程序的邏輯結(jié)構(gòu)劃分的，各個(gè)段的長(zhǎng)度因程序而邏輯結(jié)構(gòu)劃分的，各個(gè)段的長(zhǎng)度因程序而異。異。 由于段的分界與程序的自然分界相對(duì)由于段的分界與程序的自然分界相對(duì)應(yīng)，所以具有邏輯獨(dú)立性，易于程序的編應(yīng)，所以具有邏輯獨(dú)立性，易于程序的編譯、管理、修改和保護(hù)，也便于多道程序譯、管理、修改和保護(hù)，也便于多道程序共享。但是，因?yàn)槎蔚拈L(zhǎng)度參差不齊，起共享。但是，因?yàn)槎蔚拈L(zhǎng)度參差不齊，起點(diǎn)和終點(diǎn)不定，給主存空間分配帶來(lái)了麻點(diǎn)和終點(diǎn)不定，給主存空間

45、分配帶來(lái)了麻煩；容易在段間留下不能利用的零頭，造煩；容易在段間留下不能利用的零頭，造成浪費(fèi)。成浪費(fèi)。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理5.8 虛擬存儲(chǔ)器虛擬存儲(chǔ)器5.8.4 段頁(yè)段頁(yè)式虛擬存儲(chǔ)器式虛擬存儲(chǔ)器 將程序按其邏輯結(jié)構(gòu)分段，每段再劃將程序按其邏輯結(jié)構(gòu)分段，每段再劃分為若干大小相等的頁(yè)；主存空間也劃分分為若干大小相等的頁(yè)；主存空間也劃分為若干同樣大小的頁(yè)。虛存和實(shí)存之間以為若干同樣大小的頁(yè)。虛存和實(shí)存之間以頁(yè)為基本傳送單位，每個(gè)程序?qū)?yīng)一個(gè)段頁(yè)為基本傳送單位，每個(gè)程序?qū)?yīng)一個(gè)段表，每段對(duì)應(yīng)一個(gè)頁(yè)表。表，每段對(duì)應(yīng)一個(gè)頁(yè)表。CPU訪問(wèn)時(shí)，虛訪問(wèn)時(shí)，虛地址包含段號(hào)、段內(nèi)頁(yè)

46、號(hào)、頁(yè)內(nèi)地址地址包含段號(hào)、段內(nèi)頁(yè)號(hào)、頁(yè)內(nèi)地址3部分。部分。首先將段表起始地址與段號(hào)合成，得到段首先將段表起始地址與段號(hào)合成，得到段表地址；然后從段表中取出該段的頁(yè)表起表地址；然后從段表中取出該段的頁(yè)表起始地址，與段內(nèi)頁(yè)號(hào)合成，得到頁(yè)表地址；始地址，與段內(nèi)頁(yè)號(hào)合成，得到頁(yè)表地址；最后從頁(yè)表中取出實(shí)頁(yè)號(hào)，與頁(yè)內(nèi)地址拼最后從頁(yè)表中取出實(shí)頁(yè)號(hào)，與頁(yè)內(nèi)地址拼接形成主存實(shí)地址。段頁(yè)式存儲(chǔ)器綜合了接形成主存實(shí)地址。段頁(yè)式存儲(chǔ)器綜合了前兩種結(jié)構(gòu)的優(yōu)點(diǎn)，但要經(jīng)過(guò)兩級(jí)查表才前兩種結(jié)構(gòu)的優(yōu)點(diǎn)，但要經(jīng)過(guò)兩級(jí)查表才能完成地址轉(zhuǎn)換，費(fèi)時(shí)要多些。能完成地址轉(zhuǎn)換，費(fèi)時(shí)要多些。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理虛擬存儲(chǔ)器的特征虛擬存

47、儲(chǔ)器的特征離散性離散性: 是實(shí)現(xiàn)虛擬存儲(chǔ)器的基礎(chǔ)是實(shí)現(xiàn)虛擬存儲(chǔ)器的基礎(chǔ)多次性多次性: 多次將部分調(diào)入內(nèi)存多次將部分調(diào)入內(nèi)存, 每當(dāng)運(yùn)行到不在每當(dāng)運(yùn)行到不在內(nèi)存那部分程序時(shí)內(nèi)存那部分程序時(shí),再將它調(diào)入再將它調(diào)入交換性交換性: 暫時(shí)不執(zhí)行允許換出暫時(shí)不執(zhí)行允許換出, 需要時(shí)再換入需要時(shí)再換入虛擬性虛擬性: 邏輯邏輯(虛虛)上擴(kuò)充了內(nèi)存物理上擴(kuò)充了內(nèi)存物理(實(shí)實(shí))容量容量 虛擬性以多次性和交換性為基礎(chǔ)虛擬性以多次性和交換性為基礎(chǔ),多次性和多次性和交換性又必須建立在離散分配的基礎(chǔ)之上。交換性又必須建立在離散分配的基礎(chǔ)之上。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理虛擬存儲(chǔ)器的實(shí)現(xiàn)方式虛擬存儲(chǔ)器的實(shí)現(xiàn)方式請(qǐng)求分頁(yè)方式

48、請(qǐng)求分頁(yè)方式分段請(qǐng)求方式分段請(qǐng)求方式硬件支持：硬件支持：請(qǐng)求分頁(yè)請(qǐng)求分頁(yè)(段段)的頁(yè)的頁(yè)(段段)表機(jī)構(gòu)表機(jī)構(gòu)缺頁(yè)缺頁(yè)(段段)中斷機(jī)構(gòu)中斷機(jī)構(gòu)請(qǐng)求分頁(yè)請(qǐng)求分頁(yè)(段段)的地址變換機(jī)構(gòu)的地址變換機(jī)構(gòu)計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理請(qǐng)求分頁(yè)式存儲(chǔ)管理請(qǐng)求分頁(yè)式存儲(chǔ)管理 在進(jìn)程開(kāi)始運(yùn)行之前在進(jìn)程開(kāi)始運(yùn)行之前, 不是裝入全部頁(yè)面不是裝入全部頁(yè)面,而是裝入而是裝入一個(gè)或零個(gè)頁(yè)面一個(gè)或零個(gè)頁(yè)面, 之后根據(jù)進(jìn)程運(yùn)行的需要之后根據(jù)進(jìn)程運(yùn)行的需要, 動(dòng)態(tài)裝入動(dòng)態(tài)裝入其它頁(yè)面其它頁(yè)面; 當(dāng)內(nèi)存空間已滿當(dāng)內(nèi)存空間已滿,而又需要裝入新的頁(yè)面時(shí)而又需要裝入新的頁(yè)面時(shí), 則根據(jù)某種算法淘汰某個(gè)頁(yè)面則根據(jù)某種算法淘汰某個(gè)頁(yè)面, 以

49、便裝入新頁(yè)面。以便裝入新頁(yè)面。 硬件支持及工作過(guò)程硬件支持及工作過(guò)程1.頁(yè)表機(jī)制頁(yè)表機(jī)制狀態(tài)位狀態(tài)位P：表示該頁(yè)是在內(nèi)存還是在外存：表示該頁(yè)是在內(nèi)存還是在外存訪問(wèn)位：記錄該頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)訪問(wèn)位：記錄該頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù)修改位：查看此頁(yè)是否在內(nèi)存中被修改過(guò)修改位：查看此頁(yè)是否在內(nèi)存中被修改過(guò)計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理 在地址映射過(guò)程中在地址映射過(guò)程中, 在頁(yè)表中發(fā)現(xiàn)所要訪問(wèn)在頁(yè)表中發(fā)現(xiàn)所要訪問(wèn)的頁(yè)不在內(nèi)存的頁(yè)不在內(nèi)存, 則產(chǎn)生缺頁(yè)中斷。操作系統(tǒng)接到則產(chǎn)生缺頁(yè)中斷。操作系統(tǒng)接到此中斷信號(hào)后此中斷信號(hào)后, 就調(diào)出缺頁(yè)中斷處理程序就調(diào)出缺頁(yè)中斷處理程序

50、,根據(jù)頁(yè)根據(jù)頁(yè)表中給出的外存地址表中給出的外存地址, 將該頁(yè)調(diào)入內(nèi)存將該頁(yè)調(diào)入內(nèi)存,使進(jìn)程繼使進(jìn)程繼續(xù)運(yùn)行下去。續(xù)運(yùn)行下去。 如果內(nèi)存中有空閑塊如果內(nèi)存中有空閑塊, 則分配一頁(yè)將新調(diào)入則分配一頁(yè)將新調(diào)入頁(yè)裝入內(nèi)存頁(yè)裝入內(nèi)存, 并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)目的駐留并修改頁(yè)表中相應(yīng)頁(yè)表項(xiàng)目的駐留位及相應(yīng)的內(nèi)存塊號(hào)。若此時(shí)內(nèi)存中沒(méi)有空閑塊位及相應(yīng)的內(nèi)存塊號(hào)。若此時(shí)內(nèi)存中沒(méi)有空閑塊, 則要淘汰某頁(yè)則要淘汰某頁(yè), 若該頁(yè)在內(nèi)存期間被修改過(guò)若該頁(yè)在內(nèi)存期間被修改過(guò), 則要?jiǎng)t要將其寫(xiě)回外存。將其寫(xiě)回外存。2.缺頁(yè)中斷機(jī)構(gòu)缺頁(yè)中斷機(jī)構(gòu)計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理影響缺頁(yè)次數(shù)的因素影響缺頁(yè)

51、次數(shù)的因素(1) 分配給進(jìn)程的物理頁(yè)面數(shù)分配給進(jìn)程的物理頁(yè)面數(shù)(2) 頁(yè)面本身的大小頁(yè)面本身的大小(3) 程序的編制方法程序的編制方法(4) 頁(yè)面淘汰算法頁(yè)面淘汰算法計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理 頁(yè)面分配與置換頁(yè)面分配與置換請(qǐng)求調(diào)頁(yè)中操作系統(tǒng)提供的支持請(qǐng)求調(diào)頁(yè)中操作系統(tǒng)提供的支持 請(qǐng)求調(diào)頁(yè)時(shí)請(qǐng)求調(diào)頁(yè)時(shí), 把所需的頁(yè)從外存調(diào)入內(nèi)存把所需的頁(yè)從外存調(diào)入內(nèi)存 置換時(shí)置換時(shí), 將內(nèi)存的某些頁(yè)調(diào)至外存將內(nèi)存的某些頁(yè)調(diào)至外存問(wèn)題：?jiǎn)栴}：進(jìn)程正常運(yùn)行所需的最少物理塊是多少？進(jìn)程正常運(yùn)行所需的最少物理塊是多少？每個(gè)進(jìn)程分配的物理塊數(shù)是固定的嗎？每個(gè)進(jìn)程分配的物理塊數(shù)是固定的嗎？每個(gè)進(jìn)程分配的物理塊數(shù)依據(jù)是什么

52、？每個(gè)進(jìn)程分配的物理塊數(shù)依據(jù)是什么？計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理1. 最小物理塊數(shù)的確定最小物理塊數(shù)的確定 最小物理塊數(shù)與硬件結(jié)構(gòu)、指令格式、尋址方式最小物理塊數(shù)與硬件結(jié)構(gòu)、指令格式、尋址方式有關(guān)。有關(guān)。 直接尋址方式最少塊數(shù)為直接尋址方式最少塊數(shù)為2 間接尋址方式最少塊數(shù)為間接尋址方式最少塊數(shù)為3 功能較強(qiáng)的機(jī)器最少塊數(shù)為功能較強(qiáng)的機(jī)器最少塊數(shù)為62. 頁(yè)面分配和置換策略頁(yè)面分配和置換策略(固定分配、可變分配固定分配、可變分配) 1) 固定分配局部置換固定分配局部置換 系統(tǒng)中駐留的進(jìn)程數(shù)與分配給進(jìn)程的頁(yè)數(shù)是什系統(tǒng)中駐留的進(jìn)程數(shù)與分配給進(jìn)程的頁(yè)數(shù)是什么關(guān)系？（正比？反比？）么關(guān)系？（正比？反比

53、？） 塊數(shù)太多會(huì)出現(xiàn)什么問(wèn)題？塊數(shù)太多會(huì)出現(xiàn)什么問(wèn)題？ 塊數(shù)太少會(huì)出現(xiàn)什么問(wèn)題？塊數(shù)太少會(huì)出現(xiàn)什么問(wèn)題？計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理2) 可變分配全局置換可變分配全局置換 空閑物理塊由誰(shuí)管理？空閑物理塊由誰(shuí)管理？(OS?進(jìn)程？）進(jìn)程？） 缺頁(yè)中斷時(shí)從何處獲得空閑頁(yè)？缺頁(yè)中斷時(shí)從何處獲得空閑頁(yè)？ 調(diào)入調(diào)出什么時(shí)候發(fā)生（空閑頁(yè)用完還是給進(jìn)程分調(diào)入調(diào)出什么時(shí)候發(fā)生（空閑頁(yè)用完還是給進(jìn)程分配的頁(yè)用完？）配的頁(yè)用完？）3) 可變分配局部置換可變分配局部置換 為每個(gè)進(jìn)程所分配的物理塊數(shù)相對(duì)固定為每個(gè)進(jìn)程所分配的物理塊數(shù)相對(duì)固定 從每個(gè)進(jìn)程所分配的頁(yè)面中進(jìn)行換入換出。從每個(gè)進(jìn)程所分配的頁(yè)面中進(jìn)行換入換出。

54、從全局的角度動(dòng)態(tài)調(diào)整每個(gè)進(jìn)程所分配的頁(yè)面從全局的角度動(dòng)態(tài)調(diào)整每個(gè)進(jìn)程所分配的頁(yè)面計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理3. 分配算法分配算法(固定分配策略）固定分配策略） 平均分配算法平均分配算法 駐留內(nèi)存的進(jìn)程平均分配駐留內(nèi)存的進(jìn)程平均分配, 貌似公平貌似公平, 實(shí)際實(shí)際不公平不公平, 長(zhǎng)進(jìn)程缺頁(yè)率高長(zhǎng)進(jìn)程缺頁(yè)率高 按比例分配算法按比例分配算法 按駐留內(nèi)存的進(jìn)程的大小比例分配按駐留內(nèi)存的進(jìn)程的大小比例分配, 較公平較公平 考慮優(yōu)先權(quán)的分配算法考慮優(yōu)先權(quán)的分配算法 整個(gè)內(nèi)存分為兩部分整個(gè)內(nèi)存分為兩部分, 一部分按比例分配一部分按比例分配, 另一部分按優(yōu)先權(quán)分配另一部分按優(yōu)先權(quán)分配, 照顧到重要緊迫的照顧

55、到重要緊迫的進(jìn)程盡快完成進(jìn)程盡快完成計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理 頁(yè)面調(diào)入策略頁(yè)面調(diào)入策略什么時(shí)候調(diào)入？從何處調(diào)入？怎么調(diào)入？什么時(shí)候調(diào)入？從何處調(diào)入？怎么調(diào)入？1.什么時(shí)候調(diào)入什么時(shí)候調(diào)入 預(yù)調(diào)入策略預(yù)調(diào)入策略: 一次調(diào)入若干相鄰頁(yè)一次調(diào)入若干相鄰頁(yè)(預(yù)計(jì)即將運(yùn)行預(yù)計(jì)即將運(yùn)行的頁(yè)的頁(yè))比單頁(yè)調(diào)入效率高比單頁(yè)調(diào)入效率高, 命中率約命中率約5050% %。 請(qǐng)求調(diào)頁(yè)策略請(qǐng)求調(diào)頁(yè)策略: 缺頁(yè)時(shí)提出請(qǐng)求缺頁(yè)時(shí)提出請(qǐng)求, OS將所需一頁(yè)調(diào)將所需一頁(yè)調(diào)入內(nèi)存入內(nèi)存, 易于實(shí)現(xiàn)易于實(shí)現(xiàn), I/O啟動(dòng)頻率高系統(tǒng)開(kāi)銷(xiāo)大。啟動(dòng)頻率高系統(tǒng)開(kāi)銷(xiāo)大。2. 從何處調(diào)入頁(yè)面從何處調(diào)入頁(yè)面-外存分為文件區(qū)和對(duì)換區(qū)外存分為文

56、件區(qū)和對(duì)換區(qū)(I/O快快)系統(tǒng)有足夠的對(duì)換區(qū)時(shí)系統(tǒng)有足夠的對(duì)換區(qū)時(shí), 運(yùn)行前全部從文件區(qū)調(diào)入運(yùn)行前全部從文件區(qū)調(diào)入對(duì)換區(qū)對(duì)換區(qū), 運(yùn)行中全部從對(duì)換區(qū)調(diào)入所需頁(yè)。運(yùn)行中全部從對(duì)換區(qū)調(diào)入所需頁(yè)。系統(tǒng)缺少足夠的對(duì)換區(qū)時(shí)系統(tǒng)缺少足夠的對(duì)換區(qū)時(shí), 不會(huì)被修改的頁(yè)從文件不會(huì)被修改的頁(yè)從文件區(qū)調(diào)入?yún)^(qū)調(diào)入, 會(huì)被修改的頁(yè)從對(duì)換區(qū)調(diào)入換出。會(huì)被修改的頁(yè)從對(duì)換區(qū)調(diào)入換出。UNIX:未運(yùn)行過(guò)的頁(yè)從文件區(qū)調(diào)入未運(yùn)行過(guò)的頁(yè)從文件區(qū)調(diào)入, 換出到對(duì)換區(qū)換出到對(duì)換區(qū)計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理3. 頁(yè)面調(diào)入過(guò)程頁(yè)面調(diào)入過(guò)程 當(dāng)程序所要訪問(wèn)的頁(yè)不在內(nèi)存時(shí)當(dāng)程序所要訪問(wèn)的頁(yè)不在內(nèi)存時(shí), 向向CPU發(fā)出缺頁(yè)中斷發(fā)出缺頁(yè)中斷, 中

57、斷處理程序首先保留中斷處理程序首先保留CPU環(huán)環(huán)境境, 再通過(guò)查找頁(yè)表得到該頁(yè)在外存的物理塊再通過(guò)查找頁(yè)表得到該頁(yè)在外存的物理塊號(hào)。號(hào)。 此時(shí)如果內(nèi)存未滿此時(shí)如果內(nèi)存未滿,則將該頁(yè)調(diào)入內(nèi)存并則將該頁(yè)調(diào)入內(nèi)存并修改頁(yè)表修改頁(yè)表,若內(nèi)存已滿若內(nèi)存已滿,則從內(nèi)存中選出一頁(yè)準(zhǔn)則從內(nèi)存中選出一頁(yè)準(zhǔn)備換出備換出, 如果該頁(yè)已被修改則還需將它寫(xiě)回外如果該頁(yè)已被修改則還需將它寫(xiě)回外存存, 然后再把所缺頁(yè)調(diào)入內(nèi)存并修改相應(yīng)的頁(yè)然后再把所缺頁(yè)調(diào)入內(nèi)存并修改相應(yīng)的頁(yè)表項(xiàng)表項(xiàng), 置器存儲(chǔ)位為置器存儲(chǔ)位為1并將此頁(yè)表項(xiàng)寫(xiě)入快表。并將此頁(yè)表項(xiàng)寫(xiě)入快表。整個(gè)調(diào)入過(guò)程對(duì)用戶是透明的。整個(gè)調(diào)入過(guò)程對(duì)用戶是透明的。計(jì)算機(jī)組成原理

58、計(jì)算機(jī)組成原理好的頁(yè)面置換算法應(yīng)具有低的頁(yè)面更換頻率好的頁(yè)面置換算法應(yīng)具有低的頁(yè)面更換頻率 最佳置換算法最佳置換算法 先進(jìn)先出算法先進(jìn)先出算法 最近最久未使用最近最久未使用LRU 算法算法 CLOCK算法算法頁(yè)面緩沖算法頁(yè)面緩沖算法頁(yè)面置換算法頁(yè)面置換算法計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理1. 最佳置換算法最佳置換算法淘汰永不使用或最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)淘汰永不使用或最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè) 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 7 0 0 0 0 4 0 0 0 1 1 3 3 3 1 1 無(wú)法實(shí)現(xiàn)無(wú)法實(shí)現(xiàn), 只能用它做評(píng)

59、價(jià)標(biāo)準(zhǔn)。只能用它做評(píng)價(jià)標(biāo)準(zhǔn)。2. 先進(jìn)先出置換算法先進(jìn)先出置換算法 簡(jiǎn)單易行簡(jiǎn)單易行 沒(méi)有考慮訪問(wèn)頻度的差別沒(méi)有考慮訪問(wèn)頻度的差別, 不能保證經(jīng)常訪問(wèn)不能保證經(jīng)常訪問(wèn)的頁(yè)不被淘汰。的頁(yè)不被淘汰。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理3. 最近最久未使用最近最久未使用LRU 算法算法淘汰在最近最久未使用的頁(yè)面。淘汰在最近最久未使用的頁(yè)面。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 4 4 4 0 1 1 1 0 0 0 0 0 0 3 3 3 0 0 1 1 3 3 2 2 2 2 2 7如何確定哪一頁(yè)是最近最久未使用的頁(yè)？如何確定哪一頁(yè)是最近最久

60、未使用的頁(yè)？1）移位寄存器）移位寄存器 為每個(gè)在內(nèi)存的頁(yè)面配置一個(gè)移位寄存器為每個(gè)在內(nèi)存的頁(yè)面配置一個(gè)移位寄存器,當(dāng)訪問(wèn)當(dāng)訪問(wèn)某頁(yè)時(shí)將相應(yīng)的寄存器最高位置某頁(yè)時(shí)將相應(yīng)的寄存器最高位置1, 每隔一定時(shí)間將寄每隔一定時(shí)間將寄存器右移存器右移1位位,將寄存器存的數(shù)看作一個(gè)整數(shù)將寄存器存的數(shù)看作一個(gè)整數(shù),顯然最小顯然最小值的寄存器對(duì)應(yīng)的頁(yè)就是最近最久未使用的頁(yè)。值的寄存器對(duì)應(yīng)的頁(yè)就是最近最久未使用的頁(yè)。計(jì)算機(jī)組成原理計(jì)算機(jī)組成原理2）特殊棧）特殊棧 用特殊棧保存當(dāng)前在內(nèi)存的各頁(yè)面號(hào)用特殊棧保存當(dāng)前在內(nèi)存的各頁(yè)面號(hào), 棧的大小棧的大小等于分配的物理塊數(shù)等于分配的物理塊數(shù), 當(dāng)前訪問(wèn)頁(yè)號(hào)始終保持在棧頂當(dāng)前