进程的同步与通信.docx
《进程的同步与通信.docx》由会员分享,可在线阅读,更多相关《进程的同步与通信.docx(60页珍藏版)》请在冰点文库上搜索。
进程的同步与通信
第3章进程的同步与通信
3.基本点、重点和难点
在多道程序系统中,程序的执行失去了封闭性和再现性,程序的运行具有不确定性,这是我们所不希望看到的。
如果多道程序系统中程序的执行不加控制,程序的每次执行就可能得到不同的结果。
如何使多道程序的执行的结果具有再现性和确定性?
这就需要通过进程间的同步和互斥来实现,将原来无序的、不确定的程序的执行转换为有序的、确定的执行。
解决同步和互斥问题最常用的方法就是信号量的方法,通过在程序中使用P、V操作到达同步和互斥的目的。
在使用信号量和P、V操作时,很多学生觉得无从下手,感到困惑。
这主要是因为他们对进程的本质理解还不够深入、对多道程序设计的原理还不够清楚、对信号量的含义还不够明白造成的。
但这局部内容又是各类考试的必考点。
本章有很多经典问题,其解题的方法和答案在很多资料上都可以见到。
但这些解题的结果是专家们长期精炼而成的,初学者在开始时不可能得到这样的结果。
对于初学者而言,迫切想知道的已不单是解题的结果,而是问题解决的思考和分析过程。
为此,本章中对一些问题的解答给出了详细的分析过程。
3..进程的同步和互斥的概念
.同步(Synchronization)
相互合作的进程需要在某些点上协调,先到达某点的进程需要等待后到达的进程,进程间的这种协调关系叫同步。
2.互斥(Mutex)
互斥是一种特殊的同步方式。
当多个进程需要使用相同的资源,而此资源在任一时刻却只能供一个进程使用,获得资源的进程可以继续执行,没有获得资源的进程必须等待。
进程间的这种相互排斥关系叫互斥。
3.临界资源与临界区(CriticalResourceandCriticalSection)
临界资源是一次只允许一个进程使用的资源。
临界区是在进程中操作临界资源的程序段。
3..2锁操作法实现互斥
1.基本思想
实现互斥的基本思想是使多个进程不能同时进入临界区。
给每个临界资源分配一个锁:
锁翻开时,进程进入临界区,将锁关闭,开始操作临界资源,离开临界区时,将锁翻开;锁关闭时,需要进入临界区的进程要等待。
2.操作锁的步骤
(1)确定临界资源;
(2)确定临界区;
(3)确定锁个数;
(4)设置锁操作。
3..3信号量与P、V操作
.信号量的引入
965,荷兰学者Dijkstra提出的信号量机制是一种卓有成效的进程同步工具。
在长期且广泛的应用中,信号量机制得到了很大的开展:
它从整型信号量经记录型信号量,进而开展为“信号量集”机制。
现在的信号量机制已被广泛的应用于单处理机、多处理机系统和计算机网络中。
2.信号量(Semaphore)
设S为信号量,可以将S看成一个信号灯,但S能比信号灯表达更丰富的含义。
(1)当S>0时,是绿灯,进程看到绿灯可以通过。
S值越大,通过进程的能力越大,供进程使用的相关资源越多。
S值反映了可供进程使用的相关资源的数量。
(2)当S<=0时,是红灯,进程看到红灯需要等待。
此时|S|表示等待S信号的进程的个数。
3.信号量的操作
最初由Dijkstra把整型信号量定义为一个整型量,除初始化外,仅能通过两个标准的原子操作Wait(S)和Signal(S)来访问,其它方法都不能操作信号量。
这两个操作很长时间以来,一直被分别称为P、V操作,因为希腊语的Wait词头为P,Signal的词头为V。
对信号量的操作定义如下:
(1)P(S)或Wait(S):
是等待信号的操作,是查看信号的操作,是看灯操作。
假设为绿灯,进程继续前进;假设为红灯,进程必须等待。
在该操作中,进行S=S,操作使S的值向负方向转化,即操作使信号灯S向红的方向转化。
(2)V(S)或Signal(S):
是发送信号的操作。
在该操作中,进行S=S+,操作使S的值向正方向转化,即操作使信号灯S向绿的方向转化。
4.P(S)、V(S)的实现
()整型信号量
P(S):
whiles<=0donoop
S:
=S;
V(S):
S:
=S+;
(2)记录型信号量
在整型信号量机制中的wait操作,只要是信号量S<=0,就会不断地测试。
因此,该机制并未遵循“让权等待”的准则,而是该进程处于“忙等”的状态。
记录型信号量机制则是一种不存在“忙等”问题的进程同步机制。
但在采取了“让权等待”的策略后,又会出现多个进程等待访问同一临界资源的问题。
为此,在信号量机制中,除了需要一个用于代表资源数目的整型变量value外,还应增加一个进程链表L,用于链接或记录上述的所有因此信号量而等待的进程。
记录型信号量是由于它采用了纪录型的数据结构而得名的。
它所包含的上述两个数据项可描述为:
typesemaphore=record
value:
integer;
L:
listofprocess;
End
相应地,wait(s)和singal(s)操作可描述为:
Procedurewait(s)
vars:
semaphore;
Begin
S.value:
=S.value;
IfS.value<0then
Begin
Insert(*,S.L);
Block(*);
End
End
Proceduresignal(s)
varS:
semaphore;
Begin
S.value:
=S.value+;
IfS.value<=0then
Begin
N=remove(S.L);
Wakeup(N);
End
End
每次的wait操作,意味着进程请求一个单位的资源,因此描述为S.value:
=S.value;当S.value<0时,表示资源已分配完毕,进程需要等待而进入阻塞状态。
为了便于唤醒,在当前进程需要进入阻塞状态前,将当前进程号插入到信号量链表S.L中,进程调用block原语,进行自我阻塞,放弃处理机。
因为只有在S.value<0时进程才进入阻塞状态,所以当S.value<0时,S.value的绝对值表示在该信号量阻塞进程链表中进程的数目。
每次signal操作,表示执行进程释放一个单位资源,故S.value:
=S.value+操作表示资源数目加。
假设加后仍是S.value<=0,则表示在该信号量链表中,仍有等待该资源的进程被阻塞,故还应从该信号量链表中移出一个进程,调用wakeup原语将该进程唤醒。
3..4信号量实现进程的同步与互斥
.利用信号量实现互斥
当信号量用于互斥时,信号量mutex的含义是进程是否可以操作临界资源,进程是否可以进入临界区。
mutex>0时,进程可以操作临界资源,可以进入临界区,否则mutex<=0时进程必须等待。
为了使多个进程能互斥地访问某临界资源,只需为该临界资源设置互斥信号量mutex。
如果每次只允许一个进程操作临界资源,其初值为;如果最多允许k个进程使用某个资源,信号量的初值为k。
然后将各进程的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。
这样,每个欲访问该临界资源的进程,在进入临界区之前,都要对mutex执行wait操作。
假设该资源此刻未被访问,本次wait操作成功,进程便可进入自己的临界区,这时假设有其他的进程欲进入自己的临界区,进程执行wait操作必然阻塞,从而保证了该临界资源被互斥访问。
当访问临界资源的进程退出临界区后,进程对mutex执行signal操作,释放该临界资源。
要注意的是,在利用信号量机制实现进程互斥时,wait(mutex)和signal(mutex)必须成对出现。
缺少wait(mutex)将会导致系统混乱,不能保证对临界资源的互斥访问;而缺少signal(mutex)将会使临界资源永远不被释放,从而使等待该资源而阻塞的进程永远不能被唤醒。
2.利用信号量实现同步
当信号量用于互斥时,信号量S的含义是某事件是否发生,某条件是否满足。
下面看一下如何用信号量来描述程序或语句之间的前趋关系。
设有两个并发执行的进程P和P2。
P中有语句S;P2中有语句S2。
如果我们希望执行S后再执行S2。
为实现这种前趋关系,我们只需使进程P和P2共享一个公用信号量S,并赋予其初值为0,将signal(s)操作放在S后面;而在S2语句前面插入wait(s)操作,即:
在进程P中,S;signal(s)
在进程P2中,wait(s);S2
S的含义是S语句是否执行:
S执行后,信号量S>0;,S没有执行时,信号量S<=0。
初始状态S语句没有执行,因此S<=0。
因为S执行后S应变成大于0的值,所以S应被初始化为0。
这样,假设P2先执行必定阻塞自己,只有在进程P执行完S;signal(s)后,使S增为时,P2进程才能执行语句S2。
同样,可以利用信号量,按以以下图语句间的前趋关系,写出一个可并发执行的程序。
详细描述如下:
vara,b,c,d,e,f,g:
semaphore:
=0,0,0,0,0,0,0;
begin
parbegin
beginS;signal(a);signal(b);end;
beginwait(a);S2;signal(c);signal(d);end;
beginwait(b);S3;signal(e);end;
beginwait(c);S4;signal(f);end;
beginwait(d);S5;signal(g);end;
beginwait(e);wait(f);wait(g);S6;end;
parend
end
图4.进程前趋关系图
3.解决同步和互斥问题的步骤
(1)确定并发和顺序操作
哪些操作是并发的?
哪些操作是顺序的?
这是解决同步和互斥问题时首先要确定的。
并发操作可以用多个进程实现,同步和互斥就发生在这多个进程之间。
多个进程操作同一临界资源就是进程间的互斥问题,多个进程要按一定的顺序进行操作就是进程间的同步问题。
(2)确定互斥和同步的规则
分析具体问题,确定同步和互斥的基本方式,确定能够进行正确操作的条件,在这些条件中隐含着同步和互斥的规则。
(3)确定同步、互斥的操作流程
按操作的步骤,写出每个进程操作的流程
(4)确定信号量的个数和含义
根据同步和互斥规则以及操作流程确定信号量的个数,确定信号量代表的含义,只有确切地知道信号量所代表的含义,设置这个信号量才有意义。
(5)确定信号量的初值
同步信号量的初值则要根据进程的初始状态确定,具体问题要具体分析,没有统一的方法。
(6)确定P、V操作的位置
根据同步和互斥规则和每个进程的操作流程就可以确定P、V操作的位置。
需要说明的是无论是互斥问题还是同步问题,只要是需要进程进入阻塞状态,就必须想到在什么时候将进程唤醒。
初学者开始时可以按上述步骤解决同步和互斥问题,熟练后,就可以不局限于这些规则,灵活应用。
这好象学骑自行车一样,开始时需要左看右看,掌握了基本要领,熟练操作以后就可以随心所欲。
以上讲述的只是一般的求解规则,虽然有一定的可操作性,但在实际应用中还是要针对具体情况,多做多想,领悟出其中的原理和窍门。
4.同步和互斥的经典问题
(1)生产者和消费者问题(PCP:
ProducerConsumerProblem)。
例如,消息缓冲通信的管理。
(2)读者和写者问题(RWP:
ReaderWriterProblem)。
例如,共享文件的读写问题。
(3)哲学家进餐问题(DPP:
DiningPhilosopherProblem)。
例如,进程对多类资源的竞争使用。
3.2例题解析
例3.2.多道程序系统程序的执行失去了封闭性和再现性,因此多道程序的执行不需要这些特性,这种说法是否正确?
解这种说法不正确。
可以想象,如果一个程序在多道程序系统中,在相同的输入的情况下,屡次执行所得结果是不同的,有谁还敢使用这个程序?
因此,多道程序的执行也需要封闭性和再现性,只不过单道程序系统的封闭性和再现性是先天固有的,多道程序系统的程序执行要想获得封闭性和再现性,需通过程序员的精心设计才能得到。
所使用的方法就是同步和互斥的方法。
例3.2.2多个进程对信号量S进行了5次P操作,2次V操作后,现在信号量的值是3,与信号量S相关的处于阻塞状态的进程有几个?
信号量的初值是多少?
解
(1)因为S的当前值是3,因此因为S处于阻塞状态的进程有3个;
(2)因为每进行一次P(S)操作,S的值都减,每执行次V操作S的值加,故信号量的初值为3+52=0;
例3.2.3如下锁的实现方法存在什么缺点?
如何改进?
LOCK(X)UNLOCK(X)
{{
dowhileX=;X=0;
X=
}}
解存在的缺点是:
当锁是关闭时,采用的是循环等待的方法,这样的等待还是要占用处理机的时间,应该采用阻塞等待的方法。
改进的锁实现如下:
LOCK(X)UNLOCK(X)
{{
ifX.value=ifnotempty(X.L)
{insert(*,X.L);{P=remove(X.L);
Block(*)Wakeup(P)
}}
elseX.Value=elseX.Value=0
}}
这里X.value是锁的值,X.L是存放由于锁X而阻塞的进程的队列。
insert(*,X.L)将当前进程的进程号插入到X.L,remove(X.L)是从X.L中移出一个进程号。
例3.2.4使用多个进程计算Y=F(X)+F2(X).
解
(1)确定并发和顺序操作
在这个问题中,F(X)和F2(X)的计算是可以并行处理的,因此F(X)和F2(X)可以分别出现在两个进程中。
(2)确定互斥或同步的规则
在F(X)+F2(X)中,必须在F(X)和F2(X)计算完毕,才能进行加法运算,因此本问题是同步问题。
(3)同步的操作流程
〈进程main〉
创立进程p来计算F(X);
创立进程p2来计算F2(X);
F(X)计算是否完成?
没有,等待;
F2(X)计算是否完成?
没有,等待;②
进行加法运算。
〈进程p〉
y=F(X);
设置F(X)计算完成标志;③
〈进程p2〉
y=F2(X);
设置F2(X)计算完成标志。
④
(4)确定信号量的个数和含义
根据同步规则以及操作流程确定信号量的个数是2个,S和S2:
S含义是F(X)计算是否完成;
S2含义是F2(X)计算是否完成。
(5)确定信号量的初值
S=0;
S2=0。
(6)确定P、V操作的位置
上面处是一个P操作,P(S);
上面②处是一个P操作,P(S2);
上面③处是一个V操作,V(S);
上面④处是一个V操作,V(S2)。
解法
Main()
Publicy,y,y2,.P,P2
SemaphoreS,S2
{
S=0;
S2=0;
P=Creat(NF,F,x,……);
P2=Creat(NF2,F2,x,……);
P(S);
P(S2);
y=y+y2;
}
ProcedureF(x)
{
y=计算;
V(S);
}
ProcedureF2(x)
{
y2=计算2;
V(S2)
}
解法2
Main()
Publicy,y,y2,.P,x
SemaphoreS
{input(x);
S=0;
P=Creat(NF,F,x,……);
Y2=F2(x);
P(S);
y=y+y2;
}
ProcedureF(x)
{
y=计算;
V(S)
}
采用2个进程和个信号量来实现Y=F(X)+F2(X)的时候,采用的方法是父进程创立子进程,F(X)在子进程中计算,F2(X)在父进程中计算,因此F(X)和F2(X)计算仍然是并发进行的。
S信号量的含义为F(X)是否完成。
改进的方法比原来的方法节约一个进程和一个信号量,但并发操作的程度并没有降低。
生产者—消费者问题演变。
情况一个buffer,一个生产者,一个消费者,生产者只生产一个东西,消费者只进行一次消费,即:
生产者只进行一次putdata操作,消费者只进行一次getdata操作。
解这是一个同步问题,生产者和消费者分别是2个并发的进程。
()操作规则
如果buffer为空,则消费者只能等待。
(2)操作流程
<生产者>
{
putdata;
设置Buffer有数据标志V(S)
}
<消费者>
{
判断buffer是否有产品,没有则等待;
getdata;
}
(3)信号量
设置个信号量full,full表示buffer是否有数据,初值为0。
(4)P、V操作实现
varfull:
semaphore:
=0;
buffer:
array[]ofitem;
begin
parbegin
producer:
begin
putdata;
V(full);
end
consumer:
begin
P(full);
getdata;
end
parend
end
情况2一个buffer,一个生产者,一个消费者,生产者不断地进行putdata操作,消费者不断地进行getdata操作,即:
生产者不断地生产,消费者不断地消费
(1)操作规则
只有buffer为空时才能进行putdata操作;只有buffer有数据时才能进行putdata操作。
(2)操作流程
<生产者>
{
repeat
判断buffer是否为空,不空则等待;
putdata;
设置buffer有数据的标志;
untilfalse
}
<消费者>
{
repeat
判断buffer是否有数据,没有数据则等待;
getdata;
设置buffer为空标志;
untilfalse
}
(3)信号量
设置2个信号量full和empty。
full表示buffer是否有数据。
因为进程在初始状态时,buffer中没有数据,故初值为0,变化范围~。
empty表示buffer是否为空。
因为进程在初始状态时,buffer为空,故初值为0初值为,变化范围~。
(4)P、V操作实现
varfull:
semaphore:
=0;
emptyl:
semaphore:
=;
buffer:
array[]ofitem;
begin
parbegin
producer:
begin
repeat
P(empty);
putdata;
V(full);
untilfalse
end
consumer:
begin
repeatP(full);
getdata;
V(empty);
untilfalse.
end
parend
end
情况3一个buffer,多个生产者,多个消费者,多个生产者和消费者都在不断地存取buffer,即生产者不断地进行putdata操作,消费者不断地进行getdata操作。
(1)操作规则
只有buffer为空时才能进行putdata操作;只有buffer有数据时才能进行putdata操作。
这时buffer变成了临界资源,不允许多个进程同时操作buffer,即不允许多个消费者同时进行gedata,不允许多个生产者同时进行putdata操作。
(2)操作流程
<生产者>
{
repeat
判断buffer是否为空,不则等待;
是否可操作buffer;
putdata;
设置buffer可操作标志;
设置buffer有数据的标志;
untilfalse
}
<消费者>
{
repeat
判断buffer是否有数据,没有则等待;
是否可操作buffer;
getdata;
设置buffer可操作标志;
设置buffer为空标志;
untilfalse
}
(3)信号量
设置3个信号量full、empty和BM。
full表示buffer是否有数据,初值为0;
empty表示buffer是否为空,初值为;
BM表示buffer是否可操作,初值为。
由于buffer只有一个,full和empty可以保证对buffer的正确操作,故BM是多余的,可以省略。
(4)P、V操作实现
<生产者><消费者>
{{
repeatrepeat
P(empty);P(full);
P(BM); P(BM);
putdata;getdata;
V(BM); V(BM);
V(full);V(empty);
untilfalse.untilfalse
}}
情况4多个生产者,多个消费者,N个buffer,屡次循环存取buffer,即,即多个生产者不断地进行putdata操作,多个消费者不断地进行getdata操作。
()操作规则
只有buffer有空间才能进行putdata操作;
只有buffer有数据才能进行putdata操作;
这时buffer变成了临界资源,不允许多个消费者和生产者同时对同一个buffer进行gedata和putdata操作。
(2)操作流程
<生产者>
{
repeat
判断buffer是否有空间,没有则等待;
是否可操作buffer;
putdata;
设置buffer可操作标志;
设置buffer有数据的标志;
untilfalse
}
<消费者>
{
repeat
判断buffer是否有数据,没有则等待;
是否可操作buffer;
getdata;
设置buffer可操作标志;
设置buffer有空间标志;
untilfalse
}
(3)信号量
full表示buffer是否有数据,初值为0;
empty表示buffer是否为空,初值为N;
BM表示buffer是否可操作,初值为。
(4)P、V操作实现
<生产者><消费者>
{{
repeatrepeat
P(empty);P(full);
P(BM); P(BM);
putdata;getdata;
V(BM); V(BM);
V(full);V(empty);
untilfalseuntilfalse
}}
(5)改进的P、V操作实现
在上述的实现中,putdata和getdata操作都在临界区中,因此多个进程对多个buffer的操作是不能并发进行的,进程间并行操作的程度很低。
实际上只要保证多个进程同时操作不同buffer就可以实现对整个buffer的并行操作。
因此,只要保证为不同的进程分配不同buffer,putdata和getdata操作是可以同时进行。
这样互斥不是发生在对buffer的存取操作上,而是发生在对buffer的分配上,这个时间与存取buffer的时间相比是较短的,因此减少了进程处于临界区的时间。
这里引入2个函数:
getE_buffer(),返回值是空的buffer号;
getD_buffer(),返回值是有数据的buffer号。
getE_buffer()和getD_buffer()通过将buff