虛擬存儲(chǔ)器概述

普通存儲(chǔ)器管理方式很難處理的兩個(gè)問題

有些作業(yè)很大菊匿，其所要求的內(nèi)存容量超過了物理內(nèi)存的大小，所以該作業(yè)無法在機(jī)器上執(zhí)行；

有大量作業(yè)要求進(jìn)行段磨，其內(nèi)存所需容量之和超過了物理內(nèi)存的大小蜡豹，在普通存儲(chǔ)器的管理方式下，只能讓少量作業(yè)先運(yùn)行，其他作業(yè)在外存上等待調(diào)度；

可以理解的是，普通存儲(chǔ)器管理方式對(duì)這兩個(gè)問題的處理都沒有提高系統(tǒng)的吞吐量和資源的利用效率说订，而這是操作系統(tǒng)的重要目的之二；

常規(guī)存儲(chǔ)器管理方式的兩個(gè)特點(diǎn)

一次性：是指作業(yè)內(nèi)容必須全部裝入內(nèi)存后育韩，程序才能開始執(zhí)行克蚂；這樣的做法使得大作業(yè)無法在小內(nèi)存中運(yùn)行，即問題1筋讨，同時(shí)也限制了進(jìn)一步提高程序的多道并發(fā)度埃叭，直接限制了對(duì)處理機(jī)的利用率和系統(tǒng)吞吐量的提高；

駐留性：是指悉罕，作業(yè)一旦進(jìn)入內(nèi)存赤屋，直至作業(yè)運(yùn)行結(jié)束都不會(huì)調(diào)出，即便發(fā)生了IO阻塞事件壁袄，進(jìn)程長(zhǎng)期處于等待狀態(tài)类早，或者某些模塊運(yùn)行過一次之后就不在需要運(yùn)行了，它們都將留在內(nèi)存中嗜逻，占有寶貴的內(nèi)存空間涩僻；

駐留性和一次性使得內(nèi)存中存有不少用不到或者暫時(shí)用不到的程序或者數(shù)據(jù)，如果能將這些用不到的數(shù)據(jù)暫時(shí)換出栈顷，就能提高資源的利用率逆日，提高系統(tǒng)的吞吐量。實(shí)際山萄凤，一次性和駐留性是可以解決的室抽，而解決的理論就是：局部性原理；

局部性原理

程序在執(zhí)行時(shí)將呈現(xiàn)出局部性規(guī)律靡努，在一較短的時(shí)間內(nèi)坪圾，程序的執(zhí)行僅局限于某個(gè)部分，相應(yīng)的惑朦，它所需要訪問的內(nèi)存空間也會(huì)局限于某個(gè)區(qū)域兽泄，支持論點(diǎn)有：

程序執(zhí)行時(shí)，處理少部分的轉(zhuǎn)移和過程調(diào)用指令外漾月，大多數(shù)情況下是順序執(zhí)行的病梢；

過程調(diào)用將會(huì)使程序的執(zhí)行軌跡有一個(gè)區(qū)域跳轉(zhuǎn)到另一個(gè)區(qū)域，但是過程調(diào)用的深度一般情況下不超過5栅屏，這就是說飘千，程序的執(zhí)行仍然局限于這些過程的范圍之內(nèi)且該范圍不會(huì)很大；

程序中存在大量循環(huán)結(jié)構(gòu)栈雳，這些結(jié)構(gòu)僅有少量指令構(gòu)成护奈，但是它們將被執(zhí)行多次；

程序中還包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理哥纫，如對(duì)數(shù)組的處理霉旗，這些處理往往都局限于很小的空間內(nèi)；

實(shí)際上蛀骇，局部性原理又分為：

時(shí)間局部性：如果程序中某條指令被執(zhí)行過厌秒，那么在不久的將來該指令很有可能會(huì)被再次執(zhí)行；如果某個(gè)數(shù)據(jù)被訪問過擅憔，那么在不久的將來鸵闪，該數(shù)據(jù)很有可能會(huì)被再次訪問；這是因?yàn)檎擖c(diǎn)3暑诸，即大量循環(huán)操作蚌讼；

空間局部性：如果程序訪問了某個(gè)存儲(chǔ)單元，那么不久的將來程序?qū)⒃L問該程序單元附近的程序單元个榕；這是因?yàn)檎擖c(diǎn)1,2,4篡石；

虛擬存儲(chǔ)器的基本工作原理

虛擬存儲(chǔ)器基于局部性原理，在不將所有程序內(nèi)容裝入內(nèi)存的情況下西采，僅調(diào)入程序開始執(zhí)行所需要的部分內(nèi)容即啟動(dòng)程序凰萨，其余內(nèi)容仍然駐留外存；當(dāng)程序所需要的內(nèi)容不在內(nèi)存上時(shí)械馆，就發(fā)出中斷請(qǐng)求胖眷，由系統(tǒng)將其調(diào)入內(nèi)存；如果此時(shí)內(nèi)存已滿狱杰，則由系統(tǒng)根據(jù)某種算法換出一部分內(nèi)存空間上的內(nèi)容瘦材，從而接納新調(diào)入的指令和數(shù)據(jù)；這樣就解決了常規(guī)存儲(chǔ)器管理方式不易處理的兩個(gè)問題仿畸；

