《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理

第四章存儲(chǔ)管理頁(yè)式存儲(chǔ)管理頁(yè)式虛擬存儲(chǔ)技術(shù)段式存儲(chǔ)管理《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理分區(qū)存儲(chǔ)管理的缺點(diǎn)“碎片”問(wèn)題原因：作業(yè)要求連續(xù)的存儲(chǔ)空間。解決辦法：允許作業(yè)占據(jù)不連續(xù)的空間?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理基本原理“等分”內(nèi)存。把內(nèi)存劃分為大小相同的“塊”。把用戶作業(yè)空間劃分為大小相同的“頁(yè)”。頁(yè)和塊的大小相同。在把作業(yè)加載到內(nèi)存時(shí)，頁(yè)和頁(yè)之間不再連續(xù)。但頁(yè)內(nèi)連續(xù)。也不必把所有的頁(yè)都一次性加載內(nèi)存，只需要加載那些馬上要用到的頁(yè)。其余的頁(yè)在需要時(shí)再加載?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理地址變換邏輯地址：頁(yè)號(hào)+頁(yè)內(nèi)地址如何轉(zhuǎn)變?yōu)閮?nèi)存物理地址？考慮：物理地址=塊號(hào)*塊長(zhǎng)度+塊內(nèi)地址塊長(zhǎng)度一定，塊內(nèi)地地址與頁(yè)內(nèi)地址相同。問(wèn)題變?yōu)椋喝绾胃鶕?jù)頁(yè)號(hào)得到塊號(hào)？頁(yè)表：頁(yè)號(hào)頁(yè)內(nèi)地址《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理頁(yè)表《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理地址變換過(guò)程1、根據(jù)頁(yè)號(hào)查頁(yè)表，得到塊號(hào)。2、根據(jù)塊號(hào)和頁(yè)內(nèi)地址計(jì)算物理地址。3、例題：《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理例題：在分頁(yè)存儲(chǔ)管理系統(tǒng)中，用戶編程空間共32個(gè)頁(yè)，每頁(yè)大小為1024B，內(nèi)存為16KB。假定某一時(shí)刻用戶頁(yè)表如下，若邏輯地址為035E（H），求其所對(duì)應(yīng)的物理地址。頁(yè)號(hào)物理塊號(hào)

0 5 1 10 2 3 3 7分析：（1）根據(jù)題意，頁(yè)內(nèi)地址為10位，頁(yè)號(hào)為5位。

210=1024，25=32

（2）根據(jù)給定的邏輯地址得到頁(yè)號(hào)和頁(yè)內(nèi)地址。

035E（H）=（11110）2

從左邊數(shù)10位為頁(yè)內(nèi)地址，剩余為頁(yè)號(hào)。頁(yè)號(hào)為0。（3）根據(jù)頁(yè)號(hào)查頁(yè)表，得到塊號(hào)為5。（4）將塊號(hào)與塊內(nèi)地址組合為物理地址：

110=175E（H） 《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理頁(yè)表的實(shí)現(xiàn)—快表從上述地址變換過(guò)程可以看出：CPU每取一條指令或數(shù)據(jù)，都必須經(jīng)過(guò)頁(yè)表。因此，頁(yè)表的每一個(gè)表項(xiàng)都是一個(gè)動(dòng)態(tài)重定位機(jī)構(gòu)。如何實(shí)現(xiàn)頁(yè)表，將影響系統(tǒng)的效率。方式：硬件實(shí)現(xiàn)：用寄存器組。但代價(jià)太高，特別是內(nèi)存很大時(shí)，是不可能的。軟件實(shí)現(xiàn)：將頁(yè)表放在內(nèi)存中。每取一條指令，要兩次訪問(wèn)內(nèi)存?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理快表軟硬件結(jié)合：將頁(yè)表中使用最頻繁的表項(xiàng)（頁(yè)表的的一個(gè)子集）放在cache中。稱為“快表”。cache也稱為“聯(lián)想寄存器”，它不是根據(jù)地址而是根據(jù)所存信息的全部特征或部分特征進(jìn)行存取。在這里為頁(yè)號(hào)。若要訪問(wèn)的頁(yè)在cache中，則只需一次訪問(wèn)內(nèi)存。若不在，則到內(nèi)存中去找，同時(shí)把新的頁(yè)表表項(xiàng)寫(xiě)入cache?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理例題：對(duì)于利用快表且頁(yè)表存于內(nèi)存的分頁(yè)系統(tǒng)，假定CPU的一次訪問(wèn)內(nèi)存時(shí)間為1μs，訪問(wèn)快表時(shí)間忽略不計(jì)。如果85%的地址映射可直接通過(guò)快表完成，那么進(jìn)程完成一次內(nèi)存讀寫(xiě)的平均有效時(shí)間是多少？分析：（1）若直接通過(guò)快表完成，則只需一次訪問(wèn)內(nèi)存。（2）若不能，則需要兩次訪問(wèn)內(nèi)存。（3）平均時(shí)間=1*85%+2*15%《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理內(nèi)存分配用戶需求：需要多少塊？?jī)?nèi)存空閑塊的管理：位示圖。位示圖：在內(nèi)存中劃出一片區(qū)域，用一位代表一個(gè)塊，該位的值表示所代表的塊的狀態(tài)：

0：空閑；1：已分配?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理內(nèi)存分配塊號(hào)與字號(hào)、字長(zhǎng)的關(guān)系：系統(tǒng)的字長(zhǎng)一定，內(nèi)存塊從0開(kāi)始編號(hào)，則有：塊號(hào)=字號(hào)*字長(zhǎng)+位號(hào)字號(hào)=[塊號(hào)/字長(zhǎng)]（取整的意思）位號(hào)=塊號(hào)MOD字長(zhǎng)《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理用戶作業(yè)請(qǐng)求：塊數(shù)B掃描位示圖，查找為0的位空閑塊數(shù)

BN無(wú)法分配計(jì)算塊號(hào)建立頁(yè)表《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理頁(yè)式系統(tǒng)的內(nèi)存保護(hù)和共享保護(hù)：在頁(yè)表上添加一個(gè)保護(hù)位。在做地址變換時(shí)，檢查對(duì)頁(yè)面的訪問(wèn)是否合法。共享：根據(jù)地址轉(zhuǎn)換過(guò)程可知：如果在不同用戶的頁(yè)表中填上相同的頁(yè)表表項(xiàng)（塊號(hào)），就能夠訪問(wèn)相同的內(nèi)存空間?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理塊號(hào)保護(hù)位5R12WR555用戶1用戶2用戶355《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理頁(yè)式虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)器：內(nèi)存擴(kuò)充技術(shù)，為用戶提供一個(gè)比實(shí)際內(nèi)存大得多的內(nèi)存空間。實(shí)現(xiàn)虛擬的三個(gè)三個(gè)條件；程序中的哪些頁(yè)已經(jīng)加載內(nèi)存。當(dāng)要訪問(wèn)的頁(yè)不在內(nèi)存時(shí)，如何將其掉如內(nèi)存？若此時(shí)內(nèi)存空間已滿，如何選擇換出的頁(yè)？頁(yè)式虛擬的基本原理：加載作業(yè)時(shí)，只加載那些最活躍的頁(yè)，其余的頁(yè)需要時(shí)再加載。“請(qǐng)求調(diào)頁(yè)技術(shù)”和“預(yù)調(diào)頁(yè)技術(shù)”。《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理一、如何知道哪些已在內(nèi)存在頁(yè)表中添加一個(gè)標(biāo)志位（中斷位），標(biāo)志該頁(yè)是否已在內(nèi)存：0：不在

