Нужен ли мьютекс для синхронизации простого флага между pthreads?

Question

Давайте представим, что у меня есть несколько рабочих потоков, таких как:

while (1) {
    do_something();

    if (flag_isset())
        do_something_else();
}

У нас есть несколько вспомогательных функций для проверки и установки флага:

void flag_set()   { global_flag = 1; }
void flag_clear() { global_flag = 0; }
int  flag_isset() { return global_flag; }

Таким образом, потоки продолжают вызывать do_something() в занятом цикле, и в случае, если какой-то другой поток устанавливает global_flag, поток также вызывает do_something_else() (который может, например, выводить информацию о ходе выполнения или отладке при запросе, устанавливая флаг из другая тема).

Мой вопрос: Нужно ли делать что-то особенное для синхронизации доступа к global_flag? Если да, какова минимальная работа для переноса синхронизации переносным способом?

Я пытался выяснить это, прочитав много статей, но я все еще не совсем уверен в правильном ответе ... Я думаю, что это одно из следующего:

A: Нет необходимости синхронизировать, потому что установка или снятие флага не создает условий гонки:

Нам просто нужно определить флаг как volatile, чтобы убедиться, что он действительно читается из общей памяти при каждой проверке:

volatile int global_flag;

Может не распространяться сразу на другие ядра процессора, но рано или поздно гарантировано.

B: Полная синхронизация необходима, чтобы убедиться, что изменения флага распространяются между потоками:

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

volatile int    global_flag;
pthread_mutex_t flag_mutex;

void flag_set()   { pthread_mutex_lock(flag_mutex); global_flag = 1; pthread_mutex_unlock(flag_mutex); }
void flag_clear() { pthread_mutex_lock(flag_mutex); global_flag = 0; pthread_mutex_unlock(flag_mutex); }

int  flag_isset()
{
    int rc;
    pthread_mutex_lock(flag_mutex);
    rc = global_flag;
    pthread_mutex_unlock(flag_mutex);
    return rc;
}

C: Синхронизация необходима для обеспечения распространения изменений флага между потоками:

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

volatile int    global_flag;
pthread_mutex_t flag_mutex;

void flag_set()   { pthread_mutex_lock(flag_mutex); global_flag = 1; pthread_mutex_unlock(flag_mutex); }
void flag_clear() { pthread_mutex_lock(flag_mutex); global_flag = 0; pthread_mutex_unlock(flag_mutex); }

int  flag_isset() { return global_flag; }

Это позволит избежать постоянной блокировки и разблокировки мьютекса, когда мы знаем, что флаг редко изменяется. Мы просто используем побочный эффект мьютексов Pthreads, чтобы убедиться, что изменение распространяется.

Итак, какой?

Я думаю, A и B - очевидный выбор, B - безопаснее. Но как насчет C?

Если C в порядке, есть ли другой способ заставить изменение флага быть видимым на всех процессорах?

Есть один несколько связанный вопрос: Гарантирует ли защита переменной с помощью мьютекса pthread, что она также не кэшируется? ... но на самом деле это не отвечает.

Answer 1

«Минимальный объем работы» является явным барьером памяти.Синтаксис зависит от вашего компилятора;в GCC вы можете сделать:

void flag_set()   {
  global_flag = 1;
  __sync_synchronize(global_flag);
}

void flag_clear() {
  global_flag = 0;
  __sync_synchronize(global_flag);
}

int  flag_isset() {
  int val;
  // Prevent the read from migrating backwards
  __sync_synchronize(global_flag);
  val = global_flag;
  // and prevent it from being propagated forwards as well
  __sync_synchronize(global_flag);
  return val;
}

Эти барьеры памяти выполняют две важные цели:

1. Они вызывают сброс компилятора.Рассмотрим цикл, подобный следующему:

    for (int i = 0; i < 1000000000; i++) {
      flag_set(); // assume this is inlined
      local_counter += i;
    }
   

   Без барьера компилятор может решить оптимизировать его до:

    for (int i = 0; i < 1000000000; i++) {
      local_counter += i;
    }
    flag_set();
   

   Вставка барьера заставляет компилятор немедленно записать переменную обратно.

2. Они заставляют ЦП упорядочивать свои записи и чтения.Это не такая большая проблема с одним флагом - большинство архитектур ЦП в конечном итоге увидят флаг, установленный без барьеров уровня ЦП.Однако порядок может измениться.Если у нас есть два флага и в потоке A:

     // start with only flag A set
     flag_set_B();
     flag_clear_A();
   

   И в потоке B:

     a = flag_isset_A();
     b = flag_isset_B();
     assert(a || b); // can be false!
   

   Некоторые архитектуры ЦП позволяют переупорядочивать эти записи;вы можете видеть оба флага ложными (т. е. флаг A write был перемещен первым).Это может быть проблемой, если флаг защищает, скажем, действительный указатель.Барьеры памяти вынуждают упорядочивать записи для защиты от этих проблем.

