操作系統(tǒng)請(qǐng)求分頁(yè)

會(huì)計(jì)學(xué)1操作系統(tǒng)請(qǐng)求分頁(yè)虛擬存儲(chǔ)器虛擬存儲(chǔ)器（VirtualMemory），簡(jiǎn)稱(chēng)虛存，是指對(duì)內(nèi)存的虛擬，一種實(shí)際并不存在的內(nèi)存空間，包括一級(jí)存儲(chǔ)器概念和作業(yè)地址空間概念。虛擬并不是無(wú)限的，取決于機(jī)器的CPU地址結(jié)構(gòu)，虛存容量不能大于外存容量。第1頁(yè)/共38頁(yè)請(qǐng)求分頁(yè)管理請(qǐng)求分頁(yè)管理是動(dòng)態(tài)分頁(yè)管理，是在靜態(tài)分頁(yè)管理基礎(chǔ)上發(fā)展而來(lái)的。在簡(jiǎn)單分頁(yè)管理中，如果作業(yè)所要求的頁(yè)面數(shù)比內(nèi)存空閑的塊數(shù)多，則該作業(yè)不能裝入運(yùn)行。在虛擬存儲(chǔ)器技術(shù)的支持下，可以進(jìn)行請(qǐng)求分頁(yè)管理。那么請(qǐng)求分頁(yè)管理的基本思想是什么？作業(yè)要訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)，該如何處理？如何知道哪些頁(yè)面在內(nèi)存，哪些不在？如何決定把作業(yè)的哪些頁(yè)面留在內(nèi)存中呢？將虛頁(yè)調(diào)入內(nèi)存時(shí)，沒(méi)有空閑塊又怎么處理？在虛擬存儲(chǔ)系統(tǒng)中，將對(duì)邏輯空間和物理空間的考慮截然分開(kāi)，邏輯空間的容量由系統(tǒng)提供的有效地址長(zhǎng)度決定。

第2頁(yè)/共38頁(yè)請(qǐng)求分頁(yè)管理就能實(shí)現(xiàn)這種虛存空間，基本方法是在分頁(yè)管理的基礎(chǔ)上，在作業(yè)開(kāi)始執(zhí)行前，只裝入作業(yè)的一部分頁(yè)面到內(nèi)存，其它的頁(yè)面在作業(yè)執(zhí)行過(guò)程中根據(jù)需要，動(dòng)態(tài)地從輔存裝入內(nèi)存。當(dāng)內(nèi)存塊已經(jīng)占滿(mǎn)時(shí)，再根據(jù)某種策略交換出部分頁(yè)面到輔存。根據(jù)作業(yè)的執(zhí)行情況裝入作業(yè)的部分實(shí)體，顯然節(jié)省了內(nèi)存空間。請(qǐng)求分頁(yè)管理和分頁(yè)管理的數(shù)據(jù)結(jié)構(gòu)、地址映射和存儲(chǔ)保護(hù)、存儲(chǔ)分配與回收等都類(lèi)似，但請(qǐng)求分頁(yè)管理的實(shí)現(xiàn)過(guò)程復(fù)雜很多，需要由硬件和軟件的相互配合才能完成。1.請(qǐng)求調(diào)入及缺頁(yè)中斷處理2.淘汰算法3.抖動(dòng)與工作集第3頁(yè)/共38頁(yè)請(qǐng)求分頁(yè)存儲(chǔ)管理鋪墊作業(yè)在運(yùn)行期間的各個(gè)階段，多數(shù)作業(yè)只使用全部地址空間的一部分。例如用戶(hù)編制的出錯(cuò)處理子程序，在作業(yè)正常運(yùn)行情況下不會(huì)執(zhí)行這些程序，沒(méi)有必要把它們調(diào)入內(nèi)存。即程序中往往會(huì)有一些彼此互斥的部分不是每次運(yùn)行時(shí)都能執(zhí)行到。

程序的局部性。順序執(zhí)行的指令和線性結(jié)構(gòu)的數(shù)據(jù)(如數(shù)組)。它們通常被限定在某一連續(xù)區(qū)域。一旦某一位置被訪問(wèn)后，那么它附近的位置很快也會(huì)被訪問(wèn)。第4頁(yè)/共38頁(yè)

