操作系統(tǒng)精美版2013os8章內(nèi)存管理

第8章內(nèi)存管理8.1背景8.2交換8.3連續(xù)內(nèi)存分配8.4分頁8.5頁表結(jié)構(gòu)8.6分段8.7實例：IntelPentium8.1背景P236※為了解決CPU和存儲器之間速度上的不匹配，存儲系統(tǒng)分為三級存儲結(jié)構(gòu)快，貴，小主存地址，字節(jié)，統(tǒng)一編址存放CPU頻繁訪問的數(shù)據(jù)外存，輔存，慢，大頻繁訪問的磁盤數(shù)據(jù)放內(nèi)存貴小快存儲管理設(shè)備管理增加：存儲管理的主要任務(wù)存儲管理的4個主要任務(wù)：(1)支持多道程序并發(fā)，互不干擾的共享存儲資源(2)方便用戶，減少用戶對存儲器的管理(3)提高存儲器的利用率和系統(tǒng)吞吐量(4)從邏輯上擴充內(nèi)存空間，支持大程序能在小的內(nèi)存空間運行或允許更多的進程并發(fā)執(zhí)行。(虛擬存儲)增加：存儲管理的主要功能存儲管理的6個主要功能：1.存儲空間的分配和回收2.地址轉(zhuǎn)換邏輯地址轉(zhuǎn)換為物理地址的過程稱作重定位或地址映射

2種重定位方式

(1)靜態(tài)重定位(2)動態(tài)重定位3.主存空間的共享4.主存空間的保護(避免相互干擾)5.主存儲空間的擴充(虛擬存儲邏輯上擴充內(nèi)存容量)6.交換（內(nèi)外存交換）8.1.1基本硬件程序必須調(diào)入內(nèi)存才可運行完全調(diào)入，部分調(diào)入內(nèi)存中有2個區(qū)域操作系統(tǒng)區(qū)域（常駐內(nèi)存）一般在內(nèi)存低地址端，因為中斷向量在低地址用戶進程區(qū)域每個進程都有自己獨立的內(nèi)存空間通過基地址寄存器和界限寄存器來確定合法的內(nèi)存地址（內(nèi)存保護）P236圖8.1

基地址寄存器和界限寄存器定義的邏輯地址空間操作系統(tǒng)進程進程進程基地址界限P236P237圖8.2

采用基地址寄存器和界限寄存器的硬件地址保護地址基地址基地址＋界限地址操作系統(tǒng)監(jiān)視器陷阱——尋址錯誤內(nèi)存P2378.1.2地址綁定進程的程序和數(shù)據(jù)必須調(diào)入內(nèi)存才可運行在磁盤上等待調(diào)入內(nèi)存的進程形成輸入隊列用戶程序在運行之前需要經(jīng)歷若干步驟（見下一頁）。在這些步驟中，地址可能有不同的表示形式符號（源程序中）可重定位的地址（目標模塊）絕對地址（內(nèi)存映像）運行前需要得到內(nèi)存的物理地址(絕對地址)P238圖8.3一個用戶程序的多步驟處理源程序編譯器和匯編器編譯時間加載時間執(zhí)行時間其它目標模塊目標模塊鏈接器加載模塊系統(tǒng)庫加載器動態(tài)鏈接的系統(tǒng)庫動態(tài)鏈接二進制內(nèi)存鏡像3種地址綁定方式：編譯時：編譯時生成絕對地址(MS-Dos的文件)

加載時：裝入/加載時，相對地址變換為絕對地址(靜態(tài)重定位)

運行時：運行時動態(tài)鏈接，程序執(zhí)行時，相對地址變換為絕對地址（動態(tài)重定位）P238增加：程序的編譯、鏈接、裝入和運行1.編輯階段：使用某種編輯軟件，編輯源程序文件，如file1.c2.編譯階段：將初始的文本文件(file1.c)變成CPU可以識別的一系列二進制代碼文件(file1.o)3.鏈接階段：將編譯后得到的一組目標模塊以及它們所需的庫函數(shù)裝配成一個完整的裝入模塊3種鏈接方式：

