計算機操作系統(tǒng)許曰濱版第五章

1、計算機操作系統(tǒng)原理存儲管理概述 存儲管理必須實現的4大功能 存儲管理用到的數據結構 連續(xù)存儲管理方法（單分區(qū)、多分區(qū)）離散存儲管理方法（分頁、分段、段頁）存儲器外存儲器永久存放信息容量大速度慢內存儲器容量有限速度快內存儲器是一種隨機存儲器，各種程序只有裝入內存儲器才能運行需要解決什么問題？如何分配？如何回收？如何共享？如何擴充？5.1 概述內存儲器（Memory），簡稱內存由存儲體和輔助電路組成存儲體中包含若干存儲單元，每個存儲單元可存放一條獨立信息讀、寫數據以存儲單元為基本單位存儲單元也成為“內存地址”SDRAM時代DDR時代DDR2時代DDR3時代DDR4時代7內存儲器的組成內存儲器的組成

2、內內存存儲儲器器的的組組成成圖圖 85.1.2 5.1.2 存儲管理的主要功能存儲管理的主要功能存儲管理模塊的功能是對內存用戶區(qū)的存儲管存儲管理模塊的功能是對內存用戶區(qū)的存儲管理，主要概括為以下理，主要概括為以下4 4個方面?zhèn)€方面：1.1. 地址重定位地址重定位2.2.內存分配與回收內存分配與回收3.3.內存共享與保護內存共享與保護4.4.內存容量擴充內存容量擴充 9邏輯地址：邏輯地址：是用戶在其程序中使用的一種地址。由邏輯地址構成的地址空間稱邏輯地址空間，其首地址是0號地址，其它指令的地址都是相對于0號地址排定的。物理地址：是存儲單元的實際物理單元地址。一、一、地址重定位地址重定位 將邏輯地

3、址轉換成內存的物理地址的過程，稱為地址地址“重定位重定位”，地址重定位可分為靜態(tài)重定位靜態(tài)重定位和動態(tài)重定位動態(tài)重定位兩種方式。靜態(tài)重定位這是在程序運行前，由“裝載”過程實現的重定位。當把一個程序裝入內存時，對用戶代碼中使用的邏輯地址作適當調整，轉換成內存的物理地址轉換完成后，再將用戶代碼裝載到該物理空間中其后，程序使用的地址空間將不再改變動態(tài)重定位采用這種方式的硬件結構中專門設置一個“重定位寄存器”，當存儲管理系統(tǒng)為作業(yè)分配了一個內存區(qū)域后，就把該區(qū)的起始地址放到重定位寄存器中程序的物理地址將是邏輯地址和重定位寄存器的內容之和12動態(tài)重定位需要硬件支持允許執(zhí)行過程中實現操作數的地址轉換保持原

4、有邏輯空間關系可以在內存中浮動靜態(tài)重定位無需硬件支持 不允許。需要修改用戶程序原有的邏輯關系被破壞要求程序放在連續(xù)的存儲空間中二、內存分配與回收 在多道程序環(huán)境下，當系統(tǒng)需要裝載一個用戶作業(yè)時，作業(yè)調度程序將存儲管理模塊啟動起來，按某種方式分配存儲空間，并將程序代碼裝入。內存的分配有靜態(tài)分配和動態(tài)分配兩種方式。靜態(tài)分配在進程執(zhí)行前實施的內存空間分配。在這之后，系統(tǒng)不再接受進程的申請，也不允許進程在內存中移動（變更所占空間）動態(tài)分配進程在運行過程中實施的內存空間分配。也就是說，系統(tǒng)允許進程在運行過程中隨時申請內存空間三、內存的共享與保護 多道程序環(huán)境中，多個用戶作業(yè)都對內存空間提出申請，為提高內

5、存利用率，應該對內存空間實現共享。共享包括兩個方面的含義：共享內存儲器資源，讓多個進程同時進入內存區(qū)域，共享同一個存儲器共享內存儲器的某些區(qū)域，即允許兩個或多個進程訪問內存中的同一段程序或數據 內存保護上下界存儲保護技術保護鍵法上下界存儲保護技術CPU中設有一對上下界寄存器，登記當前進程所占內存空間的上下界地址對內存進行訪問時，首先做地址碼的合法性檢查。若程序中訪問的地址碼，不超出上下界寄存器所規(guī)定的范圍，則訪問是合法的；否則視為非法。對于程序的非法地址訪問，硬件將轉入“越界中斷”處理每個進程的PCB中設置上下界寄存器保護域，存放進程的上下界地址。當該進程被調度時，此兩項地址將與其它現場保護信

