Что такое воркстилинг?

Воркстилинг (work stealing) — это механизм балансировки нагрузки в многопоточных системах, где простаивающий поток (worker) "крадет" задачи из очереди другого, занятого потока.

Ключевые характеристики:

• Децентрализованный: Каждый поток управляет своей локальной очередью задач.
• Активный: Простаивающий поток активно ищет работу у других.
• Высокая производительность: Эффективен для задач с неравномерной нагрузкой.

В Golang используется в планировщике (scheduler) для распределения горутин по потокам операционной системы (M). Quando один M завершил свою текущую работу (пакет горутин на P), он ищет горутины у других P через их локальные очереди.

// Псевдокод, демонстрирующий концепцию воркстилинга
package main

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

type Task struct {
	id int
}

// Имитация очереди задач
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
}

// Попытка "украсть" задачу из другой очереди
func (q *TaskQueue) StealTask() (Task, bool) {
	q.mu.Lock()
	defer q.mu.Unlock()
	if len(q.tasks) < 2 { // Не "крадем", если мало задач (оптимизация)
		return Task{}, false
	}
	// Крадем из середины или конца, чтобы не конфликтовать с локальным извлечением
	index := len(q.tasks) / 2
	task := q.tasks[index]
	q.tasks = append(q.tasks[:index], q.tasks[index+1:]...)
	return task, true
}

// Имитация рабочего потока
func worker(id int, localQueue *TaskQueue, otherQueues []*TaskQueue, wg *sync.WaitGroup) {
	defer wg.Done()

	for {
		// Попытка взять задачу из локальной очереди
		task, ok := localQueue.GetLocalTask()
		if ok {
			fmt.Printf("Рабочий %d выполняет задачу %d локально\n", id, task.id)
			time.Sleep(100 * time.Millisecond) // Имитация работы
			continue
		}

		// Если локальная очередь пуста, пытаемся украсть
		stolen := false
		for _, queue := range otherQueues {
			if queue == localQueue {
				continue // Не крадем у себя
			}
			task, ok := queue.StealTask()
			if ok {
				fmt.Printf("Рабочий %d украл задачу %d\n", id, task.id)
				time.Sleep(100 * time.Millisecond) // Имитация работы
				stolen = true
				break // Успешно украли, выходим из цикла кражи
			}
		}

		if !stolen {
			// Если не удалось украсть, возможно, больше нет задач
			// В реальном планировщике есть более сложные механизмы завершения
			// Для демонстрации просто выходим после некоторого ожидания
			fmt.Printf("Рабочий %d простаивает, ждет...\n", id)
			time.Sleep(50 * time.Millisecond)
			// В реальном сценарии здесь был бы механизм завершения или парковки потока
			// return // Для демонстрации позволим ему выходить по условию симуляции
			break // Для упрощения симуляции
		}
	}
}

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

	// Распределяем задачи неравномерно для демонстрации воркстилинга
	for i := 0; i < numTasks; i++ {
		queueIndex := i % 2 // Больше задач у первых двух рабочих
		taskQueues[queueIndex].AddTask(Task{id: i})
	}

	var wg sync.WaitGroup
	for i := 0; i < numWorkers; i++ {
		wg.Add(1)
		// Передаем ссылки на все queues, чтобы рабочий мог "воровать"
		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("Все задачи выполнены")
}

Преимущества:

• Хорошо балансирует нагрузку, особенно при наличии "голодных" рабочих и "сытых".
• Уменьшает время простоя рабочих потоков.

Недостатки:

• Может увеличивать накладные расходы на доступ к удаленным очередям задач (конкуренция за блокировки).
• Сложнее реализовать и отладить по сравнению с централизованными планировщиками.

В Golang, воркстилинг происходит между P (процессорами) и их локальными очередями горутин. Когда M (поток ОС), связанный с P, завершает обработку локальных горутин, он пытается украсть горутины из глобальной очереди или локальных очередей других P.