主存擴(kuò)充虛擬內(nèi)存課件

1、4.5 主存擴(kuò)充(虛擬內(nèi)存)為了使程序員在編程時(shí)不受內(nèi)存的結(jié)構(gòu)和容量的限制，系統(tǒng)為用戶構(gòu)造一種存儲(chǔ)器，其結(jié)構(gòu)可能與內(nèi)存結(jié)構(gòu)不同，容量可能遠(yuǎn)遠(yuǎn)超過內(nèi)存的實(shí)際容量。這種面向編程的存儲(chǔ)器稱為虛擬存儲(chǔ)器。由虛存構(gòu)成的存儲(chǔ)空間稱為虛存空間,或稱虛地址空間。2022/10/14第四章 存儲(chǔ)管理4.5 主存擴(kuò)充(虛擬內(nèi)存)為了使程序員在編程時(shí)不受內(nèi)存的結(jié)程序局部性原理時(shí)間局部性 一條指令被執(zhí)行了，則在不久的將來它可能再被執(zhí)行空間局部性 若某一存儲(chǔ)單元被使用，則在一定時(shí)間內(nèi)，與該存儲(chǔ)單元相鄰的單元也可能被使用2022/10/14第四章 存儲(chǔ)管理程序局部性原理時(shí)間局部性2022/10/10第四章 存儲(chǔ)管理實(shí)現(xiàn)虛

2、擬內(nèi)存的基本原理將程序正在使用的部分內(nèi)容放在內(nèi)存，暫時(shí)不用的部分放在外存，在需要時(shí)由系統(tǒng)調(diào)入內(nèi)存，并將不需要（或暫不需要）的部分調(diào)出內(nèi)存。由操作系統(tǒng)結(jié)合相關(guān)硬件來完成上述工作計(jì)算機(jī)好象為用戶提供了一個(gè)容量遠(yuǎn)大于內(nèi)存的存儲(chǔ)器，這個(gè)存儲(chǔ)器稱為虛擬存儲(chǔ)器。 2022/10/14第四章 存儲(chǔ)管理實(shí)現(xiàn)虛擬內(nèi)存的基本原理將程序正在使用的部分內(nèi)容放在內(nèi)存，暫時(shí)4.6虛擬頁式存儲(chǔ)管理1、基本思想在進(jìn)程開始運(yùn)行之前，不是裝入全部頁面，而是裝入幾個(gè)或零個(gè)頁面，之后根據(jù)進(jìn)程運(yùn)行的需要，動(dòng)態(tài)裝入其它頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，則根據(jù)某種算法淘汰某個(gè)頁面，以便裝入新的頁面2022/10/14第四章 存

3、儲(chǔ)管理4.6虛擬頁式存儲(chǔ)管理1、基本思想2022/10/10第四章XXXX7X5XXX340612虛地址空間物理地址空間 虛頁頁框2022/10/14第四章 存儲(chǔ)管理XXXX7X5XXX340612虛地址空間物理地址空間 2、頁表表項(xiàng)頁號、內(nèi)存塊號、駐留位、外存地址、訪問位、修改位駐留位：表示該頁是在內(nèi)存還是在外存訪問位：根據(jù)訪問位來決定淘汰哪頁（由不同的算法決定）修改位：查看此頁是否在內(nèi)存中被修改過頁號中斷位內(nèi)存塊號外存地址訪問位修改位2022/10/14第四章 存儲(chǔ)管理2、頁表表項(xiàng)頁號、內(nèi)存塊號、駐留位、外存地址、訪問位、修改位151413121110 9 8 7 6 5 4 3 2 10

4、000000000000000111100001011000000000000011110010001110100110101 00010000000000100011000000000100110在/不在內(nèi)存頁表虛地址8196物理地址245802022/10/14第四章 存儲(chǔ)管理151413121110 9 8 7 6 5 43、缺頁中斷（Page Fault）處理在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，則產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，準(zhǔn)備將該頁調(diào)入內(nèi)存此時(shí)應(yīng)將缺頁的進(jìn)程掛起（調(diào)頁完成再喚醒）2022/10/14第四章

