計算機操作系統(tǒng)-第4章 存儲器管理

第四章存儲器管理1/14/20241存儲器是計算機系統(tǒng)的重要資源概述“瓶頸〞：關鍵、緊張1/14/20242主要內(nèi)容：4.2程序的裝入和鏈接4.3連續(xù)分配方式4.4根本分頁存儲管理方式4.5根本分段存儲管理方式4.6虛擬存儲器的根本概念4.7請求分頁存儲管理方式4.8頁面置換算法4.9請求分段存儲管理方式4.1存儲器的層次結構1/14/20243本章重點：存儲器的層次結構；動態(tài)分區(qū)分配；對換的概念；根本分頁存儲管理的實現(xiàn)原理；根本分段存儲管理的地址變換機構；虛擬存儲器的根本概念；常用的頁面置換算法本章難點：動態(tài)分區(qū)分配算法；根本分頁存儲管理的地址變換機構的實現(xiàn)；常用的頁面置換算法的原理及應用本章方案學時：121/14/202444.1存儲器的層次結構P116理想情況下：存儲器速度快；容量大；價格廉價在現(xiàn)代計算機系統(tǒng)中，存儲部件通常采用層次結構。概述1/14/20245本節(jié)主要內(nèi)容：4.1.1多級存儲器結構4.1.2主存儲器與存放器4.1.3高速緩存和磁盤緩存本節(jié)學習目標：掌握存儲器的層次結構；了解主存、存放器、高速緩存、磁盤緩存的概念及作用返回1/14/202464.1.1多級存儲器結構P116存儲層次：CPU存放器；主存；輔助存儲器輔助存儲器包括：磁盤；可移動存儲介質(zhì)主存包括：高速緩存；主存；磁盤緩存1/14/20247存儲器層次：存放器主存輔助存儲器主存〔內(nèi)存〕高速緩存磁盤緩存1/14/202484.1.2主存儲器與存放器1.主存儲器〔簡稱主存或內(nèi)存〕定義：是由存儲單元〔字節(jié)或字〕組成的一維連續(xù)的地址空間，簡稱內(nèi)存空間。內(nèi)存可以分為：系統(tǒng)區(qū)：用于存放操作系統(tǒng)常駐內(nèi)存局部用戶區(qū)：用于裝入并存放用戶程序和數(shù)據(jù)作用：用來存放當前正在運行程序的代碼及數(shù)據(jù)注意：CPU只能直接訪問主存1/14/20249存儲管理目的1、充分利用內(nèi)存，為多道程序并發(fā)執(zhí)行提供存儲根底2、盡可能方便用戶使用自動裝入用戶程序用戶程序中不必考慮硬件細節(jié)3、系統(tǒng)能夠解決程序空間比實際內(nèi)存空間大的問題1/14/2024104、程序在執(zhí)行時可以動態(tài)伸縮5、內(nèi)存存取速度快6、存儲保護與平安7、共享與通信8、了解有關資源的使用狀況1/14/202411

存儲管理的任務1、內(nèi)存空間的管理、分配與回收2、存儲共享3、存儲保護與平安4、內(nèi)存“擴充〞5、地址映射〔地址重定位〕1/14/202412地址映射〔地址重定位，地址變換〕(1)邏輯地址〔相對地址，虛地址〕(2)物理地址〔絕對地址，實地址〕(3)地址映射1/14/202413內(nèi)存空間〔或物理空間〕內(nèi)存是由假設干個存儲單元組成的，每個存儲單元有一個編號，這種編號可唯一標識一個存儲單元，稱為內(nèi)存地址〔或物理地址〕。內(nèi)存地址都是絕對地址.內(nèi)存中存儲單元的地址，可直接尋址1/14/202414邏輯空間源程序經(jīng)過匯編或編譯后，形成假設干個目標程序(模塊)，每個目標程序都是以0為基址順序進行編址的，這樣生成的目標程序占據(jù)一定的地址空間，稱為作業(yè)的邏輯地址空間，簡稱邏輯空間。每個目標模塊的地址都是相對地址.注意：不能用邏輯地址在內(nèi)存中讀取信息在邏輯空間中每條指令的地址和指令中要訪問的操作數(shù)地址統(tǒng)稱為邏輯地址。1/14/202415為了保證CPU執(zhí)行指令時可正確訪問存儲單元，需將用戶程序中的邏輯地址轉(zhuǎn)換為運行時由機器直接尋址的物理地址，這一過程稱為地址映射地址映射1/14/202416以下圖為作業(yè)的名空間、邏輯地址空間和裝入后的物理空間1/14/202417地址映射LoadA2003456。。1200物理地址空間LoadAdata1data13456源程序LoadA20034560100200編譯連接邏輯地址空間BA=10001/14/202418地址映射〔重定位〕的原因:①當程序裝入內(nèi)存時,操作系統(tǒng)要為該程序分配一個適宜的內(nèi)存空間，由于程序的邏輯地址與分配到內(nèi)存物理地址不一致,而CPU執(zhí)行指令時，是按物理地址進行的，所以要進行地址轉(zhuǎn)換②內(nèi)存中進程之間的碎片緊湊時需要移動相關進程的內(nèi)存位置；③內(nèi)存中多個并發(fā)進程在執(zhí)行過程中需要掛起調(diào)出內(nèi)存，當條件成熟時再被激活調(diào)入內(nèi)存繼續(xù)執(zhí)行，這時的該進程的地址往往已經(jīng)改變；

1/14/2024192.存放器作用：主要用于加速存儲器的訪問速度1/14/2024204.1.3高速緩存和磁盤緩存1.高速緩存其容量遠大于存放器，比內(nèi)存小兩到三個數(shù)量級左右；但訪問速度快于主存作用：將主存中一些經(jīng)常訪問的信息存放在高速緩存中，減少訪問主存的次數(shù)，可大幅度提高程序執(zhí)行速度1/14/2024212.磁盤緩存作用：將頻繁使用的一局部磁盤數(shù)據(jù)和信息，暫時存放在磁盤緩存中，可減少訪問磁盤的次數(shù)注意：磁盤緩存本身并不是一種實際存在的存儲介質(zhì)1/14/202422

高速緩存Cache：少量的、非?？焖?、昂貴、易變的內(nèi)存RAM：假設干兆字節(jié)、中等速度、中等價格、易變的磁盤：數(shù)百兆或數(shù)千兆字節(jié)、低速、價廉、不易變的存儲器小結返回1/14/2024234.2程序的裝入和鏈接P118將一個用戶源程序變?yōu)榭稍趦?nèi)存中運行的程序，通常經(jīng)過以下幾步：〔1〕編譯〔3〕裝入〔2〕鏈接概述1/14/202424本節(jié)主要內(nèi)容：4.2.1程序的裝入4.2.2程序的鏈接本節(jié)學習目標：了解程序的裝入方式和裝入過程；了解程序的鏈接方式和鏈接過程；熟練掌握并理解重定位的概念返回1/14/2024254.2.1程序的裝入將一個裝入模塊裝入內(nèi)存時，可采用三種方式：在程序中使用絕對地址2.可重定位方式3.動態(tài)運行時裝入方式1/14/2024262.可重定位裝入方式重定位：我們把在裝入時對目標程序中的指令和數(shù)據(jù)地址的修改正程稱為重定位。由于地址變換只是在裝入時一次完成，以后不再改變，故稱為靜態(tài)重定位。1/14/202427作業(yè)裝入內(nèi)存時的情況0100025005000作業(yè)地址空間LOADl,2500365內(nèi)存空間10000110001250015000LOADl,25003651/14/202428靜態(tài)重定位當用戶程序被裝入內(nèi)存時，一次性實現(xiàn)邏輯地址到物理地址的轉(zhuǎn)換，以后不再轉(zhuǎn)換〔一般在裝入內(nèi)存時由軟件完成〕動態(tài)重定位在程序運行過程中要訪問數(shù)據(jù)時再進行地址變換〔即在逐條指令執(zhí)行時完成地址映射。一般為了提高效率，此工作由硬件地址映射機制來完成?！灿布С?，軟硬件結合完成〕硬件上需要一對存放器的支持1/14/20242903456......LOADA200......0100200300.........LOADA2003456邏輯地址空間110012001300物理地址空間200VR+1000BR

動態(tài)重定位1/14/2024303.動態(tài)運行時裝入方式動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序要真正執(zhí)行時才進行。需要特殊硬件的支持?？芍囟ㄎ谎b入方式存在的問題：不允許程序運行時在內(nèi)存中移動位置。1/14/2024314.1.2程序的鏈接包括:1.靜態(tài)鏈接2.裝入時動態(tài)鏈接3.運行時動態(tài)鏈接1/14/2024321.靜態(tài)鏈接方式0L-1模塊ACALLBReturn:0M-1模塊BCALLCReturn:0N-1模塊CReturn:(a)目標模塊0L-1LL+M-1L+ML+M+N-1AJSR〞L〞BJSR〞L+M〞C(b)裝入模塊1/14/202433靜態(tài)鏈接方式中需解決的問題(1)對相對地址進行修改(2)變換外部調(diào)用符號上一頁1/14/2024342.裝入時動態(tài)鏈接優(yōu)點:(1)便于修改和更新(2)便于實現(xiàn)對目標模塊的共享1/14/2024353.運行時動態(tài)鏈接根本思想:對某些模塊的鏈接推遲到執(zhí)行時才執(zhí)行優(yōu)點:1)可加快程序的裝入過程;2)可節(jié)省大量的內(nèi)存空間1/14/202436三種鏈接方式的比較:運行時動態(tài)鏈接:裝入時動態(tài)鏈接:靜態(tài)鏈接方式:裝入前鏈接裝入時鏈接運行時鏈接返回1/14/2024374.3連續(xù)分配方式P121〔1〕靜態(tài)存儲分配：內(nèi)存分配按分配時機的不同，可分為兩種方式:指內(nèi)存分配是在作業(yè)運行之前各目標模塊連接后，把整個作業(yè)一次性全部裝入內(nèi)存，并在作業(yè)的整個運行過程中，不允許作業(yè)再申請其他內(nèi)存，或在內(nèi)存中移動位置。也就是說，內(nèi)存分配是在作業(yè)運行前一次性完成的。概述1/14/202438作業(yè)要求的根本內(nèi)存空間是在目標模塊裝入內(nèi)存時分配的，但在作業(yè)運行過程中，允許作業(yè)申請附加的內(nèi)存空間，或是在內(nèi)存中移動，即分配工作可以在作業(yè)運行前及運行過程中逐步完成。內(nèi)存分配續(xù):〔2〕動態(tài)存儲分配1/14/202439內(nèi)存分配連續(xù)分配方式離散分配方式分區(qū)分配固定分區(qū)分配動態(tài)分區(qū)分配可重定位分區(qū)分配根本分頁存儲管理方式根本分段存儲管理方式段頁式存儲管理方式請求分頁存儲管理方式請求分段存儲管理方式特點：一次性駐留性1/14/202440連續(xù)分配是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間。

