第7章-虛擬內(nèi)存管理(ppt)課件

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

2、執(zhí)行，以后根據(jù)執(zhí)行的具體情況再依次請求裝入剩下的部分，直至整個(gè)程序都執(zhí)行完畢。這就從邏輯上擴(kuò)充了內(nèi)存容量，有效地解決了上述問題。本章介紹虛擬內(nèi)存管理的相關(guān)知識(shí)。首先介紹虛擬內(nèi)存管理的一些基本概念；然后分別闡述幾種典型的虛擬內(nèi)存管理方法：請求分頁管理方式、請求分段管理方式和請求段頁式管理方式。2022/7/2527.1虛擬存儲(chǔ)基本概念 7.2請求分頁管理方式7.3請求分段管理方式7.4請求段頁式管理方式2022/7/2537.1 虛擬存儲(chǔ)基本概念7.1.1虛擬存儲(chǔ)的引入 7.1.2虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù) 2022/7/2547.1.1虛擬存儲(chǔ)的引入 在上一章中，我們介紹的分配管理技術(shù)是針對實(shí)際物理內(nèi)存

3、空間的。這一類管理技術(shù)具有兩個(gè)特性：1）程序的裝入是一次性的。即在程序運(yùn)行之前，要求一次性地將程序所有內(nèi)容都裝入內(nèi)存，而不管程序的執(zhí)行目前是否需要這些全部內(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)存利用率和系統(tǒng)吞吐量。程序的一次性和駐留性是否可以否定？程序局部性原理回答了這一問題，它說明程序的一次性與駐留性都是不必要的；這樣就可以提出改進(jìn)的存儲(chǔ)管理技術(shù)，

4、即虛擬存儲(chǔ)。2022/7/2557.1.1虛擬存儲(chǔ)的引入（一）程序局部性原理 早在1968年，P.Denning就在長期的研究中發(fā)現(xiàn)了程序的局部性原理。它是指程序在執(zhí)行過程中的一個(gè)較短時(shí)間內(nèi)，所執(zhí)行的指令地址會(huì)較集中地出現(xiàn)在某一部分，呈現(xiàn)出程序局部性現(xiàn)象。2022/7/2567.1.1虛擬存儲(chǔ)的引入程序局部性現(xiàn)象說明：在一個(gè)較短的執(zhí)行時(shí)間間隔內(nèi)，程序只執(zhí)行程序的一部分，而不會(huì)執(zhí)行程序的全部內(nèi)容；同時(shí)，執(zhí)行訪問的存儲(chǔ)空間也局限于某一區(qū)域，而不會(huì)遍歷所有存儲(chǔ)空間。這就是程序局部性原理。程序局部性原理體現(xiàn)在時(shí)間局部性和空間局部性兩個(gè)方面：（1）時(shí)間局部性（2）空間局部性2022/7/2577.1.1

5、虛擬存儲(chǔ)的引入（1）時(shí)間局部性時(shí)間局部性是指程序中的一條指令執(zhí)行后可能會(huì)再次執(zhí)行，或某個(gè)數(shù)據(jù)被訪問后也可能再次被訪問。這主要是由程序中存在大量的循環(huán)操作導(dǎo)致的；（2）空間局部性空間局部性是指程序在一段時(shí)間內(nèi)所訪問的地址可能集中在定的范圍內(nèi)。這主要是由于程序中存在大量的順序執(zhí)行。程序局部性原理可以說明：程序的一次性與駐留性都是不必要的。2022/7/2587.1.1虛擬存儲(chǔ)的引入（二）虛擬存儲(chǔ)的基本思想因?yàn)閮?nèi)存空間的有限性，系統(tǒng)無法全部裝入比它大的程序并執(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ù)需

