基本介紹
- 中文名：基本分頁存儲管理方式
- 基本單位：頁表
頁面與頁表,頁面,地址結構,頁表,地址變換機構,基本的地址變換機構,具有快表的地址變換機構,兩級和多級頁表,兩級,多級頁表,其他存儲管理方式,分段式存儲管理方式,段頁式存儲管理方式,
頁面與頁表
頁面
1) 頁面和物理塊
分頁存儲管理是將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，並為各頁加以編號，從0開始，如第0頁、第1頁等。相應地，也把記憶體空間分成與頁面相同大小的若干個存儲塊，稱為(物理)塊或頁框(frame)，也同樣為它們加以編號，如0#塊、1#塊等等。在為進程分配記憶體時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由於進程的最後一頁經常裝不滿一塊而形成了不可利用的碎片，稱之為“頁內碎片”。
2) 頁面大小
在分頁系統中的頁面其大小應適中。頁面若太小，一方面雖然可使記憶體碎片減小，從而減少了記憶體碎片的總空間，有利於提高記憶體利用率，但另一方面也會使每個進程占用較多的頁面，從而導致進程的頁表過長，占用大量記憶體；此外，還會降低頁面換進換出的效率。然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進換出的速度，但卻又會使頁內碎片增大。因此，頁面的大小應選擇適中，且頁面大小應是2的冪，通常為512 B～8 KB。
地址結構
分頁地址中的地址結構如下：
其中，INT是整除函式，MOD是取余函式。例如，其系統的頁面大小為1 KB，設A = 2170 B，則由上式可以求得P = 2，d = 122。
頁表
在分頁系統中，允許將進程的各個頁離散地存儲在記憶體不同的物理塊中，但系統應能保證進程的正確運行，即能在記憶體中找到每個頁面所對應的物理塊。為此，系統又為每個進程建立了一張頁面映像表，簡稱頁表。在進程地址空間內的所有頁(0～n)，依次在頁表中有一頁表項，其中記錄了相應頁在記憶體中對應的物理塊號，見右圖的中間部分。在配置了頁表後，進程執行時，通過查找該表，即可找到每頁在記憶體中的物理塊號。可見，頁表的作用是實現從頁號到物理塊號的地址映射。
地址變換機構
基本的地址變換機構
頁表的功能可以由一組專門的暫存器來實現。一個頁表項用一個暫存器。由於暫存器具有較高的訪問速度，因而有利於提高地址變換的速度；但由於暫存器成本較高，且大多數現代計算機的頁表又可能很大，使頁表項的總數可達幾千甚至幾十萬個，顯然這些頁表項不可能都用暫存器來實現，因此，頁表大多駐留在記憶體中。在系統中只設定一個頁表暫存器PTR(Page-Table Register)，在其中存放頁表在記憶體的始址和頁表的長度。平時，進程未執行時，頁表的始址和頁表長度存放在本進程的PCB中。當調度程式調度到某進程時，才將這兩個數據裝入頁表暫存器中。因此，在單處理機環境下，雖然系統中可以運行多個進程，但只需一個頁表暫存器。
當進程要訪問某個邏輯地址中的數據時，分頁地址變換機構會自動地將有效地址(相對地址)分為頁號頁內地址兩部分，再以頁號為索引去檢索頁表。查找操作由硬體執行。在執行檢索之前，先將頁號與頁表長度進行比較，如果頁號大於或等於頁表長度，則表示本次所訪問的地址已超越進程的地址空間。於是，這一錯誤將被系統發現並產生一地址越界中斷。若未出現越界錯誤，則將頁表始址與頁號和頁表項長度的乘積相加，便得到該表項在頁表中的位置，於是可從中得到該頁的物理塊號，將之裝入物理地址暫存器中。與此同時，再將有效地址暫存器中的頁內地址送入物理地址暫存器的塊內地址欄位中。這樣便完成了從邏輯地址到物理地址的變換。右圖示出了分頁系統的地址變換機構。
具有快表的地址變換機構
由於頁表是存放在記憶體中的，這使CPU在每存取一個數據時，都要兩次訪問記憶體。第一次是訪問記憶體中的頁表，從中找到指定頁的物理塊號，再將塊號與頁內偏移量W拼接，以形成物理地址。第二次訪問記憶體時，才是從第一次所得地址中獲得所需數據(或向此地址中寫入數據)。因此，採用這種方式將使計算機的處理速度降低近1/2。可見，以此高昂代價來換取存儲器空間利用率的提高，是得不償失的。
為了提高地址變換速度，可在地址變換機構中增設一個具有並行查尋能力的特殊高速緩衝暫存器，又稱為“聯想暫存器”(Associative Memory)，或稱為“快表”，在IBM系統中又取名為TLB(Translation Lookaside Buffer)，用以存放當前訪問的那些頁表項。此時的地址變換過程是：在CPU給出有效地址後，由地址變換機構自動地將頁號P送入高速緩衝暫存器，並將此頁號與高速快取中的所有頁號進行比較，若其中有與此相匹配的頁號，便表示所要訪問的頁表項在快表中。於是，可直接從快表中讀出該頁所對應的物理塊號，並送到物理地址暫存器中。如在塊表中未找到對應的頁表項，則還須再訪問記憶體中的頁表，找到後，把從頁表項中讀出的物理塊號送地址暫存器；同時，再將此頁表項存入快表的一個暫存器單元中，亦即，重新修改快表。但如果聯想暫存器已滿，則OS必須找到一個老的且已被認為不再需要的頁表項，將它換出。右圖示出了具有快表的地址變換機構。
兩級和多級頁表
兩級
現代的大多數計算機系統，都支持非常大的邏輯地址空間(2^32～2^64)。在這樣的環境下，頁表就變得非常大，要占用相當大的記憶體空間。例如，對於一個具有32位邏輯地址空間的分頁系統，規定頁面大小為4 KB即2^12 B，則在每個進程頁表中的頁表項可達1兆個之多。又因為每個頁表項占用四個位元組，故每個進程僅僅其頁表就要占用4 MB的記憶體空間，而且還要求是連續的。顯然這是不現實的，我們可以採用下述兩個方法來解決這一問題：
(1) 採用離散分配方式來解決難以找到一塊連續的大記憶體空間的問題；
兩級頁表(Two-Level Page Table)
對於要求連續的記憶體空間來存放頁表的問題，可利用將頁表進行分頁，並離散地將各個頁面分別存放在不同的物理塊中的辦法來加以解決，同樣也要為離散分配的頁表再建立一張頁表，稱為外層頁表(Outer Page Table)，在每個頁表項中記錄了頁表頁面的物理塊號。下面我們仍以前面的32位邏輯地址空間為例來說明。當頁面大小為 4 KB時(12位)，若採用一級頁表結構，應具有20位的頁號，即頁表項應有1兆個；在採用兩級頁表結構時，再對頁表進行分頁，使每頁中包含2^10 (即1024)個頁表項，最多允許有2^10個頁表分頁；或者說，外層頁表中的外層頁內地址P2為10位，外層頁號P1也為10位。此時的邏輯地址結構可描述如下：
由右圖可以看出，在頁表的每個表項中存放的是進程的某頁在記憶體中的物理塊號，如第0#頁存放在1#物理塊中；1#頁存放在4#物理塊中。而在外層頁表的每個頁表項中，所存放的是某頁表分頁的首址，如第0#頁表是存放在第1011#物理塊中。我們可以利用外層頁表和頁表這兩級頁表，來實現從進程的邏輯地址到記憶體中物理地址間的變換。
為了地址變換實現上的方便起見，在地址變換機構中同樣需要增設一個外層頁表暫存器，用於存放外層頁表的始址，並利用邏輯地址中的外層頁號，作為外層頁表的索引，從中找到指定頁表分頁的始址，再利用P2作為指定頁表分頁的索引，找到指定的頁表項，其中即含有該頁在記憶體的物理塊號，用該塊號和頁內地址d即可構成訪問的記憶體物理地址。右圖示出了兩級頁表時的地址變換機構。
多級頁表
對於32位的機器，採用兩級頁表結構是合適的；但對於64位的機器，採用兩級頁表是否仍可適用的問題，須做以下簡單分析。如果頁面大小仍採用4 KB即2^12 B，那么還剩下52位，假定仍按物理塊的大小(2^12位)來劃分頁表，則將餘下的42位用於外層頁號。此時在外層頁表中可能有4096 G個頁表項，要占用16 384 GB的連續記憶體空間。這樣的結果顯然是不能令人接受的，因此必須採用多級頁表，將外層頁表再進行分頁，也就是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關係。
對於64位的計算機，如果要求它能支持2^64 B(= 1 844 744 TB)規模的物理存儲空間，則即使是採用三級頁表結構也是難以辦到的；而在當前的實際套用中也無此必要。故在近兩年推出的64位OS中，把可直接定址的存儲器空間減少為45位長度(即2^45)左右，這樣便可利用三級頁表結構來實現分頁存儲管理。
其他存儲管理方式
分段式存儲管理方式
如果說推動存儲管理方式是從固定分區到動態分區分配，進而又發展到分頁存儲管理方式的主要動力，提高了記憶體利用率。那么，引入分段存儲管理方式的目的，則主要是為了滿足用戶（程式設計師）在編程和使用上多方面的要求，其中有些要求是其它幾種存儲管理方式所難以滿足的。因此，這種存儲管理方式已成為當今所有存儲管理方式的基礎。
段頁式存儲管理方式
在段頁式系統中，為了便於實現地址變換，須配置一個段表暫存器，其中存放段表始址和段表長TL。進行地址變換時，首先利用段號S，將它與段表長TL進行比較。若S<TL，表示未越界，於是利用段表始址和段號來求出該段所對應的段表項在段表中的位置，從中得到該段的頁表始址，並利用邏輯地址中的段內頁號P來獲得對應頁的頁表項位置，從中讀出該頁所在的物理塊號b，再利用塊號b和頁內地址來構成物理地址。右圖示出了段頁式系統中的地址變換機構。在段頁式系統中，為了獲得一條指令或數據，須三次訪問記憶體。第一次訪問是訪問記憶體中的段表，從中取得頁表始址；第二次訪問是訪問記憶體中的頁表，從中取出該頁所在的物理塊號，並將該塊號與頁內地址一起形成指令或數據的物理地址；第三次訪問才是真正從第二次訪問所得的地址中，取出指令或數據。
