2025q1 Homework5 (assessment)

# 2025q1 Homework5 (assessment) contributed by < `MuChengChen` > ## [〈因為自動飲料機而延畢的那一年〉](https://blog.opasschang.com/the-story-of-auto-beverage-machine-1) 讀後心得在這篇文章中，看到作者從幻想創業並做一台自動飲料機，到不斷的實驗試錯，到和不同領域的同學分工合作，到面對挫敗的無力，到和部分的現實妥協，到完成整項專案的整個過程。可以發現作者起初只是要解決更具體且實際的問題，就像是老師上課時提到的諸多專案一樣，目的是改善現有軟體某個功能的效能或是不足之處，然而如同文章中作者遇到的許多問題和挫敗一樣，要做出能運用到現實世界中的系統必定會遇到許多超乎想像的問題，且牽涉的領域很有可能不是單一的領域，需要面對我們不熟悉的領域並和擅長該領域的人共事。我也看到了作者在實作自動飲料機時對於細節的重視，包括考慮食安的問題而選用貴但相對安全的材質，用實驗上百次的數據證明秤冰塊的荷重元誤差是可以接受的等等，這和老師在課堂上一直強調的「對於細節的重視」一樣，若是不重視細節有可能會輕則造成系統效能低落，公司收益受損，重則造成難以估量的危害。現在的我就如同作者剛開始的情況一樣，尤其是沒有上過作業系統使的情況更加的糟糕，完全跟不上課程，寫測驗題和作業時也是挫敗重重，然而就像老師講的「缺甚麼，補什麼」並且「誠實面對自己」，也被老師在文章中所說的「你該學習的不是看到事情要完蛋了就去避免失敗，而是應該學習如何處理與承受失敗，你才能變得比以前更強大。」所啟發，太害怕失敗會失去成長的機會，反之，勇敢處理與承受失敗才有變強大的可能。 ## 討論議題 1. 在 CPU - Book 1.2.4 章節中提到不管是 32 位元或 64 位元系統核心的 page size 是 4 KiB，那為什麼32 位元系統的 stack size 是 8 KiB，64 位元系統的 stack size 是 16 KiB ? (在第 9 頁的第 18 行， The order of the page size ...... ) ## 問題追蹤 - Q1: Linux 「核心」內的 stack 空間是否會動態調整？在 Linux 中有 User stack 、 Kernel stack 和 interrupt stack，而 User stack 的空間有可能會動態調整， Kernel stack 則不會，Kernel stack 也是 kernel space 的一部分，所以無法直接被 user process 所使用。當在 32 位元系統時 Kernel stack 大小為 8 KiB， 64 位元系統則是 16 KiB。當一個行程 (process) 被建立時會有對應的 User stack 和 Kernel stack，在 user space 執行時會使用 User stack，然而當行程因為 system call 而轉換到 kernel space 執行時則會使用 Kernel stack。 interrupt stack 則是被用來處理額外的中斷。 ![image](https://hackmd.io/_uploads/S1-KBjrmlg.png) 我們可以使用 `ulimit -s` 查看和改變 User stack 的大小 ``` n96134271@n96134271-ASUS-EXPERTBOOK-B1400CEAEY-B1400CEAE:~$ ulimit -s 8192 n96134271@n96134271-ASUS-EXPERTBOOK-B1400CEAEY-B1400CEAE:~$ ulimit -s 32768 n96134271@n96134271-ASUS-EXPERTBOOK-B1400CEAEY-B1400CEAE:~$ ulimit -s 32768 ``` - Q2: 不依賴分支 (if-else, ?, switch-case, for, while)、迴圈、遞迴的前提，實作 bitcount，亦即計算給定數值的二進位表示中，1 (set) 的總量。 e.g., bitcount(64) = 1, bitcount(65) = 2 利用 bitmask 和 look up table 並且使用 loop unrolling 技巧可以避免使用到分支 ```c //lookup table int num_to_bit_table[16] = { 0,1,1,2,1,2,2,3, 1,2,2,3,2,3,3,4 }; int bitcount(unsigned x) { int i = num_to_bit_table[x&0xF] + num_to_bit_table[(x>>4)&0xF] + num_to_bit_table[(x>>8)&0xF] + num_to_bit_table[(x>>12)&0xF] + num_to_bit_table[(x>>16)&0xF] + num_to_bit_table[(x>>20)&0xF] + num_to_bit_table[(x>>24)&0xF] + num_to_bit_table[(x>>28)&0xF]; return i; } ``` ``` n96134271@n96134271-ASUS-EXPERTBOOK-B1400CEAEY-B1400CEAE:~/linux2025/experiment$ ./bitcount 4294967295 : 32 set bits 2147483647 : 31 set bits 1073741823 : 30 set bits 536870911 : 29 set bits 268435455 : 28 set bits 134217727 : 27 set bits 67108863 : 26 set bits 33554431 : 25 set bits 16777215 : 24 set bits 8388607 : 23 set bits 4194303 : 22 set bits 2097151 : 21 set bits 1048575 : 20 set bits 524287 : 19 set bits 262143 : 18 set bits 131071 : 17 set bits 65535 : 16 set bits 32767 : 15 set bits 16383 : 14 set bits 8191 : 13 set bits 4095 : 12 set bits 2047 : 11 set bits 1023 : 10 set bits 511 : 9 set bits 255 : 8 set bits 127 : 7 set bits 63 : 6 set bits 31 : 5 set bits 15 : 4 set bits 7 : 3 set bits 3 : 2 set bits 1 : 1 set bits ``` - Q3: 資訊科技領域中，何時用得到 bitcount? - 在分析 AES、DES 加密演算法時會使用到漢明距離，例如測量 AES 的擴散特性，而漢明距離的計算就會使用到 bitcount - 在 CIDR 中，CIDR 表示法為一個 IP 地址，一個斜線和一個十進制數字，而十進制數字為網路掩碼從左到右連續的 set bits 計數，因此計算該十進位數字就會使用到 bitcount - Q4: 為何 DRAM 會出錯? DRAM 由於需容納大量的記憶單元，記憶單元中的電容電量很低 ( $10^{-15}$ 法拉或更低)，因此只需要很短的時間電容的電量就會被耗盡，需要不斷重複對電容充電，此現象稱為漏電。漏電現象可能會導致資料的遺失，尤其在高溫環境下更為嚴重，因此 DRAM 需定期刷新以確保資料完整性，然而頻繁的刷新會造成 DRAM 資料存取的效能損失。