靜態(tài)鏈接

裝入時動態(tài)鏈接運行時動態(tài)鏈接4.裝入階段：用戶程序裝入內(nèi)存（要進行重新定位）相對地址→絕對地址5.運行階段：經(jīng)調(diào)度程序調(diào)度，進入CPU運行8.1.3邏輯地址與物理地址空間邏輯地址：由CPU生成；也稱為虛擬地址(用戶永遠只能看到邏輯地址)物理地址：內(nèi)存單元所看到的地址(內(nèi)存中的實際存放地址)地址映射：運行時邏輯地址到物理地址的映射由內(nèi)存管理單元MMU完成(硬件)動態(tài)重定位：需要設(shè)置重定位寄存器(基址寄存器)P239圖8.4使用重定位寄存器的動態(tài)重定位邏輯地址重定位寄存器物理地址內(nèi)存內(nèi)存管理單元P2398.1.4動態(tài)加載一個子程序只有在調(diào)用時才被加載一般子程序庫采用動態(tài)加載優(yōu)點：更好的內(nèi)存空間利用率，不用的子程序不會被裝入內(nèi)存8.2交換交換：內(nèi)外存交換中級調(diào)度（換入，換出）滾進、滾出－根據(jù)進程的優(yōu)先級來交換滾出：高優(yōu)先級進程來了，換出低優(yōu)先級進程，以便裝入和執(zhí)行高優(yōu)先級的進程滾入：當(dāng)高優(yōu)先級進程執(zhí)行完，低優(yōu)先級進程可以換入內(nèi)存以繼續(xù)執(zhí)行。滾入滾出的交換策略本在許多系統(tǒng)中被采用。（如UNIX,Linux及Windows)交換時間與需要交換的內(nèi)存空間大小直接成正比。P241圖8.5使用磁盤作為備份存儲的兩個進程的交換操作系統(tǒng)用戶空間內(nèi)存進程P1進程P2換出換入備用存儲空間P241增加：儲存管理方式目的：1.提高存儲器的利用率2.提高系統(tǒng)吞吐量分配方式分類（3大類）：1.連續(xù)分配方式(分配連續(xù)內(nèi)存空間)

(1)單一連續(xù)分配方式

(2)分區(qū)式分配方式

a.固定分區(qū)分配方式

b.動態(tài)分區(qū)分配方式

c.可重定位分區(qū)分配方式2.離散分配方式(不要求連續(xù)內(nèi)存空間)(1)分頁存儲管理(2)分段存儲管理方式(3)段頁式存儲管理3.虛擬存儲系統(tǒng)(邏輯上擴充內(nèi)存容量)(1)請求分頁系統(tǒng)(2)請求分段系統(tǒng)(3)

請求段頁式系統(tǒng)8.3連續(xù)內(nèi)存分配連續(xù)分配方式(分配連續(xù)內(nèi)存空間)(1)單一連續(xù)分配方式（單分區(qū)分配）(2)分區(qū)式分配方式

a.固定分區(qū)分配方式

b.動態(tài)分區(qū)分配方式（可變分區(qū)）

c.可重定位分區(qū)分配方式（緊縮技術(shù)解決外碎片）8.3.1單一連續(xù)分配?

用于單用戶單任務(wù)操作系統(tǒng)?

內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)，操作系統(tǒng)用系統(tǒng)區(qū)，單用戶使用全部用戶區(qū)空間?

優(yōu)點：

不需要硬件支持，簡單?

缺點：單道，內(nèi)存浪費，CPU利用率低P244圖8.6重定位寄存器和界限地址寄存器的硬件支持邏輯地址物理地址界限地址寄存器重定位寄存器捕獲：地址錯誤P2448.3.2內(nèi)存分配?

把內(nèi)存分為一些大小相等或不等的多個區(qū)域，一旦劃分結(jié)束，則保持不變?

劃分分區(qū)的方法

(1)分區(qū)大小相等(無法裝入大進程，小進程有內(nèi)碎片，浪費空間)

