CSAPP 并发编程读书笔记

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/多线程/