第六章 虛擬存儲器管理

1、1重點回顧重點回顧v分段：在分段存儲管理方式中，作業(yè)的地址空間分段：在分段存儲管理方式中，作業(yè)的地址空間按照用戶編程時劃分的自然段被分為若干部分。按照用戶編程時劃分的自然段被分為若干部分。每個段定義了一組邏輯信息，有自己的段名。每個段定義了一組邏輯信息，有自己的段名。v進程各段在內存中可以不連續(xù)存放，但每段要求進程各段在內存中可以不連續(xù)存放，但每段要求在內存中連續(xù)存放。內存中各段的長度由用戶程在內存中連續(xù)存放。內存中各段的長度由用戶程序中的段長決定，因此各段長度不等。序中的段長決定，因此各段長度不等。v段表段表v基本分段地址變換機構基本分段地址變換機構2重點回顧重點回顧3重點回顧重點回顧分段與

2、分頁系統(tǒng)中的段與頁的區(qū)別如下分段與分頁系統(tǒng)中的段與頁的區(qū)別如下：v段是信息的邏輯單位段是信息的邏輯單位，它是根據(jù)用戶的需要劃，它是根據(jù)用戶的需要劃分的；分的；頁是信息的物理單位頁是信息的物理單位，是為了管理主存，是為了管理主存的方便而劃分的。的方便而劃分的。v頁的頁的大小固定大小固定不變，由不變，由系統(tǒng)系統(tǒng)決定。段的決定。段的大小是大小是不固定不固定的，它由的，它由用戶用戶完成的功能決定。完成的功能決定。v通常段比頁大，因而段表比頁表短，可以縮短通常段比頁大，因而段表比頁表短，可以縮短查找時間，提高訪問速度。查找時間，提高訪問速度。v邏輯地址表示：邏輯地址表示：分頁是一維的分頁是一維的，各個模

3、塊在鏈接時必須組織成同一個，各個模塊在鏈接時必須組織成同一個地址空間；地址空間；(1)(1) 分段是二維的分段是二維的，各個模塊在鏈接時可以每個段組織成，各個模塊在鏈接時可以每個段組織成一個地址空間。一個地址空間。4重點回顧重點回顧v基本段頁式存儲管理方式基本段頁式存儲管理方式 每個作業(yè)仍按邏輯分段，但對每一段不是按單每個作業(yè)仍按邏輯分段，但對每一段不是按單一的連續(xù)整體存放到存儲器中，而是一的連續(xù)整體存放到存儲器中，而是把每個段把每個段再分成若干個頁面再分成若干個頁面，每一段不必占據(jù)連續(xù)的主，每一段不必占據(jù)連續(xù)的主存空間，可把它按頁存放在不連續(xù)的主存塊中存空間，可把它按頁存放在不連續(xù)的主存塊中

4、。 地址變換如下：地址變換如下：5段表地址寄存器段表地址寄存器段表長度段表長度 起始地址起始地址s p d 虛擬地址虛擬地址物理地址物理地址pP+ds p p 聯(lián)想存儲器聯(lián)想存儲器 段表段表 頁面頁面S S段的頁表段的頁表重點回顧重點回顧67本章內容本章內容6.1 覆蓋與交換技術覆蓋與交換技術6.2 虛擬存儲管理虛擬存儲管理6.3 請求分頁存儲管理方式請求分頁存儲管理方式6.4 請求分段存儲管理方式請求分段存儲管理方式 6.5 請求段頁存儲管理方式請求段頁存儲管理方式6.6 存儲管理方案總結存儲管理方案總結86.1 覆蓋與交換技術覆蓋與交換技術6.1.1 覆蓋技術覆蓋技術v覆蓋技術是指程序運行

5、過程中，把同一存儲區(qū)在不同覆蓋技術是指程序運行過程中，把同一存儲區(qū)在不同時刻分配給不同程序段或數(shù)據(jù)段，它是實現(xiàn)存儲區(qū)共時刻分配給不同程序段或數(shù)據(jù)段，它是實現(xiàn)存儲區(qū)共享的一種內存分配技術。可相互覆蓋的程序段叫覆蓋享的一種內存分配技術。可相互覆蓋的程序段叫覆蓋段，可進行覆蓋操作的內存區(qū)域叫做覆蓋區(qū)。段，可進行覆蓋操作的內存區(qū)域叫做覆蓋區(qū)。v覆蓋段不能超過已有內存空間大小，每個覆蓋段分先覆蓋段不能超過已有內存空間大小，每個覆蓋段分先后順序進入系統(tǒng)分配的內存空間，后進入內存空間的后順序進入系統(tǒng)分配的內存空間，后進入內存空間的段將先進入內存空間的段覆蓋。段將先進入內存空間的段覆蓋。v采用覆蓋技術后，系統(tǒng)

6、可運行比現(xiàn)有內存空間大的進采用覆蓋技術后，系統(tǒng)可運行比現(xiàn)有內存空間大的進程。程。96.1 覆蓋與交換技術覆蓋與交換技術106.1 覆蓋與交換技術覆蓋與交換技術v覆蓋技術要求操作員對作業(yè)有全面的了解，以便為系覆蓋技術要求操作員對作業(yè)有全面的了解，以便為系統(tǒng)提供一個清晰的覆蓋結構。統(tǒng)提供一個清晰的覆蓋結構。v由于覆蓋的劃分依據(jù)主要來自各程序段之間的調用關由于覆蓋的劃分依據(jù)主要來自各程序段之間的調用關系，因此，一個進程究竟劃分為多少段，其中哪些程系，因此，一個進程究竟劃分為多少段，其中哪些程序段可以共享同序段可以共享同塊存儲區(qū)，只有程序設計人員最清塊存儲區(qū)，只有程序設計人員最清楚。如果操作員不是程序

7、員，那么覆蓋技術就難以實楚。如果操作員不是程序員，那么覆蓋技術就難以實現(xiàn)。現(xiàn)。v覆蓋技術主要應用于系統(tǒng)程序，很少應用于用戶程覆蓋技術主要應用于系統(tǒng)程序，很少應用于用戶程序序 。116.1 覆蓋與交換技術覆蓋與交換技術6.1.2 交換技術交換技術v交換技術是系統(tǒng)根據(jù)需要把內存中暫時不能運行的進交換技術是系統(tǒng)根據(jù)需要把內存中暫時不能運行的進程或暫時不用的部分程序和數(shù)據(jù)移到外存，以便騰出程或暫時不用的部分程序和數(shù)據(jù)移到外存，以便騰出足夠的內存空間，把外存中已具備運行條件的進程或足夠的內存空間，把外存中已具備運行條件的進程或部分程序和數(shù)據(jù)換入，使其運行。交換是提高內存利部分程序和數(shù)據(jù)換入，使其運行。交

