1.虛擬存儲器的基本概念
1）常規(guī)存儲器管理不足的原因：
常規(guī)存儲器管理方式的特征:
一次性：作業(yè)在運(yùn)行前一次性地全部裝入內(nèi)存
駐留性：作業(yè)裝入內(nèi)存后粘优，便一直駐留在內(nèi)存中梢灭，直至作業(yè)運(yùn)行結(jié)束
2）局部性原理
時(shí)間局部性：被引用過一次的存儲器位置很可能在不遠(yuǎn)的將來再被多次引用
空間局部性：如果一個存儲器位置被引用了一次畦娄，那么程序很可能在不遠(yuǎn)的將來引用附近的一個存儲器功能。
基于局部性原理
程序運(yùn)行前，不需全部裝入內(nèi)存（打破一次性）
? ? 僅裝入當(dāng)前要運(yùn)行的部分頁面或段即可運(yùn)行，其余部分暫留在外存上害驹。
? ?缺頁/段的情況：要訪問的頁(段) 尚未調(diào)入內(nèi)存。程序應(yīng)利用OS所提供的請求調(diào)頁(段)功能蛤育，? ? ? ?將它們調(diào)入內(nèi)存宛官，使程序繼續(xù)執(zhí)行。
調(diào)入需要的頁/段時(shí)瓦糕，如果內(nèi)存已滿底洗，無法再裝入新頁(段)，通過置換功能將內(nèi)存中暫時(shí)不用的頁(段)調(diào)至外存咕娄，騰出足夠的內(nèi)存空間亥揖。（不總駐留）
3）虛擬存儲器的定義：
所謂“虛擬存儲器”，是指具有請求調(diào)入功能和置換功能圣勒，能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)费变。
虛擬存儲管理下
內(nèi)存邏輯容量由內(nèi)存容量和外存容量之和所決定
運(yùn)行速度接近于內(nèi)存速度
每位的成本卻接近于外存摧扇。
4）虛擬存儲器的實(shí)現(xiàn)
若采用連續(xù)分配方式，需申請足夠空間胡控，再分多次裝入，造成內(nèi)存資源浪費(fèi)旁趟，并不能從邏輯上擴(kuò)大內(nèi)存容量昼激。
虛擬的實(shí)現(xiàn)建立在離散分配存儲管理基礎(chǔ)上
方式：請求分頁/請求分段系統(tǒng)
細(xì)節(jié)：分頁/段機(jī)構(gòu)、中斷機(jī)構(gòu)锡搜、地址變換機(jī)構(gòu)橙困、軟件支持
5）虛擬存儲器的特征
離散分配方式是基礎(chǔ)
多次性：一個作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行
對換性：允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)、換出耕餐。（進(jìn)程整體對換不算虛擬）
最終體現(xiàn)虛擬性：能夠從邏輯上擴(kuò)充內(nèi)存容量凡傅，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。
2.請求分頁存儲管理方式
基本分頁 + “請求調(diào)頁”和“頁面置換”功能肠缔。
換入和換出基本單位都是長度固定的頁面
1）硬件支持
一臺具有一定容量的內(nèi)/外存的計(jì)算機(jī)+ 頁表機(jī)制+ 缺頁中斷機(jī)構(gòu)+ 地址轉(zhuǎn)換機(jī)構(gòu)
（1）頁表基本功能不變：邏輯地址映射為物理地址
①?狀態(tài)位P ：指示該頁是否已調(diào)入內(nèi)存夏跷。
② 訪問字段A ：用于記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)，或記錄本頁最近已有多長時(shí)間未被訪問明未。(置換時(shí)考量的參數(shù))
③修改位M ：該頁在調(diào)入內(nèi)存后是否被修改過槽华。(關(guān)系到置換時(shí)調(diào)出的具體操作)
④ 外存地址：用于指出該頁在外存上的地址。
（2）缺頁中斷機(jī)構(gòu)
每當(dāng)要訪問的頁面不在內(nèi)存時(shí)趟妥，便產(chǎn)生一缺頁中斷通知OS猫态，OS則將所缺之頁調(diào)入內(nèi)存。作為中斷披摄，需經(jīng)歷幾個步驟：
“保護(hù)CPU環(huán)境”
“分析中斷原因”
“轉(zhuǎn)入缺頁中斷處理程序”
“恢復(fù)CPU環(huán)境”等亲雪。
作為一種特殊中斷，與一般中斷有明顯區(qū)別：
①在指令執(zhí)行期間產(chǎn)生和處理中斷信號疚膊。
②?一條指令在執(zhí)行期間义辕，可能產(chǎn)生多次缺頁中斷。
（3）地址變換機(jī)構(gòu)
2）內(nèi)存分配
（1）最小物理塊數(shù)的確定
少于此數(shù)量進(jìn)程將不能運(yùn)行
與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)寓盗，取決于指令的格式终息、功能和尋址方式
（2）物理塊的分配策略
固定分配、局部置換
可變分配贞让、全局置換
可變分配周崭、局部置換
（3）物理塊的分配算法
①平均分配算法
將所有可供分配的物理塊平均分配給各進(jìn)程。
缺點(diǎn)：未考慮各進(jìn)程本身的大小喳张，利用率不均续镇。
②按比例分配算法
根據(jù)進(jìn)程的大小按比例分配物理塊。
設(shè)系統(tǒng)中共有n個進(jìn)程
則销部，每個進(jìn)程能分到的物理塊數(shù)：
Si：進(jìn)程i頁面數(shù)為摸航；S：n個進(jìn)程頁面數(shù)總和制跟；m：可用物理塊總數(shù)
③考慮優(yōu)先權(quán)的分配算法
所有可用物理塊分兩部分：
一部分按比例分配給各進(jìn)程；
另一部分根據(jù)各進(jìn)程優(yōu)先權(quán)酱虎，適當(dāng)?shù)貫槠湓黾臃蓊~雨膨，分配給各進(jìn)程。
3）調(diào)頁策略
（1）何時(shí)調(diào)入頁面
預(yù)調(diào)頁策略
請求調(diào)頁策略
（2）從何處調(diào)入頁面
在請求分頁系統(tǒng)中的外存分為：
對換區(qū)：連續(xù)存放數(shù)據(jù)读串，讀寫速度較快
文件區(qū)：離散分配方式聊记，I/O速度相對慢
發(fā)生缺頁時(shí)，系統(tǒng)應(yīng)從何處將缺頁調(diào)入內(nèi)存恢暖，分成三種情況：
①系統(tǒng)擁有足夠的對換區(qū)空間：
進(jìn)程運(yùn)行前所有頁面由文件區(qū)拷貝到對換區(qū)排监；
運(yùn)行需要的頁面全部從對換區(qū)調(diào)入內(nèi)存，提高調(diào)頁速度杰捂。
②系統(tǒng)缺少足夠的對換區(qū)空間：
不會被修改的部分舆床，在文件區(qū)操作（即：直接從文件區(qū)調(diào)入，換出時(shí)不用寫入文件嫁佳，再調(diào)入時(shí)仍從文件區(qū)調(diào)入）
可能被修改的部分挨队，在對換區(qū)操作。
③UNIX方式：（隨運(yùn)行數(shù)據(jù)逐漸從文件區(qū)轉(zhuǎn)到對換區(qū)）
未運(yùn)行的頁面從文件區(qū)調(diào)入蒿往；
曾經(jīng)運(yùn)行瞒瘸，但又被換出的頁面放在對換區(qū)，下次調(diào)入應(yīng)從對換區(qū)調(diào)入熄浓。
進(jìn)程請求的共享頁面可能已被其他進(jìn)程調(diào)入情臭，無需再從對換區(qū)調(diào)入。
（3）頁面調(diào)入過程
程序運(yùn)行前需要裝入內(nèi)存：上述的②步策略處理何處調(diào)入赌蔑；
開始運(yùn)行：先預(yù)調(diào)入一部分頁面俯在；
運(yùn)行中：需要的頁面不在內(nèi)存時(shí)，
向CPU發(fā)出一缺頁中斷娃惯，“中斷處理程序”開始工作：
? ? ①首先保留CPU環(huán)境
? ?②分析中斷原因后跷乐，轉(zhuǎn)入缺頁中斷處理程序。
? ?③處理：判斷是否置換趾浅、頁表信息更新
? ?④恢復(fù)現(xiàn)場愕提，重新操作頁面。
3.頁面置換算法
1）最佳Optimal置換算法
優(yōu)點(diǎn)：保證獲得最低的缺頁率
不足：無法實(shí)現(xiàn)皿哨，因?yàn)闊o法預(yù)知一進(jìn)程將來的運(yùn)行情況
作用：作為參照標(biāo)準(zhǔn)浅侨，評價(jià)其他算法。
2）先進(jìn)先出FIFO置換算法
先進(jìn)入的先淘汰证膨，即選擇內(nèi)存中駐留時(shí)間最久的頁面予以淘汰如输。
優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，把一進(jìn)程已調(diào)入內(nèi)存的頁面按先后次序組織成一個隊(duì)列，并設(shè)置一個指針(替換指針)不见，使它總是指向隊(duì)首最老的頁面澳化。
不足：與進(jìn)程實(shí)際運(yùn)行規(guī)律不相適應(yīng)（較早調(diào)入的頁往往是經(jīng)常被訪問的頁，頻繁被對換造成運(yùn)行性能降低）
3）最近最久未使用(LRU)置換算法
不足：有時(shí)頁面過去和未來的走向之間并無必然的聯(lián)系稳吮。
相應(yīng)的需較多的硬件支持：記錄每個頁面自上次被訪問以來所經(jīng)歷的時(shí)間t缎谷，淘汰時(shí)選擇頁面t值最大的；以及需要快速地知道哪一頁是最近最久未使用的頁面灶似，用寄存器或棧列林。
4）CLOCK置換算法
每個頁設(shè)一個使用標(biāo)志位(use bit)，若該頁被訪問則將其置為1喻奥。
設(shè)置一個指針席纽，從當(dāng)前指針位置開始按地址先后檢查各頁捏悬，尋找use bit=0的頁面作為被置換頁撞蚕。
若指針經(jīng)過的頁use bit=1，修改use bit=0（暫不凋出过牙，給被用過的頁面駐留的機(jī)會 ）甥厦，指針繼續(xù)向下。到所有頁面末尾后再返回隊(duì)首檢查寇钉。
說明：
增加了一個使用位
當(dāng)一頁首次加載入內(nèi)存時(shí)刀疙，該位為1，當(dāng)該頁被訪問時(shí)扫倡，使用位也置1
當(dāng)需要進(jìn)行頁替換時(shí)
第一個使用位為0的幀被替換谦秧，指針指向緩沖區(qū)的下一幀
循環(huán)掃描，遇到使用位為1的撵溃，變成0
改進(jìn)CLOCK：
改進(jìn)：主要考慮對沒訪問過的頁面再細(xì)分是否修改過的不同情況疚鲤，減少因修改造成的頻繁I/O操作。
每頁除記錄是否用過A缘挑，還記錄是否修改的標(biāo)志M集歇。置換時(shí)根據(jù)兩個標(biāo)志的值有4種不同情況的處理。
5）其他
（1）最少使用 (LFU, Least Frequently Used)
關(guān)鍵在次數(shù)記錄上
每頁設(shè)置訪問計(jì)數(shù)器语淘，每當(dāng)頁面被訪問時(shí)诲宇，該頁面的訪問計(jì)數(shù)器加1密浑；缺頁中斷時(shí)荆几，淘汰計(jì)數(shù)值最小的頁面，并將所有計(jì)數(shù)清零锅移；
計(jì)數(shù)的實(shí)現(xiàn)類似LRU吕粗，用移位寄存器它掂，但比較時(shí)不是簡單比較寄存器的值，而是比較寄存器每位的和∑Ri。
（2）頁面緩沖算法PBA(page buffering algorithm)
對FIFO算法的發(fā)展虐秋，彌補(bǔ)了FIFO可能造成的I/O開銷榕茧，又不需要LRU等算法的硬件支持。
仍用FIFO算法選擇被置換頁
但并不將其馬上換入外存客给。
系統(tǒng)將頁面放入兩個鏈表之一：如果頁面未被修改用押，就將其歸入到空閑頁面鏈表的末尾；否則將其歸入到已修改頁面鏈表靶剑。
需要調(diào)入新的物理頁面時(shí)蜻拨，將新頁面內(nèi)容讀入到空閑頁面鏈表的第一項(xiàng)所指的頁面，然后將第一項(xiàng)刪除（從空閑鏈表摘下）桩引。
空閑頁面和已修改頁面缎讼，仍停留在內(nèi)存中一段時(shí)間，如果這些頁面被再次訪問坑匠，只需較小開銷血崭，而被訪問的頁面可以返還作為進(jìn)程的內(nèi)存頁。
當(dāng)已修改頁面達(dá)到一定數(shù)目后厘灼，再將它們一起調(diào)出到外存夹纫，然后將它們歸入空閑頁面鏈表，這樣能大大減少I/O操作的次數(shù)设凹。
6）虛擬存儲管理下訪問內(nèi)存的有效時(shí)間
7）影響缺頁率的主要因素
(1)分配給作業(yè)的主存塊數(shù):
多則缺頁率低舰讹，反之則高。
(2)頁面大猩林臁：
大則缺頁率低月匣；反之則高。
(3)頁面調(diào)度算法：
對缺頁中斷率影響很大奋姿，但不可能找到一種最佳算法锄开。
(4)程序編制方法：
以數(shù)組運(yùn)算為例，如果每一行元素存放在一頁中胀蛮，則按行處理各元素缺頁中斷率低院刁；反之，按列處理各元素粪狼，則缺頁中斷率高退腥。
8）抖動
（1）系統(tǒng)抖動：
為了提高處理機(jī)利用率，可增加多道程序并發(fā)度再榄；
但進(jìn)程數(shù)目增加過多狡刘，每個進(jìn)程分配得到的物理塊太少，在某個臨界點(diǎn)上困鸥，會出現(xiàn)剛被淘汰的頁很快又需重新調(diào)入嗅蔬；而調(diào)入不久又被淘汰出去剑按；出現(xiàn)頻繁缺頁
大部分處理器時(shí)間都用在來回的頁面調(diào)度上，這種局面稱為系統(tǒng)抖動或顛簸（thrashing)
（2）抖動的后果：
缺頁率急劇增加
內(nèi)存有效存取時(shí)間加長澜术，
系統(tǒng)吞吐量驟減艺蝴；系統(tǒng)已基本不能完成什么任務(wù)，而是忙于頁面對換操作鸟废，cpu雖然忙猜敢，但效率急劇下降。
（3）根本原因：
頁面淘汰算法不合理盒延；分配給進(jìn)程的物理頁面數(shù)(駐留集)太少缩擂。
（4）常用防抖動方法：
局部置換策略；
頁面調(diào)入內(nèi)存前檢查各進(jìn)程工作集添寺，為缺頁率高的增加有限物理塊胯盯；
L缺頁間的平均時(shí)間=S置換一個頁面所需時(shí)間，可使磁盤和cpu達(dá)到最大利用率计露；
抖動發(fā)生時(shí)選擇暫停一些進(jìn)程博脑，調(diào)節(jié)多道程序度。
（5）工作集模型的原理：
操作系統(tǒng)跟蹤每個進(jìn)程的工作集薄坏，并為進(jìn)程分配大于其工作集的物理塊趋厉。
如果還有空閑物理塊寨闹，則可以再調(diào)一個進(jìn)程到內(nèi)存以增加多道程序數(shù)胶坠。
如果所有工作集之和增加以至于超過了可用物理塊的總數(shù)，那么操作系統(tǒng)會暫停一個進(jìn)程繁堡，將其頁面調(diào)出并且將其物理塊分配給其他進(jìn)程沈善，防止出現(xiàn)抖動現(xiàn)象。
（6）駐留集
駐留(常駐)集是指在當(dāng)前時(shí)刻椭蹄，進(jìn)程實(shí)際駐留在內(nèi)存當(dāng)中的頁面集合闻牡。
工作集是進(jìn)程在運(yùn)行過程中固有的性質(zhì)，而駐留集取決于系統(tǒng)分配給進(jìn)程的物理頁面數(shù)目绳矩，以及所采用的頁面置換算法罩润；
如果一個進(jìn)程的整個工作集都在內(nèi)存當(dāng)中，即駐留集 <=工作集翼馆，那么進(jìn)程將很順利地運(yùn)行割以，而不會造成太多的缺頁中斷（直到工作集發(fā)生劇烈變動，從而過渡到另一個狀態(tài)）应媚；
當(dāng)駐留集達(dá)到某個數(shù)目之后严沥，再給它分配更多的物理頁面，缺頁率也不會明顯下降中姜。
4.請求分段存儲管理方式
1）請求分段中的硬件支持
(1)段表機(jī)制
(2)缺段中斷機(jī)構(gòu)
(3)地址變換機(jī)構(gòu)
2)分段的共享和保護(hù)
(1)實(shí)現(xiàn)共享：共享段表
(2)共享段如何分享與回收
①共享段的分配
②共享段的回收
③分段保護(hù)
a.越界檢查
b.存取控制檢查
c.環(huán)保護(hù)機(jī)構(gòu)
