Почему этот код приводит к тупику?

Я удивлен видеть из pstack что этот код приводит к тупику! Я не вижу причины для того же.

pthread_mutex_t lock;

_Cilk_for (int i = 0; i < N; ++i) {
  int ai = A[i];
  if (ai < pivot) {
    pthread_mutex_lock(&lock);
    A[ia++] = ai;
    pthread_mutex_unlock(&lock);
  }
  else if (ai > pivot) {
    pthread_mutex_lock(&lock);
    A[ib++] = ai;
    pthread_mutex_unlock(&lock);
  }
  else {
    pthread_mutex_lock(&lock);
    A[ic++] = ai;
    pthread_mutex_unlock(&lock);
  }
}

Я просто использую мьютексы, чтобы убедиться, что доступ к А является атомарным и сериализованным.

  • Что не так с этим кодом, чтобы привести к тупику?
  • Есть ли лучший способ реализовать это?
Источник

3 ответа

Решение

Если это код внутри функции, значит, вы неправильно инициализируете мьютекс. Вам нужно установить его PTHREAD_MUTEX_INITIALIZER (для простого мьютекса по умолчанию) или выполните pthread_mutex_init() на нем (для более сложных требований). Без надлежащей инициализации вы не знаете, в каком состоянии начинается мьютекс - он вполне может находиться в заблокированном состоянии просто потому, что все, что оказалось в стеке в этой позиции, выглядело как заблокированный мьютекс.

Вот почему его всегда нужно как-то инициализировать, чтобы не было сомнений в исходном состоянии.

Еще одна потенциальная проблема, с которой вы можете столкнуться:

int ai = A[i];

Вы, вероятно, должны защищать этот доступ тем же мьютексом, так как в противном случае вы можете прочитать его в "полусостоянии" (когда другой поток только частично обновляет переменную).

И, я должен сказать, я не уверен, что темы используются здесь с умом. Использование мьютексов может затмить утверждение вроде A[ia++] = ai до такой степени, что подавляющее большинство времени будет потрачено на блокировку и разблокировку мьютекса. Они обычно более полезны, когда код, обрабатываемый во время блокировки, немного более существенен.

Вы можете обнаружить, что непоточный вариант взорвет этот вариант (но, конечно, не поверьте мне на слово - моя основная мантра оптимизации - "измерить, не угадать").

Источник

Ваш pthread_mutex_t lock не инициализируется должным образом, поэтому, поскольку это локальная переменная, она может содержать мусор и находиться в странно заблокированном состоянии. Вы должны вызвать pthread_mutex_init или инициализировать ваш lock с PTHREAD_MUTEX_INITIALIZER

Как жаловались другие, вы не мудро используете мьютексы. Критические разделы вашего кода слишком малы.

Источник

ПОСЛЕ ТОГО, КАК вы исправляете или иным образом подтверждаете, что на самом деле вы инициализируете свой lock:

pstack могут быть замешаны в механизмах контроля, введенных _Cilk_for которые мешают тому, что в противном случае было бы разумно pthread код.

Быстрый поиск показывает, что существуют мьютексные решения для использования с Cilk - смешивание Cilk и pthreads не упоминается. Похоже, что Cilk - это слой поверх pthreads - так что, если Cilk решил обернуть его вокруг mutex, они, вероятно, сделали это по уважительной причине. Я бы посоветовал остаться с Cilk API.

Помимо этого, есть более фундаментальная проблема с вашим алгоритмом. В вашем случае издержки на создание параллельных потоков и их синхронизацию, вероятно, уменьшают стоимость выполнения кода в теле цикла for. Вполне возможно, что это будет работать быстрее без распараллеливания.

Источник
Другие вопросы по тегам