8、換是提高內存利用率的一種有效措施。用率的一種有效措施。v為了實現(xiàn)交換技術，系統(tǒng)必須能實現(xiàn)兩方面的功能：為了實現(xiàn)交換技術，系統(tǒng)必須能實現(xiàn)兩方面的功能：對換空間的管理、進程的換出與換入。對換空間的管理、進程的換出與換入。126.1 覆蓋與交換技術覆蓋與交換技術1.交換空間的管理交換空間的管理v在具有對換功能的操作系統(tǒng)中，通常把外存分為文件在具有對換功能的操作系統(tǒng)中，通常把外存分為文件區(qū)和對換區(qū)。前者用于存放文件，后者用于存放從內區(qū)和對換區(qū)。前者用于存放文件，后者用于存放從內存換出的進程。系統(tǒng)對文件區(qū)一般采取離散分配方式。存換出的進程。系統(tǒng)對文件區(qū)一般采取離散分配方式。進程在對換區(qū)中駐留的時間是短暫

9、的，頻繁進行對換進程在對換區(qū)中駐留的時間是短暫的，頻繁進行對換操作，故對對換空間管理的主要目標是提高進程的對操作，故對對換空間管理的主要目標是提高進程的對換速度。換速度。v為了能對對換區(qū)中的空閑盤塊進行管理，系統(tǒng)應配置為了能對對換區(qū)中的空閑盤塊進行管理，系統(tǒng)應配置相應的數(shù)據(jù)結構來記錄外存的使用情況。其與內存動相應的數(shù)據(jù)結構來記錄外存的使用情況。其與內存動態(tài)分區(qū)分配方式中所用數(shù)據(jù)結構相似，常采用空閑分態(tài)分區(qū)分配方式中所用數(shù)據(jù)結構相似，常采用空閑分區(qū)表或空閑分區(qū)鏈。區(qū)表或空閑分區(qū)鏈。136.1 覆蓋與交換技術覆蓋與交換技術2.進程的換出與換入進程的換出與換入v 每當一進程由于創(chuàng)建子進程而需要更多的

10、內存空間時，如每當一進程由于創(chuàng)建子進程而需要更多的內存空間時，如此時系統(tǒng)無足夠的空閑內存空間供該進程使用，系統(tǒng)可將此時系統(tǒng)無足夠的空閑內存空間供該進程使用，系統(tǒng)可將某進程暫時換出。其過程是系統(tǒng)首先選擇處于阻塞狀態(tài)且某進程暫時換出。其過程是系統(tǒng)首先選擇處于阻塞狀態(tài)且優(yōu)先級最低的進程作為換出進程，然后啟動磁盤，將該進優(yōu)先級最低的進程作為換出進程，然后啟動磁盤，將該進程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送過程未出程的程序和數(shù)據(jù)傳送到磁盤的對換區(qū)上。若傳送過程未出現(xiàn)錯誤，便可回收該進程所占用的內存空間，并對該進程現(xiàn)錯誤，便可回收該進程所占用的內存空間，并對該進程的進程控制塊做相應的修改。的進程控制

11、塊做相應的修改。v 換出的進程最終還要被換入內存。操作系統(tǒng)應定時查看系換出的進程最終還要被換入內存。操作系統(tǒng)應定時查看系統(tǒng)內所有進程狀態(tài)，在系統(tǒng)允許的條件下，從磁盤中找出統(tǒng)內所有進程狀態(tài)，在系統(tǒng)允許的條件下，從磁盤中找出處于就緒狀態(tài)且換出時間最久的進程，把它從磁盤換入內處于就緒狀態(tài)且換出時間最久的進程，把它從磁盤換入內存，供調度程序調度執(zhí)行。存，供調度程序調度執(zhí)行。146.2 虛擬存儲管理虛擬存儲管理6.2.1 程序局部性原理程序局部性原理 1. 程序局部性原理程序局部性原理v程序局部性原理是指程序在執(zhí)行時將呈現(xiàn)出局部性程序局部性原理是指程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，即在一較短的時間內，程序

12、的執(zhí)行僅局限于規(guī)律，即在一較短的時間內，程序的執(zhí)行僅局限于某個部分；相應地，它所訪問的存儲空間也局限于某個部分；相應地，它所訪問的存儲空間也局限于某個區(qū)域。某個區(qū)域。156.2.1 程序局部性原理程序局部性原理v局限性還表現(xiàn)在下述兩個方面：局限性還表現(xiàn)在下述兩個方面：(1) (1) 時間局限性。如果程序中的某條指令一旦執(zhí)行，時間局限性。如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過，則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時問過，則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時間局限性的典型原因是由于在程序中存在著大量的間局限性的典

13、型原因是由于在程序中存在著大量的循環(huán)操作循環(huán)操作。(2) (2) 空間局限性。一旦程序訪問了某個存儲單元，在空間局限性。一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內所訪問的地址，可能集中在一定的范在一段時間內所訪問的地址，可能集中在一定的范圍之內，其典型情況便是程序的圍之內，其典型情況便是程序的順序執(zhí)行順序執(zhí)行。166.2.1 程序局部性原理程序局部性原理2. 虛擬存儲器的引入虛擬存儲器的引入v虛擬存儲器中存儲的進程執(zhí)行時并不把其全部內容虛擬存儲器中存儲的進程執(zhí)行時并不把其全部內容裝入內存，而只將其中一部分先

14、裝入內存。進程執(zhí)裝入內存，而只將其中一部分先裝入內存。進程執(zhí)行過程中用到那些不在內存中的信息時，再把它們行過程中用到那些不在內存中的信息時，再把它們換入內存。換入內存。v虛擬存儲器容量虛擬存儲器容量=物理內存容量物理內存容量+輔存中用于虛存輔存中用于虛存的容量的容量176.2.1 程序局部性原理程序局部性原理2. 虛擬存儲器的引入虛擬存儲器的引入186.2.2 虛擬虛擬存儲器及其特征存儲器及其特征1. 虛擬存儲器的定義虛擬存儲器的定義v虛擬存儲器的基本思想是：虛擬存儲器的基本思想是： 應用程序在運行之前僅將那些當前要運行的少數(shù)頁面或段應用程序在運行之前僅將那些當前要運行的少數(shù)頁面或段先裝入內存

