10.5 2-Prozessor Scheduling

Der Maximum-Matching-Algorithmus kann beim 2-Prozessor Scheduling zur Anwendung kommen:

Gegeben: G = (V,E) gerichtet G beschreibt Vorrang-Relation zwischen Tasks

Gesucht: Schedule für 2 Prozessoren

z.B.

bedeutet: i muß vor j bearbeitet werden.

Kante (x,y) in G' besagt, daß x und y gleichzeitig bearbeitet werden können.

Bilde G' = (V,E') ungerichtet wie folgt:

(x,y) $\in$ E'$\iff$x ist nicht Vorgänger von y und y ist nicht Vorgänger von x .

Satz:

Kardinalität eines Maximum-Matchings in G' = Zahl der gleichzeitig bearbeitbaren Taskpaare.

Falls folgende Situation

auftritt und zwischen i und j bzw. k und l keine Nachfolgebeziehungen bestehen, dann kann auch zwischen i und l bzw. k und j keine Nachfolgebeziehung bestehen, d.h., der Konflikt der auftritt, wenn i parallel zu j und k parallel zu l bearbeitet wird, kann dadurch beseitigt werden, indem man i parallel zu l und k parallel zu j bearbeitet.

D.h. ersetze

durch

.