BUAA_OO_第二单元总结

OO第二单元总结

摘要

  • Homework5:本次作业的基本目标是模拟单部多线程电梯的运行。

  • Homework6:本次作业要求模拟多部同型号电梯的运行,并要求能够响应输入数据的请求,动态增加电梯

  • Homework7:本次作业要求模拟多部不同型号电梯的运行。型号不同,指的是开关门速度,移动速度,限载人数,以及最重要的——可停靠楼层的不同。

前言

本单元的作业主要是多线程相关,同时题目有了更加实际具体的背景(电梯)后,编写代码时,工程的意识也相比之前更加强烈。三周整体的趋势是一个由难到易的过程,从刚开始第一周的苦苦挣扎到最后的顺利结束,体会万千。

第一次作业

设计策略

第一次作业是自己初次进行多线程相关的代码编写,刚开始上完理论课,加上自行搜索资料阅读后并没有产生清晰的认识。在实验课的训练后对多线程有了大致的初印象,但到自己动手还是困难重重。不过第一次作业结构比较简单,最后还是有惊无险地在周日凌晨两点完成了基本功能,下午一点完成了debug。可能是新手比较谨慎,编码过程中对线程的处理格外小心,所以并没有遇到诸如轮询或者死锁等问题。

思路是使用“生产者-消费者模式”,输入线程为生产者,电梯线程为消费者。本次没有设计调度器,直接由电梯从队列中获取需求,并完成上行下行、接人放人等操作。调度策略类似look算法。类似是因为我也只清楚look的大致思想,所以最后的实现还结合了自己的一些思考和修改。

结构分析

  • UML图

BUAA_OO_第二单元总结

  • UML协作图

BUAA_OO_第二单元总结

  • 度量分析

BUAA_OO_第二单元总结

本次作业中,dealRandomRequest写的比较复杂,其中的一些功能没有进行比较好的封装,主要原因是写的过程中发现本来实现的其他方法不足以较好地处理需求,导致该方法中还补充了很多琐碎的细节。实现进人的passengerIn方法也基本上全部飙红了,因为里面还有开关门和修改最远目的地等进人之外的操作。

同步块设置和锁的选择

本次作业仅有RequestsQueue为线程安全类,使用synchronized加锁。线程安全类RequestsQueue中维护了requests的ArrayList。

Bug分析

中弱测时发现了一个bug,就是最初的算法设计没有考虑到达最远目的地时,对于当前层请求的相关处理,添加了thisFloorIn方法后修复了此Bug。

强测中出现了一个比较离谱的Bug,我的电梯在1层接人时,没有人数限制。复查代码时,我发现了如下的离谱内容。

if (req.getFromFloor() == 1 /*&& this.passenger.size() < 6*/)

我想不到任何理由为什么自己会把写好的容量限制判断给注释掉。教训就是下次深夜写代码一定慎重,说不定就把重要内容莫名其妙注释掉了,同时,完成作业后最好也大致通读一下自己的代码,防止出现奇怪的手误。

本次互测未被hack。

Hack策略

本次采用了手动构造测试数据的策略,但是尝试构造了极端数据,仍未成功。

房内的成功案例是电梯人满仍上人和到达目的地未下人,如果去仔细读代码,可能会找出这些bug,但我也是看了一两个同学的代码就放弃了。读别人的代码是真的不好读orz。如果房友认真读了我的代码,应该也能比较容易地发现我注释掉容量限制的手误,可惜他们没有。

第二次作业

设计策略

第二次作业刚动手时也比较茫然,多部电梯的引入导致了共享对象的增加,对多线程仍未完全掌握的我在这里遇到了不少麻烦。

在考虑架构时,我首先想到的是发挥电梯的主观能动性,实行抢人策略,这样性能较好,同时也不需要对已有架构进行大的改动,只要所有电梯共享请求队列就是了,但最后还是遇到了不少问题。

首先是新需求的引入导致了所有电梯的争抢,最后的结果必然是一个电梯抢到,虽然一定程度上提高了效率,但是浪费了大量的电梯资源,虽然本题性能中没有考虑电梯的无意义运行,但显然这样的电梯内卷是不科学的。其次,对同一对象的多次共享大大增加了线程安全的处理难度,我的第一个版本由于线程不安全,只有抢到人的电梯可以正常运行,其他的电梯会”恼羞成怒“,要么上天,要么入地。

这个时候,我选择了改变思路。新思路说来也不巧妙,只是暴力,就是使用朴素的hash思想,把人的id对电梯数取模,塞给电梯。科学的集权,可以一定程度上提高效率,这次就让调度器当一次皇帝。如果新增电梯,就再加个队列,更新一下电梯总数。

新增了Dispatcher类,RequestList类,并修改了电梯内部分锁,其余部分如电梯运行、采用的“生产者-消费者模式”均未改变。

为什么不去设计新的、可能更加科学的调度算法?因为第一次作业讨论区一位助教的教诲我深以为然,大意就是复杂的策略意味着复杂的架构。将电梯的状态读入调度器是我本来没有,并且添加过程较为繁琐的功能,既然如此,不如保持其纯粹性,防止弄巧成拙。

结构分析

  • UML图

BUAA_OO_第二单元总结

  • UML协作图

BUAA_OO_第二单元总结

  • 度量分析

由于本次作业与第一次架构基本一致,所以度量分析情况也基本没有改变。但是新增的Dispatcher类的run方法CogC较高,分析后发现可能是有比较繁杂的判断结束信号的条件。

同步块设置和锁的选择

