第8章_虛擬存儲管理

1、812 虛擬存儲器虛擬存儲器 n實現(xiàn)方法：實現(xiàn)方法：一個進程在運行之時，沒有必要全部裝入內存，而只把當前運行所需要的頁（段）裝入內存便可啟動運行，而其余部分則存放在磁盤上。程序在運行時，如果所需要的頁（段）已經(jīng)調入內存，便可以繼續(xù)執(zhí)行下去。如果所需要的頁（段）不在內存，此時程序應利用操作系統(tǒng)所提供的請求調頁（段）功能，將該頁（段）調入內存，以使程序能夠運行下去。如果此時分配給該程序的內存已全部占用，不能裝入新的頁（段），則需要利用系統(tǒng)的置換功能，把內存中暫時不用的頁（段）調出至磁盤上，騰出足夠的內存空間，再將所要裝入的頁（段）調入內存，使程序能夠繼續(xù)運行下去。 812 虛擬存儲器虛擬存儲器 n

2、虛擬存儲器的定義：虛擬存儲器的定義：是指僅把進程的一部分裝入內存便可運行的存儲器系統(tǒng)，它具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的一種存儲器系統(tǒng)。n虛擬存儲器的邏輯容量：虛擬存儲器的邏輯容量：虛擬存儲器的邏輯容量由系統(tǒng)的尋址能力和外存容量之和所決定。82 請求分頁式存儲管理方式請求分頁式存儲管理方式 請求分頁式存儲管理是在分頁式存儲管理的基礎上，增加了請求調頁功能、頁面置換功能而形成的頁式虛擬存儲系統(tǒng)。它是目前常用的一種虛擬存儲器的方式。82 1 請求分頁式存儲管理的基本概念請求分頁式存儲管理的基本概念 n基本原理：基本原理：在請求分頁式存儲管理系統(tǒng)中，進程運行之前將一部分頁面

3、裝入內存，另外一部分頁面則裝入外存。在進程運行過程中，如果所訪問的頁面不在內存中，則發(fā)生缺頁中斷，進入操作系統(tǒng)，由操作系統(tǒng)進行頁面的動態(tài)調度。其方法如下：u找到被訪問頁面在外存中的地址；u在內存中找一個空閑塊，如果沒有，則按照淘汰算法選擇一個內存塊，將此塊內容寫回外存，修改頁表；u讀入所需的頁面，修改頁表；u重新啟動進程，執(zhí)行被中斷的指令。 82 1 請求分頁式存儲管理的基本概念請求分頁式存儲管理的基本概念 n頁表機制：頁表機制：純分頁的頁表只有兩項：頁號和物理塊。而請求分頁存儲管理增加了調入功能和置換功能，故需在頁表中增加若干項，供程序在換進換出時參考。下面所示是一請求分頁系統(tǒng)中的頁表：頁號

4、物理塊號 狀態(tài)位P 訪問字段A 修改位M 外存地址u狀態(tài)位狀態(tài)位P：用于指示該頁是否已調入內存，0表示該頁已在內存，1表示該頁不在內存，供程序訪問時參考； u訪問字段訪問字段A：用于記錄該頁在一段時間內被訪問的次數(shù)，或最近已有多長時間未被訪問，供置換算法選擇頁面時參考； 82 1 請求分頁式存儲管理的基本概念請求分頁式存儲管理的基本概念 u修改位修改位M：用于記錄該頁在調入內存后是否被修改過。由于內存中的每一頁都在外存上保留一個副本，因此，若未被修改，在置換該頁時就不需將該頁寫回到磁盤上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該頁重寫回磁盤上，以保證磁盤上所保留的始終是最新副本

5、。 u外存地址：外存地址：用于指出該頁在外存上的地址，通常是物理塊號，供調入該頁時使用。 82 2 頁面分配策略頁面分配策略 n內存頁面分配策略：內存頁面分配策略：u平均分配平均分配 ：將內存中的所有可供分配的物理塊，平均分配給各個進程。這是最簡單的分配方式，它看起來很公平，但實際上很不公平，因為它沒有考慮進程的大小等因素。u按進程大小比例分配按進程大小比例分配 ：系統(tǒng)按進程的大小按比例分配物理塊。若m為可用物理塊總和，S為各進程頁面總和，si為第i個進程的頁面數(shù)，則為第i個進程分配的頁面數(shù)為：u按進程優(yōu)先級比例分配 ：為照顧重要的、緊迫的進程，使其能夠盡快的完成，可以為其分配較多的內存物理塊

