Off the top of my head I can think of a couple of approaches which I'll begin to outline here. If you need a more detailed explanation, I'd be glad to elaborate. Note that I have NOT attempted to code to test either of these (yet), so take them with a grain of salt.
The first approach relies on a central dispatcher (the main thread) to coordinate a pool of worker threads and a 'work' queue (of folders). The central dispatcher initializes the thread pool to its minimum size and assigns the root folder to the first worker thread, then signals it to wake up.
Each worker thread starts in an idle state, looping until it receives a 'wake up' signal. It then checks if it's been assigned a folder to process, and begins iterating through that folder's contents. The worker thread submits any files that match the pattern to the 'found' list (or just prints it to System.out).
Any subfolders are added back into the 'work' queue (and the main thread is signalled). Afterwards, the worker thread reenters the 'idle' state (and the main thread is signalled again). Upon waking up, it should either be assigned a new folder which it starts processing the same way. Otherwise, the thread can terminate itself.
The main thread waits until it receives a signal from any worker thread. It first checks if the work queue is empty. If not, then it checks if there any worker threads that are idle. While there are any idle worker threads (and the work queue is non-empty), pop the first folder off the work queue and assign it to that thread, and signal it to wake up. The main thread then goes back to waiting.
If there are no idle threads, then check the current thread pool size against the maximum configured size. If the pool is already at maximum, then the main thread goes back to sleep (basically waiting until a thread becomes idle). Otherwise, while the pool isn't at maximum, create a new thread, add it to the pool, and assign it the first folder in the work queue, then wake it up.
If the main thread wakes up with the work queue empty, then first it checks if there are any idle threads and the worker thread pool is larger than the configured minimum. If so, the main thread can elect to wake up idle threads (with no assigned folder, so they'll terminate) and remove them from the pool. If the thread pool is already at a minimum, then again the main thread just goes back to waiting. Note that this 'downsizing' step may be unnecessary optimization (since worker threads shouldn't be consuming CPU cycles waiting anyway).
If all threads are idle and the work queue is empty then the main thread knows it's done and can signal all remaining worker threads to wake up and terminate themselves.
The trick here is all in the signaling between the main thread and the worker threads, and synchronization on the work queue (and possibly the 'found files' bin).
(Also, to simplify things a bit, one can opt for a fixed-size thread pool.)
The alternative approach doesn't involve a central dispatcher, but uses a fixed pool of worker threads sleeping for random intervals, periodically waking up to check if either a) the work queue has an item, or b) all work has been done.
The main thread just initializes the thread pool, places the root folder at the head of the work 'queue' then starts up all worker threads. It then waits for a signal telling it that all work is done and it can clean up (interrupt all the remaining worker threads to wake them up and terminate themselves).
Each worker thread starts up in a non-idle state and checks the work queue. The first thread should see the root folder, which it pops off the queue and begins processing it similar to the above. All the other threads upon starting should see an empty queue and go to sleep.
When a worker thread wakes up, it checks if the work queue has any folders remaining to be processed, and if so, works on it, setting its 'idle' flag to false. When it's done with the current folder, it checks the work queue again. If the work queue is empty, it sets its 'idle' flag.
When a worker thread finds an empty queue (either upon waking up or after processing), it checks all the other threads if they're 'idle'. If it finds at least one other thread still working then it goes to sleep for a random interval.
If all other threads are 'idle' and the work queue is empty, the thread can terminate itself. Before doing so, it interrupts or signals the main thread so the main thread can do the clean up for the rest of the other threads.
This approach can also be adapted to use a flexible sized thread pool that can dynamically grow or shrink as needed, but that just puts more complex logic into the worker threads which I won't go into for now.
