Как реализовать асинхронный таймер в системе * nix с использованием pthreads

Question

У меня 2 вопроса:

В1) Могу ли я реализовать асинхронный таймер в однопоточном приложении, т. Е. Мне нужна такая функциональность.

....
Timer mytimer(5,timeOutHandler)


.... //this thread is doing some other task


...
and after 5 seconds, the timeOutHandler function is invoked.

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

Я также хочу знать, могу ли я реализовать таймер (не тайм-аут), используя select. Select только ожидает набор файловых дескрипторов, но я хочу иметь список таймеров в порядке возрастания их тайм-аутов истечения и хочу select, чтобы сообщить мне, когда истекает первый таймер, и так далее. Таким образом, вопрос сводится к тому, можно ли реализовать асинхронный таймер, используя select / poll или какой-либо другой демультиплексор событий?

Q2) Теперь перейдем ко второму вопросу. Это мой главный вопрос. Теперь я использую выделенный поток для проверки тайм-аутов, т. Е. У меня есть минимальная куча таймеров (время истечения), и этот поток спит до истечения первого таймера, а затем вызывает обратный вызов. т.е. код выглядит примерно так

1. заблокировать мьютекс
2. проверка времени первого таймера
3. Условное время ожидания этого времени (и активация, если какой-то другой поток вставляет таймер со временем истечения меньше, чем первый таймер) Условие ожидания разблокирует блокировку.
4. После окончания ожидания состояния у нас есть блокировка. Так что разблокируйте его, удалите таймер из кучи и вызовите функцию обратного вызова.
5. перейти к 1

Мне нужна временная сложность такого асинхронного таймера. Из того, что я вижу

1. Вставка lg (n)
2. Срок действия lg (n)
3. Аннулирование

:( это вызывает у меня головокружение) проблема в том, что у меня есть минимальная куча таймеров в соответствии с их временем, и когда я вставляю таймер, я получаю уникальный идентификатор. Поэтому, когда мне нужно отменить таймер, мне нужно предоставить этот таймер, и поиск этого таймера в куче в худшем случае займет O (n)

Я не прав?

Можно ли отменить в O (LG N)

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

Answer 1

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

Вы можете проверить, используя signal () и SIGALRM для реализации функциональности в POSIX, но я бы рекомендовал против этого (сигналы Unix - отвратительные взломы, и когда запускается функция обратного вызова сигнала, очень мало что можно сделать внутри это безопасно, так как он работает асинхронно с потоком вашего приложения)

Ваша идея об использовании таймаута select () для реализации вашей функции таймера хороша - это очень распространенная техника, и она работает хорошо. По сути, вы сохраняете список ожидающих / предстоящих событий, отсортированный по отметке времени, и непосредственно перед вызовом select () вычитаете текущее время из первой отметки времени в списке и передаете эту разницу времени в качестве значения времени ожидания, чтобы выбрать (). (примечание: если дельта времени отрицательна, передайте ноль в качестве значения тайм-аута!) Когда select () возвращается, вы сравниваете текущее время со временем первого элемента в списке; если текущее время больше или равно времени события, обработайте событие таймера, вытолкните первый элемент из заголовка списка и повторите.

Что касается эффективности, то ваши большие времена будут полностью зависеть от структуры данных, которую вы используете для хранения своего упорядоченного списка таймеров. Если вы используете очередь с приоритетами (или аналогичную упорядоченную структуру древовидного типа), у вас может быть O (log N) раз для всех ваших операций. Вы даже можете пойти дальше и сохранить список событий как в хэш-таблице (с указанием идентификаторов событий), так и в связанном списке (отсортированном по отметке времени), что может дать вам O (1) раз для всех операций. O (log N), вероятно, достаточно эффективен, если только вы не планируете действительно большое количество событий, ожидающих одновременно.

Answer 2

man pthread_cond_timedwait

man pthread_cond_signal

Answer 3

Если вы используете C #, System.Timers.Timer будет делать то, что вы хотите. Вы указываете метод-обработчик события, который таймер вызывает по истечении срока действия, который может быть в классе, из которого вы вызываете таймер. Обратите внимание, что когда таймер вызывает обработчик событий, он будет делать это в отдельном потоке, который необходимо учитывать при обновлении пользовательского интерфейса или при использовании его свойства SynchronizingObject для его запуска в потоке пользовательского интерфейса. *

Answer 4

Если вы являетесь приложением Windows, вы можете инициировать отправку вам сообщения WM_TIMER в какой-то момент в будущем, которое будет работать, даже если ваше приложение является однопоточным. Однако точность хронометража не будет большой.

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

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