第五章 虛擬存儲器

sunhao06 2022-01-08 00:30:28 阅读数:726

第五章 第五

一、虛擬存儲器的基本概念
1、常規存儲器管理方式的特征
一次性:作業在運行前一次性地全部裝入內存
駐留性:作業裝入內存後,便一直駐留在內存中,直至作業運行結束。
2、局部性原理
程序在執行時將呈現出局部性規律:
在一較短的時間內
程序的執行僅局限於某個部分;
相應地,所訪問的存儲空間也局限於某個區域。
程序執行的特點:
多數情况下仍是順序執行。
少部分的轉移和過程調用指令會使程序執行由一部分區域轉至另一部分區域(但研究錶明調用深度多數情况下不超過5)
許多由少數指令構成的循環結構會多次執行。
對許多數據結構的處理(如數組)往往局限於很小的範圍內。
所有上述情况都錶現出程序執行的局部性:
時間局部性(temporal locality)
被引用過一次的存儲器比特置很可能在不遠的將來再被多次引用。
空間局部性(spatial locality)
如果一個存儲器比特置被引用了一次,那麼程序很可能在不遠的將來引用附近的一個存儲器比特置。
3、虛擬存儲器的定義
所謂“虛擬存儲器”,是指具有請求調入功能和置換功能,能從邏輯上對內存容量加以擴充的一種存儲器系統。
虛擬存儲管理下
內存邏輯容量由內存容量和外存容量之和所决定
運行速度接近於內存速度
每比特的成本卻接近於外存。
4、虛擬存儲器的實現
虛擬存儲管理:
允許將一個作業分多次調入內存。
若采用連續分配方式,需申請足够空間,再分多次裝入,造成內存資源浪費,並不能從邏輯上擴大內存容量。
虛擬的實現建立在離散分配存儲管理基礎上
方式:請求分頁/請求分段系統
細節:分頁/段機構、中斷機構、地址變換機構、軟件支持
5、虛擬存儲器的特征
離散分配方式是基礎
多次性:一個作業被分成多次調入內存運行
對換性:允許在作業的運行過程中進行換進、換出。(進程整體對換不算虛擬)
最終體現虛擬性:能够從邏輯上擴充內存容量,使用戶所看到的內存容量遠大於實際內存容量。
二、請求分頁存儲管理方式
基本分頁 + “請求調頁”和“頁面置換”功能。
換入和換出基本單比特都是長度固定的頁面
1、缺頁中斷機構
每當要訪問的頁面不在內存時,便產生一缺頁中斷通知OS,OS則將所缺之頁調入內存。作為中斷,需經曆幾個步驟:
“保護CPU環境”
“分析中斷原因”
“轉入缺頁中斷處理程序”
“恢複CPU環境”等。
作為一種特殊中斷,與一般中斷有明顯區別:
(1) 在指令執行期間產生和處理中斷信號。
(2) 一條指令在執行期間,可能產生多次缺頁中斷。
2、地址變換機構
分頁系統地址變換機構的基礎上增加
產生和處理缺頁中斷(請求調入)
從內存中換出一頁的功能(置換)
在這裏插入圖片描述
在這裏插入圖片描述
在這裏插入圖片描述
3、內存分配
作業不一次裝入,部分裝入的情况下如何為進程分配內存,涉及三個問題:
最小物理塊數的確定
少於此數量進程將不能運行
與計算機的硬件結構有關,取决於指令的格式、功能和尋址方式
物理塊的分配策略
考慮:固定OR可變分配、全局OR局部置換。
組合出三種適合的策略。
固定分配、局部置換
為每個進程分配一定數目的物理塊,在整個運行期間不再改變(基於進程的類型,或根據程序員、程序管理員的建議)
運行中缺頁時,只能從該進程內存中n個頁面中選出一頁換出,然後再調入一頁。
困難:難以把握為每個進程分配“適量”物理塊數
物理塊的分配算法
固定分配策略時,分配物理塊可采用以下幾種算法:
平均分配算法
將所有可供分配的物理塊平均分配給各進程。
缺點:未考慮各進程本身的大小,利用率不均。
按比例分配算法
根據進程的大小按比例分配物理塊。
設系統中共有n個進程
則,每個進程能分到的物理塊數:
4、調頁策略
① 何時調入頁面
預調頁策略
以預測為基礎,將預計不久後便會被訪問的若幹頁面,預先調入內存。
優點:一次調入若幹頁,效率較好
缺點:預測不一定准確,預調入的頁面可能根本不被執行到。主要用於進程的首次調入,由程序員指出應該先調入哪些頁。
請求調頁策略
運行中需要的頁面不在內存,便立即提出請求,由OS將其調入內存。
優點:由請求調頁策略所確定調入的頁,一定會被訪問;比較容易實現。
缺點:每次僅調入一頁,需花費較大的系統開銷,增加了磁盤I/O的啟動頻率。
② 從何處調入頁面
在請求分頁系統中的外存分為:
對換區:連續存放數據,讀寫速度較快
文件區:離散分配方式,I/O速度相對慢
發生缺頁時,系統應從何處將缺頁調入內存,分成三種情况:
系統擁有足够的對換區空間:
進程運行前所有頁面由文件區拷貝到對換區;
運行需要的頁面全部從對換區調入內存,提高調頁速度。
系統缺少足够的對換區空間:
不會被修改的部分,在文件區操作(即:直接從文件區調入,換出時不用寫入文件,再調入時仍從文件區調入)
可能被修改的部分,在對換區操作。
UNIX方式:(隨運行數據逐漸從文件區轉到對換區)
未運行的頁面從文件區調入;
曾經運行,但又被換出的頁面放在對換區,下次調入應從對換區調入。
進程請求的共享頁面可能已被其他進程調入,無需再從對換區調入。
③ 頁面調入過程
程序運行前需要裝入內存:上述的②步策略處理何處調入;
開始運行:先預調入一部分頁面;
運行中:需要的頁面不在內存時,
向CPU發出一缺頁中斷,“中斷處理程序”開始工作:
首先保留CPU環境
分析中斷原因後,轉入缺頁中斷處理程序。
處理:判斷是否置換、頁錶信息更新
恢複現場,重新操作頁面。
5、頁面置換算法
(1)最佳Optimal置換算法
Belady,1966年提出的一種理論上的算法
換出以後永不再用的,或在最長(未來)時間內不再被訪問的頁面。
優點:保證獲得最低的缺頁率
不足:無法實現,因為無法預知一進程將來的運行情况
作用:作為參照標准,評價其他算法。
(2)先進先出FIFO置換算法
先進入的先淘汰,即選擇內存中駐留時間最久的頁面予以淘汰。
優點:實現簡單,把一進程已調入內存的頁面按先後次序組織成一個隊列,並設置一個指針(替換指針),使它總是指向隊首最老的頁面。
不足:與進程實際運行規律不相適應(較早調入的頁往往是經常被訪問的頁,頻繁被對換造成運行性能降低)
Belady現象:出現分配的頁面數增多,缺頁率反而提高的异常現象。
描述:一個進程P要訪問M個頁,OS分配N個內存頁面給進程P;對一個訪問序列S,發生缺頁次數為PE(S,N)。當N增大時,PE(S, N)時而增大,時而减小。
Belady現象的原因:FIFO算法的置換特征與進程訪問內存的動態特征矛盾,即被置換的頁面並不是進程不會訪問的
(3)最近最久未使用(LRU)置換算法
無法預測將來的使用情况,只能利用“最近的過去”作為“最近的將來”的近似,因此,LRU置換算法選擇最近最久未使用(least recently used)的頁面予以淘汰。
(4)CLOCK置換算法
LRU(最近最久未使用算法)近似算法
折衷FIFO
每個頁設一個使用標志比特(use bit),若該頁被訪問則將其置為1。
設置一個指針,從當前指針比特置開始按地址先後檢查各頁,尋找use bit=0的頁面作為被置換頁。
若指針經過的頁use bit=1,修改use bit=0(暫不凋出,給被用過的頁面駐留的機會 ),指針繼續向下。到所有頁面末尾後再返回隊首檢查。
(5)其他
①最少使用 (LFU, Least Frequently Used)
關鍵在次數記錄上
每頁設置訪問計數器,每當頁面被訪問時,該頁面的訪問計數器加1;缺頁中斷時,淘汰計數值最小的頁面,並將所有計數清零;
計數的實現類似LRU,用移比特寄存器,但比較時不是簡單比較寄存器的值,而是比較寄存器每比特的和∑Ri。
②頁面緩沖算法PBA(page buffering algorithm)
對FIFO算法的發展,彌補了FIFO可能造成的I/O開銷,又不需要LRU等算法的硬件支持。
仍用FIFO算法選擇被置換頁
但並不將其馬上換入外存。
系統將頁面放入兩個鏈錶之一:如果頁面未被修改,就將其歸入到空閑頁面鏈錶的末尾;否則將其歸入到已修改頁面鏈錶。
需要調入新的物理頁面時,將新頁面內容讀入到空閑頁面鏈錶的第一項所指的頁面,然後將第一項删除(從空閑鏈錶摘下)。
空閑頁面和已修改頁面,仍停留在內存中一段時間,如果這些頁面被再次訪問,只需較小開銷,而被訪問的頁面可以返還作為進程的內存頁。
當已修改頁面達到一定數目後,再將它們一起調出到外存,然後將它們歸入空閑頁面鏈錶,這樣能大大减少I/O操作的次數。
三、抖動
系統抖動:
為了提高處理機利用率,可增加多道程序並發度;
但進程數目增加過多,每個進程分配得到的物理塊太少,在某個臨界點上,會出現剛被淘汰的頁很快又需重新調入;而調入不久又被淘汰出去;出現頻繁缺頁
大部分處理器時間都用在來回的頁面調度上,這種局面稱為系統抖動或顛簸(thrashing)
抖動的後果:
缺頁率急劇增加
內存有效存取時間加長,
系統吞吐量驟减;系統已基本不能完成什麼任務,而是忙於頁面對換操作,cpu雖然忙,但效率急劇下降。
根本原因:
頁面淘汰算法不合理;分配給進程的物理頁面數(駐留集)太少。
常用防抖動方法:
局部置換策略;
頁面調入內存前檢查各進程工作集,為缺頁率高的增加有限物理塊;
L缺頁間的平均時間=S置換一個頁面所需時間,可使磁盤和cpu達到最大利用率;
抖動發生時選擇暫停一些進程,調節多道程序度。
四、請求分段存儲管理方式
在請求分段系統中,程序運行之前,只需先調入若幹個分段(不必調入所有的分段),便可啟動運行。當所訪問的段不在內存中時,可請求OS將所缺的段調入內存。
1)請求分段中的硬件支持
①段錶機制
在這裏插入圖片描述
②缺段中斷機構
發現運行進程所訪問段尚未調入內存
由缺段中斷機構產生一缺段中斷信號
進入OS,由缺段中斷處理程序將所需的段調入內存。
缺段中斷同樣在一條指令的執行期間產生和處理中斷,一條指令執行可能產生多次缺段中斷。但不會出現一條指令被分割在兩個分段中或一組信息被分割在兩個分段中的情况。
③地址變換機構
基於分段系統地址變換機構的基礎
段調入內存
修改段錶
再利用段錶進行地址變換。
總之:就是增加了缺段中斷的請求及處理等功能。
2)分段的共享和保護
分段在邏輯意義上劃分,實現共享和保護都較方便。以下討論具體實現:
①實現共享:共享段錶
在內存中配置一張共享段錶,每個共享段都占有一錶項,記錄如下內容:
共享計數count:
共享段為多個進程所需要,當某進程不再需要它而釋放它時,系統並不回收該段所占內存區,僅當所有共享該段的進程全都不再需要它時,才由系統回收該段所占內存區。設置count用於記錄有多少個進程需要共享該分段。
② 共享段如何分享與回收
共享段的分配
第一個請求使用該共享段的進程A:系統為該共享段分配一物理區,再把共享段裝入該區;
將該區的始址填入A的段錶相應項;
共享段錶中增加一錶項,填寫有關數據,count置1;
其他進程B也調用該共享段時,無需再為該段分配內存,只需在B的段錶中增加一錶項,填寫該共享段的物理地址;在共享段的段錶中,填上調用進程的進程名、存取控制等,再執行count:=count+1操作。
共享段的回收
包括撤消在進程段錶中共享段所對應的錶項,執行count:=count-1。
如果count為0,則由系統回收該共享段的物理內存,並取消共享段錶中該段所對應的錶項。
③ 分段保護
越界檢查
段錶寄存器存放了段錶長度;段錶中存放了每個段的段長。
在進行存儲訪問時,將段號與段錶長度比較,段內地址與段長比較。
存取控制檢查
尤其錶現在不同進程對共享段的不同使用上。段錶每個錶項都設置“存取控制”字段,規定該段的訪問方式:只讀,只執行,讀/寫
環保護機構
規定:低編號的環具有高優先權
遵循的原則:一個程序可以訪問駐留在相同環或較低特權環中的數據。一個程序可以調用駐留在相同環或較高特權環中的服務

版权声明:本文为[sunhao06]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080030284147.html