# 小蝦米與大鯨魚

## 研讀 linux 核心模組
> 林本然

### 安裝 [ksort](https://github.com/sysprog21/ksort) 的前置處理

**記得先將 UEFI Secure Boot 關閉**：UEFI Secure Boot 會確保只有經過簽章的模組才能被掛載到核心。為了方便掛載，我們先關閉。

先查看 Linux 核心版本，並且安裝相對應 `linux-headers` 套件（與 `uname -r` 同個版本），並確認安裝成功（根據自己的版本改命令）。

$ uname -r
$ sudo apt install linux-headers-`uname -r`
$ dpkg -L linux-headers-6.11.0-19-generic | grep "/lib/modules"

接下來要準備取得 `ksort` 原始碼，首先檢查一下使用者身份，目前的使用者和 root 應該是不同的。後續也會用 `sudo` 而避免直接用 root 輸入。

$ whoami
linmarc
$ sudo whoami
[sudo] password for linmarc: 
root

安裝其他用得到的工具：

$ sudo apt install util-linux strace gnuplot-nox

取得原始程式碼然後編譯，預期會看到 2 次綠色的 `Passed [-]` 字樣

$ git clone https://github.com/sysprog21/ksort
$ cd ksort
$ make check

我執行完看起來是正常的，但並沒有出現 2 次綠色的 `Passed [-]` 字樣。

$ make check
(...)
sudo insmod sort.ko
sudo insmod xoro.ko
make[1]: Leaving directory '/home/linmarc/linux2025/ksort'
sudo ./user
Sorting succeeded!
sudo ./test_xoro
n_bytes=0 n_bytes_read=0 value=0000000000000000
n_bytes=1 n_bytes_read=1 value=000000000000005f
n_bytes=2 n_bytes_read=2 value=000000000000ed8e
n_bytes=3 n_bytes_read=3 value=0000000000747c6a
n_bytes=4 n_bytes_read=4 value=00000000c61be1dd
n_bytes=5 n_bytes_read=5 value=000000f069befa4a
n_bytes=6 n_bytes_read=6 value=0000ebab275f98f0
n_bytes=7 n_bytes_read=7 value=0042569408ac9f4b
n_bytes=8 n_bytes_read=8 value=16b355d705d7d6d7
n_bytes=9 n_bytes_read=8 value=0b7f14b4fc108855
make rmmod
make[1]: Entering directory '/home/linmarc/linux2025/ksort'
make[1]: Leaving directory '/home/linmarc/linux2025/ksort'

掛載模組 `sort.ko` 並觀察加載模組後得到的裝置檔案 `/dev/sort` ，根據 lkmpg 的 5.6 章，裝置檔案是用來與硬體溝通的，放在 `/dev` 開頭的　device file 當中。使用以下命令並觀察 `/dev/sort` 的輸出：

$ sudo insmod sort.ko
$ ls -l /dev/sort
crw------- 1 root root 510, 0 Mar 25 11:40 /dev/sort

數字間用逗號隔開，其中第一個數字 `510` 代表主設備號，第二個數字 `0` 代表次設備號。一個主設備號只會對應到一個 driver ，而且只要設備間的主設備號相同，代表他們由同一個 driver 控制。而同個 driver 控制的硬體裝置間則用次設備號去區分，代表是不同的設備。

此外裝置可分為 character device 和 block device，差別在於 block devices 有 buffer 可以排序 requests，但是 input 和 output 都只能以 block 為單位。而 character device 沒有 buffer，他可以接受不定長度的 bytes 作為輸入和輸出。觀察上面輸出的第一個字母，若為 `b` 則為 block device，若為 `c` 則為 character device 。由此可知 `/dev/sort` 是 character device。

