2025q1 Homework1 (lab0)

contributed by < willy-liu >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu | grep -E "Architecture|CPU op-mode|Byte Order|Address sizes|CPU\(s\)|On-line CPU\(s\) list|Thread\(s\) per core|Core\(s\) per socket|Socket\(s\)|NUMA node\(s\)|Vendor ID|CPU family|Model:|Model name|Stepping|CPU MHz|CPU max MHz|CPU min MHz|BogoMIPS|Virtualization|L1d cache|L1i cache|L2 cache|L3 cache|NUMA node0 CPU\(s\)"
Architecture:                         x86_64
CPU op-mode(s):                       32-bit, 64-bit
Address sizes:                        39 bits physical, 48 bits virtual
Byte Order:                           Little Endian
CPU(s):                               12
On-line CPU(s) list:                  0-11
Vendor ID:                            GenuineIntel
Model name:                           Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
CPU family:                           6
Model:                                158
Thread(s) per core:                   2
Core(s) per socket:                   6
Socket(s):                            1
Stepping:                             10
CPU(s) scaling MHz:                   25%
CPU max MHz:                          4600.0000
CPU min MHz:                          800.0000
BogoMIPS:                             6399.96
Virtualization:                       VT-x
L1d cache:                            192 KiB (6 instances)
L1i cache:                            192 KiB (6 instances)
L2 cache:                             1.5 MiB (6 instances)
L3 cache:                             12 MiB (1 instance)
NUMA node(s):                         1
NUMA node0 CPU(s):                    0-11

針對佇列操作的程式碼實作

觀念釐清

結構、函式解釋

element_t - 雙向鏈結串列中的元素

element_t 是一個雙向鏈結串列（doubly-linked list）的節點（element）。
value 是指向字串的指標，需手動分配（malloc）並手動釋放（free）。
list 是 struct list_head 類型，允許將 element_t 插入 Linux Kernel 風格的鏈結串列。

queue_contex_t - 佇列管理結構

q：指向佇列的頭部，類型為 struct list_head*，用於管理佇列的起點。
chain：允許多個佇列鏈結在一起，形成佇列的集合（類似多佇列管理）。
size：紀錄佇列長度，方便計算操作的複雜度。
id：唯一識別碼，讓每個佇列可被區分。

:warning:
如果q->next == q->prev == q，代表該佇列是空的，否則應該要指向某個element_t的list

q_new

Commit 9ab5ddf

建立新的「空」佇列

     struct list_head *head = malloc(sizeof(struct list_head));
-    if (!head)
-        return NULL;
-    head->next = head;
-    head->prev = head;
+    if (head) {
+        INIT_LIST_HEAD(head);
+    }
     return head;

一開始沒有特別留意 list.h 裡有哪些巨集可用，後來看過之後發現 INIT_LIST_HEAD 可以讓 q_new 的實作更簡潔、也更容易閱讀。

q_free

Commit 360896c

釋放佇列所佔用的記憶體

-    struct list_head *current = head->next;
-    while (current != head) {
-        element_t *element = list_entry(current, element_t, list);
-        current = current->next;
-        if (element->value) {
-            free(element->value);
-        }
-        free(element);
+    struct list_head *entry, *safe;
+    list_for_each_safe (entry, safe, head) {
+        q_release_element(list_entry(entry, element_t, list));
     }
     free(head);

使用list_for_each_safe來簡化原本的while loop，另外也把原本的if condition改成用q_release_element。

:warning: 原本要使用list_for_each_entry_safe，$ make test可以通過，但下了commit就會過不了static analysis，錯誤訊息如下

Running static analysis...
queue.c:29:5: style: Label 'int' is not used. [unusedLabel]
    list_for_each_entry_safe (entry, safe, head, list)
    ^

Fail to pass static analysis.

然而q_free裡根本沒有用到int，我進到list_for_each_entry_safe的巨集裡查看，如下

#if __LIST_HAVE_TYPEOF
#define list_for_each_entry_safe(entry, safe, head, member)            \
    for (entry = list_entry((head)->next, typeof(*entry), member),     \
        safe = list_entry(entry->member.next, typeof(*entry), member); \
         &entry->member != (head); entry = safe,                       \
        safe = list_entry(safe->member.next, typeof(*entry), member))
#else
#define list_for_each_entry_safe(entry, safe, head, member)       \
    for (entry = safe = (void *) 1; sizeof(struct { int : -1; }); \
         ++(entry), ++(safe))
#endif

注意到#else的部分，迴圈條件sizeof(struct { int : -1; });是一個錯誤的語法，會編譯錯誤，我認為這個#else本來就是要用來提醒programmer無法該環境使用此巨集，雖然該部分照理來說只要__LIST_HAVE_TYPEOF為1不會被執行到，但那個int會被static alaysis檢測出來，無法通過。

再往前看__LIST_HAVE_TYPEOF定義為

#if defined(__GNUC__) || defined(__clang__) ||         \
    (defined(__STDC__) && defined(__STDC_VERSION__) && \
     (__STDC_VERSION__ >= 202311L)) /* C23 ?*/
#define __LIST_HAVE_TYPEOF 1
#else
#define __LIST_HAVE_TYPEOF 0
#endif

只要編譯器是GNU、Clang且標準C版本大於C23就應該不會報錯。

我又到了scripts/pre-commit.hook查看，發現使用了cppcheck做static analysis，而__GNUC__、__clang__等是編譯器提供的巨集，所以在static analysis時他們當然就不存在，也就導致__LIST_HAVE_TYPEOF就會被define成0導致檢查出錯。

✅解決方法
要在cppcheck用-d選項把編譯器參數傳進去，如下
(最後根據老師的pr review，使用bash function包起來再assign給CPPCHECK_OPTS，並且改使用cc來取得C Compiler，再進行STDC_VERSION等檢查，而不是直接用gcc/clang等指令)

+# Generation of standard compliance for GCC/Clang
+detect_cc_std() {
+  local STDC_VERSION=""
+  local EXTRA_DEFINES=""
+  if command -v cc >/dev/null 2>&1; then
+    if cc --version 2>/dev/null | grep -q "clang"; +then
+      STDC_VERSION=$(cc -dM -E -xc /dev/null | awk +'/__STDC_VERSION__/ {print $3}')
+      EXTRA_DEFINES="-D__clang__=1"
+    elif cc --version 2>/dev/null | grep -q "Free +Software Foundation"; then
+      STDC_VERSION=$(cc -dM -E -xc /dev/null | awk +'/__STDC_VERSION__/ {print $3}')
+      EXTRA_DEFINES="-D__GNUC__=1"
+    fi
+  fi
+  if [ -n "$STDC_VERSION" ]; then
+    EXTRA_DEFINES+=" -D__STDC__=1 -+D__STDC_VERSION__=${STDC_VERSION}"
+  fi
+  echo "$EXTRA_DEFINES"
+}
+
 CPPCHECK_OPTS="-I. --enable=all --error-exitcode=1"
+CPPCHECK_OPTS+=" $detect_cc_std"
 CPPCHECK_OPTS+=" --force $(cppcheck_suppressions) $(cppcheck_build_unmatched)"
 CPPCHECK_OPTS+=" --cppcheck-build-dir=.out ."

q_size

Commit 03f6e38

計算目前佇列的節點總量

     int count = 0;
-    struct list_head *current = head->next;
-    while (current != head) {
+    struct list_head *node;
+
+    list_for_each (node, head)
         count++;
-        current = current->next;
-    }

使用了list.h的巨集list_for_each進行重構，提升整體可讀性。

q_insert_head

Commit 51562f7

在佇列開頭 (head) 插入新節點（LIFO 準則）

    if (!head || !s)
        return false;

    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element)
        return false;

    new_element->value = strdup(s);
    if (!new_element->value) {
        free(new_element);
        return false;
    }

