java - 예제 - 피터슨의 해결안




자바 피터슨 알고리즘? (4)

Java에서 상호 배제를위한 Peterson 알고리즘의 구현 예가 있습니까?


Peterson의 알고리즘 (Java와 같은 고급 언어로 작업 할 때 이상하게 느껴질 수 있음)에 대한 특정 요구가없는 한, 언어에 내장 된 동기화 기능을 살펴 보는 것이 좋습니다.

예를 들어, Java에서 "Race Conditions and Mutual Exclusion"에 대한이 책의 장을 참조하십시오. http://java.sun.com/developer/Books/performance2/chap3.pdf

특히 :

Java는 조건의 개념을 통해이 "상태 변경"을 기다리는 내장 지원을 제공합니다. 그러나 조건이 실제로 발생했는지 여부는 전적으로 사용자에게 달려 있기 때문에 조건은 다소 잘못된 이름입니다. 또한 조건은 구체적으로 true 또는 false 일 필요는 없습니다. 조건을 사용하려면 Object 클래스의 세 가지 주요 메서드에 익숙해야합니다.

• wait () :이 메서드는 조건을 기다리는 데 사용됩니다. 이것은 특정 (공유) 객체에 대해 현재 잠금이 유지되고있을 때 호출됩니다.

• notify () :이 메소드는 조건이 변경되었을 가능성이있는 단일 스레드에 알리는 데 사용됩니다. 이 메소드는, 현재, 특정의 오브젝트에 대해서 락이 보관 유지되고있는 경우에 불려갑니다. 이 호출로 인해 하나의 스레드 만 깨울 수 있습니다.

• notifyAll () :이 메소드는 여러 스레드에 조건이 변경되었을 가능성이 있음을 알리는 데 사용됩니다. 이 메서드를 호출 할 때 실행중인 모든 스레드에 알림이 전송됩니다.


paterson algo는 아니지만 AtomicBoolean 및 Atomic * 클래스는 공유 데이터를 업데이트하기 위해 잠금없는 바쁜 루프 방식을 사용합니다. 그들은 귀하의 요구 사항에 적합 할 수 있습니다.


웹에서 직접 찾을 수 없으므로 작성하려고했습니다.


public class Peterson implements Runnable {

    private static boolean[] in = { false, false };
    private static volatile int turn = -1;

    public static void main(String[] args) {
        new Thread(new Peterson(0), "Thread - 0").start();
        new Thread(new Peterson(1), "Thread - 1").start();
    }

    private final int id;

    public Peterson(int i) {
        id = i;
    }

    private int other() {
        return id == 0 ? 1 : 0;
    }

    @Override
    public void run() {
        in[id] = true;
        turn = other();
        while (in[other()] && turn == other()) {
            System.out.println("[" + id + "] - Waiting...");
        }
        System.out.println("[" + id + "] - Working ("
                + ((!in[other()]) ? "other done" : "my turn") + ")");
        in[id] = false;
    }
}

코멘트 주시기 바랍니다, 그것은 감사하겠습니다 :)


여기에 아무도 Java에서이 알고리즘의 정확하고 안전한 구현을 제공하지 않았습니다. John W의 해결책은 ThreadLocals의 선언과 그의 배열에 있어야하는 것에 대한 설명이 없기 때문에 어떻게 작동해야하는지 모르겠습니다. 원시 booleansget()set() get() 하지 않습니다. set() ).

Java 언어 스펙의 17 장은 Java 메모리 모델을 설명합니다. 특히 17.4.5 절 에서 발생하기 전에 발생하는 순서에 대해 설명합니다. 단일 스레드 내에서 생각하는 것은 꽤 쉽습니다. 스 니펫을 고려해보십시오.

int x, y, z, w;
x = 0;
y = 5;

z = x;
w = y;

모두이 스 니펫의 끝에서 xz 가 모두 0 이고 yw 가 모두 5 라는 점에 동의합니다. 선언을 무시하고 여기에 여섯 가지 조치가 있습니다.

  1. x 쓰기
  2. y 쓰기
  3. x 에서 읽음
  4. z 쓰기
  5. y 로부터의 읽기
  6. 쓰기 쓰기

그것들은 모두 같은 thread에 나타나기 (위해) 때문에, JLS에서는, 이러한 read 및 write에 의해,이 순서가 보증되고 있다고합니다. 위의 각 액션 n (액션은 단일 thread에 있기 때문에)에는, 모든 액션 m , m > n .

하지만 다른 스레드는 어떨까요? 일반적인 필드 접근의 경우, 쓰레드 사이에 확정 된 관계가 설정되지 않습니다. 즉, 스레드 A가 공유 변수를 증가시킬 수 있고 스레드 B가 해당 변수를 읽을 수는 있지만 새 값은 볼 수 없음을 의미합니다 . JVM에서의 프로그램 실행에서 스레드 A의 쓰기 전파는 스레드 B의 읽기 이후에 재주문 될 수 있습니다.

