作業系統 第九章

按需調頁，使用懶惰交換->隻有在需要頁時，才調入記憶體，

交換程式(swapper)對整個程序進行操作

調頁程式(pager)隻是對程序的單個頁進行操作

對标記為無效的通路會産生頁錯誤陷阱

純粹按需調頁(pure demand paging)

一條指令可能通路多個頁的記憶體（一頁用于指令，其它頁用于資料）則一頁可能産生多個頁錯誤， 不好的系統性能。 局部引用（locality of reference）

頁表：有效無效位

次級存儲器 ：用來儲存不在記憶體中的頁， 快速磁盤，交換裝置， 用于交換的這部分磁盤稱為交換空間(swap space)

請求調頁的關鍵要求 ：能夠在頁錯誤後重新執行指令， 在出現頁錯誤時，儲存中斷程序的狀态（寄存器， 條件代碼， 指令計數器）

若頁錯誤出現在指令擷取時， 可以再次擷取指令

若出現在擷取操作數時， 那麼可以再次擷取指令， 再次譯碼指令，然後再次擷取操作數。

9.2.2 按需調頁的性能

p為頁錯誤的機率， p接近于0， 頁錯誤越少， 那麼有效通路時間為 ：

有效通路時間 = (1-p) * ma + p * 頁錯誤時間

按需調頁的另一個重要方面 ： 交換空間 的處理和使用

磁盤I/O到交換空間通常比到檔案系統要快。 因為 交換空間 按大塊來配置設定的， 并不使用檔案查找和間接配置設定方法

如果在程序開始時将整個檔案鏡像複制到交換空間， 并從交換空間執行按頁排程， 那麼有可能獲得更好的調頁效果，另一選擇是開始時從檔案系統中進行按需調頁， 但是當出現頁置換時則将頁寫入交換空間， 這種方法確定隻有所需的頁才從檔案系統中調入， 而以後出現的調頁時從交換空間中讀入的。

9.3 寫時複制

通過采用類似頁面共享的技術， 采用系統調用fork建立程序的開始階段可能不需要按需調頁， 這種技術提供了快速程序建立， 且最小化新建立程序必須配置設定的新頁面的數量

寫時複制(copy-on-write) ： 允許父程序與子程序開始時共享同一頁面，這些頁面标記為寫時複制頁，即如果任何一個程序需要對頁進行寫操作， 那麼就建立一個共享頁的副本。

注意 隻有可能修改的頁才需要标記為寫時複制，不能修改的頁（即包含可執行代碼的頁）可以為父程序和子程序所共享，寫時複制是一種常用技術，為許多作業系統所采用，如Windows XP, Linux和Solaris

采用寫時複制 從哪裡配置設定空閑頁？

許多OS提供 空閑緩沖池 這些空閑頁在程序棧或隊必須擴充時可用于配置設定， 或用于管理寫時複制頁，作業系統通常采用 按需調零(zero-fill-on-demand)的技術以配置設定這些頁。 按需調零頁在需要配置設定之前先填零，清除了以前的内容。

fork()不同于寫時複制的fork() ， fork()會将父程序挂起。子程序使用父程序的位址空間。如果子程序修改父程序位址空間的任何頁， 修改過的頁在父程序重新開機時是可見的。

9.4 頁面置換

過度配置設定（over-allocating）

常用解決方法 ：頁置換(page replacement)

9.4.1 基本頁置換

幀配置設定算法(frame-allocation) 和 頁置換算法(page-replacement algorithm)

如果在記憶體中有多個程序，那麼必須決定為每個程序各配置設定多少幀， 當需要頁置換時，必須選擇要置換的幀

記憶體的引用序列稱為引用串（reference string）

9.4.2 FIFO頁置換

9.4.3 最優置換(optimal page-replacement algorithm)

9.4.4 LRU頁置換

FIFO ：頁調入記憶體的時間

OPT ：頁将來使用的時間

最優置換和LRU置換都沒有Belady異常， 都屬于同一類算法， 稱為 棧算法（stack algorithm）

9.4.5 近似LRU頁置換

1.附加引用位算法

作業系統把每個頁的引用位轉移到其8位位元組的高位，包含着該頁在8個時鐘周期内沒有使用，無符号整數，最小值的頁為LRU置換頁

數量可降為0， 隻有引用位本身， 第二次機會頁置換算法(second-chance page-replacement algorithm)

2. 二次機會算法

基本算法是FIFO置換算法

一個頁如果經常使用以至于引用位總是被設定，不會被置換

實作算法 （有時稱為時鐘算法）： 采用循環隊列

3.增強型二次機會算法

9.4.6 基于計數的頁置換

* 最不經常使用頁置換算法（LFU）

* 最常使用頁置換算法（MFU） ： 理論為具有最小次數的頁可能剛調入，還未使用

9.4.7 頁緩沖算法

系統保留一個空閑幀緩沖池

在犧牲幀寫出之前，所需要的頁就從緩沖池中讀到空閑記憶體，當在犧牲幀以後寫出時，它再加入到空閑幀池

9.4.8 應用程式與頁置換

有的作業系統允許特殊程式将磁盤作為邏輯塊數組使用，而不需要通過檔案系統的資料結構，這種數組有時稱為生磁盤(raw disk), 而對數組的I/O則稱為生I/O。

雖然有些應用程式使用其特有的磁盤存儲服務更為高效，但是絕大多數程式使用通用檔案系統服務會更好

9.5 幀配置設定

若采用純按需調頁

9.6 系統颠簸

局部置換算法(local replacement algorithm) （或 優先置換算法(priority replacement algorithm)）能限制系統颠簸

局部置換 ： 一個程序開始颠簸，那麼它不能從其他程序拿到幀，且不能使後者也颠簸

如果程序颠簸，那麼絕大多數時間内也會排隊來等待調頁裝置，由于調頁裝置的更長的平均隊列，頁錯誤的平均等待時間也會增加。是以，即使對沒有颠簸的程序， 其有效通路時間也會增加。

局部模型(locality model)

9.6.2 工作集合模型

工作集合模型（working-set model）是基于局部性假設的

工作集合視窗（working-set window）

9.7 記憶體映射檔案

9.7.3 記憶體映射I／O

當通過記憶體映射序列槽發送一長串位元組時，CPU寫一個資料位元組到資料寄存器，并設定控制寄存器的一個位以表示有位元組可用。

裝置讀取位元組，并清除控制寄存器的位以表示可以接收下一個位元組。

接着，CPU可傳輸下一個位元組，如果CPU采用輪詢方式來檢測控制位，這種操作稱為程式I/O(programmed I/O, PIO)

如果采用接收裝置就緒後可發下一個位元組的中斷的方式，稱為中斷驅動(interrupt driven)