Многопоточное программирование без блокировки?

19

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

Этот вопрос предназначен для C и C ++.

    
задан user997112 23.12.2012 в 15:42
источник
  • Проводили ли вы какие-либо исследования? –  Pubby 23.12.2012 в 15:44
  • lock-free обычно не означает «никакой блокировки», это означает что-то вроде транзакционной памяти или оптимистического дизайна, где вы не используете блокировку для каждой операции, но время от времени (для откат или выполнения транзакции ) - потребуется какой-то замок. –  amit 23.12.2012 в 15:46
  • Lock-free обычно означает, что они используют операции сравнения и замены. –  brian beuning 23.12.2012 в 16:59
  • В несколько более широком определении блокировка не относится к мьютексу, а к потенциалу «блокировки» других потоков. Наиболее очевидным примером является не выпуск мьютекса, но это пример кода без блокировки без использования мьютекса: while (X == 0) {X = 1 - X; } Учитывая правильное планирование, два потока могут оставаться в этом цикле навсегда. preshing.com/20120612/an-introduction-to-lock-free-programming –  Bas Smit 03.04.2017 в 18:52

5 ответов

23

Ключ в незаблокированном программировании - использование аппаратно-внутренних атомных операций.

Собственно, даже сами блокировки должны использовать эти атомные операции!

Но разница между заблокированным и незакрепленным программированием заключается в том, что незаблокированная программа никогда не может быть полностью остановлена ​​ни одним потоком. Напротив, если в программе блокировки один поток получает блокировку, а затем приостанавливается неограниченно, вся программа блокируется и не может добиться прогресса. Напротив, незаблокированная программа может продвигаться вперед, даже если отдельные потоки приостановлены неограниченно.

Вот простой пример: Приращение параллельного счетчика. Мы представляем две версии, которые являются «потокобезопасными», т. Е. Которые можно вызывать несколько раз одновременно. Сначала заблокированная версия:

int counter = 0;
std::mutex counter_mutex;

void increment_with_lock()
{
    std::lock_guard<std::mutex> _(counter_mutex);
    ++counter;
}

Теперь версия без блокировки:

std::atomic<int> counter(0);

void increment_lockfree()
{
    ++counter;
}

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

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

    
ответ дан Kerrek SB 23.12.2012 в 15:58
источник
  • И это максимум, который может быть достигнут без блокировок для общего случая. Более сложная операция не будет поддерживаться на уровне HW. Следует отметить, что в некоторых специализированных средах блокировки можно избежать из-за предварительного знания внешних компонентов (hw или sw) - например, HW может гарантировать, что никакие дополнительные данные не будут отправлены до тех пор, пока предыдущий пакет не будет подтвержден принимающим SW –  SomeWittyUsername 23.12.2012 в 16:06
  • @icepack: Правда, существует ограничение на то, сколько вы можете добиться без блокировок. Я думаю, что лучшим примером, который мне нравится, является однопользовательская очередь с несколькими производителями, которая может быть полностью выполнена с атомикой (производители используют CAS для размещения в очереди, потребитель использует Exchange для удаления всей очереди). Многократная / многократная очередь также возможна атомарно, но вы теряете способность управлять динамическими распределениями детерминистически. –  Kerrek SB 23.12.2012 в 16:14
  • Существует реализация блокировки распределителя памяти без блокировки. –  brian beuning 23.12.2012 в 17:04
  • @brianbeuning: проблема заключается в де-распределении, хотя ... В многопользовательской очереди трудно понять, когда безопасно удалять узел очереди. –  Kerrek SB 23.12.2012 в 17:21
  • std :: atomic <int> должен быть реализован с блокировкой, если аппаратное обеспечение не обеспечивает атомарное обновление int. Это все еще считается «незакрепленным», хотя в этом случае он включает блокировку? –  M.M 07.02.2016 в 03:52
13

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

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

Проблемы с «блокировкой» заключаются в следующем:

  • сложно разработать алгоритм без блокировки для чего-то, что не является тривиальным. Это связано с тем, что существует только так много способов выполнить «атомическую фиксацию» (часто полагаясь на атомную «сравнить и обменивать», которая заменяет указатель другим указателем).
  • Если есть противоречия, он работает хуже, чем блокировки, потому что вы многократно выполняете работу, которая отбрасывается / повторится.
  • практически невозможно создать алгоритм без блокировки, который является правильным и «справедливым». Это означает, что (в условиях конкуренции) некоторым задачам может быть повезло (и многократно выполнять свою работу и добиваться прогресса), а некоторые могут оказаться очень неудачными (и многократно терпеть неудачу и повторять попытку).

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

