BUAA OO Unit2 电梯调度

这次作业完成了一个开环可选层电梯调度系统。第二次迭代加入了容量限制、多部电梯，第三次迭代加入了电梯楼层分工、增添电梯请求。

1. 系统架构

graph LR MainClass--Requests-->Schedule Executor--Notify-->Schedule Schedule--Update-->Executor MainClass--Create-->Elevators Schedule--Check-->Elevators Executor--Operate-->Elevators Schedule--Adapt-->Method
  • MainClass用于对各个子系统的组装，发送请求至Schedule
  • Schedule用于接收来自MainClass、Executor的信息，更新状态
  • Executor监听Schedule的改变，使用单线程操纵所有电梯，同时将操作结果返回Schedule。
  • Method为策略模块，实现同步控制与策略模块的分离，可以用于适配不同的策略。

2. 同步控制

定时控制

同步控制的主要由Schedule设定，由Executor执行。并发控制的核心为一个阻塞定时监听器，可实现可调整的定时控制。这个模块的实现方法参考了java.utils.Timer。

private long scheduledTime = Long.MAX_VALUE;

public synchronized void retrieveNextAction() throws InterruptedException {
    long curTime = System.currentTimeMillis();
    while (curTime >= scheduledTime) {
        wait(scheduledTime - curTime);
        curTime = System.currentTimeMillis();
    }
    scheduledTime = Long.MAX_VALUE;
    return;
}

  • scheduledTime变量存储下一次计划动作的时间，规定该时间只减不增。即只保障不存在早于scheduledTime的动作。

  • retrieveNextAction为阻塞方法，用于Executor阻塞获取下一次的动作。

  • 存在新的预期执行的动作时，更新scheduledTime，调用notifyAll()，retrieveNextAction重置等待时间/取消等待。

  • 没有设定动作时序队列，每次完成时，需要检索全部可能的动作，并根据执行情况设置下一个scheduledTime。

  • 这样做的主要优势在于没有用到Thread.sleep方法，可以实现任意时刻对请求的及时响应。

另外，除Schedule外，另一个共享变量为Elevator。这里Elevator类仅用作记录电梯状态，提供改变电梯状态的接口。所有操作由Executor根据Schedule产生，并在敏感操作（如关门-移动序列）的执行过程中进行了上锁，屏蔽Schedule类的所有请求，保证一致性。

对于电梯移动，在Executor中对Schedule上锁保证安全性。对于人员流动，使用ConcurrentLinkedList定义可执行队列保障安全性，并在电梯移动时清空。Executor请求完成后调用相应方法通知Schedule，根据策略更新预期动作。

UML协作图 （Sequence Diagram）

* 协作图中动作可能不满足正确性，但反应了动作之间的时序关系。

* 2个线程为MainClass主线程和Executor执行线程。Schedule、Elevator为共享变量，被动进行数据调取。

* 还存在Schedule-Elevator之间的调用。

同步控制相关版本迭代

  • 第二次作业：

    • 去除了不必要的分支，简化了定时阻塞器、终止判断的执行流程，取消了不必要的PersonAction包装。
    • Schedule类中增加了notifyPersonCheckedIn，notifyPersonCheckedOut方法，以适应电梯容量受限导致的策略变化。
    • Schedule类内中的电梯相关数据由单一数据转变为列表控制。访问数据时使用电梯索引值访问。
    • Executor类内，每次检测到Schedule类存在新动作时，由检查单一电梯转变为检查全部电梯。实现宏观上的电梯并发效果
  • 第三次作业：
    • Schedule类中增加评判：人员是否需要从电梯中出去。前两次作业中只要满足与人员请求目标楼层相等都要出去。
    • Schedule类中增加方法：AddElevator。在全部数据列表中增加一项即可。
    • 优化代码结构，Schedule类使用泛型访问电梯接口，实现不同种类电梯和对应策略类的匹配。

3. 架构设计

本节以第三次作业的版本为准讨论了架构设计和可扩展性。

