实现信号量

Ruby 的 concurrent gem 确实提供了自己的 Semaphore 实现；然而，使用监视器（monitor）来学习实现一个信号量是一个有趣的练习。

简要来说，信号量是一种允许部分线程并行访问一组固定资源的机制。始终将信号量视为拥有固定数量的许可。一旦所有许可都被分配出去，请求许可的线程就必须等待，直到有许可被归还后才能继续执行。

你的任务是实现一个信号量，其构造函数接收允许的最大许可数量，并且初始化时也具有相同数量的许可。此外，如果所有许可都已分配完毕，信号量应阻塞尝试获取许可的线程。

根据上述定义，我们可以开始思考我们的 Semaphore 类需要暴露哪些方法。我们需要一个“获取许可”的方法和一个“释放许可”的方法。

1. acquire() 方法用于模拟获取许可
2. release() 方法用于模拟释放许可

构造函数接受一个整数参数，表示信号量可用的许可数量。内部我们需要维护一个计数器，用于跟踪已经分配出去的许可数量。

目前，我们的 Semaphore 类的框架如下所示。

1class CountingSemaphore
2
3  def initialize(maxPermits)
4    @maxPermits = maxPermits
5    @givenOut = 0
6  end
7
8  def acquire()
9
10  end
11
12  def release()
13
14  end
15
16end

需要注意的是，acquire() 和 release() 这两个方法可能由不同的线程同时调用，因此我们必须使用某种锁来保护它们内部的逻辑。

我们可以使用 Monitor 类来实现互斥以及线程之间的通信。

现在让我们填充 acquire() 方法的实现。当线程不允许获取信号量时是什么情况？当所有许可都已分配出去时。这意味着当 givenOut == maxPermits 时，我们需要等待一个许可变得可用。如果该条件不成立，我们只需递增 givenOut 来模拟分配一个许可。由于在没有许可可用时需要 等待，这提示我们可以使用监视器对象创建一个条件变量，并对条件变量调用 wait()。

acquire() 方法的实现如下所示。注意，我们在方法末尾还调用了 broadcast() 通知条件变量。稍后我们将讨论为什么选择广播而不是单次唤醒。

1  def acquire()
2
3    @monitor.enter()
4
5    while @givenOut == @maxPermits
6      @condVar.wait()
7    end
8
9    @givenOut += 1
10    @condVar.broadcast()
11    
12    @monitor.exit()
13  end

实现 release() 方法只需要简单地将 givenOut 变量减一。但是，什么时候应该像在 acquire() 方法中那样阻塞线程？当 givenOut == 0 时，再减一就没有意义了，因此我们应该在此条件下阻塞等待。

这可能看起来有些反直觉：你可能会问，为什么有人会在调用 acquire() 之前就调用 release()？这种情况完全可能发生，因为信号量也可以用于线程间的通信。一个线程可以在另一个线程调用同一信号量的 acquire() 之前就调用 release()。信号量没有所有权的概念！因此不同线程可以自由调用 acquire() 或 release() 方法。

这也意味着，每当我们在 givenOut 变量上进行增减操作时，都需要对条件变量调用 broadcast()，以确保其他方法中等待的线程能够继续执行。完整的实现如下：

1class CountingSemaphore
2
3  def initialize(maxPermits)
4    @maxPermits = maxPermits
5    @givenOut = 0
6    @monitor = Monitor.new
7    @condVar = @monitor.new_cond()
8  end
9
10  def acquire()
11    @monitor.enter()
12
13    while @givenOut == @maxPermits
14      @condVar.wait()
15    end
16
17    @givenOut += 1
18    @condVar.broadcast()
19
20    @monitor.exit()
21  end
22
23  def release()
24    @monitor.enter()
25
26    while @givenOut == 0
27      @condVar.wait()
28    end
29
30    @givenOut -= 1
31    @condVar.broadcast()
32
33    @monitor.exit()
34  end
35
36end

拓展问题 #1

注意，在两个方法中，我们都在对 givenOut 变量进行增减操作之后才调用 broadcast()。如果我们交换这两个语句的顺序，是否会有影响？答案是没有。因为在任一方法中的线程会一直持有与监视器关联的锁，直到调用 monitor.exit()，而这是两个方法的最后一条语句。等待条件变量的线程在被唤醒后，必须重新获取监视器才能继续执行，因此这两个语句的顺序并不重要。