【正文】 根據(jù)需求將需要的頁面調(diào)入內(nèi)存中的工作方式稱為請調(diào)； 訪問局部性：進程對頁面訪問的局部性，而且對于所有進程都有此特性； 工作集：一個進程當(dāng)前使用的頁的集合叫做此進程的工作集。 顛簸： 進程執(zhí)行過程當(dāng)中，一個隔幾個指令就發(fā)生一次頁面故障的程序稱為在顛簸。 指令執(zhí)行通常需幾個納秒，讀入頁面一般需要幾十毫秒。 進程在換出內(nèi)存然后又被調(diào)入，這樣的過程使得系統(tǒng)的性能花費在頁面的移動上，由于每次裝入的請調(diào)策略，使得開始執(zhí)行的時候程序顛簸很厲害，故利用工作集的方法來解決這個問題。 在一個進程運行之前就預(yù)先裝入它的頁面（工作集，這種方法稱為 工作集模型 ，這種技術(shù)也稱為 預(yù)先調(diào)入 （ prepaging）。 局部與全局分配策略 一直討論的是某一個進程發(fā)生缺頁故障，而實際上內(nèi)存中存在的是多個進程的頁面，當(dāng)其中某個進程發(fā)生缺頁故障的時候，實際的替換應(yīng)該有很多種方法，即涉及到了對某個進程的頁面替換還是對整個內(nèi)存中頁面的替換的問題。 對于某個進程發(fā)生了缺頁故障，替換頁面時只從此進程擁有的頁面中淘汰的方法叫做局部頁面替換策略（其實對應(yīng)的是在內(nèi)存中為每個進程分配了固定的內(nèi)存片斷）；從內(nèi)存中只關(guān)心頁面的年齡來進行淘汰的方法叫做全局頁面替換策略（其實對應(yīng)于每個進程的頁框數(shù)是可以變化的）。 Original configuration Local page replacement Global page replacement 局部與全局的優(yōu)劣性的比較： 一般來說，全局比局部較優(yōu) 局部：當(dāng)內(nèi)存中有空頁框的時候，仍然在自己固定的段內(nèi)替換，會導(dǎo)致很高缺頁率；工作集增大，顛簸變大，工作集變小，內(nèi)存又會被浪費。 全局：系統(tǒng)需要不斷確定該給不同的進程多少頁框，但是由于工作集變化的過快，跟蹤年齡位也很難實現(xiàn)?？梢远ㄆ跒楫?dāng)前進程平均分配同等頁框，但進程的大小不同，這種分配仍不合理；也可按照進程大小來分配；或者為每個進程規(guī)定最小頁框數(shù)，這樣可保證每個進程都可以執(zhí)行。 無論何種方案都是為了減少顛簸，因此需要將顛簸直接控制，可使用缺頁率 PFF算法（ page fault frequency）：控制分配集的大小，什么時候應(yīng)該增加，什么時候應(yīng)該減少分配給進程的物理頁面數(shù)。 A表示故障率過高， B表示故障率過低，過高表示頁框太少，需要增加分配；過低表示頁框過多，需要減少頁框。 頁面大小 頁面大小的選擇，會影響內(nèi)存的利用率。 內(nèi)零頭的產(chǎn)生：由于分頁存儲，且頁面有大小，當(dāng)一個頁被寫入了數(shù)據(jù)，就認為此頁被使用了，別的進程就不會再來用這個頁面，因此，就產(chǎn)生了內(nèi)碎片，且平均大小為 段數(shù) 頁面大小 /2。 Eg：一個程序被分為八個部分執(zhí)行，每部分需要4k的內(nèi)存。頁面大小為 32k時，就分配了 32k，16k時就分配了 16k， 4k時就分配了 4k。頁面過大，浪費即越大。過小的話，頁表就變得龐大，裝入時就使大量時間花在了尋道上，每次裝入頁面就耗費大量的時間。 頁表大小的選擇： 設(shè)平均進程大小為 s字節(jié)，頁面大小是 p字節(jié)，每個頁表項需要 e字節(jié)，則進程需要頁數(shù)大約是 s/p，占用的頁表空間是 se/p，由于內(nèi)碎片的存在，故總的內(nèi)存開銷為： se/p＋ p/2，通過求導(dǎo)，得到 － se/p ＋ 1/2＝ 0 p= 2se 故根據(jù) s和 e的大小，就可以得到最優(yōu)頁面的大小，但這個大小實際應(yīng)用中可以調(diào)整。 2 分段 段式虛擬存儲器，允許程序員把存儲器看成多個地址空間或段組成，段的大小不等，且是動態(tài)變化的，通過分段就把原來一維的組織方式改變了，使得數(shù)據(jù)的組織更加具有邏輯性。 例如，編譯程序在編譯過程中會建立許多表格：源文本、符號表等。 當(dāng)各個部分在一維空間中增長的時候，會進入到鄰接塊中，而且某一部分會增長迅速，填滿自己的空間，而其他部分仍有大量空余空間。 這時在機器上提供多個相互獨立的地址空間 —— 段 ，且段的長度會動態(tài)改變 ，這樣就可以將上圖改成下圖的方式： 符號表 源正文 常量 語法樹 調(diào)用棧 用戶程序劃分 按程序自身的邏輯關(guān)系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段也從 0開始編址，段內(nèi)地址是連續(xù)的。 段號 段內(nèi)地址 邏輯地址 . . . 0 S 工作區(qū)段 [B] 主程序段 [M] . . . . . . 0 E P 子程序段 [X] 0 K . . . CALL [X] [E] . . . . . . . . . CALL [Y] [F] CALL [A] 116 數(shù)組 [A] 12345 . . . B 0 S A 0 N Y 0 L X 0 P M 0 K 邏輯段號 0 1 2 3 4 作業(yè) 1的地址空間 1000 3200 5000 6000 8000 P K S L N 主存 K 3200 P 1500 L 6000 N 8000 S 5000 長度 段地址 0 1 2 3 4 操作系統(tǒng) 段的特點： ? 段的長度可以在運行期間進行改變，堆棧段的長度可以隨著數(shù)據(jù)的壓入進行增長，數(shù)據(jù)彈出時也同樣減小。 ? 段是邏輯實體，并為程序員所知，段可以容納一個過程或者一些數(shù)值變量，但每個段中的數(shù)據(jù)都相對單一。 ? 段是邏輯實體，每部分的內(nèi)容都相對單一，因此可以對不同的段進行不同的控制，如，某些段內(nèi)容只許讀，另一部分段內(nèi)容只許執(zhí)行等等。 段的特點： ? 分段便于單獨進行編譯、鏈接，也同樣便于修改，且重新編譯時只需要編譯需要修改的過程即可，不相關(guān)的過程也不會受到影響，也不要進行重新編譯，因此總的開銷也會變得很小。 ? 共享庫的使用：由于段的實現(xiàn)，可以使多個進程共享同一部分數(shù)據(jù)或過程，節(jié)省了地址空間 。 純分段系統(tǒng)的實現(xiàn) 分段和分頁的根本差別就是頁定長而段非定長，所以系統(tǒng)在運行了一段時間以后，內(nèi)存便變得混亂，被分為了很多塊，有的是段，有的是空洞，我們稱這種現(xiàn)象為跳棋盤或外碎片，由于空洞浪費了內(nèi)存，故需要通過緊縮來解決。 段 0（ 4k） 段 1（ 8k） 段 2（ 5k） 段 3（ 8k） 段 4（ 7k） 段 0（ 4k） 段 3（ 8k） 段 4（ 7k） 段 2（ 5k） 段 7（ 5k） （ 3k） 段 0（ 4k） 段 3（ 8k） 段 2（ 5k） （ 3k） 段 7（ 5k） 段 5（ 4k） （ 3k） 段 0（ 4k） 段 2（ 5k） （ 3k） （ 3k） （ 4k） 段 6（ 4k） 段 7（ 5k） 段 5（ 4k） 段 0（ 4k） 段 7（ 5k） 段 2（ 5k） 段 6（ 4k） 段 5（ 4k） （ 10k） a b c d e 分段和分頁結(jié)合 當(dāng)段變得大的時候，我們也遇到了分頁里的問題，即無法將整個段裝入內(nèi)存，因此又可以把這個段進行分頁，每次把真正需要的頁調(diào)入內(nèi)存。 分頁與分段的實例： MULTICS 為了實現(xiàn)分頁和分段的共同的優(yōu)點： 分頁：統(tǒng)一的頁面大小，只用段的一部分時，并不用全部調(diào)入內(nèi)存； 分段：易于編程、模塊化、保護和共享。 每個 MULTICS程序都有一個段表，每個段對應(yīng)一個段描述符，因為段表可能會很大，所以段表自己也是一個段并被分頁，段描述符包含段是否在內(nèi)存的標志， 18 9 1 1 1 3 3 頁表的主存地址 段長度（以頁為單位） 頁長： 0＝ 1024字， 1＝ 64 字 0＝本段分頁， 1＝本段不分頁 其他位 保護位 段描述符 MULTICS的地址由兩部分組成：段和段內(nèi)地址 進行內(nèi)存訪問時，執(zhí)行的算法是： ； ，如果在，就找到位置，如果不在，就發(fā)出段故障，如果違反保護要求就發(fā)出故障； ，頁面不在內(nèi)存就發(fā)出一個頁面故障，否則就從頁表項中取出此頁在主存中的起始地址； ； 。