8.1虛擬存儲的需求背景

虛擬內(nèi)存是非連續(xù)內(nèi)存分配的一個延續(xù)，非連續(xù)內(nèi)存分配在存儲空間內(nèi)可以連續(xù)也可以不連續(xù)。虛擬內(nèi)存是在非連續(xù)內(nèi)存分配基礎(chǔ)上，可以把一部分內(nèi)容放到外存中去，讓應(yīng)用程序有更大的空間使用。

需求背景：增長迅速的存儲需求，程序規(guī)模的增長速度遠(yuǎn)遠(yuǎn)大于存儲器容量的增長速度。

理想中的存儲器：容量更大、速度更快、價格更便宜的非易失性存儲器。

實(shí)際中的存儲器：

操作系統(tǒng)的存儲抽象：

虛擬存儲需求：

原因：計算機(jī)系統(tǒng)時常出現(xiàn)內(nèi)存空間不夠用

解決辦法：

覆蓋（overlay）：應(yīng)用程序手動把需要的指令和數(shù)據(jù)保存在內(nèi)存中

交換（swapping）：操作系統(tǒng)自動把暫時不能執(zhí)行的程序保存到外存中

虛擬存儲：在有限容量的內(nèi)存中，以頁為單位自動裝入更多更大的程序

8.2覆蓋和交換技術(shù)

8.2.1覆蓋技術(shù)

■ 目標(biāo)：在較小的可用內(nèi)存中運(yùn)行較大的程序

■ 方法：依據(jù)程序邏輯結(jié)構(gòu)，將程序劃分為若干功能相對獨(dú)立

的模塊；將不會同時執(zhí)行的模塊共享同一塊內(nèi)存區(qū)域

? （1）必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存

? （2）可選部分（不常用功能）放在其他程序模塊中,只在需要用到時裝入內(nèi)存

? （3）不存在調(diào)用關(guān)系的模塊可相互覆蓋，共用同一塊內(nèi)存區(qū)域

注：不存在相互調(diào)用關(guān)系可以分成一個覆蓋區(qū)

不足：

（1）增加編程困難

? ? ? ? ? ? 1）需程序員劃分功能模塊，并確定模塊間的覆蓋關(guān)系

? ? ? ? ? 2）增加了編程的復(fù)雜度；

（2）增加執(zhí)行時間

? ? ? ? ? 1）從外存裝入覆蓋模塊

? ? ? ? ? 2）時間換空間

8.2.2交換技術(shù)

目標(biāo)：增加正在運(yùn)行或需要運(yùn)行的程序的內(nèi)存

實(shí)現(xiàn)方法：

可將暫時不能運(yùn)行的程序放到外存；

換入換出的基本單位（整個進(jìn)程的地址空間）；

換出（swap out）：把一個進(jìn)程的整個地址空間保存到外存；

換入（swap in）：將外存中某進(jìn)程的地址空間讀入到內(nèi)存；

交換技術(shù)面臨的問題

■ 交換時機(jī)：何時需要發(fā)生交換？

? ? ? ? ? 只當(dāng)內(nèi)存空間不夠或有不夠的可能時換出

■ 交換區(qū)大小

? ? ? ? ?存放所有用戶進(jìn)程的所有內(nèi)存映像的拷貝

■ 程序換入時的重定位：換出后再換入時要放 在原處嗎？

? ? ? ? ?采用動態(tài)地址映射的方法

覆蓋與交換的比較

■ 覆蓋

只能發(fā)生在沒有調(diào)用關(guān)系的模塊間

程序員須給出模塊間的邏輯覆蓋結(jié)構(gòu)

發(fā)生在運(yùn)行程序的內(nèi)部模塊間

■ 交換

以進(jìn)程為單位

不需要模塊間的邏輯覆蓋結(jié)構(gòu)

發(fā)生在內(nèi)存進(jìn)程間

8.3局部性原理

8.3.1虛擬存儲技術(shù)的目標(biāo)：

■ 只把部分程序放到內(nèi)存中，從而運(yùn)行比物理內(nèi)存大的程序

由操作系統(tǒng)自動完成，無需程序員的干涉

