[Insight-developers] Threading Model already had Deadlock issues

[Bill Lorensen]

Hmmm...

Why haven't we seen this in over 10 years of practice? Do you have
real-world examples that illustrate the deadlock?

Bill

On Tue, Jul 12, 2011 at 1:30 PM, Bradley Lowekamp
<blowekamp at mail.nih.gov> wrote:
> Hello,
>
> I have been working with Dan trying to change the ITK threading model to use OpenMP. We have been very concerned about potential deadlock conditions arising around the use of itk::Barrier, or other threading methodologies to wait for N thread. However, in looking through ITK current threading model, I also see a large flaw which became apparent after looking at the following code:
>
>
> // Callback routine used by the threading library. This routine just calls
> // the ThreadedGenerateData method after setting the correct region for this
> // thread.
> template< class TOutputImage >
> ITK_THREAD_RETURN_TYPE
> ImageSource< TOutputImage >
> ::ThreaderCallback(void *arg)
> {
>  ..
>
>  threadId = ( (MultiThreader::ThreadInfoStruct *)( arg ) )->ThreadID;
>  threadCount = ( (MultiThreader::ThreadInfoStruct *)( arg ) )->NumberOfThreads;
>
>  str = (ThreadStruct *)( ( (MultiThreader::ThreadInfoStruct *)( arg ) )->UserData );
>
>  // execute the actual method with appropriate output region
>  // first find out how many pieces extent can be split into.
>  typename TOutputImage::RegionType splitRegion;
>  total = str->Filter->SplitRequestedRegion(threadId, threadCount,
>                                            splitRegion);
>
>  if ( threadId < total )
>    {
>    str->Filter->ThreadedGenerateData(splitRegion, threadId);
>    }
>  // else
>  //   {
>  //   otherwise don't use this thread. Sometimes the threads dont
>  //   break up very well and it is just as efficient to leave a
>  //   few threads idle.
>  //   }
>
>  return ITK_THREAD_RETURN_VALUE;
> }
>
>
> This say that currently, IITK does not guarantee that ThreadedGenerateData will be executed by N Threads. The default splitter splits orthogonal to the slowest axis. So if you have more threads then slices you are already bound for deadlock. Or in more general if S is the number of slices, there will be a not calling thread if (S%N)<N/2, and again on the right filter bound for deadlock. As N gets bigger this has a greater potential to occur.  It's amazing this hasn't been encountered more frequently.
>
> Brad
>
>
> _______________________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Kitware offers ITK Training Courses, for more information visit:
> http://kitware.com/products/protraining.html
>
> Please keep messages on-topic and check the ITK FAQ at:
> http://www.itk.org/Wiki/ITK_FAQ
>
> Follow this link to subscribe/unsubscribe:
> http://www.itk.org/mailman/listinfo/insight-developers
>