操作系统中的进程同步与进程通信

进程同步机制

背景介绍

多道程序环境

多道程序设计技术是在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制下，相互穿插运行，两个或两个以上程序在计算机系统中同处于开始到结束之间的状态, 这些程序共享计算机系统资源。与之相对应的是单道程序，即在计算机内存中只允许一个的程序运行。

背景介绍

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关系，引入了进程同步的概念。

而制约关系也分为：直接相互制约（同步）和间接相互制约（互斥）。

直接相互制约关系是指，为了完成某个目而建立的两个或多个进程，这些进程需要在某些位置协调工作次序、需要信息传递而产生的制约关系，直接相互制约关系是由于进程间的相互合作而引起的。

间接相互制约关系是指当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。间接制约关系是由于进程之间共享临界资源而引起的。

临界资源和临界区

虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所使用，我们把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，如果变量、数据等都可以被若干进程共享，也属于临界资源。 而进程用于访问临界资源的代码就被称为临界区。我们把程序中，临界区之后的代码称为剩余区。

互斥和同步

互斥，又称间接制约关系，是指系统中的某些共享资源，一次只允许一个线程访问。当一个线程正在访问该临界资源时，其它线程必须等待。

同步，又称直接制约关系，是指多个线程（或进程）为了合作完成任务，必须严格按照规定的某种先后次序来运行。

基本解决方法

遵循一让三等待原则

空闲让进:当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效利用临界资源。

忙则等待：当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程都必须等待，以保证对临界资源的互斥访问。

有限等待：对要求访问的临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。

让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免陷入"忙等"状态

软件同步机制

对进程的互斥访问，逻辑上可以分为

1.进入区加锁，其它进程不能进入

2.临界区访问临界资源

3.退出区释放锁，后其它进程可访问

4.剩余区其他操作

进入区和退出区是负责实现互斥的代码段。同步算法一般在1和3的位置做文章。

单标志法

思想：该算法设置一个公用整型变量 turn，用于指示被允许进入临界区的进程编号，比如 turn = 0 ，则允许P0进程进入临界区。该算法可确保每次只允许一个进程进入临界区。

# P0进程
while turn != 0:  continue  # 等待：确认是否能进入临界区，如果turn不等于0就一直循环等待。
section = 100  # 当turn=0时，说明允许P0进入临界区了，就开始使用临界资源 section了。
...  # 基于临界资源section的一波操作
turn = 1  # 设置turn=1，将临界资源度让给P1进程，P0进程退出临界区
...  # 剩余区

# P1进程
while turn != 1:  continue  # 等待：确认是否能进入临界区，如果turn不等于1就一直循环等待。
section = 200  # 当turn=1时，说明允许P1进入临界区了，就开始使用临界资源 section了。
...  # 基于临界资源section的一波操作
turn = 0  # 设置turn=0，将临界资源度让给P0进程，P1进程退出临界区
...  # 剩余区

两个进程必须交替进入临界区，如果某个进程不再进入临界区了，那么另一个进程也不能再进入临界区（违背“空闲让进”）这样很容易造成资源利用的不充分。例如，P0退出临界区了，turn被改成了1，但是P1一直不进入临界区，不把turn改回成0，P0就永远用不了这个临界资源了。空着但是用不了，就是违背了“空闲让进”原则。

双（多）标志法先检查

思想：设置了一个数据flags[i], 如果第i个值为FLASE，则表示第i个进程Pi未进临界区，如果值为TRUE，表示Pi进程进入临界区。

该算法的基本思想是在每一个进程访问临界区资源之前，先查看一下临界资源是否正在被访问，遍历flag，没有任何一个True出现，则代表临界资源没有被访问，当前进程可以进入临界区使用该临界资源。若被访问，即遍历flag出现了True，该进程需等待。

while True  # 等待阶段，查看一下临界资源是否正在被访问。
	is_occupation = False # 默认没有被占用
	for flag in flags:
        if flag == True:
            is_occupation = True
            break
    if not is_occupation:
        break  # 跳出while循环