基于上述情況，就沒(méi)有必要把一個(gè)作業(yè)一次性全部裝入內(nèi)存再開(kāi)始運(yùn)行。而是可以把程序當(dāng)前執(zhí)行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需要臨時(shí)調(diào)入，由操作系統(tǒng)和硬件相配合來(lái)完成主存和輔存之間信息的動(dòng)態(tài)調(diào)度。這樣的計(jì)算機(jī)系統(tǒng)好像為用戶(hù)提供了一個(gè)存儲(chǔ)容量比實(shí)際主存大得多的存儲(chǔ)器，就稱(chēng)為虛擬存儲(chǔ)器。第5頁(yè)/共38頁(yè)虛擬存儲(chǔ)器的概念P61虛擬存儲(chǔ)技術(shù)的基本思想是利用大容量的外存來(lái)擴(kuò)充內(nèi)存，產(chǎn)生一個(gè)比有限的實(shí)際內(nèi)存空間大得多的、邏輯的虛擬內(nèi)存空間，以有效地支持多道程序設(shè)計(jì)的實(shí)現(xiàn)和大型程序運(yùn)行的需要，增強(qiáng)系統(tǒng)的處理能力。請(qǐng)求分頁(yè)系統(tǒng)支持虛擬存儲(chǔ)技術(shù)第6頁(yè)/共38頁(yè)

請(qǐng)求分頁(yè)存儲(chǔ)管理名詞作業(yè)的邏輯地址空間劃分的頁(yè)，稱(chēng)為虛頁(yè)主存稱(chēng)為實(shí)存實(shí)存中的塊稱(chēng)為實(shí)頁(yè)第7頁(yè)/共38頁(yè)

請(qǐng)求分頁(yè)存儲(chǔ)管理基本原理請(qǐng)求分頁(yè)系統(tǒng)對(duì)地址空間和內(nèi)存空間的管理采用與分頁(yè)存儲(chǔ)管理系統(tǒng)相同的方式，但是它只將作業(yè)的部分頁(yè)面裝入內(nèi)存，便可開(kāi)始運(yùn)行作業(yè)，作業(yè)的其他部分被存放在輔助存儲(chǔ)器上。第8頁(yè)/共38頁(yè)請(qǐng)求分頁(yè)存儲(chǔ)管理必須解決的問(wèn)題一個(gè)作業(yè)不全部裝入，該作業(yè)能否開(kāi)始運(yùn)行，并運(yùn)行一段時(shí)間？當(dāng)程序要訪問(wèn)的某頁(yè)不在內(nèi)存時(shí)，如何發(fā)現(xiàn)這種缺頁(yè)情況？發(fā)現(xiàn)后應(yīng)如何處理？缺頁(yè)時(shí)，所需的頁(yè)面從何處裝入？裝入到何處？若此時(shí)實(shí)存中沒(méi)有空閑塊應(yīng)怎么辦？第9頁(yè)/共38頁(yè)一個(gè)作業(yè)不全部裝入，該作業(yè)能否開(kāi)始運(yùn)行，并運(yùn)行一段時(shí)間？作業(yè)在運(yùn)行期間的各個(gè)階段，多數(shù)作業(yè)只使用全部地址空間的一部分。例如用戶(hù)編制的出錯(cuò)處理子程序，在作業(yè)正常運(yùn)行情況下不會(huì)執(zhí)行這些程序，沒(méi)有必要把它們調(diào)入內(nèi)存。即程序中往往會(huì)有一些彼此互斥的部分不是每次運(yùn)行時(shí)都能執(zhí)行到。

程序的局部性。順序執(zhí)行的指令和線性結(jié)構(gòu)的數(shù)據(jù)(如數(shù)組)。它們通常被限定在某一連續(xù)區(qū)域。一旦某一位置被訪問(wèn)后，那么它附近的位置很快也會(huì)被訪問(wèn)。因此，沒(méi)有必要把一個(gè)作業(yè)一次性全部裝入內(nèi)存再開(kāi)始運(yùn)行。而是可以把程序當(dāng)前執(zhí)行所涉及的信息放入內(nèi)存中，其余部分可根據(jù)需要臨時(shí)調(diào)入，由操作系統(tǒng)和硬件相配合來(lái)完成主存和輔存之間信息的動(dòng)態(tài)調(diào)度。第10頁(yè)/共38頁(yè)當(dāng)程序要訪問(wèn)的某頁(yè)不在內(nèi)存時(shí)，如何發(fā)現(xiàn)

