---
title: 2024 年 Linux 核心設計/實作課程作業 —— ttt
image: https://hackmd.io/_uploads/r1ob8RIaa.png
description: 藉由改寫井字遊戲來熟悉數值系統和
tags: linux2024
---

# M03: ttt

> 主講人: [jserv](https://wiki.csie.ncku.edu.tw/User/jserv) / 課程討論區: [2024 年系統軟體課程](https://www.facebook.com/groups/system.software2024/)
:mega: 返回「[Linux 核心設計/實作](https://wiki.csie.ncku.edu.tw/linux/schedule)」課程進度表

## :memo: 預期目標
1. 既然「Linux 核心實作」課程與人工智慧科技碩士學位學程合開，就該有人工智慧的成分。呼應杜威博士提出在實踐中學習 (亦譯作「做中學」) 的教育思想，引導學員接觸 (古典) 人工智慧的基本概念。
2. 藉由改寫井字遊戲來熟悉[數值系統](https://hackmd.io/@sysprog/c-numerics)、[bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)、[排程器原理](https://hackmd.io/@sysprog/concurrent-sched)和 Linux 核心的 List API。
3. 為下個作業準備，即將切入到 Linux 核心模組的開發，預計重用現有程式碼。

## :rocket: 井字遊戲

在 Google 網頁搜尋 "tictactoe"，會發現網頁出現井字遊戲 ([tic-tac-toe](https://en.wikipedia.org/wiki/Tic-tac-toe))，可以在網頁直接玩。

[jserv/ttt](https://github.com/jserv/ttt) 專案提供可跟電腦對弈的互動環境，其對弈的演算法包含以下：
* [negamax](https://en.wikipedia.org/wiki/Negamax) 演算法
* [reinforcement learning](https://en.wikipedia.org/wiki/Reinforcement_learning) (RL) 演算法
* [Monte Carlo tree search](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) (MCTS) 演算法
* [Temporal difference learning](https://en.wikipedia.org/wiki/Temporal_difference_learning) (TD learning) 演算法

編譯並執行:

$ make
$ ./ttt
 1 |             
 2 |             
 3 |             
 4 |             
---+-------------
      A  B  C  D
X> 

輸入 `b2` (即橫向 ABCD 的 "B" 和縱向 1234 的 "2") 並按下 Enter 鍵，表示人類下 `×` 棋子，電腦程式會以 `○` 棋子做出回應，例如：

 1 |             
 2 |     ×  ○    
 3 |             
 4 |             
---+-------------
      A  B  C  D

最終賽局的參考輸出：

 1 |             
 2 |     ×  ○    
 3 |        ×  ○ 
 4 |           × 
---+-------------
      A  B  C  D
X won!
Moves: B2 -> C2 -> C3 -> D3 -> D4

閱讀 [ttt](https://github.com/jserv/ttt) 專案的 "Game Rules" 段落以得知勝負評斷規則。

關於 MCTS 演算法應用於井字遊戲，參閱〈[Tic Tac Toe at the Monte Carlo](https://medium.com/swlh/tic-tac-toe-at-the-monte-carlo-a5e0394c7bc2)〉，搭配以下解說影片:
* [Monte Carlo Tree Search 解說](https://youtu.be/J3I3WaJei_E)
* [Monte Carlo Tree Search - Tic-Tac-Toe Visualization](https://youtu.be/ghhznqBoESY) / [demo page](https://vgarciasc.github.io/mcts-viz/)

馬里蘭大學的網站 [Monte Carlo Tree Search Tic-Tac-Toe AI](https://terpconnect.umd.edu/~mfu/demo/) 提供互動的網頁，可理解 MCTS 演算法。

「蒙地卡羅方法」是利用隨機抽樣技術進行模擬以解決數學問題的策略，在第二次世界大戰期間首次被系統化應用於科學研究，促成 MANIAC（Mathematical Analyzer, Numerical Integrator and Computer）的誕生。由 Stanislaw Ulam, John von Neumann, Nicholas Metropolis、Enrico Fermi 等學者開發，這種以抽樣統計為基礎的方法，主要用於解決原子彈設計中的中子隨機擴散問題及 Schrödinger 方程特徵值的估算問題。最初由 Stanislaw Ulam 提出概念，後經 John von Neumann 深入研究，並於 1949 年以 [The Monte Carlo method](https://permalink.lanl.gov/object/tr?what=info:lanl-repo/lareport/LA-UR-88-9068) 一文公諸於世，隨著電腦時代的來臨，該手法從原始的手動產生隨機數解題轉變為現今的數值方法。

「蒙地卡羅方法」的命名源自 Nicholas Metropolis，靈感來自於其隨機性質與賭博的關聯，尤其是與北非蒙地卡羅城市中華麗的賭場生活息息相關。這方法適用於任何包含隨機性的過程，能夠透過大量模擬單一事件並統計平均值，來獲得在特定條件下的最可能結果。廣泛應用於自然現象如布朗運動、電波噪聲、基因突變、即時交通狀況等，顯示其多樣的適用性。又因該方法的高度可平行處理特性，廣泛應用於電腦圖形學中的光線追蹤技術以及分子動力學模擬等領域。
> 延伸閱讀: [亂灑一地的針其實有意義！布豐實驗與蒙地卡羅方法](https://pansci.asia/archives/165145)

## :calling: Linux 核心的浮點數運算

Robert Love 在 [Linux Kernel Development](https://www.amazon.com/Linux-Kernel-Development-Robert-Love/dp/0672329468/) 一書論及浮點運算:
> No (Easy) Use of Floating Point
> When using floating-point instructions kernel normally catches a trap and then initiates the transition from integer to floating point mode. Unlike user-space, the kernel does not have the luxury of seamless support for floating point because it cannot easily trap itself. Using a floating point inside the kernel requires manually saving and restoring the floating point registers. Except in the rare cases, no floating-point operations are in the kernel.
* 解說: [Use of floating point in the Linux kernel](https://stackoverflow.com/questions/13886338/use-of-floating-point-in-the-linux-kernel)

Rusty Russell 在 [Unreliable Guide To Hacking The Linux Kernel](http://landley.net/kdocs/htmldocs/kernel-hacking.html) 則說:
> The FPU context is not saved; even in user context the FPU state probably won't correspond with the current process: you would mess with some user process' FPU state. If you really want to do this, you would have to explicitly save/restore the full FPU state (and avoid context switches). It is generally a bad idea; use fixed point arithmetic first.

### Lazy FP state restore
[CVE-2018-3665](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2018-3665) 存在於 Intel Core 系列微處理器中，因為 speculative execution（推測執行）技術中的一些缺陷加上特定作業系統中對 FPU（Floating point unit）進行 context switch 所產生的漏洞，允許一個本地端的程式洩漏其他程序的 FPU 暫存器內容。

[Lazy FP state leak](https://en.wikipedia.org/wiki/Lazy_FP_state_restore) 的原理是透過 FPU 的 lazy state switching 機制達成。因為 FPU 和 SIMD 暫存器不一定會在每個任務持續被使用到，因此作業系統排程器可將不需要使用到 FPU 的任務，標註為不可使用 FPU，而不更改裡面的內容。發生 context switch 時，核心先對 FPU/SIMD 做標記，假如在待會新的 context 都沒有用到 FPU/SIMD 相關運算則其 state 將持續保存上個 context 的內容，反之，則會在新的 context 進行相關 ops 前對 kernel 發 trap，以使其保存上個 context 的內容。有鑑於此特性，資訊安全人員發現其可能被濫用的缺陷，因為 FPU/SIMD 相關暫存器不只保存浮點數運算相關資料，其也被用來暫存加密相關資料，例如 [AES](https://en.wikipedia.org/wiki/AES_instruction_set) 指令集。

作業系統相關工程師為了修復此缺陷讓作業系統效能下降 (其中一個解決方法是每次 context switch 都強制 FPU/SIMD state 一起切換，進而增加不少切換時間開銷)，而麻省理工的研究員在 2019 年底提出同時能解決此缺陷又不失效能的途徑 [A better approach to preventing Meltdown/Spectre attacks](https://www.csail.mit.edu/news/better-approach-preventing-meltdownspectre-attacks)。

然而，在現今的[亂序執行](https://en.wikipedia.org/wiki/Out-of-order_execution) CPU 中，lazy state switching 裡會設定的 "FPU not available" 可能沒辦法馬上被偵測到，導致我們在 process B，但仍然可以存取到 process A 的 FPU 暫存器內容，進而達到攻擊的目的。

基於上述原因，儘管我們在 Linux 核心模式中仍可使用浮點運算，但這不僅會拖慢執行速度，還需要手動儲存/取回相關的 FPU 暫存器，因此核心文件不建議在核心中使用到浮點運算。

[afcidk](https://github.com/afcidk) 透過開發簡單的 Linux 核心模組，來測試在單純的浮點數運算及整數運算花費的時間差異。
> 程式碼可見 [floating.ko](https://gist.github.com/afcidk/7178ef368d98ee4b49c7a1acc3704303)


可見到，以單純的運算來說，核心模式中的浮點數運算，時間成本較整數運算高。

### 定點數
並非所有 Linux 支援的硬體都具備 [FPU](https://en.wikipedia.org/wiki/Floating-point_unit)，且 Linux 核心也不建議進行浮點數計算，於是實務上要改用[定點數計算 (Fixed-point arithmetic)](https://en.wikipedia.org/wiki/Fixed-point_arithmetic)。相較於 IEEE 754 浮點數標準，定點數運算沒有一致的格式，常見的處理方式如下：
* 小數點的位置固定
* 以十進位為例，精確度到小數點後 3 位，$number_{10} \times 10^3 = 定點數_{10}$
* 以 2 進位為例，精確度到小數點後 4 位，$number_{2} \times 2^4 = 定點數_{2}$

定點數的運算存在以下常見規格：
* 定點數加法與減法 - 可直接進行
* 定點數乘法 - 結果須再**除** $b^n$ (b 為進制，n 為小數位數)
* 定點數除法 - 結果須再**乘** $b^n$ (b 為進制，n 為小數位數)

[uptime](https://man7.org/linux/man-pages/man1/uptime.1.html) 命令可顯示過去 1 / 5 / 15 分鐘的系統平均負載，類似以下輸出:

$ uptime
11:40:45 up 49 days,  2:47,  3 users,  load average: 0.01, 0.06, 0.02

Linux 核心一類的主流作業系統提供 load average，顧名思義就是要查看近期的負載平均，近期可分成三種時間間隔，計算公式如下：
$$
load_t = n \times \alpha + (1- \alpha) \times load_{t-1}
$$

這個公式很常見，在作業系統決定下一個 cpu burst 時就會運用 [Exponential average](https://www.geeksforgeeks.org/shortest-job-first-cpu-scheduling-with-predicted-burst-time/)。這個公式的好處是簡單且省記憶體的把過去的**歷史資料**都記住，而且會 aging。而很明顯的，這個公式的計算絕對牽涉的浮點數運算，而 Linux 不建議使用浮點運算，於是定點運算就派上用場。

### `fixed_power_int`
研讀 Linux 核心原始程式碼的 Load Average 處理機制，可發現 [linux/kernel/sched/loadavg.c](https://elixir.bootlin.com/linux/v5.3/source/kernel/sched/loadavg.c#L110) 有一個用來計算定點數乘冪的函式 `fixed_power_int`，適合作為理解定點數計算的範例

/**
 * fixed_power_int - compute: x^n, in O(log n) time
 *
 * @x:         base of the power
 * @frac_bits: fractional bits of @x
 * @n:         power to raise @x to.
 *
 * By exploiting the relation between the definition of the natural power
 * function: x^n := x*x*...*x (x multiplied by itself for n times), and
 * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i,
 * (where: n_i \elem {0, 1}, the binary vector representing n),
 * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
 * of course trivially computable in O(log_2 n), the length of our binary
 * vector.
 */
static unsigned long fixed_power_int(unsigned long x,
                                     unsigned int frac_bits,
                                     unsigned int n)
{
    unsigned long result = 1UL << frac_bits;

    if (n) {
        for (;;) {
            if (n & 1) {
                result *= x;
                result += 1UL << (frac_bits - 1);
                result >>= frac_bits;
            }
            n >>= 1;
            if (!n)
                break;
            x *= x;
            x += 1UL << (frac_bits - 1);
            x >>= frac_bits;
        }
    }

    return result;                                                                                                                                            
}

以二進位來思考：
$$
x^n = x^{\sum n_i \cdot 2^i} ,\ n_i\in{0, 1}
$$

以 $x^{11} = x^{1 \cdot 2^0} \times x^{1 \cdot 2^1} \times x^{0 \cdot 2^2} \times x^{1 \cdot 2^3}$ 為例：
* `if (n & 1)` 是否成立，即對應到 $n_i$ 是否為 1
* `1UL << frac_bits` 代表定點數 1 (二進位，小數點後有 `frac_bits` 位)
* `x += 1UL << (frac_bits - 1)` 會讓 `x` 進行無條件進位

因為是進行定點數乘法，還要再除 $2^{frac\_bits}$，亦即 `x >>= frac_bits`

### `loadavg_proc_show`
從 [man proc(5)](http://man7.org/linux/man-pages/man5/proc.5.html) 可知 `/proc/loadavg` 記錄著 load average 相關的資訊

$ cat /proc/loadavg

觀察 [fs/proc/loadavg.c](https://elixir.bootlin.com/linux/v5.3/source/fs/proc/loadavg.c#L33) 會發現 `/proc/loadavg` 是個 pseudo 檔案系統，對照實際輸出資料的函式 `loadavg_proc_show`

static int loadavg_proc_show(struct seq_file *m, void *v)
{
    unsigned long avnrun[3];

    get_avenrun(avnrun, FIXED_1 / 200, 0);

    seq_printf(m, "%lu.%02lu %lu.%02lu %lu.%02lu %ld/%d %d\n",
               LOAD_INT(avnrun[0]), LOAD_FRAC(avnrun[0]), LOAD_INT(avnrun[1]),
               LOAD_FRAC(avnrun[1]), LOAD_INT(avnrun[2]), LOAD_FRAC(avnrun[2]),
               nr_running(), nr_threads,
               idr_get_cursor(&task_active_pid_ns(current)->idr) - 1);
    return 0;
}

觀察 `seq_printf` 使用的格式 `%lu.%02lu`，再由 [include/linux/sched/loadavg.h](https://elixir.bootlin.com/linux/v5.3/source/include/linux/sched/loadavg.h#L43) 理解 `LOAD_INT` 和 `LOAD_FRAC` 的實作

#define LOAD_INT(x) ((x) >> FSHIFT)
#define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)

`%lu.%02lu` 分別使用 `LOAD_INT` 與 `LOAD_FRAC` 來組成完整的十進位數值，其中 `LOAD_INT` 直接取用整數部分，而 `LOAD_FRAC` 會取用小數點 (fraction) 部分，注意 `FIXED_1-1` 可視為小數點部分的 mask，乘上 100 的目的是保留十進位下的小數點後 2 位，而 `FIXED_1/200` 可理解為是十進位下的定點數 0.`005`，由於結果會保留小數點後 2 位，加上此數值目的是進行無條進件位

load average 的資料保存於 `avnrun`。

### Load Average
從 [linux/kernel/sched/loadavg.c](https://elixir.bootlin.com/linux/v5.3/source/kernel/sched/loadavg.c#L331) 可見負責更新 `avnrun` 的函式

/*
 * calc_load - update the avenrun load estimates 10 ticks after the
 * CPUs have updated calc_load_tasks.
 *
 * Called from the global timer code.
 */
void calc_global_load(unsigned long ticks)
{
    unsigned long sample_window;
    long active, delta;

    sample_window = READ_ONCE(calc_load_update);
    if (time_before(jiffies, sample_window + 10))
        return;

    /* Fold the 'old' NO_HZ-delta to include all NO_HZ CPUs. */
    delta = calc_load_nohz_fold();
    if (delta)
        atomic_long_add(delta, &calc_load_tasks);

    active = atomic_long_read(&calc_load_tasks);
    active = active > 0 ? active * FIXED_1 : 0;

    avenrun[0] = calc_load(avenrun[0], EXP_1, active);
    avenrun[1] = calc_load(avenrun[1], EXP_5, active);
    avenrun[2] = calc_load(avenrun[2], EXP_15, active);

    WRITE_ONCE(calc_load_update, sample_window + LOAD_FREQ);

    /*
     * In case we went to NO_HZ for multiple LOAD_FREQ intervals
     * catch up in bulk.
     */
    calc_global_nohz();
}

`calc_load` 是實際計算 load average 的函式，在 [include/linux/sched/loadavg.h](https://elixir.bootlin.com/linux/v5.3/source/include/linux/sched/loadavg.h#L18) 可見其函式實作

/*
 * a1 = a0 * e + a * (1 - e)
 */
static inline unsigned long calc_load(unsigned long load,
                                      unsigned long exp,
                                      unsigned long active)
{
    unsigned long newload;

    newload = load * exp + active * (FIXED_1 - exp);
    if (active >= load)
        newload += FIXED_1 - 1;

    return newload / FIXED_1;
}

計算公式使用 [Exponential smoothing](https://en.wikipedia.org/wiki/Exponential_smoothing)，可參閱〈[Linux Kernel Load Average 計算分析](https://brytonlee.github.io/blog/2014/05/07/linux-kernel-load-average-calc/)〉。其公式如下:
$$
S_t = \alpha \times X_{t-1} + (1 - $\alpha$) \times S_{t-1}, where 0 < α < 1
$$
* $S_t$ : 時間 `t` 的平滑均值。
* $S_{t-1}$ : 時間 `t-1` 的平滑均值。
* $X_{t-1}$ : 時間 `t-1` 的實際值。
* $\alpha$ : 平滑因子 (smoothing factor)。

對應 Linux 核心程式碼如下所示: (取自 `include/linux/sched/loadavg.h`)

newload = load * exp + active * (FIXED_1 - exp);

* S~t~ = newload
* S~t-1~ = load
* X~t-1~ = active (目前 'RUNNABLE + TASK_UNINTERRUPTIBLE' Process 總數: 全域變數 `calc_load_tasks`)
* $\alpha$ = exp

使用定點數:
* LSB 11 bits : mantissa
* MSB 53 bits : exponent

因此定點數 `1.0` 為 `(1 << 11)`，也就是 `FIXED_1` (第 19 行)，這就是為何 $(1 - \alpha)$ 成為 (FIXED_1 - exp)。

- [ ] `include/linux/sched/loadavg.h`

#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) */

/*
 * a1 = a0 * e + a * (1 - e)
 */
static inline unsigned long
calc_load(unsigned long load, unsigned long exp, unsigned long active)
{
        unsigned long newload;

        newload = load * exp + active * (FIXED_1 - exp);
        if (active >= load)
                newload += FIXED_1-1;

        return newload / FIXED_1;
}

extern unsigned long calc_load_n(unsigned long load, unsigned long exp,
                                 unsigned long active, unsigned int n);

#define LOAD_INT(x) ((x) >> FSHIFT)
#define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)

- [ ] `calc_load` 函式：

第 20 行: 每隔 5 秒計算 1 / 5/ 15 分鐘的系統平均負載。
第 21-23 行: 定義 1 / 5 / 15 分鐘的 $\alpha$ 值。
* 1 分鐘 $\alpha$ 值: 1/exp(5sec/1min) = 0.92004441462，其定點數 `0.92004441462 * FIXED_1 = 1884`
* 5 分鐘 $\alpha$ 值: 1/exp(5sec/5min) = 0.98347145382，其定點數 `0.98347145382 * FIXED_1 = 2014`
* 15 分鐘 $\alpha$ 值: 1/exp(5sec/15min) = 0.994459848，其定點數 `0.994459848 * FIXED_1 = 2037`
第 34-35 行: 該判斷式成立的話，代表目前 'RUNNABLE + TASK_UNINTERRUPTIBLE' 行程 (process) 總數大於上次的 load average，則 `newload` 無條件進位。
第 37 行: 由於在第 33 行進行定點數乘法運算，所以其結果需要還原 (除以 `FIXED_1`)。

- [ ] `calc_global_load` 函式

第 355-256 行: 每隔 5 秒 (其實是，5秒 + 10 ticks) 計算 1/5/15 分鐘的系統平均負載。
第 362-367 行: 計算當下 `RUNNABLE + TASK_UNINTERRUPTIBLE` Process/Task 總數。為何需要加入 `TASK_UNINTERRUPTIBLE` task 呢？可參閱 Brendan Gregg 的文章 [Linux Load Averages: Solving the Mystery](https://www.brendangregg.com/blog/2017-08-08/linux-load-averages.html)，詳盡地解說其來龍去脈，Brendan 一開始想透過 `git log -p kernel/sched/loadavg.c` 歷史紀錄找出編修紀錄，但對應修改歷史更久遠，回溯至 v0.99.13 到 v0.99.15 (1993 年)，而 git 要在 2005 年才出現。如下所示 (節錄自 [Linux Load Averages: Solving the Mystery](https://www.brendangregg.com/blog/2017-08-08/linux-load-averages.html)):
> From: Matthias Urlichs \<[e-mail]\>
> Subject: Load average broken ?
> Date: Fri, 29 Oct 1993 11:37:23 +0200
>
> The kernel only counts "runnable" processes when computing the load average.
> I don't like that; the problem is that processes which are swapping or waiting on "fast", i.e. noninterruptible, I/O, also consume resources.
>
> It seems somewhat nonintuitive that the load average goes down when you replace your fast swap disk with a slow swap disk...
>
> Anyway, the following patch seems to make the load average much more consistent WRT the subjective speed of the system. And, most important, the load is still zero when nobody is doing anything. ;-)

--- kernel/sched.c.orig Fri Oct 29 10:31:11 1993
+++ kernel/sched.c  Fri Oct 29 10:32:51 1993
@@ -414,7 +414,9 @@
unsigned long nr = 0;

for(p = &LAST_TASK; p > &FIRST_TASK; --p)
-       if (*p && (*p)->state == TASK_RUNNING)
+       if (*p && ((*p)->state == TASK_RUNNING) ||
+                  (*p)->state == TASK_UNINTERRUPTIBLE) ||
+                  (*p)->state == TASK_SWAPPING))
        nr += FIXED_1;
    return nr;
 }

一言以蔽之，考慮 system load average，而非 CPU load average。

信件發文者 Matthias Urlichs 認為 load average 代表以使用者角度觀察系統忙碌程度，也就是 system load average，而不是 CPU load average。`TASK_UNINTERRUPTIBLE` 表示 process 正在等待某特定事件 (例如: Task swapping、Disk I/O等等)，這也需要算在 system load。底下場景說明為何需要考慮 `TASK_UNINTERRUPTIBLE` (節錄自 [Linux Load Averages: Solving the Mystery](http://www.brendangregg.com/blog/2017-08-08/linux-load-averages.html)):
> A heavily disk-bound system might be extremely sluggish but only have a TASK_RUNNING average of 0.1, which doesn't help anybody.

第 368-370 行: 計算 1/5/15 分鐘的系統平均負載。全域變數 `avenrun` 用定點數格式儲存，所以使用 `printk` 輸出時，需做對應轉換。
第 372 行: 更新下次計算系統平均負載時間，即 `n + 5 秒`。

- [ ] `kernel/sched/loadavg.c`

/*
 * calc_load - update the avenrun load estimates 10 ticks after the
 * CPUs have updated calc_load_tasks.
 *
 * Called from the global timer code.
 */
void calc_global_load(unsigned long ticks)
{
        unsigned long sample_window;
        long active, delta;

        sample_window = READ_ONCE(calc_load_update);
        if (time_before(jiffies, sample_window + 10))
                return;

        /*
         * Fold the 'old' NO_HZ-delta to include all NO_HZ CPUs.
         */
        delta = calc_load_nohz_read();
        if (delta)
                atomic_long_add(delta, &calc_load_tasks);

        active = atomic_long_read(&calc_load_tasks);
        active = active > 0 ? active * FIXED_1 : 0;

        avenrun[0] = calc_load(avenrun[0], EXP_1, active);
        avenrun[1] = calc_load(avenrun[1], EXP_5, active);
        avenrun[2] = calc_load(avenrun[2], EXP_15, active);

        WRITE_ONCE(calc_load_update, sample_window + LOAD_FREQ);

        /*
         * In case we went to NO_HZ for multiple LOAD_FREQ intervals
         * catch up in bulk.
         */
        calc_global_nohz();
}

`loadavg_proc_show` 輸出 1 / 5 / 15 分鐘的系統平均負載:
* `LOAD_INT`: 取得整數部分。
* `LOAD_FRAC`: 取得小數點部分。因為只取小數點兩位，所以此巨集裡可看到乘以 100。

- [ ] `fs/proc/loadavg.c`

static int loadavg_proc_show(struct seq_file *m, void *v)
{
        unsigned long avnrun[3];

        get_avenrun(avnrun, FIXED_1/200, 0);

        seq_printf(m, "%lu.%02lu %lu.%02lu %lu.%02lu %ld/%d %d\n",
                LOAD_INT(avnrun[0]), LOAD_FRAC(avnrun[0]),
                LOAD_INT(avnrun[1]), LOAD_FRAC(avnrun[1]),
                LOAD_INT(avnrun[2]), LOAD_FRAC(avnrun[2]),
                nr_running(), nr_threads,
                idr_get_cursor(&task_active_pid_ns(current)->idr) - 1);
        return 0;
}

## :penguin: 作業要求
1. 確認你已著手投入 [M03: review](https://hackmd.io/@sysprog/linux2024-review)，至少達成指定的「檢查事項 1」，才進行本作業。
2. 將 [jserv/ttt](https://github.com/jserv/ttt) 專案的程式碼部分整合進 [lab0-c](https://github.com/sysprog21/lab0-c) 並確保符合以下規範：
* 將 Linux 核心的 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 標頭檔與 `hlist` 相關的程式碼抽出，成為 `hlist.h`，並確保後者可與 [lab0-c](https://github.com/sysprog21/lab0-c) 既有的 `list.h` 並存，[jserv/ttt](https://github.com/jserv/ttt) 專案的 `zobrist.[ch]` 會用到 `hlist.h`
* 修改 `qtest` 程式，使其新增 `ttt` 命令，其作用是執行與人類對弈的井字遊戲，並使用 [Monte Carlo tree search](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search) (MCTS) 演算法，確保使用定點數來取代原本 [jserv/ttt](https://github.com/jserv/ttt) 的浮點數運算。
* 擴充上述 `ttt` 命令，在 `qtest` 引入新的 `option` (參照 `cmd>` 命令提示的 ` help` 說明文字)，允許使用者切換「人 vs.電腦」或「電腦 vs. 電腦」的對弈，注意後者應該採取 MCTS 以外的演算法 (也可納入你發展的演算法)。對弈的過程中，要在螢幕顯示當下的時間 (含秒數)，並持續更新。
* 針對 `ttt` 命令的「電腦 vs. 電腦」的對弈模式，參照〈[並行程式設計：排程器原理](https://hackmd.io/@sysprog/concurrent-sched)〉，引入若干 coroutine (注意：不得使用 POSIX Thread，採取教材提到的實作方式)，分別對應到 AI~1~, AI~2~ (具備玩井字遊戲的人工智慧程式，採取不同的演算法) 和鍵盤事件處理，意味著使用者可連續觀看**多場**「電腦 vs. 電腦」的對弈，當按下 Ctrl-P 時暫停或回復棋盤畫面更新 (但運算仍持續)、當按下 Ctrl-Q 時離開「電腦 vs. 電腦」的對弈，注意不該使用 (n)curses 函式庫。當離開「電腦 vs. 電腦」的對弈時，`ttt` 應顯示多場對弈的過程，亦即類似 `Moves: B2 -> C2 -> C3 -> D3 -> D4` 的輸出，儘量重用現有的結構體和程式碼。
> 關於鍵盤事件和終端機畫面的處理機制，可參見 [mazu-editor](https://github.com/jserv/mazu-editor) 原始程式碼和〈[Build Your Own Text Editor](https://viewsourcecode.org/snaptoken/kilo/)〉。
* 亂數產生器對於 MCTS 相當重要，可參照 [Improving performance and efficiency of PRNG](https://github.com/jserv/ttt/issues/32)，嘗試引入其他快速的 PRNG 實作並比較 MCTS 實作獲得的效益。
* 在「電腦 vs. 電腦」的對弈模式，比照前述 load average 的計算方式，規範針對下棋 AI 的 load 機制，並運用定點數來統計不同 AI 實作機制對系統負載的使用率，整合到 `qtest` 輸出，開發過程中應有對應的數學分析和羅列實作考量因素。
* 考慮到畫面更新不該混雜其他 `printf` 的訊息，可運用 [GDB 進行遠端除錯](https://hackmd.io/@sysprog/gdb-example)。
4. 改寫 [lab0-c](https://github.com/sysprog21/lab0-c) 既有的 `shannon_entropy.c` 和 `log2_lshift16.h`，採用更有效、[準確度](https://highscope.ch.ntu.edu.tw/wordpress/?p=24512) (accuracy) 更高的定點數運算實作，需要有對應的數學統計分析和實際執行的討論。
> Linux 核心原始程式碼 [fs/btrfs/compression.c](https://github.com/torvalds/linux/blob/master/fs/btrfs/compression.c) 存在 [Shannon Entropy](https://en.wikipedia.org/wiki/Entropy_(information_theory)) 的計算，其程式碼註解提到 "Use of ilog2() decreases precision, we lower the LVL to 5 to compensate"。檔名的 "compression" 意味著 btrfs 檔案系統具備壓縮，而這機制就用到 [Shannon Entropy](https://en.wikipedia.org/wiki/Entropy_(information_theory)) 進行估算。
5. 不需要建立新的共筆，更新自己列於 ==[Homework1 作業區](https://hackmd.io/@sysprog/linux2024-homework1)== 的 `lab0-c` 開發紀錄後方即可，程式碼的變更應提交於你所 fork 的 `lab0-c` 儲存庫 (repository) 中，留意 [M03: review](https://hackmd.io/@sysprog/linux2024-review) 的規範。
7. 截止日期： Mar 25, 2024