4.3.1單一連續(xù)分配4.3連續(xù)分配方式(續(xù))4.3.2固定分區(qū)分配4.3.3動態(tài)分區(qū)分配適合單用戶單任務OS4.3.6可重定位分區(qū)分配本節(jié)主要內(nèi)容：4.3.4伙伴系統(tǒng)4.3.5哈希算法4.3.7對換1/14/202441本節(jié)學習目標：了解固定分區(qū)分配方式；掌握動態(tài)分區(qū)分配的相關算法；了解伙伴系統(tǒng)；了解可重定位分區(qū)分配的實現(xiàn)過程；理解并熟練掌握對換的定義，了解引入對換后對換空間的管理理解并掌握碎片的定義返回1/14/202442分區(qū)式分配方式由于要求將一個用戶程序分配到一個連續(xù)的內(nèi)存空間中，因此可能產(chǎn)生多個不可利用的內(nèi)存零頭?！不蚍Q“碎片〞〕4.3.2固定分區(qū)分配1/14/2024431劃分分區(qū)的方法(1)分區(qū)大小相等缺點：當程序太小時，會造成內(nèi)存空間的浪費；反之，可能因分區(qū)的大小尚缺乏以裝入該程序。(2)分區(qū)大小不等用途:用一臺計算機控制多個相同對象的場合可根據(jù)程序的大小為之分配適當?shù)姆謪^(qū).1/14/2024442.內(nèi)存分配將分區(qū)根據(jù)大小排隊，并為之建立一張分區(qū)使用表。分區(qū)號大小〔KB〕始址〔KB〕狀態(tài)11530已分配23045已分配35075已分配4100125未分配分區(qū)說明表1/14/2024450304575125OS常駐內(nèi)存局部作業(yè)A作業(yè)B作業(yè)C存儲空間分配情況作業(yè)A需要15KB作業(yè)B需要30KB作業(yè)C需要50KB未分配1/14/2024464.3.3動態(tài)分區(qū)分配〔2〕分區(qū)的分配算法思想:根據(jù)進程的實際需要,動態(tài)地為之分配內(nèi)存空間.〔1〕分區(qū)分配中使用的數(shù)據(jù)結構〔3〕分區(qū)的分配和回收操作1/14/202447可變式(動態(tài))分區(qū)內(nèi)存使用情況示意圖1/14/2024481.分區(qū)分配中的數(shù)據(jù)結構(1)空閑分區(qū)表序號分區(qū)大小分區(qū)始址狀態(tài)16444可用224132可用1/14/202449(2)空閑分區(qū)鏈N個字節(jié)可用前向指針0后向指針N＋2N＋201/14/2024502.分區(qū)分配算法(1)1)首次適應算法(firstfit,簡稱FF〕要求空閑分區(qū)鏈以地址遞增的次序鏈接。該算法傾向于優(yōu)先利用內(nèi)存中低址局部的空閑分區(qū)。優(yōu)點：保存了高址局部的大空閑區(qū)。缺點：使低址局部不斷被劃分，增加了查找可用空閑分區(qū)的開銷。1/14/202451基于首次適應算法的動態(tài)分區(qū)分配過程：38KB60KB40KB例1假設作業(yè)需要36KB的存儲空間空閑分區(qū)鏈以地址遞增的次序鏈接例2假設作業(yè)需要58KB的存儲空間46KB10KB2KB1/14/202452首次適應算法的空閑分區(qū)鏈表組織形式1/14/2024532)循環(huán)首次適應算法〔nextfit)在為進程分配內(nèi)存空間時，不再每次從鏈首開始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找，直至能找到第一個能滿足要求的空閑分區(qū)。優(yōu)缺點與FF相反。2.分區(qū)分配算法(2)1/14/202454基于循環(huán)首次適應算法的動態(tài)分區(qū)分配過程：38KB60KB40KB例1假設作業(yè)需要36KB的存儲空間空閑分區(qū)鏈以地址遞增的次序鏈接例2假設作業(yè)需要58KB的存儲空間46KB10KB2KB〔從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找〕1/14/2024553)最正確適應算法〔bestfit〕最正確：每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)。該算法將空閑分區(qū)按其大小以遞增的順序形成一空閑分區(qū)鏈。這樣，第一次找到的滿足要求的空閑區(qū)，必然是最優(yōu)的。2.分區(qū)分配算法(3)1/14/202456基于最正確適應算法的動態(tài)分區(qū)分配過程：40KB46KB60KB例1假設作業(yè)需要40KB的存儲空間空閑分區(qū)鏈以分區(qū)大小遞增的次序鏈接例2假設作業(yè)需要45KB的存儲空間38KB1KB〔假設非正好，所?？臻g也是最小的，常常不能再次分配〕1/14/202457最正確適應算法的空閑分區(qū)鏈表組織形式1/14/2024582.分區(qū)分配算法(4)4〕最壞適應算法〔worstfit〕思想：總是挑選一個最大的空閑區(qū)分割給作業(yè)使用。優(yōu)點：使剩下的空閑區(qū)不至于太小，產(chǎn)生碎片的幾率最小，對中小作業(yè)有利；同時該算法查找效率很高。缺點：使存儲器中缺乏大的空閑分區(qū)。1/14/202459最壞適應算法的空閑分區(qū)鏈表組織形式1/14/2024602.分區(qū)分配算法(5)前面的幾種算法稱為順序搜索法。5〕快速適應算法〔quickfit〕思想：將空閑分區(qū)根據(jù)其容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設立一個空閑分區(qū)鏈表；在內(nèi)存中設立一張管理索引表優(yōu)點：查找效率高；在進行空閑分區(qū)分配時，不會對任何分區(qū)產(chǎn)生分割，不會產(chǎn)生內(nèi)存碎片又稱為分類搜索法1/14/202461缺點：〔1〕在分區(qū)歸還主存時算法復雜，系統(tǒng)開銷大；〔2〕分配空閑分區(qū)時以進程為單位，一個分區(qū)只屬于一個進程，或多或少存在一定的浪費；〔3〕空閑分區(qū)劃分越細，浪費越嚴重典型的以空間換時間1/14/2024623分區(qū)分配操作1)分配內(nèi)存從頭開始查表檢索完否?返回m.size>u.size?繼續(xù)檢索下一個≤sizeYNNYNY內(nèi)存分配流程1/14/202463內(nèi)存分配流程續(xù):從該分區(qū)中劃出u.size大小的分區(qū)將該分區(qū)從鏈中移出YN將該分區(qū)分配給請求者修改有關數(shù)據(jù)結構返回1/14/2024642)回收內(nèi)存〔1〕回收區(qū)與插入點的前一個分區(qū)相鄰接〔2〕回收區(qū)與插入點的后一個分區(qū)相鄰接回收區(qū)F1(1)回收區(qū)F2(2)要考慮分區(qū)的合并F1合并后分區(qū)的大小為F1和回收區(qū)的和，始址仍為F1的始址F2合并后分區(qū)的大小為F2和回收區(qū)的和，始址為回收區(qū)的始址1/14/202465〔3〕回收區(qū)與插入點的前、后兩個分區(qū)相鄰接回收區(qū)F1F2(4)回收區(qū)既不與F1相鄰，也不與F2相鄰(3)此時應新建一個結點1/14/2024664.3.4伙伴系統(tǒng)伙伴系統(tǒng)的提出是為了解決固定分區(qū)和動態(tài)分區(qū)方式存在的缺乏1/14/2024674.3.5哈希算法1/14/2024684.3.6可重定位分區(qū)分配(1)靜態(tài)地址重定位靜態(tài)地址重定位是在程序執(zhí)行之前由操作系統(tǒng)的重定位裝入程序完成的。(2)動態(tài)地址重定位

