Conteúdo do curso Lição 48 de 148 · Máquinas emprestadas
Máquinas emprestadas

Triagem de empréstimo: ordenando uma fila de tarefas

Por que isso importa "Use uma priority queue" é o reflexo para qualquer fila com prioridades. Ela responde "quem importa mais?" quando a pergunta real é frequentemente "quem pode esperar menos?". Outros campos têm respondido a essa pergunta por muito tempo.

Três mesas

A emergência de um hospital. Uma enfermeira de triagem coloca cada chegada em uma categoria, e cada categoria tem um tempo alvo para ser atendida: no sistema Manchester amplamente usado, imediatamente, em 10 minutos, 60, 120 ou 240. Quando um médico fica livre, o próximo paciente não é simplesmente o mais doente na sala: um paciente padrão prestes a ultrapassar seu alvo pode passar antes de um urgente que chegou há um minuto e ainda tem tempo.

Check-in de aeroporto. Existem filas separadas para premium e econômica. Dentro de uma fila, as pessoas são atendidas por ordem de chegada. Mas quando um voo está prestes a fechar, os funcionários percorrem a fila da econômica chamando aquele voo para frente, antes dos passageiros premium cujos voos saem mais tarde.

A biblioteca retorna desk. Uma linha, servida estritamente em ordem. Ninguém é ultrapassado, e a urgência de ninguém é considerada.

Compare antes de codar

  1. Em cada mesa, o que decide quem é atendido a seguir?
  2. Quais desks podem fazer alguém esperar para sempre? Quais podem fazer um caso urgente esperar demais?
  3. O hospital e o aeroporto não se parecem em nada. O que eles têm em comum? Escreva isso em uma frase que não mencione nem hospitais nem aviões.
  4. No aeroporto, por que basta olhar para a frente de cada fila?

O alvo

O sistema de tarefas em segundo plano

A roda em um worker que leva exatamente um minuto por tarefa. As tarefas são interativas (prioridade 1), padrão (2) ou em lote (3), e cada prioridade tem uma promessa de serviço: o tempo máximo que uma tarefa daquela prioridade pode esperar antes de começar. O agendador atual sempre executa a tarefa de maior prioridade que está esperando, e as tarefas em lote perdem sua promessa toda tarde.

Sua vez

Escreva order(jobs, max_wait). jobs é uma lista de {"id", "arrive", "priority"} ordenados por arrive (minutos inteiros); max_wait mapeia prioridade para o máximo de minutos que um trabalho pode esperar. Retorne os ids dos trabalhos na ordem que o worker os executa. O worker executa um trabalho por minuto: um trabalho começa no momento mais tardio entre sua chegada e o fim do trabalho anterior, e sua espera é o início menos a chegada. Rule: nenhum trabalho pode esperar mais que max_wait[priority]. Os dias de teste podem todos ser atendidos sem nenhum trabalho atrasado; com {1: 3, 2: 20, 3: 60} um dia tem cerca de 1,000 trabalhos.

Viu um problema nesta lição? Reporte-o · Pergunte sobre esta lição

Este exercício abre em breve

Termine a lição anterior para que esta seja desbloqueada. O curso inteiro é gratuito, não precisa de conta, e você pode ler esta lição agora mesmo.