虛擬存儲(chǔ)器的定義食棕、特征及其實(shí)現(xiàn)方式

虛擬存儲(chǔ)器的定義

虛擬存儲(chǔ)器使得有較大內(nèi)存空間需求的程序可以運(yùn)行在較小內(nèi)存空間的機(jī)器上，使得用戶可以所感覺到的內(nèi)存容量比實(shí)際容量大的一種存儲(chǔ)器管理方式错沽，因?yàn)橛脩舢a(chǎn)生了這種“錯(cuò)覺”簿晓，是一種虛擬擴(kuò)展內(nèi)存容量的方法，故稱為虛擬存儲(chǔ)器技術(shù)千埃；

實(shí)際上憔儿，虛擬存儲(chǔ)器管理技術(shù)是指具有請(qǐng)求調(diào)入功能和置換功能，從而在邏輯上擴(kuò)展內(nèi)存容量的一種存儲(chǔ)器系統(tǒng)放可，其邏輯容量由內(nèi)存容量和外存容量共同決定谒臼，其運(yùn)行速度接近內(nèi)存的速度朝刊，而每位的平均成本接近于外存。是一種性能非常優(yōu)越的存儲(chǔ)器管理技術(shù)蜈缤；

虛擬存儲(chǔ)器的特征

與常規(guī)存儲(chǔ)器管理方式相比拾氓，虛擬存儲(chǔ)器技術(shù)有以下幾個(gè)特點(diǎn)：

多次性：是指程序的內(nèi)容是多次調(diào)入內(nèi)存空間，在程序開始時(shí)僅調(diào)入當(dāng)時(shí)所需要的部分代碼和數(shù)據(jù)底哥，其余駐留外存咙鞍，當(dāng)發(fā)生缺失中斷時(shí)再?gòu)耐獯嬷姓{(diào)入 。

對(duì)換性：程序和代碼無需常駐內(nèi)存趾徽，當(dāng)某一部分不再需要時(shí)就將其對(duì)換到外存中续滋，從而釋放其占有的內(nèi)存空間，當(dāng)再次需要時(shí)再?gòu)耐獯嬷姓{(diào)入即可孵奶，對(duì)換性也是多次性的基礎(chǔ)疲酌，如果沒有對(duì)換功能，那么再調(diào)入外存中的內(nèi)容時(shí)就有可能因?yàn)閮?nèi)存空間使用完畢而失敗了袁，系統(tǒng)無法正常工作也就談不上邏輯擴(kuò)充內(nèi)存容量了徐勃。

虛擬性：虛擬性則是說， 用戶看到的內(nèi)存容量遠(yuǎn)遠(yuǎn)大于實(shí)際的容量早像。虛擬性以多次性和對(duì)換性為基礎(chǔ)僻肖；而多次性和對(duì)換性又以離散分配為基礎(chǔ)

虛擬存儲(chǔ)器的實(shí)現(xiàn)方法

虛擬存儲(chǔ)器的實(shí)現(xiàn)常見方法有：

分頁請(qǐng)求系統(tǒng)：在分頁系統(tǒng)的基礎(chǔ)上增加請(qǐng)求調(diào)入和頁面置換功能所形成的虛擬存儲(chǔ)系統(tǒng)。系統(tǒng)需要提供必要的硬件和軟件來支持請(qǐng)求分頁的實(shí)現(xiàn)卢鹦；

分段請(qǐng)求系統(tǒng)：在分段系統(tǒng)的基礎(chǔ)上增加請(qǐng)求調(diào)入和頁面置換功能所形成的虛擬存儲(chǔ)系統(tǒng)臀脏。系統(tǒng)同樣需要提供必要的硬件和軟件來支持請(qǐng)求分頁的實(shí)現(xiàn)；

段頁式虛擬存儲(chǔ)器系統(tǒng)：在段頁式系統(tǒng)的基礎(chǔ)上通過增加請(qǐng)求調(diào)入和置換功能所形成的虛擬存儲(chǔ)系統(tǒng)冀自。

請(qǐng)求分頁存儲(chǔ)管理方式

請(qǐng)求分頁存儲(chǔ)管理方式在基礎(chǔ)的分頁基礎(chǔ)上通過增加請(qǐng)求調(diào)頁功能和頁面置換功能而形成揉稚，由于每次調(diào)入和置換出的都是長(zhǎng)度固定的頁面，所以其實(shí)現(xiàn)比較簡(jiǎn)單熬粗，因此也是最為常用的一種虛擬存儲(chǔ)器實(shí)現(xiàn)方式搀玖；

