状态机与并发编程

栈顶的指针rsp叫做指针寄存器，专门用来指向内存中的栈顶的

下图左边是单线程程序，偶尔会发生非确定性系统调用；

而右边是三线程程序，任意时刻只会执行其中一个线程，来修改对应的寄存器R和内存M 天生不确定

并发程序的状态机实在是太多了，规模要比串行普遍大不少

并发程序的难点是：每执行一个指令就要选择多个线程，这样就会有指数多的状态空间

理解并发程序我们通常有这种思考方式：将线程看做是活生生的人

我们做并发程序保证并发安全性：指的是保证两个线程都不同同时执行到两个线程的critical section（临界区）中，两个线程同时执行在这部分的时候，破坏了原子性，程序变得不是很安全。

Peterson算法

比如下面这张图， ,都陷入到critical section中，这就是有问题的。证明Peterson算法是对的，就是证明从出发节点到的所有节点都 没有 两个线程中的各自指令都在critical section，这样peterson算法就是对的。

当然，两个线程都卡在临界区之前，这也是执行不下去的

上图也说明：使用状态机的好处可以使得状态机问题转换成图论问题

进程间和线程间的协作区别：

进程互斥、同步的概念

进程互斥、同步的概念是并发进程下存在的概念，有了并发进程，就产生了资源的竞争与协作，从而就要通过进程的互斥、同步、通信来解决资源的竞争与协作问题。

下面是根据《 *** 作系统教程》3.1.4 中的介绍，整理的进程互斥、同步的概念。

在多道程序设计系统中，同一时刻可能有许多进程，这些进程之间存在两种基本关系：竞争关系和协作关系。

进程的互斥、同步、通信都是基于这两种基本关系而存在的，为了解决进程间竞争关系（间接制约关系）而引入进程互斥；为了解决进程间松散的协作关系( 直接制约关系)而引入进程同步；为了解决进程间紧密的协作关系而引入进程通信。

第一种是竞争关系

系统中的多个进程之间彼此无关，它们并不知道其他进程的存在，并且也不受其他进程执行的影响。例如，批处理系统中建立的多个用户进程， 分时系统中建立的多个终端进程。由于这些进程共用了一套计算机系统资源，因而， 必然要出现多个进程竞争资源的问题。当多个进程竞争共享硬设备、存储器、处理器 和文件等资源时， *** 作系统必须协调好进程对资源的争用。

资源竞争出现了两个控制问题：一个是死锁 （deadlock ）问题，一组进程如果都获得了部分资源，还想要得到其他进程所占有的资源，最终所有的进程将陷入死锁。另一个是饥饿（starvation ）问题，这是指这样一种情况：一个进程由于其他进程总是优先于它而被无限期拖延。

*** 作系统需要保证诸进程能互斥地访问临界资源，既要解决饥饿问题，又要解决死锁问题。

进程的互斥（mutual exclusion ）是解决进程间竞争关系( 间接制约关系) 的手段。 进程互斥指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放该资源。

第二种是协作关系

某些进程为完成同一任务需要分工协作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互协作的进程在某些协调点上协 调各自的工作。当合作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，直到其他合作进程发来协调信号或消息后方被唤醒并继续执行。这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步。

进程间的协作可以是双方不知道对方名字的间接协作，例如，通过共享访问一个缓冲区进行松散式协作；也可以是双方知道对方名字，直接通过通信机制进行紧密协作。允许进程协同工作有利于共享信息、有利于加快计算速度、有利于实现模块化程序设计。

进程的同步（Synchronization）是解决进程间协作关系( 直接制约关系) 的手段。进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于另一

个协作进程的消息或信号，当一个进程没有得到来自于另一个进程的消息或信号时则需等待，直到消息或信号到达才被唤醒。

不难看出，进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，也是对进程使用资源次序上的一种协调。

进程通信的概念

下面是根据《 *** 作系统教程》3.5 中的介绍，整理的进程通信的概念。

并发进程之间的交互必须满足两个基本要求：同步和通信。

进程竞争资源时要实施互斥，互斥是一种特殊的同步，实质上需要解决好进程同步问题，进程同步是一种进程通信，通过修改信号量，进程之间可建立起联系，相互协调运行和协同工作。但是信号量与PV *** 作只能传递信号，没有传递数据的能力。有些情况下进程之间交换的信息量虽很少，例如，仅仅交换某个状态信息，但很多情况下进程之间需要交换大批数据，例如，传送一批信息或整个文件，这可以通过一种新的通信机制来完成，进程之间互相交换信息的工作称之为进程通信IPC （InterProcess Communication）（主要是指大量数据的交换）。进程间通信的方式很多，包括：

信号（signal ）通信机制；

信号量及其原语 *** 作（PV、读写锁、管程）控制的共享存储区（shared memory ）通信机制；

管道（pipeline）提供的共享文件（shared file）通信机制；

信箱和发信/ 收信原语的消息传递（message passing ）通信机制。

其中前两种通信方式由于交换的信息量少且效率低下，故称为低级通信机制，相应地可把发信号/ 收信号及PV之类 *** 作称为低级通信原语，仅适用于集中式 *** 作系统。消息传递机制属于高级通信机制，共享文件通信机制是消息传递机制的变种，这两种通信机制，既适用于集中式 *** 作系统，又适用于分布式 *** 作系统。

进程同步的方法

前面提到，进程互斥关系是一种特殊的进程同步关系，下面给出常见的进程同步的方法，实际上也可用于进程的互斥（个人理解）。

在何炎祥的《计算机 *** 作系统》 3.2 节，将进程同步的机制与解决进程互斥方法看做是一样的，的明确指出互斥的软件解决方法为Dekker算法与Peterson算法，互斥的硬件解决方法为中断方法、以及使用机器指令的方法，后面又给出了信号量、管程、消息传递三种方法。

实际应用中，不同的系统有不同的进程同步方法，CSDN帖子http://bbs.csdn.net/topics/80156687中有一些讨论，Linux 与Windows的主要同步、通信机制如下：

Linux 下：

Linux 下常见的进程同步方法有：SysVIPC 的 sem（信号量）、file locking / record locking（通过 fcntl 设定的文件锁、记录锁）、futex（基于共享内存的快速用户态互斥锁）。针对线程（pthread）的还有 pthread_mutex 和 pthread_cond（条件变量）。

Linux 下常见的进程通信的方法有 ：pipe（管道），FIFO（命名管道），socket（套接字），SysVIPC 的 shm（共享内存）、msg queue（消息队列），mmap（文件映射）。以前还有 STREAM，不过现在比较少见了（好像）。

Windows下：

在Windwos中，进程同步主要有以下几种：互斥量、信号量、事件、可等计时器等几种技术。

在Windows下，进程通信主要有以下几种：内存映射、管道、消息等，但是内存映射是最基础的，因为，其他的进程通信手段在内部都是考内存映射来完成的。

线程的同步/通信与进程的同步/通信有区别吗？

对于该问题，教材上没有明确的回答，教材上给出的一般是进程而非线程的同步、通信方式。但网络上很多说法将两者混为一谈。根据教材，以及网上的说法，个人的理解为：

同步机制：

信号量、管程、互斥是进程的同步机制，而信号量、互斥也可用于线程的同步，但管程只在进程同步中被用到；

线程的同步除了信号量、互斥外，还有临界区、事件，没有看到教材上将这两种方式作为进程的同步方式；

通信机制：

管道、FIFO、消息队列、信号量、共享内存是进程的同步机制，教材上没有线程的通信机制这样的说法，但可以肯定这几种方法是进程的通信方式，且其中的信号量既可用于进程的同步，又可用于进程的通信，在网络上还有说可以用于线程同步的。

管道与管程是不同的，管程是进程同步的方式，而管道则是进程通信的方式。

进程的同步/通信

下面是常见的线程之间的同步方式的详细介绍。

（注：下面转自网络，下面的同步、通信方式对于进程与线程分的不是很清楚，关于进程还是线程的解释见上面——线程的同步/通信与进程的同步/通信有区别吗？）

一、进程/线程间同步机制。

临界区、互斥区、事件、信号量四种方式

临界区（Critical Section）、互斥量（Mutex）、信号量（Semaphore）、事件（Event）的区别

1、临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。

在任意时刻只允许一个线程对共享资源进行访问，如果有多个线程试图访问公共资源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占。

2、互斥量：采用互斥对象机制。

只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程访问。互斥不仅能实现同一应用程序的公共资源安全共享，还能实现不同应用程序的公共资源安全共享 .互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。

3、信号量：它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目 .

信号量对象对线程的同步方式与前面几种方法不同，信号允许多个线程同时使用共享资源，这与 *** 作系统中的PV *** 作相同。它指出了同时访问共享资源的线程最大数目。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。

PV *** 作及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量S是一个整数，S大于等于零时代表可供并发进程使用的资源实体数，但S小于零时则表示正在等待使用共享资源的进程数。

P *** 作申请资源：

（1）S减1；

（2）若S减1后仍大于等于零，则进程继续执行；

（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转入进程调度。

V *** 作 释放资源：

（1）S加1；

（2）若相加结果大于零，则进程继续执行；

（3）若相加结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转入进程调度。

4、事 件： 通过通知 *** 作的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较的 *** 作 .

总结：

1． 互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥量是跨进程的互斥量一旦被创建，就可以通过名字打开它。

2． 互斥量（Mutex），信号灯（Semaphore），事件（Event）都可以被跨越进程使用来进行同步数据 *** 作，而其他的对象与数据同步 *** 作无关，但对于进程和线程来讲，如果进程和线程在运行状态则为无信号状态，在退出后为有信号状态。所以可以使用WaitForSingleObject来等待进程和线程退出。

3． 通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库 *** 作，这时候如果利用互斥量就没有办法完成这个要求，信号灯对象可以说是一种资源计数器。

二、进程间通信方式

由于比较容易混淆，我们把进程间通信方法也列在这里做比较。

进程通信也就是所谓的IPC问题，主要是指进程间交换数据的方式。进程通信包括高级通信与低级通信，其中进程同步与互斥属于低级通信，主要用于插U农地控制信号；高级通信包括三种：共享存储系统（有的地方称作共享内存区）、消息传递系统（有的地方称作消息队列）、管道。

信号量是进程同步与互斥的常用方法，也可以作为低级的进程通信方法，用于传递控制信号。

简而言之，进程间通信方式主要包括管道、FIFO、消息队列、信号量、共享内存。

1.管道，还有命名管道和非命名管道(即匿名管道)之分，非命名管道(即匿名管道)只能用于父子进程通讯，命名管道可用于非父子进程，命名管道就是FIFO，管道是先进先出的通讯方式

2.消息队列，是用于两个进程之间的通讯，首先在一个进程中创建一个消息队列，然后再往消息队列中写数据，而另一个进程则从那个消息队列中取数据。需要注意的是，消息队列是用创建文件的方式建立的，如果一个进程向某个消息队列中写入了数据之后，另一个进程并没有取出数据，即使向消息队列中写数据的进程已经结束，保存在消息队列中的数据并没有消失，也就是说下次再从这个消息队列读数据的时候，就是上次的数据！！！！

3.信号量，它与WINDOWS下的信号量是一样的，所以就不用多说了

4.共享内存，类似于WINDOWS下的DLL中的共享变量，但LINUX下的共享内存区不需要像DLL这样的东西，只要首先创建一个共享内存区，其它进程按照一定的步骤就能访问到这个共享内存区中的数据，当然可读可写

以上几种方式的比较：

1.管道：速度慢，容量有限，只有父子进程能通讯

2.FIFO：任何进程间都能通讯，但速度慢

3.消息队列：容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题

4.信号量：不能传递复杂消息，只能用来同步

5.共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存

本质上，信号量是一个计数器，它用来记录对某个资源（如共享内存）的存取状况。一般说来，为了获得共享资源，进程需要执行下列 *** 作：

（1）测试控制该资源的信号量；

（2）若此信号量的值为正，则允许进行使用该资源，进程将进号量减1；

（3）若此信号量为0，则该资源目前不可用，进程进入睡眠状态，直至信号量值大于0，进程被唤醒，转入步骤（1）；

（4）当进程不再使用一个信号量控制的资源时，信号量值加1，如果此时有进程正在睡眠等待此信号量，则唤醒此进程。

套接字通信并不为Linux所专有，在所有提供了TCP/IP协议栈的 *** 作系统中几乎都提供了socket，而所有这样 *** 作系统，对套接字的编程方法几乎是完全一样的

三、进程/线程同步机制与进程间通信机制比较

很明显2者有类似，但是差别很大

同步主要是临界区、互斥、信号量、事件

进程间通信是管道、内存共享、消息队列、信号量、socket

共通之处是，信号量和消息（事件）

小结：

进程互斥、同步与通信的关系：进程竞争资源时要实施互斥，互斥是一种特殊的同步，实质上需要解决好进程同步问题，进程同步是一种进程通信，由此看来，进程互斥、同步都可以看做进程的通信；

信号量是进程同步与互斥的常用方法，也可以作为低级的进程通信方法，用于传递控制信号；

管道与管程是不同的，管程是进程同步的方式，而管道则是进程通信的方式；

互斥量是一个可以处于两态之一的变量：解锁和加锁。这样，只需要一个二进制位表示它，不过实际上，常常使用一个整型量，0表示解锁，而其他所有的值则表示加锁。互斥量使用两个过程。当一个线程（或进程）需要访问临界区时，它调用mutex_lock。如果该互斥量当前是解锁的（即临界区可用），此调用成功，调用线程可以自由进入该临界区。

另一方面，如果该互斥量已经加锁，调用线程被阻塞，直到在临界区中的线程完成并调用mutex_unlock。如果多个线程被阻塞在该互斥量上，将随机选择一个线程并允许它获得锁。

由于互斥量非常简单，所以如果有可用的TSL或XCHG指令，就可以很容易地在用户空间中实现它们。用于用户级线程包的mutex_lock和mutex_unlock代码如图2-29所示。XCHG解法本质上是相同的。

mutex_lock 的代码与图2-25中enter_region的代码很相似，但有一个关键的区别。当enter_region进入临界区失败时，它始终重复测试锁（忙等待）。实际上，由于时钟超时的作用，会调度其他进程运行。这样迟早拥有锁的进程会进入运行并释放锁。

在（用户）线程中，情形有所不同，因为没有时钟停止运行时间过长的线程。结果是通过忙等待的方式来试图获得锁的线程将永远循环下去，决不会得到锁，因为这个运行的线程不会让其他线程运行从而释放锁。

以上就是enter_region和mutex_lock 的差别所在。在后者取锁失败时，它调用thread_yield将CPU放弃给另一个线程。这样，就没有忙等待。在该线程下次运行时，它再一次对锁进行测试。

由于thread_yield只是在用户空间中对线程调度程序的一个调用，所以它的运行非常快捷。这样，mutex_lock和mutex_unlock都不需要任何内核调用。通过使用这些过程，用户线程完全可以实现在用户空间中的同步，这些过程仅仅需要少量的指令。

上面所叙述的互斥量系统是一套调用框架。对于软件来说，总是需要更多的特性，而同步原语也不例外。例如，有时线程包提供一个调用mutex_trylock，这个调用或者获得锁或者返回失败码，但并不阻塞线程。这就给了调用线程一个灵活性，用以决定下一步做什么，是使用替代办法还只是等待下去。

到目前为止，我们掩盖了一个问题，不过现在还是有必要把这个问题提出来。在用户级线程包中，多个线程访问同一个互斥量是没有问题的，因为所有的线程都在一个公共地址空间中 *** 作。但是，对于大多数早期解决方案，诸如Peterson算法和信号量等，都有一个未说明的前提，即这些多个进程至少应该访问一些共享内存，也许仅仅是一个字。如果进程有不连续的地址空间，如我们始终提到的，那么在Peterson算法、信号量或公共缓冲区中，它们如何共享turn变量呢？

有两种方案。第一种，有些共享数据结构，如信号量，可以存放在内核中，并且只能通过系统调用来访问。这种处理方式化解了上述问题。第二种，多数现代 *** 作系统（包括UNIX和Windows）提供一种方法，让进程与其他进程共享其部分地址空间。在这种方法中，缓冲区和其他数据结构可以共享。在最坏的情形下，如果没有可共享的途径，则可以使用共享文件。

如果两个或多个进程共享其全部或大部分地址空间，进程和线程之间的差别就变得模糊起来，但无论怎样，两者的差别还是有的。共享一个公共地址空间的两个进程仍旧有各自的打开文件、报警定时器以及其他一些单个进程的特性，而在单个进程中的线程，则共享进程全部的特性。另外，共享一个公共地址空间的多个进程决不会拥有用户级线程的效率，这一点是不容置疑的，因为内核还同其管理密切相关。

Pthread中的互斥

Pthread提供许多可以用来同步线程的函数。其基本机制是使用一个可以被锁定和解锁的互斥量来保护每个临界区。一个线程如果想要进入临界区，它首先尝试锁住相关的互斥量。如果互斥量没有加锁，那么这个线程可以立即进入，并且该互斥量被自动锁定以防止其他线程进入。如果互斥量已经被加锁，则调用线程被阻塞，直到该互斥量被解锁。如果多个线程在等待同一个互斥量，当它被解锁时，这些等待的线程中只有一个被允许运行并将互斥量重新锁定。这些互斥锁不是强制性的，而是由程序员来保证线程正确地使用它们。

与互斥量相关的主要函数调用如图2-30所示。就像所期待的那样，可以创建和撤销互斥量。实现它们的函数调用分别是pthread_mutex_init与pthread_mutex_destroy。也可以通过pthread_mutex_lock给互斥量加锁，如果该互斥量已被加锁时，则会阻塞调用者。还有一个调用可以用来尝试锁住一个互斥量，当互斥量已被加锁时会返回错误代码而不是阻塞调用者。这个调用就是pthread_mutex_trylock。如果需要的话，该调用允许一个线程有效地忙等待。最后，pthread_mutex_unlock用来给一个互斥量解锁，并在一个或多个线程等待它的情况下正确地释放一个线程。互斥量也可以有属性，但是这些属性只在某些特殊的场合下使用。

除互斥量之外，pthread提供了另一种同步机制：条件变量。互斥量在允许或阻塞对临界区的访问上是很有用的，条件变量则允许线程由于一些未达到的条件而阻塞。绝大部分情况下这两种方法是一起使用的。现在让我们进一步地研究线程、互斥量、条件变量之间的关联。

举一个简单的例子，再次考虑一下生产者-消费者问题：一个线程将产品放在一个缓冲区内，由另一个线程将它们取出。如果生产者发现缓冲区中没有空槽可以使用了，它不得不阻塞起来直到有一个空槽可以使用。生产者使用互斥量可以进行原子性检查，而不受其他线程干扰。但是当发现缓冲区已经满了以后，生产者需要一种方法来阻塞自己并在以后被唤醒。这便是条件变量做的事了。

与条件变量相关的pthread调用如图2-31所示。就像你可能期待的那样，这里有专门的调用用来创建和撤销条件变量。它们可以有属性，并且有不同的调用来管理它们（图中没有显示）。与条件变量相关的最重要的两个 *** 作是pthread_cond_wait和pthread_cond_signal。前者阻塞调用线程直到另一其他线程向它发信号（使用后一个调用）。当然，阻塞与等待的原因不是等待与发信号协议的一部分。被阻塞的线程经常是在等待发信号的线程去做某些工作、释放某些资源或是进行其他的一些活动。只有完成后被阻塞的线程才可以继续运行。条件变量允许这种等待与阻塞原子性地进行。当有多个线程被阻塞并等待同一个信号时，可以使用pthread_cond_broadcast调用。

---