■ 實(shí)現(xiàn)進(jìn)程在內(nèi)存與外存之間的交換，從而獲得更多的空閑內(nèi)存空間

在內(nèi)存和外存之間只交換進(jìn)程的部分內(nèi)容

8.3.2局部性原理（principle of locality）：

■ 程序在執(zhí)行過程中的一個較短時期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域

·時間局部性

一條指令的一次執(zhí)行和下次執(zhí)行，一個數(shù)據(jù)的一次訪問和下次訪問都集中在一個較短時期內(nèi)

·空間局部性

當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問的數(shù)據(jù)和鄰近的幾個數(shù)據(jù)都集中在一個較小區(qū)域內(nèi)

·分支局部性

一條跳轉(zhuǎn)指令的兩次執(zhí)行，很可能跳到相同的內(nèi)存位置

■ 局部性原理的意義

從理論上來說，虛擬存儲技術(shù)是能夠?qū)崿F(xiàn)的，而且可取得滿意的效果

8.4虛擬存儲概念

基本概念：

■思路

將不常用的部分內(nèi)存塊暫存到外存

■原理：

裝載程序時

只將當(dāng)前指令執(zhí)行需要的部分頁面或段裝入內(nèi)存

指令執(zhí)行中需要的指令或數(shù)據(jù)不在內(nèi)存（稱為缺頁或缺段）時

處理器通知操作系統(tǒng)將相應(yīng)的頁面或段調(diào)入內(nèi)存

操作系統(tǒng)將內(nèi)存中暫時不用的頁面或段保存到外存

■ 實(shí)現(xiàn)方式

虛擬頁式存儲

虛擬段式存儲

基本特征

■ 不連續(xù)性：

物理內(nèi)存分配非連續(xù)

虛擬地址空間使用非連續(xù)

■ 大用戶空間

提供給用戶的虛擬內(nèi)存可大于實(shí)際的物理內(nèi)存

■ 部分交換

虛擬存儲只對部分虛擬地址空間進(jìn)行調(diào)入和調(diào)出

支持技術(shù)

■ 硬件： 頁式或短時存儲中的地址轉(zhuǎn)換機(jī)制

■ 操作系統(tǒng)： 管理內(nèi)存和外存間頁面或段的換入和換出

8.5虛擬頁存儲

■ 在頁式存儲管理的基礎(chǔ)上，增加請求調(diào)頁和頁面置換

■ 思路

1當(dāng)用戶程序要裝載到內(nèi)存運(yùn)行時，只裝入部分頁面，就啟動程序運(yùn)行；

2進(jìn)程在運(yùn)行中發(fā)現(xiàn)有需要的代碼或數(shù)據(jù)不在內(nèi)存時，則向系統(tǒng)發(fā)出缺頁異常請求；

3操作系統(tǒng)在處理缺頁異常時，將外存中相應(yīng)的頁面調(diào)入內(nèi)存，使得進(jìn)程能繼續(xù)運(yùn)行；

8.5.1虛擬頁式存儲中的地址轉(zhuǎn)換

執(zhí)行到相應(yīng)頁表，標(biāo)志位表示缺頁異常，操作系統(tǒng)來接管異常，操作系統(tǒng)要做的事情呢是找頁把它寫好，然后把這個位變成有效

8.5.2虛擬頁式存儲中的頁表項(xiàng)結(jié)構(gòu)

駐留位：表示該頁是否在內(nèi)存

1表示該頁位于內(nèi)存中，該頁表項(xiàng)是有效的，可以使用

0表示該頁當(dāng)前在外存中，訪問該頁表項(xiàng)將導(dǎo)致缺頁異常

修改位：表示在內(nèi)存中的該頁是否被修改過

回收該物理頁面時，據(jù)此判斷是否要把它的內(nèi)容寫回外存

訪問位：表示該頁面是否被訪問過（讀或?qū)懀?/p>

用于頁面置換算法

保護(hù)位：表示該頁的允許訪問方式

只讀、可讀寫、可執(zhí)行等

8.6缺頁異常

8.6.1缺頁異常（缺頁中斷）的處理流程

