# 2025q1 Homework5 (assessment)
contributed by < `JeffBla` >

## 「自動販賣機而延畢的那一年」的讀後感想

正所謂人不輕狂枉少年，故事中的主角和當初國中的我相似，也因為這樣，引領我的是電機資訊學系。因為的遊戲關服，而決定模仿這種遊戲，踏上學習 3d 建模動畫、unity、python、c#等旅程，最後雖然 3d 建模動畫還堪用，但因為過程難度太高與瑣碎而澆熄了熱情，最後每個都會但，沒有把他們拼在一起，以失敗告終。那時的我貫徹一種精神，有些事情真的好難，我缺好多東西，我要把這些難題交給未來的我。就這樣，目前的我雖未完成這件事，但箇中原理現在的我已清楚知曉，大二的暑假，捨棄熟習的 unity，踏上 unreal 的旅程，我總稱它無字天書，因為文檔什麼也沒有，很多時候靠的是實驗與查資料，而 3d 模型的問題，也不再像小時候，每件事情都從重新造輪子，靠的是金錢的力量與修改別人檔案的本事。

很佩服作者找資源的本事，協調、還價與向人請教。目前的我還在重新找尋那種感覺，那種突破點，就像自動販賣機是作者想做的事情，是作者的青春，國中的我模仿已關服遊戲與製作 8 足機器人（在大三時利用 pic18f 重現了）是我的青春，而現在的我找不到在軟體的定位，唯一還算得上的是大三專題：AI 個人教練：結合電腦視覺在三維空間中呈現，並基於姿勢分析給出建議，也因此進入到交大的圖學與互動實驗室（目前大四）。奇怪的是，這些都符合我的興趣，也符合我的動機，但我的目標仍然不清楚，目前只是朝著我認為的未來機會與興趣，如：3d、多平行，發展。

這篇文章提醒了我對知識的貢獻與學習方法以及義無反顧的目標，我應該利用大四的剩餘時光，好好的重新審視。

## 前 6 週學習狀況

<s>前六周教材進度大致有跟上，看完相關內容。作業未能撰寫完善，大多有缺漏沒有完成</s>
:::danger
不要書寫含糊的話語，紀錄你的問題！
:::