6、息（如程序狀態(tài)字PSW、程序計數器PC等）一起置入CPU中四、內存容量擴充內存容量是有限的內存擴充不是硬件上的擴充，而是用存儲管理軟件來實現的邏輯擴充例如，當有一個比內存容量還要大的程序要求運行時，內存不能一下子存儲作業(yè)的全部程序，操作系統(tǒng)可采用“虛擬存儲”技術，在外存的輔助下實現內存容量擴充覆蓋技術，對換技術，虛擬存儲技術等（第6章） 5.1.3 存儲管理的數據結構設置一些數據結構等級內存的使用情況常見的數據結構有：內存分配表、空閑區(qū)表和位示圖等內存分配表MAT，Memory Allocation Table內容包括各分區(qū)的分區(qū)號、起始地址、長度和占用標志等分區(qū)號：每個分區(qū)都有一個編號，用以

7、區(qū)別不同分區(qū)起始地址：分區(qū)的起始地址，即首地址長度：分區(qū)的總長，一般以KB為單位占用標志：記錄分區(qū)的使用狀態(tài)。0為空閑，非0位占用空閑區(qū)表/鏈記錄內存空閑區(qū)狀況為什么有了分配表了，還需要空閑區(qū)表？空閑區(qū)和分配區(qū)交叉在一起查找空閑區(qū)就得從頭逐一掃描，費時將空閑區(qū)組成一個鏈表，一個結點代表一個空閑區(qū) 空閑區(qū)表中各空閑區(qū)可按地址順序來排列，也可按尺寸大小來組織。當系統(tǒng)進行內存分配時，進行的處理是：通過空閑區(qū)表/鏈，快速搜索內存的空閑區(qū)從中找出最合適的分區(qū)分配出去將該結點從鏈上刪除當需要回收某塊被釋放的區(qū)域時，系統(tǒng)處理過程為：按其地址或者大小在鏈中找到合適的位置插入一個新結點如果存在相鄰的空閑區(qū)，則需

8、要的話可將相鄰空閑區(qū)合并位示圖 位示圖是存儲器的一種存儲空間映像，系統(tǒng)可以根據位圖來進行存儲空間的管理5.1.4 存儲管理的主要方法單一連續(xù)區(qū)方式 - 內存全部空間只存放一個作業(yè)分區(qū)方式 - 內存被分成多個分區(qū)，每個分區(qū)放一個作業(yè)，每瞬間可有多個作業(yè)駐留內存分頁方式 - 內存被劃分成多個等長的存儲塊，可有多個作業(yè)駐留內存分段方式 按照段的長度分別分配內存空間，可有多個作業(yè)駐留內存。配合分頁式，構成段頁式管理模式分配的內存空間是連續(xù)的分配的內存空間是連續(xù)的分配的內存空間是離散的分配的內存空間是離散的5.2 單一連續(xù)區(qū)管理單連續(xù)區(qū)存儲管理方式，把內存的用戶區(qū)視為一個獨立的連續(xù)存儲區(qū)，任何時刻只將它

9、分配給一個作業(yè)使用。這種存儲管理非常簡單，適用于單用戶單任務系統(tǒng)（如，MS-DOS操作系統(tǒng)的早期版本）。單一連續(xù)區(qū)的內存分配如果內存的用戶區(qū)小于請求的存儲空間n，將分配失敗信息反饋給申請者結束將程序加載到內存用戶區(qū)中將分配成功的信息反饋給申請者單一連續(xù)區(qū)的內存回收將內存中的程序和數據調出去對用戶區(qū)進行必要的清理和初始化操作單一連續(xù)區(qū)管理的缺點CPU的利用率不高。因為任何時刻最多只有一個程序獨占內存，無論在該程序執(zhí)行過程中，還是CPU等待I/O時都不能讓其他用戶使用。內存空間浪費嚴重。進入系統(tǒng)運行的大多數用戶作業(yè)的尺寸不可能正好等于整個內存用戶區(qū)的大小，當作業(yè)所要求的存儲空間較小時，剩余較大的空

