2021 OO第二单元总结（多线程电梯）

一、同步块的设置和锁的选择

第五次作业

• 在本次作业中，我在共享对象WaitQueue里面使用了synchronized块。将其自身对WaitQueue操作的方法块都加了synchronized锁。WaitQueue是储存还未处理的乘客请求的一个类，InputDevice和Elevator类均会向它增加/取出请求，故将增加、取出和访问操作上锁，保证了线程安全。

• 我的代码中一共有两个线程：输入线程InputDevice和电梯线程Elevator。未在第五次作业中实现调度器。

• InputDevice的任务是获取输入的任务，传递给WaitQueue；Elevator的任务是获取WaitQueue里的任务，并决定接下来该怎么走。WaitQueue中的诸如addRequest、getFirstRequest方法、removeRequest方法等都是这两个线程所调用的，因此为了线程安全，将它们加了synchronized锁。

第六次作业

• 第六次作业的需求从实现一部电梯变为了实现三部多线程电梯，并且可增加至五部。于是加入了调度器类Scheduler。同时由于电梯数量的增多和调度器的实现，受周五实验课的启发，仿照其模式，将共享队列分为了一个WaitQueue和多个ProcessingQueue。这些队列由输入线程InputDevice、调度线程Scheduler和电梯线程Elevator所共用。
• 为了线程安全，将WaitQueue和ProcessingQueue的addRequest、getFirstRequest方法、removeRequest方法块等都加了synchronized锁。针对不同的到达模式（Morning、Night、Random）也在ProcessingQueue里面实现了不同的方法如getFullRequest方法块（用于早上到达时，将输入结束后所有乘客装进电梯或满员时才返回）、getNightStart方法块（用于晚上到达时，选择所有需求中起点楼层最高的需求作为主需求）都需要加上synchronized锁。

第七次作业

• 第七次作业的需求在第六次作业的基础上的变动是将电梯分为了不同参数的种类。最大的变化是不同类的电梯停靠的楼层不全一样，乘客可能涉及换乘。
• 为满足上诉需求的变化，我仅仅需要改动的是Scheduler类下的分配方法，将合适的指令分配给合适的ProcessingQueue。以及实现为一个请求设置中转楼层（通过实现一个具有中转楼层属性的需求类RequestChangeable）。
• 上诉改动均不涉及锁和同步块之间的关系的变化，还是维持以前第六次作业的同步块的设置和锁的选择，并为WaitQueue中新实现的requestFromWaitingToDealing（从等待队列移至正在处理队列）方法块、removeFromDealing（从正在处理队列中移出）方法块加锁。

二、调度器设计和线程交互

第五次作业

• 第五次作业由于只有一部电梯和一个共享对列WaitQueue，故没有使用将WaitQueue中的需求调度入电梯的调度算法。而是将整个WaitQueue作为电梯的一个属性。尽管第五次作业没有对电梯的运行策略作要求，但为了不被某些特殊情况卡时间，故我的电梯本身实现了ALS算法。电梯就将整个请求队列WaitQueue作为ProcessingQueue，使用ALS算法运行。

第六次作业

• 由于变为了多部电梯，故需要增加一个分配乘客指令的调度器Scheduler。它负责从WaitQueue中取出第一条指令（到达时间在队列中最早的指令），然后将其按一定的策略放入某个电梯的ProcessingQueue中，并对电梯进行通知（若电梯正在等待则将其唤醒）。当输入结束并且所有乘客请求都已完成时，调度器Scheduler会通知所有电梯停止运行。
• 对于分派指令给不同电梯的算法，我考虑得十分简单。即来一个指令就分配给当前指令号对可用电梯数取模后对应的电梯（类似循环平均分配）。由于本次作业对于请求分配没有作过多要求，我就简单的使用了这个方法进行分配。

第七次作业

• 第七次作业由于电梯的种类发生了变化，每种电梯能到达的楼层不尽相同。为了能让所有电梯都充分运行起来，需要采用合适的分配策略和换乘策略。
• 第七次作业的整体架构和第六次作业大体相当。对于第七次作业的分配策略，我使用了打表的方法。按照出发楼层和到达楼层的不同将请求类型分为了几大类，例如：若到达楼层和出发楼层都在1_3或1820楼的，就直接交给C类电梯，将到达和出发楼层全是偶数的交给A类电梯，为出发楼层和到达楼层奇偶性不同的交给A和B换乘等等。
• 上述静态分配策略似乎在性能上不够强大，并不能根据电梯运行情况（如ProcessingQueue人数、电梯运行方向等）做出相应动态处理。许多大佬没有使用换乘但是分配和电梯运行得当，在强测中仍然能得99、100分，而我的电梯只有92分。分析可能是因为作了许多不必要的换乘操作，使得两个电梯花了很多时间在转移上。例如4楼到7楼，我会先让A电梯将人运到5楼，再将从5楼到7楼的指令分配给B电梯。如果此时B电梯距离5楼较远，B电梯再转移至5楼就会额外花费很多时间，得不偿失。

三、第三次作业架构设计的可扩展性

• 我的第三次作业主要为输入线程InputDevice类、电梯类、调度器Scheduler类、待分配表WaitQueue类、Processing处理表Queue类、可变请求RequestChangeable类。类具体的结构关系见UML图。

