4

我是并发编程的新手，所以很好。我有一个基本的顺序程序（用于家庭作业），我正试图将它变成一个多线程程序。我不确定我的第二个共享变量是否需要锁。线程应该修改我的变量，但从不读取它们。应该读取的唯一时间计数是在产生我所有线程的循环完成分发密钥之后。

#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;
      }
    }
}
4

3 回答 3

6

As you suspect, count++; requires synchronization. This is actually not something you should try to "get away with" not doing. Sooner or later a second thread will read count after the first thread reads it but before it increments it. Then you will miss a count. It is impossible to predict how often it will happen. It could happen once in a blue moon or thousands of times a second.

于 2012-10-27T02:20:09.437 回答
5

实际上，您编写的代码会读取和修改变量。如果您要查看为以下行生成的机器代码

count++

你会看到它由类似的东西组成

fetch count into register
increment register
store count

所以是的，你应该在那里使用互斥锁。（即使你不这样做就可以逃脱，为什么不抓住机会练习呢？）

于 2012-10-27T02:03:01.253 回答
4

如果您只是想要count跨多个线程的精确增量，那么这些类型的单值更新正是互锁内存屏障函数的用途。

为此，如果您使用 gcc，我将使用： __sync_add_and_fetch 。您可以执行许多不同的联锁操作，其中大多数是特定于平台的，因此请检查您的文档。然而，对于像这样更新计数器，它们可以省去一大堆麻烦。其他示例包括Windows 下的InterlockedIncrement 、OS X 上的OSAtomicIncrement32等。

于 2012-10-27T02:15:30.410 回答