搜索
1作業系統第八章記憶體管理2第八章記憶體管理背景介紹位址空間位址連結重疊置換連續配置分頁分段摘要3目標與趨勢目標追蹤記憶體空間使用與否配置記憶體給需要的行程回收行程釋放出的記憶體有效率的置換（swapping）方法趨勢程式成長的速度快於記憶體成長的速度多媒體應用環境，使用更多的記憶體4位址空間記憶體位址邏輯位址，邏輯位址空間實體位址，實體位址空間執行程式時，邏輯與實體空間的位址轉換載入器（loader）：在主記憶體中尋找一塊可供使用的記憶體空間來載入程式基底暫存器（baseregister）：又名重定址暫存器，存放邏輯位址轉換成實體位址的基底值記憶體管理單元（memorymanagementunit,MMU）：負責將邏輯位址加上基底值，以轉換成實體位址5邏輯位址空間到實體位址空間的轉換記憶體管理單元邏輯位址空間500501012使用者程式邏輯位址500主記憶體使用者程式實體位址空間實體位址重定位暫存器6位址連結（1）當許多行程都要求將程式載入記憶體時：行程均進入輸入佇列依據排程器的排程結果選擇一個行程載入行程執行時，從記憶體取得指令與資料﹔執行結束後，會釋放所佔有的記憶體空間位址轉換的步驟：原始程式中的位址：以符號表示編譯器或組譯器：將符號所指之位址連結（binding）到一可重新定址的相對位址鏈結編譯器或載入器：將可重新定址的位址連結到記憶體中的絕對實體位址7位址連結（2）對於同一份資料或指令而言，所謂「位址」是隨時間而變的資料或指令連結到實體位址的動作可在下列任一階段完成編譯階段已確定程式要在記憶體的某個位址執行當起始位址改變，程式必須重新編譯，以產生新的絕對位址的程式碼8位址連結（3）載入階段不知道程式將在記憶體何處執行程式需編譯成可重新定址的程式碼，當起始位址改變，程式碼只需重新載入例：動態鏈結程式庫執行階段若在執行時，行程會從一記憶體區塊移動到另一區塊﹔或是內含執行時才能確定的資料型態例：大部分現代的作業系統中，動態產生行程或執行緒9程式執行前的處理過程原始程式printf.c原始程式main.c目的模組printf.o目的模組main.o編譯器或組譯器鏈結編譯器其他目的模組載入模組main載入器記憶體10重疊（1）目的：解決記憶體容量的限制做法：在編譯時，將程式與資料分割成多個獨立區域﹔在執行時，記憶體中只保留有需要的區段重疊驅動器：載入目前要用的區段若有區段可共用記憶體，新載入的區段會覆蓋舊區段11重疊（2）多重重疊：造成程式設計師的負擔，一般會避免使用，因為：區段分割太多置換次數過多降低程式執行效能區段分割太少可重疊的程式部分過少記憶體可能不夠，系統效能降低除外：嵌入式系統（記憶體有限，沒有虛擬記憶體）12重疊（3）主記憶體程式依序執行321作業系統重疊驅動器未使用的空間起始區段運算區段輸出區段使用者程式與資料13置換（1）時機：系統無足夠空間容納所有行程非執行中的行程暫時移到備份儲存體，要執行時再搬回記憶體中備份儲存體：一般而言指磁碟換出、置入過程CPU排程器決定下一個執行的行程分派程式到記憶體中尋找該行程若不存在且無足夠記憶體空間先換出某些行程在置入該行程時，需重新載入暫存器內容，將控制權交給該行程14置換兩個行程換出置入主記憶體作業系統使用者空間行程1行程2行程3備份儲存體行程315置換（2）產生內文切換的額外負擔時間浪費在資料傳遞上為了提高效率行程必須隨時告知作業系統行程對記憶體需求的變化以便作業系統只置換實際所需的記憶體空間，節省置換所消耗的時間16置換（3）發生記憶體存取的錯誤原因：置換出不處於閒置狀態的行程（例：置換出的行程正在等待非同步的I/O操作）解決方式：1.任何企圖作I/O操作的行程不會被置換2.只有進入作業系統緩衝區的行程才可作I/O操作，而作業系統與行程記憶體間的資料傳遞，只有在行程被置入時才可以進行17第八章記憶體管理背景介紹連續配置單一分割配置多重分割配置斷裂分頁分段摘要18記憶體分割1024K0作業系統使用者程式一部分供作業系統常駐使用放置位址常考量中斷向量的位址，因此作業系統常位於低位址另一部分供使用者行程使用配置方式：單一分割配置（單一使用者）多重分割配置（多元程式概念）19單一分割配置單一使用者記憶體分隔成兩部分，一用來常駐作業系統，剩餘僅供一個使用者行程執行缺點：僅讓一個行程執行，造成記憶體空間的浪費若行程執行I/O操作，CPU閒置，使整體系統效能降低若行程大小超過可用的記憶體空間，將導致程式無法執行（可能解決方法：重疊）20單一分割配置（2）如何保護作業系統與使用者程式不會遭到對方不當修改？利用基底暫存器與界線暫存器的輔助基底暫存器：存放最小的記憶體實體位址界線暫存器：存放邏輯位址範圍每一個邏輯位址都須小於界線暫存器的邏輯位址範圍邏輯位址＋基底暫存器內的數值記憶體的實體位址CPU排程器選定一行程分派程式將正確的值載入到基底和界線兩暫存器中CPU每存取一次邏輯位址都經由兩暫存器的核對轉換，確保作業系統與使用者程式不會互相影響21位址保護機制CPU主記憶體基底暫存器界限暫存器定址錯誤是否邏輯位址實體位址＜＋22多重分割配置(1)多元程式概念作業系統如何將可用的記憶體空間配置給正在輸入佇列中等待的多個使用者程式？將記憶體劃分成許多固定大小的區域或分割每個分割只能容納一個行程分割數目的多寡會影響到同時放置的使用者行程數量設計輸入佇列兩方法：單一工作佇列：所有的分割都對應到同一個輸入佇列記憶體使用率較高；程式的等待時間較一致多重工作佇列：每個分割均有一個對應的輸入佇列缺點：作業系統須針對每個程式找到適合的輸入佇列，會造成記憶體中雖有可用空間卻無法使用的情況23單一與多重佇列單一工作佇列主記憶體作業系統固定分割1固定分割2固定分割3固定分割4主記憶體作業系統固定分割1固定分割2固定分割3固定分割4多重工作佇列24多重分割下的系統保護邏輯位址作業系統固定分割1固定分割2固定分割3基底暫存器界限暫存器基底暫存器界限暫存器定址錯誤＜＋25多重分割配置（2）記憶體劃分成固定大小的分割之問題：若程式小於分割大小的行程，會造成記憶體空間的浪費而程式大於分割大小的行程，則因為需要跨越分割，增加系統額外的負擔解決方法：動態分割法依照程式執行時的大小，在記憶體中找到夠大的可用區塊給此行程使用需在作業系統維護一個表格，隨時記錄記憶體中哪些區塊使用中、哪些區塊空閒26多重分割配置（3）作業系統以動態分割法載入程式時，依據3種策略：最先符合法（FirstFit）：從第一個可用的區塊開始循序找起，只要找到夠大的空間，就把程式載入。最佳符合法（BestFit）：找到一個與載入程式大小最為接近的區塊，再把程式載入。最差符合法（WorstFit）：找到最大的區塊，再把程式載入。27多重分割配置（4）根據電腦模擬分析最先符合法與最佳符合法在搜尋時間和記憶體空間的使用率都優於最差符合法最先符合法的執行速度通常比最佳符合法與最差符合法要快若不考慮搜尋時間，行程大小變化較大的適合最佳符合法；反之，則適合最差符合法。行程執行結束後，作業系統將會釋放此行程所佔用的記憶體區塊檢查此被釋放區塊是否可與可用的相鄰區塊合併同時作業系統檢查輸入佇列中是否有程式正等待配置記憶體如果有，則檢查此新合併的區塊大小是否夠該行程所用。28斷裂？合併0K行程A200K行程B300K行程C100K未使用作業系統200K400K700K800K1024K行程A200K行程B300K行程C100K行程D150K行程E100K行程F300K輸入佇列0K行程A200K行程D150K行程C100K未使用作業系統200K400K700K800K1024K未使用行程E100K900K550K0K行程A200K行程D150K未使用作業系統200K400K800K1024K未使用行程E100K900K550K（a）（b）（c）29斷裂有記憶體空間卻無法用（記憶體區塊太小）外部斷裂因為行程持續地被載入與置換，使得可用的記憶體空間被分割成許多不連續的區塊雖然記憶體所剩空間總和足夠讓此行程執行，卻因為空間不連續，導致程式無法載入執行內部斷裂發生在以固定分割方式配置的記憶體當一個程式載入到固定大小的分割，假如程式小於此分割，則此分割剩餘空間無法被使用不能使用的空間散佈在各個分割內，造成輸入佇列中的程式無法順利載入執行，造成浪費30內部斷裂0固定分割作業系統200K400K550K行程A150K600K800K未使用31聚集解決外部斷裂的問題將記憶體中可用的不連續空間聚集成一大塊連續空間程式必須都可重新定位代價高，因為要搬動許多行程的實體記憶體空間0P2P3100K作業系統200K400K700K900K300K1200KP51000K0P2P3作業系統200K400K600K800K400K1200KP532第八章記憶體管理背景介紹連續配置分頁基本方法分頁表的結構多層分頁法反轉分頁表分段摘要33基本方法（1）程式可被不連續放置，沒有外部斷裂的問題將載入的程式分割成固定大小的分頁主記憶體也分割成固定大小的頁框，大小與分頁相同執行程式時，把程式所有的分頁載入記憶體任何可用的頁框中每個程式有一個分頁表，存有每分頁在記憶體中的起始位址。當程式的分頁被載入到主記憶體時，程式分頁表中記錄該分頁被載入至主記憶體的哪一個頁框中頁框表：作業系統須知道主記憶體中頁框使用與否、系統中總頁框數目有多少等資訊34分頁法01201程式22程式13程式1分頁0主記憶體磁碟10123456789頁程式2分頁表6012910程式1分頁表01232537程式1分頁2程式2分頁1程式1分頁1程式1分頁3程式2分頁3程式2分頁2頁框編號頁框35基本方法（2）CPU產生的邏輯位址分成兩部分：分頁碼為指向分頁表的索引頁偏移表示與該分頁起始位址的距離在分頁表中找到此分頁在實體記憶體中對應的基底位址後，再和頁偏移組合定義出實體記憶體位址分頁法仍有內部斷裂的問題如果一個程式所需要的記憶體大小不能被頁框大小整除，最後一個頁框就不會全部被使用而形成內部斷裂若使分頁大小縮小，就可節省因內部斷裂而產生記憶體空間浪費；但須更大空間儲存分頁表（分頁的數量增加）每個程式平均會有1/2分頁的內部斷裂36分頁邏輯位址空間與實體位址空間的轉換頁數p頁偏移d邏輯位址f分頁表pf頁偏移d實體位址實體記憶體37分頁表的結構（1）儲存分頁表：若儲存在主記憶體中，系統需作兩次記憶體存取，效率低解決方法：將分頁表放在關聯式記憶體（也稱位址查閱緩衝）中每筆資料有分頁碼，頁框編號兩欄位。關聯式記憶體以分頁碼為索引，平行地在相對的頁框中找尋很短的時間就可找尋到，時間複雜度為O(1)38分頁表的結構（2）實際上的做法（因關聯式記憶體昂貴）：使用主記憶體建立分頁表，將關聯式記憶體當成快取記憶體，只保存分頁表的部分內容若頁框編號在關聯式記憶體中找得到，就直接與頁偏移相加得到實體記憶體位址，否則再到分頁表中找尋在更新關聯式記憶體時，如果關聯式記憶體已經存滿，則系統必須置換掉其中一筆記錄（參考第9章的分頁置換規則）39使用TLB硬體支援的分頁法頁框編號TLB失誤TLB命中f分頁表pf頁偏移d實體位址頁數p頁偏移d邏輯位址TLB實體記憶體頁數40分頁表的結構（3）使用關聯式記憶體來儲存分頁表的效率：如果要尋找的分頁碼已經在關聯式記憶體中，則稱為命中，否則稱為失誤命中率的定義為〔命中次數/（命中次數+失誤次數）〕×100%例：假設存取關聯式記憶體的時間為20奈秒，直接存取主記憶體的時間為100奈秒。假設在關聯式記憶體內命中率為95%，則所需的時間為：41分頁表的結構（4）0.95×120ns+0.05×220ns=125ns其中120奈秒的20奈秒花費在關聯式記憶體中找尋（命中），100奈秒花費在存取主記憶體的資料；而220奈秒中的20奈秒花費在關聯式記憶體中找尋（失誤），100奈秒花費在主記憶體中找尋，另外100奈秒花費在存取主記憶體的資料適當地使用關聯式記憶體，可以降低主記憶體的存取時間，也可以節省成本42分頁表的結構（5）分頁的環境