作答表單: 測驗 1
, 2
作答表單: 測驗 3
測驗 1
考慮 strtrim
函式的作用是從給定的 C 字串中移除前導與尾端的空白字元,並回傳修剪 (trim) 後的子字串起始位址。它會直接修改原始字串內容(in-place),將尾端的空白字元以 \0
結束字元截斷,並將指標移到第一個非空白字元,供後續使用。以下字元會被當作空白處理:
字元 |
意義 |
十六進位 |
' ' |
空白鍵 |
0x20 |
'\t' |
tab 鍵 |
0x09 |
'\n' |
換行字元 (LF) |
0x0A |
'\r' |
斷行符號 (CR) |
0x0D |
'\v' |
垂直定位字元 |
0x0B |
'\f' |
換頁字元 |
0x0C |
在 Windows 系統中,每行結尾使用 CRLF 作為斷行符號;而在 Linux 則僅使用 LF 字元。因此,相較於 Linux,Windows 中的每行會多出一個 CR 字元。CR 原本的意思是 Carriage Return,對應鍵盤上的 Enter 鍵,LF 意思是 Line Feed,表示實際的換行動作。macOS 目前也與 Linux 一樣,使用 LF 作為行尾字元。
應用情境
- 處理使用者輸入:避免輸入欄前後的空格影響後續操作 (如登入、搜尋)
- 解析設定檔:行尾或行首常有空白,需先清除
- 處理網路協定標頭或資料行:HTTP headers、CSV 欄位等
我們利用第 3 週測驗題提及的 SWAR 技巧,來實作 strtrim
函式 (只處理 ASCII,部分程式碼遮蔽)
考慮 client.c 是我們打造的網路聊天客戶端程式碼,對應的巨集定義如下:
而 chat.c
則是網路聊天的伺服器端程式碼,定義如下 (忽略標頭檔):
主函式和事件主迴圈如下: (部分程式碼遮蔽)
對應的輔助函式如下:
static int set_nonblocking(int fd)
{
int flags = fcntl(fd, F_GETFL, 0);
if (flags < 0 || fcntl(fd, F_SETFL, flags | O_NONBLOCK) < 0) {
perror("fcntl");
return CHAT_ERR;
}
return CHAT_OK;
}
static int chat_listen(server_t *server, const char *host, int port)
{
struct addrinfo hints = {
.ai_family = AF_INET,
.ai_socktype = SOCK_STREAM,
.ai_flags = AI_PASSIVE,
};
char port_str[6];
snprintf(port_str, sizeof(port_str), "%d", port);
struct addrinfo *res;
if (getaddrinfo(host, port_str, &hints, &res)) {
perror("getaddrinfo");
return CHAT_ERR;
}
int fd = -1;
for (struct addrinfo *rp = res; rp; rp = rp->ai_next) {
fd = socket(rp->ai_family, rp->ai_socktype, rp->ai_protocol);
if (fd < 0)
continue;
if (0 > setsockopt(fd, SOL_SOCKET, SO_REUSEADDR, &(int){1},
sizeof(int)) ||
bind(fd, rp->ai_addr, rp->ai_addrlen) < 0 ||
listen(fd, BACKLOG) < 0) {
close(fd);
continue;
}
break;
}
freeaddrinfo(res);
if (fd < 0) {
perror("bind/listen");
return CHAT_ERR;
}
server->fd = fd;
return set_nonblocking(fd);
}
static int chat_accept(server_t *server)
{
int fd = accept(server->fd, NULL, NULL);
if (fd < 0) {
if (errno != EAGAIN && errno != EWOULDBLOCK)
perror("accept");
return CHAT_ERR;
}
return set_nonblocking(fd) == CHAT_OK ? fd : CHAT_ERR;
}
static void send_to_client(client_t *client, const char *msg, int len)
{
if (write(client->fd, msg, len) < 0)
perror("write");
}
static void broadcast_message(server_t *server,
const char *buf,
int sender_fd,
int server_info)
{
char msg[256];
int len = server_info ? snprintf(msg, sizeof(msg), "Server\r\n%s", buf)
: snprintf(msg, sizeof(msg), "%s\r\n%s",
server->clients[sender_fd]->nick, buf);
for (int i = 0; i < MAX_CLIENTS; i++) {
client_t *client = server->clients[i];
if (client && i != sender_fd)
send_to_client(client, msg, len);
}
}
static void handle_disconnect(server_t *server, int epollfd, int fd, char *buf)
{
client_t *client = server->clients[fd];
snprintf(buf, 256, "%s left\n", client->nick);
broadcast_message(server, buf, fd, 1);
EEEE;
close(fd);
free(client);
server->clients[fd] = NULL;
}
static void handle_client_message(server_t *server,
int epollfd,
int fd,
char *buf,
ssize_t nread)
{
buf[nread] = '\0';
client_t *client = server->clients[fd];
if (!strncmp(buf, "/quit", 5) || !strncmp(buf, "/exit", 5)) {
handle_disconnect(server, epollfd, fd, buf);
} else if (!strncmp(buf, "/nick", 5)) {
const char *nick = strtrim(buf + 5);
strncpy(client->nick, nick, NICK_MAXLEN - 1);
client->nick[NICK_MAXLEN - 1] = '\0';
} else {
broadcast_message(server, buf, fd, 0);
}
}
補完程式碼,使其運作符合預期。作答規範:
AAAA
和 CCCC
為十進位數值
BBBB
和 DDDD
為合法表示式,不得出現乘法和除法運算子
EEEE
, FFFF
, GGGG
, HHHH
皆為以 epoll_
開頭的函式呼叫
EEEE
, FFFF
, HHHH
包含 EPOLL_
開頭的巨集
- GGGG 包含
MAX_EVENTS
- 使用一致的程式碼縮排風格,以最精簡的方式撰寫,不包含表示式前後的空白字元,皆不得出現
;
或 ?
或 ;
字元
延伸問題:
- 解釋上方程式碼運作原理
- 藉由在客戶端引入對話模擬 (如 ELIZA),量化上方程式碼,並提出針對其並行處理能力的改進
測驗 2
延續第 6 週測驗題的測驗 3
。在處理大規模資料集時,常見的需求是快速判斷某個元素是否存在於一個龐大的集合中,這就是成員資格查詢 (membership query)。傳統的資料結構面臨挑戰:
- 雜湊表 (Hash Table): 雖然平均查詢時間為 ,但需要儲存元素本身或其標識,空間開銷可能非常大
- 串列/陣列 (List/Array): 無序串列查詢效率低 ();有序結構(如平衡樹、排序陣列)查詢效率尚可 (),但仍需儲存元素,且插入和維護成本較高
當應用場景滿足以下條件時,Bloom Filter 提供截然不同的解決方案:
- 可以容忍一定的誤報 (False Positives):即查詢結果為「可能存在」,但元素實際上不在集合中
- 絕不允許漏報 (No False Negatives):即查詢結果為「絕對不存在」時,元素一定不在集合中
- 對空間效率和查詢速度有極高要求
Bloom Filter 正是藉由犧牲絕對的準確性(允許誤報),換取極佳的空間和時間效率。
Bloom Filter 由以下二部分組成:
- 位元陣列 (Bit Array): 一個長度為 的位元陣列,所有位元初始值均為 0
- k 個雜湊函數: 個獨立的雜湊函數 。每個函數將輸入的鍵 (key) 均勻地映射到 的範圍內。理想情況下,這些雜湊函數的結果應相互獨立
關鍵操作:
- 添加元素 (Add / Insertion):
- 對於要添加的元素 ,使用 個雜湊函數分別計算其雜湊值:。這些雜湊值對應位元陣列中的 個索引位置。
- 將位元陣列中這 個索引位置的位元設定為 1。 (注意:即使某個位元原本已經是 1,也保持為 1)。
- 查詢元素 (Query / Check):
- 對於要查詢的元素 ,同樣使用 個雜湊函數計算其雜湊值:。
- 檢查位元陣列中這 個索引位置的位元:
- 如果所有位元都為 1: 則判斷元素 可能存在 (Possibly Present) 於集合中。這是可能產生誤報的情況。
- 如果至少有一個位元為 0: 則判斷元素 絕對不存在 (Definitely Not Present) 於集合中。這是 Bloom Filter 不會有漏報的保證。
誤報率 (False Positive Probability) 是理解 Bloom Filter 性能和進行參數設計的關鍵。我們的目標是計算當查詢一個從未被添加過的元素時,被誤判為存在的機率,即誤報率 ()。
假設 (理想情況):
- 均勻性 (Uniformity): 每個雜湊函數都將任意鍵均勻映射到位元陣列的 範圍內,即映射到任何一個特定位置的機率是
- 獨立性 (Independence): 個雜湊函數的輸出結果是相互獨立的
推導步驟:
- 單個位元保持為 0 的機率 (單次雜湊):
對於位元陣列中的某一個特定位元,當插入一個鍵時,被某個特定的雜湊函數 選中的機率是 。因此,這個位元不被 選中的機率是 。
- 單個位元保持為 0 的機率 (k 次雜湊, 單個鍵):
由於有 個獨立的雜湊函數,這個特定位元在插入單個鍵(經過 次雜湊)後仍然保持為 0 的機率是:
- 單個位元保持為 0 的機率 (插入 N 個鍵):
假設我們獨立地插入 個不同的鍵。對於某一個特定位元,它在插入 個鍵後仍然保持為 0 的機率是(每次插入的 次雜湊都不改變此位元):
- 使用近似簡化:
當位元陣列長度 相對於 很大時, 是一個很小的值。根據極限 ,我們可以得到近似:
這個近似在 越大時越精確。
- 近似單個位元保持為 0 的機率:
將上述近似代入第 3 步的公式:
- 單個位元被設為 1 的機率:
在插入 個鍵後,某個特定位元被設為 1 的機率是:
- 誤報率 () 的計算:
考慮一個從未被插入集合的元素 。查詢 時發生誤報,意味著 對應的 個雜湊位置 上的位元恰好都為 1。
為了簡化計算,我們做一個關鍵的(近似)假設:對於一個不在集合中的元素 ,其 個雜湊位置上的位元狀態是相互獨立的。
在該獨立性假設下,誤報率 (也常用 表示)約等於單個位元為 1 的機率的 次方:
參數最佳化:尋找最優的 k
給定預計插入的元素數量 和位元陣列大小 ,我們希望選擇一個最佳的雜湊函數個數 ,使得誤報率 最小。
藉由對 求導並令導數為 0,可以解得使誤報率最小的最優雜湊函數個數 滿足:
即:
由於 必須是整數,實際應用中通常取 。
反向計算:給定 N 和期望誤報率 f,計算 m 和 k
- 計算 k: 當 取最優值時,誤報率 。因此:
。
- 計算 m: 從 得到 。代入 :
整理以上可之:
Bloom filter 的優點:
- 空間效率極高: 只需 個位元,無需儲存元素本身
- 時間效率高: 插入和查詢操作時間複雜度均為 O(k),與集合元素總數 無關
- 無漏報 (No False Negatives): 查詢結果為「不存在」時絕對可靠。
- 可合併性: 兩個參數 () 相同的 Bloom Filter 可藉由按位或 (Bitwise OR) 操作合併,代表兩個集合的並集
Bloom filter 的缺點:
- 存在誤報 (False Positives): 查詢結果為「可能存在」時可能不準確。誤報率 受 影響
- 無法安全刪除元素 (標準 Bloom Filter): 直接將位元從 1 改為 0 可能影響其他元素,導致漏報。(可用 Counting Bloom Filter 改進,但增加空間開銷)
- 需要預估元素數量 N: 為獲得理想誤報率,需提前估計 以合理設定 和 。若實際 遠超預期,誤報率會急劇上升。(可用 Scalable Bloom Filter 改進)
理論上 Bloom Filter 需要 個獨立且均勻的雜湊函數,在實際硬中,產生 個高品質且完全獨立的雜湊函數成本較高。常見的解決方案有:
Linux 核心的 eBPF Bloom Filter 實作採用此方法。它使用核心的 jhash
函數,並為產生第 個雜湊值時提供不同的種子 (bloom->hash_seed + i
)。
以下是用 FNV-1a 雜湊函數和簡化版雙重雜湊策略的具體實作範例:
-
參數設定:
- 使用 個雜湊函式產生 4 個位元索引。
- 位元陣列長度設為 。
-
雜湊函數 (64 位元 FNV-1a 變體):
-
索引產生方式 (簡化版雙重雜湊): 首先計算一次基礎雜湊值 hbase = hash(key, keylen)
,然後產生 個索引:
這裡利用 64 位雜湊值的高 32 位作為步長因子,與基礎雜湊值組合後藉由位與操作(因為 是 2 的冪)映射到索引範圍。
-
理論誤判率計算: 假設此 Bloom Filter 插入 個元素:
根據誤判率公式 :
→ 理論誤判率約為 或 0.000074%。
FNV-1a 與索引衍生的實務考量與限制:
- 雜湊偏態: FNV-1a 雜湊函數雖然計算速度快,但對於具有相似字首的字串(例如 "item-001", "item-002")容易產生相似的雜湊值或碰撞,其輸出分佈的均勻性可能不如 MurmurHash 或 xxHash 等現代雜湊函數,這會影響位元陣列中位元設定的均勻性。
- 索引衍生獨立性不足: 這種藉由單一基礎雜湊值
hbase
推導產生 個索引的方法(包括簡化版雙重雜湊),其產生的 indices[0], indices[1], ..., indices[k-1]
之間存在較強的相關性,並非真正獨立。這違反了理論推導中「位元設定為獨立事件」的關鍵假設,可能導致實際的誤判率高於理論預估值。
數學推導中使用的「雜湊函數獨立」和「位元狀態獨立」的假設在現實中通常是近似滿足的。
- 使用同一個雜湊算法配合不同種子或藉由衍生方式產生的 個值並非嚴格獨立
- 位元陣列中不同位元的狀態也非完全獨立
然而:
- 實用性: 只要基礎雜湊函數具有良好的均勻分佈性與雪崩效應(輸入微小變化導致輸出大幅隨機變化),那麼即使產生 個值的方法存在一定的依賴性,基於獨立性假設推導出的誤判率公式 仍然是一個非常有用的性能估計與參數設計指南。
- 雜湊品質是關鍵: 無論如何產生 個值,基礎雜湊函數的品質(均勻性、低碰撞率)對於 Bloom Filter 的實際性能至關重要。選擇高品質的雜湊函數是改進 Bloom Filter 性能的重要一步。
- 權衡: 這體現了 Bloom Filter 設計中的權衡:追求理論上的完美獨立性可能代價過高,而實用的近似方法在效率和效果之間取得了平衡。認識到理論與實踐的差距,並了解所用方法的局限性很重要。
Linux 核心在 eBPF (extended Berkeley Packet Filter) 子系統中,藉由 BPF_MAP_TYPE_BLOOM_FILTER
類型的 eBPF map,為核心空間和使用者空間的 eBPF 程序提供了使用 Bloom Filter 的能力。
參數計算與實作 (kernel/bpf/bloom_filter.c)
核心程式碼 bloom_filter_map_alloc
負責創建 Bloom Filter map。關鍵步驟是根據使用者提供的 max_entries
() 和 nr_hash_funcs
() 計算所需的位元陣列大小 (nr_bits
):
程式碼分析:
- 計算目標: 根據使用者輸入的 和 ,計算出一個能使誤報率接近最小的位元陣列大小 。
- 公式應用與近似: 核心程式碼直接用 的關係,並使用 進行定點近似。
- 邊界處理與效率改進:處理計算溢出,確保最小尺寸,並將 取整到 2 的冪次方,以使用高效的位與操作進行索引映射。
- 隨機種子: 每個 Bloom Filter 實例使用隨機的
hash_seed
,配合 jhash
產生 個不同的雜湊值。
本次測驗中,採用 FNV-1a 的 64 位元變種。
Bloom filter 適合高效能並行場景的考量是:
- 新增與查詢操作都是 lock-free
- 不會移除元素
然而,這些操作在多核處理器或多執行緒環境下,就會遇到幾個重要的問題:
- Data Race 風險:假設二個執行緒同時對
filter->data[index]
做 bitwise-OR 操作或查詢,若未使用 atomics,則會出現下列典型的競爭情形:
這可能會導致其中一個數值被覆蓋,產生 bit flip 丟失問題,進而導致查詢誤判機率上升,甚至出現 false negative(理論上不該出現)。
- Cache coherence / False Sharing: 由於多執行緒可能同時寫入鄰近的
uint64_t
區塊,若 data[]
未妥善對齊,則可能導致 CPU 快取行為效率低下。若二個執行緒操作相鄰但不同的 data[i]
,這些可能落在同一 cache line,導致 false sharing;每次更新位元,會造成整個 cache line 的 write invalidation,增加資料匯流排負擔與記憶體同步延遲
延伸閱讀: 並行程式設計: Atomics 操作
需要留意的是,儘管使用 atomic RMW,但不足以完全解決 contention:若多執行緒集中寫入相同區段 (高 collision key),仍會造成 atomic cache ping-pong,於是需要改進雜湊函數的數值分布。另外,雖然使用 _Alignas(64)
已有助於對齊,但若結構為 struct { _Atomic uint64_t data[n]; }
,仍需考慮整體記憶體佈局 (memory layout) 和頁面分佈。
考慮以下 concurrent bloom filter,其標頭檔: (bloom.h
)
效能評比程式可見 bench.c
對應的 C 程式:
補完程式碼,使其運作符合預期。作答規範:
IIII
和 JJJJ
為 atomic_
開頭的函式呼叫
- 使用一致的程式碼縮排風格,以最精簡的方式撰寫,不包含表示式前後的空白字元,皆不得出現
;
或 ?
或 ;
字元
測驗 3
我們想精確測量 GNU/Linux 上行程和執行緒 (NPTL) 的 context switch(上下文切換)成本,其基本原理是,利用 pipe 系統呼叫雙向通訊機制造成二個執行單位 (process 或 thread) 之間交替等待與喚醒,並量測整體來回的時間,進而估算一次 context switch 的平均耗時。
延伸閱讀: Arm-Linux
測量 context switch 前,我們準備以下程式碼:
以下程式會建立二個 pipe
:
pipe1
: A 寫入、B 載入
pipe2
: B 寫入、A 載入
這構成 A ↔ B 之間一來一回的同步通訊機制,無論是行程抑或執行緒。
彼此等待與喚醒造成 context switch
- A 寫入 pipe1 → B 等待 pipe1 資料 → 喚醒並載入
- B 寫入 pipe2 → A 等待 pipe2 資料 → 喚醒並載入
- 如此重複若干次
每次來回交替,會造成二次 context switch (即 A → B 和 B → A)。
對照第 3 週測驗題的測驗三
針對行程的測試流程
- 親代行程 (A) 綁定 CPU0,設定
SCHED_FIFO
優先權 95
- 子行程 (B) 綁定 CPU1,設定
SCHED_FIFO
優先權 94
- 親代行程記錄時間,在每次來回後讀出 pipe2 的資料
- 結束後計算「平均每次 context switch = 來回時間 / (2 * iterations)」
對應的原始程式碼 (部分遮蔽):
關鍵操作:
- 使用
poll()
等待對方寫入資料,確保有 blocking,進而觸發 context switch
- 使用
SCHED_FIFO
保證完全不被 NORMAL/OTHER 等非即時行程干擾
- CPU affinity 保證切換不受處理器核遷移 (CPU migration) 影響
執行緒測試流程:
- 主執行緒與副執行緒分別固定在 CPU0 / CPU1,使用 pthread_barrier 同步起跑
- 也是透過二條 pipe 傳遞訊號與資料,一來一回代表二次 context switch
對應的原始程式碼 (部分遮蔽):
實作手法整理:
設計要素 |
原因 |
pipe + poll() |
強制 thread/process block,保證產生 context switch,而非 busy-wait 或同步競爭 |
SCHED_FIFO |
避免被其他一般行程干擾,確保測量只涵蓋必要切換成本 |
CPU affinity |
排除 CPU 排程器中遷移導致的 TLB flush、熱區 (hot region) 切換等雜訊 |
fork() 與 pthread_create() |
分別製造行程/執行緒的互動情境,便於比較差異 |
主程式:
本程式檔名為 ctx.c
,編譯方式:
執行時務必要用超級使用者權限:
在 AMD Ryzen Threadripper 2990WX 32-Core (64) @ 3.00 GHz 測試,參考輸出:
行程和執行緒的 context switch 切換成本為何如此接近?二者相差非常小,幾乎在誤差範圍內。
在 Linux 中,無論是 process 抑或 thread,其實都是 task_struct
,亦即 Linux 核心用以管理排程的基本單元。差異僅在於:
- process:有獨立的
mm_struct
,即自身的虛擬記憶體空間
- thread:與其他執行緒共享
mm_struct
,也就是與其他執行緒共享同一定址空間 (address space)
從核心的 CPU 排程器 (如 CFS 或 EEVDF) 角度來看,切換的是 task_struct
實體,而非高階語意上的 "process vs thread" (把你書架上的恐龍書移開,不要弄髒書架)。這說明何以二者的 context switch 成本在 Linux 上幾乎一樣。
學不好作業系統,不能怪你
無論是透過 fork()
建立的子行程還是透過 pthread_create()
建立的執行緒,Linux 都以相同的結構(task_struct
)管理它們,且使用相同的排程機制。因此,context switch 的基本開銷:儲存/載入暫存器、切換 kernel stack、切換分頁表 (page table) 等動作,本質相同。
由於執行緒的切換過程中,不需更換分頁表,看似會有較低的切換成本,但現代 Linux 在同 NUMA node、TLB cache 表現良好的情況下,行程中的分頁表重新載入的開銷極低,且現代中央處理器於 TLB 切換已有顯著改進,因此我們不易看出行程和執行緒切換的成本差異。
注意,許多教材或討論提及的執行緒存在的優勢,並非來自後者 context switch 成本較低 (幾乎相同),而是來自:
- 可共享 address space → 不需 IPC 可直接存取同一份資料
- 可共享 file descriptor、heap、stack (部分) 等資源
- 更容易建立大量輕量單位(例如 10 萬個 thread vs process)
作答規範:
- IGNORE_THIS1 到 IGNORE_THIS4 和 THIS_ISNT_VALID1 到 THIS_ISNT_VALID3 皆為十進位數值
延伸題目:
- 以 eBPF 進行上述測量,亦即取得行程和執行緒切換的成本
- 在多個 NUMA 節點的環境,上述程式碼能否精準測量?若無法,有哪些干擾因素、又如何排除?