Programma Lezione 48 di 148 · Macchine prese in prestito
Macchine prese in prestito

Prendi in prestito il triage: ordinare una coda di lavori

Perché è importante "Usa una coda di priorità" è il riflesso per qualsiasi coda con priorità. Risponde a "chi conta di più?" quando la vera domanda spesso è "chi può aspettare di meno?". Altri campi rispondono a quella domanda da molto tempo.

Tre sportelli

Il pronto soccorso di un ospedale. Un infermiere di triage mette ogni arrivo in una categoria, e ogni categoria ha un tempo obiettivo entro cui essere visitati: nel diffuso sistema Manchester, subito, entro 10 minuti, 60, 120 o 240. Quando un medico è libero, il paziente successivo non è semplicemente il più grave nella sala: un paziente standard che sta per superare il suo obiettivo può passare prima di uno urgente arrivato un minuto fa che ha ancora tempo.

Il check-in in aeroporto. Ci sono file separate per premium ed economy. Dentro una fila, le persone vengono servite in ordine di arrivo. Ma quando un volo sta per chiudere, il personale percorre la fila economy chiamando avanti quel volo, prima dei passeggeri premium i cui voli partono più tardi.

Lo sportello restituzioni di una biblioteca. Una sola fila, servita rigorosamente in ordine. Nessuno viene mai superato, e l'urgenza di nessuno viene considerata.

Confronta prima di scrivere codice

  1. A ogni sportello, che cosa decide chi viene servito dopo?
  2. Quali sportelli possono far aspettare qualcuno per sempre? Quali possono far aspettare troppo un caso urgente?
  3. L'ospedale e l'aeroporto non si somigliano per niente. Che cosa condividono? Scrivilo come una frase che non menzioni né ospedali né aerei.
  4. In aeroporto, perché basta guardare l'inizio di ogni fila?

Il problema di arrivo

Un sistema di lavori in background gira su un solo worker che impiega esattamente un minuto per lavoro. I lavori sono interattivi (priorità 1), standard (2) o batch (3), e ogni priorità ha una promessa di servizio: il tempo massimo che un lavoro di quella priorità può aspettare prima di iniziare. Lo scheduler attuale esegue sempre il lavoro in attesa con la priorità più alta, e ogni pomeriggio i lavori batch mancano la loro promessa.

Tocca a te

Scrivi order(jobs, max_wait). jobs è una lista di {"id", "arrive", "priority"} ordinata per arrive (minuti interi); max_wait associa la priorità al numero massimo di minuti che un lavoro può aspettare. Restituisci gli id dei lavori nell'ordine in cui il worker li esegue. Il worker esegue un lavoro al minuto: un lavoro inizia al più tardi tra il suo arrivo e la fine del lavoro precedente, e la sua attesa è l'inizio meno l'arrivo. Regola: nessun lavoro può aspettare più di max_wait[priority]. Tutti i giorni di prova si possono servire senza lavori in ritardo; con {1: 3, 2: 20, 3: 60} un giorno ha circa 1,000 lavori.

Hai notato un problema in questa lezione? Segnalalo · Chiedi qualcosa su questa lezione

Questo esercizio si apre presto

Finisci la lezione precedente e questa si sblocca. L'intero corso è gratuito, senza account, e puoi leggere questa lezione subito.