课堂笔记与思考归纳
①生产者-消费者问题
1.标准问题
多个生产者,多个消费者通过共享包含n个缓冲区的缓冲池Buffer协作,其中生产者负责生产数据并投入缓冲池,消费者从缓冲池中取得数据消费,生产者与消费者每次生产/消费一个数据,要求每个数据必须且只被消费一次,缓冲池为临界资源
- 每个数据必须且只被消费一次
- 缓冲池是临界资源
- 必须先生产后访问
可以将有界缓冲池理解成一个循环缓冲区(循环队列)
所有的生产者执行入队操作,所有的消费者执行出队操作
生产者与消费者各设置一个进程
但是不意味着只有两个进程,相当于生产者有一组进程,消费者有一组进程,但是由于行为相同,故各定义1个进程即可
- 生产者生产的数据不一定能放入有界缓冲池(如果缓冲池内都装满了数据就无法放入)
- 为两个进程设置不同的资源
- 生产者进程 : 空缓冲区资源
- 消费者进程 : 满缓冲区资源
需要为两个进程设置两个信号量
即empty与full
empty的初值设定为n,而full的初值设定为0
生产者进程
Producer:
begin
repeat
produce an item in nextp ;
wait( empty ) ;
Buffer(in) := nextp ;
in := (in + 1 ) mod n ;
signal( full ) ;
until flase
end
消费者进程
Consumer:
begin
repeat
wait( full ) ;
nextc = Buffer(out);
out := (out + 1 ) mod n ;
signal( empty ) ;
consume the item nextc ;
until flase
end
问题
- 有界缓冲池是临界资源,上述代码可能会造成多个进程同时访问临界资源
解决 : 必须要对访问缓冲池的代码构造临界区,即设置互斥信号量mutex,mutex初值为1
修改后的生产者代码(消费者也要修改)
也就是说在一个进程在访问缓冲池的情况下其他进程都会被阻塞,实现互斥
Producer:
begin
repeat
produce an item in nextp ;
wait( empty ) ;
wait( mutex ) ;
Buffer(in) := nextp ;
in := (in + 1 ) mod n ;
signal( mutex ) ;
signal( full ) ;
until flase
end
消费者代码
Consumer:
begin
repeat
wait( full ) ;
wait( mutex ) ;
nextc = Buffer(out);
out := (out + 1 ) mod n ;
signal( mutex ) ;
signal( empty ) ;
consume the item nextc ;
until flase
end
2.单生产者,单消费者,多缓冲
在标准问题上如何简化?
简化1尝试 : 能否去除mutex?
不能
考虑以下情况:缓冲池中一半放满了资源,另一半是空的
可能会导致一个生产者往缓冲池内放数据的同时,一个消费者在从缓冲池内读取数据,这违背了互斥 , 因为缓冲池依旧是临界资源
简化2尝试 : 能否去除empty与full?
不能
因为empty与full两个信号量要用来追踪不同资源的数量
3.多生产者,多消费者,单缓冲
简化1尝试: 能否去除empty与full?
不能,因为要保证顺序
简化2尝试: 能否去除mutex?
可以
这里观察一下empty与full,发现它们两个实际上组成了互斥信号量
empty与full的最大值都为1,不需要额外的互斥信号量mutex
4.允许生产者写时,消费者可读(相当于取消了缓冲池是临界资源这个条件)
- 缓冲池不再是临界资源
简化1尝试 : 能否去除mutex?
不能去除mutex,但是可以改变mutex
分为两个mutex,mutexP与mutexC
生产者共享mutexP,消费者共享mutexC
这是因为生产者与消费者不互斥,但是生产者之间需要互斥,消费者之间需要互斥。两个生产者同时访问资源时,因为不同生产者修改的都是同一指针指向的同样位置,那么这个指针其实就相当于一个临界资源
5.当缓冲区无限大
简化1尝试 : 能否去除empty?
可以
之前生产者通过empty来判断缓冲池是否满,满了则无法往缓冲池中放入资源,但是目前的情况是缓冲区无限大
也就是说无论往缓冲池中放入多少资源,也不会满
因此可以不需要empty
简化1尝试 : 能否去除full?
不能,同样的道理,因为消费者需要有资源的条件下才能进行消费
因此当缓冲池中没有资源的时候,消费者就无法进行消费
消费者通过full判断缓冲区中是否有资源
6.调整生产者wait顺序(消费者不变)
将wait( mutex ) ;
与wait( empty ) ;
顺序调换
Producer:
begin
repeat
produce an item in nextp ;
wait( mutex ) ;
wait( empty ) ;
Buffer(in) := nextp ;
in := (in + 1 ) mod n ;
signal( mutex ) ;
signal( full ) ;
until flase
end
问题
考虑以下情况
假如在某个特殊的时刻,系统的缓冲池放满了数据,意味着空缓冲区的资源为0(没有空的)
empty=0 , full=n
此时下一个生产者进入之后执行wait(mutex),然而wait(empty)的时候发生阻塞,而后续的多个生产者也会被阻塞
而消费者也会被阻塞,导致了所有生产者与消费者都被阻塞了,导致进程出现死锁
满足以下条件时该并发程序会出大问题
- 缓冲池全满
- 在此情况下调动的第一个进程为生产者进程
6.调整消费者wait顺序(生产者不变)
Consumer:
begin
repeat
wait( mutex ) ;
wait( full ) ;
nextc = Buffer(out);
out := (out + 1 ) mod n ;
signal( mutex ) ;
signal( empty ) ;
consume the item nextc ;
until flase
end
问题
与上一个问题类似,满足两个条件会导致死锁
- 有界缓冲池为空
- 在该情况下第一个调度的程序为消费者
7.上述两个问题叠加,一起换序会不会负负得正?
想啥呢 ,死锁中的死锁,锁中锁
②读者写者问题
多个读者,多个写者共享资源,允许多个读者同时访问资源,写者写的时候不允许其他进行读或写(互斥访问资源)
分析
- 读者进程 : 不控制
- 写者进程 : 互斥
- 读者与写者的顺序 : 不考虑
读者进程
Reader:
begin
repeat
wait( wmutex ) ;
perform read operation ;
signal( wmutex ) ;
until flase
end
写者进程
Writer:
begin
repeat
wait( wmutex ) ;
perform write operation;
signal( wmutex ) ;
until flase
end
因为有读者在进行读写的时候不能进行写操作,所以第一个读者与后续n个读者就有区别了
- 第一个读者完成读写后告诉写者可以进行写操作,而后续读者完成不需要
因此要判断该读者是第一个读者,还是后续读者 - 设置readcount全局变量,用来追踪当前正在访问数据文件的读者的数量
Reader:
begin
repeat
if ( readcount = 0 ) wait( wmutex ) ;
readcount := readcount + 1 ;
perform read operation ;
readcount := readcount - 1 ;
if ( readcount = 0 ) signal( wmutex ) ;
until flase
end
问题
- readcount相当于一个临界资源,然而该变量被多个读者进程共享,因为读者进程不仅访问readcount变量还会修改,因此要额外设置临界区
尝试1:设置大临界区
Reader:
begin
repeat
wait( rmutex ) ;
if ( readcount = 0 ) wait( wmutex ) ;
readcount := readcount + 1 ;
perform read operation ;
readcount := readcount - 1 ;
if ( readcount = 0 ) signal( wmutex ) ;
signal( rmutex ) ;
until flase
end
不可以
因为这样导致了读进程之间的互斥
正解
Reader:
begin
repeat
wait( rmutex ) ;
if ( readcount = 0 ) wait( wmutex ) ;
readcount := readcount + 1 ;
signal( rmutex ) ;
perform read operation ;
wait( rmutex ) ;
readcount := readcount - 1 ;
if ( readcount = 0 ) signal( wmutex ) ;
signal( rmutex ) ;
until flase
end
Q.E.D.
Comments | 0 条评论