배열의 동시성 문제 (Java)

Question

알고리즘에서 나는 특정 방법으로 배열을 블랙리스트에 올릴 수있는 블랙리스트 작성 메커니즘을 개발하려고했습니다. "1, 2, 3"이 "1, 2, 3" , 4, 5 "도 차단 목록에 포함됩니다.
나는 지금까지 생각해 낸 해결책에 대해 매우 만족합니다. 하지만 여러 스레드에서 블랙리스트에 액세스 할 때 심각한 문제가있는 것 같습니다. 배열에 블랙리스트가 없더라도 "contains"(아래 코드 참조) 메서드는 때때로 true를 반환합니다. 하나의 스레드 만 사용하는 경우이 문제는 발생하지 않으므로 동시성 문제가 발생할 가능성이 큽니다.
일부 동기화를 추가하려고했지만 아무 것도 변경하지 않았습니다. 나는 또한 java.util.concurrent 클래스를 사용하여 약간 다른 구현을 시도했다. 이 문제를 해결하는 방법에 대한 아이디어가 있습니까?

public class Blacklist { 

private static final int ARRAY_GROWTH = 10; 

private final Node root = new Node(); 

private static class Node{ 

    private volatile Node[] childNodes = new Node[ARRAY_GROWTH]; 

    private volatile boolean blacklisted = false; 

    public void blacklist(){ 
     this.blacklisted = true; 
     this.childNodes = null; 
    } 
} 

public void add(final int[] array){ 

    synchronized (root) { 

     Node currentNode = this.root; 

     for(final int edge : array){ 
      if(currentNode.blacklisted) 
       return; 

      else if(currentNode.childNodes.length <= edge) { 
       currentNode.childNodes = Arrays.copyOf(currentNode.childNodes, edge + ARRAY_GROWTH); 
      } 

      if(currentNode.childNodes[edge] == null) { 
       currentNode.childNodes[edge] = new Node(); 
      } 

      currentNode = currentNode.childNodes[edge]; 
     } 

     currentNode.blacklist(); 
    } 


} 

public boolean contains(final int[] array){ 

    synchronized (root) { 

     Node currentNode = this.root; 

     for(final int edge : array){ 
      if(currentNode.blacklisted) 
       return true; 

      else if(currentNode.childNodes.length <= edge || currentNode.childNodes[edge] == null) 
       return false; 

      currentNode = currentNode.childNodes[edge]; 
     } 

     return currentNode.blacklisted; 

    } 

} 

}

Answer 1

편집 : 내가 10 개 스레드 추가 및 패턴의 수천을 비교와 테스트 스위트를 통해 코드를 실행,하지만 구현 아무 문제를 찾을 수 있습니다. 나는 당신이 당신의 데이터를 잘못 해석하고 있다고 생각합니다.

// sometimes this can be false 
blacklist.contains(pattern) == blacklist.contains(pattern);

또 다른 스레드가 첫 번째 호출 후 사이의 블랙리스트를 변경,하지만 두 번째 호출하기 전에 : 예를 들어, 스레드 환경에서이 때때로 false를 반환합니다. 이것은 정상적인 동작이며 클래스 자체는 그것을 멈추게 할 수 없습니다. 이 원하는 행동하지 않으면, 당신은 클래스의 외부에서 동기화 할 수 있습니다 :

synchronized (blacklist) { 
    // this will always be true 
    blacklist.contains(pattern) == blacklist.contains(pattern); 
}

원래 응답 :
당신은 루트 노드를 동기화하지만,이 자식 중 하나를 동기화하지 않습니다 . 클래스를 방탄으로 만들기 위해 수행해야하는 것은 add(int[]) 및 contains(int[]) 메서드를 동기화 한 다음 참조를 누설하지 말아야한다는 것입니다. 이렇게하면 한 번에 하나의 스레드 만 Blacklist 개체를 사용할 수 있습니다. 그것의 의미를하는 동안

나는 당신의 코드와 바이올린을, 그래서 당신은뿐만 아니라 그것을 가지고 있습니다

import java.util.HashMap; 
import java.util.Map; 
import java.util.Stack; 

public class Blacklist { 
    private final Node root = new Node(Integer.MIN_VALUE, false); 

    public synchronized void add(int[] array) { 
     if (array == null) return; 
     Node next, cur = root; 

     for(int i = 0; i < array.length-1 && !cur.isLeaf(); i++) { 
      next = cur.getChild(array[i]); 

      if (next == null) { 
       next = new Node(array[i], false); 
       cur.addChild(next); 
      } 

      cur = next; 
     } 

     if (!cur.isLeaf()) { 
      next = cur.getChild(array[array.length-1]); 
      if (next == null || !next.isLeaf()) 
       cur.addChild(new Node(array[array.length-1], true)); 
     } 
    } 

    public synchronized boolean contains(int[] array) { 
     if (array == null) return false; 
     Node cur = root; 

     for (int i = 0; i < array.length; i++) { 
      cur = cur.getChild(array[i]); 
      if (cur == null) return false; 
      if (cur.isLeaf()) return true; 
     } 

     return false; 
    } 

    private static class Node { 
     private final Map<Integer, Node> children; 
     private final int value; 

     public Node(int _value, boolean leaf) { 
      children = (leaf?null:new HashMap<Integer, Node>()); 
      value = _value; 
     } 

     public void addChild(Node child) { children.put(child.value, child); } 
     public Node getChild(int value) { return children.get(value); } 
     public boolean isLeaf() { return (children == null); } 

    } 
} 

Collections framework 당신을 위해 더 쉽게 일을 할 수 있습니다. 당신은 ArrayList를 다시 구현하여 어떤 호의도하지 않습니다.

blacklist.add(new int[] {1, 2000, 3000, 4000});