-    new_element->list.next = head->next;
-    new_element->list.prev = head;
-    head->next->prev = &new_element->list;
-    head->next = &new_element->list;
+    list_add(&new_element->list, head);

重構時發現list.h裡本來就有一個function跟原本插入節點的程式碼做一樣的事，因此把原本的替換掉，提高可讀性。

q_insert_tail

Commit 51562f7

在佇列尾端 (tail) 插入新節點（FIFO 準則）

 bool q_insert_tail(struct list_head *head, char *s)
 {
-    if (!head || !s)
-        return false;
-
-    element_t *new_element = malloc(sizeof(element_t));
-    if (!new_element)
-        return false;
-
-    new_element->value = strdup(s);
-    if (!new_element->value) {
-        free(new_element);
-        return false;
-    }
-
-    new_element->list.next = head;
-    new_element->list.prev = head->prev;
-    head->prev->next = &new_element->list;
-    head->prev = &new_element->list;
-
-    return true;
+    return q_insert_head(head->prev, s);
 }

重構後想到，既然是雙向"環狀"的佇列，且佇列空的時候會有一個dummy head，prev和next都連到自己，那insert_tail不就只要把head移動到prev後再insert_head就好嗎，可讀性變佳的同時也少了大量重複程式碼。

q_remove_head

Commit 1bf85d5

在佇列開頭 (head) 移除節點

     if (!head || head->next == head)
         return NULL;
-    struct list_head *node = head->next;
-    element_t *element = list_entry(node, element_t, list);
+    element_t *element = list_entry(head->next, element_t, list);
 
-    head->next = node->next;
-    node->next->prev = head;
+    list_del(&element->list);

使用list_del將原本指標移動的部分包裝起來，另外*node原本用來獲得element以及方便做指標的移動，用了list_del後就可以把它inline進list_entry。

q_remove_tail

Commit 1bf85d5

在佇列尾端 (tail) 移除節點

    return q_remove_head(head->prev->prev, sp, bufsize);

和q_insert_tail一樣的想法，因為是雙向"環狀"的佇列，所以可以重用q_remove_head，但要注意的是有dummy head的關係，在remove head實際上是remove head->enxt，所以要傳入的應該是head->prev->prev，不然會刪錯。

q_delete_mid

Commit c45d606

    if (!head || head->next == head)
        return false;

    struct list_head *slow = head->next;
    struct list_head *fast = head->next;

    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    slow->prev->next = slow->next;
    slow->next->prev = slow->prev;

-    element_t *element = list_entry(slow, element_t, list);
-    free(element->value);
-    free(element);
+    q_release_element(list_entry(slow, element_t, list));

    return true;

參考此連結的解法，使用快慢指標刪除中心節點，在重構時改用q_release_element移除element

q_delete_dup

Commit aa37570

     if (!head || head->next == head)
         return false;
 
-    // q_sort(head, false);  // 先排序
-
-    struct list_head *current = head->next;
-    bool has_duplicates = false;
-
-    while (current != head && current->next != head) {
-        element_t *element = list_entry(current, element_t, list);
-        element_t *next_element = list_entry(current->next, element_t, list);
-
-        if (strcmp(element->value, next_element->value) == 0) {
-            has_duplicates = true;
-            struct list_head *dup = current->next;
-            current->next = dup->next;
-            dup->next->prev = current;
-            free(next_element->value);
-            free(next_element);
-        } else {
-            if (has_duplicates) {
-                struct list_head *dup = current;
-                current = current->prev;
-                current->next = dup->next;
-                dup->next->prev = current;
-                free(element->value);
-                free(element);
-                has_duplicates = false;
-            }
-            current = current->next;
-
-    if (has_duplicates) {
-        struct list_head *dup = current;
-        current = current->prev;
-        current->next = dup->next;
-        dup->next->prev = current;
-        element_t *element = list_entry(dup, element_t, list);
-        free(element->value);
-        free(element);
-    }
-
+    struct list_head *node, *safe;
+    bool last_duplicate = false;
+
+    list_for_each_safe (node, safe, head) {
+
+        element_t *element = list_entry(node, element_t, list);
+        const element_t *element_safe = list_entry(safe, element_t, list);
+
+        if (safe != head && strcmp(element->value, element_safe->value) == 0) {
+            last_duplicate = true;
+            list_del(node);
+            q_release_element(element);
+        } else if (last_duplicate) {
+            last_duplicate = false;
+            list_del(node);
+            q_release_element(element);
         }
     }
+    
     return true;
 }

使用list_for_each_safe大幅改進了可讀性，要注意的是他只要有刪除，就要全刪，所以要用一個額外的變數last_duplicate來刪除最後一個重複的節點，此外，在比較時也要注意safe有可能會跑到dummy head，會造成進行strcmp時發生segmentation fault。

q_swap

Commit 41ea59b

    if (!head || head->next == head)
        return;

    struct list_head *current = head->next;

    while (current != head && current->next != head) {
-        struct list_head *next = current->next;
-        current->prev->next = next;
-        next->prev = current->prev;
-        current->next = next->next;
-        next->next->prev = current;
-        next->next = current;
-        current->prev = next;
         // Swap current and next
+        list_move(current, current->next);

        // Move to the next pair
        current = current->next;
    }

看了list.h後，把原本移動指標的部分包裝近list_move裡，增加可讀性。

q_reverse

反向排列佇列，但不分配或釋放節點

void q_reverse(struct list_head *head)
{
    if (!head || head->next == head)
        return;

    struct list_head *current = head;
    do {
        struct list_head *temp = current->next;
        current->next = current->prev;
        current->prev = temp;
        current = temp;
    } while (current != head);
}

有想過要使用list_move修改，但是單純交換他們的prev跟next用到list_move好像就太多餘了。
只要三次的assignment不需要用六次。

q_reverseK

Commit 224251b

+    struct list_head *node, *safe;
+    int count = 0;
+    list_for_each_safe(node, safe, head) {
+        count++;
+        if (count % k == 0) {
+            while (--count) {
+                list_move_tail(node->prev, safe);
+            }
+         }

原本寫了一個helper function，用來反轉區間內的節點順序，額外用了超過40行且很難看懂，重新畫了圖之後發現可以有更簡單的方式實作，如下：

若k=3，node當前為4，safe為5，要把順序變為1->4->3->2->5的話，
這個方法中node->prev始終要移動到safe前面，而執行的次數為k-1次，所以程式碼使用了一個巧妙的寫法，將判斷條件設為--count就可以執行k-1次，且迴圈結束count也會回到0。

q_sort

Commit 527e966

以根據descend來決定以升序/降序排序佇列節點
🔗 參考 Linked List Sort
原本使用selection sort，在研讀完merge sort後改以它實作。
用的是遞迴版的merge sort，有額外寫了兩個helper function merge 和 merge_sort，前者負責將已排序的左右半合併，後者
實作流程：

先斷開環狀結構，把head->prev->next設為NULL
把head->next以及descend傳入merge_sort
使用快慢指標將list遞迴切成左右兩半，最後回傳排序並合併後的list。
回到q_sort，由於排序過程中，僅確保next，指標是正確的，所以還需重連prev指標

    struct list_head *cur = head;
    while (cur->next) {  // reconnect prev pointer
        cur->next->prev = cur;
        cur = cur->next;
    }

最後，再將環狀結構恢復。

    cur->next = head;
    head->prev = cur;

q_descend/q_ascend

/* Remove every node which has a node with a strictly less value anywhere to
 * the right side of it */
int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || head->next == head)
        return 0;

    // From last element to first element
    struct list_head *cur = head->prev;
    const element_t *cur_elem = list_entry(cur, element_t, list);
    const char *min_val = cur_elem->value;  // keep the last element

    cur = cur->prev;
    while (cur != head) {
        // Avoid the last element is removed
        struct list_head *temp = cur->prev;
        element_t *entry = list_entry(cur, element_t, list);
        if (strcmp(entry->value, min_val) > 0) {
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            free(entry->value);
            free(entry);
        } else {
            min_val = entry->value;
        }
        cur = temp;
    }
    return q_size(head);
}

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || head->next == head)
        return 0;

    // From last element to first element
    struct list_head *cur = head->prev;
    const element_t *cur_elem = list_entry(cur, element_t, list);
    const char *max_val = cur_elem->value;  // keep the last element


    cur = cur->prev;
    while (cur != head) {
        // Avoid the last element is removed
        struct list_head *temp = cur->prev;
        element_t *entry = list_entry(cur, element_t, list);
        if (strcmp(entry->value, max_val) < 0) {
            cur->prev->next = cur->next;
            cur->next->prev = cur->prev;
            free(entry->value);
            free(entry);
        } else {
            max_val = entry->value;
        }
        cur = temp;
    }
    return q_size(head);
}

