What is workstiling?

Work stealing is a load balancing mechanism in multithreaded systems where an idle thread (worker) "steals" tasks from the queue of another busy thread.

Key characteristics:

• Decentralized: Each thread manages its local task queue.
• Active: An idle thread actively seeks work from others.
• High performance: Effective for tasks with uneven load.

In Golang, it is used in the scheduler to distribute goroutines across operating system threads (M). When one M finishes its current work (a set of goroutines on P), it looks for goroutines in others' local queues.

// Pseudocode demonstrating the concept of work stealing
package main

import "fmt"
import "sync"
import "time"

type Task struct {
	id int
}

// Simulated task queue
type TaskQueue struct {
	tasks []Task
	mu    sync.Mutex
}

func (q *TaskQueue) AddTask(task Task) {
	q.mu.Lock()
	defer q.mu.Unlock()
	q.tasks = append(q.tasks, task)
}

func (q *TaskQueue) GetLocalTask() (Task, bool) {
	q.mu.Lock()
	defer q.mu.Unlock()
	if len(q.tasks) == 0 {
		return Task{}, false
	}
	task := q.tasks[0]
	q.tasks = q.tasks[1:]
	return task, true
}

// Attempt to steal a task from another queue
func (q *TaskQueue) StealTask() (Task, bool) {
	q.mu.Lock()
	defer q.mu.Unlock()
	if len(q.tasks) < 2 { // Don't steal if few tasks (optimization)
		return Task{}, false
	}
	// Steal from middle or end to avoid conflict with local extraction
	index := len(q.tasks) / 2
	task := q.tasks[index]
	q.tasks = append(q.tasks[:index], q.tasks[index+1:]...)
	return task, true
}

// Worker thread simulation
func worker(id int, localQueue *TaskQueue, otherQueues []*TaskQueue, wg *sync.WaitGroup) {
	defer wg.Done()

	for {
		// Try to get a task from local queue
		task, ok := localQueue.GetLocalTask()
		if ok {
			fmt.Printf("Worker %d executing task %d locally\n", id, task.id)
			time.Sleep(100 * time.Millisecond) // Simulate work
			continue
		}

		// If local queue is empty, try to steal
		stolen := false
		for _, queue := range otherQueues {
			if queue == localQueue {
				continue // Don't steal from itself
			}
			task, ok := queue.StealTask()
			if ok {
				fmt.Printf("Worker %d stole task %d\n", id, task.id)
				time.Sleep(100 * time.Millisecond) // Simulate work
				stolen = true
				break // Successfully stole, exit stealing loop
			}
		}

		if !stolen {
			// If couldn't steal, possibly no more tasks
			// In a real scheduler, more complex termination mechanisms exist
			// For demonstration, just wait and then exit
			fmt.Printf("Worker %d is idle, waiting...\n", id)
			time.Sleep(50 * time.Millisecond)
			// In a real scenario, there would be a termination or parking mechanism here
			// return // For demonstration, allow exit based on simulation condition
			break // Simplify simulation
		}
	}
}

func main() {
	numWorkers := 4
	numTasks := 20
	taskQueues := make([]*TaskQueue, numWorkers)
	for i := range taskQueues {
		taskQueues[i] = &TaskQueue{}
	}

	// Distribute tasks unevenly for work stealing demonstration
	for i := 0; i < numTasks; i++ {
		queueIndex := i % 2 // More tasks for first two workers
		taskQueues[queueIndex].AddTask(Task{id: i})
	}

	var wg sync.WaitGroup
	for i := 0; i < numWorkers; i++ {
		wg.Add(1)
		// Pass references to all queues so worker can "steal"
		otherQueues := make([]*TaskQueue, 0, numWorkers-1)
		for j := range taskQueues {
			if i != j {
				otherQueues = append(otherQueues, taskQueues[j])
			}
		}
		go worker(i, taskQueues[i], otherQueues, &wg)
	}

	wg.Wait()
	fmt.Println("All tasks completed")
}

Advantages:

• Balances load well, especially with "hungry" and "sated" workers.
• Reduces worker thread idle time.

Disadvantages:

• May increase overhead due to remote queue access (contention for locks).
• More complex to implement and debug compared to centralized schedulers.

In Golang, work stealing occurs between P (processors) and their local goroutine queues. When an M (OS thread) associated with P finishes processing local goroutines, it attempts to steal goroutines from the global queue or other P's local queues.