虛擬頁式存儲管理
1 分頁機制
在虛擬內存中，頁表是個映射表的概念, 即從進程能理解的線性地址(linear address)映射到存儲器上的物理地址(phisical address).
很顯然，這個頁表是需要常駐內存的東西, 以應對頻繁的查詢映射需要(實際上，現代支持VM的處理器都有一個叫TLB的硬體級頁表緩存部件，本文不討論）。
1.1 為什麼使用多級頁表來完成映射
但是為什麼要使用多級頁表來完成映射呢?
用來將虛擬地址映射到物理地址的數據結構稱為頁表, 實現兩個地址空間的關聯最容易的方式是使用數組, 對虛擬地址空間中的每一頁, 都分配一個數組項. 該數組指向與之關聯的頁幀, 但這會引發一個問題, 例如, IA-32體系結構使用4KB大小的頁, 在虛擬地址空間為4GB的前提下, 則需要包含100萬項的頁表. 這個問題在64位體系結構下, 情況會更加糟糕. 而每個進程都需要自身的頁表, 這回導致系統中大量的所有內存都用來保存頁表.
設想一個典型的32位的X86系統，它的虛擬內存用戶空間(user space)大小為3G, 並且典型的一個頁表項(page table entry, pte)大小為4 bytes，每一個頁(page)大小為4k bytes。那麼這3G空間一共有(3G/4k=)786432個頁面，每個頁面需要一個pte來保存映射信息，這樣一共需要786432個pte!
如何存儲這些信息呢？一個直觀的做法是用數組來存儲，這樣每個頁能存儲(4k/4=)1K個，這樣一共需要(786432/1k=)768個連續的物理頁面(phsical page)。而且，這只是一個進程，如果要存放所有N個進程，這個數目還要乘上N! 這是個巨大的數目，哪怕內存能提供這樣數量的空間，要找到連續768個連續的物理頁面在系統運行一段時間後碎片化的情況下，也是不現實的。
為減少頁表的大小並容許忽略不需要的區域, 計算機體系結構的涉及會將虛擬地址分成多個部分. 同時虛擬地址空間的大部分們區域都沒有使用, 因而頁沒有關聯到頁幀, 那麼就可以使用功能相同但內存用量少的多的模型: 多級頁表
但是新的問題來了, 到底採用幾級頁表合適呢?
1.2 32位系統中2級頁表
從80386開始, intel處理器的分頁單元是4KB的頁, 32位的地址空間被分為3部分
單元
描述
頁目錄表Directory 最高10位
頁中間表Table 中間10位
頁內偏移 最低12位
即頁表被劃分為頁目錄表Directory和頁中間表Tabl兩個部分
此種情況下, 線性地址的轉換分為兩步完成.
第一步, 基於兩級轉換表(頁目錄表和頁中間表), 最終查找到地址所在的頁幀
第二步, 基於偏移, 在所在的頁幀中查找到對應偏移的物理地址
使用這種二級頁表可以有效的減少每個進程頁表所需的RAM的數量. 如果使用簡單的一級頁表, 那將需要高達220個頁表, 假設每項4B, 則共需要佔用220?4B=4MB的RAM來表示每個進程的頁表. 當然我們並不需要映射所有的線性地址空間(32位機器上線性地址空間為4GB), 內核通常只為進程實際使用的那些虛擬內存區請求頁表來減少內存使用量.
1.3 64位系統中的分頁
正常來說, 對於32位的系統兩級頁表已經足夠了, 但是對於64位系統的計算機, 這遠遠不夠.
首先假設一個大小為4KB的標准頁. 因為1KB覆蓋210個地址的范圍, 4KB覆蓋212個地址, 所以offset欄位需要12位.
這樣線性地址空間就剩下64-12=52位分配給頁中間表Table和頁目錄表Directory. 如果我們現在決定僅僅使用64位中的48位來定址(這個限制其實已經足夠了, 2^48=256TB, 即可達到256TB的定址空間). 剩下的48-12=36位被分配給Table和Directory欄位. 即使我們現在決定位兩個欄位各預留18位, 那麼每個進程的頁目錄和頁表都包含218個項, 即超過256000個項.
基於這個原因, 所有64位處理器的硬體分頁系統都使用了額外的分頁級別. 使用的級別取決於處理器的類型
平台名稱
頁大小
定址所使用的位數
分頁級別數
線性地址分級
alpha 8KB 43 3 10 + 10 + 10 + 13
ia64 4KB 39 3 9 + 9 + 9 + 12
ppc64 4KB 41 3 10 + 10 + 9 + 12
sh64 4KB 41 3 10 + 10 + 9 + 12
x86_64 4KB 48 4 9 + 9 + 9 + 9 + 12
② 頁式虛擬存儲管理,過小的頁會引起什麼問題
會引起內存變小。在頁式虛擬存儲管理系統中，頁面的大小是由計算機系統的地址結構所決定的，一般由軟硬體共同決定。對於某一種系統一般採用一種大小穗簡的頁面，也有部分現代操蘆皮作系統採用雙頁面系統的。在確定地址結構時，若選擇的頁面較小，一方面可使內碎片減小，並減少了內碎猜嘩褲片的總空間，有利於提高內存利用率。另一方面，也會使每個進程要求較多的頁面，從而導致頁表過長，佔用大量內存。此外還會降低頁面換進換出的效率。
③ 在頁式虛擬存貯器中，什麼叫頁面失效什麼叫頁面爭用什麼時候兩者同時發生
頁面失效是該頁未裝入主存，需要從輔存中調頁。頁面爭用(沖突)是兩個以上的虛頁想要進入主存中同一頁面位置的現象。頁面失效不一定發生頁面沖突，頁面爭用一定由頁面失效引起。
④ 採用頁式虛擬存儲管理方式頁大小為8KB，主存塊大小為64B，為什麼物理地址的頁內偏移量不等於主存塊大小
物理地址的頁偏移量等於對應虛擬地址的頁偏移量，虛擬地址的頁偏移量與頁大小有關，這里頁大小8KB，2的13次方，所以頁偏移量為13位。
⑤ 什麼是LRU測試請知道的告訴一下
LRU是Least Recently Used的縮寫，即最近最少使用頁面置換演算法，是為虛擬頁式存儲管理服務的。 關 於操作系統的內存管理，如何節省利用容量不大的內存為最多的進程提供資源，一直是研究的重要方向。而內存的虛擬存儲管理，是現在最通用，最成功的方式—— 在內存有限的情況下，擴展一部分外存作為虛擬內存，真正的內存只存儲當前運行時所用得到信息。這無疑極大地擴充了內存的功能，極大地提高了計算機的並發 度。虛擬頁式存儲管理，則是將進程所需空間劃分為多個頁面，內存中只存放當前所需頁面，其餘頁面放入外存的管理方式。 然而，有利就有弊，虛擬頁式存儲管理減少了進程所需的內存空間，卻也帶來了運行時間變長這一缺點：進程運行過程中，不可避免地要把在外存中存放的一些信息和 內存中已有的進行交換，由於外存的低速，這一步驟所花費的時間不可忽略。因而，採取盡量好的演算法以減少讀取外存的次數，也是相當有意義的事情。 對 於虛擬頁式存儲，內外存信息的替換是以頁面為單位進行的——當需要一個放在外存的頁面時，把它調入內存，同時為了保持原有空間的大小，還要把一個內存中頁 面調出至外存。自然，這種調動越少，進程執行的效率也就越高。那麼，把哪個頁面調出去可以達到調動盡量少的目的？我們需要一個演算法。 自然，達到這樣一種情形的演算法是最理想的了——每次調換出的頁面是所有內存頁面中最遲將被使用的——這可以最大限度的推遲頁面調換，這種演算法，被稱為理想頁面置換演算法。可惜的是，這種演算法是無法實現的。 為了盡量減少與理想演算法的差距，產生了各種精妙的演算法，最近最少使用頁面置換演算法便是其中一個。LRU演算法的提出，是基於這樣一個事實：在前面幾條指令中使用頻繁的頁面很可能在後面的幾條指令中頻繁使用。反過來說，已經很久沒有使用的頁面很可能在未來較長的一段時間內不會被用到。這個，就是著名的局部性原理——比內存速度還要快的cache，也是基於同樣的原理運行的。因此，我們只需要在每次調換時，找到最近最少使用的那個頁面調出內存。這就是LRU演算法的全部內容。 如何用具體的數據結構來實現這個演算法？ 首先，最容易想到，也最簡單的方法：計時法。給頁表中的每一頁增加一個域，專門用來存放計時標志，用來記錄該頁面自上次被訪問以來所經歷的時間。頁面每被訪問一次，計時清0。要裝入新頁時，從內存的頁面中選出時間最長的一頁，調出，同時把各頁的計時標志全部清0，重新開始計時。 計時法可以稍作改變，成為計數法：頁面被訪問，計數標志清0，其餘所有內存頁面計數器加1；要裝入新頁時，選出計數最大的一頁調出，同時所有計數器清0。 這兩種方法確實很簡單，但運行效率卻不盡如人意。每個時刻，或是每調用一個頁面，就需要對內存中所有頁面的訪問情況進行記錄和更新，麻煩且開銷相當大。 另一種實現的方法：鏈表法。 操作系統為每個進程維護一條鏈表，鏈表的每個結點記錄一張頁面的地址。調用一次頁面，則把該頁面的結點從鏈中取出，放到鏈尾；要裝入新頁，則把鏈頭的頁面調出，同時生成調入頁面的結點，放到鏈尾。 鏈表法可看作簡單計時/計數法的改良，維護一個鏈表，自然要比維護所有頁面標志要簡單和輕松。可是，這並沒有在數量級上改變演算法的時間復雜度，每調用一個頁面，都要在鏈表中搜尋對應結點並放至鏈尾的工作量並不算小。 以上是單純使用軟體實現的演算法。不過，如果能有特殊的硬體幫忙，我們可以有更有效率的演算法。 首先，如果硬體有一個64位的計數器，每條指令執行完後自動加1。在每個頁表項里添加一個域，用於存放計數器的值。進程運行，每次訪問頁面的時候，都把計數器的值保存在被訪問頁面的頁表項中。一旦發生缺頁，操作系統檢查頁表中所有的計數器的值以找出最小的一個，那這一頁就是最久未使用的頁面，調出即可。 其次，另外一個矩陣演算法：在一個有n個頁框的機器中，LRU硬體可以維持一個n*n的矩陣，開始時所有位都是0。訪問到第k頁時，硬體把k行的位全設為1，之後再把k列的位置設為0。容易證明，在任意時候，二進制值最小的行即為最久未使用的頁面，當調換頁面時，將其調出。 以上的兩種演算法，無疑都要比純粹的軟體演算法方便且快捷。每次頁面訪問之後的操作——保存計數器值和設置k行k列的值，時間復雜度都是O(1)量級，與純軟體演算法不可同日而語。 那是否軟體演算法就毫無用處？當然不是，硬體演算法有它致命的缺陷，那就是需要硬體的支持才能運行。如果機器上恰好有所需硬體，那無疑是再好不過；反之，若機器上沒有這種硬體條件，我們也只能無奈地拋棄硬體演算法，轉而選取相對麻煩的軟體演算法了。 最後，讓我們來談論一下LRU算 法。首先，這是一個相當好的演算法，它是理想演算法很好的近似。在計算機系統中應用廣泛的局部性原理給它打造了堅實的理論基礎，而在實際運用中，這一演算法也被 證明擁有極高的性能。在大規模的程序運行中，它產生的缺頁中斷次數已很接近理想演算法。或許我們還能找到更好的演算法，但我想，得到的收益與付出的代價恐怕就 不成比例了。當然，LRU演算法的缺點在於實現方法的不足——效率高的硬體演算法通常在大多數機器上無法運行，而軟體演算法明顯有太多的開銷。與之相對的，FIFO演算法，和與LRU相似的NRU演算法，性能盡管不是最好，卻更容易實現。所以，找到一個優秀的演算法來實現LRU，就是一個非常有意義的問題。
希望採納
⑥ 求頁式虛擬存儲技術的原理。
虛擬存儲器是根據程序的邏輯地址轉換來的，也稱線性地址空間。一般每個進程，甚至每個段都有一個，以32位為例，則每個最大可達4G。 而主存目前一般為百M。因此程序中所指的存儲單元並不能都放到主存中，也就是並不是每個程序所用的存儲單元，都有具體的物理的存儲器單元與之對應。 但由於程序的兩個局部性原理，在一個時刻，程序只在一個比較小的范圍內運行。所以我們把程序可能用到的整個存儲空間分成一個個相同大小的頁(按頁管理硬體上容易實現)，只把其中的一些頁放在主存中，而其它的頁則等需要時再建，或放在輔存(磁碟)中。同時建立一個頁表，對應於每一頁，如果該頁在主存中，則頁表記錄它在主存中的地址；如果不在主存中，則在頁表上作不在主存的標記。 這樣，當程序需要調用某個存儲單元的內容時，先根據它的線性地址，算出其所在的頁。查頁表，看是不是在主存中？如果在，則直接存取。如果查到頁表上是不在的標記，那就是一個page fault。要把主存中的某一頁(LRU策略)換到磁碟上，把要訪問的那個單元所在的頁調入主存，再進行存取。 就象一個預計有一萬學生的學校，理論上每個學生都應有一個位子上課(一萬個虛擬位子)，而學校只有一千個(物理)位子。但實際上，學校也不會一萬個人同時上課，只要讓上課的同學有位子(在主存中)，而其它同學只要留下聯系方法能找到就好。為了降低管理的復雜性，我們採用按學號分班(頁)管理。每個班要麼一起上課(主存)，要麼一起呆在寢室(磁碟)。而在學校保留一個動態表(頁表)表明每個班在哪兒(物理地址)上課，或者沒上課(不在主存)。現在假設我們想按學號找一個同學，而且是女同學，只能在教室說話，呵呵。那麼： 先算出來是哪個班的，查動態表，看該班是否在教室。在，直接按位置找到(hit)；不在(page fault)，要先找個不上課的班趕回寢室，把要找女生所在的班調到教室，再按位置找那個同學。 動態表(頁表)的大小＝表項數＊每個表項所需的位數。 表項數＝虛擬班數＝虛擬人數(虛擬地址空間)/每班人數(每頁大小) 每個表項的位數＝Log(教室數)+適當控制位數
麻煩採納，謝謝!