10、白區(qū)未被利用，只能白白浪費。外設利用率較低。計算機的外部設備（比如，輸入/輸出設備）均被單個用戶所占用，因此利用率不高。不論該用戶是否使用，其它用戶都無法使用。5.3 分區(qū)管理建立在單一連續(xù)區(qū)的基礎上適用于多道程序運行環(huán)境思想：將內存用戶區(qū)劃分成多個存儲分區(qū)（除操作系統(tǒng)所占空間外），每一個分區(qū)可以裝入一個進程，內存中就可以同時容納多個進程固定分區(qū)思想：將內存用戶區(qū)劃分成若干固定長度的存儲塊進行分配。分區(qū)的劃分過程通常在系統(tǒng)生成時完成。各分區(qū)長度不要相等一、內存的分配與回收分區(qū)號分區(qū)號起始地址起始地址長度長度占用標志占用標志0 04k4k6k6k未分未分1 110k10k2k2k已分已分2 21

11、2k12k15k15k已分已分3 327k27k34k34k未分未分分配從頭到尾掃描內存分配表，找到滿足需求的分區(qū)將標志設為“已分”將分區(qū)的起始地址返回給用戶回收從頭到尾掃描內存分配表，找到該分區(qū)在表中的位置將其占用標志設為“未分”二、內存保護設置“上界寄存器”和“下界寄存器”某個進程運行時，系統(tǒng)將該進程所占的物理存儲區(qū)的上限和下限地址分別送入這兩個寄存器上三、固定分區(qū)的缺點浪費存儲空間，產生很多內碎片內碎片：作業(yè)獲得的空間大于需求的空間時多出來的一小部分用戶根本不需要的空閑區(qū)動態(tài)分區(qū)思想：系統(tǒng)不預先劃分固定分區(qū)，而是在裝入一個作業(yè)時，根據該用戶作業(yè)的實際需求量劃分出一個分區(qū)給它使用。若無足夠

12、大的連續(xù)空閑區(qū)供作業(yè)使用，則該作業(yè)只好等待一、內存的分配與回收動態(tài)分區(qū)分配算法可描述如下：（1）從頭到尾掃描空閑分區(qū)表，找到一個能滿足需求的空閑分區(qū)MATi。（2）若MATi（長度）= L，則：MATi（占用標志）=“已分”，轉（4）。（3）若MATi（長度）L，則：-1 L0 =MATi（長度）-L。 -2 MATi（長度）=L；MATi（占用標志）=“已分”。 -3 在內存分配表的下一個位置插入新行MATi+1。 -4 MATi+1（起始地址）=MATi（起始地址）+L。 -5 MATi+1（長度）=L0。 -6 MATi+1（占用標志）=“未分”。（4）結束。 當用戶歸還一個起始地址為M

13、的分區(qū)時，系統(tǒng)回收應做的處理是：如果這個空閑區(qū)與其它空閑區(qū)相鄰，則系統(tǒng)把它們合并成一個連續(xù)的大空閑區(qū)，以適應大作業(yè)的存儲需求。下面是回收過程：（1）在內存分配表中找到該分區(qū)的位置MATi。（2）MATi（占用標志）=“未分”。（3）若MATi-1（占用標志）=“未分”&MATi+1（占用標志）=“未分” ，則: 3個相鄰空閑區(qū)合并為一個。否則：（4）若MATi-1（占用標志）=“未分” ，則: 2個相鄰空閑區(qū)合并為一個。否則：（5）若MATi+1（占用標志）=“未分” ，則: 2個相鄰空閑區(qū)合并為一個。（6）結束。5.3.3 分配算法算法負責管理將哪個分區(qū)分配出去：首次適應算法（First F

14、it）循環(huán)首次適應算法(CFF, Circle First Fit)最佳適應算法(BF, Best Fit)最壞適應算法（WF, Worst Fit）首次適應算法 首次適應算法也稱為最早適應算法。系統(tǒng)將內存分區(qū)按地址遞增順序登記到內存分配表（或其它數據結構）中。每次進行內存分配時，系統(tǒng)根據進程申請空間的大小，從頭到尾順序掃描內存分配表（或其它數據結構），從中找到的第1個能夠滿足要求的空閑區(qū)，就立即分配出去。首次適應算法產生大量碎片每次內存分配時，都是從頭到尾順序查找，使地段地址空間使用頻繁，而高端地址空間較少使用循環(huán)首次適應算法（CFF）思想：每次存儲分配總是從上次分配的位置開始，向尾部查找。

