# Memory Management

###### tags: `IT鐵人`

雖然我們在前面的計算機結構也有講過Memory，不過那是偏向最底層硬體的實施方式，現在要介紹的是OS如何管理Memory的空間，那我們開始吧！

## 複習


如同當初提到的，我們要執行任何程式時，一定都要把他load到Memory中，不然放在Disk執行太慢了。至於Virtual Meomry則是在Memory不夠大時，暫時將部分Process轉移到Disk中，並且紀錄位置在Page Table中，以便於到時候要用的時候可以迅速找到。

## Binding

至於我們今天要提到的部分則是OS如何將程式Load進入Memory中，這個過程稱為binding，其中binding有三個時機點，分別如下：

|時間點|說明|
|-|-|
|Compiling Time|由Compiler負責Binding產生的code叫做Absolute Code，若要重新決定程式的執行起始位置，需要recompile the code|
|Load Time|由Linking Loader決定Compiler產生relocatable code，由Linking Loader負責Binding。若要改變起始位置，只需Reload the code，不須recompile|
|Execution Time|延遲到執行時期才動態決定起始位置。Process在Execution期間可任意更動其起始位址且仍可正確執行。必須有Hardware Support，Binding delay到Execution Time才做，稱為"Dynamic Binding"|

用圖片來說明就像是下面這樣。


## 白話說明Binding


白話來說，就像是學生照座號排隊去升旗，其中班級座號就像是Compiling Time的Binding，n號同學知道自己在班上的n號位置。

到了操場之後，因為每班須要站到自己的位置，所以這時候5號同學可能就不會在全校人員數下來的第5個位置，他會在自己班級排頭算下來的第5號位置。這就是Load Time的Binding。

至於Execution Time的Binding則是今天某個同學請假，可能是出去比賽或是被懲罰了，這時候叫到他的時候就要去找找他在哪裡，它的位置就會是當下的情況決定。


大guy是這個樣子啦，希望這樣子的解釋有比較簡單明瞭。

## Contiguous Memory Allocation Methods

前面提到了決定記憶體位置的時機，現在我們要來講講OS怎麼分配記憶體給Process，如果隨意分配的話，之後Memory的空閒空間就會變得支離破碎。

分配的方式有以下三中，其實從名字聽就知道worst會是最差的，其中hole的意思代表空閒、連續且沒被占據的Memory space

|方法|內容|
|-|-|
|First-Fit|從Available-list的第一個hole開始尋找，直到找到第一個space大於需求的空間，即分配該Process需求的空間給他。
|Best-Fit|檢視Available-list的所有hole，並且找出大於需求空間中最小的hole，分配需要的給該Process。
|Worst-Fit|同上，不過取最大的hole，也就是分配全場最大的hole給Process。

三個概念上都很簡單，我也不知道為甚麼要出現Worst-Fit，他花費的時間跟Best-Fit一樣，效果又比First差。

以前用malloc時教授都說沒有要用的要記得free掉，那時候我忘記的時候還很緊張問同學我的記憶體會不會被吃光，之後才知道exit時系統會將占用的memory釋放掉XDDD

## Example

底下來個Allocation的小例子吧，假設我們有一串的Available-list如下

|100KB|500KB|200KB|300KB|600KB|Nil(結尾的意思)|
|-|-|-|-|-|-|

這時候有幾個Memory需求如下212KB, 417KB, 112KB, 426KB，三種不同的Method會發生以下事情。

### First-Fit

|100KB|500KB|200KB|300KB|600KB|Nil|
|-|-|-|-|-|-|
|100KB|288KB|200KB|300KB|600KB|Nil|
|100KB|288KB|200KB|300KB|183KB|Nil|
|100KB|176KB|200KB|300KB|183KB|Nil|

而最後的426KB無法排進去。

### Best-Fit

|100KB|500KB|200KB|300KB|600KB|Nil|
|-|-|-|-|-|-|
|100KB|500KB|200KB|88KB|600KB|Nil|
|100KB|83KB|200KB|88KB|600KB|Nil|
|100KB|83KB|88KB|88KB|600KB|Nil|
|100KB|83KB|88KB|88KB|174KB|Nil|

所有需求成功處理。

### Worst-Fit

|100KB|500KB|200KB|300KB|600KB|Nil|
|-|-|-|-|-|-|
|100KB|500KB|200KB|300KB|388KB|Nil|
|100KB|83KB|200KB|300KB|388KB|Nil|
|100KB|83KB|200KB|300KB|276KB|Nil|

最後的426KB也無法排進去。

以效果來說，Best-Fit的效果最好，而First-Fit的速度最快，只有Worst-Fit兩者都比不上。

那麼這篇就到這邊了，剩下的篇幅理論上都不會太長，都是原本計算機組織講過的東西在OS上如何執行而已，88。

|上一篇|下一篇|
|--|--|
|[Process Synchronization](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/BJezizwVY)|[Virtual Memory](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/S1HbjAs4Y)