第7章虛擬內(nèi)存管理

1、第七章第七章 虛擬內(nèi)存管理虛擬內(nèi)存管理 n對(duì)于需要將程序一次性裝入內(nèi)存才能運(yùn)行的存儲(chǔ)管理方案來(lái)說，其缺點(diǎn)是明顯的。一方面，當(dāng)一個(gè)參與并發(fā)執(zhí)行的進(jìn)程運(yùn)行時(shí)，其整個(gè)程序必須都在內(nèi)存；若進(jìn)程的程序比內(nèi)存可用空間還大，該程序?qū)o(wú)法裝入內(nèi)存運(yùn)行。另一方面，程序被裝入內(nèi)存后，便一直駐留在內(nèi)存直至程序運(yùn)行結(jié)束才釋放內(nèi)存，這就會(huì)使一些需要盡快運(yùn)行的作業(yè)無(wú)法被裝入運(yùn)行；更嚴(yán)重的是，若進(jìn)程因IO而長(zhǎng)期等待或程序暫時(shí)不執(zhí)行的時(shí)候，它將一直占有內(nèi)存資源，導(dǎo)致內(nèi)存不能得到充分的利用。n虛擬內(nèi)存管理就是為了解決上述問題而產(chǎn)生的。這種技術(shù)把內(nèi)存和外存結(jié)合起來(lái)，為用戶程序提供一個(gè)容量遠(yuǎn)大于物理存儲(chǔ)器的虛擬存儲(chǔ)空間；用戶程序可

2、以先只裝入一部分就開始執(zhí)行，以后根據(jù)執(zhí)行的具體情況再依次請(qǐng)求裝入剩下的部分，直至整個(gè)程序都執(zhí)行完畢。這就從邏輯上擴(kuò)充了內(nèi)存容量，有效地解決了上述問題。n本章介紹虛擬內(nèi)存管理的相關(guān)知識(shí)。首先介紹虛擬內(nèi)存管理的一些基本概念；然后分別闡述幾種典型的虛擬內(nèi)存管理方法：請(qǐng)求分頁(yè)管理方式、請(qǐng)求分段管理方式和請(qǐng)求段頁(yè)式管理方式。2022-3-3127.1虛擬存儲(chǔ)基本概念虛擬存儲(chǔ)基本概念 7.2請(qǐng)求分頁(yè)管理方式請(qǐng)求分頁(yè)管理方式7.3請(qǐng)求分段管理方式請(qǐng)求分段管理方式7.4請(qǐng)求段頁(yè)式管理方式請(qǐng)求段頁(yè)式管理方式2022-3-3137.1 虛擬存儲(chǔ)基本概念虛擬存儲(chǔ)基本概念7.1.1虛擬存儲(chǔ)的引入虛擬存儲(chǔ)的引入 7.1

3、.2虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù) 2022-3-3147.1.1虛擬存儲(chǔ)的引入虛擬存儲(chǔ)的引入 n在上一章中，我們介紹的分配管理技術(shù)是針對(duì)實(shí)際物理內(nèi)存空間的。這一類管理技術(shù)具有兩個(gè)特性：1）程序的裝入是一次性的。即在程序運(yùn)行之前，要求一次性地將程序所有內(nèi)容都裝入內(nèi)存，而不管程序的執(zhí)行目前是否需要這些全部?jī)?nèi)容。2）程序被裝入內(nèi)存后，便一直駐留在內(nèi)存直至程序運(yùn)行結(jié)束，也不管程序的執(zhí)行目前是否真正需要某一內(nèi)容。一次性和駐留性這兩個(gè)特性使得這一類管理技術(shù)表現(xiàn)出內(nèi)存利用率低、系統(tǒng)吞吐量小等明顯缺點(diǎn)。因此，我們就自然地思考，如果可以否定一次性和駐留性，也許可以提出一種改進(jìn)的存儲(chǔ)管理技術(shù)，以提高內(nèi)存利用率

4、和系統(tǒng)吞吐量。n程序的一次性和駐留性是否可以否定？程序局部性原理回答了這一問題，它說明程序的一次性與駐留性都是不必要的；這樣就可以提出改進(jìn)的存儲(chǔ)管理技術(shù)，即虛擬存儲(chǔ)。2022-3-3157.1.1虛擬存儲(chǔ)的引入虛擬存儲(chǔ)的引入（一）程序局部性原理（一）程序局部性原理 n早在1968年，P.Denning就在長(zhǎng)期的研究中發(fā)現(xiàn)了程序的局部性原理。它是指程序在執(zhí)行過程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指令地址會(huì)較集中地出現(xiàn)在某一部分，呈現(xiàn)出程序局部性現(xiàn)象。2022-3-3167.1.1虛擬存儲(chǔ)的引入虛擬存儲(chǔ)的引入n程序局部性現(xiàn)象說明：在一個(gè)較短的執(zhí)行時(shí)間間隔內(nèi)，程序只執(zhí)行程序的一部分，而不會(huì)執(zhí)行程序的全部?jī)?nèi)

5、容；同時(shí)，執(zhí)行訪問的存儲(chǔ)空間也局限于某一區(qū)域，而不會(huì)遍歷所有存儲(chǔ)空間。這就是程序局部性原理。n程序局部性原理體現(xiàn)在時(shí)間局部性和空間局部性兩個(gè)方面：（1）時(shí)間局部性）時(shí)間局部性（2）空間局部性）空間局部性2022-3-3177.1.1虛擬存儲(chǔ)的引入虛擬存儲(chǔ)的引入（1）時(shí)間局部性）時(shí)間局部性n時(shí)間局部性是指程序中的一條指令執(zhí)行后可能會(huì)再次執(zhí)行，或某個(gè)數(shù)據(jù)被訪問后也可能再次被訪問。這主要是由程序中存在大量的循環(huán)操作導(dǎo)致的；（2）空間局部性）空間局部性n空間局部性是指程序在一段時(shí)間內(nèi)所訪問的地址可能集中在定的范圍內(nèi)。這主要是由于程序中存在大量的順序執(zhí)行。n程序局部性原理可以說明：程序的一次性與駐留性都