動態(tài)地址重定位是在程序執(zhí)行期間進行的。

概念：1/14/2024691.動態(tài)重定位的引入內(nèi)存使用情況緊湊定義：這種通過移動，把多個分散的小分區(qū)拼接成大分區(qū)的方法被稱為“拼接〞或“緊湊〞。1/14/202470缺乏:花費處理機時間必須對移動了的程序或數(shù)據(jù)重新定位緊湊后OS040K181K256K已使用空閑區(qū)OS1/14/202471采用動態(tài)重定位時內(nèi)存空間及地址重定位示意圖2.動態(tài)重定位的實現(xiàn)1/14/2024723.動態(tài)重定位分區(qū)分配算法增加了緊湊功能1/14/2024734.3.7對換(Swapping)P1291.對換的引入定義：所謂“對換〞，是指把內(nèi)存中暫不能運行的進程，或暫時不用的程序和數(shù)據(jù)，換出到外存上，以騰出足夠的內(nèi)存空間，把已具備運行條件的進程，或進程所需要的程序和數(shù)據(jù)，換入內(nèi)存。對換是提高內(nèi)存利用率的有效措施1/14/202474這種對換被廣泛用于分時系統(tǒng)中?？商岣邇?nèi)存的利用率。假設對換是以“頁〞或“段〞為單位，那么分別被稱為“頁面對換〞或“分段對換“這種對換方法是實現(xiàn)請求分頁及請求分段式存儲器的根底。目的是為了支持虛擬存儲系統(tǒng)。假設對換以這個進程為單位，那么稱之為“整體對換〞或“進程對換〞對換的引入續(xù):1/14/2024752.對換空間的管理在具有對換功能的OS中，通常把外存分為文件區(qū)和對換區(qū)。對對換空間管理的主要目標，是提高進程換進、換出的速度對文件區(qū)管理的主要目標，是提高文件存儲空間的利用率1/14/2024763.進程的換出與換入(1)進程的換出首先選擇處于阻塞或睡眠狀態(tài)的進程；(2)進程的換入首先選擇換出時間最久“就緒且換出〞的進程。其次選擇優(yōu)先級低的就緒進程選出被換出的進程:返回1/14/2024774.4根本分頁存儲管理方式P130概述離散分配方式的提出：減少碎片；減少因緊湊而造成的系統(tǒng)開銷分頁存儲管理段頁式存儲管理分段存儲管理離散分配方式：1/14/202478本節(jié)主要內(nèi)容：4.4.1頁面與頁表4.4.2地址變換機構4.4.3兩級和多級頁表1/14/202479本節(jié)學習目標：理解并掌握頁面、物理塊的定義；理解分頁地址中的地址結構并會求頁號和頁內(nèi)位移；熟練掌握根本的地址變換機構的變換過程；掌握具有快表的地址變換機構的變換過程；了解兩級和多級頁表；返回1/14/2024804.4.1頁面與頁表在分頁存儲管理方式中，將一個進程的邏輯地址空間分成假設干個大小相等的片，稱為頁面或頁。相應地，內(nèi)存空間也分成與頁相同大小的假設干個存儲塊，或稱為物理塊或頁框。1.頁面1)頁面和物理塊由于進程的最后一頁經(jīng)常裝不滿一塊，而形成不可利用的碎片，稱為“頁內(nèi)碎片〞。1/14/202481用戶程序0頁1頁2頁3頁n頁內(nèi)存012345671/14/202482在分頁系統(tǒng)中，頁面的大小是由機器的地址結構所決定的，即由硬件決定。假設選擇的頁面較小:一方面可使內(nèi)存碎片小，并減少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率；假設選擇的頁面較大，那么正好與上述相反。頁面的大小一般為512B~8KB2)頁面大小但另一方面，也會使每個進程要求較多的頁面，從而導致頁表過長，占用大量內(nèi)存；此外，還會降低頁面換進換出的效率。1/14/202483在分頁存儲管理方式中的地址結構如下：頁號P位移量W01112310~11位是頁內(nèi)地址，即每頁的大小為4KB；12~31位是頁號，地址空間最多允許有1MB頁。2.地址結構地址的高位局部為頁號，低位局部為頁內(nèi)地址1/14/202484例子：如何求頁號和頁內(nèi)位移假設給定一個邏輯地址空間的地址為A，頁面的大小為L，那么頁號P和頁內(nèi)地址d可按下式求得：P=INT[A/L]d=AMODL如：頁面大小為1KB，設A=2170,那么P=2,d=122.隨堂練習：頁面大小為1KB，〔1〕A=500〔2〕A=2500那么P、d分別為多少1/14/2024853.頁表系統(tǒng)為某個進程建立一張頁面映射表，簡稱頁表。進程執(zhí)行時，通過查找頁表，即可找到每頁在內(nèi)存中的物理塊號?？梢姡摫淼淖饔檬菍崿F(xiàn)從頁號到物理塊號的地址映射。1/14/202486頁表頁號塊號02132638459121/14/202487純(根本)分頁存儲管理示意圖1/14/2024884.4.2地址變換機構為了能將用戶地址空間中的邏輯地址，變換為內(nèi)存空間中的物理地址，在系統(tǒng)中必須設置地址變換機構。地址變換機構的任務，就是將邏輯地址中的頁號，轉(zhuǎn)換為內(nèi)存中的物理塊號。地址變換是借助于頁表來完成的.1/14/2024891.根本的地址變換機構頁表的功能可以由一組專門的存放器來實現(xiàn)，一個頁表項用一個存放器。頁表大多駐留內(nèi)存。在進程未執(zhí)行時，每個進程對應的頁表的始址和長度存放在進程的PCB中，當該進程被調(diào)度時，就將它們裝入頁表存放器在系統(tǒng)中設置一個頁表存放器PTR，其中存放頁表在內(nèi)存的始址和頁表的長度。1/14/202490在進行地址變換時，系統(tǒng)將頁號與頁表長度進行比較，如果頁號大于頁表存放器中的頁表長度，那么訪問越界，產(chǎn)生越界中斷。如未出現(xiàn)越界，那么根據(jù)頁表存放器中的頁表始址和頁號計算出該頁在頁表項中的位置，得到該頁的物理塊號，將此物理塊號裝入物理地址存放器中。與此同時，將有效地址〔邏輯地址〕存放器中頁內(nèi)地址直接裝入物理地址存放器的塊內(nèi)地址字段中，這樣便完成了從邏輯地址到物理地址的變換。變換過程描述：1/14/202491根本地址變換舉例(每頁1KB(1024))越界中斷頁表存放器邏輯地址2500頁號塊號

