4.7請求分頁存儲管理方式二.內(nèi)存分配策略和分配算法1.最小物理塊數(shù)的確定保證進(jìn)程正常運行所需的最少物理塊數(shù)；與硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。2.物理塊的分配和置換策略分配策略：固定分配、動態(tài)分配置換策略：局部置換、全局置換（1）固定分配局部置換

（2）可變分配全局置換

（3）可變分配局部置換

二.內(nèi)存分配策略和分配算法3.物理塊的分配算法平均分配算法將空閑物理塊，平均分配給各個進(jìn)程。按比例分配算法根據(jù)進(jìn)程的大小按比例分配物理塊的。考慮優(yōu)先權(quán)的分配算法優(yōu)先權(quán)高的一次分得的物理塊數(shù)多。三.調(diào)頁策略1.調(diào)入頁面的時機(jī)預(yù)調(diào)頁策略：一次調(diào)入若干相鄰的頁；

用于進(jìn)程首次調(diào)入內(nèi)存時請求調(diào)頁策略：運行中發(fā)生缺頁時，只調(diào)入所缺的那一頁2.從何處調(diào)入頁面的問題系統(tǒng)擁有足夠的對換區(qū)空間： 全部從對換區(qū)換入系統(tǒng)缺少足夠的對換區(qū)空間：沒運行過的頁面、運行過但沒被修改過的頁面：文件區(qū)被修改過之后，再被換出的頁面：對換區(qū)UNIX方式：未運行過的頁面：文件區(qū)運行后被換出的頁面：對換區(qū)3.頁面的調(diào)入過程進(jìn)程運行時，由地址變換機(jī)構(gòu)向CPU發(fā)出缺頁中斷信號；CPU響應(yīng)中斷：保存進(jìn)程的CPU現(xiàn)場，轉(zhuǎn)中斷處理程序；中斷處理程序查找頁表，得到該頁在外存中的塊號；若內(nèi)存未滿，則啟動磁盤I/O讀入缺頁；若內(nèi)存已滿，先置換，再調(diào)入；最后修改頁表對應(yīng)項的內(nèi)容。中斷返回后，被中斷進(jìn)程產(chǎn)生缺頁的那條指令將被重新執(zhí)行三.調(diào)頁策略4.8頁面置換算法要調(diào)入缺頁時，若內(nèi)存中已沒有空閑塊，則必須根據(jù)一定的策略從內(nèi)存中選擇一個頁面換出到外存。選擇換出頁面的算法稱為頁面置換算法。最佳置換算法（OPT）先進(jìn)先出（FIFO）最近最久未使用置換算法（LRU）Clock置換算法（NRU）最少使用置換算法（LFU）頁面緩沖置換算法（PBA）4.8頁面置換算法一、最佳置換算法（OPT）選擇以后永遠(yuǎn)不會被使用的頁面或?qū)碜铋L時間內(nèi)不會被訪問的頁面淘汰出去。例：在一個請求分頁系統(tǒng)中，假定系統(tǒng)分給一個作業(yè)的物理塊數(shù)為3，并且此作業(yè)的頁面走向為2，3，2，1，5，2，4，5，3，2，5，2。用OPT計算缺頁次數(shù)和缺頁率。分析：如果所訪問的頁還沒有裝入內(nèi)存，便將發(fā)生一次缺頁中斷。訪問過程中發(fā)生缺頁中斷的次數(shù)就是缺頁次數(shù)。缺頁次數(shù)除以總的訪問次數(shù)，就是缺頁率。缺頁中斷m3m2×532×532√532×534×534√534×532√532√132×32√32√2m1252354251232頁面走向使用OPT算法：缺頁次數(shù)：6，置換次數(shù)：3次，缺頁率：6/12=50%4.8頁面置換算法一、最佳置換算法（OPT）特點：理論上，性能最佳；實際上，無法實現(xiàn)；通常用該算法來評價其他算法的優(yōu)劣。4.8頁面置換算法二、先進(jìn)先出頁面置換算法（FIFO）選擇最先進(jìn)入內(nèi)存，即駐留內(nèi)存時間最長的頁予以淘汰。例：在一個請求分頁系統(tǒng)中，假定系統(tǒng)分給一個作業(yè)的物理塊數(shù)為3，并且此作業(yè)的頁面走向為2，3，2，1，5，2，4，5，3，2，5，2。用FIFO計算缺頁次數(shù)和缺頁率。缺頁中斷m3m2√253√453×423√423×425√425√125√135√132×32√32√2m1252354251232頁面走向使用FIFO算法:缺頁：9次，置換：6次，缺頁率：(9/12)*100%=75%4.8頁面置換算法二、先進(jìn)先出頁面置換算法（FIFO）特點：實現(xiàn)簡單；與進(jìn)程實際的運行規(guī)律不相適應(yīng)。例：在一個請求分頁系統(tǒng)中，假如一個作業(yè)的頁面走向為1，2，3，4，1，2，5，1，2，3，4，5,當(dāng)分給該作業(yè)的物理塊數(shù)M分別為3和4時，請用FIFO計算缺頁次數(shù)和缺頁率，并比較所得的結(jié)果。缺頁中斷最后進(jìn)入↓435√435√352521521√521√214√143√432√321√21√1最先進(jìn)入543215214321頁面走向使用FIFO算法——物理塊數(shù)為3:缺頁次數(shù)：9，置換次數(shù)：6，缺頁率：9/12最后進(jìn)入使用FIFO算法——物理塊數(shù)為4:缺頁次數(shù)：10，置換次數(shù)：6次，缺頁率：10/12內(nèi)存塊↑，缺頁次數(shù)反而有可能↑——Belady現(xiàn)象。缺頁中斷√5432√4321√3215√2154√1543√543243214321√4321√321√21√1最先進(jìn)入543215214321頁面走向4.8頁面置換算法三、最近最久未使用置換算法（LRU）

1.概念:選擇在最近一段時間內(nèi)最長時間未被使用（訪問）的頁面淘汰出去。缺頁中斷最近使用↓253523√235√354542√425251√512√12323√32√2最久未用252354251232頁面走向使用LRU算法：缺頁次數(shù)：7，缺頁率：7/12（1）移位寄存器

對正在執(zhí)行的進(jìn)程，為它每個在內(nèi)存中的頁面配置一個移位寄存器R：當(dāng)進(jìn)程訪問一物理塊時，將其對應(yīng)寄存器的最高位置1；每隔一定時間將所有移位寄存器右移一位，高位填0；值最小的寄存器所對應(yīng)的頁面就是最近最久未使用的頁面。2.LRU置換算法的硬件支持：101101108111000007110101006011010115110101104001000003001101012010010101R0R1R2R3R4R5R6R7R實頁LRU置換算法的硬件支持：（2）棧

利用一個特殊的棧來保存當(dāng)前使用的各個頁面的頁面號。當(dāng)進(jìn)程訪問此頁面時，將該頁面的頁面號從棧中移出，壓入棧頂。因此棧頂是最新被訪問頁面的編號，棧底是最近最久未使用頁面的頁面號。2.LRU置換算法的硬件支持：3.LRU置換算法的軟件實現(xiàn)：

每個頁面設(shè)置一個年齡字段，每隔一定的時間將該字段加1，訪問某個頁時將該字段清0。選擇年齡最大的頁面換出。

4.8頁面置換算法三、最近最久未使用置換算法（LRU）特點：性能較好實現(xiàn)復(fù)雜：軟件實現(xiàn)費時；硬件實現(xiàn)，增加系統(tǒng)成本。時間局部性原理四、Clock置換算法

（1）簡單的clock置換算法：每頁設(shè)置一位訪問位。當(dāng)某頁被訪問了，則訪問位置“1”。內(nèi)存中的所有頁鏈接成一個循環(huán)隊列；置換算法：循環(huán)檢查各頁面的使用情況。若訪問位為“0”，選擇該頁淘汰；若訪問位為“1”，復(fù)位訪問位為“0”，查詢指針前進(jìn)一步。又稱為“最近未使用”置換算法（NRU）4.8頁面置換算法四、Clock置換算法（2）改進(jìn)型Clock置換算法訪問位A、修改位M頁面的四種狀態(tài)：A=0,M=0：最近未被訪問也未被修改A=0,M=1：最近未被訪問但已被修改A=1,M=0：最近已被訪問但未被修改A=1,M=1：最近已被訪問且被修改最佳淘汰頁第二選擇不應(yīng)淘汰的頁四、Clock置換算法（2）改進(jìn)型Clock置換算法選擇淘汰頁的過程（最多可能要四輪掃描）：①第一輪掃描：查找A=0,M=0頁面，找到便將此頁選作淘汰頁；若掃描一輪后還未找到，則進(jìn)入下一步；②第二輪掃描：查找A=0,M=1頁面，查找過程中需將A位復(fù)位為“0”，找到便將此頁選作淘汰頁；若掃描一輪后還未找到，則重復(fù)①，如仍然沒找到，則再重復(fù)②。4.8頁面置換算法五、最少使用置換算法（LFU）選擇在最近時期使用次數(shù)最少的頁面淘汰。（頻率）需為在內(nèi)存中的每個頁面設(shè)置一個移位寄存器，用來記錄該頁面被訪問的頻率。每次訪問某頁時，便將該移位寄存器的最高位置1，此后每隔一定時間自動右移一位，最右邊的位填充0。最近一段時間最少使用的頁面是∑Ri

