# 2025q1 Homework1 ([lab0](https://github.com/willy-liu/lab0-c))
contributed by < `willy-liu` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```bash
$ 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
```
## 針對佇列操作的程式碼實作
:::spoiler 觀念釐清
### 結構、函式解釋
`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](https://github.com/willy-liu/lab0-c/commit/9ab5ddfc4a036179d7d88c0db3889b8f77a75d84)
建立新的「空」佇列
```diff
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](https://github.com/willy-liu/lab0-c/commit/360896c88ed062f1f266e4ae85312aba34994641)
釋放佇列所佔用的記憶體
```diff
- 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`的巨集裡查看，如下
```c
#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`定義為
```c
#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等指令)
```diff
+# 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](https://github.com/willy-liu/lab0-c/commit/03f6e38d534eb8a4306bd0e8e5475a7eba9df599)
計算目前佇列的節點總量
```diff
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](https://github.com/willy-liu/lab0-c/commit/51562f75840ace85d40bca6222b47a5ed5f501cf)
在佇列開頭 (`head`) 插入新節點（LIFO 準則）
```c
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;
}
```
```diff
- 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](https://github.com/willy-liu/lab0-c/commit/51562f75840ace85d40bca6222b47a5ed5f501cf)
在佇列尾端 (`tail`) 插入新節點（FIFO 準則）
```diff
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](https://github.com/willy-liu/lab0-c/commit/1bf85d5a8ccf53223c9c6ba01dd41e79edcb2279)
在佇列開頭 (`head`) 移除節點
```diff
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](https://github.com/willy-liu/lab0-c/commit/1bf85d5a8ccf53223c9c6ba01dd41e79edcb2279)
在佇列尾端 (`tail`) 移除節點
```C
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](https://github.com/willy-liu/lab0-c/commit/c45d606a09b59ed123a3d00377d2e99e679d9f32)
```diff
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;
```
參考此[連結](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/solutions/1612140/one-pass-slow-and-fast)的解法，使用快慢指標刪除中心節點，在重構時改用`q_release_element`移除element
### q_delete_dup
Commit [aa37570](https://github.com/willy-liu/lab0-c/commit/aa37570707bda75675d22fceeacafc03e60f90d7)
```diff
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](https://github.com/willy-liu/lab0-c/commit/41ea59b591226c77b142c3cffac63292ebf0ba78)
```diff
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
**反向排列**佇列，**但不分配或釋放節點**
```c
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](https://github.com/willy-liu/lab0-c/commit/224251b4164df3ee41c1c0a84d1dc5b23eab68e5)
```diff
+ 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](https://github.com/willy-liu/lab0-c/commit/527e9662c01eb23760cf7a4cc3304825afe79166)
以根據`descend`來決定以升序/降序排序佇列節點
🔗 參考 **[Linked List Sort](https://www.geeksforgeeks.org/merge-sort-for-linked-list/)**
原本使用selection sort，在研讀完merge sort後改以它實作。
用的是遞迴版的merge sort，有額外寫了兩個helper function `merge` 和 `merge_sort`，前者負責將已排序的左右半合併，後者
實作流程：
1. 先斷開環狀結構，把`head->prev->next`設為`NULL`
2. 把`head->next`以及`descend`傳入`merge_sort`
3. 使用快慢指標將list遞迴切成左右兩半，最後回傳排序並合併後的list。
4. 回到`q_sort`，由於排序過程中，僅確保`next`，指標是正確的，所以還需重連`prev`指標
```C
struct list_head *cur = head;
while (cur->next) { // reconnect prev pointer
cur->next->prev = cur;
cur = cur->next;
}
```
5. 最後，再將環狀結構恢復。
```C
cur->next = head;
head->prev = cur;
```
### q_descend/q_ascend
```c
/* 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](https://github.com/willy-liu/lab0-c/commit/cc0c21bed88b533d2b4d3113c27a60827b1ef72b)
第一版寫了一個helper function `q_merge_two` ，用於合併兩個已排序的list，但覺得兩兩合併太花時間了，特別是沒做優化時第一個list會越來越長，效率不佳。
第二版重構的方法：每次都從k個list中找到要的那個節點，然後將他移動到當前merged的最後。
```C
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
:::spoiler character device解釋
### **Character Device（字元裝置）**
在 Linux 和 Unix 系統中，**Character Device（字元裝置）** 是一種類型的裝置檔案，用來表示能夠**以字元（byte stream）為單位進行 I/O 操作的硬體裝置**。
---
### **字元裝置的特性**
1. **不使用緩衝區（Buffering）**
- **即時讀寫（Streaming）**：資料是以字元（byte-by-byte）方式傳輸，而不是以固定大小的區塊（block）傳輸。
- **不支援隨機存取（Random Access）**：通常無法像區塊裝置（Block Device）一樣支援 `seek()` 來跳轉到檔案中的某個特定位置。
2. **範例裝置**
- **終端機（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` 命令，可以看到字元裝置的類型：
```bash
ls -l /dev/tty
```
輸出範例：
```bash
crw-rw-rw- 1 root tty 5, 0 Mar 10 12:00 /dev/tty
```
- `c`（開頭的 `c` 代表 **Character Device**）
- `5, 0`（**主設備號（Major Number）** 和 **次設備號（Minor Number）**）
- 主設備號：標識設備的類別
- 次設備號：標識同一類設備中的不同設備
如果想查看所有字元裝置，可以執行：
```bash
ls -l /dev | grep "^c"
```
---
### **字元裝置 vs. 區塊裝置**
| 類型 | 讀寫方式 | 典型用途 | 例子 |
| --- | --- | --- | --- |
| **字元裝置（Character Device）** | 以**字節**為單位讀寫（流式處理），不經過緩衝 | 需要即時回應的設備 | `/dev/tty`, `/dev/random`, `/dev/snd/` |
| **區塊裝置（Block Device）** | 以**區塊**（block）為單位讀寫，有緩衝機制 | 儲存設備（支援隨機存取） | `/dev/sda`, `/dev/mmcblk0` |
---
### **如何存取字元裝置**
### 1. 使用 `cat` 或 `echo` 讀寫字元裝置
```bash
cat /dev/random # 讀取隨機數
echo "Hello" > /dev/tty # 在當前終端顯示 "Hello"
```
### 2. 使用 `dd` 讀取字元裝置
```bash
dd if=/dev/random bs=1 count=10 # 從 /dev/random 讀取 10 個字節
```
### 3. 使用 `stty` 設定字元裝置（例如調整終端行為）
```bash
stty -F /dev/ttyS0 speed 9600 # 設定序列埠速度為 9600 baud
```
---
### **結論**
字元裝置（Character Device）適用於**即時讀寫、流式輸入輸出、不支援隨機存取**的硬體，如終端機、滑鼠、聲音裝置等。它與區塊裝置（Block Device）不同，主要是用來處理小型、即時的數據流，而不是大規模的儲存讀寫。
:::
:::spoiler callback解釋
### **Callback（回呼函式）是什麼？**
**Callback（回呼函式）** 是一種**將函式作為參數傳遞給另一個函式**，並在特定時間點或條件滿足時執行該函式的機制。
這種技術常見於：
- **異步編程（Asynchronous Programming）**
- **事件驅動（Event-Driven）程式設計**
- **系統回調（如內核驅動程式、信號處理等）**
---
## **1. Callback 的基本概念**
在 C 語言或其他語言中，**回呼函式的核心概念是函式指標（Function Pointer）**，允許我們將函式的地址傳遞給其他函式，稍後再執行。
### **範例 1：基本 Callback（C語言）**
```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
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
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
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** 等語言中都廣泛使用！
:::
:::spoiler 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
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
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
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 的工作方式**
1. **每個有虛擬函式的類別都有一個 vtable**（存放虛擬函式指標的陣列）。
2. **每個物件都有一個 vptr（虛擬函式表指標，Virtual Table Pointer）**，指向該類別的 vtable。
3. **當呼叫虛擬函式時，會透過 vptr 查找對應的函式地址，並執行正確的函式。**
---
### **vtable 的運作示意圖**
假設有以下類別：
```cpp
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）。
:::
:::spoiler 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 需要存取某個資料時：
1. **查詢 L1 Cache**，若命中（Cache Hit），則直接讀取。
2. 若未命中，則查詢 L2 Cache，若命中則讀取。
3. 若仍未命中，則查詢 L3 Cache，若還未命中，則從主記憶體（RAM）讀取（Cache Miss）。
4. 讀取到的資料會存入 Cache，以便下次存取時加速。
**缺點**：
- 若資料未命中 Cache（Cache Miss），則需要存取較慢的 RAM，甚至更慢的磁碟（若涉及虛擬記憶體）。
---
## **2. IPI（Inter-Processor Interrupt，處理器間中斷）**
**IPI（處理器間中斷）** 是一種特殊的 **CPU 中斷**，允許多核心處理器（SMP 系統）之間相互通知或同步。
### **IPI 的用途**
1. **喚醒處理器**：讓閒置的 CPU 核心開始工作。
2. **重新分配工作（Rescheduling）**：讓某些執行緒轉移到其他 CPU 核心執行。
3. **快取同步（Cache Coherency）**：確保多核心 CPU 間的 Cache 資料一致性。
4. **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 的種類**
1. **Minor Page Fault（次級分頁錯誤）**
- 頁面已經在 RAM 內，但沒有映射到進程的地址空間（可能是因為換頁表未設置）。
- 例如，共享記憶體的頁面，可能需要 OS 建立適當的映射。
2. **Major Page Fault（主要分頁錯誤）**
- 需要從磁碟（如 swap 空間或 mmap 檔案）載入缺失的頁面到記憶體。
- **代價較高，因為涉及磁碟 I/O**。
3. **Invalid Page Fault（無效分頁錯誤）**
- 進程存取了**非法的記憶體區域**（例如存取 `NULL` 指標）。
- 這通常會導致 **Segmentation Fault（段錯誤，SIGSEGV）**。
### **處理流程**
1. **CPU 產生 Page Fault**
2. **OS 查詢頁表（Page Table）**
- **如果該頁面有效但尚未載入** → **從磁碟載入頁面**（可能會導致 Major Page Fault）。
- **如果該頁面無效** → **發送 SIGSEGV 訊號給進程，導致崩潰**（Segmentation Fault）。
---
## **4. Interrupts（中斷）**
**中斷（Interrupts）** 是一種 CPU **打斷當前執行流程，處理特定事件**的機制。
### **中斷的類型**
1. **硬體中斷（Hardware Interrupts）**
- 由外部設備觸發，如鍵盤、滑鼠、磁碟 I/O、網路請求。
- 例如：
- 鍵盤按下 `Enter`，產生鍵盤中斷（IRQ）。
- 磁碟完成 I/O，通知 CPU 讀取資料。
2. **軟體中斷（Software Interrupts）**
- 由軟體觸發，如 `syscall`（系統呼叫）。
- 例如：
- `int 0x80`（Linux 的舊式系統呼叫方式）。
- `syscall` 指令（現代 x86-64 使用）。
3. **異常（Exceptions）**
- 由 CPU 自行觸發，如：
- 除零錯誤（Divide by Zero）。
- Page Fault（分頁錯誤）。
- 違反存取（Segmentation Fault）。
### **中斷處理流程**
1. **CPU 儲存當前執行狀態**
2. **跳轉到對應的中斷處理函式（Interrupt Service Routine, ISR）**
3. **ISR 完成後，恢復原本的執行狀態，繼續執行程式**
---
## **5. Rescheduling（重新排程）**
**重新排程（Rescheduling）** 指的是作業系統**根據 CPU 排程策略，將 CPU 執行權移交給不同的進程（Process）或執行緒（Thread）**。
### **Rescheduling 何時發生？**
1. **時間片（Time Slice）結束**
- 在**多工系統**中，每個進程獲得的 CPU 時間有限，當時間片用完時，OS 會執行 **上下文切換（Context Switch）**，讓其他進程執行。
2. **進程進入等待狀態（Blocked）**
- 例如，當進程等待 I/O 操作完成時，OS 會將 CPU 分配給其他可執行的進程。
3. **進程被手動 `sleep()`**
- 如果進程執行 `sleep(5)`，OS 會將它從 CPU 移除，並在 5 秒後重新加入執行隊列。
4. **高優先權的進程需要執行**
- 如果有**更高優先權的進程**準備好執行，OS 可能會搶佔當前進程，強制重新排程。
### **Rescheduling 的影響**
- **提升系統效能**：讓 CPU 資源更有效率地分配。
- **支援多工（Multitasking）**：讓多個應用程式同時執行。
- **影響延遲（Latency）**：如果排程策略不佳，可能會造成程式的回應延遲。
---
## **結論**
| 概念 | 作用 |
| --- | --- |
| **Cache（快取）** | 加速 CPU 存取記憶體，減少 RAM 存取次數。 |
| **IPI（處理器間中斷）** | 讓多核 CPU 互相通訊，用於同步與工作分配。 |
| **Page Fault（分頁錯誤）** | CPU 存取未載入記憶體的頁面，OS 需載入或終止進程。 |
| **Interrupts（中斷）** | 暫停當前程式執行，以處理更高優先級的事件（如 I/O）。 |
| **Rescheduling（重新排程）** | 根據 CPU 排程策略，將執行權交給不同的進程或執行緒。 |
這些機制共同協作，確保現代電腦系統能夠有效運作。 🚀
:::
:::spoiler 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 裝置）中更是不可或缺！ 🚀
:::
:::spoiler 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 工作流程**
1. CPU 執行 `WFI` 指令，進入低功耗狀態（例如睡眠模式）。
2. CPU 暫停執行，並等待中斷（如 Timer IRQ、GPIO IRQ）。
3. 一旦中斷發生，CPU **退出低功耗狀態**，繼續執行後續指令。
### **WFI 的優勢**
- 減少 CPU 的功耗，因為在等待中斷時 CPU **停止執行指令**，降低電力消耗。
- 適用於 **需要中斷觸發的應用**，如定時喚醒、事件驅動系統。
### **WFI 使用範例（C / ARM Assembly）**
### **ARM 組語**
```
assembly
複製編輯
WFI ; CPU 進入低功耗模式，直到有中斷發生
```
### **C 語言（CMSIS for Cortex-M）**
```c
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 工作流程**
1. CPU 執行 `WFE`，進入低功耗模式，等待事件發生。
2. **事件來源**：
- 硬體中斷（如 Timer IRQ）。
- 其他 CPU 核心執行 `SEV` 指令。
3. 一旦有事件發生，CPU 會**退出低功耗狀態**並繼續執行。
### **WFE 的優勢**
- 可用於 **多處理器（Multi-Core）架構**，允許一個 CPU 喚醒另一個 CPU。
- 支援等待中斷與等待事件，使得應用更靈活。
### **WFE 使用範例**
### **ARM 組語**
```
assembly
複製編輯
WFE ; CPU 進入低功耗狀態，直到發生事件
```
### **C 語言（CMSIS for Cortex-M）**
```c
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
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 內核（以及大多數作業系統）中，進程有幾種不同的狀態：
1. **Running（執行中）**：進程正在 CPU 上運行。
2. **Runnable（可執行）**：進程已準備好執行，但尚未獲得 CPU 時間。
3. **Sleeping（睡眠中）**
- **Interruptible Sleep（可中斷睡眠）**：進程在等待某個事件（如 I/O 完成），可以被訊號（Signal）或中斷（Interrupt）喚醒。
- **Uninterruptible Sleep（不可中斷睡眠）**：進程等待某些關鍵資源，通常不會被打斷（如等待磁碟 I/O）。
4. **Stopped（停止）**：進程被暫停（如 `SIGSTOP`）。
5. **Zombie（殭屍）**：進程已終止，但仍佔據進程表條目，等待父進程回收。
當一個進程處於 **Sleeping（睡眠狀態）**，而某個事件發生時，OS **透過 Wake Up Process 機制將該進程從「睡眠狀態」轉為「可執行狀態」**。
---
## **2. Wake Up Process 何時發生？**
### **（1）I/O 完成時**
當進程在等待某個 I/O 操作完成時，它會進入 **可中斷睡眠狀態（TASK_INTERRUPTIBLE）**。當 I/O 完成時，驅動程式或內核會喚醒該進程，使其回到 **可執行狀態（Runnable）**，等待 CPU 調度。
### **範例：進程等待 I/O**
```c
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
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
bash
複製編輯
kill -USR1 <進程 PID>
```
這將發送 `SIGUSR1` 訊號，喚醒該進程。
---
### **（3）互斥鎖（Mutex）與條件變數（Condition Variable）**
當一個執行緒等待某個資源（如互斥鎖），它會進入 **等待狀態（Blocked）**，直到其他執行緒釋放資源並喚醒它。
### **範例：使用 `pthread_cond_wait()`**
```c
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()` 內部機制**
1. **`wake_up_process()`**
- 直接將進程的狀態設為 `TASK_RUNNING`，使其可以被 CPU 排程。
2. **`wake_up()`**
- `wake_up()` 會喚醒所有等待特定條件的進程。
### **內核範例**
```c
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，而是在需要時才被喚醒，以提高系統效率並降低功耗。 🚀
:::
Sign in with Wallet
Connect another wallet