ForkJoin Idee

Beginner Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

ForkJoinPool zerlegt Aufgaben rekursiv (fork) und kombiniert Ergebnisse (join). Gut für divide-and-conquer wie paralleles Sortieren.

Muster kennen, nicht jedes API-Detail.

Work-Stealing-Pool: ForkJoinPool [1].

Wo gebraucht

Parallel Streams, rekursive Parallelisierung von Divide-and-Conquer, Work-Stealing in der JVM. Passt zu Merge-Sort-artigen Aufgaben auf Mehrkernmaschinen.

Vertiefung

Das ForkJoin-Framework zerlegt eine grosse Berechnung in kleinere Tasks. fork stellt eine Teilaufgabe zur möglichen parallelen Bearbeitung bereit, join wartet auf ihr Ergebnis. Kleine Aufgaben werden direkt berechnet, damit Verwaltungsaufwand und zu feine Aufteilung begrenzt bleiben.

Worker verwenden Work Stealing: Ein untätiger Worker übernimmt Aufgaben aus der Warteschlange eines ausgelasteten Workers. Das balanciert unregelmässige Teilbäume dynamisch. Gut geeignet sind weitgehend unabhängige, CPU-lastige Berechnungen mit überschaubaren Ergebniskombinationen.

Schwierigkeitsstufen

Basisfall und Zerlegungsschwelle einer Task festlegen.
Einen Teil direkt berechnen und einen anderen parallel ausführen.
Granularität und Lastverteilung für reale Kosten abstimmen.

Fallstricke

Blockierende I/O innerhalb vieler Tasks kann den Worker-Pool ausbremsen. Eine zu kleine Schwelle erzeugt mehr Schedulingkosten als Rechengewinn, eine zu grosse lässt Parallelität ungenutzt.

Sources

[1]https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/ForkJoinPool.html Return to text

University approvals: 0

Tasks

Question 1

Wofür ist ForkJoin typischerweise gedacht?

Nur GUI-Events

Rekursive Zerlegung paralleler Teilaufgaben

Nur Datei-I/O ohne CPU

Nur Hashing

Question 2

Warum braucht eine ForkJoin-Aufgabe eine sinnvolle Grössenschwelle?

Damit kleine Aufgaben direkt berechnet und Schedulingkosten begrenzt werden.

Damit nur ein Worker jemals Arbeit erhält.

Damit join grundsätzlich vermieden wird.

Damit jede Teilaufgabe blockierende I/O ausführt.

Question 3

Summiere den halboffenen Bereich [lo, hi) rekursiv durch Teilen in zwei Teilbereiche.

Hint

Ein halbierter Index kann mit Ganzzahldivision berechnet werden. Statische rekursive Aufrufe benötigen keine Objektinstanz.

class DivideSum {
  static int sumRange(int[] a, int lo, int hi) {
    // TODO
    return 0;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Beginner
Completed: 0 users

Creator

Best

BestBuddy