虚拟记忆体(Virtual

1、Silberschatz and Galvin1999 9.1Operating System Concepts虛擬記憶體虛擬記憶體（Virtual Memory）Background（背景）背景）Demand Paging（需求分頁）需求分頁）Performance of Demand Paging （需求分頁的效能）需求分頁的效能）Page Replacement（分頁替換）分頁替換）Page-Replacement Algorithms（分頁替換的法則）分頁替換的法則）Allocation of Frames（欄的配置法則）欄的配置法則） Thrashing（輾轉現象）輾轉現象）Othe

2、r Considerations（其他考量）其他考量）Demand Segmenation（需求分段）需求分段）Silberschatz and Galvin1999 9.2Operating System Concepts背景背景（Background）虛擬記憶體（虛擬記憶體（Virtual memoryVirtual memory） 將邏輯記憶體（將邏輯記憶體（logical memorylogical memory）及實際記憶體（及實際記憶體（ physical memory physical memory）分開。分開。只有正在執行的程式才放在記憶體內只有正在執行的程式才放在記憶體內。邏

3、輯位址空間（邏輯位址空間（Logical address spaceLogical address space）可以比實際位址空間（可以比實際位址空間（physical address spacephysical address space）還大。還大。需要允許分頁資料的置換（進需要允許分頁資料的置換（進/ /出）。出）。虛擬記憶體的實施虛擬記憶體的實施需求分頁（需求分頁（Demand pagingDemand paging） 需求分段（需求分段（Demand segmentationDemand segmentation）Silberschatz and Galvin1999 9.3Oper

4、ating System Concepts虛擬記憶體虛擬記憶體vsvs實體記憶體實體記憶體page 0page 0page 1page 1page 2page 2page npage n：虛擬記憶體虛擬記憶體記憶體對映記憶體對映實體記憶體實體記憶體輔助記憶體輔助記憶體Silberschatz and Galvin1999 9.4Operating System ConceptsDemand Paging有需要的時候才將分頁載入記憶體的好處有需要的時候才將分頁載入記憶體的好處IO IO 減少減少記憶體需求減少記憶體需求減少 更多的程式可以同時執行更多的程式可以同時執行執行速度更快，回應時間更短執

5、行速度更快，回應時間更短Silberschatz and Galvin1999 9.5Operating System ConceptsValid-InvalidValid-Invalid位元位元每一個分頁會有一個每一個分頁會有一個 validinvalid validinvalid 位元位元(1 (1 分頁在記憶體中分頁在記憶體中, 0, 0 分頁不在記憶體中分頁不在記憶體中) )一剛開始，所有分頁的一剛開始，所有分頁的 validinvalid validinvalid位元的初值都設為位元的初值都設為0 0存取到存取到validinvalidvalidinvalid位元為位元為0 0的分頁

6、時會發生的分頁時會發生分頁錯誤分頁錯誤（PAGE FAULTPAGE FAULT）1 11 11 11 10 00 00 0 Frame #Frame # valid-invalid bitvalid-invalid bit分頁表格分頁表格Silberschatz and Galvin1999 9.6Operating System Concepts分頁錯誤的處理步驟分頁錯誤的處理步驟load M作業系統作業系統i輔助記憶體輔助記憶體空白欄空白欄重新重新啟動啟動指令指令重新設定重新設定分頁表分頁表插斷插斷某頁在輔助記憶體某頁在輔助記憶體載入想要的載入想要的那一頁資料那一頁資料1參用參用6234

7、5分頁表分頁表Silberschatz and Galvin1999 9.7Operating System ConceptsPerformance of Demand Paging假設分頁錯誤率假設分頁錯誤率(Page Fault Rate)為為 p, 0 p 1.0 若若 p = 0，都沒有都沒有分頁錯誤分頁錯誤 若若 p = 1, 每次參考都產生每次參考都產生分頁錯誤分頁錯誤有效存取時間（有效存取時間（Effective Access Time ; EAT) EAT = (1 p) x 記憶體存取記憶體存取 + p ( 插斷的額外負擔插斷的額外負擔 + 分頁置換分頁置換-出出 +分頁置換

8、分頁置換-入入 +重新啟動的額外負擔重新啟動的額外負擔 )Silberschatz and Galvin1999 9.8Operating System ConceptsDemand Paging Example記憶體存取記憶體存取 = 100 ns,（100*10-9)插斷的額外負擔插斷的額外負擔+重新啟動的額外負擔重新啟動的額外負擔: 1100微秒（微秒（10-6)(若再加排隊等待時間，則共約若再加排隊等待時間，則共約 1毫秒）毫秒）置換時間：置換時間：24毫秒（潛伏期：毫秒（潛伏期：8，搜尋時間，搜尋時間:15，轉移，轉移:1)EAT = (1 p) x 100 + p *(25x106

9、) =100 + 24999900 * p如果希望，因需求分頁而造成的效能減緩小於如果希望，因需求分頁而造成的效能減緩小於 10%則，則， 110 100 + 24999900*p 10 24999900 * p p 0.0000004 (約每約每2500000次存取只產生一次分頁錯誤）次存取只產生一次分頁錯誤）Silberschatz and Galvin1999 9.9Operating System Concepts分頁替換分頁替換（Page Replacement）增加多元程式規劃的程度，可能造成過渡配置增加多元程式規劃的程度，可能造成過渡配置（ over-allocation）- 當

10、發生分頁錯誤時，卻發現沒有實體空間了當發生分頁錯誤時，卻發現沒有實體空間了。解決的方式是在，分頁錯誤處理常式中加入分頁替換。解決的方式是在，分頁錯誤處理常式中加入分頁替換（ page replacement）.分頁錯誤處理常式分頁錯誤處理常式（NEW） 1. 找出想要的那一頁在磁碟中什麼地方找出想要的那一頁在磁碟中什麼地方。2. 找出可用的欄找出可用的欄（FRAME） a. 如果有空白欄，則直接使用如果有空白欄，則直接使用 b. 否則使用分頁替換演算法找到一個當作犧牲品的欄否則使用分頁替換演算法找到一個當作犧牲品的欄。 c. 將犧牲品的欄寫入磁碟，並更改分頁表及分欄表將犧牲品的欄寫入磁碟，並更

11、改分頁表及分欄表。3. 載入需求的分頁，並更改分頁表及分欄表載入需求的分頁，並更改分頁表及分欄表。4. 重新啟動使用者的行程重新啟動使用者的行程Silberschatz and Galvin1999 9.10Operating System Concepts分頁替換分頁替換（Page Replacement）- cont犧牲品犧牲品輔助記憶體輔助記憶體o if v1將犧牲品將犧牲品置換出去置換出去3載入需求載入需求的分頁的分頁2更改為更改為不可用不可用4為新的一頁為新的一頁更改分頁表更改分頁表分頁表分頁表實體記憶體實體記憶體可運用修改位元（可運用修改位元（modify bit)或髒位元（或髒位

