【正文】 序?qū)?huì)被局限于這些過(guò)程的范圍內(nèi)運(yùn)行。 11 基于局部性原理，作業(yè)沒(méi)有必要全部裝基于局部性原理，作業(yè)沒(méi)有必要全部裝入內(nèi)存。 15硬件支持： (1) 請(qǐng)求分頁(yè) 的頁(yè)表機(jī)制。 (3) 地址變換機(jī)構(gòu)。25請(qǐng)求分頁(yè)系統(tǒng)中，頁(yè)表項(xiàng)如下：請(qǐng)求分頁(yè)系統(tǒng)中，頁(yè)表項(xiàng)如下： 頁(yè)號(hào) 物理塊號(hào) 狀態(tài)位 P訪問(wèn)字段 A 修改位 M外存地址(1)狀態(tài)位 （駐留位） P:該頁(yè)是在內(nèi)存還是在外存(2)訪問(wèn)字段位 A：記錄本頁(yè)在一段時(shí)間內(nèi)被訪問(wèn)的次數(shù) 。216。此時(shí)，由系統(tǒng)調(diào)度另一作業(yè)運(yùn)行。如果進(jìn)程在運(yùn)行其間頻繁發(fā)生缺頁(yè)中斷 ,則系統(tǒng) 再為該進(jìn)程分配若干個(gè)附加物理塊 ,直至進(jìn)程的缺頁(yè)率減少到合適為止 。文件區(qū)對(duì)換區(qū)第一次 內(nèi)存外存44外存物理塊號(hào)內(nèi)存有空：調(diào)入內(nèi)存不空：換出一頁(yè)修改位為 1，重新寫入外存修改位為 0，不必寫入外存將缺頁(yè)調(diào)入內(nèi)存修改頁(yè)表，寫入快表 物理地址 訪問(wèn)數(shù)據(jù)頁(yè)面調(diào)入過(guò)程 45 頁(yè)面置換算法頁(yè)面置換算法 算法算法 置換算法置換算法46 頁(yè)面置換算法頁(yè)面置換算法 假定作業(yè) p共計(jì) n頁(yè) ，而系統(tǒng)分配給它的主存塊只有 m塊 （ m,n均為正整數(shù)，１ ≤ m≤ n），即最多只能容納 m頁(yè)。（ OPT算法 ）。55 我們來(lái)看看采用 FIFO算法進(jìn)行頁(yè)面置換時(shí)的情況。 0 1 2 4 6 3 4 2 ^ 5 6 5 7 7 1 4塊號(hào) 頁(yè)號(hào) 指針2替換指針 0 1 2 6 ^ 3 4 2 2 5 6 5 7 7 1 4塊號(hào) 頁(yè)號(hào) 指針6替換指針(a) 替換之前 (b) 替換之后58 FIFO是根據(jù)各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間來(lái)選擇被淘汰頁(yè)面，但 頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情況 。 63寄存器 為每個(gè)在內(nèi)存中的頁(yè)面配置一個(gè) 移位寄存器，表示為： R=Rn1Rn2Rn3…R 1R2R0 當(dāng)進(jìn)程訪問(wèn)某物理塊時(shí)，要將相應(yīng)的寄存器的Rn1位置為 1。 68簡(jiǎn)單的、簡(jiǎn)單的 CLock置換算法置換算法 這種算法的實(shí)質(zhì)是：當(dāng)需要置換一頁(yè)時(shí)，選擇在最近一段時(shí)間內(nèi) 最久未用 的頁(yè)予以淘汰，因此稱為 最近未用 的算法 NRU（Not Recently Used）。 2類 （ A=0， M=1），最近未被訪問(wèn)，但已被修改，不是很好的淘汰頁(yè)。75 其它置換算法其它置換算法最少使用（ Least Frequently Used）置換算法（ LFU ）既可實(shí)現(xiàn)LRU，也可實(shí)現(xiàn) LFU 為內(nèi)存中的每個(gè)頁(yè)面設(shè)置一個(gè)移位寄存器，用來(lái)記錄頁(yè)面被訪問(wèn)的頻率，淘汰頁(yè)是最少使用或是訪問(wèn)次數(shù)最少的頁(yè)面。79 那么為了提高 CPU的利用率，調(diào)度程序又去引入新的進(jìn)程，這就產(chǎn)生了惡性循環(huán)，使缺頁(yè)率急劇地上升。頁(yè)面淘汰算法不合理216。用 Nw(t, △ ) 表示工作集中所包含的頁(yè)面數(shù)。通過(guò)工作集來(lái)管理主存的分配和使用，從理論上來(lái)說(shuō)是一件非常好的事情，但工作集算法的實(shí)現(xiàn)有很多困難，目前仍然在研究和試驗(yàn)中。但是從保證作業(yè)順利執(zhí)行、使 CPU能夠有效地得到利用的角度出發(fā)，就應(yīng)該限制主存中的作業(yè)數(shù)，以避免頻繁地進(jìn)行頁(yè)面調(diào)入 /調(diào)出，導(dǎo)致系統(tǒng)的抖動(dòng)。 80CPU利用率多道程序度從圖中可看出 CPU的利用率和多道程序度 之間的關(guān)系。76頁(yè)面緩沖算法（ Page Buffering Algorithm） PBA 淘汰頁(yè)面未修改修改過(guò)空閑頁(yè)面鏈表末尾已修改頁(yè)面的鏈表中末尾采用可變分配和局部置換方式，采用 FIFO置換算法 實(shí)際上 ,頁(yè)面在內(nèi)存中并不做物理上的移動(dòng) ,只是將頁(yè)表中的表項(xiàng)移到上述鏈表 。 既要考慮到頁(yè)面的使用情況，還要考慮置換代價(jià) 4類 （ A=1， M=1），最近已被訪問(wèn)且被修改，可能再被訪問(wèn)。 當(dāng)某頁(yè)被訪問(wèn)時(shí)，訪問(wèn)位由硬件自動(dòng)置 “1”。用于記錄某進(jìn)程在內(nèi)存中各頁(yè)的使用情況。 未考慮到程序的 動(dòng)態(tài)特性 。缺頁(yè)率 15/21=3/4， 15次頁(yè)面中斷。 抖動(dòng)52 最佳置換算法是由 Relady在 1966年提出的，這種算法選擇的被淘汰頁(yè)面，將是 永不使用的，或在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。缺頁(yè)中斷率 :47影響缺頁(yè)中斷次數(shù)的因素影響缺頁(yè)中斷次數(shù)的因素（ 1） 分配給進(jìn)程的物理頁(yè)面數(shù)物理頁(yè)面數(shù)多，缺頁(yè)中斷少，反之，則缺頁(yè)中斷多物理頁(yè)面數(shù)多，進(jìn)程數(shù)少（影響系統(tǒng)效率），反之，則進(jìn)程數(shù)多（缺頁(yè)中斷多）根據(jù)試驗(yàn)分析：對(duì)一共有 n頁(yè)的進(jìn)程來(lái)說(shuō)，只要能分到n/2塊 內(nèi)存空間，就可使系統(tǒng)獲得最高效率；（ 2） 頁(yè)面本身的大小頁(yè)面大，進(jìn)程的頁(yè)數(shù)少，一頁(yè)的信息就大，缺頁(yè)中斷次數(shù)減少；不同的計(jì)算機(jī)系統(tǒng)，有不同頁(yè)面大??；48例：程序要把例：程序要把 128128的數(shù)組初值置的數(shù)組初值置 “0”，數(shù)組中，數(shù)組中每一個(gè)元素為一個(gè)字，假定頁(yè)面大小為每一個(gè)元素為一個(gè)字，假定頁(yè)面大小為 128個(gè)字，個(gè)字，數(shù)組中的每一行元素存放一頁(yè)，能供該程序使用數(shù)組中的每一行元素存放一頁(yè)，能供該程序使用的主存塊只有的主存塊只有 1塊。 3)、考慮優(yōu)先權(quán)的分配算法 2)、按比例分配算法 ， Si為某個(gè)進(jìn)程的頁(yè)面數(shù)。 33 內(nèi)存內(nèi)存 分配策略和分配算法分配策略和分配算法 在為進(jìn)程分配物理塊時(shí)，又要解決三個(gè)問(wèn)題： 保證進(jìn)程正常運(yùn)行而需要的 最少物理塊數(shù) ；進(jìn)行分配時(shí)，物理塊數(shù)目是 固定的還是可變的；（分配策略）是采取 平均分配算法 還是根據(jù)進(jìn)程的大小 按比例分配物理塊 。不在內(nèi)存，則產(chǎn)生 缺頁(yè)中斷 。頁(yè)號(hào) 物理塊號(hào) 保護(hù)信息外頁(yè)面表 當(dāng)一個(gè)作業(yè)被調(diào)度到而裝入內(nèi)存時(shí)，系統(tǒng)為它在內(nèi)存建立一張頁(yè)表。 18 虛擬存儲(chǔ)器的特征虛擬存儲(chǔ)器的特征