进程的描述与控制

  在传统的操作系统中，为了提高资源利用率和系统吞吐量，通常采用多道程序技术，将多个程序同时装入内存，并使之并发运行，传统意义上的程序不再能独立运行。此时，作为资源分配和独立运行的基本单位都是进程。操作系统所具有的四大特征也都是基于进程而形成的，并从进程的角度对操作系统进行研究.可见，在操作系统中，进程是一个极其重要的概念。因此，本篇专门对进程进行详细阐述。

前趋图和程序执行

  在早期未配置OS的系统和单道批处理系统中，程序的执行方式是顺序执行，即在内存中仅装入一道用户程序：由它独占系统中的所有资源，只有在一个用户程序执行完成后，才允许装入另一个程序并执行。可见，这种方式浪费资源、系统运行效率低等缺点。而在多道程序系统中，由于内存中可以同时装入多个程序，使它们共享系统资源，并发执行，显然可以克服上述缺点。程序的这两种执行方式间有着显著的不同，尤其是考虑到程序并发执行时的特征，才导致了在操作系统中引入进程的概念。因此，这里有必要先对程序的顺序和并发执行方式做简单的描述。

前趋图

  为了能更好地描述程序的顺序和并发执行情况，我们先介绍用于描述程序执行先后顺序的前趋图。所谓前趋图(Precedence Graph)，是指一个有向无循环图，可记为DAG(Directed Acyclic Graph)，它用于描述进程之间执行的先后顺序。图中的每个结点可用来表示一个进程或程序段，乃至一条语句，结点间的有向边则表示两个结点之间存在的偏序(Partial Order)‌或前趋关系(Precedence Relation)。
  进程（或程序）之间的前趋关系可用“\(\to\)”来表示，如果进程和号存在着前趋关系，可表示为 \((P_i,P_j)\in\to\) ，也可写成 \(P_i\to P_j\) 表示在 \(P_j\) 开始执行之前 \(P_i\) 必须完成。此时称 \(P_i\) 是 \(P_j\) 的直接前趋，而称 \(P_j\) 是 \(P_i\) 的直接后继。在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)。此外，每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或程序的执行时间。在图1(a)所示的前趋图中，存在着如下前趋关系：
  \(P_1\to P_2,P_1\to P_3,P_1\to P_4,P_2\to P_5,P_3\to P_5,P_4\to P_6,P_4\to P_7,P_5\to P_8,P_6\to P_8,P_7\to P_9,P_8\to P_9\)
  或表示为：
  \(P=\set{P_1,P_2,P_3,P_4,P_5,P_6,P_7,P_8,P_9}\)
   \(=\set{(P_1,P_2),(P_1,P_3),(P_1,P_4),(P_2,P_5),(P_3,P_5),(P_4,P_6),(P_4,P_7),(P_5,P_8),(P_6,P_8),(P_7,P_9),(P_8,P_9)}\)
  应当注意，前趋图中是不允许有循环的，否则必然会产生不可能实现的前趋关系。如图1(b)所示的前趋关系中就存在着循环。它一方面要求在 \(S_3\) 开始执行之前， \(S_2\) 必须完成，另一方面又要求在 \(S_2\) 开始执行之前， \(S_1\) 必须完成。显然，这种关系是不可能实现的。
  \(S_2\to S_3,S_3\to S_2\)

图1 前趋图

程序顺序执行

程序的顺序执行

  通常，一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，它们在执行时，都需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。例如，在进行计算时，应先运行输入程序，用于输入用户的程序和数据；然后运行计算程序，对所输入的数据进行计算；最后才是运行打印程序，打印计算结果。我们用结点(Node)‌代表各程序段的操作（在图1中用圆圈表示），其中 \(I\) 代表输入操作， \(C\) 代表计算操作， \(P\) 为打印操作，用箭头指示操作的先后次序。这样，上述的三个程序段间就存在着这样的前趋关系： \(I_i\to C_i \to P_i\) ，其执行的顺序可用前趋图图2(a)描述。

图2 程序顺序执行的前趋图

  即使是一个程序段，也可能存在着执行顺序问题，下面示出了一个包含了三条语句的程序段：
  \(S_1\): a :=x+y;
  \(S_2\): b :=a+5;
  \(S_3\): c :=b+1;
  其中，语句 \(S_2\) 必须在语句 \(S_1\) 后即（a被赋值）才能执行，语句 \(S_3\) 也只能在b被赋值后才能执行，因此，三条语句存在着这样的前趋关系： \(S_1\to S_2 \to S_3\) ，应按前趋图图2(b)所示的顺序执行。

程序顺序执行时的特征

  由上所述可以得知，在程序顺序执行时，具有这样三个特征：①顺序性：指处理机严格地按照程序所规定的顺序执行，即每一操作必须在下一个操作开始之前结束；② 封闭性：指程序在封闭的环境下运行，即程序运行时独占全机资源，资源的状态（除初始状态外）只有本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响；③可再现性：指只要程序执行时的环境和初始条件相同，当程序重复执行时，不论它是从头到尾不停顿地执行，还是“停停走走”地执行，都可获得相同的结果。程序顺序执行时的这种特性，为程序员检测和校正程序的错误带来了很大的方便。

程序并发执行

  程序顺序执行时，虽然可以给程序员带来方便，但系统资源的利用率却很低。为此，在系统中引入了多道程序技术，使程序或程序段间能并发执行。然而，并非所有的程序都能并发执行。事实上，只有在不存在前趋关系的程序之间才有可能并发执行，否则无法并发执行。

程序的并发执行

  我们通过一个常见的例子来说明程序的顺序执行和并发执行。图2中的输入程序、计算程序和打印程序三者之间，存在着 \(I_i\to C_i\to P_i\) 这样的前趋关系，以至对一个作业的输入、计算和打印三个程序段必须顺序执行。但若是对一批作业进行处理时，每道作业的输入、计算和打印程序段的执行情况如图3所示。输入程序 \(I_1\) 在输入第一次数据后，由计算程序 \(C_1\) 对该数据进行计算的同时，输入程序 \(I_2\) 可再输入第二次数据，从而使第一个计算程序 \(C_1\) 可与第二个输入程序 \(I_2\) 并发执行。事实上，正是由于 \(C_1\) 和 \(I_2\) 之间并不存在前趋关系，因此它们之间可以并发执行。一般来说，输入程序 \(I_{i+1}\) 在输入第 \(i+1\) 次数据时，计算程序 \(C_i\) 可能正在对程序 \(I_i\) 的第 \(i\) 次输入的数据进行计算，而打印程序 \(P_{i-1}\) 正在打印程序 \(C{i-1}\) 的计算结果。
  由图3可以看出，存在前趋关系 \(I_i \to C_i,I_i \to I_{i+1},C_i \to P_i, C_i \to C_{i+1},P_i\to P_{i+1}\) 而 \(I_{i+1}\) 和 \(C_i\) 及 \(P_{i-1}\) 是重叠的，即在 \(P_{i-1}\) 和 \(C_i\) 以及 \(I_{i+1}\) 之间，不存在前趋关系，可以并发执行。

图3 程序并发执行时的前趋图

  对于具有下述四条语句的程序段：
  \(S_1\) : a :=x+2
  \(S_2\) : b :=y+4
  \(S_3\) : c :=a+b
  \(S_4\) : d :=c+b
  可画出图4所示的前趋关系。可以看出： \(S_3\) 必须在a和b被赋值后方能执行； \(S_4\) 必须在 \(S_3\) 之后执行；但 \(S_1\) 和 \(S_2\) 则可以并发执行，因为它们彼此互不依赖。

图4 四条语句的前趋关系

程序并发执行时的特征

  在引入了程序间的并发执行功能后，虽然提高了系统的吞吐量和资源利用率，但由于它们共享系统资源，以及它们为完成同一项任务而相互合作，致使在这些并发执行的程序之间必将形成相互制约的关系，由此会给程序并发执行带来新的特征。
  (1) 间断性。程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。例如，图3中的 \(I\) 、 \(C\) 和 \(P\) 是三个相互合作的程序，当计算程序完成 \(C_{i-1}\) 的计算后，如果输入程序 \(I_i\) 尚未完成数据的输入，则计算程序 \(C_i\) 就无法进行数据处理，必须暂停运行。只有当使程序暂停的因素消失后（如 \(I_i\) 己完成数据输入），计算程序 \(C_i\) 便可恢复执行。由此可见，相互制约将导致并发程序具有"执行一暂停——执行”这种间断性的活动规律。
  (2) 失去封闭性。当系统中存在着多个可以并发执行的程序时，系统中的各种资源将为它们所共享，而这些资源的状态也由这些程序来改变，致使其中任一程序在运行时，其环境都必然会受到其它程序的影响。例如，当处理机已被分配给某个进程运行时，其它程序必须等待。显然，程序的运行已失去了封闭性。
  (3) 不可再现性。程序在并发执行时，由于失去了封闭性，也将导致其又失去可再现性。例如，有两个循环程序 \(A\) 和 \(B\) ，它们共享一个变量 \(N\) 。程序 \(A\) 每执行一次时，都要做 \(N=N+1\) 操作；程序 \(B\) 每执行一次时，都要执行 \(\text{Print}(N)\) 操作，然后再将 \(N\) 置成“\(0\)”。程序 \(A\) 和 \(B\) 以不同的速度运行。这样，可能出现下述三种情况（假定某时刻变量 \(N\) 的值为 \(n\) ）：
  ① \(N=N+1\) 在 \(\text{Print}(N)\) 和 \(N=0\) 之前，此时得到的N值分别为 \(n+1,n+1,0\) 。
  ② \(N=N+1\) 在 \(\text{Print}(N)\) 和 \(N=0\) 之后，此时得到的 \(N\) 值分别为 \(n,0,1\) 。
  ③ \(N=N+1\) 在 \(\text{Print}(N)\) 和 \(N=0\) 之间，此时得到的 \(N\) 值分别为 \(n,n+1,0\) 。
  上述情况说明，程序在并发执行时，由于失去了封闭性，其计算结果必将与并发程序的执行速度有关，从而使程序的执行失去了可再现性。换而言之，程序经过多次执行后，虽然它们执行时的环境和初始条件相同，但得到的结果却各不相同。

进程的描述

进程的定义和特征

进程的定义

  在多道程序环境下，程序的执行属于并发执行，此时它们将失去其封闭性，并具有间断性，以及其运行结果不可再现性的特征。由此，决定了通常的程序是不能参与并发执行的，否则，程序的运行也就失去了意义。为了能使程序并发执行，并且可以对并发执行的程序加以描述和控制，人们引入了“进程”的概念。
  为了使参与并发执行的每个程序（含数据）都能独立地运行，在操作系统中必须为之配置一个专门的数据结构，称为进程控制块(Process Control Block,PCB)。系统利用PCB来描述进程的基本情况和活动过程，进而控制和管理进程。这样，由程序段、相关的数据段和PCB三部分便构成了进程实体（又称进程映像）。一般情况下，我们把进程实体就简称为进程，例如，所谓创建进程，实质上是创建进程实体中的PCB；而撤消进程，实质上是撤消进程的PCB，本教材中也是如此。

  对于进程的定义，从不同的角度可以有不同的定义，其中较典型的定义有：
  (1) 进程是程序的一次执行。
  (2) 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
  (3) 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

  在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。”

进程的特征

  进程和程序是两个截然不同的概念，除了进程具有程序所没有的PCB结构外，还具有下面一些特征：
  (1) 动态性。进程的实质是进程实体的执行过程，因此，动态性就是进程的最基本的特征。动态性还表现在：“它由创建而产生，由调度而执行，由撤消而消亡。”可见，进程实体有一定的生命期，而程序则只是一组有序指令的集合，并存放于某种介质上，其本身并不具有活动的含义，因而是静态的。
  (2) 并发性。是指多个进程实体同存于内存中，且能在一段时间内同时运行。引入进程的目的也正是为了使其进程实体能和其它进程实体并发执行。因此，并发性是进程的另一重要特征，同时也成为OS的重要特征。而程序(没有建立PCB)是不能参与并发执行的。
  (3) 独立性。在传统的OS中，独立性是指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。
  (4) 异步性，是指进程是按异步方式运行的，即按各自独立的、不可预知的速度向前推进。正是源于此因，才导致了传统意义上的程序若参与并发执行，会产生其结果的不可再现性。为使进程在并发运行时虽具有异步性，但仍能保证进程并发执行的结果是可再现的，在OS中引进了进程的概念，并且配置相应的进程同步机制。

进程的基本状态及转换

进程的三种基本状态

  由于多个进程在并发执行时共享系统资源，致使它们在运行过程中呈现间断性的运行规律，所以进程在其生命周期内可能具有多种状态。一般而言，每一个进程至少应处于以下三种基本状态之一：
  (1) 就绪(Ready)状态。这是指进程已处于准备好运行的状态，即进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。如果系统中有许多处于就绪状态的进程，通常将它们按一定的策略（如优先级策略）排成一个队列，称该队列为就绪队列。
  (2) 执行(Running)状态。这是指进程已获得CPU，其程序正在执行的状态。对任何一个时刻而言，在单处理机系统中，只有一个进程处于执行状态，而在多处理机系统中，则有多个进程处于执行状态。
  (3) 阻塞(Block)状态。这是指正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等）暂时无法继续执行时的状态，亦即进程的执行受到阻塞。此时引起进程调度，OS把处理机分配给另一个就绪进程，而让受阻进程处于暂停状态，一般将这种暂停状态称为阻塞状态，有时也称为等待状态或封锁状态。通常系统将处于阻塞状态的进程也排成一个队列，称该队列为阻塞队列。实际上，在较大的系统中，为了减少队列操作的开销，提高系统效率，根据阻塞原因的不同，会设置多个阻塞队列。

三种基本状态的转换

  进程在运行过程中会经常发生状态的转换。例如，处于就绪状态的进程，在调度程序为之分配了处理机之后便可执行，相应地，其状态就由就绪态转变为执行态；正在执行的进程（当前进程）如果因分配给它的时间片己完而被剥夺处理机暂停执行时，其状态便由执行转为就绪：如果因发生某事件，致使当前进程的执行受阻（例如进程访问某临界资源，而该资源正被其它进程访问时），使之无法继续执行，则该进程状态将由执行转变为阻塞。图5示出了进程的三种基本状态，以及各状态之间的转换关系。

图5 进程的三种基本状态及其转换

创建状态和终止状态

  为了满足进程控制块对数据及操作的完整性要求以及增强管理的灵活性，通常在系统中又为进程引入了两种常见的状态：创建状态和终止状态。