Обратите также внимание, что на некоторых процессорах можно использовать семантику барьера «получение-освобождение» для дальнейшего снижения накладных расходов.Однако такого различия не существует в x86, и для него потребуется встроенная сборка в GCC.

Хороший обзор того, что такое барьеры памяти и зачем они нужны, можно найти в каталоге документации ядра Linux..Наконец, обратите внимание, что этого кода достаточно для одного флага, но если вы хотите синхронизировать и с любыми другими значениями, вы должны действовать очень осторожно.Блокировка - это обычно самый простой способ сделать что-либо.

Answer 2

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

юмористический блог на тему: http://software.intel.com/en-us/blogs/2013/01/06/benign-data-races-what-could-possibly-go-wrong

Случай 1: Нет синхронизации на флаге, поэтому все может происходить. Например, компилятору разрешено поворачивать

flag_set();
while(weArentBoredLoopingYet())
    doSomethingVeryExpensive();
flag_clear()

в

while(weArentBoredLoopingYet())
    doSomethingVeryExpensive();
flag_set();
flag_clear()

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

B: полная синхронизация - это правильный вызов. Это просто то, что вы должны сделать.

C: Может работать только синхронизация на устройстве записи, если вы можете доказать, что никто не хочет читать его во время записи. Официальное определение гонки данных (из спецификации C ++ 11) - один поток, записывающий переменную, в то время как другой поток может одновременно читать или записывать одну и ту же переменную. Если ваши читатели и писатели бегут одновременно, у вас все еще есть гоночный случай. Однако, если вы можете доказать, что писатель пишет один раз, происходит некоторая синхронизация, а затем читатели все читают, тогда читатели не нуждаются в синхронизации.

Что касается кэширования, правило состоит в том, что блокировка / разблокировка мьютекса синхронизируется со всеми потоками, которые блокируют / разблокируют один и тот же мьютекс. Это означает, что вы не увидите никаких необычных эффектов кэширования (хотя ваш процессор может делать впечатляющие вещи, чтобы ускорить его работу ... он просто обязан сделать так, чтобы он не делал ничего особенного). Однако, если вы не синхронизируете, вы не получите никаких гарантий, что в другом потоке нет изменений для push, которые вам нужны!

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

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

Answer 3

Назначение входящего задания рабочим потокам не требует блокировки. Типичным примером является веб-сервер, где запрос отлавливается основным потоком, и этот основной поток выбирает работника. Я пытаюсь объяснить это с помощью некоторого псевдо-кода.

main task {

  // do forever
  while (true)

    // wait for job
    while (x != null) {
      sleep(some);
      x = grabTheJob(); 
    }

    // select worker
    bool found = false;
    for (n = 0; n < NUM_OF_WORKERS; n++)
     if (workerList[n].getFlag() != AVAILABLE) continue;
     workerList[n].setJob(x);
     workerList[n].setFlag(DO_IT_PLS);
     found = true;
    }

    if (!found) panic("no free worker task! ouch!");

  } // while forever
} // main task


worker task {

  while (true) {
    while (getFlag() != DO_IT_PLS) sleep(some);
    setFlag(BUSY_DOING_THE_TASK);

    /// do it really

    setFlag(AVAILABLE);

  } // while forever 
} // worker task

Таким образом, если существует один флаг, который одна сторона устанавливает для A, а другая для B и C (основная задача устанавливает для него DO_IT_PLS, а рабочий устанавливает для него BUSY и AVAILABLE), конфликт отсутствует. Воспроизведите его на примере «из жизни», например, когда учитель дает ученикам разные задания. Учитель выбирает ученика, дает ему задание. Затем учитель ищет следующего доступного ученика. Когда ученик готов, он / она возвращается в пул доступных учеников.

ОБНОВЛЕНИЕ : просто уточнить, есть только один основной () поток и несколько - настраиваемое количество - рабочих потоков. Поскольку main () запускает только один экземпляр, нет необходимости синхронизировать выбор и запуск рабочих.

Answer 4

Для приведенного вами примера достаточно случая A при условии, что ...

1. Для получения и установки флага требуется только одна инструкция CPU.
2. do_something_else () не зависит от флага, установленного во время выполнения этой подпрограммы.

Если для получения и / или установки флага требуется более одной инструкции ЦП, вам необходимо выполнить некоторую форму блокировки.

Если do_something_else () зависит от флага, установленного во время выполнения этой подпрограммы, то вы должны заблокировать, как в случае C, но мьютекс должен быть заблокирован перед вызовом flag_isset ().

Надеюсь, это поможет.