CSAPP 并發編程筆記

并發和并行

• 并發：Concurrency，只要時間上重疊就算并發，可以是單處理器交替處理
• 并行：Parallel，屬于并發的一種特殊情況（真子集），多核/多 CPU 同時處理

構造并發程式的方法

現代作業系統提供了 3 種基本的構造并發程式的方法：

• 行程：每個邏輯控制流都是一個行程，由內核調度和維護，
• I/O 多路復用 ：在一個行程背景關系中顯式地調度他們自己的邏輯流，邏輯流被模型化為狀態機，
• 執行緒：運行在單一行程背景關系中的邏輯流，由內核進行調度，可以看作上面兩種方式的混合體（內核調度，但共享同一虛擬地址空間），

12.1 基于行程的并發編程

示例代碼

void sigchld_handler(int sig)
{
    while(waitpid(-1, 0, WNOHANG) > 0) 
        ;
}

int main()
{
    signal(SIGCHLD, sigchld_handler); // 回收僵死子行程資源
    listenfd = open_listenfd();
    while (1) {
      connfd = accept(...);
      if (fork() == 0) { // 子行程
        close(listenfd); // 關閉父行程 fd，不關閉問題不大，子行程結束時自動關閉
        process(connfd);
        close(connfd);
        exit(0);
      }
      close(connfd); // 父行程關閉 fd，重要！否則永遠不會釋放 connfd 連接描述符，導致記憶體泄漏！
    }
}

父、子行程中的已連接描述符都指向同一個檔案表表項，所以父行程關閉 connfd 至關重要，否則，永遠不會釋放已連接描述符 4 connfd 的檔案表條目，引起記憶體泄漏，因為 socket 檔案表表項中的參考計數，直到父子行程 connfd 都關閉了，到客戶端的連接才會終止，

行程并發優缺點

共享檔案表，但不共享地址空間（是優點，也是缺點），不方便共享資料，只能通過顯式 IPC，行程控制和 IPC 開銷大，

12.2 基于 I/O 多路復用的并發編程

背景知識

通過 select 函式，等待一組描述符 ready，

#include <sys/select.h>
int select(int n, fd_set *fdset, NULL, NULL, NULL); // 回傳 ready fd 的個數，出錯回傳 -1

FD_ZERO(fd_set *fdset);
FD_CLR(int fd, fd_set *fdset);
FD_SET(int fd, fd_set *fdset);
FD_ISSET(int fd, fd_set *fdset);

select 阻塞，直到至少一個 fd ready（即讀取一個位元組不阻塞）

示例代碼

注意：select 有副作用，會修改入參 fdset 的內容！

fd_set read_set;
FD_ZERO(&read_set);
FD_SET(STDIN_FILENO, &read_set);
FD_SET(listenfd, &read_set);

