import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
public class tree_lock_test{
int total_instances;
int thread_instances = 0;
int N;
static int cnt = 0;
static int cnt2 = 0;
int flag = 0;
Node root;
Peterson[] PeterInstances;
Thread[] thread;
int[] IncomingThreadIDs;
final private ThreadLocal<Integer> THREAD_ID2 = new ThreadLocal<Integer>(){
final private AtomicInteger id2 = new AtomicInteger(0);
protected Integer initialValue(){
return id2.getAndIncrement();
}
};
tree_lock_test(int n) throws Exception
{
N=n;
int temp = n;
total_instances = n - 1;
int[] IDs = new int[total_instances];
//IncomingThreadIds = new int[n];
//Determine number of instances of each thread
while(temp != 1)
{
temp /=2;
thread_instances++;
}
PeterInstances = new Peterson[total_instances];
for(int i = 0; i < total_instances; i++)
{
PeterInstances[i] = new Peterson();
}
//IncomingThreadIDs = new int[n];
//Create IDs for each thread
for(int i = 0; i < n;i+=2)
{
thread[i] = new MyThread(i);
thread[i+1] = new MyThread(i+1);
//IncomingThreadIDs[i] = cnt;
//IncomingThreadIDs[i+1] = cnt+1;
//cnt+=2;
}
for (int i = 0; i < n; i++) {
thread[i].start();
}
for (int i = 0; i < n; i++) {
thread[i].join();
}
//Create array with keys for each node in binary tree
for(int i = 0; i < total_instances;i++)
{
IDs[i]=i;
}
//Create binary tree with keys from above array
BuildTree(0,IDs.length-1,IDs);
}
//Function : BuildTree
//Input : lowest index of array, high index of array, pointer to array
//Output : Balanced Binary Tree
//Description: Createds a Balanced Binary Tree
//Credit to: David on Software: How to Build a Balanced Binary Search Tree From an Array
public Node BuildTree(int low, int high, int[] arr)
{
if(low > high)
return null;
else
{
int mid = (low + high)/2;
Node node = new Node(arr[mid]);
if(flag == 0)
{
root = node;
flag++;
}
node.leftChild = BuildTree(low,(mid-1),arr);
node.rightChild = BuildTree((mid+1),high,arr);
return node;
}
}
//Function : findNodeParent
//Input : key for a node
//Output : key of parent node
//Description : Determines the key for a parent node
public int findNodeParent(int key)
{
if(root.key == key)
return -1;
Node focusNode = root;
while(focusNode.leftChild.key != key && focusNode.rightChild.key != key)
{
if(key < focusNode.key)
{
focusNode = focusNode.leftChild;
}
else
{
focusNode = focusNode.rightChild;
}
}
return focusNode.key;
}
//Function : lock
//Description : locks other threads
//public void lock()
class MyThread extends Thread
{
int k;
public MyThread(int t)
{
int k = t;
IncomingThreadIDs[k] = t;
}
public void run()
{
//get thread ID
int cnt3 = (THREAD_ID2.get() % N);
int[] path = new int[thread_instances];
path[0] = IncomingThreadIDs[cnt3];
//create path to root node
for(int k = 1; k < thread_instances; k++)
{
path[k] = findNodeParent(path[k-1]);
}
//attempt to lock thread up to root node
for(int i = 0; i < thread_instances; i++)
{
PeterInstances[path[i]].lock();
//ThreadID = findNodeParent(ThreadID);
}
for(int k = 1; k < thread_instances; k++)
{
path[k] = findNodeParent(path[k-1]);
}
//attempt to unlock thread to the node
for(int i = thread_instances - 1; i >= 0; i--)
{
PeterInstances[path[i]].unlock();
}
}
}
// Any class implementing Lock must provide these methods
//public Condition newCondition() {
//throw new java.lang.UnsupportedOperationException();
//}
//public boolean tryLock(long time,
// TimeUnit unit)
//throws InterruptedException {
//throw new java.lang.UnsupportedOperationException();
//}
//public boolean tryLock() {
//throw new java.lang.UnsupportedOperationException();
//}
//public void lockInterruptibly() throws InterruptedException {
//throw new java.lang.UnsupportedOperationException();
//}
public static void main(String[] args)
{
try{
tree_lock_test tree = new tree_lock_test(8);
}
catch(Exception e){}
}
}
class Node
{
int key;
Node leftChild;
Node rightChild;
Node parent;
Node(int key)
{
this.key = key;
}
}
this is compiled with another Peterson class which has implemeted peterson lock for two threads