Linux 核心專題: 改進 lab0

執行人: oEric0929o

提問清單

• ?

任務簡述

重做 lab0 並彙整其他學員的成果。

TODO: 達成作業所有要求

queue.c

[目前進度](https://hackmd.io/iSd6FlDuTjas3U9mnmpW0Q) 95/100

關於進度，直接更新在「本頁面」

jserv

引入 lib/list_sort.c

參考 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 同學的做法，在 queue.c 中新增 shuffle 函式

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

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

整合網頁伺服器

TODO

研讀論文〈Dude, is my code constant time?〉

TODO

Valgrind 與 Address Sanitizer 記憶體檢查

TODO

TODO: 研讀 Linux 的 lib/list_sort.c 並量化分析

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

lib/list_sort.c

TODO: 改進原有常數時間複雜度判斷程式

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

TODO: 藉由 Timsort 嘗試改進 lib/list_sort.c

應保持原本 in-place 排序的實作策略。