第7章虛擬內存管理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、中斷頁面置換抖動2022-3-6.207.2.2 請求分頁分配管理請求分頁分配管理 n請求分頁分配管理與分頁分配管理在管理手段上有相同之處，如同樣使用內存空間使用表來描述內存所有物理塊目前使用狀況，為內存分配服務。我們在下面著重介紹需要專門設計的地方。由請求分頁存儲分配的思想可以看出，它是利用軟硬件相結合的方式來實現存儲管理的，因此協(xié)調好軟硬件之間的功能至關重要。為實現其存儲管理功能，系統(tǒng)必須提供必要的硬件支持；其中最重要的是頁表、缺頁中斷和地址變換機制。 2022-3-6.217.2.2 請求分頁分配管理請求分頁分配管理（一）頁表機制n頁表是請求分頁分配管理中最重要的一種數據結構，其作用是將

19、程序地址空間的邏輯地址轉換成內存空間的物理地址。因為請求分頁分配方式允許只將程序的一部分調入內存，還有一部分放在外存磁盤空間上，所以在構造請求分頁分配方式下的頁表時，需要在分頁分配方式的頁表的基礎上，增加一些字段。n在請求分頁分配管理中，頁表需要包括：頁號、中斷位、內存塊號、外存地址、訪問位、修改位等字段，如圖7.3所示。圖7.3 請求分頁分配管理中的頁表結構2022-3-6.227.2.2 請求分頁分配管理請求分頁分配管理 n頁號和內存塊號。定義同分頁存儲管理，這兩個字段為進行地址變換提供必要的信息。n中斷位（駐留位、內存標志位）。用來表示該頁是在內存還是在外存。當需要訪問一個頁面時，根據該

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

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

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

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

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

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

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

27、，僅具有理論上的意義。n但正因為它的效果是理論上最好的，所以可將之作為其它置換算法的評價基準；如果一個頁面置換算法的缺頁率與最佳置換算法的相近，則說明該算法選擇適當。2022-3-6.307.2.4 頁面置換頁面置換 n下面是一個采用最佳置換算法的例子。設一進程的頁面訪問序列為：4、3、2、1、4、3、5、4、3、2、1、5，該進程事先已經分配到3個物理塊。進程運行時先將4、3、2前三個頁面裝入內存。以后，訪問次數t=1時，進程需要訪問頁面1，但它目前不在內存，產生1次缺頁中斷。根據最佳置換算法，將頁面2淘汰；這是因為將在很長時間內用不到頁面2，而頁面4和頁面3會在緊接的訪問中被用到。依此類推

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

29、In First Out）的基本思想是：總選擇進入內存時間最長的頁面并淘汰之。這是最早出現的，可用于實際的置換算法。該算法在實現時，可以將所有頁面按照進入內存的次序排成一個隊列，并設置一個替換指針指向隊頭頁面；當需要進行頁面淘汰時，替換指針指向的即為當前最先進入內存的頁面，該頁面被選中淘汰，然后修改指針。當調入一個新頁面之后，將它排入隊尾。n在一定程度上，因為程序結構的順序性，通常最早調入內存的頁面以后不再被訪問的可能性最大，因此FIFO置換算法是有其合理性的；但實際情況并不完全如此。例如，經常會出現某些頁面，由于含有全局變量、常用函數等程序段，它們在進程的整個生命周期中會被頻繁訪問；根據FI

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

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

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

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

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

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