1700495652
算法之美：指导工作与生活的算法 优先级反转和优先约束
1700495653
1700495654
1997年夏，人类迎来一件值得庆祝的大事。人类火星探测车第一次降落在火星表面。价值1.5亿美元的火星探路者飞船加速到每小时16000英里的速度，穿越3.08亿英里的太空空间，并用太空安全气囊降落在红色岩石状的火星表面。
1700495655
1700495656
现在它却被暂停了。
1700495657
1700495658
在地球这边，喷气推进实验室的工程师们既担心又为难。探路者号最优先的任务（给“数据总线”输入输出信息）被神秘地忽视，而机器人却在没那么重要的任务上消磨时间。到底发生了什么？难道机器人不应该知道得更多吗？
1700495659
1700495660
突然，探路者号发现信息总线在一段不可接受的长时间里都没有被处理，并且没有一个细微的追索来源，它便进行了一次完全重启，使当天剩下的工作能被更好地完成。大约一天后，同样的事情再次发生。
1700495661
1700495662
喷气推进实验室团队经过仔细研究，终于成功重现并诊断该行为。其罪魁祸首是一种经典的危险调度行为，称为优先级反转。该行为是指低优先级任务做某些工作时拥有系统资源（这里我们可以说是访问数据库），但在做该任务时被定时器中断，该定时器使其暂停并触发系统调度器。调度器启动一个高优先级任务，但该任务不能运行，因为数据库已被占用。因此，调度器向下移动优先级列表，改为执行中等优先级工作，而不是高优先级任务（已被阻塞），或低优先级任务（已被锁定在中优先级任务之后）。在这种可怕的状况下，系统的最高优先级有时可以在任意长时间里被忽略。[1]
1700495663
1700495664
当喷气推进实验室团队的工程师将探路者号的这一问题识别为优先级反转的情况后，他们立即编写了一个修正代码，并将新代码数传送到百万英里之外的探路者号上。他们穿越太阳系发射的解决方案是什么呢？那就是优先级继承。如果发现低优先级任务阻塞高优先级资源，那么所有低优先级任务应该立刻变成系统上的最高优先级任务，“继承”被阻塞的优先级。
1700495665
1700495666
喜剧演员米奇·赫德伯格讲述了一件事：“当时我在赌场，我正在做自己的事情，有个人走过来说：‘你要挪一下位置，你挡住消防出口了。’我说，如果这里有火灾，我还不会跑吗！”这件事中，保镖的论点是优先反转，赫德伯格的反驳是优先继承。赫德伯格随便在一个暴徒的面前闲逛，将自己的低优先级（游玩任务）置于他的高优先级（逃生任务）之前。但如果他继承了优先级便不会这样。凶残的暴徒总有一种方式使其他人非常快地继承他们的优先权。正如赫德伯格所说：“只要你是可燃体，且双腿健全，你就永远不会堵住消防出口。”
1700495667
1700495668
这其中值得一提是，想把事情做好的热情不足以避免调度上的陷阱，光有想把重要事情做好的热情也不够。要承诺坚持做你所能做的最重要的事情，如果你一直目光短浅而不远望前方，那么你眼中的整个世界都仿佛处于拖延之中。正如汽车轮胎的旋转一样，只有当你的轮子被卡住时你才会渴望它立即开始运转。歌德曾说：“最重要的事情永远不应该受到不重要事情的影响。”虽然这有一定的道理，但它也不都是真的。有时候，最重要的事要等不重要的事情完成之后才能进行，所以这里只有将这些不重要的事情看得跟被阻塞的重要任务一样重要。
1700495669
1700495670
当某个任务在另一个任务完成之前无法启动时，调度理论家称之为“优先约束”。操作研究专家劳拉·艾伯特·麦克莱表示，她清楚地记得这一原则在她自己家里不止一次地产生了作用。“如果你能看到这些东西，这可能是有用的。当然，安排好三个孩子的一天，有很多需要统筹的事务……孩子们必须先吃完早餐，我们才能出门，如果我不记得递给他们勺子，那他们就不能吃早餐。有时，你忘记做一件小事会导致整个任务的延迟。在调度算法方面，仅仅知道这是什么并使其保持运转就已经大有裨益了。这就是我每天如何安排事情的。”
1700495671
1700495672
在1978年，调度理论研究者简·卡雷尔·伦斯特拉使用了相同的原理帮助他的朋友吉恩搬到伯克利的新家。“吉恩正在拖延一些事，这些事是必须在我们开始其他紧急事情之前就完成的。”伦斯特拉回忆说，他们需要退还一辆面包车，但又需要用这辆车运送一台设备，而又需要用这台设备来修理公寓里的东西。这个修理的任务没那么紧急（因此它被推迟），但换车是很紧急的。伦斯特拉说：“我向他解释道，应该考虑到前任务更加紧急。”伦斯特拉是调度理论的中心人物，因此他有能力给他的朋友提供这个建议，这也带来了特别有趣的讽刺意味。这是一个由优先约束引起的优先级反转的标准案例。可以说，20世纪最优秀的优先约束专家就是他的朋友尤金“吉恩”劳勒。
1700495673
1700495674
[1]具有讽刺意味的是，探路者号的软件团队负责人格伦·里夫斯将该问题归结于“截止日期压力”的错误，并认为在开发过程中修复这个问题被认为是“较低优先级”。因此，其根本原因在某种程度上来说，就是镜像问题本身。
1700495675
1700495676
1700495677
1700495678
1700495680
算法之美：指导工作与生活的算法 减速带
1700495681
1700495682
劳勒考虑到他一生大部分时间都在思考如何最有效地完成一系列的任务，他便对自己的职业生涯采取了一种有趣的迂回路线。他在佛罗里达州立大学学习数学，后于1954年在哈佛大学攻读研究生，但在获得博士学位前便离开。后又在法学院、军队和机械加工车间工作，1958年他回到哈佛大学，得到博士学位后他开始在密歇根大学工作。1969年，在休假期间他去了伯克利，在一场声名狼藉的反越南战争的抗议中被逮捕。次年，他成为加州大学伯克利分校的一名教师，并获得了计算机科学系的“社会良知”的美誉。他于1994年去世，此后计算机协会设立了劳勒奖，表彰那些体现出计算机科学人道主义潜力的人。
1700495683
1700495684
劳勒的优先约束理论的第一次调查表明，它们应用起来十分容易。例如，采取最早到期日算法将一组任务的最大延迟量进行最小化。如果你的任务有优先约束，那只会使事情更加棘手——如果有些任务必须在其他任务之后完成，那你就不能简单地按照到期日的先后顺序来安排任务。但在1968年，劳勒证明了只要你按照从后往前的顺序建立时间表就没有问题：只看跟其他没有依赖关系的任务，并把到期日最后的任务排在日程表的最后。然后重复这一过程，每一步都只考虑那些不作为其他（还未做安排的）任务完成前提的任务。
1700495685
1700495686
但当劳勒更深入地考虑优先约束时，他发现了一些奇怪的问题。我们所看到的是，如果你想尽可能快地从你的待办事项列表中理清尽可能多的项目，最短处理时间算法就是最佳策略。但是，如果某些任务有优先约束，便没有一个简单或明显的调整原则。虽然这看起来像一个基本调度问题，但无论是劳勒还是其他任何研究人员似乎都没能找到一个有效的解决方法。
1700495687
1700495688
然而，事实比这还糟。在那之后不久，劳勒自己也很快发现这一问题属于大多数计算机科学家认为没有行之有效的解决办法的范畴——在该领域被称为“难解性”[1]。影响调度理论发展的这第一个减速带就是一个难以逾越的障碍。
1700495689
1700495690
正如我们看到的，在“三倍或无”（要么赢三倍，要么全部输光）的情况下，最优停止理论并没有圣人的指导，每一个问题也并不都能用一个正式答案表达。在调度问题上，其定义就很清楚地表明，每一组任务和约束都有一些最好的调度安排，所以本质上调度问题并不是不可回答的，但它可能没有简单直接的算法帮你在一个合理的时间量里的找到最优安排。
1700495691
1700495692
这使劳勒和伦斯特拉这样的研究者面临一个不可抗拒的问题：究竟什么比例的调度问题是难解的？在塞尔默·约翰逊初创调度理论的20年后，对个人解决方案的探索已变成一项更浩大、更雄心勃勃的研究：通过这一探索可以纵观整个调度理论。
1700495693
1700495694
研究人员发现，即使是对调度问题进行最微妙的改变，也经常会跨越易处理和不易处理之间细致而又不规则的分界线。例如，当所有任务都具有相同权值时，穆尔算法就最大限度地减少了过期任务（或腐烂水果）的数量。但如果一些任务比其他更重要，这个问题就变得难解，没有算法可以很轻松地提供最佳安排。同样，如果某些任务必须等到某个时间点才能开始，那几乎所有的安排都会陷入难解的境地。在收垃圾车到来的前一天晚上才能把垃圾倒出去，这可能是一个合理的市政规章，但它会让你的日程安排变得棘手。
1700495695
1700495696
对调度理论边界的绘制一直持续到今天。最近的一项调查表明，在所有问题中大约有7%是仍然未知的，就是调度的未知领域。然而，在我们所理解的93%的问题中，现实也并不是很理想：只有9%的问题可以被有效解决，其他的84%已经被证明是难解的。[2]换句话说，大多数的调度问题都没有现成的解决方案。如果你觉得很难完美地管理你的日程，那也许因为实际上这就是难以管理的。尽管如此，我们讨论过的算法往往是解决那些困难问题的起点——也许不是那么完美的，但至少是可以预期的。
1700495697
1700495698
[1]我们将在第8章详细研究“难解性”这一问题。
1700495699
1700495700
[2]事实也并非数据显示的那么糟糕，因为这包括多机调度问题，更像是管理一组员工而不是管理你的日历。
[
上一页 ]
[ :1.700495651e+09 ]
[
下一页 ]