（1）在內(nèi)存中有空閑物理頁面時，分配一物理頁幀f，轉(zhuǎn)第E步；

（2）依據(jù)頁面置換算法選擇將被替換的物理頁幀f，對應(yīng)邏輯頁q；

（3）如q被修改過，則把它寫回外存；

（4）修改q的頁表項(xiàng)中駐留位置為0；

（5）將需要訪問的頁p裝入到物理頁面f；

（6）修改p的頁表項(xiàng)駐留位為1,物理頁幀號為f；

（7）重新執(zhí)行產(chǎn)生缺頁的指令

8.6.2虛擬頁式存儲中的外存管理

在何處保存未被映射的頁？

1應(yīng)能方便地找到在外存中的頁面內(nèi)容

2交換空間（磁盤或者文件）

采用特殊格式存儲未被映射的頁面

注：可以用一個文件來存這些未被映射的頁

虛擬頁式存儲中的外存選擇

1代碼段：可執(zhí)行二進(jìn)制文件（代碼指向相應(yīng)的可執(zhí)行文件）

2動態(tài)加載的共享庫程序段：動態(tài)調(diào)用的庫文件（共享庫也有相應(yīng)的目標(biāo)文件，所以上兩項(xiàng)不改）

3其它段：交換空間（數(shù)據(jù)段，堆棧）

虛擬頁式存儲管理的性能

有效存儲訪問時間（effective memory access time EAT）

EAT =訪存時間* (1-p) +缺頁異常處理時間*缺頁率p

9.1頁面置換算法的概念

9.1.1置換算法的功能和目標(biāo)

功能：當(dāng)出現(xiàn)缺頁異常，需調(diào)入新頁面而內(nèi)存已滿時，置換算法選擇被置換的物理頁面；

設(shè)計目標(biāo)：1盡可能減少頁面的調(diào)入調(diào)出次數(shù)；2把未來不再訪問或短期內(nèi)不訪問的頁面調(diào)出

頁面鎖定(frame locking)（有些頁面必須在內(nèi)存里面）

1描述必須常駐內(nèi)存的邏輯頁面

2操作系統(tǒng)的關(guān)鍵部分

3要求響應(yīng)速度的代碼和數(shù)據(jù)

4頁表中的鎖定標(biāo)志位(lock bit)

9.1.2置換算法的評價方法

9.1.3頁面置換算法分類

■ 局部頁面置換算法

置換頁面的選擇范圍僅限于當(dāng)前進(jìn)程占用的物理頁面內(nèi)

最優(yōu)算法、先進(jìn)先出算法、最近最久未使用算法

時鐘算法、最不常用算法

■ 全局頁面置換算法

置換頁面的選擇范圍是所有可換出的物理頁面

工作集算法、缺頁率算法

9.2頁面置換算法總結(jié)

9.2.1最優(yōu)頁面置換算法(OPT, optimal)

基本思路：置換在未來最長時間不訪問的頁面

算法實(shí)現(xiàn):

1缺頁時，計算內(nèi)存中每個邏輯頁面的下一次訪問時間

2選擇未來最長時間不訪問的頁面

算法特征

1缺頁最少，是理想情況

2實(shí)際系統(tǒng)中無法實(shí)現(xiàn)

3無法預(yù)知每個頁面在下次訪問前的等待時間

4這個算法可以作為置換算法的性能評價依據(jù)

（實(shí)際使用：在模擬器上運(yùn)行某個程序，并記錄每一次的頁面訪問情況,第二遍運(yùn)行時使用最優(yōu)算法）

9.2.2先進(jìn)先出算法（First-In First-Out, FIFO）

基本思路：選擇在內(nèi)存駐留時間最長的頁面進(jìn)行置換

算法實(shí)現(xiàn):

1維護(hù)一個記錄所有位于內(nèi)存中的邏輯頁面鏈表

2鏈表元素按駐留內(nèi)存的時間排序，鏈?zhǔn)鬃铋L，鏈尾最短

3出現(xiàn)缺頁時，選擇鏈?zhǔn)醉撁孢M(jìn)行置換，新頁面加到鏈尾

算法特征

1實(shí)現(xiàn)簡單

