对操作系统中信号量问题的一点认识

2009-08-28李俭张明辉任立权

计算机教育 2009年14期

关键词：同步

李　俭　张明辉　任立权

摘要:本文针对目前操作系统中利用信号量解决进程间的同步和互斥的问题,系统地总结了解决问题的一般性规律。首先介绍了信号量的定义及在信号量上可以执行的两个操作,并分别详细说明了如何利用信号量实现进程间的同步和互斥,最后结合实例说明了这两种方法在实际问题中的具体运用。

关键词:信号量;同步;互斥

中图分类号:G642 文献标识码:B

在多道程序环境下,操作系统如何实现进程之间的同步和互斥显得极为重要。荷兰学者Dijkstra给出了一种解决并发进程间互斥与同步关系的通用方法,即信号量机制。他定义了一种名为“信号量”的变量,并且规定在这种变量上只能做所谓的P操作和V操作。现在,信号量机制已经被广泛地应用于单处理机和多处理机系统以及计算机网络中,这也是学习操作系统的重点和难点之一。本文就利用信号量实现进程间的同步和互斥问题进行了分析。

1引言

信号量是一个具有非负初值的整型变量,并且有一个队列与它关联。因此,定义一个信号量时,要给出它的初值,并给出与它相关的队列指针。信号量除初始化外,仅能通过P、V两个操作来访问,这两个操作都由原语组成,即在执行过程中不可被中断,也就是说,当一个进程在修改某个信号量时,没有其他进程可同时对该信号量进行修改。

信号量的定义如下:

type semaphore=record

/*定义信号量*/

begin

value:integer;/*整型变量*/

L:list of process;

/*与该信号量相关联的队列*/

end

P(S)操作可描述为:

procedure P(S)

var S: semaphore;

begin

S.value:=S.value-1;

/*信号量的值减1*/

if S.value<0 then block(S,L)

/*若信号量的值小于0,则阻塞执行该P操作的进程*/

end

当执行P(S)操作时,信号量S的值减1,如果S≥0,表示可以继续执行;如果S<0,表示该进程只能进入S信号量的阻塞队列中等待,由调度程序重新调度其他进程执行。需要注意的是,使该信号量S的值增加的进程会将该阻塞进程唤醒,该进程一旦获得处理机,就可以直接进入临界区,无需再执行P(S)操作。

V(S)操作可描述为:

procedure V(S)

var S: semaphore;

begin

S.value:=S.value+1;

if S.value≤0

then wakeup(S,L);

end

当执行V(S)操作时,信号量S的值加1,如果S≤0,则唤醒S信号量阻塞队列队首的阻塞进程,将其状态从阻塞状态转变为就绪状态,执行V操作的进程继续执行;如果S>0,则说明没有进程在该信号量的阻塞队列当中,因此,无需唤醒其他进程,该进程继续执行。

需要说明的是,信号量的初值一定是一个非负的整数,但是在运行过程中,信号量的值可正可负。

2利用信号量实现进程互斥

利用信号量实现进程互斥的进程可描述如下:

Var s:semaphore:=1;

/*设置信号量s的初值为1*/

begin

parbegin/*并发开始*/

process1:

begin

repeat

P(s);

critical section

V(s);

remainder section

until false;

end

process2:

begin

repeat

P(s);

critical section

V(s);

remainder section

until false;

end

parend

end

以上描述的是并发执行的两个进程process1和process2,这两个进程的临界区(critical section)对应的是一个临界资源,为了保证这两个进程能够互斥地使用临界资源,在每个进程的临界区前后分别加上对同一个信号量的P操作和V操作,就好象分别是关锁和开锁操作一样。我们将该信号量的初值设为1,无论哪一个进程先获得处理机,在进入临界区之前都要进行P操作,执行P操作后,信号量s的值为0,该进程可以继续执行;若该进程在临界区内失去处理机,而由另一个进程获得处理机执行时,执行的进程在进入临界区之前执行P操作时,信号量s的值就为-1,此时该进程就得阻塞,进入到信号量s的等待队列当中等待;当在临界区内的进程再次获得处理机继续执行后,退出临界区时,执行V操作,信号量s的值为0,此时它要去唤醒阻塞进程,然后继续执行或转进程调度。

用信号量实现进程互斥的特点:

(1)要找对临界区,范围小了会出错,范围大了会影响进程运行。

(2)P、V操作位于临界区前后,在一个进程里成对出现。

(3)2个进程对1个临界资源互斥使用时信号量初值为1,取值范围为-1,0,1。

(4) 当n个进程要互斥使用m个同类临界资源时(n>m),用信号量实现互斥时,信号量的初值应为m,即该类可用资源的数目。信号量的取值范围为-(n-m)~m。

(5) 当信号量s<0时,|s|为等待该资源的进程的个数;即因该资源而阻塞的阻塞队列中进程个数。

