进程同步

进程同步（英文名称:Process Synchronization）是指广义上的并发进程在执行序列中的相互制约，它包括进程的同步和互斥。从狭义上讲，它是指为完成某项任务而建立的两个或两个以上的流程因需要在某些岗位上协调其工作顺序而产生的相互等待限制。进程同步可以满足某些共享资源（如I/O设备）中进程独占访问的要求。

进程同步的实现需要遵循相应的机制和方法，其同步机制包括空闲产出、繁忙等待、受限等待和产出等待。进程同步的实现方法可以分为软件方法和硬件方法，其中硬件方法包括中断禁用和特殊机器指令，而软件方法可以依靠锁机制、信号量机制和管道机制，信号量机制可以细分为塑料信号量、记录信号量以及信号量和信号量集类型。

典型的同步问题包括生产者-消费者问题、读者-作者问题和哲学家进餐问题，这些问题可以通过不同的信号量机制来解决，生活中的实际问题可以直接或间接地参考这些经典问题来解决。

过程限制关系：在操作系统中，虽然进程可以独立运行，但它们之间也会相互制约。进程同步是操作系统管理共享资源和避免由并发进程引起的时间相关错误的一种方法。进程之间的关系可以表现为直接的相互制约（同步关系）和短暂的相互制约（互斥关系）。从广义上讲，进程同步被定义为并发进程在执行时序上的相互制约，它包括进程同步和进程互斥。

间接相互制约（相互排斥）：间接相互限制是指进程之间竞争独占资源（互斥资源）而造成的限制，即设置不允许两个进程同时使用某个资源，此时一个进程要求使用该资源，而该资源正在被另一个进程使用，因此该进程必须等待已占用该资源的进程释放该资源后才能使用。这种制约关系的基本形式是“过程-资源-过程”。这种约束关系源于多个同类进程需要互斥共享某些系统资源（如打印机），同类进程之间设置互斥以达到互斥访问资源的目的。

直接相互制约（同步）：同步关系是指需要在某些地方协调工作并相互等待和交换信息的伙伴流程之间的约束关系。也就是说，如果一个进程没有收到另一个进程提供的必要信息，它就无法继续运行。这种情况表明，两个进程需要在某个时候相互交换信息和通信。这种制约关系的基本形式是“过程-过程”。这种限制主要来自于进程之间的协作，在不同的进程之间设置同步以实现各种进程之间的同步。

一般来说，一个进程相对于另一个进程的运行速度是不确定的。也就是说，流程在异步环境中运行，但协作流程需要在某些关键点上协调工作。直接约束关系狭义上也叫进程同步。它是指为完成某项任务而建立的两个或多个流程之间的相互等待约束关系，因为它们需要在某些岗位上协调它们的工作顺序。

在运行过程中，一个进程一般会与其他进程共享资源，有些资源同一时间只能由一个进程使用。这种资源被称为关键资源。包括打印机和绘图仪在内的许多物理设备都是关键资源。为了保证关键资源的正确使用，关键资源的访问过程一般分为四个部分，即进入区、关键区、退出区和剩余区。无论是硬件关键资源还是软件关键资源，多个进程必须互斥地访问它。访问进程中关键资源的代码称为关键部分。每个进程的临界区代码可以不同。为了进入关键区域并使用关键资源，需要在进入区域中检查是否有可能进入关键区域；如果可以进入临界区，通常会设置相应的“访问临界区”标志，以防止其他进程同时进入临界区。这个代码叫做进入临界区。如果此时某个进程正在访问关键资源，则该进程无法进入关键区域。用于清除关键区域后的“访问关键区域”标志的部分代码称为出口区域。除了入口区域、关键区域和出口区域之外，其余区域是其他部分的代码。

为了实现进程的同步，必须遵守同步规则。用于实现进程间同步的工具称为同步机制。对于关键区域的操作，同步机制应遵循以下四个标准。

Idle yield:当临界区中没有进程时，表明临界资源处于空闲状态，应该允许请求进入临界区的进程立即进入自己的临界区，以有效地使用临界资源。

繁忙等待:当现有进程进入关键区域时，表明正在访问关键资源，因此其他试图进入关键区域的进程必须等待，以确保对关键资源的互斥访问。

有限等待:对于需要访问关键资源的进程，应保证在有限时间内进入相应的关键区域，进入关键区域的进程应在有限时间内完成其操作，释放资源并退出关键区域。

让路并等待:对于那些当前处于阻塞状态且无法进入临界区的进程，它们应该放弃占用CPU，以便其他进程可以获得CPU的使用权。

进程同步问题可以通过硬件方法或软件方法来解决。用于实现系统中进程之间同步和互斥的机制称为同步机制。同步机制很少单独采用软件方法，而使用硬件方法实现互斥的主要思想是使用一条指令来检查和修改标志，或者通过中断禁用来确保检查和修改作为一个整体进行，从而确保检查和修改操作不会中断。它具有应用范围广、简单和支持多个关键领域的优点。常见的同步机制有:锁机制、信号量机制和管道机制。

硬件模式

中断禁用：中断禁用使每个进程在进入临界区后立即关闭所有中断，并在离开临界区前重新打开中断。由于中断禁用，时钟中断也被禁止，因此CPU不会切换到另一个进程。这种赋予用户进程关闭中断的权利的方法有很大的缺点。一旦进程关闭中断，如果它不再打开中断，系统可能会被终止。

特殊机器指令：许多计算机（尤其是多处理器计算机）都有一个称为TSL（测试和设置锁定）的指令:TSLRX，Lock。它将内存字锁的内容读入寄存器RX，然后在地址单元中存储一个非零值。读取和存储数据的操作是不可分的，也就是说，在此指令完成之前，其他进程无法访问该单元。然而，使用TSL指令解决进程互斥进入临界区的问题可能会导致“忙等待”——如果一个进程已经进入临界区，后者将继续使用TSL指令进行测试并等待前者解锁。

软件模式

锁定机构：锁机制的基本内容是用变量w来表示一个关键资源的状态，w称为锁或锁位置。W=0表示资源可用；W=1表示资源正在被使用。在使用关键资源之前，进程需要检查锁变量的值。如果值为0，锁将被设置为1（已锁定）。如果值为1，它将返回到第一步重新检查锁变量的值。当进程使用完资源后，锁应该设置为0。它的标准原语是lock（w）和unlock（w）。

进程同步

虽然锁定机构简单方便，但其效率很低。当一个进程处于临界区时，其他想要进入临界区的进程必须不断地进行测试，从而处于繁忙的等待状态，导致处理器时间的浪费。

信号量机制：在操作系统中，信号量是一个代表资源的物理量，它是一个与队列相关的整数变量。它的值只能通过P和V操作来更改，操作系统使用它的状态来管理资源和进程。信号量同步机制是由荷兰计算机科学家Dijkstra于1965年首次提出的。其基本思想是使用标准原语操作来解决多个协作进程之间的信号同步。其标准原语包括wait（S）和signa（S）访问，也可以记录为“P操作”和“V操作”。常见的信号量机制有:整形信号量由资源号的整数S表示，并由基元wait和signal操作。信号量的值只能由两个标准原子操作wait和signal访问。

和旗语：一个进程在运行过程中经常需要申请多个共享资源。如果使用整数或记录信号量，进程可能会由于申请资源的顺序不正确而死锁。为了解决这个问题，引入了信号量同步机制。其基本思想是将进程在整个运行过程中所需的所有资源一次性分配给该进程，然后在该进程被使用后一起释放。只要有一种资源不能分配给该进程，所有其他可能分配给它的资源都不会分配给它。

信号量集类型：在记录信号量机制中，一次只能获得或释放一个单位的关键资源。如果一次需要N个关键资源，则需要N次等待操作，这是非常低效的。此外，在某些情况下，当资源量低于某个限制时，它将不会被分配。因此，在每次分配之前，必须测试资源的数量，看它是否大于其下限。基于以上两点，AND信号量机制可以扩展为广义的“信号量集”机制。Swait操作可以描述如下，其中s是信号量，d是所需值，t是下限。

在信号量机制中，由于每个想要访问关键资源的进程都必须有自己的同步操作等待和信号，因此大量的同步操作分散在每个进程中。它不仅给系统的管理带来了麻烦，而且由于同步操作的使用不当而导致系统死锁。

管程机构：为了解决信号量机制中存在的问题，1974年和1975年，Hansen和Hoare提出了管道机制，该机制集中管理分散在各个进程中的关键区域，并用数据结构抽象地表示系统中的共享资源。Pipeline定义了一个数据结构和一组可以由并发进程（在数据结构上）执行的操作，这些操作可以同步进程并更改管道中的数据。

管道的主要特征包括共享:一个进程通过调用管道的一个进程进入管道，管道中的移除进程可以由所有想要调用管道进程的进程共享。安全性:管道的本地数据变量只能由管道的进程访问，而不能由任何其他外部进程访问，并且管道的进程不能访问任何不属于其本地的变量。互斥:在任何时候，只有一个进程可以进入管道执行，其他任何调用管道的进程都将被阻塞，只能等待当前正在访问的进程退出管道。

使用管道实现进程同步时，必须设置同步工具，如两个同步操作原语wait和signal。当进程通过管道请求获得关键资源但未能满足这些资源时，管道调用wait原语使进程等待并将其放入等待队列。只有在另一个进程访问并释放资源后，管道才会再次调用signal原语来唤醒队列头进程。管道流程由四个部分组成，它们是管道流程的名称；共享数据的描述和说明；用于操作共享数据结构的一组过程；共享数据的初始化设置。

在现实生活中，许多事件需要相互同步。在多程序环境中，进程同步是一个非常重要和有趣的问题，吸引了许多学者对其进行研究，并由此产生了一系列经典的进程同步问题，其中比较经典的有生产者-消费者问题、读者-作者问题、哲学家进餐问题等。参考经典问题可以直接或间接解决生活中的实际问题。

问题描述

生产者-消费者问题，也称为缓冲区问题，是计算机操作系统中相互协作的并发进程之间的抽象。其核心内容是一组生产者流程和消费者流程。生产者负责生产产品，消费者负责消费产品。在它们之间设置一个具有n个缓冲区的缓冲池，供生产者进程和消费者进程共享。生产者的工作是生产产品并将其放入空缓冲区；消费者从包含用于消费的产品的缓冲器中取出产品。两人互相等待，互相唤醒。

在这个过程中，如果生产者进程没有空的缓冲区来放置产品，它将转入等待状态，直到消费者取走产品并将其唤醒；同样，消费者流程将转变为等待状态，因为在生产者放置产品后将其唤醒之前没有产品。

问题解决

以记录信号量为例，它使用互斥体来实现进程对缓冲区的互斥使用。此外，信号empty和full分别表示空缓冲区的数量和满缓冲区（即产品）的数量。