6、。 )(mSsINTaii82 2 頁面分配策略頁面分配策略 n外存塊的分配策略：外存塊的分配策略：u靜態(tài)分配靜態(tài)分配 ：一個進程在運行前，將其所有頁面全部裝入外存。當某一外存頁面被調入內存時，所占用外存頁面并不釋放。這樣，當該頁面以后被淘汰時，如果它在內存中未被修改過，則不必寫回外存，因為外存中有一個和它完全相同的副本，這可以減少因頁面調度而引起的系統(tǒng)開銷，代價是犧牲一定的外存空間。u動態(tài)分配動態(tài)分配 ：一個進程在運行前，僅將未裝入內存的那部分頁面裝入外存。當某一外存頁面被調入內存，釋放所占用的外存空間。這樣，當該頁面以后被淘汰時，不管它在內存中是否被修改過，都必須重新為其申請外存物理塊，將

7、該頁重新寫回外存。這種方法的優(yōu)點是節(jié)省外存空間，但會增加由頁面調度而引起的系統(tǒng)開銷。82 3 頁面調入時機頁面調入時機 n請求調頁策略：請求調頁策略：當發(fā)生缺頁中斷時進行調度，即當訪問某一頁而該頁不在內存時，立即提出請求，由系統(tǒng)將所需頁面調入內存。顯然，采用純請求調頁策略，被調入內存的頁面一定會被用到，不會發(fā)生無意義的頁面調度。但是，請求調頁策略也有一個缺點，從缺頁中斷發(fā)生到頁面被調入內存，發(fā)生缺頁中斷的進程必須等待，影響了進程的推進速度。 n預調頁策略：預調頁策略：由于在外存上查找所缺的頁，須經(jīng)歷較長的時間。如果一個進程存放在外存中的許多頁在一個連續(xù)的區(qū)域中，每次調入若干個頁會比每次調入一頁

8、更高效些。但如果調入的一批頁面中的大多數(shù)都未被訪問，則這種調入又是低效的?？梢?，如果預測比較準確，會大大降低缺頁中斷率，從而提高進程的推進速度。82 4 頁面置換算法頁面置換算法 n最佳置換算法（最佳置換算法（OPT，Optimal）：）：最佳置換算法置換那些以后永不再使用的或者在最長的時間以后才會用到的頁面。顯然，這種算法的缺頁率最低。然而，該算法只是一種理論上的算法，因為很難估計哪一個頁面是以后永遠不再使用或在最長時間以后才會用到的頁面，所以，這種算法是不能實現(xiàn)的。盡管如此，該算法仍然是有意義的，可以把它作為衡量其它算法優(yōu)劣的一個標準。82 4 頁面置換算法頁面置換算法 【例8-1】假定系

9、統(tǒng)為某進程分配了3個物理塊，頁面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最佳置換算法，計算缺頁中斷次數(shù)和缺頁中斷率。 解：頁面置換過程如下表所示：頁面訪問序列頁面訪問序列50120304230321201501500000223332220100115122233222000101100511304440331222555+-+-+-+-+-+-缺頁中斷次數(shù)=9缺頁中斷率=9/20=45% 82 4 頁面置換算法頁面置換算法 n先進先出置換算法（先進先出置換算法（FIFO，F(xiàn)irst-In First-Out） ：先進先出置換算法總是置換

10、最先進入內存的頁面。該算法實現(xiàn)簡單，只須把一個進程已調入內存的頁面，按照進入內存的先后順序排成一個隊列，當一個頁面由外存調入內存時排入隊尾，需要淘汰時取隊首的頁面。82 4 頁面置換算法頁面置換算法 【例8-2】假定系統(tǒng)為某進程分配了3個物理塊，頁面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用先進先出置換算法，計算缺頁中斷次數(shù)和缺頁中斷率。 解：頁面置換過程如下表所示：頁面訪問序列頁面訪問序列5012030423032120150150122304230001222501501123042333011125050012304222300012

11、5+-+-+-+缺頁中斷次數(shù)=15缺頁中斷率=15/20=75% 82 4 頁面置換算法頁面置換算法 Belady異?，F(xiàn)象：異?，F(xiàn)象：一般而言，分配給進程的物理塊越多，運行時的缺頁次數(shù)應該越少。但是Belady在1969年發(fā)現(xiàn)了一個反例，使用FIFO算法時，四個物理塊時的缺頁次數(shù)比三個物理塊時的多，這種反常的現(xiàn)象稱為Belady異常。如下面兩表所示，一個進程有5個頁面，頁面訪問序列如下：Belady異?，F(xiàn)象（3個物理塊的FIFO現(xiàn)象） 82 4 頁面置換算法頁面置換算法 Belady異?，F(xiàn)象（4個物理塊的FIFO現(xiàn)象） 由表中可見，3個物理塊時缺頁次數(shù)是9次，缺頁中斷率為9/12=75%；而4

12、個物理塊時的缺頁次數(shù)是10次，缺頁中斷率為10/1283.3%。82 4 頁面置換算法頁面置換算法 n最近最久未使用置換算法（最近最久未使用置換算法（LRU，Least Recently Used）：）：該算法的基本思想是：如果某一頁面被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁面很久沒有被訪問，那么最近也不會再次被訪問。因此，該算法為每一個頁面設置一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，當須淘汰一個頁面時，選擇現(xiàn)有頁面中t值最大的，即最近最久未使用的頁面予以淘汰。uLRU的實現(xiàn)：的實現(xiàn)：p記時法：記時法：系統(tǒng)為每一頁面增設一個記時器。每當一個頁面被訪問時，當時的

13、絕對時鐘內容被拷貝到對應的記時器中，這樣系統(tǒng)記錄了內存所有頁面最后一次被訪問的時間。淘汰頁面時，選取記時器中值最小的頁面淘汰。82 4 頁面置換算法頁面置換算法 uLRU的缺點：的缺點：雖然LRU在理論上是可以實現(xiàn)的，但代價太高。為了實現(xiàn)LRU，需要在內存維持一個包含所有頁的鏈表，最近使用的頁面在表頭，最近未使用的頁面在表尾。而每次訪問頁面時都需要對鏈表進行更新。在鏈表中找到所需的頁，將它移動到表頭是一個非常費時的操作，即使使用硬件實現(xiàn)也是一樣。 82 4 頁面置換算法頁面置換算法 【例8-3】假定系統(tǒng)為某進程分配了3個物理塊，頁面訪問序列為：5、0、1、2、0、3、0、4、2、3、0、3、2

14、、1、2、0、1、5、0、1。采用最近最久未使用置換算法，計算缺頁中斷次數(shù)和缺頁中斷率。 解：頁面置換過程如下表所示：頁面訪問序列頁面訪問序列50120304230321201501501203042303212015015012030423032120150501223042203312015+-+-+-+-+-+-缺頁中斷次數(shù)=12缺頁中斷率=12/20=60% 82 4 頁面置換算法頁面置換算法 n最近未使用置換算法最近未使用置換算法（NRU，Not Recently Used） ：為了克服LRU的缺點，最近未使用置換算法為每個頁面設置一位訪問位，將內存中的所有頁面都通過鏈接指針鏈成一個

15、循環(huán)隊列。當某頁被訪問時，其訪問位置1。在選擇一頁淘汰時，檢查其訪問位，如果是0，則淘汰該頁；若為1，則把其置0，暫不換出該頁，再按照FIFO算法檢查下一個頁面。當檢查到隊列中的最后一個頁面時，若其訪問位仍為1，則再返回隊首再去檢查第一個頁面。 事實上，NRU算法不但希望淘汰最近未使用的頁，而且還希望被挑選的頁在內存駐留期間，其頁面內的數(shù)據(jù)未被修改過。淘汰該頁時，由于該頁未被修改過，因此不必寫盤，從而減少了磁盤的I/O操作次數(shù)。為此，要為每頁增設兩個硬件位：訪問位和修改位：82 4 頁面置換算法頁面置換算法 訪問位A=0：該頁尚未被訪問過 =1：該頁已經(jīng)被訪問過修改位M=0：該頁尚未被修改過

16、=1：該頁已經(jīng)被修改過訪問位和修改位的組合有以下四種：u1類（A=0，M=0）：表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁；u2類（A=0，M=1）：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁；u3類（A=1，M=0）：最近已被訪問，但未被修改，該頁有可能再次被訪問；u4類（A=1，M=1）：最近已被訪問且被修改，該頁可能再次被訪問。82 4 頁面置換算法頁面置換算法 開始時，所有頁的訪問位、修改位都置為0。當訪問某頁時，將該頁訪問位置1。當某頁的數(shù)據(jù)被修改，則該頁的修改位置1。當要選擇一頁淘汰時，挑選內存中現(xiàn)有的類別最低的頁淘汰。 82 4 頁面置換算法頁面置換算法 nClo

17、ck置換算法：置換算法：最近未使用置換算法是一種比較合理的算法，但它經(jīng)常要在鏈表中移動頁面，大大降低了系統(tǒng)效率。為了克服這個缺陷，把所有的頁面保存在一個類似時鐘表面的環(huán)形鏈表中，用一個表針指向可能淘汰的頁面，如下圖所示 ABCDEFGHIJK82 4 頁面置換算法頁面置換算法 當發(fā)生缺頁時，該算法首先檢查表針指向的頁面，如果其訪問位是0，則淘汰該頁，并把新的頁面插入到這個位置，然后把表針前移一個位置；如果訪問位是1則把其置0，并把表針前移一個位置，重復這個過程直到找到一個訪問位為0的頁為止。了解了這個算法的工作方式，我們就知道這種算法為什么被稱為Clock算法了。它與最久未使用置換算法的區(qū)別僅

18、僅是實現(xiàn)方法上的不同。 82 5 請求分頁系統(tǒng)的性能分析請求分頁系統(tǒng)的性能分析 請求分頁式存儲管理系統(tǒng)的性能優(yōu)越，較好地解決了存儲擴充問題。因此，它是目前最常用的存儲管理方式。但進程在運行時所產(chǎn)生的缺頁中斷，會影響程序的運行速度及系統(tǒng)性能。而缺頁率的高低又與分配給進程的物理塊數(shù)直接相關。因此，本節(jié)所要介紹的主要內容，是分析缺頁率對系統(tǒng)性能的影響程度，以及應為每個進程分配多少物理塊數(shù)目，才能把缺頁率保持在一個合理的水平上。82 5 請求分頁系統(tǒng)的性能分析請求分頁系統(tǒng)的性能分析 n缺頁率對有效訪問時間的影響缺頁率對有效訪問時間的影響 ：u有效訪問時間：有效訪問時間：設p為缺頁率，t為存儲器訪問時間

19、，則有效訪問時間為： 有效訪問時間=（1p）t+p缺頁中斷時間u缺頁中斷時間的組成：缺頁中斷時間的組成：缺頁中斷時間主要由三部分組成：p缺頁中斷服務時間； p將所缺的頁讀入的時間； p進程重新執(zhí)行時間。82 5 請求分頁系統(tǒng)的性能分析請求分頁系統(tǒng)的性能分析 u缺頁中斷率對訪問時間的影響：其中缺頁中斷服務時間和進程重新執(zhí)行時間之和可以不超過1ms,而將一磁盤塊讀入內存的時間大概是24ms。所以缺頁中斷時間約為25ms。如果存儲器的平均訪問時間為100 ns，于是可得： 有效訪問時間=（1p） 0.1+p25000 =0.1+24999.9p 如果希望在缺頁時，僅使有效訪問時間延長不超過10%，則

20、可計算出缺頁率p 0.1(1+10%)0.1+24999.9p 即0000004. 09 .2499901. 0p83 1 請求分段存儲管理的基本概念請求分段存儲管理的基本概念 n基本原理：基本原理：在請求分段式存儲管理系統(tǒng)中，進程運行之前一部分段裝入內存，另外一部分段則裝入外存。在進程運行過程中，如果所訪問的段不在內存中，則發(fā)生缺段中斷，進入操作系統(tǒng)，由操作系統(tǒng)進行段的動態(tài)調度。n段表機制：段表機制：請求分段的段表是在純分段的段表機制的基礎上形成的。需在段表中增加若干項，供程序在換進換出時參考。下面所示是一請求分段系統(tǒng)中的段表：段名段長 段基址 存取方式 訪問字段 修改位 存在位 增補位 外

21、存地址p存取方式：存取方式：用于標識本段的存取屬性，存取屬性包括只執(zhí)行、只讀還是讀/寫；83 1 請求分段存儲管理的基本概念請求分段存儲管理的基本概念 p存取方式：存取方式：用于標識本段的存取屬性，存取屬性包括只執(zhí)行、只讀還是讀/寫；p訪問字段：訪問字段：用于記錄該段在一段時間內被訪問的次數(shù)，或最近已有多長時間未被訪問，供置換算法選擇段時參考；p修改位：修改位：表示該段在調入內存后是否被修改過。由于內存中的每一段都在外存上保留一個副本，因此，若未被修改，在置換該段時就不需將該段寫回到磁盤上，以減少系統(tǒng)的開銷和啟動磁盤的次數(shù)；若已被修改，則必須將該段重寫回磁盤上，以保證磁盤上所保留的始終是最新副

22、本；83 1 請求分段存儲管理的基本概念請求分段存儲管理的基本概念 p存在位：存在位：說明本段是否已調入內存；p增補位：增補位：用于表示本段在運行過程中，是否進行過動態(tài)增長；p外存地址：外存地址：用于指出該段在外存上的起始地址，通常是起始物理塊號，供調入該段時使用。83 1 請求分段存儲管理的基本概念請求分段存儲管理的基本概念 n地址變換機構：地址變換機構：請求分段系統(tǒng)中的地址變換機構，是在分段系統(tǒng)的地址變換機構的基礎上形成的。由于被訪問的段并非全在內存，所以在地址變換時，若發(fā)現(xiàn)所要訪問的段不在內存時，必須先將所缺的段調入內存，在修改了段表之后，才能利用段表進行地址變換。下圖給出了請求分段系統(tǒng)

23、的地址變換過程。83 2 分段共享與保護分段共享與保護 n分段共享：分段共享：在系統(tǒng)中配置一張共享段表，所有共享段都在共享段表中占有一個表項。共享段表除具有段表中的表項外，還記錄有共享此段的每個進程的情況，其中包括：u共享進程數(shù)共享進程數(shù)count：記錄共享該段的進程數(shù)，只有當count為0時，才由系統(tǒng)回收該段所占存儲區(qū)；u存取控制字段：存取控制字段：記錄不同進程的不同存取權限。如對于擁有該段的進程，則允許讀和寫，而對于其它進程，則可能只允許讀，或者只允許執(zhí)行。 842 Linux的頁表機制的頁表機制n頁表：頁表：在Linux系統(tǒng)中，頁的大小為4KB，因此每個進程的虛存空間要有1M個頁面。如果

24、采用一級頁表描述這種映射關系，每個進程的頁表就要有1M個表項。顯然，用大量的內存資源來存放頁表的方法是不可取的，所以，Linux采用三級頁表的方式。u頁目錄（頁目錄（PGD）：）：第一級頁表為頁目錄，每個活動進程有一個頁目錄。頁目錄的大小為一頁的尺寸，頁目錄的每一項指向頁中間目錄中的一頁。每個活動進程的頁目錄都必須在內存中。u頁中間目錄（頁中間目錄（PMD）：）：第二級頁表為頁中間目錄。頁中間目錄可以有多個頁，頁中間目錄的每一項指向頁表中的一頁。u頁表（頁表（PT）：）：第三級目錄為頁表。頁表也可以有多個頁，頁表中的每一項指向該進程的一個虛擬頁。 842 Linux的頁表機制的頁表機制u把虛擬

25、地址中的最高位段與寄存器中的PGD基地址相加，在PGD中找到相應的表項，該表項指向相應的PMD基地址；u把虛擬地址中的第二個位段與PMD的基地址相加，在PMD中找到相應的表項，該表項指向相應的PT基地址；u把虛擬地址中的第三個位段與PT的基地址相加，在PT中找到相應的表項，該表項指向相應的物理頁面；u把虛擬地址中的最低位段與物理頁面的基地址相加，得到相應的物理地址。843 Linux內存頁的分配內存頁的分配 為了提高往內存中讀入頁和從內存中寫出頁的效率，Linux采用了一種機制，即把連續(xù)的頁映射到連續(xù)的物理塊中?；谶@個目的，它采用了一種伙伴系統(tǒng)。內核維護一系列大小固定的連續(xù)物理塊組，一組可以

26、包含1、2、4、8、16或32個物理塊。當一頁在內存中被分配或被釋放時，可用的組使用伙伴算法被分割或合并。844 Linux內存頁的置換算法內存頁的置換算法 Linux的頁面置換算法采用最近最少使用置換算法（NRU）。在簡單的最近最少使用置換算法中，內存中的每一頁都有一個訪問位和一個修改位。在Linux系統(tǒng)中，用一個8位的age變量取代了訪問位。每當一頁被訪問時，age變量增1。在后臺，Linux周期性地掃描全局頁池，并將所有大于0的age變量減1。Age的值為0的頁在較長一段時間內未被訪問過，是用于置換的最佳候選頁。age的值越大，該頁最近被使用的頻率越高，從而越不適合于被置換。85 Windows存儲管理存儲管理 Windows有一個非常成功的虛擬存儲系統(tǒng)。有大量的Win32函數(shù)和六個內核線程在進行存儲管理。它采用的是