Dynamic Work Stealing in Rust for Parallel Task Execution

This challenge involves implementing a dynamic work-stealing scheduler in Rust. Work stealing is a parallel programming technique where idle threads "steal" tasks from busy threads, helping to balance the workload and improve overall performance. This is particularly useful for recursive or irregularly distributed parallel computations.

Problem Description

Your task is to build a WorkStealingScheduler in Rust that can execute a collection of tasks concurrently. The scheduler should utilize a work-stealing strategy to distribute these tasks among a pool of worker threads.

Key Requirements:

Task Representation: Define a way to represent a task. For this challenge, a task can be thought of as a closure FnOnce() -> T that returns a value of type T.
Task Deque: Each worker thread should maintain its own double-ended queue (deque) of tasks. Tasks are typically pushed and popped from one end (e.g., the "local" end) by the thread itself.
Work Stealing Mechanism: When a worker thread exhausts its local tasks, it should attempt to "steal" a task from another worker's deque. A common strategy is to steal from the opposite end of the deque (the "remote" end) to minimize contention.
Thread Pool: The scheduler should manage a pool of worker threads.
Task Submission: Provide a mechanism to submit new tasks to the scheduler.
Completion: The scheduler should ensure all submitted tasks are completed before it finishes.
Error Handling: Consider basic error handling, especially for potential panics within tasks.
Generics: The scheduler should be generic over the return type of the tasks (T).

Expected Behavior:

When tasks are submitted, they are initially placed in the deque of the worker thread that submitted them.
Worker threads continuously attempt to execute tasks from their local deques.
If a worker's local deque is empty, it tries to steal a task from another worker.
The scheduler should block until all submitted tasks are finished.

Edge Cases:

No Tasks Submitted: The scheduler should handle the case where no tasks are submitted gracefully.
Single Worker: The scheduler should function correctly even with a single worker thread.
Task Panics: If a task panics, the scheduler should ideally not crash the entire program, but rather propagate the panic or handle it in a defined way. For simplicity, propagating the panic to the main thread is acceptable.
Contention: Consider the potential for contention when multiple threads try to steal from the same deque.

Examples

Example 1: Simple Task Execution

Input:
Submit 3 tasks:
Task 1: Print "Task 1"
Task 2: Print "Task 2"
Task 3: Print "Task 3"
Using 2 worker threads.

Output:
(Tasks will be printed in an interleaved or sequential order depending on scheduler behavior)
Task 1
Task 2
Task 3

Explanation: The scheduler creates two worker threads. Tasks are distributed among them. If one thread finishes its initial tasks, it might steal one from the other. All tasks are executed, and the scheduler returns after completion.

Example 2: Recursive Task Generation (Conceptual)

Input:
Define a recursive function that submits new tasks based on a condition.
For instance, a function that calculates Fibonacci numbers recursively and submits sub-problems as tasks.
Initial call: fib(10)
Using 4 worker threads.

Output:
The computed Fibonacci number for 10, and potentially log messages from task execution showing how work is distributed and stolen.

Explanation: This scenario highlights the dynamic nature of work stealing. As tasks are generated and completed, the scheduler dynamically rebalances the work. A thread might finish its part of the Fibonacci calculation and steal a sub-problem from another thread that is also working on the Fibonacci calculation.

Example 3: Large Number of Small Tasks

Input:
Submit 1,000,000 simple tasks that increment a shared counter.
Using 8 worker threads.

Output:
The final value of the shared counter, which should be 1,000,000.

Explanation: This tests the scheduler's ability to handle a high volume of small tasks and maintain good load balancing to prevent a few threads from becoming overloaded while others remain idle.

Constraints

The scheduler should support at least 1 and up to num_cpus::get() worker threads.
Tasks are represented as FnOnce() -> T closures.
The number of tasks can range from 0 to a very large number (e.g., millions).
The duration of individual tasks can vary significantly.
The primary goal is to demonstrate a functional work-stealing implementation, not necessarily the absolute fastest possible implementation.

Notes

You'll likely need to use std::thread for managing worker threads.
For the task deque, consider using a thread-safe data structure. A std::collections::VecDeque might be suitable, but you'll need to wrap it in synchronization primitives like Mutex or Arc<Mutex<...>>. For better performance, research concurrent deques or consider a lock-free approach if you're feeling ambitious.
Communication between threads for task submission and signaling completion is crucial. Arc and Mutex will be your friends.
A common approach for work stealing is using two ends of a deque: a "local" end (where the owning thread pushes/pops) and a "remote" end (where other threads try to steal from). This helps reduce contention.
Consider how to signal to worker threads that there are no more tasks to be submitted, so they can eventually exit. This might involve a shared atomic counter for submitted tasks and a way to signal shutdown.
Think about how to collect the results of the tasks if T is not () (i.e., tasks return values). For this challenge, you can either ignore return values (treat as ()) or implement a basic mechanism to collect them. If collecting, ensure thread-safety.