請(qǐng)求分頁中的硬件支持

請(qǐng)求頁表機(jī)制：

請(qǐng)求分頁系統(tǒng)使用請(qǐng)求頁表來建立頁和物理塊之間的關(guān)聯(lián)；頁表項(xiàng)的結(jié)構(gòu)相比分頁系統(tǒng)中的頁表項(xiàng)結(jié)構(gòu)也有變化驻呐，其增加了四個(gè)字段：狀態(tài)位灌诅、訪問字段、修改位含末、外存地址猜拾，原有的兩個(gè)字段是頁號(hào)和物理塊地址；各字段的含義如下：

狀態(tài)位標(biāo)志該頁面是否已調(diào)入內(nèi)存佣盒；

訪問字段用于記錄置換算法所需要的信息挎袜，常記錄在一段時(shí)間內(nèi)的訪問次數(shù)；

修改位表示該頁面內(nèi)容是否被修改，如果沒有被修改盯仪，在換出的時(shí)候就不需要重寫入磁盤啦紊搪；

外存地址表示該頁面在外存中的地址，通常是物理塊號(hào)全景，供調(diào)入頁面時(shí)使用嗦明；

請(qǐng)求分頁中的缺頁中斷機(jī)制：

在請(qǐng)求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存中時(shí)蚪燕，便產(chǎn)生一個(gè)缺頁中斷，請(qǐng)求OS將所缺頁面調(diào)入內(nèi)存奔浅。缺頁中斷作為中斷中的一種馆纳，其處理過程也要經(jīng)過：保護(hù)CPU環(huán)境、分析中斷原因汹桦、轉(zhuǎn)入中斷處理程序鲁驶、恢復(fù)CPU環(huán)境等步驟；但是缺頁中斷是一種特殊的中斷舞骆，其與一般的中斷有以下兩個(gè)區(qū)別：

一般中斷是在指令執(zhí)行完畢后钥弯，才檢查是否有中斷請(qǐng)求到達(dá)，但是缺頁中斷信號(hào)卻是在指令執(zhí)行期間發(fā)生督禽，當(dāng)所需要的指令不在內(nèi)存中時(shí)脆霎，便立即產(chǎn)生缺頁中斷信號(hào)，以便能及時(shí)調(diào)入所缺頁面狈惫；

一條指令的執(zhí)行過程中可能產(chǎn)生多次缺頁中斷睛蛛；

地址轉(zhuǎn)換方式：

首先檢查快表，試圖從中找出要訪問的頁胧谈，若找到忆肾，那么修改頁表項(xiàng)中的訪問位，對(duì)于寫指令菱肖，還需要修改修改位客冈，然后利用頁表項(xiàng)中的物理塊號(hào)和指令中的頁內(nèi)地址形成物理地址；如果沒有在快表里找到稳强，那么就根據(jù)頁號(hào)從頁表里找到對(duì)應(yīng)的頁表項(xiàng)场仲，檢查其狀態(tài)位，如果其不在內(nèi)存中退疫，則將其調(diào)入內(nèi)存燎窘，之后將其放入快表；如果快表已滿蹄咖，則根據(jù)一定算法置換出去一些緩沖項(xiàng)褐健，之后從頁表項(xiàng)中讀出物理塊號(hào)，配合指令中的頁內(nèi)地址得到數(shù)據(jù)的實(shí)際位置，如果是寫指令蚜迅，還需要修改修改位舵匾；同時(shí)更新頁表項(xiàng)中的訪問字段，為置換算法提供依據(jù)谁不；

請(qǐng)求分頁中的內(nèi)存分配

在為進(jìn)程分配內(nèi)存時(shí)坐梯，將涉及三個(gè)問題：第一，為保證進(jìn)程能正常運(yùn)行刹帕，所需要的最少物理塊數(shù)的確定吵血；第二，在為每個(gè)進(jìn)程分配物理塊時(shí)偷溺，應(yīng)該采取怎樣的分配策略蹋辅，即所分配的物理塊是固定的還是可變的；第三挫掏，為不同進(jìn)程所分配物理塊數(shù)侦另，是采取平均分配算法還是根據(jù)進(jìn)程的大小比例分配；

最小物理塊數(shù)的確定

最少物理塊數(shù)是指能保證進(jìn)程正常運(yùn)行所需要的最少物理塊數(shù)尉共，當(dāng)系統(tǒng)為進(jìn)程分配的物理塊數(shù)小于該值時(shí)褒傅，進(jìn)程將無法正常工作；至于該值的確定袄友，與計(jì)算機(jī)的硬件結(jié)構(gòu)相關(guān)殿托，取決于指令的格式、功能和尋址方式剧蚣。比如指令本身的長(zhǎng)度（存儲(chǔ)指令時(shí)需要的空間）碌尔、指令的尋址方式（尋找指令時(shí)需要的空間）等因素；