2性能較差，調(diào)出的頁面可能是經(jīng)常訪問的

3進(jìn)程分配物理頁面數(shù)增加時，缺頁并不一定減少(Belady現(xiàn)象)

4很少單獨(dú)使用

9.2.3最近最久未使用算法(Least Recently Used, LRU)

基本思路：

1選擇最長時間沒有被引用的頁面進(jìn)行置換

2如某些頁面長時間未被訪問，則它們在將來還可能會長時間不會訪問

算法實(shí)現(xiàn):

1缺頁時，計算內(nèi)存中每個邏輯頁面的上一次訪問時間

2選擇上一次使用到當(dāng)前時間最長的頁面

算法特征

最優(yōu)置換算法的一種近似

LRU算法的可能實(shí)現(xiàn)方法

頁面鏈表

·系統(tǒng)維護(hù)一個按最近一次訪問時間排序的頁面鏈表

鏈表首節(jié)點(diǎn)是最近剛剛使用過的頁面

鏈表尾節(jié)點(diǎn)是最久未使用的頁面

·訪問內(nèi)存時，找到相應(yīng)頁面，并把它移到鏈表之首

·缺頁時，置換鏈表尾節(jié)點(diǎn)的頁面

活動頁面棧

·訪問頁面時，將此頁號壓入棧頂，并棧內(nèi)相同的頁號抽出

·缺頁時，置換棧底的頁面

特征

·開銷比較大

9.2.4時鐘置換算法（Clock）

基本思路：

僅對頁面的訪問情況進(jìn)行大致統(tǒng)計

數(shù)據(jù)結(jié)構(gòu):

1在頁表項(xiàng)中增加訪問位，描述頁面在過去一段時間的內(nèi)訪問情況

2各頁面組織成環(huán)形鏈表

3指針指向最先調(diào)入的頁面

算法實(shí)現(xiàn)：

1訪問頁面時，在頁表項(xiàng)記錄頁面訪問情況

2缺頁時，從指針處開始順序查找未被訪問的頁面進(jìn)行置換

算法特征：

時鐘算法是LRU和FIFO的折中

時鐘置換算法的實(shí)現(xiàn)：

■ 頁面裝入內(nèi)存時，訪問位初始化為0

■ 訪問頁面（讀/寫)時，訪問位置1

■ 缺頁時，從指針當(dāng)前位置順序檢查環(huán)形鏈表

·訪問位為0，則置換該頁

·訪問位為1，則訪問位置0，并指針移動到下一個頁面，直到找到可置換的頁面

9.2.5改進(jìn)的Clock算法

基本思路：

減少修改頁的缺頁處理開銷

算法實(shí)現(xiàn)：

1在頁面中增加修改位，并在訪問時進(jìn)行相應(yīng)修改

2缺頁時，修改頁面標(biāo)志位，以跳過有修改的頁面

9.2.6最不常用算法（Least Frequently Used, LFU）

基本思路：

缺頁時，置換訪問次數(shù)最少的頁面

算法實(shí)現(xiàn)：

1每個頁面設(shè)置一個訪問計數(shù)（多位計數(shù)）

2訪問頁面時，訪問計數(shù)加1

3缺頁時，置換計數(shù)最小的頁面

算法特征：

1算法開銷大

2開始時頻繁使用，但以后不使用的頁面很難置換

解決方法：計數(shù)定期右移、衰減

LRU和LFU的區(qū)別

·LRU關(guān)注多久未訪問,時間越短越好

·LFU關(guān)注訪問次數(shù)，次數(shù)越多越好

9.2.7Belady現(xiàn)象

現(xiàn)象：采用FIFO等算法時，可能出現(xiàn)分配的物理頁面數(shù)增加，缺頁次數(shù)反而升高的異常現(xiàn)象

原因：

1FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動態(tài)特征矛盾

2被它置換出去的頁面并不一定是進(jìn)程近期不會訪問的

哪些置換算法沒有Belady現(xiàn)象？

時鐘(CLOCK)置換算法，最近最久未使用（LRU）算法，最佳置換算法（OPT）

時鐘/改進(jìn)的時鐘頁面置換是否有Belady現(xiàn)象？

