# Linux 核心專題: 改進 lab0
> 執行人: oEric0929o

:::success
:question: 提問清單
* ?
:::

## 任務簡述

重做 [lab0](https://hackmd.io/@sysprog/linux2023-lab0) 並彙整其他學員的成果。

## TODO: 達成作業所有要求

### queue.c
<s>
[目前進度](https://hackmd.io/iSd6FlDuTjas3U9mnmpW0Q) 95/100
</s>

:::danger
關於進度，直接更新在「本頁面」
:notes: jserv
:::

### 引入 lib/list_sort.c
參考 [chiangkd](https://github.com/chiangkd) 同學的做法，將 lib/list_sort.c 及 lib/list_sort.h 引入專案，並修改 Makefile

在 qtest.c 中新增 do_lsort 並新增 lsort 命令

比較自己實作的 merge sort 以及 Linux 核心程式碼的效能落差

cmd> new
cmd> ih RAND 260000
cmd> time sort
Delta time = 0.190
cmd> free

cmd> new
cmd> ih RAND 260000
cmd> time lsort
Delta time = 0.152

兩者的時間約相差1.25倍

### 在 qtest.c 提供新的命令 shuffle

參考 [chiangkd](https://github.com/chiangkd) 同學的做法，在 queue.c 中新增 shuffle 函式

利用不斷抽取隨機元素放到最末端達到洗牌的效果

在 qtest.c 中新增 do_shuffle 並新增 shuffle 命令

### 整合網頁伺服器

TODO

### 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉

TODO

### Valgrind 與 Address Sanitizer 記憶體檢查

TODO

## TODO: 研讀 Linux 的 `lib/list_sort.c` 並量化分析
解讀 Linux 核心原始程式碼的 `lib/list_sort.c`，設計實驗來量化分析，探討其實作手法，需要善用 perf 一類的工具。解析程式碼要有完整的圖文、數學證明，和如何達到 cache 友善。

[lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)

## TODO: 改進原有常數時間複雜度判斷程式
搭配研讀必要的統計原理，探討如何改進原有常數時間複雜度判斷程式

## TODO: 藉由 Timsort 嘗試改進 `lib/list_sort.c`
應保持原本 in-place 排序的實作策略。