课堂笔记与思考归纳

①生产者-消费者问题

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.