沒有

為什么LRU頁面置換算法沒有Belady現(xiàn)象？

對于每一時刻，下一步訪問的頁面我們也是已知的。當(dāng)N=n+1時，如果下一步會產(chǎn)生缺頁，說明下一步會訪問的頁面不在這n+1個頁面中。假設(shè)這n+1個頁面的集合為W，則當(dāng)N=n時，內(nèi)存中的頁面是W的一個子集。如果一個元素都不在W中，那么也肯定不存在于W的子集中。反之如果一個元素不存在于W的子集合中，不一定不存在W中。

所以N=n+1時會出現(xiàn)缺頁的情況，在N=n時一定缺頁。N=n缺頁時，N=n+1不一定缺頁。所以S一定時，f關(guān)于N單調(diào)遞減。

LRU一般都有棧的特性，一個N+1大小的cache很自然的就包含了大小為N的cache的內(nèi)容。所以隨著cache大小增加，hit rate要么不變，要么提高。

9.2.8LRU、FIFO和Clock的比較

■LRU算法和FIFO本質(zhì)上都是先進(jìn)先出的思路

LRU依據(jù)頁面的最近訪問時間排序

LRU需要動態(tài)地調(diào)整順序

FIFO依據(jù)頁面進(jìn)入內(nèi)存的時間排序

FIFO依據(jù)頁面進(jìn)入內(nèi)存的時間排序

■LRU可退化成FIFO

如頁面進(jìn)入內(nèi)存后沒有被訪問，最近訪問時間與進(jìn)入內(nèi)存的時間相同

例如：給進(jìn)程分配3個物理頁面，邏輯頁面的訪問順序?yàn)?、2、3、4、5、6、1、2、3…

■LRU算法性能較好，但系統(tǒng)開銷較大

■FIFO算法系統(tǒng)開銷較小，會發(fā)生Belady現(xiàn)象

■Clock算法是它們的折衷

頁面訪問時，不動態(tài)調(diào)整頁面在鏈表中的順序，僅做標(biāo)記

缺頁時，再把它移動到鏈表末尾

■對于未被訪問的頁面，Clock和LRU算法的表現(xiàn)一樣好

（注：和fifo也一樣了，沒有之前參考的信息）

■對于被訪問過的頁面，Clock算法不能記錄準(zhǔn)確訪問順序，而LRU算法可以

9.3全局頁面置換算法

■ 思路：全局置換算法為進(jìn)程分配可變數(shù)目的物理頁面

■ 全局置換算法要解決的問題

1進(jìn)程在不同階段的內(nèi)存需求是變化的

2分配給進(jìn)程的內(nèi)存也需要在不同階段有所變化

3全局置換算法需要確定分配給進(jìn)程的物理頁面數(shù)

CPU利用率與并發(fā)進(jìn)程數(shù)的關(guān)系

■CPU利用率與并發(fā)進(jìn)程數(shù)存在相互促進(jìn)和制約的關(guān)系

進(jìn)程數(shù)少時，提高并發(fā)進(jìn)程數(shù)，可提高CPU利用率

并發(fā)進(jìn)程導(dǎo)致內(nèi)存訪問增加

并發(fā)進(jìn)程的內(nèi)存訪問會降低了訪存的局部性特征

局部性特征的下降會導(dǎo)致缺頁率上升和CPU利用率下降

9.3.1工作集

一個進(jìn)程當(dāng)前正在使用的邏輯頁面集合，可表示為二元函數(shù)W(t,D)

·t是當(dāng)前的執(zhí)行時刻

D 稱為工作集窗口（working-set window），即一個定長的頁面訪問時間窗口

W(t,D)是指在當(dāng)前時刻t前的 D時間窗口中的所有訪問頁面所組成的集合

| W(t,D) |指工作集的大小，即頁面數(shù)目

W(t,D)={時間窗內(nèi)所以頁面的集合}

工作集的變化

■進(jìn)程開始執(zhí)行后，隨著訪問新頁面逐步建立較穩(wěn)定的工作集

■當(dāng)內(nèi)存訪問的局部性區(qū)域的位置大致穩(wěn)定時，工作集大小也大致穩(wěn)定