15、便可運行，其余部分放在磁盤上。程序在運行先裝入內存便可運行，其余部分放在磁盤上。程序在運行時，如果它所要訪問的頁（段）已調入內存，便可繼續(xù)執(zhí)時，如果它所要訪問的頁（段）已調入內存，便可繼續(xù)執(zhí)行下去；行下去； 但如果程序所要訪問的頁（段）尚未調入內存（稱為缺頁但如果程序所要訪問的頁（段）尚未調入內存（稱為缺頁或缺段），此時程序應利用操作系統(tǒng)提供的請求調頁（段或缺段），此時程序應利用操作系統(tǒng)提供的請求調頁（段）功能，將它們調入內存，以使進程能繼續(xù)執(zhí)行下去。）功能，將它們調入內存，以使進程能繼續(xù)執(zhí)行下去。 如果此時內存已滿，無法再裝入新的頁（段），則還須再如果此時內存已滿，無法再裝入新的頁（段），則

16、還須再利用頁（段）的置換功能，將內存中暫時不用的頁（段）利用頁（段）的置換功能，將內存中暫時不用的頁（段）調至磁盤上，在騰出足夠內存空間后，將要訪問的頁（段調至磁盤上，在騰出足夠內存空間后，將要訪問的頁（段）調入內存，使程序繼續(xù)執(zhí)行。）調入內存，使程序繼續(xù)執(zhí)行。196.2.2 虛擬虛擬存儲器及其特征存儲器及其特征2. 虛擬存儲器的特征虛擬存儲器的特征 多次性：一個作業(yè)被分成多次調入內存運行。多多次性：一個作業(yè)被分成多次調入內存運行。多次性是虛擬存儲器最重要的特征，與常規(guī)存儲器管次性是虛擬存儲器最重要的特征，與常規(guī)存儲器管理的一次性相對應。理的一次性相對應。 對換性：系統(tǒng)允許作業(yè)在運行過程中進行

17、換進、對換性：系統(tǒng)允許作業(yè)在運行過程中進行換進、換出操作。換進和換出能有效地提高內存利用率。換出操作。換進和換出能有效地提高內存利用率。 虛擬性：虛擬性是指從邏輯上擴充內存容量，并虛擬性：虛擬性是指從邏輯上擴充內存容量，并非實際存在。用戶感覺到的很大的虛擬存儲容量實非實際存在。用戶感覺到的很大的虛擬存儲容量實際上是一種際上是一種“假象假象”206.3 請求分頁存儲管理方式請求分頁存儲管理方式v在分頁系統(tǒng)的基礎上，增加了請求調頁功能和頁在分頁系統(tǒng)的基礎上，增加了請求調頁功能和頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。面置換功能所形成的頁式虛擬存儲系統(tǒng)。v它允許只裝入它允許只裝入少數(shù)頁面少數(shù)頁面的程序

18、的程序( (及數(shù)據(jù)及數(shù)據(jù)) )，便啟動，便啟動運行。以后，再通過調頁功能及頁面置換功能，運行。以后，再通過調頁功能及頁面置換功能，陸續(xù)地把即將要運行的頁面調入內存，同時把暫陸續(xù)地把即將要運行的頁面調入內存，同時把暫不運行的頁面換出到外存上。不運行的頁面換出到外存上。v置換時以置換時以頁面為單位頁面為單位。為了能實現(xiàn)請求調頁和置。為了能實現(xiàn)請求調頁和置換功能，系統(tǒng)必須提供必要的硬件支持和相應的換功能，系統(tǒng)必須提供必要的硬件支持和相應的軟件。軟件。216.3 請求分頁存儲管理方式請求分頁存儲管理方式6.3.1 請求分頁中的硬件支持請求分頁中的硬件支持 1. 頁表頁表v 在請求分頁系統(tǒng)中所需要的主要

19、數(shù)據(jù)結構是頁表。其基本在請求分頁系統(tǒng)中所需要的主要數(shù)據(jù)結構是頁表。其基本作用仍然是將用戶地址空間中的邏輯地址變換為內存空間作用仍然是將用戶地址空間中的邏輯地址變換為內存空間中的物理地址。中的物理地址。v 由于只將應用程序的一部分調入內存，還有一部分仍在盤由于只將應用程序的一部分調入內存，還有一部分仍在盤上，故需在頁表中再增加若干項，供程序上，故需在頁表中再增加若干項，供程序( (數(shù)據(jù)數(shù)據(jù)) )在換進、在換進、換出時參考。換出時參考。v 在請求分頁系統(tǒng)中的每個頁表項如下所示：在請求分頁系統(tǒng)中的每個頁表項如下所示：221頁表頁表(1) 狀態(tài)位狀態(tài)位P：用于指示該頁是否已調入內存，供：用于指示該頁是

20、否已調入內存，供程序訪問時程序訪問時參考。參考。(2) 訪問字段訪問字段A：用于記錄本頁在一段時間內被：用于記錄本頁在一段時間內被訪問的次數(shù)，或記錄本頁最近已有多長時間未訪問的次數(shù)，或記錄本頁最近已有多長時間未被訪問，供被訪問，供選擇換出頁面選擇換出頁面時參考。時參考。(3) 修改位修改位M：表示該頁在調入內存后是否被修：表示該頁在調入內存后是否被修改過。改過。M位供位供置換頁面置換頁面時參考。時參考。(4) 外存地址：用于指出該頁在外存上的地址，外存地址：用于指出該頁在外存上的地址，通常是物理塊號，供通常是物理塊號，供調入該頁調入該頁時參考。時參考。 23v請求分頁系統(tǒng)中的地址變換機構，是在

21、分頁請求分頁系統(tǒng)中的地址變換機構，是在分頁系統(tǒng)的地址變換機構的基礎上，再為實現(xiàn)虛系統(tǒng)的地址變換機構的基礎上，再為實現(xiàn)虛擬存儲器而增加了某些功能所形成的，如產(chǎn)擬存儲器而增加了某些功能所形成的，如產(chǎn)生和處理缺頁中斷，以及從內存中換出一頁生和處理缺頁中斷，以及從內存中換出一頁的功能等等。的功能等等。v下圖示出了請求分頁系統(tǒng)中的地址變換過程下圖示出了請求分頁系統(tǒng)中的地址變換過程。2地址變換機構地址變換機構24 將一頁從外存換入內存將一頁從外存換入內存 修改頁表修改頁表 否否從外存中找到缺頁從外存中找到缺頁 內存滿否？內存滿否？ 該頁是否被修改？該頁是否被修改？CPU從外存讀缺頁從外存讀缺頁 啟動啟動I

