借来分诊:给任务队列排序
为什么重要 “用一个优先队列”是面对任何带优先级的队列时的条件反射。它回答的是“谁最重要?”,而真正的问题常常是“谁最等不起?”。其他领域回答这个问题已经很久了。
三个柜台
一家医院的急诊科。一位分诊护士把每一位来者归入一个类别,每个类别都有一个就诊的目标时间:在广泛使用的曼彻斯特系统中,分别是立即、10 分钟内、60、120 或 240 分钟内。当一位医生空闲时,下一位病人并不只是房间里病得最重的那一位:一位即将超过目标时间的普通病人,可以排在一位一分钟前才到、而且仍然有时间的紧急病人前面。
机场值机。头等舱和经济舱有各自的通道。在同一条通道内,按到达顺序服务。但当一个航班即将截止办理时,工作人员会沿着经济舱的队伍呼叫这个航班的乘客上前,排到那些航班起飞时间更晚的头等舱乘客前面。
一个图书馆的还书台。只有一条队伍,严格按顺序服务。永远不会有人被插队,也永远不会考虑任何人的紧急程度。
先比较,再写代码
- 在每个柜台,是什么决定了下一个被服务的人?
- 哪些柜台会让某个人永远等下去?哪些会让一个紧急情况等得太久?
- 医院和机场看起来毫无相似之处。它们有什么共同之处?把它写成一句既不提医院也不提飞机的话。
- 在机场,为什么只看每条通道的最前面就够了?
目标
一个后台任务系统运行在一个工作进程上,每个任务恰好花一分钟。任务分为交互式(优先级 1)、标准(2)或批处理(3),每个优先级都有一个服务承诺:这个优先级的任务在开始之前最多可以等多久。当前的调度器总是运行优先级最高的等待任务,而批处理任务每天下午都会违背它们的承诺。
编写 order(jobs, max_wait)。jobs 是一个按 arrive(整数分钟)排序的 {"id", "arrive", "priority"} 列表;max_wait 把优先级映射到一个任务最多可以等待的分钟数。按工作进程运行它们的顺序返回任务 ID。工作进程每分钟运行一个任务:一个任务在它到达的时间和上一个任务结束的时间中较晚的那个开始,它的等待时间是开始时间减去到达时间。规则:任何任务的等待都不能超过 max_wait[priority]。测试中的每一天都可以在没有任何任务迟到的情况下完成服务;在 {1: 3, 2: 20, 3: 60} 的情况下,一天大约有 1,000 个任务。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。