# 完成等待，进入临界区。
flag[i] = True  # 设置进程i的flag为True，防止其他进程使用该临界资源，形成互斥。
section = 100  # 开始使用临界资源 section。
...  # 基于临界资源section的一波操作
flag[i] = False  # 设置进程i的flag为False，宣布该临界资源的使用已经结束，Pi进程退出临界区
...  # 剩余区

# 其他进程的代码一样

当 flag 只负责监控两个进程（i和j）的占用情况时，代码如下：

# pi进程
while flag[j]： # 等待，确认另一个进程j没有使用该临界资源  1
# 完成等待，进入临界区。
flag[i] = True  # 设置进程i的flag为True，防止其他进程使用该临界资源，形成互斥。 3
section = 100  # 开始使用临界资源 section。
...  # 基于临界资源section的一波操作
flag[i] = False  # 设置进程i的flag为False，宣布该临界资源的使用已经结束，Pi进程退出临界区
...  # 剩余区

# pj进程
while flag[i]： # 等待，确认另一个进程i没有使用该临界资源  2
# 完成等待，进入临界区。
flag[j] = True  # 设置进程j的flag为True，防止其他进程使用该临界资源，形成互斥。 4
section = 200  # 开始使用临界资源 section。
...  # 基于临界资源section的一波操作
flag[j] = False  # 设置进程j的flag为False，宣布该临界资源的使用已经结束，Pj进程退出临界区
...  # 剩余区

优点：不需要交替进入，可连续使用；缺点：pi和pj可能同时进入临界区，按序号①②③④执行，会同时进入临界区(违背”忙则等待“)。即在检查对方flag之后和切换自己的flag之间有一段时间，结果都检查通过，同时修改了自己的flag，开始使用同一块本应该互斥的共享资源。这里问题出在检查和修改操作不能一次进行。

双（多）标志法后检查

思想： 双（多）标志法先检查，先检测其他进程对临界资源的占用情况（状态标志），全部为False之后，再置自己标志为True，完成对临界资源的占用。但是，由于在检测和设置这两个步骤之间存在时间差，可能会有另一个进程同样完成检测和设置，这会造成两个进程分别检测后。同时进入临界区。为此，算法三采用先设置自己标志为True，再检测其余进程对临界资源的占用情况，状态，若有任何一个进程的标志为True，即正在使用临界资源，则该进程等待，否则进入临界区，使用该临界资源。

# Pi进程
flag[i] = True  # 设置进程i的flag为True，防止其他进程使用该临界资源，形成互斥。
while True  # 等待阶段，查看一下临界资源是否正在被访问。
	is_occupation = False # 默认没有被占用
	for index in range(len(flags)):
        flag = flags[flag]
        if flag == True and index != i:
            is_occupation = True
            break
    if not is_occupation:
        break  # 跳出while循环
# 完成等待，进入临界区。
section = 100  # 开始使用临界资源 section。
...  # 基于临界资源section的一波操作
flag[i] = False  # 设置进程i的flag为False，宣布该临界资源的使用已经结束，Pi进程退出临界区
...  # 剩余区

# 其他进程的代码一样

当 flag 只负责监控两个进程（i和j）的占用情况时，代码如下：

# pi进程
flag[i] = True  # 设置进程i的flag为True，防止其他进程使用该临界资源，形成互斥。
while flag[j]： # 等待，确认另一个进程j没有使用该临界资源
# 完成等待，进入临界区。
section = 100  # 开始使用临界资源 section。
...  # 基于临界资源section的一波操作
flag[i] = False  # 设置进程i的flag为False，宣布该临界资源的使用已经结束，Pi进程退出临界区
...  # 剩余区

# pj进程
flag[j] = True  # 设置进程j的flag为True，防止其他进程使用该临界资源，形成互斥。
while flag[i]： # 等待，确认另一个进程i没有使用该临界资源
# 完成等待，进入临界区。
section = 200  # 开始使用临界资源 section。
...  # 基于临界资源section的一波操作
flag[j] = False  # 设置进程j的flag为False，宣布该临界资源的使用已经结束，Pj进程退出临界区
...  # 剩余区

评价：当两个进程几乎同时想要进入临界区时，他们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态(执行while语句)，发现对方也要进入临界区，两个进程就会互相谦让，结果谁也进不了临界区，违背了空闲让进原则，从而导致"饥饿"现象。

#### Peterson's Algorithm

这个算法的关键是，同时使用了 flags 和 turn 两个变量，其中 ture 为共享变量，任何时刻只有一个值。每个进程上来就是先向世界宣布自己想访问临界区，但是，虽然这么想，它还是谦虚的认为，这一轮我不抢，让对方先来！即，把turn设置为对方的。而能让 Pi 空等的条件是，对方真的也想占用该临界资源，且确实是对方的turn。只要两个条件任何一个不满足，Pi就大方的进入了它的临界区，使用了这个临界资源，用完了就修改自己的状态标志（flags），向其他进程宣布，我用完啦。谢谢大家。

# Pi进程
flag[i] = True  # 设置进程i的flag为True，防止其他进程使用该临界资源，形成互斥。
turn = j
while True  # 等待阶段，查看一下临界资源是否正在被访问。
	is_occupation = False # 默认没有被占用
	for index in range(len(flags)):
        flag = flags[flag]
        if flag == True and index != i and turn = j:
            is_occupation = True
            break
    if not is_occupation:
        break  # 跳出while循环
# 完成等待，进入临界区。
section = 100  # 开始使用临界资源 section。
...  # 基于临界资源section的一波操作
flag[i] = False  # 设置进程i的flag为False，宣布该临界资源的使用已经结束，Pi进程退出临界区
...  # 剩余区

# 其他进程的代码一样

当 flag 只负责监控两个进程（i和j）的占用情况时，代码如下：

# pi进程
flag[i] = True  # 设置进程i的flag为True，防止其他进程使用该临界资源，形成互斥。
turn = j
while flag[j] and turn == j： # j真的想用，且turn是j的，等待
# 完成等待，进入临界区。
section = 100  # 开始使用临界资源 section。
...  # 基于临界资源section的一波操作
flag[i] = False  # 设置进程i的flag为False，宣布该临界资源的使用已经结束，Pi进程退出临界区
...  # 剩余区

# pj进程
flag[j] = True  # 设置进程j的flag为True，防止其他进程使用该临界资源，形成互斥。
turn = i
while flag[i] and turn == i： # i真的想用，且turn是i的，等待
# 完成等待，进入临界区。
section = 200  # 开始使用临界资源 section。
...  # 基于临界资源section的一波操作
flag[j] = False  # 设置进程j的flag为False，宣布该临界资源的使用已经结束，Pj进程退出临界区
...  # 剩余区

仔细看，这个和算法三相比，就多了一个绅士的动作，加一个turn为对方的条件，并且修改了等待的条件。

因此，我们看，饥饿是如何解决的：首先，两个人都宣布了自己要访问临界区，大家坦陈相待，很酷。又加上一条，承认对方的turn。 OK，很美好。那么判断的时候，需要满足两个条件自己才等待。算法三中，饥饿发生的情况是：互相检查对方的状态（flags）时，发现对方都为True，flags[i] 和 flags[j] 都是True，就会相互等待，进入饥饿状态。
现在也假设这么干，无疑，flags[i] 和 flags[j] 都是True，但是turn是共用的，Pi设置turn=j，让Pj进入这轮，Pj呢，也很绅士，让turn=i，让Pi先行，无论怎样，任何时刻，turn 只能有一个值，要么是 i，要么是 j，因此，总有一个while的将会结束，因此，不会再有饥饿。简而言之，利用 flag 解决临界资源的互斥访问，而利用 turn 解决“饥饿”现象。

硬件同步机制

许多计算机提供一些特殊的硬件指令，允许对一个字中的内容进行检查和修改，或者是对两个字的内容进行交换等。实际上,对临界区进行管理时，可以将标志看做一个锁，初始时，锁打开，“锁开”进入，"锁关"等待。每次进程要进入临界区时，检测锁。打开时，进入；关闭时，等待。

关闭中断

思想：在进入临界区之前关闭操作系统中断，直到完成之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会打发生进程或者线程切换。

中断是指程序执行过程中，遇到急需处理的事件时，暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程。操作系统是“中断驱动”的；换言之，中断（广义）是激活操作系统的唯一方式，中断有广义和狭义之分，上述中断时指广义的中断。
狭义的中断来源于处理器之外的中断事件，即与当前运行指令无关的中断事件，如I/O中断、时钟中断、外部信号中断等异常（来源于CPU内部的中断事件，和狭义共同构成广义的中断）指当前运行指令引起的中断事件，如地址异常、算术异常、处理器硬件故障等系统异常与硬件无关，系统异常指执行陷入指令而触发系统调用引起的中断事件，如请求设备、请求I/O、创建进程等

缺点：

滥用关中断权利可能会导致严重的后果
关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；
关中断方法也并不适用于多CPU系统，因为在一个处理机上关中断并不能防止其他进程在其他处理器上执行相同的临界段代码，获得相同的临界资源。

Test-and-Set指令（自旋锁机制）

目的：为了实现保护共享资源，任何时刻只能有一个保持者。即只有一个进程可以获得锁。

互斥锁机制下，如果资源被占用，资源申请者就会进入睡眠状态（即让权等待，要释放处理机）。

但是对自旋锁机制（Test-and-Set指令），如果资源被占用，资源申请者（进程）会继续一直循环在那里看自旋锁的保持者是否释放了锁（即忙等，不释放处理机和其他资源）。

借助一条硬件指令——"测试并建立"指令TS以实现互斥的方法，TS指令是原子操作（原子操作在执行的时候是不可中断的），即执行过程不可分割。用TS指令管理临界区时，为每个临界资源设置一个布尔变量lock，lock初值为FALSE，表示该临界资源空闲。进程在进入临界区之前，首先用TS指令测试lock，如果其值为FALSE，则表示没有进程在临界区内，可以进入，并将TRUE值赋予lock，这等效于关闭临界资源.如果其值为TRUE，则重复检查，直到占用这个临界资源的进程退出。

boolean TS (boolean *lock){
    boolean old;
    old = *lock;
    *lock = TRUE;
    return old;
}
while TS(&lock);
临界区
lock = false;

利用Swap指令实现互斥

swap指令时交换两个字的内容,也是一个原子操作：

void swap (boolean *a, boolean *b){
    boolean temp;
    tamp = *a;  // lock
    *a = *b
    *b = temp;
}

用Swap指令可以简单有效的实现互斥，方法是为每一个临界资源设置一个全局的boolean变量lock，其初值为false，在每个进程中再利用一个局部变量key，初值为true。

key = true;
while(key != false);  // 等待，直到某一刻，lock为False，代表该临界资源不被占用，此时，key和lock互换，key也变成了false，结束等待，进入临界区。
	swap(&lock, &key);  // 互换 key 和 lock 的值
... // 临界区
lock = false;
... // 剩余区

缺点：

当临界资源忙碌时其他访问进程必须不断测试处于一种忙等状态不符合让权等待 造成处理机时间的浪费，同时很难用于解决复杂的进程问题。从等待的进程中随机选取可能会会使得有些进程“饥饿”。

信号量机制

成熟的进程同步机制，被广泛的应用于各种OS中。

信号量机制是一种功能性比较强的机制，可以用来解决互斥与同步的问题。Dijkstra把整形信号量定义为一个用于表示资源数目的整形量 s，这个整形量 s 它只能被两个标准的原语wait(S) 和 Signal(S) 来访问，也可以记做 “P操作”(通过) 和 “V操作”(释放)。

wait()/P() 获取/申请资源，申请不成功，就wait，所以叫做wait函数。
signal()/V() 释放资源，

wait 和 signal 都属于原子操作。当我们需要利用信号量实现同步时，需要将资源值设置为0。只有 p(S) 之后，才能 v(S)。如果要实现互斥的话，则可以将资源值设置为1。（注：线程间的同步策略，也可以由信号量机制来实现。）

整型信号量

使用整形信号量控制，一直处于忙等状态，未遵循“让权等待” 的原则。

wait(S){ // P(s) 获取/
	while(S<=0);
	S‐‐;
}
signal(S){  // V(s) 释放
	S++;
}

