0

我正在测试一个 pthread 程序。

这个程序很简单。主线程创建一个子线程。

主线程和子线程都在队列上运行。

子线程不断扫描队列并无限循环返回最小元素及其位置。

主线程也在运行一个循环，每次迭代从队列中删除子线程计算的最小元素，并在队列末尾插入一些新元素。

最小元素及其位置和队列都被声明为全局变量。

当队列为空时主线程结束，它将取消子线程。

这种进展有点像广度优先搜索。

队列实现为带有大小计数器的数组。删除操作被实现为将要删除的元素替换为最后一个元素并将大小计数器减一。

这里没有使用锁。但是运行时，程序会卡住。

更神奇的是，如果我插入一些 printf 语句来查看状态，它可能会完成。

我想知道是什么原因导致这个程序没完没了？

struct multiblocks_pthread_args {
    volatile int local_e;
    volatile int local_v;
    volatile int local_pos;
    int* Q;
    int* val;
    volatile int* size;
} para;

volatile int update = 0;
void* child_thread ( void* args ) {
    pthread_setcanceltype ( PTHREAD_CANCEL_ASYNCHRONOUS, NULL );
    multiblocks_pthread_args* arglist = ( multiblocks_pthread_args* ) args;
    bindToCore ( 1 );
    int* list = arglist -> Q, * value = arglist -> val;
    while ( true ) {
        int size, e, v, pos;
        do {
            size = * ( arglist->size ), e, v = INF, pos = 0;
            update = 0;
            for ( int i = 0; i < size; i++ ) {
                int vi = value[i];
                if ( vi < v ) {
                    pos = i;
                    v = vi;
                }
            }
        } while ( update );
        if ( size > 0 ) e = list[pos];
        arglist->local_e = e;
        arglist->local_pos = pos;
        arglist->local_v = v;
    }
    return NULL;
}

void main_thread () {
    int size;
    int* Q = ( int* ) malloc ( sizeof ( int ) * NumNode );
    int** hash = ( int** ) malloc ( sizeof ( int* ) * numNode );
    NodeColor* color = ( NodeColor* ) malloc ( sizeof ( NodeColor ) * numNode ); 
    // NodeColor is a enum with 3 values: WHITE, GRAY, BLACK

    memset ( color, 0, sizeof ( NodeColor ) * numNode );

    pthread_t tid;
    para.val = ( int* ) malloc ( sizeof ( int ) * NumNode );
    para.Q = Q;
    para.size = &size;
    pthread_create ( &tid, NULL, child_thread, &para );

    // Only one element is in the queue
    size = 0;
    para.Q[size] = 0;
    para.val[size] = 0;
    hash[0] = &para.val[size]; // hash is used to modify the value of particular element
    ++size;
    color[0] = GRAY;
    while ( true ) {
        int global_e, global_v = INF, global_pos;
        global_e = para.local_e, global_v = para.local_v, global_pos = para.local_pos;
        if ( size == 0 ) break;
        if ( color[global_e] != BLACK ) {
            value[global_e] = global_v, color[global_e] = BLACK;
            if ( size > 0 ) {
                --size;
                para.Q[global_pos] = para.Q[size];
                para.val[global_pos] = para.val[size];
                hash[para.Q[global_pos]] = & para.val[global_pos];
                update = 1;
            }
            for ( int i = 0; i < MAXDEG; ++i ) {
                int ee = ;// new element;
                int vv = ;// value of new element;
                if ( /* if new element is valid */ ) {
                    if ( color[ee] == WHITE ) { // WHITE means ee is not in the queue
                        para.Q[size] = ee;
                        para.val[size] = vv;
                        hash[ee] = &para.val[size];
                        ++size, color[ee] = GRAY;
                    } else {
                        *hash[ee] = vv;
                    }
                    update = 1;
                }
            }
        }
    }
    free ( Q );
    pthread_cancel ( tid );
    printf ( "Computation finishes!!!" );
    return ;
}
4

1 回答 1

1

这不是僵局，而是竞争条件。

你挂起的整体结构是，你从WHITE索引 0 处的项目开始，这个循环永远持续下去：

size = 1;
while (size != 0) {
  if (WHITE) --size;
  for (...) {
    if (WHITE) ++size;
  }
}

这种变化的唯一方法是您的子线程将设置pos其他内容而不是0. 但是您的子线程取决于大小大于 1 以使其不是 0。您有您的竞争条件。

我的诊断可能不准确。更简洁的代码会有很大帮助。Q像, e,这样的名字v可以节省你几次击键，但很容易让你失去几天，就像在这个例子中一样。您还可以互换使用数字和枚举，这是一种不好的做法。

于 2013-11-11T09:33:07.323 回答