6、要裝入其它部分。程序運(yùn)行過程中暫不需要的部分程序也沒有必要始終駐留在內(nèi)存中，可以將它們移出到外存以釋放空間來裝入其它需要的程序部分。這樣，就可以將內(nèi)存和比內(nèi)存大的多的外存兩者結(jié)合起來使用，利用調(diào)入、調(diào)出等操作的支持，形成了一個(gè)比內(nèi)存空間大得多的、邏輯的虛擬內(nèi)存空間。這就是虛擬存儲(chǔ)器。總之，虛擬存儲(chǔ)是一種實(shí)現(xiàn)虛擬存儲(chǔ)器的技術(shù)。這一技術(shù)通過離散化存儲(chǔ)（以程序的子部分為單位分配和裝入內(nèi)存）、請求調(diào)入（即根據(jù)進(jìn)程執(zhí)行的需要來調(diào)入某些程序子部分）、置換（即將暫不需要的程序子部分調(diào)出到外存以釋放空間）等功能，來構(gòu)造一個(gè)比內(nèi)存空間大得多的、虛擬內(nèi)存空間；該空間的邏輯容量由外存和內(nèi)存容量之和決定，而運(yùn)行速度接

7、近于內(nèi)存速度，從而從邏輯上擴(kuò)充了內(nèi)存容量。2022/7/2597.1.1虛擬存儲(chǔ)的引入（三）虛擬存儲(chǔ)的特性 虛擬內(nèi)存管理技術(shù)是在內(nèi)存存儲(chǔ)管理技術(shù)的基礎(chǔ)上改進(jìn)得到的，它與上一章敘述的物理內(nèi)存存儲(chǔ)管理技術(shù)之間既有繼承，更體現(xiàn)出明顯的區(qū)別。從中可以看出虛擬存儲(chǔ)具有程序分配方式的非連續(xù)性、程序調(diào)入方式的多次性、程序駐留方式的交換性以及總體表現(xiàn)出的存儲(chǔ)管理虛擬性等特性。 表7.1 虛擬內(nèi)存存儲(chǔ)管理與物理內(nèi)存存儲(chǔ)管理的比較程序方式物理內(nèi)存存儲(chǔ)管理虛擬內(nèi)存存儲(chǔ)管理程序分配方式連續(xù)性非連續(xù)性程序駐留方式駐留性交換性程序調(diào)入方式一次性多次性2022/7/25107.1.2虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)虛擬存儲(chǔ)在實(shí)現(xiàn)時(shí)，首先需

8、要將程序邏輯地址空間離散化，即將程序劃分為若干子部分，并以程序的子部分為單位來分配內(nèi)存。因此，虛擬存儲(chǔ)的實(shí)現(xiàn)必須以非連續(xù)分配管理方式為基礎(chǔ)。具體而言，可以將程序劃分為頁、段或段頁結(jié)合，然后請求調(diào)入、置換等功能都將基于相應(yīng)的非連續(xù)分配管理方式來具體實(shí)現(xiàn)。至此，虛擬存儲(chǔ)器的實(shí)現(xiàn)技術(shù)可以分為三種：采用以分頁管理方式為基礎(chǔ)的請求分頁管理方式以分段管理方式為基礎(chǔ)的請求分段管理方式以段頁式管理方式為基礎(chǔ)的請求段頁式管理方式。 2022/7/25117.1.2虛擬存儲(chǔ)實(shí)現(xiàn)技術(shù)（一）請求分頁管理方式 請求分頁管理方式是在分頁管理方式的基礎(chǔ)上，增加了請求調(diào)頁、頁面置換等功能而形成的。它允許只裝入若干頁面的用戶程

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

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

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

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

13、的物理塊已用完，則從已在內(nèi)存的若干頁面中選出一個(gè)將其淘汰，釋放所占的物理塊后將新的頁面裝入其中，進(jìn)程繼續(xù)運(yùn)行。被淘汰的頁面如果剛才在內(nèi)存被修改過，還需要回寫到外存，以保留最新的內(nèi)容。系統(tǒng)反復(fù)進(jìn)行這樣的過程，直至進(jìn)程運(yùn)行結(jié)束。從上面的基本過程可以看出，請求分頁分配方式在許多方面與分頁分配方式是一致的；但由于允許程序裝入否定了一次性，這種方式顯得更加復(fù)雜。 2022/7/25167.2.1請求分頁分配基本思想（1）頁表需要提供一個(gè)頁表機(jī)制來記錄任一頁面在內(nèi)存的位置、外存的位置、是否被修改等信息；這一頁表比分頁分配管理中的頁表要復(fù)雜，需要重新設(shè)計(jì)。（2）頁面分配策略內(nèi)存中允許裝入多個(gè)進(jìn)程，每一進(jìn)程占

