---
# System prepended metadata

title: 2024q1 Homework6 (integration)
tags: [linux2024]

---

# 2024q1 Homework6 (integration)

contributed by < `yinghuaxia` >

### 開發環境

```shell
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  1
    Core(s) per socket:  8
    Socket(s):           1
    Stepping:            13
    CPU max MHz:         4700.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6000.00
```

### 自我檢查清單

- [x] 研讀前述 Linux 效能分析描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 從中也該理解為何不希望在虛擬機器中進行實驗;

首先先檢查 Linux 核心版本：

```shell
$ uname -r

6.5.0-27-generic
```

再確認 `linux-headers` 套件有成功的被安裝：

```shell
$ dpkg -L linux-headers-6.5.0-27-generic | grep "/lib/modules"

/lib/modules
/lib/modules/6.5.0-27-generic
/lib/modules/6.5.0-27-generic/build
```

根據 [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module) 中的掛載核心模組測試流程進行測試，包含編譯核心模組、掛載核心模組：

```shell
$ make -C /lib/modules/`uname -r`/build M=`pwd` modules
$ sudo insmod hello.ko
$ sudo dmesg

[ 3893.338854] Hello, world
```

卸載核心模組：

```shell
$ sudo rmmod hello
$ sudo dmesg

[ 3893.338854] Hello, world
[ 4040.706322] Goodbye, cruel world
```

觀察 `fibdrv.ko` 核心模組在 Linux 核心掛載後的行為:
```Shell
$ cat /sys/class/fibonacci/fibonacci/dev

236:0
```

在 `/sys/class` 底下的檔案為 kernel 在執行時間輸出的，讓 kernel 與不同的 classes 之間可以做裝置或是子系統相關的存取。在 `fibonacci/dev` 中代表的是 `fibonacci` 類別底下一個設備相關的文件。閱讀 `fibdrv.c` 中的初始化函式 `init_fib_dev`，我們可以看見有註解寫的是：
```C
// Let's register the device
// This will dynamically allocate the major number
rc = major = register_chrdev(major, DEV_FIBONACCI_NAME, &fib_fops);
```

[register_chrdev](https://archive.kernel.org/oldlinux/htmldocs/kernel-api/API---register-chrdev.html) 這個函式的功能在於分配一個還沒被使用的主設備編號，並註冊符號相關的文件操作，最後回傳一個 `int` 值，代表符號註冊到的主設備編號。這個編號由 kernel 進行分配，並且是唯一的，我們使用 `printk` 將 `major` 的數值印出來：

```shell
[356138.588080] The value of major: 236
```

可以看到這個數值與 `fibonacci/dev` 中的數值相同，而在 `fibdrv.c` 中，  `minor` 這個變數一開始宣告為全域變數，其值為 0。`major` 和 `minor` 兩個數值會接著被輸入 `MKDEV` 這個巨集。[MKDEV](https://man7.org/linux/man-pages/man3/function::mkdev.3stap.html) 的功能在於將主設備編號 (major) 和次設備編號 (minor) 合併成一個長度為 32 bit 的設備編號 (device number)，其中最高的 12 bit 表示的是主設備編號，低的 20 bit 為次設備編號。我們將 `MKDEV` 的結果印出來：

```shell
[358995.872061] The value of fib_dev: 247463936
```

將 247463936 轉為二進位後的值為 00001110 - 11000000 - 00000000 - 00000000，而 236 轉為二進位後的值為 11101100， `fib_dev` 前 12 bit 可以對上

:::info
:question: 為什麼要將主設備編號和次設備編號以 20 bit 和 12 bit 的長度進行分配。
:::


在自己的實體電腦運作 GNU/Linux 和在虛擬機器中進行實驗的差異包含：
* 硬體資源限制：使用虛擬機可能會受限於我們分配給他的資源，像是 CPU、記憶體和硬碟的空間，可能會造成性能的差異。
* 虛擬機額外成本：虛擬機的概念是在硬體上建立虛擬化層，這個層會負責管理虛擬機的資源，因此在運作時會造成額外的 CPU 開銷，造成系統性能的評估有偏差。
* 擴展性：實體電腦的 GNU/Linux 允許更多元的擴展可能性，而虛擬機可能會受限於虛擬機軟體的限制。

- [x] 閱讀〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 `insmod` 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？
    
    #### insmod 解釋
    [insmod](https://man7.org/linux/man-pages/man8/insmod.8.html) 的功能在於 insert 一個模組到 Linux 的 Kernel。在[程式碼](https://kernel.googlesource.com/pub/scm/linux/kernel/git/mmarek/kmod/+/v6/tools/kmod-insmod.c)中，主要進行空間分配動作的函式為 `int do_insmod`，最後會根據操作的結果返回一個 `int`，來表示此操作是否有成功，部份程式碼如下：
    ```C
    for (i = optind + 1; i < argc; i++) {
		size_t len = strlen(argv[i]);
		void *tmp = realloc(opts, optslen + len + 2);
		if (tmp == NULL) {
			fputs("Error: out of memory\n", stderr);
			free(opts);
			return EXIT_FAILURE;
		}
		opts = tmp;
		if (optslen > 0) {
			opts[optslen] = ' ';
			optslen++;
		}
		memcpy(opts + optslen, argv[i], len);
		optslen += len;
		opts[optslen] = '\0';
	}
	ctx = kmod_new(NULL, &null_config);
	if (!ctx) {
		fputs("Error: kmod_new() failed!\n", stderr);
		free(opts);
		return EXIT_FAILURE;
	}
	err = kmod_module_new_from_path(ctx, filename, &mod);
	if (err < 0) {
		fprintf(stderr, "Error: could not load module %s: %s\n",
			filename, strerror(-err));
		goto end;
	}
	err = kmod_module_insert_module(mod, 0, opts);
	if (err < 0) {
		fprintf(stderr, "Error: could not insert module %s: %s\n",
			filename, mod_strerror(-err));
	}
	kmod_module_unref(mod);

    ```
    for loop 的目的在於根據傳入的參數，使用 `realloc` 函式依次指派對應長度的位置給他們，其中的 `optslen + len + 2` 包含了已經儲存的字符串長度、當前參數的長度，以及 `2` 是用於儲存空格和結束符的空間。`if (tmp == NULL)` 則是對 `realloc` 函式的返回值進行判斷，如果返回值為 NULL，則代表動態分配內存的動作是失敗的，會使用 `fputs` 輸出內存已滿的錯誤訊息，並使用 `free` 函式將之前分配的空間釋放，以避免內存遭佔用，最後結束程式的執行。如果動態分配內存的動作成功，則會使用 `opts` 指向新的內存空間，並在確認已有模組儲存之後，在其後面加上一個 `' '` 空格來分開不同的模組，並將當前 `argv[i]` 的內容複製到 `opts` 指向的 `opts + optslen` 內存空間之中，將所有的模組串接在一起。根據當前參數長度更新 `optslen` 之後，在字符串的最後加上 `\0` 作為結尾。
    
    `kmod_new` 的目的在於創建 `kmod_ctx` 的上下文，用來與 `libkmod` 函式庫溝通，以利執行後續的操作。`kmod_module_new_from_path` 是為了從指定的文件路徑當中建立 `kmod_module` 模組，如果模組的文件不存在或是無法被讀取，則會返回錯誤。之後再將創建的模組插入到 Linux kernel 中，這個步驟將模組的內容加載到 kernel 中的同時，也會將模組的符號解析為 kernel 中已經存在的符號。最後要將分配的資源釋出，包含原本儲存模組的內存、`kmod_ctx` 上下文和相關的 `kmod_module` 模組。
    
    `insmod` 運作的流程包含呼叫了一個 `finite_module` 的函式，如下第八行處所示：
    ```shell=
    $ sudo strace insmod fibdrv.ko
    ...
    openat(AT_FDCWD, "/home/yinghuaxia/test_code/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
    read(3, "\177ELF\2\1", 6)               = 6
    lseek(3, 0, SEEK_SET)                   = 0
    newfstatat(3, "", {st_mode=S_IFREG|0664, st_size=274808, ...}, AT_EMPTY_PATH) = 0
    mmap(NULL, 274808, PROT_READ, MAP_PRIVATE, 3, 0) = 0x790a37b0a000
    finit_module(3, "", 0)                  = -1 EEXIST (File exists)
    write(2, "insmod: ERROR: could not insert "..., 62insmod: ERROR: could not insert module fibdrv.ko: File exists
    ) = 62
    munmap(0x790a37b0a000, 274808)          = 0
    close(3)                                = 0
    exit_group(1)                           = ?
    +++ exited with 1 +++
    ```
    
    當中有 `module_init` 這個負責初始化模組的函式，其程式碼如下所示：
    ```C
    /* Each module must use one module_init(). */
    #define module_init(initfn)					\
        static inline initcall_t __maybe_unused __inittest(void)		\
        { return initfn; }					\
        int init_module(void) __attribute__((alias(#initfn)));
    ```
    傳入的 `initfn` 是我們想要初始化的模組 pointer，`static inline initcall_t __maybe_unused __inittest` 被宣告成一個靜態的 inline 函式，靜態表示這個函式只有在現在這個編譯的單元才能被看見，而 inline 則是代表這個函示會被直接插入到調用的位置，而不像一般的函式一樣進行調用。這個函數回傳的是可能會被編譯器優化掉的 `initcall_t` 類別，是一個常用於 Linux kernel 的初始化函數 pointer，`__maybe_unused` 是給編譯器的一個提示，說明這個函式可能不會被使用到，避免產生警告，最後的 `__inittest(void)` 則是負責確保傳入的函式可以與 `initcall_t` 相容，將兩者連結起來。
    
    [\_\_attribute\_\_((alias(...)))](https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#index-alias-function-attribute) 的使用方式如下：
    > The alias attribute causes the declaration to be emitted as an alias for another symbol, which must have been previously declared with the same type, and for variables, also the same size and alignment. Declaring an alias with a different type than the target is undefined and may be diagnosed.
    
    `int init_module(void) __attribute__((alias(#initfn)))` 意思是將 `#initfn` 定義為 `init_module`，讓兩個函式可以用不同名稱實現對同一個函式的引用，因此在呼叫 `init_module` 存取的是 `#initfn` 的模組。

    #### Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)
    上面提及的 「將模組的符號解析為 kernel 中已經存在的符號」 可能是透過 `kallsyms_lookup_names()` 和 `kallsyms_on_each_symbol()` 來實現。兩個函式在 [kernel/kallsyms.c](https://github.com/torvalds/linux/blob/master/kernel/kallsyms.c) 定義，以下對 `kallsyms_lookup_names` 的程式碼進行解析：
    ```C
    static int kallsyms_lookup_names(const char *name,
				 unsigned int *start,
				 unsigned int *end)
    {
        int ret;
        int low, mid, high;
        unsigned int seq, off;
        char namebuf[KSYM_NAME_LEN];

        low = 0;
        high = kallsyms_num_syms - 1;

        while (low <= high) {
            mid = low + (high - low) / 2;
            seq = get_symbol_seq(mid);
            off = get_symbol_offset(seq);
            kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
            ret = compare_symbol_name(name, namebuf);
            if (ret > 0)
                low = mid + 1;
            else if (ret < 0)
                high = mid - 1;
            else
                break;
        }

        if (low > high)
            return -ESRCH;

        low = mid;
        while (low) {
            seq = get_symbol_seq(low - 1);
            off = get_symbol_offset(seq);
            kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
            if (compare_symbol_name(name, namebuf))
                break;
            low--;
        }
        *start = low;

        if (end) {
            high = mid;
            while (high < kallsyms_num_syms - 1) {
                seq = get_symbol_seq(high + 1);
                off = get_symbol_offset(seq);
                kallsyms_expand_symbol(off, namebuf, ARRAY_SIZE(namebuf));
                if (compare_symbol_name(name, namebuf))
                    break;
                high++;
            }
            *end = high;
        }

        return 0;
    }
    ```
    這個函式首先先接收一個符號名稱以及兩個指向 unsigned int 的 pointer 作為儲存該符號的起始與結束位址，接著使用 binary search 的方式尋找該符號，透過 `compare_symbol_name` 找到該符號之後會更新 pointer，使其指向該符號起始與結束位址，若沒有找到對應的符號，則會回傳錯誤碼 `-ESRCH`。List API 本身主要是用於實現對串列的操作，也因此可能會用於讓符號表的使用更容易，像是符號的逐一走訪、插入、刪除等動作都可以由 List API 中的函式完成。
    
    #### MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)
    
    `MODULE_LICENCE` 巨集主要用來指定一個模組的授權條款，例如說明這個模組是否為開源，來規範一個模組的使用權限及相關需要注意的限制。會再編譯之後在 `.ko` 檔中提供對應的資訊，以下為一些常用的授權：
    
    ```C
    /*
     * The following license idents are currently accepted as indicating free
     * software modules
     *
     *	"GPL"				[GNU Public License v2 or later]
     *	"GPL v2"			[GNU Public License v2]
     *	"GPL and additional rights"	[GNU Public License v2 rights and more]
     *	"Dual BSD/GPL"			[GNU Public License v2
     *					 or BSD license choice]
     *	"Dual MIT/GPL"			[GNU Public License v2
     *					 or MIT license choice]
     *	"Dual MPL/GPL"			[GNU Public License v2
     *					 or Mozilla license choice]
     *
     * The following other idents are available
     *
     *	"Proprietary"			[Non free products]
     */
    ```
    
    使用 GPL 授權的意思是這個模組只能使用於有包含 GPL 或相關兼容許可的軟體中，這個動作會影響到模組可以使用的符號列表，因為這代表這個模組只能與 kernel 中的符號進行連接，不能與非 GPL 授權的符號進行連接，以確保整個 kernel 中符號的一致性。如果沒有使用 GPL 授權，則符號列表會藉由 `EXPORT_SYMBOL_GPL()` 做輸出，只能與同一個授權下的符號進行連接，防止非 GPL 授權的模組與 GPL 授權的模組進行不當的結合，進而造成使用上的衝突。
    
    Reference：[The Linux Kernel Module Programming Guide - Ch2 Hello World](https://tldp.org/LDP/lkmpg/2.6/html/x279.html)
    
    #### 藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統
    
    [strace](https://man7.org/linux/man-pages/man1/strace.1.html) 的功能是追蹤系統的呼叫及宣告，可以讓使用者快速的了解一個程式如何與作業系統互動。以下為幾個與掛載相關的 strace 命令，更多的指令可以從 [strace/groups](https://github.com/torvalds/linux/blob/master/tools/perf/trace/strace/groups/string) 中得到更多資訊：
    * execve: 用於一個程式的執行
    * access: 檢查一個文件是否存在以及能否被訪問
    * openat: 打開文件
    * fstat: 用於得到一個文件的狀態，例如一個文件的大小、權限等
    * mmap: 將文件投射到內存中
    * close: 關閉文件

    上述的命令可以被歸類於幾個常用的子系統當中，例如文件系統相關(包含創立文件、讀取文件、更動文件等)的 `openat`、`read`、`write` 等；內存管理相關(負責內存的分配、釋放等操作)的 `mmap`、`munmap`、`mprotect` 等；process 管理相關(像是 process 的建立、銷毀、轉換等操作)的 `execve`、`fork`、`wait` 等。透過不同子系統來負責不同功能的執行，就可以構建 Linux kernel 的相關操作。
    

- [x] 閱讀《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free;

    [simrupt](https://github.com/sysprog21/simrupt/blob/main/simrupt.c) 的功能在於可以允許模擬硬體中斷的情形發生，同時也提供了不同優先級的中斷模擬、觸發的方式、中斷處理的延遲時間等，讓開發人員可以更有彈性的對硬體中斷做測試。在 `simrupt` 的程式碼中，mutex lock 的功能在於提供共享資源多一層的保護，以確保在 multi-thread 的操作中發生覆蓋、競爭所導致的不一致性。
    
    `mutex_lock` 在 `static void simrupt_work_func(struct work_struct *w)` 中出現，同時也會搭配 `mutex_unlock`。整體流程是首先對 `mutex` 變數做定義：`static DEFINE_MUTEX(consumer_lock);`，此變數會被用於保護共享資源
    
    ```C
    while (1) {
            /* Consume data from the circular buffer */
            mutex_lock(&consumer_lock);
            val = fast_buf_get();
            mutex_unlock(&consumer_lock);

            if (val < 0)
                break;

            /* Store data to the kfifo buffer */
            mutex_lock(&producer_lock);
            produce_data(val);
            mutex_unlock(&producer_lock);
        }
        wake_up_interruptible(&rx_wait);
    ```
    在 `mutex_lock` 和 `mutex_unlock` 之間會執行需要被保護的操作，放置在在之間的動作可以確保只有一個 thread 可以對他們進行執行的動作。`mutex_unlock` 之後，就可以允許其他的 thread 執行原本放置在 `mutex lock` 之間的動作。在上面第一個 `mutex lock` 之間的程式碼中做的動作是從 `fast_buf` 獲得確定沒有被其他 thread 干擾的資料，第二個 `mutex lock` 之間則是將剛剛從 `fast_buf` 獲得的資料進行 `produce_data` ，也就是將資料存入 `kfifo` buffer 的操作。最後的 [wake_up_interruptible(&rx_wait)](https://elixir.bootlin.com/linux/latest/source/include/linux/wait.h#L210) 定義如下程式碼所示，其目的是要喚醒在 `rx_wait` 中的 thread，通常這個步驟會使用在有新的可存取的資料出現，提醒使用者可以進行存取。
    ```C
    #define wake_up_interruptible(x)	__wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)
    ```
    除了使用 lock 的方式確保動作只能被一個 thread 存取之外，也可以嘗試使用 [lock free](https://hackmd.io/@sysprog/concurrency-lockfree) 的方式操作。以下對 lock 和 lock free 的操作進行分析：
    1. 性能： 使用 lock free 方式的優勢在於效能的提升，在 thread 之間高度競爭的情況發生時尤為明顯，因為 lock 會使得 thread 在等待時被阻塞，進而導致性能的下降與系統資源的浪費; 而 lock free 則允許 thread 可以同時執行。
    2. 複雜性：因為 lock 提供了明確的語意（在 lock 與 unlock 之間的操作就是只能由一個 thread 存取），因此在實作上較容易，也較容易被理解，然而可能會遇到 [dead lock](https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=https://en.wikipedia.org/wiki/Deadlock&ved=2ahUKEwisjtTNkd-FAxUVna8BHeG_C0AQFnoECDwQAQ&usg=AOvVaw3_xcM2p0YtTCMMNQY8R3nF) 或是 [starvation](https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=https://en.wikipedia.org/wiki/Starvation_(computer_science)&ved=2ahUKEwixx-Xikd-FAxWJkq8BHbkOCi0QFnoECBwQAQ&usg=AOvVaw3zEXJw60FPFXd3R_pdpjE8) 的問題; loack free 的作法通常比較複雜，因為需要考慮 thread 之間的競爭與搶佔情形，往往需要更深入的了解系統的運作，然而卻能提供更好的性能。
    4. 使用場景：lock 通常會被用於較簡單的開發場景，或是對於 thread 之間互斥要求較高的情況; lock free 則常用於對效能較敏感的開發上。

    lock free 有幾種方式可以實作：
    - [RCU(Read-Copy Update)](https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=https://en.wikipedia.org/wiki/Read-copy-update&ved=2ahUKEwiGjtfBjt-FAxWem68BHXvZDM4QFnoECBcQAQ&usg=AOvVaw06aOLddpJidvQCYtKlqSOY): 這個方式通常用於多個 reader (讀取頻繁) 但少個 update/writer (資料寫入不頻繁) 的情況。RCU 的作法是當一個 thread 想要讀取共享的操作時可以直接進行，不需要被 lock 所限制，因此可以允許多個 thread 同時進行讀取數據的動作。當一個數據需要被更新時，RCU 會先進行一個複製的動作，以確保原始數據在更新的過程中不會被更動到，也因為複製是一個輕量級的動作，因此不會對其他 threads 的運作造成堵塞，一旦更新完成，RCU 就會更新指向共享數據的指針，讓其他的 threads 可以存取到最新的資訊。最後，當沒有 thread 要使用舊數據時，RCU 就會在一個特定的延遲時間之後進行回收舊數據的動作，以確保沒有 threads 會對就數據進行訪問。
    - [Atomic Operation](https://hackmd.io/@sysprog/concurrency-atomics)：Atomic operation 能夠確保操作的執行是不可分割的，也就是一個操會址會有完全完成或是沒有執行兩個狀態，這種方式可以確保多個 threads 在同一個時間對共享資源進行搶佔的情況發生。
    - [Sequential Consistency](https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=https://en.wikipedia.org/wiki/Sequential_consistency&ved=2ahUKEwiq3K_vod-FAxX8hq8BHWyBDMQQFnoECCUQAQ&usg=AOvVaw3GaV05cWgqo94ddF_ckmag): 其定義為
        > the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program
    
        概念是多個 thread 在沒有 lock 限制的情況下，他們對於數據的訪問看起來是基於某種順序的，也就是說雖然沒有 lock，但是我們仍可對 thread 的運作做預測。這個操作的方式可以確保每次存取時的一致性。如下圖所示，A1, B1 和 C1 的執行順序是被排定的，也就是 A1 會在 B1 之前執行，B1 會在 C1 之前執行; 同理套用於 A2 和 B2 上。然而因為 processor 之間的順序未被定義，因此無法決定 `1` 結尾的 thread 和 `2` 結尾的 thread 彼此之間的先後順序。
        ![image](https://hackmd.io/_uploads/BkTIpTu-R.png)

    - [Memory Ordering](https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=https://en.wikipedia.org/wiki/Memory_ordering&ved=2ahUKEwjawMfbpN-FAxVtbfUHHZI1Bt8QFnoECBIQAQ&usg=AOvVaw1fr9SAjGB6LWy29m9XE487): Memory ordering 會指定讀取和寫入 memory 的順序，也因此它可以指定一個 thread 的寫入操作何時可以讓其他 thread 可見，以及一個 thread 何時能夠觀察到令一個 thread 對於共享操作的寫入結果。透過指定編譯器和處理器執行指令的順序，我們就可以確定操作的執行順序有符合我們的預期。
    
- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 lib/sort.c 在排序過程中的平均比較次數，並提供對應的數學證明;
    > 對照 fluxsort 和 crumsort 的分析和效能評比方式

- [ ] 研讀 [CMWQ](https://www.kernel.org/doc/html/latest/core-api/workqueue.html) (Concurrency Managed Workqueue) 文件，對照 simrupt 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？
    > 搭配閱讀《Demystifying the Linux CPU Scheduler》
    

- [ ] 解釋 `xoroshiro128+` 的原理 (對照〈[Scrambled Linear Pseudorandom Number Generators](https://arxiv.org/pdf/1805.01407.pdf)〉論文)，並利用 ksort 提供的 `xoro` 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 `xoroshiro128+` 是否有速度的優勢？其弱點又是什麼？
    > 搭配閱讀: 不亂的「亂數」
- [ ] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序