15、查到的第1個可滿足用戶需求的空閑空間，就立即分配給用戶。當查到MAT（或空閑鏈表）的尾部仍然沒有合適的，則轉到頭部重新開始46 下面的例子中，MAT有8個分區(qū)，其中帶陰影的分區(qū)是已經被占用的。假設上次分配的是1#分區(qū)，則當前的指針位置是2#分區(qū)。如果有一個用戶請求40KB，則系統(tǒng)將按順時針方向，找到5#分區(qū)分配給用戶。 最佳適應算法（BF） 在內存分配時，從空閑區(qū)表中找到一塊滿足進程需求的最小空閑區(qū)分配給它，使剩余空間最小。這種做法減少了將大空閑區(qū)進行多次分割造成的空間浪費。但容易形成一些很小的碎片無法使用，同樣不能提高內存利用率。另外，每次分配時，都要對整個內存區(qū)進行從頭到尾的搜索，系統(tǒng)開銷

16、較大。最壞適應法（WF） 在進行內存分配時，從空閑區(qū)表中找到一個滿足長度要求的最大空閑區(qū)進行分配，使得剩下來的空閑區(qū)不致太小，還可以利用。這種算法部分地緩解了由外碎片引起的浪費，適合于中小作業(yè)的運行，但對大作業(yè)的運行是不利的。與最佳適應算法一樣，每次分配需要搜索一遍內存，效率會受到一定影響。5.3.4 可重定位動態(tài)分區(qū)管理 動態(tài)分區(qū)管理方式靈活，缺陷是外碎片帶來的空間浪費。要周期性地清除外碎片將動態(tài)分區(qū)技術與重定位技術相結合就可以解決這一問題。 動態(tài)重定位技術是允許進程在內存中浮動的。當內存中出現一些外部碎片后，可以將各個進程進行“搬家”，讓它們移動到內存的一端，使所有的外部碎片移動到另一端。

17、這樣就可使若干零星的碎片合并成一個大的空閑區(qū)了。這一過程也稱進程浮動。 進程浮動的時機：若內存可用空間總量充足，但因充滿了外部碎片不能滿足一個用戶的需求，可進行浮動。5.3.5 伙伴系統(tǒng) 在伙伴系統(tǒng)中，一個內存分區(qū)的大小是可變的。系統(tǒng)初始時，整個用戶空間s被看作是一個分區(qū)。當有一個用戶請求的空間尺寸為p時，BS的準則是： （1）若s=p s/2，則將整個分區(qū)分給用戶使用。 （2）否則，將分區(qū)分成大小相等的兩個伙伴，每一個的尺寸為s/2。 （3）若s/2=p s/4，則將兩個伙伴分區(qū)中的一個分給用戶使用。 （4）否則，將一個伙伴再分成大小相等的兩個小伙伴，每個小伙伴的尺寸為s/4。 （5）若s/

18、4=p s/8，則將兩個小伙伴分區(qū)中的一個分給用戶使用。按照這種思想將分區(qū)不斷分裂，直到分配一個適合用戶使用的空間為止?；锇橄到y(tǒng)的分配過程可構成一棵二叉樹，樹中的葉結點表示當前的分區(qū)情況。進程A需要100K；進程B需要50K；進程C需要100K；進程A釋放所占內存進程D需要20K；進程D釋放所占內存伙伴系統(tǒng)的特點允許保留部分內碎片分區(qū)尺寸隨用戶需求不斷變化內碎片不會太大5.4 分頁存儲管理分頁存儲管理，是按照程序頁面進行管理的一種方法。內存的用戶空間被劃分為一些大小相等的存儲塊，通常稱為“幀”（frame），或“頁框”。系統(tǒng)把每個進程劃分成與幀同樣大小的塊，通常稱為頁面（page）。讓每個頁面

