C++에서 잠금을 사용하지 않고 경쟁 조건을 방지하려면 어떻게합니까?

Question

C++에서 잠금이나 뮤텍스/세마포어를 사용하지 않고 경쟁 조건을 방지하려면 어떻게합니까? 나는 배열에 값을 설정한다있는 루프 중첩을 처리 해요 :

for (int i = 0; i < m; ++i) 
    for (int j = 0; j < n; ++j) 
    for (int k = 0; k < o; ++k) 
     array[k] += foo(...); 

, 내가 동시에 실행중인 다른 스레드를 보장 할 수 있도록이 처리 할 더 많은 이하 동시에 배열 [k]에 쓰지 마십시오. 이것에 접근하는 방법에 대한 제안?

편집 : Linux 컴퓨터에서 실행 중이며 Intel 컴파일러도 사용해야합니다. "gcc"대신 "icc"를 사용하여 코드를 컴파일합니다.

Answer 1

가정 창문과 같은 것을 할 수 LONG 유형의 array에 포함 된 요소 : 당신이 API를 비슷한 옵션이있을 수 있습니다 윈도우 플랫폼에서 작동하지 않는 경우

for (int i = 0; i < m; ++i) 
    for (int j = 0; j < n; ++j) 
     for (int k = 0; k < o; ++k) { 
      LONG val = foo(...); 
      InterlockedAdd(&array[k], val); 
     } 

합니다. 플랫폼에 InterlockedCompareExchange() 유형의 API가있는 경우 자신의 버전 InterlockedAdd()을 작성할 수 있습니다. 다음과 같은

뭔가 (면책 조항 - 검증되지 않은) :

int InterlockedAdd(int volatile* pDest, int operand) 
{ 
     int curval = *pDest; 
     int oldval; 

     do { 
      oldval = curval; 
      curval = InterlockedCompareExchange(pDest, oldval + operand, oldval); 
     } while (curval != oldval); 

     return oldval+operand; 
} 

는 지금까지 내가 아는 한, 부스트는 분명히에만 충분히 참조 카운트의 원자 조작을 지원하기 위해 연동/원자 작업에 대한 제한적인 지원을하고있다. 나는 Boost에서 인터 로크 된 연산에 대한 지원이 구현 세부 사항 이상이라고 생각하지 않는다. (나는 현재 Boost의 다소 오래된 버전을 다루고있다. 그래서 더 이상 그렇지 않을 수도있다.)

원자 비교하고 지원하는 일부 휴대용 도서관이 있습니다 교환 및 인터페이스의 문서화 된 부품과 같은 다른 원자 작업 :

• 아파치 4월 : http://apr.apache.org/docs/apr/1.4/group__apr__atomic.html
• 입심 : http://library.gnome.org/devel/glib/stable/glib-Atomic-Operations.html
• 인텔 스레드 빌딩 블록 : http://www.threadingbuildingblocks.org/

또한 C++ 0x는 compa와 같은 원자 연산 re/exchange - 지원 수준이 현재 C++ 컴파일러인지 확실하지 않습니다 (VS 2010이 아닌 것으로 보입니다).

Answer 2

배열에 정수가 있다고 가정하고 gcc의 atomic builtins을 사용하십시오. __sync_fetch_and_add 트릭을해야합니다.

Answer 3

이 특정 루프의 경우 뒤집습니다. k을 바깥쪽에 넣으면 과 다른 스레드에 k=0을 배치 할 수 있습니다.

foo()은 k [= k]의 배열 [k]에 의존하지 않는 한 황금으로 나타납니다.

Answer 4

스레드 중 가장 안쪽의 루프를 분할합니다. 스레드 T1은 [0, L] 범위의 인덱스를 처리하고 스레드 T2는 [L, 2L] 범위의 인덱스를 처리합니다. L = o/n 여기서 n은 스레드의 수입니다. 이것은 foo() 호출이 동시에 계산 될 수있는 다른 위치를 사용하지 않는다고 가정합니다.

EDIT : 다른 사람들이 제안한 것처럼 연동 연산을 사용하면 올바른 결과를 얻을 수 있지만 성능이 크게 떨어질 수 있습니다. (내부 루프가 짧으면 많은 스레드가 메모리 위치를 거의 차지하지 않으므로 프로그램을 효과적으로 직렬화합니다.)

Answer 5

가장 효율적인 방법은 아니지만 가장 중요한 방법은 루프를 "중요한" 섹션.

여기를 참조하십시오. Wikipedia 이것은 주어진 시간에 루프 코드를 단일 스레드로 제한합니다.

Answer 6

원하는대로 할 수 없습니다! (sbi의 설명 참조)

공유 메모리를 사용할 수 있지만 여전히 잠금이 있습니다.
배열에 쓰기 및 읽기 작업을 위해 하나의 스레드 만 사용할 수도 있습니다. 올바른 프로토콜을 설정하는 것이 더 쉬운 것으로 생각되면 계속하십시오.

어쨌든 이미 자물쇠를 사용하여 (직접 또는 간접적으로) 좋은 해결책이 있습니다. 그냥 정확한 결과를 제공합니다 다른 사람이 제안으로, 연동 작업을 사용 :

Answer 7

를 하나를 선택하지만 심하게 성능이 저하 될 수 있습니다. (내부 루프 이 짧은 경우, 많은 스레드 효과적으로 프로그램을 직렬화 할 몇 가지 메모리 위치, 경쟁 될 것입니다.) 링크 | 플래그

사실 아니, 내 친구. 실제로 연동 작업은 모든 종류의 잠금보다 우수합니다. 보다 정확하게는 모든 동기화 개체 (중요한 섹션, 뮤텍스, 이벤트 등)가 연동 작업의 측면에서 명확하게 구현됩니다. 사실 동기화 연동을 보장 할 수있는 유일한 프로세서 명령어는 연동 연산입니다. 단지 불가능합니다. 연동 작업을 전혀 사용하지 않고 동기화 객체를 구현하는 것입니다..

다른 질문은 범위 잠금입니다. 내부 루프 내부의 동기화 범위 (동기화 객체 또는 직접 연동 연산으로 구현 됨)가 여러 번 실행 되었기 때문에 성능 저하를 초래할 수 있다고 말하고 싶을 것입니다.

음, 사실입니다. 그러나 다른 한편으로는 필요한 기간 동안 만 필요한 것을 잠급니다. 따라서 잠재적 인 동기화 충돌을 방지 할 수 있습니다.