同步与互斥

发表于 更新于 分类于 ，

由生产者-消费者模式展开，学习其编程的最佳实践，却发现自己不知“信号量”的概念，忘了PV操作，困惑于“使用数组做循环队列时，判断满、空的条件怎么写”，为什么不直接使用 STL 的容器做队列？进出队列是不是严格需要锁？获取队列大小时是不是严格需要锁？

进程和线程管理

参考来源：C 语言中文网

进程控制块（PCB）

为了使参与并发执行的程序（含数据）能独立地运行，必须为之配置一个专门的数据结构，称为进程控制块(Process Control Block, PCB)。系统利用PCB来描述进程的基本情况和运行状态，进而控制和管理进程。相应地，由程序段、相关数据段和PCB三部分构成了进程映像（进程实体）。所谓创建进程，实质上是创建进程映像中的PCB；而撤销进程，实质上是撤销进程的PCB。值得注意的是，进程映像是静态的，进程则是动态的。

进程的状态：

  1. 创建状态：
  2. 就绪状态：
  3. 运行状态：
  4. 阻塞状态：
  5. 终止状态：

进程的通信：PV操作是低级通信方式，髙级通信方式是指以较高的效率传输大量数据的通信方式。高级通信方法主要有以下三个类。

  1. 共享存储

    在对共享空间进行写/读操作时，需要使用同步互斥工具（如 P操作、V操作），对共享空间的写/读进行控制。

    共享存储又分为两种：低级方式的共享是基于数据结构的共享；高级方式则是基于存储区的共享。

  2. 消息传递

  3. 管道通信

    所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。

    为了协调双方的通信，管道机制必须提供以下三方面的协调能力：互斥、同步和确定对方的存在。

进程同步的基本概念

临界资源：虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次仅允许一个进程使用的资源称为临界资源。

临界区：对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可以把临界资源的访问过程分成四个部分：

  1. 进入区-为了进入临界区使用临界资源，在进入区要检查可否进入临界区，如果可以进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。
  2. 临界区-进程中访问临界资源的那段代码，又称临界段。
  3. 退出区-将正在访问临界区的标志清除。
  4. 剩余区-代码中的其余部分。

同步：同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

互斥：互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待, 当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

信号量

原语：原语是指完成某种功能且不被分割不被中断执行的操作序列。

信号量：信号量机制是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准的原语wait(S)和signal(S)来访问，也可以记为“P操作”和“V操作”。

P和V是来源于两个荷兰语词汇，P—— passeren，中文译为”通过”；V—— vrijgeven，中文译为”释放/发布”。

  • 整型信号量
  • 记录信号量

利用信号量可以解决的问题：

  1. 利用信号量实现同步
  2. 利用信号量实现互斥
  3. 利用信号量实现前驱关系

分析进程同步和互斥问题的方法步骤：

  1. 关系分析-找出问题中的进程数，并且分析它们之间的同步和互斥关系。同步、互斥、前驱关系直接按照上面例子中的经典范式改写。
  2. 整理思路-找出解决问题的关键点，并且根据做过的题目找出解决的思路。根据进程的操作流程确定P操作、V操作的大致顺序。
  3. 设置信号量-根据上面两步，设置需要的信号量，确定初值，完善整理。

管程

管程：系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略了它们的内部结构和实现细节。管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。

管程的基本特征之一是：每次仅允许一个进程在管程内执行某个内部过程。

由于管程是一个语言成分，所以管程的互斥访问完全由编译程序在编译时自动添加，无需程序员关注，而且保证正确。

在 维基百科 - 生产者消费者问题 中介绍“使用管程的算法”时特别强调了使用 while 的重要性和正确性。然后我并没有看懂啊，囧。

针对多消费者（或多生产者），有可能造成竞争条件：

某一消费者在一项数据被放入缓冲区中时被唤醒，但是另一消费者已经在管程上等待了一段时间并移除了这项数据。

但前文提到：

管程的基本特征之一是：每次仅允许一个进程在管程内执行某个内部过程。

这两点不冲突吗？所以，管程到底是什么？

经典进程同步问题

  1. 生产者-消费者问题
  2. 读者-写者问题
  3. 哲学家进餐问题
  4. 吸烟者问题

真心好玩！

我的困惑

管程在 C++ 中有对应的实现吗？代码的实例。做出进一步地了解之后，复习“管程”章节。

在 维基百科 - 生产者消费者问题 中也提到了不使用信号量和管程实现生产者消费者问题的方式。

对于生产者消费者问题来说，特别是当只有一个生产者和一个消费者时，实现一个先进先出结构或者通信通道非常重要。这样，生产者-消费者模式就可以在不依赖信号灯、互斥变量或管程的的情况下高效地传输数据。

人们喜欢用先进先出结构或者通信通道，只是因为可以避免端与端之间的原子性同步。

问题一：使用信号量解决生产者消费者问题时做同步能理解，但为什么要做互斥？是针对缓冲区的修改吗？插入和删除可能正好是同一块存储？

问题二：保证先进先出就能够保证互斥？同步由 while 实现？

POSIX

参考来源：线程间同步–互斥锁、条件变量、信号量

互斥锁

互斥锁是最常用的。使用时包含 #include <pthread.h> 头文件即可。

对于多线程的程序，访问冲突的问题是很普遍的，解决的办法是引入互斥锁（Mutex，Mutual Exclusive Lock），获得锁的线程可以完成“读-修改-写”的操作，然后释放锁给其它线程，没有获得锁的线程只能等待而不能访问共享数据，这样“读-修改-写”三步操作组成一个原子操作，要么都执行，要么都不执行，不会执行到中间被打断，也不会在其它处理器上并行做这个操作。

条件变量

条件变量：在pthread库中通过条件变量（Condition Variable）来阻塞等待一个条件，或者唤醒等待这个条件的线程。

——问题1：开发实践中应用得多吗？某些场景下感觉可以用 while-sleep 替换，使用条件变量有什么优点吗？

其实想一想，pthread_cond_wait函数也可以用一个while死循环来等待条件的成立，但要注意的是，使用while死循环会严重消耗CPU，而pthread_cond_wait则是采用线程睡眠的方式，它是一种等待模式，而不是一直的检查模式。引用来源

——问题2：Linux线程编程之生产者消费者问题 中条件变量的代码使用了 while，和上一章节“管程”中的使用一致。和使用 if 有特别大的区别吗？我是指两者在多消费者（或多生产者）的情况下，无论是用 while，还是 if 都可能造成竞争吧？

pthread_cond_wait() 返回时，互斥量再次被锁定并被调用线程拥有。

——问题3：针对上一问题中使用 while 的必要性

虚假唤醒(spurious wakeup)指没有线程明确调用cond_signal/broadcast()时，cond_wait()偶尔也会返回；或者条件状态尚不满足时就调用cond_signal/broadcast()。此时，线程虽被唤醒但条件并不成立，若不再次检查条件而往下执行，很可能导致后续的处理出现错误。因此，当从cond_wait()返回时，线程应重新测试条件成立与否。该过程一般用while循环实现。

使用while循环不仅能避免虚假唤醒造成的错误，还能避免唤醒线程间竞争导致的“惊群效应”。

例如，ProducerThread()内，调用cond_wait()对互斥量自动解锁后，在允许消费者线程修改条件的同时，也允许其他生产者线程调用该函数依次阻塞。当这些线程被唤醒时(如队列由满变为非满)，会再次竞争相应的互斥量。获得互斥量的那个线程进入临界区处理，这可能改变测试条件(如产出一件使得队列再次变满)。该线程释放互斥量后，其他某个处于等待状态的线程获得该互斥量时，虽然cond_wait()成功返回但很可能条件已不成立。因此，调用cond_wait()成功返回时，线程需要重新测试条件是否满足。 引用来源

强烈推荐 Linux线程编程之生产者消费者问题 帖子中的 2.3注意事项 ☆☆☆☆☆，尤其是其中的第1项、第5项、第7项、第8项和第9项。

互斥锁和条件变量的区别：

  1. 互斥锁和条件变量的初始化很一致；
  2. 使用上，互斥锁先是调用 pthread_mutex_lock 获得锁，获取到则向下执行，如果未获取到则阻塞，直到其被释放（pthread_mutex_unlock）；
  3. 而条件变量调用 pthread_cond_wait 之后直接阻塞，直到被唤醒（pthread_cond_signal）；

int pthread_cond_wait(pthread_cond_t *restrict cond, pthread_mutex_t *restrict mutex); 函数做以下三步操作：

  1. 释放 Mutex
  2. 阻塞等待
  3. 当被唤醒时，重新获得 Mutex并返回

需要强调的是前两个操作是原子性的（不包括第3个）。

这些本质上都是条件判断，为什么不能用全局变量？参见 C 语言中文网 - 实现临界区互斥的基本方法

Mutex变量是非0即1的，可看作一种资源的可用数量，初始化时Mutex是1，表示有一个可用资源，加锁时获得该资源，将Mutex减到0，表示不再有可用资源，解锁时释放该资源，将Mutex重新加到1，表示又有了一个可用资源。

信号量

信号量（Semaphore）和Mutex类似，表示可用资源的数量，和Mutex不同的是这个数量可以大于1。如果使用 POSIX semaphore库，需要包含 #include <semaphore.h>，这种信号量不仅可用于同一进程的线程间同步，也可用于不同进程间的同步。

使用Posix信号量可模拟互斥量和条件变量，而且通常更有优势。引用来源

C++11

接下来说说 C++11 中用并发怎么写生产者消费者问题。

参考来源：C++11 并发指南九，正确与否暂且不论。作者可真够啰嗦的，又不是写论文，凑啥篇幅。推荐作者系列文章：C++11 并发指南系列

使用“c++ 生产者消费者”作为关键字 google，其结果前 2 页含有有效代码的网页中，基本以数组（做环形队列）做有限缓冲，有两个例子使用了 STL 的 vector，一个例子使用 queue

  1. 使用 vector 例子一
  2. 使用 vector 例子二，代码比较糟糕，不支持多生产者（或多消费者）
  3. 使用 queue 例子

具体业务场景具体分析，但更具通用性（同时适用于多生产者或多消费者的情况）的上锁方式，是将“获取缓冲区大小，进出缓冲区”都作为临界区，严格上锁。