HackMD
2024q1 Homework5 (assessment)
contributed by < padaray >
閱讀〈因為自動飲料機而延畢的那一年〉的啟發
想要研發一隻好寫的原子筆，需要多少成本？
如果你只會寫程式，而且對原子筆一竅不通，那會發生什麼悲劇就可想而知了
作者前期就提到了我認為很重要的觀念，如果你只會寫程式，對其他事情一竅不通所帶來的後果，更何況大部分的情況下是連程式都寫不好。大型專案的開發所要求的不只是程式設計，還需要透過和別的專業的合作，來完成所有的需求，所以作者後來邀請了機械系的同學，共同開發自動飲料機。
經過幾次討論後，為了能在有限的時間和成本下如期完成，我們砍掉大多數的規格，只保留三個最重要的功能。我們要做一台能夠自動加茶、加糖、加冰塊的機器，其餘的封模、珍珠、履帶，通通都不必要，以最小可行產品為優先。
如同作者一樣，尚未開始實作時，總會有些天馬行空的想法，隨著開發的進程，才會發現當初構想的缺陷，最後透過一步步的妥協來完成。但作者是在有做事前調查的情況下也如此，所以我們平常更該注意到自己是否眼高手低，選擇了與自己實力不相符的專案。
工件加工的時間實在是太長了，我決定發揮想像力，試圖用土砲的方式加速整個實驗流程，不然按照目前設計的修正速度，絕對無法如期完工。我請愷宏重新繪製不同size冰斗的設計圖，但這次不是送到鐵工廠加工，而是改用木頭來做。比起加工鋼鐵，加工木頭是較為容易的事情。
遇到問題不一定要選擇解決它，繞過問題本身也是一個解決方法，有時開發上遇到無法解決的問題，經常鑽牛角尖許久，但解決的方式通常會是嘗試別種方法來避免此問題的發生。
為什麼分配冰塊這麼難，我寫程式寫了三年，沒想到卻栽在這個小小的冰塊上啊
作者花了好幾章的篇幅來描述放入指定量冰塊所遇到的困難。作者在最開始時，絕對想不到開發遇到的大難題是放冰塊，如同我們無法預期會在哪裡遇到困難，以前我認為熱情是走下去的根本，隨著開發的專案難度越來越高，我才知道不怕遇到困難才能走得長久，畢竟熱情是會隨著困境慢慢消磨殆盡。
事情如果太順利代表絕對有問題，而問題永遠會從意想不到的地方冒出來。
這一連串的問題都是可能的變因，第一眼看到時會覺得頭腦超級混亂，但現實世界就是這麼一回事，解決問題的唯一方法就是冷靜下來分析，做實驗把變因排除掉。
如果問題的可能原因很多，那就先冷靜分析，把問題一一條列解決。
看完文章我心理浮現的第一個想法是，如果是我一定辦不到。可能是在愷宏離開，或是冰塊難題，又甚至最一開始的落杯，我都有可能中途棄賽，但這一次次的難關作者都一一解決，更難得的是文章中完全沒有透露出想放棄的念頭，未來如果有放棄的念頭，我會試著回想這篇文章，讓我有繼續下去的動力。
課堂感想
經過這幾周的 Linux 核心實作，我發現不懂和要懂的東西太多。剛進入研究所時，我進入達克效應的愚昧之巔，覺得自己能跨考進來，肯定是有甚麼過人之處，但隨著修的課堂越來越多，我才發現我的過人之處只有考運，別人四年的紮實基礎以及吸收速度讓我望塵莫及，尤其在觀看 vax-r 所撰寫的文件後，那種永遠追不上的無力感讓人絕望。
隨著課程的進展，我慢慢找到屬於自己的步調，雖然作業寫得不是很好，也無法完成所有的作業要求，但我還是有學到東西，並且找到堅持下去的動力，就算追不上別人，也可以將別人看做目標，持續往那個方向前進。
Linux 核心實作是一門非常精實的課，每份課程教材都讓人收穫許多，也訓練了我靜下心來看文件的能力，以前的我只會看個大概就決定直接開發，天真的以為「做中學」才是最快的學習方式，但忽略了前人的經驗分享，碰壁後才發現是別人早已遇過的問題。透過觀摩別人的程式碼，我也了解到自己的不足，不管是考慮的周延程度，或是程式碼的精簡程度，都是我需要努力的地方。最後希望我能持續堅持下去，完成 final project 順利修完這門課。
研讀課程教材和 CS:APP 3/e
研讀課程教材
1. 並行程式設計：排程器原理
其中主要著重在 coroutine 的講解，我對於 coroutine 的理解是一種主動讓出 cpu 的技術，以此來達到在不同任務間切換，與傳統的 preemptive 有所不同。
coroutine 有兩種實作方式，stackful 和 stackless。
stackful : 每個 routine 可以直接切換 subroutine 相當靈活，缺點是需要配置一定大小的 stack，如果切換多個 subroutine 配置的記憶體空間會很大
stackless :
需要用 suspend 和 resume 手動進行任務的切換，優點是 context switch 上會更有效率，因為只需要保存少量資料，讓 hit rate 變高，
比起 preemptive 這種 OS 主動切換的機制，coroutine 在 context switch 只需保存少量資訊，也不會有 deadlock 問題
coroutine 真的那麼強大的話，一般 preemptive 還有存在的必要性嗎? 又或是應用場景不同
2. Linux 核心的紅黑樹
在樹高性質上，AVL tree 和 rbtree 雖然都是 𝑂 (log 𝑛) ，但 AVL 在樹高上較緊致，約 1.44 × log (𝑛+2) ，而 rbtree 則為 2 × log (𝑛+1) 。
AVL tree 定義 : 對於每一個節點，左子樹和右子樹的高度差必須在正負 1 之間，若違反則透過旋轉 (LL、RR、LR、RL) 來平衡
其中提到在樹高的 1.44 和 2 這兩個數字是從何而來
1.44 從 N(n) = N(n-1) + N(n-2) + 1 公式推導而來(但沒看懂影片)
CS:APP 3/e
2.1.1 十六進制表示法
- 表示法：0xFA1D37B or 0XFA1D37B (英文大小寫都可)
- 十六進制轉二進制，就是將十六進制表示成 4 個 bit 的二進制
- 當數字為 ，將 n = i + 4j 其中 i 為 小於 4 的數字，即可快速轉換成十六進制。例：n = 11 = 3 + 4x2，j 為多少，代表十六進制有幾個 0 ，i 則直接轉換成十六進制。範例： = 0x800
2.1.2 word size
- 1 個 word 有幾個 bits 組成，是由幾位元的電腦決定，若電腦為 32 位元，1 個 word 就是 32 bit (4 bytes)
- 大部分的 32 位元程式都可以跑在 64 位元的電腦 (向後兼容)
- long 在 32 位元程式是 4 bytes，64 位元是 8 bytes
2.1.3 Byte ordering
- 輸入為 0x01234567，儲存方式如下
Big endian 儲存成(高位元數先存)：
| 記憶體位置 | 儲存內容 |
|---|---|
| 0x100 | 01 |
| 0x101 | 23 |
| 0x102 | 45 |
| 0x103 | 67 |
Little endian 儲存成(低位元數先存)：
| 記憶體位置 | 儲存內容 |
|---|---|
| 0x100 | 67 |
| 0x101 | 45 |
| 0x102 | 23 |
| 0x103 | 01 |
- 大多數情況下使用哪種 endian 沒有影響，但當程式碼需要在不同機器上都能運行時，發送方需要將 internal representation 轉換成 network standard，讓接收方也可以轉換成 internal representation。
- 定義為 unsigned char 的原因，一般 char 型別是帶有符號的，因此若今天將 char(1 byte) 型別放入 int (4 bytes) 中，最高位的 1 在擴增時，會把擴增的位元全部填入 1，如果是 unsigned char 則沒有此問題，避免了轉換的問題
2.1.4 Representing Strings
- 字串終止符為 0x00
- Unicode 的 “Universal Character Set”，是用 32 bits 來表示字符( 0xab )
- 但直接使用 32 bits 又過於浪費資源，因為較小值的 Unicode 一般使用頻率較高，因此發明了 UTF-8 ( 8-bit Unicode Transformation Format )，UTF-8 靈活使用 1~4 個 bytes 來表示 Unicode
- ASCII(7 bits) 則是 Unicode 的子集( U+0000 ~ U+007F )，UTF-8也可以完美兼容
| Character | Code Point | UTF-8 Binary Encoding |
|---|---|---|
| A | U+0041 | 01000001 |
| t | U+0074 | 1110100 |
| 𩵚 | U+29D5A | 11110000 10101001 10110101 10011010 |
UTF-8 實際編碼方式
| bits | Code Point start | Code Point end | Byte1 | Byte2 | Byte3 | Byte4 |
|---|---|---|---|---|---|---|
| 7 | U+0000 | U+007F | 0xxxxxxx | –––– | –––– | –––– |
| 11 | U+0080 | U+07FF | 110xxxxx | 10xxxxxx | –––– | –––– |
| 16 | U+0800 | U+FFFF | 1110xxxx | 10xxxxxx | 10xxxxxx | –––– |
| 21 | U+10000 | U+1FFFFF | 11110xxx | 10xxxxxx | 10xxxxxx | 10xxxxxx |
舉例：
11110000 10011111 10001101 10001110
前方的 11110 代表這是一個 4 bytes 的 UTF-8 編碼，
所以實際上的 code point 是 0 0001 1111 0011 0100 1110， 對應到 U+01F34E
前方的 11110 就代表這是幾 byte，為甚麼在後面的 byte 中需要將前兩個位元設成 10 ?
2.1.7 Bit-Level Operations in C
- 做位元計算時，最好的方式是先表示成二進位，在進行運算
2.1.9 Shift Operations in C
- 算數右移：最高位為 1 時，會補上 1
- 邏輯右移：不管最高位為何，都補上 0
- 大部分的編譯器對有符號數(signed)都用算數右移，無符號數(unsigned)使用邏輯右移
- 左移位數很大(k位)時，若輸入只有w位，會位移 k mod w 位，例：0x12345678 << 32 就不位移， 0x12345678 << 36 位移 4 位
- 移位運算的優先級比一般運算低
2.2.3 Two’s-Complement Encodings
- 2’s-Complement 複習，最高 bit 位 n 代表
- C 語言只指定了每種資料型別的最小範圍，例：signed char 為 -127 ~ 127(但通常為 -128 ~ 127)，為了讓資料型別更加確切，C99 引入了 intN_t 和 uintN_t，N 可代入 8、16、32、64，透過此型別宣告變數，可以得到更精確的型別，增加可移植性
- Two’s Complement 和 Ones’ Complement 逗號位置不一樣
2.2.5 Signed versus Unsigned in C
- 當有符號數和無符號數一起進行運算時，C 語言會把所有數字都看做無符號數
2.2.6 Expanding the Bit Representation of a Number
- 無符號數擴展，直接前面補 0；有符號數擴展，如果為負前面補 1
2.3.1 Unsigned Addition
- 無符號數加法溢位，直接丟棄最高位，讓答案變成 n mod k(n 為相加後數字、k 為無符號數 Max)
- C 語言無符號數溢位不會報錯，因此要確認的話用 x + y < x 判斷
2.3.2 Two’s-Complement Addition
- 2’s Complement 加法溢位如下(右為情況)：
想投入的專案
vwifi 虛擬無線網路裝置驅動程式和實驗環境
vwifi 是用 cfg80211 框架的 500 行的 WiFi 裝置驅動程式，2022 年的開發是實作 AP 和 STA mode，以及模擬 RSSI 訊號強度。2023 年實作 STA 的網路測試環境、將 vwifi 的說明提交到 LKMPG…等。
打造 Linux 虛擬攝影機裝置驅動程式 - vcam
vcam 是個輕量的虛擬攝影機，總程式碼約 1500 行。希望透過這個專案來熟悉 Linux kernel 和 module 間的關係，並且有機會擴充其功能。了解 V4L2 這個 interface 熟悉操作。
完成 M03:TicTacToe 作業
在作業三中，需要完成 tic-tac-toe 的實作，我沒有完成作業要求。
實作對弈演算法，以及在電腦 vs 電腦參照<並行程式設計：排程器原理>引入 coroutine
TODO: vcam => Linux v6.8+ (Ubuntu Linux 24.04 搭配的核心版本)
