Здравствуйте, remark, Вы писали:
R>Большую часть моих "изысканий" я уже не публикую на RSDN — по опыту просто я вижу, что они не находят никакого отклика и понимания... Получается совершенно пустой труд. Тут я описываю, только самые общие вещи, т.к. сказать вводную часть, что доступно широким массам. Поэтому только по RSDN ты за моими изысканими не проследишь
Столько внимания к моей персоне, я прям весь засмущался и покраснел
Там я стараюсь публиковать все разработанные алгоритмы. Но там только так сказать сухая выжимка, т.е. никаких общих слов, только код. Так же там я пишу на ломаном нижегородско-английском, дабы это было доступно большей аудитории. Но я надеюсь, что это проблемой не будет.
Но значительная часть, особенно касающаяся общих вопросов, дизайна алгоритмов и т.д. пока находится исключительно у меня в голове. Просто нет времени и сил всё это излагать.
Так же со всеми этими алгоритмами связана большая проблема. Алгоритмы синхронизации, основанные на мьютексах, очень... как сказать... прямолинейны в своей семантике, побочных эффектах и т.д. С "нетрадиционными" алгоритмами синхронизации обычно всё не так просто. Например, какой-то алгоритм рассчитан на применение в окружении с фиксированным количеством потоков. Или например, есть несколько алгоритмов освобождения памяти для lock-free алгоритмов, но все они обладают слабыми сторонами, т.е. например для ситуации, когда много чтений, но мало записей лучше подходит один алгоритм, а когда наоборот, то другой. Или например, большинство lock-free алгоритмов (в не garbage-collected environment) требуют наличия упомянутого механизма освобождения памяти, а эти алгоритмы зачастую "первазивны", т.е. требуют чтобы, например, все потоки приложения периодически вызывали определенную функцию, если этого не будет, то остановится всё освобождение памяти. И т.д.
Как следствие такие алгоритмы иногда сложно выразить в "библиотечной" форме, т.е. готовой для простого использования в любом приложении. Из-за описанных "побочных эффектов", существенную роль приобретает вопрос — как, где, когда и почему их *применить*. А не просто сам алгоритм.
Если бы не это, то самым естественным способом для выражения таких алгоритмов было бы просто создание библиотеки, лёгкой для использования, и со спрятанными под капотом сложностями. Но так зачастую не получается.
Если разрабатывать алгоритмы под конкретное приложение, под конкретную ситуацию, то всё получается значительно легче.
Здравствуйте, CiViLiS, Вы писали:
CVL>PS Обязуюсь в дальнешем побороть лень и все интересные сообщения оценивать, дабы хоть какой то отклик был
Ну это будет хотя бы что-то. А то иногда я пытаюсь вдаваться в какие-то детали, а реакции 0, ни плюсов, ни минусов, ни ответов, ни вопросов. Особенно учитывая, что времени на серьёзные ответы зачастую уходит много, это сильно деморализует.
С некоторыми сообщениями вообще комическая ситуация — оценок, допустим, 10, а в избранное добавили 20
Вот лидеры:
оценок — 7, в избранном у 22: http://www.rsdn.ru/Forum/message/1849716.1.aspx
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, Константин Л., Вы писали:
КЛ>>По поводу того, что дискуссии не получается ты зря, мы читаем и наматываем на ус. так что это все очень полезно.
E>Возможно, проблема в том, что наматывание RSDN-овцами себе на ус никак не отражается на материальном благосостоянии самого remark-а.
Бесспорно, если бы какой-то из способов сопровождался улучшением моего материального состояния, то он бы имел у меня значительно больший приоритет, я бы уделял ему больше времени, и делал бы всё с бОльшим усердием
Здравствуйте, Roman Odaisky, Вы писали:
RO>Здравствуйте, remark, Вы писали:
R>>На месте, по крайней мере, я стоять не люблю R>>Большую часть моих "изысканий" я уже не публикую на RSDN — по опыту просто я вижу, что они не находят никакого отклика и понимания... Получается совершенно пустой труд. Тут я описываю, только самые общие вещи, т.к. сказать вводную часть, что доступно широким массам. Поэтому только по RSDN ты за моими изысканими не проследишь
RO>Ты пишешь преимущественно в ФП, а это опасный для здоровья форум, пиши в C++
Да я и сам в раздумьях. В принципе на RSDN такое вообще некуда писать. Форума посвященного multithreading'у и всему, что с ним свзано, нет.
На последние сообщения я делал анонсы в C++. Всё таки только в С++, я думаю, будет значительно меньше аудитория.
По поводу здоровья. Слава богу самые вредители здоровья в ФП (не будем называть имён... их и так все знают ) пока похоже обходят стороной мои сообщения
RO>Лично мне твои сообщения весьма интересны, но пока только теоретически, вот не являются сверхскоростные сервера моей нынешней сферой деятельности. Хотя я и хотел бы.
RO>Можешь быть уверен, что твои исследования наматываются на усы большими лебедками, даже если мало кто осмеливается их комментировать
RO>Кстати, а что именно разрабатываешь ты? Можно ли посмотреть на высокие технологии в действии?
Многие считают, что я разрабатываю что-то экстремальное. Но на самом деле я ничего не разрабатываю. Это просто хобби. Желание есть, но такой работы в Росии пока нет. Хочется надеяться, что это временно.
Плюс ещё "жалко" остальную команду, они ещё от Егорушкина отходят, а тут ещё я со своими lock-free алгоритмами. Поэтому я стараюсь держать всё в рамках приличия
Здравствуйте, CreatorCray, Вы писали:
CC>У меня тоже есть интерес к lock-, wait-, obstruction-, atomic-free алгоритмам. Пока наращиваю "мускульную массу", читаю вумных людей, пробую что то реализовывать и с ним играться.
Здравствуйте, remark, Вы писали:
R>С некоторыми сообщениями вообще комическая ситуация — оценок, допустим, 10, а в избранное добавили 20
Оценивать популярность по добавлениям в избранное наверное не стоит.
Я к примеру добавляю только тогда, если там есть куча ссылок или какой либо информации к которой хочу вернуться позже. Т.е. пользуюсь им как закладками.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Здравствуйте, RailRoadMan, Вы писали:
R>>Для факультативного чтения могу предложить: R>>Practical lock-freedom R>>или более свежий: R>>Concurrent Programming Without Locks R>>Обе работы написаны KEIR FRASER и TIM HARRIS, и содержат достаточно обширную "вводную часть" с освещением всех базовых вопросов.
RRM>Я понял, что основа lock-free адгоритмов — CAS, multiple-CAS и STM?
Основа lock-free алгоритмов — всё, что не блокируется. Начиная от обычных сохранений/загрузок из памяти, и заканчивая CAS.
Есть FAA (fetch-and-add).
Есть просто атомарные and/or/xor.
Есть single-word CAS, обычно просто CAS.
Есть double-word CAS, DCAS или DWCAS.
Есть double CAS, DCAS — не присутствует на современных архитектурах.
MCAS — и никогда не присутствовал. Однако возможно построение MCAS поверх STM/HTM, хотя это уже не совсем честно.
Чисто формально алгоритм использующий STM/HTM будет либо lock-free, либо obstruction-free. Зависит от того, какая реализация STM/HTM используется. Однако обычно их так не называют, а называют просто алгоритм построенный с использованием STM/HTM. Интересная особенность, что будучи lock-free (obstruction-free) такой алгоритм по своему виду идентичен lock-based алгоритму. Фактически просто производится механическая замена захвата/освобождения мьютекса на начало/коммит транзакции. В этом собственно основная сильная сторона STM/HTM.
RRM>Сейчас перечитываю вторую работу, кроме того примерно 1.5 года назад прочитал пару статей по STM. RRM>Свои мысли на этот счет я изложил здесь
1) Серьезное ограничение по сравнению с блокировками — невозможность синхронизировать ввод/вывод.
Транзацкии должны быть _перезапускаемы_ (автоматически или явно — это не важно) — этим все сказано.
Да.
2) Насколько я понял в STM используется оптимистичная синхронизация, ктр предполагает практическое отсутствие конфликтов между потоками, т.е. транзакиция выполнятеся в надежде, что синхронизация вообще не нужна, в момент commit-а это проверяется и если все нормально действия принимаются, если конфликт был транзакция перезапускается.
Ну тут зависит от длительности транзакции и кол-ва конфликтов. Например, 10-30% перезапусков для небольших транзакций, я думаю, не страшно.
Чем длинее транзакция и чем больше потоков могут потенциально пересечься тем меньше вероятность что транзакия не будет перезапушена, т.е. под нагрузкой производительность будет падать. Вопрос насколько?
Вырожденный случай — полная блокировка программы несколькими транзакциями ктр постоянно прерывают друг друга. Т.е. фактически корретныя программа при увеличении нагрузки может повиснуть в своеобразном deadlock-е
Я не говорю, что это реальная проблема, но тем не менее неприятно что это вообще возможно.
Оптимистический подход предполагает, что конкуренция должна быть не очень высокая. И перезапуск должен быть возможен. И перезапуск должен быть относительно недорогим. Т.е. для некоторых ситуаций, действительно, более разумно использовать мьютексы, даже при наличии хорошей STM/HTM.
3) Сложность с транзакцоными переменными, ктр являются большимо сложными объектами.
Затраты на создании копии сложного объекта (как память на хранение копии, так и время на копирование)
Затраты на определения был ли реально этот объект изменен и нужно ли перрывать транзакцию
Причем чем длинее транзакция тем сильнее будут проявляться проблемы
Можешь пояснить на примерах, что ты имеешь в виду. Как я себе это сейчас вижу, при использовании STM/HTM не надо ничего особо копировать, можно просто внести изменения в старый объект. А все, кто его читает, атомарно увидит либо старую версию, либо новую.
Достоинства:
1) Можно написать большими буквами. ОТСУТСВИЕ БЛОКИРОВОК и все проблемм с ними связянных
Какие проблемы ты имеешь в виду?
Очень много проблем выкрикивается как раз теми, кто сейчас начал продвигать STM/HTM. Т.е. небольшой участок кода под блокировкой, который захватывает только одну блокировку за раз, и не вызывает никакого стороннего кода, у него вобщем-то не так уж и много недостатков.
RRM>Больше всего сомнений/вопросов возникает по поводу достаточно длинных транзакций в связи RRM>1) Возможно livelock — параллельные транзакции, ктр не дают закоммитить друг другу изменения
Если STM/HTM lock-free, то этого не будет. Если только obstruction-free, то это возможно.
Сейчас STM примерно 50 на 50 lock-free или obstruction-free. Но lock-free реализации значительно тяжелее.
Первая наклювывающаяся HTM очень сильно obstruction-free.
RRM>2) Вероятность того, что поток выполняющий транзакцию будет ведеть inconsistent состояние, как результат коммита параллельных транзакций.
Опять же зависит от реализации. Некоторые позволяют dirty-read, некоторые — нет. В некоторых языках (Java, C#, Haskell) с этим можно что-то сделать, в других (C/C++) — нет.
Но вообще такая проблема существует. Стратегия решения в лоб — валидировать транзакцию после каждого чтения. Она работает, но экстремально дорогая.
RRM>Понятно, что транзакция в рамках ктр было inconsistent состояние не сможет завершиться и будет перезапущена, но она должна еще дойти до точки коммита и не зависнуть где-то внутри себя.
Именно. В общем случае поток может обратиться по невалидному указателю, или повиснуть в бесконечном цикле. Но повторюсь, в некоторых реализациях такой проблемы нет.
RRM>Очевидно, что алгоритм нужно писать соответствующим образом, но на первый взгляд это ничем не легче чем написать корректный код с блокировками. RRM>Есть ли какой-то опыт появления таких проблем в реальных приложениях или это в большей степени теоретические проблемы?
А что если совместить lock-based и lock-free модели?..
Т.е., предположим, все фундаментальные взаимодействия между процессами исчерпываются двумя классами — pipe (один поток пишет, другой читает) и, не знаю как это назвать, пусть будет share — когда есть несколько потоков которые могут как читать, так и писать. Причем по определению первый класс взаимодействий применяется для передачи большого (хотя это необязательно) объема однородных данных, а второй — для совместного доступа к данным со сложной структурой.
Тогда первый класс можно сделать частично lock-based, скажем, есть буфер, который разделен на несколько частей и при записи данных в буфер блокируется некоторая его часть, либо весь буфер если он небольшого размера.
Второй же класс можно реализовать через STM, чтобы обеспечить возможность одновременного доступа большого числа потоков без большого оверхеда.
К тому же, такую систему можно реализовать "прозрачно", что, имхо, вполне оправдает небольшую возможную потерю производительности.
Собственно, интересует полнота такой модели синхронизации. То есть, можно ли обойтись только этими двумя примитивами (lock-based pipe и STM-based share) для синхронизации потоков в приложении, или есть примеры, когда этого точно будет недостаточно, или будет очень большая потеря производительности?
Здравствуйте, MaxxK, Вы писали:
MK>А что если совместить lock-based и lock-free модели?..
Во-первых, какая конечная ЦЕЛЬ всего этого? Что ты хочешь получить в итоге?
з.ы. в принципе lock-based и lock-free прекрасно совмещаются даже в рамках одного объекта.
MK>Т.е., предположим, все фундаментальные взаимодействия между процессами исчерпываются двумя классами — pipe (один поток пишет, другой читает) и, не знаю как это назвать, пусть будет share — когда есть несколько потоков которые могут как читать, так и писать. Причем по определению первый класс взаимодействий применяется для передачи большого (хотя это необязательно) объема однородных данных, а второй — для совместного доступа к данным со сложной структурой.
MK>Тогда первый класс можно сделать частично lock-based, скажем, есть буфер, который разделен на несколько частей и при записи данных в буфер блокируется некоторая его часть, либо весь буфер если он небольшого размера.
А почему очередь lock-based, а не lock-free или STM?
MK>Второй же класс можно реализовать через STM, чтобы обеспечить возможность одновременного доступа большого числа потоков без большого оверхеда.
В общем случае утверждение, что STM == одновременный доступ без большого оверхеда, неверно.
MK>К тому же, такую систему можно реализовать "прозрачно", что, имхо, вполне оправдает небольшую возможную потерю производительности.
MK>Собственно, интересует полнота такой модели синхронизации. То есть, можно ли обойтись только этими двумя примитивами (lock-based pipe и STM-based share) для синхронизации потоков в приложении, или есть примеры, когда этого точно будет недостаточно, или будет очень большая потеря производительности?
Сложно что-либо прокомментировать по-существу пока не понятна ЦЕЛЬ.
Теоретически, даже какого-либо одного из этих примитивов достаточно для обеспечения полноты. Например, легко представить систему, состоящую из некоторого числа независимых потоков, которые взаимодействуют только посредством очередей сообщений. Так строятся системы на основе MPI. Разделяемые ресурсы в такой системе моделируются следующим образом. Какой-то поток объявляется владельцем, остальные потоки отправляют ему "запросы", он обрабатывает и отсылает назад "ответы".
Так так же есть 2 очень интересных примера применения TM.
Первый — на основе TM строится какой-то другой примитив, отсутствующий в явном виде, например, DCAS, и далее все алгоритмы строятся уже на основе DCAS. Тут длительность каждой транзакции минимальна, но алгоритм в общем случае состоит из нескольких атомарных транзакций.
Второй — lock elision (не знаю как перевести). Это как бы попытка оптимистической элиминация мьютекса. Почему это получается быстрее обычного мьютекса для меня правда загадка. Видимо особенность реализации HTM.
R>
Здравствуйте, remark, Вы писали:
R>Чисто формально алгоритм использующий STM/HTM будет либо lock-free, либо obstruction-free. Зависит от того, какая реализация STM/HTM используется. Однако обычно их так не называют, а называют просто алгоритм построенный с использованием STM/HTM. Интересная особенность, что будучи lock-free (obstruction-free) такой алгоритм по своему виду идентичен lock-based алгоритму. Фактически просто производится механическая замена захвата/освобождения мьютекса на начало/коммит транзакции. В этом собственно основная сильная сторона STM/HTM.
Все таки "классический" вариант, когда коммит и соответвтенно валидация делаются в конце транзакции, — obstruction-free. Это исключительно imho
lock-free его может сделать валидация транзакции при каждом обращении к элементу транзакции, но это теоретически достаточно дорогая операция. При валидации необходимо _атомарно_ провалидировать все элементы и проапдейтить (если мы храним копии), т.е. сделать что-то похожее на MCAS. Я до сих пор не понял, как его предполагается делать эффективно, ведь MCAS нет на современной аппаратуте. Ну разве что использовать lock —
Ну или коммит реализовывать как некий lock-free алгоритм, т.е. lock-free внутри другого lock-free
R>
R>Чем длинее транзакция и чем больше потоков могут потенциально пересечься тем меньше вероятность что транзакия не будет перезапушена, т.е. под нагрузкой производительность будет падать. Вопрос насколько?
R>Вырожденный случай — полная блокировка программы несколькими транзакциями ктр постоянно прерывают друг друга. Т.е. фактически корретныя программа при увеличении нагрузки может повиснуть в своеобразном deadlock-е
R>Я не говорю, что это реальная проблема, но тем не менее неприятно что это вообще возможно.
R>Оптимистический подход предполагает, что конкуренция должна быть не очень высокая. И перезапуск должен быть возможен. И перезапуск должен быть относительно недорогим. Т.е. для некоторых ситуаций, действительно, более разумно использовать мьютексы, даже при наличии хорошей STM/HTM.
R>Этот пункт вместе с первым говорит о том, что STM/HTM не серебрянная пуля: R>http://groups.google.com/group/comp.arch/msg/88ce8bc80c3fc747
Полностью согласен
R>
R>3) Сложность с транзакцоными переменными, ктр являются большимо сложными объектами.
R>Затраты на создании копии сложного объекта (как память на хранение копии, так и время на копирование)
R>Затраты на определения был ли реально этот объект изменен и нужно ли перрывать транзакцию
R>Причем чем длинее транзакция тем сильнее будут проявляться проблемы
R>Можешь пояснить на примерах, что ты имеешь в виду. Как я себе это сейчас вижу, при использовании STM/HTM не надо ничего особо копировать, можно просто внести изменения в старый объект. А все, кто его читает, атомарно увидит либо старую версию, либо новую.
Предположим, что транзакционная переменная не просто целое число, а действительно объект, ктр уже существует и не может быть изменен. Что будет если две транзакции будут в него одновременно писать? Тут вообще никаких гарантий нет, что он останется в согласованном состоянии.
Если делать копии, то возникнет проблема атомарного сравнения двух копий объектов при коммите/валидации транзакции.
Даже если транзакционные переменные простые слова, я не до конца уверен, что можно обойтись без их копирования. Интуиция подсказывает, что нужно, но объяснить пока не могу. В любом случае, если этого не делать, то dirty-read возможен даже из тех переменных, куда мы только что записали
R>
R>Достоинства:
R>1) Можно написать большими буквами. ОТСУТСВИЕ БЛОКИРОВОК и все проблемм с ними связянных
R>Какие проблемы ты имеешь в виду? R>Очень много проблем выкрикивается как раз теми, кто сейчас начал продвигать STM/HTM. Т.е. небольшой участок кода под блокировкой, который захватывает только одну блокировку за раз, и не вызывает никакого стороннего кода, у него вобщем-то не так уж и много недостатков.
Здравствуйте, remark, Вы писали:
R>Так так же есть 2 очень интересных примера применения TM.
R>Первый — на основе TM строится какой-то другой примитив, отсутствующий в явном виде, например, DCAS, и далее все алгоритмы строятся уже на основе DCAS. Тут длительность каждой транзакции минимальна, но алгоритм в общем случае состоит из нескольких атомарных транзакций.
В соседнем сообщении я уже написал, про реализацию коммита в STM. В случае DCAS и STM получается как с курицей и яйцом. Одно невозможно без другого. Возможно, я просто не до конца понимаю, как это реализовать.
Здравствуйте, RailRoadMan, Вы писали:
R>>Первый — на основе TM строится какой-то другой примитив, отсутствующий в явном виде, например, DCAS, и далее все алгоритмы строятся уже на основе DCAS. Тут длительность каждой транзакции минимальна, но алгоритм в общем случае состоит из нескольких атомарных транзакций.
RRM>В соседнем сообщении я уже написал, про реализацию коммита в STM. В случае DCAS и STM получается как с курицей и яйцом. Одно невозможно без другого. Возможно, я просто не до конца понимаю, как это реализовать.
RRM>Ну или нужен _H_TM.
Вообще размыiляя над STM, я приходу к мысли, что эта концепция значительно сложнее как с точки зрения реализации так и использования. Естественно не рассматривая примитивные случаи.
Главная проблема STM — больше по сравнения с использованием блокировок возможных пересечений двух потоков и взаимных влияний. Если при использовании блокировок потоки влияют друг на друга в точках работы с блокировками и основная сложность — все варианты последовательностей, в которых потоки могут приходить в эти точки. То с STM добавляются dirty-read. Если STM реализована без dirty-reads, то видимо усложнится сама реализация.
Мне кажется STM займет свою нишу, но это будет специализированный инструмент. На роль серебрянной пули больше подходит идея Erlang-а с процессами обменивающимися сообщениями. IMHO
Здравствуйте, remark, Вы писали:
R>Во-первых, какая конечная ЦЕЛЬ всего этого? Что ты хочешь получить в итоге?
Ну так как форум философский, возьмем крупномасштабный пример — сообщение между процессами и потоками в (серверной) ОС. Ну и цель в таком случае — большая производительность на многоядерных системах + хороший потенциал в плане масштабируемости (т.е. не так как ты описал, с экспоненциальным ростом времени )
R>А почему очередь lock-based, а не lock-free или STM?
Для упрощения реализации. В данном случае взаимодействуют только 2 потока, и я предполагаю что можно реализовать с одной стороны простой и легковесный, а с другой стороны исключающий дедлоки примитив передачи данных.
R>В общем случае утверждение, что STM == одновременный доступ без большого оверхеда, неверно.
Согласен, это зависит от модели транзакционной памяти и ее реализации. Но имхо возможно реализовать ее именно так — чтобы была гарантия lock-free и "легкие" транзакции. Пожертвовать, видимо, в данном случае приходится сложной системой разрешения конфликтов транзакций с рассчетом на то, что транзакций, изменяющих объект будет меньше, чем операций чтения. В тех случаях когда это не вписывается в такую модель, придется использовать нужное количество pipe.
R>Теоретически, даже какого-либо одного из этих примитивов достаточно для обеспечения полноты. Например, легко представить систему, состоящую из некоторого числа независимых потоков, которые взаимодействуют только посредством очередей сообщений. Так строятся системы на основе MPI. Разделяемые ресурсы в такой системе моделируются следующим образом. Какой-то поток объявляется владельцем, остальные потоки отправляют ему "запросы", он обрабатывает и отсылает назад "ответы".
Я тут в качестве основного преимущества вижу простоту системы. Хотя мб упускаю какие-то еще преимущества.
Но не будет ли следующий пример несколько неподходящим для очередей сообщений?
Имеем некоторую древовидную структуру, скажем, вроде VFS. "Листья" данного дерева в этом примере — это примонтированные разделы. При необходимости доступа по какому-то пути, сначала запрашивается нужный лист дерева, потом ему дается собственно запрос. Последнее взаимодействие, наверное, нормально реализуется через очереди сообщений. Но вот первое — т.е. поиск нужного листа по какому-то идентификатору... Очевидно, изменение структуры дерева не такая частая операция, по сравнению с чтением структуры.
Имхо, в данном примере "прямой" доступ к этому дереву с использованием STM будет быстрее и, возможно, удобнее — в многопроцессорном варианте, — чем создание очереди (или очередей) сообщений для "желающих" пообщаться с VFS.
R>
Здравствуйте, MaxxK, Вы писали:
R>>Во-первых, какая конечная ЦЕЛЬ всего этого? Что ты хочешь получить в итоге? MK>Ну так как форум философский, возьмем крупномасштабный пример — сообщение между процессами и потоками в (серверной) ОС. Ну и цель в таком случае — большая производительность на многоядерных системах + хороший потенциал в плане масштабируемости (т.е. не так как ты описал, с экспоненциальным ростом времени )
Ну что ж, цель достойная, мне нравится
Дабы не запутаться окончательно тут надо выделить 2 аспекта. Первый — высокоуровневый дизайн, второй — реализация конкретных структур данных.
Что касается дизайна, то лично я считаю такую модель (пайпы + шары) практически идеальной. С помощью пайпов (очередей сообщений) система хорошо структурируется на независимые части, каждая часть "однопоточно" (читай эффективно) работает со своими локальными данными, а всё взаимодействие с остальным миром очень чётко структурировано — можно только отправлять сообщения или принимать сообщения.
При этом, как ты правильно заметил, для некоторых структур данных работа на основе обмена сообщениями будет очень неэффективной. Во-первых, резко повышается латентность операций — вместо прямого обращения к разделяемой структуре, нам теперь надо отправить сообщение, другой поток "когда-то" его достанет из очереди, обработает, отправит ответ, потом исходный поток опять "когда-то" достанет ответ из очереди и продолжит обработку. Во-вторых, стоимость тоже не очевидна, т.к. каждая операция с сообщением — это обращение к разделяемой структуре данных, а у нас тут получается 4 таких операции. В третьих, если это центральная структура данных, и при этом с ней напрямую может работать только один поток, а остальные только с помощью сообщений, то получается, что у нас фактически производительность системы ограничена производительностью одного потока. Представь, например, 32-ух процессорную систему, на которой все процессоры обязаны постоянно обращаться к одному — 31 процессор будет большую часть времени простаивать.
Исходя из всего этого я лично считаю, что системы типа Eralng (основанные исключительно на обмене сообщениями) сливают в общем случае.
Тут целесообразно *некоторые* структуры реализовать именно как многопоточные разделяемые модифицируемые структуры, сделав реализацию оптимальную под данную задачу.
Что касается реализации.
Очереди типа single-producer/single-consumer можно реализовать экстремально эффективно без использования ни мьютексов, ни TM. В такой реализации каждая операция (enqueue/dequeue) занимает не более 10 машинных инструкций и не содержит никаких тяжёлых операций, типа InterlockedXXX или тяжёлых барьеров памяти. Бенчмарки такой очереди против реализаций на основе мьютексов, TM, InterlockedXXX похожи на кровопролитное массовое убийство невинных детей. Это единственный верный путь.
Что касается реализации других разделяемых структур — сложный вопрос. Он должен решаться индивидуально. Для каких-то структур STM может быть хорошим решением. Для каких-то не очень. STM — в общем случае не панацея.
Рассмотри следующую ситуацию. Есть большой список лицевых счетов. Над списком есть ряд операций, в т.ч. — проходить по всему спику и считать сумму всех балансов, и переводить сумму с одного л/с на другой. При реализации на основе STM и высокой нагрузке, как подсказывает логика и показывает практика, операции прохождения по списку *вообще* не проходят. Т.к. достаточно одной опрации модификации за время прохождения по *длинному* списку, что бы проход провалился. При чём тут не важно STM obstruction-free или lock-free — всё равно операциям прохода будет тотально "невезти".
Как следствие, если разработчик оказывается в такой ситуации и слепо верит в STM/HTM и больше ничего не умеет, то он попадает в достаточно затруднительную ситуацию...
Здравствуйте, RailRoadMan, Вы писали:
RRM>Здравствуйте, RailRoadMan, Вы писали:
R>>>Первый — на основе TM строится какой-то другой примитив, отсутствующий в явном виде, например, DCAS, и далее все алгоритмы строятся уже на основе DCAS. Тут длительность каждой транзакции минимальна, но алгоритм в общем случае состоит из нескольких атомарных транзакций.
RRM>>В соседнем сообщении я уже написал, про реализацию коммита в STM. В случае DCAS и STM получается как с курицей и яйцом. Одно невозможно без другого. Возможно, я просто не до конца понимаю, как это реализовать.
RRM>>Ну или нужен _H_TM.
Нет, не обязательно. Сейчас я попробую подобрать ряд ссылок по поводу реализации различных видов STM.
STM обычно реализует на основе CAS. Я недавно делал небольшую тестовую реализацию вообще на основе только XCHG (InterlockedExchange).
RRM>Вообще размыiляя над STM, я приходу к мысли, что эта концепция значительно сложнее как с точки зрения реализации так и использования. Естественно не рассматривая примитивные случаи.
Реализация STM неимоверно сложная. Причём большинство решений компромиссные.
Использование... ну в идеале STM просто "магически" работает, а программист ни о чём не думает, т.е. просто заменяет mutex.lock()/mutex.unlock() на trx_begin()/trx_commit() или вообще atomic {}. Такие реализации есть, но они очень непроизводительные. Остальные реализации предоставляют некий компромисс.
RRM>Главная проблема STM — больше по сравнения с использованием блокировок возможных пересечений двух потоков и взаимных влияний. Если при использовании блокировок потоки влияют друг на друга в точках работы с блокировками и основная сложность — все варианты последовательностей, в которых потоки могут приходить в эти точки. То с STM добавляются dirty-read. Если STM реализована без dirty-reads, то видимо усложнится сама реализация.
В пределе в STM нет dirty-read.
RRM>Мне кажется STM займет свою нишу, но это будет специализированный инструмент. На роль серебрянной пули больше подходит идея Erlang-а с процессами обменивающимися сообщениями. IMHO
Здравствуйте, RailRoadMan, Вы писали:
RRM>Здравствуйте, remark, Вы писали:
R>>Чисто формально алгоритм использующий STM/HTM будет либо lock-free, либо obstruction-free. Зависит от того, какая реализация STM/HTM используется. Однако обычно их так не называют, а называют просто алгоритм построенный с использованием STM/HTM. Интересная особенность, что будучи lock-free (obstruction-free) такой алгоритм по своему виду идентичен lock-based алгоритму. Фактически просто производится механическая замена захвата/освобождения мьютекса на начало/коммит транзакции. В этом собственно основная сильная сторона STM/HTM.
RRM>Все таки "классический" вариант, когда коммит и соответвтенно валидация делаются в конце транзакции, — obstruction-free. Это исключительно imho
Достаточно просто отсортировать ячейки для захвата, что бы реализация стала lock-free.
Представь — есть массив ячеек, каждый поток пытается атомарно захватить некий случайный набор ячеек. Если ячейки отсортировать перед захватом, то какой-то один поток обязательно захватит все необходимые ему ячейки.
RRM>lock-free его может сделать валидация транзакции при каждом обращении к элементу транзакции, но это теоретически достаточно дорогая операция. При валидации необходимо _атомарно_ провалидировать все элементы и проапдейтить (если мы храним копии), т.е. сделать что-то похожее на MCAS. Я до сих пор не понял, как его предполагается делать эффективно, ведь MCAS нет на современной аппаратуте. Ну разве что использовать lock —
Не знаю, пошутил ты или нет, но самые производительные реализации STM сейчас как раз на основе fine-grained lock'ов.
RRM>Ну или коммит реализовывать как некий lock-free алгоритм, т.е. lock-free внутри другого lock-free
Такие тоже есть, но они на порядок более сложные.
R>>
R>>3) Сложность с транзакцоными переменными, ктр являются большимо сложными объектами.
R>>Затраты на создании копии сложного объекта (как память на хранение копии, так и время на копирование)
R>>Затраты на определения был ли реально этот объект изменен и нужно ли перрывать транзакцию
R>>Причем чем длинее транзакция тем сильнее будут проявляться проблемы
R>>Можешь пояснить на примерах, что ты имеешь в виду. Как я себе это сейчас вижу, при использовании STM/HTM не надо ничего особо копировать, можно просто внести изменения в старый объект. А все, кто его читает, атомарно увидит либо старую версию, либо новую.
RRM>Предположим, что транзакционная переменная не просто целое число, а действительно объект, ктр уже существует и не может быть изменен. Что будет если две транзакции будут в него одновременно писать? Тут вообще никаких гарантий нет, что он останется в согласованном состоянии. RRM>Если делать копии, то возникнет проблема атомарного сравнения двух копий объектов при коммите/валидации транзакции.
Копию делать не надо. Просто писать в старый объект. На то это и STM.
RRM>Даже если транзакционные переменные простые слова, я не до конца уверен, что можно обойтись без их копирования. Интуиция подсказывает, что нужно, но объяснить пока не могу. В любом случае, если этого не делать, то dirty-read возможен даже из тех переменных, куда мы только что записали
Копии слов действительно делаются, но несколько инструкций mov погоды не делают, они практически бесплатны.
STM Это вот это — http://en.wikipedia.org/wiki/Software_transactional_memory ?
R>Рассмотри следующую ситуацию. Есть большой список лицевых счетов. Над списком есть ряд операций, в т.ч. — проходить по всему спику и считать сумму всех балансов, и переводить сумму с одного л/с на другой. При реализации на основе STM и высокой нагрузке, как подсказывает логика и показывает практика, операции прохождения по списку *вообще* не проходят. Т.к. достаточно одной опрации модификации за время прохождения по *длинному* списку, что бы проход провалился.
с чего это он провалится, если в момент прохода мы имеем консистентные на 100% данные?
При чём тут не важно STM obstruction-free или lock-free — всё равно операциям прохода будет тотально "невезти". R>Как следствие, если разработчик оказывается в такой ситуации и слепо верит в STM/HTM и больше ничего не умеет, то он попадает в достаточно затруднительную ситуацию...
А здесь можно качнуть бенчмарк для различных реализаций STM: http://stamp.stanford.edu/
Правда придётся потрудиться, что скомпилировать его с другими реализациями кроме TL2-x86.
Abstract
Software transactional memory (STM) is a promising technique for
writing concurrent programs. So far, most STM approaches have
been experimentally evaluated with small-scale benchmarks. In
this paper, we present several surprising results from implementing
and experimenting with STMBench7 – a large scale benchmark for
STMs. First, all STMs we used crashed, at some point or another,
when running STMBench7. This was mainly due to memory management
limitations. This means that, in practice, none of the tested
STMs was truly unbounded and dynamic, which are the actual motivations
for moving away from hardware transactional memories
(HTM). Performance results we gathered also differ from previously
published results. We found, for instance, that conflict detection
and contention management have the biggest performance impact,
way more than other aspects, like the choice of lock-based or
obstruction-free implementation, as typically highlighted. Implementation
of STMBench7 with various STMs also revealed several
programming related issues such as the lack of support for external
libraries and only partial support for object oriented features.
These issues prove to be a major limitation when adapting STMs
for production use.
Это.
R>>Рассмотри следующую ситуацию. Есть большой список лицевых счетов. Над списком есть ряд операций, в т.ч. — проходить по всему спику и считать сумму всех балансов, и переводить сумму с одного л/с на другой. При реализации на основе STM и высокой нагрузке, как подсказывает логика и показывает практика, операции прохождения по списку *вообще* не проходят. Т.к. достаточно одной опрации модификации за время прохождения по *длинному* списку, что бы проход провалился.
КЛ>с чего это он провалится, если в момент прохода мы имеем консистентные на 100% данные?
Ты путаешь причину и следствие. Он не провалится, если мы имеем 100% консистентные данные. Но то, что мы их имеем не факт. Это будет факт только если STM реализована через один глобальный мьютекс. Тогда каждая операция будет 100% удаваться, но это определенно не то, что мы хотим.
