[toc]
# Memory
### Binding

決定程式起始位置，即程式要在記憶體的哪個地方開始執行。Binding 有 3 個時期，compile time, load time 和 execution time。
#### 1. Compile time

由 compiler 決定，將來程式執行的起始位址不得變更。

缺點：若所決定的位址內有其它的程式在執行，或之後要變更程式執行的起始位址，則須 recompile。

#### 2. Load time

由 linking loader (or linkage editor) 決定，程式不一定都由固定位址開始執行，支援重定位。

在 load time binding 有以下缺點：

execution time 沒有被呼叫到的模組仍需事先 linking, Allocation, Loading，浪費時間也浪費記憶體。 (e.g. if-else 的程序、OS 錯誤處理程序。)
程式執行期間仍不可以改變起始位址。

[補充] loader：解決 external symbol reference 之問題，例如：呼叫 module、呼叫 library 函式、其他 module 定義之變數。

#### 3. Execution time

由 OS 動態決定，又稱 **dynamic binding**，在程式執行期間才決定程式執行的起始位址。需要的額外硬體支援 (Memory-Management Unit, MMU)。

###### Base Register : 記錄目前程式的起始位址。
###### Address : local address 須與 base register 相加才會得出 physical address。
###### 考題思考:

###### 優缺點：

- 優點：彈性高
- 缺點： 程式執行較慢，Performance差。
### dynamic loading & static linking & dynamic linking
1. Static link

Compile 時 library 就加入程式碼。

2. Dynamic linking (Share library)

在程式執行期間，當某個模組被真正呼叫到時才將其載入到 main memory 中。
節省 main memory 空間。(即是 dynamic 方法的目的)
節省編譯、組譯、連結所花費的時間。(動態連結函式庫可以單獨重新編譯)
- 常用於 library 導入。
需要 OS 支持，不同 OS 有不同的稱呼。
Windows .dll (Dynamic Linking Libraries)
Linux .so (Shared Object)。

3. Dynamic loading

讓 programmer 在程式執行的過程中，動態決定要載入的 libraries。

###### 優點：

節省 main memory 空間。
讓 programmer 可以呼叫 loader，比 dynamic linking 更具有彈性，靈活度也更高。

###### 缺點：

programmer 的負擔，要 programmer 自己規劃而不是 OS 負責。
拖長執行時間
dynamic loading 是古老的方法，e.g. MS-DOS Overlay files
### Swapping

- A process can be swapped temporarily out of memory to a backing store (such as disk), and then brought back into memory for continued execution (using priority-based scheduling algorithms).

- Swapping is a mid-term scheduler.
- Major part of swap time is transfer time.

[感覺] 儲存階層化

從 main memory 到 cache（用位址 mod 去 mapping)
從 disk 到 memory

[例題] swapping transfer time 計算

Consider that the disk transfer rate is 40MB/s, and the average disk seek overhead is 8 ms. To swap out a 10-MB process and then to swap in a 10-MB process require

10,000KB/40,000KB = 250ms (250ms+8)*2=0.516s (mid-term scheduler)
The time quantum of a typical time-sharing system is 10ms; (short-term scheduler)

much smaller than this number.
### Allocation
Contiguous Memory Allocation

OS 依據各個 Process 的大小找到一塊夠大的連續可用的記憶體，配置給該 process 使用；OS 會利用 Link List 管理 Free Blocks，稱為 Available list。

Single-partition allocation :

Relocation-register scheme used to protect user processes from each other, and from changing OS code and data.
Relocation register contains value of smallest physical address; limit register contains range of logical addresses. Each logical address must be less than the limit register.

找尋連續可用空間的方法：

- First-Fit：從 AV list head 找，第一個 free block size >= n 就配置。
- Next-Fit：從上次配置後的下一個 Block 開始搜尋，改善 First-Fit 易在 AV-list 前端附近產生許多非常小的可用空間的問題。
- Best-Fit：找所有 free block，比 n 大且最接近 n。
長期而言會剩下很大的洞跟很小的洞。
- Worst-Fit：找所有 free block，比 n 大且（size – n）值最大者。
長期結果每個洞大小差不多。
- Buddy System：16,8,4,2,1的二元樹，每一層有 list 可以搜尋有無空間。


### fragration (裂解)
均有外部碎裂(External Fragmentation)問題
#### Internal fragmentation

- 作業系統配置給 process 的 memory 空間大於 process 真正所需的空間，這些多出來的空間該 process 用不到，而且也沒辦法供其他 process 使用，形成浪費
***但是當這個 memory size 為 120 但是最小size為200 所以會發生80 的inner fragration***
###### 解決方法:
- Reducing the page size can alleviate Internal Fragmentation.
- Enlarging the page size helps to reduce the size of the page table.
#### external fragmentation
系統中，所有可用空間總和大於某個 process 所需要，但因為這些空間不連續所以無法配給該 process 使用，造成 memory 空間閒置。

###### 解決方法:
- Compaction：類似磁碟重組的概念，移動執行中的 - process，使不連續的 free blocks 得以聚集成一塊夠大的連續可用空間
很難在短時間內決定一個最佳的壓縮策略。
process 必須是 dynamic binding 才可以支援。
- Page memory management
下方會做說明

### pagging

OS 會將 disk 中的資料分割成固定大小的區塊，稱為頁（pages）。當不需要時，將分頁由 memory 移到 disk ；當需要時再將資料取回載入 memory 中。分頁是磁碟和記憶體間傳輸資料塊的最小單位。

- 實體記憶體 (Physical Memory)：視為一組頁框(Frame)之集合。各頁框的大小均相等。
- 邏輯記憶體 (Logical Memory)：即User Program。視為一組頁面(Page)的集合。頁面大小等同於頁框之大小。

一個 process 有一個 page table，page table 儲存在記憶體中，執行時用 page table 的資訊來把 logical address 轉成 physical address。

###### 優點：

- 解決 external fragmentation問題
可以支援記憶體的共享(Sharing)：不同 page 對應相同的 frame。
- 可以支援記憶體的保護(Protection)：在分頁表上多加一個 protection bit 欄位
1. R : 表示Read only
2. RW : 表示Read/Write皆可
- 支援 Dynamic Loading 及 Virtual Memory 的製作

###### 缺點：

- 會有 internal fragmentation 問題 (page size 愈大愈嚴重)
- memory 有效存取時間較長 (logical address 轉 physical address)
需要額外的硬體支援
1. page table implementation (每個 Process 皆有 1 個 page table)
2. logic address -> physical address (用到搜尋器、加法器)
###### [例題] logical address 轉 physical address 計算

    how many bit are ...

    page number (p) : 2 bit (logical 有 4 大格)
    frame number (f) : 3 bit (physical 有 8 大格)
    displacement (d) : 2 bit (1 大格有 4 小格)
    logical address : [p, d] = [2, 2]
    physical address : [f, d] = [3, 2]
    page table entry : [p, f] = [2, 3]

### page table

###### 優點：
解決External Fragmentation問題
可以支援記憶體的共享(Sharing)及保護(Protection)
支援Dynamic Loading及Virtual Memory的製作