Исследователи разработали такие вещи, как связанные с блокировкой списки (и очереди FIFO / FILO) и некоторые блокирующие деревья. Я не думаю, что есть что-то более сложное, чем те. Ибо, как это работает, потому что это сложно. Самым разумным подходом было бы определить, какой тип структуры данных вам интересен, а затем искать в Интернете соответствующие исследования по алгоритмам блокировки для этой структуры данных.

Также обратите внимание, что есть что-то, называемое «block free», которое, как блокировка, за исключением того, что вы знаете, что всегда можете совершить работу и не нужно повторять попытку. Еще сложнее разработать алгоритм без блоков, но утверждение не имеет значения, так что остальные 2 проблемы с блокировкой исчезают. Примечание: пример «параллельного счетчика» в ответе Kerrek SB вообще не блокируется, но на самом деле он свободен.

    
ответ дан Brendan 23.12.2012 в 16:19
источник
4

Идея «lock free» на самом деле не имеет блокировки, идея состоит в том, чтобы свести к минимуму количество блокировок и / или критических разделов, используя некоторые методы, которые позволяют нам не использовать блокировки для большинства операций.

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

Другие альтернативы основаны на атомных реализациях некоторых команд, таких как CAS (Compare and Swap) , что даже позволяет нам решить консенсусную проблему с учетом ее реализации. Выполняя своп на ссылках (и ни один поток не работает с общими данными), механизм CAS позволяет нам легко реализовать оптимизационный дизайн без блокировки (свопинг к новым данным тогда и только тогда, когда никто не изменил его уже, и это выполняется атомарно).

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

    
ответ дан amit 23.12.2012 в 15:51
источник
  • Это имеет смысл, что есть некоторые блокировки! –  user997112 23.12.2012 в 15:54
  • @ user997112: Обратите внимание, однако, если ваше оборудование разрешает атомный CAS, вы должны иметь возможность реализовать оптимистичный дизайн без каких-либо блокировок. (своп будет ссылочной заменой на полные данные, и ни один поток не будет фактически работать с общими данными) –  amit 23.12.2012 в 15:56
  • Блокировки не блокируются. –  Brendan 23.12.2012 в 16:20
  • Нет ли долгого доказательства того, что любой алгоритм может быть написан полностью без блокировок с использованием CAS? –  Tim Seguine 27.09.2013 в 20:37
3

Новые стандарты C и C ++ (C11 и C ++ 11) имеют потоки и разделяют между типами и операциями атомных данных потоков. Атомная операция дает гарантии для операций, которые запускаются в гонку между двумя потоками. Как только поток возвращается из такой операции, он может быть уверен, что операция выполняется целиком.

Типичная поддержка процессоров для таких атомных операций существует на современных процессорах для сравнения и подкачки (CAS) или с помощью атомных приращений.

Кроме атомарного, тип данных может иметь свойство "lock-free". Это, возможно, было придумано как «без гражданства», поскольку это свойство подразумевает, что операция над таким типом никогда не покинет объект в промежуточном состоянии, даже если он прерывается обработчиком прерываний или чтение другого потока попадает в середину обновления.

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

    
ответ дан Jens Gustedt 23.12.2012 в 17:53
источник
0

у вас есть блокированная библиотека в окнах Ссылка это считается заблокированным.

* il просто цитата из msdn как не большой эксперт: но, главным образом, если аппаратные предпосылки он предоставит вам атомную операцию, которая обрабатывает эту «lockfree», иначе она обеспечит блокировку вокруг нее, используя технологию памяти *

здесь представлены несколько вариаций в _InterlockedExchange, которые различаются в зависимости от типов данных, которые они включают, и используется ли семантика семантики, специфичная для процессора. Хотя функция _InterlockedExchange работает с 32-битными целыми значениями, _InterlockedExchange64 работает с 64-битными целыми значениями. Внутренние функции _InterlockedExchange_acq и _InterlockedExchange64_acq совпадают с соответствующими функциями без суффикса _acq, за исключением того, что операция выполняется с помощью семантики получения, что полезно при вводе критического раздела. Нет версии этой функции, которая использует семантику выпуска. В Visual C ++ 2005 эти функции ведут себя как барьеры чтения и записи. Для получения дополнительной информации см. _ReadWriteBarrier. Эти подпрограммы доступны только как встроенные.

    
ответ дан Nahum 23.12.2012 в 15:54
источник
  • Без комментариев этот ответ предлагает мало. Например, вы можете упомянуть, что эти функции зависят от блокировок шины памяти. –  David Heffernan 23.12.2012 в 15:59