进程（线程）间相互作用

相关进程与无关进程

相关进程：在逻辑上具有某种联系的进程。

无关进程：在逻辑上没有任何联系的进程。

如果一个进程的执行不影响其他进程的执行，且与其他进程的进展情况无关，即它们是各自独立的，则说这些并发进程的相互之间是无关的。无关的并发进程一定没有共享的变量。

如果一个进程的执行依赖其他进程的进展情况，或者说，一个进程的执行可能影响其他进程的执行结果，则说这些并发进程是相关的。

与时间有关的错误

京城执行的速度是不能由进程自身控制的。对于相关进程来说，可能有若干并发进程同时使用共享资源，即一个进程一次使用未结束，另一个进程也开始使用，形成交替使用共享资源。

进程同步：值多个进程中发生的事件存在某种时序关系，必须协同动作，相互配合，以共同完成一个任务。

进程互斥：指由于共享资源所要求的排他性，进程间要相互竞争以使用这些互斥资源。

进程互斥

解决进程互斥的两种方法：

• 由竞争各方平等协商。
• 引入进程管理者，有管理者来协调竞争各方对互斥资源的使用。

临界资源：计算机系统中的需要互斥使用的硬件或软件资源，如外设、共享代码块、共享数据结构等。对各进程在对临界资源进程进行访问时，特别是进行写入或修改操作时，必须互斥的运行。

计算机系统中资源共享的程度分为三个层次：互斥、死锁和饥饿。

互斥：保证资源的互斥使用是指多个进程不能同时使用同一个资源，这是正确使用资源的最基本要求。

死锁：避免死锁是指多个进程互不相让，避免出现都得不到足够资源的情况，从而保证系统功能的正常运行。

饥饿：避免饥饿是指避免某些进程一直得不到资源或者得到资源的概率很小，从而保障系统内资源使用的公平性。

为了保证临界资源的正确使用，可把临界资源的访问过程分为四个部分：

1. 进入区：为了进入临界区使用临界值资源，在进入区要检查可否进入临界区；如果可以进入临界区，通常设置相应的”正在访问临界区“标志，以阻止其他进程同时进入临界区。
2. 临界区：进程中访问临界资源的一段代码。
3. 退出区：将”正在访问临界区“标识清除。
4. 剩余区：代码中的其他部分。

为了合理使用计算机系系统中的资源，在操作系统中采用的进程同步机制应遵循以下几条：

1. 空闲则入：任何同步机制都必须保证任何时间嗯最多只有一个进程位于临界区。当有程序位于临界区时，任何其他进程均不能进入临界区。
2. 忙着等待：当以有进程处于其他临界区时，后到达的进程只能在进入区等待。
3. 有限等待：为了避免死锁等现象的出现，等待进入临界区的进程不能无期限的”死等“。
4. 让权等待：因在进入区等待而不能进入临界区的进程，应释放处理机，转换到阻塞状态以使得其他进程有机会得到处理机的使用权。

进程互斥的软件方法

算法1：单标志算法

假设有两个进程Pi和Pj，设立一个公用整理变量turn，描述允许进入临界区的进程标识。每个进程都在进入区循环检查变量turn是否允许本进程进入。即turn为i时，进程Pi可进入，否则循环检查该变量，直到turn为本进程标识，在退出区修改允许进入进程标识，即进程Pi退出时，Pj的标识为j。

可以保证任何时刻最多只有一个进程在临界区。

缺点：强制轮流进入临界区，没有考虑进程的实际需要，容易造成资源利用不充分。

算法2：双标志、先检查算法

修改临界区标志的设置，设立一个标志数组flag[]，描述各进程是否在临界区，初始值均为FALSE.

在进入区的操作为：先检查，后修改。即在进入区像检查另一个进程是否在临界区，不在时修改本进程在临界区的标志，表示本进程在临界区，在退出区修改本进程在临界区的标志，表示本进程不在临界区。

算法2的优点是克服了算法1的缺点，两个进程不用交替进入，可连续使用。但由于使用多个标志，算法有产生新的问题，即进程Pi和Pj可能同时进入临界区，从而违反了最左只有多个进程在临界区的要求。