0125*1024+452物理地址5572

塊號5塊內(nèi)地址452

頁號2頁內(nèi)地址452頁表始址頁表長度﹥

2 4 51/14/202492在請求分頁存儲管理方案中，假設某用戶空間為16個頁面，頁長1KB，現(xiàn)有頁表如下，那么邏輯地址0A1F〔H〕所對應的物理地址為〔〕。

0115233742A．0E1F〔H〕B．031F〔H〕C．0A1F〔H〕D．021F〔H〕隨堂練習題：答案為：A1/14/2024932.具有快表的地址變換機構由于頁表是存放在內(nèi)存中的，這使CPU每次要存取一個數(shù)據(jù)時，都要兩次訪問內(nèi)存。為了提高地址變換速度，可在地址變換機構中，增設一個特殊高速緩沖存儲器，又稱為“聯(lián)想存儲器〞,或稱為“快表〞.1/14/202494具有快表的地址變換機構地址變換過程：在CPU給出有效地址后，地址變換機構自動地將頁號送入高速緩存，確定所需要的頁是否在快表中。假設是，那么直接讀出該頁所對應的物理塊號，送入物理地址存放器；假設在快表中未找到對應的頁表項，那么需再訪問內(nèi)存中的頁表，找到后，把從頁表中讀出的頁表項存入快表中的一個存放器單元中，以取代一個舊的頁表項。1/14/202495p’頁表地址越界

l比較P>=1pp’...快表

b+頁號p

頁內(nèi)地址dP’d物理地址頁表地址存放器頁表長度存放器邏輯地址地址映射機制1/14/202496具有快表的地址變換機構由于本錢的原因，快表不可能做得很大，通常只能存放16~512個頁表項。例如，在Intel80486中有32個。這對中、小型作業(yè)來說，已可能把全部頁表項放入快表中；但對于大型作業(yè)來說，那么只能將一局部頁表放入快表中。由于對程序和數(shù)據(jù)的訪問往往帶有局限性，所以快表的命中率可以到達80%～90%。1/14/202497分頁存儲管理的優(yōu)缺點：優(yōu)點：解決了碎片問題便于管理缺點：不易實現(xiàn)共享不便于動態(tài)連接1/14/202498隨堂練習題：一具有快表的分頁系統(tǒng)中，邏輯地址訪問內(nèi)存的時間是100毫秒，訪問快表的時間是20毫秒。問：設從快表中找到所需頁表項的概率為85%，計算CPU存取一個數(shù)據(jù)時的有效訪問時間。參考答案：【20×0.85+〔100+20〕×0.15】+100返回1/14/2024994.4.3兩級和多級頁表引子:每個進程的頁表項很多,而且必須為頁表分配連續(xù)的存儲空間.解決方法:(1)采用離散分配方式(2)只將當前需要的局部頁表項調(diào)入內(nèi)存1/14/20241001.兩級頁表機制兩級頁表系統(tǒng)將32位邏輯地址空間的地址分成三段：其中，頁表目錄號〔外層頁號p1〕和頁號〔外層頁內(nèi)地址p2〕兩項各占10位，偏移量〔頁內(nèi)地址d〕占12位。1/14/2024101兩級頁表機制

31222112110

外層頁表頁表物理地址

外層頁號p1外層頁內(nèi)地址p2頁內(nèi)地址d外層頁表存放器++

bd邏輯地址結構1/14/2024102頁目錄地址目錄位移頁表位移頁位移邏輯地址頁表地址...頁目錄〔每進程一個〕塊號...頁表代碼或數(shù)據(jù)...內(nèi)存塊二級頁表結構及地址映射++1/14/2024103兩級頁表機制圖第0頁頁表〔物理塊號10〕內(nèi)存010┇110232第1頁頁表〔物理塊號25〕01┇1023第N頁頁表〔物理塊號120〕01