需要实现2个接口：IElevator、OperationMethod。

  • OperationMethod需要对canGetIn、canGetOff、nextfloor询问做出答复，接收addElevator、 notifyRequestReceived两个辅助更新请求。
  • IElevator需实现运行时间查询、电梯情况查询、电梯操作、人员操作相关方法。
  • 实际上Elevator类已经实现IElevator，一些特殊种类的电梯可以进行重写通过相关方法实现。同时Elevator的类型可以借助泛型通过Schedule传递到OperationMethod，实现策略类与电梯的一一对应。

第三次作业通过继承的方法已经实现了楼层限制电梯，以及针对3中楼层限制电梯的方法不同方法。

功能-性能平衡

由于采用了策略与调度分离的架构，使得在实现相应功能的同时，为策略的制订保留了很大的空间，同时允许对不同的策略进行试验。但在策略制订的过程中，可扩展性做的不是很好，功能的调整往往需要策略做出较大的调整，在前几次作业中均进行了策略重构，可能也与使用的策略具有较高的特殊性有关。

准则异常

单一责任准则：Schedule类和Executor类是所有请求实现的关键路径，对进一步添加请求不理想，应考虑建立请求接口，将请求执行步骤抽象为【电梯操作-调度更新-时间等待-新的请求】。

接口隔离：应考虑将策略接口拆分成发送策略接口、接受数据改变接口。

需求扩展方法

对于后续的扩展，可以根据扩展的类型进行版本迭代。

  • 级别1：具有不同楼层限制规则的电梯、更新评价方法。

    扩展ElevatorRestricted.Type枚举类型，编写新的MethodTypeD，调整MethodTask3分配策略。

  • 级别2：新的限制规则电梯/楼梯、不定时电梯。

    建立新的Elevator类，重写Elevator相关方法，较大规模的调整MethodTask3分配策略，编写新的MethodTypeD。

  • 级别3：新的请求类型。如：停用电梯、更改请求

    在Schedule类中增添新的方法适配请求，检查Executor类的执行过程是否符合新条件下的请求要求。考虑IElevator、OperationMethod接口中是否需要增添方法适配请求。

    如果请求的类型较多，可以考虑建立请求接口，将请求执行步骤抽象为【电梯操作-调度更新-时间等待-新的请求】过程，在Executor和Schedule中设立相应设施。

  • 级别4：新的调度维度。如：水平电梯

    建立新的调度策略。重构电梯类，将一维操作改为2维，并在所有访问位置进行修改。

4. 度量分析

类复杂度（Weighed Method Complexity）

第一次作业 第二次作业 第三次作业

第一次作业中对2种策略进行了测试，最终选用了略微优化的Als策略。另一种策略过于复杂而且效果不是很好。第二次作业中对ALS策略进行了调整，以适配多电梯，效果类似于LOOK策略，但实现后导致MethodAlsMultiple复杂度过高。第三次作业将策略分成主策略和子策略，类复杂度可以接受，MethodAlsMultiple基本未作修改。

方法复杂度（Cyclomatic Complexity）

第一次作业 第二次作业 第三次作业

这几次作业设计中Executor线程需要完成全部动作的发送，工作量较大，一开始放在了run方法，尽管后来做出了一些步骤的提取，仍旧有很多步骤被留在了run方法中，导致复杂度较高，这个是不恰当的。

另外，在第三次作业中，部分优化方法直接进行了重复逻辑的复制粘贴，在一个方法内引用了较多外部参数，还需要进一步重构。

循环依赖

第一次作业 第二次作业 第三次作业

第一次作业由于分包不太恰当，导致根目录和子包出现了循环依赖，同时策略类和调度器也存在循环应用。第二次作业调整了Timer类的分包，建立了策略类和调度器的共有引用类，解决了这个问题。第三次作业由于子类实现了主类的内部接口，而主类有又持有子类的引用导致循环引用（所以根据规范应该把内部接口放在外部，或者编写额外的工厂类组装主类、子类）。

类结构图

  • 第一次作业：实验了2个方法：ALS和动态规划。PersonAction抽象的不太恰当。Timer类分包不太恰当。
  • 第二次作业：PersonRequest嵌套提供的PersonRequest，用于实现一些特殊/虚拟的的请求。层级关系较第一次作业更好。但Elevator有待进一步抽象。
  • 使用接口-继承的方式进行了迭代更新。层次结构进一步优化。不过MethodTask3和SubMethod关系有待调整（之前已经阐述）。MainClass引用过多，应建立初始化相关类。

