BUAA-OO Unit.2 Hw8 作业总结和分享

关于这篇文章

这篇文章只适用于北航2025OO课程，每年的指导书内容可能会有变动，具体内容请以当时课程为准。
这篇文章主要是记录我在OO-Unit2期间的一些记录、思考，仅作为参考，希望对读者有所帮助。
这篇文章仅可作为参考，笔者可能会有笔误或认识不充分的问题，希望读者包涵。
如果这篇文章设计学术诚信以及不可知问题，请与我取得联系，我将及时修改。

前言

课程第二单元的核心为多线程编程，学习目标为掌握线程间的交互逻辑与协同设计层次架构和理解调度器的作用与实现的方法。

本单元以某公司大楼的目的选层电梯系统为背景。普通的目的选层电梯系统有所区分的是，该公司为提高运行效率，充分考虑不同职位的员工所从事工作的时间急迫性，为不同类型的乘客请求赋予了优先级指数。优先级指数描述了乘客到达目的楼层的急迫程度。

同步块与锁

同步块设置和锁的选择

我的作业中主要有三种情况需要同步块设置

第一种是线程需要 wait() ，此时需要在同步块里进行。
第二种是线程需要保证线程安全，因此我们在操作可以写入的可变对象的元素时我们需要加锁，防止读-写冲突或是写-写冲突。
第三种时我们需要设置多线程之间的同步/互斥关系。

我在三次作业中选择的锁的类型都是 synchronized 关键词进行加锁。

作业中 synchronized 锁有两种使用方式，第一种是对方法加锁，第二种是对对象加锁。

建议使用对对象加锁的方式，这种方法可拓展性较强，性能也比较好。

处理语句的关系

有点不明白题目的含义。根据我对同步块设置的分类，关系如下：

第一种情况 wait() 后会释放所有拿到的锁，Monitor 的对象应该和 wait() 方法的对象相同。
第二种情况锁的对象应该和处理语句的对象相同。
第三种情况锁的对象应该可以和处理语句的对象不同，但是多线程之间应该获得相同的锁。

调度器设置

调度器与线程交互

输入线程和调度器线程，以及调度器线程和电梯线程之间都是生产者-消费者模型，其中：

输入线程是生产者，请求表是托盘，调度器线程是消费者。
调度器线程是生产者，每个电梯的等待队列是托盘，电梯线程是消费者。

调度器与输入线程和电梯线程共享的托盘对象，并且内部包含调度策略逻辑，整体上起到转运的功能。每次收到输入线程提供的请求后会启动自身的调度策略，根据策略得出分配的电梯编号并将乘客请求转移到对应电梯的等待队列内。

调度策略

第一次作业乘客的请求中包括对电梯的选择，因此我们只需要根据乘客请求进行分派调度即可。

第二、三次作业我选择的是影子系统，配合调参的调度策略。

首先根据影子电梯模拟出分别向六个电梯新增当前乘客请求后增加的平均等待时间和耗电量，然后通过一个代价函数计算出代价花费，最后选择代价最低的一架电梯分派乘客请求。

架构设计

UML类图

迭代架构变化

第一次作业

第一次作业是一个从无到有的过程：

完成输入线程和调度器线程，以及调度器线程和电梯线程之间的生产者-消费者模型，数据流通路
抽象电梯运行时获得策略的接口 Advisable ，并且实现 LOOK 算法提供策略
实现电梯运行逻辑，包括部分量子电梯
新建 Floor 、 Command 、MovingDirection 类，方便后续楼层方面的迭代

第二次作业

第二次作业要求变化：

新增 RECEIVE 约束
新增 SCHE 行为
乘客请求不指定电梯

我的架构变化：

更改电梯运行逻辑，特别是量子电梯部分
注册 SCHE 操作，新增电梯相关运行逻辑
新增影子系统，电梯内新增影子系统相关状态变量，并且电梯内新增计算和存储乘客等待时间、电梯耗电量的逻辑进行评估。
调度器修改调度逻辑，新增调度策略接口，并且接入影子系统，根据影子系统-代价函数选择电梯进行调度
电梯候乘表新增 buffer ，用于在静默状态下接受乘客请求
自建乘客候乘表的数据类型，以乘客优先级为第一关键词，距离终点距离为第二关键词创建 TreeSet 并使用
修改电梯线程和调度器线程结束的条件，新增对特殊调度行为的计数

第三次作业

第三次作业要求变化：

新增 UPDATE 行为
增加双轿厢协同

我的架构变化：

注册 UPDATE 操作，新增电梯相关运行逻辑
新增 Monitor 类，双轿厢电梯线程共享对象，用于协同 UPDATE 操作和双轿厢电梯运行不撞车
修改电梯运行逻辑，新增运行范围
新增一种调度方式，从双轿厢电梯的一个轿厢调度至另外一个轿厢

UML协作图

变与不变

稳定的内容：电梯的运行策略，电梯的换乘策略，两个生产者-消费者架构

易变的内容：新增的电梯行为，调度策略

如果你每次都迭代出新的内容，想扣各种细节，那所有策略类的都是易变的。我这里的稳定和易变特别指的是“我”的实现。

对我来说，两个生产者-消费者架构是不会改变的，这种架构很好地解决了数据流的问题，并且比较贴合现实。迭代过程中，我的电梯运行策略是稳定不变的，即收到的指令和电梯的运行的映射是稳定不变的；同时，不想扣太多换乘与优先级之间的问题，因此我也沿用了第一次的换乘策略。

由于每次迭代电梯都新增了新的行动，电梯的运行策略会增加，但是原来的运行策略不会收到大的影响，可能其中会增加对其他逻辑的判断。同时新的行动强制限制了电梯的移动，因此我们的调度策略也会相应进行改变。

实现双轿厢协同

首先，我把双轿厢电梯看成两个线程，一个轿厢一个，沿用之前的线程，不会关闭和开启新的线程。

正好OS也学到了线程相关内容，双轿厢同步开始改造和运行轿厢不碰撞的内容其实就是实现多线程的同步和互斥，于是我参考了学长和OS理论信号量的内容。

双轿厢同步开始改造

参考多进程同步原语：屏障Barriers实现逻辑。我们先实现了两个轿厢共享 Monitor 类对象，尝试在这个对象内实现屏障。

我们并不需要两个单轿厢同时开始 UPDATE 的预处理操作，我们只需要在预处理和开始改造之间设置屏障，两个线程同时到达屏障后输出改造信息开始改造时间的等待即可实现双轿厢同步开始改造。

运行轿厢不碰撞

我们复用 UPDATE 使用过的 Monitor 对象实现互斥。

当某个轿厢即将进入到换乘层时，这个轿厢会尝试获取换乘层的锁，如果锁被另一个轿厢占用，则轿厢会等待直到换乘层的锁释放，然后取得换乘层的锁。当某个轿厢即将离开换乘层时，会释放自己取得的换乘层的锁。

为了规避线程安全的问题，我尝试让改造后的电梯等待或结束前会判断自己所处的层数，如果自己处于换乘层则会往其他空闲层移动，释放换乘层的锁。

Bug相关

自己的Bug

笔者在Hw6和Hw7强测都出现了Bug，经分析，这两个Bug都和量子电梯相关代码有关。

Hw6中，作业新增 RECRIVE 限制，使得电梯不能在无乘客请求的时候开始移动，当时我~~因为偷懒~~，选择在电梯调度后判断电梯的情况，若电梯调度前是不可移动的情况，则会重置电梯等待的时间。手动重置量子态。

~~以上逻辑是先写的~~，在迭代 SCHE 指令的时候忘记新的内容和以上逻辑出现的Bug，可能会在 SCHE 移动时加入乘客请求后不断重置 Move 时间，导致最终 SCHE 操作超时。
Hw7中，作业新增 UPDATE 操作，关于双轿厢电梯的换乘协作，我选择让一个轿厢给另外一个轿厢发送乘客请求。这里我新增了一种电梯调度方式，但是在新的调度方式中我忘记了重置电梯等待的时间，导致电梯移动速度过快。

在本地调试的过程中，我也出现过Bug。其中有一个比较神秘的线程安全Bug，出现在 DispatcherThread 和 ElevatorThread 的协作中。 DispatcherThread 结束时给 ElevatorThread 发送结束信号，并唤醒进程；此时有可能出现notifyAll() 在ElevatorThread 的 wait() 之前，导致最终程序无法正常结束， ElevatorThread 一睡不醒。

Debug方法

首先我们需要先清楚Bug表现出的错误是什么，是输出格式错误，还是 ctle 、 rtle 。

然后判断Bug的性质，Bug是由单线程逻辑问题还是线程安全问题引起的。

tle 相关的问题，我们可以使用 IntelliJ Profiler 跑标准输入，复现Bug，查CPU时间和线程方法的运行时间。

仅单线程的逻辑问题我们可以采用代码走查的方式Debug，也可以通过修改调度方式将多线程多电梯运行改成单电梯运行，然后使用打印调试的方法判断某些对象的值是否符合我们的预期，不断缩小Bug出现范围。

多线程的问题我们可以考虑使用调试模式观察程序非正常结束时各个线程内对象的值，也可以使用运行-转储线程观察某一时刻的线程运行情况发现死锁的问题。当然，我们也可以使用代码走查，绘制时序图，进行理论分析来Debug。

心得体会

It’s no use crying over spilt milk.

Unit2结束了，终于熬过了最难的一次迭代作业了。电梯月的分数其实并不是很理想，但再接再厉吧。

从课上和课下交流中学到了很多多线程相关的知识，十分感谢同行的同学和助教们。

线程安全

线程安全（thread-safe）是关于对象是否能被多个线程安全访问的特性。如果一个对象是线程安全的，则无论多个线程以什么样的交叠次序来访问都不会影响该对象的行为结果

我遇到的线程安全的相关问题通常有特点：复现概率不高、出现原因不明、（根据你的实现）个性化定制的特点，因此本次Debug和找Bug的过程都十分令人头疼。一是不清楚Bug出现的具体原因，只能通过推测和调试打印的方法不断缩小出现Bug的原因，并且也不好确定自己修改后的代码是否正确并完全解决问题；二是线程安全的Bug很大程度是因为自己实现的问题，很可能会出现自己认知以外的Bug，初见杀问题十分严重。

大部分线程安全问题出现在以下两个方面：

锁的使用。本次作业中我全部使用 synchronized 关键词进行加锁。为了防止数据冲突，我们需要在读、写的过程中拿到操作对象的锁。一个语句块若获取了至少两把锁，则我们需要考虑死锁的可能。更进一步，我们还要考虑锁的粒度。
wait() 和 notify() / notifyAll() 。为了防止轮询某个未准备好数据，占用CPU，我们可以先让这个线程等待(wait)，等到数据准备好后再唤醒进程(notify)。使用时我们要注意的是线程等待的对象和唤醒的对象，既要防止误唤醒，又要确定自己的 notify() 语句在时间上能执行在对应的 wait() 语句之后，还要保证不会出现所有线程都在等待队列的情况。

层次化设计

本次作业中，我采用了生产者-消费者模型。这种模型划分了两个层次，提供数据的生产者、存储数据的托盘和获得数据的消费者，职责清晰。

良好的层次化设计可以使得每次迭代作业的迭代思路变得更加清晰，提高代码的可维护性和可拓展性。

总结

这个单元内容繁多且复杂，并且似乎没有绝对正确的算法来模拟最完美的电梯。我们能做的，也就是在程序复杂度、性能与正确性之间做到权衡。

因此，我想把总结做成一个大的部分，单独放在最后。

在往下看之前，我觉得你可以看看钟鼓楼老师的博客面向对象-电梯 | 钟鼓楼，私心觉得讲的很好，非常喜欢。我们接下来的策略总结也基于上述博客其中对概念的释义。

性能指标

程序的性能指标有三个维度：系统运行时间，平均完成时间和系统耗电量。具体的定义和分数计算方式可以查看指导书。

我想说明的是，性能分数由 $、和$ 计算而出，为了多获得一点性能分，我们肯定想自己的指标尽量低，但是在优化的过程中，我们应该可以感受到，很多时候指标之间不能同时优化。

此外，我们可以仔细考虑一下系统耗电量这个指标。考虑一种极端策略，如果当所有的乘客请求都输入后，我们再启动电梯，完成乘客请求，一般来说，这种策略的系统耗电量与正常策略乘客请求输入后马上处理相比少很多，我们这种策略也可以极端地优化系统耗电量，而放弃自己的系统运行时间和平均完成时间。假如这种极端策略在强测中没有 TLE ，那么这种策略就可以拉低其他人的系统耗电量性能分，这是很恐怖的事情。

我想表达的是，我们追求的性能，追求的都是帕累托最优，但是不同的帕累托最优点之间也存在性能分差异。至于哪个点，哪些电梯的逻辑组合能让性能分达到最佳，我不清楚。这不仅与自己程序有关，也和强测中的其他人程序的性能有关。

单部电梯的运行策略

判断电梯如何应该运行的策略。电梯如何运行肯定不只是和电梯本身的状态有关，电梯是需要完成乘客乘坐需求的，因此电梯如何运行，也与具体乘客请求有关。我在讨论电梯运行策略时，默认假设电梯已经收到调度器分配的乘客请求。但是我认为，实际上部分电梯调度策略和电梯运行策略是相互耦合的（如影子电梯）。因此，以下讨论的只是电梯运行策略的部分，并且部分内容基于以调度器为基础的电梯调度策略。

我选的是比较保险的Look策略，我的舍友有选择als+Look的策略。

在我们的程序中，电梯有乘载容量限制，我们可能需要对乘客请求进行权衡和选择。而性能分（主要是平均等待时间和耗电量）的存在和追求，使得我们的策略又依赖于我们电梯完成请求的时间和乘客的优先级。在翻看学长博客的时候，我并没有看到很多关于优先级有关的策略，因此这个部分只是我个人的思考（orz)。

电梯运行策略逻辑的主要在Hw5定下了，Hw6、7中可能会有些许细节的修改，不会涉及到核心层面的改动。

Look 策略

在只考虑电梯正常运行时，与电梯运行相关的行为有两种：移动和暂停。

对于 Look 策略，我们需要额外考虑电梯的一个属性和一个行为：移动方向和调转方向。

Look 策略是 Scan 策略的升级版。

Scan 策略有几个特点：

以电梯目前的运行方向为判断电梯的接下来的行为
运行沿路遇到可以捎带的同方向的请求，我们可以开门捎带请求。若有乘客到达目的地，我们需要开门让乘客出门。捎带和完成请求后，电梯关门，向着运行方向继续运行。
我们只在运行的端点楼层进行转向。

Scan 策略如其名，就是电梯在底楼和顶楼之间来回扫，扫的过程中完成乘客请求。

与 Scan 策略不同的是， Look 策略动态检测方向终点，当当前方向没有更多请求并且请求已经完成时，电梯会立即调头，无需走到端点楼层。

因此 Look 策略比 Scan 策略更高效，但是程序逻辑更复杂。但是 Look 策略也复杂不到哪里去，我们只需要关注电梯的几个行为和属性之间的关系即可。

Look 策略也更加贴近现实电梯运行的逻辑，因此我选择了这个策略。

ALS 策略

笔者认为 ALS 和 Look 最大的区别是运行判断的重心不同。 Look 策略电梯运行时的判断重心为电梯的运行方向，而 ALS 的判断重心为主请求。

我们可以参考24年指导书对于 ALS 策略的说明：

对于每一个电梯，都采用 ALS 策略，即新增主请求和被捎带请求两个概念

主请求选择规则：

如果电梯中没有乘客，将请求队列中到达时间最早的请求作为主请求

如果电梯中有乘客，将其中到达时间最早的乘客请求作为主请求

被捎带请求选择规则：

电梯的主请求存在

该请求投喂的时刻小于等于电梯到达该请求出发楼层关门的截止时间

电梯的运行方向和该请求的目标方向一致

我不太明白这个策略的具体实现方式，也没有实现过这个策略，因此我也就不多解释啦。

ALS + Look 策略

具体可以看我好室友的博客中的描述 2025第二单元总结博客 [BUAA-OO] | theUHO 之1.3.3.2.1

个人觉得，和我的架构比较大的区别是：

若电梯已经有主请求，在尝试接顺路乘客的路上可以不输出 RECEIVE 信息
在第一条的基础上，除主请求外的乘客乘坐的电梯只有在电梯接到乘客时才确定乘客乘坐的电梯编号。

优先级、乘客请求数量与承载容量限制对策略的影响

上面的策略都是关于电梯运行/暂停的策略，我们处理多个乘客请求还受到其他条件限制。

我的小猪脑太笨了😄，想不出更优的成体系的电梯运行策略，只能基于以上策略，在特殊情况下尝试改进策略，提高性能。我们先脱离电梯调度策略（之后可能会讲到可行性）谈一座电梯的特殊情况（以下分析基于 Look 策略和指导书限制，也基于我愚蠢的程序逻辑——在调度器调度乘客请求后直接RECEIVE，请求不会再分配给其他电梯）

我们的电梯有乘载容量限制（假设为指导书中的6人），当某一层可捎带请求数>>6时，会引起多个乘客请求的冲突
- 假设我们的电梯在F1，此时同时涌入7个请求，我们先不考虑优先级的事情，或者假设请求的优先级都相同。
  
  按照接受请求的时间顺序，7个请求分别为：F1->F7、F3、F5、F4、F5、F6、F2
  
  我们肯定不能让七个人都进电梯，我们得进行抉择，到底是谁可以进电梯呢。我想：
  1. 修改调度策略，解决这种情况的前提（比如限制电梯只能接6个请求，这样电梯最多也只能接6人哩）：我觉得不太行
  2. 先到先进：Ok吧，中规中矩
  3. 设置请求的优先级，提前预估完成时间，让完成时间早的请求先进：因为我们的电梯只能捎带6人，先完成的请求可以腾出电梯的空间，让后面（时间上）可以完成高层请求的概率变大。
  可能我需要再解释一下第三点，假设我们的电梯还有8号请求 F2->F3 ，只有你带了 F1->F2 的请求，你在 F2 完成请求，你就可以顺路带上8号请求并在 F3 完成。
  
  这个情况比较顺从直觉，因此我选了这个策略。
  
  好的，我们再加上优先级和性能分的限制，假如 F1->F2、F2->F3 的优先级都是1，而其他请求的优先级都是99。在我们脑内模拟的最优情况是不是发生了改变？虽然电梯在 F1 带 F1->F2 可以节省在 F2 层开关门的耗电量（即开关次数），但是对于性能分而言，这么一点耗电量差值是否值得我们多花带权等待时间？
  
  好的，如果优先级的对比并不是这么明显，我们应该如何挑选被捎带的幸运儿？
  
  我不知道如何达到最优，也许调参+模拟（带权等待时间和耗电量）可以达到平均的最优，但我没试过，也不敢尝试。
  
  这个问题就写到这吧，再细化的情况我都不敢想。
- 乘客优先级的导入会对 Look 策略产生影响吗？我想，如果追求性能分的话，以上的答案是肯定的。我们可能需要考虑乘客的替换（？）。
  
  首先，对于带权等待时间这一参数来说，如果有两个相同起点和终点的不同优先级的人，肯定是先接优先级高的人会让带权等待时间变少。
  
  我们先考虑一种比较简单的情况：
  
  我们的电梯内目前有6个请求：F1->F3、F4、4*F7 按照顺序优先级分别为 10、20、30、40、50、60
  
  我们的电梯运行到 F3 层，然后来了2个请求，分别为 F3->F4,PRI:99 和 F3->F7,PRI:99 。
  
  这时候一共8个请求，我们已经完成了1个，现在有7个请求冲突，我们应该如何选择？
  
  可能觉得这种情况退化成了第一点，但是与第一点不同的是，新来的请求和原来的请求已经等待的时间是不同的，如果忽略这种情况的差异，两点似乎是一样的。
  
  嗯嗯，我们改一下情况：
  
  我们的电梯内目前有6个请求：F1->6*F7 按照顺序优先级分别为 1、1、1、1、1、1
  
  我们的电梯运行到 F3 层，然后来了1个请求，分别为 F3->F4,PRI:99 。
  
  此时我们需要抉择，我要开门，放下一个人，接上新的人，关门走吗？
  
  对于平均等待时间来说，似乎是应该是这样的，但这样十分反直觉。当我们路过一个楼层，该楼层有可稍带请求时，我们需要开门换请求吗？如果需要，我们的做换请求行为的度/边界又在哪里？
  
  我不知道。但是我做了偷懒的方法，也就是只在该层需要接人/完成请求开门时才会进行人员替换，可能把还没到目的地的低优先级倒霉蛋踢出，换高优先级的人进来，也就是如该点第一种情况，退化为第一点的策略。似乎，在所有情况下，我的这种方法都至少不会比原来不换人的情况差。
当电梯分配的请求数<6，时对 Look 策略的改良。

说的好听，其实并不是改良，只是特殊情况的处理，我也没用，只是想想。

在以上假设情况下，我们可以当作电梯容量是无限的。

当我们开门时，我们可以接该层所有请求。此时，除了相同方向的请求，接取的请求应该是包括目的地方向与电梯运行方向相反的。为什么？因为省电和等待时间，要是以后该楼没有新的请求，折返后电梯就不需要再在这层楼开门接请求了。

当请求数量少的时候我们这么做可以节省比较多的性能。但是还是得考虑，度在哪？

要是我们接了反方向的请求，这时候电梯请求爆单了。我们要在路上放此人下来吗？
1. 不放，此次该运行方向运行时电梯容量永久-1。
2. 放，那么你接这个人还让这个人离终点还变远了。
  - 比较良好情况，你放了这个人，转向后扫描本来这层就有人需要开门，不需要额外花费开门时间
  - 比较差的情况，你把原来在同一层两个人分开了，本来开一次门就可以接到两个人，但是现在你需要开两次门，让电梯运行节奏变慢了，后面可能很多请求都会变慢。
这个度很难把握，也许你可以根据这种情况写一种新的调度策略，通过全局请求数（？），该电梯目前的请求数（？）等信息算一个值，然后和阈值比，两种策略混着来，或者在请求输入结束后，请求数少于6（？）的时候，切换为这种改良版（？）。但是我觉得由于我们对于未来请求数的情况未知，可能在某种输入情况下你的程序肯定会变慢，这条思路我还是没有采用。

我只分析了这么多，实际上肯定还有更多的情况我没考虑到。在作业中，我只做了（在我的认知下的）一定不会拖慢电梯运行的策略。

说到底，我们很难把握性能分优化的度。优化的条件过于苛刻，可能会让性能优化并不大，优化条件过于宽松，可能会让部分测试点的性能变差，使得整体性能分不及优化前的分数。这要求我们对优化进行平衡。

而且我觉得，我上述提到的优化，优化的程度并不大，即使优化了也不能优化出很多的性能，不做相关优化也可以。

量子电梯

考虑电梯正常运行时我们的程序需要输出的信息，当我们接收到某座电梯的信息时，我们能准确描述出该电梯的状态吗。

电梯到达某一位置：[时间戳]ARRIVE-所在层-电梯ID

电梯开始开门：[时间戳]OPEN-所在层-电梯ID

电梯完成关门：[时间戳]CLOSE-所在层-电梯ID

乘客进入电梯：[时间戳]IN-乘客ID-所在层-电梯ID

乘客离开电梯：

如果乘客已到达目标楼层：[时间戳]OUT-S-乘客ID-所在层-电梯ID

否则：[时间戳]OUT-F-乘客ID-所在层-电梯ID

电梯接收分配：[时间戳]RECEIVE-乘客ID-电梯ID

电梯接收到临时调度请求：[时间戳]SCHE-ACCEPT-电梯ID-临时运行速度-目标楼层（该消息由官方包自动输出，同学无需输出）

电梯开始临时调度：[时间戳]SCHE-BEGIN-电梯ID

电梯临时调度完成：[时间戳]SCHE-END-电梯ID

电梯系统接收到改造请求：[时间戳]UPDATE-ACCEPT-A电梯ID-B电梯ID-目标楼层（该消息由官方包自动输出，同学无需输出）

双轿厢系统开始改造：[时间戳]UPDATE-BEGIN-A电梯ID-B电梯ID

双轿厢系统改造完成：[时间戳]UPDATE-END-A电梯ID-B电梯ID

举个例子，从现实的角度来看，电梯的移动，我们的输出没有描述移动的过程，仅仅描述了移动的“结果”，并没有描述移动行为的开始，以及电梯移动过程中的行为。也就是说，评测机并不知道我们从什么时候开始移动，也不知道移动时我们的电梯的行为，仅仅通过输出的 ARRIVE 信息和指导书要求的移动速度作为评判移动行为的合法性。

假设电梯最后一条输出信息的时间为10s，并且我们的电梯在 F1 层，需要往 F2 层移动，并且电梯可以随意移动，电梯移动到相邻楼层的时间为多少是合法的？当然，在 10s + v 以后的时间都是合法的。

那我们是不是可以认为，电梯在输出 ARRIVE 信息时完成了状态的突变（所处楼层的位置信息）。此时我们和评测机一样，只关注输出信息的合法性，忽略了现实中物理连续性的约束。

假设我们的运行速度 v = 0.4s/层 ，若电梯在10.4s可以到达邻层，但是当10.2s时我在本层接收到了一个可稍带乘客请求，那我当然可以选择是否要重新开门接这个乘客。假如选择要接这个乘客，我们不像现实中，需要多花一点时间从 F1 与 F2 两层楼中间移动到 F1 层，再进行开门接人的行动，而是可以直接在10.2s时开门接人。

这有点像，一座电梯在10s后分裂成两座不同状态的子电梯，其状态为两座子电梯的叠加态，一座子电梯在 F1 层等待最新请求，另一座子电梯正在从 F1 层往 F2 层赶。两个子电梯的动作都是合理的，然后我们通过我们程序的输出，将电梯的状态坍缩为某座子电梯的状态。这也就是量子电梯的量子性，是我们的程序中特有的性质。

我认为，这种性质主要来源于输出信息的信息量不足，这给了电梯一些运行时的容错，假如我们要求电梯在移动前必须输出对应信息，并且在移动过程中不能撤销移动操作，那么我们上述分析的移动和等待的叠加性也就不复存在了。

那么，如果我们需要将量子电梯思想融合进我们程序中，我们可以做什么优化呢？我们先不考虑 RECEIVE 约束：

电梯弹射起步。在电梯无乘客请求，并且距离上一条输出的时间间隔超过v时，收到第一条后电梯可以马上向乘客请求方向进行移动。

比如程序刚开始运行时，电梯没有输出过任何信息并且停在 F1 层，在1.0s电梯收到请求 F3->F7 ，那么电梯可以在1.0s到达 F2 ，也就是在0.6s开始向 F2 层进行移动，该移动行为的请求来源于未来0.4s后的乘客请求。
上述分析过的，移动和等待捎带同层乘客请求的叠加。根据具体情况进行选择。

比如，当电梯在 F1 层，2.0s接到请求 F2->F6 的人，电梯关门，准备往 F2 层移动，在2.1s接受请求 F1->F6 此时电梯可以选择2.4s到达 F2 ，也可以选择2.1s开门接人。
类似1， SCHE 也可以优化一下。比较已经等待的时间与 SCHE 指令要求的速度和当前速度的差值之间的大小关系。在符合“在两次移动楼层操作内”的要求时，在 SCHE-BEGIN 开始前判断，如果自己直接向目标楼层移动一层所花的时间，比开始后按照临时运行速度花费的时间短的话，我们可以考虑移动完， SCHE-BEGIN 后再按照临时运行速度移动。

但是hw6、7为了Ban自由竞争，要求正常情况下需要 RECEIVE 请求后电梯才可以移动，以上第一点也被Ban掉了。但是我们可以考虑以下逻辑

开门等。关门的逻辑和移动的逻辑有点像，以前的指导书都对关门时间进行了限制，把关门看成是一个过程，但今年指导书对关门的限制只有：开关门时间间隔需要大于一定时间，我们可以将关门看成一个即时行动、状态转移。

因此，在电梯完成所有乘客请求，等待新的请求的过程中，电梯可以考虑先不关门，如果新来的请求不在本层，可以立即关门并向着乘客方向进行移动，若新请求就在本层，那我们就省了开一次门和关一次门的时间。

更多、更全面关于量子电梯的介绍可以看wxm学长和bzh学长的文章口牙。

电梯系统的调度策略

面对多条的请求，我们应该选择哪一座电梯来完成呢？

调度器

调度器可以看成是程序里的具体的控制类，也可以看成是一个思想：把电梯-乘客请求之间多对多的关系，通过调度器的调度分配，简化成一对多关系。若采用调度器，电梯就只需要关注私有的乘客请求表，不需要关注更顶层的电梯系统接收到的乘客请求。

我觉得这也是有代价的，关系化简就意味着我们可能不能做到（理论上的）最佳调度——在保证正确性的前提下，最大化我们的性能指标。

我觉得调度器的调度策略可以分为两类：一类是随机的调度策略，对于不同输入、多次相同输入，该种策略的性能的方差可能比较大，而且问题不好复现，对互测和强测修Bug都不太友好；另一类是有偏向的调度策略，一般以某个指标量作为调度标准，也就是所谓的调参策略。

个人认为，随机调度策略的调度标准一般与我们目标性能无关的量有关，随机调度策略可以包括：随机分配、按id分配等。这里不详细介绍。

影子电梯

影子电梯其实就是一种完全模拟的方法。这种方法需要克隆原电梯的状态，然后通过单线程模拟原多线程电梯运行，然后根据单线程模拟的过程和结果获得我们需要的指标量，克隆出的单线程电梯被成为影子电梯，这种方法也就叫做影子电梯模拟。

当调度器采用影子电梯进行模拟时，如果我们选择模拟全部电梯接与不接的情况，一般称这些影子电梯的集合为影子系统。以电梯运行时间为例，如下：

请求调度第i部电梯\该情况下电梯运行时间\第i部电梯	1	2	3	4	5	6
1
2
3
4
5
6

看似表格有36格，但我们并不需要模拟36部影子电梯。具体实现时，我们可以进行剪枝：

对于同一个请求，每个电梯只有两种状态，接该请求和不接该请求，因此我们其实只需要模拟2*6=12部电梯
如果不考虑精确地模拟结果，我们可以考虑存储电梯上一次影子模拟的结果作为该部电梯不接该请求的模拟结果，这样做，我们只需要模拟6部影子电梯接乘客请求的情况，并在选择调度电梯编号后迭代更新存储结果即可。

一般的影子电梯以运行结束时间为指标量。不过，既然都选择完全模拟电梯运行结果了，我们也可以将性能指标：耗电量和乘客平均等待时间也纳入指标量的考察范围。比如：通过调参的方式给出一个目标函数，并且尝试最小化。

我们这里的调度器只考虑了当前乘客请求和电梯之前的状态，只能做到局部的最优解。

关于影子电梯的克隆方式，我采用的是和wxm学长相同的方法：获取六部电梯的锁后进行克隆。bzh学长也提供了他的思路：电梯主动克隆自身状态供调度器获取。

影子电梯的具体实现方式，可以参考wxm学长和bzh学长的文章。（原文写在OO讨论区，如果这里没有提供，可以找学长要哦）

hw7时，我在修改影子电梯时遇到困难。主要是我觉得双轿厢协同的模拟比较困难。对于影子电梯而言，从开始模拟开始，固定一段时候后定向投入乘客请求会比较困难。但是由于我的双轿厢协同策略逻辑是将两个轿厢分别看成两个单独的电梯，当我们向这个轿厢投入跨越两个轿厢的乘客请求时，会首先投入到具体某个轿厢，然后再在换乘层实现请求在两个轿厢之间的转移。因此，我如果想要影子电梯精确模拟出之后双轿厢（两个线程）的单线程运行过程，我最好可以实现定时投入乘客请求。

设置调度器调度乘客请求后，每一个电梯在运行时其实只会与调度器线程产生关联，电梯正常运行时其实只与自己这个线程有关，也只与自己的状态有关。这也是可以使用影子电梯模拟的前提。但是按照我的协同策略，双轿厢电梯在运行时还与另外一个轿厢线程有乘客请求的交换关系，因此hw6中的影子电梯逻辑不能很好地兼容我的迭代要求。追求影子模拟的精确度时，我也想过用一个单线程同时模拟两个轿厢之间的运行，但是我感觉这样会使得影子电梯的逻辑变得复杂，性价比较低。最后我放弃了影子模拟的精确度，尝试通过其他方式近似双轿厢协同对模拟结果的影响。

完全影子电梯

wxf学长的思路完全影子电梯 | FISH

调度器调度的时机

在hw6、hw7中，我们的电梯新增了 SCHE 和 UPDATE 这两种异常处理请求。这两种请求要求电梯需要先根据具体需求满足某种状态，然后电梯才能进入异常处理，处理时电梯属于静默状态，也就是：输出COMMAND-BEGIN 和输出COMMAND-END之间电梯不得参与电梯调度，即不能开关门、进出乘客、上下楼层、输出RECEIVE（见RECEIVE约束）等。

静默状态的电梯不能参与电梯调度，那我们的调度器需要给电梯进行乘客请求的调度吗？

我们需要仔细考虑以下极端情况：六部电梯都处于静默状态，或是五部电梯处于静默状态，一部电梯正常运行。后者在24年被成为”围师必阙“数据点，杀伤力广大。

假如我们的调度器不会给静默状态的电梯调度乘客请求，我们可能需要解决以下问题：

六部电梯都处于静默状态时，我们的调度器不能一直尝试调度，否则会花费很多 CPU 时间。
五部电梯处于静默状态，一部电梯正常运行，我们的调度器不能把所有的乘客请求都调度给正常运行的电梯，否则一部电梯处理全部乘客请求，很容易 TLE 。

我的调度器策略采用的是影子电梯，会给符合条件的静默状态电梯调度请求，但是对输出/评测机而言，我的电梯在期间并未参与电梯调度。

具体实现而言，我在电梯内新增了一个类似 buffer 的请求表，并且将静默状态下的请求调度的实现分成了两个部分，第一个部分是静默状态时往 buffer 内部增加请求，第二个部分是静默状态结束后将 buffer 内部所有请求移入电梯的乘客请求表内，并且输出相应的 RECEIVE 信息。 buffer 起了一个存储乘客请求和中转的作用。

自由竞争

~~为什么Ban了自由竞争~~

自由竞争和调度器不同之处在于，自由竞争没有集中处理乘客请求。所有电梯共享一个请求表，所有电梯争夺乘客，谁抢到乘客请求谁就去完成该请求。

程序运行时，每个电梯根据自己的运行策略运行，在电梯 ARRIVE 每层时访问请求表内的请求，若有可捎带的请求即将请求移除，然后去处理乘客请求。

在本次作业中，我们的电梯在正常运行时，只有 RECEIVE 到某个乘客请求，电梯才能开始移动。因此，在电梯刚开始运行时，若电梯没有 RECEIVE 乘客，则电梯不能移动，也不能竞争乘客请求，没有乘客请求电梯也就不能移动。这就陷入了死循环。

即便如此，我们也可以根据限制稍微修改一下逻辑，让自由竞争适配目前的要求。

比如，在之前”电梯运行策略”之中提起过的 ALS + Look 策略。电梯没有 RECEIVE 请求之前，电梯不能移动，那我们就先让电梯 RECEIVE 一个请求（类似主请求），电梯就可以自由移动了。也就是说，当并非所有电梯都可以移动时，我们不采用自由竞争策略，而是选择尽量将乘客请求分配给电梯，让电梯可以都动起来。当所有电梯都可以动起来后，我们再考虑让电梯根据自己的移动策略进行移动，并且自由竞争请求池中可以捎带的请求。