C語言中文網
首頁 > 編程筆記 > 操作系統筆記 閱讀:369

請求調頁(請求頁面調度)原理及性能詳解

想一想,如何從磁盤加載可執行程序到內存。

一種選擇是在程序執行時將整個程序加載到物理內存,這種方法的問題是最初可能不需要整個程序都處于內存。假設程序開始時帶有一組用戶可選的選項。加載整個程序會導致所有選項的執行代碼都加載到內存中,而不管這些選項是否最終使用。

另一種策略是僅在需要時才加載頁面。這種技術被稱為請求調頁,常常用于虛擬內存系統。對于請求調頁的虛擬內存,頁面只有在程序執行期間被請求時才被加載。因此,從未訪問的那些頁從不加載到物理內存中。

請求調頁系統類似于具有交換的分頁系統,如圖 1 所示,這里進程駐留在外存上(通常為磁盤)。當進程需要執行時,它被交換到內存中。不過,不是將整個進程交換到內存中,而是采用惰性交換器。惰性交換器除非需要某個頁面,否則從不將它交換到內存中。


圖 1 從分頁內存到連續磁盤空間的傳輸

在請求調頁的上下文中,使用術語“交換器”在技術上是不正確的。交換器操縱整個進程,而調頁程序只涉及進程的頁面。因此,在討論請求調頁時,我們使用“調頁程序”,而不是“交換器”。

請求調頁的基本概念

當換入進程時,調頁程序會猜測在該進程被再次換出之前會用到哪些頁。調頁程序不是調入整個進程,而是把那些要使用的頁調入內存。這樣,調頁程序就避免了讀入那些不使用的頁,也減少了交換時間和所需的物理內存空間。

使用這種方案需要一定形式的硬件支持,以區分內存的頁面和磁盤的頁面。前面所述的有效-無效位方案可用于這一目的。然而此時,當該位被設置為“有效”時,相關聯的頁面是合法的,并且在內存中。當該位被設置為“無效”時,頁面無效(即不在進程的邏輯地址空間中),或有效但只在磁盤上。對于已調入內存的頁面,它的頁表條目是照常設置的;但是對于不在內存的頁面,它的頁表條目可簡單標記為無效,或者包含磁盤上的頁面地址。這種情況如圖 2 所示。


圖 2 有些頁面不在內存的頁表

注意,如果進程從不試圖訪問標記為無效的頁面,那么并沒有什么影響。因此,如果猜測正確并且只調入所有實際需要的頁面,那么進程就如同所有頁面都已調入內存一樣正常運行。當進程執行和訪問那些內存駐留的頁面時,執行會正常進行。

但是,如果進程試圖訪問那些尚未調入內存中的頁面時,情況會如何呢?對標記為無效的頁面訪問會產生缺頁錯誤。分頁硬件在通過頁表轉換地址時會注意到無效位被設置,從而陷入操作系統。這種陷阱是由于操作系統未能將所需的頁面調入內存引起的。


圖 3 處理缺頁錯誤的步驟

處理這種缺頁錯誤的程序很簡單(圖 3):
  1. 檢查這個進程的內部表(通常與 PCB(進程控制塊)一起保存),以確定該引用是有效的還是無效的內存訪問。
  2. 如果引用無效,那么終止進程。如果引用有效但是尚未調入頁面,那么現在就應調入。
  3. 找到一個空閑幀(例如,從空閑幀鏈表上得到一個)。
  4. 調度一個磁盤操作,以將所需頁面讀到剛分配的幀。
  5. 當磁盤讀取完成時,修改進程的內部表和頁表,以指示該頁現在處于內存中。
  6. 重新啟動被陷阱中斷的指令。該進程現在能訪問所需的頁面,就好像它總是在內存中。

在極端情況下,我們可以開始執行一個沒有內存頁面的進程。當操作系統將指令指針設置為進程的第一條指令時,由于它所在的頁面并不在內存中,進程立即出現缺頁錯誤。當該頁面調入內存后,進程繼續執行;根據需要發生缺頁錯誤,直到所需每個頁面都在內存中。這時,它可以在沒有更多缺頁錯誤的情況下執行。這種方案為純請求調頁,即只有在需要時才將頁面調入內存。

