# 2024q1 Homework5 (assessment)
contributed by < `yenslife` >
```shell
$ uname -a
Linux lima-default 6.5.0-25-generic #25-Ubuntu SMP PREEMPT_DYNAMIC Wed Feb 7 15:18:19 UTC 2024 aarch64 aarch64 aarch64 GNU/Linux
$ lscpu
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Vendor ID: 0x00
Model name: -
Model: 0
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 0x0
BogoMIPS: 48.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 asimddp sha512 asimdfhm d
it uscat ilrcpc flagm sb paca pacg dcpodp flagm2 frint
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-3
```
## 從 Revolution OS 看作業系統生態變化
> [影片](https://youtu.be/vWwvh3036Fw?si=eC_fmXJmQ4x9iMvR)
## CS:APP 第 2 章教材閱讀
> [教材](https://hackmd.io/@sysprog/CSAPP-ch2)
### 第一部分
> [影片](https://youtu.be/wb2u59QF2iY?si=20eisNzF9-tHEjaD)
#### 基本
Unsigned number：$B2U(X) = \sum_{i=0}^{w-1}{x_i\cdot2^i}$
Signed number (Two's complement)：$B2T(X) = -x_{w-1}\cdot2^{w-1}+\sum_{i=0}^{w-1}{x_i\cdot2^i}$
其中 w 是位數的意思。
$UMAX = 0$ , $UMIN = 2^w-1$
$TMIN = -2^{w-1}$ , $TMAX = 2^{w-1} - 1$
$UMAX = 2 \cdot TMAX - 1$
二補數轉換成十進位：教科書常用將取一補數之後的結果加一的方法來取得二補數，這邊教材提供我一個新理解。二補數的 MSB 是 signed bit，也可以理解成最高為元代表的冪取複數，然後相加，請看以下範例。
在 C 語言中，可以透過 `#include <limit.h>` 來取得最大最小值
Unsigned 和 Signed number 之間的關係，可以發現正數和負數的值都朝同一個方向變大。
| X | $B2U(X)$ | $B2T(X)$ |
| ---- | -------- | -------- |
| 0000 | 0 | 0 |
| 0001 | 1 | 1 |
| 0010 | 2 | 2 |
| 0011 | 3 | 3 |
| 0100 | 4 | 4 |
| 0101 | 5 | 5 |
| 0110 | 6 | 6 |
| 0111 | 7 | 7 |
| 1000 | 8 | -8 |
| 1001 | 9 | -7 |
| 1010 | 10 | -6 |
| 1011 | 11 | -5 |
| 1100 | 12 | -4 |
| 1101 | 13 | -3 |
| 1110 | 14 | -2 |
| 1111 | 15 | -1 |
邏輯位移 (Logical shift) 和算術位移 (Arithmetic shift) 的意義：前者補 0；後者補上 Signed bit。以前只是把算術位移會複製 MSB 的特性背下來，現在知道這麼做是為了維持正負數的性質。算術位移可以應用在判斷正負號上 (`x >> 31` if x is integer)，因為 **gcc 的實作是算術位移**。觀察下圖 MSB 的變化。
若 n 是有號 32-bit 整數
- `n >> 31` 相當於 `n >= 0 ? 0 : -1`
- `abs(n)` 等同於 `((n >> 31) ^ n) - (n >> 31)`
- 當 n 是負數時:
`n >> 31` 是 -1; -1 以 2 補數表示為 `0xFFFFFFFF`; `n ^ (-1)` 等同於 **1 補數運算**; 最後再減 -1，得到 2 補數運算的值
- 如果將 -1 右移，不會得到 0 而是會得到 -1
#### 轉換
負值的有號數轉換成無號數可能會比原本的大，如下圖。
C 語言中，有 "U" 後綴的數值表示 unsigned number
無號數及有號數進行運算時，**有號數會被強制轉型成無號數**
無號數意外結果的例子，會造成無窮迴圈，因為無號數不小於 0
```c
unsigned i;
for (int i = n - 1 ; i - sizeof(char) >= 0; i--)
a[i] += a[i + 1];
```
另一個例子，因為 sizeof 的結果是無號數，導致無窮迴圈
```c
#define DELTA sizeof(int)
int i;
for (i = CNT; i-DLETA >= DELTA; i -= DELTA)
...
```
### 第二部分
> [影片](https://youtu.be/cGjjDea7i8g?si=5eEe-fLKzO0goO5E)
#### 微妙操作
用 xor 來判斷有沒有 overflow (正數加正數的結果為負；負數加複數的結果為正)
```c
long a, b, x;
x = a + b;
if ((x ^ a) >= 0 || (x ^ b) >= 0) // 沒有溢位才能繼續
```
三種可能性
乘以二是 `>>`，除以二是 `<<`，正負號都可以用 (gcc)
- `~x + 1 == -x` ：就是二補數
- `~-x == --x`
- `-~x == ++x`
- `~0 == -1`
- `~0 + 1` == 0
原理如下圖
`-1 < 0U` 為 False，因為有號數被轉型成無號數了
#### Unsigned 迴圈寫法
- 盡可能使用 `size_t`，不論使用的機器是什麼都會自動變成 word size 的 unsigned 類型。
- 使用 `<` 而不是 `>= 0`
- `0 - 1 == UMax`
#### Byte Ordering
記憶體位置由 byte 為單位來排序，需要區分 Big endian, Little endian
#### 動腦時間
規則：回答以下問題，左邊是條件，右邊是要判斷是否 always true？若至少一種條件不為 true 則為 false；如果沒有右邊的部分就直接判斷左邊是否為 always true。考驗自己對 overflow 可能性的判斷
第一題就是當 `x < 0`，`(x*2) < 0` 是否 always true。
`(x | -x) >> 31 == -1` 有一個反例：`x = 0`
### 第三部分
> [錄影](https://youtu.be/cvE39UfP74Q?si=DJ947wukxmmPCcq2)
#### 浮點數
二補數的小數表示方法與「浮點數」是不一樣的。後者利用類似科學記號表示方法。
- 二補數小數：101.11 = 4 + 1 + 0.5 +0.25
為什麼要這樣呢？為了讓能表示的值更多，如果用原本的方法只能表示 $x/2^k$ 種可能。
浮點數標準：IEEE 754
$v = (-1)^sM 2^E$
$E = exp-Bias$
兩種 Special case，當 exponent 為：
- 00000000000 = 0x000 當尾數為 0 時為 ±0，尾數不為0時為非正規形式的浮點數。
- 11111111111 = 0x7ff 當尾數為 0 時為 ∞，尾數不為 0 時為 NaN。
轉換方式
為什麼要減掉 Bias？參考 [stack overflow 上的回答](https://stackoverflow.com/questions/2835278/what-is-a-bias-value-of-floating-point-numbers)
>If you used a twos-complement representation for the exponent, a small positive number (i.e., with a negative exponent) would look like a very large integer because the second MSB would be set. By using a bias representation instead, you don't run into that -- a smaller exponent in the floating point number always looks like a smaller integer.
Denormalize 和 normalized 的 exp 有些微不同 (下圖是 8 bits 的例子)
## 改進測驗題
### 第一週測驗題 timsort
#### 一些提醒自己的注意事項
之所以有 warm up 是為了避免系統誤差
每個 run 的第二個節點的 `prev` 用來記錄 run 的長度，可以用 `run_size` 來取得該節點的長度。
`tp` 用來記錄堆疊的 top
`find_run` 之後，會將每個 run 最後的節點指向 NULL
將 `timsort` 中的 `merge_collapse(priv, cmp, tp);` 註解掉還是可以有已排序的陣列，因為最後會做 `merge_force_collapse` 以及 `merge_final`。
測試結果，有 `merge_collapse` 的比較次數為 9441；沒有 `merge_collapse` 的比較次數可以達到 144759，量級上的差距顯示對每個 run 預先合併有顯著的效果。
### 簡化 merge 程式碼
原本的 merge 在 `for (;;)` 迴圈中用兩個判斷來決定要不要將剩下的節點加到 tail 後面，程式碼過於冗長，其實可以將此條件寫在迴圈判斷式中，增加可讀性。
> commit [b1a3757](https://github.com/yenslife/timsort/commit/b1a3757)
```diff
- for (;;) {
+ while (a && b) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
- if (!a) {
- *tail = b;
- break;
- }
} else {
*tail = b;
tail = &b->next;
b = b->next;
- if (!b) {
- *tail = a;
- break;
- }
}
}
+
+ /* Append the remaining elements */
+ *tail = a ? a : b;
+
return head;
}
```
### 設定 minrun 並使用二分插入法 (binary insertion)
Timesort 希望最後的 run 數量可以是「2 的冪」或「略小於 2 的冪」，這邊參考 [cpython 的說明](https://github.com/python/cpython/blob/main/Objects/listsort.txt)以及[程式碼](https://github.com/python/cpython/blob/main/Objects/listobject.c)，找到 `merge_compute_minrun`，會發現 Python 直譯器尋找 minrun 也用了 bitwise 的技巧。這邊 `MAX_MINRUN` 為 64，因為 Tim 經過實驗發現資料數量為 64 時使用 insertion sort 的效率很好。若是資料數量 n 小於 `MAX_MINRUN` 則直接使用 n，因為資料太小了影響可忽略；如果大於 `MAX_MINRUN`，就在 `(MAX_MINRUN / 2, MAX_MINRUN + 1)` 的範圍內選擇 minrun，這樣即使 run 數量不是二的冪，也會接近二的冪。
```c=2648
merge_compute_minrun(Py_ssize_t n)
{
Py_ssize_t r = 0; /* becomes 1 if any 1 bits are shifted off */
assert(n >= 0);
while (n >= MAX_MINRUN) {
r |= n & 1;
n >>= 1;
}
return n + r;
}
```
測驗題中沒有控制 minrun 的數量，也就沒有實作二分插入法，因為每一個 run 的數量都太小了。
二分插入法就是將已排序資料對半切，檢查待插入節點的值屬於左半邊還是右半邊。
實作兩個函式，`size_t merge_compute_munrun(size_t len)` 和 `binary_insertion()`
```c
list_for_each (pos, head) // 先在 timsort 中利用 list API 找出資料長度
len++;
size_t minrun = merge_compute_minrun(len); // 計算 minrun
```
在 `find_run` 中添加 `minrun` 選項，如果有長度不足的 run，就用二分插入法來將後續的節點加入 run
### Galloping mode
Timsort 會使用 Galloping mode 來改進對部分排序的資料的排序，但測驗題的程式碼沒有實作這一塊。
### 效能評估
參考 [cpython](https://github.com/python/cpython/blob/main/Objects/listsort.txt) 使用的資料
## 紀錄閱讀 〈Demystifying the Linux CPU Scheduler〉的啟發以及問題
### Chapter 1
在 Linux 中最小的排程單位是 thread 而不是 process，thread 的 ID 叫做 PID (process identifier)，超怪的，process 的 id 叫做 TGID (thread group identifier)。如果 process 只有一個 thread 那該 process 的 PID 等於 TGID
> 注意 [Tuning scheduling policy](https://access.redhat.com/documentation/zh-tw/red_hat_enterprise_linux/8/html/monitoring_and_managing_system_status_and_performance/tuning-scheduling-policy_monitoring-and-managing-system-status-and-performance) 提到: "because the scheduler’s primary concern is to keep the system busy, it may not schedule threads optimally for application performance." 實際排程不會以執行緒作為單一考量來排程，例如 NUMA 就涉及到行程間對處理器節點的關聯。 :notes: jserv
Thread 和 Process 最大的差異在於：thread 之間共享 address space；process 則無，其他都一樣。在 Linux 中則以 "task" (`task_struct`) 來稱呼他們。
之所以在 `task_struct` 中有 `volatile` 是為了抑制編譯器最佳化，以確保每次都會有一個 load。
Linux 中使用 hash table 來紀錄 PID，就是測驗題提過的 `hlist_head`，所以在 `kill [PID]` 才會那麼快 $O(1)$。
`#define offsetof(TYPE, MEMBER) ((size_t) & ((TYPE *)0)->MEMBER)` 再次提醒把 0 轉換成 pointer 的技巧很好用
`TASK_RUNNING` 表示 runnable (ready but not running) 或是正在 running
17 頁的 `tast_struct` 2 ~ 7 行的註解和成員程式碼是不是寫錯了？參考新版 `v6.9rc7`。
```c=2
struct task_struct {
/* -1 unrunnable, 0 runnable, >0 stopped: */
volatile long state;
void *stack;
/* Current CPU: */
unsigned int cpu;
```
### Chapter 2
2.1.1
Fairness: 同優先權的行程被分配到差不多的 CPU time，任意優先權的行程都會被分配到時間
Starvation: 一直沒有被分配到 CPU time 的行程的狀態 [有趣的笑話](https://www.c-sharpcorner.com/blogs/omg-rumor-about-priority-scheduling1)
書中 34 頁提到
> An operating system’s liveness property cannot be broken in a finite execution since the “good” event might still happen at a later time.
這邊的 "good" event 指的是高優先權的行程嗎？good 是哪方面 good？
2.1.2
Linux 不把排程策略寫死，而是讓每個行程都有自己的排程策略類別。
為什麼引用這段[原文](https://lwn.net/Articles/230501/)要把開頭的 the introduction of Scheduling Classes: 改成中括號？
>[. . . Scheduling classes is] an extensible hierarchy of scheduler mod- ules. These modules encapsulate scheduling policy details and are handled by the scheduler core without the core code assuming too much about them.
>
在 symmetric multiprocessing 中，所有 processor 都平等，沒有主從之分，stop class 只會發生在這類系統；asymmetric multiprocessing 則有一個主要的 processor 來控制其他 processor
我不太懂為什麼 stop class 的排程類別會將該 CPU 的行程遷移到其他 CPU，又為什麼需要讓其他 CPU 多一個 kernel thread？
scheduling class 和 scheduling policies 的差異在於，前者用來區分優先權，後者則是排程的方法
nice 值越高 (19)，表示優先權越低；反之，nice 值越低 (-20) 則優先權越高，那為什麼他不要叫做 bad 值？我只是覺得有點不直覺。範圍之所以在 -20 ~ 19 是因為記憶體大小考量嗎？
2.2.1
最早的 CPU scheduler 十分簡單，沒有考慮到多核的環境。有 timeslice，以相反方向走訪 runqueue，根據 timeslice 大小、狀態 (sleep/runnable/nil) 來決定誰會先被執行。當所有在 runqueue 中 runnable task 的 timeslice 都為 0，將 task 加上一半的 timeslice + priority。從這裡開始 `TASK_RUNNING` 表示的就不是「正在執行」，而是「可以被執行/準備好被執行」，`NR_TASK` 為最大 task 數量。
44 頁的程式碼與[原始碼](https://kernel.googlesource.com/pub/scm/linux/kernel/git/nico/archive/+/refs/tags/v0.01/kernel/sched.c)有些微的不同，不知道是不是老師有意為之？
現在的 task_struct 中沒有 counter 成員了
2.2.2
$O(n)$ scheduler
用 Linked list 來紀錄 tasks，每個 task 有一個 goodness score，這個分數是根據，這個分數是根據像是 nice 值或是 timeslice 來決定。
$O(n)$ scheduler 引進了 epoch 的概念，當所有 task 的 timeslice 都被用完了(還是被用過了？)，則表示這次 epoch 結束了。若還有剩下的 timeslice，就把這剩下的 timeslice / 2 加到該 task 的新 timeslice
流程：
```mermaid
graph LR
n1(開始一個 epoch)-->n2(迭代所有 task)-->n3(計算 good score)-->n4(找出最 good 的 task 當作下一個要 run 的 task)
```
> Not to be confused with “niceness”, which is a measure of a task’s courtesy to other tasks in the system: a task with high niceness (i.e., running at a low priority) is more generous to the system’s users, whereas a less “nice” task demands more CPU resources. See Section 2.1.2 for more details
這一段註解解答了我對 "nice value" 的疑問，nice 指的是中文的「友善」，當一個 task 不佔用 CPU，表示他越「友善」。具有高「niceness」的任務運行在低優先級，對系統的其他使用者更慷慨，因為它們不急於佔用 CPU 資源，很友善。nice 高 -> priority 低；nice 低 -> priority 高。先前我錯把 nice 理解成 priority 了。
#### goodness
goddness 函式引入 List API 相關程式碼，用來計算 niceness。他會先檢查傳入的 task 使用什麼 policy，如果是 Non-real time 就直接把該 task 的 counter 當作 weight；如果不是，則先檢查 CPU，若該 task 跑在同一個 cpu 上，則讓他的優先程度增加，給這樣的任務更高的優勢。如果是在跑在同一個 address space (struct_mm)，也給他一些優勢。若該任務是 read time 的，就給他超大的權重 (1000 + real time priority)，這邊用 1000 這個數字做為分隔：-1000 表示永遠不會執行到；1000 表示 real time 的任務。
之所以叫做 $O(n)$ 就是因為這個 list_for_each。
2.2.3 $O(1)$ scheduler
在多核的環境中，scheduler 最大的挑戰就是如何在 cpu affinity 和 load balance 之間取得平衡，我們不希望有 CPU 閒置，但又要考慮到任務轉換會有 cache miss 的問題。
使用一個 global priority queue 來記錄不同優先級的 runqueue，長度為 `MAX_PRIO`(140)，還有一個 bitmap 來紀錄每一個 priority 的 queue 有沒有 task，如果沒有就是 0，如果有就是 1。
之所以叫 $O(1)$ 就是因為這個 bitmap，查找的時間不是根據 task 的數量，而是 priority 的數量 (140)
## 紀錄閱讀〈[因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1)〉的啟發
### 閱讀紀錄
八集
> 一項產業進步的速度，很大程度取決於做實驗修正問題的速度。
也太有感，但我有時候也會太依賴這樣執行速度快的特性就沒有來由地 debug 欺騙自己，讓自己覺得很有生產力。以前沒有寫過系統軟體，直到修了一堂 Linux 的 Coursera 課程，我記得是要用 Buildroot 使用系統呼叫來完成作業內容，不知道原來編譯整個 kernel 這麼花時間，所以更小心對待每次寫下的程式碼。
當然，和機械領域花的時間還是不能比的。
十一集
> 如果問題過於困難無法解決，那就重新定義問題吧！
十二集
> 你最大的問題在太害怕失敗了
>
> 青春很貴，你也知道實習會發生什麼事，公司不會指派重要的工作給你，他們只會指派低風險的工作，你學習到的東西並不會比你現在多。你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。
實習真的那麼糟嗎？不知道，因為我才大三而已，看到學校有很多關於創業、新創的比賽活動 (甚至還有專門的單位在推動創業...?)，我就在想：那些比賽的冠軍最後真的都創業了嗎？我信你個鬼，還不是當當賞金獵人而已，真的那麼簡單的話我也想創業啊。
有些東西還是買現成的就好，就像嘗試實作與加密相關的後端功能，到最後會發現，還是用現有的軟體包 (package) 更安全，密碼學太難了，更不用說物理世界的機械結構，像是掉冰機。
看到飲料機的軟體介面的時候發現，這不就是 POS 機嗎？只是學長做的是結合自動做飲料的 POS 機
十八集
> 事情如果太順利代表絕對有問題，而問題永遠會從意想不到的地方冒出來。
十九集
> 我們道了謝後離開，從來不知道老爸那麼罩。
我也是大學之後才跟自己的爸爸有比較深度的交流，才知道原來他以前做過那麼多事，經驗量遠遠超過我的想像，因為他工作不常在家的關係，以前和他很不熟。我覺得在台灣有一段時間，差不多就是我爸媽那個年紀區段的人 (四十幾五十幾)，這些人其實都有很多故事可以分享，有的甚至是隱藏版的大佬。
二十二集
> 「這些學校上課、教授不會教啊。我以前也是焊得很爛，能動就好。」紘銘說：「後來有次我進實驗室做實驗，實驗室的大學長看不下去，花了一個多小時教我這些技巧。這些基本到不行、看起來不難的東西，動手做之後才會發現很多細節要注意。」
其實我覺得上 Linux 核心設計/實作的感覺就像是有一個大學長在帶領我們「實作」程式碼，補足過去自以為懂的東西，事實上老師也是大學長沒錯，和教授不同的地方是，他們不一定會自己動手做，畢竟那種東西交給研究生就好，對吧？
二十三集
> 這個世界比任何人都殘酷，也比任何人都公平，犧牲了多少就會得到多少
當我高中把時間花在社團以及無謂的交際上時，有人已經自己手刻一個作業系統了，那些特殊選才的同學不是他們有多聰明 (就算有又怎樣？)，而是他們花了額外的時間、無數的夜晚，追求自己所渴求的知識，並將他們實作出來，所以不用去羨慕他們，應該要思考自己的時間要花在哪些真正重要的事物，才能問心無愧。
### 修課心得
其實我在大一的時候就聽過特殊選才的室友同學討論過這堂課，那時候覺得很新奇，也想修修看，但礙於成績考量，以及「害怕失敗」的心態，一直都沒有投入這堂課，害怕花了不必要的時間，那時候都覺得花時間在成績以外的事情是不值得的，現在回過頭來看真是愚蠢。資訊產業除了成績更看重自己的實力，實力這種東西是一問便知的，連成績單都不用看，那些真的只是數字而已。
真不愧是成大資訊工程系最硬的課，前六週的作業以及教材的預先閱讀量真的會讓人退避三舍 (或者我該說退選)，但只要撐過去就可以了。我自認是沒有撐過去的人，因為我的投入量比課程預期的還要少很多，但還是學到很多很多。從 `git rebase -i` 到一些系統軟體的工具使用，還有從來沒有弄懂過的 C 語言，更重要的是看待軟體開發的心態，從怪罪前人留下的程式碼，只知道挑惕卻沒有想過背後的原因；到怪罪認知不足的自己，在人類智慧的結晶之前還如此狂妄自大。
還有一個很值得帶走的能力，那就是寫作能力，過去的自己對「筆記」的概念比較像是自己看得懂就好 (殊不知未來的自己也看不懂，程式碼亦然)，現在我會更想要用簡潔的語句來傳達最大量的資訊，讓所有人的看得懂我寫的文章，還有 Git commit message。我在這堂課寫作時對細節的要求甚至比大在學修國文課還多 (就可以知道我有多混)，我從沒想過用 ChatGPT 寫英文 commit message 這麼好用，雖然在發 [PR](https://github.com/sysprog21/lab0-c/pull/177) 的時候還是不停被 Jserv 老師提點 commit message 需要改進，我也覺得一直都有改進的空間。
另外就是對規格書的重視，以往寫程式為了應付作業要求，幾乎可以使用 Google 搜尋或者 ChatGPT 來找到答案，希望尋求「速成」的路徑，但現在我們做的事情很難再用應付其他資訊系作業的態度來處理了。試想當自己做的事情我國小的表妹也做得到，那還可以帶來什麼價值？這個習慣我也帶到資訊專題，在開發平台前後端以及串接 LLM 的功能，以前可能只是看看網路上的教學文章或是 Youtube tutorial，但觀察像是 [FastAPI 的官網](https://fastapi.tiangolo.com/)，其實他們都會提供很多現成的範例。我也開始閱讀使用到的開源軟體包的程式碼，比起直接使用它們，理解後再使用它們，體驗 [Aha moment](https://en.wikipedia.org/wiki/Eureka_effect)，那個感覺是更爽了。我第一次有稍微認真 (和過去的自己比較) 去觀察[大型開源 Python 專案](https://github.com/lm-sys/FastChat)，除了自己可以把裡頭某些函式「偷」出來用以外，也發現有太多[鋩角](https://sutian.moe.edu.tw/zh-hant/su/11519/)和知識點了，這時候 Jserv 老師常用的一些 git 技巧就可以派上用場，像是用 `git blame` 觀察檔案的紀錄，找出重要的 commit (所以 commit message 才很重要)，觀察這些開源大佬們的討論過程來學習。由於 Python 也是程式語言，我覺得也應該要用這堂課對待 C 語言的態度去學習它，而不是自以為學了一些語法糖就覺得懂了。推薦這個[頻道](https://youtu.be/igB-hkESMeI?si=pi8dJuN8Twhlk3Z5)，作者教了很多從語言到 Byte code 之間的知識，當然可以閱讀規格書更好，但有個人帶何樂而不為？
還有我覺得「產出」很重要，過去會覺得產出是一件門檻極高的事情，但這堂課的所有共筆作業以及教學資源都可以即時修改，如果害怕浪費時間在「閱讀第一手材料」，那就把反思以及感想記錄下來，這也是一種低成本的產出。將知識用自己的話再說一遍，並讓其他人能夠懂，除了體貼以外，這也是[費曼學習法](https://www.yottau.com.tw/article/460)的一種實作。以前會說：「我花了很多時間在學習」，與其用沒有說服力的方式來闡述自己的投入，不如直接產出些什麼東西讓世界看到。
最後就是基礎素養，這些才是真實世界期待你所擁有的，也是除了學歷以外能夠與其他人拉開距離的東西。
#### 基礎素養
1. C 語言：從來沒有真正理解過
2. 閱讀第一手材料：回到源頭思考，因為現在搬運的成本太低了
3. 好奇心：人云亦云、機械化的學習遲早會被 AI 取代
4. 動手：不只是閱讀、宣稱自己有花時間，而是真正將程式碼運行在自己的電腦上
我覺得最可惜的是，我對時間的控管以及自身能力的評估實在太自負了，以為大三下必修課比較少，時間就都掌握在自己的手上，但忘了有專題、其他選修課以及很多很重要但我忘記也要花時間去經營與人生意義有關的事物上。我忘記人除了時間有限，一天的注意力也是有限的，就像作業系統需要 scheduler 來管理 process，而不是永遠都無腦用 FIFO 或是 Round-robin，不是把事情放到 TODOs 他們就會自己完成，現實世界是很複雜的，要考慮到自身的規格以及心理狀態 (人類的原始缺陷)。一直都覺得時間不夠用，卻沒有想過可能我對自己人生的排程根本上就出了一些問題。千金難買早知道，與其現在自怨自艾當初因害怕退選紀錄不好看而錯過了課程，不如現在開始學。
因為
> 今天不學，明天只會更難
## 簡述想投入的專案
我還需要與老師一對一討論才能確定適合自己的專案，目前感興趣的有以下
### Linux 排程器研究
探討 Linux 排程器內部設計，改進《Demystifying the Linux CPU Scheduler》，並尋求貢獻程式碼到 Linux 核心的機會。
這應該是我最感興趣的了，上學期修作業系統的時候就覺得很有趣，張老師在教學的過程中也有一直強調「現實沒有這麼簡單」，到底是多不簡單？現在有一個研究的機會就擺在眼前。<s>不過還是會害怕能力不足拖大家後腿</s> 。
### 作業及測驗題改進
之前的作業我並沒有特別去改進，頂多實作一部分，有的甚至沒有做完，如果可以在期末前把他們做得精緻也是一件不錯的事
還有在 lab0-c 中，我對我提交的 [PR (檢測是否為穩定排序)](https://github.com/sysprog21/lab0-c/pull/177) 並不是很滿意，覺得還可以用雜湊表 (或許可以嘗試 Linux 核心的 `hlist` ?) 來實作檢查功能，如此一來不需要改道 `queue.h` 也可以對每個節點標記位置，但也只停留在[構想](https://github.com/sysprog21/lab0-c/pull/177#discussion_r1539960040)階段。
### 學習資源翻譯及校訂
[2023 期末專題](https://hackmd.io/@sysprog/linux2023-projects)中提及的教材 〈每位程式開發者都該有的記憶體知識〉和《Concurrency Primer》都是開源的，我想也可以趁機會練習英文讀寫 (看看我被噹的 commit message)，並在閱讀的過程中學習。
### 其他
與老師一對一討論後，如果老師覺得有更適合我的專案，我會更傾向投入老師推薦的專案，畢竟老馬識途，而且我對 [2023 期末專題](https://hackmd.io/@sysprog/linux2023-projects)中專案的認知實在都太少了。
## 教材閱讀〈並行程式設計: Atomics 操作〉
在背後作祟的 cacheline 章節中有一段提到 `cacheline.c` 這段程式碼，我將 `#pragma pack(1)` 註解掉之後就沒有出現非預期的現象，final 只會出現 `FFFFFFFFFFFFFFFF` 或是 `0000000000000000`，我開始思考為什麼 v 表示跨越 2 個 cacheline？
```c
#pragma pack(1)
struct data {
int32_t pad[15];
int64_t v;
};
```
懂了，因為 `int32_t pad[15]` 最後剛好是 32，而 v 的型態是 `int64_t`
---
為什麼 C 語言不給改任何一個 bit?
computer architecture,
word => 32-bit, 64-bit, 128-bit
data bus 的存取單元
CPU <--> bus <--> memory
efficiency
tradeoff
byte 是 word 的一部分，在 C 語言的操作，是 byte-addressed (~1970)
(早期的電腦是 word-addressed)
alignment
float, double ==> 誤差
## 期末專案
到六月底之前要把第一章第二章全部看完 + 有貢獻 (一定要細讀，能作出貢獻，比照**新版程式碼**)，這邊的看完包含紀錄問題、與老師討論。發現有誤解的地方，改進表達。第三章第四章也要看，最好是可以和老師討論。確保 6 月底之前有東西可以拿出來。需要做貢獻的時候就需要討論。盡可能**把所有問題提出來**。
- [ ] 思考 TASK_RUNNING 表示 runnable 或是正在 running 的原因
Sign in with Wallet
Connect another wallet