q_merge

Commit cc0c21b

第一版寫了一個helper function q_merge_two ，用於合併兩個已排序的list，但覺得兩兩合併太花時間了，特別是沒做優化時第一個list會越來越長，效率不佳。

第二版重構的方法：每次都從k個list中找到要的那個節點，然後將他移動到當前merged的最後。

    while (1) {
        queue_contex_t *entry, *best_queue = NULL;
        struct list_head *best_node = NULL;

        list_for_each_entry(entry, head, chain) {
            if (list_empty(entry->q))
                continue;

            if (!best_node) {
                best_node = entry->q->next;
                best_queue = entry;
            } else if ((strcmp(
                            list_entry(entry->q->next, element_t, list)->value,
                            list_entry(best_node, element_t, list)->value) <
                        0) ^
                       descend) {
                best_node = entry->q->next;
                best_queue = entry;
            }
        }

        if (!best_node)
            break;

        if (list_is_singular(head)) {
            list_splice_tail_init(best_queue->q, &merged);
            best_queue->size = 0;
            break;
        }

        list_move_tail(best_node, &merged);
        best_queue->size--;
    }

Valgrind +自動測試程式

研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案

在 qtest 提供新的命令 shuffle

在 qtest 中執行 option entropy 1 並搭配 ih RAND 10 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 qtest 切換不同的 PRNG 的實作 (可選定 Xorshift)，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質

研讀論文〈Dude, is my code constant time?〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。

Hw3

character device解釋

Character Device（字元裝置）

在 Linux 和 Unix 系統中，Character Device（字元裝置） 是一種類型的裝置檔案，用來表示能夠以字元（byte stream）為單位進行 I/O 操作的硬體裝置。

字元裝置的特性

不使用緩衝區（Buffering）
- 即時讀寫（Streaming）：資料是以字元（byte-by-byte）方式傳輸，而不是以固定大小的區塊（block）傳輸。
- 不支援隨機存取（Random Access）：通常無法像區塊裝置（Block Device）一樣支援 seek() 來跳轉到檔案中的某個特定位置。
範例裝置
- 終端機（TTY, /dev/tty）：負責處理鍵盤輸入和螢幕輸出。
- 序列埠（Serial Port, /dev/ttyS0）：像是 RS-232 串列埠，通常用於連接嵌入式設備或工業裝置。
- 滑鼠（Mouse, /dev/input/mice）：用來處理滑鼠輸入數據。
- 聲音裝置（Sound, /dev/snd/）：音效卡的輸入輸出介面，如 /dev/dsp（舊式）、/dev/snd/（ALSA 音效架構）。
- 隨機數產生器（Random, /dev/random, /dev/urandom）：提供隨機數給應用程式使用。

如何識別字元裝置

在 Linux 中，字元裝置會在 /dev/ 目錄下，以特殊檔案的形式存在。使用 ls -l 命令，可以看到字元裝置的類型：

ls -l /dev/tty

輸出範例：

crw-rw-rw- 1 root tty 5, 0 Mar 10 12:00 /dev/tty

c（開頭的 c 代表 Character Device）
5, 0（主設備號（Major Number） 和 次設備號（Minor Number））
- 主設備號：標識設備的類別
- 次設備號：標識同一類設備中的不同設備

如果想查看所有字元裝置，可以執行：

ls -l /dev | grep "^c"

字元裝置 vs. 區塊裝置

類型	讀寫方式	典型用途	例子
字元裝置（Character Device）	以字節為單位讀寫（流式處理），不經過緩衝	需要即時回應的設備	`/dev/tty`, `/dev/random`, `/dev/snd/`
區塊裝置（Block Device）	以區塊（block）為單位讀寫，有緩衝機制	儲存設備（支援隨機存取）	`/dev/sda`, `/dev/mmcblk0`

如何存取字元裝置

1. 使用 `cat` 或 `echo` 讀寫字元裝置

cat /dev/random  # 讀取隨機數
echo "Hello" > /dev/tty  # 在當前終端顯示 "Hello"

2. 使用 `dd` 讀取字元裝置

dd if=/dev/random bs=1 count=10  # 從 /dev/random 讀取 10 個字節

3. 使用 `stty` 設定字元裝置（例如調整終端行為）

stty -F /dev/ttyS0 speed 9600  # 設定序列埠速度為 9600 baud

結論

