一、第二单元电梯作业设计思路

初次接触多线程的问题，对于作业的设计思路一开始比较迷茫，后来通过阅读上机实验的代码，觉得采用“生产者-消费者”的模式比较合适，遂模仿实验的思路设计了InputHandler、Schedule、RequestQueue来进行输入数据的实时处理和调度，事实证明这一架构模式的设计是比较安全和方便扩展的，因为我三次作业都没有进行重构，仅仅在原有代码的基础上更改和增加代码。

1.调度器的设计：

三次作业均采用“生产者-消费者”的模式进行调度。为实现多线程的调度而设计了InputHandler类、Schedule类、RequestQueue类、Building类、Circle类。Building类、Circle类分别封装了同一个楼层(楼座)的RequestQueue和Arraylist<Elevator> elevators。

RequestQueue类的实例化情况： ​ 1个waitQueue对象作为InputHandler、Schedule、所有Elevator可以共享的对象。 ​ 5个buildingQueue对象作为Schedule和每一个Building内的电梯可以共享的对象。 ​ 10个对象circleQueue作为Schedule和每一个Circle内的电梯可以共享的对象。

调度器的具体层次结构如下图：

这样设计的好处是：通过一个Schedule作为中间层，将input的request进行了分类，分别分配给了各个层（各个楼）的requestQueue。之后电梯运行时只要读取自己所在楼层（楼座）的requestQueue的内容即可，不需要对其中的request进行判断，这一判断已经在Schedule层前置进行了。使得我们的架构更加的清晰，减少了Elevator的代码量和复杂度，使Elevator能专注于实现自身的运载乘客的功能。

2.电梯运行策略设计

三次作业均采用的LOOK调度算法。写了Strategy接口，分别实现成了HorizontalLOOK和VerticalLOOK两个策略类，电梯Elevator不分竖向电梯、横向电梯，而是可以选择搭载竖向、横向的LOOK算法。这样设计可以方便后续实现更多的调度算法、或者切换调度算法。下面以单个竖向电梯LOOK算法为例：

（1）策略类与Elevator的交互：

策略类只需要对Elevator提供3个信息：curDirection（运行方向）、ifOpen（是否开关门）、Arraylist<person> personToPick（在当前位置需要运载的乘客名单）。curDirection取值有三种：1（向上），0（保持不动），-1（向下）。为此设计了3种方法：flushMoveDirection（刷新运行方向）、ifOpen（判断是否开关门）、pickUpList（获取personToPick）。

Elevator运行时与Strategy的交互如下图所示：

（2）LOOK策略的实现思路：

1.pickUpList：遍历requestQueue、如果有可以搭载的乘客（乘客前往方向与电梯运行方向保持一致），就把他加入personToPick中。 ​ 2.ifOpen：如果有可以搭载的乘客（乘客前往方向与电梯运行方向保持一致），或者有到达目的地的乘客，那就返回true，否则返回false。 ​ 3.flushMoveDirection：如果电梯内有乘客，则保持当前运行方向；如果没有乘客，先检查requestQueue中是否有request。如果没有，则Elevator在requestQueue中进行wait()，Elevator线程让出CPU资源，等待notifyAll；如果有，那么分为两种情况：1.curDirection！=0，就检测当前电梯运行方向上是否还有request，如果有则保持前进方向，否则反向。2.curDirection==0，就选择前往离电梯最近的request的方向（或者电梯所在楼层有request时，选择当前request的方向）作为方向。

（3）多电梯自由竞争策略：

采用自由竞争的竞争策略。即所有同层（同楼）的电梯都共享一个requestQueue队列（层次结构可以参见上面的图），都可以访问和获取requestQueue中的请求，进行自由竞争，这样可能会在电梯运行时占用较多的输出资源，但是在性能上并不差，而且易于实现（懒）。 ​ 其他多电梯调度策略，比如有基准策略里使用的平均分配（请求编号mod（电梯数）），还有模拟策略。模拟策略就是先对运行时间进行模拟，找到一个最优的策略。但是如果采用模拟法的话，对于一个静态的请求集合可能能找出最优的策略，但是对于一个动态增加的请求队列来说，可能也只是局部最优解，无法找到全局最优解，因为要全局最优必须能“预知未来”，但是未来不可能预知。所以一个绝对最优的策略是不存在的，采用自由竞争策略也不失为一个好的办法。

（4）中转的策略：

第三次作业选择采用静态拆分的方法，在request刚进入InputHandler的时候进行拆分，所有的request必然能在3次运载内完成。所以可以按照运载次数将request分为3类：1次运载到达目的地，2次运载到达目的地，3次运载到达目的地。并计算出相应的midfloor。

在request类的基础之上，设计了MyRequest类，增加了workTime和workTurn属性，分别记录总需要的运载次数和当前运载的次数。当workTurn==workTime的时候，才会判定request执行完毕。而且MyRequest对外隐藏了midFloor，只是对外显示的fromFloor和toFloor会随着workTurn的改变而改变。

对于所有request的完成，参考了experiment4-2多线程设计的流水线模式，设计了一个信号量RequestCount用来标识request的完成，RequestCount采用了单例模式，是一个共享对象，由Main、Input Handler、Elevator共享。获得新的request时，counter++；完成一个reuest时counter--。当所有的request都完成的时候，总的线程才会结束。

RequestCounter与线程的交互如下图：

3.线程安全——同步块与锁的设计：

三次作业中，采用前文所述的调度设计，可以得出我们的共享对象的类仅有RequestQueue、RequestCounter这两类，只需要对RequestQueue类、RequestCounter类进行加锁即可。

RequestQueue类主要有两个属性：boolean endSign（标识request的输入是否结束）、ArrayList<Person> requests（请求队列） 。这两个属性的状态均会被修改和查看。RequestCounter仅有int conter这一个属性，会被修改和查看。

根据课上所学共享对象的安全：对于共享对象中的属性，如果仅查看而不修改，可以由多个线程同时进行查看；如果要修改，只能有一个线程进行修改，且修改过程中不能有其他线程查看。也就是仅有以下两种情况正确：（1）n个线程查看，0个线程修改。（2）0个线程查看，1个线程修改。所以只需要将所有涉及到这三个属性的查看和修改的方法加上synchronized即可，而且在属性状态改变时使用notifyAll()唤醒其他等待的线程，实现wait-notify机制。

至于死锁问题，由于只有两个共享对象类，而且在俩共享对象中也没有出现获取锁去访问其他共享对象的地方。所以不会出现线程1访问A后访问B，线程2访问B后访问A这种互相等待对方释放锁的死锁现象。

二、整体架构展示和迭代开发过程：

1.第一次作业：

架构设计要点

• 采用了“生产者-消费者”模式。Schedule类、InputHandler类处理请求，属于生产者。RequestQueue作为流水线。Elevator是消费者。

• 电梯使用LOOK算法来进行调度。调度逻辑见上。

• 重新设计了自己的Request类，方便在Request里添加一些内容。

• 设计了Building类来容纳同一个楼座的多部电梯，为下一次迭代开发做准备。

• 封装了OutputHandler，保证输出线程安全。

UML类图

2.第一次作业：

架构设计要点

• 增加了Strategy接口，可以实现为HorizontalLOOK和VerticalLOOK两个类，分别指导纵向和横向电梯的运行。原有的LOOKStrategy重命名为VerticalLOOK，HorizontalLOOK仅需要在VerticalLOOK的基础上修改实现即可。

• 增加了Circle类，实现和Building类类似，在addOneElevator的实现上有所不同，而且没有初始化电梯。

• 电梯增加一个runModel属性，用来标识电梯是横向运行还是纵向运行，用来采取不同的策略和运行方式。

• InputHandler可以调用Building、Circle增加电梯的方法。

• Schedule可以将request分配给circleQueue。

UML类图

3.第三次作业：

架构设计要点

• 增加了RequstCounter类，作为控制信号量，使用单例模式，可由InputHandler调用accept()方法增加counter，可由Elevator调用release()方法减少counter，可由Main检查是否完成所有request。

• 在InputHandler里进行静态拆分，使用private方法analyseRequest()将一个request拆分成几部分。

• 在Request中增加了workTurn、workTime、midFloor属性对Request分步骤完成的过程进行描述。

• 在Elevator中新增了canStay属性表示可以停靠的楼层，新增了moveTime属性可以定制移动时间，新增了waitQueue用来连接总的waitQueue可以在请求未完成时把它扔回到新请求队列中。

• 在HorizontalLOOK策略类中增加了对canStay的判断。

UML类图

4.UML协作图：

三、采用的设计模式

主要采用了单例模式和生产者消费者模式，模仿了一点exp4-2的工人模式。

单例模式是用于第三次作业的RequestCounter计数信号量，可以标识需要多次运载的请求的完成。

生产者消费者模式从第一次作业用到了第三次作业，就是设计了InputHandler、Schedule、waitQueue来进行请求的调度。

四、BUG分析

第一次作业：

1个bug，这个bug比较严重，因为我在搭载乘客时没有判断是否超过了电梯的运载量，导致电梯超载，因此在强测中挂掉了很多个点。我在Strategy中增加了对运载乘客数量的判断予以解决。

第二次作业：

1个bug，出现在横向调度算法中，因为我设置的是没有乘客时总是寻找最近的去运载，而忽略了在楼层可以接送的乘客的需求，导致在特殊数据点处横向电梯一直运行而不接客，造成RTLE。为了解决问题，我小修改了一下横向调度策略。

第三次作业：

2个bug，这两个bug都是比较隐蔽的bug。

其一，由于我在横向电梯的策略里面一开始思路是这样写的：如果等待队列没有人，就会wait，没有可以接到的人，那么就会保持在原地不动，但是不会wait，因此可能会轮询。因此，如果某层的等待队列中有人，但是某横向电梯又接不到人（不能在那开关门），就会造成电梯什么也不做但是也不wait，出现轮询现象，因此造成了bug！ 这里改动比较大，主要在RequestQueue里在电梯进行获取等待队列时，如果等待队列不为空，需要加一个对是否等待队列里有可以运载的人的判断。

其二，由于没有考虑到一种情况：一个请求只在同一楼层中转移，在该楼层没有可以运载它的横向电梯，这时需要中转。但是我在写程序时，默认了以为所有的同楼层请求都可以不用中转而直接在该楼层运载。因此没有考虑到这种情况。因此，造成了RTLE错误。修改就是在InputHandler里进行静态拆分时，及时是同一层的运载请求也可以拆成3个阶段。

五、反思总结

1.好好听课可以事半功倍

初次接触多线程都是云里雾里的，实际上每次理论课都介绍了很多关于多线程的内容，认真听讲真的受益匪浅，包括轮询、死锁一些常见的多线程错误都有介绍，也从理论课上学到了关于多线程设计的基本思路，要抓住共享对象，给共享对象加锁保证线程安全，临界域要合适，不能过大或者过小。

2.实验的代码要仔细研读

每次实验的代码都是一个小的多线程模式的模板，比如exp3的生产者-消费者模式，exp4-1的主仆模式，exp4-2的工人模式。都很经典而且也比较短小精悍。所以可以从实验代码中学到很多多线程的知识。

3.一定要先设计、分析再写代码

第一次作业之前，头脑中要先设计好多线程的基本框架、想好要设计哪些类、哪些类是共享的、哪些是线程、各自负责什么功能。一个好的设计可以减少以后的重构，方便进行扩展。

4.要学会自测，构造数据

每次作业其实一些明显的bug是可以通过自己构造简单的测试数据来修掉的。起码每次再数据范围内的数据边界上的数据都要测试一遍，保证基本的功能不会出错，至于一些比较不明显的bug，可以通过随机生成数据来测试，当然数据的生成逻辑也要尽量覆盖到各种数据边界，不能只测一个地方。