5、存儲(chǔ)管理3、缺頁中斷（Page Fault）處理在地址映射過程中，在缺頁中斷與一般中斷都是中斷相同點(diǎn)：保護(hù)現(xiàn)場 中斷處理 恢復(fù)現(xiàn)場不同點(diǎn)：一般中斷是一條指令完成后中斷，缺頁中斷是一條指令執(zhí)行時(shí)中斷一條指令執(zhí)行時(shí)可能產(chǎn)生多個(gè)缺頁中斷。如指令可能訪問多個(gè)內(nèi)存地址，這些地址在不同的頁中。2022/10/14第四章 存儲(chǔ)管理缺頁中斷與一般中斷都是中斷2022/10/10第四章 存儲(chǔ)管4.6.2 頁面分配策略和算法為進(jìn)程分配物理塊要解決三個(gè)問題：第一，確定最少物理塊數(shù)；第二，分配的物理塊數(shù)目是否可變；第三，不同的進(jìn)程所分配的物理塊數(shù)是否相同2022/10/14第四章 存儲(chǔ)管理4.6.2 頁面分配策略和算

6、法為進(jìn)程分配物理塊要解決三個(gè)問1、最小物理塊數(shù)最少物理塊數(shù)是指能保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù)。若少于此值時(shí)，進(jìn)程將無法運(yùn)行。進(jìn)程應(yīng)獲得的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式 2022/10/14第四章 存儲(chǔ)管理1、最小物理塊數(shù)最少物理塊數(shù)是指能保證進(jìn)程正常運(yùn)行所需的最少2、頁面分配和置換策略兩種分配策略：固定分配 和 可變分配。兩種置換策略：全局置換 和 局部置換。組合后有三種方式:固定分配局部置換可變分配全局置換可變分配局部置換2022/10/14第四章 存儲(chǔ)管理2、頁面分配和置換策略兩種分配策略：固定分配 和 可變分配。固定分配局部置換 (1)基于進(jìn)程

7、的類型或根據(jù)程序員的要求，為每個(gè)進(jìn)程分配一定數(shù)目的內(nèi)存空間，如M個(gè)頁框，在整個(gè)運(yùn)行期間都不再改變。(2)發(fā)現(xiàn)缺頁時(shí)從該進(jìn)程在內(nèi)存的M個(gè)頁面中選出一頁換出。存在問題：一定數(shù)目的內(nèi)存空間難以確定，太少，會(huì)頻繁地出現(xiàn)缺頁中斷；太多，使內(nèi)存中駐留的進(jìn)程數(shù)目減少。 2022/10/14第四章 存儲(chǔ)管理固定分配局部置換 (1)基于進(jìn)程的類型或根據(jù)程序員的要求，為可變分配全局置換 (1)OS保持一個(gè)空閑物理塊隊(duì)列，先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊。(2)發(fā)現(xiàn)缺頁時(shí)，由系統(tǒng)從空閑物理塊隊(duì)列中，取出一物理塊分配給該進(jìn)程，并將欲調(diào)入的缺頁裝入其中。(3)當(dāng)空閑物理塊隊(duì)列中的物理塊用完時(shí)，才從內(nèi)存中選擇一頁調(diào)出，該

8、頁可能是系統(tǒng)中任一進(jìn)程的頁。是最易于實(shí)現(xiàn)的一種策略。 2022/10/14第四章 存儲(chǔ)管理可變分配全局置換 (1)OS保持一個(gè)空閑物理塊隊(duì)列，先為每個(gè)可變分配局部置換 先根據(jù)進(jìn)程的類型或程序員的要求，為每個(gè)進(jìn)程分配一定數(shù)目的物理塊；發(fā)生缺頁時(shí),只從該進(jìn)程在內(nèi)存的頁面中選出一頁換出。如果頻繁地發(fā)生缺頁中斷，則再為之分配若干物理塊，直至缺頁率減低到適當(dāng)程度為止；反之，若缺頁率特別低，則適當(dāng)減少物理塊。 2022/10/14第四章 存儲(chǔ)管理可變分配局部置換 先根據(jù)進(jìn)程的類型或程序員的要求，為每個(gè)進(jìn)程3、物理塊分配算法平均分配算法按比例分配算法考慮優(yōu)先權(quán)的分配算法2022/10/14第四章 存儲(chǔ)管理3