22、/O硬件硬件 修改訪問位和修改位修改訪問位和修改位形成物理地址形成物理地址 地址變換結束地址變換結束開始（程序請求訪問一頁開始（程序請求訪問一頁)頁表項是否在快表中？頁表項是否在快表中？頁是否在內存中？頁是否在內存中？否，產(chǎn)生缺頁否，產(chǎn)生缺頁中斷請求調頁中斷請求調頁保留保留CPU現(xiàn)場現(xiàn)場 缺頁中斷處理缺頁中斷處理越界中斷越界中斷是是是是修改快表修改快表是是選擇一頁換出選擇一頁換出 是是 將該頁寫回外存將該頁寫回外存 是是CPU檢索快表檢索快表否否訪問頁表訪問頁表否否否否頁號頁號頁表長度？頁表長度？圖圖 請求分頁中的地址變換過程請求分頁中的地址變換過程 25v在請求分頁系統(tǒng)中，由在請求分頁系統(tǒng)中

23、，由CPU的地址變換機構根據(jù)頁的地址變換機構根據(jù)頁表中的狀態(tài)位判斷是否產(chǎn)生缺頁中斷（表中的狀態(tài)位判斷是否產(chǎn)生缺頁中斷（page fault），請求，請求OS將所缺頁調入內存。與一般中斷的主要區(qū)將所缺頁調入內存。與一般中斷的主要區(qū)別在于：別在于：v缺頁中斷在缺頁中斷在指令執(zhí)行期間指令執(zhí)行期間產(chǎn)生和處理中斷信號，而產(chǎn)生和處理中斷信號，而一般中斷在一條一般中斷在一條指令執(zhí)行完指令執(zhí)行完后檢查和處理中斷信號后檢查和處理中斷信號。v缺頁中斷缺頁中斷返回到該指令的開始返回到該指令的開始重新執(zhí)行該指令，而重新執(zhí)行該指令，而一般中斷返回到該指令的一般中斷返回到該指令的下一條指令下一條指令執(zhí)行。執(zhí)行。3缺頁中斷

24、機構缺頁中斷機構26XX+1SWAP A,BYY+1AZZ+1B一條指令在執(zhí)行期間，一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷?？赡墚a(chǎn)生多次缺頁中斷。如：如：swap A,B，指令本，指令本身和兩個操作數(shù)都跨越相身和兩個操作數(shù)都跨越相鄰外存頁的分界處，則產(chǎn)鄰外存頁的分界處，則產(chǎn)生生5次中斷。次中斷。276.3.2 請求分頁中的請求分頁中的軟件支持軟件支持1. 物理塊分配算法物理塊分配算法v在采用固定分配策略時，可采用以下幾種物在采用固定分配策略時，可采用以下幾種物理塊分配方法。理塊分配方法。 平均分配算法平均分配算法 按比例分配算法按比例分配算法 考慮優(yōu)先權的分配算法考慮優(yōu)先權的分配算法 286

25、.3.2 請求分頁中的請求分頁中的軟件支持軟件支持2. 最小物理塊數(shù)的確定最小物理塊數(shù)的確定v實踐證明，進程占用的存儲容量越小，缺頁實踐證明，進程占用的存儲容量越小，缺頁率就越大。在為進程分配物理塊時，首先應率就越大。在為進程分配物理塊時，首先應該考慮的問題是保證進程正常運行所需的最該考慮的問題是保證進程正常運行所需的最少物理塊數(shù)（稱為最小物理塊數(shù)）。少物理塊數(shù)（稱為最小物理塊數(shù)）。v若系統(tǒng)為某進程所分配的物理塊數(shù)少于此值若系統(tǒng)為某進程所分配的物理塊數(shù)少于此值時，進程將無法運行，這主要取決于系統(tǒng)中時，進程將無法運行，這主要取決于系統(tǒng)中的指令格式和尋址方式法。的指令格式和尋址方式法。296.3.

26、2 請求分頁中的請求分頁中的軟件支持軟件支持3. 對換區(qū)管理對換區(qū)管理v在虛擬存儲系統(tǒng)中，將外存分為文件區(qū)和對換區(qū)。在虛擬存儲系統(tǒng)中，將外存分為文件區(qū)和對換區(qū)。文件區(qū)存放用戶文件；對換區(qū)存放換入換出的頁面文件區(qū)存放用戶文件；對換區(qū)存放換入換出的頁面或段。為了提高換入換出的速度，對換區(qū)常采用連或段。為了提高換入換出的速度，對換區(qū)常采用連續(xù)分配方式。續(xù)分配方式。v如果被淘汰的頁面或段在執(zhí)行期間沒有被修改過，如果被淘汰的頁面或段在執(zhí)行期間沒有被修改過，則不必回寫外存，因為外存的可執(zhí)行文件中存有它則不必回寫外存，因為外存的可執(zhí)行文件中存有它的磁盤正本；如果被淘汰頁面已被修改過，則將其的磁盤正本；如果被

27、淘汰頁面已被修改過，則將其回寫到外存的對換區(qū)中?；貙懙酵獯娴膶Q區(qū)中。306.3.3 頁面置換算法頁面置換算法為了衡量一個調度算法的優(yōu)劣，先介紹幾個概念。為了衡量一個調度算法的優(yōu)劣，先介紹幾個概念。v為了簡單起見，假定一個作業(yè)分配的主存塊數(shù)固定不變?yōu)榱撕唵纹鹨?，假定一個作業(yè)分配的主存塊數(shù)固定不變，且采用局部淘汰，且采用局部淘汰(淘汰一頁時，只考慮本作業(yè)內部實淘汰一頁時，只考慮本作業(yè)內部實施淘汰施淘汰)。v假定作業(yè)假定作業(yè)Ji共有共有m頁，系統(tǒng)分配給它的主存塊為頁，系統(tǒng)分配給它的主存塊為n塊，這塊，這里里mn。開始時，主存沒有裝入任何一頁的信息。開始時，主存沒有裝入任何一頁的信息。v如果作業(yè)如果

28、作業(yè)Ji在運行中在運行中成功訪問的次數(shù)成功訪問的次數(shù)為為S，不成功的訪不成功的訪問次數(shù)問次數(shù)為為F(產(chǎn)生缺頁中斷的次數(shù)產(chǎn)生缺頁中斷的次數(shù))，則作業(yè)執(zhí)行過程中，則作業(yè)執(zhí)行過程中總的訪問次數(shù)總的訪問次數(shù)為為A.v這里，這里，A=S(成功訪問的次數(shù)成功訪問的次數(shù))+F(不成功的訪問次數(shù)不成功的訪問次數(shù))v作業(yè)作業(yè)Ji執(zhí)行過程中的執(zhí)行過程中的缺頁率缺頁率f=F/A。重點重點311. 最佳（最佳（OPT）置換算法）置換算法v最佳置換算法是由最佳置換算法是由Belady于于1966年提出的一種理年提出的一種理論上的算法。論上的算法。v其所選擇的被淘汰頁面，將是其所選擇的被淘汰頁面，將是以后永不使用以后永不

