操作系統(tǒng)第5章存儲(chǔ)管理

1、第5章 存儲(chǔ)管理,5.1 存儲(chǔ)管理的功能 5.2 分區(qū)存儲(chǔ)管理 5.3 覆蓋與交換技術(shù) 5.4 頁(yè)式管理 5.5 段式與段頁(yè)式管理 5.6 本章小結(jié),5.1 存儲(chǔ)管理的功能 存儲(chǔ)管理的功能如下: 1.主存空間的分配與回收 2.地址轉(zhuǎn)換 3.主存空間的共享和保護(hù) 4.主存空間的擴(kuò)充,5.1.2 重定位 一.絕對(duì)地址和邏輯地址 內(nèi)存地址的集合稱為內(nèi)存空間或物理地址空間。內(nèi)存中，每一個(gè)存儲(chǔ)單元都與相應(yīng)的稱為內(nèi)存地址的編號(hào)相對(duì)應(yīng)。顯然，內(nèi)存空間是一維線性空間。 二.虛存的一維線性空間或多維線性空間變換到內(nèi)存的唯一的一維物理線性空間 1.虛擬空間的劃分問(wèn)題 2.把虛擬空間中已鏈接 和劃分好的內(nèi)容裝入 內(nèi)

2、存，并將虛擬地址 映射為內(nèi)存地址的問(wèn)題。,1. 靜態(tài)地址重定位 在虛空間程序執(zhí)行之前由裝配程序完成地址映射工作. 靜態(tài)重定位的優(yōu)點(diǎn)是不需要硬件支持。 缺點(diǎn): 不能移動(dòng) 在程序執(zhí)行之前將有關(guān)部分全部裝入 必須占用連續(xù)的內(nèi)存空間，這就難以做到程序和數(shù)據(jù)的共享。,2. 動(dòng)態(tài)地址重定位 動(dòng)態(tài)地址重定位（dynamic address relocation）是在程序執(zhí)行過(guò)程中，在cpu訪問(wèn)內(nèi)存之前，將要訪問(wèn)的程序或數(shù)據(jù)地址轉(zhuǎn)換成內(nèi)存地址。動(dòng)態(tài)重定位依靠硬件地址變換機(jī)構(gòu)完成。 地址重定位機(jī)構(gòu)需要一個(gè)(或多個(gè))基地址寄存器br和一個(gè)(或多個(gè))程序虛擬地址寄存器vr。指令或數(shù)據(jù)的內(nèi)存地址ma與虛擬地址的關(guān)系為

3、: ma=(br)+ (vr) 這里，(br)與(vr)分別表示寄存器br與vr中的內(nèi)容。,圖5.3 動(dòng)態(tài)地址重定位,動(dòng)態(tài)重定位的主要優(yōu)點(diǎn)有: (1) 可以對(duì)內(nèi)存進(jìn)行非連續(xù)分配。 (2) 動(dòng)態(tài)重定位提供了實(shí)現(xiàn)虛擬存儲(chǔ)器的基礎(chǔ)。 (3) 有利于程序段的共享。,5.1.3 內(nèi)外存數(shù)據(jù)傳輸?shù)目刂?1.是用戶程序自己控制:覆蓋技術(shù) 2.是操作系統(tǒng)控制: 交換(swapping)方式 請(qǐng)求調(diào)入(on demand)方式和預(yù)調(diào)入(on prefetch)方式。,5.1.4 內(nèi)存的分配與回收 幾種策略和數(shù)據(jù)結(jié)構(gòu): 分配結(jié)構(gòu) (2) 放置策略 (3) 交換策略 (4) 調(diào)入策略。 (5) 回收策略,5.1.5

4、 內(nèi)存信息的共享與保護(hù) 常用的內(nèi)存信息保護(hù)方法有硬件法、軟件法和軟硬件結(jié)合三種。 1.上下界保護(hù)法是一種常用的硬件保護(hù)法,2.保護(hù)鍵法。,圖5.5 保護(hù)鍵保護(hù)法,3.界限寄存器與cpu的用戶態(tài)或核心態(tài)工作方式相結(jié)合的保護(hù)方式。 在這種保護(hù)模式下，用戶態(tài)進(jìn)程只能訪問(wèn)那些在界限寄存器所規(guī)定范圍內(nèi)的內(nèi)存部分，而核心態(tài)進(jìn)程則可以訪問(wèn)整個(gè)內(nèi)存地址空間。unix系統(tǒng)就是采用的這種內(nèi)存保護(hù)方式。,5.2 分區(qū)存儲(chǔ)管理 5.2.1 分區(qū)管理基本原理 分區(qū)管理的基本原理是給每一個(gè)內(nèi)存中的進(jìn)程劃分一塊適當(dāng)大小的存儲(chǔ)區(qū),以連續(xù)存儲(chǔ)各進(jìn)程的程序和數(shù)據(jù)，使各進(jìn)程得以并發(fā)執(zhí)行。 按分區(qū)的時(shí)機(jī)，分區(qū)管理可以分為固定分區(qū)和動(dòng)

