操作系統(tǒng)2002--存儲管理(2)

1、五、分段存儲管理 1、基本原理 引入分段存儲管理方式，主要是為了滿足用戶的下引入分段存儲管理方式，主要是為了滿足用戶的下述要求：述要求：q 方便編程方便編程q 分段共享分段共享q 分段保護分段保護q 動態(tài)鏈接動態(tài)鏈接q 動態(tài)增長動態(tài)增長A A、分段、分段 在分段存儲管理方式中，作業(yè)的地址空間被劃在分段存儲管理方式中，作業(yè)的地址空間被劃分為若干個段，每個段定義了一組邏輯信息。每個分為若干個段，每個段定義了一組邏輯信息。每個段的邏輯地址都是從段的邏輯地址都是從0 0開始。段內(nèi)地址是連續(xù)的，開始。段內(nèi)地址是連續(xù)的，但段與段之間不一定是連續(xù)的。但段與段之間不一定是連續(xù)的。 分段的基本原理分段的基本原理

2、 子程子程段序段序數(shù)據(jù)棧數(shù)據(jù)棧符號表符號表主程主程序段序段系統(tǒng)系統(tǒng)函數(shù)函數(shù)作業(yè)的邏輯地址由段號與段內(nèi)地址所組成，結(jié)構(gòu)如下：作業(yè)的邏輯地址由段號與段內(nèi)地址所組成，結(jié)構(gòu)如下： 段號段號段內(nèi)地址段內(nèi)地址3116 150如果機器的地址有如果機器的地址有m m位，其中段內(nèi)地址占位，其中段內(nèi)地址占n n位，則每位，則每個作業(yè)最多可分為個作業(yè)最多可分為2 2(m-n) (m-n) 個段。個段。 B B、段表、段表 為使程序能夠正常運行，亦即能從物理內(nèi)存中為使程序能夠正常運行，亦即能從物理內(nèi)存中找出每個邏輯段所對應(yīng)的位置，應(yīng)象分頁系統(tǒng)那樣，找出每個邏輯段所對應(yīng)的位置，應(yīng)象分頁系統(tǒng)那樣，在系統(tǒng)中為每個作業(yè)建立一

3、張段的映射表，簡稱段在系統(tǒng)中為每個作業(yè)建立一張段的映射表，簡稱段表。在配置了段表后，程序在執(zhí)行過程中可通過查表。在配置了段表后，程序在執(zhí)行過程中可通過查找段表，找到每個段所對應(yīng)的內(nèi)存區(qū)找段表，找到每個段所對應(yīng)的內(nèi)存區(qū)。 子程子程段序段序數(shù)據(jù)棧數(shù)據(jù)棧符號表符號表主程主程序段序段系統(tǒng)系統(tǒng)函數(shù)函數(shù)段表段表段長段長基址基址段號段號012342 2、主存空間的分配與去配、主存空間的分配與去配 段式存儲管理分配主存空間的方法及回收存儲段式存儲管理分配主存空間的方法及回收存儲空間的方法與可變分區(qū)管理方式所采用的方法相同空間的方法與可變分區(qū)管理方式所采用的方法相同。 3 3、地址轉(zhuǎn)換與存儲保護、地址轉(zhuǎn)換與存儲

4、保護 地址變換機構(gòu)和變換過程地址變換機構(gòu)和變換過程 段表始址段表始址段表長度段表長度1K6K6004K5008K2009200位移量位移量段號段號段號段號01232100+控制寄存器控制寄存器8292基址基址段長段長越界越界邏輯地址邏輯地址物理地址物理地址主存主存例題例題: :某分段管理中采用下表所示的段表：某分段管理中采用下表所示的段表： 段號段號段的長度段的長度段的起段的起始地址始地址01234660141005809621933309012371954 給定段號和段內(nèi)地址，說明分段管理中的地址變給定段號和段內(nèi)地址，說明分段管理中的地址變 換過程；換過程； 計算計算00，430430，11

5、，1010，22，500500，33，400400， 44，2020，55，100 100 的內(nèi)存地址，其中方括號內(nèi)的內(nèi)存地址，其中方括號內(nèi) 的第一個元素是段號，第二個元素是段內(nèi)地址；的第一個元素是段號，第二個元素是段內(nèi)地址； 說明存取主存的一條指令或數(shù)據(jù)至少要訪問幾次說明存取主存的一條指令或數(shù)據(jù)至少要訪問幾次 內(nèi)存。內(nèi)存。解答：解答：00，430 430 的物理地址是：的物理地址是：219+430=649219+430=64911，10 10 的物理地址是：的物理地址是：3300+10=33103300+10=331022，500 500 的物理地址是：的物理地址是：500100500100

