Concurrent Work Stealing with a Thread Pool in Rust

Work stealing is a powerful technique for load balancing in concurrent systems. This challenge asks you to implement a basic work-stealing thread pool in Rust, allowing threads to dynamically steal tasks from each other to maximize utilization and minimize idle time. This is particularly useful in scenarios where tasks arrive at irregular intervals or have varying execution times.

Problem Description

You are to implement a thread pool that utilizes work stealing. The thread pool should manage a queue of tasks (represented as Box<dyn FnOnce() + Send + 'static>), and a set of worker threads. Each worker thread should continuously attempt to dequeue tasks from its own local queue. If a worker's queue is empty, it should attempt to "steal" a task from the queue of another worker thread. The stealing process should be designed to minimize contention and ensure fairness.

Key Requirements:

Task Queue: Each worker thread must have its own local queue to hold tasks.
Work Stealing: When a worker's queue is empty, it should attempt to steal a task from another worker's queue. Stealing should be done from the tail of the target queue to minimize contention.
Thread Pool Management: The thread pool should provide methods to submit tasks and shut down gracefully.
Thread Safety: All operations on the queues and thread pool state must be thread-safe.
Graceful Shutdown: The thread pool should allow for a graceful shutdown, ensuring all submitted tasks are completed before termination.

Expected Behavior:

Tasks submitted to the thread pool should be executed concurrently by the worker threads.
When a worker thread has no tasks in its own queue, it should actively attempt to steal tasks from other workers.
The thread pool should shut down gracefully when requested, waiting for all tasks to complete.
The system should demonstrate reasonable load balancing, with threads generally staying busy.

Edge Cases to Consider:

Empty thread pool (no workers).
All workers idle simultaneously.
Tasks arriving much faster than they can be processed.
Tasks with very short or very long execution times.
Multiple threads attempting to steal from the same queue simultaneously.

Examples

Example 1:

Input: ThreadPool with 4 workers, submitting 10 tasks.
Output: All 10 tasks are executed.  The execution order is non-deterministic but all tasks complete.
Explanation: The 4 workers will initially process the first 4 tasks.  The remaining 6 tasks will be distributed among the workers, potentially with stealing occurring as workers finish their initial tasks.

Example 2:

Input: ThreadPool with 2 workers, submitting 1 task.
Output: The single task is executed by one of the workers.
Explanation: One worker will pick up the task and execute it. The other worker will remain idle.

Example 3: (Edge Case)

Input: ThreadPool with 4 workers, submitting 0 tasks.
Output: The thread pool shuts down gracefully without executing any tasks.
Explanation: The workers will terminate without doing any work.

Constraints

The number of worker threads should be configurable at thread pool creation.
The task queue should be implemented using a Vec for simplicity. Consider using a more efficient data structure in a production environment.
The thread pool should be able to handle at least 1000 tasks without significant performance degradation.
Stealing should be performed in a round-robin fashion among the other workers.
The FnOnce() closure should be Send + 'static to ensure thread safety.

Notes

Consider using Mutex and Condvar to protect shared data and coordinate worker threads.
The work-stealing algorithm can be further optimized, but a basic implementation is sufficient for this challenge.
Focus on correctness and thread safety first, then consider performance optimizations.
Think about how to handle panics within the tasks. Should they be caught and logged, or should they terminate the worker thread? (For this challenge, panics within tasks should terminate the worker thread).
The round-robin stealing strategy is a simple approach; more sophisticated strategies exist.