wait 操作中，只要信号量S<=0，就会不断地测试。因此，该机制并未遵循“让权等待” 的准则，而是使进程处于“忙等”的状态。

记录型信号量

引入进程链表，实现了让权等待。

typedef struct{
    int value; //资源数量
    struct process *L; //进程链表
} semaphore;

void wait (semaphore S) { //相当于申请资源
    S.value‐‐;
    if(S.value<0) {
        add this process to S.L;
        block (S.L); // S.value<0表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，同时放弃处理机。
    }
}

void signal (semaphore S) { //相当于释放资源
    S.value++;
    if(S.value<=0){
	    remove a process P from S.L;
    	wakeup(P);//将第一个等待进程唤醒。
    }
}

记录型信号量是不存在“忙等”现象的进程同步机制。除了需要一个用于代表资源数目的整型变量 value 外，再增加一个进程链表 L ，用于链接所有等待该资源的进程，实现了让权等待。

And型信号量

允许一次对多种临界资源的单一个单位的获取

AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中增加了一个“AND”条件，故称为AND型信号量，或者称为同时 wait 操作，即 simultaneous wait，Swait() 和 Ssignal() 定义如下：

Swait(S1,S2.…, Sn){
	while(TRUE){
		if(Si>=1&&..…&& Sn>=1){ 
			for(i=1;i<=n;i++) Si--; 
			break;
         }
         else{
		 // place the process in the waiting queue associated with the first Si found with Sicl, and set the program count of this process to the beginning of Swait operation 将进程置入等待队列，并将该进程的程序指针指向Swait操作的开头。
	}
}

Ssignal(S1,S2,.…, Sn){
	while(TRUE){
		for(i=l;i<=n;i++){
			Si++; 
			// Remove all the process waiting in the queue associated with Si into the ready queue  将与临界资源Si有关的所有进程移出等待队列，移入就绪队列。
		}
	}
}

从机制的原理来看，And型信号量机制可以解决死锁问题。

信号量集

允许一次对多种临界资源的多个单位的获取

在前面所述的记录型信号量机制中，wait（S）或signal（S）操作仅能对信号量施以加1或减1操作，意味着每次只能对某类临界资源进行一个单位的申请或释放。当一次需要N个单位时，便要进行N次wait（S）操作，这显然是低效的，甚至会增加死锁的概率。

此外，在有些情况下，为确保系统的安全性，当所申请的资源数量低于某一下限值时，还必须进行管制，不予以分配。因此，当进程申请某类临界资源时，在每次分配之前，都必须测试资源的数量，判断是否大于可分配的下限值，决定是否予以分配。

基于上述两点，可以对AND信号量机制加以扩充，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放。进程对信号量 $S_i$，的测试值不再是1，而是该资源的分配下限值 $t_i$，即要求 $S_i \geq t_i$，否则不予分配。一旦允许分配，进程对该资源的需求值为 $d_i$，即表示资源占用量，进行 $S_i := S_i-d_i$ 操作，而不是简单的 $S_i := S_i-1$。由此形成一般化的“信号量集”机制。对应的 Swait 和 Ssignal 格式为：

1
2

Swait(S1, t1, di, ..., Sn, tn, dn);  // Si是第i类临界i资源的数量，ti是第i类临界资源可分配的下限值，di是当前进程对第i类临界资源的需求量。
Ssignal(S1, di, ..., Sn, dn);  // 释放该进程占用的所有资源

信号量集机制和And信号量机制的区别有两点：

1、引入了可分配的下限值，当且仅当临界资源数量大于等于该数值时，才得以申请。 2、引入进程对该资源的需求值，进程一次性申请该类型临界资源的多个单位。

信号量实现进程互斥

为了使得多个进程能够互斥的访问某临界资源，只需要

为使多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量 mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS（Critical Section）置于 wait(mutex) 和 signal(mutex) 操作之间即可。 这样，每个欲访问该临界资源的进程在进入临界区之前，都要先对 mutex 执行 waite()/p()，尝试申请这个临界资源，如果该资源此刻未被访问，本次wait()/p() 就必然成功，进程便可以进入自己的临界区，这时若再有其他进程也欲进入自己的临界区，由于对 mutex 执行 wait()/p() 操作必然失败，此时，该进程就会被阻塞，从而保证了对该临界资源的互斥访问。

semaphore mutex = 1;                 semaphore mutex = 1;
Pa(){                                Pb(){
	while(1){                        	while(1){
		wait(mutex);		            	wait(mutex);
		临界区		                          临界区
		signal(mutex);                      signal(mutex);
		剩余区		                          剩余区
	}                                   }
}                                    }

在使用信号量机制实现互斥时，需要注意，wait(mutex) 和 signal(mutex) 必须成对出现，没有 wait，资源访问不能保证互斥，没有 signal，资源不能被释放。

互斥锁（mutex）和标志法、T&S指令、信号量机制（semaphore）的关系

解释一 $semaphore mutex $

互斥锁（英语：Mutual exclusion，缩写 Mutex）是一种用于多线程编程中，防止两条线程同时对同一公共资源（比如全局变量）进行读写的机制。[1]

信号量机制是迪杰斯特拉提出来的一种应用广泛的进程同步工具。[2]

信号量机制是一种高级的互斥锁实现形式

单、双标志和Peterson算法以及中断关闭、Test-and-set、Swap是低级的互斥锁实现形式。

[1] 互斥锁维基百科 [2] 《计算机操作系统（第四版）》汤小丹等 P53

解释二 $semaphore mutex $

Mutex 相比信号量增加了所有权的概念，一只锁住的 Mutex 只能由给它上锁的线程解开，只有系铃人才能解铃。Mutex 的功能也就因而限制在了构造临界区上。

一元信号量则可以由任一线程解开。这样多出来的一份语义，就是解决读者-写者问题的工具。比如某进程读取磁盘并进入睡眠，等待中断读取盘块结束之后来唤醒它。这就是可以祭出一元信号量的一个情景，而 Mutex 是解决不了的。『信号量』这个词本身来自火车站的信号灯，其实本来就暗含着一层『通知』的含义。

『同步』这个词也可以拆开看，一侧是等待数据的『事件』或者『通知』，一侧是保护数据的『临界区』。信号量可以满足这两个功能，但是可以注意到两个功能的应用场景还是蛮大的，有 do one thing and do it best 的空间。linux 内核曾将 semaphore 作为同步原语，后面代码变得较难维护，刷了一把 mutex 变简单了不少还变快了，需要『通知』的场景则替换为了 completion variable。

[1] 知乎

经典的进程同步问题

生产者和消费者问题

The procedu-consumer problem

哲学家进餐问题

The Dinning Philosophers Problem

读者-写者问题

Reader-Writer

进程通讯机制

信号量机制

信号量机制中，整形、记录型等信号量来控制进程对临界资源的访问，解决互斥和共享问题，本身就是一种特别的进程通信模式。

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

在进程通信之间存在一块可以直接访问的共享空间，通过对这片空间进行读写操作实现进程之间的信息交换，需要加锁。（低级通信方式是基于数据结构的共享（变量），高级则是基于存储区。）

管道通信系统（pipe）

所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。 向管道（共享文件）提供输入的发送进程（即写进程）以字符流形式将大量的数据送入管道；而接受管道输出的接收进程（即读进程）则从管道中接收（读）数据。由于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。

为了协调双方的通信，管道机制必须提供以下三方面的协调能力： 1、互斥，即当一个进程正在对pipe 执行读/写操作时，其它（另一）进程必须等待。 2、同步，指当写（输入）进程把一定数量（如4KB）的数据写入pipe，便去睡眠等待，直到读（输出）进程取走数据后再把它唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后才将之唤醒。 3、确定对方是否存在，只有确定了对方已存在时才能进行通信。

优点：能有效地传送大量数据

无名管道 我们可以通过 int pipe(int fd[2]) 来创建一个无名管道。无名管道只能在具有亲缘关系的进程之间传递信息，并通过文件描述符 fd 来控制进程的读写操作： fd[0] 为读打开， fd[1] 为写打开。


#include<stdio.h>
#include<unistd.h>
int main(){
    int fd[2]; // 两个文件描述符
    pid_t pid;
    char buff[20];
    if(pipe(fd) < 0) // 创建管道
    	printf("Create Pipe Error!\n");
    if((pid = fork()) < 0) // 创建子进程
    	printf("Fork Error!\n");
    else if(pid > 0) {  // 父进程
        close(fd[0]); // 关闭读端
        write(fd[1], "hello world\n", 12);
    }
    else{
        close(fd[1]); // 关闭写端
        read(fd[0], buff, 20);
        printf("%s", buff);
    }
    return 0;
}

有名管道(FIFO) 我们可以使用 int mkfifo(const char* pathname, mode_t mode); 来创建有名管道在无关进程中直接交换数据。当我们 open 一个 FIFO 时，没有指定 O_NONBLOCK （默认），只读 open 要阻塞到某个其他进程为写打开 FIFO ，类似的，只写 open 要阻塞到其他进程为读而打开它。如果 open 一个 FIFO 时，指定了 O_NONELOCK ，则只读 open 立即返回。而只写 open 将出错返回 1。如果没有进程为读而打开该 FIFO ，其 errno 置 ENXIO。

// write_fifo.c
#include<stdio.h>
#include<stdlib.h> // exit
#include<fcntl.h> // O_WRONLY
#include<sys/stat.h>
#include<time.h> // time
int main(){
    int fd;
    int n, i;
    char buf[1024];
    time_t tp;
    printf("I am %d process.\n", getpid()); // 说明进程ID
    if((fd = open("fifo1", O_WRONLY)) < 0){ // 以写打开一个FIFO
        perror("Open FIFO Failed");
        exit(1);
    }
    for(i=0; i<10; ++i){
        time(&tp); // 取系统当前时间
        n=sprintf(buf,"Process %d's time is %s",getpid(),ctime(&tp));
        printf("Send message: %s", buf); // 打印
        if(write(fd, buf, n+1) < 0){ // 写入到FIFO中
            perror("Write FIFO Failed");
            close(fd);
            exit(1);
        }
        sleep(1); // 休眠1秒
    }
    close(fd); // 关闭FIFO文件
    return 0;
}

// read_fifo.c
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<fcntl.h>
#include<sys/stat.h>
int main(){
    int fd;
    int len;
    char buf[1024];
    if(mkfifo("fifo1", 0666) < 0 && errno!=EEXIST) // 创建FIFO管道
    	perror("Create FIFO Failed");
    if((fd = open("fifo1", O_RDONLY)) < 0){ // 以读打开FIFO
        perror("Open FIFO Failed");
        exit(1);
    }
    while((len = read(fd, buf, 1024)) > 0) // 读取FIFO管道
    	printf("Read message: %s", buf);
    close(fd); // 关闭FIFO文件
    return 0;
}

消息传递系统（Message Passing System）

在该机制中，以格式化的消息（message）为通信单位；利用系统为进程提供的两个高级通信原语send和received进行通信，隐藏看通讯的实现细节，对用户是透明的，使用非常方便，是使用最广泛的进程通信机制。 根据实现方式不同，可进一步将他们分为两种：

直接通信

指发送进程利用OS提供的发送原语，直接把消息发送给目标进程。并将它挂在目标进程的消息缓冲队列上，目标进程从缓存队列中取得消息。直接通信可以显式调用通信连接命令，请求系统为之建立一条通信链路，在通信完成后拆除链路，主要用于计算机网络中。也可以不显式调用命令建立通道，只利用系统提供的发送命令原语，让系统自动为之建立链路。

间接通信

发送个接收进程，都通过共享中间实体（邮箱）的方式进行消息的发送和接收，完成进程之间的通信。每一个信箱都有唯一一个标识符。发送和接受消息由系统调用实现。

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

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

客户机-服务器系统的实现方法，分为三种形式：套接字、远程过程、远程方法调用。

套接字

一个套接字就是有关通信标识类型的数据结构，包含了通信目的地，通信使用的端口号，通信网络的传输层协议。通常套接字包括两类:

基于文件型：通信进程都运行在一台机器的环境中，套接字是基于本地文件系统的支持，一个套接字关联到一个特殊的文件，双方文件基于这个特殊文件进行读写。
基于网络型：这种类型通常采用非对称方法通信，即发送者需要提供接收者的命名。通信双方的进程运行的在不同主机的网络环境下，被分配了一对套接字。

套接字的优势在于，它不仅适用于同一台计算机内部的进程通信，也适用于网络环境中不同计算机间的进程通信。

远程过程和远程方法调用

远程过程（函数）调用RPC（Remote Procedure Call），是一个通信协议，用于通过网络连接的系统。该协议允许运行于一台主机（本地）系统上的进程调用另一台主机（远程）系统上的进程，而对程序员表现为常规的过程调用，无需额外地为此编程。

不同进程通信方法总结

几种通信方法总结综上所述．进程之间的多种通信方法各自有各自的优点和缺点：如果用户传递的信息较少．或是需要通过信号来触发某些行为。信号量机制不失为一种简捷有效的进程间通信方式。

但若是进程间要求传递的信息量比较大或者进程间存在交换数据的要求，那就需要考虑别的通信方式了。无名管道简单方便，但局限于单向通信的工作方式．并且只能在创建它的进程及其子孙进程之间实现管道的共享：有名管道虽然可以提供给任意关系的进程使用．但是由于其长期存在于系统之中，使用不当容易出错．所以普通用户一般不建议使用。

消息队列可以不再局限于父子进程．而允许任意进程通过共享消息队列来实现进程间通信．并由系统调用函数来实现消息发送和接收之间的同步．从而使得用户在使用消息缓冲进行通信时不再需要考虑同步问题．使用方便，但是消息队列中信息的复制需要额外消耗CPU的时间。不适宜于信息量大或操作频繁的场合。

共享存储针对消息缓冲的缺点改而利用内存缓冲区直接交换信息，无须复制，快捷、信息量大是其优点。但是共享存储的通信方式是通过将共享的内存缓冲区直接附加到进程的虚拟地址空间中来实现的。因此，这些进程之间的读写操作的同步问题操作系统无法实现。必须由各进程利用其他同步工具解决。另外，由于内存实体存在于计算机系统中．所以只能由处于同一个计算机系统中的诸进程共享，不方便网络通信。

不同的进程通信方式有不同的优点和缺点。因此，对于不同的应用问题，要根据问题本身的情况来选择进程间的通信方式。

一般来说，进程间的通信根据通信内容可以划分为两种：即控制信息的传送与大批数据传送。有时也把进程间控制信息的交换称为低级通信，而把进程间大批量数据的交换称为高级通信。

线程通信机制

互斥量 Synchronized/Lock

采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问

信号量 Semphare

为控制具有有限数量的用户资源而设计的，它允许多个线程在同一时刻去访问同一个资源，但一般需要限制同一时刻访问此资源的最大线程数目。

等待/通知机制 Wait/Notify

使用wait/notify方法实现线程间通信，要注意以下两点： 1. wait和notify必须配合synchronized关键字使用 2. wait方法释放锁，notify方法不释放锁

通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

操作系统计算机科学入门

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

somewhere vs anywhere 上一篇

Python协程编程下一篇

进程同步与进程、线程通信问题

进程同步机制

背景介绍

多道程序环境

背景介绍

临界资源和临界区

互斥和同步

基本解决方法

遵循一让三等待原则

软件同步机制

单标志法

双（多）标志法先检查

双（多）标志法后检查

硬件同步机制

关闭中断

Test-and-Set指令（自旋锁机制）

利用Swap指令实现互斥

信号量机制

整型信号量

记录型信号量

And型信号量

信号量集

信号量实现进程互斥

互斥锁（mutex）和标志法、T&S指令、信号量机制（semaphore）的关系

解释一 $semaphore mutex $

解释二 $semaphore mutex $

经典的进程同步问题

生产者和消费者问题

哲学家进餐问题

读者-写者问题

进程通讯机制

信号量机制

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

管道通信系统（pipe）

消息传递系统（Message Passing System）

直接通信

间接通信

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

套接字

远程过程和远程方法调用

不同进程通信方法总结

线程通信机制