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

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

210=1024，25=32

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

035E（H）=（11110）2

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

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

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

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

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

1，5，4，1，2，3，2，1，5，4，2，4，3，5，1若系統(tǒng)采用：（1）最近最少使用（LRU）淘汰算法（2）先進先出（FIFO）淘汰算法請計算缺頁次數(shù)和發(fā)生缺頁中斷后的淘汰頁號。分析：（1）采用FIFO方法：將內(nèi)存中的頁按進入的先后次序排隊，后來的加入隊尾，先來的先出去。《操作系統(tǒng)》(五)頁式存儲管理（1）FIFO算法訪問隊列：154123215424351

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

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

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

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

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

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

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

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