条件变量与信号量

条件变量

条件变量的引入是为了解决互斥锁中的循环等待问题，其希望引入一种挂起、唤醒的机制来实现cpu的高效利用
使用条件变量解决生产者消费者问题：

int empty_slot = 5;
int filled_slot = 0;
struct cond empty_cond;//缓冲区无空位（满）
struct lock empty_cnt_lock;//互斥锁
struct cond filled_cond;//缓冲区无数据（空）
struct lock filled_cnt_lock;//互斥锁

void producer(void)
{
    int new_msg;
    while(TRUE){
        new_msg = prodece_new();
        lock(&empty_cnt_lock);//加锁，进入临界区
        while(empty_slot == 0)//缓冲区无空槽
            //挂起当前线程，并释放互斥锁（原子性），其中两个形参分别为条件变量和互斥锁
            cond_wait(&empty_cond,&empty_cnt_lock);//等待slot>0，故empty_cond
        empty_slot--;
        unlock(&empty_cnt_lock);
        
        buffer_add_safe(new_msg);//利用互斥锁来生产
        
        lock(&filled_cnt_lock);
        filled_slot++;
        cond_signal(&filled_cond);//一般放在临界区内唤醒
        unlock(&filled_cnt_lock);
    }
}
void consumer(void)
{
    int cur_msg;
    while(TRUE){
        lock(&filled_cnt_lock);//加锁，进入临界区
        while(filled_slot == 0)//缓冲区无数据
            //挂起当前线程，并释放互斥锁（原子性），其中两个形参分别为条件变量和互斥锁
            cond_wait(&filled_cond,&filled_cnt_lock);
        filled_slot--;
        unlock(&filled_cnt_lock);
        
        cur_msg = buffer_remove_safe();
        
        lock(&empty_cnt_lock);
        empty_slot++;
        cond_signal(&empty_cond);//唤醒等待在此变量上的生产者
        unlock(&empty_cnt_lock);
        consume_msg(cur_msg);
    }
}

条件变量的实现中要注意，当线程调用cond_wait()时需要将当前线程加入等待队列并原子地挂起当前线程并释放锁

void cond_wait(条件变量，互斥锁){
      加入条件变量的等待队列
      原子挂起并放互斥锁
      重新获得锁
}

信号量semaphore [ˈseməfɔːr]

Dijkstra提出了信号量机制，并只可以通过P(Proberen 检验) V(Verhogen 自增)操作来进行更新信号量，一般分别用wait和singal表示。wait检查信号量的值，小于等于0就循环等待，大于0就消耗资源，即减少信号量的值。signal会增加信号量的值供wait使用。
信号量解决生产者消费者问题：

sem_t empty_slot;//空闲的缓冲区资源
sem_t filled_slot;//已经填入的资源

void producer(){
    int new_msg;
    while(TRUE){
        new_msg = produce_new();
        wait(&empty_slot);//P操作
        buffer_add_safe(new_msg);//利用互斥锁进行安全增加信息
        signal(&filled_slot);//V操作
    }
}
void consumer(){
    int cur_msg;
    while(TRUE){
        wait(&filled_slot);//P操作
        cur_msg = buffer_remove_safe();//利用互斥锁进行安全消耗信息
        signal(&empty_slot);//V操作
        consume(cur_msg);
    }
}

信号量实现时存在一些问题：当多个线程共享信号量时，如果不进行原子更新信号量就会出现某个线程更新了旧值，类似于CPU cache对不同线程的不可见问题。其次，就算原子更新，如果出现多个线程同时对信号量进行减少操作，会出现负值。
为了解决以上的问题，我们需要利用互斥锁和条件变量来实现信号量

struct sem{
    int value;//没有线程等待时，value>=0,为剩余资源数；有线程等待则为等待的线程数
    int wakeup;//有线程等待时可用资源数
    struct lock sem_lock;
    struct cond sem_cond;
}

void wait(struct sem *S){
    lock(&S->sem_lock);
    S->value--;
    if(S->value < 0){
        do{
            cond_wait(&S->sem_cond, &S->sem_lock);
        }while(S->wakeup == 0);
        S->wakeup--;
    }
    unlock(&S->sem_lock);
}

void signal(struct sem *S){
    lock(&S->sem_lock);
    S->value++;
    if(S->value <= 0){
        S->wakeup++;
        cond_signal(&S->sem_cond);
    }
    unlock(&S-sem_lock);
}

进入wait后首先将value-1，如果值>=0，则代表还有空闲资源，直接unlock，如果小于0就查看wakeup，如果wakeup为0，就挂起线程。

互斥锁与信号量的异同

当信号量的初值为1，且在0和1之间变化时，成为二元信号量。其与互斥锁的区别在于：互斥锁有拥有者这一概念，信号量则没有。互斥锁由同一线程加放锁，信号量可以由不同线程进行PV操作。
计数信号量允许多个线程，且值为剩余可用资源数量。互斥锁保证多个线程对一个共享资源的互斥访问，信号量用于协调多个线程对一系列资源的访问