Emprunter le triage : ordonner une file de tâches
Pourquoi c'est important « Utilise une file de priorité » est le réflexe pour toute file avec des priorités. Elle répond à « qui compte le plus ? » alors que la vraie question est souvent « qui peut le moins attendre ? ». D'autres domaines répondent à cette question depuis longtemps.
Trois guichets
Les urgences d'un hôpital. Une infirmière de triage place chaque arrivée dans une catégorie, et chaque catégorie a un délai cible de prise en charge : dans le système de Manchester, très utilisé, immédiatement, sous 10 minutes, 60, 120 ou 240. Quand un médecin se libère, le patient suivant n'est pas simplement le plus malade de la salle : un patient standard sur le point de dépasser son délai peut passer avant un patient urgent arrivé il y a une minute qui a encore le temps.
L'enregistrement à l'aéroport. Il y a des files séparées pour la classe premium et la classe économique. Dans une file, les gens sont servis dans l'ordre d'arrivée. Mais quand un vol est sur le point de fermer, le personnel parcourt la file économique en appelant ce vol en priorité, devant des passagers premium dont les vols partent plus tard.
Le guichet des retours d'une bibliothèque. Une seule file, servie strictement dans l'ordre. Personne n'est jamais doublé, et l'urgence de personne n'est prise en compte.
Compare avant de coder
- À chaque guichet, qu'est-ce qui décide qui est servi ensuite ?
- Quels guichets peuvent faire attendre quelqu'un indéfiniment ? Lesquels peuvent faire attendre trop longtemps un cas urgent ?
- L'hôpital et l'aéroport ne se ressemblent pas du tout. Qu'ont-ils en commun ? Écris-le en une phrase qui ne mentionne ni hôpitaux ni avions.
- À l'aéroport, pourquoi suffit-il de regarder l'avant de chaque file ?
La cible
Un système de tâches en arrière-plan tourne sur un seul exécuteur qui prend exactement une minute par tâche. Les tâches sont interactives (priorité 1), standard (2) ou par lots (3), et chaque priorité a une promesse de service : le plus long qu'une tâche de cette priorité peut attendre avant de démarrer. L'ordonnanceur actuel exécute toujours la tâche en attente de plus haute priorité, et les tâches par lots ratent leur promesse chaque après-midi.
Écris order(jobs, max_wait). jobs est une liste de {"id", "arrive", "priority"} triée par arrive (minutes entières) ; max_wait associe à chaque priorité le maximum de minutes qu'une tâche peut attendre. Renvoie les ids des tâches dans l'ordre où l'exécuteur les exécute. L'exécuteur exécute une tâche par minute : une tâche démarre au plus tard entre son arrivée et la fin de la tâche précédente, et son attente est le démarrage moins l'arrivée. Règle : aucune tâche ne peut attendre plus de max_wait[priority]. Les journées de test peuvent toutes être servies sans aucune tâche en retard ; avec {1: 3, 2: 20, 3: 60}, une journée a environ 1 000 tâches.
Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon
Cet exercice s'ouvre bientôt
Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.
Ce navigateur bloque les cookies pour learn.floati.life, donc les leçons que tu as terminées ici ne peuvent pas s'ouvrir dans l'ordre. Autorise les cookies pour ce site et recharge la page.