內(nèi)存分配策略

在請(qǐng)求分頁系統(tǒng)中券敌，可采取兩種內(nèi)存分配策略唾戚，即可變分配和固定分配；在進(jìn)行置換時(shí)待诅，可以采取兩種策略叹坦，即全局置換和局部置換；于是可以組合出三種適用的策略：

固定分配局部置換

所謂固定分配是指卑雁，為每個(gè)進(jìn)程分配一組固定數(shù)目的物理塊募书，在程序運(yùn)行期間不再改變；所謂局部置換是指测蹲，如果進(jìn)程在運(yùn)行中發(fā)生缺頁莹捡，只能在分配給進(jìn)程的物理塊間選擇一個(gè)物理塊置換出去；這種策略實(shí)現(xiàn)的難點(diǎn)在于如何確定該為進(jìn)程分配多少個(gè)物理塊扣甲，如果太多篮赢，則浪費(fèi)資源齿椅，如果太少，則頻繁發(fā)生缺頁启泣，甚至系統(tǒng)難以工作涣脚；

可變分配局部置換

所謂可變分配是指，先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊寥茫，在進(jìn)程運(yùn)行期間遣蚀，可根據(jù)情況適當(dāng)增加或者減少進(jìn)程擁有的物理塊；局部置換是指纱耻，如果進(jìn)程在運(yùn)行期間發(fā)現(xiàn)缺頁芭梯，則根據(jù)一定算法，從該進(jìn)程所占有的物理塊中置換出去一個(gè)物理塊弄喘，然后將所缺少的頁面調(diào)入玖喘；當(dāng)進(jìn)程在運(yùn)行過程中頻繁發(fā)生缺頁時(shí)便再為該進(jìn)程分配若干物理塊，直至該進(jìn)程的缺頁率降低到合適程度為止限次；

可變分配全局置換

所謂可變分配是指，先為每個(gè)進(jìn)程分配一定數(shù)目的物理塊柴灯，在進(jìn)程運(yùn)行期間卖漫，可根據(jù)情況適當(dāng)增加或者減少進(jìn)程擁有的物理塊；全局置換是指赠群，如果進(jìn)程在運(yùn)行期間發(fā)現(xiàn)缺頁羊始，則從OS保留的所有空閑物理塊中取出一塊分配給該進(jìn)程，如果沒有空閑物理塊查描，那么根據(jù)一定算法置換出去一個(gè)物理塊突委，然后將所缺少的頁面調(diào)入；這是最容易實(shí)現(xiàn)的一種內(nèi)存分配策略冬三；這是最容易實(shí)現(xiàn)的一種內(nèi)存分配策略匀油；

物理塊分配算法

平均分配算法：將物理塊平均分配給所有進(jìn)程，每個(gè)進(jìn)程勾笆，無論其他屬性敌蚜，得到相同數(shù)量的物理塊；

按比例分配：將物理塊以進(jìn)程的大小按比例分配給各個(gè)進(jìn)程窝爪；

按優(yōu)先權(quán)分配算法：將物理塊以進(jìn)程緊急程度（優(yōu)先權(quán)的大谐诔怠）為依據(jù)分配給各個(gè)進(jìn)程

頁面調(diào)入策略

關(guān)于頁面調(diào)入，需要解決兩個(gè)問題：什么時(shí)候調(diào)入以及從何處調(diào)入

什么時(shí)候調(diào)入

為了確定系統(tǒng)將進(jìn)程所缺少頁面調(diào)入內(nèi)存的時(shí)機(jī)蒲每，可以采取預(yù)調(diào)頁策略或者請(qǐng)求調(diào)頁策略

預(yù)調(diào)頁策略纷跛。如果進(jìn)程的許多頁存放在外存的一個(gè)連續(xù)區(qū)域里，那么一次性調(diào)入若干個(gè)相鄰的頁面將比一次調(diào)入一個(gè)頁面更高效邀杏；但是如果調(diào)入的頁面在將來沒有被訪問贫奠，那么就會(huì)被再次置換出去，反而降低了效率；所以需要一種以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁策略叮阅，調(diào)入那些不久的將來就會(huì)訪問的頁面刁品，那么效率提升就很明顯了，然而遺憾的是浩姥，現(xiàn)在預(yù)調(diào)頁的成功率僅有50%挑随；