14、有一部分物理塊；問題是對這多個(gè)進(jìn)程，為每一進(jìn)程分配多少物理塊才合適？采用何種分配方式才更合理？即需要一個(gè)合適的頁面分配策略。(3)缺頁中斷進(jìn)程運(yùn)行若發(fā)現(xiàn)所要訪問的數(shù)據(jù)或指令不在內(nèi)存，便會(huì)產(chǎn)生缺頁中斷，到外存尋找包含所需數(shù)據(jù)或指令的頁面。這時(shí)，缺頁中斷該如何處理？2022/7/25177.2.1請求分頁分配基本思想(4)地址變換一個(gè)頁面不管是一開始就被裝入內(nèi)存，還是以后動(dòng)態(tài)地裝入內(nèi)存，都需要解決地址變換問題。(5)頁面置換在動(dòng)態(tài)裝入一個(gè)頁面時(shí)，若發(fā)現(xiàn)內(nèi)存當(dāng)前無空閑塊或分配給該進(jìn)程的物理塊已用完，則需要從已在內(nèi)存的若干頁面中選出一個(gè)將其淘汰，以釋放所占的物理塊。這時(shí)，需要考慮：具體在什么范圍內(nèi)選擇

15、頁面？并采用何種算法來實(shí)現(xiàn)頁面的淘汰？這就需要設(shè)計(jì)出合適的頁面置換算法。(6)抖動(dòng)處理請求分頁分配方式由于否定了程序裝入的一次性，程序可以在裝入一部分頁面后就開始運(yùn)行；這時(shí)，可能會(huì)遇到缺頁的問題。若缺頁過多，就會(huì)對系統(tǒng)的性能產(chǎn)生不好的影響。抖動(dòng)就是由缺頁過多導(dǎo)致的一種主要的不良后果，這時(shí)需要考慮系統(tǒng)應(yīng)該提供怎樣的抖動(dòng)處理方法？2022/7/25187.2.1請求分頁分配基本思想請求分頁分配管理需要用到頁表、頁面分配策略、缺頁中斷、地址變換、抖動(dòng)處理等的支持。這些管理手段之間的邏輯關(guān)聯(lián)是：在為程序分配內(nèi)存時(shí)，需要用到頁面分配策略；在程序裝入時(shí)，需要用到頁表和地址變換機(jī)制的支持；在進(jìn)程運(yùn)行時(shí)，需要

16、用到頁表、地址變換、缺頁中斷以及頁面置換的支持。地址變換需要用到頁表；頁面置換需要由缺頁中斷啟動(dòng)，并需要頁表和地址變換的支持。頁面分配策略也與頁面置換相關(guān)；系統(tǒng)出現(xiàn)的抖動(dòng)現(xiàn)象又與頁面分配策略和頁面置換等密切相關(guān)。 2022/7/25197.2.1請求分頁分配基本思想為程序分配內(nèi)存階段程序裝入階段圖7.2 請求分頁分配管理的關(guān)鍵技術(shù)進(jìn)程運(yùn)行階段頁面分配策略頁表地址變換缺頁中斷頁面置換抖動(dòng)2022/7/25207.2.2 請求分頁分配管理 請求分頁分配管理與分頁分配管理在管理手段上有相同之處，如同樣使用內(nèi)存空間使用表來描述內(nèi)存所有物理塊目前使用狀況，為內(nèi)存分配服務(wù)。我們在下面著重介紹需要專門設(shè)計(jì)的

