写给大忙人看的进程和线程





我们平常说的进程和线程更多的是基于编程语言的角度来说的，那么你真的了解什么是线程和进程吗？那么我们就从操作系统的角度来了解一下什么是进程和线程。



进程



操作系统中最核心的概念就是 进程，进程是对正在运行中的程序的一个抽象。操作系统的其他所有内容都是围绕着进程展开的。进程是操作系统提供的最古老也是最重要的概念之一。即使可以使用的 CPU 只有一个，它们也支持（伪）并发操作。它们会将一个单独的 CPU 抽象为多个虚拟机的 CPU。可以说：没有进程的抽象，现代操作系统将不复存在。





所有现代的计算机会在同一时刻做很多事情，过去使用计算机的人（单 CPU）可能完全无法理解现在这种变化，举个例子更能说明这一点：首先考虑一个 Web 服务器，请求都来自于 Web 网页。当一个请求到达时，服务器会检查当前页是否在缓存中，如果是在缓存中，就直接把缓存中的内容返回。如果缓存中没有的话，那么请求就会交给磁盘来处理。但是，从 CPU 的角度来看，磁盘请求需要更长的时间，因为磁盘请求会很慢。当硬盘请求完成时，更多其他请求才会进入。如果有多个磁盘的话，可以在第一个请求完成前就可以连续的对其他磁盘发出部分或全部请求。很显然，这是一种并发现象，需要有并发控制条件来控制并发现象。



现在考虑只有一个用户的 PC。当系统启动时，许多进程也在后台启动，用户通常不知道这些进程的启动，试想一下，当你自己的计算机启动的时候，你能知道哪些进程是需要启动的么？这些后台进程可能是一个需要输入电子邮件的电子邮件进程，或者是一个计算机病毒查杀进程来周期性的更新病毒库。某个用户进程可能会在所有用户上网的时候打印文件以及刻录 CD-ROM，这些活动都需要管理。于是一个支持多进程的多道程序系统就会显得很有必要了。



在许多多道程序系统中，CPU 会在进程间快速切换，使每个程序运行几十或者几百毫秒。然而，严格意义来说，在某一个瞬间，CPU 只能运行一个进程，然而我们如果把时间定位为 1 秒内的话，它可能运行多个进程。这样就会让我们产生并行的错觉。有时候人们说的 伪并行(pseudoparallelism) 就是这种情况，以此来区分多处理器系统(该系统由两个或多个 CPU 来共享同一个物理内存)



>再来详细解释一下伪并行：伪并行是指单核或多核处理器同时执行多个进程，从而使程序更快。 通过以非常有限的时间间隔在程序之间快速切换CPU，因此会产生并行感。 缺点是 CPU 时间可能分配给下一个进程，也可能不分配给下一个进程。



因为 CPU 执行速度很快，进程间的换进换出也非常迅速，因此我们很难对多个并行进程进行跟踪，所以，在经过多年的努力后，操作系统的设计者开发了用于描述并行的一种概念模型（顺序进程），使得并行更加容易理解和分析，对该模型的探讨，也是本篇文章的主题。下面我们就来探讨一下进程模型



进程模型



在进程模型中，所有计算机上运行的软件，通常也包括操作系统，被组织为若干顺序进程(sequential processes)，简称为 进程(process) 。一个进程就是一个正在执行的程序的实例，进程也包括程序计数器、寄存器和变量的当前值。从概念上来说，每个进程都有各自的虚拟 CPU，但是实际情况是 CPU 会在各个进程之间进行来回切换。





如上图所示，这是一个具有 4 个程序的多道处理程序，在进程不断切换的过程中，程序计数器也在不同的变化。





在上图中，这 4 道程序被抽象为 4 个拥有各自控制流程（即每个自己的程序计数器）的进程，并且每个程序都独立的运行。当然，实际上只有一个物理程序计数器，每个程序要运行时，其逻辑程序计数器会装载到物理程序计数器中。当程序运行结束后，其物理程序计数器就会是真正的程序计数器，然后再把它放回进程的逻辑计数器中。



从下图我们可以看到，在观察足够长的一段时间后，所有的进程都运行了，但在任何一个给定的瞬间仅有一个进程真正运行。





因此，当我们说一个 CPU 只能真正一次运行一个进程的时候，即使有 2 个核（或 CPU），每一个核也只能一次运行一个线程。



由于 CPU 会在各个进程之间来回快速切换，所以每个进程在 CPU 中的运行时间是无法确定的。并且当同一个进程再次在 CPU 中运行时，其在 CPU 内部的运行时间往往也是不固定的。进程和程序之间的区别是非常微妙的，但是通过一个例子可以让你加以区分：想想一位会做饭的计算机科学家正在为他的女儿制作生日蛋糕。他有做生日蛋糕的食谱，厨房里有所需的原谅：面粉、鸡蛋、糖、香草汁等。在这个比喻中，做蛋糕的食谱就是程序、计算机科学家就是 CPU、而做蛋糕的各种原谅都是输入数据。进程就是科学家阅读食谱、取来各种原料以及烘焙蛋糕等一系例了动作的总和。



现在假设科学家的儿子跑过来告诉他，说他的头被蜜蜂蜇了一下，那么此时科学家会记录出来他做蛋糕这个过程到了哪一步，然后拿出急救手册，按照上面的步骤给他儿子实施救助。这里，会涉及到进程之间的切换，科学家（CPU）会从做蛋糕（进程）切换到实施医疗救助（另一个进程）。等待伤口处理完毕后，科学家会回到刚刚记录做蛋糕的那一步，继续制作。



这里的关键思想是认识到一个进程所需的条件，进程是某一类特定活动的总和，它有程序、输入输出以及状态。单个处理器可以被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另外一个进程提供服务。另外需要注意的是，如果一个进程运行了两遍，则被认为是两个进程。那么我们了解到进程模型后，那么进程是如何创建的呢？



进程的创建



操作系统需要一些方式来创建进程。下面是一些创建进程的方式



• 系统初始化（init）

• 正在运行的程序执行了创建进程的系统调用（比如 fork）

• 用户请求创建一个新进程

• 初始化一个批处理工作



系统初始化



启动操作系统时，通常会创建若干个进程。其中有些是前台进程(numerous processes)，也就是同用户进行交互并替他们完成工作的进程。一些运行在后台，并不与特定的用户进行交互，例如，设计一个进程来接收发来的电子邮件，这个进程大部分的时间都在休眠，但是只要邮件到来后这个进程就会被唤醒。还可以设计一个进程来接收对该计算机上网页的传入请求，在请求到达的进程唤醒来处理网页的传入请求。进程运行在后台用来处理一些活动像是 e-mail，web 网页，新闻，打印等等被称为 守护进程(daemons)。大型系统会有很多守护进程。在 UNIX 中，ps 程序可以列出正在运行的进程， 在 Windows 中，可以使用任务管理器。



系统调用创建



除了在启动阶段创建进程之外，一些新的进程也可以在后面创建。通常，一个正在运行的进程会发出系统调用用来创建一个或多个新进程来帮助其完成工作。例如，如果有大量的数据需要经过网络调取并进行顺序处理，那么创建一个进程读数据，并把数据放到共享缓冲区中，而让第二个进程取走并正确处理会比较容易些。在多处理器中，让每个进程运行在不同的 CPU 上也可以使工作做的更快。



用户请求创建



在许多交互式系统中，输入一个命令或者双击图标就可以启动程序，以上任意一种操作都可以选择开启一个新的进程，在基本的 UNIX 系统中运行 X，新进程将接管启动它的窗口。在 Windows 中启动进程时，它一般没有窗口，但是它可以创建一个或多个窗口。每个窗口都可以运行进程。通过鼠标或者命令就可以切换窗口并与进程进行交互。



>交互式系统是以人与计算机之间大量交互为特征的计算机系统，比如游戏、web浏览器，IDE 等集成开发环境。



批处理创建



最后一种创建进程的情形会在大型机的批处理系统中应用。用户在这种系统中提交批处理作业。当操作系统决定它有资源来运行另一个任务时，它将创建一个新进程并从其中的输入队列中运行下一个作业。



从技术上讲，在所有这些情况下，让现有流程执行流程是通过创建系统调用来创建新流程的。该进程可能是正在运行的用户进程，是从键盘或鼠标调用的系统进程或批处理程序。这些就是系统调用创建新进程的过程。该系统调用告诉操作系统创建一个新进程，并直接或间接指示在其中运行哪个程序。



在 UNIX 中，仅有一个系统调用来创建一个新的进程，这个系统调用就是 fork。这个调用会创建一个与调用进程相关的副本。在 fork 后，一个父进程和子进程会有相同的内存映像，相同的环境字符串和相同的打开文件。通常，子进程会执行 execve 或者一个简单的系统调用来改变内存映像并运行一个新的程序。例如，当一个用户在 shell 中输出 sort 命令时，shell 会 fork 一个子进程然后子进程去执行 sort 命令。这两步过程的原因是允许子进程在 fork 之后但在 execve 之前操作其文件描述符，以完成标准输入，标准输出和标准错误的重定向。



在 Windows 中，情况正相反，一个简单的 Win32 功能调用 CreateProcess，会处理流程创建并将正确的程序加载到新的进程中。这个调用会有 10 个参数，包括了需要执行的程序、输入给程序的命令行参数、各种安全属性、有关打开的文件是否继承控制位、优先级信息、进程所需要创建的窗口规格以及指向一个结构的指针，在该结构中新创建进程的信息被返回给调用者。除了 CreateProcess Win 32 中大概有 100 个其他的函数用于处理进程的管理，同步以及相关的事务。下面是 UNIX 操作系统和 Windows 操作系统系统调用的对比



| UNIX | Win32 | 说明 |

| ------- | ------------------- | ------------------------------------- |

| fork | CreateProcess | 创建一个新进程 |

| waitpid | WaitForSingleObject | 等待一个进程退出 |

| execve | none | CraeteProcess = fork + servvice |

| exit | ExitProcess | 终止执行 |

| open | CreateFile | 创建一个文件或打开一个已有的文件 |

| close | CloseHandle | 关闭文件 |

| read | ReadFile | 从单个文件中读取数据 |

| write | WriteFile | 向单个文件写数据 |

| lseek | SetFilePointer | 移动文件指针 |

| stat | GetFileAttributesEx | 获得不同的文件属性 |

| mkdir | CreateDirectory | 创建一个新的目录 |

| rmdir | RemoveDirectory | 移除一个空的目录 |

| link | none | Win32 不支持 link |

| unlink | DeleteFile | 销毁一个已有的文件 |

| mount | none | Win32 不支持 mount |

| umount | none | Win32 不支持 mount，所以也不支持mount |

| chdir | SetCurrentDirectory | 切换当前工作目录 |

| chmod | none | Win32 不支持安全 |

| kill | none | Win32 不支持信号 |

| time | GetLocalTime | 获取当前时间 |



在 UNIX 和 Windows 中，进程创建之后，父进程和子进程有各自不同的地址空间。如果其中某个进程在其地址空间中修改了一个词，这个修改将对另一个进程不可见。在 UNIX 中，子进程的地址空间是父进程的一个拷贝，但是确是两个不同的地址空间；不可写的内存区域是共享的。某些 UNIX 实现是正是在两者之间共享，因为它不能被修改。或者，子进程共享父进程的所有内存，但是这种情况下内存通过 写时复制(copy-on-write) 共享，这意味着一旦两者之一想要修改部分内存，则这块内存首先被明确的复制，以确保修改发生在私有内存区域。再次强调，可写的内存是不能被共享的。但是，对于一个新创建的进程来说，确实有可能共享创建者的资源，比如可以共享打开的文件。在 Windows 中，从一开始父进程的地址空间和子进程的地址空间就是不同的。



进程的终止



进程在创建之后，它就开始运行并做完成任务。然而，没有什么事儿是永不停歇的，包括进程也一样。进程早晚会发生终止，但是通常是由于以下情况触发的



• 正常退出(自愿的)

• 错误退出(自愿的)

• 严重错误(非自愿的)

• 被其他进程杀死(非自愿的)



正常退出



多数进程是由于完成了工作而终止。当编译器完成了所给定程序的编译之后，编译器会执行一个系统调用告诉操作系统它完成了工作。这个调用在 UNIX 中是 exit ，在 Windows 中是 ExitProcess。面向屏幕中的软件也支持自愿终止操作。字处理软件、Internet 浏览器和类似的程序中总有一个供用户点击的图标或菜单项，用来通知进程删除它锁打开的任何临时文件，然后终止。



错误退出



进程发生终止的第二个原因是发现严重错误，例如，如果用户执行如下命令



cc foo.c	



为了能够编译 foo.c 但是该文件不存在，于是编译器就会发出声明并退出。在给出了错误参数时，面向屏幕的交互式进程通常并不会直接退出，因为这从用户的角度来说并不合理，用户需要知道发生了什么并想要进行重试，所以这时候应用程序通常会弹出一个对话框告知用户发生了系统错误，是需要重试还是退出。



严重错误



进程终止的第三个原因是由进程引起的错误，通常是由于程序中的错误所导致的。例如，执行了一条非法指令，引用不存在的内存，或者除数是 0 等。在有些系统比如 UNIX 中，进程可以通知操作系统，它希望自行处理某种类型的错误，在这类错误中，进程会收到信号（中断），而不是在这类错误出现时直接终止进程。



被其他进程杀死



第四个终止进程的原因是，某个进程执行系统调用告诉操作系统杀死某个进程。在 UNIX 中，这个系统调用是 kill。在 Win32 中对应的函数是 TerminateProcess（注意不是系统调用）。



进程的层次结构



在一些系统中，当一个进程创建了其他进程后，父进程和子进程就会以某种方式进行关联。子进程它自己就会创建更多进程，从而形成一个进程层次结构。



UNIX 进程体系



在 UNIX 中，进程和它的所有子进程以及子进程的子进程共同组成一个进程组。当用户从键盘中发出一个信号后，该信号被发送给当前与键盘相关的进程组中的所有成员（它们通常是在当前窗口创建的所有活动进程）。每个进程可以分别捕获该信号、忽略该信号或采取默认的动作，即被信号 kill 掉。



这里有另一个例子，可以用来说明层次的作用，考虑 UNIX 在启动时如何初始化自己。一个称为 init 的特殊进程出现在启动映像中 。当 init 进程开始运行时，它会读取一个文件，文件会告诉它有多少个终端。然后为每个终端创建一个新进程。这些进程等待用户登录。如果登录成功，该登录进程就执行一个 shell 来等待接收用户输入指令，这些命令可能会启动更多的进程，以此类推。因此，整个操作系统中所有的进程都隶属于一个单个以 init 为根的进程树。





Windows 进程体系



相反，Windows 中没有进程层次的概念，Windows 中所有进程都是平等的，唯一类似于层次结构的是在创建进程的时候，父进程得到一个特别的令牌（称为句柄），该句柄可以用来控制子进程。然而，这个令牌可能也会移交给别的操作系统，这样就不存在层次结构了。而在 UNIX 中，进程不能剥夺其子进程的 进程权。（这样看来，还是 Windows 比较渣）。



进程状态



尽管每个进程是一个独立的实体，有其自己的程序计数器和内部状态，但是，进程之间仍然需要相互帮助。例如，一个进程的结果可以作为另一个进程的输入，在 shell 命令中



cat chapter1 chapter2 chapter3 | grep tree



第一个进程是 cat，将三个文件级联并输出。第二个进程是 grep，它从输入中选择具有包含关键字 tree 的内容，根据这两个进程的相对速度（这取决于两个程序的相对复杂度和各自所分配到的 CPU 时间片），可能会发生下面这种情况，grep 准备就绪开始运行，但是输入进程还没有完成，于是必须阻塞 grep 进程，直到输入完毕。



当一个进程开始运行时，它可能会经历下面这几种状态





图中会涉及三种状态



1. 运行态，运行态指的就是进程实际占用 CPU 时间片运行时

2. 就绪态，就绪态指的是可运行，但因为其他进程正在运行而处于就绪状态

3. 阻塞态，除非某种外部事件发生，否则进程不能运行



逻辑上来说，运行态和就绪态是很相似的。这两种情况下都表示进程可运行，但是第二种情况没有获得 CPU 时间分片。第三种状态与前两种状态不同的原因是这个进程不能运行，CPU 空闲时也不能运行。



三种状态会涉及四种状态间的切换，在操作系统发现进程不能继续执行时会发生状态1的轮转，在某些系统中进程执行系统调用，例如 pause，来获取一个阻塞的状态。在其他系统中包括 UNIX，当进程从管道或特殊文件（例如终端）中读取没有可用的输入时，该进程会被自动终止。



转换 2 和转换 3 都是由进程调度程序（操作系统的一部分）引起的，进程本身不知道调度程序的存在。转换 2 的出现说明进程调度器认定当前进程已经运行了足够长的时间，是时候让其他进程运行 CPU 时间片了。当所有其他进程都运行过后，这时候该是让第一个进程重新获得 CPU 时间片的时候了，就会发生转换 3。



>程序调度指的是，决定哪个进程优先被运行和运行多久，这是很重要的一点。已经设计出许多算法来尝试平衡系统整体效率与各个流程之间的竞争需求。



当进程等待的一个外部事件发生时（如从外部输入一些数据后），则发生转换 4。如果此时没有其他进程在运行，则立刻触发转换 3，该进程便开始运行，否则该进程会处于就绪阶段，等待 CPU 空闲后再轮到它运行。



从上面的观点引入了下面的模型





操作系统最底层的就是调度程序，在它上面有许多进程。所有关于中断处理、启动进程和停止进程的具体细节都隐藏在调度程序中。事实上，调度程序只是一段非常小的程序。



进程的实现



操作系统为了执行进程间的切换，会维护着一张表格，这张表就是 进程表(process table)。每个进程占用一个进程表项。该表项包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开文件的状态、账号和调度信息，以及其他在进程由运行态转换到就绪态或阻塞态时所必须保存的信息，从而保证该进程随后能再次启动，就像从未被中断过一样。



下面展示了一个典型系统中的关键字段





第一列内容与进程管理有关，第二列内容与 存储管理有关，第三列内容与文件管理有关。



存储管理的 text segment 、 data segment、stack segment 更多了解见下面这篇文章



程序员需要了解的硬核知识之汇编语言(全)



现在我们应该对进程表有个大致的了解了，就可以在对单个 CPU 上如何运行多个顺序进程的错觉做更多的解释。与每一 I/O 类相关联的是一个称作 中断向量(interrupt vector) 的位置（靠近内存底部的固定区域）。它包含中断服务程序的入口地址。假设当一个磁盘中断发生时，用户进程 3 正在运行，则中断硬件将程序计数器、程序状态字、有时还有一个或多个寄存器压入堆栈，计算机随即跳转到中断向量所指示的地址。这就是硬件所做的事情。然后软件就随即接管一切剩余的工作。



当中断结束后，操作系统会调用一个 C 程序来处理中断剩下的工作。在完成剩下的工作后，会使某些进程就绪，接着调用调度程序，决定随后运行哪个进程。然后将控制权转移给一段汇编语言代码，为当前的进程装入寄存器值以及内存映射并启动该进程运行，下面显示了中断处理和调度的过程。



1. 硬件压入堆栈程序计数器等



1. 硬件从中断向量装入新的程序计数器



1. 汇编语言过程保存寄存器的值



1. 汇编语言过程设置新的堆栈



1. C 中断服务器运行（典型的读和缓存写入）



1. 调度器决定下面哪个程序先运行



1. C 过程返回至汇编代码



1. 汇编语言过程开始运行新的当前进程



一个进程在执行过程中可能被中断数千次，但关键每次中断后，被中断的进程都返回到与中断发生前完全相同的状态。



线程



在传统的操作系统中，每个进程都有一个地址空间和一个控制线程。事实上，这是大部分进程的定义。不过，在许多情况下，经常存在同一地址空间中运行多个控制线程的情形，这些线程就像是分离的进程。下面我们就着重探讨一下什么是线程



线程的使用



或许这个疑问也是你的疑问，为什么要在进程的基础上再创建一个线程的概念，准确的说，这其实是进程模型和线程模型的讨论，回答这个问题，可能需要分三步来回答



• 多线程之间会共享同一块地址空间和所有可用数据的能力，这是进程所不具备的

• 线程要比进程更轻量级，由于线程更轻，所以它比进程更容易创建，也更容易撤销。在许多系统中，创建一个线程要比创建一个进程快 10 - 100 倍。

• 第三个原因可能是性能方面的探讨，如果多个线程都是 CPU 密集型的，那么并不能获得性能上的增强，但是如果存在着大量的计算和大量的 I/O 处理，拥有多个线程能在这些活动中彼此重叠进行，从而会加快应用程序的执行速度



多线程解决方案



现在考虑一个线程使用的例子：一个万维网服务器，对页面的请求发送给服务器，而所请求的页面发送回客户端。在多数 web 站点上，某些页面较其他页面相比有更多的访问。例如，索尼的主页比任何一个照相机详情介绍页面具有更多的访问，Web 服务器可以把获得大量访问的页面集合保存在内存中，避免到磁盘去调入这些页面，从而改善性能。这种页面的集合称为 高速缓存(cache)，高速缓存也应用在许多场合中，比如说 CPU 缓存。





上面是一个 web 服务器的组织方式，一个叫做 调度线程(dispatcher thread) 的线程从网络中读入工作请求，在调度线程检查完请求后，它会选择一个空闲的（阻塞的）工作线程来处理请求，通常是将消息的指针写入到每个线程关联的特殊字中。然后调度线程会唤醒正在睡眠中的工作线程，把工作线程的状态从阻塞态变为就绪态。



当工作线程启动后，它会检查请求是否在 web 页面的高速缓存中存在，这个高速缓存是所有线程都可以访问的。如果高速缓存不存在这个 web 页面的话，它会调用一个 read 操作从磁盘中获取页面并且阻塞线程直到磁盘操作完成。当线程阻塞在硬盘操作的期间，为了完成更多的工作，调度线程可能挑选另一个线程运行，也可能把另一个当前就绪的工作线程投入运行。



这种模型允许将服务器编写为顺序线程的集合，在分派线程的程序中包含一个死循环，该循环用来获得工作请求并且把请求派给工作线程。每个工作线程的代码包含一个从调度线程接收的请求，并且检查 web 高速缓存中是否存在所需页面，如果有，直接把该页面返回给客户，接着工作线程阻塞，等待一个新请求的到达。如果没有，工作线程就从磁盘调入该页面，将该页面返回给客户机，然后工作线程阻塞，等待一个新请求。



下面是调度线程和工作线程的代码，这里假设 TRUE 为常数 1 ，buf 和 page 分别是保存工作请求和 Web 页面的相应结构。



调度线程的大致逻辑



while(TRUE){
  get_next_request(&buf);
  handoff_work(&buf);
}



工作线程的大致逻辑



while(TRUE){
  wait_for_work(&buf);
  look_for_page_in_cache(&buf,&page);
  if(page_not_in_cache(&page)){
    read_page_from_disk(&buf,&page);
  }
  return _page(&page);
}



单线程解决方案



现在考虑没有多线程的情况下，如何编写 Web 服务器。我们很容易的就想象为单个线程了，Web 服务器的主循环获取请求并检查请求，并争取在下一个请求之前完成工作。在等待磁盘操作时，服务器空转，并且不处理任何到来的其他请求。结果会导致每秒中只有很少的请求被处理，所以这个例子能够说明多线程提高了程序的并行性并提高了程序的性能。



状态机解决方案



到现在为止，我们已经有了两种解决方案，单线程解决方案和多线程解决方案，其实还有一种解决方案就是 状态机解决方案，它的流程如下



如果目前只有一个非阻塞版本的 read 系统调用可以使用，那么当请求到达服务器时，这个唯一的 read 调用的线程会进行检查，如果能够从高速缓存中得到响应，那么直接返回，如果不能，则启动一个非阻塞的磁盘操作



服务器在表中记录当前请求的状态，然后进入并获取下一个事件，紧接着下一个事件可能就是一个新工作的请求或是磁盘对先前操作的回答。如果是新工作的请求，那么就开始处理请求。如果是磁盘的响应，就从表中取出对应的状态信息进行处理。对于非阻塞式磁盘 I/O 而言，这种响应一般都是信号中断响应。



每次服务器从某个请求工作的状态切换到另一个状态时，都必须显示的保存或者重新装入相应的计算状态。这里，每个计算都有一个被保存的状态，存在一个会发生且使得相关状态发生改变的事件集合，我们把这类设计称为有限状态机(finite-state machine)，有限状态机杯广泛的应用在计算机科学中。



这三种解决方案各有各的特性，多线程使得顺序进程的思想得以保留下来，并且实现了并行性，但是顺序进程会阻塞系统调用；单线程服务器保留了阻塞系统的简易性，但是却放弃了性能。有限状态机的处理方法运用了非阻塞调用和中断，通过并行实现了高性能，但是给编程增加了困难。



| 模型 | 特性 |

| ---------- | -------------------------------- |

| 单线程 | 无并行性，性能较差，阻塞系统调用 |

| 多线程 | 有并行性，阻塞系统调用 |

| 有限状态机 | 并行性，非阻塞系统调用、中断 |



经典的线程模型



理解进程的另一个角度是，用某种方法把相关的资源集中在一起。进程有存放程序正文和数据以及其他资源的地址空间。这些资源包括打开的文件、子进程、即将发生的定时器、信号处理程序、账号信息等。把这些信息放在进程中会比较容易管理。



另一个概念是，进程中拥有一个执行的线程，通常简写为 线程(thread)。线程会有程序计数器，用来记录接着要执行哪一条指令；线程还拥有寄存器，用来保存线程当前正在使用的变量；线程还会有堆栈，用来记录程序的执行路径。尽管线程必须在某个进程中执行，但是进程和线程完完全全是两个不同的概念，并且他们可以分开处理。进程用于把资源集中在一起，而线程则是 CPU 上调度执行的实体。



线程给进程模型增加了一项内容，即在同一个进程中，允许彼此之间有较大的独立性且互不干扰。在一个进程中并行运行多个线程类似于在一台计算机上运行多个进程。在多个线程中，各个线程共享同一地址空间和其他资源。在多个进程中，进程共享物理内存、磁盘、打印机和其他资源。因为线程会包含有一些进程的属性，所以线程被称为轻量的进程(lightweight processes)。多线程(multithreading)一词还用于描述在同一进程中多个线程的情况。



下图我们可以看到三个传统的进程，每个进程有自己的地址空间和单个控制线程。每个线程都在不同的地址空间中运行





下图中，我们可以看到有一个进程三个线程的情况。每个线程都在相同的地址空间中运行。





线程不像是进程那样具备较强的独立性。同一个进程中的所有线程都会有完全一样的地址空间，这意味着它们也共享同样的全局变量。由于每个线程都可以访问进程地址空间内每个内存地址，因此一个线程可以读取、写入甚至擦除另一个线程的堆栈。线程之间除了共享同一内存空间外，还具有如下不同的内容





上图左边的是同一个进程中每个线程共享的内容，上图右边是每个线程中的内容。也就是说左边的列表是进程的属性，右边的列表是线程的属性。



和进程一样，线程可以处于下面这几种状态：运行中、阻塞、就绪和终止（进程图中没有画）。正在运行的线程拥有 CPU 时间片并且状态是运行中。一个被阻塞的线程会等待某个释放它的事件。例如，当一个线程执行从键盘读入数据的系统调用时，该线程就被阻塞直到有输入为止。线程通常会被阻塞，直到它等待某个外部事件的发生或者有其他线程来释放它。线程之间的状态转换和进程之间的状态转换是一样的。



每个线程都会有自己的堆栈，如下图所示





线程系统调用



进程通常会从当前的某个单线程开始，然后这个线程通过调用一个库函数（比如 thread_create ）创建新的线程。线程创建的函数会要求指定新创建线程的名称。创建的线程通常都返回一个线程标识符，该标识符就是新线程的名字。



当一个线程完成工作后，可以通过调用一个函数（比如 thread_exit）来退出。紧接着线程消失，状态变为终止，不能再进行调度。在某些线程的运行过程中，可以通过调用函数例如 thread_join ，表示一个线程可以等待另一个线程退出。这个过程阻塞调用线程直到等待特定的线程退出。在这种情况下，线程的创建和终止非常类似于进程的创建和终止。



另一个常见的线程是调用 thread_yield，它允许线程自动放弃 CPU 从而让另一个线程运行。这样一个调用还是很重要的，因为不同于进程，线程是无法利用时钟中断强制让线程让出 CPU 的。



POSIX 线程



为了使编写可移植线程程序成为可能，IEEE 在 IEEE 标准 1003.1c 中定义了线程标准。线程包被定义为 Pthreads。大部分的 UNIX 系统支持它。这个标准定义了 60 多种功能调用，一一列举不太现实，下面为你列举了一些常用的系统调用。



>POSIX线程（通常称为pthreads）是一种独立于语言而存在的执行模型，以及并行执行模型。它允许程序控制时间上重叠的多个不同的工作流程。每个工作流程都称为一个线程，可以通过调用POSIX Threads API来实现对这些流程的创建和控制。可以把它理解为线程的标准。

>

>POSIX Threads 的实现在许多类似且符合POSIX的操作系统上可用，例如 FreeBSD、NetBSD、OpenBSD、Linux、macOS、Android、Solaris，它在现有 Windows API 之上实现了pthread。

>

>IEEE 是世界上最大的技术专业组织，致力于为人类的利益而发展技术。



| 线程调用 | 描述 |

| -------------------- | ------------------------------ |

| pthread_create | 创建一个新线程 |

| pthread_exit | 结束调用的线程 |

| pthread_join | 等待一个特定的线程退出 |

| pthread_yield | 释放 CPU 来运行另外一个线程 |

| pthreadattrinit | 创建并初始化一个线程的属性结构 |

| pthreadattrdestory | 删除一个线程的属性结构 |



所有的 Pthreads 都有特定的属性，每一个都含有标识符、一组寄存器（包括程序计数器）和一组存储在结构中的属性。这个属性包括堆栈大小、调度参数以及其他线程需要的项目。



新的线程会通过 pthread_create 创建，新创建的线程的标识符会作为函数值返回。这个调用非常像是 UNIX 中的 fork 系统调用（除了参数之外），其中线程标识符起着 PID 的作用，这么做的目的是为了和其他线程进行区分。



当线程完成指派给他的工作后，会通过 pthread_exit 来终止。这个调用会停止线程并释放堆栈。



一般一个线程在继续运行前需要等待另一个线程完成它的工作并退出。可以通过 pthread_join 线程调用来等待别的特定线程的终止。而要等待线程的线程标识符作为一个参数给出。



有时会出现这种情况：一个线程逻辑上没有阻塞，但感觉上它已经运行了足够长的时间并且希望给另外一个线程机会去运行。这时候可以通过 pthread_yield 来完成。



下面两个线程调用是处理属性的。pthread_attr_init 建立关联一个线程的属性结构并初始化成默认值，这些值（例如优先级）可以通过修改属性结构的值来改变。



最后，pthread_attr_destroy 删除一个线程的结构，释放它占用的内存。它不会影响调用它的线程，这些线程会一直存在。



为了更好的理解 pthread 是如何工作的，考虑下面这个例子



#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#define NUMBER_OF_THREADS 10
void *print_hello_world(vvoid *tid){
  /* 输出线程的标识符，然后退出 */
  printf("Hello World. Greetings from thread %d\n",tid);
  pthread_exit(NULL);
}
int main(int argc,char *argv[]){
  /* 主程序创建 10 个线程，然后退出 */
  pthread_t threads[NUMBER_OF_THREADS];
  int status,i;
 	
  for(int i = 0;i < NUMBER_OF_THREADS;i++){
    printf("Main here. Creating thread %d\n",i);
    status = pthread_create(&threads[i], NULL, print_hello_world, (void *)i);
    
    if(status != 0){
      printf("Oops. pthread_create returned error code %d\n",status);
      exit(-1);
    }
  }
  exit(NULL);
}



主线程在宣布它的指责之后，循环 NUMBER_OF_THREADS 次，每次创建一个新的线程。如果线程创建失败，会打印出一条信息后退出。在创建完成所有的工作后，主程序退出。



线程实现



主要有三种实现方式



• 在用户空间中实现线程；

• 在内核空间中实现线程；

• 在用户和内核空间中混合实现线程。



下面我们分开讨论一下



在用户空间中实现线程



第一种方法是把整个线程包放在用户空间中，内核对线程一无所知，它不知道线程的存在。所有的这类实现都有同样的通用结构





线程在运行时系统之上运行，运行时系统是管理线程过程的集合，包括前面提到的四个过程： pthreadcreate, pthreadexit, pthreadjoin 和 pthreadyield。



>运行时系统(Runtime System) 也叫做运行时环境，该运行时系统提供了程序在其中运行的环境。此环境可能会解决许多问题，包括应用程序内存的布局，程序如何访问变量，在过程之间传递参数的机制，与操作系统的接口等等。编译器根据特定的运行时系统进行假设以生成正确的代码。通常，运行时系统将负责设置和管理堆栈，并且会包含诸如垃圾收集，线程或语言内置的其他动态的功能。



在用户空间管理线程时，每个进程需要有其专用的线程表(thread table)，用来跟踪该进程中的线程。这些表和内核中的进程表类似，不过它仅仅记录各个线程的属性，如每个线程的程序计数器、堆栈指针、寄存器和状态。该线程标由运行时系统统一管理。当一个线程转换到就绪状态或阻塞状态时，在该线程表中存放重新启动该线程的所有信息，与内核在进程表中存放的信息完全一样。



在用户空间实现线程的优势



在用户空间中实现线程要比在内核空间中实现线程具有这些方面的优势：考虑如果在线程完成时或者是在调用 pthread_yield 时，必要时会进程线程切换，然后线程的信息会被保存在运行时环境所提供的线程表中，然后，线程调度程序来选择另外一个需要运行的线程。保存线程的状态和调度程序都是本地过程，所以启动他们比进行内核调用效率更高。因而不需要切换到内核，也就不需要上下文切换，也不需要对内存高速缓存进行刷新，因为线程调度非常便捷，因此效率比较高。



在用户空间实现线程还有一个优势就是它允许每个进程有自己定制的调度算法。例如在某些应用程序中，那些具有垃圾收集线程的应用程序（知道是谁了吧）就不用担心自己线程会不会在不合适的时候停止，这是一个优势。用户线程还具有较好的可扩展性，因为内核空间中的内核线程需要一些表空间和堆栈空间，如果内核线程数量比较大，容易造成问题。



在用户空间实现线程的劣势



尽管在用户空间实现线程会具有一定的性能优势，但是劣势还是很明显的，你如何实现阻塞系统调用呢？假设在还没有任何键盘输入之前，一个线程读取键盘，让线程进行系统调用是不可能的，因为这会停止所有的线程。所以，使用线程的一个目标是能够让线程进行阻塞调用，并且要避免被阻塞的线程影响其他线程。



与阻塞调用类似的问题是缺页中断问题，实际上，计算机并不会把所有的程序都一次性的放入内存中，如果某个程序发生函数调用或者跳转指令到了一条不在内存的指令上，就会发生页面故障，而操作系统将到磁盘上取回这个丢失的指令，这就称为缺页故障。而在对所需的指令进行读入和执行时，相关的进程就会被阻塞。如果只有一个线程引起页面故障，内核由于甚至不知道有线程存在，通常会吧整个进程阻塞直到磁盘 I/O 完成为止，尽管其他的线程是可以运行的。



另外一个问题是，如果一个线程开始运行，该线程所在进程中的其他线程都不能运行，除非第一个线程自愿的放弃 CPU，在一个单进程内部，没有时钟中断，所以不可能使用轮转调度的方式调度线程。除非其他线程能够以自己的意愿进入运行时环境，否则调度程序没有可以调度线程的机会。



在内核中实现线程



现在我们考虑使用内核来实现线程的情况，此时不再需要运行时环境了。另外，每个进程中也没有线程表。相反，在内核中会有用来记录系统中所有线程的线程表。当某个线程希望创建一个新线程或撤销一个已有线程时，它会进行一个系统调用，这个系统调用通过对线程表的更新来完成线程创建或销毁工作。





内核中的线程表持有每个线程的寄存器、状态和其他信息。这些信息和用户空间中的线程信息相同，但是位置却被放在了内核中而不是用户空间中。另外，内核还维护了一张进程表用来跟踪系统状态。



所有能够阻塞的调用都会通过系统调用的方式来实现，当一个线程阻塞时，内核可以进行选择，是运行在同一个进程中的另一个线程（如果有就绪线程的话）还是运行一个另一个进程中的线程。但是在用户实现中，运行时系统始终运行自己的线程，直到内核剥夺它的 CPU 时间片（或者没有可运行的线程存在了）为止。



由于在内核中创建或者销毁线程的开销比较大，所以某些系统会采用可循环利用的方式来回收线程。当某个线程被销毁时，就把它标志为不可运行的状态，但是其内部结构没有受到影响。稍后，在必须创建一个新线程时，就会重新启用旧线程，把它标志为可用状态。



如果某个进程中的线程造成缺页故障后，内核很容易的就能检查出来是否有其他可运行的线程，如果有的话，在等待所需要的页面从磁盘读入时，就选择一个可运行的线程运行。这样做的缺点是系统调用的代价比较大，所以如果线程的操作（创建、终止）比较多，就会带来很大的开销。



混合实现



结合用户空间和内核空间的优点，设计人员采用了一种内核级线程的方式，然后将用户级线程与某些或者全部内核线程多路复用起来





在这种模型中，编程人员可以自由控制用户线程和内核线程的数量，具有很大的灵活度。采用这种方法，内核只识别内核级线程，并对其进行调度。其中一些内核级线程会被多个用户级线程多路复用。



进程间通信



进程是需要频繁的和其他进程进行交流的。例如，在一个 shell 管道中，第一个进程的输出必须传递给第二个进程，这样沿着管道进行下去。因此，进程之间如果需要通信的话，必须要使用一种良好的数据结构以至于不能被中断。下面我们会一起讨论有关 进程间通信(Inter Process Communication, IPC) 的问题。



关于进程间的通信，这里有三个问题



• 上面提到了第一个问题，那就是一个进程如何传递消息给其他进程。

• 第二个问题是如何确保两个或多个线程之间不会相互干扰。例如，两个航空公司都试图为不同的顾客抢购飞机上的最后一个座位。

• 第三个问题是数据的先后顺序的问题，如果进程 A 产生数据并且进程 B 打印数据。则进程 B 打印数据之前需要先等 A 产生数据后才能够进行打印。



需要注意的是，这三个问题中的后面两个问题同样也适用于线程



第一个问题在线程间比较好解决，因为它们共享一个地址空间，它们具有相同的运行时环境，可以想象你在用高级语言编写多线程代码的过程中，线程通信问题是不是比较容易解决？



另外两个问题也同样适用于线程，同样的问题可用同样的方法来解决。我们后面会慢慢讨论这三个问题，你现在脑子中大致有个印象即可。



竞态条件



在一些操作系统中，协作的进程可能共享一些彼此都能读写的公共资源。公共资源可能在内存中也可能在一个共享文件。为了讲清楚进程间是如何通信的，这里我们举一个例子：一个后台打印程序。当一个进程需要打印某个文件时，它会将文件名放在一个特殊的后台目录(spooler directory)中。另一个进程 打印后台进程(printer daemon) 会定期的检查是否需要文件被打印，如果有的话，就打印并将该文件名从目录下删除。



假设我们的后台目录有非常多的 槽位(slot)，编号依次为 0，1，2，...，每个槽位存放一个文件名。同时假设有两个共享变量：out，指向下一个需要打印的文件；in，指向目录中下个空闲的槽位。可以把这两个文件保存在一个所有进程都能访问的文件中，该文件的长度为两个字。在某一时刻，0 至 3 号槽位空，4 号至 6 号槽位被占用。在同一时刻，进程 A 和 进程 B 都决定将一个文件排队打印，情况如下





墨菲法则(Murphy) 中说过，任何可能出错的地方终将出错，这句话生效时，可能发生如下情况。



进程 A 读到 in 的值为 7，将 7 存在一个局部变量 next_free_slot 中。此时发生一次时钟中断，CPU 认为进程 A 已经运行了足够长的时间，决定切换到进程 B 。进程 B 也读取 in 的值，发现是 7，然后进程 B 将 7 写入到自己的局部变量 next_free_slot 中，在这一时刻两个进程都认为下一个可用槽位是 7 。



进程 B 现在继续运行，它会将打印文件名写入到 slot 7 中，然后把 in 的指针更改为 8 ，然后进程 B 离开去做其他的事情



现在进程 A 开始恢复运行，由于进程 A 通过检查 next_free_slot也发现 slot 7 的槽位是空的，于是将打印文件名存入 slot 7 中，然后把 in 的值更新为 8 ，由于 slot 7 这个槽位中已经有进程 B 写入的值，所以进程 A 的打印文件名会把进程 B 的文件覆盖，由于打印机内部是无法发现是哪个进程更新的，它的功能比较局限，所以这时候进程 B 永远无法打印输出，类似这种情况，即两个或多个线程同时对一共享数据进行修改，从而影响程序运行的正确性时，这种就被称为竞态条件(race condition)。调试竞态条件是一种非常困难的工作，因为绝大多数情况下程序运行良好，但在极少数的情况下会发生一些无法解释的奇怪现象。



临界区



不仅共享资源会造成竞态条件，事实上共享文件、共享内存也会造成竞态条件、那么该如何避免呢？或许一句话可以概括说明：禁止一个或多个进程在同一时刻对共享资源（包括共享内存、共享文件等）进行读写。换句话说，我们需要一种 互斥(mutual exclusion) 条件，这也就是说，如果一个进程在某种方式下使用共享变量和文件的话，除该进程之外的其他进程就禁止做这种事（访问统一资源）。上面问题的纠结点在于，在进程 A 对共享变量的使用未结束之前进程 B 就使用它。在任何操作系统中，为了实现互斥操作而选用适当的原语是一个主要的设计问题，接下来我们会着重探讨一下。



避免竞争问题的条件可以用一种抽象的方式去描述。大部分时间，进程都会忙于内部计算和其他不会导致竞争条件的计算。然而，有时候进程会访问共享内存或文件，或者做一些能够导致竞态条件的操作。我们把对共享内存进行访问的程序片段称作 临界区域(critical region) 或 临界区(critical section)。如果我们能够正确的操作，使两个不同进程不可能同时处于临界区，就能避免竞争条件，这也是从操作系统设计角度来进行的。



尽管上面这种设计避免了竞争条件，但是不能确保并发线程同时访问共享数据的正确性和高效性。一个好的解决方案，应该包含下面四种条件



1. 任何时候两个进程不能同时处于临界区

2. 不应对 CPU 的速度和数量做任何假设

3. 位于临界区外的进程不得阻塞其他进程

4. 不能使任何进程无限等待进入临界区





从抽象的角度来看，我们通常希望进程的行为如上图所示，在 t1 时刻，进程 A 进入临界区，在 t2 的时刻，进程 B 尝试进入临界区，因为此时进程 A 正在处于临界区中，所以进程 B 会阻塞直到 t3 时刻进程 A 离开临界区，此时进程 B 能够允许进入临界区。最后，在 t4 时刻，进程 B 离开临界区，系统恢复到没有进程的原始状态。



忙等互斥



下面我们会继续探讨实现互斥的各种设计，在这些方案中，当一个进程正忙于更新其关键区域的共享内存时，没有其他进程会进入其关键区域，也不会造成影响。



屏蔽中断



在单处理器系统上，最简单的解决方案是让每个进程在进入临界区后立即屏蔽所有中断，并在离开临界区之前重新启用它们。屏蔽中断后，时钟中断也会被屏蔽。CPU 只有发生时钟中断或其他中断时才会进行进程切换。这样，在屏蔽中断后 CPU 不会切换到其他进程。所以，一旦某个进程屏蔽中断之后，它就可以检查和修改共享内存，而不用担心其他进程介入访问共享数据。



这个方案可行吗？进程进入临界区域是由谁决定的呢？不是用户进程吗？当进程进入临界区域后，用户进程关闭中断，如果经过一段较长时间后进程没有离开，那么中断不就一直启用不了，结果会如何？可能会造成整个系统的终止。而且如果是多处理器的话，屏蔽中断仅仅对执行 disable 指令的 CPU 有效。其他 CPU 仍将继续运行，并可以访问共享内存。



另一方面，对内核来说，当它在执行更新变量或列表的几条指令期间将中断屏蔽是很方便的。例如，如果多个进程处理就绪列表中的时候发生中断，则可能会发生竞态条件的出现。所以，屏蔽中断对于操作系统本身来说是一项很有用的技术，但是对于用户线程来说，屏蔽中断却不是一项通用的互斥机制。



锁变量



作为第二种尝试，可以寻找一种软件层面解决方案。考虑有单个共享的（锁）变量，初始为值为 0 。当一个线程想要进入关键区域时，它首先会查看锁的值是否为 0 ，如果锁的值是 0 ，进程会把它设置为 1 并让进程进入关键区域。如果锁的状态是 1，进程会等待直到锁变量的值变为 0 。因此，锁变量的值是 0 则意味着没有线程进入关键区域。如果是 1 则意味着有进程在关键区域内。我们对上图修改后，如下所示





这种设计方式是否正确呢？是否存在纰漏呢？假设一个进程读出锁变量的值并发现它为 0 ，而恰好在它将其设置为 1 之前，另一个进程调度运行，读出锁的变量为0 ，并将锁的变量设置为 1 。然后第一个线程运行，把锁变量的值再次设置为 1，此时，临界区域就会有两个进程在同时运行。





也许有的读者可以这么认为，在进入前检查一次，在要离开的关键区域再检查一次不就解决了吗？实际上这种情况也是于事无补，因为在第二次检查期间其他线程仍有可能修改锁变量的值，换句话说，这种 set-before-check 不是一种 原子性 操作，所以同样还会发生竞争条件。



严格轮询法



第三种互斥的方式先抛出来一段代码，这里的程序是用 C 语言编写，之所以采用 C 是因为操作系统普遍是用 C 来编写的（偶尔会用 C++），而基本不会使用 Java 、Modula3 或 Pascal 这样的语言，Java 中的 native 关键字底层也是 C 或 C++ 编写的源码。对于编写操作系统而言，需要使用 C 语言这种强大、高效、可预知和有特性的语言，而对于 Java ，它是不可预知的，因为它在关键时刻会用完存储器，而在不合适的时候会调用垃圾回收机制回收内存。在 C 语言中，这种情况不会发生，C 语言中不会主动调用垃圾回收回收内存。有关 C 、C++ 、Java 和其他四种语言的比较可以参考 链接



进程 0 的代码



while(TRUE){
  while(turn != 0){
    /* 进入关键区域 */
    critical_region();
    turn = 1;
    /* 离开关键区域 */
    noncritical_region();
  }
}



进程 1 的代码



while(TRUE){
  while(turn != 1){
    critical_region();
    turn = 0;
    noncritical_region();
  }
}



在上面代码中，变量 turn，初始值为 0 ，用于记录轮到那个进程进入临界区，并检查或更新共享内存。开始时，进程 0 检查 turn，发现其值为 0 ，于是进入临界区。进程 1 也发现其值为 0 ，所以在一个等待循环中不停的测试 turn，看其值何时变为 1。连续检查一个变量直到某个值出现为止，这种方法称为 忙等待(busywaiting)。由于这种方式浪费 CPU 时间，所以这种方式通常应该要避免。只有在有理由认为等待时间是非常短的情况下，才能够使用忙等待。用于忙等待的锁，称为 自旋锁(spinlock)。



进程 0 离开临界区时，它将 turn 的值设置为 1，以便允许进程 1 进入其临界区。假设进程 1 很快便离开了临界区，则此时两个进程都处于临界区之外，turn 的值又被设置为 0 。现在进程 0 很快就执行完了整个循环，它退出临界区，并将 turn 的值设置为 1。此时，turn 的值为 1，两个进程都在其临界区外执行。



突然，进程 0 结束了非临界区的操作并返回到循环的开始。但是，这时它不能进入临界区，因为 turn 的当前值为 1，此时进程 1 还忙于非临界区的操作，进程 0 只能继续 while 循环，直到进程 1 把 turn 的值改为 0 。这说明，在一个进程比另一个进程执行速度慢了很多的情况下，轮流进入临界区并不是一个好的方法。



这种情况违反了前面的叙述 3 ，即 位于临界区外的进程不得阻塞其他进程，进程 0 被一个临界区外的进程阻塞。由于违反了第三条，所以也不能作为一个好的方案。



Peterson 解法



荷兰数学家 T.Dekker 通过将锁变量与警告变量相结合，最早提出了一个不需要严格轮换的软件互斥算法，关于 Dekker 的算法，参考 链接



后来， G.L.Peterson 发现了一种简单很多的互斥算法，它的算法如下



#define FALSE 0
#define TRUE  1
/* 进程数量 */
#define N     2													
/* 现在轮到谁 */
int turn;					
/* 所有值初始化为 0 (FALSE) */
int interested[N];											
/* 进程是 0 或 1 */
void enter_region(int process){					
  
  /* 另一个进程号 */
  int other;														
  
  /* 另一个进程 */
  other = 1 - process;				
  
  /* 表示愿意进入临界区 */
  interested[process] = TRUE;						
  turn = process;
  
  /* 空循环 */
  while(turn == process 
        && interested[other] == true){} 
  
}
void leave_region(int process){
  
  /* 表示离开临界区 */
  interested[process] == FALSE;				 
}



在使用共享变量时（即进入其临界区）之前，各个进程使用各自的进程号 0 或 1 作为参数来调用 enter_region，这个函数调用在需要时将使进程等待，直到能够安全的临界区。在完成对共享变量的操作之后，进程将调用 leave_region 表示操作完成，并且允许其他进程进入。



现在来看看这个办法是如何工作的。一开始，没有任何进程处于临界区中，现在进程 0 调用 enter_region。它通过设置数组元素和将 turn 置为 0 来表示它希望进入临界区。由于进程 1 并不想进入临界区，所以 enterregion 很快便返回。如果进程现在调用 enterregion，进程 1 将在此处挂起直到 interested[0] 变为 FALSE，这种情况只有在进程 0 调用 leave_region 退出临界区时才会发生。



那么上面讨论的是顺序进入的情况，现在来考虑一种两个进程同时调用 enter_region 的情况。它们都将自己的进程存入 turn，但只有最后保存进去的进程号才有效，前一个进程的进程号因为重写而丢失。假如进程 1 是最后存入的，则 turn 为 1 。当两个进程都运行到 while 的时候，进程 0 将不会循环并进入临界区，而进程 1 将会无限循环且不会进入临界区，直到进程 0 退出位置。



TSL 指令



现在来看一种需要硬件帮助的方案。一些计算机，特别是那些设计为多处理器的计算机，都会有下面这条指令



TSL RX,LOCK	



称为 测试并加锁(test and set lock)，它将一个内存字 lock 读到寄存器 RX 中，然后在该内存地址上存储一个非零值。读写指令能保证是一体的，不可分割的，一同执行的。在这个指令结束之前其他处理器均不允许访问内存。执行 TSL 指令的 CPU 将会锁住内存总线，用来禁止其他 CPU 在这个指令结束之前访问内存。



很重要的一点是锁住内存总线和禁用中断不一样。禁用中断并不能保证一个处理器在读写操作之间另一个处理器对内存的读写。也就是说，在处理器 1 上屏蔽中断对处理器 2 没有影响。让处理器 2 远离内存直到处理器 1 完成读写的最好的方式就是锁住总线。这需要一个特殊的硬件（基本上，一根总线就可以确保总线由锁住它的处理器使用，而其他的处理器不能使用）



为了使用 TSL 指令，要使用一个共享变量 lock 来协调对共享内存的访问。当 lock 为 0 时，任何进程都可以使用 TSL 指令将其设置为 1，并读写共享内存。当操作结束时，进程使用 move 指令将 lock 的值重新设置为 0 。



这条指令如何防止两个进程同时进入临界区呢？下面是解决方案



enter_region:
			| 复制锁到寄存器并将锁设为1
			TSL REGISTER,LOCK              
			| 锁是 0 吗？
  		CMP REGISTER,#0						 		
  		| 若不是零，说明锁已被设置，所以循环
  		JNE enter_region					 		
  		| 返回调用者，进入临界区
  		RET												 
       
leave_region:
			| 在锁中存入 0
			MOVE LOCK,#0			      
      | 返回调用者
  		RET												 



我们可以看到这个解决方案的思想和 Peterson 的思想很相似。假设存在如下共 4 指令的汇编语言程序。第一条指令将 lock 原来的值复制到寄存器中并将 lock 设置为 1 ，随后这个原来的值和 0 做对比。如果它不是零，说明之前已经被加过锁，则程序返回到开始并再次测试。经过一段时间后（可长可短），该值变为 0 （当前处于临界区中的进程退出临界区时），于是过程返回，此时已加锁。要清除这个锁也比较简单，程序只需要将 0 存入 lock 即可，不需要特殊的同步指令。



现在有了一种很明确的做法，那就是进程在进入临界区之前会先调用 enter_region，判断是否进行循环，如果lock 的值是 1 ，进行无限循环，如果 lock 是 0，不进入循环并进入临界区。在进程从临界区返回时它调用 leave_region，这会把 lock 设置为 0 。与基于临界区问题的所有解法一样，进程必须在正确的时间调用 enterregion 和 leaveregion ，解法才能奏效。



还有一个可以替换 TSL 的指令是 XCHG，它原子性的交换了两个位置的内容，例如，一个寄存器与一个内存字，代码如下



enter_region:
		| 把 1 放在内存器中
		MOVE REGISTER,#1	
    | 交换寄存器和锁变量的内容
		XCHG REGISTER,LOCK			
    | 锁是 0 吗？
		CMP REGISTER,#0		
    | 若不是 0 ，锁已被设置，进行循环
		JNE enter_region					
    | 返回调用者，进入临界区
		RET														
	
leave_region:				
		| 在锁中存入 0 
		MOVE LOCK,#0	
    | 返回调用者
		RET														



XCHG 的本质上与 TSL 的解决办法一样。所有的 Intel x86 CPU 在底层同步中使用 XCHG 指令。



睡眠与唤醒



上面解法中的 Peterson 、TSL 和 XCHG 解法都是正确的，但是它们都有忙等待的缺点。这些解法的本质上都是一样的，先检查是否能够进入临界区，若不允许，则该进程将原地等待，直到允许为止。



这种方式不但浪费了 CPU 时间，而且还可能引起意想不到的结果。考虑一台计算机上有两个进程，这两个进程具有不同的优先级，H 是属于优先级比较高的进程，L 是属于优先级比较低的进程。进程调度的规则是不论何时只要 H 进程处于就绪态 H 就开始运行。在某一时刻，L 处于临界区中，此时 H 变为就绪态，准备运行（例如，一条 I/O 操作结束）。现在 H 要开始忙等，但由于当 H 就绪时 L 就不会被调度，L 从来不会有机会离开关键区域，所以 H 会变成死循环，有时将这种情况称为优先级反转问题(priority inversion problem)。



现在让我们看一下进程间的通信原语，这些原语在不允许它们进入关键区域之前会阻塞而不是浪费 CPU 时间，最简单的是 sleep 和 wakeup。Sleep 是一个能够造成调用者阻塞的系统调用，也就是说，这个系统调用会暂停直到其他进程唤醒它。wakeup 调用有一个参数，即要唤醒的进程。还有一种方式是 wakeup 和 sleep 都有一个参数，即 sleep 和 wakeup 需要匹配的内存地址。



生产者-消费者问题



作为这些私有原语的例子，让我们考虑生产者-消费者(producer-consumer) 问题，也称作 有界缓冲区(bounded-buffer) 问题。两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者(producer)，将信息放入缓冲区， 另一个是消费者(consumer) ，会从缓冲区中取出。也可以把这个问题一般化为 m 个生产者和 n 个消费者的问题，但是我们这里只讨论一个生产者和一个消费者的情况，这样可以简化实现方案。



如果缓冲队列已满，那么当生产者仍想要将数据写入缓冲区的时候，会出现问题。它的解决办法是让生产者睡眠，也就是阻塞生产者。等到消费者从缓冲区中取出一个或多个数据项时再唤醒它。同样的，当消费者试图从缓冲区中取数据，但是发现缓冲区为空时，消费者也会睡眠，阻塞。直到生产者向其中放入一个新的数据。



这个逻辑听起来比较简单，而且这种方式也需要一种称作 监听 的变量，这个变量用于监视缓冲区的数据，我们暂定为 count，如果缓冲区最多存放 N 个数据项，生产者会每次判断 count 是否达到 N，否则生产者向缓冲区放入一个数据项并增量 count 的值。消费者的逻辑也很相似：首先测试 count 的值是否为 0 ，如果为 0 则消费者睡眠、阻塞，否则会从缓冲区取出数据并使 count 数量递减。每个进程也会检查检查是否其他线程是否应该被唤醒，如果应该被唤醒，那么就唤醒该线程。下面是生产者消费者的代码



/* 缓冲区 slot 槽的数量 */
#define N 100						
/* 缓冲区数据的数量 */
int count = 0										
  
// 生产者
void producer(void){
  int item;
  
  /* 无限循环 */
  while(TRUE){				
    /* 生成下一项数据 */
    item = produce_item()				
    /* 如果缓存区是满的，就会阻塞 */
    if(count == N){
      sleep();									
    }
    
    /* 把当前数据放在缓冲区中 */
    insert_item(item);
    /* 增加缓冲区 count 的数量 */
    count = count + 1;					
    if(count == 1){
      /* 缓冲区是否为空？ */
      wakeup(consumer);					
    }
  }
}
// 消费者
void consumer(void){
  
  int item;
  
  /* 无限循环 */
  while(TRUE){
    /* 如果缓冲区是空的，就会进行阻塞 */
  	if(count == 0){							
      sleep();
    }
    /* 从缓冲区中取出一个数据 */
   	item = remove_item();			
    /* 将缓冲区的 count 数量减一 */
    count = count - 1
    /* 缓冲区满嘛？ */
    if(count == N - 1){					
      wakeup(producer);		
    }
    /* 打印数据项 */
    consumer_item(item);				
  }
  
}



为了在 C 语言中描述像是 sleep 和 wakeup 的系统调用，我们将以库函数调用的形式来表示。它们不是 C 标准库的一部分，但可以在实际具有这些系统调用的任何系统上使用。代码中未实现的 insert_item 和 remove_item 用来记录将数据项放入缓冲区和从缓冲区取出数据等。



现在让我们回到生产者-消费者问题上来，上面代码中会产生竞争条件，因为 count 这个变量是暴露在大众视野下的。有可能出现下面这种情况：缓冲区为空，此时消费者刚好读取 count 的值发现它为 0 。此时调度程序决定暂停消费者并启动运行生产者。生产者生产了一条数据并把它放在缓冲区中，然后增加 count 的值，并注意到它的值是 1 。由于 count 为 0，消费者必须处于睡眠状态，因此生产者调用 wakeup 来唤醒消费者。但是，消费者此时在逻辑上并没有睡眠，所以 wakeup 信号会丢失。当消费者下次启动后，它会查看之前读取的 count 值，发现它的值是 0 ，然后在此进行睡眠。不久之后生产者会填满整个缓冲区，在这之后会阻塞，这样一来两个进程将永远睡眠下去。



引起上面问题的本质是 唤醒尚未进行睡眠状态的进程会导致唤醒丢失。如果它没有丢失，则一切都很正常。一种快速解决上面问题的方式是增加一个唤醒等待位(wakeup waiting bit)。当一个 wakeup 信号发送给仍在清醒的进程后，该位置为 1 。之后，当进程尝试睡眠的时候，如果唤醒等待位为 1 ，则该位清除，而进程仍然保持清醒。



然而，当进程数量有许多的时候，这时你可以说通过增加唤醒等待位的数量来唤醒等待位，于是就有了 2、4、6、8 个唤醒等待位，但是并没有从根本上解决问题。



信号量



信号量是 E.W.Dijkstra 在 1965 年提出的一种方法，它使用一个整形变量来累计唤醒次数，以供之后使用。在他的观点中，有一个新的变量类型称作 信号量(semaphore)。一个信号量的取值可以是 0 ，或任意正数。0 表示的是不需要任何唤醒，任意的正数表示的就是唤醒次数。



Dijkstra 提出了信号量有两个操作，现在通常使用 down 和 up（分别可以用 sleep 和 wakeup 来表示）。down 这个指令的操作会检查值是否大于 0 。如果大于 0 ，则将其值减 1 ；若该值为 0 ，则进程将睡眠，而且此时 down 操作将会继续执行。检查数值、修改变量值以及可能发生的睡眠操作均为一个单一的、不可分割的 原子操作(atomic action) 完成。这会保证一旦信号量操作开始，没有其他的进程能够访问信号量，直到操作完成或者阻塞。这种原子性对于解决同步问题和避免竞争绝对必不可少。



原子性操作指的是在计算机科学的许多其他领域中，一组相关操作全部执行而没有中断或根本不执行。



up 操作会使信号量的值 + 1。如果一个或者多个进程在信号量上睡眠，无法完成一个先前的 down 操作，则由系统选择其中一个并允许该程完成 down 操作。因此，对一个进程在其上睡眠的信号量执行一次 up 操作之后，该信号量的值仍然是 0 ，但在其上睡眠的进程却少了一个。信号量的值增 1 和唤醒一个进程同样也是不可分割的。不会有某个进程因执行 up 而阻塞，正如在前面的模型中不会有进程因执行 wakeup 而阻塞是一样的道理。



用信号量解决生产者 - 消费者问题



用信号量解决丢失的 wakeup 问题，代码如下



/* 定义缓冲区槽的数量 */
#define N 100
/* 信号量是一种特殊的 int */
typedef int semaphore;
/* 控制关键区域的访问 */
semaphore mutex = 1;
/* 统计 buffer 空槽的数量 */
semaphore empty = N;
/* 统计 buffer 满槽的数量 */
semaphore full = 0;												
void producer(void){ 
  
  int item;  
  
  /* TRUE 的常量是 1 */
  while(TRUE){			
    /* 产生放在缓冲区的一些数据 */
    item = producer_item();		
    /* 将空槽数量减 1  */
    down(&empty);	
    /* 进入关键区域  */
    down(&mutex);	
    /* 把数据放入缓冲区中 */
    insert_item(item);
    /* 离开临界区 */
    up(&mutex);	
    /* 将 buffer 满槽数量 + 1 */
    up(&full);														
  }
}
void consumer(void){
  
  int item;
  
  /* 无限循环 */
  while(TRUE){
    /* 缓存区满槽数量 - 1 */
    down(&full);
    /* 进入缓冲区 */	
    down(&mutex);
    /* 从缓冲区取出数据 */
    item = remove_item();	
    /* 离开临界区 */
    up(&mutex);	
    /* 将空槽数目 + 1 */
    up(&empty);	
    /* 处理数据 */
    consume_item(item);											
  }
  
}



为了确保信号量能正确工作，最重要的是要采用一种不可分割的方式来实现它。通常是将 up 和 down 作为系统调用来实现。而且操作系统只需在执行以下操作时暂时屏蔽全部中断：检查信号量、更新、必要时使进程睡眠。由于这些操作仅需要非常少的指令，因此中断不会造成影响。如果使用多个 CPU，那么信号量应该被锁进行保护。使用 TSL 或者 XCHG 指令用来确保同一时刻只有一个 CPU 对信号量进行操作。



使用 TSL 或者 XCHG 来防止几个 CPU 同时访问一个信号量，与生产者或消费者使用忙等待来等待其他腾出或填充缓冲区是完全不一样的。前者的操作仅需要几个毫秒，而生产者或消费者可能需要任意长的时间。



上面这个解决方案使用了三种信号量：一个称为 full，用来记录充满的缓冲槽数目；一个称为 empty，记录空的缓冲槽数目；一个称为 mutex，用来确保生产者和消费者不会同时进入缓冲区。Full 被初始化为 0 ，empty 初始化为缓冲区中插槽数，mutex 初始化为 1。信号量初始化为 1 并且由两个或多个进程使用，以确保它们中同时只有一个可以进入关键区域的信号被称为 二进制信号量(binary semaphores)。如果每个进程都在进入关键区域之前执行 down 操作，而在离开关键区域之后执行 up 操作，则可以确保相互互斥。



现在我们有了一个好的进程间原语的保证。然后我们再来看一下中断的顺序保证



1. 硬件压入堆栈程序计数器等



1. 硬件从中断向量装入新的程序计数器



1. 汇编语言过程保存寄存器的值



1. 汇编语言过程设置新的堆栈



1. C 中断服务器运行（典型的读和缓存写入）



1. 调度器决定下面哪个程序先运行



1. C 过程返回至汇编代码



1. 汇编语言过程开始运行新的当前进程



在使用信号量的系统中，隐藏中断的自然方法是让每个 I/O 设备都配备一个信号量，该信号量最初设置为0。在 I/O 设备启动后，中断处理程序立刻对相关联的信号执行一个 down 操作，于是进程立即被阻塞。当中断进入时，中断处理程序随后对相关的信号量执行一个 up操作，能够使已经阻止的进程恢复运行。在上面的中断处理步骤中，其中的第 5 步 C 中断服务器运行 就是中断处理程序在信号量上执行的一个 up 操作，所以在第 6 步中，操作系统能够执行设备驱动程序。当然，如果有几个进程已经处于就绪状态，调度程序可能会选择接下来运行一个更重要的进程，我们会在后面讨论调度的算法。



上面的代码实际上是通过两种不同的方式来使用信号量的，而这两种信号量之间的区别也是很重要的。mutex 信号量用于互斥。它用于确保任意时刻只有一个进程能够对缓冲区和相关变量进行读写。互斥是用于避免进程混乱所必须的一种操作。



另外一个信号量是关于同步(synchronization)的。full 和 empty 信号量用于确保事件的发生或者不发生。在这个事例中，它们确保了缓冲区满时生产者停止运行；缓冲区为空时消费者停止运行。这两个信号量的使用与 mutex 不同。



互斥量



如果不需要信号量的计数能力时，可以使用信号量的一个简单版本，称为 mutex(互斥量)。互斥量的优势就在于在一些共享资源和一段代码中保持互斥。由于互斥的实现既简单又有效，这使得互斥量在实现用户空间线程包时非常有用。



互斥量是一个处于两种状态之一的共享变量：解锁(unlocked) 和 加锁(locked)。这样，只需要一个二进制位来表示它，不过一般情况下，通常会用一个 整形(integer) 来表示。0 表示解锁，其他所有的值表示加锁，比 1 大的值表示加锁的次数。



mutex 使用两个过程，当一个线程（或者进程）需要访问关键区域时，会调用 mutex_lock 进行加锁。如果互斥锁当前处于解锁状态（表示关键区域可用），则调用成功，并且调用线程可以自由进入关键区域。



另一方面，如果 mutex 互斥量已经锁定的话，调用线程会阻塞直到关键区域内的线程执行完毕并且调用了 mutex_unlock 。如果多个线程在 mutex 互斥量上阻塞，将随机选择一个线程并允许它获得锁。





由于 mutex 互斥量非常简单，所以只要有 TSL 或者是 XCHG 指令，就可以很容易地在用户空间实现它们。用于用户级线程包的 mutex_lock 和 mutex_unlock 代码如下，XCHG 的本质也一样。



mutex_lock:
			| 将互斥信号量复制到寄存器，并将互斥信号量置为1
			TSL REGISTER,MUTEX
      | 互斥信号量是 0 吗？
			CMP REGISTER,#0	
      | 如果互斥信号量为0，它被解锁，所以返回
			JZE ok	
      | 互斥信号正在使用；调度其他线程
			CALL thread_yield	
      | 再试一次
			JMP mutex_lock	
      | 返回调用者，进入临界区
ok: 	RET														
mutex_unlcok:
			| 将 mutex 置为 0 
			MOVE MUTEX,#0	
      | 返回调用者
			RET														



mutexlock 的代码和上面 enterregion 的代码很相似，我们可以对比着看一下





上面代码最大的区别你看出来了吗？



• 根据上面我们对 TSL 的分析，我们知道，如果 TSL 判断没有进入临界区的进程会进行无限循环获取锁，而在 TSL 的处理中，如果 mutex 正在使用，那么就调度其他线程进行处理。所以上面最大的区别其实就是在判断 mutex/TSL 之后的处理。



• 在（用户）线程中，情况有所不同，因为没有时钟来停止运行时间过长的线程。结果是通过忙等待的方式来试图获得锁的线程将永远循环下去，决不会得到锁，因为这个运行的线程不会让其他线程运行从而释放锁，其他线程根本没有获得锁的机会。在后者获取锁失败时，它会调用 thread_yield 将 CPU 放弃给另外一个线程。结果就不会进行忙等待。在该线程下次运行时，它再一次对锁进行测试。



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



我们上面描述的互斥量其实是一套调用框架中的指令。从软件角度来说，总是需要更多的特性和同步原语。例如，有时线程包提供一个调用 mutex_trylock，这个调用尝试获取锁或者返回错误码，但是不会进行加锁操作。这就给了调用线程一个灵活性，以决定下一步做什么，是使用替代方法还是等候下去。



Futexes



随着并行的增加，有效的同步(synchronization)和锁定(locking) 对于性能来说是非常重要的。如果进程等待时间很短，那么自旋锁(Spin lock) 是非常有效；但是如果等待时间比较长，那么这会浪费 CPU 周期。如果进程很多，那么阻塞此进程，并仅当锁被释放的时候让内核解除阻塞是更有效的方式。不幸的是，这种方式也会导致另外的问题：它可以在进程竞争频繁的时候运行良好，但是在竞争不是很激烈的情况下内核切换的消耗会非常大，而且更困难的是，预测锁的竞争数量更不容易。



有一种有趣的解决方案是把两者的优点结合起来，提出一种新的思想，称为 futex，或者是 快速用户空间互斥(fast user space mutex)，是不是听起来很有意思？





futex 是 Linux 中的特性实现了基本的锁定（很像是互斥锁）而且避免了陷入内核中，因为内核的切换的开销非常大，这样做可以大大提高性能。futex 由两部分组成：内核服务和用户库。内核服务提供了了一个 等待队列(wait queue) 允许多个进程在锁上排队等待。除非内核明确的对他们解除阻塞，否则它们不会运行。





对于一个进程来说，把它放到等待队列需要昂贵的系统调用，这种方式应该被避免。在没有竞争的情况下，futex 可以直接在用户空间中工作。这些进程共享一个 32 位整数(integer) 作为公共锁变量。假设锁的初始化为 1，我们认为这时锁已经被释放了。线程通过执行原子性的操作减少并测试(decrement and test) 来抢占锁。decrement and set 是 Linux 中的原子功能，由包裹在 C 函数中的内联汇编组成，并在头文件中进行定义。下一步，线程会检查结果来查看锁是否已经被释放。如果锁现在不是锁定状态，那么刚好我们的线程可以成功抢占该锁。然而，如果锁被其他线程持有，抢占锁的线程不得不等待。在这种情况下，futex 库不会自旋，但是会使用一个系统调用来把线程放在内核中的等待队列中。这样一来，切换到内核的开销已经是合情合理的了，因为线程可以在任何时候阻塞。当线程完成了锁的工作时，它会使用原子性的 增加并测试(increment and test) 释放锁，并检查结果以查看内核等待队列上是否仍阻止任何进程。如果有的话，它会通知内核可以对等待队列中的一个或多个进程解除阻塞。如果没有锁竞争，内核则不需要参与竞争。



Pthreads 中的互斥量



Pthreads 提供了一些功能用来同步线程。最基本的机制是使用互斥量变量，可以锁定和解锁，用来保护每个关键区域。希望进入关键区域的线程首先要尝试获取 mutex。如果 mutex 没有加锁，线程能够马上进入并且互斥量能够自动锁定，从而阻止其他线程进入。如果 mutex 已经加锁，调用线程会阻塞，直到 mutex 解锁。如果多个线程在相同的互斥量上等待，当互斥量解锁时，只有一个线程能够进入并且重新加锁。这些锁并不是必须的，程序员需要正确使用它们。



下面是与互斥量有关的函数调用





向我们想象中的一样，mutex 能够被创建和销毁，扮演这两个角色的分别是 Phread_mutex_init 和 Pthread_mutex_destroy。mutex 也可以通过 Pthreadmutexlock 来进行加锁，如果互斥量已经加锁，则会阻塞调用者。还有一个调用Pthreadmutextrylock 用来尝试对线程加锁，当 mutex 已经被加锁时，会返回一个错误代码而不是阻塞调用者。这个调用允许线程有效的进行忙等。最后，Pthreadmutexunlock 会对 mutex 解锁并且释放一个正在等待的线程。



除了互斥量以外，Pthreads 还提供了第二种同步机制： 条件变量(condition variables) 。mutex 可以很好的允许或阻止对关键区域的访问。条件变量允许线程由于未满足某些条件而阻塞。绝大多数情况下这两种方法是一起使用的。下面我们进一步来研究线程、互斥量、条件变量之间的关联。



下面再来重新认识一下生产者和消费者问题：一个线程将东西放在一个缓冲区内，由另一个线程将它们取出。如果生产者发现缓冲区没有空槽可以使用了，生产者线程会阻塞起来直到有一个线程可以使用。生产者使用 mutex 来进行原子性检查从而不受其他线程干扰。但是当发现缓冲区已经满了以后，生产者需要一种方法来阻塞自己并在以后被唤醒。这便是条件变量做的工作。



下面是一些与条件变量有关的最重要的 pthread 调用





上表中给出了一些调用用来创建和销毁条件变量。条件变量上的主要属性是 Pthread_cond_wait 和 Pthread_cond_signal。前者阻塞调用线程，直到其他线程发出信号为止（使用后者调用）。阻塞的线程通常需要等待唤醒的信号以此来释放资源或者执行某些其他活动。只有这样阻塞的线程才能继续工作。条件变量允许等待与阻塞原子性的进程。Pthreadcondbroadcast 用来唤醒多个阻塞的、需要等待信号唤醒的线程。



>需要注意的是，条件变量（不像是信号量）不会存在于内存中。如果将一个信号量传递给一个没有线程等待的条件变量，那么这个信号就会丢失，这个需要注意



下面是一个使用互斥量和条件变量的例子



#include <stdio.h>
#include <pthread.h>
/* 需要生产的数量 */
#define MAX 1000000000										
pthread_mutex_t the_mutex;
/* 使用信号量 */
pthread_cond_t condc,condp;								
int buffer = 0;
/* 生产数据 */
void *producer(void *ptr){								
  
  int i;
  
  for(int i = 0;i <= MAX;i++){
    /* 缓冲区独占访问，也就是使用 mutex 获取锁 */
    pthread_mutex_lock(&the_mutex);				
    while(buffer != 0){
      pthread_cond_wait(&condp,&the_mutex);
    }
    /* 把他们放在缓冲区中 */
    buffer = i;			
    /* 唤醒消费者 */
    pthread_cond_signal(&condc);	
    /* 释放缓冲区 */
    pthread_mutex_unlock(&the_mutex);			
  }
  pthread_exit(0);
  
}
/* 消费数据 */
void *consumer(void *ptr){								
  
  int i;
  
  for(int i = 0;i <= MAX;i++){
    /* 缓冲区独占访问，也就是使用 mutex 获取锁 */
    pthread_mutex_lock(&the_mutex);				
    while(buffer == 0){
      pthread_cond_wait(&condc,&the_mutex);
    }
    /* 把他们从缓冲区中取出 */
    buffer = 0;	
    /* 唤醒生产者 */
    pthread_cond_signal(&condp);
    /* 释放缓冲区 */
    pthread_mutex_unlock(&the_mutex);			
  }
  pthread_exit(0);
  
}							  



管程



为了能够编写更加准确无误的程序，Brinch Hansen 和 Hoare 提出了一个更高级的同步原语叫做 管程(monitor)。他们两个人的提案略有不同，通过下面的描述你就可以知道。管程是程序、变量和数据结构等组成的一个集合，它们组成一个特殊的模块或者包。进程可以在任何需要的时候调用管程中的程序，但是它们不能从管程外部访问数据结构和程序。下面展示了一种抽象的，类似 Pascal 语言展示的简洁的管程。不能用 C 语言进行描述，因为管程是语言概念而 C 语言并不支持管程。



monitor example
	integer i;
	condition c;
	
	procedure producer();
  ...
	end;	
	
	procedure consumer();
	.
	end;
end monitor;



管程有一个很重要的特性，即在任何时候管程中只能有一个活跃的进程，这一特性使管程能够很方便的实现互斥操作。管程是编程语言的特性，所以编译器知道它们的特殊性，因此可以采用与其他过程调用不同的方法来处理对管程的调用。通常情况下，当进程调用管程中的程序时，该程序的前几条指令会检查管程中是否有其他活跃的进程。如果有的话，调用进程将被挂起，直到另一个进程离开管程才将其唤醒。如果没有活跃进程在使用管程，那么该调用进程才可以进入。



进入管程中的互斥由编译器负责，但是一种通用做法是使用 互斥量(mutex) 和 二进制信号量(binary semaphore)。由于编译器而不是程序员在操作，因此出错的几率会大大降低。在任何时候，编写管程的程序员都无需关心编译器是如何处理的。他只需要知道将所有的临界区转换成为管程过程即可。绝不会有两个进程同时执行临界区中的代码。



即使管程提供了一种简单的方式来实现互斥，但在我们看来，这还不够。因为我们还需要一种在进程无法执行被阻塞。在生产者-消费者问题中，很容易将针对缓冲区满和缓冲区空的测试放在管程程序中，但是生产者在发现缓冲区满的时候该如何阻塞呢？



解决的办法是引入条件变量(condition variables) 以及相关的两个操作 wait 和 signal。当一个管程程序发现它不能运行时（例如，生产者发现缓冲区已满），它会在某个条件变量（如 full）上执行 wait 操作。这个操作造成调用进程阻塞，并且还将另一个以前等在管程之外的进程调入管程。在前面的 pthread 中我们已经探讨过条件变量的实现细节了。另一个进程，比如消费者可以通过执行 signal 来唤醒阻塞的调用进程。



>Brinch Hansen 和 Hoare 在对进程唤醒上有所不同，Hoare 建议让新唤醒的进程继续运行；而挂起另外的进程。而 Brinch Hansen 建议让执行 signal 的进程必须退出管程，这里我们采用 Brinch Hansen 的建议，因为它在概念上更简单，并且更容易实现。



如果在一个条件变量上有若干进程都在等待，则在对该条件执行 signal 操作后，系统调度程序只能选择其中一个进程恢复运行。



顺便提一下，这里还有上面两位教授没有提出的第三种方式，它的理论是让执行 signal 的进程继续运行，等待这个进程退出管程时，其他进程才能进入管程。



条件变量不是计数器。条件变量也不能像信号量那样积累信号以便以后使用。所以，如果向一个条件变量发送信号，但是该条件变量上没有等待进程，那么信号将会丢失。也就是说，wait 操作必须在 signal 之前执行。



下面是一个使用 Pascal 语言通过管程实现的生产者-消费者问题的解法