Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Легковесные последовательные подзадачи с возможностью блокировки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
Подскажите, куда копать.

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

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

Использование потоков - крайне затратная конструкция в данном случае.
Общее число задач, исполняемых друг за другом - от одного до двух десятков.
В среднем за секунду исполняется от 30к до 1м задач.

=//=
13 фев 19, 13:54    [21808434]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Пул из N потоков создаешь при старте и дальше выполняй свои задачи в них.

Если задачи чисто вычислительные, то N равно количеству ядер проца, иначе N подбери опытным путем.

На каком ЯП написано? Нет смысла рассматривать эту задачу обобщенно, в разных ЯП разные инструменты для распараллеливания.
13 фев 19, 14:04    [21808449]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
Dima T
Пул из N потоков создаешь при старте и дальше выполняй свои задачи в них.

Если задачи чисто вычислительные, то N равно количеству ядер проца, иначе N подбери опытным путем.

На каком ЯП написано? Нет смысла рассматривать эту задачу обобщенно, в разных ЯП разные инструменты для распараллеливания.
Пул потоков не пойдет, потому что после полного цикла задач ABCDEF...Z перед повтором круга нужна полная синхронизация. А редко нужна и последовательная синхронизация, чтобы задачи A->B->C->... и только в таком порядке.

При скорости исполнения с 100к задач в секунду будет скажем 30к синхронизаций в секунду, пул потоков такое не вытянет.

С++, win/lin 86/64
13 фев 19, 14:17    [21808473]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 18845
Задача должна иметь свойство, устанавливающее, что она заблокирована. Соответственно проверять на входе, и если блок - то сразу выход, а если нет, то выполняется. И соответственно она должна сама "вести" свой счётчик-свойство, буде надо. В общем, она должна быть самодостаточной.
Само собой, должен быть некий диспетчер, который запускает некую задачу, ждёт её завершения, после чего запускает следующую по циклу задачу. Вероятно, также с аналогичным свойством, блокирование коего аналогично блокированию сразу всех задач. Что он при этом будет делать - ждать разблокировки и продолжать, или завершаться - также может быть определено присвоенным этому свойству значением.
13 фев 19, 14:18    [21808476]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 18845
Aklin
перед повтором круга нужна полная синхронизация
Т.е. если какая задача была заблокирована, новый цикл не должен начинаться до тех пор, пока все блокированные в этом цикле задачи не будут разблокированы и выполнены? да в общем не влияет... ну немножко другой алгоритм в диспетчере.
13 фев 19, 14:21    [21808480]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
Akina
Aklin
перед повтором круга нужна полная синхронизация
Т.е. если какая задача была заблокирована, новый цикл не должен начинаться до тех пор, пока все блокированные в этом цикле задачи не будут разблокированы и выполнены? да в общем не влияет... ну немножко другой алгоритм в диспетчере.
Нет.

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


Akina
Задача должна иметь свойство, устанавливающее, что она заблокирована. Соответственно проверять на входе, и если блок - то сразу выход, а если нет, то выполняется. И соответственно она должна сама "вести" свой счётчик-свойство, буде надо. В общем, она должна быть самодостаточной.
Само собой, должен быть некий диспетчер, который запускает некую задачу, ждёт её завершения, после чего запускает следующую по циклу задачу. Вероятно, также с аналогичным свойством, блокирование коего аналогично блокированию сразу всех задач. Что он при этом будет делать - ждать разблокировки и продолжать, или завершаться - также может быть определено присвоенным этому свойству значением.
Сейчас так примерно и сделано.
Проблема началась с того, что основная функция задачи начинает дергать функции ресурсов, при этом может уйти в глубину на 20-30 вызовов и где-то там в конце заблокироваться.

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

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


Читаю пока про буст-корутины, буду пробовать, не могу сказать то ли это что нужно или не совсем...
13 фев 19, 14:34    [21808508]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47390
Aklin
При скорости исполнения с 100к задач в секунду будет скажем 30к синхронизаций в секунду, пул потоков такое не вытянет.

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

Не знаю что ты называешь "полной синхронизацией", но всё решается недобавлением задачи Х в очередь пока задача У не прислала квиток о своём выполнении.
13 фев 19, 14:42    [21808524]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
alex55555
Member