1. 创建状态

  如前所述，进程是由创建而产生。创建一个进程是个很复杂的过程，一般要通过多个步骤才能完成：如首先由进程申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息； 然后为该进程分配运行时所必须的资源；最后，把该进程转入就绪状态并插入就绪队列之中。
  但如果进程所需的资源尚不能得到满足，比如系统尚无足够的内存使进程无法装入其中，此时创建工作尚未完成，进程不能被调度运行，于是把此时进程所处的状态称为创建状态。引入创建状态是为了保证进程的调度必须在创建工作完成后进行，以确保对进程控制块操作的完整性。同时，创建状态的引入也增加了管理的灵活性，OS可以根据系统性能或主存容量的限制推迟新进程的提交（创建状态）。对于处于创建状态的进程，当其获得了所需的资源以及对其PCB的初始化工作完成后，便可由创建状态转入就绪状态。

2. 终止状态

  进程的终止也要通过两个步骤：首先，是等待操作系统进行善后处理，最后将其PCB清零，并将PCB空间返还系统。当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。进入终止态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其他进程收集。一旦其他进程完成了对其信息的提取之后，操作系统将删除该进程，即将其PCB清零，并将该空白PCB返还系统。图6示出了增加了创建状态和终止状态后进程的五种状态及转换关系图。

图6 进程的五种基本状态及转换

挂起操作和进程状态的转换

  在许多系统中，进程除了就绪、执行和阻塞三种最基本的状态外，为了系统和用户观察和分析进程的需要，还引入了一个对进程的重要操作——挂起操作。当该操作作用于某个进程时，该进程将被挂起，意味着此时该进程处于静止状态。如果进程正在执行，它将暂停执行。若原本处于就绪状态，则该进程此时暂不接受调度。与挂起操作对应的操作是激活操作。

挂起操作的引入

  引入挂起操作的原因，是基于系统和用户的如下需要：
  (1) 终端用户的需要。当终端用户在自己的程序运行期间发现有可疑问题，希望暂停自己的程序的运行，使之停止下来，以便用户研究其执行情况或对程序进行修改。
  (2) 父进程请求。有时父进程希望挂起自己的某个子进程，以便考查和修改该子进程，或者协调各子进程间的活动。
  (3) 负荷调节的需要。当实时系统中的工作负荷较重，已可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常运行。
  (4) 操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。

引入挂起原语操作后三个进程状态的转换

  在引入挂起原语Suspend和激活原语Active后，在它们的作用下，进程将可能发生以下几种状态的转换：
  (1) 活动就绪🠖静止就绪。当进程处于未被挂起的就绪状态时，称此为活动就绪状态，表示为Readya，此时进程可以接受调度。当用挂起原语Suspend将该进程挂起后，该进程便转变为静止就绪状态，表示为Readys，处于Readys状态的进程不再被调度执行。
  (2) 活动阻塞🠖静止阻塞。当进程处于未被挂起的阻塞状态时，称它是处于活动阻塞状态，表示为Blockeda。当用Suspend原语将它挂起后，进程便转变为静止阻塞状态，表示为Blockeds，处于该状态的进程在其所期待的事件出现后，它将从静止阻塞变为静止就绪Readys状态。
  (3) 静止就绪🠖活动就绪。处于Readys状态的进程若用激活原语Active激活后，该进程将转变为Readya状态。
  (4) 静止阻塞🠖活动阻塞。处于Blockeds状态的进程若用激活原语Active激活后，进程将转变为Blockeda状态。图7示出了具有挂起状态的进程状态图。

图7 具有挂起状态的进程状态图

引入挂起操作后五个进程状态的转换

  如图8示出了增加了创建状态和终止状态后具有挂起状态的进程状态及转换图。
  如图8所示，引进创建和终止状态后，在进程状态转换时，与图7所示的进程五状态转换相比较，要增加考虑下面的几种情况：
  (1) NULL🠖创建：一个新进程产生时，该进程处于创建状态。
  (2) 创建🠖活动就绪：在当前系统的性能和内存的容量均允许的情况下，完成对进程创建的必要操作后，相应的系统进程将进程的状态转换为活动就绪状态。
  (3) 创建🠖静止就绪：考虑到系统当前资源状况和性能的要求，不分配给新建进程所需资源，主要是主存，相应的系统将进程状态转为静止就绪状态，被安置在外存，不参与，调度，此时进程创建工作尚未完成。
  (4) 执行🠖终止：当一个进程已完成任务时，或是出现了无法克服的错误，或是被OS，或是被其他进程所终结，此时将进程的状态转换为终止状态。

图8 具有创建、终止和挂起状态的进程状态图

进程管理中的数据结构

  如操作系统概论-操作系统的目标和作用所述，一方面，为了便于对计算机中的各类资源（包括硬件和信息）的使用和管理，OS将它们抽象为相应的各种数据结构，以及提供一组对资源进行操作的命令，用户可利用这些数据结构及操作命令来执行相关的操作，而无需关心其实现的具体细节。另一方面，操作系统作为计算机资源的管理者，尤其是为了协调诸多用户对系统中共享资源的使用，它还必须记录和查询各种资源的使用及各类进程运行情况的信息。OS对于这些信息的组织和维护也是通过建立和维护各种数据结构的方式来实现的。

操作系统中用于管理控制的数据结构

  在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，我们称之为资源信息表或进程信息表，其中包含了资源或进程的标识、描述、状态等信息以及一批指针。通过这些指针，可以将同类资源或进程的信息表，或者同一进程所占用的资源信息表分类链接成不同的队列，便于操作系统进行查找。如图9所示，OS管理的这些数据结构一般分为以下四类：内存表、设备表、文件表和用于进程管理的进程表，通常进程表又被称为进程控制块PCB。本节着重介绍PCB，其它的表将在后面的篇章中陆续介绍。

图9 操作系统控制表一般结构

进程控制块PCB的作用

  为了便于系统描述和管理进程的运行，在OS的核心为每个进程专门定义了一个数据结构——进程控制块PCB(Process Control Block)。PCB作为进程实体的一部分，记录了操作系统所需的，用于描述进程的当前情况以及管理进程运行的全部信息，是操作系统中最重要的记录型数据结构。
  PCB的作用是使一个在多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。下面对PCB的具体作用作进一步的阐述：
  (1) 作为独立运行基本单位的标志。当一个程序（含数据）配置了PCB后，就表示它已是一个能在多道程序环境下独立运行的、合法的基本单位，也就具有取得OS服务的权利，如打开文件系统中的文件，请求获得系统中的I/O设备，以及与其它相关进程进行通信等。因此，当系统创建一个新进程时，就为它建立了一个PCB。进程结束时又回收其PCB，进程于是也随之消亡。系统是通过PCB感知进程的存在的。事实上，PCB已成为进程存在于系统中的唯一标志。
  (2) 能实现间断性运行方式。在多道程序环境下，程序是采用停停走走间断性的运行方式运行的。当进程因阻塞而暂停运行时，它必须保留自己运行时的CPU现场信息，再次被调度运行时，还需要恢复其CPU现场信息。在有了PCB后，系统就可将CPU现场信息保存在被中断进程的PCB中，供该进程再次被调度执行时恢复CPU现场时使用。由此， 可再次明确，在多道程序环境下，作为传统意义上的静态程序，因其并不具有保护或保存自己运行现场的手段，无法保证其运行结果的可再现性，从而失去运行的意义。
  (3) 提供进程管理所需要的信息。当调度程序调度到某进程运行时，只能根据该进程PCB中记录的程序和数据在内存或外存中的始址指针，找到相应的程序和数据；在进程运行过程中，当需要访问文件系统中的文件或I/O设备时，也都需要借助于PCB中的信息。另外，还可根据PCB中的资源清单了解到该进程所需的全部资源等。可见，在进程的整个生命期中，操作系统总是根据PCB实施对进程的控制和管理。
  (4) 提供进程调度所需要的信息。只有处于就绪状态的进程才能被调度执行，而在PCB中就提供了进程处于何种状态的信息。如果进程处于就绪状态，系统便将它插入到进程就绪队列中，等待着调度程序的调度；另外在进行调度时往往还需要了解进程的其他信息，如在优先级调度算法中，就需要知道进程的优先级。在有些较为公平的调度算法中，还需要知道进程的等待时间和已执行的时间等。
  (5) 实现与其它进程的同步与通信。进程同步机制是用于实现诸进程的协调运行的，在采用信号量机制时，它要求在每个进程中都设置有相应的用于同步的信号量。在PCB中还具有用于实现进程通信的区域或通信队列指针等。

进程控制块中的信息

  在进程控制块中，主要包括下述四个方面的信息。

1. 进程标识符

  进程标识符用于唯一地标识一个进程。一个进程通常有两种标识符：
  (1) 外部标识符。为了方便用户（进程）对进程的访问，须为每一个进程设置一个外部标识符。它是由创建者提供的，通常由字母、数字组成。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。
  (2) 内部标识符。为了方便系统对进程的使用，在OS中又为进程设置了内部标识符，即赋予每一个进程一个唯一的数字标识符，它通常是一个进程的序号。

2. 处理机状态

  处理机状态信息也称为处理机的上下文，主要是由处理机的各种寄存器中的内容组成的。这些寄存器包括：
  ①通用寄存器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有8〜32个通用寄存器，在RISC结构的计算机中可超过100个；②指令计数器，其中存放了要访问的下一条指令的地址；③程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；④用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。处理机处于执行状态时，正在处理的许多信息都是放在寄存器中。当进程被切换时，处理机状态信息都必须保存在相应的PCB中，以便在该进程重新执行时能再从断点继续执行。

3. 进程调度信息

  在OS进行调度时，必须了解进程的状态及有关进程调度的信息，这些信息包括：①进程状态，指明进程的当前状态，它是作为进程调度和对换时的依据；②进程优先级，是用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；③进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；④事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。

4. 进程控制信息

  是指用于进程控制所必须的信息，它包括：①程序和数据的地址，进程实体中的程序和数据的内存或外存地（首）址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；②进程同步和通信机制，这是实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中：③资源清单，在该清单中列出了进程在运行期间所需的全部资源（除CPU以外），另外还有一张已分配到该进程的资源的清单；④链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。

进程控制块的组织方式

  在一个系统中，通常可拥有数十个、数百个乃至数千个PCB。为了能对它们加以有效的管理，应该用适当的方式将这些PCB组织起来。目前常用的组织方式有以下三种。
  (1) 线性方式，即将系统中所有的PCB都组织在一张线性表中，将该表的首址存放在内存的一个专用区域中。该方式实现简单、开销小，但每次查找时都需要扫描整张表，因此适合进程数目不多的系统。图10示出了线性表的PCB组织方式。

图10 PCB线性表示意图

  (2) 链接方式，即把具有相同状态进程的PCB分别通过PCB中的链接字链接成一个队列。这样，可以形成就绪队列、若干个阻塞队列和空白队列等。对就绪队列而言，往往按进程的优先级将PCB从高到低进行排列，将优先级高的进程PCB排在队列的前面。同样，也可把处于阻塞状态进程的PCB根据其阻塞原因的不同，排成多个阻塞队列，如等待I/O操作完成的队列和等待分配内存的队列等。图11示出了一种链接队列的组织方式。

图11 PCB连接队列示意图

  (3) 索引方式，即系统根据所有进程状态的不同，建立几张索引表，例如，就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB表中的地址。图12示出了索引方式的PCB组织。

图12 按索引方式组织PCB

进程控制

  进程控制是进程管理中最基本的功能，主要包括创建新进程、终止已完成的进程、将因发生异常情况而无法继续运行的进程置于阻塞状态、负责进程运行中的状态转换等功能。如当一个正在执行的进程因等待某事件而暂时不能继续执行时，将其转变为阻塞状态，而在该进程所期待的事件出现后，又将该进程转换为就绪状态等。进程控制一般是由OS的内核中的原语来实现的。

操作系统内核

  现代操作系统一般将OS划分为若干层次，再将OS的不同功能分别设置在不同的层次中。通常将一些与硬件紧密相关的模块（如中断处理程序等）、各种常用设备的驱动程序以及运行频率较高的模块（如时钟管理、进程调度和许多模块所公用的一些基本操作），都安排在紧靠硬件的软件层次中，将它们常驻内存，即通常被称为的OS内核。这种安排方式的目的在于两方面：一是便于对这些软件进行保护，防止遭受其他应用程序的破坏；二是可以提高OS的运行效率。
  相对应的是，为了防止OS本身及关键数据（如PCB等）遭受到应用程序有意或无意的破坏，通常也将处理机的执行状态分成系统态和用户态两种：①系统态：又称为管态，也称为内核态。它具有较高的特权，能执行一切指令，访问所有寄存器和存储区，传统的OS都在系统态运行。②用户态：又称为目态。它是具有较低特权的执行状态，仅能执行规定的指令，访问指定的寄存器和存储区。一般情况下，应用程序只能在用户态运行，不能去执行OS指令及访问OS区域，这样可以防止应用程序对OS的破坏。
  总体而言，不同类型和规模的OS，它们的内核所包含的功能间存在着一定的差异，但大多数OS内核都包含了以下两大方面的功能：

支撑功能

  该功能是提供给OS其它众多模块所需要的一些基本功能，以便支撑这些模块工作。其中三种最基本的支撑功能是：中断处理、时钟管理和原语操作。
  (1) 中断处理。中断处理是内核最基本的功能，是整个操作系统赖以活动的基础，OS中许多重要的活动，如各种类型的系统调用、键盘命令的输入、进程调度、设备驱动等，无不依赖于中断。通常，为减少处理机中断的时间，提高程序执行的并发性，内核在对中断进行“有限处理”后，便转入相关的进程，由这些进程继续完成后续的处理工作。
  (2) 时钟管理。时钟管理是内核的一项基本功能，在OS中的许多活动都需要得到它的支撑，如在时间片轮转调度中，每当时间片用完时，便由时钟管理产生一个中断信号，促使调度程序重新进行调度。同样，在实时系统中的截止时间控制、批处理系统中的最长运行时间控制等，也无不依赖于时钟管理功能。
  (3) 原语操作。所谓原语(Primitive)，就是由若干条指令组成的，用于完成一定功能的一个过程。它与一般过程的区别在于：它们是“原子操作(Action Operation)”。所谓原子操作是指，一个操作中的所有动作要么全做，要么全不做。换言之，它是一个不可分割的基本单位。因此，原语在执行过程中不允许被中断。原子操作在系统态下执行，常驻内存。在内核中可能有许多原语，如用于对链表进行操作的原语、用于实现进程同步的原语等。

资源管理功能

  (1) 进程管理。在进程管理中，或者由于各个功能模块的运行频率较高，如进程的调度与分派、进程的创建与撤消等；或者由于它们为多种功能模块所需要，如用于实现进程同步的原语、常用的进程通信原语等。通常都将它们放在内核中，以提高OS的性能。
  (2) 存储器管理。存储器管理软件的运行频率也比较高，如用于实现将用户空间的逻辑地址变换为内存空间的物理地址的地址转换机构、内存分配与回收的功能模块以及实现内存保护和对换功能的模块等。通常也将它们放在内核中，以保证存储器管理具有较高的运行速度。
  (3) 设备管理。由于设备管理与硬件（设备）紧密相关，因此其中很大部分也都设置在内核中。如各类设备的驱动程序、用于缓和CPU与I/O速度不匹配矛盾的缓冲管理、用于实现设备分配和设备独立性功能的模块等。

进程的创建

进程的层次结构

  在OS中，允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程称为子进程。子进程可继续创建更多的孙进程，由此便形成了一个进程的层次结构。如在UNIX中，进程与其子孙进程共同组成一个进程家族（组）。
  了解进程间的这种关系是十分重要的。因为子进程可以继承父进程所拥有的资源，例如，继承父进程打开的文件，继承父进程所分配到的缓冲区等。当子进程被撤消时，应将其从父进程那里获得的资源归还给父进程。此外，在撤消父进程时，也必须同时撤消其所有的子进程。为了标识进程之间的家族关系，在PCB中设置了家族关系表项，以标明自己的父进程及所有的子进程。进程不能拒绝其子进程的继承权。
  值得注意的是，在Windows中不存在任何进程层次结构的概念，所有的进程都具有相同的地位。如果一个进程创建另外的进程时创建进程获得了一个句柄，其作用相当于一个令牌，可以用来控制被创建的进程。但是，这个句柄是可以进行传递的，也就是说，获得了句柄的进程就拥有控制其它进程的权力，因此，进程之间的关系不再是层次关系了，而是获得句柄与否、控制与被控制的简单关系。

进程图

  为了形象地描述一个进程的家族关系而引入了进程图(Process Graph)。所谓进程图就是用于描述进程间关系的一棵有向树，如图13所示。图中的结点代表进程。在进程 \(P_i\) 创建了进程 \(P_j\) 之后，称 \(P_i\) 是 \(P_j\) 的父进程(Parent Process)， \(P_j\) 是 \(P_i\) 的子进程(Progeny Process)。这里可用一条由进程 \(P_i\) 指向进程 \(P_j\) 的有向边来描述它们之间的父子关系。创建父进程的进程称为祖先进程，这样便形成了一棵进程树，把树的根结点作为进程家族的祖先(Ancestor)。

图13 进程树

引起创建进程的事件

  为使程序之间能并发运行，应先为它们分别创建进程。导致一个进程去创建另一个进 程的典型事件有四类：
  (1) 用户登录。在分时系统中，用户在终端键入登录命令后，若登录成功，系统将为该用户建立一个进程，并把它插入就绪队列中。
  (2) 作业调度。在多道批处理系统中，当作业调度程序按一定的算法调度到某个（些）作业时，便将它（们）装入内存，为它（们）创建进程，并把它（们）插入就绪队列中。
  (3)提供服务。当运行中的用户程序提出某种请求后，系统将专门创建一个进程来提供用户所需要的服务，例如，用户程序要求进行文件打印，操作系统将为它创建一个打印进程，这样不仅可使打印进程与该用户进程并发执行，而且还便于计算为完成打印任务所花费的时间。
  (4)应用请求。在上述三种情况下，都是由系统内核为用户创建一个新进程；而这类事件则是由用户进程自己创建新进程，以便使新进程以同创建者进程并发运行的方式完成特定任务。例如，某用户程序需要不断地先从键盘终端读入数据，继而再对输入数据进行相应的处理，然后，再将处理结果以表格形式在屏幕上显示。该应用进程为使这几个操作能并发执行，以加速任务的完成，可以分别建立键盘输入进程、表格输出进程。

进程的创建(Create of Process)

  在系统中每当出现了创建新进程的请求后，OS便调用进程创建原语Create按下述步骤创建一个新进程：
  (1) 申请空白PCB，为新进程申请获得唯一的数字标识符，并从PCB集合中索取一个空白PCB。
  (2) 为新进程分配其运行所需的资源，包括各种物理和逻辑资源，如内存、文件、I/O设备和CPU时间等。这些资源或从操作系统或仅从其父进程获得。新进程对这些资源的需求详情一般也要提前告知操作系统或其父进程。例如，为新进程的程序和数据以及用户栈分配必要的内存空间时，操作系统必须知道新进程所需内存的大小：①对于批处理作业，其大小可在用户提出创建进程要求时提供；②若是为应用进程创建子进程，也应是在该进程提出创建进程的请求中给出所需内存的大小；③对于交互型作业，用户可以不给出内存要求而由系统分配一定的空间；如果新进程要共享某个己在内存的地址空间（即已装入内存的共享段），则必须建立相应的链接。
  (3) 初始化进程控制块(PCB)。PCB的初始化包括：①初始化标识信息，将系统分配的标识符和父进程标识符填入新PCB中；②初始化处理机状态信息，使程序计数器指向程序的入口地址，使栈指针指向栈顶；③初始化处理机控制信息，将进程的状态设置为就绪状态或静止就绪状态，对于优先级，通常是将它设置为最低优先级，除非用户以显式方式提出高优先级要求。
  (4) 如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。

进程的终止

引起进程终止(Termination of Process)的事件

  (1) 正常结束，表示进程的任务已经完成，准备退出运行。在任何系统中，都应有一个用于表示进程已经运行完成的指示。在批处理系统中，通常会在程序的最后安排一条Holt指令，用于向OS表示运行已结束。当程序运行到Holt指令时，将产生一个中断，去通知OS本进程已经完成；在分时系统中，用户可利用Logs off去表示进程运行完毕，此时同样可产生一个中断，去通知OS进程已运行完毕。
  (2) 异常结束，是指进程在运行时发生了某种异常事件，使程序无法继续运行。常见的异常事件有：①越界错，这是指程序所访问的存储区，已越出该进程的区域；②保护错，指进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；③非法指令，指程序试图去执行一条不存在的指令。出现该错误的原因可能是程序错误地转移到数据区，把数据当成了指令：④特权指令错，指用户进程试图去执行一条只允许OS执行的指令；⑤运行超时，指进程的执行时间超过了指定的最大值；⑥等待超时，指进程等待某事件的时间超过了规定的最大值；⑦算术运算错，指进程试图去执行一个被禁止的运算，例如，被0除；⑧I/O故障，这是指在I/O过程中发生了错误等。
  (3) 外界干预，是指进程应外界的请求而终止运行。这些干预有：①操作员或操作系统干预，指如果系统中发生了某事件，例如，发生了系统死锁，由操作员或操作系统采取终止某些进程的方式使系统从死锁状态中解救出来；②父进程请求，指当子进程已完成父进程所要求的任务时，父进程可以提出请求结束该子进程；③因父进程终止，指当父进程终止时，它的所有子进程也都应当结束，因此，OS在终止父进程的同时，也将它的所有子孙进程终止。

进程终止的过程

  如果系统中发生了要求终止进程的某事件，OS便调用进程终止原语，按下述过程去终止指定的进程：
  (1) 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。
  (2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。
  (3) 若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，以防它们成为不可控的进程。
  (4) 将被终止进程所拥有的全部资源或者归还给其父进程，或者归还给系统。
  (5) 将被终止进程(PCB)从所在队列（或链表）中移出，等待其它程序来搜集信息。

进程的阻塞与唤醒

引起进程阻塞和唤醒的事件

  有下述几类事件会引起进程阻塞或被唤醒：
  (1) 向系统请求共享资源失败。进程在向系统请求共享资源时，由于系统已无足够的资源分配给它，此时进程因不能继续运行而转变为阻塞状态。例如，一进程请求使用打印机，由于系统已将打印机分配给其它进程，已无可以再可分配的打印机，这时请求者进程只能被阻塞，仅在其它进程释放出打印机时，请求进程才被唤醒。
  (2) 等待某种操作的完成。当进程启动某种操作后，如果该进程必须在该操作完成之后才能继续执行，则应先将该进程阻塞起来，以等待操作完成。例如，进程启动了某I/O设备，如果只有在I/O设备完成了指定的I/O操作任务后进程才能继续执行，则该进程在启动了I/O设备后便应自动进入阻塞状态去等待。在I/O操作完成后，再由中断处理程序将该进程唤醒。
  (3) 新数据尚未到达。对于相互合作的进程，如果一个进程需要先获得另一进程提供的数据后才能对该数据进行处理，只要其所需数据尚未到达，进程便只有阻塞。例如，有两个进程，进程A用于输入数据，进程B对输入数据进行加工。假如A尚未将数据输入完毕，则进程B将因没有所需处理的数据而阻塞；一旦进程A把数据输入完毕，便可去唤醒进程B。
  (4) 等待新任务的到达。在某些系统中，特别是在网络环境下的OS，往往设置一些特定的系统进程，每当这种进程完成任务后便把自己阻塞起来，等待新任务的到来。例如，在网络环境中的发送进程，其主要任务是发送数据包，若已有的数据包已全部发送完成，而又无新的数据包发送，这时发送进程将把自己阻塞起来；仅当有新的数据包到达时，才将发送进程唤醒。

进程阻塞过程

  正在执行的进程，如果发生了上述某事件，进程便通过调用阻塞原语block将自己阻塞。可见，阻塞是进程自身的一种主动行为。进入block过程后，由于该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态，按新进程的PCB中的处理机状态设置CPU的环境。

进程唤醒过程

  当被阻塞进程所期待的事件发生时，比如它所启动的I/O操作已完成，或其所期待的OS，数据已经到达，则由有关进程（比如提供数据的进程）调用唤醒原语wakeup，将等待该事件OS，的进程唤醒。wakeup执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出OS，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。应当指出，block原语和wakeup原语是一对作用刚好相反的原语。在使用它们时，必须成对使用，即如果在某进程中调用了阻塞原语，则必须在与之相合作的、或其它相关的OS，进程中安排一条相应的唤醒原语，以便能唤醒被阻塞进程；否则，阻塞进程将会因不能被OS，唤醒而永久地处于阻塞状态，再无机会继续运行。

进程的挂起与激活

进程的挂起

  当系统中出现了引起进程挂起的事件时，OS将利用挂起原语suspend将指定进程或处于阻塞状态的进程挂起。suspend的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪：对于活动阻塞状态的进程，则将之改为静止阻塞；为了方便用户或父进程考查该进程的运行情况，而把该进程的PCB复制到某指定的内存区域；最后，若被挂起的进程正在执行，则转向调度程序重新调度。

进程的激活过程

  当系统中发生激活进程的事件时，OS将利用激活原语active，将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞，便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有静止就绪进程被激活而插入就绪队列时，便应检查是否要进行重新调度，即由调度程序将被激活的进程与当前进程两者的优先级进行比较，如果被激活进程的优先级低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚刚被激活的进程。

进程同步

  在OS中引入进程后，一方面可以使系统中的多道程序并发执行，这不仅能有效地改善资源利用率，还可显著地提高系统的吞吐量，但另一方面却使系统变得更加复杂。如果不能采取有效的措施，对多个进程的运行进行妥善的管理，必然会因为这些进程对系统资源的无序争夺给系统造成混乱。致使每次处理的结果存在着不确定性，即显现出其不可再现性。
  为保证多个进程能有条不紊地运行，在多道程序系统中，必须引入进程同步机制。在本文中，将详细介绍在单处理机系统中的进程同步机制——硬件同步机制、信号量机制、管程机制等，利用它们来保证程序执行的可再现性。

进程同步的基本概念

  进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。

两种形式的制约关系

  在多道程序环境下，对于同处于一个系统中的多个进程，由于它们共享系统中的资源，或为完成某一任务而相互合作，它们之间可能存在着以下两种形式的制约关系：

1. 间接相互制约关系

  多个程序在并发执行时，由于共享系统资源，如CPU、I/O设备等，致使在这些并发执行的程序之间形成相互制约的关系。对于像打印机、磁带机这样的临界资源，必须保证多个进程对之只能互斥地访问，由此，在这些进程间形成了源于对该类资源共享的所谓间接相互制约关系。为了保证这些进程能有序地运行，对于系统中的这类资源，必须由系统实施统一分配，即用户在要使用之前，应先提出申请，而不允许用户进程直接使用。

2. 直接相互制约关系

  某些应用程序，为了完成某任务而建立了两个或多个进程。这些进程将为完成同一项任务而相互合作。进程间的直接制约关系就是源于它们之间的相互合作。例如，有两个相互合作的进程——输入进程A和计算进程B，它们之间共享一个缓冲区。进程A通过缓冲向进程B提供数据。进程B从缓冲中取出数据，并对数据进行处理。但如果该缓冲空时，计算进程因不能获得所需数据而被阻塞。一旦进程A把数据输入缓冲区后便将进程B唤醒；反之，当缓冲区已满时，进程A因不能再向缓冲区投放数据而被阻塞，当进程B将缓冲区数据取走后便可唤醒A。

  在多道程序环境下，由于存在着上述两类相互制约关系，进程在运行过程中是否能获得处理机运行与以怎样的速度运行，并不能由进程自身所控制，此即进程的异步性。由此会产生对共享变量或数据结构等资源不正确的访问次序，从而造成进程每次执行结果的不一致。这种差错往往与时间有关，故称为“与时间有关的错误”。为了杜绝这种差错，必须对进程的执行次序进行协调，保证诸进程能按序执行。

临界资源(Critical Resource)

  在第一篇中我们曾经介绍过，许多硬件资源如打印机、磁带机等，都属于临界资源，诸进程间应采取互斥方式，实现对这种资源的共享。下面我们将通过一个简单的例子来说明这一过程。
  生产者—消费者（producer-consumer）问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将其所生产的产品放入一个缓冲区中:消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，既不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。
  我们可利用一个数组buffer来表示上述的具有n个缓冲区的缓冲池。每投入（或取出）一个产品时,缓冲池buffer中暂存产品（或已取走产品的空闲单元）的数组单元指针in（或out）加1。由于这里由buffer组成的缓冲池是被组织成循环缓冲的，故应把输入指针in（或输出指针out）加1，表示成in=(in+1)%n（或out=(out+1)%n）。当(in+1)%n=out时表示缓冲池满；而in=out则表示缓冲池空。此外，还引入了一个整型变量counter，其初始值为0。每当生产者进程向缓冲池中投放（或取走）一个产品后，使counter加1(或减1)。生产者和消费者两进程共享下面的变量：

1
2

int in=0, out=0, count=0;
item buffer[n];

  指针in和out初始化为0。在生产者进程中使用一局部变量nextp，用于暂时存放每次刚刚生产出来的产品；而在消费者进程中，则使用一个局部变量nextc，用于存放每次要消费的产品。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void producer() {
    item nextp;
    do {
        nextp = produce_item(); // 假设有函数produce_item()用于生成产品
        while (counter == n); // 忙等待
        buffer[in] = nextp;
        in = (in + 1) % n;
        counter++;
    } while (true);
}
void consumer() {
    item nextc;
    do {
        while (counter == 0); // 忙等待
        nextc = buffer[out];
        out = (out + 1) % n;
        counter--;
        consume_item(nextc); // 假设有函数consume_item()用于消费产品
    } while (true);
}
void main() {
    create(producer);
    create(consumer);
}

  虽然上面的生产者程序和消费者程序在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：

1
2
3
4

// 生产者进程
register1 = counter;
register1 = register1 + 1;
counter = register1;

1
2
3
4

// 消费者进程
register2 = counter;
register2 = register2 - 1;
counter = register2;

  假设counter当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语句，则最后共享变量counter的值仍为5。反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter值也还是5，但是，如果按下述顺序执行：

1
2
3
4
5
6

register1 = counter;         // (register1 = 5)
register1 = register1 + 1;   // (register1 = 6)
register2 = counter;         // (register2 = 5)
register2 = register2 - 1;   // (register2 = 4)
counter = register1;         // (counter = 6)
counter = register2;         // (counter = 4)

  正确的counter值应当是5，但现在是4。读者可以自己试试，倘若再将两段程序中各语句交叉执行的顺序改变，将可看到又可能得到counter=6的答案，这表明程序的执行已经失去了再现性。为了预防产生这种错误，解决此问题的关键是应把变量counter作为临界资源处理，亦即，令生产者进程和消费者进程互斥地访问变量counter。

临界区(critical section)

  由前所述可知，不论是硬件临界资源还是软件临界资源，多个进程必须互斥地对它进行访问。人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)。显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。为此,每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。如果此刻临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。因此，必须在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区(entry section)。相应地，在临界区后面也要加上一段称为退出区(exitsection)的代码，用于将临界区正被访问的标志恢复为未被访问的标志。进程中除上述进入区、临界区及退出区之外的其它部分的代码在这里都称为剩余区。这样，可把一个访问临界资源的循环进程描述如下：

1
2
3
4
5
6
7
8

void process() {
    do{
        enter_critical_section();   //进入区
        critical_section();         //临界区
        exit_critical_section();    //退出区
        remainder_section();        //剩余区
    } while (true);
}

同步机制应遵循的规则

  为实现进程互斥地进入自己的临界区，可用软件方法，更多的是在系统中设置专门的同步机构来协调各进程间的运行。所有同步机制都应遵循下述四条准则：
  (1) 空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
  (2) 忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
  (3) 有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入"死等”状态。
  (4) 让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

硬件同步机制

  虽然可以利用软件方法解决诸进程互斥进入临界区的问题，但有一定难度，并且存在很大的局限性，因而现在已很少采用。相应地，目前许多计算机已提供了一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。可利用这些特殊的指令来解决临界区问题。实际上，在对临界区进行管理时，可以将标志看做一个锁，“锁开”进入，“锁关”等待，初始时锁是打开的。每个要进入临界区的进程必须先对锁进行测试，当锁未开时，则必须等待，直至锁被打开。反之，当锁是打开的时候，则应立即把其锁上，以阻止其它进程进入临界区。显然，为防止多个进程同时测试到锁为打开的情况，测试和关锁操作必须是连续的，不允许分开进行。

关中断

  关中断是实现互斥的最简单的方法之一。在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。由此，保证了对锁的测试和关锁操作的连续性和完整性，有效地保证了互斥。但是，关中断的方法存在许多缺点：①滥用关中断权力可能导致严重后果；②关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；③关中断方法也不适用于多CPU系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。

利用Test-and-Set指令实现互斥

  这是一种借助一条硬件指令——“测试并建立”指令TS（Test-and-Set）‌以实现互斥的方法。在许多计算机中都提供了这种指令。TS指令的一般性描述如下：

1
2
3
4
5
6
7

#include <stdbool.h>
bool TS(bool *lock) {
    bool old;
    old = *lock;
    *lock = true;
    return old;
}

  这条指令可以看作为一个函数过程，其执行过程是不可分割的，即是一条原语。其中，lock有两种状态：当lock=false时，表示该资源空闲；当lock=true时，表示该资源正在被使用。
  用TS指令管理临界区时，为每个临界资源设置一个布尔变量lock，由于变量lock代表了该资源的状态，故可把它看成一把锁。lock初值为false，表示该临界资源空闲。进程在进入临界区之前，首先用TS指令测试lock，如果其值为false，则表示没有进程在临界区内，可以进入，并将true值赋予lock，这等效于关闭了临界资源，使任何进程都不能进入临界区，否则必须循环测试直到TS(s)为true。利用TS指令实现互斥的循环进程结构可描述如下：

1
2
3
4
5
6
7
8

void process() {
    do {
        while(TS(&lock));    //进入区
        ...                  //临界区
        lock = false;        //退出区
        ...                  //剩余区
    } while (true);
}

利用Swap指令实现互斥

  该指令称为对换指令，在Intel 80x86中又称为XCHG指令，用于交换两个字的内容。其处理过程描述如下：

1
2
3
4
5
6

void swap(bool *a, bool *b) {
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

  用对换指令可以简单有效地实现互斥，方法是为每个临界资源设置一个全局的布尔变量lock,其初值为false，在每个进程中再利用一个局部布尔变量key。利用Swap指令实现进程互斥的循环进程可描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

bool lock = false;
void process() {
    bool key;
    do {
        key = true;
        do {
            swap(&lock, &key);
        } while (key != false);  //进入区
        ...                      //临界区
        lock = false;            //退出区
        ...                      //剩余区
    } while (true);
}

  利用上述硬件指令能有效地实现进程互斥，但当临界资源忙碌时，其它访问进程必须不断地进行测试，处于一种"忙等”状态，不符合“让权等待”的原则，造成处理机时间的浪费，同时也很难将它们用于解决复杂的进程同步问题。

信号量机制

  1965年，荷兰学者Dijkstra提出的信号量(Semaphores)机制是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量经记录型信号量，进而发展为‌“信号量集”机制。现在，信号量机制已被广泛地应用于单处理机和多处理机系统以及计算机网络中。

整型信号量

  最初由Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作(Atomic Operation)‌wait(&S)和signal(&S)来访问。很长时间以来，这两个操作一直被分别称为P、V操作。wait和signal操作可描述如下：

1
2
3
4
5
6
7

void wait(int *S) {
    while (*S <= 0);
    (*S)--;
}
void signal(int *S) {
    (*S)++;
}

  wait(&S)和signal(&S)是两个原子操作，因此，它们在执行时是不可中断的。亦即，当一个进程在修改某信号量时，没有其它进程可同时对该信号量进行修改。此外，在wait操作中，对S值的测试和做S=S-1操作时都不可中断。

记录型信号量

  在整型信号量机制中的wait操作，只要是信号量S⩽0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制则是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针list，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述如下：

1
2
3
4

typedef struct {
    int value;
    struct process_control_block *list;
}semaphore;

  相应地，wait(&S)和signal(&S)操作可描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        block(&(S->list)); //阻塞进程
    }
}
void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        wakeup(&(S->list)); //唤醒进程
    }
}

  在记录型信号量机制中，S->value的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个，因此描述为S->value--；当S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞，放弃处理机，并插入到信号量链表S->list中。可见，该机制遵循了“让权等待”准则。此时S->value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个，故S->value++操作表示资源数目加1。若加1后仍是S->value⩽0,则表示在该信号量链表中仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S->list链表中的第一个等待进程唤醒。如果S->value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。

AND型信号量

  前面所述的进程互斥问题针对的是多个并发进程仅共享一个临界资源的情况。在有些应用场合，是一个进程往往需要获得两个或更多的共享资源后方能执行其任务。假定现有两个进程A和B，它们都要求访问共享数据D和E，当然，共享数据都应作为临界资源。为此，可为这两个数据分别设置用于互斥的信号量Dmutex和Emutex，并令它们的初值都是1。相应地，在两个进程中都要包含两个对Dmutex和Emutex的操作，即

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void processA() {
    do{
        wait(&Dmutex);
        signal(&Dmutex);
        wait(&Emutex);
        signal(&Emutex);
    } while (true);
}
void processB() {
    do{
        wait(&Dmutex);
        signal(&Dmutex);
        wait(&Emutex);
        signal(&Emutex);
    } while (true);
}

  若进程A和B按下述次序交替执行wait操作：

1
2
3
4

processA(): wait(&Dmutex);//Dmutex=0
processB(): wait(&Emutex);//Emutex=0
processA(): wait(&Emutex);//Emutex=-1 A阻塞
prodessB(): wait(&Dmutex);//Dmutex=-1 B阻塞

  最后，进程A和B就将处于僵持状态。在无外力作用下，两者都将无法从僵持状态中解脱出来。我们称此时的进程A和B已进入死锁状态。显然，当进程同时要求的共享资源愈多时，发生进程死锁的可能性也就愈大。
  AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中增加了一个“AND”条件，故称为‌AND同步，或称为同时wait操作，Swait定义如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// Swait：等待多个信号量满足条件
void Swait(int *S1, int *S2, ..., int *Sn) {
    int *S[n] = {S1,S2,...,Sn};
    while (true) {
        bool all_ready = true;

        // 检查所有信号量是否满足条件
        for (int i = 0; i < n; i++) {
            if (*S[i] < 1) {
                all_ready = false;
                // 将当前进程放入与第一个不足的Si相关联的等待队列中
                // 并将程序计数器设置为Swait操作的开头
                place_in_waiting_queue(S[i]);
                break;
            }
        }

        // 如果所有信号量都满足条件，减去它们的值并退出循环
        if (all_ready) {
            for (int i = 0; i < n; i++) {
                (*S[i])--;
            }
            break;
        }
    }
}
// Ssignal：释放多个信号量
void Ssignal(int *S1, int *S2, ..., int *Sn) {
    int *S[n] = {S1,S2,...,Sn};
    while (true) {
        for (int i = 0; i < n; i++) {
            (*S[i])++;
            // 将等待在与Si相关的等待队列中的所有进程移至就绪队列
            move_waiting_to_ready_queue(S[i]);
        }
        break; // 退出循环以防止无限循环
    }
}

信号量集

  在前面所述的记录型信号量机制中，wait(&S)或signal(&S)操作仅能对信号量施以加1或减1操作，意味着每次只能对某类临界资源进行一个单位的申请或释放。当一次需要N个单位时，便要进行N次wait(&S)操作，这显然是低效的，甚至会增加死锁的概率。此外，在有些情况下，为确保系统的安全性，当所申请的资源数量低于某一下限值时，还必须进行管制，不予以分配。因此，当进程申请某类临界资源时，在每次分配之前，都必须测试资源的数量，判断是否大于可分配的下限值，决定是否予以分配。
  基于上述两点，可以对 AND 信号量机制加以扩充，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次 Swait、Ssignal 原语操作中完成申请或释放。进程对信号量 *Si 的测试值不再是 1 ，而是该资源的分配下限值 ti ，即要求 *Si >= ti ，否则不予分配。一旦允许分配，进程对该资源的需求值为 di ，即表示资源占用量，进行 *Si = *Si - di 操作，而不是简单的 *Si = *Si - 1 。由此形成一般化的“信号量集”机制。对应的 Swait 和 Ssignal 格式为：

1
2

Swait(int *S1, int t1, int d1, int *S2, int t2, int d2, ... ,int *Sn, int tn, int dn);
Ssignal(int *S1, int d1, int S2, int d2, ..., int *Sn, int dn);

  一般信号量集还有下面几种特殊情况：
  (1)Swait(&S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。
  (2)Swait(&S,1,1)。此时的信号量集己退化为一般的记录型信号量（S>1时）或互斥信号量（S=1时）。
  (3)Swait(&S,1,0)。这是一种很特殊且很有用的信号量操作。当S>=1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

信号量的应用

利用信号量实现进程互斥

  为使多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait(&mutex)和signal(&mutex)操作之间即可。这样，每个欲访问该临界资源的进程在进入临界区之前，都要先对mutex执行wait操作，若该资源此刻未被访问，本次wait操作必然成功，进程便可进入自己的临界区，这时若再有其它进程也欲进入自己的临界区，由于对mutex执行wait操作定会失败，因而此时该进程阻塞，从而保证了该临界资源能被互斥地访问。当访问临界资源的进程退出临界区后，又应对mutex执行signal操作，以便释放该临界资源。利用信号量实现两个进程互斥的描述如下：
  (1)设mutex为互斥信号量，其初值为1，取值范围为(-1,0,1)。当mutex=1时，表示两个进程皆未进入需要互斥的临界区；当mutex=0时，表示有一个进程进入临界区运行，另外一个必须等待，挂入阻塞队列；当mutex=-1时，表示有一个进程正在临界区运行，另外一个进程因等待而阻塞在信号量队列中，需要被当前已在临界区运行的进程退出时唤醒。
  (2)代码描述：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

semaphore mutex=1;

void ProcessA() {
    while(true) {
        wait(&mutex);
        ...//临界区
        signal(&mutex);
        ...//剩余区
    }
}

void ProcessB() {
    while(true) {
        wait(&mutex);
        ...//临界区
        signal(&mutex);
        ...//剩余区
    }
}

  在利用信号量机制实现进程互斥时应该注意，wait(&mutex)和signal(&mutex)必须成对地出现。缺少wait(&mutex)将会导致系统混乱，不能保证对临界资源的互斥访问；而缺少signal(&mutex)将会使临界资源永远不被释放，从而使因等待该资源而阻塞的进程不能被唤醒。

利用信号量实现前趋关系

  还可利用信号量来描述程序或语句之间的前趋关系。设有两个并发执行的进程 \(P_1\) 和 \(P_2\) 。 \(P_1\) 中有语句 \(S_1\) ， \(P_2\) 中有语句 \(S_2\) 。我们希望在 \(S_1\) 执行后再执行 \(S_2\) 。为实现这种前趋关系，只需使进程 \(P_1\) 和 \(P_2\) 共享一个公用信号量 \(S\) ，并赋予其初值为0，将signal(&S)操作放在语句 \(S_1\) 后面，而在 \(S_2\) 语句前面插入wait(&S)操作，即
  在进程 \(P_1\) 中，用S1;signal(&S);
  在进程 \(P_2\) 中，用wait(&S);S2;
  由于S被初始化为0，这样，若 \(P_2\) 先执行必定阻塞，只有在进程 \(P_1\) 执行完S1;signal(&S);操作后使S增为1时， \(P_2\) 进程方能成功执行语句 \(S_2\) 。同样，我们可以利用信号量按照语句间的前趋关系（见图14），写出一个更为复杂的可并发执行的程序。图14中 \(S_1,S_2,S_3,\cdots,S_6\) 是最简单的程序段（只有一条语句）。为使各程序段能正确执行，应设置若干个初始值为“0”的信号量。如为保证 \(S_1\to S_2\) ， \(S_1 \to S_3\) 的前趋关系,应分别设置信号量a和b,同样，为了保证 \(S_2 \to S_4,S_2 \to S_5, S_3 \to S_6,S_4 \to S_6\) 和 \(S_5 \to S_6\) ，应设置信号量c、d、e、f、g。代码框架描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void p1() { S1(); signal(&a); signal(&b);}
void p2() { wait(&a); S2(); signal(&c); signal(&d);}
void p3() { wait(&b); S3(); signal(&e);}
void p4() { wait(&c); S4(); signal(&f);}
void p5() { wait(&d); S5(); signal(&g);}
void p6() { wait(&e); wait(f); wait(&g); S6();} 
void main() {
    semaphore a, b, c, d, e, f, g; 
    a.value=0; b.value=0; c.vaIue=O; d.value=0;
    e.value=0; f.value=0; g.value=0;
    p1(); p2(); p3(); p4(); p5(); p6();
}

‌

图14 前趋图举例

管程机制

  虽然信号量机制是一种既方便、又有效的进程同步机制，但每个要访问临界资源的进程都必须自备同步操作wait(&S)和signal(&S)。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。这样，在解决上述问题的过程中，便产生了一种新的进程同步工具——管程(Monitors)。

管程的定义

  系统中的各种硬件资源和软件资源均可用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。因此，可以利用共享数据结构抽象地表示系统中的共享资源，并且将对该共享数据结构实施的特定操作定义为一组过程。进程对共享资源的申请、释放和其它操作必须通过这组过程，间接地对共享数据结构实现操作。对于请求访问共享资源的诸多并发进程，可以根据资源的情况接受或阻塞，确保每次仅有一个进程进入管程，执行这组过程，使用共享资源，达到对共享资源所有访问的统一管理，有效地实现进程互斥。
  代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块，我们称之为管程。管程被请求和释放资源的进程所调用。Hansan为管程所下的定义是：“一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。
  由上述的定义可知，管程由四部分组成：①管程的名称；②局部于管程的共享数据结构说明；③对该数据结构进行操作的一组过程；④对局部于管程的共享数据设置初始值的语句。图15是一个管程的示意图。管程的语法描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class MonitorName {              
public:                         
    // 共享变量
    /* share variable declarations; */ 

    // 条件变量
    /* cond declarations; */        

    // 能被进程调用的方法
    void P1(/* params */) { /* implementation */ }
    void P2(/* params */) { /* implementation */ }
    // 其他方法...

    // 构造函数，用于初始化
    MonitorName() { 
        // initialization code 
    }
};

‌

图15 管程的示意图

  实际上，管程中包含了面向对象的思想，它将表征共享资源的数据结构及其对数据结构操作的一组过程，包括同步机制，都集中并封装在一个对象内部，隐藏了实现细节。封装于管程内部的数据结构仅能被封装于管程内部的过程所访问，任何管程外的过程都不能访问它：反之，封装于管程内部的过程也仅能访问管程内的数据结构。所有进程要访问临界资源时，都只能通过管程间接访问，而管程每次只准许一个进程进入管程，执行管程内的过程，从而实现了进程互斥。
  管程是一种程序设计语言的结构成分，它和信号量有同等的表达能力，从语言的角度看，管程主要有以下特性：①模块化，即管程是一个基本程序单位，可以单独编译；②抽象数据类型，指管程中不仅有数据，而且有对数据的操作；③信息掩蔽，指管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程（函数）的具体实现外部不可见。
  管程和进程不同:①虽然二者都定义了数据结构，但进程定义的是私有数据结构PCB，管程定义的是公共数据结构，如消息队列等；②二者都存在对各自数据结构上的操作，但进程是由顺序程序执行有关操作，而管程主要是进行同步操作和初始化操作；③设置进程的目的在于实现系统的并发性，而管程的设置则是解决共享资源的互斥使用问题；④进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序一样被调用，因而管程为被动工作方式，进程则为主动工作方式；⑤进程之间能并发执行，而管程则不能与其调用者并发；⑥进程具有动态性，由“创建”而诞生，由“撤消”而消亡，而管程则是操作系统中的一个资源管理模块，供进程调用。

条件变量

  在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语wait和signal。当某进程通过管程请求获得临界资源而未能满足时，管程便调用wait原语使该进程等待，并将其排在等待队列上，如图15所示。仅当另一进程访问完成并释放该资源之后，管程才又调用signal原语，唤醒等待队列中的队首进程。
  但是仅仅有上述的同步工具是不够的，考虑一种情况：当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程，则其它进程无法进入管程，被迫长时间的等待。为了解决这个问题，引入了条件变量condition。通常，一个进程被阻塞或挂起的条件（原因）可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问只能在管程中进行。
  管程中对每个条件变量都须予以说明，其形式为：condition x,y；对条件变量的操作仅仅是wait和signal，因此条件变量也是一种抽象数据类型，每个条件变量保存了一个链表，用于记录因该条件变量而阻塞的所有进程，同时提供的两个操作即可表示为x.wait和x.signal，其含义为：
  ①x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其它进程可以使用该管程。
  ②x.signal：正在调用管程的进程发现x条件发生了变化，则调用x.signal，重新启动一个因x条件而阻塞或挂起的进程，如果存在多个这样的进程，则选择其中的一个，如果没有，继续执行原进程，而不产生任何结果。这与信号量机制中的signal操作不同。因为，后者总是要执行s=s+1操作，因而总会改变信号量的状态。
  如果有进程Q因x条件处于阻塞状态，当正在调用管程的进程P执行了x.signal操作后，进程Q被重新启动，此时两个进程P和Q，如何确定哪个执行哪个等待，可采用下述两种方式之一进行处理：
  (1)P等待，直至Q离开管程或等待另一条件。
  (2)Q等待，直至P离开管程或等待另一条件。
  采用哪种处理方式，当然是各执一词。Hoare采用了第一种处理方式，而Hansan选择了两者的折中，他规定管程中的过程所执行的signal操作是过程体的最后一个操作，于是，进程P执行signal操作后立即退出管程，因而，进程Q马上被恢复执行。

经典进程的同步问题

  在多道程序环境下，进程同步问题十分重要，也是相当有趣的问题，因而吸引了不少学者对它进行研究，由此而产生了一系列经典的进程同步问题，其中较有代表性的是“生产者—消费者”问题、“读者—写者问题”、“哲学家进餐问题"等等。通过对这些问题的研究和学习，可以帮助我们更好地理解进程同步的概念及实现方法。

生产者—消费者问题

  前面我们已经对生产者—消费者问题（The proceducer-consumer problem）‌做了一些描述，但未考虑进程的互斥与同步问题，因而造成了数据counter的不定性。由于生产者—消费者问题是相互合作的进程关系的一种抽象，例如，在输入时，输入进程是生产者，计算进程是消费者；而在输出时，则计算进程是生产者，而打印进程是消费者，因此，该问题有很大的代表性及实用价值。本小节将利用信号量机制来解决生产者—消费者问题。

利用记录型信号量解决生产者—消费者问题

  假定在生产者和消费者之间的公用缓冲池中具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者—消费者问题可描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

int in=0, out=0;
item buffer[n];
int mutex=l, empty=n, full=0;
void producer() {
    item nextp;
    do {
        nextp = produce_item();
        wait(&empty);
        wait(&mutex);
        buffer[in] = nextp;
        in = (in + 1) % n;
        signal(&mutex);
        signal(&full);
    } while (true);
}
void consumer() {
    item nextc;
    do {
        wait(&full);
        wait(&mutex);
        nextc = buffer[out];
        out = (out + 1) % n;
        signal(&mutex);
        signal(&empty);
        consume_item(nextc);
    } while (true);
}
void main() {
    create(producer);
    create(consumer);
}

  在生产者-消费者问题中应注意：首先，在每个程序中用于实现互斥的wait(&mutex)和signal(&mutex)必须成对地出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。例如，wait(&empty)在计算进程中，而signal(&empty)则在打印进程中，计算进程若因执行wait(&empty)而阻塞，则以后将由打印进程将它唤醒；最后，在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。

利用AND型信号量解决生产者—消费者问题

  对于生产者—消费者问题，也可利用AND信号量来解决，即用Swait(&empty, &mutex)来代替wait(&empty)和wait(&mutex)；用Ssignal(&mutex, &full)来代替signal(&mutex)和signal(&full)；用Swait(&full, &mutex)代替wait(&full)和wait(&mutex)，以及用Ssignal(&mutex, &empty)代替Signal(&mutex)和Signal(&empty)。利用AND信号量来解决生产者—消费者问题的算法中的生产者和消费者可描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int in=0, out=0;
item buffer[n];
int mutex=l, empty=n, full=0;
void producer() {
    item nextp;
    do {
        nextp = produce_item();
        Swait(&empty, &mutex);
        buffer[in] = nextp;
        in = (in + 1) % n;
        Ssignal(&empty, &mutex);
    } while (true);
}
void consumer() {
    item nextc;
    do {
        Swait(&full, &mutex);
        nextc = buffer[out];
        out = (out + 1) % n;
        Ssignal(&full, &mutex);
        consume_item(nextc);
    } while (true);
}
void main() {
    create(producer);
    create(consumer);
}

利用管程解决生产者—消费者问题

  在利用管程方法来解决生产者—消费者问题时，首先便是为它们建立一个管程，并命名为ProducerConsumer，或简称为PC。其中包括两个过程：
  (1) put(&x)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中己有的产品数目，当count>=N时，表示缓冲池己满，生产者须等待。
  (2) get(&x)过程。消费者利用该过程从缓冲池中取出一个产品，当count<=0时，表示缓冲池中已无可取用的产品，消费者应等待。
  对于条件变量notfull和notempty，分别有两个过程cwait和csignal对它们进行操作：
  (1) cwait(&condition)过程：当管程被一个进程占用时，其他进程调用该过程时阻塞，并挂在条件condition的队列上。
  (2) csignal(&condition)过程：唤醒在cwait执行后阻塞在条件condition队列上的进程，如果这样的进程不止一个，则选择其中一个实施唤醒操作；如果队列为空，则无操作而返回。PC管程可描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class ProducerConsumer {              
public:

    item *buffer[N];//共享变量，缓冲区
    int in,out;    //共享变量，缓冲区队列首尾指针
    
    condition notfull, notempty; //条件变量，缓冲区是否空或是否满
    int count;                   //条件变量，缓冲区内物品数量

    //Producer放入物品
    void put(item *x) {
        //如果满了，则阻塞notfull下的队列（即Producer放入物品的队列）
        if(count >= N) cwait(&notfull);
        *buffer[in] = *x;
        in = (in + 1) % N;
        count++;
        csignal(&notempty);
    }
    
    //Consumer取出物品
    void get(item *x) {
        //如果空了，则阻塞notempty下的队列（即Consumer取出物品的队列）
        if(count <= 0) cwait(&notempty);
        *x = *buffer[out];
        out = (out + 1) % N;
        count--;
        csignal(&
        notfull);
    }

    // 构造函数
    ProducerConsumer() {
        in = 0;
        out = 0;
        count = 0;
    }
};
typedef ProducerConsumer PC;

  在利用管程解决生产者—消费者问题时，其中的生产者和消费者可描述为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

void producer() {
    item x;
    do {
        x = produce_item();
        PC.put(&x)
    } while (true);
}
void consumer() {
    item x;
    do {
        PC.get(&x);
        consume_item(x);
    } while (true);
}
void main() {
    create(producer);
    create(consumer);
}

哲学家进餐问题

  由Dijkstra提出并解决的哲学家进餐问题(The Dinning Philosophers Problem)‌是典型的同步问题。该问题是描述有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。

利用记录型信号量解决哲学家进餐问题

  经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。其描述如下：

1

int chopstick[5]={1, 1, 1, 1, 1};

  所有信号量均被初始化为1，第i位哲学家的活动可描述为：

1
2
3
4
5
6
7
8

do {
    wait(&chopstick[i]);
    wait(&chopstick[(i+1)%5]);
    ...//eat
    signal(&chopstick[i]);
    signal(&chopstick[(i+l)%5]);
    ...//think
}while (true);

  在以上描述中，当哲学家饥饿时，总是先去拿他左边的筷子，即执行wait(&chopstick[i])。成功后，再去拿他右边的筷子，即执行wait(&chopstick[(i+l)%5])。又成功后便可进餐。进餐毕，又先放下他左边的筷子，然后再放他右边的筷子。虽然，上述解法可保证不会有两个相邻的哲学家同时进餐，但却有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0；当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这样的死锁问题，可采取以下几种解决方法：
  (1 )至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
  (2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。
  (3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。

利用AND信号量机制解决哲学家进餐问题

  在哲学家进餐问题中，要求每个哲学家先获得两个临界资源（筷子）后方能进餐，这在 本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。

1
2
3
4
5
6
7

int chopstick[5]={1, 1, 1, 1, 1}；
do {
    ...//think
    Sswait(&chopstick[(i+1)%5], &chopstick[i]);
    ...//eat
    Ssignal(&chopstick[(i+1)%5], &chopstick[i]);
} while (true);

读者—写者问题

  一个数据文件或记录可被多个进程共享，我们把只要求读该文件的进程称为”reader进程”，其他进程则称为”writer进程”。允许多个进程同时读一个共享对象，因为读操作不会使数据文件混乱。但不允许一个writer进程和其他reader进程或writer进程同时访问共享对象。因为这种访问将会引起混乱。所谓“读者—写者（reader-writer Problem）问题”是指保证一个writer进程必须与其他进程互斥地访问共享对象的同步问题。读者—写者问常被用来测试新同步原语。

利用记录型信号量解决读者—写者问题

  为实现reader与writer进程间在读或写时的互斥而设置了一个互斥信号量wmutex。另外，再设置一个整型变量readcount表示正在读的进程数目。由于只要有一个reader进程在读，便不允许writer进程去写。因此，仅当readcount=0，表示尚无reader进程在读时，reader进程才需要执行Wait(&wmutex)操作。若wait(&wmutex)操作成功，reader进程便可去读，相应地，做readcount+1操作。同理，仅当reader进程在执行了readcount-1操作后其值为0时，才须执行signal(&wmutex)操作，以便让writer进程写操作。又因为readcount是一个可被多个reader进程访问的临界资源，因此，也应该为它设置一个互斥信号量rmutex。
  读者-写者问题可描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int rmutex=1, wmutex=1;
int readcount=0;
void reader() {
    do {
        wait(&rmutex);
        if (readcount==0) wait(&wmutex);
        readcount++;
        signal(&rmutex);
        ...//读操作
        wait(&rmutex);
        readcount--;
        if (readcount==0) signal(&wmutex);
        signal(&rmutex);
    }while(TRUE);
}
void writer() {
    do {
        wait(&wmutex);
        ...//写操作
        signal(&wmutex);
    } while (true);
}
void main() { 
    create(reader);
    create(writer);
}

利用信号量集机制解决读者—写者问题

  这里的读者一写者问题，与前面的略有不同，它增加了一个限制，即最多只允许RN个读者同时读。为此，又引入了一个信号量L，并赋予其初值为RN，通过执行wait(&L,1,1)操作来控制读者的数目，每当有一个读者进入时，就要先执行wait(&L,1,1)操作，使L的值减1。当有RN个读者进入读后，L便减为0，第RN+1个读者要进入读时，必然会因wait(&L,1,1)操作失败而阻塞。对利用信号量集来解决读者—写者问题的描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int RN;
int L=RN, mx=1;
void reader() {
    do {
    Swait(&L, 1, 1, &mx, 1, 0);
    ...//读操作
    Ssignal(&L, 1);
    } while (true);
}
void writer() {
    do {
    Swait(&L, RN, 0, &mx, 1, 1);
    ...//写操作
    Ssignal(&mx, 1);
    } while (TRUE);
}
void main() {
    create(reader);
    create(writer); 
}

进程通信

  进程通信是指进程之间的信息交换。由于进程的互斥与同步，需要在进程间交换一定的信息，故不少学者将它们也归为进程通信，但只能把它们称为低级进程通信。我们以信号量机制为例来说明，它们之所以低级的原因在于：①效率低，生产者每次只能向缓冲池投放一个产品（消息），消费者每次只能从缓冲区中取得一个消息；②通信对用户不透明，os只为进程之间的通信提供了共享存储器。而关于进程之间通信所需之共享数据结构的设置、数据的传送、进程的互斥与同步，都必须由程序员去实现，显然，对于用户而言，这是非常不方便的。
  在进程之间要传送大量数据时，应当利用OS提供的高级通信工具，该工具最主要的特点是：
  (1) 使用方便。OS隐藏了实现进程通信的具体细节，向用户提供了一组用于实现高级通信的命令（原语），用户可方便地直接利用它实现进程之间的通信。或者说，通信过程对用户是透明的。这样就大大减少了通信程序编制上的复杂性。
  (2) 高效地传送大量数据。用户可直接利用高级通信命令（原语）高效地传送大量的数据。

进程通信的类型

  随着OS的发展，用于进程之间实现通信的机制也在发展，并已由早期的低级进程通信机制发展为能传送大量数据的高级通信工具机制。目前，高级通信机制可归结为四大类：共享存储器系统、管道通信系统、消息传递系统以及客户机—服务器系统。

共享存储器系统（Shared-Memory System）

  在共享存储器系统中，相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。据此，又可把它们分成以下两种类型：
  (1) 基于共享数据结构的通信方式。在这种通信方式中，要求诸进程公用某些数据结构，借以实现诸进程间的信息交换，如在生产者—消费者问题中的有界缓冲区。操作系统仅提供共享存储器，由程序员负责对公用数据结构的设置及对进程间同步的处理。这种通信方式仅适于传递相对少量的数据，通信效率低下，属于低级通信。
  (2)基于共享存储区的通信方式。为了传输大量数据，在内存中划出了一块共享存储区域，诸进程可通过对该共享区的读或写交换信息，实现通信，数据的形式和位置甚至访问控制都是由进程负责，而不是OS。这种通信方式属于高级通信。需要通信的进程在通信前，先向系统申请获得共享存储区中的一个分区，并将其附加到自己的地址空间中，便可对其中的数据进行正常读、写，读写完成或不再需要时，将其归还给共享存储区。

管道(pipe)通信系统

  所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。向管道（共享文件）提供输入的发送进程（即写进程）以字符流形式将大量的数据送入管道；而接受管道输出的接收进程（即读进程）则从管道中接收（读）数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。
  为了协调双方的通信，管道机制必须提供以下三方面的协调能力：①互斥，即当一个进程正在对pipe执行读/写操作时，其它（另一）进程必须等待。②同步，指当写（输入）进程把一定数量（如4KB）的数据写入pipe，便去睡眠等待，直到读（输出）进程取走数据后再把它唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后才将之唤醒。③确定对方是否存在，只有确定了对方已存在时才能进行通信。

消息传递系统(Message Passing System)

  在该机制中，进程不必借助任何共享存储区或数据结构，而是以格式化的消息(message)为单位，将通信的数据封装在消息中，并利用操作系统提供的一组通信命令（原语），在进程间进行消息传递，完成进程间的数据交换。
  该方式隐藏了通信实现细节，使通信过程对用户透明化，降低了通信程序设计的复杂性和错误率，成为当前应用最为广泛的一类进程间通信的机制。例如：在计算机网络中，消息(message)又称为报文；在微内核操作系统中，微内核与服务器之间的通信无一例外都是采用了消息传递机制；由于该机制能很好地支持多处理机系统、分布式系统和计算机网络，因此也成为这些领域最主要的通信工具。
  基于消息传递系统的通信方式属于高级通信方式，因其实现方式的不同，可进一步分成两类：
  (1)直接通信方式，是指发送进程利用OS所提供的发送原语，直接把消息发送给目标进程。
  (2)间接通信方式，是指发送和接收进程，都通过共享中间实体（称为邮箱）的方式进行消息的发送和接收，完成进程间的通信。

客户机—服务器系统（Client-Server System）

  前面所述的共享内存、消息传递等技术，虽然也可以用于实现不同计算机间进程的双向通信，但客户机—服务器系统的通信机制，在网络环境的各种应用领域已成为当前主流的通信实现机制，其主要的实现方法分为三类：套接字、远程过程调用和远程方法调用。

1. 套接字

  套接字起源于20世纪70年代加州大学伯克利分校版本的UNIX（即BSDUnix），是UNIX操作系统下的网络通信接口。一开始，套接字被设计用在同一台主机上多个应用程序之间的通信（即进程间的通信），主要是为了解决多对进程同时通信时端口和物理线路的多路复用问题。随着计算机网络技术的发展以及UNIX操作系统的广泛使用，套接字已逐渐成为最流行的网络通信程序接口之一。
  一个套接字就是一个通信标识类型的数据结构，包含了通信目的的地址、通信使用的端口号、通信网络的传输层协议、进程所在的网络地址，以及针对客户或服务器程序提供的不同系统调用（或API函数）等，是进程通信和网络通信的基本构件。套接字是为客户/服务器模型而设计的，通常，套接字包括两类：
  (1)基于文件型：通信进程都运行在同一台机器的环境中，套接字是基于本地文件系统支持的，一个套接字关联到一个特殊的文件，通信双方通过对这个特殊文件的读写实现通信，其原理类似于前面所讲的管道。
  (2)基于网络型：该类型通常采用的是非对称方式通信，即发送者需要提供接收者命名。通信双方的进程运行在不同主机的网络环境下，被分配了一对套接字，一个属于接收进程（或服务器端），一个属于发送进程（或客户端）。一般地，发送进程（或客户端）发出连接请求时，随机申请一个套接字，主机为之分配一个端口，与该套接字绑定，不再分配给其它进程。接收进程（或服务器端）拥有全局公认的套接字和指定的端口（如ftp服务器监听端口为21,Web或http服务器监听端口为80）,并通过监听端口等待客户请求。因此，任何进程都可以向它发出连接请求和信息请求，以方便进程之间通信连接的建立。接收进程（或服务器端）一旦收到请求，就接受来自发送进程（或客户端）的连接，完成连接，即在主机间传输的数据可以准确地发送到通信进程，实现进程间的通信：当通信结束时，系统通过关闭接收进程（或服务器端）的套接字撤销连接。
  套接字的优势在于，它不仅适用于同一台计算机内部的进程通信，也适用于网络环境中不同计算机间的进程通信。由于每个套接字拥有唯一的套接字号（也称套接字标识符），这样系统中所有的连接都持有唯一的一对套接字及端口连接，对于来自不同应用程序进程或网络连接的通信，能够方便地加以区分，确保了通信双方之间逻辑链路的唯一性，便于实现数据传输的并发服务，而且隐藏了通信设施及实现细节，采用统一的接口进行处理。

2. 远程过程调用和远程方法调用

  远程过程（函数）调用RPC(Remote Procedure Call)，是一个通信协议，用于通过网络连接的系统。该协议允许运行于一台主机（本地）系统上的进程调用另一台主机（远程）系统上的进程，而对程序员表现为常规的过程调用，无需额外地为此编程。如果涉及的软件采用面向对象编程，那么远程过程调用亦可称做远程方法调用。
  负责处理远程过程调用的进程有两个，一个是本地客户进程，另一个是远程服务器进程，这两个进程通常也被称为网络守护进程，主要负责在网络间的消息传递，一般情况下，这两个进程都是处于阻塞状态，等待消息。
  为了使远程过程调用看上去与本地过程调用一样，即希望实现RPC的透明性，使得调用者感觉不到此次调用的过程是在其他主机（远程）上执行的，RPC引入一个存根(stub)‌的概念：在本地客户端，每个能够独立运行的远程过程都拥有一个客户存根(client stubborn)，本地进程调用远程过程实际是调用该过程关联的存根；与此类似，在每个远程进程所在的服务器端，其所对应的实际可执行进程也存在一个服务器存根(stub)‌与其关联。本地客户存根与对应的远程服务器存根一般也是处于阻塞状态，等待消息。
  实际上，远程过程调用的主要步骤是：
  (1) 本地过程调用者以一般方式调用远程过程在本地关联的客户存根，传递相应的参数，然后将控制权转移给客户存根。
  (2)客户存根执行，完成包括过程名和调用参数等信息的消息建立，将控制权转移给本地客户进程。
  (3)本地客户进程完成与服务器的消息传递，将消息发送到远程服务器进程。
  (4)远程服务器进程接收消息后转入执行，并根据其中的远程过程名找到对应的服务器存根，将消息转给该存根。
  (5)该服务器存根接到消息后，由阻塞状态转入执行状态，拆开消息从中取出过程调用的参数，然后以一般方式调用服务器上关联的过程。
  (6)在服务器端的远程过程运行完毕后，将结果返回给与之关联的服务器存根。
  (7)该服务器存根获得控制权运行，将结果打包为消息，并将控制权转移给远程服务器进程：
  (8)远程服务器进程将消息发送回客户端。
  (9)本地客户进程接收到消息后，根据其中的过程名将消息存入关联的客户存根，再将控制权转移给客户存根。
  (10)客户存根从消息中取出结果，返回给本地调用者进程，并完成控制权的转移。
  这样，本地调用者再次获得控制权，并且得到了所需的数据，得以继续运行。显然，上述步骤的主要作用在于：将客户过程的本地调用转化为客户存根，再转化为服务器过程的本地调用，对客户与服务器来说，它们的中间步骤是不可见的，因此，调用者在整个过程中并不知道该过程的执行是在远程，而不是在本地。

消息传递通信的实现方式

  在进程之间通信时，源进程可以直接或间接地将消息传送给目标进程，因此可将进程通信分为直接和间接两种通信方式。常见的直接消息传递系统和信箱通信就是分别采用这两种通信方式。

直接消息传递系统

  在直接消息传递系统中采用直接通信方式，即发送进程利用OS所提供的发送命令（原语），直接把消息发送给目标进程。

1. 直接通信原语

  (1)对称寻址方式。该方式要求发送进程和接收进程都必须以显式方式提供对方的标识符。通常，系统提供下述两条通信命令（原语）：
  send(receiver,message); 发送一个消息给接收进程
  receive(sender,message); 接收Sender发来的消息
  例如，原语Send(P2,m1)表示将消息m1发送给接收进程P2；而原语Receive(P1,m1)则表示接受由P1发来的消息m1。
  对称寻址方式的不足在于，一旦改变进程的名称，则可能需要检查所有其它进程的定义，有关对该进程旧名称的所有引用都必须查找到，以便将其修改为新名称，显然，这样的方式不利于实现进程定义的模块化。

  (2)非对称寻址方式。在某些情况下，接收进程可能需要与多个发送进程通信，无法事先指定发送进程。例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。对于这样的应用，在接收进程的原语中，不需要命名发送进程，只填写表示源进程的参数，即完成通信后的返回值，而发送进程仍需要命名接收进程。该方式的发送和接收原语可表示为：
  send(P, message); 发送一个消息给进程P
  receive(id, message); 接收来自任何进程的消息，id变量可设置为进行通信的发送方进程id或名字。

2. 消息的格式

  在消息传递系统中所传递的消息，必须具有一定的消息格式。在单机系统环境中，由于发送进程和接收进程处于同一台机器中，有着相同的环境，所以消息的格式比较简单，可采用比较短的定长消息格式，以减少对消息的处理和存储开销。该方式可用于办公自动化系统中，为用户提供快速的便笺式通信。但这种方式对于需要发送较长消息的用户是不方便的。为此，可采用变长的消息格式，即进程所发送消息的长度是可变的。对于变长消息，系统无论在处理方面还是存储方面，都可能会付出更多的开销，但其优点在于方便了用户。

3. 进程的同步方式

  在进程之间进行通信时，同样需要有进程同步机制，以使诸进程间能协调通信。不论是发送进程还是接收进程，在完成消息的发送或接收后，都存在两种可能性，即进程或者继续发送（或接收）或者阻塞。由此，我们可得到三种情况：①发送进程阻塞，接收进程阻塞。这种情况主要用于进程之间紧密同步，发送进程和接收进程之间无缓冲时。②发送进程不阻塞、接收进程阻塞。这是一种应用最广的进程同步方式。平时，发送进程不阻塞，因而它可以尽快地把一个或多个消息发送给多个目标；而接收进程平时则处于阻塞状态，直到发送进程发来消息时才被唤醒。③发送进程和接收进程均不阻塞。这也是一种较常见的进程同步形式。平时，发送进程和接收进程都在忙于自己的事情，仅当发生某事件使它无法继续运行时，才把自己阻塞起来等待。

4. 通信链路

  为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种方式建立通信链路。第一种方式是：由发送进程在通信之前用显式的“建立连接”命令（原语）请求系统为之建立一条通信链路，在链路使用完后拆除链路。这种方式主要用于计算机网络中。第二种方式是：发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令（原语），系统会自动地为之建立一条链路。这种方式主要用于单机系统中。而根据通信方式的不同，则又可把链路分成两种：①单向通信链路，只允许发送进程向接收进程发送消息，或者相反；②双向通信链路，既允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息。

信箱通信

  信箱通信属于间接通信方式，即进程之间的通信，需要通过某种中间实体（如共享数据结构等）来完成。该实体建立在随机存储器的公用缓冲区上，用来暂存发送进程发送给目标进程的消息；接收进程可以从该实体中取出发送进程发送给自己的消息，通常把这种中间实体称为邮箱（或信箱），每个邮箱都有一个唯一的标识符。消息在邮箱中可以安全地保存，只允许核准的目标用户随时读取。因此，利用邮箱通信方式既可实现实时通信，又可实现非实时通信。

1. 信箱的结构

  信箱定义为一种数据结构。在逻辑上，可以将其分为两个部分：
  (1)信箱头，用以存放有关信箱的描述信息，如信箱标识符、信箱的拥有者、信箱口令、信箱的空格数等。
  (2)信箱体，由若干个可以存放消息（或消息头）的信箱格组成，信箱格的数目以及每格的大小是在创建信箱时确定的。
  在消息传递方式上，最简单的情况是单向传递。消息的传递也可以是双向的。图16示出了双向通信链路的通信方式。

图16 双向信箱示意图

*2. 信箱通信原语

  系统为邮箱通信提供了若干条原语，分别用于：
  (1)邮箱的创建和撤消。进程可利用邮箱创建原语来建立一个新邮箱，创建者进程应给出邮箱名字、邮箱属性（公用、私用或共享）；对于共享邮箱，还应给出共享者的名字。当进程不再需要读邮箱时，可用邮箱撤消原语将之撤消。
  (2)消息的发送和接收。当进程之间要利用邮箱进行通信时，必须使用共享邮箱，并利用系统提供的下述通信原语进行通信。
  Send(mailbox, message); 将一消息发送到指定邮箱
  Receive(mailbox, message); 从指定邮箱中接收一个消息

3. 信箱的类型

  邮箱可由操作系统创建，也可由用户进程创建，创建者是邮箱的拥有者。据此，可把邮箱分为以下三类：
  (1)私用邮箱。用户进程可为自己建立一个新邮箱，并作为该进程的一部分。邮箱的拥有者有权从邮箱中读取消息，其他用户则只能将自己构成的消息发送到该邮箱中。这种私用邮箱可采用单向通信链路的邮箱来实现。当拥有该邮箱的进程结束时，邮箱也随之消失。
  (2)公用邮箱。由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该邮箱中，也可从邮箱中读取发送给自己的消息。显然，公用邮箱应采用双向通信链路的邮箱来实现。通常，公用邮箱在系统运行期间始终存在。
  (3)共享邮箱。由某进程创建，在创建时或创建后指明它是可共享的，同时须指出共享进程（用户）的名字。邮箱的拥有者和共享者都有权从邮箱中取走发送给自己的消息。在利用邮箱通信时，在发送进程和接收进程之间，存在以下四种关系：①一对一关系。发送进程和接收进程可以建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。②多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服务器交互(client/server interaction)。③一对多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式向接收者（多个）发送消息。④多对多关系。允许建立一个公用邮箱，让多个进程都能向邮箱中投递消息；也可从邮箱中取走属于自己的消息。

直接消息传递系统实例

  消息缓冲队列通信机制首先由美国的Hansan提出，并在RC4000系统上实现，后来被广泛应用于本地进程之间的通信中。在这种通信机制中，发送进程利用Send原语将消息直接发送给接收进程；接收进程则利用Receive原语接收消息。

消息缓冲队列通信机制中的数据结构

  (1)消息缓冲区。在消息缓冲队列通信方式中，主要利用的数据结构是消息缓冲区。它可描述如下：

1
2
3
4
5
6

typedef struct message_buffer {
    int sender;                   //发送者进程标识符
    int size;                     //消息长度
    char *text;                   //消息正文
    struct message_buffer *next;  //指向下一个消息缓冲区的指针
}MesBuf;

  (2)PCB中有关通信的数据项。在操作系统中采用了消息缓冲队列通信机制时，除了需要为进程设置消息缓冲队列外，还应在进程的PCB中增加消息队列队首指针，用于对消息队列进行操作，以及用于实现同步的互斥信号量mutex和资源信号量sm。在PCB中应增加的数据项可描述如下：

1
2
3
4
5
6
7

typedef struct processcontrol_block {
    ...
    struct message_buffer *mq;    //消息队列队首指针
    semaphore mutex;              //消息队列互斥信号量
    semaphore sm;                 //消息队列资源信号量
    ...
}PCB;

发送原语

  发送进程在利用发送原语发送消息之前，应先在自己的内存空间设置一发送区a，如图17所示，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后调用发送原语，把消息发送给目标（接收）进程。发送原语首先根据发送区a中所设置的消息长度a.size来申请一缓冲区i，接着，把发送区a中的信息复制到缓冲区i中。为了能将i挂在接收进程的消息队列mq上，应先获得接收进程的内部标识符j，然后将i挂在j.mq上。由于该队列属于临界资源，故在执行insert操作的前后都要执行wait和signal操作。最后，释放信号量sm表示消息发送完毕。

图17 消息缓冲通信

  发送原语可描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void send(Process *receiver, Message *a) {       //receive为接收进程标识符，a为发送区首地址
    MesBuf *i = getbuf(a->size);         //根据a.size申请缓冲区
    
    /* 将发送区a中的信息复制到消息缓冲区i中 */
    i->sender=a->sender;
    i->size=a->size;
    copy(i->text, a->text);
    i->next=NULL;
    
    PCB *j = get_pcb(receiver); //获取接收进程内部的标识符
    wait(&(j->mutex))
    insert(&(j->mq), i);          //将消息缓冲区插入消息队列
    signal(&(j->mutex));
    signal(&(j->sm));             //发送完毕
}

接收原语

  从自己的消息缓冲队列mq中摘下第一个消息缓冲 并将其中的数据复制到以b为首址的指定消息接收区内。接收原语描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void receive(b) {
    PCB* j = get_pid(b);         //j为接收进程b内部的标识符
    wait(&(j->sm));
    wait(&(j->mutex));
    MesBuf* i = remove(&(j->mq));    //将消息队列中的第一个消息移出
    signal(&(j.mutex));
    
    /* 将消息缓冲区i中的信息复制到接收区b */
    b->sender = i->sender;
    b->size = i->size;
    copy(b->text, i->text);
    
    releasebuf(i);               //释放消息缓冲区
}

线程(Threads)的基本概念

  在20世纪60年代中期，人们在设计多道程序OS时，引入了进程的概念，从而解决了在单处理机环境下的程序并发执行问题。此后在长达20年的时间里，在多道程序OS中一直是以进程作为能拥有资源和独立调度（运行）的基本单位的。直到80年代中期，人们又提出了比进程更小的基本单位——线程的概念，试图用它来提高程序并发执行的程度，以进一步改善系统的服务质量。特别是在进入20世纪90年代后，多处理机系统得到迅速发展，由于线程能更好地提高程序的并行执行程度，因而近几年推出的多处理机OS无一例外地都引入了线程，用以改善OS的性能。

线程的引入

  如果说，在OS中引入进程的目的是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量，那么，在操作系统中再引入线程，则是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。

进程的两个基本属性

  首先让我们来回顾进程的两个基本属性：①进程是一个可拥有资源的独立单位，一个进程要能独立运行，它必须拥有一定的资源，包括用于存放程序正文、数据的磁盘和内存地址空间，以及它在运行时所需要的I/O设备、已打开的文件、信号量等；②进程同时又是一个可独立调度和分派的基本单位，一个进程要能独立运行，它还必须是一个可独立调度和分派的基本单位。每个进程在系统中有唯一的PCB,系统可根据其PCB感知进程的存在，也可以根据其PCB中的信息，对进程进行调度，还可将断点信息保存在其PCB中。反之，再利用进程PCB中的信息来恢复进程运行的现场。正是由于进程有这两个基本属性，才使进程成为一个能独立运行的基本单位，从而也就构成了进程并发执行的基础。

程序并发执行所需付出的时空开销

  为使程序能并发执行，系统必须进行以下的一系列操作：
  (1)创建进程，系统在创建一个进程时，必须为它分配其所必需的、除处理机以外的所有资源，如内存空间、I/O设备，以及建立相应的PCB。
  (2)撤消进程，系统在撤消进程时，又必须先对其所占有的资源执行回收操作，然后再撤消PCB。
  (3)进程切换，对进程进行上下文切换时，需要保留当前进程的CPU环境，设置新选中进程的CPU环境，因而须花费不少的处理机时间。
  据此可知，由于进程是一个资源的拥有者，因而在创建、撤消和切换中，系统必须为之付出较大的时空开销。这就限制了系统中所设置进程的数目，而且进程切换也不宜过于频繁，从而限制了并发程度的进一步提高。

线程——作为调度和分派的基本单位

  如何能使多个程序更好地并发执行，同时又尽量减少系统的开销，已成为近年来设计操作系统时所追求的重要目标。有不少研究操作系统的学者们想到，要设法将进程的上述两个属性分开，由OS分开处理，亦即并不把作为调度和分派的基本单位也同时作为拥有资源的单位，以做到"轻装上阵”；而对于拥有资源的基本单位，又不对之施以频繁的切换。正是在这种思想的指导下，形成了线程的概念。
  随着VLSI技术和计算机体系结构的发展，出现了对称多处理机(SMP)计算机系统。它为提高计算机的运行速度和系统吞吐量提供了良好的硬件基础。但要使多个CPU很好地协调运行，充分发挥它们的并行处理能力，以提高系统性能，还必须配置性能良好的多处理机OS。但利用传统的进程概念和设计方法已难以设计出适合于SMP结构计算机系统的OS。其最根本的原因是进程“太重”，致使为实现多处理机环境下的进程的创建、调度、分派，都需花费较大的时间和空间开销。如果在OS中引入线程，以线程作为调度和分派的基本单位，则可以有效地改善多处理机系统的性能。因此，一些主要的OS（UNIX、Windows）厂家又进一步对线程技术做了开发，使之适用于SMP的计算机系统。

线程与进程的比较

  由于线程具有许多传统进程所具有的特征，所以又称之为轻型进程（Light-Weight Process）‌或进程元，相应地，把传统进程称为重型进程（Heavy-Weight Process）。它相当于只有一个线程的任务。下面我们从调度性、并发性、系统开销和拥有资源等方面对线程和进程进行比较。

调度的基本单位

  在传统的OS中，进程是作为独立调度和分派的基本单位，因而进程是能独立运行的基本单位。在每次被调度时，都需要进行上下文切换，开销较大。而在引入线程的OS中，已把线程作为调度和分派的基本单位，因而线程是能独立运行的基本单位。当线程切换时，仅需保存和设置少量寄存器内容，切换代价远低于进程。在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，必然就会引起进程的切换。

并发性

  在引入线程的OS中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，甚至还允许在一个进程中的所有线程都能并发执行。同样，不同进程中的线程也能并发执行。这使得OS具有更好的并发性，从而能更加有效地提高系统资源的利用率和系统的吞吐量。例如，在文字处理器中可以设置三个线程：第一个线程用于显示文字和图形，第二个线程从键盘读入数据，第三个线程在后台进行拼写和语法检查。又如，在网页浏览器中，可以设置一个线程来显示图像或文本，再设置一个线程用于从网络中接收数据。
  此外，有的应用程序需要执行多个相似的任务。例如，一个网络服务器经常会接到许多客户的请求，如果仍采用传统的单线程的进程来执行该任务，则每次只能为一个客户服务。但如果在一个进程中可以设置多个线程，将其中的一个专用于监听客户的请求，则每当有一个客户请求时，便立即创建一个线程来处理该客户的请求。

拥有资源

  进程可以拥有资源，并作为系统中拥有资源的一个基本单位。然而，线程本身并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源。比如，在每个线程中都应具有一个用于控制线程运行的线程控制块TCB、用于指示被执行指令序列的程序计数器、保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。
  线程除了拥有自己的少量资源外，还允许多个线程共享该进程所拥有的资源，这首先表现在：属于同一进程的所有线程都具有相同的地址空间，这意味着，线程可以访问该地址空间中的每一个虚地址；此外，还可以访问进程所拥有的资源，如已打开的文件、定时器、信号量机构等的内存空间和它所申请到的I/O设备等。

独立性

  在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。这是因为，为防止进程之间彼此干扰和破坏，每个进程都拥有一个独立的地址空间和其它资源，除了共享全局变量外，不允许其它进程的访问。但是同一进程中的不同线程往往是为了提高并发性以及进行相互之间的合作而创建的，它们共享进程的内存地址空间和资源，如每个线程都可以访问它们所属进程地址空间中的所有地址，如一个线程的堆栈可以被其它线程读、写，甚至完全清除。由一个线程打开的文件可以供其它线程读、写。

系统开销

  在创建或撤消进程时，系统都要为之分配和回收进程控制块、分配或回收其它资源，如内存空间和I/O设备等。OS为此所付出的开销，明显大于线程创建或撤消时所付出的开销。类似地，在进程切换时，涉及到进程上下文的切换，而线程的切换代价也远低于进程的。例如，在Solaris 2 OS中，线程的创建要比进程的创建快30倍，而线程上下文切换要比进程上下文的切换快5倍。此外，由于一个进程中的多个线程具有相同的地址空间，线程之间的同步和通信也比进程的简单。因此，在一些OS中，线程的切换、同步和通信都无需操作系统内核的干预。

支持多处理机系统

  在多处理机系统中，对于传统的进程，即单线程进程，不管有多少处理机，该进程只能运行在一个处理机上。但对于多线程进程，就可以将一个进程中的多个线程分配到多个处理机上，使它们并行执行，这无疑将加速进程的完成。因此，现代多处理机OS都无一例外地引入了多线程。

线程的状态和线程控制块

线程运行的三个状态

  与传统的进程一样，在各线程之间也存在着共享资源和相互合作的制约关系，致使线 程在运行时也具有间断性。相应地，线程在运行时也具有下述三种基本状态：
  (1)执行状态，表示线程已获得处理机而正在运行。
  (2)就绪状态，指线程已具备了各种执行条件，只须再获得CPU便可立即执行。
  (3)阻塞状态，指线程在执行中因某事件受阻而处于暂停状态，例如，当一个线程执行从键盘读入数据的系统调用时，该线程就被阻塞。 线程状态之间的转换和进程状态之间的转换是一样的，如图5所示。

线程控制块TCB

  如同每个进程有一个进程控制块一样,系统也为每个线程配置了一个线程控制块TCB,将所有用于控制和管理线程的信息记录在线程控制块中。线程控制块通常有这样几项：①线程标识符，为每个线程赋予一个唯一的线程标识符；②一组寄存器，包括程序计数器PC、状态寄存器和通用寄存器的内容；③线程运行状态，用于描述线程正处于何种运行状态；④优先级，描述线程执行的优先程度：⑤线程专有存储区，用于线程切换时存放现场保护信息，和与该线程相关的统计信息等；⑥信号屏蔽，即对某些信号加以屏蔽：⑦堆栈指针，在线程运行时，经常会进行过程调用，而过程的调用通常会出现多重嵌套的情况，这样，就必须将每次过程调用中所使用的局部变量以及返回地址保存起来。为此，应为每个线程设置一个堆栈，用它来保存局部变量和返回地址。相应地，在TCB中，也须设置两个指向堆栈的指针：指向用户自己堆栈的指针和指向核心栈的指针。前者是指当线程运行在用户态时，使用用户自己的用户栈来保存局部变量和返回地址，后者是指当线程运行在核心态时使用系统的核心栈。

多线程OS中的进程属性

  通常在多线程OS中的进程都包含了多个线程，并为它们提供资源。OS支持在一个进程中的多个线程能并发执行，但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性：
  (1)进程是一个可拥有资源的基本单位。在多线程OS中，进程仍是作为系统资源分配的基本单位，任一进程所拥有的资源都包括：用户的地址空间、实现进程（线程）间同步和通信的机制、已打开的文件和已申请到的I/O设备，以及一张由核心进程维护的地址映射表，该表用于实现用户程序的逻辑地址到其内存物理地址的映射。
  (2)多个线程可并发执行。通常一个进程都含有若干个相对独立的线程，其数目可多可少，但至少要有一个线程。由进程为这些（个）线程提供资源及运行环境，使它们能并发执行。在OS中的所有线程都只能属于某一个特定进程。实际上，现在把传统进程的执行方法称为单线程方法。如传统的UNIX系统能支持多用户进程，但只支持单线程方法。反之，将每个进程支持多个线程执行的方法称为多线程方法。如Java的运行环境是单进程多线程的，Windows 2000、Solaris、Mach等采用的则是多进程多线程的方法。
  (3)进程已不是可执行的实体。在多线程OS中，是把线程作为独立运行（或称调度）的基本单位。此时的进程已不再是一个基本的可执行实体。虽然如此，进程仍具有与执行相关的状态。例如，所谓进程处于“执行”状态，实际上是指该进程中的某线程正在执行。此外，对进程所施加的与进程状态有关的操作也对其线程起作用。例如，在把某个进程挂起时，该进程中的所有线程也都将被挂起；又如，在把某进程激活时，属于该进程的所有线程也都将被激活。

线程的实现

线程的实现方式

  线程已在许多系统中实现，但各系统的实现方式并不完全相同。在有的系统中，特别是一些数据库管理系统，如infomix所实现的是用户级线程；而另一些系统（如Macintosh和OS/2操作系统）所实现的是内核支持线程；还有一些系统如Solaris操作系统，则同时实现了这两种类型的线程。

内核支持线程KST(Kernel Supported Threads)

  在OS中的所有进程，无论是系统进程还是用户进程，都是在操作系统内核的支持下运行的，是与内核紧密相关的。而内核支持线程KST同样也是在内核的支持下运行的，它们的创建、阻塞、撤消和切换等，也都是在内核空间实现的。为了对内核线程进行控制和管理，在内核空间也为每一个内核线程设置了一个线程控制块，内核根据该控制块而感知某线程的存在，并对其加以控制。当前大多数OS都支持内核支持线程。
  这种线程实现方式主要有四个主要优点：
  (1)在多处理器系统中，内核能够同时调度同一进程中的多个线程并行执行。
  (2)如果进程中的一个线程被阻塞了，内核可以调度该进程中的其它线程占有处理器运行，也可以运行其它进程中的线程。
  (3)内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小。
  (4)内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。 内核支持线程的主要缺点是：对于用户的线程切换而言，其模式切换的开销较大，在同一个进程中，从一个线程切换到另一个线程时，需要从用户态转到核心态进行，这是因为用户进程的线程在用户态运行，而线程调度和管理是在内核实现的，系统开销较大。

用户级线程ULT(User Level Threads)

  用户级线程是在用户空间中实现的。对线程的创建、撤消、同步与通信等功能，都无需内核的支持，即用户级线程是与内核无关的。在一个系统中的用户级线程的数目可以达到数百个至数千个。由于这些线程的任务控制块都是设置在用户空间，而线程所执行的操作也无需内核的帮助，因而内核完全不知道用户级线程的存在。
  值得说明的是，对于设置了用户级线程的系统，其调度仍是以进程为单位进行的。在采用轮转调度算法时，各个进程轮流执行一个时间片，这对诸进程而言貌似是公平的。但假如在进程A中包含了一个用户级线程，而在另一个进程B中含有100个用户级线程，这样，进程A中线程的运行时间将是进程B中各线程运行时间的100倍：相应地，其速度要快上100倍，因此说实质上并不公平。
  假如系统中设置的是内核支持线程，则调度便是以线程为单位进行的。在采用轮转法调度时，是各个线程轮流执行一个时间片。同样假定进程A中只有一个内核支持线程，而在进程B中有100个内核支持线程。此时进程B可以获得的CPU时间是进程A的100倍,且进程B可使100个系统调用并发工作。

  使用用户级线程方式有许多优点：
  (1)线程切换不需要转换到内核空间。对一个进程而言，其所有线程的管理数据结构均在该进程的用户空间中，管理线程切换的线程库也在用户地址空间运行，因此进程不必切换到内核方式来做线程管理，从而节省了模式切换的开销。
  (2)调度算法可以是进程专用的。在不干扰OS调度的情况下，不同的进程可以根据自身需要选择不同的调度算法，对自己的线程进行管理和调度，而与OS的低级调度算法是无关的。
  (3)用户级线程的实现与OS平台无关，因为对于线程管理的代码是属于用户程序的一部分，所有的应用程序都可以对之进行共享。因此，用户级线程甚至可以在不支持线程机制的操作系统平台上实现。

  而用户级线程方式的主要缺点则在于：
  (1)系统调用的阻塞问题。在基于进程机制的OS中，大多数系统调用将使进程阻塞，因此，当线程执行一个系统调用时，不仅该线程被阻塞，而且，进程内的所有线程会被阻塞。而在内核支持线程方式中，则进程中的其它线程仍然可以运行。
  (2)在单纯的用户级线程实现方式中，多线程应用不能利用多处理机进行多重处理的优点，内核每次分配给一个进程的仅有一个CPU。因此，进程中仅有一个线程能执行，在该线程放弃CPU之前，其它线程只能等待。

组合方式

  有些OS把用户级线程和内核支持线程两种方式进行组合，提供了组合方式ULT/KST线程。在组合方式线程系统中，内核支持多个内核支持线程的建立、调度和管理，同时，也允许用户应用程序建立、调度和管理用户级线程。一些内核支持线程对应多个用户级线程，这是用户级线程通过时分多路复用内核支持线程来实现的。即将用户级线程对部分或全部内核支持线程进行多路复用，程序员可按应用需要和机器配置，对内核支持线程数目进行调整，以达到较好效果。组合方式线程中，同一个进程内的多个线程可以同时在多处理器上并行执行，而且在阻塞一个线程时并不需要将整个进程阻塞。所以，组合方式多线程机制能够结合KST和ULT两者的优点，并克服了其各自的不足。由于用户级线程和内核支持线程连接方式的不同，从而形成了三种不同的模型：多对一模型、一对一模型和多对多模型：
  (1)多对一模型，即将用户线程映射到一个内核控制线程。如图18(a)所示，这些用户线程一般属于一个进程，运行在该进程的用户空间，对这些线程的调度和管理也是在该进程的用户空间中完成。仅当用户线程需要访问内核时，才将其映射到一个内核控制线程上，但每次只允许一个线程进行映射。该模型的主要优点是线程管理的开销小，效率高；其主要缺点在于，如果一个线程在访问内核时发生阻塞，则整个进程都会被阻塞；此外，在任一时刻，只有一个线程能够访问内核，多个线程不能同时在多个处理机上运行。
  (2)一对一模型，即将每一个用户级线程映射到一个内核支持线程。如图18(b)所示，为每一个用户线程都设置一个内核控制线程与之连接。该模型的主要优点是：当一个线程阻塞时，允许调度另一个线程运行，所以它提供了比多对一模型更好的并发功能。此外，在多处理机系统中，它允许多个线程并行地运行在多处理机系统上。该模型的唯一缺点是:每创建一个用户线程，相应地就需要创建一个内核线程，开销较大，因此需要限制整个系统的线程数。Windows2000、WindowsNT、OS/2等系统上都实现了该模型。
  (3)多对多模型，即将许多用户线程映射到同样数量或更少数量的内核线程上。如图18(c)所示，内核控制线程的数目可以根据应用进程和系统的不同而变化，可以比用户线程少，也可以与之相同。该模型结合上述两种模型的优点，它可以像一对一模型那样，使一个进程的多个线程并行地运行在多处理机系统上，也可像多对一模型那样，减少线程的管理开销和提高效率。

图18 多线程模型

线程的实现

  不论是进程还是线程，都必须直接或间接地取得内核的支持。由于内核支持线程可以直接利用系统调用为它服务，故线程的控制相当简单；而用户级线程必须借助于某种形式的中间系统的帮助方能取得内核的服务，故在对线程的控制上要稍复杂些。

内核支持线程的实现

  在仅设置了内核支持线程的OS中，一种可能的线程控制方法是，系统在建一个新进程时，便为它分配一个任务数据区PTDA(Per Task Data Area)，其中包括若干个线程控制块TCB空间，如图19所示。在每一个TCB中可保存线程标识符、优先级、线程运行的CPU状态等信息。虽然这些信息与用户级线程TCB中的信息相同，但现在却是被保存在内核空间中。

图19 任务数据区空间

  每当进程要创建一个线程时，便为新线程分配一个TCB，将有关信息填入该TCB中，并为之分配必要的资源，如为线程分配数百至数千个字节的栈空间和局部存储区，于是新创建的线程便有条件立即执行。当PTDA中的所有TCB空间已用完，而进程又要创建新的线程时，只要其所创建的线程数目未超过系统的允许值（通常为数十至数百个），系统可再为之分配新的TCB空间；在撤消一个线程时，也应回收该线程的所有资源和TCB。可见，内核支持线程的创建、撤消均与进程的相类似。在有的系统中为了减少在创建和撤消一个线程时的开销，在撤消一个线程时并不立即回收该线程的资源和TCB，这样，当以后再要创建一个新线程时，便可直接利用已被撤消但仍保持有资源的TCB作为新线程的TCB。
  内核支持线程的调度和切换与进程的调度和切换十分相似，也分抢占式方式和非抢占方式两种。在线程的调度算法上，同样可采用时间片轮转法、优先权算法等。当线程调度选中一个线程后，便将处理机分配给它。当然，线程在调度和切换上所花费的开销要比进程的小得多。

用户级线程的实现

  用户级线程是在用户空间实现的。所有的用户级线程都具有相同的结构，它们都运行在一个中间系统上。当前有两种方式实现中间系统，即运行时系统和内核控制线程。

1. 运行时系统(Runtime System)

  所谓“运行时系统”，实质上是用于管理和控制线程的函数（过程）的集合，其中包括用于创建和撤消线程的函数、线程同步和通信的函数，以及实现线程调度的函数等。正因为有这些函数，才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间，并作为用户级线程与内核之间的接口。
  在传统的OS中，进程在切换时必须先由用户态转为核心态，再由核心来执行切换任务；而用户级线程在切换时则不须转入核心态，而是由运行时系统中的线程切换过程（函数），来执行切换任务，该过程将线程的CPU状态保存在该线程的堆栈中，然后按照一定的算法，选择一个处于就绪状态的新线程运行，将新线程堆栈中的CPU状态装入到CPU相应的寄存器中，一旦将栈指针和程序计数器切换后，便开始了新线程的运行。由于用户级线程的切换无须进入内核，且切换操作简单，因而使用户级线程的切换速度非常快。
  不论在传统的OS中，还是在多线程OS中，系统资源都是由内核管理的。在传统的OS中，进程是利用OS提供的系统调用来请求系统资源的，系统调用通过软中断（如trap）机制进入OS内核，由内核来完成相应资源的分配。用户级线程是不能利用系统调用的。当线程需要系统资源时，是将该要求传送给运行时系统，由后者通过相应的系统调用来获得系统资源。

2. 内核控制线程

  这种线程又称为轻型进程（LWP，Light Weight Process）。每一个进程都可拥有多个LWP，同用户级线程一样，每个LWP都有自己的数据结构（如TCB）,其中包括线程标识符、优先级、状态，另外还有栈和局部存储区等。LWP也可以共享进程所拥有的资源。LWP可通过系统调用来获得内核提供的服务，这样，当一个用户级线程运行时，只须将它连接到一个LWP上，此时它便具有了内核支持线程的所有属性。这种线程实现方式就是组合方式。
  在一个系统中的用户级线程数量可能很大，为了节省系统开销，不可能设置太多的LWP，而是把这些LWP做成一个缓冲池，称为“线程池”。用户进程中的任一用户线程都可以连接到LWP池中的任何一个LWP上。为使每一用户级线程都能利用LWP与内核通信,可以使多个用户级线程多路复用一个LWP,但只有当前连接到LWP上的线程才能与内核通信，其余进程或者阻塞，或者等待LWP。而每一个LWP都要连接到一个内核级线程上,这样，通过LWP可把用户级线程与内核线程连接起来，用户级线程可通过LWP来访问内核，但内核所看到的总是多个LWP而看不到用户级线程。亦即，由LWP实现了内核与用户级线程之间的隔离，从而使用户级线程与内核无关。图20示出了利用轻型进程作为中 间系统时用户级线程的实现方法。

图20 利用轻型线程作为中间系统

  当用户级线程不需要与内核通信时，并不需要LWP；而当要通信时，便须借助于LWP,而且每个要通信的用户级线程都需要一个LWP。例如，在一个任务中，如果同时有5个用户级线程发出了对文件的读、写请求，这就需要有5个LWP来予以帮助，即由LWP将对文件的读、写请求发送给相应的内核级线程，再由后者执行具体的读、写操作。如果一个任务中只有4个LWP，则只能有4个用户级线程的读、写请求被传送给内核线程，余下的一个用户级线程必须等待。
  在内核级线程执行操作时，如果发生阻塞，则与之相连接的多个LWP也将随之阻塞，进而使连接到LWP上的用户级线程也被阻塞。如果进程中只包含了一个LWP，此时进程也应阻塞。这种情况与前述的传统OS一样，在进程执行系统调用时，该进程实际上是阻塞的。但如果在一个进程中含有多个LWP，则当一个LWP阻塞时，进程中的另一个LWP可继续执行；即使进程中的所有LWP全部阻塞，进程中的线程也仍然能继续执行，只是不能再去访问内核。

线程的创建和终止

  如同进程一样，线程也是具有生命期的，它由创建而产生，由调度而执行，由终止而消亡。相应的，在OS中也就有用于创建线程的函数（或系统调用）和用于终止线程的函数（或系统调用）。

线程的创建

  应用程序在启动时，通常仅有一个线程在执行，人们把线程称为“初始化线程”，它的主要功能是用于创建新线程。在创建新线程时，需要利用一个线程创建函数（或系统调用），并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。在线程的创建函数执行完后，将返回一个线程标识符供以后使用。

线程的终止

  当一个线程完成了自己的任务（工作）后，或是线程在运行中出现异常情况而须被强行终止时，由终止线程通过调用相应的函数（或系统调用）对它执行终止操作。但有些线程（主要是系统线程），它们一旦被建立起来之后，便一直运行下去而不被终止。在大多数的OS中，线程被中止后并不立即释放它所占有的资源，只有当进程中的其它线程执行了分离函数后，被终止的线程才与资源分离，此时的资源才能被其它线程利用。
  虽已被终止但尚未释放资源的线程仍可以被需要它的线程所调用，以使被终止线程重新恢复运行。为此，调用线程须调用一条被称为“等待线程终止”的连接命令来与该线程进行连接。如果在一个调用者线程调用“等待线程终止”的连接命令，试图与指定线程相连接时，若指定线程尚未被终止，则调用连接命令的线程将会阻塞，直至指定线程被终止后，才能实现它与调用者线程的连接并继续执行：若指定线程已被终止，则调用者线程不会被阻塞而是继续执行。

人生只若如初见，何事秋风悲画扇。

― 纳兰性德, 《木兰花·拟古决绝词柬友》