第八章 虛擬內(nèi)存

1、虛擬內(nèi)存虛擬內(nèi)存(virtual memory) 允許進(jìn)程執(zhí)行時(shí)只將部分程序放入內(nèi)存進(jìn)程中的所有內(nèi)存訪(fǎng)問(wèn)都是邏輯地址，運(yùn)行時(shí)轉(zhuǎn)換成物理地址進(jìn)程可以換入換出內(nèi)存，不同時(shí)刻占據(jù)內(nèi)存中的不同區(qū)域一個(gè)進(jìn)程可以劃分成許多塊（頁(yè)和段），執(zhí)行過(guò)程不需要連續(xù)地位于內(nèi)存。虛擬內(nèi)存支持的程序的執(zhí)行OS僅讀取包含程序開(kāi)始出動(dòng)一個(gè)或幾個(gè)塊進(jìn)程中任何時(shí)候都在內(nèi)存的進(jìn)程中任何時(shí)候都在內(nèi)存的部分部分-常駐集常駐集1. 需要訪(fǎng)問(wèn)一個(gè)不在內(nèi)存的地址，產(chǎn)生中斷2. OS將進(jìn)程放置在阻塞態(tài)3. OS將引發(fā)訪(fǎng)問(wèn)故障的進(jìn)程塊讀入內(nèi)存OS產(chǎn)生一個(gè)磁盤(pán)I/O讀請(qǐng)求執(zhí)行另一個(gè)進(jìn)程需要的塊被讀入內(nèi)存時(shí)，產(chǎn)生I/O中斷OS將阻塞的進(jìn)程置為就緒態(tài)

2、提高系統(tǒng)利用率在內(nèi)存中保留多個(gè)在內(nèi)存中保留多個(gè)進(jìn)程，進(jìn)程，系統(tǒng)并發(fā)度提高系統(tǒng)并發(fā)度提高任何特定的進(jìn)程都僅僅裝入它的某些塊任何時(shí)刻都至少有一個(gè)處于就緒態(tài)進(jìn)程可以比內(nèi)存的全部空間還大將程序分塊，實(shí)施覆蓋覆蓋策略分別加載引入虛擬內(nèi)存，由OS和硬件完成內(nèi)存管理單元內(nèi)存管理單元（MMU，Memory Management Unit）集成于CPU，或作為一個(gè)協(xié)處理器功能：分解邏輯地址地址轉(zhuǎn)換發(fā)出缺頁(yè)中斷設(shè)置和檢查頁(yè)表等存儲(chǔ)器分類(lèi)存儲(chǔ)器分類(lèi)實(shí)存儲(chǔ)器：執(zhí)行進(jìn)程的內(nèi)存虛擬內(nèi)存：用戶(hù)感覺(jué)的是更大的內(nèi)存，實(shí)際分配在磁盤(pán)上支持更有效的多道程序設(shè)計(jì)解除了用戶(hù)與內(nèi)存之間的緊密約束系統(tǒng)抖動(dòng)系統(tǒng)抖動(dòng)：一塊正好在將要被用到之前

3、換出，OS不得不很快把它取回。處理器的大部分時(shí)間都用于交換塊，而不是執(zhí)行指令。避免避免抖動(dòng)抖動(dòng)局部性局部性原理原理：一個(gè)進(jìn)程中程序和數(shù)據(jù)引用的集簇傾向短時(shí)間僅需要進(jìn)程的一部分塊智能猜測(cè)將會(huì)訪(fǎng)問(wèn)哪一塊虛擬內(nèi)存所需因素必須有對(duì)所采用的分頁(yè)或分段方案的硬件支持硬件支持OS必須有管理頁(yè)或段在內(nèi)存和輔助存儲(chǔ)器之間移動(dòng)的軟件虛擬內(nèi)存特征特征離散地分配內(nèi)存進(jìn)程分多次調(diào)入內(nèi)存，每次只調(diào)入一部分從邏輯上擴(kuò)充內(nèi)存容量速度接近內(nèi)存，成本接近外存簡(jiǎn)單分頁(yè)簡(jiǎn)單分頁(yè)每個(gè)進(jìn)程都有自己的頁(yè)表頁(yè)表項(xiàng)包含與內(nèi)存中頁(yè)框相對(duì)應(yīng)的頁(yè)框號(hào)虛擬虛擬內(nèi)存分頁(yè)內(nèi)存分頁(yè)頁(yè)表項(xiàng)需駐留位駐留位（P）來(lái)表示它所對(duì)應(yīng)的頁(yè)當(dāng)前是否在內(nèi)存中，如在，還包括頁(yè)

