• 一、需求分析
  • 第一次作业：
  • 第二次作业：
  • 第三次作业：
• 二、方案实现
  • 第一次作业
  • 第二次作业
  • 第三次作业
• 三、同步块设置和锁的选择
• 四、调度器设计分析
  • 第一次作业
  • 第二次作业
  • 第三次作业
• 五、bug分析
• 六、心得体会

一、需求分析

第一次作业：

模拟一个多线程实时电梯系统，有A-E五个楼座，每个楼座一部电梯，乘客输入电梯请求，电梯需要在规定时间内按照规则完成这些请求。

第二次作业：

引入横向电梯和纵向电梯的分类，从而有电梯请求的不同，新增增加电梯请求。

第三次作业：

电梯属性可配置，电梯到达位置可配置，电梯请求的路径不唯一，需自行规划，实现换乘。

第一次作业主要是弄清电梯运行过程，进行整个系统结构的构建，控制流程基本上是请求模拟器通过控制台获得用户请求、调度器调度电梯响应请求、电梯根据调度器分配的请求提供服务。由于输入时间不定并且有多部电梯运行，从而引出了多线程的需求。第二次作业延续第五次作业，引入了多种电梯，调度稍有不同。第三次作业要求电梯可配置，乘客的请求需要路径规划，实现换乘。后两次作业整体框架变化不大，主要是调度器和电梯之间的交互更为的复杂，需要更加精细的分层设计。

二、方案实现

第一次作业

采用生产者和消费者模式，借鉴了第一次实验的整体架构，采用类似于ALS的捎带策略。

RequestTable类是借鉴实验代码设计的线程安全类，InputHandler、Schedule、Elevator都是通过共享RequestTable来实现通信的。InputHandler和Schedule之间共享inputQueue，InputHandler不断把输入请求放到inputQueue，Schedule不断取出inputQueue中的请求分配给Elevator的requestTable，我采用的设计是一个调度器给所有电梯分配，所以Schedule管理的是requestTables这个容器，即一个生产者，多个消费者。

电梯的运行逻辑是当电梯为空处于WAIT状态时，其从requestTable的等待队列中把第一个请求所在楼层作为目的地，捎带的策略是当电梯处于UP状态时，如果电梯请求的目的楼层大于当前楼层则捎带，处于DOWN状态时，则目的楼层小于当前楼层就捎带。每一层接送完乘客时，更新电梯的最终目的地，把当前电梯内乘客（即passengerTable里的乘客）的最远目的地作为电梯的最终目的地,当电梯内没有乘客并且到达目的地时，状态设置为WAIT。

电梯请求的分配在第一次作业中很简单，分配给相应楼座即可。

第二次作业

架构延续第五次作业，调度器的作用变得更加丰富了。这次作业中，我的输入线程并没有区分请求，而是直接把请求放进inputQueue让schedule来处理。因此我的调度器掌管分配电梯请求，还要识别新增电梯请求来启动电梯。当时这么设计的原因是期望管理纵向电梯和横向电梯等待子队列的容器只由一个线程更改，这样就不用担心线程安全问题，所以调度器管理着所有信息。由于有多种电梯，所有新建立电梯工厂类，为了方便调用方法，我直接把电梯工厂类的方法设为静态方法了。纵向电梯和横向电梯在很多方面都相似，所以让它们都继承电梯类来提高代码的复用性。

电梯运行逻辑上，纵向电梯没有改变，横向电梯的运行逻辑是当处于WAIT状态时，会选择等待队列中第一个请求作为目的地，选择最近的路径去接乘客，这样也就确定了方向。到达目的地后，如果电梯内无人并且有乘客要上来，则电梯会用第一个上来的人目的地来确定运行方向，运行方向确定后只要遇到有人要上电梯，满足容量的条件下，便会允许乘坐，直到所有乘客都送完后，电梯才进入WAIT状态，等待方向重新确定。

电梯请求分配需要区分纵向电梯请求和横向电梯请求，而且可能有多个纵向电梯或者横向电梯可以分配。我没有采用自由竞争策略，理论上自由竞争策略一般性能会好些，为了能够比较均匀的分配给每个电梯，我的策略是给每个电梯都配备一个子队列，电梯只负责自己子队列的请求，调度器会在可以分配的电梯中，选择子队列中等待人数最少的分配。

第三次作业

第三次作业相较于第二次，主要是把启动电梯功能放在了InputHandler里，由InputHandler来区分电梯请求和新增电梯请求，调度器只负责分配乘客到不同的电梯子队列（每个电梯负责自己的子队列里的请求）。由于电梯请求的路径需要自行规划，为了更好的复用之前的代码，重新建立一个passenger类，其内部path属性是管理personRequest的容器，代表着初始那个personRequest的路径规划，path里的personRequest要么building相同，要么floor相同，curRequest属性代表当前电梯需要服务的请求。当curRequest完成后，从path里取出第一个请求作为curRequest，直到path里的请求取完，该passenger到达目的地。

