操作系统笔记------进程同步（2）

信号量机制

描述

信号量机制是一种高效的进程同步工具，其发展由整型信号量到记录型信号量再到”信号量集”机制，广泛用于单处理机和多处理机以及计算机网络。

整型信号量

顾名思义，其定义了一个用于表示资源数目的整型量S来控制资源访问。

PV原子操作

为了实现同步，有定义了两个标准的原子操作，P（wait），V（signal），分别对资源进行请求与释放。

大致的代码描述如下：

wait()
{
	while(S<=0);
	S--;
}

signal()
{
	S++;
}

由于是两个原子性的操作，所以两个函数的实现是无法被打断的，当进程提出请求（wait）就会根据S的值来判断，S初始值为1，当有一个进程获取访问后，S–，S<=0，就会陷入while的循环等待中，直至上一个进程访问结束，S++；便可跳出循环获取访问权限。

记录型信号量

记录型信号量相比较与整型信号量，多了一个阻塞进程队列，当进程请求时会对请求进行判断，如果没有可用资源，就会将其放入阻塞队列中等待，等到资源空闲后会从队列中对其进行唤醒。

代码描述如下：

int S ;//资源数，为了好理解还是预设为1吧
struct process *list;

wait()
{
	S--;
	if(S<0)//S<0表示没有可以的资源则将其对应进程进行阻塞等待
	{
		block(list);
	}
}

signal()
{
	S++;
	if(S<=0)//释放使用的资源之后检查是否还有进程在申请，如果有就从队列中唤醒。
	{
		wakeup(list);
	}
}

参数意义

在之前的例子中S的数量是有具体的意义的，当S<0时表示没有可用的资源了，当S大于0时，其值就是资源的数量，当S的数值小于0时表示没有可用的资源了，其绝对值的大小就是被阻塞的进程数量。
当系统中某个资源的数量大于一时，我们就可以将S的数量设为资源数目，也可以使其正常同步。

死锁

之前的两种信号量都是对单个资源的请求，但是实际的使用中进程往往一次性会请求多个临界资源。
现在假设使用之前的信号量机制对两个临界资源进行管理，有进程A，B访问这两个资源R1，R2，这时假定其请求顺序是A请求R1，同时B请求R2，且都获得了访问权，但是要想让进程工作，必须要对这两个资源进行访问，这时B请求R1，但是R1被A占用了，A请求R2，同样被A占了，所以就出现了死锁状态。
进程集合中的每一个进程都在等待只能由本集合中的其他进程才能引发的事件，那么该组进程是死锁的。

AND型信号量

为了打破进程对多个资源的访问出现的死锁情况，提出了AND同步机制，其策略是对进程请求的资源实行一次性的分配策略，也就是说要获得资源访问权限必须是同时获得所需的全部资源权限，一次性分配全部，用完一次性释放。这些获取与释放资源的操作也是原子操作，在判断所有资源是否都处于可用状态时会使用AND判断，所以得名。
代码描述如下：

int S[n] ;//资源集合，初始设为1
struct process *list;//阻塞队列
wait()
{
	if(S[0]==1&&S[1]==1&&......&&S[n-1]==1)//资源的集体空闲
	{
		int i;
		for(i=0;i<n;i++)
		{
			S[i]=0;
		}
	}else
	{
		block(list);//阻塞等待
	}
	
}

signal()
{
	for(i=0;i<n;i++)
	{
		S[i]=1;//同时释放
	}
	wakeup(list);//唤醒阻塞进程	
}

信号量集

在之前的信号量操作中，我们都是以零散的方式去请求资源，这样往往会提高出现死锁的概率，同时效率也不高，所以我们可以通过改进资源的申请方式来提高效率，减小发生死锁的概率。

修改策略：之前是每次申请一个资源，现在我们设置一个资源申请的阈值，在这一阈值之下的我们不予以分配，超出这个阈值的请求，进行统一处理。通过修改原有的wait与signal原语，使我们可以对多种资源每个资源的不同数量的多个请求实现一次性分配，这样可以大大减少原语的使用次数，提高效率。

这样的话，我们每次都要去检测资源的需求量，如果大于其设置的值并且其含有可用资源数目足够就一次性分配，如果小于设置的值就不予分配。
大致的描述可以使用形如：wait（S，d，d）来表示，S为信号量，第一个d为设置的阈值，若达到该值则进行分配，之后的d表示如果当前的可用资源数（信号量）小于d时就不进行分配。

之前的记录型可以表示为wait（S，1，1），只有一个可用，请求数必须至少为1。
除此之外，还有一个wait（S，1，0），表示一个可用开关，多个进程可以同时发出需求，但是当信号量为0时不予分配。