semaphore信号量 – 源码巴士

“信号量可以解决一切并发问题”，此话真假暂且不论，但是使用信号量可以更加灵活的解决并发问题这到不假。

抽象数据类型

信号量(sem)使用一个整型来表示，且有且仅有两个原子操作，P操作和V操作：
P()操作：sem - 1，如果sem < 0则当前线程等待且释放占有资源，否则继续。这里我们可以理解为Java中wait()方法。
V()操作：sem + 1，如果sem <= 0唤醒一个等待的P，进入临界区。这里我们可以理解为Java中notify()方法。
在这里插入图片描述
上图的信号灯作为信号量sem，C车到达时执行P()操作，发现此时sem < 0则等待；只有当A车或者B车退出临界区执行V()操作，sem + 1，才会唤醒等待中的C车，此时C车方可进入临界区。

信号量实现

信号量有两种类型：二进制信号量和计数信号量。
二进制信号量，顾名思义就是使用0和1二进制数来表示信号量其值。
计数信号量，会有一个>0的初始值，且这个初始值只能由P、V来操作改变其值。初始值设为大于0，这样可以允许多个执行P操作的线程进入后续操作。

二进制信号量使用

二进制信号量可用于互斥和同步，以下说明均使用伪代码。

二进制信号量实现互斥

二进制信号量实现互斥，同样得给信号量一个初始值，且P操作和V操作需成对出现。

    // 定义一个mutex信号量且初始值为1
    // 这里初始值设为1，是要使得首次一定会进入临界区
    mutex = new Semaphore(1);
    
    // 进入临界区前执行p()操作，mutex - 1
    mutex -> p();
    
    ···
    // 临界区代码
    ···
    // 退出临界区执行v()操作，mutex + 1
    mutex -> v();

二进制信号量实现同步

二进制信号量实现同步，假设有两个线程分别为A、B，且线程A必须等到线程B执行到某个环节之后方可执行。
二进制信号量实现同步初始值应设为0

    // 定义一个condition信号量且初始值为0
    // 这里初始值设为0是为了使得Thread A执行p操作时可以被挂起
    condition = new Semaphore(0);
Thread A
    ···
    // 执行p操作挂起等待
    condition -> p();
    ···
    
Thread B
    ···
    // 执行v操作唤醒等待线程
    condition -> v();
    ···

计数信号量使用

一些稍复杂的并发问题使用二进制信号量就无法优雅的实现了，这时计数信号量就粉墨登场了。

计数信号量实现互斥+同步

一个生产者、消费者问题，假设有一个缓冲区，生产者不断往缓冲区写数据，消费者从缓冲区取数据，同时需满足以下三点要求：

任何时间只能有一个线程操作缓冲区buffer（互斥）；
当缓冲区buffer为空，消费者不消费必须等待生产者（同步）；
当缓冲区buffer满载，生产者不生产必须等待消费者（同步）；

以上三个条件需定义三个信号量方可保证其功能实现：

二进制信号量，用于实现线程间的互斥；
计数信号量emptyBuffer，用于实现缓冲区buffer为空时同步；
计数信号量fullBuffer，用于实现缓冲区buffer满载时同步；

class Buffer{
    // 定义二进制信号量用于缓冲区buffer互斥
    mutex = new Semaphore(1);
    // 定义计数信号量fullBuffer
    // 初始值为表示缓冲区buffer一开始是空的
    fullBuffer = new Semaphore(0);
    // 定义计数信号量emptyBuffer
    // 初始值为缓冲区buffer的最大值，
    emptyBuffer = new Semaphore(n);
}

// 生产者生产操作
deposit(c){
    // 计数信号量emptyBuffer，检查是否已满载（0表示满载）
    // 计数信号量emptyBuffer执行p操作，-1
    // 初始值为n且大于0，表示可重复进入n次或者n个生产者
    emptyBuffer -> p();
    // 二进制信号量mutex执行p操作，检查是否可进入临界区
    mutex -> p();
    ···
    add c to buffer
    ···
    // 二进制信号量mutex执行v操作
    mutex -> v();
    // 计数信号量fullBuffer，告诉消费者取数据
    // 计数信号量fullBuffer执行v操作，+1
    fullBuffer -> v();
}

// 消费者消费操作
remove(c){
    // 计数信号量fullBuffer，检查是否为空，-1
    // 因为fullBuffer的初始值为0，则一开始消费者无法进入缓冲区buffer进行取数据
    fullBuffer -> p();
    // 二进制信号量mutex执行p操作，检查是否可进入临界区
    mutex -> p();
    ···
    add c to buffer
    ···
    // 二进制信号量mutex执行v操作
    mutex -> v();
    // 计数信号量emptyBuffer，告诉生产者生产，+1
    emptyBuffer -> v();
}

以上P、V操作可以交换执行顺序吗？
V操作只是操作信号量+1且唤醒一个线程，因此这里的V操作相互交换执行顺序是不会存在任何问题的。但是P操作相互交换执行顺序就会出现问题，假设将生产者的emptyBuffer -> p()和mutex -> p()交换执行顺序，那么如果此时缓冲区buffer已经满载，下一个生产者进行生产时，先执行mutex -> p()进入临界区，执行emptyBuffer -> p()时发现emptyBuffer为0（因为此时缓冲区buffer已经满载），执行p操作-1，那么就会挂起线程。问题就来了，生产者一直占有mutex信号量，其它线程无法获取mutex信号量，这时就出现了死锁。

原文链接：https://blog.csdn.net/Jas000/article/details/114926104