交通923927操作系統(tǒng)電子課件zgsosjiaoan

125四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽主講教師：翟高壽（副教授）聯(lián)系電話：(辦)電子郵件：制作人：翟高壽制作單位：北京交通大學(xué)計(jì)算機(jī)學(xué)院《操作系統(tǒng)》225四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.6

請求分頁存儲管理方式4.6.1請求分頁中的硬件支持4.6.2內(nèi)存分配策略和分配算法4.6.3調(diào)頁策略4.6.4頁面置換算法325四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.6.4

頁面置換算法4.6.4.1抖動與缺頁率4.6.4.2最佳置換算法4.6.4.3先進(jìn)先出置換算法4.6.4.4最近最久未使用置換算法4.6.4.5Clock置換算法4.6.4.6最少使用置換算法4.6.4.7頁面緩沖算法425四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽抖動與缺頁率抖動的定義如果所用置換算法不當(dāng)，便可能導(dǎo)致這樣一種情形：剛被換出的頁面很快又被訪問，需重新調(diào)入，為此，又需再選一頁換出；而此剛被換出的頁面，不久也被訪問，故又需將它調(diào)入，如此頻繁地更換頁面，以致一個(gè)進(jìn)程在運(yùn)行中把大部分的時(shí)間耗費(fèi)在頁面置換的工作上，稱該進(jìn)程發(fā)生了抖動（或稱之為顛簸）缺頁率缺頁率=缺頁中斷次數(shù)/頁面訪問次數(shù)525四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.6.4

頁面置換算法4.6.4.1抖動與缺頁率4.6.4.2最佳置換算法4.6.4.3先進(jìn)先出置換算法4.6.4.4最近最久未使用置換算法4.6.4.5Clock置換算法4.6.4.6最少使用置換算法4.6.4.7頁面緩沖算法625四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽最佳置換算法基本思想選擇永不使用或是在最長時(shí)間內(nèi)不再被訪問（即距現(xiàn)在最長時(shí)間才會被訪問）的頁面淘汰出內(nèi)存評價(jià)理想化算法，具有最好性能（對于固定分配頁面方式，本法可保證獲得最低的缺頁率），但實(shí)際上卻難于實(shí)現(xiàn)，故主要用于算法評價(jià)參照725四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽最佳置換算法舉例說明70120304230321201701777222222222222227770000004440000000000111333333331111111某進(jìn)程分配獲得三個(gè)物理塊缺頁中斷次數(shù)為6次，缺頁率30%頁面訪問序列內(nèi)存頁面分布情況頁面預(yù)先裝入825四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.6.4

頁面置換算法4.6.4.1抖動與缺頁率4.6.4.2最佳置換算法4.6.4.3先進(jìn)先出置換算法4.6.4.4最近最久未使用置換算法4.6.4.5Clock置換算法4.6.4.6最少使用置換算法4.6.4.7頁面緩沖算法925四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽先進(jìn)先出置換算法基本思想選擇最先進(jìn)入內(nèi)存即在內(nèi)存駐留時(shí)間最久的頁面換出到外存進(jìn)程已調(diào)入內(nèi)存的頁面按進(jìn)入先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置替換指針以指向最老頁面評價(jià)簡單直觀，但不符合進(jìn)程實(shí)際運(yùn)行規(guī)律，性能較差，故實(shí)際應(yīng)用極少1025四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽70120304230321201701777222244400000007770000333222221111100111100033333222221某進(jìn)程分配獲得三個(gè)物理塊缺頁中斷次數(shù)為12次，缺頁率60%頁面訪問序列內(nèi)存頁面分布情況頁面預(yù)先裝入先進(jìn)先出置換算法舉例說明1125四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.6.4

