# Linux 核心專題: 高效網頁伺服器
> 執行人: Hualing-Chiu
> [專題解說影片](https://www.youtube.com/watch?v=ovZv4nGmv3M)
### Reviewed by `Wufangni`
>TasksQueue 以及 Thread Pool 在這邊扮演的角色就是送貨員以及送貨車，Taskqueue 會接收由 worker process 來的工作，處理完之後再把結果送回 worker process 中。
>cserv 也實作同樣的主從式架構，但與 NGINX 相異處在於 cserv 以 coroutine 作到 cooperative multitasking 以達到相對高效的結果。
想請問 cserv 與 NGINX 的差異只在於多了 cooperative multitasking 嗎?對於時長過長的任務也是採用 TaskQueue 來處理嗎?
### Reviewed by `nosba0957`
ab, htstress, httperf 三種測試工具的差異為何？為何選擇這三種？
## 任務簡介
開發高性能網頁伺服器，探討不同執行緒模型的影響。
## TODO: 分析第七次作業的 cserv
> cserv 採用 multiple processes)，試著去執行，含效能評比，要對照 Nginx
### 架構設計描述與探討
#### 主從式架構
##### NGINX
> NGINX 的組成為一個 Master 行程，負責做初始化相關的工作，例如組態設定, 建立 worker, 管理 worker (接收來自外界的 signal，向各 worker 發送 signal，監控 worker 的運行狀態)。至於 Worker 就是專門來處理客戶端的請求 (一般是網頁瀏覽器)，NGINX 的 worker 會對 CPU 設定 affinity，因此可降低 thread (worker) 間的 context switch 數量，抑制其引起效能低落的可能性。
從 [NGINX 開發日誌](https://www.f5.com/company/blog/nginx)中以送貨員以及排隊等候的機制去看待這個問題
假設有一堆顧客，他們需要取貨，而有些貨物(1-3 號箱)盡在眼前，同時也很多貨物存在遙遠的倉庫中，此時注意這邊這位工作者(worker) 只會盲目的遵從目前顧客的要求，並且服務目前的顧客，假設有一個顧客要求比較遠的 4 號箱子，如此一來造成了護衛效應，擋住了後面也許有機會服務更快的顧客。
讓我們再想想另外一個情形，當這個 worker 學乖了，他利用一個送貨區，當每次有太遠的貨物需要取貨時，他並不會自己慢慢跑過去，而是一通電話叫送貨人員送來。如此一來就可以更快的服務到其他顧客，與此同時目前顧客也不會因服務其他人而導致他的任務沒有進展。
而 NGINX 的 worker 也一樣，當一個進程可能需要很長的操作時間時，他不會自己處理，而是將這個任務放進 TaskQueue 中，而任何空閒的 Thread 都可將此 queue 中的任務取出來執行。
TasksQueue 以及 Thread Pool 在這邊扮演的角色就是送貨員以及送貨車，Taskqueue 會接收由 worker process 來的工作，處理完之後再把結果送回 worker process 中。
為了驗證這個事實，可以先使用以下命令
```
$ ps -ef --forest | grep nginx
root 1415 1 0 12:11 ? 00:00:00 nginx: master process /usr/sbin/nginx -g daemon on; master_process on;
www-data 1416 1415 0 12:11 ? 00:00:00 \_ nginx: worker process
www-data 1417 1415 0 12:11 ? 00:00:00 \_ nginx: worker process
www-data 1418 1415 0 12:11 ? 00:00:00 \_ nginx: worker process
www-data 1419 1415 0 12:11 ? 00:00:00 \_ nginx: worker process
www-data 1420 1415 0 12:11 ? 00:00:00 \_ nginx: worker process
www-data 1421 1415 0 12:11 ? 00:00:00 \_ nginx: worker process
www-data 1422 1415 0 12:11 ? 00:00:00 \_ nginx: worker process
www-data 1423 1415 0 12:11 ? 00:00:00 \_ nginx: worker process
```
數一下的確可發現 `nginx: worker process` 存在於 `nginx: master process` 底下。
##### cserv
cserv 也實作同樣的主從式架構，但與 NGINX 相異處在於 cserv 以 coroutine 作到 cooperative multitasking 以達到相對高效的結果。
* [cooperative multitasking](https://en.wikipedia.org/wiki/Cooperative_multitasking) 會要求每一個運行中的程式，定時放棄自己的執行權利，告知作業系統可讓下一個程式執行。相較於 preemptive multitasking，減少了作業系統需要進行 context switch 的頻率，因此效能可以大大提升。
:::danger
cooperative multitasking 和「相對高效」的關聯在哪？
:::
cserv 也有 worker
```c
// src/process.c
void process_init()
{
...
for (int i = 0; i < g_worker_processes; i++) {
struct process *p = &worker[i];
p->pid = INVALID_PID;
p->cpuid = i % get_ncpu();
}
}
```
可以從 `process_init()` 這個函式中看到此 worker 一開始被分配到不同的 cpu 底下，由此可以得知 cserv 中也有 worker process。
:::warning
每個 process 只有一個 thread => 沒有 thread-pool 設計
:::
### 測試環境
```bash
$ cat /etc/os-release
NAME="Ubuntu"
VERSION_ID="24.04"
VERSION="24.04 LTS (Noble Numbat)"
$ lscpu
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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-7700 CPU @ 3.60GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 9
CPU(s) scaling MHz: 19%
CPU max MHz: 4200.0000
CPU min MHz: 800.0000
BogoMIPS: 7200.00
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 8 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-7
```
### 壓力測試與比較
評測工具：
* [ab](https://httpd.apache.org/docs/current/programs/ab.html)
* [htstress](https://github.com/sysprog21/khttpd/blob/master/htstress.c)
* [httperf](https://github.com/httperf/httperf)
### 評測結果
#### ab
100000 requests with 500 requests at a time(concurrency)
`ab -n 100000 -c 500 -k http://127.0.0.1:8081/`
| | Requests per sec | Time per request (mean, across all concurrent requests) |
| -------- | -------- | -------- |
| cserv | 26123.73 [#/sec] | 0.038 [ms] |
| nginx | 35381.40 [#/sec] | 0.028 [ms] |
在嘗試執行 nginx 時有發生 `nginx: [emerg] still could not bind()` 的問題，從 `/etc/nginx/nginx.conf` 路徑查看 conf 檔案發現 nginx 預設的 port number 為`80`，可能的問題為此 port number 被佔用了。
可以透過 `netstat -ntlp|grep 80` 命令去查看指定的 port number 是否被佔用，所以我更改 `nginx.conf` 檔案中的預設 port number 為`8080`即可解決問題。
#### htstress
100000 requests with 500 requests at a time(concurrency)
`./htstress -n 100000 -c 500 127.0.0.1:8081/`
| | requests/sec | total time |
| -------- | -------- | -------- |
| cserv | 22771.289 #/sec | 4.391 s |
| nginx | 16535.379 #/sec | 6.048 s |
#### httperf
total 100000 requests with 500 connections
`httperf --server 127.0.0.1 --port 8081 --num-conn 500 --num-call 200 --http-version 1.0`
| | requests/sec | connection rate |
| -------- | -------- | -------- |
| cserv | 19140.9 #/sec | 9570.4 conn/s |
| nginx | 38758.8 #/sec | 193.8 conn/s |
:::info
在第三個 httperf 評測工具測試出來的結果讓我有些困惑，對比 [ktcp](https://hackmd.io/@sysprog/linux2024-ktcp/%2F%40sysprog%2Flinux2024-ktcp-d#%E5%A3%93%E5%8A%9B%E6%B8%AC%E8%A9%A6%E8%88%87%E6%AF%94%E8%BC%83) 中壓力測試的結果，nginx 的 connection rate 只有193.8，相較於 cserv 來說是不穩定的，但每一秒接收的 request 卻大於 cserv 每一秒接收到的 request。
:::
:::danger
從實驗結果，搭配設計架構去解讀為何如此。
:::
## TODO: 研讀[第 8 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz8) 和[並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency-sched)，紀錄你的認知和提問
> 注意看 neco，是 M:N threading model
### [第 8 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz8)
[task](https://gist.github.com/jserv/745dab1d9be33a9a635b193aeb53191e) 是個運用 coroutine 實作的任務排程器，針對 `AAAA`, `BBBB` 以及 `CCCC`的主要函式分別進行探討。
#### `task_lock`
這個函式實作了 spinlock，確保多個 thread 不會同時進入 critical section，利用 `task_locker` 來控制 lock 的狀態。
:::danger
你要討論 coroutine 如何搭配 POSIX Thread 使用，留意 stackful vs. stackless
詳見 [並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-sched)，留意 `__thread` (thread-local storage; tls) 的運用。
:::
使用 `atomic_compare_exchange_weak` 嘗試將 `task_locker` 的值從 false 變成 true，如果交換失敗表示 lock 目前已經被佔用，就會<s>調用</s> 呼叫 `sched_yield0()` 讓出 CPU。
:::danger
注意用語：
* call 是「呼叫」，而非「調用」
>已修正
:::
:::danger
不該急著對原始程式碼逐行解讀，你應該揣摩程式設計者的想法，給予高階的描述，特別著重於「要解決什麼問題？」
盲目解釋程式碼，可能會淪落到「舉燭」。
:::
```c
// task.c
static void task_lock(void)
{
bool expected = false;
while (!atomic_compare_exchange_weak(&task_locker, &expected, true)) {
expected = false;
sched_yield0();
}
}
```
#### `task_unlock`
釋放 spinlock，所以 `AAAA` 應該要設置為 false，表示 lock 被釋放。
```c
static void task_unlock(void)
{
atomic_store(&task_locker, AAAA);
}
```
#### `task_entry`
這個函式的目的是初始話並執行一個新的 coroutine。
:::danger
不用抄寫 AAAA, BBBB, CCCC 等填空項目，你專注在程式碼本身。
:::
`BBBB` 是一個 atomic 的操作，參閱 [Atomic library](https://en.cppreference.com/w/c/atomic) 後可以得知 `BBBB` 應填入 `atomic_fetch_add`，用來確保分配給 coroutine 的 ID 具有唯一性以及 thread 的安全。
當 coroutine 完成工作時，使用 `task_switch` 函式進行 context switch，所以 `CCCC` 用來表示這次切換是否是最終的切換，所以應該填入 true 表示 coroutine 結束。
```c
tatic void task_entry(void *udata)
{
/* Initialize a new coroutine on the user's stack. */
struct task task_stk = {0};
struct task *co = &task_stk;
co->llco = coro_current();
co->id = BBBB(&task_next_id, 1) + 1;
co->udata = udata;
co->prev = co;
co->next = co;
if (task_cur) {
/* Reschedule the coroutine that started this one */
task_list_push_back(&task_yielders, co);
task_list_push_back(&task_yielders, task_cur);
task_nyielders += 2;
task_switch(false, false);
}
task_cur = co;
if (task_user_entry) {
task_user_entry(udata);
}
/* This coroutine is finished. Switch to the next coroutine. */
task_switch(false, CCCC);
}
```
而 `task_test.c` 針對 coroutine 的基本操作和特性進行測試，確保系統在不同情況下都能正常運行，測試內容包含 coroutine 的 `test_task_start`, `test_task_sleep`, `tesk_task_pause`, `test_task_detach`, `test_task_exit`,`test_task_order` 以及 `test_task_detach`。
:::danger
上面程式碼給你什麼啟發？融合 coroutine 和 pthread，對於設計高性能網頁伺服器的助益是什麼？
:::
### [並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency-sched)
在閱讀完 coroutine 的部份時，其實對於 coroutine 與 thread 的差異還很難區分
在什情況下應該要使用 coroutine 而不是 thread？
:::danger
你看了解說錄影嗎？告訴我哪個時間段不理解。
:::
<s>
之後另外閱讀到一份教材 [coroutine](https://hackmd.io/@YLowy/HkT8-S20D) 有解釋 coroutine 與 thread 之間的差異為何，也有針對我的疑問給出了解答。
</s>
:::danger
為何不讀授課教師編撰的《Demystifying the Linux CPU Scheduler》？寫書就是你們理解結構清晰的知識，結果時間花在 Google 搜尋找他人的隻字片語，何必呢！
:::
#### Coroutine vs. Thread
| Coroutine | Thread |
| -------- | -------- |
| 使用non-preemptive multitasking，這意味著 coroutine 會自行決定何時讓出控制權給其他 coroutine | 使用preemptive multitasking，這意味著作業系統會定期切換 thread，以確保每個 thread 都有機會運行。 |
| 適合用於 I/O 密集型任務，例如 web request，因為 coroutine 可以在等待 I/O 操作完成時讓出控制權，從而提高 CPU 利用率。| 適合 CPU 密集型任務和需要利用多核 CPU 的情境 |
:::danger
注意用語，務必使用本課程教材規範的詞彙。
:::
:::danger
coroutine 亦可做到 preemptive scheduling，參見上方教材。不要淪落為「搬運工」，要能判斷和驗證資訊本身。
:::
<s>
統整 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 的幾點特性:
* 跟 thread 很像，但是採用 cooperative multitasking 而非 preemptively multitasking
* 擁有自己的 stack 跟 program counter
* 可以利用 dispatcher 輕易的在 thread 之間轉換
* 可以中斷並且繼續執行，跟一般的函式不同
* 是一種在 multi-threading 普及之前產生的概念，優點是不會產生 race-condition
* 通常由 user 控制
</s>
:::danger
使用本課程的教材，注意 Wikipedia 只是介紹通例，不該在沒有驗證的狀況下，全盤接受其說法，否則只是人云亦云。
[並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency-sched)裡頭就有 preemptive coroutine 程式碼，為何你不實際執行呢？
:::
#### neco
[neco](https://github.com/tidwall/neco) 是個 C 語言撰寫的函式庫，藉由 coroutine 提供並行處理功能。它體積小且速度快，旨在降低並行 I/O 和網路程式設計的難度。建構於以下元件：
* [llco](https://github.com/tidwall/llco): low-level coroutine
* [sco](https://github.com/tidwall/sco): coroutine scheduler
特色：
* coroutine: 啟動、休眠、暫停、恢復、建立和收合
* 同步處理：channels, generators, mutexes, condition variables, 和 waitgroups
* coroutine 生命週期由內建的排程器管理
* 快速的使用者層級的上下文切換
* stackful coroutine，可支援巢狀執行
閱讀 `neco.c` 並找出其中實施 multithread 的部份。
:::danger
neco 要解決什麼問題？
:::
##### 結構體定義
首先在 `worker_opts` 結構體中定義了一個 worker process 最多可以有幾個 thread 以及 thread entry
```c
// deps/worker.c
#define WORKER_DEF_MAX_THREADS 2
#define WORKER_DEF_MAX_THREAD_ENTRIES 32
struct worker_opts {
int max_threads; // def: 2
int max_thread_entries; // def: 32
int64_t thread_timeout; // nanoseconds, def: 1 second
void*(*malloc)(size_t); // def: system malloc
void(*free)(void*); // def: system free
};
```
定義 `worker` 結構體來管理多個 worker threads
```c
struct worker {
int nthreads;
struct worker_thread **threads;
void (*free)(void*);
};
```
##### `worker_free`
首先檢查 worker 是否為空，以確保有 thread 可以釋放，如果為空則進入迴圈遍歷每個 thread。
針對每個 thread，先使用 `pthread_mutex_lock` 鎖定狀態，標記 thread 結束後通過 `pthread_cond_signal` 發送訊號通另外一個正在處於阻塞等待狀態的線程，使其脫離阻塞狀態。
隨後 `pthread_mutex_unlock` 解鎖並等待 thread 退出。
```c
void worker_free(struct worker *worker)
{
if (worker) {
if (worker->threads) {
for (int i = 0; i < worker->nthreads; i++) {
struct worker_thread *thread = worker->threads[i];
if (thread) {
pthread_mutex_lock(&thread->mu);
thread->end = true;
pthread_t th = thread->th;
pthread_cond_signal(&thread->cond);
pthread_mutex_unlock(&thread->mu);
if (th) {
pthread_join(th, 0);
}
worker->free(thread->entries);
worker->free(thread);
}
}
worker->free(worker->threads);
}
worker->free(worker);
}
}
```
##### `worker_new`
此函式主要目的是 `malloc` 一個 `worker` 結構體，並初始化其中的 worker threads 及其他相關資源。
```c
struct worker *worker_new(struct worker_opts *opts)
{
...
for (int i = 0; i < worker->nthreads; i++) {
struct worker_thread *thread = malloc_(sizeof(struct worker_thread));
if (!thread) {
worker_free(worker);
return NULL;
}
memset(thread, 0, sizeof(struct worker_thread));
worker->threads[i] = thread;
thread->timeout = timeout;
thread->nentries = nentries;
thread->entries = malloc_(sizeof(struct worker_entry) * nentries);
if (!thread->entries) {
worker_free(worker);
return NULL;
}
memset(thread->entries, 0, sizeof(struct worker_entry) * nentries);
pthread_mutex_init(&thread->mu, 0);
pthread_cond_init(&thread->cond, 0);
thread->nentries = nentries;
}
return worker;
}
```
##### `worker_entry`
當 `thread->len > 0`時，表示 thread 中還有任務尚未處理完成，從 `thread->entries` 中取出下一個要處理的任務，並更新 `thread->pos` 指向下一個位址，如果 `thread->pos` 達到上限則重置為0。
當 `thread->len == 0` 時，表示沒有待處理的工作。使用 `clock_gettime` 獲取當前時間，並將超時時間設置為1秒後。
如果在超時前收到訊號（即有新的工作近來），則會重新把 thread lock 起來，結束之後再跳出迴圈結束工作。
```c
while (1) {
while (thread->len > 0) {
struct worker_entry entry = thread->entries[thread->pos];
thread->pos++;
if (thread->pos == thread->nentries) {
thread->pos = 0;
}
thread->len--;
pthread_mutex_unlock(&thread->mu);
if (entry.work) {
entry.work(entry.udata);
}
pthread_mutex_lock(&thread->mu);
}
struct timespec ts;
clock_gettime(CLOCK_REALTIME, &ts);
ts.tv_sec += 1;
pthread_cond_timedwait(&thread->cond, &thread->mu, &ts);
if (thread->len == 0) {
if (!thread->end) {
pthread_detach(thread->th);
}
thread->th = 0;
thread->end = false;
break;
}
}
```
##### `worker_submit`
此函式目的在於指派 worker 工作任務，根據計算出來的 `pin` 值和 worker 中 thread 數量，決定一個適當的目標 thread。
`thread->len < thread->nentries` 用來判斷此 thread 的 thread entry 是否已滿，若此條件成立表示可以提交新的工作任務。
計算下一個可用位置 `pos`，將 `work` 和 `udata` 存入 `thread->entries` 中，並將 thread 的長度加1表示新增了一個工作任務。
```c
bool worker_submit(struct worker *worker, int64_t pin, void(*work)(void *udata),
void *udata)
{
if (!worker || !work) {
return false;
}
static __thread uint32_t worker_next_index = 0;
if (pin < 0) {
pin = worker_next_index;
}
worker_next_index++;
struct worker_thread *thread = worker->threads[pin%worker->nthreads];
bool submitted = false;
pthread_mutex_lock(&thread->mu);
if (thread->len < thread->nentries) {
int pos = thread->pos + thread->len;
if (pos >= thread->nentries) {
pos -= thread->nentries;
}
thread->entries[pos].work = work;
thread->entries[pos].udata = udata;
thread->len++;
if (!thread->th) {
int ret = pthread_create(&thread->th, 0, worker_entry, thread);
if (ret == -1) {
pthread_mutex_unlock(&thread->mu);
return false;
}
}
submitted = true;
pthread_cond_signal(&thread->cond);
}
pthread_mutex_unlock(&thread->mu);
return submitted;
}
```
## TODO: 改寫 cserv，使得其具備 M:N threading model
> 進行效能評比和解讀
Sign in with Wallet
Connect another wallet