最小的頁。4.8頁面置換算法101101108110000007110101006011010115110101104001000003001101012010010101R0R1R2R3R4R5R6R7R實頁×√未被修改已被修改4.8頁面置換算法六、頁面緩沖置換算法采用可變分配、局部置換策略；頁面置換算法為FIFO算法空閑頁面鏈表已修改頁面鏈表空閑內(nèi)存塊

空白內(nèi)存塊或未修改淘汰頁所在內(nèi)存塊已修改淘汰頁所在內(nèi)存塊淘汰頁置換時，分配給換入頁的內(nèi)存塊并不是淘汰頁的內(nèi)存塊。：插入空閑頁面鏈表末尾：插入已修改頁面鏈表末尾將空閑頁面鏈表鏈?zhǔn)椎膬?nèi)存塊分配給換入頁。如：VAX/VMS操作系統(tǒng)頁面緩沖算法舉例：（1）系統(tǒng)初始化完成后假設(shè)系統(tǒng)內(nèi)存有10個空閑塊，則相應(yīng)空閑內(nèi)存塊鏈表為：空閑頁面鏈表：已修改頁面鏈表：Null（2）創(chuàng)建P1進(jìn)程，分配4個塊，則分配到0,1,2,3四塊，此時空閑頁面鏈表變?yōu)椋?198765432987654頁面緩沖算法舉例：（3）P1裝入0,1,2,3四個頁面：0132013201320132M的值：100（4）P1訪問0頁、1頁、2頁，其中0頁修改，1頁、2頁不修改：（5）若P1要寫第5頁987654空閑頁面鏈表已修改頁面鏈表頁面緩沖算法舉例：按照FIFO，淘汰第0塊中的第0頁，因為該頁已修改過，所以將空閑塊0插入已修改頁面鏈表；將空閑頁面鏈表鏈?zhǔn)椎牡?塊分配給P1，裝入P1的第5頁。009876551324132M：1000進(jìn)程P1占據(jù)內(nèi)存情況：空閑頁面鏈表已修改頁面鏈表（6）若P1要讀第6頁頁面緩沖算法舉例：按照FIFO，淘汰第1塊中的第1頁，因為該頁沒修改過，所以將空閑塊1插入空閑頁面鏈表；將空閑頁面鏈表鏈?zhǔn)椎牡?塊分配給P1，裝入P1的第6頁。0062535243M：0001進(jìn)程P1占據(jù)內(nèi)存情況：空閑頁面鏈表已修改頁面鏈表（7）若P1要讀第1頁198761頁面緩沖算法舉例：按照FIFO，淘汰第2塊中的第2頁，因為該頁沒修改過，所以將空閑塊2插入空閑頁面鏈表；從空閑頁面鏈表中摘下第1塊（其中有P1的第1頁）分配給P1。0013651354M：0100進(jìn)程P1占據(jù)內(nèi)存情況：空閑頁面鏈表已修改頁面鏈表987622頁面緩沖算法舉例：（7）P1讀1頁，系統(tǒng)處理方式為：已修改頁面鏈表：空閑頁面鏈表：進(jìn)程P1占據(jù)內(nèi)存情況：9876225314531M的值：1000600一、缺頁率對有效訪問時間的影響

設(shè)缺頁率為P，則有效訪問時間為：

(1-P)*內(nèi)存訪問時間+P*缺頁中斷處理時間4.9請求分頁系統(tǒng)的性能分析缺頁中斷處理時間缺頁中斷服務(wù)時間；讀入缺頁所需時間；重新執(zhí)行訪存指令時間。例：若某請求分頁系統(tǒng)的平均缺頁中斷時間約為25ms，存儲器的平均訪問時間為100ns，設(shè)缺頁率為P，則有效訪問時間為：

（1－p）×0.1+p×25000=0.1+24999.9p

（微秒）如果希望在缺頁時，僅使有效訪問時間延長不超過10%，則可計算出缺頁率p0.1+24999.9p<0.1×(1+10%)則P＜（0.01/24999.9）=0.0000004一、缺頁率對有效訪問時間的影響：

由此可知，要求在2500000次的訪問中，才發(fā)生一次缺頁，即請求分頁式存儲管理應(yīng)保持非常低的缺頁率，否則將使程序的執(zhí)行速度受到嚴(yán)重影響。此外，提高磁盤I/O速度，對改善請求分頁系統(tǒng)的性能至關(guān)重要。為此，應(yīng)選用高速磁盤和高速磁盤接口。二、抖動的基本概念：

1.抖動的概念及產(chǎn)生的原因：全局置換策略

2.抖動的預(yù)防：