9、、物理塊分配算法平均分配算法2022/10/10第四章 存平均分配算法將可供分配的物理塊，平均分配給各個(gè)進(jìn)程。這種方式未考慮到各進(jìn)程本身的大小，表面公平造成實(shí)際不公平。 2022/10/14第四章 存儲(chǔ)管理平均分配算法2022/10/10第四章 存儲(chǔ)管理按比例分配算法 根據(jù)進(jìn)程的大小按比例分配物理塊。n個(gè)進(jìn)程，每個(gè)進(jìn)程的頁面數(shù)是Si,則系統(tǒng)中頁面總數(shù)為：物理塊 的總數(shù)為m，進(jìn)程i所能分到的物理塊數(shù)注意：應(yīng)該取整，且必須大于最小物理塊數(shù)。2022/10/14第四章 存儲(chǔ)管理按比例分配算法 根據(jù)進(jìn)程的大小按比例分配物理塊。物理塊 的總考慮優(yōu)先權(quán)的分配算法 為優(yōu)先權(quán)高的分配較多的內(nèi)存空間。通常把內(nèi)存

10、中可供分配的物理塊分成兩部分：一部分按比例地分配給各進(jìn)程；一部分則根據(jù)各進(jìn)程的優(yōu)先權(quán)應(yīng)適當(dāng)增加的物理塊數(shù)，分配給各進(jìn)程。2022/10/14第四章 存儲(chǔ)管理考慮優(yōu)先權(quán)的分配算法 為優(yōu)先權(quán)高的分配較多的內(nèi)存空間。2024.6.3 頁面調(diào)入策略1、何時(shí)調(diào)入頁面2、從何處調(diào)入頁面3、頁面調(diào)入過程2022/10/14第四章 存儲(chǔ)管理4.6.3 頁面調(diào)入策略1、何時(shí)調(diào)入頁面2022/10/11、何時(shí)調(diào)入頁面預(yù)調(diào)頁 和 請求調(diào)頁（1）預(yù)調(diào)頁策略預(yù)調(diào)頁策略以預(yù)測為基礎(chǔ)，將那些預(yù)計(jì)在不久之后便會(huì)被訪問的程序或數(shù)據(jù)所在的頁面預(yù)先調(diào)入內(nèi)存，如一次調(diào)入若干個(gè)相鄰的頁。但預(yù)測很難準(zhǔn)確，所以預(yù)調(diào)頁的成功率僅約一半。這種

