<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><div>On Jan 28, 2010, at 11:36 AM, Michael Ash wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div>On Thu, Jan 28, 2010 at 12:20 PM, Daniel A. Steffen <<a href="mailto:dsteffen@apple.com">dsteffen@apple.com</a>> wrote:<br><blockquote type="cite"><br></blockquote><blockquote type="cite">On Jan 28, 2010, at 7:07 AM, Mario Schwalbe wrote:<br></blockquote><blockquote type="cite"><blockquote type="cite">1. Let's assume someone manages to submit n jobs that block each other causing a<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">deadlock on a machine having n processors. The thread pool implementation isn't able<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">to execute any other jobs anymore, so the application can be considered erroneous/dead.<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">The work queue implementation is still able to execute jobs waiting in the queue, so<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">the application (as a whole) can still make some progress, but cannot finish either,<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">because - assuming the results of those blocked jobs are important - it at some point<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">has to wait for their results (dispatch_group_wait()) which will block forever as well.<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"><br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">2. A deadlock requires a cycle in the dependency graph. But jobs submitted that are<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">still waiting in the queue, won't be executed yet, and, hence, won't be able to acquire<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">any resource to prevent other jobs from executing.<br></blockquote></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">not necessarily a cycle, a dependency chain longer than the size of the thread pool is sufficient:<br></blockquote><blockquote type="cite"> sem1 = dispatch_semaphore_create(0);<br></blockquote><blockquote type="cite"> sem2 = dispatch_semaphore_create(0);<br></blockquote><blockquote type="cite"> dispatch_async(q, ^{dispatch_semaphore_wait(sem1);});<br></blockquote><blockquote type="cite"> dispatch_async(q, ^{dispatch_semaphore_wait(sem2); dispatch_signal(sem1);});<br></blockquote><blockquote type="cite"> dispatch_async(q, ^{dispatch_signal(sem2);});<br></blockquote><blockquote type="cite"><br></blockquote><blockquote type="cite">this will deadlock if the pool size is 2 but work correctly with a larger pool (or with the workqueue implementation)<br></blockquote><br>Or to put it another way, every dispatch block has an implicit<br>dependency on the thread pool itself, so when you add that to the<br>analysis, this situation *does* have a cycle, because the first two<br>acquire thread pool resources, and the last two wait on thread pool<br>resources before they can run.<br><br>This is something to watch out for even on the Mac, because the thread<br>pool maxes out at, I believe, 512 threads. It's tough, but not<br>impossible, to hit that number inadvertently and have everything seize<br>up.<font class="Apple-style-span" color="#000000"><font class="Apple-style-span" color="#144FAE"><br></font></font></div></blockquote><br></div><div>Yes, there is a finite limit to threads even on a mac. :) The thread workqueue code in the kernel hooks before and after the thread context switch so it can monitor how long threads have been blocked on I/O (besides hooking thread yields). If threads have been blocked for a while it will add more threads to the work pool. If threads have been "parked" (or not doing anything) for a while it will also reduce the pool size as well.</div><div><br></div><div>Before doing a similar implementation like apple's I partially implemented some kernel code that would send "hints" (via kevents) to an user level thread manager about creating new threads. Unfortunately that didn't seem to work so well. It seemed that it would stall for a relatively long period of time when a bunch of work items where submitted to the work queue. Having the kernel create the new threads seems to do much better.</div><div><br></div><div>-stacey.</div></body></html>