BUAA_OO_UINT2电梯调度

OO第二单元总结

前言:本单元的作业是用java多线程解决电梯调度的问题,与第一单元单线程程序有很大不同。第一次接触多线程,感觉还挺神奇的,虽然本单元的作业完成的比第一单元要顺利一些,但同时也阻碍了我进一步主动地思考学习新知识,下面现总结一下本单元的内容吧,文末再对学习情况总结。

一、三次作业的设计策略:

  • 第五次作业设计策略:

多线程:

本次作业是单电梯的调度,多线程体现在:输入需求的线程和电梯线程相独立,此外还有主线程控制输入、电梯两个线程的启动。总体的逻辑比较简单,难点主要在于电梯内部的调度,本次作业我采用的是指导书中给的捎带算法。但是评测室发现这个算法在实际数据中性能比较低,所以对此算法我在第二次作业进行了重构。

同步控制:

本次作业我采用的是生产者-消费者模式,输入线程是生产者,电梯线程是消费者,中间的channel就是需求队列,用sychnonized对put和get进行同步控制。由于采用的设计模式比较简单,中间同步控制逻辑也只是简单的对放和取的操作进行同步,所以没有出现死锁的情况。

  • 第六次作业设计策略:

第六次作业相对于第五次:

  1. 增加了两部电梯

  2. 然后电梯运行楼层可以是地下层数

  3. 增加了人数的限制。

由于第五次作业性能分几乎没有,还有几个测试点超时了。所以在第六次作业中我对电梯运行算法进行了重构。由可稍带算法改成了LOOK算法,多线程的设计模式还是沿用第五次作业生产者消费者模式,只不过是消费者由原来的一个变成了三个,同步控制逻辑不必修改。

我是采取在启动程序的同时启动三部电梯,然后每部电梯都是LOOK算法对人进行运送,由于LOOK算法的逻辑比捎带算法要简单很多,所以本次重构所花的时间要比第一次写要少很多。而且在强测中体现出较高的性能。

  • 第七次作业设计策略:

第七次作业相对于第六次的迭代是:

  1. 对电梯进行了分类,

  2. 不同类型的电梯有其特定的停靠楼层。

  3. 而且要求可以动态加入电梯。由于第六次作业算法和架构都很明确。

所以本次作业的迭代比较简单。我认为主要的难点是解决如何换乘的问题。我的解决方案如下:

  1. 可以直达的需求就按第六次作业,直接对其进行运送

  2. 由于三部电梯都在一楼停靠,所以所有换乘需求都能先到一楼,再到其目的楼层,所以我将需要换乘的需求分解成从FromFloor到一楼,再从一楼到ToFloor两个需求,只有完成了第一段路程的需求,才能进行第二段需求。

同步控制和多线程还是延续第五次和第六次的架构,采用生产者-消费者模式和sychornized关键字。

对于动态加入电梯,我用工厂模式来实现不同种类电梯的创建,采取第六次作业的策略,每当电梯创建的时候就将其启动。

二、第三次作业的结构和可扩展性分析

第三次作业结构:

第三次作业是对第二次作业的迭代,结构相较于第二次,扩展了电梯类,增加了ElevatorFactory

MainClass---主线程

Channel----需求队列&调度器

inputRequest----需求输入线程

ElevatorA----A类电梯线程

ElevatorB----B类电梯线程

ElevatorC----C类电梯线程

ElevatorFactory----电梯工厂


下面从SOLID原则的五个方面分别审视自己最终的(第三次作业)设计:

  1. S——Single Responsibility Principle(单一职责原则):

    在面向对象编程中,单一功能原则(Single responsibility principle)规定每个类都应该有一个单一的功能,并且该功能应该由这个类完全封装起来。所有它的(这个类的)服务都应该严密的和该功能平行(功能平行,意味着没有依赖)。

    输入线程类和主线程类的S原则做的比较好,而channel中既有需求队列,又兼顾了调度器对需求队列的管理,略显臃肿。电梯类的设计策略是每到一层就检查有没有可以上来的乘客,所以电梯类相当于也和调度器有一定的耦合。这是第六次作业遗留下来的缺点,第七次作业由于迭代后取得了较好的性能效果,也就没有对此进行重构。

  2. O——Open Closed Principle(开闭原则):

    开闭原则规定“软件中的对象(类,模块,函数等等)应该对于扩展是开放的,但是对于修改是封闭的

    这个原则我做的不够好,主要是没有考虑后续扩展功能的要求,电梯类的主算法不必做大的修改,而如果新的请求要求电梯某些特定行为发生变化,那么肯定需要对电梯类做比较大的修改。主线也是这样。我觉得开闭原则要在全面了解需求和需求扩展方向之后才能很好的把握住。

  3. L——Liskov Substitution Principle(里氏替换原则):

    “程序中的对象应该是可以在不改变程序正确性的前提下被它的子类所替换的”的概念。

    参考契约式设计

    本次作业我几乎没有采用继承的方法,所以本原则基本上没有在本单元作业中很好地体现。

  4. I——Interface Segregation Principle(接口分离原则):

    “多个特定客户端接口要好于一个宽泛用途的接口”

    本单元中这个原则的体现是input和elevator线程实现于runnalbe接口。除此之外就没有其他接口,方法都是在类的内部实现的,这样不利于扩展,特别是当需要给电梯类增加方法的时候。

  5. D——Dependency Inversion Principle(依赖倒置原则):

    认为一个方法应该遵从“依赖于抽象而不是一个实例”

    这一点也是我做的不好的地方,我所有的方法都是放到了类的内部,而不是实现于一个接口,方法严重依赖实例。

