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

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

竞争关系

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

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

协作关系

某些进程为完成同一任务需要分工协作。例如：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);
		吃苹果;
	}
}