操作系统基础及多线程/进程同步

生产者消费者

描述

生产者消费者问题（英语：Producer-consumer problem），也称有限缓冲问题（英语：Bounded-buffer problem），是一个多线程同步问题的经典案例。该问题描述了两个共享固定大小缓冲区的线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。

解析

需要保证两个方面的同步：

• 缓冲区操作互斥
  生产者和消费者不能同时操作一个缓冲区
• 剩余容量的的同步
  生产者不能在缓冲区满的情况下生产数据，消费者不能在缓冲区为空的情况下消耗数据

伪代码

Semaphore mutex = 1
Semaphore empty_num = size, product_num = 0producer:while(1):P(empty_num)P(mutex)produce()V(mutex)V(product_num)customer:while(1):P(product_num)P(mutex)custome()V(mutex)V(empty_num)

读者写着问题

读者—写者问题（Readers-Writers problem）也是一个经典的并发程序设计问题，是经常出现的一种同步问题。计算机系统中的数据（文件、记录）常被多个进程共享，但其中某些进程可能只要求读数据（称为读者Reader）；另一些进程则要求修改数据（称为写者Writer）。就共享数据而言，Reader和Writer是两组并发进程共享一组数据区，要求：
（1）允许多个读者同时执行读操作；
（2）不允许读者、写者同时操作；
（3）不允许多个写者同时操作。

读者优先VS写者优先

多个读者可以同时读，在读文件的时候不能写，在写文件的时候不能读。

• 读者优先
  读者可以连续不断来，只要有读者，写者就不能写
• 写者优先
  一旦有写者来，之后的读者必须等待

读者优先

需要如下信号量：

• read_count 记录读者个数
• writer 记录写者互斥
• mutex 保证read_count和writer的修改操作是互斥的

Semaphore read_count = 0
Semaphore mutex = 1, writer = 1reader:while(1):P(mutex)read_count++if(read_count == 1)P(writer)V(mutex)read()P(mutex)read_count--if(read_count == 0)V(writer)V(mutex)writer:while(1):P(writer)wirte()V(wirter)

写者优先

需要增加一个互斥锁，负责当有写者的时候阻塞之后的读者。

Semaphore read_count = 0
Semaphore mutex = 1, writer = 1, queue = 1reader:while(1):P(queue)P(mutex)read_count++if(read_count == 1)P(writer)V(mutex)V(queue)read()P(mutex)read_count--if(read_count == 0)V(writer)V(mutex)writer:while(1):P(queue)P(writer)wirte()V(wirter)V(queue)

哲学家就餐问题

问题描述

哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述，因为很明显，吃米饭必须用两根筷子。

解析

对于每一个哲学家，需要拿起左边的筷子，拿起右边的筷子，吃。

Semaphore chopsticks[N]
while(1)P(chopsticks[i])P(chopsticks[i+1]%N)eat()V(chopsticks[i+1]%N)V(chopsticks[i])