Синхронизация очереди приоритетов с pthreads

Question

Я работаю над заданием в колледже, где мы должны реализовать параллельный поиск A 15 головоломки . Для этой части мы должны использовать только одну очередь с приоритетами (я полагаю, что конкуренция со стороны нескольких потоков будет ограничивать ускорение). Проблема, с которой я сталкиваюсь, заключается в правильной синхронизации выталкивания следующего «кандидата» из очереди приоритетов.

Я попробовал следующее:

while(1) {
  // The board I'm trying to pop.
  Board current_board;

  pthread_mutex_lock(&priority_queue_lock);
  // If the heap is empty, wait till another thread adds new candidates.
  if (pq->heap_size == 0)
  {
    printf("Waiting...\n");
    pthread_mutex_unlock(&priority_queue_lock);
    continue;
  }
  current_board = top(pq);
  pthread_mutex_unlock(&priority_queue_lock);

  // Generate the new boards from the current one and add to the heap...
}

Я пробовал разные варианты одной и той же идеи, но по какой-то причине бывают случаи, когда потоки застревают при «ожидании». Код работает нормально поочередно (или с двумя потоками), поэтому я полагаю, что это оскорбительная часть кода. Я могу опубликовать всю вещь, если это необходимо. Я чувствую, что это проблема с моим пониманием блокировки мьютекса. Заранее спасибо за помощь.

Редактировать: я добавил полный код для параллельной нити ниже:

// h and p are global pointers initialized in main()
void* parallelThread(void* arg)
{
    int thread_id = (int)(long long)(arg);
    while(1)
    {
        Board current_board;

        pthread_mutex_lock(&priority_queue_lock);
        current_board = top(p);
        pthread_mutex_unlock(&priority_queue_lock);

        // Move blank up.
        if (current_board.blank_x > 0)
        {
            int newpos = current_board.blank_x - 1;
            Board new_board = current_board;
            new_board.board[current_board.blank_x][current_board.blank_y] = new_board.board[newpos][current_board.blank_y];
            new_board.board[newpos][current_board.blank_y] = BLANK;
            new_board.blank_x = newpos;

            new_board.goodness = get_goodness(new_board.board);
            new_board.turncount++;

            if (check_solved(new_board))
            {
                printf("Solved in %d turns",new_board.turncount);
                exit(0);
            }

            if (!exists(h,new_board))
            {
                insert(h,new_board);
                push(p,new_board);
            }
        }

        // Move blank down.
        if (current_board.blank_x < 3)
        {
            int newpos = current_board.blank_x + 1;
            Board new_board = current_board;
            new_board.board[current_board.blank_x][current_board.blank_y] = new_board.board[newpos][current_board.blank_y];
            new_board.board[newpos][current_board.blank_y] = BLANK;
            new_board.blank_x = newpos;

            new_board.goodness = get_goodness(new_board.board);
            new_board.turncount++;

            if (check_solved(new_board))
            {
                printf("Solved in %d turns",new_board.turncount);
                exit(0);
            }

            if (!exists(h,new_board))
            {
                insert(h,new_board);
                push(p,new_board);
            }
        }

        // Move blank right.
        if (current_board.blank_y < 3)
        {
            int newpos = current_board.blank_y + 1;
            Board new_board = current_board;
            new_board.board[current_board.blank_x][current_board.blank_y] = new_board.board[current_board.blank_x][newpos];
            new_board.board[current_board.blank_x][newpos] = BLANK;
            new_board.blank_y = newpos;

            new_board.goodness = get_goodness(new_board.board);
            new_board.turncount++;

            if (check_solved(new_board))
            {
                printf("Solved in %d turns",new_board.turncount);
                exit(0);
            }

            if (!exists(h,new_board))
            {
                insert(h,new_board);
                push(p,new_board);
            }
        }

        // Move blank left.
        if (current_board.blank_y > 0)
        {
            int newpos = current_board.blank_y - 1;
            Board new_board = current_board;
            new_board.board[current_board.blank_x][current_board.blank_y] = new_board.board[current_board.blank_x][newpos];
            new_board.board[current_board.blank_x][newpos] = BLANK;
            new_board.blank_y = newpos;

            new_board.goodness = get_goodness(new_board.board);
            new_board.turncount++;

            if (check_solved(new_board))
            {
                printf("Solved in %d turns",new_board.turncount);
                exit(0);
            }

            if (!exists(h,new_board))
            {
                insert(h,new_board);
                push(p,new_board);
            }
        }
    }

    return NULL;
}

Answer 1

Я попробовал следующее:

Я не вижу ничего плохого в следующем коде, предполагая, что top также удаляет доску из очереди. Это расточительно (если очередь пуста, она будет вращать блокировку и разблокировку мьютекса), но не ошибается.

Я добавил полный код

Это бесполезно без кода для exists, insert и push.

Одно общее замечание:

    pthread_mutex_lock(&priority_queue_lock);
    current_board = top(p);
    pthread_mutex_unlock(&priority_queue_lock);

В приведенном выше коде ваша блокировка является "противоположной" от * Функция 1020 *. Но здесь:

        if (!exists(h,new_board))
        {
            insert(h,new_board);
            push(p,new_board);
        }

вы либо вообще не блокируете (в этом случае это ошибка), либо блокируете «внутри» exists, insert и push.

Вы не должны смешивать "внутреннюю" и "внешнюю" блокировку. Выберите одно или другое и придерживайтесь его.

Если вы на самом деле не блокируете очередь внутри exists, insert и т. Д. c. тогда у вас есть гонка данных и вы думаете о мьютексах неправильно: они защищают инвариантов , и вы не можете проверить, пуста ли очередь параллельно с другим выполняющимся потоком "удалить верхний элемент" "- эти операции требуют сериализации, и поэтому оба должны выполняться под замком.