Wat is workshopping?

Work stealing is een load balancing mechanisme in multithreaded systemen, waarbij een inactieve thread taken 'steelt' uit de wachtrij van een andere bezette thread.

Belangrijke kenmerken:

• Gedecentraliseerd: Elke thread beheert zijn eigen lokale taakwachtrij.
• Actief: Inactieve threads zoeken actief naar werk bij anderen.
• Hoge prestaties: Efficiënt voor taken met ongelijke belasting.

In Golang wordt het gebruikt in de scheduler om goroutines over de systeemthreads (M) te verdelen. Wanneer een M zijn huidige werk (pakket goroutines op P) heeft voltooid, zoekt hij goroutines bij andere P via hun lokale wachtrijen.

// Pseudo-code die het concept van work stealing demonstreert
package main

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

type Task struct {
	id int
}

// Simulatie van een taakwachtrij
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
}

// Poging tot "stelen" van een taak uit een andere wachtrij
func (q *TaskQueue) StealTask() (Task, bool) {
	q.mu.Lock()
	defer q.mu.Unlock()
	if len(q.tasks) < 2 { // Niet "stelen" als er weinig taken zijn (optimalisatie)
		return Task{}, false
	}
	// Stelen uit het midden of einde, om conflicten met lokale extractie te voorkomen
	index := len(q.tasks) / 2
	task := q.tasks[index]
	q.tasks = append(q.tasks[:index], q.tasks[index+1:]...)
	return task, true
}

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

	for {
		// Proberen een taak uit de lokale wachtrij te halen
		task, ok := localQueue.GetLocalTask()
		if ok {
			fmt.Printf("Worker %d voert taak %d uit\n", id, task.id)
			time.Sleep(100 * time.Millisecond) // Simulatie van werk
			continue
		}

		// Als de lokale wachtrij leeg is, proberen te stelen
		stolen := false
		for _, queue := range otherQueues {
			if queue == localQueue {
				continue // Niet stelen van jezelf
			}
			task, ok := queue.StealTask()
			if ok {
				fmt.Printf("Worker %d stal taak %d\n", id, task.id)
				time.Sleep(100 * time.Millisecond) // Simulatie van werk
				stolen = true
				break // Succesvol gestolen, uit de diefstal-lus
			}
		}

		if !stolen {
			// Als niet gestolen, mogelijk geen taken meer
			// In een echte scheduler zijn er complexere afsluitmechanismen
			// Voor demonstratie, gewoon stoppen na enige tijd
			fmt.Printf("Worker %d is inactief, wacht...\n", id)
			time.Sleep(50 * time.Millisecond)
			// In een echt scenario zou hier een afsluit- of parkmechanisme zijn
			// return // Voor demonstratie, laten we het hier stoppen
			break // Vereenvoudiging van de simulatie
		}
	}
}

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

	// Verdeel taken ongelijk voor de demonstratie van work stealing
	for i := 0; i < numTasks; i++ {
		queueIndex := i % 2 // Meer taken bij de eerste twee workers
		taskQueues[queueIndex].AddTask(Task{id: i})
	}

	var wg sync.WaitGroup
	for i := 0; i < numWorkers; i++ {
		wg.Add(1)
		// Geef referenties door naar alle wachtrijen, zodat de worker kan "stelen"
		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("Alle taken voltooid")
}

Voordelen:

• Goede balans van de belasting, vooral bij "hongerige" en "verzadigde" workers.
• Vermindert de inactiviteitstijd van worker threads.

Nadelen:

• Kan overhead verhogen door toegang tot externe wachtrijen (concurrentie op locks).
• Moeilijker te implementeren en debuggen dan gecentraliseerde planners.

In Golang gebeurt work stealing tussen P (processors) en hun lokale goroutine wachtrijen. Wanneer een M (OS thread), gekoppeld aan P, zijn lokale goroutines heeft afgehandeld, probeert hij goroutines te stelen uit de globale wachtrij of van andere P's lokale wachtrijen.