OO第二单元作业小结

前言

转眼已是第九周，第二单元的电梯系列作业已经结束，终于体验了一番多线程电梯之旅。

第一次作业是单电梯的傻瓜调度，虽然是第一次写多线程，但在课程ppt的指引下，写起来还是非常容易；第二次作业是单电梯的捎带调度，并加入了负层电梯，写起来也相对容易，不过在写捎带策略时容易出很多bug；第三次作业是多电梯协作调度，不同电梯有不同的停靠楼层、容量等，看起来好像比较难，但其实只要将请求拆分，并且有第二次作业的代码基础，需要大改的也基本上只有调度器而已。

相比于第一单元借助延时才完成作业，这一单元的作业我都及时通过了中弱测。

一、三次作业的设计策略

1、第一次作业

第一次作业的电梯没有那么复杂，采用的是ppt中的生产者消费者模式，设计有一个电梯类作为电梯线程，一个请求类作为输入线程，一个队列类用来实现电梯与输入的交互，还有一个主类。

队列只存一个请求，电梯空闲时从队列中get一个请求执行，若队列中没有请求电梯会wait，直至有新请求来时notify；若队列中已有一条待执行请求，新请求会wait，直至队列中那条请求被电梯获取时notify。

至于电梯线程，只是简单地先sleep从电梯当前层到请求出发层的时间，然后开门，进人，再sleep开关门时间，关门，然后sleep从出发层到目标层时间，开门，出人，sleep开关门时间，关门。非常简单的调度。

2、第二次作业

第二次作业由于要捎带，调度器（即请求队列）类改为用arraylist存储请求。

每当有新请求，直接存入调度器，并且notifyall一下，电梯空闲时获取队列第一条请求，队列为空时wait。

重点是电梯线程。我将电梯的运行分为从当前楼层到主请求出发楼层和从出发楼层到目标楼层两步。在从当前楼层到出发楼层这一步，只捎带出发楼层和目标楼层在这一过程之间的请求，也就是捎带请求的目标楼层不能超过这一步的目标楼层；在第二步从主请求出发楼层到主请求目标楼层时，就会将所有经过楼层并且方向与主请求方向相同的请求捎带，即捎带请求的目标楼层可以超过主请求目标楼层，实现更多的捎带。

至于捎带原则，我会在电梯到达每一层时从请求队列中寻找从当前楼层出发并且符合其他条件的请求。在电梯到达每一层时，从请求队列里寻找，然后根据找到捎带请求和目前电梯里的请求的上下楼情况判断是否要在当前层开门，若要开门，需要在sleep开关门的时间后再从请求队列里寻找一次捎带请求（因为存在电梯开关门之间有新的可以捎带的请求到来，这样可以捎带更多请求）。

3、第三次作业

第三次作业有三部电梯，调度器中设置了三个请求队列。每当有新请求，若请求有电梯能直达，就存入相应电梯队列；若不能直达，则拆分为两步，分别存入两部电梯的请求队列。拆分原则比较简单，也比较机械，比如拆分后的某一步若有两部电梯都能完成，只是固定地把他分配给其中的一部（如果有c电梯的话优先分配给c电梯，因为c电梯能够直接完成的请求不多）。

这一次我的调度策略是请求优先，就是如果一条请求需要两部电梯完成，那么两部电梯要同时出发去相应楼层完成这一请求。比如一条请求要从4到20层，我会把请求拆分成让b把他先送到15层，再让a把他送到20层，这时，在b送他时，a电梯也会出发去15层等他到达15层，再直接把他送到20层。但考虑到另一种情况，如果有4到20层的请求，不久后来了一个a电梯能直达完成的请求（假设不能捎带），那么a电梯还是会到15层等待第一条请求的到来，而不会完成第二条指令，直至把第一条请求送到20层，再去接第二条请求。这样可能会增加电梯的运行时间。总的来说，我的调度策略在请求较少时性能比较好，请求多的话反而会降低性能。（强测大部分点还是指令很多的情况，所以我相当于做了一次负优化）

至于捎带策略，就是在每部电梯运行时，捎带上出发楼层和目标楼层在当前运行区间之内，并且方向相同的请求。其他捎带细节与第二次作业相同。

二、三次作业架构与代码分析

1、第一次作业

 

第一次作业的代码非常简单，比较蠢的是我在第一次作业是没有注意到给的输入接口中的方法，而是用split方法手动拆分请求，多写了不少代码。

2、第二次作业

 

第二次作业我写的最复杂的是寻找可捎带请求的方法，每次捎带时都要遍历整个请求队列寻找，而且由于在电梯从当前楼层到主请求出发楼层和从主请求出发楼层到主请求目标楼层两个过程的捎带条件不同，每次寻找还要判断是哪一种捎带。其次是上下行的电梯调度方法，一个从电梯出发楼层到目标楼层的for循环，每一层都要判断是否开门，是否要跳过这一层（0层和第一步调度的最后一层等），是否要更改目标楼层等。

3、第三次作业

 

第三次作业最复杂的是调度器的拆分方法，用if-else语句实现所有情况的请求拆分。其次寻找捎带请求方法和调度方法与第二次作业问题相同。

三、bug分析

第一次作业强测和互测没有bug。

第二次作业原地爆炸。强测直接四十多分，互测被刀了27刀。这些都源于两处bug。第一处是，在电梯从当前楼层到请求出发楼层时，主请求还未进入电梯，我在每一层判断是否要开门时，考虑到了经过主请求目标楼层而主请求还未进入电梯的情况，而在输出上下电梯情况时没有考虑到。也就是说如果在主请求目标楼层有其它请求要上下，电梯会开门，而且会输出主请求out的信息，即人未进入电梯，我却将他放出电梯。第二处是，我在寻找捎带请求时，判断电梯当前运行方向，是让电梯当前楼层与当前目标楼层做比较，若当前楼层小于目标楼层，就是在上行，否则下行。也就是说，如果电梯在上行时运行到了目标楼层，即当前楼层与目标楼层相等，我会判他为下行，于是寻找向下走的可捎带请求，而将一些不该捎带进来的请求捎带进来，会出现重复进电梯的情况。

第三次作业吸取了第二次作业的教训，最后强测和互测都没有bug点。

四、发现别人程序bug的策略

第一次作业比较简单，最终也是100分，没有找别人的bug。

第二三次作业都是自己构造一些易错的输入，主要针对电梯运行边界的捎带情况，电梯容量等方面设计输入。

这样手动构造虽然效率不高，但能够考虑到每一个容易出错的点。在上周的研讨课上有同学讲了用java写判断输出是否正确的方法，能够随机生成输入，并判断输出是否符合各项要求的方法，这样即使不会写对拍器也可以进行自动测试。

五、心得体会

第一次接触多线程，从最初的忧虑忌惮，到后来逐渐得心应手，整个探索的过程还是比较充实的。写第一次作业时，我反复看课程ppt看了几乎一整天才大体搞懂wait()和notifyall()的用法，后来也对这些用法和线程安全等问题慢慢熟悉，逐渐掌握了多线程的写法。

除了课程的心得，从这一单元的作业中我还要吸取一个很重要的教训——对于自己代码的测试。写完第二次作业，中弱测全部通过后，我就很自信地没有测试自己的代码，其实中弱测是很弱的，即便全部通过，代码也可能存在很多问题，果然强测直接开花。另外写代码时其实也要注意，尽量减少由于粗心写出的bug。