Re: Delaying events for fixed amounts of time.
- From: "robertwessel2@xxxxxxxxx" <robertwessel2@xxxxxxxxx>
- Date: Mon, 15 Dec 2008 21:57:12 -0800 (PST)
On Dec 15, 11:25 pm, JC <jason.cipri...@xxxxxxxxx> wrote:
I'm not sure if this is an appropriate topic, but it does possibly
involve multithreading. I have some requirements and I'm not sure what
the best solution is:
I have an application and part of it is receiving "events" in real
time, and must take a delayed action on those events by waiting a
fixed amount of time (say, 5 seconds) before processing the events.
Events may be arriving much closer together than the delay time, so I
need to asynchronously delay for each event.
Additionally, each event has a "key", and events with the same keys
must be grouped together. The delayed action must happen a fixed
amount of time after the *FIRST* event with a given key arrives. This
means I have to be able to keep track of what events I'm in the
progress of waiting on, I can't lose that information.
So basically the logic is:
onEvent (key, event) {
if no event with this key is pending:
begin new asynchronous delay for this event
else
add this event to the set of other events with same key
}
Then after the time period expires, the events with that key are all
processed. Event with key 42 arrives, delay time is 5 seconds, every
other event with that key arriving in the next 5 seconds is grouped
together, and after 5 seconds passes all of those events are
processed.
Timing accuracy is not critical, but I must respond to new events
within 250 ms of their arrival (so I can't impose a limit on the
number of pending unique keys). There are going to be a lot of events,
maybe on the order of 50-100 every second, with 15-30 unique keys per
second. It's part of a server application that's going to be doing a
decent amount of other work, so minimal system resource usage will be
critical, as well as scalability in the future.
I'm not sure what the best way to implement this is. I'm on Windows so
I have anything Windows has to offer. The options considered so far
are:
1) Create a new thread and a list of events each time a new key
arrives. If a key that already has a thread+list arrives, just add the
key to the list. The thread just sleeps for 5 seconds and then
processes all the events in the associated list. Appropriate
synchronization is done to avoid race conditions keeping track of key->thread+list mappings. Disadvantage: Requires creation of a lot of
threads (is this bad?).
2) Store the current system time and create a list of events each time
a new key arrives. Start one thread that is continuously running in a
loop, checking the current system time against all of the stored
system times. Process events as timers expire. Use a manual reset
event to prevent thread from running in tight loops needlessly if no
events are pending. Pause for, say, 250ms each time through the loop
to reduce CPU load when running (250ms is good enough accuracy).
Disadvantage: Seems ugly, and complexity is linear with respect to
number of pending unique keys, although the number is small right now
(on the order of 10's or 100's).
3) Use Windows SetTimer, create a new timer + list of events when a
new key arrives. Same deal as #1, except process list when timer is
triggered. Disadvantage: SetTimer makes no guarantees about the max
number of timers that can be created, also requires a Windows message
processing loop, which is a big issue.
4) Use some other Windows timing service that I'm not aware of.
Disadvantage: I'm not aware of it.
5) Maybe there's some other Windows feature that helps, like APC or...
thread pools or something? Disadvantage: I've never used any of that
stuff before, and don't know much about it.
The major advantage of #1 is simplicity. #3, #4 and #5 can potentially
be even simpler to implement. The major advantage of #2 is it doesn't
require new threads per unique event. So I guess the question kind of
boils down to, is it better to create a ton of threads, or to take a
single threaded approach with a loop checking all of the times (or
some combination of the two and have multiple threads responsible for
subsets of all of the unique keys)? And the second question, then, is,
does Windows provide something well-suited to this task, or is there
some other technique that works well?
I'd go with a variation of #2.
Have a queue of keys, each time a new key arrives, add it to the end
of the list, and store the time it should be processed (IOW, now+5s).
If an event with a key arrives that's already in the queue, use a
linked list-type of structure to hang it off the existing member.
The service thread should wake up, look at the first element in the
queue, processes that linked list of work if it's ready, or otherwise
wait on a timer for that first element to become ready. It should
also wait on a signal that you fire every time you add a new element
(key) to the queue (note: but not when you just link in a duplicate
key). Obviously it should loop, and check for an additional list of
work after it finishes the first one. You might be able to accomplish
both functions (the delay and the signal), by using a single event to
handle the "work inserted" signal, and waiting on that with
WaitForSingleObject() with an appropriate timeout value. Note that
the service thread will be woken up more often that it's necessary to
actually run work because of the signal from the insertion process,
but that lets the service thread do all of its own scheduling.
It doesn't sound like you're going to have enough events in the queue
to matter, but if the number does get large, I'd construct a hash
table linking all the first items in the queue, indexed by the key.
That way the search and add will be fast. So you'd have all the head
elements in two structures - the queue based on the run time, and a
hash table for the key.
If you also need to insert elements with varying delays, instead of a
simple queue, a priority queue (using the classic heap structure), is
simple, and basically log(n) for all operations.
Obviously all that will need to be protected with a mutex.
Unless you have enough work, there's not really any point to create
multiple worker threads.
.
- Follow-Ups:
- Re: Delaying events for fixed amounts of time.
- From: JC
- Re: Delaying events for fixed amounts of time.
- From: David Schwartz
- Re: Delaying events for fixed amounts of time.
- References:
- Prev by Date: Delaying events for fixed amounts of time.
- Next by Date: Re: Double ended queue - review
- Previous by thread: Delaying events for fixed amounts of time.
- Next by thread: Re: Delaying events for fixed amounts of time.
- Index(es):
Relevant Pages
|
Loading