字元裝置（Character Device）適用於即時讀寫、流式輸入輸出、不支援隨機存取的硬體，如終端機、滑鼠、聲音裝置等。它與區塊裝置（Block Device）不同，主要是用來處理小型、即時的數據流，而不是大規模的儲存讀寫。

callback解釋

Callback（回呼函式）是什麼？

Callback（回呼函式） 是一種將函式作為參數傳遞給另一個函式，並在特定時間點或條件滿足時執行該函式的機制。

這種技術常見於：

異步編程（Asynchronous Programming）
事件驅動（Event-Driven）程式設計
系統回調（如內核驅動程式、信號處理等）

1. Callback 的基本概念

在 C 語言或其他語言中，回呼函式的核心概念是函式指標（Function Pointer），允許我們將函式的地址傳遞給其他函式，稍後再執行。

範例 1：基本 Callback（C語言）

c
複製編輯
#include <stdio.h>// 定義一個函式作為回呼函式
void my_callback_function() {
    printf("這是回呼函式被執行！\n");
}

// 接收函式指標作為參數
void execute_callback(void (*callback)()) {
    printf("開始執行 callback...\n");
    callback();  // 呼叫回呼函式
    printf("結束 callback\n");
}

int main() {
    execute_callback(my_callback_function);
    return 0;
}

輸出結果

複製編輯
開始執行 callback...
這是回呼函式被執行！
結束 callback

在這個例子中：

my_callback_function() 是一個普通函式。
execute_callback() 接收一個函式指標，並在適當的時機執行該函式。

2. 為什麼要使用 Callback？

（1）提高靈活性

允許我們將不同的函式傳遞給相同的函式來執行，增強可重用性。

（2）適用於異步處理（Asynchronous Processing）

適用於事件驅動架構，如 GUI 程式設計、非同步 I/O 操作。

（3）適用於系統開發（Kernel、驅動程式）

內核函式可能會在某些條件滿足時呼叫驅動程式的回呼函式。

3. 進階 Callback：傳遞參數

c
複製編輯
#include <stdio.h>// 回呼函式定義，接受一個 int 參數
void my_callback_function(int num) {
    printf("回呼函式執行，數值為: %d\n", num);
}

// 主要函式，接受函式指標和參數
void execute_callback(void (*callback)(int), int value) {
    printf("開始執行 callback...\n");
    callback(value);  // 呼叫回呼函式，傳遞 value
    printf("結束 callback\n");
}

int main() {
    execute_callback(my_callback_function, 42);
    return 0;
}

輸出結果

makefile
複製編輯
開始執行 callback...
回呼函式執行，數值為: 42
結束 callback

這裡 execute_callback() 可以接收不同的回呼函式，並將 value 作為參數傳遞。

4. Callback 在實際應用中的例子

（1）C 語言的 `qsort()` 函式

標準函式 qsort() 使用回呼函式來決定排序方式：

c
複製編輯
#include <stdio.h>#include <stdlib.h>// 比較函式（回呼函式）
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int arr[] = {5, 2, 9, 1, 6};
    int size = sizeof(arr) / sizeof(arr[0]);

    // 使用 qsort 排序，並傳遞 compare() 作為回呼函式
    qsort(arr, size, sizeof(int), compare);

    // 印出排序後的數組
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

這裡 compare() 作為回呼函式，提供 qsort() 排序時的比較規則。

（2）Linux 信號處理（Signal Handling）

c
複製編輯
#include <stdio.h>#include <signal.h>// 回呼函式，處理 SIGINT（Ctrl+C）
void signal_handler(int signum) {
    printf("收到訊號 %d，程式終止。\n", signum);
    exit(0);
}

int main() {
    signal(SIGINT, signal_handler);  // 設定回呼函式
    while (1) {}  // 無窮迴圈，等待訊號
    return 0;
}

這裡 signal_handler() 是當 SIGINT（Ctrl+C）被觸發時，系統會執行的回呼函式。

5. 結論

回呼函式（Callback） 是一種將函式指標作為參數傳遞並稍後執行的技術。
常用於異步處理、事件驅動系統、排序函式、信號處理、內核驅動等領域。
透過函式指標，可以讓程式更加模組化、靈活且可擴展。

這種技巧在 C、C++、Python、JavaScript 等語言中都廣泛使用！

vtable(virtual table)->polymorphism vs virtual function

C++ 的 vtable（Virtual Table）、多型（Polymorphism）與虛擬函式（Virtual Function）

在 C++ 中，虛擬函式（Virtual Function） 和 多型（Polymorphism） 是物件導向程式設計（OOP）的核心概念，而 vtable（虛擬函式表） 則是其底層的實作機制之一。

1. 虛擬函式（Virtual Function）

在 C++ 中，如果一個基類的函式被標記為 virtual，則在繼承該類的派生類別中，可以覆寫這個函式，而函式調用會根據物件的實際類型（runtime type）決定，而非變數的靜態類型（compile-time type）。

範例：虛擬函式

cpp
複製編輯
#include <iostream>class Base {
public:
    virtual void show() {  // 虛擬函式
        std::cout << "Base 類別的 show()\n";
    }
};

class Derived : public Base {
public:
    void show() override {  // 覆寫基類函式
        std::cout << "Derived 類別的 show()\n";
    }
};

int main() {
    Base* ptr = new Derived();
    ptr->show();  // 這裡會執行 Derived::show()

    delete ptr;
    return 0;
}

輸出結果

scss
複製編輯
Derived 類別的 show()

這裡 ptr->show(); 會根據 ptr 指向的實際物件類型 Derived 來決定呼叫 Derived::show()，這就是多型（Polymorphism）。

2. 多型（Polymorphism）

多型是一種在相同介面下能夠表現出不同行為的機制，C++ 支援編譯時多型（Compile-time Polymorphism） 和 執行時多型（Runtime Polymorphism）。

（1）編譯時多型（Compile-time Polymorphism）

這種多型發生在編譯階段，像是函式重載（Function Overloading） 和 模板（Templates）：

cpp
複製編輯
#include <iostream>// 函式重載
void show(int x) {
    std::cout << "整數: " << x << std::endl;
}

void show(double x) {
    std::cout << "浮點數: " << x << std::endl;
}

int main() {
    show(10);    // 呼叫 show(int)
    show(3.14);  // 呼叫 show(double)
    return 0;
}

（2）執行時多型（Runtime Polymorphism）

這種多型發生在程式執行階段（Runtime），是透過虛擬函式來實現的：

cpp
複製編輯
#include <iostream>class Animal {
public:
    virtual void speak() { std::cout << "動物發出聲音\n"; }
};

class Dog : public Animal {
public:
    void speak() override { std::cout << "狗叫：汪汪！\n"; }
};

int main() {
    Animal* pet = new Dog();
    pet->speak();  // 執行 Dog::speak()，因為是虛擬函式
    delete pet;
    return 0;
}

這裡 speak() 的行為會根據物件的實際類型決定，而非變數類型，這就是執行時多型的特點。

3. vtable（虛擬函式表）