11、策略主要用于進(jìn)程的首次調(diào)入時(shí)，由程序員指出應(yīng)該先調(diào)入哪些頁。2022/10/14第四章 存儲(chǔ)管理1、何時(shí)調(diào)入頁面預(yù)調(diào)頁 和 請求調(diào)頁2022/10/10第四（2）請求調(diào)頁策賂 即進(jìn)程在運(yùn)行中發(fā)現(xiàn)所要訪問的頁面不在內(nèi)存時(shí)，立即提出請求，由系統(tǒng)將其所需頁面調(diào)入內(nèi)存。請求調(diào)頁策略易于實(shí)現(xiàn)，在目前的虛擬存儲(chǔ)器中，大多采用此策略。缺點(diǎn)：因?yàn)槊看握埱笾徽{(diào)入一頁，增加了磁盤IO的啟動(dòng)頻率，系統(tǒng)開銷大。2022/10/14第四章 存儲(chǔ)管理（2）請求調(diào)頁策賂 2022/10/10第四章 存儲(chǔ)管理2、從何處調(diào)入頁面請求分頁系統(tǒng)中，外存分為文件區(qū)和對換區(qū)。分三種情況: (1)系統(tǒng)有足夠的對換區(qū)空間，在進(jìn)程運(yùn)行前，將

12、與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對換區(qū)，全部從對換區(qū)調(diào)入所需頁面，調(diào)頁速度快。 2022/10/14第四章 存儲(chǔ)管理2、從何處調(diào)入頁面請求分頁系統(tǒng)中，外存分為文件區(qū)和對換區(qū)。2(2)系統(tǒng)缺少足夠的對換區(qū)空間不會(huì)被修改的文件，直接從文件區(qū)調(diào)入，換出時(shí)不寫回，再調(diào)入時(shí)仍從文件區(qū)直接調(diào)入；對可能被修改的部分，換出時(shí)換到對換區(qū)，再調(diào)入時(shí)從對換區(qū)調(diào)入。(3)UNIX方式未運(yùn)行過的頁面，都從文件區(qū)調(diào)入;曾經(jīng)運(yùn)行過而又被換出的頁面被放在對換區(qū)，再次調(diào)入時(shí)從對換區(qū)調(diào)入。允許頁面共享，某進(jìn)程請求的頁面有可能已被其它進(jìn)程調(diào)入內(nèi)存，不用再從對換區(qū)調(diào)入 2022/10/14第四章 存儲(chǔ)管理(2)系統(tǒng)缺少足夠的對換區(qū)

13、空間2022/10/10第四章 存3、頁面調(diào)入過程程序所要訪問的頁面未在內(nèi)存時(shí)，向CPU發(fā)出缺頁中斷，由中斷處理程序首先保留CPU環(huán)境，分析中斷原因，轉(zhuǎn)入缺頁中斷處理程序。2022/10/14第四章 存儲(chǔ)管理3、頁面調(diào)入過程程序所要訪問的頁面未在內(nèi)存時(shí)，2022/104.7頁面淘汰算法理想淘汰算法最佳頁面算法（OPT）最近最久未使用頁面淘汰算法（LRU）先進(jìn)先出頁面淘汰算法（FIFO）2022/10/14第四章 存儲(chǔ)管理4.7頁面淘汰算法理想淘汰算法最佳頁面算法（OPT）2021、最佳置換算法 最佳置換算法是一種理想化的理論算法，具有最好的性能，但在實(shí)際上卻難于實(shí)現(xiàn)。它選擇永不使用的，或者是在

14、最長時(shí)間內(nèi)不再被訪問的頁面作為淘汰頁面。但這是無法預(yù)知的，因而該算法無法實(shí)現(xiàn)。它在固定分配頁面方式中可保證獲得最低的缺頁率。主要用于評價(jià)其他算法 2022/10/14第四章 存儲(chǔ)管理1、最佳置換算法 最佳置換算法是一種理想化的理論算法，具有最2、先進(jìn)先出頁面置換算法該算法總是淘汰最先調(diào)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時(shí)間最久的頁面予以淘汰。該算法實(shí)現(xiàn)時(shí)把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁面按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)替換指針，指向最老頁面。 實(shí)現(xiàn)簡單、性能差2022/10/14第四章 存儲(chǔ)管理2、先進(jìn)先出頁面置換算法該算法總是淘汰最先調(diào)入內(nèi)存的頁面，即3最近最久未使用（LRU）選擇最后一次訪問時(shí)間

15、距離當(dāng)前時(shí)間最長的一頁并淘汰之 即淘汰最長時(shí)間沒有使用的頁 性能較好，實(shí)現(xiàn)代價(jià)很高 軟件方法或硬件方法2022/10/14第四章 存儲(chǔ)管理3最近最久未使用（LRU）選擇最后一次訪問時(shí)間距離當(dāng)前時(shí)間最LRU的硬件實(shí)現(xiàn)：系統(tǒng)為每頁設(shè)置一個(gè)寄存器R，每當(dāng)訪問這一頁時(shí)，將該頁對應(yīng)的寄存器R高位置1，以后每個(gè)時(shí)間間隔將所有的R右移一位，R值越小，對應(yīng)的頁未被使用的時(shí)間越長。當(dāng)淘汰一頁時(shí)就選擇R值最小的頁。所以淘汰的是最久未使用的頁。R的位數(shù)越多越精確，但系統(tǒng)硬件成本也就越高。2022/10/14第四章 存儲(chǔ)管理LRU的硬件實(shí)現(xiàn)：系統(tǒng)為每頁設(shè)置一個(gè)寄存器R，2022/10LRU軟件實(shí)現(xiàn)：設(shè)置一個(gè)頁號棧，當(dāng)

