经典进程同步问题

生产者消费者

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，也就无法执行 up(empty) 操作，empty 永远都为 0，那么生产者和消费者就会一直等待下去，造成死锁。

一个semaphore锁定资源，两个semaphore用于计数empty和full, 之所以单独semaphore，是可以进行阻塞而不需要不停重试。

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE){
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE){
        down(&full);
        down(&mutex);
        int item = remove_item();
        up(&mutex);
        up(&empty);
        consume_item(item);
    }
}

读写者

读者优先

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。

这个是读者优先，也就是写者会挨饿。关键在于只要有读者就不能写了

参考

读者优先:

写者、读者互斥访问文件资源。
多个读者可以同时访问文件资源。
只允许一个写者访问文件资源。

具体实现:

设置信号量fileSrc实现读写者对临界资源的访问。
设置计数器readCount来统计访问临界资源的读者数目，设置信号量count_mutex完成对readCount计数器资源的互斥访问。

int count = 0; //读者数量
semaphore count_mutex = 1; //保护读者数量count
semaphore data_mutex = 1; //每次写和第一次读用


void reader() {
    while(TRUE) {
        down(&count_mutex); //申请读者队列计数器
        count++;
        if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
        up(&count_mutex); //释放读者计数器资源
        read();
        down(&count_mutex); //申请读者队列计数器
        count--;
        if(count == 0) up(&data_mutex);
        up(&count_mutex); //释放读者计数器资源
    }
}

void writer() {
    while(TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}

写者优先

写者优先:

写者线程的优先级高于读者线程。
当有写者到来时应该阻塞读者线程的队列。
当有一个写者正在写时或在阻塞队列时应当阻塞读者进程的读操作，直到所有写者进程完成写操作时放开读者进程。
当没有写者进程时读者进程应该能够同时读取文件。

具体实现:

通过添加信号量read实现写者到来时能够打断读者进程。（主要是有个信号量控制只要有写的等待时就阻塞新增读, 这就是信号量read存在的意义）
设置信号量fileSrc实现读写者对临界资源的访问。
设置计数器writeCount来统计当前阻塞的写者进程的数目，设置信号量writeCountSignal完成对writeCount计数器资源的互斥访问。（实现写队列，拆成两端)
设置计数器readCount来统计访问临界资源的读者数目，设置信号量readCountSignal完成对readCount计数器资源的互斥访问。

参考

但如何搞个写队列，完全阻塞其他读请求，因此要有个写队列，把获取read和fileSrc分成两段，前段申请read，增加writeCount以及阻塞在申请fileSrc, 申请到fileSrc后就到了后半段，因此需要writeCount

比读者多了个read信号量以及writeCount和writeCountSignal.

相比读者优先，增加writeCount和writeCountSignal在写过程里保证写优先，第一次写时申请read信号量，后面写会继续保持read信号量，read不同于fileSrc。fileSrc是保护临界区。

读时先等read信号量再走之前一样流程。

/*初始化读者、写者队列为0，初始化令牌资源、读写计数器资源的初始值为1*/
int readCount = 0;
int writeCount = 0;
semaphore readCountSignal = 1; //保护readCount
semaphore writeCountSignal = 1; //保护writeCount
semaphore read = 1; //读写都竞争，每次增加读者数需要它，第一次写需要它
semaphore fileSrc = 1; //保护文件，每次写和第一次读用
 
reader()
{
      while(true)
     {
        wait(read);            //申请令牌
        wait(readCountSignal); //申请读者队列计数器
 
        if(!readCount)         //如果读者队列为空，申请文件资源
           wait(fileSrc); 
        readCount++;
 
        signal(readCountSignal); //释放读者计数器资源
        signal(read);            //释放令牌
  
        ...
        perform read operation //执行临界区代码     
        ...
 
        wait(readCountSignal);   //申请读者计数器资源
        readCount--;
        if(!readCount)          //如果读者队列为空，释放文件资源
          signal(fileSrc);
        signal(readCountSignal); //释放读者计数器资源
      }
}
 
writer()
{
     while(true)
     {
       wait(writeCountSignal);  //申请写者计数器资源
       if(!writeCount)          //如果写者队列为空则申请令牌
         wait(read);
       writeCount++;
       signal(writeCountSignal); //释放写者计数器资源
       wait(fileSrc);               //申请文件资源
 
       ...
       perform write operation   //执行临界区代码
       ...
 
       signal(fileSrc);          //释放文件资源
       wait(writeCountSignal);   //申请写者计数器资源
       writeCount--;
       if(!writeCount)           //如果写者队列为空则释放令牌
          signal(read);
       signal(writeCountSignal); //释放写者计数器资源
      }
}

公平竞争

公平竞争：

优先级相同。
写者、读者互斥访问。
只能有一个写者访问临界区。
可以有多个读者同时访问临界资源。

具体实现：

设置file信号量实现对临界资源的互斥访问。
设置计数器readCount实现多个读者访问临界资源，通过设置信号量readCountSignal实现对readCount计数器的互斥访问。
设置信号量keySignal实现读者和写者的公平竞争（令牌）。
设置信号量OneSignal实现只有读者队列或写者阻塞在keySignal（对令牌资源的访问控制）。

参考

主要是每个读和这个写都有一样的机会，有个共同的信号量，同时只有一个写，得有个信号量对写控制只有一个才行。

相比读者优先，就是写和读外面有个竞争keySignal,然后写最外面再来个竞争OneSignal. 这样竞争就是一个写和多个读一起竞争。

/* 读者队列初始值为0，其他资源初始值为1*/
int readCount = 0;
semaphore readCountSignal = 1; //保护readCount
semaphore keySignal = 1; //每次增加读者数，每次写都用，保证公平
semaphore OneSignal = 1; //只有写用，用来保证只有一个写，最外层
semaphore fileSrc = 1; //保护文件，每次写和第一次读用
 
reader()
{
    while(true)
    {
      wait(keySignal);        //申请令牌
      wait(readCountSignal);  //申请计数器资源
      if(!readCount)          //为零则申请文件资源
         wait(fileSrc);
      readCount++;
      signal(readCountSignal); //释放计数器资源
      signal(keySignale);      //释放令牌
 
      ...
      perform read operation  //执行临界区代码
      ...
  
      wait(readCountSignal);  //申请计数器资源
      readCount--;
      if(!readCount)                //为零则释放文件资源
         signal(fileSrc);
    signal(readCountSignal); //释放读者计数器资源
    }
}
 
writer()
{
     while(true)
     {
        wait(OneSignal);     //申请令牌资源
        wait(keySignal);     //申请令牌
        wait(fileSrc);       //申请文件资源
 
        ...
        perform write operation //执行临界区代码
        ...
 
        signal(fileSrc);   //释放文件资源
        signal(keysignal); //释放令牌
        signal(OneSignal); //释放令牌资源
     }
}

哲学家进餐

参考

五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在桌子上有五只碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。

能引起死锁的情况。假如五位哲学家同时饥饿而都拿起的左边的筷子，就会使五个信号量chopstick都为0，当他们试图去拿右手边的筷子时，都将无筷子而陷入无限期的等待。

为避免死锁，可以使用以下三种策略：

策略一：至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。定义信号量count，只允许4个哲学家同时进餐，这样就能保证至少有一个哲学家可以就餐。

策略二：仅当哲学家的左右两支筷子都可用时，才允许他拿起筷子进餐。可以利用AND 型信号量机制实现，也可以利用信号量的保护机制实现。利用信号量的保护机制实现的思想是通过记录型信号量mutex对取左侧和右侧筷子的操作进行保护，使之成为一个原子操作，这样可以防止死锁的出现。

策略三：规定奇数号的哲学家先拿起他左边的筷子，然后再去拿他右边的筷子；而偶数号的哲学家则先拿起他右边的筷子，然后再去拿他左边的筷子。按此规定，将是1、2号哲学家竞争1号筷子，3、4号哲学家竞争3号筷子。即五个哲学家都竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一个哲学家能获得两支筷子而进餐。

Fulongのblog

经典进程同步问题

生产者消费者

读写者

读者优先

写者优先

公平竞争

哲学家进餐

P1P2P3缓冲区问题

理发师问题

Search

Table of Contents

Popular Posts

2022-12 typescript笔记

2022-08 scala语法

2021-12 etcd和raft

2021-09 状态压缩

2021-01 博弈论

2021-01 分布式算法和协议

2020-12 kafka原理1-基础架构

2020-12 ElasticSearch(ES)原理

2020-11 动态规划总结

2020-11 线段树

2017-12 javascript笔记