<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 &lt;<a href="mailto:dsteffen@apple.com">dsteffen@apple.com</a>&gt; 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">&nbsp; &nbsp; &nbsp; &nbsp;sem1 = dispatch_semaphore_create(0);<br></blockquote><blockquote type="cite">&nbsp; &nbsp; &nbsp; &nbsp;sem2 = dispatch_semaphore_create(0);<br></blockquote><blockquote type="cite">&nbsp; &nbsp; &nbsp; &nbsp;dispatch_async(q, ^{dispatch_semaphore_wait(sem1);});<br></blockquote><blockquote type="cite">&nbsp; &nbsp; &nbsp; &nbsp;dispatch_async(q, ^{dispatch_semaphore_wait(sem2); dispatch_signal(sem1);});<br></blockquote><blockquote type="cite">&nbsp; &nbsp; &nbsp; &nbsp;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. &nbsp;:) &nbsp;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). &nbsp; If threads have been blocked for a while it will add more threads to the work pool. &nbsp;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. &nbsp;Unfortunately that didn't seem to work so well. &nbsp; 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. &nbsp;Having the kernel create the new threads seems to do much better.</div><div><br></div><div>-stacey.</div></body></html>