文章目录

1 生产者-消费者问题问题 1问题 2 2 读者-写者问题读者优先读写公平写者优先 3 哲学家进餐问题初始方案改进方案 4 吸烟者问题5 理发师问题

1 生产者-消费者问题

问题 1

一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区，只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区时临界资源，只允许一个生产者放入消息，或一个消费者从中取出消息

分析：

生产者和消费者对缓冲区的访问是互斥关系；同时它们之间又存在着同步关系，只有生产者生产之后消费者才能消费，而只有缓冲区未满（消费者一直消费）生产者才能生产产品。

semaphore mutex = 1; //用于实现对缓冲区的互斥访问 semaphore empty = n; //空闲缓冲区数量 semaphore full = 0; //非空闲缓冲区（产品）数量 // 生产者进程 producer(){ while(1){ 生产一个消息; p(empty); p(mutex); 将一个消息放入缓冲区; v(mutex); v(full); } } // 消费者进程 producer(){ while(1){ p(full); p(mutex); 从缓冲区取一个消息; v(mutex); v(empty); 消费消息; } }

问题 2

桌上有一个盘子，每次只能向其中放入一个水果。爸爸只放苹果，妈妈只放橘子，女儿只拿苹果，儿子只拿橘子。只有盘子为空时，爸爸或妈妈才能向盘子中放水果，只有盘子不空时，儿子或女儿才能从盘子中拿水果

分析：

爸爸、妈妈都向盘子放水果，儿子、女儿都从盘子取水果，儿子取妈妈放的水果，女儿取爸爸放的水果。因此爸爸妈妈、儿子女儿各自之间为互斥关系；爸爸女儿、妈妈儿子各自之间为同步关系

semaphore plate = 1, apple = 0, orange = 0; dad(){ while(1){ 准备一个苹果; p(plate); 放入一个苹果; v(apple); } } mom(){ while(1){ 准备一个橘子; p(plate); 放入一个橘子; v(orange); } } son(){ while(1){ p(orange); 拿走一个橘子; v(plate); 吃橘子; } } daughter(){ while(1){ p(apple); 拿走一个苹果; v(plate); 吃苹果; } }

2 读者-写者问题

读者优先

有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（写进程或读进程）同时访问共享数据时则可能导致数据不一致的情况发生。因此要求：

①允许多个读者可以同时对文件执行读操作②只允许一个写者向文件写消息③任一写者完成写操作之前不允许其他读者或写者工作④写者执行写操作前，应让已有的读者和写者全部退出

分析：

允许一个或多个读者同时访问、只允许一个写者访问。因此读写互斥、写写互斥。总之，只要有写者，则必须互斥。

设置互斥信号量 mutex，用于对数据区互斥访问，再设计数器 read_count，用于记录读者数量，当第一个读者到来时，对 mutex 进行p操作，只有最后一个读者离开时，才对 mutex 进行v操作，这样只要有读者，无论来多少个写者都会被阻塞，直到所有读者离开，释放 mutex 。如此便能实现读者优先

int read_count = 0; //用于记录读者数量 semaphore rmutex = 1;//用于对read_count互斥访问 semaphore mutex = 1; //用于对数据区互斥访问 //写进程 writer(){ while(1){ p(mutex); 写; v(mutex); } } //读进程 reader(){ while(1){ p(rmutex); if(read_count == 0) p(mutex); read_count++; v(rmutex); 读; p(rmutex); read_count--; if(read_count == 0) v(mutex); v(rmutex); } }

读写公平

思考读者优先的方案：假设已有读进程正在对文件进行读取，后续又源源不断的有读进程到来，也有写进程到来。只要一直有读进程，则信号量 mutex 就一直得不到释放，则写进程就会一直被阻塞，尽管有的写进程比读进程到来的早。这就会造成写进程长时间被阻塞，甚至”饿死“。

解决方案：若希望读进程、写进程公平访问文件，则需再设一个信号量 wmutex。当有读进程或写进程到来时，需要先对 wmutex 进行 p 操作，若写进程先到，则先p(wmutex)，后续的读进程就会被阻塞；若读进程先到，则先p(wmutex)，后续的写进程就会被阻塞。如此便能保证访问的公平性了。

