# 2024q1 Homework5 (assessment)
contributed by < [`Wufangni`](https://github.com/Wufangni) >
## 閱讀〈因為自動飲料機而延畢的那一年〉
>之所以能夠用那麼低的價格買到日常用品，是因為我們發明了能夠便宜量產的技術，就算加上了運輸和零售成本，一般人也能夠負擔得起。但如果今天你的角色不再是消費者，而是研發者呢？
>想要研發一隻好寫的原子筆，需要多少成本？
>如果你只會寫程式，而且對原子筆一竅不通，那會發生什麼悲劇就可想而知了。
從文章前面這段話可得知在理想情況下認為可達成的結果，往往會因為現實考量產生重重難題，在一個完整的商業化產品製造過程中，牽涉到的不只一個資訊領域，還得經由機械製造、電路設計、材料蒐集、規模評估等多種專業互相配合，環環相扣才能從零到有的製作出一個具有商業化價值的產品。
>然後我發現一個原本以為只有在資工系發生的現象，那就是「資工系的學生不會寫程式，機械系的學生不會做機械」。
在這邊作者提出大部分本科生都缺乏自己領域相關的實作經驗，例如機械系在大學期間幾乎沒有什麼教授機構設計的課程，或是一般資訊系學生可能參與了整個學期的實作課程卻依然不會完整寫出一個網頁或APP，也有少數學生是在學期間就有足夠的能力貢獻open source程式碼，闡述了現代社會嚴重的學用落差現象。
>經過幾次討論後，為了能在有限的時間和成本下如期完成，我們砍掉大多數的規格，只保留三個最重要的功能。我們要做一台能夠自動加茶、加糖、加冰塊的機器，其餘的封模、珍珠、履帶，通通都不必要，以最小可行產品為優先。
隨著具有機械領域知識的新夥伴加入，作者重新對商品設計的可行性進行評估，對於不具急迫性或必需性的功能優先排除，提升整個計畫的實現性。
>硬體設計就是不斷的重複「設計、製造、修正」的循環，想像中的設計會經過有誤差的方式被製造出來，製造出來的產品在現實中運作的效果不如預期，找到問題的根源後再重新修正，機械設計就是重複這樣的循環。只有把東西生出來做實驗，你才會知道該如何改進。
從這邊開始作者遇到非專業領域下產生的第一個巨大困難，一個機器若要達到高效率且完美 work 在整個流程當中，需要參照設計理念在各個達到精準，且需透過不斷實驗才會明白有時候機器不會如同預期那般順利運作，在分配冰塊的環節上作者連連碰壁，由於每次試驗可行性時都需要製造的大量等待期間，逐漸消耗掉預算和時間成本。
>你最大的問題在太害怕失敗了，既然都已經決定要延畢做飲料機了，那就要好好做，才不會辜負當初自己的期望。你可以計算要花多少錢，然後評估自己可以接受多少損失，畢業後慢慢還都好，要錢我也可以借你。但青春很貴，你也知道實習會發生什麼事，公司不會指派重要的工作給你，他們只會指派低風險的工作，你學習到的東西並不會比你現在多。你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。
作者在跟老師諮詢之前已經產生了不知道是否該持續下去的迷茫，但以老師觀點來看，相較於一般去公司實習所學，作者現況學習的東西反而更多，且裡面提到的「你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗」這段話帶給我很大啟發，有時候一個計劃、一個問題，甚至是一個想法都可能產生多種不同的問題需要解決，困難層出不窮的情況往往會使人感到疲憊或退卻，最終開始懷疑起自己曾經訂下的目標，而我們應該秉持的觀念不是害怕失敗小心翼翼的去避免它產生，而是學習去承受失敗，想盡辦法處理和補救它，才能夠真正獲得解決問題的能力。
>我們提了一些內部設計問題，像是接頭的規格、馬達控制流速的方式，確保買回來後，有能力改造他，改造現成的比自己做一台快多了。我們把糖機的控制板撬開，拿出印刷電路板把上頭的按鈕解焊掉，再焊上我們的控制線。如此一來就可以用電訊號來控制加糖機了。
在加糖的環節中作者原先的計劃因為糖漿的黏稠特性導致近乎報廢，然而剛好因展覽上看到別人現成的加糖機而有了新出路，甚至可降低原先金錢成本需求，有時候換角度去思考也能意外達成不錯的結果。
> 儘管世界如此殘酷，但人卻不一樣，當你真心想做到一件事，付出足夠的犧牲，這個世界會聽見並做出回應，周遭的人漸漸願意相信你、花時間幫助你，你的付出並不見得會有結果，但是加上許多人的幫助，可能一切就不一樣了。
對你而言真正重要的事物，會比你想得到的事物更早出現在路邊。
有時候付出的努力不一定會跟理想成正比，然而過程中獲得的事物卻會比想得到的更加珍貴和得來不易，飲料機最後雖然遠沒有達到預期的狀態，也因當兵及穩定度的關係最後塵封在倉庫中，但作者這14個月的努力和與志同道合的夥伴一同合作的回憶遠超乎自己所預期，最後對於結果的釋然也當作陪了當初天真的自己追了一個夢。
### 課堂心得
最初在選擇是否修這門課的時候猶豫很久，畢竟以前對 linux 的了解不多，又因為聽聞老師上課方式相比其他課較硬許多，所以在開學前就很緊張地去看了幾篇去年的教學影片，最後從身邊同學的鼓勵下才終於加簽進課程中。期初我對於跟不跟得上課程這件事感到相當慌亂，但在觀摩多位同學的學習紀錄後也開始對一些操作比較上手一些，雖然還是沒辦法完全趕上老師安排的進度，但對於這幾周的學習狀態我覺得相當充實，原本不熟悉的 C 語言在 lab0-c 作業中不斷練習現在也能使用的比較順手，原本只在教科書上淺略學習過的知識經由實作訓練讓我也更深入的理解到運作原理，例如 linked list 和 bitwise 等運用，老師也不斷希望我們不要只顧著相信既定程式碼，也要嘗試對他進行改善和驗證，並提出問題與同學及老師互相討論。
在製作學習筆記的期間，我更懂得如何歸納自己的想法和幫住我自己重新審視以前所讀，除了對程式碼更有印象更熟練外，也能再以與當時不同角度去思考如何改善。
## 研讀 CS:APP 3/e
* 2.1 信息儲存
以二進制表示太過冗長，換成十進制則在換成位元計算時會有需要轉化的困擾，於是以十六進制( hex )表示法來表示位元形式，單一 word 值域為 $00_{16} \sim FF_{16}$。
:::danger
檢查上述說法是否成立。
>已更正
:::
| 十進制 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| -------- |:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|
| 二進制 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
| 十六進制 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
最近出現大規模從32位元處理器遷移到64位元處理器，而大多數64位元處理器可運行由32位元處理器編譯後的程式碼，稱為向後兼容，例如以下指令:
``` shell
linux> gcc -m32 prog.c
```
而若程式碼已在64位元處理器編譯後則只能在64位元機器上運行，例下列指令:
``` shell
linux> gcc -m64 prog.c
```
因同一數據類型可能因為不同編譯器給的 words 大小不同，為了方便和避免錯誤產生 IOS C99up 引入一種固定大小的數據類型，且不會隨著編譯器而變化，其中例如 int32_t 和 int64_t ，各自別為 4 words 和 8 words。
word 內部儲存順序也有所不同，一般分為 little endian 和 big endian 兩種，前者由最低有效字組在最前面依序排序，後者則由最高有效字組排列。
假設變數x類型為 int，起始位址於 0x100 ，十六進制值為 0x01234567:
**little endian**
| ... | 0x100 | 0x101 | 0x102 | 0x103 | ... |
| --- |:-----:|:-----:|:-----:|:-----:| --- |
| ... | 67 | 45 | 23 | 01 | ... |
**big endian**
| ... | 0x100 | 0x101 | 0x102 | 0x103 | ... |
| --- |:-----:|:-----:|:-----:|:-----:| --- |
| ... | 01 | 23 | 45 | 67 | ... |
位元向量也可以做一種有限集合的表示，譬如 $[a_{w-1}, ..., a_1, a_0]$ 可編碼任一子集 $A\subseteq \{0, 1, ..., w-1\}$，假設 $a\overset{.}{=}\ [ 01101001 ]$ 對照其位置可表示成集合 $A=\{0, 3, 5, 6\}$，令假設一集合為$b\overset{.}{=}\ [ 01010101 ]$，即$B=\{0, 2, 4, 6\}$，配合布爾運算 `&` 可得 $A \cap B$ 結果 $\{0, 6\}$，以此類推由 `|` 計算 $A \cup B$。
C語言中的位移運算則會因不同型態有不同的變化，分為邏輯位移和算術位移，兩者在左位移時期皆為在右後方遞補 0 ，然而右位移時因遞補的位元在左前方會影響到有號數在正負符號下的判別，從而導致錯誤產生，所以對於有號數表示我們通常以算數位移的形式去計算。
| 右位移 | 01100011 | 10010101 |
| -------- |:----------:|:----------:|
| 邏輯位移 | *0000*0110 | *0000*1001 |
| 算數位移 | *0000*0110 | *1111*1001 |
* 2.2 整數表示
整數可分為無號數表示和有號數表示法，其中所使用到的操作術語整理成以下表格:
| 符號 | 類型 | 代表含義 |
| -------- |:----:|:------------------------------:|
| $B2T_w$ | 函數 | 二進制使用二補數表示法轉換 |
| $B2U_w$ | 函數 | 二進制使用無號數表示法轉換 |
| $U2B_w$ | 函數 | 無號數轉換為二進制 |
| $U2T_w$ | 函數 | 無號數轉換為二補數表示法 |
| $T2B_w$ | 函數 | 二補數表示法轉換為二進制 |
| $T2U_w$ | 函數 | 二補數表示法轉換為無號數表示法 |
| $TMin_w$ | 常數 | 二補數表示法最小值 |
| $TMax_w$ | 常數 | 二補數表示法最大值 |
| $UMax_w$ | 常數 | 無號數表示法最大值 |
**無號數轉換**
$B2U_w(\vec{x})=\sum\limits_{i = 0}^{w-1}{x_i2^i}$
無號數不用考慮正負號關聯，故以每個位元乘該位元代表的2的冪做總和取得結果，此型態的最大值用向量表示為$[11...1]$，計算公式為: $UMax_w = \sum\limits_{i = 0}^{w-1}{2^i}$，結果也等同於 $2^w-1$。
**有號數轉換**
$B2T_w(\vec{x})=-x_{w-1}2^{w-1} + \sum\limits_{i = 0}^{w-2}{x_i2^i}$
$x_{w-1}$作為最高有效位元用於判斷正負號，為 0 時表示為正值，後面照該位置的 2 的冪正常做加總，若為 1 時代表負數，則前面須加上 $-x_{w-1}2^{w-1}$ 。
* 2.3 整數運算
**無號數加法**
假設 $0\le x, y \lt 2^{w}$，則 $x+y$ :
\begin{cases}
x+y, & \text{$x+y<2^w$} \\
x+y-2^w, & \text{$2^w\le x+y<2^{w+1}$}
\end{cases}
若 $x+y<2^w$ 表示 $x+y$ 的最高位 w+1 等於 0，丟棄此位元不改變原本的值，若 $2^w\le x+y<2^{w+1}$ 則表示 $x+y$ 的最高位 w+1 等於 1，遺棄最高位相當於減去 $2^{w}$。
**二補數加法**
假設 $-2^{w-1}\le x, y \le 2^{w_1}-1$，則 $x+y$ :
\begin{cases}
x+y-2^w, & \text{$2^{w-1} \le x+y$} \\
x+y, & \text{$-2^{w-1}\le x+y<2^{w-1}$} \\
x+y+2^w, & \text{$x+y<-2^{w-1}$}
\end{cases}
## 研讀第 1 到第 6 週「課程教材」
- [類神經網路的 ReLU 及其常數時間複雜度實作](https://hackmd.io/@sysprog/constant-time-relu)
ReLU 用於類神經網路通過卷積層後的一種非線性激勵函數，旨在希望過濾負數值只讓正數輸出，通過 ReLU 的數值若原本是負數則輸出會變成零，若為正數則照原樣輸出，因此在實作中就需要有如何判斷正負的思路，且相較於整數運算，浮點數的操作成本較高，因此可引入 union 的概念藉由 int (有號整數)的操作簡化判斷成本。
:::info
- [ ] 在教材中 union 由兩個 field 組成，可讓浮點數與整數共用同一記憶體進行操作，查看教材原始碼的理解是可對其中一種型態做運算藉此更改其他型態的值，類似這種共用記憶體的方式是否可使用指標的概念實作?
- [ ] 想問這種藉由 int 位移量來判斷 sign bit 的正負值方式是否只能在確保 union 內部組成大小相同的情況下才能使用?註解中提及 `/*且 float 和 int32_t 都佔四個 byte*/` ，因IEEE-754 規定 float 大小固定為 32bits，另一個 int 型態指定為 int32_t，因此可直接依靠 int 的計算方式找出正負值。
:::
- [記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
CPU 在擷取資料時因效率因素會一次擷取 4bytes 或 8bytes 的資料量，這時若資料存放的位置不屬於 2 的冪就會無法一次性地拿到所有資料，需要耗費較多的存取時間。
根據教材的實驗結果，使用 `#pragma pack` 的 push 和 pop 模式自定義要 alignment 的 bytes 數，且因 struct 有自動對齊的默認值，使用兩個相同內容的結構體去實驗有無對齊在執行時間上的變化。
:::info
- [ ] 根據實驗結果大部分有做對齊的執行時間會比沒有對齊還少一些，但在有些情況沒有對齊的存取時間反而比做了對齊還低許多。
:::
- [編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization)
在 Page 71 提及 printf() 和 puts() 的差別，puts() 只支援字串型態的變數輸出，一旦找到 null terminator 就會結束執行，雖然功能性來說 printf() 較強大，能支援多種輸出格式，但以執行時間來說也比 puts() 來的長。
:::info
- [ ] 教材中提到編譯器為了達到最佳化執行效率，gcc 會把特定的 printf() 悄悄換成 puts()，編譯器是如何判定何時做替換的效果會達到最佳效益?若直接判斷輸出格式為單純字串型態就做替代的方式也能達成相同效果嗎?
:::
- [不只挑選任務的排程器](https://hackmd.io/@sysprog/linux-scheduler)
Linux 2.4 只使用一個共通的 global runqueue，即代表每個 core 都需競爭同一個 runqueue 內的任務，因此需要 locking 來保持互斥避免互相影響，Linux v2.6.0 開始維護兩種 queue 供核心執行，runqueue 及 expired queue，若執行中的 process 即將耗盡 timeslice 時就會被丟到 expired queue 中，且 runqueue 內沒有任何須執行的任務時則換成 expired queue 內的行程供核心執行。
:::info
- [ ] Linux v2.6.0 使用兩種 queue 的方式若 runqueue 內沒有行程時，會換成 expired queue 供核心執行，若 expired queue 的任務尚未全部執行完成時 runqueue 內有新行程產生，則會先等待 expired queue 結束全部待處理的任務再做切換，抑或是只需等待目前處理中的行程後再回到 runqueue 分配新任務?
:::
## 簡述你想投入的專案
1. **透過 Netfilter 自動過濾廣告**
不同於一般 [AdBlock](https://getadblock.com/) 採用extension來過濾廣告的作法，透過 [Netfilter](https://www.netfilter.org/) 直接在核心層級過濾網路廣告可減少更多系統占用資源。
2. **紅黑樹實作改進**
重新實做一次紅黑數及測驗的延伸問題，並提出可改進的想法和結果比較，且彙整其他學員的做法及成果。
TODO: rbree & XTree
TODO: 閱讀 CPU sched book 第 3 章關於 AVL tree vs. rbtree，注意 cache (CFS 總是存取具備最小 vruntime 的節點)
TODO: 設計實驗 + extra
Sign in with Wallet
Connect another wallet