Work-Stealing Scheduling Algorithm

Work-stealing is a dynamic load balancing technique used in parallel computing. In a multi-threaded environment, if a thread finishes its task queue, it can “steal” tasks from the queue of another thread that is still busy. This ensures better utilization of available resources and minimizes idle time for threads. The work-stealing algorithm is crucial for optimizing performance in multi-core processors.

Solution

Below are simplified code examples in Java, C++, and Python that demonstrate a basic version of the work-stealing algorithm.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.concurrent.ConcurrentLinkedQueue;

public class WorkStealingScheduler {
    ConcurrentLinkedQueue<Runnable> taskQueue = new ConcurrentLinkedQueue<>();

    public void addTask(Runnable task) {
        taskQueue.add(task);
    }

    public void work() {
        while (true) {
            Runnable task = taskQueue.poll();
            if (task != null) {
                task.run();
            } else {
                // Steal work from another queue
                ConcurrentLinkedQueue<Runnable> anotherQueue = findAnotherQueue();
                task = anotherQueue.poll();
                if (task != null) {
                    task.run();
                }
            }
        }
    }

    public ConcurrentLinkedQueue<Runnable> findAnotherQueue() {
        // Implementation to find another task queue to steal from
        return new ConcurrentLinkedQueue<>();
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <queue>
#include <mutex>
#include <thread>

std::queue<std::function<void()>> taskQueue;
std::mutex mtx;

void work() {
    while (true) {
        std::function<void()> task;
        {
            std::lock_guard<std::mutex> lock(mtx);
            if (!taskQueue.empty()) {
                task = taskQueue.front();
                taskQueue.pop();
            }
        }

        if (task) {
            task();
        } else {
            // Steal work from another queue
            std::queue<std::function<void()>> anotherQueue = findAnotherQueue();
            if (!anotherQueue.empty()) {
                task = anotherQueue.front();
                anotherQueue.pop();
                task();
            }
        }
    }
}

std::queue<std::function<void()>> findAnotherQueue() {
    // Implementation to find another task queue to steal from
    return {};
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import deque
from threading import Lock

task_queue = deque()
queue_lock = Lock()

def work():
    while True:
        task = None
        with queue_lock:
            if task_queue:
                task = task_queue.popleft()

        if task:
            task()
        else:
            # Steal work from another queue
            another_queue = find_another_queue()
            if another_queue:
                task = another_queue.popleft()
                if task:
                    task()

def find_another_queue():
    # Implementation to find another task queue to steal from
    return deque()

Key Takeaways

Work-stealing is an effective load balancing strategy in multi-threaded environments.
Threads that become idle can steal tasks from busier threads to minimize idle time.
Work-stealing is particularly useful for optimizing resource utilization in systems with multiple cores.