6、，越界，越界33，400 400 的物理地址是：的物理地址是：1237+400=16371237+400=163744，20 20 的物理地址是：的物理地址是：1952+20=19721952+20=197255，100 100 的物理地址是：的物理地址是：5454，段號越界，段號越界存取主存的一條指令或數(shù)據(jù)至少要訪問存取主存的一條指令或數(shù)據(jù)至少要訪問2 2次內(nèi)存次內(nèi)存段號段號段的長度段的長度段的起始段的起始地址地址01234660141005809621933309012371954分段的共享分段的共享 與分頁系統(tǒng)相比較，分段系統(tǒng)對段的保護更加簡單易行。與分頁系統(tǒng)相比較，分段系統(tǒng)對段的保護更

7、加簡單易行。 假定有一文本編輯程序，程序區(qū)假定有一文本編輯程序，程序區(qū)500K500K，數(shù)據(jù)區(qū)，數(shù)據(jù)區(qū)100K100K，兩個，兩個用戶作業(yè)同時進行文本編輯，對于分頁系統(tǒng)，假定每個頁面大用戶作業(yè)同時進行文本編輯，對于分頁系統(tǒng)，假定每個頁面大小為小為1K1K。對于分頁系統(tǒng)，每個用戶作業(yè)需建立一個頁表，其中，。對于分頁系統(tǒng)，每個用戶作業(yè)需建立一個頁表，其中，500500個頁表項對應(yīng)程序區(qū)，個頁表項對應(yīng)程序區(qū)，100100個頁表項對應(yīng)數(shù)據(jù)區(qū)。而如果采個頁表項對應(yīng)數(shù)據(jù)區(qū)。而如果采用分段系統(tǒng)，則每個段表只需兩個段表項，系統(tǒng)的開銷要小的用分段系統(tǒng)，則每個段表只需兩個段表項，系統(tǒng)的開銷要小的多，而且管理也會更

8、加簡單。多，而且管理也會更加簡單。 程序段程序段數(shù)據(jù)段數(shù)據(jù)段程序程序數(shù)據(jù)數(shù)據(jù)頁表頁表段表段表分頁和分段的主要區(qū)別分頁和分段的主要區(qū)別 1 1、頁是信息的物理單位，而段是信息的邏輯單位；、頁是信息的物理單位，而段是信息的邏輯單位；2 2、頁的大小固定且由系統(tǒng)決定，而段的長度不固定，、頁的大小固定且由系統(tǒng)決定，而段的長度不固定， 決定于用戶編寫的程序；決定于用戶編寫的程序；3 3、分頁的作業(yè)地址空間是一維的，而分段的地址空間、分頁的作業(yè)地址空間是一維的，而分段的地址空間 是二維的。是二維的。4 4、分段系統(tǒng)便于動態(tài)鏈接，存儲保護，便于增長、修、分段系統(tǒng)便于動態(tài)鏈接，存儲保護，便于增長、修 改和信息

9、共享。改和信息共享。4 4、可分頁的段式存儲管理、可分頁的段式存儲管理 A A、基本原理、基本原理 先將作業(yè)分為若干個段，再把每個段劃分為若干頁。先將作業(yè)分為若干個段，再把每個段劃分為若干頁。 段號段號頁內(nèi)地址頁內(nèi)地址段內(nèi)頁號段內(nèi)頁號地址結(jié)構(gòu)地址結(jié)構(gòu)段號段號狀態(tài)狀態(tài)頁表頁表大小大小頁表頁表始址始址段表控制寄存器段表控制寄存器0 0號段頁表號段頁表1 1號段頁表號段頁表主存主存B B、地址變換過程、地址變換過程 再獲得邏輯地址后，根據(jù)段表的控制寄存器，得到段表的首再獲得邏輯地址后，根據(jù)段表的控制寄存器，得到段表的首 地址；地址； 首先利用段號，將它與段表長度進行比較，如段號大于段表首先利用段號，

10、將它與段表長度進行比較，如段號大于段表 長度，表示段號越界；長度，表示段號越界； 根據(jù)段號求得對應(yīng)該段的頁表的首地址；根據(jù)段號求得對應(yīng)該段的頁表的首地址； 再根據(jù)段內(nèi)頁號得到該頁對應(yīng)的物理塊的地址；再根據(jù)段內(nèi)頁號得到該頁對應(yīng)的物理塊的地址； 最后將物理塊的首地址和頁內(nèi)地址相加構(gòu)成最后的物理地址。最后將物理塊的首地址和頁內(nèi)地址相加構(gòu)成最后的物理地址。 1 1、基本概念、基本概念 虛擬存儲器虛擬存儲器 為用戶提供一種不受物理存儲器結(jié)構(gòu)和容量限為用戶提供一種不受物理存儲器結(jié)構(gòu)和容量限制的存儲器的技術(shù)稱為虛擬存儲器，或稱虛擬存儲制的存儲器的技術(shù)稱為虛擬存儲器，或稱虛擬存儲技術(shù)。技術(shù)。 它是用戶編程時所

