本节内容：基于锁的并发数据结构、条件变量、信号量、常见的IO模型、阻塞与非阻塞、同步与异步的区别

基于锁的并发数据结构

       懒惰计数器通过多个局部计数器和一个全局计数器来实现一个逻辑计数器，例如，在4个cpu的机器上，有4个局部计数器和一个全局计数器，还有锁：每个局部计数器有一个锁，全局计数器有一个。

       为了保持全局计数器更新，局部值会定期转移给全局计数器，方法是获取全局锁，让全局计数器加上局部计数器的值，然后将局部计数器置零。这种局部传全局的频度，取决于一个阈值S。S越小，惰性计数器则越趋近于非扩展的计数器。S越大，扩展性越强，但是全局计数器与实际计数的偏差越大。

       并发链表、队列（列头和列尾两个锁）、散列表（每个散列桶（每个桶是一个链表）都有一个锁）

       扩展链表，每个节点都有一个锁，更多并发。不一定更快，带来了大量的开销（频繁地获取锁、释放锁）

条件变量

       条件变量有两种相关的操作：wait()和signal()。线程要睡眠的时候，调用wait。当线程想唤醒等待在某个条件变量上的睡眠线程时，调用signal。

pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);

pthread_cond_signal(pthread_cond_t *c);

int done = 0;

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t c = PTHREAD_COND_INITIALIZER;

void thr_exit() {

Pthread_mutex_lock(&m);

done = 1;

Pthread_cond_signal(&c);

Pthread_mutex_unlock(&m);

}

void *child(void *arg) {

printf("child\n");

thr_exit();

return NULL;

}

void thr_join() {

Pthread_mutex_lock(&m);

while (done == 0)

Pthread_cond_wait(&c, &m);

Pthread_mutex_unlock(&m);

}

int main(int argc, char *argv[]) {

printf("parent: begin\n");

pthread_t p;

Pthread_create(&p, NULL, child, NULL);

thr_join();

printf("parent: end\n");

return 0;

}

第一种情况是父线程创建出子线程，但自己继续运行（假设只有一个处理器），然后马上调用thr_join()等待子线程。在这种情况下，它会先获取锁，检查子进程是否完成（还没有完成），然后调用wait()，让自己休眠。子线程最终得以运行，打印出“child”，并调用thr_exit()函数唤醒父进程，这段代码会在获得锁后设置状态变量done，然后向父线程发信号唤醒它。最后，父线程会运行（从wait()调用返回并持有锁），释放锁，打印出“parent:end”。

第二种情况是，子线程在创建后，立刻运行，设置变量done 为1，调用signal 函数唤醒其他线程（这里没有其他线程），然后结束。父线程运行后，调用thr_join()时，发现done 已经是1 了，就直接返回。

wait()强制要求持有锁，signal()最好持有锁。

生产者/消费者（有界缓冲区）问题

cond_t cond;

mutex_t mutex;

void *producer(void *arg) {

int i;

for (i = 0; i < loops; i++) {

Pthread_mutex_lock(&mutex); // p1

if (count == 1) // p2

Pthread_cond_wait(&cond,