记忆体管理课件.ppt

1、著作權所有 旗標出版股份有限公司,1,第 4 章 記憶體管理,著作權所有 旗標出版股份有限公司,2,本章提要,實體記憶體的分割方式 分頁 分段 置換,著作權所有 旗標出版股份有限公司,3,4-1實體記憶體的分割方式-由簡而繁,單一分割區的配置 多個行程時的記憶體配置 固定長度的多重分割區 變動長度的多重分割區 好搭檔系統,著作權所有 旗標出版股份有限公司,4,單一分割區的配置,將記憶體空間分成兩塊一塊給作業系統使用另一塊則給行程使用 可以利用硬體的基底暫存器來避免行程存取到作業系統的記憶體位址 如果程式所產生的位址小於基底暫存器中的位址則會產生定址錯誤的例外中斷,著作權所有 旗標出版股份有限公

2、司,5,定址錯誤 例外中斷,是,否,圖4-1.a 合法的邏輯位址,實體位址,基底暫存器,100,記憶體,0,Max-1,實體記憶體位址,100,112,作業系統,使用者行程,112,著作權所有 旗標出版股份有限公司,6,定址錯誤 例外中斷,是,否,圖4-1.b 存取到作業系統的記憶體位址,實體位址,基底暫存器,100,記憶體,0,Max-1,實體記憶體位址,100,作業系統,使用者行程,001,001,著作權所有 旗標出版股份有限公司,7,課堂練習,假設作業系統是位於實體記憶體由0開始的連續區段之中，且長度為256KB 請問基底暫存器的值至少應該設為多少？ 請問下列位址何者為合法的行程位址？

3、300K 25K 300,著作權所有 旗標出版股份有限公司,8,練習解答,基底暫存器的值：大於等於256K 行程： 300K-合法 25K-不合法 600-不合法,著作權所有 旗標出版股份有限公司,9,重定址暫存器,另一種保護的方式是使用重定址暫存器，用來存放行程的啟始位址 在編譯的時候將程式從0開始配置 邏輯位址：程式好像是運作在一個從0開始的一大片連續的邏輯位址空間中 實體位址：由記憶體管理硬體負責將邏輯位址轉換為在實體記憶體中的真正位址,著作權所有 旗標出版股份有限公司,10,圖4-2 利用重定址暫存器的記憶體位址轉換,邏輯位址,重定址暫存器,100,記憶體,0,Max-1,實體記憶體位

4、址,32,100,132,使用者行程,作業系統,著作權所有 旗標出版股份有限公司,11,程式的載入,絕對程式碼：在程式編譯時預先決定這支程式要放在實體記憶體的哪個位置執行則編譯出來的程式碼邏輯位址會等於實體位址 缺點在於程式碼只能放在記憶體的固定位置當多個行程要共享記憶體時就可能彼此產生干擾 可重定址程式碼：在編譯時是從0開始配置位址，然後在載入時才決定要放在哪個位置 必須透過邏輯位址加上重定址暫存器的內容，才能取得行程的實體位址 如果需要改變行程在實體記憶體中的位置時只要在搬移行程之後改變重定址暫存器的值就可以了,著作權所有 旗標出版股份有限公司,12,多個行程時的記憶體配置-固定長度,將記

5、憶體切割為相同大小的分割區作業系統只需要記住每個行程分配到哪個分割區就可以了-最簡單的多行程配置方式 因為分割區的長度都相同所以在開機的時候就可以設定長度暫存器的值 然後在某個行程取得CPU控制權的時候作業系統就將重定址暫存器的內容重新設定到該行程所在的分割區 如果將記憶體分割成相同大小的分割區有些區域內就會剩下很多空間，稱為內部碎片 可以將記憶體分割為大小不等的數個固定長度分割區，並且將不同大小的行程配置到不同長度的分割區中 當輪到某個行程使用CPU時除了要設定重定址暫存器之外作業系統還必須將長度暫存器的值設定為該行程所在分割區的長度,著作權所有 旗標出版股份有限公司,13,變動長度的多重分

6、割區,另一種減少內部碎片的方法就是不要事先分割記憶體而是根據目前的記憶體使用情況與即將要載入的行程長度來動態分割記憶體 可以將內部碎片降至最低但是卻可能造成外部碎片 如果分割區配置的選擇不當，就可能會加重外部碎片的問題 可利用聚集法重新搬移各個行程將這些碎片聚集成為完整的一大塊連續空間,著作權所有 旗標出版股份有限公司,14,圖4-3 外部碎片範例,實體記憶體,A,B,C,D,Free,(a),實體記憶體,A,B,D,Free,(b),(c),Free,行程 C 結束 行程 F 想要進入,F C F Free F C + Free,實體記憶體,A,B,D,E,外部碎片 (無法配置給F）,E,E

7、,F,如果重新調整 就足夠配置給 F,Free,著作權所有 旗標出版股份有限公司,15,分割區的選擇演算法,先適法：從記憶體的開頭開始搜尋閒置的記憶體空洞然後將行程放入第一個可以容納的洞中 次適法：從上次搜尋結束的位置往下繼續搜尋以改善搜尋的時間 最適法：從所有的閒置區域中找出長度大於這個行程而且最接近這個行程的洞 最不適法：將最大的洞分配給行程,著作權所有 旗標出版股份有限公司,16,圖4-4 分割區的選擇演算法範例,A,B,C,D,上次配置結束位置,新行程,記憶體,First Fit,Best Fit,Next Fit,Worst Fit,著作權所有 旗標出版股份有限公司,17,課堂練習,

8、A (500K),B (200K),E (330K),D (700K),上次配置結束位置,300K,新行程,C (400K),Q：假設記憶體目前的配置狀況如圖，白色區域為尚未使用的部份。請分別指出使用先適法、次適法、最適法、與最不適法時： 新行程會被分配到哪個區域？ 所產生的內部碎片大小為何？,著作權所有 旗標出版股份有限公司,18,解答,著作權所有 旗標出版股份有限公司,19,好搭檔系統,固定與變動長度分割區的平衡 以2的指數為單位來分配記憶體 當記憶體中不存在適當大小的洞時更大尺寸的洞會被一分為二成為2個只有一半大小的洞 當行程結束時如果所釋放的記憶體與相鄰的另一個洞具有同樣長度時兩個搭檔

9、又會合而為一,著作權所有 旗標出版股份有限公司,20,圖4-5 好搭檔系統的使用範例,1M,原始的記憶體區塊,請求A, 180K,請求B, 60K,請求C, 250K,請求D, 120K,釋放A,釋放C,釋放B,釋放D,A,256K,512K,A,64K,128K,B,512K,A,B,64K,128K,256K,C,A,B,64K,D,256K,C,B,64K,D,256K,C,256K,B,64K,D,256K,512K,256K,128K,D,512K,1M,著作權所有 旗標出版股份有限公司,21,好搭檔系統的搜尋流程,利用遞迴呼叫可以簡單地完成搭檔系統的搜尋程式設計,find_hole

10、 (i) if (i H) /超過區塊上限 return fail; if (可用清單中找不到2i的洞） find_hole (i+1); /尋找更大一級的洞 將find_hole (i+1) 傳回的洞切成兩個搭檔單位; 將搭檔放入可用清單中; return 清單中第一個長度為2i的洞; ,著作權所有 旗標出版股份有限公司,22,課堂練習,假設系統擁有1M的實體記憶體，並且使用好搭檔系統來配置記憶體區域，請依照下列記憶體請求與釋放順序，說明記憶體區塊的配置情況： 請求A：500K 請求B：200K 請求C：50K 釋放A 請求D：100K 釋放C,著作權所有 旗標出版股份有限公司,23,解答,

11、1M,請求A, 500K,請求B, 200K,請求C, 50K,請求D, 100K,釋放A,釋放C,A,512K,A,A,128K,B,C,512K,64K,256K,B,128K,B,C,64K,512K,B,C,64K,D,512K,B,D,128K,著作權所有 旗標出版股份有限公司,24,4-2 分頁,把行程的邏輯位址空間切割成同樣大小的區塊，稱為頁面 實體位址空間也切割為相同大小的單位稱為頁框 行程的任何一個頁面只要找到某個未被使用的頁框就可以放到實體記憶體中 每個行程都配置有一個分頁表用來儲存每個頁面所在的頁框編號,著作權所有 旗標出版股份有限公司,25,圖4-6 邏輯與實體位址空間

12、的分頁範例,Page 0,Page 1,Page 2,Page 3,0,1,2,3,4,5,6,7,8,9,10,11,Page 0,Page 1,Page 2,Page 3,0,1,2,3,5,9,1,7,行程A的 邏輯位址空間,分頁表,實體記憶體,頁框編號,著作權所有 旗標出版股份有限公司,26,圖4-7 使用分頁來解決外部碎片問題,實體記憶體,行程A,Free,(a),(b),(c),行程 C 結束,釋放3個頁面）,行程 F 進入,A1,A2,行程B,行程C,行程D,行程E,B1,B2,B4,B3,B5,B6,C1,C2,C3,D1,D2,D3,E1,E2,E3,E4,實體記憶體,行程A

13、,Free,A1,A2,行程B,行程D,行程E,B1,B2,B4,B3,B5,B6,C1,C2,C3,D1,D2,D3,E1,E2,E3,E4,Free,實體記憶體,行程A,Free,A1,A2,行程B,行程D,行程E,B1,B2,B4,B3,B5,B6,C1,C2,C3,D1,D2,D3,E1,E2,E3,E4,行程F,要求5個頁面）,F1,F3,F2,F4,F5,行程F,著作權所有 旗標出版股份有限公司,27,圖4-8 分頁時的位址轉換,p,d,邏輯位址,f,d,實體位址,p,f,f,d,分頁表,實體記憶體,著作權所有 旗標出版股份有限公司,28,課堂練習,假設有一系統的邏輯位址長度為32

14、，頁面長度為4K，請問： 在邏輯位址中，頁面編號與位移量分別佔用幾個位元？ 頁面編號的值應該落在哪個範圍？,著作權所有 旗標出版股份有限公司,29,練習解答,頁面長度4K（=212），所以位移量需要12位元 邏輯位址長度為32，剩餘的位元數為20（32-12），所以頁面編號佔據20位元 頁面編號的範圍為0到220-1,著作權所有 旗標出版股份有限公司,30,分頁設計的碎片情況,使用分頁設計可以避免外部碎片的問題 當行程的長度不能被頁面長度整除時就會形成內部碎片 內部碎片的平均值為頁面長度的一半 頁面越小內部碎片所造成的浪費也就越小，但會造成儲存與管理分頁表上的負擔，以及降低磁碟輸入/輸出的效率

15、,著作權所有 旗標出版股份有限公司,31,實作討論-Linux的好搭檔系統,Linux在分頁機制下使用了好搭檔系統來管理外部碎片的問題 所有未被使用的頁框會被分成10種不同大小的頁框串列，分別包含1、2、4、8、16、32、64、128、256、與512個連續頁框，每個頁框的長度為4KB 根據行程對連續空間的要求，選擇位於適當佇列中的連續區塊 當行程釋放不需要的頁框時，Linux會嘗試將可搭檔區域結合，並放入更大一級的串列中,著作權所有 旗標出版股份有限公司,32,4-3 分段,按照行程內容的特性進行分割例如將程式分割為程式區段與資料區段 分段因為涉及對程式的解讀所以責任會落在程式設計師或編譯

16、程式的肩上 可能產生出不同長度的段落 作業系統必須為每個行程管理一份分段表 分段表中包含分段編號、位移量，與分段的長度,著作權所有 旗標出版股份有限公司,33,圖4-9 分段時的位址轉換,s,d,邏輯位址,p,d,實體位址,s,p,p,d,分段表,實體記憶體,定址錯誤 例外中斷,是,否,len,著作權所有 旗標出版股份有限公司,34,分段機制的管理,比較類似變動長度分割區的管理 因為各段具有不同的性質可以在分段表的每個項目中加入一組保護位元針對各分段特性提供分段保護的功能，例如唯讀或唯執行等 可以達到諸如程式碼（或函式庫）或是資料段的共享,著作權所有 旗標出版股份有限公司,35,圖4-10 分

17、段的共用,編輯程式,資料A,行程A分段表,0,1,行程A的邏輯記憶體位址,編輯程式,資料B,分段編號,0,1,行程B的邏輯記憶體位址,編輯程式,實體記憶體,資料B,資料A,位址,0,16K,24K,120K,132K,240K,256K,長度,基底,12K,120K,16K,240K,行程B分段表,0,1,長度,基底,12K,120K,8K,16K,分段編號,0,1,著作權所有 旗標出版股份有限公司,36,分頁式分段,分段的好處在於提高記憶體的使用彈性但是會增加記憶體管理的複雜度也會造成外部碎片的問題 解決方式：針對分段後的各段落再進行分頁，此時每一段都有各自的分頁表 不會有外部碎片但1個行程可能會有多個內部碎片,著作權所有 旗標出版股份有限公司,37,圖4-11 分頁式分段範例,s,d,邏輯位址,f,d,實體位址,s,pp,f,d,分段表,實體記憶體,p,p,f,第S段的分頁表,著作權所有 旗標出版股份有限公司,38,實作討論-Linux的分段類型,Linux採用分頁式分段的原因 比較容易在行程間提供分段共享的功能 比較能適應各處理器不同的分段支援能力 Linux的分段類型：kernel程式區段、kernel資料區段、使用者程式