外層頁表┇102310251201214323515115201……121314……32333435……151152……返回1/14/20241044.5根本分段存儲管理方式P135分頁存儲管理的主要動力，是提高內(nèi)存利用率；分段存儲管理方式的引入，那么為了滿足用戶在編程和使用上多方面的要求。概述1/14/2024105本節(jié)主要內(nèi)容：4.5.1分段存儲管理方式的引入4.5.2分段系統(tǒng)的根本原理4.5.3信息共享4.5.4段頁式存儲管理方式1/14/2024106本節(jié)學習目標：了解分段存儲管理方式引入的原因；掌握分段系統(tǒng)的根本原理：什么是分段；分段地址中的地址結構；段表的表示；分段地址變換機構掌握什么是“純代碼〞〔可重入代碼〕；了解段頁式存儲管理方式；熟練掌握分頁和分段的主要區(qū)別；返回1/14/20241074.5.1分段存儲管理方式的引入1)、方便編程2)、信息共享3)、信息保護4)、動態(tài)鏈接5)、動態(tài)增長例如:LOAD1,[A]|<D>;STORE1,[B]|<C>;1/14/20241081〕用戶程序劃分按程序自身的邏輯關系劃分為假設干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段也從0開始編址，段內(nèi)地址是連續(xù)的4.5.2分段系統(tǒng)的根本原理1.分段1/14/20241092〕分段的邏輯地址作業(yè)的邏輯地址由段號和段內(nèi)地址組成，作業(yè)的地址空間是二維的。段號段內(nèi)地址3116150在該地址結構中，允許一個作業(yè)最多有64K個段，每個段的最大長度為64KB。分段系統(tǒng)的地址結構1/14/2024110內(nèi)存空間被動態(tài)的劃分為假設干個長度不相同的區(qū)域，這些區(qū)域被稱為物理段，每個物理段由起始地址和長度確定3〕內(nèi)存劃分1/14/20241114〕內(nèi)存分配以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間〔內(nèi)存隨機分割，需要多少分配多少〕，但各段之間可以不連續(xù)存放1/14/20241122.段表在分段式存儲管理方式中，系統(tǒng)為每個段分配一個連續(xù)的分區(qū)，而進程中的各個段可以離散地放入內(nèi)存中不同的分區(qū)中。系統(tǒng)為每個進程建立一張段映射表，簡稱“段表〞段表可放在一組存放器中，但通常放在內(nèi)存中。1/14/2024113段表：它記錄了段號，段的首〔地〕址和長度之間的關系每一個程序設置一個段表，放在內(nèi)存屬于進程的現(xiàn)場信息段號012段首址段長度58K20K100K110K260K140K1/14/2024114段號段長基址012330K40K20K80K15K120K10K150K段表作業(yè)空間(MAIN)=0030(X)=1020(D)=201530K20K15K4080120內(nèi)存空間1/14/2024115首次適應；最正確適應；最壞適應內(nèi)存的分配算法：1/14/20241163.地址變換機構控制存放器段表始址段表長度2100有效地址段號S位移量W>越界+25008K+8292物理地址8K829287928×1024+1001/14/2024117優(yōu)點：便于動態(tài)申請內(nèi)存管理和使用統(tǒng)一化便于共享便于動態(tài)鏈接缺點：產(chǎn)生碎片課后思考題：與可變分區(qū)存儲管理方案的相同點與不同點？1/14/20241184.分頁和分段的主要區(qū)別相同點：都采用離散分配方式，都通過地址映射機構來實現(xiàn)地址變換。區(qū)別：〔1〕頁是信息的物理單位，分頁是由于系統(tǒng)管理的需要；段是信息的邏輯單位，分段是為了更好地滿足用戶的需要。〔2〕頁的大小固定且由系統(tǒng)確定；而段的長度不固定〔3〕分頁的作業(yè)地址空間是一維的，分段的作業(yè)地址空間是二維的。1/14/2024119分頁和分段比較：1/14/2024120分頁和分段比較1/14/20241214.5.3信息共享例子:有一個多用戶系統(tǒng),可同時接納40個用戶,它們都執(zhí)行一個文本編輯程序.如果文本編輯程序含有160KB的代碼和40KB的數(shù)據(jù)區(qū),假設不允許共享，那么總共需要:8MB的內(nèi)存空間.如果代碼是可重入的,那么總共需要:40×40+160=1760KB.又稱為純代碼，允許多個進程同時訪問1/14/2024122分頁與分段共享比較:進程1進程2ed1ed40d1d10頁表頁表216061707180216021601/14/20241234.5.4段頁式存儲管理方式1.根本原理段號(S)段內(nèi)頁號(P)頁內(nèi)地址(W)地址結構1/14/2024124根本思想：用戶程序劃分：按段式劃分〔對用戶來講，按段的邏輯關系進行劃分；對系統(tǒng)講，按頁劃分每一段〕邏輯地址：內(nèi)存劃分：按頁式存儲管理方案內(nèi)存分配：以頁為單位進行分配段號段內(nèi)地址頁號頁內(nèi)地址1/14/20241251.段表：記錄了每一段的頁表始址和頁表長度2.頁表：記錄了邏輯頁號與內(nèi)存塊號的對應關系〔每一段有一個，一個程序可能有多個頁表〕3.分配：同頁式管理返回1/14/20241264.6虛擬存儲器的根本概念P141前面的存儲器管理方式存在以下情況：〔1〕有的作業(yè)很大，不能被全部裝入內(nèi)存〔2〕有大量作業(yè)要求運行，但由于內(nèi)存容量缺乏以容納所有這些作業(yè)，只能將少數(shù)作業(yè)裝入內(nèi)存讓它們先運行，而將其它大量的作業(yè)留在外存上等待。概述1/14/2024127解決方法：〔1〕從物理上增加內(nèi)存容量〔2〕從邏輯上擴充內(nèi)存容量1/14/2024128本節(jié)主要內(nèi)容：4.6.1虛擬存儲器的引入4.6.2虛擬存儲器的實現(xiàn)方法4.6.3虛擬存儲器的特征本節(jié)學習目標：理解并熟練掌握虛擬存儲器的概念；理解程序執(zhí)行的局部性原理；熟練掌握存儲器的特征；返回1/14/2024129虛擬存儲器的引入P1421.常規(guī)存儲器管理方式的特征(1)一次性.(2)駐留性1/14/20241302.局部性原理〔1〕程序在執(zhí)行時，除了少局部的轉(zhuǎn)移和過程調(diào)用指令外，在大多數(shù)情況下仍是順序執(zhí)行的；〔2〕程序在一段時間內(nèi)，局限在過程的范圍內(nèi)運行?！?〕程序中存在許多循環(huán)結構，它們雖由少數(shù)指令構成，但屢次執(zhí)行。〔4〕程序中還包括許多對數(shù)據(jù)結構的處理，它們往往都局限于很小的范圍內(nèi)。1/14/2024131局限性又表現(xiàn)為：〔1〕時間局限性。如果程序中某條指令一旦執(zhí)行，那么不久以后該指令可能再次執(zhí)行?！?〕空間局限性。1/14/2024132實現(xiàn)思想：當進程運行時，先將一局部程序裝入內(nèi)存，另一局部暫時留在外存，當要執(zhí)行的指令不在內(nèi)存時，由系統(tǒng)自動完成將它們從外存調(diào)入內(nèi)存工作

