[fpc-devel] Multithreading wait for

[Martin Friebe]

Mattias Gärtner wrote:
> 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.
>
>   
"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