Я видел людей/статей/SO-сообщений, которые говорят, что они разработали свой собственный "незакрепленный" контейнер для многопоточного использования. Предполагая, что они не использовали трюк модуля производительности (т.е. Каждый поток может вставлять только на основе некоторого модуля), как структуры данных могут быть многопоточными, но также и без блокировки???
Этот вопрос предназначен для C и С++.
Ключ в незаблокированном программировании - использование аппаратно-внутренних атомных операций.
Собственно, даже сами блокировки должны использовать эти атомные операции!
Но разница между заблокированным и незакрепленным программированием заключается в том, что незаблокированная программа никогда не может быть полностью остановлена ни одним потоком. Напротив, если в программе блокировки один поток получает блокировку, а затем приостанавливается неограниченно, вся программа блокируется и не может добиться прогресса. Напротив, незаблокированная программа может продвигаться вперед, даже если отдельные потоки приостановлены неограниченно.
Вот простой пример: параллельное нарастание счетчика. Мы представляем две версии, которые являются "потокобезопасными", т.е. Которые можно вызывать несколько раз одновременно. Сначала заблокированная версия:
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_*. В заблокированной версии нить не может прогрессировать до тех пор, пока поток блокировки не разблокирует мьютекс. Напротив, в версии без блокировки все потоки могут продвигаться вперед. Если поток задерживается, он просто не выполнит свою часть работы, но все остальные получат возможность выполнить свою работу.
Стоит отметить, что в целом программирование без блокировки торгует пропускной способностью и средней пропускной способностью для прогнозируемой задержки. То есть, без блокировки программа, как правило, становится менее эффективной, чем соответствующая программа блокировки, если не слишком много споров (поскольку атомные операции медленны и влияют на большую часть остальной системы), но она гарантирует, что никогда не будет непредсказуемо большие задержки.
Для блокировок идея состоит в том, что вы приобретаете блокировку, а затем выполняете свою работу, зная, что никто другой не может вмешиваться, затем отпустите блокировку.
Для "блокировки" идея состоит в том, что вы выполняете свою работу в другом месте, а затем пытаетесь атомарно передать эту работу в "видимое состояние" и повторите попытку, если вы терпите неудачу.
Проблемы с "блокировкой" заключаются в следующем:
Комбинация этих вещей означает, что она хороша только для относительно простых вещей при низкой конкуренции.
Исследователи разработали такие вещи, как связанные с блокировкой списки (и очереди FIFO/FILO) и некоторые блокирующие деревья. Я не думаю, что там что-то более сложное, чем те. Как это работает, потому что это сложно. Самым разумным подходом было бы определить, какой тип структуры данных вам интересен, а затем искать в Интернете соответствующие исследования по алгоритмам блокировки для этой структуры данных.
Также обратите внимание, что есть что-то, называемое "block free", которое, как блокировка, за исключением того, что вы знаете, что всегда можете совершить работу и не нужно повторять попытку. Еще труднее разработать алгоритм без блоков, но утверждение не имеет значения, так что остальные 2 проблемы с блокировкой исчезают. Примечание: пример "параллельного счетчика" в ответе Kerrek SB вообще не блокируется, но на самом деле блокирован.
Идея "lock free" на самом деле не имеет блокировки, идея состоит в том, чтобы свести к минимуму количество блокировок и/или критических разделов, используя некоторые методы, которые позволяют нам не использовать блокировки для большинства операций.
Это может быть достигнуто с помощью оптимистического дизайна или транзакционной памяти, где вы не блокируете данные для всех операций, но только в некоторых определенных точках (при выполнении транзакции в транзакционной памяти или при необходимости отката в оптимистичном дизайне).
Другие альтернативы основаны на атомных реализациях некоторых команд, таких как CAS (Compare And Swap), что даже позволяет нам решить консенсусная проблема с учетом ее реализации. Выполняя своп на ссылках (и ни один поток не работает с общими данными), механизм CAS позволяет нам легко реализовать оптимизационный дизайн без блокировки (свопинг к новым данным тогда и только тогда, когда никто не изменил его уже, и это выполняется атомарно).
Однако для реализации основного механизма для одного из них, скорее всего, будет использована некоторая блокировка, но количество времени, в течение которого данные будут заблокированы, будет (как предполагается) минимальным, если эти методы используются правильно.
Новые стандарты C и С++ (C11 и С++ 11) имеют потоки и разделяют между типами и операциями атомных данных потоков. Атомная операция дает гарантии для операций, которые запускаются в гонку между двумя потоками. Как только поток возвращается из такой операции, он может быть уверен, что операция выполняется целиком.
Типичная поддержка процессоров для таких атомных операций существует на современных процессорах для сравнения и подкачки (CAS) или с помощью атомных приращений.
Кроме атомарного, тип данных может иметь свойство "lock-free". Это, возможно, было придумано как "без гражданства", поскольку это свойство подразумевает, что операция над таким типом никогда не покинет объект в промежуточном состоянии, даже если он прерывается обработчиком прерываний или чтение другого потока попадает в середину обновления.
Несколько атомных типов могут (или не могут) быть заблокированными, есть макросы для проверки этого свойства. Всегда есть один тип, который гарантированно свободен от блокировки, а именно atomic_flag.
`
у вас есть блокированная библиотека в окнах http://msdn.microsoft.com/en-us/library/windows/desktop/ms683590(v=vs.85).aspx это считается заблокированным.
* il просто цитата из msdn как не большой эксперт: но, главным образом, если аппаратные предпосылки он предоставит вам атомную операцию, которая обрабатывает эту "lockfree", иначе она обеспечит блокировку вокруг нее, используя технологию памяти *
здесь представлены несколько вариаций в _InterlockedExchange, которые различаются в зависимости от типов данных, которые они включают, и используется ли семантика семантики, специфичная для процессора. Хотя функция _InterlockedExchange работает с 32-битными целыми значениями, _InterlockedExchange64 работает с 64-битными целыми значениями. Внутренние функции _InterlockedExchange_acq и _InterlockedExchange64_acq совпадают с соответствующими функциями без суффикса _acq, за исключением того, что операция выполняется с помощью семантики получения, что полезно при вводе критического раздела. Нет версии этой функции, которая использует семантику выпуска. В Visual С++ 2005 эти функции ведут себя как барьеры чтения и записи. Для получения дополнительной информации см. _ReadWriteBarrier. Эти подпрограммы доступны только как встроенные.