17、地方。由請求分頁存儲(chǔ)分配的思想可以看出，它是利用軟硬件相結(jié)合的方式來實(shí)現(xiàn)存儲(chǔ)管理的，因此協(xié)調(diào)好軟硬件之間的功能至關(guān)重要。為實(shí)現(xiàn)其存儲(chǔ)管理功能，系統(tǒng)必須提供必要的硬件支持；其中最重要的是頁表、缺頁中斷和地址變換機(jī)制。 2022/7/25217.2.2 請求分頁分配管理（一）頁表機(jī)制頁表是請求分頁分配管理中最重要的一種數(shù)據(jù)結(jié)構(gòu)，其作用是將程序地址空間的邏輯地址轉(zhuǎn)換成內(nèi)存空間的物理地址。因?yàn)檎埱蠓猪摲峙浞绞皆试S只將程序的一部分調(diào)入內(nèi)存，還有一部分放在外存磁盤空間上，所以在構(gòu)造請求分頁分配方式下的頁表時(shí)，需要在分頁分配方式的頁表的基礎(chǔ)上，增加一些字段。在請求分頁分配管理中，頁表需要包括：頁號、中斷位、

18、內(nèi)存塊號、外存地址、訪問位、修改位等字段，如圖7.3所示。圖7.3 請求分頁分配管理中的頁表結(jié)構(gòu)2022/7/25227.2.2 請求分頁分配管理 頁號和內(nèi)存塊號。定義同分頁存儲(chǔ)管理，這兩個(gè)字段為進(jìn)行地址變換提供必要的信息。中斷位（駐留位、內(nèi)存標(biāo)志位）。用來表示該頁是在內(nèi)存還是在外存。當(dāng)需要訪問一個(gè)頁面時(shí)，根據(jù)該位來判斷要訪問的頁面是否在內(nèi)存；若不在內(nèi)存則產(chǎn)生缺頁中斷。該位取值為0或1；例如，1表示該頁己在內(nèi)存；0表示該頁不在內(nèi)存。外存地址。用來指明該頁在外存中的地址，供頁面調(diào)入和保存時(shí)使用，所以通常記錄的是外存物理塊號。訪問位。用來記錄該頁面在一段時(shí)間內(nèi)被訪問的次數(shù)，或是最近已有多長時(shí)間未被

19、訪問。訪問位用來支持頁面置換算法，決定淘汰哪一頁。只要該頁中的任一指令或數(shù)據(jù)被訪問過一次，該位值就加l。一般情況下，為便于處理，該位也可用一位來表示。當(dāng)該位取值大于0表示該頁被訪問過；若該位取值為0，表示該頁未曾被訪問。修改位。用于記錄該頁面在被調(diào)入內(nèi)存后是否被修改過。該位的值決定了在該頁面被置換時(shí)是否需要回寫到外存。由于內(nèi)存中的頁面在外存上都有相應(yīng)的副本，因此，為減少磁盤寫的次數(shù)，若一個(gè)內(nèi)存頁面末被修改，則在該頁面被調(diào)出時(shí)就不需要將該頁面的內(nèi)容寫到外存；反之，若該頁面被修改，則必須將該頁面的當(dāng)前內(nèi)容重新寫到外存上，覆蓋外存對應(yīng)的物理塊，以完成最新內(nèi)容的保存。該位取值為0或1。2022/7/2

20、5237.2.2 請求分頁分配管理（二）缺頁中斷機(jī)制 （1）缺頁中斷基本思想在請求分頁存儲(chǔ)管理中，每當(dāng)所要訪問的頁面不在內(nèi)存，便要產(chǎn)生一個(gè)缺頁（Page Fault）中斷。操作系統(tǒng)接到此中斷信號后，就運(yùn)行缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使進(jìn)程繼續(xù)運(yùn)行下去。缺頁中斷是一個(gè)比較特殊的中斷。與一般的中斷相比，它同樣需要經(jīng)過保存CPU現(xiàn)場、轉(zhuǎn)缺頁中斷處理程序進(jìn)行處理、恢復(fù)CPU現(xiàn)場等幾個(gè)環(huán)節(jié)，但也體現(xiàn)出明顯的特殊之處。其特殊性主要體現(xiàn)在如下兩個(gè)方面：它在指令的執(zhí)行期間就產(chǎn)生和處理中斷。程序執(zhí)行過程中，一條指令的執(zhí)行可能產(chǎn)生多個(gè)缺頁中斷。例如，假設(shè)要執(zhí)行指令MOVE X TO

