操作系统知识点大总结【4大经典同步问题：生产者消费者问题、读者写者问题、哲学家进餐问题、睡眠的理发师问题】

傷城~ 2023-01-17 09:30 114阅读 0赞

### 文章目录 ###

*   *  一、生产者消费者问题
     *  二、写者读者问题
     *  三、哲学家进餐问题
     *  四、睡眠的理发师问题

## 一、生产者消费者问题 ##

小tip：统一把P理解为消耗，V理解为释放。  
**1、问题描述**  
生产者-消费者模型描述的是有一群生产者进程在生产产品，并将这些产品提供给消费者进程并发进行，具备并发程序的典型特征。PCM为使生产者进程和消费者进程并发进行，在它们之间设置一个具有多个缓冲区的缓冲池生产者进程可以将其所生产的产品放入一个缓冲区中，消费者进程可以从一个缓冲区中取得产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但他们之间必须保持同步，既不允许消费者进程从空的缓冲区中拿产品，也不允许生产者进程向满缓冲区中放产品。

**2、问题分析**  
设同步信号量empty，初值为n，表示生产者有n个空缓冲区可用。  
同步信号量full，初值为0，表示生产者尚未把产品放入缓冲池。  
互斥信号量mutex，初值为1，以保证同时只有一个进程能够进入临界区，访问访冲池。

**3、算法图解**  
![01][]

**4、方案**

a 这里生产者和消费者是互斥访问
    但存在相互协作关系，是同步关系
    
    semaphore mutex = 1;   // 设置临界区初始互斥量值 = 1
    semaphore empty = n;   // 设置空的单位数 = n
    semaphore full = 0;   // 设置满的单元数 = 0
    
    //生产者：
    producer()		//这里把P(empty), P(full) 理解为消耗会更好Instead of waiting
    {
    	while(1)
    	{
    		produce an item in nextp;    // 先生产一个物品
    		P(empty);   // 消耗一个空闲区
    		P(mutex);(互斥夹紧)   // 进入临界区
    		add nextp to buffer;  // 操作动作
    		V(mutex);(互斥夹紧)   // 离开临界区，释放互斥信号量
    		V(full);   // 生成一个满块
    	}
    }
    
    //消费者：
    consumer()
    {
    	while(1)
    	{
    		P(full);  //消耗一个满载区
    		P(mutex);(互斥夹紧)
    		remove an item from buffer;
    		V(mutex);(互斥夹紧)
    		V(empty);  //生成一个空块区
    		consume the item;
    	}
    }

![01][01 1]

**5、注意**

## 二、写者读者问题 ##

**1、问题描述**  
一组读者(指对共享数据对象只要求读的进程)与一组写者(指对共享数据对象只要求写的进程)循环访问共享的同一个数据对象，规定多个读者可以同时读这个数据对象，但绝不允许多个写者对这个数据对象进行写操作。也不允许读者、写者同时访问这个数据对象。

需要进行的限制：写-写互斥、读-写互斥、读-读允许

**2、问题分析**  
设互斥信号量wmutex，初值为1，用于实现写者与其它写者或读者互斥地访问共享数据对象。  
互斥信号量rmutex，初值为1，用于实现读者互斥地访问读者计数器变量。设整型变量RC，初值为0，用于对读者进行计数。

**3、算法图解**  
![02][]  
**4、方案**

int count = 0; 			// 记录当前读者数量
    
    semaphore mutex = 1;	//用于保护 更新count变量时 的互斥
    semaphore rw = 1;		//用于保护 读者 和写者互斥地访问文件
    semaphore w = 1;		//用于实现“写优先”
    
    writer()
    {
    	while(1)
    	{
    		P(w);		// 消耗写优先资源
    		P(rw);		// 消耗读写互斥资源
    		writing;
    		V(rw);		// 释放读写互斥资源
    		V(w);		//释放写优先资源
    	}
    }
    
    reader()
    {
    	while(1)
    	{
    		P(w);		   // 消耗写优先资源
    		P(mutex);		//消耗 count变量资源
    		
    		if(count == 0)  // 如果是第一个读操作，封杀写操作
    			P(rw);    	// 封杀写操作
    			
    		count++;		// 表明读者个数
    		V(mutex);		//释放 count变量资源
    		V(w);			 // 消耗写优先资源
    		reading;
    		P(mutex);		//消耗 count变量资源	
    		count--;
    		
    		if(count == 0)
    			V(rw);		// 释放读写互斥资源
    
    		V(mutex);		//释放写优先资源
    	}
    }

## 三、哲学家进餐问题 ##

**1、问题描述**  
有五位哲学家，它们的生活方式是交替的进行思考和进餐。哲学家门共用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有五只碗和五根筷子，平时哲学家进行思考，饥饿的时候视图取其左右的靠他最近的筷子，只有当拿到两根筷子时才能进餐。

**2、算法分析**  
最多只能四个哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用完时释放出他用过的两根筷子。

只有当哲学家的左、右两根筷子均可用时，才允许他拿起筷子进餐。

并且规定奇数号哲学家先拿起他左边的筷子，然后再去拿他右边的筷子；而偶数号则相反。按此规定，总会有一位哲学家能进餐，并在使用完后释放筷子。

**3、方案（利用AND信号量解决哲学家进餐问题）**

int chopstick[5] = { 1,1,1,1,1 };
    	do {
    		think;
    		wait(chopstick[(i + 1)mod 5], chopstick[i]);
    		eat;
    		signal(chopstick[(i + 1)mod 5], chopstick[i]);
    	} while (true);

## 四、睡眠的理发师问题 ##

**1、问题描述**  
在理发店里只有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。

要达到的要求是：  
如果没有顾客，理发师便在理发椅上睡觉；  
一个顾客到来时，它必须叫醒理发师；  
如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。

**2、问题分析**  
理发师和顾客是同步关系，理发师等待顾客来，然后为顾客服务，顾客来了之后叫醒理发师，执行上是有先后顺序的，所以应该有两个同步信号量，且散在两个进程里；另一方面，顾客对椅子的操作又是互斥的，属于竞争关系，所以需要互斥信号量来保证椅子的数量准确。

**3、算法描述**  
设一个计数变量waiting，表示等待理发的顾客人数，初始值为0；  
设3个信号量，，customers用来记录等候理发的顾客数，不包括正在理发的顾客；  
barners用来记录正在等待顾客的理发师数（其值为0或1）；  
mutex用于互斥。

**4、方案**

int waiting = 0; // 等候理发师 顾客坐的椅子数
    int CHAIRS = N;  // 为顾客准备的椅子数
    semaphore customers = 0; // 等候的顾客数
    semaphore barbers = 0;   // 空闲的理发师数
    semaphore mutex = 1;     // 互斥信号量，保证waiting++操作完整进行
    
    cobegin
    process barber() {  // 理发师
        while(true) {
            P(customers); // 有顾客吗？若无顾客，理发师睡眠
            P(mutex);     // 保证waiting--完整进行
            // 若有顾客时，进入临界区
            waiting--;    // 等候区顾客数减一
            V(barbers);   // 理发师准备为顾客理发
            V(mutex);
            cut_hair();   // 理发师正在理发（非临界区）
        }
    }
    
    process customer_i() {  // 顾客
        P(mutex);     // 进入临界区
        if(waiting < CHAIRS) {  // 有空椅子
        	waiting++;    // 等候顾客加一
            V(customers); // 唤醒理发师
        	V(mutex);     // 退出临界区
       	 	P(barbers);   // 理发师忙，顾客坐下等待
       	 	get_haircut();// 否则顾客坐下理发
        } else
        	V(mutex);     // 没椅子，顾客走人
    }

以上就是关于进程同步中运用PV操作和信号量来解决四大经典同步问题的分析与解决方案。

[01]: /images/20221021/028db16e67b6421393cba399bbb972e3.png
[01 1]: /images/20221021/876c0e9f9d4b460bad5f6585bd6ac1c6.png
[02]: /images/20221021/e42d845c5a0d4d70935bc95e65933cb9.png