11、使用的一種用戶思維中的存它是用戶編程時所使用的一種用戶思維中的存儲器，它可以是任何結(jié)構(gòu)（一維線性空間、二維空儲器，它可以是任何結(jié)構(gòu)（一維線性空間、二維空間、乃至間、乃至n n維空間），并沒有容量的限制。維空間），并沒有容量的限制。 現(xiàn)代計算機操作系統(tǒng)都采用了這種技術(shù)，使得現(xiàn)代計算機操作系統(tǒng)都采用了這種技術(shù)，使得用戶編程序時不需要考慮物理內(nèi)存的結(jié)構(gòu)和容量，用戶編程序時不需要考慮物理內(nèi)存的結(jié)構(gòu)和容量，極大地方便了用戶。極大地方便了用戶。 虛擬存儲器需要大容量的外存儲器的支持，或虛擬存儲器需要大容量的外存儲器的支持，或稱物資基礎(chǔ)。稱物資基礎(chǔ)。五、虛擬存儲器五、虛擬存儲器 2 2、虛擬存儲器的工作原理

12、、虛擬存儲器的工作原理 1 1、局部性原理、局部性原理 程序執(zhí)行時的局部性規(guī)律：程序執(zhí)行時的局部性規(guī)律： 程序在執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指程序在執(zhí)行時，除了少部分的轉(zhuǎn)移和過程調(diào)用指 令外，在大多數(shù)情況下，仍然是順序執(zhí)行的。令外，在大多數(shù)情況下，仍然是順序執(zhí)行的。 過程調(diào)用將會使程序的執(zhí)行軌跡從一部分內(nèi)存區(qū)過程調(diào)用將會使程序的執(zhí)行軌跡從一部分內(nèi)存區(qū) 域轉(zhuǎn)到另一部分區(qū)域，但在大多數(shù)情況下，過程域轉(zhuǎn)到另一部分區(qū)域，但在大多數(shù)情況下，過程 調(diào)用的深度都不超過調(diào)用的深度都不超過5 5。 程序中存在許多循環(huán)結(jié)構(gòu)，它們雖由少數(shù)指令構(gòu)程序中存在許多循環(huán)結(jié)構(gòu)，它們雖由少數(shù)指令構(gòu) 成，但可以多次執(zhí)行成，

13、但可以多次執(zhí)行 程序中的許多數(shù)據(jù)結(jié)構(gòu)，如數(shù)組，在被操作時，程序中的許多數(shù)據(jù)結(jié)構(gòu)，如數(shù)組，在被操作時， 往往局限于一個很小的范圍內(nèi)。往往局限于一個很小的范圍內(nèi)。 局部性原理表現(xiàn)在：局部性原理表現(xiàn)在： 時間局限性時間局限性 是指某個位置最近被訪問了，那么往往很快又要是指某個位置最近被訪問了，那么往往很快又要被再次訪問。被再次訪問。 空間局限性空間局限性 是指一旦某個位置最近被訪問了，那么它附近的是指一旦某個位置最近被訪問了，那么它附近的位置也要被訪問。位置也要被訪問。 3 3、虛擬存儲器的定義、虛擬存儲器的定義 所謂虛擬存儲器，是指僅把作業(yè)的一部分裝入內(nèi)所謂虛擬存儲器，是指僅把作業(yè)的一部分裝入內(nèi)存

14、便可運行作業(yè)的存儲器系統(tǒng)。存便可運行作業(yè)的存儲器系統(tǒng)。 4 4、虛擬存儲器的實現(xiàn)方式：、虛擬存儲器的實現(xiàn)方式：q 頁式虛擬存貯頁式虛擬存貯q 段式虛擬存儲段式虛擬存儲 頁式虛擬存儲頁式虛擬存儲 它是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功它是在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的虛擬存儲系統(tǒng)。能、頁面置換功能所形成的虛擬存儲系統(tǒng)。 系統(tǒng)必須提供的硬件支持：系統(tǒng)必須提供的硬件支持： 請求分頁的頁表機構(gòu)請求分頁的頁表機構(gòu) 缺頁中斷機構(gòu)缺頁中斷機構(gòu) 地址變換機構(gòu)地址變換機構(gòu) 段式虛擬存儲段式虛擬存儲 這是在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段功這是在分段系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)段功能

15、及分段置換功能后，所形成的段式虛擬存儲系統(tǒng)。能及分段置換功能后，所形成的段式虛擬存儲系統(tǒng)。 系統(tǒng)必須提供的硬件支持：系統(tǒng)必須提供的硬件支持： 請求分段的段表機構(gòu)請求分段的段表機構(gòu) 缺段中斷機構(gòu)缺段中斷機構(gòu) 地址變換機構(gòu)地址變換機構(gòu)虛擬存儲器的特征：虛擬存儲器的特征： v離散性離散性 指內(nèi)存分配時采用離散分配方式指內(nèi)存分配時采用離散分配方式v多次性多次性 指一個作業(yè)被分成多次的調(diào)入內(nèi)存運行指一個作業(yè)被分成多次的調(diào)入內(nèi)存運行v對換性對換性 指允許在作業(yè)運行過程中在內(nèi)存和磁盤指允許在作業(yè)運行過程中在內(nèi)存和磁盤 間換進、換出間換進、換出v虛擬性虛擬性 指能夠從邏輯上擴充內(nèi)存容量。指能夠從邏輯上擴充內(nèi)存

