计算机操作系统学习笔记——进程管理之协作进程的同步、互斥

阅读量：3940 次

发布时间：2019-05-23

本文共 5909 字，大约阅读时间需要 19 分钟。

进程管理之协作进程的同步与互斥

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

一、相关基本概念

1、临界资源

指一次仅允许一个进程使用的资源称为临界资源，例如物理设备中的打印机。对这种临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。

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

1）进入区：为了进入临界区使用临界资源，在进入区要检查是否可进入临界区，若要进入临界区，则应该设置正在访问临界区的标志，以阻止其他进程同时进入临界区。

2）临界区：进程中访问临界资源的那段代码，也称临界段。

3）退出区：用于将正在访问临界区的标志清除。

4）剩余区：代码中的其余部分。

do{		entry section;    //进入区		critical section;  // 临界区		exit section;       // 退出区		remainder section;   //剩余区	}while(ture);

2、同步

也称为直接制约关系，指为完成某种任务而建立的两个或多个进程，这些进程因为需要某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的制约关系源于它们之间的相互合作。

3、互斥

也称为间接制约关系。当一个进程进入临界区使用资源时，另一个进程必须等待，当占用临界资源的进程退出临界区时，另一进程才允许访问此临界资源。

4、相关准则

为禁止两个进程同时进入临界区，同步机制应遵循以下准则：

1）空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。

2）忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待。

3）有限等待：对请求访问的进程，应保证能在有限时间内进入临界区。

4）让权等待：当进程进入临界区时，应立即释放处理器，防止进程忙等待。

二、实现临界区互斥的基本方法

主要有软件实现方法和硬件实现方法。

1、软件实现

在进入区设置并检查一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

1）单标志法

该算法设置一个公用整型变量 turn，用于指示被允许进入临界区的进程编号；当 turn=0 时，允许进程进入临界区;该算法确保每次只允许一个进程进入临界区。
```
①进程：	while(trun!=0);	critical section;	turn=1;	remainder section;		②进程：	while(turn!=1);	critical section;	turn=0;	remainder section;
```

在上面两个例子中，两个进程交替进入临界区，若某个进程不再进入临界区，则另一个进程也无法进入临界区，这样会造成资源利用率低；另外，若进程 0 顺利进入临界区并离开临界区，但是进程 1 并没有进入临界区的打算，由于 turn=1 一直成立，使得进程 0 再也无法进入临界区。

2）双标志法先检查

基本思想是在每个进程访问临界区资源之前，先查看临界资源是否正在被使用，若是则进程等待；若不是，进程才进入临界区。该算法设置一个 flag[i] 表示某个进程是否进入临界区，true 表示进入，false 表示未进入。
```
pi进程：	while(flag[j]);     ①	flag[i]=true;        ③	critical section;	flag[i]=false;	remainder section;		pj 进程：	while[flag[i]);    ②	flag[j]=true;       ④	critical section;	flag[j]=false;	remainder section;
```

优点：不用交替进入，可连续使用。

缺点：两个进程可能同时进入临界区，按序列①②③④执行时；因为在检查对方的 flag 后切换自己的 flag 前有一段时间，结果都检查通过。问题原因在于检查和修改操作不能一次进行。

3）双标志法后检查

为弥补双标志法先检查的不足，

该算法先将自己的标志设置为 true，再检查对方的状态标志，若对方为 true，则进程等待；否则进入临界区

。

pi 进程：	flag[i]=ture;	while(flag[j]);	critical section;	flag[i]=false;	remainder section;		pj 进程：	flag[j]=true;	while(flag[i]);	critical section;	flag[j]=false;	remainder section;

这种算法可能发生的情况：两个进程几乎同时都想进入临界区时，分别同时将自己的标志设置为 true，并且同时检测对方的状态，发现对方也要进入临界区，双方互相谦让，从而导致“饥饿”现象。

4）Peterson’s Algorithm

综合前面三个算法，设置两个标志：flag 和 turn，每个进程先设置自己的 flag 再设置 turn 标志，再同时检测另一个进程的状态标志和不允许进入标志，保证两个进程同时要求进入临界区时，只允许一个进程进入临界区：
```
pi 进程	flag[i]=true;turn=j;	while(flag[j]&&turn==j);	critical section;	flag[i]=false;	remainder section;		pj 进程：	flag[j]=true;turn=i;	while(flag[i]&&turn==i);	critical section;	remiander section;
```

本算法利用 flag 解决临界资源的互斥访问，利用 turn 解决“饥饿”现象。

2、硬件实现

计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或对两个字的内容进行交换等。通过硬件支持实现临界段问题的方法称为低级方法，或称元方法。

1）中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，防止其他进程进入临界区进行访问的最简方法就是，禁止一切中断发生，称之为屏蔽中断、关中断。因为 CPU 只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利执行完，进而保证互斥的正确实现，然后再开中断。典型模型如下：
```
.	.	.	关中断	临界区	开中断	.	.	.
```

此方法限制了处理机交替执行程序的能力，从而降低执行效率，而且风险大：将关中断权利下放给用户程序，若用户程序关中断后不再开中断，系统可能因此终止。

2）硬件指令方法

a、TestAndSet 指令

该指令为原子操作，其功能是读出指定标志后把该标志设置为真，功能描述：
```
boolean TestAndSet(boolean *lock){		boolean old;		old=*lock;		*lock=true;		return old;	}
```

基于此指令，为每个临界资源设置一个共享布尔变量 lock，true 表示占用，初值为 false。进程访问临界资源前调用 TestAndSet 检测 lock，若无占用则进程直接访问临界资源，反之则循环检测直到占用临界资源的进程退出，如下：
```
while(TestAndSet(&lock));	critical section;	lock=false;	remainder section;
```

b、Swap 指令

该指令功能是交换两个字的内容，如下：

Swap(boolean *a, boolean *b){		boolean temp;		temp=*a;		*a=*b;		*b=temp;	}

同样的每个临界资源设置一个共享布尔变量 lock，初值为 false；再为每个进程设置一个布尔变量 key。进程进入临界区前，利用 Swap 交换 lock 和 key，检测 key 的状态；有进程占用临界区则重复交换和检测过程，直到进程退出。
```
key=true;	while(key!=false)		Swap(&lock,&key);	critical section;	lock=false;	remainder section;
```

3）硬件方法的优缺点

优点：适用于任意数目的进程，不管单处理机还是多处理机；简单、容易验证其正确性；支持进程内有多个临界区。

缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待；从进程中随机选取一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

三、信号量

信号量机制是一种功能较强的机制，可用于解决互斥与同步问题，只能被两个标准的原语 wait(s) 和 singal(S) 访问，也可记为“P 操作”和“V 操作”。

1、整型信号量

整型信号量被定义为一个表示资源数目的整型量 S，wait 和 singal 操作可描述为：
```
wait(s){		while(S<=0);		S=S-1;	}	signal(S){		S=S+1;	}
```

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

2、记录型信号量

这种机制下，除了一个用于代表资源数目的整型变量 value 外，还有一个进程链表 L，用于链接所有等待该资源的进程；因此此种机制下不存在“忙等”现象。记录型信号量可描述如下：
```
typdef struct{		int value;		struct process *L;	}semaphore;
```

相应的 wait 操作和 singal 操作：

void wait(semphore S){		S.value--;     //请求一个该类资源		if(S.value<0){//当该类资源已经分配完			add this process to S.L; // 进入等待队列			block(S.L); // 进行自我阻塞		}	}	void singal(semaphore S){  		S.value++;  // 释放资源		if(S.value<=0){ // 判断是否有等待该资源的进程			remove a process P from S.L; // 从等待队列中选择一个进程			wakeup(P); // 唤醒该进程		}	}

3、利用信号量实现同步

S 为进程 P1 和 P2 同步的公共信号量，初值为 0，其中 P2 要用到 P1 的一个结果，则进程同步的算法可描述如下：

semaphore S=0;	P1(){		…		x;  // 语句 x，为 P2 要用到的结果		V(S);  // 告诉 P2，语句 x 已经完成		…	}	P2(){		…		P(S);   //检测 x 语句是否完成，若没有，进程阻塞		y;  // 当语句 x 完成，运行 y 语句。	}

4、利用信号量实现进程互斥

S 为进程 P1 和 P2 的互斥信号量，初值为 1，表示资源数量为1.实现这两个进程对临界区的互斥访问的算法可描述如下：

semaphore S=1;	P1(){		…		P(S);   //准备访问临界资源，加锁		critical section;		V(S);  // 访问结束，解锁		…	}	P2(){		…		P(S);   //准备访问临界资源，加锁		critical section;		V(S);  // 访问结束，解锁		…	}

当没有进程在临界区时，执行 P操作，则 S 值减为 0，然后进入临界区；此时，若再用进程要进入临界区，同样执行 P 操作则会发生进程阻塞，直到临界区中的进程退出并执行 V 操作，这就达到了临界区的互斥。

四、管程

1、定义

利用共享数据结构抽象地表示系统中地共享资源，而把对该数据结构实施地操作定义为一组过程；这个代表共享资源地数据结构，以及由对该共享数据结构实施操作地一组过程所组成地资源管理程序，称为管程。

管程有如下四个部分组成：

① 管程的名称；

② 局部于管程内部的共享结构数据说明；

③ 对该数据结构进行操作的一组过程或函数；

④ 对局部于管程内部的共享数据设置初始值的语句。

monitor Demo{// 定义一个名称为 Demo 的管程		// 定义共享数据结构，对应系统中的某种共享资源		typdef struct S;		// 对共享数据结构初始化		init func(){			S=5;   // 初始资源数量		}		// 过程 1：申请一个资源		take_away(){			some code;  // 对共享数据结构 x 的一系列处理			S--;  // 可用资源数减一			…		}		// 过程2：归还资源		give_back(){			some code;			S++;  // 可用资源数加一		}	}

2、条件变量

一个进程进入管程后被阻塞直到阻塞的原因解除，期间若进程不释放管程则其他进程无法进入管程，为此，将阻塞原因定义为条件变量 condition，每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程，对条件变量只进行 wait 和 signal 操作。
x.wait：当 x 对应的条件不满足时，正在调用管程的进程调用 x.wait 将自己插入 x 条件的等待队列，并释放管程，此时其他进程可以使用该管程。
x.singal：x 对应的条件发生变化，则调用 x.singal 唤醒一个因 x 条件阻塞的进程。
```
monitor Demo{		typdef struct S;		condition x;		init func(){};		take_away(){			if(S<=0) x.wait();			…		}		give_back(){			…			if(有进程在等待) x.singal();		}	}
```