記憶體管理之虛拟頁式配置設定

       分頁記憶體配置設定和分段記憶體配置設定可以解決程式在記憶體中離散存放的問題，但是，這個兩種方式都要求程式将整個裝入記憶體。如果程式比記憶體大，那麼分頁和分段都無法解決這個問題。其實一個程式在短時間内的執行可能局限于某小段程式範圍内，這樣把程式全部調入記憶體早成空間浪費，可以隻裝入一部分，程序需要的其他資料存放在外存，當需要的時候調入記憶體。這樣做的好處：記憶體中可以儲存更多的程序；程序可以比主存大。

1.虛拟存儲器

       虛拟存儲是指請求調入功能和置換功能。給使用者的感覺是整個程序被調入了記憶體，其實是隻有一部分，其餘部分在外村。虛存就是記憶體和外存之和。虛拟存儲需要解決如下幾個問題：

     （1）位址映射：一個頁面可能多次被調入和調出記憶體，每次在記憶體的位址不同，這就需要将邏輯位址轉換為相應的實體位址，并且是動态的。

     （2）配置設定政策：為了通路虛存中的任何部分，待通路的資料必須駐留在記憶體。事先要提供一個種存儲器配置設定政策，以确定要調入的部分裝入到存儲器的哪個位置。

     （3）置換政策：當系統記憶體空間不夠時，系統必須通過換出頁面來找到空間。系統可以将程序某些不用的空間換出記憶體，也可以将其他程序頁面換出，如何取舍。

     （4）裝載控制：靜态裝載将程序的所有虛拟存儲器裝載到記憶體。動态裝載隻是用的時候才裝入。

2.請求分頁

       請求分頁存儲管理方式也叫虛拟頁式配置設定，是虛拟器存儲器的一種實作方法。所謂請求分頁是指在基本分頁上的基礎上增加請求調頁和頁面置換功能的一種存儲配置設定政策。純分頁系統中，程序的所有頁面都在實體記憶體中，而虛拟頁式配置設定，一個程序隻有部分頁在記憶體中，一部分在外存中。一旦程序通路的頁不在記憶體，對程序來說就意味着缺頁，就通過缺頁中斷向作業系統發出一個請求，請求把記憶體中位于外存的頁調入記憶體。

     請求分頁的硬體支援：頁表需要加入幾個标志項，缺頁中斷機構和位址變換機構。

      記憶體配置設定政策：配置設定給一個程序的存儲量越小，記憶體中容納的程序數越多，但是程序缺頁異常也就越頻繁。同時給程序配置設定一定數量的實體塊後，由于局部原理，給該程序配置設定更多的頁實體塊對該程序的缺頁率無影響了。三種配置設定政策：

     （1）固定配置設定政策：配置設定給程序的實體塊在運作過程中不變，當程序發生缺頁時，從該程序中占用的幾個實體塊找到一頁替換出去。

     （2）可變局部配置設定政策：記憶體中每個程序配置設定了一定數量的實體塊。但是系統中還有一個空閑實體塊。程序發生缺頁時，先檢查空閑實體塊，如果有空的，直接配置設定給程序。沒有空的，隻能從程序自己的空間中選一頁置換出去。

     （3）可變配置設定全局置換：一旦程序發生缺頁，從整個記憶體中選擇一頁置換出去。

       在采用固定配置設定時，可以按照程序數平均配置設定給每個程序等份的空間；可以按照程序大小比例配置設定空間；考慮程序優先級配置設定。

3.頁面轉換算法

      當頁不在記憶體中，系統要選一頁移到外存中，下面介紹幾個固定配置設定局部置換的記憶體配置設定政策：

     （1）最優頁面置換算法（OPT）:缺頁時，目前記憶體中的這幾頁中，有的頁再也不用了，那麼把該頁置換出是最好的。如果目前記憶體中的幾頁都要使用，選擇一個最後用到的頁把他轉換出去。

範例：記憶體為某程序配置設定三個實體塊（不能變了），程序頁面走向如下：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

        7：發生缺頁中斷，調入記憶體；  0：發生缺頁中斷，調入記憶體；1：發生缺頁中斷，調入記憶體；2：需要從7,0,1中選擇一個置換，頁面7是第18個要通路的頁面，0是第5個要通路的頁面，1是第14個通路的頁面，是以選擇7置換，即記憶體總還剩2 0 1。依次類推。。。

注意：開始記憶體是空的，是以沒有頁面，這時也算缺頁異常。

      （2）先進先出算法：總是選擇目前系統中最早進入記憶體的那一頁置換出去。

       7：發生缺頁中斷，調入記憶體；  0：發生缺頁中斷，調入記憶體；1：發生缺頁中斷，調入記憶體；2：淘汰7，即記憶體中0 1 2；2：已經在記憶體；0：在記憶體；3：0是最早進入記憶體的，雖然前一次是0，但是因為記憶體中，已經有了是以不算新進入的。後面依次了退。。

        FIFO算法有時候會産生Belady現象，即配置設定給程序空間增大，反而缺頁率增加了，其他算法沒有。

     （3）最近很少使用置換算法（LRU）：總是選擇目前頁面中沒有被使用時間最久的那一頁，即使用最少的那一頁，将它換出出去。

最終的序列：（7 0 1）（2 1 0）（0 2 1）（3 0 2）（0 3 2）（4 0 3）（2 4 0）（3 2 4）（0 3 2）（3 0 2）。。。

     （4）clock算法：針對FIFO性能差，而LRU實作困難。Clock算法需要給每個實體塊增加一個附加位，稱為使用位。當某頁裝入記憶體時，使用位設為1，實體塊被使用時，也被設為1。clock算法将頁面看作一個循環緩沖區，并且有一個指針與之關聯。當需要進行置換的時候，指針掃描，如果指針所指的頁面為0，則被置換。如果不為0，将其置0，繼續掃描下一塊，直到找到一個使用位為0的塊。如果所有位都是1，則掃描整個系統，回到指針開始的位置替換該頁。所有的使用位為0，則指針指向的實體塊被替換。

       Unix的clock算法：unix不是在缺頁的時候才選擇置換，而是一次缺頁總是使用目前空閑實體塊表中的一塊，如果沒有空閑塊，則程序會被阻塞，直到有空閑塊。unix中有一個頁面守護程序周期性醒來，然後選擇一些使用位為0的頁面置換出去。

     （5）改進時鐘算法：時鐘算法隻考慮了每一頁的使用頻率，并沒有考慮該頁是否被修改。如果系統中的某一頁被換出，而且它被修改了，那麼需要把該頁重新寫回外村（沒有被修改的時候，不要寫到外存，直接替換）。為了區分是否被修改，額外添加一個修改位w。新頁面裝入記憶體時，w=0，修改後，w=1。具有兩個附加位的實體塊中的頁具有以下四種情況：

              a.最近未被通路過，未被修改過（u=0，w=0）;//最适合換出的頁面

              b.最近未被通路過，被修改過（u=0，w=1）;//上面的沒有選擇這種頁面

              c.最近被通路過，未被修改過（u=1，w=0）;//上面的沒有選擇這種頁面

              c.最近被通路過，被修改過（u=1，w=1）;//上面的沒有選擇這種頁面

​