Linux 核心專題: 高效網頁伺服器

執行人: Hualing-Chiu
專題解說影片

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 開發日誌中以送貨員以及排隊等候的機制去看待這個問題

假設有一堆顧客，他們需要取貨，而有些貨物(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 會要求每一個運行中的程式，定時放棄自己的執行權利，告知作業系統可讓下一個程式執行。相較於 preemptive multitasking，減少了作業系統需要進行 context switch 的頻率，因此效能可以大大提升。

cooperative multitasking 和「相對高效」的關聯在哪？

cserv 也有 worker

// 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。

每個 process 只有一個 thread => 沒有 thread-pool 設計

測試環境

$ 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
• htstress
• 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

在第三個 httperf 評測工具測試出來的結果讓我有些困惑，對比 ktcp 中壓力測試的結果，nginx 的 connection rate 只有193.8，相較於 cserv 來說是不穩定的，但每一秒接收的 request 卻大於 cserv 每一秒接收到的 request。

從實驗結果，搭配設計架構去解讀為何如此。

TODO: 研讀第 8 週測驗題 和並行程式設計: 排程器原理，紀錄你的認知和提問

注意看 neco，是 M:N threading model

第 8 週測驗題

task 是個運用 coroutine 實作的任務排程器，針對 AAAA, BBBB 以及 CCCC的主要函式分別進行探討。

task_lock

這個函式實作了 spinlock，確保多個 thread 不會同時進入 critical section，利用 task_locker 來控制 lock 的狀態。

你要討論 coroutine 如何搭配 POSIX Thread 使用，留意 stackful vs. stackless

詳見 並行程式設計: 排程器原理，留意 __thread (thread-local storage; tls) 的運用。

使用 atomic_compare_exchange_weak 嘗試將 task_locker 的值從 false 變成 true，如果交換失敗表示 lock 目前已經被佔用，就會調用 呼叫 sched_yield0() 讓出 CPU。

注意用語：

• call 是「呼叫」，而非「調用」

已修正

不該急著對原始程式碼逐行解讀，你應該揣摩程式設計者的想法，給予高階的描述，特別著重於「要解決什麼問題？」

盲目解釋程式碼，可能會淪落到「舉燭」。

// 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 被釋放。

static void task_unlock(void)
{
    atomic_store(&task_locker, AAAA);
}

task_entry

這個函式的目的是初始話並執行一個新的 coroutine。

不用抄寫 AAAA, BBBB, CCCC 等填空項目，你專注在程式碼本身。

BBBB 是一個 atomic 的操作，參閱 Atomic library 後可以得知 BBBB 應填入 atomic_fetch_add，用來確保分配給 coroutine 的 ID 具有唯一性以及 thread 的安全。

當 coroutine 完成工作時，使用 task_switch 函式進行 context switch，所以 CCCC 用來表示這次切換是否是最終的切換，所以應該填入 true 表示 coroutine 結束。

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。

上面程式碼給你什麼啟發？融合 coroutine 和 pthread，對於設計高性能網頁伺服器的助益是什麼？

並行程式設計: 排程器原理

在閱讀完 coroutine 的部份時，其實對於 coroutine 與 thread 的差異還很難區分

在什情況下應該要使用 coroutine 而不是 thread？

你看了解說錄影嗎？告訴我哪個時間段不理解。

之後另外閱讀到一份教材 [coroutine](https://hackmd.io/@YLowy/HkT8-S20D) 有解釋 coroutine 與 thread 之間的差異為何，也有針對我的疑問給出了解答。

為何不讀授課教師編撰的《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 的情境

注意用語，務必使用本課程教材規範的詞彙。

coroutine 亦可做到 preemptive scheduling，參見上方教材。不要淪落為「搬運工」，要能判斷和驗證資訊本身。

統整 [coroutine](https://en.wikipedia.org/wiki/Coroutine) 的幾點特性: * 跟 thread 很像，但是採用 cooperative multitasking 而非 preemptively multitasking * 擁有自己的 stack 跟 program counter * 可以利用 dispatcher 輕易的在 thread 之間轉換 * 可以中斷並且繼續執行，跟一般的函式不同 * 是一種在 multi-threading 普及之前產生的概念，優點是不會產生 race-condition * 通常由 user 控制

使用本課程的教材，注意 Wikipedia 只是介紹通例，不該在沒有驗證的狀況下，全盤接受其說法，否則只是人云亦云。

並行程式設計: 排程器原理裡頭就有 preemptive coroutine 程式碼，為何你不實際執行呢？

neco

neco 是個 C 語言撰寫的函式庫，藉由 coroutine 提供並行處理功能。它體積小且速度快，旨在降低並行 I/O 和網路程式設計的難度。建構於以下元件：

• llco: low-level coroutine
• sco: coroutine scheduler

特色：

• coroutine: 啟動、休眠、暫停、恢復、建立和收合
• 同步處理：channels, generators, mutexes, condition variables, 和 waitgroups
• coroutine 生命週期由內建的排程器管理
• 快速的使用者層級的上下文切換
• stackful coroutine，可支援巢狀執行

閱讀 neco.c 並找出其中實施 multithread 的部份。

neco 要解決什麼問題？

結構體定義

首先在 worker_opts 結構體中定義了一個 worker process 最多可以有幾個 thread 以及 thread entry

// 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

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 退出。

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 及其他相關資源。

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 起來，結束之後再跳出迴圈結束工作。

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表示新增了一個工作任務。

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

進行效能評比和解讀