vtable（Virtual Table，虛擬函式表） 是 C++ 虛擬函式的底層實現方式，當一個類別內含至少一個虛擬函式時，編譯器會為這個類別生成一個vtable，它是一個函式指標的陣列，儲存該類別所有虛擬函式的地址。

vtable 的工作方式

每個有虛擬函式的類別都有一個 vtable（存放虛擬函式指標的陣列）。
每個物件都有一個 vptr（虛擬函式表指標，Virtual Table Pointer），指向該類別的 vtable。
當呼叫虛擬函式時，會透過 vptr 查找對應的函式地址，並執行正確的函式。

vtable 的運作示意圖

假設有以下類別：

cpp
複製編輯
class Base {
public:
    virtual void func1() { std::cout << "Base::func1\n"; }
    virtual void func2() { std::cout << "Base::func2\n"; }
};

class Derived : public Base {
public:
    void func1() override { std::cout << "Derived::func1\n"; }
};

這時候，編譯器會產生以下 vtable：

Base 類別的 vtable

lua
複製編輯
+--------+
| func1  | --> Base::func1
| func2  | --> Base::func2
+--------+

Derived 類別的 vtable

lua
複製編輯
+--------+
| func1  | --> Derived::func1  (覆寫)
| func2  | --> Base::func2     (繼承)
+--------+

當程式執行 Base* obj = new Derived(); 時：

obj->func1(); 會透過 vtable 找到 Derived::func1()
obj->func2(); 會透過 vtable 找到 Base::func2()

4. vtable 與虛擬函式的代價

使用虛擬函式雖然提供了多型，但也帶來了一些額外的開銷：

函式呼叫透過 vtable，會有間接尋址的開銷（比一般函式呼叫稍慢）。
每個有虛擬函式的類別會有額外的 vtable 開銷。
每個物件都會有一個額外的 vptr 指標（通常是 8 Bytes，在 64 位元系統上）。

在效能關鍵的應用（如遊戲、嵌入式系統）中，過度使用虛擬函式可能會影響執行速度，因此在設計類別時需權衡取捨。

5. 總結

概念	作用
虛擬函式（Virtual Function）	允許子類別覆寫函式，並透過基類指標/參考在執行時動態決定要執行哪個函式。
多型（Polymorphism）	讓不同類別的物件可以透過相同介面（基類）執行不同的行為。
vtable（虛擬函式表）	編譯器用來實作虛擬函式的機制，是一個函式指標陣列，物件透過 vptr 指向該類別的 vtable 來動態決定函式呼叫。

在 C++ 中，當我們使用 virtual 關鍵字時，實際上就是讓編譯器為這個類別建立 vtable，並透過 vptr 來動態解析函式調用，以達到執行時的多型（Runtime Polymorphism）。

cache, IPl （inter-processor interrupt）， page fault, interrupts, rescheduling

1. Cache（快取記憶體）

快取記憶體（Cache） 是 CPU 內部或與 CPU 緊密相連的高速記憶體，用來加速 CPU 存取資料，減少訪問主記憶體（RAM）的頻率，提升系統效能。

Cache 層級

現代 CPU 的快取一般分為多個層級：

L1 Cache（Level 1）：每個核心專屬，速度最快，容量最小（幾十 KB）。
L2 Cache（Level 2）：每個核心專屬或多個核心共享，容量較大（數百 KB）。
L3 Cache（Level 3）：多個核心共享，速度較慢，容量更大（幾 MB）。

Cache 作用

當 CPU 需要存取某個資料時：

查詢 L1 Cache，若命中（Cache Hit），則直接讀取。
若未命中，則查詢 L2 Cache，若命中則讀取。
若仍未命中，則查詢 L3 Cache，若還未命中，則從主記憶體（RAM）讀取（Cache Miss）。
讀取到的資料會存入 Cache，以便下次存取時加速。

缺點：

若資料未命中 Cache（Cache Miss），則需要存取較慢的 RAM，甚至更慢的磁碟（若涉及虛擬記憶體）。

2. IPI（Inter-Processor Interrupt，處理器間中斷）

IPI（處理器間中斷） 是一種特殊的 CPU 中斷，允許多核心處理器（SMP 系統）之間相互通知或同步。

IPI 的用途

喚醒處理器：讓閒置的 CPU 核心開始工作。
重新分配工作（Rescheduling）：讓某些執行緒轉移到其他 CPU 核心執行。
快取同步（Cache Coherency）：確保多核心 CPU 間的 Cache 資料一致性。
TLB（Translation Lookaside Buffer）同步：當某核心更新分頁表（Page Table），需要通知其他核心刷新 TLB 快取。

IPI 的運作

當一個 CPU 核心發送 IPI 給另一個核心時，目標核心的中斷控制器（APIC）會接收 IPI，然後觸發處理 IPI 的中斷服務程序（ISR）。
Linux 內核的 smp_call_function() 就是用來發送 IPI 的機制之一。

3. Page Fault（分頁錯誤）

Page Fault（分頁錯誤） 發生在 CPU 嘗試存取不在記憶體（RAM）中的頁面時，由作業系統（OS）來處理並載入該頁面。

Page Fault 的種類

Minor Page Fault（次級分頁錯誤）
- 頁面已經在 RAM 內，但沒有映射到進程的地址空間（可能是因為換頁表未設置）。
- 例如，共享記憶體的頁面，可能需要 OS 建立適當的映射。
Major Page Fault（主要分頁錯誤）
- 需要從磁碟（如 swap 空間或 mmap 檔案）載入缺失的頁面到記憶體。
- 代價較高，因為涉及磁碟 I/O。
Invalid Page Fault（無效分頁錯誤）
- 進程存取了非法的記憶體區域（例如存取 NULL 指標）。
- 這通常會導致 Segmentation Fault（段錯誤，SIGSEGV）。

處理流程

CPU 產生 Page Fault
OS 查詢頁表（Page Table）
- 如果該頁面有效但尚未載入 → 從磁碟載入頁面（可能會導致 Major Page Fault）。
- 如果該頁面無效 → 發送 SIGSEGV 訊號給進程，導致崩潰（Segmentation Fault）。

4. Interrupts（中斷）

中斷（Interrupts） 是一種 CPU 打斷當前執行流程，處理特定事件的機制。

中斷的類型

硬體中斷（Hardware Interrupts）
- 由外部設備觸發，如鍵盤、滑鼠、磁碟 I/O、網路請求。
- 例如：
  - 鍵盤按下 Enter，產生鍵盤中斷（IRQ）。
  - 磁碟完成 I/O，通知 CPU 讀取資料。
軟體中斷（Software Interrupts）
- 由軟體觸發，如 syscall（系統呼叫）。
- 例如：
  - int 0x80（Linux 的舊式系統呼叫方式）。
  - syscall 指令（現代 x86-64 使用）。
異常（Exceptions）
- 由 CPU 自行觸發，如：
  - 除零錯誤（Divide by Zero）。
  - Page Fault（分頁錯誤）。
  - 違反存取（Segmentation Fault）。

中斷處理流程

CPU 儲存當前執行狀態
跳轉到對應的中斷處理函式（Interrupt Service Routine, ISR）
ISR 完成後，恢復原本的執行狀態，繼續執行程式