1：在內(nèi)存塊號(hào)保護(hù)位標(biāo)志位《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理當(dāng)要訪問(wèn)的頁(yè)不在內(nèi)存時(shí)發(fā)生“缺頁(yè)中斷”。缺頁(yè)中斷的處理過(guò)程：保存現(xiàn)場(chǎng)在內(nèi)存中找到一個(gè)空閑塊。從磁盤(pán)上找到要調(diào)入的頁(yè)。讀磁盤(pán)到內(nèi)存?；謴?fù)現(xiàn)場(chǎng)。重新調(diào)度運(yùn)行。《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理在調(diào)入內(nèi)存時(shí)，若內(nèi)存已滿進(jìn)行“頁(yè)面替換”：從內(nèi)存中選擇一個(gè)頁(yè)調(diào)出內(nèi)存，為新調(diào)入的頁(yè)讓出空間。如果替換的不合適，則發(fā)生“抖動(dòng)”或“顛簸”現(xiàn)象：頁(yè)在內(nèi)外存之間頻繁地調(diào)入調(diào)出，系統(tǒng)開(kāi)銷很大。頁(yè)面替換算法：先進(jìn)先出法（FIFO）：將最先調(diào)入內(nèi)存的頁(yè)調(diào)出內(nèi)存。最近最少使用算法（LRU：leastrecentlyused）。將最近一段時(shí)間內(nèi)沒(méi)有用過(guò)的頁(yè)調(diào)出內(nèi)存?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理頁(yè)面替換算法最近最少使用算法（LFU）：最近一段時(shí)間內(nèi)使用次數(shù)最少的頁(yè)調(diào)出內(nèi)存。為每一個(gè)在內(nèi)存的頁(yè)設(shè)置一個(gè)計(jì)數(shù)器，選擇計(jì)數(shù)器中的值最小的調(diào)出。最優(yōu)算法（OPT）：把將來(lái)一段時(shí)間內(nèi)被使用的可能性最小的頁(yè)調(diào)出內(nèi)存。利用預(yù)測(cè)方法先來(lái)預(yù)測(cè)將來(lái)的使用情況。注意：LRU、LFU之間的區(qū)別?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理例題：有一個(gè)分頁(yè)式虛擬存儲(chǔ)管理系統(tǒng)，每個(gè)進(jìn)程在內(nèi)存有3頁(yè)數(shù)據(jù)區(qū)、1頁(yè)程序區(qū)，剛開(kāi)始時(shí)數(shù)據(jù)區(qū)為空?，F(xiàn)有一個(gè)進(jìn)程有以下訪問(wèn)序列：

1，5，4，1，2，3，2，1，5，4，2，4，3，5，1若系統(tǒng)采用：（1）最近最少使用（LRU）淘汰算法（2）先進(jìn)先出（FIFO）淘汰算法請(qǐng)計(jì)算缺頁(yè)次數(shù)和發(fā)生缺頁(yè)中斷后的淘汰頁(yè)號(hào)。分析：（1）采用FIFO方法：將內(nèi)存中的頁(yè)按進(jìn)入的先后次序排隊(duì)，后來(lái)的加入隊(duì)尾，先來(lái)的先出去?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理（1）FIFO算法訪問(wèn)隊(duì)列：154123215424351

154423315422351內(nèi)存155422315442351154423155423缺頁(yè)中斷

頁(yè)面替換154231543答案：缺頁(yè)中斷的次數(shù)為12次，頁(yè)面替換的次序是：154231543?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理（2）LRU算法：訪問(wèn)隊(duì)列：154123215424351

154423335422351內(nèi)存155122215442351141112155443缺頁(yè)中斷

頁(yè)面替換54321524答案：缺頁(yè)中斷的次數(shù)為11次，頁(yè)面替換的次序是：54321524《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理工作集模型虛擬存儲(chǔ)技術(shù)的理論基礎(chǔ)。局部性原理：進(jìn)程往往會(huì)不均勻地高度局部化地訪問(wèn)內(nèi)存。

時(shí)間局部性：剛剛被訪問(wèn)的頁(yè)，很可能在不久的將來(lái)還要訪問(wèn)。例如：循環(huán)；子程序；棧；用戶記數(shù)和總計(jì)的變量等。

空間局部性：某個(gè)頁(yè)面被訪問(wèn)，很可能它相臨的頁(yè)也要被訪問(wèn)。例如：數(shù)組遍歷；代碼程序的執(zhí)行；等等。工作集：進(jìn)程活躍地訪問(wèn)的頁(yè)面的集合?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理工作集模型（續(xù)）工作集存儲(chǔ)管理策略力求把活躍程序的工作集保存在內(nèi)存中。從上圖可以看出：僅當(dāng)一個(gè)進(jìn)程的全部工作集都在內(nèi)存時(shí)才能運(yùn)行該作業(yè)。hW(h)h0《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理頁(yè)式存儲(chǔ)管理的缺陷

從理論上講，不同用戶共享程序段或數(shù)據(jù)很簡(jiǎn)單，只需在不同用戶的頁(yè)表中填上相同的塊號(hào)，經(jīng)地址變換后，一定能訪問(wèn)相同的內(nèi)存空間。但是，由于頁(yè)的劃分是由系統(tǒng)自動(dòng)進(jìn)行的，很可能用戶要共享的頁(yè)分布在不同的頁(yè)中，給共享和保護(hù)造成了麻煩?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理段式存儲(chǔ)管理用戶程序觀點(diǎn)：一個(gè)程序由若干程序段組成，每一個(gè)段具有相對(duì)獨(dú)立的功能。段的概念：一個(gè)邏輯意義完整的信息單位。一個(gè)程序由若干個(gè)段組成。各段長(zhǎng)度不同。段式存儲(chǔ)管理的原理：作業(yè)的地址空間由若干個(gè)邏輯分段組成，每個(gè)分段有自己的名字，在內(nèi)存中占據(jù)一個(gè)連續(xù)的區(qū)域。但是段和段之間可以是不連續(xù)的。

