Как оптимально организовать ожидание на множестве таймеров? Фактически - очередь

Question

Как оптимально организовать ожидание на множестве таймеров? Фактически - очередь

таймеров с приоритетами

Задача: есть N независимых задач с периодическими таймерами; обработкой занимается общий пул потоков. По истечении времени прикреплённая к таймеру задача добавляется в очередь пула, обновляется некоторое состояние, а сам таймер с обновлённой задачей добавляется в "конец" очереди таймеров.
Сложности:
> Период может различаться
> Запуск таймеров тоже происходит не одновременно
> Таймеры могут добавляться и удаляться

Моя идея: поток-слушатель + min-heap, отсортированная по времени ожидания до ближайшего срабатывания + дополнительный флаг delete_pending в контексте каждого таймера, чтобы не усложнять удаление (т.е. таймер будет удалён не сразу, а при следующем срабатывании)

Максимальное число таймеров: несколько тысяч

#c++ #embedded #programming #russian

0

27.12.2021

15 ответов

27 просмотров

Dmitriy [Отпуск] Автор вопроса

Kelbon
почему таймер не может просто по истечению времени...

Практика показала - с несколькими тысячами таймеров при близком времени срабатывания системе становится нехорошо

0

27.12.2021

Dmitriy [Отпуск] Автор вопроса

Собственно...))

0

27.12.2021

🐈

Dmitriy [Отпуск]
Практика показала - с несколькими тысячами таймеро...

я так понимаю, это добро у вас еще где-то в драйверах болтается?

0

27.12.2021

Dmitriy [Отпуск] Автор вопроса

🐈
я так понимаю, это добро у вас еще где-то в драйве...

Ага

0

27.12.2021

🐈

Dmitriy [Отпуск]
Ага

тысячи таймеров. если не секрет, це драйвер от чего?

0

27.12.2021

место имение рейверы

ну либо так либо таймерные колеса

0

27.12.2021

Dmitriy [Отпуск] Автор вопроса

🐈
тысячи таймеров. если не секрет, це драйвер от че...

Подробности раскрыть не могу :( К каждому создаваемому процессу, соответствующему некоторому критерию, прикрепляется таймер с периодической задачей анализа VAD

0

27.12.2021

Dmitry Sokolov

Если тайм-аут ограничен можно сделать что то вроде хэша по времени. Например ограничение час, делаем 3600 интрузивных списков. При установке таймера кладём в соответствующий список, обработчик просто ходит циклически по слотам инкрементируясь на секунду. Добавление/удаление и expiration O(1). Оно даже если тайм-аут превышен тоже будет работать, просто чуть менее эффективно (при обходе в списке expired надо будет фильтровать те которые через час-два и т.д.)

0

27.12.2021

Dmitriy [Отпуск] Автор вопроса

По сути - timer wheel же и есть :)

0

27.12.2021

Dmitry Sokolov

Dmitriy [Отпуск]
По сути - timer wheel же и есть :)

А, ну так всё уж расписано :) да, точно, оно.

0

27.12.2021

Kelbon

Dmitry Sokolov
Если тайм-аут ограничен можно сделать что то вроде...

добавление и удаление случайно не O(N/3600) будут?) Хотя не знаю что вы подразумеваете под интрузивным списком

0

27.12.2021

Dmitry Sokolov

Kelbon
добавление и удаление случайно не O(N/3600) будут?...

Простой связный список который содержит все события которые экспайрятся в эту секунду.

0

27.12.2021

Arelav

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

0

28.12.2021

Dmitriy [Отпуск] Автор вопроса

Arelav
Я когда написал немного не дочитал. Я имел ввиду ...

Не совсем понял. Срабатывание таймера обработано потоком X (путь это DPC или мой поток) -> пихаем задачу/коллбэк в очередь пула...

0

28.12.2021

Kelbon · Accepted Answer

Kelbon

почему таймер не может просто по истечению времени делать что то + задавать ещё одну задачу рекурсивно (сделать Х через время N)? На буст азио таймере во всяком случае такое делается легко

0

27.12.2021

170 похожих чатов

Как оптимально организовать ожидание на множестве таймеров? Фактически - очередь

15 ответов

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