5、態(tài)分區(qū)兩種方法。,1. 固定分區(qū)法 把內(nèi)存區(qū)固定地劃分為若干個(gè)大小不等的區(qū)域。劃分的原則由系統(tǒng)操作員或操作系統(tǒng)決定。分區(qū)一旦劃分結(jié)束，在整個(gè)執(zhí)行過(guò)程中每個(gè)分區(qū)的長(zhǎng)度和內(nèi)存的總分區(qū)個(gè)數(shù)將保持不變。 系統(tǒng)對(duì)內(nèi)存的管理和控制通過(guò)數(shù)據(jù)結(jié)構(gòu)分區(qū)說(shuō)明表進(jìn)行，,圖5.6 固定分區(qū)法,2. 動(dòng)態(tài)分區(qū)法 動(dòng)態(tài)分區(qū)法在作業(yè)執(zhí)行前并不建立分區(qū)，分區(qū)的建立是在作業(yè)的處理過(guò)程中進(jìn)行的，且其大小可隨作業(yè)或進(jìn)程對(duì)內(nèi)存的要求而改變。這就改變了固定分區(qū)法中那種即使是小作業(yè)也要占據(jù)大分區(qū)的浪費(fèi)現(xiàn)象，從而提高了內(nèi)存的利用率,圖5.7 內(nèi)存初始分配情況,圖5.8 內(nèi)存分配變化過(guò)程,內(nèi)存管理用數(shù)據(jù)結(jié)構(gòu): 可用分區(qū)表:每個(gè)表目記錄一個(gè)空

6、閑區(qū) 可用分區(qū)自由鏈:查找比可用表困難，但不必占用額外的內(nèi)存區(qū)。 請(qǐng)求表:請(qǐng)求表的每個(gè)表目描述請(qǐng)求內(nèi)存資源的作業(yè)或進(jìn)程號(hào)以及所請(qǐng)求的內(nèi)存大小。,圖5.9 可用表、自由鏈及請(qǐng)求表,圖5.10 固定分區(qū)分配算法,5.2.2 分區(qū)的分配與回收 1. 固定分區(qū)時(shí)的分配與回收,2. 動(dòng)態(tài)分區(qū)時(shí)的分配與回收 動(dòng)態(tài)分區(qū)時(shí)的分配與回收主要解決三個(gè)問(wèn)題: (1) 對(duì)于請(qǐng)求表中的要求內(nèi)存長(zhǎng)度，從可用表或自由鏈中尋找出合適的空閑區(qū)分配程序。 (2) 分配空閑區(qū)之后，更新可用表或自由鏈。 (3) 進(jìn)程或作業(yè)釋放內(nèi)存資源時(shí)，和相鄰的空閑區(qū)進(jìn)行鏈接合并，更新可用表或自由鏈。,動(dòng)態(tài)分區(qū)時(shí)的分配方法： 最先適應(yīng)法(first

7、 fit algorithm) 最佳適應(yīng)法(best fit algorithm) 最壞適應(yīng)法(worst fit algoriathm) (1) 最先適應(yīng)法 按起始地址遞增的次序排列 (2) 最佳適應(yīng)算法 最佳適應(yīng)算法要求從小到大的次序組成空閑區(qū)可用表或自由鏈。 (3) 最壞適應(yīng)算法 最壞適應(yīng)算法要求空閑區(qū)按其大小遞減的順序組成空閑區(qū)可用表或自由鏈。,圖5.11 最先適應(yīng)算法,4. 幾種分配算法的比較 思考：三種分配算法的各自特點(diǎn) 從查找速度、釋放速度及空閑區(qū)的利用等三個(gè)方面對(duì)上述三種算法進(jìn)行比較。,內(nèi)存回收4種情況： 如果釋放區(qū)與上下兩空閑區(qū)相鄰 如果釋放區(qū)只與上空閑區(qū)相鄰 如果釋放區(qū)與下

8、空閑區(qū)相鄰 如果釋放區(qū)不與任何空閑區(qū)相鄰,圖5.12 空閑區(qū)的合并,5.2.3 有關(guān)分區(qū)管理其他問(wèn)題的討論 1. 關(guān)于虛存的實(shí)現(xiàn) 2. 關(guān)于內(nèi)存擴(kuò)充 3. 關(guān)于地址變換和內(nèi)存保護(hù) 設(shè)cpu指令所要訪問(wèn)的虛擬地址為d 靜態(tài)重定位:在上下限寄存器中值之間 動(dòng)態(tài)重定位 若dvr (vr是限長(zhǎng)寄存器中的限長(zhǎng)值)，則說(shuō)明地址越界 若d=vr，則該地址是合法的，由硬件完成對(duì)該虛擬地址的動(dòng)態(tài)重定位。 保護(hù)鍵法也可用來(lái)對(duì)內(nèi)存各分區(qū)提供保護(hù)。,4. 分區(qū)存儲(chǔ)管理的主要優(yōu)缺點(diǎn) 分區(qū)存儲(chǔ)管理的主要優(yōu)點(diǎn)如下: (1) 實(shí)現(xiàn)了多個(gè)作業(yè)或進(jìn)程對(duì)內(nèi)存的共享，有助于多道程序設(shè)計(jì)，從而提高了系統(tǒng)的資源利用率。 (2) 該方法要

9、求的硬件支持少，管理算法簡(jiǎn)單，因而實(shí)現(xiàn)容易。 主要缺點(diǎn)有: (1) 內(nèi)存利用率仍然不高。和單一連續(xù)分配算法一樣，存儲(chǔ)器中可能含有從未用過(guò)的信息。而且，還存在著嚴(yán)重的碎小空閑區(qū)(碎片)不能利用的問(wèn)題。 (2) 作業(yè)或進(jìn)程的大小受分區(qū)大小控制，除非配合采用覆蓋和交換技術(shù)。 (3) 難以實(shí)現(xiàn)各分區(qū)間的信息共享。,5.3.1 覆蓋技術(shù) 把程序劃分為若干個(gè)功能上相對(duì)獨(dú)立的程序段，按照程序的邏輯結(jié)構(gòu)讓那些不會(huì)同時(shí)執(zhí)行的程序段共享同一塊內(nèi)存區(qū)。 覆蓋技術(shù)要求程序員提供一個(gè)清楚的覆蓋結(jié)構(gòu)，程序員負(fù)擔(dān)較重。,5.3 覆蓋與交換技術(shù),圖5.13 覆蓋示例,5.3.2 交換技術(shù) 交換是指先將內(nèi)存某部分的程序或數(shù)據(jù)寫

10、入外存交換區(qū)，再?gòu)耐獯娼粨Q區(qū)中調(diào)入指定的程序或數(shù)據(jù)到內(nèi)存中來(lái)，并讓其執(zhí)行的一種內(nèi)存擴(kuò)充技術(shù)。 交換主要是在進(jìn)程或作業(yè)之間進(jìn)行，而覆蓋則主要在同一個(gè)作業(yè)或進(jìn)程內(nèi)進(jìn)行。 交換進(jìn)程由換出和換入兩個(gè)過(guò)程組成。其中換出(swap out)過(guò)程把內(nèi)存中的數(shù)據(jù)和程序換到外存交換區(qū)，而換入(swap in)過(guò)程把外存交換區(qū)中的數(shù)據(jù)和程序換到內(nèi)存分區(qū)中。,1.各進(jìn)程的虛擬空間被劃分成若干個(gè)長(zhǎng)度相等的頁(yè)(page)。進(jìn)程的虛地址變?yōu)轫?yè)號(hào)p與頁(yè)內(nèi)地址的d所組成。 2.把內(nèi)存空間也按頁(yè)的大小劃分為片或頁(yè)面(page frame)。 3.用戶進(jìn)程在內(nèi)存空間內(nèi)除了在每個(gè)頁(yè)面內(nèi)地址連續(xù)之外，每個(gè)頁(yè)面之間不再連續(xù)。 19 1

11、0 9 0 圖5.14 頁(yè)的劃分,5.4 頁(yè) 式 管 理 5.4.1 頁(yè)式管理的基本原理,優(yōu)點(diǎn)： 第一是實(shí)現(xiàn)了內(nèi)存中碎片的減少，因?yàn)槿我凰槠紩?huì)小于一個(gè)頁(yè)面。 第二是實(shí)現(xiàn)了由連續(xù)存儲(chǔ)到非連續(xù)存儲(chǔ)這個(gè)飛躍，為在內(nèi)存中局部地、動(dòng)態(tài)地存儲(chǔ)那些反復(fù)執(zhí)行或即將執(zhí)行的程序和數(shù)據(jù)段打下了基礎(chǔ)。,5.4.2 靜態(tài)頁(yè)面管理 靜態(tài)頁(yè)面管理方法在作業(yè)或進(jìn)程開(kāi)始執(zhí)行之前，把該作業(yè)或進(jìn)程的程序段和數(shù)據(jù)全部裝入內(nèi)存的各個(gè)頁(yè)面中，并通過(guò)頁(yè)表(page mapping table)和硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)虛擬地址到內(nèi)存物理地址的地址映射。,(1) 頁(yè)表 最簡(jiǎn)單的頁(yè)表由頁(yè)號(hào)與頁(yè)面號(hào)組成。頁(yè)式管理時(shí)每個(gè)進(jìn)程至少擁有一個(gè)頁(yè)表。 圖5

12、.15 基本頁(yè)表示例,1. 內(nèi)存頁(yè)面分配與回收,(2) 請(qǐng)求表 請(qǐng)求表用來(lái)確定作業(yè)或進(jìn)程的虛擬空間的各頁(yè)在內(nèi)存中的實(shí)際對(duì)應(yīng)位置。請(qǐng)求表整個(gè)系統(tǒng)一張，如圖5.16所示。 圖5.16 請(qǐng)求表示例,(3) 存儲(chǔ)頁(yè)面表存儲(chǔ)頁(yè)面表也是整個(gè)系統(tǒng)一張，存儲(chǔ)頁(yè)面表指出內(nèi)存各頁(yè)面是否已被分配出去, 以及未分配頁(yè)面的總數(shù)。 位示圖 空閑頁(yè)面鏈 圖5.17 位示圖,圖5.18 頁(yè)面分配算法流圖,2. 分配算法,圖5.19 頁(yè)號(hào)與頁(yè)面號(hào) 設(shè)每個(gè)頁(yè)面長(zhǎng)度為1k，指令load 1，2500的虛地址為100，怎樣通過(guò)圖5.19所示頁(yè)表來(lái)找到該指令所對(duì)應(yīng)的物理地址呢?,3. 地址變換,圖5.20 地址變換,取一個(gè)數(shù)據(jù)或指令至