理論上,有些程序的每次指令執行可以訪問多個新的頁面(一個用于指令,其他的多個用于數據),從而每條指令可能引起多個缺頁錯誤。這種情況會導致不可接受的系統性能。幸運的是,對運行進程的分析表明,這種行為是極不可能的。如前面所述,程序具有局部引用,這使得請求調頁具有較為合理的性能。

支持請求調頁的硬件與分頁和交換的硬件相同:
請求調頁的關鍵要求是在缺頁錯誤后重新啟動任何指令的能力。因為當發生缺頁錯誤時,保存了被中斷的進程狀態(寄存器、條件代碼、指令計數器),所以應能夠在完全相同的位置和狀態下,重新啟動進程,只不過現在所需的頁面已在內存中并且是可以訪問的。在大多數情況下,這個要求很容易滿足。任何內存引用都可能引起缺頁錯誤。如果在獲取指令時出現了缺頁錯誤,那么可以再次獲取指令。如果在獲取操作數時出現了缺頁錯誤,那么可以再次獲取指令、再次譯碼指令,然后再次獲取操作數。

作為最壞情況的示例,假設一個具有三個地址的指令 ADD,它可將 A 和 B 的內容相加,并將結果存入 C。這個指令的執行步驟是:
  1. 獲取并解碼指令(ADD);
  2. 獲取 A;
  3. 獲取 B;
  4. 將 A 和 B 相加;
  5. 將結果存入 C 中;

如果在嘗試保存到 C 時出現缺頁錯誤(因為 C 所在的頁面并不在內存中),那么應獲取所需的頁面,將其調入,更正頁表,然后重新啟動指令。重新啟動需要再次獲取指令,再次對指令譯碼,再次獲取兩個操作數,然后相加。然而,沒有多少重復工作(少于一條完整指令),并且僅當發生缺頁錯誤時才需要重復。

當一條指令可以修改多個不同的位置時,就會出現重要困難。例如,IBM System 360/370 的 MVC(移動字符)指令,可以從一個位置移動多達 256 字節到另一個位置(可能重疊)。如果任何一塊(源或目的)跨越頁邊界,那么在執行了部分移動時可能會出現缺頁錯誤。此外,如果源塊和目的塊有重疊,源塊可能已被修改;在這種情況下,我們不能簡單重新啟動指令。

這個問題可有兩種不同的解決方法:
這絕不是通過向現有架構添加分頁以允許請求調頁而產生的唯一的架構問題,不過它已說明了所涉及的一些困難。分頁是在計算機系統的 CPU 和內存之間添加的,它應該對用戶進程完全透明。

因此,人們經常假定分頁能夠添加到任何系統。這個假定對于非請求調頁環境來說是正確的,因為在這種環境中,缺頁錯誤就代表了一個致命錯誤。然而,對于缺頁錯誤僅意味著另外一個額外頁面需要調入內存,然后進程重新運行的情況來說,這個假定就是不正確的。

請求調頁的性能

請求調頁可以顯著影響計算機系統的性能。為了說明起見,下面計算一下請求調頁內存的有效訪問時間。

對大多數計算機系統而言,內存訪問時間(用 ma 表示)的范圍為 10?200ns。只要沒有出現缺頁錯誤,有效訪問時間就等于內存訪問時間。然而,如果出現缺頁錯誤,那么就應先從磁盤中讀入相關頁面,再訪問所需要的字。

設 p 為缺頁錯誤的概率(0≤p≤1)。希望 p 接近于 0,即缺頁錯誤很少。那么有效訪問時間為:

有效訪問時間=(1 - p) X ma + p X 缺頁錯誤時間