while(1) {
  fd_set ready_set = read_set; // 因為 select 會修改入參 read_set 的內容，每次都重新從 read_set 拷貝！
  select(listenfd+1, &ready_set, NULL, NULL, NULL);
  if(FD_ISSET(STDIN_FILENO, &ready_set)
     // ...
  if(FD_ISSET(listenfd, &ready_set)
     // ...
}

I/O 多路復用優缺點

• 單一行程背景關系，共享資料容易，

• 事件驅動，不需要背景關系切換，高效，有明顯的性能優勢，

• 編碼復雜

• 不能充分利用多核處理器

因為明顯的性能優勢，現代高性能服務器如 Node.js、nginx 和 Tornado 都是基于 I/O 多路復用的事件驅動

12.3 基于執行緒的并發編程

背景知識

# include <pthread.h>
typedef void *(func)(void *);

// 創建執行緒
int pthread_create(pthread_t *tid, pthread_attr_t *attr, func *f, void *arg);
// 回傳呼叫者執行緒 ID
pthread_t pthread_self();
// 顯示終止執行緒（threadFunc 回傳即隱式終止），如果主執行緒呼叫，則等待所有其他對等執行緒終止，再終止主執行緒和整個行程
void pthread_exit(void *thread_return);
// 對等執行緒以當前執行緒 ID 作為引數，呼叫 pthread_cancel 來終止當前執行緒
int pthread_cancel(pthread_t tid); // 成功回傳 0
// 回收已終止執行緒的資源
int pthread_join(pthread_t tid, void **thread_return); // 阻塞直到 tid 終止，成功回傳 0
// 分離執行緒
int pthread_detach(pthread_t tid); // 成功回傳 0
// 初始化執行緒 （可以用來實作單例模式）
pthread_once_t once = PTHREAD_ONCE_INIT; // 必須是全域或者靜態變數，固定初始化為 PTHREAD_ONCE_INIT（主要用其地址）
int pthread_once(pthread_once_t *once_control, void(*init_routine)(void));

執行緒由內核自動調度，每個執行緒有自己的執行緒背景關系，

執行緒背景關系：執行緒 ID（TID）、堆疊、堆疊指標、程式計數器、通用目的暫存器和條件碼，

示例代碼

while (1) {
  pConnfd = new int();
  *pConnfd = accept(...);
  pthread_create(&tid, NULL, threadFunc, pConnfd);
}

void* threadFunc(void* p)
{
  int connfd = *p;
  pthread_detach(pthread_self());
  free(p);
}

為了避免 race condition，connfd 必須在堆中創建，在執行緒中釋放，而不能直接把 connfd 的地址傳給 threadFunc！

12.4 多執行緒共享變數

執行緒記憶體模型

• 每個執行緒有獨立的執行緒背景關系，共享行程背景關系其余部分，包括整個用戶虛擬地址空間：只讀文本（代碼.text）、讀/寫資料（.bss & .data）、堆、共享庫代碼和資料，
• 執行緒堆疊不對其他執行緒設防，

將變數映射到記憶體

• 全域變數：定義在函式之外，僅一個實體@虛擬記憶體讀/寫區
• 本地自動變數：定義在函式內，且沒有 static，@虛擬記憶體執行緒堆疊
• 本地靜態變數：定義在函式內，并有 static，僅一個實體@虛擬記憶體讀/寫區

C++11 thread_local 存在哪里？

12.5 信號量

背景知識

• cnt++ 可以細分 3 個子步驟：加載 L、更新 U、儲存 S，這三個動作必須一次性完成，不可中斷，
• 進度圖不適用于多處理器，
• P(s)：若 s 非零，則 s 減 1，立即回傳，若 s 為零，掛起執行緒，直到 s 變為非零，然后將 s 減 1 回傳，
• V(s)：將 s 加 1，如果有執行緒阻塞，則喚醒這些執行緒中的某一個，
• P、V 的加一減一的操作都是原子操作，即 L、U、S 的程序沒有中斷，
• 如果有多個執行緒再等待喚醒，V(s) 只能隨機喚醒一個執行緒，不能指定喚醒哪個執行緒，

#include <semaphore.h>

// 成功回傳 0，出錯回傳 -1
int sem_init(sem_t *sem, 0, unsigned int value);
int sem_wait(sem_t *sem);  // P(s) 如果 s 為 0，掛起，直到 s 變為非零，V 操作可以重啟這個執行緒，
int sem_post(sem_t *sem);  // V(s)

生產者-消費者

int buf[N]; // 理解成 queue<int>
sem_t mutex, slots, items;

void init(int n)
{
    sem_init(&mutex, 0, 1);
    sem_init(&slots, 0, n);
    sem_init(&items, 0, 0);
}

void producer(T item)
{
    sem_wait(&slots)
    sem_wait(&mutex);
    // insert item into buf
    sem_post(&mutex);
    sem_post(&items);
}

T consumer()
{
    T item;
    sem_wait(&items);
    sem_wait(&mutex);
    // pop item from buf
    sem_post(&mutex);
    sem_post(&slots);
    return item;
}

讀者-寫者

讀者、寫者平等地爭奪 w，一旦讀者獲取了 w，將一直占有 w，直到最后一個讀者離開，釋放 w，

如果讀者不斷到達，寫者可能無限等待，導致饑餓，

以下是一個讀者優先的例子，（弱優先級，當最后一個讀者釋放 w，下一個獲取 w 的不一定是等待 w 的讀者，也有可能是等待 w 的寫者！）

int readcnt = 0;
sem_t mutex; // 保護 readcnt
sem_t w;     // 讀者或寫者搶占 w

void init()
{
    sem_init(&mutex, 0, 1);
    sem_init(&w, 0, 1);
}

void reader()
{
    while(1)
    {
        sem_wait(&mutex);
        readcnt++;
        if(readcnt == 1)
            sem_wait(&w); // 如果這是第一個讀者，搶占 w
        sem_post(&mutex);
      
        // Critical section
        // Reading...
      
        sem_wait(&mutex);
        readcnt--;
        if(readcnt == 0)
            sem_post(&w); // 如果這是最后一個讀者，釋放 w
        sem_post(&mutex);
    }
}

void writer()
{
    while(1)
    {
        sem_wait(&w);
            
        // Critical section
        // Writing...
        
        sem_post(&w);
    }
}

綜合：基于預執行緒化的并發服務器

很好的例子，結合上述多種方式的優點，建議親自寫一遍，代碼參考 CSAPP，不再贅述，

12.6 使用執行緒提高并行性

通用技術：向對等執行緒傳遞一個小整數，作為唯一的執行緒 ID，每個對等執行緒根據執行緒 ID 來決定它應該計算序列的哪一部分，

通常每個核上運行一個執行緒，在一個核上運行運行多個執行緒會有額外的背景關系切換開銷，

多執行緒求和的例子：

// 加鎖操作全域變數
void* sum_mutex(void* vargp)
{
    // 根據 vargp 確定計算范圍
    for(i=start; i<end; i++) {
        sem_wait(&mutex);
        gsum += i;
        sem_post(&mutex);
    }
    return NULL;
}

// 每個執行緒獨立位置存放結果，無需 mutex，直接累加到全域陣列，主執行緒等待所有子執行緒完成
void* sum_global(void* vargp)
{
    long threadId = *((long*) vargp);
    // 根據 vargp 確定計算范圍
    for(i=start; i<end; i++)
        gsum[threadId] += i;
    return NULL;
}

// 先用區域變數累加結果，減少不必要的記憶體參考，最后一次性賦給全域陣列
void* sum_local(void* vargp)
{
    // 根據 vargp 確定計算范圍
    int local_sum = 0;
    for(i=start; i<end; i++) {
        local_sum += i;
    }
    gsum[threadId] = local_sum;
    return NULL;
}

12.7 其他并發問題

執行緒安全

執行緒安全（thread-safe）：多個并發執行緒反復呼叫，結果正確

可重入（reentrant）：執行緒安全的真子集，不需要同步操作，比不可重入的執行緒安全的函式更高效，

四類不相交的執行緒不安全函式：

Linux 中執行緒不安全函式

大多數 Linux 函式都是執行緒安全的，包括定義在 C 庫中的函式（例如 malloc、free、realloc、printf、scanf）

死鎖

• 分析工具：進度圖
• 一個死鎖的例子：執行緒 A 持有 mutex1，等待 mutex2；執行緒 B 持有 mutex2，等待 mutex1
• 避免死鎖的最簡單方式——互斥鎖加鎖順序規則：給定所有互斥操作的一個全序，如果每個執行緒都是以一種順序獲得互斥鎖并以相反的順序釋放，那么這個程式就是無死鎖的，

注：現代 C++ 可以一次獲得多個鎖，從根源上避免了死鎖，

12.8 小結

• 并發：時間上重疊的邏輯流
• 三種并發機制：行程、I/O 多路復用和執行緒
  • 行程由內核調度，獨立虛擬地址空間，只能顯式 IPC 共享資料
  • 事件驅動程式有自己的并發邏輯流（模型化為狀態機），用 I/O 多路復用來顯式調度這些流
  • 執行緒：內核自動調度，單一行程背景關系
• 信號量解決共享資料的并發訪問問題，提供互斥訪問，也支持生產者-消費者、讀者-寫者
• 被執行緒呼叫的函式必須執行緒安全，有四類執行緒不安全的函式
• 可重入函數比不可重入函式更高效，因為不需要任何同步操作
• 小心競爭和死鎖

Reference

• CSAPP 并發編程讀書筆記

• 現代 C++ 對多執行緒/并發的支持 A Tour of C++（上）

• 現代 C++ 對多執行緒/并發的支持 A Tour of C++（下）

• https://www.cnblogs.com/tengzijian/tag/多執行緒/

標籤：其他

上一篇：上午在改BUG，下午就被通知優化了，給所有做測驗的朋友提個醒

下一篇：動作捕捉助力人-機運動協同性輔助側翻康復輔具設計