文章目录

• 2.4.1 进程同步的基本概念
• • 1. 两种形式的制约关系
  • 2. 临界资源
  • • 生产者消费者问题
  • 3. 临界区
  • 4. 同步机制应遵循的规则
• 2.4.2 硬件同步机制
• • 1. 关中断
  • 2. 利用Test-and-Set指令实现互斥
  • 3. 利用Swap指令实现进程互斥
• 2.4.3 信 量机制
• • 1. 整型信 量
  • 2. 记录型信 量
  • 3. AND型信 量
  • 4. 信 量集
• 2.4.4 信 量的应用
• • 1. 利用信 量实现进程互斥
  • 2. 利用信 量实现前趋关系
• 2.4.5 管程机制
• • 1. 管程的定义
  • 2. 条件变量

在OS中引入进程后，一方面可以使系统中的多道程序并发执行，这不仅能有效地改善资源利用率，还可显著地提高系统的吞吐量，但另一方面却使系统变得更加复杂。如果不能采取有效的措施，对多个进程的运行进行妥善的管理，必然会因为这些进程对系统资源的无序争夺给系统造成混乱。致使每次处理的结果存在着不确定性，即显现出其不可再现性。

为保证多个进程能有条不紊地运行，在多道程序系统中，必须引入进程同步机制。

2.4.1 进程同步的基本概念

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

1. 两种形式的制约关系

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

1. 间接相互制约关系（互斥关系）

   进程间互斥使用临界资源。

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

2. 直接相互制约关系（同步关系）

   进程间相互合作。

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

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

2. 临界资源

• 系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。
• 诸进程间应采取互斥方式，实现对这种资源的共享。
• 许多硬件资源如打印机、磁带机等，都属于临界资源。

下面我们将通过一个简单的例子来说明这一过程。

生产者消费者问题

生产者一消费者问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池（最多可放n个产品），生产者进程将其所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，既不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

我们首先设置4个变量

• 缓冲池buffer

  用数组来表示具有n个缓冲区的缓冲池。

• 输入指针in

  指示下一个可投放产品的缓冲区，每当生产者进程生产投放一个产品后，输入指针加1，初值为0。

• 输出指针out

  指示下一个可获取产品的缓冲区， 每当消费者进程取走一个产品后， 输出指针加1，初值为0。

• 整型变量count

  初值为0，表示缓冲区中的产品个数。

示意图：

消费者进程：

为了解决并发执行的不可再现性，和应原子性的执行。

3. 临界区

不论是硬件临界资源还是软件临界资源， 多个进程必须互斥地对它进行访问。人们把在每个进程中访问临界资源的那段代码称为临界区。在生产者消费者问题中，count为临界资源，和为临界区。

一个访问临界资源的循环进程可分为如下几个区：

1. 进入区

   用于检查进程是否可以进入临界区的代码段。

   如果此刻临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。

2. 临界区

   进程中涉及临界资源的代码段。

3. 退出区

   用于将临界区正被访问的标志恢复为未被访问的标志。

4. 剩余区

   进程中除上述进入区、临界区及退出区之外的其它部分的代码在这里都称为剩余区。

可把一个访问临界资源的循环进程描述如下：

这条指令可以看作为一个函数过程，其执行过程是不可分割的，即是一条原语。

其中，lock有两种状态：当lock为FALSE时，表示该资源空闲；当lock为TRUE时，表示该资源正在被使用。 用TS指令管理临界区时，为每个临界资源设置一个布尔变量lock,由于变量lock代表了该资源的状态，故可把它看成一把锁。lock初值为FALSE，表示该临界资空闲。进程在进入临界区之前，首先用TS指令测试lock，如果其值为FALSE，则表示没有进程在临界区内，可以进入，并将TRUE值赋予lock，这等效于关闭了临界资源，使任何进程都不能进入临界区，否则必须循环测试直到TS为TRUE。

我们用伪代码描述TS实现互斥的过程：

我们用伪代码描述TS实现互斥的过程：

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

在整型信 量机制中的wait操作，只要是信 量S

2. 记录型信 量

记录型信 量机制是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信 量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程等待队列S.list，存放阻塞在该信 量的各个进程PCB。

记录型信 量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述如下：

在记录型信 量机制中，s一>value的初值表示系统中某类资源的数目，因而又称为资源信 量，对它的每次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个，因此描述为s一>value–;当S—valuelist中。可见，该机制遵循了“让权等待”准则。此时S->value的绝对值表示在该信 量链表中己阻塞进程的数目。对信 量的每次signal操作表示执行进程释放一个单位资源， 使系统中可供分配的该类资源数增加一个，故s一>value++操作表示资源数目加1。若加1 后仍是s–>valuelist链表中的第一个等待进程唤醒。如果S一>value的初值为1， 表示只允许一个进程访问临界资源，此时的信 量转化为互斥信 量，用于进程互斥。

3. AND型信 量

前面所述的进程互斥问题针对的是多个并发进程仅共享一个临界资源的情况。在有些应用场合，是一个进程往往需要获得两个或更多的共享资源后方能执行其任务。

假定现有两个进程A和B，它们都要求访问共享数据D和E,当然，共享数据都应作为临界资源。 为此，可为这两个数据分别设置用于互斥的信 量Dmutex和Emutex，并令它们的初值都是1。相应地，在两个进程中都要包含两个对Dmutex和Emutex的操作，即：

最后，进程A和B就将处于僵持状态。在无外力作用下，两者都将无法从僵持状态中解脱出来。我们称此时的进程A和B己进入死锁状态。显然，当进程同时要求的共享资源愈多时，发生进程死锁的可能性也就愈大。

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配采取原子操作方式： 要么把它所请求的资源全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。

为此，在wait操作中增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swart(Simultaneouswait）定义如下：

一般“信 量集”还有下面几种特殊情况：

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后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。

2.4.4 信 量的应用

1. 利用信 量实现进程互斥

为使多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信 量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于walt(mutex)和signal(mutex)操作之间即可。这样，每个欲访问该临界资源的进程在进入临界区之前，都要先对mutex执行wait操作，若该资源此刻未被访问，本次wait操作必然成功，进程便可进入自己的临界区，这时若再有其它进程也欲进入自己的临界区，由于对mutex执行wait操作定会失败， 因而此时该进程阻塞，从而保证了该临界资源能被互斥地访问。当访问临界资源的进程退出临界区后，又应对mutex执行signal操作，以便释放该临界资源。

利用信 量实现两个进程互斥的描述如下：

1. 设mutex为互斥信 量，其初值为1，取值范围为（-1，0，1)。当mutex=1时，表示两个进程皆未进入需要互斥的临界区；当mutex=0时，表示有一个进程进入临界区运行， 另外一个必须等待，挂入阻塞队列；当mutex=-1时，表示有一个进程正在临界区运行，另外一个进程因等待而阻塞在信 量队列中，需要被当前已在临界区运行的进程退出时唤醒。

2. 代码描述：

   由于S被初始化为0，这样，若P2先执行必定阻塞，只有在进程P1执行完S1；signal(S)；操作后使S增为1时，P2进程方能成功执行语句S2。

   同样，我们可以利用信另量按照语句间的前趋关系，写出一个更为复杂的可并发执行的程序：

   1. 管程的定义

   系统中的各种硬件资源和软件资源均可用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。因此， 可以利用共享数据结构抽象地表示系统中的共享资源，并且将对该共享数据结构实施的特定操作定义为一组过程。进程对共享资源的申请、释放和其它操作必须通过这组过程，间接地对共享数据结构实现操作。对于请求访问共享资源的诸多并发进程，可以根据资源的情况接受或阻塞，确保每次仅有一个进程进入管程，执行这组过程，使用共享资源，达到对共享资源所有访问的统一管理，有效地实现进程互斥。

   代表共享资源的数据结构以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块，我们称之为管程。管程被请求和释放资源的进程所调用。Hansan为管程所下的定义是：“一个管程定义了一个数据结构（临界资源）和能为并发进程所执行（在该数据结构上）的一组操作（对临界资源的使用），这组操作能同步进程和改变管程中的数据。”

   由上述的定义可知，管程由四部分组成：

   1. 管程的名称；
   2. 局部于管程的共享数据结构说明；
   3. 对该数据结构进行操作的一组过程；
   4. 对局部于管程的共享数据设置初始值的语句。

   下图是一个管程的示意图：

   实际上，管程中包含了面向对象的思想，它将表征共享资源的数据结构及其对数据结构操作的一组过程，包括同步机制，都集中并封装在一个对象内部，隐藏了实现细节。封装于管程内部的数据结构仅能被封装于管程内部的过程所访问，任何管程外的过程都不能访问它；反之，封装于管程内部的过程也仅能访问管程内的数据结构。所有进程要访问临界资源时，都只能通过管程间接访问，而管程每次只准许一个进程进入管程，执行管程内的过程，从而实现了进程互斥。

   管程是一种程序设计语言的结构成分，它和信 量有同等的表达能力，从语言的角度看，管程主要有以下特性：

   1. 模块化，即管程是一个基本程序单位，可以单独编译；
   2. 抽象数据类型，指管程中不仅有数据，而且有对数据的操作；
   3. 信息掩蔽，指管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用， 而管程中的数据结构以及过程（函数）的具体实现外部不可见。

   管程和进程不同：

   不同点	进程	管程
   数据结构的访问权限不同	定义的是私有数据结构PCB	定义的是公共数据结构，如消息队列等
   对数据结构的操作不同	由顺序程序执行有关操作	进行同步操作和初始化操作
   目的不同	设置进程的目的在于实现系统的并发性	管程的设置是解决共享资源的互斥使用问题
   工作方式不同	进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序一样被调用，故进程为主动工作方式	管程为被动工作方式
   执行情况不同	进程之间能并发执行	管程不能与其调用者并发
   特性不同	进程具有动态性，由“创建”而诞生，由“撤消”而消亡	管程是操作系统中的一个资源管理模块，供进程调用

   2. 条件变量

   在利用管程实现进程同步时，必须设置同步工具，如两个同步操作原语wait和signal。当某进程通过管程请求获得临界资源而未能满足时，管程便调用wait原语使该进程等待，并将其排在等待队列上。仅当另一进程访问完成并释放该资源之后，管程才又调用signal原语，唤醒等待队列中的队首进程。但是仅仅有上述的同步工具是不够的，考虑一种情况：当一个进程调用了管程，在管程中时被阻塞或挂起，直到阻塞或挂起的原因解除，而在此期间，如果该进程不释放管程； 则其它进程无法进入管程，被迫长时间的等待。为了解决这个问题，引入了条件变量 conditiona通常，一个进程被阻塞或挂起的条件（原因）可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问只能在管程中进行。

   管程中对每个条件变量都须予以说明，其形式为：conditionx,y；对条件变量的操作仅仅是wait和signal，因此条件变量也是一种抽象数据类型，每个条件变量保存了一个链表， 用于记录因该条件变量而阻塞的所有进程，同时提供的两个操作即可表示为x.wait和x.signal其含义为：

   1. x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其它进程可以使用该管程。
   2. 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马上被恢复执行。

   ---

   参考视频：https://www.bilibili.com/video/BV17h411B7yW23

   参考资料：《计算机操作系统(第四版)》—— 汤小丹等。

   声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！