（五）操作系统-进程间的交互

在多道程序设计系统中，同一时刻可能有许多进程，这些进程之间存在两种基本关系：竞争关系和协作关系。

竞争关系

系统中的多个进程之间彼此无关，它们并不知道其他进程的存在，但由于共享系统资源，就会出现竞争。当多个进程竞争共享硬设备、变量、表格、链表、文件等资源时，可能导致处理出错。

死锁、饥饿（资源的竞争出现了这两个控制问题）
进程的互斥（临界区管理）

协作关系

某些进程为完成同一任务需要分工协作。例如：input, compute, output ，协作进程之间
各自知道对方的存在

进程的同步（解决进程间协作关系的手段）

进程互斥关系是一种特殊的进程同步关系，即逐次使用共享资源

临界区

临界区（critical sections）

进程中访问共享变量（临界资源）的代码段（程序段）
不同进程关于同一变量的临界段代码可能是完全不同的
临界资源—共享变量

进程对临界区的访问必须互斥地进行

Untitled

互斥的硬件方法

中断屏蔽方法

在单机系统中，引起进程开关，使得当前运行进程交出处理器的唯一原因是中断；
当进入锁测试之前关闭中断，直到完成锁测试并上锁之后再开中断。在这一短暂的期间，计算机系统不响应中断，因此不会转向调度，也就不会引起进程或线程切换，从而保证了锁测试和上锁操作的连续性和完整性，有效的实现了临界区管理；
缺点：首先系统要付出较高代价，关中断时间过长也会影响系统效率；其次这种方法在多处理器系统中是不能保证进程间互斥的。

硬件指令方法

TS（test-and-set）指令，又称检测和设置指令；
Swap指令，又称交换指令；

实现互斥的方法：为每个临界段或其他互斥的资源设置一个布尔变量，当其值为false则临界段未被使用，反之则说明正有进程在临界段中执行；

优点：不但适用于单处理器情况，而且适用于共享主存的对称多处理器情况；方法简单、而有效；

缺点：当进程正在临界段中执行时，其他想进入临界段的进程必须不断地检测布尔变量的值，即所谓“忙等待”，从而造成了处理器机时的浪费。

信号量

在多个相互合作的进程之间使用简单的信号来同步，一个进程强制停止在某一特定状态，直到收到专门的信号为止。

一个信号量被定义为一个整型变量，在其上定义了以下三个操作：

可以被“初始化”为一个非负数；
Wait操作将信号量值减1后，若该值为负，则执行wait操作的进程等待；
Signal操作将信号量值增1后，若该值非正，则执行signal操作的进程唤醒等待进程。

用信号量实现进程间互斥

对于两个并发进程，互斥信号量的值仅取1、0和-1三个值：

若mutex = 1，表示没有进程进入临界区；
若mutex = 0，表示有一个进程进入临界区；
若mutex = -1，表示一个进程进入临界区，另一个进程等待进入。

使用互斥信号量和操作原语解决哲学家就餐问题

在这个问题中，每一把叉子都是必须互斥使用的，因此应为每把叉子设置一个互斥信号量Si，初值均
为1。当一个哲学家吃通心面前必须获得自己左边和右边的两把叉子，即执行两个P操作，吃完通心面后必须放下叉子，即执行两个V操作。

Var forki :array[0..4] of semaphore;
	 forki := 1;
cobegin
process Pi // i=0,1,2,3,4,
begin
	L1:思考；
	P(fork[i])； 
	P(fork[(i+1)mod 5])； 
	吃通心面；
	V(fork[i])；
	V(fork[(i+1)mod 5])；
	 goto L1;
end;
coend;

读者—写者问题

有两组并发进程：读者和写者，共享一个文件F，要求：

允许多个读者同时执行读操作；
任一写者在完成写操作之前不允许其它读者或写者工作；
写者执行写操作前，应让已有的写者和读者全部退出。

单纯使用信号量不能完成读者写者问题，必须引入计数器rc对读进程计数，s是用于对计数器rc互斥的信号量，W表示允许写的信号量。

var rc, wc : integer:=0;
	 W，R: semaphore;
	 Rc := 0; /* 读进程计数 */
	 W := 1;
	 R := 1;
procedure read;
begin
	 P(R);
	 rc := rc + 1;
	 if rc=1 then P(W)；
	 V(R);
	 读文件；
	 P(R);
	 rc := rc - 1;
	 if rc = 0 then V(W)；
	 V(R);
end;
procedure write;
begin
	 P(W);
	 写文件;
	 V(W);
end;

例题1——进程控制与同步

桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

分析：在本题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。这实际上是生产者-消费者问题一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。

解答：本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为1；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。同步描述如下：

int S =1;
int Sa = 0;
int So = 0;
main(){
		cobegin
			father();
			son();
			daughter();
		coend
}

father(){
	while(1){
		P(S);
		将水果放入盘中；
		if(放入的是橘子)  
			V(So);
		else
			V(Sa);
	}
}

son(){
	while(1){
		P(So);
		从盘中取出橘子；
		V(S);
		吃橘子；
	}
}

daughter(){
	while(1){
		P(Sa);
		从盘中取出苹果；
		V(S);
		吃苹果;
	}
}

进程间通信

并发进程之间的交往本质上是互相交换信息。有些情况下进程之间交换的信息量很少，例如仅仅交换某个状态信息。有些情况下进程之间交换大批数据，例如传送一批信息或整个文件。

进程之间互相交换信息的工作称之为进程通信IPC(InterProcess Communication)。

进程间通信的方式

通过软中断提供的信号（signal）通信机制；
使用信号量及其原语操作（PV、读写锁、管程或其他操作）控制的共享存储区(shared memory)通信机制；
通过管道(pipeline)提供的共享文件(shared file)通信机制；
使用信箱和发信/收信原语的消息传递(message passing)通信机制。

其中前两种通信方式属于低级通信机制，仅适用于集中式操作系统。

消息传递机制属于高级通信机制，共享文件通信机制是消息传递机制的变种，这两种通信机制，既适用于集中式操作系统，又适用于分布式操作系统。

共享文件通信机制

管道(pipeline)是连接读写进程的一个特殊文件，允许进程按先进先出方式传送数据,也能使进程同步执行操作。如下图所示，发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以，也叫管道通信。

管道通信的方式是发送者进程和接收者进程之间通过一个管道交流信息，管道是单向的，发送者进程只能写入信息，接收者进程也只能接收信息。

Untitled (1)

管道（pipe）是Unix和C语言的传统通信方式,也是Unix发展最有意义的贡献之一。

管道的实质是一个共享文件，因此管道通信基本上可以借助于文件系统原有的机制实现，包括（管道）文件的创建、打开、关闭和读写。但是，写入进程和读出进程之间的相互协调单靠文件系统机制是解决不了的。

消息传递的方式

直接通信方式——消息缓冲区

在直接通信方式下，企图发送或接收消息的每个进程必须指出信件发给谁或从谁那里接收消息。

间接通信方式——信箱

采用间接通信方式时，进程间发送或接收消息通过一个信箱来进行，消息可以被理解成信件，每个信箱有一个唯一的标识符。当两个以上的进程有一个共享的信箱时，它们就能进行通信。一个进程也可以分别与多个进程共享多个不同的信箱，这样，一个进程可以同时和多个进程进行通信。

直接通信常用于进程间相互关系比较紧密的情况下，间接通信用于联系不十分紧密的进程间；
间接通信方式的灵活性：

发送者进程和接收者进程之间的关系可以有一对一、一对多、多对一、多对多等多种关系；
信箱可以是静态的、固定不变的，也可以是动态的、可变的。