版本 2ab949aa80d921c9bea143d8170c2ddcae09dace
Changes from 2ab949aa80d921c9bea143d8170c2ddcae09dace to 9e1a5b8239821d367d4187486e32e686b0f91299
---
title: 164253 (丁士鈞)
categories: User
...
# 簡介
* 國立成功大學 資訊工程學系 116 級 (2023~)
* GitHub: [`164253`](https://github.com/164253)
* HackMD: [`164253`](https://hackmd.io/@164253)
# 2024 Linux 核心設計 春季班 自我評量
## 成果發表和貢獻
評分與內容同[期末專題](./164253/#期末專題)。
## 作業/隨堂測驗
* lab0-c: [GitHub](https://github.com/164253/lab0-c) / [HackMD](https://hackmd.io/@164253/linux2024-homework1)
* Homework 2 (quiz 1 + 2): [HackMD](https://hackmd.io/@164253/linux2024-homework2)
* Homework 5 (assessment): [HackMD](https://hackmd.io/@164253/linux2024-homework5)
評分:
9 分，我這次在作業與測驗中學到非常多東西，包括間接指標、 linux 中的排程器設計、環狀 linked list 、各類 bitwise 操作、檢查是否越界存取記憶體、檢查時間複雜度是不是常數等。
其中 $O(1)$ 排程器中用 queue 陣列做出的 priority array 特別讓我印象深刻，考量優先級數量不多，在各類資料結構中做取捨，體現應用時應該根據常見的情況決定設計。
而在實作 lab0-c 的過程中，用到諸如 makefile, github CI 等打競賽不會使用的工具，也發現許多優化和演算法的理論複雜度不代表實際結果，例如快慢指針在 linked list 上反而會造成過多次記憶體存取，且在較小的快取中效果不佳等。同時也訓練了看規格書等原始資料，避免讀到錯誤資訊的能力。
作業 2 和作業 5 中，則讓我順便複習多個高中時正好研究過的問題，包含 leetcode 上比較有意思的幾道題，還有預處理除法優化，也就是競賽常用的 barrett reduction 等。
## 期末專題
* 強化 Linux 核心的測試模組:
* 強化 Linux 核心的測試模組: [hackmd](https://hackmd.io/@sysprog/ByvfKXXPC)
評分:
7分，提交內容仍在測試中，所以還沒有提交紀錄，也尚未收錄。
第一筆是補充 `lib/test_sort.c` 中沒有測試排序的穩定性，以及改用最差解而不是隨機的平均測資。
第二筆則是把 rbtree 線索化，可以 $O(1)$ 找到前後一個節點，再之後可以視情況加入 morris traversal 。
待這兩筆做完後，要繼續尋找其他可以修改的測試，以及能加強的資料結構。
在編譯測試的時候遇到許多問題，像是看不懂 makefile 、不會掛載模組等，學習了各類實作時才會遇見的問題。
對其他同學的期末專題 review:
在 [Linux 核心專題: 全向量視窗系統實作](https://hackmd.io/@sysprog/B13GqdgQ0) 中提出可以比照 FPU 的方式對 $\sin,\cos$ 打表，減少部分運算次數。
在 [Linux 核心專題: 針對鏈結串列的資料排序改進](https://hackmd.io/@sysprog/ryr7zfh4R) 中提出或許能透過 run 的數量選擇使用 Timsort 或其他排序方式，但具體的切換條件及實際效益需經過更多測試。
在 [Linux 核心專題: 重作第四次作業](https://hackmd.io/@sysprog/r1WImnwIC) 中指出可以使用 barrett reduction 對除法和取餘簡化為位元運算的方式，且不須像原本開發紀錄中對特定小數的值逼近。
在 [Linux 核心專題: 改進 ksort](https://hackmd.io/@sysprog/BkqsnDc8R) 基於出現次數多的數在排序中可以一併處理，提出引入摩爾投票法尋找眾數以快速減小待排序數的數量。
## 與授課教師的互動
* 2024/06/10, 10:30: 一對一討論
* 2024/03/19: [課堂問答](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ)
評分:
8分，一對一討論時確認了期末專案的進度，老師提到作業主要是讓大家熟悉基本知識和閱讀大量程式的能力，目標仍然以貢獻 linux kernel 為主。
以及許多人學過基本科目，卻在考試過後全部忘光的現象，也正好老師問的基本科目如機率與統計、資料結構、演算法等我仍是大一還沒上到，到時候可以回來找教材尋找可以應用的情況。
3/19 的課堂問答中，發現了 merge sort 的最差情況並不是完全相反，相反甚至是最佳情況之一，以及如何構造最差情況的問題，可惜最差情況的數量寫不出數學式。
## 所見所聞所感
評分:
10分，閱讀〈因為自動飲料機而延畢的那一年〉，發現許多事情並不如我預想中的美好，學校所教的理論和應用相距太過遙遠，不親身投入很容易誤以為自己已經學會，而現實生活則更是講究正確性與快速，有些程式的失誤會造成人身安全的問題，很多問題沒有漂亮的結果和證明過的正解，需要在各種功能取捨間找出效益最大的那種。
而由於我原本是打競賽的，常常有人提出競程無用的論點，經過這次課程才發現許多問題是用的到這些東西的，包含 fhq treap 、 zkw 線段樹、莫隊算法等，只是證明他們有用且比原本的做法更好才是最難的部分，沒有數據實在難以說服人，這次修改 linux kernel 中便深刻的體會到這點。
在這次的課程，還順便發現諸如潮汐現象、檢測越界使用記憶體之類等困擾競賽常用的評測系統的問題都是可以解決的，目前正在和同學一起研究，並加入我們自己做的評測系統中。
## 自我評量 (1 ~ 10)
方案 B: $1+\lfloor\sqrt[5]{7\times9\times7\times8\times10}\rfloor=9$