算法3：双标志、后检查算法

一是保证检查和修改操作间不会出现间隔。 一是修改标志含义。 算法3可防止两个进程同时进入临界区，但它的缺点是Pi和Pj可能都进入不了临界区。在修改本进程标志flag之后和检查对方flag之间有一段时间间隔，这个间隔导致两个进程都想进入临界区，从而在检查对方标志时不通过。

算法4：先修改、后检查、后修改者等待算法

结合了算法3和1，标志flag[i]表示进程i想进入临界区，标志turn表示同时修改标志时要在进入区等待的进程标识。

在进入区先修改后检查，通过修改统一标志turn来描述标志修改的先后；检查对方标志flag，如果对方不想进入临界区则自己进入；否则在检查标志turn，由于标志turn中保存的是较晚的一次赋值，则交往修改标志的进程等待，较早的修改标志的进程进入临界区。

实现了同步机制要求的四条准则中的前两条：空闲则入、忙着等待。

进程互斥的硬件方法

主要思路：使用一种指令完成读和写的两个操作，因而保证读操作与写操作不被打断，依据采用的指令的不同，硬件方法分成TS指令和Swap指令。

TS（Test-and-Set）指令

TS指令的功能是读出指定标识后把该标志设置为TRUE。

每个临界资源设置一个公共布尔变量lock，表示资源两种状态：TURE表示正被占用，FALSE表示空闲，初始值为FALSE。

有进程在临界区时，重复检查，直到其他进程退出时检查通过，所有要访问临界资源的进程的进入区和退出区代码是相同的。

Swap指令

利用Swap指令实现的进程互斥算法是，每个临界资源设置一个公共布尔变量lock，初值为FALSE，每个进程设置一个私有布尔变量key，用于与lock间的信息交换。在进入区利用Swap指令交换lock和key的内容，然后检查key的状态，有进程在临界区时，重复交换和检查过程到其他进程推出啊是检查通过。

优点：

1. 适用范围广：适用于任意数目的进程，在单处理器和多处理器黄健中完全相同。
2. 简单：硬件方法的标志设置简单，含义明确，容易验证其正确性。
3. 支持多个临界区：在一个进程内有多个临界区是，只需为每个临界区设立一个变量。

缺点：

1. 进程在等待进入临界区时，要耗费处理机时间，不能实现”让权等待“。
2. 由于进入临界区的进程是从等待进程中随机选择的，有的进程可能一直选不上，从而导致”饥饿“。

信号量

信号量机制所使用的P、V原语就来自荷兰语test和increment。每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中存放的是阻塞在该信号量的各个进程的标识。

信号量只能通过初始化和标准的原语来访问。

P、V原语的执行，不受进程调度和执行的打断，从而很好地解决了原语操作的整体性。信号量的初始化可指定一个非负整数数值，表示空闲资源总数；若为负值，其绝对值表示当前等待临界区的进程数。

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

P原语所执行的操作可用下面函数wait（s）来描述。
wait(s){
 --s.count; //表示申请一个资源
 if(s.count<0){ //表示没有空闲资源
 调用进程进入等待队列s.queue;
 阻塞调用进程;
 }
}
V原语所执行的操作可用下面函数signal(s)描述。
signal(s){
 ++s.count; //表示释放一个资源
 if(s.count <= 0){ //表示有进程处于阻塞状态
 从等待队列s.queue中取出头一个进程P；
 进程P进入就绪队列;
 }
}

在使用信号量进行共享资源访问控制时，必须成对使用P和V原语。遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放给其他等待的进程。P、V原语的使用不能次序错误、重复或遗漏。

利用操作系统提供的信号量机制可实现进程间的同步，即所谓的前驱关系。

前趋关系是指并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成执行。可为每个前趋关系设置一个互斥信号量S12，其初值为0.这样，只有在P1执行到V（S12）后，P2才会结束P（S12）的执行。

经典的进程同步问题

Dijkstra将同步问题抽象成一种“生产者-消费者关系”。

简单生产者-消费者问题