Откуда:
Сообщений: 2095
Aklin
Проблема в том, что в некий момент времени каждая задача может быть заблокирована на неопределенное время в определенном месте исполнения программы. А после снятия блокировки должна продолжить работу с того же места.
Сейчас это реализовано в виде нескольких функций, и счетчика. Блокируется переход с функции на функцию, а после снятия блокировки исполнение идет со следующей в списке функции.
Пока количество блокировок было мало, тащить этот зоопарк было просто. Сейчас же число блокировок начинает расти.

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

Откуда такие данные?
Aklin
Общее число задач, исполняемых друг за другом - от одного до двух десятков.
В среднем за секунду исполняется от 30к до 1м задач.

Сколько там в очереди на последовательную обработку - не интересно. Интереснее сколько очередей. Их не более 20. То есть нужно как-то планировать исполнение не более 20 потоков. Ну и в чём проблема-то? Оно даже уже реализовано, оно работает, но что-то не устраивает, только вот сформулировать не получается. Поэтому нужно терзать вопросами до появления понимания - чего, собственно, не нравится-то?
13 фев 19, 14:45    [21808527]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
Dimitry Sibiryakov
Aklin
При скорости исполнения с 100к задач в секунду будет скажем 30к синхронизаций в секунду, пул потоков такое не вытянет.

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

Не знаю что ты называешь "полной синхронизацией", но всё решается недобавлением задачи Х в очередь пока задача У не прислала квиток о своём выполнении.
Я понял.
Думал речь идет про ОС-потоки.


Сейчас по сути так и сделано.
Есть список активных задач, который просто по кругу вращается.
Проблема вот в чем.
Задача начинает дергать функции ресурсов, порой на глубину в 20-30 вызовов и где-то там может быть заблокирована. Вернуться в основной цикл и передать управление на следующей в списке задаче несложно.
Сложно продолжить исполнение с той точки, где произошла блокировка. Приходится вводить множество различных счетчиков состояний чуть ли не на каждом уровне вызова, а потом еще не запутаться в них (состояние еще будет зависеть от вызывающего и т.д.).
13 фев 19, 14:45    [21808529]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
alex55555
Сколько там в очереди на последовательную обработку - не интересно. Интереснее сколько очередей. Их не более 20. То есть нужно как-то планировать исполнение не более 20 потоков. Ну и в чём проблема-то? Оно даже уже реализовано, оно работает, но что-то не устраивает, только вот сформулировать не получается. Поэтому нужно терзать вопросами до появления понимания - чего, собственно, не нравится-то?
Потоков каких - ОС-потоков?
13 фев 19, 14:49    [21808535]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 18845
Aklin
Сначала доходим до конца цикла, дожидаемся все незаблокированные задачи
не понял, как это соотносится с исходным
Aklin
ряд задач, выполняются они последовательно

Я понимаю "последовательно" так, что только по завершении задача возвращает упраление диспетчеру, который запустит следующую... я неправ?
Aklin
основная функция задачи начинает дергать функции ресурсов, при этом может уйти в глубину на 20-30 вызовов
?? задачи вызывают друг друга? что за ресурсы, откуда цепной вызов? или рекурсия, что один хрен...
13 фев 19, 15:22    [21808580]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Aklin
Dima T
Пул из N потоков создаешь при старте и дальше выполняй свои задачи в них.

Если задачи чисто вычислительные, то N равно количеству ядер проца, иначе N подбери опытным путем.

На каком ЯП написано? Нет смысла рассматривать эту задачу обобщенно, в разных ЯП разные инструменты для распараллеливания.
Пул потоков не пойдет, потому что после полного цикла задач ABCDEF...Z перед повтором круга нужна полная синхронизация. А редко нужна и последовательная синхронизация, чтобы задачи A->B->C->... и только в таком порядке.

При скорости исполнения с 100к задач в секунду будет скажем 30к синхронизаций в секунду, пул потоков такое не вытянет.

С++, win/lin 86/64

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

Но подозреваю что это решение тебе не подойдет, т.к. (если я правильно понял) сейчас у тебя все сделано однопоточно, следовательно скорее всего код не потокобезопасный, т.е. переделка на многопоточный вариант будет достаточно трудоемкой.
13 фев 19, 15:40    [21808609]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Aklin
Задача начинает дергать функции ресурсов, порой на глубину в 20-30 вызовов и где-то там может быть заблокирована. Вернуться в основной цикл и передать управление на следующей в списке задаче несложно.

