Temario Lección 48 de 148 · Máquinas prestadas
Máquinas prestadas

Toma prestado el triaje: ordenar una cola de tareas

Por qué importa "Usa una cola de prioridad" es el reflejo para cualquier cola con prioridades. Responde "¿quién importa más?" cuando la pregunta real suele ser "¿quién puede esperar menos?". Otros campos llevan mucho tiempo respondiendo a esa pregunta.

Tres mostradores

Urgencias de un hospital. Una enfermera de triaje pone a cada persona que llega en una categoría, y cada categoría tiene un tiempo objetivo para ser atendida: en el muy usado sistema Manchester, de inmediato, en 10 minutos, 60, 120 o 240. Cuando un médico queda libre, el siguiente paciente no es simplemente el más grave de la sala: un paciente estándar a punto de pasar su tiempo objetivo puede ir antes que uno urgente que llegó hace un minuto y todavía tiene margen.

La facturación de un aeropuerto. Hay filas separadas para preferente y turista. Dentro de una fila, se atiende por orden de llegada. Pero cuando un vuelo está a punto de cerrar, el personal recorre la fila de turista llamando a ese vuelo para que pase delante, antes que los pasajeros preferentes cuyos vuelos salen más tarde.

El mostrador de devoluciones de una biblioteca. Una sola fila, atendida estrictamente en orden. Nadie adelanta nunca a nadie, y no se tiene en cuenta la urgencia de nadie.

Compara antes de programar

  1. En cada mostrador, ¿qué decide a quién se atiende después?
  2. ¿Qué mostradores pueden hacer que alguien espere para siempre? ¿Cuáles pueden hacer que un caso urgente espere demasiado?
  3. El hospital y el aeropuerto no se parecen en nada. ¿Qué comparten? Escríbelo en una frase que no mencione hospitales ni aviones.
  4. En el aeropuerto, ¿por qué basta con mirar el principio de cada fila?

El objetivo

Un sistema de tareas en segundo plano funciona con un solo trabajador que tarda exactamente un minuto por tarea. Las tareas son interactivas (prioridad 1), estándar (2) o por lotes (3), y cada prioridad tiene una promesa de servicio: lo máximo que puede esperar una tarea de esa prioridad antes de empezar. El planificador actual siempre ejecuta la tarea en espera de mayor prioridad, y las tareas por lotes incumplen su promesa todas las tardes.

Tu turno

Escribe order(jobs, max_wait). jobs es una lista de {"id", "arrive", "priority"} ordenada por arrive (minutos enteros); max_wait relaciona cada prioridad con los minutos máximos que puede esperar una tarea. Devuelve los ids de las tareas en el orden en que las ejecuta el trabajador. El trabajador ejecuta una tarea por minuto: una tarea empieza en el momento más tardío entre su llegada y el final de la tarea anterior, y su espera es el inicio menos la llegada. Regla: ninguna tarea puede esperar más de max_wait[priority]. Todos los días de prueba se pueden atender sin ninguna tarea tarde; con {1: 3, 2: 20, 3: 60} un día tiene unas 1,000 tareas.

¿Has visto un problema en esta lección? Avísanos · Preguntar sobre esta lección

Este ejercicio se abre pronto

Termina la lección anterior y esta se desbloquea. Todo el curso es gratis, no hace falta cuenta, y puedes leer esta lección ahora mismo.