设有一个生产者进程P，一个消费者进程Q，他们通过一个缓冲区联系起来。缓冲区只能容纳一个产品，生产者不断的生产产品；而消费者则不断从缓冲区中取出产品，并消费掉。 生产者-消费者同步问题的解决方案如下：

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

生产者进程P:
while(true){
 P(empty);
 生产一个产品;
 送产品到缓冲区;
 V(full);
};
消费者进程Q：
while(true){
 P(full);
 从缓冲区去产品;
 V(empty);
 消费产品;
};

产品生产出来之后立即往缓冲区中存放产品，因为刚开始时缓冲区是空的，一定可以存放一个产品。

多个生产者-消费者问题

设有多个生产者进程P1，P2，……, Pn，若干个消费者进程Q1，Q2，Q3，……，Qm，他们通过一个唤醒缓冲池联系起来，该环形缓冲池由K个大小相等的缓冲区组成，每个缓冲区能容纳一个产品，生产者每次往空缓冲区送一个产品；消费者每次从缓冲区取出一个产品。生产者进程不断地生产产品并把他们放给缓冲池内，消费者进程不断的从缓冲池内取出产品并消费之。

当整个缓冲池全满时，出现供大于求的现象。当整个缓冲池全空时，出现供不应求的现象。

环形缓冲池是临界资源，因为生产者和消费者都需要使用它。

1. 同步问题：P进程不能往“满”的缓冲区中放产品，设置信号量empty，初值为k，用于指示缓冲池中空缓冲区数目。Q进程不能从“空”的缓冲区中取产品，设置信号量full，初值为0，用于指示缓冲池中满缓冲区数目。
2. 互斥问题：设置信号量mutex，初值为1，用于实现临界区（环形缓冲区）的互斥。

算法：

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

P1，P2，......,Pn;
i:=0;
while(true){
 生产产品;
 P(empty);
 P(mutex);
 往Buffer[i]中放产品;
 i:=(i+1) mod k;
 V(mutex);
 V(full);
};
Q1,Q2,......,Qm;
j:=0;
while(true){
 P(full);
 P(mutex);
 从Buffer[i]中存放产品;
 j:=(j+1) mod k;
 V(mutex);
 V(empty);
 消费产品;
}

读者-写者问题

假定有某个共享文件F，系统允许若干个进程对文件F进行读或写，这里要把读文件的进程称为读者，要把写文件的进程称为写者.

多个进程可以同时读文件F；

1. 任一个进程在对文件F进行写时，按规定每次只允许一个进程执行写操作；
2. 当有进程正在读文件时不允许任何进程去写文件。
3. 当有多个读者与写者都需要读写文件时，按规定每次只允许一个进程执行写操作，且在有进程执行写的时候不允许进程读文件。

同步与互斥的综合应用

例1 路口单双号交通管制

Check：指示可否在车辆号码识别区中进入一辆汽车，由于只能进入一辆，其初值为1.

Ddd：指示汽车号码是否为奇数，其初值为0，表是不是奇数。

Lven：指示汽车号码是否为偶数，其初值为0，表示不是偶数。

例2 物流系统中的物品分拣问题

问题

从沿长江一线进入枢纽的集装箱，要从这里直接吊装到上海至旧金山的定期集装箱班轮上。

而从沪杭高速公路上进入枢纽的集装箱，要从这里还转到专门在京沪高速公路上行驶的集装箱运输箱上。

该中转枢纽的场地每次只能接受一个方向来的同一批次的集装箱。

分析

长江一线进入的集装箱卸货是一个生产者，从沪杭高速公路上进入的集装箱卸货是第二个生产者。

这两个生产者都要使用中转枢纽的场地，由于该场地每次只能接受一个方向来的同一批次的集装箱，所以长江一线生产者和沪杭高速公路生产者必须互斥。

Site：指示能否在中转的枢纽的场地上卸下集装箱。

Arrive_Y:指示场地上的集装箱是否来自长江。

Arrive_H:指示场地上的集装箱是否来自沪杭。

说明

由于Site初值为1，P(Site)起到互斥作用，无论谁先卸下了集装箱，另一个物流方向上不能在卸货，只能等待.

进程“旧金山班轮装货”和“北京运输车装货”在装完集装箱之后，都调用V(Site),发出可以接受新集装箱的消息。

Site信号量既作为互斥的信号量，又起着同步信号量的作用。

管程

管程的提出

采用P、V同步机制来编写并发程序，对于共享变量及信号量的操作将被分散于各个进程中。

缺点：

1. 对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序。
2. 程序不利于修改和维护，局部性很差，所以任意一组变量或一段代码的修改都可能影响全局。
3. 正确性难以保证，保证一个复杂系统没有逻辑错误是很难的。

管程的概念及组成

一个管程是一个由过程、变量及数据结构等组成的集合，他们组成一个特殊的模块或软件包。进程可在任何需要的时候调用管程中的过程，但他们不能在管程之外声明的过程中直接访问管程内的数据结构。

一个管程由四个部分组成：管程名称、共享数据的说明，对数据进行操作的一组过程和对共享数据赋初值的语句。

管程能保障共享资源的互斥执行，即一次只能有一个进程可以在管程内活动。

三个特性：

1. 模块化： 一个基本程序单位，可以单独编译。
2. 抽象数据类型： 管程是一种特殊的数据类型，其中不仅有数据，而且还有对数据进行操作的代码。
3. 信息隐蔽： 管程是半透明的，管程中的外部过程（函数）实现了某些功能，至于这些功能怎么样实现的，其外部则是不可见的。

管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接的访问管程中的共享变量，为了保证管程共享变量的数据完整性，规定管程互斥进入；管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作。

任意时刻管程中只能有一个活跃进程，这个特性使管程能有效地完成互斥。当一个进程调用管程过程时，该过程中的前几条指令将检查在管程中是否有其他的活跃进程，如果有，调用进程将被挂起，直到另一个进程离开管程将其唤醒，如果没有活跃进程在使用管程，则该调用进程可以进入。

管程中的条件变量

解决方法是引入条件变量以及相关的两个操作：wait和signal，当一个管程过程发现它无法继续运行时（例如：生产者发现缓冲区满），他会在某个条件变量（如full）上执行wait操作，该操作导致调用进程自身阻塞，并且还将另一个以前等在管程之外的进程调入管程，另一个进程，比如消费者，可以唤醒正在睡眠的伙伴进程，这可以通过对其伙伴正在等待的一个条件变量执行signal完成。

wait操作必须在signal之前，这条规则使得实现简单了许多，实际上这不是一个问题，因为需要时，用变量很容易跟踪每个进程的状态。

当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权每当一个进入管程的进程执行唤醒操作（如P唤醒Q）时，管程中便存在两个同时处于活动状态的进程。

处理方法：

1. P等待Q继续，直到Q退出或等待（Hoare提出）。
2. Q等待P继续，直到P等待或退出。
3. 规定唤醒为管程中最后一个可执行的操作。

当一个进程试图进入一个已被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当由一个进程等待队列。在管程内部，由于执行唤醒操作，可能会出现多个进程等待队列，因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列，它的优先级应当高于入口等待队列的优先级signal(c)；如果c链为空，则相当于空操作，执行此操作的进程继续；否者幻想第一个等待者，执行此操作的进程的PCB入紧急等待队列的尾部。

用管程解决生产者-消费则问题

Pthread中的互斥与同步

Pthread提供了可用于线程同步与互斥的机制，他们是互斥量和条件变量，两者结合起来使用已达到管程的效果。

互斥量及相关函数

解决线程互斥问题的基本思想是使用一个可以加锁和解锁的互斥量来保护临界区。一个进程如果想要进入临界区，他首先尝试锁住相关的互斥量。如果互斥量没有加锁，那么这个线程可以立即进入，并且该互斥量被自动锁定以防止其他进程进入。如果互斥量已经被加锁，则调用线程被阻塞，直到该互斥量被解锁。如果多个线程在等待同一个互斥量，当它被解锁时，这些等待的线程中只有一个得到互斥量并将其锁定。

条件变量及相关函数

除互斥量之外，Pthread提供了一种同步机制：条件变量，它允许线程由于一些为满足的条件而被阻塞。

