Set과 Queue이 있다고합시다. set을 확인하려면 contains(Element)이고 그렇지 않은 경우 add(element)은 queue입니다. 저는 두 단계를 원자 적으로하고 싶습니다.Java에서 한 쌍의 작업을 원자 적으로 실행하기위한 비 차단 전략
하나의 분명한 방법은 synchronized 블록 또는 Lock.lock()/unlock() 방법을 사용하는 것입니다. 스레드 경합 (thread contention) 하에서, 이들은 콘텍스트 스위치를 야기 할 것이다. 이것을 비 차단 방식으로 달성하기위한 간단한 설계 전략이 있습니까? 일부 원자 구조를 사용하고있을 수 있습니까?
두 구조에서 작동하기 때문에 자신이 지적한 것을 제외하고는 어떤 메커니즘에도 의존 할 수 있다고 생각하지 않습니다.
하나의 데이터 구조 (ConcurrentHashMap에 "put if not exist"와 같은)에 대한 적절한 지원이 있지만 일련의 작업에 대해서는 잠금 또는 동기화 된 블록으로 고정되어 있습니다 .
경합 사례이 해당 케이스이므로 "스핀 잠금 장치"를 확인해야합니다. 그들은 CPU를 버리지는 않지만 플래그가 곧 비게 될 것이라고 기대하는 플래그로 회전합니다.
그러나 실제 스핀 록은 보통 Lock이 상당히 좋기 때문에 Java에서는 유용하지 않습니다. 누군가가 수정을 한 후에 (즉, 올바른 테스트를 한 후에) 스핀 락이 표준 작업과 동등한 것을 발견하기 위해서만 Java에서 스핀 록을 구현 한 사람이있는 this blog을 참조하십시오.
일반적으로 스핀 잠금 장치는 악합니다. 그리고 대부분의 잠금 전략은 작업 전환을 강제하기 전에 아주 짧은 간격으로 (특별한 경우) 스핀 잠금을 사용하므로 두 세계의 장점을 최대한 활용하는 경향이 있습니다. –
@HotLicks : 나는 스핀 자물쇠가 빵과 버터 재료가 아니라, 날카로운 모서리를 가지고 있다고 동의한다. 그럼에도 불구하고 유용하고 적절한 경우가 있습니다. _IF_ 이것은 다음과 같은 경우 중 하나입니다. TO가 알려줍니다. –
경합이 매우 낮을 것으로 예상되면 실제 스핀의 양이 적을 것으로 예상되면 스핀 잠금이 좋습니다. 나는 "표준"자물쇠를 스핀 락으로 대체하여 선형 속도 향상에 준 선형 속도 향상을 보이는 알고리즘을 구현할 수있었습니다. 제 경우에는 n이 무한대로 갈수록 경쟁은 0으로 떨어질 것으로 예상되었습니다. 하지만 일반적으로 스핀 잠금을 최적화로 사용합니다. 조기 스핀 락은 [모든 악의 근원] (http://en.wikiquote.org/wiki/Donald_Knuth)의 한 요소입니다. –
일부 작업의 경우 동시 작업이 충돌없이 겹칠 수있는 "안전 시퀀스"를 사용할 수 있습니다. 예를 들어 동일한 멤버를 동시에 추가하는 두 개의 스레드가 서로 개념적으로 충돌하지 않기 때문에 동기화 할 필요없이 (이론적으로) 집합에 멤버를 추가 할 수 있습니다.
그러나 하나의 개체를 쿼리 한 다음 다른 개체에서 조건부로 작동하려면 훨씬 더 복잡한 시나리오입니다. 시퀀스가 집합을 쿼리하는 경우 조건부로 집합과 큐에 구성원을 조건부로 삽입하면 쿼리와 첫 번째 삽입이 메모리를 제외하고는 멈추지 않고 동기화되는 "비교 및 스왑"연산으로 대체 될 수 있습니다 액세스 레벨)을 생성 한 다음 첫 번째 작업의 성공에 따라 대기열에 구성원을 삽입 할 수 있으며 대기열 자체를 동기화 할 필요 만 있습니다. 그러나이 시퀀스는 다른 스레드가 삽입에 실패하고 여전히 대기열에서 구성원을 찾을 수없는 시나리오를 벗어납니다.
java.util.concurrent.ConcurrentHashMap을 사용하여 원하는 의미를 얻을 수 있습니다. 원자 삽입을 수행하는 putIfAbsent이 있습니다. 그런 다음 본질적으로 맵에 요소를 추가하려고 시도하고, 성공하면 삽입을 수행 한 스레드가있는 스레드 만 알고 있으므로 안전하게 항목을 큐에 넣을 수 있습니다. 여기에서 중요한 점은 ConcurrentMap에 대한 조작이 "발생 전"의시`틱을 보장한다는 것입니다.
ConcurrentMap<Element,Boolean> set = new ConcurrentHashMap<Element,Boolean>();
Queue<Element> queue = ...;
void maybeAddToQueue(Element e) {
if (set.putIfAbsent(e, true) == null) {
queue.offer(e);
}
}
지도의 실제 값 유형 (부울)은 중요하지 않습니다.
하지만 원자 적으로 작업을 수행하지는 않습니다. 두 번째 스레드가 집합에서 "이미 있음"응답을 가져올 수 있지만 대기열에서 요소를 찾을 수는 없습니다. –
하나의 요소가 관계없이 대기열에 들어갑니다. –
예, 두 번째 스레드가 요소가 대기열에 있다고 가정하고 액세스하려고하면 문제가 발생합니다. 그것은 모두 전반적인 프로그램 설계가 무엇이고, 시행하려는 "계약"이 무엇인지에 달려 있습니다. –
짧은 대답 : 아니오. –
'동기화'또는 '잠금'으로 인해 컨텍스트가 변경되어야하는 이유는 무엇입니까? –
이 문맥에서 원 자성이 의미하는 것은 무엇인지 명확하지 않습니다. 원자 적으로하지 않는 것의 결과는 무엇일까요? – axtavt