课堂笔记与思考归纳

①生产者-消费者问题

1.标准问题

多个生产者,多个消费者通过共享包含n个缓冲区的缓冲池Buffer协作,其中生产者负责生产数据并投入缓冲池,消费者从缓冲池中取得数据消费,生产者与消费者每次生产/消费一个数据,要求每个数据必须且只被消费一次,缓冲池为临界资源
批注 20200317 123741.jpg

  • 每个数据必须且只被消费一次
  • 缓冲池是临界资源
  • 必须先生产后访问

可以将有界缓冲池理解成一个循环缓冲区(循环队列)
所有的生产者执行入队操作,所有的消费者执行出队操作

生产者与消费者各设置一个进程

但是不意味着只有两个进程,相当于生产者有一组进程,消费者有一组进程,但是由于行为相同,故各定义1个进程即可

  • 生产者生产的数据不一定能放入有界缓冲池(如果缓冲池内都装满了数据就无法放入)
  • 为两个进程设置不同的资源
    • 生产者进程 : 空缓冲区资源
    • 消费者进程 : 满缓冲区资源

需要为两个进程设置两个信号量
emptyfull
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.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议