3.2 虛擬內存管理
3.2.1 虛擬內存的基本概念
3.2.1.1 傳統(tǒng)存儲管理方式的特征
傳統(tǒng)存儲管理很多暫時用不到的數(shù)據(jù)也會長期占用內存钦睡，導致內存利用率不高谐区，他們具有以下兩個特征
- 一次性：作業(yè)必須一次性全部裝入內存后才能開始運行。這會造成兩個問題：①作業(yè)很大時弥咪，不能全部裝入內存义黎，導致大作業(yè)無法運行冷尉；②當大量作業(yè)要求運行時，由于內存無法容納所有作業(yè)力细，因此只有少量作業(yè)能運行睬澡，導致多道程序并發(fā)度下降。
- 駐留性：一旦作業(yè)被裝入內存眠蚂，就會一直駐留在內存中煞聪，直至作業(yè)運行結束。事實上逝慧，在一個時間段內昔脯，只需要訪問作業(yè)的一小部分數(shù)據(jù)即可正常運行，這就導致了內存中會駐留大量的笛臣、暫時用不到的數(shù)據(jù)云稚，浪費了寶貴的內存資源。
3.2.1.2 局部性原理
高速緩沖技術的思想：將近期會頻繁訪問到的數(shù)據(jù)放到更高速的存儲器中沈堡，暫時用不到的數(shù)據(jù)放在更低速存儲器中静陈。快表機構就是將近期常訪問的頁表項副本放到更高速的聯(lián)想寄存器中诞丽，其依賴的就是局部性原理
時間局部性：如果執(zhí)行了程序中的某條指令窿给，那么不久后這條指令很有可能再次執(zhí)行贵白；如果某個數(shù)據(jù)被訪問過，不久之后該數(shù)據(jù)很可能再次被訪問崩泡。（因為程序中存在大量的循環(huán)）
空間局部性：一旦程序訪問了某個存儲單元禁荒，在不久之后，其附近的存儲單元也很有可能被訪問角撞。（因為很多數(shù)據(jù)在內存中都是連續(xù)存放的呛伴，并且程序的指令也是順序地在內存中存放的）
3.2.1.3 虛擬存儲器的定義和特征
基于局部性原理，在程序裝入時谒所，可以將程序中很快會用到的部分裝入內存热康，暫時用不到的部分留在外存，就可以讓程序開始執(zhí)行劣领。在程序執(zhí)行過程中姐军，當所訪問的信息不在內存時，由操作系統(tǒng)負責將所需信息從外存調入內存尖淘，然后繼續(xù)執(zhí)行程序奕锌。若內存空間不夠，由操作系統(tǒng)負責將內存中暫時用不到的信息換出到外存村生。在操作系統(tǒng)的管理下惊暴，在用戶看來似乎有一個比實際內存大得多的內存，這就是虛擬內存趁桃。虛擬內存是操作系統(tǒng)虛擬性的一個體現(xiàn)辽话，實際的物理內存大小沒有變，只是在邏輯上進行了擴充卫病。
虛擬內存有以下三個主要特征：
- 多次性：無需在作業(yè)運行時一次性全部裝入內存油啤，而是允許被分成多次調入內存。
- 對換性：在作業(yè)運行時無需一直常駐內存蟀苛，而是允許在作業(yè)運行過程中村砂，將作業(yè)換入、換出屹逛。
- 虛擬性：從邏輯上擴充了內存的容量础废，使用戶看到的內存容量，遠大于實際的容量罕模。
3.2.1.4 實現(xiàn)虛擬內存技術
虛擬內存技術评腺，允許一個作業(yè)分多次調入內存。如果采用連續(xù)分配方式淑掌，會不方便實現(xiàn)蒿讥。因此，虛擬內存的實現(xiàn)需要建立在離散分配的內存管理方式基礎上。
虛擬內存的實現(xiàn)有以下三種方式
- 請求分頁存儲管理
- 請求分段存儲管理
- 請求段頁式存儲管理
在程序執(zhí)行過程中芋绸，當所訪問的信息不在內存時媒殉，由操作系統(tǒng)負責將所需信息從外存調入內存，然后繼續(xù)執(zhí)行程序摔敛。[1]若內存空間不夠廷蓉，由操作系統(tǒng)負責將內存中暫時用不到的信息換出到外存。[2]
3.2.2 請求分頁管理方式
請求分頁系統(tǒng)建立在基本分頁系統(tǒng)之上马昙，為了支持虛擬存儲器功能而增加了請求調頁和頁面置換功能
3.2.2.1 頁表機制
與基本分頁管理相比桃犬，請求分頁管理中，為了實現(xiàn)“請求調頁”行楞，操作系統(tǒng)需要知道每個頁面是否已經(jīng)調入內存攒暇；如果還沒調入，那么也需要知道該頁面在外存中存放的位置子房。當內存空間不夠時形用，要實現(xiàn)“頁面置換”，操作系統(tǒng)需要通過某些指標來決定到底換出哪個頁面证杭；有的頁面沒有被修改過田度，就不用再浪費時間寫回外存。有的頁面修改過躯砰，就需要將外存中的舊數(shù)據(jù)覆蓋，因此携丁，操作系統(tǒng)也需要記錄各個頁面是否被修改的信息琢歇。因此，請求頁表項增加了四個字段
- 狀態(tài)位：是否已調入內存
- 訪問字段：可記錄最近被訪問過幾次梦鉴，或記錄上次訪問的時間李茫，供置換算法選擇換出頁面時參考
- 修改位：頁面調入內存后是否被修改過
- 外存地址：頁面在外存中的存放位置
3.2.2.2 缺頁中斷機構
在請求分頁系統(tǒng)中，每當要訪問的頁面不在內存時肥橙，便產生一個缺頁中斷魄宏，然后由操作系統(tǒng)的缺頁中斷處理程序處理中斷。此時缺頁的進程阻塞存筏，放入阻塞隊列宠互，調頁完成后再將其喚醒，放回就緒隊列椭坚。如果內存中有空閑塊予跌，則為進程分配一個空閑塊，將所缺頁面裝入該塊善茎，并修改頁表中相應的頁表項券册。
- 缺頁中斷是因為當前執(zhí)行的指令想要訪問的目標頁面未調入內存而產生的，因此屬于內中斷
- 一條指令在執(zhí)行期間，可能產生多次缺頁中斷烁焙。
3.2.2.3 地址變換機構
找到對應頁表項后航邢，若對應頁面未調入內存，則產生缺頁中斷骄蝇，之后由操作系統(tǒng)的缺頁中斷處理程序進行處理
快表中有的頁面一定是在內存中的膳殷。若某個頁面被換出外存，則快表中的相應表項也要刪除乞榨，否則可能訪問錯誤的頁面
- 只有“寫指令”才需要修改“修改位”秽之。并且，一般來說只需修改快表中的數(shù)據(jù)，只有要將快表項刪除時才需要寫回內存中的慢表皇钞。這樣可以減少訪存次數(shù)蛇数。
- 和普通的中斷處理一樣，缺頁中斷處理依然需要保留CPU現(xiàn)場河质。
- 需要用某種“頁面置換算法”來決定一個換出頁面
- 換入/換出頁面都需要啟動慢速的I/O操作，可見震叙，如果換入/換出太頻繁掀鹅，會有很大的開銷。
- 頁面調入內存后媒楼，需要修改慢表乐尊，同時也需要將表項復制到快表中。
3.2.3 頁面置換算法
頁面的換入划址、換出需要磁盤I/O扔嵌，會有較大的開銷，因此好的頁面置換算法應該追求更少的缺頁率
3.2.3.1 最佳置換算法(OPT)
最佳置換算法（OPT夺颤，Optimal）：每次選擇淘汰的頁面將是以后永不使用痢缎，或者在最長時間內不再被訪問的頁面，這樣可以保證最低的缺頁率世澜。
最佳置換算法可以保證最低的缺頁率独旷，但實際上，只有在進程執(zhí)行的過程中才能知道接下來會訪問到的是哪個頁面寥裂。操作系統(tǒng)無法提前預判頁面訪問序列嵌洼。因此，最佳置換算法是無法實現(xiàn)的封恰。
例：假設系統(tǒng)為某進程分配了三個內存塊咱台，并考慮到有一下頁面號引用串（會依次訪問這些頁面）：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
圖片.png整個過程缺頁中斷發(fā)生了9次，頁面置換發(fā)生了6次俭驮。
缺頁率= 9/20 = 45%
3.2.3.2 先進先出(FIFO)置換算法
先進先出置換算法（FIFO）：每次選擇淘汰的頁面是最早進入內存的頁面回溺。把調入內存的頁面根據(jù)調入的先后順序排成一個隊列春贸，需要換出頁面時選擇隊頭頁面即可。隊列的最大長度取決于系統(tǒng)為進程分配了多少個內存塊遗遵。
例：假設系統(tǒng)為某進程分配了三個內存塊萍恕，并考慮到有以下頁面號引用串：3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4
圖片.png分配四個內存塊時，缺頁次數(shù)：10次
分配三個內存塊時车要，缺頁次數(shù)：9次
只有FIFO算法會產生Belady異常[3]允粤。另外，F(xiàn)IFO算法雖然實現(xiàn)簡單翼岁，但是該算法與進程實際運行時的規(guī)律不適應类垫，因為先進入的頁面也有可能最經(jīng)常被訪問。因此琅坡，算法性能差
3.2.3.3 最近最久未使用(LRU)置換算法
最近最久未使用置換算法（LRU悉患，least recently used）：每次淘汰的頁面是最近最久未使用的頁面。賦予每個頁面對應的頁表項中榆俺，用訪問字段記錄該頁面自上次被訪問以來所經(jīng)歷的時間t售躁。當需要淘汰一個頁面時，選擇現(xiàn)有頁面中t值最大的茴晋，即最近最久未使用的頁面陪捷。
例：假設系統(tǒng)為某進程分配了四個內存塊，并考慮到有以下頁面號引用串：1, 8, 1, 7, 8, 2, 7, 2, 1, 8, 3, 8, 2, 1, 3, 1, 7, 1, 3, 7
圖片.png
該算法的實現(xiàn)需要專門的硬件支持诺擅，雖然算法性能好市袖，但是實現(xiàn)困難，開銷大
3.2.3.4 時鐘(CLOCK)置換算法
時鐘置換算法是一種性能和開銷較均衡的算法烁涌，又稱CLOCK算法苍碟，或最近未用算法（NRU，NotRecently Used）簡單的CLOCK算法實現(xiàn)方法：為每個頁面設置一個訪問位烹玉，再將內存中的頁面都通過鏈接指針鏈接成一個循環(huán)隊列驰怎。當某頁被訪問時阐滩，其訪問位置為1二打。當需要淘汰一個頁面時，只需檢查頁的訪問位掂榔。如果是0继效，就選擇該頁換出；如果是1装获，則將它置為0瑞信，暫不換出，繼續(xù)檢查下一個頁面穴豫，若第一輪掃描中所有頁面都是1凡简，則將這些頁面的訪問位依次置為0后逼友，再進行第二輪掃描（第二輪掃描中一定會有訪問位為0的頁面，因此簡單的CLOCK算法選擇一個淘汰頁面最多會經(jīng)過兩輪掃描）
改進型的時鐘置換算法：
簡單的時鐘置換算法僅考慮到一個頁面最近是否被訪問過秤涩。事實上帜乞，如果被淘汰的頁面沒有被修改過，就不需要執(zhí)行I/O操作寫回外存筐眷。只有被淘汰的頁面被修改過時黎烈，才需要寫回外存。因此匀谣，除了考慮一個頁面最近有沒有被訪問過之外照棋，操作系統(tǒng)還應考慮頁面有沒有被修改過。在其他條件都相同時武翎，應優(yōu)先淘汰沒有修改過的頁面烈炭，避免I/O操作。這就是改進型的時鐘置換算法的思想后频。修改位=0梳庆，表示頁面沒有被修改過；修改位=1卑惜，表示頁面被修改過膏执。為方便討論，用（訪問位露久，修改位）的形式表示各頁面狀態(tài)更米。如（1，1）表示一個頁面近期被訪問過毫痕，且被修改過征峦。
算法規(guī)則：將所有可能被置換的頁面排成一個循環(huán)隊列
- 第一輪：從當前位置開始掃描到第一個（0, 0）的幀用于替換。本輪掃描不修改任何標志位——第一優(yōu)先級：最近沒訪問消请，且沒修改的頁面
- 第二輪：若第一輪掃描失敗栏笆，則重新掃描，查找第一個（0, 1）的幀用于替換臊泰。本輪將所有掃描過的幀訪問位設為0——第二優(yōu)先級：最近沒訪問蛉加，但修改過的頁面
- 第三輪：若第二輪掃描失敗，則重新掃描缸逃，查找第一個（0, 0）的幀用于替換针饥。本輪掃描不修改任何標志位——第三優(yōu)先級：最近訪問過，但沒修改的頁面
- 第四輪：若第三輪掃描失敗需频，則重新掃描丁眼，查找第一個（0, 1）的幀用于替換≌蜒常——第四優(yōu)先級：最近訪問過苞七，且修改過的頁面
由于第二輪已將所有幀的訪問位設為0藐守，因此經(jīng)過第三輪、第四輪掃描一定會有一個幀被選中蹂风，因此改進型CLOCK置換算法選擇一個淘汰頁面最多會進行四輪掃描
3.2.4 頁面分配策略
3.2.4.1 駐留集大小
對于分頁式的虛擬內存吗伤，在進程準備執(zhí)行時，不需要也不可能把-一個進程的所有頁都讀入主存硫眨。因此足淆，操作系統(tǒng)必須決定讀取多少頁，即決定給特定的進程分配幾個頁框礁阁。
若駐留集太小巧号，會導致缺頁頻繁，系統(tǒng)要花大量的時間來處理缺頁姥闭，實際用于進程推進的時間很少
駐留集太大丹鸿，又會導致多道程序并發(fā)度下降，資源利用率降低棚品。所以應該選擇一個合適的駐留集大小
分配方式有
固定分配:操作系統(tǒng)為每個進程分配一組固定數(shù)目的物理塊靠欢，在進程運行其間不再改變，即大小不變
可變分配:先為每個進程分配一定數(shù)目的物理塊铜跑，在進程運行期間门怪，可即，駐留集大小可變
置換方式有
局部置換:發(fā)生缺頁時只能選進程自己的物理塊進行置換锅纺。
全局置換:可以將操作系統(tǒng)保留的空閑物理塊分配給缺頁進程掷空，也可以將別的進程持有的物理塊置換到外存，再分配給缺頁進程囤锉。
根據(jù)以上坦弟，現(xiàn)代操作系統(tǒng)通常采用三種策略：
- 固定分配局部置換:系統(tǒng)為每個進程分配一定數(shù)量的物理塊，在整個運行期間都不改變官地。若進程在運行中發(fā)生缺頁酿傍，則只能從該進程在內存中的頁面中選出一頁換出，然后再調入需要的頁面驱入。這種策略的缺點是:很難在剛開始就確定應為每個進程分配多少個物理塊才算合理赤炒。(采用這種策略的系統(tǒng)可以根據(jù)進程大小、優(yōu)先級沧侥、或是根據(jù)程序員給出的參數(shù)來確定為一個進程分配的內存塊數(shù))
- 可變分配全局置換:剛開始會為每個進程分配一定數(shù)量的物理塊可霎。操作系統(tǒng)會保持一個空閑物理塊隊列魄鸦。當某進程發(fā)生缺頁時宴杀，從空閑物理塊中取出一塊分配給該進程;若已無空閑物理塊，則可選擇一個未鎖定的頁面換出外存拾因，再將該物理塊分配給缺頁的進程旺罢。采用這種策略時旷余，只要某進程發(fā)生缺頁，都將獲得新的物理塊扁达，僅當空閑物理塊用完時正卧，系統(tǒng)才選擇一個未鎖定的頁面調出。被選擇調出的頁的頁可能是系統(tǒng)中任何一個進程中的頁跪解，因此這個被選中的進程擁有的物理塊會減少炉旷，缺頁率會增加。
- 可變分配局部置換:剛開始會為每個進程分配一定數(shù)量的物理塊叉讥。當某進程發(fā)生缺頁時窘行，只允許從該進程自己的物理塊中選出一個進行換出外存。如果進程在運行中頻繁地缺頁图仓，系統(tǒng)會為該進程多分配幾個物理課罐盔，直至該進程缺頁率趨勢適當當程度;反之，如果進程在運行中缺頁率特別低救崔，則可適當減少分配給該進程的物理塊
可變分配全局置換:只要缺頁就給分配新物理塊
可變分配局部置換:要根據(jù)發(fā)生缺頁的頻率來動態(tài)地增加或減少進程的物理塊
3.2.4.2 調入頁面的時機
預調頁策略:根據(jù)局部性原理惶看，一次調入若干個相鄰的頁面可能比一次調入一個頁面更高效。但如果提前調入的頁面中大多數(shù)都沒被訪問過六孵，則又是低效的纬黎。因此可以預測不久之后可能訪問到的頁面，將它們預先調入內存劫窒，但目前預測成功率只有50%左右莹桅。故這種策略主要用于進程的首次調入，由程序員指出應該先調入哪些部分烛亦。
請求調頁策略:進程在運行期間發(fā)現(xiàn)缺頁時才將所缺頁面調入內存诈泼。由這種策略調入的頁面一定會被訪問到，但由于每次只能調入一頁煤禽，而每次調頁都要磁盤l/O操作铐达，因此I/O開銷較大。
3.2.4.3 從何處調入頁面
請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)檬果。對換區(qū)通常采用連續(xù)分配方式瓮孙，而文件區(qū)采用離散分配方式，因此對換區(qū)的磁盤I/O速度比文件去的更快
- 系統(tǒng)擁有足夠的對換區(qū)空間:頁面的調入选脊、調出都是在內存與對換區(qū)之間進行杭抠，這樣可以保證頁面的調入、調出速度很快恳啥。在進程運行前偏灿，需將進程相關的數(shù)據(jù)從文件區(qū)復制到對換區(qū)。
- 系統(tǒng)缺少足夠的對換區(qū)空間:凡是不會被修改的數(shù)據(jù)都直接從文件區(qū)調入钝的，由于這些頁面不會被修改翁垂，因此換出時不必寫回磁盤铆遭，下次需要時再從文件區(qū)調入即可。對于可能被修改的部分沿猜，換出時需寫回磁盤對換區(qū)枚荣，下次需要時再從對換區(qū)調入。
- UNIX方式:運行之前進程有關的數(shù)據(jù)全部放在文件區(qū)啼肩，故未使用過的頁面橄妆，都可從文件區(qū)調入。若被使用過的頁面需要換出祈坠，則寫回對換區(qū)呼畸，下次需要時從對換區(qū)調入。
3.2.5 抖動
剛剛換出的頁面馬上又要換入內存颁虐，剛剛換入的頁面馬上又要換出外存蛮原，這種頻繁的頁面調度行為稱為抖動，或顛簸另绩。產生抖動的主要原因是進程頻繁訪問的頁面數(shù)目高于可用的物理塊數(shù)(分配給進程的物理塊不夠)
3.2.6 工作集
工作集:指在某段時間間隔里儒陨，進程實際訪問頁面的集合。
區(qū)別駐留集:指請求分頁存儲管理中給進程分配的內存塊的集合笋籽。
操作系統(tǒng)會根據(jù)“窗口尺寸”來算出工作集蹦漠。
圖片.png
工作集大小可能小于窗口尺寸，實際應用中车海，操作系統(tǒng)可以統(tǒng)計進程的工作集大小笛园，根據(jù)工作集大小給進程分配若干內存塊。[4]
一般來說侍芝，駐留集大小不能小于工作集大小研铆，否則進程運行過程中將頻繁缺頁。
基于局部性原理可知州叠，進程在一段時間內訪問的頁面與不久之后會訪問的頁面是有相關性的棵红。因此，可以根據(jù)進程近期訪問的頁面集合（工作集）來設計一種頁面置換算法――選擇一個不在工作集中的頁面進行淘汰咧栗。