在 [sort_mod.c](https://github.com/sysprog21/ksort/blob/master/sort_mod.c) 裡面則是由 `sort_init` 裡面的這行程式碼負責註冊新的主設備到 kernel。根據 lkmpg 6.3 章提到：
> Adding a driver to your system means registering it with the kernel. This is synonymous with assigning it a major number during the module's initialization.

而底下這個函式的定義也在同一章節被說明，此函式是分配 dynamic major number ，確保我們能從一段 major number 的範圍內，獲得一個未被使用的主設備號。

#define DEVICE_NAME "sort"
...
static int __init sort_init(void)
{
    ...
    if (alloc_chrdev_region(&dev, 0, 1, DEVICE_NAME) < 0)
        return -1;
    ...
}

int alloc_chrdev_region(dev_t *dev, unsigned int baseminor, unsigned int count, const char *name);

- `dev`：`dev_t` 型別的變數，為 `u32` 型別，即 32-bit 無號數，定義在 `linux/include/linux/types.h` 當中，一次包含了主設備號和次設備號。
- `baseminor`：一個 driver 裡面的次設備號從 `baseminor` 開始。
- `count`：要分配的裝置數量，次設備號是 `baseminor` ~ `baseminor + count - 1`
- `name`：裝置名稱，以此例就是 `sort` 。

用以下指令可以查看模組版本，這和 `sort_mod.c` 透過 `MODULE_VERSION` 所指定的版本號碼相同，預期是 `0.1` 。

$ cat /sys/module/sort/version

:::info
TODO：搞懂 MODULE_VERISON
:::

而用以下兩個命令可知道 `sort.ko` 目前的 reference counting = 0，根據 lkmpg 6.4 章，reference counter 代表現在有多少 processes 在使用這個模組，如果這個值不為 0 ，則在後續 `rmmod` 卸載模組時會失敗。

### user-level 程式與 ksort 模組互動

`ksort` 設計為一個 character device，可理解是個能夠循序存取檔案，透過定義相關的函式，可利用存取檔案的系統呼叫以存取 (即 `open`, `read`, `write`, `mmap` 等等)。因此，使用者層級的程式可透過 read 系統呼叫來得到輸出，過程中變數 `fd` 就是 `ksort` 模組的 file descriptor，讓我們可以獲得 `inbuf` 中被 `ksort` 模組排序好的資料。

int fd = open(KSORT_DEV, O_RDWR);
...
size_t n_elements = 1000;
size_t size = n_elements * sizeof(int);
int *inbuf = malloc(size);
...
ssize_t r_sz = read(fd, inbuf, size);

`sort_mod.c` 的 `sort_read` 實作 user-space 用 read 呼叫取得排序結果，從 user-space 將資料複製到 kernel-space ，再複製回 user-space。其中每個函式的作用如下：

- `copy_from_user`：user-space $\to$ kernel-space，此例為 `buf` to `sort_buffer`
- `copy_to_user`：kernel-space $\to$ user-space，此例為 `sort_buffer` to `buf`
- `sort_main`：真正實作排序演算法的函式。

static ssize_t sort_read(struct file *file,
                         char *buf,
                         size_t size,
                         loff_t *offset)
{
    void *sort_buffer = kmalloc(size, GFP_KERNEL);
    len = copy_from_user(sort_buffer, buf, size);
    ...
    sort_main(sort_buffer, size / es, es, num_compare);
    len = copy_to_user(buf, sort_buffer, size);
    ...
}

### Linux VFS 介面

透過 Linux Virtual File System 介面，本核心模組可排序使用者層級指定的資料，並讓 `client.c` 程式得以存取。

VFS 提供一統各式檔案系統的共用介面，方便使用者操作不同的裝置或檔案時，可用一致的方式存取。Linux 的裝置驅動程式大致分為:

- Character Device Driver：以 bytes 為單位的輸入輸出，比如檔案的 `open`, `close`, `read`, `write` 等 system call
- Block Device Driver：以 blocks 為單位的輸入輸出
- Network Device Driver：控制網路硬體與作業系統的溝通，負責收發 data packet，而非使用 read/write

利用 [你所不知道的 C 語言：物件導向程式設計篇](https://hackmd.io/@sysprog/c-oop#%E6%A1%88%E4%BE%8B%E5%88%86%E6%9E%90-%E9%80%9A%E8%A8%8A%E7%B3%BB%E7%B5%B1%E7%9A%84%E5%8F%AF%E6%93%B4%E5%85%85%E7%95%8C%E9%9D%A2) 的方法定義 VFS 相關操作的函式界面 `struct file_operations`，並宣告結構變數 `fops` 藉此來讓使用者在 user-space 進行 read 呼叫時，對應到的是 `ksort` 已經實作好的 `sort_read`。

struct file_operations {
    struct module *owner;
    loff_t (*llseek) (struct file *, loff_t, int);
    ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
    ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
    ...
    int (*open) (struct inode *, struct file *);
    ...
    int (*release) (struct inode *, struct file *);
    int (*fsync) (struct file *, loff_t, loff_t, int datasync);
    int (*fasync) (int, struct file *, int);
    int (*lock) (struct file *, int, struct file_lock *);
    ...
} __randomize_layout;

static const struct file_operations fops = {
    .read = sort_read,
    .write = sort_write,
    .open = sort_open,
    .release = sort_release,
    .owner = THIS_MODULE,
};

### 核心模式的時間測量

跟計時有關的功能主要用在二種情境：

- timer: 安排「在某個時間點做某件事情」。可想像成火車班次表，這個重要的地方是：若某班火車誤點，會連鎖地影響後面所有班次。因此需要較精準的計時機制。
- timeout: 用來作為逾時的通知，提醒「有東西遲到」。最簡單的例子是 qtest 裡面的 SIGALRM 的使用。這對於時間的精準度要求不高。

    static void q_init()
    {
        fail_count = 0;
        INIT_LIST_HEAD(&chain.head);
        signal(SIGSEGV, sigsegv_handler);    // segfault
        signal(SIGALRM, sigalrm_handler);    // timeout
    }

其中一種計時方式是用作業系統從開機以來的計時器中斷發生的次數作為計時的依據，這個計時機制叫作 jiffies，很早就存在於 Linux 核心。較舊的 Linux 核心提供一個建議在 jiffies 上的計時機制，叫作 timer wheel，但 timer wheel 這個機制受限於計時器中斷觸發和實質能處理的的頻率，而這個頻率有其極限。

:::info
TODO：讀 [Linux 核心設計: 中斷處理和現代架構考量](https://hackmd.io/@sysprog/linux-interrupt)
:::

`hrtimer` 則是從 Linux 2.6.16 開始有的新的計時機制，裡面使用 `ktime_t` 這個新的資料結構來進行計時。跟大多數 Linux 中的資料結構使用機制類似，都要使用專門的函數來對這個資料型態進行操作，在 x86-64 中這是個 64 位元整數。相關的使用方式如下：

- `DEFINE_KTIME(name)`：很像 `LIST_HEAD` 之於 `struct list_head`，宣告一個 `ktime_t` 並初始化成 0。
- `ktime_add(ktime_t kt1, ktime_t kt2)`：相加
- `ktime_sub(ktime_t kt1, ktime_t kt2)`：相減
- `timespec_to_ktime(struct timespec tspec)`：把 `timespec` (秒+奈秒) 換成 `ktime_t`
- `timeval_to_ktime(struct timeval tval)`：把 `timeval` (秒+微秒) 換成 `ktime_t`
- `ktime_to_timespec(ktime_t kt)`：反向轉換
- `ktime_to_timeval(ktime_t kt)`：反向轉換
- `ktime_to_clock_t(ktime_t kt)`：`ktime_t` 換成 `clock_t`
- `ktime_to_ns(ktime_t kt)`：換成以奈秒為單位的 `u64` 整數

實際用 [`ktime_t` 的 API](https://www.kernel.org/doc/html/latest/core-api/timekeeping.html) 測量 `ksort` 的時間，概念就是用 `ktime_get()` 取得開始和結束的時間戳並且互減，得到運行時間。

static long long sort_time_proxy(long long k)
{
    kt = ktime_get();
    long long result = sort_sequence(k);
    kt = ktime_sub(ktime_get(), kt);

    return result;
}

static ssize_t sort_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    return (ssize_t) sort_time_proxy(*offset);
}

### Linux 效能分析

現代 CPU 幾乎都是多核架構，通常在多核心的作業系統中常使用處理器的親和性 (processor affinity，亦稱 CPU pinning) 讓行程 (process) 在特定的 CPU 核中持續執行，不受作業系統排程的干擾。

### 查看 CPU affinity

查看所有進程的 `pid` ：

$ ps

根據當下正在跑的 process，預期得到以下輸出：

    PID TTY          TIME CMD
   3616 pts/0    00:00:00 bash
   8024 pts/0    00:00:00 ps

接下來針對 `bash` 的 pid 查看 processor affinity，使用參數 `-p` 可以指定行程，其中 `-p` 和 `-cp` 差別只在於要將可對應的 CPU 如何表示，ffff 換成二進位是 16 個 1 ，正好一個位元對應一顆 CPU，該位元為 1 則代表這個行程可以在該 CPU 上面跑，因此 ffff 就是對應第 0~15 CPU 皆可跑此行程。

$ taskset -p 3616
pid 3616's current affinity mask: ffff
$ taskset -cp 3616
pid 3616's current affinity list: 0-15

那如果要指定行程在特定的 CPU 上面運行，我們可以在 `-p` 後面加入 `COREMASK` 參數，用十六進制數字表示要跑在哪幾顆 CPU 上面，而 `-cp` 後面也一樣有 `CORELIST` 參數可用，以下兩種命令都是指定行程 3616 在第 0 個與第 4 個 CPU 核上面跑。

$ taskset -p 0x11 3616
$ taskset -cp 0,4 3616

如果要修改一個行程的處理器親和性，必須要有 [CAP_SYS_NICE](https://man7.org/linux/man-pages/man7/capabilities.7.html) 這個權限，而如果只是查看就沒有限制。

> CAP_SYS_NICE 的功能：
> - 修改任意行程的 [nice value](https://zh.wikipedia.org/zh-tw/Nice%E5%80%BC)
> - 設定任意行程的處理器親和性

還有一個設定是如果你不想要讓其他的行程干擾你正在跑的行程，可以使用 `isolcpus` 這個 Linux 核心起始參數，讓指定的核心只能被自己設定的行程使用。因為這個參數可以讓特定的 CPU 核在開機時就被保存下來。

設定的方式有兩種，以下這種是直接在 GRUB 的設定檔加入參數，這樣 Linux 的排程器在預設的狀況下就不會將任何一般行程放在這個被保留的 CPU 核中執行，只有那些被 [taskset](https://man7.org/linux/man-pages/man1/taskset.1.html) 特別指定的行程可使用這些 CPU 核。

- 打開 GRUB 設定檔
- 第二行不是命令，而是說設定檔裡的這一行，後面加上 `isolcpus=0,1` 代表保留第 0 和第 1 顆 CPU 核。
- 改完之後更新 GRUB 設定檔
- 重新開機

$ sudo nano /etc/default/grub
$ GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=0,1"
$ sudo update-grub
$ sudo reboot

之後要跑行程，我們就可以用 `taskset` 命令來指定已被 `isolcpus` 保留的 CPU 核運行。

$ 

## 研讀作業三 (KXO) 程式碼
> 林志芸

[筆記](https://hackmd.io/@salmonii/kxo)

## 研讀 linux 核心的並行處理
> 邱繼寬

## 研讀 預期目標 和 定點數計算
>Brian

### 定點數
概念：把精度為 n 的浮點數向右位移 n 個位元

#### 乘法除法校正理由
假設兩個精度為 n 的 2 進位浮點數 a, b
其定點數表達為
$a_f = a \times 2^n$
$b_f = b \times 2^n$

$a_f \times b_f = a \times b \times 2^n \times 2^n$
在轉換過程多乘了一個 $2^n$ 故要校正回來
同理發生在除法運算

$\dfrac {a_f}{b_f} = \dfrac {a}{b} \times (\dfrac {2^n}{2^n})$
$2^n$ 被抵消所以要往左位移 n 補回來

#### `fixed_power_int` 解析
理解為在定點數的框架下做計算, 這也是為什麼需要在乘法後做校正
值得一提的是這行

x += 1UL << (frac_bits - 1)

個人認為是做四捨五入讓右移時不會造成誤差大於單位的一半

### load average
意義：表示系統的負載量而非 cpu 的負載
${L_t} = {C_r} + {C_u}$

${L_t}$: 在時間點 t 的 load
${C_r}$: 狀態為 TASK_RUNNABLE的task總數
${C_u}$: 狀態為 TASK_UNINTERRUPTIBLE的task總數

系統在顯示的load average則是移動平滑後的結果
$S_t = \alpha \times X_{t-1} + (1 - \alpha) \times S_{t-1} , where
0 < α < 1$

在load avg 中使用exponential moving average來作為load的計算
所以上述公式的$\alpha$為
$e^{-t_s/T}$
$t_s$ :kernel取樣的秒數,這裡為5秒
$T$ :多少時間尺度的load avg (1min, 5min, 15min)

#### 理解常數定義

#define FSHIFT          11              /* nr of bits of precision */
#define FIXED_1         (1<<FSHIFT)     /* 1.0 as fixed-point */
#define LOAD_FREQ       (5*HZ+1)        /* 5 sec intervals */
#define EXP_1           1884            /* 1/exp(5sec/1min) as fixed-point */
#define EXP_5           2014            /* 1/exp(5sec/5min) */
#define EXP_15          2037            /* 1/exp(5sec/15min) */

- FSHIFT: 精度11的定點數
- FIXED_1：1在定點數的表示法, 右移11位
- LOAD_FREQ: 計算load avg的間隔, HZ在kernel的意義是1秒進行多少次timer interrput, 所以可以當作1單位秒
- EXP_1：$\alpha$在1分鐘的定點數表示法 = $e^{-5/60}$
- EXP_5：$\alpha$在5分鐘的定點數表示法 = $e^{-5/180}$
- EXP_15：$\alpha$在15分鐘的定點數表示法 = $e^{-5/900}$

calc_global_load 函數就是根據指數移動平滑平均和定點數運算在5秒一個間隔去更新load avg 1,5,15的值

### 強化學習（Reinforcement Learning）

#### 馬可夫決策過程（Markov Decision Process)

每列總和為1的轉移矩陣就是右隨機矩陣（right stochastic matrix)

折扣總和（discount sum）定義如下：

$E\left[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_t, s_{t+1})\right], \quad 0 \leq \gamma \leq 1$

為什麼需要一個$\gamma$去做折扣的理由是假設有一個獎勵為正的環,在沒有discount的情況下,最佳選擇就會是一直繞著環的動作,而不會採取其他考慮

自己的對這個discount的見解是下個動作之外的未來是不確定的,所需要對在這個時間點所知的報酬打折扣

##### 理解遞迴式

$V(s) = \sum_{s'} P_{\pi(s)}(s, s')\left(R_{\pi(s)}(s, s') + \gamma V(s')\right)$
在狀態s的折扣回報我們可以分成兩個部分來計算
第一個部分是選擇下一個步驟的回報s'
另一個是s'之後的每個步驟s'', s''', ....,$s^n$的折扣回報
其實這個回報就是$\gamma V(s')$

$\pi(s) = \arg\max_a \left\{ \sum_{s'} P_a(s, s')\left(R_a(s, s') + \gamma V(s')\right) \right\}$
$\pi(s)$: 對應的最佳動作選擇

這樣還是有點難懂 所以去找了一些解說
Bellman Equation
$V(s) = R(s) + \gamma\ max_{a\in A(s)}\sum_{s'}P(s' | s,a)V(s')$
[Value Iteration](https://youtu.be/KovN7WKI9Y0?si=7XNMXNBZA9tTlDgJ)
$V_0(s) <- 0$
$V_{i+1}(s) <- R(s) + \gamma\ max_{a\in A(s)}\sum_{s'}P(s' | s,a)V(s')$
利用每次迭代選擇的最佳步驟 至V(s)的值收斂

#### 例子
左邊狀態的回報計算
第一輪: $3 + 0.5*max(1.0*0.0, 0.5*0.0 + 0.5*0.0) = 3$
第二輪: $3 + 0.5*max(1.0*-1.0, 0.5*3 + 0.5*(-1)) = 3.5$
右邊狀態回報計算
第一輪: $-1 + 0.5*max(1.0*0.0, 0.0*0.0) = -1$
第二輪: $-1 + 0.5*max(1.0*-1, 1.0*3) = 0.5$

以此類推,終止條件是當兩輪的結果收斂
然後選出得到折扣報酬最大的動作

這個方法的必須先知道選擇動作的機率,在實務上可能是未知的
所以在專案ttt裡面的強化學習實作是使用時間差分學習

#### 強化學習演算法（RL Algorithm）
總結就是如同筆記的這句話
強化學習的核心目標是學習最佳的 𝜋，以最大化𝑉𝜋(𝑠)，並透過探索與利用（exploration vs. exploitation）策略來達成最優解。

#### 時間差分學習
學習的目標: 價值函式 $V(s) = E[G_t | S_t = s]$
以ttt為例, 我們學習的是在某個棋盤狀態下剩餘可以放子的格子的價值

$V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$
這個更新公式的關鍵想法是：目前狀態的價值應該向「即時獎勵 + 折扣後的下一狀態價值」靠攏

往下看括號項
$\left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$
意義是實際觀察到的狀態期望扣除當下預期期望,
換句話說,我們看到的比預期的好,遞迴狀態價值就加上學習率＊$\left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$

#### 研讀ttt程式碼

主要關注兩個檔案
- train.c:訓練的主要邏輯
- agents/reinforcement_learning.c: 強化學習的實作

##### agents/reinforcement_learning.c

**int get_action_exploit(char *table, rl_agent_t *agent)**
- 找出在某個棋盤狀態下, 下一步 o/x 最大的報酬
- 回傳值是棋盤的位置

int get_action_exploit(char *table, rl_agent_t *agent)
{
    int max_act = -1;
    float max_q = -FLT_MAX;
    float *state_value = agent->state_value;
    int candidate_count = 1;
#ifdef VERBOSE
    printf("[ ");
#endif
    // 列舉每一個可放棋子的狀態
    for_each_empty_grid (i, table) {
        table[i] = agent->player; //棋手是誰
        float new_q = state_value[table_to_hash(table)];
#ifdef VERBOSE
        printf("%f ", new_q);
#endif
        if (new_q == max_q) {
            ++candidate_count;
            if (rand() % candidate_count == 0) {
                max_act = i;
            }
        } else if (new_q > max_q) {
            candidate_count = 1;
            max_q = new_q;
            max_act = i;
        }
        table[i] = ' ';
    }
#ifdef VERBOSE
    printf(" ]\n");
    printf("exploit %d\n", max_act);
#endif
    return max_act;
}

**int table_to_hash(char *table)**
- 這個函式是把現在的棋盤狀態編碼成一個int
- 方法就是用$\sum_{i=0} S_i*3^{16-i}$,最高位是棋盤i=0的位置

char *hash_to_table(int hash)
- table_to_hash的相反, 把湊雜值變回棋盤

##### train.c

**static float update_state_value**
這個函式就是TD learning的遞迴函式

static float update_state_value(int after_state_hash,
                                float reward,
                                float next,
                                rl_agent_t *agent)
{
    float curr = reward - GAMMA * next; // 不懂為啥是減
    agent->state_value[after_state_hash] =
        (1 - LEARNING_RATE) * agent->state_value[after_state_hash] + // 提項V(S_t)
        LEARNING_RATE * curr;
#if MONTE_CARLO
    return curr;
#else
    return agent->state_value[after_state_hash];
}

**static void train**
訓練的主函式
這裡埰用兩種方法去實作下一步該往哪走
- EPSILON_GREEDY
這裡利用exploration vs exploitation的概念,當取樣隨機小於$\epsilon$下一步就是可以走的格子隨機挑一個,也就是exploration的概念,反之則是採取NON-GREEDY的選擇方式
- NON-GREEDY
選擇state_value裡面最大的格子,詳見上面的敘述

static void train(int iter)
{
    int episode_moves[N_GRIDS];  // from 0 moves to N_GRIDS moves.
    float reward[N_GRIDS];
    int episode_len = 0;
    char table[N_GRIDS];
    memset(table, ' ', N_GRIDS);
    int turn = (iter & 1) ? 0 : 1;  // 0 for 'O', 1 for 'X'
    char win = ' ';
    while (1) {
        if (win == 'D') {
#ifdef VERBOSE
            draw_board(table);
            printf("It is a draw!\n");
#endif
            break;
        } else if (win != ' ') {
#ifdef VERBOSE
            draw_board(table);
            printf("%c won!\n", win);
#endif
            break;
        }
#if EPSILON_GREEDY
        int move = get_action_epsilon_greedy(table, &agent[turn]);
#else
        int move = get_action_exploit(table, &agent[turn]);
#endif
        table[move] = "OX"[turn]; // update move to the table array
        win = check_win(table);
        episode_moves[episode_len] = table_to_hash(table);
        reward[episode_len] =
            (1 - REWARD_TRADEOFF) * get_score(table, agent[turn].player) +
            REWARD_TRADEOFF * calculate_win_value(win, agent[turn].player); // update reward
        ++episode_len;
#ifdef VERBOSE
        draw_board(table);
#endif
        turn = !turn;
    }
    // 
    turn = !turn;  // the player who makes the last move.
    float next = 0;
    for (int i_move = episode_len - 1; i_move >= 0; --i_move) {
        next = update_state_value(episode_moves[i_move], reward[i_move], next,
                                  &agent[turn]);
    }
}

---

## 4/17 利用 bpftrace 追蹤 simrupt 的流程與各項數據

步驟：
1. 下載、編譯並掛載 kxo

 sudo bpftrace -e '
tracepoint:syscalls:sys_enter_openat
/str(args->filename) == "/dev/simrupt"/
{
    printf("Opened /dev/simrupt by pid=%d, comm=%s\n", pid, comm);
}'

開另一個視窗執行以下命令

sudo touch /dev/simrupt

會得到類似的輸出：

Attaching 1 probe...
Opened /dev/simrupt by pid=438455, comm=touch

`comm` 為目前執行緒的 command name，對應於核心結構 task_struct 中的 comm 欄位，用以判斷此時執行該函式的行程名稱。

可注意到

- 邱繼寬的

tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:1, pid=437008, tid=437008
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:1, pid=437008, tid=437008
tasklet_func: comm=bash, pid=3922, tid=362706

- 林本然的

work_func: comm=kworker/u64:3, pid=9329, tid=9329
tasklet_func: comm=ksoftirqd/10, pid=56, tid=56
work_func: comm=kworker/u64:3, pid=9329, tid=9329
tasklet_func: comm=ksoftirqd/9, pid=50, tid=50
work_func: comm=kworker/u64:2, pid=8536, tid=8536
tasklet_func: comm=swapper/9, pid=0, tid=0
work_func: comm=kworker/u64:2, pid=8536, tid=8536
tasklet_func: comm=ksoftirqd/0, pid=16, tid=16
work_func: comm=kworker/u64:2, pid=8536, tid=8536
tasklet_func: comm=swapper/10, pid=0, tid=0
work_func: comm=kworker/u64:2, pid=8536, tid=8536
tasklet_func: comm=swapper/4, pid=0, tid=0