4、框號(hào)頁(yè)表項(xiàng)中還需另一個(gè)控制位控制位（M）相應(yīng)頁(yè)的內(nèi)容從上一次裝入內(nèi)存中到現(xiàn)在是否已改變?nèi)缥醋儯擁?yè)換出時(shí)，不需要用頁(yè)框中的內(nèi)容更新該頁(yè)實(shí)現(xiàn)保護(hù)和共享所需的其它控制位駐留位駐留位=0 不在內(nèi)存=1 在內(nèi)存頁(yè)號(hào)頁(yè)幀頁(yè)號(hào)頁(yè)幀PM引用字段 磁盤(pán)地址修改位修改位=0 未修改=1 已修改過(guò) 記錄訪(fǎng)問(wèn)次數(shù)、時(shí)間間隔等信息地址轉(zhuǎn)換頁(yè)表起始地址頁(yè)表起始地址nm頁(yè)表存在虛存中，至少一部分必須在內(nèi)存中1頁(yè)=4KB=212B；4GB=232B=220頁(yè)；1頁(yè)表=220頁(yè)表項(xiàng)=220*4B=210頁(yè)；一個(gè)根頁(yè)表=210頁(yè)表項(xiàng)=210*4B=212B，占據(jù)一頁(yè)內(nèi)存內(nèi)存或磁盤(pán)頁(yè)框號(hào)頁(yè)框號(hào)頁(yè)框頁(yè)框傳統(tǒng)頁(yè)表缺陷缺陷：頁(yè)表的大小

5、與虛擬地址空間的大小成正比解決方案：虛擬地址的頁(yè)號(hào)部分使用一個(gè)簡(jiǎn)單的散列函數(shù)散列函數(shù)映射到散列表散列表中，散列表中含有指向倒排表的指針，倒排表含有頁(yè)表項(xiàng)散列表和倒排表各有一項(xiàng)對(duì)應(yīng)于一個(gè)實(shí)存頁(yè)頁(yè)表的大小都是固定的=頁(yè)框數(shù)頁(yè)號(hào)頁(yè)號(hào)：虛擬地址的頁(yè)號(hào)部分進(jìn)程進(jìn)程標(biāo)志標(biāo)志符符：PID-頁(yè)號(hào)+ID=特定進(jìn)程的虛擬地址空間的一頁(yè)控制位控制位：該域包含一些標(biāo)記鏈指針鏈指針：如果某個(gè)項(xiàng)沒(méi)有鏈項(xiàng)，則該域?yàn)榭枕?yè)框號(hào)頁(yè)框號(hào)每個(gè)物理內(nèi)存頁(yè)框一項(xiàng)每個(gè)物理內(nèi)存頁(yè)框一項(xiàng)問(wèn)題：虛存訪(fǎng)問(wèn)可引起兩次物理內(nèi)存訪(fǎng)問(wèn)，時(shí)間加倍一次取相應(yīng)的頁(yè)表項(xiàng)一次取需要的數(shù)據(jù)解決：使用一個(gè)特殊的特殊的高速緩存高速緩存(TLB)保存頁(yè)表包含最近用過(guò)的頁(yè)表

6、項(xiàng)轉(zhuǎn)換檢測(cè)緩沖區(qū)轉(zhuǎn)換檢測(cè)緩沖區(qū)頁(yè)框號(hào)頁(yè)框號(hào)虛擬地址轉(zhuǎn)換成實(shí)地址訪(fǎng)問(wèn)頁(yè)表項(xiàng)在TLB中，或在內(nèi)存中或磁盤(pán)中訪(fǎng)問(wèn)的字高速緩存中、內(nèi)存中或磁盤(pán)中如果在磁盤(pán)中含有該字的頁(yè)裝入內(nèi)存；所在的塊狀如高速緩存；該頁(yè)對(duì)應(yīng)的頁(yè)表項(xiàng)更新內(nèi)部碎片：頁(yè)越小，內(nèi)部碎片的總量越少 頁(yè)表長(zhǎng)度：頁(yè)越多，頁(yè)表越大磁盤(pán)開(kāi)銷(xiāo)：頁(yè)越大，磁盤(pán)I/O開(kāi)銷(xiāo)越小缺頁(yè)中斷：頁(yè)越多，缺頁(yè)率越低輔存設(shè)備的物理特性：內(nèi)存越大，頁(yè)也增大，實(shí)現(xiàn)有效數(shù)據(jù)塊傳遞允許把內(nèi)存視為由多個(gè)地址空間或段組成，段大小不等，且是動(dòng)態(tài)的內(nèi)存訪(fǎng)問(wèn)=段號(hào)+偏移量虛擬分段優(yōu)點(diǎn)：簡(jiǎn)化對(duì)不斷增長(zhǎng)的數(shù)據(jù)結(jié)構(gòu)的處理允許程序獨(dú)立地改變或重新編譯有助于進(jìn)程間共享有助于保護(hù)，程序員可以方便指定訪(fǎng)