本次作业,RequestsQueue和RequestList为线程安全类,使用synchronized加锁。

生产者和调度器共享了RequestsQueue,而调度器和消费者共享了RequestList。

线程安全类RequestsQueue中维护了requests的ArrayList,RequestList中维护了list的ArrayList。

Bug分析

这次遇到了比较玄学的bug,就是不规则的RTLE。中弱测中同一份代码,4次提交中,有两次是不同的单个测试点RTLE,另外两次又是正常ac。强测最后的结果也是有一个点出现了RTLE,可是本地无论怎样测试都无法复现。重新提交后,又会随机出现“旧的ac,新的RTLE”的奇怪现象,但是再次尝试后又全部ac了。看到群里也有不少同学有这样的现象。可能确实是多线程不稳定,但最后也没有查出自己的问题在哪里。

本次互测未被hack。

Hack策略

本次仍采用了手动构造测试数据的策略,依然未成功。互测房内,也没有成功案例。

但是如果让我hack我自己,可以针对我的处理,尝试让所有乘客id模电梯数相等,并且构造相对极端的请求,或许可以卡到超时?

个人认为到了这一步,测评机的大量随机数据可能已经干不倒各位的程序了,或许阅读后蛇打七寸才是更合适的策略?

第三次作业

设计策略

动手之前,听到大佬讨论换乘思路热火朝天,甚至各种训练炼丹都来了,属实有了不少心理压力。看看本次的作业要求,不同电梯有不同的特色,确实容易让人想到换乘,以此对电梯性能进行最大程度地剥削。但我还是觉得,换乘不会是最优解,现实生活中,哪有人坐电梯换乘啊喂!倘若有需求必须要换乘才能完成,那自然无可非议,但是那个1-20全层停靠的1号电梯好好的在那里等着你坐呢,为啥要为难自己。更何况,本题的性能分有考虑乘客等待的时间,所以换乘在带来更快速度的同时,也延长了等待时间,增加了风险。

所以,依然是调度器给电梯塞人。来去都是1-3、18-20,直接塞到3号电梯,剩下的如果来去都是奇数,全去2号,最后的一部分,只能去1号电梯了。电梯内新增了容量属性,通过容量线性映射了运行速度,轻微地简化了代码,省去再多写几个电梯类的麻烦。

结构分析 & 同步块设置和锁的选择

此部分与第二次作业完全一致,故不再赘述。

Bug分析

本次中弱测、强测、互测均没有出现bug。

Hack策略

还是没有成功···房里有个大佬下了6刀,一刀未中,惨。多线程,彳亍!

忙着os所以这次的互测基本上就摸了。

可拓展性分析

  • 单一责任原则:生产者线程只负责读入请求,并将其加入请求队列或添加电梯;调取器仅负责将请求队列中的请求分配给电梯各自的队列;消费者线程负责处理请求。

  • 开放封闭原则:三次均使用第一次作业设计的电梯,基本无需改动。生产者线程只是根据题目的要求进行了小的修改。调度器为第二次作业新增,第三次只是修改了部分逻辑。若进行拓展,也只需要修改调度器。

  • 里氏替换原则:未涉及继承。

  • 接口分离原则:仅有线程实现Runnable接口。

  • 依赖倒置原则:各类相互依赖情况较少,利于拓展。

心得体会

关于线程安全

线程安全确实是多线程单元永恒的命题。不考虑清楚,每一步都战战兢兢。

本次代码上没有出现过严重的线程安全问题,可能是因为自己加锁比较节制理性。该加的一个不少,不该加的也不要手贱。关于避免轮询,就是按部就班照着教程理解后处理的,所以也没有出现这种情况。

关于层次化设计

本单元的架构,我从最开始的思路就是让电梯功能尽可能完备,其余部分尽可能简洁。最后证明,这样对层次化设计来说是科学的。所以本单元除了第一次作业,第二次和第三次的代码量都较少。

这次也是真正有意识开始进行整体的设计,对多种方法进行了分析和取舍。最后根据可拓展性而决定了最后的架构。同时,整个单元“生产者-消费者模式”贯穿其中,也是一个深入理解并应用的过程。

其他

相比第一单元,本单元的作业都在强测中取得了不错的成绩,思考了一下自己的塞人策略好像不算太科学,所以最主要应该还归功于电梯运行设计合理。

“君上试想,事有法可依,人依法办事。朝野便会自行运转,就算出了平庸君王,只要秦国法度不改,国家照样不会变形糜烂。若有一代雄主崛起,加之秦国强大国力支撑,完成统一大业,便指日可待。”

“法治爱民,不在其心,而在其行。”

——《大秦帝国之裂变》

写到这里,不知为何,就想起了商鞅的台词。

我觉得这其实也算符合世界的规律。我们只可能保证机械的高效,而无法保证使用者的使用方法。就像商鞅呕心沥血设计了一套科学严明的法度,却无法左右君王内心的想法。乘客在选择电梯的时候,不可能去做你代码里精心设计的那些准确计算,所以真正生活中的应用场景,反而更接近于均分。

最后的最后,结队学习使人快乐。ljygg在第一次作业debug过程帮了我很多,我也真正学到了很多东西,比如提取样例中切中你bug的有效部分,而不是无脑全部测试后慢慢筛选。另外几个好兄弟的思路交流,也对进一步的理解有巨大帮助。

第二单元完结撒花!

上一篇:[BUAA-OS]第二单元(电梯)博客总结


下一篇:BUAA_OO_2021_第二单元总结博客