19、存入一個幀中。當某個進程申請內存空間時，系統(tǒng)根據進程的長度計算出它所需要的幀數，然后，掃描MAT，選擇內存中的若干可用幀分配給該進程，整個分配一次性完成?？梢詫⑦M程的所有頁面分配到互不連續(xù)的若干幀中，因此是一種離散空間分配形式。5.4.1 頁面設系統(tǒng)的用戶區(qū)有10個幀，幀長度為1K，進程A、B、C各需要3K。它們依次進入內存，占據9個幀的位置。此后，進程B運行結束釋放所占的內存空間，系統(tǒng)接納了進程D。D需要4K內存，系統(tǒng)將它放在4個幀中。分配過程如圖。提出問題：每一幀分配什么尺寸比較合適？分頁管理和固定分配一樣，存在內碎片平均每個進程的空間浪費為L/2一般來說，幀的長度為1-4kb，此長度通常

20、與進程的平均長度、內存空間尺寸以及數據交換速度有關5.4.1 2 頁面劃分 為了使內存訪問能夠準確定位，系統(tǒng)需要將用戶程序代碼劃分為若干頁面，使原本一維的地址空間（也就是線性空間）分成低端地址和高端地址兩部分。低端地址部分，作為頁內的偏移量（即頁內地址）；高端地址部分作為頁號。 比如，系統(tǒng)規(guī)定頁面的長度為1024個字節(jié)，則頁內地址可用10個二進制位表示（1024=210）表示。若機器的地址碼是16位二進制數時，其中高6位代表頁號，低10位代表頁內地址。即： 6位位10位位頁號頁號頁內地址頁內地址5.4.1 3 頁表為了保證程序的正確運行，分頁管理機制應為每個進程建立一個數據結構頁表PT（Pag

21、e Table）。頁表中登記進程各頁面對應的幀號，供地址映射使用。 頁號幀號權限00R14R25W37R/W5.4.2 頁面分配（1）計算請求者需要的總幀數N。（2）查位圖，若找不到足夠的空閑幀，編制“分配失敗”報告返回。（3）索取一個空閑頁表PT。（4）從位圖中找出N個為0位，計算出對應的幀號，填入PT。（5）將這些位改為1。（6）將PT起始地址填入進程的PCB中。（7）結束。645.4.35.4.3 頁面共享頁面共享 1 1、可重入技術、可重入技術 在多道程序運行環(huán)境中，可重入技術是一項很有用的技術。它可以幫操作系統(tǒng)解決多任務共享同一程序的問題。一個可共享程序不能讓指令和變量交織在一起，必

22、須讓程序和變量分開。 讓程序中不發(fā)生變化的部分指令代碼，單獨存入一個程序體中，形成所謂的“純碼”。讓程序的操作對象存放（中間）結果的變量由各調用者自備。這樣，多任務共享同一個程序就成為可能的了。 652 2、共享的實現、共享的實現 頁面共享頁面共享，指的是一個頁面同時供多個進程使用。帶來了一個很重要的問題，即用戶訪問權限問題。 系統(tǒng)中提供的共享頁面，可能具有不同的調用方式。例如，對于“共享程序”頁面，通常只允許執(zhí)行，不允許寫入；而對于“共享數據”頁面，可能既允許一部分進程讀出，也允許一部分進程寫入。 比如，內存中的共享頁有兩個，它們分別存在第3幀和第4幀中。內存中的兩個進程P1和P2，按下一頁

23、圖的方式共享它們?？偨Y分頁式存儲管理離散存儲，利于大進程裝入只有很少的頁內碎片，提高內存利用率DS：位示圖、頁表動態(tài)地址重定位 邏輯地址 物理地址 一維、二維 二維、一維頁面共享不易實現5.5 分段管理技術模塊化和層次化的程序結構逐漸成為設計的主流應用程序中的每個功能模塊有一個獨立的段名，每個段含有若干條命令或數據段，指的是一組邏輯信息，如主程序、過程、函數或者數組等。例子：project ara和LG G55.5.1 分段管理的基本原理 在結構程序設計中，用戶的源程序使用的是二維地址。段中訪問一個變量時，地址形式為：。例如，一個進程P包括3個程序段：Main（主段）、Sub1（子段1）和Su

24、b2（子段2）。圖給出各個段之間的調用關系。分段管理和分頁管理在調用方式上有差別段的長度不同，為各個段分配等長的存儲空間是不現實的所以，考慮了類似動態(tài)分區(qū)的分配機制分頁 類似于固定分區(qū)，分段 類似于動態(tài)分區(qū)容易產生段之間的小碎片在分段機制中，一個進程的地址空間可以包含以下不同的段：代碼段數據段堆棧段內存共享段5.5.2 段表 與分頁管理一樣，分段管理也是一種支持離散空間分配的機制。為了使程序能夠正常運行，系統(tǒng)也必須能夠定位各個段的物理位置。為此，應當仿效分頁管理系統(tǒng)的做法，為進程建立地址映射的數據結構段表。段表ST，是用來記錄各個段地址映射關系的表格，每個進程有一張。各個分段在內存空間中的對應

