1

我正在尝试基于 Dijkstra 的并发编程控制问题的解决方案以及 Frigo 和 Leiserson 以及 Randall 的 fork/join 线程池（由具有全局任务队列的主线程池和具有自己的任务队列的 N 个线程组成）实现 Dijkstra 算法cilk-5 多线程语言的实现。

但是，这似乎太复杂了。因此，我使用了 Art of Multiprocessor Programming 中的 Filter Lock，如下所示：

本书的实现

class Filter implements Lock {
    int[] level;
    int[] victim;
    public Filter(int n) {
        level = new int[n];
        victim = new int[n]; // use 1..n-1
        for (int i = 0; i < n; i++) {
            level[i] = 0;
            }
    }
    public void lock() {
        int me = ThreadID.get();
        for (int i = 1; i < n; i++) { //attempt level 1
        level[me] = i;
        victim[i] = me;
        // spin while conflicts exist
        while ((∃k != me) (level[k] >= i && victim[i] == me)) {};
        }
    }
    public void unlock() {
        int me = ThreadID.get();
        level[me] = 0;
    }
}

我在线程池中的实现

static int* flag;
static int* victim;
const int MAX = 1e9; 
int ans = 0; 
int nthreads = 10;

struct pt
{
    int id;
    pthread_t thread;
};

static bool existK(int j, int i, int nthreads){
    for (int k = 0; k < nthreads ; k++){
        if (flag[k] >= j && k != i)
        {
            return true;
        }
    }
    return false;
}

void lock_init(void) 
{ 
    flag = (int *) calloc(nthreads, sizeof(int));
    victim = (int *) calloc(nthreads, sizeof(int));
} 

// Executed before entering critical section 
void lock(int i) 
{ 
    for (int j = 1; j < nthreads; j++){
        flag[i] = j;
        victim[j] = i;
        while (existK(j, i, nthreads) && victim[j] == i);
    }
} 

// Executed after leaving critical section 
void unlock(int i) 
{ 
    flag[i] = 0; 
} 

// in main() 
void* func(void *pw) 
{ 
    while (true) {
    lock(threadID); 
    // working on its own queue if there is a task and 
    // after it finishes this task, call unlock(threadID) and call continue; 
    //if the global queue has tasks left, work on it and call unlock and continue
    //if the other worker queue has tasks left, work on it and call unlock and continue
    }
} 

// Driver code 
int main() 
{ 

    struct pt** ptr; 
    lock_init();  
    ptr = ((struct pt **)malloc(sizeof(struct pt *) * nthreads));
    for (int i = 0; i < nthreads; i++){
        ptr[i] = malloc(sizeof(struct pt));
        (ptr[i])->id = i;
        pthread_create(&(ptr[i])->thread, NULL, func, ptr[i]); 
    }
    for (int i = 0; i < nthreads; i++){
       pthread_join((ptr[i])->thread, NULL);
    } 


return 0; 
}

但是，在我的实现中，主循环比仅使用 pthread_mutex_lock 和 pthread_mutex_unlock 慢得多。我不确定我是否在错误的地方使用了算法，或者我的算法在这一点上是错误的。另外，我想知道如何以有效的方式从其他工作人员的队列中窃取要处理的任务（找到具有可用任务的工作人员）

4

0 回答 0