(2)分區(qū)大小不等(多個小分區(qū)，適量中等分區(qū)，少量大分區(qū))?

內(nèi)存分配與回收

(1)數(shù)據(jù)結(jié)構(gòu)：分區(qū)說明表(按分區(qū)大小排隊)

(2)內(nèi)存分配和回收算法固定分區(qū)分配圖分區(qū)大小不等的固定分區(qū)示意圖分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)多個等待隊列單個等待隊列分區(qū)4分區(qū)3分區(qū)2分區(qū)1操作系統(tǒng)圖固定分區(qū)分配的分區(qū)說明表圖固定分區(qū)分配的內(nèi)存回收算法?

分配算法：見右圖?

回收算法：簡單(將分區(qū)狀態(tài)改為"未分配")動態(tài)分區(qū)分配（可變分區(qū)分配）?

動態(tài)分區(qū)分配(可變分區(qū)分配)：根據(jù)作業(yè)運行的實際需要，動態(tài)地為之分配內(nèi)存空間?

不預(yù)先設(shè)置分區(qū)的數(shù)目和大小，在作業(yè)裝入內(nèi)存時，根據(jù)實際情況確定分區(qū)數(shù)目和大小?

不存在內(nèi)碎片，可能有外碎片?

動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)：

(1)

空閑分區(qū)表

(2)空閑分區(qū)鏈圖可變分區(qū)分配的空閑分區(qū)表0K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表空空未分配30K80K未分配20K48K未分配23K15K標志長度始址空J410K110K空J312K68KJ210K38KJ115K0K標志長度始址分區(qū)分配表：分區(qū)分配表示意圖可變分區(qū)分配0K15K38K48K68K80K110K120K空閑區(qū)表已分配區(qū)表空空未分配12K98K未分配20K48K未分配23K15K標志長度始址J55K80KJ410K110KJ613K85KJ312K68KJ210K38KJ115K0K標志長度始址85K98K若有2個進程申請5K,13K空間空閑分區(qū)鏈動態(tài)分區(qū)分配算法■為把一個新作業(yè)裝入內(nèi)存，須按照一定的分配算法，從空閑分區(qū)表或空閑分區(qū)鏈中選出一個分區(qū)分配給該作業(yè)?！瞿壳俺Ｓ玫挠?種分配算法①首次/最先適應(yīng)算法(firstfit)②循環(huán)首次適應(yīng)算法(nextfit)(下次適應(yīng)算法)③最佳適應(yīng)算法(bestfit)④最壞適應(yīng)算法(worstfit)⑤快速適應(yīng)算法(quickfit)順序搜索法分類搜索法1.首次/最先適應(yīng)算法■要求：空閑分區(qū)表或鏈按起始地址遞增的次序排列■分配過程：1.從空閑分區(qū)表(鏈)首開始順序查找，找到第一個大于或等于所要求內(nèi)存長度的分區(qū)，則結(jié)束查找2.然后從該分區(qū)中劃出所要求的內(nèi)存長度分配給請求者，余下的空閑分區(qū)仍留在空閑分區(qū)表(鏈)中，并修改表(鏈)項■特點：1.優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū)，從而保留高地址部分的大空閑區(qū)2.由于低地址部分不斷被劃分，致使低地址端留下許多難以利用的小空閑分區(qū)(外碎片)3.每次查找都是從低地址部分開始，增加了查找可用空閑分區(qū)的開銷2.循環(huán)首次/下次適應(yīng)算法■類似首次適應(yīng)算法■不同之處：不再每次從空閑分區(qū)表(鏈)首開始查找，而是從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找■特點：1.使存儲空間的利用更加均衡2.減少了查找空閑分區(qū)的開銷3.但會導(dǎo)致缺乏大的空閑分區(qū)3.最佳適應(yīng)算法■要求：空閑分區(qū)按容量大小遞增的次序排列■查找：從空閑分區(qū)表(鏈)首開始順序查找，找到第一個大于或等于所要求內(nèi)存長度的分區(qū)，則結(jié)束查找（找到滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)）■特點：1.盡可能為作業(yè)選擇大小一致的空閑分區(qū)，從而保留大的空閑分區(qū)2.但空閑分區(qū)一般不可能正好和作業(yè)申請的內(nèi)存空間大小相等，因而將其分割成兩部分時致使留下許多難以利用的小空閑分區(qū)(外碎片)（宏觀上不一定最佳）4.最壞適應(yīng)算法■要求：空閑分區(qū)按容量大小遞減的次序排列■查找：查找第一個空閑分區(qū)，若不滿足，則分配失敗，否則分配■特點：1.總是挑選滿足作業(yè)要求的最大分區(qū)分配給作業(yè)，這樣使分給作業(yè)后剩下的空閑分區(qū)也比較大，能裝下其它作業(yè)（宏觀上不一定最壞）2.由于最大的空閑分區(qū)總是因首先分配而劃分，當(dāng)有大作業(yè)到來時，其存儲空間的申請往往得不到滿足5.快速適應(yīng)算法■要求：空閑分區(qū)按容量大小容量大小進行分類，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表（多個空閑分區(qū)鏈表，一個索引表）?！鋈萘看_定：一般為進程常用空間大小，如2KB,4KB,8KB等■分配：根據(jù)進程的長度，尋找到能容納它的最小空閑分區(qū)鏈表，取下第一塊分配即可■特點：1.分配時不用任何分割，能保留大的分區(qū)，也不存在碎片2.但歸還主存時算法復(fù)雜，系統(tǒng)開銷大，一個分區(qū)只屬于一個進程，非常浪費存儲空間動態(tài)分區(qū)分配流程u.size：作業(yè)請求的分區(qū)大小m.size：每個空閑分區(qū)的大小size：可再分配的最小分區(qū)大小動態(tài)分區(qū)回收■當(dāng)進程運行結(jié)束釋放內(nèi)存時，系統(tǒng)要回收已經(jīng)使用完畢的空閑區(qū)，并將其插入空閑分區(qū)表(鏈)。在將回收的空閑區(qū)插入空閑分區(qū)表(鏈)時，要考慮剩余空閑區(qū)的合并問題■有4種情況(問題：空閑區(qū)數(shù)目、首地址、大小如何改變)動態(tài)分區(qū)的分配和回收實例1.初始時只有一個分區(qū)2.按FIFO為進程ABCD分配內(nèi)存3.在某一時刻，進程C運行完后釋放內(nèi)存4.進程E(設(shè)需要內(nèi)存50K)和進程F(設(shè)需要內(nèi)存18K)，要求采用最先適應(yīng)算法為進程EF分配內(nèi)存5.進程BD完成后釋放內(nèi)存動態(tài)分區(qū)分配習(xí)題習(xí)題1：某系統(tǒng)主存容量為512KB,采用動態(tài)存儲區(qū)管理方式，某時刻t，主存中有3個空閑區(qū)，它們的首地址和大小分別為：空閑區(qū)1(30KB,100KB)，空閑區(qū)2(180KB,36KB)，空閑區(qū)3(260KB,60KB)(1)畫出t時刻內(nèi)存分布圖(2)用首次適應(yīng)算法和最佳適應(yīng)算法畫出t時刻空閑區(qū)的隊列結(jié)構(gòu)60KB第3塊36KB第2塊100KB第1塊30KB180KB260KB0512KB-1習(xí)題1(1)解答：動態(tài)分區(qū)分配習(xí)題習(xí)題1(2)解答：首次適應(yīng)算法，鏈表按地址從低到高排列∧60KB0180KB100KB0260KB36KB030KB隊列指針空閑區(qū)標志位空閑區(qū)大小下一空閑區(qū)地址動態(tài)分區(qū)分配習(xí)題習(xí)題1(2)解答：最佳適應(yīng)算法，鏈表按容量從小到大排列∧100KB0260KB36KB030KB60KB0180KB隊列指針動態(tài)分區(qū)分配習(xí)題習(xí)題2：某操作系統(tǒng)采用可變分區(qū)存儲管理，用戶區(qū)主存512KB，自由區(qū)有可用分區(qū)表管理，若分配時采用分配自由區(qū)的低地址部分，假設(shè)初始時全為空，對于下述申請次序：req(300KB),req(100KB),release(300KB),req(150KB),req(30KB),req(40KB),req(60KB)，回答下列問題(1)采用首次適應(yīng)算法FF，自由空區(qū)中有哪些空塊（給出地址，大小）(2)若采用最佳適應(yīng)算法BF，回答(1)中問題(3)若采用最壞適應(yīng)算法BF，回答(1)中問題(4)如果再申請90KB，針對(1)(2)(3)各有什么結(jié)果動態(tài)分區(qū)分配習(xí)題習(xí)題3：用可變分區(qū)管理主存時，假定主存中按地址順序依次有5個空閑區(qū)，空閑區(qū)的大小依次為32KB,10KB,8KB,228KB,100KB，現(xiàn)有5個作業(yè)J1,J2,J3,J4和J5，它們各需主存量為1KB,10KB,108KB,28KB,115KB，（1）若采用最先適應(yīng)分配算法，能把這5個作業(yè)按J1~J5的順序全部裝入主存嗎？按怎樣的次序裝入這5個作業(yè)可使主存利用率最高（2）若采用下次適應(yīng)，最佳適應(yīng)，最壞適應(yīng)算法，順序裝入J1~J5的情況怎樣？在各種適應(yīng)算法中，各按什么順序裝入5個作業(yè)使主存利用率最高動態(tài)分區(qū)分配習(xí)題習(xí)題4：設(shè)某時刻系統(tǒng)中有3個空閑區(qū)，其大小和首地址分別為(35KB,100KB),(12KB,156KB),(28KB,200KB)，設(shè)作業(yè)序列及其內(nèi)存請求為(Job1,20KB),(Job2,15KB),(Job3,15KB),(Job4,13KB)，設(shè)操作系統(tǒng)分配空閑區(qū)時，從空閑區(qū)的高地址開始分配（1）分別使用首次適應(yīng)，最佳適應(yīng)，最壞適應(yīng)3種算法對該作業(yè)序列進行分配。分別畫出空閑區(qū)隊列的初始狀態(tài)和分配后的狀態(tài)（2）根據(jù)分配的情況進行算法比較增加：伙伴系統(tǒng)■固定分區(qū)方式限制了活動進程的數(shù)目，當(dāng)進程大小與空閑分區(qū)大小不匹配時，內(nèi)存利用率很低■動態(tài)分區(qū)方式算法復(fù)雜，回收空閑分區(qū)時需要進行分區(qū)合并等，系統(tǒng)開銷較大■伙伴系統(tǒng)是對以上2種內(nèi)存分區(qū)方式的折中方案■伙伴系統(tǒng)規(guī)定：無論是已分配分區(qū)或空閑分區(qū)，其大小均為2的k次冪(k為某個正整數(shù))。■例如：當(dāng)用戶申請長度為n的內(nèi)存時，分配的空閑分區(qū)大小為2i，通過(2i-1＜n≤2i)可計算出i。■對每一類具有相同大小的所有空閑分區(qū)，都設(shè)置一個空閑分區(qū)雙向鏈表（多個空閑分區(qū)鏈表）增加：伙伴系統(tǒng)1）空閑分區(qū)鏈表結(jié)構(gòu)

