常規(guī)存儲器管理方式的特征

一次性：作業(yè)在運(yùn)行前一次性地全部裝入內(nèi)存
駐留性：作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。

程序執(zhí)行時(shí)局部性

在一較短的時(shí)間內(nèi)
程序的執(zhí)行僅局限于某個部分；
相應(yīng)地，所訪問的存儲空間也局限于某個區(qū)域。

程序執(zhí)行的特點(diǎn)

多數(shù)情況下仍是順序執(zhí)行。
少部分的轉(zhuǎn)移和過程調(diào)用指令會使程序執(zhí)行由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域（但研究表明調(diào)用深度多數(shù)情況下不超過5）
許多由少數(shù)指令構(gòu)成的循環(huán)結(jié)構(gòu)會多次執(zhí)行。
對許多數(shù)據(jù)結(jié)構(gòu)的處理（如數(shù)組）往往局限于很小的范圍內(nèi)。

時(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)存空間。（不總駐留）

為了用小的內(nèi)存實(shí)現(xiàn)在大的虛空間中程序的運(yùn)行目的
基于局部性原理
虛擬存儲器管理——由操作系統(tǒng)提供一個比實(shí)際內(nèi)存大的，假想的特大存儲器。

虛擬存儲管理

允許將一個作業(yè)分多次調(diào)入內(nèi)存。
若采用連續(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)、軟件支持

虛擬存儲器的特征

離散分配方式是基礎(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)存容量。

請求分頁存儲管理方式

1.頁表基本功能不變：邏輯地址映射為物理地址
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ū)別：
(1) 在指令執(zhí)行期間產(chǎn)生和處理中斷信號。
(2) 一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷
3.地址變換機(jī)構(gòu)
分頁系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)上增加
產(chǎn)生和處理缺頁中斷（請求調(diào)入）
從內(nèi)存中換出一頁的功能（置換）

image.png

內(nèi)存分配

作業(yè)不一次裝入，部分裝入的情況下如何為進(jìn)程分配內(nèi)存，涉及三個問題：
最小物理塊數(shù)的確定
少于此數(shù)量進(jìn)程將不能運(yùn)行
與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式
物理塊的分配策略
物理塊的分配算法

物理塊分配策略

固定分配、局部置換
為每個進(jìn)程分配一定數(shù)目的物理塊，在整個運(yùn)行期間不再改變（基于進(jìn)程的類型，或根據(jù)程序員、程序管理員的建議）
運(yùn)行中缺頁時(shí)，只能從該進(jìn)程內(nèi)存中n個頁面中選出一頁換出，然后再調(diào)入一頁。
困難：難以把握為每個進(jìn)程分配“適量”物理塊數(shù)
可變分配、全局置換
先為每個進(jìn)程分配一定數(shù)目的物理塊
OS管理一個空閑物理塊隊(duì)列，發(fā)生缺頁時(shí)，系統(tǒng)從隊(duì)列中取出一塊分配給該進(jìn)程，將欲調(diào)入的頁裝入（動態(tài)增長型，全局空閑空間都可分配使用）
空閑空間不足時(shí)，可與其他任何進(jìn)程頁面置換?！皶蛊渌M(jìn)程缺頁率提高，影響運(yùn)行”
最易實(shí)現(xiàn)

物理塊分配算法

1.平均分配算法
2.按比例分配算法
3.考慮優(yōu)先權(quán)分配算法

頁面調(diào)度策略

1.預(yù)調(diào)頁策略
2.請求調(diào)頁策略

TIM圖片20181122205949.jpg

TIM圖片20181122205957.jpg

TIM圖片20181122210003.jpg

頁面置換算法
最佳置換算法

換出以后永不再用的，或在最長(未來)時(shí)間內(nèi)不再被訪問的頁面。
優(yōu)點(diǎn)：保證獲得最低的缺頁率
不足：無法實(shí)現(xiàn)，因?yàn)闊o法預(yù)知一進(jìn)程將來的運(yùn)行情況
作用：作為參照標(biāo)準(zhǔn)，評價(jià)其他算法。

先進(jìn)先出置換算法

先進(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)行性能降低）

最久未使用置換算法

無法預(yù)測將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法選擇最近最久未使用（least recently used）的頁面予以淘汰。

寄存器記錄時(shí)間原理

一進(jìn)程有8個頁面，每個頁面需配備一個8位的（移位）寄存器。
    移位寄存器表示為
            R=Rn-1Rn-2Rn-3…R2R1R0
頁面被訪問后的操作：
將該頁對應(yīng)的寄存器的Rn-1位置為1
如何記時(shí)：
由系統(tǒng)發(fā)出定時(shí)信號，每隔一定時(shí)間將所有寄存器右移1位。
某一時(shí)刻，比較各寄存器的值，被用到的標(biāo)志1逐漸往低位上積累，若高位上沒有1，就說明最近沒用過。所以最近最久未使用的就是寄存器值最小的那個頁。

