<style>
.red {
color: #e33d2f;
font-weight: bold;
}

.green {
color: #22933f;
font-weight: bold;
}

.blue {
color: #2e7ced;
font-weight: bold;
}
</style>

## Background

### Basic Hardware

- Instruction execution cycle
- Stall
- Cache
- Base register
- Limit register
- 這兩個暫存器定義 logical address space，分別記錄 process 起始記憶體位置 (base register) 跟 process 所占記憶體位置大小 (limit register)。


### Address Binding


- Bind
- The binding of instructions and data to memory addresses **can be done at any step**
- Compile time
- 由 compiler 決定
- 如果知道 compile 時 process 在 memory 的位置，可以產生 **absolute address**。
- 假設知道 process 會在 location *R*，則 compile 出來的 code 會從這個位置開始 extend up。
- Load time
- 由 linking loader 或 linker editor 決定
- 編譯時無法確認，則生成 **relocation address** (不一定由固定位置執行)
<!-- TODO -->
- Execution time
- 由 OS 動態決定
- 如果記憶體區段要執行時被移動，連結才會延到這時
<!-- TODO -->

### Logical Versus Physical Address Space

- Logical Address
- Logical Address Space
- CPU 所產生的位置，又叫做 virtual address
- Physical Address
- Physical Address Space
- 記憶體看到的位置 (經過 MMU 處理過)
- <font class='red'>MMU (Memory Management Unit)</font>
- 可將虛擬位置轉換成實體位置的硬體裝置
- Relocation register
- Base register 在這被稱為 relocation register

### Dynamic Loading

- Dynamic Loading

### Dynamic Linking and Shared Libraries

- Dynamically linked libraries (DLLs)
- Static linking
- Dynamic linking

## Contiguous Memory Allocation

- Two partitions of memory
- Operating system
- User processes
- Contiguous memory allocation

### Memory Protection


### Memory Allocation

- Variable-partition scheme
- Hole
- Solutions to dynamic storage-allocation problem
- First fit
- 第一個容納得下就直接使用
- Best fit
- 看完所有記憶體空間，選一個夠大，而且最接近自己大小的使用。最後可能會生成許多很小的記憶體空間。
- Worst fit
- 看完所有記憶體空間，選一個最大的使用。最後可能會生成很大的記憶體空間。

## Fragmentation

- External fragmentation
- 剩下小塊小塊的記憶體空間，無法使用
- Internal fragmentation
- 記憶體空間給過大使用時， process 用不到，外面需要使用的也用不到
- Compaction
- 解決 fragmentation 的方法，將 process 移來移去，讓其餘的記憶體空間能夠聚在一起，但是 process 必須是 dynamic 才可以這樣做

## Paging

- Paging 是為了解決 fragmentation (external fragementation 可以解決，但 internal fragmentation 還是會存在) 跟處理很多不同大小的 process。

### Basic Method

- Frames & pages
- **Frames**: 將實體記憶體 (physical memory) 切割成固定大小的 block
- **Pages**: 將邏輯記憶體 (logical memory) 分成大小相同的 block
- Frames 跟 pages 的大小相同，當 program 需要 n 個 pages 時， OS 會去 physical memory 找 n 個 free frames 來放，frame 並不需要連續
- Page number (`p`)
- Page offset (`d`)
- Page table
- OS 會設置 page table，轉換 logical address 變成 physical address。


### Hardware Support


- <font class='red'>Translation Look-aside Buffer</font> (類似 cache 的概念)
- Parallel search
- TLB miss
- TLB 找不到的話就回去找 page table
- **有找到**：1 次 memory access；**找不到**：2 次 memory access (page table 算 memory)
- Hit ratio
- Effective memory access time

### Protection

- Valid-invalid bit


### Shared Pages

- Reentrant code
- 每次看都一樣（不能改內容）


## Structure of the Page Table

### Hierarchical Paging



### Hashed Page Tables


### Inverted Page Tables


- <process-id, page-number, offset>

## Swapping

- Backing store (disk)
- 在程式執行時，process 有時會需要暫時離開記憶體，之後會再搬回來執行，這就叫做 swapping，搬上搬下的動作我們稱為 **roll out** 跟 **roll in**。而在這裡的硬碟 (disk) 我們會將它稱作 backing store，兩者是互通的。

### Standard Swapping

- Standard swapping involves moving processes between main memory and a backing store


### Swapping with Paging

- Page out
- Page in


### Swapping on Mobile Systems

- Mobile systems typically do not support swapping in any form