思考：采用什么策略為段分配內(nèi)存？《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理地址變換邏輯地址：段號(hào)+段內(nèi)地址注意：該邏輯地址是二維地址。因?yàn)槎卧趦?nèi)存中占據(jù)一個(gè)連續(xù)的區(qū)域，如果知道該段在內(nèi)存中的起始地址，就可以得到物理地址：物理地址=起始地址+段內(nèi)地址段表：段號(hào)起始地址長(zhǎng)度《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理地址變換的過(guò)程1、硬件支持：段表基址寄存器和段表長(zhǎng)度寄存器。因?yàn)槎伪硎潜４嬖趦?nèi)存中的。2、步驟：（1）檢查段號(hào)是否：段號(hào)段表長(zhǎng)度寄存器若否，則產(chǎn)生“地址越界”中斷。（2）根據(jù)段號(hào)和段表基址寄存器的值取段表表項(xiàng)，得到段基址和段長(zhǎng)度。（3）判斷段內(nèi)地址是否越界：段內(nèi)地址段長(zhǎng)度。（4）物理地址=基址+段內(nèi)地址《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理段的共享和保護(hù)共享：在不同用戶的段表中添入相同的段表表項(xiàng)。保護(hù)：在段表中添加一個(gè)保護(hù)位。思考：為什么段式存儲(chǔ)管理比頁(yè)式存儲(chǔ)管理更容易實(shí)現(xiàn)共享和保護(hù)？《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理段式和頁(yè)式的問(wèn)題和優(yōu)點(diǎn)頁(yè)式：解決了碎片問(wèn)題。但不便于用戶作業(yè)的共享和保護(hù)。由于用戶調(diào)入的頁(yè)可能只用到其中的一部分，因此系統(tǒng)的效率不高。段式：很好地解決了共享和保護(hù)問(wèn)題，系統(tǒng)效率高；但由于采用可變分區(qū)方式為段分配內(nèi)存，存在碎片問(wèn)題。《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理也稱為“混合式存儲(chǔ)管理”，將頁(yè)式和段式的優(yōu)點(diǎn)結(jié)合起來(lái)。原理：程序先分段，段內(nèi)再分頁(yè)。每個(gè)段在內(nèi)存中擁有一個(gè)頁(yè)表。用戶看到的是段，即共享時(shí)采用段。內(nèi)存管理采用頁(yè)，因此消除了碎片?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理地址變換邏輯地址：段號(hào)+頁(yè)號(hào)+頁(yè)內(nèi)地址段表：段號(hào)頁(yè)表起始地址頁(yè)表：頁(yè)號(hào)塊號(hào)注意：每一個(gè)段都有一個(gè)頁(yè)表。硬件支持：段表基址寄存器和段表長(zhǎng)度寄存器。段號(hào)頁(yè)號(hào)頁(yè)內(nèi)地址《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理本章小結(jié)—內(nèi)存管理功能內(nèi)存的分配和回收地址變換內(nèi)存共享與保護(hù)虛擬存儲(chǔ)器任何一種管理策略，都需要解決上述問(wèn)題。解決上述問(wèn)題的方法，就是存儲(chǔ)管理的內(nèi)容?！恫僮飨到y(tǒng)》(五)頁(yè)式存儲(chǔ)管理本章小結(jié)—內(nèi)存管理技術(shù)單道連續(xù)存儲(chǔ)管理分區(qū)存儲(chǔ)管理固定分區(qū)存儲(chǔ)管理可變分區(qū)存儲(chǔ)管理頁(yè)式存儲(chǔ)管理段式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理《操作系統(tǒng)》(五)頁(yè)式存儲(chǔ)管理課后練習(xí)1、在一個(gè)分頁(yè)式虛擬存儲(chǔ)管理系統(tǒng)中，每個(gè)進(jìn)程在內(nèi)存中有3個(gè)數(shù)據(jù)區(qū)，2個(gè)程序區(qū)?，F(xiàn)有一進(jìn)程，其數(shù)據(jù)的第1、2，3頁(yè)已裝入內(nèi)存。現(xiàn)有一個(gè)訪問(wèn)序列：1、3、