5. BUG分析

第一次作业中，中测阶段的bug主要为题目理解不当，没有正确的使用输出包，强测互测没有发现Bug。

第二次作业中，强测互测阶段也没有发现Bug。

第三次作业中，强测阶段没有发现bug，但互测阶段发现了两个较为严重的bug。一个是电梯容量定义错误，然而在之前的中测强测中由于数据较为均匀、稀疏，加上C电梯利用率较少没有被测出来，自测时也没有再做检查。另一个是上电梯后，尽管已经通知了调度器更新，但在调度器更新函数的编写时没有考虑换乘问题，导致换乘时可能出现一个人上两个电梯的情况，在更新函数中加入一个删除相同请求就可以了。这个可能原因是前两次作业调度器编写时内联逻辑过多导致鲁棒性不高，环境改变后忘记了相关内联逻辑。

6. 测试

简易评测样例定时读入类

使用自己编写的ScannerX实现了一个简易的定时输入，满足基本的测试需求。在test模块中，将main函数中的ElevatorInput替换为ScannerX即可测试。定时输入使用sleep进行定时，在第一次调用时初始化，根据当前时间进行修正。

测试策略

  1. 手动数据：构造少量边界性数据
  2. 随机测试：生成一些数据，在时间边界投放。作业3中随机测试偏向于高频生成边缘楼层（如3楼、-3楼、15+楼等）。
  3. 覆盖性测试：覆盖作业3中所有的换乘情况

实际上第二第三次互测中均没有发现其他人的bug，可能是强测成绩比较好分到的屋大佬较多...第一次互测中由于定时输入没有做时间修正导致hack数据时间不准确，没有hack上。

和第一单元测试相比，这次测试评测机搭建更为麻烦一些，不像第一单元直接使用sympy计算就可以验证正确性，同时样例投放也更加困难一些。这导致测试的效率下降了一些。

7. 心得体会

多线程程序

这次是第一次完整地编写多线程协同程序。在并发程序的编写中，需要仔细地考虑冲突问题，但如果对于每一个语句都进行考虑显然是不划算的。一方面是经典模型引入，例如读者、写者问题，生产者、消费者问题的解决方法，一方面是系统架构的独立性。如果将一个大的并发问题拆解成几个独立的链条，仅需考虑链条与链条的并发、链条内部的互访问，便可以“分而治之”，运用相关模型逐个击破。

优化策略

在第一次作业中一开始尝试使用动态规划的思想进行优化，然而实际上效果并不是很理想，而且复杂度很高，后来采用了改进的ALS策略。实际上和缓存机制类似，由于我们并不知道未来可能存在什么请求，因此无法将其转化成背包问题，在请求来临前就实现最优调度。ALS和LOOK等方法看似和动态规划相比不是最优，但和SJF、FIFO等算法类似，都是一种基于已知内容的可行优化策略。

在第二次第三次优化的过程中，基础上采用了ALS算法的定向捎带原则，并借鉴粒子群优化算法的思想，对空闲电梯制定了打散策略，空闲电梯运动方向受到来自于其他电梯，与电梯容量、距离相关的压力的影响，使电梯容量倾向于在电梯运行空间内均匀分布，以减少调度时间期望。同时第三次作业不同种类的电梯制定了单独的策略，一个重要的策略是减少A类电梯空转时间。最终在强测中均获得了99分以上的成绩。

这两个方法还有很大的改进空间。这几次作业优化的主要路线都集中于如何应对未来可能的请求，而对当前已有的请求策略并不是最优。第三次作业的请求分配也存在问题，可能与当前最优偏离较大，但在随机数据情况下偏离不太明显。另一个优化路线是何泽欣同学的基于模拟的估价函数，模拟不同状态下电梯运行时间以完成评判。如果可以建立一个历史与未来的请求相结合的分配方法可能会有更好的效果。

实际上优化一个策略函数是一个比较复杂的问题，特别是针对未来的请求期望。或许可以有一些机器学习的方法，例如梯度下降法加以解决，完成对策略函数的拟合。

P.S.如果针对强测，考虑到助教、同学之间的博弈，均衡应该是完全随机的数据，这个也是打散算法较为重要的原因。

赞 (0)

相关推荐