Efficient "group" wait

[Burke Lantis]

I have N events, e1, e2, ... eN. The WaitForSingleObject() function
lets me wait only for one of these, while WaitForMultipleObjects()
won't return until all N get signalled. I want neither! What I want is
to be able to wake up only when, say, EITHER e1, OR e2 AND e3 together
get signalled. That is the event condition: (e1 || (e2 && e3))

Can this at all be done? Thanks in advance.

Sent via Deja.com
http://www.deja.com/

[Kaz Kylheku]

On Wed, 07 Feb 2001 22:19:45 GMT, Burke Lantis <burke...@hotmail.com> wrote:
>I have N events, e1, e2, ... eN. The WaitForSingleObject() function
>lets me wait only for one of these, while WaitForMultipleObjects()
>won't return until all N get signalled.

That is false; there is a parameter which determines whether you have
all or any behavior. WaitForMultipleObjects is capable for waiting for
everything to be signaled, or just one.

>I want neither! What I want is
>to be able to wake up only when, say, EITHER e1, OR e2 AND e3 together
>get signalled. That is the event condition: (e1 || (e2 && e3))

Then you want condition variables, the non-braindamaged synchronization
object that Microsoft, naturally, does not provide, but which can be
constructed with moderate difficulty over their API.

mutex.lock();

