临界资源: 并发程序之间需要互斥使用的共享资源
设 s 是一个记录型数据结构, 一个分量为 int value, 另一个为信号量队列 queue
typedef enum {
RUNNABLE, // 就绪, 位于就绪队列队首的进程为执行态
TIMED_WAITING,//
WAITING,
BLOCKED
} STATE;
// 数组实现的队列
typedef struct s_queue{
PROCESS* procs[NR_TASKS]; // 存放进程指针的数组, NR_TASKS 为进程数(在此次实验中未严格区分用户进程和系统任务)
int begin; // 队首
int length; // 队尾
} QUEUE;
// 信号量
typedef struct s_semaphore {
int value; // 信号量的值
QUEUE queue; //等待队列
} SEMAPHORE;
void enqueue(QUEUE *q,PROCESS*proc){
q->procs[(q->begin+q->length++)%NR_TASKS] = proc;
}
PROCESS* dequeue(QUEUE*q){
PROCESS* p;
q->length--;
p = q->procs[q->begin];
q->begin = (q->begin+1)%NR_TASKS;
return p;
}
void P(SEMAPHORE*s){
// 资源足够的话直接走了
if(--(s->value)>=0){return;}
// 当前进程设为阻塞, 移出就绪队列, 移入 s 的等待队列
p_proc_ready->state=BLOCKED;
dequeue(&readyQueue);
enqueue(&(s->queue),p_proc_ready);
// 立即调度
schedule();
}
void V(SEMAPHORE*s){
if(++(s->value)>0){
// 这说明没有进程正在等待这个资源
return;
}
// 唤醒阻塞的进程
PROCESS*p = dequeue(&(s->queue));//队首可获得资源
p->state = RUNNABLE;
enqueue(&readyQueue,p);
schedule();
}
最多只有 4 名哲学家同时取叉子
每次只允许一个人拿左右叉子
semaphore forks[5];
for(int i=0; i<5; i++)
fork[i]=1;
semaphore mutex = 1; // 互斥量
process philosopher(int i){ //i=0,1,2,3,4
while(1){
think();
hungry();
P(mutex);
P(fork[i]); // 请求右手边的叉子
P(fork[(i+1)%5]; // 请求左手边的叉子
V(mutex); // 释放, 因为允许多个哲学家同时吃饭
eat();
V(fork[i]);
V(fork[(i+1)%5];
}
}
偶数的哲学家先右后左, 奇数哲学家先左后右
semaphore forks[5];
for(int i=0; i<5; i++)
fork[i]=1;
process philosopher(int i){ //i=0,1,2,3,4
while(1){
if(i%2){
// 奇数
P(fork[(i+1)%5]; // 请求左手边的叉子
P(fork[i]); // 请求右手边的叉子
eat();
V(fork[i]);
V(fork[(i+1)%5];
} else {
// 偶数
P(fork[i]); // 请求右手边的叉子
P(fork[(i+1)%5]; // 请求左手边的叉子
eat();
V(fork[i]);
V(fork[(i+1)%5];
}
}
}
无论是怎样的套路都差不多, 每生产几个产品才拿一个, 多个缓冲单元, 多级生产者消费者什么的… 对于一组生产者消费者, 设置一个 empty 信号量, 表示缓冲区尚能放几次产品; 一个 full 信号量, 表示缓冲区中可以取几次产品.
涉及到计数量的变化, 需要互斥.
例子: 多个生产者, 多个消费者, k 个缓冲单元, 生产者每次放一个产品, 消费者每次拿一个
semaphore empty = k; // 尚能放 k 此产品
semaphore full = 0; // 一开始缓冲区为空
// 缓冲区可以当成一个队列, 每个单元可以认为是独立的, 所以此处不必生产者和消费者互斥, 但是
// 如果像仓库问题限制同时使用缓冲区的进程数, 那么还得加一个互斥量
int head = 0;
int tail = 0;
Product buf[k];
semaphore mutex1 = mutex2 = 1; // 生产者之间, 消费者之间互斥
//m 个生产者
process producer(){
while(true){
product = makeProduct();
P(empty); // 有位置才能放
P(mutex1);
head = (head+1)%k;
buf[head] = product;
V(mutex1);
V(full); // 通知消费者可以拿东西
}
}
// n 个消费者
process cosumer(){
while(true){
P(full); // 有东西才能拿
P(mutex2);
product = buf[tail];
tail = (tail+1)%k;
V(empty); // 通知生产者可以放东西
V(mutex2);
}
}
感觉差不多是生产者消费者问题的变种, 特点是特定的消费者消费特定的生产者, 那么只需针对不同的产品设定不同的信号量即可
semaphore sp = 1; // 盘子里放 1 个水果
semaphore s1 = s2 = 0; // 盘子里有 0 个苹果, 0 个橘子
process father(){
P(sp);
// 放橘子
V(s2);
}
process mother(){
P(sp);
// 放苹果
V(s1);
}
process daughter(){
P(s2);
// 吃橘子
V(sp);
}
process son(){
P(s1);
// 吃苹果
V(sp);
}
semaphore empty = 1; // 香烟供应者一开始可以放一次
semaphore s1=s2=s3=0; // 三个人都不能拿
process producer(){
// 一共就三种情况, 放烟草火柴, 火柴纸,或者烟草纸
int i=RAND()%3;
P(empty);
switch(i){
case 0:
V(s1);
break;
case 1:
V(s2);
break;
case 2:
V(s3);
break;
}
}
// 吸烟者
process consumer(){
// 三个吸烟者 P 的信号不一样
P(s_k);
// 拿东西组装烟
V(empty);
}