1.虛擬存儲器的基本概念
?引入霉咨、實現(xiàn)、特征
2.請求分頁存儲管理方式
?硬件支持驶赏、地址變換院喜、分配算法
?頁面置換算法
?性能分析
3.請求分段存儲管理方式
1.? 虛擬存儲器的基本概念
分析常規(guī)存儲器管理不足的原因：
1）常規(guī)存儲器管理方式的特征
一次性：作業(yè)在運行前一次性地全部裝入內(nèi)存
駐留性：作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中证芭，直至作業(yè)運行結(jié)束冗疮。
?：一次性及駐留性在程序運行時是否是必須的？
? ? NO檩帐。程序運行有局部性术幔。
程序在執(zhí)行時將呈現(xiàn)出局部性規(guī)律：
在一較短的時間內(nèi)
程序的執(zhí)行僅局限于某個部分；
相應(yīng)地湃密，所訪問的存儲空間也局限于某個區(qū)域诅挑。
程序執(zhí)行的特點：?
多數(shù)情況下仍是順序執(zhí)行。??
少部分的轉(zhuǎn)移和過程調(diào)用指令會使程序執(zhí)行由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域（但研究表明調(diào)用深度多數(shù)情況下不超過5）許多由少數(shù)指令構(gòu)成的循環(huán)結(jié)構(gòu)會多次執(zhí)行泛源。u對許多數(shù)據(jù)結(jié)構(gòu)的處理（如數(shù)組）往往局限于很小的范圍內(nèi)拔妥。?
所有上述情況都表現(xiàn)出程序執(zhí)行的局部性：
u時間局部性(temporal locality)
被引用過一次的存儲器位置很可能在不遠的將來再被多次引用。
u空間局部性(spatial locality)
如果一個存儲器位置被引用了一次达箍，那么程序很可能在不遠的將來引用附近的一個存儲器位置没龙。
基于局部性原理
u程序運行前，不需全部裝入內(nèi)存（打破一次性）
僅裝入當前要運行的部分頁面或段即可運行缎玫，其余部分暫留在外存上硬纤。
缺頁/段的情況：要訪問的頁(段) 尚未調(diào)入內(nèi)存。程序應(yīng)利用OS所提供的請求調(diào)頁(段)功能赃磨，將它們調(diào)入內(nèi)存筝家，使程序繼續(xù)執(zhí)行。
u調(diào)入需要的頁/段時邻辉，如果內(nèi)存已滿溪王，無法再裝入新頁(段)腮鞍，通過置換功能將內(nèi)存中暫時不用的頁(段)調(diào)至外存，騰出足夠的內(nèi)存空間莹菱。（不總駐留）
交換技術(shù)與虛存使用的調(diào)入調(diào)出技術(shù)有何相同和不同之處移国？
主要相同點是都要在內(nèi)存與外存之間交換信息；
主要區(qū)別在于交換技術(shù)換出換進一般是整個進程(proc結(jié)構(gòu)和共享正文段除外)道伟，因此一個進程的大小受物理存儲器的限制桥狡；
而虛存中使用的調(diào)入調(diào)出技術(shù)在內(nèi)存與外存之間來回傳遞的是存儲頁或存儲段，而不是整個進程皱卓，從而使得進程映射具有了更大的靈活性裹芝，且允許進程的大小比可用的物理存儲空間大的多 。
3）虛擬存儲器的定義
所謂“虛擬存儲器”娜汁，是指具有請求調(diào)入功能和置換功能嫂易，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。
虛擬存儲管理下
內(nèi)存邏輯容量由內(nèi)存容量和外存容量之和所決定
運行速度接近于內(nèi)存速度
每位的成本卻接近于外存掐禁。
4）虛擬存儲器的實現(xiàn)
虛擬存儲管理：
允許將一個作業(yè)分多次調(diào)入內(nèi)存怜械。
若采用連續(xù)分配方式，需申請足夠空間傅事，再分多次裝入缕允，造成內(nèi)存資源浪費，并不能從邏輯上擴大內(nèi)存容量蹭越。
虛擬的實現(xiàn)建立在離散分配存儲管理基礎(chǔ)上
方式：請求分頁/請求分段系統(tǒng)
細節(jié)：分頁/段機構(gòu)障本、中斷機構(gòu)、地址變換機構(gòu)响鹃、軟件支持
5）虛擬存儲器的特征
離散分配方式是基礎(chǔ)
多次性：一個作業(yè)被分成多次調(diào)入內(nèi)存運行
對換性：允許在作業(yè)的運行過程中進行換進驾霜、換出。（進程整體對換不算虛擬）
最終體現(xiàn)虛擬性：能夠從邏輯上擴充內(nèi)存容量买置，使用戶所看到的內(nèi)存容量遠大于實際內(nèi)存容量粪糙。
2.請求分頁存儲管理方式
基本分頁 + “請求調(diào)頁”和“頁面置換”功能。
換入和換出基本單位都是長度固定的頁面
1）硬件支持
? ?一臺具有一定容量的內(nèi)/外存的計算機
+ 頁表機制
+ 缺頁中斷機構(gòu)
+ 地址轉(zhuǎn)換機構(gòu)
缺頁中斷機構(gòu)
每當要訪問的頁面不在內(nèi)存時忿项，便產(chǎn)生一缺頁中斷通知OS蓉冈，OS則將所缺之頁調(diào)入內(nèi)存。作為中斷轩触，需經(jīng)歷幾個步驟：
a)“保護CPU環(huán)境”
b)“分析中斷原因”
c)“轉(zhuǎn)入缺頁中斷處理程序”
d)“恢復(fù)CPU環(huán)境”等寞酿。
作為一種特殊中斷，與一般中斷有明顯區(qū)別：
(1)
在指令執(zhí)行期間產(chǎn)生和處理中斷信號怕膛。
(2)
一條指令在執(zhí)行期間熟嫩，可能產(chǎn)生多次缺頁中斷秦踪。
2）內(nèi)存分配
? ?作業(yè)不一次裝入褐捻，部分裝入的情況下如何為進程分配內(nèi)存掸茅，涉及三個問題：
①最小物理塊數(shù)的確定
少于此數(shù)量進程將不能運行
與計算機的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式柠逞、功能和尋址方式
②物理塊的分配策略
③物理塊的分配算法
③物理塊的分配算法
u考慮優(yōu)先權(quán)的分配算法
???? 實際應(yīng)用中昧狮，要照顧重要、急迫的作業(yè)盡快完成板壮，為它分配較多的內(nèi)存空間逗鸣。
所有可用物理塊分兩部分：
?一部分按比例分配給各進程；
另一部分根據(jù)各進程優(yōu)先權(quán)绰精，適當?shù)貫槠湓黾臃蓊~撒璧，分配給各進程。
3）調(diào)頁策略
①
何時調(diào)入頁面
1.預(yù)調(diào)頁策略
以預(yù)測為基礎(chǔ)笨使，將預(yù)計不久后便會被訪問的若干頁面卿樱，預(yù)先調(diào)入內(nèi)存。
優(yōu)點：一次調(diào)入若干頁硫椰，效率較好
缺點：預(yù)測不一定準確繁调，預(yù)調(diào)入的頁面可能根本不被執(zhí)行到。主要用于進程的首次調(diào)入靶草，由程序員指出應(yīng)該先調(diào)入哪些頁蹄胰。
2.請求調(diào)頁策略
運行中需要的頁面不在內(nèi)存，便立即提出請求奕翔，由OS將其調(diào)入內(nèi)存裕寨。
優(yōu)點：由請求調(diào)頁策略所確定調(diào)入的頁，一定會被訪問派继；比較容易實現(xiàn)帮坚。
缺點：每次僅調(diào)入一頁，需花費較大的系統(tǒng)開銷互艾，增加了磁盤I/O的啟動頻率试和。
進程運行過程中，訪問的頁面不在內(nèi)存纫普，調(diào)入時內(nèi)存已無空閑空間阅悍，需要將內(nèi)存中的一頁程序或數(shù)據(jù)調(diào)到外存。
3.頁面置換算法
頁面置換算法(pagereplacement algorithms)：選擇換出哪些頁面的算法昨稼，其好壞直接影響系統(tǒng)的性能节视。
應(yīng)具有較低的缺頁率：
頁面調(diào)入次數(shù)（缺頁次數(shù)）/總的頁面使用次數(shù)
1）最佳（Optimal）置換算法
Belady，1966年提出的一種理論上的算法
換出以后永不再用的假栓，或在最長(未來)時間內(nèi)不再被訪問的頁面寻行。
優(yōu)點：保證獲得最低的缺頁率
不足：無法實現(xiàn)，因為無法預(yù)知一進程將來的運行情況
作用：作為參照標準匾荆，評價其他算法拌蜘。
2）先進先出置換算法（FIFO）
先進入的先淘汰杆烁，即選擇內(nèi)存中駐留時間最久的頁面予以淘汰。
優(yōu)點：實現(xiàn)簡單简卧，把一進程已調(diào)入內(nèi)存的頁面按先后次序組織成一個隊列兔魂，并設(shè)置一個指針(替換指針)，使它總是指向隊首最老的頁面举娩。
不足：與進程實際運行規(guī)律不相適應(yīng)（較早調(diào)入的頁往往是經(jīng)常被訪問的頁析校，頻繁被對換造成運行性能降低）
Belady現(xiàn)象：出現(xiàn)分配的頁面數(shù)增多，缺頁率反而提高的異惩妫現(xiàn)象智玻。
描述：一個進程P要訪問M個頁，OS分配N個內(nèi)存頁面給進程P芙代；對一個訪問序列S尚困，發(fā)生缺頁次數(shù)為PE（S,N）。當N增大時链蕊，PE(S, N)時而增大事甜，時而減小。
Belady現(xiàn)象的原因：FIFO算法的置換特征與進程訪問內(nèi)存的動態(tài)特征矛盾滔韵，即被置換的頁面并不是進程不會訪問的逻谦。
3）最近最久未使用(LRU)置換算法
無法預(yù)測將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似陪蜻，因此邦马，LRU置換算法選擇最近最久未使用（least recently used）的頁面予以淘汰
①寄存器記錄時間的原理
一進程有8個頁面，每個頁面需配備一個8位的（移位）寄存器宴卖。
移位寄存器表示為
? ? ? ? ? ? R=Rn-1Rn-2Rn-3…R2R1R0
頁面被訪問后的操作：
將該頁對應(yīng)的寄存器的Rn-1位置為1
如何記時：
由系統(tǒng)發(fā)出定時信號滋将，每隔一定時間將所有寄存器右移1位。
某一時刻症昏，比較各寄存器的值随闽，被用到的標志1逐漸往低位上積累，若高位上沒有1肝谭，就說明最近沒用過掘宪。所以最近最久未使用的就是寄存器值最小的那個頁。
4）輪轉(zhuǎn)算法(clock)?又稱最近未使用算法(NRU, Not Recently Used)攘烛，
LRU(最近最久未使用算法)近似算法
折衷FIFO
每個頁設(shè)一個使用標志位(use bit)魏滚，若該頁被訪問則將其置為1。
設(shè)置一個指針坟漱，從當前指針位置開始按地址先后檢查各頁鼠次，尋找use bit=0的頁面作為被置換頁。
若指針經(jīng)過的頁use bit=1，修改use bit=0（暫不凋出腥寇，給被用過的頁面駐留的機會 ）成翩，指針繼續(xù)向下。到所有頁面末尾后再返回隊首檢查花颗。
5）其他置換算法
最少使用 (LFU, Least Frequently Used)
關(guān)鍵在次數(shù)記錄上
每頁設(shè)置訪問計數(shù)器捕传，每當頁面被訪問時惠拭，該頁面的訪問計數(shù)器加1扩劝；缺頁中斷時，淘汰計數(shù)值最小的頁面职辅，并將所有計數(shù)清零棒呛；
計數(shù)的實現(xiàn)類似LRU，用移位寄存器域携，但比較時不是簡單比較寄存器的值簇秒，而是比較寄存器每位的和∑Ri。
頁面緩沖算法PBA(page buffering algorithm)
對FIFO算法的發(fā)展秀鞭，彌補了FIFO可能造成的I/O開銷趋观，又不需要LRU等算法的硬件支持。
仍用FIFO算法選擇被置換頁
但并不將其馬上換入外存锋边。
系統(tǒng)將頁面放入兩個鏈表之一：如果頁面未被修改皱坛，就將其歸入到空閑頁面鏈表的末尾；否則將其歸入到已修改頁面鏈表豆巨。
需要調(diào)入新的物理頁面時剩辟，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一項所指的頁面，然后將第一項刪除（從空閑鏈表摘下）往扔。
空閑頁面和已修改頁面贩猎，仍停留在內(nèi)存中一段時間，如果這些頁面被再次訪問萍膛，只需較小開銷吭服，而被訪問的頁面可以返還作為進程的內(nèi)存頁。
當已修改頁面達到一定數(shù)目后蝗罗，再將它們一起調(diào)出到外存噪馏，然后將它們歸入空閑頁面鏈表，這樣能大大減少I/O操作的次數(shù)绿饵。