16、容量。 1 1、問題的提出、問題的提出 在頁式存儲管理提高了內(nèi)存的利用效率，在頁式存儲管理提高了內(nèi)存的利用效率，但并不為用戶提供虛存，換句話說，當一個用但并不為用戶提供虛存，換句話說，當一個用戶程序的頁數(shù)大于當前總空閑內(nèi)存塊數(shù)時，系戶程序的頁數(shù)大于當前總空閑內(nèi)存塊數(shù)時，系統(tǒng)就不能將該程序裝入運行。即用戶程序?qū)⑹芙y(tǒng)就不能將該程序裝入運行。即用戶程序?qū)⑹艿轿锢韮?nèi)存大小的限制。為了解決這個問題，到物理內(nèi)存大小的限制。為了解決這個問題，人們提出請求分頁存儲管理技術(shù)人們提出請求分頁存儲管理技術(shù)頁式虛擬存儲管理頁式虛擬存儲管理 需要解決的問題需要解決的問題 如何發(fā)現(xiàn)執(zhí)行的程序或訪問的數(shù)據(jù)不在內(nèi)存；如何發(fā)現(xiàn)

17、執(zhí)行的程序或訪問的數(shù)據(jù)不在內(nèi)存； 程序或數(shù)據(jù)什么時候調(diào)入內(nèi)存，調(diào)入策略；程序或數(shù)據(jù)什么時候調(diào)入內(nèi)存，調(diào)入策略； 當一些頁調(diào)入內(nèi)存時，內(nèi)存沒有空閑內(nèi)存時，當一些頁調(diào)入內(nèi)存時，內(nèi)存沒有空閑內(nèi)存時， 將淘汰哪些頁，采用什么淘汰策略。將淘汰哪些頁，采用什么淘汰策略。2 2、基本原理、基本原理 頁式虛擬存儲中的頁表項組成頁式虛擬存儲中的頁表項組成： 頁號頁號物理塊號物理塊號狀態(tài)位狀態(tài)位訪問字段訪問字段修改位修改位外存地址外存地址狀態(tài)位狀態(tài)位：用于指示該頁是否已調(diào)入內(nèi)存；：用于指示該頁是否已調(diào)入內(nèi)存；訪問字段訪問字段：用于記錄該頁在一段時間內(nèi)被訪問的：用于記錄該頁在一段時間內(nèi)被訪問的 次數(shù)；次數(shù)；修改位修

18、改位：表示該頁在調(diào)入內(nèi)存后是否被修改過；：表示該頁在調(diào)入內(nèi)存后是否被修改過；外存地址外存地址：用于指出該頁在外存上的地址。：用于指出該頁在外存上的地址。3 3、頁式虛擬存儲中的缺頁中斷機構(gòu)、頁式虛擬存儲中的缺頁中斷機構(gòu)缺頁中斷與一般中斷的區(qū)別：缺頁中斷與一般中斷的區(qū)別：v在指令執(zhí)行期間產(chǎn)生和處理中斷信號在指令執(zhí)行期間產(chǎn)生和處理中斷信號v在一條指令執(zhí)行期間，可能產(chǎn)生多次中斷。在一條指令執(zhí)行期間，可能產(chǎn)生多次中斷。 COPY ATO BAB4 4、頁式虛擬存儲中的地址變換機構(gòu)、頁式虛擬存儲中的地址變換機構(gòu) 在分頁系統(tǒng)地址變化機構(gòu)的基礎(chǔ)上，再增加在分頁系統(tǒng)地址變化機構(gòu)的基礎(chǔ)上，再增加某些虛擬存儲器的

19、功能而形成的。某些虛擬存儲器的功能而形成的。 地址變換過程地址變換過程 頁號頁號頁表長度頁表長度越界中斷越界中斷開開 始始CPU檢索快表檢索快表頁表項在快表中頁表項在快表中訪問頁表訪問頁表頁在內(nèi)存頁在內(nèi)存修改快表修改快表修改訪問位和修改位修改訪問位和修改位形成物理地址形成物理地址地址變換結(jié)束地址變換結(jié)束內(nèi)存滿否內(nèi)存滿否該頁被修改過該頁被修改過將一頁從外存換入內(nèi)存將一頁從外存換入內(nèi)存啟動啟動I/O硬件硬件CPU從外存讀缺頁從外存讀缺頁將該頁寫回外存將該頁寫回外存修改頁表修改頁表選擇一頁換出選擇一頁換出從外存中找到缺頁從外存中找到缺頁保留保留CPU現(xiàn)場現(xiàn)場缺頁中斷處理缺頁中斷處理程序請求訪問一頁程