頁面置換算法4.6.4.1抖動與缺頁率4.6.4.2最佳置換算法4.6.4.3先進(jìn)先出置換算法4.6.4.4最近最久未使用置換算法4.6.4.5Clock置換算法4.6.4.6最少使用置換算法4.6.4.7頁面緩沖算法1225四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽最近最久未使用置換算法LRU基本思想以“最近的過去”作為“最近的將來”的近似，選擇最近一段時(shí)間最長時(shí)間未被訪問的頁面淘汰出內(nèi)存評價(jià)適用于各種類型的程序，性能較好，但需要較多的硬件支持1325四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽70120304230321201701777222244400011111110000000033333300000111333222222222777某進(jìn)程分配獲得三個(gè)物理塊缺頁中斷次數(shù)為9次，缺頁率45%頁面訪問序列內(nèi)存頁面分布情況頁面預(yù)先裝入最近最久未使用置換算法舉例說明1425四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽最近最久未使用置換算法硬件支持—移位寄存器B#RR7R6R5R4R3R2R1R01010100102101011003000011004011010115110101106001010117000001118011011011525四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽最近最久未使用置換算法硬件支持—棧4474707407047170410174010741210742120741210742621076某進(jìn)程分配獲得五個(gè)物理塊頁面訪問序列1625四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.6.4

頁面置換算法4.6.4.1抖動與缺頁率4.6.4.2最佳置換算法4.6.4.3先進(jìn)先出置換算法4.6.4.4最近最久未使用置換算法4.6.4.5Clock置換算法4.6.4.6最少使用置換算法4.6.4.7頁面緩沖算法1725四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽簡單Clock置換算法塊號頁號頁面訪問位指針0124034215650711查尋指針入口返回查尋指針前移指向下一表目選擇該頁淘汰頁面訪問位=0？置頁面訪問位為0是否1825四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽改進(jìn)型Clock置換算法基本思想①從查尋指針當(dāng)前位置起掃描內(nèi)存分頁循環(huán)隊(duì)列，選擇A=0且M=0的第一個(gè)頁面淘汰；若未找到，轉(zhuǎn)②②開始第二輪掃描，選擇A=0且M=1的第一個(gè)頁面淘汰，同時(shí)將經(jīng)過的所有頁面訪問位置0；若不能找到，轉(zhuǎn)①評價(jià)與簡單Clock算法相比，可減少磁盤的I/O操作次數(shù)，但淘汰頁的選擇可能經(jīng)歷多次掃描，故實(shí)現(xiàn)算法自身的開銷增大1925四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.6.4

頁面置換算法4.6.4.1抖動與缺頁率4.6.4.2最佳置換算法4.6.4.3先進(jìn)先出置換算法4.6.4.4最近最久未使用置換算法4.6.4.5Clock置換算法4.6.4.6最少使用置換算法4.6.4.7頁面緩沖算法2025四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽最少使用置換算法LFU基本思想為內(nèi)存各頁設(shè)置一移位寄存器用于記錄對應(yīng)被訪頻率，并選擇在最近時(shí)期使用次數(shù)最少的頁面淘汰評價(jià)鑒于僅用移位寄存器有限各位來記錄頁面使用會導(dǎo)致訪問一次與訪問多次的等效性，本算法并不能真實(shí)全面地反映頁面使用情況2125四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.6.4

頁面置換算法4.6.4.1抖動與缺頁率4.6.4.2最佳置換算法4.6.4.3先進(jìn)先出置換算法4.6.4.4最近最久未使用置換算法4.6.4.5Clock置換算法4.6.4.6最少使用置換算法4.6.4.7頁面緩沖算法2225四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽頁面緩沖算法PBA基本思想設(shè)立空閑頁面鏈表和已修改頁面鏈表采用可變分配和基于先進(jìn)先出的局部置換策略，并規(guī)定被淘汰頁先不做物理移動，而是依據(jù)是否修改分別掛到空閑頁面鏈表或已修改頁面鏈表的末尾空閑頁面鏈表同時(shí)用于物理塊分配當(dāng)已修改頁面鏈表達(dá)到一定長度如64個(gè)頁面時(shí)，一起將所有已修改頁面寫回磁盤，故可顯著減少磁盤I/O操作次數(shù)2325四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.6.4