請(qǐng)求調(diào)頁策略。在進(jìn)程運(yùn)行的過程中勒叠，如果發(fā)現(xiàn)需要的指令或者數(shù)據(jù)不在內(nèi)存兜挨，便發(fā)出請(qǐng)求，由OS將其所需要的頁面調(diào)入內(nèi)存眯分，由于請(qǐng)求調(diào)頁策略所調(diào)入的頁面一定會(huì)被訪問拌汇，而且實(shí)現(xiàn)起來比較簡(jiǎn)單，所以大多虛擬存儲(chǔ)器都會(huì)采用這種策略弊决；但是很明顯的是噪舀，這種策略并不高效，因?yàn)橐淮沃徽{(diào)入一個(gè)頁面飘诗；

從何處調(diào)入

分頁系統(tǒng)的外分為兩部分与倡，一部分是用于存放文件的文件區(qū)，另一部分是存放對(duì)換頁面的對(duì)換區(qū)昆稿；通常纺座，對(duì)換區(qū)采用連續(xù)分配的方式，而文件區(qū)采用離散的空間分配方式溉潭，所以從外存中獲得數(shù)據(jù)時(shí)净响，對(duì)換區(qū)要快于文件局。這樣喳瓣，每當(dāng)系統(tǒng)發(fā)生缺頁時(shí)馋贤，將有三種情況：

系統(tǒng)擁有足夠?qū)Q區(qū)，在進(jìn)程運(yùn)行之前畏陕，將所有頁面拷貝到對(duì)換區(qū)掸掸，這樣就可以直接在對(duì)換區(qū)尋找所缺少的頁面了；

系統(tǒng)沒有足夠的空間時(shí)蹭秋，凡是不會(huì)被修改的文件扰付，從文件區(qū)里獲得，因?yàn)樗鼈兺顺鰞?nèi)存時(shí)不需要寫回磁盤仁讨，所以會(huì)直接被抹去羽莺，下次需要的時(shí)候再?gòu)耐鈴闹姓{(diào)入就好；對(duì)于可能被修改的部分洞豁，需要將其調(diào)入的對(duì)換區(qū)盐固，以后需要的時(shí)候就從對(duì)換區(qū)尋找荒给；

Unix系統(tǒng)的方式：因?yàn)樗信c進(jìn)程相關(guān)的文件都放在文件區(qū)，所以凡是未運(yùn)行過的頁面刁卜，放在文件區(qū)志电，需要的時(shí)候也從文件區(qū)調(diào)入；對(duì)于從內(nèi)存中返回的頁面蛔趴，將其放入對(duì)換區(qū)挑辆，下次調(diào)入時(shí)，從對(duì)換區(qū)尋找孝情；因?yàn)閁NIX系統(tǒng)允許共享頁面鱼蝉，所以某個(gè)進(jìn)程需要的頁面可能已被其他進(jìn)程調(diào)入內(nèi)存；

缺頁率：頁面缺失的次數(shù)與頁面訪問次數(shù)的比值為缺頁率箫荡；缺頁率受以下幾個(gè)因素影響

頁面大锌唷：頁面越大，缺頁率越低羔挡；反之越高洁奈；

進(jìn)程所分配到的物理塊數(shù)：物理塊越多，缺頁率越低绞灼；反之越高利术；

頁面置換算法：算法優(yōu)劣決定了進(jìn)程執(zhí)行過程中缺頁中斷的次數(shù)，所以缺頁率也可以反映置換算法的優(yōu)劣镀赌；

程序固有特性：程序的局部性特點(diǎn)越突出氯哮，缺頁率越低际跪；反之越高商佛；

值得注意的是，在考慮置換算法時(shí)姆打，還需要考慮置換的代價(jià)良姆，比如檢查頁面是否被修改，如果沒有被修改幔戏，那么就可以直接抹去玛追，如果被修改，那么還需要寫回到磁盤闲延；

頁面置換算法

頁面置換算法是指當(dāng)內(nèi)存空間不足而又需要調(diào)入頁面時(shí)痊剖，系統(tǒng)選擇被置換出去頁面的算法；

好的頁面置換算法應(yīng)具有較低的頁面更換頻率垒玲。不適合的置換算法將出現(xiàn)抖動(dòng)情況：剛剛被置換出去的頁面陆馁，很快又被調(diào)入，這樣系統(tǒng)的一部分時(shí)間就在頁面置換工作上合愈，而沒有進(jìn)行業(yè)務(wù)處理叮贩，是一種資源的浪費(fèi)击狮；

實(shí)際上，好的頁面置換算法應(yīng)將那些再也用不到的頁面置換出去益老，但是彪蓬，如何識(shí)別未來的情況不是一件容易的事，常見的策略是站在過去看未來捺萌；

下面是幾種常見的頁面置換算法：

最佳置換算法：性能最好的置換算法档冬，因?yàn)樗鼘?duì)未來的判斷達(dá)到了100%，同樣互婿，也決定了它無法實(shí)際應(yīng)用捣郊，唯一的作用是作為衡量其他算法的標(biāo)尺；該算法從已在內(nèi)存中的頁面中選擇未來最長(zhǎng)時(shí)間內(nèi)不會(huì)使用的頁面將其置換出去慈参；但是現(xiàn)實(shí)中是無法預(yù)測(cè)未來的扒荷！

