---
title: 'CPU、記憶體、快取'
disqus: kyleAlien
---

CPU、記憶體、快取分頁快取
===

## OverView of Content

[TOC]

## 儲存裝置 - 概述

記憶體也有分階層，其關係到記憶體的速度、大小、價位... 等等，請參考下圖

> 

### 快取記憶體 - SRAM

* CPU 處理資料的流程
1. 將資料從記憶體讀取到 暫存器
2. CPU 運算暫存器上的資料
3. 將運算資料存回記憶體

> 總線：可以參考 [**C & 內存 & 操作系統**](https://hackmd.io/45lybpWGQxe4kmEdho8C2w?view#C-amp-%E5%85%A7%E5%AD%98-amp-%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%B5%B1)
>
> 

而處理資料的瓶頸之一就是從 `讀取記憶體資料到暫存器` & `暫存器存回記憶體`，因為記憶體的速度比暫存器慢很多
> 記憶體可能花 1ms
> 暫存器只需 0.1ms (該數值不重要，重要的是相差速度)

* 為了處理上述的資料傳輸速度差異，於是在 暫存器 跟 記憶體 之間出現了快取記憶體 SRAM，快取記憶體
1. 速度：記憶體 < 快取記憶體 < 暫存器

2. 大小：記憶體 > 快取記憶體 > 暫存器

:::info
* 快取記憶體在哪？

一般內建於 CPU，但也有裝置是把快取記憶體至於 CPU 之外
:::
> 

### 快取記憶體 - Dirty Data
* 知道為何需要快速記憶體後，我們來看看它是如何使用，如何加速資料的存取
1. 快取記憶體讀取資料到 `R0` 暫存器
> 

2. 再次讀取相同位址資料到 `R1` 暫存器 (**不會從記憶體，++直接透過快取記憶體++**，這樣加快了速度)
> 

3. CPU 修改 `R0` 暫存器資料為 `0xAA`
> 

4. 將暫存器 `R0` 資料寫回快取記憶體，**並在快取記憶體上 ==標記 Dirty Data==**
> 

5. 在特定時間用 **背景處理** 的方式寫回至記憶體，並清除 Dirty Data 標記
> 

:::success
* 何時寫回 ? 背景處理 ?

這個方法被稱為 **分批寫回 (Write back)**，在快取記憶體變髒的瞬間，記憶還有名為寫入一次寫回的方式 (Write Throght)
:::

### 清理快取記憶體 - 震盪現象

* 當快取記憶體空間都有資料，但又要存取一筆新的資料到快取記憶體時，就會 **捨棄** 其中一筆的資料，這會有兩種情況

1. 清除正常資料：清除資料，寫入目標資料到記憶體

2. 清除的資料是 **Dirty Data**：先將資料寫回記憶體，在讀取目標資料到快取記憶體
> 

:::danger
* 震盪現象

若快取記憶體有過多 Dirty Data，則會造成快取記憶體不斷的在寫回、讀取，這會造成使用者卡頓現象
:::

### 裝置快取記憶體

* 一般來說階層式快取記憶體取名會以 L 開頭 (Level)，**L<數字> 數字越小，速度越快**
> eg. L1 比 L2 快，L1 比 L2 小

* `x86_64` 架構的 cpu 是採用 階層式結構，不過 CPU 共用、延遲、大小都不會相同，可透過以下指令查看相關訊息

    ## 路徑： /sys/devices/system/cpu/cpu<編號>/cache/index<快取記憶體>

    # 查看 cpu0 的，L1 快取
    cat /sys/devices/system/cpu/cpu0/cache/index0

    ls -l

> 

| 檔案名稱 | 說明 |
| -------- | -------- |
| type | 快取種類，**Data 代表資料，Code 代表程式碼，Unified 以上兩者皆會快取** |
| shared_cpu_list | 共用該快取的邏輯 cpu 列表 |
| size | 大小 |
| coherency_line_size | 快取列大小 |

* 目前裝置 L1 快取 (index0)
> 

* 目前裝置 L4 快取 (index3)
> 

### 快取記憶體 - 測試

* 測試目的：不同存取大小跟快取記憶體之間的關係，如果存取大小跟快取相同（或是倍數），是否會提高存取速度

    #include <stdio.h>
    #include <stdlib.h>
    #include <unistd.h>
    #include <sys/mman.h>
    #include <time.h>
    #include <err.h>

    // 快取列大小，對應 coherency_line_size
    #define CACHE_LINE_SIZE		64       

    // 測試迴圈 (固定)
    #define NLOOP			(4 * 1024UL * 1024)
    
    // 計算時間
    #define NSECS_PER_SEC		1000000000UL

    #define TP struct timespec

    static inline long diff_nsec(TP before, TP after) {
        return (
            (after.tv_sec * NSECS_PER_SEC + after.tv_nsec) -
            (before.tv_sec * NSECS_PER_SEC + before.tv_nsec)		
        );
    }

    int main(int argc, char *argv[]) {

        char *progname = argv[0];

        if(argc != 2) {
            fprintf(stderr, "usage: %s <size[KB]>\n", progname);
            exit(EXIT_FAILURE);
        }

        // Use cpu's register 
        register int size;
        size = atoi(argv[1]) * 1024;	
        if(!size) {
            fprintf(stderr, "size should be >= 1: %d\n", size);
            exit(EXIT_FAILURE);
        }

        char *buffer;
        buffer = mmap (
                NULL, 
                size,
                PROT_READ | PROT_WRITE,
                MAP_PRIVATE | MAP_ANONYMOUS,
                -1,
                0
            );
        if(buffer == (void *) -1) {
            err(EXIT_FAILURE, "mmap() failed.");
        }

        TP before, after;

        clock_gettime(CLOCK_MONOTONIC, &before);

        int times = NLOOP / (size / CACHE_LINE_SIZE);
        printf("Target test: %d, times: %d\n", size, times);
        for(int i = 0; i < times; i++) {
            for(long j = 0; j < size; j += CACHE_LINE_SIZE) {
                buffer[j] = 0;
            }
        }

        clock_gettime(CLOCK_MONOTONIC, &after);

        printf("%f\n", (double) diff_nsec(before, after) / NLOOP);

        if(munmap(buffer, size) == -1) {
            err(EXIT_FAILURE, "munmap() failed.");
        }

        exit(EXIT_SUCCESS);

    }

* 編譯 & 運行程式：目前裝置 [**樹梅派 pi 400**](https://www.raspberrypi.com/documentation/computers/processors.html#bcm2711)，**快取層級 L1: `32KB`、L2: `1M` (共用)**
1. 由於這次需要觀測的數值較小，所以編譯時多添加 `-O3` 最佳化

        # -O3 is optimize level
        cc -O3 -o cache cache.c 

        # Test case size
        a=(4 8 16 32 64 128 256 512 1024 2048 4096 8192 16382 32768)

        # foreach array of a
        for i in ${a[@]}; do ./cache $i; done

可以看到在寫入 4KB ~ 1024KB 使用的時間相當迅速 (1024KB 似乎就有點慢了 ? )，當一次寫入大於 1024KB 時間會大幅上升
> 

:::info
從這邊可以看出如果一次寫入大於 樹梅派 pi 400 的 L2 快取記憶體 (1M)，寫入速度就會降低，這也是震盪現象產生的問題
:::

## 快取記憶體特性

### 參照局部性
* 前面的實驗我們知道，快取記憶體可以加速運算的存取速度，因為大多數程式都具有 **==參照的局部性==**，這個局部性有兩個種類
1. **時間局部性**：於某個時間點被存取，不久後再次被存取的機率很高
> eg. for 迴圈、處理中的程式區域

        int size = 20;

        for(int i = 0; i < size; i++) {
            println("Num: " + i);
        }

2. **空間局部性**：當某個時間點存取到某些資料時，會對其附近記憶體位址進行的存取可能性比較高
> eg. Array 存取 `data[0]`，那其他的 `data[0] ~ [4]` 都算是空間局部性的範圍

        int[] data = {
            0, 123, 445, 667, 1235
        };

* 行程在考慮切割成短期間時，會傾向於對比本身所取得的記憶體量還要小很多的 **範圍存取**
因此這個 **存取範圍 的大小只要落在快取記憶體大小即可**
> 這樣才能發揮快取的最大作用

## CPU - TLB 區域

* TLB 的全名是 Translation Lookaside Buffer，它是 CPU 內的一個區塊，又名為 **==後備緩衝區==，該區塊有跟快取記憶體相同的速度**

### TLB 區域
* TLB 區塊的主要功能是將虛擬記憶體位址，轉換到實體記憶體位址。一般來說必須經過以下步驟
1. 透過分頁表項目上的參照 (Virtual : Real 對應的表)，來將虛擬記憶體轉換為實體記憶體

2. 對實體記憶體進行存取
> 

## Appendix & FAQ

:::info
:::

###### tags: `Linux 系統核心`