- 在 [你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization) 有提到程式執行流程，介紹 ELF 但卻沒有他和程式執行流程的關聯，對我來說，ELF 只是一個儲存資訊的檔案，實際如何 execve 一無所知。因此[進一步觀察](https://hackmd.io/@JeffBla/Hy7gPj2Ckx)，利用 objdump 與 readelf 搭配 chatgpt 了解 ELF 如何被載入、配置。

- 在 [並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics#%E6%98%93%E6%96%BC%E8%AA%A4%E7%94%A8-volatile-%E9%97%9C%E9%8D%B5%E5%AD%97) 中無法重現在 x64 與 aarch64 上：

    int a = 0, b = 0;
    void foo(void)
    { 
        a = 1; 
        b = 1;
    }

    void bar(void)
    { 
        while (b == 0)
            continue; 
        assert(a == 1);
    }

而感到疑惑，並將所找資料[記錄](https://hackmd.io/@JeffBla/rkol7lb1el)。
為了確認 cpu 有 out of order execution.
其在

    #include <pthread.h>
    #include <stdio.h>
    #include <stdlib.h>

    static int loop_count;
    static int A, B, X, Y;

    static void *worker1(void *arg)
    {
        X = 1;
        asm volatile("" ::: "memory");
        A = Y;
    }

    static void *worker2(void *arg)
    {
        Y = 1;
        asm volatile("" ::: "memory");
        B = X;
    }

    int main(int argc, char *argv[])
    {
        pthread_t thread_1, thread_2;

        int64_t count = 0;

        if (argc != 2) {
            fprintf(stderr, "USAGE: %s <loop_count>\n", argv[0]);
            exit(1);
        }

        loop_count = atoi(argv[1]); /* FIXME: format checks */

        for (int i = 0; i < loop_count; ++i) {
            X = 0;
            Y = 0;

            /* Start the threads */
            pthread_create(&thread_1, NULL, (void *(*) (void *) ) worker1, NULL);
            pthread_create(&thread_2, NULL, (void *(*) (void *) ) worker2, NULL);

            /* Wait for the threads to end */
            pthread_join(thread_1, NULL);
            pthread_join(thread_2, NULL);

            if (A == 0 && B == 0) /* reorder caught */
                count++;
        }

        printf("%d reorder caught in %d iterations.\n", count, loop_count);

        return 0;
    }

等待一段時間後，會出現 out of order execution，之後，將目光放在 `store buffer` 上，也許 `store buffer` 停住，沒有運作？在 [**The microarchitecture of Intel, AMD, and VIA CPUs** - An optimization guide for assembly programmers and compiler makers](https://www.agner.org/optimize/microarchitecture.pdf) 確實說明 `store buffer` 會失效的情況，但上述程式碼並非失效的情形，因此為何該程式碼實驗沒有達成預期仍需進一步討論。

## 程式碼貢獻

[[cling] Refine build and usage guide](https://github.com/root-project/root/pull/18161#event-17112971136)

[fix typo in〈Demystifying the Linux CPU Scheduler〉](https://hackmd.io/@JeffBla/SJQBKow0yl)

## 隨堂測驗和作業回顧

### lab0

#### 完成事項

- 完成 queue.c 的函式功能實現
- 追蹤並修改 dudect 的程式
- 追蹤 list_sort 的程式，並且嘗試理解它更有效率的原因

#### 問題

- 和 `weiso131` 討論 `merge_final` 與 `q_merge` 的作法並參考 [kdnvt的研讀 lib/list_sort.c筆記](https://hackmd.io/@kdnvt/linux2022_lab0#%E7%A0%94%E8%AE%80-liblist_sortc)。在 `list_sort.c` 中提到：

    /*
     * Combine final list merge with restoration of standard doubly-linked
     * list structure.  This approach duplicates code from merge(), but
     * runs faster than the tidier alternatives of either a separate final
     * prev-link restoration pass, or maintaining the prev links
     * throughout.
     */

其說明了 `merge_final` 會較快於其他兩個方法，這解釋了為何自己實作的 `merge_final` 會較差。

- 對於 `dudect`，程式碼的執行時間在不同類別有不同的執行分布，而其利用 t 檢定，希望兩者的平均數相近，若不符合前述，則判斷為非常數時間演算法。然而若將兩類別的分布畫出來，可以發現其平均數差異，如下圖。
與 `weiso131` 討論後發現，他們找到問題的原因： [malloc 時間與 input_data 的關聯 - weiso131](https://hackmd.io/@weiso131/linux2025-homework1#malloc-%E6%99%82%E9%96%93%E8%88%87-input_data-%E7%9A%84%E9%97%9C%E8%81%AF)

### kxo

#### 完成事項

- 利用 bit 儲存棋盤資料
- 將 draw_board 移至 user space
- 將 select-based I/O 換成 coroutines 處理

### quiz1+2

- 改進 random_shuffle_array

- 在 [從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt) 遇到問題，不理解 `Digit-by-digit Method` 是如何寫成下列程式碼：

    uint64_t sqrt_ceil(uint64_t x)
    {
        uint64_t m, y = 0;
        if (x <= 1)
            return x;

        int total_bits = 64;

        int shift = (total_bits - 1 - clz64(x)) & ~1;
        m = 1ULL << shift;

        while (m) {
            uint64_t b = y + m;
            y >>= 1;
            if (x > b) {
                x -= b;
                y += m;
            }
            m >>= 2;
        }
        return y + 1;
    }

在看了 `rota1001` 的筆記知道是從原本的數學式寫成程式碼：

    uint64_t sqrti_simple(uint64_t x)
    {
        uint64_t m, y = 0;
        if (x <= 1)
            return x;

        int total_bits = 64;
        int shift = (total_bits - 1 - clz64(x)) & ~1;

        uint64_t p = 0;
        for(int i = (shift / 2); i >= 0; i--) {
            uint64_t b = (p << (i + 1)) + (1 << (2 * i));
            if (x >= b) {
                x -= b;
                p += (1 << i);
            } 
        }
        return y;
    }

並化簡。

## 一對一討論

- [2025年4月30日](https://hackmd.io/U10ofMHJQFaNJ3GWf9a9Xw)

## 期末專案討論

對於並行程式設計有興趣，但覺得 [並行程式設計: Atomics 操作](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-atomics#%E6%98%93%E6%96%BC%E8%AA%A4%E7%94%A8-volatile-%E9%97%9C%E9%8D%B5%E5%AD%97) 的材料過於零散沒有一個很好的組織與實作，展現實際 `atomic` 、 `store buffer` 、`fence` 等操作，讓我有學到，但還是一知半解，不知道怎麼使用，甚至覺得這真的會發生嗎？以及誰寫程式會這麼複雜的想法？

另外， `ktcp` 中的 kernel thread 與 CMWQ ，對我來說也是很好的教材，也許可以從中讓我認識並行程式的實際案例。在 `ktcp` 的講解中提到 CMWQ 提升了接近一倍的 throughput ，那如果不只是多執行緒，甚至多台電腦溝通，效果會如何？