6、是不必要的。2022-3-3187.1.1虛擬存儲(chǔ)的引入虛擬存儲(chǔ)的引入（二）虛擬存儲(chǔ)的基本思想（二）虛擬存儲(chǔ)的基本思想n因?yàn)閮?nèi)存空間的有限性，系統(tǒng)無(wú)法全部裝入比它大的程序并執(zhí)行相應(yīng)進(jìn)程。如果系統(tǒng)要運(yùn)行比內(nèi)存空間大的進(jìn)程，可以在進(jìn)程執(zhí)行時(shí)只調(diào)入當(dāng)前所需要的部分程序，而不用把全部程序都調(diào)入內(nèi)存，以后在執(zhí)行的過程中根據(jù)需要裝入其它部分。程序運(yùn)行過程中暫不需要的部分程序也沒有必要始終駐留在內(nèi)存中，可以將它們移出到外存以釋放空間來(lái)裝入其它需要的程序部分。這樣，就可以將內(nèi)存和比內(nèi)存大的多的外存兩者結(jié)合起來(lái)使用，利用調(diào)入、調(diào)出等操作的支持，形成了一個(gè)比內(nèi)存空間大得多的、邏輯的虛擬內(nèi)存空間。這就是虛擬存儲(chǔ)器。

7、n總之，虛擬存儲(chǔ)是一種實(shí)現(xiàn)虛擬存儲(chǔ)器的技術(shù)。這一技術(shù)通過離散化存儲(chǔ)（以程序的子部分為單位分配和裝入內(nèi)存）、請(qǐng)求調(diào)入（即根據(jù)進(jìn)程執(zhí)行的需要來(lái)調(diào)入某些程序子部分）、置換（即將暫不需要的程序子部分調(diào)出到外存以釋放空間）等功能，來(lái)構(gòu)造一個(gè)比內(nèi)存空間大得多的、虛擬內(nèi)存空間；該空間的邏輯容量由外存和內(nèi)存容量之和決定，而運(yùn)行速度接近于內(nèi)存速度，從而從邏輯上擴(kuò)充了內(nèi)存容量。2022-3-3197.1.1虛擬存儲(chǔ)的引入虛擬存儲(chǔ)的引入（三）虛擬存儲(chǔ)的特性（三）虛擬存儲(chǔ)的特性 n虛擬內(nèi)存管理技術(shù)是在內(nèi)存存儲(chǔ)管理技術(shù)的基礎(chǔ)上改進(jìn)得到的，它與上一章敘述的物理內(nèi)存存儲(chǔ)管理技術(shù)之間既有繼承，更體現(xiàn)出明顯的區(qū)別。從中可以看出

8、虛擬存儲(chǔ)具有程序分配方式的非連續(xù)性、程序調(diào)入方式的多次性、程序駐留方式的交換性以及總體表現(xiàn)出的存儲(chǔ)管理虛擬性等特性。 表7.1 虛擬內(nèi)存存儲(chǔ)管理與物理內(nèi)存存儲(chǔ)管理的比較程序方式程序方式物理內(nèi)存存儲(chǔ)管理物理內(nèi)存存儲(chǔ)管理 虛擬內(nèi)存存儲(chǔ)管理虛擬內(nèi)存存儲(chǔ)管理程序分配方式連續(xù)性非連續(xù)性程序駐留方式駐留性交換性程序調(diào)入方式一次性多次性2022-3-31107.1.2虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)n虛擬存儲(chǔ)在實(shí)現(xiàn)時(shí)，首先需要將程序邏輯地址空間離散化，即將程序劃分為若干子部分，并以程序的子部分為單位來(lái)分配內(nèi)存。因此，虛擬存儲(chǔ)的實(shí)現(xiàn)必須以非連續(xù)分配管理方式為基礎(chǔ)。具體而言，可以將程序劃分為頁(yè)、段或段頁(yè)結(jié)合，然

9、后請(qǐng)求調(diào)入、置換等功能都將基于相應(yīng)的非連續(xù)分配管理方式來(lái)具體實(shí)現(xiàn)。n至此，虛擬存儲(chǔ)器的實(shí)現(xiàn)技術(shù)可以分為三種：n采用以分頁(yè)管理方式為基礎(chǔ)的請(qǐng)求分頁(yè)管理方式n以分段管理方式為基礎(chǔ)的請(qǐng)求分段管理方式n以段頁(yè)式管理方式為基礎(chǔ)的請(qǐng)求段頁(yè)式管理方式。 2022-3-31117.1.2虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)（一）請(qǐng)求分頁(yè)管理方式（一）請(qǐng)求分頁(yè)管理方式 n請(qǐng)求分頁(yè)管理方式是在分頁(yè)管理方式的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)、頁(yè)面置換等功能而形成的。它允許只裝入若干頁(yè)面的用戶程序和數(shù)據(jù)，便可啟動(dòng)運(yùn)行。以后，再通過調(diào)頁(yè)功能和頁(yè)面置換等功能，陸續(xù)地把將要運(yùn)行的頁(yè)面調(diào)人內(nèi)存，同時(shí)把暫不運(yùn)行的頁(yè)面換出到外存上。置換時(shí)以頁(yè)

