2025q1 Homework1 (ideas)

contributed by < bevmmf >

依據 N02:ideas 之要求觀摩 Linux2024q1 期末專題、錄影上和錄影下。

觀摩專題一 : 排程器原理 (contributed by < jeremy90307 >)

一開始我先對這份專題進行蓋覽，並整理了這份專題做的幾個部分可分為以下 :

1. 探討並行程式設計

對 Multiprogramming、Multitasking、Multithreading、Multiprocessing進行釐清

2. 探討排程器原理

議題`1` : `Race Condition` : 多thread同時access並修改共享資源，可能導致預期結果不一致。例如

初始值 value = 0
Thread 1: read (0) → increase (1) → write back (1)
Thread 2: read (0) → increase (1) → write back (1)
結果: value = 1 (預期為 2)

解決方法有二 :

阻塞式同步: 使用 mutex lock，但需注意 priority inversion（優先權反轉），可用 Priority Inheritance 或 Priority Ceiling 解決。
- Mutex Lock: 適合複雜同步需求（如保護大段程式碼或多步驟操作），提供更廣泛的控制。非阻塞不一定總是更高效，因為 Atomic 操作無法處理複雜邏輯。
非阻塞式同步: 使用 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層級相比，更細粒度、更高效的並行方式，可分為以下三部分 :

更輕量級的執行單元
相較於 fork 創建整個process需要複製整個記憶體空間（即使有 copy-on-write 優化）並複製Parent process的資料。Process 之間切換（context switch）需要保存和恢復整個VM mapping、page等，成本很高。相比之下，pthread 只在現有process內創建thread，只需分配一個stack
共享記憶體
多 thread 之間可以直接存取 global var 或 heap 上的資料，而 Process 之間需要使用 IPC（進程間通信，如管道、訊號量）來共享資料，效率較低
高適配普及之多核心 CPU 架構
pthread 提供了一個簡單的方式，讓程式充分利用多核心並行執行
以下是常見函式(參見man 7 pthreads介紹 POSIX Thread 的整體功能和常用 API) :

pthread_create : 創建thread
參考 man 3 pthread_create
pthread_join : 塞當前的執行緒，直到另外一個執行緒執行結束
參考 man 3 pthread_join
pthread_mutex_lock : mutex_lock操作
pthread_cond_wait : 條件變數等待
參考 man 3 pthread_cond_wait

用`fork`實現並行

#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（這裡假設不會失敗，沒有錯誤處理）

輸出為 :

child process 0, PID: 7844
child process 1, PID: 7845
parent process end, PID: 7840
child process 2, PID: 7846

由於不知道os如何調度process，因此每次輸出每行順序會不同

用`pthread`實現並行

#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;
}

定義執行緒函數 thread_func
會被每個新創建的執行緒執行
參數：
- void* arg：執行緒函數的標準簽名，接受一個 void* 類型的參數，用來傳遞數據給執行緒。
- 在這裡，arg 是一個指向整數的指標（int*），表示執行緒的 ID。
創建執行緒
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* 類型）。

等待執行緒結束

    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
POSIX Thread 介紹
 The Open Group Base Specifications Issue 7, 2018 edition IEEE Std 1003.1-2017
GNU C Library (glibc) - Threads
Linux man pages
C 語言 fork 使用教學與範例
 POSIX Threads Programming

2025q1 Homework1 (ideas)

觀摩專題一 : 排程器原理 (contributed by < jeremy90307 >)

1. 探討 並行程式設計

2. 探討 排程器原理

議題1 : Race Condition : 多thread同時access並修改共享資源，可能導致預期結果不一致。例如

議題2 : False Sharing（偽共享）

3. 學習與實作 POSIX Thread

4. 設計相關實驗來驗證並行處理的結果

在深入之前我先學習關於 POSIX Thread 相關知識。以下是我的學習內容 :

用fork實現並行

用pthread實現並行

參考資料

Read more

參與者: bevis30401@gmail.com embe

2025q1 Homework4 (quiz3+4)

2025q1 Homework3 (kxo)

linux2025-homework1