Hi all,

I'm looking for a high performance 'wait-for'.

The situation:
There are m threads working in parallel on n chunks of work (n>=m). The n chunks are indexed 0..n-1.
Sometimes one thread needs the result of some of the lower indexed chunks. For example the chunk number 5 needs chunks 0..2.
So I have a function WaitForIndex(LowerIndex: integer) which should wait until all chunks with less or equal to LowerIndex have finished.

My current approach is this:
EnterCriticalSection (try..finally)
Check if all lower chunks have finished, if yes then exit LeaveCriticalSection
RTLeventWaitFor(AnEventOfTheCurrentThread);

And each time a thread has finished a chunk, it wakes all corresponding threads.

The problem is the gap between LeaveCriticalSection and RTLeventWaitFor. During this time the other threads may finish. So there is no one left to wake up the waiting thread.

Moving the RTLeventWaitFor into the CritialSection creates a deadlock. I can use the timeout of RTLeventWaitFor and check in intervals, but criticalsections and low response times don't fit together.

Mattias

"high performance 'wait-for'. "
First think that came to mind was Spin-Locks, so you never enter a wait state. But that only works, if you know you will never have to wait for long.

Another possibility is a set of Semaphores. Each thread needs one semaphore. You can use zero wait on all semaphores of "lower" threads. Each thread sets it sem to 1 while working and to zero once finished.

You can reverse the logic: 0 eq thread is busy, 1 (via increment, not via set-value) means thread is done. Then the waitng thread tries to decrement all semaphores

Best Regards
Martin

Why don't you do it the other way around?

wait_loop:

RTLEventWaitFor (SomeChunkHasFinishedEvent);
// EnterCriticalSection;
State of chunks changed ->
   so check if all lower parts are ready, if yes then exit
// LeaveCriticalSection;
goto wait_loop;

This way, the loop only gets awakened once something changed, you check the state (in an atomic way, if at all necessary) and go back. In case another event occured between the RTLEventWaitFor and EnterCriticalSection it will go through a second time immediately.

The problem is the gap between LeaveCriticalSection and RTLeventWaitFor. During this time the other threads may finish. So there is no one left to wake up the waiting thread.

So your asking the wrong question. You don't want an efficient wait loop, you want a wait loop free from race conditions.

Moving the RTLeventWaitFor into the CritialSection creates a deadlock. I can use the timeout of RTLeventWaitFor and check in intervals, but criticalsections and low response times don't fit together.

Well, depending on what your checks do, you may not even need the critical section if you reverse the logic. Either all checked threads are finished or they aren't. If the state changed during the check, the check code will be invoked immediately, because the event will already be signalled again.

Vinzent.

If I understand RTLEventWaitFor correct, then it waits until another thread calls RTLeventSetEvent.
So I must check *before* calling RTLEventWaitFor, that some other thread is running, must I not?

It's a pool of threads.

:)
I know how to do a race condition free loop inefficiently using a spin lock. My question is, if it can be done race condition free and efficiently, to allow switching thousands of times a second without busy waiting.

The critical section is needed, because after a thread finished some work it starts some other work.

Mattias

Yes. Maybe doable with sleep.

Thanks, I will try.

Mattias

Unless it's already signalled, then it should run right through.

So I must check *before* calling RTLEventWaitFor, that some other thread is running, must I not?

No, assuming RTLEvent implements a persistent signal, not a transient one. I am not 100% sure here (so someone should check the source), but I remember that there were two versions (mimicking the Windows-Events), depending on how one would set them up. I implemented my own versions some time ago (fpc2.0.0), but that was due to some bugs and quirks in fpc's implementation, so I'm not really up to date if those are fixed now for all platforms.

That's what it should do (although the term "efficiently" may depend on some other factors like number of processing units, threads waiting, average wait time and such).

Well, in that case... Another solution would be to provide specific events for the waiting threads, but this requires quite some more amount of administrative work, so in the end it may even turn out to be less efficient. ;)

Vinzent.

Zitat von Vinzent Höfler :

Yes, that works under Linux. But the documentation does not mention it, so I'm not sure if this works under all platforms.
Maybe some other OS users can try if the following code runs through:

var
  e: PRTLEvent;
begin
  e:=RTLEventCreate;
  RTLeventSetEvent(e);
  RTLeventWaitFor(e);
  RTLeventdestroy(e);
end;

If this is guaranteed then my problem is already solved and the code work as it is. But then the documentation must mention it.
Who knows if this is a documentation bug or a linux bug?

------------------
Powered by NetMail

In our previous episode, Mattias G�rtner said:

Yes, that works under Linux. But the documentation does not mention it, so I'm not sure if this works under all platforms. Maybe some other OS users can try if the following code runs through:

Uses cthreads;

Runs through on FreeBSD.

It works at least on *nix and on Windows (the behaviour on *nix emulates the Windows behaviour).

Who knows if this is a documentation bug or a linux bug?

It was changed in 2.2.0: http://wiki.freepascal.org/User_Changes_2.2.0#RTLEvent_persistence

Jonas

Thanks.

Michael, can you add that hint to the documentation?

Mattias