操作系统—经典同步问题
补充
互斥信号量mutex初值均为1
同步信号量根据问题实际描述自己设计
生产者-消费者问题
问题描述：一组生产者进程和一组消费者进程 共享一个初始为空、大小为n的缓冲区。（缓冲区：临界资源）
- 只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待
- 只有缓冲区不空时，消费者才能从中取出消息，否则必须等待
- 信号量mutex：互斥信号量，用于控制互斥访问缓冲池，初值为1
- 信号量full：同步信号量，用于记录当前缓冲池中的“满”缓冲区数，初值为0
- 信号量empty：同步信号量，用于记录当前缓冲池中的“空”缓冲区数，初值为n
注：①实现互斥的P操作一定要在实现同步的P操作之后
②两个V操作顺序可以交换
semaphore mutex=1; //临界区互斥信号量
semaphore empty=n; //同步信号量，表示空闲缓冲区数量
semaphore full=0; //同步信号量，缓冲区初始化为空，表示满缓冲区数量
producer(){ //生产者进程while(1){produce an item in nextp; //生产数据P(empty); //获取空缓冲区单元，消耗一个空闲缓冲区P(mutex); //进入临界区add nextp to buffer; //将数据放入缓冲区V(mutex); //离开临界区，释放互斥信号量V(full); //满缓冲区数+1，即增加一个产品}
}
//V(full)和P(full)：实现两进程的同步关系，是在其中一个进程执行P，另一个进程执行V
consumer(){ //消费者进程while(1){P(full); //获取满缓冲区单元，消耗一个产品（非空缓冲区）P(mutex); //进入临界区remove an item from buffer; //从缓冲区中取出数据V(mutex); //离开临界区，释放互斥信号量V(empty); //空缓冲区数+1，即增加一个空闲缓冲区consume the item; //消费数据}
}
多生产者-多消费者
问题分析：桌上有一个盘子，每次只能向其中放入一个水果。
- 只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果
- 仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出
如图，儿子和女儿之间没有互斥和同步关系。
- 信号量plate：互斥信号量，表示是否允许向盘子放入水果，初值为1（表示允许放入，且只允许放入一个）
- 信号量apple：同步信号量，表示盘子中是否有苹果，初值为0（表示盘子为空，不许取，apple=1可取）
- 信号量orange：同步信号量，表示盘子中是否有橘子，初值为0（表示盘子为空，不许取，apple=1可取）
注：在缓冲区大小=1的情况下，可以不设置mutex。但若缓冲区大小>1，则需要设置mutex
semaphore plate=1,apple=0,orange=0;
dad(){ //父亲进程while(1){prepare an apple; P(plate); //互斥向盘中取、放水果，相当于盘子数-1put the apple on the plate; //向盘中放苹果V(apple); //允许取苹果，相当于苹果数+1}
}
mom(){ //母亲进程while(1){prepare an orange;P(plate);put the orange on the plate;V(orange);}
}
son(){ //儿子进程while(1){P(orange); //互斥向盘中取橘子，相当于盘中橘子数-1take an orange from the plate;V(plate); //允许向盘中取、放水果，相当于盘子数+1，告诉父母盘子空了eat the orange;}
}
daughter(){ //女儿进程while(1){P(apple);take an apple from the plate;V(plate);eat the apple;}
}
读者-写者问题
问题描述：有读者和写者两组并发进程，共享一个文件
- 允许多个读者同时对文件执行读操作
- 只允许一个写者往文件中写信息
- 任意一个写者在完成写操作前不允许其他读者或写者工作
- 写者执行写操作前，应让已有的读者和写者全部退出
- 信号量count：记录当前读者的数量，初值为0
- 互斥信号量mutex：保护更新count变量时的互斥
- 互斥信号量rw：保证读者和写者的互斥访问
读进程优先
int count=0; //用于记录当前的读者数量
semaphore mutex=1; //用于保护更新count变量时的互斥
semaphore rw=1; //用于保证读者和写者互斥的访问文件
writer(){ //写者进程while(1){P(rw); //互斥访问共享文件——加锁writing; //写入V(rw); //释放共享文件——解锁}
}
reader(){ //读者进程while(1){P(mutex); //互斥访问count变量if(count==0) //当第一个进程读共享文件时——加锁P(rw); //阻止写进程写count++; //读者计数器+1V(mutex); //释放互斥变量countreading; //读取P(mutex); //互斥访问count变量count--; //读者计数器-1if(count==0) //当最后一个进程读共享文件时——解锁V(rw); //允许写进程写V(mutex); //释放互斥变量count}
}
读进程优先会导致：写进程“饿死”
写进程优先
当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行
- 增加一个信号量w：用于实现“写优先”，初值为1
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++; //读者计数器+1V(mutex); //释放互斥变量countV(w); //恢复对共享文件的访问reading; //读取P(mutex); //互斥访问count变量count--; //读者计数器-1if(count==0) //当最后一个进程读共享文件时——解锁V(rw); //允许写进程写V(mutex); //释放互斥变量count}
}
哲学家进餐问题
问题描述：一张圆桌边上坐着5名哲学家，每两名哲学家之间的桌上摆一根筷子，两根筷子中间是一碗米饭。哲学家们只会思考和进餐。
注：若遇到一个进程需要同时持有多个临界资源的情况，应参考哲学家问题的思想
- 哲学家在思考时，并不影响他人
- 只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根拿起）
- 若筷子已在他人手上，则需要等待
- 饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐。进餐完毕后，放下筷子继续思考
- 互斥信号量数组chopstick[5]={1,1,1,1,1}：用于对5个筷子的互斥访问
- 哲学家 i 号，左边筷子编号为 i ，右边筷子编号为 (i+1)%5
制定规则：当一名哲学家左右两边的筷子都可用时，才允许他抓起筷子（并不保证都可用时拿起）
semaphore chopstick[5]={1,1,1,1,1}; //初始化信号量
semaphore mutex=1; //设置取筷子的信号量
Pi(){ //i号哲学家的进程do{P(mutex); //在取筷子前获得互斥量P(chopstick[i]); //取左边筷子P(chopstick[(i+1)%5]); //取右边筷子V(mutex); //释放取筷子的信号量eat; //进餐V(chopstick[i]); //放回左边筷子V(chopstick[(i+1)%5]); //放回右边筷子think; //思考}while(1);
}
//哲学家进餐模板
//定义大锁
semaphore lock=1;
//定义资源数int
//如 有a、b、c三类资源，分配有9、8、5个，则定义3个int变量：int a=9; int b=8; int c=5;
Process(){while(1){P(lock);if(所有资源都够){所有资源int值减少;取xxx资源;V(lock);break;}V(lock);}做进程该做的事; //用中文说明即可P(lock);归还所有资源，所有资源int值增加;V(lock);
}
吸烟者问题（生产多个产品的单生产者）
问题描述：一个系统有三个抽烟者进程和一个供应者进程。
- 抽烟者需要三种材料：烟草、纸和胶水
- 第一个抽烟者拥有烟草，第二个抽烟者拥有纸，第三个抽烟者拥有胶水
- 供应者无限提供三种材料，供应者每次将两种材料（组合）放到桌子上。
- 拥有剩下那种材料的抽烟者卷一根烟并抽掉，同时给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌上
- 供应者与三个抽烟者是同步关系；三个抽烟者对抽烟这个动作是互斥
- 信号量offer1，offer2，offer3分别表示两两组合（烟草和纸的组合、烟草和胶水的组合、纸和胶水的组合）
- 信号量finish：用于互斥进行抽烟动作
int num=0; //存储随机数
semaphore offer1=0; //定义信号量对应烟草和纸组合的资源
semaphore offer2=0;
semaphore offer3=0;
semaphore finish=0; //定义信号量表示抽烟是否完成
provider(){ //供应者while(1){num++;num=(num+1)%3;if(num==0)V(offer1); //提供烟草和纸else if(num==1)V(offer2); //提供烟草和胶水elseV(offer3); //提供纸和胶水任意两种材料放在桌子上;P(finish);}
}
smoker1(){ //拥有烟草者while(1){P(offer3); //检查是否为组合3拿纸和胶水，卷成烟，抽掉;V(finish);}
}
smoker2(){ //拥有纸者while(1){P(offer2);拿烟草和胶水，卷成烟，抽掉;V(finish);}
}
smoker3(){ //拥有胶水者while(1){P(offer1);拿烟草和纸，卷成烟，抽掉;V(finish);}
}
理发师叫号
问题描述：一位理发师、一把理发椅，n把顾客等待理发的椅子
- 无顾客，理发师在理发椅上睡觉
- 有顾客，顾客叫醒理发师
- 理发师正在理发时，有顾客，该顾客坐在空椅上，若无空椅，则离开
int num=0; //表示有几个顾客等待被服务
semaphore lock=1; //互斥访问num
semaphore rest=0; //同步信号量，让服务人员排队等待的队列
semaphore wait=0; //同步信号量，让顾客排队等待的队列
Server(){ Customer(){while(1){ P(lock);P(lock); if(num>等待人数上限){ //有些场景可能没有规定人数上限if(num>0){ V(lock);num--; 离开;叫号; }else{V(lock); num++;V(wait); //唤醒一个顾客 取号/排队;为顾客服务; V(lock);}else{ V(rest); //唤醒一个等待的服务人员V(lock); P(wait); //等待被服务P(rest); //服务人员休息 被服务;} }} }
}