一 頁面與頁表

    分頁存儲管理是將作業(yè)的邏輯地址劃分為一系列同等大小的部分,，稱為頁。并為各頁加以編號,，每個作業(yè)的頁的編號都是從0開始的,。與之類似，把可用的物理內(nèi)存也劃分為同樣大小的連續(xù)的部分,，稱為塊或頁框,。同樣為塊也進行標號，從0#開始,。在為進程分配內(nèi)存空間時,，以頁為單位，每個內(nèi)存中的塊存放一頁用戶作業(yè),。只要內(nèi)存中有足夠多的塊,，這些塊可以相鄰也可以不相鄰，就可以存放整個作業(yè)了,。

    頁面的大小對于內(nèi)存利用和系統(tǒng)開銷來說非常重要,，頁面太大，在作業(yè)的最后一頁必然會剩余較大不能利用的空間--內(nèi)碎片,。頁面太小,，雖然可以減小內(nèi)碎片的大小，但是一個作業(yè)的頁太多,，會使得作業(yè)頁表太長而占用內(nèi)存,，同時系統(tǒng)頻繁地進行頁面轉(zhuǎn)化，加重系統(tǒng)開銷,。因此,，頁面的大小應該適中，通常為512B - 8KB,，windows系統(tǒng)的頁面大小為4KB,。