12、元（dirty bit)來減少，來減少，犧牲品寫出到磁碟的次數。犧牲品寫出到磁碟的次數。Silberschatz and Galvin1999 9.11Operating System Concepts分頁替代法則分頁替代法則（Page-Replacement Algorithms）1 2 3 4 5 6 7 2468101214欄數欄數分分頁頁錯錯誤誤的的數數量量分頁錯誤的數量與欄的數量之間的關係分頁錯誤的數量與欄的數量之間的關係Silberschatz and Galvin1999 9.12Operating System Concepts分頁替代法則分頁替代法則（Page-Replace

13、ment Algorithms）先進先出（先進先出（First-In-First-Out;FIFO)最佳法則最佳法則（Optimal Algorithm）近來最少使用近來最少使用（Least Recently Used ;LRU)v計數器計數器v堆疊堆疊LRU 近似法近似法（LRU Approximation Algorithms）v額外的參考位元法則（額外的參考位元法則（Additional Reference-Bits)v第二次機會替換法（第二次機會替換法（Second-Chance Algorithm)v加強第二次機會替換法加強第二次機會替換法計數法計數法v最不經常使用（最不經常使用（L

14、east frequently used;LFU)v最常使用最常使用Silberschatz and Galvin1999 9.13Operating System ConceptsFirst-In-First-Out (FIFO) Algorithm參考串參考串: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 53 frames (3 pages can be in memory at a time per process)4 frames愈多欄數，不見得越少分頁錯誤（愈多欄數，不見得越少分頁錯誤（畢雷地異常畢雷地異常;Beladys anomaly)1231234125

15、349 page faults1231235124510 page faults443Silberschatz and Galvin1999 9.14Operating System Concepts最佳法則最佳法則（Optimal Algorithm）置換最久不會被用到的分頁置換最久不會被用到的分頁 frames example 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5如何得知誰最久不會被用到呢如何得知誰最久不會被用到呢?12346 個個page faults45Silberschatz and Galvin1999 9.15Operating System Co

16、ncepts近來最少使用近來最少使用（Least Recently Used ;LRU) 參考串參考串: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5123544358 個個 Page FaultSilberschatz and Galvin1999 9.16Operating System ConceptsLRU Algorithm (Cont.)計數器法（計數器法（Counter） 每一分頁項目都附著一個使用時間暫存器，當分每一分頁項目都附著一個使用時間暫存器，當分頁被參考到時，便將系統的時間複製到該分頁的時頁被參考到時，便將系統的時間複製到該分頁的時間暫存器間暫存

17、器 內。內。 當發生當發生Page Fault 時便搜尋所有分頁，找到最時間最時便搜尋所有分頁，找到最時間最小的分頁，置換該分頁。小的分頁，置換該分頁。Silberschatz and Galvin1999 9.17Operating System ConceptsLRU Algorithm (Cont.)堆疊法（堆疊法（STACK） 參考串：參考串：1, 2, 3, 4, 2, 51234headtail1342headtail3425headtail分分頁頁被被參參考考到到時時，加加到到Tail，不不用用搜搜尋尋Silberschatz and Galvin1999 9.18Operati

