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

Указатель NULL - это тот, который указывает на никуда. Когда вы разыскиваете указатель p, вы говорите «дайте мне данные в месте, хранящемся в« p ». Когда p является нулевым указателем, местоположение, хранящееся в p, является nowhere, вы говорите «Дайте мне данные в месте« нигде ». Очевидно, он не может этого сделать, поэтому он выбрасывает NULL pointer exception.

В общем, это потому, что что-то не было правильно инициализировано.

36
задан raven 10 September 2010 в 12:52
поделиться

20 ответов

Короткий ответ:

Вы не можете.

ответ Long:

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

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

, Если Вы все еще настаиваете на том, чтобы создавать свою собственную блокировку свободная структура, быть уверенными:

  • запускаются с чего-то очень простого
  • , понимают модель памяти Вашей целевой платформы (включая ограничения переупорядочения чтения-записи, какие операции являются атомарными)
  • исследование много о проблемах другие люди, с которыми встречаются при реализации блокировки, которую только предполагают свободные структуры
  • , будет ли это работать, доказать, что это
  • в большой степени тестирует результат
[еще 1113] чтение:

свободная Блокировка и ожидают бесплатные алгоритмы в Википедии

Herb Sutter: Код без Блокировок: Ложное чувство безопасности

45
ответ дан Suma 27 November 2019 в 05:13
поделиться

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

Моя реализация действительно использует ConcurrentHashMap, который является алгоритмом блокировки на блок, но она не полагается на ту деталь реализации. Это могло легко быть заменено реализацией Щелчка Cliff без блокировок. Я одолжил идею от Cliff, но использовал намного более явно, должен смоделировать все операции CAS с конечным автоматом. Это значительно упрощает модель, поскольку Вы будете видеть, что у меня есть блокировки psuedo через 'состояния луга. Другой прием должен позволить лень и твердость по мере необходимости. Вы будете часто видеть это с отслеживанием в обратном порядке или разрешением другим потокам "помочь" к очистке. В моем случае я решил позволить мертвые узлы в списке быть выселенным, когда они достигают головы, вместо того, чтобы иметь дело со сложностью удаления их с середины списка. Я могу изменить это, но я не сделал совершенно доверительный мой алгоритм отслеживания в обратном порядке и хотел отложить существенное изменение как принятие подхода блокировки с 3 узлами.

книга "Искусство Многопроцессорного Программирования" является большой краткой информацией. В целом, хотя, я рекомендовал бы избежать проектов без блокировок в коде приложения. Часто времена, это - просто излишество, где другой, менее подверженный ошибкам, методы более подходят.

0
ответ дан Ben Manes 27 November 2019 в 05:13
поделиться

Можно ли разъяснить то, что Вы подразумеваете под структурой?

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

0
ответ дан Dan 27 November 2019 в 05:13
поделиться

В Java используйте java.util.concurrent пакеты в JDK 5 + вместо того, чтобы писать Ваше собственное. Как был упомянут выше, это - действительно поле для экспертов, и если у Вас нет свободного года или два, прокручивание Вашего собственного не является опцией.

0
ответ дан Munger 27 November 2019 в 05:13
поделиться

Уменьшите или устраните совместно использованное изменяемое состояние.

0
ответ дан Craig Day 27 November 2019 в 05:13
поделиться

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

0
ответ дан Oliver Mellet 27 November 2019 в 05:13
поделиться

Ну, это зависит от вида структуры, но необходимо сделать структуру так, чтобы это тщательно и тихо обнаружило и обработало возможные конфликты.

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

Вам, возможно, также понадобилась бы к черепку структура так, чтобы несколько работ потоков над отдельными объектами, и затем позже синхронизировали/повторно комбинировали.

0
ответ дан angry person 27 November 2019 в 05:13
поделиться

Если Вы пишете свои собственные структуры данных без блокировок для многоядерного CPU, не забывайте о барьерах памяти! Кроме того, рассмотрите изучение Память Транзакции программного обеспечения методы.

1
ответ дан jdkoftinoff 27 November 2019 в 05:13
поделиться

Основной принцип для синхронизации без блокировок - это:

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

  • каждый раз, когда Вы видоизменяете структуру, Вы располагаете свой алгоритм и данные так, чтобы был единственный атомарный шаг, который, если взято, заставляет все изменение становиться видимым к другим потокам и вещам расположения так, чтобы ни одно из изменения не было видимо, если тот шаг не сделан. Вы используете любой lockfree атомарный механизм, существует на Вашей платформе для того шага (например, сравнивать-и-устанавливать, load-linked+store-conditional, и т.д.). На том шаге необходимо тогда проверить, чтобы видеть, видоизменил ли какой-либо другой поток объект, так как операция мутации началась, фиксация, если это не имеет и запускается, если это имеет.

существует много примеров структур без блокировок в сети; не зная больше о том, что Вы реализуете и на том, какая платформа трудно быть более конкретным.

1
ответ дан moonshadow 27 November 2019 в 05:13
поделиться

Используйте существующую реализацию, поскольку этой областью работы является область специалистов по проблемной области и PhDs (если Вы хотите сделанный правильно!)

, Например, существует библиотека кода здесь:

http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

2
ответ дан JeeBee 27 November 2019 в 05:13
поделиться

Щелчок утеса имеет купол некоторое основное исследование в области блокировки бесплатные структуры данных путем использования конечных автоматов и также отправил много реализаций для Java. Можно найти его бумаги, слайды и реализации в его блоге: http://blogs.azulsystems.com/cliff/

4
ответ дан dsp 27 November 2019 в 05:13
поделиться

Inmutability имел бы этот эффект. Изменения в объектном результате в новом объекте. Lisp прокладывает себе путь под покрытиями.