為了計算有效訪問時間,應知道需要多少時間來處理缺頁錯誤。缺頁錯誤導致發生以下一組動作:
  1. 陷入操作系統。
  2. 保存用戶寄存器和進程狀態。
  3. 確定中斷是否為缺頁錯誤。
  4. 檢查頁面引用是否合法,并確定頁面的磁盤位置。
  5. 從磁盤讀入頁面到空閑幀:
    • 在該磁盤隊列中等待,直到讀請求被處理。
    • 等待磁盤的尋道或延遲時間。
    • 開始傳輸磁盤頁面到空閑幀。
  6. 在等待時,將 CPU 分配給其他用戶(CPU 調度,可選)。
  7. 收到來自 I/O 子系統的中斷(I/O 完成)。
  8. 保存其他用戶的寄存器和進程狀態(如果執行了第 6 步)。
  9. 確認中斷是來自上述磁盤的。
  10. 修正頁表和其他表,以表示所需頁面現在已在內存中。
  11. 等待 CPU 再次分配給本進程。
  12. 恢復用戶寄存器、進程狀態和新頁表,再重新執行中斷的指令。

以上步驟并不是在所有情況下都是必要的。例如,假設第 6 步在執行 I/O 時將 CPU 分配給另一進程。這種安排允許多道程序以提高 CPU 使用率,但是在執行完 I/O 時也需要額外時間來重新啟動缺頁錯誤的處理程序。在任何情況下,缺頁錯誤的處理時間有三個主要組成部分:
  1. 處理缺頁錯誤中斷。
  2. 讀入頁面。
  3. 重新啟動進程。

第一個和第三個任務通過仔細編碼可以減少到幾百條指令。這些任務每次可能需要 1?100ms。然而,頁面切換時間可能接近 8ms(典型硬盤的平均延遲為 3ms,尋道時間為 5ms,傳輸時間為 0.05ms。因此,總的調頁時間約為 8ms,包括硬件的和軟件的時間)。而且,要注意,這里只考慮了設備處理時間。如果有一隊列的進程正在等待設備,那么應加上等待設備的時間,以便等待調頁設備空閑來處理請求,從而增加了更多的交換時間。

如果缺頁錯誤處理的平均時間為 8ms,內存訪問時間為 200ns,那么有效內存訪問時間(以 ns 計)為:

有效訪問時間=(1-p) X (200) + p(8ms)=(1 -p)X 200 + p X 8 000 000 = 200 + 7 999 800 X p

這樣,我們看到有效訪問時間與缺頁錯誤率成正比。如果每 1000 次訪問中有一次缺頁錯誤,那么有效訪問時間為 8.2μs。由于請求分頁,計算機會減速 40 倍。如果我們希望性能下降小于 10%,則需要將缺頁錯誤的概率保持在以下級別:

220 >200 + 7 999 800 X p
20 > 7 999 800 X p
p < 0.000 002 5

也就是說,為了因缺頁錯誤而產生的性能降低可以接受,那么只能允許每 399 990 次訪問中出現不到一次的缺頁錯誤。總之,對于請求調頁,降低缺頁錯誤率是極為重要的。否則,會增加有效訪問時間,從而極大地減緩了進程的執行速度。

請求調頁的另一個方面是交換空間的處理和整體使用。交換空間的磁盤 I/O 通常要快于文件系統的。交換空間的文件系統更快,因為它是按更大的塊來分配的,且不采用文件查找和間接分配方法。

因此,系統可以在進程啟動時將整個文件映像復制到交換空間中,然后從交換空間執行請求調頁,從而獲得更好的分頁吞吐量。另一選擇是,開始時從文件系統進行請求調頁,但是在置換頁面時則將頁面寫入交換空間。這種方法確保只從文件系統讀取所需的頁面,而所有后續調頁都是從交換空間完成的。

對于二進制文件的請求調頁,有些系統試圖限制交換空間的用量。這些文件的請求調頁是從文件系統中直接讀取的。然而,當需要頁面置換時,這些幀可以簡單地覆蓋(因為它們從未被修改),當再次需要時,從文件系統中再次直接讀入。

采用這種方法,文件系統本身用作后備存儲。然而,對于與文件無關的頁面還是需要使用交換空間(稱為匿名內存),這些頁面包括進程的堆棧和堆。這種方法似乎是一個很好的折中,并用于多個操作系統,如 Solaris 與 BSD UNIX。

移動操作系統通常不支持交換。當內存變得有限時,這些系統從文件系統請求調頁,并從應用程序中回收只讀頁面(例如代碼)。如果以后需要,可以從文件系統中請求這些數據。對于 iOS,不會從應用程序中回收匿名內存頁面,除非應用程序終止或顯式釋放內存。

所有教程

優秀文章

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo