Some notes adding to the author's questions at end:
* In addition to putting a maximum number of threads, you'll probably want to put a maximum on your integral accumulator (oh, and probably a minimum number of threads too).
* If there's no cost in switching threads between different jobs, and all jobs are truly part of a single tree of steps, then you could probably get away with a global controller. However if you have certain steps that have especially unpredictable and/or time-varying requirements, you might consider giving it a separate controller
* Because queue length can't get less than 0, you can get pretty asymmetric behavior in your controller (it can only "unload" excess threads at a given rate). This might be useful behavior, but also might be worth tuning. You can implement gain scheduling (so picking different PID values for different states), or change your error measure to something that is more symmetric.
* Consider adding a dead zone/hysteresis around your zero point.
* The D term is probably not that useful here. As you saw, the addition of the I was the big game changer. Won't go into full control theory, but one way you can think about this is that 'effort' that you're putting in is scaling the number of threads. The time integral of number of threads gives you number of items processed, which is the same units as queue length. If you find a 'measure' and an 'effort' that have the same units, then you might even find that you can skip the I term completely.
* Always worth studying the cost you see (either total resources spend on threads, or cost of volatility scaling up and down) versus what the end user sees (wait time). It's possible you can get away with a much simpler system with an appropriate hard minimum + simpler (ie maybe just P + maximum rate of change) system.