7、問(wèn)權(quán)限分段組織每個(gè)進(jìn)程有一個(gè)唯一的段表段表項(xiàng)中有一位表明該段是否在內(nèi)存駐留位如在，則含有段起始地址和長(zhǎng)度 修改位其它控制位段號(hào)段號(hào)段長(zhǎng)段長(zhǎng)基址基址 駐留位駐留位 修改位修改位 訪(fǎng)問(wèn)字段訪(fǎng)問(wèn)字段存取權(quán)限存取權(quán)限擴(kuò)充位擴(kuò)充位外存地址外存地址用戶(hù)的地址空間劃分成許多段，每個(gè)段依次劃分成許多固定大小的頁(yè)，頁(yè)的長(zhǎng)度等于內(nèi)存中頁(yè)框大小分頁(yè)對(duì)程序員是透明的，消除了外部碎片分段對(duì)程序員是可見(jiàn)的，支持共享和保護(hù)每個(gè)進(jìn)程一個(gè)段表，每個(gè)段一個(gè)頁(yè)表邏輯地址段表頁(yè)表段號(hào)段號(hào)段內(nèi)頁(yè)號(hào)段內(nèi)頁(yè)號(hào)頁(yè)內(nèi)偏移量頁(yè)內(nèi)偏移量控制位控制位頁(yè)表長(zhǎng)度頁(yè)表長(zhǎng)度頁(yè)表起始地址頁(yè)表起始地址控制位控制位頁(yè)框號(hào)頁(yè)框號(hào)防止越界和越權(quán)操作系統(tǒng)內(nèi)存管理設(shè)計(jì)：

8、設(shè)計(jì)：是否使用虛存技術(shù)-硬件平臺(tái)是使用分頁(yè)還是分段，或二者結(jié)合-硬件平臺(tái)虛存管理的算法算法-軟件支持讀取策略讀取策略放置放置策略策略置換策略置換策略駐留集管理駐留集管理 清除清除策略策略 加載控制加載控制 確定一個(gè)頁(yè)何時(shí)讀入內(nèi)存請(qǐng)求分請(qǐng)求分頁(yè)頁(yè)只當(dāng)訪(fǎng)問(wèn)到某頁(yè)中的一個(gè)單元時(shí)才將該頁(yè)取入內(nèi)存預(yù)先分預(yù)先分頁(yè)頁(yè)讀取的頁(yè)并不是缺頁(yè)中斷請(qǐng)求的頁(yè)利用大多數(shù)輔存的特性，尋道時(shí)間和合理的延遲一次讀取許多連續(xù)的頁(yè)比隔一段時(shí)間讀取一頁(yè)有效進(jìn)程第一次啟動(dòng)第一次啟動(dòng)時(shí)，可以采用預(yù)先分頁(yè)策略決定決定一個(gè)進(jìn)程塊駐留一個(gè)進(jìn)程塊駐留在實(shí)存中在實(shí)存中的什么的什么地方地方分頁(yè)/段頁(yè)式系統(tǒng)：離散放置分段：最佳適配/首次適配/下次適配

9、算法非一致存儲(chǔ)訪(fǎng)問(wèn)多處理器（分布式系統(tǒng)或集群）性能依賴(lài)于數(shù)據(jù)駐留的位置與使用數(shù)據(jù)的處理器間的距離自動(dòng)放置策略希望能把頁(yè)分配到能夠提供最佳性能的內(nèi)存必須讀取一個(gè)新頁(yè)時(shí)，應(yīng)該置換內(nèi)存中的哪一頁(yè)給每個(gè)活動(dòng)進(jìn)程分配多少頁(yè)框計(jì)劃置換頁(yè)的集合是局限在哪些進(jìn)程計(jì)劃置換的頁(yè)集中計(jì)劃置換的頁(yè)集中，選擇換選擇換出哪一個(gè)頁(yè)出哪一個(gè)頁(yè)所有策略目標(biāo)：移出最不可能訪(fǎng)問(wèn)的頁(yè)所有策略目標(biāo)：移出最不可能訪(fǎng)問(wèn)的頁(yè)頁(yè)框鎖定頁(yè)框鎖定 置換策略約束：內(nèi)存中的某些頁(yè)框可能是被鎖定的鎖定頁(yè)框中的頁(yè)不可置換大部分OS內(nèi)核內(nèi)核和重要的控制結(jié)構(gòu)就保存在鎖定頁(yè)框中，I/O緩沖區(qū)和其它對(duì)時(shí)間要求嚴(yán)格的區(qū)域頁(yè)框關(guān)聯(lián)lock位位實(shí)現(xiàn)基本置換算法基本置換