■局部性區(qū)域的位置改變時，工作集快速擴(kuò)張和收縮過渡到下一個穩(wěn)定值

常駐集

在當(dāng)前時刻，進(jìn)程實(shí)際駐留在內(nèi)存當(dāng)中的頁面集合

■工作集與常駐集的關(guān)系

工作集是進(jìn)程在運(yùn)行過程中固有的性質(zhì)

常駐集取決于系統(tǒng)分配給進(jìn)程的物理頁面數(shù)目和頁面置換算法

■缺頁率與常駐集的關(guān)系

常駐集包含工作集時，缺頁較少

工作集發(fā)生劇烈變動（過渡）時，缺頁較多

進(jìn)程常駐集大小達(dá)到一定數(shù)目后，缺頁率也不會明顯下降

9.3.2工作集置換算法

■思路：換出不在工作集中的頁面

■窗口大小τ：當(dāng)前時刻前τ個內(nèi)存訪問的頁引用是工作集，τ被稱為窗口大小

■實(shí)現(xiàn)方法（開銷也大）

·訪存鏈表：維護(hù)窗口內(nèi)的訪存頁面鏈表

·訪存時，換出不在工作集的頁面；更新訪存鏈表

·缺頁時，換入頁面；更新訪存鏈表

超過工作集窗口大小的頁面及調(diào)出，例如a，時間4的時候已經(jīng)過了窗口大小所以換出。

9.3.3缺頁率置換算法（PFF, Page-Fault-Frequency）

缺頁率（兩種表示方式）

1缺頁次數(shù)/內(nèi)存訪問次數(shù)

1缺頁平均時間間隔的倒數(shù)（一般使用這個）

影響缺頁率的因素

頁面置換算法（可控）

分配給進(jìn)程的物理頁面數(shù)目

頁面大小

程序的編寫方法（可控）

缺頁率置換算法（PFF, Page-Fault-Frequency）

通過調(diào)節(jié)常駐集大小，使每個進(jìn)程的缺頁率保持在一個合理的范圍內(nèi)

·若進(jìn)程缺頁率過高，則增加常駐集以分配更多的物理頁面

·若進(jìn)程缺頁率過低，則減少常駐集以減少它的物理頁面數(shù)

缺頁率置換算法的實(shí)現(xiàn)

■訪存時，設(shè)置引用位標(biāo)志

■缺頁時，計算從上次缺頁時間tlast到現(xiàn)在tcurrent的時間間隔

如果t_current–t_last>T,則置換所有在[tlast , ?tcurrent ]時間內(nèi)沒有被引用的頁(缺頁率比較低，把不用的置換出去)

如果t_current–t_last≤T,則增加缺失頁到工作集中

9.4抖動和負(fù)載控制

9.4.1抖動問題(thrashing)

■抖動

進(jìn)程物理頁面太少，不能包含工作集

造成大量缺頁，頻繁置換

進(jìn)程運(yùn)行速度變慢

■產(chǎn)生抖動的原因

隨著駐留內(nèi)存的進(jìn)程數(shù)目增加，分配給每個進(jìn)程的物理頁面數(shù)不斷減小，缺頁率不斷上升

■操作系統(tǒng)需在并發(fā)水平和缺頁率之間達(dá)到一個平衡

選擇一個適當(dāng)?shù)倪M(jìn)程數(shù)目和進(jìn)程需要的物理頁面數(shù)

9.4.2負(fù)載控制

■通過調(diào)節(jié)并發(fā)進(jìn)程數(shù)（MPL）來進(jìn)行系統(tǒng)負(fù)載控制

平均缺頁間隔時間(MTBF) =缺頁異常處理時間(PFST)：

實(shí)際上我們利用第二條豎線，缺頁之后，有一個缺頁出現(xiàn)的平均間隔和缺頁處理的時間，這兩個構(gòu)成一個比例，如果間隔大于處理時間，cpu是能夠處理的，就在Ni/o點(diǎn)之前，如果間隔小于處理時間，cpu基本上就滿負(fù)荷的去做處理還忙不過來了， 對于這種情況就已經(jīng)到了這條線的底下了