总的来说,我在本单元使用的类相对较少,没有采用多级调度,而是电梯自行抢人,所以类的种类不多,这也导致了类内部方法冗杂,整体臃肿。

三、基于度量分析自己的程序结构

第五次作业

代码复杂度分析:

BUAA_OO_UINT2电梯调度

可以看到,电梯线程的run方法复杂度很高,这是因为
1,我的电梯类需要
2,我把大量细节在run中实现,导致其很臃肿

应该改进的是要在run里面实现整体的框架,而具体的实现细节放到其他函数中,这在我下一次作业的重构中有所体现

UML类图:
BUAA_OO_UINT2电梯调度

UML协作图:

BUAA_OO_UINT2电梯调度

从UML的类图和协作图中可以看到,我的类的逻辑很简单,就是按照生产者-消费者模式创建的。
其中inputPeople线程是生产者,elevator是消费者。

第六次作业

代码复杂度分析:
BUAA_OO_UINT2电梯调度

可以看到,本次重构之后,elevator的run方法复杂度依然很高,但是同上一次相比,本次作业虽然比上次复杂,但是run的复杂度却
比上次有所减少。

UML类图:
BUAA_OO_UINT2电梯调度

UML协作图:
BUAA_OO_UINT2电梯调度

本次电梯相较于上次仅仅是增加了两个,而我的重构是在电梯内部实现的,程序的总体运行逻辑还是依照生产者-消费者模式
只不过这次是多加了两个消费者。

第七次作业

代码复杂度分析:

BUAA_OO_UINT2电梯调度

本次我构建了三个电梯类,完全是复制粘贴,当时做的比较急,实际不需要三个电梯类,只需要一个,然后把id等属性传进构造函数就好了
所以看到三个电梯类的复杂度是一样的,而且由于是上次作业的迭代,所以run函数基本上没有修改,复杂度同上次相同。

值得注意的是,本次作业的buffer复杂度有很大的提高,是因为我把换乘的操作以及调度器的操作全都塞进了buffer中。
这里可以新建一个controller类,来使类的功能更加单一。

UML类图:
BUAA_OO_UINT2电梯调度

UML协作图:

BUAA_OO_UINT2电梯调度

本次的迭代主要集中在新加电梯类以及换乘上面,上层的架构没有改变,由于没有调度器作为god类,所以逻辑很简单。

四、分析自己程序中的bug

第五次作业在强测中出现了超时的错误,这是由于采用了不完全的捎带算法,如果数据量很大的话,有可能退化为FCFS算法,所以有个别点出现了超时的错误。不得以在第六次作业进行了重构

重构后的第六次和第七次作业不仅电梯运行的逻辑简单了,而且在强测和互测中都没有出现bug,性能也比较好。

五、分析自己发现别人程序bug所采用的策略

第五次作业是我第一次接触多线程,对这个怎么在给定时间对数据输入还是很懵,互测我采用的就是在0时刻输入大量随机数据的形式对互测成员hack,取得了2次有用的hack。

第六次由于时间紧张便没有积极hack,互测完成后发现本次的作业在强侧和互测中表现都很优秀,没有出现bug

最后一次作业,我打算实现自动评测机,但是没有最终完成,只实现了生成带有时间戳的测试数据和输出结果的python程序,用shell脚本生成了大量需要换乘的数据包用于hack,测试的效果也很明显,得到11次有效的hack,房间中六个人中有五个人用我的数据出现了bug。

我只是简单的看了同房间内人员的代码结构,并没有进行白盒测试,黑盒测试虽然没有针对性,但是可以自己构造边缘数据,可以检测出大多数人很多共性的bug。

分析本单元的测试策略与第一单元测试策略的差异之处

本单元引入了多线程的概念,与第一单元相比,测试上有很大不同,总结如下

  1. 需要考虑程序某个时刻的状态,而不像第一单元仅考虑结果
  2. 需要在不同时刻对程序输入
  3. bug的不可重现性,导致debug难度加大
  4. 自己难以构造测试用例

六、心得体会

通过本单元的学习,我对多线程、设计模式、设计原则有了一定的了解,但是几乎所有的知识都是浅尝辄止的,没有深入地探究。虽然顺利完成了既定的作业,测试中的取得了不错的分数,但是还是感觉自己学到的太少了,应该更主动地去自己探究一些问题,比如死锁,我的作业中同步控制比较简单,三次作业都没有出现死锁的情况,所以我也没有深究这个问题。到最后一次研讨课才发现原来这个问题还是很普遍的,也有一定的解决策略。就感觉自己好像少学了很多东西

本单元oo结束之后学期就过半了,总觉得疫情在家期间自己处于一个"灰色"的学习状态。没有在学校有积极性。我读书时看到一句话说:大多数人分不清劳动努力的区别,以为自己很努力了,其实不过是在劳动罢了。我觉得自己这段时间的状态就像只是在劳动,没有自己主动去学习知识,而是被推着走。其实仔细想想,既然环境不能改变,只有改变自己的心态,不能用环境作为自己堕落的借口就不去努力。

眨眼学期就过半了,我不想一学期过去回头看自己一路走来却一无所获。我希望自己对待知识能够再严谨一点,学习自己更主动一点,在家能够再自律一点。就算累也要一天有一天的收获

上一篇:BUAA-OO-最后单元总结


下一篇:[HNOI 2015]落忆枫音