作業(yè)系統(tǒng)第八章記憶體管理

1、作業(yè)系統(tǒng) 第八章 記憶體管理1.第八章 記憶體管理背景介紹位址空間位址連結(jié)重疊置換連續(xù)配置 分頁 分段 摘要 2目標(biāo)與趨勢目標(biāo)追蹤記憶體空間運(yùn)用與否配置記憶體給需求的行程回收行程釋放出的記憶體有效率的置換swapping方法趨勢程式成長的速度快於記憶體成長的速度多媒體應(yīng)用環(huán)境，運(yùn)用更多的記憶體3位址空間 記憶體位址邏輯位址，邏輯位址空間實(shí)體位址，實(shí)體位址空間執(zhí)行程式時，邏輯與實(shí)體空間的位址轉(zhuǎn)換載入器loader：在主記憶體中尋找一塊可供運(yùn)用的記憶體空間來載入程式基底暫存器base register：又名重定址暫存器，存放邏輯位址轉(zhuǎn)換成實(shí)體位址的基底值記憶體管理單元memory manageme

2、nt unit,MMU：負(fù)責(zé)將邏輯位址加上基底值，以轉(zhuǎn)換成實(shí)體位址4邏輯位址空間到實(shí)體位址空間的轉(zhuǎn)換記憶體管理單元邏輯位址空間500501012運(yùn)用者程式邏輯位址500主記憶體運(yùn)用者程式實(shí)體位址空間實(shí)體位址重定位暫存器5位址連結(jié)1 當(dāng)許多行程都要求將程式載入記憶體時：行程均進(jìn)入輸入佇列依據(jù)排程器的排程結(jié)果選擇一個行程載入行程執(zhí)行時，從記憶體獲得指令與資料執(zhí)行結(jié)束後，會釋放所佔(zhàn)有的記憶體空間位址轉(zhuǎn)換的步驟：原始程式中的位址：以符號表示編譯器或組譯器：將符號所指之位址連結(jié)binding到一可重新定址的相對位址鏈結(jié)編譯器或載入器：將可重新定址的位址連結(jié)到記憶體中的絕對實(shí)體位址6位址連結(jié)2 對於同一份

3、資料或指令而言，所謂位址是隨時間而變的資料或指令連結(jié)到實(shí)體位址的動作可在以下任一階段完成編譯階段已確定程式要在記憶體的某個位址執(zhí)行當(dāng)起始位址改變，程式必須重新編譯，以產(chǎn)生新的絕對位址的程式碼7位址連結(jié)3 載入階段不知道程式將在記憶體何處執(zhí)行程式需編譯成可重新定址的程式碼，當(dāng)起始位址改變，程式碼只需重新載入例：動態(tài)鏈結(jié)程式庫執(zhí)行階段假設(shè)在執(zhí)行時，行程會從一記憶體區(qū)塊移動到另一區(qū)塊或是內(nèi)含執(zhí)行時才干確定的資料型態(tài)例：大部分現(xiàn)代的作業(yè)系統(tǒng)中，動態(tài)產(chǎn)生行程或執(zhí)行緒8程式執(zhí)行前的處理過程原始程式printf.c原始程式main.c目的模組printf.o目的模組main.o編譯器或組譯器鏈結(jié)編譯器其他目

4、的模組載入模組main載入器記憶體9重疊1 目的：解決記憶體容量的限制做法：在編譯時，將程式與資料分割成多個獨(dú)立區(qū)域在執(zhí)行時，記憶體中只保管有需求的區(qū)段重疊驅(qū)動器：載入目前要用的區(qū)段假設(shè)有區(qū)段可共用記憶體，新載入的區(qū)段會覆蓋舊區(qū)段10重疊2 多重重疊：呵斥程式設(shè)計(jì)師的負(fù)擔(dān)，普通會防止運(yùn)用，因?yàn)椋簠^(qū)段分割太多置換次數(shù)過多降低程式執(zhí)行效能區(qū)段分割太少可重疊的程式部分過少記憶體能夠不夠，系統(tǒng)效能降低除外：嵌入式系統(tǒng)記憶體有限，沒有虛擬記憶體 11重疊3主記憶體程式依序執(zhí)行321作業(yè)系統(tǒng)重疊驅(qū)動器 未運(yùn)用的 空間起始區(qū)段運(yùn)算區(qū)段輸出區(qū)段運(yùn)用者程式與資料12置換1時機(jī)：系統(tǒng)無足夠空間容納一切行程非執(zhí)行中

5、的行程暫時移到備份儲存體，要執(zhí)行時再搬回記憶體中備份儲存體：普通而言指磁碟換出、置入過程CPU排程器決定下一個執(zhí)行的行程分派程式到記憶體中尋找該行程假設(shè)不存在且無足夠記憶體空間先換出某些行程在置入該行程時，需重新載入暫存器內(nèi)容，將控制權(quán)交給該行程13置換兩個行程換出置入主記憶體作業(yè)系統(tǒng)運(yùn)用者空間行程1行程2行程3備份儲存體行程314置換2產(chǎn)生內(nèi)文切換的額外負(fù)擔(dān)時間浪費(fèi)在資料傳遞上為了提高效率行程必須隨時告知作業(yè)系統(tǒng)行程對記憶體需求的變化以便作業(yè)系統(tǒng)只置換實(shí)際所需的記憶體空間，節(jié)省置換所耗費(fèi)的時間15置換3發(fā)生記憶體存取的錯誤緣由：置換出不處於閒置狀態(tài)的行程例：置換出的行程正在等待非同步的 I/

6、O 操作解決方式：任何企圖作I/O操作的行程不會被置換只需進(jìn)入作業(yè)系統(tǒng)緩衝區(qū)的行程才可作I/O操作，而作業(yè)系統(tǒng)與行程記憶體間的資料傳遞，只需在行程被置入時才可以進(jìn)行16第八章 記憶體管理背景介紹連續(xù)配置單一分割配置 多重分割配置 斷裂 分頁 分段 摘要 17記憶體分割1024K0作業(yè)系統(tǒng)運(yùn)用者程式一部分供作業(yè)系統(tǒng)常駐運(yùn)用放置位址常考量中斷向量的位址，因此作業(yè)系統(tǒng)常位於低位址另一部分供運(yùn)用者行程運(yùn)用配置方式：單一分割配置單一運(yùn)用者 多重分割配置多元程式概念 18單一分割配置單一運(yùn)用者記憶體分隔成兩部分，一用來常駐作業(yè)系統(tǒng)，剩餘僅供一個運(yùn)用者行程執(zhí)行缺點(diǎn)：僅讓一個行程執(zhí)行，呵斥記憶體空間的浪費(fèi)假設(shè)

7、行程執(zhí)行 I/O 操作， CPU 閒置，使整體系統(tǒng)效能降低假設(shè)行程大小超過可用的記憶體空間，將導(dǎo)致程式無法執(zhí)行能夠解決方法：重疊19單一分割配置2如何保護(hù)作業(yè)系統(tǒng)與運(yùn)用者程式不會遭到對方不當(dāng)修正？利用基底暫存器與界線暫存器的輔助基底暫存器：存放最小的記憶體實(shí)體位址界線暫存器：存放邏輯位址範(fàn)圍每一個邏輯位址都須小於界線暫存器的邏輯位址範(fàn)圍邏輯位址基底暫存器內(nèi)的數(shù)值記憶體的實(shí)體位址CPU排程器選定一行程分派程式將正確的值載入到基底和界線兩暫存器中CPU每存取一次邏輯位址都經(jīng)由兩暫存器的核對轉(zhuǎn)換，確保作業(yè)系統(tǒng)與運(yùn)用者程式不會相互影響20位址保護(hù)機(jī)制CPU主記憶體基底暫存器界限暫存器定址錯誤是否邏輯位

8、址實(shí)體位址21多重分割配置 (1)多元程式概念作業(yè)系統(tǒng)如何將可用的記憶體空間配置給正在輸入佇列中等待的多個運(yùn)用者程式？將記憶體劃分成許多固定大小的區(qū)域或分割 每個分割只能容納一個行程分割數(shù)目的多寡會影響到同時放置的運(yùn)用者行程數(shù)量 設(shè)計(jì)輸入佇列兩方法：單一任務(wù)佇列：一切的分割都對應(yīng)到同一個輸入佇列記憶體運(yùn)用率較高；程式的等待時間較一致 多重任務(wù)佇列：每個分割均有一個對應(yīng)的輸入佇列缺點(diǎn)：作業(yè)系統(tǒng)須針對每個程式找到適合的輸入佇列，會呵斥記憶體中雖有可用空間卻無法運(yùn)用的情況 22單一與多重佇列 單一任務(wù)佇列主記憶體作業(yè)系統(tǒng)固定分割 1固定分割 2固定分割 3固定分割 4主記憶體作業(yè)系統(tǒng)固定分割 1固定

9、分割 2固定分割 3固定分割 4多重任務(wù)佇列23多重分割下的系統(tǒng)保護(hù) 邏輯位址作業(yè)系統(tǒng)固定分割1固定分割2固定分割3基底暫存器界限暫存器基底暫存器界限暫存器定址錯誤24多重分割配置2記憶體劃分成固定大小的分割之問題：假設(shè)程式小於分割大小的行程，會呵斥記憶體空間的浪費(fèi)而程式大於分割大小的行程，則因?yàn)樾枨罂缭椒指?，添加系統(tǒng)額外的負(fù)擔(dān) 解決方法：動態(tài)分割法按照程式執(zhí)行時的大小，在記憶體中找到夠大的可用區(qū)塊給此行程運(yùn)用需在作業(yè)系統(tǒng)維護(hù)一個表格，隨時記錄記憶體中哪些區(qū)塊運(yùn)用中、哪些區(qū)塊空閒 25多重分割配置3作業(yè)系統(tǒng)以動態(tài)分割法載入程式時，依據(jù) 3 種戰(zhàn)略：最先符合法First Fit：從第一個可用的區(qū)

10、塊開始循序找起，只需找到夠大的空間，就把程式載入。最正確符合法Best Fit：找到一個與載入程式大小最為接近的區(qū)塊，再把程式載入。最差符合法Worst Fit：找到最大的區(qū)塊，再把程式載入。26多重分割配置4根據(jù)電腦模擬分析最先符合法與最正確符合法在搜尋時間和記憶體空間的運(yùn)用率都優(yōu)於最差符合法最先符合法的執(zhí)行速度通常比最正確符合法與最差符合法要快假設(shè)不考慮搜尋時間，行程大小變化較大的適合最正確符合法；反之，則適合最差符合法。 行程執(zhí)行結(jié)束後，作業(yè)系統(tǒng)將會釋放此行程所佔(zhàn)用的記憶體區(qū)塊檢查此被釋放區(qū)塊能否可與可用的相鄰區(qū)塊合併同時作業(yè)系統(tǒng)檢查輸入佇列中能否有程式正等待配置記憶體假設(shè)有，則檢查此新

11、合併的區(qū)塊大小能否夠該行程所用。27斷裂 ？合併0 K行程A 200 K行程B 300 K行程C 100 K未運(yùn)用作業(yè)系統(tǒng)200 K400 K700 K800 K1024 K行程A 200 K行程B 300 K行程C 100 K行程D 150 K行程E 100 K行程F 300 K輸入佇列0 K行程A 200 K行程D 150 K行程C 100 K未運(yùn)用作業(yè)系統(tǒng)200 K400 K700 K800 K1024 K未運(yùn)用行程E 100 K900 K550 K0 K行程A 200 K行程D 150 K未運(yùn)用作業(yè)系統(tǒng)200 K400 K800 K1024 K未運(yùn)用行程E 100 K900 K550

12、Kabc28斷裂有記憶體空間卻無法用記憶體區(qū)塊太小外部斷裂因?yàn)樾谐坛掷m(xù)地被載入與置換，使得可用的記憶體空間被分割成許多不連續(xù)的區(qū)塊雖然記憶體所剩空間總和足夠讓此行程執(zhí)行，卻因?yàn)榭臻g不連續(xù)，導(dǎo)致程式無法載入執(zhí)行內(nèi)部斷裂發(fā)生在以固定分割方式配置的記憶體當(dāng)一個程式載入到固定大小的分割，假設(shè)程式小於此分割，則此分割剩餘空間無法被運(yùn)用不能運(yùn)用的空間散佈在各個分割內(nèi)，呵斥輸入佇列中的程式無法順利載入執(zhí)行，呵斥浪費(fèi) 29內(nèi)部斷裂0固定分割作業(yè)系統(tǒng)200K400K550K行程A 150K600K800K未運(yùn)用30聚集解決外部斷裂的問題將記憶體中可用的不連續(xù)空間聚集成一大塊連續(xù)空間程式必須都可重新定位代價高，因

13、為要搬動許多行程的實(shí)體記憶體空間 0P2P3100K作業(yè)系統(tǒng)200K400K700K900K300K1200KP51000K0P2P3作業(yè)系統(tǒng)200K400K600K800K400K1200KP531第八章 記憶體管理背景介紹連續(xù)配置分頁根本方法分頁表的結(jié)構(gòu)多層分頁法反轉(zhuǎn)分頁表分段 摘要 32根本方法1程式可被不連續(xù)放置，沒有外部斷裂的問題將載入的程式分割成固定大小的分頁主記憶體也分割成固定大小的頁框，大小與分頁一樣執(zhí)行程式時，把程式一切的分頁載入記憶體任何可用的頁框中每個程式有一個分頁表，存有每分頁在記憶體中的起始位址。當(dāng)程式的分頁被載入到主記憶體時，程式分頁表中記錄該分頁被載入至主記憶體的

14、哪一個頁框中 頁框表：作業(yè)系統(tǒng)須知道主記憶體中頁框運(yùn)用與否、系統(tǒng)中總頁框數(shù)目有多少等資訊 33分頁法 01201程式22程式13程式1分頁0主記憶體磁碟10123456789頁程式 2 分頁表6012910程式 1 分頁表01232537程式1分頁2程式2分頁1程式1分頁1程式1分頁3程式2分頁3程式2分頁2頁框編號頁框34根本方法2CPU 產(chǎn)生的邏輯位址分成兩部分：分頁碼為指向分頁表的索引頁偏移表示與該分頁起始位址的距離 在分頁表中找到此分頁在實(shí)體記憶體中對應(yīng)的基底位址後，再和頁偏移組合定義出實(shí)體記憶體位址 分頁法仍有內(nèi)部斷裂的問題假設(shè)一個程式所需求的記憶體大小不能被頁框大小整除，最後一個頁

15、框就不會全部被運(yùn)用而構(gòu)成內(nèi)部斷裂假設(shè)使分頁大小縮小，就可節(jié)省因內(nèi)部斷裂而產(chǎn)生記憶體空間浪費(fèi)；但須更大空間儲存分頁表分頁的數(shù)量添加每個程式平均會有 1/2 分頁的內(nèi)部斷裂 35分頁邏輯位址空間與實(shí)體位址空間的轉(zhuǎn)換 頁數(shù)p頁偏移d邏輯位址f分頁表pf頁偏移d實(shí)體位址實(shí)體記憶體36分頁表的結(jié)構(gòu)1 儲存分頁表：假設(shè)儲存在主記憶體中，系統(tǒng)需作兩次記憶體存取，效率低解決方法：將分頁表放在關(guān)聯(lián)式記憶體也稱位址查閱緩衝中每筆資料有分頁碼，頁框編號兩欄位。關(guān)聯(lián)式記憶體以分頁碼為索引，平行地在相對的頁框中找尋很短的時間就可找尋到，時間複雜度為 O(1) 37分頁表的結(jié)構(gòu)2實(shí)際上的做法因關(guān)聯(lián)式記憶體昂貴：運(yùn)用主記憶

16、體建立分頁表，將關(guān)聯(lián)式記憶體當(dāng)成快取記憶體，只保管分頁表的部分內(nèi)容假設(shè)頁框編號在關(guān)聯(lián)式記憶體中找得到，就直接與頁偏移相加得到實(shí)體記憶體位址，否則再到分頁表中找尋 在更新關(guān)聯(lián)式記憶體時，假設(shè)關(guān)聯(lián)式記憶體已經(jīng)存滿，則系統(tǒng)必須置換掉其中一筆記錄參考第 9 章的分頁置換規(guī)則38運(yùn)用 TLB 硬體援助的分頁法 頁框編號TLB失誤TLB 命中f分頁表pf頁偏移d實(shí)體位址頁數(shù)p頁偏移d邏輯位址TLB實(shí)體記憶體頁數(shù)39分頁表的結(jié)構(gòu)3運(yùn)用關(guān)聯(lián)式記憶體來儲存分頁表的效率：假設(shè)要尋找的分頁碼已經(jīng)在關(guān)聯(lián)式記憶體中，則稱為命中，否則稱為失誤命中率的定義為命中次數(shù) / 命中次數(shù) + 失誤次數(shù) 100%例：假設(shè)存取關(guān)聯(lián)式記

17、憶體的時間為 20 奈秒，直接存取主記憶體的時間為 100 奈秒。假設(shè)在關(guān)聯(lián)式記憶體內(nèi)命中率為 95%，則所需的時間為：40分頁表的結(jié)構(gòu)40.95 120 ns + 0.05 220 ns = 125 ns其中 120 奈秒的 20 奈秒花費(fèi)在關(guān)聯(lián)式記憶體中找尋命中，100 奈秒花費(fèi)在存取主記憶體的資料；而 220 奈秒中的 20 奈秒花費(fèi)在關(guān)聯(lián)式記憶體中找尋失誤，100 奈秒花費(fèi)在主記憶體中找尋，另外 100 奈秒花費(fèi)在存取主記憶體的資料 適當(dāng)?shù)剡\(yùn)用關(guān)聯(lián)式記憶體，可以降低主記憶體的存取時間，也可以節(jié)省本錢41分頁表的結(jié)構(gòu)5分頁的環(huán)境中，記憶體的保護(hù)可以運(yùn)用分頁上面的保護(hù)位元來完成通常保管在分

18、頁表保護(hù)位元可以定義某一分頁是可讀、可寫或者兩者皆可每次的位址轉(zhuǎn)換均會去參考相對應(yīng)的保護(hù)位元；企圖以非保護(hù)位元所提供的動作來存取此分頁，將會引發(fā)例外中斷42分頁表的結(jié)構(gòu)6成效位元：當(dāng)此位元被設(shè)定為有效v時，表示所對應(yīng)的分頁目前在主記憶體中；假設(shè)此位元被設(shè)定成無效i，則表示所對應(yīng)的分頁在輔助記憶體中作業(yè)系統(tǒng)會設(shè)定每分頁的有效位元，以核對該分頁的存取動作；當(dāng)系統(tǒng)進(jìn)行位址轉(zhuǎn)換時，也會去檢查此位元，假設(shè)企圖存取無效的分頁也會引發(fā)例外中斷 43分頁表中的成效位元 Page 00v2v3v5v7v98v0i0123456分頁表Page 0Page 1Page 2Page 3Page 4Page 5Page

19、 1Page 2Page 3Page 4Page 5012345678Page n磁碟主記憶體0i7000001046812287欄數(shù)成效位元44兩個運(yùn)用者共用頁框 運(yùn)用分頁法另一項(xiàng)好處簡單達(dá)到程式碼共用分頁表1運(yùn)用者2運(yùn)用者1編輯器 1編輯器2資料 1編輯器1編輯器2資料 205分頁表2358資料 1編輯器1編輯器2資料 2123456783245多層分頁法1 不希望分頁表佔(zhàn)用連續(xù)的記憶體空間想把分頁表分成較小的單位儲存多層式分頁將分頁表也進(jìn)行分頁以兩層式的分頁來說，在由邏輯位址轉(zhuǎn)換成實(shí)體位址時；先以 P1 為索引到外層分頁表中找尋，所找到的記錄會指向一個相對應(yīng)的內(nèi)層分頁表然後再以 P2 為

20、索引到該內(nèi)層分頁表中找尋，所找到的記錄會指向一個頁框最後和頁偏移 d 相加成為實(shí)體記憶體位址 46兩層式分頁法 121010內(nèi)層分頁表P1P2d頁偏移內(nèi)層分頁外層分頁P(yáng)1P2主記憶體外層分頁表47多層分頁法2 64 位元的架構(gòu)不適合階層式的分頁方式外層分頁表將佔(zhàn)用太大的連續(xù)記憶體空間對於邏輯位址大於 32 位元的硬體架構(gòu)，可運(yùn)用雜湊分頁表利用雜湊函數(shù)將邏輯位址對應(yīng)到實(shí)體位址能夠發(fā)生雜湊碰撞而降低效率，但是可有效減少分頁表空間 48反轉(zhuǎn)分頁表1解決分頁表空間太大的問題：整個系統(tǒng)僅用一個分頁表行程辨識碼加上邏輯分頁與實(shí)體頁框是一對一的對應(yīng)反轉(zhuǎn)分頁表的記錄數(shù)目要與頁框一致反轉(zhuǎn)分頁表的架構(gòu)下一個邏輯位

21、址包含三個欄位：行程辨識碼PID、分頁碼、與頁偏移反轉(zhuǎn)分頁表中每個記錄包含：行程辨識碼與分頁碼兩欄位當(dāng)一個行程要進(jìn)行位址轉(zhuǎn)換，必須以 PID 與分頁碼當(dāng)索引，到反轉(zhuǎn)分頁表中找尋所屬的頁框編號，再與頁偏移相加就可以得到實(shí)體位址 49反轉(zhuǎn)分頁表2PIDPd邏輯位址i主記憶體反轉(zhuǎn)分頁表PIDPid實(shí)體位址50反轉(zhuǎn)分頁表3反轉(zhuǎn)分頁表可以降低儲存每個分頁表所需求的空間，但是搜尋分頁表所用的時間卻大量添加減輕此問題：運(yùn)用雜湊表格 從獲得邏輯位址開始到在記憶體中存得資料，至少需求兩次的記憶體讀?。阂淮问请s湊表格，另一次是反轉(zhuǎn)分頁表解決的辦法是利用類似關(guān)聯(lián)式記憶體的方式來加快搜尋在一個運(yùn)用反轉(zhuǎn)分頁表的系統(tǒng)中，

22、無法達(dá)到分頁共用的目的 51反轉(zhuǎn)分頁表雜湊表格 雜湊k雜湊表格反轉(zhuǎn)分頁表Mk插入TLB0頁框編號頁數(shù)52第八章 記憶體管理背景介紹連續(xù)配置分頁分段根本方法分頁式分段 摘要 53分段按照程式的邏輯功能將邏輯位址空間切割成許多分段每個分段的長度都不盡一樣，長度是由此分段中程式的大小來決定假設(shè)要參考分段中某一位元組，可以藉由此分段的起始位址配合段偏移來決定 54根本方法1一個行程的邏輯位址空間被分成許多分段，每個分段都有一個名稱和長度，也有一個分段編號一個行程的邏輯位址被分成兩個欄位：分段編號當(dāng)作分段表的索引與段偏移每個程式均有一個分段表，其中每一記錄都有：分段基底值：記錄分段在主記憶體中實(shí)際開始的

23、位址分段界限值：記錄該分段的大小，以防止程式執(zhí)行時超過該分段界限 55分段法的運(yùn)用主記憶體分段表分段編號s段偏移d邏輯位址長度起始位址d 長度定址錯誤是否56分段法分段表分段0主程式分段1函式分段2符號表位址長度510020015003200300300012分段0分段2分段1150018003200350051005300邏輯位址空間主記憶體57根本方法2分段表可以存放在快速的暫存器：節(jié)省對界限暫存器相加與基底暫存器比較的時間 主記憶體：對於有大量分段的程式而言，不宜放在快速暫存器中利用一個分段表基底暫存器來指向分段表；運(yùn)用一個分段表長度基底暫存器記錄分段大小 將分段基底值與段偏移相加，獲得要存取位元組的實(shí)體位址 缺點(diǎn)：每個邏輯位址需求對實(shí)際記憶體存取兩次，所以速度比較慢解決方法：也可利用關(guān)聯(lián)式暫存器儲存經(jīng)常會被運(yùn)用的分段表記錄58配合 STLR 與 STBR 的分段法 主記憶體分段表分段編碼s段偏移d邏輯位址長度起始位址d 長