18、ng System ConceptsLRU 近似法近似法（LRU Approximation Algorithms）額外的參考位元法則（額外的參考位元法則（Additional Reference-Bits)第二次機會替換法（第二次機會替換法（Second-Chance Algorithm)加強第二次機會替換法加強第二次機會替換法Silberschatz and Galvin1999 9.19Operating System ConceptsLRU 近似法近似法（LRU Approximation Algorithms）額外的參考位元法則（額外的參考位元法則（Additional Refere

19、nce-Bits) 每一個分頁保存一個每一個分頁保存一個8 位元的參考位元組。位元的參考位元組。 分頁被參考到時，將最高分頁被參考到時，將最高BIT設為設為1。 每經過一段時間便將所有該分頁的參考位元組往每經過一段時間便將所有該分頁的參考位元組往右右SHIFT。 01110111 比比 11000100 近來較少使用近來較少使用(因為因為01110111 記憶體總量記憶體總量，則會發生，則會發生輾轉現象輾轉現象只要處理好只要處理好 局部區域，便可有效控制輾轉現象局部區域，便可有效控制輾轉現象Silberschatz and Galvin1999 9.28Operating System Con

20、cepts工作組模式工作組模式（Working-Set ModelWorking-Set Model）工作組模式乃基於局部區域的假設而設定。工作組模式乃基於局部區域的假設而設定。 WSSWSSi i ( (行程行程 P Pi i 的的工作組欄框工作組欄框) = ) = 最近最近 時間內的頁參考時間內的頁參考若若 太小則無法含蓋整個太小則無法含蓋整個局部區域（局部區域（Locality)Locality). .若若 太大則會含蓋數個太大則會含蓋數個局部區域局部區域. .若若 = = 含蓋整個程式。含蓋整個程式。D D = = WSSWSSi i 所有需求分頁（所有需求分頁（ demand fra

21、mes demand frames ）若若 D D m m 輾轉現象（輾轉現象（ThrashingThrashing）(m:(m:所有記憶體）所有記憶體）結論結論，作業系統監督每一個行程的工作組，並且按照其工作組的大作業系統監督每一個行程的工作組，並且按照其工作組的大小分配給他足夠的欄使用。如果還有足夠的額外欄可用，就可以啟動小分配給他足夠的欄使用。如果還有足夠的額外欄可用，就可以啟動另一個行程。如果另一個行程。如果 D D m m ，則作業系統就選出一個行程來，讓它暫則作業系統就選出一個行程來，讓它暫時被擱置時被擱置( (降低多元程式規劃）。降低多元程式規劃）。Silberschatz an

22、d Galvin1999 9.29Operating System Concepts工作組模式工作組模式-2-2（Working-Set ModelWorking-Set Model）5101520124356假設假設 m = 14 D D= = WSSWSSi i= 12 = 12 8 8 11 11 1515 11 11 D m 擱置優先權最低之行程擱置優先權最低之行程還有很多空間還有很多空間增加行程增加行程Silberschatz and Galvin1999 9.30Operating System Concepts分頁錯誤頻率分頁錯誤頻率（Page-Fault Frequency S

23、cheme）設定一個可接受（設定一個可接受（acceptableacceptable）的分頁錯誤頻率的分頁錯誤頻率若，分頁錯誤頻率太低，則從該行程移走一個欄若，分頁錯誤頻率太低，則從該行程移走一個欄. .若，分頁錯誤頻率太高，則多配置一個欄給該行程若，分頁錯誤頻率太高，則多配置一個欄給該行程. .增加欄數增加欄數減少欄數減少欄數分分頁頁錯錯誤誤頻頻率率Silberschatz and Galvin1999 9.31Operating System Concepts其他考量其他考量（Other ConsiderationsOther Considerations）預先分頁（預先分頁（Prepag

24、ingPrepaging）將所有需要的分頁一起載入，而非發生一次分頁錯誤載入將所有需要的分頁一起載入，而非發生一次分頁錯誤載入一個分頁。一個分頁。 分頁大小的選擇（分頁大小的選擇（Page size selectionPage size selection）分頁愈大，內部斷裂（分頁愈大，內部斷裂（fragmentationfragmentation）愈大愈大分頁愈小，分頁表愈大，愈浪費記憶體分頁愈小，分頁表愈大，愈浪費記憶體 分頁愈小愈能配合程式區域性的特性，避免載入一分頁愈小愈能配合程式區域性的特性，避免載入一些用不到的程式碼。些用不到的程式碼。分頁愈小，發生分頁錯誤的機率愈高，中斷處理之額外分頁愈小，發生分頁錯誤的機率愈高，中斷處理之額外負擔愈重。負擔愈重。根據史實的統計，根據史實的統計，朝向大分頁朝向大分頁Silberschatz and Galv