21、 Y，若指令本身跨了兩個(gè)頁面，X和Y又分別各是一個(gè)數(shù)據(jù)塊，其中X跨了兩個(gè)頁面，Y也跨了兩個(gè)頁面，這樣執(zhí)行該條指令則要產(chǎn)生6次缺頁中斷。如圖7.4所示。2022/7/25247.2.2 請求分頁分配管理圖7.4 產(chǎn)生6次缺頁中斷的指令2022/7/25257.2.2 請求分頁分配管理（三）地址變換機(jī)制 請求分頁存儲(chǔ)管理的地址變換機(jī)制，是在分頁分配管理的地址變換機(jī)制基礎(chǔ)上，增加了實(shí)現(xiàn)虛擬存儲(chǔ)的缺頁中斷、頁面調(diào)入調(diào)出等功能而形成的。假設(shè)地址變換機(jī)制中設(shè)置了快表，對給定的一個(gè)邏輯地址（頁號，頁內(nèi)偏移量），其地址變換過程為：首先在快表中查找頁表。若在快表中找到所需要的頁表項(xiàng)時(shí)，就將快表中相應(yīng)的塊號與邏輯

22、地址中的頁內(nèi)位移量拼接得到物理地址，并修改頁表項(xiàng)中訪問位的值，對于寫指令還要改變修改位的值。如果快表中沒有所需的頁表項(xiàng)，則到內(nèi)存中去查找頁表。從對應(yīng)頁表項(xiàng)中的中斷位判斷該頁面是否已在內(nèi)存。如果該頁面在內(nèi)存中，此時(shí)需將此頁的頁表項(xiàng)寫入快表，若快表已滿，應(yīng)按某種算法置換出快表中的某一頁表項(xiàng)，然后再將新頁表項(xiàng)寫入快表。同時(shí)形成物理地址（即用相應(yīng)的塊號與邏輯地址中的頁內(nèi)位移量拼接得到物理地址，并修改頁表項(xiàng)中訪問位的值，對于寫指令還要改變修改位的值）。如果該頁面尚末調(diào)入內(nèi)存，產(chǎn)生缺頁中斷，然后將之從外存調(diào)入；如果內(nèi)存中沒有空閑塊，則由操作系統(tǒng)根據(jù)頁面置換算法淘汰某個(gè)頁面，然后再將該頁面調(diào)入。接著，修改頁

23、表，將此頁的頁表項(xiàng)寫入快表。最后再形成物理地址。2022/7/25267.2.2 請求分頁分配管理圖7.5 請求分頁存儲(chǔ)管理的地址變換過程2022/7/25277.2.4 頁面置換 7.2.4.1 頁面置換范圍（1）局部置換局部置換是指：當(dāng)一個(gè)進(jìn)程的運(yùn)行發(fā)生缺頁中斷時(shí)，操作系統(tǒng)只從該進(jìn)程在內(nèi)存的頁面中選擇出一個(gè)頁面進(jìn)行淘汰，釋放出對應(yīng)的物理塊，而不能用到別的進(jìn)程獲得的物理塊。即被置換的頁面只能是該進(jìn)程本身的頁面。（2）全局置換全局置換是指：當(dāng)一個(gè)進(jìn)程的運(yùn)行發(fā)生缺頁中斷時(shí)，操作系統(tǒng)可以從所有當(dāng)前位于內(nèi)存的頁面中選擇出一個(gè)頁面進(jìn)行淘汰，釋放出對應(yīng)的物理塊，而不管被選中的頁面是否屬于該進(jìn)程。即被置換