16、一個(gè)頁面被訪問時(shí)，就立即將它的頁號壓入頁號棧，并檢查頁號棧中是否有與剛壓入棧頂?shù)南嗤捻撎?，若有，則從頁號棧中抽出原有的，以保證頁號棧中無相同的頁號。當(dāng)系統(tǒng)要淘汰一頁時(shí)，總是從頁號棧底取出一個(gè)頁號淘汰，即淘汰的頁是最久未使用的。2022/10/14第四章 存儲(chǔ)管理LRU軟件實(shí)現(xiàn)：設(shè)置一個(gè)頁號棧，2022/10/10第四章 LRU軟件實(shí)現(xiàn)：2022/10/14第四章 存儲(chǔ)管理LRU軟件實(shí)現(xiàn)：2022/10/10第四章 存儲(chǔ)管理 某程序在內(nèi)存中分配三個(gè)塊，訪問頁的順序?yàn)?，3，2，1，4，3，5，4，3，2，1，5，按FIFO、 LRU、OPT算法分別計(jì)算缺頁次數(shù)假設(shè)開始時(shí)所有頁均不在內(nèi)存例120

17、22/10/14第四章 存儲(chǔ)管理 某程序在內(nèi)存中分配三個(gè)塊，訪問頁的順序?yàn)?，3，2，1FIFO 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 5 5 2 1 1 4 3 2 1 4 3 3 3 5 2 2 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共缺頁中斷9次FIFO2022/10/14第四章 存儲(chǔ)管理FIFO 4 3 2 1 4 3 5 4 訪問順序4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 4 3 2 1 4 3 2 1 4 3 5 4 3 2

18、 x x x x x x x x x x共缺頁中斷10次 LRU 2022/10/14第四章 存儲(chǔ)管理 訪問順序4 3 2 1 4 3 5 4 3 OPT 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 1 1 5 5 5 2 1 1 4 3 3 3 3 3 3 3 5 5 5 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共缺頁中斷7次OPT2022/10/14第四章 存儲(chǔ)管理 OPT 4 3 2 1 4 3 5 練習(xí)某程序在內(nèi)存中分配四個(gè)塊，訪問頁的走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5，按LRU、OPT算法分別計(jì)算缺頁次數(shù)假設(shè)開始時(shí)所有

19、頁均不在內(nèi)存2022/10/14第四章 存儲(chǔ)管理練習(xí)某程序在內(nèi)存中分配四個(gè)塊，訪問頁的走向?yàn)?，3，2，1，LRU 4 3 2 1 4 3 5 4 3 2 1 5頁1 4 3 2 1 4 3 5 4 3 2 1 5頁2 4 3 2 1 4 3 5 4 3 2 1頁3 4 3 2 1 4 3 5 4 3 2頁4 4 3 2 1 1 1 5 4 3 x x x x x x x x共缺頁中斷8次2022/10/14第四章 存儲(chǔ)管理LRU 4 3 2 1 4 OPT 4 3 2 1 4 3 5 4 3 2 1 5頁1 4 3 2 1 1 1 5 5 5 5 1 1頁2 4 3 2 2 2 2 2 2