Я правильно понимаю что есть цепочки задач с подзадачами например:
1. A()->B()->C()
2. D()->E()
Допустим первая "зависла" на вызове С и ты в этот момент хочешь вернуться в основной цикл и запустить вторую, потом закончить первую?
13 фев 19, 15:44    [21808618]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Aklin
В среднем за секунду исполняется от 30к до 1м задач.

При одном миллионе задач в секунду у нас длительность одного сеанса задачи = 1мс.
Это та самая граница где КМК надо уходить от мультизадачности в другую сторону.
Сабж у нас был на эту тему.
13 фев 19, 15:53    [21808626]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
Akina
Aklin
?? задачи вызывают друг друга? что за ресурсы, откуда цепной вызов? или рекурсия, что один хрен...
Задачи не вызывают друг друга.
Задачи могут дергать одни и те же ресурсы.
После завершения или блокировки задачи управление возвращается в диспетчер.
После разблокировки задачи надо продолжить с того же места, на котором задача встала, включая всю иерархию стеков.

Dima T
Я правильно понимаю что есть цепочки задач с подзадачами например:
1. A()->B()->C()
2. D()->E()
Допустим первая "зависла" на вызове С и ты в этот момент хочешь вернуться в основной цикл и запустить вторую, потом закончить первую?

ABCDE - задачи, abcde - ресурсы.

Нормальное исполнение (с учетом ресурсов) будет примерно такое:
(SCHEDULER) -> A(a(b(c(d(...(e))))) -> (SCHEDULER) -> B(c(d(a(b)))) -> (SCHEDULER) -> C(d(g(a)c)))) -> (SCHEDULER) -> A(a(b(c(d[BLOCK] -> (SCHEDULER) -> B(...) -> ... -> (SCHEDULER) -> [BLOCK](e))))) -> ...

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

Как сделать так, чтобы повторить с начала я знаю, сейчас так и реализовано. Но сейчас число блокировок одна штука и она простая, поэтому повторить весь путь с начала несложно. При этом добавляются и другие виды блокировок, поэтому при том же подходе придется переделывать почти всю логику ресурсов и задач, это несколько месяцев человеко-часов в лучшем случае... Вот я и думал какие методы сохранения и развертки стека есть...
13 фев 19, 16:00    [21808635]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
mayton
Aklin
В среднем за секунду исполняется от 30к до 1м задач.

При одном миллионе задач в секунду у нас длительность одного сеанса задачи = 1мс.
Это та самая граница где КМК надо уходить от мультизадачности в другую сторону.
Сабж у нас был на эту тему.
Про современную многозадачность который?

Пытаюсь осилить, пока плохо дается.


от 30к до 1м - это реальное исполнение числа задач в секунду. Но тут правда оговорка.
Задачи есть всегда, то есть конвейер задач забит, и процессор постоянно что-то молотит. В зависимости от сложности задачи ее исполнение занимает чуть больше или чуть меньше времени. Если все задачи закончились, значит программа завершена.

А не так, что если нет задач, то программа прохлаждается.
13 фев 19, 16:04    [21808642]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
При твоей архитектуре тебе нужна легковесная очередь заданий.

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

Набор потоков должен быть запасом чтоб потоки-неудачники могли спокойно висеть на 1 задаче
а их работу подхватят другие.
13 фев 19, 16:10    [21808652]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Aklin
ABCDE - задачи, abcde - ресурсы.

Нормальное исполнение (с учетом ресурсов) будет примерно такое:
(SCHEDULER) -> A(a(b(c(d(...(e))))) -> (SCHEDULER) -> B(c(d(a(b)))) -> (SCHEDULER) -> C(d(g(a)c)))) -> (SCHEDULER) -> A(a(b(c(d[BLOCK] -> (SCHEDULER) -> B(...) -> ... -> (SCHEDULER) -> [BLOCK](e))))) -> ...

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

Как сделать так, чтобы повторить с начала я знаю, сейчас так и реализовано.