頁面置換算法4.6.4.1抖動與缺頁率4.6.4.2最佳置換算法4.6.4.3先進(jìn)先出置換算法4.6.4.4最近最久未使用置換算法4.6.4.5Clock置換算法4.6.4.6最少使用置換算法4.6.4.7頁面緩沖算法2425四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.6

請求分頁存儲管理方式4.6.1請求分頁中的硬件支持4.6.2內(nèi)存分配策略和分配算法4.6.3調(diào)頁策略4.6.4頁面置換算法2525四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽第四章存儲器管理4.1程序的裝入和鏈接4.2連續(xù)分配方式4.3基本分頁存儲管理方式4.4基本分段存儲管理方式4.5虛擬存儲器概念及關(guān)鍵技術(shù)4.6請求分頁存儲管理方式4.7請求分段存儲管理方式2625四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.7

請求分段存儲管理方式4.7.1請求分段中的硬件支持4.7.2分段共享4.7.3分段保護(hù)2725四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽段表機(jī)制段表項(xiàng)的擴(kuò)充段名段長分段基址存取方式訪問字段修改位狀態(tài)位增補(bǔ)位外存地址起始盤塊號2825四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽缺段中斷機(jī)構(gòu)及處理過程缺段中斷處理內(nèi)存中有合適的空閑區(qū)？查找空閑分區(qū)(鏈)表從外存讀入所缺分段修改段表及空閑分區(qū)(鏈)表返回是否內(nèi)存空閑分區(qū)容量能否滿足？空閑分區(qū)拼接以形成一個(gè)合適的空閑區(qū)，并修改空閑分區(qū)(鏈)表是否淘汰若干實(shí)段以形成一個(gè)合適的空閑區(qū)，同時(shí)修改段表及空閑分區(qū)(鏈)表2925四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽地址變換機(jī)構(gòu)在分段系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上，增加缺段中斷產(chǎn)生和處理并分段置換功能而構(gòu)成地址變換過程要領(lǐng)從段表找到對應(yīng)分段的段表項(xiàng)獲悉該段尚未調(diào)入內(nèi)存時(shí)，應(yīng)產(chǎn)生缺段中斷，請求操作系統(tǒng)從外存把該段調(diào)入內(nèi)存關(guān)于快表和段表的檢索及表項(xiàng)修改3025四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽請求分段系統(tǒng)地址變換訪問[S][W]S<段表長度且W<分段長度？修改分段S對應(yīng)段表項(xiàng)訪問字段和修改位形成內(nèi)存物理地址(A)=(分段基址)+(W)返回是否分段越界中斷處理存取方式合法？是否分段保護(hù)中斷處理分段S在內(nèi)存？是否請求缺段中斷處理3125四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽4.7

請求分段存儲管理方式4.7.1請求分段中的硬件支持4.7.2分段共享4.7.3分段保護(hù)3225四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽共享段表共享進(jìn)程計(jì)數(shù)存取控制字段共享段不同段號…共享段表項(xiàng)i…段名段長分段基址狀態(tài)位外存地址狀態(tài)進(jìn)程名進(jìn)程號段號存取控制字段……………共享進(jìn)程計(jì)數(shù)count分段共享進(jìn)程描述共享段表3325四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽共享段的分配與回收共享段的分配對于第一個(gè)請求使用某共享段的進(jìn)程，由系統(tǒng)為該共享段進(jìn)行內(nèi)存區(qū)的分配和裝入，同時(shí)把共享段信息填入對應(yīng)進(jìn)程段表中，并在共享段表中為之增加一個(gè)表項(xiàng)和填寫相關(guān)內(nèi)容；對于以后其它進(jìn)程提出共享該段要求，則僅需對對應(yīng)的進(jìn)程段表表項(xiàng)及共享段表表項(xiàng)修正即可共享段的回收與共享段分配過程恰好相逆3425四月2023北京交通大學(xué)計(jì)算機(jī)學(xué)院翟高壽