这次作业完成了一个开环可选层电梯调度系统。第二次迭代加入了容量限制、多部电梯,第三次迭代加入了电梯楼层分工、增添电梯请求。
同步控制的主要由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,根据策略更新预期动作。
* 协作图中动作可能不满足正确性,但反应了动作之间的时序关系。
* 2个线程为mainclass主线程和executor执行线程。schedule、elevator为共享变量,被动进行数据调取。
* 还存在schedule-elevator之间的调用。
本节以第三次作业的版本为准讨论了架构设计和可扩展性。
需要实现2个接口:ielevator、operationmethod。
第三次作业通过继承的方法已经实现了楼层限制电梯,以及针对3中楼层限制电梯的方法不同方法。
由于采用了策略与调度分离的架构,使得在实现相应功能的同时,为策略的制订保留了很大的空间,同时允许对不同的策略进行试验。但在策略制订的过程中,可扩展性做的不是很好,功能的调整往往需要策略做出较大的调整,在前几次作业中均进行了策略重构,可能也与使用的策略具有较高的特殊性有关。
单一责任准则:schedule类和executor类是所有请求实现的关键路径,对进一步添加请求不理想,应考虑建立请求接口,将请求执行步骤抽象为【电梯操作-调度更新-时间等待-新的请求】。
接口隔离:应考虑将策略接口拆分成发送策略接口、接受数据改变接口。
对于后续的扩展,可以根据扩展的类型进行版本迭代。
级别1:具有不同楼层限制规则的电梯、更新评价方法。
扩展elevatorrestricted.type枚举类型,编写新的methodtyped,调整methodtask3分配策略。
级别2:新的限制规则电梯/楼梯、不定时电梯。
建立新的elevator类,重写elevator相关方法,较大规模的调整methodtask3分配策略,编写新的methodtyped。
级别3:新的请求类型。如:停用电梯、更改请求
在schedule类中增添新的方法适配请求,检查executor类的执行过程是否符合新条件下的请求要求。考虑ielevator、operationmethod接口中是否需要增添方法适配请求。
如果请求的类型较多,可以考虑建立请求接口,将请求执行步骤抽象为【电梯操作-调度更新-时间等待-新的请求】过程,在executor和schedule中设立相应设施。
级别4:新的调度维度。如:水平电梯
建立新的调度策略。重构电梯类,将一维操作改为2维,并在所有访问位置进行修改。
第一次作业 | 第二次作业 | 第三次作业 |
---|---|---|
第一次作业中对2种策略进行了测试,最终选用了略微优化的als策略。另一种策略过于复杂而且效果不是很好。第二次作业中对als策略进行了调整,以适配多电梯,效果类似于look策略,但实现后导致methodalsmultiple复杂度过高。第三次作业将策略分成主策略和子策略,类复杂度可以接受,methodalsmultiple基本未作修改。
第一次作业 | 第二次作业 | 第三次作业 |
---|---|---|
这几次作业设计中executor线程需要完成全部动作的发送,工作量较大,一开始放在了run方法,尽管后来做出了一些步骤的提取,仍旧有很多步骤被留在了run方法中,导致复杂度较高,这个是不恰当的。
另外,在第三次作业中,部分优化方法直接进行了重复逻辑的复制粘贴,在一个方法内引用了较多外部参数,还需要进一步重构。
第一次作业 | 第二次作业 | 第三次作业 |
---|---|---|
第一次作业由于分包不太恰当,导致根目录和子包出现了循环依赖,同时策略类和调度器也存在循环应用。第二次作业调整了timer类的分包,建立了策略类和调度器的共有引用类,解决了这个问题。第三次作业由于子类实现了主类的内部接口,而主类有又持有子类的引用导致循环引用(所以根据规范应该把内部接口放在外部,或者编写额外的工厂类组装主类、子类)。
第一次作业中,中测阶段的bug主要为题目理解不当,没有正确的使用输出包,强测互测没有发现bug。
第二次作业中,强测互测阶段也没有发现bug。
第三次作业中,强测阶段没有发现bug,但互测阶段发现了两个较为严重的bug。一个是电梯容量定义错误,然而在之前的中测强测中由于数据较为均匀、稀疏,加上c电梯利用率较少没有被测出来,自测时也没有再做检查。另一个是上电梯后,尽管已经通知了调度器更新,但在调度器更新函数的编写时没有考虑换乘问题,导致换乘时可能出现一个人上两个电梯的情况,在更新函数中加入一个删除相同请求就可以了。这个可能原因是前两次作业调度器编写时内联逻辑过多导致鲁棒性不高,环境改变后忘记了相关内联逻辑。
使用自己编写的scannerx实现了一个简易的定时输入,满足基本的测试需求。在test模块中,将main函数中的elevatorinput替换为scannerx即可测试。定时输入使用sleep进行定时,在第一次调用时初始化,根据当前时间进行修正。
实际上第二第三次互测中均没有发现其他人的bug,可能是强测成绩比较好分到的屋大佬较多...第一次互测中由于定时输入没有做时间修正导致hack数据时间不准确,没有hack上。
和第一单元测试相比,这次测试评测机搭建更为麻烦一些,不像第一单元直接使用sympy计算就可以验证正确性,同时样例投放也更加困难一些。这导致测试的效率下降了一些。
这次是第一次完整地编写多线程协同程序。在并发程序的编写中,需要仔细地考虑冲突问题,但如果对于每一个语句都进行考虑显然是不划算的。一方面是经典模型引入,例如读者、写者问题,生产者、消费者问题的解决方法,一方面是系统架构的独立性。如果将一个大的并发问题拆解成几个独立的链条,仅需考虑链条与链条的并发、链条内部的互访问,便可以“分而治之”,运用相关模型逐个击破。
在第一次作业中一开始尝试使用动态规划的思想进行优化,然而实际上效果并不是很理想,而且复杂度很高,后来采用了改进的als策略。实际上和缓存机制类似,由于我们并不知道未来可能存在什么请求,因此无法将其转化成背包问题,在请求来临前就实现最优调度。als和look等方法看似和动态规划相比不是最优,但和sjf、fifo等算法类似,都是一种基于已知内容的可行优化策略。
在第二次第三次优化的过程中,基础上采用了als算法的定向捎带原则,并借鉴粒子群优化算法的思想,对空闲电梯制定了打散策略,空闲电梯运动方向受到来自于其他电梯,与电梯容量、距离相关的压力的影响,使电梯容量倾向于在电梯运行空间内均匀分布,以减少调度时间期望。同时第三次作业不同种类的电梯制定了单独的策略,一个重要的策略是减少a类电梯空转时间。最终在强测中均获得了99分以上的成绩。
这两个方法还有很大的改进空间。这几次作业优化的主要路线都集中于如何应对未来可能的请求,而对当前已有的请求策略并不是最优。第三次作业的请求分配也存在问题,可能与当前最优偏离较大,但在随机数据情况下偏离不太明显。另一个优化路线是何泽欣同学的基于模拟的估价函数,模拟不同状态下电梯运行时间以完成评判。如果可以建立一个历史与未来的请求相结合的分配方法可能会有更好的效果。
实际上优化一个策略函数是一个比较复杂的问题,特别是针对未来的请求期望。或许可以有一些机器学习的方法,例如梯度下降法加以解决,完成对策略函数的拟合。
p.s.如果针对强测,考虑到助教、同学之间的博弈,均衡应该是完全随机的数据,这个也是打散算法较为重要的原因。
如对本文有疑问, 点击进行留言回复!!
Java面向对象中:方法重载和方法重写以及区别、 this关键字和super关键字以及区别
网友评论