這種缺頁(yè)情況？發(fā)現(xiàn)后應(yīng)如何處理？地址變換機(jī)構(gòu)檢測(cè)到虛頁(yè)的狀態(tài)為1，由硬件產(chǎn)生缺頁(yè)中斷，轉(zhuǎn)去中斷處理第11頁(yè)/共38頁(yè)

所需的頁(yè)面從何處裝入？

在請(qǐng)求分頁(yè)管理系統(tǒng)中，當(dāng)一個(gè)作業(yè)完成編譯鏈接后，所形成的裝配模塊通常以文件形式存入作為輔存的磁盤(pán)上，當(dāng)該頁(yè)需要裝入實(shí)存時(shí)，就從磁盤(pán)上調(diào)進(jìn)來(lái)。為此，需建立一個(gè)作業(yè)的輔助頁(yè)表，也稱(chēng)為外頁(yè)表。虛頁(yè)號(hào)輔存地址第12頁(yè)/共38頁(yè)新調(diào)入的頁(yè)面裝入何處？實(shí)存中有空閑實(shí)頁(yè)，直接將其裝入。空閑已滿(mǎn)，則必須淘汰（頁(yè)面置換算法）實(shí)存中的某一頁(yè)。

被淘汰的頁(yè)，以后可能還要用，是否需要寫(xiě)回輔存，這取決于該頁(yè)進(jìn)入實(shí)存后是否被修改，如未被修改，因輔存上已有副本則不必寫(xiě)回輔存。否則，要重新寫(xiě)回輔存。因此頁(yè)表中還可以增加一個(gè)“修改位”，以反映該頁(yè)是否已被修改過(guò)。為了便于系統(tǒng)管理頁(yè)面置換，增加“引用位”，表示該頁(yè)最近是否被訪問(wèn)過(guò)。第13頁(yè)/共38頁(yè)虛頁(yè)號(hào)主存塊號(hào)改變位引用位狀態(tài)位輔存地址0/11該頁(yè)已被修改過(guò)0該頁(yè)未被修改0/11最近已被訪問(wèn)過(guò)主存塊號(hào)0/10在內(nèi)存1不在內(nèi)存輔助頁(yè)表虛頁(yè)號(hào)輔存地址保護(hù)信息擴(kuò)充后的PMT表第14頁(yè)/共38頁(yè)圖缺頁(yè)中斷的發(fā)生及其處理抖動(dòng)/系統(tǒng)顛簸第15頁(yè)/共38頁(yè)抖動(dòng)/系統(tǒng)顛簸出頁(yè)：將某一頁(yè)從實(shí)存移到輔存入頁(yè)：將某一頁(yè)從輔存調(diào)入實(shí)存這種反復(fù)進(jìn)行入頁(yè)和出頁(yè)的現(xiàn)象稱(chēng)為“抖動(dòng)/系統(tǒng)顛簸”第16頁(yè)/共38頁(yè)

先進(jìn)先出算法(FIFO)淘汰駐留主存時(shí)間最長(zhǎng)的頁(yè)面最近最久未用置換算法(LRU)淘汰在最近一段時(shí)間最久未用的頁(yè)面最近最不常用算法最近未使用算法頁(yè)面置換算法/淘汰算法第17頁(yè)/共38頁(yè)1.先進(jìn)先出算法（FIFO算法）

這種算法的基本思想是：總是先淘汰那些駐留在內(nèi)存時(shí)間最長(zhǎng)的頁(yè)面，即先進(jìn)入內(nèi)存的頁(yè)面先被置換掉。理由是：最先進(jìn)入內(nèi)存的頁(yè)面不再被訪問(wèn)的可能性最大。

