操作系統(tǒng)課件

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

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

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

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

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

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

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

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

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

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

：

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

（1）

依次訪(fǎng)問(wèn)上述三個(gè)虛地址，各需多少時(shí)間？給出計(jì)算過(guò)程。

（2）

基于上述訪(fǎng)問(wèn)序列，虛地址1565H的

物理地址是多少？

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

1）該邏輯地址對(duì)應(yīng)的頁(yè)號(hào)是多少？

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