操作系統(tǒng)課件

第七章虛擬存儲器計算機(jī)系統(tǒng)中的另一個虛擬技術(shù)——虛存,通過交換技術(shù)將外存作為內(nèi)存的擴(kuò)充使用，解決內(nèi)存容量過小的問題。7.1虛存管理的基本概念讓程序的一部分裝入主存是否可行？一、局部性原理程序執(zhí)行過程中的一個較短時期，指令地址和操作數(shù)地址分別局限于一定區(qū)域。

7.1虛存管理的基本概念1.局部性可表現(xiàn)為A）時間局部性B）空間局部性時間局部性空間局部性步長為1步長為K的引用模式，空間局部性隨步長增加而下降7.1虛存管理的基本概念intsummatrix(inta[M][N]){inti,j,sum=0;for(j=0;j<N;j++)for(i=0;i<M;i++)sum+=a[i][j];returnsum;}按列優(yōu)先順序訪問，步長為N，空間局部性差按行優(yōu)先順序訪問，步長為1，空間局部性好7.1虛存管理的基本概念總之：（1）重復(fù)引用同一變量的程序有良好的時間局部性（2）步長越小，空間局部性越好（3）循環(huán)有良好的時間和空間局部性，循環(huán)體越小，循環(huán)迭代次數(shù)越多，局部性越好。2.局部性原理的具體體現(xiàn)（1）程序執(zhí)行的順序性（2）過程調(diào)用嵌套深度不深（3）程序中存在相當(dāng)多循環(huán)結(jié)構(gòu)（4）程序中存在相當(dāng)多對一定數(shù)據(jù)結(jié)構(gòu)的操作7.1虛存管理的基本概念二、虛擬存儲的基本原理程序運行前，不必全部裝入內(nèi)存。程序運行時，缺頁或缺段，由OS調(diào)入相應(yīng)頁和段OS將暫時不用的段和頁調(diào)出到外存上三、虛存的定義

虛存具有請求調(diào)入功能和置換功能用戶感覺有一個大容量的主存（虛擬性）7.1虛存管理的基本概念四、引入虛存技術(shù)的好處1.在小內(nèi)存中執(zhí)行較大的程序2.提供大于內(nèi)存空間的用戶空間3.內(nèi)存可容納更多程序并發(fā)執(zhí)行4.編程時，時空開銷不再成為問題五、虛存技術(shù)的特征1.離散性2.對換性3.多次性4.虛擬性六、虛存技術(shù)的種類虛擬頁式虛擬段式虛擬段頁式7.2請求分頁一、請求分頁原理1.等分主存為“塊”2.作業(yè)先存于外存文件區(qū)3.作業(yè)運行前至少裝入執(zhí)行所需的最少頁面4.作業(yè)運行時，缺頁，OS將其調(diào)入7.2請求分頁二、請求分頁中的硬件支持請求分頁系統(tǒng)比純分頁系統(tǒng)復(fù)雜，需要提供更多硬件支持1.頁表機(jī)制：需增設(shè)幾項2.缺頁中斷機(jī)構(gòu)：與普通中斷不同3.地址變換機(jī)構(gòu):增加產(chǎn)生和處理中斷功能、頁面置換功能

7.2請求分頁三、請求分頁中的地址變換過程邏輯地址（未越界）查快表有記錄形成物理地址無記錄查頁表在主存在輔存登記入快表發(fā)缺頁中斷保護(hù)現(xiàn)場有空塊？無選擇調(diào)出頁面有裝入所需頁面調(diào)整頁表并恢復(fù)現(xiàn)場硬件地址變換過程OS處理缺頁中斷過程7.2請求分頁四、調(diào)度、分配和清除策略1.調(diào)頁策略（1）何時調(diào)入頁面:請求調(diào)頁、預(yù)調(diào)頁（2）何處調(diào)入頁面：交換區(qū)、文件區(qū)（3）頁面調(diào)入過程7.2請求分頁2.物理塊的分配策略（1）固定分配，局部置換（2）可變分配，全局置換（3）可變分配，局部置換3.清除策略（1）請求清除（2）預(yù)清除7.2請求分頁五、缺頁率和抖動1.缺頁率缺頁率：缺頁中斷發(fā)生的概率缺頁率＝缺頁次數(shù)/內(nèi)存訪問次數(shù)（1）影響缺頁率的因素：

a）頁面大小b）分配給進(jìn)程的塊數(shù)7.2請求分頁2.抖動頁面在內(nèi)外存間頻繁調(diào)度的現(xiàn)象原因：1）分配給進(jìn)程的物理塊數(shù)太少2）頁面淘汰算法不合理7.3頁面置換算法一、最佳置換算法（OPT）每次置換不再訪問或最久才會訪問的頁面