10、算法最佳置換（最佳置換（OPT）選擇置換下次訪(fǎng)問(wèn)距當(dāng)前時(shí)間最長(zhǎng)的那些頁(yè) 能導(dǎo)致最少的缺頁(yè)中斷，理想化理想化 ，不可實(shí)現(xiàn)，不可實(shí)現(xiàn)初始化后缺頁(yè)率：初始化后缺頁(yè)率：3/12=25%頁(yè)框初始化頁(yè)框初始化基本置換算法基本置換算法最近最少使用（LRU）置換內(nèi)存中上次使用距當(dāng)前最遠(yuǎn)的頁(yè)難以實(shí)現(xiàn)，開(kāi)銷(xiāo)很大添加時(shí)間戳維護(hù)訪(fǎng)問(wèn)頁(yè)的棧缺頁(yè)率=4/12=33.3%先進(jìn)先出（先進(jìn)先出（FIFO）把分配給進(jìn)程的頁(yè)框視為一個(gè)循環(huán)緩沖區(qū)，按循環(huán)方式移動(dòng)頁(yè)只需一個(gè)指針，在頁(yè)框中循環(huán)，實(shí)現(xiàn)簡(jiǎn)單置換駐留內(nèi)存時(shí)間最長(zhǎng)的頁(yè)缺頁(yè)率=6/12=50%時(shí)鐘（時(shí)鐘（Clock) 需要給每一頁(yè)框關(guān)聯(lián)一個(gè)使用位，當(dāng)某頁(yè)裝入內(nèi)存時(shí)，使用位為1頁(yè)被

11、訪(fǎng)問(wèn)到時(shí)，使用位置1 當(dāng)置換頁(yè)時(shí)，OS查找使用位置為0的頁(yè)框每遇到使用位為1的頁(yè)，將其置為0 改進(jìn)的時(shí)鐘算法改進(jìn)的時(shí)鐘算法使用位+修改位最近未被訪(fǎng)問(wèn)，也未被修改（u=0；m=0）最近被訪(fǎng)問(wèn)，但未被修改（u=1；m=0）最近未被訪(fǎng)問(wèn)，但被修改（u=0；m=1）最近被訪(fǎng)問(wèn)，被修改（u=1；m=1）改進(jìn)的時(shí)鐘改進(jìn)的時(shí)鐘算法算法1.從指針當(dāng)前位開(kāi)始掃描，選擇u=0，m=02.否則，重新掃描，查找u=0；m=1，選擇第一個(gè)置換，對(duì)每個(gè)跳過(guò)的頁(yè)框，u=1置0 3.否則，指針回到最初位，此時(shí)所有u=0，重復(fù)第一步、第二步。頁(yè)緩沖技術(shù)采用FIFO，簡(jiǎn)單且開(kāi)銷(xiāo)小為提高性能，被置換的頁(yè)被分配到兩個(gè)表中如未修改，分

12、配到空閑頁(yè)鏈表如已修改，分配到修改頁(yè)鏈表不是發(fā)生物理移動(dòng)，僅是頁(yè)表項(xiàng)移動(dòng)所謂駐留集駐留集，是指在某段時(shí)間間隔內(nèi)，進(jìn)程要訪(fǎng)問(wèn)的頁(yè)面集合，是一個(gè)二元函數(shù)w（t，）分配駐留集需考慮因素分配給一個(gè)進(jìn)程的內(nèi)存越少，同時(shí)駐留內(nèi)存的進(jìn)程數(shù)越多，OS越可能找到一個(gè)就緒進(jìn)程，減少CPU時(shí)間一個(gè)進(jìn)程在內(nèi)存中的頁(yè)數(shù)較少，缺頁(yè)率則相對(duì)較高特定進(jìn)程分配的內(nèi)存空間超過(guò)一定大小后，缺頁(yè)率沒(méi)有明顯變化頁(yè)面分配策略固定分配固定分配主存中為進(jìn)程分配固定數(shù)目的頁(yè)固定數(shù)目的頁(yè)框框數(shù)目在最初加載時(shí)決定（進(jìn)程創(chuàng)建時(shí)）一旦發(fā)生頁(yè)錯(cuò)誤，進(jìn)程的一頁(yè)必須被它所需的頁(yè)替換可變分配可變分配分配給進(jìn)程的頁(yè)框數(shù)，在其生命周期中不斷變化需要OS時(shí)刻評(píng)估進(jìn)

