进程间通信

进程间通信

竞争条件：两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序。

临界区：对共享内存进行访问的程序片段。

进程通信有三方面的内容：

1.一个进程如何向另一个进程场地消息

2.必须保证多个进程在涉及临界活动时不会彼此影响（设想两个进程都试图摄取最后100kb内存的情况）。

3.当存在依赖关系时确定适当的次序：如果进程A产生数据，进程B打印数据，则B必须等到A产生了一些数据后才能开始打印。

由于存在共享内存，并且有多个进程要进行读写操作，那么如何保证不发生错误（避免竞争）？解决的方法是互斥（mutual exclusion），即以某种手段确保当一个进程在使用一个共享变量或文件时，其他的进程不能做同样的操作。

那么如何设计一个好的互斥方案？一个好的互斥解决方案，需要具备以下四个条件：

1.任何两个进程不能同时处于临界区

2.不应对CPU的速度和数目做任何假设

3.临界区外的进程不得阻塞其他进程

4.不得使进程在临界区外无休止的等待

解决方案1：关闭中断

缺点：假如用户进程关闭中断后就不开中断，系统可能会因此而终止。

关中断对于操作系统来说是一项有用的技术（内核在执行更新变量时发生中断，那么可能会导致竞争条件，因为cpu本身就是共享资源），对用户则不是一种合适的通用互斥机制。

解决方案2：锁变量（只是最简单的，也是最容易想到的）

设置一个共享锁变量，初值为0，当要访问该资源是，检查这把锁的状态。但是这种方案不行，有可能两个进程都把该锁设置为相同的状态，导致竞争条件。有多个进程同时把所变量设为相同的值，具体写代码实现就很清楚

解决方案3：严格交替法（轮流进入临界区，可行）

这是对锁变量的方案进行改进，把锁设置为0交个一个进程，把锁设置为1交个另一个进程。 也就是说一个进程只能对锁设置一种状态。

缺点：假如A进程把锁设置为1后离开临界区以便允许其他进程进入临界区，但A很快又请求进入临界区，此时A得等待有其他进程把锁设置为0，A方可进入。如果没有其他进程来更新锁的状态，那么A就得一直等待下去（忙等待），不管怎么样，A的等待是不可避免的。只有在有理由期待等待时间很短时才使用忙等待，一个适用忙等待的锁称为自旋锁（spinlock）。

解决方案4：Peterson方案

严格交替法失效的原因在于，A必须等待到有进程进入临界区更新锁的状态，然后才能进入。怎么来改进这种方案呢？A等待是因为其他进程不在临界区，所以A被临界区外的进程阻塞。假如此时A知道其他进程的状态，那么它就不需要等待。如何来实现？

缺点：存在忙等待,等待临界区的进程离开

实现：

#define FALSE 0
#define TRUE 1
#define processes 2

int turn;
int interested[processes]={0};

void critical_region();

void enter_region(int process)
{
	int other;
	other = 1 - process;
	interested[process] = TRUE;
	turn = process;
	//这里的条件判断是整个算法的核心
	//turn==process测试是否有进程更新锁状态，true是没有
	//interested[other]获得其他进程的状态,true是other处于临界区
	while(turn == process && interested[other]==TRUE);//wait
	critical_region();
	leave_region(process);
}


void leave_region(int process)
{
	interested[process]=FALSE; //表示离开临界区
}

解决方案5：睡眠（sleep）和唤醒（wakeup）

如何避免忙等待？Peterson解法的本质是，当一个进程想进入临界区，先检查是否允许进入，若不允许，则进程忙等待，直到许可为止。这种情况可能会出现一个严重的错误，永远忙等待下去。

如何来改进这一算法？一种简单的想法是，当检测到不能进入临界区的话，那么该进程就应当让出cpu（把自己阻塞），执行另外的一个进程，而不是占着cpu。那么如何实现？使用sleep和wakeup系统调用。

实现：

#define N 100	//缓冲区的槽数
int count = N;

void producer(void)
{
	int item;
	while(TRUE)
	{
		item = produce_item();
		if(count==0)sleep();
		insert_item();
		--count;

		/*这里可能会引发问题，假如消费者还没有运行呢，它就不需要wakeup；另一种情况，假如消费者没有sleep呢（当count为N时，中断发生执行生产者）
		这样也不需要wakeup。对于第二种情况是由于consumer刚执行完count==N便发生中断，当consumer再次运行时，则consumer去sleep,这样wakeup信号丢失
		导致producer最终填满缓冲区是也睡眠，从此两个进程进睡眠了。*/
		if(count==N-1)wakeup(consumer);
	}
}

void consumer(void)
{
	int item;
	while(TRUE)
	{
		if(count==N)sleep();
		item = remove_item();
		++count;

		//这里wakeup信号也会丢失
		if(count == N)wakup(producer);
		consume_item(item);
	}
}

缺点：引发上述wakeup信号丢失的原因是对count的访问未加限制。如何来解决信号丢失问题，一种快速补救的方法是，加上一个唤醒等待位（wakeup waiting bit） 。但这种方法的缺点是，假如有多个进程，那么一个唤醒等待我就不够了。

解决方案5：信号量

针对上述wakeup信号量丢失的问题，如何解决？上述问题的根本原因是不需要唤醒的时候去唤醒。

信号量是E.W.Dijkstra在1965年提出的一种方法，它使用一个整型变量来累计唤醒次数，以供以后使用。在他的建议中，引入一个新的变量，称为信号量（semaphore）。

Dijkstra建议设两种操作：P和V（分别为一般后的sleep和wakeup）。对一信号量执行P操作首先检查其值是否大于0，如果这样，则将其值减一（即用掉一个保存的唤醒信号）并继续。如果为0，则进程睡眠。检查数值、改变数值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操（atomicaction）作完成。

V操作递增信号量。如果一个或者多个进程在该信号量上睡眠，无法完成一个先前的P操作，则由系统选择其中的一个并允许其它的P操作。于是，对一个有进程在其上睡眠的信号量执行一次V操作之后，该信号量仍旧是0，但在其上睡眠的进程却少了一个。

如果每个进程在进入临界区前执行P操作，离开临界区后执行V操作，那么就能保证互斥。

信号量可能的使用方法：

互斥：初始化互斥信号量为1

共享资源：初始化信号量为共享实体的数量

协作进程：初始化信号量为0

用信号量解决生产者消费者问题：

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer(void)
{
	int item;
	while(TRUE)
	{
		item = produce_item();
		P(&empty);
		P(&mutex);
		inset_item(item);
		V(&mutex);
		V(&full);

	}
}

void consumer(void)
{
	int item;
	while(TRUE)
	{
		P(&full);
		P(&mutex);
		item = remove_item();
		V(&mutex);
		V(&empty);
		consume_item(item);
	}
}

总结：实现互斥，本质是把对信号量的递增和递减操作分隔开，一个进程只能进行一种操作，并且是原子操作。

解决方案6：管程

有了信号量之后，进程间通信看来很容易了吗？使用信号量需要程序员考虑时间问题，如何安排P的顺序（如果安排不但则会死锁），这样很容易错过一些问题，导致debug很困难。所以，一种好的方法是，把如何安排互斥的问题交给编译器来处理，即设计一种高级同步原语，称为管程。