---
# System prepended metadata

title: 'Ch9: Main Memory'
tags: [OS]

---

<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
    ![image](https://hackmd.io/_uploads/BklGv7d086.png)
    - Base register
    - Limit register
    - 這兩個暫存器定義 logical address space，分別記錄 process 起始記憶體位置 (base register) 跟 process 所占記憶體位置大小 (limit register)。

![image](https://hackmd.io/_uploads/Bk7hX_AI6.png)

### Address Binding 

![image](https://hackmd.io/_uploads/SJzH4_0Up.png)

- 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>
    - 可將虛擬位置轉換成實體位置的硬體裝置
    ![image](https://hackmd.io/_uploads/r1m8DdR86.png)
- Relocation register
    - Base register 在這被稱為 relocation register
    ![image](https://hackmd.io/_uploads/rJVuwdR8a.png)

### Dynamic Loading

- Dynamic Loading

### Dynamic Linking and Shared Libraries

- Dynamically linked libraries (DLLs)
    ![image](https://hackmd.io/_uploads/B1pPdOR8a.png)
- Static linking
- Dynamic linking

## Contiguous Memory Allocation

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

### Memory Protection

![image](https://hackmd.io/_uploads/HJEkt_AU6.png)

### 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。

![image](https://hackmd.io/_uploads/ryR_Ad0Lp.png)
![image](https://hackmd.io/_uploads/Bki7R_C8T.png)
![image](https://hackmd.io/_uploads/SkmSCdRIT.png)
![image](https://hackmd.io/_uploads/SkEvAdAL6.png)

### Hardware Support

![image](https://hackmd.io/_uploads/rJe9ktAUa.png)

- <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

![image](https://hackmd.io/_uploads/Sy9ESFA8a.png)

### Shared Pages

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

![image](https://hackmd.io/_uploads/S1o9rtC8a.png)

## Structure of the Page Table

### Hierarchical Paging

![image](https://hackmd.io/_uploads/BJSk8tA86.png)

![image](https://hackmd.io/_uploads/S16-LYC8T.png)

### Hashed Page Tables

![image](https://hackmd.io/_uploads/HJiYLK0Ua.png)

### Inverted Page Tables

![image](https://hackmd.io/_uploads/Syo28KCLT.png)

- <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

![image](https://hackmd.io/_uploads/rkFCvzQD6.png)

### Swapping with Paging

- Page out
- Page in

![image](https://hackmd.io/_uploads/BJWOuMmv6.png)


### Swapping on Mobile Systems

- Mobile systems typically do not support swapping in any form

