Semaphore：如何快速实现一个限流器

Semaphore，信号量/信号灯，类似现实生活里的红绿灯，车辆能不能通行，要看是不是绿灯。在编程世界里，线程能不能执行，也要看信号量是不是允许。

信号量于1965年提出，之后的15年，信号量一直都是并发编程领域的终结者，直到1980年管程被提出来，才有了第二选择。所有支持并发编程的语言都支持信号量机制。

信号量模型

信号量模型可以简单概括为：一个计数器，一个等待队列，三个方法。
在信号量模型里，计数器和等待队列对外是透明的，所以只能通过信号量模型提供的三个方法来访问它们，这三个方法分别是：init()、down()和up()。

init()：设置计数器的初始值。
down()：计数器的值减1；如果此时计数器的值小于0，则当前线程将被阻塞，否则当前线程可以继续执行。
up()：计数器的值加1；如果此时计数器的值小于或者等于0，则唤醒等待队列中的一个线程，并将其从等待队列中移除。

init()、down()、up()三个方法都是原子性的，并且这个原子性是由信号量模型的实现方保证的。在Java SDK里面，信号量模型是由java.util.concurrent.Semaphore实现的，Semaphore这个类能够保证这三个方法都是原子操作。

class Semaphore {
    //计数器
    int count;
    //等待队列
    Queue queue;
    //初始化操作
    Semaphore(int c) {
        this.count = c;
    }

    void down() {
        this.count --;
        if(this.count < 0) {
            //将当前线程插入等待队列
            //阻塞当前线程
        }
    }

    void up() {
        this.count ++;
        if(this.count <= 0) {
            //移除等待队列中的某个线程T
            //唤醒线程T
        }
    }
}

信号量模型里面，down()、up()这两个操作离殇最早称为P操作和V操作，信号量模型也被称为PV原语。(semWait()和semSignal())
在Java SDK并发包里，down()和up()对应的则是acquire()和release()。

信号量实现互斥锁

十字路口的红绿灯可以控制交通，得益于它的一个关键规则：车辆在通过路口前必须先检查是否是绿灯，只有绿灯才能通行。

信号量的使用也是类似的。用累加器的例子说明信号量的使用。在累加器的例子里面，count+=1操作是个临界区，只允许一个线程执行，要保证互斥。
类似互斥锁，在进入临界区之前执行一下down()操作，退出临界区之前执行一下up()操作。

//acquire()是信号量里的down()操作
//release()是信号量里的up()操作

static int count;
//初始化信号量
static final Semaphore s = new semaphore(1);
//用信号量保证互斥
static void addOne() {
    s.acquire();
    try {
        count += 1;
    } finally {
        s.release();
    }
}

信号量保证互斥：假设两个线程T1和T2同时访问addOne()方法，当它们同时调用acquire()的时候，由于acquire()是一个原子操作，所以只能有一个线程(假设T1)把信号量里的计数器减为0，另外一个线程(T2)则是将计数器减为-1。
对于线程T1，信号量里面的计数器的值是0，大于等于0，所以线程T1会继续执行；对于线程T2，信号量里面的计数器的值是-1，小于0，按照信号量模型里对down()操作的描述，线程T2将被阻塞。所以此时只有线程T1会进入临界区执行count+=1。

当线程T1执行release()操作，也就是up()操作的时候，信号量里计数器的值是-1，加1之后的值是0，小于等于0，按照信号量模型对up()操作的描述，此时等待队列中的T2将会被唤醒。于是T2在T1执行完临界区代码之后才获得了进入临界区执行的机会，从而保证了互斥性。

信号量实现限流器

Semaphore不仅可以实现类似Lock的互斥锁，Semaphore还可以允许多个线程访问一个临界区。

比较常见的需求就是工作中遇到的各种池化资源，如连接池、对象池、线程池等。如数据库连接池，在同一时刻，一定是允许多个线程同时使用连接池的，当然每个链接在被释放前，是不允许其他线程使用的。

对象池，一次性创建出N个对象，之后所有的线程重复利用这N个对象，对象在被释放前，是不允许其他线程使用的。(多例模式：可重复利用；对象有线程安全问题)
限流器，不允许多于N个线程同时进入临界区。
信号量的计数器，设置为1时，表示只允许一个线程进入临界区，把计数器的值设置成对象池里对象的个数N，就能解决对象池的限流问题。

对象池限流器示例

class ObjPool<T, R> {
    final List<T> pool;
    //用信号量实现限流器
    final Semaphore sem;
    //构造函数
    ObjPool(int size, T t) {
        pool = new Vector<T>() {};
        for(int i=0; i<size; i++) {
            pool.add(t);
        }
        sem = new Semaphore(size);
    }
    //利用对象池的对象，调用func
    R exec(Function<T, R> func) {
        T t = null;
        sem.acquire();
        try {
            t = pool.remove(0);
            return func.apply(t);
        } finally {//finally语句块在try/catch中的return之前执行
            pool.add(t);
            sem.release();
        }
    }
}

//创建对象池
ObjPool<Long, String> pool = new ObjPool<Long, String>(10, 2);
//通过对象池获取t，之后执行
pool.exec(t -> {
    System.out.println(t);
    return t.toString();
})

用一个List来保存对象实例，用Semaphore实现限流器。
关键的代码是ObjPool里面的exec()方法，这个方法里面实现了限流的功能。
首先调用acquire()方法(与之匹配的是在finally里面调用release()方法)，假设对象池的大小是10，信号量的计数器初始化为10，那么前10个线程调用acquire()方法，都能继续执行，相当于通过了信号灯，而其他线程则会阻塞在acquire()方法上。对于通过信号灯的线程，为每个线程分配了一个对象t(这个分配工作是通过pool.remove(0)实现的)，分配完之后会执行一个回调函数func，而函数的参数正是前面分配的对象t；执行完回调函数之后，他们就会释放对象(这个释放工作是通过pool.add(0)实现的)，同时调用release()方法来更新信号量的计数器。如果此时信号量里计数器的值小于等于0，那就说明有线程在等待，此时会自动唤醒等待的线程。

总结

信号量在其他语言里很有知名度，Java在并发编程领域重点支持的还是管程模型。管程模型理论上解决了信号量模型的一些不足，主要体现在易用性和工程化方面，如用信号量解决阻塞队列问题比管程模型麻烦很多。

信号量可以实现的独特功能就是同事允许多个线程进入临界区，但是信号量不能做的就是同时唤醒多个线程去争抢锁，只能唤醒一个阻塞中的线程。而且信号量模型是没有Condition的概念的，即阻塞线程被唤醒了直接就运行了而不会去检查此时临界条件是否已经不满足了，基于此考虑信号量模型才会涉及出只让一个线程被唤醒，否则就会出现因为缺少Condition检查而带来的线程安全问题。因为缺失了Condition，信号量来实现阻塞队列很麻烦。