先進(jìn)先出頁面置換算法：該算法與通常頁面的使用規(guī)律不符驮配，往往是性能最差的算法娘扩，因?yàn)樵撍惴ㄊ褂谜{(diào)入時(shí)間這一因素來預(yù)測(cè)未來，與實(shí)際的訪問情況沒有很大關(guān)系壮锻，比如琐旁，最先調(diào)入的頁面，可能最近一直被訪問猜绣，把它置換出去灰殴，不久的將來還得找回來，何必呢掰邢？

最近最久未使用算法：該算法使用近期的訪問情況作為預(yù)測(cè)未來的依據(jù)牺陶，即最近頻繁使用的頁面，那么將來也很有可能繼續(xù)訪問辣之，所以找出最近最久未使用（使用頻率最低）的頁面置換出去掰伸，因?yàn)檫@些頁面未來使用的可能性最低；該算法的實(shí)現(xiàn)怀估，需要為每個(gè)頁面使用一個(gè)寄存器來標(biāo)識(shí)時(shí)間的流逝狮鸭；如果訪問某個(gè)頁面，那么就對(duì)應(yīng)的寄存器中的存儲(chǔ)的數(shù)字的最高位置為1,多搀；然后每隔一定時(shí)間歧蕉，就將所有寄存器的數(shù)字右移一位，這樣數(shù)字的大小就能表示使用頻率啦康铭；當(dāng)然惯退，也可使用棧的方式來管理各個(gè)頁面的訪問情況；

最少使用算法：該算法和最近最久未使用算法思路相同麻削，都是使用最近的過去預(yù)測(cè)最近的未來蒸痹；在該算法里春弥，采取的依據(jù)是最近一段時(shí)間里的使用次數(shù)；其實(shí)和最近最久未使用算法基本相同叠荠；值得注意的是匿沛，因?yàn)橐莆徊僮魇窃谝欢螘r(shí)間間隔后進(jìn)行的，所以在這段時(shí)間里榛鼎，訪問10000次某頁面和訪問1次頁面是等效的逃呼；

Clock算法（最近未使用算法）：即便LRU(最近最久未使用)算法是一種不錯(cuò)的算法，但是需要系統(tǒng)提供較多的硬件支持者娱，所以在實(shí)際運(yùn)用過程中抡笼，大多采用該算法作為替代，故該算法也叫作最近未使用算法：該算法中將頁面組織為循環(huán)隊(duì)列黄鳍，每個(gè)頁面有一個(gè)訪問位推姻，如果訪問過該頁面，就將其訪問位置為1框沟，否則將其訪問位置為0藏古；當(dāng)尋找置換出去的頁面時(shí)，遇到第一個(gè)訪問位為0的頁面就將其置換出去忍燥，如果遇到訪問位為1的頁面拧晕，那么將其訪問位置為1，然后繼續(xù)尋找梅垄；由于該算法循環(huán)檢查各個(gè)頁面的使用情況厂捞，所以就叫做Clock算法了；

值得注意的是队丝，因?yàn)闆]有修改過的頁面不需要進(jìn)行寫回磁盤的操作靡馁，所以我們希望置換出去的頁面是未修改的頁面，這是考慮了置換代價(jià)的結(jié)果炭玫，此時(shí)稱為改進(jìn)版Clock算法奈嘿；這樣貌虾，最佳的置換頁面是最近既未使用過的頁面還要是未修改過的頁面吞加，這樣，檢查的時(shí)候就不能只檢查訪問位A尽狠，還需要組合修改位M衔憨。這樣就會(huì)遇到四種頁面；

A=0袄膏；M=0：最佳置換頁践图；

A=0；M=1：不是很好的置換頁沉馆；

A=1码党；M=0：表示該頁面最近被訪問德崭，但是內(nèi)容尚未被修改，該頁面可能最近還會(huì)被訪問揖盘；

A=1眉厨；M=1：該頁面不但被訪問過，而且還修改了兽狭，不好不好憾股；

此時(shí)，尋找的過程為：首先尋找A=0箕慧；M=0的頁面服球，遇到就置換出，第一次掃描時(shí)不改變?cè)L問位A颠焦；如果沒找到斩熊，那么進(jìn)行第二次尋找，此時(shí)尋找A=0伐庭；M=1的頁面座享，遇到就置換出，同時(shí)遇到A=1的頁面將其置為0似忧；如果第二遍還沒有找到渣叛，說明所有的頁面都被訪問過（沒找到A=0,M=0的，也沒找到A=0,M=1的盯捌，所以在尋找之前淳衙，所有的A=1），但是此時(shí)所有的A都會(huì)為0饺著，因?yàn)楸恍薷牧藛h箫攀，第三遍尋找的時(shí)候，我們希望A=0,M=0的頁面幼衰，此時(shí)如果遇到靴跛，就置換出；但是如果第三遍還沒有找到渡嚣，那說明開始第一遍尋找之前梢睛，A=1,M=1啊，這樣我們就需要開始第四遍尋找识椰，目標(biāo)A=0绝葡，M=1，這樣一定會(huì)找到腹鹉，遇到就置換出藏畅；