24、的頁面可以是任何一個(gè)進(jìn)程的頁面。2022/7/25287.2.4 頁面置換 7.2.4.2 典型頁面置換算法 頁面置換算法的作用是：在需要置換頁面時(shí)，決定應(yīng)該置換出哪一個(gè)頁面，以保證進(jìn)程能正常運(yùn)行。你會(huì)如何設(shè)計(jì)頁面置換算法？2022/7/25297.2.4 頁面置換 （一）最佳置換算法（OPT）最佳置換算法（OPT: Optimal），也叫理想淘汰算法、最佳頁面算法等，是由Belady于1966年提出的一種理想狀態(tài)下的頁面置換算法。其基本思想是：總選擇那些以后不再需要的或最遠(yuǎn)的將來才會(huì)用到的頁面進(jìn)行淘汰。顯然，這種頁面置換算法的效果最好，缺頁率（即產(chǎn)生缺頁中斷的次數(shù)與訪問的頁面總數(shù)之比）也最低

25、。但它需要事先精確地知道每一頁面的下次訪問時(shí)間，也就是說要求系統(tǒng)具有預(yù)測未來的能力，因此實(shí)際上是無法做到的，僅具有理論上的意義。但正因?yàn)樗男Ч抢碚撋献詈玫模钥蓪⒅鳛槠渌脫Q算法的評價(jià)基準(zhǔn)；如果一個(gè)頁面置換算法的缺頁率與最佳置換算法的相近，則說明該算法選擇適當(dāng)。2022/7/25307.2.4 頁面置換 下面是一個(gè)采用最佳置換算法的例子。設(shè)一進(jìn)程的頁面訪問序列為：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è)頁面裝入內(nèi)存。以后，訪問次數(shù)t=1時(shí)，進(jìn)程需要訪問頁面1，但它目前不在內(nèi)存，產(chǎn)生1次缺頁中斷。根據(jù)最佳置換算法，將頁

26、面2淘汰；這是因?yàn)閷⒃诤荛L時(shí)間內(nèi)用不到頁面2，而頁面4和頁面3會(huì)在緊接的訪問中被用到。依此類推，完成所有的頁面置換，如表7.2所示（表中，“”表示產(chǎn)生了1次缺頁中斷）。進(jìn)程訪問所有頁面后，共產(chǎn)生了4次缺頁中斷，即缺頁率為4/9。表7.2 最佳置換算法訪問次數(shù)t123456789頁面訪問序列432143543215物理塊1444444444222物理塊233333333311物理塊32111555555產(chǎn)生缺頁中斷xxxxx2022/7/25317.2.4 頁面置換 （二）先進(jìn)先出置換算法（FIFO） 先進(jìn)先出置換算法（FIFO: First In First Out）的基本思想是：總選擇進(jìn)入內(nèi)

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

28、理的。2022/7/25327.2.4 頁面置換 仍用上面的頁面訪問序列，采用FIFO置換算法的頁面置換情況如表7.3所示。進(jìn)程訪問所有頁面后，共產(chǎn)生了6次缺頁中斷，即缺頁率為6/9。表7.3 先進(jìn)先出置換算法訪問次數(shù)t123456789頁面訪問序列432143543215物理塊1444111555555物理塊233344444222物理塊32223333311產(chǎn)生缺頁中斷xxx2022/7/25337.2.4 頁面置換 （三）最近最少使用置換算法（LRU） （1）LRU置換算法的思想最近最少使用置換算法（LRU: Least Recently Used），也稱最近最久未使用算法，是最佳置換算

29、法的一種近似算法。根據(jù)局部性原理，剛被訪問過的頁面，它馬上還要被訪問的可能性很大；反之，如果某一頁面在過去一段時(shí)間里不曾被訪問，則它在最近的將來一段時(shí)間內(nèi)被使用的可能性也不會(huì)大。這樣，就可以用“最近的過去”作為”最近的將來”的近似。LRU算法的基本思想是：在產(chǎn)生缺頁時(shí)，總選擇距現(xiàn)在開始的過去最長時(shí)間內(nèi)沒有被訪問過的頁面，并將其先調(diào)出。 2022/7/25347.2.4 頁面置換 仍用上面的頁面訪問序列例子，采用LRU置換算法得到的頁面置換情況如表7.5所示。進(jìn)程訪問所有頁面后，共產(chǎn)生了7次缺頁中斷，即缺頁率為7/9。表7.5 最近最少使用置換算法訪問次數(shù)t123456789頁面訪問序列4321