3.虛擬存儲器的定義目的：提高內(nèi)存利用率虛擬存儲器〔簡稱虛存〕描述：把內(nèi)存與外存有機的結合起來使用，從而得到一個容量很大的“內(nèi)存〞，這就是虛存1/14/2024133所謂虛擬存儲器，是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲器系統(tǒng)。定義1/14/2024134虛擬存儲器的邏輯容量由內(nèi)存容量和外存容量之和決定，其運行速度接近于內(nèi)存速度，而本錢接近于外存。虛存的最大容量由計算機的地址長度決定,但不能超過內(nèi)外存容量之和。例子：設主存容量為1MB，輔助存儲器容量為400MB,計算機系統(tǒng)的地址存放器有24位，那么虛存的最大容量是________MB.答案：16MB1/14/20241354.6.2虛擬存儲器的實現(xiàn)方法P1431.分頁請求系統(tǒng)它是在分頁系統(tǒng)的根底上，增加了請求調(diào)頁功能和頁面置換功能所形成的頁式虛擬存儲系統(tǒng)。它允許只裝入假設干頁〔而非全部程序〕的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再通過調(diào)頁功能和頁面置換功能，陸續(xù)把將要運行的頁面調(diào)入內(nèi)存，同時把暫不運行的頁面置換到外存上，置換時以頁面為單位。1/14/20241361)硬件支持①請求分頁的頁表機制②缺頁中斷機構③地址變換機構2〕實現(xiàn)請求分頁的軟件主要包括實現(xiàn)請求調(diào)頁的軟件和實現(xiàn)頁面置換的軟件1/14/20241372.請求分段系統(tǒng)它是在分段系統(tǒng)的根底上，增加了請求調(diào)段和分段置換功能所形成的段式虛擬存儲系統(tǒng)。它允許只裝入假設干段〔而非全部段〕的用戶程序和數(shù)據(jù)，就可以啟動運行，以后再通過調(diào)段功能和置換功能將不運行的段調(diào)出，同時調(diào)入將要運行的段，置換以段為單位。1/14/20241381)硬件支持①請求分段的段表機制②缺段中斷機構③地址變換機構2〕實現(xiàn)請求分段的軟件主要包括實現(xiàn)請求調(diào)段的軟件和實現(xiàn)段置換的軟件1/14/20241393.請求段頁式系統(tǒng)：它是在段頁式系統(tǒng)的根底上，增加了請求調(diào)頁和頁面置換功能所形成的段頁式虛擬存儲系統(tǒng)。1/14/20241404.6.3虛擬存儲器的特征P1441、離散性2、屢次性屢次性是指一個作業(yè)被分成屢次地調(diào)入內(nèi)存運行。3、對換性對換性是指允許在作業(yè)地運行過程中換進、換出換進、換出能有效地提高內(nèi)存利用率4、虛擬性虛擬性是指能夠從邏輯上擴充內(nèi)存容量虛擬性是虛擬存儲器所表現(xiàn)出來的最重要的特征。返回1/14/20241414.7請求分頁存儲管理方式P144請求式分頁存儲管理與純分頁存儲管理在內(nèi)存塊的分配與回收、存儲保護某方面都十分相似，不同之處在于地址重定位問題。概述1/14/2024142根本工作原理:在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面；當內(nèi)存空間已滿，而又需要裝入新的頁面時，那么根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面1/14/2024143此時，系統(tǒng)必須解決以下兩個問題：〔2〕當需要把外存上的某個頁面調(diào)入內(nèi)存時，此時內(nèi)存中沒有空閑塊應怎么辦？〔1〕當程序要訪問的某頁不在內(nèi)存時，如何發(fā)現(xiàn)這種缺頁情況？發(fā)現(xiàn)后應如何處理？1/14/2024144本節(jié)主要內(nèi)容：4.7.1請求分頁中的硬件支持4.7.2內(nèi)存分配策略和分配算法4.7.3調(diào)頁策略本節(jié)學習目標：掌握請求分頁中的硬件支持；了解內(nèi)存分配策略和分配算法；掌握調(diào)頁策略返回1/14/20241451.頁表機制在請求分頁系統(tǒng)中所需要的主要數(shù)據(jù)結構，仍然是頁表。其根本作用是將用戶地址空間中的邏輯地址變換為內(nèi)存空間的物理地址。4.7.1請求分頁中的硬件支持頁號物理塊號狀態(tài)位P訪問字段A修改位M外存地址頁表用于指示該頁是否已調(diào)入內(nèi)存用于記錄本頁在一段時間內(nèi)被訪問的次數(shù)，或最近已有多長時間未被訪問表示該頁在調(diào)入內(nèi)存后是否被修改正用于指出該頁在外存上的地址1/14/2024146在地址映射過程中，在頁表中發(fā)現(xiàn)所要訪問的頁不在內(nèi)存，那么產(chǎn)生缺頁中斷。操作系統(tǒng)接到此中斷信號后，就調(diào)出缺頁中斷處理程序，根據(jù)頁表中給出的外存地址，將該頁調(diào)入內(nèi)存，使作業(yè)繼續(xù)運行下去如果內(nèi)存中有空閑塊，那么分配一頁，將新調(diào)入頁裝入內(nèi)存，并修改頁表中相應頁表工程的駐留位及相應的內(nèi)存塊號假設此時內(nèi)存中沒有空閑塊，那么要淘汰某頁，假設該頁在內(nèi)存期間被修改正，那么要將其寫回外存2.缺頁中斷機構1/14/2024147缺頁中斷與一般中斷的區(qū)別：〔1〕在指令執(zhí)行期間產(chǎn)生和處理中斷信號?！?〕一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。123456B:A:CopyAToB涉及6次缺頁中斷的指令1/14/2024148

缺頁中斷處理是

否

否

是

是

否產(chǎn)生缺頁中否

是

斷請求調(diào)頁是開始〔程序請求訪問一頁)越界中斷CPU檢索快表頁表項是否在快表中？訪問頁表頁是否在內(nèi)存中？修改快表修改訪問位和修改位形成物理地址

地址變換結束保存CPU現(xiàn)場從外存中找到缺頁

頁號>頁表長度？

內(nèi)存滿否？選擇一頁換出

該頁是否被修改？

將該頁寫回外存

將一頁從外存換入內(nèi)存

修改頁表

CPU從外存讀缺頁

啟動I/O硬件

地址變換機構1/14/2024149在為進程分配物理塊時，涉及到三個問題：4.7.2內(nèi)存分配策略和分配算法〔3〕物理塊的分配算法〔2〕物理塊的分配策略〔1〕為保證進程正常運行所需的最少物理塊數(shù)確實定；1/14/20241501.最小物理塊最小物理塊是指能保證進程正常運行所需的最少物理塊數(shù)。假設系統(tǒng)為某進程所分配的物理塊數(shù)少于此值時，進程將無法運行，這取決于指令的格式、功能和尋址方式。1/14/20241512、物理塊的分配和置換策略兩種分配策略：固定和可變兩種置換策略：全局置換和局部置換三種組合：固定+局部可變+全局可變+局部1/14/2024152三種組合：1)固定分配局部置換困難在于：應為每個進程分配多少個頁面的內(nèi)存。假設太少，會頻繁地出現(xiàn)缺頁中斷，降低了系統(tǒng)的吞吐量；假設太多，必然使內(nèi)存中駐留的進程數(shù)目減少，造成資源空閑。

