Leen triasering: die ordening van 'n job queue
Waarom dit saak maak "Gebruik 'n priority queue" is die refleks vir enige queue met prioriteite. Dit antwoord op "wie saak die meeste?" wanneer die werklike vraag dikwels "wie kan die minste wag?" is. Ander velde antwoord reeds lank op daardie vraag.
Drie lessenaars
'n hospitaal se nooddepartement. 'n triasieverpleegster plaas elke aankoms in 'n kategorie, en elke kategorie het 'n teikentyd om gesien te word: in die algemeen gebruikte Manchester-stelsel, onmiddellik, binne 10 minute, 60, 120 of 240. Wanneer 'n dokter vry is, is die volgende pasiënt nie bloot die siekste in die kamer nie: 'n standaardpasiënt wat amper hul teikentyd verbeur, kan voor 'n dringende een gaan wat 'n minuut gelede aangekom het en nog tyd het.
Lughawwekinnet.Da is daar aparte bane vir premium en ekonomie. Binne 'n baan word mense in volgorde van aankoms bedien. Maar wanneer 'n vlug wil sluit, loop personeel langs die ekonomie-ry en roep daardie vlug vorentoe, voor premium-passasiers wie se vlugte later vertrek.
A-biblioteek gee desk terug. Een reël, dieldiens streng in volgorde. Niemand word oortref nie, en niemand se dringendheid word oorweeg nie.
Vergelyk voor jy kodeer
- In elke lessenaar, wat besluit wie volgende bedien word?
- Watter desks kan iemand vir ewig laat wag? Watter kan 'n dringende saak te lank laat wag?
- Die hospitaal en die lughawe lyk glad nie dieselfde nie. Wat deel hulle? Skryf dit as een sin wat nie hospitale of vliegtuie noem nie.
- By die lughawe, waarom is dit genoeg om net na die voorkant van elke baan te kyk?
Die teiken
A agtergrond-werkstelsel hardloop op een werker wat presies een minuut per werk neem. Werke is interaktief (prioriteit 1), standaard (2) of batch (3), en elke prioriteit het 'n diensbelofte: die langste tyd wat 'n werk van daardie prioriteit mag wag voor dit begin. Die huidige skeduleerder hardloop altyd die wagende werk met die hoogste prioriteit, en batch-werke mis hul belofte elke middag.
Skryf order(jobs, max_wait). jobs is 'n lys van {"id", "arrive", "priority"} gesorteer volgens arrive (heele minute); max_wait koppel prioriteit aan die meeste minute wat 'n werk mag wag. Gee die job ids terug in die volgorde wat die worker dit uitvoer. Die worker voer een werk per minuut uit: 'n werk begin teen die later van sy aankoms en die einde van die vorige werk, en sy wag is begin minus aankoms. Rule: geen werk mag langer as max_wait[priority] wag nie. Die toetsdae kan almal bedien word sonder dat enige werk laat is; met {1: 3, 2: 20, 3: 60} het 'n dag ongeveer 1,000 werke.
Sien jy 'n probleem in hierdie les? Rapporteer dit · Vra oor hierdie les
Hierdie oefening open binnekort
Voltooi die lesie voor dit en hierdie een sal ontvanklik wees. Die hele kursus is gratis, geen rekening nodig nie, en jy kan hierdie les nou lees.
Hierdie blutser blokkeer koekies vir learn.floati.life, so lesse wat jy hier voltooi het kan nie in volgorde oopgaan nie. Laat koekies vir hierdie webwerf toe en laai nuut.