10、面為單位。n請(qǐng)求分頁(yè)管理方式需要系統(tǒng)提供的硬件機(jī)制主要有：n請(qǐng)求分頁(yè)的頁(yè)表機(jī)制。以分頁(yè)管理方式中的頁(yè)表機(jī)制為基礎(chǔ)，增加若干字段來(lái)構(gòu)造；用于記錄任一頁(yè)面在內(nèi)存的位置、外存的位置、是否被修改等信息。n缺頁(yè)中斷。每當(dāng)下一步要訪問的頁(yè)面尚未被調(diào)入內(nèi)存時(shí)，便產(chǎn)生一個(gè)缺頁(yè)中斷，以請(qǐng)求系統(tǒng)調(diào)入所缺的頁(yè)面。n地址變換機(jī)制。在請(qǐng)求分頁(yè)管理方式中，用于實(shí)現(xiàn)程序邏輯地址到內(nèi)存物理地址的轉(zhuǎn)換。2022-3-31127.1.2虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)（二）請(qǐng)求分段管理方式（二）請(qǐng)求分段管理方式 n請(qǐng)求分段管理方式是在分段管理方式的基礎(chǔ)上，增加了請(qǐng)求調(diào)段、分段置換等功能而形成的。它允許開始時(shí)只裝入若干段的用戶程序

11、和數(shù)據(jù)，即可啟動(dòng)運(yùn)行。以后，再通過調(diào)段功能和分段置換等功能，將暫不運(yùn)行的段調(diào)出，同時(shí)調(diào)入即將運(yùn)行的段。置換時(shí)以段為單位進(jìn)行。n請(qǐng)求分段管理方式需要系統(tǒng)提供的硬件機(jī)制主要有：n請(qǐng)求分段的段表機(jī)制。以分段管理方式中的段表機(jī)制為基礎(chǔ)，增加若干字段來(lái)構(gòu)造；用于記錄一個(gè)程序的任一段在內(nèi)存的位置、外存的位置、存取方式、是否被修改等信息。n缺段中斷。每當(dāng)下一步要訪問的段尚未被調(diào)入內(nèi)存時(shí)，便產(chǎn)生一個(gè)缺段中斷，以請(qǐng)求系統(tǒng)調(diào)入所缺的段。n地址變換機(jī)制。用于實(shí)現(xiàn)請(qǐng)求分段管理方式下的從程序邏輯地址到內(nèi)存物理地址的轉(zhuǎn)換。2022-3-31137.1.2虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)（三）請(qǐng)求段頁(yè)式管理方式（三）請(qǐng)求段

12、頁(yè)式管理方式 n請(qǐng)求段頁(yè)式管理方式結(jié)合了請(qǐng)求分頁(yè)和請(qǐng)求分段兩種管理方式的優(yōu)點(diǎn)。外存中的程序用分段方法來(lái)分配和管理，而內(nèi)存中的進(jìn)程則用分頁(yè)方法來(lái)分配和管理，使得一個(gè)段可以裝載到若干不連續(xù)的空閑物理塊中。n請(qǐng)求段頁(yè)式管理方式是在段頁(yè)式管理方式的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)、請(qǐng)求調(diào)段、段/頁(yè)置換等功能。n請(qǐng)求段頁(yè)式管理方式需要系統(tǒng)提供的硬件機(jī)制有：請(qǐng)求分頁(yè)的頁(yè)表機(jī)制、請(qǐng)求分段的段表機(jī)制、缺段中斷機(jī)構(gòu)、地址變換機(jī)構(gòu)等。2022-3-31147.2 請(qǐng)求分頁(yè)管理方式請(qǐng)求分頁(yè)管理方式7.2.1請(qǐng)求分頁(yè)分配基本思想請(qǐng)求分頁(yè)分配基本思想7.2.2請(qǐng)求分頁(yè)分配管理請(qǐng)求分頁(yè)分配管理 7.2.3頁(yè)面分配頁(yè)面分配7.2.4

13、頁(yè)面置換頁(yè)面置換7.2.5抖動(dòng)處理抖動(dòng)處理2022-3-31157.2.1請(qǐng)求分頁(yè)分配基本思想請(qǐng)求分頁(yè)分配基本思想n請(qǐng)求分頁(yè)分配方式的基本思想可描述為如下過程：1)首先，內(nèi)存空間被劃分成若干等長(zhǎng)的物理塊，并對(duì)塊編號(hào)；同時(shí)，程序仍然被分為若干與物理塊等長(zhǎng)的頁(yè)面，也對(duì)其編號(hào)。2)在進(jìn)程開始執(zhí)行之前，不是將程序包含的所有頁(yè)面一次性地全部裝入內(nèi)存，而是將進(jìn)程當(dāng)前需要的一部分頁(yè)面裝入內(nèi)存，使得進(jìn)程可以開始執(zhí)行。3)在進(jìn)程運(yùn)行過程中，如果所訪問的頁(yè)面在內(nèi)存，則對(duì)其管理與分頁(yè)存儲(chǔ)管理情形相同；若發(fā)現(xiàn)所要訪問的數(shù)據(jù)或指令不在內(nèi)存，便會(huì)產(chǎn)生缺頁(yè)中斷，到外存找到包含所需數(shù)據(jù)或指令的頁(yè)面，并動(dòng)態(tài)地將其裝入到內(nèi)存的空

