Реализация алгоритма взаимного исключения Дейкстры - PullRequest
Новая
       30

Реализация алгоритма взаимного исключения Дейкстры

0 голосов
/ 20 октября 2018

Я пытаюсь реализовать алгоритм Дейкстры в пуле потоков форка / соединения (состоит из основного пула потоков с глобальной очередью задач и N потоков с собственной очередью задач) на основе решения Дейкстры проблемы в управлении параллельным программированием, а также Фриго иЛейзерсона и Рэндалла Реализация многопоточного языка cilk-5.

Но это кажется слишком сложным.Итак, я использовал Filter Lock из Art of Multiprocessor Programming следующим образом:

Реализация книги 

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.Я не уверен, что я использую алгоритм в неправильном месте или мой алгоритм в данный момент неверен.Кроме того, мне интересно, как эффективно украсть задачи для работы из очередей других работников (найти работника с доступными задачами)

...