CSAPP 第十二章 并发编程

发表于 | 分类于

早睡早起，坚持锻炼。

1. IO多路复用

异步编程: 使用select函数，要求内核挂起进程。只有在一个或多个IO事件发生后，才将控制返回给应用程序。不利于使用多核。

2. 线程

2.1. 线程模型

  • 每个进程生命周期开始时都是单一线程。之后某一时刻，主线程创建一个对等线程（peer thread）。之后，两个线程就并发执行。
  • 线程不是严格按照父子层次来组织的，和进程相关的每一个线程组成一个对等的线程池。

2.2. Posix线程

创建线程

1
2
3
4
5
#include <pthread.h>
typedef void *(func)(void *);

int pthread_create(pthread_t *tid, pthread_attr_t *attr,
                   func *f, void *arg);

终止线程

一个线程会在下面的情况下被终止

  • 当顶层线程例程返回时，线程会隐式终止
  • pthread_exit会显示终止线程
    • 若主线程调用pthread_exit，它会等待其它所有线程终止然后再终止主线程和整个进程
  • 某个对等线程调用exit会终止整个进程
  • 另一个对等线程调用pthread_cancel可以终止当前线程
1
2
3
#include <pthread.h>

void pthread_exit(void *thread_return);

回收已终止线程的资源

1
2
3
#include <pthread.h>

int pthread_join(pthread_t tid, void **thread_return);

注意: pthread_join只能等待指定线程的终止，无法等待任意线程的终止。

分离线程

在任何时刻，有两种线程

  • 可结合的（joinable）: 能够被其它线程回收和杀死，在被其它线程回收资源之前，它的内存资源不释放
  • 分离的（detached）: 不能被其它线程回收和杀死，它的内存资源在它终止时由系统自动释放

pthread_detach用于分离可结合线程tid，参数主要通过pthread_self获取。

1
2
3
#include <pthread.h>

pthread_detach(pthread_t tid);

初始化线程

pthread_once主要用于动态初始化多个线程共享的全局变量。

once_control全局变量总是被初始化为PTHREAD_ONCE_INIT。当第一次用该参数调用pthread_once时，它会调用init_routine函数（无参数也无返回值），之后以once_control为参数对pthread_once的调用则什么也不干。

1
2
3
4
5
6
#include <pthread.h>

pthread_once_t once_control = PTHREAD_ONCE_INIT;

int pthread_once(pthread_once_t *once_control,
                 void (*init_routine)(void));

3. 用信号量同步线程

3.1. 生产者-消费者问题

使用三个信号量，一个作为互斥锁保证对缓冲区的互斥访问，另外两个记录空槽位和可用项目的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
typedef struct {
    int *buf;       /* Buffer array */
    int n;          /* Maximum number of slots */
    int front;      /* buf[(front+1)%n] is first item */
    int rear;       /* buf[rear%n] is last item */
    sem_t mutex;    /* Protects access to buf */
    sem_t slots;    /* Counts available slots */
    sem_t items;    /* Counts available items */
} sbuf_t;

void sbuf_init(sbuf_t *, int);
void sbuf_free(sbuf_t *);
void sbuf_insert(sbuf_t *, int);
int sbuf_remove(sbuf_t *)

/* Create an empty, bounded, shared FIFO buffer with n slots */
void sbuf_init(sbuf_t *sp, int n)
{
    sp->buf = Calloc(n, sizeof(int));
    sp->n = n;
    sp->front = sp->rear = 0;
    Sem_init(&sp->mutex, 0, 1);
    Sem_init(&sp->slots, 0, n);
    Sem_init(&sp->items, 0, 0);
}

/* Clean up buffer sp */
void sbuf_free(sbuf_t *sp)
{
    Free(sp->buf);
}

/* Insert an item onto the rear of shared buffer sp */
void sbuf_insert(sbuf_t *sp, int item)
{
    P(&sp->slots);
    P(&sp->mutex);
    sp->buf[(++sp->rear)%(sp->n)] = item;
    V(&sp->mutex);
    V(&sp->items);
}

/* Remove and return the first item from buffer sp */
int sbuf_remove(sbuf_t *sp)
{
    int item;
    P(&sp->items);
    P(&sp->mutex);
    item = sp->buf[(++sp->front)%(sp->n)];
    V(&sp->mutex);
    V(&sp->slots);
    return item;
}

3.2. 读写者问题

读者优先

使用共享变量readcnt，通过互斥锁保护，记录读者数量。另外使用writer互斥锁保证写者唯一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int readcnt;
sem_t mutex, w; // 初始化为1

void reader（void)
{
  while (1) {
    P(&mutex);
    readcnt++;
    if (readcnt == 1)
      P(&w);
    V(&mutex);
    // 读操作
    P(&mutex);
    readcnt--;
    if (readcnt == 0)
      V(&w)
    V(&mutex);
  }
}

void writer(void)
{
  while (1) {
    P(&w);
    // 写操作
    V(&w);
  }
}

4. 线程级并行: 性能

强扩展公式

$S_p = \frac{T_1}{T_p}$

  • $T_k$: k个核上的运行时间
  • 绝对加速比: 当$T_1$表示顺序执行版本的执行时间
  • 相对加速比: 当$T_1$表示并行版本在单个核上的执行时间

效率

$E_p = \frac{S_p}{p} = \frac{T_1}{pT_p}$

具有高效率的程序有效工作时间所占百分比更长。可以衡量并行化造成的开销。

弱扩展

增加处理器数量的同时，增加问题的规模。此时的加速比和效率表达为单位时间完成的工作总量。例如: 处理器数量翻倍，同时单位时间处理两倍工作量，则有线性的加速比和100%的效率。

5. 并发问题

5.1. 线程安全

一个函数是线程安全的，当且仅当被多个并发线程反复调用时，它会一直产生正确的结果。

以下是四种线程不安全函数类

  • 不保护共享变量的函数
  • 保持跨越多个调用的状态的函数
    • 例如: 使用函数内部的静态变量或全局变量
  • 返回指向静态变量的指针的函数
    • 例如: ctime和gethostbyname
    • 应对: 加锁-复制技术，在每一个调用线程不安全函数位置对互斥锁加锁，将函数返回结果复制到一个私有内存位置，然后对互斥锁解锁
  • 调用线程不安全函数的函数

5.2. 可重入性

可重入函数: 当它们被多个线程调用时，不会引用任何共享数据。

注意: 可重入函数集合是线程安全函数的一个真子集。即可重入函数一定线程安全，但是线程安全函数不一定是可重入的。

  • 显式可重入函数: 所有数据引用都是本地的自动栈变量，没有引用静态或全局变量。
  • 隐式可重入函数: 指针作为参数传递，若调用线程保证指针指向非共享数据，则可重入。

5.3. 竞争

竞争: 一个程序的正确性依赖于一个线程要在另一个线程到达y点之前到达它控制流中的x点。

例如: 多个线程对同一个共享变量的更新。

5.4. 死锁

死锁: 一组线程被阻塞，等待一个永远也不会为真的条件。