一個(gè)有意思的結(jié)論是，因?yàn)榭紤]了置換代價(jià)功咒，所以產(chǎn)生了尋找代價(jià)：原來只需要遍歷一遍的愉阎，現(xiàn)在有可能遍歷四遍绞蹦；這就是大自然的定律：你想要帶走點(diǎn)什么，就必須留下點(diǎn)什么榜旦；這樣道理還有很多：機(jī)械可以省力（意味著費(fèi)距離）坦辟，但是不能省功；改進(jìn)算法時(shí)常常使用空間換時(shí)間或者時(shí)間換空間章办，很難既省空間有省時(shí)間——除非提出新的算法锉走；得失之間，盡顯智慧藕届！跑遠(yuǎn)了挪蹭，回來！

PBA算法：在請(qǐng)求分頁系統(tǒng)中休偶，由于系統(tǒng)經(jīng)常發(fā)生頁面換進(jìn)換出的情況梁厉，所以置換代價(jià)會(huì)對(duì)系統(tǒng)性能產(chǎn)生重大影響，PBA準(zhǔn)確的說不是一種置換算法踏兜，而是一種處理置換頁面的方法：上述的算法只是提到了如何選擇置換頁面词顾，但是沒有說明怎么處理置換出去的頁面，而PBA算法剛好補(bǔ)上這一空缺碱妆；不得不說肉盹，緩存的確是提高效率的一把利刃，存儲(chǔ)器系統(tǒng)就是基于緩存思想而設(shè)計(jì)的疹尾，而PBA也是將修改過的頁面緩存起來上忍，從而避免頻繁地執(zhí)行中斷和IO驅(qū)動(dòng)程序（這和現(xiàn)實(shí)生活中的垃圾桶是一樣的，緩存就像是垃圾桶纳本，你可以扔一次垃圾而把一天的垃圾都處理掉窍蓝，總比產(chǎn)生一些垃圾就扔一次好吧），以這樣的方式來提高系統(tǒng)效率繁成；下面看看該算法使用的數(shù)據(jù)結(jié)構(gòu)以及算法思想吓笙；

該算法有以下幾個(gè)特點(diǎn)：

顯著降低頁面換進(jìn)換出的頻率，使IO操作的次數(shù)大為減少巾腕，從而降低了置換開銷面睛；

因?yàn)橹脫Q開銷的降低，所以支持系統(tǒng)使用較為簡(jiǎn)單的置換策略祠墅，避免復(fù)雜算法對(duì)系統(tǒng)的特殊硬件要求侮穿；

該算法使用兩個(gè)鏈表：空閑頁面鏈表和修改頁面鏈表歌径；

對(duì)于空閑頁面鏈表毁嗦，它所容納的是空閑物理塊，用于分配給頻繁發(fā)生缺頁的進(jìn)程以降低該進(jìn)程的缺頁率回铛；當(dāng)進(jìn)程需要讀入一個(gè)頁面時(shí)狗准，首先從空閑鏈表上獲取一個(gè)空閑物理塊克锣，這樣就避免了置換出其他頁面的開銷；當(dāng)有一個(gè)未修改的頁面換出時(shí)腔长，實(shí)際上將其掛入空閑鏈表的尾部而不必執(zhí)行寫入操作袭祟；需要注意的是，雖然進(jìn)入了空閑鏈表捞附，但是該物理塊還是裝有數(shù)據(jù)巾乳，以后如果還有進(jìn)程需要這些頁面的數(shù)據(jù)，可直接從空閑鏈表上取出鸟召，而不必從磁盤讀入胆绊，這也降低了頁面換進(jìn)的開銷；

對(duì)于修改頁面鏈表欧募，設(shè)置該鏈表的目的就是減少已修改頁面換出的次數(shù)压状，當(dāng)修改頁面的數(shù)量達(dá)到一定數(shù)量后，系統(tǒng)再一次性將其寫出跟继，這樣就降低了頁面寫入磁盤的頻率种冬，降低從磁盤讀入數(shù)據(jù)進(jìn)入內(nèi)存的頻率；

當(dāng)然舔糖，額外的管理也是需要時(shí)空代價(jià)的娱两，這時(shí)，需要做的就是取舍金吗；

訪問時(shí)間

訪問時(shí)間需要考慮訪問頁表和訪問實(shí)際物理地址數(shù)據(jù)的時(shí)間谷婆，還需要考慮缺頁中斷的時(shí)間，還有考慮快表的存在辽聊，下面分三種情況討論：

被訪問的頁在內(nèi)存中纪挎，而且其對(duì)應(yīng)的頁表項(xiàng)在快表中；這樣訪問時(shí)間T=訪問快表的時(shí)間+訪問實(shí)際物理地址的時(shí)間跟匆；