让一个线程锁住一个互斥量，如果该线程不能获得它期望的结果时，则等待一个条件变量；最后另一个线程会向它发出信号，使它可以继续执行。

通信进程

P、V操作是一类低级通信原语，不能承担进程间大量信息的交换任务。

解决进程之间的大量信息通信问题有三个方案：共享内存、消息机制以及通过共享文件进行通信，即管道通信。他们不仅要保证相互制约的进程之间的正确关系，还要同时实现进程之间的信息交换。

共享内存

在相互通信的进程之间设有一个公共内存区，一组进程向该公共内存中写，另一组进程中的读写互斥问题。操作系统一般只提供要共享的内存空间，而处理进程间在公共内存中的互斥关系则是程序开发人员的责任。

消息机制

消息机制是用于进程间同行的高级通信原语之一。进程在运行过程中可能需要与其他的进程进行信息交流，于是进程通过某种手段发出自己的信息或接收其他进程发来的消息。这种方式类似于人们通过邮政局收发邮件来实现交换信息的目的。

信息缓冲通信

基本思想：根据“生产者-消费者”原理，利用内存中共用消息缓冲区实现进程之间的信息交换。 内存中开辟了若干信息缓冲区，用于存放消息。

一个进程可以给若干个进程发送消息，反之，一个进程可以接受不同进程发来的消息，显然，进程中关于消息队列的操作是临界区，当发送进程正往接收进程的消息队列中添加一条消息时，接收进程不能同时从该消息队列中取出信息；反之也一样。

消息缓冲区通信机制包括以下几个内容：

1. 消息缓冲区：这是一个由消息长度、消息正文、发送者、消息队列指针组成的数据结构。
2. 消息队列首指针：m_q,一般存在PCB中。
3. 互斥信号量m_mutex,初始值为1.
4. 同步信号量m_syn,初始值为0.
5. 发送消息原语send(receiver, a)。
6. 接收信息原语receive(a).

信箱通信

以发送信件以及接收回答新建为进程间通信的基本方式。

当一个进程希望与另一个进程通信时，就创建一个链接两个进程的信箱，发送进程把信件投入信箱，而接收进程可以在任何时刻取走信件。

一个新鲜的结构可有“信箱说明”和“信箱体”两部分组成。

有如下的数据结构：

• 可存信件数 是在设立信箱时预先确定的，表明信箱的容量大小。
• 已有信件数 指出信箱中已有信件的数量。
• 可存信件的指针 指示当前可存入一封信的位置。该指针的初始值为指向可存第一封信的位置。

为了实现信箱通信，必须提供相应的原语，如创建信箱原语、撤销信箱原语、发送信箱原语和接收信箱原语等。

表示的是一个发送者和一个接收者单向通信的例子，在进程A发送信件之间，信箱中至少应该有空位置，可以存放信件，同样，在进程B接收信件之前，信箱中应该有信件，否则进程应该等待。

好处：发送方和接收方不必直接建立联系，没有处理时间上的限制。发送方可以在任何时间发信，接收方可以在任何时间收信。

由于发送方和接收方都是独立工作的，如果发的快而接受的慢，则信箱会溢出。相反，如果发的慢而收的快，则信箱会变空。

规则：

1. 若发送信件时信箱已经满了，则发送进程应被置为“等信箱”状态，直到信箱有空时才被释放。
2. 若取信件时信箱中无信，则接收进程应被置成“等信件”状态，直到有信件时才被释放。

管道通信

管道通信首先出现在UNIX操作系统中。

管道：就是连接在两个进程之间的一个打开的共享文件，专用于进程之间进行数据通信。发送进程可以源源不断的从管道一端写入数据流，每次写入的信息长度是可变的，接受进程在需要时可以从管道的另一端读出数据，读出单位长度也是可变的。管道通信的基础是文件系统。

在对管道文件进行读写操作的过程中，发送进程和接收进程都要实施正确的同步和互斥，以确保通信的正确性，管道通信机制中的同步与互斥都由操作系统自动进行，对用户是透明的。

具有传送数据量大的优点，但是通信速度比较慢。