2 地址結構

   分頁系統(tǒng)中的地址結構由兩部分組成，頁號和頁內(nèi)偏移量,?？梢越忉尀橐粋€二元組（p，w）,，其中p是頁號,，w是頁面p中的偏移量或者相對于p頁開始的位置。下圖（a) 中的地址長度為32位,，其中0 - 9位為頁內(nèi)偏移量,，每頁的大小為2的10次方 = 1k；10 - 31位為頁號,，共計2的22次方 = 4M頁,。在圖（b）中,，地址長度同樣為32位，其中0 - 11位頁內(nèi)偏移量,，每頁的大小為2的12次方 = 4k,；12 - 31位為頁號，共計2的20次方 = 1M頁,，由此可知不同的系統(tǒng)頁的大小是不一樣的,。

                          （a）頁面大小為1KB(2的10次方）


                          （b）頁面大小為4KB(2的12次方)

   對于特定的機器來說，其地址結構是一定的,。若給定邏輯地址A,頁面大小為L,，則頁號p和頁內(nèi)偏移量w分別為

p = INT [A/L]               w = [A]MODL

例如：系統(tǒng)的頁面大小事1K，設A = 3096,，則由上式得出 p =3,，w =24。

3 頁表

    在分頁存儲管理中,，頁的存放可以是連續(xù)的,，也可以是不連續(xù)的，這就增加了邏輯地址到物理地址轉(zhuǎn)換的難度,。如何在內(nèi)存中找到頁所對應的物理塊是地址裝換的關鍵,。為此，系統(tǒng)為每個進程創(chuàng)建了一個頁表,。在進程邏輯地址空間中的每一頁,，依次在頁表中有一個表項，記錄了該頁對應的物理塊號,。如下圖所示

    在配置了頁表之后，通過查找頁表就可以很容易地找到該頁在內(nèi)存中的位置,。頁表具有邏輯地址到物理地址映射的作用,。

    對于頁的保護通常設置一個存取控制字段。當這個字段占一位時,，用于規(guī)定該頁中的內(nèi)容允許寫還是讀,；如果存取控制字段占兩位，那么它可以表示存取控制為讀寫,、只讀和只運行三種,。當進程寫一個只讀頁時，系統(tǒng)就會通過中斷來報錯,。

二 地址變換結構

   為了實現(xiàn)分頁管理邏輯地址到物理地址的轉(zhuǎn)換,，系統(tǒng)中必須設置地址變換機構，用來實現(xiàn)地址映射,。由于頁的大小和塊的大小是一樣的,，當把進程的某一頁放入內(nèi)存時,，該頁內(nèi)陸址的頁偏移量和塊內(nèi)偏移量是一致的，因此地址轉(zhuǎn)換時就不必考慮偏移量,，只考慮邏輯頁號和實際物理號的對應即可,。頁表中存放的就是頁號和其對應的物理塊號，所以地址變換就要借助頁表來完成,。

1 基本地址變換

     地址變換的第一步就是檢索頁表,。為了實現(xiàn)快速的檢索頁表，最好把頁表放在寄存器中,，每一個表項都用一個寄存器,。但是有一個問題，通常計算機中的寄存器都不多,，而頁表可能非常大,，現(xiàn)代計算機的虛擬地址至少是32位的，比如,，頁的大小為4KB,，那么32位的地址空間將有1M個頁面，64位的地址空間則更多,。虛擬空間中的1M個頁面需要1M個表項,。并且，每個進程都有自己的頁表,。因此,，頁表通常存放在內(nèi)存中。在系統(tǒng)中只設置一個頁表寄存器,，其中存放頁表的開始地址和頁表長度。平時進程未執(zhí)行時,，頁表的開始地址和頁表的長度放在PCB中,，當進程運行時，把這兩個數(shù)據(jù)裝入頁表寄存器中,。

    當進程要訪問某個地址中的數(shù)據(jù)時,，地址變換機構首先自動地將地址轉(zhuǎn)換成頁號和頁內(nèi)偏移量，然后根據(jù)頁號來檢索頁表,。在檢索之前要判斷頁號是否大于等于頁表長度,，如果頁號大于等于頁表長度，說明超出了有效地址范圍,，于是產(chǎn)生一個錯誤中斷,。否則，把頁號和頁表項長度相乘得到的結果與頁表開始地址相加，就得到了該頁表項在頁表中的地址,，從而找到對應的物理塊號,，把物理塊號裝入物理地址寄存器中，同時把頁內(nèi)偏移量送入物理地址寄存器對應的塊內(nèi)偏移量中,，由此得到真正的物理地址,。

    由于頁表是放在內(nèi)存中的,，那么一次數(shù)據(jù)訪問需要兩次訪問內(nèi)存,，第一次訪問頁表，找到對應的物理號,，然后與偏移量拼接形成物理地址,；第二次從第一次得到的物理地址結構中訪問數(shù)據(jù)。系統(tǒng)的運行速度一般都受到CPU從內(nèi)存中取得指令和數(shù)據(jù)的速率的限制,，一次數(shù)據(jù)兩次訪問內(nèi)存會使計算機的處理速度降低50%,。如何有效的解決這個問題？

    采取的解決方法是在地址變換結構中增加一個具有并行查找能力的特殊的高速緩沖寄存器,，這種設備稱為轉(zhuǎn)換檢測緩沖區(qū),，又稱為快表，用于存放當前訪問過的頁表項,。此時,，當給出一個有效地址時，地址變換機構首先通過將該頁號p同TLB中的所有表項同時進行比較,，判斷該表是否在其中,，如果發(fā)現(xiàn)可匹配的頁面，則直接取出其頁表項得到物理塊號,，而不必通過頁表,。如果地址變換機構沒有可匹配的項，就進行正常的頁表查詢,。首先從TLB中淘汰一個表項,，然后用新找到的頁表項替換它。這樣,，如果這一頁很快再次被訪問,，那么第二次自然將會命中,。

    因為寄存器的價格原因,，快表的結構不可能很大，通常能存放16 - 512個頁表項,，這對中小型作業(yè)來說,，有可能把全部頁表放入快表中，對于大型作業(yè)，可以將常用的頁表項放入其中,。由于程序的局部性原則,，快表的引入極大改善了系統(tǒng)的效率，數(shù)據(jù)顯示,，從快表中查找到頁表項的概率可以達到90%,。這樣因為訪問頁表而訪問內(nèi)存的次數(shù)就會大大減少，從而降低系統(tǒng)的開銷,。

  2 多級頁表

    現(xiàn)代的計算機都有非常大的邏輯地址空間,，以32位計算機為例，假設頁的大小為4KB,那么一個作業(yè)的頁最多可以達到2的20次方個,，這意味著該作業(yè)的頁表現(xiàn)為2的20次方,。假設一個頁表現(xiàn)占用一個字節(jié)，那么該頁表的大小為2的20次方B,，即需要1MB的內(nèi)存空間,。并且要求者1MB的內(nèi)存空間是連續(xù)的。這顯然是不現(xiàn)實的,，解決這個問題的最好方法是：把頁表頁看成普通的文件,，對它進行離散分配，即對頁表再分頁,，由此形成多級頁表的思想,。

    以二級頁表為例，將頁表進行分頁后,，離散的存放在不同的物理塊中,，這樣，對這些離散分配的頁表再建立頁表,，即二級頁表,。在下圖中，32位的虛地址劃分成10位的外層頁表域,，10位的內(nèi)層頁表域和12位的頁內(nèi)偏移量,。

    

    

    32位邏輯地址空間使用兩級頁表映射到32位物理地址空間，每個頁面大小為4KB,。一級頁表的開始物理地址被存放在頁表基址寄存器中,，一級地址映射使用邏輯地址的最高10位來索引，并產(chǎn)生第二級頁表的物理地址,。下面10位用來索引第二級頁表,，產(chǎn)生出的物理頁的地址和邏輯地址的最低12位相結合以生成物理地址。如果某二級頁表中沒有實際映射,，就可將其刪除并在頂級頁表中標記為不可用,。許多分頁方案在構造的時候都使各級頁表的大小和頁的大小一致,，這樣存儲它們占用的空間可以和進程使用的內(nèi)存頁使用相同的分配方案。

    對于32位的機器,，采用二級頁表是合適的,；但對于64位的機器，采用二級頁表是不合適的,，因此必須采用多級頁表,。

    分頁存儲管理方式雖然可以解決程序和數(shù)據(jù)無需連續(xù)存儲空間的問題，但是這種內(nèi)存管理方式依然要求整個作業(yè)都要裝入內(nèi)存運行,，既沒有解決大作業(yè)小內(nèi)存的問題,，此外，該種管理方式純粹從存儲的角度去考慮,，沒有考慮到程序本身的存儲問題,。

   

  說明總結：單頁時，由于頁表項是連續(xù)的（對應著物理地址空間）,，造成必須占用一整塊連續(xù)地址空間,，是不可取的，所以采用多頁表（主要是二級頁表）,，但造成整個邏輯塊被分散,。 

基本分段分配方式

    分頁存儲管可以實現(xiàn)內(nèi)存利用率的提高，但是分頁的純物理解決方案,，一個邏輯段被離散的放在很多個物理塊中,。很多時候，程序員希望把一個程序按照它的邏輯結構存放在內(nèi)存中,。

    一個程序的邏輯段在程序運行過程中有的大小會發(fā)生變化,，如數(shù)據(jù)段和堆棧；而有的邏輯段的大小在運行過程中不發(fā)生變化,，如代碼段,。在分頁存儲管理方式中，對于隨時動態(tài)增長的段的存儲管理是非常困難的,，一旦斷的增長涉及重新分配物理塊,，那么就涉及頁表的修改等問題。

    一個具有n個過程的程序,，在分頁存儲管理中,，過程被一個一個緊緊地放在一起，中間沒有間隙,，結果是修改一個過程的大小會影響其他進程的起始地址,，進而又需要修改所有調(diào)用被移動進程的進程，以使它們的訪問指向這些過程的新地址,。在一個有數(shù)百個過程的程序中,，這個操作的開銷是相當大的。

   在分頁存儲管理中,，一個邏輯段可能存放在n個物理塊中,，如果幾個程序共享這個邏輯段就需要早每個程序的頁表中添加n項，以便實現(xiàn)地址轉(zhuǎn)換,。這樣勢必會增加頁表的大小,，進而增加系統(tǒng)的開銷，對于邏輯頁的保護也是同樣的道理,。

   針對這些問題,，一個非常通用的辦法是為一個程序提供多個相互獨立的稱為段的地址空間。每個段由一個從0到最大的線性地址序列構成,。各個段的長度可以是0到某個允許的最大值之間的一個值,。不同段的長度可以不同，而且通常也不同,。段的長度在運行期間可以改變,，堆棧段的長度在數(shù)據(jù)被壓入時會增長。在數(shù)據(jù)被彈出時又會減小,。

   因為每個段都是一個獨立的空間,，它們可以獨立地增長或減小而不會影響到其他的段。段是一個邏輯實體,，一個段可能包括一個過程,，一個數(shù)組，一個堆棧,，一組數(shù)值變量,，但一般它不會同時包含多種不同類型的內(nèi)容。分段分配方式實現(xiàn)段長度的擴充,，段的動態(tài)鏈接以及段的保護和共享都比頁式存儲容易實現(xiàn),。

  

1 段表

    在分段存儲管理中，邏輯地址結構是二維的,，即段號和段內(nèi)偏移量,。如下圖所示。在該地址結構中,，允許一個作業(yè)最長有64K個段,，每個段的最大長度為64KB。

  

  

     

    在分段分配方式中,，系統(tǒng)為每個分段分配一個連續(xù)的分區(qū),，進程中的各個段可以離散地裝入內(nèi)存中的不同分區(qū)中。為了實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換,，在系統(tǒng)中為每個進程建立一張段表,。每個段在段表中都占有一個表項,，其中記錄了該段的起始地址和段的地址，如圖所示,，段表可以存放在一組寄存器中,，這樣有助于提高地址轉(zhuǎn)換速度；但更常見的是放在內(nèi)存中,。在配置了段表之后,，執(zhí)行中的進程可以通過查找段表找到每個段所對應的內(nèi)存區(qū)。

     

    

2 采用大小不等的段,，邏輯地址和物理地址之間不再是簡單的對應關系,。考慮一個 n+m 位的地址,，左邊的n位為段號,，右邊的m位為段內(nèi)陸址。當進程進入運行狀態(tài)時,，它的段表地址被裝入到段表寄存器中,。