13、少要訪問(wèn)內(nèi)存兩次以上 辦法1：就是把頁(yè)表放在寄存器中而不是內(nèi)存中，但由于寄存器價(jià)格太貴，這樣做是不可取的 辦法2：是在地址變換機(jī)構(gòu)中加入一個(gè)高速聯(lián)想存儲(chǔ)器，構(gòu)成一張快表。在快表中，存入那些當(dāng)前執(zhí)行進(jìn)程中最常用的頁(yè)號(hào)與所對(duì)應(yīng)的頁(yè)面號(hào)，從而以提高查找速度。,靜態(tài)頁(yè)式管理 優(yōu)點(diǎn)：解決了分區(qū)管理時(shí)的碎片問(wèn)題。 缺點(diǎn)：在執(zhí)行前全部裝入內(nèi)存 作業(yè)或進(jìn)程的大小仍受內(nèi)存可用頁(yè)面數(shù)的限制,5.4.3 動(dòng)態(tài)頁(yè)式管理 分為請(qǐng)求頁(yè)式管理和預(yù)調(diào)入頁(yè)式管理。 共同點(diǎn)：請(qǐng)求頁(yè)式管理和預(yù)調(diào)入頁(yè)式管理在作業(yè)或進(jìn)程開(kāi)始執(zhí)行之前，都不把作業(yè)或進(jìn)程的程序段和數(shù)據(jù)段一次性地全部裝入內(nèi)存，而只裝入被認(rèn)為是經(jīng)常反復(fù)執(zhí)行和調(diào)用的工作區(qū)部分。

14、其他部分則在執(zhí)行過(guò)程中動(dòng)態(tài)裝入。 主要區(qū)別：在調(diào)入方式上 請(qǐng)求頁(yè)式管理：當(dāng)需要執(zhí)行某條指令而又發(fā)現(xiàn)它不在內(nèi)存時(shí)或當(dāng)執(zhí)行某條指令需要訪問(wèn)其他的數(shù)據(jù)或指令時(shí)，這些指令和數(shù)據(jù)不在內(nèi)存中，從而發(fā)生缺頁(yè)中斷，系統(tǒng)將外存中相應(yīng)的頁(yè)面調(diào)入內(nèi)存。 預(yù)調(diào)入方式：系統(tǒng)對(duì)那些在外存中的頁(yè)進(jìn)行調(diào)入順序計(jì)算，估計(jì)出這些頁(yè)中指令和數(shù)據(jù)的執(zhí)行和被訪問(wèn)的順序，并按此順序?qū)⑺鼈冺槾握{(diào)入和調(diào)出內(nèi)存。,問(wèn)題1：虛頁(yè)不在內(nèi)存中的-擴(kuò)充頁(yè)表的方法解決。增設(shè)該頁(yè)是否在內(nèi)存的中斷位以及該頁(yè)在外存中的副本起始地址。擴(kuò)充后的頁(yè)表如圖5.21。 圖5.21 加入中斷處理后的頁(yè)表,問(wèn)題2：虛頁(yè)不在內(nèi)存時(shí)的處理。 第一，采用何種方式把所缺的頁(yè)調(diào)入內(nèi)

15、存。 -產(chǎn)生缺頁(yè)中斷信號(hào)，由中斷處理程序做出相應(yīng)的處理 第二，如果內(nèi)存中沒(méi)有空閑頁(yè)面時(shí)，把調(diào)進(jìn)來(lái)的頁(yè)放在什么地方。 -置換算法 在頁(yè)表中還應(yīng)增加一項(xiàng)以記錄該頁(yè)是否曾被改變。增加改變位后的頁(yè)表項(xiàng)如圖5.22所示。,圖5.22 加入改變位后的頁(yè)表,圖5.23 動(dòng)態(tài)頁(yè)式管理流圖,置換算法 抖動(dòng)(thrashing)現(xiàn)象：如果置換算法選擇不當(dāng)，有可能產(chǎn)生剛被調(diào)出內(nèi)存的頁(yè)又要馬上被調(diào)回內(nèi)存，調(diào)回內(nèi)存不久又馬上被調(diào)出內(nèi)存，如此反復(fù)的局面。這使得整個(gè)系統(tǒng)的頁(yè)面調(diào)度非常頻繁，以致大部分時(shí)間都花費(fèi)在主存和輔存之間的來(lái)回調(diào)入調(diào)出上。這種現(xiàn)象被稱為抖動(dòng)(thrashing)現(xiàn)象。,5.4.4 請(qǐng)求頁(yè)式管理中的置換算

16、法 (1) 隨機(jī)淘汰算法。 (2) 輪轉(zhuǎn)法和先進(jìn)先出算法。 由實(shí)驗(yàn)和測(cè)試發(fā)現(xiàn)fifo算法和rr算法的內(nèi)存利用率不高。 先進(jìn)先出算法的另一個(gè)缺點(diǎn)是它有一種陷阱現(xiàn)象在未給進(jìn)程或作業(yè)分配足它所要求的頁(yè)面數(shù)時(shí)，有時(shí)會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，缺頁(yè)次數(shù)反而增加的奇怪現(xiàn)象。這種現(xiàn)象稱為belady現(xiàn)象。,圖5.24 fifo算法的belady現(xiàn)象,下面的例子可以用來(lái)說(shuō)明fifo算法的正常換頁(yè)情況和belady現(xiàn)象。例: 設(shè)進(jìn)程p共有8頁(yè)，且已在內(nèi)存中分配有3個(gè)頁(yè)面，程序訪問(wèn)內(nèi)存的順序(訪問(wèn)串)為7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。 圖5.25 belady現(xiàn)象示例(1) 缺頁(yè)率

17、為12/17=70.5%,圖5.26 belady現(xiàn)象示例(2) 如果給進(jìn)程p分配4個(gè)頁(yè)面，共發(fā)生9次缺頁(yè)，其缺頁(yè)率為9/17=52.9%,設(shè)進(jìn)程p可分為5頁(yè)，訪問(wèn)串為1，2，3，4，1，2，5，1，2，3，4，5。當(dāng)進(jìn)程p分得3個(gè)頁(yè)面時(shí)，執(zhí)行過(guò)程中內(nèi)存頁(yè)面變化如圖5.27所示。 圖5.27 belady現(xiàn)象示例(3) 缺頁(yè)9次，其缺頁(yè)率為9/12=75%。,如果為進(jìn)程p分配4個(gè)內(nèi)存頁(yè)面 圖5.28 belady現(xiàn)象示例(4) 缺頁(yè)次數(shù)為10次。即缺頁(yè)率=10/12=83.3%。 先進(jìn)先出算法產(chǎn)生belady現(xiàn)象的原因在于它根本沒(méi)有考慮程序執(zhí)行的動(dòng)態(tài)特征。,(3) 最近最久未使用頁(yè)面置換算法(

18、least recently used)。 該算法的基本思想是: 當(dāng)需要淘汰某一頁(yè)時(shí)，選擇離當(dāng)前時(shí)間最近的一段時(shí)間內(nèi)最久沒(méi)有使用過(guò)的頁(yè)先淘汰。 常用的近似算法有: a) 最不經(jīng)常使用頁(yè)面淘汰算法lfu(least frequently used)。增設(shè)一個(gè)訪問(wèn)計(jì)數(shù)器 b) 最近沒(méi)有使用頁(yè)面淘汰算法nur。該算法在需要淘汰某一頁(yè)時(shí)，從那些最近一個(gè)時(shí)期內(nèi)未被訪問(wèn)的頁(yè)中任選一頁(yè)淘汰。增設(shè)一個(gè)訪問(wèn)位 (4) 理想型淘汰算法opt(optimal replacement algorithm)。,5.4.5 存儲(chǔ)保護(hù) 頁(yè)式管理可以為內(nèi)存提供兩種方式的保護(hù)。一種是地址越界保護(hù)，另一種是通過(guò)頁(yè)表控制對(duì)內(nèi)存信息

19、的存取操作方式以提供保護(hù)。 地址越界保護(hù)可由地址變換機(jī)構(gòu)中的控制寄存器的值頁(yè)表長(zhǎng)度和所要訪問(wèn)的虛地址相比較來(lái)完成。 存取控制保護(hù)的實(shí)現(xiàn)則是在頁(yè)表中增加相應(yīng)的保護(hù)位即可。,5.4.6 頁(yè)式管理的優(yōu)缺點(diǎn) 優(yōu)點(diǎn): (1) 有效地解決了碎片問(wèn)題。 (2) 動(dòng)態(tài)頁(yè)式管理提供了內(nèi)存和外存統(tǒng)一管理的虛存實(shí)現(xiàn)方式 主要缺點(diǎn)是: 要求有相應(yīng)的硬件支持 (2) 增加了系統(tǒng)開(kāi)銷 (3) 請(qǐng)求調(diào)頁(yè)的算法如選擇不當(dāng)，有可能產(chǎn)生抖動(dòng)現(xiàn)象。 (4) 雖然消除了碎片，但每個(gè)作業(yè)或進(jìn)程的最后一頁(yè)內(nèi)總有一部分空間得不到利用。如果頁(yè)面較大 ，則這一部分的損失仍然較大。,5.5 段式與段頁(yè)式管理 5.5.1 段式管理的基本思想 段式

20、管理的基本思想是: 把程序按內(nèi)容或過(guò)程(函數(shù))關(guān)系分成段，每段有自己的名字。一個(gè)用戶作業(yè)或進(jìn)程所包含的段對(duì)應(yīng)于一個(gè)二維線性虛擬空間，也就是一個(gè)二維虛擬存儲(chǔ)器。 段式管理程序以段為單位分配內(nèi)存 有利于:不同作業(yè)或進(jìn)程之間共享 動(dòng)態(tài)鏈接,5.5.2 段式管理的實(shí)現(xiàn)原理 1. 段式虛存空間 每個(gè)段是一個(gè)首地址為零的、連續(xù)的一維線性空間。 段式管理把一個(gè)進(jìn)程的虛地址空間設(shè)計(jì)成二維結(jié)構(gòu)，即段號(hào)s 與段內(nèi)相對(duì)地址w。,2. 段式管理的內(nèi)存分配與釋放 段式管理中以段為單位分配內(nèi)存，每段分配一個(gè)連續(xù)的內(nèi)存區(qū)。 同一進(jìn)程所包含的各段之間不要求連續(xù)。 段式管理的內(nèi)存分配與釋放與可變分區(qū)相同,另一種情況: 內(nèi)存中沒(méi)

21、有足夠的空閑區(qū)滿足調(diào)入段的內(nèi)存要求時(shí) -置換算法 一次調(diào)入時(shí)所需淘汰的段數(shù)與段的大小有關(guān),圖5.29 缺段中斷處理過(guò)程,圖5.30 段表,3. 段式管理的地址變換 (1) 段表(segment mapping table),(2) 動(dòng)態(tài)地址變換 通過(guò)訪問(wèn)段表寄存器，得到該進(jìn)程的段表始址從而可開(kāi)始訪問(wèn)段表。由虛地址中的段號(hào)s為索引，查段表。若該段在內(nèi)存，則判斷其存取控制方式是否有錯(cuò)。如果存取控制方式正確，則從段表相應(yīng)表目中查出該段在內(nèi)存的起始地址，并將其和段內(nèi)相對(duì)地址w相加，從而得到實(shí)際內(nèi)存地址。 不在內(nèi)存，則產(chǎn)生缺段中斷,找到足夠長(zhǎng)度的空閑區(qū)來(lái)裝入所需要的段。如果內(nèi)存中的可用空閑區(qū)總數(shù)小于所要

22、求的段長(zhǎng)時(shí)，則檢查段表中訪問(wèn)位，以淘汰那些訪問(wèn)概率低的段并將需要段調(diào)入。 段式管理時(shí)的地址變換過(guò)程也必須經(jīng)過(guò)二次以上的內(nèi)存訪問(wèn)。 高速聯(lián)想寄存器的方法也可以用在段式地址變換中。,圖5.31 段式地址變換過(guò)程,圖5.32 段式系統(tǒng)中共享內(nèi)存副本,4. 段的共享與保護(hù) (1) 段的共享,段表中可設(shè)立相應(yīng)的共享位來(lái)判別該段是否正被某個(gè)進(jìn)程調(diào)用,(2) 段的保護(hù) 段式管理的保護(hù)主要有兩種。 一種是地址越界保護(hù)法， 段表中的段長(zhǎng)項(xiàng)與虛擬地址中的段內(nèi)相對(duì)地址比較進(jìn)行的。若段內(nèi)相對(duì)地址大于段長(zhǎng)，系統(tǒng)就會(huì)產(chǎn)生保護(hù)中斷。不過(guò)，在允許段動(dòng)態(tài)增長(zhǎng)的系統(tǒng)中，段內(nèi)相對(duì)地址大于段長(zhǎng)是允許的。為此，段表中設(shè)置相應(yīng)的增補(bǔ)位以

23、指示該段是否允許該段動(dòng)態(tài)增長(zhǎng)。 另一種是存取方式控制保護(hù)法。,5.5.3 段式管理的優(yōu)缺點(diǎn) (1) 段式管理也提供了內(nèi)外存統(tǒng)一管理的虛存實(shí)現(xiàn) (2) 在段式管理中，段長(zhǎng)可根據(jù)需要?jiǎng)討B(tài)增長(zhǎng)。 便于對(duì)具有完整邏輯功能的信息段進(jìn)行共享。 (4) 便于實(shí)現(xiàn)動(dòng)態(tài)鏈接。 要求有更多的硬件支持。這就提高了機(jī)器成本。 在碎片問(wèn)題以及為了消除碎片所進(jìn)行的合并等問(wèn)題上較分頁(yè)式管理要差。 允許段的動(dòng)態(tài)增長(zhǎng)也會(huì)給系統(tǒng)管理帶來(lái)一定的難度和開(kāi)銷。 段式管理的另一個(gè)缺點(diǎn)就是每個(gè)段的長(zhǎng)度受內(nèi)存可用區(qū)大小的限制。 和頁(yè)式管理一樣，段式管理系統(tǒng)在選擇淘汰算法時(shí)也必須十分慎重，否則也有可能產(chǎn)生抖動(dòng)現(xiàn)象。,5.5.4 段頁(yè)式管理的基

24、本思想 5.5.5 段頁(yè)式管理的實(shí)現(xiàn)原理 1. 虛地址的構(gòu)成 虛擬地址由三部分組成: 即段號(hào)s，頁(yè)號(hào)p和頁(yè)內(nèi)相對(duì)地址d。如下所示:,圖5.33 段頁(yè)式管理中段表、頁(yè)表與內(nèi)存的關(guān)系,2. 段表和頁(yè)表,3. 動(dòng)態(tài)地址變換過(guò)程 至少需要訪問(wèn)三次以上的內(nèi)存。 為了提高地址轉(zhuǎn)換速度，設(shè)置快速聯(lián)想寄存器就顯得比段式管理或頁(yè)式管理時(shí)更加需要。,圖5.34 段頁(yè)式地址變換,段頁(yè)式管理的地址變換機(jī)構(gòu),段頁(yè)式管理優(yōu)缺點(diǎn): 具有頁(yè)式管理和段式管理二者的優(yōu)點(diǎn)。 但反過(guò)來(lái)說(shuō)，由于管理軟件的增加，復(fù)雜性和開(kāi)銷也就隨之增加了。另外，需要的硬件以及占用的內(nèi)存也有所增加。更重要的是，如果不采用聯(lián)想寄存器的方式提高cpu的訪內(nèi)速

25、度，將會(huì)使得執(zhí)行速度大大下降。,5.6 局部性原理和抖動(dòng)問(wèn)題 動(dòng)態(tài)頁(yè)式管理，段式管理以及段頁(yè)式管理都提供了一種將內(nèi)存和外存統(tǒng)一管理的實(shí)現(xiàn)方法。然而，由于上述實(shí)現(xiàn)方法實(shí)質(zhì)上要在內(nèi)存和外存之間交換信息，因此，就要不斷地啟動(dòng)外部設(shè)備以及相應(yīng)的處理過(guò)程。一般來(lái)說(shuō)，計(jì)算機(jī)系統(tǒng)的外部存儲(chǔ)器具有較大的容量而訪問(wèn)速度并不高。為了進(jìn)行數(shù)據(jù)的讀寫而涉及到的一系列處理程序也要耗去大量的時(shí)間。如果內(nèi)存和外存之間數(shù)據(jù)交換頻繁，勢(shì)必會(huì)造成對(duì)輸入/輸出設(shè)備的巨大壓力和使得機(jī)器的主要開(kāi)銷大多用在反復(fù)調(diào)入調(diào)出數(shù)據(jù)和程序段上，從而無(wú)法完成用戶所要求的工作。因此，要求在內(nèi)存中存放一個(gè)不小于最低限度的程序段或數(shù)據(jù)，而且它們必須是那些

26、正在被調(diào)用，或那些即將被調(diào)用的部分。,由模擬實(shí)驗(yàn)知道，在幾乎所有的程序的執(zhí)行中，在一段時(shí)間內(nèi)，cpu總是集中地訪問(wèn)程序中的某一個(gè)部分而不是隨機(jī)地對(duì)程序所有部分具有平均訪問(wèn)概率。把這種現(xiàn)象稱為局部性原理。與cpu訪問(wèn)該局部?jī)?nèi)的程序和數(shù)據(jù)的次數(shù)相比，該局部段的移動(dòng)速率相當(dāng)慢。這就使得前面所討論的頁(yè)式管理、段式管理以及段頁(yè)式管理所實(shí)現(xiàn)的虛存系統(tǒng)成為可能。 但是，如果不能正確地將那些系統(tǒng)所需要的局部段放入內(nèi)存的話，則顯然系統(tǒng)的效率會(huì)大大降低，甚至無(wú)法有效地工作。 試驗(yàn)表明，任何程序在局部性放入時(shí)，都有一個(gè)臨界值要求。當(dāng)內(nèi)存分配小于這個(gè)臨界值時(shí)，內(nèi)存和外存之間的交換頻率將會(huì)急劇增加，而內(nèi)存分配大于這個(gè)臨

27、界值時(shí)，再增加內(nèi)存分配也不能顯著減少交換次數(shù)。,這個(gè)內(nèi)存要求的臨界值被稱為工作集。圖5.35說(shuō)明這種情況。 圖5.35 內(nèi)存與交換次數(shù)的關(guān)系,一個(gè)進(jìn)程執(zhí)行過(guò)程中缺頁(yè)(missing page)的發(fā)生有兩種可能。一種是并發(fā)進(jìn)程所要求的工作集總和大于內(nèi)存可提供的可用區(qū)。這時(shí)，系統(tǒng)將無(wú)法正常工作，因?yàn)槿狈ψ銐虻目臻g裝入所需要的程序和數(shù)據(jù)。另一種可能性是，雖然存儲(chǔ)管理程序?yàn)槊總€(gè)并發(fā)進(jìn)程分配了足夠的工作集，但系統(tǒng)無(wú)法在開(kāi)始執(zhí)行前選擇適當(dāng)?shù)某绦蚨魏蛿?shù)據(jù)進(jìn)入內(nèi)存。這種情況下，只能依靠執(zhí)行過(guò)程中，當(dāng)cpu發(fā)現(xiàn)所要訪問(wèn)的指令或數(shù)據(jù)不在內(nèi)存時(shí)，由硬件中斷后轉(zhuǎn)入中斷處理程序，將所需要的程序段和數(shù)據(jù)調(diào)入。這是一種很自

28、然的處理方法。,當(dāng)給進(jìn)程分配的內(nèi)存小于所要求的工作集時(shí)，由于內(nèi)存外存之間交換頻繁，訪問(wèn)外存時(shí)間和輸入/輸出處理時(shí)間大大增加，反而造成cpu因等待數(shù)據(jù)空轉(zhuǎn)，使得整個(gè)系統(tǒng)性能大大下降，這就造成了系統(tǒng)抖動(dòng)。 可以利用統(tǒng)計(jì)模型進(jìn)一步分析工作集與抖動(dòng)之間的關(guān)系。 設(shè)r為cpu在內(nèi)存中存取一個(gè)內(nèi)存單元的時(shí)間，t為從外存中讀出一頁(yè)數(shù)據(jù)所需時(shí)間，p(s)為cpu訪問(wèn)內(nèi)存時(shí)，所訪問(wèn)的頁(yè)正好不在內(nèi)存的概率，這里s是當(dāng)前進(jìn)程在內(nèi)存中的工作集。 顯然，在虛存情況下存取一個(gè)內(nèi)存單元的平均時(shí)間可描述為t=r+p(s)*t,由程序模擬可知，p(s)=ae-bs 這里， 0a1b，ae-bsr 另外，假定內(nèi)存中各并發(fā)進(jìn)程具有

29、相同的統(tǒng)計(jì)特性，而且對(duì)于一個(gè)并發(fā)進(jìn)程來(lái)說(shuō)，只有發(fā)生缺頁(yè)時(shí)才變成等待狀態(tài)。這是為了簡(jiǎn)化討論而忽略了外部設(shè)備和進(jìn)程通信功能的存在。 由于訪問(wèn)外存一個(gè)頁(yè)面的速度為t，且缺頁(yè)發(fā)生的概率為p(s)，則在處理機(jī)訪問(wèn)一個(gè)內(nèi)存單元的r時(shí)間內(nèi)，平均每秒引起的內(nèi)外存之間頁(yè)傳送率為p(s)/r。也就是每r/p(s) 秒需要從外存向內(nèi)存?zhèn)魉鸵豁?yè)。從而 ，對(duì)于一個(gè)在虛存范圍內(nèi)執(zhí)行的進(jìn)程，它可以處于三種可能的狀態(tài)之中，即: (1) t r/p(s)(2) t r/p(s)(3) t=r/p(s),對(duì)于第一種情況，由于頁(yè)傳送速度大于訪問(wèn)外存頁(yè)面的速度，因此，進(jìn)程在執(zhí)行過(guò)程中發(fā)生缺頁(yè)的次數(shù)較少，并不經(jīng)常從外存調(diào)頁(yè)。 但是，在

30、第二種情況時(shí)，由于內(nèi)外存之間的頁(yè)面?zhèn)魉退俣纫呀?jīng)小于訪問(wèn)外存頁(yè)面速度，因此，進(jìn)程在執(zhí)行過(guò)程中發(fā)生缺頁(yè)的次數(shù)已經(jīng)多到外存供不應(yīng)求的地步。事實(shí)上，這時(shí)的系統(tǒng)已處于抖動(dòng)狀態(tài)。 第三種情況是一種較理想的情況，即進(jìn)程在執(zhí)行過(guò)程中所需要的頁(yè)數(shù)正好等于從外存可以調(diào)入的頁(yè)數(shù)。此時(shí)該進(jìn)程在內(nèi)存中占有最佳工作集。 根據(jù)以上討論可知，一個(gè)進(jìn)程在內(nèi)存中占有最佳工作集的條件是: p(w)=r/t 這里，r是cpu訪問(wèn)內(nèi)存單元所需平均時(shí)間，t是訪問(wèn)外存一個(gè)頁(yè)面所需平均時(shí)間。,因?yàn)?p(w) 可表示為p(w)=ae-bw 從而有，w=ln(at/r)/b 即，與內(nèi)存存取速度r相比，若外存?zhèn)魉退俣仍铰?，所需工作集就越大?當(dāng)然，上面討論是在作了許多近似的情況下得出的結(jié)論。事實(shí)上，由于各進(jìn)程所包含的程序段多少，選用的淘汰算法等不一樣，工作集的選擇也不一樣。一般來(lái)說(shuō)，選擇工作集有靜態(tài)和動(dòng)態(tài)兩種選擇方法，這里不再進(jìn)一步介紹。 另外，由以上討論，我們可以找出解決抖動(dòng)問(wèn)題的幾種關(guān)鍵辦法。,抖動(dòng)只有在 tr/p(s) 時(shí)才會(huì)發(fā)生。而p(s)等于ae-bs是一個(gè)與工作集s、參數(shù)a和b有關(guān)的概率值。p(s)是可以改變的。對(duì)于給定的系統(tǒng)來(lái)說(shuō)，t和r則是一個(gè)很難改變的數(shù)字。顯然，解決抖動(dòng)問(wèn)題的最關(guān)鍵辦法是將p(s)減少到使t=r/p(s)。這只需要: (1) 增加s，也就是擴(kuò)大工作集，或是 (2) 改變參數(shù)a和b，