# 2025q1 Homework1 (ideas)
contributed by < [bevmmf](https://github.com/bevmmf) >
依據 [N02:ideas](https://hackmd.io/@sysprog/linux2025-ideas) 之要求觀摩 [Linux2024q1 期末專題](https://hackmd.io/@sysprog/linux2024-projects)、[錄影上](https://www.youtube.com/watch?v=kwYgfkD1dWA&ab_channel=.GUTS)和[錄影下](https://www.youtube.com/watch?v=qUd1PtF-R38&t=1s)。
---
## 觀摩專題一 : 排程器原理 (contributed by < [ jeremy90307](https://hackmd.io/@sysprog/HyDijL0HR) >)
一開始我先對這份專題進行蓋覽，並整理了這份專題做的幾個部分可分為以下 :
### 1. 探討 並行程式設計
對 `Multiprogramming`、`Multitasking`、`Multithreading`、`Multiprocessing`進行釐清
### 2. 探討 排程器原理
#### 議題`1` : `Race Condition` : 多thread同時access並修改共享資源，可能導致預期結果不一致。例如
```c
初始值 value = 0
Thread 1: read (0) → increase (1) → write back (1)
Thread 2: read (0) → increase (1) → write back (1)
結果: value = 1 (預期為 2)
```
解決方法有二 :
1. 阻塞式同步: 使用 `mutex lock`，但需注意 priority inversion（優先權反轉），可用 Priority Inheritance 或 Priority Ceiling 解決。
- Mutex Lock: 適合複雜同步需求（如保護大段程式碼或多步驟操作），提供更廣泛的控制。非阻塞不一定總是更高效，因為 Atomic 操作無法處理複雜邏輯。
2. 非阻塞式同步: 使用 `Atomic 操作`（如 `compare-and-swap, CAS`），確保操作不可分割
- Atomic 操作: 適用於簡單同步場景（如計數器增減），執行效率高，但功能有限。
#### 議題`2` : False Sharing（偽共享）
定義: 多執行緒存取同一 cache line（通常 64 位元組）上的不同變數時，因 cache coherence 機制導致效能下降。
例如，當 CPU0 修改了變數 X 的值時，這個變數所在的快取行（cache line，通常是一段固定大小的記憶體塊，例如 64 位元組）會被更新。然而，CPU1 的快取中可能也有一份舊的 X 的副本。為了確保所有核心看到的資料是一致的，系統必須遵循快取一致性協議（例如 MESI 協議），保證所有核心看到的資料是最新的。
solution : 變數獨占一個 cache line 大小（通常 64 bytes）
### 3. 學習與實作 `POSIX Thread`
- 設計了輕量級的 `Mutex Lock`
- 實作了 `Priority-inheritance mutex`，並解決實作過程中遇到的問題
### 4. 設計相關實驗來驗證並行處理的結果
#### 在深入之前我先學習關於 `POSIX Thread` 相關知識。以下是我的學習內容 :
是什麼?
`POSIX Thread`（簡稱 pthread / 全寫 Portable Operating System Interface）
此旨在讓開發者在支援 POSIX 的作業系統（如 Linux、Unix）上實現多執行緒應用。是一個針對多執行緒程式設計的POSIX標準 API (通過 `<pthread.h>` 頭文件引入)，允許單一程式在單一行程（process）內創建多個執行緒（threads），進而充分利用多核心 CPU 的效能。
訴求是:
與system call `fork`(由`<unistd.h>`引入)process層級相比，更細粒度、更高效的並行方式，可分為以下三部分 :
1. 更輕量級的執行單元
相較於 `fork` 創建整個process需要複製整個記憶體空間（即使有 copy-on-write 優化）並複製Parent process的資料。Process 之間切換（context switch）需要保存和恢復整個VM mapping、page等，成本很高。相比之下，`pthread` 只在現有process內創建thread，只需分配一個stack
2. 共享記憶體
多 thread 之間可以直接存取 global var 或 heap 上的資料，而 Process 之間需要使用 IPC（進程間通信，如管道、訊號量）來共享資料，效率較低
3. 高適配普及之多核心 CPU 架構
pthread 提供了一個簡單的方式，讓程式充分利用多核心並行執行
以下是常見函式(參見[man 7 pthreads](https://man7.org/linux/man-pages/man7/pthreads.7.html)介紹 POSIX Thread 的整體功能和常用 API) :
`pthread_create` : 創建thread
參考 [man 3 pthread_create](https://man7.org/linux/man-pages/man3/pthread_create.3.html)
`pthread_join` : 塞當前的執行緒，直到另外一個執行緒執行結束
參考 [man 3 pthread_join](https://linux.die.net/man/3/pthread_join)
`pthread_mutex_lock` : mutex_lock操作
`pthread_cond_wait` : 條件變數等待
參考 [man 3 pthread_cond_wait](https://man7.org/linux/man-pages/man3/pthread_cond_wait.3.html)
##### 用`fork`實現並行
```c
#include <stdio.h>
#include <unistd.h>
int main() {
for (int i = 0; i < 3; i++) {
pid_t pid = fork();
if (pid == 0) {
printf("child process %d, PID: %d\n", i, getpid());
return 0; // child process end
}
}
printf("parent process end, PID: %d\n", getpid());
return 0;
}
```
每次loop中，呼叫 `fork()` 創建一個child_process
child_process的code list只有 printf 這行
`fork()` 的返回值
- 在parent_process中，返回child_process的 PID（進程 ID，一個正整數）。
- 在child_process中，返回 0。
- 如果創建失敗，返回 -1（這裡假設不會失敗，沒有錯誤處理）
輸出為 :
```shell
child process 0, PID: 7844
child process 1, PID: 7845
parent process end, PID: 7840
child process 2, PID: 7846
```
由於不知道os如何調度process，因此每次輸出每行順序會不同
##### 用`pthread`實現並行
```c
#include <stdio.h>
#include <pthread.h>
void* thread_func(void* arg) {
int id = *(int*)arg; //將 arg 轉換為 int* 類型並解引用，獲取執行緒的 ID
printf("thread %d\n", id);
return NULL;
}
int main() {
pthread_t threads[3];
int ids[3];
for (int i = 0; i < 3; i++) { //create 3 threads
ids[i] = i;
pthread_create(&threads[i], NULL, thread_func, &ids[i]);
}
for (int i = 0; i < 3; i++) {
pthread_join(threads[i], NULL);
}
printf("main thread end\n");
return 0;
}
```
1. 定義執行緒函數 `thread_func`
會被每個新創建的執行緒執行
參數：
- void* arg：執行緒函數的標準簽名，接受一個 void* 類型的參數，用來傳遞數據給執行緒。
- 在這裡，arg 是一個指向整數的指標（int*），表示執行緒的 ID。
2. 創建執行緒
`pthread_create(&threads[i], NULL, thread_func, &ids[i]);`
呼叫 `pthread_create` 創建一個新執行緒
每個執行緒執行 thread_func，並接收對應的 `ids[i]` 地址作為參數
參數 :
- &threads[i]：指向執行緒標識符的指標，創建的執行緒 ID 會儲存在 threads[i] 中。
- NULL：執行緒屬性，傳入 NULL 表示使用預設屬性。
- thread_func：執行緒要執行的函數（thread_func）。
- &ids[i]：傳遞給執行緒函數的參數，這裡傳入 ids[i] 的地址（int* 類型）。
3. 等待執行緒結束
```c
for (int i = 0; i < 3; i++) {
pthread_join(threads[i], NULL);
}
```
`pthread_join(threads[i], NULL);`
讓主執行緒等待指定的執行緒（threads[i]）結束
參數：
- `threads[i]`：要等待的執行緒標識符。
- `NULL`：用來接收執行緒的返回值，這裡傳入 NULL 表示不關心返回值。
主執行緒會在這裡阻塞，直到所有 3 個執行緒都執行完畢（即 thread_func 返回）
4. 主執行緒結束
#### 參考資料
[POSIX執行緒-wiki](https://zh.wikipedia.org/zh-tw/POSIX%E7%BA%BF%E7%A8%8B)
[POSIX Thread 介紹](https://ithelp.ithome.com.tw/articles/10280830)
[The Open Group Base Specifications Issue 7, 2018 edition IEEE Std 1003.1-2017 ](https://pubs.opengroup.org/onlinepubs/9699919799.2018edition/)
[GNU C Library (glibc) - Threads](https://www.gnu.org/software/libc/manual/html_node/Threads.html)
[Linux man pages](https://linux.die.net/man/)
[C 語言 fork 使用教學與範例](https://blog.gtwang.org/programming/c-fork-tutorial-multi-process-programming/)
[POSIX Threads Programming](https://hpc-tutorials.llnl.gov/posix/)
Sign in with Wallet
Connect another wallet