【作业2.0】OO第二单元作业总结

OO第二单元所有作业已经完成，这一单元作业的主题是多线程编程。我将在此对作业内容进行分析和反思。

一、多线程协同和同步控制

三次作业中，我的设计基本相同，均采用了“主线程+调度线程+输入线程+若干电梯线程”的设计，具体内容如下：

1. 第一次作业

第一次作业只有一部电梯，我创建了Elevator（电梯类）、Dispatcher（调度器类）、MainClass（主类）完成相关工作，其中：

MainClass类只负责Dispatcher类的创建和线程启动。
Dispatcher类的功能如下：
1. 创建并启动电梯进程。
2. 创建输入对象，等待输入；在输入结束时结束自身进程。
3. 在收到请求时，将请求发送给电梯。
Elevator类的功能如下：
1. 主动将请求从等待队列加入电梯
2. 将请求送至目标楼层

如上图所示，在Elevator中，floor表示楼层，doorOpen表示电梯门开关状态，direction表示电梯运行方向，其中1-->上行，-1-->下行，0-->停止
（这样可以在楼层改变时直接使用floor+=direction，简化运算逻辑）。

使用floorRequest和cabinRequest两个队列储存请求，其中floorRequest是一个与Dispatcher类的共享变量，表示所有楼层在等待电梯的请求。而cabinRequest是已经进入电梯的请求。floorRequest是典型的共享变量，Dispatcher可能对其进行写操作，Elevator可能进行读或写操作，需要加锁进行保护。

我的电梯调度使用了LOOK算法。当floorRequest队列有请求时，选择第一个请求的出发楼层方向作为direction。电梯运行到某一楼层时，首先检查floorRequest中是否有从当前楼层出发的请求，如果有，将其纳入自己的cabinRequest（请求进入电梯）；检查cabinRequest中是否有在当前楼层到达的请求，如果有，则将其移出队列（请求完成），根据以上进出电梯的情况决定是否在当前楼层开门。如果cabinRequest中没有当前方向之后楼层达到的请求，且floorRequest中没有当前方向之后楼层出发的请求，则电梯停止（direction=0），进行下一步的方向判断。

电梯将上升或下降一层作为一次主循环。若当前没有请求时一直循环（轮询），CPU时间一定会超标，出现CTLE错误。因此，我在电梯完成当前楼层操作，前往下一层之后进行判断，如果cabinRequest和floorRequest两个队列均为空，则进入wait状态，等待输入。而这里出现了一个小bug，当加入新的请求之后，或线程结束时，很容易出现Elevator一直陷入阻塞的情况，经过分析之后我找到了原因。

在最初的设计中，Elevator线程被唤醒后，立即开始检查队列中是否有请求，这时Elevator可能尚未检出新增请求，就再次陷入wait。我在wait结束后添加了1ms的等待时间，等待Dispatcher完全放入请求之后再进行下一次遍历，就解决了这一问题。

如上图所示，在Dispatcher类中，有floorRequest等待队列（为迭代保留，所有电梯共享），elevators电梯队列（有多少部电梯，第一次作业只有一部），inputOver输入结束提示列表（其实使用一个自定义类当做输入结束的锁即可，在此使用容器是为了后续作业中可能存在多种输入做准备，但后续迭代证明这样的设计其实没有作用）。Dispatcher线程启动后首先启动其拥有的电梯线程，之后负责将输入的请求加入floorRequest，在输入结束之后，向inputOver插入true元素，表示输入完毕。

第一次作业中的Dispatcher类发挥的实际作用较少，我在考虑迭代设计的时候想令电梯自行获取请求。这样有一点不理想，因为Dispatcher线程和Elevator线程相比，承担的任务过少，没有做到功能的均衡分配。

另外，终止线程也花费了我相当长的时间。在最初的设计中，我令Dispatcher在结束输入时notifyAll所有电梯，但这样的设计存在一个很大的问题：输入结束时电梯进程有可能处于运行状态或wait状态，而且这一状态信息无法在Dispatcher线程中直接获取，如果Elevator仍在运行中，Dispatcher就进行notifyAll，那么当Elevator处理完请求时，将再次陷入wait，无限地阻塞下去。为了解决这个问题，我采用了共享信号inputOver来解决。

当Elevator在处理完毕请求之后先进行判断，如果inputOver中没有true元素，说明输入尚未结束，进入wait状态，等待输入请求；而inputOver中存在true元素，则说明输入已经结束，这时如果处理完所有请求，电梯应当直接结束进程。

最后，本次作业存在一个重大问题是，我在run方法中放入了几乎全部的业务逻辑，这样的处理方式无论是在面向对象编程还是面向过程编程中都是不好的习惯，出现这样的错误的原因主要在于我对多线程编程没有足够的理解，对于run方法以外的非同步方法的处理没有把握。这些问题在第二、第三次作业中得到了较好的改善。

2. 第二次作业

第二次作业主要在三个方面进行扩展：

电梯数量增加至5部
电梯限载7人
电梯存在负数楼层

对于需求1，我在第一次作业时已经预料到，直接修改Dispatcher中的电梯数目即可。

对于需求2，其实只要控制电梯在满载时不再加入新的请求即可，但在我进行架构修改之后，需求2的处理方式发生了很大的改变，虽然产生了高效的结果，但是产生了我没有预料到的bug。

对于需求3，其实负数楼层本身没有问题，int类型本就支持负数，但应当注意到并不存在”0层“的说法，因此需要做特殊处理。最直观的解决方案就是遇到0层时，直接在当前方向继续上升或继续下降。但我改良后的需求2处理方式需要对楼层差进行预测，直接进行相减会引入0层的误差，如果引入更多的逻辑又会让方法有很多不必要的代码。因此，我采用了将-3_-1，115这些楼层与0~17的下标进行映射的方式，这样的处理的好处是，如果有其他特殊楼层需求的加入（如因避讳，跳过4和13层；医院等特殊场所存在“G”层；船用楼层反向定义，最高处为第1层，甲板为第8层）楼层和下标映射的方式可以解决各种需求，可扩展性更好。

另外，在电梯调度方面，我也做了一些修改，没有完全沿袭第一次作业中对后续迭代的预测。笔者发现，在第一次作业的“电梯自行获取请求”的方案下，多部电梯会出现“争夺乘客”的现象，这并非是出现了线程安全问题，而是共享floorRequest队列所带来的必然问题。这样的设计虽然不会破坏正确性，也不会给性能造成太大影响，但与现实中的电梯调度情景严重不符。现实生活中的电梯绝对不会存在按下按钮后，有多部空闲电梯同时响应（因为增加了不必要的功耗）。另外，这样的设计在电梯运行的初期会出现“电梯趋同”的问题，也就是多部电梯同时在靠近的几个楼层活动、有运动方向相同的趋势，也不利于请求的合理分派，因此这种设计是不优雅，缺乏工程素质的。笔者使用LOOK算法进行电梯调度，正是为了使设计的电梯在满足性能要求的基础上，尽量从真实场景出发解决问题，因为真实的、常用的电梯调度策略一定是经过了长期的检验之后的结果。因此我做出了如下更改：

我将floorRequest队列分开，每个电梯各有一个floorRequest队列，是等待该电梯的请求队列，同时Dispatcher增加一个waitRequest队列，是未进行分配的请求。Dispatcher线程负责将不同的请求根据各个电梯的运行情况进行分配。具体如何分配，是我这次作业算法的一个改进之处，但也同时造成了一些线程安全的bug，经过修改之后，这些bug可以完全被消除，并非算法本身的问题。从通过的样例分数来看，这样的调度性能还是很高的。

使用LOOK算法的电梯，主要遵循了“尽量不变向”的原则，结合“目的选层电梯”的固有优势，我们可以在请求进入电梯之前就对电梯在变向前各个时刻的载客人数进行预测，我使用了estimateNum数组保存电梯每趟行程各个楼层的人数预测，当预测人数超过7人，或当前请求运行方向和电梯方向相反，或电梯已错过请求的出发楼层，Dispatcher便不再向当前电梯的floorRequest加入请求，转而使用其他电梯；除此之外的请求，尽量纳入同一部电梯。这样的调度在请求较少时，使单部电梯尽量饱和，节省了电梯的功耗；而在请求较多时能够错开各个电梯，使其活跃在不同楼层。

但是这样的改变也造成了第二次作业的严重bug，由于我完全依赖estimateNum对电梯载荷进行限制，没有做人数的强制限制，当电梯在换向时加入新的请求对estimateNum做出的更改，会在换向之后被清空，这样就会带来超载的隐患。出现这个问题的本质原因，是电梯请求的加入和estimateNum的修改无法做到完全同步（并非线程同步问题），因为两个操作的先决条件不同，无法被放在一起执行。如果要解决这一bug，只要通过强制限制电梯人数的方法即可，在电梯满载时，Elevator线程阻止任何请求进入电梯。虽然这和最初的设计有所违背，但是具有很高的安全性。

这次作业的线程停止策略也做了相应的修改，为了获取各个电梯的运行状态，我将inputOver和电梯是否运行这些状态信息集中在了一个被共享的类中，名为MainLock（因为这个类实例作为共享变量，主要发挥了锁的作用）。输入完毕和电梯停止运行的信号都是通过这个类来传递的（如图）。但是在设计这个类的时候没有使用synchronized方法，而是让调用者保证MainLock的线程安全，这样做确实不合理，我反思这一点应当做相应的修改。

同时，这次作业的Elevator.run()方法我也做了相应的简化，只放置了顶层逻辑，把原来的电梯各个阶段分成了不同的方法。虽然这样做有些面向过程的感觉，但是层次更清晰了，况且我的调度算法下的电梯行为有明显的周期性、固定性，部分面向过程的处理未必不好（当然也有改进的空间）。

3. 第三次作业

这次作业在多线程操作上基本延续了第二单元的做法，只是Dispatcher方法多了动态加入和启动电梯的逻辑。具体的功能设计和性能设计将在第二部分重点讨论。

二、第三次作业的设计和可扩展性

1. 类的设计改进

第三次作业中，我做出了以下几个改变：

增加了InputPanel类，讲输入请求的任务和调度的任务分开；取消了MainLock类，将电梯线程的终止权全部交给Dispatcher。
Elevator改为抽象类，由ElevatorA、ElevatorB、ElevatorC三个子类分别继承，继承主要的作用是覆写速度、载荷、可用楼层等信息。
添加继承自PersonRequest类的CommuteRequest类，为了满足电梯的换乘请求，在输入处理阶段就将需要换乘的请求拆分为不需换乘的分请求。

2. 功能设计和性能设计的平衡

吸取第二次作业出现严重bug的教训，第三次作业我把正确性和调度的稳定性放在首位。从ABC三种电梯的可停靠楼层特性可以观察出，任意两个楼层之间最少只需要一次换乘，1层和15层是三种电梯均可停靠的楼层。基于这些特性，我对调度算法进行如下设计：

可直达的请求尽量进行直达的分配。如果有多种可达选择，优先级A>B>C（考虑到运行时间），如果有多部可用的电梯，则多部同种电梯之间采用第二次作业（修正后）的调度算法。
无法直达的请求拆分成两个直达请求，选择1层和15层之中使得总距离最短的楼层作为换乘楼层。
由于电梯资源在第三次作业中相对固定，电梯请求的分配以“来者不拒”为主，对超载的规避由电梯线程实现。

三次作业的强测分数如下：第一次：96.9113；第二次：58.8578；第三次：90.5247。其中，第一次和第三次通过了所有强测样例，第二次通过了12/20。通过的样例分数均大于97。

由此可以看出，性能：第二次>第一次>第三次，稳定性：第三次=第一次>>第二次。第三次作业采取的保守策略获得的效果是我比较满意的，我认为最大的改进空间在于换乘楼层的选择。如果要进行这样的改进，那么CommuteRequest类就需要获得各种电梯的信息，子请求的生成也将更加复杂。但这样做带来的安全隐患应当比第二次作业中，对于电梯超载的预测算法带来的隐患小得多。

3. 从设计原则的角度看第三次作业

SOLID之SRP（Single Responsibility Principle）

这个原则要求每个方法都只应当有一个明确的职责。我认为我在Dispatcher类、CommuteRequest类中做的比较好，各个方法的功能较为简单明确。但InputPanel类和Elevator类存在一些问题。

InputPanel类本身的功能就十分单一，只是获取相应的请求。问题主要在于run()方法中加入了全部的业务逻辑，这样的代码仍然看起来简明，但是没有使run方法体现出这个类的顶层逻辑特征。这是应当做出改进的地方。

SOLID之OCP（Open-Close Principle）

开闭原则是我在这两单元作业的迭代中都实现的不够理想之处，每次迭代都不得不对已有代码进行适当的修改和调整。我认为出现这种问题的主要原因并不是没能够对后续需求做出很好的预测，毕竟电梯数量增加、载荷限制这些都是在第一次作业中都预料到的，真正的问题在于自己在前面作业中存在架构上的偷懒行为，没有把各个步骤完全分离开，即SRP原则没能够完全实现，这才导致OCP原则的实现也举步维艰。今后的作业中应当注意这一点。

SOLID之LSP、ISP、DIP

这单元的作业没有复杂的继承和实现关系，在类的层面实现相对简单。因此Liskov原则和接口封装原则没有体现出来。各个模块各司其职，没有明显的从属关系，我也没有发现DIP原则能在本单元的作业中得到明显的体现。

其他设计原则

均衡原则：这是我在迭代过程中有改善的地方，Dispatcher类从第一次作业的只负责将输入加入队列，到第二次将等待请求分配给特定电梯，到第三次的处理适用于不同电梯的请求。
局部化原则：这个原则在Elevator的继承上有所体现，ElevatorA/B/C三个类只覆写了其特异性的速度、容量、可达楼层等信息，没有出现代码冗余。
显式表达原则：本单元作业在显示表达方面存在问题，例如direction对方向的定义使用了数字，而不是isGoingUp、isGoingDown等逻辑定义。这样简化了计算逻辑但确实不够明显，即使加了充分的注释。如果在多人合作的项目中，这种问题应当被规避。
懂我原则：我的变量命名很少偷懒，都遵循了使用英文全称+驼峰命名法，清晰易懂。

4. 可扩展性

第三次作业在OO课程中已经是迭代的终点了，但是保持可扩展性仍然是必须的。我的作业中做了以下可扩展的尝试：

Elevator进程的控制权完全交给Dispatcher，这样如果之后加入了停止电梯的请求，能够保证Dispatcher可以及时将电梯停下。
楼层与下标的映射关系floor2Index、index2Floor。这一点已经在第二次作业的多线程介绍部分讲过，这样可以处理各种复杂的楼层命名和分布。
引入CommuteRequest类，将PersonRequest请求拆分，使得处理更加复杂的请求（如往返类型的请求）成为可能。

三、基于度量分析程序结构

1. 类属性个数、方法个数、类总代码规模

第一次作业

第二次作业

第三次作业

可以看出，从第一次作业到第三次作业，各个类的属性、方法个数逐渐变得平衡，但还是存在Elevator、Dispatcher方法庞大，InputPanel、MainClass方法过小的问题，这个问题如何改进是值得探讨的，我认为应当在更全面的需求出现时，再考虑向MainClass中添加新的逻辑，而InputPanel的迭代空间也很大。

2. 每个方法规模、每个方法的控制、分支数目

第一次作业

第二次作业

第三次作业

在第一次作业中，可以明显地看出，Elevator.run方法过于庞大，达到了46行之多，远超其他方法。而在第二次作业中，这一问题得到改善，最长方法行数降至26行，各方法行数也变得平均。第三次作业中的checkRequest方法规模略大，经查看后发现，这一方法主要是因为电梯的不同类使用了switch结构进行分类，导致了很长的代码量都没有有效利用。如果电梯种类继续增加，可以考虑为不同的电梯配置不同的checkRequest方法。