被訪問的頁在內(nèi)存中异袄，且其對(duì)應(yīng)的頁表項(xiàng)不在塊表中；這樣訪問時(shí)間T=訪問快表的時(shí)間+訪問頁表的時(shí)間+修改快表的時(shí)間+訪問實(shí)際物理地址的時(shí)間玛臂；

綜合1,2兩種情況烤蜕，可以用來快表的命中率來統(tǒng)一得到訪問頁面在內(nèi)存中的情況下的平均訪問時(shí)間T1；

被訪問的頁面不在內(nèi)存迹冤；這樣訪問時(shí)間T=訪問快表的時(shí)間+訪問頁表的時(shí)間+缺頁中斷時(shí)間+更新快表的時(shí)間+訪問實(shí)際物理地址的時(shí)間讽营；

可綜合T1和3，引入頁面的缺頁率來統(tǒng)一得到頁面的訪問時(shí)間TF泡徙；

抖動(dòng)與工作集

基本概念

所謂抖動(dòng)是指橱鹏，處理機(jī)的利用率趨于0的現(xiàn)象，即處理機(jī)沒有進(jìn)行業(yè)務(wù)處理，而是忙于中斷響應(yīng)莉兰；產(chǎn)生抖動(dòng)的根本原因是同時(shí)運(yùn)行在系統(tǒng)中的進(jìn)程太多挑围，而分配給每個(gè)進(jìn)程的物理塊太少，進(jìn)程頻繁發(fā)生缺頁中斷糖荒，這就使得每個(gè)進(jìn)程的大部分時(shí)間都用于頁面的換進(jìn)換出杉辙，而不去做有效的工作；

所謂工作集就是指進(jìn)程在某段時(shí)間里實(shí)際要訪問的頁面集合捶朵；這是基于程序的局部性原理來定義的蜘矢，因?yàn)楦鶕?jù)局部性原理，程序度頁面的訪問是不均勻的综看，所以一段時(shí)間里硼端，對(duì)某些頁面的訪問要明顯高于其他頁面，這些被集中訪問的頁面就是進(jìn)程當(dāng)前的工作集寓搬；

抖動(dòng)的解決方案

采取局部替換策略：這樣珍昨，一個(gè)進(jìn)程發(fā)生了“抖動(dòng)”也不會(huì)影響到其他進(jìn)程；于是可以控制抖動(dòng)的影響范圍句喷，該方法雖然簡(jiǎn)單镣典，但是效果并不是很好，因?yàn)橐坏┠硞€(gè)進(jìn)程發(fā)生抖動(dòng)唾琼，那么會(huì)讓磁盤IO的等待隊(duì)列增長(zhǎng)兄春，使得其他等待磁盤IO的進(jìn)程的等待時(shí)間變長(zhǎng)；

將工作集算法考慮到處理機(jī)調(diào)度中锡溯，當(dāng)調(diào)度程序發(fā)現(xiàn)處理機(jī)效率較低時(shí)赶舆，不是簡(jiǎn)單的從外存中引入作業(yè)，而是先檢查在內(nèi)存中的每個(gè)進(jìn)程是否有足夠的空間祭饭，如果進(jìn)程對(duì)物理塊沒有需求芜茵，那么就可以引入新的作業(yè)，如果內(nèi)存使用緊張倡蝙，則首先為那些缺頁率高的作業(yè)增加新的物理塊九串，即暫停調(diào)入新的作業(yè)；

利用L=S準(zhǔn)則來調(diào)節(jié)多道程序度寺鸥；L為缺頁之間的平均時(shí)間猪钮，S為缺頁服務(wù)時(shí)間，即置換一個(gè)頁面的平均時(shí)間胆建；如果L遠(yuǎn)遠(yuǎn)比S大烤低，說明缺頁較少發(fā)生，此時(shí)磁盤的能力尚未得到充分利用笆载；反之扑馁，如果L小于S那么涯呻，這說明缺頁頻繁發(fā)生，缺頁的速度已超過磁盤的處理能力檐蚜；只有當(dāng)L=S時(shí)魄懂，系統(tǒng)的資源利用率最為協(xié)調(diào)沿侈；實(shí)踐檢驗(yàn)后闯第，發(fā)現(xiàn)L=S準(zhǔn)則對(duì)于調(diào)節(jié)缺頁率是十分有效的；

為防止發(fā)生抖動(dòng)缀拭，系統(tǒng)必須減少多道程序的數(shù)量咳短。此時(shí)應(yīng)該基于某種選擇策略暫停當(dāng)前活動(dòng)的某些進(jìn)程以釋放內(nèi)存空間，將其分配給其他進(jìn)程蛛淋；通常采取和調(diào)度程序一致的策略咙好；

總體來說，就是保證進(jìn)程有充分的內(nèi)存空間可以使用褐荷，從而降低缺頁率勾效；