OO第二单元——夺命电梯

一、需求分析和设计策略

第一次作业——多线程无限容量单电梯调度

• 输入：不定时投放人的需求
• 输出：电梯的运行日志和人的进出日志

由于本单元有专门的输入输出接口，因此这里就不对输入输出格式作分析了。

本次是单电梯的调度，不考虑电梯容量问题，这样调度就变得十分简单，作为多线程入门级题目十分合适。

性能与电梯运行时间直接挂钩。

整体结构

我本次采用的结构如下。

圆角框表示进程：Input，Controller，Engine

方框表示共享变量：RequestMap，State

• Input：从输入接口不断取需求放到RequestMap
• Controller：分别从RequestMap和State中获取当前等待队列和电梯的状态，然后计算出下一个电梯的动作；如果电梯门开着，将RequestMap中要进电梯的乘客取出放到State中，并将State中要出电梯的乘客删除。
• Engine：维护电梯的当前状态，根据Controller计算的结果维护当前状态。

这样的结构实质上就是“生产者-消费者”模式。输入是生产者，RequestMap是托盘，电梯是消费者。电梯内部分成两部分，控制器和发动机。它们通过一个共享对象State进行交互。这样设计的好处就是将控制和运行分离，运行就变得十分简单，调度也可以在运行延时中进行，节省时间，后续如果想改调度的话也比较简单，只需要改控制器的某个函数就可以了。

调度与性能优化

关于调度算法，我采用了Look算法。另外还有个小小的优化，进人的时候不需要判断要去的方向是否正确，反正没有容量限制。效果来看也还不错。

RequestMap里面对需求的管理采用了楼层队列的方法，每个楼层对应一个队列，这样不需要遍历所有需求就可以获得所有要进电梯的人了。

曾经想到过一种优化方法~~（sstf选手请忽视）~~，就是在输入结束之后重新确定一个电梯运行策略。因为其实本次作业性能很大程度上与输入结束之后电梯的初始状态和调度算法有很大关系。如果你的电梯正在往上走，走到2楼，输入结束，这时候1楼有人要上到10楼，但是如果是Look的话就不会回头去接了。这样可能电梯还得再跑一趟，多浪费时间啊。所以如果重新制定一个静态策略，当需求不再增加的时候执行该策略，可能能有意外的效果。当然最终我没做

如何结束？

当输入结束之后，会通过RequestMap传递一个结束标志，Controller接收到结束标志之后，会检查还有没有人在等待队列或者电梯里，如果没人，也会向State传递另一个结束标志，来告知Engine结束。通过这种流水线式的告知就可以让所有线程均结束。

第二次作业——多线程有限容量单类型多电梯调度

• 输入：电梯数量，不定时投放人的需求
• 输出：电梯的运行日志和人的进出日志

这次变成多部电梯，而且电梯有了容量限制，调度和架构上也要有所调整。除此之外楼层也有所变化，出现了负层，不过这个改动对架构影响不大。性能还是跟电梯运行时间直接挂钩。

整体结构

我在原来的结构上进行扩充，变成了如下的结构。

这一次的结构相比上一次的有两个部分的变化。一个是加入了RequestQueue和Dispatch，作第一级缓冲和分派，RequestMap改成WaitingMap；第二部分变化时将State拆分为CurrentState和NextState，这样就可以脱耦合，拆分成两个“生产者-消费者”。

调度和性能优化

电梯内部的调度依然是Look算法，但是由于容量有限制，这次进人只进相同方向的，于是如何处理调头时候的进人就成为让我头痛的一个难题。

多电梯处理需求采用分派式，根据当前电梯内的人数，电梯所在楼层，电梯的方向，电梯等待队列的人数，新需求的方向和出发地点等因素设计惩罚函数，根据函数返回值大小决定分派策略。当时想这个惩罚函数想到头都要炸了

RequestQueue采用优先队列管理需求，优先处理路程短的乘客。因为路程短占用电梯空间的时间就越短，也越容易成为捎带对象。

两级等待队列的好处是可以先不要急着将某个需求进行分派，当前所有电梯都积压大堆任务的时候可以暂缓分派。（我也不知道这样做是不是确定有好处）

如何结束？

还是采用流水线的方式，操作与第一次作业类似。这次可能会有一些电梯先结束，有一些电梯后结束。

第三次作业——多线程有限容量多类型多电梯调度

• 输入：不定时投放人的需求和电梯的需求
• 输出：电梯的运行日志和人的进出日志

这次电梯分化出不同的类型，每种电梯容量，停靠楼层，移动速度均不相同。由此还衍生出了换乘问题。

电梯的数量还会动态变化，这给换乘策略的制定带来了更大的挑战。

性能评价指标也发生了变化，加入了乘客总等待时间，这意味着我们需要把优化重心更多地放到乘客的体验上。

整体结构

上一次作业性能虽然也还行，但是跟其他人的比还是有点差距。而且这一次分派策略也更加难以制定，索性放弃了分派和二级等待队列，所有电梯直接从需求队列取需求。

这样的话简化了结构，降低了开发的难度。

调度和性能优化

这样的结构对应的多电梯协同方式为自由竞争，只要能够接当前乘客的单，电梯都会抢着去接，谁先接到算谁的。这样的话在增加电梯的时候，调度也不会受到太大影响。

单部电梯的策略也改成了SSTF算法，应对像A类型电梯那种两部分相隔很远的情况。如果采用Look算法，可能出现电梯舍近求远的情况，显然对性能影响很大。每部电梯上人也采取能上则上的原则，不考虑方向。这里也有一个小小的trick：每次电梯打开的时候，电梯内的人全部都要下，要继续坐电梯只能重新排队上梯，而每个楼层的队列是优先队列，路程短的乘客排在前面，这样有可能能够用路程短的换出路程长的人。可以做到优先处理路程短的人。

换乘策略由人根据起始楼层和目的楼层来决定，因此是固定策略。根据打表分析，选出了三个固定换乘点：1,5,15。按照以下策略确定换乘策略。

• 由-3层到2~14层的，或者由-2,-1,2层到3层的，或者相反的，均经由1层换乘。
• 由3层到4~14层之间的偶数层，或者相反的，均经由5层换乘。
• 由2~14层到16~20层的，或者相反的，均经由15层换乘。
• 其余均可直达

最后强测几近满分，也说明了这种策略的可行性。不过本地测试的时候发现这个算法性能波动较大，对于一部分数据处理的性能反而比较差，所以确实也有点赌徒的亚子。

如何结束？

这次作业判断结束跟前一次作业有所不同，由于我并不是将一个人“分裂”成多个需求，如果允许电梯先后结束，则有可能会有人只能到达换乘点而无法到达最终目的地。所以我计划做到所有电梯同时结束。我在RequestMap设置了一个记录当前活跃的电梯数变量，当所有电梯都处于等待状态并且输入已经结束，就会设置结束标志。

二、架构设计的可扩展性分析

• 单一责任原则

  这次我的每一个类基本都做到了单一责任。不过有一个地方应该还可以再完善，就是把RequestMap中的判断结束的相关方法和变量单拎出来做一个类，这样RequestMap就可以专注于维护等待队列。

• 开放封闭原则

  这部分感觉自己做得不是很好。作业之间的迭代我还是通过改动原来的类来完成的，而不是继承。不过当前的架构还是可以通过继承和组合的方式来进行扩展的，最后一次作业的架构可扩展性也比前两次要好。

• 里氏替换原则

  因为这次没有很好的做到OCP，所以基本没有任何继承。

• 接口分离原则

  这次只是定义了一个接口，就是Handler，为了构造控制电梯运行的工具类。所以基本算是做到了接口分离原则。

• 依赖倒置原则

  这个原则我觉得自己也不是做得十分好，可能这也是导致我需要多次重构的原因。只有Handler接口是比较符合的。另外，我觉得Controller也可以做成接口，这样就可以很方便地更换策略了。

三、程序分析

这里就只分析最后一次的。

• 类图

图中被红框框住的部分就是电梯的内部，其中电梯与外界的交互只有Controller和RequestMap的交互，说明电梯还是被封装得比较好的。不过也暴露出了电梯内部耦合较高的特点。

• 方法复杂度

  这里仅仅截取了代码行数超过10的方法。（具体每一列的含义请参考我的上一个单元的博客）

  Method	ev(G)	iv(G)	LOC	v(G)
  request.Storey.getInQueue(int,Set)	1	7	34	7
  thread.InputThread.run()	3	6	25	6
  elevator.Controller.peopleOut(int)	1	4	24	4
  elevator.Controller.sstf(int)	3	6	24	9
  request.RequestMap.waitForInput(Set)	2	5	19	7
  elevator.Controller.control()	1	5	16	5
  elevator.NextState.setHandler(EnsHandler)	1	3	13	3
  request.Storey.hasRequest(Set)	5	3	13	5
  elevator.NextState.getHandler()	1	3	12	4
  elevator.handler.CloseHandler.change(CurrentState,String,int)	1	3	12	3
  request.RequestMap.RequestMap()	1	3	12	3
  elevator.Controller.Controller(RequestMap,CurrentState, NextState,Set,int,String)	1	1	11	1
  elevator.Controller.peopleIn(int)	2	2	11	3
  elevator.Controller.run()	3	3	11	3
  elevator.CurrentState.getCurrentState()	1	3	11	3
  elevator.CurrentState.up()	1	1	11	4
  elevator.handler.OpenHandler.change(CurrentState,String,int)	1	2	11	2
  factory.ElevatorFactory.buildElevator(String,String,RequestMap)	4	2	11	4
  request.Person.initTrans()	1	3	11	4

  这次相比前一个单元的作业，分支少了很多，也只有一个类方法的代码行数超过了30，不过确实有一些重复的代码，因为之前的作业用的是look算法，所以乘客要分成上行和下行，每个楼层有上行队列和下行队列。换了算法之后，上行队列跟下行队列的操作几乎没有区别了，所以很多方法都需要做两个一样的处理。

• 类复杂度

  Class	CSA	CSO	LOC	OCavg	WMC
  elevator.Controller	10	23	133	2.7	27
  elevator.CurrentState	7	25	98	1.62	21
  request.RequestMap	7	22	77	1.6	16
  request.Person	4	26	65	1.31	17
  request.Storey	3	16	64	3.75	15
  elevator.NextState	3	16	39	1.5	6
  thread.InputThread	24	65	33	3	6
  elevator.Engine	4	15	19	1.5	3
  factory.ElevatorFactory	3	13	19	4	4
  elevator.Elevator	2	14	17	1	2
  elevator.handler.CloseHandler	0	14	14	2	2
  elevator.handler.OpenHandler	0	14	13	1	1
  elevator.handler.DownHandler	0	14	12	1	1
  elevator.handler.UpHandler	0	14	12	1	1
  main.Main	0	13	10	1	1
  elevator.handler.StayHandler	0	14	6	1	1

  从表中可以看到，Controller内部的成员变量偏多，行数也比较多，应该通过层次分割建立继承树的方式减轻Controller的负担，也能够实现依赖倒置原则。

三、程序中的bug

在第一次作业中，由于刚刚学习多线程，被很多同步问题绕晕了，比如怎么合理运用wait,notify来挂起线程，怎样避免死锁。最后在互测中还是被hack到神奇的RE。最后是边重构边误打误撞修复了。后来分析了一下，估计是我的电梯在等待需求的时候把wait挂错了地方导致了死锁：Controller在没有需求需要处理的时候应该把wait挂在RequestMap中，而不是State，这样在新需求来的时候，RequestMap才能告诉Controller。不过还是很好奇为什么不是rtle。

后面两次作业均没有被找到bug，我也是首次不需要进修复阶段。

四、测试与互测的收获

测试是必要的，自动化测试更是必要的。这次多亏有fdh大佬的评测机（我摸了没写评测机），在本地就找出来了不少的问题并且一一修复了。并且在三次A屋中均没有断刀，其中一次还有幸拿到全屋唯一血。

附上fdh大佬的评测机博客链接

本次测试用了自动化测试+特殊数据测试的方法。进行特殊数据测试的时候从各个方面观察程序的运行，来弥补自动化测试的缺漏。这里必须提到JProfile，帮我发现了我的代码和其他人代码的轮询问题。

第一次作业发现了一个ctle，在等待需求的时候出现轮询。不过其实全屋共有四个人有bug，由于时间有限没有看完所有人的代码，还是有点可惜。

第二次作业本来打算hack一个偷时间的人（在电梯启动的时候才初始化时间戳），没想到没hack中，却hack了另外一个人的rtle，估计是电梯没任务的时候一直wait，没人通知它要结束。

第三次作业抓到了一个超载的，这个超载的还莫名的出现了RE。还抓到一个死锁的，分析发现是因为两个对象分别拥有一部分的锁并相互等待对方的锁。

这一次评测机比第一单元的更加难写，因为要做专用的输入接口，将一定格式的数据转化为定时投放，还要用很多条规则判断输出的合法性，并且识别出rtle的情况。

五、心得体会

这两个单元的作业我感觉自己都很容易将问题想复杂了，最后才发现最简单的方法也可以取得很好的效果。两个单元都是最后一次作业做得最好，说明在这几次迭代当中，整个设计架构和代码质量都在不断地提高。这两个单元对我的面向对象思维有很大的引导作用。但是我还是对一些设计模式和SOLID的原则不太感冒。下一个单元注意一下吧，特别是DIP和OCP。

O的体验还是不错的:D