2)可變分配全局置換這是最易于實現(xiàn)的一種分配和置換策略。3)可變分配局部置換1/14/20241533.物理塊分配算法1)平均分配算法2)按比例分配算法3)考慮優(yōu)先權的分配算法1/14/20241544.7.3頁面調(diào)入策略1.何時調(diào)入頁面(1)預調(diào)入策略

(2)請求調(diào)頁策略2.從何處調(diào)入頁面〔1〕從對換區(qū)調(diào)入〔系統(tǒng)擁有足夠的對換空間〕〔2〕從文件區(qū)調(diào)入〔文件不會被修改〕〔3〕UNIX方式1/14/20241553.頁面調(diào)入過程假設缺頁,向CPU發(fā)缺頁中斷CPU調(diào)用缺頁中斷處理程序中斷處理程序調(diào)頁假設頁未被修改,不必回寫假設頁已被修改,必須回寫假設內(nèi)存已滿,置換返回1/14/20241564.8頁面置換算法P149概述通常，把選擇換出的算法稱為頁面置換算法。頁面置換算法影響著系統(tǒng)的性能：盡量減少系統(tǒng)的抖動1/14/2024157最正確置換算法和先進先出置換算法4.8.2最近最久未使用(LRU)置換算法4.8.3Clock置換算法4.8.4其他置換算法1.最少使用(LFU)置換算法2.頁面緩沖算法本節(jié)主要內(nèi)容：1/14/2024158本節(jié)學習目標：理解并熟練掌握FIFO、LRU置換算法的思想和算法的應用，會求缺頁次數(shù)和置換次數(shù)；掌握CLOCK置換算法的根本思想；了解其它置換算法1/14/2024159最理想的頁面置換算法是：從內(nèi)存中移出以后不再使用的頁面；如無這樣的頁面，那么選擇以后最長時間內(nèi)不需要訪問的頁。這就是最正確算法的思想。1.最正確置換算法〔Optimal算法〕最正確置換算法和先進先出置換算法1/14/2024160這種算法本身不是一種實際的方法，因為頁面訪問的順序是很難預知的。但是，可把它作為一種評價標準，比較其他實用方法的優(yōu)劣，所以，最優(yōu)算法只具有理論上的意義。1/14/2024161假設系統(tǒng)為某進程分配了3個物理塊，頁面引用序列如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1進程運行時三個物理塊都是空閑的。例子：求:缺頁次數(shù)、缺頁率及置換次數(shù)1/14/2024162最正確〔Optimal〕置換算法發(fā)生了6次面置換，9次缺頁中斷,。9/20=45%1/14/20241632.先進先出(FIFO)頁面置換算法這種算法的根本思想是：總是先淘汰那些駐留在內(nèi)存時間最長的頁面，即先進入內(nèi)存的頁面先被置換掉。理由是：最先進入內(nèi)存的頁面不再被訪問的可能性最大。程序執(zhí)行的局部性原理1/14/2024164FIFO算法演示過程〔m=3〕1234125123451約定：每一輪訪存進行排序，將要置換的頁放在下面222113334441112255√√√√√√√21215334455523√√12341/14/2024165主存塊數(shù)m=3，置換算法采用FIFO算法，缺頁中斷次數(shù)及缺頁率如下圖。在圖中，P行表示頁面走向，M行表示在主存中的頁面號，其中帶有+的表示新調(diào)入頁面，在M行的各列按調(diào)入的順序排列，帶有圓圈的數(shù)字表示下一時刻將被淘汰頁面，F(xiàn)行表示是否引起缺頁中斷，帶√號的表示引起缺頁中斷?！纠?】1/14/2024166FIFO算法性能分析〔m=3〕從圖可以看出，缺頁中斷頁數(shù)為9次，缺頁率f=9/12=75%。1/14/2024167設m=4，仍采用FIFO算法，缺頁中斷次數(shù)及缺頁率如以下圖所示?？梢运愠?，在分配給該作業(yè)的內(nèi)存塊數(shù)增加到4時，缺頁中斷由上圖的9次反而增加到了10次，缺頁率由75%增加到10/12=83%，這就是FIFO算法的一種異?，F(xiàn)象。隨著分配的主存塊數(shù)的增加，缺頁中斷次數(shù)不但沒有降低，反而增加了。這與該算法定全不考慮程序的動態(tài)特征有關?！纠?】1/14/2024168圖為FIFO算法性能分析〔m=4〕1/14/20241694.8.2最近最久未使用(LRU)置換算法這種算法的根本思想是:如果某一頁被訪問了，那么它很可能馬上又被訪問；反之，如果某一頁很長時間沒有被訪問，那么最近也不太可能會被訪問。這種算法考慮了程序設計的局部性原理。其實質(zhì)是，當需要置換一頁時，選擇在最近一段時間最久未使用的頁面予以淘汰。實現(xiàn)這種算法可通過周期性地對“訪問位〞進行檢查，并利用它來記錄一頁面自上次被訪問以來所經(jīng)歷的時間t，淘汰時選擇t最大的頁面。1.LRU置換算法的描述1/14/2024170LRU算法演示過程〔m=3〕約定：每一輪訪存進行排序，將要置換的頁放在下面123412512345122133441112255√√√√√√√212153344523√√123412√121/14/2024171【例3】設m=3，采用LRU算法，缺頁中斷次數(shù)及缺頁率如下圖。缺頁次數(shù)：置換次數(shù)：1071/14/2024172【例4】設m=4，其余同例3，那么缺頁中斷次數(shù)及缺頁率如下圖。缺頁次數(shù)：8置換次數(shù)：41/14/20241732.LRU置換算法的硬件支持1)存放器R=Rn-1…R1R0說明:系統(tǒng)為每個在內(nèi)存中的頁面配置一個移位存放器,當進程訪問某物理塊時,將相應存放器的Rn-1位置成1.2)棧根本思想：每當進程訪問某頁時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。1/14/20241744.8.3Clock置換算法P1531.簡單的Clock置換算法(最近未用算法NRU)思想:為每頁設置一訪問位,將內(nèi)存中的所有頁面鏈成一個循環(huán)隊列.當某頁被訪問時,訪問位置1.每次選擇訪問位是0的置換出.1/14/20241752