14、閑塊中。在動(dòng)態(tài)裝入一個(gè)頁(yè)面時(shí)，若發(fā)現(xiàn)內(nèi)存無(wú)空閑塊或分配給該進(jìn)程的物理塊已用完，則從已在內(nèi)存的若干頁(yè)面中選出一個(gè)將其淘汰，釋放所占的物理塊后將新的頁(yè)面裝入其中，進(jìn)程繼續(xù)運(yùn)行。被淘汰的頁(yè)面如果剛才在內(nèi)存被修改過，還需要回寫到外存，以保留最新的內(nèi)容。系統(tǒng)反復(fù)進(jìn)行這樣的過程，直至進(jìn)程運(yùn)行結(jié)束。n從上面的基本過程可以看出，請(qǐng)求分頁(yè)分配方式在許多方面與分頁(yè)分配方式是一致的；但由于允許程序裝入否定了一次性，這種方式顯得更加復(fù)雜。 2022-3-31167.2.1請(qǐng)求分頁(yè)分配基本思想請(qǐng)求分頁(yè)分配基本思想（1）頁(yè)表）頁(yè)表n需要提供一個(gè)頁(yè)表機(jī)制來(lái)記錄任一頁(yè)面在內(nèi)存的位置、外存的位置、是否被修改等信息；這一頁(yè)表比分

15、頁(yè)分配管理中的頁(yè)表要復(fù)雜，需要重新設(shè)計(jì)。（2）頁(yè)面分配策略）頁(yè)面分配策略n內(nèi)存中允許裝入多個(gè)進(jìn)程，每一進(jìn)程占有一部分物理塊；問題是對(duì)這多個(gè)進(jìn)程，為每一進(jìn)程分配多少物理塊才合適？采用何種分配方式才更合理？即需要一個(gè)合適的頁(yè)面分配策略。(3)缺頁(yè)中斷缺頁(yè)中斷n進(jìn)程運(yùn)行若發(fā)現(xiàn)所要訪問的數(shù)據(jù)或指令不在內(nèi)存，便會(huì)產(chǎn)生缺頁(yè)中斷，到外存尋找包含所需數(shù)據(jù)或指令的頁(yè)面。這時(shí)，缺頁(yè)中斷該如何處理？2022-3-31177.2.1請(qǐng)求分頁(yè)分配基本思想請(qǐng)求分頁(yè)分配基本思想(4)地址變換地址變換n一個(gè)頁(yè)面不管是一開始就被裝入內(nèi)存，還是以后動(dòng)態(tài)地裝入內(nèi)存，都需要解決地址變換問題。(5)頁(yè)面置換頁(yè)面置換n在動(dòng)態(tài)裝入一個(gè)頁(yè)面

16、時(shí)，若發(fā)現(xiàn)內(nèi)存當(dāng)前無(wú)空閑塊或分配給該進(jìn)程的物理塊已用完，則需要從已在內(nèi)存的若干頁(yè)面中選出一個(gè)將其淘汰，以釋放所占的物理塊。這時(shí)，需要考慮：具體在什么范圍內(nèi)選擇頁(yè)面？并采用何種算法來(lái)實(shí)現(xiàn)頁(yè)面的淘汰？這就需要設(shè)計(jì)出合適的頁(yè)面置換算法。(6)抖動(dòng)處理抖動(dòng)處理n請(qǐng)求分頁(yè)分配方式由于否定了程序裝入的一次性，程序可以在裝入一部分頁(yè)面后就開始運(yùn)行；這時(shí)，可能會(huì)遇到缺頁(yè)的問題。若缺頁(yè)過多，就會(huì)對(duì)系統(tǒng)的性能產(chǎn)生不好的影響。抖動(dòng)就是由缺頁(yè)過多導(dǎo)致的一種主要的不良后果，這時(shí)需要考慮系統(tǒng)應(yīng)該提供怎樣的抖動(dòng)處理方法？2022-3-31187.2.1請(qǐng)求分頁(yè)分配基本思想請(qǐng)求分頁(yè)分配基本思想n請(qǐng)求分頁(yè)分配管理需要用到頁(yè)表、

17、頁(yè)面分配策略、缺頁(yè)中斷、地址變換、抖動(dòng)處理等的支持。n這些管理手段之間的邏輯關(guān)聯(lián)是：n在為程序分配內(nèi)存時(shí)，需要用到頁(yè)面分配策略；n在程序裝入時(shí)，需要用到頁(yè)表和地址變換機(jī)制的支持；n在進(jìn)程運(yùn)行時(shí)，需要用到頁(yè)表、地址變換、缺頁(yè)中斷以及頁(yè)面置換的支持。n地址變換需要用到頁(yè)表；n頁(yè)面置換需要由缺頁(yè)中斷啟動(dòng)，并需要頁(yè)表和地址變換的支持。n頁(yè)面分配策略也與頁(yè)面置換相關(guān)；n系統(tǒng)出現(xiàn)的抖動(dòng)現(xiàn)象又與頁(yè)面分配策略和頁(yè)面置換等密切相關(guān)。 2022-3-31197.2.1請(qǐng)求分頁(yè)分配基本思想請(qǐng)求分頁(yè)分配基本思想為程序分配內(nèi)存階段程序裝入階段圖7.2 請(qǐng)求分頁(yè)分配管理的關(guān)鍵技術(shù)進(jìn)程運(yùn)行階段頁(yè)面分配策略頁(yè)表地址變換缺頁(yè)中

