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

_>вот такая странная задача =) :
_>имеется ряд (много. сотни, тысячи) событий, которые должны происходить с определенной периодичностью каждое (от десятков миллисекунд до десятков секунд).
_>как бы по умному организовать работу такого планировщика, чтобы:
_>1. не было бы постоянной проверки в бесконечном цикле (дабы не грузить процессор)
_>2. не использовалось бы слишком много потоков

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

Здравствуйте, valery_l, Вы писали:

_>>вот такая странная задача =) :
_>>имеется ряд (много. сотни, тысячи) событий, которые должны происходить с определенной периодичностью каждое (от десятков миллисекунд до десятков секунд).
_>>как бы по умному организовать работу такого планировщика, чтобы:
_>>1. не было бы постоянной проверки в бесконечном цикле (дабы не грузить процессор)
_>>2. не использовалось бы слишком много потоков

_>Насколько я понял, Вы сами хотите генерить эти события.

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

_>Тогда на помощь придет виндовый таймер. Можно либо сделать таймер на НОД всех событий,
_>либо вычислять, когда должно произойти новое событие и переустанавливать таймер.
_>Если есть опасения, что события в текущем потоке будут обрабатываться слишком долго, в результате
_>чего следующее событие будет запаздывать, можно делать пост сообщений на другой поток.

есть момент, про который я явно не сказал — отсутствует виндовое окно =)

Здравствуйте, mr_trwister, Вы писали:

_>есть момент, про который я явно не сказал — отсутствует виндовое окно =)

WaitableTimer в отдельном потоке.

_>>есть момент, про который я явно не сказал — отсутствует виндовое окно =)

N>WaitableTimer в отдельном потоке.

а если событий несколько тысяч? (десятков/сотен тысяч)

Здравствуйте, mr_trwister, Вы писали:

N>>WaitableTimer в отдельном потоке.

_>а если событий несколько тысяч? (десятков/сотен тысяч)

Что значит несколько сотен тысяч ? В секунду ? В минуту ? Сколько их должно ожидаться в любой момент времени ?

Если в секунду — боюсь, что захлебнется вся эта обработка.

Опиши задачу поподробнее.

N>>>WaitableTimer в отдельном потоке.

_>>а если событий несколько тысяч? (десятков/сотен тысяч)

PD>Что значит несколько сотен тысяч ? В секунду ? В минуту ? Сколько их должно ожидаться в любой момент времени ?

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

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

PD>Опиши задачу поподробнее.

модуль (dll/объект/поток[и]), который по расписанию с заданной периодичностью вызывает что-то (типа колбака).
в расписании много событий. периодичность от десятков/сотен миллисекунд, до десятков/сотен секунд.

Здравствуйте, mr_trwister, Вы писали:

_>есть момент, про который я явно не сказал — отсутствует виндовое окно =)

Но ведь ничего не мешает его сделать. На ATL фиктивное окно для таймера делается достаточно просто.
Далее можно использовать такой алгоритм:
1. находим ближайшее событие, устанавливаем таймер на момент, когда это событие (одно или несколько) должно произойти.
2. срабатывает таймер, останавливаем таймер, вызываем нужные колбеки и снова повторяем п.1

Здравствуйте, mr_trwister, Вы писали:
_>всего несколько десятков/сотен тысяч событий, которые могут возникать с заданной периодичностью.
_>такое большое количество событий я указал, чтобы подвести к мысли, что WaitForMultipleObjects имеет ограничение на 64 ожидаемых WaitableTimer.

CreateTimerQueue, CreateTimerQueueTimer вам в помощь

вроде как все условия выполняются, если я конечно внимательно все прочитал

Здравствуйте, Alexey Frolov, Вы писали:

AF>Здравствуйте, mr_trwister, Вы писали:
_>>всего несколько десятков/сотен тысяч событий, которые могут возникать с заданной периодичностью.
_>>такое большое количество событий я указал, чтобы подвести к мысли, что WaitForMultipleObjects имеет ограничение на 64 ожидаемых WaitableTimer.