int read_count = 0; //用于记录读者数量 semaphore rmutex = 1;//用于对read_count互斥访问 semaphore mutex = 1; //用于对数据区互斥访问 semaphore wmutex = 1;//若已有写者到来，则阻塞后来的读者 //写进程 writer(){ while(1){ p(wmutex); p(mutex); 写; v(mutex); v(wmutex); } } //读进程 reader(){ while(1){ p(wmutex); p(rmutex); if(read_count == 0) p(mutex); read_count++; v(rmutex); v(wmutex); 读; p(rmutex); read_count--; if(read_count == 0) v(mutex); v(rmutex); } }

写者优先

仿照读者优先的例子，添加一个互斥信号量readable，让写者对此信号量进行p操作，则只要有写者存在，此信号量由于没被写者释放，则读者一直被阻塞，从而实现写者优先

semaphore mutex = 1; //用于互斥访问数据区 semaphore rmutex = 1; //用于读者互斥访问read_count semaphore wmutex = 1; //用于写者互斥访问write_count semaphore readable = 1;//用于表示当前是否有写者 int read_count = 0, write_count = 0; //用于记录读者和写者数量 reader(){ while(1){ p(readable); p(rmutex); if(read_count == 0) p(mutex); read_count++; v(rmutex); v(readable); 读; p(rmutex); read_count--; if(read_count == 0) v(mutex); v(rmutex); } } writer(){ while(1){ p(wmutex); if(write_count == 0) p(readable); v(wmutex); p(mutex); 写; v(mutex); p(wmutex); write_count--; if(write_count == 0) v(readable); v(wmutex); } }

3 哲学家进餐问题

一张圆桌边上坐着五名哲学家，没两名哲学家之间的桌上摆着一根筷子，两根筷子之间时一碗米饭，哲学家不是吃饭就是思考。只有哲学家饥饿时，才试图拿起左右两根筷子（一根一根的拿起）。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿起两根筷子才能进餐，进餐完毕后，放下筷子继续思考。

初始方案

定义信号量数组chopstick[5] = {1,1,1,1,1} ，用于对 5 根筷子进行互斥访问。哲学家按顺序编号为0~4，哲学家 i 左边筷子编号为 i ，右边筷子编号为 (i+1)%5 。

semaphore chopstick[5] = {1,1,1,1,1}; philosopher(){ while(1){ p(chopstick[i]); p(chopstick[(i+1)%5]); 吃饭; v(chopstick[i]); v(chopstick[(i+1)%5]); 思考; } }

改进方案

初始方案中，可能存在一种情况：若每名哲学家都拿起一根筷子时，由于没有人有两根筷子，于是谁也不能进餐，每个人都在等待，因此出现了死锁。

为防止死锁，可对初始方案用以下三个方法解决

方法一：至多允许 4 名哲学家同时进餐方法二：仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子。这样必有一名哲学家可以拿起 2 根筷子方法三：对哲学家顺序编号，要求齐数号哲学家先拿起左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反

方法一：至多允许 4 名哲学家同时进餐

至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。设置一个初值为 4 的信号量 num，只允许 4 个哲学家同时去拿左筷子，这样就能保证至少有一个哲学家可以就餐，不会出现饿死和死锁的现象

semaphore chopstick[5] = {1,1,1,1,1}; semaphore num = 4; philosopher(int i){ while(1){ p(num); //请求进餐 p(chopstick[i]); //拿左筷子 p(chopstick[(i+1)%5]); //拿右筷子 吃饭; v(chopstick[i]); v(chopstick[(i+1)%5]); v(num); 思考; } }

方法二：仅当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子

将拿左右筷子的操作看成一个连贯的操作，在其周围加上pv操作，从而保证拿起筷子的过程不被打断，保证同时持有左右两根筷子

semaphore chopstick[5] = {1,1,1,1,1}; semaphore mutex = 1; philosopher(){ while(1){ p(mutex); p(chopstick[i]); p(chopstick[(i+1)%5]); v(mutex); 吃饭; v(chopstick[i]); v(chopstick[(i+1)%5]); 思考; } }

方法三：对哲学家顺序编号，要求齐数号哲学家先拿起左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反

semaphore chopstick[5] = {1,1,1,1,1}; philosopher(int i){ while(1){ if(i % 2 != 0) { //若为奇数号哲学家 p(chopstick[i]); //先拿左筷子 p(chopstick[(i+1)%5]); //后拿右筷子 吃饭; v(chopstick[i]); v(chopstick[(i+1)%5]); 思考; } else { //若为偶数号哲学家 p(chopstick[(i+1)%5]); //先拿右筷子 p(chopstick[i]); //后拿左筷子 吃饭; v(chopstick[(i+1)%5]); v(chopstick[i]); 思考; } } }

4 吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停的卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者需要三种材料：烟草、纸、胶水。三个抽烟者分别拥有烟草、纸、胶水。供应者无限提供三种材料，他每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷起一根烟并抽掉，并给供应者一个信号告诉已完成，此时供应者会将两外两种材料放到桌子上，如此循环……。

要求让三个抽烟者轮流抽烟。

int random; semaphore offer1 = 0; //对应纸和胶水的资源 semaphore offer2 = 0; //对应烟草和胶水的资源 semaphore offer3 = 0; //对应烟草和纸的资源 semaphore finish = 0; //供应者进程 process(){ random = 随意一个整数; while(1){ flag = random % 3; if(flag == 0) v(offer1); else if(flag == 1) v(offer2); else v(offer3); random++; p(finish); } } //抽烟者进程 smoker_1(){ while(1){ p(offer1); 拿起纸和胶水，卷烟，抽掉; v(finish); } } smoker_2(){ while(1){ p(offer2); 拿起胶水和烟草，卷烟，抽掉; v(finish); } } smoker_3(){ while(1){ p(offer3); 拿起烟草和纸，卷烟，抽掉; v(finish); } }

5 理发师问题

理发店有一位理发师、一把理发椅、n 个供顾客等候用的凳子。若没有顾客，则理发师在理发椅上睡觉。当一位顾客到来时，顾客必须叫醒理发师；若理发师正在理发时又有顾客到来，若有空椅子可坐，则顾客坐下来等待，否则离开。

分析：

一把理发椅、n 个供顾客等候用的凳子，则理发店最多可容纳 n+1 人。根据对理发椅处理方法的不同，则有两种解决方法

方法一：将理发椅和凳子看成两种不同的资源方法二：将理发椅和凳子看成一种资源

方法一：将理发椅和凳子看成两种不同的资源

int customer_count = 0; //记录当前顾客人数 semaphore mutex = 1; //用于互斥访问wait_count semaphore baber_chair = 1; //理发椅 semaphore wait_chair = 1; //凳子 semaphore finish = 0; semaphore ready = 0; barber(){ while(1){ p(ready); //等候为顾客理发，若无顾客，则睡觉 理发; v(finish); //理发完毕，可为下一位顾客理发 } } customer(){ p(mutex); //互斥访问customers if(customer_count <= n){//还有空位 customer_count++; //进店坐下，空位减一 v(mutex); } else { v(mutex); //没有空位，直接离开 } p(wait_chair); //找一个空凳子坐下 p(barber_chair); //等待坐上理发椅 v(wait_chair); //离开凳子，去坐理发椅 v(ready); //通知理发师理发。若理发师在睡觉，则唤醒之 p(finish); //等待理发完成 v(barber_chair); //理发完成，离开理发椅 p(mutex); //互斥访问customer_count customer_count--; //离开，空位加一 v(mutex); }

方法二：将理发椅和凳子看成一种资源

int chairs = n+1; semaphore ready = 0; semaphore finish = 1; semaphore mutex = 1; barber(){ while(1){ p(ready); //等候为顾客理发，若无顾客，则睡觉 理发; p(mutex); chairs--; v(mutex); v(finish); //理发完毕，可为下一位顾客理发 } } customer(){ p(mutex); if(chairs > 0){ //有空位，进店 chairs--; v(mutex); v(ready); //通知理发师理发。若理发师在睡觉，则唤醒之 p(finish); //等待理发完成 } else { v(mutex); //无空位，离开 } }