Optimal scheduling for two-processor systems (Q2556224): Difference between revisions

From MaRDI portal
Created claim: Wikidata QID (P12): Q63353538, #quickstatements; #temporary_batch_1711574657256
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: Flow Networks and Combinatorial Operations Research / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Preemptive Scheduling on Two-Processor Systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounds for Certain Multiprocessing Anomalies / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounds on Multiprocessing Timing Anomalies / rank
 
Normal rank
Property / cites work
 
Property / cites work: Optimal Sequencing of Two Equivalent Processors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Erratum “Optimal Sequencing of Two Equivalent Processors” / rank
 
Normal rank
Property / cites work
 
Property / cites work: Paths, Trees, and Flowers / rank
 
Normal rank

Revision as of 11:01, 12 June 2024

scientific article
Language Label Description Also known as
English
Optimal scheduling for two-processor systems
scientific article

    Statements

    Optimal scheduling for two-processor systems (English)
    0 references
    0 references
    0 references
    1971
    0 references
    In Mehrprozessorsystemen spielt die Arbeitsreihenfolge der anstehenden Tasks eine fundamentale Rolle. Der Durchsatz dieser Systeme, bzw. die Zeit für die Fertigstellung einer gegebenen Taskmenge hängt entscheidend davon ab. Die Autoren behandeln Systeme mit zwei identischen Prozessoren. Alle Tasks haben konstante Abarbeitungszeit. Die Taskmenge ist halbgeordnet entsprechend ihren Abhängigkeitsbeziehungen. Unter Berücksichtigung der gegebenen Halbordnung wird eine Abarbeitungsreihenfolge gesucht, die kürzeste Gesamtheit ergibt. Die Taskmenge wird als zyklenfreier gerichteter Graph zugelassen. Damit gehen die Autoren über die bis dahin behandelten hierarchischen Anordnungen hinaus. Es wird ein Algorithmus für die Konstruktion einer optimalen Reihenfolge gegeben. Die Anzahl der Schritte ist von der Ordnung \(N^2\), wenn \(N\) die Anzahl der Tasks ist. Das Ergebnis verbessert auch die bisherigen Möglichkeiten für den hierarchischen Fall, in dem bisher Algorithmen der Ordnung \(N^4\) bekannt sind. Durch Zeitquantelung lassen sich Aufgaben behandeln, in denen die Abarbeitungszeit der einzelnen Tasks unterschiedlich ist. Mit einigen Einschränkungen lassen sich die Resultate auf Systeme mit mehr als zwei Prozessoren ausdehnen.
    0 references

    Identifiers