电梯也能无为而治——oo第二单元作业总结

时间:2022-09-06 11:10:22

oo第二单元作业总结

一、设计策略与质量分析

第一次作业
设计策略

  在第一次作业之前,我首先确定了生产者——消费者模式的大体架构,即由输入线程(可与主线程合并)充当生产者,电梯线程充当消费者,二者不直接交互,而是在Controller类的成员变量等待队列中不断取出或放入请求以达到交互的目的。而对于调度器位置的考虑,我将其与电梯线程合并,即从宏观上来看,电梯本身不断与请求队列交互,并按照自己的策略决定是否移动、开关门等(这一架构正是后两次作业中无为而治的基础)。在此基础上,添加一些线程结束的判断以及具体实现后,便完成了第一次作业,UML图及协作图如下,是一个标准的生产者——消费者模式:

电梯也能无为而治——oo第二单元作业总结

电梯也能无为而治——oo第二单元作业总结

  而对电梯自身调度策略的考虑,在第一作业中,我使用了自己想出来的弟弟调度策略(主要是因为第一次作业大部分时间都在理解锁和synchronized关键字然后摸了),从强测结果来看效果不尽人意。因此,在与cjb巨佬交流后我决定在后两次作业中均使用基于贪心的调度算法。(图为作业一惨重结果)

电梯也能无为而治——oo第二单元作业总结

质量分析

电梯也能无为而治——oo第二单元作业总结

  就单个电梯而言,这种简单的生产者——消费者模式已经能够完全满足需要,因此类的规模、方法的规模等都能得到有效地控制。第一次作业代码质量出现的主要问题是出现了一些魔数Magic Numbers,是由我对结束线程的hape判断方法导致的(具体来讲,我在初始化里往托盘内存入一个电梯无法达到的楼层的请求,如100层,当电梯发现最近请求为100层,即托盘内无其他请求时则wait,输入线程结束后会删除托盘内这个100层的请求,电梯发现托盘内无请求时会结束),虽然我在第一次作业中已经发现了这个Magic Number的存在,但是由于我不想改大的架构(虽然改这个也不难只是我太懒了),所以在后两次作业中也存在这个魔数的问题。此外,电梯线程run方法复杂度较高也是一个比较大的问题,但是我只能想到这种类似于状态机的模式,没有什么好的改进思路。使用DesigniteJava进行代码质量分析的一些具体结果如下:

电梯也能无为而治——oo第二单元作业总结

电梯也能无为而治——oo第二单元作业总结

电梯也能无为而治——oo第二单元作业总结


第二次作业
设计策略

  第二次作业主要的迭代方向是从一部电梯变成了多部电梯,且增加电梯内人数限制。对于多部电梯的情况,我仍然采用了电梯自行决定行为的方式(即所谓无为而治),即让电梯自己去争夺托盘内的请求(只要锁住托盘就不会出现线程安全问题),然而值得注意的是,若仍然使用作业一中电梯与等待队列的交互方式,则会出现多部电梯争夺一个请求而对其他请求置之不理的情况,性能极差。因此,我在电梯内部新增了一个等待队列用来表示将要被它接的请求(这些请求一定位于同一层,至于实现方法,见下方的调度算法图示)。而对于电梯人数限制,则在相应位置增加简单的判断即可,无较大改动。整体架构依然为最基础的生产者——消费者模式,协作图可视作与作业一完全相同,仅是多部电梯的区别,因此仅给出UML图如下。

电梯也能无为而治——oo第二单元作业总结

  接下来重点介绍这种无为而治的多电梯调度策略,由于没有总调度器,所以采取每个电梯每到一层就与托盘进行一次交互并根据电梯内外情况作出下一步动作的方法,具体实现如下图所示:

电梯也能无为而治——oo第二单元作业总结

  这种调度算法整体上采用的是贪心的思路,虽然由于没有顶层调度器的原因而无法做到最优的请求分配策略,但从强测结果来看这种策略对于纯随机数据的效果还不错。

电梯也能无为而治——oo第二单元作业总结

质量分析

电梯也能无为而治——oo第二单元作业总结

  第二次作业沿用第一次作业的架构,然而,在题目背景较为复杂的情况下,仍然使用调度器和电梯合并的架构会使得电梯类本身复杂度过高,即其不仅需要和托盘进行交互,使用较为复杂的方法策略决定行动方式,同时还作为电梯线程需要执行输出、wait、维护等待队列等一系列操作。站在现在的角度来看,若是能将调度器和电梯本身进行解耦,不仅能解决这个电梯类过于冗杂的问题,还能提升其可拓展性,为第三次作业构造顶层调度器留出空间,避免后文中所提到的那个性能问题。此外,魔数的bad smell在在一次作业中愈演愈烈,为了区别多种状态,我又引入了新的魔数,造成进一步的崩坏。电梯run方法的复杂度过高的问题在这一次作业中也没有得到解决。使用DesigniteJava进行代码质量分析的一些具体结果如下:

电梯也能无为而治——oo第二单元作业总结

电梯也能无为而治——oo第二单元作业总结

电梯也能无为而治——oo第二单元作业总结


第三次作业

  第三次作业主要迭代方向是区分电梯的不同类型,其中最关键的是停靠楼层的区别。在第三次作业放出指导书前,我本以为需要动态增电梯以及用户输入相应电梯可停靠楼层(在这种情况下换乘将必须动态处理,较为麻烦),然而课程组还是比较友好的。在静态规定了各类电梯的可停靠楼层的情况下,分析数据不难发现任意请求均可在一次换乘之内完成,因此一个自然的想法便是静态规定换乘策略(贪心寻找最短路径),当有请求进入时直接改写请求为从fromFloor去换乘楼层middleFloor,当其到达时再往主请求队列中添加其从middleFloortoFloor的请求,这样基本不需要对电梯和托盘进行较大的改动。协作图和调度策略与前两次作业基本相同,UML图如下所示,Pretreatment类是一个较为独立的模块,仅在初始化时调用一次以求最短路径并记录下来,后续使用时直接查表即可。

电梯也能无为而治——oo第二单元作业总结

  然而,这种电梯自行决定行为而没有顶层调度器的架构在性能上有一个较大的问题,在第三次作业中有所体现,即在多个电梯都能够执行某一请求时无法分辨运行速度快和慢的电梯,导致可能是较慢的电梯去执行这一请求,造成性能上的浪费。然而就强测结果来看,这一缺陷在纯随机数据上的体现并不明显。

电梯也能无为而治——oo第二单元作业总结

质量分析

电梯也能无为而治——oo第二单元作业总结

  第三次作业架构仍沿用第二次作业,在题目背景和细节要求进一步复杂的情况下,电梯类代码量进一步增加,已经开始出现方法行数过多以至于必须进行拆分的情况,调度策略的实现也愈发复杂,虽然想法上和前两次作业没有太大差别,但是实现起来更为繁杂,造成电梯类进一步臃肿,然而这是第二单元最后一次作业所以懒没有进行解耦,站在现在的角度来看,不仅需要将调度器和电梯进行解耦,还需要进一步简化调度器的负担,考虑采用多级调度器的形式。此外,魔数的问题和电梯run方法过于复杂的问题也没有得到解决。使用DesigniteJava进行代码质量分析的一些具体结果如下(Bad Smell甚至多到一屏放不下):

电梯也能无为而治——oo第二单元作业总结

电梯也能无为而治——oo第二单元作业总结

电梯也能无为而治——oo第二单元作业总结

电梯也能无为而治——oo第二单元作业总结

  针对第三次作业的架构,特从拓展性和SOLID角度进行分析,具体如下:

  拓展性:关于这一点,我甚至开始出现了疑惑。从代码质量分析结构来看,这种耦合度高、方法复杂度高的代码可拓展性应该并不好,但实际上我在第二、三次作业的迭代只花了几个小时便完成了。我认为一个可能的解释是第二单元的迭代并没有像第一单元那样跨度较大,反而是较为温和的,因此实际上我的架构并没有做真正的拓展。而若真正增加较为复杂的拓展,比如删减电梯等,我的架构修改起来将会比较麻烦。

  SRP:很显然,我的架构完全是反Single Responsibility Principle而行之,我为了使得架构从外部表现为最基本的生产者——消费者模式,而将调度器和电梯合并,造成电梯类职责众多,无疑是犯了大忌。

  OCP:如果忽略掉我的架构完全不符合SRP原则这一事实,则其实在Open Close Principle上做的还差强人意,无论是第三次作业中的静态换乘策略,还是电梯调度器的调度策略,都做到了模块化(虽然在同一个类里面),这也是我在两次迭代中修改较小的原因之一。

  LSP、ISP、DIP:本次作业我的架构中没有使用接口和继承,不予评价。


bug分析

  由于对于线程安全相关问题的考虑较为完备(全锁上),且在中测截止前进行了大量自动化随机数据测试,因此三次作业强测与互测中均未出现bug。

互测策略

  本单元作业的互测依然从覆盖性和针对性两方面入手:覆盖性测试依旧使用自动化评测机,值得注意的是,与第一单元作业不同,这一单元测试单个数据所需要的时间更长(一般为几十秒),若仍采用单线程评测机则在互测中效率极低,常常需要几分钟所有人才能跑完一个数据,难以接受,因此需要搭建多线程的评测机(感谢wpb巨佬)。根据我和一些同学的测试经历来看,多线程的评测(特别是线程数较多的时候)更容易暴露出程序线程不安全的问题,我认为这也是很多同学本地测没有问题而交上去就错的原因所在。针对性测试样例主要形成于自己对指导书一些细节的理解,以及在自己开发过程中所遇到的一些问题,较为琐碎,不再赘述。

  然而仅在第一次作业互测中发现了一个线程安全bug且由于不稳定复现并未Hack成功。

心得体会

  本单元主要内容是多线程的理解与应用以及生产者——消费者模式的应用。仅就这三次作业而言,与第一单元相比,理解上的难度虽略有提升,但代码量有了很大的缩减(也可能是我架构太垃圾的结果),两次迭代所需的改动也不是很大,总体而言我认为比较简单。然而,抛开电梯这一作业来看,多线程的思想与相关操作不仅重要、应用广泛,而且易于出错,错误往往也难以复现,是名副其实的重点与难点。可以说,这一单元的学习仅仅是对多线程的入门教学,对这一部分内容的学习与思考将是永无止境的。

  本单元三次作业中我都仅使用了最基础的生产者——消费者模式,使得整体架构看起来较为简单,且避免了一系列奇奇怪怪的线程安全问题,整个过程中没有遇见过死锁的问题,但是,这种表面上简单的结构的背后,却是方法的大量耦合,使得整个架构较为臃肿,拓展性较差,魔数的引入更是雪上加霜。在今后的学习中,我应该对此类问题提高注意,争取更好的代码架构。

  同时,这一单元大大提高了我对python的熟悉程度(从入门到放弃),由于我的架构较为简单且在三次作业中并未做大的修改,因此往往两个小时内就能完成一次迭代,甚至出现了一周内搭建评测机比迭代作业花费时间更长的情况,再次感谢wpb巨佬对我的相关指点,pbnb。


限于笔者水平,本篇难免有纰漏之处,敬请各位大佬在评论区进行斧正。若有对这种无为而治的架构有相关思考或疑惑的大佬也欢迎同我一齐讨论,以上。