具有理論價值二、先進(jìn)先出置換算法（FIFO）淘汰最先調(diào)入主存的頁面

可能出現(xiàn)Belady現(xiàn)象7.3頁面置換算法三、最近最久未使用置換算法（LRU）淘汰最近一段時間最久未訪問的頁四、輪轉(zhuǎn)置換算法（Clock）

最近未使用置換算法（NRU）簡單Clock算法改進(jìn)的Clock算法（1）頁面分為4類（2）算法：a.找第一類頁面b.找第二類頁面,并將訪問位置0c.重復(fù)查找第一、第二類頁面7.3頁面置換算法五、最少使用算法（LFU）選擇到當(dāng)前為止被訪問次數(shù)最少的頁面淘汰六、頁面緩沖算法（PBA）是FIFO算法的發(fā)展，采用預(yù)清除策略。（1）按FIFO次序，預(yù)選一個被淘汰的本進(jìn)程頁面，將頁面放入兩個鏈表之一：空閑頁面鏈表、已修改頁面鏈表。（2）調(diào)入頁面時，使用空閑頁面鏈表的頁。（3）已修改頁面鏈表中的頁達(dá)到一定數(shù)量時，一起調(diào)出到外存。7.4請求分段一、請求分段原理1.程序運行前，調(diào)入一個或若干個程序段2.運行時，缺段，則請求OS調(diào)入段二、地址變換1.段表：增加表項2.缺段中斷3.地址變換過程7.4請求分段邏輯地址（未越界）查快表有記錄形成物理地址無記錄查段表在主存在輔存登記入快表發(fā)缺段中斷保護(hù)現(xiàn)場無選擇調(diào)出若干段有裝入所需段調(diào)整段表并恢復(fù)現(xiàn)場硬件地址變換過程OS處理缺段中斷過程有空閑區(qū)？7.4請求分段三、段的保護(hù)與共享1.段的保護(hù)目的:a)保護(hù)系統(tǒng)程序區(qū)不被用戶侵犯（有意或無意）b)不允許用戶讀寫不屬于自己地址空間的數(shù)據(jù)。

7.4請求分段措施：a）越界檢查：段表寄存器段表中段長字段b）存取控制檢查：段表中的存取控制字段c）環(huán)保護(hù)：處理器狀態(tài)分為多個級別（環(huán)）可訪問同環(huán)或更低級別環(huán)的數(shù)據(jù)

