package jsat.utils.concurrent;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
/**
* Tree Barrier is a barrier that requires only log(n) communication
* for barrier with n threads. To use this barrier, each thread must
* know its own unique ID that is sequential in [0, number of threads)
*
* NOTE: The Tree Barrier implementation is not safe for accessing
* multiple times in a row. If accessed while some threads are still
* attempting to exit, corruption and deadlock can occur. If needed,
* two TreeBarriers can be used by alternating back and forth.
*
* @author Edward Raff
*/
public class TreeBarrier
{
final private int parties;
private Lock[] locks;
private volatile boolean competitionCondition;
/**
* Creates a new Tree Barrier for synchronization
* @param parties the number of threads that must arrive to synchronize
*/
public TreeBarrier(int parties)
{
this.parties = parties;
locks = new Lock[parties-1];
for(int i = 0; i < locks.length; i++)
locks[i] = new ReentrantLock(false);
competitionCondition = true;
}
/**
* Waits for all threads to reach this barrier.
*
* @param ID the id of the thread attempting to reach the barrier.
* @throws InterruptedException if one of the threads was interrupted
* while waiting on the barrier
*/
public void await(int ID) throws InterruptedException
{
if(parties == 1)//what are you doing?!
return;
final boolean startCondition = competitionCondition;
int competingFor = (locks.length*2-1-ID)/2;
while (competingFor >= 0)
{
final Lock node = locks[competingFor];
if (node.tryLock())//we lose, must wait
{
synchronized (node)//ignore warning, its correct. We are using the lock both for competition AND to do an internal wait
{
while(competitionCondition == startCondition)
node.wait();
}
node.unlock();
wakeUpTarget(competingFor*2+1);
wakeUpTarget(competingFor*2+2);
return;
}
else //we win, comete for another round!
{
if(competingFor == 0)
break;//we have won the last round!
competingFor = (competingFor-1)/2;
}
}
//We won! Inform the losers
competitionCondition = !competitionCondition;
wakeUpTarget(0);//biggest loser
}
private void wakeUpTarget(int nodeID)
{
if(nodeID < locks.length)
{
synchronized(locks[nodeID])
{
locks[nodeID].notify();
}
}
}
}
Ads help maintain this website.