Scheduler

Scheduler

Der Scheduler führt Prozesse mit einem Work-Stealing-Design aus. Worker pflegen lokale Deques und stehlen voneinander, wenn sie untätig sind.

Process-Interface

Der Scheduler arbeitet mit jedem Typ, der das Process-Interface implementiert:

type Process interface {
    Init(ctx context.Context, method string, input payload.Payloads) error
    Step(events []Event, out *StepOutput) error
    Close()
}

Methode	Zweck
Init	Prozess mit Entry-Methodenname und Eingabeargumenten vorbereiten
Step	Zustandsmaschine mit eingehenden Events vorantreiben, Yields in Output schreiben
Close	Ressourcen freigeben

Der method-Parameter in Init spezifiziert welchen Einstiegspunkt aufgerufen werden soll. Eine Prozessinstanz kann mehrere Einstiegspunkte exponieren, und der Aufrufer wählt welchen er ausführen möchte. Dies dient auch als Verifikation, dass der Scheduler den Prozess korrekt initiiert.

Der Scheduler ruft Step() wiederholt auf, übergibt Events (Yield-Completions, Nachrichten) und sammelt Yields (Commands zum Dispatchen). Der Prozess schreibt seinen Status und alle Yields in den StepOutput-Buffer.

type Event struct {
    Type  EventType  // EventYieldComplete oder EventMessage
    Tag   uint64     // Korrelationstag für Yield-Completions
    Data  any        // Ergebnisdaten oder Nachrichten-Payload
    Error error      // Fehler wenn Yield fehlgeschlagen
}

Struktur

Der Scheduler startet standardmäßig GOMAXPROCS Worker. Jeder Worker hat eine lokale Deque für cache-freundlichen LIFO-Zugriff. Eine globale FIFO-Queue behandelt neue Submissions und Cross-Worker-Transfers. Prozesse werden per PID für Nachrichtenrouting verfolgt.

Arbeit finden

flowchart TD
    W[Worker braucht Arbeit] --> L{Lokale Deque?}
    L -->|hat Items| LP[Von unten LIFO poppen]
    L -->|leer| G{Globale Queue?}
    G -->|hat Items| GP[Poppen + Batch-Transfer bis zu 16]
    G -->|leer| S[Von zufälligem Opfer stehlen]
    S --> SH[StealHalfInto Opfer-Deque]

Worker prüfen Quellen in Prioritätsreihenfolge:

Priorität	Quelle	Muster
1	Lokale Deque	LIFO Pop, lock-frei, cache-freundlich
2	Globale Queue	FIFO Pop mit Batch-Transfer
3	Andere Worker	Hälfte von Opfer-Deque stehlen

Beim Poppen von global nehmen Worker ein Item und transferieren bis zu 16 weitere in Batch zu ihrer lokalen Deque.

Chase-Lev-Deque

Jeder Worker besitzt eine Chase-Lev Work-Stealing-Deque:

type Deque struct {
    buffer atomic.Pointer[dequeBuffer]
    top    atomic.Int64  // Diebe stehlen hier (CAS)
    bottom atomic.Int64  // Besitzer pusht/poppt hier
}

Der Besitzer pusht und poppt von unten (LIFO) ohne Synchronisation. Diebe stehlen von oben (FIFO) per CAS. Dies gibt dem Besitzer cache-freundlichen Zugriff auf kürzlich gepushte Items während ältere Arbeit an Stealer verteilt wird.

StealHalfInto nimmt die Hälfte der Items in einer CAS-Operation und reduziert Contention.

Adaptives Spinning

Bevor auf der Condition-Variable blockiert wird, spinnen Worker adaptiv:

Spin-Count	Aktion
< 4	Enger Loop
4-15	Thread yielden (runtime.Gosched)
>= 16	Auf Condition-Variable blockieren

Prozesszustände

stateDiagram-v2
    [*] --> Ready: Submit
    Ready --> Running: CAS by worker
    Running --> Complete: done
    Running --> Blocked: yields commands
    Running --> Idle: waiting for messages
    Blocked --> Ready: CompleteYield
    Idle --> Ready: Send arrives

Zustand	Beschreibung
Ready	Für Ausführung eingereiht
Running	Worker führt Step() aus
Blocked	Wartet auf Yield-Completion
Idle	Wartet auf Nachrichten
Complete	Ausführung beendet

Ein Wakeup-Flag behandelt Race-Conditions: Wenn ein Handler CompleteYield aufruft, während der Worker noch den Prozess besitzt (Running), setzt er das Flag. Der Worker prüft das Flag nach dem Dispatchen und reiht bei gesetztem Flag neu ein.

Event-Queue

Jeder Prozess hat eine MPSC (Multi-Producer, Single-Consumer) Event-Queue:

• Producer: Command-Handler (CompleteYield), Nachrichtensender (Send)
• Consumer: Worker draint Events in Step()

Nachrichtenrouting

Der Scheduler implementiert relay.Receiver um Nachrichten an Prozesse zu routen. Wenn Send() aufgerufen wird, schlägt er die Ziel-PID in der byPID-Map nach, pusht die Nachricht als Event in die Prozess-Queue und weckt den Prozess wenn idle durch Pushen in die globale Queue.

Shutdown

Bei Shutdown sendet der Scheduler Cancel-Events an alle laufenden Prozesse und wartet auf deren Abschluss oder Timeout. Worker beenden sich sobald keine Arbeit mehr übrig ist.

Siehe auch

• Command-Dispatch - Wie Yields Handler erreichen
• Prozessmodell - High-Level-Konzepte