5. Rescheduling（重新排程）

重新排程（Rescheduling） 指的是作業系統根據 CPU 排程策略，將 CPU 執行權移交給不同的進程（Process）或執行緒（Thread）。

Rescheduling 何時發生？

時間片（Time Slice）結束
- 在多工系統中，每個進程獲得的 CPU 時間有限，當時間片用完時，OS 會執行 上下文切換（Context Switch），讓其他進程執行。
進程進入等待狀態（Blocked）
- 例如，當進程等待 I/O 操作完成時，OS 會將 CPU 分配給其他可執行的進程。
進程被手動 sleep()
- 如果進程執行 sleep(5)，OS 會將它從 CPU 移除，並在 5 秒後重新加入執行隊列。
高優先權的進程需要執行
- 如果有更高優先權的進程準備好執行，OS 可能會搶佔當前進程，強制重新排程。

Rescheduling 的影響

提升系統效能：讓 CPU 資源更有效率地分配。
支援多工（Multitasking）：讓多個應用程式同時執行。
影響延遲（Latency）：如果排程策略不佳，可能會造成程式的回應延遲。

結論

概念	作用
Cache（快取）	加速 CPU 存取記憶體，減少 RAM 存取次數。
IPI（處理器間中斷）	讓多核 CPU 互相通訊，用於同步與工作分配。
Page Fault（分頁錯誤）	CPU 存取未載入記憶體的頁面，OS 需載入或終止進程。
Interrupts（中斷）	暫停當前程式執行，以處理更高優先級的事件（如 I/O）。
Rescheduling（重新排程）	根據 CPU 排程策略，將執行權交給不同的進程或執行緒。

這些機制共同協作，確保現代電腦系統能夠有效運作。 🚀

PMIC(power management integrated circuit

PMIC（Power Management Integrated Circuit，電源管理整合電路）

1. PMIC 是什麼？

PMIC（Power Management Integrated Circuit，電源管理整合電路）是一種專門用來管理電子設備電源的整合電路（IC）。它負責調節、轉換、分配和監控電源，確保系統能夠高效、安全地運作。

PMIC 通常應用於：

智慧型手機、平板電腦、筆記型電腦
嵌入式系統（IoT、MCU、DSP）
電動車（EV）、可攜式裝置（如穿戴設備）
伺服器與網路設備

2. PMIC 的主要功能

PMIC 負責多種電源管理工作，以下是主要功能：

（1）電壓調節（Voltage Regulation）

透過 DC-DC 轉換器 或 LDO（低壓降穩壓器） 來穩定供應電壓。
例如，將 5V USB 轉換為 3.3V 或 1.8V 供應 MCU、FPGA、SoC 使用。

（2）電源切換（Power Switching）

控制不同電源輸出的開關，確保系統能夠根據需求分配電能，並支援多電壓系統。

（3）電池管理（Battery Management）

監控電池電壓、電流、溫度，確保安全充電與放電。
支援充電控制（Battery Charging），如 鋰離子電池（Li-Ion）管理。
例如 BQ24195 是一款常見的 PMIC，專門管理鋰電池充放電。

（4）能耗管理（Power Efficiency）

透過低功耗模式（Low Power Mode）、睡眠模式（Sleep Mode）來降低能耗，延長電池壽命。
常用於 行動裝置、IoT 設備，減少功耗並提升效能。

（5）過壓/過流/過熱保護（Protection Circuits）

防止電源突波、短路、過熱等情況損壞設備。
內建 過壓（OVP）、過流（OCP）、過溫（OTP）保護機制。

（6）時鐘管理（Clock Management）

某些 PMIC 內建 時鐘產生器（Clock Generator），提供時脈給 MCU 或處理器。

（7）電源狀態監測（Power Monitoring）

透過 I²C、SPI 或 GPIO 介面，回報電壓、電流等數據給主機處理器（如 SoC）。
幫助系統在電源異常時進行適當應對，如警報或安全關機。

3. PMIC 的種類

根據應用場景，PMIC 可以分為不同類型：

類型	主要功能	應用
電池管理 PMIC	負責鋰電池充放電、保護與監控	智慧手機、筆電、可攜設備
DC-DC 轉換 PMIC	提供高效率電壓轉換（Buck、Boost 轉換器）	物聯網、嵌入式設備
LDO 穩壓 PMIC	提供低雜訊的線性穩壓輸出	高精度電子裝置（音訊、RF 產品）
電源開關 PMIC	控制多個電源輸入與輸出	汽車電子、伺服器
電流監測 PMIC	監測功耗並提供 I²C/SPI 回報	伺服器、資料中心

4. PMIC 應用範例

（1）智慧型手機中的 PMIC

在手機 SoC（如 Qualcomm Snapdragon、Apple A 系列處理器）中，PMIC 負責：

提供 1.8V / 3.3V 給處理器、記憶體、顯示器。
管理 USB 充電（5V to 4.2V 鋰電池）。
監控溫度，避免過熱。

常見的手機 PMIC：

Qualcomm PM8998（Snapdragon）
TI BQ25895（快充電池管理）

（2）樹莓派（Raspberry Pi）的 PMIC

樹莓派使用 PMIC 來：

將 5V USB 電源轉換為 3.3V、1.8V。
透過 I²C 介面監測電壓與溫度。
例如 MaxLinear MxL7704 是 Raspberry Pi 4 的 PMIC。

（3）電動車（EV）中的 PMIC

電動車（如 Tesla）內的 PMIC 負責：

管理 高壓電池（400V-800V）轉換為低壓 12V/5V。
提供電源給 ADAS（自動駕駛系統）、ECU（車輛控制單元）。
例如 Texas Instruments TPS65987D 是一款支援 USB-C 電源傳輸（PD）的 PMIC。

5. 總結

特色	內容
PMIC 作用	管理電源轉換、電池充電、電壓調節、保護機制等
主要功能	DC-DC 轉換、LDO 穩壓、電池管理、過壓/過流保護、監測功耗
應用領域	智慧型手機、IoT、伺服器、電動車
常見 PMIC	Qualcomm PM8998、TI BQ25895、MxL7704

PMIC 在現代電子設備中至關重要，確保能源管理高效、安全且可靠，特別是在電池供電的設備（如手機、IoT 裝置）中更是不可或缺！ 🚀

WFI/WFE(wait for interrupt/event)

WFI / WFE（Wait For Interrupt / Wait For Event）

WFI（Wait For Interrupt） 和 WFE（Wait For Event） 是 ARM 架構中兩個低功耗指令，主要用來讓 CPU 進入低功耗狀態，等待**中斷（Interrupt）或事件（Event）**發生後再繼續執行。

這些指令常用於嵌入式系統、作業系統的省電模式、低功耗微控制器（MCU）等應用，可以顯著降低功耗並提升系統效能。

1. WFI（Wait For Interrupt）

WFI 指令的作用：

讓 CPU 進入低功耗模式，直到接收到中斷（Interrupt）時才繼續執行。
適用於處理器等待外部或內部中斷發生，類似於 sleep()。
一旦中斷發生，CPU 會恢復執行。

WFI 工作流程

CPU 執行 WFI 指令，進入低功耗狀態（例如睡眠模式）。
CPU 暫停執行，並等待中斷（如 Timer IRQ、GPIO IRQ）。
一旦中斷發生，CPU 退出低功耗狀態，繼續執行後續指令。

WFI 的優勢

減少 CPU 的功耗，因為在等待中斷時 CPU 停止執行指令，降低電力消耗。
適用於 需要中斷觸發的應用，如定時喚醒、事件驅動系統。

WFI 使用範例（C / ARM Assembly）

ARM 組語

assembly
複製編輯
    WFI   ; CPU 進入低功耗模式，直到有中斷發生

C 語言（CMSIS for Cortex-M）

c
複製編輯
#include "core_cm4.h" // Cortex-M4 CMSIS Headervoid enter_low_power_mode() {
    __WFI();  // 讓 CPU 進入低功耗狀態，等待中斷
}