while (! (condition_e1 || (condition_e2 && condition_e3))
mutex.wait(condvar);

assert (condition_e1 || (condition_e2 && condition_e3));

mutex.unlock();

So you see, a mechanism for waiting for multiple synchro objects isn't
even needed to solve this type of problem. What you need is to express
your predicates in terms of the state of shared data; then you can use
a single condition variable, to wait for a an arbitrarily complex
predicate to become true.

Short of using condition variables, what you can do is implement the
following hack. Use WaitForMultipleObjects to wait until any of the
events are fired, essentially the condition e1 || e2 || e3 .
If e1 is fired, the wait condition is satisfied, since
you clearly have e1 || (e2 && e3). Otherwise if e2 is fired, then wait
for e1 || e3, or if e3 is fired, wait for e1 || e2.

[Burke Lantis]

In article <slrn983mb...@ashi.FootPrints.net>,

k...@ashi.footprints.net wrote:
> On Wed, 07 Feb 2001 22:19:45 GMT, Burke Lantis
<burke...@hotmail.com> wrote:
> >I have N events, e1, e2, ... eN. The WaitForSingleObject() function
> >lets me wait only for one of these, while WaitForMultipleObjects()
> >won't return until all N get signalled.
>
> That is false; there is a parameter which determines whether you have
> all or any behavior. WaitForMultipleObjects is capable for waiting for
> everything to be signaled, or just one.

Thanks for the correction. Actually, I knew it too, but goofed up while
writing. Shouldn't even have mentioned WaitForSingleObject() as what I
meant was that within the context of WaitForMultipleObjects() one can
be woken up only EITHER when one OR all objects get signaled.

>
> >I want neither! What I want is
> >to be able to wake up only when, say, EITHER e1, OR e2 AND e3
together
> >get signalled. That is the event condition: (e1 || (e2 && e3))
>
> Then you want condition variables, the non-braindamaged
synchronization
> object that Microsoft, naturally, does not provide, but which can be
> constructed with moderate difficulty over their API.
>
> mutex.lock();
>
> while (! (condition_e1 || (condition_e2 && condition_e3))
> mutex.wait(condvar);
>
> assert (condition_e1 || (condition_e2 && condition_e3));
>
> mutex.unlock();
>
> So you see, a mechanism for waiting for multiple synchro objects isn't
> even needed to solve this type of problem. What you need is to express
> your predicates in terms of the state of shared data; then you can use
> a single condition variable, to wait for a an arbitrarily complex
> predicate to become true.

I'm not sure if the above will help me achieve the intended effect. I
want my thread to do different processings when different subsets of
events (out of a master event set) get together signaled (These subsets
get signaled based on arbitrarily complex predicates). Not only that, I
want my thread to go into a completely idle/wait state when none of the
predicates become true. I originally came up with the following
solution:

while (1)
{
if (predicate1)
DoProcessing1();
else if (predicate2)
DoProcessing2();
...
else if (predicateN)
DoProcessingN();

// Sleep (1);
}

This has a major drawback that the thread is executing even when none
of the predicates is true by polling all the if's. If I
skip the call to Sleep(1), CPU gets 100% busy and the rest of the
application becomes highly unresponsive (I'd like to avoid getting into
the arena of altering thread and process prioritizations.) If, however,
I do use Sleep(1), then the thread doesn't appear busy 'enough' in the
TaskManager CPU usage column eventhough I know beforehand that it ought
to be busier. The thread is dealing with complex asynchronous
conditions, and when the right sets of conditions get met, I'd like it
to finish the required processing by availing as much of the CPU as
possible (no Sleep's whatsoever). Basically, I'm looking for a callback
approach to processing rather than a polling approach.

BTW, I may have misundertood your mutex solution. Assuming there were
no typos in what you suggested, would you mind explaining it further?
Thanks a ton!

> Short of using condition variables, what you can do is implement the
> following hack. Use WaitForMultipleObjects to wait until any of the
> events are fired, essentially the condition e1 || e2 || e3 .
> If e1 is fired, the wait condition is satisfied, since
> you clearly have e1 || (e2 && e3). Otherwise if e2 is fired, then wait
> for e1 || e3, or if e3 is fired, wait for e1 || e2.
>

[Duane Bozarth]

Burke Lantis wrote:
>
> In article <slrn983mb...@ashi.FootPrints.net>,
> k...@ashi.footprints.net wrote:
> > On Wed, 07 Feb 2001 22:19:45 GMT, Burke Lantis
> <burke...@hotmail.com> wrote:
> >

....snip...

As shown, there will be no Sleep if any condition is satisfied until its
processing is finished...however, if another predicate prior (in the
sequential test list) to the one just finished is satisfied before that
processing is finished, it won't get a chance to start until Sleep
finishes...

> BTW, I may have misundertood your mutex solution. Assuming there were
> no typos in what you suggested, would you mind explaining it further?
> Thanks a ton!
>

What he's saying is write a wrapper around the API that looks for an
event you define. This event is a discernable condition predicate...

[Charles Bryant]

In article <95uku6$1jg$1...@nnrp1.deja.com>,

Burke Lantis <burke...@hotmail.com> wrote:
> I

>want my thread to do different processings when different subsets of
>events (out of a master event set) get together signaled (These subsets
>get signaled based on arbitrarily complex predicates). Not only that, I
>want my thread to go into a completely idle/wait state when none of the
>predicates become true. I originally came up with the following
>solution:
>
>while (1)
>{
> if (predicate1)
> DoProcessing1();
> else if (predicate2)
> DoProcessing2();
> ...
> else if (predicateN)
> DoProcessingN();
>
> // Sleep (1);
>}
>
>This has a major drawback that the thread is executing even when none
>of the predicates is true by polling all the if's.

Try this method. Suppose that all predicates are boolean expressions
of events (i.e. e1, e2 & e3, e4 || (e5 && e6), etc).

for (;;) {
set 'lp' to be the list of all events: e1, e2, ... eN
for (;;) {
wait for any event in 'lp'
let eX be the event that was set and terminated the wait
remove eX from 'lp'
if (predicate1) {
DoProcessing1();
break;
} else if (predicate2) {
DoProcessing2();
break;
} ...
}
}

To see how this works, suppose one predicate is 'e1 || (e2 && e3)'.
We wait for any of e1, e2, or e3. If e2 is set we now wait on either
e1 or e3, and when either is set we perform the processing and go
back to waiting for the complete set again.

--
Eppur si muove