操作系统5————进程同步的经典问题：司机售票员&问题生产者消费者问题&哲学家进餐问题&读者写者问题

曾经终败给现在 2022-05-24 07:42 286阅读 0赞

# 操作系统5————进程同步的经典问题：司机售票员&问题生产者消费者问题&哲学家进餐问题&读者写者问题 #

### 一. 目录 ###

### 文章目录 ###

*  操作系统5————进程同步的经典问题：司机售票员&问题生产者消费者问题&哲学家进餐问题&读者写者问题
 *   *   *  一. 目录
         *  二. 信号量的简单应用
         *   *  1. 使用信号量实现互斥
             *  2. 使用信号量实现前驱关系
         *  三. 司机售票员问题
         *   *  1. 问题描述
             *  2. 思路
             *  3. 使用记录型信号量解决问题
         *  四. 生产者消费者(缓存绑定问题)问题
         *   *  1. 问题描述
             *  2. 思路
             *  3. 使用信号量解决问题
         *  五. 哲学家进餐问题
         *   *  1. 问题描述
             *  2. 思路
             *  3. 使用记录型信号量解决问题
             *  4.分析
         *  六. 读者写者问题
         *   *  1. 问题描述
             *  2. 思路
             *  3. 使用记录型信号量解决问题
         *  七.参考资料

### 二. 信号量的简单应用 ###

#### 1. 使用信号量实现互斥 ####

**思路**：设mutex为互斥信号量，其初值为1，取值范围为(-1,0,1)。当mutex=1时，表示两个进程皆未进入需要互斥的临界区，当mutex=0时，表示有一个进程进入临界区。另一个必须等待，挂入阻塞队列。当muntex=-1时，表示有一个进程因等待而阻塞在信号量队列，需要被当前已在临界区运行的进程推出是唤醒

**代码描述**

semaphore mutex = 1;
    
    pA(){
        while(1){
            wait(mutex);
            临界区
            signal(mutex);
            剩余区
        }
    }
    
    
    PB(){
        while(1){
            wait(mutext);
            临界区;
            signal(mutex);
            剩余区
        }
    }

#### 2. 使用信号量实现前驱关系 ####

**问题**: 现在有进程P1和P2，P1有语句S1，P2有语句S2，我们希望执行完S1后在执行S2。  
**思路**: 我们只需要在进程P1和P2之间共享一个公用信号量S，并且赋其初值为0，将signal(S)操作放在语句S1后，而把S2语句前面插入Wait(S)操作。  
**伪代码**：

在进程P1中： S1； signal(S);
    在进程P2中：wait(S);s2;

### 三. 司机售票员问题 ###

#### 1. 问题描述 ####

公共汽车上。司机和售票员的活动分别如下：  
司机的活动：启动车辆，正常行车，到站停车.  
售票员的活动： 关车门，售票，开车门。

#### 2. 思路 ####

分析可知。售票员和司机的4个活动存在前后关系。即关车门–>启动汽车。到站停车–>开车门。所以用两个信号量s1,s2分别来控制两组前后关系.

#### 3. 使用记录型信号量解决问题 ####

**伪代码**

semaphore s1 = 1,s2 = 1;
    //司机
    void driver(){
    	signal（s1）
    	启动车辆
    	正常行驶
    	到站停车
    	wait(s2)
    }
    
    void conductor(){
    	关车门
    	wait(s1)
    	售票
    	signal（s2）
    	开门
    }

### 四. 生产者消费者(缓存绑定问题)问题 ###

#### 1. 问题描述 ####

有两个进程：一组生产者进程和一组消费者进程共享一个初始为空、固定大小为n的缓存（缓冲区）。生产者的工作是制造一段数据，只有缓冲区没满时，生产者才能把消息放入到缓冲区，否则必须等待，如此反复; 同时，只有缓冲区不空时，消费者才能从中取出消息，一次消费一段数据（即将其从缓存中移出），否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或者一个消费者从中取出消息。

#### 2. 思路 ####

**问题的核心是：**

1.  要保证不让生产者在缓存还是满的时候仍然要向内写数据;
2.  不让消费者试图从空的缓存中取出数据。

生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，他们也是同步关系。

#### 3. 使用信号量解决问题 ####

**说明:**

假定在生产者和消费者之间的公用缓存池具有n个缓冲区，这时候可利用互斥信号量mutex来实现诸进程对缓存池的互斥利用；利用信号量的empty和full分别表示缓存池中空缓存区和满缓存区的数量。

**伪代码描述：**

int in=0,out=0;
    item buffer[n];
    semaphore mutex =1,empty = n,full = 0;
    
    //生产者
    void producer(){
        do{
            producer an item nextp;
            ···
            wait(empty);  //询问是否有空缓存区
            wait(mutex); //互斥访问
            buffer[in] = nextp;
            in = (in+1)%n;
            signal(mutex);//解除互斥访问
            signal(full); //释放一个满缓存区，满缓存+1
        }while(TRUE)
    }
    
    //消费者
    void consumer(){
        do{
            wait(full);
            wait(mutex);
            nextc = buffer[out];
            out = (out+1) %n;
            signal(mutex);
            signal(empty);
        }while(TRUE)
    }

当然也可以使用AND信号量解决问题：即用Swait(empty,mutex)来代替wait(empty);wait(mutex); 用Ssignal(mutex,full)来代替signal(mutex)和signal(full);

### 五. 哲学家进餐问题 ###

#### 1. 问题描述 ####

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

#### 2. 思路 ####

分析可知，筷子是临界资源，在一段时间内只允许一位哲学家使用，为了实现对筷子的互斥使用，为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。

#### 3. 使用记录型信号量解决问题 ####

**伪代码**

semaphore chopstick[5] = {1,1,1,1,1};
    
    //第i位哲学家的活动可描述为：
    do{
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]);
        ···
        //eat
        ···
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5];
        ···
        //think
        ···
    }while(TRUE)

#### 4.分析 ####

上面的解法虽然保证了相邻的哲学家不会同时进餐，但可能会导致死锁问题，比如说，当5个哲学家同时饥饿而去拿左边的筷子是，就会发生死锁。

**避免死锁的方法：**

1.  至多只允许有4位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐。
2.  仅当哲学家左右两只筷子同时可用时，才允许他拿起筷子进餐。、
3.  规定奇数号哲学家先拿他左边的筷子，然后再去拿他右边的筷子，而偶数号哲学家则相反

### 六. 读者写者问题 ###

#### 1. 问题描述 ####

一个数据文件可以被多个文件共享，我们把只要求读文件的进程称为 “Reader进程”，其他进程则称为“Writer进程”。允许多个进程读一个文件，但不允许一个Writer进程和其他Reader进程或者Writer进程同时访问共享。

#### 2. 思路 ####

由题意可知，读者之间不互斥，写者之间互斥，写者和读者之间互斥。所以为写者之间，写者和读者之间设置互斥信号量wmutex。在设置一个整形变量readcount表示读进程的进程数目。当readcount=0时，才允许写者运行·。对于读者而言readcount是一个可被多个读者访问的临界资源。因此，也应该为它设置一个互斥信号量rmutex。

#### 3. 使用记录型信号量解决问题 ####

**伪代码**

semaphore rmutex = 1,wmutex = 1;
    int readcount = 0;
    void reader(){
    	do{
    		wait(rmutex);
    		if(readcount==0) wait(wmutex);
    		readcount++;
    		signal(rmutex);
    		···
    		perform read operation;
    		···
    		wait（rmutex）；
    		if(readcount==0) signal(wmutex);
    		readcount--;
    		signal(rmutex);
    	}while(TRUE);
    }
    
    void writer(){
    	do{
    		wait(wmutex);
    		perfrom write operation;
    		signal(wmutex); 
    	}while(TRUE);
    }

### 七.参考资料 ###

《操作系统第四版》  
[5个经典的同步问题][5]

[5]: https://blog.csdn.net/naruto_ahu/article/details/8672376