사실, 쓰레드 A는 변수 x 와 변수 y 쓸 수 있습니다. 쓰레드 A 내의 두 동작 사이에 발생 - 관계를 설정합니다. 그러나 쓰레드 B는 xy 읽을 수 있습니다. x 의 새로운 값이 나오기 전에 y 의 새로운 값이 나타납니다. 사양 :

보다 구체적으로 말하면, 두 개의 액션이 일찍 발생하는 관계를 공유하는 경우, 반드시 발생하기 전에 관계를 공유하지 않는 코드에 대해 그 순서대로 발생하지 않아도되는 것은 아닙니다.

어떻게 해결할 수 있을까요? 일반적인 필드 액세스의 경우 volatile 키워드로 충분합니다.

휘발성 변수 (§8.3.1.4)에 대한 쓰기 v는 임의의 스레드에 의한 v의 모든 후속 읽기와 동기화됩니다 (후속은 동기화 순서에 따라 정의됩니다).

synchronizes-with 는 happen-before보다 강한 조건이며, happen-before는 전 이적이므로 스레드 A가 스레드 B가 xy 대한 쓰기를보기를 원하면 xy 를 작성한 후 휘발성 변수 z 에 쓰기 만하면됩니다 . 스레드 B는 xy 를 읽기 전에 z 에서 읽어야하며 xy 의 새 값을 볼 수 있습니다.

Gabriel의 솔루션에서 우리는이 패턴을 보았습니다. 쓰기는 in 발생하고 다른 스레드에서는 볼 수 없지만 쓰기는 turn 하여 발생하므로 다른 스레드는 turn 먼저 읽는 한 두 가지 쓰기를 모두 볼 수 있습니다.

불행히도, while 루프의 조건부는 뒤쪽이다 : 스레드가 in 에 대한 부실 데이터를 보지 못하도록하려면 while 루프는 처음부터 읽어야한다.

    // ...
    while (turn == other() && in[other()]) {
        // ...

이 수정 사항을 염두에두고, 나머지 솔루션 대부분은 괜찮습니다. 중요한 섹션에서 우리는 중요한 섹션에 있기 때문에 데이터의 staleness에 신경 쓰지 않습니다! 끝 부분에 다른 단점이 있습니다 : Runnable은 in[id] 를 새로운 값으로 설정하고 종료합니다. 다른 스레드가 in[id] 의 새로운 값을 보게 될 것입니까? 사양은 아니오라고 말합니다 :

스레드 T1의 최종 동작은 T1이 종료되었음을 감지하는 다른 스레드 T2의 모든 동작과 동기화됩니다. T2는 T1.isAlive () 또는 T1.join ()을 호출하여이를 수행 할 수 있습니다.

어떻게 해결할 수 있을까요? 메서드의 끝 부분에서 다른 쓰기를 추가하면됩니다.

    // ...
    in[id] = false;
    turn = other();
}
// ...

while 루프에 재정렬 한 이후, 다른 스레드는 in[id] 대한 쓰기가 발생하기 때문에 - 쓰기가 일어나기 전에 - turn 으로부터의 읽기가 일어나기 전에 -에있는 새로운 false 값을 볼 수 있습니다. in[id] 읽습니다.

말할 것도없이 메트 릭 톤 의 주석이 없어도이 방법은 취성이 있고 누군가가 따라 와서 뭔가를 바꿀 수 있고 정확함을 미묘하게 깨뜨릴 수 있습니다. volatile 배열을 선언하는 것만으로는 충분하지 않습니다. Java Pseudo Java 메모리 모델의 수석 연구원 인 Bill Pugh가 설명한 이 스레드 에서 배열을 volatile 선언하면 배열 참조 를 다른 스레드에서 볼 수있게됩니다. 배열 요소에 대한 업데이트가 반드시 표시 될 필요는 없습니다 (따라서 배열 요소에 대한 액세스를 보호하기 위해 다른 volatile 변수를 사용하여 점프해야하는 모든 루프).

코드를 명확하고 간결하게하려면 AtomicIntegerArray 변경하십시오 (false의 경우 0, true의 경우 1, AtomicBooleanArray는 없음). 이 클래스는 요소가 volatile 이있는 배열처럼 동작하므로 모든 문제를 멋지게 해결할 수 있습니다. 또는 두 개의 휘발성 변수 인 boolean in0boolean in1 선언하고 부울 배열을 사용하는 대신이를 업데이트 할 수 있습니다.





memory-model