# 2024q1 Homework5 (assessment)
contributed by < [`padaray`](https://github.com/padaray) >

## 閱讀〈[因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1/)〉的啟發

> 想要研發一隻好寫的原子筆，需要多少成本？
如果你只會寫程式，而且對原子筆一竅不通，那會發生什麼悲劇就可想而知了

作者前期就提到了我認為很重要的觀念，如果你只會寫程式，對其他事情一竅不通所帶來的後果，更何況大部分的情況下是連程式都寫不好。大型專案的開發所要求的不只是程式設計，還需要透過和別的專業的合作，來完成所有的需求，所以作者後來邀請了機械系的同學，共同開發自動飲料機。

> 經過幾次討論後，為了能在有限的時間和成本下如期完成，我們砍掉大多數的規格，只保留三個最重要的功能。我們要做一台能夠自動加茶、加糖、加冰塊的機器，其餘的封模、珍珠、履帶，通通都不必要，以最小可行產品為優先。

如同作者一樣，尚未開始實作時，總會有些天馬行空的想法，隨著開發的進程，才會發現當初構想的缺陷，最後透過一步步的妥協來完成。但作者是在有做事前調查的情況下也如此，所以我們平常更該注意到自己是否眼高手低，選擇了與自己實力不相符的專案。

> 工件加工的時間實在是太長了，我決定發揮想像力，試圖用土砲的方式加速整個實驗流程，不然按照目前設計的修正速度，絕對無法如期完工。我請愷宏重新繪製不同size冰斗的設計圖，但這次不是送到鐵工廠加工，而是改用木頭來做。比起加工鋼鐵，加工木頭是較為容易的事情。

遇到問題不一定要選擇解決它，繞過問題本身也是一個解決方法，有時開發上遇到無法解決的問題，經常鑽牛角尖許久，但解決的方式通常會是嘗試別種方法來避免此問題的發生。

> 為什麼分配冰塊這麼難，我寫程式寫了三年，沒想到卻栽在這個小小的冰塊上啊

作者花了好幾章的篇幅來描述放入指定量冰塊所遇到的困難。作者在最開始時，絕對想不到開發遇到的大難題是放冰塊，如同我們無法預期會在哪裡遇到困難，以前我認為熱情是走下去的根本，隨著開發的專案難度越來越高，我才知道不怕遇到困難才能走得長久，畢竟熱情是會隨著困境慢慢消磨殆盡。

> 事情如果太順利代表絕對有問題，而問題永遠會從意想不到的地方冒出來。
這一連串的問題都是可能的變因，第一眼看到時會覺得頭腦超級混亂，但現實世界就是這麼一回事，解決問題的唯一方法就是冷靜下來分析，做實驗把變因排除掉。

如果問題的可能原因很多，那就先冷靜分析，把問題一一條列解決。

看完文章我心理浮現的第一個想法是，如果是我一定辦不到。可能是在愷宏離開，或是冰塊難題，又甚至最一開始的落杯，我都有可能中途棄賽，但這一次次的難關作者都一一解決，更難得的是文章中完全沒有透露出想放棄的念頭，未來如果有放棄的念頭，我會試著回想這篇文章，讓我有繼續下去的動力。

### 課堂感想
經過這幾周的 Linux 核心實作，我發現不懂和要懂的東西太多。剛進入研究所時，我進入達克效應的愚昧之巔，覺得自己能跨考進來，肯定是有甚麼過人之處，但隨著修的課堂越來越多，我才發現我的過人之處只有考運，別人四年的紮實基礎以及吸收速度讓我望塵莫及，尤其在觀看 vax-r 所撰寫的文件後，那種永遠追不上的無力感讓人絕望。

隨著課程的進展，我慢慢找到屬於自己的步調，雖然作業寫得不是很好，也無法完成所有的作業要求，但我還是有學到東西，並且找到堅持下去的動力，就算追不上別人，也可以將別人看做目標，持續往那個方向前進。

Linux 核心實作是一門非常精實的課，每份課程教材都讓人收穫許多，也訓練了我靜下心來看文件的能力，以前的我只會看個大概就決定直接開發，天真的以為「做中學」才是最快的學習方式，但忽略了前人的經驗分享，碰壁後才發現是別人早已遇過的問題。透過觀摩別人的程式碼，我也了解到自己的不足，不管是考慮的周延程度，或是程式碼的精簡程度，都是我需要努力的地方。最後希望我能持續堅持下去，完成 final project 順利修完這門課。

## 研讀課程教材和 CS:APP 3/e
### 研讀課程教材
**1. [並行程式設計：排程器原理](https://hackmd.io/@sysprog/concurrency-sched)**
其中主要著重在 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 的講解，我對於 coroutine 的理解是一種**主動讓出** cpu 的技術，以此來達到在不同任務間切換，與傳統的 preemptive 有所不同。

coroutine 有兩種實作方式，**stackful** 和 **stackless**。
**stackful** : 每個 routine 可以直接切換 subroutine 相當靈活，缺點是需要配置一定大小的 stack，如果切換多個 subroutine 配置的記憶體空間會很大
**stackless** :
需要用 `suspend` 和 `resume` 手動進行任務的切換，優點是 context switch 上會更有效率，因為只需要保存少量資料，讓 hit rate 變高，
:::info
比起 preemptive 這種 OS 主動切換的機制，coroutine 在 context switch 只需保存少量資訊，也不會有 deadlock 問題
coroutine 真的那麼強大的話，一般 preemptive 還有存在的必要性嗎? 又或是應用場景不同
:::

**2. [Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)**
> 在樹高性質上，AVL tree 和 rbtree 雖然都是 𝑂 (log ⁡𝑛) ，但 AVL 在樹高上較緊致，約 1.44 × log ⁡(𝑛+2) ，而 rbtree 則為 2 × log ⁡(𝑛+1) 。

AVL tree 定義 : 對於每一個節點，左子樹和右子樹的高度差必須在正負 1 之間，若違反則透過旋轉 (LL、RR、LR、RL) 來平衡

:::info
其中提到在樹高的 1.44 和 2 這兩個數字是從何而來
1.44 從 N(n) = N(n-1) + N(n-2) + 1 公式推導而來(但沒看懂[影片](https://www.youtube.com/watch?v=iMr4HbLDf2k))
:::

### CS:APP 3/e
2.1.1 十六進制表示法
- 表示法：0xFA1D37B or 0XFA1D37B (英文大小寫都可)
- 十六進制轉二進制，就是將十六進制表示成 4 個 bit 的二進制
- 當數字為 $2^n$，將 n = i + 4j 其中 i 為 小於 4 的數字，即可快速轉換成十六進制。例：n = 11 = 3 + 4x2，j 為多少，代表十六進制有幾個 0 ，i 則直接轉換成十六進制。範例：$2^{11}$ = 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 |

舉例：
11110**000** 10**011111** 10**001101** 10**001110**
前方的 11110 代表這是一個 4 bytes 的 UTF-8 編碼，
所以實際上的 code point 是 0 0001 1111 0011 0100 1110， 對應到 U+01F34E
:::info
前方的 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 代表 $-2^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](https://github.com/sysprog21/vwifi) 虛擬無線網路裝置驅動程式和實驗環境

vwifi 是用 cfg80211 框架的 500 行的 WiFi 裝置驅動程式，2022 年的開發是實作 AP 和 STA mode，以及模擬 RSSI 訊號強度。2023 年實作 STA 的網路測試環境、將 vwifi 的說明提交到 LKMPG...等。

</br>

### [打造 Linux 虛擬攝影機裝置驅動程式](https://hackmd.io/@sysprog/linux2023-projects#%E6%89%93%E9%80%A0-Linux-%E8%99%9B%E6%93%AC%E6%94%9D%E5%BD%B1%E6%A9%9F%E8%A3%9D%E7%BD%AE%E9%A9%85%E5%8B%95%E7%A8%8B%E5%BC%8F) - [vcam](https://github.com/sysprog21/vcam)
vcam 是個輕量的虛擬攝影機，總程式碼約 1500 行。希望透過這個專案來熟悉 Linux kernel 和 module 間的關係，並且有機會擴充其功能。了解 V4L2 這個 interface 熟悉操作。

</br>

### 完成 [M03:TicTacToe](https://github.com/jserv/ttt) 作業
在作業三中，需要完成 tic-tac-toe 的實作，我沒有完成[作業要求](https://hackmd.io/@sysprog/linux2024-ttt)。
實作對弈演算法，以及在電腦 vs 電腦參照[<並行程式設計：排程器原理>](https://hackmd.io/@sysprog/concurrency-sched)引入 coroutine

---

TODO: vcam => Linux v6.8+ (Ubuntu Linux 24.04 搭配的核心版本)