Qu'est-ce que le workshopping?

Le work stealing (vol de travail) est un mécanisme d'équilibrage de charge dans les systèmes multithread, où un thread inactif "vole" des tâches de la file d'attente d'un autre thread occupé.

Caractéristiques clés:

• Décentralisé: Chaque thread gère sa propre file de tâches.
• Actif: Le thread inactif cherche activement du travail chez les autres.
• Haute performance: Efficace pour les tâches avec une charge inégale.

En Golang, il est utilisé dans le planificateur (scheduler) pour répartir les goroutines entre les threads du système d'exploitation (M). Lorsqu'un M termine son travail actuel (le paquet de goroutines sur P), il cherche des goroutines chez d'autres P via leurs files locales.

// Pseudocode illustrant le concept de work stealing
package main

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

type Task struct {
	id int
}

// Simulation de la file de tâches
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
}

// Tentative de "vol" d'une tâche d'une autre file
func (q *TaskQueue) StealTask() (Task, bool) {
	q.mu.Lock()
	defer q.mu.Unlock()
	if len(q.tasks) < 2 { // Ne pas voler si peu de tâches
		return Task{}, false
	}
	// Voler depuis le milieu ou la fin pour éviter les conflits avec l'extraction locale
	index := len(q.tasks) / 2
	task := q.tasks[index]
	q.tasks = append(q.tasks[:index], q.tasks[index+1:]...)
	return task, true
}

// Simulation d'un worker
func worker(id int, localQueue *TaskQueue, otherQueues []*TaskQueue, wg *sync.WaitGroup) {
	defer wg.Done()

	for {
		// Essayer de prendre une tâche de la file locale
		task, ok := localQueue.GetLocalTask()
		if ok {
			fmt.Printf("Worker %d exécute tâche %d localement\n", id, task.id)
			time.Sleep(100 * time.Millisecond) // Simulation de travail
			continue
		}

		// Si la file locale est vide, essayer de voler
		stolen := false
		for _, queue := range otherQueues {
			if queue == localQueue {
				continue // Ne pas voler chez soi
			}
			task, ok := queue.StealTask()
			if ok {
				fmt.Printf("Worker %d a volé tâche %d\n", id, task.id)
				time.Sleep(100 * time.Millisecond) // Simulation de travail
				stolen = true
				break // Sortir après un vol réussi
			}
		}

		if !stolen {
			// Si on n'a pas pu voler, il n'y a peut-être plus de tâches
			// Dans un planificateur réel, il y aurait des mécanismes plus complexes pour finir
			// Pour la démo, sortir après un délai
			fmt.Printf("Worker %d est inactif, en attente...\n", id)
			time.Sleep(50 * time.Millisecond)
			// En scénario réel, ici il y aurait un mécanisme de fin ou de parking
			// return // Pour la démo, on permet de sortir
			break // Pour simplifier la simulation
		}
	}
}

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

	// Distribuer les tâches de manière non uniforme pour démonstration
	for i := 0; i < numTasks; i++ {
		queueIndex := i % 2 // Plus de tâches pour les deux premiers workers
		taskQueues[queueIndex].AddTask(Task{id: i})
	}

	var wg sync.WaitGroup
	for i := 0; i < numWorkers; i++ {
		wg.Add(1)
		// Passer les références à toutes les queues pour que le worker puisse "voler"
		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("Toutes les tâches sont terminées")
}

Avantages:

• Équilibre bien la charge, surtout avec des travailleurs "affamés" et "satisfaits".
• Réduit le temps d'inactivité des threads de travail.

Inconvénients:

• Peut augmenter les coûts d'accès aux files distantes (concurrence pour les verrouillages).
• Plus difficile à implémenter et déboguer comparé aux planificateurs centralisés.

En Golang, le work stealing se produit entre P (processeurs) et leurs files locales de goroutines. Lorsqu'un M (fil du système d'exploitation), associé à P, termine de traiter ses goroutines locales, il tente de voler des goroutines de la file globale ou des files locales d'autres P.