★假設(shè)系統(tǒng)的可利用內(nèi)存空間容量為2m個字(地址從0到2m-1)★開始運行時，整個內(nèi)存是一個大小為2m的空閑分區(qū)★在運行了一段時間之后，被分隔成若干已分配分區(qū)和空閑分區(qū)★為了再分配時查找方便，將所有大小相同的空閑分區(qū)構(gòu)成一個雙向鏈表，這樣的鏈表可能有m+1個★將這m+1個鏈表頭指針用向量結(jié)構(gòu)組織成一個表，稱為可利用空間表增加：伙伴系統(tǒng)2）伙伴系統(tǒng)的分配和回收空間：分配空間時可能需要多次分割回收空間時可能需要多次合并可利用空間表示意圖伙伴系統(tǒng)習(xí)題習(xí)題1：已知一個大小為512的存儲區(qū)，假設(shè)先后有6個用戶申請大小為23，45，52，100，11，19的存儲空間，然后再順序釋放45，52，11的占用分區(qū)，假設(shè)以伙伴系統(tǒng)實現(xiàn)存儲管理。（1）畫出可利用空間表的初始狀態(tài)（2）畫出為6個用戶分配后可利用空間表的狀態(tài)，以及每個用戶得到的存儲塊的起始地址（3）畫出回收3個占用塊之后的可利用空間表的狀態(tài)伙伴系統(tǒng)習(xí)題習(xí)題1解答：（1）畫出可利用空間表的初始狀態(tài)說明：雙向鏈表0首地址0：未被占用9：29（空閑分區(qū)大小為512）29∧28∧27∧26∧25∧24∧23∧22∧21∧20900伙伴系統(tǒng)習(xí)題習(xí)題1：（2）畫出為6個用戶分配后可利用空間表的狀態(tài)，以及每個用戶得到的存儲塊的起始地址分析：202122232425262728291248163264128256512要求分配的大?。?3，45，52，100，11，19實際應(yīng)給分區(qū)大?。?264641281632分配：23，45，52，100，11，1905120642562561283212864322304525625612832128643223045256256643212864322319252045128256643212864322319252384100045128256641612864322319252384100110451282563216128643223192523841001119224習(xí)題1解答：（2）畫出為6個用戶分配后可利用空間表的狀態(tài)，以及每個用戶得到的存儲塊的起始地址∧29∧2827∧262524∧23∧22∧21∧2040485022470384序號要求大小起始地址123024564352128410025651132619192回收：45，52，1104512825632161286432231925238410011192240128256321612864322319252384100111922464不能合并0128256321612864322319264384100111922464不能合并0128256321612864322319264384100161922464合并1282563212864322319264384100192246432考慮：若接下來將19回收，會怎么樣？習(xí)題1解答：（3）畫出回收3個占用塊之后的可利用空間表的狀態(tài)∧29∧2827∧262524∧23∧22∧21∧2060647038460128603260224伙伴系統(tǒng)習(xí)題習(xí)題2：在下圖所示伙伴系統(tǒng)中，回收2塊首地址分別為768及128，大小為27的存儲塊，請畫出回收后該伙伴系統(tǒng)的狀態(tài)圖習(xí)題2解答：地址為768與896的兩個27空閑塊，合并為28空閑塊，再與前面地址為512的28空閑塊合并為一個地址為512的29的空閑塊，地址為128和256的2個27空閑塊由于不是伙伴，不能合并8.3.3碎片◆可重定位（動態(tài)重定位）引入原因