25、位置都登記在段表中。 例：一個進程含有3個分段：Main、Sub1和Sub2（其中Main是主段），長度分別為2K、4K和1K。系統(tǒng)需要分配3塊的空間分別存放它們。比如分配的3塊不連續(xù)的存儲區(qū)，首地址分別為：14K、3K和7K。一般來說，分段數量不會很多一般采用大小不等的分段方式分配內存空間時，一并為進程制作一個段表，駐留在內存中那么，內存使用情況使用什么數據結構比較合適？MAT還是空閑分區(qū)表？這里用的MAT和動態(tài)多分區(qū)中的MAT表有何區(qū)別？一個段相當于一個分區(qū)，一個進程離散成多個段裝入多個不連續(xù)的分區(qū)中5.5.3 地址變換與分頁管理類似，區(qū)別在于段是信息的邏輯單位，由用戶劃分；頁是信息的物理

26、單位，長度是固定的，和用戶無關分段管理的地址變換是在硬件的協助下完成需要段表基址寄存器STBR和段表長度寄存器STLR76邏輯地址邏輯地址: : 二維二維 段號段號 段內地址段內地址物理地址物理地址: : 一維物理地址一維物理地址查查段段表表硬件支持硬件支持: : CPUCPU設設段表控制寄存器段表控制寄存器，記錄當前進程的段記錄當前進程的段表的起始地址和段表的起始地址和段表長度表長度段段起起始始地地址址累加累加程序運行中的地址變換過程如下：(1) 提取邏輯地址中的“段號”。(2) 比較段號與STLR的段長度。如果超出段表長度，則返回“內存定位錯誤”，終止進程的運行。(3) 從STBR中給出的

27、段表首址開始，以段號為索引查找該進程對應的段表，得到欲訪問段的首地址。(4) 取出欲訪問段的首地址，加上邏輯地址中的偏移量得到物理地址。5.5.4 分段保護與分享 分段管理模式下的信息保護分兩級。第一級是防止進程發(fā)生超出存儲空間的訪問，第二級是阻止進程超出訪問權限的讀寫。這里主要介紹一下第一級保護。共享：分段存儲管理可以方便地實現內存信息的共享。由于段具有完整的邏輯意義，因此非常適合按段進行訪問。如果多個用戶進程需要共享內存中的某些代碼段或數據段時，可將內存中共享段的起始地址及長度，填入這些進程的段表當中，就可共享一個邏輯上完整的段信息了?！岸巍迸c“頁”分段管理方式中的地址變換與分頁管理方式中

28、的十分相似。不過，段是信息的邏輯單位，是由用戶自己劃分的，其大小是隨機的；而頁是信息的物理單位，長度是固定的，用戶根本看不到頁的劃分。5.5.5 段頁式管理 這種管理方式可以看作是分段與分頁兩項管理技術的結合。系統(tǒng)為一個含有多分段的進程分配內存時，首先為這些分段建立段表，將各段長度填入表中。接下來為每個段分配地址空間。在這種系統(tǒng)中，各分段有一個頁表，其首地址存放在段表中。比如某個進程有3個段，各自對應一個頁表。假設內存中的幀長為2K，段表結構和頁表結構可通過圖所示的形式給出。5.5.5 段頁式管理 這種管理方式可以看作是分段與分頁兩項管理技術的結合。系統(tǒng)為一個含有多分段的進程分配內存時，首先為

29、這些分段建立段表，將各段長度填入表中。接下來為每個段分配地址空間。在這種系統(tǒng)中，各分段有一個頁表，其首地址存放在段表中。比如某個進程有3個段，各自對應一個頁表。假設內存中的幀長為2K，段表結構和頁表結構可通過圖所示的形式給出。84 這種系統(tǒng)的地址變換比較復雜。系統(tǒng)的硬件支持是，在處理機內部設有段表控制寄存器及地址生成邏輯。程序中的邏輯地址仍然是二維地址：。其中的偏移量將被分成兩部分：頁號和頁內偏移量。這樣一來，地址部分被當作三維地址來處理：855.6 關于分頁討論頁面尺寸 設某系統(tǒng)中的用戶區(qū)有M個字節(jié)，規(guī)定的頁面尺寸為P個字節(jié)。假定進入系統(tǒng)的進程長度平均為S個字節(jié)，則 內存中可容納的進程數為M

