Lehrplan Lektion 48 von 148 · Geliehene Maschinen
Geliehene Maschinen

Leihgabe Triage: Reihenfolge einer Job-Queue

Warum das wichtig ist "Use a priority queue" ist der Reflex für jede Warteschlange mit Prioritäten. Es beantwortet "wer ist am wichtigsten?", während die echte Frage oft "wer kann am wenigsten warten?" lautet. Andere Bereiche beantworten diese Frage schon lange.

Drei Schreibtische

A Notaufnahme eines Krankenhauses. Eine Triage-Pflegekraft ordnet jeden Patienten einer Kategorie zu, und jede Kategorie hat eine Zielzeit für die Untersuchung: im weit verbreiteten Manchester-System sofort, innerhalb von 10 Minuten, 60, 120 oder 240. Wenn ein Arzt frei wird, ist der nächste Patient nicht einfach der kränkste im Raum: ein Standardpatient, der kurz vor Ablauf seiner Zielzeit steht, kann vor einem dringenden Patienten kommen, der vor einer Minute ankam und noch Zeit hat.

Flughafen-Check-in. Es gibt getrennte Spuren für Premium und Economy. Innerhalb einer Spur werden die Leute in der Reihenfolge ihres Erscheinens bedient. Aber wenn ein Flug kurz vor dem Abflug steht, gehen die Mitarbeiter die Economy-Linie ab und rufen diesen Flug vor, vor den Premium-Passagieren, deren Flüge später abfliegen.

A Bibliothek gibt desk zurück. Eine Zeile, streng in der Reihenfolge serviert. Niemand wird jemals überholt, und die Dringlichkeit von niemandem wird berücksichtigt.

Vergleiche, bevor du programmierst

  1. Was entscheidet an jedem Schreibtisch, wer als Nächstes bedient wird?
  2. Welche Schreibtische können jemanden ewig warten lassen? Welche können einen dringenden Fall zu lange warten lassen?
  3. Das Krankenhaus und der Flughafen sehen überhaupt nicht gleich aus. Was haben sie gemeinsam? Schreibe es als einen Satz, der weder Krankenhäuser noch Flugzeuge erwähnt.
  4. Am Flughafen, warum reicht es aus, nur auf die Vorderseite jeder Spur zu schauen?

Das Ziel

Das

A Hintergrund-Jobsystem läuft auf einem Worker, der genau eine Minute pro Job benötigt. Jobs sind interaktiv (Priorität 1), Standard (2) oder Batch (3), und jede Priorität hat ein Service-Versprechen: die längste Zeit, die ein Job dieser Priorität warten darf, bevor er startet. Der aktuelle Scheduler führt immer den wartenden Job mit der höchsten Priorität aus, und Batch-Jobs verpassen ihr Versprechen jeden Nachmittag.

Du bist dran

Schreibe order(jobs, max_wait). jobs ist eine Liste von {"id", "arrive", "priority"} sortiert nach arrive (ganze Minuten); max_wait ordnet die Priorität der maximalen Minuten zu, die ein Job warten darf. Gib die job ids in der Reihenfolge zurück, in der der worker sie ausführt. Der worker führt einen Job pro Minute aus: ein Job startet zum späteren Zeitpunkt von seiner Ankunft und dem Ende des vorherigen Jobs, und seine Wartezeit ist Start minus Ankunft. Regel: darf kein Job länger als max_wait[priority] warten. Die Testtage können alle ohne verspätete Jobs bedient werden; mit {1: 3, 2: 20, 3: 60} hat ein Tag etwa 1.000 Jobs.

Ein Problem in dieser Lektion entdeckt? Melde es · Frage zu dieser Lektion

Diese Übung öffnet bald

Beende die vorherige Lektion, damit diese freigeschaltet wird. Der ganze Kurs ist kostenlos, kein Konto erforderlich, und du kannst diese Lektion jetzt direkt lesen.