碎片問題：經(jīng)過一段時間的分配回收后，內(nèi)存中存在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要求；但其總和滿足分配要求。這些空閑塊被稱為碎片或零頭，造成存儲資源的浪費◆碎片分類：內(nèi)碎片、外碎片◆碎片問題的解決緊湊技術(shù)：（緊縮技術(shù)，拼接技術(shù)，浮動技術(shù)，搬家技術(shù)）——通過在內(nèi)存移動程序，將所有小的空閑區(qū)域合并為大的空閑區(qū)域，消除了內(nèi)零頭

問題：1.開銷大；2.移動時機（當(dāng)找不到足夠大的空閑分區(qū)且空閑分區(qū)的總?cè)萘靠梢詽M足作業(yè)要求時進行拼接）動態(tài)重定位緊縮技術(shù)圖動態(tài)重定位分配算法8.4分頁離散分配方式的引入◎問題：在動態(tài)分區(qū)的存儲空間中，由于是連續(xù)分配，存在“零頭”問題（碎片問題）。盡管采用“緊湊”技術(shù)可以解決這個問題，但要為移動大量信息花去不少的處理機時間，代價較高。◎解決：離散分配（頁式，段式，段頁式）◎離散分配：允許將進程分散地裝入到許多不相鄰接的分區(qū)中

