Упрощает ли многопоточное программирование без блокировок что-нибудь?

StackOverflow https://stackoverflow.com/questions/1385468

  •  21-09-2019
  •  | 
  •  

Вопрос

Я мало читал об этой теме, но кажется, что единственное преимущество - это обойти проблемы конкуренции, но это не окажет существенного влияния на проблему взаимоблокировки, поскольку код, свободный от блокировок, настолько мал и фундаментален (fifos, lifos, hash), чтобы никогда не было проблемы взаимоблокировки.

Так что все дело в производительности – верно?

Это было полезно?

Решение

Программирование без блокировок (насколько я понимаю) всегда связано с производительностью, в противном случае использование блокировки в большинстве случаев намного проще и, следовательно, предпочтительнее.

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

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

Другие советы

Пара проблем.

Скоро мы столкнемся с настольными системами с 64, 128 и 256 ядрами.Параллизм в этой области отличается от нашего текущего опыта с 2, 4, 8 ядрами;алгоритмы, которые успешно работают на таких маленьких системах, будут работать помедленнее в высокопараллельных системах из-за конфликтов.

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

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

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

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

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

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

Да, речь идет о производительности...

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

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

Речь идет о производительности, но также и о способности воспринимать многопоточные нагрузки:

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

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

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

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

Я работал над этим вопросом, чтобы написать без ожидания (без блокировки без состояний ожидания) Хранилище ключей и значений для сервера, над которым я работаю.

Такие библиотеки, как Tokyo Cabinet (даже TC-FIXED, простой массив), полагаются на блокировки для сохранения целостности базы данных:

«пока поток записи работает с базой данных, другие потоки чтения и записи блокируются» (Документация Токийского кабинета министров)

Результаты теста без параллелизма (однопоточный тест):

SQLite   time: 56.4 ms (a B-tree)
TC       time: 10.7 ms (a hash table)
TC-FIXED time:  1.3 ms (an array)
G-WAN KV time:  0.4 ms (something new which works, but I am not sure a name is needed)

При параллельном доступе (несколько потоков записи и чтения в одной и той же БД) только G-WAN KV выдержал тот же тест, потому что (в отличие от других) он никогда не блокируется.

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

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

Кстати, я также нашел еще одно доказательство того, что любой алгоритм без блокировок на самом деле можно считать алгоритмом без ожидания из-за законов вероятности и ряда других факторов.

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

  2. Алгоритм без блокировки решает проблему масштабируемости, с которой сталкивается устаревшая блокировка.Итак, я мог бы сказать, что безблокировка в основном предназначена для производительность, не уменьшая вероятность тупиковой ситуации.

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

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

Это все еще слишком долго:Краткое содержание 2 предложения.

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top