对于电梯换乘的方法，我让InputHandler、Schedule、Elevator共享inputQueue，当一个电梯完成了passenger的curRequest后，如果path里还有请求，则把该passenger放回到inputQueue，并通知Schedule再次分配该passenger给对应电梯，处理下一个path里的请求。对于新增电梯时，我采用了半动态的更新passenger，InputHandler负责启动电梯并给每个电梯配置子队列，所以其掌握所有电梯和其子队列的信息，所以当由新电增电梯请求时，InputHandler重新计算每个电梯子队列里passenger的路径，然后更新每个子队列。

对于通知线程结束的方法，利用一个计数器记录所有乘客，当Schedule把乘客分配出去后，计数器加1，电梯完成该乘客curRequest后，计数器减1，这样保证了inputQueue为空时，计数器不为0，需要换乘时，计数器为0时，inputQueue不为空。

乘客的分配思路和第二次作业相差不大，主要是分配给横向电梯时需要注意可达性问题，然后选择每个电梯子队列加上已经在电梯里的乘客人数最少的分配。

三、同步块设置和锁的选择

三次作业中都采用同步块的方式，对于共享的资源类，如inputQueue，requestTable把方法设置为了同步方法，即把托盘打包成了一个类，内部方法都是加synchronized的同步方法。这样对于单次的增加资源或者取走资源是能够满足同步操作的，但对于遍历操作是有风险的。所以在电梯线程中，当我需要遍历requestTable检查电梯请求时，都需要加上相应对象的锁，因此在电梯类中，很多地方加上了同步控制块。第三次作业中，每个电梯和对应的requestTable配对，所以我设置了一个ArrayList<ConcurrentHashMap<Elevator,RequestTable>>的结构，不过在把乘客送到合适的requestTable过程中，也需要进行遍历操作，因此也需要设置同步控制块进行控制。使用同步控制块亦或者设置锁，其实都是来保证各个线程对共享资源的操作是同步的，即保证每个线程对共享资源的一系列相关操作是原子性的，这样就不会出现线程之间对于共享资源的冲突。不过难点就在于共享资源其内部成员可能是引用类型，可以被其他线程所持有进行改变，另外一种就是进行遍历操作时，我们是否有必要做同步控制。三次作业中，我的同步块设置过于分散，没有很好的封装在共享资源类里面，需要自己时刻警惕某个操作是否有风险。

四、调度器设计分析

第一次作业

第一次作业调度器功能十分简单，输入线程和调度器共享一个输入队列，调度器把输入队列中所有的请求按照A-E楼座分类送到相应的requestTable即可。

第二次作业

第二次作业中，偷懒去保证输入线程和输入队列的纯粹性，我的调度器既要进行电梯请求的分类，又要识别增加电梯请求，从电梯工厂获取电梯并启动电梯。

第三次作业

第三次作业中，我保证调度器只进行分类操作，把乘客按照一定策略送到相应电梯的requestTable。而乘客的路径是由输入线程去产生的，调度器只进行分类操作，不过其还是需要知晓所有电梯的信息。

五、bug分析

第一次作业在互测时被hack了一个bug，这个bug是电梯运行时的一个逻辑实现错误，即我期望电梯里没人并且为空时才把状态设置为WAIT，但是实现是只要没人就把状态设置为WAIT，导致了重复到达同一层。第二次作业没有被hack出bug。第三次作业由于多线程的随机性，导致出了大问题。对于count计数器的操作一时疏忽，直接让各个线程能够进行操作，虽然是对int变量进行加1或者减1操作，但其并不是原子性的，导致了我线程不能正常结束的bug（在ddl前发现，原本以为过了，结果没过，甚至挂了中测，不过强测点居然没有挂很多）。

六、心得体会

这个单元的层次化设计相对来说比较简单，即使随着后面的扩展，总体上架构不会进行太大变化，考虑在三次作业的基础上继续增加复杂性，本质上还是调度器和电梯之间的协调问题，对调度器这一层进行更加精细的分层应该能够有比较好的层次设计。感受最大的是多线程的debug问题，首先，bug真的不一定能够复现。如在第三次作业中，本地测试时，超时的bug我自己一个都没跑出来，包括评测机上出问题的点，但在本地跑半天，还是跑不出。（不知道评测机怎么设置的，似乎更容易找到程序的弱点）在bug分析时，更多的时候是从逻辑上去思考，通过打印一些关键信息观察状态变化，以此发现程序的问题。idea多断点调试的方法实际上操作起来很难进行，一部分原因是线程调度的随机性，一部分是断点设置其实很难加，当问题复杂的时候，比较难以抓住关键地方。