分頁存儲管理方式：離散分配的基本單位是頁

分段存儲管理方式：離散分配的基本單位是段

段頁存儲管理方式：先分段，段內(nèi)再分頁8.4.1分頁的基本方法1.頁面和物理塊■分頁存儲管理，是將一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面或頁，并為各頁加以編號。從0開始編制頁號，頁內(nèi)地址是相對于0編址。■相應(yīng)地，也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊，稱為(物理/內(nèi)存)塊或頁框/幀(frame)■在為進程分配內(nèi)存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。

（邏輯上相鄰的頁，物理上可不相鄰）2.頁面大小的確定■頁面的大小應(yīng)選擇得適中頁面太小，頁內(nèi)碎片少，但進程所占頁面多，頁表大頁面太大，頁表數(shù)目減少，但頁內(nèi)碎片增多■頁面大小應(yīng)是2的冪，通常為512B~8KB3.分頁的地址結(jié)構(gòu)■分頁地址中的地址結(jié)構(gòu)如下：位移量W頁號P311090■對某特定機器，其地址結(jié)構(gòu)是一定的。若給定一個邏輯地址空間中的地址為A，頁面大小為L，則頁號P和頁內(nèi)地址w可按下式求得：4.頁表■頁表列出了作業(yè)的邏輯頁與其在主存中的物理塊的對應(yīng)關(guān)系（頁號，塊號）■見P247圖8.7圖8.8■見P249圖8.9■地址映射：將用戶地址空間的邏輯地址變換為內(nèi)存空間的物理地址，

