뮤텍스가 필요한지 확실하지 않은 경우

Question

저는 동시 프로그래밍이 처음이므로 잘해야합니다. 나는 숙제를위한 기본 순차 프로그램을 가지고 있으며 그것을 다중 스레드 프로그램으로 바꾸려고 시도하고있다. 두 번째 공유 변수에 대한 잠금이 필요한지 확실하지 않습니다. 스레드는 내 변수를 수정해야하지만 결코 읽지 않습니다. 유일한 시간 카운트는 모든 스레드를 생성하는 루프가 키 분배를 마친 후에 읽어야합니다.

#define ARRAYSIZE 50000 

#include <pthread.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <sys/time.h> 

void binary_search(int *array, int key, int min, int max); 

int count = 0; // count of intersections 
int l_array[ARRAYSIZE * 2]; //array to check for intersection 

int main(void) 
{ 
    int r_array[ARRAYSIZE]; //array of keys 
    int ix = 0; 

    struct timeval start, stop; 
    double elapsed; 

    for(ix = 0; ix < ARRAYSIZE; ix++) 
    { 
     r_array[ix] = ix; 
    } 
    for(ix = 0; ix < ARRAYSIZE * 2; ix++) 
    { 
     l_array[ix] = ix + 500; 
    } 

    gettimeofday(&start, NULL); 

    for(ix = 0; ix < ARRAYSIZE; ix++) 
    { 
     //this is where I will spawn off separate threads 
     binary_search(l_array, r_array[ix], 0, ARRAYSIZE * 2); 
    } 

    //wait for all threads to finish computation, then proceed. 

    fprintf(stderr, "%d\n", count); 

    gettimeofday(&stop, NULL); 
    elapsed = ((stop.tv_sec - start.tv_sec) * 1000000+(stop.tv_usec-start.tv_usec))/1000000.0; 
    printf("time taken is %f seconds\n", elapsed); 
    return 0; 
} 

void binary_search(int *array, int key, int min, int max) 
{ 
    int mid = 0; 
    if (max < min) return; 
    else 
    { 
     mid = (min + max)/2; 
     if (array[mid] > key) return binary_search(array, key, min, mid - 1); 
     else if (array[mid] < key) return binary_search(array, key, mid + 1, max); 
     else 
     { 
      //this is where I'm not sure if I need a lock or not 
      count++; 
      return; 
     } 
    } 
} 

Answer 1

실제로 코드는 변수를 읽고 수정합니다. 당신은

count++ 

같은 라인에 대해 생성됩니다 당신이 그래서 그래, 당신이 뮤텍스를 사용한다

fetch count into register 
increment register 
store count 

같은 것을 구성되어 있음을 볼 수있을 기계 코드를 본다면. (심지어 그렇게하지 않고 도망 칠 수있는 경우에도 연습 할 기회를 얻지 않겠습니까?)

Answer 2

count을 여러 스레드에서 정확하게 증가 시키려면 이러한 유형의 단일 값 업데이트가 인터록 된 메모리 - 장벽 기능은 다음과 같습니다.

gcc를 사용하는 경우 __sync_add_and_fetch을 사용합니다. 당신이 할 수있는 서로 다른 인터 로크 연산들의 호스트가 있으며, 대부분은 플랫폼에 따라 다르므로 문서를 확인하십시오. 그러나 이와 같은 카운터를 업데이트하면 번거 로움을 덜 수 있습니다. 다른 샘플로는 Windows에서 InterlockedIncrement, OS X에서 OSAtomicIncrement32 등이 있습니다.

Answer 3

의심되는가요? count++;은 동기화가 필요합니다. 이것은 실제로 당신이하지 않고 "도망 가려고"해야하는 것이 아닙니다. 조만간 두 번째 쓰레드는 첫번째 쓰레드가 읽은 후에 count를 읽습니다. 그렇다면 카운트를 놓치게됩니다. 얼마나 자주 일어날 지 예측할 수는 없습니다. 그것은 푸른 달 또는 한 번 수천 번에 한 번 발생할 수 있습니다.