20、序請求訪問一頁是是否否是是否否否否是是否否是是否否是是產(chǎn)生缺頁中產(chǎn)生缺頁中斷，請求調(diào)頁斷，請求調(diào)頁5 5、頁面調(diào)度、頁面調(diào)度 主存的分配與置換策略主存的分配與置換策略固定分配局部置換：基于進程的類型（交互型或批固定分配局部置換：基于進程的類型（交互型或批處理型），或根據(jù)程序員、系統(tǒng)管理員的建議，為處理型），或根據(jù)程序員、系統(tǒng)管理員的建議，為進程分配一固定頁數(shù)的內(nèi)存空間。進程分配一固定頁數(shù)的內(nèi)存空間?？勺兎峙淙种脫Q：先為系統(tǒng)中的每一個進程分配可變分配全局置換：先為系統(tǒng)中的每一個進程分配一定數(shù)目的物理塊，一定數(shù)目的物理塊，OSOS本身保留一個空閑物理塊隊本身保留一個空閑物理塊隊列。當某進程發(fā)現(xiàn)缺

21、頁時，由系統(tǒng)從空閑物理塊隊列。當某進程發(fā)現(xiàn)缺頁時，由系統(tǒng)從空閑物理塊隊列中取出一個進行分配。列中取出一個進行分配?？勺兎峙渚植恐脫Q：同樣基于進程的類型或根據(jù)程可變分配局部置換：同樣基于進程的類型或根據(jù)程序員的要求，為每個進程分配一定數(shù)量的內(nèi)存空間。序員的要求，為每個進程分配一定數(shù)量的內(nèi)存空間。當某進程發(fā)生缺頁時，只允許從該進程在內(nèi)存的頁當某進程發(fā)生缺頁時，只允許從該進程在內(nèi)存的頁面中選出一頁換出，這樣就不會影響其它進程的運面中選出一頁換出，這樣就不會影響其它進程的運行。行。 6 6、分配算法、分配算法 在采用固定分配算法時，如何將系統(tǒng)中可供分配在采用固定分配算法時，如何將系統(tǒng)中可供分配的所有物

22、理塊分配給各個進程，可采取下述方法：的所有物理塊分配給各個進程，可采取下述方法：平均分配算法平均分配算法：將系統(tǒng)中所有可供分配的物理塊，平：將系統(tǒng)中所有可供分配的物理塊，平均分配各個進程。均分配各個進程。按比例分配算法按比例分配算法：根據(jù)進程的大小按比例分配物理塊。：根據(jù)進程的大小按比例分配物理塊。例如：如果各進程頁面數(shù)的總和是：例如：如果各進程頁面數(shù)的總和是： niiSS1同時，假定系統(tǒng)中可用物理塊總數(shù)為同時，假定系統(tǒng)中可用物理塊總數(shù)為m m， 則每個進則每個進程所能分到的物理塊程所能分到的物理塊b bi i為：為： mSSbii考慮優(yōu)先權(quán)的分配算法考慮優(yōu)先權(quán)的分配算法：把內(nèi)存中可供分配的物

23、理塊分：把內(nèi)存中可供分配的物理塊分成兩個部分：一部分按比例分配給各個進程；另一部分成兩個部分：一部分按比例分配給各個進程；另一部分則根據(jù)各進程的優(yōu)先權(quán)，適當?shù)卦黾悠湎鄳?yīng)份額后，分則根據(jù)各進程的優(yōu)先權(quán)，適當?shù)卦黾悠湎鄳?yīng)份額后，分配給各進程。配給各進程。 7 7、頁面調(diào)入策略、頁面調(diào)入策略 何時調(diào)入頁面：何時調(diào)入頁面：預(yù)調(diào)頁策略：將那些預(yù)計在不久之后便會被訪問的程序預(yù)調(diào)頁策略：將那些預(yù)計在不久之后便會被訪問的程序和數(shù)據(jù)所在的頁面，預(yù)先調(diào)入內(nèi)存。和數(shù)據(jù)所在的頁面，預(yù)先調(diào)入內(nèi)存。請求調(diào)頁策略：當發(fā)現(xiàn)所需要的頁面不再內(nèi)存時，立即請求調(diào)頁策略：當發(fā)現(xiàn)所需要的頁面不再內(nèi)存時，立即提出請求，由系統(tǒng)將所需頁面調(diào)

24、入內(nèi)存。提出請求，由系統(tǒng)將所需頁面調(diào)入內(nèi)存。 從何處調(diào)入頁面從何處調(diào)入頁面對于不同的系統(tǒng)，所采用的方法也不相同，可分成三種對于不同的系統(tǒng)，所采用的方法也不相同，可分成三種情況：情況： 如果系統(tǒng)擁有足夠的內(nèi)存空間，可以全部從對換區(qū)調(diào)入頁面，如果系統(tǒng)擁有足夠的內(nèi)存空間，可以全部從對換區(qū)調(diào)入頁面，以提高調(diào)頁速度。以提高調(diào)頁速度。 如果系統(tǒng)缺少足夠的內(nèi)存空間，則可以對不被修改的部分，如果系統(tǒng)缺少足夠的內(nèi)存空間，則可以對不被修改的部分，直接從文件區(qū)調(diào)入；對于那些可能被修改的部分，將它們換出直接從文件區(qū)調(diào)入；對于那些可能被修改的部分，將它們換出時，便需調(diào)到對換區(qū)，以后需要時再從對換區(qū)調(diào)入。時，便需調(diào)到對換

