Java - semaphore release without acquisition

Question

I have threads that are given a random number (from 1 to n), and they are prompted to print them in sorted order. I used a semaphore to get the number of permissions = random number and free one permission more than what was acquired.

received = random number; released = 1 + random number

The number of initial permissions for the semaphore is 1. Thus, a stream with a random number of 1 must get permission, and then 2, etc.

This is supported in accordance with the documents below.

There is no requirement that a thread that releases a permission must obtain that permission by calling the get () method.

The problem is that my program gets stuck after 1 for n> 2.

My program is given below:

import java.util.concurrent.Semaphore; public class MultiThreading { public static void main(String[] args) { Semaphore sem = new Semaphore(1,false); for(int i=5;i>=1;i--) new MyThread(i, sem); } } class MyThread implements Runnable { int var;Semaphore sem; public MyThread(int a, Semaphore s) { var =a;sem=s; new Thread(this).start(); } @Override public void run() { System.out.println("Acquiring lock -- "+var); try { sem.acquire(var); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println(var); System.out.println("Releasing lock -- "+var); sem.release(var+1); } } 

Exit:

Blocking Acquisition - 4
Blocking Acquisition - 5
The acquisition of the castle - 3
The acquisition of the castle - 2
Blocking Acquisition - 1
1
Lock Release - 1

While I am modifying my code with tryAcquire, it works fine. Below is a new implementation

 @Override public void run() { boolean acquired = false; while(!acquired) { acquired = sem.tryAcquire(var); } System.out.println(var); sem.release(var+1); } 

Can someone explain the mechanism for obtaining semaphore permission when busy threads are waiting with another permission request?

Answer 1

This is a smart strategy, but you don’t understand how Sempahore hand out permissions. If you run your code enough time, you will see that it reaches the second step:

 Acquiring lock -- 5 Acquiring lock -- 1 1 Releasing lock -- 1 Acquiring lock -- 3 Acquiring lock -- 2 2 Acquiring lock -- 4 Releasing lock -- 2 

If you keep rerunning it enough, you really will see that it successfully completes. This is due to the way Semaphore issues permissions. You assume that Semaphore will try to execute the acquire() call as soon as it has enough permissions to do this. If we carefully consider the documentation for Semaphore.aquire(int) , we will see that this is not the case (my attention):

If insufficient permissions are available, then the current thread is disabled for thread planning purposes and remains inactive until ... some other thread calls one of the release methods for this semaphore, the current thread has the assigned permissions nearby , and the number of available permissions satisfies this request.

In other words, Semaphore stores the queue of the pending purchase request and, after each call to .release() , checks only the queue header. In particular, if you turn on fair queuing (set the second argument of the constructor to true ), you will see that even the first step does not occur, because step 5 is the (usually) first in the queue and even a new acquire() call, which may be completed, will queue for other pending calls.

In short, you cannot rely on .acquire() to return as soon as possible, as your code suggests.

Using .tryAcquire() in a loop, you avoid making blocking calls (and therefore impose a lot more workload on Semaphore ), and as soon as the required number of permissions is available, calling tryAcquire() will successfully get them. It works, but wasteful.

Make a list of expectations in the restaurant. Using .aquire() like you enter your name in a list and expect it to be called. This may not be entirely effective, but they will get to you (reasonably reasonably). Imagine if everyone just shouted to the owner: "Do you have a table for n ?"? as often as possible is your tryAquire() loop. It may still work (as in your example), but this, of course, is not the right way to do this.

---

So what should you do instead? There are a number of useful tools in java.util.concurrent , and it best depends on what exactly you are trying to do. If you see that each thread starts the next thread, I can use BlockingQueue as a synchronization aid, each time pushing the next step into the queue. Then each thread will poll the queue, and if it is not an activated thread, replace the value and wait again.

Here is an example:

 public class MultiThreading { public static void main(String[] args) throws Exception{ // Use fair queuing to prevent an out-of-order task // from jumping to the head of the line again // try setting this to false - you'll see far more re-queuing calls BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(1, true); for (int i = 5; i >= 1; i--) { Thread.sleep(100); // not necessary, just helps demonstrate the queuing behavior new MyThread(i, queue).start(); } queue.add(1); // work starts now } static class MyThread extends Thread { int var; BlockingQueue<Integer> queue; public MyThread(int var, BlockingQueue<Integer> queue) { this.var = var; this.queue = queue; } @Override public void run() { System.out.println("Task " + var + " is now pending..."); try { while (true) { int task = queue.take(); if (task != var) { System.out.println( "Task " + var + " got task " + task + " instead - re-queuing"); queue.add(task); } else { break; } } } catch (InterruptedException e) { // If a thread is interrupted, re-mark the thread interrupted and terminate Thread.currentThread().interrupt(); return; } System.out.println("Finished task " + var); System.out.println("Registering task " + (var + 1) + " to run next"); queue.add(var + 1); } } } 

This prints the following and successfully exits:

 Task 5 is now pending... Task 4 is now pending... Task 3 is now pending... Task 2 is now pending... Task 1 is now pending... Task 5 got task 1 instead - re-queuing Task 4 got task 1 instead - re-queuing Task 3 got task 1 instead - re-queuing Task 2 got task 1 instead - re-queuing Finished task 1 Registering task 2 to run next Task 5 got task 2 instead - re-queuing Task 4 got task 2 instead - re-queuing Task 3 got task 2 instead - re-queuing Finished task 2 Registering task 3 to run next Task 5 got task 3 instead - re-queuing Task 4 got task 3 instead - re-queuing Finished task 3 Registering task 4 to run next Task 5 got task 4 instead - re-queuing Finished task 4 Registering task 5 to run next Finished task 5 Registering task 6 to run next 

Answer 2

The Javadoc for Semaphore.acquire(int) says:

 If insufficient permits are available then the current thread becomes disabled for thread scheduling purposes and lies dormant until one of two things happens: Some other thread invokes one of the release methods for this semaphore, the current thread is next to be assigned permits and the number of available permits satisfies this request [or the thread is interrupted]. 

A thread that is "next to the destination" is probably thread 4 in your example. He waits until 4 permissions are available. However, thread 1, which gets permission when calling the get () function, releases only 2 permissions, which is not enough to unlock thread 4. Meanwhile, thread 2, which is the only thread that has sufficient permissions, is not next assigned therefore it does not receive permission.

Your modified code works fine because the threads are not blocked when they try to get the semaphore; they just try again, moving to the background. In the end, stream 2 reaches the front of the line and, therefore, is located next to it, and therefore receives its permission.