OO第二单元总结

作业架构及分析

hw5

基本要求

A-E五栋楼，每栋楼里一部电梯，实现电梯调度模拟。

基本设计（架构&策略&同步块&调度器）

本次作业由于之前没有接触过多线程编程，我小心翼翼地参（照）考（抄）了实验架构。采用生产者-消费者模式，构建ReQQ类作为“托盘”作为共享对象，分别在:

（1）总调度器中实例化为allReQQ，用于存储未被投喂至电梯的请求。
（2）每部电梯中实例化为processReQQ，用于存储该楼座中的所有请求。

• 其中allReQQ为输入线程InputThread类和调度器线程Scheduler类所共享，processReQQ为调度器线程Scheduler类和各部电梯线程Elevator类所共享。可见调度器是向上承接输入线程，向下投喂请求到电梯的一座“桥梁”。其在上述两个生产者-消费者模式中分别承担了消费者和生产者的角色。此次作业Scheduler还基本只起到了中转的作用，保存了五座楼栋对应五部电梯的全部请求，每次将输入请求从上一个“托盘”取出向下一个“托盘”投喂，选择依据仅为乘客对应的楼座。

• 而线程安全方面，由于是在实验架构上进行的修改，基本只需要关心共享对象即ReQQ类的安全问题，具体操作为：修改ReQQ内部存储请求的ArrayList的方法全部套上synchronized使之成为同步块。

• 避免轮询的wait和线程结束方面，主线程外三个线程类均采取：外部while(true)、满足特定条件break跳出循环，结束线程的方法。

（1）输入线程InputThread官方包已经实现阻塞，不需要wait，而结束条件为读取null时跳出while(true)即可。而其他线程的结束的必要条件均含输入已经结束，故需要在共享对象ReQQ中设置isEnd标记外部输入是否已经结束。

（2）调度器中只需要其内部存储请求的队列为空时wait即可，具体实现为ReQQ共享类的getOneRe方法设置wait。结束方面即为队列为空且输入未结束即isEnd==True。

（3）电梯不需要运行时需要wait， 或者其实sleep(50)也行， 即其内部请求队列为空即需要wait。在实验架构上这个wait是唯一需要自己新增实现的。具体方法为在共享对象ReQQ中专门设置判断电梯是否需要wait或需要结束电梯线程的方法judgeWait()作为while(true)中true的替代。检测到输入结束且电梯无请求时结束线程；否则若电梯内无请求则电梯进入wait()。

• 另外需要注意的一点是，贡献对象判断是否需要wait()的方法不能用if,也必须用while（）所套的循环，原因是若进入了wait后又被奇奇怪怪的notifyAll唤醒，但实际上仍满足应当wait的条件，就会造成不应当退出wait时退出了wait的错误，即每次唤醒线程都应接着判断是否满足进入wait的条件，进入wait。

• 退出wait的notifyAll方面，我们需要针对调度器进入wait和电梯进入wait后的叫醒方法。一种是正常wait后来了新请求，故需要在共享对象ReQQ中的addoneRe()方法和getoneRe()中设置notifyAll，分别针对调度器线程和电梯线程做唤醒；另一种是wait时输入结束了，故需要在setEnd()时notifyAll，注意这里由调度器给电梯setEnd而非输入线程直接setEnd，因为后者可能会在调度器分配请求时直接叫醒没有来得及拿到新请求的电梯然后结束线程。这里我经过测试和思考后删去了不必要的notifyAll操作，为之后hw6清除了隐患（歪打正着）。

• 输出线程安全方面，我参照讨论区同学分享，通过单例模式实现了一个输出安全的OutputThread类。（不是线程）

• 调度策略方面，参照往届和周围同学经验采取了look策略。策略具体不再赘述，大致实现为：

    public void run() {
        boolean isUpping = true;
        while (buildingReQQ.judgeMove()) {
            isUpping = decideMove(isUpping);
            isUpping = decideAction(isUpping);
        }
    }

电梯所在座的请求队列为BuildingReQQ,通过布尔型isupping记录目前电梯“试图”上下行的方向。decideMove()函数判断电梯是否要上下行及做出移动行为，并更新isUpping。decideAction()函数判断电梯是否要对当前层开关门，并更新电梯的isUpping。

UML类图

UML时序图

hw6

基本要求

• 新增“横向电梯”，可以在1-10层相同层的A-E楼座间移动。（乘客均不需要换乘就可达目的地）
• 新增“增加电梯功能”

基本设计（架构&策略&同步块&调度器）

• 基本沿用hw5设计（做了一些变量名和底层实现的修改），新增满足以上要求的设计。

• 修改上，hw5中为了省事，我只在电梯内部封装了一个ArrayList<Integer>存储在电梯里的人的ID（好蠢啊）。而一栋楼有多电梯后，我做了每栋楼（或每层）的电梯共用一个外部请求队列的修改，用以标记楼座或楼层还没上电梯的乘客。而每个电梯内部再封装一个请求队列用于存储上了电梯的乘客。

• 对于横向电梯，直接新增LoopElevator类，这里考虑到功能仍然略有差异(懒)没有写继承关系。其内部变量与纵向电梯NormalElevator完全一致，方法上有一些变动。除了上下改为左右，int改为char外，还有一个“环形”的bug在。考虑到横向电梯有5个可能位置且可以环形运动，我将look策略中的“方向相同”就接改为了“只要碰到人就接”。（周六19:30发现了bug的地方）最后，横向的look判断方向上我没有采用高级的取模而是直接通过打表实现。

• 对于新增电梯，采取新线程AddElevatorThread类，承接inputThread读取的新增电梯请求。具体的实现也是生产者-消费者模式，新增一个缓存新增电梯请求的托盘类AddElevatorReQQ，生产者为InputThread，消费者为新增的新增电梯线程。也就是说输入线程这一生产者向两个托盘分发请求，分发依据为请求的类型。新增共享对象的同步块设置、notifyAll设置和之前的共享对象类相同。新增线程wait、notify设置方法与电梯类中的相似，均通过while条件调用贡献对象方法判断是否需要等待或者退出循环结束线程。

• 最后，多部电梯的调度策略上我选择了实现最简单的自由竞争，在请求量大的情况下，自由竞争相较于平均分配无较大差异，甚至有时更优。另外本次从大佬同学处学习到了look策略的一个优化——在电梯接人时，按照当前目标到达距离由远及近的优先级接人，可以大幅提升效率（详见dl博客—https://www.cnblogs.com/locnxe/p/16207220.html）。

• 在同步块设置上还有一个细节，就是本次作业由于电梯间也有了共享对象（同座/同层），故遍历时需要加锁，我还是暴力在遍历时套用了 synchronized来避免这一问题。

• 另外值得一提的是，如果采用第一次的实验架构，notifyAll过多很容易造成一个楼座/层有多电梯时发生轮询。一个电梯在接到人后，若外部不再有新请求，别的空电梯本应该进入wait。但notifyAll过多会让运行中的电梯不断叫醒空电梯，引发轮询。

UML类图

UML时序图

hw7

基本要求

• 乘客可以换乘了，请求只要目的地终点不完全相同就行。
• 电梯可以定制速度、最大载员；另外横向电梯可以定制可达楼层。

基本设计（架构&策略&同步块&调度器）

• 基本沿用hw6设计。

• 针对定制电梯的载员、速度，将hw6新增电梯的函数、电梯上下楼函数里的sleep函数等稍微修改即可。横向电梯还需要解析掩码，我选择直接采用boolean[5]解析出可达楼层存储，并加入作为横向电梯的一个属性。而横向电梯要特别注意不能乱开门、不能乱接人。尤其注意这里很容易造成隐蔽的轮询（详见bug分析）。这里我还修改横向电梯类，使得其在内部没有人、外部无人能接（同时判断其实楼座和到达楼座可接）的情况下wait，并且在运行时在不可开门的楼座直接退出decideAction函数避免离奇接人。

• 针对换乘，为了追求稳定和安全我选择了基准换乘策略，最多一次换乘且为纵-横-纵的方式，横向选择最近的那个楼层。另外我没有做相同距离时选择速度快的优化或选择层数绝对低的操作。具体实现参考了第二次实验中流水线模式将请求返回调度器的操作。为了能够解析乘客的当前位置和目标位置差异以进行路径选择，我重写了乘客请求类ExtendPersonRe，新增当前所处楼层、楼座和当前目标地楼座楼层，结合目标楼座楼层，可以更方便地对乘客的行动策略进行解析。而在这次作业我的调度器才有了类似于“调度”的功能，根据乘客的当前位置和目标位置得出当前目的地位置投喂到对应楼座/楼层中。每次乘客出电梯时维护当前位置，然后在电梯线程中判断是否到达了最终目的地，若到达则直接删除请求，否则发回至调度器中进行下一步的解析。相应的为了记录有哪些横向电梯可选，我新增了LoopElevatorTable类记录已有横向电梯的数据，供调度器使用。而如此的LoopElevator类便是一个共享读、单侧写对象；同样将方法均设置用synchronized设置为原子操作，又因为这个共享对象不承担“托盘”功能只负责传递信息，故不需要写wait及notifyAll方法。

• 另外，换乘带来的一大问题是线程的结束问题，因为存在请求的返回和再分配，输入结束后会出现短暂的“请求队列真空”，若不做处理就会发生乘客中转时所有线程结束退出程序的问题。对这个问题我同样参照了第二次实验的计数器设置，通过单例模式实现一个计数器，不过不同于实验的是我没有使用计数器阻塞主线程，而是用其作为输入结束后setEnd的一个判断条件。读入一条乘客请求计数器加一，每次乘客到达最终目的地计数器减一。在输入线程读到null后，进入计数器的judgeEnd函数，这里若计数器不归零则进入wait，而乘客到达最终目的地时调用计数器的计数减1的函数，这里设置对应的notifyAll，让judgeEnd函数判断是否需要setEnd。

• 最后，直到本次作业我才发现电梯进多少人应该在电梯关门前进行判断，而非开门时就定好。前两次作业强测时这点对性能分影响不大（我的一厢情愿），但需要换乘时一条条突出请求非常容易让本来应该一起换乘的人被拆成两半。

UML类图

UML时序图

复杂度分析

这单元其实没太注意复杂度的事，甚至电梯的look实现算法还写了60行多一点被我压到60行......简单列举hw7复杂度如下表：

只取复杂度最高的几个方法，很显然都是实现look调度策略的方法：

其它方法的复杂度都不大。可见实际上实现电梯调度的函数应该被我拆的更碎一些 （好像我根本没有面向对象思维......）
另外感慨：方法数足够多，方法平均复杂度就可以非常低~

类复杂度一一列举如下：

调度器的平均圈复杂度主要是方法数过少所致的，而两个电梯类的复杂度主要是其调度算法函数所致的。

Bug&Hack分析

Bug分析

这一单元的作业在公测调试时先后发现了很多Bug和性能问题，列举如下（首先在这里鸣谢臻哥、吕哥的带带）：

hw5

• 刚写好look策略的调度时边界判断出错，电梯上下0层11层。

• look策略优化问题：电梯停摆，初始层来人时，电梯会先上/下一层再折返接人。

hw6

• 在电梯遍历同座/层共享的电梯外请求队列时暴力加锁，粗心把上下楼函数也套了，导致同层间的电梯诡异的每0.4s只能走一个。

• 环形电梯由于最初想同方向再接人，发现会有”起始目的地方向与当前同但最终方向不同“各种排列组合的情况，考虑不周导致了横向电梯死循环不接人的尴尬局面。（19:30发现bug还好改掉了）

hw7

• 线程异常结束：未考虑到输入线程结束后的请求队列真空，导致线程异常结束。

• 轮询1:改掉上面的问题，发现inputThread输入线程结束后没了官方包的阻塞读取线程导致轮询。

• 轮询2：横向电梯最初wait条件没有加接不到人且内部为空，导致一层多部横向电梯，有些电梯接不到人本该wait的时候进入轮询。

• 性能的大问题：判断近人最好在关门前，不然0.4s的窗口期新来的人接不到。

而在强测和互测中均未出现正确性Bug，三次的得分别为98.8、98.9、98.4。

前两次性能没有最大化的原因可能有：没有做量子电梯常量级别优化，进人放在开门后导致中间0.4s新来的人接不到，函数写的复杂度过大，每次运行程序损失了少量时间、hw6遍历共享对象暴力加锁保证了安全性却牺牲了性能等等。第三次作业除了前面的部分问题外主要还存在换乘策略的问题 ，毕竟眼见dl同学天秀最短路算法。

Hack分析

与第一单元不同的是，这一单元测试数据手搭极其困难且效率也很低，另外许多问题多次测试才能复现或者更加隐蔽，更加需要覆盖式的轰炸才能显现。总之就是——有评测机会好的多，或者需要有时间和耐心阅读他人代码。

hw5没想到会重测，hack到容易hack中的数据就摆了，最后重测了，然后一刀也没中......

hw6、7各成功hack2人，一次隐蔽的线程不安全问题ConcurrentModificationException、一次输出时间戳非递增、一次CTLE轮询、一次电梯反复到达本层问题。

• （臻哥的）评测机轰炸数据，检查出了CurrentModificationException问题
• 边界压力数据，例如卡边界投喂时间、投喂上限条一模一样的输入、枚举所有横向电梯楼层可达情况在同一时间投喂等等，发现了剩余三个问题。

（所以可能边界压力数据其实很适合自测和互测，尤其是hw7课下有某位dl同学构造了add所有可能的电梯，然后同时间投入所有可能出现的移动请求两次的上万条数据。测完发现不会轮询、能通过同学写的正确性检查程序安全感直接拉满。）

(救命每天被ddl追着杀 课太多了 真的没时间读代码啊)

心得体会

多线程编程需要耐心，码量可能相对小一点，但细节非常多，需要仔细考虑到所有情况，并在大多数时候进行颅内debug。线程交互、线程安全都是全新的概念，需要掌握。此外设计模式的魅力在这单元开始展现，生产者-消费者模式的代码编写重难点个人认为在共享对象的选取、设计上，实验架构的生产者-消费者模式和其共享对象设计伴随了我整个单元。

另外，多看讨论区，多和身边dl请教代码思路、设计技巧等等十分重要。还有意外的一点是面向对象的思维有了一点点进步（一点点）

最后，通过廖雪峰的教程等等，我认识到这一单元只是多线程的冰山一角，而具体在实现中我甚至一个lock锁都没使用过，全都使用了synchronized，更遑论各种各样类别的锁。长路漫漫，总是越学习便越感到自己的渺小。