Peterson Алгоритм как двоичное дерево

Question

В настоящее время я пытаюсь написать программу Java, которая решает эту проблему.

«Другой способ обобщения двухпоточной блокировки Петерсона состоит в том, чтобы расположить ряд двухпоточных замков Петерсона в двоичном дереве. Предположим, что n - это мощность 2. Каждому потоку назначается блокировка листа, с которой она делится один другой поток. Каждый замок обрабатывает один поток как нить 0, а другой - как нить 1. "

Я чувствую, что решил, но мой вывод не всегда правильный. Я подозреваю, что моя проблема находится в цикле for в методе блокировки, который вызывает проверенную блокировку Петерсона (блокировка Петерсона не имеет ошибок в том, что она была предоставлена ​​для решения этой проблемы). Я в основном строю сбалансированное двоичное дерево, объявляю массив экземпляров алгоритма Петерсона, и, когда каждый поток приходит, я использую дерево как индекс и вызываю блокировки Петерсона.

package mutex; 

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 implements Lock{ 

int total_instances; 
int thread_instances = 0; 
int N; 
static int cnt = 0; 
static int cnt2 = 0; 
int flag = 0; 
Node root; 
Peterson[] PeterInstances; 
int[] IncomingThreadIDs; 

final private ThreadLocal<Integer> THREAD_ID2 = new ThreadLocal<Integer>(){ 
    final private AtomicInteger id2 = new AtomicInteger(0); 

    protected Integer initialValue(){ 
     return id2.getAndIncrement(); 
    } 
}; 


//Constructor : tree_lock Constructor 
//Input   : n, the number of threads 
//Descritpion : Determine number of instances fore each thread, Create IDs for each thread, 
//    Create Balanced Binary Tree of with keys numbered from 0 to n 
tree_lock(int n) 
{ 
    N=n; 
    int temp = n; 
    total_instances = n - 1; 
    int[] IDs = new int[total_instances]; 

    //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) 
    { 
     IncomingThreadIDs[i] = cnt; 
     IncomingThreadIDs[i+1] = cnt; 

     cnt+=2; 
    } 
    //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: http://linwdav.blogspot.com/2011/06/how-to-build-balanced-binary-search.html 
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() 
{ 
    //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++) 
    { 
      //******************************** 
      //Problem is here!!!!!!!!!!!!!!! 
     PeterInstances[path[i]].lock(); 
      //ThreadID = findNodeParent(ThreadID); 
    } 

} 
//Function : unlock 
//Description : unlocks other threads 
public void unlock() 
{ 
    //get thread ID 
    int cnt3 = (THREAD_ID2.get() % N); 

    //create path to root node 
    int[] path = new int[thread_instances]; 
    path[0] = IncomingThreadIDs[cnt3]; 

    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(); 
} 

} 

class Node 
{ 
int key; 

Node leftChild; 
Node rightChild; 
Node parent; 

Node(int key) 
{ 
    this.key = key; 

} 
} 

Answer 1

Вы указали на проблему точно. Вы должны сделать этот код синхронизированным. Я думаю, что вызов суперкласса(), который вы вызываете, не синхронизирован.

Только это решит проблему.

synchronized (this){ 
      PeterInstances[path[i]].lock(); 
     } 

Надеюсь, это поможет.