# 2026-04-28/30 問答簡記

## nyraa
mutex 和 semaphore 的差別
生產者消費者問題用 mutex 要怎麼設計

## andy20040
stack 和 heap的差別?
* stack:
stack 為 LIFO 的 資料結構，其適配了 C 語言函式呼叫的方式
例如: 先呼叫 A( ) 再呼叫 B( ) 時，會先將 A( ) 的 stack frame 壓入堆疊再將 B( ) 的 stack frame 壓入堆疊，當函式要 return 的時候由於 LIFO 的特性 B( ) 的 stack frame 會先被彈出 ，這跟 C 語言函式返回的方式相同。

* heap:
使用 malloc( ) 或 calloc() 申請空間，當空間不需要的時候，用 free()來釋放空間，可以避免記憶體洩漏

## rrrchii
如何加速llm稀疏矩陣的運算速度?
算出改為 COO 的時間複雜度，用期望值計算（會有e）?

回答：
測試程式：
來源：https://hackmd.io/@Aquamay/Syd8UdLqu

可以用for迴圈先找到非零值並把位置紀錄下來，減少結果為0的矩陣乘法來加速稀疏矩陣的運算，像是上面的例子，每一筆非零值就是一個 $1 \times 3$ 的矩陣，若有　$N$ 筆非零值，我們可以得到一個　$N \times 3$ 的小矩陣，這個方式稱為　Coordinate Format (COO)，以下是測試結果

已知密度如何算出（有ｅ）
## Bigtooth123
Thread 間如何保護共享記憶體?
* Mutex: 同一時間只能有一個 thread 在 critical section，具有 Ownership，誰加鎖就必須由誰解鎖，未取得鎖的 Thread 會進入睡眠，去到 waiting queue，釋放 CPU，需注意死鎖（Deadlock）風險。
* Semaphore: 計數器機制，控制資源數量，wait() 扣減資源，post() 釋放資源，當無可用資源時（計數器 $\le$ 0），執行 wait() 的 Thread 會被阻塞（Block）並進入 waiting queue。
* Spinlock: Busy Waiting，Thread 在 while 迴圈中不斷測試變數（如使用 test_and_set），不釋放 CPU，直到獲得鎖並進入到 critical section，需注意死鎖（Deadlock）風險。

而以上操作都需要 atomic 指令的幫助才能實現。
Atomic 指令確保了一段段操作是不可分割的，期間不會有任何的中斷。

Read Modify Write:
以 ``i++`` 來做舉例，這個操作包含了三個部分
* 讀取變數 `i`
* 修改變數 `i`
* 寫入變數 `i`

Race Condition
如果沒有 Atomic 指令保護，這三個步驟可能被其他核心的中斷或存取交錯執行，導致資料不一致，例如：兩個執行緒各加 `1`，結果卻只增加了 `1`。

實作方法:

int compare_and_swap(int *value, int expected, int new_value)
{ 
    int temp = *value; 
    if (*value == expected) 
        *value = new_value; 
    return temp; 
} 

void increment(atomic_int *v)
{
    int temp;
    do {
        temp = *v;
    }
    while (temp != (compare_and_swap(v,temp,temp+1));
}

其中 compare_and_swap 就是 atomic 操作。

當很多 Thread 競爭時，Spinlock 效率低下該怎麼辦？
從 Cache Coherence 的角度來分析
* Test & Set Lock:
* 指令裡包含一個「寫入」動作（把 lock 設為 true）
* 影響 : 核心 A 執行 test_and_set，發出訊號給其他所有核心，使得其他核心 cache 需要重新抓取資料。
* Test & Test & Set Lock:
* 在鎖被持有的期間，所有等待的 Thread 都在執行「普通讀取」。
* 影響: 大家都可以從自己的 Cache 裡讀到鎖的狀態，鎖被釋放後再去搶鎖。

第二種方法不會像是第一種方法那樣造成匯流排充斥著無意義的「失效」與「抓取」訊號。但是真正在實作的時候通常會用 MCS spinlock。

Object Lifecycle:
必須防止 Use-After-Free，確保物件釋放與存取之間具備原子性，可以使用引用計數的方式，最後一個 Thread 把計數器減到 0 時，才由該 Thread 負責執行 free。

## MAX990ck
甚麼時候會發生 lock 的爭奪

linux 核心中，有哪些方式可以實作 lock

semaphore 跟 mutex 的差別

mutex 跟 semaphore 會應有在哪裡
甚麼場合適合用semaphore
生產與消費者問題

timer 是如何震盪的
-> RLC 電路震盪的功耗

https://wiki.csie.ncku.edu.tw/embedded/priority-inversion-on-Mars.pdf

https://github.com/sysprog21/concurrent-programs
https://github.com/sysprog21/concurrent-programs/blob/master/lf-queue/lfq.c

kweb: https://hackmd.io/@sysprog/SJYvYX_Wxl
RTOS: https://hackmd.io/@Appmedia/Preempt-RT