18、斷頁(yè)面置換抖動(dòng)2022-3-31207.2.2 請(qǐng)求分頁(yè)分配管理請(qǐng)求分頁(yè)分配管理 n請(qǐng)求分頁(yè)分配管理與分頁(yè)分配管理在管理手段上有相同之處，如同樣使用內(nèi)存空間使用表來(lái)描述內(nèi)存所有物理塊目前使用狀況，為內(nèi)存分配服務(wù)。我們?cè)谙旅嬷亟榻B需要專門設(shè)計(jì)的地方。由請(qǐng)求分頁(yè)存儲(chǔ)分配的思想可以看出，它是利用軟硬件相結(jié)合的方式來(lái)實(shí)現(xiàn)存儲(chǔ)管理的，因此協(xié)調(diào)好軟硬件之間的功能至關(guān)重要。為實(shí)現(xiàn)其存儲(chǔ)管理功能，系統(tǒng)必須提供必要的硬件支持；其中最重要的是頁(yè)表、缺頁(yè)中斷和地址變換機(jī)制。 2022-3-31217.2.2 請(qǐng)求分頁(yè)分配管理請(qǐng)求分頁(yè)分配管理（一）頁(yè)表機(jī)制n頁(yè)表是請(qǐng)求分頁(yè)分配管理中最重要的一種數(shù)據(jù)結(jié)構(gòu)，其作用是將程

19、序地址空間的邏輯地址轉(zhuǎn)換成內(nèi)存空間的物理地址。因?yàn)檎?qǐng)求分頁(yè)分配方式允許只將程序的一部分調(diào)入內(nèi)存，還有一部分放在外存磁盤空間上，所以在構(gòu)造請(qǐng)求分頁(yè)分配方式下的頁(yè)表時(shí)，需要在分頁(yè)分配方式的頁(yè)表的基礎(chǔ)上，增加一些字段。n在請(qǐng)求分頁(yè)分配管理中，頁(yè)表需要包括：頁(yè)號(hào)、中斷位、內(nèi)存塊號(hào)、外存地址、訪問位、修改位等字段，如圖7.3所示。圖7.3 請(qǐng)求分頁(yè)分配管理中的頁(yè)表結(jié)構(gòu)2022-3-31227.2.2 請(qǐng)求分頁(yè)分配管理請(qǐng)求分頁(yè)分配管理 n頁(yè)號(hào)和內(nèi)存塊號(hào)。定義同分頁(yè)存儲(chǔ)管理，這兩個(gè)字段為進(jìn)行地址變換提供必要的信息。n中斷位（駐留位、內(nèi)存標(biāo)志位）。用來(lái)表示該頁(yè)是在內(nèi)存還是在外存。當(dāng)需要訪問一個(gè)頁(yè)面時(shí)，根據(jù)該位

20、來(lái)判斷要訪問的頁(yè)面是否在內(nèi)存；若不在內(nèi)存則產(chǎn)生缺頁(yè)中斷。該位取值為0或1；例如，1表示該頁(yè)己在內(nèi)存；0表示該頁(yè)不在內(nèi)存。n外存地址。用來(lái)指明該頁(yè)在外存中的地址，供頁(yè)面調(diào)入和保存時(shí)使用，所以通常記錄的是外存物理塊號(hào)。n訪問位。用來(lái)記錄該頁(yè)面在一段時(shí)間內(nèi)被訪問的次數(shù)，或是最近已有多長(zhǎng)時(shí)間未被訪問。訪問位用來(lái)支持頁(yè)面置換算法，決定淘汰哪一頁(yè)。只要該頁(yè)中的任一指令或數(shù)據(jù)被訪問過一次，該位值就加l。一般情況下，為便于處理，該位也可用一位來(lái)表示。當(dāng)該位取值大于0表示該頁(yè)被訪問過；若該位取值為0，表示該頁(yè)未曾被訪問。n修改位。用于記錄該頁(yè)面在被調(diào)入內(nèi)存后是否被修改過。該位的值決定了在該頁(yè)面被置換時(shí)是否需要回

21、寫到外存。由于內(nèi)存中的頁(yè)面在外存上都有相應(yīng)的副本，因此，為減少磁盤寫的次數(shù)，若一個(gè)內(nèi)存頁(yè)面末被修改，則在該頁(yè)面被調(diào)出時(shí)就不需要將該頁(yè)面的內(nèi)容寫到外存；反之，若該頁(yè)面被修改，則必須將該頁(yè)面的當(dāng)前內(nèi)容重新寫到外存上，覆蓋外存對(duì)應(yīng)的物理塊，以完成最新內(nèi)容的保存。該位取值為0或1。2022-3-31237.2.2 請(qǐng)求分頁(yè)分配管理請(qǐng)求分頁(yè)分配管理（二）缺頁(yè)中斷機(jī)制 （1）缺頁(yè)中斷基本思想n在請(qǐng)求分頁(yè)存儲(chǔ)管理中，每當(dāng)所要訪問的頁(yè)面不在內(nèi)存，便要產(chǎn)生一個(gè)缺頁(yè)（Page Fault）中斷。操作系統(tǒng)接到此中斷信號(hào)后，就運(yùn)行缺頁(yè)中斷處理程序，根據(jù)頁(yè)表中給出的外存地址，將該頁(yè)調(diào)入內(nèi)存，使進(jìn)程繼續(xù)運(yùn)行下去。n缺頁(yè)中

22、斷是一個(gè)比較特殊的中斷。與一般的中斷相比，它同樣需要經(jīng)過保存CPU現(xiàn)場(chǎng)、轉(zhuǎn)缺頁(yè)中斷處理程序進(jìn)行處理、恢復(fù)CPU現(xiàn)場(chǎng)等幾個(gè)環(huán)節(jié)，但也體現(xiàn)出明顯的特殊之處。其特殊性主要體現(xiàn)在如下兩個(gè)方面：n它在指令的執(zhí)行期間就產(chǎn)生和處理中斷。n程序執(zhí)行過程中，一條指令的執(zhí)行可能產(chǎn)生多個(gè)缺頁(yè)中斷。例如，假設(shè)要執(zhí)行指令MOVE X TO Y，若指令本身跨了兩個(gè)頁(yè)面，X和Y又分別各是一個(gè)數(shù)據(jù)塊，其中X跨了兩個(gè)頁(yè)面，Y也跨了兩個(gè)頁(yè)面，這樣執(zhí)行該條指令則要產(chǎn)生6次缺頁(yè)中斷。如圖7.4所示。2022-3-31247.2.2 請(qǐng)求分頁(yè)分配管理請(qǐng)求分頁(yè)分配管理圖7.4 產(chǎn)生6次缺頁(yè)中斷的指令2022-3-31257.2.2 請(qǐng)求

23、分頁(yè)分配管理請(qǐng)求分頁(yè)分配管理（三）地址變換機(jī)制（三）地址變換機(jī)制 n請(qǐng)求分頁(yè)存儲(chǔ)管理的地址變換機(jī)制，是在分頁(yè)分配管理的地址變換機(jī)制基礎(chǔ)上，增加了實(shí)現(xiàn)虛擬存儲(chǔ)的缺頁(yè)中斷、頁(yè)面調(diào)入調(diào)出等功能而形成的。n假設(shè)地址變換機(jī)制中設(shè)置了快表，對(duì)給定的一個(gè)邏輯地址（頁(yè)號(hào)，頁(yè)內(nèi)偏移量），其地址變換過程為：n首先在快表中查找頁(yè)表。若在快表中找到所需要的頁(yè)表項(xiàng)時(shí)，就將快表中相應(yīng)的塊號(hào)與邏輯地址中的頁(yè)內(nèi)位移量拼接得到物理地址，并修改頁(yè)表項(xiàng)中訪問位的值，對(duì)于寫指令還要改變修改位的值。n如果快表中沒有所需的頁(yè)表項(xiàng)，則到內(nèi)存中去查找頁(yè)表。從對(duì)應(yīng)頁(yè)表項(xiàng)中的中斷位判斷該頁(yè)面是否已在內(nèi)存。如果該頁(yè)面在內(nèi)存中，此時(shí)需將此頁(yè)的頁(yè)表項(xiàng)

24、寫入快表，若快表已滿，應(yīng)按某種算法置換出快表中的某一頁(yè)表項(xiàng)，然后再將新頁(yè)表項(xiàng)寫入快表。同時(shí)形成物理地址（即用相應(yīng)的塊號(hào)與邏輯地址中的頁(yè)內(nèi)位移量拼接得到物理地址，并修改頁(yè)表項(xiàng)中訪問位的值，對(duì)于寫指令還要改變修改位的值）。n如果該頁(yè)面尚末調(diào)入內(nèi)存，產(chǎn)生缺頁(yè)中斷，然后將之從外存調(diào)入；如果內(nèi)存中沒有空閑塊，則由操作系統(tǒng)根據(jù)頁(yè)面置換算法淘汰某個(gè)頁(yè)面，然后再將該頁(yè)面調(diào)入。接著，修改頁(yè)表，將此頁(yè)的頁(yè)表項(xiàng)寫入快表。最后再形成物理地址。2022-3-31267.2.2 請(qǐng)求分頁(yè)分配管理請(qǐng)求分頁(yè)分配管理圖7.5 請(qǐng)求分頁(yè)存儲(chǔ)管理的地址變換過程2022-3-31277.2.4 頁(yè)面置換頁(yè)面置換 7.2.4.1 頁(yè)面

25、置換范圍頁(yè)面置換范圍（1）局部置換）局部置換n局部置換是指：當(dāng)一個(gè)進(jìn)程的運(yùn)行發(fā)生缺頁(yè)中斷時(shí)，操作系統(tǒng)只從該進(jìn)程在內(nèi)存的頁(yè)面中選擇出一個(gè)頁(yè)面進(jìn)行淘汰，釋放出對(duì)應(yīng)的物理塊，而不能用到別的進(jìn)程獲得的物理塊。即被置換的頁(yè)面只能是該進(jìn)程本身的頁(yè)面。（2）全局置換）全局置換n全局置換是指：當(dāng)一個(gè)進(jìn)程的運(yùn)行發(fā)生缺頁(yè)中斷時(shí)，操作系統(tǒng)可以從所有當(dāng)前位于內(nèi)存的頁(yè)面中選擇出一個(gè)頁(yè)面進(jìn)行淘汰，釋放出對(duì)應(yīng)的物理塊，而不管被選中的頁(yè)面是否屬于該進(jìn)程。即被置換的頁(yè)面可以是任何一個(gè)進(jìn)程的頁(yè)面。2022-3-31287.2.4 頁(yè)面置換頁(yè)面置換 7.2.4.2 典型頁(yè)面置換算法典型頁(yè)面置換算法 n頁(yè)面置換算法的作用是：在需要置

26、換頁(yè)面時(shí)，決定應(yīng)該置換出哪一個(gè)頁(yè)面，以保證進(jìn)程能正常運(yùn)行。n你會(huì)如何設(shè)計(jì)頁(yè)面置換算法？2022-3-31297.2.4 頁(yè)面置換頁(yè)面置換 （一）最佳置換算法（一）最佳置換算法（OPT）n最佳置換算法（OPT: Optimal），也叫理想淘汰算法、最佳頁(yè)面算法等，是由Belady于1966年提出的一種理想狀態(tài)下的頁(yè)面置換算法。其基本思想是：總選擇那些以后不再需要的或最遠(yuǎn)的將來(lái)才會(huì)用到的頁(yè)面進(jìn)行淘汰。n顯然，這種頁(yè)面置換算法的效果最好，缺頁(yè)率（即產(chǎn)生缺頁(yè)中斷的次數(shù)與訪問的頁(yè)面總數(shù)之比）也最低。但它需要事先精確地知道每一頁(yè)面的下次訪問時(shí)間，也就是說要求系統(tǒng)具有預(yù)測(cè)未來(lái)的能力，因此實(shí)際上是無(wú)法做到的，

