Блокировка Deque в Win32 C ++

Question

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

class LocklessDeque
{
  public:

    LocklessDeque() : m_empty(false),
                      m_bottom(0),
                      m_top(0) {}


    ~LocklessDeque()
    {
      // Delete remaining tasks
      for( unsigned i = m_top; i < m_bottom; ++i )
        delete m_tasks[i];
    }


    void PushBottom(ITask* task)
    {
      m_tasks[m_bottom] = task;

      InterlockedIncrement(&m_bottom);
    }


    ITask* PopBottom()
    {
      if( m_bottom - m_top > 0 )
      {
        m_empty = false;

        InterlockedDecrement(&m_bottom);

        return m_tasks[m_bottom];
      }

      m_empty = true;

      return NULL;
    }


    ITask* PopTop()
    {
      if( m_bottom - m_top > 0 )
      {
        m_empty = false;

        InterlockedIncrement(&m_top);

        return m_tasks[m_top];
      }

      m_empty = true;

      return NULL;
    }


    bool IsEmpty() const
    {
      return m_empty;
    }

  private:

    ITask* m_tasks[16];

    bool m_empty;

    volatile unsigned m_bottom;
    volatile unsigned m_top;

};

Answer 1

Глядя на это, я думаю, что это будет проблемой:

void PushBottom(ITask* task)
{
  m_tasks[m_bottom] = task;
  InterlockedIncrement(&m_bottom);
}

Если это используется в реальной многопоточной среде, я бы подумал, что вы столкнетесь при установке m_tasks[m_bottom]. Подумайте, что произойдет, если у вас есть два потока, пытающихся сделать это одновременно - вы не можете быть уверены, какой из них на самом деле установил m_tasks [m_bottom].

Ознакомьтесь с этой статьей , которая является разумным обсуждением очереди без блокировки.

Answer 2

Вы используете члены m_bottom и m_top для индексации массива , а не хорошо Вы можете использовать возвращаемое значение InterlockedXxxx (), чтобы получить безопасный индекс. Вам нужно потерять IsEmpty (), он никогда не может быть точным в многопоточном сценарии. Та же проблема с пустой проверкой в ​​PopXxx. Я не понимаю, как вы могли бы заставить это работать без мьютекса.

Answer 3

Ключом к выполнению почти невозможных вещей, подобных этому, является использование InterlockedCompareExchange. (Это имя используется Win32, но любая многопоточная платформа будет иметь эквивалент InterlockedCompareExchange).

Идея состоит в том, что вы создаете копию структуры (которая должна быть достаточно маленькой, чтобы выполнить атомарное чтение (64 или, если вы можете справиться с некоторой непереносимостью, 128 бит на x86).

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

union State
{
    struct
    {
        short a;
        short b;
    };
    uint32_t volatile rawState;
} state;

void DoSomething()
{
    // Keep looping until nobody else changed it behind our back
    for (;;)
    {
        state origState;
        state newState;

        // It's important that you only read the state once per try
        origState.rawState = state.rawState;
        // This must copy origState, NOT read the state again
        newState.rawState = origState.rawState;

        // Now you can do something impossible to do atomically...
        // This example takes a lot of cycles, there is huge
        // opportunity for another thread to come in and change
        // it during this update
        if (newState.b == 3 || newState.b % 6 != 0)
        {
            newState.a++;
        }

        // Now we atomically update the state,
        // this ONLY changes state.rawState if it's still == origState.rawState
        // In either case, InterlockedCompareExchange returns what value it has now
        if (InterlockedCompareExchange(&state.rawState, newState.rawState,
                origState.rawState) == origState.rawState)
            return;
    }
}

(пожалуйста, прости, если приведенный выше код на самом деле не компилируется - я записал его у меня на голове)

Отлично. Теперь вы можете легко создавать алгоритмы без блокировки. НЕПРАВИЛЬНО! Проблема в том, что вы строго ограничены объемом данных, которые вы можете обновлять атомарно.

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

Не попадайтесь в ловушку, где вы "вращаетесь" или зацикливаетесь (как спин-блокировка). Хотя есть смысл в кратковременном вращении, потому что вы ожидаете, что «другой» поток что-то закончит - они могут этого не делать. «Другой» поток может быть переключен по контексту и может больше не работать. Вы просто тратите время процессора, сжигая электричество (возможно, убивая батарею ноутбука), вращаясь, пока условие не станет истинным. В тот момент, когда вы начинаете вращаться, вы также можете бросить свой код без блокировки и написать его с блокировками. Замки лучше, чем неограниченное вращение.

Просто чтобы перейти от сложного к нелепому, рассмотрим беспорядок, с которым вы можете столкнуться с другими архитектурами - в целом, x86 / x64 довольно простителен, но когда вы попадаете в другие «слабо упорядоченные» архитектуры, вы попадаете на территорию, где случаются вещи, которые не имеют смысла - обновления памяти не будут происходить в порядке программы, поэтому все ваши мысли о том, что делает другой поток, уходят в окно. (Даже x86 / x64 имеют тип памяти, называемый «объединение записи», который часто используется при обновлении видеопамяти, но может использоваться для любого оборудования буфера памяти, где вам нужны ограждения). Эти архитектуры требуют использования операций «ограничения памяти», чтобы гарантировать что все чтения / записи / оба перед ограждением будут видны глобально (другими ядрами). Ограничение записи гарантирует, что любые записи перед разделителем будут видны глобально до любых записей после разделителя. Забор с чтением гарантирует, что никакие чтения после забора не будут спекулятивно выполняться перед забором. Забор для чтения / записи (он же забор или забор памяти) даст обе гарантии. Заборы очень дорогие. (Некоторые используют термин «барьер» вместо «забор»)

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

Написание параллельных алгоритмов без блокировки очень сложно (я уверен, что вы видели написанное 1000 раз в другом месте). Часто это тоже не стоит усилий.

Answer 4

Решая проблему, указанную Аароном, я бы сделал что-то вроде:

void PushBottom(ITask *task) { 
    int pos = InterlockedIncrement(&m_bottom);
    m_tasks[pos] = task;
}

Аналогично, всплыть:

ITask* PopTop() {
  int pos = InterlockedIncrement(&m_top);
  if (pos == m_bottom) // This is still subject to a race condition.
      return NULL;
  return m_tasks[pos];
}

Я бы полностью исключил m_empty и IsEmpty() из дизайна. Результат, возвращаемый IsEmpty, зависит от состояния гонки, то есть к тому времени, когда вы смотрите на этот результат, он может быть устаревшим (то есть то, что он говорит вам об очереди, может быть неправильным, когда вы смотрите на то, что он возвратил). Аналогично, m_empty не предоставляет ничего, кроме записи информации, которая уже доступна без нее, рецепт для получения устаревших данных. Использование m_empty не гарантирует, что оно не будет работать правильно, но оно значительно увеличивает вероятность ошибок, IMO.

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

Редактировать: Я должен отметить, что состояние гонки, указанное в комментарии, довольно серьезное - и оно не единственное. Хотя это несколько лучше, чем оригинал, его следует не принять за код, который будет работать правильно.

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