第18頁(yè)/共38頁(yè)2．最近最久未使用頁(yè)面置換算法（LeastRecentlyUsed/LRU算法）這種算法的基本思想是，如果某一頁(yè)被訪問(wèn)了，那么它很可能馬上又被訪問(wèn)；反之，如果某一頁(yè)很長(zhǎng)時(shí)間沒(méi)有被訪問(wèn)，那么最近也不太可能會(huì)被訪問(wèn)。這種算法考慮了程序設(shè)計(jì)的局部性原理。其實(shí)質(zhì)是，當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間最久未使用的頁(yè)面予以淘汰。實(shí)現(xiàn)這種算法可通過(guò)周期性地對(duì)“引用位”進(jìn)行檢查，并利用它來(lái)記錄一頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t，淘汰時(shí)選擇t最大的頁(yè)面。

不太實(shí)用第19頁(yè)/共38頁(yè)

性能分析為了盡可能地減少缺頁(yè)中斷的次數(shù)，應(yīng)從程序設(shè)計(jì)的質(zhì)量頁(yè)面的大小主存的容量頁(yè)面置換算法等幾方面來(lái)考慮。第20頁(yè)/共38頁(yè)程序設(shè)計(jì)的質(zhì)量(主要指程序的局部化程度)程序的局部化程度包括時(shí)間局部化和空間局部化時(shí)間局部化是指一旦某個(gè)位置----數(shù)據(jù)或指令----被訪問(wèn)了，它常常很快又要再次被訪問(wèn)。這可通過(guò)循環(huán)、經(jīng)常用到的變量和子程序等程序結(jié)構(gòu)來(lái)實(shí)現(xiàn)?？臻g局部化是指一旦某個(gè)位置被訪問(wèn)到，那么它附近的位置很快也要用到。這可以盡量采用順序的指令列、線形的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)。局部化程度隨程序而異，一般來(lái)說(shuō)，總希望編制的程序具有較高的局部化程度。這樣，程序執(zhí)行時(shí)可經(jīng)常集中在幾個(gè)頁(yè)面上進(jìn)行訪問(wèn)，以減少缺頁(yè)中斷的次數(shù)。第21頁(yè)/共38頁(yè)頁(yè)面的大小頁(yè)面大小應(yīng)根據(jù)實(shí)際情況來(lái)確定，它和計(jì)算機(jī)的性能以及用戶(hù)的要求都有關(guān)系。頁(yè)面大，頁(yè)表小，占用空間小，缺頁(yè)中斷次數(shù)少，但換頁(yè)時(shí)間長(zhǎng)，頁(yè)內(nèi)碎片也大，浪費(fèi)空間頁(yè)面小時(shí)，正好相反第22頁(yè)/共38頁(yè)主存的容量一個(gè)作業(yè)的執(zhí)行所產(chǎn)生缺頁(yè)的次數(shù)是存放頁(yè)面的實(shí)際存儲(chǔ)容量的函數(shù)。當(dāng)存儲(chǔ)容量達(dá)到某一程度時(shí)，缺頁(yè)中斷的次數(shù)的減少就不明顯了。試驗(yàn)分析表明：對(duì)所有程序來(lái)說(shuō)，要使之有效地工作，它在主存中的頁(yè)面數(shù)不低于它的總頁(yè)面數(shù)的一半。第23頁(yè)/共38頁(yè)圖存儲(chǔ)容量與缺頁(yè)中斷次數(shù)的關(guān)系第24頁(yè)/共38頁(yè)4．頁(yè)面置換算法性能三個(gè)參數(shù)：頁(yè)面走向：每個(gè)作業(yè)的虛頁(yè)調(diào)入實(shí)存的順序，稱(chēng)為頁(yè)面軌跡，或頁(yè)面走向，用P表示。主存容量：是指分配給作業(yè)的主存塊數(shù)，M表示。置換算法：包括FIFO，LRU等第25頁(yè)/共38頁(yè)例1

