同步问题要有一定的基础,所以建议大家先看看这个:
同步问题的概念说明
案例说明:
生产者-消费者问题
问题说明:有一群生产者进程在生产产品,并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行,在两者之间设置了一个具有n个缓冲区的缓冲池,生产者进程将它所生产的产品放入一个缓冲区中;消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的,但它们之间必须保持同步,即不允许消费者进程到一个空缓冲区去取产品;也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。
用记录型信号量来解决生产者-消费者问题
分析:
1、互斥资源——缓冲区、计数器;设互斥信号mutex实现进程对缓冲池的互斥使用以及计数器的加减操作(mutex互斥信号的加入说明,在落锁之后,也就是用程序在对资源池操作,其他的程序无论是生产者还是消费者,都不能对资源进行操作)
2、资源信号量——缓冲池;用empty和full分别表示缓冲池中空缓冲池和满缓冲池的数量
思路:只要缓冲池没满,生产者就可在里面放入产品;只要缓冲池不是空,消费者就可以在缓冲池中取走产品。
源代码:
int in=0,out=0;
item buffer[n];//n个缓冲区
Semaphore mutex=1,empty=n, full=0;
void producer(){
do{
producer an item nextp; //产一个产品
wait(empty); //empty减1
wait(mutex);//加锁
//这里有一个顺序问题,就是要先wait(empty)再wait(mutex),不然已经落锁之后,所有的产品都进不来,那就没戏了。
buffer[in]=nextp;
in=(in+1) % n; //移动生产指针
signal(mutex);//解锁
signal(full); //full增1
}while(true)
}
void consumer(){
do{
wait(full);
wait(mutex);
nextc=buffer[out];
out= (out+1) %n;
signal(mutex);
signal(empty);//empty减一
consumer the item in nextc;
……
}while(true)
}
注意点:
1、在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现;
2、对资源信号量empty和full的wait和signal操作,同样需要成对地出现,但它们分别处于不同的进程中。例如,wait(empty)在生产进程中,而signal(empty)则在消费进程中,生产进程若因执行wait(empty)而阻塞, 则以后将由消费进程将它唤醒;
3、在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作,然后再执行对互斥信号量的wait操作,否则可能引起进程死锁
-------------------------------------------------------------------------
用AND信号来做
int in=0,out=0;
item buffer[n];
Semaphore mutex=1,empty=n, full=0;
void producer(){
do{
producer an item nextp; //产一个产品
Swait(empty,mutex);
buffer[in]:=nextp;
in:=(in+1) % n; //移动生产指针
Ssignal(mutex,full); //解锁
}while(true)
}
void consumer(){
do{
Swait(empty,mutex);
nextc:=buffer[out];
out:= (out+1) %n;
Ssignal(mutex,full); //解锁
consumer the item in nextc;
……
}while(true)
}
-----------------------------------------------------------------------
用管程来解决生产者-消费者问题
建立一个管程prodducerconsumer PC
(1) put(x)过程,生产者利用该过程将产品放入缓冲池,并用整型变量count表示缓冲池中已有的产品数目,count>=N时,表示缓冲池满,生产者必须等待
(2)get(x)过程,消费者利用该过程从缓冲池中取出一个产品,当count<=0时,表示缓冲池中无可取用的产品,消费者进程必须等待
Monitor producerconsumer{
item buffer[N];
int in,out;
condition notfull, notempty;
int count;
public :
void put(item x){//放操作
if(count>=N)
cwait(notfull);
buffer[N]=x;
in =(in+1)%N;
count++;
csignal(notempty);
}
void get(item x){//取操作
if(count<=N)
cwait(notempty);
x=Buffer[N];
out =(out+1)%N;
count--;
csignal(notfull);
}
{//用来初始化原来的数据
in=0;
out=0;
count=0;
}
}pc
void producer(){
item x;
while(TRUE){
producer an item nextp; //产一个产品
PC.put(x);
}
}
void consumer(){
item x;
while(TRUE){
PC.get(x);
consumer the item in nextc;
……
}
}
同步问题归纳
1.利用信号量解决临界区互斥执行问题
2.利用信号量解决资源分配问题
3.利用信号量解决进程同步问题-(一)单向同步
4.利用信号量实现解决同步问题-(二)双向同步
一、利用信号量解决临界区互斥执行问题
例1 问题描述:考虑n个进程访问临界资源的应用,用信号量实现临界区互斥执行的代码框架如下:
semaphore mutex=1; //即mutex.value=1,可将mutex看成锁状态变量,
//初始化为1,表示开锁状态,mutex≤0为上锁状态
process_1( )
{
while(1) {
wait(mutex);
<<critical section>>
signal(mutex);
<< remainder section >>
}
……..
process_n( )
{
while(1) {
wait(mutex);
<<critical section>>
signal(mutex);
<< remainder seetion >>
}
规律:
①初值mutex=1
②wait(mutex): 请求临界资源许可权
③signal(mutex): 归还临界资源许可权
④mutex≤0为资源忙,mutex=1资源空闲
⑤mutex<0时,|mutex|表示 等待资源的进程的数目
⑥mutex+等待进程数+临界区进程数=?
⑦mutex值的变化范围是?
总结:
(1)根据应用需求,写出并发进程(线程)代码框架
(2)识别临界资源与临界区(代码段)
(3)对每种临界资源,定义一个信号量(互斥信号量通常取名为mutex),初值为1
(4)在每个进程临界区前,增加针对相关临界资源信号量的P操作(wait函数),表示申请对临界资源的访问许可权(或读临界资源加锁)
(5)在每个进程临界区后,增加针对相关临界资源信号量的V操作(wait函数),表示归还对临界资源的访问许可权(或对临界资源开锁)
二、利用信号量解决资源分配问题
例2 问题描述:一个网络聊天室能容纳100人,每个聊友活动看成一个进程(或线程),函数enter()、exit()分别表示进入、退出聊天室,用信号量实现聊天室座位分配.程序为:
semaphore seats=100;//初始化为100,表示开始时聊天室100个座位全空
process_1( ) ///第1个聊友
{
while(1) {
wait(seats);
enter(); //<<进入聊天室>>
chat(); <<聊天>>
exit(); //<<退出聊天室>>
signal(seats);
}
……..
process_n( ) //第n个聊友
{
while(1) {
wait(seats);
enter(); //<<进入聊天室>>
chat(); //<<聊天>>
exit(); //<<退出聊天室>>
signal(seats);
}
规律:
①初值seats ≥1,空座位数
②wait(seats):请求分配资源,返回即已获得资源
③signal(seats):归还资源
④seats=0时,空座数为0,无等待进程
⑤seats <0时,|seats|表示 还有多少个人等待空座位资源的分配
⑥seats +等待聊友数+聊天室聊友数=?
总结:
(1)根据应用需求,写出并发进程(线程)代码框架
(2)识别待分配资源与资源访问代码段
(3)对每种资源,定义一个信号量,初值为资源数
(4)在每个进程涉及资源使用代码前,增加针对相关资源信号量的P操作(wait函数),表示申请一个资源
(5)在每个进程涉及资源使用代码后,增加针对相关资源信号量的V操作(signal函数),表示归还对一个资源
三、利用信号量解决进程同步问题——单向同步问题(就是多个进程王城一个任务,一个任务需要多个资源的问题)
例3 问题描述(多进程合作完成一项任务):孩子身上携带一个GPS位置跟踪器,后台计算机中的线程thread1每隔15秒执行函数getloc() 采集一次孩子位置数据,存入变量loc=getloc(),线程thread2对孩子位置进行分析处理:analyze(loc),包括异常报警等。程序框架为:
semaphore avail=0;//初始化为0,表示开始时尚未采集到位置数据
Thread_1( ) //位置采集线程
{
while(1) {
loc=getloc();//采集位置数据
signal(avail);//产生一个事件,也就是说明采集数据这件事已经做了,告诉下一个处理线程说你可以开始处理了
sleep(15);
}
}
……..
Thread_2( ) //位置处理线程
{
while(1) {
wait(avail);//接收到位置线程的信号,开始处理位置信息数据
analyze(loc);//分许位置,异常处理
}
}
规律:①初值avail=0,事件未发生
②wait(avail): 等待、消耗事件
③signal(avail): 产生事件
④avail=1时, avail表示事件已经发生
⑤avail <0时,|avail|表示?
⑥avail+等待线程数=事件发生与否编码
总结:
(1)根据应用需求,写出并发进程(线程)代码框架
(2)识别两进程关联操作及同步事件(所有)
(3)对每种同步事件,定义一个信号量并设置初值,已经发生时间对应信号量初值为1,未发生事件对应信号量初值为0
(4)在产生事件的操作代码后添加相应信号量V操作
在等待事件操作代码前添加相应信号量的P操作
四、用信号量解决同步问题——双向同步
典型例题就是我们文章一开始的生产者-消费者问题,这里我就不重复了。