20、2 5 5頁3 4 3 3 3 3 3 3 3 3 3頁4 4 4 4 4 4 4 4 4 4 x x x x x x 共缺頁中斷6次2022/10/14第四章 存儲(chǔ)管理OPT 4 3 2 1 4 LRU近似算法：Clock算法在頁表中增加一訪問位，每當(dāng)訪問一頁時(shí)，將該頁的訪問位由硬件置1，軟件周期（T）性地將所有訪問位置0。在時(shí)間T內(nèi)，訪問過的頁訪問位為1，反之為0，淘汰為0 的頁。缺點(diǎn)：T難定。太小，訪問位為0的頁相當(dāng)多，所選的不一定是最久未用的。太大，所有頁的引用位可能都為1，找不到合適的淘汰頁。 2022/10/14第四章 存儲(chǔ)管理LRU近似算法：Clock算法在頁表中增加一訪問位，2

21、0222022/10/14第四章 存儲(chǔ)管理2022/10/10第四章 存儲(chǔ)管理改進(jìn)型Clock置換算法 由訪問位A和修改位M可以組合成下面四種類型的頁面： 1類(A=0, M=0): 表示該頁最近既未被訪問， 又未被修改， 是最佳淘汰頁。 2類(A=0, M=1)： 表示該頁最近未被訪問， 但已被修改， 并不是很好的淘汰頁。 3類(A=1, M=0)： 最近已被訪問， 但未被修改， 該頁有可能再被訪問。 4類(A=1, M=1): 最近已被訪問且被修改， 該頁可能再被訪問。 2022/10/14第四章 存儲(chǔ)管理改進(jìn)型Clock置換算法 由訪問位A和修改位M最不經(jīng)常使用（LFU）選擇訪問次數(shù)最少

22、的頁面淘汰之 與LRU的硬件解法類似。 2022/10/14第四章 存儲(chǔ)管理最不經(jīng)常使用（LFU）選擇訪問次數(shù)最少的頁面淘汰之2022/頁面緩沖算法(PBA: Page Buffering Algorithm ) 頁面緩沖算法中，被淘汰的頁存放在兩個(gè)鏈表（隊(duì)列）：頁面未修改的淘汰頁空閑頁鏈表（實(shí)質(zhì)：空閑物理塊鏈表）頁面已修改的淘汰頁已修改頁面鏈表。2022/10/14第四章 存儲(chǔ)管理頁面緩沖算法(PBA: Page Buffering Alg當(dāng)需要讀入一個(gè)頁面時(shí)，便利用空閑物理塊鏈表中的第一個(gè)物理塊來裝入。當(dāng)有一個(gè)未被修改的頁要換出時(shí)，并不將它換出內(nèi)存，而是直接把它所在的物理塊掛在空閑頁鏈表的

23、末尾。換出一個(gè)已修改的頁面時(shí)，則將其所在的物理塊掛在修改頁面鏈表的末尾。注：換出頁面時(shí)，頁面在內(nèi)存并不做物理上的移動(dòng)，只是將頁表中的表項(xiàng)移到上述兩個(gè)鏈表之一中。 2022/10/14第四章 存儲(chǔ)管理當(dāng)需要讀入一個(gè)頁面時(shí)，便利用空閑物理塊鏈表中的第一個(gè)物理塊來優(yōu)點(diǎn)：可使已被修改的頁面和未被修改的頁面，都仍留在內(nèi)存中。當(dāng)進(jìn)程以后再次訪問這些頁面時(shí)，就有可能只須花費(fèi)較小的開銷。只有當(dāng)被修改頁面達(dá)到一定數(shù)量，例如64個(gè)頁面時(shí)，再將它們一起寫回到磁盤，從而顯著地減少了磁盤IO的操作次數(shù)。2022/10/14第四章 存儲(chǔ)管理優(yōu)點(diǎn)：可使已被修改的頁面和未被修改的頁面，都仍留在內(nèi)存中。當(dāng)(1) 分配給進(jìn)程的物

24、理塊數(shù)(2) 頁本身的大小(3) 程序的編制方法(練習(xí)）(4) 頁淘汰算法影響缺頁次數(shù)的因素2022/10/14第四章 存儲(chǔ)管理(1) 分配給進(jìn)程的物理塊數(shù)影響缺頁次數(shù)的因素2022/10思考：分配給進(jìn)程的物理塊數(shù)增加缺頁次數(shù)一定能夠減少？例2有一虛擬存儲(chǔ)系統(tǒng)，采用先進(jìn)先出的頁面淘汰算法。在內(nèi)存中為每個(gè)進(jìn)程分配3塊。進(jìn)程執(zhí)行時(shí)使用頁號的順序?yàn)?4 3 2 1 4 3 5 4 3 2 1 5(1)該進(jìn)程運(yùn)行時(shí)總共出現(xiàn)幾次缺頁。(2)若每個(gè)進(jìn)程在內(nèi)存有4塊，又將產(chǎn)生幾次缺頁。(3)如何解釋所出現(xiàn)的現(xiàn)象。 2022/10/14第四章 存儲(chǔ)管理思考：分配給進(jìn)程的物理塊數(shù)增加缺頁次數(shù)一定能夠減少？ 20

25、2FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁1 4 3 2 1 4 3 5 5 5 2 1 1頁2 4 3 2 1 4 3 3 3 5 2 2頁3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共缺頁中斷9次m=32022/10/14第四章 存儲(chǔ)管理FIFO 4 3 2 1 4 3 5 4FIFO 4 3 2 1 4 3 5 4 3 2 1 5頁1 4 3 2 1 1 1 5 4 3 2 1 5頁2 4 3 2 2 2 1 5 4 3 2 1頁3 4 3 3 3 2 1 5 4 3 2頁4 4 4 4 3 2 1 5 4 3 x x x x x x

26、 x x x x共缺頁中斷10次m=42022/10/14第四章 存儲(chǔ)管理FIFO 4 3 2 1 4 3 5 4m=3時(shí)，缺頁中斷9次， 缺頁率9/12=75%m=4時(shí)，缺頁中斷10次， 缺頁率10/12=83%FIFO頁面淘汰算法會(huì)產(chǎn)生異?，F(xiàn)象（稱為Belady現(xiàn)象），即：當(dāng)分配給進(jìn)程的物理頁面數(shù)增加時(shí)，缺頁次數(shù)反而增加2022/10/14第四章 存儲(chǔ)管理m=3時(shí)，缺頁中斷9次，2022/10/10第四章 存儲(chǔ)管理練習(xí)：程序?qū)θ表摰挠绊懗绦蚓幹品椒?：for j:=1 to 128 for i:=1 to 128 Ai,j:=0;程序編制方法2：for i:=1 to 128 for j:

27、=1 to 128 Ai,j:=0;內(nèi)存分配一頁，初始時(shí)矩陣數(shù)據(jù)均不在內(nèi)存；頁面大小為128個(gè)整數(shù)；矩陣A128X128按行存放。這兩個(gè)程序執(zhí)行時(shí)分別會(huì)產(chǎn)生多少次缺頁中斷？2022/10/14第四章 存儲(chǔ)管理練習(xí)：程序?qū)θ表摰挠绊懗绦蚓幹品椒?：程序編制方法2：內(nèi)存分解程序編制方法1：for j:=1 to 128 for i:=1 to 128 Ai,j:=0;程序編制方法2：for i:=1 to 128 for j:=1 to 128 Ai,j:=0;128*1281282022/10/14第四章 存儲(chǔ)管理解程序編制方法1：程序編制方法2：128*128128202 在虛存中，頁面在內(nèi)存

28、與外存之間頻繁調(diào)度，以至于調(diào)度頁面所需時(shí)間比進(jìn)程實(shí)際運(yùn)行的時(shí)間還多，此時(shí)系統(tǒng)效率急劇下降，甚至導(dǎo)致系統(tǒng)崩潰。這種現(xiàn)象稱為顛簸或抖動(dòng)原因：頁面淘汰算法不合理分配給進(jìn)程的物理頁面數(shù)太少顛簸（抖動(dòng)）2022/10/14第四章 存儲(chǔ)管理 在虛存中，頁面在內(nèi)存與外存之間頻繁調(diào)度，以至于調(diào)度頁面解決基本思想：根據(jù)程序局部性原理，一般進(jìn)程在一段時(shí)間內(nèi)總是集中訪問一些頁面，這些頁面稱為活躍頁面，如果分配給一個(gè)進(jìn)程的物理頁面數(shù)太少了，使該進(jìn)程所需的活躍頁面不能全部裝入內(nèi)存，則進(jìn)程在運(yùn)行過程中將頻繁發(fā)生中斷如果能為進(jìn)程提供與活躍頁面數(shù)相等的物理頁面數(shù)，則可減少缺頁中斷次數(shù)對于給定的訪問序列選取定長的區(qū)間，稱為工作