29、使用的，的，或許是或許是在最長在最長(未來未來)時間內不再被訪問時間內不再被訪問的頁面。的頁面。v采用最佳置換算法，通?？杀ＷC獲得最低的缺頁采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。率。v但由于人們目前還無法預知一個進程在內存的若但由于人們目前還無法預知一個進程在內存的若干個頁面中，哪一個頁面是未來最長時間內不再干個頁面中，哪一個頁面是未來最長時間內不再被訪問的，因而該算法是無法實現(xiàn)的，但可以利被訪問的，因而該算法是無法實現(xiàn)的，但可以利用該算法去評價其它算法。用該算法去評價其它算法。32假定系統(tǒng)為某進程分配了三個物理塊，并考慮假定系統(tǒng)為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：有

30、以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1圖圖 最佳頁面置換算法最佳頁面置換算法引用串引用串70701120304230321201701頁框頁框(物理塊）物理塊）707021023423023021071由圖可看出，采用最佳置換算法發(fā)生了由圖可看出，采用最佳置換算法發(fā)生了6次頁面置換，次頁面置換，9次缺頁。次缺頁。33重點回顧重點回顧v覆蓋技術是指程序運行過程中，把同一存儲區(qū)在覆蓋技術是指程序運行過程中，把同一存儲區(qū)在不同時刻分配給不同程序段或數(shù)據(jù)段，它是實現(xiàn)不同時刻分配給不同程序段或數(shù)據(jù)段，它是實現(xiàn)存儲區(qū)共享的一種內存分配技術。存儲區(qū)

31、共享的一種內存分配技術。v交換技術是系統(tǒng)根據(jù)需要把內存中暫時不能運行交換技術是系統(tǒng)根據(jù)需要把內存中暫時不能運行的進程或暫時不用的部分程序和數(shù)據(jù)移到外存，的進程或暫時不用的部分程序和數(shù)據(jù)移到外存，以便騰出足夠的內存空間，把外存中已具備運行以便騰出足夠的內存空間，把外存中已具備運行條件的進程或部分程序和數(shù)據(jù)換入，使其運行。條件的進程或部分程序和數(shù)據(jù)換入，使其運行。34重點回顧重點回顧v程序局部性原理是指程序在執(zhí)行時將呈現(xiàn)程序局部性原理是指程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律，即在一較短的時間內，程出局部性規(guī)律，即在一較短的時間內，程序的執(zhí)行僅局限于某個部分；相應地，它序的執(zhí)行僅局限于某個部分；相應地，它

32、所訪問的存儲空間也局限于某個區(qū)域。所訪問的存儲空間也局限于某個區(qū)域。v請求分頁存儲管理方式請求分頁存儲管理方式 頁表頁表 地址變換機構和缺頁中斷機構地址變換機構和缺頁中斷機構35重點回顧重點回顧v頁面置換算法：頁面置換算法：v最佳（最佳（OPT）置換算法）置換算法36v基本思想是：總是先淘汰那些駐留在內存時基本思想是：總是先淘汰那些駐留在內存時間最長的頁面，即先進入內存的頁面先被置間最長的頁面，即先進入內存的頁面先被置換掉。理由是：最先進入內存的頁面不再被換掉。理由是：最先進入內存的頁面不再被訪問的可能性最大。訪問的可能性最大。vFIFO算法容易實現(xiàn)，但是它所依據(jù)的理由不算法容易實現(xiàn)，但是它所

33、依據(jù)的理由不是普遍成立的。那些在內存中駐留很久的頁是普遍成立的。那些在內存中駐留很久的頁，往往是被經(jīng)常訪問的頁，結果這些常用的，往往是被經(jīng)常訪問的頁，結果這些常用的頁都被淘汰調出，而可能又需要立即調回內頁都被淘汰調出，而可能又需要立即調回內存。存。2先進先出先進先出(FIFO)頁面置換算法頁面置換算法37圖圖 FIFO置換算法置換算法 引用串引用串70701120304230321201701頁框頁框(物理塊）物理塊）707021321340203103172由圖可看出，采用由圖可看出，采用FIFO置換算法發(fā)生了置換算法發(fā)生了12次頁面置次頁面置換，換，15次缺頁。次缺頁。2先進先出先進先出(

34、FIFO)頁面置換算法頁面置換算法32024024310207270138v 采用采用FIFO算法還會產(chǎn)生一種奇怪現(xiàn)象，直觀上，分配給的作算法還會產(chǎn)生一種奇怪現(xiàn)象，直觀上，分配給的作業(yè)的實頁越多，進程執(zhí)行時發(fā)生的缺頁中斷率就越小，但對業(yè)的實頁越多，進程執(zhí)行時發(fā)生的缺頁中斷率就越小，但對FIFO算法這個結論并不是絕對的。在某些情況下，當分配的算法這個結論并不是絕對的。在某些情況下，當分配的頁面多反而導致更多的缺頁中斷，這種現(xiàn)象稱為頁面多反而導致更多的缺頁中斷，這種現(xiàn)象稱為FIFO異?，F(xiàn)異?，F(xiàn)象或稱象或稱Belady現(xiàn)象?，F(xiàn)象。2先進先出先進先出(FIFO)頁面置換算法頁面置換算法所謂異常現(xiàn)象，即

35、在未所謂異?，F(xiàn)象，即在未給進程或作業(yè)分配足它給進程或作業(yè)分配足它所要求的頁面數(shù)時，有所要求的頁面數(shù)時，有時會出現(xiàn)分配的頁面數(shù)時會出現(xiàn)分配的頁面數(shù)增多，缺頁次數(shù)反而增增多，缺頁次數(shù)反而增加的奇怪現(xiàn)象。加的奇怪現(xiàn)象。392先進先出先進先出(FIFO)頁面置換算法頁面置換算法例：設進程例：設進程P有有5頁，頁，P在內存中分配了在內存中分配了3個頁面，程個頁面，程序訪問順序為：序訪問順序為：1,2,3,4,1,2,5,1,2,3,4,5計算缺頁率（缺頁次數(shù)計算缺頁率（缺頁次數(shù)/訪問次數(shù)）訪問次數(shù)）引用串引用串1212334 1 2 5 1 2 3 4 5頁框頁框(物理塊）物理塊）12124314235

36、4152352143由圖可看出，采用由圖可看出，采用FIFO置換算法發(fā)生置換算法發(fā)生了了6次頁面置換，次頁面置換，9次缺頁。次缺頁。402先進先出先進先出(FIFO)頁面置換算法頁面置換算法上例中上例中P在內存中分配了在內存中分配了4個頁面，計算缺頁率（缺個頁面，計算缺頁率（缺頁次數(shù)頁次數(shù)/訪問次數(shù)）訪問次數(shù)）引用串引用串1212334 1 2 5 1 2 3 4 5頁框頁框(物理塊）物理塊）由圖可看出，采用由圖可看出，采用FIFO置換算法發(fā)生置換算法發(fā)生了了6次頁面置換，次頁面置換，10次缺頁。次缺頁。1121234523451345124512341234523413. 最近最久未使用最近

37、最久未使用(LRU)置換算法置換算法vFIFO置換算法性能之所以較差，是因為它所依據(jù)置換算法性能之所以較差，是因為它所依據(jù)的條件是各個頁面調入內存的時間，而頁面調入的條件是各個頁面調入內存的時間，而頁面調入的先后并不能反映頁面的使用情況。的先后并不能反映頁面的使用情況。v最近最久未使用最近最久未使用(LRU)的頁面置換算法，是根據(jù)的頁面置換算法，是根據(jù)頁面頁面調入內存后調入內存后的使用情況進行決策的。由于無的使用情況進行決策的。由于無法預測各頁面將來的使用情況，只能利用法預測各頁面將來的使用情況，只能利用“最近最近的過去的過去”作為作為“最近的將來最近的將來”的近似，因此，的近似，因此，LRU

38、置換算法是選擇最近最久未使用的頁面予以置換算法是選擇最近最久未使用的頁面予以淘汰。淘汰。v該算法賦予每個頁面一個訪問字段，用來記錄一該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間個頁面自上次被訪問以來所經(jīng)歷的時間t，當須淘，當須淘汰一個頁面時，選擇現(xiàn)有頁面中其汰一個頁面時，選擇現(xiàn)有頁面中其t值最大的，即值最大的，即最近最久未使用的頁面予以淘汰。最近最久未使用的頁面予以淘汰。42圖圖 LRU置換算法置換算法 引用串引用串70701120304230321201701頁框頁框(物理塊）物理塊）707021023043302312017由圖可看出，采用由圖可看出，采用L

39、RU置換算法發(fā)生了置換算法發(fā)生了9次頁面置換，次頁面置換，12次缺頁。次缺頁。042342012（1） LRU置換算法的描述置換算法的描述43（2）LRU置換算法的硬件支持置換算法的硬件支持vLRU置換算法雖然是一種比較好的算法，置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的但要求系統(tǒng)有較多的支持硬件支持硬件。為了了解。為了了解一個進程在內存中的各個頁面各有多少時一個進程在內存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類一頁是最近最久未使用的頁面，須有兩類硬件之一的支持：計時法、移位寄存器或硬件之一的支持

40、：計時法、移位寄存器或棧。棧。44圖圖 LRU置換算法置換算法 引用串引用串70701720304230321201701頁框頁框(物理塊）物理塊）01120032043302213170由圖可看出，采用由圖可看出，采用LRU置換算法發(fā)生了置換算法發(fā)生了9次頁面置換，次頁面置換，12次缺頁。次缺頁。420234201（2）LRU置換算法的硬件支持置換算法的硬件支持7201302032320123012701017454. 簡單簡單Clock置換算法置換算法v 當采用簡單當采用簡單Clock算法時，只需為每頁設置算法時，只需為每頁設置一位訪問位一位訪問位，再，再將內存中的所有頁面都通過鏈接指針鏈

41、接成一個循環(huán)隊列。將內存中的所有頁面都通過鏈接指針鏈接成一個循環(huán)隊列。v 當某頁被訪問時，其訪問位被置當某頁被訪問時，其訪問位被置1。v 置換算法在選擇一頁淘汰時，只需檢查頁的訪問位。如果是置換算法在選擇一頁淘汰時，只需檢查頁的訪問位。如果是0，就選擇該頁換出；若為，就選擇該頁換出；若為1，則重新將它置，則重新將它置0，暫不換出，暫不換出，而給該頁第二次駐留內存的機會，再按照而給該頁第二次駐留內存的機會，再按照FIFO算法檢查下算法檢查下一個頁面。一個頁面。v 當檢查到隊列中的最后一個頁面時，若其訪問位仍為當檢查到隊列中的最后一個頁面時，若其訪問位仍為1，則，則再返回到隊首去檢查第一個頁面。再

42、返回到隊首去檢查第一個頁面。v 下圖示出了該算法的流程和示例。由于該算法是循環(huán)地檢查下圖示出了該算法的流程和示例。由于該算法是循環(huán)地檢查各頁面的使用情況，故稱為各頁面的使用情況，故稱為Clock算法。但因該算法只有一算法。但因該算法只有一位訪問位，只能用它表示該頁是否已經(jīng)使用過，而置換時是位訪問位，只能用它表示該頁是否已經(jīng)使用過，而置換時是將未使用過的頁面換出去，故又把該算法稱為最近未用算法將未使用過的頁面換出去，故又把該算法稱為最近未用算法NRU(Not Recently Used)。46圖簡單圖簡單Clock置換算法的流程和示例置換算法的流程和示例 入口查尋指針前進一步，指向下一個表目頁面

43、訪問位0選擇該頁面淘汰是返回置頁面訪問位“ 0 ”塊號頁號 訪問位 指針0124034215650711替換指針否475改進型改進型Clock置換算法置換算法v在將一個頁面換出時，如果該頁已被修改過，便在將一個頁面換出時，如果該頁已被修改過，便須將該頁重新寫回到磁盤上；但如果該頁未被修須將該頁重新寫回到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。改過，則不必將它拷回磁盤。v在改進型在改進型Clock算法中，除須考慮頁面的使用情況算法中，除須考慮頁面的使用情況外，還須再增加一個因素，即外，還須再增加一個因素，即置換代價置換代價，這樣，這樣，選擇頁面換出時，既要是未使用過的頁面，又要選擇頁面

44、換出時，既要是未使用過的頁面，又要是未被修改過的頁面。把同時滿足這兩個條件的是未被修改過的頁面。把同時滿足這兩個條件的頁面作為首選淘汰的頁面。頁面作為首選淘汰的頁面。v由訪問位由訪問位A和修改位和修改位M可以組合成下面四種類型可以組合成下面四種類型的頁面：的頁面： 485改進型改進型Clock置換算法置換算法v1類類(A=0，M=0)：表示該頁最近既未被訪問，又：表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。未被修改，是最佳淘汰頁。v2類類(A=0，M=1)：表示該頁最近未被訪問，但已：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。被修改，并不是很好的淘汰頁。v3類類(A=1，M=

45、0)：表示該頁最近已被訪問，但未：表示該頁最近已被訪問，但未被修改，該頁有可能再被訪問。被修改，該頁有可能再被訪問。v4類類(A=1，M=1)：表示該頁最近已被訪問且被修：表示該頁最近已被訪問且被修改，該頁可能再被訪問。改，該頁可能再被訪問。 v在內存中的每個頁必定是這四類頁面之一，在進在內存中的每個頁必定是這四類頁面之一，在進行頁面置換時，可采用與簡單行頁面置換時，可采用與簡單Clock算法相類似的算法相類似的算法，其差別在于該算法須算法，其差別在于該算法須同時檢查訪問位與修同時檢查訪問位與修改位改位，以確定該頁是四類頁面中的哪一種。其執(zhí)，以確定該頁是四類頁面中的哪一種。其執(zhí)行過程可分成以下

46、三步：行過程可分成以下三步：495改進型改進型Clock置換算法置換算法(1) 從指針所指示的當前位置開始，掃描循環(huán)隊列，尋找從指針所指示的當前位置開始，掃描循環(huán)隊列，尋找A=0且且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位的淘汰頁。在第一次掃描期間不改變訪問位A。(2)如果第一步失敗，則開始第二輪掃描，尋找如果第一步失敗，則開始第二輪掃描，尋找A=0且且M=1的的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位

47、都置第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。(3) 如果第二步也失敗，則將指針返回到開始的位置，并將如果第二步也失敗，則將指針返回到開始的位置，并將所有的訪問位復所有的訪問位復0。然后回到第一步重新開始，一定能找。然后回到第一步重新開始，一定能找到被淘汰的頁。到被淘汰的頁。v 該算法與簡單該算法與簡單Clock算法比較，可減少磁盤的算法比較，可減少磁盤的I/O操作次數(shù)操作次數(shù)。但為了找到一個可置換的頁，可能須經(jīng)過幾輪掃描。換。但為了找到一個可置換的頁，可能須經(jīng)過幾輪掃描。換言之，實現(xiàn)該算法的開銷有所增加。言之，實現(xiàn)該算法的開銷有所增加。 50例如：例如：在一采用局部置換策略的請求分頁

48、系統(tǒng)中，分在一采用局部置換策略的請求分頁系統(tǒng)中，分配給某作業(yè)的內存塊數(shù)為配給某作業(yè)的內存塊數(shù)為4。其中存放的四個頁面。其中存放的四個頁面的情況如下：的情況如下： 所有值為十進制，進程運行從時刻所有值為十進制，進程運行從時刻0開始。請問，若開始。請問，若采用下列算法，將選擇哪一頁進行置換？采用下列算法，將選擇哪一頁進行置換？ (1)FIFO算法；算法；(2)LRU算法；算法；(3)改進的改進的Clock算法。算法。例題例題物理塊物理塊虛頁號虛頁號裝入時間裝入時間最后訪問最后訪問訪問位訪問位修改位修改位0 02 260601571570 01 11 11 11601601611611 10 02

49、20 026261581580 00 03 33 320201631631 11 151例題例題答答:(1) 由表中裝入時間可知，最先裝入內存的是第由表中裝入時間可知，最先裝入內存的是第3頁頁，所以采用，所以采用FIFO算法時，將選擇第算法時，將選擇第3頁進行置換。頁進行置換。(2) 由表中最后訪問時間可知，最近最久未使用的是由表中最后訪問時間可知，最近最久未使用的是第第2頁，所以采用頁，所以采用LRU算法時，將選擇第算法時，將選擇第2頁進行置頁進行置換。換。(3) 從表中可知，訪問位和修改位均為從表中可知，訪問位和修改位均為0，即未訪問，即未訪問過的頁面，又未被修改過的頁面是第過的頁面，又未

50、被修改過的頁面是第0頁，所以采用頁，所以采用改進的改進的Clock算法時，將選擇第算法時，將選擇第0頁進行置換。頁進行置換。52例題例題v設某計算機的邏輯地址空間和設某計算機的邏輯地址空間和物理地址空間均為物理地址空間均為64KB，按，按字節(jié)編址。若某進程最多需要字節(jié)編址。若某進程最多需要6頁（頁（Page）數(shù)據(jù)存儲空間，）數(shù)據(jù)存儲空間，頁的大小為頁的大小為1KB。操作系統(tǒng)采。操作系統(tǒng)采用用固定分配局部置換固定分配局部置換策略為此策略為此進程分配進程分配4個頁框（個頁框（Page Fame）。）。2010年真題年真題頁頁號號頁框頁框號號裝入裝入時刻時刻訪問訪問位位071301142301222

51、00139160153例題例題v當該進程執(zhí)行到時刻當該進程執(zhí)行到時刻260時，要訪問邏輯地址為時，要訪問邏輯地址為17CAH的數(shù)據(jù)，請回答下列問題：的數(shù)據(jù)，請回答下列問題：（1）該邏輯地址對應的頁號是多少？）該邏輯地址對應的頁號是多少？（2）若采用先進先出（）若采用先進先出（FIFO）置換算法，該邏輯）置換算法，該邏輯地址對應的物理地址是多少？要求給出計算過程地址對應的物理地址是多少？要求給出計算過程。（3）若采用時鐘（）若采用時鐘（CLOCK）置換算法，該邏輯地）置換算法，該邏輯地址對應的物理地址是多少？要求給出計算過程。址對應的物理地址是多少？要求給出計算過程。（設搜索下一頁的指針沿（設搜

52、索下一頁的指針沿順時針順時針方向移動，且當方向移動，且當前前指向指向2號頁框號頁框，示意圖如下。），示意圖如下。） 54答：答：（1）17CAH 轉換為二進制為：轉換為二進制為：0001 01 11 1100 1010, 頁的大小頁的大小為為1KB，所以頁內偏移為，所以頁內偏移為10位，于是高位，于是高6位是頁號，所以其頁位是頁號，所以其頁號為號為0001 01，轉換為，轉換為10進制為進制為5，所以，所以，17CAH對應的頁號對應的頁號為為5。（2）若采用先進先出置換算法，則被置換出的第）若采用先進先出置換算法，則被置換出的第0頁對應的頁框頁對應的頁框號是號是7，因此對應的二進制物理地址為：

53、，因此對應的二進制物理地址為：0001 11 11 1100 1010，轉換為，轉換為16進制的物理地址為進制的物理地址為1FCAH。（3）若采用時鐘算法，且當前指針指向）若采用時鐘算法，且當前指針指向2號頁框，則第一次循環(huán)號頁框，則第一次循環(huán)時，訪問位都被置為時，訪問位都被置為0，在第二次循環(huán)時，將選擇置換，在第二次循環(huán)時，將選擇置換2號頁號頁框對應的頁，因此對應的二進制物理地址為：框對應的頁，因此對應的二進制物理地址為：0000 10 11 1100 1010，轉換為，轉換為16進制物理地址為進制物理地址為0BCAH。556.3.4 性能問題性能問題1. 抖動抖動v 剛被淘汰的頁面又馬上被

54、調回內存，調回內存不久后又被剛被淘汰的頁面又馬上被調回內存，調回內存不久后又被淘汰出去，如此頻繁進行，這種現(xiàn)象稱為抖動（或稱顛淘汰出去，如此頻繁進行，這種現(xiàn)象稱為抖動（或稱顛簸）。它使得系統(tǒng)中頁面調度非常頻繁，以致簸）。它使得系統(tǒng)中頁面調度非常頻繁，以致CPU大部分大部分時間都花費在內存和外存之間的調入調出上。時間都花費在內存和外存之間的調入調出上。2. 駐留集駐留集v 所謂駐留集是指進程在內存中的頁面集合，駐留集尺寸是所謂駐留集是指進程在內存中的頁面集合，駐留集尺寸是進程駐留在內存中的頁面數(shù)量。系統(tǒng)為了建立駐留集應采進程駐留在內存中的頁面數(shù)量。系統(tǒng)為了建立駐留集應采用一定的頁面調入策略。用一

55、定的頁面調入策略。566.3.4 性能問題性能問題3. 工作集工作集v工作集是指在某一時刻工作集是指在某一時刻t，進程最近，進程最近n次內被訪問的次內被訪問的頁面集合，數(shù)字頁面集合，數(shù)字n稱為工作集窗口，即工作集的大稱為工作集窗口，即工作集的大小。如果整個工作集都在內存中，在進入下一個運小。如果整個工作集都在內存中，在進入下一個運行階段之前進程的運行不會引起很多頁面故障。如行階段之前進程的運行不會引起很多頁面故障。如果內存太小無法容納整個工作集，進程運行將引起果內存太小無法容納整個工作集，進程運行將引起大量的頁面故障并且速度十分緩慢。大量的頁面故障并且速度十分緩慢。576.3.5 影響缺頁率因

56、素影響缺頁率因素影響缺頁率的主要因素有：影響缺頁率的主要因素有：（1）分配給作業(yè)的物理塊數(shù)）分配給作業(yè)的物理塊數(shù)（2）頁面置換算法）頁面置換算法（3）頁面大小的選擇）頁面大小的選擇（4）用戶程序的編制方法）用戶程序的編制方法586.3.6 Belady現(xiàn)象現(xiàn)象v直觀上，分配給進程的物理塊越多，進程執(zhí)行時發(fā)直觀上，分配給進程的物理塊越多，進程執(zhí)行時發(fā)生的缺頁次數(shù)就越小。但是在某些情況下，當分配生的缺頁次數(shù)就越小。但是在某些情況下，當分配的物理塊多反而導致缺頁次數(shù)更大，這種現(xiàn)象稱為的物理塊多反而導致缺頁次數(shù)更大，這種現(xiàn)象稱為Belady異?，F(xiàn)象或異常現(xiàn)象或FIFO置換算法的異?，F(xiàn)象。置換算法的異常

57、現(xiàn)象。vFIFO算法是基于隊列實現(xiàn)的，會出現(xiàn)算法是基于隊列實現(xiàn)的，會出現(xiàn)Belady異常異?，F(xiàn)象。而現(xiàn)象。而LRU算法是一種堆棧類算法，理論上可算法是一種堆棧類算法，理論上可證明，堆棧類算法不可能出現(xiàn)證明，堆棧類算法不可能出現(xiàn)Belady現(xiàn)象?，F(xiàn)象。596.3.7 請求分頁存儲管理的優(yōu)缺點請求分頁存儲管理的優(yōu)缺點v請求頁式存儲管理的優(yōu)點如下：請求頁式存儲管理的優(yōu)點如下： 主存利用率比較高。主存利用率比較高。 對磁盤管理比較容易。對磁盤管理比較容易。 地址映射和變換的速度比較快。地址映射和變換的速度比較快。v請求頁式存儲管理的缺點如下：請求頁式存儲管理的缺點如下： 程序的模塊化性能不好。程序的模

58、塊化性能不好。 頁表過長。頁表過長。60重點回顧重點回顧v頁面置換算法：頁面置換算法：v最佳（最佳（OPT）置換算法）置換算法v先進先出先進先出(FIFO)頁面置換算法頁面置換算法 最近最久未使用置換算法最近最久未使用置換算法(LRU) 簡單簡單Clock置換算法置換算法616.4 請求分段存儲管理方式請求分段存儲管理方式6.4.1 請求分段存儲管理方式的概念請求分段存儲管理方式的概念基本思想：基本思想：v在分段系統(tǒng)的基礎上，增加了請求調段功能和段置換在分段系統(tǒng)的基礎上，增加了請求調段功能和段置換功能所形成的段式虛擬存儲系統(tǒng)。功能所形成的段式虛擬存儲系統(tǒng)。v它允許只裝入程序它允許只裝入程序(

59、(及數(shù)據(jù)及數(shù)據(jù)) )的的少數(shù)段少數(shù)段，便啟動運行。，便啟動運行。以后，再通過調段功能及段置換功能，陸續(xù)地把即將以后，再通過調段功能及段置換功能，陸續(xù)地把即將要運行的段調入內存，同時把暫不運行的段換出到外要運行的段調入內存，同時把暫不運行的段換出到外存上。存上。v置換時以置換時以段為單位段為單位。為了能實現(xiàn)請求調段和段置換功。為了能實現(xiàn)請求調段和段置換功能，系統(tǒng)必須提供必要的硬件支持和相應的軟件。能，系統(tǒng)必須提供必要的硬件支持和相應的軟件。626.4.1 請求分段存儲管理方式的概念請求分段存儲管理方式的概念v 段表機制段表機制v在請求分段式管理中所需的主要數(shù)據(jù)結構是段表在請求分段式管理中所需的主

60、要數(shù)據(jù)結構是段表。由于在應用程序的許多段中，只有一部分段裝。由于在應用程序的許多段中，只有一部分段裝入內存，其余的一些段仍留在外存上，故須在段入內存，其余的一些段仍留在外存上，故須在段表中增加若干項，以供程序在調進、調出時參考表中增加若干項，以供程序在調進、調出時參考。下面給出請求分段的段表項。下面給出請求分段的段表項。 631段表機制段表機制(1) 存取權限：用于標識本分段的存取屬性是只執(zhí)行、存取權限：用于標識本分段的存取屬性是只執(zhí)行、只讀，還是允許讀只讀，還是允許讀/寫。寫。(2) 訪問字段訪問字段A：其含義與請求分頁的相應字段相同，：其含義與請求分頁的相應字段相同，用于記錄該段被訪問的頻