借助頁表來完成地址映射分頁存儲管理的地址映射頁表首地址頁表長度頁表寄存器<越界中斷P247圖8.7分頁的硬件支持分頁模型邏輯內(nèi)存物理內(nèi)存頁表幀號■頁表的每一個表目稱為頁描述子.除了包含指向頁框的指針外，還包括一個存取控制字段P247圖8.8邏輯內(nèi)存和物理內(nèi)存的分頁模型分頁例子邏輯內(nèi)存物理內(nèi)存頁表P249圖8.9使用4B的頁對32B的內(nèi)存進行分頁的例子增加:分頁實例■例如：指令LOAD1,2500的地址變換過程如下：虛擬起址頁號位移量頁數(shù)頁表起址塊號位移量塊號存儲控制若頁號>頁表大小則中斷若訪問不允許則中斷物理地址頁號塊號權(quán)限021328指令頁表寄存器頁描述子頁表內(nèi)存①①⑦②②+③③④④⑤⑥⑥⑥⑦5.分頁的碎片問題■分頁存儲管理不會產(chǎn)生外碎片，可能在最后一頁產(chǎn)生頁內(nèi)碎片?！鏊伎?最大和最小的頁內(nèi)碎片是多少6.空閑幀空閑幀組織方法:1.列表法(見P250圖8.10)2.位示圖法0310/10/10/10/10/1017……空閑塊數(shù)……空閑幀的組織空閑幀列表空閑幀列表新進程新進程分配前分配后新進程的頁表P250圖8.10空閑幀8.4.2硬件支持(相聯(lián)存儲器TLB)■問題：如果把頁表放在主存中，無疑會影響系統(tǒng)的性能。這是因為每次訪問主存，首先必須訪問頁表，讀出頁描述子，之后根據(jù)形成的實際地址再訪問主存，這樣使訪問主存的次數(shù)加倍(2次訪存)，因而使總的處理速度明顯下降■解決：采用一組高速緩沖寄存器(Cache，聯(lián)想寄存器，快表,轉(zhuǎn)換表緩沖區(qū)TLB)，存放當(dāng)前訪問過的頁的頁描述子■實現(xiàn)：每次訪問主存時，首先查找快表，若找到所需的頁描述子，則快速形成物理地址。否則從頁表中查找后形成物理地址，同時把頁描述子寫入快表。如果設(shè)計得當(dāng)，快表的命中率可以很高。帶快表的分頁系統(tǒng)邏輯地址物理地址物理內(nèi)存頁表頁號幀號TLB:轉(zhuǎn)換表緩沖區(qū)(相聯(lián)存儲器)TLB命中TLB失效關(guān)鍵:盡可能提高快表命中率圖8.11帶TLB的分頁硬件P2528.4.3內(nèi)存保護幀號有效-無效位頁表圖8.12在頁表中的有效位(v)和無效位(i)■頁描述子中除包含幀號、還包含有效－無效位、存取控制位（讀寫位）P2538.4.4共享頁進程P1進程P2進程P3P1的頁表P2的頁表P3的頁表圖8.13在分頁環(huán)境下的代碼共享P2548.5頁表結(jié)構(gòu)■問題：現(xiàn)代的大多數(shù)計算機系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間■解決：可采用兩個方法來解決這一問題：①采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題：②只將當(dāng)前需要的部分頁表項調(diào)入內(nèi)存，其余的頁表項仍駐留在磁盤上，需要時再調(diào)入8.5.1層次頁表■將頁表進行分頁，離散的將大頁表的各個頁面存放在不同的物理塊中。■用外層頁表來記錄頁表頁面的物理塊號■例如：32位邏輯地址，頁面大小4KB，則1級頁表有20位頁號2級頁表有12位外層頁內(nèi)地址，10位外層頁號兩級頁表外部頁表頁表頁表的頁P256圖8.14一個兩級頁表方案二級頁表的地址轉(zhuǎn)換邏輯地址外頁表頁表的頁P256圖8.15二級32位分頁體系的地址轉(zhuǎn)換多級頁表■32位機器，可采用兩級頁表■64位機器，需要采用3級頁表■原因：64位機，假設(shè)頁面大小為4K(12位)，則頁內(nèi)位移為12位，頁表位移為12位，則剩下40位為頁目錄偏移，則共有240個頁表項，則要占240個連續(xù)空間，令人無法忍受■解決：用3級頁表哈希頁表邏輯地址哈希函數(shù)哈希表物理地址物理內(nèi)存P258圖8.16哈希頁表處理超過32位地址空間的常用方法是使用哈希頁表（要解決沖突問題）反向頁表邏輯地址物理地址物理內(nèi)存搜索頁表P259圖8.17反向頁表反向頁表：對每一個真正的內(nèi)存才有一個頁表條目優(yōu)點：節(jié)省頁表空間（不在內(nèi)存中的頁沒有頁表條目）缺點：搜索費時（不能直接計算頁表條目的地址，只能順序搜索）增加：頁式內(nèi)存管理的分配和回收■頁式的內(nèi)存分配：（修改PCB和位示圖/空閑塊表）①計算一個作業(yè)所需要的總塊數(shù)N②查位示圖或空閑塊表，看看是否還有N個空閑塊③如果有足夠的空閑塊，則頁表長度設(shè)為N，可填入PCB中；申請頁表區(qū)，把頁表始址填入PCB④依次分配N個空閑塊，將塊號和頁號填入頁表⑤修改位示圖■頁式的內(nèi)存回收：

回收頁表空間，修改進程的PCB，修改位示圖和空閑塊個數(shù)頁式習(xí)題■習(xí)題：假定某采用頁式存儲管理的系統(tǒng)中，主存容量為1M，被分成256塊，塊號為0，1，2，……，255.現(xiàn)有一個共4個頁面（頁號為0，1，2，3）的作業(yè)被依次裝入主存的第2，4，1，5塊中。請回答：（1）主存地址應(yīng)該用多少位來表示（2）作業(yè)每一頁的長度是多少字節(jié)？邏輯地址中的頁內(nèi)地址部分應(yīng)占多少位？（3）寫出作業(yè)中的每一個占用主存的主存塊的起始地址（4）若作業(yè)執(zhí)行中需要從第0頁的第75單元和第3頁的第548單元讀信息，那么，實際應(yīng)從主存的哪兩個單元讀信息，請把應(yīng)訪問的主存絕對地址用二進制編碼的十六進制數(shù)表示8.6分段■在分頁存儲系統(tǒng)中，作業(yè)