25、區(qū)，以后需要時再從對換區(qū)調(diào)入。 UNIXUNIX方式：凡是未運行過的頁面，都從文件區(qū)調(diào)入，對于方式：凡是未運行過的頁面，都從文件區(qū)調(diào)入，對于曾經(jīng)運行過而又被換出的頁面，由于是放在對換區(qū)的，因此在曾經(jīng)運行過而又被換出的頁面，由于是放在對換區(qū)的，因此在下次調(diào)入時，應(yīng)從對換區(qū)調(diào)入。下次調(diào)入時，應(yīng)從對換區(qū)調(diào)入。 常用到的幾個術(shù)語：常用到的幾個術(shù)語：抖動：剛剛被淘汰出去的頁面，不久又被調(diào)入主存，這種現(xiàn)象，抖動：剛剛被淘汰出去的頁面，不久又被調(diào)入主存，這種現(xiàn)象， 稱為抖動（也稱為顛簸）。稱為抖動（也稱為顛簸）。頁面走向：用引用串來表示。頁面走向：用引用串來表示。頁面失效率：缺頁中斷次數(shù)占全部訪問頁面數(shù)的百

26、分比，即：頁面失效率：缺頁中斷次數(shù)占全部訪問頁面數(shù)的百分比，即： 失效率失效率 = = （失效次數(shù)（失效次數(shù) / / 訪問頁面總數(shù)）訪問頁面總數(shù)） 100% 100%在討論頁面淘汰算法前假設(shè)：在討論頁面淘汰算法前假設(shè)：引用串：對進程邏輯地址空間的訪問所涉及到的頁引用串：對進程邏輯地址空間的訪問所涉及到的頁 面號序列。面號序列。僅考慮頁面號，不需考慮其頁內(nèi)位移。僅考慮頁面號，不需考慮其頁內(nèi)位移。如連續(xù)兩次對頁面如連續(xù)兩次對頁面P P進行訪問，則至少第二次訪問不進行訪問，則至少第二次訪問不 會產(chǎn)生缺頁中斷。會產(chǎn)生缺頁中斷。隨著可用塊數(shù)量的增加，產(chǎn)生缺頁中斷的次數(shù)將會隨著可用塊數(shù)量的增加，產(chǎn)生缺頁中

27、斷的次數(shù)將會 減少。減少。 8 8、頁面置換算法、頁面置換算法v先進先出頁面置換算法先進先出頁面置換算法 該算法總是在淘汰最先進入內(nèi)存的頁面，即選該算法總是在淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留最久的頁面予以淘汰，即先進入主擇在內(nèi)存中駐留最久的頁面予以淘汰，即先進入主存的頁，先退出儲存。存的頁，先退出儲存。FIFOFIFO（3 3塊）塊） 引用串引用串7 0 1 2 0 3 0 4 2 3 0 32 1 2 01 7 0 1 7 7 7 2 2 2 4 4 4 0 0 0 7 7 7 0 0 0 3 3 3 2 2 2 1 1 1 0 0 1 1 1 0 0 0 3 3 3 2 2 2

28、1發(fā)生置換發(fā)生置換 共進行了共進行了1212次頁面置換次頁面置換 假定系統(tǒng)分配給某進程假定系統(tǒng)分配給某進程3 3個存儲塊，并考慮如下引用個存儲塊，并考慮如下引用串：串： 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 FIFOFIFO（4 4塊）塊） 共進行了共進行了6 6次頁面置換次頁面置換 引用串引用串70120304230321201701 7012 3 4 0 12 7 701 2 3 4 01 2 70 1 2 3 40 1 7 0 1 2 34 0 發(fā)生置換發(fā)生置換 例題

29、：在請求分頁存儲管理中，若采用先進先出頁面淘汰算法，例題：在請求分頁存儲管理中，若采用先進先出頁面淘汰算法，會產(chǎn)生一種奇怪的現(xiàn)象：分配給作業(yè)的物理塊越多，作業(yè)執(zhí)行會產(chǎn)生一種奇怪的現(xiàn)象：分配給作業(yè)的物理塊越多，作業(yè)執(zhí)行時的缺頁率反而升高。試舉一例說明這種現(xiàn)象。時的缺頁率反而升高。試舉一例說明這種現(xiàn)象。 解答：若在作業(yè)運行過程中地址訪問的引用串為：解答：若在作業(yè)運行過程中地址訪問的引用串為：4 4，3 3，2 2，1 1，4 4，3 3，5 5，4 4，3 3，2 2，1 1，5 5。下面是為作業(yè)分配。下面是為作業(yè)分配3 3個和個和4 4個物理塊個物理塊時的頁面訪問過程：時的頁面訪問過程： 引用串

