操作系统信号量的使用四大经典问题/生产者-消费者问题/读者-写者问题/哲学家就餐问题/理发师问题
信号量 机制
用户进程可以使用操作系统提供的一对原语来对信号量进行操作，从而方便的实现进程互斥与同步。
wait和signal原语，也就是P V操作，对信号量进行加/减。
整型信号量
用一个整数型变量作为信号量，用来表示系统中某种资源的数量，但不满足让权等待，会发生忙等。
int S = 1;
void wait(int S){
while(S <= 0);
S = S-1;
}
void signal(int S){
S = S+1;
}
记录型信号量
用记录型数据结构表示的信号量。
typedef struct{
int value;
struct process *L;
}semaphore;
void wait(semaphore S){
S.value --;
if(S.value < 0) {
block(S.L);
}
}
void signal(semaphore S){
S.value ++;
if(S.value <= 0){
wakeup(S.L);
}
}
And型信号量与信号量集
AND型信号量基本思想是将进程在整个运行过程中需要的所有资源一次性全部分配给进程，待进程使用完后再一次释放。信号量集则是一种AND信号量的扩充， 实现了对进程所申请的所有资源以及每 类 ** 不同的资源需求量，在一次PV操作中完成申请与释放。
生产者 -消费者问题
semaphore mutex = 1; // 记录缓冲区读写权限
semaphore full = 0; // 记录已经生产的商品
semaphore empty = n; // 记录缓冲区空位
// 生产者
producer(){
while(1){
P(empty);
P(mutex);
product();
V(mutex);
V(full);
}
}
// 消费者
consumer(){
while(1){
P(full);
P(mutex);
consume();
V(mutex);
V(empty);
}
}
读者-写者问题
只使用记录型信号量，不考虑信号量集。
读者优先（非写者优先）
semaphore mutex1 = 1; // 记录文件访问权限
semaphore mutex2 = 1; // 记录变量访问权限
int readers = 0; // 记录当前正在读的读者
// 写者
writer(){
while(1){
P(mutex1);
write();
V(mutex1);
}
}
// 读者
reader(){
while(1){
P(mutex2);
if(readers == 0) P(mutex1);
readers++;
V(mutex2);
reading();
P(mutex2);
readers--;
if(readers == 0) V(mutex1);
V(mutex2);
}
}
写者优先
使用一个信号量来使得写者来访时阻塞后续的读者
semaphore mutex1 = 1; // 记录文件访问权限
semaphore mutex2 = 1; // 记录变量访问权限
semaphore w = 1; // 记录当前是否有写者申请访问
int readers = 0; // 记录当前正在读的读者
// 写者
writer(){
while(1){
P(w);
P(mutex1);
write();
V(mutex1);
V(w);
}
}
// 读者
reader(){
while(1){
P(w); // 如果当前已有写者请求，不再允许读者访问
P(mutex2);
if(readers == 0) P(mutex1);
readers++;
V(mutex2);
V(w);
reading();
P(mutex2);
readers--;
if(readers == 0) V(mutex1);
V(mutex2);
}
}
使用swait门控开关
semaphore mutex = 1;
semaphore file = 1; // 控制文件访问权
semaphore writewant = 1; // 用作阻塞读者的门控
int readcount = 0;
int writecount = 0; // 用作记录当前写者
// 读者
void readFile(){
while(1){
swait(writewant, 1, 0); // writewant==0时禁止读者访问
P(mutex);
if(readcount <= 0) P(file); // 没有读者，请求文件
readcount++;
V(mutex);
read();
P(mutex);
readcount--;
if(readcount <= 0) V(file); // 没有读者，释放文件
V(mutex);
}
}
// 写者
void writeFile(){
while(1){
P(mutex);
writecount++; // 写者到达
if(writecount == 1) P(writewant); // 有写者，阻塞门控
V(mutex);
P(file);
write();
P(mutex);
writecount--;
if(writecount <= 0) V(writewant); // 释放门控
V(mutex);
V(file); // 释放文件
}
}
哲学家就餐问题
最多允许四个哲学家同时坐在桌子周围
semaphore n = 4; // 记录已经入座的哲学家
semaphore chopsticks[5] = {1,1,1,1,1};
Pi(){
while(1){
P(n);
P(chopsticks[i]);
P(chopsticks[(i+1) % 5]);
eat();
V(chopsticks[i]);
V(chopsticks[(i+1) % 5]);
V(n);
}
}
必须同时拿起两根筷子
semaphore mutex = 1; // 设置取筷子的信号量
semaphore chopsticks[5] = {1,1,1,1,1};
Pi(){
while(1){
P(mutex);
P(chopsticks[i]);
P(chopsticks[(i+1) % 5]);
V(mutex);
eat();
V(chopsticks[i]);
V(chopsticks[(i+1) % 5]);
}
}
打瞌睡的理发师
semaphore customers = 0; // 记录当前等待的顾客
semaphore barbers = 0; // 记录当前理发师情况
semaphore mutex = 1; // 实现等待者的互斥访问
int waiting = 0;
void customer(){
while(1){
P(mutex);
if(waiting < 5){
waiting++;
V(customers); // 等待的顾客增加
V(mutex);
P(barbers); // 尝试申请理发师
get_haircut();
}else{
V(mutex);
leave();
}
}
}
void barber(){
while(true){
P(customers); // 没有顾客就打瞌睡
P(mutex);
waiting--;
V(babers); // 准备理发;
V(mutex);
cut_hair();
}
}
end