Introduction to the

Semaphore is a Semaphore, and in the programming world, a thread can execute only if the Semaphore is allowed.

Semaphore model

The semaphore model can be summarized simply as one counter, one wait queue, and three methods.

In the semaphore model, counters and wait queues are transparent to the outside world, so they can only be accessed through the three methods provided by the semaphore model:Init (), down(), up(). We can visualize it using a graph:



The detailed semantics of these three methods are shown below.

  • Init () : Sets the initial value of the counter.
  • Down () : the value of the counter is reduced by 1; If the value of the counter is less than 0 at this point, the current thread is blocked, otherwise the current thread can continue execution.
  • Up () : increments the value of the counter by 1; If the counter value at this point is less than or equal to 0, a thread in the wait queue is woken up and removed from the wait queue.

All three methods are atomic, and this atomicity is guaranteed by the implementor of the semaphore model. Let’s look at the coded semaphore model:

class Semaphore{
	/ / counter
	int count;
	// Wait for the queue
	Queue queue;
	Semaphore(int c){
		this.count = c;
	}
	void down(a){
		this.count--;
		if(this.count < 0) {// Insert the current thread into the wait queue
			// Block the current thread}}void up(a){
		this.count++;
		if(this.count <= 0) {// Remove a thread T from the wait queue
			// Wake up thread T}}}Copy the code

In the Java SDK, down() and up() correspond to acquire() and Release ().

How to use semaphores

                  

Take, for example, the traffic lights we see in our daily life. Traffic lights at intersections control traffic thanks to one of their key rules: vehicles must first check if they are green before crossing the intersection, and only the green light can go together.

The use of semaphores is similar. Let’s use an accumulator to illustrate the use of semaphores. In the accumulator example, the count += 1 operation is a critical section that allows only one thread to execute, which means that mutual exclusion is guaranteed. So how do we control this with semaphores?

Very simple, just like we do with mutex, just perform down() before entering the critical section and up() before exiting the critical section. Acquire () is the down() operation in the semaphore, and Release () is the up() operation in the semaphore.

static int count;
// Initialize the semaphore
static final Semaphore s = new Semaphore(1);
// Use semaphores to ensure mutual exclusion
static void addOne(a){
	s.acquire();
	try(){
		count += 1;
	} finally{ s.release(); }}Copy the code

Perhaps you still don’t understand how semaphores are mutually exclusive.

Suppose two threads T1 and T2 access addOne() at the same time. When acquire() is called at the same time, only one thread (suppose T1) can decrement the semaphore counter to 0 because acquire() is an atomic operation. The other thread (T2) reduces the counter to -1. For thread T1, the counter in the semaphore has a value of 0, greater than or equal to 0, so thread T1 will continue to execute; For thread T2, the count in the semaphore is -1, less than 0, and thread T2 will block as described in the semaphore model for down(). So only thread T1 will enter the critical section and execute count +=1.

When thread T1 performs the release() operation, that is, up() operation, the value of the counter in the semaphore is -1, and the value after adding 1 is 0, less than or equal to 0. According to the description of up() operation in the semaphore model, T2 in the waiting queue will be kept awake. Therefore, T2 gets the opportunity to enter the critical section after T1 finishes executing the critical section code, thus ensuring mutual exclusion.

Quickly implement a current limiter

In the example above, we used a semaphore to implement one of the simplest mutex functions. You may wonder why Semaphore is provided when Lock is available in the Java SDK. Implementing a mutex is only part of Semaphore’s functionality, but there is another feature that Locks can’t easily implement: Semaphore allows multiple threads to access a critical section.

Is there a need for that in reality? There is. More common requirements are the various pooled resources we encounter, such as connection pools, object pools, thread pools, and so on. Of these, we are probably most familiar with database connection pools, which must be used by multiple threads at the same time, although each connection is not allowed to be used by other threads until it is released.

Suppose you encounter a requirement for an object pool at work. Object pooling means that N objects are created at one time and reused by all threads. Of course, objects are not allowed to be used by other threads until they are released. Object pool, you can use List to hold instance objects, this is very simple. But the key is the design of the flow limiter, by which I mean that no more than N threads are allowed to enter the critical area at the same time. So how do you quickly implement such a restrictor? In this scenario, semaphores are a good solution.

The semaphore counter, in the example above, is set to 1, which means that only one thread is allowed to enter the critical section, but if we set the counter to the number of objects in the object pool, N, we can solve the problem of limiting the flow of the object pool perfectly. Here is sample object pool code.

class ObjPool<T.R>{
	final List<T> pool;
	// Implement current limiter with semaphore
	final Semaphore sem;
	// constructor
	ObjPool(int size, T t){
		pool = new Vector<T>(){};
		for(int i=0; i<size; i++){
			pool.add(t);
		}
		sem = new Semaphore(size);
	}
	// Call func using objects from the object pool
	R exec(Function<T, R> func){
		T t= null;
		sem.acquire();
		try{
			t = pool.remove(0);
			return func.apply(t);
		}finally{ pool.add(t); sem.release(); }}}// Create an object pool
ObjPool<Long, String> pool = new ObjPool<Long, String>(10.2);
// Get t from the object pool and execute
pool.exec(t -> {
	System.out.println(t);
	return t.toString();
});
Copy the code

We use a List to store object instances and Semaphore to implement the limiter. The key code is the exec() method in ObjPool, which implements limiting. Inside this method, we first call acquire() (matched by a release() call in finally). Assuming the object pool size is 10 and the semaphore counter is initialized to 10, then the first 10 threads that call acquire() continue execution. The semaphore passes, and other threads block on the acquire() method. For semaphores, we assign an object t (pool.remove(0)) to each thread, and then execute a callback function called func that takes the same object t. After executing the callback, they release the object (via pool.add(t)) and call the release() method to update the semaphore’s counter. If the value of the counter in the semaphore is less than or equal to 0, it indicates that there is a thread waiting, and the waiting thread is automatically woken up.

In short, using semaphores, we can easily implement a current limiter, which is very simple to use.