Comments 11
Работа хорошая, но есть вопросы:
1. Это сделано под конкретную задачу, или «вообще»?
2. Большой ли у вас опыт проектирования многопоточных/многопроцессных систем?
Почему спрашиваю. Сам в свое время наелся с многопоточкой. Потом уже столкнулся с многопроцессностью, но там было проще т.к. уже было базовое понимание где грабли разложены.
В итоге у меня лично сложилось убеждение, что надо всеми силами избегать ситуаций, которые вы пытаетесь разрулить в своей работе. Т.е. не должны несоколько потоков одновременно копаться в одном и том же списке. Наверное, где-то без этого никак не обойтись, но в тех реальных задачах, что вставали передо мной, всегда удавалось путем изначального проектирования этого избежать.
Иными словами, каждый поток или процесс работает со своим куском данных. Да, он может обмениваться данными с другими потоками, но это лишь некоторые результаты работы.
Например, для распараллеливания обработки больших объемов данных используется такой прием как batch машина. Суть в следующем — есть поток-раздающий (master). Он занимается предварительной обработкой данных (скажем, получение выборки из некоторого источника по некоторым условиям) и формирований заданий-пакетов для обработки. Есть потоки-обработчики (workers) — они однотипные (в общем случае) и занимаются обработкой пакетов, которые подготовил раздающий. Возможен еще один (или несколько) потоков-финишеров. Они складывают куда-то результаты обработки, ведут учет что обработано что нет и т.п. Иногда этим занимается тот же мастер (если его загрузка позволяет).
Теперь, собственно, о блокировках. Тут основная опасность — deadlock. Когда у вас несколько потоков работают с блокировками разделяемых ресурсов. Это ситуация, когда поток А ждет пока поток Б освободит ресурс, а поток Б ждет пока другой ресурс будет освобожден потоком С. Ну а поток С ждет пока поток А ему разрешит с ресурсом поработать… Все стоят и ждут друг друга. И никто ничего не делает в результате. Дедлоки могу проявляться совершенно спонтанно — на всех тестах отработало, а на проме встало. И не сразу, а через неделю-две. Пнули — отработало еще месяц. Или два. И опять встало. Ловить их тоже крайне сложно — под отладчиком может вообще не проявиться т.к. тайминги другие.
Вторая ситуация — что делать когда потоку А нужно обратиться к ресурсу, а он заблокирован потоком Б? Стоять и ждать? Или делать что-то еще? Тут вроде бы как все работает, но периодически провалы в производительности. Когда занимался системами с гарантированным временем отклика такое было недопустимо.
Все эти проблемы решаются во-первых, проектированием с использованием подходов, о которых писал выше, во-вторых, использованием для межпоточного/межпроцессного обмена системных каналов связи (каналов, доступ к которым регулируется системой).
Под Windows я в конечном итоге пришел к обмену через MailSlot Работает он в режиме датаграммы — посылки переменной длины. Плюс в том, что атомом здесь является вся посылка, это не потоковый протокол. Т.е. принимающая сторона увидит что в слоте что-то есть только когда там окажется целиком вся посылка. И прочитает всю посылку целиком. Если в слоте несколько посылок, то за одну операцию чтения читается ровно одна посылка — не надо думать где заканчивается следующая, где предыдущая.
Датаграмма имеет фиксированный заголовок и блок данных переменной длины. Минимум заголовка — размер блока данных. Также там может содержаться некоторый идентификатор, означающий что это такое (если возможны датаграммы разного содержания). Можно добавить еще что-то — например, идентификатор отправителя.
Если поток принимает разные форматы датаграмм, то делается набор обработчиков под каждый тип и все они сводятся в таблицу — код — адрес обработчика. Прочитав датаграмму поток смотрит код, находит в таблице адрес обработчика и передает датаграмму ему. А тот уже сам знает что с ней делать.
Каждый поток (или процесс) создает свой майлслот (входящая очередь данных) с предопределенным именем и все остальные могут туда писать. Все блокировки лежат на системе, этим можно не одумляться.
В никсах ближайший аналог — UnixSocket с типом DGRAM. С ним работается как с обычным UDP сокетом с той разницей, что вместо пары IP:Port там используется имя (как имя файла).
Сейчас работаю на платформе AS/400 — там еще удобнее. Есть «очереди данных» — Data Queue и User Queue. Удобнее тем, что очередь перманентна (т.е. создал ее и она живет вне зависимости от состояния процесса, ее создавшего) и писать-читать туда может кто угодно (в слоты и сокеты пишут все, но читать может только создавший их процесс). Система мастер-обработчики реализуется на одной очереди — мастер пишет туда, обработчики разбирают оттуда.
Такой подход (на моем обпыте) прост в реализации и стабилен в работе. Никаких проблем с блокировками, никаких задержек при чтении-записи, никаких дедлоков.
Все это не критика, просто поделился опытом.
1. Это сделано под конкретную задачу, или «вообще»?
2. Большой ли у вас опыт проектирования многопоточных/многопроцессных систем?
Почему спрашиваю. Сам в свое время наелся с многопоточкой. Потом уже столкнулся с многопроцессностью, но там было проще т.к. уже было базовое понимание где грабли разложены.
В итоге у меня лично сложилось убеждение, что надо всеми силами избегать ситуаций, которые вы пытаетесь разрулить в своей работе. Т.е. не должны несоколько потоков одновременно копаться в одном и том же списке. Наверное, где-то без этого никак не обойтись, но в тех реальных задачах, что вставали передо мной, всегда удавалось путем изначального проектирования этого избежать.
Иными словами, каждый поток или процесс работает со своим куском данных. Да, он может обмениваться данными с другими потоками, но это лишь некоторые результаты работы.
Например, для распараллеливания обработки больших объемов данных используется такой прием как batch машина. Суть в следующем — есть поток-раздающий (master). Он занимается предварительной обработкой данных (скажем, получение выборки из некоторого источника по некоторым условиям) и формирований заданий-пакетов для обработки. Есть потоки-обработчики (workers) — они однотипные (в общем случае) и занимаются обработкой пакетов, которые подготовил раздающий. Возможен еще один (или несколько) потоков-финишеров. Они складывают куда-то результаты обработки, ведут учет что обработано что нет и т.п. Иногда этим занимается тот же мастер (если его загрузка позволяет).
Теперь, собственно, о блокировках. Тут основная опасность — deadlock. Когда у вас несколько потоков работают с блокировками разделяемых ресурсов. Это ситуация, когда поток А ждет пока поток Б освободит ресурс, а поток Б ждет пока другой ресурс будет освобожден потоком С. Ну а поток С ждет пока поток А ему разрешит с ресурсом поработать… Все стоят и ждут друг друга. И никто ничего не делает в результате. Дедлоки могу проявляться совершенно спонтанно — на всех тестах отработало, а на проме встало. И не сразу, а через неделю-две. Пнули — отработало еще месяц. Или два. И опять встало. Ловить их тоже крайне сложно — под отладчиком может вообще не проявиться т.к. тайминги другие.
Вторая ситуация — что делать когда потоку А нужно обратиться к ресурсу, а он заблокирован потоком Б? Стоять и ждать? Или делать что-то еще? Тут вроде бы как все работает, но периодически провалы в производительности. Когда занимался системами с гарантированным временем отклика такое было недопустимо.
Все эти проблемы решаются во-первых, проектированием с использованием подходов, о которых писал выше, во-вторых, использованием для межпоточного/межпроцессного обмена системных каналов связи (каналов, доступ к которым регулируется системой).
Под Windows я в конечном итоге пришел к обмену через MailSlot Работает он в режиме датаграммы — посылки переменной длины. Плюс в том, что атомом здесь является вся посылка, это не потоковый протокол. Т.е. принимающая сторона увидит что в слоте что-то есть только когда там окажется целиком вся посылка. И прочитает всю посылку целиком. Если в слоте несколько посылок, то за одну операцию чтения читается ровно одна посылка — не надо думать где заканчивается следующая, где предыдущая.
Датаграмма имеет фиксированный заголовок и блок данных переменной длины. Минимум заголовка — размер блока данных. Также там может содержаться некоторый идентификатор, означающий что это такое (если возможны датаграммы разного содержания). Можно добавить еще что-то — например, идентификатор отправителя.
Если поток принимает разные форматы датаграмм, то делается набор обработчиков под каждый тип и все они сводятся в таблицу — код — адрес обработчика. Прочитав датаграмму поток смотрит код, находит в таблице адрес обработчика и передает датаграмму ему. А тот уже сам знает что с ней делать.
Каждый поток (или процесс) создает свой майлслот (входящая очередь данных) с предопределенным именем и все остальные могут туда писать. Все блокировки лежат на системе, этим можно не одумляться.
В никсах ближайший аналог — UnixSocket с типом DGRAM. С ним работается как с обычным UDP сокетом с той разницей, что вместо пары IP:Port там используется имя (как имя файла).
Сейчас работаю на платформе AS/400 — там еще удобнее. Есть «очереди данных» — Data Queue и User Queue. Удобнее тем, что очередь перманентна (т.е. создал ее и она живет вне зависимости от состояния процесса, ее создавшего) и писать-читать туда может кто угодно (в слоты и сокеты пишут все, но читать может только создавший их процесс). Система мастер-обработчики реализуется на одной очереди — мастер пишет туда, обработчики разбирают оттуда.
Такой подход (на моем обпыте) прост в реализации и стабилен в работе. Никаких проблем с блокировками, никаких задержек при чтении-записи, никаких дедлоков.
Все это не критика, просто поделился опытом.
Спасибо за Ваш интерес и за то, что так развёрнуто поделились опытом.
«В итоге у меня лично сложилось убеждение, что надо всеми силами избегать ситуаций, которые вы пытаетесь разрулить в своей работе. Т.е. не должны несоколько потоков одновременно копаться в одном и том же списке. Наверное, где-то без этого никак не обойтись, но в тех реальных задачах, что вставали передо мной, всегда удавалось путем изначального проектирования этого избежать».
Вы совершенно правы! Вопрос проектирования здесь ключевой в любом случае! Если можно избежать сложностей, разбить задачу на какие-то независимые части и реализовать как-то по-другому, то именно так и надо делать! Я же в своей работе исхожу из предположения: «Ну, предположим, что мне очень надо сделать именно так! Все другие решения оказались по тем или иным причинам хуже или менее подходящими. Можно ли что-то сделать в этой ситуации?» Всё, что предоставляет мой вариант этой известной структуры данных — это хоть какие-то гарантии, что программа по крайней мере не сломается, даст возможность отреагировать на ошибочную ситуацию, а также то, что работу со списком можно сделать хотя бы относительно быстрой. Все вопросы же насчёт ошибочных ситуаций и накладных расходов опять же ложатся на плечи того, кто проектирует программу, так что опять всё сводится к Вашему же исходному тезису.
Конкретно по вопросам:
1. Началось всё с конкретного практического примера, а потом я задумался, что можно сделать тут вообще.
2. Нет, опыт не очень большой, к сожалению.
«В итоге у меня лично сложилось убеждение, что надо всеми силами избегать ситуаций, которые вы пытаетесь разрулить в своей работе. Т.е. не должны несоколько потоков одновременно копаться в одном и том же списке. Наверное, где-то без этого никак не обойтись, но в тех реальных задачах, что вставали передо мной, всегда удавалось путем изначального проектирования этого избежать».
Вы совершенно правы! Вопрос проектирования здесь ключевой в любом случае! Если можно избежать сложностей, разбить задачу на какие-то независимые части и реализовать как-то по-другому, то именно так и надо делать! Я же в своей работе исхожу из предположения: «Ну, предположим, что мне очень надо сделать именно так! Все другие решения оказались по тем или иным причинам хуже или менее подходящими. Можно ли что-то сделать в этой ситуации?» Всё, что предоставляет мой вариант этой известной структуры данных — это хоть какие-то гарантии, что программа по крайней мере не сломается, даст возможность отреагировать на ошибочную ситуацию, а также то, что работу со списком можно сделать хотя бы относительно быстрой. Все вопросы же насчёт ошибочных ситуаций и накладных расходов опять же ложатся на плечи того, кто проектирует программу, так что опять всё сводится к Вашему же исходному тезису.
Конкретно по вопросам:
1. Началось всё с конкретного практического примера, а потом я задумался, что можно сделать тут вообще.
2. Нет, опыт не очень большой, к сожалению.
Просто расскажу свой опыт
На прошлой работе делали систему мониторинга инженерного оборудования зданий. С одной стороны свое железо, к которому цепляются всякие устройства, с другой стороны свой же софт.
Не реалтайм (задач не стояло), но гарантированное время отклика соблюдали.
Вкратце — с одной стороны 20-30 контроллеров верхнего уровня, которые разбросаны по всему городу, с другой стороны 3-5 интерфейсных клиентов (они где угодно могут быть).
Между ними микроядро. Обеспечивает отношение «многое-ко-многим» во-первых, занимается маршрутизацией посылок во-вторых ну делает некоторую предварительную их обработку в-третьих.
Микроядром занимался я. Там сразу было понятно — 3 основных потока (вообще-то, их было 5, но два вспомогательных, они мало что делали, больше следили за остальными). Поток IP-шлюзов (работает с контроллерами верхнего уровня по UDP протоколу — прием/отсылка сообщений, контроль сообщения на приеме, квитирование), поток клиентов (TCP сервер и работа с подключившимися клиентами по TCP протоколу) и поток обработки данных.
Поначалу была разработана красивая концепция с двумя конвеерами по которым данные двигаются от UDP к TCP (или обратно) претерпевая по дороге нужные трансформации.
даже реализовал ее. С блокировками и прочим. А потом уперся в то, что временами оно работает быстро, а временами притормаживать начинает (потоки пержимают друг другу кислород). Пару раз встал в дедлок.
В результате забил на все это и сделал на майлслотах, как описал выше. У каждого потока есть входной слот в который кидаются нужные данные. И все заработало очень стабильно и надежно. И по коду проще и прозрачнее.
На теперешней работе больше распараллеливание обработки. Там совсем просто — очередь заданий и очередь результатов. Обе сделаны на UserQueue. Задача-мастер (тут используются задания, JOB, posix threads есть, но сопровождение их не любит т.к. сложно контролировать, в отличие от задач) складывает задания в очередь заданий, обработчики их оттуда разбирают. Результаты обработки складывают в очередь результатов, откуда их забирает мастер.
На прошлой работе делали систему мониторинга инженерного оборудования зданий. С одной стороны свое железо, к которому цепляются всякие устройства, с другой стороны свой же софт.
Не реалтайм (задач не стояло), но гарантированное время отклика соблюдали.
Вкратце — с одной стороны 20-30 контроллеров верхнего уровня, которые разбросаны по всему городу, с другой стороны 3-5 интерфейсных клиентов (они где угодно могут быть).
Между ними микроядро. Обеспечивает отношение «многое-ко-многим» во-первых, занимается маршрутизацией посылок во-вторых ну делает некоторую предварительную их обработку в-третьих.
Микроядром занимался я. Там сразу было понятно — 3 основных потока (вообще-то, их было 5, но два вспомогательных, они мало что делали, больше следили за остальными). Поток IP-шлюзов (работает с контроллерами верхнего уровня по UDP протоколу — прием/отсылка сообщений, контроль сообщения на приеме, квитирование), поток клиентов (TCP сервер и работа с подключившимися клиентами по TCP протоколу) и поток обработки данных.
Поначалу была разработана красивая концепция с двумя конвеерами по которым данные двигаются от UDP к TCP (или обратно) претерпевая по дороге нужные трансформации.
даже реализовал ее. С блокировками и прочим. А потом уперся в то, что временами оно работает быстро, а временами притормаживать начинает (потоки пержимают друг другу кислород). Пару раз встал в дедлок.
В результате забил на все это и сделал на майлслотах, как описал выше. У каждого потока есть входной слот в который кидаются нужные данные. И все заработало очень стабильно и надежно. И по коду проще и прозрачнее.
На теперешней работе больше распараллеливание обработки. Там совсем просто — очередь заданий и очередь результатов. Обе сделаны на UserQueue. Задача-мастер (тут используются задания, JOB, posix threads есть, но сопровождение их не любит т.к. сложно контролировать, в отличие от задач) складывает задания в очередь заданий, обработчики их оттуда разбирают. Результаты обработки складывают в очередь результатов, откуда их забирает мастер.
Если Вам интересна производительность многопоточных структур данных — советую посмотреть в сторону lock-free/wait-free программирования. На mutex'ах/srwlock'ах быстрые структуры не получаются.
Зашёл посмотреть на параллельную работу со списком, а тут какой-то сюр: и список — какая-то извращённая хештаблица (почему бы её и не использовать?), и параллельности нет, а о сопутствующей ей скорости тоже говорить не приходиться (тестов: однопоточная очередь + транзакции, не увидел).
Что касается общей идеи, то вы натягиваете сову на глобус, я бы сделал что-то вроде двоичного дерева и очередь из блокировок, куда бы писал путь до элемента. А сравнивая свой путь и пути к заблокированным ресурсам можно решить, пересекаются ли данные или совсем в разных ветках и можно безнаказанно менять. Вот тут, скорее всего, была бы возможно и параллельная работа (проблемы бы начались при балансировании высоты дерева, но концепция должна быть рабочей). И да, всё уже придумано до меня и наверняка по этой теме, есть ключевые слова и проработанный алгоритм, я — не искал.
Что касается общей идеи, то вы натягиваете сову на глобус, я бы сделал что-то вроде двоичного дерева и очередь из блокировок, куда бы писал путь до элемента. А сравнивая свой путь и пути к заблокированным ресурсам можно решить, пересекаются ли данные или совсем в разных ветках и можно безнаказанно менять. Вот тут, скорее всего, была бы возможно и параллельная работа (проблемы бы начались при балансировании высоты дерева, но концепция должна быть рабочей). И да, всё уже придумано до меня и наверняка по этой теме, есть ключевые слова и проработанный алгоритм, я — не искал.
«и список — какая-то извращённая хештаблица (почему бы её и не использовать?)»
Список здесь так и остался списком, а извращённая, как Вы выразились, хештаблица идёт в довесок. Эту извращённую хештаблицу можно также к другим структурам пристроить: например, к дереву или графу.
«и параллельности нет, а о сопутствующей ей скорости тоже говорить не приходиться (тестов: однопоточная очередь + транзакции, не увидел)»
Параллельности в прямом смысле — нет, т.к. идёт блокировка. Но есть многопоточность, т.к. идёт речь об организации доступа к общей структуре данных из разных потоков. В этом смысле параллельность. Сравнения с другими подходами действительно нет, и тестов, соответственно, тоже: я описывал пока только свою идею.
«Что касается общей идеи, то вы натягиваете сову на глобус»
Идея-то как раз-то предельно простая и незамысловатая. Я даже не знаю, можно ли вообще придумать на эту тему что-нибудь ещё проще. Да, у неё есть свои недостатки, но идеального ничего не бывает, особенно в таком непростом вопросе. Основной минус в том, что, как там выше указали, блокировки серьёзно ухудшают производительность. С этим спорить не буду. Если те, другие, подходы лучше во всех отношениях, ну… что поделаешь. Бывает. Но если им тоже свойственны какие-то ограничения, недостатки или тонкие моменты, может, эта работа сможет занять свою нишу в практических приложениях. Трудно пока сказать.
Меня больше всего смущало, что этим простым и незамысловатом путём уже давно прошли, а я ничего об этом не знаю и ничего нового, соответственно, не сказал. Ну что ж, в таком случае хотя бы просто поупражнялся в навыках языка и создания структур данных. Тоже полезно бывает. Пригодится, если понадобится создавать что-нибудь более специализированное под конкретную задачу.
«Зашёл посмотреть на параллельную работу со списком, а тут какой-то сюр».
Бывает, что встречаются оригинальные и необщепринятые идеи и подходы, даже если не совсем удачные. Привыкайте. :)
Список здесь так и остался списком, а извращённая, как Вы выразились, хештаблица идёт в довесок. Эту извращённую хештаблицу можно также к другим структурам пристроить: например, к дереву или графу.
«и параллельности нет, а о сопутствующей ей скорости тоже говорить не приходиться (тестов: однопоточная очередь + транзакции, не увидел)»
Параллельности в прямом смысле — нет, т.к. идёт блокировка. Но есть многопоточность, т.к. идёт речь об организации доступа к общей структуре данных из разных потоков. В этом смысле параллельность. Сравнения с другими подходами действительно нет, и тестов, соответственно, тоже: я описывал пока только свою идею.
«Что касается общей идеи, то вы натягиваете сову на глобус»
Идея-то как раз-то предельно простая и незамысловатая. Я даже не знаю, можно ли вообще придумать на эту тему что-нибудь ещё проще. Да, у неё есть свои недостатки, но идеального ничего не бывает, особенно в таком непростом вопросе. Основной минус в том, что, как там выше указали, блокировки серьёзно ухудшают производительность. С этим спорить не буду. Если те, другие, подходы лучше во всех отношениях, ну… что поделаешь. Бывает. Но если им тоже свойственны какие-то ограничения, недостатки или тонкие моменты, может, эта работа сможет занять свою нишу в практических приложениях. Трудно пока сказать.
Меня больше всего смущало, что этим простым и незамысловатом путём уже давно прошли, а я ничего об этом не знаю и ничего нового, соответственно, не сказал. Ну что ж, в таком случае хотя бы просто поупражнялся в навыках языка и создания структур данных. Тоже полезно бывает. Пригодится, если понадобится создавать что-нибудь более специализированное под конкретную задачу.
«Зашёл посмотреть на параллельную работу со списком, а тут какой-то сюр».
Бывает, что встречаются оригинальные и необщепринятые идеи и подходы, даже если не совсем удачные. Привыкайте. :)
Ни разу не было необходимости в таком списке, и сложно представить практический случай. Думаю всегда можно найти более простые подходы.
Вообще, согласен. Именно потому приводил тут свои примеры когда вроде бы изначально кажется что нужен совместный доступ к данным из нескольких потоков, но потом оказывается, что можно так спроектировать разделение функционала потоков, что этот доступ, как таковой, уже и не нужен — вполне достаточно обычного обмена данными между потоками. А это уже намного более простая задача.
Что касается практического применения… Ну тут одному человеку сложно судить о всем многообразии практических задач. Не исключено, что где-то это реально может потребоваться. Но, как тут правильно сказали, там, где это реально нужно, стоит смотреть в сторону lockfree решений.
Но в совместном доступе основная проблема на мой взгляд не техническая, а логическая. Например, поток 1 изменяет элемент А. А поток 2 в это же время его удаляет. Оба потока действуют в рамках своей логики. Но что делать в том случае, когда поток 1 обнаруживает что измененный им элемент удален другим потоком? Повторюсь, не технически, а логически.
Следует ли понимать, что то процессорное время, которое потрачено потоком 1 на изменение элемента А, потрачено впустую? Т.е. налицо потеря производительности. Или тут возникает конфликт логик потоков 1 и 2 — в рамках логики 1 элемент А должен быть изменен, а в рамках логики 2 он должен быть удален. И как все это скажется на целостности данных в целом?
Или вот другой вариант. Поток 1 берет элемент А и начинает на его основе производить какие-то вычисления. А в это время поток 2 тоже производит некоторые вычисления, в результате которых данные элемента А обновляются. Т.е. все, что делал поток 1 на основе старого значения А уже неправильно. Но он про то не знает… И где-то на выходе возникает неправильный результат.
Иными словами, решение этой задачи снизу подразумевает очень много архитектурных вопросов сверху.
Что касается практического применения… Ну тут одному человеку сложно судить о всем многообразии практических задач. Не исключено, что где-то это реально может потребоваться. Но, как тут правильно сказали, там, где это реально нужно, стоит смотреть в сторону lockfree решений.
Но в совместном доступе основная проблема на мой взгляд не техническая, а логическая. Например, поток 1 изменяет элемент А. А поток 2 в это же время его удаляет. Оба потока действуют в рамках своей логики. Но что делать в том случае, когда поток 1 обнаруживает что измененный им элемент удален другим потоком? Повторюсь, не технически, а логически.
Следует ли понимать, что то процессорное время, которое потрачено потоком 1 на изменение элемента А, потрачено впустую? Т.е. налицо потеря производительности. Или тут возникает конфликт логик потоков 1 и 2 — в рамках логики 1 элемент А должен быть изменен, а в рамках логики 2 он должен быть удален. И как все это скажется на целостности данных в целом?
Или вот другой вариант. Поток 1 берет элемент А и начинает на его основе производить какие-то вычисления. А в это время поток 2 тоже производит некоторые вычисления, в результате которых данные элемента А обновляются. Т.е. все, что делал поток 1 на основе старого значения А уже неправильно. Но он про то не знает… И где-то на выходе возникает неправильный результат.
Иными словами, решение этой задачи снизу подразумевает очень много архитектурных вопросов сверху.
Или вот другой вариант. Поток 1 берет элемент А и начинает на его основе производить какие-то вычисления. А в это время поток 2 тоже производит некоторые вычисления, в результате которых данные элемента А обновляются. Т.е. все, что делал поток 1 на основе старого значения А уже неправильно. Но он про то не знает… И где-то на выходе возникает неправильный результат.
Я вам уже писал об этом, тут нужны не блокировки элементов на время записи, а транзакции, которые как раз и поддерживают логическую целостность операций в самом широком смысле.
Возьмите однопоточную очередь и вы столкнётесь ровно с тем же, в какой-то момент очередь станет не валидной, потому что на момент помещения в очередь, все элементы были, а когда до них дошло дело, таких уже нет и дело тут не в блокировках, а в том, что некоторые действия должны идти неразрывной группой, это называется транзакциями.
Я имел ввиду несколько иное.
Нисколько не умаляя проделанную работу — сделано серьезно, возможно где-то слишком навороченно, возможно можно переосмыслить, упростить и оптимизировать, но в целом подход хороший.
Но я все-таки о другом. В пытаетесь решить проблемы, я недаром привел свой пример — сначала шел вашим путем и пытался разруливать проблемы синхронизации в процессе кодирования. Потом нашел себе мужество откатиться к началу (а это означало переписывание значительной части кода) и подойти к вопросу с другой стороны. И выяснилось, что все эти героические преодоления в новой постановке задачи просто не нужны. И код стал проще и архитектура его прозрачнее. И, что самое главное, работать все это стало в среднем быстрее. В моменте может быть чуть медленнее, но полностью исчезли периодически возникающие лаги, которые в нашей задаче (гарантированное время отклика) были недопустимы.
Вашу мысль с транзакциями я понял. Но я говорил вот о чем — два потока работают с одной областью списка. Каждый в своей транзакции. Поток 1 делает какие-то вычисления, базирующиеся на текущих (на момент начала транзакции) значениях элементов A, B и C.
В тоже время, поток 2 в другой транзакции, делает иные вычисления, которые приводят к изменению значений элементов B, C и D.
Далее, когда поток 1 закончил вычисления и закрывает транзакцию, он обнаруживает, что значения элементов B и C изменены потоком 2. Т.е. все, что он делал последние хххх тактов процессора стало неактуальным — надо все начинать сначала. И не факт что такая ситуация не возникнет снова — "пока противник рисует карты, мы меняем рельеф местности" (с)
На прошлой работе я долго занимался разработкой систем с гарантированным временем отклика. Миллисекундные таймауты были нормой.
Сейчас я работаю с высоконагруженной системой. Тысячи одновременно работающих процессов, порядка 3млрд изменений БД в сутки (это только изменений, чтений как минимум на порядок больше). Все это работает на кластере из трех серверов. На каждом 16 12-ядерных SMT8 процессоров (1536 параллельных вычислительных потоков) и 2.5ТБ оперативки. И эта система в пике бывает загружена на >90%.
Любая фоновая задача перед внедрением проходит нагрузочное тестирование. И сопровождение постоянно твердит — «пишите эффективно, экономьте ресурсы процессора. Мы можем докупить памяти, мы можем расширить SSD дисковые массивы, но увеличить количество процессоров мы не можем — это предел».
И у нас есть целый пул задач на оптимизацию. Т.е. регулярно проводятся аудиты, выявляются наиболее загруженные места и выносятся на переработку с целью повышения оптимизации.
К чему все это? А к тому, что ваш подход (совместная работа с одним набором элементов) неизбежно приводит к коллизиям, которые надо разрешать. А разрешение любой коллизии это ресурсы процессора.
Я не к тому что ваша работа бесполезна. Наверняка где-то когда-то возникнет ситуация где иначе невозможно. Я к тому, что при проектировании не стоит расслабляться «у меня есть замечательный конкурентный список, буду использовать его». Надо подумать, а можно ли спроектировать задачу так, чтобы его не использовать.
Поверьте — опыт, это не знание как надо. Это образование. Опыт это понимание как не надо.
Нисколько не умаляя проделанную работу — сделано серьезно, возможно где-то слишком навороченно, возможно можно переосмыслить, упростить и оптимизировать, но в целом подход хороший.
Но я все-таки о другом. В пытаетесь решить проблемы, я недаром привел свой пример — сначала шел вашим путем и пытался разруливать проблемы синхронизации в процессе кодирования. Потом нашел себе мужество откатиться к началу (а это означало переписывание значительной части кода) и подойти к вопросу с другой стороны. И выяснилось, что все эти героические преодоления в новой постановке задачи просто не нужны. И код стал проще и архитектура его прозрачнее. И, что самое главное, работать все это стало в среднем быстрее. В моменте может быть чуть медленнее, но полностью исчезли периодически возникающие лаги, которые в нашей задаче (гарантированное время отклика) были недопустимы.
Вашу мысль с транзакциями я понял. Но я говорил вот о чем — два потока работают с одной областью списка. Каждый в своей транзакции. Поток 1 делает какие-то вычисления, базирующиеся на текущих (на момент начала транзакции) значениях элементов A, B и C.
В тоже время, поток 2 в другой транзакции, делает иные вычисления, которые приводят к изменению значений элементов B, C и D.
Далее, когда поток 1 закончил вычисления и закрывает транзакцию, он обнаруживает, что значения элементов B и C изменены потоком 2. Т.е. все, что он делал последние хххх тактов процессора стало неактуальным — надо все начинать сначала. И не факт что такая ситуация не возникнет снова — "пока противник рисует карты, мы меняем рельеф местности" (с)
На прошлой работе я долго занимался разработкой систем с гарантированным временем отклика. Миллисекундные таймауты были нормой.
Сейчас я работаю с высоконагруженной системой. Тысячи одновременно работающих процессов, порядка 3млрд изменений БД в сутки (это только изменений, чтений как минимум на порядок больше). Все это работает на кластере из трех серверов. На каждом 16 12-ядерных SMT8 процессоров (1536 параллельных вычислительных потоков) и 2.5ТБ оперативки. И эта система в пике бывает загружена на >90%.
Любая фоновая задача перед внедрением проходит нагрузочное тестирование. И сопровождение постоянно твердит — «пишите эффективно, экономьте ресурсы процессора. Мы можем докупить памяти, мы можем расширить SSD дисковые массивы, но увеличить количество процессоров мы не можем — это предел».
И у нас есть целый пул задач на оптимизацию. Т.е. регулярно проводятся аудиты, выявляются наиболее загруженные места и выносятся на переработку с целью повышения оптимизации.
К чему все это? А к тому, что ваш подход (совместная работа с одним набором элементов) неизбежно приводит к коллизиям, которые надо разрешать. А разрешение любой коллизии это ресурсы процессора.
Я не к тому что ваша работа бесполезна. Наверняка где-то когда-то возникнет ситуация где иначе невозможно. Я к тому, что при проектировании не стоит расслабляться «у меня есть замечательный конкурентный список, буду использовать его». Надо подумать, а можно ли спроектировать задачу так, чтобы его не использовать.
Поверьте — опыт, это не знание как надо. Это образование. Опыт это понимание как не надо.
Sign up to leave a comment.
Многопоточный линейный список: проблема существования элемента, повышение производительности и соотношение с STL