27、僅具有理論上的意義。n但正因?yàn)樗男Ч抢碚撋献詈玫?，所以可將之作為其它置換算法的評(píng)價(jià)基準(zhǔn)；如果一個(gè)頁(yè)面置換算法的缺頁(yè)率與最佳置換算法的相近，則說明該算法選擇適當(dāng)。2022-3-31307.2.4 頁(yè)面置換頁(yè)面置換 n下面是一個(gè)采用最佳置換算法的例子。設(shè)一進(jìn)程的頁(yè)面訪問序列為：4、3、2、1、4、3、5、4、3、2、1、5，該進(jìn)程事先已經(jīng)分配到3個(gè)物理塊。進(jìn)程運(yùn)行時(shí)先將4、3、2前三個(gè)頁(yè)面裝入內(nèi)存。以后，訪問次數(shù)t=1時(shí)，進(jìn)程需要訪問頁(yè)面1，但它目前不在內(nèi)存，產(chǎn)生1次缺頁(yè)中斷。根據(jù)最佳置換算法，將頁(yè)面2淘汰；這是因?yàn)閷⒃诤荛L(zhǎng)時(shí)間內(nèi)用不到頁(yè)面2，而頁(yè)面4和頁(yè)面3會(huì)在緊接的訪問中被用到。依此類推，

28、完成所有的頁(yè)面置換，如表7.2所示（表中，“”表示產(chǎn)生了1次缺頁(yè)中斷）。進(jìn)程訪問所有頁(yè)面后，共產(chǎn)生了4次缺頁(yè)中斷，即缺頁(yè)率為4/9。表7.2 最佳置換算法訪問次數(shù)訪問次數(shù)t t123456789頁(yè)面訪問序列頁(yè)面訪問序列4 43 32 21 14 43 35 54 43 32 21 15 5物理塊物理塊1 1444444444222物理塊物理塊2 233333333311物理塊物理塊3 32111555555產(chǎn)生缺頁(yè)中斷產(chǎn)生缺頁(yè)中斷xxxxx2022-3-31317.2.4 頁(yè)面置換頁(yè)面置換 （二）先進(jìn)先出置換算法（二）先進(jìn)先出置換算法（FIFO） n先進(jìn)先出置換算法（FIFO: First I

29、n First Out）的基本思想是：總選擇進(jìn)入內(nèi)存時(shí)間最長(zhǎng)的頁(yè)面并淘汰之。這是最早出現(xiàn)的，可用于實(shí)際的置換算法。該算法在實(shí)現(xiàn)時(shí)，可以將所有頁(yè)面按照進(jìn)入內(nèi)存的次序排成一個(gè)隊(duì)列，并設(shè)置一個(gè)替換指針指向隊(duì)頭頁(yè)面；當(dāng)需要進(jìn)行頁(yè)面淘汰時(shí)，替換指針指向的即為當(dāng)前最先進(jìn)入內(nèi)存的頁(yè)面，該頁(yè)面被選中淘汰，然后修改指針。當(dāng)調(diào)入一個(gè)新頁(yè)面之后，將它排入隊(duì)尾。n在一定程度上，因?yàn)槌绦蚪Y(jié)構(gòu)的順序性，通常最早調(diào)入內(nèi)存的頁(yè)面以后不再被訪問的可能性最大，因此FIFO置換算法是有其合理性的；但實(shí)際情況并不完全如此。例如，經(jīng)常會(huì)出現(xiàn)某些頁(yè)面，由于含有全局變量、常用函數(shù)等程序段，它們?cè)谶M(jìn)程的整個(gè)生命周期中會(huì)被頻繁訪問；根據(jù)FIF

30、O置換算法，這些頁(yè)面會(huì)被反復(fù)調(diào)入、調(diào)出，這顯然是不合理的。2022-3-31327.2.4 頁(yè)面置換頁(yè)面置換 n仍用上面的頁(yè)面訪問序列，采用FIFO置換算法的頁(yè)面置換情況如表7.3所示。進(jìn)程訪問所有頁(yè)面后，共產(chǎn)生了6次缺頁(yè)中斷，即缺頁(yè)率為6/9。表7.3 先進(jìn)先出置換算法訪問次數(shù)訪問次數(shù)t t123456789頁(yè)面訪問序列頁(yè)面訪問序列4 43 32 21 14 43 35 54 43 32 21 15 5物理塊物理塊1 1444111555555物理塊物理塊2 233344444222物理塊物理塊3 32223333311產(chǎn)生缺頁(yè)中斷產(chǎn)生缺頁(yè)中斷xxx2022-3-31337.2.4 頁(yè)面置換

31、頁(yè)面置換 （三）最近最少使用置換算法（三）最近最少使用置換算法（LRU） （1）LRU置換算法的思想置換算法的思想n最近最少使用置換算法（LRU: Least Recently Used），也稱最近最久未使用算法，是最佳置換算法的一種近似算法。根據(jù)局部性原理，剛被訪問過的頁(yè)面，它馬上還要被訪問的可能性很大；反之，如果某一頁(yè)面在過去一段時(shí)間里不曾被訪問，則它在最近的將來(lái)一段時(shí)間內(nèi)被使用的可能性也不會(huì)大。這樣，就可以用“最近的過去”作為”最近的將來(lái)”的近似。nLRU算法的基本思想是：在產(chǎn)生缺頁(yè)時(shí)，總選擇距現(xiàn)在開始的過去最長(zhǎng)時(shí)間內(nèi)沒有被訪問過的頁(yè)面，并將其先調(diào)出。 2022-3-31347.2.4