Можно перед запуском задачи нужные ресурсы блокировать? Т.е. запустил задачу, в начале получил все необходимые ресурсы, затем сделал полезную работу. Если ресурсы не получил, то перешел к следующей задаче и т.д. ИМХО так можно будет повторно запускать с начала, а не с середины.
Aklin
Вот я и думал какие методы сохранения и развертки стека есть...

Мне кажется нет ничего хорошего в этом направлении. По сути ты изобретаешь собственную многопоточность. В этом случае проще разобраться как пользоваться уже имеющейся (потоки ОС).
13 фев 19, 16:29    [21808694]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
Dima T
Т.е. запустил задачу, в начале получил все необходимые ресурсы, затем сделал полезную работу.

На начало работы задачи я, во-первых, не знаю какие там будут использованы ресурсы (не, конечно можно продублировать работу задачи, сделав две ветки: выделение ресурсов как предварительное исполнение и само исполнение как таковое, но смысла в этом не вижу пока что), а во-вторых, блокировка ресурсов зависит от результата работы многих задач, я заранее это никак не отслежу, пока не попытаюсь достучаться до ресурса.
13 фев 19, 16:39    [21808705]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
Dima T
Мне кажется нет ничего хорошего в этом направлении. По сути ты изобретаешь собственную многопоточность. В этом случае проще разобраться как пользоваться уже имеющейся (потоки ОС).
Сейчас пытаюсь сочинить пример попроще, для оценки возможностей пула потоков и времени их переключения.

Пока что у меня ощущение что время переключения одного потока соизмеримо с временем работы одной задачи. А останов пустых потоков занимает больше времени чем исполнение сотни задач. Не могу точно сказать, как заработает пример - будет яснее...
13 фев 19, 16:40    [21808709]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Aklin
Dima T
Мне кажется нет ничего хорошего в этом направлении. По сути ты изобретаешь собственную многопоточность. В этом случае проще разобраться как пользоваться уже имеющейся (потоки ОС).
Сейчас пытаюсь сочинить пример попроще, для оценки возможностей пула потоков и времени их переключения.

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

Пул потоков нужен чтобы не создавать потоки и не останавливать. Это заранее созданные потоки, которые висят и ждут когда ты в них что-то запустишь.

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

Делай пример такой чтобы тут можно было его показать, с реальным кодом проще обсуждать.
13 фев 19, 16:57    [21808725]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47390
Aklin
Задача начинает дергать функции ресурсов, порой на глубину в 20-30 вызовов и где-то там может быть заблокирована.

А вот это плохо. Надо найти причину блокировки и убить. Насмерть.
13 фев 19, 17:36    [21808780]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Aklin
Member

Откуда: Прямо сейчас меня здесь нет
Сообщений: 56546
Dima T
Это заранее созданные потоки, которые висят и ждут когда ты в них что-то запустишь.
Я боюсь, что пары-тройки потоков мне может не хватить (в случае, например, если десяток будут висеть на заблокированных задачах), а делать 30 потоков, которые выжирают процессор под ноль мне нельзя...


Dimitry Sibiryakov
А вот это плохо. Надо найти причину блокировки и убить. Насмерть.

Как раз не надо. Блокировка задачи - ожидаемое поведение, а не проблема. Задачу в какой-то момент нужно приостановить до определенной отмашки.
13 фев 19, 17:44    [21808789]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
Dima T
Member

Откуда:
Сообщений: 13634
Aklin
Я боюсь, что пары-тройки потоков мне может не хватить (в случае, например, если десяток будут висеть на заблокированных задачах), а делать 30 потоков, которые выжирают процессор под ноль мне нельзя...

Говнокод писать нельзя, а потоков хоть 300 запускай, при простое они не займут твой процессор.
Поучи матчасть. Читай про синхронизацию потоков, выделение потокам процессорного времени и т.д.
Лучше в целом что-нибудь почитай про устройство многопоточности в ОС. Например Рихтера Windows via C/C++. Хоть там про виндовс, но подходы те же что и в линуксе.
13 фев 19, 18:11    [21808829]     Ответить | Цитировать Сообщить модератору
 Re: Легковесные последовательные подзадачи с возможностью блокировки  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Так он же пишет
С++, win/lin 86/64
13 фев 19, 18:31    [21808849]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Программирование Ответить