30、引用串432143543215 4443214-3 5- 332143-52- 21435-21-缺頁缺頁 FIFOFIFO（3 3塊）塊） FIFOFIFO（4 4塊）塊） 引用串引用串432143543215 4444-3215 43 333-215432 22-154321 1 - -5 43 2 15缺頁缺頁 可見，可見，3 3塊時缺頁中斷次數(shù)為塊時缺頁中斷次數(shù)為9 9，而，而4 4塊時為塊時為1010v最佳頁面置換算法最佳頁面置換算法 所選擇的被淘汰的頁面，將是以后永不被使用的，或者所選擇的被淘汰的頁面，將是以后永不被使用的，或者是在最長時間內(nèi)不再被訪問的頁面。是在最長時間內(nèi)不再被訪

31、問的頁面。 OPTOPT（3 3塊）塊） 引用串引用串70120304230321201701 7772 2 2 2 2 7 700 0 4 0 0 0 11 3 3 3 1 1 發(fā)生置換發(fā)生置換 共進行了共進行了6 6次頁面置換。次頁面置換。 v最近最久未使用置換算法最近最久未使用置換算法 選擇最近最久未使用過的頁面進行淘汰，是用作業(yè)執(zhí)選擇最近最久未使用過的頁面進行淘汰，是用作業(yè)執(zhí)行過程中過去的頁面蹤跡來推測未來的行為。行過程中過去的頁面蹤跡來推測未來的行為。 LRULRU（3 3塊）塊） 引用串引用串70120304230321201701 7772 2 4440 1 1 1 000 0

32、0033 3 0 0 11 3 3222 2 2 7 發(fā)生置換發(fā)生置換 共發(fā)生共發(fā)生9 9次置換次置換 例題：近代計算機系統(tǒng)常采用請求頁式存儲管理方案來管理例題：近代計算機系統(tǒng)常采用請求頁式存儲管理方案來管理自己的主存。自己的主存。 用簡圖說明它的地址變換方法；用簡圖說明它的地址變換方法； 假定某假定某作業(yè)作業(yè)J J所涉及的頁面依次為：所涉及的頁面依次為：0 0，1 1，0 0，2 2，0 0，1 1，0 0，1 1，3 3，0 0，并已知主存中有并已知主存中有3 3個可供作業(yè)個可供作業(yè)J J使用的空閑存儲塊。試說明采使用的空閑存儲塊。試說明采用用FIFOFIFO和和LRULRU兩種不同淘汰算

33、法時，缺頁中斷率各是多少？兩種不同淘汰算法時，缺頁中斷率各是多少？ FIFOFIFO（3 3塊）塊） 引用串引用串01020101030 00-0-1 2 1-1-23 2-30缺頁缺頁 缺頁中斷次數(shù)為缺頁中斷次數(shù)為5 5次次 LRULRU（3 3塊）塊） 引用串引用串01020101030 00-0-0 - 1-1-1- -2-3-缺頁缺頁 缺頁中斷次數(shù)為缺頁中斷次數(shù)為4 4次次 注意，計算缺頁次數(shù)和缺頁率時，要注意初始時刻所注意，計算缺頁次數(shù)和缺頁率時，要注意初始時刻所有物理塊為空。此時，雖然不發(fā)生頁面的淘汰，但卻需要有物理塊為空。此時，雖然不發(fā)生頁面的淘汰，但卻需要引起缺頁中斷。引起缺頁

34、中斷。 vCLOCKCLOCK置換算法置換算法 簡單的簡單的CLOCKCLOCK置換算法置換算法 為每頁設(shè)置一個訪問位，將內(nèi)存中所有被使用為每頁設(shè)置一個訪問位，將內(nèi)存中所有被使用的頁面通過鏈接指針鏈成一個循環(huán)隊列。當某頁被的頁面通過鏈接指針鏈成一個循環(huán)隊列。當某頁被訪問時，其訪問位被置訪問時，其訪問位被置1 1。置換算法再選擇一頁被淘。置換算法再選擇一頁被淘汰時，只需按鏈查找，如果檢查到鏈中的某頁訪問汰時，只需按鏈查找，如果檢查到鏈中的某頁訪問位是位是0 0，則選擇該頁換出，若為，則選擇該頁換出，若為1 1，則重新將它置為，則重新將它置為0 0，然后檢查下一頁然后檢查下一頁。塊號塊號頁號頁號訪

35、問位訪問位指針指針0 1 240 3 421 5 650 711 隊首指針隊首指針頁面訪問頁面訪問位為位為0置頁面訪置頁面訪問位為問位為0入口入口選擇該頁面淘汰選擇該頁面淘汰是是否否查詢指針前進一查詢指針前進一步，指向下一表目步，指向下一表目返回返回 改進的改進的CLOCKCLOCK置換算法置換算法 除了考慮頁面的使用情況外，還考慮置換代價，除了考慮頁面的使用情況外，還考慮置換代價，即同時檢查訪問位即同時檢查訪問位A A和修改位和修改位M M。1 1類類 A=0A=0，M=0M=0，表示該頁最近既未被訪問，也未，表示該頁最近既未被訪問，也未 被修改，是最佳淘汰頁；被修改，是最佳淘汰頁；2 2類

