《深入理解计算机系统》并发编程

2017-05-30 本文已影响102人唐鱼的学习探索

我们在上一章节中讲到的Tiny Web服务器只能为单个客服端提供访问，这一章里，我们将通过进程、多路复用和线程技术研究并发的服务器。

1.1 使用进程实现并发

我们实现过一个echo服务器，但是遗憾的是只能为一个客服端服务，这不是我们的初衷，现在我们来更新上一个版本，使得服务器在接收到连接请求的时候，创建子进程为该客户端提供服务，主进程会关闭已连接的描述符，继续监听下一个客服端，这一个过程我画了一个简图：

在这个过程中，客服端1连接上了服务器，并创建了一个已连接的描述符4，服务器立即派生子进程，子进程将继承原有的已连接描述符4，通过这个子进程的描述符为客服端1提供给服务。这时候，主进程必须要关闭已连接描述符4，使得不至于发生内存泄漏。

客服端2的连接过程和客服端1的过程是一样的，还是由服务器创建子进程2提供服务，并关闭服务器中的已连接描述符5。我们来看看改进代码：只是加入了回收子进程，在子进程中关闭监听描述符和主进程中关闭已连接描述符。运行的效果如下：

可以同时为多个客服端提供服务，实现进程并发，进程级并发的一个明显的缺点是，各个进程都有独立的地址空间，使得共享信息相当困难而且慢速需要IPC，原理已经讲解了，代码就不难理解了：

1.2 使用IO多路复用实现并发

应用程序在一个进程的上下文中显示的调度它们的逻辑流，逻辑流被模型化为状态机，数据到达文件描述后，主程序显示的从一个状态切换到另一个状态。

① 响应键盘输入和客服端连接

我们使用select函数创建一个描述符集合，当其中之一的描述符做好准备的时候，将控制权返回给程序，select函数原型如下：

int select(int n, fd_set *fdset, NULL, NULL, NULL);

fdset被称为一个描述符集合，我们将需要处理的描述符添加到fdset结合中去；第一个参数n是描述符集合中最大的数。select函数会一直阻塞，直到相应的集合中的描述符准备好可以读；

我们来演示一个例子：

当我们打开了监听描述符以后，我们将一个read_set集合清空，并添加上标准输入和监听描述符3形成集合{0,3}，随后，我们进入一个无限循环，每次调用Select函数会阻塞，直到描述符0或者3到达时。

我们启动以后，随意输入内容，就会看到服务器首先响应了标准输入：

我们接下来启动已连接描述符，就会发现一个问题：

不论是服务端的标准输入，还是新启动的客户端2都被阻塞了。只有当已连接描述符客户端1关闭的时候才能使用。

一个解决之道是服务器每次循环最多回送一个文本行，就不会让已连接的描述符连续回送了。

② 多路复用实现并发

服务器为每一个客户端创建一个状态机，每个状态机三个阶段：

【准备】——【输入事件】——【写回】

我们来看看main函数主要部分：

说明：活动的客户端是在pool池塘中，通过调用init_pool完成初始化后进入一个while循环，select函数检测两种不同的输入（新的连接、已经连接的描述符准备好可以读），当新的连接到达时，accept并add_client。最后使用check_clients函数将文本行回送。

分析：init_pool函数

分析：add_client函数

分析：check_clients函数

运行的效果如图：

总结：我们这个版本的并发服务器，使用的是事件驱动的形式，它的优点就是共享数据的效果好很多，因为都是同一个进程上下文。开销也没有多进程的版本大，缺点就是复杂度要高些。总之，是优秀很多的。

1.3 基于线程的并发

线程是一个运行在进程上下文中的逻辑流，由内核自动调度，集成了多进程与多路复用的优点，每个线程就像在舞台上跳舞的演员一样，各自分工和角色不一样，共享舞台的地址空间，当然也有自己私有的服装和台词。

① 执行模型

每个线程在开始的时候都是单一的主线程，这个主线程可以创建对等线程，然后两个线程并发执行，不断的切换上下文，分别执行一段时间。与进程之间不同的是线程的上下文切换要小的多，还有就是线程之间是完全对等的关系，也就是一个线程可以杀死它的对等线程。

我们来看一个简单的例子：

主线程main中通过使用Pthread_create创建了一个新的tid线程，成功以后两个线程同时运行，主线程还使用了Pthread_join函数等待对等线程终止。对等线程只是简单的打印了一下Hello world。

② 创建线程

原型：int pthread_create(pthread_t *tid， pthread_attr_t *attr， func *f， void *arg);

其中调用成功后tid是运行中的线程ID，attr设置线程默认属性，f是线程函数，arg是传递参数

可以使用：pthread_t pthread_self（void）函数获取当前线程的ID；

③ 终止线程

原型：int pthread_cancel(pthread_t tid); 终止当前线程

原型：void pthread_exit(void *thread_return);等待所有对等线程终止

④ 回收已经终止的线程

原型：int pthread_join(pthread_t tid， void **thread_return);

函数会阻塞，直到线程tid终止并回收所有存储器资源。与wait不同的是该函数只能回收一个特定的线程；

⑤ 分离线程：分离后的线程终止以后由系统自动释放

原型：int pthread_detach(pthread_t tid);

⑥ 初始化线程

原型：int pthread_once(pthread_once_t *once_control, void (*init_routine)(void));

⑦ 一个基于线程的并发服务器

这个版本同线程的版本没有多大的变化，有两个地方需要注意，我们使用了一个connfdp指针指向一个动态分配的空间来传递已连接的描述符，避免出现竞争。同时在每个线程的函数中使用deatach进行分离，每个线程终止后由系统释放。

运行效果：

1.4 多线程中的共享变量

我们前面说过线程集中了多路复用中的共享的优点，也举例说了就像同一个舞台表演的不同演员一样，整个舞台空间是共享的。那么多线程中的共享是如何实现的，工作原理是什么？

我们看一个简单的例子，加入一些说明：

① 线程存储器模型

寄存器是不共享的，虚拟存储器总是共享的。就像同一个家庭的两个孩子一样，可以在一个饭厅吃饭，在客厅看电视，甚至共享同一个厕所，但是各自的房间通常是不一样的，各自的个人物品也不同。

② 将变量映射到存储器

全局变量：如ptr，可以使得本地变量msgs变成了共享（有时候两个孩子要共享一个厕所）；

本地自动变量：如myid是不能共享的，每个线程的myid都不一样；

本地静态变量：加入static如cnt，只有一个实例，两个对等线程访问的是同一个地方

③ 共享变量：被1个以上的线程访问过的变量，如cnt。需要注意的是msgs也变成了共享的。

1.5 用信号量同步线程

智人在进化意义上最成功的由于其合作的规模，单个的智人个体虽然远远不及同时代的尼安德特人，但是合作的规模更大，力量也就更大。我们今天探讨的就是线程的同步，如果每个线程都各顾各的，势必会影响到程序的正常运行。我们来看一个未经同步的线程的运行情况：

这个程序的运行结果就不OK了，原因在于每个单独的进程对共享变量cnt的访问不是独占式的，这种不同步导致了错误的结果。我们来研究一下最核心的代码的运行过程：

这里我们将线程函数中的for循环翻译成汇编代码，其中：Li是循环头，Ti是循环尾，Li对应于加载cnt，Ui对应于更新cnt，Si对应于存储cnt。线程的执行顺序并不一定总是我们所期望的，如果遇到下面这种运行顺序，就可能会出错。

上图中左边是正确的运行顺序，（b）就会得到错误的结果，关键点在于线程1更新了eax的值以后并没有立即写入到cnt中，就开始运行了线程2，线程2由于cnt没有更新所有eax加载还是为0，当线程2完成写入命令以后cnt就仍然是1，不会得到累加。

为了帮助大家正确理解各个线程的执行顺序，我们来画图

① 进度图

上图展现了两个线程，1和2，分别用x轴和y轴表示，其中Hi、Li、Ui、Si、Ti分别代表对共享变成操作的for循环的关键步骤，其中Li、Ui、Si涉及对cnt临界区的操作，所有经过这一区域的执行顺序都是不安全的。为了使得线程之间的同步变得科学，不跨越临界区。我们发明了信号量这种特殊的变量。

② 信号量：非负整数全局变量

信号量s其实就是一个非负整数的全局变量，对这一变量有两个操作：P（s）使得s减1，而V（s）使得s加1。我们操作信号量s的时候，通常的情况是将其初始化为1，执行P操作的时候为加锁，执行V操作的时候为解锁。为了限定线程不经由不安全区域，我们将不安全区域的设置为-1，如下图：

我们的信号量s被初始化为1，只能在0和1之间变化：

1>加锁：执行P（s），有两种情况，如果原有的值为1，那么减至0；如果为0则挂起线程;

2>解锁：执行V（s），也有两种情况，如果s=0就加1；如果s=1就等待；

③ 更新我们的badcnt程序

这样以来我们的全局共享变量cnt在运行的各个线程中就会经由加锁执行++和解锁，得到正确的结果了。

④ 信号量调度共享资源

生产者——消费者问题

以小区的自动售货机为例，消费者如果直接以下订单的方式与生产者沟通，这样的效率就太低下了。我不可能想要喝一瓶可能才让可口可乐公司给我生产。这时候缓冲区就是一个很好的发明，我们发现在小区建立几个自动售货机，假设每个自动售货机可以装100瓶饮料。这样一来只要自动售货机不为空生产者就可以将饮料放入到自动售货机中去，当然只要售货机有饮料消费者也直接从自动售货机购买饮料。这样一来就方便的多了。

我们前面讲过信号量，P操作遇到为0的情况就会等待。但是现实的生活中，这样的情况就不很科学。回到我们上面的自动售货机的例子。如果我们的消费者发现了自动售货机是空的，我们就开始在原地等待，直到生产者将生产好的饮料送到自动售货机上的时候，再购买。这样以来对个人来说是精力的极大浪费。我们有什么好的方法没有，就像我们滴滴打车一样，我们下单以后就可以去做其他事情了，一有车子接单以后就会电话联系我们。

我们使用一种新的数据结构来解决这种问题：

操作函数

读者——写者问题

这个问题类似于上一个，有点儿像我们的购票系统，票数就是我们的共享变量，同一时刻我们允许多个客户从不同的端口登录查看票数在售情况（读者优先），但是当有一个购买者（写者）的买票的时候，写会独占票数。有一个解答如下：

⑤ 实现一个预线程化的并发服务器

我们通常所用到的线程并发服务器，要求服务器为每个客户端单独生成一个线程来提供服务，就相当于一种下订单再生产的落后经济模型，我们学习了生产者消费者模型以后，尝试加入新的内容：服务器由一个主线程和一组工作线程构成，主线程接收客户端的连接请求，并将连接的描述符放入到一个缓冲区中，每个工作线程反复的从缓冲区中取出描述符，提供服务，然后等待下一个描述符。

我们来看看实现代码：

1.6 使用线程提高并行性

现代的CPU往往是多核的，如何利用这个特性变得相当重要。我们这里所的并行是并发的一个子集，代表的是在多核处理器上运行的并发程序。

如果我们要计算1,2,3…… 100各个数字相加的和，我们知道经典的答案是：（1+100）*50=5050，我们使用多线程求一个集合数字的和的方法，就是将100个数字分成5个区域，这样每个区域有20个数字，每个对等线程求出5个区域20个数字的和，然后由主线程将不同的和相加，就会得到这100个数字的和。我们来看一段代码：