I'm converting some code to use libdispatch instead of my home-grown event queue, and I'm wondering what the best approach is. There is a tree, and each task in the queue operates on a node and potentially its parent and children. Before I converted my code to libdispatch, I had a single concurrent queue and each node in the tree had a mutex. When a node was operated on, it would lock its parent, itself, and its children in that order (this isn't optimal for the application, but it was a conservative approach that meant I didn't have to think about deadlocks). Obviously this can be translated pretty directly to libdispatch, using a global concurrent queue and semaphores. However, I was wondering if (even with all the semaphores) it might be beneficial to create a serial queue for each node. In my mental model, this would eliminate blocking on threads each trying to operate on the same node – the semaphores would really only cause blocking when two adjacent nodes are being operated on. Or is it the case that a single concurrent queue would work just as well – once a task is blocked, it just grabs another one and starts that. And, if I'm using multiple serial queues, is it also beneficial to suspend the queues for the parent and children nodes while the semaphores are locked? I know the answers depend on other questions like "how long does a task take to run?" (pretty short, fraction of a second), "how many queues will you have?" (can vary a lot, but "dozens" seems reasonable), "is the tree tall or wide?" (probably more wide), and probably plenty of other things. So, hopefully this will at least help me to understand the tradeoffs involved. Thanks.
Greg, How is it that the parent is locked before the object itself? Without knowing more, that seems racy… Also, this problem shouldn't need semaphores. Queues should be sufficient, with one queue per node. Suspension also shouldn't be necessary either, just dispatch_sync() and dispatch_async(). davez On Oct 20, 2010, at 9:03 AM, Greg Pfeil wrote:
I'm converting some code to use libdispatch instead of my home-grown event queue, and I'm wondering what the best approach is. There is a tree, and each task in the queue operates on a node and potentially its parent and children.
Before I converted my code to libdispatch, I had a single concurrent queue and each node in the tree had a mutex. When a node was operated on, it would lock its parent, itself, and its children in that order (this isn't optimal for the application, but it was a conservative approach that meant I didn't have to think about deadlocks).
Obviously this can be translated pretty directly to libdispatch, using a global concurrent queue and semaphores. However, I was wondering if (even with all the semaphores) it might be beneficial to create a serial queue for each node. In my mental model, this would eliminate blocking on threads each trying to operate on the same node – the semaphores would really only cause blocking when two adjacent nodes are being operated on. Or is it the case that a single concurrent queue would work just as well – once a task is blocked, it just grabs another one and starts that.
And, if I'm using multiple serial queues, is it also beneficial to suspend the queues for the parent and children nodes while the semaphores are locked?
I know the answers depend on other questions like "how long does a task take to run?" (pretty short, fraction of a second), "how many queues will you have?" (can vary a lot, but "dozens" seems reasonable), "is the tree tall or wide?" (probably more wide), and probably plenty of other things. So, hopefully this will at least help me to understand the tradeoffs involved.
Thanks. _______________________________________________ libdispatch-dev mailing list libdispatch-dev@lists.macosforge.org http://lists.macosforge.org/mailman/listinfo.cgi/libdispatch-dev
participants (2)
-
Dave Zarzycki
-
Greg Pfeil