Помогите с алгоритмом нахождения времени, удовлетворяющего условию

[phprus]

Помогите с алгоритмом нахождения времени, удовлетворяющего условию

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

typedef struct SchedulePacked
{
	uint64	minutes;	/* минуты (0-59) */
	uint32	hours;	/* часы (0-23)   */
	uint32	days;		/* числа (1-31)  */
	uint16	months;	/* месяцы (1-12) */
	uint8		daysofweek;/* дни-недели (0-6) (воскресенье - это 0) */
} SchedulePacked;

И текущее время, хранящееся в структуре, аналогичной struct tm из libc, за исключением того, что нумерация месяцев начинается с 1. Для заполнения поля tm_wday (день недели) на основании дня, месяца и года есть специальная функция. Так-же доступно время в виде time_t.

Необходимо найти дату и время, которое строго больше текущего и удовлетворяет условиям, описанным в переменной типа SchedulePacked (если бит, соответствующий номеру минуты, часа и т.д. выставлен в 1, значит это значение допустимо).

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

 

[Sherman]

Немного подумав, предлагаю в итоге такую идею.

Все таски разбиты на списки типа: по минутам, по часами и минутам, по дням, часам и минутам и так далее. Чтобы в одной очереди были таски, которые одинаковы по частоте периода.

Списки осортированы.

У списка должен быть указатель на текущий таск.

Текущий таск = ближайший по заданному условию(приведено ТС выше).

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

 

[phprus]

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

Или ты советуешь каждую минуту проверять все задания на то, можно ли их выполнять сейчас или нет?

 

[Sherman]

Да, проверять придеться каждую минуту.

Каждую минуту, если есть таски которые выполняются как (n * * * *) в нотации крон.

 

[phprus]

Sherman
Вот от такой проверки и хотелось бы уйти. Для этого и ставилась задача нахождения времени следующего запуска, чтобы по нему построить очередь с приоритетами(приоритет - время запуска) и уже из нее выбирать задачи на исполнение (или спать, если исполнять нечего).

 

[Krishna]

Лично я ничего не понял, касательно того, в какой структуре лежат времена заданий к выполнению. Это несортированный массив записей SchedulePacked или что?

 

[Sherman]

Ну в моем случае никакого перебора до бесконечности нет.

Худшее время работы для каждого периода, это O(n) тасков. А скорее всего там будет O(1), так как таски более менее равномерно распределяются по времени.

Да, забыл сказать, что еще нужна будет очередь тасков на выполнение.

 

[Krishna]

(если бит, соответствующий номеру минуты, часа и т.д. выставлен в 1, значит это значение допустимо).

А, до меня кажется дошло. Это типа когда в месяце например прописано */2, то в months будет 101010101010?

-~{}~ 06.03.10 16:57:

P.S. Что не отменяет первого вопроса

 

[phprus]

Krishna
В рассматриваемом случае задание одно.
Есть конкретное задание, расписание которого доступно. Доступно так-же время окончания его последнего запуска. Необходимо найти время следующего запуска, при этом время следующего запуска должно быть строго больше времени окончания предыдущего и удовлетворять расписанию (SchedulePacked).

А для хранения этого времени мы можем использовать struct tm или time_t из libc. Изначально на вход подается время(время окончания предыдущего запуска задания == текущему времени) в одном из этих двух форматов и само расписание (типа SchedulePacked).

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

-~{}~ 06.03.10 19:20:

Krishna

А, до меня кажется дошло. Это типа когда в месяце например прописано */2, то в months будет 101010101010?

Да это именно так.

Sherman
Я как-то не очень понимаю твою идею. Как нам поможет объединение заданий с одинаковой частотой в одни списки? Как сортировать эти списки? Время следующего запуска же заранее не известно (его я и хочу найти).
Да и вроде-бы в такой системе возможна потеря заданий, когда к примеру во время X должно выполниться 10 заданий, а параллельно можно запускать только 5. Когда один поток выполнения закончит работу, то на часах будет уже не Х, а Х+1 и тогда 5 заданий которым не повезло потеряются, а такого допустить никак нельзя.
Набросай пожалуйста какую-либо схемку твоего алгоритма или пример каких-либо данных, а то я пока не очень понимаю какие преимущества может дать такая схема перед методом простой проверки всех заданий каждую минуту.

 

[zerkms]

phprus
пессимистический вариант: перебор 525600 вариантов (в случае, если задание запустится следующий раз через 365 дней)
причём перебор нужно осуществлять сразу после запуска. т.е. раз в год
если задание выполняется раз в сутки - тогда цикл из 1440 итераций, раз в сутки.

стоит ли искать алгоритм, если порядки циклов такие смешные?

ps: проверка ежеминутно каждого времени на необходимость запуска алгоритмически и по CPU будет даже ещё проще

-~{}~ 07.03.10 01:05:

Да и вроде-бы в такой системе возможна потеря заданий, когда к примеру во время X должно выполниться 10 заданий, а параллельно можно запускать только 5. Когда один поток выполнения закончит работу, то на часах будет уже не Х, а Х+1 и тогда 5 заданий которым не повезло потеряются, а такого допустить никак нельзя.

это уже нужно от задачи плясать. потеря задания критична, а запуск задания не по расписанию - нет?

 

[phprus]

zerkms

стоит ли искать алгоритм, если порядки циклов такие смешные?

Да. Наверное так и реализую. У меня вызывало сомнения во сколько может увеличиться период, если еще день недели указывать. Возможно ли его увеличение более чем в 7 раз?

это уже нужно от задачи плясать. потеря задания критична, а запуск задания не по расписанию - нет?

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

Всем спасибо за советы!

 

[zerkms]

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

я бы тогда сделал просто какую-то очередь, а сам scheduler разделил на 2 части: трекер и раннер. треккер считает когда запускать и в очередь добавляет задание на запуск, а раннер постоянно сканит очередь и запускает задания.

 

[phprus]

zerkms
Так я сейчас такую схему и реализую.
Есть раннер (по сути весь scheduler), который содержит в себе очередь заданий. Если подошло время исполнения задачи с вершины очереди, то задача удаляется из очереди, и запускается (параллельно scheduler'у). По окончании выполнения считается время следующего запуска (в том-же процессе, где выполнялась задача), об этом уведомляется раннер (ему-же передается вычисленное время следующего запуска), после чего он снова добавляет эту задачу в очередь уже с новым временем запуска.
Ступор возник на этапе собственно вычисления, а когда в следующий раз то запускать.

 

[Sherman]

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

Вот что придумалось.

Храним расписание следующим образом.

У нас есть 60 списков(60 минут).

Задачи добавляются в списки соответсвенно минутам(одна задача может быть в разных списках, но не более чем в 30, так как если каждую минуту, то можно завести для таких задач отдельную очередь).

Как происходит запуск.

Внутри шедулера есть значение последней даты запуска. Пример. запускаем шедулер. Даты нету. Берем текущее время.

Далее смотрим какой список у нас соответствует текущей минуте. Допустим 10.
Проходим весь список 10, вычисляя остальные параметры(неделю, мес. и так далее), если задача подходит, добавляем ее в runner(очередь).

Если мы успели уложиться в текущую минуту, ок. Засыпаем до следующей.
Если нет, тогда следующий запуск будет не по времени(current time), а как значение последней даты запуска шедулера + 1 минута.

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

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

Получается своего рода индекс. То есть идея в том, что в такого рода задачах надо делать индексированные структуры данных.