Impossible to make a cached thread pool with a size limit?

Unless I've missed something, the solution to the original question is simple. The following code implements the desired behavior as described by the original poster. It will spawn up to 5 threads to work on an unbounded queue and idle threads will terminate after 60 seconds.

tp = new ThreadPoolExecutor(5, 5, 60, TimeUnit.SECONDS,
                    new LinkedBlockingQueue<Runnable>());
tp.allowCoreThreadTimeOut(true);

The ThreadPoolExecutor has the following several key behaviors, and your problems can be explained by these behaviors.

When tasks are submitted,

1. If the thread pool has not reached the core size, it creates new threads.
2. If the core size has been reached and there is no idle threads, it queues tasks.
3. If the core size has been reached, there is no idle threads, and the queue becomes full, it creates new threads (until it reaches the max size).
4. If the max size has been reached, there is no idle threads, and the queue becomes full, the rejection policy kicks in.

In the first example, note that the SynchronousQueue has essentially size of 0. Therefore, the moment you reach the max size (3), the rejection policy kicks in (#4).

In the second example, the queue of choice is a LinkedBlockingQueue which has an unlimited size. Therefore, you get stuck with behavior #2.

You cannot really tinker much with the cached type or the fixed type, as their behavior is almost completely determined.

If you want to have a bounded and dynamic thread pool, you need to use a positive core size and max size combined with a queue of a finite size. For example,

new ThreadPoolExecutor(10, // core size
    50, // max size
    10*60, // idle timeout
    TimeUnit.SECONDS,
    new ArrayBlockingQueue<Runnable>(20)); // queue with a size

Addendum: this is a fairly old answer, and it appears that JDK changed its behavior when it comes to core size of 0. Since JDK 1.6, if the core size is 0 and the pool does not have any threads, the ThreadPoolExecutor will add a thread to execute that task. Therefore, the core size of 0 is an exception to the rule above. Thanks Steve for bringing that to my attention.