# Memory
###### tags: `EOS`
Lec16 嵌入式作業系統

## Dynamic Memory Allocation
=heap memory
開機後硬體初始化，映像檔會先 load 到記憶體，剩下一塊空間會給 malloc 用



控制區塊control block透過max-heap tree管理

## Memory Fragmentation
---
簡單舉例

### 內部破碎

- Heap 256B
- block size 32B
`malloc(100B)` -> returnd `(32B/unit * 4units)`
有 28B 用不到，造成 block 內部破碎

### 外部破碎
用完之後釋放的空間不連續 B、D 共 2 block，要空間其實 100B 理論夠，但是block間不連續

---
示意圖


### Memory Compaction 處理外部破碎

- compact: 對**實際**記憶體磁碟清理，把不連續的剩餘空間搬移成連續的，很花時間
- compact 會導致其他人沒辦法存取這個位置，嵌入式實際上等到可用空間連續才合併

#### Memory alignment
- 假設一個 32bit 系統，也就是 data bus 排線32條
- 處理器一抓是 4 個 byte
- 一般依序從 0123、4567 抓
- 萬一程式沒有寫得很好，要抓 2345，而且又剛好是低成本的處理器，一次只能抓 4 byte 就會遇到問題。

## Memory Management

- Allocation array ->free() 重新整合連續的
- Max heap ->alloc() 快速拿到空的 block

不連續的會成為 heap 的 node，當 free 完兩個 node 變成連續的會合併成會一個 node，然後 heap 重新排列。

### Allocation array (allocation map)

表示 block 可否使用


- If offset = 0x10000, unit size = 0x20 (32), address for index 9
- 0x10000 + 0x20*9 = 0x10120

用掉的 block index 最高放0，最低放(負數)用掉的數量


free 後會加回來：檢查上下的值，正數代表可以合併
1. 3 和釋放的 4 合併變 7
2. 3 和釋放的 4、2 合併變 9

### Max heap


- 從 max heap 最大的 root 給大小，不管要求多大的空間
- 假設 20 用剩 5，5 放在 root 會重新排列 (reheap)，5、18 交換，5、11 交換

### 網路卡封包的 Memory Management

memory pool

需求大小不同，有一個控制結構控制要用哪個大小。
- 假設把 1000byte，放 128 完全放不下，系統就會崩潰
- 假設封包有兩片 700B、2B，但第一個進來就塞滿了，系統也會崩潰。

### 配置空間的成本

- block size 32B
- 配置 128B 的總成本
- struct a{ int[3] };
- malloc(sizeof(a)* n) 配置 n 個 a 大小的空間

**要有空間給對應的 map index、allocation array、heap tree**

| bitmap | allocation array | heap tree 節點數 n | 配置空間
| -------- | -------- | -------- | -------- |
| 4bit | 12B (int 4B* 3 個) | 12B* n | 32B* 4 |


### Blocking vs. Non-Blocking

memory management

左下角是 memery control block(allcation array & heap)，要有一個 mutex 管理