（1）采取局部置換策略；（2）引入工作集概念：工作集就是進(jìn)程在某段時間段Δ里實際要訪問的頁面的集合。具體地說，運行進(jìn)程在時間t－Δ到t這個時間段內(nèi)所訪問的頁面的集合稱為該進(jìn)程在時間t的工作集，變量Δ稱為工作集“窗口尺寸”（WindowsSize）。4.9請求分頁系統(tǒng)的性能分析二、抖動的基本概念：2.抖動的預(yù)防：（3）L=S原則：

L：進(jìn)程產(chǎn)生缺頁的平均時間；

S：系統(tǒng)進(jìn)行缺頁中斷處理的平均時間。（4）掛起若干進(jìn)程，降低多道程序度。4.9請求分頁系統(tǒng)的性能分析4.10請求分段存儲管理方式

以基本分段內(nèi)存管理為基礎(chǔ)，程序運行前，只需先調(diào)入部分分段，便啟動執(zhí)行。其它分段在需要時，通過缺段中斷處理程序臨時調(diào)入。1請求分段中的硬件支持2請求分段中的分段共享3請求分段中的分段保護(hù)4.10請求分段存儲管理方式請求分段存儲管理系統(tǒng)的示意圖：存儲空間作業(yè)空間10K0（S）=312K0（D）=28K0（X）=120K0（MAIN）=0狀態(tài)段表基址段長段號20K030K8K190K12K2150K10K3200K1101200K030K90K150K(MAIN)=020K（X）=18K（S）=310K4.10請求分段存儲管理方式一.請求分段中的硬件支持1.段表機(jī)制段名(號)段長段的基址存取方式訪問字段A修改位M存在位P增補(bǔ)位外存始址(1)存取方式：存取屬性為只執(zhí)行、只讀或允許讀/寫(2)訪問字段A：記錄該段被訪問的頻繁程度(3)修改位M：該段在進(jìn)入內(nèi)存后是否被修改過(4)存在位P：指示本段是否已調(diào)入內(nèi)存(5)增補(bǔ)位：表示本段在運行過程中，是否做過動態(tài)增長(6)外存始址：本段在外存中的起始地址，即起始盤塊號一.請求分段中的硬件支持2.缺段中斷機(jī)構(gòu)虛段S不在內(nèi)存返回阻塞請求進(jìn)程內(nèi)存中有合適的空閑區(qū)嗎？從外存讀入段S修改段表及內(nèi)存空閑區(qū)鏈喚醒請求進(jìn)程空區(qū)容量總和能否滿足？否空區(qū)拼接，以形成一個合適的空區(qū)淘汰一個或幾個實段以形成一個合適空區(qū)是否是段基址，存在位在指令執(zhí)行期間產(chǎn)生和處理中斷信號一條指令在執(zhí)行期間可能產(chǎn)生多次缺段中斷一.請求分段中的硬件支持3.地址變換機(jī)構(gòu)返回W≤段長？修改訪問位、修改位形成訪問主存地址(A)=(主存始址)+(位移量W)是符合存取方式？段S在主存？分段越界中斷處理分段保護(hù)中斷處理缺段中斷處理是是否否否訪問[S][W]S＜段表長度？分段越界中斷處理否是4.9請求分段存儲管理方式二.分段共享:

1.共享段表公用信息；私用信息共享進(jìn)程計數(shù)count：記錄要共享該段的進(jìn)程數(shù)目存取控制字段：對一共享段，給不同進(jìn)程不同權(quán)限段號：不同進(jìn)程可以調(diào)用不同段號去共享某共享段段名段長內(nèi)存始址狀態(tài)外存始址共享進(jìn)程計數(shù)count狀態(tài)進(jìn)程名進(jìn)程號段號存取控制…………二.分段共享2.共享段的內(nèi)存分配（1）共享段第一次被訪問：為共享段分配內(nèi)存，并裝入；修改進(jìn)程段表；修改共享段表：增加一個共享段表項。

（2）共享段已在內(nèi)存修改進(jìn)程段表；修改共享段表：增加一個該進(jìn)程的私有信息3.共享段的回收4.10請求分段存儲管理方式三.分段保護(hù)

1.越界檢查段表寄存器：段表始址、段表長度邏輯地址：段號；段內(nèi)地址。比較：段號—段表長度2.存取控制檢查段表項：存取控制字段（只讀、只執(zhí)行、讀/寫）段長—段內(nèi)地址4.10請求分段存儲管理方式三.分段保護(hù)3.環(huán)保護(hù)機(jī)構(gòu)低編號的環(huán)具有高優(yōu)先權(quán)。程序可以訪問駐留在相同環(huán)或較低特權(quán)環(huán)中的數(shù)據(jù)；程序可以調(diào)用駐留在相同環(huán)或較高特權(quán)環(huán)中的服務(wù)。3.環(huán)保