30、/S個； 每個進程的頁表長度為S/P字節(jié)（設每一項只占1個字節(jié)）； 系統(tǒng)為了支持分頁管理機制，需要開辟的頁表區(qū)總容量為S/P*M/S字節(jié)。 另外，每個進程平均浪費P/2字節(jié)，全部進程總的浪費為M/S*P/2字節(jié)。87這樣，系統(tǒng)額外開銷的總字節(jié)數為： S/P*M/S + M/S*P/2為了達到額外開銷比最小，可令： F（P）=（S/P*M/S + M/S*P/2）/ M =（M/P + MP/2 S）/ M = 1/P + P/2 S 對F（P）求導，令一階導數為0，得： 從該式可以看出，頁面尺寸P是與進程平均長度S有關的參數。只有滿足上述關系時，內存的額外開銷才會達到最小。SP288二、多級頁

31、表結構二、多級頁表結構 請計算：一個由32位二進制組成的地址空間，頁面長度為4KB，每個頁表項占用4B，則：進程的頁面總數可達 個。整個頁表占用 。如果高一級的頁表也必須用多個幀來存放，那么還需要建立更高一級的頁表多級頁表那么問題又來了：頁表本身怎么存放？將進程的頁表按幀的長度劃分為多個頁面，并建立高一級的頁表來索引它們兩級頁表89計算題計算題1. 1. 一個由32位二進制組成的地址空間，頁面長度為4KB，每個頁表項占用4B。 （a）采用一級頁表機制，所允許的進程的最大長度是（ ）。（b）采用兩級級頁表機制，所允許的進程的最大長度是（ ） 。90因頁面長度為4KB，所以頁內偏移占12位；余下2

32、0位對應頁號，所以進程的頁面總數可達1M個；整個頁表占用4MB，這4MB又劃分為1K個頁面；一個頁面正好可存放1K個頁表項；所以，為了查找這1K個頁面，需建立兩級頁表結構。那么，相對地址被分成a、b、c三個域，a、b用于兩級頁表，c用于頁內偏移地址。即：外層頁號a和內層頁號b各占10位，偏移量c占12位計算題計算題2：若一個由32位二進制組成的地址空間，頁面長度為4KB，每個頁表項占用4B，請問地址結構。9192在多級頁表機制中，處理機中要設有外部頁表寄存器，存放當前進程的外部頁表首地址。系統(tǒng)根據指令給出的相對地址進行變換，過程為：用邏輯地址中的外層頁號a查外層頁表，得到內層頁表首地址。用邏輯

33、地址中的內層頁號b查內層頁表，得到數據幀號。將數據幀的首地址加上偏移地址c得到物理地址。93多級頁表機制的地址變換過程 94 三、快表快表（1）存儲在高速緩存；（2）內容為頁表中最近使用的頁表項95 對于對于CPU給出的一個相對地址給出的一個相對地址，引入快表之后的地址變換過程是：引入快表之后的地址變換過程是：（1）硬件邏輯中，將邏輯地址中的頁號P送入高速緩存，與其中的所有頁號進行比較。找到相匹配的頁號后，讀出該頁面對應的幀號，送物理地址寄存器，與偏移量W共同合成一個訪問內存的物理地址。（2）若高速緩存內找不到相匹配的頁號，表示欲訪問的頁號不在快表中。系統(tǒng)需要再訪問內存中的頁表。找到該頁的幀號，送物理地址寄存器與偏移量W共同合成訪問內存的物理地址。同時，將該頁及幀號復制到快表中。此時，如果高速緩存已沒有空閑位置，應找到一個最不常用的頁表項淘汰掉，換入新的頁表項。96下圖給出了轉換過程，中間部分是保存快表的高速緩存。97一般地，當查詢快表的命中率為一般地，當查詢快表的命中率為p，則平均內，則平均內存有效訪問時間存有效訪問時間T大約為：大約為：)2()1