30、43543215物理塊1444111555222物理塊233344444411物理塊32223333335產(chǎn)生缺頁中斷xx2022/7/25357.2.5 抖動(dòng)處理 抖動(dòng)，又稱顛簸，是指由于系統(tǒng)缺頁過于頻繁而導(dǎo)致的一種反復(fù)調(diào)入調(diào)出頁面的現(xiàn)象。抖動(dòng)現(xiàn)象發(fā)生時(shí)，頁面在內(nèi)存與外存之間被頻繁地調(diào)入、調(diào)出；也就是說，系統(tǒng)的大多數(shù)時(shí)間都在完成頁面的調(diào)入、調(diào)出，而真正用于進(jìn)程任務(wù)的時(shí)間相對過少。抖動(dòng)嚴(yán)重影響了系統(tǒng)的效率，甚至可能使系統(tǒng)全面崩潰，因此操作系統(tǒng)應(yīng)該具有相應(yīng)的處理功能。2022/7/25367.3 請求分段管理方式7.3.1請求分段分配基本思想7.3.2請求分段分配管理 2022/7/25377.

31、3.1請求分段分配基本思想請求分段管理方式是在分段管理方式的基礎(chǔ)上，增加了請求調(diào)段、分段置換等功能而形成的。請求分段分配方式的基本思想可描述為如下過程：程序根據(jù)自身的邏輯結(jié)構(gòu)分為若干段，段有段號。內(nèi)存空間根據(jù)段來動(dòng)態(tài)劃分。在進(jìn)程開始執(zhí)行之前，允許只裝入若干段的用戶程序和數(shù)據(jù)，即可啟動(dòng)運(yùn)行。在進(jìn)程運(yùn)行過程中，如果所訪問的段在內(nèi)存，則對其管理與分段存儲(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)行。被

32、淘汰的內(nèi)存段若被修改過，須將修改的段寫入外存，以保留最新的內(nèi)容。系統(tǒng)反復(fù)進(jìn)行這樣的過程，直至進(jìn)程運(yùn)行結(jié)束。請求分段分配方式在許多方面與分段分配方式是一致的；由于增加了虛擬存儲(chǔ)的實(shí)現(xiàn)，它比分段分配方式將更為復(fù)雜。但其虛擬存儲(chǔ)的實(shí)現(xiàn)又類似于請求分頁管理，因此可以借鑒請求分頁管理技術(shù)來實(shí)現(xiàn)。2022/7/25387.3.1請求分段分配基本思想實(shí)現(xiàn)請求分段分配方式需要專門解決的問題有：請求分段的段表機(jī)制。需要提供一個(gè)段表機(jī)制來記錄任一段在內(nèi)存的位置、外存的位置、是否被修改等信息；這一段表比分段分配管理中的段表要復(fù)雜，需要重新設(shè)計(jì)。缺段中斷。每當(dāng)下一步要訪問的段尚未被調(diào)入內(nèi)存時(shí)，便產(chǎn)生一個(gè)缺段中斷，以請求系統(tǒng)調(diào)入所缺的段。這時(shí)，缺段中斷該如何處理？地址變換機(jī)制。用于實(shí)現(xiàn)請求分段管理方式下的從程序邏輯地址到內(nèi)存物理地址的轉(zhuǎn)換。 2022/7/25397.3.2請求分段分配管理（一）請求分段的段表機(jī)制在請求分段分配管理中，以段為單位進(jìn)行內(nèi)存和外存之間的信息交換。相應(yīng)的段表機(jī)制以分段管理方式中的段表機(jī)制為基礎(chǔ)，增加若干字段來構(gòu)造；用于記錄一個(gè)程序的任一段在內(nèi)存的位置、外存的位置、存取方式、是否被修改等信息。請求分段的段表需要包括：段號、