参考文章：

信号量和条件变量的关系是什么？

信号量

信号量的本质是一个计数器加一个被计数器限制而等待访问的队列

一般的实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
wait(sem* S){
    S->value --;
    if(S->value<0){
        add this process to S->list;
        block();
    }
}               

signal(sem* S){
    S->value ++;
    if(S->value<=0){
        remove a process P from S->list;
        wakeup(P);
    }
}

从信号量到条件变量

首先条件变量一个目的是摆脱计数器只能以计数形式检查条件是否满足的限制，管理形式就不再是一个计数器，因此我们要改变那种一次只通知一个的方式，而是要在条件满足时一口气通知所有在等待的进程，看谁先抢到了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
wait(sem* S){
    while(S->value==0){ // 这里判断条件，注意if变成了while，因为醒过来的进程很可能抢不到机会，因此条件还是成立，于是继续阻塞自己
        add this process to S->list;
        block();
    }
    S->value--;
}               

signal(sem* S){
    S->value++;
        if(S->list非空){ //这里的条件可以多种多样了
            for(auto i in S->list){
                wakeup(i);
            }
        }
}

接下来我们要拓展条件变量的适应性，让条件变量的条件独立出去，可以由用户自定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int value = xx;
sem s;
Mutex mutex;

//消费者
mutex.lock();
while(value==0){
    wait(s.mutex);
}
value--;
mutex.unlock();

wait(sem* S，sem* mutex){ 
    add this process to S->list;
    mutex.unlock();
    block();
    mutex.lock();
} 

//生产者
mutex.lock();
value++;
mutex.unlock();
signal(s);

signal(sem* S){
        if(S->list非空){
            for(auto i in S->list){
                wakeup(i);
            }
        }  
}

现在我们可以自由地变更value的条件，特别注意为了能够互斥的操作条件，我们还引入了锁mutex，而这意味着wait进入等待需要释放mutex避免阻塞其他进程获取mutex，而从等待中醒来需要获取mutex以确保互斥

管程（以霍尔管程为例）

霍尔管程已经不是目前广泛使用的管程，主流管程实际上是MESA管程

管程进一步地抽象了条件变量部分的管理，被分为了enter(), leave(), wait(), signal()四个步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
typedef struct InterfaceModule { //InterfaceModule是结构体的名字
	semaphore mutex;             //进程调用管程过程前使用的互斥信号量
	semaphore next;              //发出signal的进程挂起自己的信号量
	int next_count;              //在next上等待的进程数
};
mutex=1;next=0;next_count=0;//初始化语句
void enter(InterfaceModule &IM) {
P(IM.mutex);             //互斥进入管程
}
void leave(InterfaceModule &IM) {
   if(IM.next_count>0)       //判有否发出过signal的进程?
V(IM.next);          //有就释放一个发出过signal的进程
else
	    V(IM.mutex);         //否则开放管程
}
void wait(semaphore &x_sem,int &x_count,InterfaceModule &IM) {
	x_count++;              //等资源进程个数加1，x_count初始化为0
	if(IM.next_count>0)     //判有否发出过signal的进程
   V(IM.next);          //有就释放一个
	else 
	   V(IM.mutex);        //否则开放管程
	 P(x_sem);              //等资源进程阻塞自己，x_sem初始化为0
x_count--;               //等资源进程个数减1 
}
void signal(semaphore &x_sem,int &x_count,InterfaceModule &IM) {
	if(x_count>0) {           //有等资源进程吗?
	   IM.next_count++;       //发出signal进程个数加1
	   V(x_sem);              //释放一个等资源的进程
	   P(IM.next);           //发出signal进程阻塞自己
       IM.next_count--;      //发出signal进程个数减1
	 }
}

IM.mutex=1; next=0; next_count=0; self[i]=0; self_count=0; state[i]=thinking; 
mutex=1;next=0;next_count=0;