2024q1 Homework5 (assessment)

contributed by < 56han >

閱讀〈因為自動飲料機而延畢的那一年〉的啟發

在每一次開始寫作業時，都覺得遇到了許多挫折，明明已經學過程式起碼四年，卻常常需要花許多時間理解題目或程式碼，觀摩其他學員的成果時，都會思考「為甚麼他想的到？」

飲料機的程式愷宏是寫不出來的，之所以能在一個月內完成，是因為我在大學期間就寫過好幾個網站了。愷宏能和工廠溝通、設計出可用的零件，是因為他在大一就在跑工廠做東西了。紘銘能輕易的設計出飲料機的電路，是因為他曾花了很多時間在電子電路課上頭，做了很多習題，纏著教授把每個疑惑都搞懂才罷休。

經過閱讀此文章後，發現所有成果都是一點一滴的累積而來，發明自動飲料機的每一個細節都不簡單，他們能成功也不是偶然，或許當下不是學習本科的內容，但或許有一天就會派上用場。現在 linux 課程也讓我有一樣的體悟，雖然常說學 linux 不知道哪天會用到，但這些努力可以讓我學習到解決問題的能力、勇於面對挫折的精神、開發系統軟體的態度、對細節的重視，以及理論和實務的融會貫通。此外，文章也讓我思考能力不足的原因，「為甚麼他想的到？」是因為其他學員花很多時間去搞懂 C 語言規格，因此現在才能在時間內完成作業，而我從以前就是為了應付作業、交差了事的學生，現在才感受到痛苦與挫折，是因為我回來還債了，就如同開頭提到的

人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。–––《鋼之鍊金術師》

研讀課程教材

紀錄心得

提問

1. O(1) 排程器的問題
   已知綜合考量下，我們可選擇的範圍就很有限：
   access 只能用 array;
   insert/deletion 只能用 linked list, queue, stack;
   所以最後在 Linux 2.6 排程器中，是選擇 FIFO queue( insert / deletion ) + 尋找指定 bitarray 第一個設定為 1 的位元 ( access )
   Q：這樣是若有 M 個 queue，bitarray 的大小是 logM 嗎？
   Q：會有 queue 數量近似於 task 數量的情形嗎？

per-CPU runqueue
ffs

2. 關於 作業6 fibdrv 的問題
   Q：注意到 511 這個數字，試著對照 fibdev.c，找尋彼此的關聯？

fibdev major/minor number
/dev/ tty0, tty1, tty2, …

簡述我想投入的專案

閱讀眾多精選範例後，我認為 CPU 排程器蠻有趣的，了解各種排程器的原理，並實現在 Linux 系統上，像是在新版本的 Linux 上執行 CPU 排程器。

---

一對一討論

題目：IEEE 754, single precision (aka float). Assume 32-bit.

程式碼

// Return x * 10
float float_mul10(float x)
{
    // using bitwise operation. No mul/div
    unsigned int bits = *(unsigned int*)&x;
    unsigned int sign = bits >> 31;
    unsigned int exp = (bits >> 23) & 0xFF; 
    unsigned int frac = bits & 0x7FFFFF; 
    if (exp == 0) {
        return 0;
    }

    // x * 8 + x * 2
    unsigned int exp_shift_3 = exp + 3;
    unsigned int exp_shift_1 = exp + 1;
    if (exp_shift_3 >= 255 || exp_shift_1 >= 255) {
        return sign ? -INFINITY : INFINITY;
    }

    unsigned int bits_shift_3 = (sign << 31) | (exp_shift_3 << 23) | frac;
    unsigned int bits_shift_1 = (sign << 31) | (exp_shift_1 << 23) | frac;
    float result = *(float*)&(bits_shift_3) + *(float*)&(bits_shift_1);

    return result;
}

TODO: 程式碼補完並測試

解釋

step 1：

unsigned int bits = *(unsigned int*)&x;

• 獲取浮點數 x 的記憶體位址。
• 將該位址類型轉換為指向 unsigned int 類型的指標。
• 透過 derefernce 該指標，獲取浮點數 x 的 bit pattern ，並將其儲存到 unsigned int bits 變數中。

step 2：

unsigned int sign = bits >> 31;
unsigned int exp = (bits >> 23) & 0xFF; 
unsigned int frac = bits & 0x7FFFFF; 

將 bits 轉換為 IEEE 754 的格式。

step 3：

unsigned int exp_shift_3 = exp + 3;
unsigned int exp_shift_1 = exp + 1;

要找到 10 的的二進位表示法，因 10 = 8 + 2 ，所以將 x * 10 拆成 x * 8 + x * 2 。

step 4：

unsigned int bits_shift_3 = (sign << 31) | (exp_shift_3 << 23) | frac;
unsigned int bits_shift_1 = (sign << 31) | (exp_shift_1 << 23) | frac;
float result = *(float*)&(bits_shift_3) + *(float*)&(bits_shift_1);

將兩個結果相加，把結果還原成浮點數。

此外，還需要排除 IEEE 754 Special Values （overflow 和 0）的情形。

if (exp == 0) {
    return 0;
}

...
    
if (exp_shift_3 >= 255 || exp_shift_1 >= 255) {
        return sign ? -INFINITY : INFINITY;
    }

測試任意數（包括 ieee 754 的特例）

Case	Input	Output
1	13.125	131.25
2	-13.125	-131.25
3	0	0
4	-0	-0
4	nan	nan
5	FLT_MIN (即 1.175494e-38)	FLT_MIN * 10 (即 1.175494e-37)
6	-FLT_MIN	-FLT_MIN * 10
7	FLT_MAX (即 3.402823e+38)	inf
8	-FLT_MAX	-inf
9	FLT_TRUE_MIN (即 1.401298e-45)	FLT_TRUE_MIN * 10 (即 1.401298e-44)
10	-FLT_TRUE_MIN	-FLT_TRUE_MIN * 10
11	inf	inf
11	-inf	-inf

註：
FLT_MIN （最小正規化數）#define FLT_MIN 1.17549435e-38F
-FLT_MIN （最小負規化數）
FLT_MAX （最大正數）// FLT_MAX = 3.402823e+38
-FLT_MAX （最小負數）
FLT_TRUE_MIN（最小非正規化數）#define FLT_TRUE_MIN 1.40129846e-45F
-FLT_TRUE_MIN（最小非負規化數）

---

TODO: Quiz7 + extra