Lenen van triage: het ordenen van een job queue
Waarom dit ertoe doet "Gebruik een priority queue" is de reflex voor elke queue met prioriteiten. Het beantwoordt "wie is het belangrijkst?" terwijl de echte vraag vaak is "wie kan het minst wachten?". Andere velden beantwoorden die vraag al een lange tijd.
Drie bureaus
A spoedeisende hulp van een ziekenhuis. Een triageverpleegkundige plaatst elke aankomende persoon in een categorie, en elke categorie heeft een doeltijd om gezien te worden: in het veelgebruikte Manchester systeem, onmiddellijk, binnen 10 minuten, 60, 120 of 240. Wanneer een arts vrij is, is de volgende patiënt niet simpelweg de ziekste in de kamer: een standaardpatiënt die bijna zijn doeltijd overschrijdt kan voorgaan op een dringende patiënt die een minuut geleden is aangekomen en nog tijd heeft.
Inchecken op de luchthaven. Er zijn aparte rijen voor premium en economy. Binnen een rij worden mensen in volgorde van aankomst geholpen. Maar wanneer een vlucht bijna sluit, lopen medewerkers langs de economy rij en roepen die vlucht naar voren, voor de premium passagiers waarvan de vluchten later vertrekken.
A library returns desk. Eén regel, strikt in volgorde geserveerd. Niemand wordt ingehaald, en de urgentie van niemand wordt meegewogen.
Vergelijk voordat je codeert
- In elke desk, wat bepaalt wie er als volgende wordt bediend?
- Welke bureaus kunnen iemand voor altijd laten wachten? Welke kunnen een dringende zaak te lang laten wachten?
- Het ziekenhuis en de luchthaven lijken totaal niet op elkaar. Wat hebben ze gemeen? Schrijf het als één zin die geen ziekenhuizen of vliegtuigen noemt.
- Op de luchthaven, waarom is het genoeg om naar de voorkant van elke rij te kijken?
Het doel
A background job systeem draait op één worker die precies één minuut per job nodig heeft. Jobs zijn interactief (prioriteit 1), standaard (2) of batch (3), en elke prioriteit heeft een servicebelofte: de langste tijd dat een job van die prioriteit mag wachten voordat hij begint. De huidige scheduler draait altijd de wachtende job met de hoogste prioriteit, en batch jobs missen hun belofte elke middag.
Schrijf order(jobs, max_wait). jobs is een lijst van {"id", "arrive", "priority"} gesorteerd op arrive (hele minuten); max_wait koppelt prioriteit aan de meeste minuten die een job mag wachten. Geef de job ids terug in de volgorde waarin de worker ze uitvoert. De worker voert één job per minuut uit: een job begint op het latere moment van de aankomst en het einde van de vorige job, en de wachttijd is start min aankomst. Regel: mag geen job langer wachten dan max_wait[priority]. De testdagen kunnen allemaal worden afgehandeld zonder dat een job te laat is; met {1: 3, 2: 20, 3: 60} heeft een dag ongeveer 1.000 jobs.
Een probleem ontdekt in deze les? Meld het · Vraag naar deze les
Deze oefening opent binnenkort
Maak de les ervoor af voordat deze wordt ontgrendeld. De hele cursus is gratis, geen account nodig, en je kunt deze les nu lezen.
Deze browser blokkeert cookies voor learn.floati.life, dus lessen die je hier hebt afgerond kunnen niet in de juiste volgorde worden geopend. Sta cookies toe voor deze site en laad de pagina opnieuw.