PV操作和信号量机制实现进程同步(对多个临界资源的互斥访问)

长平狐 发布于 2012/11/12 11:42
阅读 762
收藏 0

        

          进程同步是我们在多线程中讨论最多的一个话题,在大多数的开发语言中,他们都有自己实现进程同步的方法或者实现。但归根结底他们实现的方式都是基于操作系统的进程同步的方式。今天我们就一起来看一下在操作系统这个底层中是怎么实现进程同步的。在计算机操作系统中,PV操作是进程管理中的一个很重要的方式,这是重点也是难点。 在看PV操作之前,我们先来看另一个比较重要的概念——信号量


          什么是信号量?信号量(semaphore)的数据结构为一个值和一个指针,指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时,表示当前可用资源的数量;当它的值小于0时,其绝对值表示等待使用该资源的进程个数。注意,信号量的值仅能由PV操作来改变。信号量(Semaphore),有时被称为信号灯,是在多线程环境下使用的一种设施,是可以用来保证两个或多个关键代码段不被并发调用。在进入一个关键代码段之前,线程必须获取一个信号量;一旦该关键代码段完成了,那么该线程必须释放信号量。其它想进入该关键代码段的线程必须等待直到第一个线程释放信号量。为了完成这个过程,需要创建一个信号量VI,然后将Acquire Semaphore VI以及Release Semaphore VI分别放置在每个关键代码段的首末端。确认这些信号量VI引用的是初始创建的信号量。 


      一般来说,信号量S>=0时,S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源,因此S的值减1;当S<0时,表示已经没有可用资源,请求者必须等待别的进程释放该类资源,它才能运行下去。而执行一个V操作意味着释放一个单位资源,因此S的值加1;若S<=0,表示有某些进程正在等待该资源,因此要唤醒一个等待状态的进程,使之运行下去。


    利用信号量和PV操作实现进程互斥的一般模型是:


进程P1              进程P2           ……          进程Pn
……                  ……                           ……
P(S);              P(S);                         P(S);
临界区;             临界区;                        临界区;
V(S);              V(S);                        V(S);
……                  ……            ……           ……


    其中信号量S用于互斥,初值为1。


    使用PV操作实现进程互斥时应该注意的是:
    (1)每个程序中用户实现互斥的P、V操作必须成对出现,先做P操作,进临界区,后做V操作,出临界区。若有多个分支,要认真检查其成对性。
    (2)P、V操作应分别紧靠临界区的头尾部,临界区的代码应尽可能短,不能有死循环。
   (3)互斥信号量的初值一般为1。


        PV操作是典型的同步机制之一。用一个信号量与一个消息联系起来,当信号量的值为0时,表示期望的消息尚未产生;当信号量的值非0时,表示期望的消息已经存在。用PV操作实现进程同步时,调用P操作测试消息是否到达,调用V操作发送消息。


对一个信号量变量可以进行两种原语操作:p操作和v操作,定义如下:

	Method p(var s:samephore);  
	{  
	s.value=s.value-1;  
	if (s.value>0) 
	asleep(s.next);  
	}  
	
	
	
	
	Method  v(var s:samephore);  
	{  
	s.value=s.value+1;  
	if (s.value<=0) wakeup(s.next);  
	}  


 

其中用到两个标准过程:

asleep(s.next);执行此操作的进程的PCB进入s.next尾部,进程变成等待状态

wakeup(s.queue);将s.queue头进程唤醒插入就绪队列

s.value初值为1时,可以用来实现进程的互斥。

p操作和v操作是不可中断的程序段,称为原语。如果将信号量看作共享变量,则pv操作为其临界区,多个进程不能同时执行,一般用硬件方法保证。一个信号量只能置一次初值,以后只能对之进行p操作或v操作。由此也可以看到,信号量机制必须有公共内存,不能用于分布式操作系统中,这是它最大的弱点。

V原语的主要操作是:

⑴value加1

若相加结果大于零,则进程继续执行;

若相加结果小于或等于零,则唤醒一阻塞在该信号量上的进程,然后再返回原进程继续执行或转进程调度。

        在java JDK的并发包就给我提供了一个类似的信号量类——Semaphore ,其中的acquire()release()方法就相当于P和V操作,这两个方法的特殊之处在于对Semaphore对象的操作都是原子操作,由操作系统底层来支持。下面我们就来看一下用java实现经典的哲学家就餐问题吧。

import java.util.concurrent.Semaphore;
class Signs{
final static int THINKING=0; //哲学家的状态THINGING
final static int EATING=1; //哲学家的状态EATING
static int[] status=new int[5]; //哲学家的状态,默认都是THINGING
static Semaphore[] s=null; //信号量:记录哲学家是否可以进餐,不能进餐则堵塞
static Semaphore mutex=new Semaphore(1); //临界区互斥访问信号量(二进制信号量),相当于互斥锁
//初始化每个哲学家的进餐信号量,默认值都不能进餐
static{
s=new Semaphore[5];
for(int i=0;i<s.length;i++)
s[i]=new Semaphore(0);
};
}
class Philosopher implements Runnable{
private int pid; //当前哲学家的序号
private int lid; //坐在左手边的哲学家序号
private int rid; //坐在右手边的哲学家序号
Philosopher(int id){
this.pid=id;
this.lid=(id+4)%5;
this.rid=(id+1)%5;
}
private void test(int pid){
//如果当前哲学家左右手边的人都没有吃饭,则当前哲学家可以进餐
if(Signs.status[pid]==Signs.THINKING&&Signs.status[lid]!=Signs.EATING&&Signs.status[rid]!=Signs.EATING){
Signs.status[pid]=Signs.EATING; //此时当前哲学家线程可以进餐,但其他哲学家线程很可能无法进餐
Signs.s[pid].release(); //释放一个许可
}
}
public void run(){
try {
//尝试拿起叉子准备进餐
Signs.mutex.acquire();
test(pid);
Signs.mutex.release();
//判断当前哲学家的进餐信号量,如果不能许可进餐,则当前线程阻塞
Signs.s[pid].acquire();
System.out.println("#"+pid+" 号哲学家正在进餐...");
//放下叉子,并唤醒旁边两个被阻塞进餐的哲学家,让他们尝试进餐
Signs.mutex.acquire();
Signs.status[pid]=Signs.THINKING;
test(lid); //让左手边的哲学家尝试拿起叉子,如果可以,则释放这个哲学家的信号量许可
test(rid); //同上
Signs.mutex.release();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
public class Test{
public static void main(String[] args) {
new Thread(new Philosopher(0)).start();
new Thread(new Philosopher(1)).start();
new Thread(new Philosopher(2)).start();
new Thread(new Philosopher(3)).start();
new Thread(new Philosopher(4)).start();
}
}


更多java代码实现线程同步问题请看:http://hxraid.iteye.com/blog/739265 


------------------------------------------------------------------------------------------------------------

《Java程序员由笨鸟到菜鸟》电子版书正式发布,欢迎大家下载

http://blog.csdn.net/csh624366188/article/details/7999247






原文链接:http://blog.csdn.net/csh624366188/article/details/8035428
加载中
返回顶部
顶部