36、類 A=0A=0，M=1M=1，表示該頁最近既未被訪問，但已，表示該頁最近既未被訪問，但已 被修改，并不是很好的淘汰頁；被修改，并不是很好的淘汰頁；3 3類類 A=1A=1，M=0M=0，最近已被訪問，但未被修改，該，最近已被訪問，但未被修改，該 頁有可能再被訪問；頁有可能再被訪問；4 4類類 A=1A=1，M=1M=1，最近已被訪問，也被修改，該頁，最近已被訪問，也被修改，該頁 有可能再被訪問；有可能再被訪問；改進型改進型CLOCKCLOCK算法的執(zhí)行過程：算法的執(zhí)行過程：第一步，從指針所指示的當前位置開始，掃描循第一步，從指針所指示的當前位置開始，掃描循環(huán)隊列，尋找環(huán)隊列，尋找A=0A=0

37、且且M=0M=0的頁面，如找到，則淘汰的頁面，如找到，則淘汰之。在這遍掃描中不改變訪問位之。在這遍掃描中不改變訪問位A A。第二步，如果第一步失敗，則開始第二遍掃描，第二步，如果第一步失敗，則開始第二遍掃描，尋找尋找A=0A=0且且M=1M=1的頁面，將所遇到的第一個這樣的的頁面，將所遇到的第一個這樣的頁面作為淘汰頁，在此遍掃描中將所有經(jīng)過的頁頁面作為淘汰頁，在此遍掃描中將所有經(jīng)過的頁面的訪問位置為面的訪問位置為0 0。第三步，如果第二步也沒有找到所要淘汰的頁面，第三步，如果第二步也沒有找到所要淘汰的頁面，則將指針返回到開始的位置，并將所有頁面的訪則將指針返回到開始的位置，并將所有頁面的訪問位

38、置為問位置為0 0。然后重復(fù)第一步。然后重復(fù)第一步。9 9、缺頁中斷率、缺頁中斷率 假定，出現(xiàn)缺頁的概率為假定，出現(xiàn)缺頁的概率為p p，主存的有效訪問時間為，主存的有效訪問時間為MAMA，則，則頁式虛擬存儲管理的有效訪問時間：頁式虛擬存儲管理的有效訪問時間： 有效訪問時間有效訪問時間 = = （1 1p p）MAMAp p缺頁中斷時間缺頁中斷時間其中，缺頁中斷時間主要由三部分組成：其中，缺頁中斷時間主要由三部分組成：q缺頁中斷服務(wù)時間缺頁中斷服務(wù)時間q將缺頁讀入的時間將缺頁讀入的時間q作業(yè)重新執(zhí)行時間作業(yè)重新執(zhí)行時間 可見，有效訪問時間正比于缺頁率?？梢?，有效訪問時間正比于缺頁率。 影響缺頁中

39、斷率的因素：影響缺頁中斷率的因素： 分配給作業(yè)的的物理塊數(shù)：一般地說，分配給作業(yè)的物理塊數(shù)越分配給作業(yè)的的物理塊數(shù)：一般地說，分配給作業(yè)的物理塊數(shù)越多，則缺頁中斷率越低；多，則缺頁中斷率越低；頁面的大?。喉撁嬖酱螅b入頁面的信息量就越多，越可能降低頁面的大小：頁面越大，裝入頁面的信息量就越多，越可能降低缺頁中斷率；缺頁中斷率；程序的編制方法：程序編制的方法不同，對缺頁中斷的次數(shù)有很程序的編制方法：程序編制的方法不同，對缺頁中斷的次數(shù)有很大的影響；大的影響；頁面的調(diào)度算法：頁面的調(diào)度算法對缺頁中斷率的影響也很大。頁面的調(diào)度算法：頁面的調(diào)度算法對缺頁中斷率的影響也很大。 例子：例子： 設(shè)有二維數(shù)組設(shè)有二維數(shù)組 Var A: array1128 of array1128 of integer;在一個頁式虛擬存儲系統(tǒng)中，采用在一個頁式虛擬存儲系統(tǒng)中，采用LRULRU頁面淘汰算法，頁面淘汰算法，一個進程有一個進程有2 2頁內(nèi)存空間，每頁可以存放頁內(nèi)存空間，每頁可以存放128128個整數(shù)。個整數(shù)。其中第一頁存放程序，且假定程序已經(jīng)在內(nèi)存。請分其中第一頁存放程序，且假定程序已經(jīng)在內(nèi)存。請分別就下面程序別就下面程序A A和和B B的執(zhí)行過程計算缺頁次數(shù)。的執(zhí)行過程計算缺頁次數(shù)。 程序程序Afor i:=1 to 128 do for j:=1 to 128 do