可調(diào)用同環(huán)或更高級別環(huán)的服務(wù)7.4請求分段2.段的共享建立共享段表cos共享段表內(nèi)存段表7.4請求分段四、虛擬段頁式存儲將虛擬段式與虛擬頁式相結(jié)合1.原理（1）內(nèi)存分“塊”（2）地址空間分“段”，段內(nèi)分“頁”（3）作業(yè)運行前，部分投入頁面7.4請求分段2.地址變換（1）頁表：需增加若干位（同請求分頁）（2）段表：增加若干位（同請求分段？）（3）缺頁中斷（4）缺段中斷（5）地址變換過程7.4請求分段邏輯地址查快表有記錄形成物理地址無記錄查段表有頁表查頁表在內(nèi)存登記入快表無頁表發(fā)缺段中斷在外存發(fā)缺頁中斷繼續(xù)執(zhí)行指令7.5UNIX虛擬內(nèi)存管理UNIX系統(tǒng)中普遍采用請求分頁的存儲管理技術(shù)。一、請求調(diào)頁管理的數(shù)據(jù)結(jié)構(gòu)（1）頁表（2）磁盤塊描述表（3）頁框數(shù)據(jù)表（4）對換使用表7.5UNIX虛擬內(nèi)存管理1.頁表（1）頁框號：物理塊號（2）年齡：記錄頁面最近多久未被訪問（3）訪問位：記錄頁面是否被訪問過（4）修改位：記錄頁面是否被修改過（5）有效位：指示該頁是否有效，訪問無效的頁面會報錯（6）寫時拷貝：共享的頁面是否已有拷貝（7）保護(hù)位：指示頁面允許的訪問方式7.5UNIX虛擬內(nèi)存管理2.磁盤塊描述表描述頁面在外存磁盤中的位置情況（1）存儲器類型：file、disk（對換區(qū)）（2）對換設(shè)備號（3）設(shè)備塊號7.5UNIX虛擬內(nèi)存管理3.頁框數(shù)據(jù)表描述內(nèi)存物理塊的信息（1）頁狀態(tài)：指示頁面拷貝在對換設(shè)備還是文件區(qū)（2）引用計數(shù)（3）邏輯設(shè)備（4）邏輯塊號（5）指針1和指針24.對換使用表描述了對換設(shè)備上的每一頁引用計數(shù)：記錄引用該頁的進(jìn)程數(shù)7.5UNIX虛擬內(nèi)存管理頁框號有效位……103無效……頁表66k類型塊……disk847……磁盤塊描述表頁框號塊引用數(shù)…..……..…頁框數(shù)據(jù)表塊引用數(shù)……8470對換使用表117768471有效1776例如，系統(tǒng)中某進(jìn)程的一個區(qū)大小為68k，如果進(jìn)程在存取虛地址66k時產(chǎn)生一個有效錯（訪問無效頁），應(yīng)如何處理？7.5UNIX虛擬內(nèi)存管理二、頁面淘汰－－偷頁頁在內(nèi)存123…n未被引用的頁年齡增加可以換出頁不在內(nèi)存換出換入7.5UNIX虛擬內(nèi)存管理1.換出頁面（1）對換設(shè)備上沒有該頁復(fù)本（2）對換設(shè)備上有該頁復(fù)本，且頁未修改（3）對換設(shè)備上有該頁復(fù)本，且頁被修改（1）－－－多頁統(tǒng)一換出到對換設(shè)備上（2）－－－無需換出，直接將該頁清為無效，并鏈入空閑鏈表（3）－－－需統(tǒng)一換出到對換設(shè)備7.5UNIX虛擬內(nèi)存管理2.核心向?qū)Q設(shè)備寫一頁面（1）清除頁表項有效位（2）將頁框數(shù)據(jù)表引用計數(shù)減一，若減為0，則將其鏈入鏈表，換出或重新分配3.調(diào)入所缺頁面（1）缺頁在文件區(qū)：從文件區(qū)調(diào)入（2）缺頁在對換設(shè)備上：從對換區(qū)調(diào)入（3）缺頁在內(nèi)存中：修改表項和鏈表練習(xí)判斷：請求分頁管理系統(tǒng)，若把頁面大小增加一倍，則缺頁中斷次數(shù)會減少一半判斷：虛地址即程序執(zhí)行時所要訪問的內(nèi)存地址在請求分頁存儲管理系統(tǒng)中，地址變換過程可能會因為（）原因而發(fā)生中斷虛存的理論基礎(chǔ)是（）練習(xí)虛存中LRU算法，分配3頁，每頁存200個整數(shù)，其中第一頁存放程序，程序已在內(nèi)存，數(shù)組A按先行后列存儲，求程序A和B的缺頁次數(shù)分別為多少？程序A：程序B：Fori:=1to100doForj:=1to100doForj:=1to100doFori:=1to100doA[i,j]:=0A[i,j]:=0練習(xí)請求分頁管理系統(tǒng)中，某頁表如圖

：

頁面大小為4KB，一次內(nèi)存的訪問時間是100ns，一次快表（TLB）的訪問時間是10ns，處理一次缺頁的平均時間為108ns（已含更新TLB和頁表的時間），進(jìn)程的駐留集大小固定為2，采用LRU算法和局部淘汰策略。假設(shè):①TLB初始為空；②忽略訪問頁表之后的TLB更新時間；③有效位為0表示頁面不在內(nèi)存，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，請問：

（1）

依次訪問上述三個虛地址，各需多少時間？給出計算過程。

（2）

基于上述訪問序列，虛地址1565H的

物理地址是多少？

頁號頁框號有效位0101H11--02254H1練習(xí)設(shè)某計算機(jī)的邏輯地址空間和物理地址空間均為64KB.按字節(jié)編址。若某進(jìn)程最多需要6頁（Page）數(shù)據(jù)存儲空間，頁的大小為1KB.操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個頁框（PageFame）當(dāng)該進(jìn)程執(zhí)行到時刻260時，要訪問邏輯地址為17CAH的數(shù)據(jù)，請問答下列問題：

1）該邏輯地址對應(yīng)的頁號是多少？

2）采用FIFO置換算法，該邏輯地址對應(yīng)的物理地址是多少？3）若采用時鐘（CLOCK）置換算法，該邏輯地址對應(yīng)的物理地址是多少？（當(dāng)前指針指向2號頁框）頁號頁框號裝入時刻訪問位071301142301222001391601練習(xí)關(guān)于請求分頁系統(tǒng)的頁面置換策略如下：從0時刻開始掃描，每隔5個時間單位掃描一輪駐留集（掃描時間忽略不計），且在本輪沒有訪問過的頁框?qū)⒈换厥?，并?/p>