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

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

0 5 1 10 2 3 3 7分析：（1）根據題意，頁內地址為10位，頁號為5位。

210=1024，25=32

（2）根據給定的邏輯地址得到頁號和頁內地址。

035E（H）=（11110）2

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

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

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

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

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

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

154423315422351內存155422315442351154423155423缺頁中斷

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

154423335422351內存155122215442351141112155443缺頁中斷

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

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

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

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

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