設(shè)頁(yè)面走向?yàn)镻=4,3,2,1,4,3,5,4,3,2,1,5，主存容量M=3，置換算法采用FIFO，求訪問(wèn)過(guò)程中發(fā)生缺頁(yè)中斷的次數(shù)和缺頁(yè)率？假設(shè)開(kāi)始時(shí)，主存未裝入任何塊。表1FIFO性能分析例(M=3)缺頁(yè)中斷次數(shù)F=9缺頁(yè)率f=9/12=75%P行表示頁(yè)面走向，M行表示在主存中的頁(yè)面號(hào)，其中帶有+的表示新調(diào)入頁(yè)面，在M行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時(shí)刻將被淘汰頁(yè)面，F(xiàn)行表示是否引起缺頁(yè)中斷，帶+號(hào)的表示引起缺頁(yè)中斷。第26頁(yè)/共38頁(yè)

例2

設(shè)M=4，其余同例1。則缺頁(yè)中斷次數(shù)和缺頁(yè)率？表2FIFO性能分析例(M=4)缺頁(yè)中斷次數(shù)F=10缺頁(yè)率f=10/12=83%第27頁(yè)/共38頁(yè)由表1，表2得出：對(duì)于FIFO算法，內(nèi)存增加，缺頁(yè)率反而增加！異?，F(xiàn)象（Belady異常）第28頁(yè)/共38頁(yè)

例3

設(shè)頁(yè)面走向如上，M=3，置換算法為L(zhǎng)RU，則缺頁(yè)中斷次數(shù)和缺頁(yè)率？由于采用LRU算法，M中各列按訪問(wèn)的時(shí)間順序排列，最近被訪問(wèn)的頁(yè)面在最前。表3LRU性能分析例(M=3)缺頁(yè)中斷次數(shù)F=10，缺頁(yè)率f=10/12=83%。第29頁(yè)/共38頁(yè)例4

設(shè)M=4，其余同例3，則缺頁(yè)中斷次數(shù)和缺頁(yè)率？表4LRU性能分析例(M=4)第30頁(yè)/共38頁(yè)34第31頁(yè)/共38頁(yè)

由表3，表4可得如下事實(shí)：設(shè)G(P,M,t)表示當(dāng)頁(yè)面走向?yàn)镻，主存容量為M，在時(shí)刻t的頁(yè)面集合，對(duì)于LRU算法，存在如下關(guān)系，即成立。即對(duì)于任何時(shí)刻t(t=1,2,…,12),G(P,M,t)所選中的頁(yè)號(hào)必定包含在G(P,M+1,t)之中。這種關(guān)系說(shuō)明了增加主存容量不會(huì)增加缺頁(yè)中斷次數(shù)，然而對(duì)FIFO算法，此關(guān)系并不成立。第32頁(yè)/共38頁(yè)

請(qǐng)求分頁(yè)存儲(chǔ)管理方案的評(píng)價(jià)它提供了大容量的多個(gè)虛擬存儲(chǔ)器，作業(yè)地址空間不再受實(shí)存容量的限制；更有效地利用了主存，一個(gè)作業(yè)的地址空間不必全部同時(shí)都裝入主存，只裝入其必要部分，其它部分根據(jù)請(qǐng)求裝入，或者根本就不裝入(如錯(cuò)誤處理程序等)；更加有利于多道程序的運(yùn)行，從而提高了系統(tǒng)效率；方便了用戶(hù)，特別是大作業(yè)用戶(hù)。

第33頁(yè)/共38頁(yè)

缺點(diǎn)為處理缺頁(yè)中斷，增加了處理機(jī)時(shí)間的開(kāi)銷(xiāo)，即請(qǐng)求分頁(yè)系統(tǒng)是用時(shí)間的代價(jià)換取了空間的擴(kuò)大；可能因作業(yè)地址空間過(guò)大或多道程序道數(shù)過(guò)多以及其它原因而造成系統(tǒng)抖動(dòng)；為防止系統(tǒng)抖動(dòng)所采取的各種措施會(huì)增加系統(tǒng)的復(fù)雜性。第34頁(yè)/共38頁(yè)復(fù)習(xí)LRU頁(yè)面調(diào)度算法是選擇（）的頁(yè)面先調(diào)出。A．最近才使用B．最久未被使用

C．駐留時(shí)間最長(zhǎng)D．駐留時(shí)間最短若進(jìn)程執(zhí)行到某條指令時(shí)發(fā)生了缺頁(yè)中斷，經(jīng)