oo-Unit2
前言
又是三周的oo,终于结束了电梯的单元。
第二单元的编程难度和debug难度对我个人而言都远高于第一单元,真的是好费劲,不过不管咋样,也还算是顺利结束了这一单元的学习吧。
下面,我将分别对这三次作业进行分析。
第一次作业
题目描述
我们要模拟的电梯系统是一个类似北京航空航天大学新主楼的电梯系统,楼座内有多部电梯,电梯可以在楼座内1-11层之间运行。系统从标准输入中读入乘客请求信息(起点层,终点楼层),请求调度器会根据此时电梯运行情况(电梯所在楼层,运行方向等)将乘客请求合理分配给某部电梯,然后被分配请求的电梯会经过上下行,开关门,乘客进入/离开电梯等动作将乘客从起点层运送到终点层。
基本思路
第一次作业还算比较容易,只需要根据生产者-消费者模型,构建输入池,请求池,调度线程以及电梯线程,并编写策略类实现电梯运行策略即可。
具体实现
在整体构建上,我是参考上机实验中的代码框架,进行对应的修改。
在策略选择上,我根据往年学长经验选择了LOOK策略,在性能上强于ALS算法。
在调度上,由于第一次有具体电梯的编号,所以只需根据这些编号将总请求池的请求分到对应六个电梯的分请求池中即可。
由于第一次作业对于锁的认识还不是很深刻,所以我只是在需要读写共享对象时的方法外面加锁,并没有针对具体对象加锁。
UML图
Bug分析
本次作业强测没有出现bug,但互测中出现了bug。
bug出现在策略类,由于我是在开门的时候判断电梯是否需要转向,但是忽略了一种情况。就是当电梯开门时判断不需要转向,但是在开门之后本层出现一个需要电梯转向的请求,这时候就会发生电梯飞天遁地的情况。
改正方法也很简单,只需要在电梯关门时判断是否转向即可。
第二次作业
新增需求
- 请求不再有电梯编号,需要自己设计调度方法
- 新增
reset
重置请求
基本思路
整体架构和第一次作业一样,需要在调度器里增加调度方法,同时增加对reset
请求的处理。
具体实现
- 调度方法:我并没有采取很多同学使用的影子电梯的策略(担心写出bug),于是自己写了一个调度方法,实现大概如下:
- 首先判断当前是否有可以分配的电梯(如果一个电梯在重置或者他的请求队列大于电梯容量,那么我就判断这个电梯当前是不能分配的),如果没有可以分配的电梯,我们调度器线程wait等待唤醒。
- 有分配的电梯后,优先判断可以顺路捎带的电梯。
- 没有顺路捎带的电梯,那么我就看看当前的电梯现有的请求是否可以一趟跑完(就是不转向),如果可以那我就把请求分给离他最近的电梯。
- 如果以上条件都不满足,那我就把请求分给当前请求最少的电梯。
- reset实现:首先在输入类判断是正常电梯请求还是重置请求,如果是重置请求就调用
schdule
中分配重置请求的方法,并由该方法将对应电梯的needReset
标记置1,同时电梯中run方法的最开始判断needReset
是否为1,若为1则进行重置。当电梯发生重置时,我就开门把当前电梯中的人全放出来,如果放出来的人还没有到达目标楼层,那我就把他和该电梯请求表里的请求共同打回总请求池重新分配,并修改请求发出楼层为当前楼层。 - 对于锁的设计,本次作业一开始我依然像上次一样只对方法加锁,但很快发现了这样无法处理所有的并发情况以及会出现非常多的死锁现象,于是我将所有的锁改成对单个对象加锁。
UML图
Bug分析
本次作业强测大失败,由于赶上清明假期,我没有很好的检查死锁的情况,导致在强测中出现了很多RTLE的情况。
于是在Bug修复中我使用了printf和调试暂停的方法找到发生死锁的位置,同时我尽量避免嵌套锁的情况,对每次加锁的位置进行判断,全面修改。
当然这个过程真的痛苦,一开始我为了避免死锁删除了大量的锁,但又发现出现了并发问题,只好再去添加锁,反反复复改了好多遍,最后才顺利全部修复。
第三次作业
新增需求
- 新增双轿厢电梯重置请求和双轿厢电梯
基本思路
对于自定义函数的改变很简单,就是在替换的时候再调用一下就好
**导因子我是通过化简后对需要求导的多项式的每个单项式分别进行求导处理,因为单项式有通项形式,所以实现较为容易
具体实现
- 对于双轿厢电梯的实现:我是新建了双轿厢电梯类,在这个类里有两个电梯线程,同时将这两个电梯都放在schdule类中总电梯池里来分配请求。对于每个双轿厢电梯,我共用一个锁来避免上下两个电梯相撞。
- 对于双轿厢重置,我依然是和上次类似,发生重置就把当前电梯中的人全放出来,和请求表里的请求共同打回总请求池重新分配
- 由于本周的一半时间都在de上一周的Bug,所以对于调度方法也没有再优化,仍然是采用上一周的调度方法,这也导致了本次作业的性能相对拉胯。
UML图
Bug分析
本次作业依然出现了一个死锁bug(评测机测了200条数据也没发现我就以为没问题了)
debug方式依然是和上次类似
对于房内其他同学的hack依然是和上次一样,在49.9秒加入六个电梯的重置并放入一堆请求来卡120秒的时间。
心得体会
这周作业真的很难,尤其是debug,对于死锁这种复现不了的Bug真的让我de起来毫无头绪,只能结合printf和观察代码来改正。同时由于前两周对于锁的理解没有那么充分,也导致出现了很多bug。
但是当第二单元真的结束的时候,也会觉得这三周过得好快。我也在这三周学到了对于线程安全和并发性的处理办法,同时也让我的debug能力进一步提升。同时阅读讨论区中别人的博客,也会让我恍然大悟收获满满,希望再接下来的两个单元里我可以继续探索,继续精进我的设计,一点点进步
这就是我的第二单元总结了,oo第二单元完结,撒花!