32、頁(yè)面置換頁(yè)面置換 n仍用上面的頁(yè)面訪問序列例子，采用LRU置換算法得到的頁(yè)面置換情況如表7.5所示。進(jìn)程訪問所有頁(yè)面后，共產(chǎn)生了7次缺頁(yè)中斷，即缺頁(yè)率為7/9。表7.5 最近最少使用置換算法訪問次數(shù)t123456789頁(yè)面訪問序列4 43 32 21 14 43 35 54 43 32 21 15 5物理塊1444111555222物理塊233344444411物理塊32223333335產(chǎn)生缺頁(yè)中斷xx2022-3-31357.2.5 抖動(dòng)處理抖動(dòng)處理 n抖動(dòng)，又稱顛簸，是指由于系統(tǒng)缺頁(yè)過于頻繁而導(dǎo)致的一種反復(fù)調(diào)入調(diào)出頁(yè)面的現(xiàn)象。抖動(dòng)現(xiàn)象發(fā)生時(shí)，頁(yè)面在內(nèi)存與外存之間被頻繁地調(diào)入、調(diào)出；也就是

33、說，系統(tǒng)的大多數(shù)時(shí)間都在完成頁(yè)面的調(diào)入、調(diào)出，而真正用于進(jìn)程任務(wù)的時(shí)間相對(duì)過少。抖動(dòng)嚴(yán)重影響了系統(tǒng)的效率，甚至可能使系統(tǒng)全面崩潰，因此操作系統(tǒng)應(yīng)該具有相應(yīng)的處理功能。2022-3-31367.3 請(qǐng)求分段管理方式請(qǐng)求分段管理方式7.3.1請(qǐng)求分段分配基本思想請(qǐng)求分段分配基本思想7.3.2請(qǐng)求分段分配管理請(qǐng)求分段分配管理 2022-3-31377.3.1請(qǐng)求分段分配基本思想請(qǐng)求分段分配基本思想n請(qǐng)求分段管理方式是在分段管理方式的基礎(chǔ)上，增加了請(qǐng)求調(diào)段、分段置換等功能而形成的。請(qǐng)求分段分配方式的基本思想可描述為如下過程：n程序根據(jù)自身的邏輯結(jié)構(gòu)分為若干段，段有段號(hào)。內(nèi)存空間根據(jù)段來(lái)動(dòng)態(tài)劃分。n在進(jìn)

34、程開始執(zhí)行之前，允許只裝入若干段的用戶程序和數(shù)據(jù)，即可啟動(dòng)運(yùn)行。n在進(jìn)程運(yùn)行過程中，如果所訪問的段在內(nèi)存，則對(duì)其管理與分段存儲(chǔ)管理情形相同；若發(fā)現(xiàn)所要訪問的段不在內(nèi)存，便會(huì)產(chǎn)生缺段中斷，到外存找到該段并動(dòng)態(tài)地將其調(diào)入內(nèi)存中。在調(diào)入一個(gè)段時(shí)，先檢查內(nèi)存中是否有足夠的空閑空間，若有則直接將該段調(diào)入；否則，將內(nèi)存中的一些段淘汰，釋放所占內(nèi)存空間后將新的段裝入其中，進(jìn)程繼續(xù)運(yùn)行。被淘汰的內(nèi)存段若被修改過，須將修改的段寫入外存，以保留最新的內(nèi)容。系統(tǒng)反復(fù)進(jìn)行這樣的過程，直至進(jìn)程運(yùn)行結(jié)束。n請(qǐng)求分段分配方式在許多方面與分段分配方式是一致的；由于增加了虛擬存儲(chǔ)的實(shí)現(xiàn)，它比分段分配方式將更為復(fù)雜。但其虛擬存儲(chǔ)

35、的實(shí)現(xiàn)又類似于請(qǐng)求分頁(yè)管理，因此可以借鑒請(qǐng)求分頁(yè)管理技術(shù)來(lái)實(shí)現(xiàn)。2022-3-31387.3.1請(qǐng)求分段分配基本思想請(qǐng)求分段分配基本思想n實(shí)現(xiàn)請(qǐng)求分段分配方式需要專門解決的問題有：n請(qǐng)求分段的段表機(jī)制。需要提供一個(gè)段表機(jī)制來(lái)記錄任一段在內(nèi)存的位置、外存的位置、是否被修改等信息；這一段表比分段分配管理中的段表要復(fù)雜，需要重新設(shè)計(jì)。n缺段中斷。每當(dāng)下一步要訪問的段尚未被調(diào)入內(nèi)存時(shí)，便產(chǎn)生一個(gè)缺段中斷，以請(qǐng)求系統(tǒng)調(diào)入所缺的段。這時(shí)，缺段中斷該如何處理？n地址變換機(jī)制。用于實(shí)現(xiàn)請(qǐng)求分段管理方式下的從程序邏輯地址到內(nèi)存物理地址的轉(zhuǎn)換。 2022-3-31397.3.2請(qǐng)求分段分配管理請(qǐng)求分段分配管理（一）請(qǐng)求分段的段表機(jī)制（一）請(qǐng)求分段的段表機(jī)制n在請(qǐng)求分段分配管理中，以段為單位進(jìn)行內(nèi)存和外存之間的信息交換。相應(yīng)的段表機(jī)制以分段管理方式中的段表機(jī)制為基礎(chǔ)，增加若干字段來(lái)構(gòu)造；用于記錄一個(gè)程