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