29、集窗口，落在工作集窗口中的頁面集合稱為工作集2022/10/14第四章 存儲(chǔ)管理解決基本思想：根據(jù)程序局部性原理，一般進(jìn)程在一段時(shí)間內(nèi)總是集例如工作集某段時(shí)間內(nèi)進(jìn)程使用過的頁面的集合。N=105554777511623415341555343433312323444控制缺頁率范圍Ws(t1)=1,4,5,7 t1Ws(t1)=3,4,5 t22022/10/14第四章 存儲(chǔ)管理例如工作集Ws(t1)=1,4,5,7 t1Ws(t1)1、基本機(jī)制2、分段共享3、分段保護(hù) 4.8 虛擬段式存儲(chǔ)管理2022/10/14第四章 存儲(chǔ)管理1、基本機(jī)制4.8 虛擬段式存儲(chǔ)管理2022/10/10第四1、段

30、表內(nèi)容 增加：存取方式：標(biāo)識(shí)段的存取屬性是只執(zhí)行、只讀或允許讀寫。訪問字段A：記錄該段被訪問的頻繁程度。修改位M：表示該段進(jìn)入內(nèi)存后，是否已被修改過。存在位：指示是否已調(diào)入內(nèi)存。增補(bǔ)位：指示本段在運(yùn)行過程中，是否進(jìn)行過動(dòng)態(tài)增長。外存始址：指示本段在外存中的起始地址，即起始盤塊號。基本機(jī)制2022/10/14第四章 存儲(chǔ)管理1、段表內(nèi)容基本機(jī)制2022/10/10第四章 存儲(chǔ)管理2、缺段中斷處理檢查內(nèi)存中是否有足夠的空閑空間 若有，則裝入該段，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)，中斷返回 若沒有，內(nèi)存中空閑區(qū)的總和是否滿足要求？是，采用緊縮技術(shù)，轉(zhuǎn) ； 否，淘汰一（些）段，轉(zhuǎn) P139 圖4-31 3、地址變換

31、P140 圖4-32基本機(jī)制2022/10/14第四章 存儲(chǔ)管理2、缺段中斷處理基本機(jī)制2022/10/10第四章 存儲(chǔ)管理2022/10/14第四章 存儲(chǔ)管理2022/10/10第四章 存儲(chǔ)管理2、分段共享與保護(hù)共享段表：在系統(tǒng)中配置一張共享段表，所有共享段都在共享段表中占有一表項(xiàng)，表項(xiàng)中記錄了共享段的段號和段長、內(nèi)存始址、存在位等信息，并記錄了共享此分段的每個(gè)進(jìn)程的情況。 P140 圖 4-332022/10/14第四章 存儲(chǔ)管理2、分段共享與保護(hù)共享段表：2022/10/10第四章 存儲(chǔ)（1）共享進(jìn)程計(jì)數(shù)count整型變量，記錄共享該分段的進(jìn)程數(shù)。共享段只有當(dāng)所有共享該段的進(jìn)程全都不再需要它時(shí)，才由系統(tǒng)回收該段所占內(nèi)存區(qū)。（2）存取控制字段不同的進(jìn)程對同一共享段有不同的存取權(quán)限。（3）段號 不同的進(jìn)程可以使用不同的段號去共享該段。共享段表項(xiàng)2022/10/14第四章 存儲(chǔ)管理（1）共享進(jìn)程計(jì)數(shù)count共享段表項(xiàng)2022/10/10第例子2022/10/14第四章 存儲(chǔ)管理例