# 2024q1 Homework5 (assessment) contributed by < `steven523` > ## 紀錄閱讀〈[因為自動飲料機而延畢的那一年](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1/)〉的啟發 看完這篇文章後我深刻體會到作者所說的： >人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。------《鋼之鍊金術師》 學習任何東西就像是進行一次次的等價交換，我們付出時間和努力，換取的是技能和知識。每當遇到問題時都需要花費時間去尋找答案，並嘗試各種可能的解決方案。過程可能會很艱難，但是只有通過這樣的過程，我們才能真正地融會貫通。 其次，等價交換的原則也提醒我們，沒有捷徑可以走。像是在 Linux 核心的世界裡，我們不能期待著不付出努力就能理解它。而是需要一點一點地去學習並進步，儘管有其他同學的開發紀錄可以參考，應該將其看作是一次學習的機會，而不是一昧的照抄。 作者注意到手搖飲料的製作過程相當固定，因此想到可以製作一台自動飲料機來降低人力成本。這種將日常生活中的觀察轉化為創新點子並增加效率的方法。這讓我想到在[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator:~:text=%E5%87%BD%E6%95%B8%E7%9A%84%E6%87%89%E7%94%A8%E3%80%82-,%E9%81%8B%E7%94%A8%20bit%2Dwise%20operator,-%E5%AF%A6%E4%BD%9C%E4%BA%8C%E9%80%B2%E4%BD%8D%E5%8A%A0%E6%B3%95)提到只利用 XOR 這個 Bitwise operator，就可以實作字元的大小寫轉換和交換兩個記憶體空間內的數值，除了能降低記憶體使用量，還能縮短程式碼長度。 >事情如果太順利代表絕對有問題，而問題永遠會從意想不到的地方冒出來。 創業的過程並非一帆風順，作者在製作自動飲料機的過程中遇到了許多困難，例如架構設計的問題，以及 3D 印表機的公差問題，甚至因為冰塊大小煩惱許久。這些問題讓他們的進度大大延後，甚至讓他們懷疑自己是否能完成整個專案。然而他們並沒有因此放棄，決定尋找更多的幫手，繼續努力。 >對你而言真正重要的事物，會比你想得到的事物更早出現在路邊 這段話給我留下了深刻的印象，有時候我們在追求夢想的過程中可能會忽視身邊重要的人和事，疏於珍惜與家人的時光。作者在追求創業夢想的過程中，與父親的相處時間越來越少，直到後來才發現父親其實可以給予他很多的幫助和支持。 >飲料機的程式愷宏是寫不出來的，之所以能在一個月內完成，是因為我在大學期間就寫過好幾個網站了。愷宏能和工廠溝通、設計出可用的零件，是因為他在大一就在跑工廠做東西了。紘銘能輕易的設計出飲料機的電路，是因為他曾花了很多時間在電子電路課上頭，做了很多習題，纏著教授把每個疑惑都搞懂才罷休。</br> >這個世界比任何人都殘酷，也比任何人都公平，犧牲了多少就會得到多少。飲料機現在能做到的事，就只是付出犧牲的結果罷了。 現在想想，自己在大學時期的學習態度，很多時候都是蒙混過去而沒學到什麼東西，基礎更是不用說。導致自己現在在讀碩士時什麼都不會，得花很多時間來補齊這些本來就該懂的知識，除了學習進度落後，在與同學相處的過程中也漸漸了解自己與他們落差有多大，但是後悔也來不及了。 ## 研讀第 1 到第 6 週「課程教材」 ### 你所不知道的 C 語言: linked list 和非連續記憶體 首先提到撰寫程式時的藝術，希望我們能嘗試在過程中思考「如何撰寫更優雅的程式碼」，像是通過指標的指標 ( indirect pointer) 來操作，希望從不同角度詮釋問題並精簡程式碼，除了能有效消除例外，也有避免動態記憶體配置的優點。 再來介紹了運用快慢指標的技巧實作來刪除鏈結串列中間的節點，它相較於單一指標的方式具有更好的時間局部性 (temporal locality)，因為對於同一個節點被二次存取的時間間隔較近，意旨參照過的記憶體位置很快就能再被參照，使觸發 cache miss 的機率降低。 最後說到在 Linux 核心中相當實用的 [linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)，為 circular doubly-linked list 的封裝，只需在自定義的結構中加入 struct list_head，就可以搭配 Linux 中一系列相關操作來建立自定義結構的鏈結串列。以此，老師有派作業希望我們能學習並且有效利用這些核心原始程式碼來改進各種跟佇列有關的操作，還有要求我們研讀 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)，這裡面說到與一般 merge sort 的差別，可發現 list sort 的合併方式能使 cache 中現存的資料更容易被使用到，進而減少 cache-misses，降低執行時間 ; 而 merge sort 通常需要額外的記憶體空間來儲存很多個子串列，然後一次合併，這時通常會發生很多 cache-misses，在空間局部性的表現上較差，甚至導致 cache trashing。另外還有其迭代的算法能使 branch 的次數更少，因為更多的 branch 操作可能會造成較多的 CPU 運行中斷或預測失誤，導致程式的執行效能變差。 ### 類神經網路的 ReLU 及其常數時間複雜度實作 邏輯迴歸是用來處理分類問題，目標是找到一條直線可以將資料做分類。主要是利用 sigmoid function 將輸出轉換成 0~1 的值，表示可能為這個類別的機率值。而線性迴歸是用來預測一個連續的值，目標是想找一條直線可以逼近真實的資料。 ![image](https://hackmd.io/_uploads/HJLTJcuQR.png =60%x) :::info 文章裡提到使用了位元操作來實作 ReLU，為何不直接使用條件判斷 ? 這樣做對於像是 SIMD 或其他平行計算架構的性能等有何差異? ::: ### 你所不知道的 C 語言：記憶體管理、對齊及硬體特性 一開始能了解到 `void *` 是一種特殊的指標類型，可以指向任何型態，使得它在處理不同資料類型時具有很大的靈活性。不過運用這種靈活性時也要注意，我們不能直接對 `void *` 進行數值操作，必須進行先顯式轉型（explicit casting）或強制轉型（forced casting），以明確地告訴編譯器我們要將 `void *` 轉換為什麼類型的指標，否則會出現錯誤訊息，這種保護機制可以避免我們進行危險的指標操作，從而產生未定義行為（Undefined behavior）。 Linux 提供了記憶體映射函式 `mmap`、`munmap`，可以將檔案映射或取消映射到記憶體中，使得我們可以像操作記憶體一樣來存取這些物件。此外 `MAP_PRIVATE` 選項和寫入時複製（Copy-on-Write）的機制，允許多個行程共享同一塊記憶體，並在需要寫入時才複製記憶體，這不僅能確保資料的安全性，也能有效節省記憶體。 :::danger 注意用語： * access 是「存取」，不是「訪問」(visit) * process 是「行程」 * function 應當針對不同情境，區分「函式」「函數」，和「功能」 參照第一手材料 (如 Linux man-pages)，避免低劣簡體中文的翻譯。 >已更改，並會多使用第一手材料查詢 ::: Data alignment 的運用可以有效加快 CPU 存取速度，不過缺點就是會浪費記憶體空間，舉例來說對於像 char 這種只有 1 byte 的型態，電腦也會給他 4 bytes 的空間。此時使用 `#pragma pack` 這個預處理指令改變記憶體的封裝長度，從而改善浪費空間的問題。 ## 你所不知道的 C 語言：數值系統 透過 XOR 交換算法，不需要額外記憶體即可交換兩個數值，展現了位元運算的強大應用。此外利用 XOR 運算來轉換字母大小寫，只需一行程式碼即可完成，還有像用位元運算檢查 32-bits 資訊是否為 0 或 NULL 的方法，也展示了它在優化程式效能上的巨大潛力，特別是在處理長字串時比傳統方法更有效率。這些技術不僅讓程式碼更具藝術性，也大大提升了執行效率。 :::info 既然文中提到平衡三進位具有易於正負轉換的特性，轉換效率好，且不需要像二進位表示法那樣特別考慮 signed 和 unsigned 的區別，為什麼目前大多數系統還是使用二進位？ ::: ## 簡述你想投入的專案 ### 透過 Netfilter 自動過濾廣告 儘管我們可在網頁瀏覽器中透過像是 AdBlock 這類的 extension 來過濾廣告，但需要額外的設定和佔用更多系統資源，倘若我們能透過 netfilter，直接在核心層級過濾網路廣告，那所有應用程式都有機會受益。 ### Linux 排程器研究 探討 Linux 排程器內部設計，改進《Demystifying the Linux CPU Scheduler》，並尋求貢獻程式碼到 Linux 核心的機會 ### 高效網頁伺服器 --- https / TLS 原理 TODO: w/ aa860630 > https://hackmd.io/@qOvjgDvTQrGZGAlv5oHqsA/linux2024-homework5 --- 用來設定 iptables 阻擋從本地系統發往特定網址的廣告流量指令 [List of ad server IP addresses for use with iptables](https://pgl.yoyo.org/as/iplist.php?ipformat=iptables&showintro=1&mimetype=plaintext)