并发程序设计--信号量与 PV 操作

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();
}

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]; 
        }
    }
}

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);
}