這段程式碼會讓 MCU 進入低功耗狀態，直到發生中斷（例如按鍵、定時器觸發）。

2. WFE（Wait For Event）

WFE 指令的作用：

讓 CPU 進入低功耗模式，直到有「事件（Event）」發生。
事件可以來自中斷（Interrupt）或顯式事件通知（SEV 指令）。
適用於 多核（SMP）系統，其中一個核心可以喚醒另一個核心。

WFE 與 WFI 的不同

指令	觸發條件	應用場景
WFI	只有「中斷（Interrupt）」才能喚醒 CPU	適合低功耗模式，直到有中斷發生
WFE	中斷（Interrupt）或事件（Event）都能喚醒 CPU	適合多核心（SMP）系統，透過 `SEV` 來喚醒其他核心

WFE 工作流程

CPU 執行 WFE，進入低功耗模式，等待事件發生。
事件來源：
- 硬體中斷（如 Timer IRQ）。
- 其他 CPU 核心執行 SEV 指令。
一旦有事件發生，CPU 會退出低功耗狀態並繼續執行。

WFE 的優勢

可用於 多處理器（Multi-Core）架構，允許一個 CPU 喚醒另一個 CPU。
支援等待中斷與等待事件，使得應用更靈活。

WFE 使用範例

ARM 組語

assembly
複製編輯
    WFE   ; CPU 進入低功耗狀態，直到發生事件

C 語言（CMSIS for Cortex-M）

c
複製編輯
#include "core_cm4.h"void enter_event_waiting_mode() {
    __WFE();  // 等待事件發生
}

這段程式碼會讓 CPU 進入低功耗模式，直到有事件（如 SEV 指令或中斷）發生。

3. SEV（Set Event）—— 配合 WFE 使用

SEV（Set Event）是一個 ARM 指令，用來產生事件，通常配合 WFE 來實現核心間同步。

SEV 使用場景

多核心（SMP）系統：一個核心可以使用 SEV 來喚醒另一個執行 WFE 的核心。
主從架構（Master-Slave）：主核心（主 CPU）發送 SEV 指令來喚醒副核心（從 CPU）。

SEV 使用範例

ARM 組語

assembly
複製編輯
    SEV   ; 發送事件，喚醒執行 WFE 的 CPU

C 語言

c
複製編輯
#include "core_cm4.h"void trigger_event() {
    __SEV();  // 觸發事件，讓執行 WFE 的 CPU 醒來
}

這段程式碼讓執行 WFE 的 CPU 退出低功耗狀態並繼續執行。

4. WFI/WFE 在作業系統（OS）中的應用

WFI 和 WFE 在 RTOS（即時作業系統） 或 Linux 內核 中有許多應用：

（1）Linux 低功耗模式

在 ARM 架構的 Linux 中，當 CPU 進入閒置狀態時，Linux 內核會自動執行 WFI 或 WFE 來降低功耗：

arch_cpu_idle() 內部會執行 WFI，使 CPU 進入睡眠模式。
當有新的排程或 IRQ 發生時，CPU 會被喚醒。

（2）RTOS 任務調度

在 FreeRTOS、Zephyr 等即時作業系統中：

當任務進入 阻塞狀態（Blocked），CPU 會執行 WFI/WFE，減少不必要的功耗。
當任務準備好執行時，系統透過中斷來喚醒 CPU。

（3）多核心同步

在 SMP（對稱多處理）系統 中：

一個 CPU 使用 WFE() 進入等待狀態。
另一個 CPU 在準備好時，透過 SEV() 喚醒等待的 CPU。

5. 總結

指令	作用	何時喚醒 CPU	應用
WFI（Wait For Interrupt）	進入低功耗模式，等待中斷	中斷發生時	省電模式、OS 低功耗管理
WFE（Wait For Event）	進入低功耗模式，等待中斷或事件	中斷或 SEV 事件發生時	多核心同步、事件驅動系統
SEV（Set Event）	觸發事件，讓 `WFE` 喚醒	發送事件後	核心間同步（SMP 系統）

這些指令對於 低功耗系統設計、嵌入式系統、作業系統（OS）調度、多核心處理器 都非常重要。合理使用這些指令可以降低功耗並提升系統效率！ 🚀

你說：

wake up process是什麼

ChatGPT 說：

Wake Up Process（喚醒進程）

Wake Up Process（喚醒進程） 是指作業系統（OS）從「睡眠狀態（Sleeping）」或「等待狀態（Blocked）」中喚醒一個進程（Process）或執行緒（Thread），使其重新進入「可執行狀態（Runnable）」的過程。

這個機制在多工作業系統（如 Linux、Windows、RTOS）中至關重要，因為進程和執行緒在沒有事件發生時通常會進入休眠，以節省 CPU 資源。當某個事件（如 I/O 完成、訊號發生、中斷等）發生時，OS 會喚醒相應的進程，使其恢復執行。

1. 進程的狀態（Process States）

在 Linux 內核（以及大多數作業系統）中，進程有幾種不同的狀態：

Running（執行中）：進程正在 CPU 上運行。
Runnable（可執行）：進程已準備好執行，但尚未獲得 CPU 時間。
Sleeping（睡眠中）
- Interruptible Sleep（可中斷睡眠）：進程在等待某個事件（如 I/O 完成），可以被訊號（Signal）或中斷（Interrupt）喚醒。
- Uninterruptible Sleep（不可中斷睡眠）：進程等待某些關鍵資源，通常不會被打斷（如等待磁碟 I/O）。
Stopped（停止）：進程被暫停（如 SIGSTOP）。
Zombie（殭屍）：進程已終止，但仍佔據進程表條目，等待父進程回收。

當一個進程處於 Sleeping（睡眠狀態），而某個事件發生時，OS 透過 Wake Up Process 機制將該進程從「睡眠狀態」轉為「可執行狀態」。

2. Wake Up Process 何時發生？

（1）I/O 完成時

