13 操作系统第三章 内存管理 虚拟内存 请求分页管理方式 页面置换算法 页面分配策略
文章目錄
- 1 虛擬內(nèi)存
- 1.1 傳統(tǒng)存儲管理方式的特征、缺點
- 1.2 局部性原理
- 1.3 虛擬內(nèi)存主要特征
- 1.4 如何實現(xiàn)虛擬內(nèi)存技術
- 1.5 虛擬內(nèi)存的基本概念小結
- 2 請求分頁管理方式
- 2.1 頁表機制
- 2.2 缺頁中斷機構
- 2.3 地址變換機構
- 2.4 請求分頁管理方式小結
- 3 頁面置換算法
- 3.1 最佳置換算法 OPT
- 3.2 先進先出置換算法(FIFO)
- 3.3 最近最久未使用置換算法(LRU)
- 3.4 時鐘置換算法(CLOCK)
- 3.4.1 簡單的CLOCK算法
- 3.4.2 改進型的時鐘置換算法
- 3.5 頁面置換算法小結
- 4 頁面分配策略
- 4.1 頁面分配、置換策略
- 4.1.1 駐留集
- 4.1.2 分配、置換策略
- 4.2 何時調(diào)入頁面
- 4.3 從何處調(diào)入頁面
- 4.4 抖動(顛簸)現(xiàn)象
- 4.5 頁面分配策略小結
1 虛擬內(nèi)存
在傳統(tǒng)存儲管理方式的基礎上引入了交換技術、覆蓋技術,使得內(nèi)存利用率有所提升,并且能從邏輯上擴充內(nèi)存容量。
1.1 傳統(tǒng)存儲管理方式的特征、缺點
可用虛擬存儲技術解決上述問題
1.2 局部性原理
時間局部性:如果執(zhí)行了程序中的某條指令,那么不久后這條指令很有可能再次執(zhí)行;如果某個數(shù)據(jù)被訪問過,不久之后該數(shù)據(jù)很可能再次被訪問。(因為程序中存在大量的循環(huán))
空間局部性:一旦程序訪問了某個存儲單元,在不久之后,其附近的存儲單元也很有可能被訪問。 (因為很多數(shù)據(jù)在內(nèi)存中都是連續(xù)存放的,并且程序的指令也是順序地在內(nèi)存中存放的)
如何應用局部性原理?
高速緩沖技術的思想: 將近期會頻繁訪問到的數(shù)據(jù)放到更高速的存儲器中,暫時用不到的數(shù) 據(jù)放在更低速存儲器中。
快表機制就是將近期常訪問的頁表項副本放到更高速的聯(lián)想寄存器中
-
基于局部性原理,在程序裝入時,可以將程序中很快會用到的部分裝入內(nèi)存,暫時用不到的部分留在外存, 就可以讓程序開始執(zhí)行。
-
在程序執(zhí)行過程中,當所訪問的信息不在內(nèi)存時,由操作系統(tǒng)負責將所需信息從外存調(diào)入內(nèi)存,然后繼續(xù) 執(zhí)行程序。
-
若內(nèi)存空間不夠,由操作系統(tǒng)負責將內(nèi)存中暫時用不到的信息換出到外存。 在操作系統(tǒng)的管理下,在用戶看來似乎有一個比實際內(nèi)存大得多的內(nèi)存,這就是虛擬內(nèi)存
-
操作系統(tǒng)虛擬性的一個體現(xiàn),實際的物理內(nèi)存大小沒有變,只是在邏輯上進行了擴充。
易混知識點:
虛擬內(nèi)存的最大容量是由計算機的地址結構(CPU尋址范圍)確定的
虛擬內(nèi)存的實際容量= min(內(nèi)存和外存容量之和,CPU尋址范圍)
Eg:某計算機地址結構為32位,按字節(jié)編址,內(nèi)存大小為512MB,外存大小為2GB。 則虛擬內(nèi)存的最大容量為2 32B=4GB
虛擬內(nèi)存的實際容量=min(2 32B,512MB+2GB)=2GB+512MB
1.3 虛擬內(nèi)存主要特征
虛擬內(nèi)存有一下三個主要特征:
1.4 如何實現(xiàn)虛擬內(nèi)存技術
虛擬內(nèi)存技術,允許一個作業(yè)分多次調(diào)入內(nèi)存。如果采用連續(xù)分配方式,會不方便實現(xiàn)。因此, 虛擬內(nèi)存的實現(xiàn)需要建立在離散分配的內(nèi)存管理方式基礎上。
主要區(qū)別:
在程序執(zhí)行過程中,當所訪問的信息不在內(nèi)存時,由操作系統(tǒng)負責將所需信息從外存調(diào)入內(nèi)存,然后繼續(xù)執(zhí)行程序。 操作系統(tǒng)要提供請求調(diào)頁(或請求調(diào)段)功能
若內(nèi)存空間不夠,由操作系統(tǒng)負責將內(nèi)存中暫時用不到的信息換出到外存。操作系統(tǒng)要提供頁面置換(或段置換)的功能
1.5 虛擬內(nèi)存的基本概念小結
2 請求分頁管理方式
請求分頁存儲管理與基本分頁存儲管理的主要區(qū)別:
2.1 頁表機制
為此引入頁表機制描述頁面和內(nèi)存的情況
基本分頁存儲管理的頁表VS請求分頁存儲管理的頁表:
2.2 缺頁中斷機構
缺頁中斷是因為當前執(zhí)行的指令想要訪問的目標頁面未調(diào)入內(nèi)存而產(chǎn)生的,因此屬于內(nèi)中斷。
一條指令在執(zhí)行期間,可能產(chǎn)生多次缺頁中斷。
(如:copy A to B,即將邏輯地址A中的數(shù)據(jù)復制到邏輯地址B,而A、B屬于不同的頁面,則有可能產(chǎn)生兩次中斷)
中斷回顧:
2.3 地址變換機構
請求分頁存儲管理的地址變換機構較基本分頁存儲管理的地址變換機構的主要區(qū)別:
新增步驟1:請求調(diào)頁(查到頁表項時進行判斷)
新增步驟2:頁面置換(需要調(diào)入頁面,但沒有空閑內(nèi)存塊時進行)
新增步驟3:需要修改請求頁表中新增的表項
過程如下:
注意:
在具有快表機構的請求分頁系統(tǒng)中,訪問一個邏輯地址時,若發(fā)生缺頁,則地址變換步驟是: 查快表(未命中)——查慢表(發(fā)現(xiàn)未調(diào)入內(nèi)存)——調(diào)頁(調(diào)入的頁面對應的表項會直接加入快表)——查快表(命中)——訪問目標內(nèi)存單元
補充細節(jié):
①只有“寫指令”才需要修改 “修改位”。并且,一般來說只需修改快表中的數(shù)據(jù),只有要將快表項刪除時才需要寫回內(nèi)存中的慢表。這樣可以減少訪存次數(shù)。
②和普通的中斷處理一樣,缺頁中斷處理依然需要保留CPU現(xiàn)場。
③需要用某種“頁面置換算法” 來決定一個換出頁面。
④換入/換出頁面都需要啟動慢速的I/O操作,可見,如果換入/ 換出太頻繁,會有很大的開銷。
⑤頁面調(diào)入內(nèi)存后,需要修改慢表,同時也需要將表項復制到快表中。
2.4 請求分頁管理方式小結
3 頁面置換算法
頁面的換入、換出需要磁盤I/0,會有較大的開銷,因此好的頁面置換算法應該追求更少的缺頁率
3.1 最佳置換算法 OPT
- 最佳置換算法(OPT,Optimal):每次選擇淘汰的頁面將是以后永不使用,或者在最長時間內(nèi)不再被訪問的頁面,這樣可以保證最低的缺頁率。
例:假設系統(tǒng)為某進程分配了三個內(nèi)存塊,并考慮到有一下頁面號引用串(會依次訪問這些頁面):7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
最佳置換算法可以保證最低的缺頁率,但實際上,只有在進程執(zhí)行的過程中才能知道接下來會訪問到的是哪個頁面。操作系統(tǒng)無法提前預判頁面訪問序列。因此,最佳置換算法是無法實現(xiàn)的。
3.2 先進先出置換算法(FIFO)
- 先進先出置換算法(FIFO):每次選擇淘汰的頁面是最早進入內(nèi)存的頁面
- 實現(xiàn)方法:把調(diào)入內(nèi)存的頁面根據(jù)調(diào)入的先后順序排成一個隊列,需要換出頁面時選擇隊頭頁面即可。
- 隊列的最大長度取決于系統(tǒng)為進程分配了多少個內(nèi)存塊。
例:假設系統(tǒng)為某進程分配了三個內(nèi)存塊,并考慮到有以下頁面號引用串:
3,2,1,0,3,2,4,3,2,1,0,4
例:假設系統(tǒng)為某進程分配了四個內(nèi)存塊,并考慮到有以下頁面號引用串:
3,2,1,0,3,2,4,3,2,1,0,4
Belady異常一一當為進程分配的物理塊數(shù)增大時,缺頁次數(shù)不減反增的異常現(xiàn)象。
只有FIFO算法會產(chǎn)生Belady異常。另外,FIFO算法雖然實現(xiàn)簡單,但是該算法與進程實際運行時的規(guī)律不適應,因為先進入的頁面也有可能最經(jīng)常被訪問。因此,算法性能差
3.3 最近最久未使用置換算法(LRU)
- 最近最久未使用置換算法(LRU,least recently used):每次淘汰的頁面是最近最久未使用的頁面
- 實現(xiàn)方法:賦予每個頁面對應的頁表項中,用訪問字段記錄該頁面自上次被訪問以來所經(jīng)歷的時間t。
當需要淘汰一個頁面時,選擇現(xiàn)有頁面中t值最大的,即最近最久未使用的頁面。
例:假設系統(tǒng)為某進程分配了四個內(nèi)存塊,并考慮到有以下頁面號引用串:
1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
在手動做題時,若需要淘汰頁面,可以逆向檢查此時在內(nèi)存中的幾個頁面號。在逆向掃描過程中最后一個出現(xiàn)的頁號就是要淘汰的頁面。
該算法的實現(xiàn)需要專門的硬件支持,雖然算法性能好,但是實現(xiàn)困難,開銷大
3.4 時鐘置換算法(CLOCK)
- 最佳置換算法性能最好,但無法實現(xiàn);
- 先進先出置換算法實現(xiàn)簡單,但算法性能差;
- 最近最久未使用置換算法性能好,是最接近OPT算法性能的,但是實現(xiàn)起來需要專門的硬件支持,算法開銷大。
時鐘置換算法是一種性能和開銷較均衡的算法,又稱CLOCK算法,或最近未用算法(NRU,Not Recently Used)
3.4.1 簡單的CLOCK算法
簡單的CLOCK算法實現(xiàn)方法:為每個頁面設置一個訪問位,再將內(nèi)存中的頁面都通過鏈接指針鏈接成一個循環(huán)隊列。當某頁被訪問時,其訪問位置為1。當需要淘汰一個頁面時,只需檢查頁的訪問位。如果是0,就選擇該頁換出;如果是1,則將它置為0,暫不換出,繼續(xù)檢查下一個頁面,若第一輪掃描中所有頁面都是1,則將這些頁面的訪問位依次置為0后,再進行第二輪掃描(第二輪掃描中一定會有訪問位為0的頁面,因此簡單的CLOCK算法選擇一個淘汰頁面最多會經(jīng)過兩輪掃描)
3.4.2 改進型的時鐘置換算法
- 簡單的時鐘置換算法僅考慮到一個頁面最近是否被訪問過。事實上,如果被淘汰的頁面沒有被修改過,就不需要執(zhí)行I/0操作寫回外存。只有被淘汰的頁面被修改過時,才需要寫回外存。
- 因此,除了考慮一個頁面最近有沒有被訪問過之外,操作系統(tǒng)還應考慮頁面有沒有被修改過。在其他條件都相同時,應優(yōu)先淘汰沒有修改過的頁面,避免I/0操作。這就是改進型的時鐘置換算法的思想。
- 修改位=0,表示頁面沒有被修改過;修改位=1,表示頁面被修改過。
- 為方便討論,用(訪問位,修改位)的形式表示各頁面狀態(tài)。如(1,1)表示一個頁面近期被訪問過,且被修改過。
算法規(guī)則:將所有可能被置換的頁面排成一個循環(huán)隊列
由于第二輪已將所有幀的訪問位設為0,因此經(jīng)過第三輪、第四輪掃描一定會有一個幀被選中,因此改進型CLOCK置換算法選擇一個淘汰頁面最多會進行四輪掃描
3.5 頁面置換算法小結
4 頁面分配策略
4.1 頁面分配、置換策略
4.1.1 駐留集
- 駐留集:指請求分頁存儲管理中給進程分配的物理塊的集合。
- 在采用了虛擬存儲技術的系統(tǒng)中,駐留集大小一般小于進程的總大小。
若駐留集太小,會導致缺頁頻繁,系統(tǒng)要花大量的時間來處理缺頁,實際用于進程推進的時間很少;駐留集太大,又會導致多道程序并發(fā)度下降,資源利用率降低。所以應該選擇一個合適的駐留集大小。
考慮一個極端情況,若某進程共有100個頁面,則該進程的駐留集大小為100時進程可以全部放入內(nèi)存,運行期間不可能再發(fā)生缺頁。若駐留集大小為1,則進程運行期間必定會極頻繁地缺頁。
注意:系統(tǒng)為某個進程分配N個物理塊等價于某個進程的駐留集大小為N
4.1.2 分配、置換策略
分配、置換策略搭配:
這種策略的缺點是:很難在剛開始就確定應為每個進程分配多少個物理塊才算合理。(采用這種策略的系統(tǒng)可以根據(jù)進程大小、優(yōu)先級、或是根據(jù)程序員給出的參數(shù)來確定為一個進程分配的內(nèi)存塊數(shù))
采用這種策略時,只要某進程發(fā)生缺頁,都將獲得新的物理塊,僅當空閑物理塊用完時,系統(tǒng)才選擇一個未鎖定的頁面調(diào)出。被選擇調(diào)出的頁可能是系統(tǒng)中任何一個進程中的頁,因此這個被選中的進程擁有的物理塊會減少,缺頁率會增加。
鎖定:系統(tǒng)會鎖定一些頁面,這些頁面中的內(nèi)容不能置換出外存(如:重要的內(nèi)核數(shù)據(jù)可以設為“鎖定”)
可變分配全局置換:只要缺頁就給分配新物理塊
可變分配局部置換:要根據(jù)發(fā)生缺頁的頻率來動態(tài)地增加或減少進程的物理塊
4.2 何時調(diào)入頁面
4.3 從何處調(diào)入頁面
4.4 抖動(顛簸)現(xiàn)象
剛剛換出的頁面馬上又要換入內(nèi)存,剛剛換入的頁面馬上又要換出外存,這種頻繁的頁面調(diào)度行為稱為抖動,或顛簸。
產(chǎn)生抖動的主要原因是進程頻繁訪問的頁面數(shù)目高于可用的物理塊數(shù)(分配給進程的物理塊不夠)
為進程分配的物理塊太少,會使進程發(fā)生抖動現(xiàn)象。為進程分配的物理塊太多,又會降低系統(tǒng)整體的并發(fā)度,降低某些資源的利用率
為了研究為應該為每個進程分配多少個物理塊,Denning提出了進程 “工作集”的概念
駐留集VS 工作集
操作系統(tǒng)會根據(jù)“窗口尺寸”來算出工作集。
例: 某進程的頁面訪問序列如下,窗口尺寸為4,各時刻的工作集為?
工作集大小可能小于窗口尺寸,實際應用中,操作系統(tǒng)可以統(tǒng)計進程的工作集大小,根據(jù)工作集大小給進程分配若干內(nèi)存塊。
如:窗口尺寸為5,經(jīng)過一段時間的監(jiān)測發(fā)現(xiàn)某進程的工作集最大為3,那么 說明該進程有很好的局部性,可以給這個進程分配3個以上的內(nèi)存塊即可滿足進程的運行需要。
一般來說,駐留集大小不能小于工作集大小,否則進程運行過程中將頻繁缺頁。
拓展:基于局部性原理可知,進程在一段時間內(nèi)訪問的頁面與不久之后會訪問的頁面是有相關性的。 因此,可以根據(jù)進程近期訪問的頁面集合(工作集)來設計一種頁面置換算法——選擇一個不在工作集中的頁面進行淘汰。
4.5 頁面分配策略小結
總結
以上是生活随笔為你收集整理的13 操作系统第三章 内存管理 虚拟内存 请求分页管理方式 页面置换算法 页面分配策略的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 基于ARQ反馈的无人机通信中继自主选择研
- 下一篇: 数字化转型知识方法系列之三:以价值效益为