(6) 当信号量s>0时,s表示还允许进入临界区的进程数,即剩下的临界资源个数)。

(7) 执行一次P(s)操作,表示请求一个临界资源,s-1后,当s<0时,表示可用资源没有了,进程阻塞。

(8) 执行一次V(s)操作,表示释放一个临界资源,s+1后,若s<=0,表示还有进程在阻塞队列中,要去唤醒一个阻塞进程。

我们通过一个实例来进一步说明。有一个阅览室共100个座位,用一张表来管理它,每个表目记录座位号以及读者姓名。读者进入时要先在表上登记,退出时要注销登记。可以用信号量及其P、V操作来描述各个读者“进入”和“注销”工作之间的关系。

分析:由于一个座位在某一时刻只能分配给一个读者,所以对于多个读者来说,一个座位就是一个临界资源,100个座位即相当于此类临界资源有100个,可以设置一个信号量s1来管理座位,且其初始值为100。每个读者来后,首先要看看是否有座位,即对s1执行一次P操作,只要有座位,P操作后s1值大于等于0,此时就可以拿表来登记了。用一张表来管理这100个座位,每名读者进入或退出时都要在表上登记,并且每次只能有一个读者使用这张表,所以这一张表也相当于是临界资源,可以设置一个信号量s2来管理表格。所以一共要设置两个信号量分别用来管理这两类临界资源。

本例题的解决方法如下:

Vars1,s2:semaphore:=100,1;

/*设置两个信号量,分别对应座位和表这两个临界资源*/

parbegin

processreader(i)(i=1,2,……):

begin

P(s1);/*申请一个座位*/

P(s2);/*拿表进行登记*/

登记;

V(s2);/*登记后放回表*/

读书;

P(s2);/*拿表进行注销*/

注销;

V(s2);/*注销后放回表*/

V(s1); /*释放一个座位*/

end

parend

3利用信号量实现进程同步

可以通过一个例子来说明进程同步的实现。

例如,有一个缓冲区,某一个时刻只能存一个数据,计算进程P1将计算出的结果放入缓冲区,输出进程P2往外取数据输出,进程P1一旦放入数据后,必须等进程P2取出数据以后它才能继续往里放,否则会导致前一次放入的数据丢失;进程P2取出数据后,必须等进程P1放入下一个数据后它才能够继续取,否则会导致两次取出的是同一个数据。可见,这是一个典型的进程同步关系,进程P1和P2在协调着共同完成一个任务。

解决这个同步问题的进程描述如下:

Var s1,s2:semaphore:=0,0;

begin

parbegin

P1:

begin

repeat

获得数据;

计算;

送至缓冲区;

V(s1);

P(s2);

until false;

end

P2:

begin

repeat

P(s1);

从缓冲区中取数据;

输出;

V(s2);

until false;

end

parend

end

以上实现的是两个并发进程P1和P2的同步关系。这里设了两个信号量s1和s2,分别是两个进程用来进行相应的消息传递以便来实现同步的,一般实现同步的信号量的初值可以设为0。因为必须先计算,后输出,所以P1进程的执行要先于P2。如果P2先获得处理机,则P2要先执行一个P(s1)操作,由于s1的初值为0,所以执行P(s1)后,P2会阻塞;P1获得处理机后可以一直执行,当放完数据以后,它要执行V(s1),即看一下是否有进程在信号量s1的队列中等待,若有,它要去唤醒;然后,为了防止P1继续往缓冲区中放数据,在执行V(s1)操作之后,马上又执行P(s2),随即阻塞,直等到P2取完数据输出后执行V(s2)将其唤醒。

用信号量实现进程同步的特点:

(1) 配对的P、V操作分别在不同的进程里。有的时候P操作和V操作的个数并不相等。

(2) 初值一般为0,需要设一个以上的信号量(例如2个进程同步,需要设2个信号量,分别用来传递信息)。

(3) 在实现进程同步时,需要分析哪个进程不可以先执行,在不允许直接进行的操作前面加上P操作来进行条件限制。并在使其操作成为可能的其他进程的操作后面加上对同一个信号量的V操作。

我们通过一个实例来进一步说明。A、B两组学生进行投球比赛,规定一个组学生投一个球后应让另一个组学生投球,假设让A组同学先投,试写出A、B两个进程。

由题意分析可知,一个组学生投一个球的前提条件是另一个组的学生投球之后,即有条件制约,同样,另一个

组学生投球也受到该组学生投球的条件制约,由此可知该问题是一个进程同步的问题。所以,要在有条件制约的投球动作前加上一个P操作,即条件不满足时就阻塞;在投球动作结束后,要加上一个V操作,即自己的投球动作完成之后,使另一组学生的投球动作成为可能。

解决这个同步问题的进程描述如下:

方法一:

Var s1,s2:semaphore:=0,0;

parbegin

process A: