进程互斥经典问题（读写者问题、理发店问题）

读写者问题

问题描述

问题分析

进程互斥问题三部曲

读者写者算法实现

一、找进程——确定进程关系

二、找主营业务

三、找同步约束

a.互斥

b.资源

c.配额

理发店问题

问题描述

问题分析

进程互斥问题三部曲

理发店问题算法实现

一、找进程——确定进程关系

二、找主营业务

三、找同步约束

a.资源

b.互斥

c.配额

总结

读写者问题

问题描述

有一个许多进程共享的数据区。有一些只读取这个数据区的进程（Reader）和一些只往数据区写数据的进程(Writer)。现在要写一个程序，保证这些进程的运行是安全的。

问题分析

分析问题可以发现以下这些要点：

1、读者进程彼此可以同时访问共享数据区

2、读者和写者进程不可以同时访问共享数据区

3、写者进程彼此不可以同时访问共享数据区

进程互斥问题三部曲

任何进程互斥（PV问题）都可以按照以下三步思考（来源：山东大学高晓程老师）

一、找进程——确定进程关系

二、找主营业务——抛开互斥，确定每个进程的主要任务

三、找同步约束

互斥
资源（计数信号量、空闲空间信号量等）
限额

读者写者算法实现

接下来，我们按照上面三部曲的思路来实现这个PV经典算法

一、找进程——确定进程关系

进程有两类：1、读者进程；2、写者进程

进程关系如下：

1、读者写者是互斥的

2、写者之间是互斥的

3、读者之间不是互斥的

二、找主营业务

读者进程的主营业务就是：读取reading

写者进程的主营业务就是：写入writing

（此时不考虑任何同步约束~~）

代码如下：

//写者进程
writer(){while(1){writing;}
}//读者进程
reader(){while(1){reading;}
}

三、找同步约束

a.互斥

互斥约束：1、找到临界区；2、互斥变量紧贴临界区

在上面程序的基础上增加互斥约束，如下：

//写者进程
writer(){while(1){wait(rwmutex);writing;signal(rwmutex);}
}//读者进程
reader(){while(1){wait(mutex);if(count==0){wait(rwmutex);}count++;signal(mutex);reading;wait(mutex);count--;if(count==0)signal(rwmutex);signal(mutex);}
}

关键点：

1、读者可以一起读取文件，但是读者和写者不能一起访问资源区。这表明如果没有读者访问，此时有一个读者想要访问资源区，他需要和写者竞争这个资源。一旦这个读者开始读取后，其他读者可以直接读取，不需要互斥访问。———需要一个读者和写者之间的互斥量rwmutex。

2、由于只有第一个读者需要去竞争rwmutex，所以需要一个格外的变量count去记录目前有几个读者。

3、又由于count变量对于多个读者进程来说又是共享的变量（临界区），所以需要另外一个互斥量mutex去约束读者进程对count变量的访问

b.资源

资源视角主要包括有界缓存问题的计数信号量、先后执行问题的同步信号量等。本题显然没有这两个信号量的约束，所以这边资源视角没有新的代码修改。

但是资源视角是一个万能视角，我们可以从资源视角来看上面的互斥：

1、rwmutex是访问资源，第一个读者进程需要和众多写者进程去竞争。只有竞争成功才可以进一步操作

2、对count的访问也是一种读者进程间的访问资源，只有每个读者进程竞争到了这个资源，才可以访问count变量，对变量进行修改

c.配额

配额仅仅在特殊的进程互斥问题上才需要考虑，本题中并没有对配额进行限制。后续有遇到配额约束，我们再展开说说。

理发店问题

问题描述

理发店里有一位理发师、一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉；当一个顾客到来时，它必须叫醒理发师；如果理发师正在理发时又有顾客来到，那么，如果有空椅子可坐，顾客就坐下来等待，否则就离开理发店。

问题分析

1、只有n把顾客坐的等待椅子，一旦椅子满了，新顾客就离开

2、理发椅子只有一个

3、没有客人理发师就睡觉，客人来了理发师才理发

进程互斥问题三部曲

任何进程互斥（PV问题）都可以按照以下三步思考（来源：山东大学高晓程老师）

一、找进程——确定进程关系

二、找主营业务——抛开互斥，确定每个进程的主要任务

三、找同步约束

互斥
资源（计数信号量、空闲空间信号量等）
限额

理发店问题算法实现

一、找进程——确定进程关系

两个进程：1、理发师进程；2、顾客进程

1、理发师和顾客进程存在先后关系，顾客来了理发师才理发

2、顾客进程之间存在互斥关系，理发椅只有一张

3、顾客进程存在上限，一旦超过上限便不再添加

二、找主营业务

理发师：叫号+理发

顾客：取号+被理发

//理发师进程
Server(){while(1){叫号;理发;
}//顾客进程
Customer(){while(1){取号;被理发;
}

三、找同步约束

a.资源

顾客来了，给理发师释放一个资源；理发师理完发，给顾客们释放一种资源。所以这里需要两个资源customer、server：

//默认先对信号量操作，再进行实际操作
//理发师进程
Server(){while(1){wait(customer);叫号;  //减少一个顾客数，访问临界区signal(server);理发;
}//顾客进程
Customer(){while(1){取号;  //增加一个顾客数(可能失败，所以signal在后面），访问临界区signal(customer);wait(server)被理发;
}

只有n把顾客坐的等待椅子，一旦椅子满了，新顾客就离开。所以这里需要共享变量waiting，来记录等待的顾客数目：

//默认先对信号量操作，再进行实际操作
//理发师进程
Server(){while(1){wait(customer);叫号;  //减少一个顾客数，访问临界区waiting--;  //减少一个等待顾客数，访问临界区signal(server);理发;
}//顾客进程
Customer(){while(1){if(waiting<n){取号;  //增加一个顾客数(可能失败，所以signal在后面），访问临界区signal(customer);wait(server)被理发;}else{离店;}
}

b.互斥

对所有临界区的变量加上互斥锁

//默认先对信号量操作，再进行实际操作
//理发师进程
Server(){while(1){wait(customer);wait(mutex);叫号;  //减少一个顾客数，访问临界区waiting--;  //减少一个等待顾客数，访问临界区signal(mutex);signal(server);理发;}
}//顾客进程
Customer(){while(1){wait(mutex);  //这个wait同样也是保护if语句，所以在后面else结束if语句时也需要signalif(waiting<n){取号;  //增加一个顾客数(可能失败，所以signal在后面），访问临界区waiting++;signal(mutex);signal(customer);wait(server)被理发;}else{signal(mutex);离店;}}
}