11 操作系统第三章 内存管理 内存的基本知识 内存管理 内存空间扩充 连续分配管理方式
文章目錄
- 1 內存概念
- 1.1 內存作用
- 1.2 邏輯地址VS物理地址
- 1.3 裝入的三種方式
- 1.3.1 絕對裝入
- 1.3.2 可重定位裝入
- 1.3.3 動態重定位裝入
- 1.4 鏈接的三種方式
- 1.4.1 靜態鏈接
- 1.4.2 裝入時動態鏈接
- 1.4.3 運行時動態鏈接
- 1.5 內存的基礎知識小結
- 2 內存管理
- 2.1 內存管理的任務
- 2.2 內存保護的兩種方法
- 2.3 內存管理小結
- 3 內存空間擴充
- 3.1 內存空間擴充之覆蓋技術
- 3.2 內存空間擴充之交換技術
- 3.3 覆蓋與交換技術小結
- 4 內存空間分配
- 4.1 單一連續分配
- 4.2 固定分區分配
- 4.3 動態分區分配
- 4.4 連續分配管理小結
- 4.5 動態分區分配算法
- 4.5.1 首次適應算法
- 4.5.2 最佳適應算法
- 4.5.3 最壞（大）適應算法
- 4.5.4 鄰近適應算法
- 4.5.5 動態分區分配算法小結
1 內存概念
1.1 內存作用
內存可存放數據。程序執行前需要先放到內存中才能被CPU處理一一緩和CPU與硬盤之間的速度矛盾
思考：在多道程序環境下，系統中會有多個程序并發執行，也就是說會有多個程序的數據需要同時放到內存中。那么，如何區分各個程序的數據是放在什么地方的呢？
方案：給內存的存儲單元編地址
內存地址相當于酒店旅館中的小房間，酒店管理者為了便于管理每個房間，采取給每個房間編號
內存中也有一個一個的“小房間”，每個小房間就是一 個“存儲單元”
如果計算機“按字節編址”， 則每個存儲單元大小為1字節，即1B，即8個二進制位
如果字長為16位的計算機 “按字編址”，則每個存儲單元大小為1個字；每個字的大小為16個二進制位
存儲單元大小由計算機按字編址還是按字節編址來確定
一臺手機/電腦有4GB內存，是指該內存中可以存放4X2 30個字節。
如果是按字節編址的 話，也就是有4X2 30=232個“小房間”
這么多“小房間”，需要232個地址才能一一標識，所以地址需要用32個二進制位來表示（0~232-1）
210=1K （千）
220=1M （兆，百萬）
230=1G （十億，千兆）
可以通過內存的大小，讓我們確定地址長度應該是多少（即要多少個二進制位才能表示相應數目的存儲單元）
1.2 邏輯地址VS物理地址
實際生活中的例子：
宿舍四個人一起出去旅行，四個人的學號尾號分別是0、1、2、3。
住酒店時酒店給你們安排了4個房號相連的房間。四個人按學號遞增次序入住房間。比如0、1、2、3號同學分別入住了5、6、7、8號房間。
四個人的編號0、1、2、3其實是一個“相對位置”，而各自入住的房間號是一個“絕對位置”。
只要知道0號同學住的是房號為N的房間，那么M號同學的房號一定是N+M。
指令中的地址也可以采用這種思想。編譯時產生的指令只關心“相對地址”，實際放入內存中時再想辦法根據起始位置得到“絕對地址”。
相對地址又稱邏輯地址，絕對地址又稱物理地址。
從寫程序到程序運行：
程序經過編譯、鏈接后生成的指令中指明的是邏輯地址（相對地址），即：相對于進程的起始地址而言的地址
如何將指令中的邏輯地址轉換為物理地址？
策略：三種裝入方式
1.3 裝入的三種方式
1.3.1 絕對裝入
絕對裝入：在編譯時，如果知道程序將放到內存中的哪個位置，編譯程序將產生絕對地址的目標代碼。 裝入程序按照裝入模塊中的地址，將程序和數據裝入內存。
編譯、鏈接后得到的裝入模塊的指令直接就使用了絕對地址。
絕對裝入只適用于單道程序環境。 程序中使用的絕對地址，可在編譯或匯編時給出，也可由程序 員直接賦予。通常情況下都是編譯或匯編時再轉換為絕對地址。
1.3.2 可重定位裝入
靜態重定位：又稱可重定位裝入。編譯、鏈接后的裝入模塊的地址都是從0開始的，指令中使用的地址、數據存放的地址都是相對于起始地址而言的邏輯地址。可根據內存的當前情況，將裝入模塊裝入到內存的適當位置。裝入時對地址進行“重定位”，將邏輯地址變換為物理地址（地址變換是在裝入時一次完成的）。
靜態重定位的特點是在一個作業裝入內存時，必須分配其要求的全部內存空間，如果沒有足夠的內存，就不能裝入該作業。 作業一旦進入內存后，在運行期間就不能再移動，也不能再申請內存空間。
1.3.3 動態重定位裝入
動態重定位：又稱動態運行時裝入。編譯、鏈接后的裝入模塊的地址都是從0開始的。裝入程序把裝 入模塊裝入內存后，并不會立即把邏輯地址轉換為物理地址，而是把地址轉換推遲到程序真正要執行 時才進行。因此裝入內存后所有的地址依然是邏輯地址。這種方式需要一個重定位寄存器的支持。
1.4 鏈接的三種方式
1.4.1 靜態鏈接
1.4.2 裝入時動態鏈接
1.4.3 運行時動態鏈接
1.5 內存的基礎知識小結
2 內存管理
2.1 內存管理的任務
操作系統作為系統資源的管理者，當然也需要對內存進行管理，要管些什么呢？
1.操作系統負責內存空間的分配與回收
游戲GTA的大小超過60GB，按理來說這個游戲程序運行之前需要把60GB數據全部放入內存。然而，實際我的電腦內存才12GB，但為什么這個游戲可以順利運行呢？
——虛擬技術（操作系統的虛擬性）
為了使編程更方便，程序員寫程序時應該只需要關注指令、數據的邏輯地址。而邏輯地址到物理地址的轉換（這個過程稱為地址重定位）應該由操作系統負責，這樣就保證了程序員寫程序時不需要關注物理內存的實際情況。
三種裝入方式實現邏輯地址與物理地址的轉換：
使得各個進程只能訪問自己的內存空間
2.2 內存保護的兩種方法
方法一：在CPU中設置一對上、下限寄存器，存放進程的上、下限地址。進程的指令要訪問某個地址時，CPU檢查是否越界。
方法二：采用重定位寄存器（又稱基址寄存器）和界地址寄存器（又稱限長寄存器）進行越界檢查。
重定位寄存器中存放的是進程的起始物理地址。界地址寄存器中存放的是進程的最大邏輯地址。
2.3 內存管理小結
3 內存空間擴充
3.1 內存空間擴充之覆蓋技術
引入覆蓋技術，用來解決“程序大小超過物理內存總和”的問題
覆蓋技術的思想：
將程序分為多個段（多個模塊）。 常用的段常駐內存，不常用的段在需要時調入內存。
內存中分為一個“固定區”和若干個“覆蓋區”。
需要常駐內存的段放在“固定區”中，調入后就不再調出（除非運行結束）
不常用的段放在“覆蓋區”，需要用到時調入內存， 用不到時調出內存
由圖可見，未使用覆蓋技術時，程序執行需要使用8K+8K+10K+12K+4K+10K=52K的內存空間
采用覆蓋技術后，需要8K+10K+12K=30K的內存空間
必須由程序員聲明覆蓋結構，操作系統完成自動覆蓋。
缺點：對用戶不透明，增加了用戶編程負擔。 覆蓋技術只用于早期的操作系統中，現在已成為歷史。
3.2 內存空間擴充之交換技術
交換（對換）技術的設計思想：內存空間緊張時，系統將內存中某些進程暫時換出外存，把外存中某些已具備運行條件的進程換入內存（進程在內存與磁盤間動態調度）
暫時換出外存等待的進程狀態為掛起狀態（掛起態，suspend）
掛起態又可以進一步細分為就緒掛起、阻塞掛起兩種狀態
.
中級調度（內存調度），就是要決定將哪個處于掛起狀態的進程重新調入內存。
交換技術面臨的問題：
（1）文件區主要用于存放文件，主要追求存儲空間的利用率，因此對文件區空間的管理采用離散分配方式；
（2）對換區空間只占磁盤空間的小部分，被換出的進程數據就存放在對換區。由于對換的速度直接影響到系統的整體速度，因此對換區空間的管理主要追求換入換出速度，因此通常對換區采用連續分配方式。
（3）總之，對換區的I/O速度比文件區的更快。
例如：在發現許多進程運行時經常發生缺頁，就說明內存緊張，此時可以換出一些進程； 如果缺頁率明顯下降，就可以暫停換出。
注意：雖然交換技術會將內存中某些進程暫時換出外存，但進程的PCB會常駐內存，不會被換出外存
3.3 覆蓋與交換技術小結
4 內存空間分配
內存空間分配可分為連續分配管理方式和非連續分配管理方式
連續分配：指為用戶進程分配的必須是一個連續的內存空間
4.1 單一連續分配
在單一連續分配方式中，內存被分為系統區和用戶區。
系統區通常位于內存的低地址部分，用于存放操作系統相關數據；用戶區用于存放用戶進程相關數據。
單一連續分配 內存中只能有一道用戶程序，用戶程序獨占整個用戶區空間。
優點：實現簡單；無外部碎片；可以采用覆蓋技術擴充 內存；不一定需要采取內存保護（eg：早期的PC操作系統MS-DOS）。
缺點：只能用于單用戶、單任務的操作系統中；有內部碎片；存儲器利用率極低。
4.2 固定分區分配
20世紀60年代出現了支持多道程序的系統，為了能在內存中裝入多道程序，且這些程序之間又不會相互干擾，于是將整個用戶空間劃分為若干個固定大小的分區，在 每個分區中只裝入一道作業，這樣就形成了最早的、最 簡單的一種可運行多道程序的內存管理方式。
固定分區分配可分為分區大小相等、分區.大小不等兩種類型
分區大小相等：缺乏靈活性，但是很適合用于用一臺計 算機控制多個相同對象的場合（比如：鋼鐵廠有n個相 同的煉鋼爐，就可把內存分為n個大小相等的區域存放 n個煉鋼爐控制程序）
分區大小不等：增加了靈活性，可以滿足不同大小的進 程需求。根據常在系統中運行的作業大小情況進行劃分 （比如：劃分多個小分區、適量中等分區、少量大分區）
操作系統需要建立一個數據結構——分區說明表，來實現各個分區的分配與回收。每個表項對應一個分區，通常按分區大小排列。每個表項包括對應分區的 大小、起始地址、狀態（是否已分配）。
| 1 | 2 | 8 | 未分配 |
| 2 | 2 | 10 | 未分配 |
| 3 | 4 | 12 | 已分配 |
| ······· | ······· | ······· | ······· |
當某用戶程序要裝入內存時，由操作系統內核程序根據用戶程序大小檢索該表， 從中找到一個能滿足大小的、未分配的分區，將之分配給該程序，然后修改狀 態為“已分配”。
優點：實現簡單，無外部碎片。
缺點：a.當用戶程序太大時，可能所有的分區都不能滿足需求，此時不得不采用覆蓋技術來解決，但這又會降低性能； b.會產生內部碎片，內存利用率低。
4.3 動態分區分配
動態分區分配又稱為可變分區分配。這種分配方式不會預先劃分內存分區，而是在進程裝入內存時， 根據進程的大小動態地建立分區，并使分區的大小正好適合進程的需要。因此系統分區的大小和數目是可變的。
動態分區分配核心問題：
1.系統要用什么樣的數據結構記錄內存的使用情況？
2.當很多個空閑分區都能滿足需求時，應該選擇哪個分區進行分配？
3.如何進行分區的分配與回收操作？
兩種常用的數據結構：空閑分區表和空閑分區鏈
每一時刻系統分配如下：
采用空閑分區表：
空閑分區表：每 個空閑分區對應 一個表項。表項 中包含分區號、 分區大小、分區 起始地址等信息
| 1 | 20 | 8 | 空閑 |
| 2 | 10 | 32 | 空閑 |
| 3 | 4 | 60 | 空閑 |
空閑分區鏈：
空閑分區鏈：每個分區的起始部分和末尾部分分別設置前向指 針和后向指針。起始部分處還可記錄分區大小等信息
現有進程5(4MB)調入內存，應該用最大的分區進行分配？還是用最小的分區進行分配？又或是用地址最低的部分進行分配？
把一個新作業裝入內存時，須按照一定的動態分區分配算法，從空閑分區表（或空閑分區鏈）中選出一個分區分配給該作業。
情況一：回收區的后面有一個相鄰的空閑分區
此時分區表是
| 1 | 10 | 32 | 空閑 |
| 2 | 4 | 60 | 空閑 |
假設此時進程4運行結束，將進程4占用的4M內存空間回收，而后面有一塊10M的相鄰空閑區
此時空閑分區表：
| 1 | 14 | 28 | 空閑 |
| 2 | 4 | 60 | 空閑 |
兩個相鄰的空閑分區合并為一個
情況二：回收區的前面有一個相鄰的空閑分區
此時空閑分區表：
| 1 | 20 | 8 | 空閑 |
| 2 | 10 | 32 | 空閑 |
假設此時進程3運行結束，將進程3占用的18M內存空間回收，而前面有一塊10M的相鄰空閑區
此時空閑分區表：
| 1 | 20 | 8 | 空閑 |
| 2 | 28 | 32 | 空閑 |
兩個相鄰的空閑分區合并為一個
情況三：回收區的前、后各有一個相鄰的空閑分區
此時空閑分區表：
| 1 | 20 | 8 | 空閑 |
| 2 | 10 | 32 | 空閑 |
| 3 | 4 | 60 | 空閑 |
假設此時進程4運行結束，將進程4占用的4M內存空間回收，而后面有一塊10M的相鄰空閑區，前面有一塊20M的內存空間
| 1 | 34 | 8 | 空閑 |
| 2 | 4 | 60 | 空閑 |
三個相鄰的空閑分區合并為一個
情況四：回收區的前、后都沒有相鄰的空閑分區
此時空閑分區表：
| 1 | 4 | 60 | 空閑 |
假設此時進程2運行結束，將進程2占用的14M內存空間回收，而后面有一塊4M的不相鄰空閑區
此時空閑分區表：
| 1 | 14 | 28 | 空閑 |
| 2 | 4 | 60 | 空閑 |
注：各表項的順序不一定按照地址遞增順序排列，具體的排列方式需要依據動態分區分配算法來確定。
動態分區分配又稱為可變分區分配。這種分配方式不會預先劃分內存分區，而是在進程裝入內存時， 根據進程的大小動態地建立分區，并使分區的大小正好適合進程的需要。因此系統分區的大小和數目是可變的。
動態分區分配沒有內部碎片，但是有外部碎片。
內部碎片，分配給某進程的內存區域中，如果有些部分沒有用上。 外部碎片，是指內存中的某些空閑分區由于太小而難以利用。
如果內存中空閑空間的總和本來可以滿足某進程的要求， 但由于進程需要的是一整塊連續的內存空間，因此這些 “碎片”不能滿足進程的需求。 可以通過緊湊（拼湊，Compaction）技術來解決外部碎片。
進程1如何分配內存空間？
緊湊法挪位
從而就可以將進程1調入內存
4.4 連續分配管理小結
4.5 動態分區分配算法
動態分區分配算法解決的問題：
在動態分區分配方式中， 當很多個空閑分區都能滿足需求時，應該選擇哪個分區進行分配？
4.5.1 首次適應算法
算法思想：每次都從低地址開始查找，找到第一個能滿足大小的空閑分區。
如何實現：空閑分區以地址遞增的次序排列。每次分配內存時順序查找空閑分區鏈（或空閑分區 表），找到大小能滿足要求的第一個空閑分區。
4.5.2 最佳適應算法
算法思想：由于動態分區分配是一種連續分配方式，為各進程分配的空間必須是連續的一整片區域。因此為了保證當“大進程”到來時能有連續的大片空間，可以盡可能多地留下大片的空閑區， 即，優先使用更小的空閑區。
如何實現：空閑分區按容量遞增次序鏈接。每次分配內存時順序查找空閑分區鏈（或空閑分區 表），找到大小能滿足要求的第一個空閑分區。
缺點：每次都選最小的分區進行分配，會留下越來越多的、很小的、難以利用的內存塊。因此這種方法會產生很多的外部碎片
4.5.3 最壞（大）適應算法
算法思想：為了解決最佳適應算法的問題——即留下太多難以利用的小碎片，可以在每次分配時優先使用最大的連續空閑區，這樣分配后剩余的空閑區就不會太小，更方便使用。
如何實現：空閑分區=按容量遞減次序鏈接。每次分配內存時順序查找空閑分區鏈（或空閑分區 表），找到大小能滿足要求的第一個空閑分區。
缺點：每次都選最大的分區進行分配，雖然可以讓分配后留下的 空閑區更大，更可用，但是這種方式會導致較大的連續空閑區被 迅速用完。如果之后有“大進程”到達，就沒有內存分區可用了。
4.5.4 鄰近適應算法
算法思想：首次適應算法每次都從鏈頭開始查找的。這可能會導致低地址部分出現很多小的空閑分區，而每次分配查找時，都要經過這些分區，因此也增加了查找的開銷。如果每次都從上次查找結束的位置開始檢索，就能解決上述問題。
如何實現：空閑分區以地址遞增的順序排列（可排成一個循環鏈表）。每次分配內存時從上次查找結束的位置開始查找空閑分區鏈（或空閑分區表），找到大小能滿足要求的第一個空閑分區。
首次適應算法每次都要從頭查找，每次都需要檢索低地址的小分區。 但是這種規則也決定了當低地址部分有更小的分區可以滿足需求時， 會更有可能用到低地址部分的小分區，也會更有可能把高地址部分的大分區保留下來（最佳適應算法的優點）
鄰近適應算法的規則可能會導致無論低地址、高地址部分的空閑分區都有相同的概率被使用，也就導致了高地址部分的大分區更可能被使用，劃分為小分區，最后導致無大分區可用（最大適應算法的缺點）
綜合來看，四種算法中，首次適應算法的效果反而更好
4.5.5 動態分區分配算法小結
總結
以上是生活随笔為你收集整理的11 操作系统第三章 内存管理 内存的基本知识 内存管理 内存空间扩充 连续分配管理方式的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 图的知识点总结-数据结构
- 下一篇： 树的知识点总结-数据结构