¿Qué es el workshopping?

El work stealing (robo de trabajo) es un mecanismo de balanceo de carga en sistemas multihilo, donde un hilo o trabajador inactivo "roba" tareas de la cola de otro hilo ocupado.

Características clave:

• Descentralizado: Cada hilo gestiona su propia cola de tareas.
• Activo: El hilo inactivo busca activamente trabajo en otros.
• Alta eficiencia: Es efectivo para tareas con carga desigual.

En Golang, se usa en el planificador (scheduler) para distribuir goroutines entre los hilos del sistema operativo (M). Cuando un M termina su trabajo actual (el conjunto de goroutines en P), busca goroutines en otros P a través de sus colas locales.

// Pseudocódigo que demuestra el concepto de work stealing
package main

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

type Task struct {
	id int
}

// Simulación de cola de tareas
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
}

// Intento de "robar" tarea de otra cola
func (q *TaskQueue) StealTask() (Task, bool) {
	q.mu.Lock()
	defer q.mu.Unlock()
	if len(q.tasks) < 2 { // No "robamos" si hay pocas tareas
		return Task{}, false
	}
	// Robamos desde el medio o el final para evitar conflictos con la extracción local
	index := len(q.tasks) / 2
	task := q.tasks[index]
	q.tasks = append(q.tasks[:index], q.tasks[index+1:]...)
	return task, true
}

// Simulación de un worker
func worker(id int, localQueue *TaskQueue, otherQueues []*TaskQueue, wg *sync.WaitGroup) {
	defer wg.Done()

	for {
		// Intentar obtener tarea de la cola local
		task, ok := localQueue.GetLocalTask()
		if ok {
			fmt.Printf("Worker %d ejecuta tarea %d localmente\n", id, task.id)
			time.Sleep(100 * time.Millisecond) // Simulación de trabajo
			continue
		}

		// Si la cola local está vacía, intentar robar
		stolen := false
		for _, queue := range otherQueues {
			if queue == localQueue {
				continue // No robar de uno mismo
			}
			task, ok := queue.StealTask()
			if ok {
				fmt.Printf("Worker %d robó tarea %d\n", id, task.id)
				time.Sleep(100 * time.Millisecond) // Simulación de trabajo
				stolen = true
				break // Exit al éxito de robo
			}
		}

		if !stolen {
			// Si no se pudo robar, quizás no queden tareas
			// En un planificador real, habría mecanismos más complejos para terminar
			// Para demostración, simplemente salir después de un tiempo
			fmt.Printf("Worker %d está inactivo, esperando...\n", id)
			time.Sleep(50 * time.Millisecond)
			// En un escenario real, aquí habría un mecanismo de finalización o parking
			// return // Para demostración, permitimos salir
			break // Para simplificar la simulación
		}
	}
}

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

	// Distribuir tareas de manera no uniforme para demostrar el work stealing
	for i := 0; i < numTasks; i++ {
		queueIndex := i % 2 // Más tareas en los primeros dos workers
		taskQueues[queueIndex].AddTask(Task{id: i})
	}

	var wg sync.WaitGroup
	for i := 0; i < numWorkers; i++ {
		wg.Add(1)
		// Pasar referencias a todas las colas para que el worker pueda "robar"
		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("Todas las tareas han sido completadas")
}

Ventajas:

• Balancea bien la carga, especialmente con trabajadores "hambrientos" y "saciados".
• Reduce el tiempo de inactividad de los hilos de trabajo.

Desventajas:

• Puede aumentar los costos de acceso a colas remotas (competencia por bloqueos).
• Es más difícil de implementar y depurar comparado con planificadores centralizados.

En Golang, el work stealing ocurre entre P (procesadores) y sus colas locales de goroutines. Cuando un M (hilo del sistema operativo), asociado a P, termina de procesar sus goroutines locales, intenta robar goroutines de la cola global o de las colas locales de otros P.