3.2虛擬存儲(chǔ)器虛擬存儲(chǔ)器又稱虛擬存儲(chǔ)系統(tǒng)，或虛擬存儲(chǔ)體系等。虛擬存儲(chǔ)器是由主存儲(chǔ)器和聯(lián)機(jī)工作的外部存儲(chǔ)器共同組成。聯(lián)機(jī)工作的外部存儲(chǔ)器通常為磁盤存儲(chǔ)器，它的存儲(chǔ)容量很大，與主存儲(chǔ)器相比，速度很低，單位容量的價(jià)格很便宜。1.地址的映像與變換在虛擬存儲(chǔ)器中有三種地址空間：虛擬地址空間、主存地址空間、輔存地址空間。-3.2虛擬存儲(chǔ)器虛擬存儲(chǔ)器又稱虛擬存儲(chǔ)系統(tǒng)，或虛1地址映像是把虛擬地址空間映像到主存地址空間，具體地說(shuō)，就是把用戶用虛擬地址編寫的程序按照某種規(guī)則裝入到主存儲(chǔ)器中，并建立多用戶虛地址與主存實(shí)地址之間的對(duì)應(yīng)關(guān)系。而地址變換則是在程序被裝入主存儲(chǔ)器之后，在實(shí)際運(yùn)行時(shí)，把多用戶虛地址變換成主存實(shí)地址（內(nèi)部地址變換）或磁盤存儲(chǔ)器地址（外部地址變換）。根據(jù)所采用的地址映像和地址變換方法不同，虛擬存儲(chǔ)器一般分為頁(yè)式虛擬存儲(chǔ)器、段式虛擬存儲(chǔ)器和段頁(yè)式虛擬存儲(chǔ)器三種。-地址映像是把虛擬地址空間映像到主存地址空間，具體地22.段式虛擬存儲(chǔ)器

段式虛擬存儲(chǔ)器的基本思想是：按照程序的邏輯結(jié)構(gòu)劃分段，主存以段為單位進(jìn)行分配。由于段是按照程序的自然邊界劃分的，因此每個(gè)段的長(zhǎng)度各不相同，并且程序員通常還會(huì)把不同類型的數(shù)據(jù)劃分到不同的段中。段式虛擬存儲(chǔ)器的地址映像-2.段式虛擬存儲(chǔ)器-3段式虛擬存儲(chǔ)器的地址變換--4優(yōu)點(diǎn)：（1）程序的模塊化性能好。（2）便于程序和數(shù)據(jù)的共享。（3）程序的動(dòng)態(tài)鏈接和調(diào)度比較容易。（4）便于實(shí)現(xiàn)信息保護(hù)。缺點(diǎn)：（1）地址變換所花費(fèi)的時(shí)間比較長(zhǎng)。（2）主存儲(chǔ)器的利用率往往比較低。（3）對(duì)輔存（磁盤存儲(chǔ)器）的管理比較困難。-優(yōu)點(diǎn)：-53.頁(yè)式虛擬存儲(chǔ)器頁(yè)式存儲(chǔ)器把虛擬地址空間劃分成一個(gè)個(gè)固定大小的塊，每塊稱為一頁(yè)，把主存儲(chǔ)器的地址空間同樣的大小劃分成為頁(yè)。頁(yè)是一種邏輯上的劃分，它可以由系統(tǒng)管理軟件任意指定。一般的大小通常為1KB至16KB。在虛擬存儲(chǔ)器中，虛擬地址空間中的頁(yè)稱為虛頁(yè)，主存地址空間的頁(yè)稱為實(shí)頁(yè)。-3.頁(yè)式虛擬存儲(chǔ)器-6頁(yè)式虛擬存儲(chǔ)器的地址映像0頁(yè)1頁(yè)2頁(yè)3頁(yè)…頁(yè)號(hào)主存頁(yè)號(hào)0123用戶程序頁(yè)表主存儲(chǔ)器-頁(yè)式虛擬存儲(chǔ)器的地址映像0頁(yè)1頁(yè)2頁(yè)3頁(yè)…頁(yè)號(hào)主存頁(yè)號(hào)0127頁(yè)式虛擬器的地址變換-頁(yè)式虛擬器的地址變換-8優(yōu)點(diǎn)：（1）主存儲(chǔ)器的利用率比較高。（2）頁(yè)表相對(duì)比較簡(jiǎn)單。（3）地址映像和變換的速度比較快。（4）對(duì)輔存（磁盤存儲(chǔ)器）的管理比較容易。缺點(diǎn)：（1）程序的模塊化性能不好。（2）頁(yè)表很長(zhǎng)，需要占用很大的存儲(chǔ)空間。-優(yōu)點(diǎn)：-94.段頁(yè)式虛擬存儲(chǔ)器基本思想：對(duì)用戶用來(lái)編寫程序的虛擬存儲(chǔ)空間采用分段的方法管理，而對(duì)主存儲(chǔ)器的物理空間采用分頁(yè)的方法管理。段頁(yè)式虛擬存儲(chǔ)器一方面具有段式虛擬存儲(chǔ)器的主要優(yōu)點(diǎn)，另一方面也具有頁(yè)式虛擬存儲(chǔ)器的主要優(yōu)點(diǎn)。-4.段頁(yè)式虛擬存儲(chǔ)器-10段頁(yè)式虛擬存儲(chǔ)器的地址映象0段（12K）1段（10K）2段（5K）頁(yè)表長(zhǎng)度頁(yè)表地址3320段0頁(yè)0段1頁(yè)0段2頁(yè)2段0頁(yè)2段1頁(yè)1段0頁(yè)1段1頁(yè)1段2頁(yè)段表用戶程序頁(yè)表主存儲(chǔ)器每頁(yè)4KB-段頁(yè)式虛擬存儲(chǔ)器的地址映象0段（12K）1段（10K）2段（11優(yōu)點(diǎn)：縮短頁(yè)表的存儲(chǔ)容量，加快地址映象和變換的速度，因?yàn)橹鞔鎸?shí)地址只需要把頁(yè)表中的實(shí)頁(yè)號(hào)虛擬地址中的業(yè)內(nèi)偏移拼接起來(lái)即可，不必進(jìn)行任何計(jì)算。段頁(yè)式虛擬存儲(chǔ)器中，要從主存儲(chǔ)器中訪問(wèn)一個(gè)數(shù)據(jù)，需要查兩次表，一次是頁(yè)表，另一次是段表。如果段表和頁(yè)表都在主存儲(chǔ)器中的，則要訪問(wèn)主存儲(chǔ)器三次。-優(yōu)點(diǎn)：縮短頁(yè)表的存儲(chǔ)容量，加快地址映象和變換的速度，因?yàn)橹鞔?25.頁(yè)面替換算法及其實(shí)現(xiàn)

在虛擬存儲(chǔ)器中，當(dāng)發(fā)生頁(yè)面失效時(shí)，需要從磁盤存儲(chǔ)器中調(diào)入一頁(yè)（或一段）到主存儲(chǔ)器中。由于主存空間的局限性，必然會(huì)出現(xiàn)當(dāng)主存中所有頁(yè)面都已經(jīng)被占用，或者所有主存空間都已經(jīng)被占用，而又要從磁盤存儲(chǔ)器中調(diào)入新頁(yè)（或新段）的情況。這時(shí)，必然從主存儲(chǔ)器中淘汰掉一個(gè)不常用的頁(yè)面（或程序段），以便騰出主存空間來(lái)存放新調(diào)入的頁(yè)面（或程序段）。那么，按照什么樣的規(guī)則替換主存儲(chǔ)器中的頁(yè)面（或程序段）呢？這就是頁(yè)面替換算法要解決的問(wèn)題。

常用的頁(yè)面替換算法有如下幾種：-5.頁(yè)面替換算法及其實(shí)現(xiàn)-13（1）隨機(jī)算法（RAND算法）利用軟件或硬件的隨機(jī)數(shù)發(fā)生器來(lái)確定主存儲(chǔ)器中被替換的頁(yè)面。這種算法最簡(jiǎn)單，而且容易實(shí)現(xiàn)。但是這種算法完全沒(méi)有利用主存儲(chǔ)器中頁(yè)面調(diào)度情況的歷史信息，也沒(méi)有反應(yīng)程序的局部性，所以命中率比較低。（2）先進(jìn)先出算法（FIFO算法）這種算法選擇最先調(diào)入主存儲(chǔ)器的頁(yè)面作為被替換的頁(yè)面。它的優(yōu)點(diǎn)是比較容易實(shí)現(xiàn)，能夠利用主存儲(chǔ)器中頁(yè)面調(diào)度情況的歷史信息，但是，沒(méi)有反應(yīng)程序的局部性。因?yàn)樽钕日{(diào)入主存的頁(yè)面，很可能也是經(jīng)常要使用的頁(yè)面。-（1）隨機(jī)算法（RAND算法）-14FIFO算法的圖表說(shuō)明：（3）近期最少使用算法（LRU算法）這種算法選擇近期最少訪問(wèn)的頁(yè)面作為被替換的頁(yè)面。這是一種很合理的算法，因?yàn)榈侥壳盀橹棺钌偈褂玫捻?yè)面，很可能也是將來(lái)最少訪問(wèn)的頁(yè)面。該算法既充分利用了主存中頁(yè)面調(diào)度算法情況的歷史信息，又正確反映了程序的局部性。訪問(wèn)頁(yè)面70120304230321201701塊1777222444000777塊200033322211100塊31110003332221是否缺頁(yè)√√√√√√√√√√√√-FIFO算法的圖表說(shuō)明：訪問(wèn)頁(yè)面7012030423032115但是，這種算法實(shí)現(xiàn)起來(lái)非常的困難。它要為每個(gè)頁(yè)面設(shè)置一個(gè)很長(zhǎng)的計(jì)數(shù)器，并且要選擇一個(gè)固定的時(shí)鐘為每個(gè)計(jì)數(shù)器定時(shí)計(jì)數(shù)。在選擇被替換頁(yè)面時(shí)，要從所有計(jì)數(shù)器中找出一個(gè)計(jì)數(shù)值最大的計(jì)數(shù)器。（4）最久沒(méi)有使用算法（LFU算法）這種算法把近期最久沒(méi)有被訪問(wèn)過(guò)的頁(yè)面作為被替換的頁(yè)面。它把LRU算法中要記錄數(shù)量上的“多”與“少”簡(jiǎn)化成判斷“有”與“無(wú)”，因此，訪問(wèn)頁(yè)面70120304230321201701塊1777224440111塊200000033300塊31133222227是否缺頁(yè)√√√√√√√√√-但是，這種算法實(shí)現(xiàn)起來(lái)非常的困難。它要為每個(gè)頁(yè)面設(shè)置一個(gè)很長(zhǎng)16實(shí)現(xiàn)起來(lái)比較容易。（5）最優(yōu)替換算法（OPT算法）上面介紹的幾種頁(yè)面替換算法主要是以主存儲(chǔ)器中頁(yè)面調(diào)度情況的歷史信息為依據(jù)的，它假設(shè)將來(lái)主存儲(chǔ)器中頁(yè)面調(diào)度情況與過(guò)去一段時(shí)間內(nèi)的情況是相同的，這種替換算法的命中率是最高的。要實(shí)現(xiàn)OPT算法，唯一的辦法是讓程序先執(zhí)行一遍，記錄下實(shí)際的頁(yè)地址流情況。根據(jù)這個(gè)頁(yè)地址流才能找出當(dāng)前要被替換的頁(yè)面。OPT算法是一種理想化的算法，經(jīng)常把這種算法用來(lái)作為評(píng)價(jià)其他頁(yè)面替換算法好壞的標(biāo)準(zhǔn)。-實(shí)現(xiàn)起來(lái)比較容易。-17訪問(wèn)頁(yè)面70120304230321201701塊1777222227塊200004000塊31133311是否缺頁(yè)√√√√√√-訪問(wèn)頁(yè)面70120304230321201701塊1777218謝謝聆聽(tīng)！--193.2虛擬存儲(chǔ)器虛擬存儲(chǔ)器又稱虛擬存儲(chǔ)系統(tǒng)，或虛擬存儲(chǔ)體系等。虛擬存儲(chǔ)器是由主存儲(chǔ)器和聯(lián)機(jī)工作的外部存儲(chǔ)器共同組成。聯(lián)機(jī)工作的外部存儲(chǔ)器通常為磁盤存儲(chǔ)器，它的存儲(chǔ)容量很大，與主存儲(chǔ)器相比，速度很低，單位容量的價(jià)格很便宜。1.地址的映像與變換在虛擬存儲(chǔ)器中有三種地址空間：虛擬地址空間、主存地址空間、輔存地址空間。-3.2虛擬存儲(chǔ)器虛擬存儲(chǔ)器又稱虛擬存儲(chǔ)系統(tǒng)，或虛20地址映像是把虛擬地址空間映像到主存地址空間，具體地說(shuō)，就是把用戶用虛擬地址編寫的程序按照某種規(guī)則裝入到主存儲(chǔ)器中，并建立多用戶虛地址與主存實(shí)地址之間的對(duì)應(yīng)關(guān)系。而地址變換則是在程序被裝入主存儲(chǔ)器之后，在實(shí)際運(yùn)行時(shí)，把多用戶虛地址變換成主存實(shí)地址（內(nèi)部地址變換）或磁盤存儲(chǔ)器地址（外部地址變換）。根據(jù)所采用的地址映像和地址變換方法不同，虛擬存儲(chǔ)器一般分為頁(yè)式虛擬存儲(chǔ)器、段式虛擬存儲(chǔ)器和段頁(yè)式虛擬存儲(chǔ)器三種。-地址映像是把虛擬地址空間映像到主存地址空間，具體地212.段式虛擬存儲(chǔ)器

段式虛擬存儲(chǔ)器的基本思想是：按照程序的邏輯結(jié)構(gòu)劃分段，主存以段為單位進(jìn)行分配。由于段是按照程序的自然邊界劃分的，因此每個(gè)段的長(zhǎng)度各不相同，并且程序員通常還會(huì)把不同類型的數(shù)據(jù)劃分到不同的段中。段式虛擬存儲(chǔ)器的地址映像-2.段式虛擬存儲(chǔ)器-22段式虛擬存儲(chǔ)器的地址變換--23優(yōu)點(diǎn)：（1）程序的模塊化性能好。（2）便于程序和數(shù)據(jù)的共享。（3）程序的動(dòng)態(tài)鏈接和調(diào)度比較容易。（4）便于實(shí)現(xiàn)信息保護(hù)。缺點(diǎn)：（1）地址變換所花費(fèi)的時(shí)間比較長(zhǎng)。（2）主存儲(chǔ)器的利用率往往比較低。（3）對(duì)輔存（磁盤存儲(chǔ)器）的管理比較困難。-優(yōu)點(diǎn)：-243.頁(yè)式虛擬存儲(chǔ)器頁(yè)式存儲(chǔ)器把虛擬地址空間劃分成一個(gè)個(gè)固定大小的塊，每塊稱為一頁(yè)，把主存儲(chǔ)器的地址空間同樣的大小劃分成為頁(yè)。頁(yè)是一種邏輯上的劃分，它可以由系統(tǒng)管理軟件任意指定。一般的大小通常為1KB至16KB。在虛擬存儲(chǔ)器中，虛擬地址空間中的頁(yè)稱為虛頁(yè)，主存地址空間的頁(yè)稱為實(shí)頁(yè)。-3.頁(yè)式虛擬存儲(chǔ)器-25頁(yè)式虛擬存儲(chǔ)器的地址映像0頁(yè)1頁(yè)2頁(yè)3頁(yè)…頁(yè)號(hào)主存頁(yè)號(hào)0123用戶程序頁(yè)表主存儲(chǔ)器-頁(yè)式虛擬存儲(chǔ)器的地址映像0頁(yè)1頁(yè)2頁(yè)3頁(yè)…頁(yè)號(hào)主存頁(yè)號(hào)01226頁(yè)式虛擬器的地址變換-頁(yè)式虛擬器的地址變換-27優(yōu)點(diǎn)：（1）主存儲(chǔ)器的利用率比較高。（2）頁(yè)表相對(duì)比較簡(jiǎn)單。（3）地址映像和變換的速度比較快。（4）對(duì)輔存（磁盤存儲(chǔ)器）的管理比較容易。缺點(diǎn)：（1）程序的模塊化性能不好。（2）頁(yè)表很長(zhǎng)，需要占用很大的存儲(chǔ)空間。-優(yōu)點(diǎn)：-284.段頁(yè)式虛擬存儲(chǔ)器基本思想：對(duì)用戶用來(lái)編寫程序的虛擬存儲(chǔ)空間采用分段的方法管理，而對(duì)主存儲(chǔ)器的物理空間采用分頁(yè)的方法管理。段頁(yè)式虛擬存儲(chǔ)器一方面具有段式虛擬存儲(chǔ)器的主要優(yōu)點(diǎn)，另一方面也具有頁(yè)式虛擬存儲(chǔ)器的主要優(yōu)點(diǎn)。-4.段頁(yè)式虛擬存儲(chǔ)器-29段頁(yè)式虛擬存儲(chǔ)器的地址映象0段（12K）1段（10K）2段（5K）頁(yè)表長(zhǎng)度頁(yè)表地址3320段0頁(yè)0段1頁(yè)0段2頁(yè)2段0頁(yè)2段1頁(yè)1段0頁(yè)1段1頁(yè)1段2頁(yè)段表用戶程序頁(yè)表主存儲(chǔ)器每頁(yè)4KB-段頁(yè)式虛擬存儲(chǔ)器的地址映象0段（12K）1段（10K）2段（30優(yōu)點(diǎn)：縮短頁(yè)表的存儲(chǔ)容量，加快地址映象和變換的速度，因?yàn)橹鞔鎸?shí)地址只需要把頁(yè)表中的實(shí)頁(yè)號(hào)虛擬地址中的業(yè)內(nèi)偏移拼接起來(lái)即可，不必進(jìn)行任何計(jì)算。段頁(yè)式虛擬存儲(chǔ)器中，要從主存儲(chǔ)器中訪問(wèn)一個(gè)數(shù)據(jù)，需要查兩次表，一次是頁(yè)表，另一次是段表。如果段表和頁(yè)表都在主存儲(chǔ)器中的，則要訪問(wèn)主存儲(chǔ)器三次。-優(yōu)點(diǎn)：縮短頁(yè)表的存儲(chǔ)容量，加快地址映象和變換的速度，因?yàn)橹鞔?15.頁(yè)面替換算法及其實(shí)現(xiàn)