• 架构设计上，采用了课上讲过的生产者—消费者模式，线程InputDevice属于生产者，将输入进来的PersonRequest指令转换为可变请求RequestChangeable对象，并放在WaitQueue里。WaitQueue属于一张大桌子，上面放着还未分配给电梯们的指令。接下来由管理员Scheduler实现调度（分配指令到不同电梯的小桌子ProcessingQueue上）。电梯属于消费者，将属于自己的小桌子上的请求取出并根据自身的ALS算法作相应处理。此外，当电梯开门下客后，需要判断乘客是到达了中转站还是终点，若到达终点则将请求移除；若到达中转楼层，则将请求的起点改变后，重新放到大桌子交由Scheduler分配。

• 可扩展性较好的地方。由于这次作业的需求是多种参数不同、停靠楼层不同的电梯同时工作，我实现了可以在初始化时就设置不同参数（运行速度，最大载客量）的电梯。如果后续需要增加更多种类的电梯时，可以直接将参数输入便可，不用通过继承关系构建很多子类。此外，电梯实现了换乘，所以在功能方面设计还是比较完整的。

• 可扩展性较差的地方。此次作业可扩展性较差的地方在于我的调度策略和设置换乘的算法。以上两个功能都是由调度器Scheduler完成的，但是调度策略和换乘算法都写得很简单。如果后续增加了电梯运行情况的复杂度的话，我的调度和换乘策略又得重写一遍，可扩展性不好。在性能和复杂度上甚至还不如设计成让电梯自由竞争WaitQueue里面的请求。

• UML类图
  
  

• UML协作图
  

四、分析自己程序的Bug

第五次作业

• 轮询导致CPU时间过长。第五次作业未在强测发现bug，但在测试中测和弱测时，发现了CPU时间过长的现象。后面发现是由于在Morning模式下，一直询问输入是否结束或电梯是否装满导致的。将轮询改为wait-notify模式就解决了超时。若输入未结束且WaitQueue内没有请求了，就wait等待。当输入了请求再notify唤醒。
• 获取一个Request时进入等待的条件不对导致无线等待。我最开始写WaitQueue获取请求的方法时，使用的条件是只要WaitQueue为空就进入等待。但这种条件不全面——如果在输入结束到来之前，WaitQueue就已经为空了，那再请求Request时就进入等待，输入结束到来将它唤醒并跳出while循环并结束线程，没有问题；但如果是在WaitQueue为空了之前，输入结束就到来了并执行了一次notify，那么等到WaitQueue为空了后，再次进入等待时，以及没有可以唤醒它的语句了。因此需要将获取请求的方法时，使用的条件增加为WaitQueue为空且输入还没有结束。

第六次作业

• 一个小但是后果严重的其他类型bug。未在中测和弱测中发现bug，但是强测错了14个点。原因很小，就是因为在Scheduler分配时电梯的数组下标是从0_{4，而我用成了1}5，当电梯数量以及乘客指令增多后，就很容易出现数组越界的异常，在bug修复中仅改了3行代码。原因还是在我没有做好课下的测试工作，仅仅认为过了中测就没啥大问题。还有就是感慨中测的数据点挺弱的，不能全靠这个评测，要自己构造复杂样例。

第七次作业

• 关于操作原子性的线程安全的bug。未在强测中发现bug，但是被互测hack了一个点。这个bug很细节，但是很感谢这位找到bug的同学，因为找到这个bug需要的数据比较难构造。在电梯下客时，若该乘客只是到达了中转楼层而未到达终点时，需要将该乘客请求从处理队列Dealing中移除，并加入到WaitQueue中等待Scheduler调度。上述两步操作应该是原子性、不可分割的。但是我在写的时候写成了分开的两步，且没有加锁。在将该乘客请求从处理队列Dealing中移除之后，且加入到WaitQueue中等待Scheduler调度之前，如果Scheduler获取Request的方法正在判断是否需要进入等待并且满足（WaitQueue恰好没人&&输入结束&&Dealing处理队列为空），那么Scheduler结束电梯和自己，但是此时那个乘客还在中转楼层，没到终点。

五、发现别人Bug采用的策略

• 主要是手动构造数据，尽量选出比较极端的样例。但是由于手动构造样例效率较低，也不太全面，在第七次作业时选用了其他同学写的自动评测机来测试。对于多线程的bug有可能复现不成功。
• 本单元的测试策略与第一单元相比，可能在于需要在规定的时间内完成乘客请求。时间限制也是正确性的一个方面。此外，多线程的bug比第一单元的bug要难以复现。提高测试数据的强度可能会增加出现bug的可能。没有采用特殊的策略来发现线程安全的问题。

六、心得体会

1、线程安全

• 需要仔细考虑对共享对象的操作，合理使用synchronized锁。
• 使用wait-notify等方法而非轮询的方法。
• 需要根据三次不同的题目需求和实现来判断是否结束电梯。否则很容易导致无限等待或是提前结束。如第一次作业是输入结束且WaitQueue为空；第二次作业是输入结束且WaitQueue和所有ProcessingQueue都为空；第三次作业是输入结束且WaitQueue和处理队列Dealing都为空。
• 应用生产者—消费者模式，使得需求抽象化。

2、层次化设计

• Arguments类比较多余，没有必要实现。在第七次作业中只是包含了开关门的时间的参数而已。

• 某些类如电梯Elevator代码量比较冗长。前期的测试做得很不到位，导致了第六次作业失分严重。想到第六次作业只是在原来第五次作业的基础上增加了两个电梯和一个调度器，而调度策略又是最简单的那种，因此没有想到会出现bug。结果却在写调度策略时创作了bug。希望后续作业做好测试，不仅仅依靠中测。