棧記錄時(shí)間原理

某頁面被訪問，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此：棧頂始終是最新被訪問頁面的編號，越久未使用，頁面越被壓在棧底。

輪轉(zhuǎn)算發(fā)

LRU(最近最久未使用算法)近似算法
折衷FIFO
每個頁設(shè)一個使用標(biāo)志位(use bit)，若該頁被訪問則將其置為1。
設(shè)置一個指針，從當(dāng)前指針位置開始按地址先后檢查各頁，尋找use bit=0的頁面作為被置換頁。
若指針經(jīng)過的頁use bit=1，修改use bit=0（暫不凋出，給被用過的頁面駐留的機(jī)會 ），指針繼續(xù)向下。到所有頁面末尾后再返回隊(duì)首檢查。

頁面緩沖算法

對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ù)。

抖動
系統(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)

抖動的后果

缺頁率急劇增加
內(nèi)存有效存取時(shí)間加長，
系統(tǒng)吞吐量驟減；系統(tǒng)已基本不能完成什么任務(wù)，而是忙于頁面對換操作，cpu雖然忙，但效率急劇下降。

根本原因

頁面淘汰算法不合理；分配給進(jìn)程的物理頁面數(shù)(駐留集)太少。

防止抖動方法

局部置換策略；
頁面調(diào)入內(nèi)存前檢查各進(jìn)程工作集，為缺頁率高的增加有限物理塊；
L缺頁間的平均時(shí)間=S置換一個頁面所需時(shí)間，可使磁盤和cpu達(dá)到最大利用率；
抖動發(fā)生時(shí)選擇暫停一些進(jìn)程，調(diào)節(jié)多道程序度

缺頁率與物理塊數(shù)有關(guān)聯(lián)，基于程序局部性原理，若能預(yù)知程序在某段時(shí)間要訪問的頁面并全部調(diào)入他們，將大大降低缺頁率。

駐留集

駐留(常駐)集是指在當(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ù)目之后，再給它分配更多的物理頁面，缺頁率也不會明顯下降。

請求分段管理方式
段表

image.png

缺頁中斷

發(fā)現(xiàn)運(yùn)行進(jìn)程所訪問段尚未調(diào)入內(nèi)存
由缺段中斷機(jī)構(gòu)產(chǎn)生一缺段中斷信號
進(jìn)入OS，由缺段中斷處理程序?qū)⑺璧亩握{(diào)入內(nèi)存。
缺段中斷同樣在一條指令的執(zhí)行期間產(chǎn)生和處理中斷，一條指令執(zhí)行可能產(chǎn)生多次缺段中斷。但不會出現(xiàn)一條指令被分割在兩個分段中或一組信息被分割在兩個分段中的情況。

地址變換機(jī)構(gòu)

基于分段系統(tǒng)地址變換機(jī)構(gòu)的基礎(chǔ)
段調(diào)入內(nèi)存
修改段表
再利用段表進(jìn)行地址變換。
總之：就是增加了缺段中斷的請求及處理等功能

共線段如何分享與回收

共享段的分配
第一個請求使用該共享段的進(jìn)程A：系統(tǒng)為該共享段分配一物理區(qū)，再把共享段裝入該區(qū)；
將該區(qū)的始址填入A的段表相應(yīng)項(xiàng)；
共享段表中增加一表項(xiàng)，填寫有關(guān)數(shù)據(jù)，count置1；
其他進(jìn)程B也調(diào)用該共享段時(shí)，無需再為該段分配內(nèi)存，只需在B的段表中增加一表項(xiàng)，填寫該共享段的物理地址；在共享段的段表中，填上調(diào)用進(jìn)程的進(jìn)程名、存取控制等，再執(zhí)行count:=count+1操作。
共享段的回收
包括撤消在進(jìn)程段表中共享段所對應(yīng)的表項(xiàng)，執(zhí)行count:=count-1。
如果count為0，則由系統(tǒng)回收該共享段的物理內(nèi)存，并取消共享段表中該段所對應(yīng)的表項(xiàng)。

分段保護(hù)

越界檢查
段表寄存器存放了段表長度；段表中存放了每個段的段長。
在進(jìn)行存儲訪問時(shí)，將段號與段表長度比較，段內(nèi)地址與段長比較。
存取控制檢查
尤其表現(xiàn)在不同進(jìn)程對共享段的不同使用上。段表每個表項(xiàng)都設(shè)置“存取控制”字段，規(guī)定該段的訪問方式：只讀，只執(zhí)行，讀/寫
環(huán)保護(hù)機(jī)構(gòu)
規(guī)定：低編號的環(huán)具有高優(yōu)先權(quán)
遵循的原則：一個程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)。一個程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)