在虛擬存儲(chǔ)器中，當(dāng)發(fā)生頁(yè)面失效時(shí)，需要從磁盤存儲(chǔ)器中調(diào)入一頁(yè)（或一段）到主存儲(chǔ)器中。由于主存空間的局限性，必然會(huì)出現(xiàn)當(dāng)主存中所有頁(yè)面都已經(jīng)被占用，或者所有主存空間都已經(jīng)被占用，而又要從磁盤存儲(chǔ)器中調(diào)入新頁(yè)（或新段）的情況。這時(shí)，必然從主存儲(chǔ)器中淘汰掉一個(gè)不常用的頁(yè)面（或程序段），以便騰出主存空間來(lái)存放新調(diào)入的頁(yè)面（或程序段）。那么，按照什么樣的規(guī)則替換主存儲(chǔ)器中的頁(yè)面（或程序段）呢？這就是頁(yè)面替換算法要解決的問(wèn)題。

常用的頁(yè)面替換算法有如下幾種：-5.頁(yè)面替換算法及其實(shí)現(xiàn)-32（1）隨機(jī)算法（RAND算法）利用軟件或硬件的隨機(jī)數(shù)發(fā)生器來(lái)確定主存儲(chǔ)器中被替換的頁(yè)面。這種算法最簡(jiǎn)單，而且容易實(shí)現(xiàn)。但是這種算法完全沒(méi)有利用主存儲(chǔ)器中頁(yè)面調(diào)度情況的歷史信息，也沒(méi)有反應(yīng)程序的局部性，所以命中率比較低。（2）先進(jìn)先出算法（FIFO算法）這種算法選擇最先調(diào)入主存儲(chǔ)器的頁(yè)面作為被替換的頁(yè)面。它的優(yōu)點(diǎn)是比較容易實(shí)現(xiàn)，能夠利用主存儲(chǔ)器中頁(yè)面調(diào)度情況的歷史信息，但是，沒(méi)有反應(yīng)程序的局部性。因?yàn)樽钕日{(diào)入主存的頁(yè)面，很可能也是經(jīng)常要使用的頁(yè)面。-（1）隨機(jī)算法（RAND算法）-33FIFO算法的圖表說(shuō)明：（3）近期最少使用算法（LRU算法）這種算法選擇近期最少訪問(wèn)的頁(yè)面作為被替換的頁(yè)面。這是一種很合理的算法，因?yàn)榈侥壳盀橹棺钌偈褂玫捻?yè)面，很可能也是將來(lái)最少訪問(wèn)的頁(yè)面。該算法既充分利用了主存中頁(yè)面調(diào)度算法情況的歷史信息，又正確反映了程序的局部性。訪問(wèn)頁(yè)面70120304230321201701塊1777222444000777塊200033322211100塊31110003332221是否缺頁(yè)√√√√√√√√√√√√-FIFO算法的圖表說(shuō)明：訪問(wèn)頁(yè)面7012030423032134但是，這種算法實(shí)現(xiàn)起來(lái)非常的困難。它要為每個(gè)頁(yè)面設(shè)置一個(gè)很長(zhǎng)的計(jì)數(shù)器，并且要選擇一個(gè)固定的時(shí)鐘為每個(gè)計(jì)數(shù)器定時(shí)計(jì)數(shù)。在選擇被替換頁(yè)面時(shí)，要從所有計(jì)數(shù)器中找出一個(gè)計(jì)數(shù)值最大的計(jì)數(shù)器。（4）最久沒(méi)有使用算法（LFU算法）