當進程在等待某個 I/O 操作完成時，它會進入 可中斷睡眠狀態（TASK_INTERRUPTIBLE）。當 I/O 完成時，驅動程式或內核會喚醒該進程，使其回到 可執行狀態（Runnable），等待 CPU 調度。

範例：進程等待 I/O

c
複製編輯
#include <stdio.h>#include <unistd.h>#include <fcntl.h>int main() {
    int fd = open("test.txt", O_RDONLY);
    if (fd < 0) {
        perror("open failed");
        return 1;
    }

    char buf[100];
    printf("進程進入睡眠，等待 I/O...\n");
    ssize_t n = read(fd, buf, sizeof(buf));  // 進程會進入睡眠，直到 I/O 完成
    printf("I/O 完成，進程被喚醒，讀取到 %zd 個字節。\n", n);

    close(fd);
    return 0;
}

當 read() 嘗試讀取檔案時，如果沒有可用資料，進程會進入 睡眠狀態，直到 I/O 完成後被內核喚醒。

（2）訊號（Signal）觸發

當進程收到訊號（如 SIGUSR1），若它正在睡眠，則可以被喚醒。

範例：使用 `kill` 來喚醒進程

c
複製編輯
#include <stdio.h>#include <signal.h>#include <unistd.h>void signal_handler(int sig) {
    printf("收到訊號 %d，進程被喚醒！\n", sig);
}

int main() {
    signal(SIGUSR1, signal_handler);
    printf("進程進入睡眠狀態...\n");
    pause();  // 進程進入睡眠，直到收到訊號
    printf("進程恢復執行。\n");
    return 0;
}

執行後，在另一個終端執行：

bash
複製編輯
kill -USR1 <進程 PID>

這將發送 SIGUSR1 訊號，喚醒該進程。

（3）互斥鎖（Mutex）與條件變數（Condition Variable）

當一個執行緒等待某個資源（如互斥鎖），它會進入 等待狀態（Blocked），直到其他執行緒釋放資源並喚醒它。

範例：使用 `pthread_cond_wait()`

c
複製編輯
#include <stdio.h>#include <pthread.h>#include <unistd.h>pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

void* thread_func(void* arg) {
    pthread_mutex_lock(&lock);
    printf("執行緒進入睡眠，等待條件變數...\n");
    pthread_cond_wait(&cond, &lock);  // 進入等待狀態
    printf("執行緒被喚醒，繼續執行！\n");
    pthread_mutex_unlock(&lock);
    return NULL;
}

int main() {
    pthread_t t;
    pthread_create(&t, NULL, thread_func, NULL);

    sleep(2);  // 模擬某個事件發生
    printf("主執行緒發送信號，喚醒子執行緒！\n");
    pthread_cond_signal(&cond);  // 喚醒等待中的執行緒

    pthread_join(t, NULL);
    return 0;
}

當執行緒執行 pthread_cond_wait() 時，它會進入睡眠，直到 pthread_cond_signal() 被觸發。

3. Linux 內核中的 `wake_up()`

在 Linux 內核中，wake_up() 是喚醒進程的主要函式，用來通知某個 等待隊列（Wait Queue） 上的進程，使其從 睡眠狀態 轉為 可執行狀態。

`wake_up()` 內部機制

wake_up_process()
- 直接將進程的狀態設為 TASK_RUNNING，使其可以被 CPU 排程。
wake_up()
- wake_up() 會喚醒所有等待特定條件的進程。

內核範例

c
複製編輯
void some_event_handler() {
    wake_up(&some_wait_queue);  // 喚醒在等待隊列上的進程
}

這種機制常用於驅動程式，如當某個 I/O 操作完成時，內核會調用 wake_up() 來喚醒等待的進程。

4. 總結

觸發條件	喚醒方法	應用場景
I/O 完成	內核自動喚醒	`read()`、`write()` 等
訊號發送（Signal）	`kill()`, `SIGUSR1`	進程間通訊
條件變數（Condition Variable）	`pthread_cond_signal()`	執行緒同步
計時器（Timer）	`alarm()`, `usleep()`	定時喚醒進程
Linux 內核 `wake_up()`	內核 API	驅動程式、設備管理

Wake Up Process 是作業系統內部的重要機制，確保進程不會一直佔用 CPU，而是在需要時才被喚醒，以提高系統效率並降低功耗。 🚀

2025q1 Homework1 (lab0)

開發環境

針對佇列操作的程式碼實作

結構、函式解釋

q_new

q_free

q_size

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_descend/q_ascend

q_merge

Valgrind +自動測試程式

研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案

在 qtest 提供新的命令 shuffle

研讀論文〈Dude, is my code constant time?〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student's t-distribution 及程式實作的原理。

Hw3

Character Device（字元裝置）

字元裝置的特性

如何識別字元裝置

字元裝置 vs. 區塊裝置

如何存取字元裝置

1. 使用 cat 或 echo 讀寫字元裝置

2. 使用 dd 讀取字元裝置

3. 使用 stty 設定字元裝置（例如調整終端行為）

結論

Callback（回呼函式）是什麼？

1. Callback 的基本概念

範例 1：基本 Callback（C語言）

輸出結果

2. 為什麼要使用 Callback？

3. 進階 Callback：傳遞參數

輸出結果

4. Callback 在實際應用中的例子

（1）C 語言的 qsort() 函式

（2）Linux 信號處理（Signal Handling）

5. 結論

C++ 的 vtable（Virtual Table）、多型（Polymorphism）與虛擬函式（Virtual Function）

1. 虛擬函式（Virtual Function）

範例：虛擬函式

輸出結果

2. 多型（Polymorphism）

（1）編譯時多型（Compile-time Polymorphism）

（2）執行時多型（Runtime Polymorphism）

3. vtable（虛擬函式表）

vtable 的工作方式

vtable 的運作示意圖

Base 類別的 vtable

Derived 類別的 vtable

4. vtable 與虛擬函式的代價

5. 總結

1. Cache（快取記憶體）

Cache 層級

Cache 作用

2. IPI（Inter-Processor Interrupt，處理器間中斷）

IPI 的用途

IPI 的運作

3. Page Fault（分頁錯誤）

Page Fault 的種類

處理流程

4. Interrupts（中斷）

中斷的類型

中斷處理流程

5. Rescheduling（重新排程）

Rescheduling 何時發生？

Rescheduling 的影響

結論

PMIC（Power Management Integrated Circuit，電源管理整合電路）

1. PMIC 是什麼？

2. PMIC 的主要功能

（1）電壓調節（Voltage Regulation）

（2）電源切換（Power Switching）

（3）電池管理（Battery Management）

1. 使用 `cat` 或 `echo` 讀寫字元裝置

2. 使用 `dd` 讀取字元裝置

3. 使用 `stty` 設定字元裝置（例如調整終端行為）

（1）C 語言的 `qsort()` 函式

範例：使用 `kill` 來喚醒進程

範例：使用 `pthread_cond_wait()`

3. Linux 內核中的 `wake_up()`

`wake_up()` 內部機制

2025 linux核心設計 5/30 一對一討論問題回答