13、程行為，檢測(cè)缺頁(yè)率置換范圍局部置換策略局部置換策略?xún)H僅在產(chǎn)生缺頁(yè)的進(jìn)程的駐留頁(yè)集中選擇全局置換策略全局置換策略把內(nèi)存中所有未被鎖定的頁(yè)作為候選頁(yè)簡(jiǎn)單，開(kāi)銷(xiāo)小固定分配、局部置換固定分配、局部置換 分配給內(nèi)存中運(yùn)行的進(jìn)程的頁(yè)框數(shù)固定需要根據(jù)應(yīng)用程序的類(lèi)型和程序的請(qǐng)求總量事先確定分配給該進(jìn)程的總頁(yè)框數(shù)缺點(diǎn)：如總頁(yè)面數(shù)分配得過(guò)少，則會(huì)產(chǎn)生很高的缺頁(yè)率，如過(guò)多，內(nèi)存只能有很少的程序，處理器很多空閑時(shí)間不靈活可變分配、全局置換可變分配、全局置換易實(shí)現(xiàn)，一個(gè)進(jìn)程的某一頁(yè)置換了另一個(gè)進(jìn)程的某一頁(yè)，則該進(jìn)程分配增加一頁(yè)，另一個(gè)則減少一頁(yè)內(nèi)存中有許多分配到一定數(shù)目頁(yè)框的進(jìn)程，一個(gè)空閑頁(yè)框列表難點(diǎn)：沒(méi)有空閑頁(yè)框時(shí)，

14、如何選擇置換頁(yè)如何選擇置換頁(yè)解決：頁(yè)緩沖可變分配、局部置換可變分配、局部置換當(dāng)新進(jìn)程裝入內(nèi)存時(shí)，根據(jù)應(yīng)用類(lèi)型、程序要求或其他原則分配一定數(shù)目的頁(yè)框作為其駐留集發(fā)生一次缺頁(yè)中斷時(shí)，從產(chǎn)生缺頁(yè)中斷的進(jìn)程的駐留集中選擇一頁(yè)用于置換不時(shí)地重新評(píng)估頁(yè)框分配，增加或減少分配的頁(yè)框，以提高性能用于確定何時(shí)將修改過(guò)的頁(yè)寫(xiě)回磁盤(pán)請(qǐng)求式清除請(qǐng)求式清除只有當(dāng)一頁(yè)被選擇置換 時(shí)才被寫(xiě)回磁盤(pán)發(fā)生缺頁(yè)中斷的進(jìn)程在解除阻塞之前必須等待兩次頁(yè)傳送，耗費(fèi)CPU時(shí)間預(yù)約式預(yù)約式清除清除將被修改的多個(gè)頁(yè)在需要用到它們所占據(jù)的頁(yè)框之前成批的寫(xiě)回磁盤(pán)寫(xiě)回輔存的頁(yè)可能仍然留在內(nèi)存，在下次移出內(nèi)存之前又被修改，使得上次的寫(xiě)回操作毫無(wú)意義頁(yè)緩沖技術(shù)頁(yè)緩沖技術(shù)只清除可以用于置換的頁(yè)，取消了清除和置換之間的成對(duì)關(guān)系頁(yè)緩沖可以將被置換頁(yè)放置在兩個(gè)表中：修改表和未修改表 修改表：頁(yè)可以周期性地成批寫(xiě)出，移至未修改表未修改表：頁(yè)或因?yàn)樵L(fǎng)問(wèn)而回收，或因頁(yè)框分配給另一頁(yè)而淘汰系統(tǒng)并發(fā)度-駐留內(nèi)存中的進(jìn)程數(shù)目駐留進(jìn)程太少，所有進(jìn)程同時(shí)處于阻塞狀態(tài)的概率較大駐留進(jìn)程太多，會(huì)頻繁發(fā)生缺頁(yè)中斷，導(dǎo)致系統(tǒng)抖動(dòng)抖動(dòng)系統(tǒng)并發(fā)度系統(tǒng)并發(fā)度減小，一