Объект 13 из Эффективный Java объясняет эту технику.

5
ответ дан sblundy 27 November 2019 в 05:13
поделиться

Неизменность является одним подходом, чтобы не блокировать. См. обсуждение Eric Lippert и реализация вещей как неизменные стеки и очереди.

7
ответ дан Jeff Moser 27 November 2019 в 05:13
поделиться

Как sblundy, на который указывают, если все объекты неизменны, только для чтения, Вы не должны волноваться о блокировке, однако, это означает, что Вам, вероятно, придется скопировать, возражает много. Копирование обычно включает malloc и блокировку использования malloc для синхронизации выделений памяти через потоки, таким образом, неизменные объекты могут купить Вас меньше, чем Вы думаете (malloc, саму масштабируется скорее плохо, и malloc медленный ; если Вы делаете много malloc в производительности критический раздел, не ожидайте хорошую производительность).

, Когда только необходимо обновить простые переменные (например, интервал на 32 или 64 бита или указатели), выполните просто операции сложения или операции вычитания на них или просто подкачайте значения двух переменных, большая часть предложения платформ "атомарные операции" для того (далее, GCC предлагает их также). Атомарный не то же как ориентированное на многопотоковое исполнение . Однако атомарный удостоверяется, что, если один поток пишет 64 битовых значения в ячейку памяти, например, и другой поток чтения от него, читающий или получает значение перед операцией записи или после операции записи, но никогда поврежденный промежуток значения операция записи (например, тот, где первые 32 бита уже являются новым, последние 32 бита являются все еще старым значением! Это может произойти, если Вы не используете атомарный доступ на такой переменной).

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

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

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

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

12
ответ дан Mecki 27 November 2019 в 05:13
поделиться

Запись ориентированной на многопотоковое исполнение блокировки свободного кода трудна; но эта статья от Herb Sutter запустит Вас.

12
ответ дан Paul van Brenk 27 November 2019 в 05:13
поделиться

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

См. здесь для канонической газеты на этом предмете.

Также попытка этот статья статьи Википедии для дальнейших идей и ссылки.

1
ответ дан Justsalt 27 November 2019 в 05:13
поделиться

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

16
ответ дан Niall 27 November 2019 в 05:13
поделиться

в ре. Ответ Сума, Морис Эрлити показывает в «Искусство многопроцессорного программирования», что на самом деле все, что может быть написано без блокировок (см. Главу 6). iirc, это по существу включает в себя разбиение задач на элементы узла обработки (например, закрытие функций) и постановку в очередь каждого из них. Потоки будут вычислять состояние, следуя всем узлам из последнего кэшированного. Очевидно, что в худшем случае это может привести к последовательной производительности, но оно имеет важные свойства без блокировки, предотвращая сценарии, в которых потоки могут планироваться на длительные периоды времени, когда они удерживают блокировки. Herlithy также достигает теоретической производительности без ожидания, что означает, что один поток не будет ждать вечно, чтобы выиграть атомарную очередь (это много сложного кода).

Многопоточная очередь / стек на удивление сложна (см. Проблему ABA ). Другие вещи могут быть очень простыми. Привыкнуть к блоку while (true) {atomicCAS, пока я его не поменял местами}; они невероятно мощные. Интуиция о том, что правильно с CAS, может помочь в разработке, хотя вам следует использовать хорошее тестирование и, возможно, более мощные инструменты (например, SKETCH , предстоящий MIT Kendo или spin ] ?) чтобы проверить правильность, если вы можете уменьшить ее до простой структуры.

Пожалуйста, опубликуйте больше о вашей проблеме. Трудно дать хороший ответ без подробностей.

edit неизменность хороша, но ее применимость ограничена, если я правильно понимаю. Это действительно не преодолевает опасности записи после чтения; рассмотрим два потока, выполняющих "mem = NewNode (mem)"; они оба могли читать мем, затем оба записывали его; не подходит для классической функции приращения. Кроме того, он, вероятно, медленный из-за выделения кучи (которая должна быть синхронизирована между потоками).

6
ответ дан gatoatigrado 27 November 2019 в 05:13
поделиться

If you see lock contention, I would first try to use more granular locks on your data structures rather than completely lock-free algorithms.

For example, I currently work on multithreaded application, that has a custom messaging system (list of queues for each threads, the queue contains messages for thread to process) to pass information between threads. There is a global lock on this structure. In my case, I don't need speed so much, so it doesn't really matter. But if this lock would become a problem, it could be replaced by individual locks at each queue, for example. Then adding/removing element to/from the specific queue would didn't affect other queues. There still would be a global lock for adding new queue and such, but it wouldn't be so much contended.

Even a single multi-produces/consumer queue can be written with granular locking on each element, instead of having a global lock. This may also eliminate contention.

0
ответ дан J S 27 November 2019 в 05:13
поделиться

Как мой класс (Нир Шавит из «Искусства многопроцессорного программирования») сказал классу: пожалуйста, не надо. Основная причина - тестируемость - вы не можете протестировать код синхронизации. Вы можете запустить симуляции, вы можете даже стресс-тест. Но это грубое приближение в лучшем случае. Что вам действительно нужно, так это математическое доказательство правильности. И очень немногие способны понять их, не говоря уже о написании их. Итак, как говорили другие: используйте существующие библиотеки. В блоге Джо Даффи рассматриваются некоторые приемы (раздел 28). Первое, что вы должны попробовать - это разбиение дерева - разбить на более мелкие задачи и объединить.

10
ответ дан felixg 27 November 2019 в 05:13
поделиться
Другие вопросы по тегам:

Похожие вопросы: