OO第二单元总结——多线程电梯调度

OO第二单元总结——多线程电梯调度

第一次作业

基本思路

第一次作业要求实现单部可稍带电梯的调度策略，对于刚刚接触多线程编程的我来说的确是有些难度，在经过周三的实验和往年博客的启发之后才做出了以下的设计策略：

• 基本架构
  使用了生产者-消费者模式，输入线程不断读取输入并交给需求队列（调度器），电梯线程与需求队列进行交互，从中获取合适的请求执行。

• 调度策略
  因为本次作业并未限定电梯的承载人数，所以我让电梯每到一层就将该层所有等待的乘客都载入电梯，并将电梯内请求中最近的目的楼层作为当前运行目标，不考虑当前电梯是上行还是下行。如果电梯里没人，则选择最近的一个请求去接，将该请求的起始楼层作为当前运行目标。

• 线程安全
  本次架构中能够引起线程冲突的只有需求队列（调度器）对象，我选择了将其可能被输入线程或电梯调用的方法都加上了synchronized关键字，进行加锁。对于程序的结束，我选择在输入线程读入null之后，对需求队列发出一个输入结束信号，这个信号对电梯可见，同时输入线程自行结束；电梯在现有需求均已完成，且输入已经结束的情况下结束。

基于度量的程序结构分析

UML图：

复杂度分析（只截取了复杂度最高的一部分，下同）：

本次作业的代码复杂度比较低，唯一一个复杂度超标的方法是因为要处理本地测试时的输入，没有过多思考架构，而是除了将预处理单独分了一个类进行外，其余的读取、按时间输入等工作都一股脑的放在了输入线程类的run()方法中，导致复杂度过高。

bug分析

本次作业中我在强测和互测中均未发现bug；在互测时测出了别人的一个bug，应该是因为多线程处理不当造成的CTLE。

性能分析

本次作业的强测中我的性能分并不高，可能是因为不分上下行只管距离近，且在途中随时切换目标的策略会造成电梯来回上下跑，损失了一定的性能。

第二次作业

基本思路

第二次作业相比第一次，新增了电梯承载人数的限制和多部电梯的协同，但在第一次作业的基础上来看还不算很难。我曾尝试完全使用第一次作业的调度策略，让一堆电梯去抢人，但是这样可能会出现几个电梯都去接同一个人，造成其他电梯空跑的问题，于是我修改了调度策略，保留了基本的生产者-消费者模式架构。

• 调度策略
  第一次作业中，对于当前目标的实现，我只是读取了一个目标楼层数，该请求还留在请求队列中。这也是上述问题出现的原因。因此，我选择将主请求从需求队列中取出，在电梯类里实现其是否上下电梯等的判断。同时，本次作业的电梯不再是无限容量的，所以考虑电梯运行方向也可以提高性能。

基于度量的程序结构分析

UML图：

复杂度分析：

可以看出本次作业和第一次作业的架构一模一样。几个复杂度过高的方法中，除了从第一次作业继承下来的run()方法，其他几个方法都涉及主请求的处理。由于主请求被单拿出来放在了电梯类中，导致本来一致的处理要多考虑一堆特例，这也导致了复杂度的提升。电梯类的总复杂度过高而平均复杂度正常，说明我在电梯类中堆叠了过多的功能，应当考虑将其拆分。

bug分析

本次作业在强测中翻了车，只得了70分，根本原因是我在中测通过后便没有再进行本地测试。事实上强测中出现的两个bug都极其简单，一个是因为第二次作业中楼层数变多导致的在寻找最近的主请求时可能出现的空指针，致使电梯中途宕机关不上门；另一个是因为在判断能否上人时对于结束循环条件位置的错误，导致在电梯已满时仍会每次漏出一个人，既没有上电梯也不再在请求队列中等待，直接人间蒸发。在互测中被hack的一次也是上述bug之一。另外，在bug修复的过程中我还发现了一个导致RTLE的bug，多次测试难以复现，本地测试中更是一次都没有复现过。在仔细思考了线程结束条件以防止死锁之后，最终也没有找到原因，只是在wait()中添加了10s的时间限制。

在互测中我共找出了三名同学的各一个bug，其中一个是RTLE，推测是发生了死锁；另外两个是WA。

性能分析

本次作业的性能尚可，强测中通过的测试点性能分均在19分左右，由此看来第一次作业的性能分低确与不考虑上下行有关。

第三次作业

基本思路

第三次作业难度有一个较大的提升，新增了换乘需求。我选择按照指导书的提示，将一个无法直达的请求进行分割。

• 基本架构
  仍然延续生产者-消费者模式，不同的是在输入线程将请求交给托盘之前，增加了将一个请求包装成为一个Person对象的步骤。一个人有两个请求，并用boolean域表示其当前在执行哪一个请求。若可以直达，则将该Person对象第一个请求直接标记为完成状态。另外，我还将一些设定上的东西集中在了一个Static类中，比如电梯能到达的楼层。

• 调度策略
  本次的调度策略和第二次作业几乎完全一致，区别仅在于寻找主请求时不再选择最近的请求，而是选择先来的前七分之一请求中最近的一个，因为无法直达的请求已经被包装，和一个普通的请求是一致的。对于换乘策略，我选择的是静态规划。对各种电梯所能停靠的楼层进行分析后，我选择将与A型有关的换乘都放在1层和15层，而B和C之间的换乘则选择起止楼层的中点。另外，本次的线程结束条件有所改变，需要考虑一个已经进电梯的人的第二个请求。我选择将有第二次请求的Person同时放进另一个队列中，并在需要的时候进行检验，若该队列中第二次请求不涉及某型电梯，且输入已经结束，则其在完成工作之后可以结束。

基于度量的程序结构分析

UML图：

复杂度分析：

本次作业的架构更加复杂，不过还是能看出前两次架构的影子。本次新增了一个复杂度过高的方法，parseInput()，这个方法是用来将一条输入包装成一个Person对象的，可能是因为分支太过于复杂，对于起、止楼层组合的判断使得复杂度超标。几个类的方法过于集中（有些甚至只有一个），分化不够，也使得平均复杂度过高。

bug分析

本次作业在强测和互测中均未发现bug，在互测中也未发现其他同学的bug。第二次作业遗留的那个大概是死锁的bug也没有出现，可能是侥幸，需要进一步的测试。

性能分析

本次作业性能也还可以，大部分仍在19分左右，但有一个测试点性能分直接爆炸归零，一开始我以为是第二次作业遗留的bug使得程序多运行了10s或更多，但在输出上并未显现出那个bug的特征——莫名其妙的停止输出一段时间，所以应该是这个测试点正好攻击到了我的调度策略的弱点。

SOLID原则分析

• SRP：本次作业中共有10个类，其中大部分类都符合SRP原则，但是RequestInput类中包括了获取输入的请求和本地测试中处理时间两个职责，应当分开。
• OCP：符合程度尚可，在作业的迭代过程中我的修改主要还是集中在条件的改变上，例如电梯承载人数的变化，而不是功能的新增。新增功能都是依靠扩展实现的，例如将PersonRequest包装为Person，两者对外接口基本一致。
• LSP：本次作业中我除了线程继承Thread类之外没有用到继承。
• ISP：由于本次作业中没有一系列有相同操作的事物，本次作业中我没有使用到接口。
• DIP：实现的不好，Elevator类和InsideRequest类几乎是绑死的，同理还有Elevator类和RequestQueue类等。

测试和bug发现策略

这一系列作业中我还是没有使用自动测评机，只能手动构造测试。在本地测试时，首先进行一些简单的测试，例如只给出一条请求；然后进行一些组合测试，测试功能的配合程度。对于互测，我选择了黑箱测试，没有阅读其他同学的代码，而是手动构造了一些边缘数据或是大量请求进行测试。这样的策略也能发现一些其他同学的bug，但纯属碰运气，其实效果并不好，但对我来说也基本够用了。

心得与体会

首先，本地测试很重要。第二次作业的翻车完全是因为犯懒没有充分本地测试。其次，第一次作业一定要仔细思考架构。和第一单元不同，第二单元的作业我真正做到了迭代开发，没有进行重构，一个很明显的区别就是工程量有很大的下降，比起第一单元的手忙脚乱，第二单元的后两次作业在时间等各方面上都更加宽裕。但是，迭代开发有一个问题，就是一些之前的细节可能会被遗忘，例如我在第二次作业中忘记了最高楼层增大了，在选择最近请求时就会出现问题，其实就是一个数字的作用。因此，我认为在进行新的开发之前把上一次的代码再阅读一遍，不用太过于仔细，因为自己写的东西大致过一遍就基本都能回忆起来，这时再进行迭代可能会好很多。