AF>CreateTimerQueue, CreateTimerQueueTimer вам в помощь

AF>вроде как все условия выполняются, если я конечно внимательно все прочитал

ага. спасибо! надо повнимательнее изучить эту сторону win32api.

как я понимаю, создаем TimerQueue (CreateTimerQueue), а потом в нее добавляем много премного QueueTimer (CreateTimerQueueTimer). правильно?
в дальнейшем очередь сама мониторит эти таймеры и вызывает колбаки, заданные в них независимо от нашего участия?

не очень только понятно в каком потоке вызываются эти колбаки...

Здравствуйте, mr_trwister, Вы писали:

_>имеется ряд (много. сотни, тысячи) событий, которые должны происходить с определенной периодичностью каждое (от десятков миллисекунд до десятков секунд).
_>как бы по умному организовать работу такого планировщика, чтобы:
_>1. не было бы постоянной проверки в бесконечном цикле (дабы не грузить процессор)
_>2. не использовалось бы слишком много потоков

while (живы)
{
    выполняем очередное событие (возможно, в отдельном потоке);
    вычисляем, сколько времени до следующего события;
    ложимся спать (Sleep или WaitForSingleObject(на event выхода, с таймаутом));
}

Здравствуйте, mr_trwister, Вы писали:

_>как я понимаю, создаем TimerQueue (CreateTimerQueue), а потом в нее добавляем много премного QueueTimer (CreateTimerQueueTimer). правильно?
_>в дальнейшем очередь сама мониторит эти таймеры и вызывает колбаки, заданные в них независимо от нашего участия?

_>не очень только понятно в каком потоке вызываются эти колбаки...

Да, правильно. Для вызова callback в основном используется механизм APC (asynchronous procedure call), про него почитайте. Но возможны варианты и без него, почитайте в msdn описание последнего параметра (Flags) для CreateTimerQueueTimer, там все варианты расписаны, можете выбрать наиболее удобный и эффективный

_>>имеется ряд (много. сотни, тысячи) событий, которые должны происходить с определенной периодичностью каждое (от десятков миллисекунд до десятков секунд).
_>>как бы по умному организовать работу такого планировщика, чтобы:
_>>1. не было бы постоянной проверки в бесконечном цикле (дабы не грузить процессор)
_>>2. не использовалось бы слишком много потоков

C>

C>while (живы)
C>{
C>    выполняем очередное событие (возможно, в отдельном потоке);
C>    вычисляем, сколько времени до следующего события;
C>    ложимся спать (Sleep или WaitForSingleObject(на event выхода, с таймаутом));
C>}
C>

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

Здравствуйте, mr_trwister, Вы писали:

_>жуткое дело! если у нас сотни тысяч событий, то мы должны после пробуждения перебирать все и искать то, которое будет ближайшим?

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

_>>жуткое дело! если у нас сотни тысяч событий, то мы должны после пробуждения перебирать все и искать то, которое будет ближайшим?

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

а сортировать кто будет?

Здравствуйте, mr_trwister, Вы писали:
_>>Тогда на помощь придет виндовый таймер.
_>есть момент, про который я явно не сказал — отсутствует виндовое окно =)
Для SetTimer() не обязательно наличае окна.

// timer id
::UINT uiTimerID = 0x0BAD;

// timer procedure
VOID CALLBACK timerProc(::HWND hwnd, ::UINT uMsg, ::UINT_PTR idEvent, ::DWORD dwTime)
{
    /* ToDo: some code 
     * idEvent
     *
     *
     */
};
...
::SetTimer(NULL, uiTimerID, dw_TimerTimeOut, &timerProc);
...
::KillTimer(NULL, uiTimerID);

idEvent
[in] Specifies the timer's identifier.
dwTime
[in] Specifies the number of milliseconds that have elapsed since the system was started. This is the value returned by the GetTickCount function.

_>>>Тогда на помощь придет виндовый таймер.
_>>есть момент, про который я явно не сказал — отсутствует виндовое окно =)
T>Для SetTimer() не обязательно наличае окна.
T>

// timer id
T>::UINT uiTimerID = 0x0BAD;

T>// timer procedure
T>VOID CALLBACK timerProc(::HWND hwnd, ::UINT uMsg, ::UINT_PTR idEvent, ::DWORD dwTime)
T>{
T>    /* ToDo: some code 
T>     * idEvent
T>     *
T>     *
T>     */
T>};
T>...
T>::SetTimer(NULL, uiTimerID, dw_TimerTimeOut, &timerProc);
T>...
T>::KillTimer(NULL, uiTimerID);

T>

idEvent
T>[in] Specifies the timer's identifier.
T>dwTime
T>[in] Specifies the number of milliseconds that have elapsed since the system was started. This is the value returned by the GetTickCount function.

хм. интересный подход. единственное, что меня смущает — это "When you specify a TimerProc callback function, the default window procedure calls the callback function when it processes WM_TIMER. Therefore, you need to dispatch messages in the calling thread, even when you use TimerProc instead of processing WM_TIMER."

Ну, наверное, сортировка должна выполняться при добавлении нового события.

Здравствуйте, mr_trwister, Вы писали:

_>>>жуткое дело! если у нас сотни тысяч событий, то мы должны после пробуждения перебирать все и искать то, которое будет ближайшим?

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

_>а сортировать кто будет?

А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

Здравствуйте, mr_trwister, Вы писали:

N>>>>WaitableTimer в отдельном потоке.

_>>>а если событий несколько тысяч? (десятков/сотен тысяч)

PD>>Что значит несколько сотен тысяч ? В секунду ? В минуту ? Сколько их должно ожидаться в любой момент времени ?

_>всего несколько десятков/сотен тысяч событий, которые могут возникать с заданной периодичностью.

_>такое большое количество событий я указал, чтобы подвести к мысли, что WaitForMultipleObjects имеет ограничение на 64 ожидаемых WaitableTimer.

Интересно, где вы нашли ограничение 64 объекта обрабатываемых функцией WaitForMultipleObjects. Из своего опыта знаю, что 256 обектов она обрабатываает без проблем

Здравствуйте, Centaur, Вы писали:

C>Здравствуйте, mr_trwister, Вы писали:

_>>>>жуткое дело! если у нас сотни тысяч событий, то мы должны после пробуждения перебирать все и искать то, которое будет ближайшим?

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

_>>а сортировать кто будет?

C>А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

для такого случая самым эффективным вариантом будет контейнер priority_queue он хранит элементы в частично отсортированном виде, ему не важен полный правильный порядок, а важно чтобы "лучший, ближайший" по какому либо критерию элемент лежал на вершине. Здесь в ветке С++ как-то уже проводили замеры производительности, эта штука показывает хороший результат

_>>>>а если событий несколько тысяч? (десятков/сотен тысяч)

PD>>>Что значит несколько сотен тысяч ? В секунду ? В минуту ? Сколько их должно ожидаться в любой момент времени ?

_>>всего несколько десятков/сотен тысяч событий, которые могут возникать с заданной периодичностью.

_>>такое большое количество событий я указал, чтобы подвести к мысли, что WaitForMultipleObjects имеет ограничение на 64 ожидаемых WaitableTimer.

M>Интересно, где вы нашли ограничение 64 объекта обрабатываемых функцией WaitForMultipleObjects. Из своего опыта знаю, что 256 обектов она обрабатываает без проблем

DWORD WINAPI WaitForMultipleObjects(DWORD nCount, const HANDLE* lpHandles, BOOL bWaitAll, DWORD dwMilliseconds);

nCount — [in] The number of object handles in the array pointed to by lpHandles. The maximum number of object handles is MAXIMUM_WAIT_OBJECTS.

смотрим в winnt.h и видим #define MAXIMUM_WAIT_OBJECTS 64

_>>>>жуткое дело! если у нас сотни тысяч событий, то мы должны после пробуждения перебирать все и искать то, которое будет ближайшим?

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

_>>а сортировать кто будет?

C>А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

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

Здравствуйте, mr_trwister, Вы писали:

C>>А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

_>если события повторяются периодически, то, чтобы найти время наступления ближайшего события, надо пройтись по всему списку событий и найти ближайшее к текущему моменту.

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

_>одновременно надо вычислить, сколько всем событиям осталось до наступления.

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

class Event
{
public:
    Event(const Event& other);
    Event& operator=(const Event& other);

    DWORD time(); // of nearest occurence
    bool calculateNext(); // return false if no more occurences
    void execute();

    class earlier : public std::binary_function<Event, Event, bool>
    {
    public:
        bool operator()(const Event& lhs, const Event& rhs) const
        {
            return lhs.time() < rhs.time();
        }
    };
};

std::set<Event, Event::earlier> events;

while (!bStop)
{
    Event e = events.front();
    events.pop_front();
    e.execute();
    if (e.calculateNext()) events.insert(e);
    Sleep(events.front().time() - GetTickCount());
}

Расширение на случай, когда за одну итерацию сразу отрабатывает много событий, тривиально и предоставляется читателю в качестве упражнения

C>>>А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

_>>если события повторяются периодически, то, чтобы найти время наступления ближайшего события, надо пройтись по всему списку событий и найти ближайшее к текущему моменту.

C>Поскольку события хранятся отсортированными, то ближайшее событие — это первое в очереди. Его ближайшее время наступления предположительно уже вычислено и записано прямо в нём. Также пусть событие умеет пересчитать своё следующее время наступления.

_>>одновременно надо вычислить, сколько всем событиям осталось до наступления.

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

[...]

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

с практической же — постоянное удаление из контейнера и добавление в контейнер объекта кажется мне несколько неоптимальным =)


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

Здравствуйте, mr_trwister, Вы писали:

C>>>>А будем держать контейнер всегда отсортированным. Если события добавляются редко, будем держать массив, сортировать при старте всей системы. Если часто или если события повторяются каждое через свой интервал — заведём set или ещё какое сбалансированное дерево. Добавление, взятие первого элемента, удаление — O(ln(N)).

_>>>если события повторяются периодически, то, чтобы найти время наступления ближайшего события, надо пройтись по всему списку событий и найти ближайшее к текущему моменту.

C>>Поскольку события хранятся отсортированными, то ближайшее событие — это первое в очереди. Его ближайшее время наступления предположительно уже вычислено и записано прямо в нём. Также пусть событие умеет пересчитать своё следующее время наступления.

_>>>одновременно надо вычислить, сколько всем событиям осталось до наступления.

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

_>[...]

_>теперь понятна ваша мысль. хорошее решение с алгоритмической точки зрения.

_>с практической же — постоянное удаление из контейнера и добавление в контейнер объекта кажется мне несколько неоптимальным =)

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

_>зы: ок. думаю, что обсуждение можно смело заканчивать. все основные подходы к организации были рассмотрены — начиная с алгоритмических и заканчивая очередями таймеров win32. всем огромное спасибо за советы и помощь!

я писал подобное на питоне, работает.

Остаются мелочи:
— после обработки события надо перебирать и обрабатывать события, которые просрочены.
— ввести системное событие для управления этой самой очередью и завершения работы, вызывать его достаточно часто, чтобы не было ощущения, что программа зависла; самый простой пример -- раз в 5 секунд смотреть свободное место на диске, если меньше гигабайта -- завершать цикл.

Успехов.